Add support for importing ChooseExpr AST nodes.

[tmroeder]

Summary

This allows ASTs to be merged when they contain ChooseExpr (the GNU
builtin_choose_expr construction). This is needed, for example, for
cross-CTU analysis of C code that makes use of builtin_choose_expr.

The node is already supported in the AST, but it didn't have a matcher
in ASTMatchers. So, this change adds the matcher and adds support to
ASTImporter.

[shafik]

This looks reasonable, I will wait for @martong and/or @a_sidorin to review.

FYI LLDB is the other big user of ASTImpoter so it is helpful if you can run check-lldb especially on MacOS so you can to catch regressions before committing. After committing please make sure to monitor the GreenDragon build bots:

http://lab.llvm.org:8080/green/view/LLDB/

Thank you!

[aaron.ballman]

Please be sure to update Registry.cpp to expose the new AST matcher to the dynamic matcher infrastructure, regenerate the AST matcher documentation (run clang\docs\tools\dump_ast_matchers.py), and add tests for the matcher.

[tmroeder]

Updated Registry.cpp, regenerated the documentation, and added direct tests for the matcher.

[tmroeder]

In D58292#1399774, @shafik wrote:

This looks reasonable, I will wait for @martong and/or @a_sidorin to review.

FYI LLDB is the other big user of ASTImpoter so it is helpful if you can run check-lldb especially on MacOS so you can to catch regressions before committing. After committing please make sure to monitor the GreenDragon build bots:

I don't currently have a macOS machine to try this on, but I'll see what I can do next week.

I ran check-lldb with and without my change, and I don't seem to have broken anything new. However, check-lldb fails in a few ways at head (at least in my configuration; maybe I did something wrong):

     RESULT: FAILED (0 passes, 2 failures, 0 errors, 2 skipped, 0                                                                                                                                                                                                                                                              
     expected failures, 0 unexpected successes)                                                                                                                                                                                                                                                                                
                                                                                                                                                                                                                                                                                                                               
********************                                                                                                                                                                                                                                                                                                           
Testing Time: 59.67s                                                                                                                                                                                                                                                                                                           
********************                                                                                                                                                                                                                                                                                                           
Unexpected Passing Tests (2):                                                                                                                                                                                                                                                                                                  
    lldb-Suite :: functionalities/asan/TestMemoryHistory.py                                                                                                                                                                                                                                                                    
    lldb-Suite :: functionalities/asan/TestReportData.py                                                                                                                                                                                                                                                                       
                                                                                                                                                                                                                                                                                                                               
********************                                                                                                                                                                                                                                                                                                           
Failing Tests (3):                                                                                                                                                                                                                                                                                                             
    lldb-Suite ::                                                                                                                                                                                                                                                                                                              
functionalities/data-formatter/data-formatter-stl/libcxx/iterator/TestDataFormatterLibccIterator.py                                                                                                                                                                                                                            
    lldb-Suite ::                                                                                                                                                                                                                                                                                                              
functionalities/register/register_command/TestRegisters.py                                                                                                                                                                                                                                                                     
    lldb-Suite :: tools/lldb-server/TestGdbRemoteRegisterState.py                                                                                                                                                                                                                                                              
                                                                                                                                                                                                                                                                                                                               
  Expected Passes    : 1480                                                                                                                                                                                                                                                                                                    
  Expected Failures  : 1                                                                                                                                                                                                                                                                                                       
  Unsupported Tests  : 33                                                                                                                                                                                                                                                                                                      
  Unexpected Passes  : 2                                                                                                                                                                                                                                                                                                       
  Unexpected Failures: 3                                                                                                                                                                                                                                                                                                       
FAILED: tools/lldb/lit/CMakeFiles/check-lldb-lit                                                                                                                                                                                                                                                                               
cd /usr/local/google/home/tmroeder/src/llvm/llvm-build/release/tools/lldb/lit                                                                                                                                                                                                                                                  
  && /usr/bin/python2.7                                                                                                                                                                                                                                                                                                        
  /usr/local/google/home/tmroeder/src/llvm/llvm-build/release/./bin/llvm-lit                                                                                                                                                                                                                                                   
  -sv                                                                                                                                                                                                                                                                                                                          
  /usr/local/google/home/tmroeder/src/llvm/llvm-build/release/tools/lldb/lit                                                                                                                                                                                                                                                   
ninja: build stopped: subcommand failed.

[a_sidorin]

Hi Tom,
The change looks reasonable but the tests need some improvements.

test/ASTMerge/choose-expr/Inputs/choose1.c

1 ↗

(On Diff #187113)

This test duplicates unit test. I think we can keep unit test only and remove this one.
The other option (I like it even more) is to turn this test into constexpr check and verify that this code _behaves_ as expected, not only that its AST structure is fine. You can find some examples in ASTMerge tests - for expr import, for example.

unittests/AST/ASTImporterTest.cpp

1101

I don't think we really need such macros in unit test just to check that the expr is imported correctly - a single valid __builtin_choose_expr is enough. It can even be checked with a simple testImport() call.

unittests/ASTMatchers/ASTMatchersNodeTest.cpp

765

Same here - I think the tests should be concise if it is possible.

[tmroeder]

Thanks for the review and the suggestions for improving the tests.

This update cleans up the tests as suggested.

test/ASTMerge/choose-expr/Inputs/choose1.c

1 ↗

(On Diff #187113)

I can't use constexpr (and static_assert, as in the expr tests) because those are C++ keywords, and __builtin_choose_expr is only in C.

Instead, I used _Static_assert (from C11) to get a similar effect. Please take a look.

unittests/AST/ASTImporterTest.cpp

1101

OK, dropped the test, since I already have that in ImportExpr.ImportChooseExpr in this patch.

unittests/ASTMatchers/ASTMatchersNodeTest.cpp

765

OK, dropped this part of the test too, since the first part checks that a simple __builtin_choose_expr matches correctly.

[aaron.ballman]

lib/AST/ASTImporter.cpp

6140

Please don't use auto here; the type isn't spelled out in the initialization.

6160–6162

bool CondIsTrue = E->isConditionDependent() ? false : E->isConditionTrue();

[a_sidorin]

Hi Tom,

Thank for the fixes, now the patch looks almost fine. I have a small nit inline, but I think the patch can land after this fix.

lib/AST/ASTImporter.cpp

6140

Hi Aaron,
importSeq() is a helper targeted to simplify a lot of imports done during AST node import and related error handling. The type of this importSeq() expression is Expected<std::tuple<Expr *, Expr *, Expr *, SourceLocation, SourceLocation, QualType>>, so I think it's better to leave it as auto.

6160

bool CondIsTrue = E->isConditionDependent() && E->isConditionTrue();?

[aaron.ballman]

lib/AST/ASTImporter.cpp

6140

Wow. I really dislike that we basically *have* to hide the type information because it's just too ugly to spell. I understand why we're using auto based on your explanation, but it basically means I can't understand what this code is doing without a lot more effort.

Let's keep the auto, but let's please stop using type compositions that make it considerably harder to review the code. This feel like a misuse of std::tuple.

6160

I like that even better than my suggestion. :-)

[aaron.ballman]

lib/AST/ASTImporter.cpp

6140

After staring at this for longer, I no longer think it's a misuse of std::tuple, just... an unfortunate side-effect of the design of importSeq(). I don't have a good idea for how to make this easier on reviewers and other people who aren't frequently looking at the AST importing code. :-(

[tmroeder]

Changed the CondIsTrue RHS as suggested.

Left the auto based on the conclusion of the discussion.

[tmroeder]

Fix a mistake in the comment.

CondIsTrue only matters if the value *is* condition dependent, not *is not* condition dependent.

[aaron.ballman]

LGTM!

[tmroeder]

Reverted to the original semantics of CondIsTrue

lib/AST/ASTImporter.cpp

6160

Wait, this doesn't have the same truth table as my original code.

let CD = E->isConditionDependent()
let CT = E->isConditionTrue()

in

bool CondIsTrue = false;
if (!CD)
  CondIsTrue = CT;

has the table for CondIsTrue:

CD	CT	CondIsTrue
T	T	F
T	F	F
F	T	T
F	F	F

i.e., if CD is true, then CondIsTrue is always false. Otherwise, it's the value of CT.

The suggested line has the truth table

CD	CT	CondIsTrue
T	T	T
T	F	F
F	T	F
F	F	F

That is, the effect of CD is swapped.

Aaron's suggestion matches my original table. I based my code on include/clang/AST/Expr.h line 4032, which asserts !isConditionDependent() in the implementation of isConditionTrue.

I realized this after I "fixed" my comment to match the implementation change. Am I missing something? Or is the assertion in Expr.h wrong? I think this should be

bool CondIsTrue = !E->isConditionDependent() && E->isConditionTrue();

I've changed my code to that and reverted the comment change.

[aaron.ballman]

lib/AST/ASTImporter.cpp

6160

Good catch -- I think my eyes just missed the change in logic. Perhaps we should add a test case that exercises this?

[a_sidorin]

lib/AST/ASTImporter.cpp

6160

Wow, that's a nice catch. Sorry for the misleading.

[tmroeder]

lib/AST/ASTImporter.cpp

6160

I started to look for a way to test this, then realized that while it's possible to test the code itself, it's impossible to make a ChooseExpr with isConditionDependent() that returns true for real code.

TL;DR: ChooseExpr is a C-only construct, and isConditionDependent is a C++-only condition; it's always false in C.

Details:

ChooseExpr only represents __builtin_choose_expr which is only valid in C, not C++. That means ChooseExpr::isConditionDependent() will always be false.

The definition is

bool isConditionDependent() const {
  return getCond()->isTypeDependent() || getCond() ->isValueDependent();
}

However Expr::isTypeDependent() (see Expr.h line 158) is a purely C++ property to do with templates ([temp.dep.expr]): it is true if the type of the expression could change from one template instantiation to another.

Similarly Expr::isValueDependent() (see Expr.h line 144) is a purely C++ property to do with templates ([temp.dep.expr]): it is true for value-dependent types in templates.

Both will always be false in all instantiations of ChooseExpr, due to the language difference.

So, I think ChooseExpr can be refactored to remove isConditionDependent and change its constructor to remove TypeDependent and ValueDependent.

If it's OK with you, I'll do that in a followup patch.

[aaron.ballman]

lib/AST/ASTImporter.cpp

6160

ChooseExpr only represents __builtin_choose_expr which is only valid in C, not C++.

We allow it in C++, though: https://godbolt.org/z/_f1DPV

[tmroeder]

lib/AST/ASTImporter.cpp

6160

Hmm. Is that by design or chance? GCC doesn't allow it: https://godbolt.org/z/kvGCk1

Maybe it shouldn't be allowed?

[tmroeder]

lib/AST/ASTImporter.cpp

6160

Anyway, that means I can add a test; I'll look into doing that.

[tmroeder]

Added more unit tests.

Sorry for the delay; I had to dig into the details to figure out where to put these tests and how to structure them. Please let me know if there are better ways to do this.

I don't know any way to write a matcher that checks the condition of __builtin_choose_expr before and after import, so I added a unit test that matches the expr and compares the From and To ChooseExprs directly.

I've confirmed that without the negation in the condition in VisitChooseExpr, the new tests cause failures and with the negation, everything is clean.

[tmroeder]

Fixed a minor style typo.

[a_sidorin]

Hi Tom,
Thanks for the fixes! The patch looks good to me now. I have only a small nit inline.

lib/AST/ASTImporter.cpp

6140

I think it is a case where the type is not even important. With C++17, we would just write:

auto Imp = importSeq(E->getCond(), E->getLHS(), E->getRHS(), ...)
if (Imp)
  return Imp.takeError();
auto [ToCond, ToLHS, ToRHS] = *Imp;

The exact type is not really needed here. However, if you have any ideas on how to improve this and make the type more explicit - they are always welcome.

unittests/AST/ASTImporterTest.cpp

581

LLVm has a set of nice helpers for working with containers in range -like style. I'd recommend you to use llvm::find here:
if (llvm::find(Args), "-fdelayed-template-parsing") != Args.end()) {

[aaron.ballman]

lib/AST/ASTImporter.cpp

6140

I actually don't find the structured binding version to be any more readable than the wrapped-tuple version -- either way, I don't see the types. What makes this current code somewhat-okay to me is the std::tie() below; that at least lets me figure it out through reasoning. In the structured binding version, that would likely go away and I'd probably argue harder for this being an unfortunate design for maintainers and reviewers.

[tmroeder]

Changed to use llvm::find.

Given the disagreement about the destructuring assignment, I didn't make that change.

[tmroeder]

Updating after switching to the git monorepo model.

[rnk]

I had to revert this in rL354839 because one of the tests didn't pass on Windows:
http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/4641

docs/LibASTMatchersReference.html

 though.
 
 Example matches 'a', L'a'
   char ch = 'a';
   wchar_t chw = L'a';
 </pre></td></tr>
 
 
+<tr><td>Matcher&lt;<a href="https://clang.llvm.org/doxygen/classclang_1_1Stmt.html">Stmt</a>&gt;</td><td class="name" onclick="toggle('chooseExpr0')"><a name="chooseExpr0Anchor">chooseExpr</a></td><td>Matcher&lt;<a href="https://clang.llvm.org/doxygen/classclang_1_1ChooseExpr.html">ChooseExpr</a>&gt;...</td></tr>
+<tr><td colspan="4" class="doc" id="chooseExpr0"><pre>Matches GNU __builtin_choose_expr.
+</pre></td></tr>
+
+
 <tr><td>Matcher&lt;<a href="https://clang.llvm.org/doxygen/classclang_1_1Stmt.html">Stmt</a>&gt;</td><td class="name" onclick="toggle('compoundLiteralExpr0')"><a name="compoundLiteralExpr0Anchor">compoundLiteralExpr</a></td><td>Matcher&lt;<a href="https://clang.llvm.org/doxygen/classclang_1_1CompoundLiteralExpr.html">CompoundLiteralExpr</a>&gt;...</td></tr>
 <tr><td colspan="4" class="doc" id="compoundLiteralExpr0"><pre>Matches compound (i.e. non-scalar) literals
 
 Example match: {1}, (1, 2)
   int array[4] = {1};
   vector int myvec = (vector int)(1, 2);
 </pre></td></tr>
 

include/clang/ASTMatchers/ASTMatchers.h

 /// \endcode
 extern const internal::VariadicDynCastAllOfMatcher<Stmt, CompoundLiteralExpr>
     compoundLiteralExpr;
 
 /// Matches nullptr literal.
 extern const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNullPtrLiteralExpr>
     cxxNullPtrLiteralExpr;
 
+/// Matches GNU __builtin_choose_expr.
+extern const internal::VariadicDynCastAllOfMatcher<Stmt, ChooseExpr>
+    chooseExpr;
+
 /// Matches GNU __null expression.
 extern const internal::VariadicDynCastAllOfMatcher<Stmt, GNUNullExpr>
     gnuNullExpr;
 
 /// Matches atomic builtins.
 /// Example matches __atomic_load_n(ptr, 1)
 /// \code
 ///   void foo() { int *ptr; __atomic_load_n(ptr, 1); }

lib/AST/ASTImporter.cpp

public:
     ExpectedStmt VisitObjCAtTryStmt(ObjCAtTryStmt *S);
     ExpectedStmt VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);
     ExpectedStmt VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);
     ExpectedStmt VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S);
 
     // Importing expressions
     ExpectedStmt VisitExpr(Expr *E);
     ExpectedStmt VisitVAArgExpr(VAArgExpr *E);
+    ExpectedStmt VisitChooseExpr(ChooseExpr *E);
     ExpectedStmt VisitGNUNullExpr(GNUNullExpr *E);
     ExpectedStmt VisitPredefinedExpr(PredefinedExpr *E);
     ExpectedStmt VisitDeclRefExpr(DeclRefExpr *E);
     ExpectedStmt VisitImplicitValueInitExpr(ImplicitValueInitExpr *E);
     ExpectedStmt VisitDesignatedInitExpr(DesignatedInitExpr *E);
     ExpectedStmt VisitCXXNullPtrLiteralExpr(CXXNullPtrLiteralExpr *E);
     ExpectedStmt VisitIntegerLiteral(IntegerLiteral *E);
     ExpectedStmt VisitFloatingLiteral(FloatingLiteral *E);
ExpectedStmt ASTNodeImporter::VisitVAArgExpr(VAArgExpr *E) {
   std::tie(ToBuiltinLoc, ToSubExpr, ToWrittenTypeInfo, ToRParenLoc, ToType) =
       *Imp;
 
   return new (Importer.getToContext()) VAArgExpr(
       ToBuiltinLoc, ToSubExpr, ToWrittenTypeInfo, ToRParenLoc, ToType,
       E->isMicrosoftABI());
 }
 
