feature/noverlay 7cbeeabc7e: Tighten up handling of `otick`

[Stefan Monnier]

branch: feature/noverlay
commit 7cbeeabc7e6271948e7bb93020c2e4e50c65f384
Author: Stefan Monnier <monnier@iro.umontreal.ca>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>

    Tighten up handling of `otick`
    
    Move args between `build_overlay` and `add_buffer_overlay`,
    to try and keep buffer positions together with their buffer.
    Be more strict in the `otick` values passed to `interval_tree_insert`.
    Move a few things around to try and reduce dependencies through `.h` files.
    Fix a thinko bug in `check_tree`.
    
    * src/alloc.c (build_overlay): Remove `begin` and `end` args.
    
    * src/buffer.c (add_buffer_overlay): Move from `buffer.h`.
    Add `begin` and `end` args.
    (copy_overlays): Adjust accordingly.
    (Fmake_overlay): Use BUF_BEG and BUF_Z; adjust call to `build_overlay`
    and `add_buffer_overlay`.
    (Fmove_overlay): Use BUF_BEG and BUF_Z; Use the new `begin` and `end`
    args of `add_buffer_overlay` so we don't need to use
    `interval_node_set_region` when moving to a new buffer.
    (remove_buffer_overlay, set_overlay_region): Move from `buffer.h`.
    
    * src/buffer.h (set_overlay_region, add_buffer_overlay)
    (remove_buffer_overlay): Move to `buffer.c`.
    (build_overlay): Move from `lisp.h`.
    (maybe_alloc_buffer_overlays): Delete function (inline into its only
    caller).
    
    * src/itree.c (interval_tree_insert): Move declaration `from buffer.h`.
    (check_tree): Fix initial offset in call to `recurse_check_tree`.
    Remove redundant check of the `limit` value.
    (interval_node_init): Remove `begin` and `end` args.
    (interval_tree_insert): Mark it as static.
    Assert that the new node's `otick` should already be uptodate and its
    new parent as well.
    (itree_insert_node): New function.
    (interval_tree_insert_gap): Assert the otick of the removed+added nodes
    were uptodate and mark them as uptodate again after adjusting
    their positions.
    (interval_tree_inherit_offset): Check that the parent is at least as
    uptodate as the child.
    
    * src/lisp.h (build_overlay): Move to `buffer.h`.
    
    * src/itree.h (interval_node_init): Adjust accordingly.
    (interval_tree_insert): Remove declaration.
    (itree_insert_node): New declaration.
---
 src/alloc.c  |  8 +++-----
 src/buffer.c | 58 ++++++++++++++++++++++++++++++++++++++++++----------------
 src/buffer.h | 35 +----------------------------------
 src/itree.c  | 55 ++++++++++++++++++++++++++++++++++---------------------
 src/itree.h  |  5 +++--
 src/lisp.h   |  1 -
 6 files changed, 83 insertions(+), 79 deletions(-)

diff --git a/src/alloc.c b/src/alloc.c
index 50968b7e12..00f2991f25 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3702,19 +3702,17 @@ build_symbol_with_pos (Lisp_Object symbol, Lisp_Object 
position)
   return val;
 }
 
-/* Return a new overlay with specified START, END and PLIST.  */
+/* Return a new (deleted) overlay with PLIST.  */
 
 Lisp_Object
-build_overlay (ptrdiff_t begin, ptrdiff_t end,
-               bool front_advance, bool rear_advance,
+build_overlay (bool front_advance, bool rear_advance,
                Lisp_Object plist)
 {
   struct Lisp_Overlay *p = ALLOCATE_PSEUDOVECTOR (struct Lisp_Overlay, plist,
                                                  PVEC_OVERLAY);
   Lisp_Object overlay = make_lisp_ptr (p, Lisp_Vectorlike);
   struct interval_node *node = xmalloc (sizeof (*node));
-  interval_node_init (node, begin, end, front_advance,
-                      rear_advance, overlay);
+  interval_node_init (node, front_advance, rear_advance, overlay);
   p->interval = node;
   p->buffer = NULL;
   set_overlay_plist (overlay, plist);
diff --git a/src/buffer.c b/src/buffer.c
index f59fddcbde..e1303f2a88 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -638,6 +638,16 @@ even if it is dead.  The return value is never nil.  */)
   return buffer;
 }
 
