# Transitive Dependency Resolution

> **See also:** [`dependency-linkage.md`](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:

1. **`path = "..."`** — local path dependency. Symlinked or copied
   from the relative/absolute path in the consumer's tree.
2. **`git = "..."` (with `branch` / `tag` / `rev`)** — Git dependency.
   Cloned shallowly into `~/.ccgo/git/<repo>/`.
3. **`zip = "..."`** — archive dependency. Downloaded (`https://`) or
   read (`file://`, local path) and extracted into `.ccgo/deps/<name>/`.
4. **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`](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

```rust
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)

```rust
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)

```rust
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

```bash
ccgo install
```

### What Gets Resolved

Given this project structure:

**Project CCGO.toml:**
```toml
[package]
name = "myapp"
version = "1.0.0"

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

**libA CCGO.toml:**
```toml
[package]
name = "libA"
version = "1.0.0"

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

**libB CCGO.toml:**
```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:
```bash
cargo test dependency
```

## Limitations & Future Work

### Current Limitations

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

### Planned Enhancements

1. **Smart Version Resolution**:
   - Semantic versioning awareness
   - Minimum version selection
   - Version constraint satisfaction

2. **Lockfile Support**:
   - Generate CCGO.lock with exact versions
   - Verify lockfile on install
   - Update command to refresh lockfile

3. **Dependency Vendoring**:
   - Download and cache dependencies
   - Offline build support
   - Reproducible builds

4. **Dependency Overrides**:
   - Patch dependencies via CCGO.toml
   - Replace URLs for mirroring
   - Version pinning

5. **Build-time Dependencies**:
   - Separate build-only dependencies
   - Development dependencies
   - Optional dependencies

## Related Files

- `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](https://en.wikipedia.org/wiki/Topological_sorting)
- **Cycle Detection**: [Depth-First Search](https://en.wikipedia.org/wiki/Cycle_detection)
- **Semantic Versioning**: [semver.org](https://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.*
