[Chapel Merge] compiler/next: recursive type construction

Branch: refs/heads/main
Revision: 499bd05
Author: mppf
Link: Unavailable
Log Message:

Merge pull request #19109 from mppf/recursive-type-construction

compiler/next: recursive type construction

Closes https://github.com/Cray/chapel-private/issues/2836

This PR enables the compiler/next resolver to work with recursive types,
such as this:

class C {
  var next: owned C;

Initially, I attempted to use the query system's partial result to update
a Type* containing the fields. However I could not get that to work.
The problem is that a Type* can be stored in any number of other
queries, so we can't change the pointer; and these other queries will
assume that it exists and make decisions based upon it. After struggling
with this for a while, I looked at what the Rust compiler does for this
(since the query system we have is inspired by the Rust compiler). In the
Rust compiler the representation of a type does not include the fields.
(For generic types, it does include the substitutions). So, this PR
changes the compiler/next resolver to store the resolved fields
separately from the type. That had a number of knock-on effects, which
made this PR bigger than is ideal for a PR. However, it did allow me to
get the recursive types working.

  • It is not currently possible to know if a CompositeType* represents a
    generic type from that pointer alone since it no longer has knowledge
    of the fields. Instead, we have the query getTypeGenericity to
    compute whether a type generic. I opened #19120 to ask if the language
    design in this area is what we want. If it becomes something we can
    compute from the uAST alone then we can put the generic-ness
    information back into CompositeType*.
  • functions supporting canPass now accept a context argument so that
    they can call getTypeGenericity
  • we now have the fieldsForTypeDecl query which returns a
    ResolvedFields. The ResolvedFields is a bit like
    ResolutionResultByPostorderID in that it is built up as the fields
    are resolved. If a fieldsForTypeDecl is recursively invoked, it can
    return a partial result that is missing some fields. I am expecting
    cases that rely on not-yet-computed field types to errors.
    ResolvedFields itself is based upon what was in
  • moved the SubstitutionsMap definition to CompositeType since now
    these need to store substitutions.
  • Changed the Type* hierarchy to have Type::Genericity, an enum
    indicating the various generic-ness statuses (namely: concrete,
    generic, generic with defaults, or unknown genericity) and changed
    isGeneric to genericity to return these. Note that a record/class
    type will return unknown genericity to indicate that
    getTypeGenericity should be called to compute it.
  • Changed the CompositeType* hierarchy to include substitutions
  • Adjusted QualifiedType to have clearer helpers for computing the
    genericity of a type.

Small changes I did while working on this:

  • added a str method to ID to make it easier to debug - in
    particular I can add code like if (something->id().str() == "M@f@12") gdbShouldBreakHere().
  • added idIsClass to UntypedFnSignature to reduce the need for
    looking up the uAST for the ID just in order to know if we need to
    wrap the result of type construction in a ClassType.
  • Changed SubstitutionsMap from const Decl* keys to ID on the
    argument that these are more likely to be preserved between
    compilation. I thought also that we might be able to fabricate IDs for
    the tuple fields, but handling tuples is still future work, so we
    might go another way on that point.
  • better factored the code constructing class/record types and computing
    field types in resolution-queries.cpp
  • I had added a mechanism to check if two potentially recursive types
    match. However, this should no longer be necessary since any Type*
    stored in a Type will have already been returned by a query (and so
    should contain the existing result if nothing changed). So, this code
    for comparing potentially recursive type is just saved in the commit
    history. If it is needed in the future, look for MatchAssumptions
    and the test testRecursiveTypeMatch.cpp.

Reviewed by @dlongnecke-cray - thanks!

Modified Files:
M compiler/next/include/chpl/queries/ID.h

M compiler/next/include/chpl/resolution/can-pass.h
M compiler/next/include/chpl/resolution/resolution-queries.h
M compiler/next/include/chpl/resolution/resolution-types.h
M compiler/next/include/chpl/types/AnyType.h
M compiler/next/include/chpl/types/BasicClassType.h
M compiler/next/include/chpl/types/BuiltinType.h
M compiler/next/include/chpl/types/BytesType.h
M compiler/next/include/chpl/types/CStringType.h
M compiler/next/include/chpl/types/ClassType.h
M compiler/next/include/chpl/types/CompositeType.h
M compiler/next/include/chpl/types/ErroneousType.h
M compiler/next/include/chpl/types/NilType.h
M compiler/next/include/chpl/types/NothingType.h
M compiler/next/include/chpl/types/PrimitiveType.h
M compiler/next/include/chpl/types/QualifiedType.h
M compiler/next/include/chpl/types/RecordType.h
M compiler/next/include/chpl/types/StringType.h
M compiler/next/include/chpl/types/TupleType.h
M compiler/next/include/chpl/types/Type.h
M compiler/next/include/chpl/types/UnionType.h
M compiler/next/include/chpl/types/UnknownType.h
M compiler/next/include/chpl/types/VoidType.h
M compiler/next/include/chpl/uast/TupleDecl.h
M compiler/next/lib/queries/ID.cpp
M compiler/next/lib/resolution/can-pass.cpp
M compiler/next/lib/resolution/resolution-queries.cpp
M compiler/next/lib/resolution/resolution-types.cpp
M compiler/next/lib/types/BasicClassType.cpp
M compiler/next/lib/types/CompositeType.cpp
M compiler/next/lib/types/QualifiedType.cpp
M compiler/next/lib/types/RecordType.cpp
M compiler/next/lib/types/TupleType.cpp
M compiler/next/lib/types/Type.cpp
M compiler/next/lib/types/UnionType.cpp
M compiler/next/test/resolution/testCanPass.cpp
M compiler/next/test/resolution/testResolve.cpp
M compiler/next/test/resolution/testTypeConstruction.cpp

Compare: https://github.com/chapel-lang/chapel/compare/8ec16faaa614...499bd05bb6cb