Ada.Containers and concurrent modification exception.

Ada.Containers and concurrent modification exception.

[rakusu_klein]

Hi all!

Why Ada's Cursors does not provide the ConcurrentModificationException, as Java Collections do, or some variant of it? Consider the following:

with Ada.Containers.Indefinite_Ordered_Maps;
...
   The_Map : Map;
...
declare
   I : Cursor := First (The_Map);
   J : Cursor := First (The_Map);
begin
   --  Now Cursors are synchronized with each other and with a container.
   Delete (The_Map, I);
   --  It's O'k. But now J lost a sync and points to a dead Node.
   Next (J);
   --  What should I expected here,
   --  any well defined exception or
   --  raising a zombie?
end;

Regards.

Re: Ada.Containers and concurrent modification exception.

[Jacob Sparre Andersen]

rakusu_klein@fastmail.jp writes:

> Why Ada's Cursors does not provide the
> ConcurrentModificationException, as Java Collections do,

Because that is something from Java. ;-)

> or some variant of it?

The Ada containers define the concept of tampering.  I can't remember
which exception you get in case you tamper with a standard container,
but you can be pretty sure you will get one.

> Consider the following:
>
> with Ada.Containers.Indefinite_Ordered_Maps;
> ...
>    The_Map : Map;
> ...
> declare
>    I : Cursor := First (The_Map);
>    J : Cursor := First (The_Map);
> begin
>    --  Now Cursors are synchronized with each other and with a container.
>    Delete (The_Map, I);
>    --  It's O'k. But now J lost a sync and points to a dead Node.
>    Next (J);
>    --  What should I expected here,
>    --  any well defined exception or
>    --  raising a zombie?
> end;

Did you try it?

Both with GCC 6.3.0 and with GNAT CE 2018 I get
System.Assertions.Assert_Failure, but that is definitely not defined as
a part of the tampering checks, so I suspect GNAT is wrong (but still
safe) here.

I've posted an executable example here:

https://bitbucket.org/sparre/ada-2012-examples/src/default/src/container_tampering.adb

(Randy, feel free to adapt it for ACATS, if it shows something relevant)

Greetings,

Jacob
-- 
"In case of discrepancy, you must ignore what they ask for
 and give what they need, ignore what they would like and
 tell them what they don't want to hear but need to know."
                                                 -- E.W. Dijkstra

Re: Ada.Containers and concurrent modification exception.

[Simon Wright]

Jacob Sparre Andersen <jacob@jacob-sparre.dk> writes:

> I've posted an executable example here:
>
> https://bitbucket.org/sparre/ada-2012-examples/src/default/src/container_tampering.adb

On macOS this hangs. Also on debian stretch. No assertion failures.

Re: Ada.Containers and concurrent modification exception.

[Jacob Sparre Andersen]

Simon Wright <simon@pushface.org> writes:

> Jacob Sparre Andersen <jacob@jacob-sparre.dk> writes:
>
>> I've posted an executable example here:
>>
>> https://bitbucket.org/sparre/ada-2012-examples/src/default/src/container_tampering.adb
>
> On macOS this hangs. Also on debian stretch. No assertion failures.

Even built with the project file?  Strange.  I'm running Debian/Stretch
(9.5) here.

Greetings,

Jacob
-- 
»It will not be forever. - It will just seem like it.« -- Death

Re: Ada.Containers and concurrent modification exception.

[Simon Wright]

Jacob Sparre Andersen <jacob@jacob-sparre.dk> writes:

> Simon Wright <simon@pushface.org> writes:
>
>> Jacob Sparre Andersen <jacob@jacob-sparre.dk> writes:
>>
>>> I've posted an executable example here:
>>>
>>> https://bitbucket.org/sparre/ada-2012-examples/src/default/src/container_tampering.adb
>>
>> On macOS this hangs. Also on debian stretch. No assertion failures.
>
> Even built with the project file?  Strange.  I'm running Debian/Stretch
> (9.5) here.

It hadn't even occurred to me that there might be a project file! I
don't use bitbucket (in spite of having relatives working at Atlassian)
and confused it with pastebin ...

