Skip to content

Core

Jump to bottom
github-actions[bot] edited this page Sep 3, 2026 · 1 revision

Generated from 'wiki-core.ts' on 2026-09-01, 11:38:12 UTC (v2.15.8, R v4.6.1), please do not edit directly.

This wiki page provides an overview of the inner workings of flowR. It is mostly intended for developers that want to extend the capabilities of flowR and assumes knowledge of TypeScript and R. If you think parts of the wiki are missing, wrong, or outdated, please do not hesitate to open a new issue! In case you are new and want to develop for flowR, please check out the relevant Setup wiki page and the Contributing Guidelines.

Note

Essentially every step we explain here can be explored directly from flowR's REPL in an interactive fashion (see the Interface wiki page). We recommend to use commands like :parse or :dataflow* to explore the output of flowR using your own samples. As a quickstart you may use:

$ docker run -it --rm eagleoutice/flowr # or npm run flowr 
flowR repl v2.15.8, R v4.6.1 (r-shell engine)
R> :parse "x <- 1; print(x)"
Output 
exprlist
├ expr
│ ├ expr
│ │ ╰ SYMBOL "x" (1:1)
│ ├ LEFTASSIGN "<-" (1:3─4)
│ ╰ expr
│   ╰ NUMCONST "1" (1:6)
├ ; ";" (1:7)
╰ expr
  ├ expr
  │ ╰ SYMBOLFUNCTIONCALL "print" (1:9─13)
  ├ ( "(" (1:14)
  ├ expr
  │ ╰ SYMBOL "x" (1:15)
  ╰ ) ")" (1:16)

Retrieves the AST from the RShell.

If you are brave (or desperate) enough, you can also try to use the --verbose option to be dumped with information about flowR's internals (please, never use this for benchmarking). See the FAQ (How to get flowR to talk?) for more information.

Whatever any of these steps hands you, the questions you may ask of it live on a helper object named after it; the Helper Objects page lists all of them, grouped by what they are about.

Creating and Using a flowR Analyzer Instance

The FlowrAnalyzerBuilder class should be used as a starting point to create analyses in flowR. It provides a fluent interface for the configuration and creation of a FlowrAnalyzer instance:

const analyzer = await new FlowrAnalyzerBuilder()
    .configure('ignoreSourceCalls', true)
    .setEngine('tree-sitter')
    .build();
analyzer.addRequest('x <- 1; y <- x; print(y);');

Have a look at the Engine wiki page to understand the different engines and parsers you can use.

The analyzer instance can then be used to access analysis results like the normalized AST, the dataflow graph, and the controlflow graph:

const normalizedAst = await analyzer.normalize();
const dataflow = await analyzer.dataflow();
const cfg = await analyzer.controlflow();

The underlying FlowrAnalyzer instance will take care of caching, updates, and running the appropriate steps. It also exposes the query API:

 * Shows how to use the query API to perform a static slice (please do not simplify).
 */