+ExpectedStmt ASTNodeImporter::VisitChooseExpr(ChooseExpr *E) {
+  auto Imp = importSeq(E->getCond(), E->getLHS(), E->getRHS(),
+                       E->getBuiltinLoc(), E->getRParenLoc(), E->getType());
+  if (!Imp)
+    return Imp.takeError();
+
+  Expr *ToCond;
+  Expr *ToLHS;
+  Expr *ToRHS;
+  SourceLocation ToBuiltinLoc, ToRParenLoc;
+  QualType ToType;
+  std::tie(ToCond, ToLHS, ToRHS, ToBuiltinLoc, ToRParenLoc, ToType) = *Imp;
+
+  ExprValueKind VK = E->getValueKind();
+  ExprObjectKind OK = E->getObjectKind();
+
+  bool TypeDependent = ToCond->isTypeDependent();
+  bool ValueDependent = ToCond->isValueDependent();
+
+  // The value of CondIsTrue only matters if the value is not
+  // condition-dependent.
+  bool CondIsTrue = E->isConditionDependent() && E->isConditionTrue();
+
+  return new (Importer.getToContext())
+      ChooseExpr(ToBuiltinLoc, ToCond, ToLHS, ToRHS, ToType, VK, OK,
+                 ToRParenLoc, CondIsTrue, TypeDependent, ValueDependent);
+}
 
 ExpectedStmt ASTNodeImporter::VisitGNUNullExpr(GNUNullExpr *E) {
   ExpectedType TypeOrErr = import(E->getType());
   if (!TypeOrErr)
     return TypeOrErr.takeError();
 
   ExpectedSLoc BeginLocOrErr = import(E->getBeginLoc());
   if (!BeginLocOrErr)

lib/ASTMatchers/ASTMatchersInternal.cpp

 const internal::VariadicDynCastAllOfMatcher<Stmt, FloatingLiteral> floatLiteral;
 const internal::VariadicDynCastAllOfMatcher<Stmt, ImaginaryLiteral> imaginaryLiteral;
 const internal::VariadicDynCastAllOfMatcher<Stmt, UserDefinedLiteral>
     userDefinedLiteral;
 const internal::VariadicDynCastAllOfMatcher<Stmt, CompoundLiteralExpr>
     compoundLiteralExpr;
 const internal::VariadicDynCastAllOfMatcher<Stmt, CXXNullPtrLiteralExpr>
     cxxNullPtrLiteralExpr;
+const internal::VariadicDynCastAllOfMatcher<Stmt, ChooseExpr> chooseExpr;
 const internal::VariadicDynCastAllOfMatcher<Stmt, GNUNullExpr> gnuNullExpr;
 const internal::VariadicDynCastAllOfMatcher<Stmt, AtomicExpr> atomicExpr;
 const internal::VariadicDynCastAllOfMatcher<Stmt, StmtExpr> stmtExpr;
 const internal::VariadicDynCastAllOfMatcher<Stmt, BinaryOperator>
     binaryOperator;
 const internal::VariadicDynCastAllOfMatcher<Stmt, UnaryOperator> unaryOperator;
 const internal::VariadicDynCastAllOfMatcher<Stmt, ConditionalOperator>
     conditionalOperator;

lib/ASTMatchers/Dynamic/Registry.cpp

RegistryMaps::RegistryMaps() {
   REGISTER_MATCHER(blockPointerType);
   REGISTER_MATCHER(booleanType);
   REGISTER_MATCHER(breakStmt);
   REGISTER_MATCHER(builtinType);
   REGISTER_MATCHER(callExpr);
   REGISTER_MATCHER(caseStmt);
   REGISTER_MATCHER(castExpr);
   REGISTER_MATCHER(characterLiteral);
+  REGISTER_MATCHER(chooseExpr);
   REGISTER_MATCHER(classTemplateDecl);
   REGISTER_MATCHER(classTemplateSpecializationDecl);
   REGISTER_MATCHER(complexType);
   REGISTER_MATCHER(compoundLiteralExpr);
   REGISTER_MATCHER(compoundStmt);
   REGISTER_MATCHER(conditionalOperator);
   REGISTER_MATCHER(constantArrayType);
   REGISTER_MATCHER(constantExpr);

test/ASTMerge/choose-expr/Inputs/choose.c

+_Static_assert(__builtin_choose_expr(1, 1, 0), "Incorrect semantics of __builtin_choose_expr");
+_Static_assert(__builtin_choose_expr(0, 0, 1), "Incorrect semantics of __builtin_choose_expr");

test/ASTMerge/choose-expr/test.c

+// RUN: %clang_cc1 -std=c11 -emit-pch -o %t.ast %S/Inputs/choose.c
+// RUN: %clang_cc1 -std=c11 -ast-merge %t.ast -fsyntax-only -verify %s
+// expected-no-diagnostics
+

unittests/AST/ASTImporterTest.cpp

testImport(
           stringLiteral(hasType(asString("const wchar_t [4]"))))));
   testImport(
       "void declToImport() { (void) \"foo\" \"bar\"; }",
       Lang_CXX, "", Lang_CXX, Verifier,
       functionDecl(hasDescendant(
           stringLiteral(hasType(asString("const char [7]"))))));
 }
 
