find-duplicate-sha256.sh

#!/usr/bin/env bash
set -euo pipefail

SCRIPT_DIR="$(cd -- "$(dirname -- "${BASH_SOURCE[0]:-$0}")" && pwd)"
# shellcheck source=common.sh
source "${SCRIPT_DIR}/common.sh"

usage() {
  cat <<'EOF'
Usage:
  find-duplicate-sha256.sh [OPTIONS] [DIRECTORY...]

Description:
  Recursively scans the provided directories (defaults to ".") for files
  generated by analyze-archive.sh (suffix ".sha256") and reports any SHA-256
  digests that appear more than once. Each duplicate lists the manifest file
  and the archived path associated with that digest so you can spot redundant
  content across archives quickly.

Options:
  -A, --identical-archives   Only report archives whose manifests are identical
                             (same set of files + hashes). Requires sha256sum.
  -D, --delete-identical     Delete redundant archives/manifests when using
                             --identical-archives. Keeps the first archive in
                             each identical group and removes the rest.
  -S, --skip-intra-manifest  Ignore hashes that appear more than once inside the
                             same manifest (only care about cross-archive dupes).
  -y, --yes                  Automatically answer "yes" to deletion prompts.
  -h, --help                 Show this help message.
EOF
}

require_tool() {
  command -v "$1" >/dev/null 2>&1 || die "Required tool '$1' is not on PATH."
}

SEP=$'\x1F'
GROUP_SEP=$'\x1E'
IDENTICAL_ONLY=0
SKIP_INTRA_MANIFEST=0
DELETE_IDENTICAL=0
AUTO_CONFIRM=0

declare -A HASH_COUNTS=()
declare -A HASH_LOCATIONS=()
declare -A SIGNATURE_MANIFESTS=()
declare -A MANIFEST_ENTRY_COUNTS=()
declare -A HASH_MANIFEST_SEEN=()
declare -A HASH_UNIQUE_MANIFEST_COUNT=()

collect_related_basename_files() {
  local manifest="$1" archive="$2" out_var="$3"
  local -n __out_ref="$out_var"
  __out_ref=()

  local base_no_sha="${manifest%.sha256}"
  local dir
  dir="$(dirname -- "$manifest")"
  local stem
  stem="$(basename -- "$base_no_sha")"

  declare -A seen=()
  shopt -s nullglob dotglob
  for candidate in "$base_no_sha".* "$dir/$stem"; do
    [[ -f "$candidate" ]] || continue
    if [[ "$candidate" == "$manifest" || (-n "${archive:-}" && "$candidate" == "$archive") ]]; then
      continue
    fi
    seen["$candidate"]=1
  done
  shopt -u nullglob dotglob

  for candidate in "${!seen[@]}"; do
    __out_ref+=("$candidate")
  done
}

