Re: Mistake in TypedLinkedList?

[Jon Shapcott <eden@xibalba.demon.co.uk>]

On Sun, Nov 09, 2003 at 08:53:47PM -0500, Etienne Gagnon wrote:
> This is a bug.

Okay. I thought so. Fixed in the next release I guess.

> Ideally, we should use delegation, instead of inheritance, to protect 
> against
> addition of new methods in newer JDK versions.

I'm not so sure about this. I find the single elements methods
(addFirst(Object), getFirst(), etc.) declared by the LinkedList class really
handy. They are not part of the List interface, so this would break a lot of
existing code. The collections API is also pretty stable, so I don't think
we really need to worry about methods being added to future JDKs.

> Something like TypedLinkedList implements List, instead of "extends 
> LinkedList",
> but there might be a small performance penalty (?).

I must admit, I noticed the set method problem when making subclass of
TypedLinkedList that made use of the protected "modCount" field declared by
the AbstractList superclass. This field is incremented by the methods
declared in the LinkedList class every time elements are added or removed
from the list. This was to be used in combination with a Cast subclass that
would also set a "modified" field, so I could detect not only additions and
removals but replacements as well. This class is dependent on the
TypedLinkedList class being a subclass of at least the AbstractList class,
if not the LinkedList class.

However, threre are problems with the TypedLinkedList class. It is terribly
prone to throwing ConcurrentModificationException when the lists in nodes
are being modified. This leads ultimately to the failure to keep the strict
DAG property that I've been banging on about.

For my own experimental version of SableCC, I've replaced the usual
TypedLinkedList with one that can survive concurrent modifications, except
for using an iterator set() method to replace an element that has been
removed since the previous next() or previous() method call. This solves the
strict DAG proprty problem, with, yes, a small performance penalty.

If you like, I can take the LinkedList subclass I've written to do this,
tune it towards TypedLinkedList, and paste it into "parser.txt". It's pretty
big though, and I'd hate to have to maintain it separately from the
subclassing solution I'm using at the moment. The subclassing solution isn't
ideal for a stable release of SableCC, since it would make all parsers
generated by SableCC dependent on external libraries. I would make such a
library available, but it would make software using SableCC parsers a pain
to install.

> Jon Shapcott wrote:
> >I have noticed something rather odd about the set(int,Object) method in the
> >generated TypedLinkedList class. It is not defined. This means that the
> >set(int,Object) method defined by the Linkedlist superclass may be used to
> >violate the strict syntax tree property enforced by SableCC.
> >
> >It is such a small change that diff are barely woth it. Just add the
> >following few lines to the TypedLinkedList declaration in the "utils.txt"
> >macro file.
> >
> >
> >     public void set(int index, Object o)
> >     {
> >	super.set(index, cast.cast(o));
> >     }
> >
> >There are still a few wierd were the strict DAG property of SableCC can be
> >violated, but you have be doing something very strange. I've reported this
> >on this list previously.
> >
> 
> 
> -- 
> Etienne M. Gagnon, Ph.D.             http://www.info.uqam.ca/~egagnon/
> SableVM:                                       http://www.sablevm.org/
> SableCC:                                       http://www.sablecc.org/
> 

-- 
Jon Shapcott <eden@xibalba.demon.co.uk>
"This is the Space Age, and we are Here To Go" - Wlliam S. Burroughs