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

From: Stefan Monnier <[email-masked]>
Date: Mon, 17 Feb 2014 21:15:54 -0500

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