GNU bug report logs - #6640
23.2; Why is this regexp search taking so long? (and will it end?)

Previous Next

To reply to this bug, email your comments to 6640 AT debbugs.gnu.org.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: michael <at> cadilhac.name (Michaël Cadilhac)
To: bug-gnu-emacs <at> gnu.org
Subject: 23.2; Why is this regexp search taking so long? (and will it end?)
Date: Thu, 15 Jul 2010 11:24:17 -0400

- emacs -Q
- Clear the scratch buffer, and paste:

:AAA:AAAAAA:AAAA:aAaaaa:aAaaaa:aAAAAAaaaa:aAaaaa:aAaaaa
aaaaaaaa:Aaaaaaaa:Aaaaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:AaaaaaaaAaaaaaaaa:Aaaaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:Aaaaaaa:AaaaaaaaAaaaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:Aaaaaaa:AaaaaaaAaaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:Aaaaaa:Aaaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:Aaaaaa:Aaaaa:AAAAaaaaaaaa:a:aa:aa:aa:aa
aaaaaaaa:Aaaaaa:AaaaAaaaaaaa:AAAAaaaaaaaa:aa:aa:aa
aaaaaa:Aaa:Aaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:Aaaaaaaaa:Aaaaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:Aaaaaaaa:Aaaa:AAAAaaaaaaaa:a:aa:aa:a:a
aaaaaaaa:Aaaaaaaa:Aaaaaa:AAAAaaaaaaaa:aa:aa:aa
aaaaaaaa:AaaaaaaAaaaaa:Aaaaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:AaaaaaaaaAaaaaaaa:AaaaaaaaaaaAaaaa:AAAAaaaaaaaa:aa:aa:aa:aa
aaaaaaaa:AaaaaaaAaaaaa:Aaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:a
aaaaaaaa:Aaa:Aaaaaa:AAAAaaaaaaaa:aa:aa:aa:aa:aa
aaaaaaaa:AaaaaaaAaaaaaaaa:Aaaaa:AAAAaaaaaaaa:a:aa:aa:aa:aa
aaaaaaaa:Aaaaaaaaa:Aaaa:AAAAaaaaaaaa:a:aa:aa:aa:aa
aaaaaaaa:Aaaaaa:AaaaaaaaaAaaa:AAAAaaaaaaaa:::
aaaaaaaa:Aaaaaaaa:AaaaaaAaaaa:AAAAaaaaaaaa:aa:::aa
aaaaaaaa:Aaaaaaaa:Aaaaaaa:AAAA:::::
aaaaaaaa:AAAaaaa:AAAaaaa:AAAaaaa:::::

(a small input would give quite the same result).
- M-< C-- C-s ^\([^:]*:[^:]*\)\{9\}

  (everything works fine till now)

add an $ to the regexp.

- FEAR the possible endless loop (and the actual unexpected result of
  taking long time).

With an 8 in place of the 9, it takes a long time, but not possibly
endless.

Thanks!


In GNU Emacs 23.2.1 (x86_64-unknown-linux-gnu, GTK+ Version 2.10.14)
 of 2010-07-09 on porto.iro.umontreal.ca
Windowing system distributor `The X.Org Foundation', version 11.0.10300000
configured using `configure  '--prefix=/Tmp/.cadilhac/usr/''

Important settings:
  value of $LC_ALL: nil
  value of $LC_COLLATE: nil
  value of $LC_CTYPE: nil
  value of $LC_MESSAGES: nil
  value of $LC_MONETARY: nil
  value of $LC_NUMERIC: nil
  value of $LC_TIME: nil
  value of $LANG: en_US
  value of $XMODIFIERS: nil
  locale-coding-system: iso-latin-1-unix
  default enable-multibyte-characters: t

Major mode: Browse Server

Minor modes in effect:
  display-time-mode: t
  savehist-mode: t
  show-paren-mode: t
  partial-completion-mode: t
  jabber-activity-mode: t
  tooltip-mode: t
  mouse-wheel-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  column-number-mode: t
  line-number-mode: t

Recent input:
<escape> x g n u s <return> ^ C-n C-n C-n C-n C-t C-t 
RET C-s e m a c s . d e v C-s C-n C-t <escape> x e 
m a c s \ <backspace> - r e p <tab> M-h M-h r e p <tab> 
o r <tab> <return>

Recent messages:
Opening nnimap server on cadilhac.name...failed
nnimap: Listing subscribed mailboxes on gmail.com...done
No new newsgroups
Checking new news...
Opening nntp server on news.gmane.org...done
Checking new news...done
Connecting to news.gmane.org...
Reading active file...done
Connecting to news.gmane.org...done
Mark saved where search started

Load-path shadows:
/usr/share/emacs/site-lisp/php-mode hides ~/.emacs.d/php-mode
/usr/share/emacs/site-lisp/t-mouse hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/t-mouse
~/.emacs.d-local/gnus/pgg-pgp hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/pgg-pgp
~/.emacs.d-local/gnus/md4 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/md4
~/.emacs.d-local/gnus/pgg-parse hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/pgg-parse
~/.emacs.d-local/gnus/pgg-def hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/pgg-def
~/.emacs.d-local/gnus/format-spec hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/format-spec
~/.emacs.d-local/gnus/pgg-pgp5 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/pgg-pgp5
~/.emacs.d-local/gnus/sha1 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/sha1
~/.emacs.d-local/gnus/hex-util hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/hex-util
~/.emacs.d-local/gnus/password-cache hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/password-cache
~/.emacs.d-local/gnus/pgg-gpg hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/pgg-gpg
~/.emacs.d-local/gnus/pgg hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/pgg
~/.emacs.d-local/gnus/dns-mode hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/textmodes/dns-mode
~/.emacs.d/bubbles hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/play/bubbles
~/.emacs.d/animate hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/play/animate
~/.emacs.d-local/gnus/dig hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/dig
~/.emacs.d-local/gnus/dns hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/dns
~/.emacs.d-local/gnus/sasl-digest hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/sasl-digest
~/.emacs.d-local/gnus/netrc hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/netrc
~/.emacs.d-local/gnus/sasl-cram hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/sasl-cram
~/.emacs.d-local/gnus/sasl-ntlm hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/sasl-ntlm
~/.emacs.d-local/gnus/imap hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/imap
~/.emacs.d-local/gnus/sasl hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/sasl
~/.emacs.d-local/gnus/tls hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/tls
~/.emacs.d-local/gnus/hmac-md5 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/hmac-md5
~/.emacs.d-local/gnus/hmac-def hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/hmac-def
~/.emacs.d-local/gnus/ntlm hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/net/ntlm
~/.emacs.d-local/gnus/hashcash hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/mail/hashcash
~/.emacs.d-local/gnus/uudecode hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/mail/uudecode
~/.emacs.d-local/gnus/binhex hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/mail/binhex
~/.emacs.d-local/gnus/gnus-group hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-group
~/.emacs.d-local/gnus/mail-source hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mail-source
~/.emacs.d-local/gnus/mm-bodies hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-bodies
~/.emacs.d-local/gnus/nnnil hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnnil
~/.emacs.d-local/gnus/gnus-range hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-range
~/.emacs.d-local/gnus/rfc2231 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/rfc2231
~/.emacs.d-local/gnus/nnweb hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnweb
~/.emacs.d-local/gnus/nnml hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnml
~/.emacs.d-local/gnus/gnus-kill hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-kill
~/.emacs.d-local/gnus/auth-source hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/auth-source
~/.emacs.d-local/gnus/nnslashdot hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnslashdot
~/.emacs.d-local/gnus/gnus-nocem hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-nocem
~/.emacs.d-local/gnus/gnus-logic hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-logic
~/.emacs.d-local/gnus/gnus-mh hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-mh
~/.emacs.d-local/gnus/gnus-eform hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-eform
~/.emacs.d-local/gnus/mml2015 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mml2015
~/.emacs.d-local/gnus/compface hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/compface
~/.emacs.d-local/gnus/starttls hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/starttls
~/.emacs.d-local/gnus/gnus-mlspl hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-mlspl
~/.emacs.d-local/gnus/gnus-move hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-move
~/.emacs.d-local/gnus/rfc2104 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/rfc2104
~/.emacs.d-local/gnus/pop3 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/pop3
~/.emacs.d-local/gnus/html2text hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/html2text
~/.emacs.d-local/gnus/gnus-start hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-start
~/.emacs.d-local/gnus/gnus-delay hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-delay
~/.emacs.d-local/gnus/mm-url hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-url
~/.emacs.d-local/gnus/gnus-score hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-score
~/.emacs.d-local/gnus/spam-report hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/spam-report
~/.emacs.d-local/gnus/gnus-msg hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-msg
~/.emacs.d-local/gnus/gnus-topic hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-topic
~/.emacs.d-local/gnus/nnmairix hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnmairix
~/.emacs.d-local/gnus/gnus-dup hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-dup
~/.emacs.d-local/gnus/nnmail hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnmail
~/.emacs.d-local/gnus/gnus-srvr hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-srvr
~/.emacs.d-local/gnus/gnus-dired hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-dired
~/.emacs.d-local/gnus/nntp hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nntp
~/.emacs.d-local/gnus/gnus-salt hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-salt
~/.emacs.d-local/gnus/gnus-int hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-int
~/.emacs.d-local/gnus/gnus-uu hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-uu
~/.emacs.d-local/gnus/nndoc hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nndoc
~/.emacs.d-local/gnus/rfc1843 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/rfc1843
~/.emacs.d-local/gnus/mm-util hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-util
~/.emacs.d-local/gnus/gnus-bcklg hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-bcklg
~/.emacs.d-local/gnus/utf7 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/utf7
~/.emacs.d-local/gnus/spam hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/spam
~/.emacs.d-local/gnus/gnus-ems hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-ems
~/.emacs.d-local/gnus/score-mode hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/score-mode
~/.emacs.d-local/gnus/flow-fill hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/flow-fill
~/.emacs.d-local/gnus/gnus-spec hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-spec
~/.emacs.d-local/gnus/mailcap hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mailcap
~/.emacs.d-local/gnus/gnus-registry hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-registry
~/.emacs.d-local/gnus/nndiary hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nndiary
~/.emacs.d-local/gnus/canlock hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/canlock
~/.emacs.d-local/gnus/nnkiboze hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnkiboze
~/.emacs.d-local/gnus/gnus-cus hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-cus
~/.emacs.d-local/gnus/mm-view hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-view
~/.emacs.d-local/gnus/nnimap hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnimap
~/.emacs.d-local/gnus/nnlistserv hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnlistserv
~/.emacs.d-local/gnus/gnus-setup hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-setup
~/.emacs.d-local/gnus/spam-stat hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/spam-stat
~/.emacs.d-local/gnus/nnspool hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnspool
~/.emacs.d-local/gnus/nngateway hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nngateway
~/.emacs.d-local/gnus/legacy-gnus-agent hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/legacy-gnus-agent
~/.emacs.d-local/gnus/mml-sec hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mml-sec
~/.emacs.d-local/gnus/message hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/message
~/.emacs.d-local/gnus/mm-uu hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-uu
~/.emacs.d-local/gnus/earcon hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/earcon
~/.emacs.d-local/gnus/gnus-agent hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-agent
~/.emacs.d-local/gnus/gnus-win hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-win
~/.emacs.d-local/gnus/gnus-cache hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-cache
~/.emacs.d-local/gnus/nndraft hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nndraft
~/.emacs.d-local/gnus/gnus-sum hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-sum
~/.emacs.d-local/gnus/gnus-picon hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-picon
~/.emacs.d-local/gnus/gnus-sieve hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-sieve
~/.emacs.d-local/gnus/mm-partial hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-partial
~/.emacs.d-local/gnus/nnoo hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnoo
~/.emacs.d-local/gnus/gnus-audio hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-audio
~/.emacs.d-local/gnus/mm-decode hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-decode
~/.emacs.d-local/gnus/nnvirtual hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnvirtual
~/.emacs.d-local/gnus/yenc hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/yenc
~/.emacs.d-local/gnus/mml-smime hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mml-smime
~/.emacs.d-local/gnus/smiley hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/smiley
~/.emacs.d-local/gnus/nnmh hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnmh
~/.emacs.d-local/gnus/messcompat hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/messcompat
~/.emacs.d-local/gnus/mml1991 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mml1991
~/.emacs.d-local/gnus/gmm-utils hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gmm-utils
~/.emacs.d-local/gnus/qp hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/qp
~/.emacs.d-local/gnus/gnus-fun hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-fun
~/.emacs.d-local/gnus/gnus-soup hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-soup
~/.emacs.d-local/gnus/gnus-async hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-async
~/.emacs.d-local/gnus/nnagent hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnagent
~/.emacs.d-local/gnus/sieve hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/sieve
~/.emacs.d-local/gnus/spam-wash hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/spam-wash
~/.emacs.d-local/gnus/nnheader hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnheader
~/.emacs.d-local/gnus/smime hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/smime
~/.emacs.d-local/gnus/mail-prsvr hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mail-prsvr
~/.emacs.d-local/gnus/mail-parse hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mail-parse
~/.emacs.d-local/gnus/nndb hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nndb
~/.emacs.d-local/gnus/sieve-manage hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/sieve-manage
~/.emacs.d-local/gnus/nnir hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnir
~/.emacs.d-local/gnus/nndir hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nndir
~/.emacs.d-local/gnus/gnus hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus
~/.emacs.d-local/gnus/nneething hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nneething
~/.emacs.d-local/gnus/nnfolder hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnfolder
~/.emacs.d-local/gnus/rfc2047 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/rfc2047
~/.emacs.d-local/gnus/mm-extern hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-extern
~/.emacs.d-local/gnus/mml hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mml
~/.emacs.d-local/gnus/gnus-diary hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-diary
~/.emacs.d-local/gnus/nnsoup hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnsoup
~/.emacs.d-local/gnus/nnrss hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnrss
~/.emacs.d-local/gnus/nnmaildir hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnmaildir
~/.emacs.d-local/gnus/nnwarchive hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnwarchive
~/.emacs.d-local/gnus/nnbabyl hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnbabyl
~/.emacs.d-local/gnus/sieve-mode hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/sieve-mode
~/.emacs.d-local/gnus/gnus-demon hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-demon
~/.emacs.d-local/gnus/deuglify hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/deuglify
~/.emacs.d-local/gnus/nnmbox hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/nnmbox
~/.emacs.d-local/gnus/gnus-art hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-art
~/.emacs.d-local/gnus/gnus-bookmark hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-bookmark
~/.emacs.d-local/gnus/rfc2045 hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/rfc2045
~/.emacs.d-local/gnus/gnus-ml hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-ml
~/.emacs.d-local/gnus/gnus-cite hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-cite
~/.emacs.d-local/gnus/mm-encode hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/mm-encode
~/.emacs.d-local/gnus/gnus-util hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-util
~/.emacs.d-local/gnus/gnus-vm hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-vm
~/.emacs.d-local/gnus/ecomplete hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/ecomplete
~/.emacs.d-local/gnus/gnus-draft hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-draft
~/.emacs.d-local/gnus/gnus-undo hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/gnus-undo
~/.emacs.d-local/gnus/ietf-drums hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/gnus/ietf-drums
~/.emacs.d-local/gnus/time-date hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/calendar/time-date
~/.emacs.d-local/gnus/parse-time hides /Tmp/.cadilhac/usr/share/emacs/23.2/lisp/calendar/parse-time

