Keep invalid Switch in the AST

[ogoffart]

Summary

• When the condition is invalid, replace it by an OpaqueValueExpr

• When parsing an invalid CaseStmt, don't drop the sub statement, just return it instead.

• In Sema::ActOnStartOfSwitchStmt, always keep the SwitchStmt, even if it has duplicate case or defaults statement or that the condition cannot be converted to an integral type.

[ogoffart]

I believe only the change in ActOnFinishSwitchStmt might be controversial.
Is it breaking an invariant than having switches kept in the AST?

[ogoffart]

ping?

[ogoffart]

ping2

[ogoffart]

Ping

[ogoffart]

re-ping

[aaron.ballman]

You've explained how you are accomplishing this but not why. I don't think Clang typically keeps erroneous AST nodes in the tree. What kind of problem is this intended to solve?

[ogoffart]

The problem i'm trying to solve is precisely to keep as much as possible of the valid AST in the main AST, despite errors.
I've already done some work with r249982, r272962 and more, and there is still a lot to do. But the goal is to keep as much as possible of it.

The reason i'm working on this is highlighting of code where some code might be potentially invalid (because you are editing it, or because the tool don't have access to all headers)
Things like if statement from my previous patch, or switch statement like this patch are the things which have the more impact, because not keeping them removes highlighting for potentially big blocks of code.

This is useful for example for IDE such as KDevelop which use clang for highlighting, or my own tool [code.woboq.org]

A random example is https://code.woboq.org/linux/linux/arch/arm/kernel/module.c.html?style=kdevelop#101
(generated with this patch applied.) There are errors because this is an arm file built with the option for an intel kernel. Yet, most of the file is properly highlighted. If this patch was not applied, the whole switch statement would be removed from the AST and nothing within would be hightlighted, only because some case label are invalid.

[aaron.ballman]

In D26350#809577, @ogoffart wrote:

The problem i'm trying to solve is precisely to keep as much as possible of the valid AST in the main AST, despite errors.
I've already done some work with r249982, r272962 and more, and there is still a lot to do. But the goal is to keep as much as possible of it.

Thank you for the explanation -- I like the goal, but am definitely concerned about the assumptions it might break by doing this (in general, not specific to this patch). We try to recover gracefully whenever possible, but still, a whole lot of frontend code relies on knowing when something is invalid to prevent the compiler from doing even worse things. I'm not certain the best balance to strike with that, but suspect it's going to adversely impact tools like clang-tidy which tend to assume that AST matchers match *valid* code and not invalid code.

lib/Parse/ParseStmt.cpp

1297

succeed -> succeeds

Are the concerns pointed out in the FIXME addressed by code not in this patch?

lib/Sema/SemaStmt.cpp

669

This makes the condition result valid when it isn't. Users of this condition result may expect a valid condition result to return nonnull values when calling get(), which makes me uncomfortable.

[ogoffart]

Thanks for your review and i'll try to address the concerns.

I believe tools that really need valid code relies on the diagnostics and bail out on error. On the other hand, tools that may work on code containing error do a best effort to work on the remaining AST .
And patches like this one improve the remaining AST, so tools like clang-tidy will be able to also do valid transformation inside the switch statement, which could not have been possible when the whole body is gone.

The AST stays "valid" in the sense that all the nodes exist (no nullptr) and so conform to the expectation of the code. The condition of a switch may now be an OpaqueValueExpr which should not disturb the matchers.

lib/Parse/ParseStmt.cpp

1297

The FIXME is pointing out problems occuring if the parser found 'default' or 'case' statement, but cannot connect it to the corresponding 'switch' statement (because that switch statement did not exist as it was removed from the AST).

Now that we always keep the 'switch' statement, this is no longer a problem.

lib/Sema/SemaStmt.cpp

669

Get return a non-null value.
That's why i'm constructing an OpaqueValueExpr placeholder expression.

The ConditionVar (nullptr in the line bellow) can be null. It is null in valid code most of the time actually, when one does not declare a new variable in in condition.

But the result is that users of this condition will get a OpaqueValueExpr when calling get and should not be disturbed by that as they will just take that as an expression.

[aaron.ballman]

This looks reasonable to me, but you should wait for @rsmith to sign off before committing.

lib/Sema/SemaStmt.cpp

669

Ah, sorry, I misread the code in my haste.

