annotate lisp/emacs-lisp/regexp-opt.el @ 83004:7900111db01c

Converted display hooks to be display-local. Plus many bugfixes. lib-src/emacsclient.c (window_change_signal): Renamed to pass_signal_to_emacs. (init_signal): Pass SIGINT and SIGQUIT to the emacs process. lisp/faces.el (face-valid-attribute-values): Use the window-system function, not the variable. (read-face-attribute, face-spec-set-match-display, frame-set-background-mode) (face-set-after-frame-default): Ditto. lisp/frame.el (make-frame-on-tty): Added interactive declaration (suggested by Robert J. Chassell). Use tty-create-frame-with-faces, not make-terminal-frame. src/termhooks.h (struct display_method): Renamed to display for brevity. (struct display): Added all display hook variables as members of this structure. Added next_display, reference_count, type and display_info components. (FRAME_MUST_WRITE_SPACES, FRAME_FAST_CLEAR_END_OF_LINE, FRAME_LINE_INS_DEL_OK) (FRAME_CHAR_INS_DEL_OK, FRAME_SCROLL_REGION_OK, FRAME_SCROLL_REGION_COST) (FRAME_MEMORY_BELOW_FRAME, FRAME_RIF): Updated for struct display. (FRAME_DISPLAY): New macro. (create_display, delete_display): New prototypes. src/frame.h (struct frame): Added `display' member, removed display_method. (FRAME_LIVE_P): Look at f->display, not f->output_data. src/termchar.h (struct tty_display_info): Removed display_method component. (FRAME_TTY): Use the display structure, not output_data. src/term.c (display_list): New variable. (cursor_to_hook, raw_cursor_to_hook, clear_to_end_hook, clear_frame_hook) (clear_end_of_line_hook, ins_del_lines_hook, delete_glyphs_hook) (ring_bell_hook, reset_terminal_modes_hook, set_terminal_modes_hook) (update_begin_hook, update_end_hook, set_terminal_window_hook) (insert_glyphs_hook, write_glyphs_hook, delete_glyphs_hoo, read_socket_hook) (frame_up_to_date_hook, mouse_position_hook, frame_rehighlight_hook) (frame_raise_lower_hook, set_vertical_scroll_bar_hook, condemn_scroll_bars_hook) (redeem_scroll_bar_hook, judge_scroll_bars_hook): Moved to struct display. (tty_display_method_template): Removed. (syms_of_term): Don't initialize tty_display_method_template. (ring_bell, set_terminal_modes, reset_terminal_modes, update_begin) (update_end, set_terminal_window, cursor_to, raw_cursor_to, clear_to_end) (clear_frame, clear_end_of_line, write_glyphs, insert_glyphs) (delete_glyphs, ins_del_lines): Access display hooks through the frame pointer. (Ftty_display_color_p): Use the frame given as a parameter, or else return nil. (Ftty_display_color_cells): Ditto. (get_named_tty): Renamed to get_named_tty_display, changed return type to struct display. (term_dummy_init): Renamed to initial_term_init. Create and return an initial display. (term_init): Initialize a new struct display and return a pointer to it instead of tty_display_info. Removed frame initialization kludge. (Fdelete_tty): Updated for struct display. (delete_tty): The parameter type is now struct display, not tty_display_info. Delete the display, too. (create_tty_output): New function for creating tty_output structures. (delete_tty_output): New function for deleting tty_output structures. (create_display): New function for creating and registering display structures. (delete_display): New function for deleting and unregistering display structures. src/dispextern.h: Updated prototypes. src/dispnew.c: Include frame.h before termhooks.h. (init_display): Updated term_init call to new signature. src/emacs.c: Include frame.h (for termhooks.h). src/keymap.c: Ditto. src/lread.c: Ditto. src/xsmfns.c: Ditto. src/process.c: Include frame.h before termhooks.h. src/frame.c (Fwindow_system): New function. (syms_of_frame): Initialize it. (make_terminal_frame): Open the terminal device before creating the new frame. Disable scrollbars here, term_init cannot do that anymore. (Fdelete_frame): Use the new delete_frame_hook, don't do display-specific frame deletion here. Ditto for delete_display_hook. (Fmouse_position, Fmouse_pixel_position, Fraise_frame, Flower_frame) (Fredirect_frame_focus): Access display hooks through the frame pointer. src/keyboard.c: Include frame.h before termhooks.h. (start_polling, input_polling_used, stop_polling, gobble_input): Ignore read_socket_hook. (kbd_buffer_get_event, Fset_input_mode): Access display hooks through the frame pointer. (read_avail_input): Loop through all display devices for and call all read_socket_hook functions. Check ttys even if read_socket_hook returned an error. src/sysdep.c (discard_tty_input): Ignore read_socket_hook. (stuff_char): Don't do anything if the current frame is not on a termcap display. (request_sigio, unrequest_sigio): Ignore read_socket_hook. (init_sys_modes): Always call narrow_foreground_group. Set up terminal modes and sigio even under X. src/xdisp.c (message2_nolog, message3_nolog, redisplay_internal) (set_vertical_scroll_bar, redisplay_window): Access display hooks through the frame pointer. (echo_area_display): Don't be afraid of termcap frames during an X+tty combo session. src/xfaces.c: Include termhooks.h. (Ftty_supports_face_attributes_p): Use the given frame, not selected_frame. src/xfns.c (x_set_scroll_bar_foreground, x_set_scroll_bar_background): Access display hooks through the frame pointer. (Fx_create_frame, x_create_tip_frame): Initialize the frame's display structure. src/xmenu.c: Include termhooks.h after frame.h. src/xselect.c (x_own_selection, some_frame_on_display, x_get_foreign_selection) (Fx_disown_selection_internal, Fx_get_cut_buffer_internal) (Fx_store_cut_buffer_internal, Fx_rotate_cut_buffers_internal): Don't do anything if the selected frame is not an X frame. src/xterm.c (x_display_method): Removed. (x_create_frame_display, x_delete_frame_display): New functions for handling struct display objects. (x_term_init): Set up a new struct display object, too. (x_delete_display): Delete the struct display corresponding to the X display. (x_initialize): Moved hook initialization to x_create_frame_display. src/xterm.h (x_display_method): Removed. (struct x_display_info): Added frame_display component. git-archimport-id: [e-mail]--2004/emacs--multi-tty--0--patch-44

;;; regexp-opt.el --- generate efficient regexps to match strings

;; Copyright (C) 1994,95,96,97,98,99,2000 Free Software Foundation, Inc.

;; Author: Simon Marshall <[e-mail]>
;; Maintainer: FSF
;; Keywords: strings, regexps, extensions

;; This file is part of GNU Emacs.

;; GNU Emacs is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation; either version 2, or (at your option)
;; any later version.

;; GNU Emacs is distributed in the hope that it will be useful,
;; but WITHOUT ANY WARRANTY; without even the implied warranty of
;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
;; GNU General Public License for more details.

;; You should have received a copy of the GNU General Public License
;; along with GNU Emacs; see the file COPYING.  If not, write to the
;; Free Software Foundation, Inc., 59 Temple Place - Suite 330,
;; Boston, MA 02111-1307, USA.

;;; Commentary:

;; 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:
;;
;; (regexp-opt strings)
;;
;; is equivalent to, but more efficient than, the regexp generated by:
;;
;; (mapconcat 'regexp-quote strings "\\|")
;;
;; For example:
;;
;; (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) "\\>"))
;;  => "(\\(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.

;; Since this package was written to produce efficient regexps, not regexps
;; efficiently, it is probably not a good idea to in-line too many calls in
;; your code, unless you use the following trick with `eval-when-compile':
;;
;; (defvar definition-regexp
;;   (eval-when-compile
;;     (concat "^("
;;             (regexp-opt '("defun" "defsubst" "defmacro" "defalias"
;;                           "defvar" "defconst") t)
;;             "\\>")))
;;
;; The `byte-compile' code will be as if you had defined the variable thus:
;;
;; (defvar definition-regexp
;;   "^(\\(def\\(alias\\|const\\|macro\\|subst\\|un\\|var\\)\\)\\>")
;;
;; Note that if you use this trick for all instances of `regexp-opt' and
;; `regexp-opt-depth' in your code, regexp-opt.el would only have to be loaded
;; at compile time.  But note also that using this trick means that should
;; regexp-opt.el be changed, perhaps to fix a bug or to add a feature to
;; improve the efficiency of `regexp-opt' regexps, you would have to recompile
;; 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, 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)
  "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 grouping construct.
