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