// Copyright (C) 2026  The Software Heritage developers
// See the AUTHORS file at the top-level directory of this distribution
// License: GNU General Public License version 3, or any later version
// See top-level LICENSE file for more information

use std::collections::HashMap;

use anyhow::Result;
use osv::schema::Ecosystem;
use swh_graph::graph::SwhGraphWithProperties;
use swh_graph::graph_builder::{BuiltGraph, GraphBuilder};
use swh_graph::labels::VisitStatus;
use swh_graph::{SWHID, swhid};

use swh_osv::packages::versions::VersionType;
use swh_osv::packages::{
    Stats, SwhAffected, SwhEvent, SwhRange, SwhVersion, VersionInSwh, VersionMatch,
    VersionSearchInfo, VersionToSwhidMapping, list_affected_versions,
};

struct MultiVersionGraph {
    graph: BuiltGraph,
    origin_url: String,
    versions: HashMap<String, SWHID>,
}

impl MultiVersionGraph {
    fn swhid_for(&self, version_name: &str) -> SWHID {
        *self
            .versions
            .get(version_name)
            .expect("version present in multiversion graph")
    }

    fn version_mapping(&self, version_name: &str) -> VersionToSwhidMapping {
        VersionToSwhidMapping {
            package_version: VersionMatch {
                version_name: version_name.to_string(),
                origin_url: self.origin_url.clone(),
                fuzzy_branch_name_match: false,
                branch_name: format!("releases/{version_name}").into_bytes(),
                node: self
                    .graph
                    .properties()
                    .node_id(self.swhid_for(version_name))
                    .unwrap(),
            },
            version_type: VersionType::Semver,
            vcs: vec![],
        }
    }

    fn mapped_version(&self, version_name: &str) -> VersionInSwh {
        VersionInSwh::MappedFromVersion(self.version_mapping(version_name))
    }

    fn version(&self, version_name: &str) -> SwhVersion {
        SwhVersion {
            original_version: Some(version_name.to_string()),
            branch_name: Some(format!("releases/{version_name}")),
            swhid: self.swhid_for(version_name),
        }
    }
}

// Helper to create a graph with multiple package versions for testing list_affected_versions
fn create_multiversion_graph() -> MultiVersionGraph {
    let mut builder = GraphBuilder::default();

    let origin_url = "https://www.npmjs.com/package/test-pkg";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000010))
        .unwrap()
        .done();

    // Create releases for versions: 0.9.0, 0.9.5, 1.0.0, 1.0.5, 1.1.0, 1.1.5, 1.2.0, 1.2.5, 2.0.0
    let rel_090 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000090))
        .unwrap()
        .done();
    let rel_095 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000095))
        .unwrap()
        .done();
    let rel_100 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000100))
        .unwrap()
        .done();
    let rel_105 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000105))
        .unwrap()
        .done();
    let rel_110 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000110))
        .unwrap()
        .done();
    let rel_115 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000115))
        .unwrap()
        .done();
    let rel_120 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000120))
        .unwrap()
        .done();
    let rel_125 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000125))
        .unwrap()
        .done();
    let rel_200 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000200))
        .unwrap()
        .done();

    // Create corresponding directories
    let dir_090 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000090))
        .unwrap()
        .done();
    let dir_095 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000095))
        .unwrap()
        .done();
    let dir_100 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000100))
        .unwrap()
        .done();
    let dir_105 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000105))
        .unwrap()
        .done();
    let dir_110 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000110))
        .unwrap()
        .done();
    let dir_115 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000115))
        .unwrap()
        .done();
    let dir_120 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000120))
        .unwrap()
        .done();
    let dir_125 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000125))
        .unwrap()
        .done();
    let dir_200 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000200))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    // NPM uses "releases/VERSION" format for branch names
    builder.snp_arc(snp, rel_090, b"releases/0.9.0");
    builder.snp_arc(snp, rel_095, b"releases/0.9.5");
    builder.snp_arc(snp, rel_100, b"releases/1.0.0");
    builder.snp_arc(snp, rel_105, b"releases/1.0.5");
    builder.snp_arc(snp, rel_110, b"releases/1.1.0");
    builder.snp_arc(snp, rel_115, b"releases/1.1.5");
    builder.snp_arc(snp, rel_120, b"releases/1.2.0");
    builder.snp_arc(snp, rel_125, b"releases/1.2.5");
    builder.snp_arc(snp, rel_200, b"releases/2.0.0");

    // Releases point directly to directories
    builder.arc(rel_090, dir_090);
    builder.arc(rel_095, dir_095);
    builder.arc(rel_100, dir_100);
    builder.arc(rel_105, dir_105);
    builder.arc(rel_110, dir_110);
    builder.arc(rel_115, dir_115);
    builder.arc(rel_120, dir_120);
    builder.arc(rel_125, dir_125);
    builder.arc(rel_200, dir_200);

    MultiVersionGraph {
        graph: builder.done().unwrap(),
        origin_url: origin_url.to_string(),
        versions: HashMap::from([
            (
                "0.9.0".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000090),
            ),
            (
                "0.9.5".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000095),
            ),
            (
                "1.0.0".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000100),
            ),
            (
                "1.0.5".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000105),
            ),
            (
                "1.1.0".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000110),
            ),
            (
                "1.1.5".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000115),
            ),
            (
                "1.2.0".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000120),
            ),
            (
                "1.2.5".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000125),
            ),
            (
                "2.0.0".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000200),
            ),
        ]),
    }
}

