Fuzzy completion like in slime for Common Lisp

[bulat-nazarov-medved]

Need fully fuzzy completion like in slime for Common Lisp. Current fuzzyness is too simple.

[alexander-yakushev]

Can you please elaborate which exact fuzziness do you lack? The one that matches message when you write messaeg (like in Elisp)?

[bulat-nazarov-medved]

Suppose we have defined symbol get-last-message-date
after getlameda I want it to be expaned in get-last-message-date. If we also have symbol get-longest-media-datum it will be expaned to list. But if we type getlameada it will be expanded only to get-longest-media-datum

[alexander-yakushev]

Can't say I understood your last example (about getlameada) but anyway, I suspect that enabling this kind of completion will be detrimental to the completion performance. Although I welcome you (or anyone) to try implementing this kind of fuzziness (by using regexps or anything else) and benchmark the performance in this case.

[bulat-nazarov-medved]

Can be implemented as configurable option.

[turtle-bazon]

I also interested in fuzzy completion. And I prepared 3 functions. First use .startsWith as compliment project use. Second use same as .startsWith, but implemented in pure clojure. Third is desired fuzzy completion:

(defn match-1 [string-to-match template]
  (.startsWith string-to-match template))

(defn match-2 [string-to-match template]
  (every? true? (map = string-to-match template)))

(defn match-3 [string-to-match template]
  (if (empty? template)
    true
    (if (empty? string-to-match)
      false
      (if (= (first string-to-match) (first template))
        (match-3 (rest string-to-match) (rest template))
        (match-3 (rest string-to-match) template)))))

I performed some measures and can't say, that match-2 and match-3 lacks completion performance. But my amount of data for measures was too small and I can make mistake. I suppose you to benchmark that functions and integrate it in completion to acheive fuzzy completion.

[alexander-yakushev]

OK, I take my words about performance back. The performance of naive matching by @turtle-bazon is actually on-par with the parts-match method Compliment uses.

Although there is one more thing to consider. This fuzziness adds a lot of noise to the candidates list. For example, con matches count, second and Exception. To me it is distracting. Maybe the fuzziness should still work only on separator boundaries (like - or .), but those separators can be optional in the prefix? What do you say?

[alexander-yakushev]

Alrighty, I pushed the new fuzziness in 0.2.0-SNAPSHOT, please try and tell if your brain became all fuzzy-wuzzy. For me it all seems so fizzy that I feel kinda dizzy!

[bulat-nazarov-medved]

Ok, I'll see It later. About fuzzy. We can make fuzzy completion only on prefix lengths that more than x.

[alexander-yakushev]

We can make fuzzy completion only on prefix lengths that more than x.

I don't think that will work well. Quite often I start the completion on small prefixes and expect fuzziness to work. Anyway, I settled with the initial method (kind of "splitting" on separators), but the separators are optional to type now. So cji would complete Clojure.Java.Io, but wouldn't do CloJure-versIon.

[bulat-nazarov-medved]

Hmmm... What can I say? It cool, but there some small thing that I prefer. For example, get-last-metadata should fuzzy completed by gelameda, but now it not because it uses separator. I think there should be completion not based on separators. Camel case completion for java cool and should be. For nose in slime calculated relevance and completion sorted by relevance. We can say, that fuzzy completion should start if prefix length is more than, for example, 4 characters.

[bulat-nazarov-medved]

I think that sorting by relevance should be what I want, but now can't suppose calculation formula for it.

[bulat-nazarov-medved]

Also I think that fuzzy camel comletion implemented for Java classes should be as it is now. For all sorts of completion, I think, we should restrict in case that first symbols of prefix and compared string must match.

[alexander-yakushev]

We can say, that fuzzy completion should start if prefix length is more than, for example, 4 characters.

Possible, but again it seems like catering to only a small number of usecases. get-last-metadata can be completed fine with gelame, and then pressing Down once or twice.

first symbols of prefix and compared string must match.

Yes, it is already like that.

I think that sorting by relevance should be what I want, but now can't suppose calculation formula for it.

That could work, yes. But I've already heard people complaining about CIDER getting unreasonably bloated and complex. Keeping that in mind, I don't want to add any more sophistication to Compliment where it is not necessary. So for now I will close this issue (as the completion became fuzzier, in fact) and see how it will work. If people want even more fuzziness, we can get back to it later.

[bulat-nazarov-medved]

If i don't remeber if it get-last-meta-data or get-last-metadata I can see no results for second case if i try to complete gelameda. So, I think that it should be without delimiters.

[turtle-bazon]

Oh-oh-oh! I work intensively with korma and on fields it works as is. Ie if we give them (sql-only (select users (fields :user-info))) it generates sql query "SELECT "users"."user-info" FROM "users"". And that query cannot be executed properly on database and will raise exception. So on work with korma I can't use fuzzy completion. And it is sad. Equality of first symbol and then fuzzy complete should be sufficient.

[alexander-yakushev]

@turtle-bazon I'm sorry, I couldn't understand what is the problem. Does the query fail because of Compliment? Can you please explain clearer?

[turtle-bazon]

This query fails because it's SQL server limitation. Insted of user-info I need to use user_info or userinfo. So scenario for completion fails, because compliment uses \- as separator.

[alexander-yakushev]

Well, _ isn't used anywhere in Clojure. And free-for-all completion scheme proves to be too confusing. I'm aftraid there is nothing I can do about this case. Besides, it's also Korma problem that it doesn't munge the keywords.

[turtle-bazon]

