20625065018

Committed 31 Dec 2025 06:41PM UTC coverage: 91.336% (+3.0%) from 88.366%

Build # 20625065018

Build Type

push

github

Committed by

halostatue

Commit Message

chore: Prepare for release of diff-lcs 2.0 beta 1

Simplified build tooling, updated GitHub Actions workflows, prepared
changelog for dev release, and updated support for Ruby 3.2 through 4.x.

- Streamlined Rakefile and Gemfile and removed unnecessary complexity
- Added Ruby 4.0 support and dropped unsupported Ruby versions
- Simplified CI configuration
- Updated release and support documents.

Signed-off-by: Austin Ziegler <austin@zieglers.ca>

Run Details

400 of 597 branches covered (67.0%)

1 of 1 new or added line in 1 file covered. (100.0%)

52 existing lines in 6 files now uncovered.

622 of 681 relevant lines covered (91.34%)

291.44 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

86.43

/lib/diff/lcs/internals.rb

# frozen_string_literal: true

class << Diff::LCS
  def callbacks_for(callbacks) # :nodoc:
    callbacks.new
  rescue
    callbacks
  end
  private :callbacks_for

  def diff_traversal(method, seq1, seq2, callbacks, &block)
    callbacks = callbacks_for(callbacks)

    case method
    when :diff
      traverse_sequences(seq1, seq2, callbacks)
    when :sdiff
      traverse_balanced(seq1, seq2, callbacks)
    end

    callbacks.finish if callbacks.respond_to? :finish

    if block
      callbacks.diffs.map do |hunk|
        if hunk.is_a? Array
          hunk.map { block.call(_1) }
        else
          block.call(hunk)
        end
      end
    else
      callbacks.diffs
    end
  end
  private :diff_traversal
end

module Diff::LCS::Internals # :nodoc:
  # Compute the longest common subsequence between the sequenced enumerable values `a` and
  # `b`. The result is an array whose contents is such that
  #
  # ```ruby
  # result = Diff::LCS::Internals.lcs(a, b)
  # result.each_with_index do |e, i|
  #   assert_equal(a[i], b[e]) unless e.nil?
  # end
  # ```
  def self.lcs(a, b)
    a_start = b_start = 0
    a_finish = a.size - 1
    b_finish = b.size - 1
    vector = []

    # Collect any common elements at the beginning...
    while (a_start <= a_finish) && (b_start <= b_finish) && (a[a_start] == b[b_start])
      vector[a_start] = b_start
      a_start += 1
      b_start += 1
    end

    # Now the end...
    while (a_start <= a_finish) && (b_start <= b_finish) && (a[a_finish] == b[b_finish])
      vector[a_finish] = b_finish
      a_finish -= 1
      b_finish -= 1
    end

    # Now, compute the equivalence classes of positions of elements. An explanation for
    # how this works: https://codeforces.com/topic/92191
    b_matches = position_hash(b, b_start..b_finish)

    thresh = []
    links = []

    (a_start..a_finish).each do |i|
      ai = a[i]
      bm = b_matches[ai]
      k = nil
      bm.reverse_each do |j|
        # Although the threshold check is not mandatory for this to work, it may have an
        # optimization purpose.
        # An attempt to remove it: https://github.com/halostatue/diff-lcs/pull/72
        # Why it is reintroduced: https://github.com/halostatue/diff-lcs/issues/78
        if k && (thresh[k] > j) && (thresh[k - 1] < j)
          thresh[k] = j
        else
          k = replace_next_larger(thresh, j, k)
        end
        links[k] = [k.positive? ? links[k - 1] : nil, i, j] unless k.nil?
      end
    end

    unless thresh.empty?
      link = links[thresh.size - 1]
      until link.nil?
        vector[link[1]] = link[2]
        link = link[0]
      end
    end

    vector
  end

  # This method will analyze the provided patchset to provide a single-pass normalization
  # (conversion of the array form of Diff::LCS::Change objects to the object form of same)
  # and detection of whether the patchset represents changes to be made.
  def self.analyze_patchset(patchset, depth = 0)
    fail "Patchset too complex" if depth > 1

    has_changes = false
    new_patchset = []

    # Format:
    # [ # patchset
    #   # hunk (change)
    #   [ # hunk
    #     # change
    #   ]
    # ]

    patchset.each do |hunk|
      case hunk
      when Diff::LCS::Change, Diff::LCS::ContextChange
        has_changes ||= !hunk.unchanged?
        new_patchset << hunk
      when Array
        # Detect if the 'hunk' is actually an array-format change object.
        if Diff::LCS::Change.valid_action? hunk[0]
          hunk = Diff::LCS::Change.from_a(hunk)
          has_changes ||= !hunk.unchanged?
          new_patchset << hunk
        else
          with_changes, hunk = analyze_patchset(hunk, depth + 1)
          has_changes ||= with_changes
          new_patchset.concat(hunk)
        end
      else
        fail ArgumentError, "Cannot normalise a hunk of class #{hunk.class}."
      end
    end

    [has_changes, new_patchset]
  end

  # Examine the patchset and the source to see in which direction the patch should be
  # applied.
  #
  # WARNING: By default, this examines the whole patch, so this could take some time. This
  # also works better with Diff::LCS::ContextChange or Diff::LCS::Change as its source, as
  # an array will cause the creation of one of the above.
  def self.intuit_diff_direction(src, patchset, limit = nil)
    count = left_match = left_miss = right_match = right_miss = 0

    patchset.each do |change|
      count += 1

      case change
      when Diff::LCS::ContextChange
        le = src[change.old_position]
        re = src[change.new_position]

        case change.action
        when "-" # Remove details from the old string
          if le == change.old_element
            left_match += 1
          else
            left_miss += 1
          end
        when "+"
          if re == change.new_element
            right_match += 1
          else
            right_miss += 1
          end
        when "="
          left_miss += 1 if le != change.old_element
          right_miss += 1 if re != change.new_element
        when "!"
          if le == change.old_element
            left_match += 1
          elsif re == change.new_element
            right_match += 1
          else
            left_miss += 1
            right_miss += 1
          end
        end
      when Diff::LCS::Change
        # With a simplistic change, we can't tell the difference between the left and
        # right on '!' actions, so we ignore those. On '=' actions, if there's a miss, we
        # miss both left and right.
        element = src[change.position]

        case change.action
        when "-"
          if element == change.element
            left_match += 1
          else
            left_miss += 1
          end
        when "+"
          if element == change.element
            right_match += 1
          else
            right_miss += 1
          end
        when "="
          if element != change.element
            left_miss += 1
            right_miss += 1
          end
        end
      end

      break if !limit.nil? && (count > limit)
    end

    no_left = left_match.zero? && left_miss.positive?
    no_right = right_match.zero? && right_miss.positive?

    case [no_left, no_right]
    when [false, true]
      :patch
    when [true, false]
      :unpatch
    else
      case left_match <=> right_match
      when 1
        if left_miss.zero?
          :patch
        else
          :unpatch
        end
      when -1
        if right_miss.zero?
          :unpatch
        else
          :patch
        end
      else
        fail "The provided patchset does not appear to apply to the provided enumerable as either source or destination value."
      end
    end
  end

  class << self
    # Find the place at which `value` would normally be inserted into the Enumerable. If
    # that place is already occupied by `value`, do nothing and return `nil`. If the place
    # does not exist (i.e., it is off the end of the Enumerable), add it to the end.
    # Otherwise, replace the element at that point with `value`. It is assumed that the
    # Enumerable's values are numeric.
    #
    # This operation preserves the sort order.
    def replace_next_larger(enum, value, last_index = nil)
      # Off the end?
      if enum.empty? || (value > enum[-1])
        enum << value
        return enum.size - 1
      end

      # Binary search for the insertion point
      last_index ||= enum.size - 1
      first_index = 0
      while first_index <= last_index
        i = (first_index + last_index) >> 1

        found = enum[i]

        return nil if value == found

        if value > found
          first_index = i + 1
        else
          last_index = i - 1
        end
      end

      # The insertion point is in first_index; overwrite the next larger value.
      enum[first_index] = value
      first_index
    end
    private :replace_next_larger

    # If `vector` maps the matching elements of another collection onto this Enumerable,
    # compute the inverse of `vector` that maps this Enumerable onto the collection.
    # (Currently unused.)
    def inverse_vector(a, vector)
      inverse = a.dup
      (0...vector.size).each do
        inverse[vector[_1]] = i unless vector[_1].nil?
      end
      inverse
    end
    private :inverse_vector

    # Returns a hash mapping each element of an Enumerable to the set of positions it
    # occupies in the Enumerable, optionally restricted to the elements specified in the
    # range of indexes specified by `interval`.
    def position_hash(enum, interval)
      Hash.new { |h, k| h[k] = [] }.tap { |hash| interval.each { hash[enum[_1]] << _1 } }
    end
    private :position_hash
  end
end

1	# frozen_string_literal: true
2
3	class << Diff::LCS	2✔
4	def callbacks_for(callbacks) # :nodoc:	2✔
5	callbacks.new	330✔
6	rescue
UNCOV 7	callbacks	×
8	end
9	private :callbacks_for	2✔
10
11	def diff_traversal(method, seq1, seq2, callbacks, &block)	2✔
12	callbacks = callbacks_for(callbacks)	330✔
13
14	case method	330!
15	when :diff	83✔
16	traverse_sequences(seq1, seq2, callbacks)	166✔
17	when :sdiff	82✔
18	traverse_balanced(seq1, seq2, callbacks)	164✔
19	end
20
21	callbacks.finish if callbacks.respond_to? :finish	330✔
22
23	if block	330!
UNCOV 24	callbacks.diffs.map do \|hunk\|	×
UNCOV 25	if hunk.is_a? Array	×
UNCOV 26	hunk.map { block.call(_1) }	×
27	else	×
UNCOV 28	block.call(hunk)	×
29	end
30	end
31	else	165✔
32	callbacks.diffs	330✔
33	end
34	end
35	private :diff_traversal	2✔
36	end
37
38	module Diff::LCS::Internals # :nodoc:	2✔
39	# Compute the longest common subsequence between the sequenced enumerable values `a` and
40	# `b`. The result is an array whose contents is such that
41	#
42	# ```ruby
43	# result = Diff::LCS::Internals.lcs(a, b)
44	# result.each_with_index do \|e, i\|
45	# assert_equal(a[i], b[e]) unless e.nil?
46	# end
47	# ```
48	def self.lcs(a, b)	2✔
49	a_start = b_start = 0	548✔
50	a_finish = a.size - 1	548✔
51	b_finish = b.size - 1	548✔
52	vector = []	548✔
53
54	# Collect any common elements at the beginning...
55	while (a_start <= a_finish) && (b_start <= b_finish) && (a[a_start] == b[b_start])	1,908✔
56	vector[a_start] = b_start	812✔
57	a_start += 1	812✔
58	b_start += 1	812✔
59	end
60
61	# Now the end...
62	while (a_start <= a_finish) && (b_start <= b_finish) && (a[a_finish] == b[b_finish])	2,110✔
63	vector[a_finish] = b_finish	1,014✔
64	a_finish -= 1	1,014✔
65	b_finish -= 1	1,014✔
66	end
67
68	# Now, compute the equivalence classes of positions of elements. An explanation for
69	# how this works: https://codeforces.com/topic/92191
70	b_matches = position_hash(b, b_start..b_finish)	548✔
71
72	thresh = []	548✔
73	links = []	548✔
74
75	(a_start..a_finish).each do \|i\|	548✔
76	ai = a[i]	2,284✔
77	bm = b_matches[ai]	2,284✔
78	k = nil	2,284✔
79	bm.reverse_each do \|j\|	2,284✔
80	# Although the threshold check is not mandatory for this to work, it may have an
81	# optimization purpose.
82	# An attempt to remove it: https://github.com/halostatue/diff-lcs/pull/72
83	# Why it is reintroduced: https://github.com/halostatue/diff-lcs/issues/78
84	if k && (thresh[k] > j) && (thresh[k - 1] < j)	1,042✔
85	thresh[k] = j	4✔
86	else	519✔
87	k = replace_next_larger(thresh, j, k)	1,038✔
88	end
89	links[k] = [k.positive? ? links[k - 1] : nil, i, j] unless k.nil?	1,042✔
90	end
91	end
92
93	unless thresh.empty?	548✔
94	link = links[thresh.size - 1]	202✔
95	until link.nil?	202✔
96	vector[link[1]] = link[2]	994✔
97	link = link[0]	994✔
98	end
99	end
100
101	vector	548✔
102	end
103
104	# This method will analyze the provided patchset to provide a single-pass normalization
105	# (conversion of the array form of Diff::LCS::Change objects to the object form of same)
106	# and detection of whether the patchset represents changes to be made.
107	def self.analyze_patchset(patchset, depth = 0)	2✔
108	fail "Patchset too complex" if depth > 1	910!
109
110	has_changes = false	910✔
111	new_patchset = []	910✔
112
113	# Format:
114	# [ # patchset
115	# # hunk (change)
116	# [ # hunk
117	# # change
118	# ]
119	# ]
120
121	patchset.each do \|hunk\|	910✔
122	case hunk	2,908!
123	when Diff::LCS::Change, Diff::LCS::ContextChange	1,156✔
124	has_changes \|\|= !hunk.unchanged?	2,312✔
125	new_patchset << hunk	2,312✔
126	when Array
127	# Detect if the 'hunk' is actually an array-format change object.	298✔
128	if Diff::LCS::Change.valid_action? hunk[0]	596!
UNCOV 129	hunk = Diff::LCS::Change.from_a(hunk)	×
UNCOV 130	has_changes \|\|= !hunk.unchanged?	×
UNCOV 131	new_patchset << hunk	×
132	else	298✔
133	with_changes, hunk = analyze_patchset(hunk, depth + 1)	596✔
134	has_changes \|\|= with_changes	596✔
135	new_patchset.concat(hunk)	596✔
136	end
137	else	×
UNCOV 138	fail ArgumentError, "Cannot normalise a hunk of class #{hunk.class}."	×
139	end
140	end
141
142	[has_changes, new_patchset]	910✔
143	end
144
145	# Examine the patchset and the source to see in which direction the patch should be
146	# applied.
147	#
148	# WARNING: By default, this examines the whole patch, so this could take some time. This
149	# also works better with Diff::LCS::ContextChange or Diff::LCS::Change as its source, as
150	# an array will cause the creation of one of the above.
151	def self.intuit_diff_direction(src, patchset, limit = nil)	2✔
152	count = left_match = left_miss = right_match = right_miss = 0	114✔
153
154	patchset.each do \|change\|	114✔
155	count += 1	788✔
156
157	case change	788!
158	when Diff::LCS::ContextChange	288✔
159	le = src[change.old_position]	576✔
160	re = src[change.new_position]	576✔
161
162	case change.action	576!
163	when "-" # Remove details from the old string	64✔
164	if le == change.old_element	128✔
165	left_match += 1	64✔
166	else	32✔
167	left_miss += 1	64✔
168	end
169	when "+"	64✔
170	if re == change.new_element	128✔
171	right_match += 1	64✔
172	else	32✔
173	right_miss += 1	64✔
174	end
175	when "="	136✔
176	left_miss += 1 if le != change.old_element	272✔
177	right_miss += 1 if re != change.new_element	272✔
178	when "!"	24✔
179	if le == change.old_element	48✔
180	left_match += 1	24✔
181	elsif re == change.new_element	24!
182	right_match += 1	24✔
183	else	×
UNCOV 184	left_miss += 1	×
UNCOV 185	right_miss += 1	×
186	end
187	end
188	when Diff::LCS::Change
189	# With a simplistic change, we can't tell the difference between the left and
190	# right on '!' actions, so we ignore those. On '=' actions, if there's a miss, we
191	# miss both left and right.	106✔
192	element = src[change.position]	212✔
193
194	case change.action	212!
195	when "-"	52✔
196	if element == change.element	104✔
197	left_match += 1	56✔
198	else	24✔
199	left_miss += 1	48✔
200	end
201	when "+"	54✔
202	if element == change.element	108✔
203	right_match += 1	56✔
204	else	26✔
205	right_miss += 1	52✔
206	end
207	when "="	×
UNCOV 208	if element != change.element	×
UNCOV 209	left_miss += 1	×
UNCOV 210	right_miss += 1	×
211	end
212	end
213	end
214
215	break if !limit.nil? && (count > limit)	788!
216	end
217
218	no_left = left_match.zero? && left_miss.positive?	114✔
219	no_right = right_match.zero? && right_miss.positive?	114✔
220
221	case [no_left, no_right]	114✔
222	when [false, true]	21✔
223	:patch	42✔
224	when [true, false]	20✔
225	:unpatch	40✔
226	else	16✔
227	case left_match <=> right_match	32!
228	when 1	8✔
229	if left_miss.zero?	16✔
230	:patch	12✔
231	else	2✔
232	:unpatch	4✔
233	end
234	when -1	8✔
235	if right_miss.zero?	16✔
236	:unpatch	12✔
237	else	2✔
238	:patch	4✔
239	end
240	else	×
UNCOV 241	fail "The provided patchset does not appear to apply to the provided enumerable as either source or destination value."	×
242	end
243	end
244	end
245
246	class << self	2✔
247	# Find the place at which `value` would normally be inserted into the Enumerable. If
248	# that place is already occupied by `value`, do nothing and return `nil`. If the place
249	# does not exist (i.e., it is off the end of the Enumerable), add it to the end.
250	# Otherwise, replace the element at that point with `value`. It is assumed that the
251	# Enumerable's values are numeric.
252	#
253	# This operation preserves the sort order.
254	def replace_next_larger(enum, value, last_index = nil)	2✔
255	# Off the end?
256	if enum.empty? \|\| (value > enum[-1])	1,038✔
257	enum << value	994✔
258	return enum.size - 1	994✔
259	end
260
261	# Binary search for the insertion point
262	last_index \|\|= enum.size - 1	44✔
263	first_index = 0	44✔
264	while first_index <= last_index	44✔
265	i = (first_index + last_index) >> 1	48✔
266
267	found = enum[i]	48✔
268
269	return nil if value == found	48✔
270
271	if value > found	24✔
272	first_index = i + 1	4✔
273	else	10✔
274	last_index = i - 1	20✔
275	end
276	end
277
278	# The insertion point is in first_index; overwrite the next larger value.
279	enum[first_index] = value	20✔
280	first_index	20✔
281	end
282	private :replace_next_larger	2✔
283
284	# If `vector` maps the matching elements of another collection onto this Enumerable,
285	# compute the inverse of `vector` that maps this Enumerable onto the collection.
286	# (Currently unused.)
287	def inverse_vector(a, vector)	2✔
288	inverse = a.dup	×
289	(0...vector.size).each do	×
UNCOV 290	inverse[vector[_1]] = i unless vector[_1].nil?	×
291	end
UNCOV 292	inverse	×
293	end
294	private :inverse_vector	2✔
295
296	# Returns a hash mapping each element of an Enumerable to the set of positions it
297	# occupies in the Enumerable, optionally restricted to the elements specified in the
298	# range of indexes specified by `interval`.
299	def position_hash(enum, interval)	2✔
300	Hash.new { \|h, k\| h[k] = [] }.tap { \|hash\| interval.each { hash[enum[_1]] << _1 } }	6,938✔
301	end
302	private :position_hash	2✔
303	end
304	end

halostatue / diff-lcs / 20625065018

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous