-;;; regexp-opt.el --- generate efficient regexps to match strings.
+;;; regexp-opt.el --- generate efficient regexps to match strings
;; Copyright (C) 1994,95,96,97,98,99,2000 Free Software Foundation, Inc.
(save-match-data
;; Recurse on the sorted list.
(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)
"Return the depth of 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.
(require 'cl))
(defun regexp-opt-group (strings &optional paren lax)
- "Return a regexp to match a string in 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.
+ ;; 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 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.
+ ;; 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."
+ ;; 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 (cond ((stringp paren) paren) (paren "\\(?:") (t "")))
(close-group (if paren "\\)" ""))
(open-charset (if lax "" open-group))
;;
;; We have a list of different length strings.
(t
- (let ((prefix (try-completion "" (mapcar 'list strings))))
+ (let ((prefix (try-completion "" strings)))
(if (> (length prefix) 0)
;; common prefix: take it and recurse on the suffixes.
(let* ((n (length prefix))
(let* ((sgnirts (mapcar (lambda (s)
(concat (nreverse (string-to-list s))))
strings))
- (xiffus (try-completion "" (mapcar 'list sgnirts))))
+ (xiffus (try-completion "" sgnirts)))
(if (> (length xiffus) 0)
;; common suffix: take it and recurse on the prefixes.
(let* ((n (- (length xiffus)))
- (prefixes (mapcar (lambda (s) (substring s 0 n)) strings)))
+ (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 (mapcar 'list strings)))
+ (half1 (all-completions char strings))
(half2 (nthcdr (length half1) strings)))
(concat open-group
(regexp-opt-group half1)