Trait DagAlgorithm 

pub trait DagAlgorithm: Send + Sync {
    // Required methods
    fn sort<'life0, 'life1, 'async_trait>(
        &'life0 self,
        set: &'life1 Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait,
             'life1: 'async_trait;
    fn parent_names<'life0, 'async_trait>(
        &'life0 self,
        name: Vertex,
    ) -> Pin<Box<dyn Future<Output = Result<Vec<Vertex>>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn all<'life0, 'async_trait>(
        &'life0 self,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn master_group<'life0, 'async_trait>(
        &'life0 self,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn virtual_group<'life0, 'async_trait>(
        &'life0 self,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn ancestors<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn children<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn range<'life0, 'async_trait>(
        &'life0 self,
        roots: Set,
        heads: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn descendants<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn suggest_bisect<'life0, 'async_trait>(
        &'life0 self,
        roots: Set,
        heads: Set,
        skip: Set,
    ) -> Pin<Box<dyn Future<Output = Result<(Option<Vertex>, Set, Set)>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn dirty<'life0, 'async_trait>(
        &'life0 self,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait;
    fn is_vertex_lazy(&self) -> bool;
    fn dag_snapshot(&self) -> Result<Arc<dyn DagAlgorithm + Send + Sync>>;
    fn dag_id(&self) -> &str;
    fn dag_version(&self) -> &VerLink;

    // Provided methods
    fn beautify<'life0, 'async_trait>(
        &'life0 self,
        main_branch: Option<Set>,
    ) -> Pin<Box<dyn Future<Output = Result<MemDag>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn subdag<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<MemDag>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn parents<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn first_ancestor_nth<'life0, 'async_trait>(
        &'life0 self,
        name: Vertex,
        n: u64,
    ) -> Pin<Box<dyn Future<Output = Result<Option<Vertex>>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn first_ancestors<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn heads<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn roots<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn merges<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn gca_one<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Option<Vertex>>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn gca_all<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn common_ancestors<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn is_ancestor<'life0, 'async_trait>(
        &'life0 self,
        ancestor: Vertex,
        descendant: Vertex,
    ) -> Pin<Box<dyn Future<Output = Result<bool>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn heads_ancestors<'life0, 'async_trait>(
        &'life0 self,
        set: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn only<'life0, 'async_trait>(
        &'life0 self,
        reachable: Set,
        unreachable: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn only_both<'life0, 'async_trait>(
        &'life0 self,
        reachable: Set,
        unreachable: Set,
    ) -> Pin<Box<dyn Future<Output = Result<(Set, Set)>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn reachable_roots<'life0, 'async_trait>(
        &'life0 self,
        roots: Set,
        heads: Set,
    ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>
       where Self: 'async_trait,
             'life0: 'async_trait { ... }
    fn id_dag_snapshot(&self) -> Result<Arc<dyn IdDagAlgorithm + Send + Sync>> { ... }
}

DAG related read-only algorithms.

Required Methods

fn sort<'life0, 'life1, 'async_trait>( &'life0 self, set: &'life1 Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait, 'life1: 'async_trait,

Sort a Set topologically in descending order.

The returned set should have dag and id_map hints set to associated with this dag or its previous compatible version. For example, if a set is sorted on another dag but not in this dag, it should be resorted using this dag. If a set is empty and not associated to the current dag in its hints, the return value should be a different empty set that has the dag and id_map hints set to this dag.

fn parent_names<'life0, 'async_trait>( &'life0 self, name: Vertex, ) -> Pin<Box<dyn Future<Output = Result<Vec<Vertex>>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Get ordered parent vertexes.

fn all<'life0, 'async_trait>( &'life0 self, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Returns a set that covers all vertexes tracked by this DAG.

Does not include VIRTUAL vertexes.

fn master_group<'life0, 'async_trait>( &'life0 self, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Returns a set that covers all vertexes in the master group.

fn virtual_group<'life0, 'async_trait>( &'life0 self, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Returns a set that covers all vertexes in the virtual group.

fn ancestors<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates all ancestors reachable from any name from the given set.

fn children<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates children of the given set.

fn range<'life0, 'async_trait>( &'life0 self, roots: Set, heads: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates the “dag range” - vertexes reachable from both sides.

fn descendants<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates the descendants of the given set.

fn suggest_bisect<'life0, 'async_trait>( &'life0 self, roots: Set, heads: Set, skip: Set, ) -> Pin<Box<dyn Future<Output = Result<(Option<Vertex>, Set, Set)>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Suggest the next place to test during a bisect.

• (roots, heads) are either (good, bad) or (bad, good).
• skip should be non-lazy.

Return (vertex_to_bisect_next, untested_set, roots(high::)).

If vertex_to_bisect_next is None, the bisect is completed. At this time, roots(heads::) is the “first good/bad” set. untested_set is usually empty, or a subset of skip.

fn dirty<'life0, 'async_trait>( &'life0 self, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Vertexes buffered in memory, not yet written to disk.

Does not include VIRTUAL vertexes.

fn is_vertex_lazy(&self) -> bool

Returns true if the vertex names might need to be resolved remotely.

fn dag_snapshot(&self) -> Result<Arc<dyn DagAlgorithm + Send + Sync>>

Get a snapshot of the current graph that can operate separately.

This makes it easier to fight with borrowck.

fn dag_id(&self) -> &str

Identity of the dag.

fn dag_version(&self) -> &VerLink

Version of the dag. Useful to figure out compatibility between two dags.

For performance, this does not include changes to the VIRTUAL group.

Provided Methods

fn beautify<'life0, 'async_trait>( &'life0 self, main_branch: Option<Set>, ) -> Pin<Box<dyn Future<Output = Result<MemDag>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Re-create the graph so it looks better when rendered.

fn subdag<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<MemDag>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Extract a sub graph containing only specified vertexes.

fn parents<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates parents of the given set.

Note: Parent order is not preserved. Use [Dag::parent_names] to preserve order.

fn first_ancestor_nth<'life0, 'async_trait>( &'life0 self, name: Vertex, n: u64, ) -> Pin<Box<dyn Future<Output = Result<Option<Vertex>>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates the n-th first ancestor.

fn first_ancestors<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates ancestors but only follows the first parent.

fn heads<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates heads of the given set.

fn roots<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates roots of the given set.

fn merges<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates merges of the selected set (vertexes with >=2 parents).

fn gca_one<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Option<Vertex>>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates one “greatest common ancestor” of the given set.

If there are no common ancestors, return None. If there are multiple greatest common ancestors, pick one arbitrarily. Use gca_all to get all of them.

fn gca_all<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates all “greatest common ancestor“s of the given set. gca_one is faster if an arbitrary answer is ok.

fn common_ancestors<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates all common ancestors of the given set.

fn is_ancestor<'life0, 'async_trait>( &'life0 self, ancestor: Vertex, descendant: Vertex, ) -> Pin<Box<dyn Future<Output = Result<bool>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Tests if ancestor is an ancestor of descendant.

fn heads_ancestors<'life0, 'async_trait>( &'life0 self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates “heads” of the ancestors of the given set. That is, Find Y, which is the smallest subset of set X, where ancestors(Y) is ancestors(X).

This is faster than calculating heads(ancestors(set)) in certain implementations like segmented changelog.

This is different from heads. In case set contains X and Y, and Y is an ancestor of X, but not the immediate ancestor, heads will include Y while this function won’t.

fn only<'life0, 'async_trait>( &'life0 self, reachable: Set, unreachable: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates ancestors(reachable) - ancestors(unreachable).

fn only_both<'life0, 'async_trait>( &'life0 self, reachable: Set, unreachable: Set, ) -> Pin<Box<dyn Future<Output = Result<(Set, Set)>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates ancestors(reachable) - ancestors(unreachable), and ancestors(unreachable). This might be faster in some implementations than calculating only and ancestors separately.

fn reachable_roots<'life0, 'async_trait>( &'life0 self, roots: Set, heads: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Calculates roots that are reachable from heads without going through other roots. For example, given the following graph:

  F
  |\
  C E
  | |
  B D
  |/
  A

reachable_roots(roots=[A, B, C], heads=[F]) returns [A, C]. B is not included because it cannot be reached without going through another root C from F. A is included because it can be reached via F -> E -> D -> A that does not go through other roots.

The can be calculated as roots & (heads | parents(only(heads, roots & ancestors(heads)))). Actual implementation might have faster paths.

The roots & ancestors(heads) portion filters out bogus roots for compatibility, if the callsite does not provide bogus roots, it could be simplified to just roots.

fn id_dag_snapshot(&self) -> Result<Arc<dyn IdDagAlgorithm + Send + Sync>>

Get a snapshot of the IdDag that can operate separately.

This is for advanced use-cases. For example, if callsite wants to do some graph calculation without network, and control how to batch the vertex name lookups precisely.

Trait Implementations

impl Parents for &(dyn DagAlgorithm + Send + Sync)

fn parent_names<'life0, 'async_trait>( &'life0 self, name: Vertex, ) -> Pin<Box<dyn Future<Output = Result<Vec<Vertex>>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

fn hint_subdag_for_insertion<'life0, 'life1, 'async_trait>( &'life0 self, heads: &'life1 [Vertex], ) -> Pin<Box<dyn Future<Output = Result<MemDag>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait, 'life1: 'async_trait,

A hint of a sub-graph for inserting heads.

Implementations on Foreign Types

impl DagAlgorithm for Arc<dyn DagAlgorithm + Send + Sync>

fn sort<'a: 'c, 'b: 'c, 'c>( &'a self, set: &'b Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 'c>>

where Self: 'c,

fn parent_names<'a: 'c, 'c>( &'a self, name: Vertex, ) -> Pin<Box<dyn Future<Output = Result<Vec<Vertex>>> + Send + 'c>>

where Self: 'c,

fn all<'a: 's, 's>( &'a self, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn master_group<'a: 's, 's>( &'a self, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn virtual_group<'a: 's, 's>( &'a self, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn ancestors<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn first_ancestors<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn parents<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn merges<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn first_ancestor_nth<'a: 's, 's>( &'a self, name: Vertex, n: u64, ) -> Pin<Box<dyn Future<Output = Result<Option<Vertex>>> + Send + 's>>

where Self: 's,

fn heads<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn children<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn roots<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn gca_one<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Option<Vertex>>> + Send + 's>>

where Self: 's,

fn gca_all<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn common_ancestors<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn is_ancestor<'a: 's, 's>( &'a self, ancestor: Vertex, descendant: Vertex, ) -> Pin<Box<dyn Future<Output = Result<bool>> + Send + 's>>

where Self: 's,

fn heads_ancestors<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn range<'a: 's, 's>( &'a self, roots: Set, heads: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn only<'a: 's, 's>( &'a self, reachable: Set, unreachable: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn only_both<'a: 's, 's>( &'a self, reachable: Set, unreachable: Set, ) -> Pin<Box<dyn Future<Output = Result<(Set, Set)>> + Send + 's>>

where Self: 's,

fn descendants<'a: 's, 's>( &'a self, set: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn reachable_roots<'a: 's, 's>( &'a self, roots: Set, heads: Set, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn suggest_bisect<'a: 's, 's>( &'a self, roots: Set, heads: Set, skip: Set, ) -> Pin<Box<dyn Future<Output = Result<(Option<Vertex>, Set, Set)>> + Send + 's>>

where Self: 's,

fn dirty<'a: 's, 's>( &'a self, ) -> Pin<Box<dyn Future<Output = Result<Set>> + Send + 's>>

where Self: 's,

fn is_vertex_lazy(&self) -> bool

fn dag_snapshot(&self) -> Result<Arc<dyn DagAlgorithm + Send + Sync>>

fn id_dag_snapshot(&self) -> Result<Arc<dyn IdDagAlgorithm + Send + Sync>>

fn dag_id(&self) -> &str

fn dag_version(&self) -> &VerLink

Implementors

impl<IS, M, P, S> DagAlgorithm for AbstractDag<IdDag<IS>, M, P, S>

where IS: IdDagStore, IdDag<IS>: TryClone + 'static, M: TryClone + IdConvert + Sync + Send + 'static, P: TryClone + Sync + Send + 'static, S: TryClone + Sync + Send + 'static,

DAG related read-only algorithms.