agpm-cli 0.4.14

//! Integration tests for backtracking conflict resolution.
//!
//! These tests verify the automatic conflict resolution via backtracking,
//! including oscillation detection, multiple conflicts, and error handling.

use crate::common::{ManifestBuilder, TestProject};
use anyhow::Result;

/// Test that backtracking successfully handles complex transitive conflicts via backtracking.
///
/// This test demonstrates that backtracking can successfully resolve conflicts by
/// modifying transitive dependency versions. The prefix filtering makes top-level
/// dependency selection deterministic, but transitive conflict resolution remains
/// non-deterministic (known limitation).
///
/// Dependency structure:
/// ```
/// Manifest: D >=v1.0.0 (matches both v1 and v2, resolves to v2.0.0 deterministically)
///
/// D v1.0.0 → A v1.0.0 + B v1.0.0
/// D v2.0.0 → A v2.0.0 + B v2.0.0
///
/// A v1.0.0 → X v1.0.0 (initial requirement)
/// A v2.0.0 → X v2.0.0 (initial requirement)
/// B v1.0.0 → X v2.0.0  (conflicts with A v1!)
/// B v2.0.0 → X v1.0.0  (conflicts with A v2!)
/// ```
///
/// Backtracking resolution (partially deterministic):
/// 1. Selects D v2.0.0 deterministically (highest version matching d->=v1.0.0 with d- prefix)
/// 2. D v2.0.0 requires A v2.0.0 (wants X v2.0.0) + B v2.0.0 (wants X v1.0.0)
/// 3. Resolves transitive conflict non-deterministically by choosing either X v1.0.0 or X v2.0.0
///    (both are valid resolutions; specific version depends on internal backtracking order)
///
/// NOTE: This test accepts either X v1.0.0 or X v2.0.0 as valid outcomes due to the
/// non-deterministic transitive resolution. This is a known limitation to be addressed.
#[tokio::test]
async fn test_backtracking_oscillation_detection() -> Result<()> {
    let project = TestProject::new().await?;
    let source_repo = project.create_source_repo("source").await?;

    // Create Snippet X v1.0.0 and v2.0.0
    source_repo.add_resource("snippets", "snippet-x", "# Snippet X v1.0.0").await?;
    source_repo.commit_all("Snippet X v1.0.0")?;
    source_repo.tag_version("x-v1.0.0")?;

    source_repo.add_resource("snippets", "snippet-x", "# Snippet X v2.0.0 CHANGED").await?;
    source_repo.commit_all("Snippet X v2.0.0")?;
    source_repo.tag_version("x-v2.0.0")?;

    // Create A v1.0.0 → X v1.0.0
    let agent_a_v1 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-x.md
      version: x-v1.0.0
---
# Agent A v1.0.0"#;
    source_repo.add_resource("agents", "agent-a", agent_a_v1).await?;
    source_repo.commit_all("Agent A v1.0.0")?;
    source_repo.tag_version("a-v1.0.0")?;

    // Create A v2.0.0 → X v2.0.0
    let agent_a_v2 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-x.md
      version: x-v2.0.0
---
# Agent A v2.0.0 CHANGED"#;
    source_repo.add_resource("agents", "agent-a", agent_a_v2).await?;
    source_repo.commit_all("Agent A v2.0.0")?;
    source_repo.tag_version("a-v2.0.0")?;

    // Create B v1.0.0 → X v2.0.0 (conflicts with A v1!)
    let agent_b_v1 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-x.md
      version: x-v2.0.0
---
# Agent B v1.0.0"#;
    source_repo.add_resource("agents", "agent-b", agent_b_v1).await?;
    source_repo.commit_all("Agent B v1.0.0")?;
    source_repo.tag_version("b-v1.0.0")?;

    // Create B v2.0.0 → X v1.0.0 (conflicts with A v2!)
    let agent_b_v2 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-x.md
      version: x-v1.0.0
---
# Agent B v2.0.0 CHANGED"#;
    source_repo.add_resource("agents", "agent-b", agent_b_v2).await?;
    source_repo.commit_all("Agent B v2.0.0")?;
    source_repo.tag_version("b-v2.0.0")?;

    // Create D v1.0.0 → A v1.0.0 + B v1.0.0
    let command_d_v1 = r#"---
dependencies:
  agents:
    - path: agents/agent-a.md
      version: a-v1.0.0
    - path: agents/agent-b.md
      version: b-v1.0.0
---
# Command D v1.0.0"#;
    source_repo.add_resource("commands", "deploy", command_d_v1).await?;
    source_repo.commit_all("Command D v1.0.0")?;
    source_repo.tag_version("d-v1.0.0")?;

    // Create D v2.0.0 → A v2.0.0 + B v2.0.0
    let command_d_v2 = r#"---
dependencies:
  agents:
    - path: agents/agent-a.md
      version: a-v2.0.0
    - path: agents/agent-b.md
      version: b-v2.0.0
---
# Command D v2.0.0 CHANGED"#;
    source_repo.add_resource("commands", "deploy", command_d_v2).await?;
    source_repo.commit_all("Command D v2.0.0")?;
    source_repo.tag_version("d-v2.0.0")?;

    // Create manifest requesting D with version range >=v1.0.0 (matches both v1 and v2)
    let manifest = ManifestBuilder::new()
        .add_source("source", &source_repo.bare_file_url(project.sources_path()).await?)
        .add_command("deploy", |d| {
            d.source("source").path("commands/deploy.md").version("d->=v1.0.0")
        })
        .build();
    project.write_manifest(&manifest).await?;

    let output = project.run_agpm_with_env(
        &["install"],
        &[("RUST_LOG", "fs::retry=warn,version_resolver=debug,agpm_cli::resolver=debug")],
    )?;

    // Should succeed - backtracking successfully resolves the conflict
    assert!(output.success, "Install should succeed via backtracking. Stderr: {}", output.stderr);

    let lockfile = project.read_lockfile().await?;

    // Verify backtracking resolved to D v2.0.0
    // With deterministic prefix filtering, d->=v1.0.0 consistently selects d-v2.0.0 (highest version)
    assert!(
        lockfile.contains("d-v2.0.0"),
        "Lockfile should contain d-v2.0.0 (highest matching version with deterministic prefix filtering)"
    );

    // NOTE: There's still non-determinism in backtracking's transitive conflict resolution
    // D v2.0.0 → A v2.0.0 (wants X v2) + B v2.0.0 (wants X v1)
    // Backtracking non-deterministically chooses EITHER x-v1.0.0 OR x-v2.0.0
    // Both are valid resolutions. This is a separate bug to fix.
    assert!(
        lockfile.contains("snippets/snippet-x"),
        "Lockfile should contain snippet-x (transitive dependency)"
    );
    assert!(
        lockfile.contains("x-v1.0.0") || lockfile.contains("x-v2.0.0"),
        "Lockfile should contain either x-v1.0.0 or x-v2.0.0 (both are valid backtracking resolutions)"
    );

    // Verify all resources are installed
    assert!(project.project_path().join(".claude/commands/agpm/deploy.md").exists());
    assert!(project.project_path().join(".claude/agents/agpm/agent-a.md").exists());
    assert!(project.project_path().join(".claude/agents/agpm/agent-b.md").exists());
    // This test has NO manifest dep on snippet-x, only transitive deps.
    // Transitive deps inherit tool from parent (command/agent uses claude-code).
    assert!(project.project_path().join(".claude/snippets/agpm/snippet-x.md").exists());

    // Ensure no panic or errors occurred
    assert!(
        !output.stderr.contains("panic") && !output.stderr.contains("Error"),
        "Should not have errors. Stderr: {}",
        output.stderr
    );

    Ok(())
}

/// Test that backtracking can handle multiple simultaneous independent conflicts.
///
/// This verifies that when 3+ independent resources have version conflicts,
/// the backtracking algorithm can identify and report all of them clearly.
///
/// Scenario:
/// - Create 3 independent resources: agents/helper, snippets/utils, commands/deploy
/// - Each has v1.0.0 and v2.0.0 with different content (different SHAs)
/// - Manifest requests both versions of each resource (6 total dependencies)
/// - All 3 conflicts should be detected
#[tokio::test]
async fn test_backtracking_multiple_simultaneous_conflicts() -> Result<()> {
    let project = TestProject::new().await?;
    let source_repo = project.create_source_repo("source").await?;

    // Create helper v1.0.0
    source_repo.add_resource("agents", "helper", "# Helper v1.0.0").await?;
    source_repo.add_resource("snippets", "utils", "# Utils v1.0.0").await?;
    source_repo.add_resource("commands", "deploy", "# Deploy v1.0.0").await?;
    source_repo.commit_all("v1.0.0")?;
    source_repo.tag_version("v1.0.0")?;

    // Create v2.0.0 with different content for all 3 resources
    source_repo.add_resource("agents", "helper", "# Helper v2.0.0 CHANGED").await?;
    source_repo.add_resource("snippets", "utils", "# Utils v2.0.0 CHANGED").await?;
    source_repo.add_resource("commands", "deploy", "# Deploy v2.0.0 CHANGED").await?;
    source_repo.commit_all("v2.0.0")?;
    source_repo.tag_version("v2.0.0")?;

    // Create manifest with 6 dependencies - 2 per resource, each with conflicting exact versions
    let manifest = ManifestBuilder::new()
        .add_source("source", &source_repo.bare_file_url(project.sources_path()).await?)
        .add_agent("helper-v1", |d| d.source("source").path("agents/helper.md").version("v1.0.0"))
        .add_agent("helper-v2", |d| d.source("source").path("agents/helper.md").version("v2.0.0"))
        .add_snippet("utils-v1", |d| d.source("source").path("snippets/utils.md").version("v1.0.0"))
        .add_snippet("utils-v2", |d| d.source("source").path("snippets/utils.md").version("v2.0.0"))
        .add_command("deploy-v1", |d| {
            d.source("source").path("commands/deploy.md").version("v1.0.0")
        })
        .add_command("deploy-v2", |d| {
            d.source("source").path("commands/deploy.md").version("v2.0.0")
        })
        .build();
    project.write_manifest(&manifest).await?;

    let output = project.run_agpm(&["install"])?;

    // Should fail with multiple version conflicts
    assert!(
        !output.success,
        "Install should fail with multiple conflicts. Stderr: {}",
        output.stderr
    );

    // Should mention version conflicts
    assert!(
        output.stderr.contains("Version conflicts detected")
            || output.stderr.contains("automatic resolution failed")
            || output.stderr.contains("Unresolvable SHA conflicts detected"),
        "Should report version conflicts. Stderr: {}",
        output.stderr
    );

    // All 3 conflicting resources should be mentioned
    assert!(
        output.stderr.contains("helper"),
        "Should mention helper conflict. Stderr: {}",
        output.stderr
    );
    assert!(
        output.stderr.contains("utils"),
        "Should mention utils conflict. Stderr: {}",
        output.stderr
    );
    assert!(
        output.stderr.contains("deploy"),
        "Should mention deploy conflict. Stderr: {}",
        output.stderr
    );

    // Ensure no panic occurred
    assert!(!output.stderr.contains("panic"), "Should not panic. Stderr: {}", output.stderr);

    Ok(())
}

/// Test that backtracking handles errors gracefully without panicking.
///
/// This test verifies proper error handling in several failure scenarios:
/// 1. Missing/invalid source repository
/// 2. Incompatible exact version constraints (NoCompatibleVersion)
/// 3. General Git operation failures
///
/// All scenarios should fail gracefully with helpful error messages, not panics.
#[tokio::test]
async fn test_backtracking_error_handling() -> Result<()> {
    // Scenario A: Missing source repository
    {
        let project = TestProject::new().await?;

        // Create manifest referencing a non-existent source
        let manifest = ManifestBuilder::new()
            .add_source("nonexistent", "file:///nonexistent/repo.git")
            .add_agent("agent", |d| d.source("nonexistent").path("agents/agent.md"))
            .build();
        project.write_manifest(&manifest).await?;

        let output = project.run_agpm(&["install"])?;

        assert!(
            !output.success,
            "Should fail gracefully with missing source. Stderr: {}",
            output.stderr
        );
        assert!(
            output.stderr.contains("Failed")
                || output.stderr.contains("Error")
                || output.stderr.contains("not found"),
            "Should have helpful error message. Stderr: {}",
            output.stderr
        );
        assert!(!output.stderr.contains("panicked"), "Should not panic. Stderr: {}", output.stderr);
    }

    // Scenario B: Incompatible exact version constraints
    {
        let project = TestProject::new().await?;
        let source_repo = project.create_source_repo("source").await?;

        // Create v1.0.0
        source_repo.add_resource("agents", "agent-a", "# Agent A v1.0.0").await?;
        source_repo.commit_all("v1.0.0")?;
        source_repo.tag_version("v1.0.0")?;

        // Create v2.0.0 with different content
        source_repo.add_resource("agents", "agent-a", "# Agent A v2.0.0 CHANGED").await?;
        source_repo.commit_all("v2.0.0")?;
        source_repo.tag_version("v2.0.0")?;

        // Create manifest with incompatible exact version requirements
        let manifest = ManifestBuilder::new()
            .add_source("source", &source_repo.bare_file_url(project.sources_path()).await?)
            .add_agent("agent-v1", |d| {
                d.source("source").path("agents/agent-a.md").version("v1.0.0")
            })
            .add_agent("agent-v2", |d| {
                d.source("source").path("agents/agent-a.md").version("v2.0.0")
            })
            .build();
        project.write_manifest(&manifest).await?;

        let output = project.run_agpm(&["install"])?;

        assert!(
            !output.success,
            "Should fail with incompatible versions. Stderr: {}",
            output.stderr
        );
        assert!(
            output.stderr.contains("no compatible version")
                || output.stderr.contains("Version conflicts detected")
                || output.stderr.contains("automatic resolution failed")
                || output.stderr.contains("Unresolvable SHA conflicts detected"),
            "Should report inability to resolve. Stderr: {}",
            output.stderr
        );
        assert!(
            output.stderr.contains("agents/agent-a"),
            "Should mention the conflicting resource. Stderr: {}",
            output.stderr
        );
        assert!(!output.stderr.contains("panicked"), "Should not panic. Stderr: {}", output.stderr);
    }

    Ok(())
}

