This is an archive of the discontinued LLVM Phabricator instance.

Add a concept AST node.
ClosedPublic

Authored by massberg on Jul 20 2023, 9:30 AM.

Details

Summary

This patch adds a concept AST node (ConceptReference) and uses it at the corresponding places.

There are three objects that might have constraints via concepts:
TypeConstraint, ConceptSpecializationExpr and AutoTypeLoc.
The first two inherit from ConceptReference while the latter has
the information about a possible constraint directly stored in AutoTypeLocInfo. It would be nice if the concept information would be stored the same way in all three cases.

Moreover the current structure makes it difficult to deal with these concepts. For example in Clangd accessing the locations of constraints of a AutoTypeLoc can only be done with quite ugly hacks.

So we think that it makes sense to create a new AST node for such concepts.

In details we propose the following:

  • Make ConceptReference the new AST node.
  • TypeConstraint and ConceptSpecializationExpr do not longer inherit from ConceptReference but store a pointer to a ConceptReference.
  • AutoTypeLoc stores a pointer to ConceptReference instead of storing the concept info in AutoTypeLocInfo.

This patch implements a first version of this idea which compiles and where the existing tests pass.
To make this patch as small as possible we keep the existing member functions to access concept data. Later these can be replaced by directly calling the corresponding functions of the ConceptReferences.

Diff Detail

Event Timeline

massberg created this revision.Jul 20 2023, 9:30 AM
Herald added a project: Restricted Project. · View Herald Transcript
sammccall added inline comments.Jul 20 2023, 9:49 AM
clang/include/clang/AST/ASTConcept.h
248–282

FWIW clang doesn't seem to usually bother with const-correctness, so it's hardly even clear what it means.

I'd stick with ConceptLoc *getConceptLoc() const :-)

clang/lib/AST/ASTImporter.cpp
5666–5667

better to instead import via the TC->getConceptLoc(), and have a function to wrap up the import of the individual properties

5674

the templateKWLoc should be the import of the original constraint's conceptloc's templatekwloc

clang/lib/Sema/SemaTemplate.cpp
1274

From reading the code that currently initializes ConceptReference for a TypeConstraint, this is always SourceLocation{}.

Either this is not possible at the language level, or it's just not something the AST currently tracks.

clang/lib/Serialization/ASTReaderDecl.cpp
2630

again, this is correct, at least as correct as current code.
type constraints never have the template keyword, or it's never tracked

massberg updated this revision to Diff 544722.Jul 27 2023, 5:20 AM

AutoTypeLoc now uses ConceptLoc to store information of a concept instead of storing all information itself.

massberg added inline comments.Jul 27 2023, 5:27 AM
clang/include/clang/AST/TypeLoc.h
2154

I cannot replace this by SourceLocation() without failing tests, although this function should only be called if there are constraints.

2181

I assume that getLAngleLoc and getRAngleLoc should be moved to ConceptLoc, even if it currently only used by AutoTypeLoc?

2199–2202

I don't know why we need this here.
getArgLoc should only be called if there are constraints and in that case getConceptLoc() should be set.
However, we still run into this return. Note that ArgsInfo is only initialized in initializeLocal but never changed afterwards.

massberg updated this revision to Diff 545601.Jul 31 2023, 4:57 AM

Initial changes to RecursiveASTVisitor to traverse ConceptLocs.

massberg updated this revision to Diff 545640.Jul 31 2023, 7:04 AM

Add VisitConceptLoc.

massberg marked 2 inline comments as done.Jul 31 2023, 7:24 AM
massberg added inline comments.
clang/include/clang/AST/RecursiveASTVisitor.h
318

This is basically the old TraverseConceptReferenceHelper function. Is it by purpose that this isn't const in most other functions? Could the passes objects be changed in such functions?

clang/include/clang/AST/TypeLoc.h
2181

