/*
 This file is part of GNU Taler
 (C) 2021-2024 Taler Systems S.A.

 GNU Taler is free software; you can redistribute it and/or modify it under the
 terms of the GNU General Public License as published by the Free Software
 Foundation; either version 3, or (at your option) any later version.

 GNU Taler is distributed in the hope that it will be useful, but WITHOUT ANY
 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

 You should have received a copy of the GNU General Public License along with
 GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
 */

/**
 * Selection of coins for payments.
 *
 * @author Florian Dold
 */

/**
 * Imports.
 */
import { GlobalIDB } from "@gnu-taler/idb-bridge";
import {
  AbsoluteTime,
  AccountRestriction,
  AgeRestriction,
  AllowedAuditorInfo,
  AllowedExchangeInfo,
  AmountJson,
  Amounts,
  checkDbInvariant,
  checkLogicInvariant,
  CoinStatus,
  DenominationInfo,
  ForcedCoinSel,
  InternationalizedString,
  j2s,
  Logger,
  parsePaytoUri,
  PayCoinSelection,
  PaymentInsufficientBalanceDetails,
  SelectedCoin,
  strcmp,
  TalerProtocolTimestamp,
} from "@gnu-taler/taler-util";
import { getPaymentBalanceDetailsInTx } from "./balance.js";
import { getAutoRefreshExecuteThreshold } from "./common.js";
import { DenominationRecord, WalletDbReadOnlyTransaction } from "./db.js";
import {
  ExchangeWireDetails,
  getExchangeWireDetailsInTx,
} from "./exchanges.js";
import { getDenomInfo, WalletExecutionContext } from "./wallet.js";

const logger = new Logger("coinSelection.ts");

export type PreviousPayCoins = {
  coinPub: string;
  contribution: AmountJson;
}[];

export interface ExchangeRestrictionSpec {
  exchanges: AllowedExchangeInfo[];
  auditors: AllowedAuditorInfo[];
}

export interface CoinSelectionTally {
  /**
   * Amount that still needs to be paid.
   * May increase during the computation when fees need to be covered.
   */
  amountPayRemaining: AmountJson;

  /**
   * Allowance given by the merchant towards deposit fees
   * (and wire fees after wire fee limit is exhausted)
   */
  amountDepositFeeLimitRemaining: AmountJson;

  customerDepositFees: AmountJson;

  customerWireFees: AmountJson;

  wireFeeCoveredForExchange: Set<string>;

  lastDepositFee: AmountJson;
}

/**
 * Account for the fees of spending a coin.
 */
function tallyFees(
  tally: CoinSelectionTally,
  wireFeesPerExchange: Record<string, AmountJson>,
  wireFeeAmortization: number,
  exchangeBaseUrl: string,
  feeDeposit: AmountJson,
): void {
  const currency = tally.amountPayRemaining.currency;

  if (!tally.wireFeeCoveredForExchange.has(exchangeBaseUrl)) {
    const wf =
      wireFeesPerExchange[exchangeBaseUrl] ?? Amounts.zeroOfCurrency(currency);
    // The remaining, amortized amount needs to be paid by the
    // wallet or covered by the deposit fee allowance.
    let wfRemaining = Amounts.divide(wf, wireFeeAmortization);
    // This is the amount forgiven via the deposit fee allowance.
    const wfDepositForgiven = Amounts.min(
      tally.amountDepositFeeLimitRemaining,
      wfRemaining,
    );
    tally.amountDepositFeeLimitRemaining = Amounts.sub(
      tally.amountDepositFeeLimitRemaining,
      wfDepositForgiven,
    ).amount;
    wfRemaining = Amounts.sub(wfRemaining, wfDepositForgiven).amount;
    tally.customerWireFees = Amounts.add(
      tally.customerWireFees,
      wfRemaining,
    ).amount;
    tally.amountPayRemaining = Amounts.add(
      tally.amountPayRemaining,
      wfRemaining,
    ).amount;
    tally.wireFeeCoveredForExchange.add(exchangeBaseUrl);
  }

  const dfForgiven = Amounts.min(
    feeDeposit,
    tally.amountDepositFeeLimitRemaining,
  );

  tally.amountDepositFeeLimitRemaining = Amounts.sub(
    tally.amountDepositFeeLimitRemaining,
    dfForgiven,
  ).amount;

  // How much does the user spend on deposit fees for this coin?
  const dfRemaining = Amounts.sub(feeDeposit, dfForgiven).amount;
  tally.customerDepositFees = Amounts.add(
    tally.customerDepositFees,
    dfRemaining,
  ).amount;
  tally.amountPayRemaining = Amounts.add(
    tally.amountPayRemaining,
    dfRemaining,
  ).amount;
  tally.lastDepositFee = feeDeposit;
}

export type SelectPayCoinsResult =
  | {
      type: "failure";
      insufficientBalanceDetails: PaymentInsufficientBalanceDetails;
    }
  | { type: "success"; coinSel: PayCoinSelection };

/**
 * Select coins to spend under the merchant's constraints.
 *
 * The prevPayCoins can be specified to "repair" a coin selection
 * by adding additional coins, after a broken (e.g. double-spent) coin
 * has been removed from the selection.
 */
export async function selectPayCoins(
  wex: WalletExecutionContext,
  req: SelectPayCoinRequestNg,
): Promise<SelectPayCoinsResult> {
  const { contractTermsAmount, depositFeeLimit } = req;

  if (logger.shouldLogTrace()) {
    logger.trace(`selecting coins for ${j2s(req)}`);
  }

  return await wex.db.runReadOnlyTx(
    [
      "coinAvailability",
      "denominations",
      "refreshGroups",
      "exchanges",
      "exchangeDetails",
      "coins",
    ],
    async (tx) => {
      const [candidateDenoms, wireFeesPerExchange] = await selectPayCandidates(
        wex,
        tx,
        {
          restrictExchanges: req.restrictExchanges,
          instructedAmount: req.contractTermsAmount,
          restrictWireMethod: req.restrictWireMethod,
          depositPaytoUri: req.depositPaytoUri,
          requiredMinimumAge: req.requiredMinimumAge,
        },
      );

      logger.trace(`wire fees per exchange: ${j2s(wireFeesPerExchange)}`);

      const coinRes: SelectedCoin[] = [];
      const currency = contractTermsAmount.currency;

      let tally: CoinSelectionTally = {
        amountPayRemaining: contractTermsAmount,
        amountDepositFeeLimitRemaining: depositFeeLimit,
        customerDepositFees: Amounts.zeroOfCurrency(currency),
        customerWireFees: Amounts.zeroOfCurrency(currency),
        wireFeeCoveredForExchange: new Set(),
        lastDepositFee: Amounts.zeroOfCurrency(currency),
      };

      await maybeRepairCoinSelection(
        wex,
        tx,
        req.prevPayCoins ?? [],
        coinRes,
        tally,
        {
          wireFeeAmortization: req.wireFeeAmortization,
          wireFeesPerExchange: wireFeesPerExchange,
        },
      );

      let selectedDenom: SelResult | undefined;
      if (req.forcedSelection) {
        selectedDenom = selectForced(req, candidateDenoms);
      } else {
        // FIXME:  Here, we should select coins in a smarter way.
        // Instead of always spending the next-largest coin,
        // we should try to find the smallest coin that covers the
        // amount.
        selectedDenom = selectGreedy(
          {
            wireFeeAmortization: req.wireFeeAmortization,
            wireFeesPerExchange: wireFeesPerExchange,
          },
          candidateDenoms,
          tally,
        );
      }

      if (!selectedDenom) {
        return {
          type: "failure",
          insufficientBalanceDetails: await reportInsufficientBalanceDetails(
            wex,
            tx,
            {
              restrictExchanges: req.restrictExchanges,
              instructedAmount: req.contractTermsAmount,
              requiredMinimumAge: req.requiredMinimumAge,
              wireMethod: req.restrictWireMethod,
              depositPaytoUri: req.depositPaytoUri,
            },
          ),
        } satisfies SelectPayCoinsResult;
      }

      const coinSel = await assembleSelectPayCoinsSuccessResult(
        tx,
        selectedDenom,
        coinRes,
        tally,
      );

      if (logger.shouldLogTrace()) {
        logger.trace(`coin selection: ${j2s(coinSel)}`);
      }

      return {
        type: "success",
        coinSel,
      };
    },
  );
}

