Re: list strawman

[Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov>]

Ted Dennison<dennison@telepath.com> writes:

> In article <ug05j42sp.fsf@gsfc.nasa.gov>, Stephen Leake says...
> >
> >I've done a priliminary implementation of
> >http://www.telepath.com/dennison/Ted/Containers-Lists-Unbounded.ads.html
> ..
> >This was an interesting excersize. I got quite stuck on making the
> 
> Yes it is, isn't it? :-)
> 
> >iterators safe, while at the same time not requiring the user to use
> >'Unchecked_Access. A hint from http://homepage.ntlworld.com/ramatthews/
> >(Robert A. Matthews' GAPSE) set me straight; use a layer of indirection.
> 
> I ended up doing almost exactly the same thing. 

Cool. Great minds think alike? or just common environments lead to
common evolution :).

One issue I did not point out is the changes I had to make to the
spec. In particular, I had to declare "List" as tagged, and use 'class
in a couple places. Do you have any objections to that?

> >The final implementation is quite complex (and I haven't done sort
> >yet). I don't think I will ever use this package in a real project.
> >Just writing all the tests to prove that iterators actually are
> >safe will take quite a while. But it is an interesting example of
> >what can be done.
> 
> Things that I have stumbled over so far:

Well, I have _not_ done thorough testing, so it is quite possible
you've uncovered real bugs.

> The List Adjust routine should wipe out any iterator lists, as they
> belong to the source List (and visa versa), not the target. You
> don't deal with this.

Hmm. Adjust (List) explicitly sets the new list's iterator list to
null. The source list iterators are preserved, and the new list has no
iterators. Are you saying I should "wipe out" the source iterators,
and not preserve them? That's not what I would expect.

> The List Finalize routine needs to invalidate any iterators on the
> list's iterator list. You don't do this. (The comment says you do,
> but you just seem to be calling Unchecked_Conversion on the list
> header, unless I am missing something)

Actually Unchecked_Deallocation. That eventually calls Finalize on the
iterator list, which should invalidate all of them. A test case
proving this is needed.

> The List and Iterator Initialize routines have to allocate new list
> and iterator structures respectively before they do anything else.
> The list Initialize does this, but the iterator one looks like it
> tries to dereference the (null) pointer immediately. You say you've
> tested with iterators, so you must have gotten this to work somehow,
> but I'm mystified as to how (unless it was the passive iterator
> generic).

Yes, I've only used the passive generic (to print the lists), so maybe
I am missing something. 

There is a tradeoff between putting stuff in Initialize, and doing
stuff with aggregates when an object is created. If you assign an
aggregate to a Controlled object, Initialize is _not_ called (LRM 7.6
(10)). So any place you assign an aggregate to a Controlled object,
you have to be sure you do everything Initialize would do. I'm pretty
sure I haven't got that right yet.

> A subtle point: Iterators may have the "No_Item" condition, but
> still be validly associated with a list (eg: An empty list that you
> want to add items to with "Insert").

Yes. SAL just raises Constraint_Error for the No_Item condition; I do
not map that to the No_Item exception everywhere yet.

I just noticed that the No_Item exception is declared within the
generic Lists.Unbounded package, which means we get a different one
for each instantiation. We probably want to move that up to Lists or
ACL.

> When elements are removed from a list, you have to invalidate any
> iterator entires that may point to that element. It doesn't look
> like this is being done in "Remove" (end or iterator versions).

Yes, I haven't put that in yet. I wanted to write a test that failed
first, so I would know the test was valid :).

> Efficiency issues:
> 
> I discovered it is possible to get rid of all dynamic allocations in iterator
> manipulations. <snip>

I'd definitely like to see this.

> It also looks like it is possible to get rid of all list searches in iterator
> manipulations. <snip>

Are you sure you are considering all the nasty things users can do?
Like declaring several iterators to a list, but not actually using
them for anything.

> A nice side benifit to doing this is that iterators can be
> made to travel with the element when it chages lists (via Splice).
> We will have to discuss if this is a Bad Thing or a Good Thing from
> a user perspective.

I think that's a Bad Thing. But if it were clearly documented, maybe
it would be ok.

> Anyway, sorry for all the criticism. Good work. Believe me, I know
> how much effort it is to try to get this right. :-)

Hey, it was actually fun! It made me appreciate having written SAL;
having a working low-level list abstraction makes it easier to
implement the safe iterators. And doing this clarified some of the
design issues in SAL.

You might consider using my Test_Storage_Pools package in your test
harness; it makes it possible to find memory leaks as part of testing.

-- 
-- Stephe