sendfun-sdk 4.0.0

//! Resolves the Token-2022 transfer-hook accounts of an instruction from
//! accounts that you fetch.
//!
//! A builder resolves each transfer of its instruction from the
//! [`HookState`] of each mint, as `spl-tlv-account-resolution` 0.11.4 does.
//! It appends the merged list after all accounts of the instruction.
//!
//! The resolver refuses a list that no resolver can resolve before the
//! instruction runs, and a list with a seed on the transfer amount
//! ([`Unresolvable`]). An instruction can still fail when a hook refuses the
//! transfer, the chain holds an extra read-only, or a mint is paused.
//! Simulate the transaction. A router that cannot simulate checks a trade
//! with [`route`].
//!
//! Read a mint with [`MintInfo::load`](crate::utils::MintInfo::load) and fill
//! its [`HookState`]: the builders and [`route::trade`] take the `MintInfo`.

use std::collections::BTreeMap;
use std::fmt;

use solana_address::{Address, MAX_SEEDS};
use solana_instruction::AccountMeta;
use spl_discriminator::{ArrayDiscriminator, SplDiscriminate};
use spl_tlv_account_resolution::account::ExtraAccountMeta;
use spl_tlv_account_resolution::pubkey_data::PubkeyData;
use spl_tlv_account_resolution::seeds::Seed;
use spl_tlv_account_resolution::solana_program_error::ProgramError;
use spl_tlv_account_resolution::state::ExtraAccountMetaList;
use spl_token_2022_interface::extension::transfer_hook::TransferHook;
use spl_type_length_value::error::TlvError;
use spl_type_length_value::state::TlvStateBorrowed;

use crate::transfer_fee::{
	TransferFeeConfig, extension, mint_extensions, spl_token_mint,
};
use crate::utils::{MintInfo, TradeMints};

pub mod route;

/// Discriminator of the hook's `Execute` instruction. Also the TLV type of the
/// entry that holds the account list.
pub const EXECUTE_DISCRIMINATOR: [u8; 8] =
	[105, 37, 101, 197, 75, 251, 102, 26];

/// Seeds of the validation account: `["extra-account-metas", mint]`, under
/// the hook program.
pub const VALIDATION_SEED: &[u8] = b"extra-account-metas";

/// `Execute` accounts: source, mint, destination, authority, validation
/// account.
const VALIDATION_INDEX: usize = 4;
const EXECUTE_ACCOUNTS: usize = 5;

/// The `Execute` data: the discriminator, then the transfer amount as a
/// little-endian `u64`.
const EXECUTE_DATA_LEN: usize = 16;

/// Mint and owner: the token-account bytes that no transfer changes.
const TOKEN_ACCOUNT_KNOWN_LEN: usize = 64;

const PUBKEY_LEN: usize = 32;

/// 128 and above: a PDA of the program at index `discriminator - 128`.
const META_FIXED: u8 = 0;
const META_HOOK_PDA: u8 = 1;
const META_PUBKEY_DATA: u8 = 2;
const META_EXTERNAL_PDA: u8 = 128;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct AccountView<'a> {
	pub owner: &'a Address,
	pub data: &'a [u8],
}

/// What a lookup knows of an account.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Fetched<'a> {
	Account(AccountView<'a>),
	/// Fetched, and no account exists at the address.
	Missing,
	/// Not fetched yet.
	NotFetched,
}

#[must_use]
pub fn find_validation_address(mint: &Address, program: &Address) -> Address {
	Address::find_program_address(&[VALIDATION_SEED, mint.as_ref()], program).0
}

/// A decoded mint. [`MintInfo::load`] reads one.
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct MintState {
	pub token_program: Address,
	/// Fixed when the mint is created.
	pub decimals: u8,
	pub transfer_fee: Option<TransferFeeConfig>,
	/// The hook program. Token-2022 calls it on every transfer. The instruction
	/// must carry its accounts.
	pub transfer_hook: Option<Address>,
}

