Principle:MaterializeInc Materialize Image Dependency Resolution

Knowledge Sources	Build system theory, graph theory (topological sorting), container orchestration patterns
Domains	Build Systems, Dependency Management, Container Infrastructure, Graph Algorithms
Last Updated	2026-02-08

Overview

Dependency graph resolution for container images determines a correct, cycle-free build order by constructing and topologically sorting a directed acyclic graph (DAG) of image dependencies.

Description

In any build system where artifacts depend on other artifacts, the fundamental problem is determining which artifacts to build and in what order. When building Docker images, one image may reference another as a base layer or as a build dependency. These inter-image relationships form a directed acyclic graph (DAG), where each node is an image and each edge represents a "depends on" relationship.

Dependency graph resolution is the process of:

1. Discovery -- Walking the repository filesystem to identify all buildable images and their declared dependencies.
2. Validation -- Confirming that every referenced dependency actually exists in the repository (no dangling references).
3. Cycle detection -- Ensuring the dependency graph contains no cycles, which would make a valid build order impossible.
4. Topological sorting -- Producing a linear ordering of images such that every image appears after all of its dependencies.

The resulting topological order guarantees that when an image is built, all images it depends on have already been built and are available.

Usage

Use dependency graph resolution when:

• Building a set of container images that have inter-image dependencies (e.g., MZFROM directives referencing other mzbuild images).
• Determining the minimal set of images needed to satisfy a build request, including all transitive dependencies.
• Validating repository integrity at initialization time, ensuring no broken or circular dependency references exist.
• Planning parallel builds -- images at the same depth in the DAG can be built concurrently once their shared dependencies are satisfied.

Theoretical Basis

Directed Acyclic Graphs (DAGs)

A DAG is a directed graph with no directed cycles. In the context of build systems, the DAG property guarantees that a valid build order exists. If a cycle were present (A depends on B, B depends on C, C depends on A), no image could be built first, and the build would be impossible.

Topological Sort via Depth-First Search

The classical algorithm for topological sorting uses depth-first search (DFS) with a visiting set to detect cycles:

def topological_sort(graph):
    """Sort nodes in topological order using DFS.

    Args:
        graph: dict mapping node -> list of dependency nodes

    Returns:
        List of nodes in topological order (dependencies first).

    Raises:
        ValueError: If a cycle is detected.
    """
    resolved = OrderedDict()
    visiting = set()

    def visit(node, path=None):
        if path is None:
            path = []
        if node in resolved:
            return
        if node in visiting:
            cycle = " -> ".join(path + [node])
            raise ValueError(f"circular dependency: {cycle}")

        visiting.add(node)
        for dep in graph[node]:
            visit(dep, path + [node])
        resolved[node] = True

    for node in graph:
        visit(node)

    return list(resolved.keys())

Key properties:

• Time complexity: O(V + E) where V is the number of images and E is the number of dependency edges.
• Cycle detection: The visiting set tracks nodes currently on the DFS stack. Encountering a node already in this set means a back-edge exists, indicating a cycle.
• Path tracking: Maintaining the current DFS path allows producing a human-readable cycle diagram (e.g., A -> B -> C -> A) when a cycle is detected.

Build System Parallels

This pattern is fundamental to many build systems:

• Make uses a dependency DAG to determine build order.
• Bazel constructs an action graph that is a DAG of build steps.
• Nix models the entire package universe as a DAG of derivations.
• Docker multi-stage builds implicitly create a DAG of build stages.

The mzbuild system extends Docker's native capabilities by managing cross-image dependencies (not just intra-Dockerfile stages) through the MZFROM directive, which requires explicit graph resolution across the entire repository.

Related Pages

Implemented By

• Implementation:MaterializeInc_Materialize_Repository_Init