Documentation
¶
Overview ¶
Package dag contains the base common code to define an entity stored in a chain of git objects, supporting actions like Push, Pull and Merge.
Example (Entity) ¶
package main import ( "encoding/json" "fmt" "os" "time" "github.com/MichaelMure/git-bug/entities/identity" "github.com/MichaelMure/git-bug/entity" "github.com/MichaelMure/git-bug/entity/dag" "github.com/MichaelMure/git-bug/repository" ) // Note: you can find explanations about the underlying data model here: // https://github.com/MichaelMure/git-bug/blob/master/doc/model.md // This file explains how to define a replicated data structure, stored in and using git as a medium for // synchronisation. To do this, we'll use the entity/dag package, which will do all the complex handling. // // The example we'll use here is a small shared configuration with two fields. One of them is special as // it also defines who is allowed to change said configuration. // Note: this example is voluntarily a bit complex with operation linking to identities and logic rules, // to show that how something more complex than a toy would look like. That said, it's still a simplified // example: in git-bug for example, more layers are added for caching, memory handling and to provide an // easier to use API. // // Let's start by defining the document/structure we are going to share: // Snapshot is the compiled view of a ProjectConfig type Snapshot struct { // Administrator is the set of users with the higher level of access Administrator map[identity.Interface]struct{} // SignatureRequired indicate that all git commit need to be signed SignatureRequired bool } // HasAdministrator returns true if the given identity is included in the administrator. func (snap *Snapshot) HasAdministrator(i identity.Interface) bool { for admin, _ := range snap.Administrator { if admin.Id() == i.Id() { return true } } return false } // Now, we will not edit this configuration directly. Instead, we are going to apply "operations" on it. // Those are the ones that will be stored and shared. Doing things that way allow merging concurrent editing // and deal with conflict. // // Here, we will define three operations: // - SetSignatureRequired is a simple operation that set or unset the SignatureRequired boolean // - AddAdministrator is more complex and add a new administrator in the Administrator set // - RemoveAdministrator is the counterpart the remove administrators // // Note: there is some amount of boilerplate for operations. In a real project, some of that can be // factorized and simplified. // Operation is the operation interface acting on Snapshot type Operation interface { dag.Operation // Apply the operation to a Snapshot to create the final state Apply(snapshot *Snapshot) } const ( _ dag.OperationType = iota SetSignatureRequiredOp AddAdministratorOp RemoveAdministratorOp ) // SetSignatureRequired is an operation to set/unset if git signature are required. type SetSignatureRequired struct { dag.OpBase Value bool `json:"value"` } func NewSetSignatureRequired(author identity.Interface, value bool) *SetSignatureRequired { return &SetSignatureRequired{ OpBase: dag.NewOpBase(SetSignatureRequiredOp, author, time.Now().Unix()), Value: value, } } func (ssr *SetSignatureRequired) Id() entity.Id { // the Id of the operation is the hash of the serialized data. return dag.IdOperation(ssr, &ssr.OpBase) } func (ssr *SetSignatureRequired) Validate() error { return ssr.OpBase.Validate(ssr, SetSignatureRequiredOp) } // Apply is the function that makes changes on the snapshot func (ssr *SetSignatureRequired) Apply(snapshot *Snapshot) { // check that we are allowed to change the config if _, ok := snapshot.Administrator[ssr.Author()]; !ok { return } snapshot.SignatureRequired = ssr.Value } // AddAdministrator is an operation to add a new administrator in the set type AddAdministrator struct { dag.OpBase ToAdd []identity.Interface `json:"to_add"` } func NewAddAdministratorOp(author identity.Interface, toAdd ...identity.Interface) *AddAdministrator { return &AddAdministrator{ OpBase: dag.NewOpBase(AddAdministratorOp, author, time.Now().Unix()), ToAdd: toAdd, } } func (aa *AddAdministrator) Id() entity.Id { // the Id of the operation is the hash of the serialized data. return dag.IdOperation(aa, &aa.OpBase) } func (aa *AddAdministrator) Validate() error { // Let's enforce an arbitrary rule if len(aa.ToAdd) == 0 { return fmt.Errorf("nothing to add") } return aa.OpBase.Validate(aa, AddAdministratorOp) } // Apply is the function that makes changes on the snapshot func (aa *AddAdministrator) Apply(snapshot *Snapshot) { // check that we are allowed to change the config ... or if there is no admin yet if !snapshot.HasAdministrator(aa.Author()) && len(snapshot.Administrator) != 0 { return } for _, toAdd := range aa.ToAdd { snapshot.Administrator[toAdd] = struct{}{} } } // RemoveAdministrator is an operation to remove an administrator from the set type RemoveAdministrator struct { dag.OpBase ToRemove []identity.Interface `json:"to_remove"` } func NewRemoveAdministratorOp(author identity.Interface, toRemove ...identity.Interface) *RemoveAdministrator { return &RemoveAdministrator{ OpBase: dag.NewOpBase(RemoveAdministratorOp, author, time.Now().Unix()), ToRemove: toRemove, } } func (ra *RemoveAdministrator) Id() entity.Id { // the Id of the operation is the hash of the serialized data. return dag.IdOperation(ra, &ra.OpBase) } func (ra *RemoveAdministrator) Validate() error { // Let's enforce some rules. If we return an error, this operation will be // considered invalid and will not be included in our data. if len(ra.ToRemove) == 0 { return fmt.Errorf("nothing to remove") } return ra.OpBase.Validate(ra, RemoveAdministratorOp) } // Apply is the function that makes changes on the snapshot func (ra *RemoveAdministrator) Apply(snapshot *Snapshot) { // check if we are allowed to make changes if !snapshot.HasAdministrator(ra.Author()) { return } // special rule: we can't end up with no administrator stillSome := false for admin, _ := range snapshot.Administrator { if admin != ra.Author() { stillSome = true break } } if !stillSome { return } // apply for _, toRemove := range ra.ToRemove { delete(snapshot.Administrator, toRemove) } } // Now, let's create the main object (the entity) we are going to manipulate: ProjectConfig. // This object wrap a dag.Entity, which makes it inherit some methods and provide all the complex // DAG handling. Additionally, ProjectConfig is the place where we can add functions specific for that type. type ProjectConfig struct { // this is really all we need *dag.Entity } func NewProjectConfig() *ProjectConfig { return &ProjectConfig{Entity: dag.New(def)} } // a Definition describes a few properties of the Entity, a sort of configuration to manipulate the // DAG of operations var def = dag.Definition{ Typename: "project config", Namespace: "conf", OperationUnmarshaler: operationUnmarshaler, FormatVersion: 1, } // operationUnmarshaler is a function doing the de-serialization of the JSON data into our own // concrete Operations. If needed, we can use the resolver to connect to other entities. func operationUnmarshaler(raw json.RawMessage, resolvers entity.Resolvers) (dag.Operation, error) { var t struct { OperationType dag.OperationType `json:"type"` } if err := json.Unmarshal(raw, &t); err != nil { return nil, err } var op dag.Operation switch t.OperationType { case AddAdministratorOp: op = &AddAdministrator{} case RemoveAdministratorOp: op = &RemoveAdministrator{} case SetSignatureRequiredOp: op = &SetSignatureRequired{} default: panic(fmt.Sprintf("unknown operation type %v", t.OperationType)) } err := json.Unmarshal(raw, &op) if err != nil { return nil, err } switch op := op.(type) { case *AddAdministrator: // We need to resolve identities for i, stub := range op.ToAdd { iden, err := entity.Resolve[identity.Interface](resolvers, stub.Id()) if err != nil { return nil, err } op.ToAdd[i] = iden } case *RemoveAdministrator: // We need to resolve identities for i, stub := range op.ToRemove { iden, err := entity.Resolve[identity.Interface](resolvers, stub.Id()) if err != nil { return nil, err } op.ToRemove[i] = iden } } return op, nil } // Compile compute a view of the final state. This is what we would use to display the state // in a user interface. func (pc ProjectConfig) Compile() *Snapshot { // Note: this would benefit from caching, but it's a simple example snap := &Snapshot{ // default value Administrator: make(map[identity.Interface]struct{}), SignatureRequired: false, } for _, op := range pc.Operations() { op.(Operation).Apply(snap) } return snap } // Read is a helper to load a ProjectConfig from a Repository func Read(repo repository.ClockedRepo, id entity.Id) (*ProjectConfig, error) { e, err := dag.Read(def, repo, simpleResolvers(repo), id) if err != nil { return nil, err } return &ProjectConfig{Entity: e}, nil } func simpleResolvers(repo repository.ClockedRepo) entity.Resolvers { // resolvers can look a bit complex or out of place here, but it's an important concept // to allow caching and flexibility when constructing the final app. return entity.Resolvers{ &identity.Identity{}: identity.NewSimpleResolver(repo), } } func main() { const gitBugNamespace = "git-bug" // Note: this example ignore errors for readability // Note: variable names get a little confusing as we are simulating both side in the same function // Let's start by defining two git repository and connecting them as remote repoRenePath, _ := os.MkdirTemp("", "") repoIsaacPath, _ := os.MkdirTemp("", "") repoRene, _ := repository.InitGoGitRepo(repoRenePath, gitBugNamespace) defer repoRene.Close() repoIsaac, _ := repository.InitGoGitRepo(repoIsaacPath, gitBugNamespace) defer repoIsaac.Close() _ = repoRene.AddRemote("origin", repoIsaacPath) _ = repoIsaac.AddRemote("origin", repoRenePath) // Now we need identities and to propagate them rene, _ := identity.NewIdentity(repoRene, "René Descartes", "rene@descartes.fr") isaac, _ := identity.NewIdentity(repoRene, "Isaac Newton", "isaac@newton.uk") _ = rene.Commit(repoRene) _ = isaac.Commit(repoRene) _ = identity.Pull(repoIsaac, "origin") // create a new entity confRene := NewProjectConfig() // add some operations confRene.Append(NewAddAdministratorOp(rene, rene)) confRene.Append(NewAddAdministratorOp(rene, isaac)) confRene.Append(NewSetSignatureRequired(rene, true)) // Rene commits on its own repo _ = confRene.Commit(repoRene) // Isaac pull and read the config _ = dag.Pull(def, repoIsaac, simpleResolvers(repoIsaac), "origin", isaac) confIsaac, _ := Read(repoIsaac, confRene.Id()) // Compile gives the current state of the config snapshot := confIsaac.Compile() for admin, _ := range snapshot.Administrator { fmt.Println(admin.DisplayName()) } // Isaac add more operations confIsaac.Append(NewSetSignatureRequired(isaac, false)) reneFromIsaacRepo, _ := identity.ReadLocal(repoIsaac, rene.Id()) confIsaac.Append(NewRemoveAdministratorOp(isaac, reneFromIsaacRepo)) _ = confIsaac.Commit(repoIsaac) }
Output:
Index ¶
- func ClockLoader(defs ...Definition) repository.ClockLoader
- func Fetch(def Definition, repo repository.Repo, remote string) (string, error)
- func IdOperation(op Operation, base *OpBase) entity.Id
- func ListLocalIds(def Definition, repo repository.RepoData) ([]entity.Id, error)
- func MergeAll(def Definition, repo repository.ClockedRepo, resolvers entity.Resolvers, ...) <-chan entity.MergeResult
- func Pull(def Definition, repo repository.ClockedRepo, resolvers entity.Resolvers, ...) error
- func Push(def Definition, repo repository.Repo, remote string) (string, error)
- func ReadAll(def Definition, repo repository.ClockedRepo, resolvers entity.Resolvers) <-chan StreamedEntity
- func ReadAllClocksNoCheck(def Definition, repo repository.ClockedRepo) error
- func Remove(def Definition, repo repository.ClockedRepo, id entity.Id) error
- func SerializeRoundTripTest[OpT Operation](t *testing.T, unmarshaler OperationUnmarshaler, ...)
- type Definition
- type Entity
- func (e *Entity) Append(op Operation)
- func (e *Entity) Commit(repo repository.ClockedRepo) error
- func (e *Entity) CommitAsNeeded(repo repository.ClockedRepo) error
- func (e *Entity) CreateLamportTime() lamport.Time
- func (e *Entity) EditLamportTime() lamport.Time
- func (e *Entity) FirstOp() Operation
- func (e *Entity) Id() entity.Id
- func (e *Entity) LastOp() Operation
- func (e *Entity) NeedCommit() bool
- func (e *Entity) Operations() []Operation
- func (e *Entity) Validate() error
- type Interface
- type NoOpOperation
- type OpBase
- func (base *OpBase) AllMetadata() map[string]string
- func (base *OpBase) Author() identity.Interface
- func (base *OpBase) GetMetadata(key string) (string, bool)
- func (base *OpBase) IdIsSet() bool
- func (base *OpBase) IsAuthored()
- func (base *OpBase) SetMetadata(key string, value string)
- func (base *OpBase) Time() time.Time
- func (base *OpBase) Type() OperationType
- func (base *OpBase) Validate(op Operation, opType OperationType) error
- type Operation
- type OperationDoesntChangeSnapshot
- type OperationType
- type OperationUnmarshaler
- type OperationWithFiles
- type PGPKeyring
- type SetMetadataOperation
- type Snapshot
- type StreamedEntity
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ClockLoader ¶
func ClockLoader(defs ...Definition) repository.ClockLoader
ClockLoader is the repository.ClockLoader for Entity
func Fetch ¶
func Fetch(def Definition, repo repository.Repo, remote string) (string, error)
Fetch retrieve updates from a remote This does not change the local entity state
func ListLocalIds ¶
func ListLocalIds(def Definition, repo repository.RepoData) ([]entity.Id, error)
ListLocalIds list all the available local Entity's Id
func MergeAll ¶
func MergeAll(def Definition, repo repository.ClockedRepo, resolvers entity.Resolvers, remote string, author identity.Interface) <-chan entity.MergeResult
MergeAll will merge all the available remote Entity:
Multiple scenario exist:
- if the remote Entity doesn't exist locally, it's created --> emit entity.MergeStatusNew
- if the remote and local Entity have the same state, nothing is changed --> emit entity.MergeStatusNothing
- if the local Entity has new commits but the remote don't, nothing is changed --> emit entity.MergeStatusNothing
- if the remote has new commit, the local bug is updated to match the same history (fast-forward update) --> emit entity.MergeStatusUpdated
- if both local and remote Entity have new commits (that is, we have a concurrent edition), a merge commit with an empty operationPack is created to join both branch and form a DAG. --> emit entity.MergeStatusUpdated
Note: an author is necessary for the case where a merge commit is created, as this commit will have an author and may be signed if a signing key is available.
func Pull ¶
func Pull(def Definition, repo repository.ClockedRepo, resolvers entity.Resolvers, remote string, author identity.Interface) error
Pull will do a Fetch + MergeAll Contrary to MergeAll, this function will return an error if a merge fail.
func Push ¶
func Push(def Definition, repo repository.Repo, remote string) (string, error)
Push update a remote with the local changes
func ReadAll ¶
func ReadAll(def Definition, repo repository.ClockedRepo, resolvers entity.Resolvers) <-chan StreamedEntity
ReadAll read and parse all local Entity
func ReadAllClocksNoCheck ¶
func ReadAllClocksNoCheck(def Definition, repo repository.ClockedRepo) error
ReadAllClocksNoCheck goes over all entities matching Definition and read/witness the corresponding clocks so that the repo end up with correct clocks for the next write.
func Remove ¶
func Remove(def Definition, repo repository.ClockedRepo, id entity.Id) error
Remove delete an Entity. Remove is idempotent.
func SerializeRoundTripTest ¶
func SerializeRoundTripTest[OpT Operation]( t *testing.T, unmarshaler OperationUnmarshaler, maker func(author identity.Interface, unixTime int64) (OpT, entity.Resolvers), )
SerializeRoundTripTest realize a marshall/unmarshall round-trip in the same condition as with OperationPack, and check if the recovered operation is identical.
Types ¶
type Definition ¶
type Definition struct { // the name of the entity (bug, pull-request, ...), for human consumption Typename string // the Namespace in git references (bugs, prs, ...) Namespace string // a function decoding a JSON message into an Operation OperationUnmarshaler OperationUnmarshaler // the expected format version number, that can be used for data migration/upgrade FormatVersion uint }
Definition hold the details defining one specialization of an Entity.
type Entity ¶
type Entity struct { Definition // contains filtered or unexported fields }
Entity is a data structure stored in a chain of git objects, supporting actions like Push, Pull and Merge.
func Read ¶
func Read(def Definition, repo repository.ClockedRepo, resolvers entity.Resolvers, id entity.Id) (*Entity, error)
Read will read and decode a stored local Entity from a repository
func (*Entity) Commit ¶
func (e *Entity) Commit(repo repository.ClockedRepo) error
Commit write the appended operations in the repository
func (*Entity) CommitAsNeeded ¶
func (e *Entity) CommitAsNeeded(repo repository.ClockedRepo) error
CommitAsNeeded execute a Commit only if necessary. This function is useful to avoid getting an error if the Entity is already in sync with the repository.
func (*Entity) CreateLamportTime ¶
CreateLamportTime return the Lamport time of creation
func (*Entity) EditLamportTime ¶
EditLamportTime return the Lamport time of the last edition
func (*Entity) NeedCommit ¶
NeedCommit indicate if the in-memory state changed and need to be commit in the repository
func (*Entity) Operations ¶
Operations return the ordered operations
type Interface ¶
type Interface[SnapT Snapshot, OpT Operation] interface { entity.Interface // Validate checks if the Entity data is valid Validate() error // Append an operation into the staging area, to be committed later Append(op OpT) // Operations returns the ordered operations Operations() []OpT // NeedCommit indicates that the in-memory state changed and need to be committed in the repository NeedCommit() bool // Commit writes the staging area in Git and move the operations to the packs Commit(repo repository.ClockedRepo) error // FirstOp lookup for the very first operation of the Entity. FirstOp() OpT // LastOp lookup for the very last operation of the Entity. // For a valid Entity, should never be nil LastOp() OpT // Compile a bug in an easily usable snapshot Compile() SnapT // CreateLamportTime return the Lamport time of creation CreateLamportTime() lamport.Time // EditLamportTime return the Lamport time of the last edit EditLamportTime() lamport.Time }
Interface define the extended interface of a dag.Entity
type NoOpOperation ¶
NoOpOperation is an operation that does not change the entity state. It can however be used to store arbitrary metadata in the entity history, for example to support a bridge feature.
func NewNoOpOp ¶
func NewNoOpOp[SnapT Snapshot](opType OperationType, author identity.Interface, unixTime int64) *NoOpOperation[SnapT]
func (*NoOpOperation[SnapT]) Apply ¶
func (op *NoOpOperation[SnapT]) Apply(snapshot SnapT)
func (*NoOpOperation[SnapT]) DoesntChangeSnapshot ¶
func (op *NoOpOperation[SnapT]) DoesntChangeSnapshot()
func (*NoOpOperation[SnapT]) Id ¶
func (op *NoOpOperation[SnapT]) Id() entity.Id
func (*NoOpOperation[SnapT]) Validate ¶
func (op *NoOpOperation[SnapT]) Validate() error
type OpBase ¶
type OpBase struct { OperationType OperationType `json:"type"` UnixTime int64 `json:"timestamp"` // mandatory random bytes to ensure a better randomness of the data used to later generate the ID // len(Nonce) should be > 20 and < 64 bytes // It has no functional purpose and should be ignored. Nonce []byte `json:"nonce"` Metadata map[string]string `json:"metadata,omitempty"` // contains filtered or unexported fields }
OpBase implement the common feature that every Operation should support.
func NewOpBase ¶
func NewOpBase(opType OperationType, author identity.Interface, unixTime int64) OpBase
func (*OpBase) AllMetadata ¶
AllMetadata return all metadata for this operation
func (*OpBase) GetMetadata ¶
GetMetadata retrieve arbitrary metadata about the operation
func (*OpBase) IsAuthored ¶
func (base *OpBase) IsAuthored()
IsAuthored is a sign post method for gqlgen
func (*OpBase) SetMetadata ¶
SetMetadata store arbitrary metadata about the operation
func (*OpBase) Type ¶
func (base *OpBase) Type() OperationType
type Operation ¶
type Operation interface { // Id return the Operation identifier // // Some care need to be taken to define a correct Id derivation and enough entropy in the data used to avoid // collisions. Notably: // - the Id of the first Operation will be used as the Id of the Entity. Collision need to be avoided across entities // of the same type (example: no collision within the "bug" namespace). // - collisions can also happen within the set of Operations of an Entity. Simple Operation might not have enough // entropy to yield unique Ids (example: two "close" operation within the same second, same author). // If this is a concern, it is recommended to include a piece of random data in the operation's data, to guarantee // a minimal amount of entropy and avoid collision. // // Author's note: I tried to find a clever way around that inelegance (stuffing random useless data into the stored // structure is not exactly elegant), but I failed to find a proper way. Essentially, anything that would reuse some // other data (parent operation's Id, lamport clock) or the graph structure (depth) impose that the Id would only // make sense in the context of the graph and yield some deep coupling between Entity and Operation. This in turn // make the whole thing even less elegant. // // A common way to derive an Id will be to use the entity.DeriveId() function on the serialized operation data. Id() entity.Id // Type return the type of the operation Type() OperationType // Validate check if the Operation data is valid Validate() error // Author returns the author of this operation Author() identity.Interface // Time return the time when the operation was added Time() time.Time // SetMetadata store arbitrary metadata about the operation SetMetadata(key string, value string) // GetMetadata retrieve arbitrary metadata about the operation GetMetadata(key string) (string, bool) // AllMetadata return all metadata for this operation AllMetadata() map[string]string // contains filtered or unexported methods }
Operation is a piece of data defining a change to reflect on the state of an Entity. What this Operation or Entity's state looks like is not of the resort of this package as it only deals with the data structure and storage.
type OperationDoesntChangeSnapshot ¶
type OperationDoesntChangeSnapshot interface {
DoesntChangeSnapshot()
}
OperationDoesntChangeSnapshot is an interface signaling that the Operation implementing it doesn't change the snapshot, for example a metadata operation that act on other operations.
type OperationUnmarshaler ¶
type OperationWithFiles ¶
type OperationWithFiles interface { // GetFiles return the files needed by this operation // This implies that the Operation maintain and store internally the references to those files. This is how // this information is read later, when loading from storage. // For example, an operation that has a text value referencing some files would maintain a mapping (text ref --> // hash). GetFiles() []repository.Hash }
OperationWithFiles is an optional extension for an Operation that has files dependency, stored in git.
type PGPKeyring ¶
PGPKeyring implement a openpgp.KeyRing from an slice of Key
func (PGPKeyring) DecryptionKeys ¶
func (pk PGPKeyring) DecryptionKeys() []openpgp.Key
func (PGPKeyring) KeysByIdUsage ¶
func (pk PGPKeyring) KeysByIdUsage(id uint64, requiredUsage byte) []openpgp.Key
type SetMetadataOperation ¶
type SetMetadataOperation[SnapT Snapshot] struct { OpBase Target entity.Id `json:"target"` NewMetadata map[string]string `json:"new_metadata"` }
func NewSetMetadataOp ¶
func NewSetMetadataOp[SnapT Snapshot](opType OperationType, author identity.Interface, unixTime int64, target entity.Id, newMetadata map[string]string) *SetMetadataOperation[SnapT]
func (*SetMetadataOperation[SnapT]) Apply ¶
func (op *SetMetadataOperation[SnapT]) Apply(snapshot SnapT)
func (*SetMetadataOperation[SnapT]) DoesntChangeSnapshot ¶
func (op *SetMetadataOperation[SnapT]) DoesntChangeSnapshot()
func (*SetMetadataOperation[SnapT]) Id ¶
func (op *SetMetadataOperation[SnapT]) Id() entity.Id
func (*SetMetadataOperation[SnapT]) Validate ¶
func (op *SetMetadataOperation[SnapT]) Validate() error
type Snapshot ¶
type Snapshot interface { // AllOperations returns all the operations that have been applied to that snapshot, in order AllOperations() []Operation }
Snapshot is the minimal interface that a snapshot need to implement