/// Test that backtracking successfully resolves conflicts in deep dependency chains.
///
/// This test verifies that the backtracking algorithm can navigate up through
/// multiple levels of transitive dependencies to find a compatible version.
///
/// Dependency structure: A→B→C→D where D conflicts with another resource
/// ```
/// Manifest: A ^1.0.0
///
/// A v1.0.0 → B v1.0.0 → C v1.0.0 → D v1.0.0
/// A v2.0.0 → B v1.0.0 → C v1.0.0 → D v2.0.0 (conflicts with E)
///
/// E v1.0.0 (conflicts with D v2.0.0)
/// E v2.0.0 (compatible with D v1.0.0)
/// ```
///
/// Backtracking should find that A v1.0.0 → D v1.0.0 resolves the conflict.
#[tokio::test]
async fn test_backtracking_deep_chain_conflict() -> Result<()> {
    let project = TestProject::new().await?;
    let source_repo = project.create_source_repo("source").await?;

    // Create resource E v1.0.0 and v2.0.0 (conflicting resource)
    source_repo.add_resource("snippets", "snippet-e", "# Snippet E v1.0.0").await?;
    source_repo.commit_all("Snippet E v1.0.0")?;
    source_repo.tag_version("e-v1.0.0")?;

    source_repo.add_resource("snippets", "snippet-e", "# Snippet E v2.0.0 CHANGED").await?;
    source_repo.commit_all("Snippet E v2.0.0")?;
    source_repo.tag_version("e-v2.0.0")?;

    // Create D v1.0.0 → E v2.0.0 (compatible)
    let command_d_v1 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-e.md
      version: e-v2.0.0
---
# Command D v1.0.0"#;
    source_repo.add_resource("commands", "command-d", command_d_v1).await?;
    source_repo.commit_all("Command D v1.0.0")?;
    source_repo.tag_version("d-v1.0.0")?;

    // Create D v2.0.0 → E v1.0.0 (conflicts with A v2)
    let command_d_v2 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-e.md
      version: e-v1.0.0
---
# Command D v2.0.0 CHANGED"#;
    source_repo.add_resource("commands", "command-d", command_d_v2).await?;
    source_repo.commit_all("Command D v2.0.0")?;
    source_repo.tag_version("d-v2.0.0")?;

    // Create C v1.0.0 → D v1.0.0
    let agent_c_v1 = r#"---
dependencies:
  commands:
    - path: commands/command-d.md
      version: d-v1.0.0
---
# Agent C v1.0.0"#;
    source_repo.add_resource("agents", "agent-c", agent_c_v1).await?;
    source_repo.commit_all("Agent C v1.0.0")?;
    source_repo.tag_version("c-v1.0.0")?;

    // Create B v1.0.0 → C v1.0.0
    let agent_b_v1 = r#"---
dependencies:
  agents:
    - path: agents/agent-c.md
      version: c-v1.0.0
---
# Agent B v1.0.0"#;
    source_repo.add_resource("agents", "agent-b", agent_b_v1).await?;
    source_repo.commit_all("Agent B v1.0.0")?;
    source_repo.tag_version("b-v1.0.0")?;

    // Create A v1.0.0 → B v1.0.0
    let agent_a_v1 = r#"---
dependencies:
  agents:
    - path: agents/agent-b.md
      version: b-v1.0.0
---
# Agent A v1.0.0"#;
    source_repo.add_resource("agents", "agent-a", agent_a_v1).await?;
    source_repo.commit_all("Agent A v1.0.0")?;
    source_repo.tag_version("a-v1.0.0")?;

    // Create A v2.0.0 → B v1.0.0 (leads to conflict via D v2)
    let agent_a_v2 = r#"---
dependencies:
  agents:
    - path: agents/agent-b.md
      version: b-v1.0.0
---
# Agent A v2.0.0 CHANGED"#;
    source_repo.add_resource("agents", "agent-a", agent_a_v2).await?;
    source_repo.commit_all("Agent A v2.0.0")?;
    source_repo.tag_version("a-v2.0.0")?;

    // Create manifest with both A (leading to conflict) and E v2.0.0
    let manifest = ManifestBuilder::new()
        .add_source("source", &source_repo.bare_file_url(project.sources_path()).await?)
        .add_agent("agent-a", |d| d.source("source").path("agents/agent-a.md").version("a-^v1.0.0"))
        .add_snippet("snippet-e", |d| {
            d.source("source").path("snippets/snippet-e.md").version("e-v2.0.0")
        })
        .build();
    project.write_manifest(&manifest).await?;

    let output = project.run_agpm(&["install"])?;

    // Debug: Check what was actually installed
    let lockfile = project.read_lockfile().await?;
    eprintln!("\n=== FULL LOCKFILE ===");
    eprintln!("{}", lockfile);

    // Should succeed - backtracking should resolve conflict by choosing A v1.0.0
    assert!(output.success, "Install should succeed via backtracking. Stderr: {}", output.stderr);

    // Verify backtracking chose the compatible path (A v1.0.0 → D v1.0.0 → E v2.0.0)
    assert!(
        lockfile.contains("agents/agent-a") && lockfile.contains("a-v1.0.0"),
        "Lockfile should contain agent-a at v1.0.0 (compatible path)"
    );
    assert!(
        lockfile.contains("snippets/snippet-e") && lockfile.contains("e-v2.0.0"),
        "Lockfile should contain snippet-e at v2.0.0 (no conflict)"
    );

    // Verify all resources are installed correctly
    assert!(project.project_path().join(".claude/agents/agpm/agent-a.md").exists());
    assert!(project.project_path().join(".claude/agents/agpm/agent-b.md").exists());
    assert!(project.project_path().join(".claude/agents/agpm/agent-c.md").exists());
    assert!(project.project_path().join(".claude/commands/agpm/command-d.md").exists());
    // Manifest dep uses default tool for snippets (agpm), so installed to .agpm/
    assert!(project.project_path().join(".agpm/snippets/snippet-e.md").exists());

    // Ensure no panic or errors occurred
    assert!(
        !output.stderr.contains("panic") && !output.stderr.contains("Error"),
        "Should not have errors. Stderr: {}",
        output.stderr
    );

    Ok(())
}

/// Test that backtracking handles multiple branch conflicts at different depths.
///
/// This test verifies that when conflicts occur at different levels in the
/// dependency tree, backtracking can resolve all of them simultaneously.
///
/// Dependency structure: A→B→D and A→C→E where D and E conflict on same resource
/// ```
/// Manifest: A ^1.0.0, X v1.0.0
///
/// A v1.0.0:
/// ├── B v1.0.0 → D v1.0.0 → X v1.0.0 (compatible with manifest)
/// └── C v1.0.0 → E v1.0.0 → X v1.0.0 (compatible with manifest)
///
/// A v2.0.0:
/// ├── B v2.0.0 → D v2.0.0 → X v2.0.0 (conflict with manifest X v1.0.0)
/// └── C v2.0.0 → E v2.0.0 → X v2.0.0 (same conflict)
///
/// X v1.0.0 and X v2.0.0 (manifest requests v1.0.0)
/// ```
///
/// Backtracking should choose A v1.0.0 to resolve both branch conflicts.
#[tokio::test]
async fn test_backtracking_multiple_branch_conflicts() -> Result<()> {
    let project = TestProject::new().await?;
    let source_repo = project.create_source_repo("source").await?;

    // Create X v1.0.0 and v2.0.0 (shared conflicting resource)
    source_repo.add_resource("snippets", "snippet-x", "# Snippet X v1.0.0").await?;
    source_repo.commit_all("Snippet X v1.0.0")?;
    source_repo.tag_version("x-v1.0.0")?;

    source_repo.add_resource("snippets", "snippet-x", "# Snippet X v2.0.0 CHANGED").await?;
    source_repo.commit_all("Snippet X v2.0.0")?;
    source_repo.tag_version("x-v2.0.0")?;

    // Create D v1.0.0 → X v1.0.0 (compatible)
    let command_d_v1 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-x.md
      version: x-v1.0.0
---
# Command D v1.0.0"#;
    source_repo.add_resource("commands", "command-d", command_d_v1).await?;
    source_repo.commit_all("Command D v1.0.0")?;
    source_repo.tag_version("d-v1.0.0")?;

    // Create D v2.0.0 → X v2.0.0 (conflicts with manifest)
    let command_d_v2 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-x.md
      version: x-v2.0.0
---
# Command D v2.0.0 CHANGED"#;
    source_repo.add_resource("commands", "command-d", command_d_v2).await?;
    source_repo.commit_all("Command D v2.0.0")?;
    source_repo.tag_version("d-v2.0.0")?;

    // Create E v1.0.0 → X v1.0.0 (compatible)
    let command_e_v1 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-x.md
      version: x-v1.0.0
---
# Command E v1.0.0"#;
    source_repo.add_resource("commands", "command-e", command_e_v1).await?;
    source_repo.commit_all("Command E v1.0.0")?;
    source_repo.tag_version("e-v1.0.0")?;

    // Create E v2.0.0 → X v2.0.0 (conflicts with manifest)
    let command_e_v2 = r#"---
dependencies:
  snippets:
    - path: snippets/snippet-x.md
      version: x-v2.0.0
---
# Command E v2.0.0 CHANGED"#;
    source_repo.add_resource("commands", "command-e", command_e_v2).await?;
    source_repo.commit_all("Command E v2.0.0")?;
    source_repo.tag_version("e-v2.0.0")?;

    // Create B v1.0.0 → D v1.0.0 (compatible path)
    let agent_b_v1 = r#"---
dependencies:
  commands:
    - path: commands/command-d.md
      version: d-v1.0.0
---
# Agent B v1.0.0"#;
    source_repo.add_resource("agents", "agent-b", agent_b_v1).await?;
    source_repo.commit_all("Agent B v1.0.0")?;
    source_repo.tag_version("b-v1.0.0")?;

    // Create B v2.0.0 → D v2.0.0 (conflict path)
    let agent_b_v2 = r#"---
dependencies:
  commands:
    - path: commands/command-d.md
      version: d-v2.0.0
---
# Agent B v2.0.0 CHANGED"#;
    source_repo.add_resource("agents", "agent-b", agent_b_v2).await?;
    source_repo.commit_all("Agent B v2.0.0")?;
    source_repo.tag_version("b-v2.0.0")?;

    // Create C v1.0.0 → E v1.0.0 (compatible path)
    let agent_c_v1 = r#"---
dependencies:
  commands:
    - path: commands/command-e.md
      version: e-v1.0.0
---
# Agent C v1.0.0"#;
    source_repo.add_resource("agents", "agent-c", agent_c_v1).await?;
    source_repo.commit_all("Agent C v1.0.0")?;
    source_repo.tag_version("c-v1.0.0")?;

    // Create C v2.0.0 → E v2.0.0 (conflict path)
    let agent_c_v2 = r#"---
dependencies:
  commands:
    - path: commands/command-e.md
      version: e-v2.0.0
---
# Agent C v2.0.0 CHANGED"#;
    source_repo.add_resource("agents", "agent-c", agent_c_v2).await?;
    source_repo.commit_all("Agent C v2.0.0")?;
    source_repo.tag_version("c-v2.0.0")?;

    // Create A v1.0.0 → B v1.0.0 + C v1.0.0 (compatible path)
    let agent_a_v1 = r#"---
dependencies:
  agents:
    - path: agents/agent-b.md
      version: b-v1.0.0
    - path: agents/agent-c.md
      version: c-v1.0.0
---
# Agent A v1.0.0"#;
    source_repo.add_resource("agents", "agent-a", agent_a_v1).await?;
    source_repo.commit_all("Agent A v1.0.0")?;
    source_repo.tag_version("a-v1.0.0")?;

    // Create A v2.0.0 → B v2.0.0 + C v2.0.0 (leads to conflicts via D v2 and E v2)
    let agent_a_v2 = r#"---
dependencies:
  agents:
    - path: agents/agent-b.md
      version: b-v2.0.0
    - path: agents/agent-c.md
      version: c-v2.0.0
---
# Agent A v2.0.0 CHANGED"#;
    source_repo.add_resource("agents", "agent-a", agent_a_v2).await?;
    source_repo.commit_all("Agent A v2.0.0")?;
    source_repo.tag_version("a-v2.0.0")?;

    // Create manifest with A (could conflict) and X v1.0.0 (fixed constraint)
    let manifest = ManifestBuilder::new()
        .add_source("source", &source_repo.bare_file_url(project.sources_path()).await?)
        .add_agent("agent-a", |d| d.source("source").path("agents/agent-a.md").version("a-^v1.0.0"))
        .add_snippet("snippet-x", |d| {
            d.source("source").path("snippets/snippet-x.md").version("x-v1.0.0")
        })
        .build();
    project.write_manifest(&manifest).await?;

    let output = project.run_agpm(&["install"])?;

    // Should succeed - backtracking should resolve both branch conflicts by choosing A v1.0.0
    assert!(output.success, "Install should succeed via backtracking. Stderr: {}", output.stderr);

    let lockfile = project.read_lockfile().await?;

    // Verify backtracking chose compatible path (A v1.0.0 → D v1.0.0/E v1.0.0 → X v1.0.0)
    assert!(
        lockfile.contains("agents/agent-a") && lockfile.contains("a-v1.0.0"),
        "Lockfile should contain agent-a at v1.0.0 (compatible path)"
    );
    assert!(
        lockfile.contains("snippets/snippet-x") && lockfile.contains("x-v1.0.0"),
        "Lockfile should contain snippet-x at v1.0.0 (no conflict)"
    );

    // Verify all resources are installed correctly
    assert!(project.project_path().join(".claude/agents/agpm/agent-a.md").exists());
    assert!(project.project_path().join(".claude/agents/agpm/agent-b.md").exists());
    assert!(project.project_path().join(".claude/agents/agpm/agent-c.md").exists());
    assert!(project.project_path().join(".claude/commands/agpm/command-d.md").exists());
    assert!(project.project_path().join(".claude/commands/agpm/command-e.md").exists());
    // Manifest dep uses default tool for snippets (agpm), so installed to .agpm/
    assert!(project.project_path().join(".agpm/snippets/snippet-x.md").exists());

    // Ensure no panic or errors occurred
    assert!(
        !output.stderr.contains("panic") && !output.stderr.contains("Error"),
        "Should not have errors. Stderr: {}",
        output.stderr
    );

    Ok(())
}

/// Test that backtracking detects circular dependencies with transitive dependencies.
///
/// This test verifies that the dependency graph correctly detects cycles
/// at any depth and provides appropriate error messages.
///
/// Dependency structure: A→B→C→A (circular)
/// ```
/// Manifest: A v1.0.0
///
/// A v1.0.0 → B v1.0.0 → C v1.0.0 → A v1.0.0 (cycle!)
/// ```
#[tokio::test]
async fn test_backtracking_circular_dependency_detection() -> Result<()> {
    let project = TestProject::new().await?;
    let source_repo = project.create_source_repo("source").await?;

    // Create all three agents with circular dependencies in one batch
    source_repo
        .add_resource(
            "agents",
            "agent-a",
            r#"---
dependencies:
  agents:
    - path: ./agent-b.md
      version: v1.0.0
---
# Agent A v1.0.0
Depends on Agent B
"#,
        )
        .await?;

    source_repo
        .add_resource(
            "agents",
            "agent-b",
            r#"---
dependencies:
  agents:
    - path: ./agent-c.md
      version: v1.0.0
---
# Agent B v1.0.0
Depends on Agent C
"#,
        )
        .await?;

    source_repo
        .add_resource(
            "agents",
            "agent-c",
            r#"---
dependencies:
  agents:
    - path: ./agent-a.md
      version: v1.0.0
---
# Agent C v1.0.0
Depends on Agent A (completes cycle)
"#,
        )
        .await?;

    source_repo.commit_all("Add agents with circular dependencies")?;
    source_repo.tag_version("v1.0.0")?;

    // Create manifest that will trigger cycle
    let manifest = ManifestBuilder::new()
        .add_source("source", &source_repo.bare_file_url(project.sources_path()).await?)
        .add_agent("agent-a", |d| d.source("source").path("agents/agent-a.md").version("v1.0.0"))
        .build();
    project.write_manifest(&manifest).await?;

    let output = project.run_agpm(&["install"])?;

    // Should fail due to circular dependency
    assert!(
        !output.success,
        "Install should fail due to circular dependency. Stderr: {}",
        output.stderr
    );

    // Should mention circular dependency or cycle in error
    assert!(
        output.stderr.to_lowercase().contains("circular")
            || output.stderr.to_lowercase().contains("cycle")
            || output.stderr.to_lowercase().contains("dependency cycle"),
        "Should report circular dependency. Stderr: {}",
        output.stderr
    );

    // Ensure no panic occurred (should be a graceful error)
    assert!(!output.stderr.contains("panicked"), "Should not panic. Stderr: {}", output.stderr);

    Ok(())
}

