1use std::{
2 any::Any,
3 collections::{BTreeMap, BTreeSet, HashMap},
4};
5
6use alloy::primitives::U256;
7use num_bigint::BigUint;
8use num_traits::ToPrimitive;
9use tycho_common::{
10 dto::ProtocolStateDelta,
11 models::token::Token,
12 simulation::{
13 errors::{SimulationError, TransitionError},
14 protocol_sim::{
15 Balances, BlockContext, GetAmountOutResult, PoolSwap, Price, ProtocolSim,
16 QueryPoolSwapParams, SwapConstraint,
17 },
18 },
19 Bytes,
20};
21
22use super::{
23 decoder::{allowance_key, apply_attributes, board_key, hex_address, pair_key, AttributeChange},
24 math::{
25 after_protocol_fee, board_view, merge, Address, BlockEnv, Board, BoardInputs, BoardView,
26 Plan, PricingError,
27 },
28};
29use crate::{
30 evm::protocol::u256_num::{biguint_to_u256, u256_to_biguint},
31 utils::decimals_exponent,
32};
33
34const BASE_GAS: u64 = 40_000;
40const GAS_PER_DARK_BOARD: u64 = 15_000;
41const GAS_PER_LIVE_BOARD: u64 = 60_000;
42const GAS_PER_FILL: u64 = 130_000;
43
44#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
46pub enum ProviderKind {
47 Balance,
49 Vault(Address),
51 Unbounded,
53}
54
55#[derive(Clone, Copy, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
56pub struct ProviderConfig {
57 pub kind: ProviderKind,
58}
59
60#[derive(Clone, Debug, Default, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
64pub struct BiconomyState {
65 pub venue: Address,
66 pub executor: Address,
68 pub fee_bps: u16,
69 pub maker_count: u64,
71 pub maker_slots: BTreeMap<u8, Address>,
73 pub boards: BTreeMap<String, BTreeMap<u8, U256>>,
75 pub anchors: BTreeMap<String, U256>,
77 pub paused: BTreeSet<Address>,
78 pub providers: BTreeMap<String, ProviderConfig>,
80 pub signers: BTreeMap<String, Address>,
82 pub approved_executors: BTreeMap<String, Address>,
85 pub router_counts: BTreeMap<String, U256>,
87 pub routers: BTreeMap<String, Address>,
90 pub balances: BTreeMap<String, U256>,
92 pub allowances: BTreeMap<String, U256>,
94 pub block: BlockEnvState,
96}
97
98#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
99pub struct BlockEnvState {
100 pub number: u64,
101 pub timestamp: u64,
102}
103
104fn balance_value(word: U256) -> U256 {
106 word & (U256::MAX >> 1)
107}
108
109impl BiconomyState {
110 pub fn makers(&self) -> Vec<Address> {
112 let count = u8::try_from(self.maker_count).unwrap_or(u8::MAX);
113 (0..count)
114 .map(|i| {
115 self.maker_slots
116 .get(&i)
117 .copied()
118 .unwrap_or_default()
119 })
120 .collect()
121 }
122
123 fn balance(&self, token: &Address, holder: &Address) -> U256 {
124 self.balances
125 .get(&pair_key(token, holder))
126 .copied()
127 .map(balance_value)
128 .unwrap_or_default()
129 }
130
131 fn allowance(&self, token: &Address, owner: &Address, spender: &Address) -> U256 {
132 self.allowances
133 .get(&allowance_key(token, owner, spender))
134 .copied()
135 .unwrap_or_default()
136 }
137
138 fn available(&self, provider: &Address, token: &Address) -> Option<U256> {
141 let config = self
142 .providers
143 .get(&hex_address(provider))?;
144 Some(match config.kind {
145 ProviderKind::Balance => self.balance(token, provider),
146 ProviderKind::Vault(vault) if self.router(&vault) == Some(*provider) => self
147 .balance(token, &vault)
148 .min(self.allowance(token, &vault, provider)),
149 ProviderKind::Vault(_) => U256::ZERO,
150 ProviderKind::Unbounded => U256::MAX,
151 })
152 }
153
154 fn router(&self, vault: &Address) -> Option<Address> {
156 let key = hex_address(vault);
157 if self
158 .router_counts
159 .get(&key)
160 .is_none_or(|count| count.is_zero())
161 {
162 return None;
163 }
164 self.routers.get(&key).copied()
165 }
166
167 fn signer_matches(&self, provider: &Address, mm: &Address) -> bool {
169 let key = hex_address(provider);
170 self.providers.contains_key(&key) && self.signers.get(&key) == Some(mm)
171 }
172
173 fn approves_executor(&self, provider: &Address) -> bool {
176 self.approved_executors
177 .get(&hex_address(provider)) ==
178 Some(&self.executor)
179 }
180
181 fn env(&self) -> BlockEnv {
182 BlockEnv { number: self.block.number, timestamp: self.block.timestamp }
183 }
184
185 fn board(&self, mm: &Address, token_in: &Address, token_out: &Address) -> Board {
186 self.boards
187 .get(&board_key(mm, token_in, token_out))
188 .map(Board::decode)
189 .unwrap_or_else(|| Board::decode(&BTreeMap::new()))
190 }
191
192 fn anchor(&self, mm: &Address, token_in: &Address, token_out: &Address) -> U256 {
193 let (t0, t1) =
194 if token_in < token_out { (token_in, token_out) } else { (token_out, token_in) };
195 self.anchors
196 .get(&board_key(mm, t0, t1))
197 .copied()
198 .unwrap_or_default()
199 }
200
201 fn board_views(
203 &self,
204 token_in: &Address,
205 token_out: &Address,
206 ) -> Result<(Vec<Board>, Vec<BoardView>), PricingError> {
207 let env = self.env();
208 let makers = self.makers();
209 let mut boards = Vec::with_capacity(makers.len());
210 let mut views = Vec::with_capacity(makers.len());
211 for mm in &makers {
212 let board = self.board(mm, token_in, token_out);
213 let inputs = BoardInputs {
214 board: &board,
215 anchor: self.anchor(mm, token_in, token_out),
216 paused: self.paused.contains(mm),
217 signer_matches: self.signer_matches(&board.provider, mm),
218 available_out: self.available(&board.provider, token_out),
219 };
220 views.push(board_view(&inputs, token_in, token_out, &env)?);
221 boards.push(board);
222 }
223 Ok((boards, views))
224 }
225
226 fn quote(
228 &self,
229 token_in: &Address,
230 token_out: &Address,
231 amount_in: U256,
232 ) -> Result<(U256, Plan, Vec<Board>, BigUint), SimulationError> {
233 if amount_in.is_zero() {
234 return Err(inactive());
235 }
236 let (boards, views) = self
237 .board_views(token_in, token_out)
238 .map_err(pricing_error)?;
239 let plan = merge(&views, amount_in);
240 if plan.covered < amount_in || plan.out.is_zero() {
241 return Err(inactive());
242 }
243 self.check_fillable(&boards, &plan)?;
244 let gas = gas(&views, &plan);
245 Ok((after_protocol_fee(plan.out, self.fee_bps), plan, boards, gas))
246 }
247
248 fn routes_to_stuck_maker(&self, boards: &[Board], plan: &Plan) -> bool {
250 plan.alloc
251 .iter()
252 .zip(boards)
253 .any(|(alloc, board)| !alloc.is_zero() && !self.approves_executor(&board.provider))
254 }
255
256 fn check_fillable(&self, boards: &[Board], plan: &Plan) -> Result<(), SimulationError> {
259 if self.routes_to_stuck_maker(boards, plan) {
260 return Err(SimulationError::RecoverableError(
261 "Biconomy venue would route to a maker whose provider does not approve the \
262 executor, so the swap reverts (FillLegFailed)"
263 .to_owned(),
264 ));
265 }
266 Ok(())
267 }
268
269 fn after_fill(
273 &self,
274 token_in: &Address,
275 token_out: &Address,
276 plan: &Plan,
277 boards: &[Board],
278 ) -> Self {
279 let mut next = self.clone();
280 let number = self.block.number;
281 for (i, mm) in self.makers().iter().enumerate() {
282 let alloc = plan.alloc[i];
283 if alloc.is_zero() {
284 continue;
285 }
286 let board = &boards[i];
287 let in_block =
288 if board.last_fill_block == number { board.filled_in_block + alloc } else { alloc };
289 let words = next
290 .boards
291 .entry(board_key(mm, token_in, token_out))
292 .or_default();
293 Board::record_fill(words, board.filled + alloc, number, in_block);
294
295 next.move_inventory(&board.provider, token_in, token_out, alloc, plan.out_by_maker[i]);
296 }
297 next
298 }
299}
300
301impl BiconomyState {
302 fn executable_capacity(&self, boards: &[Board], views: &[BoardView], capacity: U256) -> U256 {
307 let executable = |amount: U256| {
308 let plan = merge(views, amount);
309 plan.covered == amount && !self.routes_to_stuck_maker(boards, &plan)
310 };
311 if executable(capacity) {
312 return capacity;
313 }
314 largest_passing(capacity, executable)
315 }
316
317 fn trade_limit_amount(&self, views: &[BoardView], limit: &Price, capacity: U256) -> U256 {
321 let meets = |amount: U256| {
322 let out = after_protocol_fee(merge(views, amount).out, self.fee_bps);
323 !out.is_zero() &&
324 u256_to_biguint(out) * &limit.denominator >=
325 u256_to_biguint(amount) * &limit.numerator
326 };
327 if meets(capacity) {
328 return capacity;
329 }
330 largest_passing(capacity, meets)
331 }
332
333 fn target_price_amount(
339 &self,
340 views: &[BoardView],
341 target: &Price,
342 tolerance: f64,
343 capacity: U256,
344 ) -> Result<U256, SimulationError> {
345 let fee_factor = BigUint::from(10_000u32 - u32::from(self.fee_bps));
348 let scale = BigUint::from(10u8).pow(18) * BigUint::from(10_000u32);
349 let versus_target = |price: U256| {
350 (u256_to_biguint(price) * &fee_factor * &target.denominator, &target.numerator * &scale)
351 };
352 let at_least_target = |price: U256| {
353 let (marginal, target) = versus_target(price);
354 marginal >= target
355 };
356 let within_band = |price: U256| {
357 let (marginal, target) = versus_target(price);
358 let ratio = marginal.to_f64().unwrap_or(f64::MAX) / target.to_f64().unwrap_or(f64::MAX);
359 ratio <= 1.0 + tolerance
360 };
361
362 let spot = marginal_after(views, U256::ZERO).ok_or_else(inactive)?;
363 if !at_least_target(spot) {
364 return Err(SimulationError::InvalidInput(
365 "Target is above the Biconomy venue's marginal price".to_owned(),
366 None,
367 ));
368 }
369 if within_band(spot) {
370 return Ok(U256::ZERO);
371 }
372 let reached = |amount: U256| marginal_after(views, amount).is_none_or(within_band);
373 if !reached(capacity) {
374 return Ok(capacity);
375 }
376 let amount = largest_passing(capacity, |amount| !reached(amount)) + U256::from(1u8);
378 Ok(match marginal_after(views, amount) {
379 Some(price) if !at_least_target(price) => amount - U256::from(1u8),
380 _ => amount,
381 })
382 }
383
384 fn move_inventory(
385 &mut self,
386 provider: &Address,
387 token_in: &Address,
388 token_out: &Address,
389 amount_in: U256,
390 amount_out: U256,
391 ) {
392 let Some(config) = self
393 .providers
394 .get(&hex_address(provider))
395 .copied()
396 else {
397 return;
398 };
399 let holder = match config.kind {
400 ProviderKind::Balance => *provider,
401 ProviderKind::Vault(vault) => {
402 let key = allowance_key(token_out, &vault, provider);
403 if let Some(allowance) = self.allowances.get_mut(&key) {
404 if *allowance != U256::MAX {
405 *allowance = allowance.saturating_sub(amount_out);
406 }
407 }
408 vault
409 }
410 ProviderKind::Unbounded => return,
411 };
412 for (token, delta_in, delta_out) in
413 [(token_in, amount_in, U256::ZERO), (token_out, U256::ZERO, amount_out)]
414 {
415 let entry = self
416 .balances
417 .entry(pair_key(token, &holder))
418 .or_default();
419 let value_mask: U256 = U256::MAX >> 1;
420 let flags = *entry & !value_mask;
421 let value = balance_value(*entry)
422 .saturating_add(delta_in)
423 .saturating_sub(delta_out);
424 *entry = flags | value;
425 }
426 }
427}
428
429fn largest_passing(high: U256, passes: impl Fn(U256) -> bool) -> U256 {
433 let (mut low, mut high) = (U256::ZERO, high);
434 while high - low > U256::from(1u8) {
435 let mid = low + (high - low) / U256::from(2u8);
436 if passes(mid) {
437 low = mid;
438 } else {
439 high = mid;
440 }
441 }
442 low
443}
444
445fn marginal_after(views: &[BoardView], amount: U256) -> Option<U256> {
448 let plan = merge(views, amount);
449 views
450 .iter()
451 .zip(&plan.alloc)
452 .filter(|(view, alloc)| view.remaining > **alloc)
453 .filter_map(|(view, alloc)| {
454 let cursor = view.filled + *alloc;
455 view.levels
456 .iter()
457 .find(|level| level.size > cursor)
458 .map(|level| level.price)
459 })
460 .max()
461}
462
463fn amount_u256(amount: &BigUint) -> Result<U256, SimulationError> {
465 if amount.bits() > 256 {
466 return Err(SimulationError::InvalidInput("amount_in exceeds uint256".to_owned(), None));
467 }
468 Ok(biguint_to_u256(amount))
469}
470
471fn gas(views: &[BoardView], plan: &Plan) -> BigUint {
472 let live = views
473 .iter()
474 .filter(|view| !view.remaining.is_zero())
475 .count() as u64;
476 let dark = views.len() as u64 - live;
477 let fills = plan
478 .alloc
479 .iter()
480 .filter(|alloc| !alloc.is_zero())
481 .count() as u64;
482 BigUint::from(
483 BASE_GAS + GAS_PER_DARK_BOARD * dark + GAS_PER_LIVE_BOARD * live + GAS_PER_FILL * fills,
484 )
485}
486
487fn inactive() -> SimulationError {
488 SimulationError::RecoverableError("Biconomy venue cannot cover the size (Inactive)".to_owned())
489}
490
491fn pricing_error(err: PricingError) -> SimulationError {
492 SimulationError::FatalError(format!("Biconomy venue pricing would revert: {err:?}"))
493}
494
495fn address(token: &Bytes) -> Result<Address, SimulationError> {
496 token
497 .as_ref()
498 .try_into()
499 .map_err(|_not_20_bytes| {
500 SimulationError::InvalidInput(format!("invalid token address {token}"), None)
501 })
502}
503
504fn wad_to_f64(value: U256) -> f64 {
505 value
506 .to_string()
507 .parse::<f64>()
508 .unwrap_or(0.0) /
509 1e18
510}
511
512#[typetag::serde]
513impl ProtocolSim for BiconomyState {
514 fn fee(&self) -> f64 {
515 f64::from(self.fee_bps) / 10_000.0
516 }
517
518 fn spot_price(&self, base: &Token, quote: &Token) -> Result<f64, SimulationError> {
519 let token_in = address("e.address)?;
521 let token_out = address(&base.address)?;
522 let (_, views) = self
523 .board_views(&token_in, &token_out)
524 .map_err(pricing_error)?;
525 let best = views
527 .iter()
528 .filter(|view| !view.remaining.is_zero())
529 .filter_map(|view| {
530 view.levels
531 .iter()
532 .find(|level| level.size > view.filled)
533 })
534 .map(|level| level.price)
535 .max()
536 .ok_or_else(inactive)?;
537 let base_per_quote = wad_to_f64(best) *
540 10f64.powf(f64::from(decimals_exponent(quote.decimals, base.decimals)?));
541 if base_per_quote <= 0.0 {
542 return Err(inactive());
543 }
544 Ok(1.0 / base_per_quote / (1.0 - self.fee()))
545 }
546
547 fn get_amount_out(
548 &self,
549 amount_in: BigUint,
550 token_in: &Token,
551 token_out: &Token,
552 ) -> Result<GetAmountOutResult, SimulationError> {
553 let tin = address(&token_in.address)?;
554 let tout = address(&token_out.address)?;
555 let (amount_out, plan, boards, gas) = self.quote(&tin, &tout, amount_u256(&amount_in)?)?;
556 let next = self.after_fill(&tin, &tout, &plan, &boards);
557 Ok(GetAmountOutResult::new(u256_to_biguint(amount_out), gas, Box::new(next)))
558 }
559
560 fn get_limits(
561 &self,
562 sell_token: Bytes,
563 buy_token: Bytes,
564 ) -> Result<(BigUint, BigUint), SimulationError> {
565 let tin = address(&sell_token)?;
566 let tout = address(&buy_token)?;
567 let (boards, views) = self
568 .board_views(&tin, &tout)
569 .map_err(pricing_error)?;
570 let none = (BigUint::ZERO, BigUint::ZERO);
571 let room = views
572 .iter()
573 .fold(U256::ZERO, |sum, view| sum.saturating_add(view.remaining));
574 if room.is_zero() {
575 return Ok(none);
576 }
577 let mut plan = merge(&views, room);
580 if plan.covered < room {
581 let capacity = plan.covered;
582 if capacity.is_zero() {
583 return Ok(none);
584 }
585 plan = merge(&views, capacity);
586 if plan.covered != capacity {
587 return Ok(none);
588 }
589 }
590 if plan.out.is_zero() {
591 return Ok(none);
592 }
593 if self
596 .check_fillable(&boards, &plan)
597 .is_err()
598 {
599 let executable = self.executable_capacity(&boards, &views, plan.covered);
600 if executable.is_zero() {
601 return Ok(none);
602 }
603 plan = merge(&views, executable);
604 if plan.out.is_zero() {
605 return Ok(none);
606 }
607 }
608 Ok((
609 u256_to_biguint(plan.covered),
610 u256_to_biguint(after_protocol_fee(plan.out, self.fee_bps)),
611 ))
612 }
613
614 fn delta_transition(
615 &mut self,
616 delta: ProtocolStateDelta,
617 _tokens: &HashMap<Bytes, Token>,
618 _balances: &Balances,
619 ) -> Result<(), TransitionError> {
620 let changes = delta
621 .updated_attributes
622 .iter()
623 .filter(|(name, _)| *name != "block_number" && *name != "block_timestamp")
624 .map(|(name, value)| AttributeChange::Set(name, value))
625 .chain(
626 delta
627 .deleted_attributes
628 .iter()
629 .map(AttributeChange::Delete),
630 );
631 apply_attributes(self, changes).map_err(|err| TransitionError::DecodeError(err.to_string()))
632 }
633
634 fn query_pool_swap(&self, params: &QueryPoolSwapParams) -> Result<PoolSwap, SimulationError> {
638 let (price, tolerance, min_amount_in, max_amount_in, trade_limit) = match params
639 .swap_constraint()
640 {
641 SwapConstraint::TradeLimitPrice { limit, tolerance, min_amount_in, max_amount_in } => {
642 (limit, *tolerance, min_amount_in, max_amount_in, true)
643 }
644 SwapConstraint::PoolTargetPrice { target, tolerance, min_amount_in, max_amount_in } => {
645 (target, *tolerance, min_amount_in, max_amount_in, false)
646 }
647 };
648 if price.numerator == BigUint::ZERO ||
649 price.denominator == BigUint::ZERO ||
650 !tolerance.is_finite() ||
651 tolerance < 0.0 ||
652 matches!((min_amount_in, max_amount_in), (Some(min), Some(max)) if min > max)
653 {
654 return Err(SimulationError::InvalidInput(
655 "invalid Biconomy price query bounds".to_owned(),
656 None,
657 ));
658 }
659 let token_in = params.token_in();
660 let token_out = params.token_out();
661 let zero = || PoolSwap::new(BigUint::ZERO, BigUint::ZERO, self.clone_box(), None);
662
663 let (max_in, _) = self.get_limits(token_in.address.clone(), token_out.address.clone())?;
664 let mut capacity = biguint_to_u256(&max_in);
665 if let Some(max) = max_amount_in {
666 if max.bits() <= 256 {
667 capacity = capacity.min(biguint_to_u256(max));
668 }
669 }
670 if capacity.is_zero() {
671 return Ok(zero());
672 }
673 let (_, views) = self
674 .board_views(&address(&token_in.address)?, &address(&token_out.address)?)
675 .map_err(pricing_error)?;
676 let amount = if trade_limit {
677 self.trade_limit_amount(&views, price, capacity)
678 } else {
679 self.target_price_amount(&views, price, tolerance, capacity)?
680 };
681 let amount = u256_to_biguint(amount);
682 if amount == BigUint::ZERO ||
683 min_amount_in
684 .as_ref()
685 .is_some_and(|min| amount < *min)
686 {
687 return Ok(zero());
688 }
689 let result = self.get_amount_out(amount.clone(), token_in, token_out)?;
690 Ok(PoolSwap::new(amount, result.amount, result.new_state, None))
691 }
692
693 fn clone_box(&self) -> Box<dyn ProtocolSim> {
694 Box::new(self.clone())
695 }
696
697 fn as_any(&self) -> &dyn Any {
698 self
699 }
700
701 fn as_any_mut(&mut self) -> &mut dyn Any {
702 self
703 }
704
705 fn eq(&self, other: &dyn ProtocolSim) -> bool {
706 other.as_any().downcast_ref::<Self>() == Some(self)
707 }
708
709 fn apply_block(&mut self, block: &BlockContext) -> bool {
712 let next = BlockEnvState { number: block.number(), timestamp: block.timestamp() };
713 if next == self.block {
714 return false;
715 }
716 self.block = next;
717 !self.boards.is_empty()
718 }
719}