all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* Subtle bugs in interval code.
@ 2007-03-23 11:45 Kim F. Storm
  2007-03-23 11:55 ` David Kastrup
                   ` (2 more replies)
  0 siblings, 3 replies; 9+ messages in thread
From: Kim F. Storm @ 2007-03-23 11:45 UTC (permalink / raw)
  To: emacs-devel


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

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: Subtle bugs in interval code.
  2007-03-23 11:45 Subtle bugs in interval code Kim F. Storm
@ 2007-03-23 11:55 ` David Kastrup
  2007-03-23 14:03   ` Kim F. Storm
  2007-03-23 14:59 ` Johan Bockgård
  2007-03-23 22:32 ` Richard Stallman
  2 siblings, 1 reply; 9+ messages in thread
From: David Kastrup @ 2007-03-23 11:55 UTC (permalink / raw)
  To: Kim F. Storm; +Cc: emacs-devel

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

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: Subtle bugs in interval code.
  2007-03-23 11:55 ` David Kastrup
@ 2007-03-23 14:03   ` Kim F. Storm
  0 siblings, 0 replies; 9+ messages in thread
From: Kim F. Storm @ 2007-03-23 14:03 UTC (permalink / raw)
  To: David Kastrup; +Cc: emacs-devel

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

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: Subtle bugs in interval code.
  2007-03-23 11:45 Subtle bugs in interval code Kim F. Storm
  2007-03-23 11:55 ` David Kastrup
@ 2007-03-23 14:59 ` Johan Bockgård
  2007-03-23 15:42   ` Kim F. Storm
  2007-03-23 22:32 ` Richard Stallman
  2 siblings, 1 reply; 9+ messages in thread
From: Johan Bockgård @ 2007-03-23 14:59 UTC (permalink / raw)
  To: emacs-devel

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

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: Subtle bugs in interval code.
  2007-03-23 14:59 ` Johan Bockgård
@ 2007-03-23 15:42   ` Kim F. Storm
  0 siblings, 0 replies; 9+ messages in thread
From: Kim F. Storm @ 2007-03-23 15:42 UTC (permalink / raw)
  To: emacs-devel

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

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: Subtle bugs in interval code.
  2007-03-23 11:45 Subtle bugs in interval code Kim F. Storm
  2007-03-23 11:55 ` David Kastrup
  2007-03-23 14:59 ` Johan Bockgård
@ 2007-03-23 22:32 ` Richard Stallman
  2007-03-25  1:19   ` Kim F. Storm
  2 siblings, 1 reply; 9+ messages in thread
From: Richard Stallman @ 2007-03-23 22:32 UTC (permalink / raw)
  To: Kim F. Storm; +Cc: emacs-devel

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

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: Subtle bugs in interval code.
  2007-03-23 22:32 ` Richard Stallman
@ 2007-03-25  1:19   ` Kim F. Storm
  2007-03-25 17:27     ` Richard Stallman
  0 siblings, 1 reply; 9+ messages in thread
From: Kim F. Storm @ 2007-03-25  1:19 UTC (permalink / raw)
  To: rms; +Cc: emacs-devel

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

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: Subtle bugs in interval code.
  2007-03-25  1:19   ` Kim F. Storm
@ 2007-03-25 17:27     ` Richard Stallman
  2007-03-25 22:47       ` Kim F. Storm
  0 siblings, 1 reply; 9+ messages in thread
From: Richard Stallman @ 2007-03-25 17:27 UTC (permalink / raw)
  To: Kim F. Storm; +Cc: emacs-devel

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.

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: Subtle bugs in interval code.
  2007-03-25 17:27     ` Richard Stallman
@ 2007-03-25 22:47       ` Kim F. Storm
  0 siblings, 0 replies; 9+ messages in thread
From: Kim F. Storm @ 2007-03-25 22:47 UTC (permalink / raw)
  To: rms; +Cc: emacs-devel

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

^ permalink raw reply	[flat|nested] 9+ messages in thread

end of thread, other threads:[~2007-03-25 22:47 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2007-03-23 11:45 Subtle bugs in interval code Kim F. Storm
2007-03-23 11:55 ` David Kastrup
2007-03-23 14:03   ` Kim F. Storm
2007-03-23 14:59 ` Johan Bockgård
2007-03-23 15:42   ` Kim F. Storm
2007-03-23 22:32 ` Richard Stallman
2007-03-25  1:19   ` Kim F. Storm
2007-03-25 17:27     ` Richard Stallman
2007-03-25 22:47       ` Kim F. Storm

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.