bug: add a Lamport logical clock to be able to sort bugs by creation time and edit time without having to rely on a timestamp

8 files changed, 183 insertions, 21 deletions

diff --git a/bug/bug.go b/bug/bug.go
index d4eafdf2..b90beaa7 100644
--- a/bug/bug.go
+++ b/bug/bug.go
@@ -11,10 +11,16 @@ import (
 
 const bugsRefPattern = "refs/bugs/"
 const bugsRemoteRefPattern = "refs/remotes/%s/bugs/"
+
 const opsEntryName = "ops"
 const rootEntryName = "root"
 const mediaEntryName = "media"
 
+const createClockEntryPrefix = "create-clock-"
+const createClockEntryPattern = "create-clock-%d"
+const editClockEntryPrefix = "edit-clock-"
+const editClockEntryPattern = "edit-clock-%d"
+
 const idLength = 40
 const humanIdLength = 7
 
@@ -22,14 +28,19 @@ const humanIdLength = 7
 // how it will be persisted inside Git. This is the data structure
 // used for merge of two different version.
 type Bug struct {
+
+	// A Lamport clock is a logical clock that allow to order event
+	// inside a distributed system.
+	// It must be the first field in this struct due to https://github.com/golang/go/issues/599
+	createTime util.LamportTime
+	editTime   util.LamportTime
+
 	// Id used as unique identifier
 	id string
 
 	lastCommit util.Hash
 	rootPack   util.Hash
 
-	// TODO: need a way to order bugs, probably a Lamport clock
-
 	// all the commited operations
 	packs []OperationPack
 
@@ -41,6 +52,7 @@ type Bug struct {
 // Create a new Bug
 func NewBug() *Bug {
 	// No id yet
+	// No logical clock yet
 	return &Bug{}
 }
 
@@ -115,6 +127,8 @@ func readBug(repo repository.Repo, ref string) (*Bug, error) {
 		opsFound := false
 		var rootEntry repository.TreeEntry
 		rootFound := false
+		var createTime uint64
+		var editTime uint64
 
 		for _, entry := range entries {
 			if entry.Name == opsEntryName {
@@ -126,18 +140,46 @@ func readBug(repo repository.Repo, ref string) (*Bug, error) {
 				rootEntry = entry
 				rootFound = true
 			}
+			if strings.HasPrefix(entry.Name, createClockEntryPrefix) {
+				n, err := fmt.Sscanf(string(entry.Name), createClockEntryPattern, &createTime)
+				if err != nil {
+					return nil, err
+				}
+				if n != 1 {
+					return nil, fmt.Errorf("could not parse create time lamport value")
+				}
+			}
+			if strings.HasPrefix(entry.Name, editClockEntryPrefix) {
+				n, err := fmt.Sscanf(string(entry.Name), editClockEntryPattern, &editTime)
+				if err != nil {
+					return nil, err
+				}
+				if n != 1 {
+					return nil, fmt.Errorf("could not parse edit time lamport value")
+				}
+			}
 		}
 
 		if !opsFound {
 			return nil, errors.New("Invalid tree, missing the ops entry")
 		}
-
 		if !rootFound {
 			return nil, errors.New("Invalid tree, missing the root entry")
 		}
 
 		if bug.rootPack == "" {
 			bug.rootPack = rootEntry.Hash
+			bug.createTime = util.LamportTime(createTime)
+		}
+
+		bug.editTime = util.LamportTime(editTime)
+
+		// Update the clocks
+		if err := repo.CreateWitness(bug.createTime); err != nil {
+			return nil, err
+		}
+		if err := repo.EditWitness(bug.editTime); err != nil {
+			return nil, err
 		}
 
 		data, err := repo.ReadData(opsEntry.Hash)
@@ -286,7 +328,7 @@ func (bug *Bug) Commit(repo repository.Repo) error {
 		{ObjectType: repository.Blob, Hash: bug.rootPack, Name: rootEntryName},
 	}
 
-	// Also reference if any all the files required by the ops
+	// Reference, if any, all the files required by the ops
 	// Git will check that they actually exist in the storage and will make sure
 	// to push/pull them as needed.
 	mediaTree := makeMediaTree(bug.staging)
@@ -302,6 +344,40 @@ func (bug *Bug) Commit(repo repository.Repo) error {
 		})
 	}
 
+	// Store the logical clocks as well
+	// --> edit clock for each OperationPack/commits
+	// --> create clock only for the first OperationPack/commits
+	//
+	// To avoid having one blob for each clock value, clocks are serialized
+	// directly into the entry name
+	emptyBlobHash, err := repo.StoreData([]byte{})
+	if err != nil {
+		return err
+	}
+
+	editTime, err := repo.EditTimeIncrement()
+	if err != nil {
+		return err
+	}
+
+	tree = append(tree, repository.TreeEntry{
+		ObjectType: repository.Blob,
+		Hash:       emptyBlobHash,
+		Name:       fmt.Sprintf(editClockEntryPattern, editTime),
+	})
+	if bug.lastCommit == "" {
+		createTime, err := repo.CreateTimeIncrement()
+		if err != nil {
+			return err
+		}
+
+		tree = append(tree, repository.TreeEntry{
+			ObjectType: repository.Blob,
+			Hash:       emptyBlobHash,
+			Name:       fmt.Sprintf(createClockEntryPattern, createTime),
+		})
+	}
+
 	// Store the tree
 	hash, err = repo.StoreTree(tree)
 	if err != nil {
@@ -488,6 +564,26 @@ func (bug *Bug) firstOp() Operation {
 	return nil
 }
 
+// Lookup for the very last operation of the bug.
+// For a valid Bug, should never be nil
+func (bug *Bug) lastOp() Operation {
+	if !bug.staging.IsEmpty() {
+		return bug.staging.Operations[len(bug.staging.Operations)-1]
+	}
+
+	if len(bug.packs) == 0 {
+		return nil
+	}
+
+	lastPack := bug.packs[len(bug.packs)-1]
+
+	if len(lastPack.Operations) == 0 {
+		return nil
+	}
+
+	return lastPack.Operations[len(lastPack.Operations)-1]
+}
+
 // Compile a bug in a easily usable snapshot
 func (bug *Bug) Compile() Snapshot {
 	snap := Snapshot{
diff --git a/bug/clocks.go b/bug/clocks.go
new file mode 100644
index 00000000..7b254746
--- /dev/null
+++ b/bug/clocks.go
@@ -0,0 +1,18 @@
+package bug
+
+import (
+	"github.com/MichaelMure/git-bug/repository"
+)
+
+func Witnesser(repo *repository.GitRepo) error {
+	for b := range ReadAllLocalBugs(repo) {
+		if b.Err != nil {
+			return b.Err
+		}
+
+		repo.CreateWitness(b.Bug.createTime)
+		repo.EditWitness(b.Bug.editTime)
+	}
+
+	return nil
+}
diff --git a/bug/operation.go b/bug/operation.go
index 736c88dd..3949ac7b 100644
--- a/bug/operation.go
+++ b/bug/operation.go
@@ -47,3 +47,7 @@ func (op OpBase) OpType() OperationType {
 func (op OpBase) Time() time.Time {
 	return time.Unix(op.UnixTime, 0)
 }
+
+func (op OpBase) Files() []util.Hash {
+	return nil
+}
diff --git a/bug/operations/add_comment.go b/bug/operations/add_comment.go
index f2e76b73..7ae6f2dd 100644
--- a/bug/operations/add_comment.go
+++ b/bug/operations/add_comment.go
@@ -12,7 +12,8 @@ var _ bug.Operation = AddCommentOperation{}
 type AddCommentOperation struct {
 	bug.OpBase
 	Message string
-	files   []util.Hash
+	// TODO: change for a map[string]util.hash to store the filename ?
+	files []util.Hash
 }
 
 func (op AddCommentOperation) Apply(snapshot bug.Snapshot) bug.Snapshot {
diff --git a/bug/operations/label_change.go b/bug/operations/label_change.go
index f289fedc..85bae595 100644
--- a/bug/operations/label_change.go
+++ b/bug/operations/label_change.go
@@ -2,11 +2,11 @@ package operations
 
 import (
 	"fmt"
-	"github.com/MichaelMure/git-bug/bug"
-	"github.com/MichaelMure/git-bug/util"
 	"io"
 	"io/ioutil"
 	"sort"
+
+	"github.com/MichaelMure/git-bug/bug"
 )
 
 // LabelChangeOperation will add or remove a set of labels
@@ -51,10 +51,6 @@ AddLoop:
 	return snapshot
 }
 
-func (op LabelChangeOperation) Files() []util.Hash {
-	return nil
-}
-
 func NewLabelChangeOperation(author bug.Person, added, removed []bug.Label) LabelChangeOperation {
 	return LabelChangeOperation{
 		OpBase:  bug.NewOpBase(bug.LabelChangeOp, author),
diff --git a/bug/operations/set_status.go b/bug/operations/set_status.go
index 87ca14bf..ed6c328c 100644
--- a/bug/operations/set_status.go
+++ b/bug/operations/set_status.go
@@ -2,7 +2,6 @@ package operations
 
 import (
 	"github.com/MichaelMure/git-bug/bug"
-	"github.com/MichaelMure/git-bug/util"
 )
 
 // SetStatusOperation will change the status of a bug
@@ -20,10 +19,6 @@ func (op SetStatusOperation) Apply(snapshot bug.Snapshot) bug.Snapshot {
 	return snapshot
 }
 
-func (op SetStatusOperation) Files() []util.Hash {
-	return nil
-}
-
 func NewSetStatusOp(author bug.Person, status bug.Status) SetStatusOperation {
 	return SetStatusOperation{
 		OpBase: bug.NewOpBase(bug.SetStatusOp, author),
diff --git a/bug/operations/set_title.go b/bug/operations/set_title.go
index d6186f41..fab01d8a 100644
--- a/bug/operations/set_title.go
+++ b/bug/operations/set_title.go
@@ -2,7 +2,6 @@ package operations
 
 import (
 	"github.com/MichaelMure/git-bug/bug"
-	"github.com/MichaelMure/git-bug/util"
 )
 
 // SetTitleOperation will change the title of a bug
@@ -20,10 +19,6 @@ func (op SetTitleOperation) Apply(snapshot bug.Snapshot) bug.Snapshot {
 	return snapshot
 }
 
-func (op SetTitleOperation) Files() []util.Hash {
-	return nil
-}
-
 func NewSetTitleOp(author bug.Person, title string) SetTitleOperation {
 	return SetTitleOperation{
 		OpBase: bug.NewOpBase(bug.SetTitleOp, author),
diff --git a/bug/sorting.go b/bug/sorting.go
new file mode 100644
index 00000000..231055bd
--- /dev/null
+++ b/bug/sorting.go
@@ -0,0 +1,57 @@
+package bug
+
+type BugsByCreationTime []*Bug
+
+func (b BugsByCreationTime) Len() int {
+	return len(b)
+}
+
+func (b BugsByCreationTime) Less(i, j int) bool {
+	if b[i].createTime < b[j].createTime {
+		return true
+	}
+
+	if b[i].createTime > b[j].createTime {
+		return false
+	}
+
+	// When the logical clocks are identical, that means we had a concurrent
+	// edition. In this case we rely on the timestamp. While the timestamp might
+	// be incorrect due to a badly set clock, the drift in sorting is bounded
+	// by the first sorting using the logical clock. That means that if user
+	// synchronize their bugs regularly, the timestamp will rarely be used, and
+	// should still provide a kinda accurate sorting when needed.
+	return b[i].firstOp().Time().Before(b[j].firstOp().Time())
+}
+
+func (b BugsByCreationTime) Swap(i, j int) {
+	b[i], b[j] = b[j], b[i]
+}
+
+type BugsByEditTime []*Bug
+
+func (b BugsByEditTime) Len() int {
+	return len(b)
+}
+
+func (b BugsByEditTime) Less(i, j int) bool {
+	if b[i].editTime < b[j].editTime {
+		return true
+	}
+
+	if b[i].editTime > b[j].editTime {
+		return false
+	}
+
+	// When the logical clocks are identical, that means we had a concurrent
+	// edition. In this case we rely on the timestamp. While the timestamp might
+	// be incorrect due to a badly set clock, the drift in sorting is bounded
+	// by the first sorting using the logical clock. That means that if user
+	// synchronize their bugs regularly, the timestamp will rarely be used, and
+	// should still provide a kinda accurate sorting when needed.
+	return b[i].lastOp().Time().Before(b[j].lastOp().Time())
+}
+
+func (b BugsByEditTime) Swap(i, j int) {
+	b[i], b[j] = b[j], b[i]
+}