avy-jump without complete paths and overlays on top of the jump target (like in ace-jump)

[tsdh]

I've switched from ace-jump to avy-jump just recently. One major difference is that ace-jump's overlays are displayed on top of the jump target and only one jump character is displayed at a time. With avy-mode, the overlays always show the complete jump character sequence and are displayed right of the jump target.

At least my personal preference (which is not ace-jump biased too much; I started using that only two weeks ago before switching to avy-jump yesterday) is that I like the ace-jump behavior better because the buffer contents won't switch to the right. That is, if you have 5 matches on a line, each requiring a 2-char key sequence to jump to, then the last match has switched 8 chars to the right. With ace-jump, it stays where it has been before. So this "fix target with your eyes and then jump" thingy works better.

[abo-abo]

It's not yet customizable, but it should be soon. There are 3 styles:

• avy--overlay-pre
• avy--overlay-post
• avy--overlay-at

The first one is the currently used one that I like. The last one is ace-jump style. I'll make it customizable soon. Like this probably.

[tsdh]

Oh yes, that'd be great!

[PythonNut]

@abo-abo there is (and you may already know this) potentially a way to do multi-char targets that also overlay. The math is described on the May 19th posts here. In essence, we allow the targets to overlap and do extra math to make sure that all possible intervals on the combined targets are unique. This is the method used by vim-easymotion versions 2+.

Does that sound at all feasible?

[abo-abo]

Does that sound at all feasible?

Thanks for the pointer, I'll have to look into this. At the moment, I think that overlaying multiple chars would quickly result in a loss of context, since a large portion of the original text would be hidden.

[PythonNut]

@abo-abo that may be true, but I doubt this is better:

Targets are so far displaced from their original positions that it's decently hard to follow where they went. I, personally, rely on remembering where the target was originally and just mash whatever shows up so I don't have time to forget. I could just use the at stye, if this doesn't work out, though.

[tsdh]

Me, too. I fixate the position I wanna jump to and then just type whatever shows up. So I'd 👍 @PythonNut's method.

[abo-abo]

but I doubt this is better:

Would it be better with three consecutive chars overlayed on each target? You wouldn't be able to see the original text at all.

[tsdh]

@abo-abo I think yes. I fix the jump position, then invoke avy-goto-char, and just type. The original text is not important anymore at that point.

[abo-abo]

The original text is not important anymore at that point.

OK, we'll just have to implement and see.

[arejensen]

I came to suggest exactly the same thing as @PythonNut and @tsdh.
I attempted to implement the feature with ace-jump, but quickly grew frustrated when disentangling the code. When I saw your initial work on avy, I had great hope that you would implement this feature.
Thank you for your work.

[vermiculus]

👍 It looks like there's a small bug where it picks up the newline in the overlay if the query char is at the end of the line.

[abo-abo]

Thanks, I see it now.

[tsdh]

Wow, this is awesome! Thanks @abo-abo!

[PythonNut]

Does at-full have no effect on the actual target sequences (i.e. kk, kj,...)?

[abo-abo]

@PythonNut at-full is only the overlay style. The target sequences are determined by avy-keys or avy-keys-alist.

[PythonNut]

So if the targets are adjacent, the text is shifted one character to the right?

[abo-abo]

Yes.

[tsdh]

Indeed. Hm, that makes the at-full style useless if there are matches whose distance between each other is less or equal than the length of the key sequence for the former. A user cannot see at which position the sequence he has to type actually begins.

To implement the algorithm @PythonNut referenced, avy-tree and its helpers would need to assume that the list given to it is actually a list of markers because the algorithm needs to know which matches are adjacent.

I wonder if there's even some "better" algorithm where better means no restriction on number of adjacent matches but possibly longer key sequences. Basically, what needs to be ensured is that the key sequence assigned to match N+1 shares its front keys with match N if the key sequence of that runs into match N+1.

Basically, that's simple when doing by hand, but I don't see the math behind it right now. Here's an example where the matches are ?x characters, and avy-keys are just ?a and ?b.

xxxxxZx
aa       ;; 1. match
 ab      ;; 2. match
  ba     ;; 3. match
   aab   ;; 4. match
    abb  ;; 5. match
      bb ;; 6. match

Can anyone formalize that?

[abo-abo]

I could add an overwrite check, although the best solution to the problem is just to use pre, it seems to me that at-full can't be solved perfectly.

avy-tree algorithm is sound, and a good part of it is that it has no idea about the type of the candidates' set or the decision set, it only cares about the sizes of these sets. And it's optimal in the tree depth and leafs amount.

You can try to implement a less optimal algorithm in the two mentioned parameters, that instead resolves overlay conflicts. But I expect that the result will not be very consistent: the leading chars structure will vary depending on the buffer text. The current sequence is actually pretty consistent, since it's basically increasing in lexicographic order by 1 each time.

[abo-abo]

See, for instance, this example with the word that. Sequences of length 2 are used there, which is reasonable, and it's very had to see the original text.

[tsdh]

Yes, of course you are right. But still it's a very interesting problem to me, and if there is a general solution probably resulting in longer key sequences and of course in non-lexicographic ordering, I'd still want to try it out. Especially the non-lexicographic order is a non-issue anyway because when you jump, you know where you want to end up so you don't care about the preceding or following matches and thus not about their key sequences. Well, and if you don't use the full alphabet as avy-keys lexicographic order is strange anyhow.

I'll try to ask some math guy. Maybe there is a good solution that could be implemented in a special at-full specific alternative avy-tree implementation.

[abo-abo]

Suppose that the buffer is filled with 15 occurrences of the word eye, and avy-goto-char is called for e. To avoid problems with at-full style, a single length path would need to be used in these 30 places. Which means that you can avy-keys must be at least longer than 30. So you can't just cover all cases in a perfect way.

Also note that in the screenshot, it's not all that bad: the first decision char is always in the proper position, and I can make sure that it's not overwritten. And thanks to the proper sequencing, you can easily type the prefix to narrow the candidates (since candidates with same prefix are in the same area).

I could enhance this by coloring the first prefix with a different face.

[abo-abo]

What do you think about the different face color for the first prefix? Is it more clear?

[abo-abo]

Oops, I was wrong before: the overlays don't get overwritten. at-full actually behaves like pre if there's an overlap.

[PythonNut]

@abo-abo currently, at-full leaves some targets unreachable. (Note adjacent blue targets, and how one shadows the other).

I'm really excited. If at-full grows the necessary sequencing, then it can supersede all three other styles. It costs one mind-keyboard round trip like pre and post, zero scans for shifted content like at, and is also precise (as in, it doesn't come before or after the target, it goes over the target) like at. It's seriously the best of all the other styles in one.

Currently, the math is done. The only addition I would add is the case when two targets are not adjacent, but still overlap, as would be the case jumping to * here with a target length of three.

*=*=*=*=*=*

In this case, you can just skip forward n entries (where n is the total number of chars between the targets) and resume the sequence.

*=*=*=*=*=*
aaa
 aab          ⇐ ignored
  aba
   bab        ⇐ ignored
    abb
     bbb      ⇐ ignored
      bba
       baa    ⇐ ignored
        aac
         aca  ⇐ ignored
          cac
final result: (caps indicate highlighted char)
*=*=*=*=*=*
AaAbAbBbAaCac

[vermiculus]

I love De Bruijn sequences, but I'll say it: I'm confused.

[PythonNut]

@vermiculus okay, maybe I need to say more.

Suppose that our targets do not completely overlap (which can be the case if the subsequence length is >2).

*=*
???   Target 1
  ??? Target 2

This would normally be a problem, because the order 3 De Bruijn overlaps by two chars, not one.

We can fix this by adding dummy target to the group:

*=*
aaababb Master Sequence
aaa   Target 1
 aab  (dummy)
  aba Target 2

And we just drop it later, to get:

*=*
aaa   Target 1
  aba Target 2

*=*
aaaba (highlighted as)
Target 1 path: aaa
Target 2 path: aba

Imperatively, we "skip" over the dummy when we detect a partially overlapping target, which is what I was clumsily trying to describe. Typing aab, which would have taken you to the =, is voluntarily and specifically not part of the scope of valid inputs.

It's really pretty dumb. I should probably just have left it to the implementer to discover.

Does that help at all?

