| 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)))))) |