Closed liz3 closed 7 months ago
We wouldn't want this as there is a potential that the element has wrapped around to the start - will need some more investigation into your issue as to why you're currently getting an infinite loop (more than likely something being freed when it shouldn't have if it's non-deterministic)
This condition only applies once all the entries where iterated at least once, so wrapping around should'nt affect it. The bug only occurs on insert.
Ofc it might be that the dict is shrunken when it should'nt leading to there being no elements "free" as in no key and no value. So the issue is deterministic but my repro example isn't since the algo is inherently based on randomness(seeing the issue) making the way the dicts resize not deterministic. But the condition is: some sized dict with no entries where both the key and the value are unset(only occupied or tombstones).
Ah yes sorry you're right the count would have to be the full size of the internal list. Yeah I'd like to do a little more research into this as if this is an issue here (as in finding elements in the dict) it would be an issue with the internal Table type that came from craftinginterpreters which could be a much bigger issue as this type is used throughout the codebase.
Many thanks for the PR and the really detailed issue by the way!
@Jason2605 Apologies it took a while i had to do some debugging but heres a deterministic example to correctly and always reproduce the deadlock:
var e = {};
e["lkc"] = 1;
e["qvh"] = 1;
e["bck"] = 1;
e["bks"] = 1;
e["bpp"] = 1;
e.remove("bks");
e["gpx"] = 1;
e.remove("bpp");
e["ndj"] = 1;
e.remove("lkc");
e["xmn"] = 1;
// this will fail
e["std"] = 1;
Maybe that can help.
Thank you so much for the simpler reproduction this will help me a lot!!
Okay yeah, so the issue is the fact that the count is being lowered but tombstones are still technically a "value" and aren't cleared until the dictionary is resized. For dictionaries we probably want a track of count
and maybe countActive
so we can expose the length to dictu code
Okay yeah, so the issue is the fact that the count is being lowered but tombstones are still technically a "value" and aren't cleared until the dictionary is resized. For dictionaries we probably want a track of
count
and maybecountActive
so we can expose the length to dictu code
Can you elaborate maybe on how to solve the issue the way you described, since i see two ways(unrelated of exposing the count as a public api):
The simplest solution in my eyes is to have an extra count
so countActive
that keeps tracks of values that are not tombstones and count
becomes the count of values + tombstones. count
would still be used the same internally as is and countActive
is what we'd use for .len()
Add countActive
https://github.com/dictu-lang/Dictu/blob/develop/src/vm/object.h#L148
countActive++
https://github.com/dictu-lang/Dictu/blob/develop/src/vm/value.c#L150
Remove count--
Add countActive--
https://github.com/dictu-lang/Dictu/blob/develop/src/vm/value.c#L162
countActive
https://github.com/dictu-lang/Dictu/blob/develop/src/vm/datatypes/dicts/dicts.c#L34
Ive changed the pr to reflect the discussed changes, let me know if i missed anything!
Thanks for this!
fix: correctly return tombstone when theres no free element
The dict findDictEntry function did not correctly handle the case when, a dict had no "free" slot but had tombstones, it would loop forever.
Resolves: https://github.com/dictu-lang/Dictu/issues/726
What's Changed:
This fixes that by conditionally returning a tombstone when all other indexes where processed.
Type of Change:
#
Housekeeping: