owldag

package
v0.0.0-...-1704659 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 3, 2023 License: GPL-3.0 Imports: 17 Imported by: 0

Documentation

Index

Constants

View Source
const MaxNodeSize = 1 << 16

Variables

This section is empty.

Functions

func AnyHasAncestor

func AnyHasAncestor(ctx context.Context, s cadata.Getter, srcs IDSet[Ref], ancRef cadata.ID) (bool, error)

AnyHasAncestor determines if any of srcs have an ancestor target. Nodes are considered to be their own ancestor

func CheckNode

func CheckNode[T any](ctx context.Context, s cadata.Getter, node Node[T]) error

CheckNode runs context independent checks on the node. CheckNode: - ensures that all the nodes which are referenced by node exist. - that the node's N is exactly 1 greater than the max of the previous nodes. - is NOT recursive. It is assumed that nodes in s are already valid.

func ForEachDesc

func ForEachDesc[T any](ctx context.Context, s cadata.Getter, ids []Ref, fn func(Ref, Node[T]) error) error

ForEachDesc traverses the DAG in descending order of N, starting with ids. Nodes with the same value of N can be visited in any order.

func ForEachDescGroup

func ForEachDescGroup[T any](ctx context.Context, s cadata.Getter, ids []Ref, fn func(uint64, []Pair[T]) error) error

ForEachDescGroup calls fn with all the nodes in the graph, reachable from ids, with a given value of N for each value of N descending down to 0.

func HasAncestor

func HasAncestor(ctx context.Context, s cadata.Getter, srcRef Ref, ancRef cadata.ID) (bool, error)

HasAncestors returns true if srcRef has ancRef as an ancestor. Nodes are considered to be their own ancestor.

Types

type ConsultFunc

type ConsultFunc = func(PeerID) bool

type DAG

type DAG[T any] struct {
	// contains filtered or unexported fields
}

func New

func New[T any](sch Scheme[T], dagStore, innerStore cadata.Store, state State[T]) *DAG[T]

New creates a new DAG using dagStore to store nodes, and passing innerStore to the underlying scheme as needed.

func (*DAG[T]) AddHead

func (d *DAG[T]) AddHead(ctx context.Context, h Head) error

AddHead adds a head from another peer.

func (*DAG[T]) CanRead

func (d *DAG[T]) CanRead(ctx context.Context, peer PeerID) (bool, error)

func (*DAG[T]) ContainsAll

func (d *DAG[T]) ContainsAll(ctx context.Context, refs []Ref) (bool, error)

func (*DAG[T]) GetEpoch

func (d *DAG[T]) GetEpoch(ctx context.Context) (*Ref, error)

func (*DAG[T]) GetHeadRefs

func (d *DAG[T]) GetHeadRefs() []Ref

func (*DAG[T]) GetHeads

func (d *DAG[T]) GetHeads() []Head

func (*DAG[T]) ListPeers

func (d *DAG[T]) ListPeers(ctx context.Context) ([]PeerID, error)

func (*DAG[T]) Modify

func (d *DAG[T]) Modify(ctx context.Context, privKey PrivateKey, fn func(s cadata.Store, x T) (*T, error)) error

Modify calls fn to modify the DAG's state.

func (*DAG[T]) Pull

func (d *DAG[T]) Pull(ctx context.Context, src cadata.Getter, h Head) error

Pull takes a head and syncs the data structure from src.

func (*DAG[T]) SaveBytes

func (d *DAG[T]) SaveBytes() []byte

func (*DAG[T]) View

func (d *DAG[T]) View() T

View returns the DAG's state.

type ErrBadN

type ErrBadN[T any] struct {
	Have, Want uint64
	Node       Node[T]
}

func (ErrBadN[T]) Error

func (e ErrBadN[T]) Error() string

type ErrNotAllowed

type ErrNotAllowed struct {
	Peer PeerID
}

func (ErrNotAllowed) Error

func (e ErrNotAllowed) Error() string

type ErrReplayedN

type ErrReplayedN struct {
	N, Last uint64
	Peer    PeerID
}

func (ErrReplayedN) Error

func (e ErrReplayedN) Error() string
type Head struct {
	Ref       Ref    `json:"ref"`
	PublicKey []byte `json:"pub_key"`
	Sig       []byte `json:"sig"`
}

