#!/bin/sh
# 
# reconcile.sh: filter which plans a replay-based multi-branch merge
################################################################
# Copyright (C) 2001, 2002 Tom Lord
# 
# See the file "COPYING" for further information about
# the copyright and warranty status of this work.
# 

set -e 

################################################################
# special options
# 
# Some options are special:
# 
#	--version | -V
#	--help | -h
# 
if test $# -ne 0 ; then

  for opt in "$@" ; do
    case $opt in

      --version|-V) exec larch --version
                    ;;


      --help|-h)
		printf "filter which plans a replay-based multi-branch merge\\n"
		printf "usage: reconcile [options]\\n"
		printf "\\n"
		printf " -V --version                  print version info\\n"
		printf " -h --help                     display help\\n"
		printf "\\n"
		printf "Compute a minimal list of necessary patches from a larger\\n"
		printf "list of needed patches.  Applying the necessary patches has\\n"
		printf "the effect of merging all changes found in the needed patches.\\n"
		printf "\\n"
		printf "Input to this command is a list of pairs of patch names, as\\n"
		printf "might be output by \"larch whats-missing --merge\".\\n"
		printf "\\n"
		printf "More specifically, the input has two fields per line.  The first\\n"
		printf "field is a patch.  The second field, separated by a space, is\\n"
		printf "is a second patch whose changes are included in the patch in the\\n"
		printf "first field:\\n"
		printf "\\n"
		printf "	PATCH INCLUDED-PATCH\\n"
		printf "\\n"
		printf "For every PATCH, there is a line expressing the (trivial) relation\\n"
		printf "of self-inclusion\\n"
		printf "\\n"
		printf "	PATCH PATCH\\n"
		printf "\\n"
		printf "The ordering of lines in the input is significant for the first\\n"
		printf "field: for two patches on the same branch version, the earlier patch\\n"
		printf "must come first in the list.  For any other two patches, not in the\\n"
		printf "same branch version, the ordering expresses a user preference: if\\n"
		printf "possible, the user wants to apply the first patch before the second\\n"
		printf "patch.\\n"
		printf "\\n"
		printf "The output of this command is a minimal list of patches whose cumulative\\n"
		printf "effect is the same as the cumulative effect of all of the patches in\\n"
		printf "the first field of the input, ordered primarily by prerequisite ordering\\n"
		printf "(don't apply a patch until the changes from all earlier patches in the\\n"
		printf "same branch are present) and secondarilly by the user's\\n"
		printf "preference ordering (e.g., the order of branch versions in the arguments\\n"
		printf "to \"whats-missing\").\\n"
		printf "\\n"
		printf "The output is suitable for use as input to the \"larch replay --list\"\\n"
		printf "command.\\n"
		printf "\\n"
		exit 0
      		;;

      *)
		;;
    esac
  done
fi

################################################################
# Ordinary Options
# 
# 

while test $# -ne 0 ; do

  case "$1" in 

    --)			shift
			break
			;;

    -*)			printf "reconcile: unrecognized option (%s)\\n" "$1" 1>&2
			printf "try --help\\n" 1>&2
			exit 2
			;;

    *)			break
    			;;

  esac

done



################################################################
# Ordinary Arguments
# 

if test $# -gt 0 ; then
  printf "usage: reconcile [options]\\n" 1>&2
  printf "try --help\\n" 1>&2
  printf "\\n" 1>&2
  exit 1
fi


################################################################
# Compute Replay Plan
# 

here="`pwd`"
tmpdir="$here/,,reconcile"

clean()
{
  cd "$here"
  rm -rf "$tmpdir"
}

bail()
{
  clean
  exit 1
}

trap "printf \"reconcile: interrupted -- cleaning up\\n\" 1>&2 ; bail" INT

rm -rf "$tmpdir"
mkdir -p "$tmpdir"
cd "$tmpdir"

# 
# input is:
# 
#   patch-A patch-B
# 
# where patch-A includes all changes from patch-B.
# 
# Sorted primarilly by version preference, secondarilly by patch level.
# 
cat > input

# 
# input-by-included is the input list, sorted by the second column.
# 
sort -k 2 input > input-by-included

# 
# The left column of input is the patches whose cumulative effect
# the user wants.
# 
cut -s -d ' ' -f 1 input > demanded