Now it is my problem. :) And it can be easily solved if we do not use separators in compliment.

[alexander-yakushev]

Not possible, sorry. Please read the whole thread.

[turtle-bazon]

I've read whole thread and doesn't see any problem for it. \- used only for decreasing completion noise. But with my experience I can say that equality of first symbol and then fuzzy complete decrease noise enough. So I propose to make completion without separators.

[bbatsov]

@alexander-yakushev Did you document anywhere the usage of this feature? Seems to me it was developed without a clear definition.

[alexander-yakushev]

@bbatsov Not yet. Seems like it is time to update Examples page, it haven't been touched in a while. Briefly speaking, nothing has changed besides the fact that you can now omit typing separators to execute the completion, so that both a-mand am match alter-meta!.

[bulat-nazarov-medved]

It is more convenient for alter-meta! type ameta and press complete rather than type a, then type -, them meta because \- sign is inconvenient for thoose who practice 10 finger typing. And It lacks performace of typing for people at all. Not computer performance.

[alexander-yakushev]

Well, that's how it works now, doesn't it?

[bulat-nazarov-medved]

Yes, it is.

[bulat-nazarov-medved]

From my current project:

(def appnamestring "smsdiarysync")
(def studentsnamestring "students")
(def employeesnamestring "employees")
(def parentsnamestring "parents")
(def classesnamestring "klasses")

Yes. We can say that it is naming problem in my code. But I have limitations. And this is fact.
Next:

(defn parents-timestamp []
  (find-version parentsnamestring))

Idiomatically write timestamp, not time-stamp. And parents-timestamp I can't complete with partstam. It is limitation and it is fact. Do not know how it more convenient rename it parents-time-stamp.
Next:

(initialize @operating-backend)

Word initialize is too long. And we can complete it by init. But there can be more inits. Especially in project where we initialize many things. So there will be interesting to complete it with inilize.

(def staffcards-id-pool general-generator)

There is also namin convention problem. My entity in database named as staffcard. And to be close to each other I also named my class representing database entity as staffcard. Database doesn't developed by me and it is given to me as is. I can rename it to staff-card to be able complete as stacard, but It be some confusing to me.

Also some functions that should be generated to java class named with _. So it is not fatal current implementation, but bit annoying. Anyway current implementation of fuzzy complete much more better than without it. But it'll be cool if it can be better than now. :)

[alexander-yakushev]

We can say that it is naming problem in my code.

Yes, there is a naming problem in your code. If you have, say, both classesnamestring and classesnameint, so that the current fuzziness doesn't help you, then you have even bigger problem and completion has nothing to do with solving it.

Regarding all your examples.

People use auto-completion for two different purposes. The first one is to complete something that they already know (just don't want typing it all). In this case you write the minimal sufficient string so that the completion happens immediately without the menu popping up. Your examples are from this category. There are also cases when completion is used for discovery. In this case users type their query small and then call the completion to see the list of items they can choose from. If fuzziness is completely out of control, they will see a lot of noise that is both confusing and irritating.

You are welcome to make a fork, replace the matching function with the one that @turtle-bazon provided, then make build of Compliment and use it in your projects. This will both solve your problem, and you will be able to test whether this approach works for you, so that sometime later we can get back to this question.

Having said that, this is my last message in this thread.

[turtle-bazon]

Hmm... Before you quit can you give me level noise on this types of completion? For example, with fuzzy proposed these by me, but with first symbols match and with your fuzzyness implementation?

[laurentpetit]

CCW uses fuzzy completion, and "solves" (empirically) the possible confusion issue by sorting the the list by first making "full match" come first, then fuzzy matches with preference for narrower matches over broader matches. So far it's worked well. Also, if the unfiltered list is too big (empirical limit of 50 elements), fuzzy completion filtering is not used, plain ".contains" filtering is used.

Even though it seems quite non scientific and somewhat subjective, this combo has worked well in practice, to the extent that nobody complained that true "match-considering-separators" has not been implemented!

[alexander-yakushev]

This might work, but will require a significant rewriting of most sources. Performance also needs to be considered. Overall, I don't feel like it is worth the trouble, few examples provided in this thread are too marginal to bother. As I've said before, completion has two goals — exploratory, when you don't know what you want; and auxiliary, when you do. It doesn't have a goal to play Scrabble with user and guess what they meant by whatever symbols they typed in.

Add the fact that fuzzy matching has to be implemented on both Compliment side (Clojure) and Emacs auto-complete side (Elisp), because AC does not repoll the backend as user continues typing after initial completion request. Also, matching first symbol can no longer be used as a hard filter for candidates because of #20.

If I get a working and sane pull request that covers all the above considerations, I will accept it, but I highly doubt it is something that one should put time into.

[laurentpetit]

You are probably right and I should refrain myself from working on it yet. I will first deliver CCW with what compliment offers through cider, and wait for the users reactions. And then wait a little bit more (once they're used to the new behavior). Only then will I consider true fuzzy completion again, if the complaints stream does not stop.

I'm not sure what you mean by "matching first symbol can no longer be used ..."?

[alexander-yakushev]

There was an argument in this thread that regardless of the fuzziness completion should only work if the first symbol of the prefix matches the first symbol of the candidate. And it was so, until #20 introduced candidates that don't confirm to this rule (Arr expands to java.util.ArrayList). While this change touches only the classname source, Emacs side of the completion doesn't know about sources, and it uses one-size-fits-all fuzzy filter. Which means I no longer use first-symbol rule when matching.