diff options
-rw-r--r-- | bug/bug.go | 104 | ||||
-rw-r--r-- | bug/clocks.go | 18 | ||||
-rw-r--r-- | bug/operation.go | 4 | ||||
-rw-r--r-- | bug/operations/add_comment.go | 3 | ||||
-rw-r--r-- | bug/operations/label_change.go | 8 | ||||
-rw-r--r-- | bug/operations/set_status.go | 5 | ||||
-rw-r--r-- | bug/operations/set_title.go | 5 | ||||
-rw-r--r-- | bug/sorting.go | 57 | ||||
-rw-r--r-- | commands/root.go | 8 | ||||
-rw-r--r-- | repository/git.go | 97 | ||||
-rw-r--r-- | repository/mock_repo.go | 46 | ||||
-rw-r--r-- | repository/repo.go | 12 | ||||
-rw-r--r-- | util/lamport.go | 4 | ||||
-rw-r--r-- | util/lamport_test.go | 2 | ||||
-rw-r--r-- | util/persisted_lamport.go | 21 |
15 files changed, 345 insertions, 49 deletions
@@ -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] +} diff --git a/commands/root.go b/commands/root.go index cee39083..be258199 100644 --- a/commands/root.go +++ b/commands/root.go @@ -2,6 +2,7 @@ package commands import ( "fmt" + "github.com/MichaelMure/git-bug/bug" "github.com/MichaelMure/git-bug/repository" "github.com/spf13/cobra" "os" @@ -49,10 +50,13 @@ func loadRepo(cmd *cobra.Command, args []string) error { return fmt.Errorf("Unable to get the current working directory: %q\n", err) } - repo, err = repository.NewGitRepo(cwd) - if err != nil { + repo, err = repository.NewGitRepo(cwd, bug.Witnesser) + if err == repository.ErrNotARepo { return fmt.Errorf("%s must be run from within a git repo.\n", rootCommandName) + } + if err != nil { + return err } return nil diff --git a/repository/git.go b/repository/git.go index aa0e72b7..5748d52a 100644 --- a/repository/git.go +++ b/repository/git.go @@ -3,18 +3,27 @@ package repository import ( "bytes" + "errors" "fmt" "io" "os" "os/exec" + "path" "strings" "github.com/MichaelMure/git-bug/util" ) +const createClockFile = "/.git/git-bug/create-clock" +const editClockFile = "/.git/git-bug/edit-clock" + +var ErrNotARepo = errors.New("not a git repository") + // GitRepo represents an instance of a (local) git repository. type GitRepo struct { - Path string + Path string + createClock *util.PersistedLamport + editClock *util.PersistedLamport } // Run the given git command with the given I/O reader/writers, returning an error if it fails. @@ -62,35 +71,62 @@ func (repo *GitRepo) runGitCommandInline(args ...string) error { // NewGitRepo determines if the given working directory is inside of a git repository, // and returns the corresponding GitRepo instance if it is. -func NewGitRepo(path string) (*GitRepo, error) { +func NewGitRepo(path string, witnesser func(repo *GitRepo) error) (*GitRepo, error) { repo := &GitRepo{Path: path} + + // Check the repo and retrieve the root path stdout, err := repo.runGitCommand("rev-parse", "--show-toplevel") if err != nil { - return nil, err + return nil, ErrNotARepo } // Fix the path to be sure we are at the root repo.Path = stdout + err = repo.LoadClocks() + + if err != nil { + // No clock yet, trying to initialize them + repo.createClocks() + + err = witnesser(repo) + if err != nil { + return nil, err + } + + err = repo.WriteClocks() + if err != nil { + return nil, err + } + + return repo, nil + } + return repo, nil } func InitGitRepo(path string) (*GitRepo, error) { repo := &GitRepo{Path: path} + repo.createClocks() + _, err := repo.runGitCommand("init", path) if err != nil { return nil, err } + return repo, nil } func InitBareGitRepo(path string) (*GitRepo, error) { repo := &GitRepo{Path: path} + repo.createClocks() + _, err := repo.runGitCommand("init", "--bare", path) if err != nil { return nil, err } + return repo, nil } @@ -308,8 +344,63 @@ func (repo *GitRepo) GetTreeHash(commit util.Hash) (util.Hash, error) { } // Add a new remote to the repository +// Not in the interface because it's only used for testing func (repo *GitRepo) AddRemote(name string, url string) error { _, err := repo.runGitCommand("remote", "add", name, url) return err } + +func (repo *GitRepo) createClocks() { + createPath := path.Join(repo.Path, createClockFile) + repo.createClock = util.NewPersistedLamport(createPath) + + editPath := path.Join(repo.Path, editClockFile) + repo.editClock = util.NewPersistedLamport(editPath) +} + +func (repo *GitRepo) LoadClocks() error { + createClock, err := util.LoadPersistedLamport(repo.GetPath() + createClockFile) + if err != nil { + return err + } + + editClock, err := util.LoadPersistedLamport(repo.GetPath() + editClockFile) + if err != nil { + return err + } + + repo.createClock = createClock + repo.editClock = editClock + return nil +} + +func (repo *GitRepo) WriteClocks() error { + err := repo.createClock.Write() + if err != nil { + return err + } + + err = repo.editClock.Write() + if err != nil { + return err + } + + return nil +} + +func (repo *GitRepo) CreateTimeIncrement() (util.LamportTime, error) { + return repo.createClock.Increment() +} + +func (repo *GitRepo) EditTimeIncrement() (util.LamportTime, error) { + return repo.editClock.Increment() +} + +func (repo *GitRepo) CreateWitness(time util.LamportTime) error { + return repo.createClock.Witness(time) +} + +func (repo *GitRepo) EditWitness(time util.LamportTime) error { + return repo.editClock.Witness(time) +} diff --git a/repository/mock_repo.go b/repository/mock_repo.go index f8653c64..eb48f85f 100644 --- a/repository/mock_repo.go +++ b/repository/mock_repo.go @@ -10,10 +10,12 @@ import ( // mockRepoForTest defines an instance of Repo that can be used for testing. type mockRepoForTest struct { - blobs map[util.Hash][]byte - trees map[util.Hash]string - commits map[util.Hash]commit - refs map[string]util.Hash + blobs map[util.Hash][]byte + trees map[util.Hash]string + commits map[util.Hash]commit + refs map[string]util.Hash + createClock util.LamportClock + editClock util.LamportClock } type commit struct { @@ -23,10 +25,12 @@ type commit struct { func NewMockRepoForTest() Repo { return &mockRepoForTest{ - blobs: make(map[util.Hash][]byte), - trees: make(map[util.Hash]string), - commits: make(map[util.Hash]commit), - refs: make(map[string]util.Hash), + blobs: make(map[util.Hash][]byte), + trees: make(map[util.Hash]string), + commits: make(map[util.Hash]commit), + refs: make(map[string]util.Hash), + createClock: util.NewLamportClock(), + editClock: util.NewLamportClock(), } } @@ -200,3 +204,29 @@ func (r *mockRepoForTest) FindCommonAncestor(hash1 util.Hash, hash2 util.Hash) ( func (r *mockRepoForTest) GetTreeHash(commit util.Hash) (util.Hash, error) { panic("implement me") } + +func (r *mockRepoForTest) LoadClocks() error { + return nil +} + +func (r *mockRepoForTest) WriteClocks() error { + return nil +} + +func (r *mockRepoForTest) CreateTimeIncrement() (util.LamportTime, error) { + return r.createClock.Increment(), nil +} + +func (r *mockRepoForTest) EditTimeIncrement() (util.LamportTime, error) { + return r.editClock.Increment(), nil +} + +func (r *mockRepoForTest) CreateWitness(time util.LamportTime) error { + r.createClock.Witness(time) + return nil +} + +func (r *mockRepoForTest) EditWitness(time util.LamportTime) error { + r.editClock.Witness(time) + return nil +} diff --git a/repository/repo.go b/repository/repo.go index 38d8a6cb..057223ad 100644 --- a/repository/repo.go +++ b/repository/repo.go @@ -69,6 +69,18 @@ type Repo interface { // Return the git tree hash referenced in a commit GetTreeHash(commit util.Hash) (util.Hash, error) + + LoadClocks() error + + WriteClocks() error + + CreateTimeIncrement() (util.LamportTime, error) + + EditTimeIncrement() (util.LamportTime, error) + + CreateWitness(time util.LamportTime) error + + EditWitness(time util.LamportTime) error } func prepareTreeEntries(entries []TreeEntry) bytes.Buffer { diff --git a/util/lamport.go b/util/lamport.go index c75e1d15..4d5dcf5b 100644 --- a/util/lamport.go +++ b/util/lamport.go @@ -58,9 +58,9 @@ func (l *LamportClock) Time() LamportTime { return LamportTime(atomic.LoadUint64(&l.counter)) } -// Increment is used to increment and return the value of the lamport clock +// Increment is used to return the value of the lamport clock and increment it afterwards func (l *LamportClock) Increment() LamportTime { - return LamportTime(atomic.AddUint64(&l.counter, 1)) + return LamportTime(atomic.AddUint64(&l.counter, 1) - 1) } // Witness is called to update our local clock if necessary after diff --git a/util/lamport_test.go b/util/lamport_test.go index 0bac7d51..de7f1822 100644 --- a/util/lamport_test.go +++ b/util/lamport_test.go @@ -38,7 +38,7 @@ func TestLamportClock(t *testing.T) { t.Fatalf("bad time value") } - if l.Increment() != 1 { + if l.Increment() != 0 { t.Fatalf("bad time value") } diff --git a/util/persisted_lamport.go b/util/persisted_lamport.go index 43a2863c..c8c898e2 100644 --- a/util/persisted_lamport.go +++ b/util/persisted_lamport.go @@ -14,7 +14,8 @@ type PersistedLamport struct { func NewPersistedLamport(filePath string) *PersistedLamport { clock := &PersistedLamport{ - filePath: filePath, + LamportClock: NewLamportClock(), + filePath: filePath, } return clock } @@ -32,21 +33,17 @@ func LoadPersistedLamport(filePath string) (*PersistedLamport, error) { return clock, nil } +func (c *PersistedLamport) Increment() (LamportTime, error) { + time := c.LamportClock.Increment() + return time, c.Write() +} + func (c *PersistedLamport) Witness(time LamportTime) error { + // TODO: rework so that we write only when the clock was actually updated c.LamportClock.Witness(time) return c.Write() } -func (c *PersistedLamport) Time() LamportTime { - // Equivalent to: - // - // res = c.LamportClock.Time() - // bugClock.Increment() - // - // ... but thread safe - return c.Increment() - 1 -} - func (c *PersistedLamport) read() error { content, err := ioutil.ReadFile(c.filePath) if err != nil { @@ -76,6 +73,6 @@ func (c *PersistedLamport) Write() error { return err } - data := []byte(fmt.Sprintf("%d", c.LamportClock.Time())) + data := []byte(fmt.Sprintf("%d", c.counter)) return ioutil.WriteFile(c.filePath, data, 0644) } |