#!/bin/bash

UPDATING_REF="$1"
FROM_HASH="$2"
TO_HASH="$3"

# GENERAL Problem Background:
# - In git, repo paths are inherently case-sensitive
# - In two of the three major dev workstation OSs (Windows, OSX), filesystems are typically case-insensitive
# - When files are added in the repo that are duplicates in the filesystem, but not in git, usability problems abound
# - A particularly onerous issue occurs when case-insensitive-duplicate files have differing content; after a checkout
#       of such a tree, the case-insensitive working tree always looks like it has a change to one or the other of the
#       VCS files. In such an "unavoidably/unfixably dirty tree" state, a casual user cannot even "pull" a fixed branch
#       state, as git will will refuse to pull in a dirty working tree.
# - Git currently offers no built-in mechanism to prevent this
# - It is preferable to avoid this issue in a server hook, rather than in CI validations (although the latter can also
#       work) - the earlier the issue is "nipped in the bud" the better.
# - There is a reasonably trivial shell scripting test for "Tree has duplicates", but validating simply on the basis of
#       this test presents two challenges:
#   - It might be too expensive to run on every commit in a large repo
#   - It might trigger "false positives" when creating new refs pointing to old already-problematic commits

# SPECIFIC Problem Repo Background:
# - 200K files, in deeply nested (java) folder structures (+50k directories)
# - Doing a "naive" full-tree case-insensitive duplicate search takes around 2s
#   - This is not a price we're willing to pay on every branch update
# - Case-insensitive duplicates are sometimes folders, sometimes files
# - Repo has lots of refs - 110k - so scanning them is costly
# - New refs are created *very* often - most often as "keeparound" refs in GitLab
#   - Validations don't make sense / don't add value for some or many classes of ref (those created by automated
#       systems, where a violation is not the "fault" of the pusher)
# - Some (active) branches are very distant from each other - there is no single "master"
 
# Test Cases / situations:
# - Single "normal" change, a dozen added files
# - Single "large-ish" change, a few hundred added files
# - on an existing branch (eg simple change, merge from upstream)
# - on a new branch, varying the original/upstream branch
# - on new refs that are excluded from validation by path/pattern

# Expected & tested performance characteristics of this hook script:
# - For non-branch or otherwise disqualified refs, close to no overhead.
# - For updates to existing refs, it is reasonably optimal
#   - There are four non-trivial operations, which all scale with the diff size:
#     - Finding the files added in the ref update (git diff)
#     - Finding all the ancestor-paths for these files (output_all_ancestor_gitpaths)
#       - This *can* be made slightly more efficient by using eg python
#     - Finding all items in these paths (git ls-tree)
#     - Sorting the resulting paths/items (sort)
#   - When the number of added files is too high, we fall back to a full-tree search
# - For new non-disqualified refs, there are additional overheads:
#   - Finding the best/closest "standard branch" to diff from, for a new ref, might be non-trivial in some repos
#     - (in the generic implementation, it is a trivial/cheap check for "master" and "main")
#   - Depending on the strategy used to find a "diff from" ref, diffs on new refs will likely be much larger/more expensive than they should ideally need to be

# Future work / possible improvements:
# - If git provided an easy/cheap way to detect "commits new to this repo" in an update hook, the diffs could be consistently much smaller/more efficient.
#   - (it is possible to find out whether a commit is net-new with something like "git rev-list MYREF --not --exclude MYREF --all", but this is *expensive* in a large repo)
# - If "git ls-tree" supported icase pathspec magic, we could pass in full added-file pathspecs, and subsequent dupe-detection could be more efficient
#   - (there would be a functional difference: the current strategy finds dupe directories even if they have non-overlapping contents; this other approach would not)

# Requirements:
# - Bash 4 for associative arrays


#---------
#FUNCTIONS - called via subshell
#---------

