///|
pub(all) struct DuplicateOptions {
  minimum_size : Int64
  maximum_file_size : Int64
  maximum_groups : Int
} derive(Eq, Debug, ToJson, FromJson)

///|
pub fn DuplicateOptions::default() -> DuplicateOptions {
  DuplicateOptions::{
    minimum_size: 1L,
    maximum_file_size: 256L * 1024L * 1024L,
    maximum_groups: 1000,
  }
}

///|
pub(all) struct DuplicateGroup {
  size : Int64
  paths : Array[String]
  reclaimable_size : Int64
} derive(Eq, Debug, ToJson, FromJson)

///|
pub(all) struct DuplicateError {
  path : String
  message : String
} derive(Eq, Debug, ToJson, FromJson)

///|
pub(all) struct DuplicateResult {
  groups : Array[DuplicateGroup]
  errors : Array[DuplicateError]
  candidate_files : Int
  compared_files : Int
  reclaimable_size : Int64
} derive(Eq, Debug, ToJson, FromJson)

///|
fn duplicate_candidates(
  snapshot : Snapshot,
  options : DuplicateOptions,
) -> Map[String, Array[Entry]] {
  let by_size : Map[String, Array[Entry]] = Map([])
  for entry in snapshot.entries {
    if entry.is_file() &&
      entry.size >= options.minimum_size &&
      entry.size <= options.maximum_file_size {
      let key = entry.size.to_string()
      match by_size.get(key) {
        Some(entries) => entries.push(entry)
        None => by_size[key] = [entry]
      }
    }
  }
  by_size
}

///|
fn sort_duplicate_groups(groups : Array[DuplicateGroup]) -> Unit {
  groups.sort_by(fn(a, b) {
    if a.reclaimable_size > b.reclaimable_size {
      -1
    } else if a.reclaimable_size < b.reclaimable_size {
      1
    } else if a.size > b.size {
      -1
    } else if a.size < b.size {
      1
    } else if a.paths[0] < b.paths[0] {
      -1
    } else {
      1
    }
  })
}

///|
/// Find exact duplicate files. File size is used as a cheap prefilter; bytes are
/// only read for size buckets containing at least two files. Every reported pair
/// is confirmed using complete byte equality.
pub async fn find_duplicates(
  snapshot : Snapshot,
  options? : DuplicateOptions = DuplicateOptions::default(),
) -> DuplicateResult {
  let minimum = if options.minimum_size < 0L {
    0L
  } else {
    options.minimum_size
  }
  let effective = DuplicateOptions::{
    minimum_size: minimum,
    maximum_file_size: if options.maximum_file_size < minimum {
      minimum
    } else {
      options.maximum_file_size
    },
    maximum_groups: if options.maximum_groups < 1 {
      1
    } else {
      options.maximum_groups
    },
  }
  let groups : Array[DuplicateGroup] = []
  let errors : Array[DuplicateError] = []
  let processed : Map[String, Bool] = Map([])
  let buckets = duplicate_candidates(snapshot, effective)
  let mut candidate_files = 0
  let mut compared_files = 0
  for _, entries in buckets {
    if entries.length() < 2 {
      continue
    }
    candidate_files += entries.length()
    entries.sort_by(fn(a, b) { if a.path < b.path { -1 } else { 1 } })
    for i = 0; i < entries.length(); i = i + 1 {
      let representative = entries[i]
      if processed.get(representative.path) is Some(_) {
        continue
      }
      let representative_path = native_join(snapshot.root, representative.path)
      let reference = try {
        compared_files += 1
        @fs.read_file(representative_path).binary()
      } catch {
        error => {
          errors.push(DuplicateError::{
            path: representative.path,
            message: @debug.to_string(error),
          })
          processed[representative.path] = true
          continue
        }
      }
      let paths : Array[String] = [representative.path]
      processed[representative.path] = true
      for j = i + 1; j < entries.length(); j = j + 1 {
        let candidate = entries[j]
        if processed.get(candidate.path) is Some(_) {
          continue
        }
        try {
          compared_files += 1
          let content = @fs.read_file(
            native_join(snapshot.root, candidate.path),
          ).binary()
          if content == reference {
            paths.push(candidate.path)
            processed[candidate.path] = true
          }
        } catch {
          error => {
            errors.push(DuplicateError::{
              path: candidate.path,
              message: @debug.to_string(error),
            })
            processed[candidate.path] = true
          }
        }
      }
      if paths.length() > 1 {
        groups.push(DuplicateGroup::{
          size: representative.size,
          paths,
          reclaimable_size: representative.size *
          (paths.length() - 1).to_int64(),
        })
      }
    }
  }
  sort_duplicate_groups(groups)
  let limited = if groups.length() > effective.maximum_groups {
    groups[:effective.maximum_groups].to_owned()
  } else {
    groups
  }
  let mut reclaimable = 0L
  for group in limited {
    reclaimable += group.reclaimable_size
  }
  DuplicateResult::{
    groups: limited,
    errors,
    candidate_files,
    compared_files,
    reclaimable_size: reclaimable,
  }
}

///|
pub fn render_duplicates(result : DuplicateResult) -> String {
  let lines : Array[String] = [
    "MoonDisk duplicate-file report",
    "Duplicate groups: " + result.groups.length().to_string(),
    "Potentially reclaimable: " + format_bytes(result.reclaimable_size),
    "Size-prefilter candidates: " + result.candidate_files.to_string(),
    "Files compared: " + result.compared_files.to_string(),
    "Read errors: " + result.errors.length().to_string(),
  ]
  for group in result.groups {
    lines.push("")
    lines.push(
      format_bytes(group.size) +
      " each, " +
      format_bytes(group.reclaimable_size) +
      " reclaimable",
    )
    for path in group.paths {
      lines.push("  - " + path)
    }
  }
  if !result.errors.is_empty() {
    lines.push("")
    lines.push("Files that could not be compared")
    for error in result.errors {
      lines.push("  - " + error.path + ": " + error.message)
    }
  }
  lines.join("\n")
}

///|
pub fn duplicate_result_to_json(
  result : DuplicateResult,
  pretty? : Bool = true,
) -> String {
  let json = ToJson::to_json(result)
  if pretty {
    json.stringify(indent=2)
  } else {
    json.stringify()
  }
}