Branching and naïve merge strategies

* AGPL license

* branching and merging

* Delete LICENSE in favor of separate PR

Signed-off-by: Marcos Magueta <maguetamarcos@gmail.com>

* add unmonitored tests and docs

---------

Signed-off-by: Marcos Magueta <maguetamarcos@gmail.com>

5 files changed, 240 insertions, 11 deletions

diff --git a/docs/dcl.org b/docs/dcl.org
new file mode 100644
index 0000000..92fc19d
--- /dev/null
+++ b/docs/dcl.org
@@ -0,0 +1,105 @@
+#+TITLE: DCL — Database Control Language
+
+DCL manages branches: named pointers to database states. It provides
+Git-like operations built on Sakura's append-only, content-addressed
+storage. Every mutation automatically advances the current branch tip,
+so you never need to track hashes manually.
+
+* Syntax reference
+
+| Command                                    | Effect                               |
+|--------------------------------------------+--------------------------------------|
+| ~(CreateBranch (name N))~                  | Create branch N at current state     |
+| ~(CreateBranch (name N) (hash H))~         | Create branch N at a specific hash   |
+| ~(Checkout N)~                             | Switch to branch N, restore its db   |
+| ~(GetHead)~                                | Print the current HEAD branch name   |
+| ~(GetBranchTip N)~                         | Print the stored hash of branch N    |
+| ~(UpdateBranchTip (name N) (hash H))~      | Manually advance branch N to hash H  |
+| ~(Merge (left L) (right R) (strategy S))~  | 3-way merge branch R into L          |
+
+Branch state is always queryable as relations:
+
+#+begin_src sexp
+(Base sakura:branch)   ; name × hash for every branch
+(Base sakura:head)     ; single-tuple: current branch name
+#+end_src
+
+Merge strategies:
+
+| Strategy           | Behaviour on conflict                        |
+|--------------------+----------------------------------------------|
+| ~PreferLeft~       | Keep the left branch's version               |
+| ~PreferRight~      | Keep the right branch's version              |
+| ~RevertToAncestor~ | Revert conflicting relation to the LCA state |
+
+* Example: travelling through history
+
+#+begin_src sexp
+(CreateRelation (name "scores") (schema ((player "string") (pts "integer"))))
+
+(CreateBranch (name "v0"))
+
+(InsertTuple (relation "scores") (attributes ((player (Str "Alice")) (pts (Int 10)))))
+
+(CreateBranch (name "v1"))
+
+(InsertTuple (relation "scores") (attributes ((player (Str "Bob")) (pts (Int 25)))))
+
+(CreateBranch (name "v2"))
+#+end_src
+
+Now jump around and watch the relation change:
+
+#+begin_src sexp
+(Checkout "v0")
+(Base scores)
+; (0 rows)
+
+(Checkout "v1")
+(Base scores)
+; ┌────────┬─────┐
+; │ player │ pts │
+; ├────────┼─────┤
+; │ Alice  │  10 │
+; └────────┴─────┘
+
+(Checkout "v2")
+(Base scores)
+; ┌────────┬─────┐
+; │ player │ pts │
+; ├────────┼─────┤
+; │ Alice  │  10 │
+; │ Bob    │  25 │
+; └────────┴─────┘
+#+end_src
+
+* Example: diverge and merge
+
+#+begin_src sexp
+(Checkout "master")
+(CreateBranch (name "feature"))
+
+(Checkout "master")
+(InsertTuple (relation "users") (attributes ((id (Int 1)) (name (Str "Alice")))))
+
+(Checkout "feature")
+(InsertTuple (relation "users") (attributes ((id (Int 2)) (name (Str "Bob")))))
+
+(Merge (left "master") (right "feature") (strategy PreferLeft))
+
+(Checkout "master")
+(Base users)
+; ┌────┬───────┐
+; │ id │ name  │
+; ├────┼───────┤
+; │  1 │ Alice │
+; │  2 │ Bob   │
+; └────┴───────┘
+#+end_src
+
+* See also
+
+- ~lib/dcl/~ — AST, parser, executor
+- ~lib/management/branch.ml~ — branch registry and ephemeral relations
+- ~lib/management/merge.ml~ — 3-way merge engine
+- ~lib/management/diff.ml~ — relation diff used internally by merge
diff --git a/docs/dcl-quantification.org b/docs/icl-quantification.org
index 81e9cad..7a81551 100644
--- a/docs/dcl-quantification.org
+++ b/docs/icl-quantification.org
@@ -1,8 +1,8 @@
-#+TITLE: DCL Quantification: Runtime Model and Evaluation
+#+TITLE: ICL Quantification: Runtime Model and Evaluation
 
 * Overview
 
