/*
 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,
  AgeRestriction,
  AllowedAuditorInfo,
  AllowedExchangeInfo,
  AmountJson,
  Amounts,
  checkAccountRestriction,
  checkDbInvariant,
  checkLogicInvariant,
  CoinStatus,
  DenominationInfo,
  ExchangeGlobalFees,
  ForcedCoinSel,
  GetMaxDepositAmountRequest,
  GetMaxDepositAmountResponse,
  GetMaxPeerPushDebitAmountRequest,
  GetMaxPeerPushDebitAmountResponse,
  j2s,
  Logger,
  parsePaytoUri,
  PayCoinSelection,
  PaymentInsufficientBalanceDetails,
  ProspectivePayCoinSelection,
  ScopeInfo,
  ScopeType,
  SelectedCoin,
  SelectedProspectiveCoin,
  strcmp,
  TalerProtocolTimestamp,
} from "@gnu-taler/taler-util";
import { getPaymentBalanceDetailsInTx } from "./balance.js";
import { getAutoRefreshExecuteThreshold } from "./common.js";
import { DenominationRecord, WalletDbReadOnlyTransaction } from "./db.js";
import {
  checkExchangeInScope,
  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;

  totalDepositFees: AmountJson;

  customerWireFees: AmountJson;

  wireFeeCoveredForExchange: Set<string>;

  lastDepositFee: AmountJson;
}

/**
 * Account for the fees of spending a coin.
 */
function tallyFees(
  tally: CoinSelectionTally,
  wireFeesPerExchange: Record<string, AmountJson>,
  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 = wf;
    // 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;
  tally.totalDepositFees = Amounts.add(
    tally.totalDepositFees,
    feeDeposit,
  ).amount;
}

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

async function internalSelectPayCoins(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<
    [
      "coinAvailability",
      "denominations",
      "refreshGroups",
      "exchanges",
      "exchangeDetails",
      "coins",
    ]
  >,
  req: SelectPayCoinRequestNg,
  includePendingCoins: boolean,
): Promise<
  | { sel: SelResult; coinRes: SelectedCoin[]; tally: CoinSelectionTally }
  | undefined
