You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Morgan Delagrange <md...@yahoo.com> on 2002/05/08 20:08:40 UTC
[Collections] Bug or Feature? - SequencedHashMap iterators do not throw ConcurrentModificationExceptions
Hi all,
In tracking down a bug in LRUMap, I added a new unit test to testMap() to
check if all our Map Iterators throw ConcurrentModificationExceptions when
the underlying collection is modified. SequencedHashMap does not. I know
that it's not absolutely _required_ to handle modifications that way, but
should we classify this as a bug or an unsupported feature? It seems risky
not to throw a ConcurrentModificationException, because it probably makes
the behaviour of the Iterator indeterminate, and in the case of LRUMap I
think it's leading to an infinite promotion loop.
- Morgan
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do
not throw ConcurrentModificationExceptions
Posted by "Michael A. Smith" <ma...@apache.org>.
On Wed, 8 May 2002, Morgan Delagrange wrote:
> Making a modification-resistant iterator might be a
> little tricky. E.g. what happens when, while
> iterating over a keySet, you iterate a, then remove a,
> and readd it later in the iteration? A set iteration
> with duplicates? :)
yes, definately a bug.
> > I assume your get looks like this:
> >
> > public Object get(Object key) {
> > // need explicit check for contains so we don't
> > add in a mapping to
> > // null if a mapping to null didn't exist
> > before.
> > if(!contains(key)) return null;
> >
> > Object value = remove(key);
> > put(key, value);
> >
> > return value;
> > }
>
> Yep, except that the containsKey() check is still in
> my notes, not in CVS.
I'll add it. :)
> > and something is iterating and calling get within
> > the iterator...
>
> Right, it's the testSequenceMap test in your
> TestSequencedHashMap class. I overrode it in my
> TestHashMap subclass just to avoid the infinite loop;
> you'll want to comment my override out.
ok.
michael
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do not throw ConcurrentModificationExceptions
Posted by Morgan Delagrange <md...@yahoo.com>.
Oops forgot to respond to this part.
--- "Michael A. Smith" <ma...@apache.org> wrote:
>
>
> I assume your get looks like this:
>
> public Object get(Object key) {
> // need explicit check for contains so we don't
> add in a mapping to
> // null if a mapping to null didn't exist
> before.
> if(!contains(key)) return null;
>
> Object value = remove(key);
> put(key, value);
>
> return value;
> }
Yep, except that the containsKey() check is still in
my notes, not in CVS.
> and something is iterating and calling get within
> the iterator...
>
Right, it's the testSequenceMap test in your
TestSequencedHashMap class. I overrode it in my
TestHashMap subclass just to avoid the infinite loop;
you'll want to comment my override out.
- Morgan
=====
Morgan Delagrange
http://jakarta.apache.org/taglibs
http://jakarta.apache.org/commons
http://axion.tigris.org
__________________________________________________
Do You Yahoo!?
Yahoo! Health - your guide to health and wellness
http://health.yahoo.com
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do
not throw ConcurrentModificationExceptions
Posted by "Michael A. Smith" <ma...@apache.org>.
On Thu, 9 May 2002, Morgan Delagrange wrote:
> Great, now all we have to do is figure out what kind
> of release this necessitates. It's a bug fix for
> LRUMap, but I'm a little nervous because it will
> probably introduce new exceptions to a few clients.
>
> I think it's acceptable to release this as Collections
> 2.0.1, yes?
yes, probably.
regards,
michael
>
> - Morgan
>
> --- "Michael A. Smith" <mi...@iammichael.org> wrote:
> > On Wed, 8 May 2002, Michael A. Smith wrote:
> > > Another solution would be to fix the end of the
> > list at the time of
> > > iterator creation. That way, new elements aren't
> > reflected in previously
> > > created iterators. I like that better than
> > throwing
> > > ConcurrentModificationException. That should be a
> > fairly easy fix and I
> > > can put that in this evening.
> >
> > It turns out, this doesn't work. At least not
> > easily. At first, I
> > thought I could just save the last entry, and don't
> > let the iterator
> > iterate past it; however, if the last entry is
> > removed before the iterator
> > gets to it, that last entry will never be reached
> > and you still may end up
> > in an infinite loop.
> >
> > The only way I could think of to get around that
> > would be to add a
> > monotonically increasing "id" of some kind to each
> > entry and store the id
> > of the last entry. If the iterator reaches an entry
> > with an id greater
> > than it's saved id, then the iterator stops.
> > However, that seems like a
> > large memory waste.
> >
> > Instead, I modified things to throw a concurrent
> > modification exception.
> > My commit message should come across momentarily.
> >
> > regards,
> > michael
> >
> >
> > --
> > To unsubscribe, e-mail:
> > <ma...@jakarta.apache.org>
> > For additional commands, e-mail:
> > <ma...@jakarta.apache.org>
> >
>
>
> =====
> Morgan Delagrange
> http://jakarta.apache.org/taglibs
> http://jakarta.apache.org/commons
> http://axion.tigris.org
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Shopping - Mother's Day is May 12th!
> http://shopping.yahoo.com
>
> --
> To unsubscribe, e-mail: <ma...@jakarta.apache.org>
> For additional commands, e-mail: <ma...@jakarta.apache.org>
>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do not throw ConcurrentModificationExceptions
Posted by Morgan Delagrange <md...@yahoo.com>.
Great, now all we have to do is figure out what kind
of release this necessitates. It's a bug fix for
LRUMap, but I'm a little nervous because it will
probably introduce new exceptions to a few clients.
I think it's acceptable to release this as Collections
2.0.1, yes?
- Morgan
--- "Michael A. Smith" <mi...@iammichael.org> wrote:
> On Wed, 8 May 2002, Michael A. Smith wrote:
> > Another solution would be to fix the end of the
> list at the time of
> > iterator creation. That way, new elements aren't
> reflected in previously
> > created iterators. I like that better than
> throwing
> > ConcurrentModificationException. That should be a
> fairly easy fix and I
> > can put that in this evening.
>
> It turns out, this doesn't work. At least not
> easily. At first, I
> thought I could just save the last entry, and don't
> let the iterator
> iterate past it; however, if the last entry is
> removed before the iterator
> gets to it, that last entry will never be reached
> and you still may end up
> in an infinite loop.
>
> The only way I could think of to get around that
> would be to add a
> monotonically increasing "id" of some kind to each
> entry and store the id
> of the last entry. If the iterator reaches an entry
> with an id greater
> than it's saved id, then the iterator stops.
> However, that seems like a
> large memory waste.
>
> Instead, I modified things to throw a concurrent
> modification exception.
> My commit message should come across momentarily.
>
> regards,
> michael
>
>
> --
> To unsubscribe, e-mail:
> <ma...@jakarta.apache.org>
> For additional commands, e-mail:
> <ma...@jakarta.apache.org>
>
=====
Morgan Delagrange
http://jakarta.apache.org/taglibs
http://jakarta.apache.org/commons
http://axion.tigris.org
__________________________________________________
Do You Yahoo!?
Yahoo! Shopping - Mother's Day is May 12th!
http://shopping.yahoo.com
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do
not throw ConcurrentModificationExceptions
Posted by "Michael A. Smith" <mi...@iammichael.org>.
On Wed, 8 May 2002, Michael A. Smith wrote:
> Another solution would be to fix the end of the list at the time of
> iterator creation. That way, new elements aren't reflected in previously
> created iterators. I like that better than throwing
> ConcurrentModificationException. That should be a fairly easy fix and I
> can put that in this evening.
It turns out, this doesn't work. At least not easily. At first, I
thought I could just save the last entry, and don't let the iterator
iterate past it; however, if the last entry is removed before the iterator
gets to it, that last entry will never be reached and you still may end up
in an infinite loop.
The only way I could think of to get around that would be to add a
monotonically increasing "id" of some kind to each entry and store the id
of the last entry. If the iterator reaches an entry with an id greater
than it's saved id, then the iterator stops. However, that seems like a
large memory waste.
Instead, I modified things to throw a concurrent modification exception.
My commit message should come across momentarily.
regards,
michael
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do not throw ConcurrentModificationExceptions
Posted by Morgan Delagrange <md...@yahoo.com>.
--- "Michael A. Smith" <ma...@apache.org> wrote:
> On Wed, 8 May 2002, Morgan Delagrange wrote:
> > > Iterators should be able to continue iterating
> and see any concurrent
> > > modifications made to the map*. If the iterator
> is looking at an element
> > > that is removed, and then "next" is called, the
> iterator should continue
> > > where it left off, even though the element was
> removed. If an element is
> > > added, it's added at the end of the list, and
> the iterator should iterate
> > > to it when it gets to the end of the list (note:
> if the iterator has
> > > already reached the end of the list, hasNext is
> false, and then a new
> > > mapping is added, the iterator will then return
> true from hasNext as the
> > > new element can then be iterated over).
> >
> > I think it may be working all too well. The
> LRUMap promotion removes keys
> > and re-adds them to the end, which I think the
> iterator may be reading over
> > and over. Perhaps a
> ConcurrentModificationException would be safer.
>
> ah, I see the problem now.
>
> Another solution would be to fix the end of the list
> at the time of
> iterator creation. That way, new elements aren't
> reflected in previously
> created iterators. I like that better than throwing
>
> ConcurrentModificationException. That should be a
> fairly easy fix and I
> can put that in this evening.
That might work.
Making a modification-resistant iterator might be a
little tricky. E.g. what happens when, while
iterating over a keySet, you iterate a, then remove a,
and readd it later in the iteration? A set iteration
with duplicates? :)
- Morgan
=====
Morgan Delagrange
http://jakarta.apache.org/taglibs
http://jakarta.apache.org/commons
http://axion.tigris.org
__________________________________________________
Do You Yahoo!?
Yahoo! Health - your guide to health and wellness
http://health.yahoo.com
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do
not throw ConcurrentModificationExceptions
Posted by "Michael A. Smith" <ma...@apache.org>.
On Wed, 8 May 2002, Morgan Delagrange wrote:
> > Iterators should be able to continue iterating and see any concurrent
> > modifications made to the map*. If the iterator is looking at an element
> > that is removed, and then "next" is called, the iterator should continue
> > where it left off, even though the element was removed. If an element is
> > added, it's added at the end of the list, and the iterator should iterate
> > to it when it gets to the end of the list (note: if the iterator has
> > already reached the end of the list, hasNext is false, and then a new
> > mapping is added, the iterator will then return true from hasNext as the
> > new element can then be iterated over).
>
> I think it may be working all too well. The LRUMap promotion removes keys
> and re-adds them to the end, which I think the iterator may be reading over
> and over. Perhaps a ConcurrentModificationException would be safer.
ah, I see the problem now.
Another solution would be to fix the end of the list at the time of
iterator creation. That way, new elements aren't reflected in previously
created iterators. I like that better than throwing
ConcurrentModificationException. That should be a fairly easy fix and I
can put that in this evening.
> > That is, of course, assuming things are working properly. If you're
> > seeing problems, then maybe something *is* broken, and thus a bug may be
> > lurking. I'll take a look tonight as to why LRUMap is getting in an
> > infinite loop just in case there really is a bug somewhere.
>
> Just to give you a bit of background... It turns out that, somehow, I
> forgot to add get(Object) promotion to LRUMap and that, somehow, we didn't
> have any unit tests for it. So I'm trying to add that promotion, but I'm
> getting this infinite loop for the testSequenceMap test in the
> TestSequencedHashMap class. It's clearly caused by the new get(Object)
> promotion somehow. Feel free to take a look; I'm done for today. Getting
> crosseyed...
I assume your get looks like this:
public Object get(Object key) {
// need explicit check for contains so we don't add in a mapping to
// null if a mapping to null didn't exist before.
if(!contains(key)) return null;
Object value = remove(key);
put(key, value);
return value;
}
and something is iterating and calling get within the iterator...
I'll take a look tonight and fix things up.
regards,
michael
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do not throw ConcurrentModificationExceptions
Posted by Morgan Delagrange <md...@yahoo.com>.
----- Original Message -----
From: "Michael A. Smith" <ma...@apache.org>
To: "Jakarta Commons Developers List" <co...@jakarta.apache.org>;
"Morgan Delagrange" <mo...@apache.org>
Sent: Wednesday, May 08, 2002 1:45 PM
Subject: Re: [Collections] Bug or Feature? - SequencedHashMap iterators do
not throw ConcurrentModificationExceptions
> On Wed, 8 May 2002, Morgan Delagrange wrote:
> > In tracking down a bug in LRUMap, I added a new unit test to testMap()
to
> > check if all our Map Iterators throw ConcurrentModificationExceptions
when
> > the underlying collection is modified. SequencedHashMap does not. I
know
> > that it's not absolutely _required_ to handle modifications that way,
but
> > should we classify this as a bug or an unsupported feature? It seems
risky
> > not to throw a ConcurrentModificationException, because it probably
makes
> > the behaviour of the Iterator indeterminate, and in the case of LRUMap I
> > think it's leading to an infinite promotion loop.
>
> Not throwing a ConcurrentModificationException is not a violation of the
> contracts, so it isn't really a "bug". I'm a bit concerned though because
> I believe the SequencedHashMap should support concurrent modifications via
> the map or the iterator.
>
> Iterators should be able to continue iterating and see any concurrent
> modifications made to the map*. If the iterator is looking at an element
> that is removed, and then "next" is called, the iterator should continue
> where it left off, even though the element was removed. If an element is
> added, it's added at the end of the list, and the iterator should iterate
> to it when it gets to the end of the list (note: if the iterator has
> already reached the end of the list, hasNext is false, and then a new
> mapping is added, the iterator will then return true from hasNext as the
> new element can then be iterated over).
I think it may be working all too well. The LRUMap promotion removes keys
and re-adds them to the end, which I think the iterator may be reading over
and over. Perhaps a ConcurrentModificationException would be safer.
> That is, of course, assuming things are working properly. If you're
> seeing problems, then maybe something *is* broken, and thus a bug may be
> lurking. I'll take a look tonight as to why LRUMap is getting in an
> infinite loop just in case there really is a bug somewhere.
Just to give you a bit of background... It turns out that, somehow, I
forgot to add get(Object) promotion to LRUMap and that, somehow, we didn't
have any unit tests for it. So I'm trying to add that promotion, but I'm
getting this infinite loop for the testSequenceMap test in the
TestSequencedHashMap class. It's clearly caused by the new get(Object)
promotion somehow. Feel free to take a look; I'm done for today. Getting
crosseyed...
> As for throwing ConcurrentModificationException, I really don't think its
> necessary. There's no reason why we can't support modification of the map
> while an iterator exists with this particular collection.
>
> regards,
> michael
>
> * This does not mean that SequencedHashMap is thread-safe. It just means
> that if only one thread at a time is operating on the map or its
> iterators, then things should work without any problems.
>
>
>
> --
> To unsubscribe, e-mail:
<ma...@jakarta.apache.org>
> For additional commands, e-mail:
<ma...@jakarta.apache.org>
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] Bug or Feature? - SequencedHashMap iterators do
not throw ConcurrentModificationExceptions
Posted by "Michael A. Smith" <ma...@apache.org>.
On Wed, 8 May 2002, Morgan Delagrange wrote:
> In tracking down a bug in LRUMap, I added a new unit test to testMap() to
> check if all our Map Iterators throw ConcurrentModificationExceptions when
> the underlying collection is modified. SequencedHashMap does not. I know
> that it's not absolutely _required_ to handle modifications that way, but
> should we classify this as a bug or an unsupported feature? It seems risky
> not to throw a ConcurrentModificationException, because it probably makes
> the behaviour of the Iterator indeterminate, and in the case of LRUMap I
> think it's leading to an infinite promotion loop.
Not throwing a ConcurrentModificationException is not a violation of the
contracts, so it isn't really a "bug". I'm a bit concerned though because
I believe the SequencedHashMap should support concurrent modifications via
the map or the iterator.
Iterators should be able to continue iterating and see any concurrent
modifications made to the map*. If the iterator is looking at an element
that is removed, and then "next" is called, the iterator should continue
where it left off, even though the element was removed. If an element is
added, it's added at the end of the list, and the iterator should iterate
to it when it gets to the end of the list (note: if the iterator has
already reached the end of the list, hasNext is false, and then a new
mapping is added, the iterator will then return true from hasNext as the
new element can then be iterated over).
That is, of course, assuming things are working properly. If you're
seeing problems, then maybe something *is* broken, and thus a bug may be
lurking. I'll take a look tonight as to why LRUMap is getting in an
infinite loop just in case there really is a bug somewhere.
As for throwing ConcurrentModificationException, I really don't think its
necessary. There's no reason why we can't support modification of the map
while an iterator exists with this particular collection.
regards,
michael
* This does not mean that SequencedHashMap is thread-safe. It just means
that if only one thread at a time is operating on the map or its
iterators, then things should work without any problems.
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>