1 ;;; avy.el --- set-based completion -*- lexical-binding: t -*-
3 ;; Copyright (C) 2015 Free Software Foundation, Inc.
7 ;; This file is part of GNU Emacs.
9 ;; This file is free software; you can redistribute it and/or modify
10 ;; it under the terms of the GNU General Public License as published by
11 ;; the Free Software Foundation; either version 3, or (at your option)
14 ;; This program is distributed in the hope that it will be useful,
15 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
16 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 ;; GNU General Public License for more details.
19 ;; For a full copy of the GNU General Public License
20 ;; see <http://www.gnu.org/licenses/>.
24 ;; This package provides a generic completion method based on building
25 ;; a balanced decision tree with each candidate being a leaf. To
26 ;; traverse the tree from the root to a desired leaf, typically a
27 ;; sequence of `read-char' can be used.
29 ;; In order for `read-char' to make sense, the tree needs to be
30 ;; visualized appropriately, with a character at each branch node. So
31 ;; this completion method works only for things that you can see on
32 ;; your screen, all at once:
34 ;; * character positions
35 ;; * word or subword start positions
36 ;; * line beginning positions
40 ;; If you're familiar with the popular `ace-jump-mode' package, this
41 ;; package does all that and more, without the implementation
47 (defmacro avy-multipop (lst n)
48 "Remove LST's first N elements and return them."
49 `(if (<= (length ,lst) ,n)
54 (nthcdr (1- ,n) (prog1 ,lst (setq ,lst (nthcdr ,n ,lst))))
57 (defun avy-tree (lst keys)
58 "Coerce LST into a balanced tree.
59 The degree of the tree is the length of KEYS.
60 KEYS are placed appropriately on internal nodes."
61 (let ((len (length keys)))
64 (let ((ln (length ls)))
67 (mapcar (lambda (x) (cons 'leaf x)) ls))
68 (let ((ks (copy-sequence keys))
70 (dolist (s (avy-subdiv ln len))
74 (rd (avy-multipop ls s))))
79 (defun avy-subdiv (n b)
80 "Distribute N in B terms in a balanced way."
81 (let* ((p (1- (floor (+ (log n b) 1e-6))))
85 (n2 (/ delta (- x2 x1)))
90 (- n (* n1 x1) (* n2 x2)))
93 (defun avy-traverse (tree walker &optional recur-key)
94 "Traverse TREE generated by `avy-tree'.
95 WALKER is a function that takes KEYS and LEAF.
97 RECUR-KEY is used in recursion.
99 LEAF is a member of LST argument of `avy-tree'.
101 KEYS is the path from the root of `avy-tree' to LEAF."
103 (let ((key (cons (car br) recur-key)))
104 (if (eq (cadr br) 'leaf)
105 (funcall walker key (cddr br))
106 (avy-traverse (cdr br) walker key)))))
108 (defun avy-read (tree display-fn cleanup-fn)
109 "Select a leaf from TREE using consecutive `read-char'.
111 DISPLAY-FN should take CHAR and LEAF and signify that LEAFs
112 associated with CHAR will be selected if CHAR is pressed. This is
113 commonly done by adding a CHAR overlay at LEAF position.
115 CLEANUP-FN should take no arguments and remove the effects of
116 multiple DISPLAY-FN invokations."
119 (avy-traverse tree display-fn)
120 (let ((char (read-char))
123 (if (setq branch (assoc char tree))
124 (if (eq (car (setq tree (cdr branch))) 'leaf)
125 (throw 'done (cdr tree)))
126 (signal 'user-error (list "No such candidate" char))
127 (throw 'done nil))))))