dag/nameset/
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::AsyncNameSetQuery;
15use super::BoxVertexStream;
16use super::Hints;
17use super::NameSet;
18use crate::Result;
19use crate::VertexName;
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.
37pub struct MetaSet {
38    evaluate: Box<dyn Fn() -> BoxFuture<'static, Result<NameSet>> + Send + Sync>,
39    evaluated: RwLock<Option<NameSet>>,
40
41    /// Optional "contains" fast path.
42    contains: Option<
43        Box<
44            dyn for<'a> Fn(&'a MetaSet, &'a VertexName) -> BoxFuture<'a, Result<bool>>
45                + Send
46                + Sync,
47        >,
48    >,
49
50    hints: Hints,
51}
52
53impl fmt::Debug for MetaSet {
54    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
55        f.write_str("<meta ")?;
56        if let Some(set) = self.evaluated() {
57            set.fmt(f)?;
58        } else {
59            f.write_str("?")?;
60        }
61        f.write_str(">")?;
62        Ok(())
63    }
64}
65
66impl MetaSet {
67    /// Constructs `MetaSet` from an `evaluate` function that returns a
68    /// `NameSet`. The `evaluate` function is not called immediately.
69    pub fn from_evaluate_hints(
70        evaluate: Box<dyn Fn() -> BoxFuture<'static, Result<NameSet>> + Send + Sync + 'static>,
71        hints: Hints,
72    ) -> Self {
73        Self {
74            evaluate,
75            evaluated: Default::default(),
76            contains: None,
77            hints,
78        }
79    }
80
81    /// Provides a fast path for `contains`. Be careful to make sure "contains"
82    /// matches "evaluate".
83    pub fn with_contains(
84        mut self,
85        contains: Box<
86            dyn for<'a> Fn(&'a MetaSet, &'a VertexName) -> BoxFuture<'a, Result<bool>>
87                + Send
88                + Sync,
89        >,
90    ) -> Self {
91        self.contains = Some(contains);
92        self
93    }
94
95    /// Evaluate the set. Returns a new set.
96    pub async fn evaluate(&self) -> Result<NameSet> {
97        if let Some(s) = &*self.evaluated.read().unwrap() {
98            return Ok(s.clone());
99        }
100        let s = (self.evaluate)().await?;
101        *self.evaluated.write().unwrap() = Some(s.clone());
102        Ok(s)
103    }
104
105    /// Returns the evaluated set if it was evaluated.
106    /// Returns None if the set was not evaluated.
107    pub fn evaluated(&self) -> Option<NameSet> {
108        self.evaluated.read().unwrap().clone()
109    }
110}
111
112#[async_trait::async_trait]
113impl AsyncNameSetQuery for MetaSet {
114    async fn iter(&self) -> Result<BoxVertexStream> {
115        self.evaluate().await?.iter().await
116    }
117
118    async fn iter_rev(&self) -> Result<BoxVertexStream> {
119        self.evaluate().await?.iter_rev().await
120    }
121
122    async fn count(&self) -> Result<usize> {
123        self.evaluate().await?.count().await
124    }
125
126    async fn last(&self) -> Result<Option<VertexName>> {
127        self.evaluate().await?.last().await
128    }
129
130    async fn contains(&self, name: &VertexName) -> Result<bool> {
131        match self.evaluated() {
132            Some(set) => set.contains(name).await,
133            None => match &self.contains {
134                Some(f) => f(self, name).await,
135                None => self.evaluate().await?.contains(name).await,
136            },
137        }
138    }
139
140    async fn contains_fast(&self, name: &VertexName) -> Result<Option<bool>> {
141        match &self.contains {
142            Some(f) => Ok(Some(f(self, name).await?)),
143            None => Ok(None),
144        }
145    }
146
147    fn as_any(&self) -> &dyn Any {
148        self
149    }
150
151    fn hints(&self) -> &Hints {
152        &self.hints
153    }
154}
155
156#[cfg(test)]
157mod tests {
158    use nonblocking::non_blocking_result as r;
159
160    use super::super::tests::*;
161    use super::*;
162
163    fn meta_set(v: &[impl ToString]) -> MetaSet {
164        let v: Vec<_> = v.iter().map(|s| s.to_string()).collect();
165        let f = move || -> BoxFuture<_> {
166            let s = NameSet::from_static_names(v.clone().into_iter().map(Into::into));
167            Box::pin(async move { Ok(s) })
168        };
169        MetaSet::from_evaluate_hints(Box::new(f), Hints::default())
170    }
171
172    #[test]
173    fn test_meta_basic() -> Result<()> {
174        let set = meta_set(&["1", "3", "2", "7", "5"]);
175
176        assert!(set.evaluated().is_none());
177        assert!(nb(set.contains(&"2".into()))?);
178        // The set is evaluated after a "contains" check without a "contains" fast path.
179        assert!(set.evaluated().is_some());
180
181        check_invariants(&set)?;
182        Ok(())
183    }
184
185    #[test]
186    fn test_meta_contains() -> Result<()> {
187        let set = meta_set(&["1", "3", "2", "7", "5"]).with_contains(Box::new(|_, v| {
188            let r = Ok(v.as_ref().len() == 1 && b"12357".contains(&v.as_ref()[0]));
189            Box::pin(async move { r })
190        }));
191
192        assert!(nb(set.contains(&"2".into()))?);
193        assert!(!nb(set.contains(&"6".into()))?);
194        // The set is not evaluated - contains fast path takes care of the checks.
195        assert!(set.evaluated().is_none());
196
197        check_invariants(&set)?;
198        Ok(())
199    }
200
201    #[test]
202    fn test_debug() {
203        let set = meta_set(&["1", "3", "2", "7", "5"]);
204        assert_eq!(format!("{:?}", &set), "<meta ?>");
205        r(set.evaluate()).unwrap();
206        assert_eq!(
207            format!("{:5?}", &set),
208            "<meta <static [31, 33, 32, 37, 35]>>"
209        );
210    }
211
212    quickcheck::quickcheck! {
213        fn test_meta_quickcheck(v: Vec<String>) -> bool {
214            let set = meta_set(&v);
215            check_invariants(&set).unwrap();
216            true
217        }
218    }
219}
dag/nameset/meta.rs

dag/nameset/
meta.rs
