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