1 unstable release
0.0.0 | Sep 22, 2024 |
---|
#27 in #triple
192 downloads per month
30KB
453 lines
Karmeliet
Karmeliet is an experimental, in-memory, statically-typed triple store. It's currently missing many features, and is therefore not recommended for use.
See the documentation for examples.
lib.rs
:
Karmeliet is an experimental, in-memory, statically-typed triple store. It's currently missing many features, and is therefore not recommended for use.
A triple store is a database that stores triples (subject, attribute, value)
.
In Karmeliet, subjects are unique IDs called "entities", attributes are Rust
types, and values are instances of those types.
Differences from other triple stores
Karmeliet is strongly-typed. You can think of it as having a strict schema on the columns of a database. In that sense, it is closer to e.g. Datomic than to Datascript.
Unlike most triple stores out there, Karmeliet is quite bare-bones, and does almost no work for you. For example, Datomic will compute several different indexes to make certain queries faster. Karmeliet does no such thing, and instead leaves it up to the user to build indexes via insertion and removal hooks. Currently, it also provides no declarative query API, which means the user must query data by mapping and filtering over Rust iterators. This might change in the future.
This is a sort of "rusty" trade-off. By being strict about types and not computing any indexes, Karmeliet can enjoy better performance than alternatives, and allows the user to model their domain more precisely. In exchange, it makes the database less flexible and requires more boilerplate to use efficiently.
Basic usage
Here's an example of using Karmeliet to store books in a simple database. It shows the basic API of the crate, but doesn't use any hooks.
use karmeliet::Store;
struct Book {
title: &'static str,
year: u16,
}
// Initialize an empty store
let mut store = Store::default();
// Create a new entity
let psalm = store.entity();
// Attach an attribute to that entity
store.insert(
psalm,
Book {
title: "A Plasm for the Wild-Built",
year: 2021,
},
);
// Retrieve that attribute
assert_eq!(
store.get::<Book>(psalm).unwrap().title,
"A Plasm for the Wild-Built"
);
// Create a few other entities
let song = store.entity();
store.insert(
song,
Book {
title: "The Song of Achilles",
year: 2011,
},
);
let circe = store.entity();
store.insert(
circe,
Book {
title: "Circe",
year: 2018,
},
);
// Iterate over entities with a `Book` attribute
let mut books: Vec<_> = store.iter::<Book>().collect();
books.sort_unstable_by_key(|(_, book)| &book.year);
assert_eq!(books[0].0, song);
assert_eq!(books[1].0, circe);
assert_eq!(books[2].0, psalm);
// Insert a second attribute on an entity
struct CurrentlyReading;
store.insert(circe, CurrentlyReading);
// Find the `Book` with `CurrentlyReading` attribute
let book = store
.iter::<CurrentlyReading>()
.find_map(|(entity, _)| store.get::<Book>(entity));
assert_eq!(book.unwrap().title, "Circe");
// Remove that attribute
store.remove::<CurrentlyReading>(circe);
// There's no longer a book with `CurrentlyReading`
let book = store
.iter::<CurrentlyReading>()
.find_map(|(entity, _)| store.get::<Book>(entity));
assert!(book.is_none());
Using hooks to maintain indexes
Karmeliet only provides fast, O(log N) access when querying an
(entity, attribute)
pair, or when accessing a range of entities with a
specific attribute. If you need to query data by value, you'll have to iterate
over every (entity, attribute)
pair and keep only the ones that match.
This can be good enough, especially when prototyping. However, if you find that a specific query is too slow, then you might benefit from building an index to speed it up. This can be done with insertion and removal hooks, which are functions that run when attributes are inserted, removed, or updated.
In the following example, we use a hook to build a sorted map from year to entity, which can be used to query the range of all books published in a specific year, as well as just generally querying a range of books pre-sorted by year.
use std::collections::BTreeSet;
use karmeliet::{Entity, Store};
struct Book {
title: &'static str,
year: u16,
}
#[derive(Default)]
struct YearBooks {
index: BTreeSet<(u16, Entity)>,
}
let mut store = Store::default();
// Setup insert and remove hooks
store.hook_before_insert(|store, entity, book: &Book| {
// We store the index as an attribute on the entity `SINGLETON`, which
// exists for this exact purpose.
// `upsert` will create the attribute if it's missing.
store.upsert(Entity::SINGLETON, |YearBooks { index }| {
index.insert((book.year, entity));
});
});
store.hook_after_remove(|store, entity, book: &Book| {
store.upsert(Entity::SINGLETON, |YearBooks { index }| {
index.remove(&(book.year, entity));
});
});
// ...insert data into the store...
// Use the index to query all books published in 2018
let books: Vec<_> = store.get::<YearBooks>(Entity::SINGLETON)
.unwrap()
.index
.range((2018, Entity::MIN)..=(2018, Entity::MAX))
.flat_map(|&(_, entity)| store.get::<Book>(entity))
.collect();
Another common use case for hooks is to maintain indexes on specific entities.
For example, we could complement our book database with authors. We'd do that
by adding a new Author
attribute, and storing the entity of an author inside
each book. Now, if we might like to list all the books written by a given
author. We can do this by adding a hook on books, which will construct an index
for each author, listing the books they've written.
use std::collections::HashSet;
use karmeliet::{Entity, Store};
struct Person {
name: &'static str,
}
struct Book {
title: &'static str,
author: Entity,
}
#[derive(Default)]
struct AuthorBooks {
index: HashSet<Entity>,
}
let mut store = Store::default();
store.hook_before_insert(|store, entity, &Book { author, .. }: &Book| {
store.upsert(author, |AuthorBooks { index }| {
index.insert(entity);
});
});
store.hook_after_remove(|store, entity, &Book { author, .. }: &Book| {
store.update(author, |AuthorBooks { index }| {
index.remove(&entity);
});
});
// ...insert data into the store...
// Use the index to query all book titles from `some_author`
let titles_from_some_author: Vec<_> = store.get::<AuthorBooks>(some_author)
.unwrap()
.index
.iter()
.flat_map(|&entity| store.get::<Book>(entity))
.map(|book| book.title)
.collect();
unstable
feature
As an experiment, the unstable
feature can be enabled on nightly. This
removes the default hook mechanism where hooks are registered with
Store::hook_before_insert
and Store::hook_after_remove
, and instead
enables a Hook
trait which can be implemented directly on any type. This has
several advantages: first, it's more efficient, since there's no longer any
hook checks on types that don't have a specific implementation of Hook
.
Second, it's a better guarantee that invariants are enforced, since it's no
longer possible to forget to register a hook.
This feature depends on the min_specialization unstable Rust
feature, which makes it possible to give a default (empty) implementation of
Hook
for all types, and still provide a specialized implementation when
needed.