dag_types/
segment.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 serde::Deserialize;
9use serde::Serialize;
10
11use crate::id::Id;
12
13/// Base segment.
14///
15/// Intermediate structure between processing a Dag and constructing high level segments.
16#[derive(Debug, Clone, PartialEq, Eq)]
17#[derive(Serialize, Deserialize, Ord, PartialOrd)]
18pub struct FlatSegment {
19    pub low: Id,
20    pub high: Id,
21    pub parents: Vec<Id>,
22}
23
24#[cfg(any(test, feature = "for-tests"))]
25impl quickcheck::Arbitrary for FlatSegment {
26    fn arbitrary(g: &mut quickcheck::Gen) -> Self {
27        Self {
28            low: Id::arbitrary(g),
29            high: Id::arbitrary(g),
30            parents: Vec::arbitrary(g),
31        }
32    }
33}
34
35use std::collections::BTreeSet;
36
37/// These segments can be used directly in the build process of the IdDag.
38/// They produced by `IdMap::assign_head` and `IdDag::all_flat_segments`.
39#[derive(Clone, Debug, Default, PartialEq, Eq)]
40#[derive(Serialize, Deserialize)]
41pub struct PreparedFlatSegments {
42    /// New flat segments.
43    pub segments: BTreeSet<FlatSegment>,
44}
45
46impl PreparedFlatSegments {
47    pub fn vertex_count(&self) -> u64 {
48        let mut count = 0;
49        for segment in &self.segments {
50            count += segment.high.0 - segment.low.0 + 1;
51        }
52        count
53    }
54
55    pub fn segment_count(&self) -> usize {
56        self.segments.len()
57    }
58
59    /// Return set of all (unique) parents + head + roots of flat segments.
60    ///
61    /// Used by the pull fast path to provide necessary "anchor" vertexes
62    /// ("universally known", and ones needed by the client to make decisions)
63    /// in the IdMap.
64    ///
65    /// Might return some extra `Id`s that are not part of parents, heads, or
66    /// roots. They are useful for the client to verify the graph is the same
67    /// as the server.
68    ///
69    /// The size of the returned `Id`s is about `O(segments)`.
70    pub fn parents_head_and_roots(&self) -> BTreeSet<Id> {
71        self.segments
72            .iter()
73            .flat_map(|seg| {
74                // `seg.high` is either a head, or a parent referred by another seg
75                // `seg.low` is either a room, or something unnecessary for lazy protocol,
76                // but speeds up graph shape verification (see `check_isomorphic_graph`).
77                // `parents` are either "universally known", essential for lazy protocol,
78                // or something necessary for the pull protocol to re-map the IdMap.
79                [seg.high, seg.low].into_iter().chain(seg.parents.clone())
80            })
81            .collect()
82    }
83}
dag_types/segment.rs

dag_types/
segment.rs
