arctable

Documentation

Overview

Package arctable defines the Explicit Arc Table interface and implementations. ArcTable is an internal component for fast lookup of arc targets. It provides NO correctness guarantee; verification belongs to the semantic layer and its commitment backend.

Package arctable provides the Explicit Arc Table (ArcTable) abstraction. This file contains common utilities and interfaces shared by ArcTable implementations.

Index

• func DefaultArcKey(namespace string, path arcset.Path) []byte
• func DefaultNamespacePrefix(namespace string) []byte
• func IsNotFound(err error) bool
• func RootKeyFormat(root cid.Cid) []byte
• func VersionedArcKey(namespace string, version cid.Cid, path arcset.Path) []byte
• func VersionedNamespacePrefix(namespace string, version cid.Cid) []byte
• type ArcTable
• type BloomFilterManager
  • func NewBloomFilterManager(bloomCache *bloom.BloomCache) *BloomFilterManager
  • func (bfm *BloomFilterManager) AddBatch(ctx context.Context, namespace string, paths []string) error
  • func (bfm *BloomFilterManager) CreateNamespace(ctx context.Context, namespace string, cfg *bloom.NamespaceConfig) error
  • func (bfm *BloomFilterManager) Delete(ctx context.Context, namespace, path string) error
  • func (bfm *BloomFilterManager) Enabled() bool
  • func (bfm *BloomFilterManager) GetBloomCache() *bloom.BloomCache
  • func (bfm *BloomFilterManager) Insert(ctx context.Context, namespace, path string) error
  • func (bfm *BloomFilterManager) MightContain(namespace, path string) bool
  • func (bfm *BloomFilterManager) MightContainBatch(ctx context.Context, namespace string, paths []string) (map[string]bool, error)
• type BranchingArcTable
• type NamespaceCreator

Functions

func DefaultArcKey

func DefaultArcKey(namespace string, path arcset.Path) []byte

DefaultArcKey generates the standard arc key format. Used by overwrite ArcTable implementation.

func DefaultNamespacePrefix

func DefaultNamespacePrefix(namespace string) []byte

DefaultNamespacePrefix generates the standard namespace prefix format. Used by overwrite ArcTable implementation.

func IsNotFound

func IsNotFound(err error) bool

IsNotFound checks if an error represents an arc-not-found condition. It covers both arctable and arcset not-found errors.

func RootKeyFormat

func RootKeyFormat(root cid.Cid) []byte

RootKeyFormat generates the key for root->namespace mapping. This is shared across all ArcTable implementations.

func VersionedArcKey

func VersionedArcKey(namespace string, version cid.Cid, path arcset.Path) []byte

VersionedArcKey generates a versioned arc key format. Used by versioned ArcTable implementation to include version information.

func VersionedNamespacePrefix

func VersionedNamespacePrefix(namespace string, version cid.Cid) []byte

VersionedNamespacePrefix generates a versioned namespace prefix format. Used by versioned ArcTable implementation to include version information.

Types

type ArcTable