+TEST_P(ImportExpr, ImportChooseExpr) {
+  MatchVerifier<Decl> Verifier;
+
+  testImport(
+    "void declToImport() { __builtin_choose_expr(1, 2, 3); }",
+    Lang_C, "", Lang_C, Verifier,
+    functionDecl(hasDescendant(chooseExpr())));
+}
+
 TEST_P(ImportExpr, ImportGNUNullExpr) {
   MatchVerifier<Decl> Verifier;
   testImport(
       "void declToImport() { (void)__null; }",
       Lang_CXX, "", Lang_CXX, Verifier,
       functionDecl(hasDescendant(gnuNullExpr(hasType(isInteger())))));
 }
 
 TEST_P(ImportExpr, ImportCXXNullPtrLiteralExpr) {
   MatchVerifier<Decl> Verifier;
   testImport(
       "void declToImport() { (void)nullptr; }",
       Lang_CXX11, "", Lang_CXX11, Verifier,
       functionDecl(hasDescendant(cxxNullPtrLiteralExpr())));
 }

 
 const internal::VariadicDynCastAllOfMatcher<Expr, CXXPseudoDestructorExpr>
     cxxPseudoDestructorExpr;
 
 TEST_P(ImportExpr, ImportCXXPseudoDestructorExpr) {
   MatchVerifier<Decl> Verifier;
   testImport(
       "typedef int T;"
       "void declToImport(int *p) {"
       "  T t;"
       "  p->T::~T();"
       "}",
       Lang_CXX, "", Lang_CXX, Verifier,
       functionDecl(hasDescendant(
           callExpr(has(cxxPseudoDestructorExpr())))));
 }
 

unittests/ASTMatchers/ASTMatchersNodeTest.cpp

TEST(Matcher, FloatLiterals) {
   EXPECT_TRUE(
     notMatches("double i = 5.0;", floatLiteral(equals(llvm::APFloat(6.0)))));
 }
 
 TEST(Matcher, NullPtrLiteral) {
   EXPECT_TRUE(matches("int* i = nullptr;", cxxNullPtrLiteralExpr()));
 }
 
+TEST(Matcher, ChooseExpr) {
+  EXPECT_TRUE(matchesC("void f() { (void)__builtin_choose_expr(1, 2, 3); }",
+                       chooseExpr()));
+}
+
 TEST(Matcher, GNUNullExpr) {
   EXPECT_TRUE(matches("int* i = __null;", gnuNullExpr()));
 }
 
 TEST(Matcher, AtomicExpr) {
   EXPECT_TRUE(matches("void foo() { int *ptr; __atomic_load_n(ptr, 1); }",
                       atomicExpr()));
 }
 
 TEST(Matcher, Initializers) {
   const char *ToMatch = "void foo() { struct point { double x; double y; };"
     "  struct point ptarray[10] = "