1 ;;; avy.el --- set-based completion -*- lexical-binding: t -*-
3 ;; Copyright (C) 2015 Free Software Foundation, Inc.
5 ;; Author: Oleh Krehel <ohwoeowho@gmail.com>
6 ;; URL: https://github.com/abo-abo/avy
8 ;; Package-Requires: ((emacs "24.1") (cl-lib "0.5"))
9 ;; Keywords: point, location
11 ;; This file is part of GNU Emacs.
13 ;; This file is free software; you can redistribute it and/or modify
14 ;; it under the terms of the GNU General Public License as published by
15 ;; the Free Software Foundation; either version 3, or (at your option)
18 ;; This program is distributed in the hope that it will be useful,
19 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
20 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21 ;; GNU General Public License for more details.
23 ;; For a full copy of the GNU General Public License
24 ;; see <http://www.gnu.org/licenses/>.
28 ;; This package provides a generic completion method based on building
29 ;; a balanced decision tree with each candidate being a leaf. To
30 ;; traverse the tree from the root to a desired leaf, typically a
31 ;; sequence of `read-char' can be used.
33 ;; In order for `read-char' to make sense, the tree needs to be
34 ;; visualized appropriately, with a character at each branch node. So
35 ;; this completion method works only for things that you can see on
36 ;; your screen, all at once:
38 ;; * character positions
39 ;; * word or subword start positions
40 ;; * line beginning positions
44 ;; If you're familiar with the popular `ace-jump-mode' package, this
45 ;; package does all that and more, without the implementation
53 "Jump to things tree-style."
57 (defcustom avy-keys '(?a ?s ?d ?f ?g ?h ?j ?k ?l)
58 "Default keys for jumping."
59 :type '(repeat :tag "Keys" character))
61 (defcustom avy-keys-alist nil
62 "Alist of avy-jump commands to `avy-keys' overriding the default `avy-keys'."
64 :key-type (choice :tag "Command"
66 (const avy-goto-char-2)
69 (const avy-goto-subword-0)
70 (const avy-goto-subword-1)
71 (const avy-goto-word-0)
72 (const avy-goto-word-1)
74 (const avy-copy-region)
75 (const avy-move-line))
76 :value-type (repeat :tag "Keys" character)))
78 (defcustom avy-style 'pre
79 "The default method of displaying the overlays.
80 Use `avy-styles-alist' to customize this per-command."
82 (const :tag "Pre" pre)
84 (const :tag "At Full" at-full)
85 (const :tag "Post" post)))
87 (defcustom avy-styles-alist nil
88 "Alist of avy-jump commands to the style for each command.
89 If the commands isn't on the list, `avy-style' is used."
91 :key-type (choice :tag "Command"
93 (const avy-goto-char-2)
96 (const avy-goto-subword-0)
97 (const avy-goto-subword-1)
98 (const avy-goto-word-0)
99 (const avy-goto-word-1)
100 (const avy-copy-line)
101 (const avy-copy-region)
102 (const avy-move-line))
104 (const :tag "Pre" pre)
106 (const :tag "At Full" at-full)
107 (const :tag "Post" post))))
109 (defcustom avy-background nil
110 "When non-nil, a gray background will be added during the selection."
113 (defcustom avy-all-windows t
114 "Determine the list of windows to consider in search of candidates."
117 (const :tag "All Frames" all-frames)
118 (const :tag "This Frame" t)
119 (const :tag "This Window" nil)))
121 (defcustom avy-case-fold-search t
122 "Non-nil if searches should ignore case."
125 (defcustom avy-word-punc-regexp "[!-/:-@[-`{-~]"
126 "Regexp of punctuation chars that count as word starts for `avy-goto-word-1.
127 When nil, punctuation chars will not be matched.
129 \"[!-/:-@[-`{-~]\" will match all printable punctuation chars."
132 (defface avy-lead-face-0
133 '((t (:foreground "white" :background "#4f57f9")))
134 "Face used for first non-terminating leading chars.")
136 (defface avy-lead-face-1
137 '((t (:foreground "white" :background "gray")))
138 "Face used for matched leading chars.")
140 (defface avy-lead-face
141 '((t (:foreground "white" :background "#e52b50")))
142 "Face used for the leading chars.")
144 (defface avy-background-face
145 '((t (:foreground "gray40")))
146 "Face for whole window background during selection.")
150 (defmacro avy-multipop (lst n)
151 "Remove LST's first N elements and return them."
152 `(if (<= (length ,lst) ,n)
157 (nthcdr (1- ,n) (prog1 ,lst (setq ,lst (nthcdr ,n ,lst))))
160 (defun avy-tree (lst keys)
161 "Coerce LST into a balanced tree.
162 The degree of the tree is the length of KEYS.
163 KEYS are placed appropriately on internal nodes."
164 (let ((len (length keys)))
167 (let ((ln (length ls)))
170 (mapcar (lambda (x) (cons 'leaf x)) ls))
171 (let ((ks (copy-sequence keys))
173 (dolist (s (avy-subdiv ln len))
176 (cons 'leaf (pop ls))
177 (rd (avy-multipop ls s))))
182 (defun avy-subdiv (n b)
183 "Distribute N in B terms in a balanced way."
184 (let* ((p (1- (floor (+ (log n b) 1e-6))))
188 (n2 (/ delta (- x2 x1)))
193 (- n (* n1 x1) (* n2 x2)))
196 (defun avy-traverse (tree walker &optional recur-key)
197 "Traverse TREE generated by `avy-tree'.
198 WALKER is a function that takes KEYS and LEAF.
200 RECUR-KEY is used in recursion.
202 LEAF is a member of LST argument of `avy-tree'.
204 KEYS is the path from the root of `avy-tree' to LEAF."
206 (let ((key (cons (car br) recur-key)))
207 (if (eq (cadr br) 'leaf)
208 (funcall walker key (cddr br))
209 (avy-traverse (cdr br) walker key)))))
211 (defun avy-handler-default (char)
212 "The default hander for a bad CHAR."
213 (signal 'user-error (list "No such candidate" char))
216 (defvar avy-handler-function 'avy-handler-default
217 "A function to call for a bad `read-char' in `avy-read'.")
219 (defvar avy-current-path ""
220 "Store the current incomplete path during `avy-read'.")
222 (defun avy-read (tree display-fn cleanup-fn)
223 "Select a leaf from TREE using consecutive `read-char'.
225 DISPLAY-FN should take CHAR and LEAF and signify that LEAFs
226 associated with CHAR will be selected if CHAR is pressed. This is
227 commonly done by adding a CHAR overlay at LEAF position.
229 CLEANUP-FN should take no arguments and remove the effects of
230 multiple DISPLAY-FN invokations."
232 (setq avy-current-path "")
234 (let ((avy--leafs nil))
237 (push (cons path leaf) avy--leafs)))
238 (dolist (x avy--leafs)
239 (funcall display-fn (car x) (cdr x))))
240 (let ((char (read-char))
243 (if (setq branch (assoc char tree))
244 (if (eq (car (setq tree (cdr branch))) 'leaf)
245 (throw 'done (cdr tree))
246 (setq avy-current-path
247 (concat avy-current-path (string char))))
248 (funcall avy-handler-function char))))))
251 (defun avy-window-list ()
252 "Return a list of windows depending on `avy-all-windows'."
253 (cond ((eq avy-all-windows 'all-frames)
254 (cl-mapcan #'window-list (frame-list)))
256 ((eq avy-all-windows t)
259 ((null avy-all-windows)
260 (list (selected-window)))
263 (error "Unrecognized option: %S" avy-all-windows))))
265 (defmacro avy-dowindows (flip &rest body)
266 "Depending on FLIP and `avy-all-windows' run BODY in each or selected window."
269 `(let ((avy-all-windows (if ,flip
270 (not avy-all-windows)
272 (dolist (wnd (avy-window-list))
273 (with-selected-window wnd
274 (unless (memq major-mode '(image-mode doc-view-mode))
277 (defmacro avy--with-avy-keys (command &rest body)
278 "Set `avy-keys' according to COMMAND and execute BODY."
281 `(let ((avy-keys (or (cdr (assq ',command avy-keys-alist))
283 (avy-style (or (cdr (assq ',command avy-styles-alist))
290 POS is either a position or (BEG . END)."
292 (message "zero candidates"))
294 ;; ignore exit from `avy-handler-function'
298 (select-window (cdr x))
302 (unless (= pt (point)) (push-mark))
305 (defun avy--process (candidates overlay-fn)
306 "Select one of CANDIDATES using `avy-read'.
307 Use OVERLAY-FN to visualize the decision overlay."
309 (cl-case (length candidates)
315 (avy--make-backgrounds
317 (avy-read (avy-tree candidates avy-keys)
319 #'avy--remove-leading-chars)))
322 (defvar avy--overlays-back nil
323 "Hold overlays for when `avy-background' is t.")
325 (defun avy--make-backgrounds (wnd-list)
326 "Create a dim background overlay for each window on WND-LIST."
328 (setq avy--overlays-back
330 (let ((ol (make-overlay
334 (overlay-put ol 'face 'avy-background-face)
335 (overlay-put ol 'window w)
341 (mapc #'delete-overlay avy--overlays-back)
342 (setq avy--overlays-back nil)
343 (avy--remove-leading-chars))
345 (defun avy--regex-candidates (regex &optional beg end pred group)
346 "Return all elements that match REGEX.
347 Each element of the list is ((BEG . END) . WND)
348 When PRED is non-nil, it's a filter for matching point positions.
349 When GROUP is non-nil, (BEG . END) should delimit that regex group."
350 (setq group (or group 0))
351 (let ((case-fold-search avy-case-fold-search)
354 (let ((we (or end (window-end (selected-window) t))))
356 (goto-char (or beg (window-start)))
357 (while (re-search-forward regex we t)
358 (unless (get-char-property (point) 'invisible)
359 (when (or (null pred)
361 (push (cons (cons (match-beginning group)
363 wnd) candidates)))))))
364 (nreverse candidates)))
366 (defvar avy--overlay-offset 0
367 "The offset to apply in `avy--overlay'.")
369 (defvar avy--overlays-lead nil
370 "Hold overlays for leading chars.")
372 (defun avy--remove-leading-chars ()
373 "Remove leading char overlays."
374 (mapc #'delete-overlay avy--overlays-lead)
375 (setq avy--overlays-lead nil))
377 (defun avy--overlay (str pt wnd)
378 "Create an overlay with STR at PT in WND."
379 (when (<= (1+ pt) (with-selected-window wnd (point-max)))
380 (let* ((pt (+ pt avy--overlay-offset))
381 (ol (make-overlay pt (1+ pt) (window-buffer wnd)))
382 (old-str (with-selected-window wnd
383 (buffer-substring pt (1+ pt)))))
385 (setq old-str (propertize
386 old-str 'face 'avy-background-face)))
387 (overlay-put ol 'window wnd)
388 (overlay-put ol 'display (concat str old-str))
389 (push ol avy--overlays-lead))))
391 (defcustom avy-highlight-first nil
392 "When non-nil highlight the first decision char with `avy-lead-face-0'.
393 Do this even when the char is terminating."
396 (defun avy--overlay-pre (path leaf)
397 "Create an overlay with PATH at LEAF.
398 PATH is a list of keys from tree root to LEAF.
399 LEAF is normally ((BEG . END) . WND)."
400 (let ((str (propertize (apply #'string (reverse path))
401 'face 'avy-lead-face)))
402 (when (or avy-highlight-first (> (length str) 1))
403 (set-text-properties 0 1 '(face avy-lead-face-0) str))
405 (propertize avy-current-path
406 'face 'avy-lead-face-1)
410 (cond ((numberp leaf)
418 (selected-window)))))
420 (defun avy--overlay-at (path leaf)
421 "Create an overlay with PATH at LEAF.
422 PATH is a list of keys from tree root to LEAF.
423 LEAF is normally ((BEG . END) . WND)."
424 (let ((str (propertize
425 (string (car (last path)))
426 'face 'avy-lead-face))
427 (pt (+ (if (consp (car leaf))
430 avy--overlay-offset))
432 (let ((ol (make-overlay pt (1+ pt)
433 (window-buffer wnd)))
434 (old-str (with-selected-window wnd
435 (buffer-substring pt (1+ pt)))))
437 (setq old-str (propertize
438 old-str 'face 'avy-background-face)))
439 (overlay-put ol 'window wnd)
440 (overlay-put ol 'display (if (string= old-str "\n")
443 (push ol avy--overlays-lead))))
445 (defun avy--overlay-at-full (path leaf)
446 "Create an overlay with PATH at LEAF.
447 PATH is a list of keys from tree root to LEAF.
448 LEAF is normally ((BEG . END) . WND)."
449 (let* ((str (propertize
450 (apply #'string (reverse path))
451 'face 'avy-lead-face))
453 (beg (if (consp (car leaf))
457 (when (or avy-highlight-first (> (length str) 1))
458 (set-text-properties 0 1 '(face avy-lead-face-0) str))
459 (with-selected-window wnd
462 (when (cl-some (lambda (o)
463 (and (eq (overlay-get o 'category) 'avy)
464 (eq (overlay-get o 'window) wnd)))
465 (overlays-in (point) (min (+ (point) len)
466 (line-end-position))))
467 (setq str (substring str 0 1))
469 (let ((other-ov (cl-find-if
471 (and (eq (overlay-get o 'category) 'avy)
472 (eq (overlay-start o) beg)
473 (not (eq (overlay-get o 'window) wnd))))
474 (overlays-in (point) (min (+ (point) len)
475 (line-end-position))))))
477 (> (overlay-end other-ov)
479 (setq str (concat str (buffer-substring
481 (overlay-end other-ov))))
482 (setq len (- (overlay-end other-ov)
484 (let* ((end (if (= beg (line-end-position))
487 (if (eq (char-after) ?\t)
490 (line-end-position))))
494 (old-str (buffer-substring beg (1+ beg))))
496 (setq old-str (propertize
497 old-str 'face 'avy-background-face)))
498 (overlay-put ol 'window wnd)
499 (overlay-put ol 'category 'avy)
500 (overlay-put ol 'display
501 (cond ((string= old-str "\n")
503 ((string= old-str "\t")
504 (concat str (make-string (- tab-width len) ?\ )))
507 (push ol avy--overlays-lead))))))
509 (defun avy--overlay-post (path leaf)
510 "Create an overlay with PATH at LEAF.
511 PATH is a list of keys from tree root to LEAF.
512 LEAF is normally ((BEG . END) . WND)."
513 (let ((str (propertize (apply #'string (reverse path))
514 'face 'avy-lead-face)))
515 (when (or avy-highlight-first (> (length str) 1))
516 (set-text-properties 0 1 '(face avy-lead-face-0) str))
518 (propertize avy-current-path
519 'face 'avy-lead-face-1)
523 (cond ((numberp leaf)
531 (selected-window)))))
533 (defun avy--style-fn (style)
534 "Transform STYLE symbol to a style function."
536 (pre #'avy--overlay-pre)
537 (at #'avy--overlay-at)
538 (at-full 'avy--overlay-at-full)
539 (post #'avy--overlay-post)
540 (t (error "Unexpected style %S" style))))
542 (defun avy--generic-jump (regex window-flip style)
544 When WINDOW-FLIP is non-nil, do the opposite of `avy-all-windows'.
545 STYLE determines the leading char overlay style."
546 (let ((avy-all-windows
548 (not avy-all-windows)
552 (avy--regex-candidates regex)
553 (avy--style-fn style)))))
557 (defun avy-goto-char (char &optional arg)
558 "Jump to the currently visible CHAR.
559 The window scope is determined by `avy-all-windows' (ARG negates it)."
560 (interactive (list (read-char "char: ")
562 (avy--with-avy-keys avy-goto-char
566 (regexp-quote (string char)))
571 (defun avy-goto-char-in-line (char &optional arg)
572 "Jump to the currently visible CHAR in the current line.
573 The window scope is determined by `avy-all-windows' (ARG negates it)."
574 (interactive (list (read-char "char: ")
576 (let ((avy-all-windows
578 (not avy-all-windows)
580 (avy--with-avy-keys avy-goto-char
584 (narrow-to-region (line-beginning-position)
586 (avy--regex-candidates (string char)))
587 (avy--style-fn avy-style))))))
590 (defun avy-goto-char-2 (char1 char2 &optional arg)
591 "Jump to the currently visible CHAR1 followed by CHAR2.
592 The window scope is determined by `avy-all-windows' (ARG negates it)."
593 (interactive (list (read-char "char 1: ")
594 (read-char "char 2: ")
596 (avy--with-avy-keys avy-goto-char-2
598 (regexp-quote (string char1 char2))
603 (defun avy-isearch ()
604 "Jump to one of the current isearch candidates."
606 (avy--with-avy-keys avy-isearch
608 (avy--regex-candidates isearch-string))
611 (avy--process candidates #'avy--overlay-post)))
613 (avy--goto candidate))))
616 (defun avy-goto-word-0 (arg)
617 "Jump to a word start.
618 The window scope is determined by `avy-all-windows' (ARG negates it)."
620 (avy--with-avy-keys avy-goto-word-0
621 (avy--generic-jump "\\b\\sw" arg avy-style)))
624 (defun avy-goto-word-1 (char &optional arg)
625 "Jump to the currently visible CHAR at a word start.
626 The window scope is determined by `avy-all-windows' (ARG negates it)."
627 (interactive (list (read-char "char: ")
629 (avy--with-avy-keys avy-goto-word-1
630 (let* ((str (string char))
631 (regex (cond ((string= str ".")
633 ((and avy-word-punc-regexp
634 (string-match avy-word-punc-regexp str))
640 (avy--generic-jump regex arg avy-style))))
642 (declare-function subword-backward "subword")
645 (defun avy-goto-subword-0 (&optional arg predicate)
646 "Jump to a word or subword start.
648 The window scope is determined by `avy-all-windows' (ARG negates it).
650 When PREDICATE is non-nil it's a function of zero parameters that
654 (avy--with-avy-keys avy-goto-subword-0
655 (let ((case-fold-search nil)
658 (let ((ws (window-start))
661 (goto-char (window-end (selected-window) t))
663 (while (> (point) ws)
664 (when (or (null predicate)
665 (and predicate (funcall predicate)))
666 (push (cons (point) (selected-window)) window-cands))
668 (setq candidates (nconc candidates window-cands))))
670 (avy--process candidates (avy--style-fn avy-style))))))
673 (defun avy-goto-subword-1 (char arg)
674 "Jump to the currently visible CHAR at a subword start.
675 The window scope is determined by `avy-all-windows' (ARG negates it).
676 The case of CHAR is ignored."
677 (interactive (list (read-char "char: ")
679 (avy--with-avy-keys avy-goto-subword-1
680 (let ((char (downcase char)))
682 arg (lambda () (eq (downcase (char-after)) char))))))
684 (defun avy-goto-word-or-subword-1 ()
685 "Forward to `avy-goto-subword-1' or `avy-goto-word-1'.
686 Which one depends on variable `subword-mode'."
688 (if (bound-and-true-p subword-mode)
689 (call-interactively #'avy-goto-subword-1)
690 (call-interactively #'avy-goto-word-1)))
692 (defun avy--line (&optional arg)
694 The window scope is determined by `avy-all-windows' (ARG negates it)."
695 (let ((avy-background nil)
698 (let ((ws (window-start)))
701 (narrow-to-region ws (window-end (selected-window) t))
702 (goto-char (point-min))
703 (while (< (point) (point-max))
704 (unless (get-char-property
705 (max (1- (point)) ws) 'invisible)
707 (if (eq avy-style 'post)
709 (line-beginning-position))
710 (selected-window)) candidates))
711 (forward-line 1))))))
712 (avy--process (nreverse candidates) (avy--style-fn avy-style))))
715 (defun avy-goto-line (&optional arg)
716 "Jump to a line start in current buffer.
717 The window scope is determined by `avy-all-windows' (ARG negates it)."
719 (avy--with-avy-keys avy-goto-line
720 (let ((avy-handler-function
724 (avy-handler-default char)
725 (let ((line (read-from-minibuffer
726 "Goto line: " (string char))))
728 (goto-char (point-min))
729 (forward-line (1- (string-to-number line)))
730 (throw 'done 'exit)))))))
731 (avy--goto (avy--line arg)))))
734 (defun avy-copy-line (arg)
735 "Copy a selected line above the current line.
736 ARG lines can be used."
738 (avy--with-avy-keys avy-copy-line
739 (let ((start (car (avy--line))))
740 (move-beginning-of-line nil)
743 (buffer-substring-no-properties
747 (move-end-of-line arg)
752 (defun avy-move-line (arg)
753 "Move a selected line above the current line.
754 ARG lines can be used."
756 (avy--with-avy-keys avy-move-line
757 (let ((start (car (avy--line))))
758 (move-beginning-of-line nil)
762 (kill-whole-line arg))
764 (current-kill 0))))))
767 (defun avy-copy-region ()
768 "Select two lines and copy the text between them here."
770 (avy--with-avy-keys avy-copy-region
771 (let ((beg (car (avy--line)))
772 (end (car (avy--line)))
773 (pad (if (bolp) "" "\n")))
774 (move-beginning-of-line nil)
777 (buffer-substring-no-properties
781 (line-end-position)))
785 (defun avy-setup-default ()
786 "Setup the default shortcuts."
787 (eval-after-load "isearch"
788 '(define-key isearch-mode-map (kbd "C-'") 'avy-isearch)))
790 (defcustom avy-timeout-seconds 0.5
791 "How many seconds to wait for the second char.")
794 (defun avy-goto-char-timer (&optional arg)
795 "Read one or two consecutive chars and jump to the first one.
796 The window scope is determined by `avy-all-windows' (ARG negates it)."
798 (let ((c1 (read-char "char 1: "))
799 (c2 (read-char "char 2: " nil avy-timeout-seconds)))
808 (define-obsolete-variable-alias
809 'avy-goto-char-style 'avy-style "0.1.0"
810 "Use `avy-style' and `avy-styles-alist' instead.")
811 (define-obsolete-variable-alias
812 'avy-goto-word-style 'avy-style "0.1.0"
813 "Use `avy-style' and `avy-styles-alist' instead.")
814 (define-obsolete-variable-alias 'avi-keys 'avy-keys "0.1.0")
815 (define-obsolete-variable-alias 'avi-background 'avy-background "0.1.0")
816 (define-obsolete-variable-alias 'avi-word-punc-regexp 'avy-word-punc-regexp "0.1.0")
817 (define-obsolete-face-alias 'avi-lead-face 'avy-lead-face "0.1.0")
818 (define-obsolete-function-alias 'avi--goto 'avy--goto "0.1.0")
819 (define-obsolete-function-alias 'avi--process 'avy--process "0.1.0")
820 (define-obsolete-variable-alias 'avi-all-windows 'avy-all-windows "0.1.0")
821 (define-obsolete-function-alias 'avi--overlay-pre 'avy--overlay-pre "0.1.0")
822 (define-obsolete-function-alias 'avi--overlay-at 'avy--overlay-at "0.1.0")
823 (define-obsolete-function-alias 'avi--overlay-post 'avy--overlay-post "0.1.0")
824 (define-obsolete-function-alias 'avi-goto-char 'avy-goto-char "0.1.0")
825 (define-obsolete-function-alias 'avi-goto-char-2 'avy-goto-char-2 "0.1.0")
826 (define-obsolete-function-alias 'avi-isearch 'avy-isearch "0.1.0")
827 (define-obsolete-function-alias 'avi-goto-word-0 'avy-goto-word-0 "0.1.0")
828 (define-obsolete-function-alias 'avi-goto-subword-0 'avy-goto-subword-0 "0.1.0")
829 (define-obsolete-function-alias 'avi-goto-word-1 'avy-goto-word-1 "0.1.0")
830 (define-obsolete-function-alias 'avi-goto-line 'avy-goto-line "0.1.0")
831 (define-obsolete-function-alias 'avi-copy-line 'avy-copy-line "0.1.0")
832 (define-obsolete-function-alias 'avi-move-line 'avy-move-line "0.1.0")
833 (define-obsolete-function-alias 'avi-copy-region 'avy-copy-region "0.1.0")
834 (define-obsolete-function-alias 'avi--regex-candidates 'avy--regex-candidates "0.1.0")