dvv 0.1.2.0 → 0.1.2.1

raw patch · 5 files changed

+94/−14 lines, 5 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• README.md +13/−11
• changelog.md +3/−0
• dvv.cabal +1/−1
• src/Data/DVV.hs +31/−2
• test/Spec.hs +46/−0

@@ -2,8 +2,10 @@  [![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT) -A GHC-Haskell implementation of [**Dotted Version Vectors (DVV)**](https://gsd.di.uminho.pt/members/vff/dotted-version-vectors-2012.pdf), a data structure for tracking causality and resolving conflicts in distributed systems. This library is inspired by the canonical [Erlang example implementation](https://github.com/ricardobcl/Dotted-Version-Vectors).+A GHC-Haskell implementation of [**Dotted Version Vectors (DVV)**](https://gsd.di.uminho.pt/members/vff/dotted-version-vectors-2012.pdf), a data structure for tracking causality and resolving conflicts in distributed systems updating a single piece of data. +This library is inspired by the canonical [Erlang DVVSet example implementation](https://github.com/ricardobcl/Dotted-Version-Vectors).+ ## Table of Contents  - [Introduction](#introduction)@@ -21,18 +23,18 @@  **Dotted Version Vectors** solve this by combining: 1.  **History (Context):** A summary of all events seen by the system.-2.  **Dots:** Discrete events (actor + sequence number) that created specific values.+2.  **Dots:** Discrete events (actor + sequence number) that updated specific values 3.  **Siblings:** A set of values that are concurrent (i.e., none of them has "seen" the others).  ## Key Concepts --   **Dot:** A pair `{Actor, Counter}` representing a single write.--   **History (Version Vector):** A mapping from actors to their latest sequence numbers.--   **DVV:** A structure containing a history and a set of active siblings.+-   **Dot:** A pair `Actor x Count` representing a single write.+-   **History (Version Vector):** A mapping from actors to their latest sequence numbers. `Map Actor Count`+-   **DVV:** A structure containing a history and a set of active siblings. `Map Actor Count x Map Dot Value`  ### How it Works -DVV provides a mechanism for **causal ordering**. When an actor writes a value, it creates a "Dot" – a unique identifier for that specific version of the data. +DVV provides a mechanism for **causal ordering**. When an actor writes a value, it creates a "Dot" – a unique identifier for that specific version of the data. Usually the "server", i.e. the thing doing the tracking of state is the "actor".  ```mermaid graph TD@@ -52,17 +54,17 @@  ### 1. Construction and Initialization -You can start with an empty DVV or a singleton:+You can start with an empty DVV or a singleton, i.e. no causal history, without a value or with the first value (count implicitly = 1):  ```haskell import Data.DVV import qualified Data.HashMap.Strict as Map --- An empty DVV+-- An empty DVV without any causal history empty :: DVV String Int empty = EmptyDVV --- A singleton DVV (initial write)+-- A singleton DVV (initial write with no prior causal history) initial :: DVV String Int initial = SingletonDVV "actor1" 42 ```@@ -100,7 +102,7 @@ #### Manual Reconciliation  ```haskell--- Pick the maximum value from siblings+-- Pick the maximum value from siblings, reconcile just takes a deterministic "decider" function over a pair of `concurrent values`. let resolved = reconcile max "resolver-actor" merged ``` @@ -126,7 +128,7 @@  ## Type Safety -This library uses `HashMap` internally for efficiency and requires actor IDs to be instances of `Hashable`. The `DVV` type is also an instance of `Functor`, `Foldable`, and `Traversable`, making it easy to manipulate the stored values.+This library uses `HashMap` internally for efficiency and requires actor IDs to be instances of `Hashable`.  ## Performance Considerations 

@@ -1,3 +1,6 @@+# 0.1.2.1 [James R. Thompson](mailto:jamesthompsonoxford@gmail.com) February 2026+Improve documentation and fix Eq instance+ # 0.1.2.0 [James R. Thompson](mailto:jamesthompsonoxford@gmail.com) February 2026 Hide VersionVector field accessors to force smart constructor usage 

@@ -1,6 +1,6 @@ cabal-version:      3.0 name:               dvv-version:            0.1.2.0+version:            0.1.2.1 license:            MIT license-file:       LICENSE copyright:          2026-Present, James R. Thompson

@@ -39,10 +39,11 @@ where  import Algebra.PartialOrd (PartialOrd (..))+import Data.Function (on) import Data.HashMap.Strict (HashMap) import qualified Data.HashMap.Strict as Map import Data.Hashable (Hashable (..))-import Data.List (foldl', foldl1', sortBy)+import Data.List (foldl', foldl1', sort, sortBy) import Data.Maybe (fromMaybe) import Data.Word (Word64) import GHC.Generics (Generic)@@ -111,7 +112,35 @@   = EmptyDVV   | SingletonDVV !actorID !value   | DVV !(VersionVector actorID) !(HashMap (Dot actorID) value)-  deriving stock (Eq, Show, Generic)+  deriving stock (Generic)++instance (Hashable actorID, Eq value) => Eq (DVV actorID value) where+  EmptyDVV == EmptyDVV = True+  SingletonDVV a1 v1 == SingletonDVV a2 v2 = a1 == a2 && v1 == v2+  DVV vv1 dots1 == DVV vv2 dots2 = vv1 == vv2 && dots1 == dots2+  l == SingletonDVV a2 v2 = l == event EmptyDVV Nothing a2 v2+  SingletonDVV a1 v1 == r = event EmptyDVV Nothing a1 v1 == r+  _ == _ = False++instance+  (Show actorID, Show value, Ord actorID, Hashable actorID) =>+  Show (DVV actorID value)+  where+  show dvv =+    case dvv of+      EmptyDVV -> "([],[])"+      _ ->+        let (_, dots) = extractComponents dvv+            ctx = getVersionVectorCounts (context dvv)+            allActors = sort (Map.keys ctx)+            dotsList = Map.toList dots+            groupedValues a =+              map snd $+                sortBy (flip compare `on` (\(Dot _ c, _) -> c)) $+                  filter (\(Dot a' _, _) -> a' == a) dotsList++            formattedEntries = [(a, Map.findWithDefault 0 a ctx, groupedValues a) | a <- allActors]+         in show (formattedEntries, [] :: [value])  isSeenBy ::   (Ord actorID, Hashable actorID) =>

@@ -171,6 +171,52 @@       -- B remains at 1 (as history).       context dLWW `shouldBe` mkVersionVector (Map.fromList [("A", 2), ("B", 1)]) +  describe "DVV Show Instance" $ do+    it "should show EmptyDVV as Erlang empty DVVSet" $ do+      show (EmptyDVV :: DVV ID Value) `shouldBe` "([],[])"++    it "should show SingletonDVV as Erlang DVVSet with one entry" $ do+      let d = SingletonDVV "A" "v1" :: DVV ID Value+      -- ( [("A", 1, ["v1"])], [] )+      show d `shouldBe` "([(\"A\",1,[\"v1\"])],[])"++    it "should show concurrent values grouped by actor" $ do+      let dA = SingletonDVV "A" "v1" :: DVV ID Value+          dB = SingletonDVV "B" "v2"+          d0 = sync dA dB+      -- Two concurrent values: A:1:v1 and B:1:v2+      show d0 `shouldBe` "([(\"A\",1,[\"v1\"]),(\"B\",1,[\"v2\"])],[])"++    it "should show causal history and concurrent values correctly" $ do+      let dA = SingletonDVV "A" "v1" :: DVV ID Value+          ctxA = context dA+          dB = event dA (Just ctxA) "B" "v2"+      -- A:1 is history, B:1 is the current value+      -- Format: [("A",1,[]), ("B",1,["v2"])]+      show dB `shouldBe` "([(\"A\",1,[]),(\"B\",1,[\"v2\"])],[])"++    it+      "should correctly handle the example scenario from the Erlang documentation example"+      $ do+        -- Image Step 1: C1 PUT v1 ~ {} -> State A (A, 1, [v1])+        let s0 = EmptyDVV :: DVV ID Value+            s1 = event s0 Nothing "A" "v1"+            s1' = SingletonDVV "A" "v1"+        s1 `shouldBe` s1'+        show s1 `shouldBe` "([(\"A\",1,[\"v1\"])],[])"++        -- Image Step 2: C2 PUT v2 ~ {} -> State A (A, 2, [v2, v1])+        -- C2's PUT is concurrent with C1's (context {})+        let emptyCtx = mkVersionVector Map.empty+            s2 = event s1 (Just emptyCtx) "A" "v2"+        show s2 `shouldBe` "([(\"A\",2,[\"v2\",\"v1\"])],[])"++        -- Image Step 3: C1 GET and then PUT v3 ~ (A, 1) -> State A (A, 3, [v3, v2])+        -- C1 provides context (A, 1), so v1 is superseded but v2 is not.+        let ctxA1 = mkVersionVector (Map.singleton "A" 1)+            s3 = event s2 (Just ctxA1) "A" "v3"+        show s3 `shouldBe` "([(\"A\",3,[\"v3\",\"v2\"])],[])"+   describe "DVV QuickCheck Properties" $ do     it "sync is idempotent: sync d d == d (semantically)" $       property $ \(d :: DVV ID Value) ->