Class: DiffMatchPatch

Inherits:
Object
  • Object
show all
Defined in:
lib/diff_match_patch.rb

Overview

Class containing the diff, match and patch methods. Also contains the behaviour settings.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ DiffMatchPatch

Returns a new instance of DiffMatchPatch.



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
 
# File 'lib/diff_match_patch.rb', line 14

def initialize
  # Inits a diff_match_patch object with default settings.
  # Redefine these in your program to override the defaults.

  # Number of seconds to map a diff before giving up (0 for infinity).
  @diff_timeout = 1
  # Cost of an empty edit operation in terms of edit characters.
  @diff_editCost = 4
  # At what point is no match declared (0.0 = perfection, 1.0 = very loose).
  @match_threshold = 0.5
  # How far to search for a match (0 = exact location, 1000+ = broad match).
  # A match this many characters away from the expected location will add
  # 1.0 to the score (0.0 is a perfect match).
  @match_distance = 1000
  # When deleting a large block of text (over ~64 characters), how close does
  # the contents have to match the expected contents. (0.0 = perfection,
  # 1.0 = very loose).  Note that Match_Threshold controls how closely the
  # end points of a delete need to match.
  @patch_deleteThreshold = 0.5
  # Chunk size for context length.
  @patch_margin = 4

  # The number of bits in an int.
  # Python has no maximum, thus to disable patch splitting set to 0.
  # However to avoid long patches in certain pathological cases, use 32.
  # Multiple short patches (using native ints) are much faster than long ones.
  @match_maxBits = 32
end

Instance Attribute Details

#diff_editCost ⇒ Object

Returns the value of attribute diff_editCost.



7
8
9
 
# File 'lib/diff_match_patch.rb', line 7

def diff_editCost
  @diff_editCost
end

#diff_timeout ⇒ Object

Returns the value of attribute diff_timeout.



6
7
8
 
# File 'lib/diff_match_patch.rb', line 6

def diff_timeout
  @diff_timeout
end

#match_distance ⇒ Object

Returns the value of attribute match_distance.



9
10
11
 
# File 'lib/diff_match_patch.rb', line 9

def match_distance
  @match_distance
end

#match_maxBits ⇒ Object (readonly)

Returns the value of attribute match_maxBits.



12
13
14
 
# File 'lib/diff_match_patch.rb', line 12

def match_maxBits
  @match_maxBits
end

#match_threshold ⇒ Object

Returns the value of attribute match_threshold.



8
9
10
 
# File 'lib/diff_match_patch.rb', line 8

def match_threshold
  @match_threshold
end

#patch_deleteThreshold ⇒ Object

Returns the value of attribute patch_deleteThreshold.



10
11
12
 
# File 'lib/diff_match_patch.rb', line 10

def patch_deleteThreshold
  @patch_deleteThreshold
end

#patch_margin ⇒ Object

Returns the value of attribute patch_margin.



11
12
13
 
# File 'lib/diff_match_patch.rb', line 11

def patch_margin
  @patch_margin
end

Instance Method Details

#diff_bisect(text1, text2, deadline) ⇒ Object

Find the ‘middle snake’ of a diff, split the problem in two and return the recursively constructed diff. See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.



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
 
# File 'lib/diff_match_patch.rb', line 201

def diff_bisect(text1, text2, deadline)
  # Cache the text lengths to prevent multiple calls.
  text1_length = text1.length
  text2_length = text2.length
  max_d = (text1_length + text2_length + 1) / 2
  v_offset = max_d
  v_length = 2 * max_d
  v1 = Array.new(v_length, -1)
  v2 = Array.new(v_length, -1)
  v1[v_offset + 1] = 0
  v2[v_offset + 1] = 0
  delta = text1_length - text2_length

  # If the total number of characters is odd, then the front path will 
  # collide with the reverse path.
  front = (delta % 2 != 0)
  # Offsets for start and end of k loop.
  # Prevents mapping of space beyond the grid.
  k1start = 0
  k1end = 0
  k2start = 0
  k2end = 0
  max_d.times do |d|
    # Bail out if deadline is reached.
    break if deadline && Time.now >= deadline

    # Walk the front path one step.
    (-d + k1start).step(d - k1end, 2) do |k1|
      k1_offset = v_offset + k1
      if k1 == -d || k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1]
        x1 = v1[k1_offset + 1]
      else
        x1 = v1[k1_offset - 1] + 1
      end

      y1 = x1 - k1
      while x1 < text1_length && y1 < text2_length && text1[x1] == text2[y1]
        x1 += 1
        y1 += 1
      end

      v1[k1_offset] = x1
      if x1 > text1_length
        # Ran off the right of the graph.
        k1end += 2
      elsif y1 > text2_length
        # Ran off the bottom of the graph.
        k1start += 2
      elsif front
        k2_offset = v_offset + delta - k1
        if k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1
          # Mirror x2 onto top-left coordinate system.
          x2 = text1_length - v2[k2_offset]
          if x1 >= x2
            # Overlap detected.
            return diff_bisectSplit(text1, text2, x1, y1, deadline)
          end
        end
      end
    end

    # Walk the reverse path one step.
    (-d + k2start).step(d - k2end, 2) do |k2|
      k2_offset = v_offset + k2
      if k2 == -d || k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1]
        x2 = v2[k2_offset + 1]
      else
        x2 = v2[k2_offset - 1] + 1
      end
    
      y2 = x2 - k2
      while x2 < text1_length && y2 < text2_length && text1[-x2-1] == text2[-y2-1]
        x2 += 1
        y2 += 1
      end

      v2[k2_offset] = x2
      if x2 > text1_length
        # Ran off the left of the graph.
        k2end += 2
      elsif y2 > text2_length
        # Ran off the top of the graph.
        k2start += 2
      elsif !front
        k1_offset = v_offset + delta - k2
        if k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1
          x1 = v1[k1_offset]
          y1 = v_offset + x1 - k1_offset
          # Mirror x2 onto top-left coordinate system.
          x2 = text1_length - x2
          if x1 >= x2
            # Overlap detected.
            return diff_bisectSplit(text1, text2, x1, y1, deadline)
          end
        end
      end
    end
  end

  # Diff took too long and hit the deadline or
  # number of diffs equals number of characters, no commonality at all.
  [[:delete, text1], [:insert, text2]]
end

#diff_bisectSplit(text1, text2, x, y, deadline) ⇒ Object

Given the location of the ‘middle snake’, split the diff in two parts and recurse.



307
308
309
310
311
312
313
314
315
316
317
318
 
# File 'lib/diff_match_patch.rb', line 307

def diff_bisectSplit(text1, text2, x, y, deadline)
  text1a = text1[0...x]
  text2a = text2[0...y]
  text1b = text1[x..-1]
  text2b = text2[y..-1]

  # Compute both diffs serially.
  diffs = diff_main(text1a, text2a, false, deadline)
  diffsb = diff_main(text1b, text2b, false, deadline)

  diffs + diffsb
end

#diff_charsToLines(diffs, line_array) ⇒ Object

Rehydrate the text in a diff from a string of line hashes to real lines of text.



344
345
346
347
348
 
# File 'lib/diff_match_patch.rb', line 344

