Re: noverlay branch

[Matt Armstrong]

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

> Matt Armstrong [2022-10-07 09:51:32] wrote:
>> Stefan Monnier <monnier@iro.umontreal.ca> writes:
>>> I just updated the noverlay branch to the code in `master` (most of it
>>> was mechanical except for the fact that since the last commit on that
>>> branch we have gotten rid of Lisp_Misc and we moved to pdumper).
>>>
>>> I'm getting ready to install this in `master`, so I'd encourage people
>>> to try this code as much as possible to try and weed out the most
>>> glaring problems before it hits master.
>>
>> Stefan (and others), where are we at with this?  Are there things that
>> must happen before a merge?
>
> I'm mainly waiting to hear feedback (including my own) about "I use it
> with no visible problem".

I like that criteria.  :)

>> Is anybody able to use the noverlay branch for daily work?
>
> I do.
>
>> I'm running the noverlay branch now and was observing an eassume
>> failure.
>
> Do you have the file&line number at least?

Not the specific eassert because...reasons.  Long story short: I can
debug eassert failures now, but not then.

In any case, I do have a new test for tests/src/buffer-tests.el that
crashes feature/noverlay Emacs immediately, when ENABLE_CHECKING is on,
in a spot in itree.c having to do with offset inheritance.

Two patches, also on https://git.sr.ht/~matta/emacs/log/feature/noverlay
as before.  I'll work on fixing the crash next, but wanted to get the
test in because it takes an...interesting approach...that may require
discussion.

>From 87204feaa4f50744701481f3aa051483647cf9da Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sat, 8 Oct 2022 09:15:26 -0700
Subject: [PATCH 1/2] Comment change: explain inheriting "dirty" offsets

; * src/itree.c (interval_generator_next): explain why the code
handles inheriting offsets from dirty nodes.
---
 src/itree.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/src/itree.c b/src/itree.c
index de16af5b0c..1fc711b021 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -1086,9 +1086,17 @@ interval_tree_inherit_offset (uintmax_t otick, struct 
interval_node *node)
         node->right->offset += node->offset;
       node->offset = 0;
     }
-  /* FIXME: I wonder when/why this condition can be false, and more generally
-     why we'd want to propagate offsets that may not be fully up-to-date.  */
-  if (node->parent == ITREE_NULL || node->parent->otick == otick)
+  /* FIXME: I wonder when/why this condition can be false, and more
+     generally why we'd want to propagate offsets that may not be
+     fully up-to-date. --stef
+
+     Offsets can be inherited from dirty nodes (with out of date
+     otick) during insert and remove.  Offsets aren't inherited
+     downward from the root for these operations so rotations are
+     performed on potentially "dirty" nodes.  We could fix this by
+     always inheriting offsets downward from the root for every insert
+     and remove.  --matt
+  */
     node->otick = otick;
 }
 
-- 
2.35.1

>From 89ed5cbee03cce6c621af6570d2c4411e7586f9d Mon Sep 17 00:00:00 2001
From: Matt Armstrong <matt@rfc20.org>
Date: Sat, 8 Oct 2022 09:28:29 -0700
Subject: [PATCH 2/2] ; * test/src/buffer-tests.el (test-overlay-randomly): new
 test.

---
 test/src/buffer-tests.el | 92 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 92 insertions(+)

diff --git a/test/src/buffer-tests.el b/test/src/buffer-tests.el
index a12d15bc79..46e57289a1 100644
--- a/test/src/buffer-tests.el
+++ b/test/src/buffer-tests.el
@@ -1508,6 +1508,98 @@ test-overlay-multibyte-transition-2
         (ovshould nonempty-eob-end 4 5)
         (ovshould empty-eob        5 5)))))
 
+(ert-deftest test-overlay-randomly ()
+  "Exercise overlay code, but perform few assertions.
+
+This test works best when Emacs is configured with
+--enable-checking=yes.  This is a little bit like fuzz testing,
+except this test has no way to reduce to a minimal failng test
+case.  Regardless, by exercising many corner cases bugs can be
+found using Emacs' internal consistency assertions."
+  (let* (
+         ;; The size and slack for the test buffer size.
+         (buffer-size-target 1000)
+         (buffer-size-slack 200)
+
+         ;; Use up to 100 overlays.  We need not use more to observe
+         ;; reasonable variation in the overlay data structures.
+         (overlay-count-limit 100)
+
+         ;; This test maintains a vector of overlays.  Each iteration
+         ;; may append or erase one overlay.
+         (overlays (make-vector overlay-count-limit nil))
+         (overlay-count 0)
+
+         ;; The test is either slowly growing or shrinking the overlay
+         ;; count.  Deletions still occur while growing, and additions
+         ;; still occur while shrinking.  The GROWING variable only
+         ;; controls the relative probability of doing one or the
+         ;; other.
+         (growing t)
+
+         ;; Loop up to 100K times.
+         (iteration-count 0)
+         (iteration-target 100000))
+    (with-temp-buffer
+      (while (< (buffer-size) buffer-size-target)
+        (insert "Sed ut perspiciatis, unde omnis iste natus error sit 
voluptatem
+accusantium doloremque laudantium, totam rem aperiam eaque ipsa,
+quae ab illo inventore veritatis et quasi architecto beatae vitae
+dicta sunt, explicabo.  "))
+
+      (while (< iteration-count iteration-target)
+        (cl-incf iteration-count)
+
+        ;; Toggle GROWING if we've reached a size boundary.  The idea
+        ;; is to initially steadily increase the overlay count, then
+        ;; steadily decrease it, then repeat.
+        (when (and growing (= overlay-count overlay-count-limit))
+          (message "now shrinking")
+          (setq growing nil))
+        (when (and (not growing) (= overlay-count 0))
+          (message "now growing")
+          (setq growing t))
+
+        ;; Create or delete a random overlay according to a
+        ;; probability chosen by GROWING.
+        (let ((create-overlay (>= (random 100) (if growing 40 60))))
+          (cond
+           ;; Possibly create a new overlay in a random place in the
+           ;; buffer.  We have two easy choices.  We can choose the
+           ;; overlay BEGIN randomly, then choose its END among the
+           ;; valid remaining buffer posiitions.  Or we could choose
+           ;; the overlay width randomly, then choose a valid BEGIN.
+           ;; We take the former approach, because the overlay data
+           ;; structure is ordered primarily by BEGIN.
+           ((and create-overlay (< overlay-count overlay-count-limit))
+            (let* ((begin (random (buffer-size)))
+                   (end (+ begin (random (- (buffer-size) begin))))
+                   (ov (make-overlay begin end nil
+                                     (= 0 (random 2)) (= 0 (random 2)))))
+              (aset overlays overlay-count ov)
+              (cl-incf overlay-count)))
+           ((and (not create-overlay) (> overlay-count 0))
+
+            ;; Possibly delete a random overlay.
+            (let* ((last-index (1- overlay-count))
+                   (index (random overlay-count))
+                   (ov (aref overlays index)))
+              (when (< index last-index)
+                (aset overlays index (aref overlays last-index)))
+              (aset overlays last-index nil)
+              (cl-decf overlay-count)
+              (delete-overlay ov)))))
+
+        ;; Modify the buffer on occasion, which exercises the
+        ;; insert/remove gap logic in the overlay implementation.
+        (when (and (< (buffer-size) (+ buffer-size-target buffer-size-slack))
+                   (zerop (random 10)))
+          (goto-char (1+ (random (buffer-size))))
+          (insert (+ ?a (random 26))))
+        (when (and (> (buffer-size) (- buffer-size-target buffer-size-slack))
+                   (zerop (random 10)))
+          (goto-char (1+ (random (buffer-size))))
+          (delete-char 1))))))
 
 
 
-- 
2.35.1