Further Reading

This guide explains in-depth the different features for navigating through AST in different ways.

For XPath API, read more here: XPath API

Basic API

In our rule’s visit method, we have access to a BaseNode type object (com.als.core.ast.BaseNode interface). This object represents the AST root node in which the source code we are analyzing has become, and it is the starting point from which to seek the information needed to determine whether if the code shows a violation of the standard to be certified.

To browse through the nodes, we have the TreeNode class (com.als.core.ast.TreeNode), which is an implementation of BaseNode. Therefore, we can turn our BaseNode nodes into TreeNode and vice versa at any time.

BaseNode <–> TreeNode conversion

import com.als.core.AbstractRule;
import com.als.core.RuleContext;
import com.als.core.ast.BaseNode;

public class MyDummyRule extends AbstractRule {
  @Override
  protected void visit (BaseNode root, final RuleContext ctx) {
    // rule body...
  }
}

TreeNode type objects provide us almost unlimited ways to move all along the AST, looking for sibling, descendant or ancestor of any level nodes and meeting the specific characteristics we want. Among the most useful methods, we have:

child: it searches between “child” nodes (level 1 descendants of a node).
find: it searches inside the subtree in the current node (level ‘n’ descendants of a node).
parent: it returns the current node’s parent.
ancestor: it searches among all the ancestors of the current node.
rightSibling / leftSibling: it returns the node immediately to the right/left of the current node.

Checking conditions in the nodes: TreeNode and NodePredicate

Other TreeNode objects functionalities, not directly related to navigation, but very useful, are:

count: it counts the number of nodes of a certain type in the subtree in the current node.
countAncestors: it counts the number of nodes of certain type among the ancestors of the current one.
findImage: it returns the node image (usually, the concrete item of the source code under analysis, which is represented by the current node).
findLine: it returns the number of lines of the node (corresponding to the line number within the file of the source code under analysis in which the concrete item is, which is represented by the current node).
has: it checks if there is a node in the subtree within the current node.
hasAncestor: it checks if there is a node among the ascendants of the current node.
hasChildren: it checks if there is a node among the children (level 1 descendants) of the current node.
isLeaf / isRoot: it checks if the current node is a leaf or the root node.
isNull / isNotNull: it checks if the current object is a null node (very useful for testing after search operations, since those can return TreeNode.NULLTREE, NullNode.NULL o null objects when they do not find a node that meets the specified conditions).
isTypeName: it checks the current node’s type.

Most search methods allow arguments to establish specific conditions that the nodes to search should meet. These conditions may be as simple as “the node must be of a certain type” or something like “the node must be of a certain type, and have a certain image, and be descendant/ancestor of…“.

For these cases, we can define a NodePredicate (com.als.core.ast.NodePredicate) object:

NodePredicate sample:

NodePredicate nodeToFind = new NodePredicate {
  public boolean is(BaseNode node) {
    TreeNode tNode = TreeNode.on(node);
    return tNode.isTypeName("MethodDeclaration") &amp;&amp;
      tNode.findImage().equals("methodName") &amp;&amp;
      tNode.hasAncestor("InterfaceDeclaration");
  }
};


@Override
protected void visit (BaseNode root, final RuleContext ctx) {
  TreeNode methodDeclar = TreeNode.on(root).find(nodeToFind);
}

We have already mentioned in Getting Started with Rule Development the visitor strategy, with which we could go all along AST nodes from a given one, using the accept methods provided by TreeNode.

Visitor strategy:

import com.als.core.ast.TreeNode;
import com.als.core.ast.NodeVisitor;


public class MyDummyRule extends AbstractRule {
  @Override
  protected void visit(BaseNode root, final RuleContext ctx) {
    // this 'visit' is executed on each one of the source code files under analysis
    TreeNode.on(root).accept(new NodeVisitor() {
      public void visit(BaseNode node) {
       // this 'visit' is executed on each one of the nodes in the AST of the current file under analysis
     // ...
    }
  });
 }
}

We can apply the same strategy, using the NodeVisitor objects (com.als.core.ast.NodeVisitor), to any subtree within the tree we are dealing with:

Applying Visitor:

@Override
public void visit(BaseNode root, final RuleContext ctx) {


final NodeVisitor methodVisitor = new NodeVisitor(){
  public void visit(BaseNode node) {
    // do something on an AST which represents a method
  }
};


TreeNode.on(root).accept(new NodeVisitor(){
  public void visit(BaseNode classDeclar) {
    // search for class or interface declarations
    if (!classDeclar.isTypeName("ClassOrInterfaceDeclaration")) return;
    TreeNode clazz = TreeNode.on(classDeclar);
    // traverse clazz/interface searching for method declarations
    // but avoiding methods declared in nested classes
    clazz.child("ClassOrInterfaceBody").acceptChildren(new NodeVisitor() {
    // Visitor will visits this node, then its immediate children
    public void visit(BaseNode methodDeclar) {
      TreeNode method = TreeNode.on(methodDeclar);
      if (!method.hasChildren("MethodDeclaration")) return;
      // apply the 'methodVisitor' on each method found
      method.accept(methodVisitor);
      }
    });
   }
 });
}

High-Level AST and Low-Level AST

You may have noticed, working with Kiuwan Rule Developer, that the node types of the generated AST vary depending on the language of the source code we are analyzing.

This is something you should always keep in mind when developing your rules: each rule will be specific for the analysis of a particular programming language.

The nodes that Kiuwan Rule Developer shows us by default are the low-level nodes, Low-Level AST, which show in detail each one of the processed code elements. However, for certain rules, perhaps it is not necessary so much detail and it would be enough with a somewhat higher abstraction.