impl MintState {
	/// Fails with `ProgramError::IncorrectProgramId` if no token program owns
	/// the mint, and with another error if its data is not an initialized
	/// mint. An SPL Token mint is the 82-byte base mint alone, with no hook
	/// and no fee.
	pub(crate) fn load(mint: AccountView<'_>) -> Result<Self, ProgramError> {
		let token_program = *mint.owner;
		let Some(state) = mint_extensions(mint.data, &token_program)? else {
			return Ok(Self {
				token_program,
				decimals: spl_token_mint(mint.data)?.decimals,
				transfer_fee: None,
				transfer_hook: None,
			});
		};
		Ok(Self {
			token_program,
			decimals: state.base.decimals,
			transfer_fee: extension::<TransferFeeConfig>(&state)?.copied(),
			// Token-2022 calls a hook only when `program_id` is set.
			transfer_hook: extension::<TransferHook>(&state)?
				.and_then(|hook| Option::from(hook.program_id)),
		})
	}
}

/// A list that no resolver can resolve before the instruction runs, or that
/// reads the transfer amount.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Unresolvable {
	MalformedList,
	NoExecuteEntry,
	/// An extra is at an account index above 255.
	ListTooLong,
	MalformedExtra,
	MalformedSeed,
	/// A PDA has more than 15 seeds. The bump is the 16th.
	TooManySeeds,
	SeedTooLong,
	/// SPL's resolver fails on an extra: a read past the end of an account's
	/// data, or of a missing account, or seeds no address takes.
	ExtraUnresolved,
	/// A seed reads the transfer amount.
	ReadsTransferAmount,
	/// An extra reads past byte 16 of the `Execute` data: the discriminator,
	/// then the amount.
	ReadsPastInstructionData,
	/// An extra names an account at its own index or later.
	NamesUnresolvedAccount,
	/// An extra reads data that changes before the hook runs. This is data
	/// past the mint and owner of a token account that the instruction moves,
	/// or an account that it writes first.
	ReadsSwapTimeData,
}

impl fmt::Display for Unresolvable {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		f.write_str(match self {
			Self::MalformedList => "malformed list",
			Self::NoExecuteEntry => "no Execute entry in the list",
			Self::ListTooLong => "list too long",
			Self::MalformedExtra => "malformed extra",
			Self::MalformedSeed => "malformed seed",
			Self::TooManySeeds => "a PDA has more seeds than an address allows",
			Self::SeedTooLong => "seed longer than 32 bytes",
			Self::ExtraUnresolved => "an extra does not resolve",
			Self::ReadsTransferAmount => "a seed reads the transfer amount",
			Self::ReadsPastInstructionData => {
				"an extra reads past the end of the hook's instruction data"
			}
			Self::NamesUnresolvedAccount => {
				"an extra names an account not yet resolved"
			}
			Self::ReadsSwapTimeData => {
				"an extra reads account data the instruction changes first"
			}
		})
	}
}

#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum HookError {
	/// The mint infos do not hold these accounts. Fetch them. Insert them into
	/// a copy of each mint info. Build again until the build does not return
	/// `NotLoaded`.
	NotLoaded(Vec<Address>),
	/// The validation account is missing, or the hook program does not own it.
	/// Token-2022 still calls the hook, and the transfer fails.
	NoList,
	/// A mint in a [`HookState`] is not a mint that a token program owns, or
	/// its extensions do not decode. [`HookState::missing`] gives it.
	MalformedMint,
	Unresolvable(Unresolvable),
}

impl fmt::Display for HookError {
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
		match self {
			Self::NotLoaded(_) => {
				write!(f, "transfer hook accounts not loaded")
			}
			Self::NoList => {
				write!(f, "transfer hook has no ExtraAccountMetaList")
			}
			Self::MalformedMint => {
				write!(f, "a transfer's mint does not decode as a mint")
			}
			Self::Unresolvable(reason) => write!(
				f,
				"transfer hook cannot be resolved ahead of the instruction: \
				 {reason}"
			),
		}
	}
}

impl std::error::Error for HookError {}

impl From<Unresolvable> for HookError {
	fn from(reason: Unresolvable) -> Self {
		Self::Unresolvable(reason)
	}
}

/// A mint's armed hook and the state of its list.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Hook {
	mint: Address,
	program: Address,
	validation: Address,
	list: List,
}

#[derive(Clone, Debug, PartialEq, Eq)]
enum List {
	NotFetched,
	Missing,
	Loaded(Vec<u8>),
}