fn create_pypi_pep440_graph() -> MultiVersionGraph {
    let mut builder = GraphBuilder::default();

    let origin_url = "https://pypi.org/project/test-pkg/";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000001010))
        .unwrap()
        .done();

    let rel_100rc1 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000001001))
        .unwrap()
        .done();
    let rel_100 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000001000))
        .unwrap()
        .done();
    let rel_100post1 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000001002))
        .unwrap()
        .done();
    let rel_110 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000001100))
        .unwrap()
        .done();

    let dir_100rc1 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000001001))
        .unwrap()
        .done();
    let dir_100 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000001000))
        .unwrap()
        .done();
    let dir_100post1 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000001002))
        .unwrap()
        .done();
    let dir_110 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000001100))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    builder.snp_arc(snp, rel_100rc1, b"releases/1.0rc1");
    builder.snp_arc(snp, rel_100, b"releases/1.0");
    builder.snp_arc(snp, rel_100post1, b"releases/1.0.post1");
    builder.snp_arc(snp, rel_110, b"releases/1.1");

    builder.arc(rel_100rc1, dir_100rc1);
    builder.arc(rel_100, dir_100);
    builder.arc(rel_100post1, dir_100post1);
    builder.arc(rel_110, dir_110);

    MultiVersionGraph {
        graph: builder.done().unwrap(),
        origin_url: origin_url.to_string(),
        versions: HashMap::from([
            (
                "1.0rc1".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000001001),
            ),
            (
                "1.0".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000001000),
            ),
            (
                "1.0.post1".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000001002),
            ),
            (
                "1.1".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000001100),
            ),
        ]),
    }
}

#[test]
fn test_list_affected_versions_no_ranges() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: None,
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-001.json",
        &Ecosystem::Npm,
        affected,
    )?;

    assert_eq!(result, vec![]);

    Ok(())
}

#[test]
fn test_list_affected_versions_empty_ranges() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-001.json",
        &Ecosystem::Npm,
        affected,
    )?;

    assert_eq!(result, vec![]);

    Ok(())
}

#[test]
fn test_list_affected_versions_pypi_pep440_rc_ordering() -> Result<()> {
    let graph = create_pypi_pep440_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(graph.mapped_version("1.0rc1")),
                SwhEvent::Fixed(graph.mapped_version("1.0")),
            ],
            version_type: VersionType::Pep440,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-PEP440.json",
        &Ecosystem::PyPI,
        affected,
    )?;

    assert_eq!(result, vec![graph.version("1.0rc1")]);

    Ok(())
}

#[test]
fn test_list_affected_versions_range_with_no_events() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-001.json",
        &Ecosystem::Npm,
        affected,
    )?;

    assert_eq!(result, vec![]);

    Ok(())
}

#[test]
fn test_list_affected_versions_introduced_zero_and_fixed() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    // all versions before 1.2.0
    let expected = vec![
        graph.version("0.9.0"),
        graph.version("0.9.5"),
        graph.version("1.0.0"),
        graph.version("1.0.5"),
        graph.version("1.1.0"),
        graph.version("1.1.5"),
    ];

    let cases = vec![
        vec![
            SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
            SwhEvent::Fixed(graph.mapped_version("1.2.0")),
        ],
        vec![
            SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
            SwhEvent::Introduced(graph.mapped_version("1.0.0")),
            SwhEvent::Fixed(graph.mapped_version("1.2.0")),
        ],
        vec![
            SwhEvent::Introduced(graph.mapped_version("1.0.0")),
            SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
            SwhEvent::Fixed(graph.mapped_version("1.2.0")),
        ],
    ];

    for (case_index, events) in cases.into_iter().enumerate() {
        let affected = SwhAffected {
            origins: vec![graph.origin_url.clone()],
            ranges: Some(vec![SwhRange {
                events,
                version_type: VersionType::Semver,
            }]),
            versions: (),
        };

        let result = list_affected_versions(
            &graph.graph,
            &stats,
            &format!("TEST-001-{case_index}.json"),
            &Ecosystem::Npm,
            affected,
        )?;

        assert_eq!(result, expected);
    }

    Ok(())
}

#[test]
fn test_list_affected_versions_introduced_and_fixed() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    // versions >= 1.0.0 and < 1.2.0
    let expected = vec![
        graph.version("1.0.0"),
        graph.version("1.0.5"),
        graph.version("1.1.0"),
        graph.version("1.1.5"),
    ];

    let cases = vec![
        vec![
            SwhEvent::Introduced(graph.mapped_version("1.0.0")),
            SwhEvent::Fixed(graph.mapped_version("1.2.0")),
        ],
        vec![
            SwhEvent::Introduced(graph.mapped_version("1.0.0")),
            SwhEvent::Introduced(graph.mapped_version("1.1.0")),
            SwhEvent::Fixed(graph.mapped_version("1.2.0")),
        ],
    ];

    for (case_index, events) in cases.into_iter().enumerate() {
        let affected = SwhAffected {
            origins: vec![graph.origin_url.clone()],
            ranges: Some(vec![SwhRange {
                events,
                version_type: VersionType::Semver,
            }]),
            versions: (),
        };

        let result = list_affected_versions(
            &graph.graph,
            &stats,
            &format!("TEST-002-{case_index}.json"),
            &Ecosystem::Npm,
            affected,
        )?;

        assert_eq!(result, expected);
    }

    Ok(())
}

#[test]
fn test_list_affected_versions_only_introduced() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![SwhEvent::Introduced(graph.mapped_version("1.1.0"))],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-003.json",
        &Ecosystem::Npm,
        affected,
    )?;

    // all versions >= 1.1.0
    let expected = vec![
        graph.version("1.1.0"),
        graph.version("1.1.5"),
        graph.version("1.2.0"),
        graph.version("1.2.5"),
        graph.version("2.0.0"),
    ];
    assert_eq!(result, expected);

    Ok(())
}

