31:T741,md` ## Previous/other work - [An earlier attempt at visualizing JS execution](https://visualized-execution.js.org/) ([and accompanying notebook](https://observablehq.com/@kelleyvanevert/visualizing-js-execution)), hand-constructing a basic interpreter for the whole language. This is tedious of course, but does lead to very fine-grained control, with all the accompanying visualization perks. - A React hooks execution visualizer that sparked renewed interested in execution visualization efforts, because of the strictly harder context. ## Artefacts - [Proof-of-concept visualizer, needs work](https://epic-curran-35ad59.netlify.com/) - [AST explorer with the transpiler](https://astexplorer.net/#/gist/ca504f9c414704245b5b4bf816bcf4dd/latest) - [CodeSandbox with the React interop idea](https://codesandbox.io/s/generator-react-components-uwhtz?fontsize=14&hidenavigation=1&theme=dark) - [GH repo](https://github.com/kelleyvanevert/js_execution_stepping_through_meta_syntactic_transform) ## The idea in a nutshell `32:T13be,!show_info ? md`*Use the toggle*` : md` The idea is to _transpile_ ("lift") a piece of normal JavaScript code into _one giant iterator_, that performs two tasks simultaneously, while stepping through: - execution the original code _as it was_; - and _yielding_ back execution information for visualization purposes. For example, we'd take this code: \`\`\`js function app() { const js = { invented: 1995, usage: "everywhere", paradigms: [ "multi", "event-driven", "imperative", "functional", "object-oriented" ] }; } \`\`\` and translate it into something like this: \`\`\`js function* app() { yield _stm("VariableDeclaration", ...); const js = yield _expr("ObjectExpression", ..., { invented: yield _expr("NumericLiteral", ..., 1995), usage: yield _expr("StringLiteral", ..., "everywhere"), paradigms: yield _expr("ArrayLiteral", ..., [ yield _expr("StringLiteral", ..., "multi"), yield _expr("StringLiteral", ..., "event-driven"), yield _expr("StringLiteral", ..., "imperative"), yield _expr("StringLiteral", ..., "functional"), yield _expr("StringLiteral", ..., "object-oriented") ]) }); } \`\`\` At the places of the ellipses, we'd put information about the origin source location of the AST node, so that we would be able to highlight the relevant code while stepping through the program. Important detail: we also need to transpile all user-defined functions into generator functions, and then yield over control to them when calling them. For example: \`\`\`js function* userFn() { // ... } yield* userFn(...) \`\`\` This also means that generator functions are not supported in the user's code 🤷‍♀️ (until I spend some time cleverly crafting their transpilation somehow). ## Some notable and mostly overcome problems ### Syntactic call-site context binding of function invocations It was a bit tricky to get function calling to work as expected. JavaScript has an odd language feature where the semantics of a call expression depends on whether the callee is syntactically either a member expression or not. I call this _syntactic call-site context binding._ For example, \`o.f(41)\` sets \`this\` inside of the function to be \`o\`, whereas \`(yield _expr(..., o.f))(41)\`, even though the callee still refers to the same function, sets \`this\` inside of the function to \`undefined\` (or whatever). To overcome this problem, you have to perform a more subtle transpilation. The end-result is as follows. We transpile JS like this: \`\`\`js o.f(a, b); \`\`\` into stuff like this: \`\`\`js yield _expr("o.f(a, b)", yield* ( (yield _expr("o.f", (yield _expr("o", TMP = o)).f)) .call( TMP, yield _expr("a", a), yield _expr("b", b) ) ) ) \`\`\` Note the temporary storage of the object expression, because it might be a complex expression which should not be evaluated twice. Also, if the member expression is computed (with brackets \`[ ]\`), the computed property should also be transpiled correctly. ### Interop with the standard library We're "lifting" the code to a different execution semantics. This also means that interop is broken unless cleverly avoided/fixed. There's two "directions" in which the interopability needs fixing: gettings results _back_ from non-user-defined functions, and _passing callbacks_ to other code. (Data is still data, so there's no worry there.) The first problem is reasonably easily solved (disregarding some edge-cases that would require more work). We can just conditionally _lift_ the result of function calls: \`\`\`js yield* _lift(r = (/* some call expression */)) \`\`\` If the function call result is an iterator as a result of our own making, we can leave it be, and if it's just data, we simply lift it to be a trivial iterator: \`\`\`js (function*() { return r; })(); \`\`\` The second problem is considerably harder, because we will be passing our lifted callback functions into all kinds of unknowing APIs: \`\`\`js (/* some array expression */).map(function* (number) { yield _stm("ReturnExpression"); return yield _expr(...); }) \`\`\` I don't think there's any way to cleverly side-step this problem, we just have to make sure these APIs happen to work with iterators as well. For the sake of our visualizer though, that usually doesn't mean much more than the common standard library functions like \`Array::map\`, etc. And this is totally achievable with a bit of old-school (gotta love JavaScript!) monkey-patching: \`\`\`js const _Array_map = Array.prototype.map; Array.prototype.map = function(callback) { return (callback instanceof function*() {}.constructor ? function*(callback) { console.log("!! using lifted version of Array::map"); const mapped = []; for (let i = 0; i < this.length; i++) { mapped[i] = yield* callback(this[i], i, this); } return mapped; } : _Array_map ).apply(this, arguments); }; // etc. \`\`\` `33:T5ab,{ const Y = code.split("\n").length; const hpad = 3; const vpad = 0; const el = this && this.Y === Y && this.fontCss === fontCss ? this : html`

${Array.from({ length: Y }) .map( () => `

` ) .join("")}

`; el.Y = Y; el.fontCss = fontCss; el.querySelector("pre").innerHTML = highlight_bold( code, step.info ? step.info.loc : undefined ); const markers = el.querySelectorAll(".marker"); if (step.info && step.info.loc) { const ranges = loc_to_ranges(code, step.info.loc); markers.forEach((marker, i) => { const range = ranges[Math.min(i, ranges.length - 1)]; marker.style.background = colors[step.info.time].bg; marker.style.top = `${(range.line - 1) * H - vpad}px`; marker.style.height = `${H + 2 * vpad}px`; marker.style.left = `${range.a * W - hpad}px`; marker.style.width = `${(range.b - range.a) * W + 2 * hpad}px`; }); } else { markers.forEach(marker => { marker.style.width = marker.style.height = 0; }); } return el; }34:T1b0a,visitor = { let _cache_id = -1; const visitor = { VariableDeclaration(path) { // This is an ugly trick to get the scope data "out" easily // If we leave the variables as let and const, then we run into non-initialized errors // when reporting back the scope's contents. path.node.kind = "var"; }, Statement(path) { if (t.isBlockStatement(path.node)) return; path.insertBefore( t.expressionStatement( t.yieldExpression( t.callExpression(t.identifier("_app._stm"), [ meta(path.node, path.scope, "before") ]) ) ) ); const report_before = path.getSibling(path.key - 1); report_before.skip(); path.insertAfter( t.expressionStatement( t.yieldExpression( t.callExpression(t.identifier("_app._stm"), [ meta(path.node, path.scope, "after") ]) ) ) ); const report_after = path.getSibling(path.key + 1); report_after.skip(); if (t.isReturnStatement(path)) { path.scope._hasReturn = true; const return_value = t.identifier("_return"); path.replaceWith( t.variableDeclaration("var", [ t.variableDeclarator(return_value, u(path.node.argument)) ]) ); path.skip(); path .get("declarations")[0] .get("init") .traverse(visitor); // recurse report_after.insertAfter(t.returnStatement(return_value)); report_after.getSibling(report_after.key + 1).skip(); } }, Function(path) { if (path.node.generator) { throw new Error("Generator functions are not supported yet"); } if (t.isArrowFunctionExpression(path)) { const block = t.isBlockStatement(path.node.body); path.replaceWith( t.yieldExpression( t.callExpression(t.identifier("_app._expr"), [ meta( path.node, // No idea why, but for some // reason the scope of an ArrowFunctionExpression node // is not the surrounding scope of it as an expression, // but rather it's own scope. Not what we're looking for! path.parentPath.scope, "after" ), t.callExpression( t.memberExpression( t.functionExpression( null, path.node.params, block ? path.node.body : t.blockStatement([ t.returnStatement(u(path.node.body)) ]), true ), t.identifier("bind") ), [t.thisExpression()] ) ]) ) ); path.skip(); const body = path .get("argument") .get("arguments")[1] .get("callee") .get("object") .get("body"); if (block) { body.traverse(visitor); // recurse } else { body .get("body")[0] .get("argument") .traverse(visitor); // recurse } } else { path.node.generator = true; } }, Expression(path) { // console.log("E", path.node.type, "@", path.node.loc.start); // preventloop(); if (t.isCallExpression(path)) { const contextual = t.isMemberExpression(path.get("callee")); // Automatically works even if non-contextual, // because then the absence of the assignment, // the cached item will undefined const cached_context = contextual ? t.memberExpression( t.identifier("_cache"), t.numericLiteral(++_cache_id), true ) : t.identifier("undefined"); const computed = contextual ? path.node.callee.computed : "irrelevant"; const report_before_call = t.yieldExpression( t.callExpression(t.identifier("_app._expr"), [ meta(path.node, path.scope, "before") ]) ); path.replaceWith( t.yieldExpression( t.callExpression(t.identifier("_app._expr"), [ meta(path.node, path.scope, "after"), t.yieldExpression( t.callExpression(t.identifier("_app._lift"), [ t.callExpression( t.memberExpression( contextual ? t.yieldExpression( t.callExpression(t.identifier("_app._expr"), [ meta(path.node.callee, path.scope, "after"), t.memberExpression( t.assignmentExpression( "=", cached_context, u(path.node.callee.object) ), computed ? u(path.node.callee.property) : path.node.callee.property, computed ) ]) ) : u(path.node.callee), t.identifier("call") ), [cached_context, ...path.node.arguments.map(u)] ) ]), true ) ]) ) ); path.skip(); const expr = path .get("argument") // yielded value .get("arguments")[1]; const call = expr.get("argument").get("arguments")[0]; let caller = call.get("callee").get("object"); if (contextual) { caller = caller.get("argument").get("arguments")[1]; caller .get("object") .get("right") .traverse(visitor); // recurse if (computed) { caller.get("property").traverse(visitor); // recurse } } else { caller.traverse(visitor); // recurse } call .get("arguments") .slice(1) .forEach(argPath => { argPath.traverse(visitor); // recurse }); } else { path.replaceWith( t.yieldExpression( t.callExpression(t.identifier("_app._expr"), [ meta(path.node, path.scope, "after"), path.node ]) ) ); path.skip(); path .get("argument") .get("arguments")[1] .traverse(visitor); // recurse } } }; return visitor; }35:Td80,{ const _Array_find = Array.prototype.find; Array.prototype.find = function(callback) { return (callback instanceof function*() {}.constructor ? function*(callback) { console.log("!! using lifted version of Array::find"); for (let i = 0; i < this.length; i++) { if (yield* callback(this[i], i, this)) { return this[i]; } } } : _Array_find ).apply(this, arguments); }; const _Array_findIndex = Array.prototype.findIndex; Array.prototype.findIndex = function(callback) { return (callback instanceof function*() {}.constructor ? function*(callback) { console.log("!! using lifted version of Array::findIndex"); for (let i = 0; i < this.length; i++) { if (yield* callback(this[i], i, this)) { return i; } } } : _Array_findIndex ).apply(this, arguments); }; const _Array_map = Array.prototype.map; Array.prototype.map = function(callback) { return (callback instanceof function*() {}.constructor ? function*(callback) { console.log("!! using lifted version of Array::map"); const mapped = []; for (let i = 0; i < this.length; i++) { mapped[i] = yield* callback(this[i], i, this); } return mapped; } : _Array_map ).apply(this, arguments); }; const _Array_forEach = Array.prototype.forEach; Array.prototype.forEach = function(callback) { return (callback instanceof function*() {}.constructor ? function*(callback) { console.log("!! using lifted version of Array::forEach"); for (let i = 0; i < this.length; i++) { yield* callback(this[i], i, this); } } : _Array_forEach ).apply(this, arguments); }; const _Array_filter = Array.prototype.filter; Array.prototype.filter = function(callback) { return (callback instanceof function*() {}.constructor ? function*(callback) { console.log("!! using lifted version of Array::filter"); const filtered = []; for (let i = 0; i < this.length; i++) { if (yield* callback(this[i], i, this)) { filtered.push(this[i]); } } return filtered; } : _Array_filter ).apply(this, arguments); }; const _Array_reduce = Array.prototype.reduce; Array.prototype.reduce = function(callback) { return (callback instanceof function*() {}.constructor ? function*(callback) { console.log("!! using lifted version of Array::reduce"); const using_initial = arguments.length >= 2; let memo = using_initial ? arguments[1] : this[0]; for (let i = using_initial ? 0 : 1; i < this.length; i++) { memo = yield* callback(memo, this[i], i, this); } return memo; } : _Array_reduce ).apply(this, arguments); }; const _Array_flatMap = Array.prototype.flatMap; Array.prototype.flatMap = function(callback) { return (callback instanceof function*() {}.constructor ? function*(callback) { console.log("!! using lifted version of Array::flatMap"); return this.map(callback).flat(); } : _Array_flatMap ).apply(this, arguments); }; return md`## Lifted standard library functions (In this cell)`; }36:T418,// highlight( // code, // step.info ? step.info.loc : undefined, // step.type === "statement" ? "#fffad2" : "#d5e6ed" // ) function highlight(code, loc, color = "#d5e6ed") { if (!loc) { return html`${code}`; } const lines = code.split("\n"); const before = [ ...lines.slice(0, loc.start.line - 1), lines[loc.start.line - 1].slice(0, loc.start.column) ].join("\n"); const highlighted = loc.start.line === loc.end.line ? lines[loc.start.line - 1].slice(loc.start.column, loc.end.column) : [ lines[loc.start.line - 1].slice(loc.start.column), ...lines.slice(loc.start.line, loc.end.line - 1), lines[loc.end.line - 1].slice(0, loc.end.column) ].join("\n"); const after = [ lines[loc.end.line - 1].slice(loc.end.column), ...lines.slice(loc.end.line) ].join("\n"); return html`${before}${highlighted}${after}`; }37:[] 2f:{"title":"Visualizing JS execution #2","cells":[{"id":0,"value":"md`# Visualizing JS execution #2`","pinned":false,"hidden":false,"mode":"ojs"},{"id":311,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":338,"value":"viewof show_info = toggle({\n title: 'Toggle details'\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":343,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":349,"value":"md`## Example`","pinned":false,"hidden":false,"mode":"ojs"},{"id":198,"value":"viewof step = mapinputdata(\n slider({\n title: \"Execution step\",\n value: 0,\n min: 0,\n max: steps.length - 1,\n step: 1\n }),\n stepno => {\n const step = steps[stepno];\n step.no = stepno;\n return step;\n }\n)","pinned":false,"hidden":false,"mode":"ojs"},{"id":423,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":359,"value":"step.error\n ? html`

Error: ${step.error.message}

`\n : html`

${\n step.info.time === \"before\"\n ? `about to ${step.type === \"statement\" ? \"execute\" : \"evaluate\"}`\n : step.type === \"statement\"\n ? \"executed\"\n : \"evaluated\"\n } ${step.type} of type ${\n step.info.type\n } ${\n step.info.time === \"after\" && step.type === \"expression\"\n ? `to:`\n : \"\"\n }

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":240,"value":"step.type === \"expression\" ? step.value : md``","pinned":false,"hidden":false,"mode":"ojs"},{"id":530,"value":"md`***The current scope's contents:***`","pinned":false,"hidden":false,"mode":"ojs"},{"id":509,"value":"step.info ? step.info.scope : md``","pinned":false,"hidden":false,"mode":"ojs"},{"id":533,"value":"md`---`","pinned":false,"hidden":false,"mode":"ojs"},{"id":29,"value":"viewof code = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":690,"value":"{\n const ast = babel.parse(code);\n traverse(ast, visitor);\n const generated_code = generate(ast)\n .code.replace(/\"([a-z]+)\":[ ]?/g, \"$1:\")\n .replace(/(|,|}|},|{)\\n[ ]*/g, \"$1\");\n\n const el = html``;\n el.value = generated_code;\n el.onclick = () => el.setSelectionRange(0, el.value.length);\n return html`${el}
(${generated_code.length} characters = ${Math.floor(\n 100 * (generated_code.length / code.length)\n )}% of original)`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":142,"value":"app = {\n const ast = babel.parse(code);\n traverse(ast, visitor);\n const transpiled = generate(ast)\n .code // bare-bones minification\n .replace(/\"([a-z]+)\":[ ]?/g, \"$1:\")\n .replace(/(|,|}|},|{)\\n[ ]*/g, \"$1\");\n\n const app = eval(`\n function* _app() {\n const _cache = {};\n const _return = undefined;\n ${transpiled}\n }\n _app;\n `);\n\n app._lift = r => {\n if (r && r[Symbol.iterator] && typeof r !== \"string\" && !Array.isArray(r)) {\n return r;\n } else {\n return (function*() {\n return r;\n })();\n }\n };\n\n app._stm = info => {\n return {\n type: \"statement\",\n info\n };\n };\n\n app._expr = (info, value) => {\n return {\n type: \"expression\",\n info,\n value\n };\n };\n\n return app;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":180,"value":"steps = {\n const stepper = app();\n let iterator_state = stepper.next();\n\n const steps = [iterator_state.value];\n\n try {\n while (true) {\n iterator_state = stepper.next(iterator_state.value.value);\n if (iterator_state.done) {\n break;\n }\n steps.push(iterator_state.value);\n }\n } catch (error) {\n steps.push({ error });\n }\n\n return steps;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":160,"value":"md`## The transpiler`","pinned":false,"hidden":false,"mode":"ojs"},{"id":90,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":156,"value":"md`## Helpers`","pinned":false,"hidden":false,"mode":"ojs"},{"id":98,"value":"function meta(node, scope, time) {\n // return json(node.type);\n const metadata = {\n time,\n loc: node.loc,\n type: node.type\n };\n\n if (scope) {\n metadata.scope = Object.fromEntries(\n Object.keys(scope.bindings).map(id => [id, { $ast: t.identifier(id) }])\n );\n if (scope._hasReturn) {\n metadata.scope[\"$return\"] = { $ast: t.identifier(\"_return\") };\n }\n }\n\n return json(metadata);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":87,"value":"// A dirty trick to get expressionPath.traverse(visitor)\n// to work also on the top level expression:\n// just perform it on a sequence expression wrapped\n// version of the expression\nfunction u(expressionNode) {\n return t.sequenceExpression([expressionNode]);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"function json(data) {\n if (typeof data === \"string\") {\n return t.stringLiteral(data);\n } else if (typeof data === \"number\") {\n return t.numericLiteral(data);\n } else if (data === null) {\n return t.nullLiteral();\n } else if (data === void 0) {\n return t.identifier(\"undefined\");\n } else if (data instanceof Array) {\n return t.arrayExpression(data.map(json));\n } else if (data.$ast) {\n return data.$ast;\n } else {\n return t.objectExpression(\n Object.entries(data).map(([key, value]) => {\n return t.objectProperty(t.stringLiteral(key), json(value));\n })\n );\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":478,"value":"colors = ({\n before: { bg: \"#fbf1a0\", fg: \"#d0bf3a\" },\n after: { bg: \"#4dd4aa\", fg: \"#2eb98e\" }\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"md`## Babel packages`","pinned":false,"hidden":false,"mode":"ojs"},{"id":115,"value":"generate = (await require('https://bundle.run/@babel/generator@7.8.0')).default","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"t = require('https://bundle.run/@babel/types@7.8.0')","pinned":false,"hidden":false,"mode":"ojs"},{"id":24,"value":"traverse = (await require('https://bundle.run/@babel/traverse@7.8.0')).default","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"babel = require('https://bundle.run/@babel/parser@7.8.0')","pinned":false,"hidden":false,"mode":"ojs"},{"id":192,"value":"md`## Other dependencies`","pinned":false,"hidden":false,"mode":"ojs"},{"id":171,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":418,"value":"function highlight_bold(code, loc) {\n if (!loc) {\n return code;\n }\n\n const lines = code.split(\"\\n\");\n\n const before = [\n ...lines.slice(0, loc.start.line - 1),\n lines[loc.start.line - 1].slice(0, loc.start.column)\n ].join(\"\\n\");\n\n const highlighted =\n loc.start.line === loc.end.line\n ? lines[loc.start.line - 1].slice(loc.start.column, loc.end.column)\n : [\n lines[loc.start.line - 1].slice(loc.start.column),\n ...lines.slice(loc.start.line, loc.end.line - 1),\n lines[loc.end.line - 1].slice(0, loc.end.column)\n ].join(\"\\n\");\n\n const after = [\n lines[loc.end.line - 1].slice(loc.end.column),\n ...lines.slice(loc.end.line)\n ].join(\"\\n\");\n\n return `${before}${highlighted}${after}`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":415,"value":"function loc_to_ranges(code, loc) {\n const { start, end } = loc;\n const codelines = code.split(\"\\n\");\n return start.line === end.line\n ? [{ line: start.line, a: start.column, b: end.column }]\n : [\n {\n line: start.line,\n a: start.column,\n b: codelines[start.line - 1].length\n },\n ...Array.from({ length: end.line - start.line - 1 })\n .map((_, i) => i + start.line + 1)\n .map(line => ({ line, a: 0, b: codelines[line - 1].length })),\n { line: end.line, a: 0, b: end.column }\n ];\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":401,"value":"H = 28","pinned":false,"hidden":false,"mode":"ojs"},{"id":383,"value":"viewof W = {\n const X = 50;\n\n const el = html`${Array(X + 1).join(\"X\")}`;\n\n setTimeout(() => {\n el.value = el.clientWidth / X;\n el.dispatchEvent(new CustomEvent(\"input\"));\n }, 20);\n\n return el;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":398,"value":"fontCss = `\nfont-family: Menlo, Consolas, monospace;\nfont-size: 20px;\nline-height: ${H}px;\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":327,"value":"import { toggle, mapinputdata } from \"@kelleyvanevert/little-things\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":195,"value":"import { slider } from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W37","stdlib":"1","titling":"auto"}