[abo-abo]

Note adjacent blue targets, and how one shadows the other

I'm aware of this, I think it's a feature: it's like saying in bold that if you type this letter, the corresponding area will become active.

[abo-abo]

Currently, the math is done

Well, I'd love to see an implementation. So far, De Bruijn are only theoretically good. I wonder how it will look in practice.

[tsdh]

Do I see it correctly that De Bruijn is very similar to (but a bit more space-efficient to compute) just using the cartesian product of avy-keys^n for paths of length n? That is, you'd compute De Bruijn for avy-keys and path length n, and then any subsequence of length n can be used as avy path.

In both cases, you have to walk the matches and pick non-conflicting paths when there are overlaps. And it might turn out that De Bruijn/cartesian product for paths of length n (which produce avy-keys^n different paths) don't turn out to be enough for the set of matches because many aren't usable due to overlaps. In this case, the algorithm would need to try again with n+1. So in the usual case, the algorithm would first try 1-char paths, fail, try 2-char paths, fail, try 3-char paths, and that has a reasonable chance of being good enough. (Of course that depends on the number of chars in avy-keys.

[PythonNut]

@tsdh set of subsequences produced by De Bruijn is the same as the cartesian product (that is, all possible combinations are present). However, the ordering is different. The ordering matters very much because, if we we choose correctly, we don't have to

[...] walk the matches and pick non-conflicting paths when there are overlaps. [...]

Suppose we want to jump to * in this: [also pretend that avy-keys is {a, b}]

2 * 2 == pow(2, 2) * 1;
char** a = 1 * 2;

(for convenience, I'll number the *s from 1 to 5)

Under cartesian allocation

1. aaa
2. aab
3. aba
4. abb
5. baa

This is very similar to the algorithm that avy currently uses. And, as you can see, targets 3 and 4 already conflict:

char** a = 1 * 2;
    aba
     abb
             baa

chara??b = 1 abb;
    ^^       ^

We'd need some overlap resolution algorithm to resolve a new unique path.

Under De Bruijn allocation

1. aaa
2. aab
3. aba
4. bab
5. abb
   The sequence starts out similar, but quickly diverges. You might think that targets 3 and 4 are still a problem, but if you look closely.

char** a = 1 * 2;
    aba
     bab
             abb

charabab = 1 abb;
    ^^       ^

As you can see, there is no conflict. In fact, that's the magic of De Bruijn. All conflicts are resolved before they even have a chance to happen.

it might turn out that [...] don't turn out to be enough for the set of matches because many aren't usable due to overlaps

De Bruijn is dense. In fact, it covers the entire space of paths (all possible combinations appear in the sequence). It is, essentially, optimal. The only exception is the case I highlight in my last post, which could bring the efficiency down by a factor of a-1, but that worst case is extremely unlikely. And, in any case, we are still bounded by the total number of chars in the window, which is usually within a four char path at worst.

[tsdh]

Yes, I got that. So a*b*c*d sequences (assuming you want to jump to *) are the worst case for paths of length 3 because here you can only use every second subsequence of De Bruijn (actually the half of the subseqs + 1, IIUC, i.e. 4 out of 7 for db(2,2)).

BTW, I don't think this is such an overly rare case. For example, the letter e occurs very often in English or German, and frequently the distance between two consecutive e is exactly 2. (bejeweled, telemeter, epexegesis, antecedence, decedent, reference, ...)

So then you have the choice: either you assign sequences linearly in one go which is fast but a significant portion of subsequences will be skipped, or you remember the skipped sequences and try to assign them later at places with no overlaps. The second approach is a bit more complex (but not really hard) and has the benefit that chances are higher that you don't have to fall back to longer paths.

[tsdh]

Ok, I think I've implemented a good part of the stuff.

(defun avy--de-bruijn (keys n)
  "DeBruijn seq for alphabet `keys' and subseqs of length `n'."
  (let* ((k (length keys))
         (a (make-list (* n k) 0))
         sequence)
    (cl-labels ((db (T p)
                    (if (> T n)
                        (if (eq (% n p) 0)
                            (setq sequence
                                  (append sequence
                                          (cl-subseq a 1 (1+ p)))))
                      (setf (nth T a) (nth (- T p) a))
                      (db (1+ T) p)
                      (cl-loop for j from (1+ (nth (- T p) a)) to (1- k) do
                               (setf (nth T a) j)
                               (db (1+ T) T)))))
      (db 1 1)
      (mapcar (lambda (n)
                (nth n keys))
              sequence))))

(defun avy--starts-with-p (list prefix)
  "Return true iff LIST starts with PREFIX."
  (if prefix
      (catch 'found
        (while (= (car list) (car prefix))
          (setq list (cdr list)
                prefix (cdr prefix))
          (unless prefix
            (throw 'found t)))
        (throw 'found nil))
    t))

;; FIXME: This doesn't consider the window of matches yet but only their
;; position.
(defun avy--path-alist-1 (matches seq-len keys)
  (let ((db-seq (avy--de-bruijn keys seq-len))
        prev-pos prev-seq path-alist)
    ;; The De Bruijn seq is cyclic, so append the seq-len - 1 first chars to
    ;; the end.
    (setq db-seq (nconc db-seq (cl-subseq db-seq 0 (1- seq-len))))
    (cl-labels ((subseq-and-pop ()
                                (when (nth (1- seq-len) db-seq)
                                  (prog1 (cl-subseq db-seq 0 seq-len)
                                    (pop db-seq)))))
      (while matches
        (let* ((cur (car matches))
               (pos (caar cur))
               (path (if prev-pos
                         (let ((diff (- pos prev-pos)))
                           (when (and (> diff 0) (< diff seq-len))
                             (while (and (nth (1- seq-len) db-seq)
                                         (not (avy--starts-with-p
                                               (cl-subseq db-seq 0 seq-len)
                                               (cl-subseq prev-seq diff))))
                               (pop db-seq)))
                           (subseq-and-pop))
                       (subseq-and-pop))))
          (if (not path)
              (setq matches nil
                    path-alist nil)
            (push (cons path (car matches)) path-alist)
            (setq prev-pos  pos
                  prev-seq path
                  matches (cdr matches))))))
    (nreverse path-alist)))

(defun avy--path-alist (matches keys)
  "Returns as alist with entries (PATH . MATCH)."
  (let* ((seq-len 1)
         (path-alist (avy--path-alist-1 matches seq-len keys)))
    (while (not path-alist)
      (cl-incf seq-len)
      (setq path-alist (avy--path-alist-1 matches seq-len keys)))
    path-alist))

(avy--path-alist matches avy-keys) returns an alist where the entries have the form (PATH . MATCH) and there are (length matches) entries of course.

What remains to be done is to convert this alist into the tree representation of avy-tree. Ah, and avy--path-alist-1 should also consider the window of matches although that's not really important because when its not considered, the only difference is that if the last match in w1 is at position 99 and the first match in w2 is at position 101, there is a chance that a De Bruijn subseq gets skipped because the algorithms thinks there is an overlap which of course isn't there.

[PythonNut]

Strange, I finished this just last afternoon.

(eval-when-compile (require 'cl-lib))

(defmacro avy-multipop (lst n)
  "Remove LST's first N elements and return them."
  `(if (<= (length ,lst) ,n)
     (prog1 ,lst
       (setq ,lst nil))
     (prog1 ,lst
       (setcdr
         (nthcdr (1- ,n) (prog1 ,lst (setq ,lst (nthcdr ,n ,lst))))
         nil))))

(defun avy-de-bruijn (k n terms)
  "De Bruijn sequence for alphabet `k' and sub-sequences of length `n', for a
minimum of `terms' terms"
  (catch 'return
    (when (= k 0)
      (throw 'return (vector)))
    (let ((a (make-vector (* n k ) 0))
           (sequence (vector))
           (db (lambda (T p)
                 (if (> T n)
                   (when (eq (% n p) 0)
                     (setq sequence
                       (vconcat sequence
                         (cl-subseq a 1 (1+ p))))
                     (when (< (+ terms n) (length sequence))
                       (throw 'return sequence)))
                   (setf (elt a T) (elt a (- T p)))
                   (funcall db (1+ T) p)
                   (cl-loop for j from (1+ (elt a (- T p))) to (1- k) do
                     (setf (elt a T) j)
                     (funcall db (1+ T) T))))))
      (funcall db 1 1)
      (throw 'return sequence))))

(defun avy-partition (k n)
  "The optimal block sizes for alphabet k and number of targets n.
k is partitioned into De Bruijn blocks that cover n with minimal depth."
  (let* ((max-order (ceiling (log n k)))
          (var (vconcat
                 (make-vector (1- max-order) 0)
                 (list k)))
          (i (1- (length var))))
    (catch 'return
      (while t
        (if (eq (elt var i) 0)
          (progn
            (when (eq i 0)
              (throw 'return var))
            (cl-decf i))
          (cl-decf (elt var i))
          (when (/= i 0)
            (cl-incf (elt var (1- i))))
          (when (< (apply #'+
                     (cl-mapcar #'expt var
                       (number-sequence 1 (length var))))
                  n)
            (cl-incf (elt var i))
            (cl-decf (elt var (1- i)))
            (if (= i 0)
              (throw 'return var))
            (cl-decf i)))))))

(defun avy-tree* (lst keys)
  (let ((targets-needed 0)
         (last-target-point 0)
         (depth-guess (ceiling (log (length lst) (length keys)))))
    ;; compute the total number of targets needed, including edge cases
    (mapc (lambda (loc)
            (let* ((pos (caar loc))
                    (delta (- pos last-target-point)))
              (if (< delta depth-guess)
                (cl-incf targets-needed delta)
                (cl-incf targets-needed 1))))
      lst)
    (let ((partitions (avy-partition (length keys) targets-needed))
           (keys-left keys))
      ;; compute the de-brujin blocks
      (setq partitions
        (cl-mapcar
          (lambda (k n)
            (let* ((block-keys (if (/= k 0) (avy-multipop keys-left k)))
                    (seq (mapcar (lambda (char)
                                   (elt block-keys char))
                           (avy-de-bruijn k n targets-needed)))
                    (result))
              seq
              (cl-loop for i from 0 to (1- (- (length seq) n)) do
                (setq result (cons (cl-subseq seq i (+ i n)) result)))
              (nreverse result)))
          partitions
          (number-sequence 1 (length partitions))))
      partitions)))

We're pretty much in the same place, so I'll let you continue the development. The major differences are:

1. I switched to vectors, because O(n) nth was bothering me philosophically.
2. I have the concept of blocks, which are independently computed sequences of different path lengths (over independent subsets of avy-keys).

1 2  3    Block #
  .. ...
a df ggi
b de ggh
c dd ggg

This is so we can have a worst case path length, but still give some targets a better path length. I don't have a closed form solution for the optimal block sizes, so I use gradient descent instead.

I'm no lisp expert. Python I can do, Elisp, not so much. I'll let you continue the development.

[tsdh]

@abo-abo @PythonNut I've pushed my changes to a separate branch of my fork https://github.com/tsdh/avy-jump/tree/de-bruijn.

I think the actual calculation and tree-building is correct. What's missing is the UI/overlay changes, and I'd welcome if @abo-abo could give this a whirl. Basically, the at-full style should now be able to fully write out each path, because if there is some overlap the overlapping parts are equal anyway.

[PythonNut]

@tsdh the math seems to be working out. I have a hard time telling because of the way the overlays are implemented.

@abo-abo How difficult would it be to fix at-full for this?

[abo-abo]

@abo-abo How difficult would it be to fix at-full for this?

Hard to say. There aren't any test cases, so I don't know if it's working at all. Plus the avy-tree was rewritten to a different data type. Since it doesn't fit the current interface, I can't check if it works correctly or at all.

[tsdh]

@abo-abo The avy-tree function in the branch https://github.com/tsdh/avy-jump/tree/de-bruijn returns a tree of the same format as it is right now. So it should theoretically be a drop-in replacement for the master branch's avy-tree function.

[abo-abo]

So it should theoretically be a drop-in replacement for the master branch's avy-tree function.

It wants to take caar of MATCHES, if I understood correctly. That doesn't fit the current interface.

[tsdh]

It assumes that MATCHES is a list of matches where each match has the form ((start-pos . end-pos) . window). With caar it (or rather avy--path-alist-1) accesses the start-pos of a match. Isn't that a valid assumption?

[abo-abo]

Isn't that a valid assumption?

No. It's valid sometimes, but the original avy-tree puts no assumption on the structure of the arguments.

For example, in ace-window the type is (pos . window).

[tsdh]

Ok, I see. I could test if the car of a match is a cons or a plain integer to work around this exact issue. But it's not possible to be completely agnostic to the match representation because the algorithm requires the start position and the window in order to figure out if a subpart of the De Bruijn sequence needs to be skipped when there are almost adjacent matches.

[abo-abo]

I've just had a test of the code and it seems to work fine.

You should try to integrate it if you have the time.

My suggestion:

• add another style 'de-bruin to the 4 that we have
• rename to avy-tree-debruin
• modify avy--generic-jump to call either avy-tree or avy-tree-debruin
• use a log estimate to compute seq-len at once in avy-tree-debruin instead of just consing and iterating a bunch of times
• try to avoid the dependency on seq.el, a hash table may work instead

Then just tie avy--generic-jump to use this overlay fn for 'de-bruin:

(defun avy--overlay-debruin (path leaf)
  "Create an overlay with PATH at LEAF.
PATH is a list of keys from tree root to LEAF.
LEAF is normally ((BEG . END) . WND)."
  (let* ((str (propertize
               (apply #'string (reverse path))
               'face 'avy-lead-face))
         (len (length path))
         (beg (if (consp (car leaf))
                  (caar leaf)
                (car leaf)))
         (wnd (cdr leaf)))
    (when (> (length str) 1)
      (set-text-properties 0 1 '(face avy-lead-face-0) str))
    (with-selected-window wnd
      (save-excursion
        (goto-char beg)
        (let* ((end (min (+ beg len) (line-end-position)))
               (ol (make-overlay
                    beg end
                    (current-buffer)))
               (old-str (buffer-substring beg (1+ beg))))
          (when avy-background
            (setq old-str (propertize
                           old-str 'face 'avy-background-face)))
          (overlay-put ol 'window wnd)
          (overlay-put ol 'category 'avy)
          (overlay-put ol 'display (if (string= old-str "\n")
                                       (concat str "\n")
                                     str))
          (push ol avy--overlays-lead))))))

[tsdh]

@abo-abo Cool, I'm gonna do that as soon as I find some spare time.

Wrt. seq-len, I can easily add an estimate so that we start with the shortest path length that works for the number of matches in case there are no "almost adjacent" overlaps. Of course, it's still possible that seq-len needs to be incremented if there are many such overlaps which don't allow for using all subsequences of the De Brujin seq. But you are right that it's suboptimal to try 1-char sequences if there are 20 matches but only 8 avy-keys.

[PythonNut]

There seems to be a slight bug where the overlays start incorrectly marking decision chars.

Example Jump text

;; This buffer is for notes you don't want to save, and for Lisp evaluation.
;; If you want to create a file, visit that file with C-x C-f,
;; then enter the text in that file's own buffer.

;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;

Other than that, it seems to work perfectly!

There is one other possible difficulty: it's hard to tell how many characters a certain target needs. Of course, you can tell from context (you can scan forward to the end of the cluster and count the number of non decision chars to determine the needed length.)

I'm not entirely sure how to solve this. One way would be to have different color decision chars based on the number of characters left to type. (As far as I can tell, this is the way evil-easymotion does it. They have yellow for single character jumps and red for two character jumps (no idea what happens if they need three characters). Of course this is

• probably confusing for beginners
• a lot of code for just one style

I'm convinced that the second isn't much of a problem. (We already have quite a bit of code dedicated to this style). The first is probably also a non-issue, as de-bruijn will probably not come as the default.

[tsdh]

@PythonNut I can reproduce that, but for me all three lines look like your first line of semicolons, e.g., after the first two lead chars, only every second char is shown as a lead char although every char is.

Aside from that, could you please open a separate issue for that? This issue is solved IMHO and already has a gazillion comments completely unrelated to this specific bug.

@abo-abo Please close this one.

[abo-abo]

@abo-abo Please close this one.

It's been closed for weeks now :)

[tsdh]

Ups. ;-)