Traversal steps

The most important basic traversal steps will be the ones generated for your domain as highlighted in glimpse-of-a-simple-use-case.

In addition to the generated domain-specific steps based on your schema, there’s some basic traversal steps that you can use generically across domains, e.g. to traverse from a node (or an Iterator[Node]) to their neighbors, lookup their properties etc. There are also more advanced steps like repeat and advanced features like path tracking which will be described further below.

Step Types

The various traversal queries can be divided into a number of types: Filter, Map, Side Effect, and Terminal.

Filter Steps

Filter Steps are atomic traversals that filter nodes according to given criteria. The most common filter step is aptly-named filter, which continues the traversal in the step it suffixes for all nodes which pass its criterion. Its criterion is represented by a lambda function which has access to the node of the previous step and returns a boolean. Continuing with the previous example, let us execute a query which returns all METHOD nodes of the Code Property Graph for X42, but only if their IS_EXTERNAL property is set to false:

joern> cpg.method.filter(_.isExternal == false).name.toList 
res11: List[String] = List("main")

Dissecting this query, we have cpg as the root object, a node-type step method which returns all nodes of type METHOD, a filter step where(_.isExternal == false) which continues the traversal only for nodes which have their IS_EXTERNAL property set to false (with _ referencing the individual nodes, and isExternal a property directive which accesses their IS_EXTERNAL property), followed by a property directive name which returns the values of the NAME property of the nodes that passed the Filter Step, and finally an Execution Directive toList which executes the traversal and returns the results in a list.

A shorter version of a query which returns the same results as the one above can be written using a Property-Filter Step. Property-filter steps are Filter Steps which continue the traversal only for nodes which have a specific value in the property the Property Filter Step refers to:

joern> cpg.method.isExternal(false).name.toList 
res11: List[String] = List("main")

Dissecting the query again, cpg is the root object, method is a node-type step, isExternal(false) is a property-filter step that filters for nodes which have false as the value of their IS_EXTERNAL property, name is a property directive, and toList is the execution directive you are already familiar with.

A final Filter Step we will look at is named where. Unlike filter, this doesn’t take a simple predicate A => Boolean, but instead takes a Traversal[A] => Traversal[_]. I.e. you supply a traversal which will be executed at the current position. The resulting Traversal will preserves elements if the provided traversal has at least one result. The previous query that used a Property Filter Step can be re-written using where like so:

joern> cpg.method.where(_.isExternal(false)).name.toList 
res24: List[String] = List("main")

Maybe not particularly useful-seeming given this specific example, but keep it in the back of your head, because filter is a handy tool to have in the toolbox. Next up, Map Steps.

Map Steps

Map Steps are traversals that map a set of nodes into a different form given a function. Map Steps are a powerful mechanism when you need to transform results to fit your specifics. For example, say you’d like to return both the IS_EXTERNAL and the NAME properties of all METHOD nodes in X42’s Code Property Graph. You can achieve that with the following query:

joern> cpg.method.map(node => (node.isExternal, node.name)).toList
res6: List[(Boolean, String)] = List(
  (false, "main"),
  (true, "fprintf"),
  (true, "exit"),
  (true, "<operator>.logicalAnd"),
  (true, "<operator>.equals"),
  (true, "<operator>.greaterThan"),
  (true, "strcmp"),
  (true, "<operator>.indirectIndexAccess"),
  (true, "printf")
)

Don’t be intimidated by the syntax used in the map Step above. If you examine map(node => (node.isExternal, node.name)) for a bit, you might be able to infer that the first node simply defines the variable that represents the node which preceeds the map Step, that the ASCII arrow => is just syntax that preceeds the body of a lambda function, and that (node.isExternal, node.name) means that the return value of the lambda is a list which contains the value of the isExternal and name Property Directives for each of the nodes matched in the previous step and also passed into the lambda. In most cases in which you need map, you can simply follow the pattern above. But should you ever feel constrained by the common pattern shown, remember that the function for the map step is written in the Scala programming language, a fact which opens up a wide range of possibilities if you invest a little time learning the language.

Side Effect Steps

Side Effect Steps are traversal steps that perform an action or modify the state of the traversal without altering the path of the traversal itself. They do not directly contribute to the results that are returned, but they might be used to store information, log data, or manipulate variables during traversal. These steps can be thought of as adding “side effects” to the traversal that can be useful for various purposes like counting, aggregating, or modifying data.

Terminal Steps

Terminal Steps are steps that end the traversal and return the final result. Once a terminal step is reached, the traversal is considered complete, and it provides the output in some form (e.g., a list, a set, or a single element). Unlike intermediate steps that continue building the traversal, terminal steps execute the traversal and stop further processing. After a terminal step, the traversal cannot be continued or extended; it’s finished.

Traversal Steps

The steps described below are available when called on an Iterator. For these to be available, the following packaged must be imported, i.e., import flatgraph.traversal.language.*.

Basic steps

Assuming you have an Iterator[X], where X is typically a domain specific type, but could also be flatgraph’s root type for nodes GNode, here’s a (non-exhaustive) list of basic traversal steps.

Node Steps

When starting the traversal from an Iterator of nodes GNode.

Edge Steps

When starting the traversal from an Iterator of nodes Edge.

Property Directives

The steps described below are available when called on the entity/object directly. These are available as methods or properties on the objects so no import is necessary.

Graph Steps

Steps available from an instance of Graph.

Edge Steps

Steps available from an instance of Edge.

Node Steps

Steps available from an instance of GNode.