7.2. Binding Graph#

The binding graph is a graph structure that represents the relationships between identifiers across source files in a CompilationUnit. It stores cursors to all definitions and references, and can resolve the edges between them.

Building this graph can be an expensive operation. So, it is constructed lazily on the first access, and cached thereafter. You can use cursors to query the graph for definitions or references.

Any identifier in the tree can be resolved to a definition or a reference. Note that there are multiple kinds of identifiers. For example, Solidity has Identifier, and Yul has YulIdentifier. To find/filter terminals that are identifiers, you can use the TerminalKindExtensions.isIdentifier() API to test for that.

Resolving Definitions#

To resolve definitions we need to provide the binding graph with a cursor pointing to the identifier. Some identifiers in the code may not be acting as definitions. In those cases, definitionAt() will return undefined.

Definition objects will contain two binding locations:

nameLocation referring to the identifier that resolved to the definition
definiensLocation referring to the CST node that is being defined (a contract, function, struct, etc)

Because binding graphs span multiple files, these locations are not simple Cursor objects. Instead they are BindingLocation objects, which can refer to locations in user files or built-ins:

UserFileLocation in turn contains the fileId and the cursor in the CST tree of the file.
BuiltInLocation refers to a location in system defined built-in. You may get a definition on such a location when finding which definitions a Reference binds to (see section below), but never when resolving to a definition from a cursor.

find-definitions.mts

import assert from "node:assert";
import { assertTerminalNode, TerminalKindExtensions } from "@nomicfoundation/slang/cst";
import { CompilationUnit } from "@nomicfoundation/slang/compilation";
import { assertUserFileLocation, Definition } from "@nomicfoundation/slang/bindings";

export function findDefinitionsInFile(unit: CompilationUnit, fileId: string): Definition[] {
  const file = unit.file(fileId);
  assert(file);

  const definitions = [];

  // traverse the file's CST tree looking for identifiers
  const cursor = file.createTreeCursor();
  while (cursor.goToNextTerminal()) {
    assertTerminalNode(cursor.node);
    if (!TerminalKindExtensions.isIdentifier(cursor.node.kind)) {
      continue;
    }

    // attempt to resolve a definition
    const definition = unit.bindingGraph.definitionAt(cursor);

    if (definition) {
      // name should be located in the file we queried
      assertUserFileLocation(definition.nameLocation);
      assert.strictEqual(definition.nameLocation.fileId, fileId);

      // definiens should too be located in the file we queried
      assertUserFileLocation(definition.definiensLocation);
      assert.strictEqual(definition.definiensLocation.fileId, fileId);

      definitions.push(definition);
    }
  }

  return definitions;
}

User file binding locations will also contain a cursor to the underlying identifier or CST node of the entity defined. Using the same contract from last section, we can look for definitions in the contract.sol file:

resolving-definitions.mts

import assert from "node:assert";
import { buildCompilationUnit } from "../../common/compilation-builder.mjs";
import { findDefinitionsInFile } from "./find-definitions.mjs";
import { NonterminalKind } from "@nomicfoundation/slang/cst";
import { assertUserFileLocation } from "@nomicfoundation/slang/bindings";

test("find definitions in file", async () => {
  const unit = await buildCompilationUnit();
  const definitions = findDefinitionsInFile(unit, "contract.sol");

  const found = [];
  for (const definition of definitions) {
    assertUserFileLocation(definition.nameLocation);
    const name = definition.nameLocation.cursor.node.unparse();

    assertUserFileLocation(definition.definiensLocation);
    const kind = definition.definiensLocation.cursor.node.kind;

    found.push({ name, kind });
  }

  assert.strictEqual(found.length, 3);
  assert.deepEqual(found, [
    { name: "Log", kind: NonterminalKind.ImportDeconstructionSymbol },
    { name: "MyContract", kind: NonterminalKind.ContractDefinition },
    { name: "test", kind: NonterminalKind.FunctionDefinition },
  ]);
});

We find 3 definitions:

the Log imported symbol
the MyContract contract
the test method

The Log import symbol is a special case and also acts as a reference to the actual event type defined in events.sol. Let's find all references in the file next.

Resolving References#

In the same way to resolving definitions, we can also attempt to resolve a cursor to an identifier to a reference. If the resolution is successful, the returned Reference will have a location pointing to the identifier. As before, we can expect this location to be in the user file whose CST tree we are querying.

find-references.mts

import assert from "node:assert";
import { assertTerminalNode, TerminalKindExtensions } from "@nomicfoundation/slang/cst";
import { CompilationUnit } from "@nomicfoundation/slang/compilation";
import { assertUserFileLocation, Reference } from "@nomicfoundation/slang/bindings";

export function findReferencesInFile(unit: CompilationUnit, fileId: string): Reference[] {
  const file = unit.file(fileId);
  assert(file);

  const references = [];

  // traverse the file's CST tree looking for identifiers
  const cursor = file.createTreeCursor();
  while (cursor.goToNextTerminal()) {
    assertTerminalNode(cursor.node);
    if (!TerminalKindExtensions.isIdentifier(cursor.node.kind)) {
      continue;
    }

    // attempt to resolve a reference
    const reference = unit.bindingGraph.referenceAt(cursor);

    if (reference) {
      // should be located in the file we queried
      assertUserFileLocation(reference.location);
      assert.strictEqual(reference.location.fileId, fileId);

      references.push(reference);
    }
  }

  return references;
}