OK, building with -gnata to enable assertions does indeed produce
assertion failures:

  $ ./container_tampering 
  ABC
  SYSTEM.ASSERTIONS.ASSERT_FAILURE: Position cursor of Next is bad
  SYSTEM.ASSERTIONS.ASSERT_FAILURE: Position cursor of function Key is bad

But, if I'd been writing the Containers, this would have been a
Program_Error; it's a disaster (and quite legal to reward erroneous code
with PE, too).

Re: Ada.Containers and concurrent modification exception.

[Anh Vo]

On Wednesday, September 19, 2018 at 9:05:03 AM UTC-7, Simon Wright wrote:
> Jacob Sparre Andersen <jacob@jacob-sparre.dk> writes:
> 
> > I've posted an executable example here:
> >
> > https://bitbucket.org/sparre/ada-2012-examples/src/default/src/container_tampering.adb
> 
> On macOS this hangs. Also on debian stretch. No assertion failures.

It also occurred on GNAT Community 2018 running on Windows 7 and Red Hat Enterprise Linux Workstation release 7.5 (Maipo)

Anh Vo 

Re: Ada.Containers and concurrent modification exception.

[Anh Vo]

On Wednesday, September 19, 2018 at 9:31:43 AM UTC-7, Anh Vo wrote:
> On Wednesday, September 19, 2018 at 9:05:03 AM UTC-7, Simon Wright wrote:
> > Jacob Sparre Andersen <jacob@jacob-sparre.dk> writes:
> > 
> > > I've posted an executable example here:
> > >
> > > https://bitbucket.org/sparre/ada-2012-examples/src/default/src/container_tampering.adb
> > 
> > On macOS this hangs. Also on debian stretch. No assertion failures.
> 
> It also occurred on GNAT Community 2018 running on Windows 7 and Red Hat Enterprise Linux Workstation release 7.5 (Maipo)
 
Adding -gnata switch to compilation, the SYSTEM.ASSERTIONS.ASSERT_FAILURE was raised on both Windows and Red Hat.

This is compiler dependency. Should pragma Assertion_Policy(check) be used for consistency. 

Re: Ada.Containers and concurrent modification exception.

[rakusu_klein]

On WinXP with GNAT GPL 2017 (20170515) (i686-pc-mingw32) I get the indefinite loop without “-gnata” and with this option — the same assertions as others have, which produces by the Vet procedure, which checks if a dead Node referring to itself. I don't think that necromancy is a good idea — the memory for a dead Node is actually free and may use for an other Node object, so what happens in that case?

Re: Ada.Containers and concurrent modification exception.

[Simon Wright]

rakusu_klein@fastmail.jp writes:

> On WinXP with GNAT GPL 2017 (20170515) (i686-pc-mingw32) I get the
> indefinite loop without “-gnata” and with this option — the same
> assertions as others have, which produces by the Vet procedure, which
> checks if a dead Node referring to itself. I don't think that
> necromancy is a good idea — the memory for a dead Node is actually
> free and may use for an other Node object, so what happens in that
> case?

Nothing good.

And it might be in use for something completely different, anyway!

Re: Ada.Containers and concurrent modification exception.

[Simon Wright]

rakusu_klein@fastmail.jp writes:

> Why Ada's Cursors does not provide the
> ConcurrentModificationException, as Java Collections do, or some
> variant of it? Consider the following:
>
> with Ada.Containers.Indefinite_Ordered_Maps;
> ...
>    The_Map : Map;
> ...
> declare
>    I : Cursor := First (The_Map);
>    J : Cursor := First (The_Map);
> begin
>    --  Now Cursors are synchronized with each other and with a container.
>    Delete (The_Map, I);
>    --  It's O'k. But now J lost a sync and points to a dead Node.
>    Next (J);
>    --  What should I expected here,
>    --  any well defined exception or
>    --  raising a zombie?
> end;

What actually happens in this case (GNAT CE 2018) is that the program
enters an endless loop looking at (what it thinks is) a node with both
left and right pointers designating itself.