gather_delete_targets() {
  local manifest="$1" out_var="$2"
  local -n __out_ref="$out_var"
  __out_ref=()

  local archive=""
  if [[ -e "$manifest" ]]; then
    __out_ref+=("$manifest")
  fi

  if [[ "$manifest" == *.sha256 ]]; then
    archive="${manifest%.sha256}"
    if [[ -e "$archive" ]]; then
      __out_ref+=("$archive")
    fi
  fi

  local -a related_files=()
  collect_related_basename_files "$manifest" "${archive:-}" related_files
  if ((${#related_files[@]} > 0)); then
    __out_ref+=("${related_files[@]}")
  fi
}

format_manifest_choice_label() {
  local manifest="$1"
  local -a targets=()
  gather_delete_targets "$manifest" targets

  local label="$manifest"
  if ((${#targets[@]} > 1)); then
    local -a extras=("${targets[@]:1}")
    label+=" (also removes: "
    label+="$(printf '%s, ' "${extras[@]}")"
    label="${label%, }"
    label+=")"
  fi
  printf '%s\n' "$label"
}

interactive_select_items() {
  local result_var="$1"
  local prompt="$2"
  shift 2
  local -n __result_ref="$result_var"
  local -a options=("$@")
  __result_ref=()

  if ((${#options[@]} == 0)); then
    return 1
  fi

  if command -v fzf >/dev/null 2>&1; then
    local selection
    if ! selection="$(
      printf '%s\n' "${options[@]}" |
        fzf --multi --prompt "$prompt" \
          --header=$'TAB to toggle selections, ENTER to confirm, ESC to cancel'
    )"; then
      return 1
    fi
    if [[ -z "$selection" ]]; then
      return 1
    fi
    mapfile -t __result_ref <<<"$selection"
    return 0
  fi

  while true; do
    printf '%s\n' "$prompt"
    for idx in "${!options[@]}"; do
      printf '  [%d] %s\n' "$((idx + 1))" "${options[idx]}"
    done
    printf 'Enter comma-separated numbers to delete (blank to cancel): '
    local input
    if ! IFS= read -r input; then
      return 1
    fi
    input="${input//[[:space:]]/}"
    if [[ -z "$input" ]]; then
      return 1
    fi
    IFS=',' read -r -a selected_indices <<<"$input"
    declare -a selected_unique=()
    declare -A seen_index=()
    invalid=0
    for raw in "${selected_indices[@]}"; do
      if [[ ! "$raw" =~ ^[0-9]+$ ]]; then
        invalid=1
        break
      fi
      local idx=$((raw - 1))
      if ((idx < 0 || idx >= ${#options[@]})); then
        invalid=1
        break
      fi
      if [[ -z "${seen_index[$idx]:-}" ]]; then
        selected_unique+=("${options[idx]}")
        seen_index[$idx]=1
      fi
    done
    if ((invalid || ${#selected_unique[@]} == 0)); then
      printf 'Invalid selection. Please try again.\n'
      continue
    fi
    __result_ref=("${selected_unique[@]}")
    return 0
  done
}

delete_redundant_manifest() {
  local manifest="$1"
  local -a targets=()
  gather_delete_targets "$manifest" targets

  if [[ "${#targets[@]}" -eq 0 ]]; then
    printf 'warning: nothing to delete for %s (files missing)\n' "$manifest" >&2
    return
  fi

  if confirm_action "The following ${#targets[@]} item(s) will be removed:" "$AUTO_CONFIRM" "${targets[@]}"; then
    for path in "${targets[@]}"; do
      if rm -f -- "$path"; then
        printf 'Deleted %s\n' "$path"
      else
        printf 'Failed to delete %s\n' "$path" >&2
      fi
    done
  fi
}

record_entry() {
  local hash="$1" manifest="$2" entry="$3"
  HASH_COUNTS["$hash"]=$((${HASH_COUNTS["$hash"]:-0} + 1))
  if [[ -v HASH_LOCATIONS["$hash"] ]]; then
    HASH_LOCATIONS["$hash"]+=$'\n'"$manifest$SEP$entry"
  else
    HASH_LOCATIONS["$hash"]="$manifest$SEP$entry"
  fi
  local combination="$hash$GROUP_SEP$manifest"
  if [[ ! -v HASH_MANIFEST_SEEN["$combination"] ]]; then
    HASH_MANIFEST_SEEN["$combination"]=1
    HASH_UNIQUE_MANIFEST_COUNT["$hash"]=$((${HASH_UNIQUE_MANIFEST_COUNT["$hash"]:-0} + 1))
  fi
}

entries_recorded=0
lines_skipped=0

process_manifest() {
  local manifest="$1" line line_no=0 manifest_entries=0
  local -a manifest_pairs=()
  local hash rest entry_path
  while IFS= read -r line || [[ -n "$line" ]]; do
    line_no=$((line_no + 1))
    line="${line%$'\r'}"
    [[ -z "$line" ]] && continue
    [[ "$line" =~ ^[[:space:]]*# ]] && continue
    if [[ "$line" =~ ^([[:xdigit:]]{64})[[:space:]][[:space:]]+(.+)$ ]]; then
      hash="${BASH_REMATCH[1]}"
      rest="${BASH_REMATCH[2]}"
      entry_path="$rest"
      if [[ "$rest" =~ ^(.*[^[:space:]])[[:space:]][[:space:]]+([0-9]+)$ ]]; then
        entry_path="${BASH_REMATCH[1]}"
      fi
      record_entry "$hash" "$manifest" "$entry_path"
      manifest_pairs+=("$hash$SEP$entry_path")
      entries_recorded=$((entries_recorded + 1))
      manifest_entries=$((manifest_entries + 1))
    else
      lines_skipped=$((lines_skipped + 1))
      printf 'warning: %s:%d not recognized, skipping\n' "$manifest" "$line_no" >&2
    fi
  done <"$manifest"

  MANIFEST_ENTRY_COUNTS["$manifest"]=$manifest_entries

  if [[ "$manifest_entries" -eq 0 ]]; then
    printf 'note: %s contained no recognizable entries\n' "$manifest" >&2
  fi

  if ((IDENTICAL_ONLY)); then
    local signature
    if ((${#manifest_pairs[@]} > 0)); then
      signature="$(printf '%s\n' "${manifest_pairs[@]}" | LC_ALL=C sort | sha256sum | awk '{print $1}')"
    else
      signature="$(printf '' | sha256sum | awk '{print $1}')"
    fi
    if [[ -v SIGNATURE_MANIFESTS["$signature"] ]]; then
      SIGNATURE_MANIFESTS["$signature"]+="$GROUP_SEP$manifest"
    else
      SIGNATURE_MANIFESTS["$signature"]="$manifest"
    fi
  fi
}

dirs=()
while [[ $# -gt 0 ]]; do
  case "$1" in
  -A | --identical-archives)
    IDENTICAL_ONLY=1
    shift
    ;;
  -D | --delete-identical)
    DELETE_IDENTICAL=1
    shift
    ;;
  -S | --skip-intra-manifest)
    SKIP_INTRA_MANIFEST=1
    shift
    ;;
  -y | --yes)
    AUTO_CONFIRM=1
    shift
    ;;
  -h | --help)
    usage
    exit 0
    ;;
  --)
    shift
    break
    ;;
  -*)
    die "Unknown option: $1"
    ;;
  *)
    dirs+=("$1")
    shift
    ;;
  esac
done

if [[ $# -gt 0 ]]; then
  dirs+=("$@")
fi

if [[ "${#dirs[@]}" -eq 0 ]]; then
  dirs=(".")
fi

if ((DELETE_IDENTICAL && !IDENTICAL_ONLY)); then
  die "--delete-identical requires --identical-archives"
fi

for dir in "${dirs[@]}"; do
  [[ -d "$dir" ]] || die "Directory not found: $dir"
done

if ((IDENTICAL_ONLY)); then
  require_tool sha256sum
fi

manifests_scanned=0
while IFS= read -r -d '' manifest; do
  manifests_scanned=$((manifests_scanned + 1))
  process_manifest "$manifest"
done < <(find "${dirs[@]}" -type f -name '*.sha256' -print0)

if [[ "$manifests_scanned" -eq 0 ]]; then
  die "No .sha256 manifests found under the provided directory set."
fi

printf 'Scanned %d manifest(s); %d total entries (%d unique hashes). Skipped %d line(s).\n' \
  "$manifests_scanned" "$entries_recorded" "${#HASH_COUNTS[@]}" "$lines_skipped"

if ((IDENTICAL_ONLY)); then
  identical_groups_found=0
  for signature in "${!SIGNATURE_MANIFESTS[@]}"; do
    IFS=$GROUP_SEP read -r -a manifests_in_group <<<"${SIGNATURE_MANIFESTS["$signature"]}"
    if ((${#manifests_in_group[@]} > 1)); then
      identical_groups_found=1
      mapfile -t manifests_in_group < <(printf '%s\n' "${manifests_in_group[@]}" | LC_ALL=C sort)
      entries="${MANIFEST_ENTRY_COUNTS["${manifests_in_group[0]}"]:-0}"
      printf '\nArchives with identical contents (%d entries):\n' "$entries"
      for manifest in "${manifests_in_group[@]}"; do
        printf '  - %s\n' "$manifest"
      done
      if ((DELETE_IDENTICAL)); then
        declare -a manifests_to_delete=()
        if ((AUTO_CONFIRM)); then
          manifests_to_delete=("${manifests_in_group[@]:1}")
          printf 'Auto mode: keeping %s and deleting %d additional archive(s).\n' \
            "${manifests_in_group[0]}" "${#manifests_to_delete[@]}"
        else
          declare -a choice_labels=()
          declare -A label_to_manifest=()
          for manifest in "${manifests_in_group[@]}"; do
            label="$(format_manifest_choice_label "$manifest")"
            choice_labels+=("$label")
            label_to_manifest["$label"]="$manifest"
          done
          printf $'Select redundant archives to delete. Leave at least one archive unchecked.\n'
          declare -a selected_labels=()
          if ! interactive_select_items selected_labels "delete> " "${choice_labels[@]}"; then
            printf 'No archives were selected for deletion; skipping this group.\n'
            continue
          fi
          for label in "${selected_labels[@]}"; do
            manifest="${label_to_manifest["$label"]-}"
            if [[ -z "$manifest" ]]; then
              printf 'warning: selection "%s" did not map to a manifest, skipping\n' "$label" >&2
              continue
            fi
            manifests_to_delete+=("$manifest")
          done
          if ((${#manifests_to_delete[@]} >= ${#manifests_in_group[@]})); then
            printf 'Cannot delete every archive in a group; skipping this group.\n'
            continue
          fi
        fi
        for manifest in "${manifests_to_delete[@]}"; do
          delete_redundant_manifest "$manifest"
        done
      fi
    fi
  done

  if ((identical_groups_found == 0)); then
    printf 'No archives with identical contents were found.\n'
  elif ((DELETE_IDENTICAL)); then
    printf '\nDeletion pass complete.\n'
  fi
  exit 0
fi

duplicate_hashes=()
for hash in "${!HASH_COUNTS[@]}"; do
  if ((SKIP_INTRA_MANIFEST)); then
    if ((${HASH_UNIQUE_MANIFEST_COUNT["$hash"]:-0} > 1)); then
      duplicate_hashes+=("$hash")
    fi
  else
    if ((HASH_COUNTS["$hash"] > 1)); then
      duplicate_hashes+=("$hash")
    fi
  fi
done

if [[ "${#duplicate_hashes[@]}" -eq 0 ]]; then
  printf 'No duplicate SHA-256 entries found.\n'
  exit 0
fi

printf '\nDuplicate SHA-256 digests:\n'
IFS=$'\n' read -r -d '' -a duplicate_hashes < <(printf '%s\n' "${duplicate_hashes[@]}" | LC_ALL=C sort && printf '\0')

for hash in "${duplicate_hashes[@]}"; do
  display_count="${HASH_COUNTS["$hash"]}"
  if ((SKIP_INTRA_MANIFEST)); then
    display_count="${HASH_UNIQUE_MANIFEST_COUNT["$hash"]:-0}"
  fi
  printf '\nSHA256 %s (%d occurrences):\n' "$hash" "$display_count"
  printed_manifest_list=""
  while IFS= read -r location || [[ -n "$location" ]]; do
    IFS=$SEP read -r manifest entry <<<"$location"
    if ((SKIP_INTRA_MANIFEST)); then
      if [[ ":$printed_manifest_list:" == *":$manifest:"* ]]; then
        continue
      fi
      printed_manifest_list="${printed_manifest_list:+$printed_manifest_list:}$manifest"
    fi
    printf '  - %s :: %s\n' "$manifest" "$entry"
  done <<<"${HASH_LOCATIONS["$hash"]}"
done