async function maybeRepairCoinSelection(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<["coins", "denominations"]>,
  prevPayCoins: PreviousPayCoins,
  coinRes: SelectedCoin[],
  tally: CoinSelectionTally,
  feeInfo: {
    wireFeeAmortization: number;
    wireFeesPerExchange: Record<string, AmountJson>;
  },
): Promise<void> {
  // Look at existing pay coin selection and tally up
  for (const prev of prevPayCoins) {
    const coin = await tx.coins.get(prev.coinPub);
    if (!coin) {
      continue;
    }
    const denom = await getDenomInfo(
      wex,
      tx,
      coin.exchangeBaseUrl,
      coin.denomPubHash,
    );
    if (!denom) {
      continue;
    }
    tallyFees(
      tally,
      feeInfo.wireFeesPerExchange,
      feeInfo.wireFeeAmortization,
      coin.exchangeBaseUrl,
      Amounts.parseOrThrow(denom.feeDeposit),
    );
    tally.amountPayRemaining = Amounts.sub(
      tally.amountPayRemaining,
      prev.contribution,
    ).amount;

    coinRes.push({
      coinPub: prev.coinPub,
      contribution: Amounts.stringify(prev.contribution),
    });
  }
}

async function assembleSelectPayCoinsSuccessResult(
  tx: WalletDbReadOnlyTransaction<["coins"]>,
  finalSel: SelResult,
  coinRes: SelectedCoin[],
  tally: CoinSelectionTally,
): Promise<PayCoinSelection> {
  for (const dph of Object.keys(finalSel)) {
    const selInfo = finalSel[dph];
    const numRequested = selInfo.contributions.length;
    const query = [
      selInfo.exchangeBaseUrl,
      selInfo.denomPubHash,
      selInfo.maxAge,
      CoinStatus.Fresh,
    ];
    logger.trace(`query: ${j2s(query)}`);
    const coins =
      await tx.coins.indexes.byExchangeDenomPubHashAndAgeAndStatus.getAll(
        query,
        numRequested,
      );
    if (coins.length != numRequested) {
      throw Error(
        `coin selection failed (not available anymore, got only ${coins.length}/${numRequested})`,
      );
    }

    for (let i = 0; i < selInfo.contributions.length; i++) {
      coinRes.push({
        coinPub: coins[i].coinPub,
        contribution: Amounts.stringify(selInfo.contributions[i]),
      });
    }
  }

  return {
    coins: coinRes,
    customerDepositFees: Amounts.stringify(tally.customerDepositFees),
    customerWireFees: Amounts.stringify(tally.customerWireFees),
  };
}

interface ReportInsufficientBalanceRequest {
  instructedAmount: AmountJson;
  requiredMinimumAge: number | undefined;
  restrictExchanges: ExchangeRestrictionSpec | undefined;
  wireMethod: string | undefined;
  depositPaytoUri: string | undefined;
}

export async function reportInsufficientBalanceDetails(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<
    [
      "coinAvailability",
      "exchanges",
      "exchangeDetails",
      "refreshGroups",
      "denominations",
    ]
  >,
  req: ReportInsufficientBalanceRequest,
): Promise<PaymentInsufficientBalanceDetails> {
  const details = await getPaymentBalanceDetailsInTx(wex, tx, {
    restrictExchanges: req.restrictExchanges,
    restrictWireMethods: req.wireMethod ? [req.wireMethod] : undefined,
    currency: Amounts.currencyOf(req.instructedAmount),
    minAge: req.requiredMinimumAge ?? 0,
    depositPaytoUri: req.depositPaytoUri,
  });
  const perExchange: PaymentInsufficientBalanceDetails["perExchange"] = {};
  const exchanges = await tx.exchanges.getAll();

  for (const exch of exchanges) {
    if (!exch.detailsPointer) {
      continue;
    }
    const exchDet = await getPaymentBalanceDetailsInTx(wex, tx, {
      restrictExchanges: {
        exchanges: [
          {
            exchangeBaseUrl: exch.baseUrl,
            exchangePub: exch.detailsPointer?.masterPublicKey,
          },
        ],
        auditors: [],
      },
      restrictWireMethods: req.wireMethod ? [req.wireMethod] : [],
      currency: Amounts.currencyOf(req.instructedAmount),
      minAge: req.requiredMinimumAge ?? 0,
      depositPaytoUri: req.depositPaytoUri,
    });
    perExchange[exch.baseUrl] = {
      balanceAvailable: Amounts.stringify(exchDet.balanceAvailable),
      balanceMaterial: Amounts.stringify(exchDet.balanceMaterial),
      balanceExchangeDepositable: Amounts.stringify(
        exchDet.balanceExchangeDepositable,
      ),
      balanceAgeAcceptable: Amounts.stringify(exchDet.balanceAgeAcceptable),
      balanceReceiverAcceptable: Amounts.stringify(
        exchDet.balanceReceiverAcceptable,
      ),
      balanceReceiverDepositable: Amounts.stringify(
        exchDet.balanceReceiverDepositable,
      ),
      maxEffectiveSpendAmount: Amounts.stringify(
        exchDet.maxEffectiveSpendAmount,
      ),
    };
  }

  return {
    amountRequested: Amounts.stringify(req.instructedAmount),
    balanceAgeAcceptable: Amounts.stringify(details.balanceAgeAcceptable),
    balanceAvailable: Amounts.stringify(details.balanceAvailable),
    balanceMaterial: Amounts.stringify(details.balanceMaterial),
    balanceReceiverAcceptable: Amounts.stringify(
      details.balanceReceiverAcceptable,
    ),
    balanceExchangeDepositable: Amounts.stringify(
      details.balanceExchangeDepositable,
    ),
    balanceReceiverDepositable: Amounts.stringify(
      details.balanceReceiverDepositable,
    ),
    maxEffectiveSpendAmount: Amounts.stringify(details.maxEffectiveSpendAmount),
    perExchange,
  };
}

function makeAvailabilityKey(
  exchangeBaseUrl: string,
  denomPubHash: string,
  maxAge: number,
): string {
  return `${denomPubHash};${maxAge};${exchangeBaseUrl}`;
}

/**
 * Selection result.
 */
interface SelResult {
  /**
   * Map from an availability key
   * to an array of contributions.
   */
  [avKey: string]: {
    exchangeBaseUrl: string;
    denomPubHash: string;
    maxAge: number;
    contributions: AmountJson[];
  };
}

export function testing_selectGreedy(
  ...args: Parameters<typeof selectGreedy>
): ReturnType<typeof selectGreedy> {
  return selectGreedy(...args);
}

export interface SelectGreedyRequest {
  wireFeeAmortization: number;
  wireFeesPerExchange: Record<string, AmountJson>;
}

