dag/nameset/
hints.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::cmp;
9use std::fmt;
10use std::sync::atomic::AtomicU32;
11use std::sync::atomic::AtomicU64;
12use std::sync::atomic::Ordering::Acquire;
13use std::sync::atomic::Ordering::Relaxed;
14use std::sync::atomic::Ordering::Release;
15use std::sync::Arc;
16
17use bitflags::bitflags;
18
19use crate::ops::DagAlgorithm;
20use crate::ops::IdConvert;
21use crate::Id;
22use crate::VerLink;
23
24bitflags! {
25    pub struct Flags: u32 {
26        /// Full. A full Set & other set X with compatible Dag results in X.
27        const FULL = 0x1;
28
29        /// Empty (also implies ID_DESC | ID_ASC | TOPO_DESC).
30        const EMPTY = 0x2;
31
32        /// Sorted by Id. Descending (head -> root).
33        const ID_DESC = 0x4;
34
35        /// Sorted by Id. Ascending (root -> head).
36        const ID_ASC = 0x8;
37
38        /// Sorted topologically. Descending (head -> root).
39        const TOPO_DESC = 0x10;
40
41        /// Minimal Id is known.
42        const HAS_MIN_ID = 0x20;
43
44        /// Maximum Id is known.
45        const HAS_MAX_ID = 0x40;
46
47        /// A "filter" set. It provides "contains" but iteration is inefficient.
48        const FILTER = 0x80;
49
50        /// The set contains ancestors. If X in set, any ancestor of X is also in set.
51        const ANCESTORS = 0x100;
52    }
53}
54
55/// Optimation hints.
56#[derive(Default)]
57pub struct Hints {
58    // Atomic is used for interior mutability.
59    flags: AtomicU32,
60    min_id: AtomicU64,
61    max_id: AtomicU64,
62    id_map: IdMapSnapshot,
63    dag: DagSnapshot,
64}
65
66impl Hints {
67    pub fn new_with_idmap_dag(
68        id_map: impl Into<IdMapSnapshot>,
69        dag: impl Into<DagSnapshot>,
70    ) -> Self {
71        Self {
72            id_map: id_map.into(),
73            dag: dag.into(),
74            ..Default::default()
75        }
76    }
77
78    pub fn new_inherit_idmap_dag(hints: &Self) -> Self {
79        Self::new_with_idmap_dag(hints, hints)
80    }
81
82    /// Attempt to inherit properties (IdMap and Dag snapshots) from a list of
83    /// hints. The returned hints have IdMap and Dag set to be compatible with
84    /// all other hints in the list (or set to be None if that's not possible).
85    pub fn union(hints_list: &[&Self]) -> Self {
86        let default = Self::default();
87        // Find the id_map that is compatible with all other id_maps.
88        debug_assert!(default.id_map().is_none());
89        let id_map = hints_list
90            .iter()
91            .fold(Some(&default), |opt_a, b| {
92                opt_a.and_then(
93                    |a| match a.id_map_version().partial_cmp(&b.id_map_version()) {
94                        None => None, // Incompatible sets
95                        Some(cmp::Ordering::Equal) | Some(cmp::Ordering::Greater) => Some(a),
96                        Some(cmp::Ordering::Less) => Some(b),
97                    },
98                )
99            })
100            .and_then(|a| a.id_map());
101        // Find the dag that is compatible with all other dags.
102        debug_assert!(default.dag().is_none());
103        let dag = hints_list
104            .iter()
105            .fold(Some(&default), |opt_a, b| {
106                opt_a.and_then(|a| match a.dag_version().partial_cmp(&b.dag_version()) {
107                    None => None,
108                    Some(cmp::Ordering::Equal) | Some(cmp::Ordering::Greater) => Some(a),
109                    Some(cmp::Ordering::Less) => Some(b),
110                })
111            })
112            .and_then(|a| a.dag());
113        Self {
114            id_map: IdMapSnapshot(id_map),
115            dag: DagSnapshot(dag),
116            ..Self::default()
117        }
118    }
119
120    pub fn flags(&self) -> Flags {
121        let flags = self.flags.load(Relaxed);
122        Flags::from_bits_truncate(flags)
123    }
124
125    pub fn contains(&self, flags: Flags) -> bool {
126        self.flags().contains(flags)
127    }
128
129    pub fn min_id(&self) -> Option<Id> {
130        if self.contains(Flags::HAS_MIN_ID) {
131            Some(Id(self.min_id.load(Acquire)))
132        } else {
133            None
134        }
135    }
136
137    pub fn max_id(&self) -> Option<Id> {
138        if self.contains(Flags::HAS_MAX_ID) {
139            Some(Id(self.max_id.load(Acquire)))
140        } else {
141            None
142        }
143    }
144
145    pub fn update_flags_with(&self, func: impl Fn(Flags) -> Flags) -> &Self {
146        let mut flags = func(self.flags());
147        // Automatically add "derived" flags.
148        if flags.contains(Flags::EMPTY) {
149            flags.insert(Flags::ID_ASC | Flags::ID_DESC | Flags::TOPO_DESC | Flags::ANCESTORS);
150        }
151        if flags.contains(Flags::FULL) {
152            flags.insert(Flags::ANCESTORS);
153        }
154        self.flags.store(flags.bits(), Relaxed);
155        self
156    }
157
158    pub fn add_flags(&self, flags: Flags) -> &Self {
159        self.update_flags_with(|f| f | flags);
160        self
161    }
162
163    pub fn remove_flags(&self, flags: Flags) -> &Self {
164        self.update_flags_with(|f| f - flags);
165        self
166    }
167
168    pub fn set_min_id(&self, min_id: Id) -> &Self {
169        self.min_id.store(min_id.0, Release);
170        self.add_flags(Flags::HAS_MIN_ID);
171        self
172    }
173
174    pub fn set_max_id(&self, max_id: Id) -> &Self {
175        self.max_id.store(max_id.0, Release);
176        self.add_flags(Flags::HAS_MAX_ID);
177        self
178    }
179
180    pub fn inherit_flags_min_max_id(&self, other: &Hints) -> &Self {
181        self.update_flags_with(|_| other.flags());
182        if let Some(id) = other.min_id() {
183            self.set_min_id(id);
184        }
185        if let Some(id) = other.max_id() {
186            self.set_max_id(id);
187        }
188        self
189    }
190
191    pub fn dag(&self) -> Option<Arc<dyn DagAlgorithm + Send + Sync>> {
192        self.dag.0.clone()
193    }
194
195    pub fn id_map(&self) -> Option<Arc<dyn IdConvert + Send + Sync>> {
196        self.id_map.0.clone()
197    }
198
199    /// The `VerLink` of the Dag. `None` if there is no Dag associated.
200    pub fn dag_version(&self) -> Option<&VerLink> {
201        self.dag.0.as_ref().map(|d| d.dag_version())
202    }
203
204    /// The `VerLink` of the IdMap. `None` if there is no IdMap associated.
205    pub fn id_map_version(&self) -> Option<&VerLink> {
206        self.id_map.0.as_ref().map(|d| d.map_version())
207    }
208}
209
210#[derive(Clone, Default)]
211pub struct DagSnapshot(Option<Arc<dyn DagAlgorithm + Send + Sync>>);
212
213impl From<&Hints> for DagSnapshot {
214    fn from(hints: &Hints) -> Self {
215        hints.dag.clone()
216    }
217}
218
219impl From<Arc<dyn DagAlgorithm + Send + Sync>> for DagSnapshot {
220    fn from(dag: Arc<dyn DagAlgorithm + Send + Sync>) -> Self {
221        DagSnapshot(Some(dag))
222    }
223}
224
225#[derive(Clone, Default)]
226pub struct IdMapSnapshot(Option<Arc<dyn IdConvert + Send + Sync>>);
227
228impl From<&Hints> for IdMapSnapshot {
229    fn from(hints: &Hints) -> Self {
230        hints.id_map.clone()
231    }
232}
233
234impl From<Arc<dyn IdConvert + Send + Sync>> for IdMapSnapshot {
235    fn from(dag: Arc<dyn IdConvert + Send + Sync>) -> Self {
236        IdMapSnapshot(Some(dag))
237    }
238}
239
240#[derive(Clone, Default)]
241pub struct DagVersion<'a>(Option<&'a VerLink>);
242
243impl<'a> From<&'a Hints> for DagVersion<'a> {
244    fn from(hints: &'a Hints) -> Self {
245        Self(match &hints.dag.0 {
246            Some(d) => Some(d.dag_version()),
247            None => None,
248        })
249    }
250}
251
252impl<'a> From<&'a VerLink> for DagVersion<'a> {
253    fn from(version: &'a VerLink) -> Self {
254        Self(Some(version))
255    }
256}
257
258#[derive(Clone, Default)]
259pub struct IdMapVersion<'a>(Option<&'a VerLink>);
260
261impl<'a> From<&'a Hints> for IdMapVersion<'a> {
262    fn from(hints: &'a Hints) -> Self {
263        Self(match &hints.id_map.0 {
264            Some(m) => Some(m.map_version()),
265            None => None,
266        })
267    }
268}
269
270impl<'a> From<&'a VerLink> for IdMapVersion<'a> {
271    fn from(version: &'a VerLink) -> Self {
272        Self(Some(version))
273    }
274}
275
276impl Clone for Hints {
277    fn clone(&self) -> Self {
278        Self {
279            flags: AtomicU32::new(self.flags.load(Acquire)),
280            min_id: AtomicU64::new(self.min_id.load(Acquire)),
281            max_id: AtomicU64::new(self.max_id.load(Acquire)),
282            id_map: self.id_map.clone(),
283            dag: self.dag.clone(),
284        }
285    }
286}
287
288impl fmt::Debug for Hints {
289    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
290        write!(
291            f,
292            "Hints({:?}",
293            self.flags() - (Flags::HAS_MIN_ID | Flags::HAS_MAX_ID)
294        )?;
295        match (self.min_id(), self.max_id()) {
296            (Some(min), Some(max)) => write!(f, ", {}..={}", min.0, max.0)?,
297            (Some(min), None) => write!(f, ", {}..", min.0)?,
298            (None, Some(max)) => write!(f, ", ..={}", max.0)?,
299            (None, None) => {}
300        }
301        write!(f, ")")?;
302        Ok(())
303    }
304}
305
306#[cfg(test)]
307#[test]
308fn test_incompatilbe_union() {
309    use crate::tests::dummy_dag::DummyDag;
310    let dag1 = DummyDag::new();
311    let dag2 = DummyDag::new();
312
313    let mut hints1 = Hints::default();
314    hints1.dag = DagSnapshot(Some(dag1.dag_snapshot().unwrap()));
315
316    let mut hints2 = Hints::default();
317    hints2.dag = DagSnapshot(Some(dag2.dag_snapshot().unwrap()));
318
319    assert_eq!(
320        Hints::union(&[&hints1, &hints1]).dag_version(),
321        hints1.dag_version()
322    );
323
324    assert_eq!(Hints::union(&[&hints1, &hints2]).dag_version(), None);
325    assert_eq!(Hints::union(&[&hints2, &hints1]).dag_version(), None);
326    assert_eq!(
327        Hints::union(&[&hints2, &hints1, &hints2]).dag_version(),
328        None
329    );
330}
dag/nameset/hints.rs

dag/nameset/
hints.rs
