[FR] add `orderless-without-regexp`

[NightMachinery]

[oantolin]

Sorry, I have no idea what this means! Can you explain a bit?

[NightMachinery]

@oantolin It's like orderless-without-literal, except it excludes everything that matches a regex.

[oantolin]

Oh, I see! Sorry, I think I forgot what orderless-without-literal was called and didn't see the parallel.

I'm actually not sure an orderless-without-regexp is possible for the full Emacs regexp syntax with includes backreferences. It is possible for the subset that implements regular languages. But even for the regular language subset it can get cumbersome to implement. I guess the nice thing is that one can extend the implementation gradually and every bit of extra syntax supported is a nice little improvement.

[NightMachinery]

Yes, a gradual implementation can work. Ivy already supports this (no idea how completely) in its ivy—plus-regex (not sure about the name, I’m on mobile now). Perhaps check out what they do.

[oantolin]

Ivy just loops over the results and removes the ones that match the negative regexps. Orderless on the other hand turns the literal into a regexp that matches anything that does not contain the literal.

The way orderless does it you can take advantage of a loop written in C inside Emacs that finds all the completion candidates that match all the regexps in a list. Ivy on the other hand has to loop over the results in an Emacs Lisp function. This is why I don't want to do it the Ivy way.

So what use cases did you have in mind for this feature? (Back when I used Ivy I only ever used negative literals.)

[NightMachinery]

I currently only use this in one of my functions, to exclude IRC posts that I have posted myself, and only see other people's mentions of me: (concat me " !\\(^[[:space:]]*\\*+\\|^[[:space:]]*" me "\\)")

But it's one of those things that's pretty useful in general, in ad-hock searches; E.g., I want to exclude time.?loop, it would be a pain to do this literals.

[daanturo]

Currently I try to achieve this by defining a new completion style.

Idea: Given the arguments STRING, TABLE, PRED, _POINT, it will check STRING for patterns after " !" to :

• Tweak STRING: remove anything after " !" (if any)

and the important part:

• Decorate PRED to exclude candidates that match one of valid patterns after " !"

;;;###autoload
(add-to-list 'completion-styles-alist
             '(my-completion-style
               my-completion-style-try-completion
               my-completion-style-all-completions
               ""))

;;;###autoload
(defun my-completion-style-try-completion (string table pred point)
  (my-completion-style-process #'orderless-try-completion string table pred point 'may-change-point))

;;;###autoload
(defun my-completion-style-all-completions (string table pred point)
  (my-completion-style-process #'orderless-all-completions string table pred point))

(defun my-completion-style-process (complete-func string table pred point &optional may-change-point)
  (cl-destructuring-bind (new-str new-pred)
      (my-completion-style-compute-filtered-input-and-predicate string pred)
    (funcall complete-func
             new-str table new-pred
             (if may-change-point
                 (min point (length new-str))
               point))))

(defun my-completion-style-compute-filtered-input-and-predicate (input pred)
  "Call `my-completion-style-filter-function' on INPUT.
If it returns non-nil new input S and new pred P, return S and a
predicate that satisfies both PRED and P; Else the arguments."
  (-if-let* (((new-input new-pred) (my-completion-style-filter input)))
      (list new-input
            (cond ((and pred new-pred) (-andfn pred new-pred))
                  ((or pred new-pred))))
    `(,input ,pred)))

(defun my-completion-style-filter (input)
  ;; "`without-regexp'": Valid patterns after " !": don't match any of those
  (-let* (((+str . -patterns) (my-partition-patterns-from-special input " !")))
    (and -patterns
         (list
          ;; New input to compare is stripped from " !" onwards
          +str
          ;; For each candidate, we can reject if it matches one of those patterns
          ;; by the `some' loop, but grouping all valid patterns to check at once
          ;; is slightly faster
          (my-candidate-not-match-regexp?-fn (my-group-or-regexps -patterns))))))

;;;###autoload
(defun my-group-or-regexps (regexps)
  (format "\\(?:%s\\)" (string-join regexps "\\|")))

(defun my-partition-patterns-from-special (str special)
  "Return a list whose:
- First element is the string in STR before SPECIAL
- The rest is split patterns after SPECIAL which are valid."
  (-if-let* ((special-pos (string-search special str)))
      (cons (substring str 0 special-pos)
            (--> (substring str (+ (length special) special-pos))
                 (split-string it " " 'omit-nulls)
                 (-take-while #'orderless-regexp it)))
    (list str)))

(defun my-candidate-not-match-regexp?-fn (regexp)
  (lambda (cand &rest _)
    (let ((cand-str (cond ((stringp cand) cand)
                          ((consp cand) (car cand))
                          ((symbolp cand) (symbol-name cand))
                          (t cand))))
      (my-safe-completion-string-not-match-regexp? regexp cand-str))))

(defun my-safe-completion-string-not-match-regexp? (regexp str)
  ;; case-sensitive removals
  (dlet ((case-fold-search nil))
    (not (string-match-p regexp str))))

Although this isn't the same as what Ivy does (manually remove candidates), it still not purely regexp-only.

If orderless exposes STRING and PRED, I think it can be simplified.

[aki2o]

I tried to create a patch that allows us to exclude the matched entries with inputing - prefix string.

  (advice-add 'orderless-filter :around 'my/orderless-let-unmatch-filterable)

  (defun my/orderless-let-unmatch-filterable (orig &rest args)
    (let* ((all-components (funcall orderless-component-separator (nth 0 args)))
           (not-components (cl-remove-if-not (lambda (x) (string-prefix-p "-" x)) all-components)))
      (if (= (length not-components) 0)
          (apply orig args)
        (pop args)
        (let* ((components (cl-remove-if (lambda (x) (member x not-components)) all-components))
               (table (apply orig `(,(mapconcat 'identity components " ") ,(pop args) ,@args))))
          (cl-loop for c in (mapcar (lambda (x) (substring x 1)) not-components)
                   for not-table = (apply orig `(,c ,table ,@args))
                   do (setq table (cl-remove-if (lambda (x) (member x not-table)) table))
                   finally return table)))))

I feel it's not good approach but I shared because it looks work. We can list the entries that matches foo and do not match bar or baz with inputing foo -bar -baz

[minad]

@oantolin What do you think about generalizing the Orderless pattern compilers to either return a regexp string or a function? If a function is returned, it could be combined with the completion predicate. This would allow us to define orderless-without-regexp and simplify/speed up orderless-without-literal.

Furthermore users could define an orderless-annotation matching style which could trigger for the @ dispatcher character and which accesses the annotation-function or affixation-function of the completion table. Such an annotation matcher might be out of scope of Orderless but it would be neat if we could at least define it given the machinery here.

Annotation matching has been requested very often, see the bottom of https://github.com/oantolin/orderless/issues/30. I got reminded about this by https://old.reddit.com/r/emacs/comments/1aqg7kc/how_to_make_orderless_search_marginalia_text_also/.