path: root/bin/git-deli

#!/bin/bash
#
# git-deli.sh: delinearized git workflows helper
#
# Copytight (C) 2025 Mirek Kratochvil <exa.exa@gmail.com>
#

#
# ARGUMENT PARSING AND MAIN ENTRYPOINT
#

OPTS_SPEC="\
git deli head [-b=<branch>] [-m=<msg>] [<commit>] [-s]
git deli eat [-c] [-s] [-b=<branch>] [-m=<msg>] <commit>
git deli commit ...
git deli boundary [-d] <commit>
git deli merge <commit> ...
git deli push [-f] [<repository>] [<refspec>]
git deli pull [<repository>] [<ref>]
--
 common options:
h,help! show the help
m,message!= specify the commit message
 'head' and 'eat' actions:
b,branch!= start a new branch instead of using the target one
s,set-boundary use the <commit> as a boundary for the new head
c,create-head start a new head at <commit> and delinearize into it
 'boundary' options:
d,delete delete the boundary commit instead of adding it
 'push' options:
f,force internally do a true force-push instead of the safe force-with-lease
"
main() {
  if test $# -eq 0
  then set -- -h
  fi

  set_args="$(echo "$OPTS_SPEC" | git-rev-parse --parseopt --stuck-long -- "$@" || echo exit $?)"
  eval "$set_args"
  . git-sh-setup
  require_work_tree
  
  # find the command right away (TODO: actually validate if the options
  # belong to the given command later)
  while test $# -gt 0
  do
    opt="$1"
    shift
    [ "$opt" = "--" ] && break
  done
  arg_command=$1
  eval "$set_args"

  arg_msg=
  arg_branch=
  arg_create_head=
  arg_set_boundary=
  arg_all=
  arg_patch=
  arg_delete=
  arg_force=
  while test $# -gt 0
  do
    opt="$1"
    shift
    case "$opt" in
    --delete)
      [ -z "$arg_delete" ] || die "conflicting options for --delete"]
      arg_delete=yes ;;
    --no-delete)
      [ -z "$arg_delete" ] || die "conflicting options for --delete"]
      arg_delete=no ;;
    --message=*)
      [ -z "$arg_msg" ] || die "conflicting options for --message"]
      arg_msg="${opt#*=}" ;;
    --branch=*)
      [ -z "$arg_branch" ] || die "conflicting options for --branch"]
      arg_branch="${opt#*=}" ;;
    --create-head)
      [ -z "$arg_create_head" ] || die "conflicting options for --create-head"]
      arg_create_head=yes ;;
    --no-create-head)
      [ -z "$arg_create_head" ] || die "conflicting options for --create-head"]
      arg_create_head=no ;;
    --set-boundary)
      [ -z "$arg_set_boundary" ] || die "conflicting options for --set-boundary"]
      arg_set_boundary=yes ;;
    --no-set-boundary)
      [ -z "$arg_set_boundary" ] || die "conflicting options for --set-boundary"]
      arg_set_boundary=no ;;
    --delete)
      [ -z "$arg_delete" ] || die "conflicting options for --delete"]
      arg_delete=yes ;;
    --no-delete)
      [ -z "$arg_delete" ] || die "conflicting options for --delete"]
      arg_delete=no ;;
    --force)
      [ -z "$arg_force" ] || die "conflicting options for --force"]
      arg_force=yes ;;
    --no-force)
      [ -z "$arg_force" ] || die "conflicting options for --force"]
      arg_force=no ;;
    --)
      break ;;
    *)
      die "fatal: unexpected option: $opt"
    esac
  done

  shift # drop the command, we already got it
  case "$arg_command" in
  head) cmd_head "$arg_msg" "$arg_branch" "$arg_set_boundary" "$@" ;;
  eat) cmd_eat "$arg_msg" "$arg_branch" "$@" ;;
  commit) cmd_commit "$arg_msg" "$@" ;;
  boundary) cmd_boundary "$arg_delete" "$@" ;;
  merge) cmd_merge "$@" ;;
  push) cmd_push "$arg_force" "$@" ;;
  pull) cmd_pull "$@" ;;
  *)
    die "fatal: unknonwn command: $arg_command" ;;
  esac
}

#
# COMMANDS
#

