Record Class Rewrite<L extends Language<L>, D extends @Nullable Object>

java.lang.Object
java.lang.Record
io.github.vecbricks.jegg.Rewrite<L,D>
Type Parameters:
L - the language
D - the analysis fact
Record Components:
name - the rule's name, as toString() shows it; not null
lhs - the left-hand pattern or multi-pattern to search for; not null
rhs - what to add for each match; not null. A pattern applier's variables are checked against lhs's on construction
condition - whether a match may be applied, read at apply time; not null

public record Rewrite<L extends Language<L>, D extends @Nullable Object>(String name, Searcher<L extends Language<L>> lhs, Applier<L extends Language<L>, D extends @Nullable Object> rhs, Condition<L extends Language<L>, D extends @Nullable Object> condition) extends Record
A named rewrite: a left-hand Searcher (a pattern, or several joined in a MultiPattern), a right-hand Applier and a Condition. Searching finds the matches; applying one adds the right-hand side and unions it with the matched class, or, for a multi-pattern right-hand side, with the classes its clause variables name. The runner does both for every rule each iteration, reading all matches before writing any, which is the equality-saturation loop of the paper's Figure 5b.
  • Constructor Details

    • Rewrite

      public Rewrite(String name, Searcher<L> lhs, Applier<L,D> rhs, Condition<L,D> condition)
      Checks that no component is null and that a pattern right-hand side uses only variables the left-hand side binds.
      Throws:
      IllegalArgumentException - if the right-hand side has a subterm or payload variable the left-hand side does not bind (or, for a multi-pattern right-hand side, no earlier clause binds), or if the left-hand side is a multi-pattern whose first clause is a bare variable; egg refuses that one only when it searches
  • Method Details

    • of

      public static <L extends Language<L>, D extends @Nullable Object> Rewrite<L,D> of(String name, Pattern<L> lhs, Pattern<L> rhs)
      A rewrite from one pattern to another, unconditional.
      Type Parameters:
      L - the language
      D - the analysis fact
      Parameters:
      name - the rule's name
      lhs - the pattern to search for
      rhs - the pattern to instantiate for each match, over variables lhs binds
      Returns:
      the rewrite, whose condition always holds
    • multi

      public static <L extends Language<L>, D extends @Nullable Object> Rewrite<L,D> multi(String name, MultiPattern<L> lhs, MultiPattern<L> rhs)
      A rewrite from a multi-pattern to a multi-pattern, unconditional: egg's multi_rewrite!. Each match applies the right-hand clauses in order.
      Type Parameters:
      L - the language
      D - the analysis fact
      Parameters:
      name - the rule's name
      lhs - the clauses to join for a match; the first is not a bare variable
      rhs - the clauses to apply for each match, over variables lhs binds or an earlier right-hand clause does
      Returns:
      the rewrite, whose condition always holds
    • dynamic

      public static <L extends Language<L>, D extends @Nullable Object> Rewrite<L,D> dynamic(String name, Searcher<L> lhs, Applier<L,D> rhs)
      A rewrite from a pattern or multi-pattern to a computed right-hand side, unconditional.
      Type Parameters:
      L - the language
      D - the analysis fact
      Parameters:
      name - the rule's name
      lhs - the pattern or multi-pattern to search for
      rhs - computes the classes to union with each match; a function's variables are not checked, a pattern's or a multi-pattern's (Applier.multi(MultiPattern)) are
      Returns:
      the rewrite, whose condition always holds
    • when

      public Rewrite<L,D> when(Condition<L,D> extra)
      This rewrite under a further condition.
      Parameters:
      extra - a condition that must hold as well as this rewrite's own
      Returns:
      a new rewrite, equal to this one but for the condition, which is this one's and extra
    • search

      public List<Matcher.Match> search(EGraph<L,D> graph)
      The matches of the left-hand side, in the matcher's order. The condition is not read here but in apply(EGraph, Matcher.Match), as egg's ConditionalApplier reads it.
      Parameters:
      graph - the graph to search; not changed
      Returns:
      a fresh list of matches, empty if there are none
    • search

      public List<Matcher.Match> search(EGraph<L,D> graph, int limit)
      The first limit matches, a prefix of all of them (Searcher.search(EGraph, int)); a pattern's search stops within the node that reached the limit, a multi-pattern's within the class of its first clause.
      Parameters:
      graph - the graph to search; not changed
      limit - the most matches to return; must be positive
      Returns:
      a fresh list of at most limit matches, in the matcher's order
    • apply

      public Optional<Applied> apply(EGraph<L,D> graph, Matcher.Match match)
      Applies one match if its condition holds: the right-hand side's Applier.applyTo(EGraph, Matcher.Match) adds its classes and unions them with the matched class, or, for a multi-pattern, does its own unions. Returns what that did, or empty if the condition did not hold and nothing was applied.

      The condition is read here, at apply time, not at search: the runner applies a match only after the matches before it in the iteration, whose merges may have made the condition false since the search.

      Parameters:
      graph - the graph to write to; the match must come from a search of it
      match - a match of this rewrite's left-hand side: the matched class and the substitution for the variables
      Returns:
      the unions that changed the graph and the number egg counts as applied, or empty if the condition did not hold
    • toString

      public String toString()
      Returns a string representation of this record class. The representation contains the name of the class, followed by the name and value of each of the record components.
      Specified by:
      toString in class Record
      Returns:
      a string representation of this object
    • hashCode

      public final int hashCode()
      Returns a hash code value for this object. The value is derived from the hash code of each of the record components.
      Specified by:
      hashCode in class Record
      Returns:
      a hash code value for this object
    • equals

      public final boolean equals(Object o)
      Indicates whether some other object is "equal to" this one. The objects are equal if the other object is of the same class and if all the record components are equal. All components in this record class are compared with Objects::equals(Object,Object).
      Specified by:
      equals in class Record
      Parameters:
      o - the object with which to compare
      Returns:
      true if this object is the same as the o argument; false otherwise.
    • name

      public String name()
      Returns the value of the name record component.
      Returns:
      the value of the name record component
    • lhs

      public Searcher<L> lhs()
      Returns the value of the lhs record component.
      Returns:
      the value of the lhs record component
    • rhs

      public Applier<L,D> rhs()
      Returns the value of the rhs record component.
      Returns:
      the value of the rhs record component
    • condition

      public Condition<L,D> condition()
      Returns the value of the condition record component.
      Returns:
      the value of the condition record component