#[test]
fn test_list_affected_versions_introduced_fixed_introduced_fixed() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let expected = vec![
        graph.version("0.9.0"),
        graph.version("0.9.5"),
        graph.version("1.2.0"),
        graph.version("1.2.5"),
    ];

    let cases = vec![
        vec![
            SwhEvent::Introduced(graph.mapped_version("0.9.0")),
            SwhEvent::Fixed(graph.mapped_version("1.0.0")),
            SwhEvent::Introduced(graph.mapped_version("1.2.0")),
            SwhEvent::Fixed(graph.mapped_version("2.0.0")),
        ],
        vec![
            SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
            SwhEvent::Fixed(graph.mapped_version("1.0.0")),
            SwhEvent::Introduced(graph.mapped_version("1.2.0")),
            SwhEvent::Fixed(graph.mapped_version("2.0.0")),
        ],
    ];

    for (case_index, events) in cases.into_iter().enumerate() {
        let affected = SwhAffected {
            origins: vec![graph.origin_url.clone()],
            ranges: Some(vec![SwhRange {
                events,
                version_type: VersionType::Semver,
            }]),
            versions: (),
        };

        let result = list_affected_versions(
            &graph.graph,
            &stats,
            &format!("TEST-002-intervals-{case_index}.json"),
            &Ecosystem::Npm,
            affected,
        )?;

        assert_eq!(result, expected);
    }

    Ok(())
}

#[test]
fn test_list_affected_versions_with_last_affected() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::LastAffected(graph.mapped_version("1.1.0")),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-004.json",
        &Ecosystem::Npm,
        affected,
    )?;

    // all versions <= 1.1.0
    let expected = vec![
        graph.version("0.9.0"),
        graph.version("0.9.5"),
        graph.version("1.0.0"),
        graph.version("1.0.5"),
        graph.version("1.1.0"),
    ];
    assert_eq!(result, expected);

    Ok(())
}

/// When the fixed version is not found, should treat it as if all versions are affected
#[test]
fn test_list_affected_versions_with_version_not_found() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::VersionNotFound(VersionSearchInfo {
                    version: "99.0.0".to_string(),
                    tried_origin_urls: vec![graph.origin_url.clone()],
                    branch_names: vec![],
                })),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-007.json",
        &Ecosystem::Npm,
        affected,
    )?;

    let expected = vec![
        graph.version("0.9.0"),
        graph.version("0.9.5"),
        graph.version("1.0.0"),
        graph.version("1.0.5"),
        graph.version("1.1.0"),
        graph.version("1.1.5"),
        graph.version("1.2.0"),
        graph.version("1.2.5"),
        graph.version("2.0.0"),
    ];
    assert_eq!(result, expected);

    Ok(())
}

#[test]
fn test_list_affected_versions_with_package_not_found() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::PackageNotFound),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-008.json",
        &Ecosystem::Npm,
        affected,
    )?;

    assert_eq!(result, vec![]);

    Ok(())
}

#[test]
fn test_list_affected_versions_git_range() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::FromGit(
                    swhid!(swh:1:rev:0000000000000000000000000000000000000101),
                )),
                SwhEvent::Fixed(VersionInSwh::FromGit(
                    swhid!(swh:1:rev:0000000000000000000000000000000000000121),
                )),
            ],
            version_type: VersionType::Git,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-006.json",
        &Ecosystem::Npm,
        affected,
    )?;

    // Git ranges are ignored - they're better handled by vuln2commit_parquet
    // which is designed for large sets of commits
    assert_eq!(result, vec![]);

    Ok(())
}

// Helper to create a graph with various version formats (v prefix, no slash, etc.)
fn create_varied_version_graph() -> (BuiltGraph, usize) {
    let mut builder = GraphBuilder::default();

    let origin_url = "https://example.com/package";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000020))
        .unwrap()
        .done();

    // Create releases with different branch name formats
    // Version 1.0.0 → 100
    let rel_100 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000100))
        .unwrap()
        .done();
    // Version 2.0.0 → 200
    let rel_200 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000200))
        .unwrap()
        .done();
    // Version 3.0.0 → 300
    let rel_300 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000300))
        .unwrap()
        .done();

    let dir_100 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000100))
        .unwrap()
        .done();
    let dir_200 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000200))
        .unwrap()
        .done();
    let dir_300 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000300))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    // Different formats: v prefix, no slash, refs/tags prefix
    builder.snp_arc(snp, rel_100, b"v1.0.0");
    builder.snp_arc(snp, rel_200, b"2.0.0");
    builder.snp_arc(snp, rel_300, b"refs/tags/3.0.0");

    builder.arc(rel_100, dir_100);
    builder.arc(rel_200, dir_200);
    builder.arc(rel_300, dir_300);

    (builder.done().unwrap(), origin)
}

fn create_linux_version_graph() -> (BuiltGraph, usize) {
    let mut builder = GraphBuilder::default();

    let origin_url = "https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000030))
        .unwrap()
        .done();

    // Linux versions: 5.4.0 → 540, 5.5.0 → 550, 5.10.0 → 5100
    let rel_540 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000540))
        .unwrap()
        .done();
    let rel_550 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000550))
        .unwrap()
        .done();
    let rel_5100 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000005100))
        .unwrap()
        .done();

    let rel_6000 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000006000))
        .unwrap()
        .done();
    let rel_6100_rc1 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000006101))
        .unwrap()
        .done();
    let rel_6100_rc2 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000006102))
        .unwrap()
        .done();
    let rel_6100 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000006100))
        .unwrap()
        .done();

    let dir_540 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000540))
        .unwrap()
        .done();
    let dir_550 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000550))
        .unwrap()
        .done();
    let dir_5100 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000005100))
        .unwrap()
        .done();

    let dir_6000 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000006000))
        .unwrap()
        .done();
    let dir_6100_rc1 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000006101))
        .unwrap()
        .done();
    let dir_6100_rc2 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000006102))
        .unwrap()
        .done();
    let dir_6100 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000006100))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    // Linux tags may omit trailing .0 for X.Y.0
    builder.snp_arc(snp, rel_540, b"refs/tags/v5.4");
    builder.snp_arc(snp, rel_550, b"refs/tags/v5.5");
    builder.snp_arc(snp, rel_5100, b"refs/tags/v5.10.0");
    builder.snp_arc(snp, rel_6000, b"refs/tags/v6.0.0");
    builder.snp_arc(snp, rel_6100_rc1, b"refs/tags/v6.1.0-rc1");
    builder.snp_arc(snp, rel_6100_rc2, b"refs/tags/v6.1.0-rc2");
    builder.snp_arc(snp, rel_6100, b"refs/tags/v6.1.0");

    builder.arc(rel_540, dir_540);
    builder.arc(rel_550, dir_550);
    builder.arc(rel_5100, dir_5100);
    builder.arc(rel_6000, dir_6000);
    builder.arc(rel_6100_rc1, dir_6100_rc1);
    builder.arc(rel_6100_rc2, dir_6100_rc2);
    builder.arc(rel_6100, dir_6100);

    (builder.done().unwrap(), origin)
}

