Struct cranelift_isle::DisjointSets

pub struct DisjointSets<T> { /* private fields */ }

Stores disjoint sets and provides efficient operations to merge two sets, and to find a representative member of a set given any member of that set. In this implementation, sets always have at least two members, and can only be formed by the merge operation.

Implementations

impl<T: Copy + Debug + Eq + Hash> DisjointSets<T>

pub fn find_mut(&mut self, x: T) -> Option<T>

Find a representative member of the set containing x. If x has not been merged with any other items using merge, returns None. This method updates the data structure to make future queries faster, and takes amortized constant time.

let mut sets = cranelift_isle::DisjointSets::default();
sets.merge(1, 2);
sets.merge(1, 3);
sets.merge(2, 4);
assert_eq!(sets.find_mut(3).unwrap(), sets.find_mut(4).unwrap());
assert_eq!(sets.find_mut(10), None);

Examples found in repository

src/lib.rs (line 132)

    pub fn merge(&mut self, x: T, y: T) {
        assert_ne!(x, y);
        let mut x = if let Some(x) = self.find_mut(x) {
            self.parent[&x]
        } else {
            self.parent.insert(x, (x, 0));
            (x, 0)
        };
        let mut y = if let Some(y) = self.find_mut(y) {
            self.parent[&y]
        } else {
            self.parent.insert(y, (y, 0));
            (y, 0)
        };

        if x == y {
            return;
        }

        if x.1 < y.1 {
            std::mem::swap(&mut x, &mut y);
        }

        self.parent.get_mut(&y.0).unwrap().0 = x.0;
        if x.1 == y.1 {
            let x_rank = &mut self.parent.get_mut(&x.0).unwrap().1;
            *x_rank = x_rank.saturating_add(1);
        }
    }

    /// Remove the set containing the given item, and return all members of that set. The set is
    /// returned in sorted order. This method takes time linear in the total size of all sets.
    ///
    /// ```
    /// let mut sets = cranelift_isle::DisjointSets::default();
    /// sets.merge(1, 2);
    /// sets.merge(1, 3);
    /// sets.merge(2, 4);
    /// assert_eq!(sets.remove_set_of(4), &[1, 2, 3, 4]);
    /// assert_eq!(sets.remove_set_of(1), &[]);
    /// assert!(sets.is_empty());
    /// ```
    pub fn remove_set_of(&mut self, x: T) -> Vec<T>
    where
        T: Ord,
    {
        let mut set = Vec::new();
        if let Some(x) = self.find_mut(x) {
            set.extend(self.parent.keys().copied());
            // It's important to use `find_mut` here to avoid quadratic worst-case time.
            set.retain(|&y| self.find_mut(y).unwrap() == x);
            for y in set.iter() {
                self.parent.remove(y);
            }
            set.sort_unstable();
        }
        set
    }

src/trie_again.rs (line 345)

    fn normalize_equivalence_classes(&mut self) {
        // First, find all the constraints that need to be copied to other binding sites in their
        // respective equivalence classes. Note: do not remove these constraints here! Yes, we'll
        // put them back later, but we rely on still having them around so that
        // `set_constraint` can detect conflicting constraints.
        let mut deferred_constraints = Vec::new();
        for (&binding, &constraint) in self.current_rule.constraints.iter() {
            if let Some(root) = self.current_rule.equals.find_mut(binding) {
                deferred_constraints.push((root, constraint));
            }
        }

        // Pick one constraint and propagate it through its equivalence class. If there are no
        // errors then it doesn't matter what order we do this in, because that means that any
        // redundant constraints on an equivalence class were equal. We can write equal values into
        // the constraint map in any order and get the same result. If there were errors, we aren't
        // going to generate code from this rule, so order only affects how conflicts are reported.
        while let Some((current, constraint)) = deferred_constraints.pop() {
            // Remove the entire equivalence class and instead add copies of this constraint to
            // every binding site in the class. If there are constraints on other binding sites in
            // this class, then when we try to copy this constraint to those binding sites,
            // `set_constraint` will check that the constraints are equal and record an appropriate
            // error otherwise.
            //
            // Later, we'll re-visit those other binding sites because they're still in
            // `deferred_constraints`, but `set` will be empty because we already deleted the
            // equivalence class the first time we encountered it.
            let set = self.current_rule.equals.remove_set_of(current);
            match (constraint, set.split_first()) {
                // If the equivalence class was empty we don't have to do anything.
                (_, None) => continue,

                // If we removed an equivalence class with an enum variant constraint, make the
                // fields of the variant equal instead. Create a binding for every field of every
                // member of `set`. Arbitrarily pick one to set all the others equal to. If there
                // are existing constraints on the new fields, copy those around the new equivalence
                // classes too.
                (
                    Constraint::Variant {
                        fields, variant, ..
                    },
                    Some((&base, rest)),
                ) => {
                    let mut defer = |this: &Self, binding| {
                        // We're adding equality constraints to binding sites that may not have had
                        // one already. If that binding site already had a concrete constraint, then
                        // we need to "recursively" propagate that constraint through the new
                        // equivalence class too.
                        if let Some(constraint) = this.current_rule.get_constraint(binding) {
                            deferred_constraints.push((binding, constraint));
                        }
                    };
                    let base_fields = self.variant_bindings(base, fields, variant);
                    base_fields.iter().for_each(|&x| defer(self, x));
                    for &binding in rest {
                        for (&x, y) in base_fields
                            .iter()
                            .zip(self.variant_bindings(binding, fields, variant))
                        {
                            defer(self, y);
                            self.current_rule.equals.merge(x, y);
                        }
                    }
                }

                // These constraints don't introduce new binding sites.
                (Constraint::ConstInt { .. } | Constraint::ConstPrim { .. }, _) => {}

                // Currently, `Some` constraints are only introduced implicitly during the
                // translation from `sema`, so there's no way to set the corresponding binding
                // sites equal to each other. Instead, any equality constraints get applied on
                // the results of matching `Some()` or tuple patterns.
                (Constraint::Some, _) => unreachable!(),
            }

            for binding in set {
                self.set_constraint(binding, constraint);
            }
        }
    }

pub fn merge(&mut self, x: T, y: T)

Merge the set containing x with the set containing y. This method takes amortized constant time.

Examples found in repository

src/trie_again.rs (line 398)

    fn normalize_equivalence_classes(&mut self) {
        // First, find all the constraints that need to be copied to other binding sites in their
        // respective equivalence classes. Note: do not remove these constraints here! Yes, we'll
        // put them back later, but we rely on still having them around so that
        // `set_constraint` can detect conflicting constraints.
        let mut deferred_constraints = Vec::new();
        for (&binding, &constraint) in self.current_rule.constraints.iter() {
            if let Some(root) = self.current_rule.equals.find_mut(binding) {
                deferred_constraints.push((root, constraint));
            }
        }

        // Pick one constraint and propagate it through its equivalence class. If there are no
        // errors then it doesn't matter what order we do this in, because that means that any
        // redundant constraints on an equivalence class were equal. We can write equal values into
        // the constraint map in any order and get the same result. If there were errors, we aren't
        // going to generate code from this rule, so order only affects how conflicts are reported.
        while let Some((current, constraint)) = deferred_constraints.pop() {
            // Remove the entire equivalence class and instead add copies of this constraint to
            // every binding site in the class. If there are constraints on other binding sites in
            // this class, then when we try to copy this constraint to those binding sites,
            // `set_constraint` will check that the constraints are equal and record an appropriate
            // error otherwise.
            //
            // Later, we'll re-visit those other binding sites because they're still in
            // `deferred_constraints`, but `set` will be empty because we already deleted the
            // equivalence class the first time we encountered it.
            let set = self.current_rule.equals.remove_set_of(current);
            match (constraint, set.split_first()) {
                // If the equivalence class was empty we don't have to do anything.
                (_, None) => continue,

                // If we removed an equivalence class with an enum variant constraint, make the
                // fields of the variant equal instead. Create a binding for every field of every
                // member of `set`. Arbitrarily pick one to set all the others equal to. If there
                // are existing constraints on the new fields, copy those around the new equivalence
                // classes too.
                (
                    Constraint::Variant {
                        fields, variant, ..
                    },
                    Some((&base, rest)),
                ) => {
                    let mut defer = |this: &Self, binding| {
                        // We're adding equality constraints to binding sites that may not have had
                        // one already. If that binding site already had a concrete constraint, then
                        // we need to "recursively" propagate that constraint through the new
                        // equivalence class too.
                        if let Some(constraint) = this.current_rule.get_constraint(binding) {
                            deferred_constraints.push((binding, constraint));
                        }
                    };
                    let base_fields = self.variant_bindings(base, fields, variant);
                    base_fields.iter().for_each(|&x| defer(self, x));
                    for &binding in rest {
                        for (&x, y) in base_fields
                            .iter()
                            .zip(self.variant_bindings(binding, fields, variant))
                        {
                            defer(self, y);
                            self.current_rule.equals.merge(x, y);
                        }
                    }
                }

                // These constraints don't introduce new binding sites.
                (Constraint::ConstInt { .. } | Constraint::ConstPrim { .. }, _) => {}

                // Currently, `Some` constraints are only introduced implicitly during the
                // translation from `sema`, so there's no way to set the corresponding binding
                // sites equal to each other. Instead, any equality constraints get applied on
                // the results of matching `Some()` or tuple patterns.
                (Constraint::Some, _) => unreachable!(),
            }

            for binding in set {
                self.set_constraint(binding, constraint);
            }
        }
    }

    fn variant_bindings(
        &mut self,
        binding: BindingId,
        fields: TupleIndex,
        variant: sema::VariantId,
    ) -> Vec<BindingId> {
        (0..fields.0)
            .map(|field| {
                self.dedup_binding(Binding::MatchVariant {
                    source: binding,
                    variant,
                    field: TupleIndex(field),
                })
            })
            .collect()
    }

    fn dedup_binding(&mut self, binding: Binding) -> BindingId {
        if let Some(binding) = self.binding_map.get(&binding) {
            *binding
        } else {
            let id = BindingId(self.rules.bindings.len().try_into().unwrap());
            self.rules.bindings.push(binding.clone());
            self.binding_map.insert(binding, id);
            id
        }
    }

    fn set_constraint(&mut self, input: BindingId, constraint: Constraint) {
        if let Err(e) = self.current_rule.set_constraint(input, constraint) {
            self.unreachable.push(e);
        }
    }

    fn add_pattern_constraints(&mut self, expr: BindingId) {
        match &self.rules.bindings[expr.index()] {
            Binding::ConstInt { .. } | Binding::ConstPrim { .. } | Binding::Argument { .. } => {}
            Binding::Constructor {
                parameters: sources,
                ..
            }
            | Binding::MakeVariant {
                fields: sources, ..
            } => {
                for source in sources.to_vec() {
                    self.add_pattern_constraints(source);
                }
            }
            &Binding::Extractor {
                parameter: source, ..
            }
            | &Binding::MatchVariant { source, .. }
            | &Binding::MatchTuple { source, .. } => self.add_pattern_constraints(source),
            &Binding::MatchSome { source } => {
                self.set_constraint(source, Constraint::Some);
                self.add_pattern_constraints(source);
            }
        }
    }
}