impl Hook {
	/// The hook of `mint`, which runs `program`. Returns `None` for a mint
	/// that runs no hook. Reads the list at its validation address from
	/// `accounts`. A list that the hook program does not own reads as missing.
	pub(crate) fn load<'a>(
		mint: &Address,
		program: Option<Address>,
		accounts: impl Fn(&Address) -> Fetched<'a>,
	) -> Option<Self> {
		let program = program?;
		let validation = find_validation_address(mint, &program);
		let list = match accounts(&validation) {
			Fetched::Account(account) if *account.owner == program => {
				List::Loaded(account.data.to_vec())
			}
			Fetched::Account(_) | Fetched::Missing => List::Missing,
			Fetched::NotFetched => List::NotFetched,
		};
		Some(Self {
			mint: *mint,
			program,
			validation,
			list,
		})
	}

	/// The list's bytes. `None` until it is fetched, and for a missing list.
	fn list(&self) -> Option<&[u8]> {
		match &self.list {
			List::Loaded(data) => Some(data),
			List::NotFetched | List::Missing => None,
		}
	}

	fn extras(&self) -> Result<Vec<ExtraAccountMeta>, HookError> {
		match &self.list {
			List::NotFetched => {
				Err(HookError::NotLoaded(vec![self.validation]))
			}
			List::Missing => Err(HookError::NoList),
			List::Loaded(data) => Ok(screen_list(data)?),
		}
	}
}

/// The hooks of a market's two mints, each read from its own [`MintInfo`].
/// `None` is a hook-free mint.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct MarketHooks {
	base: Option<Hook>,
	quote: Option<Hook>,
}

impl MarketHooks {
	/// The hooks of both mints. Reads each list at its validation address from
	/// the mint's own [`HookState`]. A list that the hook program does not own
	/// reads as missing.
	pub(crate) fn load(base: &MintInfo, quote: &MintInfo) -> Self {
		Self {
			base: Self::hook_of(base),
			quote: Self::hook_of(quote),
		}
	}

	fn hook_of(info: &MintInfo) -> Option<Hook> {
		Hook::load(&info.address, info.hook_program, |address| {
			info.fetched(address)
		})
	}

	/// Both hooks, base first.
	pub(crate) fn hooks(&self) -> Vec<&Hook> {
		[&self.base, &self.quote].into_iter().flatten().collect()
	}
}

/// The hook accounts of `legs` on the market of `mints`. Each list comes from
/// its own mint's [`HookState`]. A list read looks in both mints' snapshots,
/// then in `cache`.
///
/// # Errors
///
/// [`HookError::NotLoaded`] with each list of a moved mint that its snapshot
/// lacks. Else the errors of [`resolve_legs`].
pub(crate) fn resolve_market<'i, 'a: 'i>(
	mints: TradeMints<'i>,
	legs: &HookLegs,
	cache: impl Fn(&Address) -> Fetched<'a>,
) -> Result<Step<Resolved>, HookError> {
	let hooks = MarketHooks::load(mints.base, mints.quote);
	let hooks = hooks.hooks();
	let lists: Vec<Address> = hooks
		.iter()
		.filter(|hook| {
			hook.list == List::NotFetched
				&& legs.legs.iter().any(|leg| leg.mint == hook.mint)
		})
		.map(|hook| hook.validation)
		.collect();
	if !lists.is_empty() {
		return Err(HookError::NotLoaded(lists));
	}
	resolve_legs(&hooks, legs, &|key| {
		[mints.base, mints.quote]
			.into_iter()
			.map(|info| info.fetched(key))
			.find(|fetched| !matches!(fetched, Fetched::NotFetched))
			.unwrap_or_else(|| cache(key))
	})
}

/// One token transfer an instruction makes.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct HookLeg {
	pub source: Address,
	pub mint: Address,
	pub destination: Address,
	/// Signs the transfer and owns `source`.
	pub authority: Address,
	pub destination_owner: Address,
}

/// The transfers of one instruction, in the order the program makes them.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct HookLegs {
	pub legs: Vec<HookLeg>,
	/// Accounts the instruction writes before its transfers. A list that reads
	/// one does not resolve.
	pub written: Vec<Address>,
}

/// An account that exists, as a lookup fetched it.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct FetchedAccount {
	pub owner: Address,
	pub data: Vec<u8>,
}

