GNU bug report logs - #11077
24.0.94; avl-tree--enter-balance: (wrong-type-argument arrayp nil)

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 11077 in the body.
You can then email your comments to 11077 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Christopher Schmidt <christopher <at> ch.ristopher.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 24.0.94; avl-tree--enter-balance: (wrong-type-argument arrayp nil)
Date: Fri, 23 Mar 2012 20:28:01 +0100

[Message part 1 (text/plain, inline)]

I think I hit on a bug in avl-tree.el on GNU Emacs 24.0.94.1
(x86_64-unknown-linux-gnu, GTK+ Version 2.24.10) of 2012-03-23.

Recipe:
emacs -q
eval:
#+BEGIN_SRC emacs-lisp
(require 'cl)
(require 'avl-tree)

(defun gen-random ()
  (loop repeat 10
        concat (char-to-string (+ ?0 (random 10)))))

(loop repeat 10
      for tree = (avl-tree-create (lambda (a b) (string< a b)))
      do (loop repeat 400
               do (avl-tree-enter tree (gen-random) (lambda (data match) match))))
#+END_SRC

Backtrace:

[backtrace (text/plain, attachment)]

[Message part 3 (text/plain, inline)]

I have to run the body of the outer loop multiple times or increase the
repeat count of the inner loop to trigger the error.  I am not running
out of virtual memory, though.  Adding `do (garbage-collect)' to the
outer loop does not help either.

        Christopher

Message #8 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Christopher Schmidt <christopher <at> ch.ristopher.com>
To: bug-gnu-emacs <at> gnu.org
Subject: Re: bug#11077: 24.0.94;
	avl-tree--enter-balance: (wrong-type-argument arrayp nil)
Date: Fri, 23 Mar 2012 21:43:25 +0100

Christopher Schmidt <christopher <at> ch.ristopher.com> writes:

> I have to run the body of the outer loop multiple times or increase
> the repeat count of the inner loop to trigger the error.  I am not
> running out of virtual memory, though.  Adding `do (garbage-collect)'
> to the outer loop does not help either.

This seems to be a bug caused by inconsistencies in the tree generated
by a specific dataset.  This recipe triggers the error right away:

#+BEGIN_SRC emacs-lisp
(require 'cl)
(require 'avl-tree)

(loop with *random-state* = (vector 'cl-random-state-tag -1 30 6988712785513)
      repeat 1000
      with tree = (avl-tree-create (lambda (a b) (< a b)))
      do (avl-tree-enter tree (random* 100000)))
#+END_SRC

        Christopher

Message #11 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Christopher Schmidt <christopher <at> ch.ristopher.com>
To: bug-gnu-emacs <at> gnu.org
Subject: Re: bug#11077: 24.0.94;
	avl-tree--enter-balance: (wrong-type-argument arrayp nil)
Date: Tue, 27 Mar 2012 19:59:02 +0200

Christopher Schmidt <christopher <at> ch.ristopher.com> writes:

> Christopher Schmidt <christopher <at> ch.ristopher.com> writes:
>
>> I have to run the body of the outer loop multiple times or increase
>> the repeat count of the inner loop to trigger the error.  I am not
>> running out of virtual memory, though.  Adding `do (garbage-collect)'
>> to the outer loop does not help either.
>
> This seems to be a bug caused by inconsistencies in the tree generated
> by a specific dataset.  This recipe triggers the error right away:
>
> #+BEGIN_SRC emacs-lisp
> (require 'cl)
> (require 'avl-tree)
>
> (loop with *random-state* = (vector 'cl-random-state-tag -1 30 6988712785513)
>       repeat 1000
>       with tree = (avl-tree-create (lambda (a b) (< a b)))
>       do (avl-tree-enter tree (random* 100000)))
> #+END_SRC

BTW. this is a regression.  The code above works fine in Emacs 23.3.
Here's the commit that introduced the problem:

revno: 104392 [merge]
author: Toby Cubitt <toby-predictive <at> dr-qubit.org>
committer: Stefan Monnier <monnier <at> iro.umontreal.ca>
branch nick: trunk
timestamp: Fri 2011-05-27 20:03:26 -0300
message:
  * lisp/emacs-lisp/avl-tree.el: New avl-tree-stack datatype.  Add new
  traversal functions for avl-trees.  Consolidate rebalancing code.

        Christopher

Message #14 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Stefan Monnier <monnier <at> IRO.UMontreal.CA>
To: bug-gnu-emacs <at> gnu.org
Subject: Re: bug#11077: 24.0.94;
	avl-tree--enter-balance: (wrong-type-argument arrayp nil)
Date: Tue, 27 Mar 2012 16:44:18 -0400

>> I have to run the body of the outer loop multiple times or increase
>> the repeat count of the inner loop to trigger the error.  I am not
>> running out of virtual memory, though.  Adding `do (garbage-collect)'
>> to the outer loop does not help either.

> This seems to be a bug caused by inconsistencies in the tree generated
> by a specific dataset.  This recipe triggers the error right away:

This was a simple paren-typo.  Thank you for catching it,


        Stefan


=== modified file 'lisp/emacs-lisp/avl-tree.el'
--- lisp/emacs-lisp/avl-tree.el	2012-01-19 07:21:25 +0000
+++ lisp/emacs-lisp/avl-tree.el	2012-03-27 20:40:27 +0000
@@ -295,9 +295,9 @@
 	        (if (> (* sgn b2) 0) (- sgn) 0)
 	      (avl-tree--node-balance p1)
 	        (if (< (* sgn b2) 0) sgn 0)
-	      (avl-tree--node-branch node branch) p2
-	      (avl-tree--node-balance
-	       (avl-tree--node-branch node branch)) 0))
+                (avl-tree--node-branch node branch) p2))
+      (setf (avl-tree--node-balance
+             (avl-tree--node-branch node branch)) 0)
       nil))))
 
 (defun avl-tree--do-enter (cmpfun root branch data &optional updatefun)

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.