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