/// A snapshot of the accounts that the hook lists of its mints read. A
/// builder resolves the hook accounts from the snapshot of each mint.
///
/// Fill the snapshot with [`missing`](Self::missing): fetch the accounts it
/// returns, [`insert`](Self::insert) each one and call it again, until it
/// returns none. A builder reads no account outside the snapshot. An account
/// that the snapshot does not have, such as a PDA of the trader, fails with
/// [`HookError::NotLoaded`], which names the accounts.
///
/// A hook armed or changed after the fill makes the transaction fail in
/// simulation. Fill the snapshot again.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct HookState {
	/// Each fetched account: `Some` where it exists, `None` where it does
	/// not. An address it does not hold was not fetched.
	pub accounts: BTreeMap<Address, Option<FetchedAccount>>,
}

impl HookState {
	/// Records what a fetch of `address` returned: `None` for no account.
	pub fn insert(
		&mut self,
		address: Address,
		account: Option<FetchedAccount>,
	) {
		self.accounts.insert(address, account);
	}

	/// What the snapshot knows of `address`.
	#[must_use]
	pub fn fetched(&self, address: &Address) -> Fetched<'_> {
		match self.accounts.get(address) {
			Some(Some(account)) => Fetched::Account(AccountView {
				owner: &account.owner,
				data: &account.data,
			}),
			Some(None) => Fetched::Missing,
			None => Fetched::NotFetched,
		}
	}

	/// The accounts to fetch next for a snapshot of `mints`: the mints, then
	/// each hook's list, then each account a list reads at a fixed address.
	/// Empty when the snapshot holds them all.
	///
	/// An address is fixed when no trade sets it: a fixed key, or a PDA or
	/// data key whose inputs are literal seeds, the first 8 bytes of the
	/// `Execute` data (the discriminator), the mint, the validation account
	/// and earlier fixed extras. It names no extra that reads the source, the
	/// destination or the authority.
	///
	/// A missing mint runs no hook. For a missing list, or a list that no
	/// resolver can resolve, it returns no more accounts, and a build fails.
	///
	/// # Errors
	///
	/// [`HookError::MalformedMint`] for a mint that does not decode.
	pub fn missing(
		&self,
		mints: &[Address],
	) -> Result<Vec<Address>, HookError> {
		let mut distinct: Vec<Address> = Vec::new();
		for mint in mints {
			if !distinct.contains(mint) {
				distinct.push(*mint);
			}
		}
		let unread: Vec<Address> = distinct
			.iter()
			.filter(|mint| !self.accounts.contains_key(mint))
			.copied()
			.collect();
		if !unread.is_empty() {
			return Ok(unread);
		}
		let mut hooks = Vec::new();
		let mut fetch = Vec::new();
		for mint in &distinct {
			let Fetched::Account(account) = self.fetched(mint) else {
				continue;
			};
			let state = MintState::load(account)
				.map_err(|_| HookError::MalformedMint)?;
			match Hook::load(mint, state.transfer_hook, |address| {
				self.fetched(address)
			}) {
				Some(hook) if hook.list == List::NotFetched => {
					fetch.push(hook.validation);
				}
				Some(hook) => hooks.push(hook),
				None => {}
			}
		}
		if !fetch.is_empty() {
			return Ok(fetch);
		}
		for hook in &hooks {
			for address in self.fixed_reads(hook) {
				if !fetch.contains(&address) {
					fetch.push(address);
				}
			}
		}
		Ok(fetch)
	}

	/// The accounts at a fixed address whose data `hook`'s list reads, which
	/// the snapshot lacks.
	fn fixed_reads(&self, hook: &Hook) -> Vec<Address> {
		let Ok(extras) = hook.extras() else {
			return Vec::new();
		};
		let list = hook.list().unwrap_or_default();
		let data = execute_data();
		// Each `Execute` account's address when no trade sets it: the mint
		// and the validation account, then each fixed extra.
		let mut fixed: Vec<Option<Address>> =
			vec![None, Some(hook.mint), None, None, Some(hook.validation)];
		let mut fetch = Vec::new();
		for extra in &extras {
			let mut bytes: Vec<Option<Vec<u8>>> = vec![None; fixed.len()];
			let mut known = true;
			for (index, _) in data_reads(extra) {
				// `None` where the trade sets the account.
				let address = fixed.get(index).copied().flatten();
				let read = if index == VALIDATION_INDEX {
					Some(list.to_vec())
				} else {
					address.and_then(|address| match self.fetched(&address) {
						Fetched::Account(account) => {
							Some(account.data.to_vec())
						}
						// On chain a missing account has no data.
						Fetched::Missing => Some(Vec::new()),
						Fetched::NotFetched => {
							if !fetch.contains(&address) {
								fetch.push(address);
							}
							None
						}
					})
				};
				match (read, bytes.get_mut(index)) {
					(Some(read), Some(slot)) => *slot = Some(read),
					_ => known = false,
				}
			}
			let keyed = key_reads(extra)
				.into_iter()
				.all(|index| fixed.get(index).copied().flatten().is_some());
			let resolved = (known && keyed)
				.then(|| {
					extra
						.resolve(&data, &hook.program, |index| {
							fixed.get(index).and_then(Option::as_ref).map(
								|key| {
									(
										key,
										bytes
											.get(index)
											.and_then(|read| read.as_deref()),
									)
								},
							)
						})
						.ok()
				})
				.flatten();
			fixed.push(resolved.map(|meta| meta.pubkey));
		}
		fetch
	}
}

