/*
 This file is part of GNU Taler
 (C) 2021 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,
  AgeCommitmentProof,
  AgeRestriction,
  AllowedAuditorInfo,
  AllowedExchangeInfo,
  AmountJson,
  AmountLike,
  Amounts,
  AmountString,
  checkDbInvariant,
  checkLogicInvariant,
  CoinPublicKeyString,
  CoinStatus,
  DenominationInfo,
  DenominationPubKey,
  DenomSelectionState,
  Duration,
  ForcedCoinSel,
  ForcedDenomSel,
  InternationalizedString,
  j2s,
  Logger,
  parsePaytoUri,
  PayCoinSelection,
  PayMerchantInsufficientBalanceDetails,
  PayPeerInsufficientBalanceDetails,
  strcmp,
  TalerProtocolTimestamp,
  UnblindedSignature,
} from "@gnu-taler/taler-util";
import {
  getMerchantPaymentBalanceDetails,
  getPeerPaymentBalanceDetailsInTx,
} from "./balance.js";
import { getAutoRefreshExecuteThreshold } from "./common.js";
import { DenominationRecord, WalletDbReadOnlyTransaction } from "./db.js";
import { isWithdrawableDenom } from "./denominations.js";
import { getExchangeWireDetailsInTx } from "./exchanges.js";
import {
  getDenomInfo,
  InternalWalletState,
  WalletExecutionContext,
} from "./wallet.js";

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

/**
 * Structure to describe a coin that is available to be
 * used in a payment.
 */
export interface AvailableCoinInfo {
  /**
   * Public key of the coin.
   */
  coinPub: string;

  /**
   * Coin's denomination public key.
   *
   * FIXME: We should only need the denomPubHash here, if at all.
   */
  denomPub: DenominationPubKey;

  /**
   * Full value of the coin.
   */
  value: AmountJson;

  /**
   * Amount still remaining (typically the full amount,
   * as coins are always refreshed after use.)
   */
  availableAmount: AmountJson;

  /**
   * Deposit fee for the coin.
   */
  feeDeposit: AmountJson;

  exchangeBaseUrl: string;

  maxAge: number;
  ageCommitmentProof?: AgeCommitmentProof;
}

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

export interface CoinCandidateSelection {
  candidateCoins: AvailableCoinInfo[];
  wireFeesPerExchange: Record<string, AmountJson>;
}

export interface SelectPayCoinRequest {
  candidates: CoinCandidateSelection;
  contractTermsAmount: AmountJson;
  depositFeeLimit: AmountJson;
  wireFeeLimit: AmountJson;
  wireFeeAmortization: number;
  prevPayCoins?: PreviousPayCoins;
  requiredMinimumAge?: number;
}

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 wire fees
   */
  amountWireFeeLimitRemaining: 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: Readonly<CoinSelectionTally>,
  wireFeesPerExchange: Record<string, AmountJson>,
  wireFeeAmortization: number,
  exchangeBaseUrl: string,
  feeDeposit: AmountJson,
): CoinSelectionTally {
  const currency = tally.amountPayRemaining.currency;
  let amountWireFeeLimitRemaining = tally.amountWireFeeLimitRemaining;
  let amountDepositFeeLimitRemaining = tally.amountDepositFeeLimitRemaining;
  let customerDepositFees = tally.customerDepositFees;
  let customerWireFees = tally.customerWireFees;
  let amountPayRemaining = tally.amountPayRemaining;
  const wireFeeCoveredForExchange = new Set(tally.wireFeeCoveredForExchange);

  if (!tally.wireFeeCoveredForExchange.has(exchangeBaseUrl)) {
    const wf =
      wireFeesPerExchange[exchangeBaseUrl] ?? Amounts.zeroOfCurrency(currency);
    const wfForgiven = Amounts.min(amountWireFeeLimitRemaining, wf);
    amountWireFeeLimitRemaining = Amounts.sub(
      amountWireFeeLimitRemaining,
      wfForgiven,
    ).amount;
    // The remaining, amortized amount needs to be paid by the
    // wallet or covered by the deposit fee allowance.
    let wfRemaining = Amounts.divide(
      Amounts.sub(wf, wfForgiven).amount,
      wireFeeAmortization,
    );

    // This is the amount forgiven via the deposit fee allowance.
    const wfDepositForgiven = Amounts.min(
      amountDepositFeeLimitRemaining,
      wfRemaining,
    );
    amountDepositFeeLimitRemaining = Amounts.sub(
      amountDepositFeeLimitRemaining,
      wfDepositForgiven,
    ).amount;

    wfRemaining = Amounts.sub(wfRemaining, wfDepositForgiven).amount;
    customerWireFees = Amounts.add(customerWireFees, wfRemaining).amount;
    amountPayRemaining = Amounts.add(amountPayRemaining, wfRemaining).amount;

    wireFeeCoveredForExchange.add(exchangeBaseUrl);
  }

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

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

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

  return {
    amountDepositFeeLimitRemaining,
    amountPayRemaining,
    amountWireFeeLimitRemaining,
    customerDepositFees,
    customerWireFees,
    wireFeeCoveredForExchange,
    lastDepositFee: feeDeposit,
  };
}

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

