dix_diff/

engine.rs

use std::{
  cmp,
  collections::BTreeMap,
  num::NonZeroUsize,
};

use itertools::EitherOrBoth;

use crate::{
  Version,
  matching::match_version_amounts,
  model::{
    Diff,
    DiffStatus,
    VersionAmount,
    VersionDiff,
  },
  snapshot::{
    Package,
    PackageSnapshot,
  },
  version::VersionChangeOrdering,
};

#[must_use]
pub fn diff_snapshots(
  old: &PackageSnapshot,
  new: &PackageSnapshot,
) -> Vec<Diff> {
  let mut diffs = build_package_diffs(&old.packages, &new.packages);
  canonicalize_diffs(&mut diffs);
  diffs
}

fn build_package_diffs<'a>(
  packages_old: impl IntoIterator<Item = &'a Package>,
  packages_new: impl IntoIterator<Item = &'a Package>,
) -> Vec<Diff> {
  let versions_by_name = collect_package_versions(packages_old, packages_new);
  generate_diffs_from_version_map(versions_by_name)
}

fn canonicalize_diffs(diffs: &mut [Diff]) {
  diffs.sort_by(|left, right| left.name.cmp(&right.name));
}

fn collect_package_versions<'a>(
  old: impl IntoIterator<Item = &'a Package>,
  new: impl IntoIterator<Item = &'a Package>,
) -> BTreeMap<String, PackageVersions> {
  let mut packages = BTreeMap::<String, PackageVersions>::new();
  let mut old_count = 0usize;
  let mut new_count = 0usize;

  for package in old {
    old_count += 1;
    packages
      .entry(package.name.clone())
      .or_default()
      .old
      .add(package.version.clone());
  }

  for package in new {
    new_count += 1;
    packages
      .entry(package.name.clone())
      .or_default()
      .new
      .add(package.version.clone());
  }

  debug_assert_eq!(
    old_count + new_count,
    packages
      .values()
      .map(PackageVersions::total_amount)
      .sum::<usize>(),
  );

  packages
}

#[derive(Default)]
struct PackageVersions {
  old: VersionAmounts,
  new: VersionAmounts,
}

impl PackageVersions {
  fn total_amount(&self) -> usize {
    self.old.total_amount() + self.new.total_amount()
  }
}

#[derive(Default)]
struct VersionAmounts {
  amounts: BTreeMap<Version, NonZeroUsize>,
}

impl VersionAmounts {
  fn add(&mut self, version: Version) {
    self
      .amounts
      .entry(version)
      .and_modify(|amount| *amount = increment_amount(*amount))
      .or_insert(NonZeroUsize::MIN);
  }

  fn is_empty(&self) -> bool {
    self.amounts.is_empty()
  }

  fn get(&self, version: &Version) -> Option<NonZeroUsize> {
    self.amounts.get(version).copied()
  }

  fn contains(&self, version: &Version) -> bool {
    self.amounts.contains_key(version)
  }

  fn iter(&self) -> impl Iterator<Item = (&Version, NonZeroUsize)> {
    self
      .amounts
      .iter()
      .map(|(version, amount)| (version, *amount))
  }

  fn total_amount(&self) -> usize {
    self.amounts.values().map(|amount| amount.get()).sum()
  }
}

fn increment_amount(amount: NonZeroUsize) -> NonZeroUsize {
  amount
    .get()
    .checked_add(1)
    .and_then(NonZeroUsize::new)
    .unwrap_or_else(|| panic!("version amount overflowed usize"))
}

struct VersionChanges {
  diffs:                Vec<VersionDiff>,
  has_omitted_versions: bool,
}

