all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
From: Stefan Monnier <monnier@iro.umontreal.ca>
To: Matt Armstrong <matt@rfc20.org>
Cc: emacs-devel@gnu.org
Subject: Re: noverlay branch
Date: Mon, 10 Oct 2022 10:44:55 -0400	[thread overview]
Message-ID: <jwva663yf2z.fsf-monnier+emacs@gnu.org> (raw)
In-Reply-To: <87pmf04c7s.fsf@rfc20.org> (Matt Armstrong's message of "Sun, 09 Oct 2022 19:57:43 -0700")

> I had a different idea of tightening the otree invariant to this:
>
>  1) A node's otick must be greater than or equal to its children's.

That's already checked in the current code, right?

>  2) There is no tree->otick, just tree->root->otick.  That is what is
>     incremented when offsets are added.

Sounds good.

>  3) All downward tree traversal propagates offsets and otick.

I think we already do that, but if there are places we missed, then yes,
of course.

Regarding `otick`, I can see 2 more options:
- Get rid of it completely: its sole purpose is to try and keep
  `overlay-start/end` O(1) in the usual case instead of O(log N), but
  I'm not convinced it's worth the cost of propagating `otick` everywhere
  all the time.
- A halfway point is to keep `otick` but update it more lazily,
  i.e. only update it when we do `overlay-start/end` (e.g. in
  `interval_tree_validate`).

> Anyway, thanks for fixing my "thinko" bug in the check_tree code -- I
> had the fix but should have sent it faster.  I didn't actually intend
> for that to be commited yet (pushed it to sr.ht by accident), but maybe
> it helped you chase down the bugs you fixed today?

Yes, pointed out the problem in the tree insertion code, yes.

> Subject: [PATCH 2/2] Add ./configure --enable-checking=overlays

I think this is going overboard.  I'd rather focus on providing good
"everyday checks" (i.e. cheap checks which help document our invariants,
controlled by the normal ENABLE_CHECKING) and leave the rest of the
debugging code under "manual" control rather than expose it as an
`--enable-checking=` option.

My assumption here is that once debugged, this overlay code will stay
untouched for the next many years (based on the past history of our
overlay code).

> +static struct check_subtree_result
> +check_subtree (struct interval_node *node, uintmax_t tree_otick,
> +               int max_depth, ptrdiff_t offset, ptrdiff_t min_begin,
> +               ptrdiff_t max_begin)

This max_depth also sounds to me like over-engineering.

> -  /* We don't check the RB invariants here (neither the absence of
> -     red+red nor the equal-black-depth), so that we can use this check
> -     even while the tree is temporarily breaking some of those invarints.  */
> -  /* Red nodes cannot have red parents.  */
> -  /* eassert (node->parent == ITREE_NULL
> -              || !(node->red && node->parent->red)); */
> +  /* We don't normally check the RB invariants here (neither the
> +     absence of red+red nor the equal-black-depth), so that we can use
> +     this check even while the tree is temporarily breaking some of
> +     those invarints.  You can enable them if you want.  */
> +  if (false)
> +    {
> +      /* If a node is red then both of its children are black.  Red
> +         nodes cannot have red parents.  */
> +      if (node->red)
> +        {
> +          eassert (node->left == ITREE_NULL
> +                   || node->left->red == false);
> +          eassert (node->right == ITREE_NULL
> +                   || node->right->red == false);
> +          eassert (node->parent == ITREE_NULL || !node->parent->red);
> +        }
> +    }

Since we'll be recursing into the children, the first two easserts seem
redundant with the third (IOW the new code just does the same as the old
code, only more verbosely and less efficiently :-( ).
What am I missing?

> +  result.complete = left_result.complete && right_result.complete;
> +  if (result.complete)

I think all calls to `check_tree` should be complete traversals.

Most of the invariants checked in it are already checked incrementally
via sprinkled assertions elsewhere, so it's only really useful when
debugging a concrete known issue where the "local" checks aren't
good enough.

We could also include a few "cheap" calls to `check_tree` via `eassert`
(i.e. calls which we know shouldn't be algorithmically too expensive
because we're already traversing the whole tree for some other reason,
e.g. when killing a buffer (e.g. to verify that, at the end of the day,
we still preversed the RB invariants :-) or maybe during GC).

> +    {
> +      /* Every path from a node to a descendent leaf contains the same
> +         number of black nodes.  Often said this way: all nodes have
> +         the same "black height".  */
> +      eassert (left_result.black_height == right_result.black_height);

IIUC this assertion should be conditionalized in the same way as the
red+red check, since this invariant can be temporarily false.


        Stefan




  parent reply	other threads:[~2022-10-10 14:44 UTC|newest]

Thread overview: 71+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2022-09-25 22:38 noverlay branch Stefan Monnier
2022-09-25 22:50 ` Lars Ingebrigtsen
2022-09-25 22:56   ` Stefan Monnier
2022-09-26  2:52 ` Ihor Radchenko
2022-09-26  3:17   ` Stefan Monnier
2022-09-26  6:11   ` Eli Zaretskii
2022-09-26 13:08     ` Ihor Radchenko
2022-09-26 15:59       ` Eli Zaretskii
     [not found]         ` <87v8ovdosz.fsf@localhost>
2022-10-08  6:57           ` Eli Zaretskii
2022-10-09  3:25             ` Matt Armstrong
2022-10-09  4:30               ` Eli Zaretskii
2022-10-09  3:23           ` Matt Armstrong
2022-10-09  3:47           ` Stefan Monnier
2022-10-13 12:09             ` Ihor Radchenko
2022-09-29 18:12       ` Stefan Monnier
2022-09-27  5:12 ` Matt Armstrong
2022-09-27  6:53   ` Eli Zaretskii
2022-09-27 17:31     ` Matt Armstrong
2022-09-27 18:45       ` Stefan Monnier
2022-09-28 23:09   ` Stefan Monnier
2022-09-29 14:54     ` Gerd Möllmann
2022-09-29 21:36       ` Stefan Monnier
2022-09-30  5:20         ` Gerd Möllmann
2022-10-06  4:47         ` Matt Armstrong
2022-10-06  5:43           ` Gerd Möllmann
2022-10-07  4:11             ` Matt Armstrong
2022-10-07  4:34               ` Gerd Möllmann
2022-10-07 13:33                 ` Stefan Monnier
2022-10-07 14:29                   ` Gerd Möllmann
2022-10-07 14:51                     ` Stefan Monnier
2022-10-07 15:12                       ` Gerd Möllmann
2022-10-07 17:12                         ` Stefan Monnier
2022-10-07 14:56                   ` Stefan Monnier
2022-10-07 15:59                   ` Matt Armstrong
2022-10-07 15:34                 ` Matt Armstrong
2022-10-06 12:08           ` Stefan Monnier
2022-09-27  8:39 ` Gerd Möllmann
2022-09-27  9:38   ` Eli Zaretskii
2022-10-06 20:41 ` Matt Armstrong
2022-10-07 16:51 ` Matt Armstrong
2022-10-07 18:28   ` Stefan Monnier
2022-10-08 23:33     ` Matt Armstrong
2022-10-09  3:44       ` Matt Armstrong
2022-10-09  4:12       ` Stefan Monnier
2022-10-09 15:34         ` Stefan Monnier
2022-10-10  2:57           ` Matt Armstrong
2022-10-10  6:24             ` Eli Zaretskii
2022-10-10 16:26               ` Matt Armstrong
2022-10-10 14:44             ` Stefan Monnier [this message]
2022-10-11  3:46               ` Matt Armstrong
2022-10-11  4:09                 ` Stefan Monnier
2022-10-11 18:02                   ` Matt Armstrong
2022-10-11 18:59                     ` Stefan Monnier
2022-10-12  5:18                       ` Matt Armstrong
2022-10-12 18:02                         ` Stefan Monnier
2022-10-12 22:26                           ` Matt Armstrong
2022-10-13  4:03                             ` Stefan Monnier
2022-10-09 23:47       ` Stefan Monnier
2022-10-10  0:05         ` Emanuel Berg
2022-10-10 16:27           ` Matt Armstrong
2022-10-10 16:33         ` Matt Armstrong
2022-10-10 18:32           ` Matt Armstrong
2022-10-11 16:06             ` Stefan Monnier
2022-10-12 17:33               ` Matt Armstrong
2022-10-13  3:59                 ` Stefan Monnier
2022-10-16 21:53                   ` Matt Armstrong
2022-10-23  4:49 ` Matt Armstrong
2022-10-24  9:14   ` Stefan Kangas
2022-10-24 16:21     ` Matt Armstrong
2022-10-24 12:51   ` Eli Zaretskii
2022-10-25 20:57     ` Dmitry Gutov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=jwva663yf2z.fsf-monnier+emacs@gnu.org \
    --to=monnier@iro.umontreal.ca \
    --cc=emacs-devel@gnu.org \
    --cc=matt@rfc20.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.