output_all_ancestor_gitpaths() {
  declare -A INTERESTING_PATHS
  while IFS= read -r INPUT_LINE; do
    CURRENT_PATH="$INPUT_LINE"
    while [ "$CURRENT_PATH" != ":" ]; do
      [[ "$CURRENT_PATH" == */* ]] || CURRENT_PATH=":/$CURRENT_PATH"
      PARENT_PATH="${CURRENT_PATH%/*}"
      if [ "${INTERESTING_PATHS["${PARENT_PATH}/"]}" = "1" ]; then
        break
      fi
      INTERESTING_PATHS["${PARENT_PATH}/"]="1"
      CURRENT_PATH="$PARENT_PATH"
    done
  done <<< "$1"
  for key in ${!INTERESTING_PATHS[@]}; do echo "$key"; done
  debug_log "FOUND ${#INTERESTING_PATHS[@]} INTERESTING PATHS" 
}

find_closest_standard_branch() {
  # Simplest implementation, look for "master" or "main" or give up.
  # there will likely be better repo-specific strategies in specific repos.
  git for-each-ref --format="%(refname)" --count=1 refs/heads/master refs/heads/main
}

START_TIME="$(date +%s%N)"
debug_log() {
  if [ -n "$DEBUG_DUPE_HOOK" ]; then
    CURRENT_TIME="$(date +%s%N)"
    echo "Debug at $(($(($CURRENT_TIME-$START_TIME))/1000000))ms: $1" >&2
  fi
}

#-----------
#MAIN SCRIPT
#-----------

if [ -z "$TO_HASH" ]; then
  # branch deletion, no possibility of new dupes
  debug_log "BRANCH DELETION - SKIPPING DUPE VALIDATION"
  exit 0
fi

VALIDATING_PATH_PREFIXES=("refs/heads/")
REF_IS_VALIDATABLE=0
for PATH_PREFIX in "${VALIDATING_PATH_PREFIXES[@]}"
do
  if [[ "$UPDATING_REF" = "$PATH_PREFIX"* ]]; then
    REF_IS_VALIDATABLE=1
  fi
done

if [[ "$REF_IS_VALIDATABLE" = "0" ]]; then
  # we're not interested in validating for dupes on this ref.
  debug_log "NON-VALIDATABLE REF - SKIPPING DUPE VALIDATION"
  exit 0
fi

FULL_SEARCH=false
if [ -z "$FROM_HASH" ]; then
  # New ref; in most repos new "interesting" (not-excluded-from-dupe-check)
  # refs will likely be closely related to master/main most of the time, so
  # diff from there rather than starting from scratch.
  debug_log "NEW REF - LOOKING FOR STANDARD BRANCH"
  FROM_HASH=$(find_closest_standard_branch "$TO_HASH")
fi

if [ -z "$FROM_HASH" ]; then
  # If this is a new ref and no "standard upstream ref" was found, fall back
  # to full dupe search.
  debug_log "NO STANDARD UPSTREAM REF FOUND; DOING FULL SEARCH"
  FULL_SEARCH=true
else
  debug_log "CHECKING DIFF: git diff --diff-filter=A --no-renames --name-only '$FROM_HASH' '$TO_HASH'"
  NEW_FILES=$(git diff --diff-filter=A --no-renames --name-only "$FROM_HASH" "$TO_HASH")
  NEW_FILE_LINE_COUNT=$(wc -l <<< "$NEW_FILES")
  
  if [ "$NEW_FILE_LINE_COUNT" -le "1" ] && [ -z "$NEW_FILES" ]; then
    # no newly added files, no possibility of new dupes
	# (count "1" can be an empty line)
    debug_log "EXITING WITH 0 ADDED FILES"
    exit 0
  fi

  if [ "$NEW_FILE_LINE_COUNT" -gt 10000 ]; then
    # If there are too many files, then generating all the sub-paths and
    # running ls-tree with a huge pathspec will be slower than simply
    # checking the whole tree.
    debug_log "FILE COUNT $NEW_FILE_LINE_COUNT OVER LIMIT; DOING FULL SEARCH"
    FULL_SEARCH=true
  fi
fi

if [ "$FULL_SEARCH" = "true" ]; then
  debug_log "DOING FULL DUPE SEARCH"
  DUPE_PATHS=$(git ls-tree --name-only -r "$TO_HASH" | sort | uniq -i -D)
else
  debug_log "DOING DIFF SEARCH OF $NEW_FILE_LINE_COUNT ADDED FILES BETWEEN $FROM_HASH AND $TO_HASH"
  DUPE_PATHS=$(output_all_ancestor_gitpaths "$NEW_FILES" | sort | xargs -d"\n" --no-run-if-empty git ls-tree --name-only -t "$TO_HASH" | sort | uniq | uniq -i -D)
fi

if [ -z "$DUPE_PATHS" ]; then
  debug_log "EXITING - NO DUPES FOUND"
  exit 0
else
  debug_log "EXITING WITH DUPES ERROR"
  echo "This ref cannot be accepted - duplicate folders or files found:"
  echo "$DUPE_PATHS"
  exit 1
fi