This might be accessible from `getConceptLoc()->getTemplateArgsAsWritten().

massberg updated this revision to Diff 545686.Jul 31 2023, 8:34 AM

Add readConceptLoc and AddConceptLoc functions.

massberg updated this revision to Diff 545690.Jul 31 2023, 8:48 AM

Code clean-up.

massberg updated this revision to Diff 546037.Aug 1 2023, 6:58 AM

Remove LAngleLoc and RAngleLoc from AutoTypeLocInfo and access thse location directly from the template args at thestored ConceptLoc.

massberg updated this revision to Diff 546040.Aug 1 2023, 7:02 AM

Fix typo.

massberg updated this revision to Diff 546054.Aug 1 2023, 7:27 AM

Some code simplification.

massberg retitled this revision from Prototype for concept AST nodes. to Add a concept AST node..Aug 1 2023, 7:48 AM
massberg edited the summary of this revision. (Show Details)

@erichkeane Hi Erich, we would like to add an AST node for concepts (see description above) and we are interested in your opinion on it.
This patch is a draft of what the new AST node could look like and how it would be part of the existing infrastructure.

massberg retitled this revision from Add a concept AST node. to Add a concept AST node..Aug 1 2023, 9:27 AM
massberg updated this revision to Diff 546094.Aug 1 2023, 9:31 AM

Create a patch from draft version.

massberg updated this revision to Diff 546339.Aug 2 2023, 12:18 AM

Updated comments.

hokein added a comment.Aug 2 2023, 1:01 AM

Thanks, this looks like in a good sharp, I left some comments.

I think it would be nice to get some high-level design input from @erichkeane before making further changes.

clang/include/clang/AST/ASTConcept.h
115

It would be nice to update this comment (for the other related classes, TypeConstraint), this is an important comment which helps reviewers easier understand the design principles of this change.

123

I'm not sure the ConceptLoc is a reasonable name for this structure.

  1. In general, classes named *Loc in clang AST are tiny, and they are passed by value, so seeing the usage ConceptLoc * in the code is a bit wired and inconsistent.
  2. Unlike other TemplateArgumentLoc, NestedNameSpecifierLoc, TypeLoc (where they all have TemplateArgument/TemplateArgumentLoc split), and we don't have a corresponding split for ConceptLoc.

I think 2) is probably fine, but 1) is a concern, we plan to make it a real AST node, so we will likely add it to the DynTypedNode, adding a big class there will increase the DynTypedNode a lot (from 40 bytes => 80 bytes).

One idea is to make this class ConceptLocInfo, and create a new wrapper class ConceptLoc wrapper which contains a ConceptLocInfo* pointer, and a ConceptDecl* concept.

clang/include/clang/AST/TypeLoc.h
2111

It looks like this is not necessary now, as we can reuse the TemplateArgument in ConceptLoc, maybe we can even remove it in the future

2111

just an idea, instead storing a ConceptLoc* in AutoTypeLoc, there is another approach (not sure it was considered before), which is to have a TypeConstraint* in the AutoType (and remove the ConceptDecl*).

This gives us a model following the grammar closely. type-constrains is used in the auto grammar rule, so it seems reasonable to have TypeConstraint in AutoType. The downside is that there is a lot of indirections: AutoTypeLoc -> AutoType -> TypeConstraint -> ConceptLoc vs AutoTypeLoc -> ConceptLoc.

2139

nit: if (const auto* Concept = getConcetLoc()), the same for the other places.

any reason why we need this null sanity check?

2154

is this comment still applied (you marked it done)? It seems reasonable to return a SourceLocation(), which tests were failed if we did this?

2202

which kind of tests were broken if we remove this?

massberg marked an inline comment as done.Aug 2 2023, 1:25 AM
massberg added inline comments.
clang/include/clang/AST/TypeLoc.h
2154

My original comment had become obsolete.

massberg marked an inline comment as done.EditedAug 2 2023, 2:36 AM

(removed comment)

massberg edited the summary of this revision. (Show Details)Aug 2 2023, 2:37 AM
massberg edited the summary of this revision. (Show Details)Aug 2 2023, 3:48 AM
massberg published this revision for review.Aug 2 2023, 3:53 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 2 2023, 3:53 AM
nridge added a subscriber: nridge.Aug 5 2023, 4:51 PM
massberg added a reviewer: Restricted Project.Aug 7 2023, 12:34 AM
cor3ntin added inline comments.
clang/include/clang/AST/ASTConcept.h
123

Agreed, the name change seems more confusing than anything and not really consistent with preexisting names.
It is still unclear to me what is wrong with the current name (and all these renamings obfuscate what the patch is actually trying to do)

massberg updated this revision to Diff 547804.Aug 7 2023, 8:31 AM
massberg edited the summary of this revision. (Show Details)

Rename ConceptLoc back to ConceptReference.

massberg edited the summary of this revision. (Show Details)Aug 7 2023, 8:32 AM
massberg marked an inline comment as done.
massberg added inline comments.
clang/include/clang/AST/ASTConcept.h
123

I'm sorry if the renaming led to confusions. I have renamed it back to ConceptReference for now. I'm happy for any proposals for a good name (or to keep the old name).

adding @aaron.ballman, who might have opinion on this.

cor3ntin added inline comments.Aug 9 2023, 12:39 AM
clang/include/clang/AST/ExprConcepts.h
145–146

Should there be a getLocation() method on ConceptReference ? It seems useful. maybe even a getSourceRange() method too

clang/lib/Serialization/ASTWriter.cpp
472–484

I tink it would be better to only call AddConceptReference with non null parameters, and save in the parents whether there is a concept reference or not

massberg updated this revision to Diff 549066.Aug 10 2023, 9:04 AM
massberg marked an inline comment as done.

Only call AddConceptReference if there is a concept reference.

(There are still outstanding comments e.g. in ASTImport)

I think it would be useful to add to the patch description:

  • the current deficiencies of ConceptReference that make it not a well-behaved AST node now
  • which of these are addressed in this patch (RecursiveASTVisitor, use in all relevant places, avoiding multiple inheritance)
  • which of these will be addressed in future patches (DynTypedNode, maybe text-dumper?)
clang/include/clang/AST/ASTConcept.h
111–112

Doc comment is out of date. Suggestion:

/// A reference to a concept and its template args, as it appears in the code.
///
/// Examples:
///   template <int X> requires is_even<X> int half = X/2;
///                             ~~~~~~~~~~ (in ConceptSpecializationExpr)
///
///   std::input_iterator auto I = Container.begin();
///   ~~~~~~~~~~~~~~~~~~~ (in AutoTypeLoc)
///
///   template <std::derives_from<Expr> T> void dump();
///             ~~~~~~~~~~~~~~~~~~~~~~~ (in TemplateTypeParmDecl)
149

this constructor should now be private, like other AST nodes

156–157

following the pattern for other AST nodes, this constructor should be private or gone. If deserialization needs to create an empty ConceptReference, provide a CreateEmpty() factory

220–229

We're not really changing this class, but I think it could use a doc comment as its relationship to ConceptReference, TemplateTypeParmType, and AutoTypeLoc wasn't all that clear. Suggestion:

/// Models the abbreviated syntax to constrain a template type parameter:
///   template <convertible_to<string> T> void print(T object);
///             ~~~~~~~~~~~~~~~~~~~~~~
/// Semantically, this adds an "immediately-declared constraint" with extra arg:
///    requires convertible_to<T, string>
///
/// In the C++ grammar, a type-constraint is also used for auto types:
///    convertible_to<string> auto X = ...;
/// We do *not* model these as TypeConstraints, but AutoType(Loc) directly.
clang/include/clang/AST/ExprConcepts.h
90

incomplete comment: "to prevent" what?

Also FWIW I don't think *all* uses should be migrated, e.g. getNamedConcept() is fundamental enough to be exposed here even if it's implemented via ConceptReference.

145–146

agree, though we actually shouldn't call ConceptReference::getLocation() method here because primary location != start location.

I think

  • ConceptReference::getLocation() should return getConceptNameLoc() (just an alias)
  • ConceptSpecializationExpr::getExprLoc() should return ConceptReference::getLocation()
  • ConceptReference::getBeginLoc() should contain this logic, ConceptSpecializationExpr::getBeginLoc() should return it
  • ditto end loc
  • ConceptReference::getSourceRange() is a useful helper
  • ConceptSpecializationExpr already has getSourceRange() inherited from Stmt
clang/include/clang/AST/RecursiveASTVisitor.h
318

It's somewhere between intended and awkward historical baggage: most RAVs don't mutate the nodes, but some do.

I suggest making this take a mutable pointer (rather than the more natural const reference) purely for consistency - RAV is confusing enough as it is.

2517

I think this should be guarded by if (!getDerived().shouldTraversePostOrder()), and then the opposite at the end

clang/include/clang/AST/TypeLoc.h
2111

I did look at this. Maybe it's a good idea, but it's not simple and it's mostly independent of the change in this patch.

The thing that TypeConstraint concretely adds to ConceptReference is the immediately-declared-constraint.
Today this constrains the TypeParmType and semantic analysis can treat it as a separate constraint: void foo(Iterator auto x) is equivalent to template<class T> void foo(T x) requires Iterator<T> or so.
However this formulation isn't convenient for placeholder types: Iterator auto x = ... isn't a template, there's no code processing requirements where we can tack on requires Iterator<auto>. It also doesn't clearly represent the idea that the two auto placeholders should be the same.

I agree it would be nice to follow the grammar (or if not, use different names) but I think that it's a separate change, and going from AutoTypeLoc{ConceptNameLoc etc} to AutoTypeLoc{ConceptReference{ConceptNameLocEtc}} is a useful stepping-stone to AutoTypeLoc{TypeConstraint{ConceptReference{ConceptNameLoc etc}}}

2139

Agree with the style change.

We need the check because there may be no constraining concept here: auto x = 2 should return an empty NNSLoc, not crash

2199–2202

I think this FIXME should be addressed before landing this patch.

Currently the code (apparently) stores two copies of the args: one as trailing objects here and one in the conceptreference.

Ideally we'd remove the trailing objects immediately. A FIXME to do so later is fine if needed, but if they're inconsistent then we know one of them has a bug, or we don't really understand the design.

These can lead to downstream bugs now, and also make it less likely such a FIXME will ever be cleaned up.

clang/lib/Sema/TreeTransform.h
6856

fix/remove commented-out code?

massberg updated this revision to Diff 552307.Aug 22 2023, 4:13 AM

Resolve some of the reviewer's comments.

massberg marked 13 inline comments as done.Aug 22 2023, 4:19 AM

I have resolved some of the comments, but I need another round to finish all of the, Thanks to all reviewers so far!

clang/include/clang/AST/ExprConcepts.h
90

I have updated the FIXME.

clang/include/clang/AST/TypeLoc.h
2202

This is fixed now

massberg marked 2 inline comments as done.Aug 22 2023, 4:23 AM
massberg added inline comments.
clang/lib/Sema/TreeTransform.h
6829–6841

This is very ugly as I have to create the TALI and TAL arrays temporarily to use the existing transformations.
Is there a better way to do that?
Moreover, is this the correct place for the transformation? This is necessary as the passed AutoTypeLoc doesn't have an attached ConceptReference even if it is constrained. Has the ConceptReferenecof the original AutoTypeLoc be added somewhere earlier?

sammccall added inline comments.Aug 22 2023, 5:04 AM
clang/lib/Sema/TreeTransform.h
6829–6841

If I'm understanding the situation right...
the AutoTypeLoc in the template should have a ConceptReference, since the auto is constrained.
This seems like a bug to be fixed elsewhere, and then this else becomes dead.

Do you have a minimal example?

Hi! I was away on vacation, so I didn't get a chance to take a look at this. I'm currently digging my way through my 'back to work' tasks, but will keep this on my list of things to review ASAP.

So I did a quick run through, I think this is a fine idea and an improvement. However, @sammccall has given some very good feedback that I'd like to have him do the final approval.

clang/include/clang/AST/ASTConcept.h
233

Preference to name this something like ConceptRef instead of CR here.

clang/include/clang/AST/ExprConcepts.h
49

Same comment here.

150–154

What did you find that resulted in this change? What does hasExplicitTemplateArgs 'mean' when we have empty arguments, so something like:

template<UnaryConcept<> C>
void foo(const C&){}

Basically, the end loc should ALWAYS be the right-angle if it exists, right?

massberg updated this revision to Diff 552742.Aug 23 2023, 8:51 AM
massberg marked 4 inline comments as done.

Resolved the next round of comments. There are still some left to be addressed.

massberg marked 3 inline comments as done.Aug 23 2023, 8:53 AM
sammccall added inline comments.Aug 29 2023, 2:56 AM
clang/lib/AST/TypeLoc.cpp
625–647

static

massberg updated this revision to Diff 554257.Aug 29 2023, 4:18 AM
massberg marked 7 inline comments as done.

Resolve more of the open comments.

  • add getBeginLoc(), getEndLoc() and getSourceRange() to ConceptReference and updated corresponding functions in ConceptSpecializationExpr
  • additional fixed getBeginLoc() to work correctly with empty argument lists
  • remove const from parameters of TraverseConceptReference() and VisitConceptReference()

still missing:

  • Add tests for new location functions
  • Investigation why we have to create a ConceptReference in initializeLocal() which looks not right
  • Update patch description.

OK, so I learned a bit about initializeLocal/trivial TypeSourceInfo. Mostly things I didn't want to know :-)
TL;DR I think the current version of the patch is right.

The crash is caused by:

  1. CheckTemplateArgument calls SubstType without passing a TypeLoc, which synthesizes a trivial TypeSourceInfo to instantiate
  2. the trivial TypeSourceInfo never has a ConceptReference
  3. instantiating an AutoTypeLoc where the type is constrained but there's no ConceptReference is not supported

We can choose to address any of these.

Fixing #1 is tempting: the SubstType overload with no TypeLoc is deprecated and calling it ~always loses information. Cleaning up this call is an improvement, but there are ~15 calls to this overload, and probably more places that use trivial TypeSourceInfo.
So this is nice to have, but I think leaves us with an AST that will still crash in other cases. Consumers will not expect an AutoTypeLoc where the type is constrained but the loc isn't, and it's hard to know how to handle this case.

Fixing #2 is what this patch currently does. It also seems to be the pattern used by other types (their initializeLocal methods conditionally initialize structure based on the underlying type). The only possible downside is because we store the ConceptReference subobject by pointer and support replacement but not mutation, if the caller calls initializeLocal and then fills in with real data we'll waste the original ConceptReference object. Still, I don't think this is how non-trivial TSIs are generally created, and I think this is the way to go.

Fixing #3 is the previous version of the patch, again it leaves us with a bug-prone AST and some extra complexity.

clang/include/clang/AST/ASTConcept.h
183

if the qualifier is null the template KW must also be null
so this is correct, you may or may not want a comment for that! up to you

188

getTemplateArgsAsWritten() is nullable, right?

217

nit: printingpolicy by const ref, I think
(we're not totally consistent, but I think ref is more common)

massberg updated this revision to Diff 554660.Aug 30 2023, 3:43 AM
massberg marked 3 inline comments as done.

Resolve remaining comments.

  • Added tests for new location functions of ConceptReference. There is an existing bug with the end location if there are no template arguments. As it is an existing bug I have added a FIXME which will be fixed in a follow up patch.
  • Additional minor changes.
massberg added inline comments.Aug 30 2023, 4:07 AM
clang/lib/Sema/TreeTransform.h
6829–6841

A minimal example:

template <typename T> concept C = true;

template<C auto M>
void foo2() {}

int main(void) {
  foo2<1>();
}

As discussed, a ConceptReference will now be created in initializeLocal so that it is guaranteed that we have it available here. I have added an assert to verify that there is an ConceptReference in case that the AutoType is constrained.
If we do not set the ConceptReference in initializeLocal then there are already several tests that fail as the assert isn't satisifed.

sammccall accepted this revision.Aug 30 2023, 8:03 AM

LGTM, just nits!

The SourceRanges are actually correct :-)

clang/include/clang/AST/ASTConcept.h
124

remove protected (and private: below), we don't inherit from this

clang/include/clang/AST/ExprConcepts.h
46

while here: this is unused, remove?

48

while here: this class is final, so these can be private instead of protected

clang/lib/AST/TypeLoc.cpp
625

nit: createTrivialConceptReference?
hinting at the relationship to trivial TypeSourceInfo

maybe a comment too?

// Builds a ConceptReference where all locations point at the same token,
// for use in trivial TypeSourceInfo for constrained AutoType
clang/unittests/AST/SourceLocationTest.cpp
1025

why that range?
SourceRanges are generally "closed token ranges", so the endpoint is the *beginning* of the last token *in* the range.
CCC is (2, 1, 2, 1)

1073

as above

This revision is now accepted and ready to land.Aug 30 2023, 8:03 AM
massberg updated this revision to Diff 554743.Aug 30 2023, 8:43 AM
massberg marked 7 inline comments as done.

Fixed remaining nits. Thanks for the reviews and comments everyone!

This revision was landed with ongoing or failed builds.Aug 31 2023, 1:38 AM
This revision was automatically updated to reflect the committed changes.