Perl script for intelligent merge

[Ho...@t-online.de]

Hi,
in my last mail, i described an algorithm to perform an intelligent
merge. As i learned now,
the ideas are not new and already mentioned in subversion's docs. To
test the algorithm,
i wrote my first perl script (please excuse bad style; i just started).
It's more an experiment 
than a full featured tool and only works on complete repository trees.
Hope it gives some inspiration
to you or even helps to solve simple tasks. It uses an entry in the log
to remember merges.

Horst

#!/usr/bin/perl
# Determines the steps to merge two repository parts in a way, that
already merged diffs
# are not merged again.  
# task: repository contains trunk and branch; merge all changes from
trunk into branch.
# todo: cd workdir; switch to branch; commit last changes; update from
repository
# call script: perl imerge.pl URL/trunk URL/branch .
# 
# Author: Horst Schuenemann
# Date:   03/03/2004
# Email:  horst.schuenemann@t-online.de 
#
# tested with this sample:
#
# trunk
# -------->[1]------>[2]----------->[4]---------->[8]---+---->[9]
#  create	   add    |   bugfix     |   bugfix         ^
#   repo      commit  |   commit     |   commit         | merge
#                     |              |                  |
#                     |              |                  |
#                     |              |                  |
#             branch  |       merge  |                  |
# branch              v              v                  |
#                    [3]------->[5]--+---->[6]-------->[7]
#                         cr 1                  cr 2
#                        commit                commit
# 
# - The process for a very simple project starts with creating the 
#   repository (release [1]). 
# - Files are added (release [2]). 
# - A branch is created to implement some change requests (release [3]).
# - A bugfix is implemented in the trunk (release [4]).
# - The first change request is implemented (release [5]).
# - The bugfix in the trunk is necessary for the cr branch too. [4] is 
#   imerged with [5] (release [6]).
# - The second change request is implemented (release [7]).
# - A second bugfix is added to the trunk (release [8]).
# - The work on the cr branch is finished and the results [7] are
#   imerged with [8] (release [9]).
 
use strict;

my $IMergeLog = "++imerge++";

#
-----------------------------------------------------------------------------
  
# --- Get parameters from cmd line   
# --- URL1 is the repository part, from which the deltas will be
calculated
# --- URL2 is the repository part, where the deltas of URL1 are merge
into
# --- WCPATH is the working directory containing the latest update of
URL2
#
-----------------------------------------------------------------------------
  

my $URL1 = shift @ARGV;
my $URL2 = shift @ARGV;
my $WCPATH = shift @ARGV;

#
-----------------------------------------------------------------------------
  
# --- Make sure we got all the arguments we wanted
#
-----------------------------------------------------------------------------
  

if (   (not defined $URL1) or (not defined $URL2) or (not defined
$WCPATH)
    or ($URL1 eq '') or ($URL2 eq '') or ($WCPATH eq '')) { 
   print "Usage: imerge.pl URL1 URL2 WCPATH\n\n";
   exit;
}

#
-----------------------------------------------------------------------------
  
# --- Switch to URL2 and update the working copy
#
-----------------------------------------------------------------------------
  

print "Updating $WCPATH from $URL2\n\n";
system("svn switch -q $URL2");
system("svn update -q $WCPATH");

#
-----------------------------------------------------------------------------
  
# --- Collect lines of ULR1 and URL 2 log
#
-----------------------------------------------------------------------------
  

my @LogLines1 = getLogLines($URL1, 0);
my @LogLines2 = getLogLines($URL2, 0);

#
-----------------------------------------------------------------------------
  
# --- Filter release numbers and deltas from logs
# --- sample: URL1 [7 6 2:4 5 3 2 1], URL2 [8 4 2 1]
#
-----------------------------------------------------------------------------
  

my @ReleasesAndDeltas1 = getReleasesAndDeltas(@LogLines1);
my @ReleasesAndDeltas2 = getReleasesAndDeltas(@LogLines2);

#
-----------------------------------------------------------------------------
  
# --- build a list of deltas from the log releases
# --- sample URL1 [0:1 1:2 2:3 3:5 2:4 6:7], URL2 [0:1 1:2 2:4 4:8]
#
-----------------------------------------------------------------------------
  

my @Deltas1 = getDeltas(@ReleasesAndDeltas1);
my @Deltas2 = getDeltas(@ReleasesAndDeltas2);

#
-----------------------------------------------------------------------------
  
# --- Determine deltas in URL1 that are new to URL2
# --- sample @ToMerge [2:3 3:5 6:7]
#
-----------------------------------------------------------------------------
  

my @ToMerge;
my $Element;

foreach $Element (@Deltas1) 
{
  if(not elementInList($Element, @Deltas2)) {
    push(@ToMerge, $Element);
  }
}

#
-----------------------------------------------------------------------------
  
