factstore

package
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: Dec 15, 2023 License: Apache-2.0 Imports: 14 Imported by: 1

Documentation

Overview

Package factstore contains the interface and a simple implementation for access to facts (atoms that are ground, i.e. contain no variables).

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrCouldNotRead is returned when the input file could not be read.
	ErrCouldNotRead = errors.New("could not read file")

	// ErrNotSupported is returned when ReadPred is called for 0-arity predicate.
	ErrNotSupported = errors.New("not supported")

	// ErrWrongArgument is returned when an argument does not make sense.
	ErrWrongArgument = errors.New("wrong argument")

	// ErrTooManyPreds is returned when a store has too many predicates.
	// The limit is unreasonably large and clients should shard their storage.
	ErrTooManyPreds = errors.New("too many preds")

	// ErrTooManyFacts is returned when a store has too many facts for a predicate.
	// The limit is unreasonably large and clients should implement a custom FactStore.
	ErrTooManyFacts = errors.New("too many facts")

	// ErrUnsupportedArity is returned when a predicate has too many arguments.
	// The limit is unreasonably large and clients should organize data differently or come
	// up with a different storage.
	ErrUnsupportedArity = errors.New("unsupported arity")
)

Functions

func Matches 

func Matches(pattern []ast.BaseTerm, args []ast.BaseTerm) bool

Matches matches a list of patterns against a list of base terms.

Types

type ConcurrentFactStore 

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

ConcurrentFactStore is an implementation of FactStore that allows multiple concurrent operations on it. The operations are protected by a read-write lock so multiple read operations like Contains or GetFacts can run concurrently, but only one write operation like Add or Merge can run at a time. Also, read operations block on running write operations. ConcurrentFactStore forwards all its operations to an underlying base FactStore.

func NewConcurrentFactStore 

func NewConcurrentFactStore(base FactStore) ConcurrentFactStore

NewConcurrentFactStore returns a new ConcurrentFactStore that wraps the given FactStore.

func (ConcurrentFactStore) Add 

func (s ConcurrentFactStore) Add(a ast.Atom) bool

Add implementation that adds to the base store after acquiring a write lock.

func (ConcurrentFactStore) Contains 

func (s ConcurrentFactStore) Contains(a ast.Atom) bool

Contains implementation that checks base store after acquiring a read lock.

func (ConcurrentFactStore) EstimateFactCount 

func (s ConcurrentFactStore) EstimateFactCount() int

EstimateFactCount returns the number of facts in the base store after acquiring a read lock.

func (ConcurrentFactStore) GetFacts 

