planetarium / planetarium/lib9c
Make `Inventory.Serialize()` deterministic
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
Itemclass 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 updateItemand miss updatingCompare()andCompareTo()implementations. - Treat
Inventoryas a proper list and do not sort anything when serializing or deserializing. This doesn't solve the issue of possible non-determinism of anItemremoval, 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 currentInventory's implementation of ordering. One possible concern may be when drawing theInventoryon the GUI side, but this work can be offloaded to the client side.
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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