Now on revision 107696. ------------------------------------------------------------ revno: 107696 committer: Glenn Morris branch nick: trunk timestamp: Wed 2012-03-28 12:30:12 -0700 message: Doc and lispref updates related to searching * doc/lispref/searching.texi (Regexp Functions, Regexp Search): (Simple Match Data, Saving Match Data, Standard Regexps): Copyedits. (Regexp Functions): Mention regexp-opt is not guaranteed. Mention regexp-opt-charset. (Regexp Search): Recommend against looking-back. (Search and Replace): Use Texinfo recommended quote convention. Add more query-replace-map items. List multi-query-replace-map items. * lisp/replace.el (query-replace-map): Doc fix. * admin/FOR-RELEASE: Related markup. diff: === modified file 'admin/FOR-RELEASE' --- admin/FOR-RELEASE 2012-03-18 15:02:12 +0000 +++ admin/FOR-RELEASE 2012-03-28 19:30:12 +0000 @@ -220,7 +220,7 @@ package.texi rgm positions.texi cyd processes.texi -searching.texi +searching.texi rgm sequences.texi cyd streams.texi cyd strings.texi cyd === modified file 'doc/lispref/ChangeLog' --- doc/lispref/ChangeLog 2012-03-28 07:57:42 +0000 +++ doc/lispref/ChangeLog 2012-03-28 19:30:12 +0000 @@ -1,9 +1,15 @@ 2012-03-28 Glenn Morris * searching.texi (Regular Expressions, Regexp Special): - (Regexp Backslash, Regexp Example): Copyedits. + (Regexp Backslash, Regexp Example, Regexp Functions, Regexp Search): + (Simple Match Data, Saving Match Data, Standard Regexps): Copyedits. (Regexp Special): Mention collation. Clarify char classes with an example. + (Regexp Functions): Mention regexp-opt is not guaranteed. + Mention regexp-opt-charset. + (Regexp Search): Recommend against looking-back. + (Search and Replace): Use Texinfo recommended quote convention. + Add more query-replace-map items. List multi-query-replace-map items. 2012-03-27 Martin Rudalics === modified file 'doc/lispref/searching.texi' --- doc/lispref/searching.texi 2012-03-28 08:02:53 +0000 +++ doc/lispref/searching.texi 2012-03-28 19:30:12 +0000 @@ -902,7 +902,7 @@ @var{string}. Using this regular expression in @code{looking-at} will succeed only if the next characters in the buffer are @var{string}; using it in a search function will succeed if the text being searched -contains @var{string}. +contains @var{string}. @xref{Regexp Search}. This allows you to request an exact string match or search when calling a function that wants a regular expression. @@ -931,7 +931,11 @@ This function returns an efficient regular expression that will match any of the strings in the list @var{strings}. This is useful when you need to make matching or searching as fast as possible---for example, -for Font Lock mode. +for Font Lock mode@footnote{Note that @code{regexp-opt} does not +guarantee that its result is absolutely the most efficient form +possible. A hand-tuned regular expression can sometimes be slightly +more efficient, but is almost never worth the effort.}. +@c See eg http://debbugs.gnu.org/2816 If the optional argument @var{paren} is non-@code{nil}, then the returned regular expression is always enclosed by at least one @@ -947,7 +951,7 @@ (but not as efficient): @example -(defun regexp-opt (strings paren) +(defun regexp-opt (strings &optional paren) (let ((open-paren (if paren "\\(" "")) (close-paren (if paren "\\)" ""))) (concat open-paren @@ -962,6 +966,19 @@ shy groups (@pxref{Regexp Backslash}). @end defun +@c Supposedly an internal regexp-opt function, but table.el uses it at least. +@defun regexp-opt-charset chars +This function returns a regular expression matching a character in the +list of characters @var{chars}. + +@example +(regexp-opt-charset '(?a ?b ?c ?d ?e)) + @result{} "[a-e]" +@end example +@end defun + +@c Internal functions: regexp-opt-group + @node Regexp Search @section Regular Expression Searching @cindex regular expression searching @@ -1104,8 +1121,7 @@ succeed only starting with the first character following point. The result is @code{t} if so, @code{nil} otherwise. -This function does not move point, but it updates the match data, which -you can access using @code{match-beginning} and @code{match-end}. +This function does not move point, but it does update the match data. @xref{Match Data}. If you need to test for a match without modifying the match data, use @code{looking-at-p}, described below. @@ -1126,8 +1142,8 @@ @end defun @defun looking-back regexp &optional limit greedy -This function returns @code{t} if @var{regexp} matches text before -point, ending at point, and @code{nil} otherwise. +This function returns @code{t} if @var{regexp} matches the text +immediately before point (i.e., ending at point), and @code{nil} otherwise. Because regular expression matching works only going forward, this is implemented by searching backwards from point for a match that ends at @@ -1155,6 +1171,11 @@ @result{} nil @end group @end example + +@c http://debbugs.gnu.org/5689 +As a general recommendation, try to avoid using @code{looking-back} +wherever possible, since it is slow. For this reason, there are no +plans to add a @code{looking-back-p} function. @end defun @defun looking-at-p regexp @@ -1178,6 +1199,7 @@ @node POSIX Regexps @section POSIX Regular Expression Searching +@cindex backtracking and POSIX regular expressions The usual regular expression functions do backtracking when necessary to handle the @samp{\|} and repetition constructs, but they continue this only until they find @emph{some} match. Then they succeed and @@ -1350,12 +1372,16 @@ query the match data immediately after searching, before calling any other function that might perform another search. Alternatively, you may save and restore the match data (@pxref{Saving Match Data}) around -the call to functions that could perform another search. +the call to functions that could perform another search. Or use the +functions that explicitly do not modify the match data; +e.g. @code{string-match-p}. +@c This is an old comment and presumably there is no prospect of this +@c changing now. But still the advice stands. A search which fails may or may not alter the match data. In the -past, a failing search did not do this, but we may change it in the -future. So don't try to rely on the value of the match data after -a failing search. +current implementation, it does not, but we may change it in the +future. Don't try to rely on the value of the match data after a +failing search. @defun match-string count &optional in-string This function returns, as a string, the text matched in the last search @@ -1369,7 +1395,7 @@ you should omit @var{in-string} or pass @code{nil} for it; but you should make sure that the current buffer when you call @code{match-string} is the one in which you did the searching or -matching. +matching. Failure to follow this advice will lead to incorrect results. The value is @code{nil} if @var{count} is out of range, or for a subexpression inside a @samp{\|} alternative that wasn't used or a @@ -1382,7 +1408,7 @@ @end defun @defun match-beginning count -This function returns the position of the start of text matched by the +This function returns the position of the start of the text matched by the last regular expression searched for, or a subexpression of it. If @var{count} is zero, then the value is the position of the start of @@ -1475,7 +1501,7 @@ @defun match-data &optional integers reuse reseat This function returns a list of positions (markers or integers) that -record all the information on what text the last search matched. +record all the information on the text that the last search matched. Element zero is the position of the beginning of the match for the whole expression; element one is the position of the end of the match for the expression. The next two elements are the positions of the @@ -1544,6 +1570,7 @@ If @var{reseat} is non-@code{nil}, all markers on the @var{match-list} list are reseated to point to nowhere. +@c TODO Make it properly obsolete. @findex store-match-data @code{store-match-data} is a semi-obsolete alias for @code{set-match-data}. @end defun @@ -1551,7 +1578,7 @@ @node Saving Match Data @subsection Saving and Restoring the Match Data - When you call a function that may do a search, you may need to save + When you call a function that may search, you may need to save and restore the match data around that call, if you want to preserve the match data from an earlier search for later use. Here is an example that shows the problem that arises if you fail to save the match data: @@ -1560,8 +1587,7 @@ @group (re-search-forward "The \\(cat \\)") @result{} 48 -(foo) ; @r{Perhaps @code{foo} does} - ; @r{more searching.} +(foo) ; @r{@code{foo} does more searching.} (match-end 0) @result{} 61 ; @r{Unexpected result---not 48!} @end group @@ -1654,7 +1680,7 @@ @code{replace-regexp-in-string} calls @var{rep} for each match, passing the text of the match as its sole argument. It collects the value @var{rep} returns and passes that to @code{replace-match} as the -replacement string. The match-data at this point are the result +replacement string. The match data at this point are the result of matching @var{regexp} against a substring of @var{string}. @end defun @@ -1692,7 +1718,7 @@ If @var{from-string} contains upper-case letters, then @code{perform-replace} binds @code{case-fold-search} to @code{nil}, and -it uses the @code{replacements} without altering the case of them. +it uses the @var{replacements} without altering their case. Normally, the keymap @code{query-replace-map} defines the possible user responses for queries. The argument @var{map}, if @@ -1722,7 +1748,7 @@ Prefix keys are not supported; each key binding must be for a single-event key sequence. This is because the functions don't use @code{read-key-sequence} to get the input; instead, they read a single -event and look it up ``by hand.'' +event and look it up ``by hand''. @end itemize @end defvar @@ -1732,26 +1758,30 @@ @table @code @item act -Do take the action being considered---in other words, ``yes.'' +Do take the action being considered---in other words, ``yes''. @item skip -Do not take action for this question---in other words, ``no.'' +Do not take action for this question---in other words, ``no''. @item exit -Answer this question ``no,'' and give up on the entire series of -questions, assuming that the answers will be ``no.'' +Answer this question ``no'', and give up on the entire series of +questions, assuming that the answers will be ``no''. + +@item exit-prefix +Like @code{exit}, but add the key that was pressed to +@code{unread-comment-events}. @item act-and-exit -Answer this question ``yes,'' and give up on the entire series of -questions, assuming that subsequent answers will be ``no.'' +Answer this question ``yes'', and give up on the entire series of +questions, assuming that subsequent answers will be ``no''. @item act-and-show -Answer this question ``yes,'' but show the results---don't advance yet +Answer this question ``yes'', but show the results---don't advance yet to the next question. @item automatic Answer this question and all subsequent questions in the series with -``yes,'' without further user interaction. +``yes'', without further user interaction. @item backup Move back to the previous place that a question was asked about. @@ -1760,6 +1790,9 @@ Enter a recursive edit to deal with this question---instead of any other action that would normally be taken. +@item edit-replacement +Edit the replacement for this question in the minibuffer. + @item delete-and-edit Delete the text being considered, then enter a recursive edit to replace it. @@ -1778,7 +1811,18 @@ @defvar multi-query-replace-map This variable holds a keymap that extends @code{query-replace-map} by providing additional keybindings that are useful in multi-buffer -replacements. +replacements. The additional ``bindings'' are: + +@table @code +@item automatic-all +Answer this question and all subsequent questions in the series with +``yes'', without further user interaction, for all remaining buffers. + +@item exit-current +Answer this question ``no'', and give up on the entire series of +questions for the current buffer. Continue to the next buffer in the +sequence. +@end table @end defvar @defvar replace-search-function @@ -1841,8 +1885,8 @@ the end of a sentence, including the whitespace following the sentence. (All paragraph boundaries also end sentences, regardless.) -If the value is @code{nil}, the default, then the function -@code{sentence-end} has to construct the regexp. That is why you +If the value is @code{nil}, as it is by default, then the function +@code{sentence-end} constructs the regexp. That is why you should always call the function @code{sentence-end} to obtain the regexp to be used to recognize the end of a sentence. @end defopt @@ -1852,6 +1896,6 @@ if non-@code{nil}. Otherwise it returns a default value based on the values of the variables @code{sentence-end-double-space} (@pxref{Definition of sentence-end-double-space}), -@code{sentence-end-without-period} and +@code{sentence-end-without-period}, and @code{sentence-end-without-space}. @end defun === modified file 'lisp/ChangeLog' --- lisp/ChangeLog 2012-03-28 10:12:02 +0000 +++ lisp/ChangeLog 2012-03-28 19:30:12 +0000 @@ -1,3 +1,7 @@ +2012-03-28 Glenn Morris + + * replace.el (query-replace-map): Doc fix. + 2012-03-28 Andreas Schwab * vc/vc-git.el (vc-git-state): Don't try to match all of the diff === modified file 'lisp/replace.el' --- lisp/replace.el 2012-03-11 10:27:53 +0000 +++ lisp/replace.el 2012-03-28 19:30:12 +0000 @@ -1594,8 +1594,8 @@ "Keymap that defines the responses to questions in `query-replace'. The \"bindings\" in this map are not commands; they are answers. The valid answers include `act', `skip', `act-and-show', -`exit', `act-and-exit', `edit', `delete-and-edit', `recenter', -`automatic', `backup', `exit-prefix', and `help'.") +`exit', `act-and-exit', `edit', `edit-replacement', `delete-and-edit', +`recenter', `automatic', `backup', `exit-prefix', `quit', and `help'.") (defvar multi-query-replace-map (let ((map (make-sparse-keymap))) ------------------------------------------------------------ revno: 107695 committer: Stefan Monnier branch nick: trunk timestamp: Wed 2012-03-28 11:54:54 -0400 message: * src/keyboard.c (safe_run_hooks_error): Don't unquote strings. diff: === modified file 'src/ChangeLog' --- src/ChangeLog 2012-03-27 06:46:42 +0000 +++ src/ChangeLog 2012-03-28 15:54:54 +0000 @@ -1,3 +1,7 @@ +2012-03-28 Stefan Monnier + + * keyboard.c (safe_run_hooks_error): Don't unquote strings. + 2012-03-27 Glenn Morris * search.c (Fword_search_backward_lax, Fword_search_forward_lax): @@ -16,8 +20,7 @@ 2012-03-25 Fabrice Popineau - * w32heap.c (_heap_init, _heap_term): Remove dead MSVC-specific - code. + * w32heap.c (_heap_init, _heap_term): Remove dead MSVC-specific code. 2012-03-25 Kenichi Handa === modified file 'src/keyboard.c' --- src/keyboard.c 2012-03-26 04:06:31 +0000 +++ src/keyboard.c 2012-03-28 15:54:54 +0000 @@ -1881,7 +1881,7 @@ = CONSP (Vinhibit_quit) ? XCAR (Vinhibit_quit) : Vinhibit_quit; Lisp_Object fun = CONSP (Vinhibit_quit) ? XCDR (Vinhibit_quit) : Qnil; Lisp_Object args[4]; - args[0] = build_string ("Error in %s (%s): %s"); + args[0] = build_string ("Error in %s (%s): %S"); args[1] = hook; args[2] = fun; args[3] = error_data; ------------------------------------------------------------ revno: 107694 committer: Andreas Schwab branch nick: emacs timestamp: Wed 2012-03-28 12:12:02 +0200 message: Fixes: debbugs:11109 * vc/vc-git.el (vc-git-state): Don't try to match all of the diff contents. diff: === modified file 'lisp/ChangeLog' --- lisp/ChangeLog 2012-03-27 20:43:09 +0000 +++ lisp/ChangeLog 2012-03-28 10:12:02 +0000 @@ -1,3 +1,8 @@ +2012-03-28 Andreas Schwab + + * vc/vc-git.el (vc-git-state): Don't try to match all of the diff + contents. (Bug#11109) + 2012-03-27 Stefan Monnier * emacs-lisp/avl-tree.el (avl-tree--enter-balance): Fix paren typo === modified file 'lisp/vc/vc-git.el' --- lisp/vc/vc-git.el 2012-03-26 03:08:15 +0000 +++ lisp/vc/vc-git.el 2012-03-28 10:12:02 +0000 @@ -220,11 +220,10 @@ (let ((diff (vc-git--run-command-string file "diff-index" "-p" "--raw" "-z" "HEAD" "--"))) (if (and diff - (string-match ":[0-7]\\{6\\} [0-7]\\{6\\} [0-9a-f]\\{40\\} [0-9a-f]\\{40\\} \\([ADMUT]\\)\0[^\0]+\0\\(\\(?:.\\|\n\\)*\\)\\'" + (string-match ":[0-7]\\{6\\} [0-7]\\{6\\} [0-9a-f]\\{40\\} [0-9a-f]\\{40\\} \\([ADMUT]\\)\0[^\0]+\0\\(.\\)?" diff)) - (let ((diff-letter (match-string 1 diff)) - (diff-contents (match-string 2 diff))) - (if (not (string-match "\n." diff-contents)) + (let ((diff-letter (match-string 1 diff))) + (if (not (match-beginning 2)) ;; Empty diff: file contents is the same as the HEAD ;; revision, but timestamps are different (eg, file ;; was "touch"ed). Update timestamp in index: ------------------------------------------------------------ revno: 107693 committer: Glenn Morris branch nick: trunk timestamp: Wed 2012-03-28 01:02:53 -0700 message: Comment diff: === modified file 'doc/lispref/searching.texi' --- doc/lispref/searching.texi 2012-03-28 07:57:42 +0000 +++ doc/lispref/searching.texi 2012-03-28 08:02:53 +0000 @@ -392,6 +392,10 @@ matches upper-case letters. Note that a range like @samp{[a-z]} is not affected by the locale's collation sequence, it always represents a sequence in @acronym{ASCII} order. +@c This wasn't obvious to me, since eg the grep manual "Character +@c Classes and Bracket Expressions" specifically notes the opposite +@c behavior. But by experiment Emacs seems unaffected by LC_COLLATE +@c in this regard. Note also that the usual regexp special characters are not special inside a character alternative. A completely different set of characters is ------------------------------------------------------------ revno: 107692 committer: Glenn Morris branch nick: trunk timestamp: Wed 2012-03-28 00:57:42 -0700 message: lispref/searching.tex small edits * doc/lispref/searching.texi (Regular Expressions, Regexp Special): (Regexp Backslash, Regexp Example): Copyedits. (Regexp Special): Mention collation. Clarify char classes with an example. diff: === modified file 'doc/lispref/ChangeLog' --- doc/lispref/ChangeLog 2012-03-27 09:22:01 +0000 +++ doc/lispref/ChangeLog 2012-03-28 07:57:42 +0000 @@ -1,3 +1,10 @@ +2012-03-28 Glenn Morris + + * searching.texi (Regular Expressions, Regexp Special): + (Regexp Backslash, Regexp Example): Copyedits. + (Regexp Special): Mention collation. + Clarify char classes with an example. + 2012-03-27 Martin Rudalics * windows.texi (Window History): Describe new option === modified file 'doc/lispref/searching.texi' --- doc/lispref/searching.texi 2012-03-27 06:46:42 +0000 +++ doc/lispref/searching.texi 2012-03-28 07:57:42 +0000 @@ -241,7 +241,7 @@ @findex re-builder @cindex regular expressions, developing - For convenient interactive development of regular expressions, you + For interactive development of regular expressions, you can use the @kbd{M-x re-builder} command. It provides a convenient interface for creating regular expressions, by giving immediate visual feedback in a separate buffer. As you edit the regexp, all its @@ -318,6 +318,7 @@ expression. Thus, @samp{fo*} has a repeating @samp{o}, not a repeating @samp{fo}. It matches @samp{f}, @samp{fo}, @samp{foo}, and so on. +@cindex backtracking and regular expressions The matcher processes a @samp{*} construct by matching, immediately, as many repetitions as can be found. Then it continues with the rest of the pattern. If that fails, backtracking occurs, discarding some of the @@ -387,7 +388,12 @@ @samp{[a-z$%.]}, which matches any lower case @acronym{ASCII} letter or @samp{$}, @samp{%} or period. -Note that the usual regexp special characters are not special inside a +If @code{case-fold-search} is non-@code{nil}, @samp{[a-z]} also +matches upper-case letters. Note that a range like @samp{[a-z]} is +not affected by the locale's collation sequence, it always represents +a sequence in @acronym{ASCII} order. + +Note also that the usual regexp special characters are not special inside a character alternative. A completely different set of characters is special inside character alternatives: @samp{]}, @samp{-} and @samp{^}. @@ -395,23 +401,27 @@ first character. For example, @samp{[]a]} matches @samp{]} or @samp{a}. To include a @samp{-}, write @samp{-} as the first or last character of the character alternative, or put it after a range. Thus, @samp{[]-]} -matches both @samp{]} and @samp{-}. +matches both @samp{]} and @samp{-}. (As explained below, you cannot +use @samp{\]} to include a @samp{]} inside a character alternative, +since @samp{\} is not special there.) To include @samp{^} in a character alternative, put it anywhere but at the beginning. +@c What if it starts with a multibyte and ends with a unibyte? +@c That doesn't seem to match anything...? If a range starts with a unibyte character @var{c} and ends with a multibyte character @var{c2}, the range is divided into two parts: one -is @samp{@var{c}..?\377}, the other is @samp{@var{c1}..@var{c2}}, where -@var{c1} is the first character of the charset to which @var{c2} -belongs. +spans the unibyte characters @samp{@var{c}..?\377}, the other the +multibyte characters @samp{@var{c1}..@var{c2}}, where @var{c1} is the +first character of the charset to which @var{c2} belongs. A character alternative can also specify named character classes -(@pxref{Char Classes}). This is a POSIX feature whose syntax is -@samp{[:@var{class}:]}. Using a character class is equivalent to -mentioning each of the characters in that class; but the latter is not -feasible in practice, since some classes include thousands of -different characters. +(@pxref{Char Classes}). This is a POSIX feature. For example, +@samp{[[:ascii:]]} matches any @acronym{ASCII} character. +Using a character class is equivalent to mentioning each of the +characters in that class; but the latter is not feasible in practice, +since some classes include thousands of different characters. @item @samp{[^ @dots{} ]} @cindex @samp{^} in regexp @@ -812,7 +822,7 @@ @kindex invalid-regexp Not every string is a valid regular expression. For example, a string -that ends inside a character alternative without terminating @samp{]} +that ends inside a character alternative without a terminating @samp{]} is invalid, and so is a string that ends with a single @samp{\}. If an invalid regular expression is passed to any of the search functions, an @code{invalid-regexp} error is signaled. @@ -827,20 +837,14 @@ regexp constructed by the function @code{sentence-end}. @xref{Standard Regexps}.) - First, we show the regexp as a string in Lisp syntax to distinguish -spaces from tab characters. The string constant begins and ends with a + Below, we show first the regexp as a string in Lisp syntax (to +distinguish spaces from tab characters), and then the result of +evaluating it. The string constant begins and ends with a double-quote. @samp{\"} stands for a double-quote as part of the string, @samp{\\} for a backslash as part of the string, @samp{\t} for a tab and @samp{\n} for a newline. @example -"[.?!][]\"')@}]*\\($\\| $\\|\t\\|@ @ \\)[ \t\n]*" -@end example - -@noindent -In contrast, if you evaluate this string, you will see the following: - -@example @group "[.?!][]\"')@}]*\\($\\| $\\|\t\\|@ @ \\)[ \t\n]*" @result{} "[.?!][]\"')@}]*\\($\\| $\\| \\|@ @ \\)[ @@ -849,7 +853,7 @@ @end example @noindent -In this output, tab and newline appear as themselves. +In the output, tab and newline appear as themselves. This regular expression contains four parts in succession and can be deciphered as follows: ------------------------------------------------------------ revno: 107691 committer: Paul Eggert branch nick: trunk timestamp: Wed 2012-03-28 00:24:26 -0700 message: Spelling fixes. diff: === modified file 'lisp/forms.el' --- lisp/forms.el 2012-01-19 07:21:25 +0000 +++ lisp/forms.el 2012-03-28 07:24:26 +0000 @@ -581,7 +581,7 @@ (error (concat "Forms control file error: " "`forms-modified-record-filter' is not a function"))) - ;; The filters acces the contents of the forms using `forms-fields'. + ;; The filters access the contents of the forms using `forms-fields'. (make-local-variable 'forms-fields) ;; Dynamic text support. === modified file 'lisp/progmodes/ada-mode.el' --- lisp/progmodes/ada-mode.el 2012-01-19 07:21:25 +0000 +++ lisp/progmodes/ada-mode.el 2012-03-28 07:24:26 +0000 @@ -4728,7 +4728,7 @@ ["Entry family" ada-entry-family t] ["Select" ada-select t] ["Accept" ada-accept t] - ["Or accept" ada-or-accep t] + ["Or accept" ada-or-accept t] ["Or delay" ada-or-delay t] ["Or terminate" ada-or-terminate t] ["---" nil nil] === modified file 'lisp/textmodes/ispell.el' --- lisp/textmodes/ispell.el 2012-03-17 19:46:52 +0000 +++ lisp/textmodes/ispell.el 2012-03-28 07:24:26 +0000 @@ -740,7 +740,7 @@ Note that with \"ispell\" as the speller, the CASECHARS and OTHERCHARS slots of the alist should contain the same character set as casechars and otherchars in the LANGUAGE.aff file \(e.g., -english.aff\). apsell and hunspell don't have this limitation.") +english.aff\). aspell and hunspell don't have this limitation.") (defvar ispell-really-aspell nil) ; Non-nil if we can use aspell extensions. (defvar ispell-really-hunspell nil) ; Non-nil if we can use hunspell extensions. ------------------------------------------------------------ revno: 107690 fixes bug(s): http://debbugs.gnu.org/cgi/bugreport.cgi?bug=11077 committer: Stefan Monnier branch nick: trunk timestamp: Tue 2012-03-27 16:43:09 -0400 message: * lisp/emacs-lisp/avl-tree.el (avl-tree--enter-balance): Fix paren typo. (avl-tree--check, avl-tree--check-node): New funs. diff: === modified file 'lisp/ChangeLog' --- lisp/ChangeLog 2012-03-27 09:22:01 +0000 +++ lisp/ChangeLog 2012-03-27 20:43:09 +0000 @@ -1,8 +1,14 @@ +2012-03-27 Stefan Monnier + + * emacs-lisp/avl-tree.el (avl-tree--enter-balance): Fix paren typo + (bug#11077). + (avl-tree--check, avl-tree--check-node): New funs. + 2012-03-27 Martin Rudalics * window.el (switch-to-visible-buffer): New option. - (switch-to-prev-buffer, switch-to-next-buffer): Observe - switch-to-visible-buffer. Make sure that checking for a window + (switch-to-prev-buffer, switch-to-next-buffer): + Observe switch-to-visible-buffer. Make sure that checking for a window showing a buffer already is done on the same frame. 2012-03-27 Glenn Morris @@ -28,8 +34,7 @@ 2012-03-25 Eli Zaretskii * makefile.w32-in (install): Use $(DIRNAME)_same-dir.tst instead - of same-dir.tst, to avoid stepping on other (parallel) Make job's - toes. + of same-dir.tst, to avoid stepping on other (parallel) Make job's toes. 2012-03-25 Chong Yidong === modified file 'lisp/emacs-lisp/avl-tree.el' --- lisp/emacs-lisp/avl-tree.el 2012-01-19 07:21:25 +0000 +++ lisp/emacs-lisp/avl-tree.el 2012-03-27 20:43:09 +0000 @@ -295,9 +295,9 @@ (if (> (* sgn b2) 0) (- sgn) 0) (avl-tree--node-balance p1) (if (< (* sgn b2) 0) sgn 0) - (avl-tree--node-branch node branch) p2 - (avl-tree--node-balance - (avl-tree--node-branch node branch)) 0)) + (avl-tree--node-branch node branch) p2)) + (setf (avl-tree--node-balance + (avl-tree--node-branch node branch)) 0) nil)))) (defun avl-tree--do-enter (cmpfun root branch data &optional updatefun) @@ -339,6 +339,16 @@ (cons nil newdata)) ; return value )))) +(defun avl-tree--check (tree) + "Check the tree's balance." + (avl-tree--check-node (avl-tree--root tree))) +(defun avl-tree--check-node (node) + (if (null node) 0 + (let ((dl (avl-tree--check-node (avl-tree--node-left node))) + (dr (avl-tree--check-node (avl-tree--node-right node)))) + (assert (= (- dr dl) (avl-tree--node-balance node))) + (1+ (max dl dr))))) + ;; ----------------------------------------------------------------