bug#16786: 24.2; PostScript file with long lines locks up UI

bug#16786: 24.2; PostScript file with long lines locks up UI

[Andreas Gustafsson]

Hi,

I have a PostScript source file containing some embedded font data
in the form of a single line about 100,000 characters long.

When I open this file in emacs, it stops responding to keystrokes
(including control-G) for several minutes, consuming 100% CPU.

I see this behavior in 22.2.1, 23.4.1, and 24.2.1, but not in 21.4.1.

The problem can be reproduced by evaluating the following elisp
expression:

  (progn
    (switch-to-buffer "test")
    (insert (make-string 100000 97))
    (ps-mode)
  )

-- 
Andreas Gustafsson, gson@gson.org

In GNU Emacs 24.2.1 (x86_64--netbsd)
 of 2012-10-12 on pomegranate.tastylime.net
Configured using:
 `configure '--srcdir=/scratch/editors/emacs24-nox11/work/emacs-24.2'
 '--localstatedir=/var' '--without-dbus' '--without-m17n-flt'
 '--without-otf' '--without-rsvg' '--without-x' '--without-xft'
 '--without-gif' '--without-jpeg' '--without-png' '--without-tiff'
 '--without-xpm' '--prefix=/usr/pkg' '--build=x86_64--netbsd'
 '--host=x86_64--netbsd' '--infodir=/usr/pkg/info'
 '--mandir=/usr/pkg/man' 'build_alias=x86_64--netbsd'
 'host_alias=x86_64--netbsd' 'CC=gcc' 'CFLAGS=-O2 -I/usr/include'
 'LDFLAGS=-L/usr/lib -Wl,-R/usr/lib -Wl,-R/usr/pkg/lib' 'LIBS='
 'CPPFLAGS=-DTERMINFO -I/usr/include''

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: nil
  value of $XMODIFIERS: nil
  locale-coding-system: nil
  default enable-multibyte-characters: t

Major mode: Lisp Interaction

Minor modes in effect:
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  line-number-mode: t
  transient-mark-mode: t

Recent input:
ESC [ ? 1 ; 2 c ESC x r e p o r TAB RET

Recent messages:
("emacs")
Customizing...
Done.
For information about GNU Emacs and the GNU system, type C-h C-a.

Load-path shadows:
None found.

Features:
(shadow sort gnus-util mail-extr warnings emacsbug message format-spec
rfc822 mml easymenu mml-sec mm-decode mm-bodies mm-encode mail-parse
rfc2231 mailabbrev gmm-utils mailheader sendmail rfc2047 rfc2045
ietf-drums mm-util mail-prsvr mail-utils time-date guess-offset cc-vars
cc-defs regexp-opt ediff-hook vc-hooks lisp-float-type lisp-mode
register page menu-bar rfn-eshadow timer 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 minibuffer loaddefs button faces
cus-face files text-properties overlay sha1 md5 base64 format env
code-pages mule custom widget hashtable-print-readable backquote
make-network-process multi-tty emacs)

bug#16786: 24.2; PostScript file with long lines locks up UI

[Glenn Morris]

Andreas Gustafsson wrote:

> I have a PostScript source file containing some embedded font data
> in the form of a single line about 100,000 characters long.

I'm afraid this is a known problem. Emacs does not do well with long
lines, and absolutely not with lines that long.

See http://debbugs.gnu.org/3219 and related reports.

bug#16786: 24.2; PostScript file with long lines locks up UI

[Stefan Monnier]

>   (progn
>     (switch-to-buffer "test")
>     (insert (make-string 100000 97))
>     (ps-mode)
>   )

For this test, the main bottleneck seems to be the

   ("([^()\n%]*\\|[^()\n]*)" . font-lock-warning-face)

rule in ps-mode-font-lock-keywords-1.  The problem is the second half of
the regexp, which will take O(N) time to fail to match at a particular
position and which will try matching at every buffer position, for
a total of O(N^2).

This can be fixed by anchoring the search, e.g. with the patch below.
Of course, a small variation of the above test leads to
other bottlenecks.


        Stefan


=== modified file 'lisp/progmodes/ps-mode.el'
--- lisp/progmodes/ps-mode.el	2014-01-08 18:28:43 +0000
+++ lisp/progmodes/ps-mode.el	2014-02-18 02:10:59 +0000
@@ -220,7 +220,8 @@
     (ps-mode-match-string-or-comment
      (1 font-lock-comment-face nil t)
      (2 font-lock-string-face nil t))
-    ("([^()\n%]*\\|[^()\n]*)" . font-lock-warning-face)
+    ("\\(([^()\n%]*\\)\\|\\(?:^\\|[()]\\)\\(?1:[^()\n]*)\\)"
+     (1 font-lock-warning-face))
     ("[\200-\377]+" (0 font-lock-warning-face prepend nil)))
   "Subdued level highlighting for PostScript mode.")
 

bug#16786: 24.2; PostScript file with long lines locks up UI

[Lars Ingebrigtsen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>   (progn
>>     (switch-to-buffer "test")
>>     (insert (make-string 100000 97))
>>     (ps-mode)
>>   )
>
> For this test, the main bottleneck seems to be the
>
>    ("([^()\n%]*\\|[^()\n]*)" . font-lock-warning-face)

[...]

> This can be fixed by anchoring the search, e.g. with the patch below.
> Of course, a small variation of the above test leads to
> other bottlenecks.

The patch no longer applies...  but on the other hand, the test case
doesn't seem to be a problem any more -- everything seems to be fine in
that area in Emacs 28.

So I'm going to go ahead and close this bug report.  If the problem
still exists, please respond to this email and we'll reopen the bug
report.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no