function selectGreedy(
  req: SelectGreedyRequest,
  candidateDenoms: AvailableDenom[],
  tally: CoinSelectionTally,
): SelResult | undefined {
  const { wireFeeAmortization } = req;
  const selectedDenom: SelResult = {};
  for (const denom of candidateDenoms) {
    const contributions: AmountJson[] = [];

    // Don't use this coin if depositing it is more expensive than
    // the amount it would give the merchant.
    if (Amounts.cmp(denom.feeDeposit, denom.value) > 0) {
      tally.lastDepositFee = Amounts.parseOrThrow(denom.feeDeposit);
      continue;
    }

    for (
      let i = 0;
      i < denom.numAvailable && Amounts.isNonZero(tally.amountPayRemaining);
      i++
    ) {
      tallyFees(
        tally,
        req.wireFeesPerExchange,
        wireFeeAmortization,
        denom.exchangeBaseUrl,
        Amounts.parseOrThrow(denom.feeDeposit),
      );

      const coinSpend = Amounts.max(
        Amounts.min(tally.amountPayRemaining, denom.value),
        denom.feeDeposit,
      );

      tally.amountPayRemaining = Amounts.sub(
        tally.amountPayRemaining,
        coinSpend,
      ).amount;

      contributions.push(coinSpend);
    }

    if (contributions.length) {
      const avKey = makeAvailabilityKey(
        denom.exchangeBaseUrl,
        denom.denomPubHash,
        denom.maxAge,
      );
      let sd = selectedDenom[avKey];
      if (!sd) {
        sd = {
          contributions: [],
          denomPubHash: denom.denomPubHash,
          exchangeBaseUrl: denom.exchangeBaseUrl,
          maxAge: denom.maxAge,
        };
      }
      sd.contributions.push(...contributions);
      selectedDenom[avKey] = sd;
    }
  }
  return Amounts.isZero(tally.amountPayRemaining) ? selectedDenom : undefined;
}

function selectForced(
  req: SelectPayCoinRequestNg,
  candidateDenoms: AvailableDenom[],
): SelResult | undefined {
  const selectedDenom: SelResult = {};

  const forcedSelection = req.forcedSelection;
  checkLogicInvariant(!!forcedSelection);

  for (const forcedCoin of forcedSelection.coins) {
    let found = false;
    for (const aci of candidateDenoms) {
      if (aci.numAvailable <= 0) {
        continue;
      }
      if (Amounts.cmp(aci.value, forcedCoin.value) === 0) {
        aci.numAvailable--;
        const avKey = makeAvailabilityKey(
          aci.exchangeBaseUrl,
          aci.denomPubHash,
          aci.maxAge,
        );
        let sd = selectedDenom[avKey];
        if (!sd) {
          sd = {
            contributions: [],
            denomPubHash: aci.denomPubHash,
            exchangeBaseUrl: aci.exchangeBaseUrl,
            maxAge: aci.maxAge,
          };
        }
        sd.contributions.push(Amounts.parseOrThrow(forcedCoin.value));
        selectedDenom[avKey] = sd;
        found = true;
        break;
      }
    }
    if (!found) {
      throw Error("can't find coin for forced coin selection");
    }
  }
  return selectedDenom;
}

export function checkAccountRestriction(
  paytoUri: string,
  restrictions: AccountRestriction[],
): { ok: boolean; hint?: string; hintI18n?: InternationalizedString } {
  for (const myRestriction of restrictions) {
    switch (myRestriction.type) {
      case "deny":
        return { ok: false };
      case "regex":
        const regex = new RegExp(myRestriction.payto_regex);
        if (!regex.test(paytoUri)) {
          return {
            ok: false,
            hint: myRestriction.human_hint,
            hintI18n: myRestriction.human_hint_i18n,
          };
        }
    }
  }
  return {
    ok: true,
  };
}

export interface SelectPayCoinRequestNg {
  restrictExchanges: ExchangeRestrictionSpec | undefined;
  restrictWireMethod: string;
  contractTermsAmount: AmountJson;
  depositFeeLimit: AmountJson;
  wireFeeAmortization: number;
  prevPayCoins?: PreviousPayCoins;
  requiredMinimumAge?: number;
  forcedSelection?: ForcedCoinSel;