The returned regexp is typically more efficient than the equivalent regexp:

 (let ((open (if PAREN \"\\\\(\" \"\")) (close (if PAREN \"\\\\)\" \"\")))
   (concat open (mapconcat 'regexp-quote STRINGS \"\\\\|\") close))

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))
	   (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.
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 ((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))

(defun regexp-opt-group (strings &optional paren lax)
  ;; 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.

  ;; 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))
	 (close-charset (if lax "" close-group)))
    (cond
     ;;
     ;; 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)
	  (concat open-charset (regexp-quote (car strings)) close-charset)
	(concat open-group (regexp-quote (car strings)) close-group)))
     ;;
     ;; 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) "?"
	      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 "" 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)
  ;;
  ;; Return a regexp to match a character in CHARS.
  ;;
  ;; 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* ((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 chars)
      (case char
	(?\]
	 (setq bracket "]"))
	(?^
	 (setq caret "^"))
	(?-
	 (setq dash "-"))
	(otherwise
	 (aset charmap char t))))
    ;;
    ;; Make a character set from the map using ranges where applicable.
    (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 ""))
	(concat "[" dash caret "]")
      (concat "[" bracket charset caret dash "]"))))

(provide 'regexp-opt)

;;; arch-tag: 6c5a66f4-29af-4fd6-8c3b-4b554d5b4370
;;; regexp-opt.el ends here