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 ¶
- Constants
- 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 DirectoryReader
- func (r *DirectoryReader) LookupEntry(dir key.Key, name []byte) (Entry, error)
- func (r *DirectoryReader) ResolveEntry(root key.Key, path string) (*Entry, error)
- func (r *DirectoryReader) ResolvePath(root key.Key, path string) (key.Key, error)
- func (r *DirectoryReader) WriteContent(w io.Writer, k key.Key) error
- type DirectoryReaderOption
- 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 Link
- type MissingObjectError
- type Object
Constants ¶
const DefaultDirectoryReaderCapacity = 4096
DefaultDirectoryReaderCapacity is the capacity of a DirectoryReader made without WithCapacity, in directory objects.
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 leaves (Blob and XattrSet objects, and git blobs a tree or tag says are blobs: see Links) 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. A git object's children are what git follows from it (gitobj.Links).
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; objects known to be leaves are not fetched: Blob and XattrSet objects, and git blobs a tree or tag says are blobs (Links).
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 DirectoryReader ¶ added in v0.0.12
type DirectoryReader struct {
// contains filtered or unexported fields
}
DirectoryReader answers LookupEntry, ResolveEntry and ResolvePath as the functions of those names do, with the same results and the same errors, and keeps each directory object it decodes. The functions decode every directory object on the path at each call; a reader decodes it once, so it suits a walk of many paths in one tree. Its getter must return the same content for a key every time, as for LookupEntry.
A reader holds at most its capacity of decoded directory objects; when full, it drops the least recently used half, so most misses pay nothing for the bound. It also holds at most its capacity of commit-to-tree answers (DirOf), all dropped when full. A hit does not read the object again, so the reader can answer for objects that gc removed after it decoded them: keep one for a bounded operation.
A DirectoryReader is not safe for concurrent use: every call changes what it holds, a hit too, and it takes no lock. Give each goroutine its own, or guard a shared one with a mutex. The entries it returns are the caller's, as the functions' are: they share no memory with what the reader holds.
func NewDirectoryReader ¶ added in v0.0.12
func NewDirectoryReader(get func(key.Key) ([]byte, error), opts ...DirectoryReaderOption) *DirectoryReader
NewDirectoryReader returns a DirectoryReader that fetches the bytes stored under a key with get. It holds DefaultDirectoryReaderCapacity directory objects unless WithCapacity says otherwise.
func (*DirectoryReader) LookupEntry ¶ added in v0.0.12
LookupEntry returns the entry called name in the directory object dir, as the function LookupEntry does. dir may be the key of a Commit.
func (*DirectoryReader) ResolveEntry ¶ added in v0.0.12
ResolveEntry descends from the directory object root along the slash-separated path and returns the entry the final component names, nil for the root itself, as the function ResolveEntry does.
func (*DirectoryReader) ResolvePath ¶ added in v0.0.12
ResolvePath descends from the directory object root along the slash-separated path and returns the content key of the directory entry it names, as the function ResolvePath does.
func (*DirectoryReader) WriteContent ¶ added in v0.0.12
WriteContent writes the regular-file content addressed by k to w, as the function WriteContent does, reading through the reader's getter. The reader keeps none of it.
type DirectoryReaderOption ¶ added in v0.0.12
type DirectoryReaderOption func(*DirectoryReader)
DirectoryReaderOption configures a DirectoryReader as it is made.
func WithCapacity ¶ added in v0.0.12
func WithCapacity(n int) DirectoryReaderOption
WithCapacity sets how many decoded directory objects a DirectoryReader holds, and how many commit-to-tree answers. Less than 1 is taken as 1.
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 Link ¶ added in v0.11.0
Link is one object's reference to another, with what a walk may skip: a Leaf has no children, so it is counted without being read.
func LinkTo ¶ added in v0.11.0
LinkTo is the link to a root, which no object refers to: all that is known of it is what its key says. A Blob or XattrSet key says it is a leaf. A git key says nothing of the kind: it holds a SHA-1 alone, and a blob and a commit look the same.
func Links ¶ added in v0.11.0
Links returns what ChildKeys returns, with each child's Leaf set. A child's own key tells for the store's own types. For a git object the referring object tells: a tree entry's mode or a tag's type line says which targets are blobs.
That is a claim, and two links can disagree: one tree entry may call an object a file and another call it a directory. A walk must therefore not prune on a key it has seen only through a Leaf link, or it passes over what the other link reaches. See visits.
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