| 1 |
;;; |
| 2 |
;;; text.gap-buffer - gap-buffer for character array |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2015-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 |
;; A simple gap-buffer implementation for the back-end of |
| 35 |
;; text editor/viewer. |
| 36 |
|
| 37 |
;; For the time being, we naively use flat vector for the buf. |
| 38 |
;; It isn't gc-friendly, especially when the buffer is large. If |
| 39 |
;; it becomes an issue, we'll employ more sophisticated structure. |
| 40 |
|
| 41 |
(define-module text.gap-buffer |
| 42 |
(use gauche.uvector) |
| 43 |
(use gauche.generator) |
| 44 |
(use util.match) |
| 45 |
(export make-gap-buffer string->gap-buffer gap-buffer-copy |
| 46 |
gap-buffer? gap-buffer-capacity gap-buffer-content-length |
| 47 |
gap-buffer-pos gap-buffer-pos-at-end? gap-buffer-gap-at? |
| 48 |
gap-buffer-ref gap-buffer-move! |
| 49 |
gap-buffer-insert! gap-buffer-delete! gap-buffer-replace! |
| 50 |
gap-buffer-clear! |
| 51 |
gap-buffer-contains gap-buffer-looking-at? |
| 52 |
gap-buffer-edit! |
| 53 |
gap-buffer->generator gap-buffer->string) |
| 54 |
) |
| 55 |
(select-module text.gap-buffer) |
| 56 |
|
| 57 |
(define-class <gap-buffer> () |
| 58 |
([buffer :init-keyword :buffer] |
| 59 |
[gap-start :init-keyword :gap-start] |
| 60 |
[gap-end :init-keyword :gap-end])) |
| 61 |
|
| 62 |
(define-inline (%gbuf-size gbuf) (u32vector-length (~ gbuf'buffer))) |
| 63 |
(define-inline (%gbuf-content-length gbuf) |
| 64 |
(- (%gbuf-size gbuf) |
| 65 |
(- (~ gbuf'gap-end) (~ gbuf'gap-start)))) |
| 66 |
(define-inline (%gbuf-index gbuf i) |
| 67 |
(let1 s (~ gbuf'gap-start) |
| 68 |
(if (< i s) i (+ i (- (~ gbuf'gap-end) s))))) |
| 69 |
|
| 70 |
;; API |
| 71 |
(define (gap-buffer? obj) (is-a? obj <gap-buffer>)) |
| 72 |
|
| 73 |
;; API |
| 74 |
(define (gap-buffer-pos gbuf) |
| 75 |
(assume-type gbuf <gap-buffer>) |
| 76 |
(~ gbuf'gap-start)) |
| 77 |
|
| 78 |
;; API |
| 79 |
;; Trivial, but useful. |
| 80 |
(define (gap-buffer-pos-at-end? gbuf pos) |
| 81 |
(assume-type gbuf <gap-buffer>) |
| 82 |
(= pos (%gbuf-content-length gbuf))) |
| 83 |
|
| 84 |
;; API |
| 85 |
;; Trivial, but useful. |
| 86 |
(define (gap-buffer-gap-at? gbuf whence) |
| 87 |
(case whence |
| 88 |
[(beginning) (= (~ gbuf'gap-start) 0)] |
| 89 |
[(end) (= (~ gbuf'gap-end) (%gbuf-size gbuf))] |
| 90 |
[else (error "either a symbol `beginning' or `end' requierd, \ |
| 91 |
but got:" whence)])) |
| 92 |
|
| 93 |
;; API |
| 94 |
(define (gap-buffer-ref gbuf index :optional (fallback (undefined))) |
| 95 |
(define (oob) |
| 96 |
(if (undefined? fallback) |
| 97 |
(error "index out of range:" index) |
| 98 |
fallback)) |
| 99 |
(define (ret i) (integer->char (~ gbuf'buffer i))) |
| 100 |
(cond [(< index 0) (oob)] |
| 101 |
[(< index (~ gbuf'gap-start)) (ret index)] |
| 102 |
[(< index (%gbuf-content-length gbuf)) |
| 103 |
(ret (+ index (- (~ gbuf'gap-end) (~ gbuf'gap-start))))] |
| 104 |
[else (oob)])) |
| 105 |
|
| 106 |
;; API |
| 107 |
(define (gap-buffer-set! gbuf index char) |
| 108 |
(cond [(< index 0) (error "index out of range:" index)] |
| 109 |
[(< index (~ gbuf'gap-start)) |
| 110 |
(set! (~ gbuf'buffer index) (char->integer char))] |
| 111 |
[(< index (%gbuf-content-length gbuf)) |
| 112 |
(set! (~ gbuf'buffer (+ index (- (~ gbuf'gap-end) |
| 113 |
(~ gbuf'gap-start)))) |
| 114 |
(char->integer char))] |
| 115 |
[else (error "index out of range:" index)])) |
| 116 |
|
| 117 |
;; API |
| 118 |
(define (gap-buffer-capacity gbuf) |
| 119 |
(assume-type gbuf <gap-buffer>) |
| 120 |
(%gbuf-size gbuf)) |
| 121 |
|
| 122 |
;; API |
| 123 |
(define (gap-buffer-content-length gbuf) |
| 124 |
(assume-type gbuf <gap-buffer>) |
| 125 |
(%gbuf-content-length gbuf)) |
| 126 |
|
| 127 |
;; Returns gap-start and gap-end index |
| 128 |
(define (%calculate-gap-position source-len buffer-len pos whence) |
| 129 |
(let1 gap-start (case whence |
| 130 |
[(beginning) pos] |
| 131 |
[(end) (- source-len pos)] |
| 132 |
[else |
| 133 |
(error "either a symbol `beginning' or `end' required, \ |
| 134 |
but got:" whence)]) |
| 135 |
(unless (<= 0 gap-start source-len) |
| 136 |
(errorf "position ~a from ~a is out of bound of the source" |
| 137 |
pos whence)) |
| 138 |
(values gap-start (- buffer-len (- source-len gap-start))))) |
| 139 |
|
| 140 |
;; API |
| 141 |
(define (make-gap-buffer :key (initial-capacity 8)) |
| 142 |
(let1 len (expt 2 (integer-length (- initial-capacity 1))) ;make sure 2^n |
| 143 |
(make <gap-buffer> |
| 144 |
:buffer (make-u32vector len) |
| 145 |
:gap-start 0 |
| 146 |
:gap-end len))) |
| 147 |
|
| 148 |
;; API |
| 149 |
(define (string->gap-buffer string |
| 150 |
:optional (pos 0) (whence 'end) |
| 151 |
(start 0) (end (undefined))) |
| 152 |
(let* ([slen (string-length string)] |
| 153 |
[source (if (undefined? end) |
| 154 |
(if (= start 0) |
| 155 |
string |
| 156 |
(string-copy string start)) |
| 157 |
(string-copy string start end))] |
| 158 |
[bufsiz (expt 2 (integer-length (string-length source)))] |
| 159 |
[buf (make-u32vector bufsiz 0)]) |
| 160 |
(receive (gap-start gap-end) (%calculate-gap-position (string-length source) |
| 161 |
bufsiz pos whence) |
| 162 |
(string->u32vector! buf 0 source 0 gap-start) |
| 163 |
(string->u32vector! buf gap-end source gap-start) |
| 164 |
(make <gap-buffer> |
| 165 |
:buffer buf :gap-start gap-start :gap-end gap-end)))) |
| 166 |
|
| 167 |
;; API |
| 168 |
(define (gap-buffer-copy gbuf) |
| 169 |
(make <gap-buffer> |
| 170 |
:buffer (u32vector-copy (~ gbuf'buffer)) |
| 171 |
:gap-start (~ gbuf'gap-start) |
| 172 |
:gap-end (~ gbuf'gap-end))) |
| 173 |
|
| 174 |
;; API |
| 175 |
(define (gap-buffer-move! gbuf pos :optional (whence 'beginning)) |
| 176 |
(let ([abspos (case whence |
| 177 |
[(beginning) pos] |
| 178 |
[(current) (+ pos (~ gbuf 'gap-start))] |
| 179 |
[(end) (+ pos (%gbuf-content-length gbuf))] |
| 180 |
[else (errorf "position ~a from ~a is out of buffer" |
| 181 |
pos whence)])] |
| 182 |
[start (~ gbuf 'gap-start)] |
| 183 |
[end (~ gbuf 'gap-end)] |
| 184 |
[buf (~ gbuf 'buffer)]) |
| 185 |
(cond [(< abspos start) |
| 186 |
(let1 newend (- end (- start abspos)) |
| 187 |
(u32vector-copy! buf newend buf abspos start) |
| 188 |
(set! (~ gbuf 'gap-start) abspos) |
| 189 |
(set! (~ gbuf 'gap-end) newend))] |
| 190 |
[(> abspos start) |
| 191 |
(let1 newend (+ end (- abspos start)) |
| 192 |
(u32vector-copy! buf start buf end newend) |
| 193 |
(set! (~ gbuf 'gap-start) abspos) |
| 194 |
(set! (~ gbuf 'gap-end) newend))]) |
| 195 |
gbuf)) |
| 196 |
|
| 197 |
;; API |
| 198 |
;; content can be a string or a char |
| 199 |
(define (gap-buffer-insert! gbuf content) |
| 200 |
(let ([clen (cond [(string? content) (string-length content)] |
| 201 |
[(char? content) 1] |
| 202 |
[else (error "string or char required, but got:" content)])] |
| 203 |
[start (~ gbuf'gap-start)] |
| 204 |
[end (~ gbuf'gap-end)]) |
| 205 |
(if (< (- end start) clen) |
| 206 |
(gap-buffer-insert! (%gap-buffer-extend! gbuf) content) |
| 207 |
(cond [(string? content) |
| 208 |
(string->u32vector! (~ gbuf'buffer) start content) |
| 209 |
(set! (~ gbuf'gap-start) (+ start clen))] |
| 210 |
[else |
| 211 |
(u32vector-set! (~ gbuf'buffer) start (char->integer content)) |
| 212 |
(set! (~ gbuf'gap-start) (+ start 1))]))) |
| 213 |
gbuf) |
| 214 |
|
| 215 |
(define (%gap-buffer-extend! gbuf) |
| 216 |
(let* ([oldbuf (~ gbuf'buffer)] |
| 217 |
[oldlen (u32vector-length oldbuf)] |
| 218 |
[newlen (* 2 oldlen)] |
| 219 |
[newbuf (make-u32vector newlen 0)] |
| 220 |
[newend (+ (~ gbuf'gap-end) oldlen)]) |
| 221 |
(u32vector-copy! newbuf 0 oldbuf 0 (~ gbuf'gap-start)) |
| 222 |
(u32vector-copy! newbuf newend oldbuf (~ gbuf'gap-end)) |
| 223 |
(set! (~ gbuf'buffer) newbuf) |
| 224 |
(set! (~ gbuf'gap-end) newend) |
| 225 |
gbuf)) |
| 226 |
|
| 227 |
;; API |
| 228 |
(define (gap-buffer-delete! gbuf size) |
| 229 |
(let1 newend (+ (~ gbuf'gap-end) size) |
| 230 |
(when (< (%gbuf-size gbuf) newend) |
| 231 |
(error "deletion size too big:" size)) |
| 232 |
(set! (~ gbuf'gap-end) newend) |
| 233 |
gbuf)) |
| 234 |
|
| 235 |
;; API |
| 236 |
(define (gap-buffer-clear! gbuf) |
| 237 |
(set! (~ gbuf'gap-start) 0) |
| 238 |
(set! (~ gbuf'gap-end) (%gbuf-size gbuf))) |
| 239 |
|
| 240 |
;; API |
| 241 |
;; Delete SIZE from the current pos, then insert content. |
| 242 |
;; For the convenience. |
| 243 |
(define (gap-buffer-replace! gbuf size content) |
| 244 |
(gap-buffer-delete! gbuf size) |
| 245 |
(gap-buffer-insert! gbuf content)) |
| 246 |
|
| 247 |
;; API |
| 248 |
;; This is higher-level API, with undo feature. |
| 249 |
;; |
| 250 |
;; EDIT-COMMAND is one of the followings: |
| 251 |
;; |
| 252 |
;; (i <pos> <string>) Insert string at <pos> |
| 253 |
;; (d <pos> <length>) Delete <length> chars from <pos> |
| 254 |
;; (c <pos> <length> <string>) Substitute <length> chars from <pos> |
| 255 |
;; for <string> |
| 256 |
;; |
| 257 |
;; <pos> can be #f, in that case the current position is used. |
| 258 |
;; |
| 259 |
;; It returns another edit-command that undo the change when given to |
| 260 |
;; gap-buffer-edit!. |
| 261 |
(define (gap-buffer-edit! gbuf edit-command) |
| 262 |
(define (mov! pos) |
| 263 |
(when (and pos (not (= pos (gap-buffer-pos gbuf)))) |
| 264 |
(gap-buffer-move! gbuf pos)) |
| 265 |
(gap-buffer-pos gbuf)) |
| 266 |
(match edit-command |
| 267 |
[('i pos str) |
| 268 |
(let ([cpos (mov! pos)]) |
| 269 |
(gap-buffer-insert! gbuf str) |
| 270 |
`(d ,cpos ,(string-length str)))] |
| 271 |
[('d pos len) |
| 272 |
(let* ([cpos (mov! pos)] |
| 273 |
[s (gap-buffer->string gbuf cpos (+ cpos len))]) |
| 274 |
(gap-buffer-delete! gbuf len) |
| 275 |
`(i ,cpos ,s))] |
| 276 |
[('c pos len str) |
| 277 |
(let* ([cpos (mov! pos)] |
| 278 |
[s (gap-buffer->string gbuf cpos (+ cpos len))]) |
| 279 |
(gap-buffer-replace! gbuf len str) |
| 280 |
`(c ,cpos ,(string-length str) ,s))] |
| 281 |
[_ (error "Invalid edit-command:" edit-command)])) |
| 282 |
|
| 283 |
;; API |
| 284 |
;; NB: For better performance, we don't consider the case when gbuf is |
| 285 |
;; modified during traversal. |
| 286 |
(define (gap-buffer->generator gbuf :optional (start 0) (end (undefined))) |
| 287 |
(let ([count (- (min (%gbuf-content-length gbuf) |
| 288 |
(if (undefined? end) +inf.0 end)) |
| 289 |
start)] |
| 290 |
[gap-start (~ gbuf'gap-start)] |
| 291 |
[gap-skip (- (~ gbuf'gap-end) (~ gbuf'gap-start))] |
| 292 |
[index start]) |
| 293 |
(when (< count 0) |
| 294 |
(error "start index is too large:" start)) |
| 295 |
(^[] |
| 296 |
(cond [(zero? count) (eof-object)] |
| 297 |
[(< index gap-start) |
| 298 |
(begin0 (integer->char (u32vector-ref (~ gbuf'buffer) index)) |
| 299 |
(dec! count) |
| 300 |
(inc! index))] |
| 301 |
[else |
| 302 |
(let1 xindex (+ index gap-skip) |
| 303 |
(if (< xindex (%gbuf-size gbuf)) |
| 304 |
(begin0 (integer->char (u32vector-ref (~ gbuf'buffer) xindex)) |
| 305 |
(dec! count) |
| 306 |
(inc! index)) |
| 307 |
(begin (set! count 0) (eof-object))))])))) |
| 308 |
|
| 309 |
;; API |
| 310 |
(define (gap-buffer->string gbuf :optional (start 0) (end (undefined))) |
| 311 |
(let1 g (gap-buffer->generator gbuf start end) |
| 312 |
(with-output-to-string (^[] (generator-for-each display g))))) |
| 313 |
|
| 314 |
;; API |
| 315 |
;; Search string STR in GBUF, returns its starting index if found, |
| 316 |
;; #f if not. |
| 317 |
(define (gap-buffer-contains gbuf str |
| 318 |
:optional (gstart 0) (gend #f) sstart send) |
| 319 |
(assume-type gbuf <gap-buffer>) |
| 320 |
(assume-type str <string>) |
| 321 |
(let* ([needle (string->u32vector (opt-substring str sstart send))] |
| 322 |
[needlelen (u32vector-length needle)] |
| 323 |
[buf (~ gbuf'buffer)] |
| 324 |
[ilimit (- (or gend (%gbuf-content-length gbuf)) needlelen)] |
| 325 |
[gap-start (~ gbuf'gap-start)] |
| 326 |
[gap-end (~ gbuf'gap-end)]) |
| 327 |
;; We could adopt better algorithm like KMP once it is necessary. |
| 328 |
;; For the time being, supposed use cases are having short STR, |
| 329 |
;; so we don't bother. |
| 330 |
(let outer ([i gstart]) |
| 331 |
(and (<= i ilimit) |
| 332 |
(let inner ([j (%gbuf-index gbuf i)] [k 0]) |
| 333 |
(if (< k needlelen) |
| 334 |
(if (eqv? (u32vector-ref buf j) (u32vector-ref needle k)) |
| 335 |
(inner (if (= j (- gap-start 1)) |
| 336 |
gap-end |
| 337 |
(+ j 1)) |
| 338 |
(+ k 1)) |
| 339 |
(outer (+ i 1))) |
| 340 |
i)))))) ;found |
| 341 |
|
| 342 |
;; API |
| 343 |
;; Returns #t iff gbuffer content immediate following the current point |
| 344 |
;; matches the given string STR. |
| 345 |
;; NB: Emacs's looking-at takes regexp. We may extend this to do so later, |
| 346 |
;; though |
| 347 |
(define (gap-buffer-looking-at? gbuf str :optional (point #f)) |
| 348 |
(assume-type gbuf <gap-buffer>) |
| 349 |
(assume-type str <string>) |
| 350 |
(let* ([needle (string->u32vector str)] |
| 351 |
[needlelen (u32vector-length needle)] |
| 352 |
[buf (~ gbuf'buffer)] |
| 353 |
[gap-start (~ gbuf'gap-start)] |
| 354 |
[gap-end (~ gbuf'gap-end)] |
| 355 |
[point (or point gap-start)]) |
| 356 |
(and (<= point (- (%gbuf-content-length gbuf) needlelen)) |
| 357 |
(let loop ([j (%gbuf-index gbuf point)] [k 0]) |
| 358 |
(or (= k needlelen) |
| 359 |
(and (eqv? (u32vector-ref buf j) (u32vector-ref needle k)) |
| 360 |
(loop (if (= j (- gap-start 1)) |
| 361 |
gap-end |
| 362 |
(+ j 1)) |
| 363 |
(+ k 1)))))))) |