/// Test that backtracking detects circular dependencies in complex scenarios.
///
/// This test verifies that cycle detection works even when cycles involve
/// different resource types and deeper chains.
///
/// Dependency structure: A→B→C→D→A (4-node cycle)
/// ```
/// Manifest: A v1.0.0
///
/// A v1.0.0 → B v1.0.0 → C v1.0.0 → D v1.0.0 → A v1.0.0
/// ```
#[tokio::test]
async fn test_backtracking_complex_circular_dependency() -> Result<()> {
    let project = TestProject::new().await?;
    let source_repo = project.create_source_repo("source").await?;

    // Create A v1.0.0 → B v1.0.0
    let agent_a_v1 = r#"---
dependencies:
  agents:
    - path: ./agent-b.md
      version: v1.0.0
---
# Agent A v1.0.0
Depends on Agent B
"#;
    source_repo.add_resource("agents", "agent-a", agent_a_v1).await?;
    source_repo.commit_all("Agent A v1.0.0")?;
    source_repo.tag_version("a-v1.0.0")?;

    // Create B v1.0.0 → C v1.0.0
    let agent_b_v1 = r#"---
dependencies:
  commands:
    - path: commands/command-c.md
      version: v1.0.0
---
# Agent B v1.0.0
Depends on Command C
"#;
    source_repo.add_resource("agents", "agent-b", agent_b_v1).await?;
    source_repo.commit_all("Agent B v1.0.0")?;
    source_repo.tag_version("b-v1.0.0")?;

    // Create C v1.0.0 → D v1.0.0
    let command_c_v1 = r#"---
dependencies:
  agents:
    - path: agents/agent-d.md
      version: v1.0.0
---
# Command C v1.0.0
Depends on Agent D
"#;
    source_repo.add_resource("commands", "command-c", command_c_v1).await?;

    // Create D v1.0.0 → A v1.0.0 (completes 4-node cycle)
    let agent_d_v1 = r#"---
dependencies:
  agents:
    - path: agents/agent-a.md
      version: v1.0.0
---
# Agent D v1.0.0
Depends on Agent A (completes 4-node cycle)
"#;
    source_repo.add_resource("agents", "agent-d", agent_d_v1).await?;

    source_repo.commit_all("Add resources with 4-node circular dependency")?;
    source_repo.tag_version("v1.0.0")?;

    // Create manifest that will trigger cycle
    let manifest = ManifestBuilder::new()
        .add_source("source", &source_repo.bare_file_url(project.sources_path()).await?)
        .add_agent("agent-a", |d| d.source("source").path("agents/agent-a.md").version("v1.0.0"))
        .build();
    project.write_manifest(&manifest).await?;

    let output = project.run_agpm(&["install"])?;

    // Should fail due to circular dependency
    assert!(
        !output.success,
        "Install should fail due to circular dependency. Stderr: {}",
        output.stderr
    );

    // Should mention circular dependency or cycle in error
    assert!(
        output.stderr.to_lowercase().contains("circular")
            || output.stderr.to_lowercase().contains("cycle")
            || output.stderr.to_lowercase().contains("dependency cycle"),
        "Should report circular dependency. Stderr: {}",
        output.stderr
    );

    // Ensure no panic occurred (should be a graceful error)
    assert!(!output.stderr.contains("panicked"), "Should not panic. Stderr: {}", output.stderr);

    Ok(())
}