Build Systems & Monorepos - Graphs, Caching, Hermeticity & Reproducible Environments

"""A build system is a function from inputs to outputs over a graph.

This toy engine checks the four properties the hub page talks about:
  1. correctness   - every output equals what a clean rebuild would produce
  2. incrementality - only tasks whose inputs changed are re-run
  3. caching        - results are looked up by a hash of declared inputs
  4. hermeticity    - a task may only read what it declared
Everything is in memory so it runs anywhere with plain Python 3.
"""
import hashlib, json

def h(obj) -> str:
    """Stable short hash of any JSON-serialisable value."""
    return hashlib.sha256(json.dumps(obj, sort_keys=True).encode()).hexdigest()[:10]

# Source files: the "inputs" of the whole function.
src = {"util.c": "int add(int a,int b){return a+b;}",
       "main.c": "int main(){return add(1,2);}"}

# Each task declares its inputs and a pure function that computes its output.
tasks = {
    "util.o": (["util.c"], lambda r: "obj(" + r("util.c") + ")"),
    "main.o": (["main.c"], lambda r: "obj(" + r("main.c") + ")"),
    "app":    (["util.o", "main.o"], lambda r: "link(" + r("util.o") + "+" + r("main.o") + ")"),
}

cache = {}   # cache key -> output (a content-addressed action cache)
runs = []    # which tasks actually executed in the current build

def build(target, store, env, hermetic=True):
    """Build target, returning its value; store holds sources and built outputs."""
    if target in src:
        return store[target]
    deps, fn = tasks[target]
    dep_vals = [build(d, store, env, hermetic) for d in deps]
    key = h([target, deps, dep_vals])          # declared inputs only
    if key in cache:                           # property 3: caching
        store[target] = cache[key]
        return store[target]
    def read(name):
        # property 4: hermeticity - reading an undeclared name is an error
        if hermetic and name not in deps:
            raise PermissionError(f"{target} read undeclared input {name}")
        return store[name] if name in store else env[name]
    runs.append(target)                        # property 2: incrementality
    store[target] = cache[key] = fn(read)
    return store[target]

def clean_rebuild(target):
    """Reference answer: rebuild from scratch with no cache."""
    store = dict(src)
    def go(t):
        if t in src: return store[t]
        deps, fn = tasks[t]
        for d in deps: go(d)
        store[t] = fn(lambda n: store[n]); return store[t]
    return go(target)

store = dict(src)
build("app", store, env={})
print("build 1 ran:", runs)

runs.clear(); build("app", store, env={})
print("build 2 (no change) ran:", runs)

src["main.c"] = "int main(){return add(2,3);}"   # edit one file
store["main.c"] = src["main.c"]
runs.clear(); build("app", store, env={})
print("build 3 (main.c edited) ran:", runs)
print("property 1, correct vs clean rebuild:", store["app"] == clean_rebuild("app"))

# A task that sneaks a look at the environment breaks hermeticity.
tasks["main.o"] = (["main.c"], lambda r: "obj(" + r("main.c") + r("CFLAGS") + ")")
cache.clear(); store = dict(src)
try:
    build("app", store, env={"CFLAGS": "-O2"})
except PermissionError as e:
    print("hermetic engine refused:", e)

build 1 ran: ['util.o', 'main.o', 'app']
build 2 (no change) ran: []
build 3 (main.c edited) ran: ['main.o', 'app']
property 1, correct vs clean rebuild: True
hermetic engine refused: main.o read undeclared input CFLAGS

// Same edit, three granularities: what gets re-run?
// - task runner, no cache: reruns every task (the Make-less npm scripts world)
// - package-level graph (Turborepo / Nx style): reruns the changed package and its dependents
// - target/file-level graph (Bazel / Buck2 / Pants style): reruns only targets whose inputs changed
// Repo: app -> ui -> utils, app -> api-client -> utils. Each package has a few source files.

type Pkg = { name: string; deps: string[]; files: string[] };

const pkgs: Pkg[] = [
  { name: "utils", deps: [], files: ["utils/date.ts", "utils/money.ts", "utils/strings.ts"] },
  { name: "ui", deps: ["utils"], files: ["ui/button.tsx", "ui/table.tsx"] },
  { name: "api-client", deps: ["utils"], files: ["api-client/http.ts", "api-client/orders.ts"] },
  { name: "app", deps: ["ui", "api-client"], files: ["app/page.tsx", "app/checkout.tsx"] },
];

// Fine-grained targets: which source files actually import which.
// Only orders.ts and checkout.tsx use utils/money.ts.
const fileDeps: Record<string, string[]> = {
  "api-client/orders.ts": ["utils/money.ts", "api-client/http.ts"],
  "app/checkout.tsx": ["api-client/orders.ts", "utils/money.ts"],
  "ui/table.tsx": ["utils/strings.ts"],
  "app/page.tsx": ["ui/button.tsx", "ui/table.tsx"],
};

const tasksPerPkg = ["build", "test", "lint"];

function closure(seed: string[], edges: Record<string, string[]>): Set<string> {
  // Reverse-dependency closure: everything that (transitively) depends on a seed.
  const out = new Set<string>(seed);
  let grew = true;
  while (grew) {
    grew = false;
    for (const [node, ds] of Object.entries(edges)) {
      if (!out.has(node) && ds.some((d) => out.has(d))) { out.add(node); grew = true; }
    }
  }
  return out;
}

const pkgEdges = Object.fromEntries(pkgs.map((p) => [p.name, p.deps]));

for (const changed of ["utils/money.ts", "app/page.tsx"]) {
  const owner = pkgs.find((p) => p.files.includes(changed))!.name;
  const affected = closure([owner], pkgEdges);   // package granularity
  const dirty = closure([changed], fileDeps);     // file/target granularity
  console.log(`edit: ${changed}`);
  console.log(`  task runner, no graph or cache: ${pkgs.length * tasksPerPkg.length} tasks`);
  console.log(`  package graph: ${[...affected].join(", ")} -> ${affected.size * tasksPerPkg.length} tasks`);
  console.log(`  file/target graph: ${[...dirty].join(", ")} -> ${dirty.size} compile units`);
}
console.log("trade-off: finer graphs rerun less but need every dependency declared (or inferred) precisely");

edit: utils/money.ts
  task runner, no graph or cache: 12 tasks
  package graph: utils, ui, api-client, app -> 12 tasks
  file/target graph: utils/money.ts, api-client/orders.ts, app/checkout.tsx -> 3 compile units
edit: app/page.tsx
  task runner, no graph or cache: 12 tasks
  package graph: app -> 3 tasks
  file/target graph: app/page.tsx -> 1 compile units
trade-off: finer graphs rerun less but need every dependency declared (or inferred) precisely