ConceptClang: The Compilation Model


Introduction

The ConceptClang infrastructure is centered around the following main constituants of generic programming with concepts, each by some varying degree of support depending on the selected design for concepts:
  • concept definitions,
  • concept model specifications,
    • some of which can be templated,
  • constrained template definitions,
  • constrained template specializations' checking,
    • which consists of constraints satisfaction after normal type checking, and
  • constrained template instantiations.

In addition to the above, we consider an extension of function overloading: concepts-based overloading.
This deals with maintainning support for adhoc-polymorphism in the presence of concepts.

  1. Implementation Considerations
  2. Implementation Structure


Implementation Considerations

Representations of concept definitions and models need to collect listings of requirements (and specifications of requirements), as well as facilitate their parsing.
Constrained template definitions need to be checked against the constraints environments that they are associated to.
In addition, each specialization of a constrained template needs to be checked against its constraints environment, via execution of some constraints satisfaction procedure.
The constraints satisfaction procedure is executed during template argument deduction -- for overload resolution, and results in a listing of models satisfying the constraints for the type of the specialization.

During the execution of all the above, and as necessary, the appropriate values must be conserved and passed around for proper instantiation of the constrained templates, which often occurs much later in the compilation process, e.g. at the end of the translation unit.
For instance, references to entities that are associated to concepts, e.g. constructed during the checking of constrained template definitions, must be reconstructed to link to corresponding model specifications in the result of the earlier execution of the constraints satisfaction procedure.

For concept-based overloading, constraints environments must be effectively compared against oneanother, and template specializations necessitate that we specify the correct ordering mechanisms to use when the partial ordering of template specializations meets that of constraints.


Implementation Structure

Our extension of the Clang compilation engine consists of three main components:
The semantic analysis components is, in turn, organized under 6 main subcomponents: 1 general and 5 more specialized. The specialized components focus of implementations directly affecting:
  • the creation of new instances of data structures,
  • references to entities associated with concepts,
  • name lookup,
  • typechecking, substitutions and instantiations of entities, and
  • template argument deduction, for concepts-based overloading.

The Data Structures

As extension of
Clang, we define two data structures to represent concept definitions and concept model specifications: the classes ConceptDecl and ConceptMapDecl, respecfully. Both these classes extend TemplateDecl and DeclContext, treating the representations as extensions of template declarations and declaration contexts. Hence, both ConceptDecl and ConceptMapDecl hold, as declarations, representations of associated requirements and specifications; and have a scope associated with them, to facilitate their parsing.
In addition, the ConceptMapDecl class also extends LLVM's FoldingSetNode class, for unique identification purposes. Further, each ConceptDecl object holds a list of pointers to ConceptMapDecl objects, representing all existing models for each given concept; and ConceptMapDecl objects are not visible by name lookup.

To complete the representations necessary for our model, we introduce more generic forms of the notions of concept model archetypes and restricted scope.

Concept model archetypes are simply fake concept models with minimal specification. We take this definition literally and represent them with the ConceptMapDecl class. However, in this special case, ConceptMapDecl simply holds substituted versions of requirements in the concepts mapped by the archetypes.
This representation of concept map archetypes is used to represent constraints in constrained templates, concept refinements, associated requirements, and as placeholders for concrete concept models when checking concept model templates.

For restricted scopes, we simply add an additional scope flag in the Scope class: RestrictedScope. Each encounter of the requires keyword immediately sets that flag on the surrounding scope, which is most likely to be a template parameter scope, dictating:

  • that constraints to be parsed in must be collected in the associated scope, and
  • that, with some exceptions, name lookup that reaches this scope must abandon its normal lookup path and deviate to the constraints in the associated constraints environment.
The exceptions to this name lookup deviation are:
  • all outer template parameter scopes, specified with the TemplateParmScope flag,
  • name lookup for non-dependent call expressions,
  • name lookup for references to constrained templates, and
  • prior encounter of latecheck scopes.
