forked from mhagger/git-imerge
-
Notifications
You must be signed in to change notification settings - Fork 0
/
git-imerge
executable file
·2797 lines (2341 loc) · 94.3 KB
/
git-imerge
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#! /usr/bin/env python2
# Copyright 2012-2013 Michael Haggerty <mhagger@alum.mit.edu>
#
# This file is part of git-imerge.
#
# git-imerge is free software: you can redistribute it and/or
# modify it under the terms of the GNU General Public License as
# published by the Free Software Foundation, either version 2 of the
# License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# General Public License for more details.
#
# You should have received a copy of the GNU General Public License
# along with this program. If not, see
# <http://www.gnu.org/licenses/>.
r"""Git incremental merge
Perform the merge between two branches incrementally. If conflicts
are encountered, figure out exactly which pairs of commits conflict,
and present the user with one pairwise conflict at a time for
resolution.
git-imerge has two primary design goals:
* Reduce the pain of resolving merge conflicts to its unavoidable
minimum, by finding and presenting the smallest possible conflicts:
those between the changes introduced by one commit from each branch.
* Allow a merge to be saved, tested, interrupted, published, and
collaborated on while it is in progress.
The best thing to read to get started is "git-imerge: A Practical
Introduction" [1]. The theory and benefits of incremental merging are
described in minute detail in a series of blog posts [2], as are the
benefits of retaining history when doing a rebase [3].
Multiple incremental merges can be in progress at the same time. Each
incremental merge has a name, and its progress is recorded in the Git
repository as references under 'refs/imerge/NAME'. The current state
of an incremental merge can (crudely) be visualized using the
"diagram" command.
An incremental merge can be interrupted and resumed arbitrarily, or
even pushed to a server to allow somebody else to work on it.
When an incremental merge is finished, you can discard the
intermediate merge commits and create a simpler history to record
permanently in your project repository using either the "finish" or
"simplify" command. The incremental merge can be simplified in one of
three ways:
* merge
keep only a simple merge of the second branch into the first
branch, discarding all intermediate merges. The result is
similar to what you would get from
git checkout BRANCH1
git merge BRANCH2
* rebase
keep the versions of the commits from the second branch rebased
onto the first branch. The result is similar to what you would
get from
git checkout BRANCH2
git rebase BRANCH1
* rebase-with-history
like rebase, except that each of the rebased commits is recorded
as a merge from its original version to its rebased predecessor.
This is a style of rebasing that does not discard the old
version of the branch, and allows an already-published branch to
be rebased. See [3] for more information.
Simple operation:
For basic operation, you only need to know three git-imerge commands.
To merge BRANCH into MASTER or rebase BRANCH onto MASTER,
git checkout MASTER
git-imerge start --name=NAME --goal=GOAL --first-parent BRANCH
while not done:
<fix conflict presented to you>
git commit
git-imerge continue
git-imerge finish
where
NAME is the name for this merge (and also the default name of the
branch to which the results will be saved)
GOAL describes how you want to simplify the results:
"merge" for a simple merge
"rebase" for a simple rebase
"rebase-with-history" for a rebase that retains history. This
is equivalent to merging the commits from BRANCH into MASTER,
one commit at a time. In other words, it transforms this::
o---o---o---o MASTER
\
A---B---C---D BRANCH
into this::
o---o---o---o---A'--B'--C'--D' MASTER
\ / / / /
--------A---B---C---D BRANCH
This is like a rebase, except that it retains the history of
individual merges. See [3] for more information.
[1] http://softwareswirl.blogspot.com/2013/05/git-imerge-practical-introduction.html
[2] http://softwareswirl.blogspot.com/2012/12/the-conflict-frontier-of-nightmare-merge.html
http://softwareswirl.blogspot.com/2012/12/mapping-merge-conflict-frontier.html
http://softwareswirl.blogspot.com/2012/12/real-world-conflict-diagrams.html
http://softwareswirl.blogspot.com/2013/05/git-incremental-merge.html
http://softwareswirl.blogspot.com/2013/05/one-merge-to-rule-them-all.html
http://softwareswirl.blogspot.com/2013/05/incremental-merge-vs-direct-merge-vs.html
[3] http://softwareswirl.blogspot.com/2009/04/truce-in-merge-vs-rebase-war.html
http://softwareswirl.blogspot.com/2009/08/upstream-rebase-just-works-if-history.html
http://softwareswirl.blogspot.com/2009/08/rebase-with-history-implementation.html
"""
import sys
import re
import subprocess
import itertools
import functools
import argparse
from cStringIO import StringIO
import json
import os
# CalledProcessError, check_call, and check_output were not in the
# original Python 2.4 subprocess library, so implement it here if
# necessary (implementations are taken from the Python 2.7 library):
try:
from subprocess import CalledProcessError
except ImportError:
class CalledProcessError(Exception):
def __init__(self, returncode, cmd, output=None):
self.returncode = returncode
self.cmd = cmd
self.output = output
def __str__(self):
return "Command '%s' returned non-zero exit status %d" % (self.cmd, self.returncode)
try:
from subprocess import check_call
except ImportError:
def check_call(*popenargs, **kwargs):
retcode = subprocess.call(*popenargs, **kwargs)
if retcode:
cmd = kwargs.get("args")
if cmd is None:
cmd = popenargs[0]
raise CalledProcessError(retcode, cmd)
return 0
try:
from subprocess import check_output
except ImportError:
def check_output(*popenargs, **kwargs):
if 'stdout' in kwargs:
raise ValueError('stdout argument not allowed, it will be overridden.')
process = subprocess.Popen(stdout=subprocess.PIPE, *popenargs, **kwargs)
output, unused_err = process.communicate()
retcode = process.poll()
if retcode:
cmd = kwargs.get("args")
if cmd is None:
cmd = popenargs[0]
# We don't store output in the CalledProcessError because
# the "output" keyword parameter was not supported in
# Python 2.6:
raise CalledProcessError(retcode, cmd)
return output
STATE_VERSION = (1, 0, 0)
ZEROS = '0' * 40
ALLOWED_GOALS = [
#'full',
'rebase-with-history',
'rebase',
'merge',
]
DEFAULT_GOAL = 'merge'
class Failure(Exception):
"""An exception that indicates a normal failure of the script.
Failures are reported at top level via sys.exit(str(e)) rather
than via a Python stack dump."""
@classmethod
def wrap(klass, f):
"""Wrap a function inside a try...except that catches this error.
If the exception is thrown, call sys.exit(). This function
can be used as a decorator."""
@functools.wraps(f)
def wrapper(*args, **kw):
try:
return f(*args, **kw)
except klass, e:
sys.exit(str(e))
return wrapper
pass
class AnsiColor:
BLACK = '\033[0;30m'
RED = '\033[0;31m'
GREEN = '\033[0;32m'
YELLOW = '\033[0;33m'
BLUE = '\033[0;34m'
MAGENTA = '\033[0;35m'
CYAN = '\033[0;36m'
B_GRAY = '\033[0;37m'
D_GRAY = '\033[1;30m'
B_RED = '\033[1;31m'
B_GREEN = '\033[1;32m'
B_YELLOW = '\033[1;33m'
B_BLUE = '\033[1;34m'
B_MAGENTA = '\033[1;35m'
B_CYAN = '\033[1;36m'
WHITE = '\033[1;37m'
END = '\033[0m'
@classmethod
def disable(cls):
cls.BLACK = ''
cls.RED = ''
cls.GREEN = ''
cls.YELLOW = ''
cls.BLUE = ''
cls.MAGENTA = ''
cls.CYAN = ''
cls.B_GRAY = ''
cls.D_GRAY = ''
cls.B_RED = ''
cls.B_GREEN = ''
cls.B_YELLOW = ''
cls.B_BLUE = ''
cls.B_MAGENTA = ''
cls.B_CYAN = ''
cls.WHITE = ''
cls.END = ''
def iter_neighbors(iterable):
"""For an iterable (x0, x1, x2, ...) generate [(x0,x1), (x1,x2), ...]."""
i = iter(iterable)
try:
last = i.next()
except StopIteration:
return
for x in i:
yield (last, x)
last = x
def find_first_false(f, lo, hi):
"""Return the smallest i in lo <= i < hi for which f(i) returns False using bisection.
If there is no such i, return hi.
"""
# Loop invariant: f(i) returns True for i < lo; f(i) returns False
# for i >= hi.
while lo < hi:
mid = (lo + hi) // 2
if f(mid):
lo = mid + 1
else:
hi = mid
return lo
def call_silently(cmd):
try:
NULL = open('/dev/null', 'w')
except IOError:
NULL = subprocess.PIPE
p = subprocess.Popen(
cmd, stdout=NULL, stderr=subprocess.PIPE,
)
(out,err) = p.communicate()
retcode = p.wait()
if retcode:
raise CalledProcessError(retcode, cmd)
class UncleanWorkTreeError(Failure):
pass
def require_clean_work_tree(action):
"""Verify that the current tree is clean.
The code is a Python translation of the git-sh-setup(1) function
of the same name."""
process = subprocess.Popen(
['git', 'rev-parse', '--verify', 'HEAD'],
stdout=subprocess.PIPE, stderr=subprocess.PIPE,
)
_unused, err = process.communicate()
retcode = process.poll()
if retcode:
raise UncleanWorkTreeError(err.rstrip())
process = subprocess.Popen(
['git', 'update-index', '-q', '--ignore-submodules', '--refresh'],
stdout=subprocess.PIPE, stderr=subprocess.PIPE,
)
out, err = process.communicate()
retcode = process.poll()
if retcode:
raise UncleanWorkTreeError(err.rstrip() or out.rstrip())
error = []
try:
check_call(['git', 'diff-files', '--quiet', '--ignore-submodules'])
except CalledProcessError:
error.append('Cannot %s: You have unstaged changes.' % (action,))
try:
check_call([
'git', 'diff-index', '--cached', '--quiet',
'--ignore-submodules', 'HEAD', '--',
])
except CalledProcessError:
if not error:
error.append('Cannot %s: Your index contains uncommitted changes.' % (action,))
else:
error.append('Additionally, your index contains uncommitted changes.')
if error:
raise UncleanWorkTreeError('\n'.join(error))
def rev_parse(arg):
return check_output(['git', 'rev-parse', '--verify', '--quiet', arg]).strip()
def rev_list(*args):
return [
l.strip()
for l in check_output(['git', 'rev-list'] + list(args),).splitlines()
]
def get_type(arg):
"""Return the type of a git object ('commit', 'tree', 'blob', or 'tag')."""
return check_output(['git', 'cat-file', '-t', arg]).strip()
def get_tree(arg):
return rev_parse('%s^{tree}' % (arg,))
BRANCH_PREFIX = 'refs/heads/'
def checkout(refname):
if refname.startswith(BRANCH_PREFIX):
target = refname[len(BRANCH_PREFIX):]
else:
target = '%s^0' % (refname,)
check_call(['git', 'checkout', target])
def get_commit_sha1(arg):
"""Convert arg into a SHA1 and verify that it refers to a commit.
If not, raise ValueError."""
try:
return rev_parse('%s^{commit}' % (arg,))
except CalledProcessError:
raise ValueError('%r does not refer to a valid git commit' % (arg,))
def get_commit_parents(commit):
"""Return a list containing the parents of commit."""
return check_output(
['git', 'log', '--no-walk', '--pretty=format:%P', commit]
).strip().split()
def get_log_message(commit):
contents = check_output([
'git', 'cat-file', 'commit', commit
]).splitlines(True)
contents = contents[contents.index('\n') + 1:]
if contents and contents[-1][-1:] != '\n':
contents.append('\n')
return ''.join(contents)
def get_author_info(commit):
a = check_output([
'git', 'log', '-n1',
'--format=%an%x00%ae%x00%ad', commit
]).strip().split('\x00')
return {
'GIT_AUTHOR_NAME': a[0],
'GIT_AUTHOR_EMAIL': a[1],
'GIT_AUTHOR_DATE': a[2],
}
def commit_tree(tree, parents, msg, metadata=None):
"""Create a commit containing the specified tree.
metadata can be author or committer information to be added to the
environment; e.g., {'GIT_AUTHOR_NAME' : 'me'}.
Return the SHA-1 of the new commit object."""
cmd = ['git', 'commit-tree', tree]
for parent in parents:
cmd += ['-p', parent]
if metadata is not None:
env = os.environ.copy()
env.update(metadata)
else:
env = os.environ
process = subprocess.Popen(
cmd, env=env, stdin=subprocess.PIPE, stdout=subprocess.PIPE,
)
out, err = process.communicate(msg)
retcode = process.poll()
if retcode:
# We don't store the output in the CalledProcessError because
# the "output" keyword parameter was not supported in Python
# 2.6:
raise CalledProcessError(retcode, cmd)
return out.strip()
class TemporaryHead(object):
"""A context manager that records the current HEAD state then restores it.
The message is used for the reflog."""
def __enter__(self, message='imerge: restoring'):
self.message = message
try:
self.head_name = check_output(['git', 'symbolic-ref', '--quiet', 'HEAD']).strip()
except CalledProcessError:
self.head_name = None
self.orig_head = get_commit_sha1('HEAD')
return self
def __exit__(self, exc_type, exc_val, exc_tb):
if self.head_name:
try:
check_call([
'git', 'symbolic-ref',
'-m', self.message, 'HEAD',
self.head_name,
])
except Exception, e:
raise Failure(
'Could not restore HEAD to %r!: %s\n'
% (self.head_name, e.message,)
)
else:
try:
check_call(['git', 'reset', '--hard', self.orig_head])
except Exception, e:
raise Failure(
'Could not restore HEAD to %r!: %s\n'
% (self.orig_head, e.message,)
)
return False
def reparent(commit, parent_sha1s):
"""Create a new commit object like commit, but with the specified parents.
commit is the SHA1 of an existing commit and parent_sha1s is a
list of SHA1s. Create a new commit exactly like that one, except
that it has the specified parent commits. Return the SHA1 of the
resulting commit object, which is already stored in the object
database but is not yet referenced by anything."""
old_commit = check_output(['git', 'cat-file', 'commit', commit])
separator = old_commit.index('\n\n')
headers = old_commit[:separator + 1].splitlines(True)
rest = old_commit[separator + 1:]
new_commit = StringIO()
for i in range(len(headers)):
line = headers[i]
if line.startswith('tree '):
new_commit.write(line)
for parent_sha1 in parent_sha1s:
new_commit.write('parent %s\n' % (parent_sha1,))
elif line.startswith('parent '):
# Discard old parents:
pass
else:
new_commit.write(line)
new_commit.write(rest)
process = subprocess.Popen(
['git', 'hash-object', '-t', 'commit', '-w', '--stdin'],
stdin=subprocess.PIPE, stdout=subprocess.PIPE,
)
out, err = process.communicate(new_commit.getvalue())
retcode = process.poll()
if retcode:
raise Failure('Could not reparent commit %s' % (commit,))
return out.strip()
class AutomaticMergeFailed(Exception):
def __init__(self, commit1, commit2):
Exception.__init__(
self, 'Automatic merge of %s and %s failed' % (commit1, commit2,)
)
self.commit1, self.commit2 = commit1, commit2
def automerge(commit1, commit2):
"""Attempt an automatic merge of commit1 and commit2.
Return the SHA1 of the resulting commit, or raise
AutomaticMergeFailed on error. This must be called with a clean
worktree."""
call_silently(['git', 'checkout', '-f', commit1])
try:
call_silently(['git', '-c', 'rerere.enabled=false', 'merge', commit2])
except CalledProcessError:
# We don't use "git merge --abort" here because it was only
# added in git version 1.7.4.
call_silently(['git', 'reset', '--merge'])
raise AutomaticMergeFailed(commit1, commit2)
else:
return get_commit_sha1('HEAD')
class MergeRecord(object):
# Bits for the flags field:
# There is a saved successful auto merge:
SAVED_AUTO = 0x01
# An auto merge (which may have been unsuccessful) has been done:
NEW_AUTO = 0x02
# There is a saved successful manual merge:
SAVED_MANUAL = 0x04
# A manual merge (which may have been unsuccessful) has been done:
NEW_MANUAL = 0x08
# A merge that is currently blocking the merge frontier:
BLOCKED = 0x10
# Some useful bit combinations:
SAVED = SAVED_AUTO | SAVED_MANUAL
NEW = NEW_AUTO | NEW_MANUAL
AUTO = SAVED_AUTO | NEW_AUTO
MANUAL = SAVED_MANUAL | NEW_MANUAL
ALLOWED_INITIAL_FLAGS = [
SAVED_AUTO,
SAVED_MANUAL,
NEW_AUTO,
NEW_MANUAL,
]
def __init__(self, sha1=None, flags=0):
# The currently believed correct merge, or None if it is
# unknown or the best attempt was unsuccessful.
self.sha1 = sha1
if self.sha1 is None:
if flags != 0:
raise ValueError('Initial flags (%s) for sha1=None should be 0' % (flags,))
elif flags not in self.ALLOWED_INITIAL_FLAGS:
raise ValueError('Initial flags (%s) is invalid' % (flags,))
# See bits above.
self.flags = flags
def record_merge(self, sha1, source):
"""Record a merge at this position.
source must be SAVED_AUTO, SAVED_MANUAL, NEW_AUTO, or NEW_MANUAL."""
if source == self.SAVED_AUTO:
# SAVED_AUTO is recorded in any case, but only used if it
# is the only info available.
if self.flags & (self.MANUAL | self.NEW) == 0:
self.sha1 = sha1
self.flags |= source
elif source == self.NEW_AUTO:
# NEW_AUTO is silently ignored if any MANUAL value is
# already recorded.
if self.flags & self.MANUAL == 0:
self.sha1 = sha1
self.flags |= source
elif source == self.SAVED_MANUAL:
# SAVED_MANUAL is recorded in any case, but only used if
# no NEW_MANUAL is available.
if self.flags & self.NEW_MANUAL == 0:
self.sha1 = sha1
self.flags |= source
elif source == self.NEW_MANUAL:
# NEW_MANUAL is always used, and also causes NEW_AUTO to
# be forgotten if present.
self.sha1 = sha1
self.flags = (self.flags | source) & ~self.NEW_AUTO
else:
raise ValueError('Undefined source: %s' % (source,))
def record_blocked(self, blocked):
if blocked:
self.flags |= self.BLOCKED
else:
self.flags &= ~self.BLOCKED
def is_known(self):
return self.sha1 is not None
def is_blocked(self):
return self.flags & self.BLOCKED != 0
def is_manual(self):
return self.flags & self.MANUAL != 0
def save(self, name, i1, i2):
"""If this record has changed, save it."""
def set_ref(source):
check_call([
'git', 'update-ref',
'-m', 'imerge %r: Record %s merge' % (name, source,),
'refs/imerge/%s/%s/%d-%d' % (name, source, i1, i2),
self.sha1,
])
def clear_ref(source):
check_call([
'git', 'update-ref',
'-d', 'imerge %r: Remove obsolete %s merge' % (name, source,),
'refs/imerge/%s/%s/%d-%d' % (name, source, i1, i2),
])
if self.flags & self.MANUAL:
if self.flags & self.AUTO:
# Any MANUAL obsoletes any AUTO:
if self.flags & self.SAVED_AUTO:
clear_ref('auto')
self.flags &= ~self.AUTO
if self.flags & self.NEW_MANUAL:
# Convert NEW_MANUAL to SAVED_MANUAL.
if self.sha1:
set_ref('manual')
self.flags |= self.SAVED_MANUAL
elif self.flags & self.SAVED_MANUAL:
# Delete any existing SAVED_MANUAL:
clear_ref('manual')
self.flags &= ~self.SAVED_MANUAL
self.flags &= ~self.NEW_MANUAL
elif self.flags & self.NEW_AUTO:
# Convert NEW_AUTO to SAVED_AUTO.
if self.sha1:
set_ref('auto')
self.flags |= self.SAVED_AUTO
elif self.flags & self.SAVED_AUTO:
# Delete any existing SAVED_AUTO:
clear_ref('auto')
self.flags &= ~self.SAVED_AUTO
self.flags &= ~self.NEW_AUTO
class UnexpectedMergeFailure(Exception):
def __init__(self, msg, i1, i2):
Exception.__init__(self, msg)
self.i1, self.i2 = i1, i2
class BlockCompleteError(Exception):
pass
class FrontierBlockedError(Exception):
def __init__(self, msg, i1, i2):
Exception.__init__(self, msg)
self.i1 = i1
self.i2 = i2
class NotABlockingCommitError(Exception):
pass
class MergeFrontier(object):
"""Represents the merge frontier within a Block.
A MergeFrontier is represented by a list of SubBlocks, each of
which is thought to be completely mergeable. The list is kept in
normalized form:
* Only non-empty blocks are retained
* Blocks are sorted from bottom left to upper right
* No redundant blocks
"""
@staticmethod
def map_known_frontier(block):
"""Return the MergeFrontier describing existing successful merges in block.
The return value only includes the part that is fully outlined
and whose outline consists of rectangles reaching back to
(0,0).
A blocked commit is *not* considered to be within the
frontier, even if a merge is registered for it. Such merges
must be explicitly unblocked."""
# FIXME: This algorithm can take combinatorial time, for
# example if there is a big block of merges that is a dead
# end:
#
# +++++++
# +?+++++
# +?+++++
# +?+++++
# +?*++++
#
# The problem is that the algorithm will explore all of the
# ways of getting to commit *, and the number of paths grows
# like a binomial coefficient. The solution would be to
# remember dead-ends and reject any curves that visit a point
# to the right of a dead-end.
#
# For now we don't intend to allow a situation like this to be
# created, so we ignore the problem.
# A list (i1, i2, down) of points in the path so far. down is
# True iff the attempted step following this one was
# downwards.
path = []
def create_frontier(path):
blocks = []
for ((i1old, i2old, downold), (i1new, i2new, downnew)) in iter_neighbors(path):
if downold == True and downnew == False:
blocks.append(block[:i1new + 1, :i2new + 1])
return MergeFrontier(block, blocks)
# Loop invariants:
#
# * path is a valid path
#
# * (i1, i2) is in block but it not yet added to path
#
# * down is True if a step downwards from (i1, i2) has not yet
# been attempted
(i1, i2) = (block.len1 - 1, 0)
down = True
while True:
if down:
if i2 == block.len2 - 1:
# Hit edge of block; can't move down:
down = False
elif (i1, i2 + 1) in block and not block.is_blocked(i1, i2 + 1):
# Can move down
path.append((i1, i2, True))
i2 += 1
else:
# Can't move down.
down = False
else:
if i1 == 0:
# Success!
path.append((i1, i2, False))
return create_frontier(path)
elif (i1 - 1, i2) in block and not block.is_blocked(i1 - 1, i2):
# Can move left
path.append((i1, i2, False))
down = True
i1 -= 1
else:
# There's no way to go forward; backtrack until we
# find a place where we can still try going left:
while True:
try:
(i1, i2, down) = path.pop()
except IndexError:
# This shouldn't happen because, in the
# worst case, there is a valid path across
# the top edge of the merge diagram.
raise RuntimeError('Block is improperly formed!')
if down:
down = False
break
@staticmethod
def compute_by_bisection(block):
"""Return a MergeFrontier instance for block.
We make the following assumptions (using Python subscript
notation):
0. All of the merges in block[1:,0] and block[0,1:] are
already known. (This is an invariant of the Block class.)
1. If a direct merge can be done between block[i1-1,0] and
block[0,i2-1], then all of the pairwise merges in
block[1:i1, 1:i2] can also be done.
2. If a direct merge fails between block[i1-1,0] and
block[0,i2-1], then all of the pairwise merges in
block[i1-1:,i2-1:] would also fail.
Under these assumptions, the merge frontier is a stepstair
pattern going from the bottom-left to the top-right, and
bisection can be used to find the transition between mergeable
and conflicting in any row or column.
Of course these assumptions are not rigorously true, so the
MergeFrontier returned by this function is only an
approximation of the real merge diagram. We check for and
correct such inconsistencies later."""
# Given that these diagrams typically have few blocks, check
# the end of a range first to see if the whole range can be
# determined, and fall back to bisection otherwise. We
# determine the frontier block by block, starting in the lower
# left.
if block.len1 <= 1 or block.len2 <= 1 or block.is_blocked(1, 1):
return MergeFrontier(block, [])
if not block.is_mergeable(1, 1):
# There are no mergeable blocks in block; therefore,
# block[1,1] must itself be unmergeable. Record that
# fact:
block[1,1].record_blocked(True)
return MergeFrontier(block, [])
blocks = []
# At this point, we know that there is at least one mergeable
# commit in the first column. Find the height of the success
# block in column 1:
i1 = 1
i2 = find_first_false(
lambda i: block.is_mergeable(i1, i),
1, block.len2,
)
# Now we know that (1,i2-1) is mergeable but (1,i2) is not;
# e.g., (i1, i2) is like 'A' (or maybe 'B') in the following
# diagram (where '*' means mergeable, 'x' means not mergeable,
# and '?' means indeterminate) and that the merge under 'A' is
# not mergeable:
#
# i1
#
# 0123456
# 0 *******
# 1 **?????
# i2 2 **?????
# 3 **?????
# 4 *Axxxxx
# 5 *xxxxxx
# B
while True:
if i2 == 1:
break
# At this point in the loop, we know that any blocks to
# the left of 'A' have already been recorded, (i1, i2-1)
# is mergeable but (i1, i2) is not; e.g., we are at a
# place like 'A' in the following diagram:
#
# i1
#
# 0123456
# 0 **|****
# 1 **|*???
# i2 2 **|*???
# 3 **|Axxx
# 4 --+xxxx
# 5 *xxxxxx
#
# This implies that (i1, i2) is the first unmergeable
# commit in a blocker block (though blocker blocks are not
# recorded explicitly). It also implies that a mergeable
# block has its last mergeable commit somewhere in row
# i2-1; find its width.
if block.is_mergeable(block.len1 - 1, i2 - 1):
i1 = block.len1
blocks.append(block[:i1,:i2])
break
else:
i1 = find_first_false(
lambda i: block.is_mergeable(i, i2 - 1),
i1 + 1, block.len1 - 1,
)
blocks.append(block[:i1,:i2])
# At this point in the loop, (i1-1, i2-1) is mergeable but
# (i1, i2-1) is not; e.g., 'A' in the following diagram:
#
# i1
#
# 0123456
# 0 **|*|**
# 1 **|*|??
# i2 2 --+-+xx
# 3 **|xxAx
# 4 --+xxxx
# 5 *xxxxxx
#
# The block ending at (i1-1,i2-1) has just been recorded.
# Now find the height of the conflict rectangle at column
# i1 and fill it in:
if block.is_mergeable(i1, 1):
i2 = find_first_false(
lambda i: block.is_mergeable(i1, i),
2, i2 - 1,
)
else:
break
return MergeFrontier(block, blocks)
def __init__(self, block, blocks=None):
self.block = block
blocks = list(self._iter_non_empty_blocks(blocks or []))
blocks.sort(key=lambda block: block.len1)
self.blocks = list(self._iter_non_redundant_blocks(blocks))
def __iter__(self):
"""Iterate over blocks from bottom left to upper right."""
return iter(self.blocks)
def __nonzero__(self):
"""Return True iff this frontier has no completed parts."""
return bool(self.blocks)
def is_complete(self):
"""Return True iff the frontier covers the whole block."""
return (