/// One leg's `Execute`: every account the hook receives, with the role SPL's
/// resolver gives it, and the flags the list declares for each extra.
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct LegExecute {
	pub(crate) program: Address,
	/// Source, mint, destination, authority, the validation account, then
	/// each extra.
	pub(crate) metas: Vec<AccountMeta>,
	/// `(signer, writable)` as the list declares each extra.
	pub(crate) declared: Vec<(bool, bool)>,
}

impl LegExecute {
	/// SPL resolver order: the extras, the hook program, the validation
	/// account.
	fn trailing(&self) -> impl Iterator<Item = AccountMeta> + '_ {
		let validation = self
			.metas
			.get(VALIDATION_INDEX)
			.map_or_else(Address::default, |meta| meta.pubkey);
		self.metas.iter().skip(EXECUTE_ACCOUNTS).cloned().chain([
			AccountMeta::new_readonly(self.program, false),
			AccountMeta::new_readonly(validation, false),
		])
	}
}

pub(crate) struct Resolved {
	pub(crate) accounts: Vec<AccountMeta>,
	pub(crate) executes: Vec<LegExecute>,
	/// Each account whose data a list read through the lookup.
	pub(crate) reads: Vec<Address>,
}

pub(crate) enum Step<T> {
	Done(T),
	Fetch(Vec<Address>),
}

/// The token accounts the legs move, each with its mint and owner.
fn moved_accounts(
	legs: &HookLegs,
) -> Vec<(Address, [u8; TOKEN_ACCOUNT_KNOWN_LEN])> {
	let mut moved: Vec<(Address, [u8; TOKEN_ACCOUNT_KNOWN_LEN])> = Vec::new();
	for leg in &legs.legs {
		for (account, owner) in [
			(leg.source, leg.authority),
			(leg.destination, leg.destination_owner),
		] {
			if !moved.iter().any(|(key, _)| *key == account) {
				moved.push((account, token_account_prefix(&leg.mint, &owner)));
			}
		}
	}
	moved
}

fn token_account_prefix(
	mint: &Address,
	owner: &Address,
) -> [u8; TOKEN_ACCOUNT_KNOWN_LEN] {
	let mut prefix = [0; TOKEN_ACCOUNT_KNOWN_LEN];
	let (mint_bytes, owner_bytes) = prefix.split_at_mut(PUBKEY_LEN);
	mint_bytes.copy_from_slice(mint.as_ref());
	owner_bytes.copy_from_slice(owner.as_ref());
	prefix
}