# --- correct the deltas in @ToMerge to contain only releases, that are
in the
# --- stop-on-copy log.
#
-----------------------------------------------------------------------------
  

my @LogLines1StOC = getLogLines($URL1, 1);
my @Releases1StOC = getReleasesStopOnCopy(@LogLines1StOC);

@Releases1StOC = reverse(@Releases1StOC);

my @CorrectedToMerge;

foreach $Element (@ToMerge)
{
  my @Tokens = split(/:/, $Element);
  my $From = $Tokens[0];
  my $To = $Tokens[1];

  if(elementInList($From, @Releases1StOC) and elementInList($To,
@Releases1StOC)) {
    push(@CorrectedToMerge, $Element);
  }
}

#
-----------------------------------------------------------------------------
  
# --- merge succeeding deltas to bigger deltas
# --- sample @ToMergePacked [2:5 6:7]
#
-----------------------------------------------------------------------------
  

my @ToMergePacked = packDeltas(@CorrectedToMerge);

my $Delta;

# --- Print wha's todo
print "todo:\n\n";

if(@ToMergePacked > 0) 
{
  foreach $Delta (@ToMergePacked) 
  {
    print "svn merge -r $Delta $URL1 $WCPATH\n\n";
    print "# resolve conflicts before you continue; don't commit now\n";
    print "# if conflicts were resolved: svn resolved $WCPATH\n\n";
  }

  print "svn commit -m \"$IMergeLog @ToMerge\" $WCPATH\n";
  print "svn update $WCPATH\n";
} 
else {
  print "nothing\n";
}

#
-----------------------------------------------------------------------------
  
# --- Subroutines start here
#
-----------------------------------------------------------------------------

#
-----------------------------------------------------------------------------
  
# --- Get the lines of "svn log URL" as an array
#
-----------------------------------------------------------------------------

sub getLogLines() 
{
  my ($Repository, $StopOnCopy) = @_;

  my $Command;

  if($StopOnCopy) {
    $Command = "svn log --stop-on-copy $Repository";
  } else {
    $Command = "svn log $Repository";
  }

  open(FILE, "$Command|") || die "$Command failed";
  
  my @LogLines = <FILE>;

  close(FILE);

  chomp(@LogLines);

  return(@LogLines);
}

#
-----------------------------------------------------------------------------
# --- Create a list of all releases of a product line from HEAD to
START.
# --- Input is an array with the log lines. The result array contains
the
# --- releases and the deltas from additional imerges. 
#
-----------------------------------------------------------------------------

sub getReleasesAndDeltas() 
{
  my (@LogLines) = @_;

  my @Releases;

  for(my $Index = 0; $Index < @LogLines; $Index++) 
  {
    my $Line = $LogLines[$Index];
    my @Tokens = split(/ /, $Line);
    my $FirstToken = $Tokens[0];

    if($FirstToken =~ /r[0-9]+/) 
	{
	  # --- found start of release entry
      push(@Releases, substr($FirstToken, 1));
	  
	  # --- look for imerge log entries
	  for($Index++; $Index < @LogLines; $Index++)
	  {
	    $Line = $LogLines[$Index];

        @Tokens = split(/ /, $Line);

		if($Tokens[0] eq $IMergeLog) 
		{
		   # --- found imerge entry; continue looping till end of entry
           for(my $DeltaIndex = 1; $DeltaIndex <= $#Tokens;
$DeltaIndex++) 
	       {
  	         my $Token = $Tokens[$DeltaIndex];

	         if($Token =~ /[0-9]+:[0-9]+/) {
	           push(@Releases, $Token);
	         }
           }
		}

		if($Line =~ /[-]+/) 
		{
		   # --- reached end of entry
		   last;
		}
	  }
    }
  }

  return(@Releases);
}

#
-----------------------------------------------------------------------------
# --- Create a list of all releases of a product line from HEAD to begin
of
# --- branch. Input is an array with the log lines. 
#
-----------------------------------------------------------------------------

sub getReleasesStopOnCopy() 
{
  my (@LogLines) = @_;

  my @Releases;

  for(my $Index = 0; $Index < @LogLines; $Index++) 
  {
    my $Line = $LogLines[$Index];
    my @Tokens = split(/ /, $Line);
    my $FirstToken = $Tokens[0];

    if($FirstToken =~ /r[0-9]+/) 
	{
	  # --- found start of release entry
      push(@Releases, substr($FirstToken, 1));
	  
	  # --- look for imerge log entries
	  for($Index++; $Index < @LogLines; $Index++)
	  {
	    $Line = $LogLines[$Index];

		if($Line =~ /[-]+/) 
		{
		   # --- reached end of entry
		   last;
		}
	  }
    }
  }

  return(@Releases);
}

#
-----------------------------------------------------------------------------
# --- Create a list of deltas from a list of releases and deltas of a
product 
# --- line. The list of releases goes from HEAD to START. The list of
deltas goes 
# --- from START to HEAD.
#
-----------------------------------------------------------------------------

sub getDeltas() 
{
  my (@Releases) = @_; 

  push(@Releases, "0");

  my @Deltas;

  if(@Releases eq 1)
  {
    my $Element = $Releases[0];

    if($Element =~ /[0-9]+:[0-9]+/)
    {
	  # --- its a delta
      push(@Deltas, $Element);
    }
  }
  else
  {
    my @Pair;
    my $PairIndex = 0;

    for(my $Index = @Releases - 1; $Index >= 0; $Index--)
    {
	  my $Current = $Releases[$Index];

      if($Current =~ /[0-9]+:[0-9]+/)
	  {
	    # --- its already a delta
        push(@Deltas, $Current);
	    $PairIndex = 0;
		next;
	  }

      $Pair[$PairIndex] = $Current;

	  $PairIndex++;
	  
	  if($PairIndex eq 2)
	  {
	    my $Delta = $Pair[0] . ":" . $Pair[1];
	    push(@Deltas, $Delta);

		$Pair[0] = $Pair[1];
	    $PairIndex = 1;
	  }	
    }
  }

  return(@Deltas);
}

#
-----------------------------------------------------------------------------
# Look for an element in a list. Return 1 if found; otherwise 0.
#
-----------------------------------------------------------------------------

sub elementInList() 
{
  my ($Element, @List) = @_; 

  my $Elem;

  foreach $Elem (@List) 
  {
    if($Elem eq $Element) {
	  return(1);
    }
  }

  return(0);
}

#
-----------------------------------------------------------------------------
# Create a list of packed deltas from a list of unpacked deltas.
# sample [0:2 2:4] becomes [0:4]. 
#
-----------------------------------------------------------------------------

sub packDeltas() 
{
  my (@Unpacked) = @_; 
  
  my @Packed;

  if(@Unpacked > 1)
  {
    my $CurDelta = $Unpacked[0];
    my @CurReleases = split(/:/, $CurDelta);
	my $CurFrom = $CurReleases[0];
	my $CurTo = $CurReleases[1];

    for(my $Index = 1; $Index < @Unpacked; $Index++) 
	{
      my @NextReleases = split(/:/, $Unpacked[$Index]);
  	  my $NextFrom = $NextReleases[0];
	  my $NextTo = $NextReleases[1];

	  if($CurTo eq $NextFrom) {
        $CurTo = $NextTo;
	  }
	  else
	  {
	     $CurDelta = $CurFrom . ":" . $CurTo;
		 push(@Packed, $CurDelta);

	     $CurFrom = $NextFrom;
	     $CurTo = $NextTo;
	  }
    }

    $CurDelta = $CurFrom . ":" . $CurTo;
	push(@Packed, $CurDelta);
  }
  else {
    @Packed = @Unpacked;
  }

  return(@Packed);
}







---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org

Re: Perl script for intelligent merge

[marvin greenberg <mg...@dctd.No.spam.saic.com>]

It's a script that attempts to track the merges between two branches, by marking 
merges with log messages, and then incrementally applying the deltas.  We 
started doing something like this a long time ago, but decided it just wasn't 
worth it.

If you have two branches

-------a------------d-----e---------   trunk
         \          /       \
          \  delta /         \
           b------c------------------   somebranch

You work on somebranch for a while, (and other folks on the trunk, say)
Someone wants to merge what you've done, so they do
   svn merge -r b:c http:/somebranch  trunkWorkingCopy    creating a d revision.

Then later you want to merge the changes from the trunk to your branch.  What 
you have to do according to the red book, is remember all the merges, and don't 
apply them again.
    svn merge -r a:d-1 http:/trunk somebranchWorkingCopy
    svn merge -r d:e   http:/trunk somebranchWorkingCopy

You don't want to apply the delta from d-1:d since those were changes that came 
from "somebranch".  Horst's script attempts to automate this, by marking merges 
with special log messages to "remember" what has been merged.

The big problem is that you can't automate it because conflicts can happen, in 
which case the script dies in the middle leaving the developer with even less 
clues what's going on.  (Also early on, svn had some problems with diff, that 
made it real problematic)

marvin

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org

Re: Perl script for intelligent merge

[Calvin Spealman <ca...@ironfroggy.com>]

i havent touched perl in far too long. could you explain what this is for, 
exactly? what does it do differently than svn merge?

On Thursday 04 March 2004 5:55 am, Horst.Schuenemann@t-online.de wrote:
> Hi,
> in my last mail, i described an algorithm to perform an intelligent
> merge. As i learned now,
> the ideas are not new and already mentioned in subversion's docs. To
> test the algorithm,
> i wrote my first perl script (please excuse bad style; i just started).
> It's more an experiment
> than a full featured tool and only works on complete repository trees.
> Hope it gives some inspiration
> to you or even helps to solve simple tasks. It uses an entry in the log
> to remember merges.

---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org