4.1.5 depset vs list

depset is the Starlark data structure for rule data that grows through dependencies: transitive sources, headers, libraries, runfiles, flags, or metadata carried in providers. A list is still the right shape for small data local to one target, but it becomes expensive when every target republishes "my values plus everything below me." A depset is a nested graph with efficient merge operations, so a target can add direct values and point at child depsets instead of copying the whole transitive closure.¹

The Shape Difference

A list stores the flattened result immediately. If target B publishes ["b", "a"], then targets C and D that depend on B each copy B's entries into their own lists. In a small graph that is invisible. In a deep chain, the same values appear again and again. In overlapping top-level binaries or tests, several consumers may each copy a large shared dependency closure.²

A depset stores a node with direct elements and transitive child depsets. The constructor creates a new graph node whose children are existing depsets, so the merge is representation sharing, not list concatenation.³ This is why depset matches the mental model from 2.1 Directed Acyclic Graph (DAG): each rule contributes local facts, then passes a compact transitive view upward.

FilesInfo = provider(fields = {
    "transitive_files": "All files needed by downstream rules.",
})

def _impl(ctx):
    direct_files = ctx.files.srcs
    transitive_files = [
        dep[FilesInfo].transitive_files
        for dep in ctx.attr.deps
    ]

    return [FilesInfo(
        transitive_files = depset(
            direct = direct_files,
            transitive = transitive_files,
        ),
    )]

This is the standard provider pattern: publish bounded rule-local values as lists if useful, but publish graph-propagated values as depsets.⁴ A typical language-rule provider such as a GoLibraryInfo uses this shape: each library target returns its own metadata plus a depset of dependency metadata, and the linker-like consumer reads the transitive view when it needs the complete set.⁵ The provider mechanics themselves are expanded in 4.2.7 Custom Provider Declaration. Here the important part is the collection boundary.

Why Lists Go Quadratic

The performance failure is not that lists are slow in isolation. The failure is repeated flattening across the graph. In a dependency chain where each target copies all sources accumulated before it, total analysis work becomes effectively O(n²) for a chain of length n.⁶ Traversing or copying data accumulated from dependencies is the most common rule performance pitfall, and across a whole build it can easily become O(N²) in time or space.⁷

The "binary at the top" intuition is also incomplete. Flattening once for one requested terminal target may be acceptable, but a real invocation often builds many overlapping top-level targets, such as a test subtree or an IDE import. If each top-level target expands the same shared depsets into private lists or strings, the overlap recreates quadratic memory use at the boundary.⁸

This is why the safe default is: keep transitive data as a depset until the API that truly consumes it. If the consuming API accepts depsets, pass the depset directly. ctx.actions.run(inputs = ...) accepts a depset for transitive action inputs, and ctx.actions.args() can hold depsets so command-line expansion is deferred until action execution. That keeps analysis from materializing large intermediate lists.⁹ The full command-line design belongs in 4.2.3 Args & Command Lines.

Where list Still Belongs

Use a list for data that is local, small, and bounded by the current rule's attributes: this target's direct sources, direct dependency providers, a handful of mode strings, or validation choices. Local lists are fine when they are not publishing transitive dependency information.¹⁰

Use a depset when the field name would naturally start with transitive_, all_, or closure_: all headers below this target, all runtime files, all libraries for a linker, all metadata collected by an aspect. Those are graph-shaped facts. They should preserve sharing until the final consumer, not expand at every intermediate node.¹¹

Do not build a depset one element at a time in a loop. That creates deeply nested depsets and can perform poorly. Collect child depsets into a list, then call depset(transitive = children) once, or use a comprehension when the shape is simple.¹²

# Avoid: repeatedly wraps the previous depset.
files = depset()
for dep in ctx.attr.deps:
    files = depset(transitive = [files, dep[FilesInfo].transitive_files])

# Prefer: merge all transitive children in one constructor call.
files = depset(
    transitive = [
        dep[FilesInfo].transitive_files
        for dep in ctx.attr.deps
    ],
)

Flattening Is A Boundary

to_list() is not forbidden. It is a boundary marker. It copies the depset's contents into a list, suppressing duplicates according to the depset's traversal order.¹³ Once you call it, downstream code has lost the sharing property that made the depset cheap to propagate.

Good reasons to flatten are narrow: debugging, final validation that genuinely needs list operations, or an external API that only accepts a list and cannot be changed. When the API can consume a depset, prefer that. Action inputs, runfiles helpers, DefaultInfo.files, and Args.add_all() are common places where keeping the depset intact avoids unnecessary analysis memory.¹⁴

If you need membership tests, filtering, or set algebra inside one implementation function, a depset is usually the wrong local tool. Depsets are not general hash sets and do not support fast membership tests. Use the Starlark set type where available, or a dictionary-key pattern when compatibility requires it.¹⁵ That local collection choice is the boundary with 4.1.6 set (Bazel 8.1+).

Order Is Part Of The Contract

Depsets are not unordered bags. When you construct one, the order parameter controls how to_list() traverses the nested graph. Bazel documents default, postorder, preorder, and topological. default is deterministic but otherwise unspecified.¹⁶ Choose an order only when the consuming tool needs one, such as a linker command line where dependency ordering can matter.¹⁷

Orders also constrain merging. Two depsets can be merged when they have the same order, or when one uses default. Otherwise the orders are incompatible.¹⁸ Pick the order at the provider boundary and keep it consistent through the transitive field.

The mini-ruleset puts this pattern into practice: GlyphInfo declares transitive depset fields, and the manifest rollup composes them without flattening.