# How we made JavaScript analyzer understand control flow

We recently added JavaScript/TypeScript support to PVS\-Studio analyzer\. From its first release, the analyzer can detect control\-flow bugs in code\. In this article, we'll learn about the control flow graph \(CFG\), how we've implemented it, and why it's useful\.

![1418_js_cfg/image1.png](https://import.viva64.com/docx/blog/1418_js_cfg/image1.png)

## A Control Flow Graph?

I've touched on this topic before, in my [series](https://pvs-studio.com/en/blog/posts/java/1198/) on taint analysis in Java, but let's quickly recap it here\. A static analyzer starts by converting source code into an abstract syntax tree \(AST\)\. It almost completely mirrors the structure of the code as you write it in the editor\. That makes it a poor fit for anything involving control flow analysis, such as finding unreachable code\. It's possible to write a check for unreachable code on the AST, but:

1. this would be unreliable in corner cases;
1. this wouldn't scale well to similar rules;
1. this would be hard to maintain\. Every bug fix or new language version would mean revisiting all of these diagnostic rules\.

The Control Flow Graph \(CFG\) exists to address these issues; it maps out all possible execution paths in a program\.

![1418_js_cfg/image2.png](https://import.viva64.com/docx/blog/1418_js_cfg/image2.png)

The CFG consists of three components:

1. entry and exit nodes;
1. Basic blocks nodes, each containing linear instructions;
    * Each basic block ends with a terminator \(or with nothing\)\. A terminator is a special instruction that determines specific semantics for the execution flow: branching, `break`/`continue`, and so on\.
1. Edges between nodes that represent possible control flow transitions\.

![1418_js_cfg/image3.png](https://import.viva64.com/docx/blog/1418_js_cfg/image3.png)

## How did we do it?

### Common CFG

In our [article](https://pvs-studio.com/en/blog/posts/js/1363/) on developing the JavaScript/TypeScript analyzer, we [mentioned](https://pvs-studio.com/en/blog/posts/js/1363/#IDC01AE1A5F1) that the tool includes not only a syntax tree for each specific language, but also a common one for multilingual analysis\. We named it CAT \(Common Abstract Tree\)\.

No other languages have joined JavaScript/TypeScript yet, but we've already made the CFG extensible: the core engine doesn't depend on any specific language\. We define a set of multiple semantics and just combine them like building blocks into a CFG for a specific language we need\. It'll save time when it comes to supporting other languages in the future\.

![1418_js_cfg/image4.png](https://import.viva64.com/docx/blog/1418_js_cfg/image4.png)

Here are two examples of language\-specific semantics for JavaScript/TypeScript:

* The `try` blocks in which exceptions are untyped, and only one `catch` is allowed\.
* Labels are attached to a specific statement, and you can jump to them only from the `break` statement nested within that statement\. You can also jump to the label using `continue` if it is inside a loop\.

### Testing approach

Checking that a CFG is correct is quite an adventure of its own\. The first thing that comes to mind is to serialize the graph in [Graphviz](https://en.wikipedia.org/wiki/Graphviz) \(or some other way\), check it visually, and save it as a reference\. Spoiler: that was a trap, and we fell into it\. Here's why it doesn't work:

* The graph changes constantly during development\. You end up manually rewriting the failing tests or burning through AI agents' tokens\.
* It's very easy to miss a bug in the reference\. If people didn't make mistakes, the static analysis industry wouldn't exist\.
* A neat\-looking topology doesn't guarantee that the graph captures the full semantics of the control flow\.

So we changed the approach and wrote a mini\-interpreter for our CAT, driven by the CFG\. The idea is simple: if our interpreter, after traversing the graph, produces the same result as the JavaScript interpreter, the graph is constructed correctly\. We verify this with a simple assertion API, like this:

```cpp
@Test
void branching() {
    EvaluationAssert.evaluate("branching")
                    .withParam("param", true)
                    .expect("a", 2);

    EvaluationAssert.evaluate("branching")
                    .withParam("param", false)
                    .expect("a", 0);
}
```

This test runs the interpreter and compares the execution results with the reference, which you can get by running the TypeScript code beforehand:

```cpp
function branching(param: boolean) {
    let a = 1;
    if (param) {
        a++;
    } else {
        a--;
    }
}
```

We didn't have to implement the entire JavaScript specification—a tiny subset was enough\. Cutting corners actually worked in our favor: if you don't clear variables when they go out of scope, you can inspect the state of the code at different points\.

![1418_js_cfg/image5.png](https://import.viva64.com/docx/blog/1418_js_cfg/image5.png)

Another nice bonus: the minimalist interpreter is a full\-fledged proof of concept for graph processing\. It can serve both as a reference for using the API and as groundwork for upcoming data\-flow analysis\.

The result is a working graph builder for JavaScript/TypeScript that constructs each graph in a single AST traversal\. It's quite fast: for [React](https://www.google.com/search?client=firefox-b-d&q=react&sei=_ymVao7PAuev5NoPzafroAY), all graphs are built in a quarter of a second\.

## What it can catch today

### Linear code

The most basic typos, the kind the AST could catch too, come first, of course:

```cpp
if ( curveLengths[ i ] >= d ) {
    diff = curveLengths[ i ] - d;
    curve = this.curves[ i ];
    var u = 1 - diff / curve.getLength();
    return curve.getPointAt( u );
    break;
}
```

The PVS\-Studio warning: [V7039](https://pvs-studio.com/en/docs/warnings/v7039/) Unreachable code detected\. Control flow never reaches this statement\. [three\.js 29417](https://github.com/juice-shop/juice-shop/blob/1618a611b173b4bf114028e6e02549950606e29d/frontend/src/assets/private/three.js#L29417)\.

That's the graph built by the analyzer:

![1418_js_cfg/image6.png](https://import.viva64.com/docx/blog/1418_js_cfg/image6.png)



<details>
   <summary>What are merge nodes?</summary>

A merge node is an auxiliary node used during graph construction\. It makes the graph easier to work with, because nodes with multiple predecessors are cumbersome to handle\. The analysis doesn't use merge nodes \(yet\)\. 

In the example above, the merge has only one incoming edge instead of two, as in the previous scheme, because the `true` branch contains a `return`, which requires an edge to be created straight to the exit node\. 


</details>
The graph shows clearly no path lead to `break`, so the analyzer marks it as unreachable\. 

It's unlikely that this error has any effect, and the unreachable `break` is probably just redundant\. But here's the interesting part: this file is the [Three\.js](https://github.com/mrdoob/three.js/) library, copied into [Juice Shop](https://github.com/juice-shop/juice-shop/), and we couldn't find the same error in the current Three\.js repository\.

By the way, here's a classic bug involving automatic semicolon insertion \(ASI\):

```cpp
function foo() {
    return // asi happens here
        this.bar
}
```

The analyzer catches it the same way\. The inserted `;` creates a terminator in the block containing the `return` and moves `this.bar` to the next block:

![1418_js_cfg/image7.png](https://import.viva64.com/docx/blog/1418_js_cfg/image7.png)

### Conditions

[Phaser](https://github.com/phaserjs/phaser) gives us a good example of "defensive programming":

```cpp
if (!childA.parentContainer && !childB.parentContainer)
{
    return this.displayList.getIndex(childB)
      - this.displayList.getIndex(childA);
}
else if (childA.parentContainer === childB.parentContainer) {
// more branches ending with return statements here
} else
{
    var listA = childA.getIndexList();
    var listB = childB.getIndexList();
    var len = Math.min(listA.length, listB.length);

    for (var i = 0; i < len; i++)
    {
        var indexA = listA[i];
        var indexB = listB[i];

        if (indexA === indexB)
        {
            continue;
        }
        else
        {
            return indexB - indexA;
        }
    }
    return listB.length - listA.length;
}
//  Technically this shouldn't happen, but ...
// eslint-disable-next-line no-unreachable
return 0;
```

The PVS\-Studio warning: [V7039](https://pvs-studio.com/en/docs/warnings/v7039/) Unreachable code detected\. Control flow never reaches this statement\. [InputPlugin\.js 2981](https://github.com/phaserjs/phaser/blob/02d8931b626d9764c133cbb3fbf99966c03c757c/src/input/InputPlugin.js#L2981)

There were more `else-if` branches, but I removed them to keep the example short and to the graph small:

![1418_js_cfg/image9.png](https://import.viva64.com/docx/blog/1418_js_cfg/image9.png)

If you peruse the comment and look at the code, the programmers' concern starts making sense: the logic above is complex, merging more than 5 branches, each of which terminates the execution flow\. Devs decided to play it safe, not even trusting ESLint\. Following its trail, the analyzer saw from the graph's topology that there is simply no path to `return 0`\.

### Loops

As a bonus, we also get the ability to identify loops that run infinitely or, conversely, only once\. I found such a case in the already mentioned Three\.js:

```cpp
loop:
for (var pos = 0; pos < limit; pos++) {
    for (; pos < limit; pos++) {                 // <=
        for (var k = 0; k < needleLength; k++) {
            if (haystack[pos + k] !== needle[k]) {
                continue loop;
            }
        }

        return pos;
    }
}
```

The PVS\-Studio warning: [V7039](https://pvs-studio.com/en/docs/warnings/v7039/) Unreachable code detected\. Control flow never reaches this statement\. [opentype\.module\.js 6109](https://github.com/mrdoob/three.js/blob/aa625d502d4920a84975c80a6438c108678fb4ac/examples/jsm/libs/opentype.module.js#L6109)\.

Here is the control flow graph:

![1418_js_cfg/image10.png](https://import.viva64.com/docx/blog/1418_js_cfg/image10.png)

The diagnostic rule warns that the increment of the `pos` variable in the loop is unreachable\. Looking at the code, you can easily see that all the branches indeed terminate the second `for` loop, so it runs only once\. The graph confirms this—there is no path to the increment\.

This code originally came from [OpenType](https://github.com/opentypejs/opentype.js), but the copied dependency was removed at the time of the writing\.

### Exception handling

Nested `try` blocks and execution flow interruptions from `finally` are rare andoften considered a code smell, so I couldn't find any instances in open\-source code right away\.

Still, this was one of the trickiest cases to handle due to the complexity of the `try-catch-finally` semantics\. The analyzer has to handle several things:

* Check if the `try` block contains a `catch`, a `finally`, or both;
* Track explicit `throw` statements and also handle where implicit exceptions lead\.
* Override the control flow interruption within the `finally` block when the control flow interruption occurs in `try` or `catch`\.
* Propagate the control flow interruption that occurs in `finally` up through the `try` block\. 
* Cover many other edge cases and their combinations\.

Since I still want to show this case, here's a synthetic example:

```cpp
function tryCatchFinallyCase() {
    try {
        try {
            throw new Error("Whoops");
        } finally {
            console.log("inner")
        }
        return true // V7039
    } finally {
        console.log("outer")
    }
    return false; // V7039
}
```

For this function, the analyzer will construct the following graph:

![1418_js_cfg/image11.png](https://import.viva64.com/docx/blog/1418_js_cfg/image11.png)

The diagram clearly shows that the edges themselves carry information about which operation they "remembered" before exiting the function\. The analyzer also identifies the unreachable `return` nodes\. 

## What's next?

We've walked through the errors that the analyzer can now detect thanks to control flow graph support\. It has already proven its capabilities, making it fairly straightforward to implement diagnostic rules [V7039](https://pvs-studio.com/en/docs/warnings/v7039/) \(unreachable code\) and [V7040](https://pvs-studio.com/en/docs/warnings/v7040/) \(infinite recursion\) by the time PVS\-Studio 8\.00 was released\. Beyond adding new diagnostic rules, other opportunities are opening up:

* Extend the CFG construction by applying it to short\-circuit expressions\.
* Find dead code as well as unreachable code, using conditional constant propagation\. Once we have laid the groundwork for the data\-flow analysis engine, we can implement [taint analysis](https://pvs-studio.com/en/blog/terms/6496/) \(tracking tainted data throughout the program\)\.
* Extend the same engine to other kinds of [data\-flow analysis](https://pvs-studio.com/en/blog/terms/7004/), such as detecting null dereference, division by zero, and so on\.

In short, CAT grows the analyzer wider, and the CFG lets us grow it deeper\. The ground for developing the new analyzer is now even more productive\.

## Wrap\-up

That's the end of the brief overview of the analyzer's technology\. I hope you enjoyed seeing how static analysis works and what kinds of errors control flow analysis can find\. If you've worked with similar technologies, share your experience in the comments\. I'd love to read your stories\. The promised article on the inner workings of CAT is still on the way, along with more articles on code quality\. Follow us to stay tuned:

* PVS\-Studio in [X](https://x.com/pvs_studio);
* [monthly newsletter](https://pvs-studio.com/en/subscribe/);
* my personal [blog](https://twitter.com/kvolokhovskii)\.