Transitive Dependency Resolution¶

See also: dependency-linkage.md for how each fetched dep is integrated into your build product (shared-external vs static-embedded vs static-external).

Overview¶

CCGO now supports automatic transitive dependency resolution. When you run ccgo install, it automatically discovers and installs dependencies of your dependencies, determines the correct build order, and detects circular dependencies.

Resolution priority¶

For each [[dependencies]] entry, ccgo fetch decides where the bytes come from by walking these source kinds in order. The first one that matches the dep's declared fields wins:

path = "..." — local path dependency. Symlinked or copied from the relative/absolute path in the consumer's tree.
git = "..." (with branch / tag / rev) — Git dependency. Cloned shallowly into ~/.ccgo/git/<repo>/.
zip = "..." — archive dependency. Downloaded (https://) or read (file://, local path) and extracted into .ccgo/deps/<name>/.
Registry resolution — when [registries] is non-empty AND the dep has no path/git/zip source. ccgo walks declared registries (or just the one named by [[dependencies]].registry) in TOML declaration order, takes the first non-yanked exact-version match, then chooses one of two sub-paths:
Archive — when the matched VersionEntry.archive_url is set: download those bytes, SHA-256-verify, extract.
Git+tag fallback — when archive_url is absent but PackageEntry.repository is set (which ccgo publish index always populates from the project's git remote): git clone --branch <tag> the source repo. The lockfile records source = "registry+<index-url>" and locked.git.revision for deterministic re-fetch.

See features/registry.md for the index schema and the [registries] configuration syntax. 5. Version-only local cache fallback — when nothing above resolves AND the dep has a non-empty version. ccgo looks under ~/.ccgo/packages/<name>/<version>/ (the cache populated by ccgo install in the source project) and copies that into .ccgo/deps/<name>/. This mirrors the Cargo / Maven workflow where the dep is identified by name+version and the location lives entirely in a developer-machine cache.

When step 4 returns "no match" it falls through cleanly to step 5 — existing version-only deps that don't appear in any configured registry keep working unchanged. When [registries] is empty, step 4 is skipped entirely. This is what makes the registry tier opt-in and incremental: older git/zip declarations stay valid forever.

Features¶

1. Transitive Dependency Discovery¶

When installing a dependency that has its own CCGO.toml file with dependencies, CCGO will: - Automatically read the dependency's CCGO.toml - Discover its dependencies (transitive dependencies) - Recursively resolve all dependencies in the entire dependency tree - Handle both git and path dependencies

2. Dependency Graph Visualization¶

CCGO displays a visual tree of your dependencies showing: - Direct dependencies (declared in your CCGO.toml) - Transitive dependencies (dependencies of dependencies) - Shared dependencies (used by multiple packages) - Source information (git URL, path, version)

Example output:

Dependency tree:
mylib v1.0.0
├── fmt v9.1.0 (git: https://github.com/fmtlib/fmt)
│   └── gtest v1.12.0 (git: https://github.com/google/googletest)
└── json v3.11.2 (git: https://github.com/nlohmann/json)

3 unique dependencies found, 4 total (1 shared)

3. Topological Sorting for Build Order¶

CCGO uses topological sorting to determine the correct installation order: - Dependencies with no dependencies are installed first - Dependencies are installed before their dependents - Ensures builds succeed by respecting dependency chains

Example:

📦 Installing in dependency order:
  1. gtest
  2. fmt
  3. mylib

4. Circular Dependency Detection¶

CCGO detects circular dependencies and reports them with the full cycle path:

Error: Circular dependency detected: libA -> libB -> libC -> libA

5. Version Conflict Warnings¶

When multiple packages depend on different versions of the same dependency, CCGO: - Warns about version conflicts - Uses the first version encountered (for now) - Displays clear warnings to help resolve conflicts

Example:

⚠️  Version conflict for 'fmt': have 9.1.0, need 10.0.0

6. Max Depth Protection¶

To prevent infinite recursion, CCGO limits dependency depth to 50 levels and reports an error if exceeded.

Implementation¶

Architecture¶

The dependency resolution system consists of three main components:

1. Dependency Graph (`src/dependency/graph.rs`)¶

DependencyNode: Represents a single dependency with metadata
DependencyGraph: Manages the entire dependency graph
Cycle Detection: DFS-based algorithm to find circular dependencies
Topological Sort: Kahn's algorithm for build order
Tree Formatting: Pretty-print dependency tree
Statistics: Calculate unique, shared, and total dependencies

2. Dependency Resolver (`src/dependency/resolver.rs`)¶

DependencyResolver: Main resolver that orchestrates dependency resolution
Recursive Resolution: Traverses dependency tree recursively
Path Resolution: Handles relative paths in transitive dependencies
Caching: Visited set prevents duplicate processing
Error Handling: Graceful degradation on resolution failures

3. Install Command Integration (`src/commands/install.rs`)¶

Calls resolver to build dependency graph
Displays dependency tree and statistics
Uses topological sort for installation order
Falls back to direct dependencies on errors
Installs dependencies in correct order

Data Structures¶

pub struct DependencyNode {
    pub name: String,
    pub version: String,
    pub source: String,              // git+url or path+path
    pub dependencies: Vec<String>,   // Direct dependencies
    pub depth: usize,                // Depth in dependency tree
    pub config: DependencyConfig,    // Original config
}

pub struct DependencyGraph {
    nodes: HashMap<String, DependencyNode>,
    edges: Vec<(String, String)>,    // (from, to) edges
    roots: HashSet<String>,          // Root dependencies
}

Key Algorithms¶

Cycle Detection (DFS)¶

pub fn detect_cycles(&self) -> Option<Vec<String>>

Uses depth-first search with a recursion stack to detect cycles. Returns the cycle path if found.

Topological Sort (Kahn's Algorithm)¶

pub fn topological_sort(&self) -> Result<Vec<String>>

Implements Kahn's algorithm with in-degree calculation to determine build order.

Usage¶

Basic Usage¶

Simply run ccgo install and CCGO will automatically: 1. Resolve transitive dependencies 2. Display the dependency tree 3. Show installation order 4. Install all dependencies in correct order

ccgo install

What Gets Resolved¶

Given this project structure:

Project CCGO.toml:

[package]
name = "myapp"
version = "1.0.0"

[[dependencies]]
name = "libA"
version = "1.0.0"
path = "../libA"

libA CCGO.toml:

[package]
name = "libA"
version = "1.0.0"

[[dependencies]]
name = "libB"
version = "2.0.0"
path = "../libB"

libB CCGO.toml:

[package]
name = "libB"
version = "2.0.0"
# No dependencies

Running ccgo install will: 1. Discover libA (direct dependency) 2. Read libA's CCGO.toml 3. Discover libB (transitive dependency) 4. Read libB's CCGO.toml 5. Determine order: libB → libA → myapp 6. Install libB first, then libA

Testing¶

The implementation includes comprehensive tests:

Unit Tests¶

Located in src/dependency/resolver.rs and src/dependency/graph.rs:

test_simple_resolution: Basic single dependency
test_transitive_dependencies: Chain of dependencies (A → B → C)
test_circular_dependency_detection: Detect cycles (A → B → C → A)
test_shared_dependency: Diamond pattern (A → C, B → C)
test_missing_ccgo_toml: Handle dependencies without CCGO.toml
test_version_conflict_warning: Detect version conflicts
test_max_depth_exceeded: Prevent infinite recursion
test_simple_graph: Basic graph operations
test_cycle_detection: Cycle detection algorithm
test_shared_dependency (graph): Shared dependency statistics

Run tests with:

cargo test dependency

Limitations & Future Work¶

Current Limitations¶

Version Resolution: Currently uses "first version wins" strategy. Need proper semantic versioning resolution.
Workspace Dependencies: Not yet fully implemented for workspace inheritance.
Lockfile: No lockfile generation yet for reproducible builds.
Dependency Patching: No support for overriding transitive dependencies.

Planned Enhancements¶

Smart Version Resolution:
Semantic versioning awareness
Minimum version selection
Version constraint satisfaction
Lockfile Support:
Generate CCGO.lock with exact versions
Verify lockfile on install
Update command to refresh lockfile
Dependency Vendoring:
Download and cache dependencies
Offline build support
Reproducible builds
Dependency Overrides:
Patch dependencies via CCGO.toml
Replace URLs for mirroring
Version pinning
Build-time Dependencies:
Separate build-only dependencies
Development dependencies
Optional dependencies

src/dependency/mod.rs - Module definition
src/dependency/graph.rs - Dependency graph implementation (~450 lines)
src/dependency/resolver.rs - Dependency resolver (~620 lines)
src/commands/install.rs - Install command integration
src/config/ccgo_toml.rs - CCGO.toml configuration

References¶

Topological Sorting: Kahn's Algorithm
Cycle Detection: Depth-First Search
Semantic Versioning: semver.org

Changelog¶

v3.0.11 (2025-01-21)¶

✅ Implemented transitive dependency resolution
✅ Added dependency graph with cycle detection
✅ Added topological sorting for correct build order
✅ Added dependency tree visualization
✅ Added version conflict detection (warnings only)
✅ Integrated into install command
✅ Added comprehensive test suite (7 resolver tests + 3 graph tests)

This feature is part of the Rust CLI rewrite (spec 001-rust-cli-rewrite) to achieve zero Python dependency.