Class: Amp::Merges::ThreeWayMerger

Inherits:
Object
  • Object
show all
Defined in:
lib/amp/merges/simple_merge.rb

Overview

SimpleMerge - basic 3-way merging

This class takes 2 texts and a common ancestor text, and tries to produce a text incorporating all the changes from ancestor->local and ancestor->remote. It will produce the annoying >>>>>> ====== <<<<< markers just like mercurial/cvs does.

For the record, for any methods that don’t have comments in the code, I have an excuse: I don’t understand the code.

p.s. threeway. hehe. three way.

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(base_text, a_text, b_text, base = nil, a = nil, b = nil) ⇒ ThreeWayMerger

Initializes the merger object with the 3 necessary texts, as well as subsections to merge (if we don’t want to merge the entire texts).

Parameters:

  • base_text (String) —

    the common ancestor text, from which we are merging changes

  • a_text (String) —

    one descendent text - typically the local copy of the file

  • b_text (String) —

    the other descendent text - typically a copy committed by somebody else.

  • base_subset (String) —

    (base_text.split_newlines) the subsection of the common ancestor we are concerned with (if not merging full texts)

  • a_subset (String) —

    (a_text.split_newlines) the subsection of the first text we are concerned with (if not merging full texts)

  • b_subset (String) —

    (b_text.split_newlines) the subsection of the second text we are concerned with (if not merging full texts)



98
99
100
101
102
103
 
# File 'lib/amp/merges/simple_merge.rb', line 98

def initialize(base_text, a_text, b_text, base=nil, a=nil, b=nil)
  @base_text, @a_text, @b_text = base_text, a_text, b_text
  @base = base || @base_text.split_lines_better
  @a    = a    || @a_text.split_lines_better
  @b    = b    || @b_text.split_lines_better
end

Instance Attribute Details

#conflicts ⇒ Object

Have there been any conflicts in the merge?



24
25
26
 
# File 'lib/amp/merges/simple_merge.rb', line 24

def conflicts
  @conflicts
end

Class Method Details

.three_way_merge(local, base, other, opts = {}) ⇒ Boolean

Performs a 3-way merge on the 3 files provided. Saves the merged file over the local file. This basically handles the file juggling while applying the instance methods to do merging.

Parameters:

  • local (String) —

    path to the original local file

  • base (String) —

    path to a (temporary) base file

  • other (String) —

    path to a (temporary) target file

  • opts (Hash) (defaults to: {}) —

    additional options for merging

Returns:

  • (Boolean) —

    were there conflicts during the merge?



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
 
# File 'lib/amp/merges/simple_merge.rb', line 36

def self.three_way_merge(local, base, other, opts={})
  name_a = local
  name_b = other
  labels = opts[:labels] || []
  
  name_a = labels.shift if labels.any?
  name_b = labels.shift if labels.any?
  raise abort("You can only specify 2 labels") if labels.any?
  
  local_text = read_file local
  base_text  = read_file base
  other_text = read_file other
  local = Pathname.new(local).realpath
  unless opts[:print]
    # special temp name for our new merged file
    newname = File.amp_make_tmpname local
    out     = File.open newname, "w"
    
    # add rename method to this object to do atomicity
    def out.rename(local, newname)
      self.close
      File.unlink(local)
      File.move(newname, local)
    end
  else
    out = STDOUT
  end
  
  reprocess = !opts[:no_minimal]
  merger = ThreeWayMerger.new(base_text, local_text, other_text)
  merger.merge_lines(:name_a => name_a, :name_b => name_b, :reprocess => reprocess) do |line|
    out.write line
  end
  
  out.rename(local, newname) unless opts[:print]
  
  if merger.conflicts
    unless opts[:quiet]
      UI.warn("conflicts during merge.")
    end
    return true # yes conflicts
  end
  
  false # no conflicts
end

Instance Method Details

#assert(val, msg = "Assertion failed") ⇒ Object

Raises:



19
20
21
 
# File 'lib/amp/merges/simple_merge.rb', line 19

def assert(val, msg="Assertion failed")
  raise MergeAssertion.new(msg) unless val
end

#find_sync_regions ⇒ Array<Hash>

Returns a list of sync’d regions, where both descendents match the base. Generates a list of :base_end, :a_start, :a_end, :b_start, :b_end

Returns:

  • (Array<Hash>) —

    A list of sync regions, each stored as a hash, with the keys :base_end, :a_start, :a_end, :b_start, :b_end. There is always a zero-length sync region at the end of any file (because the EOF always matches).



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
 
# File 'lib/amp/merges/simple_merge.rb', line 332

