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

Contents of /src/hemlock/completion.lisp

Parent Directory Parent Directory | Revision Log Revision Log


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

  ViewVC Help
Powered by ViewVC 1.1.5