The RestrictedScope flag is also set on the scopes associated with ConceptDecl and ConceptMapDecl objects, to facilitate parsing while looking up names in concepts refinements, or associated requirements, or their corresponding maps. However, additional flags are necessary to allow name lookup to continue its normal lookup path, regardless of the RestrictedScope setting, so that concept definitions and concept model specifications can pick up implementations from the surrounding scope as well. Respectively, those flags are ConceptDefnScope and ConceptMapScope.

There are several other data structures that are added or extended in a fashion similar to the above. We reserve their description for the upcoming documentation.

The Parser Engine

The parsing of entities related to concepts is rather straighforward, mostly reusing Clang implementation. We simply need to make sure that components are parsed into the right data structures, via calls to semantic analysis engine procedures, and that the right flags are set up.

That is, for parsing template type parameters while parsing the body of concept definitions, e.g. in the pre-Frankfurt design, we might want to allow the shadowing of the type parameters when a concept is allowed to override the default implementation of an associated type of one of its refinements.

When parsing constraints after a requires keyword is encountered, the same storage of the constraints environment in the surrounding Scope, is shared with the list of template parameters in the enclosing template declaration.

When optionally parsing scope specifiers, via ParseExprCXX.cpp's ParseOptionalCXXScopeSpecifier(), the implementation of isTemplateName() and TemplateNameKind must be extended to specify results specific to concepts, which triggers special care.

Most notably, the parsing of call expressions, necessitates special care, since the failure of parsing a name as associated to a concept might mean that the name refers to an existing constrained template. In other words. when the previous lookup within the restricted scope fails, the calling context information must be updated, with a repeat of name lookup in the parent of the outermost restricted scope.

Lastly, new types of diagnoses necessitate the extension of the parser diagnostics in the include file Basic/DiagnosticParseKinds.td.

The Semantic Analysis Engine

The semantic analysis component is the most demanding of all, as it controls the instantiation of objects necessary for the completion of our model. Overall, it handles the checking of concept model specifications, the constraints satisfaction, the reconstruction of references to entities associated to concepts for constrained templates instantiation, and another array of functions.

Notably, we end up with two vastly reusable and mutually recursive procedures: constraints satisfaction and concept model checking.

Constraints satisfaction takes in a list of template type parameters, the constraints on those parameters, and a list of template type arguments, and attempts to satisfy all the constraints on the parameters based the arguments.
The satisfaction of a constraint, in this case, consists of finding an appropriate concept model. When the model is not found, one is automatically generated if:

  • the model maps an implicit concept and implicit concepts is supported, or
  • as instructed by concept model checking.

For a given concept model, concept model checking attempts to satisfy all the requirements in the concept mapped by the concept model. It succeeds only when all requirements are satisfied.
The satisfaction of most kinds of requirements may vary from one design to the other. However, the satisfaction of refinements is the same accross all designs and is nothing but constraints satisfaction between the concept model arguments and the concept parameters of the mapped concept.
During this particular constraints satisfaction, concept map checking allows the implicit generation of concept models whenever necessary.

When the concept model is an archetype, instead of satisfying the requirements from the mapped mapped, concept model checking simply substitutes its types into the requirements of the mapped concept, and copies the substituted forms over to the concept model archetype.

When the concept model is templated, concept model checking instructs constraints satisfaction to generate concept model archetypes as placeholders for concrete concept models, whenever the satisfaction of a refinement requires a concept model whose arguments are dependent on the template parameters of the concept model template.

The above mutual recursion also shapes the generation of concept models from concept model templates, which reuses constraints satisfaction in two folds:

  1. to satisfy the constraints on the concept map template, given the generated concept model's arguments, and
  2. to fill in "placeholder" concept models with concept models from the result of satisfying the constraints on the concept map template.

Another notable function is the extension of the SFINAE property to constraints satisfaction failure. Inevitably, the data structures component of our model has also been extended with respect to this.

Lastly, similarly to the parsing engine, new types of diagnoses necessitate the extension of the sema diagnostics in the include file Basic/DiagnosticSemaKinds.td.