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