  /**
   * Deposit payto URI, in case we already know the account that
   * will be deposited into.
   *
   * That is typically the case when the wallet does a deposit to
   * return funds to the user's own bank account.
   */
  depositPaytoUri?: string;
}

export type AvailableDenom = DenominationInfo & {
  maxAge: number;
  numAvailable: number;
};

export function findMatchingWire(
  wireMethod: string,
  depositPaytoUri: string | undefined,
  exchangeWireDetails: ExchangeWireDetails,
): { wireFee: AmountJson } | undefined {
  for (const acc of exchangeWireDetails.wireInfo.accounts) {
    const pp = parsePaytoUri(acc.payto_uri);
    checkLogicInvariant(!!pp);
    if (pp.targetType !== wireMethod) {
      continue;
    }
    const wireFeeStr = exchangeWireDetails.wireInfo.feesForType[
      wireMethod
    ]?.find((x) => {
      return AbsoluteTime.isBetween(
        AbsoluteTime.now(),
        AbsoluteTime.fromProtocolTimestamp(x.startStamp),
        AbsoluteTime.fromProtocolTimestamp(x.endStamp),
      );
    })?.wireFee;

    if (!wireFeeStr) {
      continue;
    }

    let debitAccountCheckOk = false;
    if (depositPaytoUri) {
      // FIXME: We should somehow propagate the hint here!
      const checkResult = checkAccountRestriction(
        depositPaytoUri,
        acc.debit_restrictions,
      );
      if (checkResult.ok) {
        debitAccountCheckOk = true;
      }
    } else {
      debitAccountCheckOk = true;
    }

    if (!debitAccountCheckOk) {
      continue;
    }

    return {
      wireFee: Amounts.parseOrThrow(wireFeeStr),
    };
  }
  return undefined;
}

function checkExchangeAccepted(
  exchangeDetails: ExchangeWireDetails,
  exchangeRestrictions: ExchangeRestrictionSpec | undefined,
): boolean {
  if (!exchangeRestrictions) {
    return true;
  }
  let accepted = false;
  for (const allowedExchange of exchangeRestrictions.exchanges) {
    if (allowedExchange.exchangePub === exchangeDetails.masterPublicKey) {
      accepted = true;
      break;
    }
  }
  for (const allowedAuditor of exchangeRestrictions.auditors) {
    for (const providedAuditor of exchangeDetails.auditors) {
      if (allowedAuditor.auditorPub === providedAuditor.auditor_pub) {
        accepted = true;
        break;
      }
    }
  }
  return accepted;
}

interface SelectPayCandidatesRequest {
  instructedAmount: AmountJson;
  restrictWireMethod: string | undefined;
  depositPaytoUri?: string;
  restrictExchanges: ExchangeRestrictionSpec | undefined;
  requiredMinimumAge?: number;
}

