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.
- Implementation Considerations
- Implementation Structure
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.
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
- 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
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.
the ConceptMapDecl class also extends LLVM's
class, for unique
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
For restricted scopes, we simply add an additional scope flag in the
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:
The exceptions to this name lookup deviation are:
- 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
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
- all outer template parameter scopes, specified with the
- name lookup for non-dependent call expressions,
- name lookup for references to constrained templates, and
- prior encounter of latecheck scopes.
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
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
When optionally parsing scope specifiers, via
the implementation of
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
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
- 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:
- to satisfy the constraints on the concept map template, given the
generated concept model's arguments, and
- 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