#[test]
fn test_list_affected_versions_with_v_prefix() -> Result<()> {
    let origin_url = "https://example.com/package";
    let (graph, _origin) = create_varied_version_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.to_string()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "2.0.0".to_string(),
                        origin_url: origin_url.to_string(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"2.0.0".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000000200))
                            .unwrap(),
                    },
                    version_type: VersionType::Semver,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-009.json", &Ecosystem::Linux, affected)?;

    // Should include v1.0.0 (matched despite "v" prefix)
    let expected = vec![SwhVersion {
        original_version: Some("1.0.0".to_string()),
        branch_name: Some("v1.0.0".to_string()),
        swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000100),
    }];
    assert_eq!(result, expected);

    Ok(())
}

#[test]
fn test_list_affected_versions_without_prefix() -> Result<()> {
    let origin_url = "https://example.com/package";
    let (graph, _origin) = create_varied_version_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.to_string()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "2.0.0".to_string(),
                        origin_url: origin_url.to_string(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"2.0.0".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000000200))
                            .unwrap(),
                    },
                    version_type: VersionType::Semver,
                    vcs: vec![],
                })),
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "3.0.0".to_string(),
                        origin_url: origin_url.to_string(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"refs/tags/3.0.0".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000000300))
                            .unwrap(),
                    },
                    version_type: VersionType::Semver,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-010.json", &Ecosystem::Linux, affected)?;

    // Should include 2.0.0 (no prefix in branch name)
    let expected = vec![SwhVersion {
        original_version: Some("2.0.0".to_string()),
        branch_name: Some("2.0.0".to_string()),
        swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000200),
    }];
    assert_eq!(result, expected);

    Ok(())
}

#[test]
fn test_list_affected_versions_refs_tags_prefix() -> Result<()> {
    let origin_url = "https://example.com/package";
    let (graph, _origin) = create_varied_version_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.to_string()],
        ranges: Some(vec![SwhRange {
            events: vec![SwhEvent::Introduced(VersionInSwh::MappedFromVersion(
                VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "3.0.0".to_string(),
                        origin_url: origin_url.to_string(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"refs/tags/3.0.0".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000000300))
                            .unwrap(),
                    },
                    version_type: VersionType::Semver,
                    vcs: vec![],
                },
            ))],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-011.json", &Ecosystem::Linux, affected)?;

    // Should include 3.0.0 (matched despite refs/tags/ prefix)
    let expected = vec![SwhVersion {
        original_version: Some("3.0.0".to_string()),
        branch_name: Some("refs/tags/3.0.0".to_string()),
        swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000300),
    }];
    assert_eq!(result, expected);

    Ok(())
}

#[test]
fn test_list_affected_versions_linux_omitted_zero() -> Result<()> {
    let origin_url = "https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/";
    let (graph, _origin) = create_linux_version_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.to_string()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                // OSV reports 5.5.0 but Linux tags it as v5.5
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "5.5.0".to_string(),
                        origin_url: origin_url.to_string(),
                        fuzzy_branch_name_match: true, // fuzzy because .0 was stripped
                        branch_name: b"refs/tags/v5.5".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000000550))
                            .unwrap(),
                    },
                    version_type: VersionType::Linux,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Linux,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-012.json", &Ecosystem::Linux, affected)?;

    // Should include v5.4 (matched even though OSV says 5.4.0)
    let expected = vec![SwhVersion {
        original_version: Some("5.4".to_string()),
        branch_name: Some("refs/tags/v5.4".to_string()),
        swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000540),
    }];
    assert_eq!(result, expected);

    Ok(())
}

