ace-window without ace

02 Mar 2015

Today, ace-window is dropping the dependency on ace-jump-mode. Most of the dependency was already dropped in 0.7.0, when I had to fix ace-window to work better with defhydra.

The change will not be user-visible, unless you relied on some customizations of ace-jump-mode to transfer to ace-window. You'll be able to transfer your customizations to similarly named variables.

The reason for the move is that, due to the implementation of ace-jump-mode, it's hard to wrap its calls, since the function exits before any of the red chars are selected by the user. Also, ace-jump-mode uses its own defstructs for candidates while I'd rather have plain lists, but that's a minor issue.

New back end: avy.el

I tried to pinpoint the most generic algorithm that ace-jump-mode implements and wrote it down in avy. Here's the core of the implementation:

(defun avy-subdiv (n b)
  "Distribute N in B terms in a balanced way."
  (let* ((p (1- (floor (log n b))))
         (x1 (expt b p))
         (x2 (* b x1))
         (delta (- n x2))
         (n2 (/ delta (- x2 x1)))
         (n1 (- b n2 1)))
    (append
     (make-list n1 x1)
     (list
      (- n (* n1 x1) (* n2 x2)))
     (make-list n2 x2))))

(defun avy-tree (lst keys)
  "Coerce LST into a balanced tree.
The degree of the tree is the length of KEYS.
KEYS are placed appropriately on internal nodes."
  (let ((len (length keys)))
    (cl-labels
        ((rd (ls)
           (let ((ln (length ls)))
             (if (< ln len)
                 (cl-pairlis
                  keys
                  (mapcar (lambda (x) (cons 'leaf x)) ls))
               (let ((ks (copy-sequence keys))
                     res)
                 (dolist (s (avy-subdiv ln len))
                   (push (cons (pop ks)
                               (if (eq s 1)
                                   (cons 'leaf (pop ls))
                                 (rd (avy-multipop ls s))))
                         res))
                 (nreverse res))))))
      (rd lst))))

The first function, avy-subdiv, tries to split a number in terms of the base in a way that the most leaves have the lowest level:

(avy-subdiv 42 5)
;;=> (5 5 5 5 22)

(avy-subdiv 42 4)
;;=> (4 6 16 16)

(avy-subdiv 42 3)
;;=> (9 9 24)

(avy-subdiv 42 2)
;;=> (16 26)

And here's an example of what avy-tree produces:

(avy-tree
 '("Acid green" "Aero blue" "Almond" "Amaranth"
   "Amber" "Amethyst" "Apple green" "Aqua"
   "Aquamarine" "Auburn" "Aureolin" "Azure"
   "Beige" "Black" "Bronze" "Blue" "Burgundy" "Candy apple red")
 '(1 2 3 4))
;;=>
((1 (1 leaf . "Acid green")
    (2 leaf . "Aero blue")
    (3 leaf . "Almond")
    (4 leaf . "Amaranth"))
 (2 (1 leaf . "Amber")
    (2 leaf . "Amethyst")
    (3 leaf . "Apple green")
    (4 leaf . "Aqua"))
 (3 (1 leaf . "Aquamarine")
    (2 leaf . "Auburn")
    (3 leaf . "Aureolin")
    (4 leaf . "Azure"))
 (4 (1 leaf . "Beige")
    (2 leaf . "Black")
    (3 leaf . "Bronze")
    (4 (1 leaf . "Blue")
       (2 leaf . "Burgundy")
       (3 leaf . "Candy apple red"))))

I think the library turned out to be pretty clean, since it knows nothing of points, buffers or overlays, and imposes no restrictions on the type of leaf items and keys.

Some cool `avy`-based commands

I'll list them together with the code, so it's easier to see what they do. The basic customizable variable is this one:

(defcustom avy-keys '(?a ?s ?d ?f ?g ?h ?j ?k ?l)
  "Keys for jumping.")

Note that, while ace-jump-mode has 52 selection chars by default, I prefer to have only the 8 chars on the home row. This means that I'll usually have to go around one level deeper, but the characters are easy to find and press.

`avy-jump-double-char`

(defun avy-jump-double-char ()
  "Read two chars and jump to them in current window."
  (interactive)
  (avy--process (avy--regex-candidates
                 (string
                  (read-char "char 1: ")
                  (read-char "char 2: "))
                 (selected-window))
                #'avy--goto))

This one will read two chars and then offer avy-selection for the matches. This is a pretty sensible approach for a pool of 8 keys, since usually 3 chars total will be necessary, with the first two being in natural succession.

Here's a screenshot of me typing in a natural two-char sequence "do":

avy-jump-double-char

As you see, with 8 keys, 8 candidates will have depth 1, and another 8 candidates will have depth 2. The sorting preference is for the first candidates to have lower depth.

`avy-jump-line`

(defun avy-jump-line ()
  "Jump to a line start in current buffer."
  (interactive)
  (let ((we (window-end))
        candidates)
    (save-excursion
      (goto-char (window-start))
      (while (< (point) we)
        (push (cons (point) (selected-window))
              candidates)
        (forward-line 1)))
    (avy--process (nreverse candidates)
                  #'avy--goto
                  t)))

This one is quite nice, since I always have less than 8*8=64 lines in any window. Here's how it looks like:

avy-jump-line

I removed the gray background, since the leading chars are always in an expected position.

`avy-jump-isearch`

Saving the most clever one for last:

(defun avy-jump-isearch ()
  "Jump to one of the current isearch candidates."
  (interactive)
  (let ((candidates
         (mapcar (lambda (x) (cons (1+ (car x))
                              (cdr x)))
                 (avy--regex-candidates isearch-string))))
    (avy--process candidates #'avy--goto t)
    (isearch-done)))
(define-key isearch-mode-map "'" 'avy-jump-isearch)

I don't mind not being able to isearch-forward-regexp for a single quote without using C-q (quoted-insert). In return, I get the ability to very quickly jump to a search candidate on screen. I like this command the most. In case when there's only one match, it's a faster way to call isearch-done (than C-m). Here's the result of C-s sen ':

avy-jump-isearch

Outro

I've used the new functionality for a few days already, so it shouldn't be fragile. If the newest MELPA version bugs out for you, you can fall back to version 0.7.1 on MELPA Stable and post an issue. Finally, I hope that some people will take advantage of avy.el simplicity and come up with some cool new commands to share with me. Happy hacking!

(or emacs irrelevant)