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