#[test]
fn test_list_affected_versions_linux_rc_versions() -> Result<()> {
    let origin_url = "https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git/";
    let (graph, _origin) = create_linux_version_graph();
    let stats = Stats::default();

    let cases = vec![
        (
            "6.1.0",
            b"refs/tags/v6.1.0".to_vec(),
            swhid!(swh:1:rel:0000000000000000000000000000000000006100),
            vec![
                SwhVersion {
                    original_version: Some("5.4".to_string()),
                    branch_name: Some("refs/tags/v5.4".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000540),
                },
                SwhVersion {
                    original_version: Some("5.5".to_string()),
                    branch_name: Some("refs/tags/v5.5".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000550),
                },
                SwhVersion {
                    original_version: Some("5.10.0".to_string()),
                    branch_name: Some("refs/tags/v5.10.0".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000005100),
                },
                SwhVersion {
                    original_version: Some("6.0.0".to_string()),
                    branch_name: Some("refs/tags/v6.0.0".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000006000),
                },
                SwhVersion {
                    original_version: Some("6.1.0-rc1".to_string()),
                    branch_name: Some("refs/tags/v6.1.0-rc1".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000006101),
                },
                SwhVersion {
                    original_version: Some("6.1.0-rc2".to_string()),
                    branch_name: Some("refs/tags/v6.1.0-rc2".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000006102),
                },
            ],
        ),
        (
            "6.1.0-rc2",
            b"refs/tags/v6.1.0-rc2".to_vec(),
            swhid!(swh:1:rel:0000000000000000000000000000000000006102),
            vec![
                SwhVersion {
                    original_version: Some("5.4".to_string()),
                    branch_name: Some("refs/tags/v5.4".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000540),
                },
                SwhVersion {
                    original_version: Some("5.5".to_string()),
                    branch_name: Some("refs/tags/v5.5".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000550),
                },
                SwhVersion {
                    original_version: Some("5.10.0".to_string()),
                    branch_name: Some("refs/tags/v5.10.0".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000005100),
                },
                SwhVersion {
                    original_version: Some("6.0.0".to_string()),
                    branch_name: Some("refs/tags/v6.0.0".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000006000),
                },
                SwhVersion {
                    original_version: Some("6.1.0-rc1".to_string()),
                    branch_name: Some("refs/tags/v6.1.0-rc1".to_string()),
                    swhid: swhid!(swh:1:rel:0000000000000000000000000000000000006101),
                },
            ],
        ),
    ];

    for (case_index, (fixed_version, fixed_branch_name, fixed_swhid, expected)) in
        cases.into_iter().enumerate()
    {
        let affected = SwhAffected {
            origins: vec![origin_url.to_string()],
            ranges: Some(vec![SwhRange {
                events: vec![
                    SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                    SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                        package_version: VersionMatch {
                            version_name: fixed_version.to_string(),
                            origin_url: origin_url.to_string(),
                            fuzzy_branch_name_match: false,
                            branch_name: fixed_branch_name,
                            node: graph.properties().node_id(fixed_swhid).unwrap(),
                        },
                        version_type: VersionType::Linux,
                        vcs: vec![],
                    })),
                ],
                version_type: VersionType::Linux,
            }]),
            versions: (),
        };

        let result = list_affected_versions(
            &graph,
            &stats,
            &format!("TEST-012-linux-rc-{case_index}.json"),
            &Ecosystem::Linux,
            affected,
        )?;

        assert_eq!(result, expected);
    }

    Ok(())
}

#[test]
fn test_list_affected_versions_mixed_formats() -> Result<()> {
    let origin_url = "https://example.com/package";
    let (graph, _origin) = create_varied_version_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.to_string()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "3.0.0".to_string(),
                        origin_url: origin_url.to_string(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"refs/tags/3.0.0".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000000300))
                            .unwrap(),
                    },
                    version_type: VersionType::Semver,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-013.json", &Ecosystem::Linux, affected)?;

    // Should include all versions before 3.0.0, regardless of their branch name format
    let expected = vec![
        SwhVersion {
            original_version: Some("1.0.0".to_string()),
            branch_name: Some("v1.0.0".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000100),
        },
        SwhVersion {
            original_version: Some("2.0.0".to_string()),
            branch_name: Some("2.0.0".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000200),
        },
    ];
    assert_eq!(result, expected);

    Ok(())
}

fn create_debian_firefox_esr_graph() -> (BuiltGraph, String) {
    let mut builder = GraphBuilder::default();

    let origin_url = "deb://Debian/packages/firefox-esr";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000040))
        .unwrap()
        .done();

    // Firefox ESR versions
    let rel_11511 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000011511))
        .unwrap()
        .done();
    let rel_11512 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000011512))
        .unwrap()
        .done();
    let rel_11513 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000011513))
        .unwrap()
        .done();
    let rel_11514 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000011514))
        .unwrap()
        .done();
    let rel_11515 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000011515))
        .unwrap()
        .done();

    let dir_11511 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000011511))
        .unwrap()
        .done();
    let dir_11512 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000011512))
        .unwrap()
        .done();
    let dir_11513 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000011513))
        .unwrap()
        .done();
    let dir_11514 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000011514))
        .unwrap()
        .done();
    let dir_11515 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000011515))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    builder.snp_arc(snp, rel_11511, b"debian/115.11.0esr-1~deb12u1");
    builder.snp_arc(snp, rel_11512, b"debian/115.12.0esr-1~deb12u1");
    builder.snp_arc(snp, rel_11513, b"debian/115.13.0esr-1~deb12u1");
    builder.snp_arc(snp, rel_11514, b"debian/115.14.0esr-1~deb99u1");
    builder.snp_arc(snp, rel_11515, b"debian/115.15.0esr-1~deb12u1");

    builder.arc(rel_11511, dir_11511);
    builder.arc(rel_11512, dir_11512);
    builder.arc(rel_11513, dir_11513);
    builder.arc(rel_11514, dir_11514);
    builder.arc(rel_11515, dir_11515);

    (builder.done().unwrap(), origin_url.to_string())
}

#[test]
fn test_list_affected_versions_with_firefox_esr_version() -> Result<()> {
    let (graph, origin_url) = create_debian_firefox_esr_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "115.14.0esr-1~deb12u1".to_string(),
                        origin_url: origin_url.clone(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"debian/115.14.0esr-1~deb99u1".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000011514))
                            .unwrap(),
                    },
                    version_type: VersionType::Dpkg,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Dpkg,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-014.json", &Ecosystem::Linux, affected)?;

    let expected = vec![
        SwhVersion {
            original_version: Some("115.11.0esr-1~deb12u1".to_string()),
            branch_name: Some("debian/115.11.0esr-1~deb12u1".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000011511),
        },
        SwhVersion {
            original_version: Some("115.12.0esr-1~deb12u1".to_string()),
            branch_name: Some("debian/115.12.0esr-1~deb12u1".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000011512),
        },
        SwhVersion {
            original_version: Some("115.13.0esr-1~deb12u1".to_string()),
            branch_name: Some("debian/115.13.0esr-1~deb12u1".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000011513),
        },
    ];
    assert_eq!(result, expected);

    Ok(())
}

