Subtle bugs in interval code.

Subtle bugs in interval code.

[Kim F. Storm]

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.

That's not a safe way to do that;

E.g. consider a plist like this:

(setq p '(a b c d))

Now,

 (plist-get p 'a) => b
 (plist-get p 'b) => nil

whereas

 (memq 'a p) => (a b c d)
 (memq 'b p) => (b c d)   !=   nil

So due to the use of Fmemq, the interval code may wrongly assume that
the plist has a `b' member with a value of `c'.

I'm not aware of any specific bugs related to this.

Note that we cannot just use plist-get instead of memq, as we then
cannot differentiate between "property is on list with nil value"
and "property is not on list".

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

Re: Subtle bugs in interval code.

[David Kastrup]

storm@cua.dk (Kim F. Storm) 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.
>
> That's not a safe way to do that;
>
> E.g. consider a plist like this:
>
> (setq p '(a b c d))
>
> Now,
>
>  (plist-get p 'a) => b
>  (plist-get p 'b) => nil
>
> whereas
>
>  (memq 'a p) => (a b c d)
>  (memq 'b p) => (b c d)   !=   nil
>
> So due to the use of Fmemq, the interval code may wrongly assume that
> the plist has a `b' member with a value of `c'.
>
> I'm not aware of any specific bugs related to this.
>
> Note that we cannot just use plist-get instead of memq, as we then
> cannot differentiate between "property is on list with nil value"
> and "property is not on list".

One could check whether the length of the rest sequence is even.

The cleanest option might be to add an optional DEFAULT argument to
plist-get, but that would require changes to all C level callers.
Maybe one should add an explicit plist-get-default function that takes
the default for non-existing elements from its third argument?

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: Subtle bugs in interval code.

[Kim F. Storm]

David Kastrup <dak@gnu.org> writes:

> storm@cua.dk (Kim F. Storm) 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.
>>
>> That's not a safe way to do that;
>>
>> E.g. consider a plist like this:
>>
>> (setq p '(a b c d))
>>
>> Now,
>>
>>  (plist-get p 'a) => b
>>  (plist-get p 'b) => nil
>>
>> whereas
>>
>>  (memq 'a p) => (a b c d)
>>  (memq 'b p) => (b c d)   !=   nil
>>
>> So due to the use of Fmemq, the interval code may wrongly assume that
>> the plist has a `b' member with a value of `c'.
>>
>> I'm not aware of any specific bugs related to this.
>>
>> Note that we cannot just use plist-get instead of memq, as we then
>> cannot differentiate between "property is on list with nil value"
>> and "property is not on list".
>
> One could check whether the length of the rest sequence is even.

Not really.  Consider:

(memq 'b '(a b b c)) => (b b c)

> The cleanest option might be to add an optional DEFAULT argument to
> plist-get, but that would require changes to all C level callers.

No good!

> Maybe one should add an explicit plist-get-default function that takes
> the default for non-existing elements from its third argument?

That might work if you can advice on a default value that will
never be a valid element value of any relevant plist...

A version of memq which skips every 2nd element would work always!

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

Re: Subtle bugs in interval code.

[Johan Bockgård]

storm@cua.dk (Kim F. Storm) writes:

> Note that we cannot just use plist-get instead of memq, as we then
> cannot differentiate between "property is on list with nil value"
> and "property is not on list".

    plist-member is a built-in function in `src/fns.c'.
    (plist-member plist prop)

    Return non-nil if plist has the property prop.
    plist is a property list, which is a list of the form
    (PROP1 VALUE1 PROP2 VALUE2 ...).  prop is a symbol.
    Unlike `plist-get', this allows you to distinguish between a missing
    property and a property with the value nil.
    The value is actually the tail of plist whose car is prop.

-- 
Johan Bockgård

Re: Subtle bugs in interval code.

[Kim F. Storm]

bojohan+news@dd.chalmers.se (Johan Bockgård) writes:

> storm@cua.dk (Kim F. Storm) writes:
>
>> Note that we cannot just use plist-get instead of memq, as we then
>> cannot differentiate between "property is on list with nil value"
>> and "property is not on list".
>
>     plist-member is a built-in function in `src/fns.c'.
>     (plist-member plist prop)
>
>     Return non-nil if plist has the property prop.
>     plist is a property list, which is a list of the form
>     (PROP1 VALUE1 PROP2 VALUE2 ...).  prop is a symbol.
>     Unlike `plist-get', this allows you to distinguish between a missing
>     property and a property with the value nil.
>     The value is actually the tail of plist whose car is prop.

Brilliant!!  Thanks.

I have installed a fix using this.

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

Re: Subtle bugs in interval code.

[Richard Stallman]

    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;.

Re: Subtle bugs in interval code.

[Kim F. Storm]

Richard Stallman <rms@gnu.org> 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;
  }
  \f
  
--- 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));
  }
  \f
  

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

Re: Subtle bugs in interval code.

[Richard Stallman]

The patches look good.  Thanks.

    !       if (i0_cdr = XCDR (i0_cdr), !CONSP (i0_cdr))

It is clearer to move the assignment to statement level.
Inside of an if, it could be overlooked.

Re: Subtle bugs in interval code.

[Kim F. Storm]

Richard Stallman <rms@gnu.org> writes:

> The patches look good.  Thanks.
>
>     !       if (i0_cdr = XCDR (i0_cdr), !CONSP (i0_cdr))
>
> It is clearer to move the assignment to statement level.
> Inside of an if, it could be overlooked.

Ok.  I changed that and installed the fixes.

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