Module: DiffMatchPatchES

Defined in:
lib/diff_match_patch_es.rb,
lib/diff_match_patch_es.rb,
lib/diff_match_patch_es/diff.rb,
lib/diff_match_patch_es/match.rb,
lib/diff_match_patch_es/patch.rb,
lib/diff_match_patch_es/options.rb,
lib/diff_match_patch_es/version.rb,
lib/diff_match_patch_es/js_string.rb,
sig/diff_match_patch_es.rbs,
sig/diff_match_patch_es/diff.rbs,
sig/diff_match_patch_es/match.rbs,
sig/diff_match_patch_es/patch.rbs,
sig/diff_match_patch_es/options.rbs,
sig/diff_match_patch_es/version.rbs,
sig/diff_match_patch_es/js_string.rbs

Overview

Ruby port of diff-match-patch-es (the TypeScript/ESM rewrite by Anthony Fu of Neil Fraser's diff-match-patch), producing identical results.

The API is a set of stateless module functions; nothing mutates shared state, DEFAULT_OPTIONS is frozen, and every call operates only on its arguments and locals, so the module is safe to use from multiple threads (and Ractors) concurrently.

Defined Under Namespace

Modules: JsString Classes: Error, Options, Patch

Constant Summary collapse

DIFF_DELETE =

Returns:

  • (-1) 
-1
DIFF_INSERT =

Returns:

  • (1) 
1
DIFF_EQUAL =

Returns:

  • (0) 
0
LINE_INDEX_SURROGATE_SHIFT =

Line-mode diffing maps each unique line to a single character. JavaScript strings tolerate lone surrogates (code units 0xD800..0xDFFF) but UTF-8 cannot represent them, so indices at or above 0xD800 shift up by 0x800. The mapping is injective either way, and the diff algorithm only observes equality between these placeholder characters, so results are identical.

Returns:

  • (Integer) 
0x800
NON_ALPHA_NUMERIC_REGEX =

Returns:

  • (Regexp) 
/[^a-z0-9]/i
WHITESPACE_REGEX =

Matches the JS \s class (which the reference implementation uses).

Returns:

  • (Regexp) 
/[\t\n\v\f\r \u00A0\u1680\u2000-\u200A\u2028\u2029\u202F\u205F\u3000\uFEFF]/
LINEBREAK_REGEX =

Returns:

  • (Regexp) 
/[\r\n]/
BLANKLINE_END_REGEX =

Returns:

  • (Regexp) 
/\n\r?\n\z/
BLANKLINE_START_REGEX =

Returns:

  • (Regexp) 
/\A\r?\n\r?\n/
MASK32 =

JS bitwise operators coerce to 32-bit integers; Ruby integers are arbitrary precision, so shifts are masked to keep the two congruent.

Returns:

  • (Integer) 
0xFFFFFFFF
DEFAULT_OPTIONS =

Returns:

Options.new.freeze
VERSION =

Returns:

  • (String) 
'2.0.0'

Class Method Summary collapse

Instance Method Summary collapse

Class Method Details

.create_diff(op, text) ⇒ Object 



18
19
20
 
# File 'lib/diff_match_patch_es/diff.rb', line 18

def create_diff(op, text)
  [op, text]
end

.create_patch ⇒ Object 



60
61
62
 
# File 'lib/diff_match_patch_es/patch.rb', line 60

def create_patch
  Patch.new
end

.diff(text1, text2, options = nil, checklines = true, deadline = nil) ⇒ Object 



40
41
42
 
# File 'lib/diff_match_patch_es.rb', line 40

def diff(text1, text2, options = nil, checklines = true, deadline = nil)
  diff_main(text1, text2, options, checklines, deadline)
end

.diff_bisect(text1, text2, options, 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.



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 176

def diff_bisect(text1, text2, options, 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.odd?
  # Offsets for start and end of k loop.
  # Prevents mapping of space beyond the grid.
  k1start = 0
  k1end = 0
  k2start = 0
  k2end = 0
  d = 0
  while d < max_d
    # Bail out if deadline is reached.
    break if now_ms > deadline

    # Walk the front path one step.
    k1 = -d + k1start
    while k1 <= d - k1end
      k1_offset = v_offset + k1
      x1 = if k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])
             v1[k1_offset + 1]
           else
             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_bisect_split(text1, text2, options, x1, y1, deadline)
          end
        end
      end
      k1 += 2
    end

    # Walk the reverse path one step.
    k2 = -d + k2start
    while k2 <= d - k2end
      k2_offset = v_offset + k2
      x2 = if k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])
             v2[k2_offset + 1]
           else
             v2[k2_offset - 1] + 1
           end
      y2 = x2 - k2
      while x2 < text1_length && y2 < text2_length &&
            text1[text1_length - x2 - 1] == text2[text2_length - 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_bisect_split(text1, text2, options, x1, y1, deadline)
          end
        end
      end
      k2 += 2
    end
    d += 1
  end
  # Diff took too long and hit the deadline or
  # number of diffs equals number of characters, no commonality at all.
  [create_diff(DIFF_DELETE, text1), create_diff(DIFF_INSERT, text2)]
end

.diff_bisect_split(text1, text2, options, x, y, deadline) ⇒ Object

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



283
284
285
286
287
288
289
290
291
292
293
294
 
# File 'lib/diff_match_patch_es/diff.rb', line 283

def diff_bisect_split(text1, text2, options, x, y, deadline)
  text1a = JsString.substring(text1, 0, x)
  text2a = JsString.substring(text2, 0, y)
  text1b = JsString.substring(text1, x)
  text2b = JsString.substring(text2, y)

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

  diffs.concat(diffsb)
end

.diff_chars_to_lines(diffs, line_array) ⇒ Object

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



358
359
360
361
362
363
364
365
366
 
# File 'lib/diff_match_patch_es/diff.rb', line 358

def diff_chars_to_lines(diffs, line_array)
  diffs.each do |diff|
    chars = diff[1]
    text = +''
    chars.each_char { |ch| text << line_array[line_index_for(ch)] }
    diff[1] = text
  end
  nil
end

.diff_cleanup_efficiency(diffs, options = nil) ⇒ Object

Reduce the number of edits by eliminating operationally trivial equalities.



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 731

def diff_cleanup_efficiency(diffs, options = nil)
  diff_edit_cost = resolve_options(options).diff_edit_cost

  changes = false
  # Stack of indices where equalities are found (Hash for the same
  # negative-index reason as in diff_cleanup_semantic).
  equalities = {}
  equalities_length = 0
  last_equality = nil
  # Always equal to diffs[equalities[equalities_length - 1]][1]
  pointer = 0 # Index of current position.

  # Is there an insertion operation before the last equality.
  pre_ins = false
  # Is there a deletion operation before the last equality.
  pre_del = false
  # Is there an insertion operation after the last equality.
  post_ins = false
  # Is there a deletion operation after the last equality.
  post_del = false
  while pointer < diffs.length
    if diffs[pointer][0] == DIFF_EQUAL # Equality found.
      if diffs[pointer][1].length < diff_edit_cost && (post_ins || post_del)
        # Candidate found.
        equalities[equalities_length] = pointer
        equalities_length += 1
        pre_ins = post_ins
        pre_del = post_del
        last_equality = diffs[pointer][1]
      else
        # Not a candidate, and can never become one.
        equalities_length = 0
        last_equality = nil
      end
      post_ins = post_del = false
    else # An insertion or deletion.
      if diffs[pointer][0] == DIFF_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 && ((pre_ins && pre_del && post_ins && post_del) ||
        ((last_equality.length < diff_edit_cost / 2.0) &&
          [pre_ins, pre_del, post_ins, post_del].count(true) == 3))
        # Duplicate record.
        diffs.insert(equalities[equalities_length - 1], create_diff(DIFF_DELETE, last_equality))
        # Change second copy to insert.
        diffs[equalities[equalities_length - 1] + 1][0] = DIFF_INSERT
        equalities_length -= 1 # Throw away the equality we just deleted;
        last_equality = nil
        if pre_ins && pre_del
          # No changes made which could affect previous entry, keep going.
          post_ins = post_del = true
          equalities_length = 0
        else
          equalities_length -= 1 # Throw away the previous equality.
          pointer = equalities_length.positive? ? equalities[equalities_length - 1] : -1
          post_ins = post_del = false
        end
        changes = true
      end
    end
    pointer += 1
  end

  diff_cleanup_merge(diffs) if changes
  nil
end

.diff_cleanup_merge(diffs) ⇒ Object

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



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 809

def diff_cleanup_merge(diffs)
  # Add a dummy entry at the end.
  diffs.push(create_diff(DIFF_EQUAL, ''))
  pointer = 0
  count_delete = 0
  count_insert = 0
  text_delete = +''
  text_insert = +''
  while pointer < diffs.length
    case diffs[pointer][0]
    when DIFF_INSERT
      count_insert += 1
      text_insert += diffs[pointer][1]
      pointer += 1
    when DIFF_DELETE
      count_delete += 1
      text_delete += diffs[pointer][1]
      pointer += 1
    when DIFF_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 prefixes.
          commonlength = diff_common_prefix(text_insert, text_delete)
          if commonlength != 0
            if (pointer - count_delete - count_insert).positive? &&
               diffs[pointer - count_delete - count_insert - 1][0] == DIFF_EQUAL
              diffs[pointer - count_delete - count_insert - 1][1] += JsString.substring(text_insert, 0, commonlength)
            else
              diffs.insert(0, create_diff(DIFF_EQUAL, JsString.substring(text_insert, 0, commonlength)))
              pointer += 1
            end
            text_insert = JsString.substring(text_insert, commonlength)
            text_delete = JsString.substring(text_delete, commonlength)
          end
          # Factor out any common suffixes.
          commonlength = diff_common_suffix(text_insert, text_delete)
          if commonlength != 0
            diffs[pointer][1] = JsString.substring(text_insert, text_insert.length - commonlength) + diffs[pointer][1]
            text_insert = JsString.substring(text_insert, 0, text_insert.length - commonlength)
            text_delete = JsString.substring(text_delete, 0, text_delete.length - commonlength)
          end
        end
        # Delete the offending records and add the merged ones.
        pointer -= count_delete + count_insert
        diffs.slice!(pointer, count_delete + count_insert)
        unless text_delete.empty?
          diffs.insert(pointer, create_diff(DIFF_DELETE, text_delete))
          pointer += 1
        end
        unless text_insert.empty?
          diffs.insert(pointer, create_diff(DIFF_INSERT, text_insert))
          pointer += 1
        end
        pointer += 1
      elsif pointer != 0 && diffs[pointer - 1][0] == DIFF_EQUAL
        # Merge this equality with the previous one.
        diffs[pointer - 1][1] += diffs[pointer][1]
        diffs.delete_at(pointer)
      else
        pointer += 1
      end
      count_insert = 0
      count_delete = 0
      text_delete = +''
      text_insert = +''
    end
  end
  diffs.pop if diffs[diffs.length - 1][1] == '' # Remove the dummy entry at the 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] == DIFF_EQUAL && diffs[pointer + 1][0] == DIFF_EQUAL
      # This is a single edit surrounded by equalities.
      if JsString.substring(diffs[pointer][1], diffs[pointer][1].length - diffs[pointer - 1][1].length) ==
         diffs[pointer - 1][1]
        # Shift the edit over the previous equality.
        diffs[pointer][1] = diffs[pointer - 1][1] +
                            JsString.substring(diffs[pointer][1], 0,
                                               diffs[pointer][1].length - diffs[pointer - 1][1].length)
        diffs[pointer + 1][1] = diffs[pointer - 1][1] + diffs[pointer + 1][1]
        diffs.delete_at(pointer - 1)
        changes = true
      elsif JsString.substring(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] = JsString.substring(diffs[pointer][1], diffs[pointer + 1][1].length) +
                            diffs[pointer + 1][1]
        diffs.delete_at(pointer + 1)
        changes = true
      end
    end
    pointer += 1
  end
  # If shifts were made, the diff needs reordering and another shift sweep.
  diff_cleanup_merge(diffs) if changes
  nil
end

.diff_cleanup_semantic(diffs) ⇒ Object

Reduce the number of edits by eliminating semantically trivial equalities.



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 516

def diff_cleanup_semantic(diffs)
  changes = false
  # Stack of indices where equalities are found. The reference
  # implementation lets the stack pointer go negative and stores into the
  # JS array at index -1 (a plain property write), so a Hash reproduces
  # those semantics.
  equalities = {}
  equalities_length = 0
  last_equality = nil
  # Always equal to diffs[equalities[equalities_length - 1]][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] == DIFF_EQUAL # Equality found.
      equalities[equalities_length] = pointer
      equalities_length += 1
      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] == DIFF_INSERT
        length_insertions2 += diffs[pointer][1].length
      else
        length_deletions2 += diffs[pointer][1].length
      end

      # Eliminate an equality that is smaller or equal to the edits on both
      # sides of it.
      if last_equality &&
         last_equality.length <= [length_insertions1, length_deletions1].max &&
         last_equality.length <= [length_insertions2, length_deletions2].max
        # Duplicate record.
        diffs.insert(equalities[equalities_length - 1], create_diff(DIFF_DELETE, last_equality))
        # Change second copy to insert.
        diffs[equalities[equalities_length - 1] + 1][0] = DIFF_INSERT
        # Throw away the equality we just deleted.
        equalities_length -= 1
        # Throw away the previous equality (it needs to be reevaluated).
        equalities_length -= 1
        pointer = equalities_length.positive? ? equalities[equalities_length - 1] : -1
        length_insertions1 = 0 # Reset the counters.
        length_deletions1 = 0
        length_insertions2 = 0
        length_deletions2 = 0
        last_equality = nil
        changes = true
      end
    end
    pointer += 1
  end

  # Normalize the diff.
  diff_cleanup_merge(diffs) if changes

  diff_cleanup_semantic_lossless(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] == DIFF_DELETE && diffs[pointer][0] == DIFF_INSERT
      deletion = diffs[pointer - 1][1]
      insertion = diffs[pointer][1]
      overlap_length1 = diff_common_overlap(deletion, insertion)
      overlap_length2 = diff_common_overlap(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.insert(pointer, create_diff(DIFF_EQUAL, JsString.substring(insertion, 0, overlap_length1)))
          diffs[pointer - 1][1] = JsString.substring(deletion, 0, deletion.length - overlap_length1)
          diffs[pointer + 1][1] = JsString.substring(insertion, overlap_length1)
          pointer += 1
        end
      elsif overlap_length2 >= deletion.length / 2.0 || overlap_length2 >= insertion.length / 2.0
        # Reverse overlap found.
        # Insert an equality and swap and trim the surrounding edits.
        diffs.insert(pointer, create_diff(DIFF_EQUAL, JsString.substring(deletion, 0, overlap_length2)))
        diffs[pointer - 1][0] = DIFF_INSERT
        diffs[pointer - 1][1] = JsString.substring(insertion, 0, insertion.length - overlap_length2)
        diffs[pointer + 1][0] = DIFF_DELETE
        diffs[pointer + 1][1] = JsString.substring(deletion, overlap_length2)
        pointer += 1
      end
      pointer += 1
    end
    pointer += 1
  end
  nil
end

.diff_cleanup_semantic_lossless(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 cat came. -> The cat came.



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 668

def diff_cleanup_semantic_lossless(diffs)
  pointer = 1
  # Intentionally ignore the first and last element (don't need checking).
  while pointer < diffs.length - 1
    if diffs[pointer - 1][0] == DIFF_EQUAL && diffs[pointer + 1][0] == DIFF_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_common_suffix(equality1, edit)
      if common_offset.positive?
        common_string = JsString.substring(edit, edit.length - common_offset)
        equality1 = JsString.substring(equality1, 0, equality1.length - common_offset)
        edit = common_string + JsString.substring(edit, 0, edit.length - 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_cleanup_semantic_score(equality1, edit) +
                   diff_cleanup_semantic_score(edit, equality2)
      while !edit.empty? && !equality2.empty? && edit[0] == equality2[0]
        equality1 += edit[0]
        edit = JsString.substring(edit, 1) + equality2[0]
        equality2 = JsString.substring(equality2, 1)
        score = diff_cleanup_semantic_score(equality1, edit) +
                diff_cleanup_semantic_score(edit, equality2)
        # The >= encourages trailing rather than leading whitespace on edits.
        next unless score >= best_score

        best_score = score
        best_equality1 = equality1
        best_edit = edit
        best_equality2 = equality2
      end

      if diffs[pointer - 1][1] != best_equality1
        # We have an improvement, save it back to the diff.
        if best_equality1.empty?
          diffs.delete_at(pointer - 1)
          pointer -= 1
        else
          diffs[pointer - 1][1] = best_equality1
        end
        diffs[pointer][1] = best_edit
        if best_equality2.empty?
          diffs.delete_at(pointer + 1)
          pointer -= 1
        else
          diffs[pointer + 1][1] = best_equality2
        end
      end
    end
    pointer += 1
  end
  nil
end

.diff_cleanup_semantic_score(one, two) ⇒ Object

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



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 628

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

  char1 = one[-1]
  char2 = two[0]
  non_alpha_numeric1 = NON_ALPHA_NUMERIC_REGEX.match?(char1)
  non_alpha_numeric2 = NON_ALPHA_NUMERIC_REGEX.match?(char2)
  whitespace1 = non_alpha_numeric1 && WHITESPACE_REGEX.match?(char1)
  whitespace2 = non_alpha_numeric2 && WHITESPACE_REGEX.match?(char2)
  line_break1 = whitespace1 && LINEBREAK_REGEX.match?(char1)
  line_break2 = whitespace2 && LINEBREAK_REGEX.match?(char2)
  blank_line1 = line_break1 && BLANKLINE_END_REGEX.match?(one)
  blank_line2 = line_break2 && BLANKLINE_START_REGEX.match?(two)

  if blank_line1 || blank_line2
    # Five points for blank lines.
    5
  elsif line_break1 || line_break2
    # Four points for line breaks.
    4
  elsif non_alpha_numeric1 && !whitespace1 && whitespace2
    # Three points for end of sentences.
    3
  elsif whitespace1 || whitespace2
    # Two points for whitespace.
    2
  elsif non_alpha_numeric1 || non_alpha_numeric2
    # One point for non-alphanumeric.
    1
  else
    0
  end
end

.diff_common_overlap(text1, text2) ⇒ Object

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



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 417

def diff_common_overlap(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 = JsString.substring(text1, text1_length - text2_length)
  elsif text1_length < text2_length
    text2 = JsString.substring(text2, 0, text1_length)
  end

  text_length = [text1_length, text2_length].min
  # Quick check for the worst 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: https://neil.fraser.name/news/2010/11/04/
  best = 0
  length = 1
  loop do
    pattern = JsString.substring(text1, text_length - length)
    found = JsString.index_of(text2, pattern)
    return best if found == -1

    length += found
    if found.zero? || JsString.substring(text1, text_length - length) == JsString.substring(text2, 0, length)
      best = length
      length += 1
    end
  end
end

.diff_common_prefix(text1, text2) ⇒ Object

Determine the common prefix of two strings.



369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
 
# File 'lib/diff_match_patch_es/diff.rb', line 369

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

  # Binary search.
  # Performance analysis: https://neil.fraser.name/news/2007/10/09/
  pointermin = 0
  pointermax = [text1.length, text2.length].min
  pointermid = pointermax
  pointerstart = 0
  while pointermin < pointermid
    if JsString.substring(text1, pointerstart, pointermid) ==
       JsString.substring(text2, pointerstart, pointermid)
      pointermin = pointermid
      pointerstart = pointermin
    else
      pointermax = pointermid
    end
    pointermid = (pointermax - pointermin) / 2 + pointermin
  end
  pointermid
end

.diff_common_suffix(text1, text2) ⇒ Object

Determine the common suffix of two strings.



393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
 
# File 'lib/diff_match_patch_es/diff.rb', line 393

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

  # Binary search.
  # Performance analysis: https://neil.fraser.name/news/2007/10/09/
  pointermin = 0
  pointermax = [text1.length, text2.length].min
  pointermid = pointermax
  pointerend = 0
  while pointermin < pointermid
    if JsString.substring(text1, text1.length - pointermid, text1.length - pointerend) ==
       JsString.substring(text2, text2.length - pointermid, text2.length - pointerend)
      pointermin = pointermid
      pointerend = pointermin
    else
      pointermax = pointermid
    end
    pointermid = (pointermax - pointermin) / 2 + pointermin
  end
  pointermid
end

.diff_compute(text1, text2, options, checklines, deadline) ⇒ Object

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



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 71

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

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

  longtext = text1.length > text2.length ? text1 : text2
  shorttext = text1.length > text2.length ? text2 : text1
  i = longtext.index(shorttext)
  unless i.nil?
    # Shorter text is inside the longer text (speedup).
    diffs = [
      create_diff(DIFF_INSERT, JsString.substring(longtext, 0, i)),
      create_diff(DIFF_EQUAL, shorttext),
      create_diff(DIFF_INSERT, JsString.substring(longtext, i + shorttext.length)),
    ]
    # Swap insertions for deletions if diff is reversed.
    diffs[0][0] = diffs[2][0] = DIFF_DELETE if text1.length > text2.length

    return diffs
  end

  if shorttext.length == 1
    # Single character string.
    # After the previous speedup, the character can't be an equality.
    return [create_diff(DIFF_DELETE, text1), create_diff(DIFF_INSERT, text2)]
  end

  # Check to see if the problem can be split in two.
  hm = diff_half_match(text1, text2, options)
  if hm
    # 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, options, checklines, deadline)
    diffs_b = diff_main(text1_b, text2_b, options, checklines, deadline)
    # Merge the results.
    return diffs_a.concat([create_diff(DIFF_EQUAL, mid_common)], diffs_b)
  end

  return diff_line_mode(text1, text2, options, deadline) if checklines && text1.length > 100 && text2.length > 100

  diff_bisect(text1, text2, options, deadline)
end

.diff_from_delta(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.



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
1047
1048
1049
 
# File 'lib/diff_match_patch_es/diff.rb', line 1011

def diff_from_delta(text1, delta)
  diffs = []
  pointer = 0 # Cursor in text1
  tokens = delta.split("\t", -1)
  tokens.each do |token|
    # Each token begins with a one character parameter which specifies the
    # operation of this token (delete, insert, equality).
    param = JsString.substring(token, 1)
    case JsString.char_at(token, 0)
    when '+'
      begin
        diffs << create_diff(DIFF_INSERT, JsString.decode_uri(param))
      rescue JsString::UriError
        # Malformed URI sequence.
        raise Error, "Illegal escape in diff_fromDelta: #{param}"
      end
    when '-', '='
      n = JsString.parse_int(param)
      raise Error, "Invalid number in diff_fromDelta: #{param}" if n.nil? || n.negative?

      text = JsString.substring(text1, pointer, pointer + n)
      pointer += n
      if token[0] == '='
        diffs << create_diff(DIFF_EQUAL, text)
      else
        diffs << create_diff(DIFF_DELETE, text)
      end
    else
      # Blank tokens are ok (from a trailing \t).
      # Anything else is an error.
      raise Error, "Invalid diff operation in diff_fromDelta: #{token}" unless token.empty?
    end
  end
  if pointer != text1.length
    raise Error, "Delta length (#{pointer}) does not equal source text length (#{text1.length})."
  end

  diffs
end

.diff_half_match(text1, text2, options) ⇒ 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.



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 455

def diff_half_match(text1, text2, options)
  if options.diff_timeout <= 0
    # Don't risk returning a non-optimal diff if we have unlimited time.
    return nil
  end
  longtext = text1.length > text2.length ? text1 : text2
  shorttext = text1.length > text2.length ? text2 : text1
  return nil if longtext.length < 4 || shorttext.length * 2 < longtext.length # Pointless.

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

  if !hm1 && !hm2
    return nil
  elsif !hm2
    hm = hm1
  elsif !hm1
    hm = 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 = hm
  else
    text2_a, text2_b, text1_a, text1_b = hm
  end
  mid_common = hm[4]
  [text1_a, text1_b, text2_a, text2_b, mid_common]
end

.diff_half_match_i(longtext, shorttext, i) ⇒ Object

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



492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
 
# File 'lib/diff_match_patch_es/diff.rb', line 492

def diff_half_match_i(longtext, shorttext, i)
  # Start with a 1/4 length substring at position i as a seed.
  seed = JsString.substring(longtext, i, i + (longtext.length / 4))
  j = -1
  best_common = ''
  best_longtext_a = best_longtext_b = best_shorttext_a = best_shorttext_b = nil
  while (j = JsString.index_of(shorttext, seed, j + 1)) != -1
    prefix_length = diff_common_prefix(JsString.substring(longtext, i), JsString.substring(shorttext, j))
    suffix_length = diff_common_suffix(JsString.substring(longtext, 0, i), JsString.substring(shorttext, 0, j))
    next unless best_common.length < suffix_length + prefix_length

    best_common = JsString.substring(shorttext, j - suffix_length, j) +
                  JsString.substring(shorttext, j, j + prefix_length)
    best_longtext_a = JsString.substring(longtext, 0, i - suffix_length)
    best_longtext_b = JsString.substring(longtext, i + prefix_length)
    best_shorttext_a = JsString.substring(shorttext, 0, j - suffix_length)
    best_shorttext_b = JsString.substring(shorttext, j + prefix_length)
  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.



974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
 
# File 'lib/diff_match_patch_es/diff.rb', line 974

def diff_levenshtein(diffs)
  levenshtein = 0
  insertions = 0
  deletions = 0
  diffs.each do |(op, data)|
    case op
    when DIFF_INSERT
      insertions += data.length
    when DIFF_DELETE
      deletions += data.length
    when DIFF_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_line_mode(text1, text2, options, deadline) ⇒ Object

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



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 119

def diff_line_mode(text1, text2, options, deadline)
  # Scan the text on a line-by-line basis first.
  a = diff_lines_to_chars(text1, text2)
  text1 = a[:chars1]
  text2 = a[:chars2]
  linearray = a[:line_array]

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

  # Convert the diff back to original text.
  diff_chars_to_lines(diffs, linearray)
  # Eliminate freak matches (e.g. blank lines)
  diff_cleanup_semantic(diffs)

  # Re-diff any replacement blocks, this time character-by-character.
  # Add a dummy entry at the end.
  diffs.push(create_diff(DIFF_EQUAL, ''))
  pointer = 0
  count_delete = 0
  count_insert = 0
  text_delete = +''
  text_insert = +''
  while pointer < diffs.length
    case diffs[pointer][0]
    when DIFF_INSERT
      count_insert += 1
      text_insert += diffs[pointer][1]
    when DIFF_DELETE
      count_delete += 1
      text_delete += diffs[pointer][1]
    when DIFF_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.
        diffs.slice!(pointer - count_delete - count_insert, count_delete + count_insert)
        pointer = pointer - count_delete - count_insert
        sub_diff = diff_main(text_delete, text_insert, options, false, deadline)
        (sub_diff.length - 1).downto(0) do |j|
          diffs.insert(pointer, sub_diff[j])
        end
        pointer += sub_diff.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.

  diffs
end

.diff_lines_to_chars(text1, text2) ⇒ Object

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



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 308

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

  # Allocate 2/3rds of the space for text1, the rest for text2.
  max_lines = 40_000

  # '\x00' is a valid character, but various debuggers don't like it.
  # So we'll insert a junk entry to avoid generating a null character.
  line_array[0] = ''

  munge = lambda do |text|
    chars = +''
    # Walk the text, pulling out a substring for each line.
    line_start = 0
    line_end = -1
    line_array_length = line_array.length
    while line_end < text.length - 1
      line_end = text.index("\n", line_start) || -1
      line_end = text.length - 1 if line_end == -1

      line = JsString.substring(text, line_start, line_end + 1)

      if line_hash.key?(line)
        chars << line_char_for(line_hash[line])
      else
        if line_array_length == max_lines
          # Bail out at 65535 because
          # String.fromCharCode(65536) == String.fromCharCode(0)
          line = JsString.substring(text, line_start)
          line_end = text.length
        end
        chars << line_char_for(line_array_length)
        line_hash[line] = line_array_length
        line_array[line_array_length] = line
        line_array_length += 1
      end
      line_start = line_end + 1
    end
    chars
  end

  chars1 = munge.call(text1)
  max_lines = 65_535
  chars2 = munge.call(text2)
  { chars1: chars1, chars2: chars2, line_array: line_array }
end

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

Find the differences between two texts.

Raises:



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 27

def diff_main(text1, text2, options = nil, checklines = true, deadline = nil)
  resolved = resolve_options(options)

  if deadline.nil?
    deadline = if resolved.diff_timeout <= 0
                 Float::MAX
               else
                 now_ms + resolved.diff_timeout * 1000
               end
  end

  raise Error, 'Null input. (diff_main)' if text1.nil? || text2.nil?

  if text1 == text2
    return [create_diff(DIFF_EQUAL, text1)] unless text1.empty?

    return []
  end

  # Trim off common prefix (speedup).
  commonlength = diff_common_prefix(text1, text2)
  commonprefix = JsString.substring(text1, 0, commonlength)
  text1 = JsString.substring(text1, commonlength)
  text2 = JsString.substring(text2, commonlength)

  # Trim off common suffix (speedup).
  commonlength = diff_common_suffix(text1, text2)
  commonsuffix = JsString.substring(text1, text1.length - commonlength)
  text1 = JsString.substring(text1, 0, text1.length - commonlength)
  text2 = JsString.substring(text2, 0, text2.length - commonlength)

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

  # Restore the prefix and suffix.
  diffs.unshift(create_diff(DIFF_EQUAL, commonprefix)) unless commonprefix.empty?
  diffs.push(create_diff(DIFF_EQUAL, commonsuffix)) unless commonsuffix.empty?

  diff_cleanup_merge(diffs)
  diffs
end

.diff_pretty_html(diffs) ⇒ Object

Convert a diff array into a pretty HTML report.



942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
 
# File 'lib/diff_match_patch_es/diff.rb', line 942

def diff_pretty_html(diffs)
  html = +''
  diffs.each do |(op, data)|
    text = data.gsub('&', '&amp;').gsub('<', '&lt;').gsub('>', '&gt;').gsub("\n", '&para;<br>')
    case op
    when DIFF_INSERT
      html << %(<ins style="background:#e6ffe6;">#{text}</ins>)
    when DIFF_DELETE
      html << %(<del style="background:#ffe6e6;">#{text}</del>)
    when DIFF_EQUAL
      html << "<span>#{text}</span>"
    end
  end
  html
end

.diff_text1(diffs) ⇒ Object

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



959
960
961
962
963
 
# File 'lib/diff_match_patch_es/diff.rb', line 959

def diff_text1(diffs)
  text = +''
  diffs.each { |(op, data)| text << data if op != DIFF_INSERT }
  text
end

.diff_text2(diffs) ⇒ Object

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



966
967
968
969
970
 
# File 'lib/diff_match_patch_es/diff.rb', line 966

def diff_text2(diffs)
  text = +''
  diffs.each { |(op, data)| text << data if op != DIFF_DELETE }
  text
end

.diff_to_delta(diffs) ⇒ Object

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



998
999
1000
1001
1002
1003
1004
1005
1006
1007
 
# File 'lib/diff_match_patch_es/diff.rb', line 998

def diff_to_delta(diffs)
  text = diffs.map do |(op, data)|
    case op
    when DIFF_INSERT then "+#{JsString.encode_uri(data)}"
    when DIFF_DELETE then "-#{data.length}"
    when DIFF_EQUAL then "=#{data.length}"
    end
  end
  text.join("\t").gsub('%20', ' ')
end

.diff_x_index(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



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
 
# File 'lib/diff_match_patch_es/diff.rb', line 915

def diff_x_index(diffs, loc)
  chars1 = 0
  chars2 = 0
  last_chars1 = 0
  last_chars2 = 0
  x = 0
  while x < diffs.length
    if diffs[x][0] != DIFF_INSERT # Equality or deletion.
      chars1 += diffs[x][1].length
    end
    if diffs[x][0] != DIFF_DELETE # Equality or insertion.
      chars2 += diffs[x][1].length
    end
    break if chars1 > loc # Overshot the location.

    last_chars1 = chars1
    last_chars2 = chars2
    x += 1
  end
  # Was the location deleted?
  return last_chars2 if diffs.length != x && diffs[x][0] == DIFF_DELETE

  # Add the remaining character length.
  last_chars2 + (loc - last_chars1)
end

.line_char_for(index) ⇒ Object 



296
297
298
299
 
# File 'lib/diff_match_patch_es/diff.rb', line 296

def line_char_for(index)
  codepoint = index < 0xD800 ? index : index + LINE_INDEX_SURROGATE_SHIFT
  codepoint.chr(Encoding::UTF_8)
end

.line_index_for(char) ⇒ Object 



301
302
303
304
 
# File 'lib/diff_match_patch_es/diff.rb', line 301

def line_index_for(char)
  codepoint = char.ord
  codepoint < 0xD800 ? codepoint : codepoint - LINE_INDEX_SURROGATE_SHIFT
end

.match(text, pattern, loc, options = nil) ⇒ Object 



44
45
46
 
# File 'lib/diff_match_patch_es.rb', line 44

def match(text, pattern, loc, options = nil)
  match_main(text, pattern, loc, options)
end

.match_alphabet(pattern) ⇒ Object

Initialise the alphabet for the Bitap algorithm.



133
134
135
136
137
138
139
140
 
# File 'lib/diff_match_patch_es/match.rb', line 133

def match_alphabet(pattern)
  s = {}
  pattern.each_char { |ch| s[ch] = 0 }
  pattern.length.times do |i|
    s[pattern[i]] |= (1 << (pattern.length - i - 1)) & MASK32
  end
  s
end

.match_bitap(text, pattern, loc, options = nil) ⇒ Object

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

Raises:



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
 
# File 'lib/diff_match_patch_es/match.rb', line 35

def match_bitap(text, pattern, loc, options = nil)
  resolved = resolve_options(options)

  raise Error, 'Pattern too long for this browser.' if pattern.length > resolved.match_max_bits

  # Initialise the alphabet.
  s = match_alphabet(pattern)

  # Compute and return the score for a match with e errors and x location.
  # (0.0 = good, 1.0 = bad)
  bitap_score = lambda do |e, x|
    accuracy = e.fdiv(pattern.length)
    proximity = (loc - x).abs
    if resolved.match_distance.zero?
      # Dodge divide by zero error.
      return proximity.zero? ? accuracy : 1.0
    end
    accuracy + proximity.fdiv(resolved.match_distance)
  end

  # Highest score beyond which we give up.
  score_threshold = resolved.match_threshold
  # Is there a nearby exact match? (speedup)
  best_loc = JsString.index_of(text, pattern, loc)
  if best_loc != -1
    score_threshold = [bitap_score.call(0, best_loc), score_threshold].min
    # What about in the other direction? (speedup)
    best_loc = JsString.last_index_of(text, pattern, loc + pattern.length)
    score_threshold = [bitap_score.call(0, best_loc), score_threshold].min if best_loc != -1
  end

  # Initialise the bit arrays.
  matchmask = (1 << (pattern.length - 1)) & MASK32
  best_loc = -1

  bin_max = pattern.length + text.length
  last_rd = []
  d = 0
  while d < pattern.length
    # 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 bitap_score.call(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) & MASK32
    j = finish
    while j >= start
      char_match = s[JsString.char_at(text, j - 1)] || 0
      rd[j] = if d.zero? # First pass: exact match.
                (((rd[j + 1] << 1) | 1) & char_match) & MASK32
              else # Subsequent passes: fuzzy match.
                ((((rd[j + 1] << 1) | 1) & char_match) |
                  ((((last_rd[j + 1] || 0) | (last_rd[j] || 0)) << 1) | 1) |
                  (last_rd[j + 1] || 0)) & MASK32
              end
      if (rd[j] & matchmask) != 0
        score = bitap_score.call(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
      j -= 1
    end
    # No hope for a (better) match at greater error levels.
    break if bitap_score.call(d + 1, loc) > score_threshold

    last_rd = rd
    d += 1
  end
  best_loc
end

.match_main(text, pattern, loc, options = nil) ⇒ Object

Locate the best instance of 'pattern' in 'text' near 'loc'. Returns the best match index or -1.

Raises:



13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# File 'lib/diff_match_patch_es/match.rb', line 13

def match_main(text, pattern, loc, options = nil)
  # Check for null inputs.
  raise Error, 'Null input. (match_main)' if text.nil? || pattern.nil? || loc.nil?

  loc = loc.clamp(0, text.length)
  if text == pattern
    # Shortcut (potentially not guaranteed by the algorithm)
    0
  elsif text.empty?
    # Nothing to match.
    -1
  elsif JsString.substring(text, loc, 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, options)
  end
end

.now_ms ⇒ Object 



22
23
24
 
# File 'lib/diff_match_patch_es/diff.rb', line 22

def now_ms
  Process.clock_gettime(Process::CLOCK_MONOTONIC, :float_millisecond)
end

.patch(a, opt_b = nil, opt_c = nil, options = nil) ⇒ Object 



48
49
50
 
# File 'lib/diff_match_patch_es.rb', line 48

def patch(a, opt_b = nil, opt_c = nil, options = nil)
  patch_make(a, opt_b, opt_c, options)
end

.patch_add_context(patch, text, options) ⇒ Object

Increase the context until it is unique, but don't let the pattern expand beyond match_max_bits.

Raises:



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
 
# File 'lib/diff_match_patch_es/patch.rb', line 66

def patch_add_context(patch, text, options)
  return if text.empty?

  raise Error, 'patch not initialized' if patch.start2.nil?

  resolved = resolve_options(options)
  match_max_bits = resolved.match_max_bits
  patch_margin = resolved.patch_margin

  pattern = JsString.substring(text, patch.start2, 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 JsString.index_of(text, pattern) != JsString.last_index_of(text, pattern, text.length) &&
        pattern.length < match_max_bits - patch_margin - patch_margin
    padding += patch_margin
    pattern = JsString.substring(text, patch.start2 - padding, patch.start2 + patch.length1 + padding)
  end
  # Add one chunk for good luck.
  padding += patch_margin

  # Add the prefix.
  prefix = JsString.substring(text, patch.start2 - padding, patch.start2)
  patch.diffs.unshift(create_diff(DIFF_EQUAL, prefix)) unless prefix.empty?

  # Add the suffix.
  suffix = JsString.substring(text, patch.start2 + patch.length1, patch.start2 + patch.length1 + padding)
  patch.diffs.push(create_diff(DIFF_EQUAL, suffix)) unless suffix.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
  nil
end

.patch_add_padding(patches, options = nil) ⇒ Object

Add some padding on text start and end so that edges can match something. Intended to be called only from within patch_apply. Returns the padding string added to each side.



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
 
# File 'lib/diff_match_patch_es/patch.rb', line 331

def patch_add_padding(patches, options = nil)
  padding_length = resolve_options(options).patch_margin
  null_padding = +''
  (1..padding_length).each { |x| null_padding << x.chr(Encoding::UTF_8) }

  # 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[0]
  diffs = patch.diffs
  if diffs.empty? || diffs[0][0] != DIFF_EQUAL
    # Add null_padding equality.
    diffs.unshift(create_diff(DIFF_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[0][1].length
    # Grow first equality.
    extra_length = padding_length - diffs[0][1].length
    diffs[0][1] = JsString.substring(null_padding, diffs[0][1].length) + diffs[0][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[patches.length - 1]
  diffs = patch.diffs
  if diffs.empty? || diffs[diffs.length - 1][0] != DIFF_EQUAL
    # Add null_padding equality.
    diffs.push(create_diff(DIFF_EQUAL, null_padding))
    patch.length1 += padding_length
    patch.length2 += padding_length
  elsif padding_length > diffs[diffs.length - 1][1].length
    # Grow last equality.
    extra_length = padding_length - diffs[diffs.length - 1][1].length
    diffs[diffs.length - 1][1] += JsString.substring(null_padding, 0, extra_length)
    patch.length1 += extra_length
    patch.length2 += extra_length
  end

  null_padding
end

.patch_apply(patches, text, options = nil) ⇒ 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.



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
 
# File 'lib/diff_match_patch_es/patch.rb', line 231

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

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

  resolved = resolve_options(options)
  null_padding = patch_add_padding(patches, resolved)
  text = null_padding + text + null_padding

  patch_split_max(patches, resolved)
  # 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 > resolved.match_max_bits
      # patch_split_max will only provide an oversized pattern in the case
      # of a monster delete.
      start_loc = match_main(
        text,
        JsString.substring(text1, 0, resolved.match_max_bits),
        expected_loc,
        resolved,
      )
      if start_loc != -1
        end_loc = match_main(
          text,
          JsString.substring(text1, text1.length - resolved.match_max_bits),
          expected_loc + text1.length - resolved.match_max_bits,
          resolved,
        )
        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, resolved)
    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 = if end_loc == -1
                JsString.substring(text, start_loc, start_loc + text1.length)
              else
                JsString.substring(text, start_loc, end_loc + resolved.match_max_bits)
              end

      if text1 == text2
        # Perfect match, just shove the replacement text in.
        text = JsString.substring(text, 0, start_loc) +
               diff_text2(patch.diffs) +
               JsString.substring(text, start_loc + text1.length)
      else
        # Imperfect match.  Run a diff to get a framework of equivalent
        # indices.
        diffs = diff_main(text1, text2, resolved, false)
        if text1.length > resolved.match_max_bits &&
           diff_levenshtein(diffs).fdiv(text1.length) > resolved.patch_delete_threshold
          # The end points match, but the content is unacceptably bad.
          results[x] = false
        else
          diff_cleanup_semantic_lossless(diffs)
          index1 = 0
          index2 = 0
          patch.diffs.each do |mod|
            index2 = diff_x_index(diffs, index1) if mod[0] != DIFF_EQUAL
            if mod[0] == DIFF_INSERT # Insertion
              text = JsString.substring(text, 0, start_loc + index2) + mod[1] +
                     JsString.substring(text, start_loc + index2)
            elsif mod[0] == DIFF_DELETE # Deletion
              text = JsString.substring(text, 0, start_loc + index2) +
                     JsString.substring(text, start_loc + diff_x_index(diffs, index1 + mod[1].length))
            end
            index1 += mod[1].length if mod[0] != DIFF_DELETE
          end
        end
      end
    end
  end
  # Strip the padding off.
  text = JsString.substring(text, null_padding.length, text.length - null_padding.length)
  [text, results]
end

.patch_deep_copy(patches) ⇒ Object

Given an array of patches, return another array that is identical.



217
218
219
220
221
222
223
224
225
226
227
 
# File 'lib/diff_match_patch_es/patch.rb', line 217

def patch_deep_copy(patches)
  patches.map do |patch|
    patch_copy = Patch.new
    patch_copy.diffs = patch.diffs.map { |(op, text)| create_diff(op, text) }
    patch_copy.start1 = patch.start1
    patch_copy.start2 = patch.start2
    patch_copy.length1 = patch.length1
    patch_copy.length2 = patch.length2
    patch_copy
  end
end

.patch_from_text(textline) ⇒ Object

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



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
 
# File 'lib/diff_match_patch_es/patch.rb', line 481

def patch_from_text(textline)
  patches = []
  return patches if textline.nil? || textline.empty?

  text = textline.split("\n", -1)
  text_pointer = 0
  patch_header = /\A@@ -(\d+),?(\d*) \+(\d+),?(\d*) @@\z/
  while text_pointer < text.length
    m = patch_header.match(text[text_pointer])
    raise Error, "Invalid patch string: #{text[text_pointer]}" unless m

    patch = Patch.new
    patches.push(patch)
    patch.start1 = m[1].to_i
    if m[2] == ''
      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] == ''
      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
      sign = JsString.char_at(text[text_pointer], 0)
      line = ''
      begin
        line = JsString.decode_uri(JsString.substring(text[text_pointer], 1))
      rescue JsString::UriError
        # Malformed URI sequence.  (The reference implementation reports the
        # pre-assignment value of `line`, which is always empty.)
        raise Error, 'Illegal escape in patch_fromText: '
      end
      case sign
      when '-'
        # Deletion.
        patch.diffs.push(create_diff(DIFF_DELETE, line))
      when '+'
        # Insertion.
        patch.diffs.push(create_diff(DIFF_INSERT, line))
      when ' '
        # Minor equality.
        patch.diffs.push(create_diff(DIFF_EQUAL, line))
      when '@'
        # Start of next patch.
        break
      when ''
        # Blank line?  Whatever.
      else
        # WTF?
        raise Error, "Invalid patch mode \"#{sign}\" in: #{line}"
      end
      text_pointer += 1
    end
  end
  patches
end

.patch_make(a, opt_b = nil, opt_c = nil, options = nil) ⇒ 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



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
 
# File 'lib/diff_match_patch_es/patch.rb', line 113

def patch_make(a, opt_b = nil, opt_c = nil, options = nil)
  resolved = resolve_options(options)

  if a.is_a?(String) && opt_b.is_a?(String) && opt_c.nil?
    # Method 1: text1, text2
    # Compute diffs from text1 and text2.
    text1 = a
    diffs = diff_main(text1, opt_b, resolved, true)
    if diffs.length > 2
      diff_cleanup_semantic(diffs)
      diff_cleanup_efficiency(diffs, resolved)
    end
  elsif a.is_a?(Array) && opt_b.nil? && opt_c.nil?
    # Method 2: diffs
    # Compute text1 from diffs.
    diffs = a
    text1 = diff_text1(diffs)
  elsif a.is_a?(String) && opt_b.is_a?(Array) && opt_c.nil?
    # Method 3: text1, diffs
    text1 = a
    diffs = opt_b
  elsif a.is_a?(String) && opt_b.is_a?(String) && opt_c.is_a?(Array)
    # Method 4: text1, text2, diffs
    # text2 is not used.
    text1 = a
    diffs = opt_c
  else
    raise Error, 'Unknown call format to patch_make.'
  end

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

  patches = []
  patch = Patch.new
  patch_diff_length = 0 # Keeping our own length var is faster in JS.
  char_count1 = 0 # Number of characters into the text1 string.
  char_count2 = 0 # Number of characters into the text2 string.
  # Start with text1 (prepatch_text) and apply the diffs until we arrive at
  # text2 (postpatch_text).  We recreate the patches one by one to determine
  # context info.
  prepatch_text = text1
  postpatch_text = text1
  diffs.each_with_index do |diff, x|
    diff_type = diff[0]
    diff_text = diff[1]

    if patch_diff_length.zero? && diff_type != DIFF_EQUAL
      # A new patch starts here.
      patch.start1 = char_count1
      patch.start2 = char_count2
    end

    case diff_type
    when DIFF_INSERT
      patch.diffs[patch_diff_length] = diff
      patch_diff_length += 1
      patch.length2 += diff_text.length
      postpatch_text = JsString.substring(postpatch_text, 0, char_count2) + diff_text +
                       JsString.substring(postpatch_text, char_count2)
    when DIFF_DELETE
      patch.length1 += diff_text.length
      patch.diffs[patch_diff_length] = diff
      patch_diff_length += 1
      postpatch_text = JsString.substring(postpatch_text, 0, char_count2) +
                       JsString.substring(postpatch_text, char_count2 + diff_text.length)
    when DIFF_EQUAL
      if diff_text.length <= 2 * resolved.patch_margin &&
         patch_diff_length.positive? && diffs.length != x + 1
        # Small equality inside a patch.
        patch.diffs[patch_diff_length] = diff
        patch_diff_length += 1
        patch.length1 += diff_text.length
        patch.length2 += diff_text.length
      elsif diff_text.length >= 2 * resolved.patch_margin
        # Time for a new patch.
        if patch_diff_length.positive?
          patch_add_context(patch, prepatch_text, resolved)
          patches.push(patch)
          patch = Patch.new
          patch_diff_length = 0
          # Unlike Unidiff, our patch lists have a rolling context.
          # https://github.com/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.
    char_count1 += diff_text.length if diff_type != DIFF_INSERT
    char_count2 += diff_text.length if diff_type != DIFF_DELETE
  end
  # Pick up the leftover patch if not empty.
  if patch_diff_length.positive?
    patch_add_context(patch, prepatch_text, resolved)
    patches.push(patch)
  end

  patches
end

.patch_split_max(patches, options = nil) ⇒ Object

Look through the patches and break up any which are longer than the maximum limit of the match algorithm. Intended to be called only from within patch_apply.



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
 
# File 'lib/diff_match_patch_es/patch.rb', line 384

def patch_split_max(patches, options = nil)
  resolved = resolve_options(options)
  x = 0
  while x < patches.length
    if patches[x].length1 <= resolved.match_max_bits
      x += 1
      next
    end

    bigpatch = patches[x]
    # Remove the big old patch.
    patches.delete_at(x)
    x -= 1
    start1 = bigpatch.start1
    start2 = bigpatch.start2
    precontext = ''
    until bigpatch.diffs.empty?
      # Create one of several smaller patches.
      patch = Patch.new
      empty = true
      patch.start1 = start1 - precontext.length
      patch.start2 = start2 - precontext.length
      unless precontext.empty?
        patch.length1 = patch.length2 = precontext.length
        patch.diffs.push(create_diff(DIFF_EQUAL, precontext))
      end
      while !bigpatch.diffs.empty? &&
            patch.length1 < resolved.match_max_bits - resolved.patch_margin
        diff_type = bigpatch.diffs[0][0]
        diff_text = bigpatch.diffs[0][1]
        if diff_type == DIFF_INSERT
          # Insertions are harmless.
          patch.length2 += diff_text.length
          start2 += diff_text.length
          patch.diffs.push(bigpatch.diffs.shift)
          empty = false
        elsif diff_type == DIFF_DELETE && patch.diffs.length == 1 &&
              patch.diffs[0][0] == DIFF_EQUAL &&
              diff_text.length > 2 * resolved.match_max_bits
          # This is a large deletion.  Let it pass in one chunk.
          patch.length1 += diff_text.length
          start1 += diff_text.length
          empty = false
          patch.diffs.push(create_diff(diff_type, diff_text))
          bigpatch.diffs.shift
        else
          # Deletion or equality.  Only take as much as we can stomach.
          diff_text = JsString.substring(
            diff_text, 0, resolved.match_max_bits - patch.length1 - resolved.patch_margin
          )
          patch.length1 += diff_text.length
          start1 += diff_text.length
          if diff_type == DIFF_EQUAL
            patch.length2 += diff_text.length
            start2 += diff_text.length
          else
            empty = false
          end
          patch.diffs.push(create_diff(diff_type, diff_text))
          if diff_text == bigpatch.diffs[0][1]
            bigpatch.diffs.shift
          else
            bigpatch.diffs[0][1] = JsString.substring(bigpatch.diffs[0][1], diff_text.length)
          end
        end
      end
      # Compute the head context for the next patch.
      precontext = diff_text2(patch.diffs)
      precontext = JsString.substring(precontext, precontext.length - resolved.patch_margin)
      # Append the end context for this patch.
      postcontext = JsString.substring(diff_text1(bigpatch.diffs), 0, resolved.patch_margin)
      unless postcontext.empty?
        patch.length1 += postcontext.length
        patch.length2 += postcontext.length
        if !patch.diffs.empty? && patch.diffs[patch.diffs.length - 1][0] == DIFF_EQUAL
          patch.diffs[patch.diffs.length - 1][1] += postcontext
        else
          patch.diffs.push(create_diff(DIFF_EQUAL, postcontext))
        end
      end
      unless empty
        x += 1
        patches.insert(x, patch)
      end
    end
    x += 1
  end
  nil
end

.patch_to_text(patches) ⇒ Object

Take a list of patches and return a textual representation.



475
476
477
 
# File 'lib/diff_match_patch_es/patch.rb', line 475

def patch_to_text(patches)
  patches.map(&:to_s).join
end

.resolve_options(options = nil) ⇒ Object

Accepts nil, a Hash of overrides, or an already-resolved Options.



49
50
51
52
53
54
55
56
57
 
# File 'lib/diff_match_patch_es/options.rb', line 49

def resolve_options(options = nil)
  case options
  when Options then options
  when nil then Options.new
  when Hash then Options.new(**options)
  else
    raise ArgumentError, "Unsupported options: #{options.inspect}"
  end
end

Instance Method Details

#self?.create_diff ⇒ diff

Parameters:

  • operation (op)
  • text (String)

Returns:



23
 
# File 'sig/diff_match_patch_es/diff.rbs', line 23

def self?.create_diff: (op operation, String text) -> diff

#self?.create_patch ⇒ Patch

Returns:



23
 
# File 'sig/diff_match_patch_es/patch.rbs', line 23

def self?.create_patch: () -> Patch

#self?.diff ⇒ Array[diff]

Short aliases mirroring the diff/match/patch exports of index.ts.

Parameters:

  • text1 (String)
  • text2 (String)
  • options (options_arg)
  • checklines (Boolean)
  • deadline (Numeric, nil)

Returns:



26
 
# File 'sig/diff_match_patch_es.rbs', line 26

def self?.diff: (String text1, String text2, ?options_arg options, ?bool checklines, ?Numeric? deadline) -> Array[diff]

#self?.diff_bisect ⇒ Array[diff]

Find the 'middle snake' of a diff, split the problem in two and return the recursively constructed diff.

Parameters:

  • text1 (String)
  • text2 (String)
  • options (Options)
  • deadline (Numeric)

Returns:



40
 
# File 'sig/diff_match_patch_es/diff.rbs', line 40

def self?.diff_bisect: (String text1, String text2, Options options, Numeric deadline) -> Array[diff]

#self?.diff_bisect_split ⇒ Array[diff]

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

Parameters:

  • text1 (String)
  • text2 (String)
  • options (Options)
  • x (Integer)
  • y (Integer)
  • deadline (Numeric)

Returns:



43
 
# File 'sig/diff_match_patch_es/diff.rbs', line 43

def self?.diff_bisect_split: (String text1, String text2, Options options, Integer x, Integer y, Numeric deadline) -> Array[diff]

#self?.diff_chars_to_lines ⇒ nil

Rehydrate the text in a diff from a string of line placeholders to real lines of text. Mutates diffs in place.

Parameters:

  • diffs (Array[diff])
  • line_array (Array[String])

Returns:

  • (nil) 


54
 
# File 'sig/diff_match_patch_es/diff.rbs', line 54

def self?.diff_chars_to_lines: (Array[diff] diffs, Array[String] line_array) -> nil

#self?.diff_cleanup_efficiency ⇒ nil

Reduce the number of edits by eliminating operationally trivial equalities. Mutates diffs in place.

Parameters:

  • diffs (Array[diff])
  • options (options_arg)

Returns:

  • (nil) 


84
 
# File 'sig/diff_match_patch_es/diff.rbs', line 84

def self?.diff_cleanup_efficiency: (Array[diff] diffs, ?options_arg options) -> nil

#self?.diff_cleanup_merge ⇒ nil

Reorder and merge like edit sections. Merge equalities. Mutates diffs.

Parameters:

  • diffs (Array[diff])

Returns:

  • (nil) 


87
 
# File 'sig/diff_match_patch_es/diff.rbs', line 87

def self?.diff_cleanup_merge: (Array[diff] diffs) -> nil

#self?.diff_cleanup_semantic ⇒ nil

Reduce the number of edits by eliminating semantically trivial equalities. Mutates diffs in place.

Parameters:

  • diffs (Array[diff])

Returns:

  • (nil) 


72
 
# File 'sig/diff_match_patch_es/diff.rbs', line 72

def self?.diff_cleanup_semantic: (Array[diff] diffs) -> nil

#self?.diff_cleanup_semantic_lossless ⇒ nil

Look for single edits surrounded on both sides by equalities which can be shifted sideways to align the edit to a word boundary. Mutates diffs.

Parameters:

  • diffs (Array[diff])

Returns:

  • (nil) 


80
 
# File 'sig/diff_match_patch_es/diff.rbs', line 80

def self?.diff_cleanup_semantic_lossless: (Array[diff] diffs) -> nil

#self?.diff_cleanup_semantic_score ⇒ Integer

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

Parameters:

  • one (String)
  • two (String)

Returns:

  • (Integer) 


76
 
# File 'sig/diff_match_patch_es/diff.rbs', line 76

def self?.diff_cleanup_semantic_score: (String one, String two) -> Integer

#self?.diff_common_overlap ⇒ Integer

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

Parameters:

  • text1 (String)
  • text2 (String)

Returns:

  • (Integer) 


63
 
# File 'sig/diff_match_patch_es/diff.rbs', line 63

def self?.diff_common_overlap: (String text1, String text2) -> Integer

#self?.diff_common_prefix ⇒ Integer

Determine the common prefix of two strings.

Parameters:

  • text1 (String)
  • text2 (String)

Returns:

  • (Integer) 


57
 
# File 'sig/diff_match_patch_es/diff.rbs', line 57

def self?.diff_common_prefix: (String text1, String text2) -> Integer

#self?.diff_common_suffix ⇒ Integer

Determine the common suffix of two strings.

Parameters:

  • text1 (String)
  • text2 (String)

Returns:

  • (Integer) 


60
 
# File 'sig/diff_match_patch_es/diff.rbs', line 60

def self?.diff_common_suffix: (String text1, String text2) -> Integer

#self?.diff_compute ⇒ Array[diff]

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

Parameters:

  • text1 (String)
  • text2 (String)
  • options (Options)
  • checklines (Boolean)
  • deadline (Numeric)

Returns:



32
 
# File 'sig/diff_match_patch_es/diff.rbs', line 32

def self?.diff_compute: (String text1, String text2, Options options, bool checklines, Numeric deadline) -> Array[diff]

#self?.diff_from_delta ⇒ Array[diff]

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

Parameters:

  • text1 (String)
  • delta (String)

Returns:



112
 
# File 'sig/diff_match_patch_es/diff.rbs', line 112

def self?.diff_from_delta: (String text1, String delta) -> Array[diff]

#self?.diff_half_match ⇒ half_match?

Do the two texts share a substring which is at least half the length of the longer text?

Parameters:

  • text1 (String)
  • text2 (String)
  • options (Options)

Returns:

  • (half_match, nil) 


66
 
# File 'sig/diff_match_patch_es/diff.rbs', line 66

def self?.diff_half_match: (String text1, String text2, Options options) -> half_match?

#self?.diff_half_match_i ⇒ half_match?

Parameters:

  • longtext (String)
  • shorttext (String)
  • i (Integer)

Returns:

  • (half_match, nil) 


68
 
# File 'sig/diff_match_patch_es/diff.rbs', line 68

def self?.diff_half_match_i: (String longtext, String shorttext, Integer i) -> half_match?

#self?.diff_levenshtein ⇒ Integer

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

Parameters:

  • diffs (Array[diff])

Returns:

  • (Integer) 


104
 
# File 'sig/diff_match_patch_es/diff.rbs', line 104

def self?.diff_levenshtein: (Array[diff] diffs) -> Integer

#self?.diff_line_mode ⇒ Array[diff]

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

Parameters:

  • text1 (String)
  • text2 (String)
  • options (Options)
  • deadline (Numeric)

Returns:



36
 
# File 'sig/diff_match_patch_es/diff.rbs', line 36

def self?.diff_line_mode: (String text1, String text2, Options options, Numeric deadline) -> Array[diff]

#self?.diff_lines_to_chars ⇒ { chars1: String, chars2: String, line_array: Array[String] }

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

Parameters:

  • text1 (String)
  • text2 (String)

Returns:

  • ({ chars1: String, chars2: String, line_array: Array[String] }) 


51
 
# File 'sig/diff_match_patch_es/diff.rbs', line 51

def self?.diff_lines_to_chars: (String text1, String text2) -> { chars1: String, chars2: String, line_array: Array[String] }

#self?.diff_main ⇒ Array[diff]

Find the differences between two texts.

Parameters:

  • text1 (String)
  • text2 (String)
  • options (options_arg)
  • checklines (Boolean)
  • deadline (Numeric, nil)

Returns:



28
 
# File 'sig/diff_match_patch_es/diff.rbs', line 28

def self?.diff_main: (String text1, String text2, ?options_arg options, ?bool checklines, ?Numeric? deadline) -> Array[diff]

#self?.diff_pretty_html ⇒ String

Convert a diff array into a pretty HTML report.

Parameters:

  • diffs (Array[diff])

Returns:

  • (String) 


94
 
# File 'sig/diff_match_patch_es/diff.rbs', line 94

def self?.diff_pretty_html: (Array[diff] diffs) -> String

#self?.diff_text1 ⇒ String

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

Parameters:

  • diffs (Array[diff])

Returns:

  • (String) 


97
 
# File 'sig/diff_match_patch_es/diff.rbs', line 97

def self?.diff_text1: (Array[diff] diffs) -> String

#self?.diff_text2 ⇒ String

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

Parameters:

  • diffs (Array[diff])

Returns:

  • (String) 


100
 
# File 'sig/diff_match_patch_es/diff.rbs', line 100

def self?.diff_text2: (Array[diff] diffs) -> String

#self?.diff_to_delta ⇒ String

Crush the diff into an encoded string which describes the operations required to transform text1 into text2.

Parameters:

  • diffs (Array[diff])

Returns:

  • (String) 


108
 
# File 'sig/diff_match_patch_es/diff.rbs', line 108

def self?.diff_to_delta: (Array[diff] diffs) -> String

#self?.diff_x_index ⇒ Integer

loc is a location in text1, compute and return the equivalent location in text2.

Parameters:

  • diffs (Array[diff])
  • loc (Integer)

Returns:

  • (Integer) 


91
 
# File 'sig/diff_match_patch_es/diff.rbs', line 91

def self?.diff_x_index: (Array[diff] diffs, Integer loc) -> Integer

#self?.line_char_for ⇒ String

Parameters:

  • index (Integer)

Returns:

  • (String) 


45
 
# File 'sig/diff_match_patch_es/diff.rbs', line 45

def self?.line_char_for: (Integer index) -> String

#self?.line_index_for ⇒ Integer

Parameters:

  • char (String)

Returns:

  • (Integer) 


47
 
# File 'sig/diff_match_patch_es/diff.rbs', line 47

def self?.line_index_for: (String char) -> Integer

#self?.match ⇒ Integer

Parameters:

  • text (String)
  • pattern (String)
  • loc (Integer)
  • options (options_arg)

Returns:

  • (Integer) 


28
 
# File 'sig/diff_match_patch_es.rbs', line 28

def self?.match: (String text, String pattern, Integer loc, ?options_arg options) -> Integer

#self?.match_alphabet ⇒ Hash[String, Integer]

Initialise the alphabet (character -> bitmask) for the Bitap algorithm.

Parameters:

  • pattern (String)

Returns:

  • (Hash[String, Integer]) 


13
 
# File 'sig/diff_match_patch_es/match.rbs', line 13

def self?.match_alphabet: (String pattern) -> Hash[String, Integer]

#self?.match_bitap ⇒ Integer

Locate the best instance of 'pattern' in 'text' near 'loc' using the Bitap algorithm. Returns the best match index or -1.

Parameters:

  • text (String)
  • pattern (String)
  • loc (Integer)
  • options (options_arg)

Returns:

  • (Integer) 


10
 
# File 'sig/diff_match_patch_es/match.rbs', line 10

def self?.match_bitap: (String text, String pattern, Integer loc, ?options_arg options) -> Integer

#self?.match_main ⇒ Integer

Locate the best instance of 'pattern' in 'text' near 'loc'. Returns the best match index or -1.

Parameters:

  • text (String)
  • pattern (String)
  • loc (Integer)
  • options (options_arg)

Returns:

  • (Integer) 


6
 
# File 'sig/diff_match_patch_es/match.rbs', line 6

def self?.match_main: (String text, String pattern, Integer loc, ?options_arg options) -> Integer

#self?.now_ms ⇒ Float

Returns:

  • (Float) 


25
 
# File 'sig/diff_match_patch_es/diff.rbs', line 25

def self?.now_ms: () -> Float

#self? ⇒ Array[Patch] #self? ⇒ Array[Patch] #self? ⇒ Array[Patch] #self? ⇒ Array[Patch]

Overloads:

  • #self? ⇒ Array[Patch]

    Parameters:

    • a (String)
    • opt_b (String)
    • opt_c (nil)
    • options (options_arg)

    Returns:

  • #self? ⇒ Array[Patch]

    Parameters:

    • a (Array[diff])
    • opt_b (nil)
    • opt_c (nil)
    • options (options_arg)

    Returns:

  • #self? ⇒ Array[Patch]

    Parameters:

    • a (String)
    • opt_b (Array[diff])
    • opt_c (nil)
    • options (options_arg)

    Returns:

  • #self? ⇒ Array[Patch]

    Parameters:

    • a (String)
    • opt_b (String)
    • opt_c (Array[diff])
    • options (options_arg)

    Returns:



30
31
32
33
 
# File 'sig/diff_match_patch_es.rbs', line 30

def self?.patch: (String a, String opt_b, ?nil opt_c, ?options_arg options) -> Array[Patch]
| (Array[diff] a, ?nil opt_b, ?nil opt_c, ?options_arg options) -> Array[Patch]
| (String a, Array[diff] opt_b, ?nil opt_c, ?options_arg options) -> Array[Patch]
| (String a, String opt_b, Array[diff] opt_c, ?options_arg options) -> Array[Patch]

#self?.patch_add_context ⇒ nil

Increase the context until it is unique, but don't let the pattern expand beyond match_max_bits. Mutates patch in place.

Parameters:

  • patch (Patch)
  • text (String)
  • options (options_arg)

Returns:

  • (nil) 


27
 
# File 'sig/diff_match_patch_es/patch.rbs', line 27

def self?.patch_add_context: (Patch patch, String text, options_arg options) -> nil

#self?.patch_add_padding ⇒ String

Add some padding on text start and end so that edges can match something. Returns the padding string added to each side.

Parameters:

  • patches (Array[Patch])
  • options (options_arg)

Returns:

  • (String) 


48
 
# File 'sig/diff_match_patch_es/patch.rbs', line 48

def self?.patch_add_padding: (Array[Patch] patches, ?options_arg options) -> String

#self?.patch_apply ⇒ [String, Array[bool]]

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.

Parameters:

  • patches (Array[Patch])
  • text (String)
  • options (options_arg)

Returns:

  • ([String, Array[bool]]) 


44
 
# File 'sig/diff_match_patch_es/patch.rbs', line 44

def self?.patch_apply: (Array[Patch] patches, String text, ?options_arg options) -> [String, Array[bool]]

#self?.patch_deep_copy ⇒ Array[Patch]

Given an array of patches, return another array that is identical.

Parameters:

Returns:



40
 
# File 'sig/diff_match_patch_es/patch.rbs', line 40

def self?.patch_deep_copy: (Array[Patch] patches) -> Array[Patch]

#self?.patch_from_text ⇒ Array[Patch]

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

Parameters:

  • textline (String, nil)

Returns:



59
 
# File 'sig/diff_match_patch_es/patch.rbs', line 59

def self?.patch_from_text: (String? textline) -> Array[Patch]

#self? ⇒ Array[Patch] #self? ⇒ Array[Patch] #self? ⇒ Array[Patch] #self? ⇒ Array[Patch]

Compute a list of patches to turn text1 into text2. 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

Overloads:

  • #self? ⇒ Array[Patch]

    Parameters:

    • a (String)
    • opt_b (String)
    • opt_c (nil)
    • options (options_arg)

    Returns:

  • #self? ⇒ Array[Patch]

    Parameters:

    • a (Array[diff])
    • opt_b (nil)
    • opt_c (nil)
    • options (options_arg)

    Returns:

  • #self? ⇒ Array[Patch]

    Parameters:

    • a (String)
    • opt_b (Array[diff])
    • opt_c (nil)
    • options (options_arg)

    Returns:

  • #self? ⇒ Array[Patch]

    Parameters:

    • a (String)
    • opt_b (String)
    • opt_c (Array[diff])
    • options (options_arg)

    Returns:



34
35
36
37
 
# File 'sig/diff_match_patch_es/patch.rbs', line 34

def self?.patch_make: (String a, String opt_b, ?nil opt_c, ?options_arg options) -> Array[Patch]
| (Array[diff] a, ?nil opt_b, ?nil opt_c, ?options_arg options) -> Array[Patch]
| (String a, Array[diff] opt_b, ?nil opt_c, ?options_arg options) -> Array[Patch]
| (String a, String opt_b, Array[diff] opt_c, ?options_arg options) -> Array[Patch]

#self?.patch_split_max ⇒ nil

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

Parameters:

  • patches (Array[Patch])
  • options (options_arg)

Returns:

  • (nil) 


52
 
# File 'sig/diff_match_patch_es/patch.rbs', line 52

def self?.patch_split_max: (Array[Patch] patches, ?options_arg options) -> nil

#self?.patch_to_text ⇒ String

Take a list of patches and return a textual representation.

Parameters:

Returns:

  • (String) 


55
 
# File 'sig/diff_match_patch_es/patch.rbs', line 55

def self?.patch_to_text: (Array[Patch] patches) -> String

#self?.resolve_options ⇒ Options

Accepts nil, a Hash of overrides, or an already-resolved Options.

Parameters:

  • options (options_arg)

Returns:



37
 
# File 'sig/diff_match_patch_es/options.rbs', line 37

def self?.resolve_options: (?options_arg options) -> Options