Bisection, but for git rebase, to quickly rebase across thousands of upstream commits

bisect-rebase.sh

  # Viktor Dukhovni's (@vdukhovni) slow rebase, made faster by bisecting, sort of
  #
  # fastrebase BRANCH_TO_REBASE ONTO
  function fastrebase {
      typeset b N

      if (($# > 0)) && [[ $1 = -h || $1 = --help ]]; then
          printf 'Usage: fastrebase BRANCH_TO_REBASE ONTO_HEAD\n'
          printf '       fastrebase # to continue after resolving conflicts\n'
          printf '\n\tfastrebase is a shell function that uses the following\n'
          printf '\tglobal variables to keep state: $S $T $B ${C[@]}\n'
          printf '\t                                $fastrebase_window_sz\n'
          printf '\tDO NOT CHANGE THOSE VARIABLES.\n'
          return 0
      elif (($# > 0 && $# != 2)); then
          printf 'Usage: fastrebase BRANCH_TO_REBASE ONTO_HEAD\n' 1>&2
          printf '       fastrebase # to continue after resolving conflicts\n'
          printf '\n\tfastrebase is a shell function that uses the following\n' 1>&2
          printf '\tglobal variables to keep state: $S $T $B ${C[@]}\n' 1>&2
          printf '\t                                $fastrebase_window_sz\n' 1>&2
          printf '\tDO NOT CHANGE THOSE VARIABLES.\n' 1>&2
          return 1
      fi

      if (($# == 2)); then
          fastrebase_window_sz=1
          S=$1
          T=$2
          B=$(git merge-base "$S" "$T")
          C=( $(git log --oneline "$B".."$2" | awk '{print $1}') )
          set --

          # Prep
          git log -n1 "$S" > /dev/null || return 1
          if [[ $(git log --oneline -n1 HEAD) != $(git log --oneline -n1 "$S") ]]; then
              if (($(git status -sb | wc -l) != 1)); then
                  printf 'Error: please clean your workspace\n'
                  return 1
              fi
              git checkout "$S"
          elif (($(git status -sbuno | wc -l) != 1)); then
              printf 'Error: please clean your workspace\n'
              return 1
          fi

          # Fall through to get started
      elif [[ $(git log --oneline -n1 HEAD) != $(git log --oneline -n1 "$S") ]] &&
         ! git rebase --continue; then
          N=$(( ${#C[@]} - fastrebase_window_sz ))
          printf '\nConflicts while rebasing $S (%s) slowly onto $T (%s)\n' "$S" "$T"
          printf '${C[@]} has the commits left to process (%s left)\n' $N
          printf '$B is the commit we are rebasing onto right now: %s\n' "$B"
          printf '$b is the previous commit we had already rebased onto: %s\n' "$b"
          return 1
      fi

      while ((${#C[@]} > 0)); do
          printf '%s commits left\n' ${#C[@]}
          N=$(( ${#C[@]} - fastrebase_window_sz ))
          b=$B
          B=${C[$N]}
          printf 'Rebasing onto %s\n' "$(git log --oneline -n1 "$B")"
          if git rebase --onto "$B" "$b" "$S"; then
              # No conflicts.  Let's go faster if we can.
              if ((fastrebase_window_sz < N)); then
                  ((fastrebase_window_sz++))
              fi
              C=(${C[@]:0:$N})
              continue
          fi

          # We have conflicts; bisect if we can
          if ((fastrebase_window_sz > 1)); then
              # Bisect to find the first commit causing the conflicts
              ((fastrebase_window_sz = (fastrebase_window_sz + 1) / 2))
              git rebase --abort
              continue
          fi

          # Finally, we have a commit causing conflicts.  The user has to
          # resolve and invoke this function again.
          unset C[$N]

          printf '\nConflicts while rebasing $S (%s) slowly onto $T (%s)\n' "$S" "$T"
          printf '${C[@]} has the commits left to process (%s left)\n' ${#C[@]}
          printf '$B is the commit we are rebasing onto right now: %s\n' "$B"
          printf '$b is the previous commit we had already rebased onto: %s\n' "$b"
          return 1
      done

      printf '\n\nDONE!\n'
      return 0
  }

This used to be called slowrebase, and it was slow because it went upstream-commit-by-commit. This version goes commit-by-commit only for those runs of upstream commits where every commit causes conflicts with the branch being rebased, but that is very rare. In the best case this does just one rebase.

One can imagine a number of variations on this idea:

• aggressive: try to rebase directly onto the desired target, on conflict back-off half-way
• slow-start: rebase across one upstream commit, then two, then four, then eight, and so on, but as soon as a conflict is found, go back to rebasing across one upstream commit
• somewhere in between

More options for this kind of bisect-rebase:

https://github.com/CTSRD-CHERI/git-mergify-rebase
https://github.com/mhagger/git-imerge/
https://github.com/brooksdavis/mergify/

@pabs3 nice! Thanks for the links! Looks like similar ideas. git-imerge in particular aims to do something very similar:

If conflicts are encountered, figure out exactly which pairs of commits conflict, and present the user with one pairwise conflict at a time for resolution.

and

Reduce the pain of resolving merge conflicts to its unavoidable minimum, by finding and presenting the smallest possible conflicts: those between the changes introduced by one commit from each branch.