Crdt.Node

crdt · API reference

CRDT node types

CRDT node types.

This module defines all 7 CRDT node types from json-joy:

con: constant/immutable value
val: mutable reference (LWW register)
obj: mutable string-keyed map (LWW-Map)
vec: mutable indexed tuple (fixed slots)
arr: mutable ordered list (RGA)
str: mutable text string (RGA)
bin: mutable binary data (RGA) Each node has a unique ID (timestamp) assigned when it is created.

Node Type Enumeration

type node_type = 
  | Con (* Constant/immutable value *)
  | Val (* Mutable reference (LWW register) *)
  | Obj (* Mutable string-keyed map *)
  | Vec (* Mutable indexed tuple *)
  | Arr (* Mutable ordered list (RGA) *)
  | Str (* Mutable text string (RGA) *)
  | Bin (* Mutable binary data (RGA) *)

Node types as an enumeration

val type_name : node_type -> string

Get the node type name

RGA Chunk (re-export from Rga module)

type 'a rga_chunk = 'a Rga.chunk

A chunk in an RGA - contiguous elements with sequential IDs. For str: each ID represents one UTF-16 code unit. For bin: each ID represents one byte. For arr: each ID represents one element reference.

Node Data Structures

type con_node = {
  con_id : Clock.timestamp;
  con_value : Value.t; (* The immutable value or Timestamp_ref *)
}

Constant node - holds an immutable value. The value can be a primitive (null, bool, number, string) or a reference to another node (timestamp).

type val_node = {
  val_id : Clock.timestamp;
  mutable val_ref : Clock.timestamp option; (* Reference to the current value node *)
}

Value node - LWW register holding a reference to another node. Initially the value is None (not set).

type obj_entry = {
  obj_key : string;
  obj_value : Clock.timestamp; (* Reference to value node *)
  obj_write_ts : Clock.timestamp; (* When this key was written (for LWW) *)
}

Object node - LWW-Map of string keys to node references. Each key maps to a (timestamp, value) pair where timestamp is when the key was last written.

type obj_node = {
  obj_id : Clock.timestamp;
  obj_entries : (string, obj_entry) Hashtbl.t; (* Key-value pairs *)
}

type vec_slot = {
  vec_idx : int; (* Slot index 0-255 *)
  vec_value : Clock.timestamp; (* Reference to value node *)
  vec_write_ts : Clock.timestamp; (* When this slot was written *)
}

Vector node - fixed-size tuple with up to 256 slots. Each slot is a LWW register.

type vec_node = {
  vec_id : Clock.timestamp;
  mutable vec_slots : vec_slot list; (* Slots that have been set *)
}

type arr_chunk = Clock.timestamp list

type arr_node = {
  arr_id : Clock.timestamp;
  arr_rga : arr_chunk Rga.t; (* RGA chunks of node references *)
}

Array node - RGA of node references

type str_node = {
  str_id : Clock.timestamp;
  str_rga : str_chunk Rga.t; (* RGA of UTF-16 text slices *)
  mutable str_view_cache : string option;
}

String node - RGA of UTF-16 text

and str_chunk = {
  str_buffer : string;
  str_offset : int;
  str_length : int;
  str_utf16_length : int;
}

type bin_chunk = {
  buffer : bytes;
  offset : int;
  length : int;
}

type bin_node = {
  bin_id : Clock.timestamp;
  bin_rga : bin_chunk Rga.t; (* RGA of byte slices *)
  mutable bin_view_cache : bytes option;
}

Binary node - RGA of bytes

Node Sum Type

type t = 
  | Node_con of con_node
  | Node_val of val_node
  | Node_obj of obj_node
  | Node_vec of vec_node
  | Node_arr of arr_node
  | Node_str of str_node
  | Node_bin of bin_node

A CRDT node - one of the 7 types

Node Properties

val id : t -> Clock.timestamp

Get the ID of a node

val node_type : t -> node_type

Get the type of a node

val name : t -> string

Get the type name of a node

Node Constructors

val make_con : id:Clock.timestamp -> value:Value.t -> t

Create a constant node

val make_val : id:Clock.timestamp -> t

Create a value node (initially empty)

val make_obj : id:Clock.timestamp -> t

Create an object node (initially empty)

