1

I want to search for a combination of two or more strings, in any order. I use org-mode.

  • 1
    Please clarify what you want to do, and what you have tried so far. – Dan Nov 3 '16 at 21:17
  • @Dan. I want to search for lines containing a combination of names, years, and attributes. For example, "Adam Smith 1900 history", but the words can be in any order. I normally would use I-search and type a regexp, but I need the flexibility here regarding the order of elements. – Quora Feans Nov 3 '16 at 21:19
  • Please also clarify what you have tried so far. It looks like you could use regular expressions. – Dan Nov 3 '16 at 21:20
  • @Dan how can I then combine multiple regexps? Or create a regexp where order is indifferent? – Quora Feans Nov 3 '16 at 21:21
1

Another easy way to do what you want is to use Icicles. With Icicles search you first define search contexts, and then you type patterns to match within the contexts.

You can define contexts using a regexp, or several other ways. And some Icicles search commands define contexts for you. For example, icicle-occur, bound by default to C-c ', the contexts are lines. For icicle-search, bound by default to C-c `, you are prompted for a context-defining regexp.

After establishing the search contexts, whatever you type in the minibuffer is taken as a pattern (e.g. a regexp) to match within the contexts.

It is Icicles progressive completion that provides the answer to your question. To match another search pattern you just hit S-SPC, locking in the previous one, and then type another. The patterns are ANDed, each one narrowing the search further.

Because this is all done by matching minibuffer input against completion candidates, you can change the current pattern to match anytime, incrementally. And because each S-SPC creates a recursive minibuffer, you can also use C-] to pop out of the current pattern inputting altogether and change the previous, formerly "locked in" pattern. You can thus input an infinite number of sets of matching patterns, to search for different things within the set of search contexts.

Harder to describe than to experience...

1

Drew already described ways of recursive filtering lines.

You can also use occur (already shipped with emacs) recursively for that purpose.

To search for a line containing the words Adam Smith 1900 history use occur on Adam in the original buffer. Afterwards use occur on Smith in the resulting occur-buffer. Afterwards use occur on 1900 in the resulting buffer and finally use occur on history in the resulting buffer.

Afterwards you can go back to the line containing all words in the original buffer recursively through the occur buffers.

There are some false positives with this method. E.g., if you are searching for the word matches also the first line of an occur-buffer matches. But, these should not disturb too much.

1

If you are searching files, and if you only care about search contexts that are lines of text, then you can use M-x grep. You just keep piping grep commands, to add additional filters. The resulting lines are those containing matches for each of the filters, in any order.

For example:

M-x grep -nH -e for icicles-doc.el | grep the | grep function

icicles-doc1.el:1758:;; prompts you for a function to apply to the current completion

icicles-doc1.el:2415:;; For most Emacs functions that prompt you for input, the person who

icicles-doc1.el:4182:;; candidates are proxy candidates for these functions.)

icicles-doc1.el:4783:;; The second argument is the actual function used for sorting. It

icicles-doc1.el:5532:;; function is designed to be `C-u' sensitive. This is the case for

icicles-doc1.el:6241:;; prompts you once for the function to apply, and then applies it to

icicles-doc1.el:6270:;; function for some command. Do this if you always want the same

icicles-doc1.el:6302:;; predefined for type `function'. Since the actions you can choose

icicles-doc1.el:6304:;; them, to apply a function-for-functions (e.g. `find-function' or

...

1

Regular expressions will only get you so far, if you want to search for multiple things in any order. The regexp you use needs to specify each possible order for the things. For two or three things that's not such a big deal, but for more it quickly becomes problematic. A single regexp is not your friend when trying to match patterns in any order.

I'm assuming that you want to do this searching interactively. If you use library Isearch+ you can easily do what you request.

  1. The first thing you do is search for a general context. For example, C-M-s .* searches for full lines. (But you are by no means limited to defining line contexts; a search context can be any zone of text.)

  2. Then you impose an Isearch filter predicate that restricts the set of matching lines to those that also match your first pattern (a regexp). For example, to restrict search to lines that contain cat you do this (during the same search for .*:

    C-z % cat

  3. Then you do the same for another pattern you want the lines found to also match:

    C-z % dog

  4. And so on: C-z % turtle...

    C-z % prompts you for a pattern, which is in fact a regexp, so you are not limited to a literal sequence such as turtle.

What happens is that when you enter a regexp, Isearch+ constructs a predicate that filters for its matches - within the current set of search hits.

There are lots of other ways that Isearch+ provides to dynamically refine search contexts, besides regexp matching. This page about its Dynamic Isearch Filtering describes this and various other ways to combine multiple Isearch filters.

  • "Regular expressions will only get you so far" That's why I am here. – Quora Feans Nov 3 '16 at 21:43
  • Right. The point is that a single regexp that matches multiple orders is hard to come up with, and is not very performant. But code that combines multiple simple regexps can do the job easily. Isearch lets us filter what would otherwise be search hits by applying a predicate. Such a predicate can limit searches to also match another regexp. That's what C-z % does: it piles another filtering predicate on top of any filtering that is already being done. Isearch+ lets you combine any number of such filters, on demand. – Drew Nov 3 '16 at 21:47
0

Just as an exercise, here's a more occur-like way to search for matching lines:

(defvar search-multi-mode-map nil
  ;; (let ((map (make-sparse-keymap)))
  ;;   (define-key map (kbd "RET") 'search-multi-goto)
  ;;   map)
  "Keymap for `search-multi-mode'.")

(defvar search-multi-mode-hook nil
  "These hooks are run when `search-multi-mode' starts")

(define-derived-mode search-multi-mode fundamental-mode "Search-Multi"
  "Major mode for searching for multiple words in a buffer.

Available commands:
\\{search-multi-mode-map}"

  (run-hooks search-multi-mode-hook)
  (buffer-disable-undo)
  (read-only-mode 0)
  (erase-buffer)
  (insert ";; -*- mode: multi-search -*-\n\n")
  (read-only-mode 1))

(defun search-multi-goto (button)
  (interactive)
  (let ((line (button-get button 'line)))
    (with-current-buffer (pop-to-buffer search-multi-source)
      (goto-char (point-min))
      (forward-line (1- line)))))

(defvar-local search-multi-source nil
  "The source buffer where the search was performed")

(defun search-multi-popup (matches)
  (let ((b (current-buffer)))
    (with-current-buffer (get-buffer-create "*multi-search*")
      (search-multi-mode)
      (read-only-mode 0)
      (setq-local search-multi-source b)
      (insert "searched: " (buffer-name b) "\n\n")
      (while matches
        (let ((match (car matches))
              (p (point)))
          (insert (format "%d: %s" (car match) (cdr match)))
          (make-text-button p (point)
                            'face 'font-lock-variable-name-face
                            'action 'search-multi-goto
                            'line (car match)))
        (setq matches (cdr matches)))
      (read-only-mode 1)
      (pop-to-buffer (current-buffer)))))

(defun search-multi (words)
  (interactive "MWords to search (separate with space): ")
  (let ((words (sort (split-string words " ") 'string-lessp))
        (current-line 0)
        matches)
    (while (not (eobp))
      (setq current-line (1+ current-line))
      (let* ((raw-line (buffer-substring-no-properties
                        (point)
                        (progn (forward-line) (point))))
             (line
              (sort (split-string raw-line "[^[:alnum:]]" t)
                    'string-lessp))
             (words words))
        (catch :failed
          (while (and words line)
            (let ((a (car words))
                  (b (car line)))
              (cond
               ((string-equal a b)
                (setq words (cdr words) line (cdr line)))
               ((string-lessp b a)
                (setq line (cdr line)))
               (t (throw :failed t)))))
          (unless words
            (setq matches
                  (cons (cons current-line raw-line) matches))))))
    (search-multi-popup matches)))

(provide 'search-multi)
0

The following lisp code provides you with a single command that finds a line containing all words given by the user as space-separated list in any order. You can apply this command iteratively to find consecutive matching lines using the input history. This is ensured by placing point at the end of the matching line. The search starts at point. If you place point in the middle of some line then only the partial line starting at point is tested.

If you want to avoid regexp-matches replace string-match by string-equal.

(require 'cl-lib)

(defun search-forward-words-in-line (words)
  "Search forward for a line containing some words in any order.
WORDS is a string of words separated by spaces.
Search starts at the line where point is in.
Puts point on the end of the found line.
So you can use this command iteratively."
  (interactive "sSpace separated list of words:")
  (let ((word-list (split-string words))
    found)
    (while (and (null (eobp))
        (null (setq found (cl-subsetp word-list (split-string (buffer-substring-no-properties (point) (line-end-position))) :test #'string-match))))
      (forward-line))
    (and found (goto-char (line-end-position)))))

There follows an alternative implementation with an associated special occur named occur-words-in-line in the following. The function re-search-forward is hijacked by occur-search-forward-words-in-line during the execution of the original occur.

I had to modify the behavior of search-forward-words-in-line to make this work. The new version of this function applies re-search-forward starting at the beginning of the line that contains all the words from wordstr or at point if point was initially in the middle of the line. It places point and determines its return value and match data by this call of re-search-forward.

(defun search-forward-words-in-line (wordstr &optional bound noerror)
  "Search forward for a line containing the words from WORDSTR in any order.
WORDS is a string of words separated by spaces.
Search starts at the line where point is in."
  (interactive "sSpace separated list of words:")
  (unless bound (setq bound (point-max)))
  (let ((word-list (split-string wordstr))
    line
    found)
    (while (and (< (point) bound)
        (setq line (buffer-substring-no-properties (point) (min bound (line-end-position))))
        (null (setq found (cl-subsetp word-list (split-string line) :test #'string-match))))
      (forward-line))
    (if found
    (let ((b (line-beginning-position))
          (e (line-end-position)))
      (goto-char b)
      (re-search-forward (concat "\\(" (mapconcat #'identity word-list "\\)\\|\\(") "\\)") e)) ;; Set `match-data', place point and return beginning of match.
      (unless noerror
    (error "Line with words %s not found" word-list))
      )))

(defun occur-words-in-line (words &optional nlines)
  "Linke `occur' but with `re-search-forward' replaced by `search-forward-words-in-line'."
  (interactive "sSpace separated list of words:\nP")
  (setq nlines (and (numberp nlines) nlines))
  (let* ((original-re-search-forward (symbol-function 're-search-forward))
     (words-in-line-words words)
     (word-list (split-string words))
     (words-in-line-re (concat "\\(" (mapconcat #'identity word-list "\\)\\|\\(") "\\)")) ;; we keep regular expressions
     words-in-line-re-search-forward)
    (setq words-in-line-re-search-forward
      (lambda (words &optional bound noerror)
        (fset 're-search-forward original-re-search-forward)
        (prog1 (search-forward-words-in-line words-in-line-words bound noerror)
          (fset 're-search-forward words-in-line-re-search-forward))))
    (unwind-protect
    (progn
      (fset 're-search-forward words-in-line-re-search-forward)
      (occur words-in-line-re nlines))
      (fset 're-search-forward original-re-search-forward))))

The programming of occur-words-in-line would have been much cleaner if occur provided search-plugins such as query-replace-regexp does with replace-re-search-function.

  • In terms of algorithmic complexity it would be more efficient to first sort both lists and then to compare. cl-subsetp is a naive quadratic algorithm. Though I understand that the number of words is probably small, so the gains won't be noticeable if any. – wvxvw Nov 4 '16 at 13:01
  • @wvxvw The number of words is small and sort adds complexity to the lisp-code in the answer. Simple code was the main design criterion at this point. (Note, that I considered to use sort but dismissed it in favor to simple code.) – Tobias Nov 4 '16 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.