-This document describes precisely how DCL constraints are represented, compiled,
+This document describes precisely how ICL constraints are represented, compiled,
 and evaluated at runtime. It covers the full stack from the s-expression syntax
 through AST compilation, context construction, and recursive evaluation — with
 particular attention to the cost model of quantifiers, which is the primary target
diff --git a/docs/icl.org b/docs/icl.org
new file mode 100644
index 0000000..c2258bf
--- /dev/null
+++ b/docs/icl.org
@@ -0,0 +1,108 @@
+#+TITLE: ICL — Integrity Control Language
+
+ICL registers integrity constraints on relations. A constraint is a
+membership check: before any tuple is inserted, Sakura verifies that
+the tuple belongs to every constraint-relation attached to the target
+relation.
+
+Constraints are expressed as S-expressions and sent over the wire like
+any other command.
+
+* Syntax
+
+#+begin_src
+(RegisterConstraint
+  (constraint_name "<name>")
+  (relation_name   "<target-relation>")
+  (body            <constraint-body>))
+#+end_src
+
+A ~<constraint-body>~ is one of:
+
+| Form                                            | Meaning                        |
+|-------------------------------------------------+--------------------------------|
+| ~(MemberOf (target R) (binding (...)))~         | Tuple must be in relation R    |
+| ~(Not (body B) (universe R))~                   | Negation (closed-world over R) |
+| ~(And (B1 B2 ...))~                             | All must hold                  |
+| ~(Or  (B1 B2 ...))~                             | At least one must hold         |
+| ~(Exists (variable v) (quantifier R) (body B))~ | ∃ v ∈ R such that B holds      |
+| ~(Forall (variable v) (quantifier R) (body B))~ | ∀ v ∈ R, B holds               |
+
+Bindings map target-relation attribute names to values drawn from the
+tuple being checked:
+
+| Binding expr        | Meaning                        |
+|---------------------+--------------------------------|
+| ~(Var "attr")~      | Value of ~attr~ from the tuple |
+| ~(Const (Int N))~   | Literal integer N              |
+| ~(Const (Str "s"))~ | Literal string s               |
+| ~(Const (Float f))~ | Literal float f                |
+
+* Examples
+
+** Foreign key
+
+#+begin_src sexp
+(CreateRelation (name "Department") (schema ((dept_id "integer") (dept_name "string"))))
+(CreateRelation (name "Employee")   (schema ((emp_id "integer") (emp_name "string") (dept_id "integer"))))
+
+(RegisterConstraint
+  (constraint_name "fk_employee_dept")
+  (relation_name   "Employee")
+  (body (MemberOf
+    (target "Department")
+    (binding ((dept_id (Var "dept_id")))))))
+#+end_src
+
+** Range check
+
+#+begin_src sexp
+(CreateRelation (name "Result") (schema ((student_id "integer") (score "integer"))))
+
+(RegisterConstraint
+  (constraint_name "score_range")
+  (relation_name   "Result")
+  (body (And
+    ((MemberOf (target "greater_than_or_equal_natural")
+               (binding ((left (Var "score")) (right (Const (Int 0))))))
+     (MemberOf (target "less_than_or_equal_natural")
+               (binding ((left (Var "score")) (right (Const (Int 100))))))))))
+#+end_src
+
+** Existential (FK through a join)
+
+A ~Suite~ is only valid if its room belongs to a building with more
+than 3 floors:
+
+#+begin_src sexp
+(CreateRelation (name "Building") (schema ((building_id "integer") (building_name "string") (floors "integer"))))
+(CreateRelation (name "Room")     (schema ((room_id "integer") (building_id "integer") (floor "integer"))))
+(CreateRelation (name "Suite")    (schema ((suite_id "integer") (room_id "integer") (suite_name "string"))))
+
+(RegisterConstraint
+  (constraint_name "suite_in_tall_building")
+  (relation_name   "Suite")
+  (body
+    (Exists (variable "r") (quantifier "Room")
+      (body
+        (Exists (variable "b") (quantifier "Building")
+          (body
+            (And
+              ((MemberOf (target "Room")
+                         (binding ((room_id (Var "room_id")))))
+               (MemberOf (target "Building")
+                         (binding ((building_id (Var "r.building_id")))))
+               (MemberOf (target "greater_than_natural")
+                         (binding ((left (Var "b.floors"))
+                                   (right (Const (Int 3))))))))))))))
+#+end_src
+
+Note: quantifier variables are namespaced — attributes from variable
+~r~ are accessed as ~r.attr_name~ inside nested scopes.
+
+* See also
+
+- ~lib/icl/~ — AST, parser, executor
+- ~lib/constraint.ml~ — runtime constraint representation and evaluator
+- ~docs/icl-quantification.org~ — full runtime model for ~Exists~/~Forall~
+- ~docs/constraints.org~ — conceptual background
diff --git a/docs/karuta-integration.org b/docs/karuta-integration.org
index a144a25..0642254 100644
--- a/docs/karuta-integration.org
+++ b/docs/karuta-integration.org
@@ -14,10 +14,26 @@ Here's an overview of the sublanguages and how they are manifested in Karuta:
 - Pure querying, total/terminating subset;
 - No user recursion with no self references.
 
-** DCL (Data Constraint Language)
+** ICL (Integrity Control Language)
 
 - Integrity rules (key, FK-like, checks, assertions, aggregates-for-integrity).
 - Semantically predicates, but with enforcement timing (on write/commit), not free query operators.
+- Implemented in =lib/icl/= (=Ast=, =Parser=, =Executor=).
+
+** DCL (Database Control Language)
+
+- Branch management: create/checkout branches, query HEAD and tip hashes.
+- Merge: 3-way merge of two branch tips with configurable conflict strategy (=PreferLeft=, =PreferRight=, =RevertToAncestor=).
+- Implemented in =lib/dcl/= (=Ast=, =Parser=, =Executor=).
+- Example commands:
+  #+begin_src sexp
+  (CreateBranch (name "feature") (tip "<hash>"))
+  (Checkout "feature")
+  (GetHead)
+  (GetBranchTip "main")
+  (UpdateBranchTip (name "main") (tip "<hash>"))
+  (Merge (left "main") (right "feature") (strategy PreferLeft))
+  #+end_src
 
 ** DML (Data Manipulation Language)
 
@@ -35,7 +51,7 @@ Here's an overview of the sublanguages and how they are manifested in Karuta:
 ** PPL (Procedural Predicate Language)
 
 - Stored procedures/functions, recursion allowed, orchestration logic.
-- Can call DRL/DML/DCL-aware operations, but not all PPL predicates are DRL-safe.
+- Can call DRL/DML/ICL/DCL-aware operations, but not all PPL predicates are DRL-safe.
   
 ** ACL (Authorization/Policy Language) (optional early, important later)
 
@@ -62,21 +78,21 @@ Here's an overview of the sublanguages and how they are manifested in Karuta:
       person[string, natural] :: sakura:persisted
       person[Name, Age] :- valid_age[Age].
 
-      % DCL
+      % ICL
       another-constraint[list[person], string, natural] :: sakura:constraint
       another-constraint[[], _, _].
       another-constraint[[person[Name, Age]|Rest], Whatever1, Whatever2] :-
         (eq[Name, Whatever1] ; !eq[Name, Whatever1], !eq[Age, Whatever2]),
         another-constraint[Rest, Whatever1, Whatever2].
 
-      % DCL
+      % ICL
       my-predicate[int, string, nat] :: sakura:constraint
       my-predicate[Arg1, Arg2, Arg3] :- 
         another-module:my-predicate[Arg1, Arg2, Arg3],
         on[insert, update],
         timing[immediate].
 
-      % DCL
+      % ICL
       valid_age/1 :: sakura:constraint
       valid_age[Age] with [karuta, sakura] :-
         nat[Age],
diff --git a/docs/n-way-binding.org b/docs/n-way-binding.org
index 39c9d65..85dc0e3 100644
--- a/docs/n-way-binding.org
+++ b/docs/n-way-binding.org
@@ -1,9 +1,9 @@
-#+TITLE: N-Way Binding in DCL Constraints
+#+TITLE: N-Way Binding in ICL Constraints
 #+DATE: 2026-03-11
 
 * Overview
 
-The DCL constraint language supports quantified membership checks via ~Exists~ and ~Forall~.
+The ICL constraint language supports quantified membership checks via ~Exists~ and ~Forall~.
 This document illustrates the hotel/building/room/suite example to motivate n-ary quantification
 and show how 3-wise (and deeper) relational composition is expressed.
 
@@ -72,7 +72,7 @@ to fire when suites referencing its rooms are inserted.
      ((suite_id (Int 1003)) (room_id (Int 102)) (suite_name (Str "Deluxe"))       (capacity (Int 3))))))
 #+end_src
 
-* DCL — Constraints
+* ICL — Constraints
 
 Binary FK constraints compose to enforce referential integrity along the chain
 ~Suite → Room → Building~. Each link is declared independently.
@@ -202,5 +202,5 @@ bound to variable ~x~.
 
 Without namespacing, ~extend_tuple~ would overwrite the incoming tuple's attributes
 with same-named attributes from the quantifier row, silently making ~Var~ resolve to
-the wrong scope. See ~lib/constraint.ml~ and ~docs/dcl-quantification.org~ for a full
+the wrong scope. See ~lib/constraint.ml~ and ~docs/icl-quantification.org~ for a full
 account of this failure mode and the provenance TODO.