Trait IdDagAlgorithm

pub trait IdDagAlgorithm: IdDagStore {
    // Provided methods
    fn all(&self) -> Result<IdSet> { ... }
    fn master_group(&self) -> Result<IdSet> { ... }
    fn ancestors(&self, set: IdSet) -> Result<IdSet> { ... }
    fn first_ancestors(&self, set: IdSet) -> Result<IdSet> { ... }
    fn merges(&self, set: IdSet) -> Result<IdSet> { ... }
    fn parents(&self, set: IdSet) -> Result<IdSet> { ... }
    fn parent_ids(&self, id: Id) -> Result<Vec<Id>> { ... }
    fn first_ancestor_nth(&self, id: Id, n: u64) -> Result<Id> { ... }
    fn try_first_ancestor_nth(&self, id: Id, n: u64) -> Result<Option<Id>> { ... }
    fn to_first_ancestor_nth(
        &self,
        id: Id,
        constraint: FirstAncestorConstraint,
    ) -> Result<Option<(Id, u64)>> { ... }
    fn to_first_ancestor_nth_known_universally(
        &self,
        id: Id,
        heads: IdSet,
    ) -> Result<Option<(Id, u64)>> { ... }
    fn to_first_ancestor_nth_known_universally_with_errors(
        &self,
        id: Id,
        heads: &IdSet,
        details: Option<Vec<String>>,
    ) -> Result<Option<(Id, u64)>> { ... }
    fn heads(&self, set: IdSet) -> Result<IdSet> { ... }
    fn children_id(&self, id: Id) -> Result<IdSet> { ... }
    fn children(&self, set: IdSet) -> Result<IdSet> { ... }
    fn children_set(&self, set: IdSet) -> Result<IdSet> { ... }
    fn roots(&self, set: IdSet) -> Result<IdSet> { ... }
    fn gca_one(&self, set: IdSet) -> Result<Option<Id>> { ... }
    fn gca_all(&self, set: IdSet) -> Result<IdSet> { ... }
    fn common_ancestors(&self, set: IdSet) -> Result<IdSet> { ... }
    fn is_ancestor(&self, ancestor_id: Id, descendant_id: Id) -> Result<bool> { ... }
    fn heads_ancestors(&self, set: IdSet) -> Result<IdSet> { ... }
    fn range(&self, roots: IdSet, heads: IdSet) -> Result<IdSet> { ... }
    fn descendants(&self, set: IdSet) -> Result<IdSet> { ... }
    fn descendants_intersection(
        &self,
        roots: &IdSet,
        ancestors: &IdSet,
    ) -> Result<IdSet> { ... }
    fn id_set_to_id_segments(
        &self,
        id_set: &IdSet,
    ) -> Result<VecDeque<IdSegment>> { ... }
    fn id_segment_to_lower_level_id_segments(
        &self,
        id_segment: &IdSegment,
    ) -> Result<VecDeque<IdSegment>> { ... }
    fn id_set_to_id_segments_with_max_level(
        &self,
        id_set: &IdSet,
        max_level: Level,
    ) -> Result<VecDeque<IdSegment>> { ... }
}

Provided Methods

fn all(&self) -> Result<IdSet>

Return a IdSet that covers all ids stored in this IdDag.

fn master_group(&self) -> Result<IdSet>

Return a IdSet that covers all ids stored in the master group.

fn ancestors(&self, set: IdSet) -> Result<IdSet>

Calculate all ancestors reachable from any id from the given set.

union(ancestors(i) for i in set)

fn first_ancestors(&self, set: IdSet) -> Result<IdSet>

Like ancestors but follows only the first parents.

fn merges(&self, set: IdSet) -> Result<IdSet>

Calculate merges within the given set.

fn parents(&self, set: IdSet) -> Result<IdSet>

Calculate parents of the given set.

Note: IdSet does not preserve order. Use [IdDag::parent_ids] if order is needed.

fn parent_ids(&self, id: Id) -> Result<Vec<Id>>

Get parents of a single id. Preserve the order.

fn first_ancestor_nth(&self, id: Id, n: u64) -> Result<Id>

Calculate the n-th first ancestor. If n is 0, return id unchanged. If n is 1, return the first parent of id.

fn try_first_ancestor_nth(&self, id: Id, n: u64) -> Result<Option<Id>>

Calculate the n-th first ancestor. If n is 0, return id unchanged. If n is 1, return the first parent of id. If n is too large, exceeding the distance between the root and id, return None.

fn to_first_ancestor_nth( &self, id: Id, constraint: FirstAncestorConstraint, ) -> Result<Option<(Id, u64)>>

Convert an id to x~n form with the given constraint.

Return None if the conversion can not be done with the constraints.

fn to_first_ancestor_nth_known_universally( &self, id: Id, heads: IdSet, ) -> Result<Option<(Id, u64)>>

See FirstAncestorConstraint::KnownUniversally.

Try to represent id as x~n (revset notation) form, where x must be in heads + parents(merge() & ancestors(heads)).

Return None if id is not part of ancestors(heads).

fn to_first_ancestor_nth_known_universally_with_errors( &self, id: Id, heads: &IdSet, details: Option<Vec<String>>, ) -> Result<Option<(Id, u64)>>

Internal implementation of to_first_ancestor_nth_known_universally.

If details is not None, it is used to store extra error messages with some extra overhead.

fn heads(&self, set: IdSet) -> Result<IdSet>

Calculate heads of the given set.

fn children_id(&self, id: Id) -> Result<IdSet>

Calculate children for a single Id.

fn children(&self, set: IdSet) -> Result<IdSet>

Calculate children of the given set.

fn children_set(&self, set: IdSet) -> Result<IdSet>

fn roots(&self, set: IdSet) -> Result<IdSet>

Calculate roots of the given set.

fn gca_one(&self, set: IdSet) -> Result<Option<Id>>

Calculate 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(&self, set: IdSet) -> Result<IdSet>

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

fn common_ancestors(&self, set: IdSet) -> Result<IdSet>

Calculate all common ancestors of the given set.

intersect(ancestors(i) for i in set)

fn is_ancestor(&self, ancestor_id: Id, descendant_id: Id) -> Result<bool>

Test if ancestor_id is an ancestor of descendant_id.

fn heads_ancestors(&self, set: IdSet) -> Result<IdSet>

Calculate “heads” of the ancestors of the given IdSet. 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)).

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 range(&self, roots: IdSet, heads: IdSet) -> Result<IdSet>

Calculate the “dag range” - ids reachable from both sides.

intersect(ancestors(heads), descendants(roots))

This is O(flat segments), or O(merges).

fn descendants(&self, set: IdSet) -> Result<IdSet>

Calculate the descendants of the given set.

Logically equivalent to range(set, all()).

This is O(flat segments), or O(merges).

fn descendants_intersection( &self, roots: &IdSet, ancestors: &IdSet, ) -> Result<IdSet>

Calculate (descendants(roots) & ancestors).

This is O(flat segments), or O(merges).

ancestors(ancestors) must be equal to ancestors.

fn id_set_to_id_segments(&self, id_set: &IdSet) -> Result<VecDeque<IdSegment>>

Find segments that cover the given id_set exactly. Returned segments are in DESC order.

fn id_segment_to_lower_level_id_segments( &self, id_segment: &IdSegment, ) -> Result<VecDeque<IdSegment>>

Find lower level segments that cover the given id_segment exactly. Returned segments are in DESC order.

fn id_set_to_id_segments_with_max_level( &self, id_set: &IdSet, max_level: Level, ) -> Result<VecDeque<IdSegment>>

Find segments with max level limitation that cover the given id_set exactly. Returned segments are in DESC order.

Implementors

impl<S: IdDagStore> IdDagAlgorithm for S