Class ConcreteSubtypeFinder

java.lang.Object
org.ek9lang.compiler.phase5.ConcreteSubtypeFinder
public final class ConcreteSubtypeFinder extends Object
Finds all concrete (non-abstract) subtypes of a given abstract aggregate type.

This component is designed for use from Phase 5 onwards where the full type hierarchy is stable. It serves DI ordering validation, dispatcher type hierarchy validation, and Phase 7 dispatch table generation.

How it answers. An inverted index is built once per instance: every aggregate is registered under the fully-qualified name of itself and of every ancestor reachable through its super chain and trait closure. A query is then a map lookup returning a handful of candidates, each of which is still confirmed with the real predicate. Previously each distinct query rescanned every aggregate in the program, making the enclosing pass O(D x A) - which is the single super-linear term in the whole compiler (b = 2.03, and 42% of a 200K-SLOC compile).

Why the index can be keyed on a name. The relation it stands in for already is: Symbol.isExactSameType is sameCategory && fullyQualifiedName.equals(...), and Symbol.equals compares name, category, genus and source token - which pins a declaration site, so equal symbols share a name. The index is therefore a sound superset: it can offer a candidate that is not really a subtype (two distinct symbols sharing an FQN), and isSubtypeOrImplementor(IAggregateSymbol, IAggregateSymbol) rejects it. It cannot miss one. Self is deliberately registered, because two distinct symbols sharing an FQN are in each other's hierarchy by that definition, and the legacy scan returned them.

The index and cache are per-instance and live for the duration of the validation pass. That is deliberate: aggregates are still created after phase 5 (monomorphised parameterised types in phase 7), so a program-lifetime index would need invalidation. Sharing one index across phases is a separate change with its own correctness question; this one keeps today's lifetime exactly.

Validated against the pre-index full scan by a differential that ran on every query over the whole test corpus (1,739 tests including 37 dispatcher sources and the trait hierarchies), the codegen corpus (653) and the 20K/100K scale rungs: zero divergences, with the differential itself proven able to fail by deliberately truncating the index. See the commit that removed it if it is ever needed again.

  • Constructor Details

  • Method Details

    • findConcreteSubtypes

      public List<AggregateSymbol> findConcreteSubtypes(IAggregateSymbol abstractType)
      Find all concrete (non-abstract) aggregate types that have the given abstract type in their type hierarchy. Checks both the single-inheritance super chain and the full trait hierarchy (including trait supers).
      Parameters:
      abstractType - The abstract aggregate to find subtypes/implementors of
      Returns:
      List of concrete AggregateSymbol instances extending or implementing the abstract type

    • findAllSubtypes

      public List<AggregateSymbol> findAllSubtypes(IAggregateSymbol baseType)
      Find all aggregate types (both abstract and concrete) that have the given base type in their type hierarchy. Used for dispatcher type hierarchy validation where the base type may be concrete and any subtype could implement a trait.
      Parameters:
      baseType - The base aggregate to find all subtypes/implementors of
      Returns:
      List of AggregateSymbol instances extending or implementing the base type