Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

AnyLuaValue derives PartialEq; but LuaArray is ordered #178

Open
tpdickso opened this issue Nov 6, 2017 · 0 comments
Open

AnyLuaValue derives PartialEq; but LuaArray is ordered #178

tpdickso opened this issue Nov 6, 2017 · 0 comments
Labels

Comments

@tpdickso
Copy link

tpdickso commented Nov 6, 2017

This is probably not correct for the case of a LuaArray, as lua tables are unordered, but the table itself is stored as a Vec<(AnyLuaValue, AnyLuaValue)> which compares unequal if the keys are in a different order. Thus, if you read the same table from lua twice, it may compare unequal with itself if its keys are not read in the same order.

This is worse for AnyHashableLuaValue, which derives Eq and Hash: If you create some kind of hash map using a lua value as a key, you may not be able to retrieve the correct value even by reading the exact same table as a key.

In the case of AnyHashableLuaValue, since we've already guaranteed that the key values are themselves hashable, it may make sense just to store LuaArray as a HashMap; this allows to derive Eq correctly without needing anything fancy. However, a custom Hash impl will still be needed, as the stock HashMap does not implement it. There is also no Ord, but to be honest, I'm not even sure what a correct Ord for AnyHashableLuaValue would look like; perhaps lexicographic ordering on sorted key-value pairs? In that case, maybe a BTreeMap would be more efficient, as one could avoid allocations in cmp.

In the case of AnyLuaValue, the easiest cop-out is to impl PartialEq to return false when both values are LuaArray, but this is probably not the expected behaviour. As far as I know a correct algorithm that doesn't take extra allocations would unfortunately be $$O(n^2)$$ comparing each key-value pair to each other key-value pair, but this is probably nevertheless what's called for in this situation.

@tomaka tomaka added the bug label Nov 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants