Neat.  As an aside, I would love to see a prompt like this for + and
-, allowing multiple tags to be modified at once (and starting out
with whichever of + or - got you in to the prompt).

Quoth Dmitry Kurochkin on Jan 26 at  5:12 am:
> The patch adds <tab> completion to "tag all" operation bound to "*"
> (`notmuch-search-operate-all' function).
> ---
>  emacs/notmuch.el |   48 ++++++++++++++++++++++++++++++++++++------------
>  1 files changed, 36 insertions(+), 12 deletions(-)
> 
> diff --git a/emacs/notmuch.el b/emacs/notmuch.el
> index e02966f..71b0221 100644
> --- a/emacs/notmuch.el
> +++ b/emacs/notmuch.el
> @@ -48,6 +48,7 @@
>  ;; required, but is available from http://notmuchmail.org).
>  
>  (eval-when-compile (require 'cl))
> +(require 'crm)
>  (require 'mm-view)
>  (require 'message)
>  
> @@ -75,12 +76,33 @@ For example:
>  (defvar notmuch-query-history nil
>    "Variable to store minibuffer history for notmuch queries")
>  
> -(defun notmuch-select-tag-with-completion (prompt &rest search-terms)
> +(defun notmuch-tag-completions (&optional search-terms prefixes)
>    (let ((tag-list
>  	 (with-output-to-string
>  	   (with-current-buffer standard-output
>  	     (apply 'call-process notmuch-command nil t nil "search-tags" search-terms)))))
> -    (completing-read prompt (split-string tag-list "\n+" t) nil nil nil)))
> +    (setq tag-list (split-string tag-list "\n+" t))
> +    (if (null prefixes)
> +	tag-list
> +      (apply #'append
> +	     (mapcar (lambda (tag)
> +		       (mapcar (lambda (prefix)
> +				 (concat prefix tag)) prefixes))
> +		     tag-list)))))
> +
> +(defun notmuch-select-tag-with-completion (prompt &optional search-terms prefixes)

This changes the API of notmuch-select-tag-with-completion in a
non-backwards-compatible way.  I'm pretty sure this breaks
notmuch-search-remove-tag and notmuch-show-remove-tag, but I haven't
tested it.

> +  (let ((tag-list (notmuch-tag-completions search-terms prefixes)))
> +    (completing-read prompt tag-list)))
> +
> +(defun notmuch-select-tags-with-completion (prompt &optional search-terms prefixes)
> +  (let ((tag-list (notmuch-tag-completions search-terms prefixes))
> +	(crm-separator " ")
> +	(crm-local-completion-map (copy-keymap crm-local-completion-map)))

Alternatively, you could create a child keymap.
crm-local-completion-map is small enough that it probably doesn't
matter, so whatever makes the code clearer.

> +    ;; By default, space is bound to "complete word" function.
> +    ;; Re-bind it to insert a space instead.  Note that <tab> still
> +    ;; does the completion.
> +    (define-key crm-local-completion-map " " 'self-insert-command)
> +    (completing-read-multiple prompt tag-list)))
>  
>  (defun notmuch-foreach-mime-part (function mm-handle)
>    (cond ((stringp (car mm-handle))
> @@ -860,16 +882,18 @@ will prompt for tags to be added or removed. Tags prefixed with
>  Each character of the tag name may consist of alphanumeric
>  characters as well as `_.+-'.
>  "

Technically this changes the API of notmuch-search-operate-all, though
the new one is better.  Perhaps it should test for (stringp action)
and be backwards-compatible?

The argument should probably be called "actions" now and it may even
make sense to make it a &rest argument (though then you can't make it
backwards-compatible).

> -  (interactive "sOperation (+add -drop): notmuch tag ")
> -  (let ((action-split (split-string action " +")))
> -    ;; Perform some validation
> -    (let ((words action-split))
> -      (when (null words) (error "No operation given"))
> -      (while words
> -	(unless (string-match-p "^[-+][-+_.[:word:]]+$" (car words))
> -	  (error "Action must be of the form `+thistag -that_tag'"))
> -	(setq words (cdr words))))
> -    (apply 'notmuch-tag notmuch-search-query-string action-split)))
> +  (interactive (list (notmuch-select-tags-with-completion
> +		      "Operation (+add -drop): notmuch tag " nil
> +		      '("+" "-"))))
> +  (setq action (delete "" action))
> +  ;; Perform some validation
> +  (let ((words action))
> +    (when (null words) (error "No operation given"))
> +    (while words
> +      (unless (string-match-p "^[-+][-+_.[:word:]]+$" (car words))
> +	(error "Action must be of the form `+thistag -that_tag'"))
> +      (setq words (cdr words))))

This should really be a mapc or a dolist, but maybe that's for another
patch.

> +  (apply 'notmuch-tag notmuch-search-query-string action))
>  
>  (defun notmuch-search-buffer-title (query)
>    "Returns the title for a buffer with notmuch search results."