1package bug
2
3import (
4 "errors"
5 "fmt"
6 "strings"
7
8 "github.com/MichaelMure/git-bug/repository"
9 "github.com/MichaelMure/git-bug/util"
10)
11
12const bugsRefPattern = "refs/bugs/"
13const bugsRemoteRefPattern = "refs/remotes/%s/bugs/"
14
15const opsEntryName = "ops"
16const rootEntryName = "root"
17const mediaEntryName = "media"
18
19const createClockEntryPrefix = "create-clock-"
20const createClockEntryPattern = "create-clock-%d"
21const editClockEntryPrefix = "edit-clock-"
22const editClockEntryPattern = "edit-clock-%d"
23
24const idLength = 40
25const humanIdLength = 7
26
27// Bug hold the data of a bug thread, organized in a way close to
28// how it will be persisted inside Git. This is the data structure
29// used for merge of two different version.
30type Bug struct {
31
32 // A Lamport clock is a logical clock that allow to order event
33 // inside a distributed system.
34 // It must be the first field in this struct due to https://github.com/golang/go/issues/599
35 createTime util.LamportTime
36 editTime util.LamportTime
37
38 // Id used as unique identifier
39 id string
40
41 lastCommit util.Hash
42 rootPack util.Hash
43
44 // all the commited operations
45 packs []OperationPack
46
47 // a temporary pack of operations used for convenience to pile up new operations
48 // before a commit
49 staging OperationPack
50}
51
52// Create a new Bug
53func NewBug() *Bug {
54 // No id yet
55 // No logical clock yet
56 return &Bug{}
57}
58
59// Find an existing Bug matching a prefix
60func FindLocalBug(repo repository.Repo, prefix string) (*Bug, error) {
61 ids, err := repo.ListIds(bugsRefPattern)
62
63 if err != nil {
64 return nil, err
65 }
66
67 // preallocate but empty
68 matching := make([]string, 0, 5)
69
70 for _, id := range ids {
71 if strings.HasPrefix(id, prefix) {
72 matching = append(matching, id)
73 }
74 }
75
76 if len(matching) == 0 {
77 return nil, errors.New("No matching bug found.")
78 }
79
80 if len(matching) > 1 {
81 return nil, fmt.Errorf("Multiple matching bug found:\n%s", strings.Join(matching, "\n"))
82 }
83
84 return ReadLocalBug(repo, matching[0])
85}
86
87func ReadLocalBug(repo repository.Repo, id string) (*Bug, error) {
88 ref := bugsRefPattern + id
89 return readBug(repo, ref)
90}
91
92func ReadRemoteBug(repo repository.Repo, remote string, id string) (*Bug, error) {
93 ref := fmt.Sprintf(bugsRemoteRefPattern, remote) + id
94 return readBug(repo, ref)
95}
96
97// Read and parse a Bug from git
98func readBug(repo repository.Repo, ref string) (*Bug, error) {
99 hashes, err := repo.ListCommits(ref)
100
101 if err != nil {
102 return nil, err
103 }
104
105 refSplitted := strings.Split(ref, "/")
106 id := refSplitted[len(refSplitted)-1]
107
108 if len(id) != idLength {
109 return nil, fmt.Errorf("Invalid ref length")
110 }
111
112 bug := Bug{
113 id: id,
114 }
115
116 // Load each OperationPack
117 for _, hash := range hashes {
118 entries, err := repo.ListEntries(hash)
119
120 bug.lastCommit = hash
121
122 if err != nil {
123 return nil, err
124 }
125
126 var opsEntry repository.TreeEntry
127 opsFound := false
128 var rootEntry repository.TreeEntry
129 rootFound := false
130 var createTime uint64
131 var editTime uint64
132
133 for _, entry := range entries {
134 if entry.Name == opsEntryName {
135 opsEntry = entry
136 opsFound = true
137 continue
138 }
139 if entry.Name == rootEntryName {
140 rootEntry = entry
141 rootFound = true
142 }
143 if strings.HasPrefix(entry.Name, createClockEntryPrefix) {
144 n, err := fmt.Sscanf(string(entry.Name), createClockEntryPattern, &createTime)
145 if err != nil {
146 return nil, err
147 }
148 if n != 1 {
149 return nil, fmt.Errorf("could not parse create time lamport value")
150 }
151 }
152 if strings.HasPrefix(entry.Name, editClockEntryPrefix) {
153 n, err := fmt.Sscanf(string(entry.Name), editClockEntryPattern, &editTime)
154 if err != nil {
155 return nil, err
156 }
157 if n != 1 {
158 return nil, fmt.Errorf("could not parse edit time lamport value")
159 }
160 }
161 }
162
163 if !opsFound {
164 return nil, errors.New("Invalid tree, missing the ops entry")
165 }
166 if !rootFound {
167 return nil, errors.New("Invalid tree, missing the root entry")
168 }
169
170 if bug.rootPack == "" {
171 bug.rootPack = rootEntry.Hash
172 bug.createTime = util.LamportTime(createTime)
173 }
174
175 bug.editTime = util.LamportTime(editTime)
176
177 // Update the clocks
178 if err := repo.CreateWitness(bug.createTime); err != nil {
179 return nil, err
180 }
181 if err := repo.EditWitness(bug.editTime); err != nil {
182 return nil, err
183 }
184
185 data, err := repo.ReadData(opsEntry.Hash)
186
187 if err != nil {
188 return nil, err
189 }
190
191 op, err := ParseOperationPack(data)
192
193 if err != nil {
194 return nil, err
195 }
196
197 // tag the pack with the commit hash
198 op.commitHash = hash
199
200 if err != nil {
201 return nil, err
202 }
203
204 bug.packs = append(bug.packs, *op)
205 }
206
207 return &bug, nil
208}
209
210type StreamedBug struct {
211 Bug *Bug
212 Err error
213}
214
215// Read and parse all local bugs
216func ReadAllLocalBugs(repo repository.Repo) <-chan StreamedBug {
217 return readAllBugs(repo, bugsRefPattern)
218}
219
220// Read and parse all remote bugs for a given remote
221func ReadAllRemoteBugs(repo repository.Repo, remote string) <-chan StreamedBug {
222 refPrefix := fmt.Sprintf(bugsRemoteRefPattern, remote)
223 return readAllBugs(repo, refPrefix)
224}
225
226// Read and parse all available bug with a given ref prefix
227func readAllBugs(repo repository.Repo, refPrefix string) <-chan StreamedBug {
228 out := make(chan StreamedBug)
229
230 go func() {
231 defer close(out)
232
233 refs, err := repo.ListRefs(refPrefix)
234 if err != nil {
235 out <- StreamedBug{Err: err}
236 return
237 }
238
239 for _, ref := range refs {
240 b, err := readBug(repo, ref)
241
242 if err != nil {
243 out <- StreamedBug{Err: err}
244 return
245 }
246
247 out <- StreamedBug{Bug: b}
248 }
249 }()
250
251 return out
252}
253
254// List all the available local bug ids
255func ListLocalIds(repo repository.Repo) ([]string, error) {
256 return repo.ListIds(bugsRefPattern)
257}
258
259// IsValid check if the Bug data is valid
260func (bug *Bug) IsValid() bool {
261 // non-empty
262 if len(bug.packs) == 0 && bug.staging.IsEmpty() {
263 return false
264 }
265
266 // check if each pack is valid
267 for _, pack := range bug.packs {
268 if !pack.IsValid() {
269 return false
270 }
271 }
272
273 // check if staging is valid if needed
274 if !bug.staging.IsEmpty() {
275 if !bug.staging.IsValid() {
276 return false
277 }
278 }
279
280 // The very first Op should be a CreateOp
281 firstOp := bug.firstOp()
282 if firstOp == nil || firstOp.OpType() != CreateOp {
283 return false
284 }
285
286 // Check that there is no more CreateOp op
287 it := NewOperationIterator(bug)
288 createCount := 0
289 for it.Next() {
290 if it.Value().OpType() == CreateOp {
291 createCount++
292 }
293 }
294
295 if createCount != 1 {
296 return false
297 }
298
299 return true
300}
301
302// Append an operation into the staging area, to be commited later
303func (bug *Bug) Append(op Operation) {
304 bug.staging.Append(op)
305}
306
307// Write the staging area in Git and move the operations to the packs
308func (bug *Bug) Commit(repo repository.Repo) error {
309 if bug.staging.IsEmpty() {
310 return fmt.Errorf("can't commit a bug with no pending operation")
311 }
312
313 // Write the Ops as a Git blob containing the serialized array
314 hash, err := bug.staging.Write(repo)
315 if err != nil {
316 return err
317 }
318
319 if bug.rootPack == "" {
320 bug.rootPack = hash
321 }
322
323 // Make a Git tree referencing this blob
324 tree := []repository.TreeEntry{
325 // the last pack of ops
326 {ObjectType: repository.Blob, Hash: hash, Name: opsEntryName},
327 // always the first pack of ops (might be the same)
328 {ObjectType: repository.Blob, Hash: bug.rootPack, Name: rootEntryName},
329 }
330
331 // Reference, if any, all the files required by the ops
332 // Git will check that they actually exist in the storage and will make sure
333 // to push/pull them as needed.
334 mediaTree := makeMediaTree(bug.staging)
335 if len(mediaTree) > 0 {
336 mediaTreeHash, err := repo.StoreTree(mediaTree)
337 if err != nil {
338 return err
339 }
340 tree = append(tree, repository.TreeEntry{
341 ObjectType: repository.Tree,
342 Hash: mediaTreeHash,
343 Name: mediaEntryName,
344 })
345 }
346
347 // Store the logical clocks as well
348 // --> edit clock for each OperationPack/commits
349 // --> create clock only for the first OperationPack/commits
350 //
351 // To avoid having one blob for each clock value, clocks are serialized
352 // directly into the entry name
353 emptyBlobHash, err := repo.StoreData([]byte{})
354 if err != nil {
355 return err
356 }
357
358 editTime, err := repo.EditTimeIncrement()
359 if err != nil {
360 return err
361 }
362
363 tree = append(tree, repository.TreeEntry{
364 ObjectType: repository.Blob,
365 Hash: emptyBlobHash,
366 Name: fmt.Sprintf(editClockEntryPattern, editTime),
367 })
368 if bug.lastCommit == "" {
369 createTime, err := repo.CreateTimeIncrement()
370 if err != nil {
371 return err
372 }
373
374 tree = append(tree, repository.TreeEntry{
375 ObjectType: repository.Blob,
376 Hash: emptyBlobHash,
377 Name: fmt.Sprintf(createClockEntryPattern, createTime),
378 })
379 }
380
381 // Store the tree
382 hash, err = repo.StoreTree(tree)
383 if err != nil {
384 return err
385 }
386
387 // Write a Git commit referencing the tree, with the previous commit as parent
388 if bug.lastCommit != "" {
389 hash, err = repo.StoreCommitWithParent(hash, bug.lastCommit)
390 } else {
391 hash, err = repo.StoreCommit(hash)
392 }
393
394 if err != nil {
395 return err
396 }
397
398 bug.lastCommit = hash
399
400 // if it was the first commit, use the commit hash as bug id
401 if bug.id == "" {
402 bug.id = string(hash)
403 }
404
405 // Create or update the Git reference for this bug
406 // When pushing later, the remote will ensure that this ref update
407 // is fast-forward, that is no data has been overwritten
408 ref := fmt.Sprintf("%s%s", bugsRefPattern, bug.id)
409 err = repo.UpdateRef(ref, hash)
410
411 if err != nil {
412 return err
413 }
414
415 bug.packs = append(bug.packs, bug.staging)
416 bug.staging = OperationPack{}
417
418 return nil
419}
420
421func makeMediaTree(pack OperationPack) []repository.TreeEntry {
422 var tree []repository.TreeEntry
423 counter := 0
424 added := make(map[util.Hash]interface{})
425
426 for _, ops := range pack.Operations {
427 for _, file := range ops.Files() {
428 if _, has := added[file]; !has {
429 tree = append(tree, repository.TreeEntry{
430 ObjectType: repository.Blob,
431 Hash: file,
432 // The name is not important here, we only need to
433 // reference the blob.
434 Name: fmt.Sprintf("file%d", counter),
435 })
436 counter++
437 added[file] = struct{}{}
438 }
439 }
440 }
441
442 return tree
443}
444
445// Merge a different version of the same bug by rebasing operations of this bug
446// that are not present in the other on top of the chain of operations of the
447// other version.
448func (bug *Bug) Merge(repo repository.Repo, other *Bug) (bool, error) {
449 // Note: a faster merge should be possible without actually reading and parsing
450 // all operations pack of our side.
451 // Reading the other side is still necessary to validate remote data, at least
452 // for new operations
453
454 if bug.id != other.id {
455 return false, errors.New("merging unrelated bugs is not supported")
456 }
457
458 if len(other.staging.Operations) > 0 {
459 return false, errors.New("merging a bug with a non-empty staging is not supported")
460 }
461
462 if bug.lastCommit == "" || other.lastCommit == "" {
463 return false, errors.New("can't merge a bug that has never been stored")
464 }
465
466 ancestor, err := repo.FindCommonAncestor(bug.lastCommit, other.lastCommit)
467
468 if err != nil {
469 return false, err
470 }
471
472 ancestorIndex := 0
473 newPacks := make([]OperationPack, 0, len(bug.packs))
474
475 // Find the root of the rebase
476 for i, pack := range bug.packs {
477 newPacks = append(newPacks, pack)
478
479 if pack.commitHash == ancestor {
480 ancestorIndex = i
481 break
482 }
483 }
484
485 if len(other.packs) == ancestorIndex+1 {
486 // Nothing to rebase, return early
487 return false, nil
488 }
489
490 // get other bug's extra packs
491 for i := ancestorIndex + 1; i < len(other.packs); i++ {
492 // clone is probably not necessary
493 newPack := other.packs[i].Clone()
494
495 newPacks = append(newPacks, newPack)
496 bug.lastCommit = newPack.commitHash
497 }
498
499 // rebase our extra packs
500 for i := ancestorIndex + 1; i < len(bug.packs); i++ {
501 pack := bug.packs[i]
502
503 // get the referenced git tree
504 treeHash, err := repo.GetTreeHash(pack.commitHash)
505
506 if err != nil {
507 return false, err
508 }
509
510 // create a new commit with the correct ancestor
511 hash, err := repo.StoreCommitWithParent(treeHash, bug.lastCommit)
512
513 // replace the pack
514 newPack := pack.Clone()
515 newPack.commitHash = hash
516 newPacks = append(newPacks, newPack)
517
518 // update the bug
519 bug.lastCommit = hash
520 }
521
522 // Update the git ref
523 err = repo.UpdateRef(bugsRefPattern+bug.id, bug.lastCommit)
524 if err != nil {
525 return false, err
526 }
527
528 return true, nil
529}
530
531// Return the Bug identifier
532func (bug *Bug) Id() string {
533 if bug.id == "" {
534 // simply panic as it would be a coding error
535 // (using an id of a bug not stored yet)
536 panic("no id yet")
537 }
538 return bug.id
539}
540
541// Return the Bug identifier truncated for human consumption
542func (bug *Bug) HumanId() string {
543 return formatHumanId(bug.Id())
544}
545
546func formatHumanId(id string) string {
547 format := fmt.Sprintf("%%.%ds", humanIdLength)
548 return fmt.Sprintf(format, id)
549}
550
551// Lookup for the very first operation of the bug.
552// For a valid Bug, this operation should be a CreateOp
553func (bug *Bug) firstOp() Operation {
554 for _, pack := range bug.packs {
555 for _, op := range pack.Operations {
556 return op
557 }
558 }
559
560 if !bug.staging.IsEmpty() {
561 return bug.staging.Operations[0]
562 }
563
564 return nil
565}
566
567// Lookup for the very last operation of the bug.
568// For a valid Bug, should never be nil
569func (bug *Bug) lastOp() Operation {
570 if !bug.staging.IsEmpty() {
571 return bug.staging.Operations[len(bug.staging.Operations)-1]
572 }
573
574 if len(bug.packs) == 0 {
575 return nil
576 }
577
578 lastPack := bug.packs[len(bug.packs)-1]
579
580 if len(lastPack.Operations) == 0 {
581 return nil
582 }
583
584 return lastPack.Operations[len(lastPack.Operations)-1]
585}
586
587// Compile a bug in a easily usable snapshot
588func (bug *Bug) Compile() Snapshot {
589 snap := Snapshot{
590 id: bug.id,
591 Status: OpenStatus,
592 }
593
594 it := NewOperationIterator(bug)
595
596 for it.Next() {
597 op := it.Value()
598 snap = op.Apply(snap)
599 snap.Operations = append(snap.Operations, op)
600 }
601
602 return snap
603}