type ArcTable interface {
	// Get retrieves the target CID for (namespace, root, path).
	// namespace is the namespace for the arc set.
	// For overwrite ArcTable: root is optional (cid.Undef skips validation).
	// For versioned ArcTable: root is the version to start the chain lookup.
	// Returns ErrNotFound if not found.
	Get(ctx context.Context, namespace string, root cid.Cid, path arcset.Path) (cid.Cid, error)

	// BatchGet retrieves multiple target CIDs in a single operation.
	// Returns a map of path -> CID for paths that were found.
	// Paths not found are omitted from the result map (no error).
	BatchGet(ctx context.Context, namespace string, root cid.Cid, paths []arcset.Path) (map[arcset.Path]cid.Cid, error)

	// Update stores arc entries with a new commitment root.
	// namespace is the namespace for the arc set.
	// For overwrite ArcTable: oldRoot mappings are invalidated, data is overwritten.
	// For versioned ArcTable: newRoot is linked to parentRoot via @previous.
	// Use cid.Undef for oldRoot/parentRoot for the first version.
	// If a target CID is cid.Undef, the corresponding arc is deleted.
	Update(ctx context.Context, namespace string, newRoot, oldRoot cid.Cid, arcs arcset.ArcSet) error

	// Snapshot returns an immutable snapshot of all arcs for a given root.
	// The snapshot preloads all data into memory, suitable for random access.
	// For overwrite ArcTable: root is optional (cid.Undef skips validation).
	// For versioned ArcTable: includes all ancestor arcs via @previous chain.
	Snapshot(ctx context.Context, namespace string, root cid.Cid) (arcset.ArcSet, error)

	// Iterate returns a streaming iterator over arcs for a given root.
	// For overwrite ArcTable: root is optional (cid.Undef skips validation).
	// For versioned ArcTable: root is the version to iterate (walks @previous chain).
	// Caller must call Close() on the iterator when done.
	Iterate(ctx context.Context, namespace string, root cid.Cid) arcset.Iterator

	// Close releases resources.
	Close() error
}

ArcTable (Explicit Arc Table) stores arc entries for fast lookup. It maps (namespace, path) -> target CID. namespace provides namespace isolation for different graphs. Both versioned and non-versioned implementations share this interface.

type BloomFilterManager

type BloomFilterManager struct {
	// contains filtered or unexported fields
}

BloomFilterManager provides unified bloom filter management across ArcTable implementations.

func NewBloomFilterManager

func NewBloomFilterManager(bloomCache *bloom.BloomCache) *BloomFilterManager

NewBloomFilterManager creates a new bloom filter manager.

func (*BloomFilterManager) AddBatch

func (bfm *BloomFilterManager) AddBatch(ctx context.Context, namespace string, paths []string) error

AddBatch adds multiple paths to the bloom filter at once.

func (*BloomFilterManager) CreateNamespace

func (bfm *BloomFilterManager) CreateNamespace(ctx context.Context, namespace string, cfg *bloom.NamespaceConfig) error

CreateNamespace creates a new namespace with custom bloom configuration.

func (*BloomFilterManager) Delete

func (bfm *BloomFilterManager) Delete(ctx context.Context, namespace, path string) error

Delete records that a path no longer exists in the bloom filter. Note: BloomCache does not support path deletion, only namespace-level operations. This is a no-op to maintain interface consistency.

func (*BloomFilterManager) Enabled

func (bfm *BloomFilterManager) Enabled() bool

Enabled returns whether bloom filter is enabled.

func (*BloomFilterManager) GetBloomCache

func (bfm *BloomFilterManager) GetBloomCache() *bloom.BloomCache

GetBloomCache returns the underlying BloomCache for advanced operations. This is intended for internal use by ArcTable implementations that need direct access.

func (*BloomFilterManager) Insert

func (bfm *BloomFilterManager) Insert(ctx context.Context, namespace, path string) error

Insert records that a path exists in the bloom filter.

func (*BloomFilterManager) MightContain

func (bfm *BloomFilterManager) MightContain(namespace, path string) bool

Checker checks if a path might exist in the cache using bloom filter.

func (*BloomFilterManager) MightContainBatch

func (bfm *BloomFilterManager) MightContainBatch(ctx context.Context, namespace string, paths []string) (map[string]bool, error)

MightContainBatch checks multiple paths at once using bloom filter.

type BranchingArcTable

type BranchingArcTable interface {
	SupportsConcurrentBranches() bool
}

BranchingArcTable may be implemented by ArcTable backends that preserve multiple concurrent children from the same parent root.

Writers can skip stale-root guards for backends that report support for concurrent branches.

type NamespaceCreator

type NamespaceCreator interface {
	// CreateNamespace creates a new namespace with custom bloom configuration.
	// If cfg is nil, default configuration is used.
	CreateNamespace(ctx context.Context, namespace string, cfg *bloom.NamespaceConfig) error
}

NamespaceCreator is an optional interface for ArcTable implementations that support creating namespaces with custom bloom filter configuration.