md`# Lazy Graph`
StaleDeps = {
const sd = []
sd[StaleDepsTag] = "stale-deps"
return sd
}
StaleDepsTag = Symbol("stale-deps")
function getStackTrace () {
var stack;
try {
throw new Error('');
} catch (error) {
stack = error.stack || '';
}
stack = stack.split('\n').map(function (line) { return line.trim(); });
return stack.splice(stack[0] == 'Error' ? 2 : 1);
}
class LazyNode {
constructor(name, trace) {
this.name = name
this.downstream = undefined
this.deps = StaleDeps
if (trace) {
this.stack = getStackTrace()
}
// Save a few bytes
// this.marks = 0
// this.debug = false
// this.data = undefined
}
log(...args) {
console.log("NODE", this.name, ...args)
}
await(fn) {
return this.awaitNotify({notify: fn})
}
get stale() {
return this.deps === StaleDeps
}
awaitNotify(node) {
if (this.debug) { this.log("await", node) }
if (this.stale) {
throw new Error(`Can't await while already stale. [name=${this.name}] [node=${node.name}]`)
}
if (this.downstream === undefined) {
this.downstream = node
} else if (this.downstream instanceof Array) {
this.downstream.push(node)
} else if (this.downstream !== node) {
this.downstream = [this.downstream, node]
}
return this
}
abortNotify(node) {
if (this.debug) { this.log("await", node) }
if (this.downstream === undefined) {
return
}
if (this.downstream === node) {
this.downstream = undefined
} else if (this.downstream instanceof Array) {
for (let i = this.downstream.length - 1; i >= 0; --i) {
if (this.downstream[i] === node) {
this.downstream[i] = this.downstream[this.downstream.length - 1]
this.downstream.pop()
break
}
}
} else {
// throw new Error(`Didn't find node to abort. [name=${this.name}] [downstream=${this.downstream.name}] [node=${node.name}]`)
}
// if (!popped) {
// throw new Error(`Didn't find node to abort. [name=${this.name}]`)
// }
}
used() {
this.graph.used(this)
}
notify(notifier) {
if (this.debug) { this.log("notify") }
this.graph.free(this)
if (this.deps !== undefined && this.deps != StaleDeps) {
for (const dep of this.deps) {
if (dep === notifier) {
continue
}
dep.abortNotify(this)
}
this.deps = undefined
}
if (this.downstream !== undefined) {
if (this.downstream instanceof Array) {
for (const node of this.downstream) {
if (this.debug) { this.log("downstream", node) }
node.notify(this)
}
this.downstream.length = 0
} else {
if (this.debug) { this.log("downstream", this.downstream) }
this.downstream.notify(this)
this.downstream = undefined
}
}
this.deps = StaleDeps
}
mark(deps, data) {
if (this.debug) {
this.marks = this.marks ? this.marks + 1 : 1
this.log("mark", this.marks, deps)
}
this.notify()
this.deps = deps
if (this.debug) { this.data = data }
if (deps !== undefined) {
for (const dep of deps) {
dep.awaitNotify(this)
}
}
return this
}
}
class Graph {
constructor() {
class PrivateLazyNode extends LazyNode {}
PrivateLazyNode.prototype.graph = this
this.depsStack = []
this.nodeStack = []
this.currentDeps = undefined
this.currentNode = undefined
this.traceNames = undefined
this.nextNodeId = 0
this.lazyNodeClass = PrivateLazyNode
this.tick = Promise.resolve()
}
trace(name) {
if (!this.traceNames) {
this.traceNames = new Set()
}
this.traceNames.add(name)
}
_newNode(name) {
this.nextNodeId++
return new this.lazyNodeClass(name, this.traceNames ? this.traceNames.has(name) : false)
}
newNode(name) {
const node = this._newNode(name)
node.used = () => this.used(node)
return node
}
used(node) {
if (this.currentDeps !== undefined) {
if (this.currentNode === node) {
throw new Error(`node can't depend on itself!!! [${node.name}]`)
}
this.currentDeps.add(node)
}
}
free(node) {
if (this.currentDeps !== undefined) {
this.currentDeps.delete(node)
}
for (const set of this.depsStack) {
set.delete(node)
}
}
runDiscoveringDeps(node, fn, cb) {
if (this.currentDeps !== undefined) {
this.depsStack.push(this.currentDeps)
this.nodeStack.push(this.currentNode)
}
const deps = new Set()
this.currentNode = node
this.currentDeps = deps
let result
let error
try {
result = fn()
} catch (e) {
error = e
}
this.currentDeps = this.depsStack.pop()
this.currentNode = this.nodeStack.pop()
cb(deps.size === 0 ? undefined : Array.from(deps), result, error)
if (error) {
throw error
}
return result
}
*yieldPromises(gen, name) {
let o
// let invalidations = 0
try {
o = this.runAndPromiseInvalidation(() => gen.next(), name)
// console.log("yielding", o.value.value)
yield Promise.resolve(o.value.value)
while (!o.value.done) {
// console.log("yielding again")
yield new Promise(resolve => {
o.invalidation.then(() => {
// console.log("invalidated", o.value.value)
// if (invalidations++ > 100) {
// debugger
// gen.return()
// }
this.tick.then(() => {
o = this.runAndPromiseInvalidation(() => gen.next(), name)
// console.log("resolving", o.value.value)
resolve(o.value.value)
})
})
})
}
} finally {
// console.log("cancelled", o.value.value)
gen.return()
if (o && o.cancel !== undefined) {
o.cancel()
}
}
}
runAndPromiseInvalidation(fn, name) {
const node = this._newNode("promise::" + name + "::" + this.nextNodeId)
let deps
const value = this.runDiscoveringDeps(
node,
fn,
(d, data) => (
deps = d,
node.mark(d, data),
this.used(node)),
)
let pseudoNode
let reject
const invalidation = new Promise((resolve, reject_) => {
pseudoNode = {
notify: (notifier) => {
resolve()
}
}
reject = reject_
node.awaitNotify(pseudoNode)
})
return {
deps,
invalidation,
cancel() {
node.abortNotify(pseudoNode)
node.mark(undefined, "abort")
// Don't actually reject right now since it's not part of our spec yet...
// reject()
},
value,
}
}
newLazyProxy(cache, upstream, namePrefix) {
let nodes = new Map()
return {
revoke() {
for (const node of nodes.values()) {
node.mark(undefined, "revoked")
}
nodes = null
},
proxy: new Proxy(upstream, {
deleteProperty: (target, prop) => {
if (nodes === null) {
throw new TypeError(`Cannot delete "${prop}", already revoked "${namePrefix}"`)
}
let node = nodes.get(prop)
if (node === undefined) {
return true
}
delete cache[prop]
nodes.delete(prop)
node.mark(undefined, "prop deleted")
return true
},
get: (target, prop, receiver) => {
if (nodes === null) {
throw new TypeError(`Cannot get "${prop}", already revoked "${namePrefix}"`)
}
let node = nodes.get(prop)
let result = undefined
if (node === undefined || node.stale) {
// If node is stale or we've never calculated this value before
this.runDiscoveringDeps(
node,
() => {
result = Reflect.get(target, prop, receiver)
if (result === undefined) {
// Otherwise we don't have a value, so stop caching it.
return
}
// If we have a value, cache it.
cache[prop] = result
return result
},
(deps, data) => {
// Now that we know deps...
if (result === undefined) {
// If we don't have a value now, but we used to, clear the previous mark and return
if (node !== undefined) {
node.mark(undefined, "deleted")
nodes.delete(prop)
delete cache[prop]
node = undefined
}
// Re-mark all of the discovered deps as used so that we know to retry this if any of them change
if (deps) {
for (const dep of deps) {
this.used(dep)
}
}
return
}
// Otherwise we have a result now so we'll want to either create a new node if needed
if (node === undefined) {
node = this._newNode(namePrefix ? namePrefix + prop : prop)
nodes.set(prop, node)
}
if (node && node.debug) {
node.log("lazy deps", deps)
}
// and populate that node with deps
node.mark(deps, data)
},
)
} else {
result = cache[prop]
}
// if we've made it this far and we have a node, mark it as used
if (node) {
this.used(node)
}
return result
},
})
}
}
defineProperties(o, properties, namePrefix) {
for (const k in properties) {
const property = properties[k]
if ("value" in property) {
let node
let value = property.value
Object.defineProperty(o, k, {
enumerable: property.enumerable,
configurable: property.configurable,
get: () => {
if (node === undefined) {
node = this._newNode(namePrefix ? namePrefix + k : k).mark(undefined, value)
}
this.used(node)
return value
},
set: property.writable == false ? undefined : next => {
if (value !== next) {
if (node !== undefined) {
node.mark(undefined, next)
}
value = next
}
if (node === undefined) {
node = this._newNode(namePrefix ? namePrefix + k : k).mark(undefined, value)
}
this.used(node)
return true
},
})
} else {
let node
let value
const getter = property.get
Object.defineProperty(o, k, {
enumerable: property.enumerable,
configurable: property.configurable,
get: () => {
if (node === undefined) {
node = this._newNode(namePrefix ? namePrefix + k : k)
} else if (!node.stale) {
this.used(node)
return value
}
return this.runDiscoveringDeps(
node,
() => value = getter.call(o),
(deps, data) => (node.mark(deps, data), this.used(node)),
)
},
})
}
}
return o
}
}
md`## Tests`
{
try {
const graph = new Graph()
const o1 = graph.defineProperties({}, {x: {value: 0}, y: {value: 1}})
if (o1.x != 0) { throw new Error() }
if (o1.y != 1) { throw new Error() }
o1.x = 1
if (o1.x != 1) { throw new Error() }
let zcount = 0
const {proxy: o2, revoke: o2Revoke} = graph.newLazyProxy({}, {get z() { zcount++; return o1.x + o1.y }})
if (o2.z != 2) { throw new Error() }
if (o2.z != 2) { throw new Error() }
if (zcount != 1) { throw new Error() }
o1.y = 2
if (o2.z != 3) { throw new Error() }
if (zcount != 2) { throw new Error() }
let wcount = 0
const {proxy: o3, revoke: o3Revoke} = graph.newLazyProxy({}, {get w() { wcount++; return o1.y + o2.z }})
if (o3.w != 5) { throw new Error() }
if (o3.w != 5) { throw new Error() }
if (o3.w != 5) { throw new Error() }
if (zcount != 2) { throw new Error() }
if (wcount != 1) { throw new Error() }
o1.y = 3
if (o3.w != 7) { throw new Error() }
o1.x = 3
if (o3.w != 9) { throw new Error() }
if (wcount != 3) { throw new Error() }
o1.x = 3
if (o3.w != 9) { throw new Error() }
if (wcount != 3) { throw new Error() }
o1.x = 4
if (o3.w != 10) { throw new Error() }
if (wcount != 4) { throw new Error() }
} catch (e) {
console.log(e)
throw e
}
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
