[Chapel Merge] compiler/next: adding function resolution

Branch: refs/heads/main
Revision: 32dd29e
Author: mppf
Log Message:

Merge pull request #18122 from mppf/resolve-uast

compiler/next: adding function resolution

This PR adds function resolution to compiler/next.

Generally speaking, when there is an ordering constraint between
different operations (e.g. scope resolution to occur before type
resolution), there are two ways to handle it with the query framework:

  1. One query calls another query
  2. A query uses a data type that can only be produced by another
    operation that it depends upon The new resolution code uses approach
    (2) in several cases.

The main scope resolution functions and queries are declared in
scope-queries.h. These include an idea of a ResolvedVisibilityScope,
where what a use/import refers to is figured out. These are figured out
as-needed when lookupInScope and related functions are called.

The main (Function) resolution functions and queries are declared in
resolution-queries.h. These queries interact with the following types
declared in resolution-types.h:

  • QualifiedType - a Type as well as a Kind (think var / const /
    in etc) and Param values, if any
  • ResolvedExpression - combines QualifiedType along with information
    about which NamedDecl / Functions an expression refers to
  • ResolutionResultByPostorderID - stores a ResolvedExpression for
    every Expression contained in a symbol
  • UntypedFnSignature - stores only the function signature parts of a
    Function before any resolution is done - so it is mainly just a list
    of formals. This type exists so that, in incremental compilation, a
    choice of which function to call will not depend on the body of that
    function. (Where generally we have the property that changing
    something within an AST element will cause a new pointer to be made
    for it).
  • TypedFnSignature - stores a function signature along with some type
    information. A TypedFnSignature can represent a generic function
    with the generic types resolved. Or it can represent an
    instantiation of a generic function. Either way, this type is only
    talking about the function signature (formals and where clause) and
    does not consider anything about return type or body of the
    function.
  • ResolvedFunction - this type represents a fully resolved function
    including the function body. If it is a generic function, it must be
    an instantiation.

Function resolution proceeds in this general flow:

  • resolveModule is the normal entry point to drive the process
  • to resolve an expression to produce a ResolvedExpression:
    • if it is a Dot or Identifier, do scope resolution to figure out
      what it refers to
    • if it is a Call, perform call resolution, including finding
      candidates and instantiating
    • Either way, these details are handled in the implementation by the
      Resolver visitor

Call resolution is handled by resolveCall. It is relatively complex and
consists of several stages:

  • First, lookupCalledExpr gathers visible functions
  • Then, filterCandidatesInitial uses the list of visible functions to
    establish the list of possibly-generic functions (before
    instantiation) that are candidates. To do so, establish the initial
    type signatures for each candidate - that is, figure out what the
    possibly-generic types in the signature refer to without
    instantiating. Since this is done in the query framework, the result
    here is cached, so it will be reused if the same function is a
    candidate for another call.
  • Then, filterCandidatesInstantiating uses the list of
    possibly-generic candidates to produce a list of concrete or
    instantiated functions that are candidates. To do so, perform
    instantiation for any function signatures for candidates that are
    generic.

The above steps are completed first in the scope of the Call and repeated
for each point-of-instantiation until candidates are found. (See
PRs #16158 and #16279 for a history of this behavior in the production
compiler).

Point-of-instantiation is tracked primarily by passing a PoiScope to the
Resolver visitor and to key functions such as resolveCall. However
instantiation caching uses two different strategies:

  • for TypedFnSignature, these are unique'd by their contents (e.g.
    formal types etc) since these are generally small
  • for ResolvedFunction, these are first checked according to PoiInfo
    (which in the future will follow the strategy in #16261 by having the
    hashtable hash-code based on the function signature but the == checks
    use the POI information). Once the function is resolved, we can be
    comprehensive about unique-ifying to ensure correct reuse of
    instantiations and we do that by storing the ResolvedFunctions in a
    map with a key including the signature and also {set of (Call ID, resolution result ID) for calls that came from the Point of Instantiation}.

Besides adding function resolution, this PR makes the following
supporting changes:

  • Adjusted Context to include an error overload accepting a typed
    function signature.
  • Adjusted QUERY_STORE_RESULT to only store the first result if called
    multiple times within a single revision. That addresses a memory
    manegement error with one of the ResolvedFunction hashtables described
    above.
  • Added hash function for std::pair
  • renamed the query poiScope to pointOfInstantiationScope since the
    1st name collides with the obvious variable name
  • implement PoiInfo::canReuse similarly to PR #16261

Future Work:

  • adjust many of the new types to be better engineered e.g. with
    accessor methods and private fields.
  • make production-quality error messages
  • implement real logic for canPass etc
  • handle varargs functions
  • make sure we get a reasonable error for naming the same argument twice
    in a call
  • describe the flow of resolution (e.g. with the contents of this PR
    message) in a comment at the top of the resolver implementation

Reviewed by @stonea @lydia-duncan and @e-kayrakli - thanks!

  • [x] full local testing

    Modified Files:
    A compiler/next/test/resolution/testPoi.cpp
    M compiler/next/include/chpl/queries/Context.h
    M compiler/next/include/chpl/queries/query-impl.h
    M compiler/next/include/chpl/resolution/resolution-queries.h
    M compiler/next/include/chpl/resolution/resolution-types.h
    M compiler/next/include/chpl/resolution/scope-queries.h
    M compiler/next/include/chpl/resolution/scope-types.h
    M compiler/next/include/chpl/util/hash.h
    M compiler/next/lib/queries/Context.cpp
    M compiler/next/lib/resolution/resolution-queries.cpp
    M compiler/next/lib/resolution/resolution-types.cpp
    M compiler/next/lib/resolution/scope-queries.cpp
    M compiler/next/lib/types/QualifiedType.cpp
    M compiler/next/lib/uast/Builder.cpp
    M compiler/next/test/resolution/CMakeLists.txt
    M compiler/next/test/resolution/testInteractive.cpp
    M compiler/next/test/resolution/testResolve.cpp

    Compare: Comparing 2e29e4a15346...32dd29e6af43 · chapel-lang/chapel · GitHub