impl sema::PatternVisitor for RuleSetBuilder {
    type PatternId = BindingId;

    fn add_match_equal(&mut self, a: BindingId, b: BindingId, _ty: sema::TypeId) {
        // If both bindings represent the same binding site, they're implicitly equal.
        if a != b {
            self.current_rule.equals.merge(a, b);
        }
    }

pub fn remove_set_of(&mut self, x: T) -> Vec<T>where
    T: Ord,

Remove the set containing the given item, and return all members of that set. The set is returned in sorted order. This method takes time linear in the total size of all sets.

let mut sets = cranelift_isle::DisjointSets::default();
sets.merge(1, 2);
sets.merge(1, 3);
sets.merge(2, 4);
assert_eq!(sets.remove_set_of(4), &[1, 2, 3, 4]);
assert_eq!(sets.remove_set_of(1), &[]);
assert!(sets.is_empty());

Examples found in repository

src/trie_again.rs (line 365)

    fn normalize_equivalence_classes(&mut self) {
        // First, find all the constraints that need to be copied to other binding sites in their
        // respective equivalence classes. Note: do not remove these constraints here! Yes, we'll
        // put them back later, but we rely on still having them around so that
        // `set_constraint` can detect conflicting constraints.
        let mut deferred_constraints = Vec::new();
        for (&binding, &constraint) in self.current_rule.constraints.iter() {
            if let Some(root) = self.current_rule.equals.find_mut(binding) {
                deferred_constraints.push((root, constraint));
            }
        }

        // Pick one constraint and propagate it through its equivalence class. If there are no
        // errors then it doesn't matter what order we do this in, because that means that any
        // redundant constraints on an equivalence class were equal. We can write equal values into
        // the constraint map in any order and get the same result. If there were errors, we aren't
        // going to generate code from this rule, so order only affects how conflicts are reported.
        while let Some((current, constraint)) = deferred_constraints.pop() {
            // Remove the entire equivalence class and instead add copies of this constraint to
            // every binding site in the class. If there are constraints on other binding sites in
            // this class, then when we try to copy this constraint to those binding sites,
            // `set_constraint` will check that the constraints are equal and record an appropriate
            // error otherwise.
            //
            // Later, we'll re-visit those other binding sites because they're still in
            // `deferred_constraints`, but `set` will be empty because we already deleted the
            // equivalence class the first time we encountered it.
            let set = self.current_rule.equals.remove_set_of(current);
            match (constraint, set.split_first()) {
                // If the equivalence class was empty we don't have to do anything.
                (_, None) => continue,

                // If we removed an equivalence class with an enum variant constraint, make the
                // fields of the variant equal instead. Create a binding for every field of every
                // member of `set`. Arbitrarily pick one to set all the others equal to. If there
                // are existing constraints on the new fields, copy those around the new equivalence
                // classes too.
                (
                    Constraint::Variant {
                        fields, variant, ..
                    },
                    Some((&base, rest)),
                ) => {
                    let mut defer = |this: &Self, binding| {
                        // We're adding equality constraints to binding sites that may not have had
                        // one already. If that binding site already had a concrete constraint, then
                        // we need to "recursively" propagate that constraint through the new
                        // equivalence class too.
                        if let Some(constraint) = this.current_rule.get_constraint(binding) {
                            deferred_constraints.push((binding, constraint));
                        }
                    };
                    let base_fields = self.variant_bindings(base, fields, variant);
                    base_fields.iter().for_each(|&x| defer(self, x));
                    for &binding in rest {
                        for (&x, y) in base_fields
                            .iter()
                            .zip(self.variant_bindings(binding, fields, variant))
                        {
                            defer(self, y);
                            self.current_rule.equals.merge(x, y);
                        }
                    }
                }

                // These constraints don't introduce new binding sites.
                (Constraint::ConstInt { .. } | Constraint::ConstPrim { .. }, _) => {}

                // Currently, `Some` constraints are only introduced implicitly during the
                // translation from `sema`, so there's no way to set the corresponding binding
                // sites equal to each other. Instead, any equality constraints get applied on
                // the results of matching `Some()` or tuple patterns.
                (Constraint::Some, _) => unreachable!(),
            }

            for binding in set {
                self.set_constraint(binding, constraint);
            }
        }
    }

pub fn is_empty(&self) -> bool

Returns true if there are no sets. This method takes constant time.

let mut sets = cranelift_isle::DisjointSets::default();
assert!(sets.is_empty());
sets.merge(1, 2);
assert!(!sets.is_empty());

Examples found in repository

src/trie_again.rs (line 220)

