Documentation
¶
Overview ¶
Package fstree encodes the Amber-Store filesystem tree objects (FileNode, DirLeaf, DirNode, XattrSet, Blob) as deterministic CBOR per architecture/fstree.md, and builds files and directories bottom-up by streaming. See architecture/types.md for the length-field semantics.
The object-graph walks (ChildKeys, ReachableKeys, CheckComplete) also follow Commit objects (package commit), whose children are their trees — one, or every side of a conflict — and their parent commits. The directory readers take a commit for the directory it records (dirof.go).
Index ¶
- Variables
- func CheckComplete(root key.Key, get func(key.Key) ([]byte, error), ...) ([]key.Key, error)
- func ChildKeys(k key.Key, data []byte) ([]key.Key, error)
- func DecodeFileNode(b []byte) ([]key.Key, error)
- func DirOf(k key.Key, get func(key.Key) ([]byte, error)) (key.Key, error)
- func ReachableKeys(root key.Key, get func(key.Key) ([]byte, error)) ([]key.Key, error)
- func ResolvePath(root key.Key, path string, get func(key.Key) ([]byte, error)) (key.Key, error)
- func WriteContent(w io.Writer, k key.Key, get func(key.Key) ([]byte, error)) error
- type DirBuilder
- type DirPair
- type Emit
- type Entry
- func CollectEntries(k key.Key, get func(key.Key) ([]byte, error)) ([]Entry, error)
- func DecodeDirLeaf(b []byte) ([]Entry, error)
- func ListEntries(dir key.Key, after []byte, limit int, get func(key.Key) ([]byte, error)) ([]Entry, bool, error)
- func LookupEntry(dir key.Key, name []byte, get func(key.Key) ([]byte, error)) (Entry, error)
- func ResolveEntry(root key.Key, path string, get func(key.Key) ([]byte, error)) (*Entry, error)
- type IndexBuilder
- type MissingObjectError
- type Object
Constants ¶
This section is empty.
Variables ¶
var ErrNotDir = errors.New("not a directory")
ErrNotDir reports a path component that exists but is not a directory.
var ErrNotFound = errors.New("entry not found")
ErrNotFound reports a path component that does not exist in its directory.
Functions ¶
func CheckComplete ¶
func CheckComplete(root key.Key, get func(key.Key) ([]byte, error), has func(key.Key) (bool, error), jobs int) ([]key.Key, error)
CheckComplete verifies that every object reachable from root exists and returns the visited keys — root first, then discovery order, each once. The tree is walked breadth-first, checking each level's objects with up to jobs concurrent lookups (jobs <= 0 means GOMAXPROCS): interior nodes are read with get — a failed read surfaces as the wrapped get error — and Blob and XattrSet leaves are tested with has — an absent leaf surfaces as a *MissingObjectError. On error the visited list is nil.
func ChildKeys ¶
ChildKeys returns the keys directly referenced by the object with key k and serialized bytes data, in encounter order. Blob and XattrSet objects are leaves and have no children. A Commit's children are its tree, the further terms of a conflicted tree, then its parents, all in recorded order — so every walk built on ChildKeys follows history and keeps every side of a conflict. A DirLeaf's children are its entries' content keys whatever their type, so a directory entry that holds a Commit is followed too.
func DecodeFileNode ¶
DecodeFileNode decodes a FileNode body (a CBOR array of child keys) into its child keys, in file order. The inverse of EncodeFileNode.
func DirOf ¶ added in v0.0.10
DirOf returns the directory object k stands for: k itself when it is a DirLeaf or DirNode, the tree of the commit when it is a Commit. get fetches the bytes stored under a key.
func ReachableKeys ¶
ReachableKeys returns the keys of every object reachable from root — the set that must be transferred to hold the whole content — with root first and the remaining keys in unspecified order (callers must not rely on any ordering beyond root-first), each key listed once even when referenced repeatedly. root may be any object type. get fetches the bytes stored under a key; Blob and XattrSet objects are leaves and are not fetched.
The walk is a breadth-first sweep that fetches each round's frontier concurrently (bounded by GOMAXPROCS), so a wide tree of small objects is read in parallel. The current implementation happens to be deterministic — results are indexed by frontier position — but that is not part of the contract. get must be safe for concurrent use.
func ResolvePath ¶
ResolvePath descends from the directory object root along the slash-separated path and returns the content key of the directory entry it names, as stored: a DirLeaf or DirNode key, or the key of a Commit that stands for its tree (DirOf), which every reader here takes. Empty components and "." are ignored, so "", ".", and paths with leading/trailing slashes are accepted; ".." is rejected (a CAS tree has no parent links). A missing component wraps ErrNotFound, a non-directory component wraps ErrNotDir.
Types ¶
type DirBuilder ¶
type DirBuilder struct {
// contains filtered or unexported fields
}
DirBuilder builds one directory's prolly tree by streaming its entries (which the caller supplies already sorted bytewise by name). It chunks entries into DirLeaf objects and promotes their keys through a DirNode index. Objects are emitted children-before-parents; the directory root is emitted last.
func NewDirBuilder ¶
func NewDirBuilder(ic chunkers.ItemChunker) *DirBuilder
NewDirBuilder returns a DirBuilder using ic for both the entry stream and the DirNode index stream.
type DirPair ¶
DirPair is one [sepName, childKey] element of a DirNode, encoded as a 2-element CBOR array of byte strings.
func DecodeDirNode ¶
DecodeDirNode decodes a DirNode body (a CBOR array of [sepName, childKey] pairs) into its pairs, in sepName order. The inverse of EncodeDirNode.
type Emit ¶
Emit is called once per built object, in children-before-parents order. The consumer (the pack driver) is responsible for writing the object to the sink.
type Entry ¶
type Entry struct {
Name []byte `cbor:"0,keyasint"`
Mode uint64 `cbor:"1,keyasint"` // raw POSIX st_mode (type + perms)
UID uint64 `cbor:"2,keyasint"`
GID uint64 `cbor:"3,keyasint"`
Mtime int64 `cbor:"4,keyasint"` // ns since the Unix epoch (may be negative)
ContentKey []byte `cbor:"5,keyasint,omitempty"` // S_IFREG / S_IFDIR
LinkTarget []byte `cbor:"6,keyasint,omitempty"` // S_IFLNK
Rdev []uint64 `cbor:"7,keyasint,omitempty"` // S_IFCHR / S_IFBLK: [major, minor]
XattrsIn cbor.RawMessage `cbor:"8,keyasint,omitempty"` // inline xattrs (pre-encoded bstr map)
XattrsKey []byte `cbor:"9,keyasint,omitempty"` // spilled XattrSet key
}
Entry is a single directory entry, encoded as a canonical CBOR map with integer keys 0-9 (architecture/fstree.md, DirLeaf). Fields are declared in ascending key order so the encoding is canonical. Required keys (0-4) are never omitempty because uid/gid/mtime/mode are legitimately zero. The payload keys 5-9 are mutually constrained by the caller per the entry's type.
func CollectEntries ¶
CollectEntries returns the directory entries reachable from k, descending DirNode index levels into the DirLeaves that hold them. Entries are returned in name order (the order the leaves store them). get fetches the bytes stored under a key.
Names must strictly increase across leaves. This also stops a pushed DAG whose DirNodes repeat one child from expanding multiplicatively.
func DecodeDirLeaf ¶
DecodeDirLeaf decodes a DirLeaf body (a CBOR array of entry maps) into its entries, in name order. The inverse of EncodeDirLeaf.
func ListEntries ¶
func ListEntries(dir key.Key, after []byte, limit int, get func(key.Key) ([]byte, error)) ([]Entry, bool, error)
ListEntries returns up to limit entries of the directory object dir whose names sort strictly after `after` (nil or empty lists from the start), in name order, and whether more such entries follow. When more is true the returned page is full: len(entries) == limit. It descends only the subtrees that can hold qualifying names — a DirNode pair is skipped when its SepName (the subtree's greatest name) is not after `after` — touching O(log n + limit) objects. limit must be positive.
func LookupEntry ¶
LookupEntry returns the entry called name in the directory object dir. It descends DirNode levels by binary search over each pair's SepName (the greatest entry name in that child's subtree), then scans the one DirLeaf that could hold the name — O(log n) objects for an n-entry directory. A missing name wraps ErrNotFound; get fetches the bytes stored under a key. dir may be the key of a Commit, which stands for its tree (DirOf).
func ResolveEntry ¶
ResolveEntry descends from the directory object root along the slash-separated path and returns the entry the final component names — of any kind (file, directory, symlink, device, …), carrying its metadata. The empty path (or chains of "" and ".") returns nil: the root directory is not an entry and has no metadata of its own. Intermediate components must name directories (ErrNotDir otherwise); a missing component wraps ErrNotFound; ".." is rejected.
type IndexBuilder ¶
type IndexBuilder struct {
// contains filtered or unexported fields
}
IndexBuilder builds the index levels above a leaf level by streaming child references and item-chunking them into FileNode (files) or DirNode (dirs) objects, level by level, until one object remains (the root). Objects are emitted children-before-parents; the root is emitted last. Memory is O(levels x MaxRun) — it never holds a whole level's bytes.
func NewFileIndexBuilder ¶
func NewFileIndexBuilder(ic chunkers.ItemChunker) *IndexBuilder
NewFileIndexBuilder builds FileNode levels over Blob/FileNode child keys.
func (*IndexBuilder) AddChild ¶
AddChild adds one leaf-level child reference. sep is the child subtree's greatest entry name for directory indexes, and is ignored for file indexes.
func (*IndexBuilder) Finish ¶
func (ib *IndexBuilder) Finish(emit Emit) (key.Key, error)
Finish collapses all open runs bottom-up and returns the root key. The single object that reaches the top with no parent is the root; a single child is returned without wrapping it in a degenerate one-child node.
type MissingObjectError ¶
MissingObjectError reports a leaf object found absent by CheckComplete.
func (*MissingObjectError) Error ¶
func (e *MissingObjectError) Error() string
type Object ¶
Object is a built CAS object: its key and its serialized bytes.
func EncodeBlob ¶
EncodeBlob wraps raw file-content bytes as a Blob object (no CBOR framing).
func EncodeDirLeaf ¶
EncodeDirLeaf encodes a run of directory entries (already sorted by name) as a CBOR array of entry maps. Its length field is its own serialized bytes plus the content-key length of each regular-file/directory entry plus the xattrs-key length of each entry whose xattrs were spilled to an XattrSet.
func EncodeDirNode ¶
EncodeDirNode encodes a directory index node as a CBOR array of [sepName, childKey] pairs (sorted by sepName). Its length field is its own serialized bytes plus the cumulative length of every child.
func EncodeFileNode ¶
EncodeFileNode encodes a file index node: a CBOR array of child keys. Its length field is the sum of child content sizes (excludes its own bytes).
Source Files