Skip to content

Instantly share code, notes, and snippets.

@Gozala

Gozala/db.js

Last active December 14, 2023 19:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Gozala/2be75bbd6335ed213b7dd4eb8d19d2d9 to your computer and use it in GitHub Desktop.
Save Gozala/2be75bbd6335ed213b7dd4eb8d19d2d9 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
db.js
import * as API from '@ucanto/interface'
/**
* @typedef {number} Integer
* @typedef {number} Float
* @typedef {Readonly<Uint8Array>} Bytes
* @typedef {string} UTF8
*
* @typedef {String} Entity
* @typedef {Integer|Float|Bytes|UTF8} Attribute
* @typedef {boolean|UTF8|Integer|Float|Bytes} Data
*/
/**
* Database is represented as a collection of facts.
* @typedef {object} Database
* @property {readonly Fact[]} facts
*/
/**
* An atomic fact in the database, associating an `entity` , `attribute` ,
* `value`.
*
* - `entity` - The first component is `entity` that specifies who or what the fact is about.
* - `attribute` - Something that can be said about an `entity` . An attribute has a name,
* e.g. "firstName" and a value type, e.g. string, and a cardinality.
* - `value` - Something that does not change e.g. 42, "John", true. Fact relates
* an `entity` to a particular `value` through an `attribute`.ich
*
* @typedef {readonly [entity: Entity, attribute: Attribute, value: Data]} Fact
*/
/**
* Creates an assertion.
*
* @template {Entity} E
* @template {Attribute} A
* @template {Data} V
*
* @param {E} entity
* @param {A} attribute
* @param {V} value
* @returns {readonly [entity: E, attribute:A, value:V]}
*/
export const assert = (entity, attribute, value) => [entity, attribute, value]
/**
* Variable is placeholder for a value that will be matched against by the
* query engine. It is represented as an abstract `Reader` that will attempt
* to read arbitrary {@type Data} and return result with either `ok` of the
* `Type` or an `error`.
*
* Variables will be assigned unique `bindingKey` by a query engine that will
* be used as unique identifier for the variable.
*
* @template {Data} [Type=Data]
* @typedef {API.Reader<Type, Data> & {propertyKey?: PropertyKey}} Variable
*/
/**
* Term is either a constant or a {@link Variable}. Terms are used to describe
* predicates of the query.
*
* @typedef {Data|Variable} Term
*/
/**
* Describes association between `entity`, `attribute`, `value` of the
* {@link Fact}. Each component of the {@link Relation} is a {@link Term}
* that is either a constant or a {@link Variable}.
*
* Query engine during execution will attempt to match {@link Relation} against
* all facts in the database and unify {@link Variable}s across them to identify
* all possible solutions.
*
* @typedef {[entity: Term, attribute: Term, value: Term]} Relation
*/
/**
* Selection describes set of (named) variables that query engine will attempt
* to find values for that satisfy the query.
*
* @typedef {Record<PropertyKey, Variable>} Selector
*/
/**
* @template {Selector} Selection
* @typedef {{[Key in keyof Selection]: Selection[Key] extends Variable<infer T> ? T : never}} InferMatch
*/
/**
* @template {Selector} Selection
* @typedef {{[Key in keyof Selection]: Selection[Key] extends Variable<infer T> ? (Variable<T> | T) : never}} InferState
*/
const ENTITY = 0
const ATTRIBUTE = 1
const VALUE = 2
/**
* @template {Selector} Selection
* @param {Relation} relation
* @param {Fact} fact
* @param {InferState<Selection>} context
* @returns {InferState<Selection>|null}
*/
export const matchRelation = (relation, fact, context) => {
let state = context
for (const id of [ENTITY, ATTRIBUTE, VALUE]) {
const match = matchTerm(relation[id], fact[id], state)
if (match) {
state = match
} else {
return null
}
}
return state
}
/**
* @template {Selector} Selection
*
* @param {Term} term
* @param {Data} data
* @param {InferState<Selection>} context
*/
export const matchTerm = (term, data, context) =>
// If term is a variable then we attempt to match a data against it
// otherwise we compare data against the constant term.
isVariable(term)
? matchVariable(term, data, context)
: isBlank(term)
? context
: matchConstant(term, data, context)
/**
* @template Context
*
* @param {Data} constant
* @param {Data} data
* @param {Context} context
* @returns {Context|null}
*/
export const matchConstant = (constant, data, context) =>
constant === data ? context : null
/**
* @typedef {Record<string|symbol, Data>} Context
*/
/**
* @template {Selector} Selection
*
* @param {Variable} variable
* @param {Data} data
* @param {InferState<Selection>} context
* @returns {InferState<Selection>|null}
*/
export const matchVariable = (variable, data, context) => {
// Get key this variable is bound to in the context
const key = SelectedVariable.getPropertyKey(variable)
// If context already contains binding for we attempt o unify it with the
// new data otherwise we bind the data to the variable.
return key in context
? matchTerm(context[key], data, context)
: { ...context, [key]: data }
}
/**
* @template {Data} T
* @param {unknown|Variable<T>} x
* @returns {x is Variable<T>}
*/
const isVariable = (x) => {
return (
typeof x === 'object' &&
x !== null &&
'read' in x &&
typeof x.read === 'function'
)
}
/**
*
* @param {unknown} x
* @returns {x is Schema._}
*/
const isBlank = (x) => x === Schema._
/**
* @template {Selector} Selection
* @param {Relation} relation
* @param {Database} db
* @param {InferState<Selection>} context
* @returns {InferState<Selection>[]}
*/
const queryRelation = (relation, { facts }, context) => {
const matches = []
for (const triple of facts) {
const match = matchRelation(relation, triple, context)
if (match) {
matches.push(match)
}
}
return matches
}
/**
* @template {Selector} Selection
* @param {Database} db
* @param {Relation[]} relations
* @param {InferState<Selection>} context
* @returns {InferState<Selection>[]}
*/
export const queryRelations = (db, relations, context) =>
relations.reduce(
/**
* @param {InferState<Selection>[]} contexts
* @param {Relation} relation
* @returns
*/
(contexts, relation) =>
contexts.flatMap((context) => queryRelation(relation, db, context)),
[context]
)
/**
* Takes a selector which is set of variables that will be used in the query
* conditions. Returns a query builder that has `.where` method for specifying
* the query conditions.
*
* @example
* ```ts
* const moviesAndTheirDirectorsThatShotArnold = select({
* directorName: Schema.string(),
* movieTitle: Schema.string(),
* }).where(({ directorName, movieTitle }) => {
* const arnoldId = Schema.number()
* const movie = Schema.number()
* const director = Schema.number()
*
* return [
* [arnold, "person/name", "Arnold Schwarzenegger"],
* [movie, "movie/cast", arnoldId],
* [movie, "movie/title", movieTitle],
* [movie, "movie/director", director],
* [director, "person/name", directorName]
* ]
* })
* ```
*
* @template {Selector} Selection
* @param {Selection} selector
* @returns {QueryBuilder<Selection>}
*/
export const select = (selector) => new QueryBuilder({ select: selector })
/**
* @template {Selector} Selection
* @param {Database} db
* @param {object} source
* @param {Selection} source.select
* @param {Relation[]} source.where
* @returns {InferMatch<Selection>[]}
*/
export const query = (db, { select, where }) => {
const contexts = queryRelations(
db,
where,
/** @type {InferState<Selection>} */ ({})
)
return contexts.map((context) => materialize(select, context))
}
/**
* A query builder API which is designed to enable type inference of the query
* and the results it will produce.
*
* @template {Selector} Select
*/
class QueryBuilder {
/**
* @param {object} source
* @param {Select} source.select
*/
constructor({ select }) {
this.select = select
}
/**
* @param {(variables: Select) => Iterable<Relation>} conditions
* @returns {Query<Select>}
*/
where(conditions) {
return new Query({
select: this.select,
where: [...conditions(this.select)],
})
}
}
/**
* @template {Record<string, unknown>} Object
* @param {Object} object
* @returns {{[Key in keyof Object]: [Key, Object[Key]]}[keyof Object][]}
*/
const entries = (object) => /** @type {any} */ (Object.entries(object))
/**
* @template {Selector} Selection
*/
class Query {
/**
* @param {object} model
* @param {Selection} model.select
* @param {Relation[]} model.where
*/
constructor(model) {
this.model = model
}
/**
*
* @param {Database} db
* @returns {InferMatch<Selection>[]}
*/
execute(db) {
return query(db, this.model)
}
}
/**
* @template {Selector} Selection
* @param {Selection} select
* @param {InferState<Selection>} context
* @returns {InferMatch<Selection>}
*/
const materialize = (select, context) =>
/** @type {InferMatch<Selection>} */
(
Object.fromEntries(
entries(select).map(([name, variable]) => [
name,
isVariable(variable)
? context[SelectedVariable.getPropertyKey(variable)]
: variable,
])
)
)
/**
* @template {Data} T
* @implements {API.Reader<T, Data>}
*/
export class Schema {
/**
* @param {(value: unknown) => value is T} is
*/
constructor(is) {
this.is = is
}
/**
* @param {unknown} value
* @returns {{ok: T, error?: undefined}|{ok?: undefined, error: Error}}
*/
read(value) {
return this.is(value)
? { ok: value }
: { error: new TypeError(`Unknown value type ${typeof value}`) }
}
static string() {
return new Schema(
/**
* @param {unknown} value
* @returns {value is string}
*/
(value) => typeof value === 'string'
)
}
static number() {
return new Schema(
/**
* @param {unknown} value
* @returns {value is number}
*/
(value) => typeof value === 'number'
)
}
static boolean() {
return new Schema(
/**
* @param {unknown} value
* @returns {value is boolean}
*/
(value) => typeof value === 'boolean'
)
}
static _ = Object.assign(
new Schema(
/**
* @param {unknown} _
* @returns {_ is any}
*/
(_) => true
),
{ propertyKey: '_' }
)
}
/**
* @template {Data} [T=Data]
* @template {PropertyKey} [Key=PropertyKey]
* @extends {Variable<T>}
*/
class SelectedVariable {
static lastKey = 0
/**
* @param {Variable} variable
* @returns {PropertyKey}
*/
static getPropertyKey(variable) {
const { propertyKey } = variable
if (propertyKey) {
return propertyKey
} else {
const bindingKey = `${++this.lastKey}`
variable.propertyKey = bindingKey
return bindingKey
}
}
/**
* @param {object} source
* @param {Key} source.key
* @param {Variable<T>} source.schema
*/
constructor({ key, schema }) {
this.propertyKey = key
this.schema = schema
}
/**
* @param {Data} value
*/
read(value) {
return this.schema.read(value)
}
}
Raw
db.test.js
import * as DB from './db.js'
const proofsDB = /** @type {const} */ ({
facts: [
['bafy...upload', 'issuer', 'did:key:zAlice'],
['bafy...upload', 'audience', 'did:key:zBob'],
['bafy...upload', 'expiration', 1702413523],
['bafy...upload', 'capabilities', 'bafy...upload/capabilities/0'],
['bafy...upload/capabilities/0', 'can', 'upload/add'],
['bafy...upload/capabilities/0', 'with', 'did:key:zAlice'],
['bafy...store', 'issuer', 'did:key:zAlice'],
['bafy...store', 'audience', 'did:key:zBob'],
['bafy...store', 'expiration', 1702413523],
['bafy...store', 'capabilities', 'bafy...store/capabilities/0'],
['bafy...store/capabilities/0', 'can', 'store/add'],
['bafy...store/capabilities/0', 'with', 'did:key:zAlice'],
['bafy...store', 'capabilities', 'bafy...store/capabilities/1'],
['bafy...store/capabilities/1', 'can', 'store/list'],
['bafy...store/capabilities/1', 'with', 'did:key:zAlice'],
],
})
/**
* @type {Test.BasicSuite}
*/
export const testDB = {
'test capabilities across ucans': async (assert) => {
const uploadLink = DB.Schema.string()
const storeLink = DB.Schema.string()
const space = DB.Schema.string()
const uploadID = DB.Schema.string()
const storeID = DB.Schema.string()
const result = DB.query(proofsDB, {
select: {
uploadLink,
storeLink,
space,
},
where: [
[uploadLink, 'capabilities', uploadID],
[uploadID, 'can', 'upload/add'],
[uploadID, 'with', space],
[storeLink, 'capabilities', storeID],
[storeID, 'can', 'store/add'],
[storeID, 'with', space],
],
})
assert.deepEqual(result, [
{
uploadLink: 'bafy...upload',
storeLink: 'bafy...store',
space: 'did:key:zAlice',
},
])
},
'test query builder': async (assert) => {
const query = DB.select({
uploadLink: DB.Schema.string(),
storeLink: DB.Schema.string(),
}).where(({ uploadLink, storeLink }) => {
const space = DB.Schema.string()
const uploadID = DB.Schema.string()
const storeID = DB.Schema.string()
return [
[uploadLink, 'capabilities', uploadID],
[uploadID, 'can', 'upload/add'],
[uploadID, 'with', space],
[storeLink, 'capabilities', storeID],
[storeID, 'can', 'store/add'],
[storeID, 'with', space],
]
})
assert.deepEqual(query.execute(proofsDB), [
{
uploadLink: 'bafy...upload',
storeLink: 'bafy...store',
},
])
},
'test baisc': async (assert) => {
const facts = [
DB.assert('sally', 'age', 21),
DB.assert('fred', 'age', 42),
DB.assert('ethel', 'age', 42),
DB.assert('fred', 'likes', 'pizza'),
DB.assert('sally', 'likes', 'opera'),
DB.assert('ethel', 'likes', 'sushi'),
]
const e = DB.Schema.number()
assert.deepEqual(
DB.query(
{ facts },
{
select: { e },
where: [[e, 'age', 42]],
}
),
[{ e: 'fred' }, { e: 'ethel' }]
)
const x = DB.Schema.number()
assert.deepEqual(
DB.query(
{ facts },
{
select: { x },
where: [[DB.Schema._, 'likes', x]],
}
),
[{ x: 'pizza' }, { x: 'opera' }, { x: 'sushi' }]
)
},
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment