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 ¶
- Variables
- func GetAllFacts(fs FactStore, fn func(ast.Atom) error) error
- func Matches(pattern []ast.BaseTerm, args []ast.BaseTerm) bool
- type ConcurrentFactStore
- func (s ConcurrentFactStore) Add(a ast.Atom) bool
- func (s ConcurrentFactStore) Contains(a ast.Atom) bool
- func (s ConcurrentFactStore) EstimateFactCount() int
- func (s ConcurrentFactStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error
- func (s ConcurrentFactStore) ListPredicates() []ast.PredicateSym
- func (s ConcurrentFactStore) Merge(other ReadOnlyFactStore)
- func (s ConcurrentFactStore) Remove(a ast.Atom) bool
- type FactStore
- type FactStoreWithRemove
- type InMemoryStore
- type IndexedInMemoryStore
- func (s IndexedInMemoryStore) Add(a ast.Atom) bool
- func (s IndexedInMemoryStore) Contains(a ast.Atom) bool
- func (s IndexedInMemoryStore) EstimateFactCount() int
- func (s IndexedInMemoryStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error
- func (s IndexedInMemoryStore) ListPredicates() []ast.PredicateSym
- func (s IndexedInMemoryStore) Merge(other ReadOnlyFactStore)
- func (s IndexedInMemoryStore) Remove(a ast.Atom) bool
- type MergedStore
- func (s MergedStore) Add(atom ast.Atom) bool
- func (s MergedStore) Contains(atom ast.Atom) bool
- func (s MergedStore) EstimateFactCount() int
- func (s MergedStore) GetFacts(query ast.Atom, cb func(ast.Atom) error) error
- func (s MergedStore) ListPredicates() []ast.PredicateSym
- func (s MergedStore) Merge(other ReadOnlyFactStore)
- type MultiIndexedArrayInMemoryStore
- func (s *MultiIndexedArrayInMemoryStore) Add(a ast.Atom) bool
- func (s *MultiIndexedArrayInMemoryStore) Contains(a ast.Atom) bool
- func (s *MultiIndexedArrayInMemoryStore) EstimateFactCount() int
- func (s *MultiIndexedArrayInMemoryStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error
- func (s *MultiIndexedArrayInMemoryStore) ListPredicates() []ast.PredicateSym
- func (s *MultiIndexedArrayInMemoryStore) Merge(other ReadOnlyFactStore)
- func (s *MultiIndexedArrayInMemoryStore) Remove(a ast.Atom) bool
- type MultiIndexedInMemoryStore
- func (s MultiIndexedInMemoryStore) Add(a ast.Atom) bool
- func (s MultiIndexedInMemoryStore) Contains(a ast.Atom) bool
- func (s MultiIndexedInMemoryStore) EstimateFactCount() int
- func (s MultiIndexedInMemoryStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error
- func (s MultiIndexedInMemoryStore) ListPredicates() []ast.PredicateSym
- func (s MultiIndexedInMemoryStore) Merge(other ReadOnlyFactStore)
- func (s MultiIndexedInMemoryStore) Remove(a ast.Atom) bool
- type ReadOnlyFactStore
- type SimpleColumn
- type SimpleColumnStore
- type SimpleInMemoryStore
- func (s SimpleInMemoryStore) Add(a ast.Atom) bool
- func (s SimpleInMemoryStore) Contains(a ast.Atom) bool
- func (s SimpleInMemoryStore) EstimateFactCount() int
- func (s SimpleInMemoryStore) GetFacts(a ast.Atom, fn func(ast.Atom) error) error
- func (s SimpleInMemoryStore) ListPredicates() []ast.PredicateSym
- func (s SimpleInMemoryStore) Merge(other ReadOnlyFactStore)
- func (s SimpleInMemoryStore) Remove(a ast.Atom) bool
- func (s SimpleInMemoryStore) String() string
- type TeeingStore
- func (s TeeingStore) Add(atom ast.Atom) bool
- func (s TeeingStore) Contains(atom ast.Atom) bool
- func (s TeeingStore) EstimateFactCount() int
- func (s TeeingStore) GetFacts(query ast.Atom, cb func(ast.Atom) error) error
- func (s TeeingStore) ListPredicates() []ast.PredicateSym
- func (s TeeingStore) Merge(other ReadOnlyFactStore)
- func (s TeeingStore) Remove(atom ast.Atom) bool
Constants ¶
This section is empty.
Variables ¶
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 GetAllFacts ¶ added in v0.2.0
GetAllFacts streams all facts in a store.
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 FactStoreWithRemove) 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 ¶
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 a fact to the store and returns true if it 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 FactStoreWithRemove ¶ added in v0.2.0
type FactStoreWithRemove interface { FactStore // Removes a fact from the store and returns true if that fact was present. Remove(ast.Atom) bool }
FactStoreWithRemove is a FactStore that supports fact removal.
This low-level functionality is intended to be used by the engine, to be invoked for facts that can be removed safely.
If this factstore contains the result of evaluating rules, beware that removing a fact may lose the property that all facts are either from the extensional database or consequences of applying rules.
Also, implementations that are backed by readonly store may not properly support removing facts from those stores.
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 ¶
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. MergedStore supports Remove for its write store.
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) 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 ¶
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 ¶
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 ¶
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) 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 ¶
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) Remove ¶ added in v0.2.0
func (s SimpleInMemoryStore) Remove(a ast.Atom) bool
Remove removes the fact from the backing map.
func (SimpleInMemoryStore) String ¶
func (s SimpleInMemoryStore) String() string
String returns a readable debug string for this store.
type TeeingStore ¶
type TeeingStore struct { Out FactStoreWithRemove // 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) 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.