Module com.darkcollective.relix.ast
Package com.darkcollective.relix.ast.internal

Class AstEquivalence

java.lang.Object
com.darkcollective.relix.ast.internal.AstEquivalence
public final class AstEquivalence extends Object
Structural equality over the AST — "are these two fragments the same expression?", asked without regard to where each was written.

Why record equality is not the answer

Every RelNode, Predicate and Operand is a Java record carrying a SourceLocation as a component, and nothing in this module overrides equals. The compiler-generated component-wise equality therefore includes the source position: σ x > 5 written on line 3 and σ x > 5 written on line 7 are unequal, with different hash codes. Every rule that wants to know whether two fragments say the same thing — duplicate-conjunct removal (p ∧ p → p), bound comparison for contradiction detection, the set-op idempotence laws, any common-subexpression elimination — needs this class instead.

⚠ Testing this

Every test-convenience constructor in this module uses SourceLocation.UNKNOWN. An implementation keyed on record equality passes its unit tests and then finds nothing on real parsed queries, because only parsed fragments carry distinct locations. Fixtures for anything that depends on this class must be built through the parser; hand-built AstBuilders fragments are not evidence.

What is normalised

  • Source locations — ignored everywhere, recursively, including inside the predicates and operands a node carries.
  • Numeric literals — NumberOperand stores a String, so 5, 5.0 and 05 are three distinct values under record equality. They are compared as BigDecimals and are equivalent here. A literal that does not parse as a decimal falls back to string comparison.
  • Identifier case — attribute, function and relation names are compared case-insensitively, matching Predicates.isColumn(com.darkcollective.relix.ast.Operand, java.lang.String) and the symbol layer.

This is not exact structural equality

The normalisation above is the point of this class, and it is also what makes it the wrong comparison for a test asserting that a fragment parsed or was built exactly as written: under the rules above 5.0 matches 5 and users matches Users, so a test asserting either distinction would silently stop asserting anything. Comparing printed forms is the weaker claim in the other direction too — two structurally different trees that print alike compare equal here. For the exact, position-blind comparison, strip the locations and use record equality: AstLocations.stripLocations, published from this module's test fixtures, with RelNodeAssert.isStructurallyEqualTo as its assertion form.

What is deliberately not normalised

  • An attribute's qualifier. Users.id and id are not equivalent. AttributeNames.stripQualifier(java.lang.String) exists and is tempting, but "equal ignoring qualifier" is wrong exactly where this class gets used: in A ⨝ B, A.x and B.x name different columns, and merging them would make a rule that reasons about them vacuous — the same conclusion EQ-001 reached independently. A caller that genuinely wants the unqualified reading should strip before comparing, which makes the choice visible at the call site.
  • Commutativity and associativity. a ∧ b is not equivalent to b ∧ a, and x + 1 is not equivalent to 1 + x. This is structural equality, not semantic equality; a caller that wants the commutative reading should canonicalise its operands first (the predicate simplifier's PRED-003 already normalises a comparison's operand order for precisely this reason).
  • Arithmetic identities. x + 0 is not equivalent to x; that is the expression simplifier's job, and running it first is what makes this comparison see the simplified form.

Reference identity is a different question

RelNode.mapChildren(java.util.function.UnaryOperator<com.darkcollective.relix.ast.RelNode>) contracts to return this when nothing changed, so != is the optimizer's established "did this rewrite fire" signal. That is identity. This class answers semantic sameness, and the two must not be conflated: two fragments can be equivalent here and still be different objects, which is the entire point.

This class is stateless; every method is static.

  • Method Summary

    Modifier and Type
    Method
    Description
    static String
    digest(RelNode node)
    Returns a location-free canonical string for node, equal for exactly the trees equivalent(RelNode, RelNode) accepts — so it can be used as a map or set key where pairwise comparison would be quadratic.
    static boolean
    equivalent(Operand a, Operand b)
    Returns whether two operand expressions are structurally equivalent, ignoring source locations and normalising numeric literals and identifier case.
    static boolean
    equivalent(Predicate a, Predicate b)
    Returns whether two predicates are structurally equivalent, ignoring source locations and normalising the operands they compare.
    static boolean
    equivalent(RelNode a, RelNode b)
    Returns whether two expression trees are structurally equivalent, ignoring source locations.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • equivalent

      public static boolean equivalent(Operand a, Operand b)
      Returns whether two operand expressions are structurally equivalent, ignoring source locations and normalising numeric literals and identifier case.
      Parameters:
      a - the first operand; must not be null
      b - the second operand; must not be null
      Returns:
      true if the two denote the same expression

    • equivalent

      public static boolean equivalent(Predicate a, Predicate b)
      Returns whether two predicates are structurally equivalent, ignoring source locations and normalising the operands they compare.

      This is the comparison duplicate-conjunct removal (p ∧ p → p) asks: Predicates.conjuncts(com.darkcollective.relix.ast.Predicate) splits, this decides which of the results say the same thing, and Predicates.conjoin(java.util.List<com.darkcollective.relix.ast.Predicate>) rebuilds.

      Parameters:
      a - the first predicate; must not be null
      b - the second predicate; must not be null
      Returns:
      true if the two denote the same condition

    • equivalent

      public static boolean equivalent(RelNode a, RelNode b)
      Returns whether two expression trees are structurally equivalent, ignoring source locations.

      How, and what that costs

      This is decided by comparing RelNode.prettyPrint() forms rather than by a 48-arm structural walk, for two reasons that are properties of the printer rather than conveniences:

      • It is location-free — no arm prints a SourceLocation — so the position a fragment was written at cannot leak into the answer.
      • It round-trips through the parser. Two trees that print identically therefore parse back to the same tree, which is what rules out a false positive — the only dangerous direction for a rewrite that deletes one of two "identical" sub-trees.

      It is also exhaustive by construction: RelNodeVisitor has no default arm, so a new node type cannot be added without teaching the printer about it, and this comparison follows for free.

      Known limitation. The printer spells literals verbatim, so σ x > 5 (R) and σ x > 5.0 (R) are not equivalent here, even though equivalent(Operand, Operand) says their bounds are. That is a false negative — a rule declines to fire — which is the safe direction, and it is where the line is drawn deliberately: normalising literals inside a node needs an operand-rewriting arm for all 48 RelNode types, which is the cost this class exists to avoid, and no shipped rule consumes node-level equivalence yet. Fix it when the first one does.

      Parameters:
      a - the first tree; must not be null
      b - the second tree; must not be null
      Returns:
      true if the two trees denote the same expression

    • digest

      public static String digest(RelNode node)
      Returns a location-free canonical string for node, equal for exactly the trees equivalent(RelNode, RelNode) accepts — so it can be used as a map or set key where pairwise comparison would be quadratic.
      Parameters:
      node - the tree to digest; must not be null
      Returns:
      the canonical form; never null