/// The hook accounts of `legs`, or the accounts that `accounts` has not
/// fetched. `hooks` holds the hook of each hooked mint that the legs move. A
/// leg whose mint has no hook in `hooks` is hook-free.
///
/// Each extra resolves as SPL's resolver resolves it, from the transfer's
/// `Execute`: source, mint, destination, authority and the validation
/// account, all read-only. An extra that repeats a key of the `Execute` is
/// read-only when each earlier copy is read-only. No extra signs.
///
/// The hook program and the validation account follow the extras. The legs
/// merge into one list. Each address occurs once, writable if one leg makes
/// it writable.
///
/// A token account that a leg moves reads as its mint and owner, so it need
/// not exist before the instruction.
///
/// # Errors
///
/// [`HookError::NotLoaded`] for a list that was not fetched.
/// [`HookError::NoList`] for a missing list.
/// [`HookError::Unresolvable`] for a list that does not resolve.
pub(crate) fn resolve_legs<'a>(
	hooks: &[&Hook],
	legs: &HookLegs,
	accounts: &impl Fn(&Address) -> Fetched<'a>,
) -> Result<Step<Resolved>, HookError> {
	let moved = moved_accounts(legs);
	let mut executes = Vec::new();
	let mut fetch: Vec<Address> = Vec::new();
	let mut reader = Reader {
		moved: &moved,
		written: &legs.written,
		accounts,
		reads: Vec::new(),
	};
	for leg in &legs.legs {
		let Some(hook) = hooks.iter().find(|hook| hook.mint == leg.mint) else {
			continue;
		};
		match resolve_leg(hook, leg, &mut reader)? {
			Step::Done(execute) => executes.push(execute),
			// The other legs still name what they read.
			Step::Fetch(addresses) => {
				for address in addresses {
					if !fetch.contains(&address) {
						fetch.push(address);
					}
				}
			}
		}
	}
	if !fetch.is_empty() {
		return Ok(Step::Fetch(fetch));
	}
	let mut merged: Vec<AccountMeta> = Vec::new();
	for execute in &executes {
		for meta in execute.trailing() {
			match merged
				.iter_mut()
				.find(|account| account.pubkey == meta.pubkey)
			{
				Some(existing) => existing.is_writable |= meta.is_writable,
				None => merged.push(meta),
			}
		}
	}
	Ok(Step::Done(Resolved {
		accounts: merged,
		executes,
		reads: reader.reads,
	}))
}

/// Where SPL's resolver finds the data of an `Execute` account.
struct Reader<'r, F> {
	moved: &'r [(Address, [u8; TOKEN_ACCOUNT_KNOWN_LEN])],
	written: &'r [Address],
	accounts: &'r F,
	/// Each account read through `accounts`.
	reads: Vec<Address>,
}

enum Data {
	Bytes(Vec<u8>),
	NotFetched,
}

impl<'a, F: Fn(&Address) -> Fetched<'a>> Reader<'_, F> {
	/// The data of `key` that a read up to byte `end` sees on chain.
	fn read(
		&mut self,
		key: &Address,
		end: usize,
	) -> Result<Data, Unresolvable> {
		if let Some((_, prefix)) =
			self.moved.iter().find(|(account, _)| account == key)
		{
			// Past the mint and owner, the transfer changes the account.
			if end > TOKEN_ACCOUNT_KNOWN_LEN {
				return Err(Unresolvable::ReadsSwapTimeData);
			}
			return Ok(Data::Bytes(prefix.to_vec()));
		}
		if self.written.contains(key) {
			return Err(Unresolvable::ReadsSwapTimeData);
		}
		Ok(match (self.accounts)(key) {
			Fetched::Account(account) => {
				self.record(key);
				Data::Bytes(account.data.to_vec())
			}
			Fetched::Missing => {
				self.record(key);
				// On chain a missing account has no data, and the read fails.
				Data::Bytes(Vec::new())
			}
			Fetched::NotFetched => Data::NotFetched,
		})
	}

	fn record(&mut self, key: &Address) {
		if !self.reads.contains(key) {
			self.reads.push(*key);
		}
	}
}

