stack

#!/usr/bin/env bash

state_file="$(realpath $(dirname "$0"))/.stack-state"
lock_index="$(realpath $(dirname "$0"))/.lock-index"
cache_index="$(realpath $(dirname "$0"))/.cache-index"
dir="$(realpath $(dirname $0)/ocaml)"

if [[ ! -d $dir ]]; then
  echo "Expect OCaml clone in $dir" >&2
  exit 1
fi

cd "$dir"

if ! git rev-parse --verify upstream/trunk &> /dev/null; then
  echo 'Could not find upstream/trunk' >&2
  exit 1
fi

if ! git rev-parse --verify relocatable-locks &> /dev/null; then
  if ! git rev-parse --verify origin/relocatable-locks &> /dev/null; then
    echo "origin/relocatable-locks not found?!" >&2
    exit 1
  fi
  git branch --track relocatable-locks origin/relocatable-locks
fi

function merge-base
{
  local base="$(git merge-base "$1" "$2")"
  # There's an error in the branching history for 4.13, possibly caused by PRs
  # merged shortly after it was branched. The effect is that there are two
  # "last commit before branching 4.13" commits in the history which causes the
  # common parent dd7927 to be selected. We manually amend this to 4.13's
  # merge-base.
  if [[ $base = 'dd7927e156b7cb2f9cb73d2d54a15a9c81921392' ]]; then
    base='621753f3eec9de91495a25723de00cef33a9e35a'
  fi
  echo "$base"
}

# Return status 0 only if the commit specified by $1 is based on a branch which
# is newer than the commit specified by $2 (i.e. cherry-picking $1 onto $2 would
# be a back-port, not a revert)
function is-backport
{
  local commit="$1"
  local target="$2"
  # The multicore merge history (from #10831) causes issues for `git merge-base`
  # $pre_10831 is the last commit on trunk before #10831 was merged. If that
  # commit is _not_ an ancestor of $target, then we use that instead of the tip
  # of trunk to work out the merge-base, as this avoids the complicated rebase
  # and merge history in #10831.
  local pre_10831='263a2a429c'
  if git merge-base --is-ancestor $pre_10831 "$target"; then
    local trunk='upstream/trunk'
  else
    local trunk=$pre_10831
  fi
  local target_sha="$(git rev-list -n 1 "$target")"
  local target_mergebase="$(merge-base "$target" $trunk)"
  local mergebase="$(merge-base "$commit" "$target")"
  if [[ $mergebase = $target_sha ]]; then
    # Commit is based on target!
    return
  elif [[ $mergebase = $target_mergebase ]]; then
    # The common point between $commit and $target is $target's merge-base with
    # trunk. That means $commit is newer, as otherwise the common point would
    # be the merge-base of $commit and trunk.
    return
  fi

  # This isn't a back-port
  return 1
}

# XXX At the moment, caching and locking _almost_ work, but there seem to be
#     some instances where rerere files can be missed.
use_caching=1
re_cache=0
declare -A SKIP_CACHE

menu=false
while true; do
  case "$1" in
    --cache)
      shift 1
      use_caching=1;;
    --re-cache)
      shift 1
      re_cache=1;;
    --no-cache)
      shift 1
      use_caching=0;;
    --skip-cache)
      SKIP_CACHE["$2"]=''
      shift 2;;
    --menu)
      shift 1
      menu=true
      break;;
    --is-backport)
      if is-backport "$2" "$3"; then
        echo -e "$2 is \e[97molder\e[0m than $3"
      else
        echo -e "$2 is in scope"
      fi
      exit 0;;
    *)
      break;;
  esac
done

if [[ -n $1 ]]; then
  if [[ $1 = ${1#@} ]]; then
    if ! git rev-parse --verify "$1" &> /dev/null; then
      echo "Lock not found: $1" >&2
      exit 1
    fi

    lock="$(git rev-parse "$1")"
    contained="$(git branch relocatable-locks --contains "$lock")"
    if [[ -z $contained ]]; then
      echo "Lock not found: $1" >&2
      exit 1
    fi

    git --work-tree=../.git/modules/ocaml restore --source=$lock --worktree -- rr-cache
    backports="$lock"
    lock="git show $lock:branches"

    if git show "$backports:config" &>/dev/null; then
      while read -r key value; do
        case $key in
          keep_changes)
            keep_changes="$value";;
          legacy_empty_commits)
            legacy_empty_commits="$value";;
          linear_commit_history)
            linear_commit_history="$value";;
          *)
            echo "Unexpected key in lock config file: $key"
            exit 1;;
        esac
      done < <(git show "$backports:config")
      if [[ -z $legacy_empty_commits && $keep_changes -eq 1 ]]; then
        # Slightly grim hack which affects locks c013d8555a, 590e211336 and
        # b5aa73d89c. These locks were committed where an empty commit followed
        # by an empty fixup resulted in an empty commit in the series. Newer
        # locks record legacy_empty_commits=0 explicitly. Although it affects
        # c013d8555a, there aren't any empty+empty-fixup commits in that lock.
        legacy_empty_commits=1
      fi
    else
      keep_changes=0
      legacy_empty_commits=0
      linear_commit_history=0
    fi

    rm -f ../branches
  else
    lock="$(realpath ${1#@})"
    lock="cat \"$lock\""
    rm -f ../branches
    cp "${1#@}" ../branches
    backports=''
    # XXX Hack!
    keep_changes=1
    legacy_empty_commits=0
    linear_commit_history=1
  fi
else
  lock=''
  backports=''
fi

start_time=$(date '+%Y-%m-%d %H:%M:%S')

declare -A HEADS

ALL_TARGETS=(trunk 5.4 5.3 5.2 5.1 5.0 4.14 4.13 4.12 4.11 4.10 4.09 4.08)

function branch
{
  if [[ $2 =~ upstream/ ]]; then
    BRANCHES+=("$1@${2#upstream/}")
  else
    BRANCHES+=("$1")
  fi
}

function fixup
{
  local upstream="$2"
  [[ $upstream != 'relocatable-base-trunk' ]] || upstream='upstream/trunk'
  if [[ "$3$upstream" =~ ^upstream/ ]]; then
    BRANCHES+=("$1@${upstream#upstream/}@fixup")
  else
    if [[ ${3:-0} -gt 0 ]]; then
      BRANCHES+=("$1@fixup~$3")
    else
      BRANCHES+=("$1@fixup")
    fi
  fi
}

if [[ -z $lock ]]; then

  if [[ ! -e ../menu ]]; then
    echo "Menu (../menu) not found!"
    exit 1
  fi

  . ../menu

  # The default is to preserve the Changes file
  keep_changes=1
  legacy_empty_commits=0
  linear_commit_history=1

  TARGETS=(trunk 5.4 5.3 5.2 5.1 5.0 4.14 4.13 4.12 4.11 4.10 4.09 4.08)

  # Check the branches all exist and collect the commits to stack
  for instruction in "${BRANCHES[@]}"; do
    [[ $instruction != 'stop-backporting' ]] || continue
    branch="${instruction%%@*}"
    if ! git rev-parse --verify $branch &> /dev/null; then
      if ! git rev-parse --verify origin/$branch &> /dev/null; then
        echo "Both $branch and origin/$branch do not exist!" >&2
        exit 1
      else
        git branch --track $branch origin/$branch
      fi
    fi
    if [[ -n ${HEADS[$branch]+x} ]]; then
      echo "$branch appears more than once in \$BRANCHES" >&2
      exit 1
    else
      HEADS["$instruction"]="$(git rev-parse $branch)"
    fi
  done

  fault=0
  for root in "${ALL_TARGETS[@]}"; do
    if ! git rev-parse --verify relocatable-base-$root &> /dev/null; then
      if ! git rev-parse --verify origin/relocatable-base-$root &> /dev/null; then
        echo "Target $root not found" >&2
        fault=1
        continue
      else
        git branch relocatable-base-$root origin/relocatable-base-$root
      fi
    fi
    HEADS["relocatable-base-$root"]="$(git rev-parse relocatable-base-$root)"
  done
  if ((fault)); then
    exit 1
  fi

  for instruction in "${BRANCHES[@]}" "${TARGETS[@]}"; do
    if [[ -z ${HEADS[$instruction]} ]]; then
      if [[ $instruction = 'stop-backporting' ]]; then
        echo "$instruction"
      else
        echo "relocatable-base-$instruction ${HEADS[relocatable-base-$instruction]}"
      fi
    else
      echo "$instruction ${HEADS[$instruction]}"
    fi
  done > ../branches