# 
# preference order is a list "%s %s\\n" of PATCH SEQ
# 
cat demanded \
| awk -v counter=0 \
      '{
         print $1 " " counter;
	 counter += 1;
       }' \
| sort -k 1 \
> preference_order

# 
# The user's demand, sorted.
# 
sort -u demanded > demanded-sorted

# 
# patches included by some other patch, sorted
# 
cat input \
| awk '{ if ($1 != $2) print $2 }' \
| sort -u \
> included-somewhere

# 
# The smallest set of patches that satisfies the user's demand:
# 
comm -2 -3 demanded-sorted included-somewhere > necessary

# 
# The set of demanded patches we won't be applying:
# 
comm -2 -3 demanded-sorted necessary > omitted

# 
# precedes is a tsort list of patch pairs, each pair either:
# 
# 	A A
# or
# 
# 	A B
# 
# where A is the patch level immediately before B on the same
# version in the input list.
# 
# Order is the same as in input.
# 
cat input \
| awk \
	'BEGIN { last_patch = "" }
	 {
	   patch = $1;
	   if ((patch == $2) && !done[patch " " patch])
	     {
	       print patch " " patch;
	       done[patch " " patch] = 1;
	     }
	   version = patch;
	   sub ("--([^-]|-[^-])*$", "", version);
	   if ((version == last_version) && (last_patch != "") && !done[last_patch " " patch])
	     {
	       print last_patch " " patch;
	       done[last_patch " " patch] = 1;
	     }
	   last_patch = patch;
	   last_version = version;
	 }' \
> precedes

#
# inc-necessary is the input list (but sort -k 1) to lines where the
# left column is in the necessary patch list
# 
cat input \
| sort -k 1 \
| join -o 1.1,1.2 -1 1 -2 1 - necessary \
> inc-necessary


touch done
touch schedule
cp necessary agenda

# 
# While there are patches yet unscheduled:
# 
while test ! -z "`cat agenda | head -1`" ; do

  # 
  # Figure out the next patch to apply
  # 
  # That patch is the most preferred patch with no missing
  # pre-reqs.
  # 
  # First, what is the list of patches with no missing
  # pre-reqs?
  # 

  rm -f ready
  for patch in `cat agenda` ; do
# echo
# echo PATCH $patch
    rm -f prereqs
    cat precedes | awk -v patch=$patch '{ if (($1 != patch) && ($2 == patch)) print $1 }' | sort > prereqs
# echo PREREQS
# cat prereqs
# echo
# echo DONE
# cat done
# echo
    if test -z "`comm -2 -3 prereqs done | head -1`" ; then
# echo READY $patch
      printf "%s\\n" $patch >> ready
# else
# echo NOT READY $patch
    fi
# echo
  done


  if test ! -e ready ; then
    printf "\\n" 1>&2
    printf "reconcile: illegal input\\n" 1>&2
    printf "\\n" 1>&2
    printf "  After applying these patches:\\n" 1>&2
    cat schedule | sed -e 's/^/    /' 1>&2
    printf "\\n" 1>&2
    printf "  there is no patch ready to be applied next, although\\n" 1>&2
    printf "  these patches remain to be applied:\\n" 1>&2
    printf "\\n" 1>&2
    cat agenda | sed -e 's/^/    /' 1>&2
    printf "\\n" 1>&2
    exit 1
  fi

# echo COMPUTING NEXT FROM READY SET:
# cat ready
# echo
  # 
  # of the ready patches, which is the most preferred?
  #
  next=`sort ready | join -o 2.1,2.2 - preference_order | sort -k 2,2n | head -1 | cut -s -d ' ' -f 1`

# echo NEXT $next
# echo

  printf "%s\\n" $next >> schedule

  rm -f ,,tmp
  mv done ,,tmp
  ( cat ,,tmp ; printf "%s\\n" $next | join -o 2.2 -1 1 -2 1 - inc-necessary ) | sort > done
  rm -f ,,tmp
  mv agenda ,,tmp
  cat ,,tmp | grep -v -F -x $next > agenda || true

done
  
cat schedule

clean

# tag: Tom Lord Tue Dec 18 06:25:58 2001 (branching-and-merging/reconcile.sh)
#