async function selectPayCandidates(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<
    ["exchanges", "coinAvailability", "exchangeDetails", "denominations"]
  >,
  req: SelectPayCandidatesRequest,
): Promise<[AvailableDenom[], Record<string, AmountJson>]> {
  // FIXME: Use the existing helper (from balance.ts) to
  // get acceptable exchanges.
  const denoms: AvailableDenom[] = [];
  const exchanges = await tx.exchanges.iter().toArray();
  const wfPerExchange: Record<string, AmountJson> = {};
  for (const exchange of exchanges) {
    const exchangeDetails = await getExchangeWireDetailsInTx(
      tx,
      exchange.baseUrl,
    );
    // 1. exchange has same currency
    if (exchangeDetails?.currency !== req.instructedAmount.currency) {
      continue;
    }

    // 2. Exchange supports wire method (only for pay/deposit)
    if (req.restrictWireMethod) {
      const wire = findMatchingWire(
        req.restrictWireMethod,
        req.depositPaytoUri,
        exchangeDetails,
      );
      if (!wire) {
        continue;
      }
      wfPerExchange[exchange.baseUrl] = wire.wireFee;
    }

    // 3. exchange is trusted in the exchange list or auditor list
    let accepted = checkExchangeAccepted(
      exchangeDetails,
      req.restrictExchanges,
    );
    if (!accepted) {
      continue;
    }

    // 4. filter coins restricted by age
    let ageLower = 0;
    let ageUpper = AgeRestriction.AGE_UNRESTRICTED;
    if (req.requiredMinimumAge) {
      ageLower = req.requiredMinimumAge;
    }

    const myExchangeCoins =
      await tx.coinAvailability.indexes.byExchangeAgeAvailability.getAll(
        GlobalIDB.KeyRange.bound(
          [exchangeDetails.exchangeBaseUrl, ageLower, 1],
          [exchangeDetails.exchangeBaseUrl, ageUpper, Number.MAX_SAFE_INTEGER],
        ),
      );

    // 5. save denoms with how many coins are available
    // FIXME: Check that the individual denomination is audited!
    // FIXME: Should we exclude denominations that are
    // not spendable anymore?
    for (const coinAvail of myExchangeCoins) {
      const denom = await tx.denominations.get([
        coinAvail.exchangeBaseUrl,
        coinAvail.denomPubHash,
      ]);
      checkDbInvariant(!!denom);
      if (denom.isRevoked || !denom.isOffered) {
        continue;
      }
      denoms.push({
        ...DenominationRecord.toDenomInfo(denom),
        numAvailable: coinAvail.freshCoinCount ?? 0,
        maxAge: coinAvail.maxAge,
      });
    }
  }
  // Sort by available amount (descending),  deposit fee (ascending) and
  // denomPub (ascending) if deposit fee is the same
  // (to guarantee deterministic results)
  denoms.sort(
    (o1, o2) =>
      -Amounts.cmp(o1.value, o2.value) ||
      Amounts.cmp(o1.feeDeposit, o2.feeDeposit) ||
      strcmp(o1.denomPubHash, o2.denomPubHash),
  );
  return [denoms, wfPerExchange];
}

export interface PeerCoinSelectionDetails {
  exchangeBaseUrl: string;

  /**
   * Info of Coins that were selected.
   */
  coins: SelectedCoin[];

  /**
   * How much of the deposit fees is the customer paying?
   */
  depositFees: AmountJson;

  maxExpirationDate: TalerProtocolTimestamp;
}

export type SelectPeerCoinsResult =
  | { type: "success"; result: PeerCoinSelectionDetails }
  | {
      type: "failure";
      insufficientBalanceDetails: PaymentInsufficientBalanceDetails;
    };

export interface PeerCoinSelectionRequest {
  instructedAmount: AmountJson;

  /**
   * Instruct the coin selection to repair this coin
   * selection instead of selecting completely new coins.
   */
  repair?: PreviousPayCoins;
}

export async function computeCoinSelMaxExpirationDate(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<["coins", "denominations"]>,
  selectedDenom: SelResult,
): Promise<TalerProtocolTimestamp> {
  let minAutorefreshExecuteThreshold = TalerProtocolTimestamp.never();
  for (const dph of Object.keys(selectedDenom)) {
    const selInfo = selectedDenom[dph];
    const denom = await getDenomInfo(
      wex,
      tx,
      selInfo.exchangeBaseUrl,
      selInfo.denomPubHash,
    );
    if (!denom) {
      continue;
    }
    // Compute earliest time that a selected denom
    // would have its coins auto-refreshed.
    minAutorefreshExecuteThreshold = TalerProtocolTimestamp.min(
      minAutorefreshExecuteThreshold,
      AbsoluteTime.toProtocolTimestamp(
        getAutoRefreshExecuteThreshold({
          stampExpireDeposit: denom.stampExpireDeposit,
          stampExpireWithdraw: denom.stampExpireWithdraw,
        }),
      ),
    );
  }
  return minAutorefreshExecuteThreshold;
}