/**
 * Given a list of candidate coins, 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.
 *
 * This function is only exported for the sake of unit tests.
 */
export async function selectPayCoinsNew(
  wex: WalletExecutionContext,
  req: SelectPayCoinRequestNg,
): Promise<SelectPayCoinsResult> {
  const {
    contractTermsAmount,
    depositFeeLimit,
    wireFeeLimit,
    wireFeeAmortization,
  } = req;

  // FIXME: Why don't we do this in a transaction?
  const [candidateDenoms, wireFeesPerExchange] =
    await selectPayMerchantCandidates(wex, req);

  const coinPubs: string[] = [];
  const coinContributions: AmountJson[] = [];
  const currency = contractTermsAmount.currency;

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

  const prevPayCoins = req.prevPayCoins ?? [];

  // Look at existing pay coin selection and tally up
  for (const prev of prevPayCoins) {
    tally = tallyFees(
      tally,
      wireFeesPerExchange,
      wireFeeAmortization,
      prev.exchangeBaseUrl,
      prev.feeDeposit,
    );
    tally.amountPayRemaining = Amounts.sub(
      tally.amountPayRemaining,
      prev.contribution,
    ).amount;

    coinPubs.push(prev.coinPub);
    coinContributions.push(prev.contribution);
  }

  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(
      req,
      candidateDenoms,
      wireFeesPerExchange,
      tally,
    );
  }

  if (!selectedDenom) {
    const details = await getMerchantPaymentBalanceDetails(wex, {
      acceptedAuditors: req.auditors,
      acceptedExchanges: req.exchanges,
      acceptedWireMethods: [req.wireMethod],
      currency: Amounts.currencyOf(req.contractTermsAmount),
      minAge: req.requiredMinimumAge ?? 0,
    });
    let feeGapEstimate: AmountJson;
    if (
      Amounts.cmp(
        details.balanceMerchantDepositable,
        req.contractTermsAmount,
      ) >= 0
    ) {
      // FIXME: We can probably give a better estimate.
      feeGapEstimate = Amounts.add(
        tally.amountPayRemaining,
        tally.lastDepositFee,
      ).amount;
    } else {
      feeGapEstimate = Amounts.zeroOfAmount(req.contractTermsAmount);
    }
    return {
      type: "failure",
      insufficientBalanceDetails: {
        amountRequested: Amounts.stringify(req.contractTermsAmount),
        balanceAgeAcceptable: Amounts.stringify(details.balanceAgeAcceptable),
        balanceAvailable: Amounts.stringify(details.balanceAvailable),
        balanceMaterial: Amounts.stringify(details.balanceMaterial),
        balanceMerchantAcceptable: Amounts.stringify(
          details.balanceMerchantAcceptable,
        ),
        balanceMerchantDepositable: Amounts.stringify(
          details.balanceMerchantDepositable,
        ),
        feeGapEstimate: Amounts.stringify(feeGapEstimate),
      },
    };
  }

  const finalSel = selectedDenom;

  logger.trace(`coin selection request ${j2s(req)}`);
  logger.trace(`selected coins (via denoms) for payment: ${j2s(finalSel)}`);

  await wex.db.runReadOnlyTx(["coins", "denominations"], async (tx) => {
    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})`,
        );
      }
      coinPubs.push(...coins.map((x) => x.coinPub));
      coinContributions.push(...selInfo.contributions);
    }
  });

  return {
    type: "success",
    coinSel: {
      paymentAmount: Amounts.stringify(contractTermsAmount),
      coinContributions: coinContributions.map((x) => Amounts.stringify(x)),
      coinPubs,
      customerDepositFees: Amounts.stringify(tally.customerDepositFees),
      customerWireFees: Amounts.stringify(tally.customerWireFees),
    },
  };
}

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;
    expireWithdraw: TalerProtocolTimestamp;
    expireDeposit: TalerProtocolTimestamp;
    maxAge: number;
    contributions: AmountJson[];
  };
}

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

function selectGreedy(
  req: SelectPayCoinRequestNg,
  candidateDenoms: AvailableDenom[],
  wireFeesPerExchange: Record<string, AmountJson>,
  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++
    ) {
      tally = tallyFees(
        tally,
        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,
          expireDeposit: denom.stampExpireDeposit,
          expireWithdraw: denom.stampExpireWithdraw,
        };
      }
      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,
            expireDeposit: aci.stampExpireDeposit,
            expireWithdraw: aci.stampExpireWithdraw,
          };
        }
        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 {
  exchanges: AllowedExchangeInfo[];
  auditors: AllowedAuditorInfo[];
  wireMethod: string;
  contractTermsAmount: AmountJson;
  depositFeeLimit: AmountJson;
  wireFeeLimit: 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;
};

async function selectPayMerchantCandidates(
  wex: WalletExecutionContext,
  req: SelectPayCoinRequestNg,
): Promise<[AvailableDenom[], Record<string, AmountJson>]> {
  return await wex.db.runReadOnlyTx(
    ["exchanges", "exchangeDetails", "denominations", "coinAvailability"],
    async (tx) => {
      // 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> = {};
      loopExchange: for (const exchange of exchanges) {
        const exchangeDetails = await getExchangeWireDetailsInTx(
          tx,
          exchange.baseUrl,
        );
        // 1.- exchange has same currency
        if (exchangeDetails?.currency !== req.contractTermsAmount.currency) {
          continue;
        }
        let wireMethodFee: string | undefined;
        // 2.- exchange supports wire method
        loopWireAccount: for (const acc of exchangeDetails.wireInfo.accounts) {
          const pp = parsePaytoUri(acc.payto_uri);
          checkLogicInvariant(!!pp);
          if (pp.targetType !== req.wireMethod) {
            continue;
          }
          const wireFeeStr = exchangeDetails.wireInfo.feesForType[
            req.wireMethod
          ]?.find((x) => {
            return AbsoluteTime.isBetween(
              AbsoluteTime.now(),
              AbsoluteTime.fromProtocolTimestamp(x.startStamp),
              AbsoluteTime.fromProtocolTimestamp(x.endStamp),
            );
          })?.wireFee;
          let debitAccountCheckOk = false;
          if (req.depositPaytoUri) {
            // FIXME: We should somehow propagate the hint here!
            const checkResult = checkAccountRestriction(
              req.depositPaytoUri,
              acc.debit_restrictions,
            );
            if (checkResult.ok) {
              debitAccountCheckOk = true;
            }
          } else {
            debitAccountCheckOk = true;
          }

          if (wireFeeStr) {
            wireMethodFee = wireFeeStr;
            break loopWireAccount;
          }
        }
        if (!wireMethodFee) {
          continue;
        }
        wfPerExchange[exchange.baseUrl] = Amounts.parseOrThrow(wireMethodFee);

        // 3.- exchange is trusted in the exchange list or auditor list
        let accepted = false;
        for (const allowedExchange of req.exchanges) {
          if (allowedExchange.exchangePub === exchangeDetails.masterPublicKey) {
            accepted = true;
            break;
          }
        }
        for (const allowedAuditor of req.auditors) {
          for (const providedAuditor of exchangeDetails.auditors) {
            if (allowedAuditor.auditorPub === providedAuditor.auditor_pub) {
              accepted = true;
              break;
            }
          }
        }
        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,
          });
        }
      }
      logger.info(`available denoms ${j2s(denoms)}`);
      // 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];
    },
  );
}

/**
 * Get a list of denominations (with repetitions possible)
 * whose total value is as close as possible to the available
 * amount, but never larger.
 */
export function selectWithdrawalDenominations(
  amountAvailable: AmountJson,
  denoms: DenominationRecord[],
  denomselAllowLate: boolean = false,
): DenomSelectionState {
  let remaining = Amounts.copy(amountAvailable);

  const selectedDenoms: {
    count: number;
    denomPubHash: string;
  }[] = [];

  let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency);
  let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency);

  denoms = denoms.filter((d) => isWithdrawableDenom(d, denomselAllowLate));
  denoms.sort((d1, d2) => Amounts.cmp(d2.value, d1.value));

  for (const d of denoms) {
    const cost = Amounts.add(d.value, d.fees.feeWithdraw).amount;
    const res = Amounts.divmod(remaining, cost);
    const count = res.quotient;
    remaining = Amounts.sub(remaining, Amounts.mult(cost, count).amount).amount;
    if (count > 0) {
      totalCoinValue = Amounts.add(
        totalCoinValue,
        Amounts.mult(d.value, count).amount,
      ).amount;
      totalWithdrawCost = Amounts.add(
        totalWithdrawCost,
        Amounts.mult(cost, count).amount,
      ).amount;
      selectedDenoms.push({
        count,
        denomPubHash: d.denomPubHash,
      });
    }

    if (Amounts.isZero(remaining)) {
      break;
    }
  }

  if (logger.shouldLogTrace()) {
    logger.trace(
      `selected withdrawal denoms for ${Amounts.stringify(totalCoinValue)}`,
    );
    for (const sd of selectedDenoms) {
      logger.trace(`denom_pub_hash=${sd.denomPubHash}, count=${sd.count}`);
    }
    logger.trace("(end of withdrawal denom list)");
  }

  return {
    selectedDenoms,
    totalCoinValue: Amounts.stringify(totalCoinValue),
    totalWithdrawCost: Amounts.stringify(totalWithdrawCost),
  };
}

export function selectForcedWithdrawalDenominations(
  amountAvailable: AmountJson,
  denoms: DenominationRecord[],
  forcedDenomSel: ForcedDenomSel,
  denomselAllowLate: boolean,
): DenomSelectionState {
  const selectedDenoms: {
    count: number;
    denomPubHash: string;
  }[] = [];

  let totalCoinValue = Amounts.zeroOfCurrency(amountAvailable.currency);
  let totalWithdrawCost = Amounts.zeroOfCurrency(amountAvailable.currency);

  denoms = denoms.filter((d) => isWithdrawableDenom(d, denomselAllowLate));
  denoms.sort((d1, d2) => Amounts.cmp(d2.value, d1.value));

  for (const fds of forcedDenomSel.denoms) {
    const count = fds.count;
    const denom = denoms.find((x) => {
      return Amounts.cmp(x.value, fds.value) == 0;
    });
    if (!denom) {
      throw Error(
        `unable to find denom for forced selection (value ${fds.value})`,
      );
    }
    const cost = Amounts.add(denom.value, denom.fees.feeWithdraw).amount;
    totalCoinValue = Amounts.add(
      totalCoinValue,
      Amounts.mult(denom.value, count).amount,
    ).amount;
    totalWithdrawCost = Amounts.add(
      totalWithdrawCost,
      Amounts.mult(cost, count).amount,
    ).amount;
    selectedDenoms.push({
      count,
      denomPubHash: denom.denomPubHash,
    });
  }

  return {
    selectedDenoms,
    totalCoinValue: Amounts.stringify(totalCoinValue),
    totalWithdrawCost: Amounts.stringify(totalWithdrawCost),
  };
}

export interface CoinInfo {
  id: string;
  value: AmountJson;
  denomDeposit: AmountJson;
  denomWithdraw: AmountJson;
  denomRefresh: AmountJson;
  totalAvailable: number | undefined;
  exchangeWire: AmountJson | undefined;
  exchangePurse: AmountJson | undefined;
  duration: Duration;
  exchangeBaseUrl: string;
  maxAge: number;
}

export interface SelectedPeerCoin {
  coinPub: string;
  coinPriv: string;
  contribution: AmountString;
  denomPubHash: string;
  denomSig: UnblindedSignature;
  ageCommitmentProof: AgeCommitmentProof | undefined;
}

export interface PeerCoinSelectionDetails {
  exchangeBaseUrl: string;

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

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

  maxExpirationDate: TalerProtocolTimestamp;
}

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

export interface PeerCoinRepair {
  exchangeBaseUrl: string;
  coinPubs: CoinPublicKeyString[];
  contribs: AmountJson[];
}

export interface PeerCoinSelectionRequest {
  instructedAmount: AmountJson;

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

/**
 * Get coin availability information for a certain exchange.
 */
async function selectPayPeerCandidatesForExchange(
  wex: WalletExecutionContext,
  tx: WalletDbReadOnlyTransaction<["coinAvailability", "denominations"]>,
  exchangeBaseUrl: string,
): Promise<AvailableDenom[]> {
  const denoms: AvailableDenom[] = [];

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

  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;
}

interface PeerCoinSelectionTally {
  amountAcc: AmountJson;
  depositFeesAcc: AmountJson;
  lastDepositFee: AmountJson;
}

/**
 * exporting for testing
 */
export function testing_greedySelectPeer(
  ...args: Parameters<typeof greedySelectPeer>
): ReturnType<typeof greedySelectPeer> {
  return greedySelectPeer(...args);
}

function greedySelectPeer(
  candidates: AvailableDenom[],
  instructedAmount: AmountLike,
  tally: PeerCoinSelectionTally,
): SelResult | undefined {
  const selectedDenom: SelResult = {};
  for (const denom of candidates) {
    const contributions: AmountJson[] = [];
    for (
      let i = 0;
      i < denom.numAvailable &&
      Amounts.cmp(tally.amountAcc, instructedAmount) < 0;
      i++
    ) {
      const amountPayRemaining = Amounts.sub(
        instructedAmount,
        tally.amountAcc,
      ).amount;
      // Maximum amount the coin could effectively contribute.
      const maxCoinContrib = Amounts.sub(denom.value, denom.feeDeposit).amount;

      const coinSpend = Amounts.min(
        Amounts.add(amountPayRemaining, denom.feeDeposit).amount,
        maxCoinContrib,
      );

      tally.amountAcc = Amounts.add(tally.amountAcc, coinSpend).amount;
      tally.amountAcc = Amounts.sub(tally.amountAcc, denom.feeDeposit).amount;

      tally.depositFeesAcc = Amounts.add(
        tally.depositFeesAcc,
        denom.feeDeposit,
      ).amount;

      tally.lastDepositFee = Amounts.parseOrThrow(denom.feeDeposit);

      contributions.push(coinSpend);
    }
    if (contributions.length > 0) {
      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,
          expireDeposit: denom.stampExpireDeposit,
          expireWithdraw: denom.stampExpireWithdraw,
        };
      }
      sd.contributions.push(...contributions);
      selectedDenom[avKey] = sd;
    }
    if (Amounts.cmp(tally.amountAcc, instructedAmount) >= 0) {
      break;
    }
  }

  if (Amounts.cmp(tally.amountAcc, instructedAmount) >= 0) {
    return selectedDenom;
  }
  return undefined;
}

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",
      "peerPushDebit",
    ],
    async (tx) => {
      const exchanges = await tx.exchanges.iter().toArray();
      const exchangeFeeGap: { [url: string]: AmountJson } = {};
      const currency = Amounts.currencyOf(instructedAmount);
      for (const exch of exchanges) {
        if (exch.detailsPointer?.currency !== currency) {
          continue;
        }
        const candidates = await selectPayPeerCandidatesForExchange(
          wex,
          tx,
          exch.baseUrl,
        );
        const tally: PeerCoinSelectionTally = {
          amountAcc: Amounts.zeroOfCurrency(currency),
          depositFeesAcc: Amounts.zeroOfCurrency(currency),
          lastDepositFee: Amounts.zeroOfCurrency(currency),
        };
        const resCoins: {
          coinPub: string;
          coinPriv: string;
          contribution: AmountString;
          denomPubHash: string;
          denomSig: UnblindedSignature;
          ageCommitmentProof: AgeCommitmentProof | undefined;
        }[] = [];

        if (req.repair && req.repair.exchangeBaseUrl === exch.baseUrl) {
          for (let i = 0; i < req.repair.coinPubs.length; i++) {
            const contrib = req.repair.contribs[i];
            const coin = await tx.coins.get(req.repair.coinPubs[i]);
            if (!coin) {
              throw Error("repair not possible, coin not found");
            }
            const denom = await getDenomInfo(
              wex,
              tx,
              coin.exchangeBaseUrl,
              coin.denomPubHash,
            );
            checkDbInvariant(!!denom);
            resCoins.push({
              coinPriv: coin.coinPriv,
              coinPub: coin.coinPub,
              contribution: Amounts.stringify(contrib),
              denomPubHash: coin.denomPubHash,
              denomSig: coin.denomSig,
              ageCommitmentProof: coin.ageCommitmentProof,
            });
            const depositFee = Amounts.parseOrThrow(denom.feeDeposit);
            tally.lastDepositFee = depositFee;
            tally.amountAcc = Amounts.add(
              tally.amountAcc,
              Amounts.sub(contrib, depositFee).amount,
            ).amount;
            tally.depositFeesAcc = Amounts.add(
              tally.depositFeesAcc,
              depositFee,
            ).amount;
          }
        }

        const selectedDenom = greedySelectPeer(
          candidates,
          instructedAmount,
          tally,
        );

        if (selectedDenom) {
          let minAutorefreshExecuteThreshold = TalerProtocolTimestamp.never();
          for (const dph of Object.keys(selectedDenom)) {
            const selInfo = selectedDenom[dph];
            // Compute earliest time that a selected denom
            // would have its coins auto-refreshed.
            minAutorefreshExecuteThreshold = TalerProtocolTimestamp.min(
              minAutorefreshExecuteThreshold,
              AbsoluteTime.toProtocolTimestamp(
                getAutoRefreshExecuteThreshold({
                  stampExpireDeposit: selInfo.expireDeposit,
                  stampExpireWithdraw: selInfo.expireWithdraw,
                }),
              ),
            );
            const numRequested = selInfo.contributions.length;
            const query = [
              selInfo.exchangeBaseUrl,
              selInfo.denomPubHash,
              selInfo.maxAge,
              CoinStatus.Fresh,
            ];
            logger.info(`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++) {
              resCoins.push({
                coinPriv: coins[i].coinPriv,
                coinPub: coins[i].coinPub,
                contribution: Amounts.stringify(selInfo.contributions[i]),
                ageCommitmentProof: coins[i].ageCommitmentProof,
                denomPubHash: selInfo.denomPubHash,
                denomSig: coins[i].denomSig,
              });
            }
          }

          const res: PeerCoinSelectionDetails = {
            exchangeBaseUrl: exch.baseUrl,
            coins: resCoins,
            depositFees: tally.depositFeesAcc,
            maxExpirationDate: minAutorefreshExecuteThreshold,
          };
          return { type: "success", result: res };
        }

        const diff = Amounts.sub(instructedAmount, tally.amountAcc).amount;
        exchangeFeeGap[exch.baseUrl] = Amounts.add(
          tally.lastDepositFee,
          diff,
        ).amount;

        continue;
      }

      // We were unable to select coins.
      // Now we need to produce error details.

      const infoGeneral = await getPeerPaymentBalanceDetailsInTx(wex, tx, {
        currency,
      });

      const perExchange: PayPeerInsufficientBalanceDetails["perExchange"] = {};

      let maxFeeGapEstimate = Amounts.zeroOfCurrency(currency);

      for (const exch of exchanges) {
        if (exch.detailsPointer?.currency !== currency) {
          continue;
        }
        const infoExchange = await getPeerPaymentBalanceDetailsInTx(wex, tx, {
          currency,
          restrictExchangeTo: exch.baseUrl,
        });
        let gap =
          exchangeFeeGap[exch.baseUrl] ?? Amounts.zeroOfCurrency(currency);
        if (Amounts.cmp(infoExchange.balanceMaterial, instructedAmount) < 0) {
          // Show fee gap only if we should've been able to pay with the material amount
          gap = Amounts.zeroOfCurrency(currency);
        }
        perExchange[exch.baseUrl] = {
          balanceAvailable: Amounts.stringify(infoExchange.balanceAvailable),
          balanceMaterial: Amounts.stringify(infoExchange.balanceMaterial),
          feeGapEstimate: Amounts.stringify(gap),
        };

        maxFeeGapEstimate = Amounts.max(maxFeeGapEstimate, gap);
      }

      const errDetails: PayPeerInsufficientBalanceDetails = {
        amountRequested: Amounts.stringify(instructedAmount),
        balanceAvailable: Amounts.stringify(infoGeneral.balanceAvailable),
        balanceMaterial: Amounts.stringify(infoGeneral.balanceMaterial),
        feeGapEstimate: Amounts.stringify(maxFeeGapEstimate),
        perExchange,
      };

      return { type: "failure", insufficientBalanceDetails: errDetails };
    },
  );
}