Command identity is a function of the parse traversal, not of the project

[typeless]

Summary

Command identity is the cross-build join key and the change detector. It is computed by hashing the fully rendered command text — compute_command_identity (src/graph/dag.cpp:1034) folds in expand_instruction(...) at dag.cpp:1041, whose %f is expanded from cmd->inputs.

cmd->inputs is not declared data. It is the result of glob resolution performed during the parse, and expand_glob_pattern (src/graph/builder.cpp:661) unions two halves:

1. the filesystem half — now fully deterministic after Order glob matches by path, not by interning order (fixes #171) #174, Merge filesystem and generated glob matches into one path-ordered list (fixes #177, fixes #178) #180, Return directory entries in name order (fixes #179) #181;
2. the graph half — for (auto id : nodes_of_type(ctx.state->graph, NodeType::Generated)) (builder.cpp:690), a scan of the partially built graph, whose membership is whatever the parse has produced so far.

So identity is a function of the parse traversal, not of the project.

Three facts make that concrete:

• Parse order comes from sort_dirs_by_depth (src/cli/context.cpp:686), which despite its name sorts by byte length of the directory path, descending (:699, :702), then lexicographically.
• The parse fixpoint (context.cpp:928) re-runs only while new Tupfile directories are discovered. It never re-runs because the Generated set grew, and there is no glob re-resolution pass.
• The mitigation added in Merge filesystem and generated glob matches into one path-ordered list (fixes #177, fixes #178) #180, request_demand_driven_parse(*ctx.eval, abs_pattern_dir_sv) (builder.cpp:685), force-parses the directory the pattern points at — not the directory that produces the match. That is right when a rule writes into its own directory and silent when a third directory writes into the pattern's directory.

Demonstrated: a permanent 0-byte artifact, exit 0

Root Tupfile.ini; b/ an empty directory; m/Tupfile = : ../b/*.q |> cat %f > %o |> out.txt; n/Tupfile = : |> echo x > %o |> ../b/gen.q. Out-of-tree (putup -B build):

build 1:  cat  > ../build/m/out.txt      <- %f empty; m parses before n, so b/gen.q is not in the graph yet
build 2:  (nothing runs)   exit 0
build 3:  (nothing runs)   exit 0
build 4:  (nothing runs)   exit 0

build/m/out.txt: 0 bytes, permanently

The rule names an input that a sibling directory generates, and putup ships an empty artifact and reports success forever. It never heals: the filesystem half searches the source tree, where the generated file never appears (it lands in build/b/gen.q), and the graph half already ran.

Rename the producing directory and the answer changes. Same project, n/ renamed to a/:

build 1:  cat ../build/b/gen.q > ../build/m/out.txt      out.txt: 2 bytes

Whether this project builds correctly depends on the name of a directory.

In-tree the same project self-heals on build 2 — the filesystem half then finds the generated file sitting next to the sources — at the cost of %f, and therefore identity, changing between build 1 and build 2 of an unchanged project.

Why the recent work does not close this

#171/#174, #180 and #181 purified the order of glob matches, and #180 additionally fixed membership shadowing between the two halves. This is membership as a function of traversal, which none of them touch. #180's description claimed to have removed the fixpoint dependence; that claim has been corrected on the PR.

Analysis: identity does two jobs that want opposite things

find_by_identity (src/cli/cmd_build.cpp:929) serves preserve_old_implicit_edges (:835), merge_out_of_scope_commands (:986), reconcile_input_set (:1406) and remove_stale_outputs (:1517) — a join key, which wants maximal stability. detect_new_commands (:1346) reruns a command whose identity is absent from the old index — a change detector, which wants maximal sensitivity. Conflating them means every source of churn is simultaneously a spurious rebuild and a lost join.

The index version history is the receipt: v11, v15, v16 and v17 all exist because the identity function's input changed.

Options

D — enforce injectivity first (cheap, do this regardless). build_identity_map (cmd_build.cpp:915) appends without a uniqueness check and its comparator ignores the NodeId, so equal-hash order is unspecified; find_by_identity is a lower_bound returning an arbitrary twin. An std::adjacent_find after the sort turns a silent mis-join into a diagnosable error. This is #170, and it is a few lines.

A — resolve globs after the parse fixpoint. Parse rules with patterns unresolved, then resolve every pattern once against the completed graph plus filesystem, then compute identity. Makes the input set a function of project state by construction, which is how tup gets it: tup resolves globs out of its node table rather than mid-parse. Cost: a resolution pass and identity computation move after parsing; rule-time constructs that consume %f during evaluation need care.

Not recommended — excluding foreign-generated matches by rule. Reviewed and rejected: it would leave the demonstrated case rendering empty on every build rather than fixing it, it regresses cases that work today (a producer that sorts first resolves correctly out-of-tree right now), and it breaks putup's own build graph, where test/runner/Tupfile names ../unit/putup_test$(_exe) and ../../putup$(_exe) — foreign-generated files named explicitly across directories.

Not recommended as stated — keying identity on the output set. Not well-defined here: src/graph/builder.cpp deliberately permits two commands with mutually exclusive guards to declare the same output, so the output set is not unique.

Scope

This issue is the mechanism. #170 is the injectivity half and stays open as its own issue; option D above is its fix.

Not covered here: anything about how the index records state across builds — that is a separate root cause, filed separately.

Provenance

Mechanism and citations verified against merged main. The demonstrations above were run directly. One further claim from the research pass — that an identity collision causes remove_stale_outputs to skip a deletion permanently — did not reproduce when I tried it (the surviving twin recreates the file, so the observation is confounded); it is deliberately not asserted here.

🤖 Generated with Claude Code

https://claude.ai/code/session_01TLob4Ef3qyMd3Dnp9q3XmA

[typeless]

Reopening: I closed this prematurely. PR #190 (fixes #188) split command identity into a join key and a signature, which addresses the "identity does two jobs that want opposite things" analysis in this issue — but that was a subsection, not the headline. The headline mechanism is untouched: expand_glob_pattern (src/graph/builder.cpp:690) still resolves the generated half of a glob against the partially-built graph during the parse, so membership remains a function of the traversal.

The demonstrated failure in the issue body reproduces bit-for-bit on current main (a47fe41f5):

m/Tupfile: : ../b/*.q |> echo %f > %o |> out.txt
n/Tupfile: : |> echo x > %o |> ../b/gen.q

putup configure -B build && putup -B build
  build 1: Build completed: 2 commands     out.txt: 1 byte (empty %f)
  build 2: Nothing to do (up to date).     out.txt: 1 byte
  build 3: Nothing to do (up to date).     out.txt: 1 byte

Permanently empty artifact, exit 0.

The split did change one thing here, and not for the better as a diagnostic: with the signature now stable across identically-traversed builds, the empty render is stable rather than churning between builds. The symptom got quieter, not absent.

Option A in the issue body — resolve globs after the parse fixpoint — remains the fix, and no cheaper correct one has been identified. What #190 legitimately closed is the dual-role problem; that part should not be reopened.

Found by an adversarial review of the merged PRs in this campaign.