Struct cranelift_isle::trie_again::Rule
source · pub struct Rule {
pub pos: Pos,
pub equals: DisjointSets<BindingId>,
pub prio: i64,
pub result: BindingId,
/* private fields */
}Expand description
Fields§
§pos: PosWhere was this rule defined?
equals: DisjointSets<BindingId>Sets of bindings which must be equal for this rule to match.
prio: i64If other rules apply along with this one, the one with the highest numeric priority is evaluated. If multiple applicable rules have the same priority, that’s an overlap error.
result: BindingIdIf this rule applies, the top-level term should evaluate to this expression.
Implementations§
source§impl Rule
impl Rule
sourcepub fn may_overlap(&self, other: &Rule) -> Overlap
pub fn may_overlap(&self, other: &Rule) -> Overlap
Returns whether a given pair of rules can both match on some input, and if so, whether
either matches a subset of the other’s inputs. If this function returns No, then the two
rules definitely do not overlap. However, it may return Yes in cases where the rules can’t
overlap in practice, or where this analysis is not yet precise enough to decide.
Examples found in repository?
src/overlap.rs (line 90)
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
fn check_pair(&mut self, a: &trie_again::Rule, b: &trie_again::Rule) {
if let trie_again::Overlap::Yes { subset } = a.may_overlap(b) {
if a.prio == b.prio {
// edges are undirected
self.nodes.entry(a.pos).or_default().insert(b.pos);
self.nodes.entry(b.pos).or_default().insert(a.pos);
} else if subset {
// One rule's constraints are a subset of the other's, or they're equal.
// This is fine as long as the higher-priority rule has more constraints.
let (lo, hi) = if a.prio < b.prio { (a, b) } else { (b, a) };
if hi.total_constraints() <= lo.total_constraints() {
// Otherwise, the lower-priority rule can never match.
self.shadowed.entry(hi.pos).or_default().push(lo.pos);
}
}
}
}sourcepub fn total_constraints(&self) -> usize
pub fn total_constraints(&self) -> usize
Returns the total number of binding sites which this rule constrains, with either a concrete pattern or an equality constraint.
Examples found in repository?
src/overlap.rs (line 99)
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
fn check_pair(&mut self, a: &trie_again::Rule, b: &trie_again::Rule) {
if let trie_again::Overlap::Yes { subset } = a.may_overlap(b) {
if a.prio == b.prio {
// edges are undirected
self.nodes.entry(a.pos).or_default().insert(b.pos);
self.nodes.entry(b.pos).or_default().insert(a.pos);
} else if subset {
// One rule's constraints are a subset of the other's, or they're equal.
// This is fine as long as the higher-priority rule has more constraints.
let (lo, hi) = if a.prio < b.prio { (a, b) } else { (b, a) };
if hi.total_constraints() <= lo.total_constraints() {
// Otherwise, the lower-priority rule can never match.
self.shadowed.entry(hi.pos).or_default().push(lo.pos);
}
}
}
}sourcepub fn get_constraint(&self, source: BindingId) -> Option<Constraint>
pub fn get_constraint(&self, source: BindingId) -> Option<Constraint>
Returns the constraint that the given binding site must satisfy for this rule to match, if there is one.
Examples found in repository?
src/trie_again.rs (line 386)
338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417
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);
}
}
}