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