Implementation:Iterative Dvc Repo Trie

Knowledge Sources	Iterative_Dvc
Domains	Data_Structures, Pipeline_Management
Last Updated	2026-02-10 10:00 GMT

Overview

Repo_Trie provides a function for building a prefix tree (trie) data structure from DVC stage outputs. It is implemented in dvc/repo/trie.py (38 lines) and exposes a single public function build_outs_trie().

from dvc.repo.trie import build_outs_trie

The trie enables efficient path-based lookup and validation of DVC outputs across all pipeline stages, ensuring no duplicate or overlapping output paths exist.

Public Function

build_outs_trie()

Builds a pygtrie.Trie from all outputs of the given stages, validating that no duplicates or overlapping paths exist.

Signature:

def build_outs_trie(stages) -> Trie:

Parameters:

Parameter	Type	Default	Description
stages	iterable	required	An iterable of DVC Stage objects whose outputs will be indexed

Return value: A pygtrie.Trie instance where keys are filesystem path parts (tuples) and values are the corresponding output objects.

Exceptions:

• dvc.exceptions.OutputDuplicationError -- raised when two stages produce outputs at the exact same path
• dvc.exceptions.OverlappingOutputPathsError -- raised when one output path is a prefix of another (i.e., one tracked directory contains another tracked path)

Execution Flow

1. An empty Trie is created.
2. For each stage, each output's filesystem path is split into parts using out.fs.parts(out.fs_path) to form the trie key.
3. Duplicate check: If the exact key already exists in the trie, an OutputDuplicationError is raised, identifying both offending stages.
4. Overlap check: Two overlap conditions are tested:
   • Subtrie exists: If the new key has existing children in the trie (i.e., the new path is a parent directory of an existing output), the new path is the parent and the existing entry is the overlapping child.
   • Prefix exists: If the new key has an existing ancestor in the trie (i.e., the new path is inside an already-tracked directory), the existing entry is the parent and the new path is the overlapping child.
5. If either overlap condition is detected, an OverlappingOutputPathsError is raised.
6. If no conflicts exist, the output is inserted into the trie.

Validation Logic

# Check for duplicate outputs
if out_key in outs:
    dup_stages = [stage, outs[out_key].stage]
    raise OutputDuplicationError(str(out), set(dup_stages))

# Check for overlapping outputs
if outs.has_subtrie(out_key):
    parent = out
    overlapping = first(outs.values(prefix=out_key))
else:
    parent = outs.shortest_prefix(out_key).value
    overlapping = out
if parent and overlapping:
    raise OverlappingOutputPathsError(parent, overlapping, msg)

The overlap detection leverages the trie's structural properties:

• has_subtrie(key) checks if any keys exist that are prefixed by key.
• shortest_prefix(key).value retrieves the closest ancestor node with a value.

Key Design Decisions

• Trie data structure: Using a prefix tree allows O(k) path lookups (where k is the number of path components) and natural prefix/ancestor queries, which are essential for detecting overlapping outputs.
• Strict validation: Both exact duplicates and overlapping paths are treated as errors. This prevents scenarios where DVC would not know which stage owns a particular file, maintaining pipeline reproducibility.
• Path decomposition: Filesystem paths are decomposed into parts via out.fs.parts() rather than being stored as raw strings. This ensures correct prefix matching regardless of path separator conventions.

Dependencies

• pygtrie.Trie -- prefix tree implementation
• funcy.first -- retrieves the first element from an iterable
• dvc.exceptions.OutputDuplicationError -- error for duplicate outputs
• dvc.exceptions.OverlappingOutputPathsError -- error for overlapping output paths