/[cmucl]/src/hemlock/completion.lisp
ViewVC logotype

Contents of /src/hemlock/completion.lisp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.1 - (show annotations)
Wed May 9 13:03:21 1990 UTC (23 years, 11 months ago) by ram
Branch: MAIN
Initial revision
1 ;;; -*- Log: hemlock.log; Package: Hemlock -*-
2 ;;;
3 ;;; **********************************************************************
4 ;;; This code was written as part of the Spice Lisp project at
5 ;;; Carnegie-Mellon University, and has been placed in the public domain.
6 ;;; Spice Lisp is currently incomplete and under active development.
7 ;;; If you want to use this code or any part of Spice Lisp, please contact
8 ;;; Scott Fahlman (FAHLMAN@CMUC).
9 ;;; **********************************************************************
10 ;;;
11 ;;; Written by Skef Wholey and Blaine Burks.
12 ;;; General idea stolen from Jim Salem's TMC LISPM completion code.
13 ;;;
14
15 (in-package "HEMLOCK")
16
17
18
19 ;;;; The Completion Database.
20
21 ;;; The top level structure here is an array that gets indexed with the
22 ;;; first three characters of the word to be completed. That will get us to
23 ;;; a list of the strings with that prefix sorted in most-recently-used order.
24 ;;; The number of strings in any given bucket will never exceed
25 ;;; Completion-Bucket-Size-Limit. Strings are stored in the database in
26 ;;; lowercase form always.
27
28 (defconstant completion-table-size 991)
29
30 (defvar *completions* (make-array completion-table-size))
31
32 (defhvar "Completion Bucket Size"
33 "This limits the number of completions saved for a particular combination of
34 the first three letters of any word."
35 :value 20)
36
37
38 ;;; Mapping strings into buckets.
39
40 ;;; The characters that are considered parts of "words" change from mode
41 ;;; to mode.
42 ;;;
43 (defattribute "Completion Wordchar"
44 "1 for characters we consider to be constituents of words.")
45
46 (defconstant default-other-wordchars
47 '(#\- #\* #\' #\_))
48
49 (do-alpha-chars (char :both)
50 (setf (character-attribute :completion-wordchar char) 1))
51
52 (dolist (char '(#\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9))
53 (setf (character-attribute :completion-wordchar char) 1))
54
55 (dolist (char default-other-wordchars)
56 (setf (character-attribute :completion-wordchar char) 1))
57
58
59 ;;; The difference between Lisp mode and the other modes is pretty radical in
60 ;;; this respect. These are interesting too, but they're on by default: #\*,
61 ;;; #\-, and #\_. #\' is on by default too, but it's uninteresting in "Lisp"
62 ;;; mode.
63 ;;;
64 (defconstant default-lisp-wordchars
65 '(#\~ #\! #\@ #\$ #\% #\^ #\& #\+ #\= #\: #\< #\> #\. #\/ #\?))
66
67 (dolist (char default-lisp-wordchars)
68 (shadow-attribute :completion-wordchar char 1 "Lisp"))
69
70 (shadow-attribute :completion-wordchar #\' 0 "Lisp")
71
72 (defmacro completion-char-p (char)
73 `(= (the fixnum (character-attribute :completion-wordchar ,char)) 1))
74
75 ;;; COMPLETION-BUCKET-FOR returns the Completion-Bucket that might hold a
76 ;;; completion for the given String. With optional Value, sets the bucket.
77 ;;;
78 (defun completion-bucket-for (string length &optional (value nil value-p))
79 (declare (simple-string string)
80 (fixnum length))
81 (when (and (>= length 3)
82 (completion-char-p (char string 0))
83 (completion-char-p (char string 1))
84 (completion-char-p (char string 2)))
85 (let ((index (mod (logxor (ash
86 (logxor
87 (ash (hi::search-hash-code (schar string 0))
88 5)
89 (hi::search-hash-code (schar string 1)))
90 3)
91 (hi::search-hash-code (schar string 2)))
92 completion-table-size)))
93 (declare (fixnum index))
94 (if value-p
95 (setf (svref *completions* index) value)
96 (svref *completions* index)))))
97
98 (defsetf completion-bucket-for completion-bucket-for)
99
100
101 ;;; FIND-COMPLETION returns the most recent string matching the given
102 ;;; Prefix, or Nil if nothing appropriate is in the database. We assume
103 ;;; the Prefix is passed to us in lowercase form so we can use String=. If
104 ;;; we find something appropriate, we bring it to the front of the list.
105 ;;; Prefix-Length, if supplied restricts us to look at just the start of
106 ;;; the string...
107 ;;;
108 (defun find-completion (prefix &optional (prefix-length (length prefix)))
109 (declare (simple-string prefix)
110 (fixnum prefix-length))
111 (let ((bucket (completion-bucket-for prefix prefix-length)))
112 (do ((list bucket (cdr list)))
113 ((null list))
114 (let ((completion (car list)))
115 (declare (simple-string completion))
116 (when (and (>= (length completion) prefix-length)
117 (string= prefix completion
118 :end1 prefix-length
119 :end2 prefix-length))
120 (unless (eq list bucket)
121 (rotatef (car list) (car bucket)))
122 (return completion))))))
123
124 ;;; RECORD-COMPLETION saves string in the completion database as the first item
125 ;;; in the bucket, that's the most recently used completion. If the bucket is
126 ;;; full, drop the oldest item in the list. If string is already in the
127 ;;; bucket, simply move it to the front. The way we move an element to the
128 ;;; front requires a full bucket to be at least three elements long.
129 ;;;
130 (defun record-completion (string)
131 (declare (simple-string string))
132 (let ((string-length (length string)))
133 (declare (fixnum string-length))
134 (when (> string-length 3)
135 (let ((bucket (completion-bucket-for string string-length))
136 (limit (value completion-bucket-size)))
137 (do ((list bucket (cdr list))
138 (last nil list)
139 (length 1 (1+ length)))
140 ((null list)
141 (setf (completion-bucket-for string string-length)
142 (cons string bucket)))
143 (cond ((= length limit)
144 (setf (car list) string)
145 (setf (completion-bucket-for string string-length) list)
146 (setf (cdr list) bucket)
147 (setf (cdr last) nil)
148 (return))
149 ((string= string (the simple-string (car list)))
150 (unless (eq list bucket)
151 (rotatef (car list) (car bucket)))
152 (return))))))))
153
154 ;;; ROTATE-COMPLETIONS rotates the completion bucket for the given Prefix.
155 ;;; We just search for the first thing in the bucket with the Prefix, then
156 ;;; move that to the end of the list. If there ain't no such thing there,
157 ;;; or if it's already at the end, we do nothing.
158 ;;;
159 (defun rotate-completions (prefix &optional (prefix-length (length prefix)))
160 (declare (simple-string prefix))
161 (let ((bucket (completion-bucket-for prefix prefix-length)))
162 (do ((list bucket (cdr list))
163 (prev nil list))
164 ((null list))
165 (let ((completion (car list)))
166 (declare (simple-string completion))
167 (when (and (>= (length completion) prefix-length)
168 (string= prefix completion
169 :end1 prefix-length :end2 prefix-length))
170 (when (cdr list)
171 (if prev
172 (setf (cdr prev) (cdr list))
173 (setf (completion-bucket-for prefix prefix-length) (cdr list)))
174 (setf (cdr (last list)) list)
175 (setf (cdr list) nil))
176 (return nil))))))
177
178
179
180 ;;;; Hemlock interface.
181
182 (defmode "Completion" :transparent-p t :precedence 10.0
183 :documentation
184 "This is a minor mode that saves words greater than three characters in length,
185 allowing later completion of those words. This is very useful for often
186 long identifiers used in Lisp code. All words with the same first three
187 letters are in one list sorted by most recently used. \"Completion Bucket
188 Size\" limits the number of completions saved in each list.")
189
190 (defcommand "Completion Mode" (p)
191 "Toggles Completion Mode in the current buffer."
192 "Toggles Completion Mode in the current buffer."
193 (declare (ignore p))
194 (setf (buffer-minor-mode (current-buffer) "Completion")
195 (not (buffer-minor-mode (current-buffer) "Completion"))))
196
197
198 ;;; Consecutive alphanumeric keystrokes that start a word cause a possible
199 ;;; completion to be displayed in the echo area's modeline, the status line.
200 ;;; Since most insertion is building up a word that was already started, we
201 ;;; keep track of the word in *completion-prefix* that the user is typing. The
202 ;;; length of the thing is kept in *completion-prefix-length*.
203 ;;;
204 (defconstant completion-prefix-max-size 100)
205
206 (defvar *completion-prefix* (make-string completion-prefix-max-size))
207
208 (defvar *completion-prefix-length* 0)
209
210
211 ;;; "Completion Self Insert" does different stuff depending on whether or
212 ;;; not the thing to be inserted is Completion-Char-P. If it is, then we
213 ;;; try to come up with a possible completion, using Last-Command-Type to
214 ;;; tense things up a bit. Otherwise, if Last-Command-Type says we were
215 ;;; just doing a word, then we record that word in the database.
216 ;;;
217 (defcommand "Completion Self Insert" (p)
218 "Insert the last character typed, showing possible completions. With prefix
219 argument insert the character that many times."
220 "Implements \"Completion Self Insert\". Calling this function is not
221 meaningful."
222 (let ((char (text-character *last-character-typed*)))
223 (unless char (editor-error "Can't insert that character."))
224 (cond ((completion-char-p char)
225 ;; If start of word not already in *completion-prefix*, put it
226 ;; there.
227 (unless (eq (last-command-type) :completion-self-insert)
228 (set-completion-prefix))
229 ;; Then add new stuff.
230 (cond ((and p (> p 1))
231 (fill *completion-prefix* (char-downcase char)
232 :start *completion-prefix-length*
233 :end (+ *completion-prefix-length* p))
234 (incf *completion-prefix-length* p))
235 (t
236 (setf (schar *completion-prefix* *completion-prefix-length*)
237 (char-downcase char))
238 (incf *completion-prefix-length*)))
239 ;; Display possible completion, if any.
240 (display-possible-completion *completion-prefix*
241 *completion-prefix-length*)
242 (setf (last-command-type) :completion-self-insert))
243 (t
244 (when (eq (last-command-type) :completion-self-insert)
245 (record-completion (subseq *completion-prefix*
246 0 *completion-prefix-length*)))))))
247
248 ;;; SET-COMPLETION-PREFIX grabs any completion-wordchars immediately before
249 ;;; point and stores these into *completion-prefix*.
250 ;;;
251 (defun set-completion-prefix ()
252 (let* ((point (current-point))
253 (point-line (mark-line point)))
254 (cond ((and (previous-character point)
255 (completion-char-p (previous-character point)))
256 (with-mark ((mark point))
257 (reverse-find-attribute mark :completion-wordchar #'zerop)
258 (unless (eq (mark-line mark) point-line)
259 (editor-error "No completion wordchars on this line!"))
260 (let ((insert-string (nstring-downcase
261 (region-to-string
262 (region mark point)))))
263 (replace *completion-prefix* insert-string)
264 (setq *completion-prefix-length* (length insert-string)))))
265 (t
266 (setq *completion-prefix-length* 0)))))
267
268
269 (defcommand "Completion Complete Word" (p)
270 "Complete the word if we've got a completion, fixing up the case. Invoking
271 this immediately in succession rotates through possible completions in the
272 buffer. If there is no currently displayed completion, this tries to choose
273 a completion from text immediately before the point and displays the
274 completion if found."
275 "Complete the word if we've got a completion, fixing up the case."
276 (declare (ignore p))
277 (let ((last-command-type (last-command-type)))
278 ;; If the user has been cursoring around and then tries to complete,
279 ;; let him.
280 ;;
281 (unless (member last-command-type '(:completion-self-insert :completion))
282 (set-completion-prefix)
283 (setf last-command-type :completion-self-insert))
284 (case last-command-type
285 (:completion-self-insert
286 (do-completion))
287 (:completion
288 (rotate-completions *completion-prefix* *completion-prefix-length*)
289 (do-completion))))
290 (setf (last-command-type) :completion))
291
292 (defcommand "List Possible Completions" (p)
293 "List all possible completions of the prefix the user has typed."
294 "List all possible completions of the prefix the user has typed."
295 (declare (ignore p))
296 (let ((last-command-type (last-command-type)))
297 (unless (member last-command-type '(:completion-self-insert :completion))
298 (set-completion-prefix))
299 (let* ((prefix *completion-prefix*)
300 (prefix-length *completion-prefix-length*)
301 (bucket (completion-bucket-for prefix prefix-length)))
302 (with-pop-up-display (s)
303 (dolist (completion bucket)
304 (when (and (> (length completion) prefix-length)
305 (string= completion prefix
306 :end1 prefix-length
307 :end2 prefix-length))
308 (write-line completion s))))))
309 ;; Keep the redisplay hook from clearing any possibly displayed completion.
310 (setf (last-command-type) :completion-self-insert))
311
312 (defvar *last-completion-mark* nil)
313
314 (defun do-completion ()
315 (let ((completion (find-completion *completion-prefix*
316 *completion-prefix-length*))
317 (point (current-point)))
318 (when completion
319 (if *last-completion-mark*
320 (move-mark *last-completion-mark* point)
321 (setq *last-completion-mark* (copy-mark point :temporary)))
322 (let ((mark *last-completion-mark*))
323 (reverse-find-attribute mark :completion-wordchar #'zerop)
324 (let* ((region (region mark point))
325 (string (region-to-string region)))
326 (declare (simple-string string))
327 (delete-region region)
328 (let* ((first (position-if #'alpha-char-p string))
329 (next (if first (position-if #'alpha-char-p string
330 :start (1+ first)))))
331 (insert-string point
332 (cond ((and first (lower-case-p (char string first)))
333 completion)
334 ((and next (lower-case-p (char string next)))
335 (word-capitalize completion))
336 (t
337 (string-upcase completion))))))))))
338
339
340 ;;; WORD-CAPITALIZE is like STRING-CAPITALIZE except that it treats apostrophes
341 ;;; the Right Way.
342 ;;;
343 (defun word-capitalize (string)
344 (let* ((length (length string))
345 (strung (make-string length)))
346 (do ((i 0 (1+ i))
347 (new-word t))
348 ((= i length))
349 (let ((char (schar string i)))
350 (cond ((or (alphanumericp char)
351 (char= char #\'))
352 (setf (schar strung i)
353 (if new-word (char-upcase char) (char-downcase char)))
354 (setq new-word nil))
355 (t
356 (setf (schar strung i) char)
357 (setq new-word t)))))
358 strung))
359
360 (defcommand "Completion Rotate Completions" (p)
361 "Show another possible completion in the status line, if there is one.
362 If there is no currently displayed completion, this tries to choose a
363 completion from text immediately before the point and displays the
364 completion if found. With an argument, rotate the completion ring that many
365 times."
366 "Show another possible completion in the status line, if there is one.
367 With an argument, rotate the completion ring that many times."
368 (unless (eq (last-command-type) :completion-self-insert)
369 (set-completion-prefix)
370 (setf (last-command-type) :completion-self-insert))
371 (dotimes (i (or p 1))
372 (rotate-completions *completion-prefix* *completion-prefix-length*))
373 (display-possible-completion *completion-prefix* *completion-prefix-length*)
374 (setf (last-command-type) :completion-self-insert))
375
376
377 ;;;; Nifty database and parsing machanisms.
378
379 (defhvar "Completion Database Filename"
380 "The file that \"Save Completions\" and \"Read Completions\" will
381 respectively write and read the completion database to and from."
382 :value nil)
383
384 (defvar *completion-default-default-database-filename*
385 "hemlock-completions.txt"
386 "The file that will be defaultly written to and read from by \"Save
387 Completions\" and \"Read Completions\".")
388
389 (defcommand "Save Completions" (p)
390 "Writes the current completion database to a file, defaultly the value of
391 \"Completion Database Filename\". With an argument, prompts for a
392 filename."
393 "Writes the current completion database to a file, defaultly the value of
394 \"Completion Database Filename\". With an argument, prompts for a
395 filename."
396 (let ((filename (or (and (not p) (value completion-database-filename))
397 (prompt-for-file
398 :must-exist nil
399 :default *completion-default-default-database-filename*
400 :prompt "File to write completions to: "))))
401 (with-open-file (s filename
402 :direction :output
403 :if-exists :rename-and-delete
404 :if-does-not-exist :create)
405 (message "Saving completions...")
406 (dotimes (i (length *completions*))
407 (let ((bucket (svref *completions* i)))
408 (when bucket
409 (write i :stream s :base 10 :radix 10)
410 (write-char #\newline s)
411 (dolist (completion bucket)
412 (write-line completion s))
413 (terpri s))))
414 (message "Done."))))
415
416 (defcommand "Read Completions" (p)
417 "Reads some completions from a file, defaultly the value of \"Completion
418 Database File\". With an argument, prompts for a filename."
419 "Reads some completions from a file, defaultly the value of \"Completion
420 Database File\". With an argument, prompts for a filename."
421 (let ((filename (or (and (not p) (value completion-database-filename))
422 (prompt-for-file
423 :must-exist nil
424 :default *completion-default-default-database-filename*
425 :prompt "File to read completions from: ")))
426 (index nil)
427 (completion nil))
428 (with-open-file (s filename :if-does-not-exist :error)
429 (message "Reading in completions...")
430 (loop
431 (let ((new-completions '()))
432 (unless (setf index (read-preserving-whitespace s nil nil))
433 (return))
434 ;; Zip past the newline that I know is directly after the number.
435 ;; All this to avoid consing. I love it.
436 (read-char s)
437 (loop
438 (setf completion (read-line s))
439 (when (string= completion "") (return))
440 (unless (member completion (svref *completions* index))
441 (push completion new-completions)))
442 (let ((new-bucket (nconc (nreverse new-completions)
443 (svref *completions* index))))
444 (setf (svref *completions* index) new-bucket)
445 (do ((completion new-bucket (cdr completion))
446 (end (1- (value completion-bucket-size)))
447 (i 0 (1+ i)))
448 ((endp completion))
449 (when (= i end) (setf (cdr completion) nil))))))
450 (message "Done."))))
451
452 (defcommand "Parse Buffer for Completions" (p)
453 "Zips over a buffer slamming everything that is a valid completion word
454 into the completion hashtable."
455 "Zips over a buffer slamming everything that is a valid completion word
456 into the completion hashtable."
457 (declare (ignore p))
458 (let ((buffer (prompt-for-buffer :prompt "Buffer to parse: "
459 :must-exist t
460 :default (current-buffer)
461 :default-string (buffer-name
462 (current-buffer)))))
463 (with-mark ((word-start (buffer-start-mark buffer) :right-inserting)
464 (word-end (buffer-start-mark buffer) :left-inserting)
465 (buffer-end-mark (buffer-start-mark buffer)))
466 (message "Starting parse of ~S..." (buffer-name buffer))
467 (loop
468 (unless (find-attribute word-start :completion-wordchar) (return))
469 (record-completion
470 (region-to-string (region word-start
471 (or (find-attribute
472 (move-mark word-end word-start)
473 :completion-wordchar #'zerop)
474 buffer-end-mark))))
475 (move-mark word-start word-end))
476 (message "Done."))))
477
478
479
480 ;;;; Modeline hackery:
481
482 (defvar *completion-mode-possibility* "")
483
484 (defvar *completion-modeline-field* (modeline-field :completion))
485
486 (defun display-possible-completion (prefix
487 &optional (prefix-length (length prefix)))
488 (let ((old *completion-mode-possibility*))
489 (setq *completion-mode-possibility*
490 (or (find-completion prefix prefix-length) ""))
491 (unless (eq old *completion-mode-possibility*)
492 (update-modeline-field *echo-area-buffer* *echo-area-window*
493 *completion-modeline-field*))))
494
495 (defun clear-completion-display ()
496 (unless (= (length (the simple-string *completion-mode-possibility*)) 0)
497 (setq *completion-mode-possibility* "")
498 (update-modeline-field *echo-area-buffer* *echo-area-window*
499 *completion-modeline-field*)))
500
501
502 ;;; COMPLETION-REDISPLAY-FUN erases any completion displayed in the status line.
503 ;;;
504 (defun completion-redisplay-fun (window)
505 (declare (ignore window))
506 (unless (eq (last-command-type) :completion-self-insert)
507 (clear-completion-display)))
508 ;;;
509 (add-hook redisplay-hook #'completion-redisplay-fun)

  ViewVC Help
Powered by ViewVC 1.1.5