def diff_charsToLines(diffs, line_array)
  diffs.each do |diff|
    diff[1] = diff[1].chars.map{ |c| line_array[c.ord] }.join
  end
end

#diff_cleanupEfficiency(diffs) ⇒ Object

Reduce the number of edits by eliminating operationally trivial equalities.



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
 
# File 'lib/diff_match_patch.rb', line 711

def diff_cleanupEfficiency(diffs)
  changes = false
  equalities = []  # Stack of indices where equalities are found.
  last_equality = ''  # Always equal to equalities.last[1]
  pointer = 0  # Index of current position.    
  pre_ins = false # Is there an insertion operation before the last equality.      
  pre_del = false # Is there a deletion operation before the last equality.      
  post_ins = false # Is there an insertion operation after the last equality.      
  post_del = false # Is there a deletion operation after the last equality.

  while pointer < diffs.length
    if diffs[pointer][0] == :equal # Equality found.
      if diffs[pointer][1].length < diff_editCost && (post_ins || post_del)
        # Candidate found.
        equalities.push(pointer)
        pre_ins = post_ins
        pre_del = post_del
        last_equality = diffs[pointer][1]
      else
        # Not a candidate, and can never become one.
        equalities.clear
        last_equality = ''
      end
      post_ins = false
      post_del = false
    else # An insertion or deletion.
      if diffs[pointer][0] == :delete
        post_del = true
      else
        post_ins = true
      end

      # Five types to be split:
      # <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>
      # <ins>A</ins>X<ins>C</ins><del>D</del>
      # <ins>A</ins><del>B</del>X<ins>C</ins>
      # <ins>A</del>X<ins>C</ins><del>D</del>
      # <ins>A</ins><del>B</del>X<del>C</del>

      if !last_equality.empty? && 
         ((pre_ins && pre_del && post_ins && post_del) ||
         ((last_equality.length < diff_editCost / 2) &&
         [pre_ins, pre_del, post_ins, post_del].count(true) == 3))
        # Duplicate record.
        diffs[equalities.last, 0] = [[:delete, last_equality]]
        # Change second copy to insert.
        diffs[equalities.last + 1][0] = :insert
        equalities.pop # Throw away the equality we just deleted
        last_equality = ''
        if pre_ins && pre_del
          # No changes made which could affect previous entry, keep going.
          post_ins = true
          post_del = true
          equalities.clear
        else
          if !equalities.empty?
            equalities.pop  # Throw away the previous equality.
            pointer = equalities.last || -1
          end
          post_ins = false
          post_del = false
        end
        changes = true
      end      
    end
    pointer += 1
  end

  if changes
      diff_cleanupMerge(diffs)
  end
end

#diff_cleanupMerge(diffs) ⇒ Object

Reorder and merge like edit sections. Merge equalities. Any edit section can move as long as it doesn’t cross an equality.



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
 
# File 'lib/diff_match_patch.rb', line 786

def diff_cleanupMerge(diffs)
  diffs.push([:equal, '']) # Add a dummy entry at the end.
  pointer = 0
  count_delete = 0
  count_insert = 0
  text_delete = ''
  text_insert = ''

  while pointer < diffs.length
    case diffs[pointer][0]
      when :insert
        count_insert += 1
        text_insert += diffs[pointer][1]
        pointer += 1
      when :delete
        count_delete += 1
        text_delete += diffs[pointer][1]
        pointer += 1
      when :equal
        # Upon reaching an equality, check for prior redundancies.
        if count_delete + count_insert > 1
          if count_delete != 0 && count_insert != 0
            # Factor out any common prefixies.
            common_length = diff_commonPrefix(text_insert, text_delete)
            if common_length != 0
              if (pointer - count_delete - count_insert) > 0 &&
                 diffs[pointer - count_delete - count_insert - 1][0] == :equal
                diffs[pointer - count_delete - count_insert - 1][1] +=
                  text_insert[0...common_length]
              else
                diffs.unshift([:equal, text_insert[0...common_length]])
                pointer += 1
              end
              text_insert = text_insert[common_length..-1]
              text_delete = text_delete[common_length..-1]
            end
            # Factor out any common suffixies.
            common_length = diff_commonSuffix(text_insert, text_delete)
            if common_length != 0
              diffs[pointer][1] = text_insert[-common_length..-1] + diffs[pointer][1]
              text_insert = text_insert[0...-common_length]
              text_delete = text_delete[0...-common_length]
            end
          end

          # Delete the offending records and add the merged ones.
          if count_delete.zero?
            diffs[pointer - count_delete - count_insert, count_delete + count_insert] = 
              [[:insert, text_insert]]
          elsif count_insert.zero?
            diffs[pointer - count_delete - count_insert, count_delete + count_insert] = 
              [[:delete, text_delete]]
          else
            diffs[pointer - count_delete - count_insert, count_delete + count_insert] = 
              [[:delete, text_delete], [:insert, text_insert]]
          end
          pointer = pointer - count_delete - count_insert +
            (count_delete.zero? ? 0 : 1) + (count_insert.zero? ? 0 : 1) + 1
        elsif pointer != 0 && diffs[pointer - 1][0] == :equal
          # Merge this equality with the previous one.
          diffs[pointer - 1][1] += diffs[pointer][1]
          diffs[pointer, 1] = []
        else
          pointer += 1
        end
        count_insert = 0
        count_delete = 0
        text_delete = ''
        text_insert = ''
    end
  end

  if diffs.last[1].empty?
    diffs.pop # Remove the dummy entry at the end.
  end

  # Second pass: look for single edits surrounded on both sides by equalities
  # which can be shifted sideways to eliminate an equality.
  # e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
  changes = false
  pointer = 1

  # Intentionally ignore the first and last element (don't need checking).
  while pointer < diffs.length - 1
    if diffs[pointer - 1][0] == :equal && diffs[pointer + 1][0] == :equal
      # This is a single edit surrounded by equalities.
      if diffs[pointer][1][-diffs[pointer - 1][1].length..-1] == diffs[pointer - 1][1]
        # Shift the edit over the previous equality.
        diffs[pointer][1] = diffs[pointer - 1][1] + diffs[pointer][1][0...-diffs[pointer - 1][1].length]
        diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1]
        diffs[pointer - 1, 1] = []
        changes = true
      elsif diffs[pointer][1][0...diffs[pointer + 1][1].length] == diffs[pointer + 1][1]
        # Shift the edit over the next equality.
        diffs[pointer - 1][1] += diffs[pointer + 1][1]
        diffs[pointer][1] = diffs[pointer][1][diffs[pointer + 1][1].length..-1] + 
          diffs[pointer + 1][1]
        diffs[pointer + 1, 1] = []
        changes = true
      end
    end
    pointer += 1
  end

  # If shifts were made, the diff needs reordering and another shift sweep.
  if changes
    diff_cleanupMerge(diffs)
  end
end

#diff_cleanupSemantic(diffs) ⇒ Object

Reduce the number of edits by eliminating semantically trivial equalities.



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
 
# File 'lib/diff_match_patch.rb', line 499