Therefore, with certain technologies (Java, C++, C#, Cobol, Javascript), we can access the high-level nodes, High-Level AST, representing elements to a less detailed level. To see one level of abstraction or the other, in Kiuwan Rule Developer‘s Syntax Tree tab, we can find Full Tree and Summarized Tree options (only available in those technologies that support them).

Low-Level AST <–> High-Level AST conversion

protected void visit (BaseNode root, final RuleContext ctx) {
  TreeNode lowLevelNode = TreeNode.on(root);  // BaseNode to TreeNode
  TreeNode highLevelNode = ASTSwitcher.getHighLevelNode(lowLevelNode);
  lowLevelNode = ASTSwitcher.getLowLevelNode(highLevelNode);
}

This guide shows you how to implement development rules with Query API.

The com.optimyth.qaking.highlevelapi.dsl.Query class represents a query in the syntax tree, in this case, the High-Level Tree (HLT).

Query provides a fluent interface to perform searches in the AST, specifying a sequence of operations (find, filter, navigate, visit...), which will be done starting from a given set of nodes. Each operation will be set passing primitive objects (NodePredicate, NodeVisitor, NodeSearch, or Navigation) so then a call to one of the available run() methods will be made to execute all the registered operations.

Once the nodes of interest are found, the report() operation will generate in the report one violation for each node reached.

Primitive objects

com.als.core.ast.NodeVisitor: apply some logic to the node. Execution sequence on a tree or sub-tree.
com.als.core.ast.NodePredicate: check if a node meets a series of clauses or conditions.
com.optimyth.qaking.highlevelapi.nodeset.NodeSearch: find some node starting from a given one. For example, find the declaration of a variable from its use, the definition of a function from its call...
com.optimyth.qaking.highlevelapi.navigation.Navigation: navigate through the AST from a given node, possibly applying some other primitive object.
com.optimyth.qaking.highlevelapi.dsl.QueryOperation: definition of a new operation.

The available operations to perform the queries can be classified as follows:

Operation	Effect	Signature
custom operation	Registers a custom operation	operation(QueryOperation)
execute query	Executes the query, specifying initial node(s)	run(Rule, RuleContext) run(Rule, RuleContext, BaseNode...) run(Rule, RuleContext, NodeSet)
filter	Filter current context nodes	filter(NodePredicate) filter(Query)
find following a navigation	Find nodes traversed by navigation, matching predicate	find(NodePredicate, Navigation)
find sucessors	Find all successors matching predicate	find(NodePredicate match)
navigate	Traverses the given navigation from current (context) nodes	navigate(Navigation) navigate(NodeSearch) navigate(String xpath)
navigate & visit	Visit each node reachable via given navigation with visitor	visit(NodeVisitor, Navigation)
report	Emit a rule violation for each current context node or snapshot, using the ToViolation object to custimize violation to emit	report() report(String snapshot) report(ToViolation) report(String, ToViolation)
snapshot	Create a "snapshot" of current context nodeset, giving it a name	snapshot(String)
visit	Visits each node in current context	visit(NodeVisitor)

Most of these operations return the same Query instance so that calls can be chained. Besides, available actions and primitives are typically thread-safe, so you could use the Query object as a rule instance field and make the query.run() call from the visit method of the rule to process each source file under analysis.

As a simple example, imagine you want to report the getter methods that return null. Using the Query API, your rule could have an implementation that:

Predicate isGetter = ...;
NodePredicate returnsNull = ...;

Query q = Query.query()
               .find(methods(isGetter))
               .filter(returnsNull)
               .report();

... // execute query from high-level root node 
q.run(rule, ctx, ctx.getHighLevelTree());

The rule will be in a declarative format and coded in a few lines, leaving the thickest part of the implementation in the declaration of the appropriate primitives for each case.

For the supported languages (Abap, C#, Cobol, C++, Java, Javascript, PHP), we can find primitives, both predicates and navigations, already predefined, available to use directly in our rules. In each case, they will be found in the jar of the technology parser; for instance, we will have the classes com.optimyth.qaking.java.hla.JavaPredicates (where we can find the isGetter and returnsNull methods, used in the example above, already defined) and com.optimyth.qaking.java.hla.JavaNavigations.

Besides, we can always define those specific classes we need. To do that specifically in the case of the predicates, it is possible to use both the own class com.als.core.ast.NodePredicate, already mentioned, and the one defined in Google Guava library (com.google.common.base.Predicate), which is included in the classpath for development.

Let's see a complete example; in this case, a rule that detects, in Java classes, not-used variables (local, class fields, or parameters).

Java rule implementation example - Query API

import com.als.core.AbstractRule;
import com.als.core.RuleContext;
import com.als.core.ast.BaseNode;
import com.als.core.ast.NodePredicate;
import com.als.core.util.NodeToStr;
import com.optimyth.qaking.highlevelapi.dsl.Query;
import com.optimyth.qaking.highlevelapi.nodeset.ToViolation;
import com.optimyth.qaking.java.hla.ast.JavaVariable;
 

import staticcom.als.core.ast.NodePredicates.*;
import staticcom.optimyth.qaking.highlevelapi.dsl.Query.query;
import staticcom.optimyth.qaking.highlevelapi.nodeset.ToViolation.extraMessage;
import staticcom.optimyth.qaking.java.hla.JavaPredicates.*;
  

public class UnusedVars extends AbstractRule {
  // For reporting the name of the unused var
  private static final ToViolation reportVarName = extraMessage(new NodeToStr() {
    public String apply(BaseNode node) {
      return"unused " + ((JavaVariable) node).getName();
    }
  });
  
  // Match variable declarations of interest
  private static final NodePredicate varsPredicate = or(
    localVariablePred,
    // Unused private fields can only be used in other classes using reflection
    // In Java, some class fields like serialVersionUID or serialPersistentFields
    // are used by JVM, not by user code. How could you add such exceptions?
    and(instanceVariablePred, isPrivatePred),
    parameterPred
  );

  
  // What is unused var?
  private static final Query unusedVars= query()
    .find( varsPredicate )
    // An unused var should not have initialization with side-effects
    // (because then, declaration cannot be removed)
    .filter(not(hasSideEffectInInitPred))
    .filter(not(hasUsages))
    .report( reportVarName);

  @Override protected void visit(BaseNode root, RuleContext ctx) {
    unusedVars.run(this, ctx, ctx.getHighLevelTree()); // rule is simply query execution
  }

}

Another one is the implementation of a rule for Cobol files that detects the use of the DISPLAY statement in arithmetical operations.

Cobol rule implementation example - Query API
import com.als.cobol.CobolAstUtil;
import com.als.cobol.rules.AbstractCobolRule;
import com.als.core.RuleContext;
import com.als.core.ast.BaseNode;
import com.als.core.ast.NodePredicate;
import com.optimyth.qaking.cobol.ast.CobolNode;
import com.optimyth.qaking.cobol.hla.ast.DataEntry;
import com.optimyth.qaking.cobol.util.Declarations;
import com.optimyth.qaking.highlevelapi.dsl.Query;
  

import static com.als.cobol.UtilCobol.STATEMENT;
import static com.optimyth.qaking.cobol.hla.primitives.CobolPredicates.ARITH_STATEMENTS;


public class NoDisplayDataInArithmeticOp extends AbstractCobolRule {
  
 // Match QualifiedDataName operand in arithmetic statement
 private final NodePredicate dataRefInArithStmt = new NodePredicate() {
  // To check that data item reference iside arithmetic statement
  private NodePredicate onArithStatement = new NodePredicate() {
   public boolean is(BaseNode node) {
    CobolNode containerStmt = ((CobolNode)node).ancestor(STATEMENT).child(0);
    return ARITH_STATEMENTS.is(containerStmt);
   }
  };
  public boolean is(BaseNode node) {
   if(node.isTypeName("QualifiedDataName")) {
    CobolNode n = (CobolNode)node;
    return onArithStatement.is(n);
   }
   return false;
  }
 };

  
 // Match data item with DISPLAY or DISPLAY-1 types
 private final NodePredicate isDisplayType = new NodePredicate() {
  public boolean is(BaseNode node) {
   DataEntry de = Declarations.getDataEntry(node); // Find data item declaration in DATA DIVISION
   if(de == null) return false; // no data item declaration in DATA DIVISION
   String type = de.getType();
   return "DISPLAY".equalsIgnoreCase(type) || "DISPLAY-1".equalsIgnoreCase(type);
  }
 };


 // "Match data reference in arithmetic expression where the data item type is DISPLAY type"
 private final Query query = Query.query()
  .find(dataRefInArithStmt) // get data references in arithmetic statement
  .filter(isDisplayType) // ... but only DISPLAY / DISPLAY-1 types
  .report();

  
 @Override protected void visit(BaseNode root, RuleContext ctx) {
  query.run(this, ctx, CobolAstUtil.getProcedureDivision(root));
 } 

}

If you know XPath, the class com.optimyth.qaking.highlevelapi.navigation.Region is available, which will provide Navigation instances for each XPath axis.

Region name XPath axis Nodes traversed

SELF self:: context node itself
ROOT / go to the root node
CHILDREN child:: immediate children
PARENT parent:: parent node
ANCESTORS ancestor-or-self:: ancestors, including self
SUCCESSORS descendant:: subtree nodes from a node, not including itself
LEFTSIBLINGS preceding-sibling:: Siblings of node at left, not including itself
RIGHTSIBLINGS following-sibling:: Siblings of node at right, not including itself
PRECEDING preceding:: Nodes appearing before node (before in code text)
FOLLOWING following:: Nodes appearing after node (before in code text)

As you can guess, this API provides great power and potential, so we encourage you to examine and test the available options when developing your own rules.

To expand and consolidate the concepts that we have presented, please consult the documentation in the development\doc directory of Kiuwan Local Analyzer distribution.

Rule Development Manual

This guide explains the rule development facilities in Kiuwan.

Kiuwan engine is the static analysis platform embedded in Kiuwan products. With it, it is possible to perform many different types of static analysis on source code:

Verification of compliance with coding standards: Are standards being followed in the software implementation?
Inefficiencies in code (examples: string concatenation, improper use of synchronization, unnecessary object construction...).
Security checks (like tainting propagation, to see if a user-controller input can reach a "sink", a resource like a database, without proper validation).
Dependency analysis, to detect design smells (god class, implementation dependency, low cohesion, and high coupling), or architecture violations (a layer is using another layer, and should not).
Code metrics evaluation. A code metric on a software artifact represents a certain property (like size or coupling) of the analyzed software.

Each check is coded in a unit, called Kiuwan RULE, comprising of:

Check code (a Java class),
A rule definition (XML file) including configuration and documentation.

The rule definition XML descriptor contains:

An identifier,
An implementation classname,
Technologies that analyze,
Message/description,
Priority (1=critical ... 5=informative),
Configuration properties,
Examples for a bad / repair code,
Benefits and incovenients for adopting the rule, etc.

Rules are aggregated in rulesets (parts of the quality model), used during static analysis.

When a flaw (non-compliant code) is detected in a certain source file, a violation is emitted and added to the analysis report. Metric rules create a metric value for a certain software artifact instead.

The guide exposes the different alternatives the rule programmer has when developing rules for automated static analysis verifications, and how to extend the Kiuwan engine platform for more advanced usages.

Prerequisites: Kiuwan is developed in Java, so good skills in Java programming (JDK only, not J2EE) and design principles are needed for rule developers.

Note: For detailed documentation of the API classes, consult the JavaDocs provided with the API deliverable.

API alternatives

There are different alternatives for developing rules in Kiuwan, according to the level of abstraction: Abstract Syntax Tree, NavigableNode, XPath, or Query API.

Certain primitive objects could be passed in many parts of the rules API and are used in many places in the Kiuwan API:

Primitive	Effect	Method to implement
NodeVisitor	Apply logic to node	void visit(BaseNode)
NodePredicate	Does this node satisfy X?	boolean is(BaseNode)
NodeSearch	"Find a related node from a given node"	BaseNode apply(BaseNode)
Navigation	Perform certain navigation on AST starting at given node, possibly applying another primitive	NodeSet navigate(BaseNode) NodeSet navigate(BaseNode, NodePredicate) void visit(BaseNode, NodeVisitor)

As examples of typical NodeSearch, think of finding the variable declaration for a certain variable usage, function definition for a call, container node for any other node, etc.

Navigation combines traversal + primitive, used in Query API (discussed later).

Abstract Syntax Tree (low-level and high-level) API

Kiuwan engine analyzers parse source code using a programming language grammar parser. The parser translates plain text to a tree-based representation of the source code (named Abstract Syntax Tree). This tree is a low-level representation of the source code file and represents in a very detailed way all the elements, from top-level language elements (like class or function definitions) to the literals and expressions contained in the source file. Low-level AST is named LLA in what follows.

For certain languages, an alternate high-level AST (HLA) is produced from the low-level AST. The high-level AST represents the main structures in source code, frequently expressed as nodes in a language-independent way.

The low-level AST (LLA) may have too much detail for what is necessary to implement many rules. The high-level AST is a condensed view of the source syntax, showing relevant items for the target programming language (programs, types, functions, statements), but remove punctuation nodes, or detail nodes (e.g. expressions are leaf nodes in the HLA).

For processing AST (both LLA or HLA), rules could extend com.als.core.AbstractRule, and implement logic in the method void visit(BaseNode ast, RuleContext ruleContext). The first argument is the AST root node (e.g. a CompilationUnit in Java grammar), and the rule logic must navigate the AST to look for the condition that the rule detects. Navigating the AST is rather difficult, but this level of abstraction is adequate for rules that need access to the finest details of the source code, that may not be afforded with the rest of the APIs.

Technically, AST is provided as a tree where each node implements the interface com.als.core.ast.BaseNode. For some technologies, nodes extend this interface (like com.als.core.ast.NavigableNode or com.als.core.ast.TreeNode, see below) that provide extra facilities for searching nodes in the AST.

For most languages, a single AST node type for each language construct is provided (named CobolNode, PhpNode, CppNode, ...) implementing the common interface BaseNode.
For a few languages (Java, JSP, PowerScript, VB6), a different Java type is provided for each different grammar construct. The AST nodes provide accessors (getters) to fetch properties.

To help processing AST for common needs, a set of utility classes are provided for each technology. See JavaDoc for full details.

NavigableNode / TreeNode API

This API (com.als.core.ast.TreeNode class) decorates a BaseNode for any language, exposing NavigableNode interface that simplifies node searches and navigations. Could be used for many simple rules that do not need advanced static analysis facilities.

Note: For certain technologies (like Cobol, JavaScript or PHP), LLA already implements NavigableNode, which does not need to be wrapped in TreeNode to access extra search methods exposed.

TreeNode is a decorated BaseNode that support many navigation operations. Provide methods for doing something (finding first, finding all, counting, checking, navigating...) on a certain navigation "axis" in the tree concerning wrapped nodes (children, successors, brothers at left/right, parent, ancestors), using certain constraints (a predicate, node types), and using a processing paradigm (a NodeVisitor, code in a for-each loop...).

Decorating a BaseNode is simple: TreeNode node = TreeNode.on(baseNode).

Child (direct or immediate children) axis:

acceptChildren(NodeVisitor), apply a certain operation (encoded in visitor) to this node and its immediate children.
child(NodePredicate), to find first direct child matching predicate.
findAllChildren(NodePredicate), returns list of child nodes matching predicate.
countChildren(NodePredicate) and similar methods, to count children matching predicate.
hasChildren(NodePredicate), return true if at least one child matches predicate.

TreeNode itself is an iterable that iterates over direct children:

for(TreeNode child : treenode) {...}

will iterate on treenode children, left to right.

Successor (subtree) axis:

find(NodePredicate, boolean), to look for first node matching certain condition
findAll(NodePredicate, boolean), to look for all occurences of nodes matching a certain condition
accept(NodeVisitor, boolean), to apply a certain operation to this node and all of its descendants (parent-first)
has(NodePredicate) and similar methods, for checking if at least one of the successors matches predicate
acceptChildrenFirst(NodeVisitor, boolean), to apply a certain operation to all of this node descendants, then to this node (children-first)
subtreeBreadthFirst(NodePredicate), to use in a for-each loop to process successor nodes matching predicate (traversed breadth-first)
subtreeDepthFirst(NodePredicate), also with for-each loop as above (but traversed depth-first)
count(NodePredicate), to count nodes matching predicate

Parent (antecessor) axis:

findFirstAncestor(NodePredicate) or ancestor(NodePredicate), to look for first node matching certain condition
findAllAncestors(NodePredicate), to look for all occurrences of nodes matching a certain condition
acceptAncestors(NodeVisitor), to apply a certain operation to this node and all of its descendants
countAncestors(NodePredicate), count of ancestors matching predicate
hasAncestor(NodePredicate), returns true if at least one of the ancestors in path from this to root matched predicate
onAncestor(NodePredicate), Iterable that permits to process in a for-loop each node in path from this to root matching predicate

Sibling axis:

getLeftSibling() The immediate brother to the left
getLeftSiblings() Iterator to brothers to the left, traversed from right to left.
onLeftSiblings(NodePredicate) Iterable for processing left brothers that match predicate in a for-each loop.
getRightSibling() The immediate brother to the right
getRightSiblings() Iterator to brothers to the right, traversed from left to right.
onRightSiblings(NodePredicate) Iterable for processing right brothers that match predicate in a for-each loop.

Additionally, there are safe simple navigation methods that check if the requested parent or child exists, returning NULLTREE so methods can be chained without fear of runtime exceptions.

Example:

TreeNode n = TreeNode.on(node);
// from n, get first child, then first child of type {{Expression}},
// then go up to parent, then go to second node, then first, then first again
n = n.child(0).child("Expression").parent().path(1, 0, 0);
if(n.isNotNull()) ....; // Voila! such complex navigation reached node of interest...

In rules this facility can be used to focus on "node detection" logic, with navigation logic hidden in the navigation methods of this class.

Sample usage:

new TreeNode(root).find("ProcedureDivision").accept(new NodeVisitor() {
  public void visit(BaseNode node) {
    // Logic for any node under Cobol PROCEDURE DIVISION
  }
}

XPath rules

XPath is a language for searching in trees (typically XML trees, but it could be applied to AST as well).

The simplest way to code a Kiuwan rule is an XPath rule, that express using XPath notation the condition that AST nodes must match to be considered violations of the rule. An XPath rule is declarative, and does not need to be programmed, but require a certain knowledge of the AST.

For example, the following XPath expression detects loops without initialization nor update, that may be replaced by easier-to-understand while loops (last predicate exludes "for each" loops):

//ForStatement
  [count(*)>1]
  [not(ForInit)]
  [not(ForUpdate)]
  [not(Type and Expression and Statement)]

Adequate for simple rules. Typically, naming conventions could be easily verified using XPath expressions.

For example, if we are looking for the usages of System.gc() in Java code, the rule may use the XPath expression:

//Name[@Image='System.gc' or @Image='java.lang.System.gc']

Note: XPath attribute axis (@property) fetches a AST node property (getter returning a primitive type). For example, @Image invokes getImage() method on context AST nodes.

XPath-based rules could be implemented configuring com.als.core.rule.XPath, passing proper XPath expression in xpath rule property.

Many convenient XPath functions are provided, for full details on XPath, see the XPath section.

Query API

The class com.optimyth.qaking.highlevelapi.dsl.Query represents a query in an abstract syntax tree (or high-level tree). Query provides a fluent interface for expressing a search on AST, specifying the sequence of operations (find, filter, navigate, visit) to perform, starting at a given set of nodes. Each operation is configured by passing primitive objects (NodePredicate, NodeVisitor, NodeSearch, or Navigation). Then one of the run() methods should be called to execute the operations registered.

As a simple example, imagine that you need to report getter methods that return null. Such a rule could be implemented in a few code lines:

Predicate isGetter = ...;
NodePredicate returnsNull = ...;
Query q = Query.query()
  .find(methods(isGetter))
  .filter(returnsNull)
  .report();
...
// execute query from high-level root node
q.run(rule, ctx, ctx.getHighLevelTree());

Appropriate primitives could be found for each supported language; for example, for Java, com.optimyth.qaking.java.hla.JavaPredicates provides instances for returnsNull and isGetter.

When a query is executed using run() over a certain set of initial nodes (typically the root HLA or LLA node), nodes reached by each operation are remembered and act as context nodes for the next operation in sequence.

Operations that could be registered in a Query are:

Operation	Effect	Signature
find sucessors	Find all successors matching predicate	find(NodePredicate match)
find following a navigation	Find nodes traversed by navigation, matching predicate	find(NodePredicate match, Navigation navigation)
navigate	Traverses the given navigation from current (context) nodes	navigate(Navigation) navigate(NodeSearch) navigate(String xpath)
filter	Filter current context nodes	filter(NodePredicate) filter(Query)
visit	Visits each node in current context	visit(NodeVisitor)
navigate & visit	Visit each node reachable via given navigation with visitor	visit(NodeVisitor, Navigation)
custom operation	Registers a custom operation	operation(QueryOperation)
snapshot	Create a "snapshot" of current context nodeset, giving it a name	snapshot(String)
report	Emit a rule violation for each current context node or snapshot, using the ToViolation object to custimize violation to emit	report() report(String snapshot) report(ToViolation) report(String, ToViolation)
execute query	Executes the query, specifying initial node(s)	run(Rule, RuleContext) run(Rule, RuleContext, BaseNode...) run(Rule, RuleContext, NodeSet)

If you know about XPath, the com.optimyth.qaking.highlevelapi.navigation.Region provides Navigation instances for each XPath axis:

Region name	XPath axis	Nodes traversed
SELF	self::	context node itself
ROOT	/	go to root node
CHILDREN	child::	immediate children
PARENT	parent::	parent node
ANCESTORS	ancestor-or-self::	ancestors, including self
SUCCESSORS	descendant::	subtree nodes from node, not including itself
LEFTSIBLINGS	preceding-sibling::	Siblings of node at left, not including itself
RIGHTSIBLINGS	following-sibling::	Siblings of node at right, not including itself
PRECEDING	preceding::	Nodes appearing before node (before in code text)
FOLLOWING	following::	Nodes appearing after node (before in code text)

NOTE - Thread-safety: Query is thread-safe if primitives passed are thread-safe. This means that you may use a Query object as instance field of a rule, and call query.run() on the visit() method of the rule to process each input source, in multi-thread analysis this do not produce race conditions.

Examples:

Find unused vars (Java)

private static final Query unusedVars = Query.query()
  .find( varsPredicate )
  // An unused var should not have initialization with side-effects
  // (because then, declaration cannot be removed)
  .filter( not(hasSideEffectInInitPred) )
  .filter( not(hasUsages) )
  .report( reportVarName ); // special reporting

See com.optimyth.qaking.rules.samples.java.UnusedVars sample rule for the full implementation.

Avoid data references in arithmetic expressions where data item is DISPLAY (Cobol)

private final Query query = Query.query()
  .find(dataRefInArithStmt) // get data references in arithmetic statement
  .filter(isDisplayType) // ... but only DISPLAY / DISPLAY-1 types
  .report();

See com.optimyth.qaking.rules.samples.cobol.NoDisplayDataInArithmeticOp sample rule for full implementation.

Additional static analysis facilities

Static analysis is more than a syntax issue. Some well-known static analysis elements are: type resolution, symbol table, data-flow analysis, tainting propagation, constant or expression propagation, semantic metadata for technology APIs (and many more).

For certain technologies, extended static analysis facilities are provided. Most of them are located in the highLevelAPI.jar and codeAnalysis.jar JAR files.

Control-flow graph (CFG) and data-flow analysis

The control-flow graph is a graph where nodes represent statements and other code items (like variable declarations or function declarations). Nodes are connected according to the control flow (a statement s1 is connected to statement s2 if s2 may follow execution of s1 under certain conditions). Traversal of the CFG is useful to follow control logic, and certain properties of data flowing through the statements in the CFG could be derived statically (this is called "data-flow analysis").

An instance of the CFG is compiled for each behavioral unit (like a function or method). For some languages (e.g. in Cobol) the behavioral unit considered could be more global (e.g. the whole program in Cobol).

Dummy start and end nodes are added to the CFG (typically, all exit points terminate in the end node, while the start node represents the entry point to the behavioral unit).

Two objects are used: DataFlowNode (represents a node in the CFG) and DataFlowGraph (represents a CFG for a certain behavioral unit). These elements are under com.optimyth.qaking.codeanalysis.controlflow the package.

AST nodes for languages with CFG support implement the HasCFG interface:

DataFlowGraph getDataFlowGraph()
boolean hasDataFlowGraph()
DataFlowNode getDataFlowNode()
boolean hasDataFlowNode()

To build the CFG containing a certain AST node, the API provides instances of ControlFlowSupport, builder of the CFG from the AST for a particular behavioral unit. For example, for JavaScript and Cobol:

DataFlowGraph cfg = new JavascriptControlFlowSupport(ctx).getFlowGraph(function);
DataFlowGraph cfg =  new 
CobolControlFlowSupport(ctx).getFlowGraph(procedureDivision);

Two operations are typical with the CFG:

Traversal (forward- or backward-, depth- or breadth-first) from a starting point, that could traverse the CFG (without infinite loops, as there may be cycles in the CFG) following the desired navigation. The com.optimyth.qaking.codeanalysis.controlflow.ControlFlowNavigator provides the navigation methods, typically calling a user-provided ControlFlowVisitor with each CFG node traversed in the navigation.
Process all potential paths between two CFG nodes: com.optimyth.qaking.codeanalysis.controlflow.paths.PathFinder, that discover potential distinct paths during a certain CFG traversal and calls an user-provided PathVisitor with each matching path found.

Library metadata

Document the behavior for items (global variables, macros, functions / methods, types / classes...) in external APIs (e.g. class or function libraries common for target technology).

Library metadata facility permits to declare the metadata information (in an XML file descriptor) for each 'library', and to find metadata for a particular entity.

A Libraries object provides a façade for queries on library metadata. The relevant classes are located under package com.optimyth.qaking.codeanalysis.metadata.model and subpackages.

Typically, the base rule (or utility) for technologies supporting Library Metadata provides a Libraries loadLibraries(RuleContext) method to get the Libraries instance for a particular programming language.

Entity items have different incarnations: LibraryDescriptor, FieldDescriptor, FunctionDescriptor, GlobalObject, HeaderDescriptor, MacroDef, Type, ClassDescriptor, MethodDescriptor.

Library Metadata is used by tainting propagation facility in order to document the behaviour of API items. For tainting propagation, items may declare a Neutralization (declaring a point where inputs are "neutralized", Source (declaring an external input point) or Sink (declaring a point where the API gives access to a resource).

See javadoc for full details. Library Metadata XML descriptors could be found under the JKQA_HOME/libraries directory.

Tainting propagation

Detect a dataflow path connecting a 'source' (info input) and 'sink' (a point where API provides access to a sensitive resource). Relevant for security flaws (like 'injection vulnerabilities': SQL injection, cross-site scripting, etc.) Leverages control-flow graph and library metadata to perform.

Variables affected by sources (like external inputs to program) are 'tainted', and this condition propagates according to the semantics of statements and API items between sources and sinks. Taintedness status may be intercepted possibly by a 'neutralization' (a point where data is checked or transformed), that 'untaints' the data.

For technologies with tainting propagation support, a tainting rule simply declares what sources, sinks and neutralizations should be considered. For example, a "Path Traversal" security rule in PHP is simply:

Path traversal rule for PHP

public class PathTraversalRule extends AbstractPhpTaintingRule {
  private static final String SINK_KIND = "path_traversal";


  private List<SinkChecker> checkers;


  @Override public void initialize(RuleContext ctx) {
    super.initialize(ctx);
    Predicate<SinkDef> sinksPred = getPredicate(SINK_KIND);
    checkers = getSinkCheckers(sinksPred, ctx);
  }


  @Override protected void visit(BaseNode root, RuleContext ctx) {
    propagateTainting(root, getSourcesPredicate(), checkers, ctx);
  }
}

Local / Global Symbol Table

Model code items with a given name (a "symbol": functions, types, global variables...) that could be later searched for.

Symbol Table could be Global (GST: all source code inputs are parsed and processed first to compile global symbols), or Local (LST: only the symbols declared in current source unit are compiled).

Global Symbol Table (GST)

Entities modelled in the GST are: SourceFile, Function, Program, Relation, Type, TypeMethod, Variable (under package {{com.optimyth.qaking.globalmodel.model }}, see JavaDoc for full details).

Certain dependencies (like inheritance) are modelled in the GST.

The GST facilitates global analysis, but should be used with caution, as it is not as efficient in execution times as pure local analysis.

Note: As building the GST is expensive, it is built only if at least one of the rules in the analysis declares its intention to use GST (rule decorated with the @UseGlobalSymbolTable annotation).

The façade SymbolTable (in com.optimyth.qaking.globalmodel.query package) provides access to the GST:

SymbolTable SymbolTable.get(RuleContext); // Get instance representing the GST

SymbolTable provides many query methods for finding item(s) in the GST, but additional query utilities are provided for extensive searches on certain item types:

FunctionQuery: queries for function and method entities.
InheritanceQuery: queries on type inheritance information.
TypeQuery: queries over types (classes).
VariableQuery: queries over instance variables (fields) and global variables.

See javadoc for com.optimyth.qaking.globalmodel.query package for full details.

For example, to check for indirect inheritance on the java.io.Serializable interface:

SymbolTable table = SymbolTable.get(ctx);
if(table != null) {
  // Check only indirect inheritance (direct inheritance is processed in visit)
  InheritanceQuery inh = new InheritanceQuery(table);
  for(InheritanceRow rel : inh.findInheritanceRows("supername='java.io.Serializable' AND level>1")) {
    String subtype = rel.getSubtype();
    Variable field = table.findVariable(FIELD_NAME, subtype, "java");
    ...
  }
}

See sample rule com.optimyth.qaking.rules.samples.java.SerializableWithVersionUid under JKQA_HOME/doc/samples for full details.

SymbolTable provide a mechanism for getting AST of code files containing declarations referenced in current AST ("inter-AST searches"). As an example, imagine that the definition of functions called at certain points need to be processed, and that definition is not in the code file with the call:

SymbolTable table = SymbolTable.get(ctx);
...
BaseNode callNode = ...;
String calledFunction = FunctionUtil.getShortFunctionName(callNode);
// Find definition for the called function, by name
Function def = table.findFunction(calledFunction, null, null);
if(def != null) {
  // Loads the AST with the function declaration
  BaseNode defNode = table.loadNode(def);
  ...
}

Local Symbol Table (LST)

For certain technologies (see table below), a Local Symbol Table (LST) could be compiled efficiently to model specific symbols defined in current code unit. LSTs are used, for example, for locating usages for a variable declaration, or declaration for a variable usage.

A few examples may help to understand how LSTs are compiled and used:

LST for PHP

LocalSymbolTable symtab = LocalSymbolTableBuilder.getSymbolTable((PhpNode)root);
symtab.visitForward(new Visitor() {
  public boolean onSymbol(Symbol symbol) {
    // ignore symbols with usages or global
    if(symbol.hasUsages() || symbol.isMagicConstant()) return true;


    if(symbol.getKind()== SymbolKind.PARAMETER) {
      // Check that the parameter symbol is in a function with body.
      // Interface methods and abstract methods do not use their parameters
      if(hasBody(symbol.getNode())) {
        report(symbol, "{0}: unused parameter {1}", ctx);
      }


    } else if(isPrivateField(symbol)) {
      report(symbol, "{0}: unused private field {1}", ctx);



    } else if(isPrivateMethod(symbol)) {
      report(symbol, "{0}: unused private method {1}()", ctx);
    }
    return true;
  }
});

See JavaDoc for com.optimyth.qaking.php.symboltable.LocalSymbolTable class.

LST for JavaScript

// Build symbol table for this source unit
LocalSymbolTable symTable = LocalSymbolTable.build((JSNode)root);


// Fetch configured globals in source code comment
Set<String> configuredGlobals = getGlobals((JSNode) root);


// Report unused vars
List<SymbolEntry> unusedList = symTable.getUnusedSymbols(UNUSED, NodePredicate.TRUE);
for(SymbolEntry unused : unusedList) {
  String msg = getMessage() + ": unused symbol " + unused.getSymbol().getName();
  reportViolation(ctx, unused.getDefinition(), msg);
}


// Report undefined vars used
List<SymbolEntry> undefList = symTable.getGlobalSymbols(UNDEF);
for(SymbolEntry undef : undefList) {
  if(configuredGlobals.contains( undef.getName() )) continue;
  String msg = getMessage() + ": undefined symbol " + undef.getSymbol().getName();


  for(JSNode undefUsage : undef.getUsages()) {
    reportViolation(ctx, undefUsage, msg);
  }
}

See sample rule com.optimyth.qaking.rules.samples.javascript.AvoidUndefUnusedVars.

LST for Java

public class AvoidLocalVariablesDifferUpperLowerCase extends AbstractRule {


    protected void visit(BaseNode root, final RuleContext ctx) {
    if (!(root instanceof ASTCompilationUnit)) return;
    ASTCompilationUnit cu = (ASTCompilationUnit) root;
    initLocalSymbolTable(cu);


    TreeNode.on(root).accept(new NodeVisitor() {
      public void visit(BaseNode node) {
        if(node instanceof ASTLocalVariableDeclaration) {
          ASTLocalVariableDeclaration varDecl = (ASTLocalVariableDeclaration)node;
          Set<String> lowerVars = Sets.newHashSet();
          for(ASTVariableDeclaratorId varName : varDecl.getVariableIds()) {
            lowerVars.add(varName.getImage().toLowerCase());
          }

          Scope scope = varDecl.getScope();
          while(scope instanceof LocalScope) {
            findCollidingVar((LocalScope)scope, varDecl, lowerVars, ctx);
            scope = scope.getParent();
          }
        }
      }
    });
    }

  /**
   * Check that local variables in scope collide with the variable names declared in varDecl
   * and stored in lowerVars set. If collision, emit a violation
   */
  protected void findCollidingVar(LocalScope scope, ASTLocalVariableDeclaration varDecl,
                                  Set<String> lowerVars, RuleContext ctx) {
    for(VariableNameDeclaration vn : scope.getVariableDeclarations().keySet()) {
      AccessNode influencingDecl = vn.getAccessNodeParent();
      if(varDecl==influencingDecl || !(influencingDecl instanceof ASTLocalVariableDeclaration)) continue;
      if(influencingDecl.getEndLine() > varDecl.getBeginLine()) continue;
      ASTVariableDeclaratorId id = vn.getDeclaratorId();
      String varname = id.getImage().toLowerCase();
      if(lowerVars.contains(varname)) {
        report(this, varDecl, ctx);
      }
    }
  }
}

Tips for programming static analysis Rules

Rule programming best practices

To simplify rule programming and produce more robust and maintainable programming rules, see the following best practice tips.

Use `BaseNode` interface whenever possible

Never use implementation node classes, like the generic Node interface or SimpleNode class generated by the parser generator (e.g. JavaCC). The reason is obvious: An AST tree may have nodes generated by different parsers (heterogeneous tree). BaseNode is the common denominator, all AST nodes implement this interface. If not, your rule may produce a ClassCastException when traversing AST nodes generated by the parsers for embedded languages (like SQL nodes in the COBOL AST tree, when EXEC SQL sentences are parsed). To avoid problems, and implement rules less dependent on potential grammar changes, it is advisable to use, when possible, the BaseNode interface.

If you need to check for the language the node belongs to, use BaseNode.getLanguage(). This is a simple way of determining which language the node belongs to.

Use common tree navigation facilities, instead of implementing your own "utility methods" for traversing AST trees.

The TreeNode decorator is a powerful AST tree navigation helper. You can traverse trees rooted at a certain BaseNode using a NodeVisitor (recursively or traversing the node and its immediate children), fetch for nodes that match a certain condition (using NodePredicate), or traverse the siblings of a certain node. See the javadoc for BaseTree for further information.

You may add utility methods if you need certain reusable extraction operations, but in this case, use the TreeNode facilities to implement such methods, avoiding usage of the specific AST implementation classes, as mentioned in the previous tip.

Never add "artificial state" to your rule classes.

Rules should be, if possible, "stateless", with no side-effects. Never add instance variables (like a node list) that depend on the nodes of the currently processed file. If you do not obey this simple rule, your rule must clean-up such artificial state before processing the next source input, increasing memory footprint and opening the opportunity for all kinds of errors (when a list of nodes is not cleaned-up, the rule will see in the list nodes belonging to previous input sources, producing bugs difficult to resolve).

Exceptions to this rule are:

Configuration state (for rules that use complex expressions, lists of accepted/rejected tokens, and so on). Rules may override the initialize() method, that will be invoked by the framework at analysis startup, when the rule should prepare complex configuration items (like pre-compiling regular expressions to be used in the visit() method). Remember that, for simple properties, this is not necessary (getProperty() methods provide access to rule parameters). For example, a numeric threshold does not need to be an instance variable.

Global state (for global rules). Global rules are rules that will first visit all input sources, compiling a global model that will be checked for when all input sources are processed. The rule here needs to remember a model of all input sources, before looking in that model for certain conditions. A dependencies rule that checks for dependencies between input sources is a typical rule of this kind: The visit() method implement the model building phase, and the postProcess() rule method will be used to check for the intended conditions in the model. But remember that local rules (rules that inspect a single input source at a time) are the most usual pattern for static analysis.

Emit violations judiciously

For naming/format convention rules, when a line does not match the convention, a RuleViolation could be emitted. The problem with this approach is that it could produce a rule violations storm, when hundreds or thousands of violations are registered in the violations report, making the vision on the most important issues to fix first more difficult. So it is better to decide before if the more conservative approach of emitting a single violation per file, to tell programmers which files do not follow the convention, could fit the bill avoiding the violations storm.

One violation per rule or single violation per file?

It depends on the importance of the convention. Emitting a violation for all lines tells the programmer where each violation can be found, but at the cost of contaminating both the violations report and the confidence factors, hiding other rules (like potential bugs) that should be visible. So as a trade-off, for such convention-checking rules, the single violation per file approach is better.

Avoid plain-text checks

The purpose of the AST is to present a source code structure, in a way that simplifies structural checks (as the AST eliminates issues like the exact source code format). So if the AST contains the needed information for the rule revision, use it.

There are certain kind of rules that do need access to the source code: most parsers discard comments (comments are not seen in the AST) and, due to grammar limitations, even essential source code is not available in the image field of the AST nodes. When this happens, use the FileContents interface as follows:

FileContents contents = ctx.getOriginalFileContents(); // Or ctx.getTransformedFileContents()
    String code = contents.getContent(); // To process all code content
    String[] codeLines = contents.getLines(); // To process all lines
    String line = contents.getLine( node.getBeginLine()-1 ); // Direct access to the code line for node
    ... put your checks on code, codeLines or line here ...

When you find yourself creating complicated regular expressions to fetch code elements. Think twice if the AST tree provides the needed information.

The static analysis framework provides a FileContents bean that gives direct access to source code contents/lines, without the need to re-read the input file (and leave open file descriptors around).

Using FileContents for processing source code text is safer (no IOException possible), more efficient (as the input files are read only once), and more maintainable (as your rule "business" code is not polluted with file I/O).

Try to limit dependencies with the underlying grammar

If your rule code is coupled too much with the grammar artifacts (node classes, node, and token images, node hierarchies for language constructs, etc.), then changes in the grammar and generated parser will produce AST trees that will break your rules. Of course, this is easy to say, but very difficult to follow. Rules usually need to locate nodes that match grammar rules. But try to limit such dependencies on underlying grammar as much as possible.

Rule programming anti-patterns

The next section explains some anti-patterns, that you could follow if you want your rules to be unmaintainable, break for difficult-to-track causes, consume lots of memory, and lead to an OutOfMemory error.

Add artificial state to your rules (in the form of instance variables)

As said before, local rules should not have side-effects between different source code inputs. Never use RuleContext it as an instance parameter, pass it as method parameter from the visit() method to the helper methods that need it. And never collect (in local rules) lists of AST nodes: use local variables instead (that will be garbage collected quickly when the variable is out of scope, without the need to clear collections at the end of the visit method), and pass them to the utility method. Or better, use AST navigation facilities provided by TreeNode, to process nodes of interest locally, and avoid creating node collections and iterating over such collections later. Your code will be crystal-clear.

In the past, we have seen many rule programmers following this anti-pattern, copying&pasting many code blocks that use unnecessary instance variables. This anti-pattern should be never followed (but remember that rule configuration and global model data are exceptions to the avoid artificial state rule).

Read source code files liberally

Once again, never read source files. Use FileContents to access source code contents most easily.

If every rule of N reads the file, and you have M files, your I/O rate will be N*M (N times more than the M rate that the static analyzer itself needs).

If you have 1,000 rules and 1,000 input sources, you are reading files 1,000,000 times.

Your static analysis performance will crawl and take hours to complete. Your rules are intelligent, so to demonstrate how important they are, read files liberally, to demonstrate how much complexity your brain can manage.

Put nonsense comments in your code, but refuse to document the rule purpose and how the condition is checked.

Some things that do not add value to your code are:

Useless code comments, like single-line comments at the end of a method or class,
@param javadoc entries for obvious parameters,
Or trivial documents to a trivial line of rule source code.

If your rule purpose is not documented in JavaDoc comments, and complex checks are not documented appropriately, your rule will not be maintainable. Make sure to document exceptions, put sample code with the kind of conditions detected by the rule, and so on.

XPath API

XPath is a language for searching in trees (typically XML trees, but it could be applied to AST as well).

The simplest way to code a Kiuwan rule is with an XPath rule that expresses, using XPath notation, the condition that AST nodes must match to be considered violations of the rule. An XPath rule is declarative and does not need to be programmed, but requires a certain knowledge of the AST. You may use the Rule Developer to parse the AST for sample input code and execute XPath expressions against the parsed AST (XPath operates on both low-level and high-level ASTs).

For example, the following XPath expression detects loops without initialization or update, which may be replaced by easier-to-understand while loops (first predicate admit for(; (wink) loops, while last predicate excludes "for each" loops):

//ForStatement
  [count(*)>1]
  [not(ForInit)]
  [not(ForUpdate)]
  [not(LocalVariableDeclaration and Expression and Statement)]

XPath is adequate for simple rules. Typically, naming conventions could be easily verified using XPath expressions.

For example, if we are looking for the usages of System.gc() in Java code, the rule may use the XPath expression:

//Name[@Image='System.gc' or @Image='java.lang.System.gc']

NOTE: the XPath attribute axis (@property) fetches an AST node property (getter returning a primitive type). For example, @Image invokes the getImage() method on context AST nodes.

XPath-based rules could be implemented configuring com.als.core.rule.XPathRule, passing proper XPath expression in xpath rule property.

XPath basics

An XPath path expression uses steps and predicates (enclosed between square brackets [ and ]) to select nodes in a tree (AST in what follows). Each step matches a AST node whose type name is the name of the step. / represents the root node, . represents the current node, .. represents the parent of current node, while // represents any successor node(s) of the given type.

XPath function calls could be used, represented as functionName(arg1, ..., argN). All steps are relative to current node in context (typically initial context contains just the root of the AST).

Each step could be qualified by an XPath axis axis::step, representing a navigation from the current node. The default axis (tick) is children, while .. is a shortcut for parent::, // shortcut for descendant::, and @attribute a shortcut for attribute:: axis that returns the value of AST node property with that name (result of getter method with that name, for the node).

Some examples make the XPath syntax clearer:

//Class/Field[@Name='x'] matches the AST nodes of type "Field" under any node of type Class, with "x" as the value of the Name property (getName() getter).
/Class[1]/Method[not(FormalParameter)] matches Method under the first top-level class, without FormalParameter children (i.e. no-parameter methods).
//CallStatement[ matches(@Name, 'PATTERN') ]/following-sibling::*[1] matches the next AST node following any call to a function matching PATTERN.

XPath functions reference

NOTE: In the function signatures, optional arguments are enclosed between [ and ]. A sequence of multiple arguments is represented by '...'.

Basic XPath functions:

Function	Meaning	Example
empty(a1, ..., aN)	True if no args or all args are empty lists or null	//Class[ empty(Field, Method) ]
qak:every(var, binding, test)	True if test XPath expr (executed on each value in binding expr bound to var) is true for all values in the binding expression.	//ConstructorDeclaration[ qak:every('$call', qak:find('calls', .), 'CHECK_ON_METHOD_CALL') ]
except(A, B)	Nodeset difference: Return items in A but not in B (alias: difference())	except(//Field \| //Method, //*[matches(@Name, '^get')] )
exists(a1, ..., aN)	True if args and each arg is non-empty list or non-null	//Class[ exists(Field, Method) ]
qak:for(var, binding, returnExpr)	Return set with values returned by executing returnExpr for each value in the binding expression, with var bound to value on each execution.	qak:for('$x', //Method, 'qak:search("container", $x)' )
qak:getCommentOn()	Return the code comment on the context node (null if no comment)	//Method[ contains(qak:getCommentOn(), 'password') ]
qak:groovy($code, args)	Evaluate groovy closure with given args	//ClassOrInterfaceDeclaration[ qak:groovy('{args, ctx -> args.isPublic() }', .) ]
qak:if($test, $expr1, $expr2)	Return value of $expr1 if boolean($test) is true, $expr2 otherwise. If no $expr2 is provided, empty nodeset is returned.	qak:if( $clazz[@Interface='true'], $clazz/Method, $clazz/Method[@Public='true'])
qak:in($left, $right) \\\ qak:in($right)	Return true if $left is contained in $right (all elements in $left are in $right). $left is the context set if not explicitely given.	qak:search('variableDeclaration', qak:navigate('variableUsages', //VariableDeclaratorId )) [qak:in( //LocalVariableDeclaration )]
intersect($first, $second)	Intersection	intersect(//Field \| //Method, //*[matches(@Name, '^get')] )
matches(arg, regularExpr)	True if any substring for arg matches the regular expression	//Method[ matches(@Name, '^get') ]
max(a1, ..., aN)	Max value in the input argument	//Method[@BeginLine < max(../Field/@BeginLine)]
min(a1, ..., aN)	Min value in the input argument	//Field[@BeginLine > min(../Method/@BeginLine)]
node-after($one, $two)	True if $one appears later in code than $two	//Field[node-after(., ../Method)]
node-before($one, $two)	True if $one appears before in code than $two	//Method[node-before(., ../Field[last()])]
replace($str, $regexp, $subst)	Replace groups matched in str by regexp with subst pattern	replace(@Name, '^(is\|get\|has)(.+)$', '$2')
reverse($nodeset)	Reverse items in nodeset	reverse(//Statement)
root() / root($arg)	Get root node	except(//Method, root()/Class[1]/Method)
qak:some(var, binding, test)	True if test expr (executed on each value in binding expr bound to var) is true for at least one value in binding expression.	//ConstructorDeclaration[ qak:some('$call', qak:find('calls', .), 'SOME_CHECK_ON_METHOD_CALL') ]
subsequence($arr, $init [, $size])	Extract subsequence from arr starting from init (starts at 1) up to size	subsequence(//Class, 2, count(//Class - 2))
qak:strict-path($nodes, $p1, ..., $pN) qak:strict-path($p1, ..., $pN)	Return nodes (in $nodes or in context nodes when not present) that have degenerate subtree composed of the p1 ... pN successor node types.	qak:variable('$includes', //IncludeStatement \| //IncludeExpression) \| $includes[not(qak:strict-path('Expression', 'UnaryExpression', 'PrimaryExpression', 'String'))]
qak:symmetric-difference($one, $two)	Items in one of the sets but not both	qak:symmetric-difference(/Class/Method[@Public='true'], /Class/Method[starts-with(@Name, 'test')])
union(a1, ..., aN)	Same as a1 \| ... \| aN	union(//Method, //Constructor)
qak:variable(var, expr)	Sets var to expr, returning empty set (so it could be used in union expressions). Similar to <xsl:variable>	qak:variable('$f', //Field) \| qak:variable('$m', //Method) \| except($m, qak:hla(qak:navigate('variableUsages', $f))/ancestor::Method)

For better understanding of XPath functions, you may execute the sample XPath expressions in Rule Developer and try to understand for each example what nodes are looked for.

For example:

//ConstructorDeclaration[
  qak:every('$call', qak:find('calls', .), 'matches( $call/PrimaryPrefix/@Label, "super\.")')
]

looks for constructors (in Java) where all calls are to methods in super class.

Extended XPath functions

Extended XPath functions use primitives, like predicates, visitors, navigations or visitors:

Category	Function	Meaning	Example
Search & Navigation	qak:accept($visitor, $arg)	Apply visitor to nodes in $arg.	qak:accept($myVisitor, //MethodDeclaration)
Search & Navigation	qak:filter($pred, $arg)	Return nodeset with nodes in $arg matching NodePredicate $pred.	qak:filter('hasUsages', //VariableDeclaratorId)
Search & Navigation	qak:find($pred, $arg)	Return nodeset with all nodes matching pred under each subtree rooted at each node in $arg	//MethodDeclaration[not( qak:find('calls', .) )]
Search & Navigation	qak:navigate($navigation, $arg)	Return nodeset with nodes reachable after running $navigation starting at each node in $arg	qak:navigate('container', //PrimaryExpression[...]) qak:navigate('variableUsages', //VariableDeclaratorId)
Search & Navigation	qak:query($query, $arg)	Return nodeset with nodes reachable after running $query starting at nodes in $arg	qak:query($myQuery, //VariableDeclaratorId) //VariableDeclaratorId[ qak:query($myQuery) ]
Search & Navigation	qak:search($search, $arg)	Return nodeset with nodes found after executing $search on each node in $arg.	qak:search('methodDeclaration', qak:find('calls')) qak:find('calls')[ qak:search($search) ]
HLA/LLA conversion	qak:hla() / qak:hla($arg)	Return HLA nodes for each context node or each node in $arg	qak:hla( /xpath/expr/to/nodes, /other/xpath/expr/to/nodes ) qak:hla()/path/on/hla
HLA/LLA conversion	qak:lla() / qak:lla($arg)	Return LLA nodes for each context node or each node in $arg	qak:lla( /xpath/expr/to/nodes, /other/xpath/expr/to/nodes )

Language-specific XPath functions

For some technologies, a few additional XPath functions (prefixed with qak-LANGUAGE) are provided.

Function	Meaning	Example
qak-java:typeof($val, $full[, $short])	True if $var (an attribute) match full/short type name, or node matches type	//ClassOrInterfaceDeclaration[ qak-java:typeof(@Image, 'java.io.Serializable') ]

XPath API

Often you may use the XPath API to build an XPath expression that you may execute in a rule: Part of a complex search could be represented succintly by an XPath expression, while other parts of the query could be implemented by other means. For that, XPath class provides an interface to declarative queries in the AST.

The com.als.core.xpath.XPath class (in qaKingCore module) represents an XPath expression that could be executed from a start node (typically a BaseNode). The XPath interface is rather simple:

XPath(String xpath) throws JaxenException;
XPath(String xpath, RuleContext ctx) throws JaxenException;

List selectNodes(Object initial);
Object selectSingleNode(Object initial);
Object evaluate(Object initial);

Sample usage that could be used in custom rules:

BaseNode astNode = ...;
XPath xpath = new XPath("//MyNode/SubNode[@Image='x']", ruleContext);
List nodes = xpath.selectNodes(astNode); // A list of BaseNode (possibly empty)
BaseNode node = xpath.selectNode(astNode); // The first node matching the XPath expr, or null

XPath xpath2 = new XPath("//MyNode/SubNode/@Image");
List images = xpath.evaluate(astNode);

The astNode passed could be high-level or low-level AST, depending on the node that you pass as the initial node.

NOTE: Other parts of the API accept an XPath expression argument. For example, com.optimyth.qaking.highlevelapi.navigation.XPathRegion builds a navigation based on XPath expression. And com.optimyth.qaking.query.Query some methods have an XPath expression as argument:

// Visit nodes reachable from current context by XPath expression
visit(XPath xpath, NodeVisitor visitor);
visit(String xpath, NodeVisitor visitor);


// Navigate to nodes reachable by XPath expression, starting from current query context
navigate(XPath xpath);
navigate(XPath xpath, NodePredicate pred);
navigate(String xpath);
navigate(String xpath, NodePredicate pred);

Extending XPathRule

Usually, an XPath custom rule does not need a custom Java class with explicit logic. You simply specify the Java class com.als.core.rule.XPathRule in the descriptor and provide the XPath expression in the "xpath" rule property.

In some cases, you may need to set XPath variables to the XPath expression or provide a non-default logic for reporting violations at nodes returned by the XPath expression. XPathRule could be extended by overwriting two methods:

/**
 * Invoked in rule initialization. Subclasses may add additional logic for configuring the XPath statement,
 * like setting XPath variables. Default implementation does nothing.
 */
 protected void initializeQuery(XPath xpath, RuleContext ctx) {}


  /**
   * Invoked on each BaseNode matched by the XPath query. Subclasses may change the rule violation reporting logic.
   * Default implementation simply create and report a violation on the node begin line.
   * @param node BaseNode where the violation will be reported.
   * @param ctx RuleContext
   * @return RuleViolation created (added to the report).
   */

  protected RuleViolation reportViolation(BaseNode node, RuleContext ctx) {
    int line = node.getBeginLine();
    if(line<=0) line = TreeNode.on(node).findLine();
    RuleViolation rv = createRuleViolation(ctx, line);
    ctx.getReport().addRuleViolation( rv );
    return rv;
  }

Related to

Basic API

Basic navigation: BaseNode and TreeNode

Checking conditions in the nodes: TreeNode and NodePredicate

Navigation within the navigation: TreeNode and NodeVisitor

High-Level AST and Low-Level AST

Query API

Rule Development Manual

API alternatives

Abstract Syntax Tree (low-level and high-level) API

NavigableNode / TreeNode API

XPath rules

Query API

Additional static analysis facilities

Control-flow graph (CFG) and data-flow analysis

Library metadata

Tainting propagation

Local / Global Symbol Table

Global Symbol Table (GST)

Local Symbol Table (LST)

Tips for programming static analysis Rules

Rule programming best practices

Use `BaseNode` interface whenever possible

Use common tree navigation facilities, instead of implementing your own "utility methods" for traversing AST trees.

Never add "artificial state" to your rule classes.

Emit violations judiciously

Avoid plain-text checks

Try to limit dependencies with the underlying grammar

Rule programming anti-patterns

Add artificial state to your rules (in the form of instance variables)

Read source code files liberally

Put nonsense comments in your code, but refuse to document the rule purpose and how the condition is checked.

XPath API

XPath basics

XPath functions reference

Basic XPath functions:

Extended XPath functions

Language-specific XPath functions

XPath API

Extending XPathRule

Basic API

Basic navigation: BaseNode and TreeNode

Checking conditions in the nodes: TreeNode and NodePredicate

Navigation within the navigation: TreeNode and NodeVisitor

High-Level AST and Low-Level AST

Query API

Rule Development Manual

API alternatives

Abstract Syntax Tree (low-level and high-level) API

NavigableNode / TreeNode API

XPath rules

Query API

Additional static analysis facilities

Control-flow graph (CFG) and data-flow analysis

Library metadata

Tainting propagation

Local / Global Symbol Table

Global Symbol Table (GST)

Local Symbol Table (LST)

Tips for programming static analysis Rules

Rule programming best practices

Use BaseNode interface whenever possible

Use common tree navigation facilities, instead of implementing your own "utility methods" for traversing AST trees.

Never add "artificial state" to your rule classes.

Emit violations judiciously

Avoid plain-text checks

Try to limit dependencies with the underlying grammar

Rule programming anti-patterns

Add artificial state to your rules (in the form of instance variables)

Read source code files liberally

Put nonsense comments in your code, but refuse to document the rule purpose and how the condition is checked.

XPath API

XPath basics

XPath functions reference

Basic XPath functions:

Extended XPath functions

Language-specific XPath functions

XPath API

Extending XPathRule

Use `BaseNode` interface whenever possible