1 ;;; sregex.el --- symbolic regular expressions
3 ;; Copyright (C) 1997, 1998, 2000, 2001, 2002, 2003, 2004,
4 ;; 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
6 ;; Author: Bob Glickstein <bobg+sregex@zanshin.com>
7 ;; Maintainer: Bob Glickstein <bobg+sregex@zanshin.com>
8 ;; Keywords: extensions
10 ;; This file is part of GNU Emacs.
12 ;; GNU Emacs is free software; you can redistribute it and/or modify
13 ;; it under the terms of the GNU General Public License as published by
14 ;; the Free Software Foundation; either version 3, or (at your option)
17 ;; GNU Emacs is distributed in the hope that it will be useful,
18 ;; but WITHOUT ANY WARRANTY; without even the implied warranty of
19 ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 ;; GNU General Public License for more details.
22 ;; You should have received a copy of the GNU General Public License
23 ;; along with GNU Emacs; see the file COPYING. If not, write to the
24 ;; Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
25 ;; Boston, MA 02110-1301, USA.
29 ;; This package allows you to write regular expressions using a
30 ;; totally new, Lisp-like syntax.
32 ;; A "symbolic regular expression" (sregex for short) is a Lisp form
33 ;; that, when evaluated, produces the string form of the specified
34 ;; regular expression. Here's a simple example:
36 ;; (sregexq (or "Bob" "Robert")) => "Bob\\|Robert"
38 ;; As you can see, an sregex is specified by placing one or more
39 ;; special clauses in a call to `sregexq'. The clause in this case is
40 ;; the `or' of two strings (not to be confused with the Lisp function
41 ;; `or'). The list of allowable clauses appears below.
43 ;; With sregex, it is never necessary to "escape" magic characters
44 ;; that are meant to be taken literally; that happens automatically.
47 ;; (sregexq "M*A*S*H") => "M\\*A\\*S\\*H"
49 ;; It is also unnecessary to "group" parts of the expression together
50 ;; to overcome operator precedence; that also happens automatically.
53 ;; (sregexq (opt (or "Bob" "Robert"))) => "\\(?:Bob\\|Robert\\)?"
55 ;; It *is* possible to group parts of the expression in order to refer
56 ;; to them with numbered backreferences:
58 ;; (sregexq (group (or "Go" "Run"))
60 ;; (backref 1)) => "\\(Go\\|Run\\), Spot, \\1"
62 ;; `sregexq' is a macro. Each time it is used, it constructs a simple
63 ;; Lisp expression that then invokes a moderately complex engine to
64 ;; interpret the sregex and render the string form. Because of this,
65 ;; I don't recommend sprinkling calls to `sregexq' throughout your
66 ;; code, the way one normally does with string regexes (which are
67 ;; cheap to evaluate). Instead, it's wiser to precompute the regexes
68 ;; you need wherever possible instead of repeatedly constructing the
69 ;; same ones over and over. Example:
71 ;; (let ((field-regex (sregexq (opt "resent-")
72 ;; (or "to" "cc" "bcc"))))
76 ;; (re-search-forward field-regex ...)
79 ;; The arguments to `sregexq' are automatically quoted, but the
80 ;; flipside of this is that it is not straightforward to include
81 ;; computed (i.e., non-constant) values in `sregexq' expressions. So
82 ;; `sregex' is a function that is like `sregexq' but which does not
83 ;; automatically quote its values. Literal sregex clauses must be
84 ;; explicitly quoted like so:
86 ;; (sregex '(or "Bob" "Robert")) => "Bob\\|Robert"
88 ;; but computed clauses can be included easily, allowing for the reuse
91 ;; (let ((dotstar '(0+ any))
92 ;; (whitespace '(1+ (syntax ?-)))
93 ;; (digits '(1+ (char (?0 . ?9)))))
94 ;; (sregex 'bol dotstar ":" whitespace digits)) => "^.*:\\s-+[0-9]+"
96 ;; To use this package in a Lisp program, simply (require 'sregex).
98 ;; Here are the clauses allowed in an `sregex' or `sregexq'
102 ;; This stands for the literal string. If it contains
103 ;; metacharacters, they will be escaped in the resulting regex
104 ;; (using `regexp-quote').
106 ;; - the symbol `any'
107 ;; This stands for ".", a regex matching any character except
110 ;; - the symbol `bol'
111 ;; Stands for "^", matching the empty string at the beginning of a line
113 ;; - the symbol `eol'
114 ;; Stands for "$", matching the empty string at the end of a line
116 ;; - (group CLAUSE ...)
117 ;; Groups the given CLAUSEs using "\\(" and "\\)".
119 ;; - (sequence CLAUSE ...)
121 ;; Groups the given CLAUSEs; may or may not use "\\(?:" and "\\)".
122 ;; Clauses grouped by `sequence' do not count for purposes of
123 ;; numbering backreferences. Use `sequence' in situations like
126 ;; (sregexq (or "dog" "cat"
127 ;; (sequence (opt "sea ") "monkey")))
128 ;; => "dog\\|cat\\|\\(?:sea \\)?monkey"
130 ;; where a single `or' alternate needs to contain multiple
134 ;; Matches the same string previously matched by the Nth "group" in
135 ;; the same sregex. N is a positive integer.
138 ;; Matches any one of the CLAUSEs by separating them with "\\|".
141 ;; Concatenates the given CLAUSEs and matches zero or more
142 ;; occurrences by appending "*".
145 ;; Concatenates the given CLAUSEs and matches one or more
146 ;; occurrences by appending "+".
148 ;; - (opt CLAUSE ...)
149 ;; Concatenates the given CLAUSEs and matches zero or one occurrence
152 ;; - (repeat MIN MAX CLAUSE ...)
153 ;; Concatenates the given CLAUSEs and constructs a regex matching at
154 ;; least MIN occurrences and at most MAX occurrences. MIN must be a
155 ;; non-negative integer. MAX must be a non-negative integer greater
156 ;; than or equal to MIN; or MAX can be nil to mean "infinity."
158 ;; - (char CHAR-CLAUSE ...)
159 ;; Creates a "character class" matching one character from the given
160 ;; set. See below for how to construct a CHAR-CLAUSE.
162 ;; - (not-char CHAR-CLAUSE ...)
163 ;; Creates a "character class" matching any one character not in the
164 ;; given set. See below for how to construct a CHAR-CLAUSE.
166 ;; - the symbol `bot'
167 ;; Stands for "\\`", matching the empty string at the beginning of
168 ;; text (beginning of a string or of a buffer).
170 ;; - the symbol `eot'
171 ;; Stands for "\\'", matching the empty string at the end of text.
173 ;; - the symbol `point'
174 ;; Stands for "\\=", matching the empty string at point.
176 ;; - the symbol `word-boundary'
177 ;; Stands for "\\b", matching the empty string at the beginning or
180 ;; - the symbol `not-word-boundary'
181 ;; Stands for "\\B", matching the empty string not at the beginning
184 ;; - the symbol `bow'
185 ;; Stands for "\\<", matching the empty string at the beginning of a
188 ;; - the symbol `eow'
189 ;; Stands for "\\>", matching the empty string at the end of a word.
191 ;; - the symbol `wordchar'
192 ;; Stands for the regex "\\w", matching a word-constituent character
193 ;; (as determined by the current syntax table)
195 ;; - the symbol `not-wordchar'
196 ;; Stands for the regex "\\W", matching a non-word-constituent
200 ;; Stands for the regex "\\sCODE", where CODE is a syntax table code
201 ;; (a single character). Matches any character with the requested
204 ;; - (not-syntax CODE)
205 ;; Stands for the regex "\\SCODE", where CODE is a syntax table code
206 ;; (a single character). Matches any character without the
210 ;; This is a "trapdoor" for including ordinary regular expression
211 ;; strings in the result. Some regular expressions are clearer when
212 ;; written the old way: "[a-z]" vs. (sregexq (char (?a . ?z))), for
213 ;; instance. However, see the note under "Bugs," below.
215 ;; Each CHAR-CLAUSE that is passed to (char ...) and (not-char ...)
216 ;; has one of the following forms:
219 ;; Adds that character to the set.
222 ;; Adds all the characters in the string to the set.
224 ;; - A pair (MIN . MAX)
225 ;; Where MIN and MAX are characters, adds the range of characters
226 ;; from MIN through MAX to the set.
230 ;; An earlier version of this package could optionally translate the
231 ;; symbolic regex into other languages' syntaxes, e.g. Perl. For
232 ;; instance, with Perl syntax selected, (sregexq (or "ab" "cd")) would
233 ;; yield "ab|cd" instead of "ab\\|cd". It might be useful to restore
236 ;; - handle multibyte chars in sregex--char-aux
237 ;; - add support for character classes ([:blank:], ...)
238 ;; - add support for non-greedy operators *? and +?
239 ;; - bug: (sregexq (opt (opt ?a))) returns "a??" which is a non-greedy "a?"
245 (eval-when-compile (require 'cl
))
247 ;; Compatibility code for when we didn't have shy-groups
248 (defvar sregex--current-sregex nil
)
249 (defun sregex-info () nil
)
250 (defmacro sregex-save-match-data
(&rest forms
) (cons 'save-match-data forms
))
251 (defun sregex-replace-match (r &optional f l str subexp x
)
252 (replace-match r f l str subexp
))
253 (defun sregex-match-string (c &optional i x
) (match-string c i
))
254 (defun sregex-match-string-no-properties (count &optional in-string sregex
)
255 (match-string-no-properties count in-string
))
256 (defun sregex-match-beginning (count &optional sregex
) (match-beginning count
))
257 (defun sregex-match-end (count &optional sregex
) (match-end count
))
258 (defun sregex-match-data (&optional sregex
) (match-data))
259 (defun sregex-backref-num (n &optional sregex
) n
)
262 (defun sregex (&rest exps
)
263 "Symbolic regular expression interpreter.
264 This is exactly like `sregexq' (q.v.) except that it evaluates all its
265 arguments, so literal sregex clauses must be quoted. For example:
267 (sregex '(or \"Bob\" \"Robert\")) => \"Bob\\\\|Robert\"
269 An argument-evaluating sregex interpreter lets you reuse sregex
272 (let ((dotstar '(0+ any))
273 (whitespace '(1+ (syntax ?-)))
274 (digits '(1+ (char (?0 . ?9)))))
275 (sregex 'bol dotstar \":\" whitespace digits)) => \"^.*:\\\\s-+[0-9]+\""
276 (sregex--sequence exps nil
))
278 (defmacro sregexq
(&rest exps
)
279 "Symbolic regular expression interpreter.
280 This macro allows you to specify a regular expression (regexp) in
281 symbolic form, and converts it into the string form required by Emacs's
282 regex functions such as `re-search-forward' and `looking-at'. Here is
285 (sregexq (or \"Bob\" \"Robert\")) => \"Bob\\\\|Robert\"
287 As you can see, an sregex is specified by placing one or more special
288 clauses in a call to `sregexq'. The clause in this case is the `or'
289 of two strings (not to be confused with the Lisp function `or'). The
290 list of allowable clauses appears below.
292 With `sregex', it is never necessary to \"escape\" magic characters
293 that are meant to be taken literally; that happens automatically.
296 (sregexq \"M*A*S*H\") => \"M\\\\*A\\\\*S\\\\*H\"
298 It is also unnecessary to \"group\" parts of the expression together
299 to overcome operator precedence; that also happens automatically.
302 (sregexq (opt (or \"Bob\" \"Robert\"))) => \"\\\\(Bob\\\\|Robert\\\\)?\"
304 It *is* possible to group parts of the expression in order to refer
305 to them with numbered backreferences:
307 (sregexq (group (or \"Go\" \"Run\"))
309 (backref 1)) => \"\\\\(Go\\\\|Run\\\\), Spot, \\\\1\"
311 If `sregexq' needs to introduce its own grouping parentheses, it will
312 automatically renumber your backreferences:
314 (sregexq (opt \"resent-\")
315 (group (or \"to\" \"cc\" \"bcc\"))
317 (backref 1)) => \"\\\\(resent-\\\\)?\\\\(to\\\\|cc\\\\|bcc\\\\): \\\\2\"
319 `sregexq' is a macro. Each time it is used, it constructs a simple
320 Lisp expression that then invokes a moderately complex engine to
321 interpret the sregex and render the string form. Because of this, I
322 don't recommend sprinkling calls to `sregexq' throughout your code,
323 the way one normally does with string regexes (which are cheap to
324 evaluate). Instead, it's wiser to precompute the regexes you need
325 wherever possible instead of repeatedly constructing the same ones
326 over and over. Example:
328 (let ((field-regex (sregexq (opt \"resent-\")
329 (or \"to\" \"cc\" \"bcc\"))))
333 (re-search-forward field-regex ...)
336 The arguments to `sregexq' are automatically quoted, but the
337 flipside of this is that it is not straightforward to include
338 computed (i.e., non-constant) values in `sregexq' expressions. So
339 `sregex' is a function that is like `sregexq' but which does not
340 automatically quote its values. Literal sregex clauses must be
341 explicitly quoted like so:
343 (sregex '(or \"Bob\" \"Robert\")) => \"Bob\\\\|Robert\"
345 but computed clauses can be included easily, allowing for the reuse
348 (let ((dotstar '(0+ any))
349 (whitespace '(1+ (syntax ?-)))
350 (digits '(1+ (char (?0 . ?9)))))
351 (sregex 'bol dotstar \":\" whitespace digits)) => \"^.*:\\\\s-+[0-9]+\"
353 Here are the clauses allowed in an `sregex' or `sregexq' expression:
356 This stands for the literal string. If it contains
357 metacharacters, they will be escaped in the resulting regex
358 (using `regexp-quote').
361 This stands for \".\", a regex matching any character except
365 Stands for \"^\", matching the empty string at the beginning of a line
368 Stands for \"$\", matching the empty string at the end of a line
371 Groups the given CLAUSEs using \"\\\\(\" and \"\\\\)\".
373 - (sequence CLAUSE ...)
375 Groups the given CLAUSEs; may or may not use \"\\\\(\" and \"\\\\)\".
376 Clauses grouped by `sequence' do not count for purposes of
377 numbering backreferences. Use `sequence' in situations like
380 (sregexq (or \"dog\" \"cat\"
381 (sequence (opt \"sea \") \"monkey\")))
382 => \"dog\\\\|cat\\\\|\\\\(?:sea \\\\)?monkey\"
384 where a single `or' alternate needs to contain multiple
388 Matches the same string previously matched by the Nth \"group\" in
389 the same sregex. N is a positive integer.
392 Matches any one of the CLAUSEs by separating them with \"\\\\|\".
395 Concatenates the given CLAUSEs and matches zero or more
396 occurrences by appending \"*\".
399 Concatenates the given CLAUSEs and matches one or more
400 occurrences by appending \"+\".
403 Concatenates the given CLAUSEs and matches zero or one occurrence
406 - (repeat MIN MAX CLAUSE ...)
407 Concatenates the given CLAUSEs and constructs a regex matching at
408 least MIN occurrences and at most MAX occurrences. MIN must be a
409 non-negative integer. MAX must be a non-negative integer greater
410 than or equal to MIN; or MAX can be nil to mean \"infinity.\"
412 - (char CHAR-CLAUSE ...)
413 Creates a \"character class\" matching one character from the given
414 set. See below for how to construct a CHAR-CLAUSE.
416 - (not-char CHAR-CLAUSE ...)
417 Creates a \"character class\" matching any one character not in the
418 given set. See below for how to construct a CHAR-CLAUSE.
421 Stands for \"\\\\`\", matching the empty string at the beginning of
422 text (beginning of a string or of a buffer).
425 Stands for \"\\\\'\", matching the empty string at the end of text.
428 Stands for \"\\\\=\\=\", matching the empty string at point.
430 - the symbol `word-boundary'
431 Stands for \"\\\\b\", matching the empty string at the beginning or
434 - the symbol `not-word-boundary'
435 Stands for \"\\\\B\", matching the empty string not at the beginning
439 Stands for \"\\\\=\\<\", matching the empty string at the beginning of a
443 Stands for \"\\\\=\\>\", matching the empty string at the end of a word.
445 - the symbol `wordchar'
446 Stands for the regex \"\\\\w\", matching a word-constituent character
447 (as determined by the current syntax table)
449 - the symbol `not-wordchar'
450 Stands for the regex \"\\\\W\", matching a non-word-constituent
454 Stands for the regex \"\\\\sCODE\", where CODE is a syntax table code
455 (a single character). Matches any character with the requested
459 Stands for the regex \"\\\\SCODE\", where CODE is a syntax table code
460 (a single character). Matches any character without the
464 This is a \"trapdoor\" for including ordinary regular expression
465 strings in the result. Some regular expressions are clearer when
466 written the old way: \"[a-z]\" vs. (sregexq (char (?a . ?z))), for
469 Each CHAR-CLAUSE that is passed to (char ...) and (not-char ...)
470 has one of the following forms:
473 Adds that character to the set.
476 Adds all the characters in the string to the set.
479 Where MIN and MAX are characters, adds the range of characters
480 from MIN through MAX to the set."
481 `(apply 'sregex
',exps
))
483 (defun sregex--engine (exp combine
)
489 (concat "\\(?:" (regexp-quote exp
) "\\)")
501 (word-boundary "\\b")
502 (not-word-boundary "\\B")
506 (funcall (intern (concat "sregex--"
507 (symbol-name (car exp
))))
510 (t (error "Invalid expression: %s" exp
))))
512 (defun sregex--sequence (exps combine
)
513 (if (= (length exps
) 1) (sregex--engine (car exps
) combine
)
515 (lambda (e) (sregex--engine e
'concat
))
517 (if (eq combine
'suffix
)
518 (concat "\\(?:" re
"\\)")
521 (defun sregex--or (exps combine
)
522 (if (= (length exps
) 1) (sregex--engine (car exps
) combine
)
524 (lambda (e) (sregex--engine e
'or
))
526 (if (not (eq combine
'or
))
527 (concat "\\(?:" re
"\\)")
530 (defun sregex--group (exps combine
) (concat "\\(" (sregex--sequence exps nil
) "\\)"))
532 (defun sregex--backref (exps combine
) (concat "\\" (int-to-string (car exps
))))
533 (defun sregex--opt (exps combine
) (concat (sregex--sequence exps
'suffix
) "?"))
534 (defun sregex--0+ (exps combine
) (concat (sregex--sequence exps
'suffix
) "*"))
535 (defun sregex--1+ (exps combine
) (concat (sregex--sequence exps
'suffix
) "+"))
537 (defun sregex--char (exps combine
) (sregex--char-aux nil exps
))
538 (defun sregex--not-char (exps combine
) (sregex--char-aux t exps
))
540 (defun sregex--syntax (exps combine
) (format "\\s%c" (car exps
)))
541 (defun sregex--not-syntax (exps combine
) (format "\\S%c" (car exps
)))
543 (defun sregex--regex (exps combine
)
544 (if combine
(concat "\\(?:" (car exps
) "\\)") (car exps
)))
546 (defun sregex--repeat (exps combine
)
547 (let* ((min (or (pop exps
) 0))
548 (minstr (number-to-string min
))
550 (concat (sregex--sequence exps
'suffix
)
551 (concat "\\{" minstr
","
552 (when max
(number-to-string max
)) "\\}"))))
554 (defun sregex--char-range (start end
)
555 (let ((startc (char-to-string start
))
556 (endc (char-to-string end
)))
558 ((> end
(+ start
2)) (concat startc
"-" endc
))
559 ((> end
(+ start
1)) (concat startc
(char-to-string (1+ start
)) endc
))
560 ((> end start
) (concat startc endc
))
563 (defun sregex--char-aux (complement args
)
564 ;; regex-opt does the same, we should join effort.
565 (let ((chars (make-bool-vector 256 nil
))) ; Yeah, right!
567 (cond ((integerp arg
) (aset chars arg t
))
568 ((stringp arg
) (mapc (lambda (c) (aset chars c t
)) arg
))
570 (let ((start (car arg
))
573 (let ((tmp start
)) (setq start end
) (setq end tmp
)))
578 (setq i
(1+ i
))))))))
579 ;; now chars is a map of the characters in the class
580 (let ((caret (aref chars ?^
))
581 (dash (aref chars ?-
))
582 (class (if (aref chars ?\
]) "]" "")))
591 (unless start
(setq start i
))
595 (setq class
(concat class
(sregex--char-range start end
)))
598 (setq class
(concat class
(sregex--char-range start end
)))))
600 (if (> (length class
) 0)
601 (setq class
(concat class
(if caret
"^") (if dash
"-")))
602 (setq class
(concat class
(if dash
"-") (if caret
"^"))))
603 (if (and (not complement
) (= (length class
) 1))
605 (concat "[" (if complement
"^") class
"]")))))
609 ;; arch-tag: 460c1f5a-eb6e-42ec-a451-ffac78bdf492
610 ;;; sregex.el ends here