fn collect_version_changes(
  old_versions: &VersionAmounts,
  new_versions: &VersionAmounts,
) -> VersionChanges {
  let mut old_only = Vec::new();
  let mut new_only = Vec::new();
  let mut amount_diffs = Vec::new();
  let mut has_omitted_versions = false;

  for (version, old_amount) in old_versions.iter() {
    match new_versions.get(version) {
      Some(new_amount) if old_amount == new_amount => {
        has_omitted_versions = true;
      },
      Some(new_amount) => {
        amount_diffs.push(VersionDiff::AmountChanged {
          version: version.clone(),
          old_amount,
          new_amount,
        });
      },
      None => old_only.push(VersionAmount::new(version.clone(), old_amount)),
    }
  }

  for (version, new_amount) in new_versions.iter() {
    if !old_versions.contains(version) {
      new_only.push(VersionAmount::new(version.clone(), new_amount));
    }
  }

  let mut diffs = version_diffs(&old_only, &new_only);
  diffs.extend(amount_diffs);

  VersionChanges {
    diffs,
    has_omitted_versions,
  }
}

fn generate_diffs_from_version_map(
  packages: BTreeMap<String, PackageVersions>,
) -> Vec<Diff> {
  let mut result = Vec::with_capacity(packages.len());

  for (name, package_versions) in packages {
    let version_changes =
      collect_version_changes(&package_versions.old, &package_versions.new);

    let status = if version_changes.diffs.is_empty() {
      continue;
    } else if package_versions.old.is_empty() {
      DiffStatus::Added
    } else if package_versions.new.is_empty() {
      DiffStatus::Removed
    } else {
      determine_change_status(&version_changes.diffs)
        .unwrap_or(DiffStatus::Changed)
    };

    result.push(Diff {
      name,
      versions: version_changes.diffs,
      status,
      has_omitted_versions: version_changes.has_omitted_versions,
    });
  }

  result
}

fn version_diffs(
  old_versions: &[VersionAmount],
  new_versions: &[VersionAmount],
) -> Vec<VersionDiff> {
  match_version_amounts(old_versions, new_versions)
    .into_iter()
    .map(|ver_diff| {
      match ver_diff {
        EitherOrBoth::Left(old) => VersionDiff::Removed(old.clone()),
        EitherOrBoth::Right(new) => VersionDiff::Added(new.clone()),
        EitherOrBoth::Both(old, new) => {
          VersionDiff::Changed {
            old: old.clone(),
            new: new.clone(),
          }
        },
      }
    })
    .collect()
}

fn determine_change_status(
  version_diffs: &[VersionDiff],
) -> Option<DiffStatus> {
  let mut saw_upgrade = false;
  let mut saw_downgrade = false;
  let mut saw_changed = false;

  for ver_diff in version_diffs {
    match ver_diff {
      VersionDiff::Removed(_) => saw_downgrade = true,
      VersionDiff::Added(_) => saw_upgrade = true,
      VersionDiff::Changed { old, new } => {
        match old.version.change_ordering(&new.version) {
          VersionChangeOrdering::Ordered(cmp::Ordering::Less) => {
            saw_upgrade = true;
          },
          VersionChangeOrdering::Ordered(cmp::Ordering::Greater) => {
            saw_downgrade = true;
          },
          VersionChangeOrdering::Ordered(cmp::Ordering::Equal)
          | VersionChangeOrdering::Unordered => {
            saw_changed = true;
          },
        }
      },
      VersionDiff::AmountChanged { .. } => {
        saw_changed = true;
      },
    }
    if saw_upgrade && saw_downgrade {
      break;
    }
  }

  match (saw_upgrade, saw_downgrade, saw_changed) {
    (true, true, _) => Some(DiffStatus::Mixed),
    (true, false, _) => Some(DiffStatus::Upgraded),
    (false, true, _) => Some(DiffStatus::Downgraded),
    (false, false, true) => Some(DiffStatus::Changed),
    (false, false, false) => None,
  }
}

#[cfg(test)]
mod tests {
  use std::{
    collections::{
      BTreeMap,
      HashSet,
    },
    num::NonZeroUsize,
  };

  use super::*;

  fn nonzero(amount: usize) -> NonZeroUsize {
    NonZeroUsize::new(amount)
      .unwrap_or_else(|| panic!("test version amount must be nonzero"))
  }

  fn version_amount(version: &str, amount: usize) -> VersionAmount {
    VersionAmount::new(version, nonzero(amount))
  }

