New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Properly support matching ignoring order #329

Closed
jyp opened this Issue Dec 26, 2015 · 4 comments

Comments

Projects
None yet
3 participants
@jyp
Contributor

jyp commented Dec 26, 2015

I'd like to replace helm by avy in my configuration, but I cannot live with proper support for matching parts of the input in any order.

As indicated in #296, ivy--regex-ignore-order behaves incorrectly. It was concluded that doing matching by building a regexp matching all the permutations would be prohibitively slow. I'd like to offer the following counter arguments:

  1. If the user is willing to pay this cost, why not allow it?
  2. Notwithstanding the above point, the conclusion was reached on the assumption that the cost of matching a regexp is proportional to the length of the regexp. However, a proper regexp matcher should not behave like this. I'm guessing that emacs' native matcher is 'bad', but one could use an efficient matcher. (There exists a 'good' elisp implementation: http://www.emacswiki.org/emacs/TaggedNFA)
  3. Even using a slow matcher, one can implement matching-ignoring-order by filtering the candidates with each of the sub-expressions, in series. In fact, ivy--filter has already code to support this behaviour today:
                         (dolist (re re-list)
                           (setq res
                                 (ignore-errors
                                   (funcall
                                    (if (cdr re)
                                        #'cl-remove-if-not
                                      #'cl-remove-if)
                                    (let ((re-str (car re)))
                                      (lambda (x) (string-match re-str x)))
                                    res))))

unfortunately, several other places in the code assume that the regexp is a string. That is, if ivy--regex-ignore-order was to return a list, errors would be thrown.

Would it be reasonable to support list of regexps consistently?

@Konubinix

This comment has been minimized.

Show comment
Hide comment
@Konubinix

Konubinix Jan 2, 2016

Contributor
Contributor

Konubinix commented Jan 2, 2016

@jyp

This comment has been minimized.

Show comment
Hide comment
@jyp

jyp Jan 2, 2016

Contributor

Thanks for the feedback. I'll see what I can do. Yet, the first step will be to obtain a copyright assigment from my employer, so don't hold your breath :)

Contributor

jyp commented Jan 2, 2016

Thanks for the feedback. I'll see what I can do. Yet, the first step will be to obtain a copyright assigment from my employer, so don't hold your breath :)

@abo-abo abo-abo closed this in 93d1adc Jan 7, 2016

@abo-abo

This comment has been minimized.

Show comment
Hide comment
@abo-abo

abo-abo Jan 7, 2016

Owner

Thanks, please test.

Owner

abo-abo commented Jan 7, 2016

Thanks, please test.

@Konubinix

This comment has been minimized.

Show comment
Hide comment
@Konubinix

Konubinix Jan 8, 2016

Contributor
Contributor

Konubinix commented Jan 8, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment