module LCS
Constants
- BalancedCallbacks
This callback object implements the default set of callback events, which only returns the event itself. Note that finished_a and finished_b are not implemented – I haven't yet figured out where they would be useful.
Note that this is intended to be called as is, e.g.,
Diff::LCS.LCS(seq1, seq2, Diff::LCS::DefaultCallbacks)
- SequenceCallbacks
This callback object implements the default set of callback events, which only returns the event itself. Note that finished_a and finished_b are not implemented – I haven't yet figured out where they would be useful.
Note that this is intended to be called as is, e.g.,
Diff::LCS.LCS(seq1, seq2, Diff::LCS::DefaultCallbacks)
- VERSION
Private Class Methods
# File lib/diff/lcs/callbacks.rb, line 48 def self.callbacks_for(callbacks) callbacks.new rescue callbacks end
diff computes the smallest set of additions and deletions necessary to turn the first sequence into the second, and returns a description of these changes.
See Diff::LCS::DiffCallbacks for the default behaviour. An alternate
behaviour may be implemented with Diff::LCS::ContextDiffCallbacks. If a
Class argument is provided for callbacks
, diff will attempt to initialise it. If
the callbacks
object (possibly initialised) responds to
finish, it will be called.
# File lib/diff/lcs.rb, line 164 def diff(seq1, seq2, callbacks = nil, &block) # :yields diff changes: diff_traversal(:diff, seq1, seq2, callbacks || Diff::LCS::DiffCallbacks, &block) end
# File lib/diff/lcs/internals.rb, line 3 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.kind_of? Array hunk.map { |hunk_block| block[hunk_block] } else block[hunk] end end else callbacks.diffs end end
# File lib/diff/lcs.rb, line 140 def lcs(seq1, seq2, &block) #:yields seq1[i] for each matched: matches = Diff::LCS::Internals.lcs(seq1, seq2) ret = [] string = seq1.kind_of? String matches.each_with_index do |e, i| unless matches[i].nil? v = string ? seq1[i, 1] : seq1[i] v = block[v] if block ret << v end end ret end
Applies a patchset
to the sequence src
according
to the direction
(:patch
or
:unpatch
), producing a new sequence.
If the direction
is not specified, ::patch will attempt to discover the
direction of the patchset
.
A patchset
can be considered to apply forward
(:patch
) if the following expression is true:
patch(s1, diff(s1, s2)) -> s2
A patchset
can be considered to apply backward
(:unpatch
) if the following expression is true:
patch(s2, diff(s1, s2)) -> s1
If the patchset
contains no changes, the src
value will be returned as either src.dup
or src
.
A patchset
can be deemed as having no changes if the following
predicate returns true:
patchset.empty? or patchset.flatten.all? { |change| change.unchanged? }
Patchsets¶ ↑
A patchset
is always an enumerable sequence of changes, hunks
of changes, or a mix of the two. A hunk of changes is an enumerable
sequence of changes:
[ # patchset # change [ # hunk # change ] ]
The patch
method accepts patchset
s that are
enumerable sequences containing either Diff::LCS::Change objects (or a
subclass) or the array representations of those objects. Prior to
application, array representations of Diff::LCS::Change objects will be
reified.
# File lib/diff/lcs.rb, line 608 def patch(src, patchset, direction = nil) # Normalize the patchset. has_changes, patchset = Diff::LCS::Internals.analyze_patchset(patchset) if not has_changes return src.dup if src.respond_to? :dup return src end string = src.kind_of?(String) # Start with a new empty type of the source's class res = src.class.new direction ||= Diff::LCS::Internals.intuit_diff_direction(src, patchset) ai = bj = 0 patch_map = PATCH_MAP[direction] patchset.flatten.each do |change| # Both Change and ContextChange support #action action = patch_map[change.action] case change when Diff::LCS::ContextChange case direction when :patch el = change.new_element op = change.old_position np = change.new_position when :unpatch el = change.old_element op = change.new_position np = change.old_position end case action when '-' # Remove details from the old string while ai < op res << (string ? src[ai, 1] : src[ai]) ai += 1 bj += 1 end ai += 1 when '+' while bj < np res << (string ? src[ai, 1] : src[ai]) ai += 1 bj += 1 end res << el bj += 1 when '=' # This only appears in sdiff output with the SDiff callback. # Therefore, we only need to worry about dealing with a single # element. res << el ai += 1 bj += 1 when '!' while ai < op res << (string ? src[ai, 1] : src[ai]) ai += 1 bj += 1 end bj += 1 ai += 1 res << el end when Diff::LCS::Change case action when '-' while ai < change.position res << (string ? src[ai, 1] : src[ai]) ai += 1 bj += 1 end ai += 1 when '+' while bj < change.position res << (string ? src[ai, 1] : src[ai]) ai += 1 bj += 1 end bj += 1 res << change.element end end end while ai < src.size res << (string ? src[ai, 1] : src[ai]) ai += 1 bj += 1 end res end
Given a set of patchset, convert the current version to the next version. Does no auto-discovery.
# File lib/diff/lcs.rb, line 721 def patch!(src, patchset) patch(src, patchset, :patch) end
sdiff computes all necessary components to show two sequences and their minimized differences side by side, just like the Unix utility sdiff does:
old < - same same before | after - > new
See Diff::LCS::SDiffCallbacks for the default behaviour. An alternate
behaviour may be implemented with Diff::LCS::ContextDiffCallbacks. If a
Class argument is provided for callbacks
, diff will attempt to initialise it. If
the callbacks
object (possibly initialised) responds to
finish, it will be called.
# File lib/diff/lcs.rb, line 183 def sdiff(seq1, seq2, callbacks = nil, &block) #:yields diff changes: diff_traversal(:sdiff, seq1, seq2, callbacks || Diff::LCS::SDiffCallbacks, &block) end
traverse_balanced is an alternative to traverse_sequences. It uses a different algorithm to iterate through the entries in the computed longest common subsequence. Instead of viewing the changes as insertions or deletions from one of the sequences, traverse_balanced will report changes between the sequences.
The arguments to traverse_balanced are the two sequences to traverse and a callback object, like this:
traverse_balanced(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)
sdiff is implemented with traverse_balanced.
Callback Methods¶ ↑
Optional callback methods are emphasized.
- callbacks#match
-
Called when
a
andb
are pointing to common elements inA
andB
. - callbacks#discard_a
-
Called when
a
is pointing to an element not inB
. - callbacks#discard_b
-
Called when
b
is pointing to an element not inA
. - callbacks#change
-
Called when
a
andb
are pointing to the same relative position, butA[a]
andB[b]
are not the same; a change has occurred.
traverse_balanced might be a bit slower than traverse_sequences, noticable only while processing huge amounts of data.
Algorithm¶ ↑
a---+ v A = a b c e h j l m n p B = b c d e f j k l m r s t ^ b---+
Matches¶ ↑
If there are two arrows (a
and b
) pointing to
elements of sequences A
and B
, the arrows will
initially point to the first elements of their respective sequences. traverse_sequences will
advance the arrows through the sequences one element at a time, calling a
method on the user-specified callback object before each advance. It will
advance the arrows in such a way that if there are elements
A[i]
and B[j]
which are both equal and part of
the longest common subsequence, there will be some moment during the
execution of traverse_sequences when
arrow a
is pointing to A[i]
and arrow
b
is pointing to B[j]
. When this happens, traverse_sequences will
call callbacks#match
and then it will advance both arrows.
Discards¶ ↑
Otherwise, one of the arrows is pointing to an element of its sequence that
is not part of the longest common subsequence. traverse_sequences will
advance that arrow and will call callbacks#discard_a
or
callbacks#discard_b
, depending on which arrow it advanced.
Changes¶ ↑
If both a
and b
point to elements that are not
part of the longest common subsequence, then traverse_sequences will try
to call callbacks#change
and advance both arrows. If
callbacks#change
is not implemented, then
callbacks#discard_a
and callbacks#discard_b
will
be called in turn.
The methods for callbacks#match
,
callbacks#discard_a
, callbacks#discard_b
, and
callbacks#change
are invoked with an event comprising the
action (“=”, “+”, “-”, or “!”, respectively), the indicies i
and j
, and the elements A[i]
and
B[j]
. Return values are discarded by traverse_balanced.
Context¶ ↑
Note that i
and j
may not be the same index
position, even if a
and b
are considered to be
pointing to matching or changed elements.
# File lib/diff/lcs.rb, line 460 def traverse_balanced(seq1, seq2, callbacks = Diff::LCS::BalancedCallbacks) matches = Diff::LCS::Internals.lcs(seq1, seq2) a_size = seq1.size b_size = seq2.size ai = bj = mb = 0 ma = -1 string = seq1.kind_of?(String) # Process all the lines in the match vector. loop do # Find next match indices +ma+ and +mb+ loop do ma += 1 break unless ma < matches.size and matches[ma].nil? end break if ma >= matches.size # end of matches? mb = matches[ma] # Change(seq2) while (ai < ma) or (bj < mb) ax = string ? seq1[ai, 1] : seq1[ai] bx = string ? seq2[bj, 1] : seq2[bj] case [(ai < ma), (bj < mb)] when [true, true] if callbacks.respond_to?(:change) event = Diff::LCS::ContextChange.new('!', ai, ax, bj, bx) event = yield event if block_given? callbacks.change(event) ai += 1 bj += 1 else event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_a(event) ai += 1 ax = string ? seq1[ai, 1] : seq1[ai] event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_b(event) bj += 1 end when [true, false] event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_a(event) ai += 1 when [false, true] event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_b(event) bj += 1 end end # Match ax = string ? seq1[ai, 1] : seq1[ai] bx = string ? seq2[bj, 1] : seq2[bj] event = Diff::LCS::ContextChange.new('=', ai, ax, bj, bx) event = yield event if block_given? callbacks.match(event) ai += 1 bj += 1 end while (ai < a_size) or (bj < b_size) ax = string ? seq1[ai, 1] : seq1[ai] bx = string ? seq2[bj, 1] : seq2[bj] case [(ai < a_size), (bj < b_size)] when [true, true] if callbacks.respond_to?(:change) event = Diff::LCS::ContextChange.new('!', ai, ax, bj, bx) event = yield event if block_given? callbacks.change(event) ai += 1 bj += 1 else event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_a(event) ai += 1 ax = string ? seq1[ai, 1] : seq1[ai] event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_b(event) bj += 1 end when [true, false] event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_a(event) ai += 1 when [false, true] event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_b(event) bj += 1 end end end
traverse_sequences is the most general facility provided by this module; diff and lcs are implemented as calls to it.
The arguments to traverse_sequences are the two sequences to traverse, and a callback object, like this:
traverse_sequences(seq1, seq2, Diff::LCS::ContextDiffCallbacks.new)
Callback Methods¶ ↑
Optional callback methods are emphasized.
- callbacks#match
-
Called when
a
andb
are pointing to common elements inA
andB
. - callbacks#discard_a
-
Called when
a
is pointing to an element not inB
. - callbacks#discard_b
-
Called when
b
is pointing to an element not inA
. - callbacks#finished_a
-
Called when
a
has reached the end of sequenceA
. - callbacks#finished_b
-
Called when
b
has reached the end of sequenceB
.
Algorithm¶ ↑
a---+ v A = a b c e h j l m n p B = b c d e f j k l m r s t ^ b---+
If there are two arrows (a
and b
) pointing to
elements of sequences A
and B
, the arrows will
initially point to the first elements of their respective sequences. traverse_sequences will
advance the arrows through the sequences one element at a time, calling a
method on the user-specified callback object before each advance. It will
advance the arrows in such a way that if there are elements
A[i]
and B[j]
which are both equal and part of
the longest common subsequence, there will be some moment during the
execution of traverse_sequences when
arrow a
is pointing to A[i]
and arrow
b
is pointing to B[j]
. When this happens, traverse_sequences will
call callbacks#match
and then it will advance both arrows.
Otherwise, one of the arrows is pointing to an element of its sequence that
is not part of the longest common subsequence. traverse_sequences will
advance that arrow and will call callbacks#discard_a
or
callbacks#discard_b
, depending on which arrow it advanced. If
both arrows point to elements that are not part of the longest common
subsequence, then traverse_sequences will
advance one of them and call the appropriate callback, but it is not
specified which it will call.
The methods for callbacks#match
,
callbacks#discard_a
, and callbacks#discard_b
are
invoked with an event comprising the action (“=”, “+”, or “-”,
respectively), the indicies i
and j
, and the
elements A[i]
and B[j]
. Return values are
discarded by traverse_sequences.
End of Sequences¶ ↑
If arrow a
reaches the end of its sequence before arrow
b
does, traverse_sequence will try to call
callbacks#finished_a
with the last index and element of
A
(A[-1]
) and the current index and element of
B
(B[j]
). If callbacks#finished_a
does not exist, then callbacks#discard_b
will be called on
each element of B
until the end of the sequence is reached
(the call will be done with A[-1]
and B[j]
for
each element).
If b
reaches the end of B
before a
reaches the end of A
, callbacks#finished_b
will
be called with the current index and element of A
(A[i]
) and the last index and element of B
(A[-1]
). Again, if callbacks#finished_b
does not
exist on the callback object, then callbacks#discard_a
will be
called on each element of A
until the end of the sequence is
reached (A[i]
and B[-1]
).
There is a chance that one additional callbacks#discard_a
or
callbacks#discard_b
will be called after the end of the
sequence is reached, if a
has not yet reached the end of
A
or b
has not yet reached the end of
B
.
# File lib/diff/lcs.rb, line 269 def traverse_sequences(seq1, seq2, callbacks = Diff::LCS::SequenceCallbacks, &block) #:yields change events: callbacks ||= Diff::LCS::SequenceCallbacks matches = Diff::LCS::Internals.lcs(seq1, seq2) run_finished_a = run_finished_b = false string = seq1.kind_of?(String) a_size = seq1.size b_size = seq2.size ai = bj = 0 (0..matches.size).each do |i| b_line = matches[i] ax = string ? seq1[i, 1] : seq1[i] bx = string ? seq2[bj, 1] : seq2[bj] if b_line.nil? unless ax.nil? or (string and ax.empty?) event = Diff::LCS::ContextChange.new('-', i, ax, bj, bx) event = yield event if block_given? callbacks.discard_a(event) end else loop do break unless bj < b_line bx = string ? seq2[bj, 1] : seq2[bj] event = Diff::LCS::ContextChange.new('+', i, ax, bj, bx) event = yield event if block_given? callbacks.discard_b(event) bj += 1 end bx = string ? seq2[bj, 1] : seq2[bj] event = Diff::LCS::ContextChange.new('=', i, ax, bj, bx) event = yield event if block_given? callbacks.match(event) bj += 1 end ai = i end ai += 1 # The last entry (if any) processed was a match. +ai+ and +bj+ point # just past the last matching lines in their sequences. while (ai < a_size) or (bj < b_size) # last A? if ai == a_size and bj < b_size if callbacks.respond_to?(:finished_a) and not run_finished_a ax = string ? seq1[-1, 1] : seq1[-1] bx = string ? seq2[bj, 1] : seq2[bj] event = Diff::LCS::ContextChange.new('>', (a_size - 1), ax, bj, bx) event = yield event if block_given? callbacks.finished_a(event) run_finished_a = true else ax = string ? seq1[ai, 1] : seq1[ai] loop do bx = string ? seq2[bj, 1] : seq2[bj] event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_b(event) bj += 1 break unless bj < b_size end end end # last B? if bj == b_size and ai < a_size if callbacks.respond_to?(:finished_b) and not run_finished_b ax = string ? seq1[ai, 1] : seq1[ai] bx = string ? seq2[-1, 1] : seq2[-1] event = Diff::LCS::ContextChange.new('<', ai, ax, (b_size - 1), bx) event = yield event if block_given? callbacks.finished_b(event) run_finished_b = true else bx = string ? seq2[bj, 1] : seq2[bj] loop do ax = string ? seq1[ai, 1] : seq1[ai] event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_a(event) ai += 1 break unless bj < b_size end end end if ai < a_size ax = string ? seq1[ai, 1] : seq1[ai] bx = string ? seq2[bj, 1] : seq2[bj] event = Diff::LCS::ContextChange.new('-', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_a(event) ai += 1 end if bj < b_size ax = string ? seq1[ai, 1] : seq1[ai] bx = string ? seq2[bj, 1] : seq2[bj] event = Diff::LCS::ContextChange.new('+', ai, ax, bj, bx) event = yield event if block_given? callbacks.discard_b(event) bj += 1 end end end
Given a set of patchset, convert the current version to the prior version. Does no auto-discovery.
# File lib/diff/lcs.rb, line 715 def unpatch!(src, patchset) patch(src, patchset, :unpatch) end
Private Instance Methods
Returns the difference set between self
and
other
. See #diff.
# File lib/diff/lcs.rb, line 68 def diff(other, callbacks = nil, &block) Diff::LCS.diff(self, other, callbacks, &block) end
Returns an Array containing the longest common
subsequence(s) between self
and other
. See
Diff::LCS#LCS.
lcs = seq1.lcs(seq2)
# File lib/diff/lcs.rb, line 62 def lcs(other, &block) #:yields self[i] if there are matched subsequences: Diff::LCS.lcs(self, other, &block) end
Attempts to patch self
with the provided
patchset
. A new sequence based on self
and the
patchset
will be created. See #patch. Attempts to autodiscover the
direction of the patch.
# File lib/diff/lcs.rb, line 96 def patch(patchset) Diff::LCS.patch(self, patchset) end
Attempts to patch self
with the provided
patchset
. A new sequence based on self
and the
patchset
will be created. See #patch. Does no patch direction
autodiscovery.
# File lib/diff/lcs.rb, line 104 def patch!(patchset) Diff::LCS.patch!(self, patchset) end
Attempts to patch self
with the provided
patchset
, using patch!. If the sequence this is used
on supports replace, the value of self
will be replaced. See
#patch. Does no patch direction
autodiscovery.
# File lib/diff/lcs.rb, line 118 def patch_me(patchset) if respond_to? :replace replace(patch!(patchset)) else patch!(patchset) end end
Returns the balanced (“side-by-side”) difference set between
self
and other
. See #sdiff.
# File lib/diff/lcs.rb, line 74 def sdiff(other, callbacks = nil, &block) Diff::LCS.sdiff(self, other, callbacks, &block) end
Traverses the discovered longest common subsequences between
self
and other
using the alternate, balanced
algorithm. See #traverse_balanced.
# File lib/diff/lcs.rb, line 88 def traverse_balanced(other, callbacks = nil, &block) traverse_balanced(self, other, callbacks || Diff::LCS.YieldingCallbacks, &block) end
Traverses the discovered longest common subsequences between
self
and other
. See #traverse_sequences.
# File lib/diff/lcs.rb, line 80 def traverse_sequences(other, callbacks = nil, &block) traverse_sequences(self, other, callbacks || Diff::LCS.YieldingCallbacks, &block) end
Attempts to unpatch self
with the provided
patchset
. A new sequence based on self
and the
patchset
will be created. See #unpatch. Does no patch direction
autodiscovery.
# File lib/diff/lcs.rb, line 111 def unpatch!(patchset) Diff::LCS.unpatch!(self, patchset) end
Attempts to unpatch self
with the provided
patchset
, using unpatch!. If the sequence this is
used on supports replace, the value of self
will be replaced.
See #unpatch. Does no patch
direction autodiscovery.
# File lib/diff/lcs.rb, line 130 def unpatch_me(patchset) if respond_to? :replace replace(unpatch!(patchset)) else unpatch!(patchset) end end