The overlay branch (yet again)

The overlay branch (yet again)

[Vladimir Kazanov]

Hi all,

a few years ago I tried replacing the underlying overlay data
structure with a tree-based one. Back then I ran out of spare time and
had to delay the project.

I'll have time on my hands this winter and would like to get back to
the project again. This time it seems that most of the work was done
by Andreas Politz in the feature/noverlay branch:

https://lists.gnu.org/archive/html/emacs-devel/2018-03/msg00565.html
https://lists.gnu.org/archive/html/emacs-devel/2019-09/msg00543.html

It seems reasonable to pick up the branch and try to finish it, unless
somebody is already working on it. So my questions are:

is anybody working on the branch? why was it abandoned? Are there any
known problems with it?

Thank you

-- 
Yours sincerely,


Vladimir Kazanov

Re: The overlay branch (yet again)

[Vladimir Kazanov]

Hi all again,

I went through the code written by Andreas Politz (in the
feature/noverlay branch) and all of the related discussions. He
completed an astonishing amount of work! Apart from changes to the
working code the branch includes 1300 LOC of manually written
overlay-related tests, 5700 LOC of automatically generated unit tests
and C-level interval tree tests. Check test/src/buffer-tests.el in the
feature/noverlay branch for reference.

It would be a waste to just throw all of that away. As a first step I
really want to put those tests to work.

Given that nobody replied to my original email I assume everybody is
busy with the new release. In the meantime I'd really like to try to
pick up the work already done on overlays. I have a following plan:

1. A separate patch containing all those tests.
2. A second patch, making overlay code independent from the underlying
implementation.
3. A third patch, providing a tree-based data structure using either
what Andreas built, or smth else.

The first patch should be fairy trivial: I'll extract overlay-specific
tests into a overlay-test.el (while attributing all of the changes to
Andreas, of course), clean up a bit and drop C-level tests. I believe
those tests are really useful the way they are right now and can be
merged separately.

Having those tests merged it will be much easier to go on with further
overlay-related changes (i.e. tweaking internal APIs, or underlying
data structures).

Is anybody interested in me doing this work?

On Tue, Nov 26, 2019 at 2:44 PM Vladimir Kazanov <vekazanov@gmail.com> wrote:
>
> Hi all,
>
> a few years ago I tried replacing the underlying overlay data
> structure with a tree-based one. Back then I ran out of spare time and
> had to delay the project.
>
> I'll have time on my hands this winter and would like to get back to
> the project again. This time it seems that most of the work was done
> by Andreas Politz in the feature/noverlay branch:
>
> https://lists.gnu.org/archive/html/emacs-devel/2018-03/msg00565.html
> https://lists.gnu.org/archive/html/emacs-devel/2019-09/msg00543.html
>
> It seems reasonable to pick up the branch and try to finish it, unless
> somebody is already working on it. So my questions are:
>
> is anybody working on the branch? why was it abandoned? Are there any
> known problems with it?
>
> Thank you
>
> --
> Yours sincerely,
>
>
> Vladimir Kazanov



-- 
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Re: The overlay branch (yet again)

[Eli Zaretskii]

> From: Vladimir Kazanov <vekazanov@gmail.com>
> Date: Tue, 3 Dec 2019 15:35:17 +0000
> 
> Is anybody interested in me doing this work?

Yes, of course.  Thanks for volunteering.

Re: The overlay branch (yet again)

[martin rudalics]

 > Given that nobody replied to my original email I assume everybody is
 > busy with the new release.

I didn't reply becaue I'm not enough familiar with the subject, in
particular with the work that Andreas did.

 > Is anybody interested in me doing this work?

I definitely am interested.

Thanks, martin

Re: The overlay branch (yet again)

[Vladimir Kazanov]

Thanks, Eli and Martin! Will do.

Martin,

in short, Andreas replaced the current (relatively) inefficient linked
list overlay implementation with a tree-based one. This might sound as
something relatively simple but in practice it turns out that there
are lots of subtle issues in both the tree implementation and
resulting Emacs integration. I know because I tried - and failed. At
least twice :-)

But Andreas almost made it! So I want to reuse some of that massive
effort: merge tests at the very least, untangle overlay code a bit and
- hopefully - replace those linked lists.

On Tue, Dec 3, 2019 at 4:06 PM martin rudalics <rudalics@gmx.at> wrote:
>
>  > Given that nobody replied to my original email I assume everybody is
>  > busy with the new release.
>
> I didn't reply becaue I'm not enough familiar with the subject, in
> particular with the work that Andreas did.
>
>  > Is anybody interested in me doing this work?
>
> I definitely am interested.
>
> Thanks, martin



-- 
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Re: The overlay branch (yet again)

[Stefan Monnier]

>>  > Given that nobody replied to my original email I assume everybody is
>>  > busy with the new release.