+static void
+add_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov,
+                    ptrdiff_t begin, ptrdiff_t end)
+{
+  eassert (! ov->buffer);
+  if (! b->overlays)
+    b->overlays = interval_tree_create ();
+  ov->buffer = b;
+  itree_insert_node (b->overlays, ov->interval, begin, end);
+}
 
 /* Copy overlays of buffer FROM to buffer TO.  */
 
@@ -650,11 +660,10 @@ copy_overlays (struct buffer *from, struct buffer *to)
   ITREE_FOREACH (node, from->overlays, PTRDIFF_MIN, PTRDIFF_MAX, ASCENDING)
     {
       Lisp_Object ov = node->data;
-      Lisp_Object copy = build_overlay (node->begin, node->end,
-                                        node->front_advance,
+      Lisp_Object copy = build_overlay (node->front_advance,
                                         node->rear_advance,
                                         Fcopy_sequence (OVERLAY_PLIST (ov)));
-      add_buffer_overlay (to, XOVERLAY (copy));
+      add_buffer_overlay (to, XOVERLAY (copy), node->begin, node->end);
     }
 }
 
@@ -897,6 +906,15 @@ does not run the hooks `kill-buffer-hook',
   return buf;
 }
 
+static void
+remove_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov)
+{
+  eassert (b->overlays);
+  eassert (ov->buffer == b);
+  interval_tree_remove (ov->buffer->overlays, ov->interval);
+  ov->buffer = NULL;
+}
+
 /* Mark OV as no longer associated with its buffer.  */
 
 static void
@@ -3486,12 +3504,11 @@ for the rear of the overlay advance when text is 
inserted there
       temp = beg; beg = end; end = temp;
     }
 
-  ptrdiff_t obeg = clip_to_bounds (BEG, XFIXNUM (beg), b->text->z);
-  ptrdiff_t oend = clip_to_bounds (obeg, XFIXNUM (end), b->text->z);
-  ov = build_overlay (obeg, oend,
-                      ! NILP (front_advance),
+  ptrdiff_t obeg = clip_to_bounds (BUF_BEG (b), XFIXNUM (beg), BUF_Z (b));
+  ptrdiff_t oend = clip_to_bounds (obeg, XFIXNUM (end), BUF_Z (b));
+  ov = build_overlay (! NILP (front_advance),
                       ! NILP (rear_advance), Qnil);
-  add_buffer_overlay (b, XOVERLAY (ov));
+  add_buffer_overlay (b, XOVERLAY (ov), obeg, oend);
 
   /* We don't need to redisplay the region covered by the overlay, because
      the overlay has no properties at the moment.  */
@@ -3518,6 +3535,15 @@ modify_overlay (struct buffer *buf, ptrdiff_t start, 
ptrdiff_t end)
   modiff_incr (&BUF_OVERLAY_MODIFF (buf), 1);
 }
 
+INLINE void
+set_overlay_region (struct Lisp_Overlay *ov, ptrdiff_t begin, ptrdiff_t end)
+{
+  eassert (ov->buffer);
+  begin = clip_to_bounds (BEG, begin, ov->buffer->text->z);
+  end = clip_to_bounds (begin, end, ov->buffer->text->z);
+  interval_node_set_region (ov->buffer->overlays, ov->interval, begin, end);
+}
+
 DEFUN ("move-overlay", Fmove_overlay, Smove_overlay, 3, 4, 0,
        doc: /* Set the endpoints of OVERLAY to BEG and END in BUFFER.
 If BUFFER is omitted, leave OVERLAY in the same buffer it inhabits now.
@@ -3528,7 +3554,6 @@ buffer.  */)
   struct buffer *b, *ob = 0;
   Lisp_Object obuffer;
   specpdl_ref count = SPECPDL_INDEX ();
-  ptrdiff_t n_beg, n_end;
   ptrdiff_t o_beg UNINIT, o_end UNINIT;
 
   CHECK_OVERLAY (overlay);
@@ -3555,11 +3580,14 @@ buffer.  */)
       temp = beg; beg = end; end = temp;
     }
 
-  specbind (Qinhibit_quit, Qt);
+  specbind (Qinhibit_quit, Qt); /* FIXME: Why?  */
 
   obuffer = Foverlay_buffer (overlay);
   b = XBUFFER (buffer);
 
+  ptrdiff_t n_beg = clip_to_bounds (BUF_BEG (b), XFIXNUM (beg), BUF_Z (b));
+  ptrdiff_t n_end = clip_to_bounds (n_beg, XFIXNUM (end), BUF_Z (b));
+
   if (!NILP (obuffer))
     {
       ob = XBUFFER (obuffer);
@@ -3572,13 +3600,11 @@ buffer.  */)
     {
       if (! NILP (obuffer))
         remove_buffer_overlay (XBUFFER (obuffer), XOVERLAY (overlay));
-      add_buffer_overlay (XBUFFER (buffer), XOVERLAY (overlay));
+      add_buffer_overlay (XBUFFER (buffer), XOVERLAY (overlay), n_beg, n_end);
     }
-  /* Set the overlay boundaries, which may clip them.  */
-  set_overlay_region (XOVERLAY (overlay), XFIXNUM (beg), XFIXNUM (end));
-
-  n_beg = OVERLAY_START (overlay);
-  n_end = OVERLAY_END (overlay);
+  else
+    interval_node_set_region (b->overlays, XOVERLAY (overlay)->interval,
+                              n_beg, n_end);
 
   /* If the overlay has changed buffers, do a thorough redisplay.  */
   if (!BASE_EQ (buffer, obuffer))
diff --git a/src/buffer.h b/src/buffer.h
index a4e3934cad..288acd4f5e 100644
--- a/src/buffer.h
+++ b/src/buffer.h
@@ -1189,6 +1189,7 @@ extern void fix_overlays_before (struct buffer *, 
ptrdiff_t, ptrdiff_t);
 extern void mmap_set_vars (bool);
 extern void restore_buffer (Lisp_Object);
 extern void set_buffer_if_live (Lisp_Object);
+extern Lisp_Object build_overlay (bool, bool, Lisp_Object);
 
 /* Return B as a struct buffer pointer, defaulting to the current buffer.  */
 
@@ -1408,40 +1409,6 @@ overlay_end (struct Lisp_Overlay *ov)
   return interval_node_end (ov->buffer->overlays, ov->interval);
 }
 
-INLINE void
-set_overlay_region (struct Lisp_Overlay *ov, ptrdiff_t begin, ptrdiff_t end)
-{
-  eassert (ov->buffer);
-  begin = clip_to_bounds (BEG, begin, ov->buffer->text->z);
-  end = clip_to_bounds (begin, end, ov->buffer->text->z);
-  interval_node_set_region (ov->buffer->overlays, ov->interval, begin, end);
-}
-
-INLINE void
-maybe_alloc_buffer_overlays (struct buffer *b)
-{
-  if (! b->overlays)
-    b->overlays = interval_tree_create ();
-}
-
-INLINE void
-add_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov)
-{
-  eassert (! ov->buffer);
-  maybe_alloc_buffer_overlays (b);
-  ov->buffer = b;
-  interval_tree_insert (b->overlays, ov->interval);
-}
-
-INLINE void
-remove_buffer_overlay (struct buffer *b, struct Lisp_Overlay *ov)
-{
-  eassert (b->overlays);
-  eassert (ov->buffer == b);
-  interval_tree_remove (ov->buffer->overlays, ov->interval);
-  ov->buffer = NULL;
-}
-
 /* Return the start of OV in its buffer, or -1 if OV is not associated
    with any buffer.  */
 
diff --git a/src/itree.c b/src/itree.c
index b57c3cc656..bbab70dac7 100644
--- a/src/itree.c
+++ b/src/itree.c
@@ -142,6 +142,7 @@ static void interval_tree_rotate_right (struct 
interval_tree *, struct interval_
 static void interval_tree_insert_fix (struct interval_tree *, struct 
interval_node *);
 static void interval_tree_transplant (struct interval_tree *, struct 
interval_node *, struct interval_node *);
 static struct interval_generator* interval_generator_create (struct 
interval_tree *);
+static void interval_tree_insert (struct interval_tree *, struct interval_node 
*);
 
 /* The sentinel node, the null node.  */
 struct interval_node itree_null;
@@ -260,11 +261,8 @@ check_tree (struct interval_tree *tree)
     return true;
 
   intmax_t size = 0;
-  ptrdiff_t offset = tree->root->offset;
-  ptrdiff_t limit
-    = recurse_check_tree (tree->root, tree->otick, offset,
-                          PTRDIFF_MIN, PTRDIFF_MAX, &size);
-  eassert (limit == tree->root->limit + offset);
+  recurse_check_tree (tree->root, tree->otick, 0,
+                      PTRDIFF_MIN, PTRDIFF_MAX, &size);
   return true;
 }
 
@@ -375,12 +373,11 @@ interval_stack_pop (struct interval_stack *stack)
 
 void
 interval_node_init (struct interval_node *node,
-                    ptrdiff_t begin, ptrdiff_t end,
                     bool front_advance, bool rear_advance,
                     Lisp_Object data)
 {
-  node->begin = begin;
-  node->end = max (begin, end);
+  node->begin = -1;
+  node->end = -1;
   node->front_advance = front_advance;
   node->rear_advance = rear_advance;
   node->data = data;
@@ -488,7 +485,7 @@ interval_tree_size (struct interval_tree *tree)
    Note, that inserting a node twice results in undefined behaviour.
 */
 
-void
+static void
 interval_tree_insert (struct interval_tree *tree, struct interval_node *node)
 {
   eassert (node && node->begin <= node->end && node != ITREE_NULL);
@@ -497,6 +494,9 @@ interval_tree_insert (struct interval_tree *tree, struct 
interval_node *node)
   struct interval_node *parent = ITREE_NULL;
   struct interval_node *child = tree->root;
   uintmax_t otick = tree->otick;
+  /* It's the responsability of the caller to set `otick` on the node,
+     to "confirm" that the begin/end fields are uptodate.  */
+  eassert (node->otick == otick);
 
   /* Find the insertion point, accumulate node's offset and update
      ancestors limit values.  */
@@ -526,7 +526,7 @@ interval_tree_insert (struct interval_tree *tree, struct 
interval_node *node)
   node->red = true;
   node->offset = 0;
   node->limit = node->end;
-  node->otick = otick;
+  eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick);
 
   /* Fix/update the tree */
   ++tree->size;
@@ -534,6 +534,16 @@ interval_tree_insert (struct interval_tree *tree, struct 
interval_node *node)
   interval_tree_insert_fix (tree, node);
 }
 
+void
+itree_insert_node (struct interval_tree *tree, struct interval_node *node,
+                   ptrdiff_t begin, ptrdiff_t end)
+{
+  node->begin = begin;
+  node->end = end;
+  node->otick = tree->otick;
+  interval_tree_insert (tree, node);
+}
+
 /* Return true, if NODE is a member of TREE. */
 
 static bool
@@ -849,6 +859,7 @@ interval_tree_insert_gap (struct interval_tree *tree, 
ptrdiff_t pos, ptrdiff_t l
 {
   if (length <= 0 || tree->root == ITREE_NULL)
     return;
+  uintmax_t ootick = tree->otick;
 
   /* FIXME: Don't allocate generator/stack anew every time. */
 
@@ -907,13 +918,16 @@ interval_tree_insert_gap (struct interval_tree *tree, 
ptrdiff_t pos, ptrdiff_t l
     }
 
   /* Reinsert nodes starting at POS having front-advance. */
+  uintmax_t notick = tree->otick;
   nodeptr_and_flag nav;
   while ((nav = interval_stack_pop (saved),
           node = nav_nodeptr (nav)))
     {
+      eassert (node->otick == ootick);
       node->begin += length;
       if (node->end != pos || node->rear_advance)
         node->end += length;
+      node->otick = notick;
       interval_tree_insert (tree, node);
     }
 
@@ -1123,12 +1137,19 @@ interval_tree_update_limit (struct interval_node *node)
 static void
 interval_tree_inherit_offset (uintmax_t otick, struct interval_node *node)
 {
+  eassert (node->parent == ITREE_NULL || node->parent->otick >= node->otick);
   if (node->otick == otick)
     {
       eassert (node->offset == 0);
       return;
     }
 
+  /* 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, where we only make sure
+     the *local* offsets are all zero.  */
+
   if (node->offset)
     {
       node->begin += node->offset;
@@ -1140,17 +1161,9 @@ 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. --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
-  */
+  /* The only thing that matters about `otick` is whether it's equal to
+     that of the tree.  We could also "blindly" inherit from parent->otick,
+     but we need to tree's `otick` anyway for when there's no parent.  */
   if (node->parent == ITREE_NULL || node->parent->otick == otick)
     node->otick = otick;
 }
diff --git a/src/itree.h b/src/itree.h
index 7fdc9c07c9..5733ec1530 100644
--- a/src/itree.h
+++ b/src/itree.h
@@ -112,7 +112,7 @@ enum interval_tree_order {
   ITREE_PRE_ORDER,
 };
 
-void interval_node_init (struct interval_node *, ptrdiff_t, ptrdiff_t, bool, 
bool, Lisp_Object);
+void interval_node_init (struct interval_node *, bool, bool, Lisp_Object);
 ptrdiff_t interval_node_begin (struct interval_tree *, struct interval_node *);
 ptrdiff_t interval_node_end (struct interval_tree *, struct interval_node *);
 void interval_node_set_region (struct interval_tree *, struct interval_node *, 
ptrdiff_t, ptrdiff_t);
@@ -120,7 +120,8 @@ struct interval_tree *interval_tree_create (void);
 void interval_tree_destroy (struct interval_tree *);
 intmax_t interval_tree_size (struct interval_tree *);
 void interval_tree_clear (struct interval_tree *);
-void interval_tree_insert (struct interval_tree *, struct interval_node *);
+void itree_insert_node (struct interval_tree *tree, struct interval_node *node,
+                        ptrdiff_t begin, ptrdiff_t end);
 struct interval_node *interval_tree_remove (struct interval_tree *, struct 
interval_node *);
 struct interval_generator *interval_tree_iter_start (struct interval_tree *, 
ptrdiff_t, ptrdiff_t, enum interval_tree_order,
                               const char* file, int line);
diff --git a/src/lisp.h b/src/lisp.h
index 7d838afb5c..7cd7871281 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -4415,7 +4415,6 @@ extern Lisp_Object make_float (double);
 extern void display_malloc_warning (void);
 extern specpdl_ref inhibit_garbage_collection (void);
 extern Lisp_Object build_symbol_with_pos (Lisp_Object, Lisp_Object);
-extern Lisp_Object build_overlay (ptrdiff_t, ptrdiff_t, bool, bool, 
Lisp_Object);
 extern void free_cons (struct Lisp_Cons *);
 extern void init_alloc_once (void);
 extern void init_alloc (void);