  fn package_versions(old: &[&str], new: &[&str]) -> PackageVersions {
    let mut versions = PackageVersions::default();
    for version in old {
      versions.old.add(Version::new(*version));
    }
    for version in new {
      versions.new.add(Version::new(*version));
    }
    versions
  }

  fn version_map(
    name: &str,
    old: &[&str],
    new: &[&str],
  ) -> BTreeMap<String, PackageVersions> {
    let mut packages = BTreeMap::new();
    packages.insert(name.to_owned(), package_versions(old, new));
    packages
  }

  fn diff_for(name: &str, old: &[&str], new: &[&str]) -> Diff {
    let mut diffs =
      generate_diffs_from_version_map(version_map(name, old, new));
    canonicalize_diffs(&mut diffs);
    assert_eq!(diffs.len(), 1);
    diffs.remove(0)
  }

  fn old_side_count(diff: &Diff) -> usize {
    diff
      .versions
      .iter()
      .filter(|version_diff| {
        matches!(
          version_diff,
          VersionDiff::Removed(_)
            | VersionDiff::Changed { .. }
            | VersionDiff::AmountChanged { .. }
        )
      })
      .count()
  }

  fn new_side_count(diff: &Diff) -> usize {
    diff
      .versions
      .iter()
      .filter(|version_diff| {
        matches!(
          version_diff,
          VersionDiff::Added(_)
            | VersionDiff::Changed { .. }
            | VersionDiff::AmountChanged { .. }
        )
      })
      .count()
  }

  #[test]
  fn generate_diffs_empty_paths() {
    let packages = BTreeMap::new();
    assert!(generate_diffs_from_version_map(packages).is_empty());
  }

  #[test]
  fn generate_diffs_unchanged_package() {
    assert!(
      generate_diffs_from_version_map(version_map("package", &["1.0.0"], &[
        "1.0.0"
      ]))
      .is_empty()
    );
  }

  #[test]
  fn generate_diffs_unchanged_duplicate_versions() {
    assert!(
      generate_diffs_from_version_map(version_map(
        "package",
        &["1.0.0", "1.0.0"],
        &["1.0.0", "1.0.0"],
      ))
      .is_empty()
    );
  }

  #[test]
  fn generate_diffs_added_package() {
    let diff = diff_for("new-pkg", &[], &["1.0.0"]);

    assert_eq!(diff.name, "new-pkg");
    assert_eq!(diff.status, DiffStatus::Added);
    assert_eq!(diff.versions, vec![VersionDiff::Added(version_amount(
      "1.0.0", 1
    ))]);
  }

  #[test]
  fn generate_diffs_removed_package() {
    let diff = diff_for("old-pkg", &["1.0.0"], &[]);

    assert_eq!(diff.name, "old-pkg");
    assert_eq!(diff.status, DiffStatus::Removed);
    assert_eq!(diff.versions, vec![VersionDiff::Removed(version_amount(
      "1.0.0", 1
    ))]);
  }

  #[test]
  fn generate_diffs_reports_added_version_amounts() {
    let diff = diff_for("new-pkg", &[], &["1.0.0", "1.0.0"]);

    assert_eq!(diff.status, DiffStatus::Added);
    assert_eq!(diff.versions, vec![VersionDiff::Added(version_amount(
      "1.0.0", 2
    ))]);
  }

  #[test]
  fn generate_diffs_reports_removed_version_amounts() {
    let diff = diff_for("old-pkg", &["1.0.0", "1.0.0"], &[]);

    assert_eq!(diff.status, DiffStatus::Removed);
    assert_eq!(diff.versions, vec![VersionDiff::Removed(version_amount(
      "1.0.0", 2
    ))]);
  }

  #[test]
  fn generate_diffs_reports_changed_version_amounts() {
    let diff = diff_for("pkg", &["1.0.0"], &["1.0.0", "1.0.0"]);

    assert_eq!(diff.status, DiffStatus::Changed);
    assert!(!diff.has_omitted_versions);
    assert_eq!(diff.versions, vec![VersionDiff::AmountChanged {
      version:    Version::new("1.0.0"),
      old_amount: nonzero(1),
      new_amount: nonzero(2),
    }]);
  }

