Repository navigation
Detect cross-VCS cycles and duplicate source identities before materialization #489
Description
Goal
Add one canonical graph-admission pass that detects source cycles, duplicate canonical repositories, duplicate package identities, and conflicting destination ownership across Zed packages, Git submodules, Mercurial subrepos, and Jujutsu-backed sources before filesystem or lock mutation.
Coordinates:
zed-pkg/zed-interfaces#154— canonical VCS source identity;zed-pkg/zed-lib-core#76/#77— stitch planning + path ownership;zed-pkg/zed-cli#177/#484/#485/#488— backend-specific topology.
Identity normalization
Normalize each dependency/source into a canonical graph node keyed by authority-relevant identity. This must distinguish:
- package identity/version requirements;
- canonical repository identity;
- immutable source revision;
- materialization destination.
Repository URL spelling aliases that refer to the same admitted source should not evade duplicate detection, but unrelated repositories must never be guessed/merged from name similarity.
Required refusals
Detect and fail before mutation for at least:
- Git A -> Hg B -> Git A cycle;
- Hg A -> Git B -> Hg A cycle;
- JJ/Git colocated source re-entering itself through a package edge;
- same package represented simultaneously as Zed package + adopted VCS source without an explicit migration/override rule;
- same canonical repo/revision materialized to two conflicting authority roots;
- two different sources targeting the same path;
- one destination nested under another mutable VCS worktree in a way that violates ownership rules;
- source alias spellings that normalize to the same canonical identity;
- case-normalization/path-equivalence conflicts on Windows/macOS filesystems.
Diagnostics
Return a deterministic, bounded explanation containing the shortest discovered cycle/conflict path where practical, source kinds, package/source ids, and destination paths. Never print credentials or raw signed URLs.
Algorithm / resource bounds
- graph construction/order must be deterministic;
- cycle detection O(V+E) or equivalently bounded;
- cap graph node/edge counts using existing dependency graph limits or an explicit new bound;
- pathological nested VCS metadata must not cause recursion/stack exhaustion;
- duplicate/conflict detection happens before network fetch where identity is already knowable and again after canonical source resolution if aliases become clear only then.
Tests
- acyclic Zed-only, Git-only, Hg-only, JJ-only graphs;
- each cross-backend cycle combination;
- diamond dependency without false cycle;
- exact same immutable source reused read-only where policy permits;
- duplicate package + VCS representation refusal;
- destination collision;
- path case/canonicalization collision;
- graph size/depth bound;
- deterministic error ordering across repeated runs.
Keep the reusable graph logic in or move it toward zed-lib-core as #76 matures; CLI owns UX, not a second graph algorithm.
Activity
ORESoftware commentedon Oct 26, 2026
Current-main reconciliation — 2026-10-25
Fresh state:
zed-pkg/zed-climain:388161f681bac8ae704a22a593280ceed6cc4fa9(merge feat(graph): resolve full dependency graph directly from .zpkg.toml #530,feat(graph): resolve full dependency graph directly from .zpkg.toml).86d499aff19807cee3500777ee4a9e48ea646821, recorded base5d0cbc0609703e7516e2185ea3c1749c9feda482, open/non-draft,mergeable=false, no submitted reviews.src/versioned_graph.rsordocs/versioned-circular-dependencies.md;src/graph_export.rsalso lacks the materialization integration. Thus the cycle/diamond intent is not superseded by feat(graph): resolve full dependency graph directly from .zpkg.toml #530's manifest graph resolver.Disposition: AUDIT_ONLY-BLOCKED; do not merge #315 as-is. Its semantics remain useful, but
graph_export.rshas since evolved through #530. Next gate is a semantic current-main port of the exact-node graph/materialization module, tests, docs and focused workflow onto a fresh branch, preserving #530's manifest resolver and ordinary one-version lock semantics. Then run exact-head CI and the dedicated graph workflow with executed steps and independent review. No package mass-bumps or automatic solver fallback are justified by this gap.Observed #315 workflow state: #34060370962 CLI portability: failure; #34060371003 zed-pkg-test candidate smoke: success; #34060371007 agents policy: success; #34060371192 Pre-build source policy lint: success; #34060370499 nix-export-plan: success; #34060370683 repository hardening: success; #34060370479 native task runtime: failure; #34060370579 blocking store process locks: success; #34060370590 nix-export-bundle: success; #34060370457 Global executable package profiles: failure; #34060370540 release plan browser report: success; #34060370467 ci: success; #34060370567 current mise lock contract: failure; #34060370445 Formal review procedure: success; #34060370454 manifestless polyglot installs: success; #34060370487 Zed package graph: success; #34060370532 frozen lock integrity: success; #34060370621 versioned circular dependencies: success; #34060370558 nix-export-persist: success; #34060370598 R2 Android binary live certification: success; #34060370617 recursive install windows locking: success; #34060370502 asdf environment interop: failure; #34060370501 Nested and self dependency install modes: success; #34060370495 Devbox and Flox environment export: failure; #34060370610 standalone locked install: success; #34060370466 nix-fetch-bundle: success; #34060370553 develop-shell: success; #34060370541 nix-interop: success; #34060370653 copy-mode OCI contract: success; #34060370624 frozen-fetch: success; #34060370588 durable first-install manifests: success; #34060370703 nix-bundle-write: success; #34060370591 polyglot: success; #34060370671 R2 binary registry e2e: success; #34060370652 frozen offline tool profiles: failure; #34060370514 zed tip dependency canary: success.