Re: Ada.Containers and concurrent modification exception.

["Randy Brukardt" <randy@rrsoftware.com>]

<rakusu_klein@fastmail.jp> wrote in message 
news:b41ee5c2-3000-442f-93cf-67116eac833a@googlegroups.com...
???????, 22 ???????? 2018 ?., 2:27:59 UTC+3 ???????????? Randy Brukardt 
???????:
>> And it would be wrong: deleting a node from the Map only invalidates 
>> cursors
>> that point at that node, not cursors that point at other nodes in the 
>> Map.
>> Those can continue to be used (for instance, if stored in another 
>> container)
>> until their nodes or the map as a whole are deleted.
>
>You missed the point, perhaps because I choose obscure names for 
>properties. Sorry.

No, I understood the point quite well. It doesn't work. Consider the 
following Ada pseudo-code (which you ought to be able to understand 
regardless of any language barrier):

    M : Map;
    R1, R2 : Cursor;

    M.Insert (..., R1); -- Insert a record saving the cursor. Mod counter = 
1.
    M.Insert (..., R2); -- Mod counter = 2.
    M.Delete (R1); -- Oops, cursor is invalid, container was modifed since 
it was created -- but this must work.
    ... Element (R2) ...; -- Oops, cursor is invalid, container was modifed 
since it was created, but this must work.
    ... Element (R1) ...; -- Cursor is invalid, OK to have raise an error 
here.

The important point is that a cursor remains valid until either the 
container as a whole or the element it designated is deleted. Thus, if you 
were to use some sort of counter implementation, it has to be per-node (that 
is, per-element).

In addition, some container operations (especially with lists) allow moving 
nodes from one container to another, so the counter has to be global to all 
of the containers of a particular type. This brings tasking issues into it.

Unlikely Dmitry, I think this check can be done usefully, *but* it can't be 
done in a way which is 100% accurate. False positives (that is, errors in 
correct cases) cannot be tolerated, so it necessarily has to be 
conservative.

...
>> when a container is destroyed and a new one created in the same location
>It will be created with zero number of modifications. If iterator will have 
>zero number
>of modifications too, nothing wrong happens (just because container is 
>empty),
>otherwise exception will be raised.

As noted above, the counter has to be per-element and global to all 
containers of a given type (at least for some types of containers). So 
resetting for each container doesn't work.

>> It also could fail if the counter wrapped arround
>Why? We just need to check if the value of Known_Modifications in iterator 
>...

We're not talking about "iterators", we're talking about cursors. Iterators 
have the tampering check (an iterator being an active structure that 
iterates, a for loop being the basic example), which does indeed work like 
this. (And that is mandated.) Cursors are references, rather similar to 
access values in Ada. They live individually.

>...is equal to the value of Actual_Modifications in container. It is the 
>reason why I called
>they both a State - an unique number that reflects a number of container's 
>modifications.
>And on a 32-bit machine we have a 4_294_967_296 modifications before a 
>wrap.

Remember, this check has to be per-element, as detailed above. Then consider 
a long-lived program (like a web server, which may run weeks or months) and 
a data structure that might be modified thousands of times per second. I 
agree that this is not very likely, but a check based on such a counter 
cannot detect all possible errors -- 99.9999% perhaps, but that is not a 
appropriate answer to a requirement. (And it will be much less effective if 
the memory is returned to the system when nodes are deleted.)

>Of course, there is a possibility of check failure exists, but it has very 
>low probability.

Too high in my view to consider it a solution for cursor checks. Especially 
as they cannot be effective once the memory of the designated node is 
reclaimed. (For the Janus/Ada implementation, we will delay reclaimation 
among other tricks to maximize detection, but it's far from perfect.)

                                          Randy.