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                self.active = true;
43            }
44            Some(spill) => {
45                tracing::debug!(new_spill_price = %new_path.price, old_spill_price = %spill.price, "new path is worse than spill path, ignore");
46            }
47            None => {
48                tracing::debug!(new_spill_price = %new_path.price, "new path is a suitable spill path, updating cache");
49                self.spill = Some(new_path);
50                self.active = true;
51            }
52        }
53    }
54}
55
56impl<S: StateRead + 'static> From<Path<S>> for PathEntry<S> {
57    fn from(path: Path<S>) -> Self {
58        Self {
59            path,
60            active: true,
61            spill: None,
62        }
63    }
64}
65
66pub(super) struct PathCache<S: StateRead + 'static>(pub(super) BTreeMap<asset::Id, PathEntry<S>>);
67pub(super) type SharedPathCache<S> = Arc<Mutex<PathCache<S>>>;
68
69impl<S: StateRead + 'static> PathCache<S> {
70    /// Initializes a new PathCache with the identity path for the start asset.
71    pub fn begin(start: asset::Id, state: StateDelta<S>) -> SharedPathCache<S> {
72        let mut cache = BTreeMap::new();
73        cache.insert(
74            start,
75            PathEntry {
76                path: Path::begin(start, state),
77                active: true,
78                spill: None,
79            },
80        );
81        Arc::new(Mutex::new(Self(cache)))
82    }
83
84    /// Consider a new candidate path, updating if it's better than an existing one.
85    pub fn consider(&mut self, path: Path<S>) {
86        // We can't use the entry combinators because avoiding cloning requires
87        // establishing that we'll only do one of the two operations.
88        use std::collections::btree_map::Entry;
89        let span = path.span.clone();
90        span.in_scope(|| match self.0.entry(*path.end()) {
91            Entry::Occupied(mut entry) => {
92                entry.get_mut().update(path);
93            }
94            Entry::Vacant(entry) => {
95                tracing::debug!("inserting new path");
96                entry.insert(path.into());
97            }
98        })
99    }
100
101    /// Extract all active paths, marking their existing entries as inactive.
102    pub fn extract_active(&mut self) -> Vec<Path<S>> {
103        self.0
104            .iter_mut()
105            .filter_map(|(_, entry)| {
106                if entry.active {
107                    entry.active = false;
108                    Some(entry.path.fork())
109                } else {
110                    None
111                }
112            })
113            .collect()
114    }
115}
penumbra_sdk_dex/component/router/path_cache.rs

penumbra_sdk_dex/component/router/
path_cache.rs
