planetarium / planetarium/lib9c

Make `Inventory.Serialize()` deterministic

Open
#2,425 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C#
Stars
30
Forks
56
Avg merge
9h 2m
Merged PRs (30d)
6

Description

Relevant parts are

https://github.com/planetarium/lib9c/blob/be6c238677a498e93d692d3510b00234d5b3590f/Lib9c/Model/Item/Inventory.cs#L144-L147
for serialization and

https://github.com/planetarium/lib9c/blob/be6c238677a498e93d692d3510b00234d5b3590f/Lib9c/Model/Item/Inventory.cs#L134-L142
https://github.com/planetarium/lib9c/blob/be6c238677a498e93d692d3510b00234d5b3590f/Lib9c/Model/Item/Inventory.cs#L66-L78
for deserialization.

Neither guarantees to be deterministic. It just so happens that we haven't had any serious problems such as IAction.Execute() not returning a different serialized result, but for all we know, the ordering can be C# language version/target framework/implementation specific. It has already been observed that two identical inventories can be stored differently. I haven't dug deeper into the issue as to why exactly this has happened, but my guess would be

var inventory = new Inventory(serialized);
Assert.Equal(serialized, inventory.Serialize());

is not always the case. Furthermore, many mutating methods on Inventory also seem that they may not be deterministic (especially those with Remove() combined with rather complicated argument selection process).

Also this happens to waste much storage space as an inventory can get "shuffled" during IAction.Execute() even if there is no change in its content resulting in writing multiple copies of rather large serialized representation of the said inventory.

There are two possible ways to resolve this:

  • Provide a better total ordering on all possible items. This may be hard as Item class seems to have too many parameters and it may be expanded at any time, which would require us to redefine ordering over and over. Besides, this would be very easy to overlook, that is, to update Item and miss updating Compare() and CompareTo() implementations.
  • Treat Inventory as a proper list and do not sort anything when serializing or deserializing. This doesn't solve the issue of possible non-determinism of an Item removal, but would reduce some possible risks and save some storage space. This would be more suitable if there isn't any external code that relies on current Inventory's implementation of ordering. One possible concern may be when drawing the Inventory on the GUI side, but this work can be offloaded to the client side.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with Lib9c/Model/Item/Inventory.cs, especially the serialization lines 144-147 and deserialization lines 134-142 and 66-78. Reproduce the issue with the provided Inventory round-trip assertion, then determine which ordering behavior must be covered by tests. Done means equivalent inventories serialize deterministically without unnecessary shuffled representations.

Written by the indexing model from the issue text.

Assessment

Tech stack
csharp
Domain
game-dev
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.