Published
Edited
Aug 7, 2019
Importers
1 star
Insert cell
md`# Lazy Graph`
Insert cell
StaleDeps = {
const sd = []
sd[StaleDepsTag] = "stale-deps"
return sd
}
Insert cell
StaleDepsTag = Symbol("stale-deps")
Insert cell
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);
}
Insert cell
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
}
}
Insert cell
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
}
}
Insert cell
md`## Tests`
Insert cell
{
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
}
}
Insert cell

One platform to build and deploy the best data apps

Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.
Learn more