Re: Subtle bugs in interval code.

[Kim F. Storm]

Richard Stallman <address@hidden> writes:

>     Studying the code in interval.c for merge_properties and
>     intervals_equal, I noticed that they use Fmemq to search
>     for a given property on a plist.
>
> This is a simple thing, so how about writing an explicit loop in those
> two places, which does exactly the right thing?  No need to make it a
> subroutine.
>
> It probably should not do QUIT;.

Here is a patch which does the search in an explicit loop
in those cases.

Also, it optimizes the code by generally eliminating calls to Fcar and
Fcdr, replacing them with explicit checking with CONSP and the XCAR and
XCDR macros.

It also eliminates the call to Flength in intervals_equal, by
doing the "equal length" check on the fly.

I've not tested this code extensively, but it seems to behave ok.


*** intervals.c 23 Mar 2007 17:03:15 +0100      1.138
--- intervals.c 25 Mar 2007 01:54:14 +0100      
***************
*** 125,142 ****
    while (CONSP (o))
      {
        sym = XCAR (o);
!       val = Fplist_member (target->plist, sym);
  
        if (NILP (val))
        {
-         o = XCDR (o);
-         CHECK_CONS (o);
          val = XCAR (o);
          target->plist = Fcons (sym, Fcons (val, target->plist));
-         o = XCDR (o);
        }
!       else
!       o = Fcdr (XCDR (o));
      }
  }
  
--- 125,144 ----
    while (CONSP (o))
      {
        sym = XCAR (o);
!       o = XCDR (o);
!       CHECK_CONS (o);
! 
!       val = target->plist;
!       while (CONSP (val) && !EQ (XCAR (val), sym))
!       if (val = XCDR (val), CONSP (val))
!         val = XCDR (val);
  
        if (NILP (val))
        {
          val = XCAR (o);
          target->plist = Fcons (sym, Fcons (val, target->plist));
        }
!       o = XCDR (o);
      }
  }
  
***************
*** 147,154 ****
  intervals_equal (i0, i1)
       INTERVAL i0, i1;
  {
!   register Lisp_Object i0_cdr, i0_sym, i1_val;
!   register int i1_len;
  
    if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
      return 1;
--- 149,156 ----
  intervals_equal (i0, i1)
       INTERVAL i0, i1;
  {
!   register Lisp_Object i0_cdr, i0_sym;
!   register Lisp_Object i1_cdr, i1_val;
  
    if (DEFAULT_INTERVAL_P (i0) && DEFAULT_INTERVAL_P (i1))
      return 1;
***************
*** 156,194 ****
    if (DEFAULT_INTERVAL_P (i0) || DEFAULT_INTERVAL_P (i1))
      return 0;
  
-   i1_len = XFASTINT (Flength (i1->plist));
-   if (i1_len & 0x1)           /* Paranoia -- plists are always even */
-     abort ();
-   i1_len /= 2;
    i0_cdr = i0->plist;
!   while (CONSP (i0_cdr))
      {
-       /* Lengths of the two plists were unequal.  */
-       if (i1_len == 0)
-       return 0;
- 
        i0_sym = XCAR (i0_cdr);
!       i1_val = Fplist_member (i1->plist, i0_sym);
  
        /* i0 has something i1 doesn't.  */
        if (EQ (i1_val, Qnil))
        return 0;
  
        /* i0 and i1 both have sym, but it has different values in each.  */
!       i0_cdr = XCDR (i0_cdr);
!       CHECK_CONS (i0_cdr);
!       if (!EQ (Fcar (Fcdr (i1_val)), XCAR (i0_cdr)))
        return 0;
  
        i0_cdr = XCDR (i0_cdr);
!       i1_len--;
      }
  
!   /* Lengths of the two plists were unequal.  */
!   if (i1_len > 0)
!     return 0;
! 
!   return 1;
  }
  
  
--- 158,193 ----
    if (DEFAULT_INTERVAL_P (i0) || DEFAULT_INTERVAL_P (i1))
      return 0;
  
    i0_cdr = i0->plist;
!   i1_cdr = i1->plist;
!   while (CONSP (i0_cdr) && CONSP (i1_cdr))
      {
        i0_sym = XCAR (i0_cdr);
!       if (i0_cdr = XCDR (i0_cdr), !CONSP (i0_cdr))
!       return 0;
!       i1_val = i1->plist;
!       while (CONSP (i1_val) && !EQ (XCAR (i1_val), i0_sym))
!       if (i1_val = XCDR (i1_val), CONSP (i1_val))
!         i1_val = XCDR (i1_val);
  
        /* i0 has something i1 doesn't.  */
        if (EQ (i1_val, Qnil))
        return 0;
  
        /* i0 and i1 both have sym, but it has different values in each.  */
!       if (!CONSP (i1_val)
!         || (i1_val = XCDR (i1_val), !CONSP (i1_val))
!         || !EQ (XCAR (i1_val), XCAR (i0_cdr)))
        return 0;
  
        i0_cdr = XCDR (i0_cdr);
!       if (i1_cdr = XCDR (i1_cdr), !CONSP (i1_cdr))
!       return 0;
!       i1_cdr = XCDR (i1_cdr);
      }
  
!   /* Lengths of the two plists were equal.  */
!   return (NILP (i0_cdr) && NILP (i1_cdr));
  }
  
  

-- 
Kim F. Storm <address@hidden> http://www.cua.dk