1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
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("")
}
|
