penumbra_sdk_dex/component/router/
path_cache.rs

1use std::{collections::BTreeMap, sync::Arc};
2
3use cnidarium::{StateDelta, StateRead};
4use parking_lot::Mutex;
5use penumbra_sdk_asset::asset;
6
7use super::Path;
8
9/// An entry in the path cache, representing a best known sub-path.
10pub(super) struct PathEntry<S: StateRead + 'static> {
11    /// The best known path to the intermediate asset.
12    pub path: Path<S>,
13    /// Whether the path is active, used to implement the SPFA optimization.
14    /// Newly extended paths are active.  By deactivating paths if all of their
15    /// possible extensions are suboptimal, we can avoid re-extending them in
16    /// each iteration.
17    pub active: bool,
18    /// The second best known path to the intermediate asset, used to record spill prices.
19    pub spill: Option<Path<S>>,
20}
21
22impl<S: StateRead + 'static> PathEntry<S> {
23    /// Update the best path or spill price if the new path is better, otherwise do nothing.
24    pub fn update(&mut self, new_path: Path<S>) {
25        if new_path < self.path {
26            tracing::debug!(new_price = %new_path.price, old_price = %self.path.price, "new path is better than best path, updating cache");
27            self.spill = Some(std::mem::replace(&mut self.path, new_path));
28            self.active = true;
29        } else {
30            // The new path is worse than the best path, but it might be better than the spill path.
31            self.update_spill(new_path);
32        }
33    }
34
35    /// Update the spill price if the new path is better, or if the spill price has not
36    /// been set yet. Otherwise do nothing.
37    fn update_spill(&mut self, new_path: Path<S>) {
38        match &self.spill {
39            Some(spill) if new_path.price < spill.price => {
40                tracing::debug!(new_spill_price = %new_path.price, old_spill_price = %spill.price, "new path is better than spill path, updating cache");
41                self.spill = Some(new_path);
42            }
43            Some(spill) => {
44                tracing::debug!(new_spill_price = %new_path.price, old_spill_price = %spill.price, "new path is worse than spill path, ignore");
45            }
46            None => {
47                tracing::debug!(new_spill_price = %new_path.price, "new path is a suitable spill path, updating cache");
48                self.spill = Some(new_path);
49            }
50        }
51    }
52}
53
54impl<S: StateRead + 'static> From<Path<S>> for PathEntry<S> {
55    fn from(path: Path<S>) -> Self {
56        Self {
57            path,
58            active: true,
59            spill: None,
60        }
61    }
62}
63
64pub(super) struct PathCache<S: StateRead + 'static>(pub(super) BTreeMap<asset::Id, PathEntry<S>>);
65pub(super) type SharedPathCache<S> = Arc<Mutex<PathCache<S>>>;
66
67impl<S: StateRead + 'static> PathCache<S> {
68    /// Initializes a new PathCache with the identity path for the start asset.
69    pub fn begin(start: asset::Id, state: StateDelta<S>) -> SharedPathCache<S> {
70        let mut cache = BTreeMap::new();
71        cache.insert(
72            start,
73            PathEntry {
74                path: Path::begin(start, state),
75                active: true,
76                spill: None,
77            },
78        );
79        Arc::new(Mutex::new(Self(cache)))
80    }
81
82    /// Consider a new candidate path, updating if it's better than an existing one.
83    pub fn consider(&mut self, path: Path<S>) {
84        // We can't use the entry combinators because avoiding cloning requires
85        // establishing that we'll only do one of the two operations.
86        use std::collections::btree_map::Entry;
87        let span = path.span.clone();
88        span.in_scope(|| match self.0.entry(*path.end()) {
89            Entry::Occupied(mut entry) => {
90                entry.get_mut().update(path);
91            }
92            Entry::Vacant(entry) => {
93                tracing::debug!("inserting new path");
94                entry.insert(path.into());
95            }
96        })
97    }
98
99    /// Extract all active paths, marking their existing entries as inactive.
100    pub fn extract_active(&mut self) -> Vec<Path<S>> {
101        self.0
102            .iter_mut()
103            .filter_map(|(_, entry)| {
104                if entry.active {
105                    entry.active = false;
106                    Some(entry.path.fork())
107                } else {
108                    None
109                }
110            })
111            .collect()
112    }
113}
penumbra_sdk_dex/component/router/path_cache.rs

penumbra_sdk_dex/component/router/
path_cache.rs
