Debian Codegraph @

libsrc/text/gap-buffer.scm

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