The ARM goes to a lot of trouble to prevent "tampering with cursors",
but that's mainly to do with detecting altering the structure of a
container while iterating over it, and the code you show isn't really
covered by that. So I'm not sure if it isn't 'just' erroneous[1].

It would be a good thing if the error was detected. Perhaps submit a bug
report to AdaCore?

[1] http://www.adaic.org/resources/add_content/docs/95style/html/sec_5/5-9.html

Re: Ada.Containers and concurrent modification exception.

[rakusu_klein]

среда, 19 сентября 2018 г., 18:53:31 UTC+3 пользователь Simon Wright написал:
> It would be a good thing if the error was detected. Perhaps submit a bug
> report to AdaCore?
I am new in Ada, so don't know what is it — a bug or a feature.

Honestly, I just try to implement a standard containers in Ada by myself for educational purposes. In process I looking in GNU Classpath sources for an advice, and notice, that they are used an int counters (an int in Java have wrap-around semantic) in both containers and iterators for preventing working with invalid iterators. They call this a “fail-fast semantic”. So I decided to implement my own containers in that way, for example:
private
   type State_Type is mod 2 ** Integer'Size;

   type Map is
      record
         State : State_Type  := State_Type'First;
         Size  : Natural     := Natural'First;
         Root  : Node_Access := new Node_Object (Variant => Empty);
      end record;

   type Map_Access is access constant Map;

   type Cursor is
      record
         Container : Map_Access  := null;
         State     : State_Type  := State_Type'First;
         Node      : Node_Access := null;
      end record;

In operations with container I just compare States in Container and Cursor and throw a Concurent_Modification exception if they are not equal. If any operation   deletes a Node, I just increment States in Container and Cursor, if it used, — it makes invalid any other Cursors. It may be stupid, but works well for me.

After all I looked at the Ada.Containers and notice, that its Cursors does not have any kind of modification counters. So I decided to ask here about it.

Re: Ada.Containers and concurrent modification exception.

[Randy Brukardt]

<rakusu_klein@fastmail.jp> wrote in message 
news:64f5bbad-2f06-4ea9-aa33-8c66e9cbb2a5@googlegroups.com...

>In operations with container I just compare States in Container and Cursor 
>and
>throw a Concurent_Modification exception if they are not equal. If any 
>operation
>deletes a Node, I just increment States in Container and Cursor, if it 
>used, - it
>makes invalid any other Cursors. It may be stupid, but works well for me.

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 would have to use such a counter in each *node* for this to work. An 
implementation on this line is the 99% percent solution that I was 
suggesting, but it could fail in various circumstances, most likely when a 
container is destroyed and a new one created in the same location (as could 
happen with a commonly called subprogram). It also could fail if the counter 
wrapped arround (as it could if many nodes are created and destroyed 
repeatedly).

                                               Randy.

Re: Ada.Containers and concurrent modification exception.

[rakusu_klein]

суббота, 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.

State_Type is a modification's counter with a wrap-around sematic. It counts modifications of an internal container's structure and exists in all container's instances (call them Actual_Modifications) and in every iterator's instance (call them Known_Modifications). When an iterator is created for an existing container, its counter is initialized by value of that container, so their values are equal. When container is changed by any public method, its modification counter is incremented by one. If modification process by public method involves an iterator, the modification counter inside the iterator also incremented by one. Before any modification will doing, values of counters for container and iterator will be compared for equality, and if The_Container.Actual_Modifications /= The_Cursor.Known_Modifications then raise Concurent_Modification.
Look at http://developer.classpath.org/doc/java/util/TreeMap-source.html “knownMod” and “modCount” private ints.

> 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.

> It also could fail if the counter wrapped arround
Why? We just need to check if the value of Known_Modifications in iterator 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.

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

Re: Ada.Containers and concurrent modification exception.

[Dmitry A. Kazakov]

On 2018-09-22 03:09, rakusu_klein@fastmail.jp wrote:
> суббота, 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.
> 
> State_Type is a modification's counter with a wrap-around sematic. It counts modifications of an internal container's structure and exists in all container's instances (call them Actual_Modifications) and in every iterator's instance (call them Known_Modifications). When an iterator is created for an existing container, its counter is initialized by value of that container, so their values are equal. When container is changed by any public method, its modification counter is incremented by one. If modification process by public method involves an iterator, the modification counter inside the iterator also incremented by one. Before any modification will doing, values of counters for container and iterator will be compared for equality, and if The_Container.Actual_Modifications /= The_Cursor.Known_Modifications then raise Concurent_Modification.

This schema (sequence numbers) would invalidate all cursors. Not a good 
idea at all, in presence of many cursors. If there is only one cursor 
then there is also no problem. So the case looks quite marginal to me.

If I wanted to cover it, provided I ever used cursors, I would rather 
have the task ID to identify the owner of the change. This would be sort 
of re-entrant mutex with the difference that it would raise exception 
instead of blocking the offender.

In short:

1. The whole idea of fine interlocking/detection of concurrent access at 
the granularity level of individual container elements is wrong. It will 
never work, IMO.

2. The idea of raising exceptions concurrently at run-time to indicate 
tasking design errors is even worse.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Ada.Containers and concurrent modification exception.

[rakusu_klein]

Hello. Did you speak Russian? I do not understand what's going on, so I need help.

Re: Ada.Containers and concurrent modification exception.

[Dmitry A. Kazakov]

On 2018-09-22 19:49, rakusu_klein@fastmail.jp wrote:
> Hello. Did you speak Russian?

I certainly did. (:-))

> I do not understand what's going on, so I need help.

If I can, I don't use the library containers.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Ada.Containers and concurrent modification exception.

[Randy Brukardt]

<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.

Re: Ada.Containers and concurrent modification exception.

[Petter Fryklund]

Personally I prefer passive iterators:

The container has a 

generic
  with procedure Process(Item : in Item_Type; Continue : out Boolean);
procedure Traverse_Container;

The user instantiate the generic with:

procedure Process(Item : in Item_Type; Continue : out Boolean);

procedure Travers is new Traverse_Container(Process);

And then implements the body of Process.

Re: Ada.Containers and concurrent modification exception.

[Randy Brukardt]

"Petter Fryklund" <petter.fryklund@atero.se> wrote in message 
news:95d94212-9ae3-423e-980f-705fea24744d@googlegroups.com...
> Personally I prefer passive iterators:

Which has what to do with this discussion on tampering and dangling cursor 
checks? A passive iterator still needs a tampering check.

Note that the Ada.Containers have these sort of iterators (in the form of 
iterators with access-to-procedure parameters). And they have tampering 
checks.

                                                                     Randy.

Re: Ada.Containers and concurrent modification exception.

[Petter Fryklund]

Just a try to be funny, you wrote:
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. 

Regards,
Petter        

Re: Ada.Containers and concurrent modification exception.

[Jeffrey R. Carter]

On 09/19/2018 03:12 PM, rakusu_klein@fastmail.jp wrote:
> 
> with Ada.Containers.Indefinite_Ordered_Maps;
> ...
>     The_Map : Map;
> ...
> declare
>     I : Cursor := First (The_Map);
>     J : Cursor := First (The_Map);
> begin
>     --  Now Cursors are synchronized with each other and with a container.
>     Delete (The_Map, I);
>     --  It's O'k. But now J lost a sync and points to a dead Node.
>     Next (J);
>     --  What should I expected here,
>     --  any well defined exception or
>     --  raising a zombie?
> end;

