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