Not exactly with the new release, but yes your message fell into the
"todo" black hole, sorry :-(

>>  > Is anybody interested in me doing this work?
>> I definitely am interested.

Me too.

> But Andreas almost made it! So I want to reuse some of that massive
> effort: merge tests at the very least, untangle overlay code a bit and
> - hopefully - replace those linked lists.

Yes, please!

Also, I hope the new code can capture some of the insights learned along
the way, and the design choices, e.g. in the form of comments describing the
various performance aspects that were considered (complexity of
`make-overlay`, `delete-overlay`, `overlay-start`, `overlays-at/in`,
`previous-char-property-change`, of updating overlays in response to
buffer text modifications, ...).

Also, some performance tests would be great.  IIRC a few months ago
someone here posted some simple tests showing some percentage
improvement in some cases, but there has to be situations where the new
code is massively faster (after all, the new code uses a different data
structure specifically to change the algorithmic complexity of some
operations).  It's quite possible that those situations don't "occur
naturally" in current code, but it should be possible to trigger them in
artificial but realistic situations (maybe changing font-lock to use
overlays instead of text-properties, or forcing nhexl-mode to nhexlify
eagerly the whole buffer, I don't know).

But merging the tests into `master` would be a great first step.


        Stefan

Re: The overlay branch (yet again)

[Vladimir Kazanov]

> Also, I hope the new code can capture some of the insights learned along
> the way, and the design choices, e.g. in the form of comments describing the
> various performance aspects that were considered (complexity of
> `make-overlay`, `delete-overlay`, `overlay-start`, `overlays-at/in`,
> `previous-char-property-change`, of updating overlays in response to
> buffer text modifications, ...).

Do mean something like inline comments for functions accessible from
Emacs Lisp? I'll try to do my best. But it'll take some time before I
will fell comfortable with the new implementation. This time around I
want to proceed in small steps: merge tests -> untangle/clarify
internal overlay apis -> replace the lists (with the code Andreas
built, hopefully).

> Also, some performance tests would be great.  IIRC a few months ago
> someone here posted some simple tests showing some percentage
> improvement in some cases, but there has to be situations where the new
> code is massively faster (after all, the new code uses a different data
> structure specifically to change the algorithmic complexity of some
> operations).  It's quite possible that those situations don't "occur
> naturally" in current code, but it should be possible to trigger them in
> artificial but realistic situations (maybe changing font-lock to use
> overlays instead of text-properties, or forcing nhexl-mode to nhexlify
> eagerly the whole buffer, I don't know).

I found at least three performance comparisons Andreas provided when
discussing his implementation:

https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00488.html
https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00598.html
https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00736.html

Notice how in the second message he provides a couple of nice
realistic examples.

But I don't think I saw (I'll have to recheck as I wasn't looking) any
benchmarking code in the branch. Anyways, It'll take some time for me
to reach that point.

> But merging the tests into `master` would be a great first step.

Indeed.

On Tue, Dec 3, 2019 at 5:58 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>
> >>  > Given that nobody replied to my original email I assume everybody is
> >>  > busy with the new release.
>
> Not exactly with the new release, but yes your message fell into the
> "todo" black hole, sorry :-(
>
> >>  > Is anybody interested in me doing this work?
> >> I definitely am interested.
>
> Me too.
>
> > But Andreas almost made it! So I want to reuse some of that massive
> > effort: merge tests at the very least, untangle overlay code a bit and
> > - hopefully - replace those linked lists.
>
> Yes, please!
>
> Also, I hope the new code can capture some of the insights learned along
> the way, and the design choices, e.g. in the form of comments describing the
> various performance aspects that were considered (complexity of
> `make-overlay`, `delete-overlay`, `overlay-start`, `overlays-at/in`,
> `previous-char-property-change`, of updating overlays in response to
> buffer text modifications, ...).
>
> Also, some performance tests would be great.  IIRC a few months ago
> someone here posted some simple tests showing some percentage
> improvement in some cases, but there has to be situations where the new
> code is massively faster (after all, the new code uses a different data
> structure specifically to change the algorithmic complexity of some
> operations).  It's quite possible that those situations don't "occur
> naturally" in current code, but it should be possible to trigger them in
> artificial but realistic situations (maybe changing font-lock to use
> overlays instead of text-properties, or forcing nhexl-mode to nhexlify
> eagerly the whole buffer, I don't know).
>
> But merging the tests into `master` would be a great first step.
>
>
>         Stefan
>


-- 
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Re: The overlay branch (yet again)

[Stefan Monnier]

> https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00488.html
> https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00598.html
> https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00736.html

At least those links should be in comments somewhere in the code.


        Stefan

Re: The overlay branch (yet again)

[Vladimir Kazanov]

[-- Attachment #1: Type: text/plain, Size: 1199 bytes --]

So here's the first patch containing a few hundred (!!!)
implementation-agnostic overlay tests.

I took all Lisp-level overlay related tests in the feature-noverlay
branch, removed automatically generated ones and a single test that
was aware of the tree-based implementation. This should be a good
basis for any further work related to overlays (and buffers in
general).

I did not add a single line of code, all credit goes to Andreas.

Feel free to request tweaks and additions. Note that I am still in the
process of pushing the papers through corporate bureaucracy. No
problems, I got all the approvals needed but it'll take a week or two
more.

Thanks

On Tue, Dec 3, 2019 at 10:43 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
>
> > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00488.html
> > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00598.html
> > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00736.html
>
> At least those links should be in comments somewhere in the code.
>
>
>         Stefan
>


-- 
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

[-- Attachment #2: 0001-Include-overlay-tests.patch --]
[-- Type: text/x-patch, Size: 53157 bytes --]

diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el
index 845d41f9d6..1a78960b9d 100644
--- a/test/src/buffer-tests.el
+++ b/test/src/buffer-tests.el
@@ -94,4 +94,1212 @@
       (insert "toto")
       (move-overlay ol (point-min) (point-min)))))
 
+
+;; +===================================================================================+
+;; | Overlay test setup
+;; +===================================================================================+
+
+(eval-when-compile
+  (defun make-overlay-test-name (fn x y)
+    (intern (format "test-%s-%s-%s" fn x y))))
+
+(defun unmake-ov-test-name (symbol)
+  (let ((name (if (stringp symbol) symbol (symbol-name symbol))))
+    (when (string-match "\\`test-\\(.*\\)-\\(.*\\)-\\(.*\\)\\'" name)
+      (list (match-string 1 name) (match-string 2 name) (match-string 3 name)))))
+
+(defmacro deftest-make-overlay-1 (id args)
+  (declare (indent 1))
+  `(ert-deftest ,(make-overlay-test-name 'make-overlay 1 id) ()
+     (with-temp-buffer
+       (should ,(cons 'make-overlay args)))))
+
+(defmacro deftest-make-overlay-2 (id args condition)
+  (declare (indent 1))
+  `(ert-deftest ,(make-overlay-test-name 'make-overlay 2 id) ()
+     (with-temp-buffer
+       (should-error
+        ,(cons 'make-overlay args)
+        :type ',condition
+        :exclude-subtypes t))))
+
+(defmacro deftest-overlay-start/end-1 (id start-end-args start-end-should)
+  (declare (indent 1))
+  (cl-destructuring-bind (start end sstart send)
+      (append start-end-args start-end-should)
+    `(ert-deftest ,(make-overlay-test-name 'overlay-start/end 1 id) ()
+       (with-temp-buffer
+         (insert (make-string 9 ?\n))
+         (let ((ov (make-overlay ,start ,end)))
+           (should (equal ,sstart (overlay-start ov)))
+           (should (equal ,send (overlay-end ov))))))))
+
+(defmacro deftest-overlay-buffer-1 (id arg-expr should-expr)
+  (declare (indent 1))
+  `(ert-deftest ,(make-overlay-test-name 'overlay-buffer 1 id) ()
+     (with-temp-buffer
+       (should (equal (overlay-buffer (make-overlay 1 1 ,arg-expr))
+                      ,should-expr)))))
+
+(defmacro deftest-overlayp-1 (id arg-expr should-expr)
+  (declare (indent 1))
+  `(ert-deftest ,(make-overlay-test-name 'overlay-buffer 1 id) ()
+     (with-temp-buffer
+       (should (equal ,should-expr (overlayp ,arg-expr))))))
+
+(defmacro deftest-next-overlay-change-1 (id pos result &rest ov-tuple)
+  `(ert-deftest ,(make-overlay-test-name 'next-overlay-change 1 id) ()
+     (let ((tuple (copy-sequence ',ov-tuple)))
+       (with-temp-buffer
+         (insert (make-string (max 100 (if tuple
+                                           (apply #'max
+                                                  (mapcar
+                                                   (lambda (m) (apply #'max m)) tuple))
+                                         0))
+                              ?\n))
+         (dolist (tup tuple)
+           (make-overlay (car tup) (cadr tup)))
+         (should (equal (next-overlay-change ,pos)
+                        ,result))))))
+
+(defmacro deftest-previous-overlay-change-1 (id pos result &rest ov-tuple)
+  `(ert-deftest ,(make-overlay-test-name 'previous-overlay-change 1 id) ()
+     (let ((tuple ',ov-tuple))
+       (with-temp-buffer
+         (insert (make-string (max 100 (if tuple
+                                           (apply #'max
+                                                  (mapcar
+                                                   (lambda (m) (apply #'max m)) tuple))
+                                         0))
+                              ?\n))
+         (dolist (tup tuple)
+           (make-overlay (car tup) (cadr tup)))
+         (should (equal (previous-overlay-change ,pos)
+                        ,result))))))
+
+(defmacro deftest-overlays-at-1 (id pos result &rest ov-triple)
+  `(ert-deftest ,(make-overlay-test-name 'overlays-at 1 id) ()
+     (let ((pos* ,pos))
+       (with-temp-buffer
+         (insert (make-string 100 ?\s))
+         (should-not (memq nil ',result))
+         (dolist (v ',ov-triple)
+           (cl-destructuring-bind (tag start end)
+               v
+             (overlay-put (make-overlay start end) 'tag tag)))
+         (let ((ovl (overlays-at pos*)))
+           (should (equal (length ovl) (length ',result)))
+           (dolist (ov ovl)
+             (should (memq (overlay-get ov 'tag) ',result))))))))
+
+(defmacro deftest-overlays-in-1 (id beg end result &rest ov-triple)
+  `(ert-deftest ,(make-overlay-test-name 'overlays-in 1 id) ()
+     (let ((beg* ,beg)
+           (end* ,end))
+       (with-temp-buffer
+         (insert (make-string 100 ?\s))
+         (should-not (memq nil ',result))
+         (dolist (v ',ov-triple)
+           (cl-destructuring-bind (tag start end)
+               v
+             (overlay-put (make-overlay start end) 'tag tag)))
+         (let ((ovl (overlays-in beg* end*)))
+           (should (equal (length ovl) (length ',result)))
+           (dolist (ov ovl)
+             (should (memq (overlay-get ov 'tag) ',result))))))))
+
+(defmacro test-with-overlay-in-buffer (symbol-beg-end-fa-ra &rest body)
+  (declare (indent 1))
+  (cl-destructuring-bind (symbol beg end &optional fa ra)
+      symbol-beg-end-fa-ra
+    `(with-temp-buffer
+       (insert (make-string (max 1000 (1- ,end)) ?\s))
+       (goto-char 1)
+       (let ((,symbol (make-overlay ,beg ,end nil ,fa ,ra)))
+         ,@body))))
+
+(defmacro deftest-overlays-equal-1 (id result ov1-args ov2-args)
+  `(ert-deftest ,(make-overlay-test-name 'overlays-equal 1 id) ()
+     (cl-labels ((create-overlay (args)
+                                 (cl-destructuring-bind (start end &optional fa ra &rest properties)
+                                     args
+                                   (let ((ov (make-overlay start end nil fa ra)))
+                                     (while properties
+                                       (overlay-put ov (pop properties) (pop properties)))
+                                     ov))))
+       (with-temp-buffer
+         (insert (make-string 1024 ?\s))
+         (should (,(if result 'identity 'not)
+                  (equal (create-overlay ',ov1-args)
+                         (create-overlay ',ov2-args))))))))
+
+
+(defun find-ert-overlay-test (name)
+  (let ((test (unmake-ov-test-name name)))
+    (or (and test
+             (cl-destructuring-bind (fn x y)
+                 test
+               (let ((regexp (format "deftest-%s-%s +%s" fn x y)))
+                 (re-search-forward regexp nil t))))
+        (let ((find-function-regexp-alist
+               (cl-remove 'find-ert-overlay-test find-function-regexp-alist :key #'cdr)))
+          (find-function-do-it name 'ert-deftest 'switch-to-buffer-other-window)))))
+
+(add-to-list 'find-function-regexp-alist
+             '(ert-deftest . find-ert-overlay-test))
+
+
+;; +===================================================================================+
+;; | make-overlay
+;; +===================================================================================+
+
+;; Test if making an overlay succeeds.
+(deftest-make-overlay-1 A (1 1))
+(deftest-make-overlay-1 B (7 26))
+(deftest-make-overlay-1 C (29 7))
+(deftest-make-overlay-1 D (most-positive-fixnum 1))
+(deftest-make-overlay-1 E (most-negative-fixnum 1))
+(deftest-make-overlay-1 F (1 most-positive-fixnum))
+(deftest-make-overlay-1 G (1 most-negative-fixnum))
+(deftest-make-overlay-1 H (1 1 nil t))
+(deftest-make-overlay-1 I (1 1 nil nil))
+(deftest-make-overlay-1 J (1 1 nil nil nil))
+(deftest-make-overlay-1 K (1 1 nil nil t))
+(deftest-make-overlay-1 L (1 1 nil t t))
+(deftest-make-overlay-1 M (1 1 nil "yes" "yes"))
+
+;; Test if trying to make an overlay signals conditions.
+(deftest-make-overlay-2 A ()            wrong-number-of-arguments)
+(deftest-make-overlay-2 B (1)           wrong-number-of-arguments)
+(deftest-make-overlay-2 C (1 2 3 4 5 6) wrong-number-of-arguments)
+(deftest-make-overlay-2 D ("1")         wrong-number-of-arguments)
+(deftest-make-overlay-2 E ("1" "2")     wrong-type-argument)
+(deftest-make-overlay-2 F (1 2 "b")     wrong-type-argument)
+(deftest-make-overlay-2 G (1 2 3.14)    wrong-type-argument)
+(deftest-make-overlay-2 H (3.14 3)      wrong-type-argument)
+(deftest-make-overlay-2 I (1 [1])       wrong-type-argument)
+(deftest-make-overlay-2 J (1 1 (with-temp-buffer
+                                 (current-buffer)))
+  error)
+
+
+;; +===================================================================================+
+;; | overlay-start/end
+;; +===================================================================================+
+
+;; Test if the overlays return proper positions.  point-max of the
+;; buffer will equal 10.        ARG RESULT
+(deftest-overlay-start/end-1 A (1 1) (1 1))
+(deftest-overlay-start/end-1 B (2 7) (2 7))
+(deftest-overlay-start/end-1 C (7 2) (2 7))
+(deftest-overlay-start/end-1 D (1 10) (1 10))
+(deftest-overlay-start/end-1 E (1 11) (1 10))
+(deftest-overlay-start/end-1 F (1 most-positive-fixnum) (1 10))
+(deftest-overlay-start/end-1 G (most-positive-fixnum 1) (1 10))
+(deftest-overlay-start/end-1 H (most-positive-fixnum most-positive-fixnum) (10 10))
+(deftest-overlay-start/end-1 I (100 11) (10 10))
+(deftest-overlay-start/end-1 J (11 100) (10 10))
+(deftest-overlay-start/end-1 K (0 1) (1 1))
+(deftest-overlay-start/end-1 L (1 0) (1 1))
+(deftest-overlay-start/end-1 M (0 0) (1 1))
+
+(ert-deftest test-overlay-start/end-2 ()
+  (should-not (overlay-start (with-temp-buffer (make-overlay 1 1))))
+  (should-not (overlay-end (with-temp-buffer (make-overlay 1 1)))))
+
+
+;; +===================================================================================+
+;; | overlay-buffer
+;; +===================================================================================+
+
+;; Test if overlay-buffer returns appropriate values.
+(deftest-overlay-buffer-1 A (current-buffer) (current-buffer))
+(deftest-overlay-buffer-1 B nil (current-buffer))
+(ert-deftest test-overlay-buffer-1-C ()
+  (should-error (make-overlay
+                 1 1 (with-temp-buffer (current-buffer)))))
+
+
+;; +===================================================================================+
+;; | overlayp
+;; +===================================================================================+
+
+;; Check the overlay predicate.
+(deftest-overlayp-1 A (make-overlay 1 1) t)
+(deftest-overlayp-1 B (with-temp-buffer (make-overlay 1 1)) t)
+(deftest-overlayp-1 C nil                            nil)
+(deftest-overlayp-1 D 'symbol                        nil)
+(deftest-overlayp-1 E "string"                       nil)
+(deftest-overlayp-1 F 42                             nil)
+(deftest-overlayp-1 G [1 2]                          nil)
+(deftest-overlayp-1 H (symbol-function 'car)         nil)
+(deftest-overlayp-1 I float-pi                       nil)
+(deftest-overlayp-1 J (cons 1 2)                     nil)
+(deftest-overlayp-1 K (make-hash-table)              nil)
+(deftest-overlayp-1 L (symbol-function 'ert-deftest) nil)
+(deftest-overlayp-1 M (current-buffer)               nil)
+(deftest-overlayp-1 N (selected-window)              nil)
+(deftest-overlayp-1 O (selected-frame)               nil)
+
+
+;; +===================================================================================+
+;; | overlay equality
+;; +===================================================================================+
+
+(deftest-overlays-equal-1 A t (1 1) (1 1))
+(deftest-overlays-equal-1 B t (5 10) (5 10))
+(deftest-overlays-equal-1 C nil (5 11) (5 10))
+(deftest-overlays-equal-1 D t (10 20 t) (10 20))
+(deftest-overlays-equal-1 E t (10 20 nil t) (10 20))
+(deftest-overlays-equal-1 F t (10 20 t t) (10 20 nil t))
+(deftest-overlays-equal-1 G t (10 20 t t) (10 20 t nil))
+(deftest-overlays-equal-1 H t (10 20 nil nil foo 42) (10 20 nil nil foo 42))
+(deftest-overlays-equal-1 I nil (10 20 nil nil foo 42) (10 20 nil nil foo 43))
+
+
+;; +===================================================================================+
+;; | overlay-lists
+;; +===================================================================================+
+
+;; Check whether overlay-lists returns something sensible.
+(ert-deftest test-overlay-lists-1 ()
+  (with-temp-buffer
+    (should (equal (cons nil nil) (overlay-lists)))
+    (dotimes (i 10) (make-overlay 1 i))
+    (should (listp (car (overlay-lists))))
+    (should (listp (cdr (overlay-lists))))
+    (let ((list (append (car (overlay-lists))
+                        (cdr (overlay-lists)))))
+      (should (= 10 (length list)))
+      (should (seq-every-p #'overlayp list)))))
+
+
+;; +===================================================================================+
+;; | overlay-put/get/properties
+;; +===================================================================================+
+
+;; Test if overlay-put properties can be retrieved by overlay-get and
+;; overlay-properties.
+(ert-deftest test-overlay-props-1 ()
+  (with-temp-buffer
+    (let* ((keys '(:k1 :k2 :k3))
+           (values '(1 "v2" v3))
+           (ov (make-overlay 1 1))
+           (n (length keys)))
+      (should (equal (length keys) (length values)))
+      (should (null (overlay-properties ov)))
+      ;; Insert keys and values.
+      (dotimes (i n)
+        (should (equal (overlay-put ov (nth i keys) (nth i values))
+                       (nth i values))))
+      ;; Compare with what overlay-get says.
+      (dotimes (i n)
+        (should (equal (overlay-get ov (nth i keys))
+                       (nth i values))))
+      ;; Test if overlay-properties is a superset.
+      (dotimes (i n)
+        (should (equal (plist-get (overlay-properties ov)
+                                  (nth i keys))
+                       (nth i values))))
+      ;; Check if overlay-properties is a subset.
+      (should (= (length (overlay-properties ov)) (* n 2))))))
+
+
+;; +===================================================================================+
+;; | next-overlay-change
+;; +===================================================================================+
+
+;; Test if next-overlay-change returns RESULT if called with POS in a
+;; buffer with overlays corresponding to OVS and point-max >= 100.
+;;                               (POS RESULT &rest OVS)
+;; 0 overlays
+(deftest-next-overlay-change-1 A (point-min) (point-max))
+(deftest-next-overlay-change-1 B (point-max) (point-max))
+;; 1 non-empty overlay
+(deftest-next-overlay-change-1 C 1 10 (10 20))
+(deftest-next-overlay-change-1 D 10 20 (10 20))
+(deftest-next-overlay-change-1 E 15 20 (10 20))
+(deftest-next-overlay-change-1 F 20 (point-max) (10 20))
+(deftest-next-overlay-change-1 G 30 (point-max) (10 20))
+;; 1 empty overlay
+(deftest-next-overlay-change-1 H 1 10 (10 10))
+(deftest-next-overlay-change-1 I 10 (point-max) (10 10))
+(deftest-next-overlay-change-1 J 20 (point-max) (10 10))
+;; 2 non-empty, non-intersecting
+(deftest-next-overlay-change-1 D 10 20 (20 30) (40 50))
+(deftest-next-overlay-change-1 E 35 40 (20 30) (40 50))
+(deftest-next-overlay-change-1 F 60 (point-max) (20 30) (40 50))
+(deftest-next-overlay-change-1 G 30 40 (20 30) (40 50))
+(deftest-next-overlay-change-1 H 50 (point-max) (20 30) (40 50))
+;; 2 non-empty, intersecting
+(deftest-next-overlay-change-1 I 10 20 (20 30) (25 35))
+(deftest-next-overlay-change-1 J 20 25 (20 30) (25 35))
+(deftest-next-overlay-change-1 K 23 25 (20 30) (25 35))
+(deftest-next-overlay-change-1 L 25 30 (20 30) (25 35))
+(deftest-next-overlay-change-1 M 28 30 (20 30) (25 35))
+(deftest-next-overlay-change-1 N 30 35 (20 30) (25 35))
+(deftest-next-overlay-change-1 O 35 (point-max) (20 30) (25 35))
+(deftest-next-overlay-change-1 P 50 (point-max) (20 30) (25 35))
+;; 2 non-empty, continuous
+(deftest-next-overlay-change-1 Q 10 20 (20 30) (30 40))
+(deftest-next-overlay-change-1 R 20 30 (20 30) (30 40))
+(deftest-next-overlay-change-1 S 25 30 (20 30) (30 40))
+(deftest-next-overlay-change-1 T 30 40 (20 30) (30 40))
+(deftest-next-overlay-change-1 U 35 40 (20 30) (30 40))
+(deftest-next-overlay-change-1 V 40 (point-max) (20 30) (30 40))
+(deftest-next-overlay-change-1 W 50 (point-max) (20 30) (30 40))
+;; 1 empty, 1 non-empty, non-in
+(deftest-next-overlay-change-1 a 10 20 (20 20) (30 40))
+(deftest-next-overlay-change-1 b 20 30 (20 30) (30 40))
+(deftest-next-overlay-change-1 c 25 30 (20 30) (30 40))
+(deftest-next-overlay-change-1 d 30 40 (20 30) (30 40))
+(deftest-next-overlay-change-1 e 35 40 (20 30) (30 40))
+(deftest-next-overlay-change-1 f 40 (point-max) (20 30) (30 40))
+(deftest-next-overlay-change-1 g 50 (point-max) (20 30) (30 40))
+;; 1 empty, 1 non-empty, intersecting at begin
+(deftest-next-overlay-change-1 h 10 20 (20 20) (20 30))
+(deftest-next-overlay-change-1 i 20 30 (20 20) (20 30))
+(deftest-next-overlay-change-1 j 25 30 (20 20) (20 30))
+(deftest-next-overlay-change-1 k 30 (point-max) (20 20) (20 30))
+(deftest-next-overlay-change-1 l 40 (point-max) (20 20) (20 30))
+;; 1 empty, 1 non-empty, intersecting at end
+(deftest-next-overlay-change-1 h 10 20 (30 30) (20 30))
+(deftest-next-overlay-change-1 i 20 30 (30 30) (20 30))
+(deftest-next-overlay-change-1 j 25 30 (30 30) (20 30))
+(deftest-next-overlay-change-1 k 30 (point-max) (20 20) (20 30))
+(deftest-next-overlay-change-1 l 40 (point-max) (20 20) (20 30))
+;; 1 empty, 1 non-empty, intersecting in the middle
+(deftest-next-overlay-change-1 m 10 20 (25 25) (20 30))
+(deftest-next-overlay-change-1 n 20 25 (25 25) (20 30))
+(deftest-next-overlay-change-1 o 25 30 (25 25) (20 30))
+(deftest-next-overlay-change-1 p 30 (point-max) (25 25) (20 30))
+(deftest-next-overlay-change-1 q 40 (point-max) (25 25) (20 30))
+;; 2 empty, intersecting
+(deftest-next-overlay-change-1 r 10 20 (20 20) (20 20))
+(deftest-next-overlay-change-1 s 20 (point-max) (20 20) (20 20))
+(deftest-next-overlay-change-1 t 30 (point-max) (20 20) (20 20))
+;; 2 empty, non-intersecting
+(deftest-next-overlay-change-1 u 10 20 (20 20) (30 30))
+(deftest-next-overlay-change-1 v 20 30 (20 20) (30 30))
+(deftest-next-overlay-change-1 w 25 30 (20 20) (30 30))
+(deftest-next-overlay-change-1 x 30 (point-max) (20 20) (30 30))
+(deftest-next-overlay-change-1 y 50 (point-max) (20 20) (30 30))
+;; 10 random
+(deftest-next-overlay-change-1 aa 1 5
+  (58 66) (41 10) (9 67) (28 88) (27 43)
+  (24 27) (48 36) (5 90) (61 9))
+(deftest-next-overlay-change-1 ab (point-max) (point-max)
+  (58 66) (41 10) (9 67) (28 88) (27 43)
+  (24 27) (48 36) (5 90) (61 9))
+(deftest-next-overlay-change-1 ac 67 88
+  (58 66) (41 10) (9 67) (28 88) (27 43)
+  (24 27) (48 36) (5 90) (61 9))
+
+
+;; +===================================================================================+
+;; | previous-overlay-change.
+;; +===================================================================================+
+
+;; Same for previous-overlay-change.
+;; 1 non-empty overlay
+(deftest-previous-overlay-change-1 A (point-max) 1)
+(deftest-previous-overlay-change-1 B 1 1)
+(deftest-previous-overlay-change-1 C 1 1 (10 20))
+(deftest-previous-overlay-change-1 D 10 1 (10 20))
+(deftest-previous-overlay-change-1 E 15 10 (10 20))
+(deftest-previous-overlay-change-1 F 20 10 (10 20))
+(deftest-previous-overlay-change-1 G 30 20 (10 20))
+;; 1 empty overlay
+(deftest-previous-overlay-change-1 H 1 1 (10 10))
+(deftest-previous-overlay-change-1 I 10 1 (10 10))
+(deftest-previous-overlay-change-1 J 20 10 (10 10))
+;; 2 non-empty, non-intersecting
+(deftest-previous-overlay-change-1 D 10 1 (20 30) (40 50))
+(deftest-previous-overlay-change-1 E 35 30 (20 30) (40 50))
+(deftest-previous-overlay-change-1 F 60 50 (20 30) (40 50))
+(deftest-previous-overlay-change-1 G 30 20 (20 30) (40 50))
+(deftest-previous-overlay-change-1 H 50 40 (20 30) (40 50))
+;; 2 non-empty, intersecting
+(deftest-previous-overlay-change-1 I 10 1 (20 30) (25 35))
+(deftest-previous-overlay-change-1 J 20 1 (20 30) (25 35))
+(deftest-previous-overlay-change-1 K 23 20 (20 30) (25 35))
+(deftest-previous-overlay-change-1 L 25 20 (20 30) (25 35))
+(deftest-previous-overlay-change-1 M 28 25 (20 30) (25 35))
+(deftest-previous-overlay-change-1 N 30 25 (20 30) (25 35))
+(deftest-previous-overlay-change-1 O 35 30 (20 30) (25 35))
+(deftest-previous-overlay-change-1 P 50 35 (20 30) (25 35))
+;; 2 non-empty, continuous
+(deftest-previous-overlay-change-1 Q 10 1 (20 30) (30 40))
+(deftest-previous-overlay-change-1 R 20 1 (20 30) (30 40))
+(deftest-previous-overlay-change-1 S 25 20 (20 30) (30 40))
+(deftest-previous-overlay-change-1 T 30 20 (20 30) (30 40))
+(deftest-previous-overlay-change-1 U 35 30 (20 30) (30 40))
+(deftest-previous-overlay-change-1 V 40 30 (20 30) (30 40))
+(deftest-previous-overlay-change-1 W 50 40 (20 30) (30 40))
+;; 1 empty, 1 non-empty, non-intersecting
+(deftest-previous-overlay-change-1 a 10 1 (20 20) (30 40))
+(deftest-previous-overlay-change-1 b 20 1 (20 30) (30 40))
+(deftest-previous-overlay-change-1 c 25 20 (20 30) (30 40))
+(deftest-previous-overlay-change-1 d 30 20 (20 30) (30 40))
+(deftest-previous-overlay-change-1 e 35 30 (20 30) (30 40))
+(deftest-previous-overlay-change-1 f 40 30 (20 30) (30 40))
+(deftest-previous-overlay-change-1 g 50 40 (20 30) (30 40))
+;; 1 empty, 1 non-empty, intersecting at begin
+(deftest-previous-overlay-change-1 h 10 1 (20 20) (20 30))
+(deftest-previous-overlay-change-1 i 20 1 (20 20) (20 30))
+(deftest-previous-overlay-change-1 j 25 20 (20 20) (20 30))
+(deftest-previous-overlay-change-1 k 30 20 (20 20) (20 30))
+(deftest-previous-overlay-change-1 l 40 30 (20 20) (20 30))
+;; 1 empty, 1 non-empty, intersecting at end
+(deftest-previous-overlay-change-1 m 10 1 (30 30) (20 30))
+(deftest-previous-overlay-change-1 n 20 1 (30 30) (20 30))
+(deftest-previous-overlay-change-1 o 25 20 (30 30) (20 30))
+(deftest-previous-overlay-change-1 p 30 20 (20 20) (20 30))
+(deftest-previous-overlay-change-1 q 40 30 (20 20) (20 30))
+;; 1 empty, 1 non-empty, intersectig in the middle
+(deftest-previous-overlay-change-1 r 10 1 (25 25) (20 30))
+(deftest-previous-overlay-change-1 s 20 1 (25 25) (20 30))
+(deftest-previous-overlay-change-1 t 25 20 (25 25) (20 30))
+(deftest-previous-overlay-change-1 u 30 25 (25 25) (20 30))
+(deftest-previous-overlay-change-1 v 40 30 (25 25) (20 30))
+;; 2 empty, intersecting
+(deftest-previous-overlay-change-1 w 10 1 (20 20) (20 20))
+(deftest-previous-overlay-change-1 x 20 1 (20 20) (20 20))
+(deftest-previous-overlay-change-1 y 30 20 (20 20) (20 20))
+;; 2 empty, non-intersecting
+(deftest-previous-overlay-change-1 z 10 1 (20 20) (30 30))
+(deftest-previous-overlay-change-1 aa 20 1 (20 20) (30 30))
+(deftest-previous-overlay-change-1 ab 25 20 (20 20) (30 30))
+(deftest-previous-overlay-change-1 ac 30 20 (20 20) (30 30))
+(deftest-previous-overlay-change-1 ad 50 30 (20 20) (30 30))
+;; 10 random
+(deftest-previous-overlay-change-1 ae 100 90
+  (58 66) (41 10) (9 67) (28 88) (27 43)
+  (24 27) (48 36) (5 90) (61 9))
+(deftest-previous-overlay-change-1 af (point-min) (point-min)
+  (58 66) (41 10) (9 67) (28 88) (27 43)
+  (24 27) (48 36) (5 90) (61 9))
+(deftest-previous-overlay-change-1 ag 29 28
+  (58 66) (41 10) (9 67) (28 88) (27 43)
+  (24 27) (48 36) (5 90) (61 9))
+
+
+;; +===================================================================================+
+;; | overlays-at
+;; +===================================================================================+
+
+
+;; Test whether overlay-at returns RESULT at POS after overlays OVL were
+;; created in a buffer.         POS RES OVL
+(deftest-overlays-at-1 A 1 ())
+;; 1 overlay
+(deftest-overlays-at-1 B 10 (a) (a 10 20))
+(deftest-overlays-at-1 C 15 (a) (a 10 20))
+(deftest-overlays-at-1 D 19 (a) (a 10 20))
+(deftest-overlays-at-1 E 20 ()  (a 10 20))
+(deftest-overlays-at-1 F 1 () (a 10 20))
+
+;; 2 non-empty overlays non-intersecting
+(deftest-overlays-at-1 G 1 () (a 10 20) (b 30 40))
+(deftest-overlays-at-1 H 10 (a) (a 10 20) (b 30 40))
+(deftest-overlays-at-1 I 15 (a) (a 10 20) (b 30 40))
+(deftest-overlays-at-1 K 20 () (a 10 20) (b 30 40))
+(deftest-overlays-at-1 L 25 () (a 10 20) (b 30 40))
+(deftest-overlays-at-1 M 30 (b) (a 10 20) (b 30 40))
+(deftest-overlays-at-1 N 35 (b) (a 10 20) (b 30 40))
+(deftest-overlays-at-1 O 40 () (a 10 20) (b 30 40))
+(deftest-overlays-at-1 P 50 () (a 10 20) (b 30 40))
+
+;; 2 non-empty overlays intersecting
+(deftest-overlays-at-1 G 1 () (a 10 30) (b 20 40))
+(deftest-overlays-at-1 H 10 (a) (a 10 30) (b 20 40))
+(deftest-overlays-at-1 I 15 (a) (a 10 30) (b 20 40))
+(deftest-overlays-at-1 K 20 (a b) (a 10 30) (b 20 40))
+(deftest-overlays-at-1 L 25 (a b) (a 10 30) (b 20 40))
+(deftest-overlays-at-1 M 30 (b) (a 10 30) (b 20 40))
+(deftest-overlays-at-1 N 35 (b) (a 10 30) (b 20 40))
+(deftest-overlays-at-1 O 40 () (a 10 30) (b 20 40))
+(deftest-overlays-at-1 P 50 () (a 10 30) (b 20 40))
+
+;; 2 non-empty overlays continuous
+(deftest-overlays-at-1 G 1 () (a 10 20) (b 20 30))
+(deftest-overlays-at-1 H 10 (a) (a 10 20) (b 20 30))
+(deftest-overlays-at-1 I 15 (a) (a 10 20) (b 20 30))
+(deftest-overlays-at-1 K 20 (b) (a 10 20) (b 20 30))
+(deftest-overlays-at-1 L 25 (b) (a 10 20) (b 20 30))
+(deftest-overlays-at-1 M 30 () (a 10 20) (b 20 30))
+
+;; overlays-at never returns empty overlays.
+(deftest-overlays-at-1 N 1 (a) (a 1 60) (c 1 1) (b 30 30) (d 50 50))
+(deftest-overlays-at-1 O 20 (a) (a 1 60) (c 1 1) (b 30 30) (d 50 50))
+(deftest-overlays-at-1 P 30 (a) (a 1 60) (c 1 1) (b 30 30) (d 50 50))
+(deftest-overlays-at-1 Q 40 (a) (a 1 60) (c 1 1) (b 30 30) (d 50 50))
+(deftest-overlays-at-1 R 50 (a) (a 1 60) (c 1 1) (b 30 30) (d 50 50))
+(deftest-overlays-at-1 S 60 () (a 1 60) (c 1 1) (b 30 30) (d 50 50))
+
+;; behaviour at point-min and point-max
+(ert-deftest test-overlays-at-2 ()
+  (cl-macrolet ((should-length (n list)
+                               `(should (= ,n (length ,list)))))
+    (with-temp-buffer
+      (insert (make-string 100 ?\s))
+      (make-overlay 1 (point-max))
+      (make-overlay 10 10)
+      (make-overlay 20 20)
+      (make-overlay (point-max) (point-max))
+      (should-length 1 (overlays-at 1))
+      (should-length 1 (overlays-at 10))
+      (should-length 1 (overlays-at 20))
+      (should-length 0 (overlays-at (point-max)))
+      (narrow-to-region 10 20)
+      (should-length 1 (overlays-at (point-min)))
+      (should-length 1 (overlays-at 15))
+      (should-length 1 (overlays-at (point-max))))))
+
+
+;; +===================================================================================+
+;; | overlay-in
+;; +===================================================================================+
+
+
+;; Test whether overlays-in returns RES in BEG,END after overlays OVL were
+;; created in a buffer.
+
+(deftest-overlays-in-1 A 1 (point-max) ());;POS RES OVL
+;; 1 overlay
+(deftest-overlays-in-1 B 1 10 () (a 10 20))
+(deftest-overlays-in-1 C 5 10 () (a 10 20))
+(deftest-overlays-in-1 D 5 15 (a) (a 10 20))
+(deftest-overlays-in-1 E 10 15 (a)  (a 10 20))
+(deftest-overlays-in-1 F 10 20 (a) (a 10 20))
+(deftest-overlays-in-1 G 15 20 (a) (a 10 20))
+(deftest-overlays-in-1 H 15 25 (a) (a 10 20))
+(deftest-overlays-in-1 I 20 25 () (a 10 20))
+(deftest-overlays-in-1 J 30 50 () (a 10 20))
+
+;; 2 non-empty overlays non-intersecting
+(deftest-overlays-in-1 K 1 5 () (a 10 20) (b 30 40))
+(deftest-overlays-in-1 L 5 10 () (a 10 20) (b 30 40))
+(deftest-overlays-in-1 M 5 15 (a) (a 10 20) (b 30 40))
+(deftest-overlays-in-1 N 10 15 (a) (a 10 20) (b 30 40))
+(deftest-overlays-in-1 O 15 20 (a) (a 10 20) (b 30 40))
+(deftest-overlays-in-1 P 15 25 (a) (a 10 20) (b 30 40))
+(deftest-overlays-in-1 Q 20 25 () (a 10 20) (b 30 40))
+(deftest-overlays-in-1 R 20 30 () (a 10 20) (b 30 40))
+(deftest-overlays-in-1 S 25 30 () (a 10 20) (b 30 40))
+(deftest-overlays-in-1 T 25 35 (b) (a 10 20) (b 30 40))
+(deftest-overlays-in-1 U 30 35 (b) (a 10 20) (b 30 40))
+(deftest-overlays-in-1 V 40 50  () (a 10 20) (b 30 40))
+(deftest-overlays-in-1 W 50 60  () (a 10 20) (b 30 40))
+(deftest-overlays-in-1 X 1 50  (a b) (a 10 20) (b 30 40))
+(deftest-overlays-in-1 Y 10 40  (a b) (a 10 20) (b 30 40))
+(deftest-overlays-in-1 Z 10 41  (a b) (a 10 20) (b 30 40))
+
+;; 2 non-empty overlays intersecting
+(deftest-overlays-in-1 a 1 5 () (a 10 30) (b 20 40))
+(deftest-overlays-in-1 b 5 10 () (a 10 30) (b 20 40))
+(deftest-overlays-in-1 c 5 15 (a) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 d 10 15 (a) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 e 10 20 (a) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 f 15 20 (a) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 g 20 30 (a b) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 h 20 40 (a b) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 i 25 30 (a b) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 j 30 30 (b) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 k 30 35 (b) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 l 35 40 (b) (a 10 30) (b 20 40))
+(deftest-overlays-in-1 m 40 45 () (a 10 30) (b 20 40))
+(deftest-overlays-in-1 n 41 45 () (a 10 30) (b 20 40))
+(deftest-overlays-in-1 o 50 60 () (a 10 30) (b 20 40))
+
+;; 2 non-empty overlays continuous
+(deftest-overlays-in-1 p 1 5 () (a 10 20) (b 20 30))
+(deftest-overlays-in-1 q 5 10 () (a 10 20) (b 20 30))
+(deftest-overlays-in-1 r 15 20 (a) (a 10 20) (b 20 30))
+(deftest-overlays-in-1 s 15 25 (a b) (a 10 20) (b 20 30))
+(deftest-overlays-in-1 t 20 25 (b) (a 10 20) (b 20 30))
+(deftest-overlays-in-1 u 25 30 (b) (a 10 20) (b 20 30))
+(deftest-overlays-in-1 v 29 35 (b) (a 10 20) (b 20 30))
+(deftest-overlays-in-1 w 30 35 () (a 10 20) (b 20 30))
+(deftest-overlays-in-1 x 35 50 () (a 10 20) (b 20 30))
+(deftest-overlays-in-1 y 1 50 (a b) (a 10 20) (b 20 30))
+(deftest-overlays-in-1 z 15 50 (a b) (a 10 20) (b 20 30))
+(deftest-overlays-in-1 aa 1 25 (a b) (a 10 20) (b 20 30))
+
+;; 1 empty overlay
+(deftest-overlays-in-1 ab 1 10 () (a 10 10))
+(deftest-overlays-in-1 ac 10 10 (a) (a 10 10))
+(deftest-overlays-in-1 ad 9 10 () (a 10 10))
+(deftest-overlays-in-1 ae 9 11 (a) (a 10 10))
+(deftest-overlays-in-1 af 10 11 (a) (a 10 10))
+
+
+;; behaviour at point-max
+(ert-deftest test-overlays-in-2 ()
+  (cl-macrolet ((should-length (n list)
+                               `(should (= ,n (length ,list)))))
+    (with-temp-buffer
+      (insert (make-string 100 ?\s))
+      (make-overlay (point-max) (point-max))
+      (make-overlay 50 50)
+      (should-length 1 (overlays-in 50 50))
+      (should-length 2 (overlays-in 1 (point-max)))
+      (should-length 1 (overlays-in (point-max) (point-max)))
+      (narrow-to-region 1 50)
+      (should-length 0 (overlays-in 1 (point-max)))
+      (should-length 1 (overlays-in (point-max) (point-max))))))
+
+
+;; +===================================================================================+
+;; | overlay-recenter
+;; +===================================================================================+
+
+;; This function is a noop in the overlay tree branch.
+(ert-deftest test-overlay-recenter ()
+  (with-temp-buffer
+    (should-not (overlay-recenter 1))
+    (insert (make-string 100 ?\s))
+    (dotimes (i 10)
+      (make-overlay i (1+ i))
+      (should-not (overlay-recenter i)))))
+
+
+;; +===================================================================================+
+;; | move-overlay
+;; +===================================================================================+
+
+;; buffer nil with live overlay
+(ert-deftest test-move-overlay-1 ()
+  (test-with-overlay-in-buffer (ov 1 100)
+                               (move-overlay ov 50 60)
+                               (should (= 50 (overlay-start ov)))
+                               (should (= 60 (overlay-end ov)))
+                               (should (eq (current-buffer) (overlay-buffer ov)))))
+
+;; buffer nil, dead overlay
+(ert-deftest test-move-overlay-2 ()
+  (with-temp-buffer
+    (let ((ov (test-with-overlay-in-buffer (ov 1 100) ov)))
+      (insert (make-string 100 ?\s))
+      (move-overlay ov 50 60)
+      (should (= 50 (overlay-start ov)))
+      (should (= 60 (overlay-end ov)))
+      (should (eq (current-buffer) (overlay-buffer ov))))))
+
+;; buffer non-nil, live overlay
+(ert-deftest test-move-overlay-3 ()
+  (test-with-overlay-in-buffer (ov 10 100)
+                               (with-temp-buffer
+                                 (move-overlay ov 1 1 (current-buffer))
+                                 (should (= 1 (overlay-start ov)))
+                                 (should (= 1 (overlay-end ov)))
+                                 (should (eq (current-buffer) (overlay-buffer ov))))
+                               (should-not (overlay-start ov))
+                               (should-not (overlay-end ov))
+                               (should-not (overlay-buffer ov))))
+
+;; buffer non-nil, dead overlay
+(ert-deftest test-move-overlay-4 ()
+  (let ((ov (test-with-overlay-in-buffer (ov 1 1) ov)))
+    (with-temp-buffer
+      (move-overlay ov 1 1 (current-buffer))
+      (should (= 1 (overlay-start ov)))
+      (should (= 1 (overlay-end ov)))
+      (should (eq (current-buffer) (overlay-buffer ov))))
+    (should-not (overlay-start ov))
+    (should-not (overlay-end ov))
+    (should-not (overlay-buffer ov))))
+
+;; +===================================================================================+
+;; | delete-(all-)overlay
+;; +===================================================================================+
+
+;; delete live overlay
+(ert-deftest test-delete-overlay-1 ()
+  (test-with-overlay-in-buffer (ov 10 100)
+                               (should (buffer-live-p (overlay-buffer ov)))
+                               (delete-overlay ov)
+                               (should-not (overlay-start ov))
+                               (should-not (overlay-end ov))
+                               (should-not (overlay-buffer ov))))
+
+;; delete dead overlay
+(ert-deftest test-delete-overlay-2 ()
+  (let ((ov (test-with-overlay-in-buffer (ov 10 100) ov)))
+    (should-not (overlay-start ov))
+    (should-not (overlay-end ov))
+    (should-not (overlay-buffer ov))
+    (should-not (delete-overlay ov))
+    (should-not (overlay-start ov))
+    (should-not (overlay-end ov))
+    (should-not (overlay-buffer ov))))
+
+(ert-deftest test-delete-all-overlay-1 ()
+  (with-temp-buffer
+    (should-not (delete-all-overlays))
+    (should-not (delete-all-overlays (current-buffer)))
+    (insert (make-string 100 ?\s))
+    (dotimes (i 10) (make-overlay i (1+ i)))
+    (should-not (delete-all-overlays (current-buffer)))
+    (should-not (delete-all-overlays))))
+
+
+;; +===================================================================================+
+;; | get-char-property(-and-overlay)
+;; +===================================================================================+
+
+;; FIXME: TBD
+
+
+;; +===================================================================================+
+;; | Moving by insertions
+;; +===================================================================================+
+
+(defmacro deftest-moving-insert-1 (id beg-end insert sbeg-send fa ra)
+  (cl-destructuring-bind (beg end ipos ilen sbeg send fa ra)
+      (append beg-end insert sbeg-send (list fa ra) nil)
+    `(ert-deftest ,(make-overlay-test-name 'moving-insert 1 id) ()
+       (test-with-overlay-in-buffer (ov ,beg ,end ,fa ,ra)
+                                    (should (= ,beg (overlay-start ov)))
+                                    (should (= ,end (overlay-end ov)))
+                                    (goto-char ,ipos)
+                                    (insert (make-string ,ilen ?x))
+                                    (should (= ,sbeg (overlay-start ov)))
+                                    (should (= ,send (overlay-end ov)))))))
+
+;; non-empty, no fa, no ra
+;; --------------------  OV      INS    RESULT
+(deftest-moving-insert-1 A (10 20) (15 3) (10 23) nil nil)
+(deftest-moving-insert-1 B (10 20) (20 4) (10 20) nil nil)
+(deftest-moving-insert-1 C (10 20) (5 5) (15 25) nil nil)
+(deftest-moving-insert-1 D (10 20) (10 3) (10 23) nil nil)
+(deftest-moving-insert-1 E (10 20) (20 4) (10 20) nil nil)
+
+;; non-empty no fa, ra
+(deftest-moving-insert-1 F (10 20) (15 3) (10 23) nil t)
+(deftest-moving-insert-1 G (10 20) (20 4) (10 24) nil t)
+(deftest-moving-insert-1 H (10 20) (5 5) (15 25) nil t)
+(deftest-moving-insert-1 I (10 20) (10 3) (10 23) nil t)
+(deftest-moving-insert-1 J (10 20) (20 4) (10 24) nil t)
+
+;; non-empty, fa, no r
+(deftest-moving-insert-1 K (10 20) (15 3) (10 23) t nil)
+(deftest-moving-insert-1 L (10 20) (20 4) (10 20) t nil)
+(deftest-moving-insert-1 M (10 20) (5 5) (15 25) t nil)
+(deftest-moving-insert-1 N (10 20) (10 3) (13 23) t nil)
+(deftest-moving-insert-1 O (10 20) (20 4) (10 20) t nil)
+
+;; This used to fail.
+(ert-deftest test-moving-insert-2-a ()
+  (with-temp-buffer
+    (insert (make-string 1 ?.))
+    (let ((ov (make-overlay 1 1 nil t nil)))
+      (insert "()")
+      (should (= 1 (overlay-end ov))))))
+
+;; non-empty, fa, ra
+(deftest-moving-insert-1 P (10 20) (15 3) (10 23) t t)
+(deftest-moving-insert-1 Q (10 20) (20 4) (10 24) t t)
+(deftest-moving-insert-1 R (10 20) (5 5) (15 25) t t)
+(deftest-moving-insert-1 S (10 20) (10 3) (13 23) t t)
+(deftest-moving-insert-1 T (10 20) (20 4) (10 24) t t)
+
+;; empty, no fa, no ra
+(deftest-moving-insert-1 U (15 15) (20 4) (15 15) nil nil)
+(deftest-moving-insert-1 V (15 15) (5 5) (20 20) nil nil)
+(deftest-moving-insert-1 W (15 15) (15 3) (15 15) nil nil)
+
+;; empty no fa, ra
+(deftest-moving-insert-1 X (15 15) (20 4) (15 15) nil t)
+(deftest-moving-insert-1 Y (15 15) (5 5) (20 20) nil t)
+(deftest-moving-insert-1 Z (15 15) (15 3) (15 18) nil t)
+
+;; empty, fa, no ra
+(deftest-moving-insert-1 a (15 15) (20 4) (15 15) t nil)
+(deftest-moving-insert-1 b (15 15) (5 5) (20 20) t nil)
+(deftest-moving-insert-1 c (15 15) (15 3) (15 15) t nil)
+
+;; empty, fa, ra
+(deftest-moving-insert-1 d (15 15) (20 4) (15 15) t t)
+(deftest-moving-insert-1 e (15 15) (5 5) (20 20) t t)
+(deftest-moving-insert-1 f (15 15) (15 3) (18 18) t t)
+
+;; Try to trigger a pathological case where the tree could become
+;; unordered due to an insert operation.
+
+(ert-deftest test-moving-insert-2 ()
+  (with-temp-buffer
+    (insert (make-string 1000 ?x))
+    (let ((root (make-overlay 50 75 nil    nil             'rear-advance))
+          (left (make-overlay 25 50 nil    'front-advance  'rear-advance))
+          (right (make-overlay 75 100 nil  nil             nil)))
+      ;;     [50] <--- start
+      ;;    /    \
+      ;; (25)    (75)
+      (delete-region 25 75)
+      ;;     [25]
+      ;;    /    \
+      ;; (25)    (25)
+      (should (= 25 (overlay-start root)))
+      (should (= 25 (overlay-end root)))
+      (should (= 25 (overlay-start left)))
+      (should (= 25 (overlay-end left)))
+      (should (= 25 (overlay-start right)))
+      (should (= 50 (overlay-end right)))
+      ;; Inserting at start should make left advance while right and
+      ;; root stay, thus we would have left > right .
+      (goto-char 25)
+      (insert (make-string 25 ?x))
+      ;;     [25]
+      ;;    /    \
+      ;; (50)    (25)
+      (should (= 25 (overlay-start root)))
+      (should (= 50 (overlay-end root)))
+      (should (= 50 (overlay-start left)))
+      (should (= 50 (overlay-end left)))
+      (should (= 25 (overlay-start right)))
+      (should (= 75 (overlay-end right)))
+      ;; Try to detect the error, by removing left.  The should fail
+      ;; an eassert, since it won't be found by a reular tree
+      ;; traversal - in theory.
+      (delete-overlay left)
+      (should (= 2 (length (overlays-in 1 (point-max))))))))
+
+
+
+;; +===================================================================================+
+;; | Moving by deletions
+;; +===================================================================================+
+
+(defmacro deftest-moving-delete-1 (id beg-end delete sbeg-send fa ra)
+  (cl-destructuring-bind (beg end dpos dlen sbeg send fa ra)
+      (append beg-end delete sbeg-send (list fa ra) nil)
+    `(ert-deftest ,(make-overlay-test-name 'moving-delete 1 id) ()
+       (test-with-overlay-in-buffer (ov ,beg ,end ,fa ,ra)
+                                    (should (= ,beg (overlay-start ov)))
+                                    (should (= ,end (overlay-end ov)))
+                                    (delete-region ,dpos (+ ,dpos ,dlen))
+                                    (should (= ,sbeg (overlay-start ov)))
+                                    (should (= ,send (overlay-end ov)))))))
+
+;; non-empty, no fa, no ra
+;; --------------------  OV      DEL    RESULT
+(deftest-moving-delete-1 A (10 20) (15 3) (10 17) nil nil)
+(deftest-moving-delete-1 B (10 20) (20 4) (10 20) nil nil)
+(deftest-moving-delete-1 C (10 20) (5 5) (5 15) nil nil)
+(deftest-moving-delete-1 D (10 20) (10 3) (10 17) nil nil)
+(deftest-moving-delete-1 E (10 20) (20 4) (10 20) nil nil)
+
+;; non-empty no fa, ra
+(deftest-moving-delete-1 F (10 20) (15 3) (10 17) nil t)
+(deftest-moving-delete-1 G (10 20) (20 4) (10 20) nil t)
+(deftest-moving-delete-1 H (10 20) (5 5) (5 15) nil t)
+(deftest-moving-delete-1 I (10 20) (10 3) (10 17) nil t)
+(deftest-moving-delete-1 J (10 20) (20 4) (10 20) nil t)
+
+;; non-empty, fa, no ra
+(deftest-moving-delete-1 K (10 20) (15 3) (10 17) t nil)
+(deftest-moving-delete-1 L (10 20) (20 4) (10 20) t nil)
+(deftest-moving-delete-1 M (10 20) (5 5) (5 15) t nil)
+(deftest-moving-delete-1 N (10 20) (10 3) (10 17) t nil)
+(deftest-moving-delete-1 O (10 20) (20 4) (10 20) t nil)
+
+;; non-empty, fa, ra
+(deftest-moving-delete-1 P (10 20) (15 3) (10 17) t t)
+(deftest-moving-delete-1 Q (10 20) (20 4) (10 20) t t)
+(deftest-moving-delete-1 R (10 20) (5 5) (5 15) t t)
+(deftest-moving-delete-1 S (10 20) (10 3) (10 17) t t)
+(deftest-moving-delete-1 T (10 20) (20 4) (10 20) t t)
+
+;; empty, no fa, no ra
+(deftest-moving-delete-1 U (15 15) (20 4) (15 15) nil nil)
+(deftest-moving-delete-1 V (15 15) (5 5) (10 10) nil nil)
+(deftest-moving-delete-1 W (15 15) (15 3) (15 15) nil nil)
+
+;; empty no fa, ra
+(deftest-moving-delete-1 X (15 15) (20 4) (15 15) nil t)
+(deftest-moving-delete-1 Y (15 15) (5 5) (10 10) nil t)
+(deftest-moving-delete-1 Z (15 15) (15 3) (15 15) nil t)
+
+;; empty, fa, no ra
+(deftest-moving-delete-1 a (15 15) (20 4) (15 15) t nil)
+(deftest-moving-delete-1 b (15 15) (5 5) (10 10) t nil)
+(deftest-moving-delete-1 c (15 15) (15 3) (15 15) t nil)
+
+;; empty, fa, ra
+(deftest-moving-delete-1 d (15 15) (20 4) (15 15) t t)
+(deftest-moving-delete-1 e (15 15) (5 5) (10 10) t t)
+(deftest-moving-delete-1 f (15 15) (15 3) (15 15) t t)
+
+
+;; +===================================================================================+
+;; | make-indirect-buffer
+;; +===================================================================================+
+
+;; Check if overlays are cloned/seperate from indirect buffer.
+(ert-deftest test-make-indirect-buffer-1 ()
+  (with-temp-buffer
+    (dotimes (_ 10) (make-overlay 1 1))
+    (let (indirect clone)
+      (unwind-protect
+          (progn
+            (setq indirect (make-indirect-buffer
+                            (current-buffer) "indirect"))
+            (with-current-buffer indirect
+              (should-not (overlays-in (point-min) (point-max)))
+              (dotimes (_ 20) (make-overlay 1 1))
+              (should (= 20 (length (overlays-in (point-min) (point-max)))))
+              (delete-all-overlays)
+              (should-not (overlays-in (point-min) (point-max))))
+            (should (= 10 (length (overlays-in (point-min) (point-max)))))
+            (setq clone (make-indirect-buffer
+                         (current-buffer) "clone" 'clone))
+            (with-current-buffer clone
+              (should (= 10 (length (overlays-in (point-min) (point-max)))))
+              (dotimes (_ 30) (make-overlay 1 1))
+              (should (= 40 (length (overlays-in (point-min) (point-max))))))
+            ;; back in temp buffer
+            (should (= 10 (length (overlays-in (point-min) (point-max)))))
+            (with-current-buffer clone
+              (mapc #'delete-overlay
+                    (seq-take (overlays-in (point-min) (point-max)) 10))
+              (should (= 30 (length (overlays-in (point-min) (point-max))))))
+            (should (= 10 (length (overlays-in (point-min) (point-max)))))
+            (delete-all-overlays)
+            (with-current-buffer clone
+              (should (= 30 (length (overlays-in (point-min) (point-max)))))))
+        (when (buffer-live-p clone)
+          (kill-buffer clone))
+        (when (buffer-live-p indirect)
+          (kill-buffer indirect))))))
+
+
+
+;; +===================================================================================+
+;; | buffer-swap-text
+;; +===================================================================================+
+
+(defmacro test-with-temp-buffers (vars &rest body)
+  (declare (indent 1) (debug (sexp &rest form)))
+  (if (null vars)
+      `(progn ,@body)
+    `(with-temp-buffer
+       (let ((,(car vars) (current-buffer)))
+         (test-with-temp-buffers ,(cdr vars) ,@body)))))
+
+;; basic
+(ert-deftest test-buffer-swap-text-1 ()
+  (test-with-temp-buffers (buffer other)
+                          (with-current-buffer buffer
+                            (let ((ov (make-overlay 1 1)))
+                              (buffer-swap-text other)
+                              (should-not (overlays-in 1 1))
+                              (with-current-buffer other
+                                (should (overlays-in 1 1))
+                                (should (eq ov (car (overlays-in 1 1)))))))))
+
+;; properties
+(ert-deftest test-buffer-swap-text-1 ()
+  (test-with-temp-buffers (buffer other)
+                          (with-current-buffer other
+                            (overlay-put (make-overlay 1 1) 'buffer 'other))
+                          (with-current-buffer buffer
+                            (overlay-put (make-overlay 1 1) 'buffer 'buffer)
+                            (buffer-swap-text other)
+                            (should (= 1 (length (overlays-in 1 1))))
+                            (should (eq (overlay-get (car (overlays-in 1 1)) 'buffer) 'other)))
+                          (with-current-buffer other
+                            (should (= 1 (length (overlays-in 1 1))))
+                            (should (eq (overlay-get (car (overlays-in 1 1)) 'buffer) 'buffer)))))
+
+
+;; +===================================================================================+
+;; | priorities
+;; +===================================================================================+
+
+(ert-deftest test-overlay-priorities-1 ()
+  (with-temp-buffer
+    (insert " ")
+    (dotimes (i 10)
+      (let ((ov (make-overlay 1 2)))
+        (overlay-put ov 'priority i)
+        (overlay-put ov 'value i)))
+    (should (eq 9 (get-char-property 1 'value)))))
+
+(ert-deftest test-overlay-priorities-2 ()
+  (with-temp-buffer
+    (insert " ")
+    (dotimes (j 10)
+      (let* ((i (- 9 j))
+             (ov (make-overlay 1 2)))
+        (overlay-put ov 'priority i)
+        (overlay-put ov 'value i)))
+    (should (eq 9 (get-char-property 1 'value)))))
+
+
+;; +===================================================================================+
+;; | Other
+;; +===================================================================================+
+
+(defun test-overlay-regions ()
+  (sort (mapcar (lambda (ov)
+                  (cons (overlay-start ov)
+                        (overlay-end ov)))
+                (overlays-in (point-min)
+                             (point-max)))
+        (lambda (o1 o2)
+          (or (< (car o1) (car o2))
+              (and (= (car o1) (car o2))
+                   (< (cdr o1) (cdr o2)))))))
+
+;; This test used to fail.
+(ert-deftest overlay-complex-delete-with-offset ()
+  (with-temp-buffer
+    (let (todelete)
+      (insert (make-string 1000 ?\s))
+      (make-overlay 1 2 nil t nil)
+      (make-overlay 2 3 nil t nil)
+      (make-overlay 3 4 nil t nil)
+      (make-overlay 4 5 nil t nil)
+      (setq todelete (make-overlay 280 287 nil t nil))
+      (make-overlay 265 275 nil t nil)
+      (make-overlay 329 386 nil t nil)
+      (make-overlay 386 390 nil t nil)
+      (goto-char 50)
+      (delete-char 50)
+      (goto-char 1)
+      (delete-char 2)
+      (delete-overlay todelete)
+      (should (equal (test-overlay-regions)
+                     '((1 . 1) (1 . 1) (1 . 2) (2 . 3) (213 . 223) (277 . 334) (334 . 338)))))))
+
+;; This test used to fail.
+(ert-deftest overlay-complex-insert-1 ()
+  (with-temp-buffer
+    (insert "          ")
+    (make-overlay 8 11 nil nil t)
+    (make-overlay 2 7 nil nil nil)
+    (make-overlay 2 4 nil t nil)
+    (goto-char 1)
+    (insert "     ")
+    (should (equal (test-overlay-regions)
+                   '((7 . 9)
+                     (7 . 12)
+                     (13 . 16))))))
+
+;; This test used to fail.
+(ert-deftest overlay-complex-insert-2 ()
+  (with-temp-buffer
+    (insert (make-string 100 ?\s))
+    (make-overlay 77 7 nil nil t)
+    (make-overlay 21 53 nil t t)
+    (make-overlay 84 14 nil nil nil)
+    (make-overlay 38 69 nil t nil)
+    (make-overlay 93 15 nil nil t)
+    (make-overlay 73 48 nil t t)
+    (make-overlay 96 51 nil t t)
+    (make-overlay 6 43 nil t t)
+    (make-overlay 15 100 nil t t)
+    (make-overlay 22 17 nil nil nil)
+    (make-overlay 72 45 nil t nil)
+    (make-overlay 2 74 nil nil t)
+    (make-overlay 15 29 nil t t)
+    (make-overlay 17 34 nil t t)
+    (make-overlay 101 66 nil t nil)
+    (make-overlay 94 24 nil nil nil)
+    (goto-char 78)
+    (insert "           ")
+    (narrow-to-region 47 19)
+    (goto-char 46)
+    (widen)
+    (narrow-to-region 13 3)
+    (goto-char 9)
+    (delete-char 0)
+    (goto-char 11)
+    (insert "           ")
+    (goto-char 3)
+    (insert "          ")
+    (goto-char 8)
+    (insert "       ")
+    (goto-char 26)
+    (insert "  ")
+    (goto-char 14)
+    (widen)
+    (narrow-to-region 71 35)
+    (should
+     (equal (test-overlay-regions)
+            '((2 . 104)
+              (23 . 73)
+              (24 . 107)
+              (44 . 125)
+              (45 . 59)
+              (45 . 134)
+              (45 . 141)
+              (47 . 52)
+              (47 . 64)
+              (51 . 83)
+              (54 . 135)
+              (68 . 99))))))
+
+(ert-deftest test-overlay-multibyte-transition-1 ()
+  (with-temp-buffer
+    (set-buffer-multibyte t)
+    (insert "ääää")
+    ;; aeaeaeae
+    ;; 1 2 3 4 5
+    ;; 123456789
+    (let ((nonempty-bob (make-overlay 1 2))
+          (empty-bob    (make-overlay 1 1))
+          (empty        (make-overlay 2 2))
+          (nonempty     (make-overlay 2 4))
+          (nonempty-eob (make-overlay 4 5))
+          (empty-eob    (make-overlay 5 5)))
+      (set-buffer-multibyte nil)
+      (cl-macrolet ((ovshould (ov begin end)
+                              `(should (equal (list (overlay-start ,ov) (overlay-end ,ov))
+                                              (list ,begin ,end)))))
+        (ovshould nonempty-bob 1 3)
+        (ovshould empty-bob    1 1)
+        (ovshould empty        3 3)
+        (ovshould nonempty     3 7)
+        (ovshould nonempty-eob 7 9)
+        (ovshould empty-eob    9 9)))))
+
+(ert-deftest test-overlay-multibyte-transition-2 ()
+  (with-temp-buffer
+    (set-buffer-multibyte t)
+    (insert "ääää")
+    (set-buffer-multibyte nil)
+    ;; aeaeaeae
+    ;; 1 2 3 4 5
+    ;; 123456789
+    (let ((nonempty-bob-end (make-overlay 1 2))
+          (nonempty-bob-beg (make-overlay 1 3))
+          (empty-bob        (make-overlay 1 1))
+          (empty-beg        (make-overlay 3 3))
+          (empty-end        (make-overlay 2 2))
+          (nonempty-beg-beg (make-overlay 3 7))
+          (nonempty-beg-end (make-overlay 3 8))
+          (nonempty-end-beg (make-overlay 4 7))
+          (nonempty-end-end (make-overlay 4 8))
+          (nonempty-eob-beg (make-overlay 5 9))
+          (nonempty-eob-end (make-overlay 6 9))
+          (empty-eob        (make-overlay 9 9)))
+      (set-buffer-multibyte t)
+      (cl-macrolet ((ovshould (ov begin end)
+                              `(should (equal (list (overlay-start ,ov) (overlay-end ,ov))
+                                              (list ,begin ,end)))))
+        (ovshould nonempty-bob-end 1 2)
+        (ovshould nonempty-bob-beg 1 2)
+        (ovshould empty-bob        1 1)
+        (ovshould empty-beg        2 2)
+        (ovshould empty-end        2 2)
+        (ovshould nonempty-beg-beg 2 4)
+        (ovshould nonempty-beg-end 2 5)
+        (ovshould nonempty-end-beg 3 4)
+        (ovshould nonempty-end-end 3 5)
+        (ovshould nonempty-eob-beg 3 5)
+        (ovshould nonempty-eob-end 4 5)
+        (ovshould empty-eob        5 5)))))
+
 ;;; buffer-tests.el ends here

Re: The overlay branch (yet again)

[Vladimir Kazanov]

a gentle reminder :-)

On Wed, Dec 4, 2019 at 11:41 AM Vladimir Kazanov <vekazanov@gmail.com> wrote:
>
> So here's the first patch containing a few hundred (!!!)
> implementation-agnostic overlay tests.
>
> I took all Lisp-level overlay related tests in the feature-noverlay
> branch, removed automatically generated ones and a single test that
> was aware of the tree-based implementation. This should be a good
> basis for any further work related to overlays (and buffers in
> general).
>
> I did not add a single line of code, all credit goes to Andreas.
>
> Feel free to request tweaks and additions. Note that I am still in the
> process of pushing the papers through corporate bureaucracy. No
> problems, I got all the approvals needed but it'll take a week or two
> more.
>
> Thanks
>
> On Tue, Dec 3, 2019 at 10:43 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> >
> > > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00488.html
> > > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00598.html
> > > https://lists.gnu.org/archive/html/emacs-devel/2017-02/msg00736.html
> >
> > At least those links should be in comments somewhere in the code.
> >
> >
> >         Stefan
> >
>
>
> --
> Yours sincerely,
>
>
> Vladimir Kazanov
>
>
> --
> С уважением,
>
> Владимир Казанов



-- 
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Re: The overlay branch (yet again)

[Eli Zaretskii]

> From: Vladimir Kazanov <vekazanov@gmail.com>
> Date: Thu, 5 Dec 2019 14:13:30 +0000
> Cc: martin rudalics <rudalics@gmx.at>, emacs-devel@gnu.org
> 
> a gentle reminder :-)

Please wait for a while longer.  It takes time here to process
patches, and at least I personally like to leave them for a few days
before pushing, so that others could have an opportunity to read and
comment.

Also, do I understand that this is all work by Andreas?  The patches
have no log message (something that we normally ask for providing), so
the authorship is unclear.

Thanks.

Re: The overlay branch (yet again)

[Vladimir Kazanov]

Eli,

oops, sorry.

> Also, do I understand that this is all work by Andreas?

Yes, the code is by Andreas. I only removed some of the
irrelevant/temporary tests. He dumped most of it into the
features/noverlay branch in a single commit containing both tests and
main code. So I had to extract things manually.

> (something that we normally ask for providing)

Would something like using the default "git format-patch" format work..?

Thanks


On Thu, Dec 5, 2019 at 3:14 PM Eli Zaretskii <eliz@gnu.org> wrote:
>
> > From: Vladimir Kazanov <vekazanov@gmail.com>
> > Date: Thu, 5 Dec 2019 14:13:30 +0000
> > Cc: martin rudalics <rudalics@gmx.at>, emacs-devel@gnu.org
> >
> > a gentle reminder :-)
>
> Please wait for a while longer.  It takes time here to process
> patches, and at least I personally like to leave them for a few days
> before pushing, so that others could have an opportunity to read and
> comment.
>
> Also, do I understand that this is all work by Andreas?  The patches
> have no log message (something that we normally ask for providing), so
> the authorship is unclear.
>
> Thanks.



-- 
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Re: The overlay branch (yet again)

[Eli Zaretskii]

> From: Vladimir Kazanov <vekazanov@gmail.com>
> Date: Thu, 5 Dec 2019 15:31:12 +0000
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, martin rudalics <rudalics@gmx.at>, emacs-devel@gnu.org
> 
> Would something like using the default "git format-patch" format work..?

It would, but how would you produce such a patch if there's a single
commit on the branch, which mixes these changes with others?

Re: The overlay branch (yet again)

[Vladimir Kazanov]

On Thu, Dec 5, 2019 at 4:38 PM Eli Zaretskii <eliz@gnu.org> wrote:
> It would, but how would you produce such a patch if there's a single
> commit on the branch, which mixes these changes with others?

I wouldn't, at least not this time. But I already have a second patch
in the works, and I really want it to be usable the way I send it..

Stefan already merged the patch, by the way. Nice!


--
Yours sincerely,


Vladimir Kazanov


--
С уважением,

Владимир Казанов

Re: The overlay branch (yet again)

[Vladimir Kazanov]

[-- Attachment #1: Type: text/plain, Size: 1832 bytes --]

Hello again!

I did another dive into the feature/noverlay branch this weekend. It
turns out that apart from the Lisp-level overlay unit tests Andreas
also developed a very nice benchmarking suite, making it easy to
compare implementations. In fact, all the benchmarking results he
reported in the mailing list are included already.

Benchmarking code contains numerous synthetic performance tests, a
replication of performance issues reported with Flycheck and line
numbering using overlays. I wanted to come up with my own benchmarks
but the job was already done. The code is included in the
test/manual/noverlay directory and a convenient Makefile is provided.
Running the complete suite against master took about 20 minutes on my
machine, mostly due to those overlay linked lists being slow.

I've cleaned the code a bit by removing external dependencies and only
including a subset of what was provided in Makefile. I did not so any
formatting improvements to make sure it's not tainted with my code.

Stefan, could you also include the patch in master? My feeling is that
it might be very useful to anybody working on overlay code.

On Fri, Dec 6, 2019 at 6:48 AM Vladimir Kazanov <vekazanov@gmail.com> wrote:
>
> On Thu, Dec 5, 2019 at 4:38 PM Eli Zaretskii <eliz@gnu.org> wrote:
> > It would, but how would you produce such a patch if there's a single
> > commit on the branch, which mixes these changes with others?
>
> I wouldn't, at least not this time. But I already have a second patch
> in the works, and I really want it to be usable the way I send it..
>
> Stefan already merged the patch, by the way. Nice!
>
>
> --
> Yours sincerely,
>
>
> Vladimir Kazanov
>
>
> --
> С уважением,
>
> Владимир Казанов



-- 
Regards,

Vladimir Kazanov

[-- Attachment #2: include-overlay-benchmarks.patch --]
[-- Type: text/x-patch, Size: 75455 bytes --]

diff --git a/configure.ac b/configure.ac
index 3b6a2a6d16..22aae5894f 100644
--- a/configure.ac
+++ b/configure.ac
@@ -5777,6 +5777,7 @@ m4_define
   dnl Again, it's best not to use a variable.  Though you can add
   dnl ", [], [opt_makefile='$opt_makefile']" and it should work.
   AC_CONFIG_FILES([test/Makefile])
+  AC_CONFIG_FILES([test/manual/noverlay/Makefile])
 fi
 
 
diff --git a/test/manual/noverlay/Makefile.in b/test/manual/noverlay/Makefile.in
new file mode 100644
index 0000000000..35f898e5dc
--- /dev/null
+++ b/test/manual/noverlay/Makefile.in
@@ -0,0 +1,12 @@
+top_srcdir = @top_srcdir@
+EMACS ?= ../../../src/emacs
+
+.PHONY: all
+
+all: perf
+
+perf:
+	-$(EMACS) -Q -l ./overlay-perf.el -f perf-run-batch
+
+distclean:
+	rm -f -- Makefile
diff --git a/test/manual/noverlay/many-errors.py b/test/manual/noverlay/many-errors.py
new file mode 100644
index 0000000000..fa4ef5f98d
--- /dev/null
+++ b/test/manual/noverlay/many-errors.py
@@ -0,0 +1,2480 @@
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
+def a(x, y, y):
+    return t; pass
diff --git a/test/manual/noverlay/overlay-perf.el b/test/manual/noverlay/overlay-perf.el
new file mode 100644
index 0000000000..6706a0af8a
--- /dev/null
+++ b/test/manual/noverlay/overlay-perf.el
@@ -0,0 +1,764 @@
+;; -*- lexical-binding:t -*-
+(require 'cl-lib)
+(require 'subr-x)
+(require 'seq)
+(require 'hi-lock)
+
+
+;; +===================================================================================+
+;; | Framework
+;; +===================================================================================+
+
+(defmacro perf-define-constant-test (name &optional doc &rest body)
+  (declare (indent 1) (debug (symbol &optional string &rest form)))
+  `(progn
+     (put ',name 'perf-constant-test t)
+     (defun ,name nil ,doc ,@body)))
+
+(defmacro perf-define-variable-test (name args &optional doc &rest body)
+  (declare (indent 2) (debug defun))
+  (unless (and (consp args)
+               (= (length args) 1))
+    (error "Function %s should accept exactly one argument." name))
+  `(progn
+     (put ',name 'perf-variable-test t)
+     (defun ,name ,args ,doc ,@body)))
+
+(defmacro perf-define-test-suite (name &rest tests)
+  (declare (indent 1))
+  `(put ',name 'perf-test-suite
+        ,(cons 'list tests)))
+
+(defun perf-constant-test-p (test)
+  (get test 'perf-constant-test))
+
+(defun perf-variable-test-p (test)
+  (get test 'perf-variable-test))
+
+(defun perf-test-suite-p (suite)
+  (not (null (perf-test-suite-elements suite))))
+
+(defun perf-test-suite-elements (suite)
+  (get suite 'perf-test-suite))
+
+(defun perf-expand-suites (test-and-suites)
+  (apply #' append (mapcar (lambda (elt)
+                             (if (perf-test-suite-p elt)
+                                 (perf-test-suite-elements elt)
+                               (list elt)))
+                           test-and-suites)))
+(defun perf-test-p (symbol)
+  (or (perf-variable-test-p symbol)
+      (perf-constant-test-p symbol)))
+
+(defun perf-all-tests ()
+  (let (result)
+    (mapatoms (lambda (symbol)
+                (when (and (fboundp symbol)
+                           (perf-test-p symbol))
+                  (push symbol result))))
+    (sort result #'string-lessp)))
+
+(defvar perf-default-test-argument 4096)
+
+(defun perf-run-1 (&optional k n &rest tests)
+  "Run TESTS K times using N as argument for non-constant ones.
+
+Return test-total elapsed time."
+  (random "")
+  (when (and n (not (numberp n)))
+    (push k tests)
+    (push n tests)
+    (setq n nil k nil))
+  (when (and k (not (numberp k)))
+    (push k tests)
+    (setq k nil))
+  (let* ((k (or k 1))
+         (n (or n perf-default-test-argument))
+         (tests (perf-expand-suites (or tests
+                                        (perf-all-tests))))
+         (variable-tests (seq-filter #'perf-variable-test-p tests))
+         (constant-tests (seq-filter #'perf-constant-test-p tests))
+         (max-test-string-width (perf-max-symbol-length tests)))
+    (unless (seq-every-p #'perf-test-p tests)
+      (error "Some of these are not tests: %s" tests))
+    (cl-labels ((format-result (result)
+                  (cond
+                   ((numberp result) (format "%.2f" result))
+                   ((stringp result) result)
+                   ((null result) "N/A")))
+                (format-test (fn)
+                  (concat (symbol-name fn)
+                          (make-string
+                           (+ (- max-test-string-width
+                                 (length (symbol-name fn)))
+                              1)
+                           ?\s)))
+                (format-summary (results _total)
+                  (let ((min (apply #'min results))
+                        (max (apply #'max results))
+                        (avg (/ (apply #'+ results) (float (length results)))))
+                    (format "n=%d min=%.2f avg=%.2f max=%.2f" (length results) min avg max)))
+                (run-test (fn)
+                  (let ((total 0) results)
+                    (dotimes (_ (max 0 k))
+                      (garbage-collect)
+                      (princ (concat " " (format-test fn)))
+                      (let ((result  (condition-case-unless-debug err
+                                         (cond
+                                          ((perf-variable-test-p fn)
+                                           (random "") (car (funcall fn n)))
+                                          ((perf-constant-test-p fn)
+                                           (random "") (car (funcall fn)))
+                                          (t "skip"))
+                                       (error (error-message-string err)))))
+                        (when (numberp result)
+                          (cl-incf total result)
+                          (push result results))
+                        (princ (format-result result))
+                        (terpri)))
+                    (when (> (length results) 1)
+                      (princ (concat "#" (format-test fn)
+                                     (format-summary results total)))
+                      (terpri)))))
+      (when variable-tests
+        (terpri)
+        (dolist (fn variable-tests)
+          (run-test fn)
+          (terpri)))
+      (when constant-tests
+        (dolist (fn constant-tests)
+          (run-test fn)
+          (terpri))))))
+
+(defun perf-run (&optional k n &rest tests)
+  (interactive
+   (let* ((n (if current-prefix-arg
+                 (prefix-numeric-value current-prefix-arg)
+               perf-default-test-argument))
+          (tests (mapcar #'intern
+                         (completing-read-multiple
+                          (format "Run tests (n=%d): " n)
+                          (perf-all-tests) nil t nil 'perf-test-history))))
+     (cons 1 (cons n tests))))
+  (with-current-buffer (get-buffer-create "*perf-results*")
+    (let ((inhibit-read-only t)
+          (standard-output (current-buffer)))
+      (erase-buffer)
+      (apply #'perf-run-1 k n tests)
+      (display-buffer (current-buffer)))))
+
+
+(defun perf-batch-parse-command-line (args)
+  (let ((k 1)
+        (n perf-default-test-argument)
+        tests)
+    (while args
+      (cond ((string-match-p "\\`-[cn]\\'" (car args))
+             (unless (and (cdr args)
+                          (string-match-p "\\`[0-9]+\\'" (cadr args)))
+               (error "%s expectes a natnum argument" (car args)))
+             (if (equal (car args) "-c")
+                 (setq k (string-to-number (cadr args)))
+               (setq n (string-to-number (cadr args))))
+             (setq args (cddr args)))
+            (t (push (intern (pop args)) tests))))
+    (list k n tests)))
+
+
+(defun perf-run-batch ()
+  "Runs tests from `command-line-args-left' and kill emacs."
+  (let ((standard-output #'external-debugging-output))
+    (condition-case err
+        (cl-destructuring-bind (k n tests)
+            (perf-batch-parse-command-line command-line-args-left)
+          (apply #'perf-run-1 k n tests)
+          (save-buffers-kill-emacs))
+      (error
+       (princ (error-message-string err))
+       (save-buffers-kill-emacs)))))
+
+(defconst perf-number-of-columns 70)
+
+(defun perf-insert-lines (n)
+  "Insert N lines into the current buffer."
+  (dotimes (i n)
+    (insert (make-string 70 (if (= (% i 2) 0)
+                                ?.
+                              ?O))
+            ?\n)))
+
+(defun perf-switch-to-buffer-scroll-random (n &optional buffer)
+  (interactive)
+  (set-window-buffer nil (or buffer (current-buffer)))
+  (goto-char (point-min))
+  (redisplay t)
+  (dotimes (_ n)
+    (goto-char (random (point-max)))
+    (recenter)
+    (redisplay t)))
+
+(defun perf-insert-overlays (n &optional create-callback random-p)
+  (if random-p
+      (perf-insert-overlays-random n create-callback)
+    (perf-insert-overlays-sequential n create-callback)))
+
+(defun perf-insert-overlays-sequential (n &optional create-callback)
+  "Insert an overlay every Nth line."
+  (declare (indent 1))
+  (let ((i 0)
+        (create-callback (or create-callback #'ignore)))
+    (save-excursion
+      (goto-char (point-min))
+      (while (not (eobp))
+        (when (= 0 (% i n))
+          (let ((ov (make-overlay (point-at-bol) (point-at-eol))))
+            (funcall create-callback ov)
+            (overlay-put ov 'priority (random (buffer-size)))))
+        (cl-incf i)
+        (forward-line)))))
+
+(defun perf-insert-overlays-random (n &optional create-callback)
+  "Insert an overlay every Nth line."
+  (declare (indent 1))
+  (let ((create-callback (or create-callback #'ignore)))
+    (save-excursion
+      (while (>= (cl-decf n) 0)
+        (let* ((beg (1+ (random (point-max))))
+               (ov (make-overlay beg (+ beg (random 70)))))
+          (funcall create-callback ov)
+          (overlay-put ov 'priority (random (buffer-size))))))))
+
+(defun perf-insert-overlays-hierarchical (n &optional create-callback)
+  (let ((create-callback (or create-callback #'ignore)))
+    (save-excursion
+      (goto-char (point-min))
+      (let ((spacing (floor (/ (/ (count-lines (point-min) (point-max))
+                                  (float 3))
+                               n))))
+        (when (< spacing 1)
+          (error "Hierarchical overlay overflow !!"))
+        (dotimes (i n)
+          (funcall create-callback
+                   (make-overlay (point)
+                                 (save-excursion
+                                   (goto-char (point-max))
+                                   (forward-line (- (* spacing i)))
+                                   (point))))
+
+          (when (eobp)
+            (error "End of buffer in hierarchical overlays"))
+          (forward-line spacing))))))
+
+(defun perf-overlay-ascii-chart (&optional buffer width)
+  (interactive)
+  (save-current-buffer
+    (when buffer (set-buffer buffer))
+    (unless width (setq width 100))
+    (let* ((ovl (sort (overlays-in (point-min) (point-max))
+                      (lambda (ov1 ov2)
+                        (or (<= (overlay-start ov1)
+                                (overlay-start ov2))
+                            (and
+                             (= (overlay-start ov1)
+                                (overlay-start ov2))
+                             (< (overlay-end ov1)
+                                (overlay-end ov2)))))))
+           (ov-width (apply #'max (mapcar (lambda (ov)
+                                            (- (overlay-end ov)
+                                               (overlay-start ov)))
+                                          ovl)))
+           (ov-min (apply #'min (mapcar #'overlay-start ovl)))
+           (ov-max (apply #'max (mapcar #'overlay-end ovl)))
+           (scale (/ (float width) (+ ov-min ov-width))))
+      (with-current-buffer (get-buffer-create "*overlay-ascii-chart*")
+        (let ((inhibit-read-only t))
+          (erase-buffer)
+          (buffer-disable-undo)
+          (insert (format "%06d%s%06d\n" ov-min (make-string (- width 12) ?\s) ov-max))
+          (dolist (ov ovl)
+            (let ((length (round (* scale (- (overlay-end ov)
+                                             (overlay-start ov))))))
+              (insert (make-string (round (* scale (overlay-start ov))) ?\s))
+              (cl-case length
+                (0 (insert "O"))
+                (1 (insert "|"))
+                (t (insert (format "|%s|" (make-string (- length 2) ?-)))))
+              (insert "\n")))
+          (goto-char (point-min)))
+        (read-only-mode 1)
+        (pop-to-buffer (current-buffer))))))
+
+(defconst perf-overlay-faces (mapcar #'intern (seq-take hi-lock-face-defaults 3)))
+
+(defun perf-overlay-face-callback (ov)
+  (overlay-put ov 'face (nth (random (length perf-overlay-faces))
+                             perf-overlay-faces)))
+
+(defun perf-overlay-invisible-callback (ov)
+  (overlay-put ov 'invisble (= 1 (random 2))))
+
+(defun perf-overlay-display-callback (ov)
+  (overlay-put ov 'display (make-string 70 ?*)))
+
+(defmacro perf-define-display-test (overlay-type property-type scroll-type)
+  (let ((name (intern (format "perf-display-%s/%s/%s"
+                              overlay-type property-type scroll-type)))
+        (arg (make-symbol "n")))
+
+    `(perf-define-variable-test ,name (,arg)
+       (with-temp-buffer
+         (perf-insert-lines ,arg)
+         (overlay-recenter (point-max))
+         ,@(perf-define-display-test-1 arg overlay-type property-type scroll-type)))))
+
+(defun perf-define-display-test-1 (arg overlay-type property-type scroll-type)
+  (list (append (cl-case overlay-type
+                  (sequential
+                   (list 'perf-insert-overlays-sequential 2))
+                  (hierarchical
+                   `(perf-insert-overlays-hierarchical (/ ,arg 10)))
+                  (random
+                   `(perf-insert-overlays-random (/ ,arg 2)))
+                  (t (error "Invalid insert type: %s" overlay-type)))
+                (list
+                 (cl-case property-type
+                   (display '#'perf-overlay-display-callback)
+                   (face '#'perf-overlay-face-callback)
+                   (invisible '#'perf-overlay-invisible-callback)
+                   (t (error "Invalid overlay type: %s" overlay-type)))))
+        (list 'benchmark-run 1
+              (cl-case scroll-type
+                (scroll '(perf-switch-to-buffer-scroll-up-and-down))
+                (random `(perf-switch-to-buffer-scroll-random (/ ,arg 50)))
+                (t (error "Invalid scroll type: %s" overlay-type))))))
+
+(defun perf-max-symbol-length (symbols)
+  "Return the longest symbol in SYMBOLS, or -1 if symbols is nil."
+  (if (null symbols)
+      -1
+    (apply #'max (mapcar
+                  (lambda (elt)
+                    (length (symbol-name elt)))
+                  symbols))))
+
+(defun perf-insert-text (n)
+  "Insert N character into the current buffer."
+  (let ((ncols 68)
+        (char ?.))
+    (dotimes (_  (/ n ncols))
+      (insert (make-string (1- ncols) char) ?\n))
+    (when (> (% n ncols) 0)
+      (insert (make-string (1- (% n ncols)) char) ?\n))))
+
+(defconst perf-insert-overlays-default-length 24)
+
+(defun perf-insert-overlays-scattered (n &optional length)
+  "Insert N overlays of max length 24 randomly."
+  (dotimes (_ n)
+    (let ((begin (random (1+ (point-max)))))
+      (make-overlay
+       begin (+ begin (random (1+ (or length perf-insert-overlays-default-length 0))))))))
+
+(defvar perf-marker-gc-protection nil)
+
+(defun perf-insert-marker-scattered (n)
+  "Insert N marker randomly."
+  (setq perf-marker-gc-protection nil)
+  (dotimes (_ n)
+    (push (copy-marker (random (1+ (point-max))))
+          perf-marker-gc-protection)))
+
+(defun perf-switch-to-buffer-scroll-up-and-down (&optional buffer)
+  (interactive)
+  (set-window-buffer nil (or buffer (current-buffer)))
+  (goto-char (point-min))
+  (redisplay t)
+  (while (condition-case nil
+             (progn (scroll-up) t)
+           (end-of-buffer nil))
+    (redisplay t))
+  (while (condition-case nil
+             (progn (scroll-down) t)
+           (beginning-of-buffer nil))
+    (redisplay t)))
+
+(defun perf-emacs-lisp-setup ()
+  (add-to-list 'imenu-generic-expression
+               '(nil "^\\s-*(perf-define\\(?:\\w\\|\\s_\\)*\\s-*\\(\\(?:\\w\\|\\s_\\)+\\)" 1)))
+
+(add-hook 'emacs-lisp-mode 'perf-emacs-lisp-setup)
+
+
+;; +===================================================================================+
+;; | Basic performance tests
+;; +===================================================================================+
+
+(perf-define-variable-test perf-make-overlay (n)
+  (with-temp-buffer
+    (overlay-recenter (point-min))
+    (benchmark-run 1
+      (dotimes (_ n)
+        (make-overlay 1 1)))))
+
+(perf-define-variable-test perf-make-overlay-continuous (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (overlay-recenter (point-max))
+    (benchmark-run 1
+      (dotimes (i n)
+        (make-overlay i (1+ i))))))
+
+(perf-define-variable-test perf-make-overlay-scatter (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (benchmark-run 1
+      (perf-insert-overlays-scattered n))))
+
+(perf-define-variable-test perf-delete-overlay (n)
+  (with-temp-buffer
+    (let ((ovls (cl-loop for i from 1 to n
+                        collect (make-overlay 1 1))))
+      (overlay-recenter (point-min))
+      (benchmark-run 1
+        (mapc #'delete-overlay ovls)))))
+
+(perf-define-variable-test perf-delete-overlay-continuous (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (let ((ovls (cl-loop for i from 1 to n
+                         collect (make-overlay i (1+ i)))))
+      (overlay-recenter (point-min))
+      (benchmark-run 1
+        (mapc #'delete-overlay ovls)))))
+
+(perf-define-variable-test perf-delete-overlay-scatter (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (let ((ovls (progn (perf-insert-overlays-scattered n)
+                       (overlays-in (point-min) (point-max)))))
+      (benchmark-run 1
+        (mapc #'delete-overlay ovls)))))
+
+(perf-define-variable-test perf-overlays-at (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (perf-insert-overlays-scattered n)
+    (benchmark-run 1
+      (dotimes (i (point-max))
+        (overlays-at i)))))
+
+(perf-define-variable-test perf-overlays-in (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (perf-insert-overlays-scattered n)
+    (let ((len perf-insert-overlays-default-length))
+      (benchmark-run 1
+        (dotimes (i (- (point-max) len))
+          (overlays-in i (+ i len)))))))
+
+(perf-define-variable-test perf-insert-before (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (perf-insert-overlays-scattered n)
+    (goto-char 1)
+    (overlay-recenter (point-min))
+    (benchmark-run 1
+      (dotimes (_ (/ n 2))
+        (insert ?X)))))
+
+(perf-define-variable-test perf-insert-before-empty (n)
+  (let ((perf-insert-overlays-default-length 0))
+    (perf-insert-before n)))
+(perf-define-variable-test perf-insert-after-empty (n)
+  (let ((perf-insert-overlays-default-length 0))
+    (perf-insert-after n)))
+(perf-define-variable-test perf-insert-scatter-empty (n)
+  (let ((perf-insert-overlays-default-length 0))
+    (perf-insert-scatter n)))
+(perf-define-variable-test perf-delete-before-empty (n)
+  (let ((perf-insert-overlays-default-length 0))
+    (perf-delete-before n)))
+(perf-define-variable-test perf-delete-after-empty (n)
+  (let ((perf-insert-overlays-default-length 0))
+    (perf-delete-after n)))
+(perf-define-variable-test perf-delete-scatter-empty (n)
+  (let ((perf-insert-overlays-default-length 0))
+    (perf-delete-scatter n)))
+
+(defmacro perf-define-marker-test (type where)
+  (let ((name (intern (format "perf-%s-%s-marker" type where))))
+    `(perf-define-variable-test ,name (n)
+       (with-temp-buffer
+         (perf-insert-text n)
+         (perf-insert-marker-scattered n)
+         (goto-char ,(cl-case where
+                       (after (list 'point-max))
+                       (t (list 'point-min))))
+         (benchmark-run 1
+           (dotimes (_ (/ n 2))
+             ,@(when (eq where 'scatter)
+                 (list '(goto-char (max 1 (random (point-max))))))
+             ,(cl-case type
+                (insert (list 'insert ?X))
+                (delete (list 'delete-char (if (eq where 'after) -1 1))))))))))
+
+(perf-define-test-suite perf-marker-suite
+  (perf-define-marker-test insert before)
+  (perf-define-marker-test insert after)
+  (perf-define-marker-test insert scatter)
+  (perf-define-marker-test delete before)
+  (perf-define-marker-test delete after)
+  (perf-define-marker-test delete scatter))
+
+(perf-define-variable-test perf-insert-after (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (perf-insert-overlays-scattered n)
+    (goto-char (point-max))
+    (overlay-recenter (point-max))
+    (benchmark-run 1
+      (dotimes (_ (/ n 2))
+        (insert ?X)))))
+
+(perf-define-variable-test perf-insert-scatter (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (perf-insert-overlays-scattered n)
+    (goto-char (point-max))
+    (benchmark-run 1
+      (dotimes (_ (/ n 2))
+        (goto-char (1+ (random (point-max))))
+        (insert ?X)))))
+
+(perf-define-variable-test perf-delete-before (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (perf-insert-overlays-scattered n)
+    (goto-char 1)
+    (overlay-recenter (point-min))
+    (benchmark-run 1
+      (dotimes (_ (/ n 2))
+        (delete-char 1)))))
+
+(perf-define-variable-test perf-delete-after (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (perf-insert-overlays-scattered n)
+    (goto-char (point-max))
+    (overlay-recenter (point-max))
+    (benchmark-run 1
+      (dotimes (_ (/ n 2))
+        (delete-char -1)))))
+
+(perf-define-variable-test perf-delete-scatter (n)
+  (with-temp-buffer
+    (perf-insert-text n)
+    (perf-insert-overlays-scattered n)
+    (goto-char (point-max))
+    (benchmark-run 1
+      (dotimes (_ (/ n 2))
+        (goto-char (max 1 (random (point-max))))
+        (delete-char 1)))))
+
+(perf-define-test-suite perf-insert-delete-suite
+  'perf-insert-before
+  'perf-insert-after
+  'perf-insert-scatter
+  'perf-delete-before
+  'perf-delete-after
+  'perf-delete-scatter
+  )
+
+
+;; +===================================================================================+
+;; | Redisplay (new)
+;; +===================================================================================+
+
+;; 5000
+;; 25000
+;; 75000
+
+;; Number of Overlays =  N / 2
+;;
+;; (except for the hierarchical case, where it is divided by 10.)
+
+  ;; . scrolling through a buffer with lots of overlays that affect faces
+  ;;   of characters in the buffer text
+  ;; . scrolling through a buffer with lots of overlays that define
+  ;;   'display' properties which are strings
+  ;; . scrolling through a buffer with lots of overlays that define
+  ;;   'invisible' properties
+
+(perf-define-test-suite perf-display-suite
+  (perf-define-display-test sequential display scroll)
+  (perf-define-display-test sequential display random)
+  (perf-define-display-test sequential face scroll)
+  (perf-define-display-test sequential face random)
+  (perf-define-display-test sequential invisible scroll)
+  (perf-define-display-test sequential invisible random)
+  (perf-define-display-test random display scroll)
+  (perf-define-display-test random display random)
+  (perf-define-display-test random face scroll)
+  (perf-define-display-test random face random)
+  (perf-define-display-test random invisible scroll)
+  (perf-define-display-test random invisible random))
+
+;; |------------|
+;;   |--------|
+;;     |----|
+(perf-define-display-test hierarchical face scroll)
+
+
+
+
+;; +===================================================================================+
+;; | Real World
+;; +===================================================================================+
+
+(require 'python)
+
+(defconst perf-many-errors-file
+  (expand-file-name "many-errors.py"
+                    (and load-file-name (file-name-directory load-file-name))))
+
+(perf-define-constant-test perf-realworld-flycheck
+  (interactive)
+  (package-initialize)
+  (when (and (require 'flycheck nil t)
+             (file-exists-p perf-many-errors-file)
+             (or (executable-find "pylint")
+                 (executable-find "flake8")))
+    (setq flycheck-python-pylint-executable
+          (executable-find "pylint"))
+    (setq flycheck-python-flake8-executable
+          (executable-find "flake8"))
+    (setq python-indent-guess-indent-offset-verbose nil)
+    (setq flycheck-check-syntax-automatically nil)
+    (setq flycheck-checker-error-threshold nil)
+    (setq flycheck-display-errors-function nil)
+    (with-current-buffer (find-file-noselect perf-many-errors-file)
+      (let* ((done)
+             (flycheck-after-syntax-check-hook
+              (list (lambda () (setq done t)))))
+        (flycheck-mode 1)
+        (flycheck-buffer)
+        (benchmark-run 1
+          (while (not done)
+            (accept-process-output))
+          (perf-switch-to-buffer-scroll-up-and-down)
+          (flycheck-mode -1))))))
+
+;; https://lists.gnu.org/archive/html/emacs-devel/2009-04/msg00242.html
+(defun make-lines-invisible (regexp &optional arg)
+  "Make all lines matching a regexp invisible and intangible.
+With a prefix arg, make it visible again.  It is not necessary
+that REGEXP matches the whole line; if a hit is found, the
+affected line gets automatically selected.
+
+This command affects the whole buffer."
+  (interactive "MRegexp: \nP")
+  (let (ov
+        ovs
+        count)
+    (cond
+     ((equal arg '(4))
+      (setq ovs (overlays-in (point-min) (point-max)))
+      (mapc (lambda (o)
+              (if (overlay-get o 'make-lines-invisible)
+                  (delete-overlay o)))
+            ovs))
+     (t
+      (save-excursion
+        (goto-char (point-min))
+        (setq count 0)
+        (while (re-search-forward regexp nil t)
+          (setq count (1+ count))
+          (if (= (% count 100) 0)
+              (message "%d" count))
+          (setq ov (make-overlay (line-beginning-position)
+                                 (1+ (line-end-position))))
+          (overlay-put ov 'make-lines-invisible t)
+          (overlay-put ov 'invisible t)
+          (overlay-put ov 'intangible t)
+          (goto-char (line-end-position))))))))
+
+(perf-define-constant-test perf-realworld-make-lines-invisible
+  (with-temp-buffer
+    (insert-file-contents "/usr/share/dict/words")
+    (set-window-buffer nil (current-buffer))
+    (redisplay t)
+    (overlay-recenter (point-max))
+    (benchmark-run 1
+      (make-lines-invisible "a"))))
+
+(perf-define-constant-test perf-realworld-line-numbering
+  (interactive)
+  (with-temp-buffer
+    (insert-file-contents "/usr/share/dict/words")
+    (overlay-recenter (point-max))
+    (goto-char (point-min))
+    (let* ((nlines (count-lines (point-min) (point-max)))
+           (line 1)
+           (width 0))
+      (dotimes (i nlines) ;;-with-progress-reporter "Creating overlays"
+        (let ((ov (make-overlay (point) (point)))
+              (str (propertize (format "%04d" line) 'face 'shadow)))
+          (overlay-put ov 'before-string
+                       (propertize " " 'display `((margin left-margin) ,str)))
+          (setq width (max width (length str)))
+          (cl-incf line)
+          (forward-line)))
+      (benchmark-run 1
+        (let ((left-margin-width width))
+          (perf-switch-to-buffer-scroll-up-and-down))))))
+
+(perf-define-test-suite perf-realworld-suite
+  'perf-realworld-flycheck
+  'perf-realworld-make-lines-invisible
+  'perf-realworld-line-numbering)
+
+
+;; +===================================================================================+
+;; | next-overlay-change
+;; +===================================================================================+
+
+(perf-define-variable-test perf-noc-hierarchical/forward/linear (n)
+  "Search linear for the next change on every line."
+  (with-temp-buffer
+    (perf-insert-lines (* 3 n))
+    (perf-insert-overlays-hierarchical n)
+    (goto-char (point-min))
+    (benchmark-run 1
+      (while (not (eobp))
+        (next-overlay-change (point))
+        (forward-line)))))
+
+(perf-define-variable-test perf-noc-sequential/forward/linear (n)
+  "Search linear for the next change on every line."
+  (with-temp-buffer
+    (perf-insert-lines (* 3 n))
+    (perf-insert-overlays-sequential n)
+    (goto-char (point-min))
+    (benchmark-run 1
+      (while (not (eobp))
+        (next-overlay-change (point))
+        (forward-line)))))
+
+(perf-define-variable-test perf-noc-hierarchical/forward/backnforth (n)
+  "Search back and forth for the next change from `point-min' to `point-max'."
+  (with-temp-buffer
+    (perf-insert-lines (* 3 n))
+    (overlay-recenter (point-max))
+    (perf-insert-overlays-hierarchical n)
+    (goto-char (point-min))
+    (benchmark-run 1
+      (while (not (eobp))
+        (next-overlay-change (point))
+        (next-overlay-change (+ (point) 2))
+        (forward-char)))))
+
+(perf-define-test-suite perf-noc-suite
+  'perf-noc-hierarchical/forward/linear
+  'perf-noc-hierarchical/forward/backnforth
+  'perf-noc-hierarchical/forward/backnforth)