// 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

//! Version detection from package managers

use std::cmp::Ordering;
use std::sync::OnceLock;

use anyhow::{Context, Result, bail};
use chrono::DateTime;
use itertools::Itertools;
use osv::schema::{Ecosystem, Version};
use regex::Regex;
use swh_graph::graph::{SwhGraphWithProperties, SwhLabeledForwardGraph};
use swh_graph::labels::{Branch, Visit};
use swh_graph::{NodeType, SWHID, properties, swhid};
use tracing::{Level, span};
use version_spec::clean_version_string;

use super::versions::{ParsedVersion, VersionType};
use super::{
    Stats, SwhAffected, SwhEvent, SwhVersion, VersionInSwh, VersionSearchInfo,
    increment_by_ecosystem,
};

#[derive(Debug, Clone)]
struct AvailableVersion {
    parsed_version: ParsedVersion,
    original_version: Version,
    branch_name: String,
    swhid: SWHID,
}

/// Extracts a version string from a branch name of unknown ecosystems
///
/// Returns `None` for branches unlikely to be releases.
/// For example `refs/heads/*` are Git branches, which very unlikely to be parsable
/// as a version number. And even if we can it is likely to be a false positive
/// (eg. refs/heads/2.1 would be the branch for development of all 2.1.x versions,
/// and not 2.1.0 itself).
///
/// # Examples
///
/// ```
/// use swh_osv::packages::guess_version_from_branch_name;
///
/// assert_eq!(guess_version_from_branch_name("releases/1.0.0"), Some("1.0.0".to_string()));
/// assert_eq!(guess_version_from_branch_name("releases/v2.1.3"), Some("2.1.3".to_string()));
/// assert_eq!(guess_version_from_branch_name("refs/tags/v5.4"), Some("5.4".to_string()));
///
/// assert_eq!(guess_version_from_branch_name("1.0.0"), Some("1.0.0".to_string()));
/// assert_eq!(guess_version_from_branch_name("v2.1.3"), Some("2.1.3".to_string()));
///
/// // Git branches
/// assert_eq!(guess_version_from_branch_name("refs/heads/main"), None);
/// assert_eq!(guess_version_from_branch_name("refs/heads/2.1"), None);
///
/// // Do not look like a version number
/// assert_eq!(guess_version_from_branch_name("refs/tags/foo.bar"), None);
/// ```
pub fn guess_version_from_branch_name(branch_name: &str) -> Option<String> {
    if branch_name.starts_with("refs/heads/") {
        None
    } else {
        let raw_version = branch_name
            .rsplit_once('/')
            .map(|(_, last_segment)| last_segment)
            .unwrap_or_else(|| branch_name);

        // if there are no digits, ignore
        if !raw_version.chars().any(|c| "0123456789".contains(c)) {
            return None;
        }

        // remove 'v' prefix
        Some(clean_version_string(raw_version))
    }
}

/// Extracts a version string from a branch name
///
/// Falls back to [`guess_version_from_branch_name`] for unsupported ecosystems
pub fn version_from_branch_name(branch_name: &str, ecosystem: &Ecosystem) -> Option<String> {
    match ecosystem {
        Ecosystem::PyPI | Ecosystem::CRAN => {
            // For CRAN/PyPI, parse branches matching "releases/<version>" or "releases/<version>/<filename>"
            static RELEASES_REGEX: OnceLock<Regex> = OnceLock::new();
            let regex = RELEASES_REGEX.get_or_init(|| {
                Regex::new(r"^releases/([^/]+)(?:/.*)?$").expect("releases branch regex is valid")
            });

            let captures = regex.captures(branch_name)?;
            let version_part = captures.get(1)?.as_str();

            // if there are no digits, ignore
            if !version_part.chars().any(|c| "0123456789".contains(c)) {
                return None;
            }

            // remove 'v' prefix
            Some(clean_version_string(version_part))
        }
        _ => guess_version_from_branch_name(branch_name),
    }
}