export function emptyTallyForPeerPayment(
  instructedAmount: AmountJson,
): CoinSelectionTally {
  const currency = instructedAmount.currency;
  const zero = Amounts.zeroOfCurrency(currency);
  return {
    amountPayRemaining: instructedAmount,
    customerDepositFees: zero,
    lastDepositFee: zero,
    amountDepositFeeLimitRemaining: zero,
    customerWireFees: zero,
    wireFeeCoveredForExchange: new Set(),
  };
}

export async function selectPeerCoins(
  wex: WalletExecutionContext,
  req: PeerCoinSelectionRequest,
): Promise<SelectPeerCoinsResult> {
  const instructedAmount = req.instructedAmount;
  if (Amounts.isZero(instructedAmount)) {
    // Other parts of the code assume that we have at least
    // one coin to spend.
    throw new Error("amount of zero not allowed");
  }

  return await wex.db.runReadWriteTx(
    [
      "exchanges",
      "contractTerms",
      "coins",
      "coinAvailability",
      "denominations",
      "refreshGroups",
      "exchangeDetails",
    ],
    async (tx): Promise<SelectPeerCoinsResult> => {
      const exchanges = await tx.exchanges.iter().toArray();
      const currency = Amounts.currencyOf(instructedAmount);
      for (const exch of exchanges) {
        if (exch.detailsPointer?.currency !== currency) {
          continue;
        }
        const candidatesRes = await selectPayCandidates(wex, tx, {
          instructedAmount,
          restrictExchanges: {
            auditors: [],
            exchanges: [
              {
                exchangeBaseUrl: exch.baseUrl,
                exchangePub: exch.detailsPointer.masterPublicKey,
              },
            ],
          },
          restrictWireMethod: undefined,
        });
        const candidates = candidatesRes[0];
        if (logger.shouldLogTrace()) {
          logger.trace(`peer payment candidate coins: ${j2s(candidates)}`);
        }
        const tally = emptyTallyForPeerPayment(req.instructedAmount);
        const resCoins: SelectedCoin[] = [];

        await maybeRepairCoinSelection(
          wex,
          tx,
          req.repair ?? [],
          resCoins,
          tally,
          {
            wireFeeAmortization: 1,
            wireFeesPerExchange: {},
          },
        );

        if (logger.shouldLogTrace()) {
          logger.trace(`candidates: ${j2s(candidates)}`);
          logger.trace(`instructedAmount: ${j2s(instructedAmount)}`);
          logger.trace(`tally: ${j2s(tally)}`);
        }

        const selectedDenom = selectGreedy(
          {
            wireFeeAmortization: 1,
            wireFeesPerExchange: {},
          },
          candidates,
          tally,
        );

        if (selectedDenom) {
          const r = await assembleSelectPayCoinsSuccessResult(
            tx,
            selectedDenom,
            resCoins,
            tally,
          );

          const maxExpirationDate = await computeCoinSelMaxExpirationDate(
            wex,
            tx,
            selectedDenom,
          );

          return {
            type: "success",
            result: {
              coins: r.coins,
              depositFees: Amounts.parseOrThrow(r.customerDepositFees),
              exchangeBaseUrl: exch.baseUrl,
              maxExpirationDate,
            },
          };
        }
      }
      const insufficientBalanceDetails = await reportInsufficientBalanceDetails(
        wex,
        tx,
        {
          restrictExchanges: undefined,
          instructedAmount: req.instructedAmount,
          requiredMinimumAge: undefined,
          wireMethod: undefined,
          depositPaytoUri: undefined,
        },
      );
      return {
        type: "failure",
        insufficientBalanceDetails,
      };
    },
  );
}