Example 8: Designing a 'descendent::' search

As we saw in Example 7, there's often a need to perform an exhaustive search of a collection of items-statements in that case. To provide this capability, the API exposes the function:

 ktc_forAllSubtreeNodes(ktc_tree_t, int (*callback)(ktc_tree_t, void*), void*);

This function performs a depth-first search of the subtree under the specified start node, providing a simple way of searching a compound statement (or any other collection) for a particular pattern or patterns.

Another feature of this API is that, unlike the class member iterator we used in Example 3, this function allows us to pass state data to the callback, eliminating the need for global state. We can define an arbitrary data structure to carry state and pass it into this API so it will get passed into our callback whenever it's invoked. The callback can drive the next step of the API by returning zero (keep searching), 1 (stop searching), or 2 (stop searching child nodes, but keep looking at siblings at this depth level).

For the purpose of this example, we're going to pass an array of traversal rules (TRULE) as our state data to a callback function that will attempt the traversal, and if successful, print out a suitable message to the build log.

 #include <stdio.h>
 #include <XPath_plugins.h>
 #include <ktcAPI.h>
   
 // This function is called for each node found by ktc_forAllSubtreeNodes()
 static int nodeCheck(ktc_tree_t node, void* data)
 {
   node = traverse(node, (TRULE*)data);
   if( node != 0 )
     fprintf(stderr, "Assignment to %s\n", ktc_getIdentifier(node));
   return 0;
 }
   
 int logAssignmentsEx(ktc_tree_t node)
 {
   ktc_semanticInfo_t si = ktc_getSemanticInfo(node);
   fprintf(stderr, "Looking for assignments in function %s\n", ktc_sema_getQualifiedName(si));
  
   // Incoming 'node' is a FuncDef node, so let's get into its CompoundStmt
   // This is the equivalent of the KAST expression:
   //   // FuncDef / FuncBody / Stmt::CompoundStmt
   TRULE stmts[] = {
     {cid_FuncBody, tid_Any},
     {cid_Stmt, tid_CompoundStmt},
     {0, 0}
   };
   node = traverse(node, stmts);
   
   // This set of traversal rules looks for "a = b"
   TRULE idexpr[] = {
     {cid_Expr, tid_BinaryExpr},
     {cid_Left, tid_IdExpr},
     {0, 0}
   };
   ktc_forAllSubtreeNodes(node, nodeCheck, idexpr);
   
   // This set of traversal rules looks for "this->a = b"
   TRULE memexpr[] = {
     {cid_Expr, tid_BinaryExpr},
     {cid_Left, tid_MemberExpr},
     {cid_Name, tid_Any},
     {0, 0}
   };
   ktc_forAllSubtreeNodes(node, nodeCheck, memexpr);
  
   return 1;
 }
  
 HOOKS_SET_START
   ...
   XPath_register_int_hook("logAssignmentsEx", logAssignmentsEx);
 HOOKS_SET_END

This function accomplishes the 'descendent::' search objective of our exercise. The next stage for a real-world custom checker function might be to validate the expression statement as an assignment to a member variable in the appropriate class (for example, extend the context data to carry around the semantic information for the class), but that's beyond the scope of this tutorial.