This is an archive of the discontinued LLVM Phabricator instance.

[AST] Refactor propagation of dependency bits. NFC
ClosedPublic

Authored by hokein on Dec 27 2019, 1:22 AM.

Details

Summary

This changes introduces an enum to represent dependencies as a bitmask
and extract common patterns from code that computes dependency bits into
helper functions.

Diff Detail

Event Timeline

ilya-biryukov created this revision.Dec 27 2019, 1:22 AM
Herald added a reviewer: shafik. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript

@rsmith, could you please take a look and let me know whether you think adding a new type for this makes sense?

On one hand, I feel it's good to have a type to represent "dependencies" and it allow to write helper functions and easily add new bits into the dependencies without rewriting all the code propagating those flags (error bit).

OTOH, using this for some things might be confusing:

  • a type cannot be value-dependent, but dependency flags allow for that.
  • a template argument can currently be "dependent" after can be either type- or value-dependent, also confusing.
  • ...

Note there are still some rough edges here, see the added FIXMEs.

Also note that this change does not move any code around to make sure this change is easy to review and validate that the code is doing the same thing.
I'm also planning to move all the code that computes dependencies into one place (it's currently scattered around many files and it certainly makes it quite hard to find bugs in the code and update it). But I would really like to get everyone aligned on the direction we're taking here.

