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