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

> Dive compares file trees between layers by stacking reference trees and annotating differences using cached TreeIndexKey system with DiffType flags for added, removed, or modified states.

- Repository: [Alex Goodman/dive](https://github.com/wagoodman/dive)
- Tags: internals
- Published: 2026-03-07

---

**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`](https://github.com/wagoodman/dive/blob/main/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`](https://github.com/wagoodman/dive/blob/main/dive/filetree/comparer.go):

```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`](https://github.com/wagoodman/dive/blob/main/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`](https://github.com/wagoodman/dive/blob/main/dive/filetree/comparer.go)):

```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`](https://github.com/wagoodman/dive/blob/main/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`](https://github.com/wagoodman/dive/blob/main/cmd/dive/cli/internal/ui/v1/viewmodel/filetree.go) requests annotated trees whenever the user navigates between layers:

```go
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`](https://github.com/wagoodman/dive/blob/main/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:

```go
// 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:

```go
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`](https://github.com/wagoodman/dive/blob/main/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`](https://github.com/wagoodman/dive/blob/main/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`](https://github.com/wagoodman/dive/blob/main/cmd/dive/cli/internal/ui/v1/viewmodel/filetree.go) consumes annotated trees, while [`cmd/dive/cli/internal/ui/v1/view/layer.go`](https://github.com/wagoodman/dive/blob/main/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`](https://github.com/wagoodman/dive/blob/main/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`](https://github.com/wagoodman/dive/blob/main/dive/filetree/comparer.go) (key generation and caching) and [`dive/filetree/file_tree.go`](https://github.com/wagoodman/dive/blob/main/dive/filetree/file_tree.go) (diff annotation via `CompareAndMark`). The reference data originates in [`dive/image/analysis.go`](https://github.com/wagoodman/dive/blob/main/dive/image/analysis.go), while UI consumption occurs in [`cmd/dive/cli/internal/ui/v1/viewmodel/filetree.go`](https://github.com/wagoodman/dive/blob/main/cmd/dive/cli/internal/ui/v1/viewmodel/filetree.go) with rendering support in [`cmd/dive/cli/internal/ui/v1/view/layer.go`](https://github.com/wagoodman/dive/blob/main/cmd/dive/cli/internal/ui/v1/view/layer.go).