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