> {
  const { contractTermsAmount, depositFeeLimit } = req;
  const candidateRes = await selectPayCandidates(wex, tx, {
    currency: Amounts.currencyOf(req.contractTermsAmount),
    restrictExchanges: req.restrictExchanges,
    restrictWireMethod: req.restrictWireMethod,
    depositPaytoUri: req.depositPaytoUri,
    requiredMinimumAge: req.requiredMinimumAge,
    includePendingCoins,
  });

  const wireFeesPerExchange = candidateRes.currentWireFeePerExchange;
  const candidateDenoms = candidateRes.coinAvailability;

  if (logger.shouldLogTrace()) {
    logger.trace(
      `instructed amount: ${Amounts.stringify(req.contractTermsAmount)}`,
    );
    logger.trace(`wire fees per exchange: ${j2s(wireFeesPerExchange)}`);
    logger.trace(`candidates: ${j2s(candidateDenoms)}`);
  }

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

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

  await maybeRepairCoinSelection(
    wex,
    tx,
    req.prevPayCoins ?? [],
    coinRes,
    tally,
    {
      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(
      {
        wireFeesPerExchange: wireFeesPerExchange,
      },
      candidateDenoms,
      tally,
    );
  }

  if (!selectedDenom) {
    return undefined;
  }
  return {
    sel: selectedDenom,
    coinRes,
    tally,
  };
}

export async function selectPayCoinsInTx(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<
    [
      "coinAvailability",
      "denominations",
      "refreshGroups",
      "exchanges",
      "exchangeDetails",
      "coins",
    ]
  >,
  req: SelectPayCoinRequestNg,
): Promise<SelectPayCoinsResult> {
  if (logger.shouldLogTrace()) {
    logger.trace(`selecting coins for ${j2s(req)}`);
  }

  const materialAvSel = await internalSelectPayCoins(wex, tx, req, false);

  if (!materialAvSel) {
    const prospectiveAvSel = await internalSelectPayCoins(wex, tx, req, true);

    if (prospectiveAvSel) {
      const prospectiveCoins: SelectedProspectiveCoin[] = [];
      for (const avKey of Object.keys(prospectiveAvSel.sel)) {
        const mySel = prospectiveAvSel.sel[avKey];
        for (const contrib of mySel.contributions) {
          prospectiveCoins.push({
            denomPubHash: mySel.denomPubHash,
            contribution: Amounts.stringify(contrib),
            exchangeBaseUrl: mySel.exchangeBaseUrl,
          });
        }
      }
      return {
        type: "prospective",
        result: {
          prospectiveCoins,
          customerDepositFees: Amounts.stringify(
            prospectiveAvSel.tally.customerDepositFees,
          ),
          customerWireFees: Amounts.stringify(
            prospectiveAvSel.tally.customerWireFees,
          ),
        },
      } satisfies SelectPayCoinsResult;
    }

    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,
    materialAvSel.sel,
    materialAvSel.coinRes,
    materialAvSel.tally,
  );

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

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

/**
 * 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> {
  return await wex.db.runReadOnlyTx(
    {
      storeNames: [
        "coinAvailability",
        "denominations",
        "refreshGroups",
        "exchanges",
        "exchangeDetails",
        "coins",
      ],
    },
    async (tx) => {
      return selectPayCoinsInTx(wex, tx, req);
    },
  );
}

async function maybeRepairCoinSelection(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<["coins", "denominations"]>,
  prevPayCoins: PreviousPayCoins,
  coinRes: SelectedCoin[],
  tally: CoinSelectionTally,
  feeInfo: {
    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,
      coin.exchangeBaseUrl,
      Amounts.parseOrThrow(denom.feeDeposit),
    );
    tally.amountPayRemaining = Amounts.sub(
      tally.amountPayRemaining,
      prev.contribution,
    ).amount;

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

/**
 * Returns undefined if the success response could not be assembled,
 * as not enough coins are actually available.
 */
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({
        denomPubHash: coins[i].denomPubHash,
        coinPub: coins[i].coinPub,
        contribution: Amounts.stringify(selInfo.contributions[i]),
        exchangeBaseUrl: coins[i].exchangeBaseUrl,
      });
    }
  }

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

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;
    }
    let missingGlobalFees = false;
    const exchWire = await getExchangeWireDetailsInTx(tx, exch.baseUrl);
    if (!exchWire) {
      // No wire details about the exchange known, skip!
      continue;
    }
    const globalFees = getGlobalFees(exchWire);
    if (!globalFees) {
      missingGlobalFees = true;
    }
    if (exchWire.currency !== Amounts.currencyOf(req.instructedAmount)) {
      // Do not report anything for an exchange with a different currency.
      continue;
    }
    const exchDet = await getPaymentBalanceDetailsInTx(wex, tx, {
      restrictExchanges: {
        exchanges: [
          {
            exchangeBaseUrl: exch.baseUrl,
            exchangePub: exch.detailsPointer?.masterPublicKey,
          },
        ],
        auditors: [],
      },
      restrictWireMethods: req.wireMethod ? [req.wireMethod] : undefined,
      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.maxMerchantEffectiveDepositAmount,
      ),
      missingGlobalFees,
    };
  }

  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.maxMerchantEffectiveDepositAmount,
    ),
    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 {
  wireFeesPerExchange: Record<string, AmountJson>;
}