def find_sync_regions
  idx_a = idx_b = 0
  a_matches = Amp::Diffs::MercurialDiff.get_matching_blocks(@base_text, @a_text)
  b_matches = Amp::Diffs::MercurialDiff.get_matching_blocks(@base_text, @b_text)
  
  len_a, len_b = a_matches.size, b_matches.size
  sync_regions = []
  
  while idx_a < len_a && idx_b < len_b
    next_a, next_b = a_matches[idx_a], b_matches[idx_b]
    
    a_base, a_match, a_len = next_a[:start_a], next_a[:start_b], next_a[:length]
    b_base, b_match, b_len = next_b[:start_a], next_b[:start_b], next_b[:length]
    
    intersection = (a_base..(a_base+a_len)) - (b_base..(b_base+b_len))
    if intersection
      # add the sync region
      sync_regions << synced_region_for_intersection(intersection, a_base, b_base, a_match, b_match)
    end
    if (a_base + a_len) < (b_base + b_len)
      idx_a += 1
    else
      idx_b += 1
    end
  end
  # add the EOF-marker
  inter_base = @base.size
  a_base     = @a.size
  b_base     = @b.size
  sync_regions << {:base_start => inter_base, :base_end => inter_base,
                   :a_start    => a_base,   :a_end    => a_base      ,  
                   :b_start    => b_base,   :b_end    => b_base      }
  
  sync_regions
end

#merge_groups ⇒ Object

Yield sequence of line groups. Each one is a tuple:

:unchanged, lines

Lines unchanged from base

:a, lines

Lines taken from a

:same, lines

Lines taken from a (and equal to b)

:b, lines

Lines taken from b

:conflict, base_lines, a_lines, b_lines

Lines from base were changed to either a or b and conflict.



182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
 
# File 'lib/amp/merges/simple_merge.rb', line 182

def merge_groups
  merge_regions do |list|
    case list[0]
    when :unchanged
      yield list[0], @base[list[1]..(list[2]-1)]
    when :a, :same
      yield list[0],    @a[list[1]..(list[2]-1)]
    when :b
      yield list[0],    @b[list[1]..(list[2]-1)]
    when :conflict
      yield list[0], @base[list[1]..(list[2]-1)],
                        @a[list[3]..(list[4]-1)],
                        @b[list[5]..(list[6]-1)]
    else
      raise ArgumentError.new(list[0])
    end
  end
end

#merge_lines(opts = {}) {|line| ... } ⇒ Object

Merges the texts in a CVS-like form. The start_marker, mid_markers, and end_marker arguments are used to delimit conflicts. Yields lines - doesn’t return anything.

Yields:

  • the merged lines

Yield Parameters:

  • line (String) —

    1 line that belongs in the merged file.



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
 
# File 'lib/amp/merges/simple_merge.rb', line 111

def merge_lines(opts = {})
  defaults = {:name_a => nil, :name_b => nil, :name_base => nil,
              :start_marker => "<<<<<<<", :mid_marker => "=======", 
              :end_marker => ">>>>>>>", :base_marker => nil, :reprocess => false}
  opts = defaults.merge(opts)
  
  @conflicts = false # no conflicts yet!
  # Figure out what our newline character is (silly windows)
  newline = "\n"
  if @a.size > 0
    newline = "\r\n" if @a.first.end_with?("\r\n")
    newline = "\r"   if @a.first.end_with?("\r")
  end
  
  if opts[:base_marker] && opts[:reprocess]
    raise ArgumentError.new("Can't reprocess and show base markers!")
  end
  
  # Add revision names to the markers
  opts[:start_marker] += " #{opts[:name_a]}"    if opts[:name_a]
  opts[:end_marker]   += " #{opts[:name_b]}"    if opts[:name_b]
  opts[:base_marker]  += " #{opts[:name_base]}" if opts[:name_base] && opts[:base_marker]
  
  merge_method = opts[:reprocess] ? :reprocessed_merge_regions : :merge_regions
  self.send(merge_method) do |*t|
    status = t[0]
    case status
    when :unchanged
      t[1].upto(t[2]-1) {|i| yield @base[i] } # nothing changed, use base
    when :a, :same
      t[1].upto(t[2]-1) {|i| yield @a[i]    } # local (A) insertion
    when :b
      t[1].upto(t[2]-1) {|i| yield @b[i]    } # remote (B) insertion
    when :conflict
      @conflicts = true # :-( we have conflicts
      
      yield opts[:start_marker] + newline # do the <<<<<<
      t[3].upto(t[4]-1) {|i| yield @a[i]} # and the local copy
      
      if opts[:base_marker]
        yield base_marker + newline       # do the base
        t[1].upto(t[2]-1) {|i| yield @base[i]} # and the base lines
      end
      
      yield opts[:mid_marker] + newline   # do the =====
      t[5].upto(t[6]-1) {|i| yield @b[i]} # and the remote copy
      yield opts[:end_marker] + newline   # and then >>>>>>
    else
      raise ArgumentError.new("invalid region: #{status.inspect}")
    end
  end
  
end

#merge_regions { ... } ⇒ Object

Yield sequences of matching and conflicting regions.

This returns tuples, where the first value says what kind we have:

‘unchanged’, start, end

Take a region of base[start:end]

‘same’, astart, aend

b and a are different from base but give the same result

‘a’, start, end

Non-clashing insertion from a[start:end]

Method is as follows:

The two sequences align only on regions which match the base and both descendents. These are found by doing a two-way diff of each one against the base, and then finding the intersections between those regions. These “sync regions” are by definition unchanged in both and easily dealt with.

The regions in between can be in any of three cases: conflicted, or changed on only one side.

Yields:

  • Arrays of regions that require merging



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
 
# File 'lib/amp/merges/simple_merge.rb', line 228

def merge_regions
  ##     NOTE: we use "z" as an abbreviation for "base" or the "ancestor", because
  #      we can't very well abbreviate "ancestor" as "a" or "base" as "b".
  idx_z = idx_a = idx_b = 0
  
  find_sync_regions.each do |match|
    z_match, z_end = match[:base_start], match[:base_end]
    a_match, a_end = match[:a_start   ], match[:a_end   ]
    b_match, b_end = match[:b_start   ], match[:b_end   ]
    
    match_len = z_end - z_match
    assert match_len >= 0
    assert match_len == (a_end - a_match), "expected #{match_len}, got #{(a_end - a_match)} (#{a_end} - #{a_match})"
    assert match_len == (b_end - b_match)
    
    len_a = a_match - idx_a
    len_b = b_match - idx_b
    len_base = z_match - idx_z
    assert len_a >= 0
    assert len_b >= 0
    assert len_base >= 0
    
    if len_a > 0 || len_b > 0
      equal_a = compare_range(@a, idx_a, a_match, @base, idx_z, z_match)
      equal_b = compare_range(@b, idx_b, b_match, @base, idx_z, z_match)
      same    = compare_range(@a, idx_a, a_match, @b,    idx_b, b_match)
      
      if same
        yield :same, idx_a, a_match
      elsif equal_a && !equal_b
        yield :b, idx_b, b_match
      elsif equal_b && !equal_a
        yield :a, idx_a, a_match
      elsif !equal_a && !equal_b
        yield :conflict, idx_z, z_match, idx_a, a_match, idx_b, b_match
      else
        raise AssertionError.new("can't handle a=b=base but unmatched!")
      end
      
      idx_a = a_match
      idx_b = b_match
    end
    idx_z = z_match
    
    if match_len > 0
      assert idx_a == a_match
      assert idx_b == b_match
      assert idx_z == z_match
      
      yield :unchanged, z_match, z_end
      
      idx_a = a_end
      idx_b = b_end
      idx_z = z_end
    end
  end
end

#reprocessed_merge_regions ⇒ Object

Take the merge regions yielded by merge_regions, and remove lines where both A and B (local & remote) have made the same changes.



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
 
# File 'lib/amp/merges/simple_merge.rb', line 289

def reprocessed_merge_regions
  merge_regions do |*region|
    if region[0] != :conflict
      yield *region
      next
    end
    type, idx_z, z_match, idx_a, a_match, idx_b, b_match = region
    a_region = @a[idx_a..(a_match-1)]
    b_region = @b[idx_b..(b_match-1)]
    matches = Amp::Diffs::MercurialDiff.get_matching_blocks(a_region.join, b_region.join)
    
    next_a = idx_a
    next_b = idx_b
    
    matches[0..-2].each do |block|
      region_ia, region_ib, region_len = block[:start_a], block[:start_b], block[:length]
      region_ia += idx_a
      region_ib += idx_b
      
      reg = mismatch_region(next_a, region_ia, next_b, region_ib)
      
      yield *reg if reg
      yield :same, region_ia, region_len + region_ia
      
      next_a = region_ia + region_len
      next_b = region_ib + region_len
      
    end
    reg = mismatch_region(next_a, a_match, next_b, b_match)
    yield *reg if reg
  end
end

#synced_region_for_intersection(intersection, a_base, b_base, a_match, b_match) ⇒ Object 



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
 
# File 'lib/amp/merges/simple_merge.rb', line 368

def synced_region_for_intersection(intersection, a_base, b_base, a_match, b_match)
  inter_base = intersection.begin
  inter_end  = intersection.end
  inter_len  = inter_end - inter_base
  
  # found a match of base[inter_base..inter_end] - this may be less than the region
  # that matches in either one. Let's do some assertions
  #assert inter_len <= a_len
  #assert inter_len <= b_len
  assert a_base    <= inter_base
  assert b_base    <= inter_base
  
  # shift section downward or upward
  a_sub = a_match + (inter_base - a_base)
  b_sub = b_match + (inter_base - b_base)
  # end points = base_len + starts
  a_end = a_sub + inter_len
  b_end = b_sub + inter_len
  
  # make sure the texts are equal of course....
  assert @base[inter_base..(inter_end-1)] == @a[a_sub..(a_end-1)]
  assert @base[inter_base..(inter_end-1)] == @b[b_sub..(b_end-1)]
  
  # return the sync region
  {:base_start => inter_base, :base_end => inter_end,
   :a_start    => a_sub,   :a_end    => a_end       ,  
   :b_start    => b_sub,   :b_end    => b_end       }
end