2d:null 2e:["$","title",null,{"children":"Execution DAG reduction + ranking | Leonard Pauli | Observable"}] 33:T75d,md`# Execution DAG reduction + ranking *Created by Leonard Pauli, 7 feb 2020* This is an excerpt from my journey to create a **"thought medium"** (see [my twitter](https://twitter.com/LeonardPauli) for more) - supported by a "normalized" graph of knowledge *and logic* - where a way to go from declarative logic to imperative code (to be executed on common hardware) was needed. Avoiding the [halting-problem](https://en.wikipedia.org/wiki/Halting_problem) seems nice (ie. allows for many powerful ideas), thus, all logic will be organized as a [DAG](https://en.wikipedia.org/wiki/Directed_acyclic_graph) (see [total functional programming](https://en.wikipedia.org/wiki/Total_functional_programming)), pure/without [side-effects](https://en.wikipedia.org/wiki/Side_effect_(computer_science)), and seen as a "blackbox"/node with inputs and outputs. An input signal could be the position of a mouse, or the current time with a certain resolution. An output could be what to display on the screen. State may be added by connecting an output to the input through some external memmory. "[Turing-completeness](https://en.wikipedia.org/wiki/Turing_completeness)", eg. an infinite loop (for eg. the [Collatz conjecture](https://en.wikipedia.org/wiki/Collatz_conjecture) ([video](https://www.youtube.com/watch?v=LqKpkdRRLZw), [plot](https://mathematica.stackexchange.com/questions/85718/trying-to-visualize-the-collatz-conjecture), [sidetrack](https://www.instagram.com/zouassi/))), could similary be achieved by having an external unit taking the output and conditionally feeding it back as input. For these cases, the halting-problem would still be in effect, though clearly identifiable, controlled, and limited. *(Assumption: a sufficiently large part of engineering is spent with halting logic, and ability for turing-completeness in those cases often does "more harm than good")* `34:T54b,md` Observations/Steps to convert the logic *(described declarative, platform independent, ie. the "blackbox")*, into something executable *(usually imperative, platform dependent, code)*: - only the output is of interest - *-> ignore branches that doesn't lead to an output* - when the input changes, previous calculations may be reused - futhermore, multiple outputs may have the same internal dependencies - likewise, calculation of one output may reference the same internal dependency multiple times - *-> detect such dependencies ("cross-points") and make sure they're not unnecessarily re-calculated* - ie. possibly by caching calculations at those points - every cache increases memory + compute requirement - *-> attempt to minimize "unecessary" cache-points* - ie. by "reducing" the graph to only those "cross-points" + final outputs and their original input sources - each "cross-point" will then have possibly many inputs, and only one output - *-> convert each "cross-point" to a "function"* - the inputs needs to be evaluated first - *-> figure out the execution order of these functions* - then, bundle them together with an additional "update" function that takes some new input values and triggers the execution of the relevant functions in the relevant order and then notifies the "blackbox" output watcher with the new value, if any `35:Td95c,src = ((observable_require)=> { const is_src_to_observablehq = true const modules = { "bootstrapped_nodes.yaml": { varname: "bootstrapped_nodes_yaml", load: (function (require, observable_require) { const module = {exports: {}} module.exports = `\$type: nn_file title: bootstrapped_nodes.yaml created_by: Leonard Pauli, 7-11 jan 2020 nodes: - \$id: js_value_raw \$type: js_value_raw \$bootstrapped: true \$value: null \$comment: 'only valid in bootrapped state (used instead of binary value, as mvp execution environment is js and not binary)' \$property_type: {} \$to_rim: | return it \$to_js: |- return rim.value(it) - \$id: node_type \$type: node_type \$bootstrapped: true \$value: null \$comment: "" \$property_type: \\$id: {\$type: string, \$comment: 'system unique, auto generated by default, (\\$|\\\\$)?[a-z][a-z0-9_]*'} \\$type: {\$type: string, \$comment: 'node.\$id'} \\$bootstrapped: {\$type: boolean} \\$value: {\$type: js_value_raw, \$comment: 'used by primitive nodes to store binary data'} \\$comment: {\$: string} \\$property_type: {\$type: dictionary, \$comment: 'used to validate properties, eg. {property_name: {\$: integer}}'} \\$to_rim: {\$type: string, \$comment: 'in js-function-rim format, though always return a rim.node (used as the nodes "output")'} \\$to_js: {\$type: string, \$comment: 'in js-function-rim format, though always return plain js values'} \$to_rim: | return it \$to_js: |- return rim.error({message: '\$to_js not implemented for it', it}) - \$id: js_function_rim \$type: node_type \$bootstrapped: true \$comment: | \$type: js_function_rim input_type: {\$type: list, type: {\$: integer}} output_type: {\$: integer} is_pure: true body: | const list = rim.value(it) const sum = list.reduce((s, v)=> s+rim.to_js(v), 0) return rim.node(sum) \$property_type: input_type: {\$: node_type} output_type: {\$: node_type} input: {\$: node_type} # extended_self.input_type output: {\$: node_type} # extended_self.output_type is_pure: \$type: boolean \$value: false \$comment: 'if invocable multiple times with same behaviour / no "side effects"' body: {\$: string} \$to_rim: | const body_id = rim.travelUpTypechainUntilPropNodeId(it, 'body') const body_node = rim.nodeById(body_id) const body = rim.value(body_node) const fn = new Function(['it', 'rim'], body) return fn(it, rim) \$to_js: | return rim.to_js(rim.to_rim(it)) - \$id: js_value_raw_to_node \$type: js_function_rim \$bootstrapped: true input_type: {\$: js_value_raw} body: | const input = rim.property(it, 'input') const _it = it it = rim.to_js(input) const typeof_it = typeof it if (typeof_it === 'string') { return rim.node({\$type: 'string', \$value: it}) } if (typeof_it === 'boolean') { return rim.node({\$type: 'boolean', \$value: it}) } if (typeof_it === 'number') { const it_as_int32 = (it | 0) const is_int32 = !isNaN(it) && it === it_as_int32 if (!is_int32) return rim.error({ message: 'unhandled_typeof_variant', typeof_it, is_int32, }) return rim.node({\$type: 'integer', \$value: it_as_int32}) } if (typeof_it === 'object') { if (it === null) { return rim.error({message: 'unhandled_typeof_variant', typeof_it, it}) } if (Array.isArray(it)) { return rim.node({\$type: 'list', \$value: it}) } return rim.node({\$type: 'dictionary', \$value: it}) } return rim.error({message: 'unhandled_typeof', typeof_it}) - \$id: node_to_js_value_raw \$type: js_function_rim \$bootstrapped: true input_type: {\$: node_type} output_type: {\$: js_value_raw} is_pure: true body: | const input = rim.property(it, 'input') const js_value = rim.to_js(input) return rim.node({\$type: 'js_value_raw', \$value: js_value}) - \$id: string \$type: node_type \$bootstrapped: true \$value: "" \$to_js: | return rim.value(it) - \$id: integer \$type: node_type \$bootstrapped: true \$value: 0 \$to_js: | return rim.value(it) \$to_js_str_pipe: | const val = rim.value(it) const str = val.toString(10) return { deps: [], expr: [str], } - \$id: boolean \$type: node_type \$bootstrapped: true \$value: false \$to_js: | return rim.value(it) - \$id: dictionary \$type: node_type \$bootstrapped: true \$value: {} \$property_type: value_type_default: {\$: node_type} \$to_js: | const keys = rim.dictionary_keys(it) const entries = keys.map(k=> { const value = rim.dictionary_value(it, k) const js_value = rim.to_js(value) return [k, js_value] }) return Object.fromEntries(entries) - \$id: list \$type: node_type \$bootstrapped: true \$value: [] \$property_type: type: {\$: node_type} \$to_js: | const length = rim.list_length(it) const values = [] for (let i = 0; i expr.push(v, ',')) expr.push(']') return { deps: values, expr, } - \$id: dynamic \$type: node_type \$bootstrapped: true \$property_type: input_type: {\$: node_type} input: {\$: node_type} is_applied: {\$: boolean} # TODO: later: use option (none/some) on input instead input_type: {\$: node_type} # TODO: validation should auto add prop from prop_type def input: {\$: node_type} is_applied: false \$to_js: | const is_applied = rim.to_js(rim.nodeById(rim.travelUpTypechainUntilPropNodeId(it, 'is_applied'))) if (is_applied) { const input = rim.nodeById(rim.travelUpTypechainUntilPropNodeId(it, 'input')) return rim.to_js(input) } return rim.error({message: 'use of unapplied dynamic', it}) \$to_js_str_pipe: | return { is_input: true, \$type: rim.property_id(it, 'input_type'), } - \$id: output \$type: node_type \$bootstrapped: true \$property_type: input: {\$: node_type} output_type: {\$: node_type} input: {\$: node_type} output_type: {\$: node_type} # later: auto-calc based on output_type of input, alt rim.output_type(...) or manually settable + validated with rim.output_type \$to_js_str_pipe: | const input_id = rim.property_id(it, 'input') return { is_output: true, deps: [{\$: input_id}], expr: [{\$: input_id}], \$type: rim.property_id(it, 'output_type'), } - \$id: to_js_function \$type: js_function_rim input_type: {\$: node_type} output_type: {\$: js_value_raw} is_pure: true body: | - \$id: nn_file \$type: node_type \$property_type: title: {\$: string} created_by: {\$: string} command: {\$: node_to_js_value_raw} nodes: {\$type: list, type: {\$: node_type}} \$to_js: | const command = rim.property(it, 'command') const js_value = rim.to_js(command) return js_value - \$id: integer_add \$type: js_function_rim input_type: {\$type: list, type: {\$: integer}} output_type: {\$: integer} is_pure: true body: | const input = rim.property(it, 'input') const js_values = rim.to_js(input) const res = js_values.reduce((a, v)=> a+v, 0) return rim.node({\$type: 'integer', \$value: res}) \$to_js_str_pipe: | const input_id = rim.property_id(it, 'input') return { deps: [{\$: input_id}], expr: [{\$: input_id}, '.reduce((s, v)=> s+v, 0)'], } - \$id: integer_multiply \$type: js_function_rim input_type: {\$type: list, type: {\$: integer}} output_type: {\$: integer} is_pure: true body: | const input = rim.property(it, 'input') const js_values = rim.to_js(input) const res = js_values.reduce((a, v)=> a*v, 1) return rim.node({\$type: 'integer', \$value: res}) ` return module.exports }), loading: false, value: null, }, "declarative_to_js_bootstrap_tests.yaml": { varname: "declarative_to_js_bootstrap_tests_yaml", load: (function (require, observable_require) { const module = {exports: {}} module.exports = `\$type: nn_file title: declarative_to_js_bootstrap_tests.yaml created_by: Leonard Pauli, 7 jan 2020 command: {\$: start} nodes: - \$id: start \$type: integer_add input: - \$id: dyn1 \$type: dynamic input_type: {\$: integer} - 2 - \$id: myout \$type: output input: {\$: hello} output_type: {\$: integer} - {\$: tresout} - \$id: hello \$type: integer_add input: - 3 - 4 - {\$: dyn1} - {\$: tresout} - \$id: tresout \$type: output input: {\$: tres} output_type: {\$: integer} - \$id: tres \$type: integer_add input: - {\$: dyn1} - 9 ` return module.exports }), loading: false, value: null, }, "index.js": { varname: "index_js", load: (function (require, observable_require) { const module = {exports: {}} const {yaml, dot, fs, util, exec, exec_dot} = (typeof is_src_to_observablehq !== 'undefined'? (()=> { return { yaml: observable_require('js-yaml@3.13.1/dist/js-yaml.js'), dot: {}, // observable_require("@observablehq/graphviz@0.2"), fs: {}, util: {}, exec: ()=> {}, exec_dot: ()=> {}, } }): (()=> { const yaml = require('js-yaml') const fs = require('fs') const util = require('util') const exec = util.promisify(require('child_process').exec) async function exec_dot({filename = 'input.dot', output_type = 'pdf'}) { try { const auto_gen_output_filename = '-O' const filename_escaped = `'${filename.replace(/'/g, `'"'"'`)}'` const args = ['dot', `-T${output_type}`, auto_gen_output_filename, filename_escaped] const command = args.join(' ') const { stdout, stderr } = await exec(command) console.log('stdout:', stdout) console.log('stderr:', stderr) } catch (err) { console.error(err) } } return {yaml, fs, util, exec, exec_dot} }))() const {nodeedges_to_dot_text, nodeedges_clean_ids_for_dot} = require('./nodeedges_to_dot_text.js') const {json_as_rimraw_to_nodeedges} = require('./json_as_rimraw_to_nodeedges.js') const { inout_pipeline_run, pipeline_run, passthrough, error, assert_string, } = require('./utils.js') const {rim_new} = require('./rim_new.js') const js_str_pipe = require('./js_str_pipe.js') const main = async ()=> { const pipeline = [ {id: "to_js_value_raw_test", fn: to_js_value_raw_test}, ] const _out = await pipeline_run(pipeline, {log: true}) } const to_js_value_raw_test = ()=> inout_pipeline_run([ {out: 'rim', fn: rim_new}, {fn: ()=> 'bootstrapped_nodes.yaml', title: 'bootstrapped_nodes.yaml'}, {fn: filename_load_contents_as_text}, {fn: text_as_yaml_to_json}, {out: 'file_bootstrap', fnctx: ctx=> ctx.rim.node, use: ['rim']}, {fn: ()=> 'declarative_to_js_bootstrap_tests.yaml', title: 'declarative_to_js_bootstrap_tests.yaml'}, {fn: filename_load_contents_as_text}, {fn: text_as_yaml_to_json}, {out: 'file_test', fnctx: ctx=> ctx.rim.node, use: ['rim']}, {use: ['rim', 'file_bootstrap', 'file_test'], title: 'custom', fnctx: ctx=> async ()=> { const {rim, file_bootstrap, file_test} = ctx const meta_key_unhandled = rim.meta_key_unhandled() if (meta_key_unhandled.length) console.dir({meta_key_unhandled}) const _command = rim.property(file_test, 'command') const command = rim.node({$type: 'output', input: {$: _command.$id}}) const pipes_raw = js_str_pipe.pipes_get(rim, command) const print_out_pipes_raw_dot = true const print_out_dag_red_dot = true if (print_out_pipes_raw_dot) { const dot = js_str_pipe.pipes_raw_to_dot_text(pipes_raw) const filename = await text_save_to_filename({text: dot, filename: 'tmp/pipes_raw_out.dot'}) await exec_dot({filename, output_type: 'pdf'}) } const debug_iteration = obj=> { const dot = js_str_pipe.dag_reduced_to_dot(obj, {rank_clusters: true}) const nrid = obj.iteration? obj.iteration.nr+'_'+obj.iteration.node.id: 'out' return (async ()=> { const filename = await text_save_to_filename({text: dot, filename: `tmp/dag_red/d_${nrid}.dot`}) await exec_dot({filename, output_type: 'pdf'}) })() } const schedule = js_str_pipe.schedule_pipes(pipes_raw, {debug_iteration}) if (print_out_dag_red_dot) { await debug_iteration(schedule.dag_red) } return {} // schedule }}, {fn: it=> console.dir(it, {depth: 5}), title: 'log'}, ], {log: true}) const dag_reduced_iterations_dot_from_yaml = (bootstrapped_nodes_yaml, file_node_yaml)=> inout_pipeline_run([ {out: 'rim', fn: rim_new}, {fn: ()=> bootstrapped_nodes_yaml, title: 'bootstrapped_nodes_yaml'}, {fn: text_as_yaml_to_json}, {out: 'file_bootstrap', fnctx: ctx=> ctx.rim.node, use: ['rim']}, {fn: ()=> file_node_yaml, title: 'file_node_yaml'}, {fn: text_as_yaml_to_json}, {out: 'file_test', fnctx: ctx=> ctx.rim.node, use: ['rim']}, {use: ['rim', 'file_bootstrap', 'file_test'], title: 'custom', fnctx: ctx=> async ()=> { const {rim, file_test} = ctx return dag_reduced_iterations_dot({rim, file_node: file_test}) }}, ], {log: false}) const dag_reduced_iterations_dot = ({rim, file_node})=> { const meta_key_unhandled = rim.meta_key_unhandled() if (meta_key_unhandled.length) console.dir({meta_key_unhandled}) const _command = rim.property(file_node, 'command') const command = rim.node({$type: 'output', input: {$: _command.$id}}) const pipes_raw = js_str_pipe.pipes_get(rim, command) const dot = js_str_pipe.pipes_raw_to_dot_text(pipes_raw) const items = [] items.push({dot, title: 'pipes_raw'}) const debug_iteration = obj=> { const dot = js_str_pipe.dag_reduced_to_dot(obj, {rank_clusters: true}) const nrid = obj.iteration? obj.iteration.nr+'_'+obj.iteration.node.id: 'out' items.push({dot, title: nrid}) } const schedule = js_str_pipe.schedule_pipes(pipes_raw, {debug_iteration}) debug_iteration(schedule.dag_red) return items } const filename_load_contents_as_text = it=> { return fs.promises.readFile(it, 'utf-8') } const text_save_to_filename = async it=> { await fs.promises.writeFile(it.filename, it.text) return it.filename } const text_as_yaml_to_json = async it=> { return yaml.safeLoad? yaml.safeLoad(it): (await yaml).safeLoad(it) } if (typeof is_src_to_observablehq === 'undefined') { main().catch(e=> console.error(e)) } module.exports = { dag_reduced_iterations_dot_from_yaml, text_as_yaml_to_json, } return module.exports }), loading: false, value: null, }, "js_str_pipe.js": { varname: "js_str_pipe_js", load: (function (require, observable_require) { const module = {exports: {}} /* assumes: node: $id: string $type: string some_prop: {$: node_id} some_dynamic: {$: other_node_id} $to_js_str_pipe: | const some_prop = rim.property(it, 'some_prop') const some_dynamic = rim.property(it, 'some_dynamic') return { deps: [{$: some_prop.$id}], // optional, intermediate nodes optional, whos js-value should be provided directly as input expr: [{$: some_prop.$id}, '+', {$: some_dynamic.$id}], } or { is_input: true, $type: some_dynamic.$type, } or { is_output: true, deps: [{$: some_prop.$id}], expr: [{$: some_prop.$id}], } */ const to_js_str_pipe = (rim, node)=> { const value = rim.to_js(node, {fn_body_key: '$to_js_str_pipe'}) return value } const pipes_get = (rim, node)=> { const pipes = {} const deps_input_all = {} const deps_output_all = {} const depsNoted = new Set([node.$id]) const queue = [node.$id] while (queue.length>0) { const node_id = queue.pop() const node = rim.nodeById(node_id) const p = to_js_str_pipe(rim, node) if (p.is_input) { const dep = { $id: node_id, deps: [], expr: [{$: node_id}], $type: p.$type, } const existing = deps_input_all[node_id] if (existing) { if (existing.$type !== dep.$type) { return rim.error({message: 'different types for same input dep', dep, existing}) } return } pipes[dep.$id] = dep deps_input_all[dep.$id] = dep } else { const {deps, expr, is_output} = p if (deps) deps.filter(d=> !depsNoted.has(d.$)).map(d=> { depsNoted.add(d.$) queue.push(d.$) }) const dep = { $id: node.$id, deps: deps || [], expr, } pipes[dep.$id] = dep if (is_output) { deps_output_all[dep.$id] = dep } } } const to_object_set = obj=> Object.fromEntries(Object.entries(obj) .map(([k, v])=> [k, true])) return { pipes, sources: to_object_set(deps_input_all), sinks: to_object_set(deps_output_all), } } const pipes_raw_to_dot_text = (pipes_raw)=> { const pipe_to_dot = n=> { const is_input = n.$id in pipes_raw.sources return `"${n.$id}" [${is_input?'color="blue"':''}`+ `label="${n.$id}${is_input?': '+n.$type:''}", `+ `xlabel="${(n.expr.map(a=> typeof a !== 'string'?a.$:a) .join('')).replace(/"/g, '\\"').replace(/\n/g, '\\n')}"];` } return `digraph pipes_raw { rankdir=LR; nodesep=0.4; ranksep=1.5; compound=true; // something for clustering? node [shape="ellipse"]; node [color="black"]; ${Object.values(pipes_raw.pipes).map(pipe_to_dot).join('\n\t')} node [color="red"]; edge [color="black"]; ${Object.values(pipes_raw.pipes) .map(p=> p.deps.map(d=> [d.$, p.$id])) .reduce((a, b)=> a.concat(b), []) .map(([a, b])=> `${a} -> ${b};`).join(' ')} } ` } const schedule_pipes = (pipes_raw, {debug_iteration=null})=> { const sources = new Set(Object.keys(pipes_raw.sources)) const sinks = new Set(Object.keys(pipes_raw.sinks)) const edges = xs_concat( Object.values(pipes_raw.pipes) .map(p=> p.deps.map(d=> ({origin: d.$, target: p.$id}))) ) const dag_red = dag_reduce({sources, sinks, edges}, { debug_iteration: !debug_iteration? null: obj=> { const reset_inlets = dag_correct_inlets(obj.supernodes_all) const reset_ranks = dag_add_ranks_as_max_dep_chain_length(obj.supernodes_all) debug_iteration(obj) reset_ranks() reset_inlets() } }) if (dag_red.supernodes_dangling.size > 0) { throw new Error(`dag_red got supernodes_dangling (`+ `${[...dag_red.supernodes_dangling].map(sn=> sn.id).join(', ')})`) } dag_correct_inlets(dag_red.supernodes_all) dag_add_ranks_as_max_dep_chain_length(dag_red.supernodes_all) const pipes = dag_reduced_to_pipes(dag_red) return { dot: dag_reduced_to_dot(dag_red, {rank_clusters: true}), dag_red, pipes, } } const dag_correct_inlets = supernodes_all=> { const reset_list = [] supernodes_all.forEach(sn=> { reset_list.push({sn, inlets: sn.inlets}) sn.inlets = new Set([...sn.inlets]) }) const reset = ()=> reset_list .forEach(({sn, inlets})=> {sn.inlets = inlets}) supernodes_all.forEach(sn=> { sn.outlet.outputs.forEach(n=> { if (n.supernode===sn) return n.supernode && n.supernode.inlets.add(sn) }) }) return reset } const dag_add_ranks_as_max_dep_chain_length = supernodes_all=> { const reset = ()=> supernodes_all .forEach(sn=> sn.max_dep_chain_length = null) const items = [...supernodes_all] while (items.length > 0) { const item = items.pop() if (item.max_dep_chain_length != null) continue const take = [], taken = [] item.inlets.forEach(sn=> { if (sn.max_dep_chain_length != null) taken.push(sn) else take.push(sn) }) if (take.length > 0) { items.push(item, ...take) continue } item.max_dep_chain_length = taken .reduce((p, sn)=> Math.max(p, sn.max_dep_chain_length), 0) + (taken.length > 0? 1: 0) } return reset } const flatten_dag_reduced_for_logging = dag_red=> { const nodes_all = [] const supernodes_all_flat = dag_red.supernodes_all.map(sn=> { nodes_all.push(...sn.nodes_all) return { id: sn.id, nodes: sn.nodes_all.map(n=> n.id), outlet: sn.outlet.id, inlets: [...sn.inlets].map(sn=> sn.id), max_dep_chain_length: sn.max_dep_chain_length, } }) const nodes_all_flat = nodes_all.map(n=> ({ id: n.id, inputs: [...n.inputs].map(n=> n.id), outputs: [...n.outputs].map(n=> n.id), sinks_final: [...n.sinks_final].map(sn=> sn.id), supernode: n.supernode && n.supernode.id, })) return { nodes: nodes_all_flat, supernodes: supernodes_all_flat, sources: [...dag_red.supernodes_sources].map(sn=> sn.id), internal: [...dag_red.supernodes_internal].map(sn=> sn.id), sinks: [...dag_red.supernodes_sinks].map(sn=> sn.id), dangling: [...dag_red.supernodes_dangling].map(sn=> sn.id), } } const dag_reduced_to_pipes = dag_red=> { return {} } const dag_reduced_to_dot = (dag_red, {rank_clusters=false} = {})=> { const { supernodes_all, supernodes_sources, supernodes_internal, supernodes_sinks, supernodes_dangling, ...rest } = dag_red const {meta, iteration: _iteration} = rest const nodes_all_in_supernodes = supernodes_all .map(sn=> sn.nodes_all) .reduce((a, ns)=> (ns.forEach(n=> a.add(n)), a), new Set()) const nodes_all = meta? meta.nodes_all: [...nodes_all_in_supernodes] const nodes_taking = meta? meta.nodes_taking: new Set() const nodes_taken = meta? meta.nodes_taken: new Set(nodes_all) const nodes_take = meta ? new Set(nodes_all.filter(n=> !nodes_all_in_supernodes.has(n))) : new Set() const edges_take = [...nodes_take].map(n=> [...n.inputs] .map(o=> ({origin: o, target: n}))) .reduce((a, b)=> a.concat(b), []) const iteration = _iteration? _iteration: { nr: null, node: null, going_upstream: null, supernode_cached: null, is_return: false, downstream_from_node: null, } const items = !meta?[]: meta.items.map((o, i)=> ({...o, i})) const node_dot = (n, sn=null)=> { const is_outlet = sn && n===sn.outlet const is_current = iteration.node === n const color = is_current ? 'red' : nodes_take.has(n) ? 'gray' : nodes_taking.has(n) ? 'orange' : is_outlet? 'cyan' : 'black' return `"${n.id}" [`+ `label="${n.id}", `+ `color="${color}"`+ `];` } const supernode_to_cluster_dot = sn=> { return `subgraph cluster_${sn.id} { label="supernode_${sn.id}"; ${sn.nodes_all.map(n=> node_dot(n, sn)).join('\n\t\t')} }` } const in_edge_dot = ({n, n_in})=> { return `"${n_in.id}" -> "${n.id}";` } return `digraph dag_red { rankdir=LR; nodesep=0.4; ranksep=1.5; compound=true; // something for clustering? node [shape="ellipse"]; node [color=transparent]; ${items.map(o=> `_item_${o.i} [label="${o.going_upstream?'(':''}${o.node.id}${o.going_upstream?')':''}"];`).join('\n\t')} ${items.map(o=> `"_item_${o.i}"`).reduce((s, id)=> `${s} -> ${id}; ${id}`, '_item_start')+' -> _item_end;'} node [color=black]; ${rank_clusters? ` ${(()=> { const groups = {} supernodes_all.forEach(sn=> { const group = groups[sn.max_dep_chain_length] = groups[sn.max_dep_chain_length] || [] group.push(sn) }) return Object.keys(groups).map(key=> `subgraph cluster_rank_${key} { label="rank_${key}"; color="gray"; ${groups[key].map(supernode_to_cluster_dot).join('\n\t\t')} }`).join('\n\t') + '\n\n\t' })()} `: ` ${[...supernodes_sources].map(supernode_to_cluster_dot).join('\n\t')} ${[...supernodes_internal].map(supernode_to_cluster_dot).join('\n\t')} ${[...supernodes_dangling].map(supernode_to_cluster_dot).join('\n\t')} ${[...supernodes_sinks].map(supernode_to_cluster_dot).join('\n\t')} `} ${[...nodes_take].map(n=> node_dot(n, null)).join('\n\t')} ${[ ...supernodes_sources, ...supernodes_internal, ...supernodes_dangling, ...supernodes_sinks, ].map(sn=> sn.nodes_all) .reduce((a, b)=> a.concat(b), []) .map(n=> [...n.inputs].map(n_in=> in_edge_dot({n, n_in})).join(' ')) .join('\n\t') } edge [color="gray", style=dashed]; ${edges_take.map(({origin, target})=> `"${origin.id}" -> "${target.id}";`).join(' ')} }` } const dag_reduce = (graph, {debug_iteration = null}={})=> { const nodes = {} const nodes_all = [] const node_add = ({id})=> { const id_exists = id in nodes if (id_exists) return nodes[id] const node = { id, inputs: new Set(), outputs: new Set(), sinks_final: new Set(), } nodes[id] = node nodes_all.push(node) return node } const supernodes = {} const supernodes_all = [] const supernode_make = node=> { const supernode = { id: node.id, nodes_all: [], outlet: node, inlets: new Set(), } const id_exists = supernode.id in supernodes if (id_exists) throw new Error(`${supernode.id} supernode already exists`) supernode_add_node(supernode, node) supernodes[supernode.id] = supernode supernodes_all.push(supernode) return supernode } const supernode_add_node = (supernode, node)=> { const has_supernode = !!node.supernode if (has_supernode) { if (node.supernode===supernode) return throw new Error(`${node.id} already has supernode`) } else { node.supernode = supernode } supernode.nodes_all.push(node) } graph.sources.forEach(id=> node_add({id})) const nodes_sink = [...graph.sinks].map(id=> node_add({id})) graph.edges.forEach(({origin, target})=> (node_add({id: origin}), node_add({id: target}))) graph.edges.forEach(({origin, target})=> { const o = nodes[origin] const t = nodes[target] o.outputs.add(t) t.inputs.add(o) }) const supernodes_sources = new Set() graph.sources.forEach(id=> { const node = nodes[id] const supernode = supernode_make(node) supernodes_sources.add(supernode) }) const supernodes_sinks = new Set() graph.sinks.forEach(id=> { const node = nodes[id] const supernode = supernode_make(node) supernodes_sinks.add(supernode) node.sinks_final.add(supernode) }) const nodes_taking = new Set() const nodes_taken = new Set() const supernodes_internal = new Set() const supernodes_dangling = new Set() const items = [...nodes_sink].map(sink=> ({ node: sink, going_upstream: true, supernode_cached: supernodes[sink.id], })) const log_stack_tree = false let log_stack_tree_indent = '' const log_stack_tree_log = !log_stack_tree? ()=> {} : (...args)=> console.log(log_stack_tree_indent, ...args) let nr = 0 while (items.length > 0) { nr++ log_stack_tree_log(items.map(it=> it.node.id)) const {node, going_upstream, supernode_cached, is_return, downstream_from_node} = items.pop() log_stack_tree_log(log_stack_tree_indent, node.id, going_upstream?'(<-)':'(->)') debug_iteration && debug_iteration({ meta: { nodes_all, nodes_taking, nodes_taken, items, }, iteration: { nr, node, going_upstream, supernode_cached, is_return, downstream_from_node, }, supernodes_all, supernodes_sources, supernodes_internal, supernodes_sinks, supernodes_dangling, }) if (nodes_taken.has(node)) continue; if (nodes_taking.has(node) && !is_return) { throw new Error(`${node.id} cycle detected`) } nodes_taking.add(node) if (log_stack_tree) log_stack_tree_indent += '\t' const taken = [], taking = [], take = [] node.outputs.forEach(node=> { if (nodes_taken.has(node)) { taken.push(node) } else if (nodes_taking.has(node)) { taking.push(node) } else { take.push(node) } }) if (taking.length > 0) { throw new Error(`${node.id} possible cycles detected with ${taking.map(n=> n.id)}`) continue } if (take.length > 0) { log_stack_tree_log(log_stack_tree_indent, '-> downstream: '+take.map(n=> n.id)) items.push({ node, going_upstream: true, supernode_cached: null, is_return: true, downstream_from_node, }) take.forEach(n=> { items.push({ node: n, going_upstream: false, supernode_cached: null, downstream_from_node: node, }) }) continue } const is_leaf = taken.length === 0 let supernode = supernode_cached || supernodes[node.id] || null if (!supernode) { if (is_leaf) { supernode = supernode_make(node) supernodes_dangling.add(supernode) } else { supernode = taken[0].supernode } } if (!is_leaf) { const is_supernode_outlet = node.supernode && node.supernode.outlet === node taken .map(n=> [...n.sinks_final]) .reduce((a, b)=> a.concat(b), []) .forEach(sink=> node.sinks_final.add(sink)) const {sinks_final} = node let is_internal_crosspoint = null if (is_supernode_outlet) { is_internal_crosspoint = false } else { const supernode_sinks_final = supernode.outlet.sinks_final const sinks_final_differ = [...sinks_final].some(s=> !supernode_sinks_final.has(s)) const sinks_final_is_larger = sinks_final.size > supernode_sinks_final.size if (sinks_final_differ && !sinks_final_is_larger) throw new Error( `expected sinks_final to be superset of supernode_sinks_final`) const is_internal_crosspoint = sinks_final_is_larger } if (is_internal_crosspoint) { supernode = supernode_make(node) supernodes_internal.add(supernode) } else { const already_has_supernode = !!node.supernode if (already_has_supernode) { if (supernodes_sources.has(node.supernode) || supernodes_sinks.has(node.supernode)) { supernode = node.supernode } else { throw new Error(`${node.id} already_has_supernode and isn't a source`) } } else { supernode_add_node(supernode, node) } } } nodes_taking.delete(node) nodes_taken.add(node) if (log_stack_tree) log_stack_tree_indent = log_stack_tree_indent .substring(0, log_stack_tree_indent.length-1) if (downstream_from_node) { log_stack_tree_log(log_stack_tree_indent, 'downstream_from_node', downstream_from_node.id) } const to_add = [] // if (log_stack_tree) node.inputs.forEach(n=> { if (downstream_from_node===n) return const item = { node: n, going_upstream: true, supernode_cached: supernode, } if (downstream_from_node) { items.unshift(item) if (log_stack_tree) to_add.unshift(item) } else { items.push(item) if (log_stack_tree) to_add.push(item) } }) log_stack_tree_log(log_stack_tree_indent, '-- will add ['+ (to_add.map(it=> it.node.id).join(','))+'] of ['+( [...node.inputs].map(n=> n.id).join(','))+']') } if (nodes_taking.size > 0) throw new Error( `expected all nodes to be taken (left: ${[...nodes_taking].map(n=> n.id)})`) return { supernodes_all, supernodes_sources, supernodes_internal, supernodes_sinks, supernodes_dangling, } } const xs_concat = xs=> xs.reduce((s, v)=> s.concat(v), []) /* const html_str_from_pipes = ({pipes, default_values, view_id})=> { const hstr = '' return hstr } const dom_from_pipes = ({pipes, sources, view_id, prerender = false, default_values = {}})=> { if (prerender) { assert(default_values match sources) } const mount_js_fn_str = '' const pipes_all_ids = Object.keys(pipes) if (prerender) { const prerendered_html_str = '' const prerendered_css_str = '' return {prerendered_html_str, prerendered_css_str, mount_js_fn_str} } return {mount_js_fn_str} } */ module.exports = { pipes_get, pipes_raw_to_dot_text, schedule_pipes, dag_reduced_to_dot, } return module.exports }), loading: false, value: null, }, "json_as_rimraw_to_nodeedges.js": { varname: "json_as_rimraw_to_nodeedges_js", load: (function (require, observable_require) { const module = {exports: {}} const { pipeline_run, passthrough, error, assert_string, } = require('./utils.js') const json_as_rimraw_to_nodeedges = (it, {id_groups = {}, log = false} = {})=> { const flats = {} // rimraw node -> flat node -> ... const edges = [] const refs = [] const meta_key_unhandled = [] let id = null const reserved_id_get = rimraw=> { const id = rimraw_node_id(rimraw, id_groups, flats) rimraw_node_id_reserve(id, id_groups) return id } let queue_processed_tot = 0 const queue = [it] const addSub = sub=> { if (sub.flat) { flats[sub.flat.$id] = sub.flat if (!id) id = sub.flat.$id } if (sub.refs) refs.push(...sub.refs) if (sub.edges) edges.push(...sub.edges) if (sub.meta_key_unhandled) meta_key_unhandled.push(...sub.meta_key_unhandled) if (sub.defs) queue.push(...sub.defs) } while (queue.length>0) { const raw = queue.pop() const queueLenPrev = queue.length const subs = json_as_rimraw_to_subnodes_and_edges(raw, reserved_id_get) subs.forEach(addSub) queue_processed_tot++ if (log) { const curr_tot_added = queue.length - queueLenPrev const curr_tot = queue_processed_tot + queue.length - curr_tot_added const curr_tot_added_txt = curr_tot_added>0?' + '+curr_tot_added:'' const progress = `${queue_processed_tot} of ${curr_tot}${curr_tot_added_txt}` const title = subs.filter(s=> s.flat).map(s=> s.flat.$id).join(',') console.log(`queue.processed (${progress}): ${title}`) } } const refs_dangling = refs.filter(id=> !(id in flats)) return { id, flats, edges, refs_dangling, id_groups, meta_key_unhandled, } } const json_as_rimraw_to_subnodes_and_edges = (it, reserved_id_get)=> { const handlers = json_as_rimraw_node_type_handlers const handle_raw = function handle_raw(v, k) { const vtype = typeof v const has_handler = vtype in handlers if (!has_handler) throw error({ at: "handle_raw", has_handler, vtype, v, }) return handlers[vtype](v, {k, reserved_id_get, handle_raw}) } const handled = handle_raw(it, null) if (handled.ref!=null) { return [{ flat: {$: handled.ref}, refs: [handled.ref], }, ...handled.subs || []] } else { const id = reserved_id_get(handled.def) const subs = json_as_rimraw_node_to_subnodes_and_edges(handled.def, id, reserved_id_get, handle_raw) return [...subs, ...handled.subs || []] } } const json_as_rimraw_node_to_subnodes_and_edges = (it, id, reserved_id_get, handle_raw)=> { if (typeof it !== 'object' || !it || "$" in it) throw error({ at: "json_as_rimraw_node_to_subnodes_and_edges", it, expected: 'rimraw node', }) const origin = id const subs = [] const edges = [] // is many {(origin, target) is id, key is string} const defs = [] // is many rimraw_node const refs = [] // is many id const nodeflat = {} nodeflat.$id = origin nodeflat.$type = it.$type || rimraw_default_type if ('$value' in it) nodeflat.$value = it.$value const meta_key_raw = new Set('$id,$type,$value'.split(',')) const meta_key_supported = new Set('$bootstrapped,$comment,$property_type,$to_rim,$to_js,$to_js_str_pipe'.split(',')) const meta_key_unhandled = [] const raw_entries_meta = [] const raw_entries_property = [] Object.entries(it).forEach(([k, v])=> { if (k.startsWith('$')) { if (meta_key_raw.has(k)) return if (meta_key_supported.has(k)) return raw_entries_meta.push([k, v]) return meta_key_unhandled.push(k) } else if (k.startsWith('\\$')) { raw_entries_property.push([k.slice(1), v]) } else { raw_entries_property.push([k, v]) } }) const process_entry = ([k, v])=> { const handled = handle_raw(v, k) if (handled.subs) subs.push(...handled.subs) let target_id = null if (handled.ref!=null) { target_id = handled.ref refs.push(target_id) } else { target_id = reserved_id_get(handled.def) const def_w_id = {...handled.def, $id: target_id} defs.push(def_w_id) } return [k, target_id] } const p_meta = raw_entries_meta.map(process_entry) const p_prop = raw_entries_property.map(process_entry) p_meta.map(([k, v])=> nodeflat[k] = v) nodeflat.$property = Object.fromEntries(p_prop) edges.push(...p_meta.map(([key, target])=> ({origin, target, key}))) edges.push(...p_prop.map(([key, target])=> ({origin, target, key, is_prop: true}))) return [{ flat: nodeflat, refs, defs, edges, meta_key_unhandled, }, ...subs] } const json_as_rimraw_node_type_handlers = { "undefined": (v, {k})=> { throw error({at: 'json_as_rimraw_node_type_handlers', unhandled: typeof v, k, v}) }, "object": (v, {k, reserved_id_get, handle_raw})=> { if (v === null) { throw error({at: 'json_as_rimraw_node_type_handlers', unhandled: typeof v, k, v}) } else if (Array.isArray(v)) { const subs = [] const defs = [] const refs = [] const edges = [] const item_ids = v.map(rimraw=> { const sub = handle_raw(rimraw, '$value') if (sub.subs) subs.push(...sub.subs) if (sub.ref!=null) { refs.push(sub.ref) return sub.ref } else { const id = reserved_id_get(sub.def) const def_w_id = {...sub.def, $id: id} defs.push(def_w_id) return id } }) const def = {$type: 'list', $value: item_ids} def.$id = reserved_id_get(def) const origin = def.$id edges.push(...def.$value.map(target=> ({origin, target, key: '$value'}))) subs.push({defs, refs, edges}) return {def, subs} } else { const is_ref = "$" in v if (is_ref) { return {ref: v['$']} } else { // is def return {def: v} } } }, "boolean": (v, {k})=> { return {def: {$type: 'boolean', $value: v}} }, "number": (v, {k})=> { const v_as_int32 = (v | 0) const is_int32 = !isNaN(v) && v === v_as_int32 if (!is_int32) throw error({ at: 'json_as_rimraw_node_type_handlers', unhandled: typeof v, k, v, is_int32, }) return {def: {$type: 'integer', $value: v_as_int32}} }, "bigint": (v, {k})=> { throw error({at: 'json_as_rimraw_node_type_handlers', unhandled: typeof v, k, v}) }, "string": (v, {k})=> { return {def: {$type: 'string', $value: v}} }, "symbol": (v, {k})=> { throw error({at: 'json_as_rimraw_node_type_handlers', unhandled: typeof v, k, v}) }, "function": (v, {k})=> { throw error({at: 'json_as_rimraw_node_type_handlers', unhandled: typeof v, k, v}) }, } const rimraw_node_id = (it, id_groups, flats)=> { const custom_id = it.$id const id = custom_id || rimraw_node_id_new(it, id_groups) if (custom_id) { assert_string({at: 'rimraw_node_id', custom_id}) const registered_already = custom_id in flats if (registered_already) { const existing = flats[custom_id] throw error({at: 'rimraw_node_id', registered_already, it, existing}) } } return id } const rimraw_default_type = 'node_type' const rimraw_node_id_group_key = it=> { return it.$type || rimraw_default_type } const rimraw_node_id_new = (it, id_groups)=> { const group_key = rimraw_node_id_group_key(it) const group_exists = group_key in id_groups const nr_next = group_exists? id_groups[group_key]: 0 return `${group_key}_${nr_next}` } const rimraw_node_id_reserve = (id, id_groups)=> { const auto_id_match = id.match(/^(.*)_(\d+)$/) if (auto_id_match) { const [_, group_key, nr] = auto_id_match const group_exists = group_key in id_groups const nr_next = group_exists? id_groups[group_key]: 0 id_groups[group_key] = Math.max(nr_next, parseInt(nr)+1) } } module.exports = {json_as_rimraw_to_nodeedges} return module.exports }), loading: false, value: null, }, "nodeedges_to_dot_text.js": { varname: "nodeedges_to_dot_text_js", load: (function (require, observable_require) { const module = {exports: {}} const nodeedges_to_dot_text = (it, { cluster_node_types = false, render_primitive = false, useLR = true, } = {})=> { const primitive_types = 'string,boolean,integer'.split(',') const primitive_value_typeofs = 'string,boolean,number'.split(',') const node_node_type = [] const node_custom = [] const node_primitive = [] const node_primitive_integer = [] Object.values(it.flats).forEach(n=> { if (n.$bootstrapped) return node_node_type.push(n) if (n.$type==='integer') return node_primitive_integer.push(n) if (primitive_types.includes(n.$type)) return node_primitive.push(n) return node_custom.push(n) }) const edge_node_type = [] const edge_property = [] const edge_primitive = [] const edge_property_type_node = [] it.edges.forEach(e=> { const target = it.flats[e.target] if (target && primitive_types.includes(target.$type)) return edge_primitive.push(e) if (e.key==='$property_type') return edge_property_type_node.push(e) return edge_property.push(e) }) Object.values(it.flats).forEach(n=> { if (!render_primitive && primitive_types.includes(n.$type)) return edge_node_type.push({origin: n.$type, target: n.$id, key: '$type'}) }) const node_to_dot = n=> { let vstr = null if ('$value' in n || primitive_value_typeofs.includes(typeof n.$value)) { const v_s = typeof n.$value==='object' ? Array.isArray(n.$value) ? `[${n.$value.length}]` : n.$value!==null ? `{${Object.keys(n.$value).join(', ')}}` : '(null)' : JSON.stringify(n.$value) vstr = `<$value> ${(v_s.substr(0, 20)+(v_s.length>20?'...':'')).replace(/(["<>{}|])/g, '\\$1') }` } const meta_handled = new Set('$id,$type,$value,$property,$property_type,$bootstrapped,$to_js'.split(',')) const meta_unhandled = Object.keys(n).filter(k=> !meta_handled.has(k)) const header_entries = [ `<$id> ${n.$id}`, `<$type> (${n.$type})`, vstr, ...'$bootstrapped,$to_js'.split(',').filter(k=> k in n).map(k=> `<${k}> ${k}`), ...meta_unhandled.map(k=> `<${k}> (?) ${k}`), ].filter(Boolean) const header = `{<$> | {${header_entries.join(' | ')}}}` const pstr = Object.keys(n.$property).map(k=> `<${k}> ${k}`).join(' | ') return `"${n.$id}" [label="${useLR?'':'{'}${header}${pstr?' | '+pstr:''}${useLR?'':'}'}"];` } return ` digraph mygraph { ${useLR?'rankdir=LR;':''} nodesep=0.4; ranksep=1.5; compound=true; // something for clustering? node [shape="record"]; ${cluster_node_types?'subgraph cluster_0 {':''} node [color="blue"]; ${node_node_type.map(node_to_dot).join('\n\t\t')} ${cluster_node_types?'}':''} node [color="black"]; ${node_custom.map(node_to_dot).join('\n\t')} ${render_primitive?'':'/*'} node [color="#cfff00"]; ${node_primitive_integer.map(node_to_dot).join('\n\t')} node [color="green"]; ${node_primitive.map(node_to_dot).join('\n\t')} ${render_primitive?'':'*/'} node [shape="ellipse", color="orange"]; ${it.refs_dangling.map(n=> `"${n}";`).join(' ')} node [shape="box", color="orange"]; ${it.meta_key_unhandled.map(n=> `"${n}";`).join(' ')} node [shape="ellipse", color="red"]; edge [color="gray", weight=0]; ${edge_node_type.map(e=> `"${e.origin}":"$id":e -> "${e.target}":"$type":w;`).join('\n\t')} edge [color="black", weight=1]; ${edge_property.map(e=> `"${e.origin}":"${e.key}":e -> "${e.target}":"$":w;`).join('\n\t')} edge [color="cyan", weight=3]; ${edge_property_type_node.map(e=> `"${e.origin}":"$id":e -> "${e.target}":"$":w;`).join('\n\t')} ${render_primitive?'':'/*'} edge [color="green", weight=1.5]; ${edge_primitive.map(e=> `"${e.origin}":"${e.key}":e -> "${e.target}":"$":w;`).join('\n\t')} ${render_primitive?'':'*/'} } ` } const nested_map = (fn, key_fn=k=>k)=> function mapper(it, key) { if (typeof it==='object') { if (it===null) { return fn(it, key) } if (Array.isArray(it)) { return it.map(mapper) } return Object.fromEntries(Object.entries(it).map(([k, v])=> [key_fn(k, key, v), mapper(v, k)])) } return fn(it, key) } const nodeedges_clean_ids_for_dot = it=> { const clean_id = id=> id.replace(/[<>{}"|\\]/g, '_') const nested_clean = nested_map((v, k)=> typeof v==='string'? clean_id(v): v, clean_id) const ret = nested_clean(it) return ret } module.exports = {nodeedges_to_dot_text, nodeedges_clean_ids_for_dot} return module.exports }), loading: false, value: null, }, "nodenotes-mvp-3jan2020.yaml": { varname: "nodenotes_mvp_3jan2020_yaml", load: (function (require, observable_require) { const module = {exports: {}} module.exports = `title: nodenotes-mvp-3jan2020 created_by: Leonard Pauli, 3 jan 2020 comment: minimal full application with ability to edit itself descibed declaratively comment.2: invoke rim_3jan2020 nodenotes-mvp-3jan2020.yaml to start serving frontend-only webapp in dev mode on-start: on-start nodes: - id: on-start type: command kind: live-serve-web-app app: nn-app - id: nn-app type: app view: id: app-view type: view subviews: - id: wsp-container-view type: view-scroll subviews: - wsp-canvas-view - wsp-node-view - id: canvas-info-message-view type: view layout-self: id: canvas-info-message-view-layout-self type: view-layout kind: absolute origin: bottom-left subviews: - id: canvas-info-message-view-text type: view-text text: info-message-text - id: wsp-node-view type: view subviews: - id: wsp-canvas-view type: view subviews: - id: info-message-text type: text value: - type: string value: "Hello there, " - type: integer-to-string input: app-mouse-x - id: app-mouse type: property-value-by-key of: nn-app key: type: string value: mouse - id: app-mouse-x type: property-value-by-key of: app-mouse key: type: string value: mouse ` return module.exports }), loading: false, value: null, }, "rim_new.js": { varname: "rim_new_js", load: (function (require, observable_require) { const module = {exports: {}} const {json_as_rimraw_to_nodeedges} = require('./json_as_rimraw_to_nodeedges.js') const rim_new = (()=> { const rim = {} rim.error = ({message, ...rest})=> { const restkeys = Object.keys(rest) const reststr = (restkeys.length && ` (meta: ${restkeys})` || '') const error = new Error(`rim (from api): ${message}`+reststr) console.error({message, ...rest}) error.meta = rest throw error } const ctx = rim.ctx = { id_groups: {}, flats: {}, edges: [], refs_dangling: [], meta_key_unhandled: [], } rim.meta_key_unhandled = ()=> ctx.meta_key_unhandled // TODO: maybe as histogram instead? const addSub = sub=> { if (sub.flats) { const duplicates = Object.keys(sub.flats).map(k=> { if (k in ctx.flats) return k ctx.flats[k] = sub.flats[k] }).filter(Boolean) if (duplicates.length) rim.error({message: 'duplicate flat id', duplicates}) } if (sub.edges) ctx.edges.push(...sub.edges) if (sub.refs_dangling) ctx.refs_dangling.push(...sub.refs_dangling) if (sub.meta_key_unhandled) ctx.meta_key_unhandled.push(...sub.meta_key_unhandled) } rim.nodeById = id=> ctx.flats[id] rim.node = (rimraw)=> { const sub = json_as_rimraw_to_nodeedges(rimraw, {id_groups: ctx.id_groups}) addSub(sub) const flat = sub.flats[sub.id] if (!flat) return rim.error({message: 'rim.node of rimraw did not give a node', rimraw, sub}) return flat } rim.value = (node)=> node.$value rim.property_id = (node, key)=> { const kval = node.$property[key] return kval } rim.property = (node, key)=> { const kval = node.$property[key] return rim.nodeById(kval) } rim.comment = (node)=> node.$comment || '' // TODO: find parent comment? rim.travelUpTypechainUntilMetaNode = (node, key, {log = false} = {})=> { if (log) console.log(` travelUpTypechainUntilMetaNode ${node.$id}.${key}`) const is_root = node.$type === node.$id if (key in node || is_root) return node[key] const node_type_node = rim.nodeById(node.$type) if (!node_type_node) rim.error({message: 'parent node not found', parent_id: node.$type, node_type_node, node, key}) return rim.travelUpTypechainUntilMetaNode(node_type_node, key, {log}) } rim.type_chain = (node)=> { const is_root = node.$type === node.$id if (is_root) return [node.$id] const node_type_node = rim.nodeById(node.$type) if (!node_type_node) rim.error({message: 'parent node not found', parent_id: node.$type, node_type_node, node}) return [node.$id, ...rim.type_chain(node_type_node)] } rim.inherits = (node, $type)=> { return rim.type_chain(node).includes($type) } rim.travelUpTypechainUntilPropNodeId = (node, key, {log = false} = {})=> { if (log) console.log(` travelUpTypechainUntilPropNodeId ${node.$id}.${key}`) const is_root = node.$type === node.$id if (key in node.$property || is_root) return node.$property[key] const node_type_node = rim.nodeById(node.$type) if (!node_type_node) rim.error({message: 'parent node not found', parent_id: node.$type, node_type_node, node, key}) return rim.travelUpTypechainUntilPropNodeId(node_type_node, key, {log}) } rim.to_js = (node, {fn_body_key = '$to_js'} = {})=> { if (!node) return rim.error({message: 'rim.to_js expected node', node}) const fn_body_id = rim.travelUpTypechainUntilMetaNode(node, fn_body_key) if (!fn_body_id) rim.error({message: 'in rim.to_js, no fn body', node}) const fn_body_node = rim.nodeById(fn_body_id) const fn_body = rim.value(fn_body_node) const fn = new Function(['it', 'rim'], fn_body) const value = fn(node, rim) return value } rim.to_rim = (node)=> { const fn_body_id = rim.travelUpTypechainUntilMetaNode(node, '$to_rim', {log: false}) if (!fn_body_id) rim.error({message: 'in rim.to_rim, no fn body', node}) const fn_body_node = rim.nodeById(fn_body_id) const fn_body = rim.value(fn_body_node) const fn = new Function(['it', 'rim'], fn_body) const value = fn(node, rim) return value } rim.dictionary_keys = (node)=> { const val = rim.value(node) if (typeof val !== 'object' || val===null) return rim.error({message: 'expected dictionary node', node}) return Object.keys(val) } rim.dictionary_value = (node, key)=> { const val = rim.value(node) if (typeof val !== 'object' || val===null) return rim.error({message: 'expected dictionary node', node}) const hasVal = key in val && val[key] !== undefined if (!hasVal) return null return rim.nodeById(val[key]) } rim.list_length = (node)=> { const val = rim.value(node) if (typeof val !== 'object' || val===null) return rim.error({message: 'expected list node', node}) return val.length } rim.list_value = (node, index)=> { const val = rim.value(node) if (!Array.isArray(val)) return rim.error({message: 'expected list node', node}) const hasIndexNot = index < 0 || index >= val.length if (hasIndexNot) return null return rim.nodeById(val[index]) } return rim }) module.exports = {rim_new} return module.exports }), loading: false, value: null, }, "src_to_observablehq.js": { varname: "src_to_observablehq_js", load: (function (require, observable_require) { const module = {exports: {}} const {fs, path} = (typeof is_src_to_observablehq !== 'undefined'? (()=> { return {fs: {}, path: {}} })(): (()=> { const fs = require('fs').promises const path = require('path') return {fs, path} })()) const config = { dir: './', varname: 'src', outname: './tmp/observablehq-paste-src-in-2.js', skip: [ "json_as_rimraw_to_nodeedges-tests.yaml", "declarative-subparts-tests.yaml", "bootstrapped_nodes_tmp.yaml", ], stupid_filter_comments_and_empty_lines: true, } const main = async ()=> { const files = await fs.readdir(config.dir) const entries = [] const js_id = id=> id.replace(/[^A-Za-z0-9]/g, '_').replace(/^[0-9]+/, '_') const txt_filter = config.stupid_filter_comments_and_empty_lines ? t=> t.replace(/^(\t| )*((\/\/|#)[^\n]*|)\n/gm, '') : t=> t for (let fname of files) { if (config.skip.includes(fname)) continue if (fname.endsWith('.js')) { const varname = js_id(fname) const js = await fs.readFile(path.join(config.dir, fname), 'utf-8') const load = `(function (require, observable_require) { const module = {exports: {}} ${txt_filter(js)} return module.exports })` entries.push({varname, load, fname}) } else if (fname.endsWith('.yaml')) { const varname = js_id(fname) const yaml = await fs.readFile(path.join(config.dir, fname), 'utf-8') const load = `(function (require, observable_require) { const module = {exports: {}} module.exports = \`${txt_filter(yaml .replace(/`/g, '\\`') .replace(/\$/g, '\\$$') )}\` return module.exports })` entries.push({varname, load, fname}) } } const txt = `${config.varname} = ((observable_require)=> { const is_src_to_observablehq = true const modules = { ${entries.map(({varname, fname, load})=> `"${fname}": { varname: "${varname}", load: ${load}, loading: false, value: null, },`).join('\n\t\t')} } const require = _fname=> { const fname = _fname.replace(/^\\.\\//, '') const module = modules[fname] if (!module) throw new Error('module "'+fname+'" not found') if (!module.value) { if (module.loading) throw new Error('circular dep on module "'+fname+'"') module.loading = true module.value = module.load(require, observable_require) module.loading = false } return module.value } return { ${entries.map(({varname, fname})=> `${varname}: require("${fname}"),`).join('\n\t\t')} } })(require)` await fs.writeFile(config.outname, txt) } if (typeof is_src_to_observablehq === 'undefined') { main().catch(console.error) } return module.exports }), loading: false, value: null, }, "utils.js": { varname: "utils_js", load: (function (require, observable_require) { const module = {exports: {}} const pipeline_run = async (pipeline, {log = false} = {})=> pipeline.reduce((prev, pipe, i, all)=> prev.then(it=> { if (log) console.log(`(${i+1}/${all.length}): ${pipe.id || pipe.name}`) return typeof pipe === 'function'? pipe(it): pipe.fn(it) }), Promise.resolve(null)) const passthrough = fn=> a=> (fn(a), a) const inout_pipeline_run = async (pipeline, {log = false, ctx = {}} = {})=> { return pipeline.reduce((prev, pipe, i, all)=> prev.then(async it=> { const {in: _in, out, use, fn, fnctx, title} = pipe const valid = fn? !fnctx && !use: fnctx && use if (!valid) throw new Error('invalid pipe config ' + Object.keys(pipe)) const pipe_name = title || '' const pipe_fn = fnctx? fnctx(ctx): fn const pipe_in = _in? _in.map(k=> ctx[k]): [it] if (log) console.log(`\x1b[02m(${i+1}/${all.length}):\x1b[0m ${pipe_name}`) const pipe_out = await Promise.resolve(null).then(()=> pipe_fn(...pipe_in)) if (out) ctx[out] = pipe_out return pipe_out }), Promise.resolve(null)) } const error = ({at, ...rest})=> { const reststr = Object.entries(rest) .map(([k, v])=> `${k}: ${v}`).join('\n\t') const post = reststr? '; \n\t'+reststr: '' const err = new Error(`${at}: error${post}`) Object.assign(err, rest) return err } const assert_string = ({at, ...rest})=> { const type = typeof Object.values(rest)[0] const expected = 'string' if (type !== expected) throw error({at, ...rest, type, expected}) } module.exports = { inout_pipeline_run, pipeline_run, passthrough, error, assert_string, } return module.exports }), loading: false, value: null, }, } const require = _fname=> { const fname = _fname.replace(/^\.\//, '') const module = modules[fname] if (!module) throw new Error('module "'+fname+'" not found') if (!module.value) { if (module.loading) throw new Error('circular dep on module "'+fname+'"') module.loading = true module.value = module.load(require, observable_require) module.loading = false } return module.value } return { bootstrapped_nodes_yaml: require("bootstrapped_nodes.yaml"), declarative_to_js_bootstrap_tests_yaml: require("declarative_to_js_bootstrap_tests.yaml"), index_js: require("index.js"), js_str_pipe_js: require("js_str_pipe.js"), json_as_rimraw_to_nodeedges_js: require("json_as_rimraw_to_nodeedges.js"), nodeedges_to_dot_text_js: require("nodeedges_to_dot_text.js"), nodenotes_mvp_3jan2020_yaml: require("nodenotes-mvp-3jan2020.yaml"), rim_new_js: require("rim_new.js"), src_to_observablehq_js: require("src_to_observablehq.js"), utils_js: require("utils.js"), } })(require)36:[] 31:{"id":"7ef8d5ffd8a6dced","slug":"execution-dag-reduction-ranking","title":"Execution DAG reduction + ranking","thumbnail":"7356459c247461ac7b6bfbae3abec4d6a40661412bfff09b212a6e9253f3a2d0","access_level":"public","create_time":"$D2020-02-07T15:27:44.313Z","update_time":"$D2020-02-08T10:54:31.077Z","view_time":null,"first_public_time":"$D2020-02-07T21:55:40.862Z","has_unpublished_edits":null,"fork":false,"stars":5,"starred":false,"owner":{"type":"team","id":"2a5ee84d3cad3e57","login":"leonardpauli","name":"Leonard Pauli","avatar_url":"https://avatars-next.observableusercontent.com/9ea06552481b8da2b5612736cd90f6bfc88a75b62d026c85e7aeee43ebc0ea94","tier":"starter_2024"},"version":221,"publish_version":221,"role":null,"authored":false,"authors":[{"type":"individual","id":"8b1047ce3ae8a009","login":"leonardpauli","name":"Leonard Pauli","avatar_url":"https://avatars-next.observableusercontent.com/9ea06552481b8da2b5612736cd90f6bfc88a75b62d026c85e7aeee43ebc0ea94","tier":null}],"members":[{"type":"individual","id":"8b1047ce3ae8a009","login":"leonardpauli","name":"Leonard Pauli","avatar_url":"https://avatars-next.observableusercontent.com/9ea06552481b8da2b5612736cd90f6bfc88a75b62d026c85e7aeee43ebc0ea94","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":null,"type":"notebook","body":{"title":"Execution DAG reduction + ranking","cells":[{"id":0,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"adot`digraph blackbox_intro {\n rankdir=LR;\n node [color=black];\n\n subgraph cluster_1 {\n color=transparent;\n blackbox [label=\"blackbox\\n(pure logic)\"];\n input -> blackbox -> output;\n }\n external [constraint=false];\n output:se -> external:nw;\n external:w -> input:se;\n\n}`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"md`## Example`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"md`Below is a graph described with yaml (try edit it, *dynamic*, *output*, *integer*, and *integer_add* are available types). It is then run through the algorithm to find cross-points (cyan), reduce it to them, and rank reductions/functions into execution order. Use the iteration stepper to view an animation of the algorithm below.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":203,"value":"viewof file_node_yaml = code(`\n$type: nn_file\ntitle: declarative_to_js_bootstrap_tests.yaml\ncreated_by: Leonard Pauli, 7 jan 2020\ncommand: {$: start}\n# include: \"./bootstrapped_nodes.yaml\"\n\nnodes:\n\n- $id: start\n $type: integer_add\n input:\n - $id: user_input\n $type: dynamic\n input_type: {$: integer}\n - 2\n - $id: second_output\n $type: output\n input: {$: some_intermediate}\n output_type: {$: integer}\n # - {$: start}\n - {$: third_output}\n\n- $id: some_intermediate\n $type: integer_add\n input:\n - 3\n - 4\n - {$: user_input}\n - {$: third_output}\n\n- $id: third_output\n $type: output\n input: {$: third}\n output_type: {$: integer}\n\n- $id: third\n $type: integer_add\n input:\n - {$: user_input}\n - 9\n`, 'yaml', true)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"graphs = src.index_js.dag_reduced_iterations_dot_from_yaml(src.bootstrapped_nodes_yaml, file_node_yaml|| src.declarative_to_js_bootstrap_tests_yaml)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":183,"value":"viewof visgraphi = {\n const vmax = graphs.length-1\n \n const start = html``\n const end = html``\n const a = html``\n const b = html``\n const t = html``\n const o = html`${start} ${a} iteration ${t} of ${vmax} ${b} ${end}`\n const update = v=> (t.innerText = o.value = Math.max(0, Math.min(v, vmax)), o.dispatchEvent(new CustomEvent('input')))\n\n start.onclick = ()=> update(0)\n end.onclick = ()=> update(vmax)\n a.onclick = ()=> update(o.value-1)\n b.onclick = ()=> update(o.value+1)\n \n update(0)\n \n return o\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":158,"value":"adot.bind(this)`${visgraph}${{duration: 400, fit: true, width: width, height: 500}}`","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"viewof visgraph = {\n const o = md`(dot)`\n o.value = graphs[visgraphi].dot\n return o\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"md`## Source blob`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"md`## Dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":205,"value":"code = (t, lang='js', hide=false)=> {\n const o = hide?md`(${lang})`:md`\\`\\`\\`${lang}\n${t.trim()}\n\\`\\`\\``\n o.value = t\n return o\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":58,"value":"md`#### Using dot + [d3-graphviz](https://observablehq.com/@magjac/introduction-to-d3-graphviz) for visualization`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"d3 = require(\"d3-graphviz\", \"d3-selection\", \"d3-transition\", \"d3-ease\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":47,"value":"import {slider, button, checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"import {adot, logoDots, logoDot} from \"@magjac/d3-graphviz\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"import {slide, slide_style} from \"@mbostock/slide\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":55,"value":"slide_style","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 32:"$31:body"