/// Validates that events are sorted in proper order by version
fn validate_events_sorted(events: &[SwhEvent], version_type: &VersionType) -> Result<()> {
    let mut prev_parsed: Option<ParsedVersion> = None;

    for event in events {
        let version = match event {
            SwhEvent::Introduced(v) => v,
            SwhEvent::Fixed(v) => v,
            SwhEvent::LastAffected(v) => v,
            SwhEvent::Limit(v) => v,
        };

        // Parse the version if possible
        let parsed = parse_event_version(version, version_type)?;

        // Only validate ordering for events with parseable versions
        if let VersionInSwh::MappedFromVersion(current_version) = parsed {
            if let Some(prev_version) = &prev_parsed {
                if current_version.try_cmp(prev_version)? == Ordering::Less {
                    bail!("Events are not sorted: events must be in ascending version order");
                }
            }

            prev_parsed = Some(current_version);
        } else {
            // Special versions (SinceTheBeginning, FromGit, etc.) reset the comparison
            prev_parsed = None;
        }
    }

    Ok(())
}

/// Enumerates all version a [`SwhAffected`] instance covers.
///
/// This ignores Git ranges, which are better handled by [`crate::vuln2commit_parquet`] as they
/// typically over large sets of commits.
pub fn list_affected_versions<G>(
    graph: &G,
    stats: &Stats,
    filename: &str,
    ecosystem: &Ecosystem,
    affected: SwhAffected,
) -> Result<Vec<SwhVersion>>
where
    G: SwhLabeledForwardGraph + SwhGraphWithProperties,
    <G as SwhGraphWithProperties>::Maps: properties::Maps,
    <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
{
    let SwhAffected {
        origins, ranges, ..
    } = affected;

    let Some(ranges) = ranges else {
        return Ok(Vec::new());
    };

    if ranges.is_empty() {
        return Ok(Vec::new());
    }

    let mut affected_versions = Vec::new();
    let mut seen_swhids = rapidhash::RapidHashSet::default();

    for range in ranges {
        let _span = span!(
            Level::INFO,
            "parse range",
            version_type = %format!("{:?}", range.version_type),
            events = %format!("[{}]", range.events.iter().map(|event| {
                let (s, v) = match event {
                    SwhEvent::Introduced(v) => ("introduced", v),
                    SwhEvent::Fixed(v) => ("fixed", v),
                    SwhEvent::LastAffected(v) => ("last_affected", v),
                    SwhEvent::Limit(v) => ("limit", v),
                };
                format!(
                    "{s}({})",
                    match v {
                        VersionInSwh::MappedFromVersion(mapping) => mapping.package_version.version_name.clone(),
                        VersionInSwh::SinceTheBeginning => "0".to_owned(),
                        VersionInSwh::FromGit(swhid) => swhid.to_string(),
                        VersionInSwh::PackageNotFound => "<package not found in SWH>".to_owned(),
                        VersionInSwh::VersionNotFound(info) => format!("{} <not found in SWH>", info.version),
                    }
                )
            }).join(", "))
        )
        .entered();

        if range.events.is_empty() {
            continue;
        }

        if range.version_type == VersionType::Git {
            continue;
        }

        let available_versions =
            list_versions_in_origins(graph, &origins, ecosystem, &range.version_type)?;

        if available_versions.is_empty() {
            continue;
        }

        let mut intervals = Vec::new();

        let mut has_git_event = false;
        let mut has_package_not_found = false;
        for event in &range.events {
            match event.version() {
                VersionInSwh::FromGit(_) => {
                    has_git_event = true;
                    break;
                }
                VersionInSwh::PackageNotFound => {
                    has_package_not_found = true;
                }
                VersionInSwh::SinceTheBeginning
                | VersionInSwh::MappedFromVersion(_)
                | VersionInSwh::VersionNotFound(_) => {}
            }
        }

        if has_git_event {
            continue;
        }

        if has_package_not_found {
            return Ok(Vec::new());
        }

        if validate_events_sorted(&range.events, &range.version_type).is_err() {
            // Happens occasionally from PYSEC. Two of their reports make no sense:
            // * https://github.com/pypa/advisory-database/blob/main/vulns/tryton/PYSEC-2022-43170.yaml#L18-L27
            // * https://github.com/pypa/advisory-database/blob/main/vulns/tryton/PYSEC-2022-43171.yaml
            increment_by_ecosystem(&stats.unsorted_events, ecosystem);
            log::warn!("Skipping range in {filename}, events are not sorted");
            continue;
        }

        let mut current_start = RangeStart::Unset;

        for event in range.events {
            match event {
                SwhEvent::Introduced(version) => {
                    match parse_event_version(&version, &range.version_type)? {
                        VersionInSwh::SinceTheBeginning => {
                            current_start = RangeStart::Beginning;
                        }
                        VersionInSwh::MappedFromVersion(version) => match &current_start {
                            RangeStart::Unset => {
                                current_start = RangeStart::Known(version);
                            }
                            RangeStart::Beginning => {}
                            RangeStart::Known(current_version) => {
                                if version.try_cmp(current_version)? == Ordering::Less {
                                    current_start = RangeStart::Known(version);
                                }
                            }
                        },
                        VersionInSwh::VersionNotFound(v) => {
                            log::debug!(
                                "Introduced version {} not found in {:?}",
                                v.version,
                                v.tried_origin_urls
                            );
                            if !matches!(current_start, RangeStart::Beginning) {
                                current_start = RangeStart::Beginning;
                            }
                        }
                        VersionInSwh::PackageNotFound => {
                            return Ok(Vec::new());
                        }
                        VersionInSwh::FromGit(_) => {
                            current_start = RangeStart::Unset;
                        }
                    }
                }
                SwhEvent::Fixed(version) => {
                    let (end, package_not_found) =
                        range_end_from_event(&version, false, "Fixed", &range.version_type)?;
                    if package_not_found {
                        return Ok(Vec::new());
                    }

                    if matches!(current_start, RangeStart::Unset) {
                        // bogus document. eg. CVE-2024-55881.json defines both
                        // 5.16.0->(6.1.122, 6.6.68) and 6.2.0->6.12.7 as vulnerable.
                        // considering 6.6.68 is already in the second range, I think we can
                        // safely ignore it.
                        // Other known instances: CVE-2024-49949.json, CVE-2024-41006.json, and
                        // CVE-2025-40261.json.
                        increment_by_ecosystem(
                            &stats.fixed_event_without_corresponding_introduced,
                            ecosystem,
                        );
                        log::warn!(
                            "Fixed event without corresponding Introduced event in {filename}"
                        );
                    }

                    intervals.push(RangeInterval {
                        start: current_start.clone(),
                        end,
                    });

                    current_start = RangeStart::Unset;
                }
                SwhEvent::LastAffected(version) => {
                    let (end, package_not_found) =
                        range_end_from_event(&version, true, "LastAffected", &range.version_type)?;
                    if package_not_found {
                        return Ok(Vec::new());
                    }

                    if matches!(current_start, RangeStart::Unset) {
                        bail!("LastAffected event without corresponding Introduced event");
                    }

                    intervals.push(RangeInterval {
                        start: current_start.clone(),
                        end,
                    });

                    current_start = RangeStart::Unset;
                }
                SwhEvent::Limit(version) => {
                    let (end, package_not_found) =
                        range_end_from_event(&version, false, "Limit", &range.version_type)?;
                    if package_not_found {
                        return Ok(Vec::new());
                    }

                    if matches!(current_start, RangeStart::Unset) {
                        bail!("Limit event without corresponding Introduced event");
                    }

                    intervals.push(RangeInterval {
                        start: current_start.clone(),
                        end,
                    });

                    current_start = RangeStart::Unset;
                }
            }
        }

        if !matches!(current_start, RangeStart::Unset) {
            intervals.push(RangeInterval {
                start: current_start,
                end: None,
            });
        }

        if intervals.is_empty() {
            continue;
        }

        for available in available_versions {
            let mut in_range = false;
            for interval in &intervals {
                if version_in_interval(&available.parsed_version, interval).with_context(|| {
                    format!(
                        "Could not check whether {:?} is in {interval:?}",
                        available.parsed_version
                    )
                })? {
                    in_range = true;
                    break;
                }
            }

            if in_range && seen_swhids.insert(available.swhid) {
                affected_versions.push(SwhVersion {
                    original_version: Some(available.original_version),
                    branch_name: Some(available.branch_name),
                    swhid: available.swhid,
                });
            }
        }
    }

    Ok(affected_versions)
}

