In a pickle.

In a pickle.

[chris.danx]

Hi,

Is there a resolution to the following problem that allows convienant
assignment of iterators?  An iterator points to a node in a list, like this

   -- Bi-Directional Iterator definition for positions within
   -- objects of List_Type.
   --
   type Iterator_Type is new Ada.Finalization.Controlled
   with record
      List       :   List_Base_Access;
      Position   :   Node_Access;
   end record;

While more than one iterator points to a node it cannot be deallocated, with
the number of iterators pointing to the node, recorded in the node itself.
The problem is assignment!  If we do

Iterator := Next (Iterator);

The iterator is assigned to the next position, but the count of iterators
isn't decremented so the node always thinks an iterator is on it.

I've just noticed something in Cohen that may help but am not sure if my
interpretation is correct.

At the top of page 573 he says "The target variable in an assignment
statement is finalized just before a new value is about to be copied to that
variable".

Does this mean that in the above assignment Iterator is finalized after Next
(Iterator) is evaluated but before the assignment takes place?  That would
mean that a suitably coded finalize would do the job, correct?


Chris

Re: In a pickle.

[Jim Rogers]

chris.danx wrote:

> Hi,
> 
> Is there a resolution to the following problem that allows convienant
> assignment of iterators?  An iterator points to a node in a list, like this
> 
>    -- Bi-Directional Iterator definition for positions within
>    -- objects of List_Type.
>    --
>    type Iterator_Type is new Ada.Finalization.Controlled
>    with record
>       List       :   List_Base_Access;
>       Position   :   Node_Access;
>    end record;
> 
> While more than one iterator points to a node it cannot be deallocated, with
> the number of iterators pointing to the node, recorded in the node itself.
> The problem is assignment!  If we do
> 
> Iterator := Next (Iterator);
> 
> The iterator is assigned to the next position, but the count of iterators
> isn't decremented so the node always thinks an iterator is on it.
> 
> I've just noticed something in Cohen that may help but am not sure if my
> interpretation is correct.
> 
> At the top of page 573 he says "The target variable in an assignment
> statement is finalized just before a new value is about to be copied to that
> variable".
> 
> Does this mean that in the above assignment Iterator is finalized after Next
> (Iterator) is evaluated but before the assignment takes place?  That would
> mean that a suitably coded finalize would do the job, correct?


That is my understanding of how assignment works.

Jim Rogers

Re: In a pickle.

[Simon Wright]

"chris.danx" <spamoff.danx@ntlworld.com> writes:

> Does this mean that in the above assignment Iterator is finalized
> after Next (Iterator) is evaluated but before the assignment takes
> place?  That would mean that a suitably coded finalize would do the
> job, correct?

   a := b;

I'm not sure whether a has to be finalized after b has been
evaluated. However, disregarding that, what happens is

   finalize the old a
   overwrite a with a bitwise copy of b
   adjust the overwritten a

It gets recursive if a has components which themselves have
finalize/adjust.

Re: In a pickle.

[chris.danx]

"Jim Rogers" <jimmaureenrogers@worldnet.att.net> wrote in message
news:3D3F0E27.9080303@worldnet.att.net...

> That is my understanding of how assignment works.

ARGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH!!!!!!!!!!!

Managing all the finalisation calls is a nightmare!

raised PROGRAM_ERROR : aqua-lists-linear-unbounded-doubly.adb:56

caused by finalization of an iterator in a call in a subprogram.  I reckon I
know how to fix it, but it will require each iterator modifing subprogram
setting a flag, while basic query ops clear it.  Finalization will check the
flag and if it's cleared do nothing, otherwise adjust the iterator.

Think that's ugly?  Anyone think of a better way?

Re: In a pickle.

[chris.danx]

Jim Rogers wrote:
> chris.danx wrote:
> 
>> Hi,
>>
>> Is there a resolution to the following problem that allows convienant
>> assignment of iterators?  An iterator points to a node in a list, like 
>> this
>>
>>    -- Bi-Directional Iterator definition for positions within
>>    -- objects of List_Type.
>>    --
>>    type Iterator_Type is new Ada.Finalization.Controlled
>>    with record
>>       List       :   List_Base_Access;
>>       Position   :   Node_Access;
>>    end record;
>>
>> While more than one iterator points to a node it cannot be 
>> deallocated, with
>> the number of iterators pointing to the node, recorded in the node 
>> itself.
>> The problem is assignment!  If we do
>>
>> Iterator := Next (Iterator);
>>
>> The iterator is assigned to the next position, but the count of iterators
>> isn't decremented so the node always thinks an iterator is on it.
>>
>> I've just noticed something in Cohen that may help but am not sure if my
>> interpretation is correct.
>>
>> At the top of page 573 he says "The target variable in an assignment
>> statement is finalized just before a new value is about to be copied 
>> to that
>> variable".
>>
>> Does this mean that in the above assignment Iterator is finalized 
>> after Next
>> (Iterator) is evaluated but before the assignment takes place?  That 
>> would
>> mean that a suitably coded finalize would do the job, correct?
> 
> 
> 
> That is my understanding of how assignment works.
> 
> Jim Rogers


ARGHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH!!!!!!!!!!!

Managing all the finalisation calls is a nightmare!

raised PROGRAM_ERROR : aqua-lists-linear-unbounded-doubly.adb:56

caused by finalization of an iterator in a call in a subprogram.  I reckon I
know how to fix it, but it will require each iterator modifing subprogram
setting a flag, while basic query ops clear it.  Finalization will check the
flag and if it's cleared do nothing, otherwise adjust the iterator.

Think that's ugly?  Anyone think of a better way?

Re: In a pickle.

[chris.danx]

Jim Rogers wrote:
> 
> That is my understanding of how assignment works.

Thanks.

> Jim Rogers
> 

Try posting this again (for the third time). :(

The task of implementing iterators is proving very difficult, can anyone 
please offer some guidance/pointers?  I want operations on a node which 
would invalidate iterators to take place only when one iterator 
references a node.  For example deleting a node should only occur when 
one, and only one iterator points to it (if more than one iterator 
points to the node an exception should occur).

First I tried a scheme involving counting the number of iterators that 
reference a node, but this approach lead to a very complex 
implementation, so it's back to the drawing board. :(


One difficulty encountered is in signalling that we are done with a 
node.  Suppose the statement

Iterator := Next (Iterator);

is allowed.  Prior to the call Iterator points to a node in the list (if 
it did not Next would raise Invalid_Iterator_Error), which it will leave 
after the assignment.  The node needs to know an iterator has left, but 
how?  Finalize can decrement the counter but it's difficult to control 
exactly when.  Consider this...

function Next (Iterator : in Iterator_Type) return Iterator_Type is
    Temp : Iterator_Type;
begin
    ...
    return Temp;
end Next;

After return Temp; Temp will be finalized so we need to record that temp 
is just temporary.  Then we have the problem of intelligently adjusting 
the iterator on the left hand-side. :(

Now I know why John English skipped the issue in "ada: the craft..." (I 
didn't fully appreciate Johns' warning on this) and why other list 
implementations either skip the issue or are quite complex.

Is there a better solution to this problem???


Thanks for your time,
Chris

Re: In a pickle.

[Grein, Christoph]

See my paper about Safe_Pointers in my home page.

http://home.T-online.de/home/Christ-Usch.Grein/Ada

This discusses in great detail how reference counting pointers can be 
implemented. This might help. This paper has appeared some time ago in Ada 
Letters and also in Ada User Journal. It includes complete software ready to 
use.

HTH

Christoph Grein

Re: In a pickle.

[Stephen Leake]

"chris.danx" <spamoff.danx@ntlworld.com> writes:

> The task of implementing iterators is proving very difficult, can
> anyone please offer some guidance/pointers?  

I've just put up my Grace.Lists implementation; see 

http://users.erols.com/leakstan/Stephe/index.html

It does "safe" iterators; iterators are invalidated if the item they
point to is deleted, etc.

> I want operations on a node which would invalidate iterators to take
> place only when one iterator references a node. For example deleting
> a node should only occur when one, and only one iterator points to
> it (if more than one iterator points to the node an exception should
> occur).

Grace does not require this. I guess you're doing something like
"reference counting garbage collection". 

So Grace iterators are not exactly what you want. But there may be
some implementation ideas you can use.

> First I tried a scheme involving counting the number of iterators
> that reference a node, but this approach lead to a very complex
> implementation, so it's back to the drawing board. :(

Complexity is sometimes necessary :).

> One difficulty encountered is in signalling that we are done with a
> node. Suppose the statement
> 
> Iterator := Next (Iterator);
> 
> is allowed.  Prior to the call Iterator points to a node in the list
> (if it did not Next would raise Invalid_Iterator_Error), which it will
> leave after the assignment.  The node needs to know an iterator has
> left, but how?  Finalize can decrement the counter but it's difficult
> to control exactly when.  Consider this...
> 
> function Next (Iterator : in Iterator_Type) return Iterator_Type is
>     Temp : Iterator_Type;
> begin
>     ...
>     return Temp;
> end Next;
> 
> After return Temp; Temp will be finalized so we need to record that
> temp is just temporary.  Then we have the problem of intelligently
> adjusting the iterator on the left hand-side. :(

Yes, using temporaries causes complexity. You might try using
aggregates instead; that gives you more direct control over what's
going on. Neither Initialize nor Finalize is called on an aggregate.

> Now I know why John English skipped the issue in "ada: the craft..."
> (I didn't fully appreciate Johns' warning on this) and why other
> list implementations either skip the issue or are quite complex.

Welcome to the club :). Implementing the Grace iterators was much more
challenging than I thought it would be. And I haven't really tested it
yet; that's more work than I want to do right now.

> Is there a better solution to this problem???

Since I'm not sure what your real top level problem is, I can't say.
Can you say more about why you want reference counted iterators?

-- 
-- Stephe

Re: In a pickle.

[chris.danx]

Stephen Leake wrote:
> "chris.danx" <spamoff.danx@ntlworld.com> writes:
 >
> I've just put up my Grace.Lists implementation; see 
> 
> http://users.erols.com/leakstan/Stephe/index.html
> 
> It does "safe" iterators; iterators are invalidated if the item they
> point to is deleted, etc.

Nice.

>>I want operations on a node which would invalidate iterators to take
>>place only when one iterator references a node. For example deleting
>>a node should only occur when one, and only one iterator points to
>>it (if more than one iterator points to the node an exception should
>>occur).
> 
> 
> Grace does not require this. I guess you're doing something like
> "reference counting garbage collection". 
> 
> So Grace iterators are not exactly what you want. But there may be
> some implementation ideas you can use.

I am undecided whether to invalidate all iterators like your Grace 
implementation or disallow deletion when multiple iterators point to the 
same iterator.  Chris Greins code has shed some light on the using 
aggregates which I was unaware of and this makes the use of temporaries 
unnecessary (didn't know how to use tagged types with aggregates).



>>First I tried a scheme involving counting the number of iterators
>>that reference a node, but this approach lead to a very complex
>>implementation, so it's back to the drawing board. :(
> 
> Complexity is sometimes necessary :).

It's a simple idea though.  Why do simple ideas have to be so complex? :)


> Yes, using temporaries causes complexity. You might try using
> aggregates instead; that gives you more direct control over what's
> going on. Neither Initialize nor Finalize is called on an aggregate.

Will do!

>>Now I know why John English skipped the issue in "ada: the craft..."
>>(I didn't fully appreciate Johns' warning on this) and why other
>>list implementations either skip the issue or are quite complex.
> 
> Welcome to the club :). Implementing the Grace iterators was much more
> challenging than I thought it would be. And I haven't really tested it
> yet; that's more work than I want to do right now.

Glad to see I'm not the only one :)

>>Is there a better solution to this problem???
> 
> Since I'm not sure what your real top level problem is, I can't say.
> Can you say more about why you want reference counted iterators?

I don't really know why.  My logic was that if the programmer calls 
delete on a node referenced by more than one iterator, there's a good 
chance it is an error and they should be warned.  I suppose a better 
idea would be to let the programmer delete the node and raise a 
constraint error when an attempt is made to use the iterator (just 
realised the programmer may really want to delete the node).

I'm really not sure what do, but after looking at Chris Greins paper the 
method of pointing Iterators directly at nodes doesn't seem so good. 
Maybe pointing Iterators to a unique object which points the node is 
better.  Need to experiment and have a look at how others have got round 
this problem.


Chris
-- 

to reply change 'spamoff' to 'chris'

Re: In a pickle.

[sk]

Hi,

"chris.danx" <spamoff.danx@ntlworld.com>
> It's a simple idea though.  Why do simple ideas have to be so complex? :)

Simple Idea: "Lets harness the explosive force of petrol ..."

Simple enough, but give me a well engineered and complex motorcycle
instead. 

 o o
  |
 \_/

-- 
-------------------------------------
-- Merge vertically for real address
-------------------------------------
s n p @ t . o
 k i e k c c m
-------------------------------------

Re: In a pickle.

[chris.danx]

Grein, Christoph wrote:
 > See my paper about Safe_Pointers in my home page.

Tis' very good.

 > http://home.T-online.de/home/Christ-Usch.Grein/Ada
 >
 > This discusses in great detail how reference counting pointers can be
 > implemented. This might help. This paper has appeared some time ago in
 > Ada Letters and also in Ada User Journal.

ping (lightbulb)!

I've constructed a rather contrived program using your safe pointers 
package dealing with the same situation as the iterators which works as 
required (I think).  I will attempt to work out the details for the list 
and hopefully if the above program expresses the intent correctly, the 
iterator problem will be resolved.

 > HTH
 >
 > Christoph Grein

Thanks Christoph, it was most helpful.



-- 

to reply directly change 'spamoff' to 'chris'