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.
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).
16 # list of all commits, in order
18 # maps short commit names to long ones
20 # maps commit -> parents
22 # maps commit -> children
24 # maps commit -> file_name -> hunk list
25 # where hunk list is a struct returned by hunks_data()
26 my %commit_changes = ();
32 if ($seen{$_[0]} eq undef) {
34 $seen{$_[0]} = $#list;
40 my $index = $seen{$_[0]};
41 return if $index eq undef;
43 splice(@list, $index, 1);
44 for (; $i <= $#list; $i++) {
45 $seen{$list[$i]} = $i;
48 'contains' => sub ($) {
49 return $seen{$_[0]} ne undef;
52 map { &$add($_) } @
{$_[0]->{'list'}()};
55 my $cloned = ordered_set
();
56 map { $cloned->{'add'}($_) } @list;
65 sub imply_parents
($$) {
69 foreach my $parent(@
$parents) {
70 next if $child eq $parent;
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);
85 my $insert = sub ($$$$) {
86 splice(@begin, $_[0], 0, $_[1]);
87 splice(@end, $_[0], 0, $_[2]);
88 splice(@revisions, $_[0], 0, $_[3]);
96 'revisions' => \
@revisions,
100 if (ref($_[2]) ne 'HASH') {
101 my $set = ordered_set
();
102 $set->{'add'}($_[2]);
105 push(@revisions, $_[2]);
108 my @begin2 = @
{$_[0]->{'begin'}};
109 my @end2 = @
{$_[0]->{'end'}};
110 my @revisions2 = @
{$_[0]->{'revisions'}};
113 while ($i <= $#end && $j <= $#end2) {
114 if ($begin[$i] >= $end2[$j]) {
115 &$insert($i, $begin2[$j], $end2[$j], $revisions2[$j]);
117 } elsif ($end[$i] > $begin2[$j]) {
118 if ($begin[$i] < $begin2[$j]) {
119 &$insert($i, $begin[$i], $begin2[$j], $revisions[$i]->{'clone'}());
121 } elsif ($begin1 > $begin2[$j]) {
122 &$insert($i, $begin2[$j], $begin[$i], $revisions2[$j]->{'clone'}());
125 if ($end[$i] < $end2[$j]) {
126 &$insert($i + 1, $end[$i], $end2[$j], $revisions2[$j]->{'clone'}());
127 $revisions[$i]->{'merge'}($revisions2[$j]);
129 } elsif ($end[$i] > $end2[$j]) {
130 &$insert($i + 1, $end2[$j], $end[$i], $revisions[$i]->{'clone'}());
131 $revisions[$i]->{'merge'}($revisions2[$j]);
134 $revisions[$i]->{'merge'}($revisions2[$j]);
139 while ($j <= $#end2) {
140 push(@begin, $begin2[$j]);
141 push(@end, $end2[$j]);
142 push(@revisions, $revisions2[$j]);
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'}};
153 while ($i <= $#end && $j <= $#end2) {
154 if ($begin[$i] >= $end2[$j]) {
155 &$insert($i, $begin2[$j], $end2[$j], $revisions2[$j]);
157 } elsif ($end[$i] > $begin2[$j]) {
158 if ($begin1 > $begin2[$j]) {
159 &$insert($i, $begin2[$j], $begin[$i], $revisions2[$j]->{'clone'}());
162 if ($end[$i] < $end2[$j]) {
163 &$insert($i + 1, $end[$i], $end2[$j], $revisions2[$j]->{'clone'}());
169 while ($j <= $#end2) {
170 push(@begin, $begin2[$j]);
171 push(@end, $end2[$j]);
172 push(@revisions, $revisions2[$j]);
176 'clone-for-hunk-adjustment' => sub () {
177 my $clone = hunks_data
();
179 $clone->{'hunk'} = sub ($$$$) {
182 $clone->{'finish'} = sub () {
183 my $i = 0, $offset = 0;
184 while ($i <= $#end) {
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);
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]);
200 while ($i <= $#end) {
201 $clone->{'add'}($offset + $begin[$i], $offset + $end[$i], $revisions[$i]);
204 delete $clone->{'hunk'};
205 delete $clone->{'finish'};
209 'implied-revisions' => sub ($) {
210 my @begin2 = @
{$_[0]->{'begin'}};
211 my @end2 = @
{$_[0]->{'end'}};
212 my @revisions2 = @
{$_[0]->{'revisions'}};
215 my $result = ordered_set
();
216 while ($i <= $#end && $j <= $#end2) {
217 if ($end[$i] < $begin2[$j]) {
219 } elsif ($begin[$i] > $end2[$j]) {
222 $result->{'merge'}($revisions2[$j]);
226 return $result->{'list'}();
231 sub handle_single_parent
($$$$$) {
232 my $current_commit = $_[0];
234 my %original_parent_changes = %{$_[2]};
236 my $parent_changes = $_[4];
240 my $parent_hunks = undef;
241 my %handled_files = ();
243 my $finish_file = sub () {
244 if ($hunks ne undef) {
245 if ($changes->{$file_name} eq undef) {
246 $changes->{$file_name} = $hunks;
248 $changes->{$file_name}->{'merge'}($hunks);
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;
256 $parent_changes->{$file_name}->{'merge'}($parent_hunks);
259 $handled_files{$file_name} = 1 if $file_name ne undef;
263 # TODO: handle spaces and even " b/" as part of a filename
264 if (/^diff --git a\/.* b\
/(.*)$/) {
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;
278 $hunks->{'add'}($begin1, $end1, $current_commit);
279 $parent_hunks->{'hunk'}($begin0, $end0, $begin1, $end1) if $parent_hunks ne undef;
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;
290 $parent_changes->{$file_name}->{'merge'}($hunks);
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`).
303 sub read_commit
($$) {
304 my $current_commit = $_[0];
305 my @parents = @
{$_[1]};
307 my %parent_changes = ();
308 $commit_changes{$current_commit} = \
%changes;
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};
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);
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);
330 map { $changes{$_} = $parent_changes{$_} if $changes{$_} eq undef; } keys %parent_changes;
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`.
338 sub read_commits
($) {
339 my $commit_range = $_[0];
344 my $previous_file_name;
346 my @current_file_changes;
347 my @parent_file_changes;
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);
355 open (my $in, '-|', @command);
358 print $i++ . "...\r";
360 if (/^([0-9a-f]+) ([0-9a-f]+) ([0-9a-f ]*)$/) {
363 @parents = split(/ /, $3);
365 push(@commits, $current);
366 $short2long{$current} = $sha1;
367 read_commit
($current, \
@parents);
376 for (my $i = 0; $i <= $#ARGV; $i++) {
377 if ($ARGV[$i] eq '--') {
381 if ($ARGV[$i] eq '--gitk') {
383 } elsif ($ARGV[$i] eq '--simplify') {
385 } elsif ($ARGV[$i] eq '--no-simplify') {
390 splice(@ARGV, $i, 1);
394 read_commits
(\
@ARGV);
396 sub get_parents
($) {
397 my $parents = $forward{$_[0]};
398 return [] if $parents eq undef;
399 return $parents->{'list'}();
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).
407 foreach my $current (@commits) {
411 foreach my $parent (@
{get_parents
($current)}) {
412 $parents{$parent} = 1;
413 foreach my $grampy (@
{get_parents
($parent)}) {
414 push(@stack, $grampy);
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};
424 foreach my $parent (@
{get_parents
($commit)}) {
425 push(@stack, $parent);
432 # Unfortunately, there is no scriptable way to use the --graph support of `git
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.
439 my $git_dir = `git rev-parse --git-dir`;
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;
460 $ENV{'GIT_GRAFT_FILE'} = $grafts_file;
462 # add file arguments from @ARGV
463 for (my $i = 0; $i <= $#ARGV; $i++) {
464 next if $ARGV[$i] ne '--';
466 push(@args, @ARGV[$i..$#ARGV]) if $i <= $#ARGV;