X-Git-Url: https://code.delx.au/gnu-emacs/blobdiff_plain/5762abecd390e960b2a15bc58b5ed6a07af5955f..09c774f7137ab0efacf7858ba4ccd454a7c72bed:/lisp/emacs-lisp/regexp-opt.el

diff --git a/lisp/emacs-lisp/regexp-opt.el b/lisp/emacs-lisp/regexp-opt.el
index a6ed0734f1..f24789eb4a 100644
--- a/lisp/emacs-lisp/regexp-opt.el
+++ b/lisp/emacs-lisp/regexp-opt.el
@@ -1,9 +1,10 @@
-;;; 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.org>
-;; Keywords: strings, regexps
+;; Maintainer: FSF
+;; Keywords: strings, regexps, extensions
 
 ;; This file is part of GNU Emacs.
 
@@ -24,7 +25,7 @@
 
 ;;; 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 (which matches
 ;; one of those strings) so that the regexp generated by:
@@ -72,11 +73,15 @@
 ;; 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 and Dan Nicolaescu.
-;; 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.
+;; 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.
 
 ;;; Code:
 
@@ -88,16 +93,40 @@ 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:
 
- (let ((open-paren (if PAREN \"\\\\(\" \"\")) (close-paren (if PAREN \"\\\\)\" \"\")))
-   (concat open-paren (mapconcat 'regexp-quote STRINGS \"\\\\|\") close-paren))
+ (let ((open (if PAREN \"\\\\(\" \"\")) (close (if PAREN \"\\\\)\" \"\")))
+   (concat open (mapconcat 'regexp-quote STRINGS \"\\\\|\") close))
 
-but typically contains more 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)
@@ -109,8 +138,12 @@ in 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)))
 
 ;;; Workhorse functions.
@@ -118,32 +151,29 @@ in REGEXP."
 (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
-     ;; Protect against user-stupidity... could call error here
-     ((null strings)
-      nil)
+     ;;
+     ;; 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)
@@ -156,45 +186,68 @@ in REGEXP."
 	      (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 (first so the final regexp finds the longest match).
-	 ((> (length letters) 1)
-	  (let ((rest (let ((completion-regexp-list '("^..+$")))
-			(all-completions "" (mapcar 'list strings)))))
-	    (concat open-group
-		    (regexp-opt-group rest) "\\|" (regexp-opt-charset letters)
-		    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)
   ;;
@@ -203,13 +256,13 @@ in REGEXP."
   ;; 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.
-    (dolist (char (mapcar 'string-to-char chars))
+    (dolist (char chars)
       (case char
 	(?\]
 	 (setq bracket "]"))
@@ -221,14 +274,23 @@ in REGEXP."
 	 (aset charmap char t))))
     ;;
     ;; Make a character set from the map using ranges where applicable.
-    (dotimes (char charwidth)
-      (let ((start char))
-	(while (and (< char charwidth) (aref charmap char))
-	  (incf char))
-	(cond ((> char (+ start 3))
-	       (setq charset (format "%s%c-%c" charset start (1- char))))
-	      ((> char start)
-	       (setq charset (format "%s%c" charset (setq char start)))))))
+    (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 ""))
@@ -237,4 +299,5 @@ in REGEXP."
 
 (provide 'regexp-opt)
 
+;;; arch-tag: 6c5a66f4-29af-4fd6-8c3b-4b554d5b4370
 ;;; regexp-opt.el ends here