Dependency Trees

Table of Contents

• Dependency Trees
• Table of Contents
• What is a Dependency Tree?
• Initialisation
• Parsing
• Identify Dependencies
• Resolve Dependency Paths
• Recursive Traversal
• What is this used for?
• Example

What is a Dependency Tree?

• It's a Directed Acyclic Graph (DAG) where nodes represent modules (files) and edges represent dependencies between these modules.
• We can represent a DAG in code using an adjacency list, which is a collection of lists or sets. Each node has a list of nodes it depends on.

{
    "index.js": ['library3000.js'],
    "library3000.js": ['date.js', 'time.js'],
    "date.js": [],
    "time.js": []
}

Initialisation

• The process of finding dependencies will start from the page/file that is loaded initially.
• This is typically an index file. (index.js)

const entryFilePath = path.resolve(__dirname, 'index.js');

Parsing

• The entry file is read and parsed to identify all the import or require statements.
• Parsing involves converting the code into an Abstract Syntax Tree (AST), which we won't go over as Khai and Myself have spoken about this.
• We will do this part in the example with the help of a JS parser Acorn.

// Read the file
const content = fs.readFileSync(entryFilePath, 'utf-8');
// Parse the file
const ast = acorn.parse(content, { sourceType: 'module' });

Identify Dependencies

• Now we have our AST, we need go searching through it!
• We simply want to search for imports and require statements.
• Import statements are called ImportDeclaration in the AST.
• require statements are CallExpressions, so we need to do some additional checks to make sure it is a dependency.
• You can see the AST here

1 const dependencies = [];
2 walk.simple(ast, {
3   ImportDeclaration(node) {
4     dependencies.push(node.source.value);
5   },
6   CallExpression(node) {
7     if (node.callee.name === 'require' && node.arguments.length === 1) {
8       const argument = node.arguments[0];
9       if (argument.type === 'Literal') {
10         dependencies.push(argument.value);
11       }
12     }
13   }
14 });

Resolve Dependency Paths

• We want to convert relative paths to absolute paths to ensure consistency and avoid path conflicts.

const resolvePath = (basePath, relativePath) =>
    path.resolve(path.dirname(basePath), relativePath);

Recursive Traversal

For each identified dependency, add nodes (modules) and edges (dependencies) to the graph. Apply this same dependency extraction process to each dependency until all modules are processed.

1 function buildDependencyTree(entryFilePath) {
2   const graph = new Graph();
3   const stack = [entryFilePath];
4   const visited = new Set();
5   const pathStack = [];
6
7   while (stack.length > 0) {
8     const currentFilePath = stack.pop();
9     if (visited.has(currentFilePath)) continue;
10
11     if (pathStack.includes(currentFilePath)) {
12       console.warn(
13         `Cyclic dependency detected: ${pathStack.join(
14           " -> "
15         )} -> ${currentFilePath}`
16       );
17       continue;
18     }
19
20     visited.add(currentFilePath);
21     pathStack.push(currentFilePath);
22     graph.addNode(currentFilePath);
23
24     const dependencies = getDependencies(currentFilePath);
25     for (const dep of dependencies) {
26       const depFilePath = resolvePath(currentFilePath, dep);
27       graph.addNode(depFilePath);
28       graph.addEdge(currentFilePath, depFilePath);
29       stack.push(depFilePath);
30     }
31
32     pathStack.pop();
33   }
34
35   return graph;
36 }

What is this used for?

Now we have a structured representation of how modules depend on each other. This enables the bundler to correctly order and include modules, and optimise code.

Example

    const fs = require("fs");
    const path = require("path");
    const acorn = require("acorn");
    const walk = require("acorn-walk");

    class Graph {
    constructor() {
        this.nodes = new Map();
    }

    addNode(node) {
        if (!this.nodes.has(node)) {
        this.nodes.set(node, []);
        }
    }

    addEdge(fromNode, toNode) {
        if (!this.nodes.has(fromNode)) {
        this.addNode(fromNode);
        }
        if (!this.nodes.has(toNode)) {
        this.addNode(toNode);
        }
        this.nodes.get(fromNode).push(toNode);
    }

    printGraph() {
        for (let [node, dependencies] of this.nodes) {
        console.log(`${node} -> ${dependencies.join(", ")}`);
        }
        console.log("\n", this.nodes);
    }
    }

    function getDependencies(filePath) {
    const content = fs.readFileSync(filePath, "utf-8");
    const ast = acorn.parse(content, { sourceType: "module", ecmaVersion: 2020 });

    const dependencies = [];
    walk.simple(ast, {
        ImportDeclaration(node) {
        dependencies.push(node.source.value);
        },
        CallExpression(node) {
        if (node.callee.name === "require" && node.arguments.length === 1) {
            const argument = node.arguments[0];
            if (argument.type === "Literal") {
            dependencies.push(argument.value);
            }
        }
        },
    });

    return dependencies;
    }

    function resolvePath(basePath, relativePath) {
    const possibleExtensions = [".js"]; // Add other extensions if necessary
    for (const ext of possibleExtensions) {
        const fullPath = path.resolve(
        path.dirname(basePath),
        `${relativePath}${ext}`
        );
        if (fs.existsSync(fullPath)) {
        return fullPath;
        }
    }
    throw new Error(`Cannot resolve module: ${relativePath}`);
    }

    function buildDependencyTree(entryFilePath) {
    const graph = new Graph();
    const stack = [entryFilePath];
    const visited = new Set();
    const pathStack = [];

    while (stack.length > 0) {
        const currentFilePath = stack.pop();
        if (visited.has(currentFilePath)) continue;

        if (pathStack.includes(currentFilePath)) {
        console.warn(
            `Cyclic dependency detected: ${pathStack.join(
            " -> "
            )} -> ${currentFilePath}`
        );
        continue;
        }

        visited.add(currentFilePath);
        pathStack.push(currentFilePath);
        graph.addNode(currentFilePath);

        const dependencies = getDependencies(currentFilePath);
        for (const dep of dependencies) {
        const depFilePath = resolvePath(currentFilePath, dep);
        graph.addNode(depFilePath);
        graph.addEdge(currentFilePath, depFilePath);
        stack.push(depFilePath);
        }

        pathStack.pop();
    }

    return graph;
    }

    // Example usage
    const entryFilePath = path.resolve(__dirname, "index.js");
    const dependencyGraph = buildDependencyTree(entryFilePath);
    dependencyGraph.printGraph();

Return