The ARM covers this case in ARM A.18.4(76-80) [I am unable to access the current 
ARM right now, so I'm quoting from ISO/IEC 8652:2007, which should be similar]:

"A Cursor value is invalid if ... The node it designates has been deleted from 
the map. The result of "=" or Has_Element is unspecified if these functions are 
called with an invalid cursor parameter. Execution is erroneous if any other 
subprogram declared in Containers.Hashed_Maps or Containers.Ordered_Maps is 
called with an invalid cursor parameter.

So J is invalid and Next (J) is erroneous. ARM 1.1.5(10) defines erroneous 
execution: "there is no language-specified bound on the possible effect of 
erroneous execution; the effect is in general not predictable." In other words, 
this call can do anything.

-- 
Jeff Carter
"I spun around, and there I was, face to face with a
six-year-old kid. Well, I just threw my guns down and
walked away. Little bastard shot me in the ass."
Blazing Saddles
40

Re: Ada.Containers and concurrent modification exception.

[rakusu_klein]

среда, 19 сентября 2018 г., 23:16:18 UTC+3 пользователь Jeffrey R. Carter написал:
> The ARM covers this case in ARM A.18.4(76-80) [I am unable to access the current 
> ARM right now, so I'm quoting from ISO/IEC 8652:2007, which should be similar]:
> 
> "A Cursor value is invalid if ... The node it designates has been deleted from 
> the map. The result of "=" or Has_Element is unspecified if these functions are 
> called with an invalid cursor parameter. Execution is erroneous if any other 
> subprogram declared in Containers.Hashed_Maps or Containers.Ordered_Maps is 
> called with an invalid cursor parameter.
> 
> So J is invalid and Next (J) is erroneous. ARM 1.1.5(10) defines erroneous 
> execution: "there is no language-specified bound on the possible effect of 
> erroneous execution; the effect is in general not predictable." In other words, 
> this call can do anything.

That isn't right, even if it defined in reference manual. Depending on heap usage, that https://pastebin.com/H73KZ8Ti mess will work for years and in one fine day may fail for unknown reason.

Re: Ada.Containers and concurrent modification exception.

[Randy Brukardt]

<rakusu_klein@fastmail.jp> wrote in message 
news:168a229f-55de-4cb1-8405-8771e132d3ad@googlegroups.com...
>?????, 19 ???????? 2018 ?., 23:16:18 UTC+3 ???????????? Jeffrey R. Carter 
>???????:
>> The ARM covers this case in ARM A.18.4(76-80) [I am unable to access the 
>> current
>> ARM right now, so I'm quoting from ISO/IEC 8652:2007, which should be 
>> similar]:
>>
>> "A Cursor value is invalid if ... The node it designates has been deleted 
>> from
>> the map. The result of "=" or Has_Element is unspecified if these 
>> functions are
>> called with an invalid cursor parameter. Execution is erroneous if any 
>> other
>> subprogram declared in Containers.Hashed_Maps or Containers.Ordered_Maps 
>> is
>> called with an invalid cursor parameter.
>>
>> So J is invalid and Next (J) is erroneous. ARM 1.1.5(10) defines 
>> erroneous
>> execution: "there is no language-specified bound on the possible effect 
>> of
>> erroneous execution; the effect is in general not predictable." In other 
>> words,
>> this call can do anything.
>
>That isn't right, even if it defined in reference manual. Depending on heap 
>usage, that >https://pastebin.com/H73KZ8Ti mess will work for years and in 
>one fine day may fail
>for unknown reason.

Of course it's right. The intent is that a cursor is directly implemented by 
a pair of access objects, and that is the behavior of a dangling pointer. 
(That is, all real programs in Ada (and C!!) have exactly this possibility - 
we've lived with it for 40+ years. Doing something different would have been 
too radical in 1980, and it's way to late to do that now - other than 
optionally).

We wanted it to be possible for the Ada containers to be 
performance-competitiive with C++ containers, and expensive cursor checks 
would make that impossible. In particular, the only known way to implement 
perfect dangling cursor detection would be to make all cursors controlled 
and keep links from them back to their originating container. That would be 
much slower (5-10 times) on every cursor operation than the current 
definition -- and such an implementation would have been required had we not 
made the operations erroneous.
(Note that the performance of the checks we did require are considered too 
expensive such that some of those will be eliminated from Ada 2020's 
definition.)

That said, another goal was to allow (but not require) dangling cursor 
detection -- an implementation *can* detect dangling cursors if it wants. 
There are definitely schemes available that can detect 99% of such problems 
(noting that some corner cases can't be detected) without much extra 
overhead. It's also possible that an implementation could have a "checking" 
implementation of the containers to make such checks as well as a "fast" 
implementation that does not.

                                                 Randy.