    pub fn may_overlap(&self, other: &Rule) -> Overlap {
        // Two rules can't overlap if, for some binding site in the intersection of their
        // constraints, the rules have different constraints: an input can't possibly match both
        // rules then. If the rules do overlap, and one has a subset of the constraints of the
        // other, then the less-constrained rule matches every input that the more-constrained rule
        // matches, and possibly more. We test for both conditions at once, with the observation
        // that if the intersection of two sets is equal to the smaller set, then it's a subset. So
        // the outer loop needs to go over the rule with fewer constraints in order to correctly
        // identify if it's a subset of the other rule. Also, that way around is faster.
        let (small, big) = if self.constraints.len() <= other.constraints.len() {
            (self, other)
        } else {
            (other, self)
        };

        // TODO: nonlinear constraints complicate the subset check
        // For the purpose of overlap checking, equality constraints act like other constraints, in
        // that they can cause rules to not overlap. However, because we don't have a concrete
        // pattern to compare, the analysis to prove that is complicated. For now, we approximate
        // the result. If either rule has nonlinear constraints, conservatively report that neither
        // is a subset of the other. Note that this does not disagree with the doc comment for
        // `Overlap::Yes { subset }` which says to use `total_constraints` to disambiguate, since if
        // we return `subset: true` here, `equals` is empty for both rules, so `total_constraints()`
        // equals `constraints.len()`.
        let mut subset = small.equals.is_empty() && big.equals.is_empty();

        for (binding, a) in small.constraints.iter() {
            if let Some(b) = big.constraints.get(binding) {
                if a != b {
                    // If any binding site is constrained differently by both rules then there is
                    // no input where both rules can match.
                    return Overlap::No;
                }
                // Otherwise both are constrained in the same way at this binding site. That doesn't
                // rule out any possibilities for what inputs the rules accept.
            } else {
                // The `big` rule's inputs are a subset of the `small` rule's inputs if every
                // constraint in `small` is exactly matched in `big`. But we found a counterexample.
                subset = false;
            }
        }
        Overlap::Yes { subset }
    }

pub fn len(&self) -> usize

Returns the total number of elements in all sets. This method takes constant time.

let mut sets = cranelift_isle::DisjointSets::default();
sets.merge(1, 2);
assert_eq!(sets.len(), 2);
sets.merge(3, 4);
sets.merge(3, 5);
assert_eq!(sets.len(), 5);

Examples found in repository

src/trie_again.rs (line 245)

    pub fn total_constraints(&self) -> usize {
        // Because of `normalize_equivalence_classes`, these two sets don't overlap, so the size of
        // the union is the sum of their sizes.
        self.constraints.len() + self.equals.len()
    }

Trait Implementations

impl<T: Debug> Debug for DisjointSets<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default> Default for DisjointSets<T>

fn default() -> DisjointSets<T>

Returns the “default value” for a type.