dag/set/
meta.rs

1/*
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8use std::any::Any;
9use std::fmt;
10use std::sync::RwLock;
11
12use futures::future::BoxFuture;
13
14use super::AsyncSetQuery;
15use super::BoxVertexStream;
16use super::Hints;
17use super::Set;
18use crate::Result;
19use crate::Vertex;
20
21/// A set that is lazily evaluated to another set on access, with an
22/// optional fast path for "contains".
23///
24/// This can be useful for various cases. Especially when "contains" and "iter"
25/// have separate fast paths. For example, `merge()` (merge commits) obviously
26/// has a cheap "contains" fast path by checking if a given commit has
27/// multiple parents. However, if we want to iterating through the set,
28/// segmented changelog has a fast path by iterating flat segments, instead
29/// of testing commits one by one using the "contains" check.
30///
31/// `MetaSet` is different from `LazySet`: `MetaSet`'s `evaluate` function can
32/// return static or lazy or meta sets. `LazySet` does not support a "contains"
33/// fast path (yet).
34///
35/// `MetaSet` is different from a pure filtering set (ex. only has "contains"
36/// fast path), as `MetaSet` supports fast path for iteration, if the underlying
37/// set supports it.
38pub struct MetaSet {
39    evaluate: Box<dyn Fn() -> BoxFuture<'static, Result<Set>> + Send + Sync>,
40    evaluated: RwLock<Option<Set>>,
41
42    /// Optional "contains" fast path.
43    contains: Option<
44        Box<dyn for<'a> Fn(&'a MetaSet, &'a Vertex) -> BoxFuture<'a, Result<bool>> + Send + Sync>,
45    >,
46
47    hints: Hints,
48}
49
50impl fmt::Debug for MetaSet {
51    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
52        f.write_str("<meta ")?;
53        if let Some(set) = self.evaluated() {
54            set.fmt(f)?;
55        } else {
56            f.write_str("?")?;
57        }
58        f.write_str(">")?;
59        Ok(())
60    }
61}
62
63impl MetaSet {
64    /// Constructs `MetaSet` from an `evaluate` function that returns a
65    /// `Set`. The `evaluate` function is not called immediately.
66    pub fn from_evaluate_hints(
67        evaluate: Box<dyn Fn() -> BoxFuture<'static, Result<Set>> + Send + Sync + 'static>,
68        hints: Hints,
69    ) -> Self {
70        Self {
71            evaluate,
72            evaluated: Default::default(),
73            contains: None,
74            hints,
75        }
76    }
77
78    /// Provides a fast path for `contains`. Be careful to make sure "contains"
79    /// matches "evaluate".
80    pub fn with_contains(
81        mut self,
82        contains: Box<
83            dyn for<'a> Fn(&'a MetaSet, &'a Vertex) -> BoxFuture<'a, Result<bool>> + Send + Sync,
84        >,
85    ) -> Self {
86        self.contains = Some(contains);
87        self
88    }
89
90    /// Evaluate the set. Returns a new set.
91    pub async fn evaluate(&self) -> Result<Set> {
92        if let Some(s) = &*self.evaluated.read().unwrap() {
93            return Ok(s.clone());
94        }
95        let s = (self.evaluate)().await?;
96        *self.evaluated.write().unwrap() = Some(s.clone());
97        Ok(s)
98    }
99
100    /// Returns the evaluated set if it was evaluated.
101    /// Returns None if the set was not evaluated.
102    pub fn evaluated(&self) -> Option<Set> {
103        self.evaluated.read().unwrap().clone()
104    }
105}
106
107#[async_trait::async_trait]
108impl AsyncSetQuery for MetaSet {
109    async fn iter(&self) -> Result<BoxVertexStream> {
110        self.evaluate().await?.iter().await
111    }
112
113    async fn iter_rev(&self) -> Result<BoxVertexStream> {
114        self.evaluate().await?.iter_rev().await
115    }
116
117    async fn count_slow(&self) -> Result<u64> {
118        self.evaluate().await?.count_slow().await
119    }
120
121    async fn size_hint(&self) -> (u64, Option<u64>) {
122        match self.evaluated() {
123            Some(set) => set.size_hint().await,
124            None => (0, None),
125        }
126    }
127
128    async fn last(&self) -> Result<Option<Vertex>> {
129        self.evaluate().await?.last().await
130    }
131
132    async fn contains(&self, name: &Vertex) -> Result<bool> {
133        match self.evaluated() {
134            Some(set) => set.contains(name).await,
135            None => match &self.contains {
136                Some(f) => f(self, name).await,
137                None => self.evaluate().await?.contains(name).await,
138            },
139        }
140    }
141
142    async fn contains_fast(&self, name: &Vertex) -> Result<Option<bool>> {
143        match &self.contains {
144            Some(f) => Ok(Some(f(self, name).await?)),
145            None => Ok(None),
146        }
147    }
148
149    fn as_any(&self) -> &dyn Any {
150        self
151    }
152
153    fn hints(&self) -> &Hints {
154        &self.hints
155    }
156}
157
158#[cfg(test)]
159mod tests {
160    use nonblocking::non_blocking_result as r;
161
162    use super::super::tests::*;
163    use super::*;
164
165    fn meta_set(v: &[impl ToString]) -> MetaSet {
166        let v: Vec<_> = v.iter().map(|s| s.to_string()).collect();
167        let f = move || -> BoxFuture<_> {
168            let s = Set::from_static_names(v.clone().into_iter().map(Into::into));
169            Box::pin(async move { Ok(s) })
170        };
171        MetaSet::from_evaluate_hints(Box::new(f), Hints::default())
172    }
173
174    #[test]
175    fn test_meta_basic() -> Result<()> {
176        let set = meta_set(&["1", "3", "2", "7", "5"]);
177
178        assert!(set.evaluated().is_none());
179        assert!(nb(set.contains(&"2".into()))?);
180        // The set is evaluated after a "contains" check without a "contains" fast path.
181        assert!(set.evaluated().is_some());
182
183        check_invariants(&set)?;
184        Ok(())
185    }
186
187    #[test]
188    fn test_meta_contains() -> Result<()> {
189        let set = meta_set(&["1", "3", "2", "7", "5"]).with_contains(Box::new(|_, v| {
190            let r = Ok(v.as_ref().len() == 1 && b"12357".contains(&v.as_ref()[0]));
191            Box::pin(async move { r })
192        }));
193
194        assert!(nb(set.contains(&"2".into()))?);
195        assert!(!nb(set.contains(&"6".into()))?);
196        // The set is not evaluated - contains fast path takes care of the checks.
197        assert!(set.evaluated().is_none());
198
199        check_invariants(&set)?;
200        Ok(())
201    }
202
203    #[test]
204    fn test_size_hint() -> Result<()> {
205        let set = meta_set(&["1", "2"]);
206
207        assert!(set.evaluated().is_none());
208        assert_eq!(nb(set.size_hint()), (0, None));
209
210        assert!(nb(set.contains(&"2".into()))?);
211        assert_eq!(nb(set.size_hint()), (2, Some(2)));
212
213        Ok(())
214    }
215
216    #[test]
217    fn test_debug() {
218        let set = meta_set(&["1", "3", "2", "7", "5"]);
219        assert_eq!(dbg(&set), "<meta ?>");
220        r(set.evaluate()).unwrap();
221        assert_eq!(
222            format!("{:5?}", &set),
223            "<meta <static [31, 33, 32, 37, 35]>>"
224        );
225    }
226
227    quickcheck::quickcheck! {
228        fn test_meta_quickcheck(v: Vec<String>) -> bool {
229            let set = meta_set(&v);
230            check_invariants(&set).unwrap();
231            true
232        }
233    }
234}
dag/set/meta.rs

dag/set/
meta.rs
