8.4. Find unused definitions#

Let's now explore a more complex example. We want to find all definitions in a compilation unit that are not referenced from a main contract. The general idea of the algorithm to implement is as follows: starting from the given contract, mark all constructors and public functions, as well as any inherited contracts or implemented interfaces. After that, recursively process (visit) each marked definition following references we find inside them.

As a result, we'll get a list of definitions that are reachable from our main contract. We get the unused definitions by subtracting this set from all the definitions available in the compilation unit. An important thing to note is that this will include nested definitions. For example, variables and parameters in an unused function, or fields in an unused struct. To clean this up, we make a final pass to remove definitions nested inside other unused definitions.

Disclaimer: This is only an example and to keep it relatively short, we won't cover all possible corner cases. The resulting algorithm may produce both false positives and false negatives.

find-unused-definitions.mts

import { CompilationUnit } from "@nomicfoundation/slang/compilation";
import { assertUserFileLocation, Definition } from "@nomicfoundation/slang/bindings";
import { findContractByName } from "./find-contract-by-name.mjs";
import { collectDefinitions, collectAllDefinitions } from "./collect-definitions.mjs";
import { visitDefinition } from "./visit-definition.mjs";

export function findUnusedDefinitions(unit: CompilationUnit, startingContractName: string): Definition[] {
  const allDefinitions = collectAllDefinitions(unit);
  const unusedDefinitions = new Map(allDefinitions.map((definition) => [definition.id, definition]));

  const visitQueue = [findContractByName(unit, startingContractName)];
  while (visitQueue.length > 0) {
    const toVisit = visitQueue.shift()!;
    if (!unusedDefinitions.has(toVisit.id)) continue;
    unusedDefinitions.delete(toVisit.id);

    const definiensLocation = toVisit.definiensLocation;
    assertUserFileLocation(definiensLocation);

    const followed = visitDefinition(unit, definiensLocation.cursor.spawn());
    visitQueue.push(...followed);
  }

  // for remaining unused definitions, remove any nested definitions inside them
  // to prevent reporting eg. a function and all its parameters
  visitQueue.push(...unusedDefinitions.values());
  while (visitQueue.length > 0) {
    const toVisit = visitQueue.shift()!;
    if (!unusedDefinitions.has(toVisit.id)) continue;

    const definiensLocation = toVisit.definiensLocation;
    assertUserFileLocation(definiensLocation);

    const innerDefinitions = collectDefinitions(unit, definiensLocation.cursor);
    for (const inner of innerDefinitions) {
      if (inner.id == toVisit.id) continue;
      unusedDefinitions.delete(inner.id);
    }
  }

  return Array.from(unusedDefinitions.values());
}

To implement the above we use several auxiliary functions. First and foremost, we need a way to collect definitions, both in the whole compilation unit, as well as under a specific cursor. We can accomplish this using the Cursor API and the Binding Graph API:

collect-definitions.mts

import { assertTerminalNode, Cursor, TerminalKindExtensions } from "@nomicfoundation/slang/cst";
import { CompilationUnit } from "@nomicfoundation/slang/compilation";
import { Definition } from "@nomicfoundation/slang/bindings";

export function collectAllDefinitions(unit: CompilationUnit): Definition[] {
  const allDefinitions = [];
  for (const file of unit.files()) {
    const cursor = file.createTreeCursor();
    allDefinitions.push(...collectDefinitions(unit, cursor));
  }
  return allDefinitions;
}

export function collectDefinitions(unit: CompilationUnit, root: Cursor): Definition[] {
  const cursor = root.spawn();
  const definitions = [];
  while (cursor.goToNextTerminal()) {
    assertTerminalNode(cursor.node);
    if (!TerminalKindExtensions.isIdentifier(cursor.node.kind)) continue;

    const definition = unit.bindingGraph.definitionAt(cursor);
    if (!definition) continue;

    definitions.push(definition);
  }
  return definitions;
}

The other important piece of the puzzle is the visitDefinition function. This is where we decide what is reachable from a definition, and what we do here depends on the kind we're visiting, aka. the kind of the definiens node of the definition. For FunctionDefinition and ModifierDefinition, we want to follow all references enclosed in them to visit the definitions they bind to. For libraries, structs and enums, we want to do no further processing. Their fields and members should be explicitly referenced to be considered used.

As we said earlier, for a ContractDefinition, public state variables and functions should be marked and queued for visiting later. Constructors and other special functions do not have an identifier that names them and therefore will not create definitions in the binding graph. So, we want to visit their declarations explicitly to find references in them. All this behavior is complex enough to warrant its own, separate function visitContract. We use queries to find the different components of the contract.

visit-definition.mts

import assert from "node:assert";
import { assertNonterminalNode, Cursor, NonterminalKind, Query } from "@nomicfoundation/slang/cst";
import { CompilationUnit } from "@nomicfoundation/slang/compilation";
import { Definition } from "@nomicfoundation/slang/bindings";
import { collectDefinitions } from "./collect-definitions.mjs";
import { followAllReferences } from "./follow-all-references.mjs";

export function visitDefinition(unit: CompilationUnit, definiens: Cursor): Definition[] {
  assertNonterminalNode(definiens.node);
  const kind = definiens.node.kind;

  if (kind == NonterminalKind.ContractDefinition) {
    // special case contracts; see below
    return visitContract(unit, definiens);
  } else if (
    kind == NonterminalKind.LibraryDefinition ||
    kind == NonterminalKind.StructDefinition ||
    kind == NonterminalKind.EnumDefinition
  ) {
    // members must be explicitly referenced
    return [];
  } else if (kind == NonterminalKind.FunctionDefinition || kind == NonterminalKind.ModifierDefinition) {
    // follow any references inside, but don't automatically reference any new
    // definitions (eg. a parameter)
    return followAllReferences(unit, definiens);
  } else {
    // anything else (events, errors, interfaces) should be considered fully
    // referenced (including inner definitions) and we need to follow any
    // references inside them
    const otherDefinitions = collectDefinitions(unit, definiens);
    return followAllReferences(unit, definiens).concat(otherDefinitions);
  }
}

