1package entity
2
3import (
4 "encoding/json"
5 "fmt"
6 "sort"
7
8 "github.com/pkg/errors"
9
10 "github.com/MichaelMure/git-bug/repository"
11)
12
13type Operation interface {
14 // Id() Id
15 // MarshalJSON() ([]byte, error)
16 Validate() error
17
18 base() *OpBase
19}
20
21type OperationIterator struct {
22}
23
24type Definition struct {
25 namespace string
26 operationUnmarshaler func(raw json.RawMessage) (Operation, error)
27 formatVersion uint
28}
29
30type Entity struct {
31 Definition
32
33 ops []Operation
34}
35
36func New(definition Definition) *Entity {
37 return &Entity{
38 Definition: definition,
39 }
40}
41
42func Read(def Definition, repo repository.ClockedRepo, id Id) (*Entity, error) {
43 if err := id.Validate(); err != nil {
44 return nil, errors.Wrap(err, "invalid id")
45 }
46
47 ref := fmt.Sprintf("refs/%s/%s", def.namespace, id.String())
48
49 rootHash, err := repo.ResolveRef(ref)
50 if err != nil {
51 return nil, err
52 }
53
54 // Perform a depth-first search to get a topological order of the DAG where we discover the
55 // parents commit and go back in time up to the chronological root
56
57 stack := make([]repository.Hash, 0, 32)
58 visited := make(map[repository.Hash]struct{})
59 DFSOrder := make([]repository.Commit, 0, 32)
60
61 stack = append(stack, rootHash)
62
63 for len(stack) > 0 {
64 // pop
65 hash := stack[len(stack)-1]
66 stack = stack[:len(stack)-1]
67
68 if _, ok := visited[hash]; ok {
69 continue
70 }
71
72 // mark as visited
73 visited[hash] = struct{}{}
74
75 commit, err := repo.ReadCommit(hash)
76 if err != nil {
77 return nil, err
78 }
79
80 DFSOrder = append(DFSOrder, commit)
81
82 for _, parent := range commit.Parents {
83 stack = append(stack, parent)
84 }
85 }
86
87 // Now, we can reverse this topological order and read the commits in an order where
88 // we are sure to have read all the chronological ancestors when we read a commit.
89
90 // Next step is to:
91 // 1) read the operationPacks
92 // 2) make sure that the clocks causality respect the DAG topology.
93
94 oppMap := make(map[repository.Hash]*operationPack)
95 var opsCount int
96
97 rootCommit := DFSOrder[len(DFSOrder)-1]
98 rootOpp, err := readOperationPack(def, repo, rootCommit.TreeHash)
99 if err != nil {
100 return nil, err
101 }
102 oppMap[rootCommit.Hash] = rootOpp
103
104 for i := len(DFSOrder) - 2; i >= 0; i-- {
105 commit := DFSOrder[i]
106
107 // Verify DAG structure: single chronological root
108 if len(commit.Parents) == 0 {
109 return nil, fmt.Errorf("multiple root in the entity DAG")
110 }
111
112 opp, err := readOperationPack(def, repo, commit.TreeHash)
113 if err != nil {
114 return nil, err
115 }
116
117 // make sure that the lamport clocks causality match the DAG topology
118 for _, parentHash := range commit.Parents {
119 parentPack, ok := oppMap[parentHash]
120 if !ok {
121 panic("DFS failed")
122 }
123
124 if parentPack.EditTime >= opp.EditTime {
125 return nil, fmt.Errorf("lamport clock ordering doesn't match the DAG")
126 }
127
128 // to avoid an attack where clocks are pushed toward the uint64 rollover, make sure
129 // that the clocks don't jump too far in the future
130 if opp.EditTime-parentPack.EditTime > 10_000 {
131 return nil, fmt.Errorf("lamport clock jumping too far in the future, likely an attack")
132 }
133 }
134
135 oppMap[commit.Hash] = opp
136 opsCount += len(opp.Operations)
137 }
138
139 // Now that we know that the topological order and clocks are fine, we order the operationPacks
140 // based on the logical clocks, entirely ignoring the DAG topology
141
142 oppSlice := make([]*operationPack, 0, len(oppMap))
143 for _, pack := range oppMap {
144 oppSlice = append(oppSlice, pack)
145 }
146 sort.Slice(oppSlice, func(i, j int) bool {
147 // TODO: no secondary ordering?
148 return oppSlice[i].EditTime < oppSlice[i].EditTime
149 })
150
151 // Now that we ordered the operationPacks, we have the order of the Operations
152
153 ops := make([]Operation, 0, opsCount)
154 for _, pack := range oppSlice {
155 for _, operation := range pack.Operations {
156 ops = append(ops, operation)
157 }
158 }
159
160 return &Entity{
161 Definition: def,
162 ops: ops,
163 }, nil
164}
165
166func Remove() error {
167 panic("")
168}
169
170func (e *Entity) Id() {
171
172}
173
174// return the ordered operations
175func (e *Entity) Operations() []Operation {
176 return e.ops
177}
178
179func (e *Entity) Commit() error {
180 panic("")
181}