hgmerge

Optimize manifest.add

Testing shows that manifest.add is spending a significant percentage of
its time running calcoffsets and doing text = "".join(addlist).  This
patch removes the need for both of these by storying the manifest in a
character array, and using a modified bisect search to find lines without
the help of a separate index of line offsets.

manifest.add was also reworked to push delta construction/combination into the
main loop.

Time to apply 2751 patches (without psyco, ext3 noatime,data=writeback):

Stock hg: 4m45s real 3m32s user 55s sys
patched:  2m48s real 1m53s user 43s sys
quilt:    2m30s real   45s user 50s sys

(quilt does much more io...)

#!/bin/sh
#
# hgmerge - default merge helper for Mercurial
#
# This tries to find a way to do three-way merge on the current system.
# The result ought to end up in $1.

set -e # bail out quickly on failure

LOCAL="$1"
BASE="$2"
OTHER="$3"

if [ -z "$EDITOR" ]; then
    EDITOR="vi"
fi

# find decent versions of our utilities, insisting on the GNU versions where we
# need to
DIFF3=gdiff3
DIFF=gdiff
PATCH=gpatch

type $DIFF3 >/dev/null 2>&1 || DIFF3=diff3
type $DIFF  >/dev/null 2>&1 || DIFF=diff
type $PATCH  >/dev/null 2>&1 || PATCH=patch
$DIFF3 --version >/dev/null 2>&1 || DIFF3=

# Back up our file
cp "$LOCAL" "$LOCAL.orig"

# Attempt to do a non-interactive merge
if type merge > /dev/null 2>&1; then
    merge "$LOCAL" "$BASE" "$OTHER" 2> /dev/null && exit 0
    cp "$LOCAL.orig" "$LOCAL"
elif [ -n "$DIFF3" ]; then
    echo $DIFF3 -m "$LOCAL.orig" "$BASE" "$OTHER"
    $DIFF3 -m "$LOCAL.orig" "$BASE" "$OTHER" > "$LOCAL" && exit 0
    if [ $? -eq 2 ]; then
        echo "$DIFF3 failed! Exiting." 1>&2
        cp "$LOCAL.orig" "$LOCAL"
        exit 1
    fi
    cp "$LOCAL.orig" "$LOCAL"
fi

if [ -n "$DISPLAY" ]; then
    # try using kdiff3, which is fairly nice
    if type kdiff3 > /dev/null 2>&1; then
	kdiff3 --auto "$BASE" "$LOCAL" "$OTHER" -o "$LOCAL" || exit 1
	exit 0
    fi

    # try using tkdiff, which is a bit less sophisticated
    if type tkdiff > /dev/null 2>&1; then
	tkdiff "$LOCAL" "$OTHER" -a "$BASE" -o "$LOCAL" || exit 1
	exit 0
    fi
fi

# Attempt to do a merge with $EDITOR
if type merge > /dev/null 2>&1; then
    echo "conflicts detected in $LOCAL"
    merge "$LOCAL" "$BASE" "$OTHER" 2>/dev/null || $EDITOR "$LOCAL"
    exit 0
fi

if [ -n "$DIFF3" ]; then
    echo "conflicts detected in $LOCAL"
    $DIFF3 -m "$LOCAL.orig" "$BASE" "$OTHER" > "$LOCAL" || {
        case $? in
            1)
                $EDITOR "$LOCAL" ;;
            2)  echo "$DIFF3 failed! Exiting." 1>&2
                cp "$LOCAL.orig" "$LOCAL"
                exit 1 ;;
        esac
        exit 0
    }
fi

HGTMP=""
cleanup_exit() {
    rm -rf "$HGTMP"
}

# attempt to manually merge with diff and patch
if [ -n "$DIFF" -a -n "$PATCH" ]; then
    # Remove temporary files even if we get interrupted
    trap "cleanup_exit" 0 # normal exit
    trap "exit 1" 1 2 3 6 15 # HUP INT QUIT ABRT TERM

    HGTMP="${TMPDIR-/tmp}/hgmerge.$RANDOM.$RANDOM.$RANDOM.$$"
    (umask 077 && mkdir "$HGTMP") || {
	echo "Could not create temporary directory! Exiting." 1>&2
	exit 1
    }

    $DIFF -u "$BASE" "$OTHER" > "$HGTMP/diff" || :
    if $PATCH "$LOCAL" < "$HGTMP/diff"; then
	exit 0
    else
	# If rejects are empty after using the editor, merge was ok
	$EDITOR "$LOCAL" "$LOCAL.rej" && test -s "$LOCAL.rej" || exit 0
    fi
    exit 1
fi

echo "hgmerge: unable to find merge, tkdiff, kdiff3, or diff+patch!"
exit 1