Features:
(shadow sort footnote flyspell ispell emacsbug multi-isearch gnus-topic
nnfolder utf-7 utf7 auth-source netrc nnimap imap nndraft nnmh bbdb-gnus
bbdb-snarf mail-extr bbdb-com nnnil gnus-agent gnus-srvr gnus-score
score-mode nnvirtual gnus-msg gnus-art mm-uu mml2015 epg-config mm-view
smime password-cache dig gnus-cache gnus-demon nntp bbdb-autoloads
gnus-registry gnus-sum nnoo gnus-group time-date gnus-undo nnmail
mail-source smtpmail bbdb gnus-start gnus-spec gnus-int gnus-range
message idna sendmail rfc822 mml mml-sec mm-decode mm-bodies mm-encode
mail-parse rfc2231 rfc2047 rfc2045 ietf-drums mailabbrev gmm-utils
mailheader gnus-win gnus gnus-ems nnheader gnus-util mail-utils server
copyright latex-directory latex tex-style tex vaucanson whitespace
tabify page-ext time savehist paren complete rebox lpr quail help-mode
view proof-site proof-autoloads netsoul jabber jabber-events
jabber-vcard jabber-activity jabber-watch jabber-keepalive
jabber-modeline easy-mmode jabber-ahc-presence jabber-ahc jabber-version
jabber-browse jabber-search jabber-register jabber-roster format-spec
jabber-presence jabber-muc jabber-widget jabber-disco wid-edit
jabber-chat jabber-history jabber-chatbuffer jabber-alert
jabber-xmessage jabber-festival jabber-sawfish jabber-ratpoison
jabber-screen jabber-iq jabber-keymap jabber-core jabber-sasl sasl
sasl-anonymous sasl-login sasl-plain jabber-logon sha1 hex-util
jabber-conn tls jabber-xml xml jabber-menu jabber-util msf-abbrev
anything-config advice help-fns advice-preload rx anything edmacro
kmacro woman man assoc cl cl-19 ido tempo url url-proxy url-privacy
url-expand url-methods url-history url-cookie url-util url-parse
timezone url-vars mm-util mail-prsvr mailcap xml-parse doxymacs
buffer-move windmove parenface cc-mode cc-fonts easymenu cc-menus
cc-cmds cc-styles cc-align cc-engine cc-vars cc-defs regexp-opt
mathematica tex-site tooltip ediff-hook vc-hooks lisp-float-type mwheel
x-win x-dnd font-setting tool-bar dnd fontset image fringe lisp-mode
register page menu-bar rfn-eshadow timer select scroll-bar mldrag mouse
jit-lock font-lock syntax facemenu font-core frame cham georgian
utf-8-lang misc-lang vietnamese tibetan thai tai-viet lao korean
japanese hebrew greek romanian slovak czech european ethiopic indian
cyrillic chinese case-table epa-hook jka-cmpr-hook help simple abbrev
loaddefs button minibuffer faces cus-face files text-properties overlay
md5 base64 format env code-pages mule custom widget
hashtable-print-readable backquote make-network-process dbusbind
system-font-setting font-render-setting gtk x-toolkit x multi-tty emacs)

Message #8 received at 6640 <at> debbugs.gnu.org (full text, mbox):

From: Ryan Rix <ryan <at> whatthefuck.computer>
To: 6640 <at> debbugs.gnu.org
Cc: michael <at> cadilhac.name
Subject: Re: bug#6640: 23.2;
 Why is this regexp search taking so long? (and will it end?)
Date: Sun, 06 Mar 2016 04:12:59 +0000

michael <at> cadilhac.name "(Michaël" Cadilhac) writes:
> - emacs -Q
> - Clear the scratch buffer, and paste:
>
[redact]
>
> (a small input would give quite the same result).
> - M-< C-- C-s ^\([^:]*:[^:]*\)\{9\}
>
>   (everything works fine till now)
>
> add an $ to the regexp.
>
> - FEAR the possible endless loop (and the actual unexpected result of
>   taking long time).
>
> With an 8 in place of the 9, it takes a long time, but not possibly
> endless.
>
> Thanks!

Hi Michael,

Thanks for reporting this. I can confirm this is still an issue in the
latest emacs-25, commit e51b27ec2ce214ef3d8377a27ee9d857bcc66afc

I will leave it to smarter minds than my own to debug the regex engine,
though.

Message #11 received at 6640 <at> debbugs.gnu.org (full text, mbox):

From: Noam Postavsky <npostavs <at> users.sourceforge.net>
To: 6640 <at> debbugs.gnu.org
Cc: Ryan Rix <ryan <at> whatthefuck.computer>, michael <at> cadilhac.name
Subject: Re: bug#6640: 23.2; Why is this regexp search taking so long? (and
 will it end?)
Date: Fri, 10 Jun 2016 17:13:16 -0400

I haven't actually debugged the regexp engine, but I believe the
problem is that this regexp contains several repetitions of [^:]*[^:]*
(which becomes apparent if you expand the \{9\}). The regexp engine
isn't smart enough to coalesce them so when the match fails (due to
$), it has to go back and retry with all the possible different
matches to see if it will work that way. There are A^n possible
matches to try, where A is the length of non-colon string in the
buffer, and n is the number of [^:]*[^:]* sequences in the regexp
(which is 8 if \{9\} is used).

A regexp which should match the same thing is ^\([^:]*:\)\{9\}[^:]*
and ^\([^:]*:\)\{9\}[^:]*$ will fail to match anything much faster.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.