tests/testlib/merge-combination-util.sh
author Arun Kulshreshtha <akulshreshtha@janestreet.com>
Tue, 30 Aug 2022 15:29:55 -0400
changeset 49491 c6a1beba27e9
parent 46266 e8b0c519dfb3
permissions -rw-r--r--
bisect: avoid copying ancestor list for non-merge commits During a bisection, hg needs to compute a list of all ancestors for every candidate commit. This is accomplished via a bottom-up traversal of the set of candidates, during which each revision's ancestor list is populated using the ancestor list of its parent(s). Previously, this involved copying the entire list, which could be very long in if the bisection range was large. To help improve this, we can observe that each candidate commit is visited exactly once, at which point its ancestor list is copied into its children's lists and then dropped. In the case of non-merge commits, a commit's ancestor list consists exactly of its parent's list plus itself. This means that we can trivially reuse the parent's existing list for one of its non-merge children, which avoids copying entirely if that commit is the parent's only child. This makes bisections over linear ranges of commits much faster. During some informal testing in the large publicly-available `mozilla-central` repository, this noticeably sped up bisections over large ranges of history: Setup: $ cd mozilla-central $ hg bisect --reset $ hg bisect --good 0 $ hg log -r tip -T '{rev}\n' 628417 Test: $ time hg bisect --bad tip --noupdate Before: real 3m35.927s user 3m35.553s sys 0m0.319s After: real 1m41.142s user 1m40.810s sys 0m0.285s
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
46266
e8b0c519dfb3 test: split tests/test-merge-combination.t into multiple parts
Pierre-Yves David <pierre-yves.david@octobus.net>
parents: 46265
diff changeset
     1
# genmerges is the workhorse of the test-merge-combination-*.t tests.
46265
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
     2
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
     3
# Given:
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
     4
# - a `range` function describing the possible values for file a
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
     5
# - a `isgood` function to filter out uninteresting combination
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
     6
# - a `createfile` function to actually write the values for file a on the
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
     7
#   filesystem
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
     8
#
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
     9
# it print a series of lines that look like: abcd C: output of -T {files}
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    10
# describing the file a at respectively the base, p2, p1, merge
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    11
# revision. "C" indicates that hg merge had conflicts.
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    12
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    13
genmerges () {
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    14
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    15
  (LC_ALL=C type range | grep -q 'function') || (echo >&2 "missing function: range")
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    16
  (LC_ALL=C type isgood | grep -q 'function') || (echo >&2 "missing function: isgood")
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    17
  (LC_ALL=C type createfile | grep -q 'function') || (echo >&2 "missing function: createfile")
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    18
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    19
  for base in `range` -; do
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    20
    for r1 in `range $base` -; do
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    21
      for r2 in `range $base $r1` -; do
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    22
        for m in `range $base $r1 $r2` -; do
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    23
          line="$base$r1$r2$m"
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    24
          isgood $line || continue
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    25
          hg init repo
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    26
          cd repo
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    27
          make_commit () {
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    28
            v=$1; msg=$2; file=$3;
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    29
            if [ $v != - ]; then
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    30
              createfile $v
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    31
            else
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    32
              if [ -f a ]
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    33
              then rm a
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    34
              else touch $file
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    35
              fi
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    36
            fi
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    37
            hg commit -q -Am $msg || exit 123
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    38
          }
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    39
          echo foo > foo
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    40
          make_commit $base base b
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    41
          make_commit $r1 r1 c
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    42
          hg up -r 0 -q
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    43
          make_commit $r2 r2 d
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    44
          hg merge -q -r 1 > ../output 2>&1
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    45
          if [ $? -ne 0 ]; then rm -f *.orig; hg resolve -m --all -q; fi
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    46
          if [ -s ../output ]; then conflicts=" C"; else conflicts="  "; fi
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    47
          make_commit $m m e
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    48
          if [ $m = $r1 ] && [ $m = $r2 ]
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    49
          then expected=
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    50
          elif [ $m = $r1 ]
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    51
          then if [ $base = $r2 ]
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    52
               then expected=
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    53
               else expected=a
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    54
               fi
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    55
          elif [ $m = $r2 ]
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    56
          then if [ $base = $r1 ]
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    57
               then expected=
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    58
               else expected=a
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    59
               fi
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    60
          else expected=a
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    61
          fi
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    62
          got=`hg log -r 3 --template '{files}\n' | tr -d 'e '`
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    63
          if [ "$got" = "$expected" ]
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    64
          then echo "$line$conflicts: agree on \"$got\""
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    65
          else echo "$line$conflicts: hg said \"$got\", expected \"$expected\""
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    66
          fi
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    67
          cd ../
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    68
          rm -rf repo
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    69
        done
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    70
      done
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    71
    done
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    72
  done
8045e4aa366b test: extract the `genmerges` out of test-merge-combination.t
Pierre-Yves David <pierre-yves.david@octobus.net>
parents:
diff changeset
    73
}