function selectGreedy(
  req: SelectGreedyRequest,
  candidateDenoms: AvailableCoinsOfDenom[],
  tally: CoinSelectionTally,
): SelResult | undefined {
  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,
        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: AvailableCoinsOfDenom[],
): 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 interface SelectPayCoinRequestNg {
  restrictExchanges: ExchangeRestrictionSpec | undefined;
  restrictWireMethod: string;
  contractTermsAmount: AmountJson;
  depositFeeLimit: AmountJson;
  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 AvailableCoinsOfDenom = 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 {
  currency: string;
  restrictWireMethod: string | undefined;
  depositPaytoUri?: string;
  restrictExchanges: ExchangeRestrictionSpec | undefined;
  requiredMinimumAge?: number;

  /**
   * If set to true, the coin selection will also use coins that are not
   * materially available yet, but that are expected to become available
   * as the output of a refresh operation.
   */
  includePendingCoins: boolean;
}

export interface PayCoinCandidates {
  coinAvailability: AvailableCoinsOfDenom[];
  currentWireFeePerExchange: Record<string, AmountJson>;
}

async function selectPayCandidates(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<
    ["exchanges", "coinAvailability", "exchangeDetails", "denominations"]
  >,
  req: SelectPayCandidatesRequest,
): Promise<PayCoinCandidates> {
  // FIXME: Use the existing helper (from balance.ts) to
  // get acceptable exchanges.
  logger.shouldLogTrace() &&
    logger.trace(`selecting available coin candidates for ${j2s(req)}`);
  const denoms: AvailableCoinsOfDenom[] = [];
  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.currency) {
      logger.shouldLogTrace() &&
        logger.trace(`skipping ${exchange.baseUrl} due to currency mismatch`);
      continue;
    }

    // 2. Exchange supports wire method (only for pay/deposit)
    if (req.restrictWireMethod) {
      const wire = findMatchingWire(
        req.restrictWireMethod,
        req.depositPaytoUri,
        exchangeDetails,
      );
      if (!wire) {
        if (logger.shouldLogTrace()) {
          logger.trace(
            `skipping ${exchange.baseUrl} due to missing wire info mismatch`,
          );
        }
        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) {
      if (logger.shouldLogTrace()) {
        logger.trace(`skipping ${exchange.baseUrl} due to unacceptability`);
      }
      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],
        ),
      );

    if (logger.shouldLogTrace()) {
      logger.trace(
        `exchange ${exchange.baseUrl} has ${myExchangeCoins.length} candidate records`,
      );
    }

    let numUsable = 0;

    // 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,
        `denomination of a coin is missing hash: ${coinAvail.denomPubHash}`,
      );
      if (denom.isRevoked) {
        logger.trace("denom is revoked");
        continue;
      }
      if (!denom.isOffered) {
        logger.trace("denom is unoffered");
        continue;
      }
      numUsable++;
      let numAvailable = coinAvail.freshCoinCount ?? 0;
      if (req.includePendingCoins) {
        numAvailable += coinAvail.pendingRefreshOutputCount ?? 0;
      }
      denoms.push({
        ...DenominationRecord.toDenomInfo(denom),
        numAvailable,
        maxAge: coinAvail.maxAge,
      });
    }

    if (logger.shouldLogTrace()) {
      logger.trace(
        `exchange ${exchange.baseUrl} has ${numUsable} candidate records with usable denominations`,
      );
    }
  }
  // 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 {
    coinAvailability: denoms,
    currentWireFeePerExchange: wfPerExchange,
  };
}

export interface PeerCoinSelectionDetails {
  exchangeBaseUrl: string;

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

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

  totalDepositFees: AmountJson;

  maxExpirationDate: TalerProtocolTimestamp;
}

export interface ProspectivePeerCoinSelectionDetails {
  exchangeBaseUrl: string;

  prospectiveCoins: SelectedProspectiveCoin[];

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

  totalDepositFees: AmountJson;

  maxExpirationDate: TalerProtocolTimestamp;
}

export type SelectPeerCoinsResult =
  | { type: "success"; result: PeerCoinSelectionDetails }
  // Successful, but using coins that are not materially available yet.
  | { type: "prospective"; result: ProspectivePeerCoinSelectionDetails }
  | {
      type: "failure";
      insufficientBalanceDetails: PaymentInsufficientBalanceDetails;
    };

export interface PeerCoinSelectionRequest {
  instructedAmount: AmountJson;

  /**
   * Are deposit fees covered by the counterparty?
   *
   * Defaults to false.
   */
  feesCoveredByCounterparty?: boolean;

  /**
   * Restrict the scope of funds that can be spent via the given
   * scope info.
   */
  restrictScope?: ScopeInfo;

