7:30 a.m.
User: ben
Date: 05/02/03 08:30:23
Modified: xemacs/lisp ChangeLog regexp-opt.el
Log:
Update regexp-opt
regexp-opt.el: Update to latest version in package tree.
Revision Changes Path
1.626 +8 -0 XEmacs/xemacs/lisp/ChangeLog
(In the diff below, changes in quantity of whitespace are not shown.)
Index: ChangeLog
===================================================================
RCS file: /pack/xemacscvs/XEmacs/xemacs/lisp/ChangeLog,v
retrieving revision 1.625
retrieving revision 1.626
diff -u -b -r1.625 -r1.626
--- ChangeLog 2005/02/03 07:15:56 1.625
+++ ChangeLog 2005/02/03 07:30:21 1.626
＠＠ -1,5 +1,13 ＠＠
2005-02-03 Ben Wing <ben(a)xemacs.org>
+ * regexp-opt.el:
+ * regexp-opt.el (regexp-opt):
+ * regexp-opt.el (regexp-opt-not-groupie*-re): New.
+ * regexp-opt.el (regexp-opt-group):
+ Update to latest version in package tree.
+
+2005-02-03 Ben Wing <ben(a)xemacs.org>
+
* paragraphs.el:
* paragraphs.el (paragraphs): New.
* paragraphs.el (use-hard-newlines): Removed.
1.2 +58 -58 XEmacs/xemacs/lisp/regexp-opt.el
(In the diff below, changes in quantity of whitespace are not shown.)
Index: regexp-opt.el
===================================================================
RCS file: /pack/xemacscvs/XEmacs/xemacs/lisp/regexp-opt.el,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -b -r1.1 -r1.2
--- regexp-opt.el 2005/02/03 07:11:21 1.1
+++ regexp-opt.el 2005/02/03 07:30:22 1.2
＠＠ -6,9 +6,6 ＠＠
;; Maintainer: FSF
;; Keywords: strings, regexps, extensions
-;; Modified by Karl M. Hegbloom Sep. 1997 to support the new regexp syntax
-;; with shy groups. (benchmarks pending)
-
;; This file is part of XEmacs.
;; XEmacs is free software; you can redistribute it and/or modify
＠＠ -26,9 +23,15 ＠＠
;; Free Software Foundation, Inc., 59 Temple Place - Suite 330,
;; Boston, MA 02111-1307, USA.
+;;; Synched up with: GNU Emacs 21.3 + paren-in-char-set fix from CVS
+;;; revision 1.25. Some implementation differences in
+;;; regexp-opt-group and regexp-opt-charset but the APIs
+;;; are compatible and should return compatible (if not
+;;; exactly the same) regexps.
+
;;; Commentary:
-;; The "opt" in "regexp-opt" stands for
"optim\\(al\\|i\\(se\\|ze\\)\\)".
+;; The "opt" in "regexp-opt" stands for
"optim\\(?:al\\|i\\(?:se\\|ze\\)\\)".
;;
;; This package generates a regexp from a given list of strings (which matches
;; one of those strings) so that the regexp generated by:
＠＠ -47,19 +50,7 ＠＠
;; "save-current-buffer" "save-match-data"
;; "catch" "throw" "unwind-protect"
"condition-case")))
;; (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\\)\\)\\>"
-;;
-;;
-;; (let ((strings '("cond" "if" "when"
"unless" "while"
-;; "let" "let*" "progn" "prog1"
"prog2"
-;; "save-restriction" "save-excursion"
"save-window-excursion"
-;; "save-current-buffer" "save-match-data"
-;; "catch" "throw" "unwind-protect"
"condition-case")))
-;; (concat "(" (regexp-opt strings t 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\\)\\)\\>"
-;;
+;; =>
"(\\(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 takes approximately
;; two-thirds of the time taken using the equivalent `mapconcat' regexp.
＠＠ -88,30 +79,29 ＠＠
;; 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:
;;;###autoload
-(defun regexp-opt (strings &optional paren non-shy)
+(defun regexp-opt (strings &optional paren)
"Return a regexp to match a string in STRINGS.
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 match grouping construct. If optional
-NON-SHY is non nil, the inner groupings will use \"\\\\( \\\\)\" grouping,
-rather than the default \"\\\\(?: \\\\)\" 'shy', or
non-match-capturing groups.
+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
＠＠ -119,56 +109,66 ＠＠
(let* ((max-lisp-eval-depth (* 1024 1024))
(completion-ignore-case 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 paren nil non-shy)))
+ (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 &optional count-shy-groups-too)
+(defun regexp-opt-depth (regexp)
"Return the depth of REGEXP.
-This means the number of regexp grouping constructs (parenthesised
-expressions) in REGEXP, not counting the \"\\\\(?: \\\\)\"
-non-match-capturing groups unless COUNT-SHY-GROUPS-TOO is non-nil.
-See `regexp-opt'."
+This means the number of regexp grouping constructs (parenthesised expressions)
+in REGEXP."
(save-match-data
;; Hack to signal an error if REGEXP does not have balanced parentheses.
(string-match regexp "")
;; Count the number of open parentheses in REGEXP.
- (let ((max (1- (length regexp)))
- (count 0) start)
- (while (string-match "\\\\(" regexp start)
- (setq start (match-end 0))
- (when (or count-shy-groups-too
- (not (string= (substring regexp start (min (+ start 2) max))
"?:")))
- (setq count (1+ count))))
+ (let ((count 0) start)
+ (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.
(eval-when-compile
(require 'cl))
-
-(unless (fboundp 'make-bool-vector)
- (defalias 'make-bool-vector 'make-vector))
-(defun regexp-opt-group (strings &optional paren lax non-shy)
+(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.
-If NON-SHY non-nil, don't use \\(?: \\) shy groups, use match capturing ones.
Merges keywords to avoid backtracking in Emacs' regexp matcher.
-The basic idea is to find the shortest common prefix, remove it
+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 (cond
- ((and paren non-shy) "\\(")
- (paren "\\(?:")
- (t "")))
+ (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)))
＠＠ -187,7 +187,7 ＠＠
;; If there is an empty string, remove it and recurse on the rest.
((= (length (car strings)) 0)
(concat open-charset
- (regexp-opt-group (cdr strings) t t non-shy) "?"
+ (regexp-opt-group (cdr strings) t t) "?"
close-charset))
;;
;; If all are one-character strings, just return a character set.
＠＠ -208,7 +208,7 ＠＠
(let* ((length (length prefix))
(suffixes (mapcar (lambda (s) (substring s length)) strings)))
(concat open-group
- (regexp-quote prefix) (regexp-opt-group suffixes t t non-shy)
+ (regexp-quote prefix) (regexp-opt-group suffixes t t)
close-group)))
;;
;; If there are several one-character strings, remove them and recurse
＠＠ -217,7 +217,7 ＠＠
(let ((rest (let ((completion-regexp-list '("^..+$")))
(all-completions "" (mapcar 'list strings)))))
(concat open-group
- (regexp-opt-group rest nil nil non-shy) "\\|" (regexp-opt-charset
letters)
+ (regexp-opt-group rest) "\\|" (regexp-opt-charset letters)
close-group)))
;;
;; Otherwise, divide the list into those that start with a particular
＠＠ -227,7 +227,7 ＠＠
(half1 (all-completions char (mapcar 'list strings)))
(half2 (nthcdr (length half1) strings)))
(concat open-group
- (regexp-opt-group half1 nil nil non-shy) "\\|" (regexp-opt-group half2
nil nil non-shy)
+ (regexp-opt-group half1) "\\|" (regexp-opt-group half2)
close-group)))))))))
(defun regexp-opt-charset (chars)