Re: Intervals crash

[Eli Zaretskii <eliz@gnu.org>]

> From: Chong Yidong <cyd@stupidchicken.com>
> Date: Thu, 23 Sep 2010 14:23:24 -0400
> Cc: emacs-devel@gnu.org
> 
> The LENGTH macro in intervals.h:114 has to be able to return a negative
> number.

Given this information, I find it difficult to reconcile the facts
with the code.  The implementation does this:

  struct interval
  {
    /* The first group of entries deal with the tree structure.  */

    EMACS_UINT total_length;      /* Length of myself and both children.  */
    EMACS_UINT position;	  /* Cache of interval's character position.  */
    ...

  /* The total size of all text represented by this interval and all its
     children in the tree.   This is zero if the interval is null. */
  #define TOTAL_LENGTH(i) ((i) == NULL_INTERVAL ? 0 : (i)->total_length)

  /* The size of text represented by this interval alone. */
  #define LENGTH(i) ((i) == NULL_INTERVAL ? 0 : (TOTAL_LENGTH ((i))          \
						 - TOTAL_LENGTH ((i)->right) \
						 - TOTAL_LENGTH ((i)->left)))

If total_length is an unsigned type, then computing negative values
from unsigned values is asking for trouble, no?  The above definitions
led me to believe that using EMACS_UINT for the result of LENGTH would
be safe, because, I reasoned, no one in their right minds would
otherwise use an unsigned type.

Also, the comment in the code that crashes:

  EMACS_INT amt = LENGTH (i);

  if (amt > 0)			/* Only used on zero-length intervals now.  */
    abort ();

lies through its teeth, doesn't it?  It implies that the result of
LENGTH is always non-negative, which again convinced me that my
understanding is correct.  But the crash says otherwise.

In addition, the commentary to delete_interval says:

  /* Delete interval I from its tree by calling `delete_node'
     and properly connecting the resultant subtree.

     I is presumed to be empty; that is, no adjustments are made
     for the length of I.  */

"I is presumed to be empty."  Is that also a lie?  Or is the code
buggy, and using an unsigned type simply exposed those bugs?

If the code is correct and the comments are wrong, I'd say we should
fix the comments, and make total_length a signed type (EMACS_INT).

Opinions and insights are most welcome.