else
  TARGETS=()
  BRANCHES=()
  while read -r branch head; do
    if [[ $branch = ${branch#relocatable-base-} ]]; then
      BRANCHES+=($branch)
    else
      TARGETS+=(${branch#relocatable-base-})
    fi
    [[ -z $head ]] || HEADS[$branch]=$head
  done < <(eval "$lock")
fi

# At this point:
# - BRANCHES is an array of the all the branches to be consolidated
# - TARGETS is an array of all the targets to make (trunk, 5.3, etc.)
# - HEADS is an associative array mapping everything in BRANCHES to a sha

declare -A PROVENANCE
declare -A THIS_PROVENANCE
declare -A FIRST_BRANCH
function menu-info
{
  if [[ $menu = 'true' ]]; then
    if [[ $3 = ${3#* } ]]; then
      sha="$3"
    else
      sha="${3# }"
      sha="${sha%% *}"
    fi
    cmd="\e[34m$1\e[0m (${FIRST_BRANCH["$sha"]}): "
    if [[ $2 = 'skip' ]]; then
      cmd="$cmd\e[90mSkipping $3 as it's already present"
    else
      cmd="$cmd$2 \e[97m$3\e[0m"
    fi
    if [[ $3 = ${3#* } ]]; then
      echo -e "$cmd - $(git log --format='%s' -1 $3)"
    else
      echo -e "$cmd"
      for sha in $3; do
        echo "${branch//?/ }    $(git log --format='%s' -1 $sha)"
      done
    fi
    echo -ne '\e[0m'
  elif [[ $2 != 'skip' ]]; then
    for sha in $3; do
      PROVENANCE[$sha]="$branch"
      THIS_PROVENANCE[$sha]="$branch"
    done
  fi
}

function commit-basis
{
  base="$(git merge-base $1 upstream/trunk)"
  if [[ -z ${FIRST_BRANCH["$base"]} ]]; then
    for target in "${ALL_TARGETS[@]}" failed; do
      if [[ $target = 'failed' ]]; then
        echo "Unable to work out basis for $1"
        exit 1
      fi
      test_head="${HEADS["relocatable-base-$target"]}"
      if [[ -z $test_head ]]; then
        test_head="$(git merge-base upstream/$target upstream/trunk)"
      fi
      if is-backport "$1" "$test_head"; then
        base="$target"
        break
      fi
    done
  else
    base="${FIRST_BRANCH["$base"]}"
  fi
  for sha in "$@"; do
    FIRST_BRANCH["$sha"]="$base"
  done
}

declare -A PICKED
declare -A TOUCHED
declare -A TAKEN
TOUCHED['stop-backporting']=1
COMMANDS=()
COMMITS=()
WORKING=()
base_trunk="${HEADS['relocatable-base-trunk']}"
if [[ ! -e $state_file ]]; then
  # Remove files leftover by CTRL+C
  rm -f _log
  rm -rf autom4te.cache
  if [[ -n "$(git status --porcelain)" ]]; then
    echo 'The working tree is not clean' >&2
    exit 1
  fi

  if [[ -e "$(git rev-parse --git-dir)/REBASE_HEAD" ]]; then
    echo 'A rebase appears to be in progress?' >&2
    exit 1
  elif [[ -e "$(git rev-parse --git-dir)/CHERRY_PICK_HEAD" ]]; then
    echo 'A cherry-pick appears to be in progress' >&2
    exit 1
  elif [[ -e "$(git rev-parse --git-dir)/MERGE_HEAD" ]]; then
    echo 'A merge appears to be in progress' >&2
    exit 1
  fi

  git clean -dfX &> /dev/null

  if [[ $menu != 'true' ]]; then
    echo -n 'Calculating the menu... '
  fi
  for target in "${ALL_TARGETS[@]}"; do
    if [[ -n ${HEADS["relocatable-base-$target"]+x} ]]; then
      base="$(git merge-base ${HEADS["relocatable-base-$target"]} upstream/trunk)"
    else
      base="$(git merge-base upstream/$target upstream/trunk)"
    fi
    FIRST_BRANCH["$base"]="$target"
  done

  # Calculate the menu. First, determine the initial commit list from the
  # branches.
  for entry in "${BRANCHES[@]}"; do
    if [[ $entry = 'stop-backporting' ]]; then
      COMMITS+=('stop-backporting')
      continue
    fi
    upstream="${entry#*@}"
    branch="${entry%%@*}"
    if [[ $upstream = $entry ]]; then
      # $entry is just a branch name
      upstream='trunk'
    fi
    if [[ $upstream =~ ^fixup(~[0-9]+)?$ ]]; then
      # $entry is foo@fixup (single fixup with optional offset)
      count="${upstream#fixup~}"
      if [[ $count = $upstream ]]; then
        count=0
      fi
      commit="$(git log --format=%h -n 1 "${HEADS[$entry]}")"
      commit-basis "$commit"
      menu-info "$branch" "adjust $count $entry" "$commit"
      COMMITS+=("adjust $count $entry $commit")
    elif [[ $upstream =~ @fixup$ ]]; then
      # $entry is foo@upstream@fixup (fixups with root + optional Basis)
      # upstream refers to upstream/$upstream (at the moment) (at the moment)
      upstream="${upstream%@fixup}"
      commits=''
      count=-1
      while read -r entry; do
        commit="${entry%% *}"
        if [[ ${entry#* } = 'Basis' ]]; then
          continue
        fi
        commits="$commits $commit"
        ((count++))
      done < <(git log upstream/$upstream..${HEADS[$entry]} --format="%h %s" --reverse)
      commit-basis $commits
      menu-info "$branch" "adjust $count $branch" "$commits"
      COMMITS+=("adjust $count $branch$commits")
    else
      if [[ $upstream = 'trunk' ]]; then
        head="${HEADS["$entry"]}"
        if [[ $(git merge-base 'upstream/trunk' "$head") = $head ]]; then
          # This PR has been merged
          merge="$(git log --format='%H %P' --min-parents=2 upstream/trunk | grep -F " $head" | head -n 1 | cut -f1 -d' ')"
          if [[ -z $merge ]]; then
            echo "Graph interpretation error: $head is merged into upstream/trunk, but cannot find merge commit?">&2
            exit 1
          fi
          upstream="$(git merge-base "$merge~1" "$head")"
          #upstream="$base_trunk"
# If this case comes back in being relevant, try commenting it!
#        elif [[ -n $base_trunk && $(git merge-base "$base_trunk" "$head") = $base_trunk ]]; then
#          upstream="$base_trunk"
        else
          upstream='upstream/trunk'
        fi
      else
        #upstream="${HEADS["relocatable-base-$upstream"]}"
        upstream="upstream/$upstream"
      fi
      this_basis=''
      while read -r entry; do
        commit="${entry%% *}"
        bootstrap=0
        diffs=0
        while read -r path; do
          case "$path" in
            boot/ocaml*) bootstrap=1;;
            *) diffs=1;;
          esac
        done < <(git diff-tree --no-commit-id --name-only -r "$commit")
        if [[ -z $this_basis ]]; then
          commit-basis "$commit"
          this_basis="$base"
        else
          FIRST_BRANCH["$commit"]="$this_basis"
        fi
        if [[ $bootstrap -eq 1 ]]; then
          if [[ $diffs -eq 0 ]]; then
            menu-info "$branch" "bootstrap" "$commit"
            COMMITS+=("bootstrap $commit")
          else
            menu-info "$branch" "coreboot" "$commit"
            COMMITS+=("coreboot $commit")
          fi
        else
          if [[ -n ${PICKED["$commit"]} ]]; then
            menu-info "$branch" "skip" "$commit"
          else
            menu-info "$branch" "pick" "$commit"
            COMMITS+=("pick $commit")
            PICKED["$commit"]='1'
          fi
        fi
      done < <(git log $upstream..${HEADS[$entry]} --format='%h %s' --reverse)
    fi
  done
  if [[ $menu != 'true' ]]; then
    echo 'done!'
  fi

  # Now generate commands for each target branch
  for root in "${TARGETS[@]}"; do
    COMMANDS+=("branch relocatable-base-$root")
  done

  # Eliminate the reflog caches, now that we're ready to go
  rm -f ../.reflog-all ../.reflog-bootstrap
else
  if [[ -n "$(git ls-files --exclude-standard --others)" ]]; then
    echo 'Untracked files in the working directory' >&2
    exit 1
  elif [[ -n "$(git diff --stat)" ]]; then
    echo 'Unstaged changes in the working directory' >&2
    exit 1
  fi

  rm -f ../.stack-branches

  # Load the stack state
  phase=0
  while read -r line; do
    case ${line%% *} in
      pick|bootstrap|coreboot|fixup|adjust|next|stop-backporting)
        if ((phase)); then
          WORKING+=("$line")
        else
          COMMITS+=("$line")
        fi;;
      commit)
        COMMANDS+=("$line")
        phase=1;;
      branch)
        COMMANDS+=("$line");;
      target)
        target="${line#* }";;
      target-branch)
        target_branch="${line#* }";;
      touched)
        TOUCHED["${line#* }"]=1;;
      taken)
        TAKEN["${line#* }"]=1;;
      lock)
        echo "${line#* }" >> ../.stack-branches;;
      cherry-stamp)
        cherry_stamp="${line#* }";;
      start)
        start_time="${line#* }";;
      provenance)
        line="${line#* }"
        PROVENANCE[${line% *}]="${line#* }";;
      first)
        line="${line#* }"
        FIRST_BRANCH[${line% *}]="${line#* }";;
      *)
        echo "Unrecognised command: $line" >&2
        phase=2;;
    esac
  done < <(cat "$state_file")

  if [[ $phase -gt 1 ]]; then
    exit 1
  fi

  if diff -q ../branches ../.stack-branches > /dev/null ; then
    rm ../.stack-branches
  else
    echo "Branches appear to have been altered:"
    diff ../.stack-branches ../branches
    exit 1
  fi

  rm "$state_file"
fi

if [[ $menu = 'true' ]]; then
  exit 0
fi

rm -f "$lock_index"
if [[ -e ../branches ]]; then
  mkdir -p lock-temp
  cd lock-temp
  mv ../../branches .
  GIT_INDEX_FILE="$lock_index" git --work-tree=. add -f branches
  echo "keep_changes $keep_changes" > config
  echo "legacy_empty_commits $legacy_empty_commits" >> config
  echo "linear_commit_history $linear_commit_history" >> config
  GIT_INDEX_FILE="$lock_index" git --work-tree=. add -f config
  cd ..
  rm -rf lock-temp
fi

function abort
{
#  echo "Branch: $branch for $target"
  echo "  $action"
  {
    for sha in "${!PROVENANCE[@]}"; do
      echo "provenance $sha ${PROVENANCE[$sha]}"
    done;
    for sha in "${!FIRST_BRANCH[@]}"; do
      echo "first $sha ${FIRST_BRANCH[$sha]}"
    done;
    for branch in "${!TOUCHED[@]}"; do
      echo "touched $branch"
    done;
    for branch in "${!TAKEN[@]}"; do
      echo "taken $branch"
    done;
    echo "start $start_time"
    echo "cherry-stamp $cherry_stamp"
    if ((!backporting)); then
      echo 'stop-backporting'
    fi
    for commit in "${COMMITS[@]}"; do
      echo "$commit"
    done;
    echo "target $target";
    echo "target-branch $target_branch";
    echo "commit $instr";
    for instruction in "${BRANCHES[@]}" "${TARGETS[@]}"; do
      if [[ -z ${HEADS[$instruction]} ]]; then
        if [[ $instruction = 'stop-backporting' ]]; then
          echo "lock $instruction"
        else
          echo "lock relocatable-base-$instruction ${HEADS[relocatable-base-$instruction]}"
        fi
      else
        echo "lock $instruction ${HEADS[$instruction]}"
      fi
    done
  } > "$state_file"
  aborting=1
}

