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