Using clang matchers to detect sequence of patterns

Question

Is it possible to use clang matchers to identify sequence of patterns in a program?

For example I need to find cases in which pattern1 happens before pattern2.

For instance:

Pattern1 = assigning a value to pointer P
pattern2 = dereferencing pointer P

I can identify cases that pattern1 and pattern2 happen in the code, but is it possible to specify an ordering? (say pattern1 has to happen before pattern2 and only match those cases) Thanks!

Answer 1

Correct Answer

In reality traversing ASTs for sequence patterning (which is the basis of static analysis) is not really the correct approach because you DON'T know whether the statement pattern1 is ACTUALLY going to happen before pattern2

Consider

 int foo() {
       int a = 0;
       int *b;
       int c = -1;
       if(c < 0) goto fixit;
 nowhat:
       b = &a;
 fixit: 
       c = *b;
       goto nowhat;
 }

As you can see AST is not going to help here but CFG is the correct thing to use.

Somewhat of an answer using ASTs

If you look at the Traversal Matchers in AST (v6.0.0) they are, pretty much, hierarchical in nature. You are looking to extend the matching to look for siblings.

Much of what I am about to get into assumes that you know how to implement a custom AST matcher. If not, it is explained rather nicely by Manu Sánchez in his Writing AST Matchers for libclang blog post.

Not sure if he gets into actually writing a sibling matcher, but he comes very close to it, so start there and then you have to implement something akin to this:

Let's say given the code:

  class P {}; class Q {}; class R {};

We want to be able to do something like:

 (matcher = recordDecl(hasName("P"), \
        hasNextSibling(recordDecl(hasName("R"))))`

You can combine matchesChild and matchesParent in AstMatchFinder class and traverse the children of the parent of the current cursor (these would be the siblings :P). Read the footnotes as you would have to implement BoundCursors in order to avoid runaway recursion.