fn create_tzdata_graph() -> (BuiltGraph, String) {
    let mut builder = GraphBuilder::default();

    let origin_url = "deb://Debian/packages/tzdata";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000050))
        .unwrap()
        .done();

    let rel_20180315 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000020180315))
        .unwrap()
        .done();
    let rel_20180419 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000020180419))
        .unwrap()
        .done();
    let rel_20180518 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000020180518))
        .unwrap()
        .done();
    let rel_20180622 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000020180622))
        .unwrap()
        .done();
    let rel_20180726 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000020180726))
        .unwrap()
        .done();

    let dir_20180315 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000020180315))
        .unwrap()
        .done();
    let dir_20180419 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000020180419))
        .unwrap()
        .done();
    let dir_20180518 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000020180518))
        .unwrap()
        .done();
    let dir_20180622 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000020180622))
        .unwrap()
        .done();
    let dir_20180726 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000020180726))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    builder.snp_arc(snp, rel_20180315, b"debian/20180315-1");
    builder.snp_arc(snp, rel_20180419, b"debian/20180419-1");
    builder.snp_arc(snp, rel_20180518, b"debian/20180518-1");
    builder.snp_arc(snp, rel_20180622, b"debian/20180622-1");
    builder.snp_arc(snp, rel_20180726, b"debian/20180726-1");

    builder.arc(rel_20180315, dir_20180315);
    builder.arc(rel_20180419, dir_20180419);
    builder.arc(rel_20180518, dir_20180518);
    builder.arc(rel_20180622, dir_20180622);
    builder.arc(rel_20180726, dir_20180726);

    (builder.done().unwrap(), origin_url.to_string())
}

#[test]
fn test_list_affected_versions_with_date_based_version() -> Result<()> {
    let (graph, origin_url) = create_tzdata_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "20180622-1".to_string(),
                        origin_url: origin_url.clone(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"debian/20180622-1".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000020180622))
                            .unwrap(),
                    },
                    version_type: VersionType::Dpkg,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Dpkg,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-015.json", &Ecosystem::Linux, affected)?;

    let expected = vec![
        SwhVersion {
            original_version: Some("20180315-1".to_string()),
            branch_name: Some("debian/20180315-1".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000020180315),
        },
        SwhVersion {
            original_version: Some("20180419-1".to_string()),
            branch_name: Some("debian/20180419-1".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000020180419),
        },
        SwhVersion {
            original_version: Some("20180518-1".to_string()),
            branch_name: Some("debian/20180518-1".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000020180518),
        },
    ];
    assert_eq!(result, expected);

    Ok(())
}

fn create_debian_backport_graph() -> (BuiltGraph, String) {
    let mut builder = GraphBuilder::default();

    let origin_url = "deb://Debian/packages/golang-1.17";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000060))
        .unwrap()
        .done();

    let rel_1170 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000001170))
        .unwrap()
        .done();
    let rel_1171 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000001171))
        .unwrap()
        .done();
    let rel_1172 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000001172))
        .unwrap()
        .done();
    let rel_1173 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000001173))
        .unwrap()
        .done();

    let dir_1170 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000001170))
        .unwrap()
        .done();
    let dir_1171 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000001171))
        .unwrap()
        .done();
    let dir_1172 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000001172))
        .unwrap()
        .done();
    let dir_1173 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000001173))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    builder.snp_arc(snp, rel_1170, b"debian/1.17.0-1~bpo11+1");
    builder.snp_arc(snp, rel_1171, b"debian/1.17.1-1~bpo11+1");
    builder.snp_arc(snp, rel_1172, b"debian/1.17.2-1~bpo11+1");
    builder.snp_arc(snp, rel_1173, b"debian/1.17.3-1~bpo11+1");

    builder.arc(rel_1170, dir_1170);
    builder.arc(rel_1171, dir_1171);
    builder.arc(rel_1172, dir_1172);
    builder.arc(rel_1173, dir_1173);

    (builder.done().unwrap(), origin_url.to_string())
}

#[test]
fn test_list_affected_versions_with_backport_version() -> Result<()> {
    let (graph, origin_url) = create_debian_backport_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "1.17.2-1~bpo11+1".to_string(),
                        origin_url: origin_url.clone(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"debian/1.17.2-1~bpo11+1".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000001172))
                            .unwrap(),
                    },
                    version_type: VersionType::Dpkg,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Dpkg,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-016.json", &Ecosystem::Linux, affected)?;

    let expected = vec![
        SwhVersion {
            original_version: Some("1.17.0-1~bpo11+1".to_string()),
            branch_name: Some("debian/1.17.0-1~bpo11+1".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000001170),
        },
        SwhVersion {
            original_version: Some("1.17.1-1~bpo11+1".to_string()),
            branch_name: Some("debian/1.17.1-1~bpo11+1".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000001171),
        },
    ];
    assert_eq!(result, expected);

    Ok(())
}

fn create_dfsg_graph() -> (BuiltGraph, String) {
    let mut builder = GraphBuilder::default();

    let origin_url = "deb://Debian/packages/libfoo";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000070))
        .unwrap()
        .done();

    let rel_30 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000030))
        .unwrap()
        .done();
    let rel_31 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000031))
        .unwrap()
        .done();
    let rel_32 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000032))
        .unwrap()
        .done();
    let rel_33 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000033))
        .unwrap()
        .done();

    let dir_30 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000030))
        .unwrap()
        .done();
    let dir_31 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000031))
        .unwrap()
        .done();
    let dir_32 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000032))
        .unwrap()
        .done();
    let dir_33 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000033))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    builder.snp_arc(snp, rel_30, b"debian/3.0+dfsg-2");
    builder.snp_arc(snp, rel_31, b"debian/3.1+dfsg-8+deb10u4");
    builder.snp_arc(snp, rel_32, b"debian/3.2+dfsg-1");
    builder.snp_arc(snp, rel_33, b"debian/3.3+dfsg-1");

    builder.arc(rel_30, dir_30);
    builder.arc(rel_31, dir_31);
    builder.arc(rel_32, dir_32);
    builder.arc(rel_33, dir_33);

    (builder.done().unwrap(), origin_url.to_string())
}