#[derive(Clone, Debug)]
enum RangeStart {
    Unset,
    Beginning,
    Known(ParsedVersion),
}

#[derive(Debug)]
enum RangeEnd {
    Exclusive(ParsedVersion),
    Inclusive(ParsedVersion),
}

#[derive(Debug)]
struct RangeInterval {
    start: RangeStart,
    end: Option<RangeEnd>,
}

fn parse_event_version(
    version: &VersionInSwh,
    version_type: &VersionType,
) -> Result<VersionInSwh<ParsedVersion>> {
    match version {
        // if found and not git
        VersionInSwh::MappedFromVersion(mapping) => {
            let version_name = &mapping.package_version.version_name;
            let Some(parsed) = ParsedVersion::parse(version_name, version_type)? else {
                return Ok(VersionInSwh::VersionNotFound(VersionSearchInfo {
                    version: version_name.clone(),
                    tried_origin_urls: vec![mapping.package_version.origin_url.clone()],
                    branch_names: Vec::new(),
                }));
            };

            Ok(VersionInSwh::MappedFromVersion(parsed))
        }
        // otherwise, passthrough
        VersionInSwh::SinceTheBeginning => Ok(VersionInSwh::SinceTheBeginning),
        VersionInSwh::FromGit(swhid) => Ok(VersionInSwh::FromGit(*swhid)),
        VersionInSwh::PackageNotFound => Ok(VersionInSwh::PackageNotFound),
        VersionInSwh::VersionNotFound(info) => Ok(VersionInSwh::VersionNotFound(info.clone())),
    }
}

