cgit.sxemacs.org Git - sxemacs/blob - lisp/regexp-opt.el

   1 ;;; regexp-opt.el --- generate efficient regexps to match strings
   2
   3 ;; Copyright (C) 1994,95,96,97,98,99,2000 Free Software Foundation, Inc.
   4
   5 ;; Author: Simon Marshall <simon@gnu.org>
   6 ;; Maintainer: FSF
   7 ;; Keywords: strings, regexps, extensions
   8
   9 ;; This file is part of SXEmacs.
  10
  11 ;; SXEmacs is free software: you can redistribute it and/or modify
  12 ;; it under the terms of the GNU General Public License as published by
  13 ;; the Free Software Foundation, either version 3 of the License, or
  14 ;; (at your option) any later version.
  15
  16 ;; SXEmacs is distributed in the hope that it will be useful,
  17 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 ;; GNU General Public License for more details.
  20
  21 ;; You should have received a copy of the GNU General Public License
  22 ;; along with this program.  If not, see <http://www.gnu.org/licenses/>.
  23
  24 ;;; Synched up with: GNU Emacs 21.3 + paren-in-char-set fix from CVS
  25 ;;;                  revision 1.25.  Some implementation differences in
  26 ;;;                  regexp-opt-group and regexp-opt-charset but the APIs
  27 ;;;                  are compatible and should return compatible (if not
  28 ;;;                  exactly the same) regexps.
  29
  30 ;;; Commentary:
  31
  32 ;; The "opt" in "regexp-opt" stands for "optim\\(?:al\\|i\\(?:se\\|ze\\)\\)".
  33 ;;
  34 ;; This package generates a regexp from a given list of strings (which matches
  35 ;; one of those strings) so that the regexp generated by:
  36 ;;
  37 ;; (regexp-opt strings)
  38 ;;
  39 ;; is equivalent to, but more efficient than, the regexp generated by:
  40 ;;
  41 ;; (mapconcat 'regexp-quote strings "\\|")
  42 ;;
  43 ;; For example:
  44 ;;
  45 ;; (let ((strings '("cond" "if" "when" "unless" "while"
  46 ;;                  "let" "let*" "progn" "prog1" "prog2"
  47 ;;                  "save-restriction" "save-excursion" "save-window-excursion"
  48 ;;                  "save-current-buffer" "save-match-data"
  49 ;;                  "catch" "throw" "unwind-protect" "condition-case")))
  50 ;;   (concat "(" (regexp-opt strings t) "\\>"))
  51 ;;  => "(\\(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\\)\\)\\>"
  52 ;;
  53 ;; Searching using the above example `regexp-opt' regexp takes approximately
  54 ;; two-thirds of the time taken using the equivalent `mapconcat' regexp.
  55
  56 ;; Since this package was written to produce efficient regexps, not regexps
  57 ;; efficiently, it is probably not a good idea to in-line too many calls in
  58 ;; your code, unless you use the following trick with `eval-when-compile':
  59 ;;
  60 ;; (defvar definition-regexp
  61 ;;   (eval-when-compile
  62 ;;     (concat "^("
  63 ;;             (regexp-opt '("defun" "defsubst" "defmacro" "defalias"
  64 ;;                           "defvar" "defconst") t)
  65 ;;             "\\>")))
  66 ;;
  67 ;; The `byte-compile' code will be as if you had defined the variable thus:
  68 ;;
  69 ;; (defvar definition-regexp
  70 ;;   "^(\\(def\\(alias\\|const\\|macro\\|subst\\|un\\|var\\)\\)\\>")
  71 ;;
  72 ;; Note that if you use this trick for all instances of `regexp-opt' and
  73 ;; `regexp-opt-depth' in your code, regexp-opt.el would only have to be loaded
  74 ;; at compile time.  But note also that using this trick means that should
  75 ;; regexp-opt.el be changed, perhaps to fix a bug or to add a feature to
  76 ;; improve the efficiency of `regexp-opt' regexps, you would have to recompile
  77 ;; your code for such changes to have effect in your code.
  78
  79 ;; Originally written for font-lock.el, from an idea from Stig's hl319.el, with
  80 ;; thanks for ideas also to Michael Ernst, Bob Glickstein, Dan Nicolaescu and
  81 ;;