teemperor created this revision.
teemperor added reviewers: v.g.vassilev, zaks.anna.
teemperor added a subscriber: cfe-commits.
The ASTStructure class generates data for performant searching Stmts with
similar structure.
http://reviews.llvm.org/D20795
Files:
include/clang/AST/ASTStructure.h
include/clang/Basic/SourceManager.h
lib/AST/ASTStructure.cpp
lib/AST/CMakeLists.txt
lib/Sema/SemaChecking.cpp
unittests/AST/ASTStructureTest.cpp
unittests/AST/CMakeLists.txt
Index: unittests/AST/CMakeLists.txt
===================================================================
--- unittests/AST/CMakeLists.txt
+++ unittests/AST/CMakeLists.txt
@@ -5,6 +5,7 @@
add_clang_unittest(ASTTests
ASTContextParentMapTest.cpp
ASTImporterTest.cpp
+ ASTStructureTest.cpp
ASTTypeTraitsTest.cpp
ASTVectorTest.cpp
CommentLexer.cpp
Index: unittests/AST/ASTStructureTest.cpp
===================================================================
--- /dev/null
+++ unittests/AST/ASTStructureTest.cpp
@@ -0,0 +1,679 @@
+//===- unittests/AST/ASTStructureTest.cpp --- AST structure hasing tests-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains tests for ASTStructure.
+//
+//===----------------------------------------------------------------------===//
+
+#include "gtest/gtest.h"
+#include "clang/AST/ASTStructure.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Tooling/Tooling.h"
+
+using namespace clang;
+
+class FunctionFinder : public RecursiveASTVisitor<FunctionFinder> {
+ std::string FunctionName;
+ FunctionDecl *FoundFunction = nullptr;
+
+public:
+ FunctionFinder(const std::string &FunctionName)
+ : FunctionName(FunctionName) {}
+
+ FunctionDecl *getDecl() { return FoundFunction; }
+
+ bool VisitFunctionDecl(FunctionDecl *D) {
+ if (D->getQualifiedNameAsString() == FunctionName) {
+ FoundFunction = D;
+ return false;
+ }
+ return true;
+ }
+};
+
+// Returns true if the declaration with the given qualified name
+// is hashed when processing the given code.
+bool isHashed(const std::string &DeclName, const std::string &code) {
+ auto ASTUnit = tooling::buildASTFromCode(code);
+ ASTContext &ASTContext = ASTUnit->getASTContext();
+
+ auto Hash = ASTStructure(ASTUnit->getASTContext());
+
+ FunctionFinder Finder(DeclName);
+ Finder.TraverseTranslationUnitDecl(ASTContext.getTranslationUnitDecl());
+
+ assert(Finder.getDecl());
+ return Hash.findHash(Finder.getDecl()->getBody()).Success;
+}
+
+class FindStmt : public RecursiveASTVisitor<FindStmt> {
+ Stmt::StmtClass NeededStmtClass;
+ Stmt *FoundStmt = nullptr;
+
+public:
+ FindStmt(Stmt::StmtClass NeededStmtClass)
+ : NeededStmtClass(NeededStmtClass) {}
+
+ Stmt *getStmt() { return FoundStmt; }
+
+ bool VisitStmt(Stmt *S) {
+ if (S->getStmtClass() == NeededStmtClass) {
+ FoundStmt = S;
+ return false;
+ }
+ return true;
+ }
+};
+
+// Returns true if any Stmt with the given class
+// is hashed when processing the given code.
+bool isHashed(Stmt::StmtClass NeededStmtClass, const std::string &code) {
+ auto ASTUnit = tooling::buildASTFromCode(code);
+ ASTContext &ASTContext = ASTUnit->getASTContext();
+
+ auto Hash = ASTStructure(ASTUnit->getASTContext());
+
+ FindStmt Finder(NeededStmtClass);
+ Finder.TraverseTranslationUnitDecl(ASTContext.getTranslationUnitDecl());
+
+ assert(Finder.getStmt());
+ return Hash.findHash(Finder.getStmt()).Success;
+}
+
+// Returns true if the Decls with the given qualified names
+// have similar structure according to ASTStructure.
+bool compareStructure(const std::string &DeclNameA,
+ const std::string &DeclNameB, const std::string &codeA,
+ const std::string &codeB) {
+ auto ASTUnitA = tooling::buildASTFromCodeWithArgs(
+ codeA, {"-std=c++1z", "-fms-extensions"});
+ auto ASTUnitB = tooling::buildASTFromCodeWithArgs(
+ codeB, {"-std=c++1z", "-fms-extensions"});
+
+ auto HashA = ASTStructure(ASTUnitA->getASTContext());
+ auto HashB = ASTStructure(ASTUnitB->getASTContext());
+
+ auto &ASTContextA = ASTUnitA->getASTContext();
+ auto &ASTContextB = ASTUnitB->getASTContext();
+
+ FunctionFinder FinderA(DeclNameA);
+ FinderA.TraverseTranslationUnitDecl(ASTContextA.getTranslationUnitDecl());
+ assert(FinderA.getDecl());
+
+ FunctionFinder FinderB(DeclNameB);
+ FinderB.TraverseTranslationUnitDecl(ASTContextB.getTranslationUnitDecl());
+ assert(FinderB.getDecl());
+
+ auto HashSearchA = HashA.findHash(FinderA.getDecl()->getBody());
+ auto HashSearchB = HashB.findHash(FinderB.getDecl()->getBody());
+ assert(HashSearchA.Success);
+ assert(HashSearchB.Success);
+ return HashSearchA.Hash == HashSearchB.Hash;
+}
+
+// Returns true if the given Stmts
+// have similar structure according to ASTStructure.
+bool compareStmt(const std::string &codeA, const std::string &codeB) {
+ return compareStructure("x", "x", "void x() { " + codeA + "}",
+ "void x() { " + codeB + "}");
+}
+
+TEST(ASTStructure, IfStmt) {
+ ASSERT_TRUE(compareStmt("if (true) {}", "if (false) {}"));
+ ASSERT_FALSE(compareStmt("if (true) { int x; }", "if (false) {}"));
+ ASSERT_FALSE(compareStmt("if (int y = 0) {}", "if (false) {}"));
+}
+
+TEST(ASTStructure, StmtExpr) {
+ ASSERT_TRUE(
+ compareStmt("int v = ({int x = 4; x;});", "int v = ({int y = 5; y;});"));
+ ASSERT_FALSE(compareStmt("int v = ({int x = 4 + 4; x;});",
+ "int v = ({int y = 5; y;});"));
+ ASSERT_FALSE(compareStmt("int v = ({int x = 5; x;});",
+ "int v = ({int y = 5; y++; y;});"));
+}
+
+TEST(ASTStructure, MSDependentExistsStmt) {
+ // Check that __if_exists != __if_not_exists
+ ASSERT_FALSE(compareStructure("x", "x",
+ R"test(
+ template<typename T>
+ void x(T &t) {
+ __if_exists (T::foo) {
+ }
+ }
+ )test",
+ R"test(
+ template<typename T>
+ void x(T &t) {
+ __if_not_exists (T::foo) {
+ }
+ }
+ )test"));
+}
+
+TEST(ASTStructure, DeclStmt) {
+ // Check that types don't influence the structure.
+ ASSERT_TRUE(compareStmt("int y = 0;", "long v = 0;"));
+ // Check that the initialization expression influences the structure.
+ ASSERT_FALSE(compareStmt("int y = 0;", "int y = (1 + 1);"));
+ // Check that multiple declarations != single declarations
+ ASSERT_FALSE(compareStmt("int a, b = 0;", "int b = 0;"));
+}
+
+TEST(ASTStructure, ArraySubscriptExpr) {
+ // Check that the parameter influences the structure
+ ASSERT_FALSE(compareStmt("int i[2]; i[1] = 0;", "int i[2]; i[1 + 0] = 0;"));
+ // Reverse check from above
+ ASSERT_FALSE(
+ compareStmt("int i[2]; (1)[i] = 0;", "int i[2]; (1 + 0)[i] = 0;"));
+ // Previous two checks mixed together.
+ ASSERT_FALSE(
+ compareStmt("int i[2]; (i)[1 + 0] = 0;", "int i[2]; (1 + 0)[i] = 0;"));
+}
+
+TEST(ASTStructure, ConditionalOperator) {
+ ASSERT_TRUE(compareStmt("int y = true ? 1 : 0;", "int x = false ? 0 : 1;"));
+ // first operand different
+ ASSERT_FALSE(
+ compareStmt("int y = true == true ? 1 : 0;", "int y = false ? 1 : 0;"));
+ // second operand different
+ ASSERT_FALSE(
+ compareStmt("int y = true ? 1 : 0;", "int y = true ? 1 + 1 : 0;"));
+ // third operand different
+ ASSERT_FALSE(
+ compareStmt("int y = true ? 1 : 0;", "int y = true ? 1 : 0 + 0;"));
+
+ // Check GNU version is also correctly handled
+ ASSERT_FALSE(compareStmt("int y = 1 ? : 0;", "int y = 1 ? : 0 + 0;"));
+ ASSERT_FALSE(compareStmt("int y = 1 ? : 0;", "int y = 1 + 1 ? : 0;"));
+}
+
+TEST(ASTStructure, CXXFold) {
+ // Different operators influence structure
+ ASSERT_FALSE(compareStructure(
+ "x", "x",
+ "template<class... A> bool x(A... args) { return (... && args); }",
+ "template<class... A> bool x(A... args) { return (... || args); }"));
+ // Right-side vs left-side influences structure
+ ASSERT_FALSE(compareStructure(
+ "x", "x",
+ "template<class... A> bool x(A... args) { return (... && args); }",
+ "template<class... A> bool x(A... args) { return (args && ...); }"));
+}
+
+TEST(ASTStructure, CXXOperatorCallExpr) {
+ // Different operands influence structure
+ ASSERT_FALSE(compareStructure("x", "x",
+ R"test(
+ class X {
+ public:
+ void operator-=(int i);
+ void operator+=(int i);
+ };
+ void x() { X x; x += 1; }
+ )test",
+
+ R"test(
+ class X {
+ public:
+ void operator-=(int i);
+ void operator+=(int i);
+ };
+ void x() { X x; x -= 1; }
+ )test"));
+}
+
+TEST(ASTStructure, CXXTryStmt) {
+ ASSERT_TRUE(compareStmt("try { int x; } catch (int x) {}",
+ "try { int y; } catch (int x) {}"));
+ // Different body influences structure.
+ ASSERT_FALSE(compareStmt("try { int x; } catch (int x) {}",
+ "try { } catch (int x) {}"));
+}
+
+TEST(ASTStructure, DoStmt) {
+ ASSERT_TRUE(compareStmt("do { int x; } while (true);",
+ "do { int y; } while (false);"));
+ // Different body influences structure.
+ ASSERT_FALSE(
+ compareStmt("do { int x; } while (true);", "do { } while (true);"));
+ // Different condition influences structure.
+ ASSERT_FALSE(compareStmt("int v; do { int x; } while ((v = 1));",
+ "int v; do { int y; } while (true);"));
+}
+
+TEST(ASTStructure, GCCAsmStmt) {
+ // Different assembly influences structure
+ ASSERT_FALSE(compareStmt(
+ R"test(
+ int a, b = 1;
+ asm ("mov %1, %0\n\t"
+ "add $1, %0"
+ : "=r" (a)
+ : "r" (b));
+
+ )test",
+ R"test(
+ int a, b = 1;
+ // NOTE: different asm here
+ asm ("mov %1, %1\n\t"
+ "add $1, %0"
+ : "=r" (a)
+ : "r" (b));
+
+ )test"));
+ // Different output operands influences structure
+ ASSERT_FALSE(compareStmt(
+ R"test(
+ int a, b = 1, c = 1;
+ asm ("mov %1, %0\n\t"
+ "add $1, %0"
+ : "=r" (a)
+ : "r" (b));
+ )test",
+ R"test(
+ int a, b = 1, c = 1;
+ asm ("mov %1, %0\n\t"
+ "add $1, %0"
+ : "=r" (a)
+ // NOTE: Different output operands
+ : "r" (b), "r" (c));
+ )test"));
+ // TODO Check different input operands
+}
+
+TEST(ASTStructure, LambdaExpr) {
+ ASSERT_TRUE(compareStmt("auto a = [](){ return 1; };",
+ "auto a = [](){ return 2; };"));
+ // Different lambda body influences structure.
+ ASSERT_FALSE(compareStmt("int i; auto a = [](){ return 2; };",
+ "int i; auto a = [](){ return 1 + 1; };"));
+ // Different capture types influence structure.
+ ASSERT_FALSE(compareStmt("int i; auto a = [i](){ return 1; };",
+ "int i; auto a = [&i](){ return 1; };"));
+ // Different amount of captures influences structure.
+ ASSERT_FALSE(compareStmt("int i, j; auto a = [i](){ return 1; };",
+ "int i, j; auto a = [i, j](){ return 1; };"));
+ // Different function signature influences structure.
+ ASSERT_FALSE(compareStmt("auto a = [](int i){ return i; };",
+ "auto a = [](int i, int b){ return i; };"));
+}
+
+TEST(ASTStructure, CompoundStmt) {
+ ASSERT_TRUE(compareStmt("int x; int y;", "int x; int y;"));
+ // Different amount of Stmts influence structure.
+ ASSERT_FALSE(compareStmt("int x;", "int x; int y;"));
+}
+
+TEST(ASTStructure, Labels) {
+ ASSERT_TRUE(compareStmt("lbl: goto lbl;", "lbl: goto lbl;"));
+ ASSERT_TRUE(compareStmt("void* lbladdr = &&lbl; goto *lbladdr; lbl:;",
+ "void* lbladdr = &&lbl; goto *lbladdr; lbl:;"));
+ // Different label names influence structure.
+ // FIXME: Put lbl names into feature vectors if possible.
+ ASSERT_FALSE(compareStmt("lbl: goto lbl;", "lbl2: goto lbl2;"));
+ // Same as above with indirect goto.
+ ASSERT_FALSE(
+ compareStmt("lbl2:; void* lbladdr = &&lbl; goto *lbladdr; lbl:;",
+ "lbl2:; void* lbladdr = &&lbl2; goto *lbladdr; lbl:;"));
+}
+
+TEST(ASTStructure, WhileStmt) {
+ ASSERT_TRUE(
+ compareStmt("while (true) { int x; }", "while (false) { int y; }"));
+ ASSERT_TRUE(compareStmt("while (int v = 0) { int x; }",
+ "while (int w = 0) { int y; }"));
+ // Different bodies influence structure.
+ ASSERT_FALSE(compareStmt("while (true) { int x; }", "while (false) { }"));
+ // Different condition influences structure.
+ ASSERT_FALSE(compareStmt("int v; while ((v = 0)) { int x; }",
+ "int v; while (false) { int y; }"));
+}
+
+TEST(ASTStructure, NumberLiterals) {
+ // Test that different number literals always
+ // result in the same structure.
+ // Some of the tests have implicit casts in them that also
+ // need to be ignored by ASTStructure to pass the test.
+ ASSERT_TRUE(compareStmt("double x = 1;", "double x = 1l;"));
+ ASSERT_TRUE(compareStmt("double x = 1u;", "double x = 1l;"));
+ ASSERT_TRUE(compareStmt("double x = 1.0;", "long x = 1;"));
+ ASSERT_TRUE(compareStmt("double x = 1.0f;", "double x = 1l;"));
+}
+
+TEST(ASTStructure, AtomicExpr) {
+ ASSERT_TRUE(
+ compareStmt("int i[2]; __atomic_store_n(i, 1, __ATOMIC_RELAXED);",
+ "int j[2]; __atomic_store_n(j, 1, __ATOMIC_RELAXED);"));
+ // Test first argument influences structure.
+ ASSERT_FALSE(
+ compareStmt("int i[2]; __atomic_store_n(i, 1, __ATOMIC_RELAXED);",
+ "int i[2]; __atomic_store_n(i + 1, 1, __ATOMIC_RELAXED);"));
+ // Test second argument influences structure.
+ ASSERT_FALSE(
+ compareStmt("int i[2]; __atomic_store_n(i, 1, __ATOMIC_RELAXED);",
+ "int i[2]; __atomic_store_n(i, 1 + 1, __ATOMIC_RELAXED);"));
+ // Test that different builtin types influence structure.
+ ASSERT_FALSE(
+ compareStmt("int i[2]; __atomic_exchange_n(i, 1, __ATOMIC_RELAXED);",
+ "int i[2]; __atomic_store_n (i, 1, __ATOMIC_RELAXED);"));
+}
+
+TEST(ASTStructure, BinaryOperator) {
+ ASSERT_TRUE(compareStructure("x", "x", "int x() { return 1 + 4 * 8; }",
+ "int x() { return 2 + 3 * 9; }"));
+ // Different operations influence structure.
+ ASSERT_FALSE(compareStructure("x", "x", "int x() { return 1 + 4 - 8; }",
+ "int x() { return 2 + 3 * 9; }"));
+}
+
+TEST(ASTStructure, UnaryOperator) {
+ ASSERT_TRUE(compareStructure("x", "x", "int x() { return -8; }",
+ "int x() { return -9; }"));
+ // Different operations influence structure.
+ ASSERT_FALSE(compareStructure("x", "x", "int x() { return -8; }",
+ "int x() { return +8; }"));
+}
+
+TEST(ASTStructure, InitListExpr) {
+ ASSERT_TRUE(compareStructure(
+ "x", "x", "struct A {int a, b, c; }; void x() { A a = {1, 2, 3}; }",
+ "struct A {int a, b, c; }; void x() { A a = {4, 5, 6}; }"));
+ // Subexprs in the list influence structure.
+ ASSERT_FALSE(compareStructure(
+ "x", "x", "struct A {int a, b, c; }; void x() { A a = {1 + 1, 2, 3}; }",
+ "struct A {int a, b, c; }; void x() { A a = {2, 2, 3}; }"));
+}
+
+TEST(ASTStructure, Casting) {
+ ASSERT_TRUE(compareStructure("x", "x",
+ "int x() { return static_cast<unsigned>(1); }",
+ "int x() { return static_cast<long>(1); }"));
+ // Different cast types don't influence structure.
+ ASSERT_TRUE(compareStructure("x", "x",
+ "int x() { return static_cast<unsigned>(1); }",
+ "int x() { return static_cast<long>(1); }"));
+ // Different kinds of casts influence structure.
+ ASSERT_FALSE(compareStructure(
+ "x", "x", "int i[2] = {0, 0}; int *x() { return static_cast<int *>(i); }",
+ "const int i[2] = {0, 0}; int *x() { return const_cast<int *>(i); }"));
+
+ // Different arguments influence structure.
+ ASSERT_FALSE(
+ compareStructure("x", "x", "int x() { return static_cast<unsigned>(1); }",
+ "int x() { return static_cast<unsigned>(1 + 1); }"));
+ ASSERT_FALSE(compareStructure("x", "x", "int x() { return (int) (1 + 1); }",
+ "int x() { return (int) (1); }"));
+}
+
+TEST(ASTStructure, CXXCatchStmt) {
+ ASSERT_TRUE(
+ compareStmt("try {} catch (long x) {}", "try {} catch (int x) {}"));
+ // Body influences structure.
+ ASSERT_FALSE(
+ compareStmt("try {} catch (...) { int x; }", "try {} catch (...) {}"));
+ // Catch-all influences structure.
+ ASSERT_FALSE(compareStmt("try {} catch (int x) {}", "try {} catch (...) {}"));
+}
+
+TEST(ASTStructure, ForStmt) {
+ // Two functions with different
+ // naming conventions but doing the same need
+ // to have the same structure.
+ ASSERT_TRUE(compareStructure(
+ "array_sum", "ArraySum", "int array_sum(int* array, unsigned len) {\n"
+ " int sum = 0;\n"
+ " for (unsigned i = 0; i < len; i++)\n"
+ " sum += array[i];\n"
+ " return sum;\n"
+ "}\n",
+
+ "int ArraySum(int* InputArray, unsigned Length) {\n"
+ " int Sum = 0;\n"
+ " for (unsigned j = 0; j < Length; j++)\n"
+ " Sum += InputArray[j];\n"
+ " return Sum;\n"
+ "}\n"));
+
+ ASSERT_FALSE(compareStructure(
+ "array_sum", "array_sum", "int array_sum(int* array, unsigned len) {"
+ " int sum = 0;"
+ " for (unsigned i = 0; i < len; i++)"
+ " sum += array[i];"
+ " return sum;"
+ "}",
+
+ "int array_sum(int* array, unsigned len) {"
+ " int sum = 0;"
+ " for (unsigned i = 0; i < len; i++)"
+ " sum += array[i];"
+ " if (sum < 0) return 0;" // Note that we added an if here and so the
+ // structure changed
+ " return sum;"
+ "}"));
+}
+
+// Macro tests
+
+TEST(ASTStructure, MacroTest) {
+ // Code that is an macro argument should be hashed
+ ASSERT_TRUE(isHashed(Stmt::StmtClass::DoStmtClass,
+ R"test(
+ #define GTEST1(Code) void foo() { Code }
+ #define GTEST2(Code) GTEST1({ int gtest_var; Code })
+ GTEST2({
+ do {
+ int i = 0;
+ int j = 2;
+ } while(0);
+ })
+ )test"));
+ // Function is generated by macro and shouldn't be hashed.
+ ASSERT_FALSE(isHashed("foo",
+ R"test(
+ #define GTEST1(Code) void foo() { Code }
+ #define GTEST2(Code) GTEST1({ while(false){} int gtest_var; Code })
+ GTEST2({
+ do {
+ int i = 0;
+ int j = 2;
+ } while(0);
+ })
+ )test"));
+ // Code that is in macro bodies shouldn't be hashed
+ ASSERT_FALSE(isHashed(Stmt::StmtClass::WhileStmtClass,
+ R"test(
+ #define GTEST1(Code) void foo() { Code }
+ #define GTEST2(Code) GTEST1({ while(false){} Code })
+ GTEST2({})
+ )test"));
+}
+
+// Imported tests from the related GSoC 2015 project
+TEST(ASTStructure, GSoC2015CompoundStmt) {
+ ASSERT_TRUE(compareStructure("x", "x",
+ R"test(
+ void x() {
+ int a, b, c, d, e;
+ a++;
+ b--;
+ c++;
+ d--;
+ e--;
+ d*=2;
+ }
+ )test",
+
+ R"test(
+ void x() {
+ int z, x, q, w, r;
+ z++;
+ x--;
+ q++;
+ w--;
+ r--;
+ w*=2;
+ }
+ )test"));
+}
+
+TEST(ASTStructure, GSoC2015CompoundStmtLocals) {
+ ASSERT_TRUE(compareStructure("x", "x",
+ R"test(
+ void x() {
+ int one = 21,
+ two = -1;
+ if (one == 0) {
+ two++;
+ for (two = 0; two < 10; two++) {
+ one--;
+ }
+ one = 21;
+ }
+ }
+ )test",
+
+ R"test(
+ void x() {
+ int a = 21,
+ b = -1;
+ if (a == 0) {
+ b++;
+ for (b = 0; b < 10; b++) {
+ a--;
+ }
+ a = 21;
+ }
+ }
+ )test"));
+}
+
+TEST(ASTStructure, CompoundStmtLocal) {
+ ASSERT_TRUE(compareStructure("x", "x",
+ R"test(
+ int global_one,
+ global_two;
+
+ void x() {
+ global_one = 21;
+ if (global_one == 0) {
+ global_two++;
+ for (global_two = 0; global_two < 10; global_two++) {
+ global_one--;
+ }
+ global_one = 21;
+ }
+ }
+ )test",
+
+ R"test(
+ int global_one,
+ global_two;
+
+ void x() {
+ global_two = 21;
+ if (global_two == 0) {
+ global_one++;
+ for (global_one = 0; global_one < 10; global_one++) {
+ global_two--;
+ }
+ global_two = 21;
+ }
+ }
+ )test"));
+}
+
+// Use case tests
+
+// This is the example from the project proposal:
+// Two test cases testing the setWidth and setHeight method
+// of the Image class. The setHeight test however is an
+// clone of the setWidth test case and should be detected as such.
+TEST(ASTStructure, ImageTest) {
+ ASSERT_TRUE(compareStructure("testWidthRanges", "testHeightRanges",
+ R"test(struct Image {
+ int width() { return 0; }
+ int height() { return 0; }
+ void setWidth(int x) {}
+ void setHeight(int y) {}
+ };
+ void assert(bool);
+ void testWidthRanges() {
+ Image img;
+ img.setWidth(0);
+ assert(img.width() == 0);
+ img.setWidth(1);
+ assert(img.width() == 1);
+ try {
+ img.setWidth(-1);
+ assert(false);
+ } catch (...) { }
+ })test",
+
+ R"test(struct Image {
+ int width() { return 0; }
+ int height() { return 0; }
+ void setWidth(int x) {}
+ void setHeight(int y) {}
+ };
+ void assert(bool);
+ void testHeightRanges() {
+ Image img;
+ img.setHeight(0);
+ assert(img.height() == 0);
+ img.setHeight(1);
+ assert(img.height() == 1);
+ try {
+ // NOTE: Failed to adapt clone here
+ img.setWidth(-1);
+ assert(false);
+ } catch (...) { }
+ })test"));
+
+ ASSERT_FALSE(compareStructure("testWidthRanges", "testHeightRanges",
+ R"test(struct Image {
+ int width() { return 0; }
+ int height() { return 0; }
+ void setWidth(int x) {}
+ void setHeight(int y) {}
+ };
+ void assert(bool);
+ void testWidthRanges() {
+ Image img;
+ img.setWidth(0);
+ assert(img.width() == 0);
+ img.setWidth(1);
+ assert(img.width() == 1);
+ try {
+ img.setWidth(-1);
+ assert(false);
+ } catch (...) { }
+ })test",
+
+ R"test(struct Image {
+ int width() { return 0; }
+ int height() { return 0; }
+ void setWidth(int x) {}
+ void setHeight(int y) {}
+ };
+ void assert(bool);
+ void testHeightRanges() {
+ Image img;
+ img.setHeight(0);
+ assert(img.height() == 0);
+ // NOTE: Missing img.setHeight(1);
+ assert(img.height() == 1);
+ try {
+ // NOTE: Failed to adapt clone here
+ img.setWidth(-1);
+ assert(false);
+ } catch (...) { }
+ })test"));
+}
Index: lib/Sema/SemaChecking.cpp
===================================================================
--- lib/Sema/SemaChecking.cpp
+++ lib/Sema/SemaChecking.cpp
@@ -8144,22 +8144,6 @@
return true;
}
-// Returns true if the SourceLocation is expanded from any macro body.
-// Returns false if the SourceLocation is invalid, is from not in a macro
-// expansion, or is from expanded from a top-level macro argument.
-static bool IsInAnyMacroBody(const SourceManager &SM, SourceLocation Loc) {
- if (Loc.isInvalid())
- return false;
-
- while (Loc.isMacroID()) {
- if (SM.isMacroBodyExpansion(Loc))
- return true;
- Loc = SM.getImmediateMacroCallerLoc(Loc);
- }
-
- return false;
-}
-
/// \brief Diagnose pointers that are always non-null.
/// \param E the expression containing the pointer
/// \param NullKind NPCK_NotNull if E is a cast to bool, otherwise, E is
@@ -8175,8 +8159,8 @@
// Don't warn inside macros.
if (E->getExprLoc().isMacroID()) {
const SourceManager &SM = getSourceManager();
- if (IsInAnyMacroBody(SM, E->getExprLoc()) ||
- IsInAnyMacroBody(SM, Range.getBegin()))
+ if (SM.IsInAnyMacroBody(E->getExprLoc()) ||
+ SM.IsInAnyMacroBody(Range.getBegin()))
return;
}
E = E->IgnoreImpCasts();
Index: lib/AST/CMakeLists.txt
===================================================================
--- lib/AST/CMakeLists.txt
+++ lib/AST/CMakeLists.txt
@@ -7,6 +7,7 @@
ASTDiagnostic.cpp
ASTDumper.cpp
ASTImporter.cpp
+ ASTStructure.cpp
ASTTypeTraits.cpp
AttrImpl.cpp
CXXInheritance.cpp
Index: lib/AST/ASTStructure.cpp
===================================================================
--- /dev/null
+++ lib/AST/ASTStructure.cpp
@@ -0,0 +1,464 @@
+//===--- ASTStructure.cpp - Analyses the structure of an AST ----*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the StructuralHash class.
+//
+//===----------------------------------------------------------------------===//
+
+#include <clang/AST/ASTStructure.h>
+#include <clang/AST/RecursiveASTVisitor.h>
+#include <clang/AST/ASTContext.h>
+
+#include <iostream>
+
+using namespace clang;
+
+namespace {
+
+class StructuralHashVisitor
+ : public RecursiveASTVisitor<StructuralHashVisitor> {
+
+public:
+ explicit StructuralHashVisitor(ASTStructure &Hash, ASTContext &Context)
+ : SH(Hash), Context(Context) {}
+
+ ~StructuralHashVisitor() {
+ // As each hash value is only saved when the calculation of the next
+ // Stmt starts, we need to explicitly save the hash value of
+ // the last Stmt here.
+ SaveCurrentHash();
+ }
+
+ bool shouldTraversePostOrder() const { return true; }
+
+ bool PostVisitStmt(Stmt *S) {
+ // At this point we know that all Visit* calls for the previous Stmt have
+ // finished, so we know save the calculated hash before starting
+ // to calculate the next hash.
+ SaveCurrentHash();
+
+ // PostVisitStmt is the first method to be called for a new
+ // Stmt, so we save what Stmt we are currently processing
+ // for SaveCurrentHash.
+ CurrentStmt = S;
+ // Reset the initial hash code for this Stmt.
+ Hash = 0;
+ ClassHash = S->getStmtClass();
+ // Reset options for the current hash code.
+ SkipHash = false;
+ IgnoreClassHash = false;
+
+ if (shouldSkipStmt(S))
+ return Skip();
+
+ // Incorporate the hash values of all child Stmts into the current.
+ // Hash value.
+ for (Stmt *Child : S->children()) {
+ if (Child == nullptr) {
+ // We use an placeholder value for missing children.
+ CalcHash(313);
+ } else {
+ CalcHash(Child);
+ }
+ }
+
+ return true;
+ }
+
+// Define all PostVisit methods for all possible Stmts.
+#define STMT(CLASS, PARENT) bool PostVisit##CLASS(CLASS *S);
+#include "clang/AST/StmtNodes.inc"
+
+private:
+
+ bool shouldSkipStmt(Stmt *S) {
+ switch (S->getStmtClass()) {
+ case Stmt::FloatingLiteralClass:
+ case Stmt::CXXBoolLiteralExprClass:
+ case Stmt::ObjCBoolLiteralExprClass:
+ case Stmt::IntegerLiteralClass:
+ return false;
+ default:
+ return Context.getSourceManager().IsInAnyMacroBody(S->getLocStart()) ||
+ Context.getSourceManager().IsInAnyMacroBody(S->getLocEnd());
+ }
+ }
+
+ // Marks the current Stmt as no to be processed.
+ // Always returns \c true that it can be called
+ bool Skip() {
+ SkipHash = true;
+ return true;
+ }
+
+ // Merges the given value into the current hash code.
+ void CalcHash(unsigned Value) {
+ // We follow the same idea as Java's hashCode():
+ // Multiply with an prime, then add the new value to the
+ // hash code.
+ Hash *= 53;
+ Hash += Value;
+ }
+
+ void CalcHash(const llvm::StringRef &String) {
+ for (char c : String) {
+ CalcHash(static_cast<unsigned>(c));
+ }
+ }
+
+ // Merges the hash code of the given Stmt into the
+ // current hash code. Stmts that weren't hashed before by this visitor
+ // are ignored.
+ void CalcHash(Stmt *S) {
+ auto I = SH.findHash(S);
+ if (I.Success) {
+ CalcHash(I.Hash);
+ }
+ }
+
+ // Saves the current hash code into the persistent storage of this
+ // ASTStructure.
+ void SaveCurrentHash() {
+ if (SkipHash) {
+ return;
+ }
+ if (!IgnoreClassHash) {
+ Hash += ClassHash;
+ }
+ SH.add(Hash, CurrentStmt);
+ CurrentStmt = nullptr;
+ }
+
+ ASTStructure &SH;
+ ASTContext &Context;
+
+ // The current statement that is being hashed at the moment
+ // or 0 if there is no statement currently hashed.
+ Stmt *CurrentStmt = nullptr;
+
+ // All members specify properties of the hash process for the current
+ // Stmt. They are resetted after the Stmt is successfully hased.
+
+ // If the current hash should not be saved for later use.
+ bool SkipHash = false;
+
+ // The hash value that is calculated right now.
+ unsigned Hash;
+
+ // If true, the current Hash only depends on custom data of the
+ // current Stmt and the child values.
+ // Use case for this are implicit Stmts that need their child to be
+ // processed but shouldn't influence the hash value of the parent.
+ bool IgnoreClassHash = false;
+
+ // A hash value that is unique to the current Stmt class.
+ // By default, this value is merged with the \c Hash variable
+ // for the resulting
+ unsigned ClassHash;
+};
+
+#define DEF_STMT_VISIT(CLASS, CODE) \
+ bool StructuralHashVisitor::PostVisit##CLASS(CLASS *S) { \
+ if (SkipHash) \
+ return true; \
+ { CODE; } \
+ return true; \
+ }
+
+//--- Builtin functionality ------------------------------------------------//
+DEF_STMT_VISIT(ArrayTypeTraitExpr, { CalcHash(S->getTrait()); })
+DEF_STMT_VISIT(AsTypeExpr, {})
+DEF_STMT_VISIT(AtomicExpr, {
+ CalcHash(S->isVolatile());
+ CalcHash(S->getOp());
+})
+DEF_STMT_VISIT(ChooseExpr, {})
+DEF_STMT_VISIT(ConvertVectorExpr, {})
+DEF_STMT_VISIT(CXXNoexceptExpr, {})
+DEF_STMT_VISIT(ExpressionTraitExpr, { CalcHash(S->getTrait()); })
+DEF_STMT_VISIT(ShuffleVectorExpr, {})
+DEF_STMT_VISIT(PredefinedExpr, { CalcHash(S->getIdentType()); })
+DEF_STMT_VISIT(TypeTraitExpr, { CalcHash(S->getTrait()); })
+DEF_STMT_VISIT(VAArgExpr, {})
+
+//--- MS properties --------------------------------------------------------//
+DEF_STMT_VISIT(MSPropertyRefExpr, {})
+DEF_STMT_VISIT(MSPropertySubscriptExpr, {})
+
+//--- Calls ----------------------------------------------------------------//
+DEF_STMT_VISIT(CXXOperatorCallExpr, { CalcHash(S->getOperator()); })
+DEF_STMT_VISIT(CXXMemberCallExpr, {})
+DEF_STMT_VISIT(CallExpr, {})
+
+//--- Invalid code ---------------------------------------------------------//
+// We don't support hasing invalid code, so we skip all Stmts representing
+// invalid code.
+DEF_STMT_VISIT(TypoExpr, { return Skip(); })
+DEF_STMT_VISIT(UnresolvedLookupExpr, { return Skip(); })
+DEF_STMT_VISIT(UnresolvedMemberExpr, { return Skip(); })
+DEF_STMT_VISIT(CXXUnresolvedConstructExpr, { return Skip(); })
+DEF_STMT_VISIT(OverloadExpr, { return Skip(); })
+
+//--- Exceptions -----------------------------------------------------------//
+DEF_STMT_VISIT(CXXThrowExpr, {})
+DEF_STMT_VISIT(CXXCatchStmt, {
+ if (S->getExceptionDecl())
+ CalcHash(829);
+})
+DEF_STMT_VISIT(CXXTryStmt, {})
+DEF_STMT_VISIT(SEHExceptStmt, {})
+DEF_STMT_VISIT(SEHFinallyStmt, {})
+DEF_STMT_VISIT(SEHLeaveStmt, {})
+DEF_STMT_VISIT(SEHTryStmt, {})
+
+//--- Literals -------------------------------------------------------------//
+DEF_STMT_VISIT(CharacterLiteral, {
+ // We treat all literals as integer literals
+ // as the hash is type independent
+ ClassHash = Stmt::StmtClass::IntegerLiteralClass;
+})
+DEF_STMT_VISIT(FloatingLiteral, {
+ // We treat all literals as integer literals
+ // as the hash is type independent
+ ClassHash = Stmt::StmtClass::IntegerLiteralClass;
+})
+DEF_STMT_VISIT(ImaginaryLiteral, {
+ // We treat all literals as integer literals
+ // as the hash is type independent
+ ClassHash = Stmt::StmtClass::IntegerLiteralClass;
+})
+DEF_STMT_VISIT(IntegerLiteral, {})
+
+DEF_STMT_VISIT(ObjCBoolLiteralExpr, {})
+DEF_STMT_VISIT(CXXBoolLiteralExpr, {})
+
+DEF_STMT_VISIT(StringLiteral, {})
+DEF_STMT_VISIT(ObjCStringLiteral, {})
+
+DEF_STMT_VISIT(CompoundLiteralExpr, {})
+
+DEF_STMT_VISIT(GNUNullExpr, {})
+DEF_STMT_VISIT(CXXNullPtrLiteralExpr, {})
+
+// TODO implement hashing for this
+DEF_STMT_VISIT(UserDefinedLiteral, { return Skip(); })
+
+//--- C++-OOP Stmts --------------------------------------------------------//
+DEF_STMT_VISIT(MemberExpr, {})
+DEF_STMT_VISIT(CXXNewExpr, {})
+DEF_STMT_VISIT(CXXThisExpr, {})
+DEF_STMT_VISIT(CXXConstructExpr, {})
+DEF_STMT_VISIT(CXXDeleteExpr, {
+ CalcHash(S->isArrayFormAsWritten());
+ CalcHash(S->isGlobalDelete());
+})
+DEF_STMT_VISIT(DesignatedInitExpr, {})
+DEF_STMT_VISIT(DesignatedInitUpdateExpr, {})
+DEF_STMT_VISIT(NoInitExpr, {})
+DEF_STMT_VISIT(InitListExpr, {})
+DEF_STMT_VISIT(CXXStdInitializerListExpr, {})
+
+DEF_STMT_VISIT(CXXTemporaryObjectExpr, { IgnoreClassHash = true; })
+DEF_STMT_VISIT(CXXDefaultArgExpr, {})
+DEF_STMT_VISIT(CXXDefaultInitExpr, {})
+
+//--- Casts ----------------------------------------------------------------//
+DEF_STMT_VISIT(CXXFunctionalCastExpr, {})
+
+DEF_STMT_VISIT(CXXNamedCastExpr, {})
+DEF_STMT_VISIT(CXXConstCastExpr, {})
+DEF_STMT_VISIT(CXXDynamicCastExpr, {})
+DEF_STMT_VISIT(CXXReinterpretCastExpr, {})
+DEF_STMT_VISIT(CXXStaticCastExpr, {})
+
+DEF_STMT_VISIT(ImplicitCastExpr, { IgnoreClassHash = true; })
+
+DEF_STMT_VISIT(CastExpr, {})
+DEF_STMT_VISIT(ExplicitCastExpr, {})
+DEF_STMT_VISIT(CStyleCastExpr, {})
+DEF_STMT_VISIT(ObjCBridgedCastExpr, { CalcHash(S->getBridgeKind()); })
+
+//--- Miscellaneous Exprs --------------------------------------------------//
+DEF_STMT_VISIT(Expr, {})
+DEF_STMT_VISIT(ParenExpr, {})
+DEF_STMT_VISIT(ArraySubscriptExpr, {})
+DEF_STMT_VISIT(BinaryOperator, { CalcHash(S->getOpcode()); })
+DEF_STMT_VISIT(UnaryOperator, { CalcHash(S->getOpcode()); })
+
+//--- Control flow ---------------------------------------------------------//
+DEF_STMT_VISIT(ForStmt, {})
+DEF_STMT_VISIT(GotoStmt, {})
+DEF_STMT_VISIT(IfStmt, {})
+DEF_STMT_VISIT(WhileStmt, {})
+DEF_STMT_VISIT(IndirectGotoStmt, {})
+DEF_STMT_VISIT(LabelStmt, { CalcHash(S->getDecl()->getName()); })
+DEF_STMT_VISIT(MSDependentExistsStmt, { CalcHash(S->isIfExists()); })
+DEF_STMT_VISIT(AddrLabelExpr, { CalcHash(S->getLabel()->getName()); })
+DEF_STMT_VISIT(BreakStmt, {})
+DEF_STMT_VISIT(CompoundStmt, {})
+DEF_STMT_VISIT(ContinueStmt, {})
+DEF_STMT_VISIT(DoStmt, {})
+
+DEF_STMT_VISIT(SwitchStmt, {})
+DEF_STMT_VISIT(SwitchCase, {})
+DEF_STMT_VISIT(CaseStmt, {})
+DEF_STMT_VISIT(DefaultStmt, {})
+
+DEF_STMT_VISIT(ReturnStmt, {})
+
+DEF_STMT_VISIT(AbstractConditionalOperator, {})
+DEF_STMT_VISIT(BinaryConditionalOperator, {})
+DEF_STMT_VISIT(ConditionalOperator, {})
+
+//--- Objective-C ----------------------------------------------------------//
+DEF_STMT_VISIT(ObjCArrayLiteral, {})
+DEF_STMT_VISIT(ObjCBoxedExpr, {})
+DEF_STMT_VISIT(ObjCDictionaryLiteral, {})
+DEF_STMT_VISIT(ObjCEncodeExpr, {})
+DEF_STMT_VISIT(ObjCIndirectCopyRestoreExpr, { CalcHash(S->shouldCopy()); })
+DEF_STMT_VISIT(ObjCIsaExpr, {})
+DEF_STMT_VISIT(ObjCIvarRefExpr, {})
+DEF_STMT_VISIT(ObjCMessageExpr, {})
+DEF_STMT_VISIT(ObjCPropertyRefExpr, {
+ CalcHash(S->isSuperReceiver());
+ CalcHash(S->isImplicitProperty());
+})
+DEF_STMT_VISIT(ObjCProtocolExpr, {})
+DEF_STMT_VISIT(ObjCSelectorExpr, {})
+DEF_STMT_VISIT(ObjCSubscriptRefExpr, {})
+DEF_STMT_VISIT(ObjCAtCatchStmt, { CalcHash(S->hasEllipsis()); })
+DEF_STMT_VISIT(ObjCAtFinallyStmt, {})
+DEF_STMT_VISIT(ObjCAtSynchronizedStmt, {})
+DEF_STMT_VISIT(ObjCAtThrowStmt, {})
+DEF_STMT_VISIT(ObjCAtTryStmt, {})
+DEF_STMT_VISIT(ObjCAutoreleasePoolStmt, {})
+DEF_STMT_VISIT(ObjCForCollectionStmt, {})
+
+//--- Miscellaneous Stmts --------------------------------------------------//
+DEF_STMT_VISIT(CXXFoldExpr, {
+ CalcHash(S->isRightFold());
+ CalcHash(S->getOperator());
+})
+DEF_STMT_VISIT(StmtExpr, {})
+DEF_STMT_VISIT(ExprWithCleanups, {})
+DEF_STMT_VISIT(GenericSelectionExpr, { CalcHash(S->getNumAssocs()); })
+DEF_STMT_VISIT(LambdaExpr, {
+ for (const LambdaCapture &C : S->captures()) {
+ CalcHash(C.isPackExpansion());
+ CalcHash(C.getCaptureKind());
+ }
+ CalcHash(S->isGenericLambda());
+ CalcHash(S->isMutable());
+ CalcHash(S->getCallOperator()->param_size());
+})
+DEF_STMT_VISIT(OpaqueValueExpr, { IgnoreClassHash = true; })
+DEF_STMT_VISIT(MaterializeTemporaryExpr, { IgnoreClassHash = true; })
+DEF_STMT_VISIT(SubstNonTypeTemplateParmExpr, {})
+DEF_STMT_VISIT(SubstNonTypeTemplateParmPackExpr, {})
+DEF_STMT_VISIT(DeclStmt, {
+ auto numDecls = std::distance(S->decl_begin(), S->decl_end());
+ CalcHash(537u + static_cast<unsigned>(numDecls));
+})
+
+DEF_STMT_VISIT(CompoundAssignOperator, {})
+DEF_STMT_VISIT(CXXBindTemporaryExpr, {})
+DEF_STMT_VISIT(NullStmt, {})
+DEF_STMT_VISIT(CXXScalarValueInitExpr, {})
+DEF_STMT_VISIT(ImplicitValueInitExpr, {})
+DEF_STMT_VISIT(OffsetOfExpr, {})
+DEF_STMT_VISIT(SizeOfPackExpr, {})
+DEF_STMT_VISIT(DeclRefExpr, {})
+DEF_STMT_VISIT(DependentScopeDeclRefExpr, {})
+DEF_STMT_VISIT(CXXPseudoDestructorExpr, {})
+DEF_STMT_VISIT(FunctionParmPackExpr, {})
+DEF_STMT_VISIT(ParenListExpr, {})
+DEF_STMT_VISIT(PackExpansionExpr, {})
+DEF_STMT_VISIT(UnaryExprOrTypeTraitExpr, {})
+DEF_STMT_VISIT(PseudoObjectExpr, {})
+DEF_STMT_VISIT(GCCAsmStmt, {
+ CalcHash(S->isVolatile());
+ CalcHash(S->isSimple());
+ CalcHash(S->getAsmString()->getString());
+ CalcHash(S->getNumOutputs());
+ for (unsigned I = 0, N = S->getNumOutputs(); I != N; ++I) {
+ CalcHash(S->getOutputName(I));
+ VisitStringLiteral(S->getOutputConstraintLiteral(I));
+ }
+ CalcHash(S->getNumInputs());
+ for (unsigned I = 0, N = S->getNumInputs(); I != N; ++I) {
+ CalcHash(S->getInputName(I));
+ CalcHash(S->getInputConstraintLiteral(I));
+ }
+ CalcHash(S->getNumClobbers());
+ for (unsigned I = 0, N = S->getNumClobbers(); I != N; ++I)
+ CalcHash(S->getClobberStringLiteral(I));
+})
+
+// TODO: implement hashing custom data of these Stmts
+DEF_STMT_VISIT(AsmStmt, {})
+DEF_STMT_VISIT(MSAsmStmt, {})
+DEF_STMT_VISIT(CXXForRangeStmt, {})
+DEF_STMT_VISIT(CapturedStmt, {})
+DEF_STMT_VISIT(CoreturnStmt, {})
+DEF_STMT_VISIT(CoroutineBodyStmt, {})
+DEF_STMT_VISIT(CoroutineSuspendExpr, {})
+DEF_STMT_VISIT(AttributedStmt, {})
+DEF_STMT_VISIT(BlockExpr, {})
+DEF_STMT_VISIT(CoawaitExpr, {})
+DEF_STMT_VISIT(CoyieldExpr, {})
+DEF_STMT_VISIT(CUDAKernelCallExpr, {})
+DEF_STMT_VISIT(CXXUuidofExpr, {})
+DEF_STMT_VISIT(ExtVectorElementExpr, {})
+DEF_STMT_VISIT(CXXDependentScopeMemberExpr, {})
+DEF_STMT_VISIT(CXXTypeidExpr, {})
+
+//--- OpenMP ---------------------------------------------------------------//
+// All OMP Stmts don't have any data attached to them,
+// so we can just use the default code.
+DEF_STMT_VISIT(OMPExecutableDirective, {})
+DEF_STMT_VISIT(OMPAtomicDirective, {})
+DEF_STMT_VISIT(OMPBarrierDirective, {})
+DEF_STMT_VISIT(OMPCancelDirective, {})
+DEF_STMT_VISIT(OMPCancellationPointDirective, {})
+DEF_STMT_VISIT(OMPCriticalDirective, {})
+DEF_STMT_VISIT(OMPFlushDirective, {})
+DEF_STMT_VISIT(OMPLoopDirective, {})
+DEF_STMT_VISIT(OMPDistributeDirective, {})
+DEF_STMT_VISIT(OMPForDirective, {})
+DEF_STMT_VISIT(OMPForSimdDirective, {})
+DEF_STMT_VISIT(OMPParallelForDirective, {})
+DEF_STMT_VISIT(OMPParallelForSimdDirective, {})
+DEF_STMT_VISIT(OMPSimdDirective, {})
+DEF_STMT_VISIT(OMPTaskLoopDirective, {})
+DEF_STMT_VISIT(OMPTaskLoopSimdDirective, {})
+DEF_STMT_VISIT(OMPMasterDirective, {})
+DEF_STMT_VISIT(OMPOrderedDirective, {})
+DEF_STMT_VISIT(OMPParallelDirective, {})
+DEF_STMT_VISIT(OMPParallelSectionsDirective, {})
+DEF_STMT_VISIT(OMPSectionDirective, {})
+DEF_STMT_VISIT(OMPSectionsDirective, {})
+DEF_STMT_VISIT(OMPSingleDirective, {})
+DEF_STMT_VISIT(OMPTargetDataDirective, {})
+DEF_STMT_VISIT(OMPTargetDirective, {})
+DEF_STMT_VISIT(OMPTargetEnterDataDirective, {})
+DEF_STMT_VISIT(OMPTargetExitDataDirective, {})
+DEF_STMT_VISIT(OMPTargetParallelDirective, {})
+DEF_STMT_VISIT(OMPTargetParallelForDirective, {})
+DEF_STMT_VISIT(OMPTaskDirective, {})
+DEF_STMT_VISIT(OMPTaskgroupDirective, {})
+DEF_STMT_VISIT(OMPTaskwaitDirective, {})
+DEF_STMT_VISIT(OMPTaskyieldDirective, {})
+DEF_STMT_VISIT(OMPTeamsDirective, {})
+DEF_STMT_VISIT(OMPArraySectionExpr, {})
+}
+
+ASTStructure::ASTStructure(ASTContext &Context) {
+ StructuralHashVisitor visitor(*this, Context);
+ visitor.TraverseDecl(Context.getTranslationUnitDecl());
+}
Index: include/clang/Basic/SourceManager.h
===================================================================
--- include/clang/Basic/SourceManager.h
+++ include/clang/Basic/SourceManager.h
@@ -1169,6 +1169,28 @@
return getDecomposedLoc(SpellingLoc).second;
}
+
+ //
+
+ /// \brief Tests whether the given source location is expanded from any
+ /// macro body.
+ ///
+ /// \returns Returns true if the SourceLocation is expanded from any macro
+ /// body. Returns false if the SourceLocation is invalid, is from not in a
+ /// macro expansion, or is from expanded from a top-level macro argument.
+ bool IsInAnyMacroBody(SourceLocation Loc) const {
+ if (Loc.isInvalid())
+ return false;
+
+ while (Loc.isMacroID()) {
+ if (isMacroBodyExpansion(Loc))
+ return true;
+ Loc = getImmediateMacroCallerLoc(Loc);
+ }
+
+ return false;
+ }
+
/// \brief Tests whether the given source location represents a macro
/// argument's expansion into the function-like macro definition.
///
Index: include/clang/AST/ASTStructure.h
===================================================================
--- /dev/null
+++ include/clang/AST/ASTStructure.h
@@ -0,0 +1,88 @@
+//===--- AstStructure.h - Analyses the structure of an AST -----*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the ASTStructure class, which can analyse the structure
+// of an AST.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_STRUCTURALHASH_H
+#define LLVM_CLANG_AST_STRUCTURALHASH_H
+
+#include <unordered_map>
+#include <clang/AST/Stmt.h>
+
+namespace clang {
+
+/// ASTStructure - This class analyses the structure of the Stmts
+/// in a given AST and is intended to be used to find sub-trees with identical
+/// structure. The structure of a tree equals the functionality of the
+/// code behind it.
+///
+/// Specifically this class provides a locality-sensitive hash function
+/// for Stmts that generates colliding hash values
+/// for nodes with the same structure.
+///
+/// This is done by only hashing
+/// information that describes structure (e.g. the type of each
+/// node).
+/// Other information such as the names of variables, classes
+/// and other parts of the program are ignored.
+class ASTStructure {
+
+ std::unordered_map<const Stmt *, unsigned> HashedStmts;
+
+public:
+ ///
+ /// \brief ASTStructure generates information about the Stmts in the AST.
+ ///
+ /// \param Context The AST that shall be analyzed.
+ ///
+ /// Analyses the Stmts in the given AST and stores all information
+ /// about their structure in the newly created ASTStructure object.
+ explicit ASTStructure(ASTContext &Context);
+
+ struct HashSearchResult {
+ unsigned Hash;
+ bool Success;
+ };
+
+ ///
+ /// \brief Looks up the structure hash code for the given Stmt
+ /// in the storage of this ASTStructure object.
+ ///
+ /// \param S the given Stmt.
+ ///
+ /// \returns A \c HashSearchResult containing information of whether
+ /// the search was successful and if yes the found hash code.
+ ///
+ /// The structure hash code is a integer describing the structure
+ /// of the given Stmt. Stmts with an equal structure hash code probably
+ /// have the same structure.
+ HashSearchResult findHash(const Stmt *S) {
+ auto I = HashedStmts.find(S);
+ if (I == HashedStmts.end()) {
+ return {0, false};
+ }
+ return {I->second, true};
+ }
+ ///
+ /// \brief Adds with the given Stmt with the associated structure hash code
+ /// to the storage of this ASTStructure object.
+ ///
+ /// \param Hash the hash code of the given Stmt.
+ /// \param S the given Stmt.
+ void add(unsigned Hash, const Stmt *S) {
+ HashedStmts.insert(std::make_pair(S, Hash));
+ }
+};
+
+} // end namespace clang
+
+#endif
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