Head is a signed reference to a Node in the DAG It represents a single peer's view of the DAG at the time of their last modification.

func NewHead

func NewHead(privKey PrivateKey, ref Ref) (Head, error)

func (Head) GetPeerID

func (h Head) GetPeerID() (PeerID, error)

func (Head) Verify

func (h Head) Verify() error

type IDSet

type IDSet[T ~[32]byte] []T

func Intersect

func Intersect[T ~[32]byte](a, b IDSet[T]) (ret IDSet[T])

func NewIDSet

func NewIDSet[T ~[32]byte](elems ...T) IDSet[T]

func Union

func Union[T ~[32]byte](a, b IDSet[T]) IDSet[T]

func (IDSet[T]) Add

func (s IDSet[T]) Add(x T) IDSet[T]

func (IDSet[T]) Contains

func (s IDSet[T]) Contains(x T) bool

func (IDSet[T]) IsEmpty

func (s IDSet[T]) IsEmpty() bool

func (IDSet[T]) MarshalJSON

func (s IDSet[T]) MarshalJSON() ([]byte, error)

func (IDSet[T]) Remove

func (s IDSet[T]) Remove(x T) IDSet[T]

func (*IDSet[T]) UnmarshalJSON

func (s *IDSet[T]) UnmarshalJSON(data []byte) error

type Node

type Node[T any] struct {
	N        uint64     `json:"n"`
	Previous IDSet[Ref] `json:"prevs"`

	Salt  []byte     `json:"salt,omitempty"`
	State T          `json:"state"`
	Sigs  gotkv.Root `json:"sigs"`
}

Node is a Node/Vertex in the DAG

func GetNode

func GetNode[T any](ctx context.Context, s cadata.Getter, ref Ref) (*Node[T], error)

GetNode retreives the node at ref from s

func ParseNode

func ParseNode[T any](data []byte) (*Node[T], error)

func (*Node[T]) Marshal

func (n *Node[T]) Marshal() []byte

type Pair

type Pair[T any] struct {
	ID   Ref
	Node Node[T]
}

type PeerID

type PeerID = inet256.ID

type PrivateKey

type PrivateKey = inet256.PrivateKey

type PublicKey

type PublicKey = inet256.PublicKey

type Ref

type Ref = cadata.ID

func Hash

func Hash(x []byte) (ret Ref)

func NCA

func NCA(ctx context.Context, s cadata.Getter, xs []Ref) (*Ref, error)

NCA finds the nearest common ancestor of xs

func NewRef

func NewRef[T any](e Node[T]) Ref

func PostNode

func PostNode[T any](ctx context.Context, s cadata.Poster, n Node[T]) (*Ref, error)

func RefFromBytes

func RefFromBytes(x []byte) Ref

type Scheme

type Scheme[T any] interface {
	// Validate checks that the state is valid
	Validate(ctx context.Context, s cadata.Getter, consult ConsultFunc, x T) error

	// ValidateStep checks that next is valid, given that prev is known to be valid.
	ValidateStep(ctx context.Context, s cadata.Getter, consult ConsultFunc, prev, next T) error

	Merge(ctx context.Context, s cadata.Store, xs []T) (*T, error)

	// Sync ensures that all of the data reachable by x is in dst, using src
	// to get missing data.
	Sync(ctx context.Context, src cadata.Getter, dst cadata.Store, x T) error

	CanRead(ctx context.Context, s cadata.Getter, x T, id PeerID) (bool, error)
	ListPeers(ctx context.Context, s cadata.Getter, x T) ([]PeerID, error)
}

type State

type State[T any] struct {
	Max uint64 `json:"max"`
	// Prev is the set of heads needed to reference the entire graph.
	Prev []Head `json:"prev"`

	// Heads is the root of the head for each peer.
	Heads  gotkv.Root `json:"heads"`
	Epochs []Ref      `json:"epochs"`

	X T `json:"x"`
}

State is the current state of the feed.

func InitState

func InitState[T any](ctx context.Context, s cadata.Store, x T, salt *[32]byte) (*State[T], error)

func ParseState

func ParseState[T any](data []byte) (*State[T], error)

func (State[T]) Marshal

func (s State[T]) Marshal() []byte

func (State[T]) PrevRefs

func (s State[T]) PrevRefs() IDSet[Ref]

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL