Fix order of units stored by [store_unit]

[mattsc]

The wiki claims that "units will be stored in order of their internal underlying_id attribute" by [store_unit]. That is currently not true with the [store_unit] tag coded in Lua and can cause units to be stored in different orders in the same situation. That, in turn, can lead to OOS errors when orders are different between what happens in game and in a replay, such as the OOS error reported here. And while it is true that it would be better to have WML that is not dependent on the order of the stored units, there should not be a difference between what happens in game and in a replay.

The proposal:

• Reinstate sorting by underlying_id as it apparently was the case in earlier Wesnoth versions. This requires two table.sort() commands in data/lua/wml-tags.lua (or one table.sort() and one merging of the two tables). The problem is that underlying_id is not a field of the unit proxy table, and going through the table dump is slow. Thus, the second part of the proposal is:
• Add underlying_id to the unit proxy table as a read-only field. I have encountered several occasions in my AI work where I would like this to be the case anyway, for other reasons.

I have coded both (it requires a total of 3 lines of code, 2 in Lua, 1 in C++) and timed it. If 500 units are being stored, it takes about 5 milliseconds, while the overall execution takes about 150-200. I believe this is well worth the benefits, esp. since storing 500 units does not happen all that often ...

So, if nobody complains too loudly, I will commit this shortly.

[Anonymissimus]

IIRC I mentioned exactly this order as a feature which must not become bugged at the point a certain former dev refactored the unit map, whose name I cannot mention as shadowmaster kills me then.
After all, refactoring the unit map wasn't worth it then, especially considering the code complication. Reason was to improve performance, which is reduced by the sorting anyway then.
So, your fix seems just a workaround for the true fix which should be reverting the changes to the unit map.
It is also probably not enough to fix store_unit only; any time a SUF is called at the same gamestate it is not guaranteed to get the same result, if what you're saying is true *and* the filter criterias do not identify a single unit in particular.

[mattsc]

Thanks for the comments, Anonymissimus. That all apparently happened "before my time" so I don't know anything about it. If you or anybody else want to fix this by changing the unit map, I'm all for that.

It is also probably not enough to fix store_unit only; any time a SUF is called at the same gamestate it is not guaranteed to get the same result, if what you're saying is true *and* the filter criterias do not identify a single unit in particular.

Rats, you are right ... I just hacked into the two saves I have where I get different behavior between in-game save and replay and replaced the offending [store_unit] with a [teleport]. A different unit gets teleported indeed in one than in the other. Well, I'll have a look to see if I can find out what the real fix would be, but I might be in over my head here. Any help would be appreciated, even just pointers to where to look... It would be really good to have this fixed for 1.12.

[Anonymissimus]

It would be nice to check whether this faulty behavior does not yet occur in versions previously to commit 9da3b6ac61970bc31371f8b1ddd25ccc1b367b20 (02.08.2011, mid to late 1.9, so bug present in 1.10.x as well).
I'm of course assuming that the change from using std::map (ordered by keys = underlying_id) to boost::unordered_map ("unordered") is actually responsible. It feels too simple to me, and I mentioned the ordering back then, so I wonder why the change was made at all.

[mattsc]

So it took some time to get these tests done, because I couldn't find an easy way to reproduce the problem at first. It's another one of those bugs that depends on how you play through a scenario. If you play straight through a scenario, everything's fine, no matter what you do in WML. There's only a problem if, at some point, you load an intermediate save. In a nutshell, the order of units retrieved by SUFs from unit_map is always in inverse order in which they were put on the map, just that the order in which they are put on the map from a saved game is different from what happens in game. There are more detailed (but also less coherent) ramblings in today's IRC log, for those of you interested in more details.

The bottom line is this: because of the way how savegames are set up, it is not possible to reconstruct the order of units from the save (other than maybe having the game play through the replay every single time a game is loaded). Thus, ordering needs to be enforced in some other way, either by having unit_map sorted or by sorting the units when extracting them with a filter.

And a simple test to show that this is a serious problem: in 1.11, start HttT (or any other campaign or MP scenario), recruit two units, save game, load that save, recruit two more units and save a replay. Then watch that replay produce an OOS error after the second recruit.
[The problem also exists in 1.10, but it does not cause the replay OOS error there, so it is not as obvious.]

Finally, I confirmed that the problem is present in 1.11.7+dev, 1.11.5, 1.10.6 and 1.9.9 (released 4 Sep 2011), but not in 1.9.8 (released 24 July 2011).

Also, moved to Technical Support as this clearly is not a Lua issue, contrary to what I thought originally.

[AI]

I believe the issue is something like this:
-When a unit is added, it is pushed to the front of a linked list (std::list<unit_pod>)
-Iterating over the unit_map is implemented by iterating over this list
-This preserves ordering during a single playthrough
-When loading a saved game, the sides are loaded in order, so the units are added in that order too, with the leaders being special-cased
-The units are probably stored by iterating over them, causing the order to reverse

If preserving ordering by underlying_id was a requirement, I have no idea how this implemenation passed inspection, since the std::list<unit_pod> that preserves ordering (by (inverse) order of addition) was added in a later patch.

I don't really see any options other than going back to an ordered map.

Also, moved to coder's corner.

[Anonymissimus]

If preserving ordering by underlying_id was a requirement, I have no idea how this implemenation passed inspection, since the std::list<unit_pod> that preserves ordering (by (inverse) order of addition) was added in a later patch

I mentioned the ordering by underlying_id once the patch had already been applied, perhaps this was the reaction.

Well, personally I never needed the ordering by underlying_id and wouldn't mind giving up on that, and lua can do it with table.sort and a getter for underlying_id; but some (any) ordering needs to be preserved/be deterministic to prevent these OOS.

(I'd also like the unit_map to be not so much of an extremely cryptic piece of code. Typedefs such as
typedef value_type* pointer;
are just pointless, that doesn't reallly save a lot of typing.)

[gfgtdf]

if i remember correctly there was an intent to replace underlying_id with a UUID which is also saved during savegames and replays, anyone know what happend to this plan ?
(you could also generate the UUID with the deterministic rand.)

[AI]

Well, I've just taken a look at [patch]2819[/patch], and the attached performance profiles do suggest the unordered_map is a big improvement. I think I may be able to restore ordering by turning just one of the two maps (the underlying_id->unit one, which is not the one that's used in the critical codepath) back into an std::map and basing the iterators on that.

I haven't heard of the UUID thing, though it could fix bug #18877 [Gna.org].

[gfgtdf]

ok another question: in which cases id the normal "id" not unique and why do we need the underlying_id ?

EDIT: ok i just tested and found out that the game lets you have several units with the same id.

i still want to know what could be the disadvantages of storing the underlying_id's in replays, or generating them with the synced rand?

[AI]

I just checked the [unstore_unit] code, and it checks the underlying_id when storing to the recall list, while the unit_map checks the underlying_id when units are put onto the map. Nothing in this codepath checks for duplicates of the regular ID though. (so you could unstore a single unit 100 times)

Update: I have a fix in a personal fork. It still needs some more work before I can push it to master, but it's ready for testing.

Update: Merged in ffc68170fedc4312892438fd1f33235c14512fcd.