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