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 := 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
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 return repo.ListIds(bugsRefPattern)
259}
260
261// IsValid check if the Bug data is valid
262func (bug *Bug) IsValid() bool {
263 // non-empty
264 if len(bug.packs) == 0 && bug.staging.IsEmpty() {
265 return false
266 }
267
268 // check if each pack is valid
269 for _, pack := range bug.packs {
270 if !pack.IsValid() {
271 return false
272 }
273 }
274
275 // check if staging is valid if needed
276 if !bug.staging.IsEmpty() {
277 if !bug.staging.IsValid() {
278 return false
279 }
280 }
281
282 // The very first Op should be a CreateOp
283 firstOp := bug.firstOp()
284 if firstOp == nil || firstOp.OpType() != CreateOp {
285 return false
286 }
287
288 // Check that there is no more CreateOp op
289 it := NewOperationIterator(bug)
290 createCount := 0
291 for it.Next() {
292 if it.Value().OpType() == CreateOp {
293 createCount++
294 }
295 }
296
297 if createCount != 1 {
298 return false
299 }
300
301 return true
302}
303
304// Append an operation into the staging area, to be committed later
305func (bug *Bug) Append(op Operation) {
306 bug.staging.Append(op)
307}
308
309// HasPendingOp tell if the bug need to be committed
310func (bug *Bug) HasPendingOp() bool {
311 return !bug.staging.IsEmpty()
312}
313
314// Commit write the staging area in Git and move the operations to the packs
315func (bug *Bug) Commit(repo repository.Repo) error {
316 if bug.staging.IsEmpty() {
317 return fmt.Errorf("can't commit a bug with no pending operation")
318 }
319
320 // Write the Ops as a Git blob containing the serialized array
321 hash, err := bug.staging.Write(repo)
322 if err != nil {
323 return err
324 }
325
326 if bug.rootPack == "" {
327 bug.rootPack = hash
328 }
329
330 // Make a Git tree referencing this blob
331 tree := []repository.TreeEntry{
332 // the last pack of ops
333 {ObjectType: repository.Blob, Hash: hash, Name: opsEntryName},
334 // always the first pack of ops (might be the same)
335 {ObjectType: repository.Blob, Hash: bug.rootPack, Name: rootEntryName},
336 }
337
338 // Reference, if any, all the files required by the ops
339 // Git will check that they actually exist in the storage and will make sure
340 // to push/pull them as needed.
341 mediaTree := makeMediaTree(bug.staging)
342 if len(mediaTree) > 0 {
343 mediaTreeHash, err := repo.StoreTree(mediaTree)
344 if err != nil {
345 return err
346 }
347 tree = append(tree, repository.TreeEntry{
348 ObjectType: repository.Tree,
349 Hash: mediaTreeHash,
350 Name: mediaEntryName,
351 })
352 }
353
354 // Store the logical clocks as well
355 // --> edit clock for each OperationPack/commits
356 // --> create clock only for the first OperationPack/commits
357 //
358 // To avoid having one blob for each clock value, clocks are serialized
359 // directly into the entry name
360 emptyBlobHash, err := repo.StoreData([]byte{})
361 if err != nil {
362 return err
363 }
364
365 editTime, err := repo.EditTimeIncrement()
366 if err != nil {
367 return err
368 }
369
370 tree = append(tree, repository.TreeEntry{
371 ObjectType: repository.Blob,
372 Hash: emptyBlobHash,
373 Name: fmt.Sprintf(editClockEntryPattern, editTime),
374 })
375 if bug.lastCommit == "" {
376 createTime, err := repo.CreateTimeIncrement()
377 if err != nil {
378 return err
379 }
380
381 tree = append(tree, repository.TreeEntry{
382 ObjectType: repository.Blob,
383 Hash: emptyBlobHash,
384 Name: fmt.Sprintf(createClockEntryPattern, createTime),
385 })
386 }
387
388 // Store the tree
389 hash, err = repo.StoreTree(tree)
390 if err != nil {
391 return err
392 }
393
394 // Write a Git commit referencing the tree, with the previous commit as parent
395 if bug.lastCommit != "" {
396 hash, err = repo.StoreCommitWithParent(hash, bug.lastCommit)
397 } else {
398 hash, err = repo.StoreCommit(hash)
399 }
400
401 if err != nil {
402 return err
403 }
404
405 bug.lastCommit = hash
406
407 // if it was the first commit, use the commit hash as bug id
408 if bug.id == "" {
409 bug.id = string(hash)
410 }
411
412 // Create or update the Git reference for this bug
413 // When pushing later, the remote will ensure that this ref update
414 // is fast-forward, that is no data has been overwritten
415 ref := fmt.Sprintf("%s%s", bugsRefPattern, bug.id)
416 err = repo.UpdateRef(ref, hash)
417
418 if err != nil {
419 return err
420 }
421
422 bug.packs = append(bug.packs, bug.staging)
423 bug.staging = OperationPack{}
424
425 return nil
426}
427
428func makeMediaTree(pack OperationPack) []repository.TreeEntry {
429 var tree []repository.TreeEntry
430 counter := 0
431 added := make(map[util.Hash]interface{})
432
433 for _, ops := range pack.Operations {
434 for _, file := range ops.Files() {
435 if _, has := added[file]; !has {
436 tree = append(tree, repository.TreeEntry{
437 ObjectType: repository.Blob,
438 Hash: file,
439 // The name is not important here, we only need to
440 // reference the blob.
441 Name: fmt.Sprintf("file%d", counter),
442 })
443 counter++
444 added[file] = struct{}{}
445 }
446 }
447 }
448
449 return tree
450}
451
452// Merge a different version of the same bug by rebasing operations of this bug
453// that are not present in the other on top of the chain of operations of the
454// other version.
455func (bug *Bug) Merge(repo repository.Repo, other *Bug) (bool, error) {
456 // Note: a faster merge should be possible without actually reading and parsing
457 // all operations pack of our side.
458 // Reading the other side is still necessary to validate remote data, at least
459 // for new operations
460
461 if bug.id != other.id {
462 return false, errors.New("merging unrelated bugs is not supported")
463 }
464
465 if len(other.staging.Operations) > 0 {
466 return false, errors.New("merging a bug with a non-empty staging is not supported")
467 }
468
469 if bug.lastCommit == "" || other.lastCommit == "" {
470 return false, errors.New("can't merge a bug that has never been stored")
471 }
472
473 ancestor, err := repo.FindCommonAncestor(bug.lastCommit, other.lastCommit)
474
475 if err != nil {
476 return false, err
477 }
478
479 ancestorIndex := 0
480 newPacks := make([]OperationPack, 0, len(bug.packs))
481
482 // Find the root of the rebase
483 for i, pack := range bug.packs {
484 newPacks = append(newPacks, pack)
485
486 if pack.commitHash == ancestor {
487 ancestorIndex = i
488 break
489 }
490 }
491
492 if len(other.packs) == ancestorIndex+1 {
493 // Nothing to rebase, return early
494 return false, nil
495 }
496
497 // get other bug's extra packs
498 for i := ancestorIndex + 1; i < len(other.packs); i++ {
499 // clone is probably not necessary
500 newPack := other.packs[i].Clone()
501
502 newPacks = append(newPacks, newPack)
503 bug.lastCommit = newPack.commitHash
504 }
505
506 // rebase our extra packs
507 for i := ancestorIndex + 1; i < len(bug.packs); i++ {
508 pack := bug.packs[i]
509
510 // get the referenced git tree
511 treeHash, err := repo.GetTreeHash(pack.commitHash)
512
513 if err != nil {
514 return false, err
515 }
516
517 // create a new commit with the correct ancestor
518 hash, err := repo.StoreCommitWithParent(treeHash, bug.lastCommit)
519
520 if err != nil {
521 return false, err
522 }
523
524 // replace the pack
525 newPack := pack.Clone()
526 newPack.commitHash = hash
527 newPacks = append(newPacks, newPack)
528
529 // update the bug
530 bug.lastCommit = hash
531 }
532
533 // Update the git ref
534 err = repo.UpdateRef(bugsRefPattern+bug.id, bug.lastCommit)
535 if err != nil {
536 return false, err
537 }
538
539 return true, nil
540}
541
542// Id return the Bug identifier
543func (bug *Bug) Id() string {
544 if bug.id == "" {
545 // simply panic as it would be a coding error
546 // (using an id of a bug not stored yet)
547 panic("no id yet")
548 }
549 return bug.id
550}
551
552// HumanId return the Bug identifier truncated for human consumption
553func (bug *Bug) HumanId() string {
554 return formatHumanId(bug.Id())
555}
556
557func formatHumanId(id string) string {
558 format := fmt.Sprintf("%%.%ds", humanIdLength)
559 return fmt.Sprintf(format, id)
560}
561
562// Lookup for the very first operation of the bug.
563// For a valid Bug, this operation should be a CreateOp
564func (bug *Bug) firstOp() Operation {
565 for _, pack := range bug.packs {
566 for _, op := range pack.Operations {
567 return op
568 }
569 }
570
571 if !bug.staging.IsEmpty() {
572 return bug.staging.Operations[0]
573 }
574
575 return nil
576}
577
578// Lookup for the very last operation of the bug.
579// For a valid Bug, should never be nil
580func (bug *Bug) lastOp() Operation {
581 if !bug.staging.IsEmpty() {
582 return bug.staging.Operations[len(bug.staging.Operations)-1]
583 }
584
585 if len(bug.packs) == 0 {
586 return nil
587 }
588
589 lastPack := bug.packs[len(bug.packs)-1]
590
591 if len(lastPack.Operations) == 0 {
592 return nil
593 }
594
595 return lastPack.Operations[len(lastPack.Operations)-1]
596}
597
598// Compile a bug in a easily usable snapshot
599func (bug *Bug) Compile() Snapshot {
600 snap := Snapshot{
601 id: bug.id,
602 Status: OpenStatus,
603 }
604
605 it := NewOperationIterator(bug)
606
607 for it.Next() {
608 op := it.Value()
609 snap = op.Apply(snap)
610 snap.Operations = append(snap.Operations, op)
611 }
612
613 return snap
614}