#[test]
fn test_list_affected_versions_with_dfsg_version() -> Result<()> {
    let (graph, origin_url) = create_dfsg_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "3.2+dfsg-1".to_string(),
                        origin_url: origin_url.clone(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"debian/3.2+dfsg-1".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000000032))
                            .unwrap(),
                    },
                    version_type: VersionType::Dpkg,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Dpkg,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-017.json", &Ecosystem::Linux, affected)?;

    let expected = vec![
        SwhVersion {
            original_version: Some("3.0+dfsg-2".to_string()),
            branch_name: Some("debian/3.0+dfsg-2".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000030),
        },
        SwhVersion {
            original_version: Some("3.1+dfsg-8+deb10u4".to_string()),
            branch_name: Some("debian/3.1+dfsg-8+deb10u4".to_string()),
            swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000031),
        },
    ];
    assert_eq!(result, expected);

    Ok(())
}

#[test]
fn test_list_affected_versions_first_fixed_without_introduced() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![SwhEvent::Fixed(graph.mapped_version("1.2.0"))],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-022.json",
        &Ecosystem::Npm,
        affected,
    )?;

    assert_eq!(result, vec![]);
    assert_eq!(
        stats
            .fixed_event_without_corresponding_introduced
            .into_iter()
            .map(|(key, value)| (key, value.into_inner()))
            .collect::<Vec<_>>(),
        vec![("Npm".to_owned(), 1)]
    );

    Ok(())
}

#[test]
fn test_list_affected_versions_consecutive_fixed_without_introduced() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(graph.mapped_version("1.0.0")),
                SwhEvent::Fixed(graph.mapped_version("1.1.0")),
                SwhEvent::Fixed(graph.mapped_version("1.2.0")),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-023.json",
        &Ecosystem::Npm,
        affected,
    )?;

    assert_eq!(result, vec![graph.version("1.0.0"), graph.version("1.0.5")]);
    assert_eq!(
        stats
            .fixed_event_without_corresponding_introduced
            .into_iter()
            .map(|(key, value)| (key, value.into_inner()))
            .collect::<Vec<_>>(),
        vec![("Npm".to_owned(), 1)]
    );

    Ok(())
}

#[test]
fn test_list_affected_versions_unsorted_introduced_events() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                // Unsorted: 1.1.0 before 1.0.0
                SwhEvent::Introduced(graph.mapped_version("1.1.0")),
                SwhEvent::Introduced(graph.mapped_version("1.0.0")),
                SwhEvent::Fixed(graph.mapped_version("1.2.0")),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-026.json",
        &Ecosystem::Npm,
        affected,
    )?;

    assert_eq!(result, vec![]);
    assert_eq!(
        stats
            .unsorted_events
            .into_iter()
            .map(|(key, value)| (key, value.into_inner()))
            .collect::<Vec<_>>(),
        vec![("Npm".to_owned(), 1)]
    );

    Ok(())
}

#[test]
fn test_list_affected_versions_unsorted_fixed_events() -> Result<()> {
    let graph = create_multiversion_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(graph.mapped_version("1.0.0")),
                // Unsorted: 2.0.0 before 1.2.0
                SwhEvent::Fixed(graph.mapped_version("2.0.0")),
                SwhEvent::Fixed(graph.mapped_version("1.2.0")),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-027.json",
        &Ecosystem::Npm,
        affected,
    )?;

    assert_eq!(result, vec![]);
    assert_eq!(
        stats
            .unsorted_events
            .into_iter()
            .map(|(key, value)| (key, value.into_inner()))
            .collect::<Vec<_>>(),
        vec![("Npm".to_owned(), 1)]
    );

    Ok(())
}

fn create_pypi_pillow_graph() -> MultiVersionGraph {
    let mut builder = GraphBuilder::default();

    let origin_url = "https://pypi.org/project/Pillow/";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    let snp = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000002020))
        .unwrap()
        .done();

    // Create releases for various Pillow versions
    // Each file type (.tar.gz, .zip) gets its own release object
    let rel_253 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000253))
        .unwrap()
        .done();
    let rel_310rc1_tar = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000031011))
        .unwrap()
        .done();
    let rel_310rc1_zip = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000031012))
        .unwrap()
        .done();
    let rel_310_tar = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000031001))
        .unwrap()
        .done();
    let rel_310_zip = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000031002))
        .unwrap()
        .done();
    let rel_311_tar = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000031101))
        .unwrap()
        .done();
    let rel_311_zip = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000031102))
        .unwrap()
        .done();
    let rel_400 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000004000))
        .unwrap()
        .done();

    // All releases of the same version point to the same directory
    let dir_253 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000253))
        .unwrap()
        .done();
    let dir_310rc1 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000003101))
        .unwrap()
        .done();
    let dir_310 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000003100))
        .unwrap()
        .done();
    let dir_311 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000003110))
        .unwrap()
        .done();
    let dir_400 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000004000))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    // PyPI branch names: some simple, some with filenames (multiple files per version)
    builder.snp_arc(snp, rel_253, b"releases/2.5.3");
    builder.snp_arc(
        snp,
        rel_310rc1_tar,
        b"releases/3.1.0.rc1/Pillow-3.1.0.rc1.tar.gz",
    );
    builder.snp_arc(
        snp,
        rel_310rc1_zip,
        b"releases/3.1.0.rc1/Pillow-3.1.0.rc1.zip",
    );
    builder.snp_arc(snp, rel_310_tar, b"releases/3.1.0/Pillow-3.1.0.tar.gz");
    builder.snp_arc(snp, rel_310_zip, b"releases/3.1.0/Pillow-3.1.0.zip");
    builder.snp_arc(snp, rel_311_tar, b"releases/3.1.1/Pillow-3.1.1.tar.gz");
    builder.snp_arc(snp, rel_311_zip, b"releases/3.1.1/Pillow-3.1.1.zip");
    builder.snp_arc(snp, rel_400, b"releases/4.0.0");

    builder.arc(rel_253, dir_253);
    builder.arc(rel_310rc1_tar, dir_310rc1);
    builder.arc(rel_310rc1_zip, dir_310rc1);
    builder.arc(rel_310_tar, dir_310);
    builder.arc(rel_310_zip, dir_310);
    builder.arc(rel_311_tar, dir_311);
    builder.arc(rel_311_zip, dir_311);
    builder.arc(rel_400, dir_400);

    MultiVersionGraph {
        graph: builder.done().unwrap(),
        origin_url: origin_url.to_string(),
        versions: HashMap::from([
            (
                "2.5.3".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000000253),
            ),
            // Include both .tar.gz and .zip variants for versions that have them
            (
                "3.1.0.rc1-tar".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031011),
            ),
            (
                "3.1.0.rc1-zip".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031012),
            ),
            // Keep canonical names pointing to .tar.gz for backward compatibility
            (
                "3.1.0.rc1".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031011),
            ),
            (
                "3.1.0-tar".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031001),
            ),
            (
                "3.1.0-zip".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031002),
            ),
            (
                "3.1.0".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031001),
            ),
            (
                "3.1.1-tar".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031101),
            ),
            (
                "3.1.1-zip".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031102),
            ),
            (
                "3.1.1".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000031101),
            ),
            (
                "4.0.0".to_string(),
                swhid!(swh:1:rel:0000000000000000000000000000000000004000),
            ),
        ]),
    }
}