fn version_in_interval(version: &ParsedVersion, interval: &RangeInterval) -> Result<bool> {
    match &interval.start {
        RangeStart::Unset => return Ok(false),
        RangeStart::Beginning => {}
        RangeStart::Known(start) => {
            if version.try_cmp(start)? == Ordering::Less {
                return Ok(false);
            }
        }
    }

    Ok(match &interval.end {
        None => true,
        Some(RangeEnd::Exclusive(end)) => version.try_cmp(end)? == Ordering::Less,
        Some(RangeEnd::Inclusive(end)) => {
            matches!(version.try_cmp(end)?, Ordering::Less | Ordering::Equal)
        }
    })
}

fn range_end_from_event(
    version: &VersionInSwh,
    inclusive: bool,
    label: &str,
    version_type: &VersionType,
) -> Result<(Option<RangeEnd>, bool)> {
    let _span = span!(
        Level::INFO,
        "parse",
        version = %format!("{version:?}"),
        version_type = %format!("{version_type:?}"),
    )
    .entered();

    let parsed = parse_event_version(version, version_type)?;
    Ok(match parsed {
        VersionInSwh::MappedFromVersion(version) => {
            let end = if inclusive {
                RangeEnd::Inclusive(version)
            } else {
                RangeEnd::Exclusive(version)
            };
            (Some(end), false)
        }
        VersionInSwh::SinceTheBeginning => {
            log::info!("{label} event had a beginning marker");
            (None, false)
        }
        VersionInSwh::VersionNotFound(_) | VersionInSwh::FromGit(_) => (None, false),
        VersionInSwh::PackageNotFound => (None, true),
    })
}