val ordered_obj_entries : ('a, obj_entry) Hashtbl.t -> obj_entry list

val obj_entries : t -> obj_entry list

val find_obj_key : t -> string -> obj_entry option

val make_vec : id:Clock.timestamp -> t

Create a vector node (initially empty)

val make_arr : id:Clock.timestamp -> t

Create an array node (initially empty)

val arr_chunks : t -> Clock.timestamp Rga.chunk list

val arr_values : t -> Clock.timestamp list

val arr_last_id : t -> Clock.timestamp option

val arr_find_position : t -> int -> Clock.timestamp option

val arr_find_spans : t -> pos:int -> len:int -> Clock.timespan list

val arr_length : t -> int

val make_str : id:Clock.timestamp -> t

Create a string node (initially empty)

val make_bin : id:Clock.timestamp -> t

Create a binary node (initially empty)

val str_chunk_of_string : string -> str_chunk

val materialize_str_chunk : str_chunk -> string

val split_str_chunk : 
  str_chunk ->
  byte_offset:int ->
  utf16_offset:int ->
  str_chunk * str_chunk

val str_chunk_span : str_chunk -> int

val utf16_offset_to_str_chunk_byte : str_chunk -> int -> int

val split_str_chunk_utf16 : str_chunk -> int -> str_chunk * str_chunk

val str_chunks : t -> string Rga.chunk list

val str_last_id : t -> Clock.timestamp option

val str_find_position : t -> int -> Clock.timestamp option

val str_find_spans : t -> pos:int -> len:int -> Clock.timespan list

val str_length : t -> int

val bin_chunk_of_bytes : bytes -> bin_chunk

val empty_bin_chunk : bin_chunk

val materialize_bin_chunk : bin_chunk -> bytes

val split_bin_chunk : bin_chunk -> int -> bin_chunk * bin_chunk

val bin_chunk_span : bin_chunk -> int

val make_str_with_rga : id:Clock.timestamp -> string Rga.t -> t

val make_bin_with_rga : id:Clock.timestamp -> bytes Rga.t -> t

val bin_chunks : t -> bytes Rga.chunk list

val bin_last_id : t -> Clock.timestamp option

val bin_find_position : t -> int -> Clock.timestamp option

val bin_find_spans : t -> pos:int -> len:int -> Clock.timespan list

val bin_length : t -> int

val string_view : t -> string

val bytes_view : t -> bytes

View Functions

val view : t -> Value.t

Get the view (current state as Value.t) of a node. Note: For nodes with references (val, obj, vec, arr), this returns a partial view. Use Model.view for the full resolved view.

Mutation Operations

val set_val : t -> value:Clock.timestamp -> unit

Set the reference in a value node

val set_obj_key : 
  t ->
  key:string ->
  value:Clock.timestamp ->
  write_ts:Clock.timestamp ->
  unit

Set a key in an object node (LWW semantics)

val set_vec_slot : 
  t ->
  idx:int ->
  value:Clock.timestamp ->
  write_ts:Clock.timestamp ->
  unit

Set a slot in a vector node (LWW semantics)

RGA Operations

val insert_str : 
  t ->
  after:Clock.timestamp option ->
  chunk_id:Clock.timestamp ->
  text:string ->
  unit

Insert text into a string node after a given position.

parameter after The timestamp to insert after (None for head) parameter chunk_id The timestamp for this insert operation parameter text The text to insert

val insert_bin : 
  t ->
  after:Clock.timestamp option ->
  chunk_id:Clock.timestamp ->
  data:bytes ->
  unit

Insert bytes into a binary node.

parameter after The timestamp to insert after (None for head) parameter chunk_id The timestamp for this insert operation parameter data The bytes to insert

val insert_arr : 
  t ->
  after:Clock.timestamp option ->
  chunk_id:Clock.timestamp ->
  value:Clock.timestamp ->
  unit

Insert element into an array node.

parameter after The timestamp to insert after (None for head) parameter chunk_id The timestamp for this insert operation parameter value The element reference to insert

val insert_arr_values : 
  t ->
  after:Clock.timestamp option ->
  chunk_id:Clock.timestamp ->
  values:arr_chunk ->
  unit

val seq_contains : t -> Clock.timestamp -> bool

Whether a sequence node already contains the element ts (visible or tombstoned). Used to make op re-delivery idempotent: an RGA insert whose first element is present was already applied.

val delete_range : t -> spans:Clock.timespan list -> unit

Delete a range in an RGA node by marking elements as deleted (tombstones).

parameter spans List of timespans to delete

Pretty Printing

val pp : Format.formatter -> t -> unit

Pretty print a node

val to_string : t -> string

Convert node to string for debugging