-;;; regexp-opt.el --- generate efficient regexps to match strings.
+;;; regexp-opt.el --- generate efficient regexps to match strings
-;; Copyright (C) 1994, 1995, 1996, 1997 Free Software Foundation, Inc.
+;; Copyright (C) 1994,95,96,97,98,99,2000 Free Software Foundation, Inc.
-;; Author: Simon Marshall <simon@gnu.ai.mit.edu>
-;; Keywords: strings, regexps
-;; Version: 1.04.01
+;; Author: Simon Marshall <simon@gnu.org>
+;; Maintainer: FSF
+;; Keywords: strings, regexps, extensions
;; This file is part of GNU Emacs.
;;; Commentary:
-;; The "opt" in "regexp-opt" stands for "optim\\(al\\|i\\(se\\|ze\\)\\)".
+;; The "opt" in "regexp-opt" stands for "optim\\(al\\|i[sz]e\\)".
;;
-;; This package generates a regexp from a given list of strings (that matches
-;; one of those strings) that is equivalent to but more efficient than:
+;; This package generates a regexp from a given list of strings (which matches
+;; one of those strings) so that the regexp generated by:
;;
-;; (mapconcat 'identity (mapcar 'regexp-quote strings) "\\|")
+;; (regexp-opt strings)
+;;
+;; is equivalent to, but more efficient than, the regexp generated by:
+;;
+;; (mapconcat 'regexp-quote strings "\\|")
;;
;; For example:
;;
;; (concat "(" (regexp-opt strings t) "\\>"))
;; => "(\\(c\\(atch\\|ond\\(ition-case\\)?\\)\\|if\\|let\\*?\\|prog[12n]\\|save-\\(current-buffer\\|excursion\\|match-data\\|restriction\\|window-excursion\\)\\|throw\\|un\\(less\\|wind-protect\\)\\|wh\\(en\\|ile\\)\\)\\>"
;;
-;; Searching using the above example `regexp-opt' regexp is significantly
-;; faster than searching using the equivalent `mapconcat' regexp, taking
-;; approximately two-thirds of the time.
-;;
+;; Searching using the above example `regexp-opt' regexp takes approximately
+;; two-thirds of the time taken using the equivalent `mapconcat' regexp.
+
;; Since this package was written to produce efficient regexps, not regexps
;; efficiently, it is probably not a good idea to in-line too many calls in
;; your code, unless you use the following trick with `eval-when-compile':
;; (defvar definition-regexp
;; "^(\\(def\\(alias\\|const\\|macro\\|subst\\|un\\|var\\)\\)\\>")
;;
-;; Originally written for font-lock.el, from an idea from Stig's hl319.el.
-;; Please don't tell me that it doesn't produce optimal regexps; I know that
-;; already. For example, the above explanation for the meaning of "opt" would
-;; be more efficient as "optim\\(al\\|i[sz]e\\)", but this requires complex
-;; forward looking. But (ideas or) code to improve things (are) is welcome.
+;; Note that if you use this trick for all instances of `regexp-opt' and
+;; `regexp-opt-depth' in your code, regexp-opt.el would only have to be loaded
+;; at compile time. But note also that using this trick means that should
+;; regexp-opt.el be changed, perhaps to fix a bug or to add a feature to
+;; improve the efficiency of `regexp-opt' regexps, you would have to recompile
+;; your code for such changes to have effect in your code.
+
+;; Originally written for font-lock.el, from an idea from Stig's hl319.el, with
+;; thanks for ideas also to Michael Ernst, Bob Glickstein, Dan Nicolaescu and
+;; Stefan Monnier.
+;; No doubt `regexp-opt' doesn't always produce optimal regexps, so code, ideas
+;; or any other information to improve things are welcome.
+;;
+;; One possible improvement would be to compile '("aa" "ab" "ba" "bb")
+;; into "[ab][ab]" rather than "a[ab]\\|b[ab]". I'm not sure it's worth
+;; it but if someone knows how to do it without going through too many
+;; contortions, I'm all ears.
\f
;;; Code:
;;;###autoload
(defun regexp-opt (strings &optional paren)
"Return a regexp to match a string in STRINGS.
-If optional PAREN non-nil, ensure that the returned regexp is enclosed by at
-least one regexp grouping construct.
-Each string in STRINGS should be unique and should not contain any regexps.
+Each string should be unique in STRINGS and should not contain any regexps,
+quoted or not. If optional PAREN is non-nil, ensure that the returned regexp
+is enclosed by at least one regexp grouping construct.
The returned regexp is typically more efficient than the equivalent regexp:
- (mapconcat 'identity (mapcar 'regexp-quote STRINGS) \"\\\\|\")
+ (let ((open (if PAREN \"\\\\(\" \"\")) (close (if PAREN \"\\\\)\" \"\")))
+ (concat open (mapconcat 'regexp-quote STRINGS \"\\\\|\") close))
-but typically contains regexp grouping constructs. Use `regexp-opt-depth' to
-count them."
+If PAREN is `words', then the resulting regexp is additionally surrounded
+by \\=\\< and \\>."
(save-match-data
;; Recurse on the sorted list.
- (let ((max-lisp-eval-depth (* 1024 1024))
- (completion-ignore-case nil))
- (regexp-opt-group (sort (copy-sequence strings) 'string-lessp) paren))))
+ (let* ((max-lisp-eval-depth (* 1024 1024))
+ (max-specpdl-size (* 1024 1024))
+ (completion-ignore-case nil)
+ (completion-regexp-list nil)
+ (words (eq paren 'words))
+ (open (cond ((stringp paren) paren) (paren "\\(")))
+ (sorted-strings (sort (copy-sequence strings) 'string-lessp))
+ (re (regexp-opt-group sorted-strings open)))
+ (if words (concat "\\<" re "\\>") re))))
+
+(defconst regexp-opt-not-groupie*-re
+ (let* ((harmless-ch "[^\\\\[]")
+ (esc-pair-not-lp "\\\\[^(]")
+ (class-harmless-ch "[^][]")
+ (class-lb-harmless "[^]:]")
+ (class-lb-colon-maybe-charclass ":\\([a-z]+:]\\)?")
+ (class-lb (concat "\\[\\(" class-lb-harmless
+ "\\|" class-lb-colon-maybe-charclass "\\)"))
+ (class
+ (concat "\\[^?]?"
+ "\\(" class-harmless-ch
+ "\\|" class-lb "\\)*"
+ "\\[?]")) ; special handling for bare [ at end of re
+ (shy-lp "\\\\(\\?:"))
+ (concat "\\(" harmless-ch "\\|" esc-pair-not-lp
+ "\\|" class "\\|" shy-lp "\\)*"))
+ "Matches any part of a regular expression EXCEPT for non-shy \"\\\\(\"s")
;;;###autoload
(defun regexp-opt-depth (regexp)
(string-match regexp "")
;; Count the number of open parentheses in REGEXP.
(let ((count 0) start)
- (while (string-match "\\\\(" regexp start)
- (setq count (1+ count) start (match-end 0)))
+ (while
+ (progn
+ (string-match regexp-opt-not-groupie*-re regexp start)
+ (setq start ( + (match-end 0) 2)) ; +2 for "\\(" after match-end.
+ (<= start (length regexp)))
+ (setq count (1+ count)))
count)))
\f
;;; Workhorse functions.
(eval-when-compile
(require 'cl))
-(unless (fboundp 'make-bool-vector)
- (defalias 'make-bool-vector 'make-vector))
-
(defun regexp-opt-group (strings &optional paren lax)
- ;;
- ;; Return a regexp to match a string in STRINGS.
+ ;; Return a regexp to match a string in the sorted list STRINGS.
;; If PAREN non-nil, output regexp parentheses around returned regexp.
;; If LAX non-nil, don't output parentheses if it doesn't require them.
;; Merges keywords to avoid backtracking in Emacs' regexp matcher.
- ;;
- ;; The basic idea is to find the shortest common prefix, remove it and
- ;; recurse. If there is no prefix, we divide the list into two so that (at
- ;; least) one half will have at least a one-character common prefix.
- ;;
+
+ ;; The basic idea is to find the shortest common prefix or suffix, remove it
+ ;; and recurse. If there is no prefix, we divide the list into two so that
+ ;; \(at least) one half will have at least a one-character common prefix.
+
;; Also we delay the addition of grouping parenthesis as long as possible
;; until we're sure we need them, and try to remove one-character sequences
;; so we can use character sets rather than grouping parenthesis.
- ;;
- (let* ((open-group (if paren "\\(" ""))
+ (let* ((open-group (cond ((stringp paren) paren) (paren "\\(?:") (t "")))
(close-group (if paren "\\)" ""))
(open-charset (if lax "" open-group))
(close-charset (if lax "" close-group)))
(cond
;;
+ ;; If there are no strings, just return the empty string.
+ ((= (length strings) 0)
+ "")
+ ;;
;; If there is only one string, just return it.
((= (length strings) 1)
(if (= (length (car strings)) 1)
(regexp-opt-group (cdr strings) t t) "?"
close-charset))
;;
- ;; If all are one-character strings, just return a character set.
- ((= (length strings) (apply '+ (mapcar 'length strings)))
- (concat open-charset
- (regexp-opt-charset strings)
- close-charset))
+ ;; If there are several one-char strings, use charsets
+ ((and (= (length (car strings)) 1)
+ (let ((strs (cdr strings)))
+ (while (and strs (/= (length (car strs)) 1))
+ (pop strs))
+ strs))
+ (let (letters rest)
+ ;; Collect one-char strings
+ (dolist (s strings)
+ (if (= (length s) 1) (push (string-to-char s) letters) (push s rest)))
+
+ (if rest
+ ;; several one-char strings: take them and recurse
+ ;; on the rest (first so as to match the longest).
+ (concat open-group
+ (regexp-opt-group (nreverse rest))
+ "\\|" (regexp-opt-charset letters)
+ close-group)
+ ;; all are one-char strings: just return a character set.
+ (concat open-charset
+ (regexp-opt-charset letters)
+ close-charset))))
;;
;; We have a list of different length strings.
(t
- (let ((prefix (try-completion "" (mapcar 'list strings)))
- (letters (let ((completion-regexp-list '("^.$")))
- (all-completions "" (mapcar 'list strings)))))
- (cond
- ;;
- ;; If there is a common prefix, remove it and recurse on the suffixes.
- ((> (length prefix) 0)
- (let* ((length (length prefix))
- (suffixes (mapcar (lambda (s) (substring s length)) strings)))
- (concat open-group
- (regexp-quote prefix) (regexp-opt-group suffixes t t)
- close-group)))
- ;;
- ;; If there are several one-character strings, remove them and recurse
- ;; on the rest.
- ((> (length letters) 1)
- (let ((rest (let ((completion-regexp-list '("^..+$")))
- (all-completions "" (mapcar 'list strings)))))
- (concat open-group
- (regexp-opt-charset letters) "\\|" (regexp-opt-group rest)
- close-group)))
- ;;
- ;; Otherwise, divide the list into those that start with a particular
- ;; letter and those that do not, and recurse on them.
- (t
- (let* ((char (substring (car strings) 0 1))
- (half1 (all-completions char (mapcar 'list strings)))
- (half2 (nthcdr (length half1) strings)))
- (concat open-group
- (regexp-opt-group half1) "\\|" (regexp-opt-group half2)
- close-group)))))))))
+ (let ((prefix (try-completion "" strings)))
+ (if (> (length prefix) 0)
+ ;; common prefix: take it and recurse on the suffixes.
+ (let* ((n (length prefix))
+ (suffixes (mapcar (lambda (s) (substring s n)) strings)))
+ (concat open-group
+ (regexp-quote prefix)
+ (regexp-opt-group suffixes t t)
+ close-group))
+
+ (let* ((sgnirts (mapcar (lambda (s)
+ (concat (nreverse (string-to-list s))))
+ strings))
+ (xiffus (try-completion "" sgnirts)))
+ (if (> (length xiffus) 0)
+ ;; common suffix: take it and recurse on the prefixes.
+ (let* ((n (- (length xiffus)))
+ (prefixes
+ ;; Sorting is necessary in cases such as ("ad" "d").
+ (sort (mapcar (lambda (s) (substring s 0 n)) strings)
+ 'string-lessp)))
+ (concat open-group
+ (regexp-opt-group prefixes t t)
+ (regexp-quote
+ (concat (nreverse (string-to-list xiffus))))
+ close-group))
+
+ ;; Otherwise, divide the list into those that start with a
+ ;; particular letter and those that do not, and recurse on them.
+ (let* ((char (char-to-string (string-to-char (car strings))))
+ (half1 (all-completions char strings))
+ (half2 (nthcdr (length half1) strings)))
+ (concat open-group
+ (regexp-opt-group half1)
+ "\\|" (regexp-opt-group half2)
+ close-group))))))))))
+
(defun regexp-opt-charset (chars)
;;
;; The basic idea is to find character ranges. Also we take care in the
;; position of character set meta characters in the character set regexp.
;;
- (let* ((charwidth 256) ; Yeah, right.
- (charmap (make-bool-vector charwidth nil))
+ (let* ((charmap (make-char-table 'case-table))
+ (start -1) (end -2)
(charset "")
(bracket "") (dash "") (caret ""))
;;
;; Make a character map but extract character set meta characters.
- (let (char)
- (while chars
- (setq char (string-to-char (pop chars)))
- (cond ((eq char ?\])
- (setq bracket "]"))
- ((eq char ?^)
- (setq caret "^"))
- ((eq char ?-)
- (setq dash "-"))
- (t
- (aset charmap char t)))))
+ (dolist (char chars)
+ (case char
+ (?\]
+ (setq bracket "]"))
+ (?^
+ (setq caret "^"))
+ (?-
+ (setq dash "-"))
+ (otherwise
+ (aset charmap char t))))
;;
;; Make a character set from the map using ranges where applicable.
- (let ((elt 0) start)
- (while (< elt charwidth)
- (when (aref charmap elt)
- (setq start (1+ elt))
- (while (and (< start charwidth) (aref charmap start))
- (incf start))
- (if (< (- start elt) 4)
- (setq charset (format "%s%c" charset elt))
- (setq charset (format "%s%c-%c" charset elt (1- start))
- elt start)))
- (incf elt)))
+ (map-char-table
+ (lambda (c v)
+ (when v
+ (if (= (1- c) end) (setq end c)
+ (if (> end (+ start 2))
+ (setq charset (format "%s%c-%c" charset start end))
+ (while (>= end start)
+ (setq charset (format "%s%c" charset start))
+ (incf start)))
+ (setq start c end c))))
+ charmap)
+ (when (>= end start)
+ (if (> end (+ start 2))
+ (setq charset (format "%s%c-%c" charset start end))
+ (while (>= end start)
+ (setq charset (format "%s%c" charset start))
+ (incf start))))
;;
;; Make sure a caret is not first and a dash is first or last.
(if (and (string-equal charset "") (string-equal bracket ""))