#11494 closed defect (invalid)
BASE: Possible use of invalid iterators
Reported by: | Tkachov | Owned by: | criezy |
---|---|---|---|
Priority: | high | Component: | --Unset-- |
Version: | Keywords: | iterators, invalidate, erase | |
Cc: | Game: |
Description
I've stumbled onto C++ iterators-related comment (in Russian: https://habr.com/ru/post/492410/#comment_21566838): someone cached collection.end()
and then used i = collection.erase(i)
, which invalidates old iterators.
So I've decided to look through ScummVM code and I've found some places I think might use invalid iterators. I've used GitHub search and briefly read the files, so I might've skipped something or made a false positive mistake. Also, I'm not sure if ScummVM iterators invalidate after erase()
or not.
Anyways, here are these places:
for (TimerSlotMap::iterator i = _callbacks.begin(), end = _callbacks.end(); i != end; ++i) { if (i->_value == callback) _callbacks.erase(i);
_callbacks.end()
is cached, buterase()
is used.erase()
returns new valid iterator, but this code continues to use the old one.
Std::list<Gump *>::iterator end = _children.end(); while (it != end) { Gump *g = *it; it = _children.erase(it);
erase()
probably invalidates that cached end
. Comment up there says "Delete all children", so I don't see why erase()
is even needed. One could iterate through all the children, deleting each of them and then use clear()
. Or, maybe, do something like this:
while (!ch.empty()) { delete *ch.begin(); ch.erase(ch.begin()); }
https://github.com/scummvm/scummvm/blob/1a097b1d971e6e3cf3c10f6eb7c7a30def2d2f7c/engines/cruise/gfxModule.cpp#L252L265
and the same code at
https://github.com/scummvm/scummvm/blob/1a097b1d971e6e3cf3c10f6eb7c7a30def2d2f7c/engines/tony/gfxcore.cpp#L398L412
for (rOuter = _dirtyRects.begin(); rOuter != _dirtyRects.end(); ++rOuter) { rInner = rOuter; while (++rInner != _dirtyRects.end()) { ... // remove the inner rect from the list _dirtyRects.erase(rInner); // move back to beginning of list rInner = rOuter;
I see why this probably works: erase()
only invalidates iterators pointing to elements further than the erased one, so earlier iterators are fine. If that's not so, rOuter
should be as invalid as rInner
, and code probably should be rewritten to use integer indexes instead.
_subsList.erase(it);
The cycle goes on without break
or return
there, so erase()
return value should be used to update it
and it++
should not be called.
#define CLEAROPCODEGOB(i) _opcodesGob.erase(i)
I couldn't find usages of CLEAROPCODEGOB
, so I don't know if that is even related to iterators, but if it is, its return value should be used and end()
around there should not be cached.
Change History (4)
comment:1 by , 4 years ago
Summary: | Possible usage of invalid iterators → BASE: Possible use of invalid iterators |
---|
comment:2 by , 4 years ago
Priority: | low → high |
---|
comment:3 by , 4 years ago
Owner: | set to |
---|---|
Resolution: | → fixed |
Status: | new → closed |
comment:4 by , 4 years ago
Resolution: | fixed → invalid |
---|
Thank you for the reports.
The good news is that they are all false positive.
DefaultTimerManager: This is a false positive as _callbacks is a
Common::HashMap
and callingHashMap::erase(iterator)
does not invalidate iterators. Even iterators on the erased node remain partially valid. They can no longer be dereferenced, but can still be used for the iteration. Alsoerase()
does not actually return anything.Ultima8: This is also a false positive. This time the code is using a
Std::list
that derives fromCommon::List
.Common::List
is implemented as a linked list, and erase only invalidates iterators pointing to the erased item.Cruise and Tony: Again false positives. They are using a
Common::List<Common::Rect>
(so again only iterators to the erased items are invalidated).ZVision:
_subsList
is aSubtitleMap
which is a typedef tp aCommon::HashMap
. So the code is actually correct (HashMap::erase()
does not return an iterator, and we can continue iterating using the current one).Gob:
_opcodesGob
is aCommon::HashMap
. Soerase()
does not return anything and does not invalidate iterators.