2b:null 2c:["$","title",null,{"children":"Diagramming heap layout? | Kelley van Evert | Observable"}] 31:Ta2d,function forceRectCollide() { var nodes, sizes, masses; var size = constant([0, 0]); var strength = 1; var iterations = 1; function force() { var node, size, mass, xi, yi; var i = -1; while (++i < iterations) { iterate(); } function iterate() { var j = -1; var tree = d3.quadtree(nodes, xCenter, yCenter).visitAfter(prepare); while (++j < nodes.length) { node = nodes[j]; size = sizes[j]; mass = masses[j]; xi = xCenter(node); yi = yCenter(node); tree.visit(apply); } } function apply(quad, x0, y0, x1, y1) { var data = quad.data; var xSize = (size[0] + quad.size[0]) / 2; var ySize = (size[1] + quad.size[1]) / 2; if (data) { if (data.index <= node.index) { return; } var x = xi - xCenter(data); var y = yi - yCenter(data); var xd = Math.abs(x) - xSize; var yd = Math.abs(y) - ySize; if (xd < 0 && yd < 0) { var l = Math.sqrt(x * x + y * y); var m = masses[data.index] / (mass + masses[data.index]); if (Math.abs(xd) < Math.abs(yd)) { node.vx -= (x *= (xd / l) * strength) * m; data.vx += x * (1 - m); } else { node.vy -= (y *= (yd / l) * strength) * m; data.vy += y * (1 - m); } } } return ( x0 > xi + xSize || y0 > yi + ySize || x1 < xi - xSize || y1 < yi - ySize ); } function prepare(quad) { if (quad.data) { quad.size = sizes[quad.data.index]; } else { quad.size = [0, 0]; var i = -1; while (++i < 4) { if (quad[i] && quad[i].size) { quad.size[0] = Math.max(quad.size[0], quad[i].size[0]); quad.size[1] = Math.max(quad.size[1], quad[i].size[1]); } } } } } function xCenter(d) { return d.x + d.vx + sizes[d.index][0] / 2; } function yCenter(d) { return d.y + d.vy + sizes[d.index][1] / 2; } force.initialize = function(_) { sizes = (nodes = _).map(size); masses = sizes.map(function(d) { return d[0] * d[1]; }); }; force.size = function(_) { return arguments.length ? ((size = typeof _ === "function" ? _ : constant(_)), force) : size; }; force.strength = function(_) { return arguments.length ? ((strength = +_), force) : strength; }; force.iterations = function(_) { return arguments.length ? ((iterations = +_), force) : iterations; }; return force; }32:T8f6,{ btn; const height = 500; // const { heap } = describe(value); // const graphNodes = heap.map((_, at) => { // return render({ node: { category: "compound", at }, heap }); // }); const svg = d3.select(DOM.svg(width, 500)); const layers = { objects: svg.append("g"), references: svg.append("g") }; const references = layers.references .selectAll(".ref") .data( graphNodes .map((a, i) => { return a.refs.map(({ x, y, at: j }) => { return { i, a, j, b: graphNodes[j], x, y }; }); }) .flat() ) .join(enter => enter .append("path") .attr("stroke", "black") .attr("stroke-width", 2) .attr("stroke-linecap", "round") .attr("stroke-linejoin", "round") .attr("fill", "none") .attr("class", "ref") ); function draw() { layers.objects .selectAll(".node") .data(graphNodes) .attr("transform", d => `translate(${d.x} ${d.y})`); references.attr("d", ({ i, a, j, b, x, y }) => { return d_ref([a.x + x, a.y + y], [b.x, b.y + b.height / 2]); }); } // add nodes layers.objects .selectAll(".node") .data(graphNodes) .enter() .append(d => d.el) .attr("class", "node") .style("cursor", "pointer") .call( d3 .drag() .on("start", function(gn) { simulation.alpha(1).restart(); }) .on("drag", function(gn) { gn.x = gn.fx = d3.event.x; gn.y = gn.fy = d3.event.y; draw(); }) .on("end", function(gn) { delete gn.fx; delete gn.fy; }) ); draw(); const simulation = d3 .forceSimulation(graphNodes) // .force("place_top_left", forceTopLeft()) .force( "center", d3 .forceCenter() .x(width / 2) .y(250) ) .force("heap_references", forceHeapRef()) .force( "avoid_collisions", forceRectCollide() .strength(.3) .size(gn => [gn.width + 50, gn.height + 50]) ) // .force("connect_refs", connectRefs()) .on("tick", draw); return svg.node(); }33:T671,{ b; const height = 500; const { heap } = describe(value); const graphNodes = heap.map((_, at) => { return render({ node: { category: "compound", at }, heap }); }); positionHeuristically(graphNodes); const svg = d3.select(DOM.svg(width, 500)); const layers = { objects: svg.append("g"), references: svg.append("g") }; // add references const references = layers.references .selectAll(".ref") .data( graphNodes .map((a, i) => { return a.refs.map(({ x, y, at: j }) => { return { i, a, j, b: graphNodes[j], x, y }; }); }) .flat() ) .join(enter => enter .append("path") .attr("stroke", "black") .attr("stroke-width", 2) .attr("stroke-linecap", "round") .attr("stroke-linejoin", "round") .attr("fill", "none") .attr("class", "ref") ); function draw() { svg .selectAll(".node") .data(graphNodes) .attr("transform", d => `translate(${d.x} ${d.y})`); references.attr("d", ({ i, a, j, b, x, y }) => { return d_ref([a.x + x, a.y + y], [b.x, b.y + b.height / 2]); }); } // add nodes layers.objects .selectAll(".node") .data(graphNodes) .enter() .append(d => d.el) .attr("class", "node") .style("cursor", "pointer") .call( d3.drag().on("drag", function(graphNode) { graphNode.x = d3.event.x; graphNode.y = d3.event.y; draw(); }) ); draw(); return svg.node(); }34:Tb1e,render = { const CH = 16; // char height const R = 0.6; // char width/height for "Menlo" const CW = R * CH; // char width const PY = 10; const PX = 10; const RR = 6; // ref circle radius function renderKey(key) { const width = 0.85 * CW * key.length; return { width, el: svg`${key}` }; } return function render({ node, heap }, revived = []) { const { category, type, value, str, at } = node; if (category === "primitive") { const valueStr = type === "string" ? `"${value}"` : type === "symbol" ? str : String(value); const width = CW * valueStr.length; return { node, heap, width, height: CH, refs: [], el: svg`${valueStr}` }; } else if (revived[at]) { return revived[at]; } else { const { type, entries } = heap[at]; const gn = (revived[at] = { node, heap, width: PX, height: PY, refs: [] }); const children = []; for (const [key, node] of entries) { const k = renderKey(key); const { width, height, el } = node.category === "primitive" ? render({ node, heap }) : { node, heap, width: 2 * RR, height: CH, refs: [], el: svg`` }; if (node.category !== "primitive") { gn.refs.push({ x: k.width + PX + PX + RR, y: gn.height + CH / 2, at: node.at }); } children.push(svg` ${k.el} ${el} `); gn.width = Math.max(gn.width, k.width + PX + width + PX); gn.height += PY + height; } gn.width += PX; if (entries.length === 0) { gn.height += PY; } gn.el = svg` ${children} `; return gn; } }; }35:T60a,function describe(value, heap = [], map = new Map()) { if (typeof value === "string") { return { node: { category: "primitive", type: "string", value }, heap }; } else if (typeof value === "boolean") { return { node: { category: "primitive", type: "boolean", value }, heap }; } else if (typeof value === "number") { return { node: { category: "primitive", type: "number", value }, heap }; } else if (value === null) { return { node: { category: "primitive", type: "null", value }, heap }; } else if (value === void 0) { return { node: { category: "primitive", type: "undefined", value }, heap }; } else if (typeof value === "symbol") { return { node: { category: "primitive", type: "symbol", str: value.toString() }, heap }; } else if (map.has(value)) { return { node: { category: "compound", at: map.get(value) }, heap }; } else { const at = heap.length; map.set(value, at); const obj = { type: "object", entries: [] }; heap.push(obj); if (typeof value === "function") { obj.type = "function"; } else if ("then" in value && "catch" in value) { obj.type = "promise"; } else if (Array.isArray(value)) { obj.type = "array"; obj.length = value.length; } else { obj.cname = value.constructor.name; } Object.entries(value).forEach(([key, v]) => { const { node: described } = describe(v, heap, map); obj.entries.push([key, described]); }); return { node: { category: "compound", at }, heap }; } }36:T412,function undescribe({ node, heap }, revived = []) { if (node.category === "primitive") { if (node.type === "symbol") { const m = (node.str || "").match(/^Symbol$(.*)$$/); return Symbol(m ? m[1] : undefined); } else { return node.value; } } else if (revived[node.at]) { return revived[node.at]; } const obj = heap[node.at]; let value = {}; if (obj.type === "function") { value = (() => () => {})(); // To avoid the transpiler naming it `f value()` } else if (obj.type === "promise") { value = new Promise(() => {}); } else if (obj.type === "array") { value = []; value.length = obj.length; } else if (obj.cname) { const FAKE_CONSTRUCTORS = self.FAKE_CONSTRUCTORS || {}; value = new (FAKE_CONSTRUCTORS[obj.cname] = FAKE_CONSTRUCTORS[obj.cname] || eval(`function ${obj.cname}(){}; ${obj.cname}`))(); } revived[node.at] = value; obj.entries.forEach(([key, node]) => { value[key] = undescribe({ node, heap }, revived); }); return value; }37:[] 2f:{"id":"36301dce3c86052f","slug":"diagramming-heap-layout","title":"Diagramming heap layout?","thumbnail":"0b1042e4b1689f4d0c22776c81cc8f56573079915ce700bc5d48be33fc643b37","access_level":"public","create_time":"$D2020-02-05T20:16:33.683Z","update_time":"$D2020-02-14T21:00:16.764Z","view_time":null,"first_public_time":"$D2020-02-13T22:45:14.588Z","fork":false,"stars":43,"starred":false,"owner":{"type":"team","id":"cdda271b76654961","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":"starter_2024"},"version":1093,"publish_version":1093,"role":null,"authored":false,"authors":[{"type":"individual","id":"a35690ff73833989","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":null}],"members":[{"type":"individual","id":"a35690ff73833989","login":"kelleyvanevert","name":"Kelley van Evert","avatar_url":"https://avatars-next.observableusercontent.com/86df2bc54dd099fad6826dfcf7ae3dd97c5e0cdcf0cf3e0ac85ecd13e1938db2","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":14,"collection":null,"type":"notebook","body":{"title":"Diagramming heap layout?","cells":[{"id":0,"value":"md`# Diagramming heap layout?`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"md`Any (compound) node is layouted with SVG with known dimensions. Sure, it's a bit finicky, it's definitely less effort than having to coordinate the multi-step process of first DOM layouting, then measuring, then layouting the diagram. (Tried that.) It will have a rectangular bound, and then some reference starting positions within thsoe bounds. An example could be:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"svg``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":235,"value":"md`Forces:\n\n- \"Entry node\" has fixed position\n - Every other node aligns no higher, and to it's right\n- Nodes shouldn't overlap\n- Gravitate to top/left\n- References try to align left—right, with some fixed desired minimum distance\n- _I feel I need more, to stabilize the process ... or make it more deterministic_`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":721,"value":"md`## 4. Automatically layouting the heap`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":911,"value":"function connectRefs() {\n let nodes;\n\n function force() {\n for (let node of nodes) {\n if (node.isRefConnector) {\n node.vx = node.obj.vx;\n node.vy = node.obj.vy;\n node.x = node.obj.x + node.internalOffset.x;\n node.y = node.obj.y + node.internalOffset.y;\n node.fx = node.obj.fx ? node.obj.fx + node.internalOffset.x : undefined;\n node.fy = node.obj.fy ? node.obj.fy + node.internalOffset.y : undefined;\n }\n }\n }\n\n force.initialize = newNodes => {\n nodes = newNodes;\n };\n\n return force;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":852,"value":"function forceTopLeft(margin = 20) {\n let nodes;\n\n function force() {\n const max = {\n x: Math.max(...nodes.map(n => n.x)),\n y: Math.max(...nodes.map(n => n.y))\n };\n\n for (let node of nodes) {\n if (node.isRefDot) return;\n\n node.x = Math.max(margin, node.x);\n node.y = Math.max(margin, node.y);\n\n // TODO make this more intelligent ;)\n node.vx -= node.x / max.x;\n node.vy -= node.y / max.y;\n }\n }\n\n force.initialize = newNodes => {\n nodes = newNodes;\n };\n\n return force;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":864,"value":"$31","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":966,"value":"function forceHeapRef() {\n let nodes;\n\n function force(alpha) {\n for (let a of nodes) {\n for (let { x, y, at } of a.refs) {\n const b = nodes[at];\n // (a.x + x) + OFFSET ==== b.x\n // (a.y + y) ============= b.y + b.height/2\n const dx = b.x - (a.x + a.width) - 75;\n const dy = b.y + b.height / 2 - (a.y + y);\n\n b.vx -= dx * 0.1 * alpha;\n a.vx += dx * 0.1 * alpha;\n b.vy -= dy * 0.1 * alpha;\n a.vy += dy * 0.1 * alpha;\n }\n }\n }\n\n force.initialize = newNodes => {\n nodes = newNodes;\n };\n\n return force;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1024,"value":"graphNodes = {\n const { heap } = describe(value);\n\n return heap.map((_, at) => {\n const prev = (this && this[at]) || {};\n return {\n x: prev.x,\n y: prev.y,\n index: prev.index,\n ...render({ node: { category: \"compound\", at }, heap })\n };\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":783,"value":"value = {\n // const a = {};\n // a.b = { c: {}, d: { a } };\n\n // return a;\n\n const kelley = {\n name: \"Kelley!\",\n age: 27,\n hobbies: [\n { title: \"Programming\", level: 7 },\n { title: \"Sleeping\", level: 10 },\n { title: \"Teaching\", level: 6, a: {} }\n ]\n };\n // kelley.hobbies[0].sleeping = kelley.hobbies[1];\n return kelley;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":843,"value":"viewof btn = {\n const btn = html``;\n\n btn.onclick = () => {\n positionHeuristically(graphNodes);\n };\n\n return btn;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":957,"value":"$32","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":626,"value":"md`## 3. Drawing reference \"wires\"`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":701,"value":"md`Just scattering the objects randomly about the screen, and then drawing curvy references. The curve I'm drawing now isn't super pretty, but it's roughly the drawing logic I'd need for references... (drag the nodes)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":684,"value":"curve = d3.line().curve(d3.curveBasis)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":709,"value":"function add([a, b], [c, d]) {\n return [a + c, b + d];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":688,"value":"function d_ref(start, end) {\n const dx = end[0] - start[0];\n const dy = end[1] - start[1];\n\n const mid = add(start, [0.5 * dx, 0.5 * dy]);\n\n const c1 = add(start, [Math.max(50, 0.3 * dx), 0]);\n const c2 = add(end, [-Math.max(50, 0.3 * dx), 0]);\n\n const points = [start, c1, c2, end];\n\n if (dx < 0) {\n points.splice(2, 0, add(mid, [-dx, 0]), add(mid, [dx, 0]));\n }\n\n return curve(points);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":728,"value":"viewof b = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":734,"value":"function positionHeuristically(graphNodes) {\n return graphNodes.map(gn => {\n gn.x = (width - 200) * Math.random();\n gn.y = 400 * Math.random();\n return gn;\n });\n\n // First heuristic approach:\n // - Place in a grid at (col,row) coordinates\n // - Traverse the heap in some order (yet to determine best approach)\n // - Use col = reference depth on first encounter\n // - Use row = first available, downwards starting at the referencing object's row\n const grid = [];\n\n function visit(gn, parentRow = 0, depth = 0) {\n if (gn._pos) return;\n\n const col = depth;\n if (!grid[col]) grid[col] = [];\n let row = parentRow;\n while (grid[col][row]) row++;\n grid[col][row] = gn;\n gn._pos = [col, row];\n gn.x = 30 + 200 * col;\n gn.y = 30 + 100 * row;\n\n for (const [key, node] of gn.heap[gn.node.at].entries) {\n if (node.category === \"compound\") {\n visit(graphNodes[node.at], row, depth + 1);\n }\n }\n }\n\n visit(graphNodes[0]);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":629,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"md`## 2. Rendering graph nodes`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":490,"value":"md`\\`\\`\\`ts\ninterface GraphNode extends Description {\n el: SVGElement;\n width: number;\n height: number;\n refs: Array<{ x: number; y: number; at: number; }>;\n}\n\\`\\`\\``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":516,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":506,"value":"html`

\n ${[\n \"Kelley\",\n \"\",\n 42,\n 1.2345,\n true,\n false,\n null,\n undefined,\n Symbol(\"Hello\"),\n Symbol(),\n [\"A\", \"B\", \"C\"],\n { name: \"Kelley\", age: 27, hobbies: [\"A\", \"B\", \"C\"] }\n ].map(v => {\n const descr = describe(v);\n const { width, height, el } = render(descr);\n return svg``;\n })}\n

`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":420,"value":"md`## 1. Describe/undescribe`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":461,"value":"md`\\`\\`\\`ts\ntype Node =\n { category: \"primitive\"; type: \"string\" | \"boolean\" | \"number\" | \"null\" | \"undefined\"; value }\n | { category: \"primitive\"; type: \"symbol\"; str: string }\n | { category: \"compound\"; at: number };\n\ntype Compound =\n { entries: Array<[string, Node]> } & (\n { type: \"object\"; cname: string }\n | { type: \"function\" }\n | { type: \"promise\" }\n | { type: \"array\"; length: number }\n );\n\ntype Heap = Compound[];\ntype Description = { node: Node; heap: Heap };\n\nfunction describe(value: any): Description;\nfunction undescribe(description: Description): any;\n\\`\\`\\``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":418,"value":"$35","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":432,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":272,"value":"md`## Libs`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":857,"value":"function constant(_) {\n return function() {\n return _;\n };\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":276,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W37","stdlib":"1","titling":"auto"}} 30:"$2f:body"