[rsmith]

lib/Parse/ParseStmt.cpp

1297

I'm uncomfortable about this; this change couples Parser to the implementation details of Sema. How about this: remove this assert and change ActOnFinishSwitchStmt to take a StmtResult instead (which might be invalid). Then you can tell from within ActOnFinishSwitchStmt whether to check the case statements against the condition based on whether the switch is in fact invalid.

(Alternatively: change ActOnStartSwitchStmt to return void and make ActOnFinishSwitchStmt pick up the switch statement from the SwitchStack.)

lib/Sema/SemaStmt.cpp

672

Won't this result in warnings or errors later on if we have case labels with expressions of other types? (Eg, narrowing warnings/errors)

Please instead (somehow) track that the switch condition is invalid and skip those checks -- perhaps either by returning an invalid-but-not-null statement here and passing that back into ActOnFinishSwitchStmt, or by tracking an "invalid" flag on the SwitchStack entry.

1173–1177

Hmm. Removing this will result in us producing invalid ASTs in some cases (with duplicate case or default labels). That's a condition that it would be reasonable for AST consumers to assert on currently, so this is concerning.

That said... it's inevitable that this work to keep more invalid constructs in the AST will result in such changes. Perhaps what we need is just a marker to say "beyond this point the AST does not necessarily correspond to any valid source code" for Stmt nodes, analogous to the Invalid marker on declarations. (Maybe a wrapper InvalidStmt node, so that tree traversals can easily avoid walking through it.)

Let's try this change out as-is. It may be that this concern is baseless.

[ogoffart]

Updated the patch so that ActOnStartOfSwitchStmt returns void, and ActOnFinishSwitchStmt will skip some checks in case of error

[rsmith]

lib/Sema/SemaStmt.cpp

823

It's fragile to assume that the only way you can see an OpaqueValueExpr here is by it being created in ActOnStartOfSwitchStmt. We could tunnel this information through in another way, though, such as by tracking a bool in the SwitchStack in addition to the statement.

However, perhaps it's time to bite the bullet and add actual support for error nodes in the AST. For example, we could add a new kind of placeholder type for an erroneous expression, and build syntactic expression trees with that type when we encounter errors.

[aaron.ballman]

lib/Sema/SemaStmt.cpp

823

FWIW, I would find error nodes in the AST to be extremely useful.

lib/Parse/ParseStmt.cpp

   }
 
   // Install the body into the most deeply-nested case.
   if (DeepestParsedCaseStmt) {
     // Broken sub-stmt shouldn't prevent forming the case statement properly.
     if (SubStmt.isInvalid())
       SubStmt = Actions.ActOnNullStmt(SourceLocation());
     Actions.ActOnCaseStmtBody(DeepestParsedCaseStmt, SubStmt.get());
+  } else {
+    // The case statement is invalid, recover by returning the statement body.
+    return SubStmt;
   }
 
   // Return the top level parsed statement tree.
   return TopLevelCase;
 }
 
 /// ParseDefaultStatement
 ///       labeled-statement:

   Sema::ConditionResult Cond;
   if (ParseParenExprOrCondition(&InitStmt, Cond, SwitchLoc,
                                 Sema::ConditionKind::Switch))
     return StmtError();
 
   StmtResult Switch =
       Actions.ActOnStartOfSwitchStmt(SwitchLoc, InitStmt.get(), Cond);
 
-  if (Switch.isInvalid()) {
-    // Skip the switch body.
-    // FIXME: This is not optimal recovery, but parsing the body is more
-    // dangerous due to the presence of case and default statements, which
-    // will have no place to connect back with the switch.
-    if (Tok.is(tok::l_brace)) {
-      ConsumeBrace();
-      SkipUntil(tok::r_brace);
-    } else
-      SkipUntil(tok::semi);
-    return Switch;
-  }
+  assert(!Switch.isInvalid() && "ActOnStartOfSwitchStmt always succeed");
 
   // C99 6.8.4p3 - In C99, the body of the switch statement is a scope, even if
   // there is no compound stmt.  C90 does not have this clause.  We only do this
   // if the body isn't a compound statement to avoid push/pop in common cases.
   //
   // C++ 6.4p1:
   // The substatement in a selection-statement (each substatement, in the else
   // form of the if statement) implicitly defines a local scope.

lib/Sema/SemaStmt.cpp

 
   // C99 6.8.4.2p5 - Integer promotions are performed on the controlling expr.
   return UsualUnaryConversions(CondResult.get());
 }
 
 StmtResult Sema::ActOnStartOfSwitchStmt(SourceLocation SwitchLoc,
                                         Stmt *InitStmt, ConditionResult Cond) {
   if (Cond.isInvalid())
-    return StmtError();
+    Cond = ConditionResult(
+        *this, nullptr,
+        MakeFullExpr(new (Context) OpaqueValueExpr(SourceLocation(),
+                                                   Context.IntTy, VK_RValue),
+                     SwitchLoc),
+        false);
 
   getCurFunction()->setHasBranchIntoScope();
 
   SwitchStmt *SS = new (Context)
       SwitchStmt(Context, InitStmt, Cond.get().first, Cond.get().second);
   getCurFunction()->SwitchStack.push_back(SS);
   return SS;
 }

   // type (before the promotion) doesn't make sense, even when it can
   // be represented by the promoted type.  Therefore we need to find
   // the pre-promotion type of the switch condition.
   if (!CondExpr->isTypeDependent()) {
     // We have already converted the expression to an integral or enumeration
     // type, when we started the switch statement. If we don't have an
     // appropriate type now, just return an error.
     if (!CondType->isIntegralOrEnumerationType())
-      return StmtError();
+      return SS;
 
     if (CondExpr->isKnownToHaveBooleanValue()) {
       // switch(bool_expr) {...} is often a programmer error, e.g.
       //   switch(n && mask) { ... }  // Doh - should be "n & mask".
       // One can always use an if statement instead of switch(bool_expr).
       Diag(SwitchLoc, diag::warn_bool_switch_condition)
           << CondExpr->getSourceRange();
     }

   bool CaseListIsErroneous = false;
 
   for (SwitchCase *SC = SS->getSwitchCaseList(); SC && !HasDependentValue;
        SC = SC->getNextSwitchCase()) {
 
     if (DefaultStmt *DS = dyn_cast<DefaultStmt>(SC)) {
       if (TheDefaultStmt) {
         Diag(DS->getDefaultLoc(), diag::err_multiple_default_labels_defined);
         Diag(TheDefaultStmt->getDefaultLoc(), diag::note_duplicate_case_prev);
 
         // FIXME: Remove the default statement from the switch block so that
         // we'll return a valid AST.  This requires recursing down the AST and
         // finding it, not something we are set up to do right now.  For now,
         // just lop the entire switch stmt out of the AST.
         CaseListIsErroneous = true;
       }
       TheDefaultStmt = DS;

         SS->setAllEnumCasesCovered();
     }
   }
 
   if (BodyStmt)
     DiagnoseEmptyStmtBody(CondExpr->getLocEnd(), BodyStmt,
                           diag::warn_empty_switch_body);
 
-  // FIXME: If the case list was broken is some way, we don't have a good system
-  // to patch it up.  Instead, just return the whole substmt as broken.
-  if (CaseListIsErroneous)
-    return StmtError();
-
   return SS;
 }
 
 void
 Sema::DiagnoseAssignmentEnum(QualType DstType, QualType SrcType,
                              Expr *SrcExpr) {
   if (Diags.isIgnored(diag::warn_not_in_enum_assignment, SrcExpr->getExprLoc()))
     return;

test/Misc/ast-dump-invalid-switch.cpp

+// RUN: not %clang_cc1 -std=c++11 -triple x86_64-linux-gnu -fms-extensions -ast-dump -ast-dump-filter Test %s | FileCheck -check-prefix CHECK -strict-whitespace %s
+
+/* This test ensures that the AST is still complete, even for invalid code */
+
+namespace TestInvalidSwithCondition {
+int f(int x) {
+  switch (_invalid_) {
+  case 0:
+    return 1;
+  default:
+    return 2;
+  }
+}
+}
+
+// CHECK: NamespaceDecl {{.*}} TestInvalidSwithCondition
+// CHECK-NEXT: `-FunctionDecl
+// CHECK-NEXT:   |-ParmVarDecl
+// CHECK-NEXT:   `-CompoundStmt
+// CHECK-NEXT:     `-SwitchStmt
+// CHECK-NEXT:       |-<<<NULL>>>
+// CHECK-NEXT:       |-<<<NULL>>>
+// CHECK-NEXT:       |-OpaqueValueExpr
+// CHECK-NEXT:       `-CompoundStmt
+// CHECK-NEXT:         |-CaseStmt
+// CHECK-NEXT:         | |-IntegerLiteral {{.*}} 'int' 0
+// CHECK-NEXT:         | |-<<<NULL>>>
+// CHECK-NEXT:         | `-ReturnStmt
+// CHECK-NEXT:         |   `-IntegerLiteral {{.*}} 'int' 1
+// CHECK-NEXT:         `-DefaultStmt
+// CHECK-NEXT:           `-ReturnStmt
+// CHECK-NEXT:             `-IntegerLiteral {{.*}} 'int' 2
+
+namespace TestSwitchConditionNotIntegral {
+int g(int *x) {
+  switch (x) {
+  case 0:
+    return 1;
+  default:
+    return 2;
+  }
+}
+}
+
+// CHECK: NamespaceDecl {{.*}} TestSwitchConditionNotIntegral
+// CHECK-NEXT: `-FunctionDecl
+// CHECK-NEXT:   |-ParmVarDecl
+// CHECK-NEXT:   `-CompoundStmt
+// CHECK-NEXT:     `-SwitchStmt
+// CHECK-NEXT:       |-<<<NULL>>>
+// CHECK-NEXT:       |-<<<NULL>>>
+// CHECK-NEXT:       |-ImplicitCastExpr
+// CHECK-NEXT:       | `-DeclRefExpr {{.*}} 'x' 'int *'
+// CHECK-NEXT:       `-CompoundStmt
+// CHECK-NEXT:         |-CaseStmt
+// CHECK-NEXT:         | |-IntegerLiteral {{.*}} 'int' 0
+// CHECK-NEXT:         | |-<<<NULL>>>
+// CHECK-NEXT:         | `-ReturnStmt
+// CHECK-NEXT:         |   `-IntegerLiteral {{.*}} 'int' 1
+// CHECK-NEXT:         `-DefaultStmt
+// CHECK-NEXT:           `-ReturnStmt
+// CHECK-NEXT:             `-IntegerLiteral {{.*}} 'int' 2
+
+namespace TestSwitchInvalidCases {
+int g(int x) {
+  switch (x) {
+  case _invalid_:
+    return 1;
+  case _invalid_:
+    return 2;
+  case x:
+    return 3;
+  default:
+    return 4;
+  default:
+    return 5;
+  }
+}
+}
+
+// CHECK: NamespaceDecl {{.*}} TestSwitchInvalidCases
+// CHECK-NEXT: `-FunctionDecl
+// CHECK-NEXT:   |-ParmVarDecl
+// CHECK-NEXT:   `-CompoundStmt
+// CHECK-NEXT:     `-SwitchStmt
+// CHECK-NEXT:       |-<<<NULL>>>
+// CHECK-NEXT:       |-<<<NULL>>>
+// CHECK-NEXT:       |-ImplicitCastExpr
+// CHECK-NEXT:       | `-DeclRefExpr {{.*}}'x' 'int'
+// CHECK-NEXT:       `-CompoundStmt
+// CHECK-NEXT:         |-ReturnStmt
+// CHECK-NEXT:         | `-IntegerLiteral {{.*}} 'int' 1
+// CHECK-NEXT:         |-ReturnStmt
+// CHECK-NEXT:         | `-IntegerLiteral {{.*}} 'int' 2
+// CHECK-NEXT:         |-CaseStmt
+// CHECK-NEXT:         | |-DeclRefExpr {{.*}} 'x' 'int'
+// CHECK-NEXT:         | |-<<<NULL>>>
+// CHECK-NEXT:         | `-ReturnStmt
+// CHECK-NEXT:         |   `-IntegerLiteral {{.*}} 'int' 3
+// CHECK-NEXT:         |-DefaultStmt
+// CHECK-NEXT:         | `-ReturnStmt
+// CHECK-NEXT:         |   `-IntegerLiteral {{.*}} 'int' 4
+// CHECK-NEXT:         `-DefaultStmt
+// CHECK-NEXT:           `-ReturnStmt
+// CHECK-NEXT:             `-IntegerLiteral {{.*}} 'int' 5