#[test]
fn test_list_affected_versions_pypi() -> Result<()> {
    let graph = create_pypi_pillow_graph();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![graph.origin_url.clone()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(graph.mapped_version("2.5.3")),
                SwhEvent::Fixed(graph.mapped_version("3.1.0")),
            ],
            version_type: VersionType::Pep440,
        }]),
        versions: (),
    };

    let result = list_affected_versions(
        &graph.graph,
        &stats,
        "TEST-PYPI-001.json",
        &Ecosystem::PyPI,
        affected,
    )?;

    let expected = vec![
        graph.version("2.5.3"),
        SwhVersion {
            original_version: Some("3.1.0.rc1".to_string()),
            branch_name: Some("releases/3.1.0.rc1/Pillow-3.1.0.rc1.tar.gz".to_string()),
            swhid: graph.swhid_for("3.1.0.rc1-tar"),
        },
        SwhVersion {
            original_version: Some("3.1.0.rc1".to_string()),
            branch_name: Some("releases/3.1.0.rc1/Pillow-3.1.0.rc1.zip".to_string()),
            swhid: graph.swhid_for("3.1.0.rc1-zip"),
        },
    ];
    assert_eq!(result, expected);

    Ok(())
}

#[test]
fn test_list_affected_versions_duplicate_branches_across_snapshots() -> Result<()> {
    let mut builder = GraphBuilder::default();

    let origin_url = "https://www.npmjs.com/package/test-pkg";
    let origin = builder
        .node(SWHID::from_origin_url(origin_url))
        .unwrap()
        .message(origin_url.as_bytes().to_vec())
        .done();

    // Create two snapshots
    let snp1 = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000091))
        .unwrap()
        .done();
    let snp2 = builder
        .node(swhid!(swh:1:snp:0000000000000000000000000000000000000092))
        .unwrap()
        .done();

    let rel_100 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000100))
        .unwrap()
        .done();
    let rel_200 = builder
        .node(swhid!(swh:1:rel:0000000000000000000000000000000000000200))
        .unwrap()
        .done();

    let dir_100 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000100))
        .unwrap()
        .done();
    let dir_200 = builder
        .node(swhid!(swh:1:dir:0000000000000000000000000000000000000200))
        .unwrap()
        .done();

    builder.ori_arc(
        origin,
        snp1,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );
    builder.ori_arc(
        origin,
        snp2,
        VisitStatus::Full,
        /* timestamp */ 1768989569,
    );

    // Both snapshots have the same branches
    builder.snp_arc(snp1, rel_100, b"releases/1.0.0");
    builder.snp_arc(snp1, rel_200, b"releases/2.0.0");
    builder.snp_arc(snp2, rel_100, b"releases/1.0.0"); // Duplicate
    builder.snp_arc(snp2, rel_200, b"releases/2.0.0"); // Duplicate

    builder.arc(rel_100, dir_100);
    builder.arc(rel_200, dir_200);

    let graph = builder.done().unwrap();
    let stats = Stats::default();

    let affected = SwhAffected {
        origins: vec![origin_url.to_string()],
        ranges: Some(vec![SwhRange {
            events: vec![
                SwhEvent::Introduced(VersionInSwh::SinceTheBeginning),
                SwhEvent::Fixed(VersionInSwh::MappedFromVersion(VersionToSwhidMapping {
                    package_version: VersionMatch {
                        version_name: "2.0.0".to_string(),
                        origin_url: origin_url.to_string(),
                        fuzzy_branch_name_match: false,
                        branch_name: b"releases/2.0.0".to_vec(),
                        node: graph
                            .properties()
                            .node_id(swhid!(swh:1:rel:0000000000000000000000000000000000000200))
                            .unwrap(),
                    },
                    version_type: VersionType::Semver,
                    vcs: vec![],
                })),
            ],
            version_type: VersionType::Semver,
        }]),
        versions: (),
    };

    let result =
        list_affected_versions(&graph, &stats, "TEST-019.json", &Ecosystem::Linux, affected)?;

    // Should not have duplicates despite appearing in two snapshots
    let expected = vec![SwhVersion {
        original_version: Some("1.0.0".to_string()),
        branch_name: Some("releases/1.0.0".to_string()),
        swhid: swhid!(swh:1:rel:0000000000000000000000000000000000000100),
    }];
    assert_eq!(result, expected);

    Ok(())
}
