Provide a new tree data-structure for overlays.

* src/itree.c
(interval_generator_narrow, interval_generator_next)
(interval_node_init, interval_node_begin)
(interval_node_end, interval_node_set_region)
(interval_tree_create, interval_tree_clear)
(interval_tree_init, interval_tree_destroy)
(interval_tree_size, interval_tree_insert)
(interval_tree_contains, interval_tree_remove)
(interval_tree_validate, interval_tree_iter_start)
(interval_tree_iter_finish, interval_tree_iter_next)
(interval_tree_iter_ensure_space, interval_tree_max_height)
(interval_tree_insert_gap, interval_tree_delete_gap)
(interval_generator_create, interval_generator_reset)
(interval_generator_ensure_space, interval_node_intersects)
(interval_generator_next, interval_generator_narrow)
(interval_generator_destroy, interval_stack_create)
(interval_stack_destroy, interval_stack_clear)
(interval_stack_ensure_space, interval_stack_push)
(interval_stack_push_flagged, interval_stack_pop)
(interval_tree_update_limit, interval_tree_inherit_offset)
(interval_tree_propagate_limit, interval_tree_rotate_left)
(interval_tree_rotate_right, interval_tree_insert_fix)
(interval_tree_remove_fix, interval_tree_transplant)
(interval_tree_subtree_min): New file and new functions.

* src/itree.h: New file.

* configure.ac: Create Makefile for manual overlay tests.

* src/Makefile.in: Add itree.o target.

* src/alloc.c (build_overlay, mark_overlay, mark_buffer)
(sweep_misc, sweep_buffers): Adapt to new tree data-structure.

* src/buffer.c (overlays_in, overlays_at): Remove unused arguments
prev_ptr and change_req, adapt to new data-structure and reuse
code.
(copy_overlays, drop_overlays, delete_all_overlays)
(reset_buffer, kill-buffer, buffer-swap-text, next_overlay_change)
(previous_overlay_change, mouse_face_overlay_overlaps)
(disable_line_numbers_overlay_at_eob, overlay_touches_p)
(overlay_strings, adjust_overlays_for_insert)
(adjust_overlays_for_delete, overlayp, make-overlay, move-overlay)
(delete-overlay, overlay-start, overlay-end, overlay-buffer)
(overlay-properties, overlays-at, overlays-in)
(next-overlay-change, previous-overlay-change, overlay-put)
(overlay-get, report_overlay_modification, evaporate_overlays)
(init_buffer_once): Adapt to changes and tree data-structure.
(overlay-lists, overlay-recenter): Funtions are now obsolete, but
kept anyway.
(set_buffer_overlays_before, set_buffer_overlays_after)
(recenter_overlay_lists,fix_start_end_in_overlays,fix_overlays_before)
(unchain_overlay,): Removed functions of the old list
data-structure.
(swap_buffer_overlays, make_sortvec_item): New functions.
(sort_overlays): Adapt to changes and tree data-structure.
(sortvec): Moved to buffer.h .
(make_lispy_interval_node, overlay_tree, overlay-tree)
[ITREE_DEBUG]: New debugging functions.

* src/buffer.h (overlays_before, overlays_after): Removed struct
member of the list data-structure.
(overlays): Added tree struct member.
(sortvec): Moved here from buffer.c .
(GET_OVERLAYS_AT): Adapt to changes.
(set_buffer_intervals, OVERLAY_START, OVERLAY_END, OVERLAY_PLIST):
Adapt to tree data-structure.
(OVERLAY_POSITION): Removed macro of the list data-structure.
(OVERLAY_REAR_ADVANCE_P, OVERLAY_FRONT_ADVANCE_P): New macros.
(overlay_start, overlay_end)
(set_overlay_region, maybe_alloc_buffer_overlays)
(free_buffer_overlays, add_buffer_overlay)
(remove_buffer_overlay, buffer_overlay_iter_start)
(buffer_overlay_iter_next, buffer_overlay_iter_finish)
(buffer_overlay_iter_narrow): New functions.
(compare_overlays, make_sortvec_item): Export functions.

* src/editfns.c (overlays_around): Reuse overlays_in.
(get-pos-property): Adapt to tree data-structure.
(transpose-regions): Remove call to deleted function.

* src/fileio.c: (insert-file-contents): Remove
references to deleted struct member.

* src/fns.c (internal_equal): Adapt to tree data-structure.

* src/indent.c (check_display_width): Adapt to tree
data-structure.
(skip_invisible): Remove call to deleted function.

* src/insdel.c (adjust_markers_for_insert): Remove calls to
deleted functions.

* src/intervals.c (adjust_for_invis_intang): Adapt to tree
data-structure.

* src/keyboard.c (adjust_point_for_property): Adapt to tree
data-structure.

* src/lisp.h (Lisp_Overlay): Modified struct layout.

* src/print.c (temp_output_buffer_setup, print_object): Adapt to
tree data-structure.

* src/textprop.c (get_char_property_and_overlay): Adapt to tree
data-structure.  Take advantage of the new data-structure.

* src/window.h (overlay_matches_window): New function.

* src/xdisp.h (next_overlay_change): Removed function.  Use
next-overlay-change, which does not use xmalloc anymore.
(handle_single_display_spec, load_overlay_strings)
(back_to_previous_visible_line_start, note_mouse_highlight): Adapt
to tree data-structure.
(move_it_to, display_line): Remove calls to deleted functions.

* src/xfaces.c (face_at_buffer_position): Adapt to changes and
tree data-structure.

* test/src/buffer-tests.el: Many tests regarding overlays added.

* test/manual/noverlay/itree-tests.c: New file with tests of the
tree data-structure on the C level.
* test/manual/noverlay/Makefile.in: New file.
* test/manual/noverlay/check-sanitize.sh: New file.
* test/manual/noverlay/emacs-compat.h: New file.
* test/manual/noverlay/.gitignore: New file.

* test/manual/noverlay/overlay-perf.el: New file providing
performance tests.
* test/manual/noverlay/many-errors.h: New file.

7 files changed, 4721 insertions, 0 deletions

diff --git a/test/manual/noverlay/.gitignore b/test/manual/noverlay/.gitignore
new file mode 100644
index 00000000000..ca7fc452b84
--- /dev/null
+++ b/test/manual/noverlay/.gitignore
@@ -0,0 +1 @@
+itree-tests
diff --git a/test/manual/noverlay/Makefile.in b/test/manual/noverlay/Makefile.in
new file mode 100644
index 00000000000..beef1dbc097
--- /dev/null
+++ b/test/manual/noverlay/Makefile.in
@@ -0,0 +1,32 @@
+PROGRAM = itree-tests
+LIBS = check
+top_srcdir = @top_srcdir@
+CFLAGS += -O0 -g3 $(shell pkg-config --cflags $(LIBS)) -I $(top_srcdir)/src
+LDFLAGS += $(shell pkg-config --libs $(LIBS)) -lm
+OBJECTS = itree-tests.o
+CC = gcc
+EMACS ?= ../../../src/emacs
+
+.PHONY: all check have-libcheck
+
+all: check
+
+have-libcheck:
+	pkg-config --cflags $(LIBS)
+
+check: have-libcheck $(PROGRAM)
+	./check-sanitize.sh ./$(PROGRAM)
+
+itree-tests.o: emacs-compat.h itree-tests.c $(top_srcdir)/src/itree.c $(top_srcdir)/src/itree.h
+
+$(PROGRAM): $(OBJECTS)
+	$(CC) $(CFLAGS) $(LDFLAGS) $(OBJECTS) -o $(PROGRAM)
+
+perf:
+	-$(EMACS) -Q -l ./overlay-perf.el -f perf-run-batch
+
+clean:
+	rm -f -- $(OBJECTS) $(PROGRAM)
+
+distclean: clean
+	rm -f -- Makefile
diff --git a/test/manual/noverlay/check-sanitize.sh b/test/manual/noverlay/check-sanitize.sh
new file mode 100755
index 00000000000..03eedce8a67
--- /dev/null
+++ b/test/manual/noverlay/check-sanitize.sh
@@ -0,0 +1,11 @@
+#!/bin/bash
+
+prog=$1
+shift
+
+[ -z "$prog" ] && {
+    echo "usage:$(basename $0) CHECK_PRGOGRAM";
+    exit 1;
+}
+
+"$prog" "$@" | sed -e 's/^\([^:]\+\):\([0-9]\+\):[PFE]:[^:]*:\([^:]*\):[^:]*: *\(.*\)/\1:\2:\3:\4/'
diff --git a/test/manual/noverlay/emacs-compat.h b/test/manual/noverlay/emacs-compat.h
new file mode 100644
index 00000000000..812f8e48a36
--- /dev/null
+++ b/test/manual/noverlay/emacs-compat.h
@@ -0,0 +1,52 @@
+#ifndef TEST_COMPAT_H
+#define TEST_COMPAT_H
+
+#include <stdio.h>
+#include <limits.h>
+
+typedef int Lisp_Object;
+
+void *
+xmalloc (size_t size)
+{
+  return malloc (size);
+}
+
+void
+xfree (void *ptr)
+{
+  free (ptr);
+}
+
+void *
+xrealloc (void *block, size_t size)
+{
+  return realloc (block, size);
+}
+
+void
+emacs_abort ()
+{
+  fprintf (stderr, "Aborting...\n");
+  exit (1);
+}
+
+#ifndef eassert
+#define eassert(cond)                                                   \
+  do {                                                                  \
+    if (! (cond)) {                                                     \
+      fprintf (stderr, "\n%s:%d:eassert condition failed: %s\n",        \
+               __FILE__, __LINE__ ,#cond);                              \
+      exit (1);                                                         \
+    }                                                                   \
+  } while (0)
+#endif
+
+#ifndef max
+#define max(x,y) ((x) >= (y) ? (x) : (y))
+#endif
+#ifndef min
+#define min(x,y) ((x) <= (y) ? (x) : (y))
+#endif
+
+#endif
diff --git a/test/manual/noverlay/itree-tests.c b/test/manual/noverlay/itree-tests.c
new file mode 100644
index 00000000000..a3183892132
--- /dev/null
+++ b/test/manual/noverlay/itree-tests.c
@@ -0,0 +1,1381 @@
+#include <config.h>
+#include <check.h>
+#include <stdlib.h>
+#include <stdarg.h>
+#include "emacs-compat.h"
+
+#define EMACS_LISP_H            /* lisp.h inclusion guard */
+#define ITREE_DEBUG 1
+#define ITREE_TESTING
+#include "itree.c"
+
+/* Basic tests of the interval_tree data-structure. */
+
+/* +===================================================================================+
+ * | Insert
+ * +===================================================================================+ */
+
+/* The graphs below display the trees after each insertion (as they
+   should be).  See the source code for the different cases
+   applied. */
+
+#define N_50 (n[0])
+#define N_30 (n[1])
+#define N_20 (n[2])
+#define N_10 (n[3])
+#define N_15 (n[4])
+#define N_05 (n[5])
+
+#define DEF_TEST_SETUP()                        \
+  struct interval_tree tree;                    \
+  struct interval_node n[6];                    \
+  interval_tree_init (&tree);                   \
+  const int values[] = {50, 30, 20, 10, 15, 5}; \
+  for (int i = 0; i < 6; ++i)                   \
+    {                                           \
+      n[i].begin = values[i];                   \
+      n[i].end = values[i];                     \
+    }
+
+START_TEST (test_insert_1)
+{
+  /*
+   *                 [50]
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (&N_50 == tree.root);
+}
+END_TEST
+
+START_TEST (test_insert_2)
+{
+  /*
+   *                 [50]
+   *                /
+   *              (30)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_30);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (N_30.color == ITREE_RED);
+  ck_assert (&N_50 == tree.root);
+  ck_assert (N_30.parent == &N_50);
+  ck_assert (N_50.left == &N_30);
+  ck_assert (N_50.right == &tree.nil);
+  ck_assert (N_30.left == &tree.nil);
+  ck_assert (N_30.right == &tree.nil);
+}
+END_TEST
+
+START_TEST (test_insert_3)
+{
+  /* case 3.a
+   *                [30]
+   *               /    \
+   *             (20)   (50)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_30);
+  interval_tree_insert (&tree, &N_20);
+  ck_assert (N_50.color == ITREE_RED);
+  ck_assert (N_30.color == ITREE_BLACK);
+  ck_assert (N_20.color == ITREE_RED);
+  ck_assert (&N_30 == tree.root);
+  ck_assert (N_50.parent == &N_30);
+  ck_assert (N_30.right == &N_50);
+  ck_assert (N_30.left == &N_20);
+  ck_assert (N_20.left == &tree.nil);
+  ck_assert (N_20.right == &tree.nil);
+  ck_assert (N_20.parent == &N_30);
+}
+END_TEST
+
+START_TEST (test_insert_4)
+{
+  /* 1.a
+   *                [30]
+   *               /    \
+   *             [20]   [50]
+   *             /
+   *           (10)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_30);
+  interval_tree_insert (&tree, &N_20);
+  interval_tree_insert (&tree, &N_10);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (N_30.color == ITREE_BLACK);
+  ck_assert (N_20.color == ITREE_BLACK);
+  ck_assert (N_10.color == ITREE_RED);
+  ck_assert (&N_30 == tree.root);
+  ck_assert (N_50.parent == &N_30);
+  ck_assert (N_30.right == &N_50);
+  ck_assert (N_30.left == &N_20);
+  ck_assert (N_20.left == &N_10);
+  ck_assert (N_20.right == &tree.nil);
+  ck_assert (N_20.parent == &N_30);
+  ck_assert (N_10.parent == &N_20);
+  ck_assert (N_20.left == &N_10);
+  ck_assert (N_10.right == &tree.nil);
+}
+END_TEST
+
+START_TEST (test_insert_5)
+{
+  /* 2.a
+   *                [30]
+   *               /    \
+   *             [15]   [50]
+   *             /  \
+   *           (10) (20)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_30);
+  interval_tree_insert (&tree, &N_20);
+  interval_tree_insert (&tree, &N_10);
+  interval_tree_insert (&tree, &N_15);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (N_30.color == ITREE_BLACK);
+  ck_assert (N_20.color == ITREE_RED);
+  ck_assert (N_10.color == ITREE_RED);
+  ck_assert (N_15.color == ITREE_BLACK);
+  ck_assert (&N_30 == tree.root);
+  ck_assert (N_50.parent == &N_30);
+  ck_assert (N_30.right == &N_50);
+  ck_assert (N_30.left == &N_15);
+  ck_assert (N_20.left == &tree.nil);
+  ck_assert (N_20.right == &tree.nil);
+  ck_assert (N_20.parent == &N_15);
+  ck_assert (N_10.parent == &N_15);
+  ck_assert (N_20.left == &tree.nil);
+  ck_assert (N_10.right == &tree.nil);
+  ck_assert (N_15.right == &N_20);
+  ck_assert (N_15.left == &N_10);
+  ck_assert (N_15.parent == &N_30);
+
+}
+END_TEST
+
+START_TEST (test_insert_6)
+{
+  /* 1.a
+   *                [30]
+   *               /    \
+   *             (15)   [50]
+   *             /  \
+   *           [10] [20]
+   *           /
+   *         (5)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_30);
+  interval_tree_insert (&tree, &N_20);
+  interval_tree_insert (&tree, &N_10);
+  interval_tree_insert (&tree, &N_15);
+  interval_tree_insert (&tree, &N_05);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (N_30.color == ITREE_BLACK);
+  ck_assert (N_20.color == ITREE_BLACK);
+  ck_assert (N_10.color == ITREE_BLACK);
+  ck_assert (N_15.color == ITREE_RED);
+  ck_assert (N_05.color == ITREE_RED);
+  ck_assert (&N_30 == tree.root);
+  ck_assert (N_50.parent == &N_30);
+  ck_assert (N_30.right == &N_50);
+  ck_assert (N_30.left == &N_15);
+  ck_assert (N_20.left == &tree.nil);
+  ck_assert (N_20.right == &tree.nil);
+  ck_assert (N_20.parent == &N_15);
+  ck_assert (N_10.parent == &N_15);
+  ck_assert (N_20.left == &tree.nil);
+  ck_assert (N_10.right == &tree.nil);
+  ck_assert (N_15.right == &N_20);
+  ck_assert (N_15.left == &N_10);
+  ck_assert (N_15.parent == &N_30);
+  ck_assert (N_05.parent == &N_10);
+  ck_assert (N_10.left == &N_05);
+  ck_assert (N_05.right == &tree.nil);
+}
+END_TEST
+
+#undef N_50
+#undef N_30
+#undef N_20
+#undef N_10
+#undef N_15
+#undef N_05
+#undef DEF_TEST_SETUP
+
+
+
+/* These are the mirror cases to the above ones.  */
+
+#define N_50 (n[0])
+#define N_70 (n[1])
+#define N_80 (n[2])
+#define N_90 (n[3])
+#define N_85 (n[4])
+#define N_95 (n[5])
+
+#define DEF_TEST_SETUP()                                \
+  struct interval_tree tree;                            \
+  struct interval_node n[6];                            \
+  interval_tree_init (&tree);                           \
+  const int values[] = {50, 70, 80, 90, 85, 95};        \
+  for (int i = 0; i < 6; ++i)                           \
+    {                                                   \
+      n[i].begin = values[i];                           \
+      n[i].end = values[i];                             \
+    }
+
+START_TEST (test_insert_7)
+{
+  /*
+   *                 [50]
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (&N_50 == tree.root);
+}
+END_TEST
+
+START_TEST (test_insert_8)
+{
+  /*
+   *                 [50]
+   *                    \
+   *                   (70)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_70);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (N_70.color == ITREE_RED);
+  ck_assert (&N_50 == tree.root);
+  ck_assert (N_70.parent == &N_50);
+  ck_assert (N_50.right == &N_70);
+  ck_assert (N_50.left == &tree.nil);
+  ck_assert (N_70.right == &tree.nil);
+  ck_assert (N_70.left == &tree.nil);
+}
+END_TEST
+
+START_TEST (test_insert_9)
+{
+  /* 3.a
+   *                [70]
+   *               /    \
+   *             (50)   (80)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_70);
+  interval_tree_insert (&tree, &N_80);
+  ck_assert (N_50.color == ITREE_RED);
+  ck_assert (N_70.color == ITREE_BLACK);
+  ck_assert (N_80.color == ITREE_RED);
+  ck_assert (&N_70 == tree.root);
+  ck_assert (N_50.parent == &N_70);
+  ck_assert (N_70.right == &N_80);
+  ck_assert (N_70.left == &N_50);
+  ck_assert (N_80.right == &tree.nil);
+  ck_assert (N_80.left == &tree.nil);
+  ck_assert (N_80.parent == &N_70);
+}
+END_TEST
+
+START_TEST (test_insert_10)
+{
+  /* 1.b
+   *                [70]
+   *               /    \
+   *             [50]   [80]
+   *                      \
+   *                      (90)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_70);
+  interval_tree_insert (&tree, &N_80);
+  interval_tree_insert (&tree, &N_90);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (N_70.color == ITREE_BLACK);
+  ck_assert (N_80.color == ITREE_BLACK);
+  ck_assert (N_90.color == ITREE_RED);
+  ck_assert (&N_70 == tree.root);
+  ck_assert (N_50.parent == &N_70);
+  ck_assert (N_70.right == &N_80);
+  ck_assert (N_70.left == &N_50);
+  ck_assert (N_80.right == &N_90);
+  ck_assert (N_80.left == &tree.nil);
+  ck_assert (N_80.parent == &N_70);
+  ck_assert (N_90.parent == &N_80);
+  ck_assert (N_80.right == &N_90);
+  ck_assert (N_90.left == &tree.nil);
+}
+END_TEST
+
+START_TEST (test_insert_11)
+{
+  /* 2.b
+   *                [70]
+   *               /    \
+   *             [50]   [85]
+   *                    /  \
+   *                  (80) (90)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_70);
+  interval_tree_insert (&tree, &N_80);
+  interval_tree_insert (&tree, &N_90);
+  interval_tree_insert (&tree, &N_85);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (N_70.color == ITREE_BLACK);
+  ck_assert (N_80.color == ITREE_RED);
+  ck_assert (N_90.color == ITREE_RED);
+  ck_assert (N_85.color == ITREE_BLACK);
+  ck_assert (&N_70 == tree.root);
+  ck_assert (N_50.parent == &N_70);
+  ck_assert (N_70.right == &N_85);
+  ck_assert (N_70.left == &N_50);
+  ck_assert (N_80.right == &tree.nil);
+  ck_assert (N_80.left == &tree.nil);
+  ck_assert (N_80.parent == &N_85);
+  ck_assert (N_90.parent == &N_85);
+  ck_assert (N_80.right == &tree.nil);
+  ck_assert (N_90.left == &tree.nil);
+  ck_assert (N_85.right == &N_90);
+  ck_assert (N_85.left == &N_80);
+  ck_assert (N_85.parent == &N_70);
+
+}
+END_TEST
+
+START_TEST (test_insert_12)
+{
+  /* 1.b
+   *                [70]
+   *               /    \
+   *             [50]   (85)
+   *                    /  \
+   *                  [80] [90]
+   *                         \
+   *                        (95)
+   */
+
+  DEF_TEST_SETUP ();
+  interval_tree_insert (&tree, &N_50);
+  interval_tree_insert (&tree, &N_70);
+  interval_tree_insert (&tree, &N_80);
+  interval_tree_insert (&tree, &N_90);
+  interval_tree_insert (&tree, &N_85);
+  interval_tree_insert (&tree, &N_95);
+  ck_assert (N_50.color == ITREE_BLACK);
+  ck_assert (N_70.color == ITREE_BLACK);
+  ck_assert (N_80.color == ITREE_BLACK);
+  ck_assert (N_90.color == ITREE_BLACK);
+  ck_assert (N_85.color == ITREE_RED);
+  ck_assert (N_95.color == ITREE_RED);
+  ck_assert (&N_70 == tree.root);
+  ck_assert (N_50.parent == &N_70);
+  ck_assert (N_70.right == &N_85);
+  ck_assert (N_70.left == &N_50);
+  ck_assert (N_80.right == &tree.nil);
+  ck_assert (N_80.left == &tree.nil);
+  ck_assert (N_80.parent == &N_85);
+  ck_assert (N_90.parent == &N_85);
+  ck_assert (N_80.right == &tree.nil);
+  ck_assert (N_90.left == &tree.nil);
+  ck_assert (N_85.right == &N_90);
+  ck_assert (N_85.left == &N_80);
+  ck_assert (N_85.parent == &N_70);
+  ck_assert (N_95.parent == &N_90);
+  ck_assert (N_90.right == &N_95);
+  ck_assert (N_95.left == &tree.nil);
+}
+END_TEST
+
+#undef N_50
+#undef N_70
+#undef N_80
+#undef N_90
+#undef N_85
+#undef N_95
+#undef DEF_TEST_SETUP
+
+struct interval_tree*
+test_get_tree4 (struct interval_node **n)
+{
+  static struct interval_tree tree;
+  static struct interval_node nodes[4];
+  memset (&tree, 0, sizeof (struct interval_tree));
+  memset (&nodes, 0, 4 * sizeof (struct interval_node));
+  interval_tree_init (&tree);
+  for (int i = 0; i < 4; ++i)
+    {
+      nodes[i].begin = 10 * (i + 1);
+      nodes[i].end = nodes[i].begin;
+      interval_tree_insert (&tree, &nodes[i]);
+    }
+  *n = nodes;
+  return &tree;
+}
+
+static void
+shuffle (int *index, int n)
+{
+  for (int i = n - 1; i >= 0; --i)
+    {
+      int j = random () % (i + 1);
+      int h = index[j];
+      index[j] = index[i];
+      index[i] = h;
+    }
+}
+
+#define N_10 (nodes[0])
+#define N_20 (nodes[1])
+#define N_30 (nodes[2])
+#define N_40 (nodes[3])
+
+START_TEST (test_insert_13)
+{
+  struct interval_node *nodes = NULL;
+  struct interval_tree *tree = test_get_tree4 (&nodes);
+
+
+  ck_assert (tree->root == &N_20);
+  ck_assert (N_20.left == &N_10);
+  ck_assert (N_20.right == &N_30);
+  ck_assert (N_30.right == &N_40);
+  ck_assert (N_10.color == ITREE_BLACK);
+  ck_assert (N_20.color == ITREE_BLACK);
+  ck_assert (N_30.color == ITREE_BLACK);
+  ck_assert (N_40.color == ITREE_RED);
+}
+END_TEST
+
+START_TEST (test_insert_14)
+{
+  struct interval_tree tree;
+  struct interval_node nodes[3];
+
+  nodes[0].begin = nodes[1].begin = nodes[2].begin = 10;
+  nodes[0].end = nodes[1].end = nodes[2].end = 10;
+
+  for (int i = 0; i < 3; ++i)
+    interval_tree_insert (&tree, &nodes[i]);
+  for (int i = 0; i < 3; ++i)
+    ck_assert (interval_tree_contains (&tree, &nodes[i]));
+}
+END_TEST
+
+
+
+
+/* +===================================================================================+
+ * | Remove
+ * +===================================================================================+ */
+
+#define A (nodes[0])
+#define B (nodes[1])
+#define C (nodes[2])
+#define D (nodes[3])
+#define E (nodes[4])
+
+/* Creating proper test trees for the formal tests via insertions is
+   way to tedious, so we just fake it and only test the
+   fix-routine. */
+#define DEF_TEST_SETUP()                                        \
+    struct interval_tree tree;                                  \
+    struct interval_node nodes[5];                              \
+    interval_tree_init (&tree);                                 \
+    tree.root = &B;                                             \
+    A.parent = &B; B.parent = &tree.nil; C.parent = &D;         \
+    D.parent = &B; E.parent = &D;                               \
+    A.left = A.right = C.left = C.right = &tree.nil;            \
+    E.left = E.right = &tree.nil;                               \
+    B.left = &A; B.right = &D; D.left = &C; D.right = &E        \
+
+/* 1.a -> 2.a
+ *                [B]
+ *               /    \
+ *             [A]    (D)
+ *                    /  \
+ *                 [C]   [E]
+ */
+
+
+START_TEST (test_remove_1)
+{
+  DEF_TEST_SETUP ();
+  B.color = A.color = C.color = E.color = ITREE_BLACK;
+  D.color = ITREE_RED;
+  interval_tree_remove_fix (&tree, &A);
+
+  ck_assert (A.color == ITREE_BLACK);
+  ck_assert (B.color == ITREE_BLACK);
+  ck_assert (C.color == ITREE_RED);
+  ck_assert (D.color == ITREE_BLACK);
+  ck_assert (E.color == ITREE_BLACK);
+  ck_assert (A.parent == &B);
+  ck_assert (B.left == &A);
+  ck_assert (B.right == &C);
+  ck_assert (C.parent == &B);
+  ck_assert (E.parent == &D);
+  ck_assert (D.right == &E);
+  ck_assert (D.left == &B);
+  ck_assert (tree.root == &D);
+}
+END_TEST
+
+/* 2.a */
+START_TEST (test_remove_2)
+{
+  DEF_TEST_SETUP ();
+  B.color = D.color = A.color = C.color = E.color = ITREE_BLACK;
+  interval_tree_remove_fix (&tree, &A);
+
+  ck_assert (A.color == ITREE_BLACK);
+  ck_assert (B.color == ITREE_BLACK);
+  ck_assert (C.color == ITREE_BLACK);
+  ck_assert (D.color == ITREE_RED);
+  ck_assert (E.color == ITREE_BLACK);
+  ck_assert (A.parent == &B);
+  ck_assert (B.left == &A);
+  ck_assert (B.right == &D);
+  ck_assert (C.parent == &D);
+  ck_assert (E.parent == &D);
+  ck_assert (tree.root == &B);
+}
+END_TEST
+
+/* 3.a -> 4.a*/
+START_TEST (test_remove_3)
+{
+  DEF_TEST_SETUP ();
+  D.color = A.color = E.color = ITREE_BLACK;
+  B.color = C.color = ITREE_RED;
+  interval_tree_remove_fix (&tree, &A);
+
+  ck_assert (A.color == ITREE_BLACK);
+  ck_assert (B.color == ITREE_BLACK);
+  ck_assert (C.color == ITREE_BLACK);
+  ck_assert (D.color == ITREE_BLACK);
+  ck_assert (E.color == ITREE_BLACK);
+  ck_assert (A.parent == &B);
+  ck_assert (B.left == &A);
+  ck_assert (B.right == &tree.nil);
+  ck_assert (&C == tree.root);
+  ck_assert (C.left == &B);
+  ck_assert (C.right == &D);
+  ck_assert (E.parent == &D);
+  ck_assert (D.left == &tree.nil);
+
+}
+END_TEST
+
+/* 4.a */
+START_TEST (test_remove_4)
+{
+  DEF_TEST_SETUP ();
+  B.color = C.color = E.color = ITREE_RED;
+  A.color = D.color = ITREE_BLACK;
+  interval_tree_remove_fix (&tree, &A);
+
+  ck_assert (A.color == ITREE_BLACK);
+  ck_assert (B.color == ITREE_BLACK);
+  ck_assert (C.color == ITREE_RED);
+  ck_assert (D.color == ITREE_BLACK);
+  ck_assert (E.color == ITREE_BLACK);
+  ck_assert (A.parent == &B);
+  ck_assert (B.left == &A);
+  ck_assert (B.right == &C);
+  ck_assert (C.parent == &B);
+  ck_assert (E.parent == &D);
+  ck_assert (tree.root == &D);
+}
+END_TEST
+
+
+#undef A
+#undef B
+#undef C
+#undef D
+#undef E
+#undef DEF_TEST_SETUP
+
+
+
+/* These are the mirrored cases. */
+
+#define A (nodes[0])
+#define B (nodes[1])
+#define C (nodes[2])
+#define D (nodes[3])
+#define E (nodes[4])
+
+#define DEF_TEST_SETUP()                                        \
+    struct interval_tree tree;                                  \
+    struct interval_node nodes[5];                              \
+    interval_tree_init (&tree);                                 \
+    tree.root = &B;                                             \
+    A.parent = &B; B.parent = &tree.nil; C.parent = &D;         \
+    D.parent = &B; E.parent = &D;                               \
+    A.right = A.left = C.right = C.left = &tree.nil;            \
+    E.right = E.left = &tree.nil;                               \
+    B.right = &A; B.left = &D; D.right = &C; D.left = &E        \
+
+/* 1.b -> 2.b
+ *                [B]
+ *               /    \
+ *             [A]    (D)
+ *                    /  \
+ *                 [C]   [E]
+ */
+
+
+START_TEST (test_remove_5)
+{
+  DEF_TEST_SETUP ();
+  B.color = A.color = C.color = E.color = ITREE_BLACK;
+  D.color = ITREE_RED;
+  interval_tree_remove_fix (&tree, &A);
+
+  ck_assert (A.color == ITREE_BLACK);
+  ck_assert (B.color == ITREE_BLACK);
+  ck_assert (C.color == ITREE_RED);
+  ck_assert (D.color == ITREE_BLACK);
+  ck_assert (E.color == ITREE_BLACK);
+  ck_assert (A.parent == &B);
+  ck_assert (B.right == &A);
+  ck_assert (B.left == &C);
+  ck_assert (C.parent == &B);
+  ck_assert (E.parent == &D);
+  ck_assert (D.left == &E);
+  ck_assert (D.right == &B);
+  ck_assert (tree.root == &D);
+}
+END_TEST
+
+/* 2.b */
+START_TEST (test_remove_6)
+{
+  DEF_TEST_SETUP ();
+  B.color = D.color = A.color = C.color = E.color = ITREE_BLACK;
+  interval_tree_remove_fix (&tree, &A);
+
+  ck_assert (A.color == ITREE_BLACK);
+  ck_assert (B.color == ITREE_BLACK);
+  ck_assert (C.color == ITREE_BLACK);
+  ck_assert (D.color == ITREE_RED);
+  ck_assert (E.color == ITREE_BLACK);
+  ck_assert (A.parent == &B);
+  ck_assert (B.right == &A);
+  ck_assert (B.left == &D);
+  ck_assert (C.parent == &D);
+  ck_assert (E.parent == &D);
+  ck_assert (tree.root == &B);
+}
+END_TEST
+
+/* 3.b -> 4.b*/
+START_TEST (test_remove_7)
+{
+  DEF_TEST_SETUP ();
+  D.color = A.color = E.color = ITREE_BLACK;
+  B.color = C.color = ITREE_RED;
+  interval_tree_remove_fix (&tree, &A);
+
+  ck_assert (A.color == ITREE_BLACK);
+  ck_assert (B.color == ITREE_BLACK);
+  ck_assert (C.color == ITREE_BLACK);
+  ck_assert (D.color == ITREE_BLACK);
+  ck_assert (E.color == ITREE_BLACK);
+  ck_assert (A.parent == &B);
+  ck_assert (B.right == &A);
+  ck_assert (B.left == &tree.nil);
+  ck_assert (&C == tree.root);
+  ck_assert (C.right == &B);
+  ck_assert (C.left == &D);
+  ck_assert (E.parent == &D);
+  ck_assert (D.right == &tree.nil);
+
+}
+END_TEST
+
+/* 4.b */
+START_TEST (test_remove_8)
+{
+  DEF_TEST_SETUP ();
+  B.color = C.color = E.color = ITREE_RED;
+  A.color = D.color = ITREE_BLACK;
+  interval_tree_remove_fix (&tree, &A);
+
+  ck_assert (A.color == ITREE_BLACK);
+  ck_assert (B.color == ITREE_BLACK);
+  ck_assert (C.color == ITREE_RED);
+  ck_assert (D.color == ITREE_BLACK);
+  ck_assert (E.color == ITREE_BLACK);
+  ck_assert (A.parent == &B);
+  ck_assert (B.right == &A);
+  ck_assert (B.left == &C);
+  ck_assert (C.parent == &B);
+  ck_assert (E.parent == &D);
+  ck_assert (tree.root == &D);
+}
+END_TEST
+
+
+#undef A
+#undef B
+#undef C
+#undef D
+#undef E
+#undef DEF_TEST_SETUP
+
+
+START_TEST (test_remove_9)
+{
+  struct interval_node *nodes = NULL;
+  struct interval_tree *tree = test_get_tree4 (&nodes);
+
+  ck_assert (tree->root == &N_20);
+  ck_assert (N_20.left == &N_10);
+  ck_assert (N_20.right == &N_30);
+  ck_assert (N_30.right == &N_40);
+  ck_assert (N_20.color == ITREE_BLACK);
+  ck_assert (N_10.color == ITREE_BLACK);
+  ck_assert (N_30.color == ITREE_BLACK);
+  ck_assert (N_40.color == ITREE_RED);
+
+  interval_tree_remove (tree, &N_10);
+
+  ck_assert (tree->root == &N_30);
+  ck_assert (N_30.parent == &tree->nil);
+  ck_assert (N_30.left == &N_20);
+  ck_assert (N_30.right == &N_40);
+  ck_assert (N_20.color == ITREE_BLACK);
+  ck_assert (N_30.color == ITREE_BLACK);
+  ck_assert (N_40.color == ITREE_BLACK);
+}
+END_TEST
+
+#define N 3
+
+START_TEST (test_remove_10)
+{
+  struct interval_tree tree;
+  struct interval_node nodes[N];
+  int index[N];
+
+  srand (42);
+  interval_tree_init (&tree);
+  for (int i = 0; i < N; ++i)
+    {
+      nodes[i].begin = (i + 1) * 10;
+      nodes[i].end = nodes[i].begin + 1;
+      index[i] = i;
+    }
+  shuffle (index, N);
+  for (int i = 0; i < N; ++i)
+    interval_tree_insert (&tree, &nodes[index[i]]);
+
+  shuffle (index, N);
+  for (int i = 0; i < N; ++i)
+    {
+      ck_assert (interval_tree_contains (&tree, &nodes[index[i]]));
+      interval_tree_remove (&tree, &nodes[index[i]]);
+    }
+  ck_assert (tree.root == &tree.nil);
+  ck_assert (tree.size == 0);
+}
+END_TEST
+
+
+/* +===================================================================================+
+ * | Generator
+ * +===================================================================================+ */
+
+START_TEST (test_generator_1)
+{
+  struct interval_tree tree;
+  struct interval_node node, *n;
+  struct interval_generator *g;
+  interval_tree_init (&tree);
+  node.begin = 10;
+  node.end = 20;
+  interval_tree_insert (&tree, &node);
+  g = interval_generator_create (&tree);
+  interval_generator_reset (g, 0, 30, ITREE_ASCENDING);
+  n = interval_generator_next (g);
+  ck_assert (n == &node);
+  ck_assert (n->begin == 10 && n->end == 20);
+  ck_assert (interval_generator_next (g) == NULL);
+  ck_assert (interval_generator_next (g) == NULL);
+  ck_assert (interval_generator_next (g) == NULL);
+  interval_generator_destroy (g);
+
+  g = interval_generator_create (&tree);
+  interval_generator_reset (g, 30, 50, ITREE_ASCENDING);
+  ck_assert (interval_generator_next (g) == NULL);
+  ck_assert (interval_generator_next (g) == NULL);
+  ck_assert (interval_generator_next (g) == NULL);
+  interval_generator_destroy (g);
+}
+END_TEST
+
+void
+test_check_generator (struct interval_tree *tree,
+                      ptrdiff_t begin, ptrdiff_t end,
+                      int n, ...)
+{
+  va_list ap;
+  struct interval_generator *g = interval_generator_create (tree);
+  interval_generator_reset (g, begin, end, ITREE_ASCENDING);
+
+  va_start (ap, n);
+  for (int i = 0; i < n; ++i)
+    {
+      ptrdiff_t begin = va_arg (ap, ptrdiff_t);
+      struct interval_node *node = interval_generator_next (g);
+      ck_assert (node);
+      ck_assert_int_eq (node->begin, begin);
+    }
+  va_end (ap);
+  ck_assert (! interval_generator_next (g));
+  ck_assert (! interval_generator_next (g));
+  interval_generator_destroy (g);
+}
+
+#define DEF_TEST_SETUP()                        \
+
+
+START_TEST (test_generator_2)
+{
+  struct interval_tree tree;
+  struct interval_node nodes[3];
+
+  interval_tree_init (&tree);
+
+  for (int i = 0; i < 3; ++i) {
+    nodes[i].begin = 10 * (i + 1);
+    nodes[i].end = 10 * (i + 2);
+    interval_tree_insert (&tree, &nodes[i]);
+  }
+
+  test_check_generator (&tree, 0, 50, 3,
+                        10, 20, 30);
+  test_check_generator (&tree, 0, 10, 0);
+  test_check_generator (&tree, 40, 50, 0);
+  test_check_generator (&tree, 15, 35, 3,
+                        10, 20, 30);
+  test_check_generator (&tree, -100, -50, 0);
+  test_check_generator (&tree, -100, -50, 0);
+  test_check_generator (&tree, 100, 50, 0);
+  test_check_generator (&tree, 100, 150, 0);
+  test_check_generator (&tree, 0, 0, 0);
+  test_check_generator (&tree, 40, 40, 0);
+  test_check_generator (&tree, 30, 30, 0);
+  test_check_generator (&tree, 35, 35, 1,
+                        30);
+}
+END_TEST
+
+
+struct interval_node*
+test_create_tree (struct interval_tree *tree, int n,
+                  bool doshuffle, ...)
+{
+  va_list ap;
+  struct interval_node *nodes = calloc (n, sizeof (struct interval_node));
+  int *index = calloc (n, sizeof (int));
+
+  interval_tree_init (tree);
+  va_start (ap, doshuffle);
+  for (int i = 0; i < n; ++i)
+    {
+      ptrdiff_t begin = va_arg (ap, ptrdiff_t);
+      ptrdiff_t end = va_arg (ap, ptrdiff_t);
+      nodes[i].begin = begin;
+      nodes[i].end = end;
+      index[i] = i;
+    }
+  va_end (ap);
+  srand (42);
+  if (doshuffle)
+    shuffle (index, n);
+  for (int i = 0; i < n; ++i)
+    interval_tree_insert (tree, &nodes[index[i]]);
+  free (index);
+
+  return nodes;
+}
+
+START_TEST (test_generator_3)
+{
+  struct interval_tree tree;
+  struct interval_node *nodes = NULL;
+
+  nodes = test_create_tree (&tree, 3, true,
+                            10, 10,
+                            10, 10,
+                            10, 10);
+  test_check_generator (&tree, 0, 10, 0);
+  test_check_generator (&tree, 10, 10, 3, 10, 10, 10);
+  test_check_generator (&tree, 10, 20, 3, 10, 10, 10);
+  free (nodes);
+}
+END_TEST
+
+#define FOREACH(n, g)                                   \
+  for ((n) = interval_generator_next (g); (n) != NULL;  \
+       (n) = interval_generator_next (g))
+
+START_TEST (test_generator_5)
+{
+  struct interval_tree tree;
+  struct interval_node *nodes;
+  struct interval_generator *g;
+  nodes = test_create_tree (&tree, 4, false,
+                            10, 30,
+                            20, 40,
+                            30, 50,
+                            40, 60);
+  g = interval_generator_create (&tree);
+  interval_generator_reset (g, 0, 100, ITREE_PRE_ORDER);
+  for (int i = 0; i < 4; ++i)
+    {
+      struct interval_node *n = interval_generator_next (g);
+      ck_assert (n);
+      switch (i)
+        {
+        case 0: ck_assert_int_eq (20, n->begin); break;
+        case 1: ck_assert_int_eq (10, n->begin); break;
+        case 2: ck_assert_int_eq (30, n->begin); break;
+        case 3: ck_assert_int_eq (40, n->begin); break;
+        }
+    }
+  interval_generator_destroy (g);
+  free (nodes);
+
+}
+END_TEST
+
+START_TEST (test_generator_6)
+{
+  struct interval_tree tree;
+  struct interval_node *nodes;
+  struct interval_generator *g;
+  nodes = test_create_tree (&tree, 4, true,
+                            10, 30,
+                            20, 40,
+                            30, 50,
+                            40, 60);
+  g = interval_generator_create (&tree);
+  interval_generator_reset (g, 0, 100, ITREE_ASCENDING);
+  for (int i = 0; i < 4; ++i)
+    {
+      struct interval_node *n = interval_generator_next (g);
+      ck_assert (n);
+      switch (i)
+        {
+        case 0: ck_assert_int_eq (10, n->begin); break;
+        case 1: ck_assert_int_eq (20, n->begin); break;
+        case 2: ck_assert_int_eq (30, n->begin); break;
+        case 3: ck_assert_int_eq (40, n->begin); break;
+        }
+    }
+  interval_generator_destroy (g);
+  free (nodes);
+
+}
+END_TEST
+
+START_TEST (test_generator_7)
+{
+  struct interval_tree tree;
+  struct interval_node *nodes;
+  struct interval_generator *g;
+  nodes = test_create_tree (&tree, 4, true,
+                            10, 30,
+                            20, 40,
+                            30, 50,
+                            40, 60);
+  g = interval_generator_create (&tree);
+  interval_generator_reset (g, 0, 100, ITREE_DESCENDING);
+  for (int i = 0; i < 4; ++i)
+    {
+      struct interval_node *n = interval_generator_next (g);
+      ck_assert (n);
+      switch (i)
+        {
+        case 0: ck_assert_int_eq (40, n->begin); break;
+        case 1: ck_assert_int_eq (30, n->begin); break;
+        case 2: ck_assert_int_eq (20, n->begin); break;
+        case 3: ck_assert_int_eq (10, n->begin); break;
+        }
+    }
+  interval_generator_destroy (g);
+  free (nodes);
+
+}
+END_TEST
+
+START_TEST (test_generator_8)
+{
+  struct interval_tree tree;
+  struct interval_node *nodes, *n;
+  struct interval_generator *g;
+  nodes = test_create_tree (&tree, 2, false,
+                            20, 30,
+                            40, 50);
+  g = interval_generator_create (&tree);
+  interval_generator_reset (g, 1, 60, ITREE_DESCENDING);
+  n = interval_generator_next (g);
+  ck_assert_int_eq (n->begin, 40);
+  interval_generator_narrow (g, 50, 60);
+  n = interval_generator_next (g);
+  ck_assert (n == NULL);
+  free (nodes);
+}
+END_TEST
+
+
+START_TEST (test_generator_9)
+{
+  struct interval_tree tree;
+  struct interval_node *nodes, *n;
+  struct interval_generator *g;
+  nodes = test_create_tree (&tree, 2, false,
+                            25, 25,
+                            20, 30);
+  g = interval_generator_create (&tree);
+  interval_generator_reset (g, 1, 30, ITREE_DESCENDING);
+  n = interval_generator_next (g);
+  ck_assert_int_eq (n->begin, 25);
+  interval_generator_narrow (g, 25, 35);
+  n = interval_generator_next (g);
+  ck_assert_int_eq (n->begin, 20);
+  free (nodes);
+}
+END_TEST
+
+
+/* +===================================================================================+
+ * | Insert Gap
+ * +===================================================================================+ */
+
+static struct interval_tree gap_tree;
+static struct interval_node gap_node;
+
+#define N_BEG (interval_tree_validate (&gap_tree, &gap_node)->begin)
+#define N_END (interval_tree_validate (&gap_tree, &gap_node)->end)
+
+static void
+test_setup_gap_node (ptrdiff_t begin, ptrdiff_t end,
+                     bool front_advance, bool rear_advance)
+{
+  interval_tree_init (&gap_tree);
+  gap_node.begin = begin;
+  gap_node.end = end;
+  gap_node.front_advance = front_advance;
+  gap_node.rear_advance = rear_advance;
+  interval_tree_insert (&gap_tree, &gap_node);
+}
+
+static void
+test_setup_gap_node_noadvance (ptrdiff_t begin, ptrdiff_t end)
+{
+  test_setup_gap_node (begin, end, false, false);
+}
+
+START_TEST (test_gap_insert_1)
+{
+  test_setup_gap_node (100, 200, false, false);
+  interval_tree_insert_gap (&gap_tree, 100 + 10, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 200 + 20);
+}
+END_TEST
+
+START_TEST (test_gap_insert_2)
+{
+  test_setup_gap_node (100, 200, false, false);
+  interval_tree_insert_gap (&gap_tree, 300, 10);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 200);
+}
+END_TEST
+
+START_TEST (test_gap_insert_3)
+{
+  test_setup_gap_node (100, 200, false, false);
+  interval_tree_insert_gap (&gap_tree, 0, 15);
+  ck_assert_int_eq (N_BEG, 100 + 15);
+  ck_assert_int_eq (N_END, 200 + 15);
+}
+END_TEST
+
+START_TEST (test_gap_insert_4)
+{
+  test_setup_gap_node (100, 200, true, false);
+  interval_tree_insert_gap (&gap_tree, 100, 20);
+  ck_assert_int_eq (N_BEG, 100 + 20);
+  ck_assert_int_eq (N_END, 200 + 20);
+
+}
+END_TEST
+
+START_TEST (test_gap_insert_5)
+{
+  test_setup_gap_node (100, 200, false, false);
+  interval_tree_insert_gap (&gap_tree, 100, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 200 + 20);
+
+}
+END_TEST
+
+START_TEST (test_gap_insert_6)
+{
+  test_setup_gap_node (100, 200, false, true);
+  interval_tree_insert_gap (&gap_tree, 200, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 200 + 20);
+
+}
+END_TEST
+
+START_TEST (test_gap_insert_7)
+{
+  test_setup_gap_node (100, 200, false, false);
+  interval_tree_insert_gap (&gap_tree, 200, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 200);
+
+}
+END_TEST
+
+START_TEST (test_gap_insert_8)
+{
+  test_setup_gap_node (100, 100, true, true);
+  interval_tree_insert_gap (&gap_tree, 100, 20);
+  ck_assert_int_eq (N_BEG, 100 + 20);
+  ck_assert_int_eq (N_END, 100 + 20);
+
+}
+END_TEST
+
+START_TEST (test_gap_insert_9)
+{
+  test_setup_gap_node (100, 100, false, true);
+  interval_tree_insert_gap (&gap_tree, 100, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 100 + 20);
+
+}
+END_TEST
+
+START_TEST (test_gap_insert_10)
+{
+  test_setup_gap_node (100, 100, true, false);
+  interval_tree_insert_gap (&gap_tree, 100, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 100);
+
+}
+END_TEST
+
+START_TEST (test_gap_insert_11)
+{
+  test_setup_gap_node (100, 100, false, false);
+  interval_tree_insert_gap (&gap_tree, 100, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 100);
+
+}
+END_TEST
+
+
+/* +===================================================================================+
+ * | Delete Gap
+ * +===================================================================================+ */
+
+START_TEST (test_gap_delete_1)
+{
+  test_setup_gap_node_noadvance (100, 200);
+  interval_tree_delete_gap (&gap_tree, 100 + 10, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 200 - 20);
+
+}
+END_TEST
+
+START_TEST (test_gap_delete_2)
+{
+  test_setup_gap_node_noadvance (100, 200);
+  interval_tree_delete_gap (&gap_tree, 200 + 10, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 200);
+
+}
+END_TEST
+
+START_TEST (test_gap_delete_3)
+{
+  test_setup_gap_node_noadvance (100, 200);
+  interval_tree_delete_gap (&gap_tree, 200, 20);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 200);
+
+}
+END_TEST
+
+START_TEST (test_gap_delete_4)
+{
+  test_setup_gap_node_noadvance (100, 200);
+  interval_tree_delete_gap (&gap_tree, 100 - 20, 20);
+  ck_assert_int_eq (N_BEG, 100 - 20);
+  ck_assert_int_eq (N_END, 200 - 20);
+
+}
+END_TEST
+
+START_TEST (test_gap_delete_5)
+{
+  test_setup_gap_node_noadvance (100, 200);
+  interval_tree_delete_gap (&gap_tree, 70, 20);
+  ck_assert_int_eq (N_BEG, 100 - 20);
+  ck_assert_int_eq (N_END, 200 - 20);
+
+}
+END_TEST
+
+START_TEST (test_gap_delete_6)
+{
+  test_setup_gap_node_noadvance (100, 200);
+  interval_tree_delete_gap (&gap_tree, 80, 100);
+  ck_assert_int_eq (N_BEG, 80);
+  ck_assert_int_eq (N_END, 100);
+}
+END_TEST
+
+START_TEST (test_gap_delete_7)
+{
+  test_setup_gap_node_noadvance (100, 200);
+  interval_tree_delete_gap (&gap_tree, 120, 100);
+  ck_assert_int_eq (N_BEG, 100);
+  ck_assert_int_eq (N_END, 120);
+}
+END_TEST
+
+START_TEST (test_gap_delete_8)
+{
+  test_setup_gap_node_noadvance (100, 200);
+  interval_tree_delete_gap (&gap_tree, 100 - 20, 200 + 20);
+  ck_assert_int_eq (N_BEG, 100 - 20);
+  ck_assert_int_eq (N_END, 100 - 20);
+
+}
+END_TEST
+
+
+
+Suite * basic_suite ()
+{
+  Suite *s = suite_create ("basic_suite");
+  TCase *tc = tcase_create ("basic_test");
+
+  tcase_add_test (tc, test_insert_1);
+  tcase_add_test (tc, test_insert_2);
+  tcase_add_test (tc, test_insert_3);
+  tcase_add_test (tc, test_insert_4);
+  tcase_add_test (tc, test_insert_5);
+  tcase_add_test (tc, test_insert_6);
+  tcase_add_test (tc, test_insert_7);
+  tcase_add_test (tc, test_insert_8);
+  tcase_add_test (tc, test_insert_9);
+  tcase_add_test (tc, test_insert_10);
+  tcase_add_test (tc, test_insert_11);
+  tcase_add_test (tc, test_insert_12);
+  tcase_add_test (tc, test_insert_13);
+
+  tcase_add_test (tc, test_remove_1);
+  tcase_add_test (tc, test_remove_2);
+  tcase_add_test (tc, test_remove_3);
+  tcase_add_test (tc, test_remove_4);
+  tcase_add_test (tc, test_remove_5);
+  tcase_add_test (tc, test_remove_6);
+  tcase_add_test (tc, test_remove_7);
+  tcase_add_test (tc, test_remove_8);
+  tcase_add_test (tc, test_remove_9);
+  tcase_add_test (tc, test_remove_10);
+
+  tcase_add_test (tc, test_generator_1);
+  tcase_add_test (tc, test_generator_2);
+  tcase_add_test (tc, test_generator_3);
+  tcase_add_test (tc, test_generator_5);
+  tcase_add_test (tc, test_generator_6);
+  tcase_add_test (tc, test_generator_7);
+  tcase_add_test (tc, test_generator_8);
+  tcase_add_test (tc, test_generator_9);
+
+  tcase_add_test (tc, test_gap_insert_1);
+  tcase_add_test (tc, test_gap_insert_2);
+  tcase_add_test (tc, test_gap_insert_3);
+  tcase_add_test (tc, test_gap_insert_4);
+  tcase_add_test (tc, test_gap_insert_5);
+  tcase_add_test (tc, test_gap_insert_6);
+  tcase_add_test (tc, test_gap_insert_7);
+  tcase_add_test (tc, test_gap_insert_8);
+  tcase_add_test (tc, test_gap_insert_9);
+  tcase_add_test (tc, test_gap_insert_10);
+  tcase_add_test (tc, test_gap_insert_11);
+
+  tcase_add_test (tc, test_gap_delete_1);
+  tcase_add_test (tc, test_gap_delete_2);
+  tcase_add_test (tc, test_gap_delete_3);
+  tcase_add_test (tc, test_gap_delete_4);
+  tcase_add_test (tc, test_gap_delete_5);
+  tcase_add_test (tc, test_gap_delete_6);
+  tcase_add_test (tc, test_gap_delete_7);
+  tcase_add_test (tc, test_gap_delete_8);
+
+  /* tcase_set_timeout (tc, 120); */
+  suite_add_tcase (s, tc);
+  return s;
+}
+
+int
+main (void)
+{
+  int nfailed;
+  Suite *s = basic_suite ();
+  SRunner *sr = srunner_create (s);
+
+  srunner_run_all (sr, CK_NORMAL);
+  nfailed = srunner_ntests_failed (sr);
+  srunner_free (sr);
+  return (nfailed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
+}
diff --git a/test/manual/noverlay/many-errors.py b/test/manual/noverlay/many-errors.py
new file mode 100644
index 00000000000..fa4ef5f98d1
--- /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 00000000000..e84941c08f9
--- /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)