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

Resolve conflicts of MapNode with duplicate key caused by concurrent update to the same key with different type values other than primitive #14

Open
TanUkkii007 opened this issue Jan 14, 2017 · 1 comment

Comments

@TanUkkii007
Copy link
Contributor

Document state to JSON conversion introduced from #12 does not handle duplicate key as reported at this comment.

Duplicate key can be made when MapNode is updated with different type values other than primitive.

For example, concurrently updating to the same key "key" with object and string

val p1 = p0
    .applyCmd(doc.downField("key") := `{}`)
    .applyCmd(doc.downField("key").downField("key2") := "D")
val q1 = q0.applyCmd(doc.downField("key") := "C")
merge(p1, q1)

results in duplicate keys, RegT(StrK(key)) and MapT(StrK(key)).

MapNode(
  Map(
    MapT(DocK) -> MapNode(
      Map(
        RegT(StrK(key)) -> RegNode(Map(Id(2,q) -> Str(C))),
        MapT(StrK(key)) -> MapNode(Map(RegT(StrK(key2)) -> RegNode(Map(Id(3,p) -> Str(D)))),Map(StrK(key2) -> Set(Id(3,p))))
      ),
      Map(StrK(key) -> Set(Id(2,p), Id(3,p), Id(2,q)))
    )
  ),
  Map(DocK -> Set(Id(1,p), Id(2,p), Id(3,p), Id(2,q)))
)
@TanUkkii007
Copy link
Contributor Author

TanUkkii007 commented Jan 14, 2017

I suspect ListNode might have duplicate index as well as MapNode but have not reproduced it yet. Lemma 4 says that concurrent insertion to the same cursor will result in deterministic order so ListNode will not have duplicate indexes by INSERT. Lemma 7 says that concurrent ASSIGN operation with non-primitive values to the same position will have different keys. Checking ListNode state under concurrent assignment to the same position would help our understandings.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant