Interface Analysis<L extends Language<L>, D extends @Nullable Object>

Type Parameters:
L - the language
D - the fact

public interface Analysis<L extends Language<L>, D extends @Nullable Object>
An e-class analysis: a fact of type D for every e-class, kept true as the graph changes (egg's Analysis trait, the paper's section 4).

make(EGraph, L) computes the fact for one e-node from the facts of its children's classes; join(D, D) combines the facts of two classes that become one, and must be a semilattice join - commutative, associative and idempotent - or rebuilding may not terminate; modify(EGraph, int) may add nodes or merge classes once a class's fact is known, as constant folding does, and must be idempotent for the same reason. The invariant the graph keeps is that every class's fact equals the join of make over its nodes.

  • Method Summary

    Modifier and Type
    Method
    Description
    join(D a, D b)
    The fact for a class made of two classes with these facts.
    make(EGraph<L,D> graph, L node)
    The fact for node, whose children's facts are readable through graph.
    default void
    modify(EGraph<L,D> graph, int id)
    A hook after a class's fact changes: add nodes to it or merge, or do nothing.
    static <L extends Language<L>>
    Analysis<L,Void>
    The analysis that knows nothing: every fact is null and nothing is modified.
  • Method Details

    • make

      D make(EGraph<L,D> graph, L node)
      The fact for node, whose children's facts are readable through graph.
      Parameters:
      graph - the graph the node is being added to
      node - the e-node, whose children are ids of classes of graph
      Returns:
      the node's fact; null only if the analysis allows it, as none() does
    • join

      D join(D a, D b)
      The fact for a class made of two classes with these facts.
      Parameters:
      a - the fact of one class
      b - the fact of the other
      Returns:
      the semilattice join of a and b
    • modify

      default void modify(EGraph<L,D> graph, int id)
      A hook after a class's fact changes: add nodes to it or merge, or do nothing.
      Parameters:
      graph - the graph to change
      id - the class whose fact is known or changed, an id of the graph, not necessarily canonical
    • none

      static <L extends Language<L>> Analysis<L,Void> none()
      The analysis that knows nothing: every fact is null and nothing is modified.
      Type Parameters:
      L - the language
      Returns:
      an analysis whose fact type is Void