Skip to main content

tycho_simulation/pamm/protocols/baibai/
state.rs

1use std::{any::Any, collections::HashMap};
2
3use alloy::primitives::{address, Address, U256};
4use num_bigint::BigUint;
5use serde::{Deserialize, Serialize};
6use tycho_common::{
7    dto::ProtocolStateDelta,
8    models::token::Token,
9    simulation::{
10        errors::{SimulationError, TransitionError},
11        protocol_sim::{Balances, GetAmountOutResult, PoolSwap, ProtocolSim, QueryPoolSwapParams},
12    },
13    Bytes,
14};
15
16use crate::{
17    book::{
18        component::PairState,
19        sim::{self, SwapDirection},
20    },
21    evm::protocol::{
22        u256_num::{biguint_to_u256, u256_to_biguint},
23        utils::solidity_math::mul_div,
24    },
25    pamm::protocols::baibai::math::{invalid, Curve, Side},
26};
27
28/// Gas of the executor's swap: a base cost, a cost per knot below the side's cursor after the swap
29/// (behind its previous fill or passed by this swap), and, buying base, a further cost per knot
30/// the swap itself passes. Measured cold on Base forks against WETH's five-knot sides: a base of
31/// 110,963 buying and 111,330 selling at block 53,234,728, which the Entrypoint upgrade at
32/// 53,492,231 raised by 3,379 both ways, to 114,342 and 114,709; the constant rounds the larger
33/// up, with a margin of about 700. Each knot passed adds 1,527 selling and 2,908 buying,
34/// unchanged by the upgrade: a knot below the cursor costs 1,550 (1,527 rounded up) and a knot
35/// bought through a further 1,360 (2,908 less 1,550, rounded up). Curves with more knots were not
36/// available to measure. The router's own transfers and approval are added on top by
37/// tycho-execution's gas estimator.
38const BASE_SWAP_GAS: u64 = 115_400;
39const GAS_PER_KNOT_BELOW_CURSOR: u64 = 1_550;
40const GAS_PER_KNOT_BOUGHT_THROUGH: u64 = 1_360;
41
42/// Gas a base token's own transfers inside the swap add over WETH's, selling base then buying it:
43/// cbBTC's go through its proxy. Measured at Base block 53,545,000 as the difference between
44/// entrypoint swaps of each base within its first segment, +17,079 selling and +15,352 buying,
45/// rounded up. A base not listed here, such as one served through
46/// [`BaibaiFeedBuilder::bases`](super::BaibaiFeedBuilder::bases), is priced as WETH.
47const BASE_TRANSFER_GAS: [(Address, u64, u64); 1] =
48    [(address!("cbB7C0000aB88B473b1f5aFd9ef808440eed33Bf"), 17_100, 15_400)];
49
50/// The entrypoint's fee denominator: fees are set in millionths of the gross output.
51const FEE_DENOMINATOR: u32 = 1_000_000;
52
53/// One BaiBai pair as the chain held it at one block: the curve's two sides, the custody each
54/// payout draws on, and the fee the entrypoint charges the taker the feed was built for.
55///
56/// Prices exact-input swaps wei for wei as `Entrypoint.quoteFor(base, tokenIn, amountIn, taker)`
57/// does at that block, except that it refuses inputs past a bid segment that exactly breaks even,
58/// which the contract fills (see `Curve::capacity`). It does not price the entrypoint's priority
59/// surcharge, up to 50 bps withheld from a swap sent with a priority fee above 0.002 gwei: see the
60/// module docs.
61#[derive(Clone, derive_more::Debug, PartialEq, Serialize, Deserialize)]
62pub struct BaibaiState {
63    pub(super) base_token: Token,
64    pub(super) quote_token: Token,
65    /// Quote atoms per 10^18 base atoms, before each side's spread.
66    pub(super) mid: U256,
67    pub(super) q_unit: U256,
68    pub(super) c_unit: U256,
69    #[debug("{{ filled: {}, {} knots }}", ask.filled, ask.knots.len())]
70    pub(super) ask: Side,
71    #[debug("{{ filled: {}, {} knots }}", bid.filled, bid.knots.len())]
72    pub(super) bid: Side,
73    /// What the custodian can pay out, base then quote: its balance less pending withdrawals.
74    pub(super) available: [U256; 2],
75    pub(super) fee_pips: u32,
76}
77
78impl BaibaiState {
79    /// Fails for a curve the contract would never store or a fee it would never charge.
80    pub(super) fn validated(self) -> Result<Self, SimulationError> {
81        if self.mid == U256::ZERO || self.q_unit == U256::ZERO || self.c_unit == U256::ZERO {
82            return Err(invalid("curve has no mid price or unit"));
83        }
84        self.kept_pips()?;
85        self.curve(SwapDirection::BaseToQuote)?;
86        self.curve(SwapDirection::QuoteToBase)?;
87        Ok(self)
88    }
89
90    /// The side a swap in `direction` walks: selling base fills the bid, buying it the ask.
91    fn curve(&self, direction: SwapDirection) -> Result<Curve, SimulationError> {
92        let (side, asks) = match direction {
93            SwapDirection::BaseToQuote => (&self.bid, false),
94            SwapDirection::QuoteToBase => (&self.ask, true),
95        };
96        Curve::new(side, self.mid, self.q_unit, self.c_unit, asks)
97    }
98
99    /// Indices into `available` of the token a swap in `direction` pays in and the one it pays
100    /// out.
101    fn custody(direction: SwapDirection) -> (usize, usize) {
102        match direction {
103            SwapDirection::BaseToQuote => (0, 1),
104            SwapDirection::QuoteToBase => (1, 0),
105        }
106    }
107
108    /// The millionths of the gross output the taker keeps. Fails for a fee of the whole output or
109    /// more, which the entrypoint never charges: [`Self::validated`] refuses it, and a
110    /// deserialized state, which has not been through it, fails every quote and price for it and
111    /// lists no direction.
112    fn kept_pips(&self) -> Result<u32, SimulationError> {
113        if self.fee_pips >= FEE_DENOMINATOR {
114            return Err(invalid(format!("fee of {} pips takes the whole output", self.fee_pips)));
115        }
116        Ok(FEE_DENOMINATOR - self.fee_pips)
117    }
118
119    /// The gross output less the entrypoint's fee, which the contract rounds up.
120    fn after_fee(&self, gross: U256) -> Result<U256, SimulationError> {
121        let kept = self.kept_pips()?;
122        mul_div(gross, U256::from(kept), U256::from(FEE_DENOMINATOR))
123    }
124
125    /// The executor's gas for a swap in `direction` that moves the side's cursor to `cursor`.
126    fn gas(&self, curve: &Curve, direction: SwapDirection, cursor: U256) -> u64 {
127        let below = curve.knots_below(cursor);
128        let bought_through = match direction {
129            SwapDirection::BaseToQuote => 0,
130            SwapDirection::QuoteToBase => below - curve.knots_below(curve.filled),
131        };
132        let transfers = BASE_TRANSFER_GAS
133            .iter()
134            .find(|(base, _, _)| self.base_token.address.as_ref() == base.as_slice())
135            .map_or(0, |(_, selling, buying)| match direction {
136                SwapDirection::BaseToQuote => *selling,
137                SwapDirection::QuoteToBase => *buying,
138            });
139        BASE_SWAP_GAS +
140            transfers +
141            GAS_PER_KNOT_BELOW_CURSOR * below +
142            GAS_PER_KNOT_BOUGHT_THROUGH * bought_through
143    }
144
145    fn sells(&self, direction: SwapDirection) -> bool {
146        let (_, out) = Self::custody(direction);
147        self.kept_pips().is_ok() &&
148            self.available[out] > U256::ZERO &&
149            self.curve(direction)
150                .and_then(|curve| curve.capacity())
151                .is_ok_and(|capacity| capacity > U256::ZERO)
152    }
153}
154
155impl PairState for BaibaiState {
156    fn base_token(&self) -> &Token {
157        &self.base_token
158    }
159
160    fn quote_token(&self) -> &Token {
161        &self.quote_token
162    }
163
164    fn directions(&self) -> Vec<(Bytes, Bytes)> {
165        sim::directions(
166            &self.base_token,
167            &self.quote_token,
168            self.sells(SwapDirection::BaseToQuote),
169            self.sells(SwapDirection::QuoteToBase),
170        )
171    }
172}
173
174#[typetag::serde]
175impl ProtocolSim for BaibaiState {
176    fn fee(&self) -> f64 {
177        f64::from(self.fee_pips) / f64::from(FEE_DENOMINATOR)
178    }
179
180    /// The marginal rate of selling `base` for `quote`, fee included.
181    fn spot_price(&self, base: &Token, quote: &Token) -> Result<f64, SimulationError> {
182        let direction = SwapDirection::require(
183            &self.base_token,
184            &self.quote_token,
185            &base.address,
186            &quote.address,
187        )?;
188        let (_, out) = Self::custody(direction);
189        if self.available[out] == U256::ZERO {
190            return Err(invalid("no custody to pay out"));
191        }
192        let atomic = self
193            .curve(direction)?
194            .marginal_price()?;
195        let decimals = 10f64.powf(f64::from(base.decimals) - f64::from(quote.decimals));
196        let kept = f64::from(self.kept_pips()?) / f64::from(FEE_DENOMINATOR);
197        Ok(atomic * decimals * kept)
198    }
199
200    fn get_amount_out(
201        &self,
202        amount_in: BigUint,
203        token_in: &Token,
204        token_out: &Token,
205    ) -> Result<GetAmountOutResult, SimulationError> {
206        sim::require_positive_amount(&amount_in)?;
207        let direction = SwapDirection::require(
208            &self.base_token,
209            &self.quote_token,
210            &token_in.address,
211            &token_out.address,
212        )?;
213        if amount_in.bits() > 256 {
214            return Err(invalid("amount exceeds uint256"));
215        }
216        let input = biguint_to_u256(&amount_in);
217        let curve = self.curve(direction)?;
218        let (gross, cursor) = curve.quote(input)?;
219        let output = self.after_fee(gross)?;
220        if output == U256::ZERO {
221            return Err(invalid("input below the curve's atomic precision"));
222        }
223        let (paid_in, paid_out) = Self::custody(direction);
224        if output > self.available[paid_out] {
225            return Err(invalid(format!(
226                "output {output} exceeds the custodian's available {}",
227                self.available[paid_out]
228            )));
229        }
230        let mut next = self.clone();
231        match direction {
232            SwapDirection::BaseToQuote => next.bid.filled = cursor,
233            SwapDirection::QuoteToBase => next.ask.filled = cursor,
234        }
235        next.available[paid_in] = next.available[paid_in].saturating_add(input);
236        next.available[paid_out] -= output;
237        Ok(GetAmountOutResult::new(
238            u256_to_biguint(output),
239            BigUint::from(self.gas(&curve, direction, cursor)),
240            Box::new(next),
241        ))
242    }
243
244    /// The largest input the curve fills and custody pays out, and its output. Zero both ways
245    /// when nothing can be swapped in that direction.
246    fn get_limits(
247        &self,
248        sell_token: Bytes,
249        buy_token: Bytes,
250    ) -> Result<(BigUint, BigUint), SimulationError> {
251        let direction =
252            SwapDirection::require(&self.base_token, &self.quote_token, &sell_token, &buy_token)?;
253        let (paid_in, paid_out) = Self::custody(direction);
254        let available = self.available[paid_out];
255        if available == U256::ZERO {
256            return Ok((BigUint::ZERO, BigUint::ZERO));
257        }
258        let curve = self.curve(direction)?;
259        let mut high = curve
260            .capacity()?
261            .min(U256::MAX - self.available[paid_in]);
262        let full_output = self.after_fee(curve.quote(high)?.0)?;
263        if full_output == U256::ZERO {
264            return Ok((BigUint::ZERO, BigUint::ZERO));
265        }
266        if self.after_fee(curve.output_bound(high)?)? <= available {
267            return Ok((u256_to_biguint(high), u256_to_biguint(full_output)));
268        }
269        // Custody binds before the curve does: find the largest input whose output it covers.
270        let mut low = U256::ZERO;
271        while low < high {
272            let mid = low + (high - low).div_ceil(U256::from(2));
273            if self.after_fee(curve.output_bound(mid)?)? <= available {
274                low = mid;
275            } else {
276                high = mid - U256::from(1);
277            }
278        }
279        let output = self.after_fee(curve.quote(low)?.0)?;
280        if output == U256::ZERO {
281            return Ok((BigUint::ZERO, BigUint::ZERO));
282        }
283        Ok((u256_to_biguint(low), u256_to_biguint(output)))
284    }
285
286    fn delta_transition(
287        &mut self,
288        _delta: ProtocolStateDelta,
289        _tokens: &HashMap<Bytes, Token>,
290        _balances: &Balances,
291    ) -> Result<(), TransitionError> {
292        Err(TransitionError::DecodeError(
293            "BaiBai state is read whole every poll and does not take deltas".into(),
294        ))
295    }
296
297    fn query_pool_swap(&self, params: &QueryPoolSwapParams) -> Result<PoolSwap, SimulationError> {
298        crate::evm::query_pool_swap::query_pool_swap(self, params)
299    }
300
301    fn clone_box(&self) -> Box<dyn ProtocolSim> {
302        Box::new(self.clone())
303    }
304
305    fn as_any(&self) -> &dyn Any {
306        self
307    }
308
309    fn as_any_mut(&mut self) -> &mut dyn Any {
310        self
311    }
312
313    fn eq(&self, other: &dyn ProtocolSim) -> bool {
314        other.as_any().downcast_ref::<Self>() == Some(self)
315    }
316}
317
318#[cfg(test)]
319mod tests {
320    use rstest::rstest;
321
322    use super::*;
323    use crate::pamm::protocols::baibai::{
324        math::Knot,
325        test_support::{fee_charging_fixture, fixture, fixtures, state, token, weth_state},
326        BASE_DEPLOYMENT,
327    };
328
329    fn quote() -> Token {
330        token(BASE_DEPLOYMENT.quote)
331    }
332
333    /// Every recorded `quoteFor` for Tycho's router, both pairs and both directions, at blocks
334    /// before and after the router's whitelist and the Entrypoint upgrade, with every cursor at
335    /// zero, the ask partly filled and the bid partly filled, priced wei for wei, including the
336    /// sizes the entrypoint refused (recorded as zero output).
337    #[test]
338    fn quotes_match_the_entrypoint_wei_for_wei() {
339        let mut priced = 0;
340        for fixture in fixtures() {
341            for pair in &fixture.pairs {
342                let state = state(&fixture, pair);
343                for case in &pair.cases {
344                    let (token_in, token_out) = if case.sell_base {
345                        (state.base_token.clone(), quote())
346                    } else {
347                        (quote(), state.base_token.clone())
348                    };
349                    let amount_in = u256_to_biguint(case.amount_in);
350                    match state.get_amount_out(amount_in, &token_in, &token_out) {
351                        Ok(result) => {
352                            assert_eq!(result.amount, u256_to_biguint(case.amount_out), "{case:?}");
353                            priced += 1;
354                        }
355                        Err(error) => {
356                            assert_eq!(case.amount_out, U256::ZERO, "{case:?}: {error}")
357                        }
358                    }
359                }
360            }
361        }
362        assert_eq!(priced, 116, "the recordings' fillable cases");
363    }
364
365    /// The curve itself, without the fee, matches `CurveBook.quote` at every recorded block.
366    #[test]
367    fn a_feeless_state_matches_the_curve_book() {
368        for fixture in fixtures() {
369            for pair in &fixture.pairs {
370                let mut state = state(&fixture, pair);
371                state.fee_pips = 0;
372                for case in pair
373                    .cases
374                    .iter()
375                    .filter(|case| case.curve_out != U256::ZERO)
376                {
377                    let (token_in, token_out) = if case.sell_base {
378                        (state.base_token.clone(), quote())
379                    } else {
380                        (quote(), state.base_token.clone())
381                    };
382                    let result = state
383                        .get_amount_out(u256_to_biguint(case.amount_in), &token_in, &token_out)
384                        .unwrap();
385                    assert_eq!(result.amount, u256_to_biguint(case.curve_out), "{case:?}");
386                }
387            }
388        }
389    }
390
391    /// The 53,234,728 recording's router fee, 50 millionths, before the whitelist.
392    #[test]
393    fn the_fee_is_in_millionths_of_the_output() {
394        let fixture = fee_charging_fixture();
395
396        assert_eq!(state(&fixture, &fixture.pairs[0]).fee(), 0.00005);
397    }
398
399    /// Since the router's whitelist, it is charged nothing: selling 1 WETH at block 53,545,000
400    /// fetched exactly what `quoteFor` returned for the router there.
401    #[test]
402    fn the_router_pays_no_fee_since_its_whitelist() {
403        let state = weth_state();
404
405        let result = state
406            .get_amount_out(BigUint::from(10u64).pow(18), &state.base_token.clone(), &quote())
407            .unwrap();
408
409        assert_eq!(state.fee(), 0.0);
410        assert_eq!(result.amount, BigUint::from(2_416_825_836u64));
411    }
412
413    #[test]
414    fn a_swap_advances_the_cursor_and_moves_custody() {
415        let state = weth_state();
416        let weth = state.base_token.clone();
417        let amount = BigUint::from(10u64).pow(17);
418
419        let result = state
420            .get_amount_out(amount.clone(), &weth, &quote())
421            .unwrap();
422
423        let next = result
424            .new_state
425            .as_any()
426            .downcast_ref::<BaibaiState>()
427            .unwrap();
428        assert_eq!(next.bid.filled, U256::from(10u64).pow(U256::from(17)));
429        assert_eq!(next.ask.filled, state.ask.filled);
430        assert_eq!(
431            u256_to_biguint(next.available[0]),
432            u256_to_biguint(state.available[0]) + amount
433        );
434        assert_eq!(
435            u256_to_biguint(next.available[1]),
436            u256_to_biguint(state.available[1]) - &result.amount
437        );
438        // The same size again walks further along the bid and pays no more.
439        let again = next
440            .get_amount_out(BigUint::from(10u64).pow(17), &weth, &quote())
441            .unwrap();
442        assert!(again.amount <= result.amount);
443    }
444
445    /// A swap costs a base amount plus a share per knot it walks past, and more per knot buying
446    /// base. The 53,545,000 recording's WETH sides have five knots, the first three at about 0.41,
447    /// 1.03 and 3.10 WETH; the fork at 53,234,728 measured 1,527 more gas per knot selling 2 WETH
448    /// (two knots) than 0.2 WETH (none), and 2,908 more buying with 1,000 USDC (one knot, just:
449    /// it buys 0.4137086 WETH against a knot at 0.4137) than with 500.
450    #[rstest]
451    #[case::selling_within_the_first_segment(true, 2u64 * 10u64.pow(17), 115_400)]
452    #[case::selling_past_two_knots(true, 2u64 * 10u64.pow(18), 118_500)]
453    #[case::buying_within_the_first_segment(false, 500_000_000, 115_400)]
454    #[case::buying_past_one_knot(false, 1_000_000_000, 118_310)]
455    fn gas_grows_with_the_knots_a_swap_passes(
456        #[case] sell_base: bool,
457        #[case] amount: u64,
458        #[case] expected: u64,
459    ) {
460        let state = weth_state();
461        let (token_in, token_out) = if sell_base {
462            (state.base_token.clone(), quote())
463        } else {
464            (quote(), state.base_token.clone())
465        };
466
467        let gas = state
468            .get_amount_out(BigUint::from(amount), &token_in, &token_out)
469            .unwrap()
470            .gas;
471
472        assert_eq!(gas, BigUint::from(expected));
473    }
474
475    /// cbBTC's own transfers cost more than WETH's, each way, on top of the same curve walk.
476    #[rstest]
477    #[case::selling(true, 1_000_000, 115_400 + 17_100)]
478    #[case::buying(false, 500_000_000, 115_400 + 15_400)]
479    fn cbbtc_swaps_add_its_transfer_gas(
480        #[case] sell_base: bool,
481        #[case] amount: u64,
482        #[case] expected: u64,
483    ) {
484        let fixture = fixture();
485        let state = state(&fixture, &fixture.pairs[1]);
486        assert_eq!(state.base_token.symbol, "cbBTC");
487        let (token_in, token_out) = if sell_base {
488            (state.base_token.clone(), quote())
489        } else {
490            (quote(), state.base_token.clone())
491        };
492
493        let gas = state
494            .get_amount_out(BigUint::from(amount), &token_in, &token_out)
495            .unwrap()
496            .gas;
497
498        assert_eq!(gas, BigUint::from(expected));
499    }
500
501    /// A knot behind the side's previous fill still costs its share, but no longer the extra a
502    /// buy pays for walking through it.
503    #[test]
504    fn knots_behind_the_cursor_still_cost_gas() {
505        let mut state = weth_state();
506        state.ask.filled = U256::from(5u64) * U256::from(10u64).pow(U256::from(17));
507
508        let gas = state
509            .get_amount_out(BigUint::from(1_000_000u64), &quote(), &state.base_token.clone())
510            .unwrap()
511            .gas;
512
513        assert_eq!(gas, BigUint::from(115_400u64 + 1_550));
514    }
515
516    /// Past a bid segment that loses money the contract reverts; the state refuses the same
517    /// inputs, and `get_limits` stops before them.
518    #[test]
519    fn a_bid_past_its_paying_depth_is_refused() {
520        let mut state = weth_state();
521        state.bid.knots = vec![Knot { q: 1_000, extra: 0 }, Knot { q: 2_000, extra: 46_000_000 }];
522        let weth = state.base_token.clone();
523
524        let (max_in, max_out) = state
525            .get_limits(weth.address.clone(), quote().address)
526            .unwrap();
527
528        let at_limit = state
529            .get_amount_out(max_in.clone(), &weth, &quote())
530            .unwrap();
531        assert_eq!(at_limit.amount, max_out);
532        let error = state
533            .get_amount_out(max_in + 1u32, &weth, &quote())
534            .unwrap_err();
535        assert!(
536            error
537                .to_string()
538                .contains("paying depth"),
539            "{error}"
540        );
541    }
542
543    /// A state deserialized from elsewhere has not been validated. A fee of the whole output or
544    /// more fails its quotes and prices alike, and it lists no direction to trade.
545    #[rstest]
546    #[case::the_whole_output(1_000_000)]
547    #[case::more_than_the_output(1_000_001)]
548    fn a_fee_of_the_whole_output_trades_nothing(#[case] fee_pips: u32) {
549        let mut state = weth_state();
550        state.fee_pips = fee_pips;
551        let weth = state.base_token.clone();
552
553        let quoted = state
554            .get_amount_out(BigUint::from(10u64).pow(16), &weth, &quote())
555            .unwrap_err();
556        let priced = state
557            .spot_price(&weth, &quote())
558            .unwrap_err();
559
560        for error in [quoted, priced] {
561            assert!(
562                error
563                    .to_string()
564                    .contains("takes the whole output"),
565                "{error}"
566            );
567        }
568        assert!(state.directions().is_empty());
569        assert!(state.validated().is_err());
570    }
571
572    #[test]
573    fn output_beyond_custody_is_refused() {
574        let mut state = weth_state();
575        state.available[1] = U256::from(1_000_000);
576
577        let error = state
578            .get_amount_out(BigUint::from(10u64).pow(17), &state.base_token.clone(), &quote())
579            .unwrap_err();
580
581        assert!(error.to_string().contains("available"), "{error}");
582    }
583
584    #[rstest]
585    #[case::zero_amount(0u64, true)]
586    #[case::unrelated_tokens(1_000u64, false)]
587    fn invalid_requests_are_refused(#[case] amount: u64, #[case] own_tokens: bool) {
588        let state = weth_state();
589        let token_in = if own_tokens {
590            state.base_token.clone()
591        } else {
592            token(alloy::primitives::Address::repeat_byte(0x11))
593        };
594
595        let error = state
596            .get_amount_out(BigUint::from(amount), &token_in, &quote())
597            .unwrap_err();
598
599        assert!(matches!(error, SimulationError::InvalidInput(..)), "{error}");
600    }
601
602    /// The limits are a swap the state fills, and the next atom past a curve-bound limit is not.
603    #[rstest]
604    #[case::sell_base(true)]
605    #[case::buy_base(false)]
606    fn the_limits_are_fillable_and_tight(#[case] sell_base: bool) {
607        let state = weth_state();
608        let (token_in, token_out) = if sell_base {
609            (state.base_token.clone(), quote())
610        } else {
611            (quote(), state.base_token.clone())
612        };
613
614        let (max_in, max_out) = state
615            .get_limits(token_in.address.clone(), token_out.address.clone())
616            .unwrap();
617
618        let at_limit = state
619            .get_amount_out(max_in.clone(), &token_in, &token_out)
620            .unwrap();
621        assert_eq!(at_limit.amount, max_out);
622        assert!(state
623            .get_amount_out(max_in + 1u32, &token_in, &token_out)
624            .is_err());
625    }
626
627    /// The base the bid buys before it stops paying, derived from the side's parameters rather
628    /// than [`Curve::capacity`]: up to its depth, and short of the first segment past its cursor
629    /// whose extra cost takes all the spread-adjusted mid pays for it.
630    fn bid_paying_depth(state: &BaibaiState) -> U256 {
631        let side = &state.bid;
632        let wad = U256::from(10u64).pow(U256::from(18));
633        let bps = U256::from(10_000u64);
634        let scale = U256::from(u64::try_from(10_000 + i64::from(side.spread_bps)).unwrap());
635        let price = state.mid * scale / bps;
636        let last_q = side
637            .knots
638            .last()
639            .map_or(U256::ZERO, |knot| U256::from(knot.q) * state.q_unit);
640        let depth = last_q * U256::from(side.depth_bps) / bps;
641        let mut reach = side.filled;
642        let (mut prev_q, mut prev_c) = (U256::ZERO, U256::ZERO);
643        for knot in &side.knots {
644            let q = U256::from(knot.q) * state.q_unit;
645            let c = U256::from(knot.extra) * state.c_unit;
646            if q > side.filled && reach < depth {
647                if price * (q - prev_q) <= (c - prev_c) * wad {
648                    break;
649                }
650                reach = q.min(depth);
651            }
652            (prev_q, prev_c) = (q, c);
653        }
654        reach.saturating_sub(side.filled)
655    }
656
657    /// Checks that `state`'s limits in `direction` are a swap it fills at their stated output and
658    /// that one atom more is refused with `refusal`, or, when `flat_allowed`, pays no more than
659    /// the limit. Returns the limits.
660    fn assert_tight_limits(
661        state: &BaibaiState,
662        direction: SwapDirection,
663        refusal: &str,
664        flat_allowed: bool,
665        context: &str,
666    ) -> (BigUint, BigUint) {
667        let (token_in, token_out) = match direction {
668            SwapDirection::BaseToQuote => (state.base_token.clone(), quote()),
669            SwapDirection::QuoteToBase => (quote(), state.base_token.clone()),
670        };
671        let (max_in, max_out) = state
672            .get_limits(token_in.address.clone(), token_out.address.clone())
673            .unwrap();
674        if max_in == BigUint::ZERO {
675            return (max_in, max_out);
676        }
677        let at_limit = state
678            .get_amount_out(max_in.clone(), &token_in, &token_out)
679            .unwrap_or_else(|e| panic!("{context}: the limit {max_in} is refused: {e}"));
680        assert_eq!(at_limit.amount, max_out, "{context}");
681        match state.get_amount_out(max_in.clone() + 1u32, &token_in, &token_out) {
682            Err(error) => assert!(error.to_string().contains(refusal), "{context}: {error}"),
683            Ok(past) => assert!(
684                flat_allowed && past.amount == max_out,
685                "{context}: one atom past the limit {max_in} pays {}",
686                past.amount
687            ),
688        }
689        (max_in, max_out)
690    }
691
692    /// The limits hold beyond a trivial state: on every recorded pair, including partly filled
693    /// sides, as recorded and with a fee, a spread or half the depth, in both directions.
694    /// - With the custody as recorded, the curve binds: the bid's limit is the depth that still
695    ///   pays, derived without [`Curve::capacity`], and one atom past either limit is refused as
696    ///   beyond the curve.
697    /// - With half the curve's output in custody, custody binds: the limit's output fits it, and
698    ///   one atom more is refused as exceeding it or pays no more. The second happens on WETH's
699    ///   bid, where many wei buy the same USDC atom and [`Curve::output_bound`], one atom above the
700    ///   exact output there, stops the search short of the last such wei.
701    #[rstest]
702    #[case::as_recorded(|_: &mut BaibaiState| {})]
703    #[case::with_a_fee(|s: &mut BaibaiState| s.fee_pips = 1_000)]
704    #[case::with_spreads(|s: &mut BaibaiState| {
705        s.ask.spread_bps = 25;
706        s.bid.spread_bps = -25;
707    })]
708    #[case::at_half_depth(|s: &mut BaibaiState| {
709        s.ask.depth_bps = 5_000;
710        s.bid.depth_bps = 5_000;
711    })]
712    fn the_limits_hold_on_every_recording(#[case] vary: fn(&mut BaibaiState)) {
713        let (mut curve_bound, mut custody_bound) = (0, 0);
714        for fixture in fixtures() {
715            for pair in &fixture.pairs {
716                let mut state = state(&fixture, pair);
717                vary(&mut state);
718                let state = state.validated().unwrap();
719                for (direction, beyond_curve) in [
720                    (SwapDirection::BaseToQuote, "beyond the bid's paying depth"),
721                    (SwapDirection::QuoteToBase, "beyond ask depth"),
722                ] {
723                    let context = format!("{direction:?} at block {}", fixture.block);
724                    let (max_in, max_out) =
725                        assert_tight_limits(&state, direction, beyond_curve, false, &context);
726                    if direction == SwapDirection::BaseToQuote {
727                        assert_eq!(biguint_to_u256(&max_in), bid_paying_depth(&state), "{context}");
728                    }
729                    if max_out < BigUint::from(2u32) {
730                        continue;
731                    }
732                    curve_bound += 1;
733
734                    let mut short = state.clone();
735                    let available = biguint_to_u256(&max_out) / U256::from(2);
736                    short.available[BaibaiState::custody(direction).1] = available;
737                    let (short_in, short_out) = assert_tight_limits(
738                        &short,
739                        direction,
740                        "exceeds the custodian's",
741                        true,
742                        &context,
743                    );
744                    assert!(short_out <= u256_to_biguint(available), "{context}");
745                    assert!(short_in < max_in, "{context}");
746                    custody_bound += 1;
747                }
748            }
749        }
750        assert!(curve_bound > 0, "no limit was bound by the curve");
751        assert!(custody_bound > 0, "no limit was bound by custody");
752    }
753
754    #[test]
755    fn an_empty_custody_trades_neither_way() {
756        let mut state = weth_state();
757        state.available = [U256::ZERO, U256::ZERO];
758
759        assert!(state.directions().is_empty());
760        let limits = state
761            .get_limits(state.base_token.address.clone(), quote().address)
762            .unwrap();
763        assert_eq!(limits, (BigUint::ZERO, BigUint::ZERO));
764        assert!(state
765            .spot_price(&state.base_token.clone(), &quote())
766            .is_err());
767    }
768
769    /// Selling base pays the bid, buying it costs the ask: the two spot prices bracket the mid.
770    #[test]
771    fn spot_prices_bracket_the_mid() {
772        let state = weth_state();
773        let weth = state.base_token.clone();
774        let mid = 2_417.07;
775
776        let bid = state
777            .spot_price(&weth, &quote())
778            .unwrap();
779        let ask = 1.0 /
780            state
781                .spot_price(&quote(), &weth)
782                .unwrap();
783
784        assert!(bid < ask, "bid {bid} ask {ask}");
785        assert!((bid - mid).abs() / mid < 0.01, "bid {bid}");
786        assert!((ask - mid).abs() / mid < 0.01, "ask {ask}");
787    }
788
789    #[rstest]
790    #[case::fee_takes_everything(|s: &mut BaibaiState| s.fee_pips = 1_000_000)]
791    #[case::no_mid(|s: &mut BaibaiState| s.mid = U256::ZERO)]
792    #[case::too_many_knots(|s: &mut BaibaiState| s.ask.knots = (1..=37).map(|i| Knot { q: i, extra: i }).collect())]
793    #[case::falling_cost(|s: &mut BaibaiState| s.bid.knots = vec![Knot { q: 1, extra: 5 }, Knot { q: 2, extra: 4 }])]
794    #[case::repeated_quantity(|s: &mut BaibaiState| s.bid.knots = vec![Knot { q: 1, extra: 0 }, Knot { q: 1, extra: 1 }])]
795    #[case::depth_over_100_percent(|s: &mut BaibaiState| s.ask.depth_bps = 10_001)]
796    #[case::spread_of_minus_100_percent(|s: &mut BaibaiState| s.bid.spread_bps = -10_000)]
797    #[case::spread_below_minus_100_percent(|s: &mut BaibaiState| s.ask.spread_bps = i16::MIN)]
798    fn malformed_states_are_rejected(#[case] corrupt: fn(&mut BaibaiState)) {
799        let mut state = weth_state();
800        corrupt(&mut state);
801
802        assert!(state.validated().is_err());
803    }
804
805    #[test]
806    fn a_state_round_trips_through_serde() {
807        let state: Box<dyn ProtocolSim> = Box::new(weth_state());
808
809        let json = serde_json::to_string(&state).unwrap();
810        let back: Box<dyn ProtocolSim> = serde_json::from_str(&json).unwrap();
811
812        assert!(back.eq(state.as_ref()));
813    }
814}