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
  }

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.