share/msysGit/implied-commit-order.perl

   1 #!/usr/bin/perl
   2
   3 # List the given commit range similar to "git log --graph" but instead of
   4 # showing the branches as recorded in the commits, show the implicit commit
   5 # hierarchy as far as merge conflicts are concerned: a commit is considered an
   6 # "implicit ancestor" of a descendant commit if exchanging both in the commit
   7 # history would cause merge conflicts, i.e. if their changes overlap.
   8 #
   9 # The idea originates from the Darcs SCM which -- while its underlying idea is
  10 # cool, and replicated in this Perl script -- was doomed by the choice of
  11 # programming language and by trying to describe the principle via quantum
  12 # physics (when the proper scientific background would have been group theory,
  13 # really, although that would have been even worse a vehicle to document the
  14 # motivation and implementation).
  15
  16 # list of all commits, in order
  17 my @commits = ();
  18 # maps short commit names to long ones
  19 my %short2long = ();
  20 # maps commit -> parents
  21 my %forward = ();
  22 # maps commit -> children
  23 my %backward = ();
  24 # maps commit -> file_name -> hunk list
  25 # where hunk list is a struct returned by hunks_data()
  26 my %commit_changes = ();
  27
  28 sub ordered_set () {
  29         my @list = ();
  30         my %seen = ();
  31         my $add = sub ($) {
  32                 if ($seen{$_[0]} eq undef) {
  33                         push(@list, $_[0]);
  34                         $seen{$_[0]} = $#list;
  35                 }
  36         };
  37         return {
  38                 'add' => $add,
  39                 'remove' => sub ($) {
  40                         my $index = $seen{$_[0]};
  41                         return if $index eq undef;
  42                         delete $seen{$_[0]};
  43                         splice(@list, $index, 1);
  44                         for (; $i <= $#list; $i++) {
  45                                 $seen{$list[$i]} = $i;
  46                         }
  47                 },
  48                 'contains' => sub ($) {
  49                         return $seen{$_[0]} ne undef;
  50                 },
  51                 'merge' => sub ($) {
  52                         map { &$add($_) } @{$_[0]->{'list'}()};
  53                 },
  54                 'clone' => sub () {
  55                         my $cloned = ordered_set();
  56                         map { $cloned->{'add'}($_) } @list;
  57                         return $cloned;
  58                 },
  59                 'list' => sub () {
  60                         return \@list;
  61                 }
  62         };
  63 }
  64
  65 sub imply_parents ($$) {
  66         my $child = $_[0];
  67         my $parents = $_[1];
  68
  69         foreach my $parent(@$parents) {
  70                 next if $child eq $parent;
  71
  72                 $forward{$child} = ordered_set() if $forward{$child} eq undef;
  73                 return if ($forward{$child}->{'contains'}($parent));
  74                 $forward{$child}->{'add'}($parent);
  75                 $backward{$parent} = ordered_set() if $backward{$parent} eq undef;
  76                 $backward{$parent}->{'add'}($child);
  77         }
  78 }
  79
  80 sub hunks_data () {
  81         my @begin = ();
  82         my @end = ();
  83         my @revisions = ();
  84
  85         my $insert = sub ($$$$) {
  86                 splice(@begin, $_[0], 0, $_[1]);
  87                 splice(@end, $_[0], 0, $_[2]);
  88                 splice(@revisions, $_[0], 0, $_[3]);
  89         };
  90         return {
  91                 'size' => sub () {
  92                         return $#end;
  93                 },
  94                 'begin' => \@begin,
  95                 'end' => \@end,
  96                 'revisions' => \@revisions,
  97                 'add' => sub ($$$) {
  98                         push(@begin, $_[0]);
  99                         push(@end, $_[1]);
 100                         if (ref($_[2]) ne 'HASH') {
 101                                 my $set = ordered_set();
 102                                 $set->{'add'}($_[2]);
 103                                 $_[2] = $set;
 104                         }
 105                         push(@revisions, $_[2]);
 106                 },
 107                 'merge' => sub ($) {
 108                         my @begin2 = @{$_[0]->{'begin'}};
 109                         my @end2 = @{$_[0]->{'end'}};
 110                         my @revisions2 = @{$_[0]->{'revisions'}};
 111                         my $i = 0;
 112                         my $j = 0;
 113                         while ($i <= $#end && $j <= $#end2) {
 114                                 if ($begin[$i] >= $end2[$j]) {
 115                                         &$insert($i, $begin2[$j], $end2[$j], $revisions2[$j]);
 116                                         $j++;
 117                                 } elsif ($end[$i] > $begin2[$j]) {
 118                                         if ($begin[$i] < $begin2[$j]) {
 119                                                 &$insert($i, $begin[$i], $begin2[$j], $revisions[$i]->{'clone'}());
 120                                                 $i++;
 121                                         } elsif ($begin1 > $begin2[$j]) {
 122                                                 &$insert($i, $begin2[$j], $begin[$i], $revisions2[$j]->{'clone'}());
 123                                                 $i++;
 124                                         }
 125                                         if ($end[$i] < $end2[$j]) {
 126                                                 &$insert($i + 1, $end[$i], $end2[$j], $revisions2[$j]->{'clone'}());
 127                                                 $revisions[$i]->{'merge'}($revisions2[$j]);
 128                                                 $i++;
 129                                         } elsif ($end[$i] > $end2[$j]) {
 130                                                 &$insert($i + 1, $end2[$j], $end[$i], $revisions[$i]->{'clone'}());
 131                                                 $revisions[$i]->{'merge'}($revisions2[$j]);
 132                                                 $i++;
 133                                         } else {
 134                                                 $revisions[$i]->{'merge'}($revisions2[$j]);
 135                                         }
 136                                 }
 137                                 $i++;
 138                         }
 139                         while ($j <= $#end2) {
 140                                 push(@begin, $begin2[$j]);
 141                                 push(@end, $end2[$j]);
 142                                 push(@revisions, $revisions2[$j]);
 143                                 $j++;
 144                         }
 145                 },
 146                 # merge-weakly merges only the specified hunks which do not overlap with the current ones.
 147                 'merge-weakly' => sub ($) {
 148                         my @begin2 = @{$_[0]->{'begin'}};
 149                         my @end2 = @{$_[0]->{'end'}};
 150                         my @revisions2 = @{$_[0]->{'revisions'}};
 151                         my $i = 0;
 152                         my $j = 0;
 153                         while ($i <= $#end && $j <= $#end2) {
 154                                 if ($begin[$i] >= $end2[$j]) {
 155                                         &$insert($i, $begin2[$j], $end2[$j], $revisions2[$j]);
 156                                         $j++;
 157                                 } elsif ($end[$i] > $begin2[$j]) {
 158                                         if ($begin1 > $begin2[$j]) {
 159                                                 &$insert($i, $begin2[$j], $begin[$i], $revisions2[$j]->{'clone'}());
 160                                                 $i++;
 161                                         }
 162                                         if ($end[$i] < $end2[$j]) {
 163                                                 &$insert($i + 1, $end[$i], $end2[$j], $revisions2[$j]->{'clone'}());
 164                                                 $i++;
 165                                         }
 166                                 }
 167                                 $i++;
 168                         }
 169                         while ($j <= $#end2) {
 170                                 push(@begin, $begin2[$j]);
 171                                 push(@end, $end2[$j]);
 172                                 push(@revisions, $revisions2[$j]);
 173                                 $j++;
 174                         }
 175                 },
 176                 'clone-for-hunk-adjustment' => sub () {
 177                         my $clone = hunks_data();
 178                         my @hunks = ();
 179                         $clone->{'hunk'} = sub ($$$$) {
 180                                 push(@hunks, @_);
 181                         };
 182                         $clone->{'finish'} = sub () {
 183                                 my $i = 0, $offset = 0;
 184                                 while ($i <= $#end) {
 185                                         last if $#hunks < 0;
 186                                         if ($end[$i] < $hunks[0]) {
 187                                                 $clone->{'add'}($offset + $begin[$i], $offset + $end[$i], $revisions[$i]);
 188                                         } elsif ($begin[$i] > $hunks[1]) {
 189                                                 $offset = $hunks[3] - $hunks[1];
 190                                                 splice(@hunks, 0, 4);
 191                                                 next;
 192                                         } else {
 193                                                 my $begin2 = $begin[$i] < $hunks[0] ? $begin[$i] + $offset : $hunks[2];
 194                                                 $offset = $hunks[3] - $hunks[1];
 195                                                 my $end2 = $end[$i] <= $hunks[1] ? $hunks[2] : $end[$i] + $offset;
 196                                                 $clone->{'add'}($begin2, $end2, $revisions[$i]);
 197                                         }
 198                                         $i++;
 199                                 }
 200                                 while ($i <= $#end) {
 201                                         $clone->{'add'}($offset + $begin[$i], $offset + $end[$i], $revisions[$i]);
 202                                         $i++;
 203                                 }
 204                                 delete $clone->{'hunk'};
 205                                 delete $clone->{'finish'};
 206                         };
 207                         return $clone;
 208                 },
 209                 'implied-revisions' => sub ($) {
 210                         my @begin2 = @{$_[0]->{'begin'}};
 211                         my @end2 = @{$_[0]->{'end'}};
 212                         my @revisions2 = @{$_[0]->{'revisions'}};
 213                         my $i = 0;
 214                         my $j = 0;
 215                         my $result = ordered_set();
 216                         while ($i <= $#end && $j <= $#end2) {
 217                                 if ($end[$i] < $begin2[$j]) {
 218                                         $i++;
 219                                 } elsif ($begin[$i] > $end2[$j]) {
 220                                         $j++;
 221                                 } else {
 222                                         $result->{'merge'}($revisions2[$j]);
 223                                         $j++;
 224                                 }
 225                         }
 226                         return $result->{'list'}();
 227                 }
 228         };
 229 }
 230
 231 sub handle_single_parent ($$$$$) {
 232         my $current_commit = $_[0];
 233         my $in = $_[1];
 234         my %original_parent_changes = %{$_[2]};
 235         my $changes = $_[3];
 236         my $parent_changes = $_[4];
 237
 238         my $file_name;
 239         my $hunks = undef;
 240         my $parent_hunks = undef;
 241         my %handled_files = ();
 242
 243         my $finish_file = sub () {
 244                 if ($hunks ne undef) {
 245                         if ($changes->{$file_name} eq undef) {
 246                                 $changes->{$file_name} = $hunks;
 247                         } else {
 248                                 $changes->{$file_name}->{'merge'}($hunks);
 249                         }
 250                 }
 251                 if ($parent_hunks ne undef) {
 252                         $parent_hunks->{'finish'}();
 253                         if ($parent_changes->{$file_name} eq undef) {
 254                                 $parent_changes->{$file_name} = $parent_hunks;
 255                         } else {
 256                                 $parent_changes->{$file_name}->{'merge'}($parent_hunks);
 257                         }
 258                 }
 259                 $handled_files{$file_name} = 1 if $file_name ne undef;
 260         };
 261
 262         while (<$in>) {
 263                 # TODO: handle spaces and even " b/" as part of a filename
 264                 if (/^diff --git a\/.* b\/(.*)$/) {
 265                         &$finish_file();
 266                         $file_name = $1;
 267                         $hunks = hunks_data();
 268                         $parent_hunks = $original_parent_changes{$file_name};
 269                         $parent_hunks = $parent_hunks->{'clone-for-hunk-adjustment'}() if $parent_hunks ne undef;
 270                 } elsif (/^@@ -(\d+)(,(\d+))? \+(\d+)(,(\d+))? @@/) {
 271                         my $length0 = $3 ne '' ? $3 : 1;
 272                         my $begin0 = $1 + ($3 eq '0' ? 1 : 0);
 273                         my $end0 = $begin0 + $length0;
 274                         my $length1 = $6 ne '' ? $6 : 1;
 275                         my $begin1 = $4 + ($6 eq '0' ? 1 : 0);
 276                         my $end1 = $begin1 + $length1;
 277
 278                         $hunks->{'add'}($begin1, $end1, $current_commit);
 279                         $parent_hunks->{'hunk'}($begin0, $end0, $begin1, $end1) if $parent_hunks ne undef;
 280                 }
 281         }
 282         &$finish_file();
 283
 284         foreach my $file_name (keys %original_parent_changes) {
 285                 if ($handled_files{$file_name} eq undef) {
 286                         my $hunks = $original_parent_changes{$file_name};
 287                         if ($parent_changes->{$file_name} eq undef) {
 288                                 $parent_changes->{$file_name} = $hunks;
 289                         } else {
 290                                 $parent_changes->{$file_name}->{'merge'}($hunks);
 291                         }
 292                 }
 293         }
 294 }
 295
 296 # Reads the diff(s) associated with the (merge) commit into the global data
 297 # structures. Takes previously read information about ancestors into account.
 298 # After this method has been called on all the commits of interest,
 299 # $commit_changes{$commit} will refer to a hash that maps all touched files to
 300 # the respective hunk lists (that document what commits touched which parts,
 301 # sort of a simultaneous `git blame`).
 302
 303 sub read_commit ($$) {
 304         my $current_commit = $_[0];
 305         my @parents = @{$_[1]};
 306         my %changes = ();
 307         my %parent_changes = ();
 308         $commit_changes{$current_commit} = \%changes;
 309
 310         # use the empty tree to compare initial commits against
 311         @parents = ( '4b825dc642cb6eb9a060e54bf8d69288fbee4904' ) if $#parents < 0;
 312         foreach my $parent (@parents) {
 313                 my $original_parent_changes = $commit_changes{$parent};
 314
 315                 my @command = ('git', 'diff', '-U0', # '-M',
 316                         $parent, $current_commit);
 317                 open(my $in, '-|', @command);
 318                 handle_single_parent($current_commit, $in, $original_parent_changes, \%changes, \%parent_changes);
 319                 close($in);
 320         }
 321
 322         foreach my $file_name (keys %changes) {
 323                 my $parent_hunks = $parent_changes{$file_name};
 324                 next if $parent_hunks eq undef;
 325                 my $hunks = $changes{$file_name};
 326                 imply_parents($current_commit, $hunks->{'implied-revisions'}($parent_hunks));
 327                 $hunks->{'merge-weakly'}($parent_hunks);
 328         }
 329
 330         map { $changes{$_} = $parent_changes{$_} if $changes{$_} eq undef; } keys %parent_changes;
 331
 332 }
 333
 334 # Reads all necessary information for the commit range specified by the argument
 335 # which is expected to be a reference to an array of command-line arguments
 336 # appropriate for being called with `git log`.
 337
 338 sub read_commits ($) {
 339         my $commit_range = $_[0];
 340         my $current;
 341         my @parents;
 342         my %parent_changes;
 343
 344         my $previous_file_name;
 345         my $current_file;
 346         my @current_file_changes;
 347         my @parent_file_changes;
 348         my $offset;
 349
 350         my @command = ('git', 'log', '--reverse', '--topo-order',
 351                 '--format=%H %h %p');
 352         # TODO: filter out --graph and stuff
 353         push(@command, @$commit_range);
 354         my $i = 1;
 355         open (my $in, '-|', @command);
 356         while (<$in>) {
 357                 next if (/^$/);
 358                 print $i++ . "...\r";
 359                 chomp;
 360                 if (/^([0-9a-f]+) ([0-9a-f]+) ([0-9a-f ]*)$/) {
 361                         my $sha1 = $1;
 362                         $current = $2;
 363                         @parents = split(/ /, $3);
 364
 365                         push(@commits, $current);
 366                         $short2long{$current} = $sha1;
 367                         read_commit($current, \@parents);
 368                 }
 369         }
 370         close($in);
 371 }
 372
 373 my $use_gitk = 0;
 374 my $simplify = 1;
 375 my $dashdash = -1;
 376 for (my $i = 0; $i <= $#ARGV; $i++) {
 377         if ($ARGV[$i] eq '--') {
 378                 $dashdash = $i;
 379                 last;
 380         }
 381         if ($ARGV[$i] eq '--gitk') {
 382                 $use_gitk = 1;
 383         } elsif ($ARGV[$i] eq '--simplify') {
 384                 $simplify = 1;
 385         } elsif ($ARGV[$i] eq '--no-simplify') {
 386                 $simplify = 0;
 387         } else {
 388                 next;
 389         }
 390         splice(@ARGV, $i, 1);
 391         $i--;
 392 }
 393
 394 read_commits(\@ARGV);
 395
 396 sub get_parents ($) {
 397         my $parents = $forward{$_[0]};
 398         return [] if $parents eq undef;
 399         return $parents->{'list'}();
 400 }
 401
 402 # We can simplify the implied history by skipping parents that are ancestors of
 403 # other parents (e.g. if a commit is already an implied grandparent, it does
 404 # not have to be an implied parent, too).
 405
 406 if ($simplify) {
 407         foreach my $current (@commits) {
 408                 my @stack = ();
 409                 my %seen = ();
 410                 my %parents = ();
 411                 foreach my $parent (@{get_parents($current)}) {
 412                         $parents{$parent} = 1;
 413                         foreach my $grampy (@{get_parents($parent)}) {
 414                                 push(@stack, $grampy);
 415                         }
 416                 }
 417                 while ($#stack >= 0) {
 418                         my $commit = pop(@stack);
 419                         next if $seen{$commit} ne undef;
 420                         if ($parents{$commit} ne undef) {
 421                                 $forward{$current}->{'remove'}($commit);
 422                                 delete $parents{$commit};
 423                         }
 424                         foreach my $parent (@{get_parents($commit)}) {
 425                                 push(@stack, $parent);
 426                         }
 427                         $seen{$commit} = 1;
 428                 }
 429         }
 430 }
 431
 432 # Unfortunately, there is no scriptable way to use the --graph support of `git
 433 # log`.
 434 #
 435 # Fortunately, however, there is a way to circumvent that: by defining the
 436 # commit order using temporary grafts, written into a temporary file and used
 437 # via a temporary GIT_GRAFT_FILE env variable.
 438
 439 my $git_dir = `git rev-parse --git-dir`;
 440 chomp $git_dir;
 441
 442 sub show () {
 443         my $grafts_file = $git_dir . '/TEMP-GRAFTS';
 444         my @args = ('log', '--graph', '--format=%h %s%n');
 445         open(my $grafts, '>', $grafts_file);
 446         foreach my $current (@commits) {
 447                 push(@args, $current) if $backward{$current} eq undef;
 448                 print $grafts $short2long{$current};
 449                 if (ref($forward{$current}) eq 'HASH') {
 450                         foreach my $parent (@{$forward{$current}->{'list'}()}) {
 451                                 my $sha1 = $short2long{$parent};
 452                                 if ($sha1 ne undef) {
 453                                         print $grafts ' ' . $sha1;
 454                                 }
 455                         }
 456                 }
 457                 print $grafts "\n";
 458         }
 459         close($grafts);
 460         $ENV{'GIT_GRAFT_FILE'} = $grafts_file;
 461         push(@args, '--');
 462         # add file arguments from @ARGV
 463         for (my $i = 0; $i <= $#ARGV; $i++) {
 464                 next if $ARGV[$i] ne '--';
 465                 $i++;
 466                 push(@args, @ARGV[$i..$#ARGV]) if $i <= $#ARGV;
 467                 last;
 468         }
 469         if ($use_gitk) {
 470                 splice(@args, 0, 3);
 471                 exec('gitk', @args);
 472         }
 473         exec('git', @args);
 474 }
 475
 476 show();