  #[test]
  fn generate_diffs_reports_version_change_amounts() {
    let diff = diff_for("pkg", &["1.0.0"], &["2.0.0", "2.0.0"]);

    assert_eq!(diff.status, DiffStatus::Upgraded);
    assert_eq!(diff.versions, vec![VersionDiff::Changed {
      old: version_amount("1.0.0", 1),
      new: version_amount("2.0.0", 2),
    }]);
  }

  #[test]
  fn generate_diffs_upgraded() {
    let diff = diff_for("pkg", &["1.0.0"], &["2.0.0"]);

    assert_eq!(diff.status, DiffStatus::Upgraded);
    assert_eq!(diff.versions, vec![VersionDiff::Changed {
      old: version_amount("1.0.0", 1),
      new: version_amount("2.0.0", 1),
    }]);
  }

  #[test]
  fn generate_diffs_reports_git_hash_only_change_as_changed() {
    let diff = diff_for("sunsetr", &["0.11.1-946aa34"], &["0.11.1-3564204"]);

    assert_eq!(diff.status, DiffStatus::Changed);
    assert_eq!(diff.versions, vec![VersionDiff::Changed {
      old: version_amount("0.11.1-946aa34", 1),
      new: version_amount("0.11.1-3564204", 1),
    }]);
  }

  #[test]
  fn generate_diffs_uses_dated_component_before_git_hash_for_upgrade() {
    let diff = diff_for("yazi", &["25.05.31pre20250531_946aa34"], &[
      "25.05.31pre20250601_3564204",
    ]);

    assert_eq!(diff.status, DiffStatus::Upgraded);
  }

  #[test]
  fn generate_diffs_downgraded() {
    let diff = diff_for("pkg", &["2.0.0"], &["1.0.0"]);

    assert_eq!(diff.status, DiffStatus::Downgraded);
  }

  #[test]
  fn generate_diffs_upgrade_downgrade() {
    let diff = diff_for("pkg", &["1.0", "5.0"], &["2.0", "4.0"]);

    assert_eq!(diff.status, DiffStatus::Mixed);
  }

  #[test]
  fn generate_diffs_multiple_packages() {
    let mut packages = BTreeMap::new();
    packages
      .insert("pkg-a".to_owned(), package_versions(&["1.0.0"], &["2.0.0"]));
    packages.insert("pkg-b".to_owned(), package_versions(&[], &["1.0.0"]));
    packages
      .insert("pkg-c".to_owned(), package_versions(&["1.0.0"], &["1.0.0"]));

    let result = generate_diffs_from_version_map(packages);
    let names: HashSet<_> =
      result.iter().map(|diff| diff.name.as_str()).collect();

    assert_eq!(result.len(), 2);
    assert!(names.contains("pkg-a"));
    assert!(names.contains("pkg-b"));
    assert!(!names.contains("pkg-c"));
  }

  #[test]
  fn generate_diffs_common_versions() {
    let diff = diff_for("pkg", &["1.0.0", "2.0.0"], &["2.0.0", "3.0.0"]);

    assert!(diff.has_omitted_versions);
    assert_eq!(diff.status, DiffStatus::Upgraded);
  }

  #[test]
  fn generate_diffs_many_versions() {
    let old_versions: Vec<_> = (0..100)
      .map(|index| Version::new(format!("1.{index}.{index}")))
      .collect();
    let new_versions: Vec<_> = (50..150)
      .map(|index| Version::new(format!("1.{index}.{index}")))
      .collect();
    let mut versions = PackageVersions::default();
    for version in old_versions {
      versions.old.add(version);
    }
    for version in new_versions {
      versions.new.add(version);
    }
    let mut packages = BTreeMap::new();
    packages.insert("large-pkg".to_owned(), versions);

    let result = generate_diffs_from_version_map(packages);

    assert_eq!(result.len(), 1);
    assert!(result[0].has_omitted_versions);
    assert_eq!(old_side_count(&result[0]), 50);
    assert_eq!(new_side_count(&result[0]), 50);
  }
}