Module MakeWithSplitting

Provides a shared interface for constructing control-flow graphs (CFGs) from abstract syntax trees (ASTs).

The implementation is centered around the concept of a completion, which models how the execution of a statement or expression terminates.

The CFG is built by structural recursion over the AST, using the abstract class ControlFlowTree. To achieve this, the CFG edges related to a given AST node, n, are divided into three categories:

The in-going edge that points to the first CFG node to execute when n is going to be executed.
The out-going edges for control flow leaving n that are going to some other node in the surrounding context of n.
The edges that have both of their end-points entirely within the AST node and its children.

The edges in (1) and (2) are inherently non-local and are therefore initially calculated as half-edges, that is, the single node, k, of the edge contained within n, by the predicates k = n.first() and k = n.last(_), respectively. The edges in (3) can then be enumerated directly by the predicate succ by calling first and last recursively on the children of n and connecting the end-points. This yields the entire CFG, since all edges are in (3) for some AST node.

The parameter of last is the completion, which is necessary to distinguish the out-going edges from n. Note that the completion changes as the calculation of last proceeds outward through the AST; for example, a completion representing a loop break will be caught up by its surrounding loop and turned into a normal completion.

Import path

import codeql.controlflow.Cfg

Imports

Public

Predicates

first	Holds if `first` is the first element executed within control flow element `cft`.
last	Holds if `last` with completion `c` is a potential last element executed within control flow element `cft`.
succ	Holds if `succ` is a control flow successor for `pred`, given that `pred` finishes with completion `c`.

Classes

AnnotatedExitNode	An exit node for a given scope, annotated with the type of exit.
AstCfgNode	A node for an AST node.
ControlFlowTree	An element with associated control flow.
EntryNode	An entry node for a given scope.
ExitNode	An exit node for a given scope.
LeafTree	An element that is a leaf in the control flow graph.
NormalExitNode	A control flow node indicating normal termination of a callable.
PostOrderTree	An element that is executed in post-order, typically used for expressions.
PreOrderTree	An element that is executed in pre-order, typically used for statements.
SplitImpl	An interface for implementing an entity to split on.
SplitKind	A split kind. Each control flow node can have at most one split of a given kind.
Splits	A set of control flow node splits. The set is represented by a list of splits, ordered by ascending rank.
StandardPostOrderTree	A standard element that is executed in post-order.
StandardPreOrderTree	A standard element that is executed in pre-order.
StandardTree	An element where the children are evaluated following a standard left-to-right evaluation. The actual evaluation order is determined by the predicate `getChildNode()`.

Modules

BasicBlocks	Provides a basic block construction on top of the control flow graph.
Consistency	Provides a set of consistency queries.
SplitImplementations	Provides logic for common CFG split implementations that can be reused across languages.
TestOutput	Import this module into a `.ql` file to output a CFG. The graph is restricted to nodes from `RelevantNode`.
ViewCfgQuery	Provides an implementation for a `View CFG` query.

Type signatures

RelevantNodeSig

A node to be included in the output of TestOutput.

Module signatures

ViewCfgQueryInputSig

Provides the input to ViewCfgQuery.

Aliases

Node	A control flow node.

Parameters

Location		LocationSig
Input		InputSig<MakeWithSplitting::Location>
SplittingInput		SplittingInputSig<MakeWithSplitting::Location, MakeWithSplitting::Input>
ConditionalCompletionSplittingInput		ConditionalCompletionSplittingInputSig<MakeWithSplitting::Location, MakeWithSplitting::Input, MakeWithSplitting::SplittingInput>