penumbra_sdk_dex/component/router/
path.rs

1use anyhow::Result;
2
3use cnidarium::{StateDelta, StateRead};
4use penumbra_sdk_asset::asset;
5use penumbra_sdk_num::fixpoint::U128x128;
6use std::cmp::Ordering;
7use tracing::Instrument;
8
9use crate::{component::PositionRead, DirectedTradingPair};
10
11/// A path is an ordered sequence of assets, implicitly defining a trading pair,
12/// and a price for trading along that path. It contains a forked view of the
13/// state after traveling along the path.
14///
15/// # Ordering
16/// The ordering of paths is based on their effective price estimate first,
17/// then their length, then their start asset, and finally their intermediary
18/// assets.
19pub(super) struct Path<S: StateRead + 'static> {
20    /// The start point of the path
21    pub start: asset::Id,
22    /// The nodes along the path, implicitly defining the end
23    pub nodes: Vec<asset::Id>,
24    /// An estimate of the end-to-end effective price along the path
25    pub price: U128x128,
26    /// A forked view of the state after traveling along this path.
27    pub state: StateDelta<S>,
28    /// A span recording information about the path, for debugging.
29    pub span: tracing::Span,
30}
31
32impl<S: StateRead + 'static> Path<S> {
33    pub fn end(&self) -> &asset::Id {
34        self.nodes.last().unwrap_or(&self.start)
35    }
36
37    pub fn begin(start: asset::Id, state: StateDelta<S>) -> Self {
38        let span = tracing::debug_span!("path", start = ?start);
39        span.in_scope(|| tracing::debug!("beginning path"));
40        Self {
41            start,
42            nodes: Vec::new(),
43            price: 1u64.into(),
44            state,
45            span,
46        }
47    }
48
49    // We can't clone, because StateDelta only has an explicit fork() on purpose
50    pub fn fork(&mut self) -> Self {
51        Self {
52            start: self.start,
53            nodes: self.nodes.clone(),
54            price: self.price,
55            state: self.state.fork(),
56            span: self.span.clone(),
57        }
58    }
59
60    // Making this consuming forces callers to explicitly fork the path first.
61    pub async fn extend_to(self, new_end: asset::Id) -> Result<Option<Path<S>>> {
62        let span = tracing::debug_span!(parent: &self.span, "extend_to", new_end = ?new_end);
63        // Passing to an inner function lets us control the span more precisely than if
64        // we used the #[instrument] macro (which does something similar to this internally).
65        self.extend_to_inner(new_end).instrument(span).await
66    }
67
68    async fn extend_to_inner(mut self, new_end: asset::Id) -> Result<Option<Path<S>>> {
69        let target_pair = DirectedTradingPair::new(*self.end(), new_end);
70        // Pulls the (id, position) that have the best effective price for this hop.
71        let Some((best_price_lp_id, best_price_lp)) =
72            self.state.best_position(&target_pair).await?
73        else {
74            tracing::trace!("no best position, failing to extend path");
75            return Ok(None);
76        };
77        // Deindex the position we "consumed" in this and all descendant state forks,
78        // ensuring we don't double-count liquidity while traversing cycles.
79        use crate::component::position_manager::price_index::PositionByPriceIndex;
80        self.state
81            .deindex_position_by_price(&best_price_lp, &best_price_lp_id);
82
83        // Compute the effective price of a trade in the direction self.end()=>new_end
84        let hop_price = best_price_lp
85            .phi
86            .orient_end(new_end)
87            .expect("position should be contain the end asset")
88            .effective_price();
89
90        match self.price * hop_price {
91            Ok(path_price) => {
92                // Update and return the path.
93                tracing::debug!(%path_price, %hop_price, ?best_price_lp_id, "extended path");
94                self.price = path_price;
95                self.nodes.push(new_end);
96                // Create a new span for the extension.  Note: this is a child of
97                // the path span (:path:via:via:via etc), not a child of the current
98                // span (:path:via:via:extend_to).
99                self.span = tracing::debug_span!(parent: &self.span, "via", id = ?new_end);
100                Ok(Some(self))
101            }
102            Err(e) => {
103                // If there was an overflow estimating the effective price, we failed
104                // to extend the path.
105                tracing::debug!(?e, "failed to extend path due to overflow");
106                Ok(None)
107            }
108        }
109    }
110}
111
112impl<S: StateRead + 'static> PartialEq for Path<S> {
113    fn eq(&self, other: &Self) -> bool {
114        self.start == other.start && self.price == other.price && self.nodes == other.nodes
115    }
116}
117
118impl<S: StateRead + 'static> PartialOrd for Path<S> {
119    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
120        Some(self.cmp(other))
121    }
122}
123
124impl<S: StateRead + 'static> Eq for Path<S> {}
125
126impl<S: StateRead + 'static> Ord for Path<S> {
127    fn cmp(&self, other: &Self) -> Ordering {
128        self.price.cmp(&other.price).then_with(|| {
129            self.nodes.len().cmp(&other.nodes.len()).then_with(|| {
130                self.start
131                    .cmp(&other.start)
132                    .then_with(|| self.nodes.cmp(&other.nodes))
133            })
134        })
135    }
136}
penumbra_sdk_dex/component/router/path.rs

penumbra_sdk_dex/component/router/
path.rs