/// Returns all unique versions available in the origins, sorted
fn list_versions_in_origins<G>(
    graph: &G,
    origins: &[impl AsRef<str>],
    ecosystem: &Ecosystem,
    version_type: &VersionType,
) -> Result<Vec<AvailableVersion>>
where
    G: SwhLabeledForwardGraph + SwhGraphWithProperties,
    <G as SwhGraphWithProperties>::Maps: properties::Maps,
    <G as SwhGraphWithProperties>::LabelNames: properties::LabelNames,
{
    let mut available_versions = Vec::new();
    let mut seen_versions = rapidhash::RapidHashSet::default();

    for origin_url in origins {
        let origin_url = origin_url.as_ref();
        let Ok(origin_id) = graph
            .properties()
            .node_id(SWHID::from_origin_url(origin_url))
        else {
            log::info!("Unknown origin {origin_url}");
            continue;
        };

        for (snapshot, labels) in graph.untyped_labeled_successors(origin_id) {
            let visit_dates: Vec<_> = labels
                .into_iter()
                .map(|label| Visit::from(label).timestamp())
                .collect();
            let first_visit = *visit_dates.iter().min().expect("first visit");
            let last_visit = *visit_dates.iter().max().expect("last visit");

            let snp_swhid = graph.properties().swhid(snapshot);
            static IGNORE_SNAPSHOTS: &[SWHID] = &[
                // old snapshot of pkg:npm/yui with non-semver versions (eg. 3.6.0pr3)
                swhid!(swh:1:snp:e029ee5d40cfdb1ceb5839f9c96dd2130fa7a3d5),
                // old snapshot of pkg:npm/localeval with non-semver versions (eg. 13.05.29)
                swhid!(swh:1:snp:55c288b85fbcc5dbe546af3723bcd73e1f23986a),
            ];
            if IGNORE_SNAPSHOTS.contains(&snp_swhid) {
                continue;
            }

            let _span = span!(
                Level::INFO,
                "listing snapshot",
                ori = %origin_url,
                snp = %snp_swhid,
                first_visit = %DateTime::from_timestamp(
                    first_visit.try_into().expect("first_visit overflow"), 0
                )
                .expect("first_visit date")
                .date_naive(),
                last_visit = %DateTime::from_timestamp(
                    last_visit.try_into().expect("last_visit overflow"), 0
                )
                .expect("first_visit date")
                .date_naive(),
            )
            .entered();

            for (branch_target, labels) in graph.untyped_labeled_successors(snapshot) {
                let node_type = graph.properties().node_type(branch_target);
                match node_type {
                    NodeType::Release | NodeType::Revision => {}
                    NodeType::Content
                    | NodeType::Directory
                    | NodeType::Origin
                    | NodeType::Snapshot => {
                        log::debug!(
                            "Ignoring snapshot label to unexpected node type {node_type:?}"
                        );
                        continue;
                    }
                }

                for label in labels {
                    let label = Branch::from(label);
                    if !seen_versions.insert((label.label_name_id(), branch_target)) {
                        // already saw this branch in a previous snapshot
                        continue;
                    }
                    let branch_name = graph.properties().label_name(label.label_name_id());
                    let branch_name = String::from_utf8_lossy(&branch_name).to_string();

                    let _span = span!(
                        Level::INFO,
                        "branch",
                        name = %branch_name,
                        target = %graph.properties().swhid(branch_target),
                    )
                    .entered();

                    let Some(original_version) = version_from_branch_name(&branch_name, ecosystem)
                    else {
                        log::debug!("Skipping branch {branch_name}, probably not a release");
                        continue;
                    };

                    let Some(parsed_version) =
                        ParsedVersion::parse(&original_version, version_type)?
                    else {
                        continue;
                    };

                    let swhid = graph.properties().swhid(branch_target);
                    available_versions.push(AvailableVersion {
                        parsed_version,
                        original_version,
                        branch_name,
                        swhid,
                    });
                }
            }
        }
    }

    available_versions.sort_by(|left, right| {
        left.parsed_version
            .try_cmp(&right.parsed_version)
            .expect("Could not sort available versions")
            .then_with(|| left.branch_name.cmp(&right.branch_name))
    });

    Ok(available_versions)
}