ilya-biryukov marked an inline comment as done.Dec 27 2019, 1:33 AM
ilya-biryukov added inline comments.
clang-tools-extra/clang-tidy/hicpp/ExceptionBaseclassCheck.cpp
17 ↗(On Diff #235397)
NOTE: We need this to fix compiler errors down below. There's an AST matcher called isTypeDependent and we add a function clang::isTypeDependent(DependencyFlags) in this change.

Overload resolution does its job, but we have to make sure they're in the same namespace, so we need to put using namespace somewhere inside the clang namespace.

Unit tests: pass. 61128 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

I like the goal of this patch and the simplifications it does. I don't feel qualified to do a full review.

clang/include/clang/AST/Expr.h
126

Just curious why do you prefer D = D | DependencyFlags::Type; over D |= DependencyFlags::Type; ? The latter seems to be more common.

clang/include/clang/AST/Stmt.h
323

Please use enum { NumExprBits = NumStmtBits + 5 + DependencyFlagsBits }; to avoid bugs when the size changes.

  • Use DependencyFlagsBits for computing NumExprBits
  • Reformat
ilya-biryukov marked 4 inline comments as done.Jan 2 2020, 2:10 AM
ilya-biryukov added inline comments.
clang/include/clang/AST/Expr.h
126

Would also prefer D |=, but it leads to compilation errors.

The builtin operator |= accepts ints and, therefore, fails on strongly-typed enums.
And, AFAIK, there's no way to redefine operator |= for non-class types.

clang/include/clang/AST/Stmt.h
323

Many thanks! Using it here was the reason I wanted to add the constant in the first place. Ended up forgetting about it.
Thanks!

Unit tests: pass. 61158 tests passed, 0 failed and 728 were skipped.

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

riccibruno added inline comments.Jan 2 2020, 7:39 AM
clang/include/clang/AST/Expr.h
126

You certainly can define a compound assignment operator for an enumeration type. It is only non-compound-assignment that is special cased and required to be a member function.

Example: https://godbolt.org/z/JV5uPw

134

You may want to add an assertion here to make sure that no truncation occurred.

clang/lib/Serialization/ASTReaderStmt.cpp
531

I think it would be nicer to add an abbreviation for the right number of bits (using DependencyFlagsBits) and as you say just serialize/deserialize all the flags in one go.

ilya-biryukov marked 4 inline comments as done.Jan 2 2020, 8:06 AM
ilya-biryukov added inline comments.
clang/include/clang/AST/Expr.h
126

Ah, thanks! So it turns out I was wrong. Will update the patch.

clang/lib/Serialization/ASTReaderStmt.cpp
531

Will do this in a follow-up.
That would be a functional change, I'm aiming to keep this one an NFC.

martong resigned from this revision.Jan 7 2020, 7:37 AM

@rsmith, gentle ping. WDYT? Is this a step in the right direction?

  • Add compound assignment operations

Unit tests: pass. 61745 tests passed, 0 failed and 780 were skipped.

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

  • Use DependencyFlags for TemplateName and NestedNameSpecifier

Unit tests: fail. 61841 tests passed, 5 failed and 780 were skipped.

failed: libc++.std/language_support/cmp/cmp_partialord/partialord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongeq/cmp.strongeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongord/strongord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakeq/cmp.weakeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakord/weakord.pass.cpp

clang-tidy: pass.

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

I don't like the name getDependencies, because the function is not getting a list of dependencies, it's getting flags that indicate whether certain properties of the construct are dependent. Maybe getDependence or getDependenceFlags would be a better name? Likewise, instead of addDependencies, perhaps addDependence?

clang/include/clang/AST/DependencyFlags.h
18–29

Hmm. We have a different set of propagated flags for types (dependent / instantiation dependent / unexpanded pack / variably-modified) and for (eg) template arguments and nested name specifiers (dependent / instantiation dependent / unexpanded pack). It would be nice to use the same machinery everywhere without introducing the possibility of meaningless states and giving the wrong names to some states.

I think we should aim for something more type-safe than this: use a different type for each different family of AST nodes, so we don't conflate "dependent" for template arguments with one or both of "type-dependent" and "value-dependent" for expressions, which mean different things.

33–60

You can use LLVM's BitmaskEnum mechanism in place of these operators. (#include "clang/Basic/BitmaskEnum.h" and add LLVM_MARK_AS_BITMASK_ENUM(/*LargestValue=*/UnexpandedPack) to the end of the enum.)

82–86

This whole function should be equivalent to just F & ~DependencyFlags::Type. Any type-dependent expression must also be value-dependent, so you should never need to set the ::Value bit. Perhaps we could assert this somewhere.

clang/lib/AST/NestedNameSpecifier.cpp
221–222

This is wrong: super should be instantiation-dependent whenever Specifier names a dependent type. Please add a FIXME.

ilya-biryukov marked an inline comment as done.Jan 28 2020, 2:01 AM
ilya-biryukov added inline comments.
clang/include/clang/AST/DependencyFlags.h
18–29

Yep, sounds good, probably the types would end up being more complicated, but I also like more type-safe approach.
Let me try to come up with something, I'll send a patch today.

82–86

Good point, I'll try to find a place to assert this with multiple types for different AST categories.

ilya-biryukov marked an inline comment as done and an inline comment as not done.
  • Use different types for different AST categories
  • Rename to getDependence

I've opted for duplicating the common flags across all the introduced enums (contains-unexpanded-pack, instantiation-dependent) , this is somewhat ugly, but everything else is even more complicated to use.
Less enums would also be a good idea probably, see the relevant comment.

Other than that, this should be ready for the next round.

I don't like the name getDependencies, because the function is not getting a list of dependencies, it's getting flags that indicate whether certain properties of the construct are dependent. Maybe getDependence or getDependenceFlags would be a better name? Likewise, instead of addDependencies, perhaps addDependence?

Good point. I've opted for getDependence, but didn't have enough time today to change addDependencies, will make sure to do it in the next iteration.

clang/include/clang/AST/DependencyFlags.h
18–29

I've introduced a separate enum for each of the AST classes, but that looks like an overkill.
We could probably merge the three for template arguments, template names and nested name specifiers into one.
(Would allow to get rid of macros too).

Note that TypeDependence is missing variably-modified bit, was't sure if it's part of the dependency propagation (don't have enough context to understand what it does and didn't look into it). From you message, I assume you would prefer to have it in the enum too?

WDYT about the approach in general?

33–60

Thanks, that does look better. I've used this and also switched to non-strongly-typed enums to allow simple conversions to bool (and code like bool IsTypeDependent = D & ExprDependence::Type).

There's a catch, though. We can't use LLVM_MARK_AS_BITMASK_ENUM on two enums inside the same namespace, it results in redeclaration of the same enumerator.

So I had to put them into structs (to introduce a scope). Might be a bit weird, let me know what you think, changing back to strongly-typed enums should not be too hard. That would mean we need helpers like isTypeDependent or checks like (D & Flags::Type) != Flags::None, both don't look good.

82–86

Was thinking about the best place for assert.
Putting it into headers means introducing possibly ODR violations, we do care about keeping those off LLVM, right?
Putting it into the .cpp files means we're loosing optimization opportunities in non-LTO builds (those functions should really be inlined).

Decided to not put the assertions here for now, but those could be easy to add later.

clang/lib/AST/NestedNameSpecifier.cpp
221–222

Done.
This is true for everything, right? Dependent always implies instantiation-dependent, right?

Unit tests: fail. 61841 tests passed, 5 failed and 780 were skipped.

failed: libc++.std/language_support/cmp/cmp_partialord/partialord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongeq/cmp.strongeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_strongord/strongord.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakeq/cmp.weakeq.pass.cpp
failed: libc++.std/language_support/cmp/cmp_weakord/weakord.pass.cpp

clang-tidy: fail. clang-tidy found 0 errors and 4 warnings. 0 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

sammccall added a subscriber: sammccall.

Rebase (ConceptSpecializationExpr moved).
Added FIXME to use enum for concept requirement dependence, it's still murky to me.
addDependencies -> addDependence, for clarity.
Move variably-modified into TypeDependence bitfield.

sammccall commandeered this revision.Feb 11 2020, 10:55 AM
sammccall added a reviewer: ilya-biryukov.

@ilya-biryukov isn't working on clang fulltime anymore :-(

I'm going to try to pick up the work on RecoveryExpr, starting with this patch.

@rsmith I think this is waiting on your review (sorry if I've missed anything else that was outstanding).

If you'd like to have concept::Requirement use a similar bitfield, I'd just like to confirm my understanding of the current code before refactoring it:

  • there's just one Dependent bit (along with UnexpandedPack) - instantiation-dependence isn't relevant?
  • RequiresExpr is only instantiation-dependent if value-dependent (unlike other exprs)
hokein added a subscriber: hokein.Feb 12 2020, 2:14 AM

@rsmith Friendly ping. Do you want to review this/other patches in this sequence, or should we be a bit bolder and pull you in when we're uncertain in principle what to do?

@rsmith Friendly ping. Do you want to review this/other patches in this sequence, or should we be a bit bolder and pull you in when we're uncertain in principle what to do?

I'm fine with you making progress on this without my involvement; I consider the general plan described in https://reviews.llvm.org/D65591 to be approved.

If you'd like to have concept::Requirement use a similar bitfield, I'd just like to confirm my understanding of the current code before refactoring it:

  • there's just one Dependent bit (along with UnexpandedPack) - instantiation-dependence isn't relevant?

Correct; requirements are weird in this regard because substitution failure affects their value rather than their validity, so there's no difference between "refers to template parameter / substitution can fail" and "value depends on template parameters"

  • RequiresExpr is only instantiation-dependent if value-dependent (unlike other exprs)

I don't think that's quite correct: a RequiresExpr should also be instantiation-dependent if it has instantiation-dependent parameters. Other than that case, it's both value-dependent and instantiation-dependent if it has dependent requirements and neither otherwise, so yes, the two flags are the same.

sammccall marked an inline comment as done.

Thanks Richard! Haojian agreed to take a look at this.

clang/lib/AST/ExprConcepts.cpp
186

Per Richard's comment, it sounds like this may be incorrect in obscure cases (if we have a non-dependent requirement that is always unsatisfied, but parameters are instantiation-dependent). I'll add a FIXME

hokein added inline comments.Feb 26 2020, 1:38 AM
clang/include/clang/AST/DependencyFlags.h
58

should we make the enum as uint8_t as the other ExprDependence above?

82

nit: I think we can get rid of the static_cast, sine we already use LLVM_MARK_AS_BITMASK_ENUM.

clang/include/clang/AST/Type.h
1468

would be nice to keep this comments in the new TypeDependence struct.

clang/lib/AST/TemplateName.cpp
174

This part of refactoring seems a little scary to me, I think it is correct by comparing with the previous version. but the getDependence() now is very complicated, I have no idea what it is doing.

instead of merging three different non-trivial if branches into a single function, maybe keep them as it-is.

hokein updated this revision to Diff 247818.Mar 3 2020, 1:18 AM
  • rebase to master
  • address my comments
  • added a FIXME about the RequiresExpr
hokein commandeered this revision.Mar 3 2020, 1:25 AM
hokein edited reviewers, added: sammccall; removed: hokein.
hokein added inline comments.
clang/lib/AST/TemplateName.cpp
174

I have restructured the code, let me know whether it is clear now.

sammccall added inline comments.Mar 3 2020, 2:51 AM
clang/lib/AST/TemplateName.cpp
174

nit: please don't use "Dependency" to mean "Dependence" :-)

I find this easier to read with a short name here (like D or the previous F, but up to you.

175

I think it would add some useful structure to put everything except the getAsTemplateDecl() in a switch (getKind()) rather than ifs scattered around. This would make it clearer which cases are disjoint.

206

As far as I can tell, an overloaded template will always return null for getAsTemplateDecl(). So this assert can be hoisted to the top, which I think would be clearer.

213

Why are we querying/propagating individual bits here rather than converting and adding DTN->getQualifier()->getDependence()? Are we deliberately dropping some of the bits?

(Checking individual bits makes adding new bits e.g. errors harder, as they won't be propagated by default)

217

why not just add DependentInstantiation above in the first place?
Tracking incorrect bits and then fixing them at the end seems a bit confusing.

hokein updated this revision to Diff 247881.Mar 3 2020, 6:28 AM
hokein marked 4 inline comments as done.

address comments.

hokein added inline comments.Mar 3 2020, 6:30 AM
clang/lib/AST/TemplateName.cpp
206

I didn't get your point here, did you mean moving the assert to the switch (getKind()) like

switch (getKind()) {
  case OverloadedTemplate:
    assert(!GetAsTemplateDecl());
}

?

217

oops, I was confused by the DependentInstantiation and Dependent bits.

sammccall accepted this revision.Mar 3 2020, 6:49 AM

thanks, that looks better to me

clang/lib/AST/TemplateName.cpp
206

ITYM assert(getAsTemplateDecl())

Yes, but also if this is an OverloadedTemplate, then getAsTemplateDecl is always false. So this can just be assert(false && "some message") in that case statement

211

what's this line about?

This revision is now accepted and ready to land.Mar 3 2020, 6:49 AM
hokein updated this revision to Diff 247905.Mar 3 2020, 8:00 AM
hokein marked an inline comment as done.

move the assert to overloadedTemplate switch case.

clang/lib/AST/TemplateName.cpp
211

this indicates that the template name is dependent if it doesn't refer to any known template declarations (getAsTemplateDecl() returns null). removing it will cause a test failure.

sammccall added inline comments.Mar 3 2020, 8:27 AM
clang/lib/AST/TemplateName.cpp
211

oh, I missed the early return in the other case.
nit: I'd suggest a single return and put this in an else { ... }, which I think makes it slightly clearer that the two "parts" of this function are simply composed together. Up to you though.

This revision was automatically updated to reflect the committed changes.
hokein marked an inline comment as done.
AlexeySachkov added inline comments.
clang/include/clang/AST/Type.h
1827–1830

@ilya-biryukov, Is this code snippet correct?

It seems to be, that it should look like:

if (Dependent)
  Deps |= TypeDependence::Dependent;
if (InstantiationDependent)
  Deps |= TypeDependence::Dependent | TypeDependence::Instantiation;
sammccall added inline comments.Mar 17 2020, 10:34 AM
clang/include/clang/AST/Type.h
1827–1830

I agree that seems clearer, but ISTM they are equivalent because a dependent type is always instantiation-dependent (right?)

Are you seeing related problems?

AlexeySachkov added inline comments.Mar 18 2020, 1:03 AM
clang/include/clang/AST/Type.h
1827–1830

Are you seeing related problems?

I though I was seeing a related problem, but it turned out that I wasn't.

Looking at the code again with a clear head, I believe that everything is correct here