{"thread":{"id":"1758","subject":"[PATCH] archimport - add merge detection","startedAt":"2005-09-10T11:38:17Z","lastAt":"2005-09-10T11:38:17Z","messageCount":1,"participants":["martin@catalyst.net.nz"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"8249","messageId":"1126352297800-git-send-email-martin@catalyst.net.nz","threadId":"1758","inReplyTo":null,"subject":"[PATCH] archimport - add merge detection","fromName":"","fromEmail":"martin@catalyst.net.nz","sentAt":"2005-09-10T11:38:17Z","receivedAt":"2005-09-10T11:38:17Z","isPatch":true,"sender":{"key":"martin@laptop.org","avatar":null},"body":"We now keep track of the patches merged in each branch since they have\ndiverged, using the records that the Arch \"logs\" provide. Merge parents\nfor a commit are defined if we are merging a series of patches that starts\nfrom the mergebase.\n\nIf patches from a related branch are merged out-of-order, we keep track of\nhow much has been merged sequentially -- the tip of that sequential merge\nis our new parent from that branch.\n\nThis mechanism works very well for branches that merge in dovetail and/or\nflying fish patterns, probably less well for others.\n\n---\n\n git-archimport.perl |  184 ++++++++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 180 insertions(+), 4 deletions(-)\n\ne4921c767dd41e23ad9f84b10c7ce1715827905f\ndiff --git a/git-archimport.perl b/git-archimport.perl\n--- a/git-archimport.perl\n+++ b/git-archimport.perl\n@@ -61,7 +61,7 @@ END\n     exit(1);\n }\n \n-getopts(\"hviC:t:\") or usage();\n+getopts(\"ThviC:t:\") or usage();\n usage if $opt_h;\n \n @ARGV >= 1 or usage();\n@@ -76,6 +76,10 @@ $git_tree ||= \".\";\n \n \n my @psets  = ();                # the collection\n+my %psets  = ();                # the collection, by name\n+\n+my %rptags = ();                # my reverse private tags\n+                                # to map a SHA1 to a commitid\n \n foreach my $root (@arch_roots) {\n     my ($arepo, $abranch) = split(m!/!, $root);\n@@ -96,6 +100,7 @@ foreach my $root (@arch_roots) {\n             if (%ps) {\n                 my %temp = %ps; # break references\n                 push (@psets, \\%temp);\n+\t\t$psets{$temp{id}} = \\%temp;\n                 %ps = ();\n             }\n             \n@@ -158,7 +163,8 @@ foreach my $root (@arch_roots) {\n \n     if (%ps) {\n         my %temp = %ps;         # break references\n-        push (@psets, \\%temp);\n+        push (@psets, \\%temp);  \n+\t$psets{ $temp{id} } = \\%temp;\n         %ps = ();\n     }    \n     close ABROWSE;\n@@ -183,6 +189,24 @@ unless (-d '.git') { # initial import\n     } else {\n         die \"Need to start from an import or a tag -- cannot use $psets[0]{id}\";\n     }\n+} else {    # progressing an import\n+    # load the rptags\n+    opendir(DIR, \".git/archimport/tags\")\n+\t|| die \"can't opendir: $!\";\n+    while (my $file = readdir(DIR)) {\n+\t# skip non-interesting-files\n+\tnext unless -f \".git/archimport/tags/$file\";\n+\tnext if     $file =~ m/--base-0$/; # don't care for base-0\n+\tmy $sha = ptag($file);\n+\tchomp $sha;\n+\t# reconvert the 3rd '--' sequence from the end\n+\t# into a slash\n+\t# $file = reverse $file;\n+\t# $file =~ s!^(.+?--.+?--.+?--.+?)--(.+)$!$1/$2!;\n+\t# $file = reverse $file;\n+\t$rptags{$sha} = $file;\n+    }\n+    closedir DIR;\n }\n \n # process patchsets\n@@ -345,6 +369,9 @@ foreach my $ps (@psets) {\n         }\n     }\n     \n+    if ($ps->{merges}) {\n+        push @par, find_parents($ps);\n+    }\n     my $par = join (' ', @par);\n \n     #    \n@@ -391,7 +418,8 @@ foreach my $ps (@psets) {\n     print \" * Committed $ps->{id}\\n\";\n     print \"   + tree   $tree\\n\";\n     print \"   + commit $commitid\\n\";\n-    # print \"   + commit date is  $ps->{date} \\n\";\n+    $opt_v && print \"   + commit date is  $ps->{date} \\n\";\n+    $opt_v && print \"   + parents:  $par \\n\";\n }\n \n sub branchname {\n@@ -556,7 +584,7 @@ sub tag {\n             or die \"Cannot write tag $tag: $!\\n\";\n         close(C)\n             or die \"Cannot write tag $tag: $!\\n\";\n-        print \"Created tag '$tag' on '$commit'\\n\" if $opt_v;\n+        print \" * Created tag ' $tag' on '$commit'\\n\" if $opt_v;\n     } else {                    # read\n         open(C,\"<.git/refs/tags/$tag\")\n             or die \"Cannot read tag $tag: $!\\n\";\n@@ -587,6 +615,8 @@ sub ptag {\n             or die \"Cannot write tag $tag: $!\\n\";\n         close(C)\n             or die \"Cannot write tag $tag: $!\\n\";\n+\t$rptags{$commit} = $tag \n+\t    unless $tag =~ m/--base-0$/;\n     } else {                    # read\n         # if the tag isn't there, return 0\n         unless ( -s \".git/archimport/tags/$tag\") {\n@@ -599,6 +629,152 @@ sub ptag {\n         die \"Error reading tag $tag: $!\\n\" unless length $commit == 40;\n         close(C)\n             or die \"Cannot read tag $tag: $!\\n\";\n+\tunless (defined $rptags{$commit}) {\n+\t    $rptags{$commit} = $tag;\n+\t}\n         return $commit;\n     }\n }\n+\n+sub find_parents {\n+    #\n+    # Identify what branches are merging into me\n+    # and whether we are fully merged\n+    # git-merge-base <headsha> <headsha> should tell\n+    # me what the base of the merge should be \n+    #\n+    my $ps = shift;\n+\n+    my %branches; # holds an arrayref per branch\n+                  # the arrayref contains a list of\n+                  # merged patches between the base\n+                  # of the merge and the current head\n+\n+    my @parents;  # parents found for this commit\n+\n+    # simple loop to split the merges\n+    # per branch\n+    foreach my $merge (@{$ps->{merges}}) {\n+\tmy $branch = branchname($merge);\n+\tunless (defined $branches{$branch} ){\n+\t    $branches{$branch} = [];\n+\t}\n+\tpush @{$branches{$branch}}, $merge;\n+    }\n+\n+    #\n+    # foreach branch find a merge base and walk it to the \n+    # head where we are, collecting the merged patchsets that\n+    # Arch has recorded. Keep that in @have\n+    # Compare that with the commits on the other branch\n+    # between merge-base and the tip of the branch (@need)\n+    # and see if we have a series of consecutive patches\n+    # starting from the merge base. The tip of the series\n+    # of consecutive patches merged is our new parent for \n+    # that branch.\n+    #\n+    foreach my $branch (keys %branches) {\n+\tmy $mergebase = `git-merge-base $branch $ps->{branch}`;\n+\tdie \"Cannot find merge base for $branch and $ps->{branch}\" if $?;\n+\tchomp $mergebase;\n+\n+\t# now walk up to the mergepoint collecting what patches we have\n+\tmy $branchtip = git_rev_parse($ps->{branch});\n+\tmy @ancestors = `git-rev-list --merge-order $branchtip ^$mergebase`;\n+\tmy %have; # collected merges this branch has\n+\tforeach my $merge (@{$ps->{merges}}) {\n+\t    $have{$merge} = 1;\n+\t}\n+\tmy %ancestorshave;\n+\tforeach my $par (@ancestors) {\n+\t    $par = commitid2pset($par);\n+\t    if (defined $par->{merges}) {\n+\t\tforeach my $merge (@{$par->{merges}}) {\n+\t\t    $ancestorshave{$merge}=1;\n+\t\t}\n+\t    }\n+\t}\n+\t# print \"++++ Merges in $ps->{id} are....\\n\";\n+\t# my @have = sort keys %have;\tprint Dumper(\\@have);\n+\n+\t# merge what we have with what ancestors have\n+\t%have = (%have, %ancestorshave);\n+\n+\t# see what the remote branch has - these are the merges we \n+\t# will want to have in a consecutive series from the mergebase\n+\tmy $otherbranchtip = git_rev_parse($branch);\n+\tmy @needraw = `git-rev-list --merge-order $otherbranchtip ^$mergebase`;\n+\tmy @need;\n+\tforeach my $needps (@needraw) { \t# get the psets\n+\t    $needps = commitid2pset($needps);\n+\t    # git-rev-list will also\n+\t    # list commits merged in via earlier \n+\t    # merges. we are only interested in commits\n+\t    # from the branch we're looking at\n+\t    if ($branch eq $needps->{branch}) {\n+\t\tpush @need, $needps->{id};\n+\t    }\n+\t}\n+\n+\t# print \"++++ Merges from $branch we want are....\\n\";\n+\t# print Dumper(\\@need);\n+\n+\tmy $newparent;\n+\twhile (my $needed_commit = pop @need) {\n+\t    if ($have{$needed_commit}) {\n+\t\t$newparent = $needed_commit;\n+\t    } else {\n+\t\tlast; # break out of the while\n+\t    }\n+\t}\n+\tif ($newparent) {\n+\t    push @parents, $newparent;\n+\t}\n+\n+\n+    } # end foreach branch\n+\n+    # prune redundant parents\n+    my %parents;\n+    foreach my $p (@parents) {\n+\t$parents{$p} = 1;\n+    }\n+    foreach my $p (@parents) {\n+\tnext unless exists $psets{$p}{merges};\n+\tnext unless ref    $psets{$p}{merges};\n+\tmy @merges = @{$psets{$p}{merges}};\n+\tforeach my $merge (@merges) {\n+\t    if ($parents{$merge}) { \n+\t\tdelete $parents{$merge};\n+\t    }\n+\t}\n+    }\n+    @parents = keys %parents;\n+    @parents = map { \" -p \" . ptag($_) } @parents;\n+    return @parents;\n+}\n+\n+sub git_rev_parse {\n+    my $name = shift;\n+    my $val  = `git-rev-parse $name`;\n+    die \"Error: git-rev-parse $name\" if $?;\n+    chomp $val;\n+    return $val;\n+}\n+\n+# resolve a SHA1 to a known patchset\n+sub commitid2pset {\n+    my $commitid = shift;\n+    chomp $commitid;\n+    my $name = $rptags{$commitid} \n+\t|| die \"Cannot find reverse tag mapping for $commitid\";\n+    # the keys in %rptag  are slightly munged; unmunge\n+    # reconvert the 3rd '--' sequence from the end\n+    # into a slash\n+    $name = reverse $name;\n+    $name =~ s!^(.+?--.+?--.+?--.+?)--(.+)$!$1/$2!;\n+    $name = reverse $name;\n+    my $ps   = $psets{$name} \n+\t|| (print Dumper(sort keys %psets)) && die \"Cannot find patchset for $name\";\n+    return $ps;\n+}\n"}]}