function visitContract(unit: CompilationUnit, cursor: Cursor): Definition[] {
  // for a contract, we need to explicitly follow inheritance specifiers and constructors,
  // and visit state variables and public functions
  const visitedDefinitions = [];

  const inheritance = Query.create(`
    [InheritanceSpecifier]
  `);
  const unnamedFunctions = Query.create(`
    (
      [ConstructorDefinition]
    | [ReceiveFunctionDefinition]
    | [FallbackFunctionDefinition]
    | [UnnamedFunctionDefinition]
    | [FunctionDefinition [FunctionName [FallbackKeyword]]]
    | [FunctionDefinition [FunctionName [ReceiveKeyword]]]
    )
  `);
  const publicFunctions = Query.create(`
    [FunctionDefinition
      name: [FunctionName @name [Identifier]]
      attributes: [_ [FunctionAttribute [PublicKeyword]]]
    ]
  `);
  const publicStateVars = Query.create(`
    [StateVariableDefinition
      attributes: [_ [StateVariableAttribute [PublicKeyword]]]
      @name name: [Identifier]
    ]
  `);
  const matches = cursor.query([inheritance, unnamedFunctions, publicFunctions, publicStateVars]);
  for (const match of matches) {
    switch (match.queryIndex) {
      case 0:
      case 1:
        visitedDefinitions.push(...followAllReferences(unit, match.root));
        break;
      case 2:
      case 3:
        const innerDefinition = unit.bindingGraph.definitionAt(match.captures["name"][0]);
        assert(innerDefinition);
        visitedDefinitions.push(innerDefinition);
        break;
    }
  }
  return visitedDefinitions;
}

When analyzing functions bodies, expressions and blocks of statements, we need to follow all references to their bound definitions to mark them as used. This again is simple to implement with the Cursor and Binding Graph APIs:

follow-all-references.mts

import { assertTerminalNode, Cursor, TerminalKindExtensions } from "@nomicfoundation/slang/cst";
import { CompilationUnit } from "@nomicfoundation/slang/compilation";
import { Definition } from "@nomicfoundation/slang/bindings";

export function followAllReferences(unit: CompilationUnit, root: Cursor): Definition[] {
  const referencedDefinitions = [];
  const cursor = root.spawn();
  while (cursor.goToNextTerminal()) {
    assertTerminalNode(cursor.node);
    if (!TerminalKindExtensions.isIdentifier(cursor.node.kind)) continue;

    const reference = unit.bindingGraph.referenceAt(cursor);
    if (!reference) continue;

    for (const definition of reference.definitions()) {
      if (definition.nameLocation.isBuiltInLocation()) continue;
      referencedDefinitions.push(definition);
    }
  }

  return referencedDefinitions;
}

Lastly, we need a way to locate the initial contract. This is similar to what we implemented in the first example, but now we want to return a Binding Graph Definition object to kickstart our algorithm:

find-contract-by-name.mts

import assert from "node:assert";
import { Query } from "@nomicfoundation/slang/cst";
import { CompilationUnit } from "@nomicfoundation/slang/compilation";
import { Definition } from "@nomicfoundation/slang/bindings";

export function findContractByName(unit: CompilationUnit, contractName: string): Definition {
  for (const file of unit.files()) {
    const cursor = file.createTreeCursor();
    const query = Query.create(`
      [ContractDefinition
        @name name: [Identifier]
      ]
    `);
    const matches = cursor.query([query]);

    for (const match of matches) {
      const nameCursor = match.captures["name"][0];
      const name = nameCursor.node.unparse();
      if (name == contractName) {
        const definition = unit.bindingGraph.definitionAt(nameCursor);
        assert(definition);
        return definition;
      }
    }
  }

  throw new Error(`Could not find contract named ${contractName}`);
}

Finally, we can test the functionality on a slightly larger Solidity example:

test-find-unused-definitions.mts

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

const CONTRACT_VFS = new Map<string, string>([
  [
    "contract.sol",
    `
abstract contract Ownable {
  address _owner;
  constructor() {
    _owner = msg.sender;
  }
  modifier onlyOwner() {
    require(_owner == msg.sender);
    _;
  }
  function checkOwner(address addr) internal returns (bool) {
    return _owner == addr;
  }
}

contract Counter is Ownable {
  uint _count;
  uint _unused;
  constructor(uint initialCount) {
    _count = initialCount;
  }
  function count() public view returns (uint) {
    return _count;
  }
  function increment(uint delta, uint multiplier) public onlyOwner returns (uint) {
    require(delta > 0, "Delta must be positive");
    _count += delta;
    return _count;
  }
  function unusedDecrement() private {
    require(checkOwner(msg.sender));
    _count -= 1;
  }
}
    `,
  ],
]);

test("find unused definitions", async () => {
  const unit = await buildCompilationUnit(CONTRACT_VFS, "0.8.0", "contract.sol");

  const unused = findUnusedDefinitions(unit, "Counter");
  const expected = unused.map((definition) => {
    const location = definition.nameLocation;
    assertUserFileLocation(location);
    const name = location.cursor.node.unparse();
    return [name, location.cursor.textOffset.line];
  });
  assert.deepEqual(expected, [
    ["checkOwner", 10],
    ["_unused", 17],
    ["multiplier", 24],
    ["unusedDecrement", 29],
  ]);
});