danmar#7027 TokenList::validateAst() did not detect broken AST with endless recursion

amai2012 · amai2012 · commit a288d5eb16ff · 2016-01-31T22:16:58.000+01:00
diff --git a/lib/tokenlist.cpp b/lib/tokenlist.cpp
@@ -1098,7 +1098,7 @@ void TokenList::createAst()
 
 void TokenList::validateAst()
 {
-    std::set < const Token* > astTokens;
+    std::set < const Token* > safeAstTokens;
     // Verify that ast looks ok
     for (const Token *tok = _front; tok; tok = tok->next()) {
         // Syntax error if binary operator only has 1 operand
@@ -1111,14 +1111,15 @@ void TokenList::validateAst()
 
         // check for endless recursion
         const Token* parent=tok;
+        std::set < const Token* > astTokens;
         while ((parent = parent->astParent()) != nullptr) {
-            if (parent==tok)
-                throw InternalError(tok, "AST broken: endless recursion from '" + tok->str() + "'", InternalError::SYNTAX);
-            if (astTokens.find(parent)!= astTokens.end()) {
+            if (safeAstTokens.find(parent)!= safeAstTokens.end())
                 break;
-            }
+            if (astTokens.find(parent)!= astTokens.end())
+                throw InternalError(tok, "AST broken: endless recursion from '" + tok->str() + "'", InternalError::SYNTAX);
             astTokens.insert(parent);
         }
+        safeAstTokens.insert(astTokens.begin(), astTokens.end());
     }
 }
 
@@ -1136,7 +1137,7 @@ bool TokenList::validateToken(const Token* tok) const
 {
     if (!tok)
         return true;
-    for (Token *t = _front; t; t = t->next()) {
+    for (const Token *t = _front; t; t = t->next()) {
         if (tok==t)
             return true;
     }
diff --git a/test/testgarbage.cpp b/test/testgarbage.cpp
@@ -223,6 +223,7 @@ class TestGarbage : public TestFixture {
         TEST_CASE(garbageCode172);
         TEST_CASE(garbageCode173); // #6781
         TEST_CASE(garbageCode174); // #7356
+        TEST_CASE(garbageCode175);
         TEST_CASE(garbageValueFlow);
         TEST_CASE(garbageSymbolDatabase);
         TEST_CASE(garbageAST);
@@ -1464,6 +1465,15 @@ class TestGarbage : public TestFixture {
     void garbageCode174() { // #7356
         checkCode("{r e() { w*constD = (())D = cast< }}");
     }
+
+    void garbageCode175() { // #7027
+        ASSERT_THROW(checkCode("int f() {\n"
+                               "  int i , j;\n"
+                               "  for ( i = t3 , i < t1 ; i++ )\n"
+                               "    for ( j = 0 ; j < = j++ )\n"
+                               "        return t1 ,\n"
+                               "}"), InternalError);
+    }
 };
 
 REGISTER_TEST(TestGarbage)

Original file line number	Diff line number	Diff line change
`@@ -1098,7 +1098,7 @@ void TokenList::createAst()`
`1098`	`1098`
`1099`	`1099`	`void TokenList::validateAst()`
`1100`	`1100`	`{`
`1101`		`- std::set < const Token* > astTokens;`
	`1101`	`+ std::set < const Token* > safeAstTokens;`
`1102`	`1102`	`// Verify that ast looks ok`
`1103`	`1103`	`for (const Token *tok = _front; tok; tok = tok->next()) {`
`1104`	`1104`	`// Syntax error if binary operator only has 1 operand`
`@@ -1111,14 +1111,15 @@ void TokenList::validateAst()`
`1111`	`1111`
`1112`	`1112`	`// check for endless recursion`
`1113`	`1113`	`const Token* parent=tok;`
	`1114`	`+ std::set < const Token* > astTokens;`
`1114`	`1115`	`while ((parent = parent->astParent()) != nullptr) {`
`1115`		`- if (parent==tok)`
`1116`		`- throw InternalError(tok, "AST broken: endless recursion from '" + tok->str() + "'", InternalError::SYNTAX);`
`1117`		`- if (astTokens.find(parent)!= astTokens.end()) {`
	`1116`	`+ if (safeAstTokens.find(parent)!= safeAstTokens.end())`
`1118`	`1117`	`break;`
`1119`		`- }`
	`1118`	`+ if (astTokens.find(parent)!= astTokens.end())`
	`1119`	`+ throw InternalError(tok, "AST broken: endless recursion from '" + tok->str() + "'", InternalError::SYNTAX);`
`1120`	`1120`	`astTokens.insert(parent);`
`1121`	`1121`	`}`
	`1122`	`+ safeAstTokens.insert(astTokens.begin(), astTokens.end());`
`1122`	`1123`	`}`
`1123`	`1124`	`}`
`1124`	`1125`
`@@ -1136,7 +1137,7 @@ bool TokenList::validateToken(const Token* tok) const`
`1136`	`1137`	`{`
`1137`	`1138`	`if (!tok)`
`1138`	`1139`	`return true;`
`1139`		`- for (Token *t = _front; t; t = t->next()) {`
	`1140`	`+ for (const Token *t = _front; t; t = t->next()) {`
`1140`	`1141`	`if (tok==t)`
`1141`	`1142`	`return true;`
`1142`	`1143`	`}`