Non-greedy match for orderless-flex?

[daanturo]

Non-greedy match for orderless-flex?

[oantolin]

I think there was a third style which in addition to being strict anchored the match at the beginning!

Since initialisms already only match characters at word boundaries I don't find this non-strict matching really causes many false positives, at least not for command names which is really the only thing I use initialism matching for.

[minad]

One could even use a variant of flex which is more strict and doesn't skip the same letter. abc -> a[^b]*b[^c]*c. These regexps perform better.

[daanturo]

My implementation, inspired by @minad 's comment:

(defun my-orderless-non-greedy-flex (component)
  (rx-to-string
   `(seq ,@(cl-loop
            for (head . tail) on (string-to-list component)
            collect `(group ,head)
            when tail
            collect `(* (not ,(car tail)))))))

(my-orderless-non-greedy-flex "abc")
=> "\\(?:\\(a\\)[^b]*\\(b\\)[^c]*\\(c\\)\\)"

[oantolin]

Thanks for the suggestion, @daanturo. I went with @minad's suggested compilation.

[minad]

@oantolin Are there more matching styles which could be made more strict such that we get better complexity? Initialism?

I think it is worth the trade off since regexps like the ones generated by the old flex compiler behaved really badly for long candidates. We discussed this a while ago in another issue.

[oantolin]

I don't think initialism would benefit from a similar compilation since it already only matches characters at word boundaries. But it does make sense to think about each style to make sure we aren't missing any obvious compiler optimizations.

[minad]

For initialism does ac match axxx-bxxx-cxxx or only axxx-cxxx? I mean such an optimization, maybe there are others for other styles?

I think I prefer matching less with better performance instead of more flexible matching. I also like literal more than flex. But one should keep in mind that restricting the style may be undesired for other users who prefer more typo tolerance.

[oantolin]

For initialism does ac match axxx-bxxx-cxxx or only axxx-cxxx?

It does match axxx-bxxx-cxxx. There used to be a related matching style called "strict initialism" that would only match "axxx-cxxx".

[minad]

Yes, but didn't the strict style also have anchoring? I thought we could maybe use an unanchored strict style.