def diff_cleanupSemantic(diffs)
  changes = false
  equalities = []  # Stack of indices where equalities are found.
  last_equality = nil # Always equal to equalities.last[1]
  pointer = 0 # Index of current position.
  # Number of characters that changed prior to the equality.
  length_insertions1 = 0
  length_deletions1 = 0
  # Number of characters that changed after the equality.
  length_insertions2 = 0
  length_deletions2 = 0

  while pointer < diffs.length
    if diffs[pointer][0] == :equal # Equality found.
      equalities.push(pointer)
      length_insertions1 = length_insertions2
      length_deletions1 = length_deletions2
      length_insertions2 = 0
      length_deletions2 = 0
      last_equality = diffs[pointer][1]
    else  # An insertion or deletion.
      if diffs[pointer][0] == :insert
        length_insertions2 += diffs[pointer][1].length
      else
        length_deletions2 += diffs[pointer][1].length
      end

      if last_equality &&
         last_equality.length <= [length_insertions1, length_deletions1].max &&
         last_equality.length <= [length_insertions2, length_deletions2].max
        # Duplicate record.
        diffs[equalities.last, 0] = [[:delete, last_equality]]

        # Change second copy to insert.
        diffs[equalities.last + 1][0] = :insert

        # Throw away the equality we just deleted.
        equalities.pop
        # Throw away the previous equality (it needs to be reevaluated).
        equalities.pop
        pointer = equalities.last || -1

        # Reset the counters.
        length_insertions1 = 0
        length_deletions1 = 0
        length_insertions2 = 0
        length_deletions2 = 0
        last_equality = nil

        changes = true
      end
    end
    pointer += 1
  end

  # Normalize the diff.
  if changes
    diff_cleanupMerge(diffs)
  end
  diff_cleanupSemanticLossless(diffs)

  # Find any overlaps between deletions and insertions.
  # e.g: <del>abcxxx</del><ins>xxxdef</ins>
  #   -> <del>abc</del>xxx<ins>def</ins>
  # e.g: <del>xxxabc</del><ins>defxxx</ins>
  #   -> <ins>def</ins>xxx<del>abc</del>
  # Only extract an overlap if it is as big as the edit ahead or behind it.
  pointer = 1
  while pointer < diffs.length
    if diffs[pointer - 1][0] == :delete && diffs[pointer][0] == :insert
      deletion = diffs[pointer - 1][1]
      insertion = diffs[pointer][1]
      overlap_length1 = diff_commonOverlap(deletion, insertion)
      overlap_length2 = diff_commonOverlap(insertion, deletion)
      if overlap_length1 >= overlap_length2
        if overlap_length1 >= deletion.length / 2.0 ||
           overlap_length1 >= insertion.length / 2.0
          # Overlap found.  Insert an equality and trim the surrounding edits.
          diffs[pointer, 0] = [[:equal, insertion[0...overlap_length1]]]
          diffs[pointer -1][0] = :delete
          diffs[pointer - 1][1] = deletion[0...-overlap_length1]
          diffs[pointer + 1][0] = :insert
          diffs[pointer + 1][1] = insertion[overlap_length1..-1]
          pointer += 1
        end
      else
        if overlap_length2 >= deletion.length / 2.0 ||
           overlap_length2 >= insertion.length / 2.0
          diffs[pointer, 0] = [[:equal, deletion[0...overlap_length2]]]
          diffs[pointer - 1][0] = :insert
          diffs[pointer - 1][1] = insertion[0...-overlap_length2]
          diffs[pointer + 1][0] = :delete
          diffs[pointer + 1][1] = deletion[overlap_length2..-1]
          pointer += 1
        end
      end        
      pointer += 1
    end
    pointer += 1
  end
end

#diff_cleanupSemanticLossless(diffs) ⇒ Object

Look for single edits surrounded on both sides by equalities which can be shifted sideways to align the edit to a word boundary. e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.



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
 
# File 'lib/diff_match_patch.rb', line 646

def diff_cleanupSemanticLossless(diffs)
  pointer = 1
  # Intentionally ignore the first and last element (don't need checking).
  while pointer < diffs.length - 1
    if diffs[pointer - 1][0] == :equal && diffs[pointer + 1][0] == :equal
      # This is a single edit surrounded by equalities.
      equality1 = diffs[pointer - 1][1]
      edit = diffs[pointer][1]
      equality2 = diffs[pointer + 1][1]

      # First, shift the edit as far left as possible.
      common_offset = diff_commonSuffix(equality1, edit)
      if common_offset != 0
        common_string = edit[-common_offset..-1]
        equality1 = equality1[0...-common_offset]
        edit = common_string + edit[0...-common_offset]
        equality2 = common_string + equality2
      end

      # Second, step character by character right, looking for the best fit.
      best_equality1 = equality1
      best_edit = edit
      best_equality2 = equality2
      best_score = diff_cleanupSemanticScore(equality1, edit) +
        diff_cleanupSemanticScore(edit, equality2)
      while edit[0] == equality2[0]
        equality1 += edit[0]
        edit = edit[1..-1] + equality2[0]
        equality2 = equality2[1..-1]
        score = diff_cleanupSemanticScore(equality1, edit) +
          diff_cleanupSemanticScore(edit, equality2)
        # The >= encourages trailing rather than leading whitespace on edits.
        if score >= best_score
          best_score = score
          best_equality1 = equality1
          best_edit = edit
          best_equality2 = equality2
        end
      end

      if diffs[pointer - 1][1] != best_equality1
        # We have an improvement, save it back to the diff.
        if best_equality1.empty?
          diffs[pointer - 1, 1] = []
          pointer -= 1            
        else
          diffs[pointer - 1][1] = best_equality1
        end

        diffs[pointer][1] = best_edit

        if best_equality2.empty?
          diffs[pointer + 1, 1] = []
          pointer -= 1
        else
          diffs[pointer + 1][1] = best_equality2
        end
      end
    end

    pointer += 1
  end
end

#diff_cleanupSemanticScore(one, two) ⇒ Object

Given two strings, compute a score representing whether the internal boundary falls on logical boundaries. Scores range from 5 (best) to 0 (worst).



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
 
# File 'lib/diff_match_patch.rb', line 604

def diff_cleanupSemanticScore(one, two)
  if one.empty? || two.empty?
    # Edges are the best.
    return 5
  end

  # Define some regex patterns for matching boundaries.
  nonWordCharacter = /[^a-zA-Z0-9]/
  whitespace = /\s/
  linebreak = /[\r\n]/
  lineEnd = /\n\r?\n$/
  lineStart = /^\r?\n\r?\n/

  # Each port of this function behaves slightly differently due to
  # subtle differences in each language's definition of things like
  # 'whitespace'.  Since this function's purpose is largely cosmetic,
  # the choice has been made to use each language's native features
  # rather than force total conformity.
  score = 0
  # One point for non-alphanumeric.
  if one[-1] =~ nonWordCharacter || two[0] =~ nonWordCharacter
    score += 1
    # Two points for whitespace.
    if one[-1] =~ whitespace || two[0] =~ whitespace
      score += 1
      # Three points for line breaks.
      if one[-1] =~ linebreak || two[0] =~ linebreak
        score += 1
        # Four points for blank lines.
        if one =~ lineEnd || two =~ lineStart
          score += 1
        end
      end
    end
  end

  score
end

#diff_commonOverlap(text1, text2) ⇒ Object

Determine if the suffix of one string is the prefix of another.



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
 
# File 'lib/diff_match_patch.rb', line 401

def diff_commonOverlap(text1, text2)
  # Cache the text lengths to prevent multiple calls.
  text1_length = text1.length
  text2_length = text2.length

  # Eliminate the null case.
  return 0  if text1_length.zero? || text2_length.zero?

  # Truncate the longer string.
  if text1_length > text2_length
    text1 = text1[-text2_length..-1]
  else
    text2 = text2[0...text1_length]
  end
  text_length = [text1_length, text2_length].min

  # Quick check for the whole case.
  return text_length if text1 == text2

  # Start by looking for a single character match
  # and increase length until no match is found.
  # Performance analysis: http://neil.fraser.name/news/2010/11/04/
  best = 0
  length = 1
  loop do
    pattern = text1[(text_length - length)..-1]
    found = text2.index(pattern)

    return best if found.nil?

    length += found
    if found == 0 || text1[(text_length - length)..-1] == text2[0..length]
      best = length
      length += 1
    end
  end
end

#diff_commonPrefix(text1, text2) ⇒ Object

Determine the common prefix of two strings.



351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
 
# File 'lib/diff_match_patch.rb', line 351

def diff_commonPrefix(text1, text2)
  # Quick check for common null cases.
  return 0 if text1.empty? || text2.empty? || text1[0] != text2[0]

  # Binary search.
  # Performance analysis: http://neil.fraser.name/news/2007/10/09/
  pointer_min = 0
  pointer_max = [text1.length, text2.length].min
  pointer_mid = pointer_max
  pointer_start = 0

  while pointer_min < pointer_mid
    if text1[pointer_start...pointer_mid] == text2[pointer_start...pointer_mid]
      pointer_min = pointer_mid
      pointer_start = pointer_min
    else
      pointer_max = pointer_mid
    end
    pointer_mid = (pointer_max - pointer_min) / 2 + pointer_min
  end

  pointer_mid
end

#diff_commonSuffix(text1, text2) ⇒ Object

Determine the common suffix of two strings.



376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
 
# File 'lib/diff_match_patch.rb', line 376

def diff_commonSuffix(text1, text2)
  # Quick check for common null cases.
  return 0 if text1.empty? || text2.empty? || text1[-1] != text2[-1]

  # Binary search.
  # Performance analysis: http://neil.fraser.name/news/2007/10/09/
  pointer_min = 0
  pointer_max = [text1.length, text2.length].min
  pointer_mid = pointer_max
  pointer_end = 0

  while pointer_min < pointer_mid
    if text1[-pointer_mid..(-pointer_end-1)] == text2[-pointer_mid..(-pointer_end-1)]
      pointer_min = pointer_mid
      pointer_end = pointer_min
    else
      pointer_max = pointer_mid
    end
    pointer_mid = (pointer_max - pointer_min) / 2 + pointer_min
  end

  pointer_mid
end

#diff_compute(text1, text2, checklines, deadline) ⇒ Object

Find the differences between two texts. Assumes that the texts do not have any common prefix or suffix.



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
 
# File 'lib/diff_match_patch.rb', line 94

def diff_compute(text1, text2, checklines, deadline)
  # Just add some text (speedup).
  return [[:insert, text2]] if text1.empty?

  # Just delete some text (speedup).
  return [[:delete, text1]] if text2.empty?

  shorttext, longtext = [text1, text2].sort_by(&:length)
  if i = longtext.index(shorttext)
    # Shorter text is inside the longer text (speedup).
    diffs = [[:insert, longtext[0...i]], [:equal, shorttext],
             [:insert, longtext[(i + shorttext.length)..-1]]]

    # Swap insertions for deletions if diff is reversed.
    if text1.length > text2.length
        diffs[0][0] = :delete
        diffs[2][0] = :delete
    end

    return diffs
  end

  if shorttext.length == 1
    # Single character string.
    # After the previous speedup, the character can't be an equality.
    return [[:delete, text1], [:insert, text2]]
  end

  # Garbage collect.
  longtext = nil 
  shorttext = nil

  # Check to see if the problem can be split in two.
  if hm = diff_halfMatch(text1, text2)
    # A half-match was found, sort out the return data.
    text1_a, text1_b, text2_a, text2_b, mid_common = hm
    # Send both pairs off for separate processing.
    diffs_a = diff_main(text1_a, text2_a, checklines, deadline)
    diffs_b = diff_main(text1_b, text2_b, checklines, deadline)
    # Merge the results.
    return diffs_a + [[:equal, mid_common]] + diffs_b
  end

  if checklines && text1.length > 100 && text2.length > 100
    return diff_lineMode(text1, text2, deadline)
  end

  return diff_bisect(text1, text2, deadline)
end

#diff_fromDelta(text1, delta) ⇒ Object

Given the original text1, and an encoded string which describes the operations required to transform text1 into text2, compute the full diff.



1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
 
# File 'lib/diff_match_patch.rb', line 1008

def diff_fromDelta(text1, delta)
  # Deltas should be composed of a subset of ascii chars, Unicode not required.
  delta.encode('ascii')
  diffs = []
  pointer = 0 # Cursor in text1
  delta.split("\t").each do |token|
    # Each token begins with a one character parameter which specifies the
    # operation of this token (delete, insert, equality).
    param = token[1..-1]
    case token[0]
      when '+'
        diffs.push([:insert, URI.decode(param.force_encoding(Encoding::UTF_8))])
      when '-', '='
        begin
          n = Integer(param)
          raise if n < 0
          text = text1[pointer...(pointer + n)]
          pointer += n
          if token[0] == '='
            diffs.push([:equal, text])
          else
            diffs.push([:delete, text])
          end
        rescue ArgumentError => e
          raise ArgumentError.new(
            "Invalid number in diff_fromDelta: #{param.inspect}")
        end
      else
        raise ArgumentError.new(
          "Invalid diff operation in diff_fromDelta: #{token.inspect}")        
    end
  end
  
  if pointer != text1.length
    raise ArgumentError.new("Delta length (#{pointer}) does not equal " +
      "source text length #{text1.length}")
  end
  diffs
end

#diff_halfMatch(text1, text2) ⇒ Object

Do the two texts share a substring which is at least half the length of the longer text? This speedup can produce non-minimal diffs.



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
 
# File 'lib/diff_match_patch.rb', line 465

def diff_halfMatch(text1, text2)
  # Don't risk returning a non-optimal diff if we have unlimited time
  return nil if diff_timeout <= 0

  shorttext, longtext = [text1, text2].sort_by(&:length)
  if longtext.length < 4 || shorttext.length * 2 < longtext.length
    return nil # Pointless.
  end

  # First check if the second quarter is the seed for a half-match.
  hm1 = diff_halfMatchI(longtext, shorttext, (longtext.length + 3) / 4)
  # Check again based on the third quarter.
  hm2 = diff_halfMatchI(longtext, shorttext, (longtext.length + 1) / 2)

  if hm1.nil? && hm2.nil?
    return nil
  elsif hm2.nil? || hm1.nil?
    hm = hm2.nil? ? hm1 : hm2
  else
    # Both matched.  Select the longest.
    hm = hm1[4].length > hm2[4].length ? hm1 : hm2
  end

  # A half-match was found, sort out the return data.
  if text1.length > text2.length
    text1_a, text1_b, text2_a, text2_b, mid_common = hm
  else
    text2_a, text2_b, text1_a, text1_b, mid_common = hm
  end

  [text1_a, text1_b, text2_a, text2_b, mid_common]
end

#diff_halfMatchI(longtext, shorttext, i) ⇒ Object

Does a substring of shorttext exist within longtext such that the substring is at least half the length of longtext?



441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
 
# File 'lib/diff_match_patch.rb', line 441

def diff_halfMatchI(longtext, shorttext, i)
  seed = longtext[i, longtext.length / 4]
  j = -1
  best_common = ''
  while j = shorttext.index(seed, j + 1)
    prefix_length = diff_commonPrefix(longtext[i..-1], shorttext[j..-1])
    suffix_length = diff_commonSuffix(longtext[0...i], shorttext[0...j])
    if best_common.length < suffix_length + prefix_length
      best_common = shorttext[(j - suffix_length)...j] + shorttext[j...(j + prefix_length)]
      best_longtext_a = longtext[0...(i - suffix_length)]
      best_longtext_b = longtext[(i + prefix_length)..-1]
      best_shorttext_a = shorttext[0...(j - suffix_length)]
      best_shorttext_b = shorttext[(j + prefix_length)..-1]
    end
  end

  if best_common.length * 2 >= longtext.length
    [best_longtext_a, best_longtext_b, best_shorttext_a, best_shorttext_b,  best_common]
  end
end

#diff_levenshtein(diffs) ⇒ Object

Compute the Levenshtein distance; the number of inserted, deleted or substituted characters.



967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
 
# File 'lib/diff_match_patch.rb', line 967

def diff_levenshtein(diffs)
  levenshtein = 0
  insertions = 0
  deletions = 0

  diffs.each do |op, data|
    case op
      when :insert
        insertions += data.length
      when :delete
        deletions += data.length
      when :equal
        # A deletion and an insertion is one substitution.
        levenshtein += [insertions, deletions].max
        insertions = 0
        deletions = 0
    end
  end

  levenshtein + [insertions, deletions].max
end

#diff_lineMode(text1, text2, deadline) ⇒ Object

Do a quick line-level diff on both strings, then rediff the parts for greater accuracy. This speedup can produce non-minimal diffs.



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
 
# File 'lib/diff_match_patch.rb', line 147

def diff_lineMode(text1, text2, deadline)
  # Scan the text on a line-by-line basis first.
  text1, text2, line_array = diff_linesToChars(text1, text2)

  diffs = diff_main(text1, text2, false, deadline)

  # Convert the diff back to original text.
  diff_charsToLines(diffs, line_array)
  # Eliminate freak matches (e.g. blank lines)
  diff_cleanupSemantic(diffs)

  # Rediff any replacement blocks, this time character-by-character.
  # Add a dummy entry at the end.
  diffs.push([:equal, ''])
  pointer = 0
  count_delete = 0
  count_insert = 0
  text_delete = ''
  text_insert = ''

  while pointer < diffs.length
    case diffs[pointer][0]
      when :insert
        count_insert += 1
        text_insert += diffs[pointer][1]
      when :delete
        count_delete += 1
        text_delete += diffs[pointer][1]
      when :equal
        # Upon reaching an equality, check for prior redundancies.
        if count_delete >= 1 && count_insert >= 1
          # Delete the offending records and add the merged ones.
          a = diff_main(text_delete, text_insert, false, deadline)
          diffs[pointer - count_delete - count_insert, 
            count_delete + count_insert] = []
          pointer = pointer - count_delete - count_insert
          diffs[pointer, 0] = a
          pointer = pointer + a.length
        end
        count_insert = 0
        count_delete = 0
        text_delete = ''
        text_insert = ''
    end
    pointer += 1
  end
  
  diffs.pop # Remove the dummy entry at the end. 
  return diffs
end

#diff_linesToChars(text1, text2) ⇒ Object

Split two texts into an array of strings. Reduce the texts to a string of hashes where each Unicode character represents one line.



322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
 
# File 'lib/diff_match_patch.rb', line 322

def diff_linesToChars(text1, text2)
  line_array = ['']  # e.g. line_array[4] == "Hello\n"
  line_hash = {}     # e.g. line_hash["Hello\n"] == 4

  [text1, text2].map do |text|
    # Split text into an array of strings.  Reduce the text to a string of
    # hashes where each Unicode character represents one line.
    chars = ''
    text.each_line do |line|
      if line_hash[line]
        chars += line_hash[line].chr(Encoding::UTF_8)
      else
        chars += line_array.length.chr(Encoding::UTF_8)
        line_hash[line] = line_array.length
        line_array.push(line)
      end
    end
    chars
  end.push(line_array)
end

#diff_main(text1, text2, checklines = true, deadline = nil) ⇒ Object

Find the differences between two texts. Simplifies the problem by stripping any common prefix or suffix off the texts before diffing.



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
 
# File 'lib/diff_match_patch.rb', line 46

def diff_main(text1, text2, checklines=true, deadline=nil)
  # Set a deadline by which time the diff must be complete.
  if deadline.nil? && diff_timeout > 0
      deadline = Time.now + diff_timeout
  end

  # Check for null inputs.
  if text1.nil? || text2.nil?
    raise ArgumentError.new('Null inputs. (diff_main)')
  end

  # Check for equality (speedup).
  if text1 == text2
    return [] if text1.empty?
    return [[:equal, text1]] 
  end
     
  checklines = true if checklines.nil?

  # Trim off common prefix (speedup).
  common_length = diff_commonPrefix(text1, text2)
  if common_length.nonzero?
    common_prefix = text1[0...common_length]
    text1 = text1[common_length..-1]
    text2 = text2[common_length..-1]    
  end

  # Trim off common suffix (speedup).
  common_length = diff_commonSuffix(text1, text2)
  if common_length.nonzero?
    common_suffix = text1[-common_length..-1]
    text1 = text1[0...-common_length]
    text2 = text2[0...-common_length]
  end

  # Compute the diff on the middle block.
  diffs = diff_compute(text1, text2, checklines, deadline)

  # Restore the prefix and suffix.
  diffs.unshift([:equal, common_prefix]) unless common_prefix.nil?
  diffs.push([:equal, common_suffix]) unless common_suffix.nil?
  diff_cleanupMerge(diffs)  

  diffs
end

#diff_prettyHtml(diffs) ⇒ Object

Convert a diff array into a pretty HTML report.



929
930
931
932
933
934
935
936
937
938
939
940
941
 
# File 'lib/diff_match_patch.rb', line 929

def diff_prettyHtml(diffs)
  diffs.map do |op, data|
    text = data.gsub('&', '&amp;').gsub('<', '&lt;').gsub('>', '&gt;').gsub('\n', '&para;<br>')
    case op
      when :insert
        "<ins style=\"background:#e6ffe6;\">#{text}</ins>"
      when :delete
        "<del style=\"background:#ffe6e6;\">#{text}</del>"
      when :equal
        "<span>#{text}</span>"
    end
  end.join
end

#diff_text1(diffs) ⇒ Object

Compute and return the source text (all equalities and deletions).



944
945
946
947
948
949
950
951
952
 
# File 'lib/diff_match_patch.rb', line 944

def diff_text1(diffs)
  diffs.map do |op, data|
    if op == :insert
      ''
    else
      data
    end
  end.join
end

#diff_text2(diffs) ⇒ Object

Compute and return the destination text (all equalities and insertions).



955
956
957
958
959
960
961
962
963
 
# File 'lib/diff_match_patch.rb', line 955

def diff_text2(diffs)
  diffs.map do |op, data|
    if op == :delete
      ''
    else
      data
    end
  end.join
end

#diff_toDelta(diffs) ⇒ Object

Crush the diff into an encoded string which describes the operations required to transform text1 into text2. E.g. =3t-2t+ing -> Keep 3 chars, delete 2 chars, insert ‘ing’. Operations are tab-separated. Inserted text is escaped using %xx notation.



993
994
995
996
997
998
999
1000
1001
1002
1003
1004
 
# File 'lib/diff_match_patch.rb', line 993

def diff_toDelta(diffs)
  diffs.map do |op, data|
    case op
      when :insert
        '+' + URI.encode(data, /[^0-9A-Za-z_.;!~*'(),\/?:@&=+$\#-]/)
      when :delete
        '-' + data.length.to_s
      when :equal
        '=' + data.length.to_s
    end
  end.join("\t").gsub('%20', ' ')
end

#diff_xIndex(diffs, loc) ⇒ Object

loc is a location in text1, compute and return the equivalent location in text2. e.g. ‘The cat’ vs ‘The big cat’, 1->1, 5->8



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
 
# File 'lib/diff_match_patch.rb', line 898

def diff_xIndex(diffs, loc)
  chars1 = 0
  chars2 = 0
  last_chars1 = 0
  last_chars2 = 0
  x = diffs.index do |diff|
    if diff[0] != :insert
      chars1 += diff[1].length
    end
    if diff[0] != :delete
      chars2 += diff[1].length
    end 
    if chars1 > loc
      true
    else
      last_chars1 = chars1
      last_chars2 = chars2
      false
    end
  end

  if diffs.length != x && diffs[x][0] == :delete
    # The location was deleted.
    last_chars2
  else
    # Add the remaining len(character).
    last_chars2 + (loc - last_chars1)
  end
end

#match_alphabet(pattern) ⇒ Object

Initialise the alphabet for the Bitap algorithm.



1172
1173
1174
1175
1176
1177
1178
1179
 
# File 'lib/diff_match_patch.rb', line 1172

def match_alphabet(pattern)
  s = {}
  pattern.chars.each_with_index do |c, i|
    s[c] ||= 0
    s[c] |= 1 << (pattern.length - i - 1)
  end
  s
end

#match_bitap(text, pattern, loc) ⇒ Object

Locate the best instance of ‘pattern’ in ‘text’ near ‘loc’ using the Bitap algorithm.



1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
 
# File 'lib/diff_match_patch.rb', line 1073

def match_bitap(text, pattern, loc)
  if pattern.length > match_maxBits
    throw ArgumentError.new("Pattern too long")
  end

  # Initialise the alphabet.
  s = match_alphabet(pattern)

  # Compute and return the score for a match with e errors and x location.
  match_bitapScore = -> e, x do
    accuracy = e.to_f / pattern.length
    proximity = (loc - x).abs
    if match_distance == 0
      # Dodge divide by zero error.
      return proximity == 0 ? accuracy : 1.0
    end
    return accuracy + (proximity.to_f / match_distance)
  end    

  # Highest score beyond which we give up.
  score_threshold = match_threshold
  # Is there a nearby exact match? (speedup)
  best_loc = text.index(pattern, loc)
  if best_loc
    score_threshold = [match_bitapScore[0, best_loc], score_threshold].min
    # What about in the other direction? (speedup)
    best_loc = text.rindex(pattern, loc + pattern.length)
    if best_loc
      score_threshold = [match_bitapScore[0, best_loc], score_threshold].min
    end
  end

  # Initialise the bit arrays.
  match_mask = 1 << (pattern.length - 1)
  best_loc = -1

  bin_max = pattern.length + text.length  
  # Empty initialization added to appease pychecker.
  last_rd = nil
  pattern.length.times do |d|
    # Scan for the best match; each iteration allows for one more error.
    # Run a binary search to determine how far from 'loc' we can stray at this
    # error level.
    bin_min = 0
    bin_mid = bin_max
    while bin_min < bin_mid
      if match_bitapScore[d, loc + bin_mid] <= score_threshold
        bin_min = bin_mid
      else
        bin_max = bin_mid
      end
      bin_mid = (bin_max - bin_min) / 2 + bin_min
    end

    # Use the result from this iteration as the maximum for the next.
    bin_max = bin_mid
    start = [1, loc - bin_mid + 1].max
    finish = [loc + bin_mid, text.length].min + pattern.length

    rd = Array.new(finish + 2, 0)
    rd[finish + 1] = (1 << d) - 1
    finish.downto(start) do |j|
      char_match = s[text[j - 1]] || 0        
      if d == 0 # First pass: exact match.
        rd[j] = ((rd[j + 1] << 1) | 1) & char_match
      else # Subsequent passes: fuzzy match.
        rd[j] = ((rd[j + 1] << 1) | 1) & char_match |
          (((last_rd[j + 1] | last_rd[j]) << 1) | 1) | last_rd[j + 1]
      end
      if (rd[j] & match_mask).nonzero?
        score = match_bitapScore[d, j - 1]
        # This match will almost certainly be better than any existing match.
        # But check anyway.
        if score <= score_threshold
          # Told you so.
          score_threshold = score
          best_loc = j - 1
          if best_loc > loc
            # When passing loc, don't exceed our current distance from loc.
            start = [1, 2 * loc - best_loc].max
          else
            # Already passed loc, downhill from here on in.
            break
          end
        end
      end
    end

    # No hope for a (better) match at greater error levels.
    if match_bitapScore[d + 1, loc] > score_threshold
      break
    end
    last_rd = rd
  end

  best_loc
end

#match_main(text, pattern, loc) ⇒ Object

Locate the best instance of ‘pattern’ in ‘text’ near ‘loc’.



1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
 
# File 'lib/diff_match_patch.rb', line 1049

def match_main(text, pattern, loc)
  # Check for null inputs.
  if [text, pattern].any?(&:nil?)
    raise ArgumentError.new("Null input. (match_main)")
  end

  loc = [0, [loc, text.length].min].max
  if text == pattern
    # Shortcut (potentially not guaranteed by the algorithm)
    0
  elsif text.empty?
    # Nothing to match
    -1
  elsif text[loc, pattern.length] == pattern
    # Perfect match at the perfect spot!  (Includes case of null pattern)
    loc
  else
    # Do a fuzzy compare.
    match_bitap(text, pattern, loc)
  end
end

#patch_addContext(patch, text) ⇒ Object

Increase the context until it is unique, but don’t let the pattern expand beyond match_maxBits



1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
 
# File 'lib/diff_match_patch.rb', line 1261

def patch_addContext(patch, text)
  return  if text.empty?
  pattern = text[patch.start2, patch.length1]
  padding = 0

  # Look for the first and last matches of pattern in text.  If two different
  # matches are found, increase the pattern length.
  while text.index(pattern) != text.rindex(pattern) &&
        pattern.length < match_maxBits - 2 * patch_margin
    padding += patch_margin
    pattern = text[[0, patch.start2 - padding].max...(patch.start2 + patch.length1 + padding)]
  end

  # Add one chunk for good luck.
  padding += patch_margin

  # Add the prefix.
  prefix = text[[0, patch.start2 - padding].max...patch.start2]
  patch.diffs.unshift([:equal, prefix]) if !prefix.to_s.empty?

  # Add the suffix.
  suffix = text[patch.start2 + patch.length1, padding]
  patch.diffs.push([:equal, suffix]) if !suffix.to_s.empty?
 
  # Roll back the start points.
  patch.start1 -= prefix.length
  patch.start2 -= prefix.length

  # Extend the lengths.
  patch.length1 += prefix.length + suffix.length
  patch.length2 += prefix.length + suffix.length
end

#patch_addPadding(patches) ⇒ Object

Add some padding on text start and end so that edges can match something. Intended to be called only from within patch_apply.



1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
 
# File 'lib/diff_match_patch.rb', line 1493

def patch_addPadding(patches)
  padding_length = patch_margin
  null_padding = (1..padding_length).map{ |x| x.chr(Encoding::UTF_8) }.join

  # Bump all the patches forward.
  patches.each do |patch|
    patch.start1 += padding_length
    patch.start2 += padding_length
  end

  # Add some padding on start of first diff.
  patch = patches.first
  diffs = patch.diffs
  if diffs.empty? || diffs.first[0] != :equal
    # Add nullPadding equality.
    diffs.unshift([:equal, null_padding])
    patch.start1 -= padding_length  # Should be 0.
    patch.start2 -= padding_length  # Should be 0.
    patch.length1 += padding_length
    patch.length2 += padding_length
  elsif padding_length > diffs.first[1].length
    # Grow first equality.
    extra_length = padding_length - diffs.first[1].length
    diffs.first[1] = null_padding[diffs.first[1].length..-1] + diffs.first[1]
    patch.start1 -= extra_length
    patch.start2 -= extra_length
    patch.length1 += extra_length
    patch.length2 += extra_length
  end

  # Add some padding on end of last diff.
  patch = patches.last
  diffs = patch.diffs
  if diffs.empty? || diffs.last[0] != :equal
    # Add nullPadding equality.
    diffs.push([:equal, null_padding])
    patch.length1 += padding_length
    patch.length2 += padding_length
  elsif padding_length > diffs.last[1].length
    # Grow last equality.
    extra_length = padding_length - diffs.last[1].length
    diffs.last[1] += null_padding[0, extra_length]
    patch.length1 += extra_length
    patch.length2 += extra_length
  end

  null_padding
end

#patch_apply(patches, text) ⇒ Object

Merge a set of patches onto the text. Return a patched text, as well as a list of true/false values indicating which patches were applied.



1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
 
# File 'lib/diff_match_patch.rb', line 1407

def patch_apply(patches, text)  
  return [text, []]  if patches.empty?

  # Deep copy the patches so that no changes are made to originals.
  patches = Marshal.load(Marshal.dump(patches))

  null_padding = patch_addPadding(patches)
  text = null_padding + text + null_padding
  patch_splitMax(patches)

  # delta keeps track of the offset between the expected and actual location
  # of the previous patch.  If there are patches expected at positions 10 and
  # 20, but the first patch was found at 12, delta is 2 and the second patch
  # has an effective expected position of 22.
  delta = 0
  results = []
  patches.each_with_index do |patch, x|
    expected_loc = patch.start2 + delta
    text1 = diff_text1(patch.diffs)
    end_loc = -1      
    if text1.length > match_maxBits
      # patch_splitMax will only provide an oversized pattern in the case of
      # a monster delete.
      start_loc = match_main(text, text1[0, match_maxBits], expected_loc)
      if start_loc != -1
        end_loc = match_main(text, text1[(text1.length - match_maxBits)..-1],
          expected_loc + text1.length - match_maxBits)
        if end_loc == -1 || start_loc >= end_loc
          # Can't find valid trailing context.  Drop this patch.
          start_loc = -1
        end
      end
    else
      start_loc = match_main(text, text1, expected_loc)
    end
    if start_loc == -1
      # No match found.  :(
      results[x] = false
      # Subtract the delta for this failed patch from subsequent patches.
      delta -= patch.length2 - patch.length1
    else
      # Found a match.  :)
      results[x] = true
      delta = start_loc - expected_loc
      text2 = text[start_loc, (end_loc == -1) ? text1.length : end_loc + match_maxBits]
 
      if text1 == text2
        # Perfect match, just shove the replacement text in.
        text = text[0, start_loc] + diff_text2(patch.diffs) + text[(start_loc + text1.length)..-1]
      else
        # Imperfect match. 
        # Run a diff to get a framework of equivalent indices.
        diffs = diff_main(text1, text2, false)
        if text1.length > match_maxBits &&
           diff_levenshtein(diffs).to_f / text1.length > patch_deleteThreshold
          # The end points match, but the content is unacceptably bad.
          results[x] = false
        else
          diff_cleanupSemanticLossless(diffs)
          index1 = 0  
          patch.diffs.each do |op, data|
            if op != :equal
              index2 = diff_xIndex(diffs, index1)
            end
            if op == :insert  # Insertion
              text = text[0, start_loc + index2] + data + text[(start_loc + index2)..-1]
            elsif op == :delete  # Deletion
              text = text[0, start_loc + index2] +
               text[(start_loc + diff_xIndex(diffs, index1 + data.length))..-1]
            end
            if op != :delete
              index1 += data.length
            end
          end
        end
      end
    end
  end

  # Strip the padding off.
  text = text[null_padding.length...-null_padding.length]  
  [text, results]
end

#patch_fromText(textline) ⇒ Object

Parse a textual representation of patches and return a list of patch objects.



1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
 
# File 'lib/diff_match_patch.rb', line 1183

def patch_fromText(textline)
  return []  if textline.empty?

  patches = []
  text = textline.split("\n")
  text_pointer = 0
  patch_header = /^@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@$/
  while text_pointer < text.length
    m = text[text_pointer].match(patch_header)
    if m.nil?
      raise ArgumentError.new("Invalid patch string: #{text[text_pointer]}")
    end
    patch = PatchObj.new
    patches.push(patch)
    patch.start1 = m[1].to_i
    if m[2].empty?
      patch.start1 -= 1
      patch.length1 = 1
    elsif m[2] == '0'
      patch.length1 = 0
    else
      patch.start1 -= 1
      patch.length1 = m[2].to_i
    end

    patch.start2 = m[3].to_i
    if m[4].empty?
      patch.start2 -= 1
      patch.length2 = 1
    elsif m[4] == '0'
      patch.length2 = 0
    else
      patch.start2 -= 1
      patch.length2 = m[4].to_i
    end
    text_pointer += 1

    while text_pointer < text.length
      if text[text_pointer].empty?
        # Blank line? Whatever.
        text_pointer += 1
        next
      end

      sign = text[text_pointer][0]
      line = URI.decode(text[text_pointer][1..-1].force_encoding(Encoding::UTF_8))

      case sign
      when '-'
        # Deletion.
        patch.diffs.push([:delete, line])
      when '+'
        # Insertion.
        patch.diffs.push([:insert, line])
      when ' '
        # Minor equality
        patch.diffs.push([:equal, line])
      when '@'
        # Start of next patch.
        break
      else
        # WTF?
        raise ArgumentError.new("Invalid patch mode \"#{sign}\" in: #{line}")
      end
      text_pointer += 1
    end
  end

  patches
end

#patch_make(*args) ⇒ Object

Compute a list of patches to turn text1 into text2. Use diffs if provided, otherwise compute it ourselves. There are four ways to call this function, depending on what data is available to the caller: Method 1: a = text1, b = text2 Method 2: a = diffs Method 3 (optimal): a = text1, b = diffs Method 4 (deprecated, use method 3): a = text1, b = text2, c = diffs



1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
 
# File 'lib/diff_match_patch.rb', line 1306

def patch_make(*args)
  text1 = nil
  diffs = nil
  if args.length == 2 && args[0].is_a?(String) && args[1].is_a?(String)
    # Compute diffs from text1 and text2.
    text1 = args[0]
    text2 = args[1]
    diffs = diff_main(text1, text2, true)
    if diffs.length > 2
      diff_cleanupSemantic(diffs)
      diff_cleanupEfficiency(diffs)
    end
  elsif args.length == 1 && args[0].is_a?(Array)
    # Compute text1 from diffs.
    diffs = args[0]
    text1 = diff_text1(diffs)
  elsif args.length == 2 && args[0].is_a?(String) && args[1].is_a?(Array)
    text1 = args[0]
    diffs = args[1]
  elsif args.length == 3 && args[0].is_a?(String) && args[1].is_a?(String) &&
        args[2].is_a?(Array)
    # Method 4: text1, text2, diffs
    # text2 is not used.
    text1 = args[0]
    text2 = args[1]
    diffs = args[2]
  else
    raise ArgumentError.new('Unknown call format to patch_make.')
  end

  return []  if diffs.empty? # Get rid of the null case.

  patches = []
  patch = PatchObj.new
  char_count1 = 0 # Number of characters into the text1 string.
  char_count2 = 0 # Number of characters into the text2 string.
  prepatch_text = text1 # Recreate the patches to determine context info.
  postpatch_text = text1

  diffs.each_with_index do |diff, x|
    diff_type, diff_text = diffs[x]
    if patch.diffs.empty? && diff_type != :equal
      # A new patch starts here.
      patch.start1 = char_count1
      patch.start2 = char_count2
    end

    case diff_type
      when :insert
        patch.diffs.push(diff)
        patch.length2 += diff_text.length
        postpatch_text = postpatch_text[0...char_count2] + diff_text +
          postpatch_text[char_count2..-1]
      when :delete
        patch.length1 += diff_text.length
        patch.diffs.push(diff)
        postpatch_text = postpatch_text[0...char_count2] +
          postpatch_text[(char_count2 + diff_text.length)..-1]
      when :equal
        if diff_text.length <= 2 * patch_margin &&
           !patch.diffs.empty? && diffs.length != x + 1
          # Small equality inside a patch.
          patch.diffs.push(diff)
          patch.length1 += diff_text.length
          patch.length2 += diff_text.length
        elsif diff_text.length >= 2 * patch_margin
          # Time for a new patch.
          unless patch.diffs.empty?
            patch_addContext(patch, prepatch_text)
            patches.push(patch)
            patch = PatchObj.new
            # Unlike Unidiff, our patch lists have a rolling context.
            # http://code.google.com/p/google-diff-match-patch/wiki/Unidiff
            # Update prepatch text & pos to reflect the application of the
            # just completed patch.
            prepatch_text = postpatch_text
            char_count1 = char_count2
          end
        end
    end

    # Update the current character count.
    if diff_type != :insert
      char_count1 += diff_text.length
    end
    if diff_type != :delete
      char_count2 += diff_text.length
    end
  end

  # Pick up the leftover patch if not empty.
  unless patch.diffs.empty?
    patch_addContext(patch, prepatch_text)
    patches.push(patch)
  end

  patches
end

#patch_splitMax(patches) ⇒ Object

Look through the patches and break up any which are longer than the maximum limit of the match algorithm.



1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
 
# File 'lib/diff_match_patch.rb', line 1544

def patch_splitMax(patches)
  patch_size = match_maxBits

  x = 0
  while x < patches.length
    if patches[x].length1 > patch_size
      big_patch = patches[x]
      # Remove the big old patch
      patches[x, 1] = []
      x -= 1
      start1 = big_patch.start1
      start2 = big_patch.start2
      pre_context = ''
      while !big_patch.diffs.empty?
        # Create one of several smaller patches.
        patch = PatchObj.new
        empty = true
        patch.start1 = start1 - pre_context.length
        patch.start2 = start2 - pre_context.length
        unless pre_context.empty?
          patch.length1 = patch.length2 = pre_context.length
          patch.diffs.push([:equal, pre_context])
        end

        while !big_patch.diffs.empty? && patch.length1 < patch_size - patch_margin
          diff = big_patch.diffs.first
          if diff[0] == :insert
            # Insertions are harmless.
            patch.length2 += diff[1].length
            start2 += diff[1].length
            patch.diffs.push(big_patch.diffs.shift)
            empty = false
          elsif diff[0] == :delete && patch.diffs.length == 1 &&
                patch.diffs.first[0] == :equal && diff[1].length > 2 * patch_size
            # This is a large deletion.  Let it pass in one chunk.
            patch.length1 += diff[1].length
            start1 += diff[1].length
            empty = false
            patch.diffs.push(big_patch.diffs.shift)
          else
            # Deletion or equality.  Only take as much as we can stomach.
            diff_text = diff[1][0, patch_size - patch.length1 - patch_margin]
            patch.length1 += diff_text.length
            start1 += diff_text.length
            if diff[0] == :equal
              patch.length2 += diff_text.length
              start2 += diff_text.length
            else
              empty = false
            end
            patch.diffs.push([diff[0], diff_text])
            if diff_text == big_patch.diffs.first[1]
              big_patch.diffs.shift
            else
              big_patch.diffs.first[1] = big_patch.diffs.first[1][diff_text.length..-1]
            end
          end
        end

        # Compute the head context for the next patch.
        pre_context = diff_text2(patch.diffs)[-patch_margin..-1] || ''

        # Append the end context for this patch.
        post_context = diff_text1(big_patch.diffs)[0...patch_margin] || ''
        unless post_context.empty?
          patch.length1 += post_context.length
          patch.length2 += post_context.length
          if !patch.diffs.empty? && patch.diffs.last[0] == :equal
            patch.diffs.last[1] += post_context
          else
            patch.diffs.push([:equal, post_context])
          end
        end
        if !empty
          x += 1
          patches[x, 0] = [patch]
        end
      end
    end
    x += 1
  end
end

#patch_toText(patches) ⇒ Object

Take a list of patches and return a textual representation



1255
1256
1257
 
# File 'lib/diff_match_patch.rb', line 1255

def patch_toText(patches)
  patches.join
end