async function sliceQueryExample(analyzer: FlowrAnalyzer) {
	const result = await analyzer.query([{
		type:     'static-slice',
		criteria: ['1@y']
	}]);

One of the additional advantages of using the FlowrAnalyzer is that it provides you with context information about the analysed files:

 * Shows how to inspect the context of an analyzer instance.
 */
export function inspectContextExample(analyzer: FlowrAnalyzer) {
	const ctx = analyzer.inspectContext();
	console.log('dplyr version', ctx.deps.getDependency('dplyr'));
	console.log('loading order', ctx.files.loadingOrder.getLoadingOrder());

Pipelines and their Execution

At the core of every analysis done via a FlowrAnalyzer is the PipelineExecutor class which takes a sequence of analysis steps (in the form of a Pipeline) and executes it on a given input. In general, these pipeline steps are analysis agnostic and may use arbitrary input and ordering. However, two important and predefined pipelines, the DEFAULT_DATAFLOW_PIPELINE and the TREE_SITTER_DATAFLOW_PIPELINE adequately cover the most common analysis steps (differentiated only by the Engine used).

Tip

You can hover over most links within these wiki pages to get access to the tsdoc comment of the respective element. The links should direct you to the up-to-date implementation.

Using the tree-sitter engine you can request a dataflow analysis of a sample piece of R code like the following:

const executor = new PipelineExecutor(TREE_SITTER_DATAFLOW_PIPELINE, {
	parser:  new TreeSitterExecutor(),
	context: contextFromInput('x <- 1; y <- x; print(y);')
});
const result = await executor.allRemainingSteps();

This is, roughly, what the dataflow function does when using the tree-sitter engine. We create a new PipelineExecutor with the TREE_SITTER_DATAFLOW_PIPELINE and then use PipelineExecutor::allRemainingSteps to cause the execution of all contained steps (in general, pipelines can be executed step-by-step, but this is usually not required if you just want the result).

In general, however, most flowR-internal functions which are tasked with generating dataflow prefer the use of createDataflowPipeline as this function automatically selects the correct pipeline based on the engine used.

Understanding Pipeline Steps

Everything that complies to the IPipelineStep interface can be used as a step in a pipeline, with the most important definition being the processor function, which refers to the actual work performed by the step. For example, the STATIC_DATAFLOW step ultimately relies on the produceDataFlowGraph function to create a dataflow graph using the normalized AST of the program.

Shape of a Pipeline Step

Using code, you can provide an arbitrary pipeline step to the executor, as long as it implements the IPipelineStep interface:

  • IPipelineStep
    Defines what is to be known of a single step in a pipeline. It wraps around a single processor function, providing additional information. Steps will be executed synchronously, in-sequence, based on their dependencies .

    Defined at src/core/steps/pipeline-step.ts#L70 
    /**
 * Defines what is to be known of a single step in a pipeline.
 * It wraps around a single {@link IPipelineStep#processor|processor} function, providing additional information.
 * Steps will be executed synchronously, in-sequence, based on their {@link IPipelineStep#dependencies|dependencies}.
 */
export interface IPipelineStep<
    Name extends PipelineStepName = PipelineStepName,
    // eslint-disable-next-line -- by default, we assume nothing about the function shape
    Fn extends StepProcessingFunction = (...args: any[]) => any,
> extends MergeableRecord, IPipelineStepOrder<Name> {
    /** Human-readable name of this step */
    readonly humanReadableName: string
    /** Human-readable description of this step */
    readonly description:       string
    /** The main processor that essentially performs the logic of this step */
    readonly processor:         (...input: Parameters<Fn>) => ReturnType<Fn>
    /** How to visualize the results of the respective step to the user? */
    readonly printer: {
        [K in StepOutputFormat]?: IPipelineStepPrinter<Fn, K, never[]>
    } & {
        // we always want to have an internal printer
        [StepOutputFormat.Internal]: InternalStepPrinter<Fn>
    }
    /**
     * Input configuration required to perform the respective steps.
     * Required inputs of dependencies do not have to, but can be repeated.
     * <p>
     * Use the pattern `undefined as unknown as T` to indicate that the value is required but not provided.
     */
    readonly requiredInput: object
}

Every step may specify required inputs, ways of visualizing the output, and its dependencies using the IPipelineStepOrder interface. As the types may seem to be somewhat confusing or over-complicated, we recommend you to look at some existing steps, like the PARSE_WITH_R_SHELL_STEP or the STATIC_DATAFLOW step. The pipeline executor should do a good job of scheduling these steps (usually using a topological sort), and inferring the required inputs in the type system (have a look at the createPipeline function if you want to know more).

Note

Under the hood there is a step-subtype called a decoration. Such a step can be added to a pipeline to decorate the output of another one (e.g., making it more precise, re-adding debug info, ...). To mark a step as a decoration, you can use the decorates field in the IPipelineStepOrder interface. However, as such steps are currently not relevant for any of flowR's core analyses we will not go into detail here. It suffices to know how "real" steps work.

How flowR Produces Dataflow Graphs

This section focuses on the generation of a dataflow graph from a given R program, using the RShell Engine and hence the DEFAULT_DATAFLOW_PIPELINE. The tree-sitter engine uses the TREE_SITTER_DATAFLOW_PIPELINE), which replaces the parser with the integrated tree-sitter parser and hence uses a slightly adapted normalization step to produce a similar normalized AST. The dataflow graph should be the same for both engines (although tree-sitter is faster and may be able to parse more files).

Overview

Let's have a look at the definition of the pipeline:

  • DEFAULT_DATAFLOW_PIPELINE
    The default pipeline for working with flowR, including the dataflow step. See the DEFAULT_NORMALIZE_PIPELINE for the pipeline without the dataflow step and the DEFAULT_SLICE_AND_RECONSTRUCT_PIPELINE for the pipeline with slicing and reconstructing steps

    Defined at src/core/steps/pipeline/default-pipelines.ts#L30 
    DEFAULT_DATAFLOW_PIPELINE = createPipeline(PARSE_WITH_R_SHELL_STEP, NORMALIZE, STATIC_DATAFLOW)

We can see that it relies on three steps:

  1. PARSE_WITH_R_SHELL_STEP (parsing): Uses the RShell to parse the input program.
    Its main function linked as the processor is the parseRequests function.
  2. NORMALIZE (normalization): Normalizes the AST produced by the parser (to create a normalized AST).
    Its main function linked as the processor is the normalize function.
  3. STATIC_DATAFLOW (dataflow): Produces the actual dataflow graph from the normalized AST.
    Its main function linked as the processor is the produceDataFlowGraph function.

To explore these steps, let's use the REPL with the (very simple and contrived) R code: x <- 1; print(x).

$ docker run -it --rm eagleoutice/flowr # or npm run flowr 
flowR repl v2.15.8, R v4.6.1 (r-shell engine)
R> :parse "x <- 1; print(x)"
Output 
exprlist
├ expr
│ ├ expr
│ │ ╰ SYMBOL "x" (1:1)
│ ├ LEFTASSIGN "<-" (1:3─4)
│ ╰ expr
│   ╰ NUMCONST "1" (1:6)
├ ; ";" (1:7)
╰ expr
  ├ expr
  │ ╰ SYMBOLFUNCTIONCALL "print" (1:9─13)
  ├ ( "(" (1:14)
  ├ expr
  │ ╰ SYMBOL "x" (1:15)
  ╰ ) ")" (1:16)

This shows the ASCII-Art representation of the parse-tree of the R code x <- 1; print(x), as it is provided by the RShell. See the initCommand function for more information on how we request a parse.

R> :normalize* "x <- 1; print(x)"
Output 
https://mermaid.live/view#base64:eyJjb2RlIjoiZmxvd2NoYXJ0IFREXG4gICAgbjcoW1wiUkV4cHJlc3Npb25MaXN0ICg3KVxuIFwiXSlcbiAgICBuMihbXCJSQmluYXJ5T3AgKDIpXG4jNjA7IzQ1O1wiXSlcbiAgICBuNyAtLT58XCJlbC1jLTBcInwgbjJcbiAgICBuMChbXCJSU3ltYm9sICgwKVxueFwiXSlcbiAgICBuMiAtLT58XCJiaW4tbFwifCBuMFxuICAgIG4xKFtcIlJOdW1iZXIgKDEpXG4xXCJdKVxuICAgIG4yIC0tPnxcImJpbi1yXCJ8IG4xXG4gICAgbjYoW1wiUkZ1bmN0aW9uQ2FsbCAoNilcbnByaW50XCJdKVxuICAgIG43IC0tPnxcImVsLWMtMVwifCBuNlxuICAgIG4zKFtcIlJTeW1ib2wgKDMpXG5wcmludFwiXSlcbiAgICBuNiAtLT58XCJjYWxsLW5hbWVcInwgbjNcbiAgICBuNShbXCJSQXJndW1lbnQgKDUpXG54XCJdKVxuICAgIG42IC0tPnxcImNhbGwtYXJnLTFcInwgbjVcbiAgICBuNChbXCJSU3ltYm9sICg0KVxueFwiXSlcbiAgICBuNSAtLT58XCJhcmctdlwifCBuNFxuIiwibWVybWFpZCI6eyJhdXRvU3luYyI6dHJ1ZX19

Following the link output should show the following:

flowchart TD
    n7(["RExpressionList (7)
 "])
    n2(["RBinaryOp (2)
#60;#45;"])
    n7 -->|"el-c-0"| n2
    n0(["RSymbol (0)
x"])
    n2 -->|"bin-l"| n0
    n1(["RNumber (1)
1"])
    n2 -->|"bin-r"| n1
    n6(["RFunctionCall (6)
print"])
    n7 -->|"el-c-1"| n6
    n3(["RSymbol (3)
print"])
    n6 -->|"call-name"| n3
    n5(["RArgument (5)
x"])
    n6 -->|"call-arg-1"| n5
    n4(["RSymbol (4)
x"])
    n5 -->|"arg-v"| n4
Loading

(The analysis required 5.0 ms (including parsing with the r-shell engine) within the generation environment.)

R> :dataflow* "x <- 1; print(x)"
Output 
https://mermaid.live/view#base64:eyJjb2RlIjoiZmxvd2NoYXJ0IFREXG4gICAgMXt7XCJgKiM5MTtSTnVtYmVyIzkzOyogKioxKipcbiAgICAgICoxLjYqICgqKmlkOiAxKiopYFwifX1cbiAgICAwW1wiYCojOTE7UlN5bWJvbCM5MzsqICoqeCoqXG4gICAgICAqMS4xKiAoKippZDogMCoqLCB2OiAxKWBcIl1cbiAgICAyW1tcImAqIzkxO1JCaW5hcnlPcCM5MzsqIGJhc2UjNTg7IzU4OyoqIzYwOyM0NTsqKlxuICAgICAgKjEuMS02KiAoKippZDogMioqKVxuICAgIGFyZzogKDAsIDEpYFwiXV1cbiAgICBidWlsdC1pbjpfLVtcImBCdWlsdC1JbjpcbiM2MDsjNDU7YFwiXVxuICAgIHN0eWxlIGJ1aWx0LWluOl8tIHN0cm9rZTpncmF5LGZpbGw6Z3JheSxzdHJva2Utd2lkdGg6MnB4LG9wYWNpdHk6Ljg7XG4gICAgNChbXCJgKiM5MTtSU3ltYm9sIzkzOyogKip4KipcbiAgICAgICoxLjE1KiAoKippZDogNCoqKWBcIl0pXG4gICAgNltbXCJgKiM5MTtSRnVuY3Rpb25DYWxsIzkzOyogYmFzZSM1ODsjNTg7KipwcmludCoqXG4gICAgICAqMS45LTE2KiAoKippZDogNioqKVxuICAgIGFyZzogKDQpYFwiXV1cbiAgICBidWlsdC1pbjpwcmludFtcImBCdWlsdC1JbjpcbnByaW50YFwiXVxuICAgIHN0eWxlIGJ1aWx0LWluOnByaW50IHN0cm9rZTpncmF5LGZpbGw6Z3JheSxzdHJva2Utd2lkdGg6MnB4LG9wYWNpdHk6Ljg7XG4gICAgMSAtLi0+fFwiZmxvd1wifCAwXG4gICAgbGlua1N0eWxlIDAgc3Ryb2tlOmdyYXksY29sb3I6Z3JheTtcbiAgICAwIC0tPnxcImRlZmluZWQtYnksIGZsb3dcInwgMlxuICAgIDAgLS0+fFwiZGVmaW5lZC1ieVwifCAxXG4gICAgMiAtLT58XCJyZWFkcywgYXJnXCJ8IDFcbiAgICAyIC0tPnxcInJldHVybnMsIGFyZ1wifCAwXG4gICAgMiAtLi0+fFwicmVhZHMsIGNhbGxzXCJ8IGJ1aWx0LWluOl8tXG4gICAgbGlua1N0eWxlIDUgc3Ryb2tlOmdyYXk7XG4gICAgMiAtLi0+fFwiZmxvd1wifCA0XG4gICAgbGlua1N0eWxlIDYgc3Ryb2tlOmdyYXksY29sb3I6Z3JheTtcbiAgICA0IC0tPnxcInJlYWRzXCJ8IDBcbiAgICA0IC0uLT58XCJmbG93XCJ8IDZcbiAgICBsaW5rU3R5bGUgOCBzdHJva2U6Z3JheSxjb2xvcjpncmF5O1xuICAgIDYgLS0+fFwicmVhZHMsIHJldHVybnMsIGFyZ1wifCA0XG4gICAgNiAtLi0+fFwicmVhZHMsIGNhbGxzXCJ8IGJ1aWx0LWluOnByaW50XG4gICAgbGlua1N0eWxlIDEwIHN0cm9rZTpncmF5OyIsIm1lcm1haWQiOnsiYXV0b1N5bmMiOnRydWV9fQ==

Following the link output should show the following:

flowchart LR
    1{{"`*#91;RNumber#93;* **1**
      *1.6* (**id: 1**)`"}}
    0["`*#91;RSymbol#93;* **x**
      *1.1* (**id: 0**, v: 1)`"]
    2[["`*#91;RBinaryOp#93;* base#58;#58;**#60;#45;**
      *1.1-6* (**id: 2**)
    arg: (0, 1)`"]]
    built-in:_-["`Built-In:
#60;#45;`"]
    style built-in:_- stroke:gray,fill:gray,stroke-width:2px,opacity:.8;
    4(["`*#91;RSymbol#93;* **x**
      *1.15* (**id: 4**)`"])
    6[["`*#91;RFunctionCall#93;* base#58;#58;**print**
      *1.9-16* (**id: 6**)
    arg: (4)`"]]
    built-in:print["`Built-In:
print`"]
    style built-in:print stroke:gray,fill:gray,stroke-width:2px,opacity:.8;
    1 -.->|"flow"| 0
    linkStyle 0 stroke:gray,color:gray;
    0 -->|"defined-by, flow"| 2
    0 -->|"defined-by"| 1
    2 -->|"reads, arg"| 1
    2 -->|"returns, arg"| 0
    2 -.->|"reads, calls"| built-in:_-
    linkStyle 5 stroke:gray;
    2 -.->|"flow"| 4
    linkStyle 6 stroke:gray,color:gray;
    4 -->|"reads"| 0
    4 -.->|"flow"| 6
    linkStyle 8 stroke:gray,color:gray;
    6 -->|"reads, returns, arg"| 4
    6 -.->|"reads, calls"| built-in:print
    linkStyle 10 stroke:gray;
Loading

(The analysis required 2.9 ms (including parse and normalize, using the r-shell engine) within the generation environment. No signature database is mounted for these generated graphs, so library() calls attach no package exports; base-R names are still qualified via the generated base-package store (e.g. acf as stats::acf).)

Tip

All of these commands accept file paths as well, so you can write longer R code within a file, and then pass the file path prefixed with file:// (e.g., file://test/testfiles/example.R) to the commands.

Especially when you are just starting with flowR, we recommend using the REPL to explore the output of the different steps.

Note

Maybe you are left with the question: What is tree-sitter doing differently? Expand the following to get more information!

And what changes with tree-sitter?

Essentially not much (from a user perspective, it does essentially everything and all differently under the hood)! Have a look at the Engines wiki page for more information on the differences between the engines. Below you can see the Repl commands for the tree-sitter engine (using --default-engine to set the engine to tree-sitter):

$ docker run -it --rm eagleoutice/flowr --default-engine tree-sitter # or npm run flowr -- --default-engine tree-sitter
flowR repl v2.15.8, R grammar v14 (tree-sitter engine)
R> :parse "x <- 1; print(x)"
Output 
program
├ binary_operator
│ ├ identifier "x" (1:1─2)
│ ├ <- "<-" (1:3─5)
│ ╰ float "1" (1:6─7)
╰ call
  ├ identifier "print" (1:9─14)
  ╰ arguments
    ├ ( "(" (1:14─15)
    ├ argument
    │ ╰ identifier "x" (1:15─16)
    ╰ ) ")" (1:16─17)

This shows the ASCII-Art representation of the parse-tree of the R code x <- 1; print(x), as it is provided by the TreeSitterExecutor. See the Engines wiki page for more information on the differences between the engines.

R> :normalize* "x <- 1; print(x)"
Output 
https://mermaid.live/view#base64:eyJjb2RlIjoiZmxvd2NoYXJ0IFREXG4gICAgbjcoW1wiUkV4cHJlc3Npb25MaXN0ICg3KVxuIFwiXSlcbiAgICBuMihbXCJSQmluYXJ5T3AgKDIpXG4jNjA7IzQ1O1wiXSlcbiAgICBuNyAtLT58XCJlbC1jLTBcInwgbjJcbiAgICBuMChbXCJSU3ltYm9sICgwKVxueFwiXSlcbiAgICBuMiAtLT58XCJiaW4tbFwifCBuMFxuICAgIG4xKFtcIlJOdW1iZXIgKDEpXG4xXCJdKVxuICAgIG4yIC0tPnxcImJpbi1yXCJ8IG4xXG4gICAgbjYoW1wiUkZ1bmN0aW9uQ2FsbCAoNilcbnByaW50XCJdKVxuICAgIG43IC0tPnxcImVsLWMtMVwifCBuNlxuICAgIG4zKFtcIlJTeW1ib2wgKDMpXG5wcmludFwiXSlcbiAgICBuNiAtLT58XCJjYWxsLW5hbWVcInwgbjNcbiAgICBuNShbXCJSQXJndW1lbnQgKDUpXG54XCJdKVxuICAgIG42IC0tPnxcImNhbGwtYXJnLTFcInwgbjVcbiAgICBuNChbXCJSU3ltYm9sICg0KVxueFwiXSlcbiAgICBuNSAtLT58XCJhcmctdlwifCBuNFxuIiwibWVybWFpZCI6eyJhdXRvU3luYyI6dHJ1ZX19

Following the link output should show the following:

flowchart TD
    n7(["RExpressionList (7)
 "])
    n2(["RBinaryOp (2)
#60;#45;"])
    n7 -->|"el-c-0"| n2
    n0(["RSymbol (0)
x"])
    n2 -->|"bin-l"| n0
    n1(["RNumber (1)
1"])
    n2 -->|"bin-r"| n1
    n6(["RFunctionCall (6)
print"])
    n7 -->|"el-c-1"| n6
    n3(["RSymbol (3)
print"])
    n6 -->|"call-name"| n3
    n5(["RArgument (5)
x"])
    n6 -->|"call-arg-1"| n5
    n4(["RSymbol (4)
x"])
    n5 -->|"arg-v"| n4
Loading

(The analysis required 0.8 ms (including parsing with the tree-sitter engine) within the generation environment.)

R> :dataflow* "x <- 1; print(x)"
Output 
https://mermaid.live/view#base64:eyJjb2RlIjoiZmxvd2NoYXJ0IFREXG4gICAgMXt7XCJgKiM5MTtSTnVtYmVyIzkzOyogKioxKipcbiAgICAgICoxLjYqICgqKmlkOiAxKiopYFwifX1cbiAgICAwW1wiYCojOTE7UlN5bWJvbCM5MzsqICoqeCoqXG4gICAgICAqMS4xKiAoKippZDogMCoqLCB2OiAxKWBcIl1cbiAgICAyW1tcImAqIzkxO1JCaW5hcnlPcCM5MzsqIGJhc2UjNTg7IzU4OyoqIzYwOyM0NTsqKlxuICAgICAgKjEuMS02KiAoKippZDogMioqKVxuICAgIGFyZzogKDAsIDEpYFwiXV1cbiAgICBidWlsdC1pbjpfLVtcImBCdWlsdC1JbjpcbiM2MDsjNDU7YFwiXVxuICAgIHN0eWxlIGJ1aWx0LWluOl8tIHN0cm9rZTpncmF5LGZpbGw6Z3JheSxzdHJva2Utd2lkdGg6MnB4LG9wYWNpdHk6Ljg7XG4gICAgNChbXCJgKiM5MTtSU3ltYm9sIzkzOyogKip4KipcbiAgICAgICoxLjE1KiAoKippZDogNCoqKWBcIl0pXG4gICAgNltbXCJgKiM5MTtSRnVuY3Rpb25DYWxsIzkzOyogYmFzZSM1ODsjNTg7KipwcmludCoqXG4gICAgICAqMS45LTE2KiAoKippZDogNioqKVxuICAgIGFyZzogKDQpYFwiXV1cbiAgICBidWlsdC1pbjpwcmludFtcImBCdWlsdC1JbjpcbnByaW50YFwiXVxuICAgIHN0eWxlIGJ1aWx0LWluOnByaW50IHN0cm9rZTpncmF5LGZpbGw6Z3JheSxzdHJva2Utd2lkdGg6MnB4LG9wYWNpdHk6Ljg7XG4gICAgMSAtLi0+fFwiZmxvd1wifCAwXG4gICAgbGlua1N0eWxlIDAgc3Ryb2tlOmdyYXksY29sb3I6Z3JheTtcbiAgICAwIC0tPnxcImRlZmluZWQtYnksIGZsb3dcInwgMlxuICAgIDAgLS0+fFwiZGVmaW5lZC1ieVwifCAxXG4gICAgMiAtLT58XCJyZWFkcywgYXJnXCJ8IDFcbiAgICAyIC0tPnxcInJldHVybnMsIGFyZ1wifCAwXG4gICAgMiAtLi0+fFwicmVhZHMsIGNhbGxzXCJ8IGJ1aWx0LWluOl8tXG4gICAgbGlua1N0eWxlIDUgc3Ryb2tlOmdyYXk7XG4gICAgMiAtLi0+fFwiZmxvd1wifCA0XG4gICAgbGlua1N0eWxlIDYgc3Ryb2tlOmdyYXksY29sb3I6Z3JheTtcbiAgICA0IC0tPnxcInJlYWRzXCJ8IDBcbiAgICA0IC0uLT58XCJmbG93XCJ8IDZcbiAgICBsaW5rU3R5bGUgOCBzdHJva2U6Z3JheSxjb2xvcjpncmF5O1xuICAgIDYgLS0+fFwicmVhZHMsIHJldHVybnMsIGFyZ1wifCA0XG4gICAgNiAtLi0+fFwicmVhZHMsIGNhbGxzXCJ8IGJ1aWx0LWluOnByaW50XG4gICAgbGlua1N0eWxlIDEwIHN0cm9rZTpncmF5OyIsIm1lcm1haWQiOnsiYXV0b1N5bmMiOnRydWV9fQ==

Following the link output should show the following:

flowchart LR
    1{{"`*#91;RNumber#93;* **1**
      *1.6* (**id: 1**)`"}}
    0["`*#91;RSymbol#93;* **x**
      *1.1* (**id: 0**, v: 1)`"]
    2[["`*#91;RBinaryOp#93;* base#58;#58;**#60;#45;**
      *1.1-6* (**id: 2**)
    arg: (0, 1)`"]]
    built-in:_-["`Built-In:
#60;#45;`"]
    style built-in:_- stroke:gray,fill:gray,stroke-width:2px,opacity:.8;
    4(["`*#91;RSymbol#93;* **x**
      *1.15* (**id: 4**)`"])
    6[["`*#91;RFunctionCall#93;* base#58;#58;**print**
      *1.9-16* (**id: 6**)
    arg: (4)`"]]
    built-in:print["`Built-In:
print`"]
    style built-in:print stroke:gray,fill:gray,stroke-width:2px,opacity:.8;
    1 -.->|"flow"| 0
    linkStyle 0 stroke:gray,color:gray;
    0 -->|"defined-by, flow"| 2
    0 -->|"defined-by"| 1
    2 -->|"reads, arg"| 1
    2 -->|"returns, arg"| 0
    2 -.->|"reads, calls"| built-in:_-
    linkStyle 5 stroke:gray;
    2 -.->|"flow"| 4
    linkStyle 6 stroke:gray,color:gray;
    4 -->|"reads"| 0
    4 -.->|"flow"| 6
    linkStyle 8 stroke:gray,color:gray;
    6 -->|"reads, returns, arg"| 4
    6 -.->|"reads, calls"| built-in:print
    linkStyle 10 stroke:gray;
Loading

(The analysis required 0.7 ms (including parse and normalize, using the tree-sitter engine) within the generation environment. No signature database is mounted for these generated graphs, so library() calls attach no package exports; base-R names are still qualified via the generated base-package store (e.g. acf as stats::acf).)

Parsing

The parsing step uses the RShell to parse the input program (or, of course, the TreeSitterExecutor when using the tree-sitter engine). To speed up the process, we use the initCommand function to compile the parsing function and rely on a custom serialization, which outputs the information in a CSV-like format. This means, that the :parse command actually kind-of lies to you, as it does pretty print the serialized version which looks more like the following (this uses the retrieveParseDataFromRCode function with the sample code x <- 1; print(x)):

Raw parse output for x <- 1; print(x)

For the code x <- 1; print(x):

[1,1,1,6,7,0,"expr",false,"x <- 1"],[1,1,1,1,1,3,"SYMBOL",true,"x"],[1,1,1,1,3,7,"expr",false,"x"],[1,3,1,4,2,7,"LEFT_ASSIGN",true,"<-"],[1,6,1,6,4,5,"NUM_CONST",true,"1"],[1,6,1,6,5,7,"expr",false,"1"],[1,7,1,7,6,0,"';'",true,";"],[1,9,1,16,19,0,"expr",false,"print(x)"],[1,9,1,13,10,12,"SYMBOL_FUNCTION_CALL",true,"print"],[1,9,1,13,12,19,"expr",false,"print"],[1,14,1,14,11,19,"'('",true,"("],[1,15,1,15,13,15,"SYMBOL",true,"x"],[1,15,1,15,15,19,"expr",false,"x"],[1,16,1,16,14,19,"')'",true,")"]

Beautiful, right? I thought so too! In fact, the output is a little bit nicer, when we put it into a table-format and add the appropriate headers:

Parse output in table format

For the code x <- 1; print(x):

line-start col-start line-end col-end id parent token type terminal text
1 1 1 6 7 0 expr false x <- 1
1 1 1 1 1 3 SYMBOL true x
1 1 1 1 3 7 expr false x
1 3 1 4 2 7 LEFT_ASSIGN true <-
1 6 1 6 4 5 NUM_CONST true 1
1 6 1 6 5 7 expr false 1
1 7 1 7 6 0 ';' true ;
1 9 1 16 19 0 expr false print(x)
1 9 1 13 10 12 SYMBOL_FUNCTION_CALL true print
1 9 1 13 12 19 expr false print
1 14 1 14 11 19 '(' true (
1 15 1 15 13 15 SYMBOL true x
1 15 1 15 15 19 expr false x
1 16 1 16 14 19 ')' true )

In fact, this data is merely what R's base::parse and utils::getParseData functions provide. We then use this data in the normalization step to create a normalized AST.

If you are interested in the raw token types that we may encounter, have a look at the RawRType enum.

Normalization

The normalization function normalize takes the output from the previous steps and uses the prepareParsedData and convertPreparedParsedData functions to first transform the serialized parsing output to an object. Next, normalizeRootObjToAst transforms this object to a normalized AST and decorateAst adds additional information to the AST (like roles, ids, depth, etc.). While looking at the mermaid visualization of such an AST is nice and usually sufficient, looking at the objects themselves shows you the full range of information the AST provides (all encompassed within the RNode type).

Let's have a look at the normalized AST for the sample code x <- 1; print(x) (please refer to the normalized AST wiki page for more information):

Normalized AST for x <- 1; print(x) 
{
    "type": "RProject",
    "files": [
        {
            "root": {
                "type": "RExpressionList",
                "children": [
                    {
                        "type": "RBinaryOp",
                        "location": [
                            1,
                            3,
                            1,
                            4
                        ],
                        "lhs": {
                            "type": "RSymbol",
                            "location": [
                                1,
                                1,
                                1,
                                1
                            ],
                            "content": "x",
                            "lexeme": "x",
                            "info": {
                                "fullRange": [
                                    1,
                                    1,
                                    1,
                                    1
                                ],
                                "adToks": [],
                                "id": 0,
                                "parent": 2,
                                "role": "bin-l",
                                "index": 0,
                                "nest": 0
                            }
                        },
                        "rhs": {
                            "location": [
                                1,
                                6,
                                1,
                                6
                            ],
                            "lexeme": "1",
                            "info": {
                                "fullRange": [
                                    1,
                                    6,
                                    1,
                                    6
                                ],
                                "adToks": [],
                                "id": 1,
                                "parent": 2,
                                "role": "bin-r",
                                "index": 1,
                                "nest": 0
                            },
                            "type": "RNumber",
                            "content": {
                                "num": 1,
                                "complexNumber": false,
                                "markedAsInt": false
                            }
                        },
                        "operator": "<-",
                        "lexeme": "<-",
                        "info": {
                            "fullRange": [
                                1,
                                1,
                                1,
                                6
                            ],
                            "adToks": [],
                            "id": 2,
                            "parent": 7,
                            "nest": 0,
                            "index": 0,
                            "role": "el-c"
                        }
                    },
                    {
                        "type": "RFunctionCall",
                        "named": true,
                        "location": [
                            1,
                            9,
                            1,
                            13
                        ],
                        "lexeme": "print",
                        "functionName": {
                            "type": "RSymbol",
                            "location": [
                                1,
                                9,
                                1,
                                13
                            ],
                            "content": "print",
                            "lexeme": "print",
                            "info": {
                                "fullRange": [
                                    1,
                                    9,
                                    1,
                                    16
                                ],
                                "adToks": [],
                                "id": 3,
                                "parent": 6,
                                "role": "call-name",
                                "index": 0,
                                "nest": 0
                            }
                        },
                        "arguments": [
                            {
                                "type": "RArgument",
                                "location": [
                                    1,
                                    15,
                                    1,
                                    15
                                ],
                                "lexeme": "x",
                                "value": {
                                    "type": "RSymbol",
                                    "location": [
                                        1,
                                        15,
                                        1,
                                        15
                                    ],
                                    "content": "x",
                                    "lexeme": "x",
                                    "info": {
                                        "fullRange": [
                                            1,
                                            15,
                                            1,
                                            15
                                        ],
                                        "adToks": [],
                                        "id": 4,
                                        "parent": 5,
                                        "role": "arg-v",
                                        "index": 0,
                                        "nest": 0
                                    }
                                },
                                "info": {
                                    "fullRange": [
                                        1,
                                        15,
                                        1,
                                        15
                                    ],
                                    "adToks": [],
                                    "id": 5,
                                    "parent": 6,
                                    "nest": 0,
                                    "index": 1,
                                    "role": "call-arg"
                                }
                            }
                        ],
                        "info": {
                            "fullRange": [
                                1,
                                9,
                                1,
                                16
                            ],
                            "adToks": [],
                            "id": 6,
                            "parent": 7,
                            "nest": 0,
                            "index": 1,
                            "role": "el-c"
                        }
                    }
                ],
                "info": {
                    "adToks": [],
                    "id": 7,
                    "nest": 0,
                    "role": "root",
                    "index": 0
                }
            }
        }
    ],
    "info": {
        "id": 8
    }
}

This is… a lot! We get the type from the RType enum, the lexeme, location information, an id, the children of the node, and their parents. While the normalized AST wiki page provides you with information on how to interpret this data, we will focus on how we get it from the table provided by the parsing step.

There are two important functions: normalizeRootObjToAst, which operates on the parse-output already transformed into a tree-like structure, and decorateAst, which adds additional information to the AST. Both follow a fold pattern. The fold is explicit for decorateAst, which directly relies on the foldAstStateful function, while normalizeRootObjToAst uses the fold-idiom but deviates in cases in which (for example) we require more information on other nodes to know what it should be normalized too.

Normalizing the Object

We have a handler for everything. For example tryNormalizeIfThen or tryNormalizeFor to handle if(x) y or for(i in 1:10) x constructs. All of these handlers contain many sanity checks to be sure that we talk to an RShell which we can handle (as assumptions may break with newer versions). These functions contain the keyword try as they may fail. For example, whenever they notice late into normalization that they should actually be a different construct (R is great). For single nodes, we use normalizeSingleNode which contains a catch-all for some edge-cases in the R grammar.

The output of just this pass is listed below (using the normalizeButNotDecorated function):

Ast for x <- 1; print(x) after the first normalization 
{
    "type": "RProject",
    "files": [
        {
            "root": {
                "type": "RExpressionList",
                "children": [
                    {
                        "type": "RBinaryOp",
                        "location": [
                            1,
                            3,
                            1,
                            4
                        ],
                        "lhs": {
                            "type": "RSymbol",
                            "location": [
                                1,
                                1,
                                1,
                                1
                            ],
                            "content": "x",
                            "lexeme": "x",
                            "info": {
                                "fullRange": [
                                    1,
                                    1,
                                    1,
                                    1
                                ],
                                "adToks": []
                            }
                        },
                        "rhs": {
                            "location": [
                                1,
                                6,
                                1,
                                6
                            ],
                            "lexeme": "1",
                            "info": {
                                "fullRange": [
                                    1,
                                    6,
                                    1,
                                    6
                                ],
                                "adToks": []
                            },
                            "type": "RNumber",
                            "content": {
                                "num": 1,
                                "complexNumber": false,
                                "markedAsInt": false
                            }
                        },
                        "operator": "<-",
                        "lexeme": "<-",
                        "info": {
                            "fullRange": [
                                1,
                                1,
                                1,
                                6
                            ],
                            "adToks": []
                        }
                    },
                    {
                        "type": "RFunctionCall",
                        "named": true,
                        "location": [
                            1,
                            9,
                            1,
                            13
                        ],
                        "lexeme": "print",
                        "functionName": {
                            "type": "RSymbol",
                            "location": [
                                1,
                                9,
                                1,
                                13
                            ],
                            "content": "print",
                            "lexeme": "print",
                            "info": {
                                "fullRange": [
                                    1,
                                    9,
                                    1,
                                    16
                                ],
                                "adToks": []
                            }
                        },
                        "arguments": [
                            {
                                "type": "RArgument",
                                "location": [
                                    1,
                                    15,
                                    1,
                                    15
                                ],
                                "lexeme": "x",
                                "value": {
                                    "type": "RSymbol",
                                    "location": [
                                        1,
                                        15,
                                        1,
                                        15
                                    ],
                                    "content": "x",
                                    "lexeme": "x",
                                    "info": {
                                        "fullRange": [
                                            1,
                                            15,
                                            1,
                                            15
                                        ],
                                        "adToks": []
                                    }
                                },
                                "info": {
                                    "fullRange": [
                                        1,
                                        15,
                                        1,
                                        15
                                    ],
                                    "adToks": []
                                }
                            }
                        ],
                        "info": {
                            "fullRange": [
                                1,
                                9,
                                1,
                                16
                            ],
                            "adToks": []
                        }
                    }
                ],
                "info": {
                    "adToks": []
                }
            }
        }
    ]
}

Decorating the AST

The decoration is comparatively trivial. We take the AST throw it into the decorateAst function (which again, handles each normalized node type) and get:

  1. The AST with ids, roles, and depth information (see the normalized AST wiki page for more information).
  2. A mapping of ids to nodes in the form of a AstIdMap object. This allows us to quickly access nodes by their id.

The ids used for the AST generation are arbitrary (usually created by the deterministicCountingIdGenerator) function) but unique and intentionally separated from the ids used by the R parser. For one, this detaches us from the Engine used, and secondly, it allows for much easier extension of the AST (e.g., when R files use base::source to include other R files). All ids conform to the NodeId type.

Dataflow Graph Generation

The core of the dataflow graph generation works as a "stateful fold", which uses the tree-like structure of the AST to combine the dataflow information of the children, while tracking the currently active variables and control flow information as a “backpack” (state). We use the produceDataFlowGraph function as an entry point to the dataflow generation (the actual fold entry is in processDataflowFor). The function is mainly backed by its processors object which maps each type in the normalized AST to an appropriate handler ("fold-function").

To understand these handlers, let's start with the simplest one, processUninterestingLeaf signals that we do not care about this node and just produce an empty dataflow information (using DataflowInformation::initialize). Looking at the function showcases the general structure of a processor:

  • processUninterestingLeaf
    Processes a leaf node that does not contribute to dataflow by initializing a clean dataflow information object for it. This can be used to ignore nodes that do not affect dataflow analysis.

    Defined at src/dataflow/internal/process/process-uninteresting-leaf.ts#L11 
    /**
 * Processes a leaf node that does not contribute to dataflow by initializing
 * a clean dataflow information object for it.
 * This can be used to ignore nodes that do not affect dataflow analysis.
 */
export function processUninterestingLeaf<OtherInfo>(leaf: RNodeWithParent, info: DataflowProcessorInformation<OtherInfo>): DataflowInformation {
    return DataflowInformation.initialize(leaf.info.id, info);
}

Every processor has the same shape. It takes the normalized node (see the normalized AST for more information), and a DataflowProcessorInformation object which, as some kind of "backpack" carries global information to every handler. This information is to be used to create a DataflowInformation:

  • DataflowInformation
    The dataflow information is one of the fundamental structures we have in the dataflow analysis. It is continuously updated during the dataflow analysis and holds its current state for the respective subtree processed. Each processor during the dataflow analysis may use the information from its children to produce a new state of the dataflow information. You may initialize a new dataflow information with DataflowInformation.initialize .

    Defined at src/dataflow/info.ts#L224 
    /**
 * The dataflow information is one of the fundamental structures we have in the dataflow analysis.
 * It is continuously updated during the dataflow analysis
 * and holds its current state for the respective subtree processed.
 * Each processor during the dataflow analysis may use the information from its children
 * to produce a new state of the dataflow information.
 *
 * You may initialize a new dataflow information with {@link DataflowInformation.initialize}.
 * @see {@link DataflowCfgInformation} - the control flow aspects
 */
export interface DataflowInformation extends DataflowCfgInformation {
    /**
     * References that have not been identified as read or write and will be so on higher processors.
     *
     * For example, when we analyze the `x` vertex in `x <- 3`, we will first create an unknown reference for `x`
     * as we have not yet seen the assignment!
     * @see {@link IdentifierReference} - a reference on a variable, parameter, function call, ...
     */
    unknownReferences: readonly IdentifierReference[]
    /**
     * References which are read within the current subtree.
     * @see {@link IdentifierReference} - a reference on a variable, parameter, function call, ...
     */
    in:                readonly IdentifierReference[]
    /**
     * References which are written to within the current subtree
     * @see {@link IdentifierReference} - a reference on a variable, parameter, function call, ...
     */
    out:               readonly IdentifierReference[]
    /** Current environments used for name resolution, probably updated on the next expression-list processing */
    environment:       REnvironmentInformation
    /** The current constructed dataflow graph */
    graph:             DataflowGraph
    /**
     * References removed from scope within the current subtree (e.g., via `rm`); `undefined` unless an `rm` occurred.
     * @see {@link KillReference}
     */
    kill?:             readonly KillReference[]
    /**
     * Set by {@link produceDataFlowGraph} when a {@link DataflowBudget} ended the extraction early. The
     * {@link graph} is then partial: everything processed before the bound was hit, and nothing after it.
     */
    cutShort?:         DataflowBudgetExhaustion
}
    View more (DataflowCfgInformation)

    • DataflowCfgInformation
      The control flow information for the current DataflowInformation.

      Defined at src/dataflow/info.ts#L187 
      /** The control flow information for the current DataflowInformation. */
export interface DataflowCfgInformation {
    /** The entry node into the subgraph */
    entryPoint: NodeId,
    /**
     * The node control flow enters this subtree at.
     * Control flow is modeled in post-order (operands are evaluated before the operator that consumes them),
     * so for compound constructs this is not the {@link DataflowCfgInformation#entryPoint|entryPoint}
     * (which names the value-producing node) but the first node that is actually evaluated.
     * Left `undefined` whenever both coincide, which is the case for all leaves.
     */
    cfgEntry?:  NodeId,
    /**
     * The node control flow leaves this subtree at, joining the branches of the construct if it has any.
     * Left `undefined` whenever the {@link DataflowCfgInformation#exitPoints|exitPoints} already name it,
     * which is the case whenever the construct has a single point of exit.
     */
    cfgExit?:   NodeId,
    /**
     * All already identified exit points (active 'return'/'break'/'next'-likes) of the respective structure.
     * This also tracks (local knowledge of) exceptions thrown within the structure.
     * See the {@link ExitPointType#Error|Error} type for more information.
     */
    exitPoints: readonly ExitPoint[]
    /** Registered hooks within the current subtree */
    hooks:      HookInformation[];
}

Essentially, these processors should use the dataflow information from their children combined with their own semantics to produce a new dataflow information to pass upwards in the fold. The DataflowInformation contains:

  • the DataflowGraph of the current subtree
  • the currently active REnvironmentInformation as an abstraction of all active definitions linking to potential definition locations (see Advanced R::Environments)
  • control flow information in DataflowCfgInformation which is used to enrich the dataflow information with control flow information
  • sets of currently ingoing (read), outgoing (write), and unknown IdentifierReferences.
  • and a set of KillReferences which tracks variables that go out of scope within the current subtree (e.g., due to rm). Just like the reference sets above, kills are carried upwards in the fold so that the enclosing scope (expression list, branch, loop, or function body) can apply the removal (via applyKills) at the correct location, even when the rm happens nested within a branch or block. This also covers clearing the whole environment with rm(list=ls()) and conservatively handling removals whose target cannot be resolved statically.

While all of them are essentially empty when processing an “uninteresting leaf”, handling a constant is slightly more interesting with processValue:

  • processValue
    Processes a value node in the AST for dataflow analysis. For example, literals like numbers.

    Defined at src/dataflow/internal/process/process-value.ts#L14 
    /**
 * Processes a value node in the AST for dataflow analysis.
 * For example, literals like numbers.
 */
export function processValue<OtherInfo>({ info: { id } }: RNodeWithParent, { cds, completeAst: { idMap }, environment }: DataflowProcessorInformation<OtherInfo>): DataflowInformation {
    return {
        unknownReferences: [],
        in:                [{ nodeId: id, name: undefined, cds, type: ReferenceType.Constant }],
        out:               [],
        environment,
        graph:             new DataflowGraph(idMap).addVertex({
            tag: VertexType.Value,
            id,
            cds
        }, undefined as unknown as REnvironmentInformation),
        exitPoints: [{ nodeId: id, type: ExitPointType.Default, cds }],
        entryPoint: id,
        hooks:      []
    };
}

Please note, that we add the value vertex to the newly created dataflow graph, which holds a reference to the constant. If you are confused with the use of the ParentInformation type, this stems from the AST decoration and signals that we have a decorated RNode (which may have additional information in OtherInfo).

Yet again, this is not very interesting. When looking at the processors object you may be confused by many lines just mapping the node to the processAsNamedCall function. This is because during the dataflow analysis we actually "desugar" the AST, and treat syntax constructs like binary operators (e.g., x + y) as function calls (e.g. `+`(x, y)). We do this, because R does it the same way, and allows to even overwrite these operators (including if, <-, etc.) by their name. By treating them like R, as function calls, we get support for these overwrites for free, courtesy of flowR's call resolution.

But where are all the interesting things handled then? For that, we want to have a look at the built-in environment, which can be freely configured using flowR's configuration system. FlowR's heart and soul resides in the DefaultBuiltinConfig object, which is used to configure the built-in environment by mapping function names to BuiltInProcessorMapper functions. There you can find functions like processAccess which handles the (subset) access to a variable, or processForLoop which handles the primitive for loop construct (whenever it is not overwritten).

Besides the processor, an entry states what the function does with BuiltInFnInfo -- see Labeling the Built-Ins below for the labels it may carry.

Labeling the Built-Ins

Besides the processor, an entry says what the function is, in three label vocabularies:

  • CallProp labels how the called code behaves (props, a bitfield): whether it is pure, whether it throws, whether it returns invisibly, whether it dispatches, what it does to the frames around it. R's primitive generics (+, sin, length, ...) are Pure | Generic | Primitive, and as they have no R body, the store is the only place that can say they dispatch.
  • SemanticCallTag labels what semantic a call has (tags, an array): which resource it accesses, what it produces, what it is used for. print is Invisible | Generic with [Prints].
  • ArgProp labels each parameter (sig), in the order R declares them: which one carries the data, which one only selects a behavior, which one names a file, which one is called as a function.

For several analyses the labels are all they know about a call: BuiltInIndex turns them into the questions callers ask over and over (with, without, params), which is how the input-sources query knows which functions bring in data of their own, and how linting rules like seeded randomness find every call drawing from the RNG without naming a single one of them. Labeling a built-in therefore teaches all of them at once.

So lapply is pure on its own but runs what it is handed, and says which argument that is:

{ type: 'function', names: Identifier.fromAll(PkgName.Base, ['lapply', 'sapply', 'vapply']),
  processor: BuiltInProcName.Apply,
  config:    { indexOfFunction: 1, nameOfFunctionArgument: 'FUN', unquoteFunction: true,
               props: CallProp.MayPure | CallProp.Primitive, sig: [['X', ArgProp.Value], ['FUN', ArgProp.Callee], ['...', ArgProp.Value]] } }

while read.csv states what it does instead:

{ type: 'function', names: [Identifier.from(['read.csv', PkgName.Utils])],
  processor: BuiltInProcName.DefaultReadAllArgs,
  config:    { tags: [SemanticCallTag.File, SemanticCallTag.Reads], sig: [['file', ArgProp.Forced | ArgProp.Resource], ['header', ArgProp.Forced | ArgProp.Flag], ...] } }

The three tables below are generated from the configuration itself, so they always list every label that exists, what it means, and how many built-ins carry it.

What each call property means

db marks the bits the signature database states for any package function on its own (inferFnProps reads them off an entry and carries what a function calls over to the function calling it).

Call property Built-ins Meaning
Pure 367 computes a result and nothing else, the positive counterpart of hasUnknownSideEffects (excludes ImpureProps)
MayPure 92 pure on its own, but it runs code it is handed, so whatever that code does happens too. The parameter it runs is marked ArgProp.Callee or ArgProp.Nse, as with lapply(x, f).
Throwsdb 10 may signal an error, like stop() (see SigDbInferable)
Invisible 105 returns invisibly, so the result is not auto-printed
Genericdb 120 dispatches on the class of an argument (S3, S4, or S7), a group generic like + on either operand
Scope 60 binds, rebinds, or removes names outside of its own frame, like assign or library
Ambient 16 depends on ambient state like the clock, the locale, environment variables, or global options (stated instead of NonDet)
Configures 16 sets ambient state later calls read back: the working directory, environment variables, options, the locale, the RNG seed. The counterpart of CallProp.Ambient; a call doing both states both.
Ffi 9 calls native code through the foreign function interface, like .Call
Lang 79 produces a language object, like quote or deparse
Concurrentdb 43 runs its work in parallel (workers, a cluster, a future/promise backend); says nothing about purity, only reproducibility and where an error surfaces.
Primitive 308 the R language itself provides it: a .Primitive or .Internal of a base package, if and for and the operators included. Set from RBasePrimitives, which is read out of a real R, so it states what that R has rather than what a definition assumes. No package's sources contain these, which is why a signature database has no entry for them and flowR is the only thing that can answer.
What each semantic property means
Semantic property Built-ins Meaning
Random 28 draws from the random number generator, or sets its state (stated instead of NonDet)
File 287 touches the file system
TempFile 9 produces a temporary path; on its own this touches no file system, so a call that also does states File too
Network 85 always reaches the network, like curl::curl_download. Calls that only do so for some arguments, like read.csv of a URL, are left to the network-functions rule, which decides that per call site.
Process 13 runs a system command
User 44 asks the user, like readline or a file chooser
CommandLine 1 hands back what the program was invoked with, as commandArgs and the option parsers built on it do
Glob 4 yields the paths it matches at run time rather than one it was handed (list.files, Sys.glob); empty is an answer
Graphics 512 draws on a graphics device
Database 10 talks to a database
Opens 18 hands back a handle the program is expected to close again, like file or DBI::dbConnect
Closes 7 ends what an opener started: a graphics device, a connection, a sink. Narrower than SemanticCallTag.Graphics.
Reads 183 reads the resource its Resource arguments name
Writes 154 writes the resource its Resource arguments name
Prints 11 may emit to standard output, like print or a cat without a file, and follows a sink when one is active
Narrows 36 the result is bounded no matter what flows in: a count, an index, a logical, or one of the values of the argument marked ArgProp.Bounds. So nothing an argument carries reaches the result, which is what lets the input-sources query stop tracing at length(x) or match.arg(arg, choices).
Statistics 66 performs a statistical test, so its result is the test statistic a reader is meant to see (t.test, anova)
Deprecated 135 marked for removal, with a better alternative available, like dplyr::funs
Eval 11 dynamically executes R code or returns the value of dynamically computed identifiers, like eval, do.call, or get
Html 4 produces raw HTML or JavaScript, such as shiny::HTML
JavaScript 3 produces raw JavaScript code, such as shinyjs::runjs

Two pairs read like refinements but are not: TempFile does not imply File (making up a path touches no file system, so a call doing both states both), and Reads/Writes say what happens to the resource an ArgProp.Resource argument names, so they only ever appear next to a resource property.

Most of these properties combine freely. The exceptions are ExclusiveCallProps, which a test checks the whole configuration against:

  • Pure rules out MayPure, Scope, NonDet, Ambient, Configures, Ffi, Lang, Random, File, TempFile, Network, Process, User, CommandLine, Graphics, Database, Opens, Closes, Reads, Writes, Prints
  • NonDet rules out Ambient, Random
  • Random rules out Ambient
What each argument role means

A role is stated per parameter in the FnSig of a built-in, in the order R declares them, with ... covering every position from where it appears. The count is how many built-ins have at least one parameter in that role.

Argument role Built-ins Meaning
Forced 1192 evaluated whenever the call happens, even if the result goes unused, like x in force(x)
NoDefault 71 declared without a default value, like x in nchar(x, type); says nothing about whether a call must supply it
Alias 27 the result is this argument, handed back unchanged, like x in identity(x); this is what draws the Returns edge
Value 575 the result is computed from the argument's value, like x in sum(x)
Shape 24 only the shape is used (length, dimensions, names, other attributes), like x in nrow(x)
Flag 59 selects a behavior instead of carrying data, like na.rm in sum(x, na.rm = TRUE)
Resource 307 names the resource the call reads or writes, like file in write.csv(x, file)
Written 4 what it refers to may be modified, like envir in assign(x, v, envir = e)
Nse 15 quoted or evaluated in another frame, like expr in quote(expr)
Callee 49 called as a function, like FUN in lapply(x, FUN)
Presence 2 only whether it was supplied matters, as with missing()
Bounds 1 the result is one of this argument's values, like choices in match.arg(arg, choices). The bounding argument of a SemanticCallTag.Narrows call; without one such a call yields a value of its own making.
Atomic 16 only atomic data works here, never a closure, as with e1 in e1 > e2. A bare symbol in such an argument therefore names a variable even when a function of that name is in scope.
Handle 20 the open handle the call acts on, like con in close(con)
Injectable 35 open to injection, so a call handing it unescaped data is a finding: system commands, R expressions, database queries, HTML, or JavaScript.

Just as an example, we want to have a look at the processRepeatLoop function, as it is one of the simplest built-in processors we have:

  • processRepeatLoop
    Process a built-in repeat loop function call like repeat { ... }.

    Defined at src/dataflow/internal/process/functions/call/built-in/built-in-repeat-loop.ts#L29 
    /**
 * Process a built-in repeat loop function call like `repeat { ... }`.
 * @param name   - The name of the function being called.
 * @param args   - The arguments passed to the function.
 * @param rootId - The root node ID for the current processing context.
 * @param data   - Additional dataflow processor information.
 * @returns      - The resulting dataflow information after processing the repeat loop.
 */
export function processRepeatLoop<OtherInfo>(
    name: RSymbol<OtherInfo & ParentInformation>,
    args: readonly PotentiallyEmptyRArgument<OtherInfo & ParentInformation>[],
    rootId: NodeId,
    data: DataflowProcessorInformation<OtherInfo & ParentInformation>
): DataflowInformation {
    if(args.length !== 1 || RArgument.isEmpty(args[0])) {
        dataflowLogger.warn(`Repeat-Loop ${Identifier.toString(name.content)} does not have 1 argument, skipping`);
        return processKnownFunctionCall({ name, args, rootId, data, origin: 'default' }).information;
    }

    const unpacked = unpackNonameArg(args[0]);
    const { information, processedArguments } = processKnownFunctionCall({
        name,
        args:      unpacked ? [unpacked] : args,
        rootId,
        data,
        sig:       FunctionSemantics.call.signature.every,
        patchData: (d, i) => {
            if(i === 0) {
                return { ...d, cds: [...d.cds ?? [], { id: name.info.id }] };
            }
            return d;
        },
        markAsNSE:         [0],
        customControlFlow: true,
        origin:            BuiltInProcName.RepeatLoop
    });

    const body = processedArguments[0];
    guard(body !== undefined, () => `Repeat-Loop ${Identifier.toString(name.content)} has no body, impossible!`);

    linkCircularRedefinitionsWithinALoop(information.graph, produceNameSharedIdMap(findNonLocalReads(information.graph)), body.out, body.environment);
    reapplyLoopExitPoints(body.exitPoints, body.in.concat(body.out, body.unknownReferences), information.graph);

    information.exitPoints = filterOutLoopExitPoints(information.exitPoints);

    const graph = information.graph;
    const bodyEntry = ControlFlow.entryOf(body);
    ControlFlow.continuesWith(graph, body, bodyEntry);
    ControlFlow.jumpsTo(graph, body, ExitPointType.Next, bodyEntry);
    ControlFlow.jumpsTo(graph, body, ExitPointType.Break, rootId);

    /* the body is evaluated in the enclosing environment, so its definitions and removals have to bubble up */
    const kill = body.kill?.length ? body.kill : undefined;
    const leftByBreak = body.exitPoints.some(e => e.type === ExitPointType.Break);
    if(!leftByBreak) {
        /* without a `break` the loop never terminates, so nothing ever reaches the repeat vertex */
        information.exitPoints = information.exitPoints.filter(e => e.type !== ExitPointType.Default || e.nodeId !== rootId);
    }
    return {
        ...information,
        cfgEntry:    bodyEntry,
        cfgExit:     leftByBreak ? rootId : undefined,
        out:         information.out.concat(body.out),
        /* the body always runs at least once, so a removal within it is certain */
        environment: applyKills(information.environment, kill),
        kill
    };
}

Similar to any other built-in processor, we get the name of the function call which caused us to land here, as well as the passed arguments. The rootId refers to what caused the call to happen (and is usually just the function call), while data is our good old backpack, carrying all the information we need to produce a dataflow graph.

After a couple of common sanity checks at the beginning which we use to check whether the repeat loop is used in a way that we expect, we start by issuing the fold continuation by processing its arguments. Given we expect repeat <body>, we expect only a single argument. During the processing we make sure to stitch in the correct control dependencies, adding the repeat loop to the mix. For just the repeat loop the stitching is actually not necessary, but this way the handling is consistent for all looping constructs.

Afterward, we take the processedArguments, perform another round of sanity checks and then use two special functions to apply the semantic effects of the repeat loop. We first use one of flowR's linkers to linkCircularRedefinitionsWithinALoop and then retrieve the active exit points with filterOutLoopExitPoints.

Feel free to have a look around and explore the other handlers for now. Each of them uses the results of its children alongside the active backpack to produce a new dataflow information.

Beyond the Dataflow Graph

Given the dataflow graph, you can do a lot more! You can issue queries to explore the graph, search for specific elements, or, for example, request a static backward slice. Of course, all of these endeavors work not just with the RShell but also with the tree-sitter engine.

Static Backward Slicing

The slicing is available as an extra step as you can see by inspecting he DEFAULT_SLICING_PIPELINE. Besides STATIC_SLICE it contains a NAIVE_RECONSTRUCT to print the slice as (executable) R code.

Your main point of interesting here is the staticSlice function which relies on a modified breadth-first search to collect all nodes which are part of the slice. For more information on how the slicing works, please refer to the tool demonstration (Section 3.2), or the original master's thesis (Chapter 4).

You can explore the slicing using the REPL with the :slicer command:

$ docker run -it --rm eagleoutice/flowr # or npm run flowr 
flowR repl v2.15.8, R grammar v14 (tree-sitter engine)
R> :query @static-slice (12@product) file://test/testfiles/example.R
Output 
product <- 1
N <- 10
for(i in 1:(N-1)) product <- product  i
product
All queries together required ≈6 ms (1ms accuracy, total 7 ms)

Slice for the example file for the variable "prod" in line 12.

Gas (Resource Guard)

During a large analysis, flowR may run into memory or time pressure. The gas system provides per-feature resource guards that check the current heap usage and elapsed analysis time.

Any analysis site queries the level with FlowrAnalyzerGasContext::checkGas, where key is a feature name. The call is a no-op when gas is disabled for that key and no gas plugins are registered. Heap statistics come from the v8 module (Node.js, Electron, VS Code) or Chromium's performance.memory in browsers. If neither is available, gas skips the memory check and only the elapsed-time thresholds apply. Programmatic configs can supply a custom source via the heapProvider of the FlowrGasConfig (config.gas.heapProvider), and gas plugins can override levels entirely.

Level Value Description
GasLevel.Normal 0 Safe to continue, all resources are within bounds.
GasLevel.Problematic 1 Approaching a threshold. Consider emitting a warning and continue.
GasLevel.Critical 2 Threshold exceeded. The caller should skip the expensive work.

Enabling Gas for a Feature

Gas is disabled by default for every feature (see GasFeatureKey for all recognized keys). Enable it by setting a positive factor in config.gas.features:

{
  "gas": {
    "thresholds": {
      "memory": { "problematic": 0.7, "critical": 0.9 },
      "timeMs":  { "problematic": 100000, "critical": 120000 }
    },
    "features": {
      "source": 1
    }
  }
}

The factor scales both dimensions before comparing against the thresholds:

scaled_ratio   = (used_heap / heap_limit) * factor
scaled_elapsed = elapsed_ms              * factor

A factor of 2 makes the check twice as sensitive: it triggers Problematic when the heap is at 35% (= 0.7 / 2) instead of 70%.

Per-Feature Thresholds

A dataflow extraction, a linter pass and a static slice are not worth the same allowance, so each dimension of config.gas.thresholds may be bounded per feature key (see GasThresholdSpec), with default covering the keys that have no entry of their own:

{
  "gas": {
    "thresholds": {
      "timeMs": {
        "default": { "problematic": 60000, "critical": 120000 },
        "slicer":  { "problematic": 24000, "critical": 30000 }
      }
    },
    "features": {
      "slicer": 1
    }
  }
}

An entry only has to name the bounds it changes; the rest falls back to default and then to a directly given { problematic, critical } pair, which stays valid and still means "the same bound for everything".

Per-Operation Contingents

The elapsed-time bound is not measured from the creation of the analyzer. Each analysis run (parse, normalize, dataflow) and each staticSlice runs against a contingent of its own, so analysing a project and then asking for twenty slices gives twenty-one contingents, not one clock the analysis spent.

Anything beginning a new analysis restarts it too: an added file, a cache invalidation, a re-parse, or an explicit FlowrAnalyzer::reset. Operations in flight keep theirs, as restarting a running traversal's clock would defeat the guard bounding it. To split your own phases, call FlowrAnalyzerGasContext::reset on the writeable context (analyzer.context().gas.reset()) - supported API, not an internal hook.

Bounding a Single Call

Bounds for one call, keyed by the same feature names and measured from that call (see GasOverrides):

await analyzer.query([{ type: 'static-slice', criteria: ['12@product'] }], {
    gas: { slicer: { critical: 30_000 } }
});

Bare problematic/critical numbers are elapsed milliseconds; use timeMs/memory to be explicit and factor for the sensitivity. Naming a feature enables gas for it even when config.gas.features disables it (pass factor: 0 to keep it off). FlowrAnalyzer::runFull and FlowrAnalyzer::runSearch take the same, and read-only holders of a context can derive a bounded view with FlowrAnalyzerGasContext::scope.

When the Slicer Runs Out

A slice cut short comes back with stoppedEarly and a progress saying how far it got (see SliceProgress). A frontier of 0 means the queue drained after all; a small frontier next to a large visited says little is missing. Without it a truncated slice is all-or-nothing, and "as far as flowR got" is not "what is independent", so it would have to be discarded.

Known Feature Keys

Known feature keys accepted by ReadOnlyFlowrAnalyzerGasContext.checkGas , each a sensitivity factor in FlowrGasConfig.features .

Key Description
source Gas key for built-in source() file analysis.
side-effect-linking Gas key for the side-effect link resolution phase of the dataflow extractor (matches unknown side effects against call sites via the CFG).
linter Gas key for the linter, checked once per rule; remaining rules are skipped under critical pressure.
slicer Gas key for the static slicer, checked while traversing the dataflow graph; a hit stops traversal early (SliceResult.stoppedEarly).
dataflow Gas key for dataflow extraction. Unlike the keys above it is armed once per run (see
ReadOnlyFlowrAnalyzerGasContext.budget
) and counted as the fold goes.

You can search for ctx.gas.checkGas( in the source to locate every active check site.

Gas Plugins

Base class for gas plugins, queried on-demand by FlowrAnalyzerGasContext.checkGas . Override process to provide a custom resource-pressure assessment for a feature key. Return undefined to defer to the built-in memory and time checks. Multiple Gas plugins are combined by taking the maximum ( GasLevel ) returned by any plugin or by the built-in checks. A gas plugin is the right place to add domain-specific checks (e.g., CPU, I/O, quota limits) or to override default behavior for testing by returning a hardcoded level.

class MyGasPlugin extends FlowrAnalyzerGasPlugin {
    readonly name        = 'my-gas-plugin';
    readonly description = 'Returns Critical for source when RSS exceeds 1 GB.';
    readonly version     = new SemVer('1.0.0');

    protected process(_ctx: FlowrAnalyzerContext, key: string): GasLevel | undefined {
        if(key === GasFeatureKey.Source) {
            const { rss } = process.memoryUsage();
            if(rss > 1024 * 1024 * 1024) {
                return GasLevel.Critical;
            }
            if(rss > 512  * 1024 * 1024) {
                return GasLevel.Problematic;
            }
        }
        return undefined;
    }
}

return await new FlowrAnalyzerBuilder()
    .registerPlugins(new MyGasPlugin())
    .setEngine('tree-sitter')
    .build();

Currently maintained by Florian Sihler and Oliver Gerstl at Ulm University
Email | GitHub | Penguins | Portfolio

💮 flowR Home (Landing Page)

Clone this wiki locally