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