From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: storm@cua.dk (Kim F. Storm) Newsgroups: gmane.emacs.devel Subject: Re: Subtle bugs in interval code. Date: Sun, 25 Mar 2007 03:19:42 +0200 Message-ID: References: NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1174785607 11467 80.91.229.12 (25 Mar 2007 01:20:07 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sun, 25 Mar 2007 01:20:07 +0000 (UTC) Cc: emacs-devel@gnu.org To: rms@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Mar 25 03:20:00 2007 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1HVHOk-00017L-Q8 for ged-emacs-devel@m.gmane.org; Sun, 25 Mar 2007 03:19:55 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1HVHQp-000746-7W for ged-emacs-devel@m.gmane.org; Sat, 24 Mar 2007 20:22:03 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1HVHQm-00070s-2D for emacs-devel@gnu.org; Sat, 24 Mar 2007 21:22:00 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1HVHQl-0006zW-Bz for emacs-devel@gnu.org; Sat, 24 Mar 2007 21:21:59 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1HVHQl-0006zL-9o for emacs-devel@gnu.org; Sat, 24 Mar 2007 20:21:59 -0500 Original-Received: from pfepa.post.tele.dk ([195.41.46.235]) by monty-python.gnu.org with esmtp (Exim 4.60) (envelope-from ) id 1HVHOe-00056Q-ET; Sat, 24 Mar 2007 21:19:48 -0400 Original-Received: from kfs-l.imdomain.dk.cua.dk (0x503e2644.bynxx19.adsl-dhcp.tele.dk [80.62.38.68]) by pfepa.post.tele.dk (Postfix) with SMTP id AC067FAC019; Sun, 25 Mar 2007 03:19:46 +0200 (CEST) In-Reply-To: (Richard Stallman's message of "Fri\, 23 Mar 2007 18\:32\:34 -0400") User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.96 (gnu/linux) X-detected-kernel: Linux 2.6, seldom 2.4 (older, 4) X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:68514 Archived-At: Richard Stallman 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 http://www.cua.dk