  /**
   * 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(
  req: PeerCoinSelectionRequest,
): CoinSelectionTally {
  const instructedAmount = req.instructedAmount;
  const currency = instructedAmount.currency;
  const zero = Amounts.zeroOfCurrency(currency);
  return {
    amountPayRemaining: instructedAmount,
    customerDepositFees: zero,
    lastDepositFee: zero,
    amountDepositFeeLimitRemaining: req.feesCoveredByCounterparty
      ? instructedAmount
      : zero,
    customerWireFees: zero,
    wireFeeCoveredForExchange: new Set(),
    totalDepositFees: zero,
  };
}

function getGlobalFees(
  wireDetails: ExchangeWireDetails,
): ExchangeGlobalFees | undefined {
  const now = AbsoluteTime.now();
  for (let gf of wireDetails.globalFees) {
    const isActive = AbsoluteTime.isBetween(
      now,
      AbsoluteTime.fromProtocolTimestamp(gf.startDate),
      AbsoluteTime.fromProtocolTimestamp(gf.endDate),
    );
    if (!isActive) {
      continue;
    }
    return gf;
  }
  return undefined;
}

async function internalSelectPeerCoins(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<
    [
      "exchanges",
      "contractTerms",
      "coins",
      "coinAvailability",
      "denominations",
      "refreshGroups",
      "exchangeDetails",
    ]
  >,
  req: PeerCoinSelectionRequest,
  exch: ExchangeWireDetails,
  includePendingCoins: boolean,
): Promise<
  | { sel: SelResult; tally: CoinSelectionTally; resCoins: SelectedCoin[] }
  | undefined
> {
  const candidatesRes = await selectPayCandidates(wex, tx, {
    currency: Amounts.currencyOf(req.instructedAmount),
    restrictExchanges: {
      auditors: [],
      exchanges: [
        {
          exchangeBaseUrl: exch.exchangeBaseUrl,
          exchangePub: exch.masterPublicKey,
        },
      ],
    },
    restrictWireMethod: undefined,
    includePendingCoins,
  });
  const candidates = candidatesRes.coinAvailability;
  if (logger.shouldLogTrace()) {
    logger.trace(`peer payment candidate coins: ${j2s(candidates)}`);
  }
  const tally = emptyTallyForPeerPayment(req);
  const resCoins: SelectedCoin[] = [];

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

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

  const selRes = selectGreedy(
    {
      wireFeesPerExchange: {},
    },
    candidates,
    tally,
  );
  if (!selRes) {
    return undefined;
  }

  return {
    sel: selRes,
    tally,
    resCoins,
  };
}

export async function selectPeerCoinsInTx(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<
    [
      "exchanges",
      "contractTerms",
      "coins",
      "coinAvailability",
      "denominations",
      "refreshGroups",
      "exchangeDetails",
    ]
  >,
  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("peer-to-peer payment with amount of zero not supported");
  }

  const exchanges = await tx.exchanges.iter().toArray();
  const currency = Amounts.currencyOf(instructedAmount);
  for (const exch of exchanges) {
    if (exch.detailsPointer?.currency !== currency) {
      continue;
    }
    const exchWire = await getExchangeWireDetailsInTx(tx, exch.baseUrl);
    if (!exchWire) {
      continue;
    }
    const isInScope = req.restrictScope
      ? await checkExchangeInScope(wex, exch.baseUrl, req.restrictScope)
      : true;
    if (!isInScope) {
      continue;
    }
    if (
      req.restrictScope &&
      req.restrictScope.type === ScopeType.Exchange &&
      req.restrictScope.url !== exch.baseUrl
    ) {
      continue;
    }
    const globalFees = getGlobalFees(exchWire);
    if (!globalFees) {
      continue;
    }

    const avRes = await internalSelectPeerCoins(wex, tx, req, exchWire, false);

    if (!avRes) {
      // Try to see if we can do a prospective selection
      const prospectiveAvRes = await internalSelectPeerCoins(
        wex,
        tx,
        req,
        exchWire,
        true,
      );
      if (prospectiveAvRes) {
        const prospectiveCoins: SelectedProspectiveCoin[] = [];
        for (const avKey of Object.keys(prospectiveAvRes.sel)) {
          const mySel = prospectiveAvRes.sel[avKey];
          for (const contrib of mySel.contributions) {
            prospectiveCoins.push({
              denomPubHash: mySel.denomPubHash,
              contribution: Amounts.stringify(contrib),
              exchangeBaseUrl: mySel.exchangeBaseUrl,
            });
          }
        }
        const maxExpirationDate = await computeCoinSelMaxExpirationDate(
          wex,
          tx,
          prospectiveAvRes.sel,
        );
        return {
          type: "prospective",
          result: {
            prospectiveCoins,
            customerDepositFees: prospectiveAvRes.tally.customerDepositFees,
            totalDepositFees: prospectiveAvRes.tally.totalDepositFees,
            exchangeBaseUrl: exch.baseUrl,
            maxExpirationDate,
          },
        };
      }
    } else if (avRes) {
      const r = await assembleSelectPayCoinsSuccessResult(
        tx,
        avRes.sel,
        avRes.resCoins,
        avRes.tally,
      );

      const maxExpirationDate = await computeCoinSelMaxExpirationDate(
        wex,
        tx,
        avRes.sel,
      );

      return {
        type: "success",
        result: {
          coins: r.coins,
          customerDepositFees: Amounts.parseOrThrow(r.customerDepositFees),
          totalDepositFees: Amounts.parseOrThrow(r.totalDepositFees),
          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,
  };
}

export async function selectPeerCoins(
  wex: WalletExecutionContext,
  req: PeerCoinSelectionRequest,
): Promise<SelectPeerCoinsResult> {
  return await wex.db.runReadWriteTx(
    {
      storeNames: [
        "exchanges",
        "contractTerms",
        "coins",
        "coinAvailability",
        "denominations",
        "refreshGroups",
        "exchangeDetails",
      ],
    },
    async (tx): Promise<SelectPeerCoinsResult> => {
      return selectPeerCoinsInTx(wex, tx, req);
    },
  );
}

function getMaxDepositAmountForAvailableCoins(
  req: GetMaxDepositAmountRequest,
  candidateRes: PayCoinCandidates,
): GetMaxDepositAmountResponse {
  const wireFeeCoveredForExchange = new Set<string>();

  let amountEffective = Amounts.zeroOfCurrency(req.currency);
  let fees = Amounts.zeroOfCurrency(req.currency);

  for (const cc of candidateRes.coinAvailability) {
    if (!wireFeeCoveredForExchange.has(cc.exchangeBaseUrl)) {
      const wireFee =
        candidateRes.currentWireFeePerExchange[cc.exchangeBaseUrl];
      // Wire fee can be null if max deposit amount is computed
      // without restricting the wire method.
      if (wireFee != null) {
        fees = Amounts.add(fees, wireFee).amount;
      }
      wireFeeCoveredForExchange.add(cc.exchangeBaseUrl);
    }

    amountEffective = Amounts.add(
      amountEffective,
      Amounts.mult(cc.value, cc.numAvailable).amount,
    ).amount;

    fees = Amounts.add(
      fees,
      Amounts.mult(cc.feeDeposit, cc.numAvailable).amount,
    ).amount;
  }

  return {
    effectiveAmount: Amounts.stringify(amountEffective),
    rawAmount: Amounts.stringify(Amounts.sub(amountEffective, fees).amount),
  };
}

/**
 * Only used for unit testing getMaxDepositAmountForAvailableCoins.
 */
export const testing_getMaxDepositAmountForAvailableCoins =
  getMaxDepositAmountForAvailableCoins;

export async function getMaxDepositAmount(
  wex: WalletExecutionContext,
  req: GetMaxDepositAmountRequest,
): Promise<GetMaxDepositAmountResponse> {
  logger.trace(`getting max deposit amount for: ${j2s(req)}`);
  return await wex.db.runReadOnlyTx(
    {
      storeNames: [
        "exchanges",
        "coinAvailability",
        "denominations",
        "exchangeDetails",
      ],
    },
    async (tx): Promise<GetMaxDepositAmountResponse> => {
      let restrictWireMethod: string | undefined = undefined;
      if (req.depositPaytoUri) {
        const p = parsePaytoUri(req.depositPaytoUri);
        if (!p) {
          throw Error("invalid payto URI");
        }
        restrictWireMethod = p.targetType;
      }
      const candidateRes = await selectPayCandidates(wex, tx, {
        currency: req.currency,
        restrictExchanges: undefined,
        restrictWireMethod,
        depositPaytoUri: req.depositPaytoUri,
        requiredMinimumAge: undefined,
        includePendingCoins: true,
      });
      return getMaxDepositAmountForAvailableCoins(req, candidateRes);
    },
  );
}

function getMaxPeerPushDebitAmountForAvailableCoins(
  req: GetMaxDepositAmountRequest,
  exchangeBaseUrl: string,
  candidateRes: PayCoinCandidates,
): GetMaxPeerPushDebitAmountResponse {
  let amountEffective = Amounts.zeroOfCurrency(req.currency);
  let fees = Amounts.zeroOfCurrency(req.currency);

  for (const cc of candidateRes.coinAvailability) {
    amountEffective = Amounts.add(
      amountEffective,
      Amounts.mult(cc.value, cc.numAvailable).amount,
    ).amount;

    fees = Amounts.add(
      fees,
      Amounts.mult(cc.feeDeposit, cc.numAvailable).amount,
    ).amount;
  }

  return {
    exchangeBaseUrl,
    effectiveAmount: Amounts.stringify(amountEffective),
    rawAmount: Amounts.stringify(Amounts.sub(amountEffective, fees).amount),
  };
}

export async function getMaxPeerPushDebitAmount(
  wex: WalletExecutionContext,
  req: GetMaxPeerPushDebitAmountRequest,
): Promise<GetMaxPeerPushDebitAmountResponse> {
  logger.trace(`getting max deposit amount for: ${j2s(req)}`);

  return await wex.db.runReadOnlyTx(
    {
      storeNames: [
        "exchanges",
        "coinAvailability",
        "denominations",
        "exchangeDetails",
      ],
    },
    async (tx): Promise<GetMaxPeerPushDebitAmountResponse> => {
      let result: GetMaxDepositAmountResponse | undefined = undefined;
      const currency = req.currency;
      const exchanges = await tx.exchanges.iter().toArray();
      for (const exch of exchanges) {
        if (exch.detailsPointer?.currency !== currency) {
          continue;
        }
        const exchWire = await getExchangeWireDetailsInTx(tx, exch.baseUrl);
        if (!exchWire) {
          continue;
        }
        const isInScope = req.restrictScope
          ? await checkExchangeInScope(wex, exch.baseUrl, req.restrictScope)
          : true;
        if (!isInScope) {
          continue;
        }
        if (
          req.restrictScope &&
          req.restrictScope.type === ScopeType.Exchange &&
          req.restrictScope.url !== exch.baseUrl
        ) {
          continue;
        }
        const globalFees = getGlobalFees(exchWire);
        if (!globalFees) {
          continue;
        }

        const candidatesRes = await selectPayCandidates(wex, tx, {
          currency,
          restrictExchanges: {
            auditors: [],
            exchanges: [
              {
                exchangeBaseUrl: exchWire.exchangeBaseUrl,
                exchangePub: exchWire.masterPublicKey,
              },
            ],
          },
          restrictWireMethod: undefined,
          includePendingCoins: true,
        });

        const myExchangeRes = getMaxPeerPushDebitAmountForAvailableCoins(
          req,
          exchWire.exchangeBaseUrl,
          candidatesRes,
        );

        if (!result) {
          result = myExchangeRes;
        } else if (Amounts.cmp(result.rawAmount, myExchangeRes.rawAmount) < 0) {
          result = myExchangeRes;
        }
      }
      if (!result) {
        return {
          effectiveAmount: Amounts.stringify(Amounts.zeroOfCurrency(currency)),
          rawAmount: Amounts.stringify(Amounts.zeroOfCurrency(currency)),
        };
      }
      return result;
    },
  );
}