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