entity: add embryo of a generic, DAG-enabled entity

3 files changed, 333 insertions, 0 deletions

diff --git a/entity/entity.go b/entity/entity.go
new file mode 100644
index 00000000..c12dc2c4
--- /dev/null
+++ b/entity/entity.go
@@ -0,0 +1,181 @@
+package entity
+
+import (
+	"encoding/json"
+	"fmt"
+	"sort"
+
+	"github.com/pkg/errors"
+
+	"github.com/MichaelMure/git-bug/repository"
+)
+
+type Operation interface {
+	// Id() Id
+	// MarshalJSON() ([]byte, error)
+	Validate() error
+
+	base() *OpBase
+}
+
+type OperationIterator struct {
+}
+
+type Definition struct {
+	namespace            string
+	operationUnmarshaler func(raw json.RawMessage) (Operation, error)
+	formatVersion        uint
+}
+
+type Entity struct {
+	Definition
+
+	ops []Operation
+}
+
+func New(definition Definition) *Entity {
+	return &Entity{
+		Definition: definition,
+	}
+}
+
+func Read(def Definition, repo repository.ClockedRepo, id Id) (*Entity, error) {
+	if err := id.Validate(); err != nil {
+		return nil, errors.Wrap(err, "invalid id")
+	}
+
+	ref := fmt.Sprintf("refs/%s/%s", def.namespace, id.String())
+
+	rootHash, err := repo.ResolveRef(ref)
+	if err != nil {
+		return nil, err
+	}
+
+	// Perform a depth-first search to get a topological order of the DAG where we discover the
+	// parents commit and go back in time up to the chronological root
+
+	stack := make([]repository.Hash, 0, 32)
+	visited := make(map[repository.Hash]struct{})
+	DFSOrder := make([]repository.Commit, 0, 32)
+
+	stack = append(stack, rootHash)
+
+	for len(stack) > 0 {
+		// pop
+		hash := stack[len(stack)-1]
+		stack = stack[:len(stack)-1]
+
+		if _, ok := visited[hash]; ok {
+			continue
+		}
+
+		// mark as visited
+		visited[hash] = struct{}{}
+
+		commit, err := repo.ReadCommit(hash)
+		if err != nil {
+			return nil, err
+		}
+
+		DFSOrder = append(DFSOrder, commit)
+
+		for _, parent := range commit.Parents {
+			stack = append(stack, parent)
+		}
+	}
+
+	// Now, we can reverse this topological order and read the commits in an order where
+	// we are sure to have read all the chronological ancestors when we read a commit.
+
+	// Next step is to:
+	// 1) read the operationPacks
+	// 2) make sure that the clocks causality respect the DAG topology.
+
+	oppMap := make(map[repository.Hash]*operationPack)
+	var opsCount int
+
+	rootCommit := DFSOrder[len(DFSOrder)-1]
+	rootOpp, err := readOperationPack(def, repo, rootCommit.TreeHash)
+	if err != nil {
+		return nil, err
+	}
+	oppMap[rootCommit.Hash] = rootOpp
+
+	for i := len(DFSOrder) - 2; i >= 0; i-- {
+		commit := DFSOrder[i]
+
+		// Verify DAG structure: single chronological root
+		if len(commit.Parents) == 0 {
+			return nil, fmt.Errorf("multiple root in the entity DAG")
+		}
+
+		opp, err := readOperationPack(def, repo, commit.TreeHash)
+		if err != nil {
+			return nil, err
+		}
+
+		// make sure that the lamport clocks causality match the DAG topology
+		for _, parentHash := range commit.Parents {
+			parentPack, ok := oppMap[parentHash]
+			if !ok {
+				panic("DFS failed")
+			}
+
+			if parentPack.EditTime >= opp.EditTime {
+				return nil, fmt.Errorf("lamport clock ordering doesn't match the DAG")
+			}
+
+			// to avoid an attack where clocks are pushed toward the uint64 rollover, make sure
+			// that the clocks don't jump too far in the future
+			if opp.EditTime-parentPack.EditTime > 10_000 {
+				return nil, fmt.Errorf("lamport clock jumping too far in the future, likely an attack")
+			}
+		}
+
+		oppMap[commit.Hash] = opp
+		opsCount += len(opp.Operations)
+	}
+
+	// Now that we know that the topological order and clocks are fine, we order the operationPacks
+	// based on the logical clocks, entirely ignoring the DAG topology
+
+	oppSlice := make([]*operationPack, 0, len(oppMap))
+	for _, pack := range oppMap {
+		oppSlice = append(oppSlice, pack)
+	}
+	sort.Slice(oppSlice, func(i, j int) bool {
+		// TODO: no secondary ordering?
+		return oppSlice[i].EditTime < oppSlice[i].EditTime
+	})
+
+	// Now that we ordered the operationPacks, we have the order of the Operations
+
+	ops := make([]Operation, 0, opsCount)
+	for _, pack := range oppSlice {
+		for _, operation := range pack.Operations {
+			ops = append(ops, operation)
+		}
+	}
+
+	return &Entity{
+		Definition: def,
+		ops:        ops,
+	}, nil
+}
+
+func Remove() error {
+	panic("")
+}
+
+func (e *Entity) Id() {
+
+}
+
+// return the ordered operations
+func (e *Entity) Operations() []Operation {
+	return e.ops
+}
+
+func (e *Entity) Commit() error {
+	panic("")
+}
diff --git a/entity/entity_actions.go b/entity/entity_actions.go
new file mode 100644
index 00000000..02e76487
--- /dev/null
+++ b/entity/entity_actions.go
@@ -0,0 +1,27 @@
+package entity
+
+import (
+	"fmt"
+
+	"github.com/MichaelMure/git-bug/repository"
+)
+
+func ListLocalIds(typename string, repo repository.RepoData) ([]Id, error) {
+	refs, err := repo.ListRefs(fmt.Sprintf("refs/%s/", typename))
+	if err != nil {
+		return nil, err
+	}
+	return RefsToIds(refs), nil
+}
+
+func Fetch() {
+
+}
+
+func Pull() {
+
+}
+
+func Push() {
+
+}
diff --git a/entity/operation_pack.go b/entity/operation_pack.go
new file mode 100644
index 00000000..2377167f
--- /dev/null
+++ b/entity/operation_pack.go
@@ -0,0 +1,125 @@
+package entity
+
+import (
+	"encoding/json"
+	"strconv"
+	"strings"
+
+	"github.com/pkg/errors"
+
+	"github.com/MichaelMure/git-bug/repository"
+	"github.com/MichaelMure/git-bug/util/lamport"
+)
+
+const opsEntryName = "ops"
+const versionEntryPrefix = "version-"
+const createClockEntryPrefix = "create-clock-"
+const editClockEntryPrefix = "edit-clock-"
+
+type operationPack struct {
+	Operations []Operation
+	CreateTime lamport.Time
+	EditTime   lamport.Time
+}
+
+// func (opp *operationPack) MarshalJSON() ([]byte, error) {
+// 	return json.Marshal(struct {
+// 		Operations []Operation `json:"ops"`
+// 	}{
+// 		Operations: opp.Operations,
+// 	})
+// }
+
+func readOperationPack(def Definition, repo repository.RepoData, treeHash repository.Hash) (*operationPack, error) {
+	entries, err := repo.ReadTree(treeHash)
+	if err != nil {
+		return nil, err
+	}
+
+	// check the format version first, fail early instead of trying to read something
+	// var version uint
+	// for _, entry := range entries {
+	// 	if strings.HasPrefix(entry.Name, versionEntryPrefix) {
+	// 		v, err := strconv.ParseUint(strings.TrimPrefix(entry.Name, versionEntryPrefix), 10, 64)
+	// 		if err != nil {
+	// 			return nil, errors.Wrap(err, "can't read format version")
+	// 		}
+	// 		if v > 1<<12 {
+	// 			return nil, fmt.Errorf("format version too big")
+	// 		}
+	// 		version = uint(v)
+	// 		break
+	// 	}
+	// }
+	// if version == 0 {
+	// 	return nil, NewErrUnknowFormat(def.formatVersion)
+	// }
+	// if version != def.formatVersion {
+	// 	return nil, NewErrInvalidFormat(version, def.formatVersion)
+	// }
+
+	var ops []Operation
+	var createTime lamport.Time
+	var editTime lamport.Time
+
+	for _, entry := range entries {
+		if entry.Name == opsEntryName {
+			data, err := repo.ReadData(entry.Hash)
+			if err != nil {
+				return nil, errors.Wrap(err, "failed to read git blob data")
+			}
+
+			ops, err = unmarshallOperations(def, data)
+			if err != nil {
+				return nil, err
+			}
+			break
+		}
+
+		if strings.HasPrefix(entry.Name, createClockEntryPrefix) {
+			v, err := strconv.ParseUint(strings.TrimPrefix(entry.Name, createClockEntryPrefix), 10, 64)
+			if err != nil {
+				return nil, errors.Wrap(err, "can't read creation lamport time")
+			}
+			createTime = lamport.Time(v)
+		}
+
+		if strings.HasPrefix(entry.Name, editClockEntryPrefix) {
+			v, err := strconv.ParseUint(strings.TrimPrefix(entry.Name, editClockEntryPrefix), 10, 64)
+			if err != nil {
+				return nil, errors.Wrap(err, "can't read edit lamport time")
+			}
+			editTime = lamport.Time(v)
+		}
+	}
+
+	return &operationPack{
+		Operations: ops,
+		CreateTime: createTime,
+		EditTime:   editTime,
+	}, nil
+}
+
+func unmarshallOperations(def Definition, data []byte) ([]Operation, error) {
+	aux := struct {
+		Operations []json.RawMessage `json:"ops"`
+	}{}
+
+	if err := json.Unmarshal(data, &aux); err != nil {
+		return nil, err
+	}
+
+	ops := make([]Operation, 0, len(aux.Operations))
+
+	for _, raw := range aux.Operations {
+		// delegate to specialized unmarshal function
+		op, err := def.operationUnmarshaler(raw)
+		if err != nil {
+			return nil, err
+		}
+
+		ops = append(ops, op)
+	}
+
+	return ops, nil
+}