function display-with-provenance
{
  local sha="$2"
  local provenance="${PROVENANCE["$sha"]}"
  if [[ ${provenance#@} = $provenance ]]; then
    if [[ -z $provenance ]]; then
      echo -e "$1 (\e[5;31mNo - we got no provenance\e[0m) $3"
    else
      echo -e "$1 (from \e[34m$provenance\e[0m) $3"
    fi
  else
    local via=()
    local fixups=()
    if [[ ${provenance#*+} != $provenance ]]; then
      fixups+=("${provenance#*+}")
      provenance="${provenance%+*}"
    fi
    local chain="$provenance"
    local last_provenance=''
    if [[ ${PROVENANCE[@$sha]} != $target_branch ]]; then
      last_provenance="${PROVENANCE[@$sha]}"
      via+=($last_provenance)
    fi
    while [[ ${provenance#@} != $provenance ]]; do
      sha="${provenance#@}"
      if [[ ${PROVENANCE[$provenance]} != $last_provenance ]]; then
        last_provenance="${PROVENANCE[$provenance]}"
        if [[ -n $last_provenance ]]; then
          via+=("$last_provenance")
        fi
      fi
      provenance="${PROVENANCE["$sha"]}"
      if [[ ${provenance#*+} != $provenance ]]; then
        fixups+=("${provenance#*+}")
        provenance="${provenance%+*}"
      fi
      chain="$chain -> $provenance"
    done
    case ${#via[@]} in
      0) via_seg='';;
      1) via_seg=" via \e[34m${via[0]}\e[0m";;
      2) via_seg=" via \e[34m${via[0]}\e[0m -> \e[34m${via[1]}\e[0m";;
      3) via_seg=" via \e[34m${via[0]}\e[0m -> \e[34m${via[1]}\e[0m -> \e[34m${via[2]}\e[0m";;
      *)
        local count=${#via[@]}
        ((count-=2))
        via_seg=" via \e[34m${via[0]}\e[0m -> ... \e[34m$count more\e[0m ... -> \e[34m${via[-1]}\e[0m";;
    esac
    if [[ -z $provenance ]]; then
      provenance="\e[5;31m<broken provenance chain: $chain>\e[0m"
    fi
    if [[ ${#via[@]} -le 1 && ${#fixups[@]} -eq 0 ]]; then
      echo -e "$1 (from \e[34m$provenance\e[0m$via_seg) $3"
    else
      echo -e "$1 $3"
      case ${#fixups[@]} in
        0)
          echo -e "  from \e[34m$provenance\e[0m$via_seg";;
        1)
          echo -e "  from \e[34m$provenance\e[0m with \e[34m${PROVENANCE[${fixups[0]}]}\e[0m@\e[97m${fixups[0]}\e[0m$via_seg";;
        *)
          echo -ne "  from \e[34m$provenance\e[0m with"
          local cycle=1
          local sep=' '
          for fixup in "${fixups[@]}"; do
            if ((cycle % 3 == 0)); then
              echo
              echo -n '     '
              sep='+ '
            fi
            echo -ne "$sep\e[34m${PROVENANCE[$fixup]}\e[0m@\e[97m$fixup\e[0m"
            sep=' + '
            ((cycle++))
          done
          echo
          if [[ -n $via_seg ]]; then
            echo -e "  $via_seg"
          fi;;
      esac
    fi
  fi
}

stamping=0
function reset-committer
{
  info="$(git log -1 --format='%ct')"
  current_stamp="${info% *}"
  info="$(git log -1 --format='%at %ad' --date='format:%z')"
  this_stamp="${info% *}"
  this_offset="${info#* }"
  info="$(git log -1 --format='%ct %cd' --date='format:%z' HEAD~1)"
  last_stamp="${info% *}"
  last_stamp=$((last_stamp + 1))
  last_offset="${info#* }"
  if [[ $stamping -eq 0 ]]; then
    stamping=1
    last_stamp="$this_stamp"
    last_offset="$this_offset"
  fi
  if [[ $this_stamp -ge $last_stamp ]]; then
    last_stamp="$this_stamp"
    last_offset="$this_offset"
  fi
  if [[ $linear_commit_history -eq 1 ]]; then
    if [[ $current_stamp != $last_stamp ]]; then
      if ! GIT_COMMITTER_DATE="$last_stamp $last_offset" git commit --allow-empty --amend --no-verify --no-edit &> /dev/null; then
        GIT_COMMITTER_DATE="$last_stamp $last_offset" git commit --allow-empty --amend --no-verify --no-edit
        echo "Resetting the committer date on the last commit has failed" >&2
        exit 1
      fi
      return 1
    fi
  else
    if ! git rebase --committer-date-is-author-date HEAD~1 &> /dev/null; then
      git rebase --committer-date-is-author-date HEAD~1
    fi
  fi
}

declare -A THIS_REMAP
function rebase
{
  while [[ ${#WORKING[@]} -gt 0 ]]; do
    instr="${WORKING[0]}"
    WORKING=("${WORKING[@]:1}")
    sha="${instr#* }"
    verb="${instr%% *}"
    case $verb in
      stop-backporting)
        last_provenance='_not_a_provenance'
        backporting=0;;
      next)
        if ((backporting)); then
          COMMITS+=("$sha")
        fi;;
      pick|fixup)
        if [[ ${PROVENANCE[$sha]} != $last_provenance ]]; then
          if [[ ${#SKIPPED} -gt 0 ]]; then
            for commit in "${SKIPPED[@]}"; do
              if ((backporting)); then
                if [[ -z ${TAKEN[${PROVENANCE[$commit]}]} ]]; then
                  echo -e "Keeping \e[97m$commit\e[0m (from \e[34m$last_provenance\e[0m) as the branch hasn't been used"
                  THIS_REMAP["$commit"]="$commit"
                  COMMITS+=("pick $commit")
                else
                  echo -e "Dropping \e[97m$commit\e[0m (from \e[34m$last_provenance\e[0m) as other commits from the branch have been used"
                fi
              fi
            done
          fi
          last_provenance='_not_a_provenance'
          SKIPPED=()
        fi
        if [[ $verb = 'fixup' ]]; then
          this_subject="$(git log -n 1 --format='%s' $sha)"
          if [[ $this_subject != "$last_subject" ]]; then
            this_subject="\e[33m$this_subject\e[0m (different subject)"
          fi
          display-with-provenance "fixup \e[97m$sha\e[0m" "$sha" "on \e[97m$(git rev-parse --short $target_branch)\e[0m of $target_branch - $this_subject"
          msg="$(git rev-parse --short HEAD)"
          amend='--amend'
          next=''
        else
          current_pick="$sha"
          last_subject="$(git log -n 1 --format='%s' $sha)"
          display-with-provenance "cherry-pick \e[97m$sha\e[0m" "$sha" "to $target_branch - $last_subject"
          msg="$sha"
          amend=''
          next='pick $head'
        fi
        if cherry-pick "$sha"; then
          commit "$msg" "$next" "$instr" "$amend"
        fi;;
      bootstrap)
        current_pick="$sha"
        last_provenance='_not_a_provenance'
        SKIPPED=()
        bootstrap_msg="Bootstrap \e[97m$sha\e[0m to $target_branch ($(git rev-parse --short HEAD))"
        cherry_stamp="$(date '+%Y-%m-%d %H:%M:%S.%N')"
        display-with-provenance "Bootstrap \e[97m$sha\e[0m" "$sha" "to $target_branch ($(git rev-parse --short HEAD))"
        if [[ ! -e ../.reflog-bootstrap ]]; then
          echo -n 'Scouring reflog for previous bootstraps: '
          git reflog --format='%h %p' -- boot/ocamlc > ../.reflog-bootstrap
          echo 'done!'
        fi
        cached="$(grep " $(git rev-parse --short HEAD)$" ../.reflog-bootstrap | head -n 1 | cut -f1 -d' ')"
        if [[ -n $cached ]] && git diff-tree --no-commit-id --name-only -r "$cached" | grep -Fq 'boot/ocaml'; then
          git merge --ff-only $cached &> /dev/null
          if [[ -s boot/ocamlc ]]; then
            echo "Re-using previous bootstrap computation from $cached"
            if ! reset-committer; then
              new="$(git rev-parse --short HEAD)"
              echo "  Reset committer information on $cached to give $new"
              cached="$new"
            fi
            if ((backporting)); then
              THIS_REMAP["$current_pick"]="$cached"
              COMMITS+=("bootstrap $cached")
              PROVENANCE["$cached"]="@$sha"
              PROVENANCE["@$cached"]="$target_branch"
              THIS_PROVENANCE["$cached"]="@$sha"
              THIS_PROVENANCE["@$cached"]="$target_branch"
            fi
          else
            git reset --hard HEAD~1 &> /dev/null
            commit "$sha" 'bootstrap $head' "$instr"
          fi
        else
          BOOTSTRAPS+=("$bootstrap_msg")
          echo "  Bootstrapping..."
          if ! ./configure --disable-native-compiler --disable-ocamldoc --disable-ocamltest --disable-debugger > _log 2>&1; then
            cat _log
            rm _log
            abort
            echo "configure failed: either fix or erase $state_file"
          elif ! make -j coldstart > _log 2>&1; then
            cat _log
            rm _log
            abort
            echo "make coldstart failed: either fix or erase $state_file"
            echo 'Do _not_ bootstrap'
          elif ! make -j coreall > _log 2>&1; then
            cat _log
            rm _log
            abort
            echo "make coreall failed: either fix or erase $state_file"
            echo 'Do _not_ bootstrap'
          elif ! make -j bootstrap > _log 2>&1; then
            cat _log
            rm _log
            abort
            git reset -- boot/ocaml* &> /dev/null
            git checkout -- boot/ocaml* &> /dev/null
            echo "make bootstrap failed: either fix or erase $state_file"
            echo 'Do _not_ bootstrap'
          else
            rm _log
            git clean -dfX &> /dev/null
            # OCaml 4.06 and earlier
            if [[ -e boot/ocamldep ]]; then
              git add -- boot/ocamldep
            fi
            git add -- boot/ocamlc boot/ocamllex
            if [[ -z "$(git status --porcelain)" ]]; then
              # Bootstrap with no change - record a special commit to cache this
              truncate --size 0 boot/ocamlc
              git add -- boot/ocamlc
              git commit -m 'Bootstrap (empty - for caching)' --no-verify &> /dev/null
              git reset --hard HEAD~1 &> /dev/null
            fi
            commit "$sha" 'bootstrap $head' "$instr"
          fi
        fi;;
      coreboot)
        if [[ -z $current_pick ]]; then
          current_pick="$sha"
        fi
        last_provenance='_not_a_provenance'
        SKIPPED=()
        coreboot_msg="Coreboot \e[97m$sha\e[0m to $target_branch ($(git rev-parse --short HEAD)) - $(git log -n 1 --format='%s' $sha)"
        display-with-provenance "Coreboot \e[97m$sha\e[0m" "$sha" "to $target_branch ($(git rev-parse --short HEAD)) - $(git log -n 1 --format='%s' $sha)"
        if cherry-pick "$sha" 'boot/ocaml*' 'Do _not_ bootstrap'; then
          next="${WORKING[0]}"
          if [[ ${next%% *} = 'fixup' ]]; then
            echo "  Deferring coreboot - next command is a fixup"
            deferred_coreboot="$current_pick"
            if ! git commit --reuse-message="$sha" &> _log; then
              cat _log
              rm _log
              abort
              echo "Commit failed - please fix and re-run $0"
              echo 'Do _not_ bootstrap'
            else
              rm _log
              reset-committer
              head="$(git rev-parse --short HEAD)"
              #PROVENANCE["$head"]="@$sha"
              #PROVENANCE["@$head"]="$target_branch"
              if ((backporting)); then
                COMMITS+=("coreboot $head")
                PROVENANCE["$head"]="@$sha"
                THIS_PROVENANCE["$head"]="@$sha"
              fi
            fi
          else
            coreboot "$sha" "$coreboot_msg"
          fi
        fi;;
      *)
        echo "Internal error: unrecognised command $instr" >&2
        exit 1;;
    esac
    if ((aborting)); then
      for instr in "${WORKING[@]}"; do
        echo "$instr" >> "$state_file"
      done
      WORKING=()
    fi
  done
}

function reconfigure
{
  reconfigure=0
  while read -r item; do
    case $item in
      configure)
        if [[ $reconfigure -eq 0 ]]; then
          reconfigure=1
        fi;;
      configure.ac|aclocal.m4|build-aux/*)
        if grep -q '^<<<<<' $item; then
          reconfigure=-1
        elif [[ $reconfigure -eq 0 ]]; then
          reconfigure=1
        fi;;
    esac
  done < <(git diff --name-only --cached)
  if [[ reconfigure -eq 1 ]]; then
    echo -e "  \e[90mconfigure.ac has been changed - regenerating configure\e[0m"
    if [[ -e tools/autogen ]]; then
      autogen=tools/autogen
    else
      autogen=./autogen
    fi
    rm -f configure
    if [[ $(sed -ne 's/^AC_PREREQ(\[\(.*\)\])$/\1/p' configure.ac) =~ ^(2.69)?$ ]]; then
      if grep -q '^autoconf ' $autogen; then
        restore="sed -i -e 's/^\${1-autoconf}/autoconf/' $autogen"
        sed -i -e 's/^autoconf/${1-autoconf}/' $autogen
      elif grep -q '[^$]autoconf -' $autogen; then
        restore="sed -i -e 's/\${1-autoconf}/autoconf/' $autogen"
        sed -i -e 's/autoconf -/${1-autoconf} -/' $autogen
      else
        restore=''
      fi
      autogen="$autogen autoconf2.69"
    fi
    if $autogen; then
      eval $restore
      if [[ -e utils/config.mlp ]]; then
        if ! grep -q '^<<<<<' utils/config.mlp ; then
          git add -- utils/config.mlp
        fi
      fi
      if [[ -e utils/config.common.ml ]]; then
        if [[ -z "$(git status --porcelain | fgrep 'DU utils/config.common.ml')" ]]; then
          if ! grep -q '^<<<<<' utils/config.common.ml ; then
            git add -- utils/config.common.ml
            rm -f utils/config.common.ml.in
          fi
        fi
      fi
      if [[ -e utils/config.common.ml.in ]]; then
        if [[ -z "$(git status --porcelain --no-renames | grep '\(DU\|A \) utils/config.common.ml.in')" ]]; then
          case "$target" in
            relocatable-base-trunk|relocatable-base-5.4|relocatable-base-5.3|relocatable-base-5.2)
              ;;
            *)
              echo $target
              git status --porcelain
              exit 1;;
          esac
          if ! grep -q '^<<<<<' utils/config.common.ml.in ; then
            git add -- utils/config.common.ml.in
          fi
        fi
      fi
      git add -- configure VERSION
    else
      eval $restore
      abort
      echo "Regenerating configure failed - please fix and re-run $0"
      return 1
    fi
  fi
}

function rerere-hash
{
  # This facility is crude, but it should be adequate to compute rerere hashes
  awk -f- "$1" <<'EOF'
/^(<<<<<<<|=======)/ {
  in_hunk++;
  next;
}

/^>>>>>>>/ {
  if (one > two) {
    printf("%s\0%s\0", two, one);
  } else {
    printf("%s\0%s\0", one, two);
  }
  in_hunk=0;
  one="";
  two="";
  next;
}

{
  if (in_hunk == 1) {
    one = one $0 "\n";
  } else if (in_hunk == 2) {
    two = two $0 "\n";
  }
}
EOF
}

declare -A RERERE
function cherry-pick
{
  unset RERERE
  declare -gA RERERE
  local conflicts=0
  cherry_stamp="$(date '+%Y-%m-%d %H:%M:%S.%N')"
  local displaying=0
  while [[ -n "$(find ../.git/modules/ocaml/rr-cache -type f -newermt "$cherry_stamp")" ]]; do
    cherry_stamp="$(date '+%Y-%m-%d %H:%M:%S.%N')"
    if ((!displaying)); then
      echo -n 'Waiting for rr-cache to stabilize: '
      displaying=1
    fi
    sleep 0.1
    echo -n '.'
  done
  if ((displaying)); then
    echo
  fi
  # Initially cherry-pick without using rerere
  git -c rerere.enabled=false cherry-pick --no-commit "$1" &> /dev/null
  # Now scan the status for any files with conflicts and, if found, compute
  # the rerere hash
  while read -r status; do
    file=${status:3}
    case ${status:0:2} in
      UU|AA)
        if grep -q '^<<<<<' "$file" ; then
          rerere_hash=$(rerere-hash "$file" | sha1sum | cut -f1 -d' ')
          if [[ -n ${RERERE[$rerere_hash]} ]]; then
            # Conflicting IDs - assume stronger matching here
            RERERE[$rerere_hash]='*'
          else
            RERERE[$rerere_hash]=$file
          fi
          conflicts=1
        fi;;
    esac
  done < <(git status --porcelain 2>/dev/null)
  # Only if there were conflicts, repeat the cherry-pick, this time with rerere
  # turned on.
  if ((conflicts)); then
    git reset --hard HEAD &> /dev/null
    git cherry-pick --no-commit "$1" &> /dev/null
  fi
  if [[ $keep_changes -eq 0 ]]; then
    git reset -- Changes $2 &> /dev/null
    git checkout -- Changes $2 &> /dev/null
  fi
  if reconfigure; then
    while read -r status; do
      case ${status:0:2} in
        DU)
          git reset -- "${status:3}" &> /dev/null
          TO_DELETE+=("${status:3}");;
        UU|AA)
          if ! grep -q '^<<<<<' "${status:3}" ; then
            git add -- "${status:3}"
          else
            git reset -- "${status:3}" &>/dev/null
          fi;;
      esac
    done < <(git status --porcelain)

    if [[ -n $(git diff --stat) ]]; then
      abort
      git status
      echo
      echo "Please resolve changes, add to the index and re-run $0"
      if [[ -n $3 ]]; then
        echo "$3"
      fi
      return 1
    else
      return 0
    fi
  else
    return 1
  fi
}

function coreboot
{
  head_sha="$(git rev-parse --short HEAD)"
  # Check the cache
  if [[ -z "$(git status --porcelain)" ]]; then
    THIS_REMAP["$current_pick"]=''
    current_pick=''
    echo "  Commit skipped - it's empty"
    return
  fi
  if ! git commit --reuse-message="$1" &> _log; then
    cat _log
    rm _log
    abort
    echo "Commit failed for "$1" - please fix and re-run $0"
  else
    rm _log
    reset-committer
    code_sha="$(git rev-parse --short HEAD)"
    show-rr-resolutions "$cherry_stamp" "$head"
    if [[ ! -e ../.reflog-all ]]; then
      echo -n 'Absorbing all the energy of the Time Vortex: '
      git reflog --format='%h %p' > ../.reflog-all
      echo 'done!'
    fi
    for cached in $(grep " ${code_sha}\$" ../.reflog-all | cut -f1 -d' '); do
      if [[ -n $cached ]] && git diff-tree --no-commit-id --name-only -r "$cached" | grep -Fq 'boot/ocaml'; then
        # This code commit has a bootstrap parent - so we can search for a unified commit
        combined=''
        while read -r commit; do
          if git diff --quiet $cached $commit; then
            combined="$commit"
            break;
          fi
        done < <(grep " ${head_sha}\$" ../.reflog-all | cut -f1 -d' ' | sort | uniq)
        if [[ -n $combined ]] && git diff-tree --no-commit-id --name-only -r "$combined" | grep -Fq 'boot/ocaml'; then
          echo "  Re-using previous coreboot computation from $combined"
          git reset --hard $combined &> /dev/null
          if ! reset-committer; then
            new="$(git rev-parse --short HEAD)"
            echo "  Reset committer information on $combined to give $new"
            combined="$new"
          fi
          if ((backporting)); then
            THIS_REMAP["$current_pick"]="$combined"
            COMMITS+=("coreboot $combined")
            PROVENANCE["$combined"]="@$1"
            PROVENANCE["@$combined"]="$target_branch"
            THIS_PROVENANCE["$combined"]="@$1"
            THIS_PROVENANCE["@$combined"]="$target_branch"
          fi
          current_pick=''
          return
        fi
      fi
    done
    git reset --hard $head_sha &> /dev/null
    if ! ./configure --disable-native-compiler --disable-ocamldoc --disable-ocamltest --disable-debugger > _log 2>&1; then
      cat _log
      rm _log
      abort
      echo "configure failed: either fix or erase $state_file"
      return
    fi
    BOOTSTRAPS+=("$2")
    echo '  Warming up...'
    if ! make -j coldstart > _log 2>&1; then
      cat _log
      rm _log
      abort
      echo "make coldstart failed: either fix or erase $state_file"
      return
    fi
    rm -f _log
    echo '  Building...'
    if ! git merge --ff-only $code_sha &> /dev/null || \
       ! { if git diff-tree --no-commit-id --name-only -r "$code_sha" | grep -Fxq configure; then \
             ./configure --disable-native-compiler --disable-ocamldoc --disable-ocamltest --disable-debugger; \
           else \
             ./config.status;
           fi; \
           make -j coreall ; } > _log 2>&1 ; then
      cat _log
      rm _log
      git reset --hard $head_sha &> /dev/null
      git cherry-pick --no-commit $code_sha &> /dev/null
      abort
      echo "make coreall failed: either fix or erase $state_file"
      echo 'Do _not_ bootstrap'
      return
    fi
    echo '  Bootstrapping...'
    if ! make -j bootstrap > _log 2>&1; then
      cat _log
      rm _log
      git reset --hard $head_sha &> /dev/null
      git cherry-pick --no-commit $code_sha &> /dev/null
      abort
      echo "make bootstrap failed: either fix or erase $state_file"
      echo 'Do _not_ bootstrap'
    else
      rm _log
      git clean -dfX &> /dev/null
      # OCaml 4.06 and earlier
      if [[ -e boot/ocamldep ]]; then
        git add -- boot/ocamldep
      fi
      git add -- boot/ocamlc boot/ocamllex
      if ! git commit -m 'Bootstrap' &> _log; then
        cat _log
        rm _log
        abort
        echo "Commit failed - please fix and re-run $0"
      else
        rm -f _log
        reset-committer
        boot_sha="$(git rev-parse --short HEAD)"
        git reset --hard HEAD~1 &> /dev/null
        git cherry-pick --no-commit $boot_sha &> /dev/null
        git commit --reuse-message="$1" --amend &> /dev/null
        reset-committer
        head="$(git rev-parse --short HEAD)"
        if ((backporting)); then
          THIS_REMAP["$current_pick"]="$head"
          COMMITS+=("coreboot $head")
          PROVENANCE["$head"]="@$1"
          PROVENANCE["@$head"]="$target_branch"
          THIS_PROVENANCE["$head"]="@$1"
          THIS_PROVENANCE["@$head"]="$target_branch"
        fi
        current_pick=''
      fi
    fi
  fi
}

declare -A THIS_USES
function show-rr-resolutions
{
  if [[ -d ../.git/modules/ocaml/rr-cache ]]; then
    for file in $(find ../.git/modules/ocaml/rr-cache -type f -newermt "$1" -name postimage\*); do
      if [[ -z ${THIS_USES["$file"]+x} ]]; then
        THIS_USES["$file"]=1
      fi
      rr_cache_hash="$(basename "$(dirname "$file")")"
      in_tree="${RERERE[$rr_cache_hash]}"
      if [[ $in_tree = '*' ]]; then
        # Several files collide over this resolution. Hope that the match is
        # exact, rather than having to resort to a 3-way merge test
        in_tree="$(git ls-tree -r "$(git log -1 --format='%T' "$2")" | sed -ne 's/^[^ ]* [^ ]* '"$(git hash-object $file)"'\t//p')"
      fi
      if [[ -z $in_tree ]]; then
        echo -e "  \e[31mUnclear why $file was used\e[0m"
      else
        case "$in_tree" in
          configure)
            # configure is always regenerated anyway if dependencies are touched
            # byt ehc ommit, so rerere isn't adding much.
            ;;
          *)
            # Changes is automatically stubbed out during cherry-picking and
            if [[ $in_tree = "Changes" && $keep_changes -eq 0 ]]; then
              continue
            else
              echo -e "  \e[90m$in_tree corrected using $file\e[0m"
            fi;;
        esac
      fi
    done
  fi
}

declare -A FIXUP_NEXT
last_provenance='_not_a_provenance_'
SKIPPED=()
TO_DELETE=()
function commit
{
  for file in "${TO_DELETE[@]}"; do
    rm -f "$file"
  done
  TO_DELETE=()
  this_provenance="${PROVENANCE["$1"]}"
  if [[ -z "$(git status --porcelain)" && -z "${FIXUP_NEXT[$1]}" ]]; then
    if git commit --allow-empty -m Empty &> /dev/null; then
      git reset --hard HEAD~1 &> /dev/null
    fi
    show-rr-resolutions "$cherry_stamp" "$(git rev-parse --short HEAD)"
    if [[ $this_provenance != $last_provenance ]]; then
      if [[ $this_provenance = ${this_provenance#@*} ]] && ((backporting)); then
        last_provenance="$this_provenance"
        SKIPPED=("$1")
      else
        last_provenance='_not_a_provenance'
        SKIPPED=()
      fi
    elif [[ ${#SKIPPED} -gt 0 ]]; then
      SKIPPED+=("$1")
    fi
    echo -e "  Commit skipped - it's empty"
    if ((backporting)); then
      if [[ -z $4 ]]; then
        THIS_REMAP["$current_pick"]=''
      fi
    fi
    current_pick=''
    head="$(git rev-parse --short HEAD)"
  elif git diff --cached --exit-code --quiet HEAD~1 && [[ ${3% *} = 'fixup' ]]; then
    if [[ -z $4 ]]; then
      echo "Internal error: given that \${3% *} = 'fixup'; expected \$4 = --amend, but it's '$4'" >&2
      exit 1
    elif [[ -n $2 ]]; then
      echo "Internal error: given a fixup creating an empty commit, didn't expect next commands, but \$2 = '$2'" >&2
      exit 1
    fi
    # This is a fixup which now creates an empty commit - delete the previous
    # commit from the run
    unset 'COMMITS[-1]'
    git reset --hard HEAD~1 &> /dev/null
    echo -e "  Commit reverted - it's now empty"
    head="$(git rev-parse --short HEAD)"
    if ((backporting)); then
      THIS_REMAP["$current_pick"]=''
    fi
    current_pick=''
  else
    if [[ $this_provenance = $last_provenance ]]; then
      SKIPPED=()
    fi
    if ! git commit --allow-empty --reuse-message="$1" $4 &> _log; then
      cat _log
      rm _log
      abort
      echo "Commit failed - please fix and re-run $0"
      return
    fi
    rm -f _log
    reset-committer
    head="$(git rev-parse --short HEAD)"
    if [[ ${3% *} = 'fixup' ]]; then
      prev_sha="${COMMITS[-1]#* }"
      PROVENANCE["$head"]="@$prev_sha+${3#* }"
      THIS_PROVENANCE["$head"]="@$prev_sha+${3#* }"
    elif [[ $head != $1 ]]; then
      PROVENANCE["$head"]="@$1"
      THIS_PROVENANCE["$head"]="@$1"
    fi
    PROVENANCE["@$head"]="$target_branch"
    THIS_PROVENANCE["@$head"]="$target_branch"
    show-rr-resolutions "$cherry_stamp" "$head"
    #echo "Committed HEAD $head"
    TAKEN["$this_provenance"]=1
    if ((backporting)); then
      THIS_REMAP["$current_pick"]="$head"
    fi
    if [[ ! "${WORKING[0]}" =~ ^fixup' ' ]]; then
      current_pick=''
    fi
    if [[ -n $2 ]]; then
      eval "com=\"$2\""
      if ((backporting)); then
        COMMITS+=("$com")
      fi
    else
      if ((backporting)); then
        previous="${COMMITS[-1]}"
        COMMITS[-1]="${previous%% *} $head"
      fi
    fi
  fi
  if [[ -z $2 ]]; then
    previous="${COMMITS[-1]}"
    if [[ ${previous%% *} = 'coreboot' ]]; then
      echo "  Now executing deferred coreboot"
      current_pick="$deferred_coreboot"
      # It's slightly simpler just repeat the coreboot commit rather than
      # threading this through the entire fixup logic that it needs to
      # coldstart with HEAD~1. The changes would either need stashing or
      # committing in stages, etc. which muddles the error code.
      # Throw this commit away
      git reset --hard HEAD~1 &> /dev/null
      # Remove the previous coreboot from COMMITS
      COMMITS=("${COMMITS[@]:0:$((${#COMMITS[@]} - 1))}")
      # Add this commit to be coreboot'd now
      WORKING=("coreboot $head" "${WORKING[@]}")
    fi
  fi
}

# Useful loop for identifying branches needing rebasing
#our_base="$(git rev-parse relocatable-base-trunk)"
#our_base='d98fd806573088994b0ab60de032d7d54221488f'
#for entry in "${BRANCHES[@]}"; do
#  base="$(merge-base ${entry%%@*} upstream/trunk)"
#  if [[ $base = $our_base ]]; then
#    echo "$entry: $base"
#  fi
#done
#exit 0

# The main loop iterates over COMMANDS, which consists of branch commands and
# possibly (if recovering from a failure) a commit command. Each branch pours
# all the commands from COMMITS into WORKING (with any commits which are not yet
# required buried in a next command). The rebase function then iterates over
# the WORKING set which carries out the instructions while moving the results
# back to COMMITS.

declare -A ALL_REMAPS
test_WORKING=()
function apply-cache
{
  test_WORKING=()
  for cmd in "${WORKING[@]}"; do
    if [[ $cmd = 'stop-backporting' ]]; then
      break
    fi
    verb="${cmd%% *}"
    sha="${cmd#* }"
    case $verb in
      next)
        test_WORKING+=("$sha");;
      fixup)
        ;;
      *)
        case $verb,${ALL_REMAPS[$sha]} in
          pick,|coreboot,|bootstrap,)
            ;;
          *)
            test_WORKING+=("$verb ${ALL_REMAPS[$sha]}");;
        esac;;
    esac
  done
}

debug_new_mechanism=0
use_new_mechanism=1

declare -A THIS_TOUCHED
BOOTSTRAP=()
aborting=0
while [[ ${#COMMANDS[@]} -gt 0 ]]; do
  instr="${COMMANDS[0]}"
  COMMANDS=("${COMMANDS[@]:1}")
  arg="${instr#* }"
  case ${instr%% *} in
    commit)
      git clean -dfX &> /dev/null
      verb="${arg% *}"
      instr="$arg"
      if [[ $verb = 'coreboot' ]]; then
        coreboot "${arg#* }"
      else
        if [[ $verb = 'fixup' ]]; then
          msg="$(git rev-parse --short HEAD)"
          next=''
          amend='--amend'
        else
          msg="${arg#* }"
          next="$verb \$head"
          amend=''
        fi
        if reconfigure; then
          commit "$msg" "$next" "$arg" "$amend"
          if ((!aborting)); then
            rebase
          fi
        fi
      fi;;
    branch)
      unset THIS_USES
      unset THIS_TOUCHED
      unset THIS_PROVENANCE
      unset THIS_REMAP
      declare -gA THIS_TOUCHED
      declare -gA THIS_USES
      declare -gA THIS_PROVENANCE
      declare -gA THIS_REMAP
      if [[ -n $target_branch ]]; then
#        THIS_TOUCHED["$target_branch"]="$(git rev-parse $target_branch)"
        THIS_TOUCHED["$target_branch"]="${HEADS[$target_branch]}"
      fi
      target_branch="backport-${arg#relocatable-base-}"
      echo -e "Creating branch \e[34m$target_branch\e[0m on \e[34m$arg\e[0m"
      target="$arg"
      WORKING=()
      backporting=1
      failure=0
      for cmd in "${COMMITS[@]}"; do
        verb="${cmd%% *}"
        sha="${cmd#* }"
        case "$verb" in
          stop-backporting)
            WORKING+=('stop-backporting');;
          pick|bootstrap|coreboot)
            if ((!use_new_mechanism || debug_new_mechanism)); then
              if ! is-backport "$sha" "${HEADS[$target]}"; then
                if is-backport "$sha" "$(merge-base 'upstream/trunk' "${HEADS[$target]}")"; then
#                  echo -e "Taking \e[97m$sha\e[0m ($(provenance "$sha")) by the new rule! - $(git log -n 1 --format=%s $sha)"
                  older=0
                  old_older=0
                else
                  display-with-provenance "Skipping \e[97m$sha\e[0m" "$sha" "as it's older than $target - $(git log -n 1 --format=%s $sha)"
                  older=1
                  old_older=1
                fi
              else
                older=0
                old_older=0
              fi
            fi
            if ((use_new_mechanism || debug_new_mechanism)); then
              introduces="${FIRST_BRANCH["$sha"]}"
              if [[ -z $introduces || $target = "relocatable-base-$introduces" ]]; then
                # The first branch cherry-picked may cherry-pick _exactly_
                # (assuming the committer date is equal to author date, etc.),
                # so blank out the entry in FIRST_BRANCH to ensure that the
                # commit is not suddenly considered old next time round!
                FIRST_BRANCH["$sha"]=''
                older=0
                new_older=0
              else
                older=1
                new_older=1
#                display-with-provenance "Skipping \e[97m$sha\e[0m" "$sha" "as it's older than $target - $(git log -n 1 --format=%s $sha)"
              fi
            fi
            if ((debug_new_mechanism)) && [[ $new_older != $old_older ]]; then
              echo "NOPE! This is $sha and ${PROVENANCE[$sha]} and ${FIRST_BRANCH["$sha"]}"
              if ((new_older)); then
                echo "New mechanism skips this commit; old mechanism takes it"
              else
                echo "New mechanism takes this commit; old mechanism skips it"
              fi
              failure=1
            fi
            if ((older)); then
              WORKING+=("next $cmd")
            else
              # This may write more than is required - @ could be skipped)
              prov="${PROVENANCE["$sha"]}"
              if [[ -n $prov ]]; then
                TOUCHED["$prov"]=1
                if [[ ! $prov =~ ^@ ]]; then
                  if [[ -z ${THIS_TOUCHED["$prov"]+x} ]]; then
#                    THIS_TOUCHED["$prov"]="$(git rev-parse "$prov")"
                    THIS_TOUCHED["$prov"]="${HEADS["$prov"]}"
                  fi
                fi
              fi
              WORKING+=("$cmd")
            fi;;
          adjust)
            # INSTR[0] = adjust; INSTR[1] = count; INSTR[2] = description; INSTR[@]:3 = commits
            INSTR=($cmd)
            if ((use_new_mechanism)); then
              introduces="${FIRST_BRANCH["${INSTR[3]}"]}"
              if [[ -z $introduces || $target = "relocatable-base-$introduces" ]]; then
                older=0
              else
                older=1
#                echo -e "Skipping \e[34m${INSTR[2]}\e[0m as it's older than $target"
              fi
            else
              if ! is-backport "${INSTR[3]}" "${HEADS[$target]}"; then
                if is-backport "${INSTR[3]}" "$(merge-base 'upstream/trunk' "${HEADS[$target]}")"; then
#                  echo -e "Taking \e[34m${INSTR[2]}\e[0m by the new rule!"
                  older=0
                else
                  echo -e "Skipping \e[34m${INSTR[2]}\e[0m as it's older than $target"
                  older=1
                fi
              else
                older=0
              fi
            fi
            if ((older)); then
              WORKING+=("next $cmd")
            else
              prov="${INSTR[2]%%@*}"
              TOUCHED["$prov"]=1
              if [[ ! $prov =~ ^@ ]]; then
                if [[ -z ${THIS_TOUCHED["$prov"]+x} ]]; then
#                  THIS_TOUCHED["$prov"]="$(git rev-parse "$prov")"
                  THIS_TOUCHED["$prov"]="${HEADS["$prov"]}"
                fi
              fi
              count="${INSTR[1]}"
              # Remove $count items from WORKING (not counting fixup/next items)
              if [[ $count -eq 0 ]]; then
                POPPED=()
              else
                i=0
                while [[ $count -gt 0 ]]; do
                  ((i++))
                  element="${WORKING[-$i]}"
                  case "${element%% *}" in
                    fixup|next) ;;
                    *) ((count--));
                  esac
                done
                POPPED=("${WORKING[@]: -$i}")
                WORKING=("${WORKING[@]:0:$((${#WORKING[@]} - $i))}")
              fi
              INSTR=("${INSTR[@]:3}")
              # Now interleave all of the commits in the adjust with the
              # instructions just popped
              while [[ ${#INSTR[@]} -gt 0 ]]; do
                sha="${INSTR[0]}"
                INSTR=("${INSTR[@]:1}")
                previous_cmd="${WORKING[-1]}"
                if [[ -z $(git diff-tree --no-commit-id --name-only -r "$sha") ]]; then
                  if ((legacy_empty_commits)); then
                    FIXUP_NEXT["${previous_cmd#* }"]=1
                  fi
                  #display-with-provenance "Pruning \e[97m$sha\e[0m" "$sha" "to $target_branch - $(git log -1 --format='%s' $sha)"
                else
                  FIXUP_NEXT["${previous_cmd#* }"]=1
                  WORKING+=("fixup $sha")
                fi
                # Add the next command from POPPED and any fixup/next commands
                # which followed it
                loop=1
                while [[ ${#POPPED[@]} -gt 0 && $loop -eq 1 ]]; do
                  elt="${POPPED[0]}"
                  WORKING+=("$elt")
                  POPPED=("${POPPED[@]:1}")
                  case "${elt%% *}" in
                    fixup|next) ;;
                    *) loop=0;;
                  esac
                done
              done
              # The commit list does not have to be the same size as the offset,
              # so ensure all remaining popped commands have been restored to
              # WORKING
              for cmd in "${POPPED[@]}"; do
                WORKING+=("$cmd")
              done
            fi;;
          *)
            echo "Internal error: unrecognised command $cmd" >&2
            exit 1;;
        esac
      done
      if ((failure)); then
        exit 1
      fi
      COMMITS=()
      for cmd in "${WORKING[@]}"; do
        if [[ ${cmd%% *} != 'next' ]]; then
          echo "$cmd"
        fi
      done > branches
      rm -f "$cache_index"
      GIT_INDEX_FILE="$cache_index" git add -f branches
      if [[ $linear_commit_history -eq 1 ]]; then
        echo "linear_commit_history $linear_commit_history" > rebase-config
        GIT_INDEX_FILE="$cache_index" git add -f rebase-config
      fi
      initial_sha="$(GIT_INDEX_FILE="$cache_index" git write-tree)"
      rm -f "$cache_index" branches rebase-config
      found_cache=''
      if ! git rev-parse --verify relocatable-cache &> /dev/null; then
        cache_root=$(git commit-tree '4b825dc642cb6eb9a060e54bf8d69288fbee4904' <<"EOF"
Relocatable Cache

This branch is used to root the index for the fast rebase cache commits
and is not intended to be pushed.
EOF
)
        git branch relocatable-cache "$cache_root"
      fi
      while read -r commit tree; do
        if [[ $tree = $initial_sha ]]; then
          valid=1
          for parent in $(git log -n 1 --format=%P "$commit"); do
            for entry in $(git ls-tree --name-only "$parent"); do
              if [[ $entry = 'rr-cache' ]]; then
                for rr in $(git ls-tree --name-only -r "$parent"); do
                  if ! diff -q <(git show "$parent:$rr") "../.git/modules/ocaml/$rr" > /dev/null; then
                    echo "Discounted $parent from $commit because of ../.git/modules/ocaml/$rr"
                    valid=0
                  else
                    touch "../.git/modules/ocaml/$rr"
                  fi
                done
              elif [[ $entry = 'commits' ]]; then
                found_cache="$parent"
              elif [[ $entry = 'configure' ]]; then
                target_sha="$parent"
              fi
            done
          done
          if ((!valid)); then
            found_cache=''
          fi
          break
        fi
      done < <(git log relocatable-cache --first-parent --format="%h %T")
      if ((re_cache)); then
        found_cache=''
      fi
      if [[ -n $found_cache ]]; then
        # Load the cache
        while read -r from to; do
          ALL_REMAPS["$from"]="$to"
        done < <(git show "$found_cache:commits")
        while read -r from to; do
          PROVENANCE["$from"]="$to"
        done < <(git show "$found_cache:provenance")
        apply-cache
        use_cache="$use_caching"
        if ((use_cache)) && [[ -n ${SKIP_CACHE[${target_branch#backport-}]+x} ]]; then
          use_cache=0
        fi
        if ((use_cache)); then
          echo -e "Using cache entry \e[97m$(git rev-parse --short $commit)\e[0m to set \e[34m$target_branch\e[0m to \e[97m$(git rev-parse --short $target_sha)\e[0m"
          COMMITS=("${test_WORKING[@]}")
          git checkout -B "$target_branch" "$target_sha" &> /dev/null
        else
          git checkout -B "$target_branch" "${HEADS[$arg]}" &> /dev/null
          rebase
        fi
      else
        test_WORKING=("${WORKING[@]}")
        git checkout -B "$target_branch" "${HEADS[$arg]}" &> /dev/null
        rebase
      fi
      if ((aborting)); then
        found_cache='poison'
      fi
      if [[ -z $found_cache ]]; then
        target_sha="$(git rev-parse HEAD)"
        # Create the cache entry
        rm -rf relocatable-cache-working
        mkdir relocatable-cache-working
        for entry in "${!THIS_USES[@]}"; do
          root="${entry#*/rr-cache/}"
          rr_dir="${root%/*}"
          mkdir -p "relocatable-cache-working/rr-cache/$rr_dir"
          cp "$entry" "relocatable-cache-working/rr-cache/$rr_dir/"
          cp "${entry/postimage/preimage}" "relocatable-cache-working/rr-cache/$rr_dir/"
        done
        for from in "${!THIS_REMAP[@]}"; do
          echo "$from ${THIS_REMAP["$from"]}"
        done > commits
        for prov in "${!THIS_PROVENANCE[@]}"; do
          echo "$prov ${THIS_PROVENANCE["$prov"]}"
        done > provenance
        GIT_INDEX_FILE="$cache_index" git add -f commits provenance
        result_tree_sha="$(GIT_INDEX_FILE="$cache_index" git write-tree)"
        rm -f "$cache_index" commits provenance
        result_sha="$(git commit-tree -m Result "$result_tree_sha")"
        cache_head="$(git rev-parse relocatable-cache)"
        parents=(-p "$result_sha" -p "$target_branch")
        if [[ -d 'relocatable-cache-working/rr-cache' ]]; then
          cd relocatable-cache-working
          GIT_INDEX_FILE="$cache_index" git --work-tree=. add -f rr-cache
          rr_sha="$(GIT_INDEX_FILE="$cache_index" git write-tree)"
          rm -f "$cache_index"
          cd ..
          rm -rf relocatable-cache-working
          rr_sha="$(git commit-tree -m Resolutions "$rr_sha")"
          parents+=(-p "$rr_sha")
        fi
        existing_cache=''
        while read -r commit tree; do
          if [[ $tree = $initial_sha ]]; then
            valid=1
            for parent in $(git log -n 1 --format=%P "$commit"); do
              for entry in $(git ls-tree --name-only "$parent"); do
                case $entry in
                  branches)
                    # Parent commit on relocatable-cache
                    ;;
                  commits|provenance)
                    # Result
                    if [[ $(git log -n 1 --format=%T "$parent") != $result_tree_sha ]]; then
                      valid=0
                    fi;;
                  rr-cache)
                    # rr-cache
                    for rr in $(git ls-tree --name-only -r "$parent"); do
                      if ! diff -q <(git show "$parent:$rr") "../.git/modules/ocaml/$rr" > /dev/null; then
                        valid=0
                      fi
                    done;;
                esac
              done
            done
            if ((valid)); then
              existing_cache="$commit"
            fi
            break
          fi
        done < <(git log relocatable-cache --first-parent --format="%h %T")
        if [[ -z $existing_cache ]]; then
          cache_commit="$(git commit-tree -m Cache -p "$cache_head" "${parents[@]}" "$initial_sha")"
          git branch -f relocatable-cache "$cache_commit"
        fi

        # Now apply the cache to test_WORKING in order to validate that it is
        # correct
        for from in "${!THIS_REMAP[@]}"; do
          ALL_REMAPS["$from"]="${THIS_REMAP["$from"]}"
        done
        WORKING=("${test_WORKING[@]}")
        test_WORKING=()
        apply-cache
      fi
      if ((!aborting)); then
        # Verify that the cache correctly predicted COMMITS
        failed=0
        if [[ ${#test_WORKING[@]} -ne ${#COMMITS[@]} ]]; then
          failed=1
        else
          while IFS=$'\t' read -r predicted actual; do
            if [[ $predicted != $actual ]]; then
              failed=1
              break
            fi
          done < <(paste <(printf "%s\n" "${test_WORKING[@]}") <(printf "%s\n" "${COMMITS[@]}"))
        fi
        if ((failed)); then
          if [[ -z $found_cache ]]; then
            echo 'The cache entry just created is inconsistent:'
          else
            echo 'The cache has failed validation:'
          fi
          patdiff <(printf "%s\n" "${test_WORKING[@]}") <(printf "%s\n" "${COMMITS[@]}")
          exit 1
        fi
        if [[ $(git rev-parse HEAD) != $target_sha ]]; then
          echo "Cache predicted $target_sha, but HEAD is $(git rev-parse HEAD)"
          exit 1
        fi
      fi
      ;;
    *)
      echo "Internal error: unrecognised command $instr" >&2
      exit 1;;
  esac
  if ((aborting)); then
    for instr in "${COMMANDS[@]}"; do
      echo "$instr" >> "$state_file"
    done
    COMMANDS=()
  fi
done

cd ..
if ((!aborting)); then
  git submodule update
  git -C "$dir" clean -dfX &> /dev/null
fi

if [[ ${#BOOTSTRAPS[@]} -gt 0 ]]; then
  echo
  echo Bootstrap summary:
  for msg in "${BOOTSTRAPS[@]}"; do
    echo -e " - $msg"
  done
fi

if ((aborting)); then
  exit 2
fi

declare -A BACKPORTS
declare -A REBASE_ROOTS
if [[ -n $backports ]]; then
  # Load from the file
  while read -r root sha; do
    BACKPORTS[$root]="$sha"
    REBASE_ROOTS[$root]="${HEADS[relocatable-base-${root#backport-}]}"
  done < <(git -C "$dir" show "$backports:backports-generated" 2>/dev/null || git -C "$dir" show "$backports:backports")
else
  # Load from origin
  for root in "${TARGETS[@]}"; do
    BACKPORTS[backport-$root]="$(git -C "$dir" rev-parse origin/backport-$root)"
    REBASE_ROOTS[backport-$root]="$(git -C "$dir" rev-parse origin/relocatable-base-$root)"
  done
fi

return_to="$(git -C "$dir" rev-parse HEAD)"
echo "Backport summary (first sha is just built; second sha is expected)"
echo -e " - Identical shas \e[90mgreyed out\e[0m;"
echo -e " - Differ only by commit date (old stack bug) \e[32min green\e[0m;"
echo -e " - Final tree identical but commit sequence differs \e[33min yellow\e[0m;"
echo -e " - Trees differ \e[31min red\e[0m with differences shown"
differ=0
for root in "${TARGETS[@]}"; do
  calculated_sha="$(git -C "$dir" rev-parse backport-$root)"
  recorded_sha="${BACKPORTS[backport-$root]}"
  if [[ $calculated_sha = $recorded_sha ]]; then
    echo -e "backport-$root: \e[90m$calculated_sha $recorded_sha\e[0m"
  elif ! git -C "$dir" diff --exit-code --quiet $recorded_sha $calculated_sha; then
    differ=1
    echo -e "backport-$root: $calculated_sha \e[31m$recorded_sha\e[0m"
    if [[ ${REBASE_ROOTS[backport-$root]} = ${HEADS[relocatable-base-$root]} ]]; then
      git --no-pager -C "$dir" diff --stat $recorded_sha $calculated_sha
    else
      echo "  - Roots differ; no diff displayed"
    fi
  else
    git -C "$dir" checkout -qB stack-checking-for-committer $recorded_sha
    git -C "$dir" rebase --committer-date-is-author-date ${HEADS[relocatable-base-$root]} &> /dev/null
    cleaned_sha="$(git -C "$dir" rev-parse HEAD)"
    git -C "$dir" checkout -q $return_to
    git -C "$dir" branch -qD stack-checking-for-committer
    if [[ $cleaned_sha = $calculated_sha ]]; then
      echo -e "backport-$root: $calculated_sha \e[32m$recorded_sha\e[0m"
    else
      differ=1
      echo -e "backport-$root: $calculated_sha \e[33m$recorded_sha\e[0m"
    fi
  fi
done
UNTOUCHED=()
for branch in "${BRANCHES[@]}"; do
  if [[ -z ${TOUCHED["${branch%%@*}"]} ]]; then
    UNTOUCHED+=("$branch")
  fi
done
if [[ ${#UNTOUCHED} -gt 0 ]]; then
  echo
  echo -e "\e[97m!!\e[0m \e[33mWARNING\e[0m \e[97m!!\e[0m These branches were unused:"
  for branch in "${UNTOUCHED[@]}"; do
    echo " - $branch"
  done
  echo
fi

if [[ ! -e $lock_index ]]; then
  if ((differ)); then
    echo "Lock failed to build correctly!"
    exit 1
  else
    exit 0
  fi
fi

cd "$dir"

GIT_INDEX_FILE="$lock_index" git --work-tree=../.git/modules/ocaml add \
  $(cd ../.git/modules/ocaml ; \
    find rr-cache -type f -newermt "$start_time" -name postimage\*) \
  $(cd ../.git/modules/ocaml ;
    find rr-cache -type f -newermt "$start_time" -name postimage\* | sed -e 's/postimage/preimage/')

for root in "${TARGETS[@]}"; do
  echo "backport-$root $(git rev-parse backport-$root)"
done > backports
GIT_INDEX_FILE="$lock_index" git add backports
rm backports

lock_tree_sha="$(GIT_INDEX_FILE="$lock_index" git write-tree)"
locks_head="$(git rev-parse relocatable-locks)"
found_lock=''
while read -r commit tree; do
  if [[ $tree = $lock_tree_sha ]]; then
    found_lock="$commit"
    break
  fi
done < <(git log relocatable-locks --format="%h %T")

if [[ -z $found_lock ]]; then
  parents=()
  for instruction in "${BRANCHES[@]}" "${TARGETS[@]}"; do
    if [[ $instruction != 'stop-backporting' ]]; then
      if [[ -z ${HEADS[$instruction]} ]]; then
        parents+=(-p ${HEADS[relocatable-base-$instruction]})
      else
        parents+=(-p ${HEADS[$instruction]})
      fi
    fi
  done
  for root in "${TARGETS[@]}"; do
    parents+=(-p $(git rev-parse backport-$root))
  done
  lock_tree_commit="$(git commit-tree -m Lock -p "$locks_head" "${parents[@]}" "$lock_tree_sha")"
  git branch -f relocatable-locks "$lock_tree_commit"
  echo "Added $lock_tree_commit to relocatable-locks"
else
  echo "Lock $lock_tree_sha already present in relocatable-locks @ $found_lock"
fi

cd ..