We can now find all the references in the same contract.sol file:

resolving-references.mts

import assert from "node:assert";
import { buildCompilationUnit } from "../../common/compilation-builder.mjs";
import { findReferencesInFile } from "./find-references.mjs";
import { assertUserFileLocation } from "@nomicfoundation/slang/bindings";

test("find references in file", async () => {
  const unit = await buildCompilationUnit();
  const references = findReferencesInFile(unit, "contract.sol");

  const found = [];
  for (const reference of references) {
    assertUserFileLocation(reference.location);
    const name = reference.location.cursor.node.unparse();
    const line = reference.location.cursor.textRange.start.line;

    found.push({ name, line });
  }

  assert.strictEqual(found.length, 4);
  assert.deepEqual(found, [
    { name: "Log", line: 1 },
    { name: "Log", line: 5 },
    { name: "msg", line: 5 },
    { name: "sender", line: 5 },
  ]);
});

Navigating between definitions and references#

Iterating over the references found in the last section, we can find where are the definitions they refer to by using the definitions() method of Reference:

references-to-definitions.mts

import assert from "node:assert";
import { buildCompilationUnit } from "../../common/compilation-builder.mjs";
import { findReferencesInFile } from "./find-references.mjs";
import { NonterminalKind } from "@nomicfoundation/slang/cst";
import { assertUserFileLocation } from "@nomicfoundation/slang/bindings";

test("navigate from references to definitions", async () => {
  const unit = await buildCompilationUnit();
  const references = findReferencesInFile(unit, "contract.sol");

  const found = [];
  for (const reference of references) {
    assertUserFileLocation(reference.location);
    const name = reference.location.cursor.node.unparse();
    const line = reference.location.cursor.textRange.start.line;

    // find definitions this reference binds to
    const definitions = [];
    for (const definition of reference.definitions()) {
      if (definition.nameLocation.isUserFileLocation() && definition.definiensLocation.isUserFileLocation()) {
        // it's a user provided definition
        definitions.push({
          file: definition.nameLocation.fileId,
          kind: definition.definiensLocation.cursor.node.kind,
        });
      } else {
        // it's a built-in
        definitions.push({ file: "BUILT-IN" });
      }
    }

    found.push({ name, line, definitions });
  }

  assert.strictEqual(found.length, 4);
  assert.deepEqual(found, [
    { name: "Log", line: 1, definitions: [{ file: "events.sol", kind: NonterminalKind.EventDefinition }] },
    {
      name: "Log",
      line: 5,
      definitions: [
        { file: "contract.sol", kind: NonterminalKind.ImportDeconstructionSymbol },
        { file: "events.sol", kind: NonterminalKind.EventDefinition },
      ],
    },
    { name: "msg", line: 5, definitions: [{ file: "BUILT-IN" }] },
    { name: "sender", line: 5, definitions: [{ file: "BUILT-IN" }] },
  ]);
});

There are two interesting observations here:

Slang recognizes the Solidity built-in global variable msg and its member sender. See next section for more details and an example use case.
There may be multiple definitions bound to our reference: the Log identifier in the emit statement refers to the imported symbol, and also to the event type which is declared in a different file.

There are other cases where Slang may return multiple definitions for a reference. Function overloads and virtual method calls are typical examples.

Starting from a definition, we can also query the binding graph for all places where it's being referred to with the method references() of Definition objects. In this example, we navigate from the Log event definition in events.sol back to the two references in contract.sol:

definitions-to-references.mts

import assert from "node:assert";
import { buildCompilationUnit } from "../../common/compilation-builder.mjs";
import { findDefinitionsInFile } from "./find-definitions.mjs";
import { NonterminalKind } from "@nomicfoundation/slang/cst";
import { assertUserFileLocation } from "@nomicfoundation/slang/bindings";

test("navigate from definitions to references", async () => {
  const unit = await buildCompilationUnit();
  const definitions = findDefinitionsInFile(unit, "events.sol");

  // there are three definitions in the file: the event and its two parameters
  assert.strictEqual(definitions.length, 3);

  // we only care about the event type definition for this example
  const logEvent = definitions[0];
  assertUserFileLocation(logEvent.definiensLocation);
  assert.strictEqual(logEvent.definiensLocation.cursor.node.kind, NonterminalKind.EventDefinition);

  // find references bound to its definition
  const references = logEvent.references();
  assert.strictEqual(references.length, 2);

  // first should be the import statement
  assertUserFileLocation(references[0].location);
  assert.strictEqual(references[0].location.fileId, "contract.sol");
  assert.strictEqual(references[0].location.cursor.textRange.start.line, 1);

  // second should be the emit statement
  assertUserFileLocation(references[1].location);
  assert.strictEqual(references[1].location.fileId, "contract.sol");
  assert.strictEqual(references[1].location.cursor.textRange.start.line, 5);
});