cmd_head () {
  # we're making a new head
  custom_msg="$1"
  branch="$2"
  set_boundary="$3"
  shift 3

  if [ $# -gt 1 ]
  then die "too many arguments"
  fi

  msg="delinearized head view"
  if [ -n "$branch" ]
  then
    git checkout -b "$branch" "$@" || die "git-checkout failed"
    msg="$msg on $branch"
  fi

  if [ -n "$custom_msg" ]
  then msg="$custom_msg"
  fi

  current_head=$( git rev-parse HEAD || die "git-rev-parse on HEAD failed" )
  if [ $set_boundary = yes ]
  then msg="$msg\n\ndeli-boundary: $current_head"
  fi

  new_head=$(git commit-tree $current_head^{tree} -p $current_head -m "$msg" || die "git-commit-tree failed")
  git reset --soft "$new_head" || die "git-reset failed to set the new HEAD"
}

cmd_eat () {
  # we're squashing whatever has been done atop of a given head view
  false
}

cmd_commit () {
  msg="$1"
  shift
  # TODO run a git commit with all extra args, THEN run head with the original commit
  false
}

cmd_boundary () {
  delete="$1"
  shift
  [ $# -eq 1 ] || die "specify one boundary commit"
  commit="$1"

  # TODO this adds or removes the "extra parents" to the head commit
  false
}

cmd_merge () {
  # TODO this should merge multiple "head" commits
  # notably, there must not be any actual merging involved -- there must
  # be no conflicts etc. What happens is that, quite simply, the parents
  # of the new head become all (latest) parents of all original heads. If
  # there is any actual merging required, it must be resolved elsewhere
  # and recorded in the history so that branches merge cleanly.
  false
}

cmd_push () {
  # TODO like git-push but actually force-pushes the current multihead.
  # Uses a force-with-lease by default.
  false
}

cmd_pull () {
  # TODO like a normal git fetch followed by git deli merge
  false
}

#
# THE TRICKERY
#
# The main algorithm takes a DELI HEAD and some given COMMIT. Initially, the
# DELI HEAD is an ancestor of COMMIT, and the aim is to instead make the COMMIT
# a new parent of DELI HEAD, but preferably only depending on the historical
# changes that are really required for the commit to apply cleanly. Thus, two
# independent (non-overlapping) COMMITs that are tricked through in such manner
# should preferably become independent branches.
#
# We boldly assume that:
# - the stuff that the COMMIT "depends" on can be traced by git-blame on the
#   source lines
# - to simplify, we pick the set of youngest independent commits out of all
#   blamed ones
#
# What can go wrong:
# - The set of independent commits from the blame may happen to not "merge
#   cleanly", because they contain conflicting changes unrelated to our COMMIT.
#   Quite necessarily, these must have been already solved somewhere in the
#   history (somehow) because the DELI HEAD exists and the commits are all its
#   ancestors. In that case we kindly ask the user to place suitable bound(s)
#   into the history that contain the solved merge. (We could as well try to
#   bisect to find a single good bound, but I'm genuinely unsure how to bisect
#   search for a combination of commits to merge. That's very
#   multidimensional.)
# - If the merge succeeds, the commit patch is ofcourse not really guaranteed
#   to apply to the combined commit. If that's the case, we can ask the user
#   for a better bound again, or give the user a chance to fix the conflict
#   manually, as usual.
# - It may happen that the DELI HEAD is blamed as a "source" of a change, thus
#   a candidate for a new parent of our COMMIT. That's terribly wrong -- first,
#   because we want the reverse (to make the COMMIT a parent of the DELI HEAD),
#   but mainly because it means that the DELI HEAD is not a mere "clean view"
#   on the history, but instead describes some changes by itself. In such case,
#   we say the DELI HEAD is corrupted and kindly ask the user to create a new
#   one.  (This may probably happen quite frequently if someone runs `go` on a
#   commit that is not a proper DELI HEAD.)
#
# The progress is thus as follows:
# - extract all source (context&keep&delete) line commit information from the
#   COMMIT. For all commits it is assumed that the COMMIT is supposed to serve as
#   a direct child of DELI HEAD and is thus diffed against the DELI HEAD, the
#   "original" parts of the diff serve as the information source for the blame.
#   The blame runs from DELI HEAD.
# - reduce the source commits to an independent set of commits that describe
#   the "direct" COMMIT ancestors
#   (that is done by `git merge-base --independent`)
# - fail if:
#   - DELI HEAD is in the commits, or
#   - DELI HEAD is an ancestor of any of these
#   (technically both conditions are equivalent for the --is-ancestor check)
# - bail out if:
#   - the independent set doesn't merge cleanly
#   - the commit doesn't apply atop the merged independent set (and the user
#     doesn't want to resolve the conflict manually)
# - at this point, this should give a single new merged commit
# - add the commit to the set of parents of the DELI HEAD (possibly pruning out
#   its own ancestors again) and commit the new DELI HEAD
#
# TODO:
# - How does the blame assumption interact with file renames?
#   At this point we're kindly asking the blame to treat renames as rewrites so
#   that the "merging" doesn't need to manage any of that. Which ain't super
#   good, more ideas would be welcome.
# - Is there a cleaner way to detect where the blame assumption would fail?

# usage:  <shas  >shas
stream_independent_commit_set () {
  # This would be also possible directly, but we might have tons of commits
  # incoming (this comes from annotated diffs :D) and the argcount limit might
  # get hit too easily. So this is a streaming version. Might get faster by
  # processing the shas in batches.
  mps=
  while read sha trailing_garbage
  do mps=$( git merge-base --independent $mps "$sha" || die "git-merge-base --independent failed" )
  done
  for sha in $mps
  do echo "$sha"
  done
}

# usage: revision  <diff  >shas
# TODO: Binary files (match ^Binary in output, ask for all lines)
deli_diff_to_source_lines () {
  awk -f '
BEGIN {
  file="";
  ranges="";
}

match($0, /^\+\+\+ b\/(.+)$/, matched) {
  if(ranges!="") print(ranges, "--", file);
  file=matched[1];
  ranges="";
}

match($0, /^@@ -([0-9]+),([0-9]+) /, matched) && file!="" {
  if(matched[2]!="0")
    ranges = ranges " -L " matched[1] ",+" matched[2];
}

END {
  if(ranges!="") print(ranges, "--", file);
}
  ' \
  | xargs -l git annotate -l "$1" \
  | cut -d'\t' -f1
}

deli_eat_commit () {
  delihead="$1"
  target="$2"
  # TODO insert bounds
  parents=$( git diff ${DELI_DIFF_ARGS:-} -p "$delihead" "$target" | deli_diff_to_source_lines | sort | uniq | stream_independent_commit_set )
  # check if the parents are ok
  for i in parents
  do git merge-base --is-ancestor "$delihead" "$i" || die "changes in $target are based on $delihead"
  done
  set -- $parents
  echo "sourcing commit $1..." >&2
  merged_tree="$1^{tree}"
  shift
  while test $# -gt 0
  do
    echo "merging commit $1..." >&2
    merged_tree=$( git merge-tree --write-tree "$merged_tree" "$1^{tree}" || die "merging of the parents failed" )
    shift
  done

  new_commit=$(
    ( echo "tree $merged_tree"
      for i in $parents
      do echo "parent $i"
      done
      git cat-file commit "$target" | sed '/^$/bx; /^tree /d ; /^parent /d ;  n ; :x'
    ) | git hash-object -t commit --stdin -w || die "could not save new commit for tree $merged_tree"
  )

  false
}

#
# MERGING DELI HEADS
#
# This takes 2 mergeable DELI HEADs and simply produces a new one. The heads
# must merge cleanly, otherwise the conflict must be resolved by a manual git
# merge followed by the commit trickery algorithm as above.
#
# Given the heads merge cleanly, the algorithm actually reduces to a very
# simple task:
#
# - we do a normal merge (this must solve cleanly)
# - all parents from the original 2 commits are combined and reduced to
#   independent set
# - all bounds from the original 2 commits are also reduced to an independent
#   set
# - if, for whichever reason, any of the parents becomes an ancestor of any of
#   the bounds, we fail
#   (TODO does it make sense to check this?)
# - we write out the new commit with all parents and all bounds
#
# TODO tbh this should be the very same as doing the `eat` operation after a
# merge, but the eat would need to handle multiple parents correctly.

deli_merge () {
  false
}

# finally, run the main
main "$@"