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