func (s ConcurrentFactStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error

GetFacts implementation that queries the base store after acquiring a read lock.

func (ConcurrentFactStore) ListPredicates 

func (s ConcurrentFactStore) ListPredicates() []ast.PredicateSym

ListPredicates returns a list of predicates in the base store after acquiring a read lock.

func (ConcurrentFactStore) Merge 

func (s ConcurrentFactStore) Merge(other ReadOnlyFactStore)

Merge implementation that adds to the base store after acquiring a write lock.

type FactStore 

type FactStore interface {
	ReadOnlyFactStore

	// Add adds an atom to a store and returns true if the fact didn't exist before.
	Add(ast.Atom) bool

	// Merge merges contents of given store.
	Merge(ReadOnlyFactStore)
}

FactStore provides access to a set of facts.

func NewMergedStore 

func NewMergedStore[T ReadOnlyFactStore](readStores []T, writeStore FactStore) FactStore

NewMergedStore returns a new MergedStore.

type InMemoryStore 

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

InMemoryStore provides a simple implementation backed by a map from each predicate sym to a T value.

func NewInMemoryStore 

func NewInMemoryStore[T any]() InMemoryStore[T]

NewInMemoryStore constructs a new InMemoryStore.

type IndexedInMemoryStore 

type IndexedInMemoryStore struct {
	InMemoryStore[map[uint64]map[uint64]ast.Atom]
}

IndexedInMemoryStore provides a simple implementation backed by a three-level map. For each predicate sym, we have a separate map, using hash of the first argument and then hash of the entire atom.

func NewIndexedInMemoryStore 

func NewIndexedInMemoryStore() IndexedInMemoryStore

NewIndexedInMemoryStore constructs a new IndexedInMemoryStore.

func (IndexedInMemoryStore) Add 

func (s IndexedInMemoryStore) Add(a ast.Atom) bool

Add implements the FactStore interface by adding the fact to the backing map.

func (IndexedInMemoryStore) Contains 

func (s IndexedInMemoryStore) Contains(a ast.Atom) bool

Contains returns true if this store contains this atom already.

func (IndexedInMemoryStore) EstimateFactCount 

func (s IndexedInMemoryStore) EstimateFactCount() int

EstimateFactCount returns the number of facts.

func (IndexedInMemoryStore) GetFacts 

func (s IndexedInMemoryStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error

GetFacts implementation that looks up facts from an in-memory map.

func (IndexedInMemoryStore) ListPredicates 

func (s IndexedInMemoryStore) ListPredicates() []ast.PredicateSym

ListPredicates returns a list of predicates.

func (IndexedInMemoryStore) Merge 

func (s IndexedInMemoryStore) Merge(other ReadOnlyFactStore)

Merge adds all facts from other to this fact store.

type MergedStore 

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

MergedStore is an implementation of FactStore that merges multiple fact stores. It dispatches lookup requests to all of them but sending all writes to a single one. It is advisable that the read stores are disjoint, otherwise it may well happen that GetFacts will invoke the callback with a fact multiple times.

func (MergedStore) Add 

func (s MergedStore) Add(atom ast.Atom) bool

Add implementation that adds to the write store.

func (MergedStore) Contains 

func (s MergedStore) Contains(atom ast.Atom) bool

Contains implementation that checks all stores.

func (MergedStore) EstimateFactCount 

func (s MergedStore) EstimateFactCount() int

EstimateFactCount implements a FactStore method. The result is an overestimate, because facts may be stored multiple times.

func (MergedStore) GetFacts 

func (s MergedStore) GetFacts(query ast.Atom, cb func(ast.Atom) error) error

GetFacts implementation that dispatches to all stores.

func (MergedStore) ListPredicates 

func (s MergedStore) ListPredicates() []ast.PredicateSym

ListPredicates returns a merged list of predicates.

func (MergedStore) Merge 

func (s MergedStore) Merge(other ReadOnlyFactStore)

Merge forwards to writeStore.Merge

type MultiIndexedArrayInMemoryStore 

type MultiIndexedArrayInMemoryStore struct {
	InMemoryStore[map[uint16]map[uint64]map[uint64][]*ast.Atom]
	// contains filtered or unexported fields
}

MultiIndexedArrayInMemoryStore provides a simple implementation backed by a four-level map. For each predicate sym, we have a separate map, using the index and the hash of the nth argument and then hash of the entire atom, with the ultimate value being an array of Atoms.

func NewMultiIndexedArrayInMemoryStore 

func NewMultiIndexedArrayInMemoryStore() *MultiIndexedArrayInMemoryStore

NewMultiIndexedArrayInMemoryStore constructs a new MultiIndexedArrayInMemoryStore.

func (*MultiIndexedArrayInMemoryStore) Add 

func (s *MultiIndexedArrayInMemoryStore) Add(a ast.Atom) bool

Add implements the FactStore interface by adding the fact to the backing map.

func (*MultiIndexedArrayInMemoryStore) Contains 

func (s *MultiIndexedArrayInMemoryStore) Contains(a ast.Atom) bool

Contains returns true if this store contains this atom already.

func (*MultiIndexedArrayInMemoryStore) EstimateFactCount 

func (s *MultiIndexedArrayInMemoryStore) EstimateFactCount() int

EstimateFactCount returns the number of facts.

func (*MultiIndexedArrayInMemoryStore) GetFacts 

func (s *MultiIndexedArrayInMemoryStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error

GetFacts implementation that looks up facts from an in-memory map.

func (*MultiIndexedArrayInMemoryStore) ListPredicates 

func (s *MultiIndexedArrayInMemoryStore) ListPredicates() []ast.PredicateSym

ListPredicates returns a list of predicates.

func (*MultiIndexedArrayInMemoryStore) Merge 

func (s *MultiIndexedArrayInMemoryStore) Merge(other ReadOnlyFactStore)

Merge adds all facts from other to this fact store.

type MultiIndexedInMemoryStore 

type MultiIndexedInMemoryStore struct {
	InMemoryStore[map[uint16]map[uint64]map[uint64]*ast.Atom]
}

MultiIndexedInMemoryStore provides a simple implementation backed by a four-level map. For each predicate sym, we have a separate map, using the index and the hash of the nth argument and then hash of the entire atom.

func NewMultiIndexedInMemoryStore 

func NewMultiIndexedInMemoryStore() MultiIndexedInMemoryStore

NewMultiIndexedInMemoryStore constructs a new MultiIndexedInMemoryStore.

func (MultiIndexedInMemoryStore) Add 

func (s MultiIndexedInMemoryStore) Add(a ast.Atom) bool

Add implements the FactStore interface by adding the fact to the backing map.

func (MultiIndexedInMemoryStore) Contains 

func (s MultiIndexedInMemoryStore) Contains(a ast.Atom) bool

Contains returns true if this store contains this atom already.

func (MultiIndexedInMemoryStore) EstimateFactCount 

func (s MultiIndexedInMemoryStore) EstimateFactCount() int

EstimateFactCount returns the number of facts.

func (MultiIndexedInMemoryStore) GetFacts 

func (s MultiIndexedInMemoryStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error

GetFacts implementation that looks up facts from an in-memory map.

func (MultiIndexedInMemoryStore) ListPredicates 

func (s MultiIndexedInMemoryStore) ListPredicates() []ast.PredicateSym

ListPredicates returns a list of predicates.

func (MultiIndexedInMemoryStore) Merge 

func (s MultiIndexedInMemoryStore) Merge(other ReadOnlyFactStore)

Merge adds all facts from other to this fact store.

type ReadOnlyFactStore 

type ReadOnlyFactStore interface {
	// Returns a stream of facts that match a given atom. It takes a callback
	// to process results. If the callback returns an error, or it encounters
	// a malformed atom, scanning stops and that error is returned.
	GetFacts(ast.Atom, func(ast.Atom) error) error

	// Contains returns true if given atom is already present in store.
	// This is a convenience method that has a straightforward implementation
	// in terms of GetFacts. It does not return error and treats any
	// error condition as "false". Clients who distinguish "absent" from "error"
	// should call GetFacts directly.
	Contains(ast.Atom) bool

	// ListPredicates lists predicates available in this store.
	ListPredicates() []ast.PredicateSym

	// EstimateFactCount returns the estimated number of facts in the store.
	EstimateFactCount() int
}

ReadOnlyFactStore provides read access to a set of facts.

type SimpleColumn 

type SimpleColumn struct {
	// If true, write methods ensure deterministic output.
	// When reading from a factstore, the order of facts is not guaranteed
	// to be deterministic. This setting enables sorting of the facts
	// according to order determined by fact hashes.
	// If a fact store implementation returns facts in a deterministic order,
	// then it is not necessary to enable this.
	Deterministic bool
}

SimpleColumn is a file format to store a knowledge base.

The simplecolumm format is meant to provide a good enough, "batteries included" library for storing facts. SimpleColumn enforces the following limits: - not more than 2^16 predicates - not more than 2^32 facts per predicate - predicate cannot have more than 2^10 arguments

The SimpleColumnStore implements the ReadOnlyFactStore interface however it does not provide any form for indexing. Large datasets that are frequently accessed would benefit from a different store implementation or splitting up into multiple files.

For a list of predicates p_1 ... p_n, the format is as follows: line 1. <number of predicates> line 1 + i. <predicate #i name> <arity> <num facts> // i \in {1, n}

For each predicate p_i \in {1, n} that has arity > 0 and num facts > 0: 

	let m be number of p_i facts
	For each argument  j \in {1, arity(p_i)} ("column"):
    let h be the number of preceding lines: 1 + n + /preceding predicates/ + m * (j-1)
	  For each fact p_i(x_1...x_arity) with index k \in {1, m} :

line h + k: <serialized argument x_j for fact k>

Constants are base64 encoded so the file can be opened in text editor, sent over all sorts of networks, put into JSON etc. TODO: fully specify serialization format of constants for forward compatibility.

func (SimpleColumn) ReadInto 

func (sc SimpleColumn) ReadInto(r io.Reader, store FactStore) error

ReadInto reads contents in simplecolumn format into a fact store.

func (SimpleColumn) WriteTo 

func (sc SimpleColumn) WriteTo(store ReadOnlyFactStore, w io.Writer) error

WriteTo writes contents of a fact store to the writer. It only calls the ListPredicates and GetFacts methods on the store. Flushing or closing the writer is is the caller's responsibility.

type SimpleColumnStore 

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

SimpleColumnStore is a read-only fact store backed by a simple column file.

func NewSimpleColumnStore 

func NewSimpleColumnStore(input func() (io.ReadCloser, error)) (*SimpleColumnStore, error)

NewSimpleColumnStore returns a new fact store backed by a simple column file. The input closure is called immediately to parse the header.

func NewSimpleColumnStoreFromBytes 

func NewSimpleColumnStoreFromBytes(data []byte) (*SimpleColumnStore, error)

NewSimpleColumnStoreFromBytes returns a new fact store backed by data in simplecolumn format.

func NewSimpleColumnStoreFromGzipBytes 

func NewSimpleColumnStoreFromGzipBytes(data []byte) (*SimpleColumnStore, error)

NewSimpleColumnStoreFromGzipBytes returns a new fact store backed by data that is a gzipped file in simplecolumn format.

func (*SimpleColumnStore) Contains 

func (s *SimpleColumnStore) Contains(fact ast.Atom) bool

Contains implements a ReadOnlyFactStore method.

func (*SimpleColumnStore) EstimateFactCount 

func (s *SimpleColumnStore) EstimateFactCount() int

EstimateFactCount implements a ReadOnlyFactStore method.

func (*SimpleColumnStore) GetFacts 

func (s *SimpleColumnStore) GetFacts(query ast.Atom, cb func(ast.Atom) error) error

GetFacts implements a ReadOnlyFactStore method.

func (*SimpleColumnStore) ListPredicates 

func (s *SimpleColumnStore) ListPredicates() []ast.PredicateSym

ListPredicates implements a ReadOnlyFactStore method.

type SimpleInMemoryStore 

type SimpleInMemoryStore struct {
	InMemoryStore[map[uint64]ast.Atom]
}

SimpleInMemoryStore provides a simple implementation backed by a two-level map. For each predicate sym, we have a separate map, using numeric hash as key.

func NewSimpleInMemoryStore 

func NewSimpleInMemoryStore() SimpleInMemoryStore

NewSimpleInMemoryStore constructs a new SimpleInMemoryStore.

func (SimpleInMemoryStore) Add 

func (s SimpleInMemoryStore) Add(a ast.Atom) bool

Add implements the FactStore interface by adding the fact to the backing map.

func (SimpleInMemoryStore) Contains 

func (s SimpleInMemoryStore) Contains(a ast.Atom) bool

Contains returns true if this store contains this atom already.

func (SimpleInMemoryStore) EstimateFactCount 

func (s SimpleInMemoryStore) EstimateFactCount() int

EstimateFactCount returns the number of facts.

func (SimpleInMemoryStore) GetFacts 

func (s SimpleInMemoryStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error

GetFacts implementation that looks up facts from an in-memory map.

func (SimpleInMemoryStore) ListPredicates 

func (s SimpleInMemoryStore) ListPredicates() []ast.PredicateSym

ListPredicates returns a list of predicates.

func (SimpleInMemoryStore) Merge 

func (s SimpleInMemoryStore) Merge(other ReadOnlyFactStore)

Merge adds all facts from other to this fact store.

func (SimpleInMemoryStore) String 

func (s SimpleInMemoryStore) String() string

String returns a readable debug string for this store.

type TeeingStore 

type TeeingStore struct {
	Out FactStore
	// contains filtered or unexported fields
}

TeeingStore is an implementation of FactStore that directs all writes to an output store, while distributing reads over a read-only base store and the output store.

func NewTeeingStore 

func NewTeeingStore(base FactStore) TeeingStore

NewTeeingStore returns a new TeeingStore.

func (TeeingStore) Add 

func (s TeeingStore) Add(atom ast.Atom) bool

Add implementation that adds to the output store.

func (TeeingStore) Contains 

func (s TeeingStore) Contains(atom ast.Atom) bool

Contains implementation that checks both stores.

func (TeeingStore) EstimateFactCount 

func (s TeeingStore) EstimateFactCount() int

EstimateFactCount returns the number of facts. The real number can be lower in case of duplicates.

func (TeeingStore) GetFacts 

func (s TeeingStore) GetFacts(query ast.Atom, cb func(ast.Atom) error) error

GetFacts implementation that queries both stores.

func (TeeingStore) ListPredicates 

func (s TeeingStore) ListPredicates() []ast.PredicateSym

ListPredicates returns a list of predicates.

func (TeeingStore) Merge 

func (s TeeingStore) Merge(other ReadOnlyFactStore)

Merge implementation that adds to the output store.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.