Debian Codegraph @

lib/util/lcs.scm

raw
1 ;;;; lcs.scm -- find out the longest common sequence
2 ;;;
3 ;;; Copyright (c) 2002-2003 by Alex Shinn, All rights reserved.
4 ;;; Copyright (c) 2002-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;;; Created: <2002-06-21 15:36:46 foof>
35 ;;; Time-stamp: <2003-02-15 00:09:55 foof>
36 ;;; Author: Alex Shinn <[email protected]>
37
38 ;;; Modified by Shiro Kawai
39 ;;; - added lcs-fold and rewrote lcs-edit-list using lcs-fold
40 ;;; - replaced base algorithm from DP to Myers'
41
42 (define-module util.lcs
43 (use gauche.sequence)
44 (use gauche.record)
45 (use scheme.list)
46 (use util.match)
47 (export lcs lcs-with-positions lcs-fold lcs-edit-list
48 lcs-edit-list/context lcs-edit-list/unified))
49 (select-module util.lcs)
50
51 ;; The base algorithm. This code implements
52 ;; Eugene Myers, "An O(ND) Difference Algorithm and Its Variations",
53 ;; Algorithmica Vol. 1 No. 2, 1986, pp. 251-266.
54 ;; It takes O((M+N)D) time and O((M+N)L) space, where
55 ;; N = (length a), M = (length b), D is the length of the smallest edit
56 ;; sequence (SES), and L is the length of the longest common subsequence (LCS).
57 ;; In most applications the difference is small, so it is much better than
58 ;; DP algorithm that is generally O(MN) time and space complextiy.
59 ;; The worst case where a and b totally differ is O((M+N)^2).
60 ;; The Myers's paper gives refinement of the algorithm
61 ;; that improves worst case behavior, but I don't implement it yet. --[SK]
62
63 (define (lcs-with-positions a-ls b-ls :optional (eq equal?))
64 (let* ((A (list->vector a-ls))
65 (B (list->vector b-ls))
66 (N (vector-length A))
67 (M (vector-length B))
68 (M+N (+ N M))
69 (V_d (make-vector (+ (* 2 M+N) 1) 0))
70 (V_r (make-vector (+ (* 2 M+N) 1) '()))
71 (V_l (make-vector (+ (* 2 M+N) 1) 0)))
72
73 (let-syntax ((vd
74 (syntax-rules ()
75 ((vd i) (vector-ref V_d (+ i M+N)))
76 ((vd i x) (vector-set! V_d (+ i M+N) x))))
77 (vr
78 (syntax-rules ()
79 ((vr i) (vector-ref V_r (+ i M+N)))
80 ((vr i x) (vector-set! V_r (+ i M+N) x))))
81 (vl
82 (syntax-rules ()
83 ((vl i) (vector-ref V_l (+ i M+N)))
84 ((vl i x) (vector-set! V_l (+ i M+N) x)))))
85
86 (define (finish)
87 (let loop ((i (- M+N)) (maxl 0) (r '()))
88 (cond ((> i M+N) (list maxl (reverse! r)))
89 ((> (vl i) maxl)
90 (loop (+ i 1) (vl i) (vr i)))
91 (else
92 (loop (+ i 1) maxl r)))))
93
94 (if (zero? M+N)
95 '(0 ()) ;; boundary case
96 (let d-loop ((d 0))
97 (if (> d M+N)
98 (error "lcs-with-positions; something's wrong (implementation error?)")
99 (let k-loop ((k (- d)))
100 (if (> k d)
101 (d-loop (+ d 1))
102 (receive (x l r)
103 (if (or (= k (- d))
104 (and (not (= k d))
105 (< (vd (- k 1)) (vd (+ k 1)))))
106 (values (vd (+ k 1)) (vl (+ k 1)) (vr (+ k 1)))
107 (values (+ (vd (- k 1)) 1) (vl (- k 1)) (vr (- k 1))))
108 (receive (x y l r)
109 (let xy-loop ((x x) (y (- x k)) (l l) (r r))
110 (cond ((>= x N) (values x y l r))
111 ((>= y M) (values x y l r))
112 ((eq (vector-ref A x) (vector-ref B y))
113 (xy-loop (+ x 1) (+ y 1) (+ l 1)
114 (cons (list (vector-ref A x) x y)
115 r)))
116 (else (values x y l r))))
117 (vd k x)
118 (vr k r)
119 (vl k l)
120 (if (and (>= x N) (>= y M))
121 (finish)
122 (k-loop (+ k 2))))
123 )))
124 )))
125 )))
126
127 ;; Just returns the LCS
128 (define (lcs a b :optional (eq equal?))
129 (map car (cadr (lcs-with-positions a b eq))))
130
131 ;; Fundamental iterator to deal with editlist.
132 ;; Similar to Perl's Algorith::Diff's traverse_sequence.
133 (define (lcs-fold a-only b-only both seed a b :optional (eq equal?))
134 (let1 common (cadr (lcs-with-positions a b eq))
135 ;; Calculates edit-list from the LCS.
136 ;; Loop parameters:
137 ;; common - list of common elements
138 ;; seed - seed value
139 ;; a - head of sequence a
140 ;; a-pos - current position count of sequence a
141 ;; b - head of sequence b
142 ;; b-pos - current position count of sequence b
143 (let loop ((common common) (seed seed)
144 (a a) (a-pos 0) (b b) (b-pos 0))
145 (if (null? common)
146 ;; No more common elements. Fold the tail of a and b.
147 (fold b-only (fold a-only seed a) b)
148 ;; We have a common element.
149 (let* ((elt (car common))
150 (a-off (cadr elt))
151 (a-skip (- a-off a-pos))
152 (b-off (caddr elt))
153 (b-skip (- b-off b-pos)))
154 (let-values (((a-head a-tail) (split-at a a-skip))
155 ((b-head b-tail) (split-at b b-skip)))
156 (loop (cdr common)
157 (both (car elt)
158 (fold b-only (fold a-only seed a-head) b-head))
159 (cdr a-tail) (+ a-off 1) (cdr b-tail) (+ b-off 1)))))
160 )
161 ))
162
163 ;; Returns an 'edit-list', which is a list of command sequences
164 ;; that turns the sequence a to the sequence b.
165 ;; The return value is a list of hunks, where each hunk is a
166 ;; list of edit commands, (<command> <index> <element>).
167
168 (define (lcs-edit-list a b . opt-eq)
169 (define a-pos -1) ;; we use pre-increment, so begin from -1.
170 (define b-pos -1) ;; ditto
171 (define hunks '())
172 (let1 last
173 (apply lcs-fold
174 (lambda (elt hunk) ;; a-only - remove
175 (inc! a-pos) `((- ,a-pos ,elt) ,@hunk))
176 (lambda (elt hunk) ;; b-only - add
177 (inc! b-pos) `((+ ,b-pos ,elt) ,@hunk))
178 (lambda (elt hunk) ;; same - reset hunks
179 (inc! a-pos) (inc! b-pos)
180 (unless (null? hunk) (push! hunks (reverse! hunk)))
181 '())
182 '()
183 a b opt-eq)
184 (unless (null? last) (push! hunks (reverse! last))))
185 (reverse! hunks))
186
187 ;; lcs-edit-list/context
188 ;; Similar to 'lcs-edit-list', but each hunk is surrounded by
189 ;; CONTEXT-SIZE elements that are common to both input.
190 ;;
191 ;; Returns a list of hunks. Each hunk has a form:
192 ;;
193 ;; #((<A-start-pos> <A-end-pos> (<sign> <elt>) ...)
194 ;; (<B-start-pos> <B-end-pos> (<sign> <elt>) ...))
195 ;;
196 ;; where <sign> may be one of the followings.
197 ;; = (common),
198 ;; + (inserted, only appear in B elements),
199 ;; - (deleted, only appear in A elements),
200 ;; ! (replaced, appears in both).
201 ;;
202 ;; The position is 0-origin. Start-pos is inclusive, end-pos is excluisve.
203 ;;
204 ;; Strategy:
205 ;; In the first pass, we create a bidirectional graph of nodes
206 ;; #(item a-pos a-prev a-next b-pos b-prev b-next)
207 ;; In the second pass, we extract hunks from the nodes.
208
209 (define-record-type (Node (pseudo-rtd <vector>)) %make-node #f
210 item
211 (a-pos)
212 (a-prev)
213 (a-next)
214 (b-pos)
215 (b-prev)
216 (b-next))
217
218 (define (make-node item a-pos b-pos)
219 (%make-node item a-pos #f #f b-pos #f #f))
220
221 ;; The graph begins with head node, and end with tail node, both have
222 ;; #f in the item field.
223 (define (build-graph a b eq)
224 (rlet1 head (make-node #f -1 -1)
225 ;; The seed value is (<tip-of-a-graph> . <tip-of-b-graph>)
226 (define (a-tip tips) (car tips))
227 (define (b-tip tips) (cdr tips))
228 (let1 tips
229 (lcs-fold (^[elt tips] ;a-only
230 (let1 n (make-node elt (+ 1 (Node-a-pos (a-tip tips))) #f)
231 (Node-a-prev-set! n (a-tip tips))
232 (Node-a-next-set! (a-tip tips) n)
233 (cons n (b-tip tips))))
234 (^[elt tips] ;b-only
235 (let1 n (make-node elt #f (+ 1 (Node-b-pos (b-tip tips))))
236 (Node-b-prev-set! n (b-tip tips))
237 (Node-b-next-set! (b-tip tips) n)
238 (cons (a-tip tips) n)))
239 (^[elt tips] ;common
240 (let1 n (make-node elt
241 (+ 1 (Node-a-pos (a-tip tips)))
242 (+ 1 (Node-b-pos (b-tip tips))))
243 (Node-a-prev-set! n (a-tip tips))
244 (Node-a-next-set! (a-tip tips) n)
245 (Node-b-prev-set! n (b-tip tips))
246 (Node-b-next-set! (b-tip tips) n)
247 (cons n n)))
248 (cons head head) a b eq)
249 (let1 tail (make-node #f
250 (+ 1 (Node-a-pos (a-tip tips)))
251 (+ 1 (Node-b-pos (b-tip tips))))
252 (Node-a-prev-set! tail (a-tip tips))
253 (Node-a-next-set! (a-tip tips) tail)
254 (Node-b-prev-set! tail (b-tip tips))
255 (Node-b-next-set! (b-tip tips) tail)))))
256
257 (define (split-point? node)
258 (not (eq? (Node-a-next node) (Node-b-next node))))
259
260 (define (common-node? node) ; node is any node but head
261 (and (Node-a-prev node) (Node-b-prev node)))
262
263 (define (anchor-node? node) (not (Node-item node)))
264
265 ;; Returns a node where a and b diverges. Returns #f if it reaches
266 ;; the end of the grpah.
267 (define (find-split-point node)
268 (cond [(or (not (Node-a-next node)) (not (Node-b-next node))) #f]
269 [(split-point? node) node]
270 [else (find-split-point (Node-a-next node))]))
271
272 ;; node must be common to both a-path and b-path. go down the
273 ;; common path, up to N nodes, and returns the last common node.
274 ;; If the paths splits before N nodes, returns the split point node.
275 (define (forward-path node n)
276 (cond [(zero? n) node]
277 [(or (not (Node-a-next node)) (not (Node-b-next node))) node]
278 [(split-point? node) node]
279 [else (forward-path (Node-a-next node) (- n 1))]))
280
281 ;; node must be common to both paths. go back upstream up to N nodes.
282 (define (backward-path node n)
283 (cond [(zero? n) node]
284 [(not (eq? (Node-a-prev node) (Node-b-prev node))) node]
285 [(not (Node-a-prev node)) node]
286 [else (backward-path (Node-a-prev node) (- n 1))]))
287
288 ;; Starting from a split-point node, find a merge-point node.
289 ;; There's always a merge-point (since we have a commin tail node).
290 (define (find-merge-point node)
291 (define (loop a-node)
292 (if (common-node? a-node)
293 a-node
294 (loop (Node-a-next a-node))))
295 (loop (Node-a-next node)))
296
297 ;;Starting from the given common node, extract a next hunk if any.
298 (define (find-hunk node maker context-size)
299 (if-let1 start (find-split-point node)
300 (let loop ([hd start])
301 (let* ([tl (find-merge-point hd)]
302 [next (forward-path tl (- (* 2 context-size) 1))])
303 (if (split-point? next)
304 (loop next) ; continue
305 ;; Need -1, for 'start' and 'next' are both common node.
306 (values (maker (backward-path start (- context-size 1))
307 (forward-path tl (- context-size 1)))
308 next))))
309 (values #f #f)))
310
311 (define (make-context-hunk start-node end-node)
312 (define (gather this-next other-next sign)
313 (let rec ([n start-node]
314 [change? (and (anchor-node? start-node)
315 (not (common-node? (other-next start-node))))])
316 (let1 tail (cond [(eq? n end-node) '()]
317 [(other-next n)
318 => (^[nn]
319 (if (common-node? nn)
320 (rec (this-next n) #f)
321 (rec (this-next n) #t)))]
322 [else (rec (this-next n) change?)])
323 (cond [(anchor-node? n) tail]
324 [(common-node? n) `((= ,(Node-item n)) ,@tail)]
325 [change? `((! ,(Node-item n)) ,@tail)]
326 [else `((,sign ,(Node-item n)) ,@tail)]))))
327 (define (make-half-hunk this-pos this-next other-next sign)
328 (let ([start-index (if (anchor-node? start-node)
329 0
330 (this-pos start-node))]
331 [end-index (if (anchor-node? end-node)
332 (this-pos end-node)
333 (+ 1 (this-pos end-node)))]
334 [path (gather this-next other-next sign)])
335 (list* start-index end-index path)))
336
337 (vector (make-half-hunk Node-a-pos Node-a-next Node-b-next '-)
338 (make-half-hunk Node-b-pos Node-b-next Node-a-next '+)))
339
340 ;; API
341 (define (lcs-edit-list/context a b :optional (eq equal?)
342 :key (context-size 3))
343 (assume (and (exact-integer? context-size)
344 (<= 1 context-size)))
345 (let1 graph (build-graph a b eq)
346 (let loop ([hunks '()] [next graph])
347 (receive (hunk next) (find-hunk next make-context-hunk context-size)
348 (if hunk
349 (loop (cons hunk hunks) next)
350 (reverse hunks))))))
351
352 ;; lcs-edit-list/unified
353 ;;
354 ;; Hunk format
355 ;; #(<a-start> <a-len> <b-start> <b-len> (<edit> ...))
356 ;;
357 ;; <edit> : (= <element>)
358 ;; | (- <element>)
359 ;; | (+ <element>)
360 ;;
361
362 ;; API
363 (define (lcs-edit-list/unified a b :optional (eq equal?)
364 :key (context-size 3))
365 (define (make-unified-hunk start-node end-node)
366 (define (common n rs)
367 (let1 rs (if (anchor-node? n) rs `((= ,(Node-item n)) ,@rs))
368 (if (eq? n end-node)
369 (reverse rs)
370 (let ([a (Node-a-next n)]
371 [b (Node-b-next n)])
372 (if (eq? a b)
373 (common a rs)
374 (a-only a b rs))))))
375 (define (a-only n b rs)
376 (if (common-node? n)
377 (b-only b rs)
378 (a-only (Node-a-next n) b `((- ,(Node-item n)) ,@rs))))
379 (define (b-only n rs)
380 (if (common-node? n)
381 (common n rs)
382 (b-only (Node-b-next n) `((+ ,(Node-item n)) ,@rs))))
383 (define (start-index n pos)
384 (if (anchor-node? n) (+ 1 (pos n)) (pos n)))
385 (define (end-index n pos)
386 (if (anchor-node? n) (pos n) (+ 1 (pos n))))
387 (define (hunk-size s e pos)
388 (- (end-index e pos) (start-index s pos)))
389
390 `#(,(start-index start-node Node-a-pos)
391 ,(hunk-size start-node end-node Node-a-pos)
392 ,(start-index start-node Node-b-pos)
393 ,(hunk-size start-node end-node Node-b-pos)
394 ,(common start-node '())))
395
396 (assume (and (exact-integer? context-size)
397 (<= 1 context-size)))
398 (let1 graph (build-graph a b eq)
399 (let loop ([hunks '()] [next graph])
400 (receive (hunk next) (find-hunk next make-unified-hunk context-size)
401 (if hunk
402 (loop (cons hunk hunks) next)
403 (reverse hunks))))))