/// Rust `ExtraAccountMetaList::add_to_instruction` for one transfer.
fn resolve_leg<'a, F: Fn(&Address) -> Fetched<'a>>(
	hook: &Hook,
	leg: &HookLeg,
	reader: &mut Reader<'_, F>,
) -> Result<Step<LegExecute>, HookError> {
	let extras = hook.extras()?;
	let list = hook.list().unwrap_or_default();
	let data = execute_data();

	// Token-2022 passes the five `Execute` accounts read-only.
	let mut metas: Vec<AccountMeta> = [
		leg.source,
		leg.mint,
		leg.destination,
		leg.authority,
		hook.validation,
	]
	.into_iter()
	.map(|key| AccountMeta::new_readonly(key, false))
	.collect();
	let mut declared = Vec::with_capacity(extras.len());
	for extra in &extras {
		let mut bytes: Vec<Option<Vec<u8>>> = vec![None; metas.len()];
		for (index, end) in data_reads(extra) {
			let Some(slot) = bytes.get_mut(index) else {
				// The list check allows only reads of earlier accounts.
				return Err(Unresolvable::NamesUnresolvedAccount.into());
			};
			if index == VALIDATION_INDEX {
				*slot = Some(list.to_vec());
				continue;
			}
			let key =
				metas.get(index).map(|meta| meta.pubkey).unwrap_or_default();
			match reader.read(&key, end)? {
				Data::Bytes(read) => *slot = Some(read),
				Data::NotFetched => return Ok(Step::Fetch(vec![key])),
			}
		}
		let resolved = extra
			.resolve(&data, &hook.program, |index| {
				metas.get(index).map(|meta| {
					(
						&meta.pubkey,
						bytes.get(index).and_then(|read| read.as_deref()),
					)
				})
			})
			.map_err(|_| Unresolvable::ExtraUnresolved)?;
		// `de_escalate_account_meta`: a repeat of a key of the `Execute` is
		// read-only when each earlier copy is read-only. Never a signer.
		let earlier = metas
			.iter()
			.filter(|meta| meta.pubkey == resolved.pubkey)
			.map(|meta| meta.is_writable)
			.reduce(|any, writable| any || writable);
		metas.push(AccountMeta {
			pubkey: resolved.pubkey,
			is_signer: false,
			is_writable: resolved.is_writable && earlier != Some(false),
		});
		declared
			.push((bool::from(extra.is_signer), bool::from(extra.is_writable)));
	}
	Ok(Step::Done(LegExecute {
		program: hook.program,
		metas,
		declared,
	}))
}

/// The `Execute` data that a resolution reads: the discriminator, then a zero
/// amount. No screened list reads the amount.
const fn execute_data() -> [u8; EXECUTE_DATA_LEN] {
	let mut data = [0; EXECUTE_DATA_LEN];
	let (discriminator, _) = data.split_at_mut(EXECUTE_DISCRIMINATOR.len());
	discriminator.copy_from_slice(&EXECUTE_DISCRIMINATOR);
	data
}

struct Execute;

impl SplDiscriminate for Execute {
	const SPL_DISCRIMINATOR: ArrayDiscriminator =
		ArrayDiscriminator::new(EXECUTE_DISCRIMINATOR);
}

fn unpack_list(data: &[u8]) -> Result<Vec<ExtraAccountMeta>, Unresolvable> {
	let list_error = |error: ProgramError| {
		if error == ProgramError::from(TlvError::TypeNotFound) {
			Unresolvable::NoExecuteEntry
		} else {
			Unresolvable::MalformedList
		}
	};
	let state = TlvStateBorrowed::unpack(data).map_err(list_error)?;
	let extras = ExtraAccountMetaList::unpack_with_tlv_state::<Execute>(&state)
		.map_err(list_error)?;
	Ok(extras.iter().copied().collect())
}

/// Refuses a list that SPL's resolver fails or panics on, whatever the
/// transfer, and a list that reads the transfer amount.
fn screen_list(data: &[u8]) -> Result<Vec<ExtraAccountMeta>, Unresolvable> {
	let extras = unpack_list(data)?;
	for (index, extra) in extras.iter().enumerate() {
		let position = index
			.checked_add(EXECUTE_ACCOUNTS)
			.filter(|position| u8::try_from(*position).is_ok())
			.ok_or(Unresolvable::ListTooLong)?;
		screen_extra(extra, position)?;
	}
	if reads_amount(&extras) {
		return Err(Unresolvable::ReadsTransferAmount);
	}
	Ok(extras)
}

fn screen_extra(
	extra: &ExtraAccountMeta,
	position: usize,
) -> Result<(), Unresolvable> {
	match extra.discriminator {
		META_FIXED => Ok(()),
		META_HOOK_PDA => screen_seeds(&extra.address_config, position),
		META_PUBKEY_DATA => match PubkeyData::unpack(&extra.address_config)
			.map_err(|_| Unresolvable::MalformedExtra)?
		{
			PubkeyData::AccountData { account_index, .. } => {
				prior(account_index, position)
			}
			// A pubkey is 32 bytes. The `Execute` data is 16.
			PubkeyData::InstructionData { .. } => {
				Err(Unresolvable::ReadsPastInstructionData)
			}
			PubkeyData::Uninitialized => Err(Unresolvable::MalformedExtra),
		},
		external => match external.checked_sub(META_EXTERNAL_PDA) {
			Some(program) => {
				prior(program, position)?;
				screen_seeds(&extra.address_config, position)
			}
			None => Err(Unresolvable::MalformedExtra),
		},
	}
}

fn seeds_of(extra: &ExtraAccountMeta) -> Vec<Seed> {
	match extra.discriminator {
		META_FIXED | META_PUBKEY_DATA => Vec::new(),
		_ => Seed::unpack_address_config(&extra.address_config)
			.unwrap_or_default(),
	}
}

fn screen_seeds(
	config: &[u8; 32],
	position: usize,
) -> Result<(), Unresolvable> {
	let seeds = Seed::unpack_address_config(config)
		.map_err(|_| Unresolvable::MalformedSeed)?;
	// With the bump, this is above `MAX_SEEDS`: `find_program_address` panics.
	if seeds.len() >= MAX_SEEDS {
		return Err(Unresolvable::TooManySeeds);
	}
	for seed in &seeds {
		match *seed {
			// A literal fits in the 32-byte config. It is never too long.
			Seed::Uninitialized | Seed::Literal { .. } => {}
			Seed::InstructionData { index, length } => {
				let end = usize::from(index)
					.checked_add(usize::from(length))
					.ok_or(Unresolvable::MalformedSeed)?;
				if end > EXECUTE_DATA_LEN {
					return Err(Unresolvable::ReadsPastInstructionData);
				}
			}
			Seed::AccountKey { index } => prior(index, position)?,
			Seed::AccountData {
				account_index,
				length,
				..
			} => {
				if usize::from(length) > PUBKEY_LEN {
					return Err(Unresolvable::SeedTooLong);
				}
				prior(account_index, position)?;
			}
		}
	}
	Ok(())
}

/// `index` must name an account resolved before `position`, as on-chain.
fn prior(index: u8, position: usize) -> Result<(), Unresolvable> {
	if usize::from(index) < position {
		Ok(())
	} else {
		Err(Unresolvable::NamesUnresolvedAccount)
	}
}

/// `true` if a seed reads bytes 8 to 16 of `Execute`, the transfer amount.
fn reads_amount(extras: &[ExtraAccountMeta]) -> bool {
	extras.iter().flat_map(seeds_of).any(|seed| match seed {
		Seed::InstructionData { index, length } => {
			length > 0 && read_end(index, length) > EXECUTE_DISCRIMINATOR.len()
		}
		_ => false,
	})
}

/// The end of a read of `length` bytes at `offset`.
#[expect(
	clippy::arithmetic_side_effects,
	reason = "two u8s cannot overflow a u16"
)]
fn read_end(offset: u8, length: u8) -> usize {
	usize::from(u16::from(offset) + u16::from(length))
}

/// The `Execute` account index and the end of each data read of `extra`.
fn data_reads(extra: &ExtraAccountMeta) -> Vec<(usize, usize)> {
	if extra.discriminator == META_PUBKEY_DATA {
		return match PubkeyData::unpack(&extra.address_config) {
			Ok(PubkeyData::AccountData {
				account_index,
				data_index,
			}) => vec![(
				usize::from(account_index),
				// A pubkey read is 32 bytes.
				read_end(data_index, 32),
			)],
			_ => Vec::new(),
		};
	}
	seeds_of(extra)
		.into_iter()
		.filter_map(|seed| match seed {
			Seed::AccountData {
				account_index,
				data_index,
				length,
			} => {
				Some((usize::from(account_index), read_end(data_index, length)))
			}
			_ => None,
		})
		.collect()
}

/// The `Execute` account index of each key `extra` reads: the program of an
/// external PDA, and each account-key seed.
fn key_reads(extra: &ExtraAccountMeta) -> Vec<usize> {
	let program = extra
		.discriminator
		.checked_sub(META_EXTERNAL_PDA)
		.map(usize::from);
	program
		.into_iter()
		.chain(seeds_of(extra).into_iter().filter_map(|seed| match seed {
			Seed::AccountKey { index } => Some(usize::from(index)),
			_ => None,
		}))
		.collect()
}

#[cfg(test)]
mod tests;