How Dive Compares File Trees Between Layers: Stacked Diff Analysis in Go

Dive compares file trees between image layers by stacking ranges of reference trees into a composite base and annotating differences against upper layers using a cached TreeIndexKey system that marks each node with DiffType flags for added, removed, or modified states.

Dive is an open-source tool for exploring Docker and OCI image layers built by wagoodman/dive. To show exactly what changes between builds, the tool must efficiently compare file trees between layers. According to the source code, this file tree comparison relies on a sophisticated stacking and caching mechanism that processes layer ranges rather than computing individual diffs repeatedly.

Reference Trees and Layer Indexing

During image analysis, the system in dive/image/analysis.go converts each layer into a *filetree.FileTree and stores the complete slice in Analysis.RefTrees. These reference trees serve as the immutable baseline for all comparison operations.

The comparison engine does not mutate these reference trees. Instead, it creates new stacked trees by combining ranges from this slice, ensuring the original layer data remains intact for reuse across different view modes.

TreeIndexKey and Comparison Modes

The core abstraction for defining which layers to compare is TreeIndexKey, defined in dive/filetree/comparer.go:

type TreeIndexKey struct {
    bottomTreeStart, bottomTreeStop int // inclusive indexes of the bottom stack
    topTreeStart, topTreeStop       int // inclusive indexes of the top stack
}

Dive supports two distinct comparison modes that utilize this structure:

• Natural comparison: Fixes the top stack to a single layer while the bottom stack accumulates all lower layers. This shows exactly what changed in one specific layer.
• Aggregated comparison: Fixes the bottom stack to layer 0 (the base image) and expands the top stack to include all changes up to a target layer.

The generators Comparer.NaturalIndexes() and Comparer.AggregatedIndexes() (lines 85-118 of comparer.go) produce these keys dynamically based on the total layer count.

The Stacking and Caching Engine

The Comparer struct maintains an internal cache (trees map[TreeIndexKey]*FileTree) to avoid recomputing expensive tree operations during UI navigation. When GetTree(key) is invoked, it either returns a cached result or builds a new composite tree via StackTreeRange.

The stacking process follows this sequence:

1. Build the base: Combine reference trees from bottomTreeStart to bottomTreeStop into a single stacked tree.
2. Annotate differences: Walk through layers from topTreeStart to topTreeStop, calling CompareAndMark against the base tree.
3. Cache the result: Store the fully annotated tree for subsequent UI requests.

This implementation appears in Comparer.get (lines 70-82 of dive/filetree/comparer.go):

newTree, err := StackTreeRange(cmp.refTrees, key.bottomTreeStart, key.bottomTreeStop)
for idx := key.topTreeStart; idx <= key.topTreeStop; idx++ {
    newTree.CompareAndMark(cmp.refTrees[idx])
}

Annotating Differences with CompareAndMark

The core diff logic resides in FileTree.CompareAndMark(upper), implemented in dive/filetree/file_tree.go (lines 300-365). This method performs a leaf-first walk of the upper tree to determine file states:

• Whiteouts: Detects deletion markers (.wh.* files) and calls markRemoved to flag the node as deleted.
• Additions: Flags nodes that exist in the upper tree but not the lower as added.
• Modifications: Uses lowerNode.compare(upperNode) to determine if a file is modified or unmodified based on size, permissions, or hash.

After processing leaves, deriveDiffType propagates diff statuses up to parent directories. Finally, the upper payload writes into the lower node, completing the annotation with a tentative DiffType resolved to final states.

Consuming Compared Trees in the UI

The view model in cmd/dive/cli/internal/ui/v1/viewmodel/filetree.go requests annotated trees whenever the user navigates between layers:

newTree, err := vm.comparer.GetTree(
    filetree.NewTreeIndexKey(bottomTreeStart, bottomTreeStop,
                            topTreeStart, topTreeStop))

The returned FileTree contains FileNode.Data.DiffType values that enable color-coding in the terminal interface. The renderCompareBar function in cmd/dive/cli/internal/ui/v1/view/layer.go uses these annotations to render the comparison bar and toggle between single-layer and aggregated views.

Practical Code Examples

To programmatically compare layer ranges using the Dive engine:

// Build a comparer for all layer trees
cmp := filetree.NewComparer(analysis.RefTrees)

// Single-layer view: compare layer 3 against layers 0-2
key := filetree.NewTreeIndexKey(0, 2, 3, 3)
tree, err := cmp.GetTree(key) // tree nodes now have DiffType flags

// Aggregated view: compare cumulative state up to layer 4 against base layer 0
keyAgg := filetree.NewTreeIndexKey(0, 0, 1, 4)
aggTree, _ := cmp.GetTree(keyAgg)

For UI integration, update the view model when the cursor changes:

func (vm *FileTreeViewModel) SetTreeByLayer(bottomStart, bottomStop, topStart, topStop int) error {
    newTree, err := vm.comparer.GetTree(
        filetree.NewTreeIndexKey(bottomStart, bottomStop, topStart, topStop))
    if err != nil { return err }
    vm.ModelTree = newTree
    return nil
}

Summary

• Reference Trees: Dive stores per-layer file trees in Analysis.RefTrees during initial image analysis in dive/image/analysis.go.
• TreeIndexKey: Defines inclusive ranges for bottom (base) and top (change) layer stacks, supporting both natural and aggregated comparison modes via Comparer.
• Caching Strategy: The Comparer caches computed trees by TreeIndexKey to optimize UI navigation performance and avoid redundant stacking operations.
• Diff Annotation: CompareAndMark walks upper layers leaf-first in dive/filetree/file_tree.go, handling whiteouts and propagating DiffType flags (added, removed, modified) to enable terminal color-coding.
• UI Integration: cmd/dive/cli/internal/ui/v1/viewmodel/filetree.go consumes annotated trees, while cmd/dive/cli/internal/ui/v1/view/layer.go renders the comparison indicators.

Frequently Asked Questions

What is the difference between natural and aggregated comparison in Dive?

Natural comparison shows changes introduced by a single specific layer by fixing the top stack to one layer and accumulating all lower layers in the bottom stack. Aggregated comparison shows cumulative changes up to a specific layer by fixing the bottom stack to the base image (layer 0) and expanding the top stack through the target layer. Both modes use the same TreeIndexKey structure but different index generators in Comparer.

How does Dive handle deleted files when comparing layers?

Dive detects whiteout files (special markers indicating deletion in layer tarballs) during the CompareAndMark leaf-first walk in dive/filetree/file_tree.go. When encountered, the method calls markRemoved to annotate the node as deleted. This logic resides alongside handling for added and modified files, ensuring accurate representation of layer deletions in the UI.

Why does Dive cache file tree comparisons?

The Comparer maintains a map[TreeIndexKey]*FileTree cache to avoid recomputing expensive stack and diff operations when users navigate between layers in the TUI. Since tree comparison involves walking filesystem nodes, resolving diff types, and handling whiteouts, caching ensures responsive layer switching even for images with many layers or large file trees.

Which source files contain the core comparison logic?

The primary comparison logic lives in dive/filetree/comparer.go (key generation and caching) and dive/filetree/file_tree.go (diff annotation via CompareAndMark). The reference data originates in dive/image/analysis.go, while UI consumption occurs in cmd/dive/cli/internal/ui/v1/viewmodel/filetree.go with rendering support in cmd/dive/cli/internal/ui/v1/view/layer.go.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}