2b:null 2c:["$","title",null,{"children":"Connections between core Clang classes (WIP) | Volodymyr Sapsai | Observable"}] 31:T2d44,dataset = [ { "name": "CompilerInstance", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1CompilerInstance.html", "connections": [ {"name": "Invocation", "type": "CompilerInvocation", "kind": "shared"}, {"name": "Diagnostics", "type": "DiagnosticsEngine", "kind": "shared"}, {"name": "Target", "type": "TargetInfo", "kind": "shared"}, {"name": "AuxTarget", "type": "TargetInfo", "kind": "shared"}, {"name": "FileMgr", "type": "FileManager", "kind": "shared"}, {"name": "SourceMgr", "type": "SourceManager", "kind": "shared"}, {"name": "ModuleCache", "type": "InMemoryModuleCache", "kind": "shared"}, {"name": "PP", "type": "Preprocessor", "kind": "shared"}, {"name": "Context", "type": "ASTContext", "kind": "shared"}, {"name": "ExternalSemaSrc", "type": "ExternalSemaSource", "kind": "shared"}, {"name": "Consumer", "type": "ASTConsumer", "kind": "owns"}, {"name": "CompletionConsumer", "type": "CodeCompleteConsumer", "kind": "owns"}, {"name": "TheSema", "type": "Sema", "kind": "owns"}, {"name": "FrontendTimerGroup", "type": "TimerGroup", "kind": "owns"}, {"name": "FrontendTimer", "type": "Timer", "kind": "owns"}, {"name": "TheASTReader", "type": "ASTReader", "kind": "shared"}, {"name": "ModuleDepCollector", "type": "ModuleDependencyCollector", "kind": "shared"}, {"name": "ThePCHContainerOperations", "type": "PCHContainerOperations", "kind": "shared"}, {"name": "DependencyCollectors", "type": "DependencyCollector", "kind": "shared"}, // ignore it is a vector, really {"name": "OwnedVerboseOutputStream", "type": "raw_ostream", "kind": "owns"}, {"name": "OutputStream", "type": "raw_pwrite_stream", "kind": "owns"}, ], }, { "name": "CompilerInvocation", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1CompilerInvocation.html", "connections": [ {"name": "LangOpts", "type": "LangOptions", "kind": "shared"}, {"name": "TargetOpts", "type": "TargetOptions", "kind": "shared"}, {"name": "DiagnosticOpts", "type": "DiagnosticOptions", "kind": "shared"}, {"name": "HeaderSearchOpts", "type": "HeaderSearchOptions", "kind": "shared"}, {"name": "PreprocessorOpts", "type": "PreprocessorOptions", "kind": "shared"}, {"name": "AnalyzerOpts", "type": "AnalyzerOptionsRef", "kind": "reference"}, {"name": "MigratorOpts", "type": "MigratorOptions", "kind": "copy"}, {"name": "CodeGenOpts", "type": "CodeGenOptions", "kind": "copy"}, {"name": "DependencyOutputOpts", "type": "DependencyOutputOptions", "kind": "copy"}, {"name": "FileSystemOpts", "type": "FileSystemOptions", "kind": "copy"}, {"name": "FrontendOpts", "type": "FrontendOptions", "kind": "copy"}, {"name": "PreprocessorOutputOpts", "type": "PreprocessorOutputOptions", "kind": "copy"}, ], }, { "name": "DiagnosticsEngine", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1DiagnosticsEngine.html", "connections": [ {"name": "Diags", "type": "DiagnosticIDs", "kind": "shared"}, {"name": "DiagOpts", "type": "DiagnosticOptions", "kind": "shared"}, {"name": "Client", "type": "DiagnosticConsumer", "kind": "reference"}, {"name": "Owner", "type": "DiagnosticConsumer", "kind": "owns"}, {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, ], }, { "name": "FileManager", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1FileManager.html", "connections": [ {"name": "FS", "type": "FileSystem", "kind": "shared"}, {"name": "FileSystemOpts", "type": "FileSystemOptions", "kind": "copy"}, {"name": "StatCache", "type": "FileSystemStatCache", "kind": "owns"}, ], }, { "name": "SourceManager", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1SourceManager.html", "connections": [ {"name": "Diag", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "FileMgr", "type": "FileManager", "kind": "reference"}, {"name": "LineTable", "type": "LineTableInfo", "kind": "owns"}, ], }, { "name": "Preprocessor", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1Preprocessor.html", "connections": [ {"name": "PPOpts", "type": "PreprocessorOptions", "kind": "shared"}, {"name": "Diags", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "LangOpts", "type": "LangOptions", "kind": "reference"}, {"name": "Target", "type": "TargetInfo", "kind": "reference"}, {"name": "AuxTarget", "type": "TargetInfo", "kind": "reference"}, {"name": "FileMgr", "type": "FileManager", "kind": "reference"}, {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, {"name": "ScratchBuf", "type": "ScratchBuffer", "kind": "owns"}, {"name": "HeaderInfo", "type": "HeaderSearch", "kind": "reference"}, {"name": "TheModuleLoader", "type": "ModuleLoader", "kind": "reference"}, {"name": "ExternalSource", "type": "ExternalPreprocessorSource", "kind": "reference"}, {"name": "Identifiers", "type": "IdentifierTable", "kind": "copy"}, {"name": "PragmaHandlers", "type": "PragmaNamespace", "kind": "owns"}, {"name": "PragmaHandlersBackup", "type": "PragmaNamespace", "kind": "owns"}, {"name": "CurLexer", "type": "Lexer", "kind": "owns"}, {"name": "CurPPLexer", "type": "PreprocessorLexer", "kind": "reference"}, {"name": "CurTokenLexer", "type": "TokenLexer", "kind": "owns"}, {"name": "Callbacks", "type": "PPCallbacks", "kind": "owns"}, {"name": "TokenLexerCache", "type": "TokenLexer", "kind": "owns"}, ], }, { "name": "ASTContext", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1ASTContext.html", "connections": [ {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, {"name": "LangOpts", "type": "LangOptions", "kind": "reference"}, {"name": "NoSanitizeL", "type": "NoSanitizeList", "kind": "owns"}, {"name": "XRayFilter", "type": "XRayFunctionFilter", "kind": "owns"}, {"name": "ProfList", "type": "ProfileList", "kind": "owns"}, {"name": "ABI", "type": "CXXABI", "kind": "owns"}, {"name": "Target", "type": "TargetInfo", "kind": "reference"}, {"name": "AuxTarget", "type": "TargetInfo", "kind": "reference"}, {"name": "InterpContext", "type": "interp::Context", "kind": "owns"}, {"name": "ParentMapCtx", "type": "ParentMapContext", "kind": "owns"}, {"name": "Idents", "type": "IdentifierTable", "kind": "reference"}, {"name": "ExternalSource", "type": "ExternalASTSource", "kind": "shared"}, // ASTContext stores lots of other useful data but it's not interesting for our purposes. ], }, { "name": "Sema", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1Sema.html", "connections": [ {"name": "ExternalSource", "type": "ExternalSemaSource", "kind": "reference"}, {"name": "LangOpts", "type": "LangOptions", "kind": "reference"}, {"name": "PP", "type": "Preprocessor", "kind": "reference"}, {"name": "Context", "type": "ASTContext", "kind": "reference"}, {"name": "Consumer", "type": "ASTConsumer", "kind": "reference"}, {"name": "Diags", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, {"name": "SemaPPCallbackHandler", "type": "SemaPPCallbacks", "kind": "reference"}, // Sema stores lots of other useful data but it's not interesting for our purposes. ], }, { "name": "ASTReader", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1ASTReader.html", "connections": [ {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, {"name": "FileMgr", "type": "FileManager", "kind": "reference"}, {"name": "PCHContainerRdr", "type": "PCHContainerReader", "kind": "reference"}, {"name": "Diags", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "SemaObj", "type": "Sema", "kind": "reference"}, {"name": "PP", "type": "Preprocessor", "kind": "reference"}, {"name": "ContextObj", "type": "ASTContext", "kind": "reference"}, {"name": "Consumer", "type": "ASTConsumer", "kind": "reference"}, {"name": "ModuleMgr", "type": "ModuleManager", "kind": "copy"}, ], }, { "name": "HeaderSearch", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1HeaderSearch.html", "connections": [ {"name": "HSOpts", "type": "HeaderSearchOptions", "kind": "shared"}, {"name": "Diags", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "FileMgr", "type": "FileManager", "kind": "reference"}, {"name": "ModMap", "type": "ModuleMap", "kind": "copy"}, {"name": "ExternalLookup", "type": "ExternalPreprocessorSource", "kind": "reference"}, {"name": "ExternalSource", "type": "ExternalHeaderFileInfoSource", "kind": "reference"}, // HeaderSearch also stores other information but it's not useful for us now. ], }, { "name": "PreprocessorLexer", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1PreprocessorLexer.html", "connections": [ {"name": "PP", "type": "Preprocessor", "kind": "reference"}, ], }, { "name": "Lexer", // it is a PreprocessorLexer too but won't express that in dependencies yet, just copy PP field. "doclink": "https://clang.llvm.org/doxygen/classclang_1_1Lexer.html", "connections": [ {"name": "PP", "type": "Preprocessor", "kind": "reference"}, {"name": "LangOpts", "type": "LangOptions", "kind": "reference"}, ], }, { "name": "TokenLexer", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1TokenLexer.html", "connections": [ {"name": "PP", "type": "Preprocessor", "kind": "reference"}, ], }, ]32:T591,chart = { // Force-directed graph resources // * https://observablehq.com/@d3/force-directed-graph // * https://resources.oreilly.com/examples/0636920026938/blob/master/chapter_11/04_force.html // * https://github.com/d3/d3-force const layoutDataset = prepareDataset(dataset); let simulation = d3.forceSimulation(layoutDataset.nodes) .force("link", d3.forceLink(layoutDataset.links)) .force("charge", d3.forceManyBody()) .force("center", d3.forceCenter(width / 2, height / 2)); let svg = d3.create("svg") .attr("viewBox", [0, 0, width, height]); const link = svg.append("g") .attr("stroke", "#999") .attr("stroke-opacity", 0.6) .selectAll("line") .data(layoutDataset.links) .join("line"); //.attr("stroke-width", d => Math.sqrt(d.value)); const node = svg.append("g") .attr("stroke", "#fff") .attr("stroke-width", 1.5) .selectAll("circle") .data(layoutDataset.nodes) .join("circle") .attr("r", 5) .attr("fill", "steelblue"); simulation.on("tick", () => { link .attr("x1", d => d.source.x) .attr("y1", d => d.source.y) .attr("x2", d => d.target.x) .attr("y2", d => d.target.y); node .attr("cx", d => d.x) .attr("cy", d => d.y); }); node.append("title") .text(d => d.name); invalidation.then(() => simulation.stop()); return svg.node(); }33:T8d1,colaChart = { // https://ialab.it.monash.edu/webcola/examples/downwardedges.html // https://observablehq.com/@mbostock/hello-cola var d3cola = cola.d3adaptor(d3) .avoidOverlaps(true) .size([width, height]); const svg = d3.select(DOM.svg(width, height)); const layoutDataset = prepareDataset(dataset); const nodeRadius = 5; layoutDataset.nodes.forEach(function (v) { v.height = v.width = 2 * nodeRadius; }); d3cola .nodes(layoutDataset.nodes) .links(layoutDataset.links) .flowLayout("y", 60) .symmetricDiffLinkLengths(8) .start(10,20,20); // define arrow markers for graph links svg.append('svg:defs').append('svg:marker') .attr('id', 'end-arrow') .attr('viewBox', '0 -5 10 10') .attr('refX', 6) .attr('markerWidth', 3) .attr('markerHeight', 3) .attr('orient', 'auto') .append('svg:path') .attr('d', 'M0,-5L10,0L0,5') .attr('fill', '#000'); var path = svg.selectAll(".link") .data(layoutDataset.links) .enter().append('svg:path') .attr('class', 'link'); var node = svg.selectAll(".node") .data(layoutDataset.nodes) .enter().append("circle") .attr("class", "node") .attr("r", nodeRadius) .style("fill", "steelblue") .call(d3cola.drag); node.append("title") .text(d => d.name); d3cola.on("tick", function () { // draw directed edges with proper padding from node centers path.attr('d', function (d) { var deltaX = d.target.x - d.source.x, deltaY = d.target.y - d.source.y, dist = Math.sqrt(deltaX * deltaX + deltaY * deltaY), normX = deltaX / dist, normY = deltaY / dist, sourcePadding = nodeRadius, targetPadding = nodeRadius + 2, sourceX = d.source.x + (sourcePadding * normX), sourceY = d.source.y + (sourcePadding * normY), targetX = d.target.x - (targetPadding * normX), targetY = d.target.y - (targetPadding * normY); return 'M' + sourceX + ',' + sourceY + 'L' + targetX + ',' + targetY; }); node.attr("cx", d => d.x) .attr("cy", d => d.y); }); return svg.node(); }34:T6b5,isAcyclicGraph = { function convertDatasetToGraph(linearDataset) { var result = new Map(); let initIfNecessary = function(name) { if (!result.has(name)) { result.set(name, {"name": name, "edges": []}); } } linearDataset.forEach(entry => { initIfNecessary(entry.name); entry.connections.forEach(connectedEntry => { const connectedName = connectedEntry.type; initIfNecessary(connectedName); // We ignore "reference" edges to avoid cycles. Instead of converting the directed // graph into acyclic based on heuristics, we take out "reference" edges as // they convey the lack of ownership. We'll add these edges back later. if (connectedEntry.kind != "reference") { result.get(entry.name).edges.push(connectedName); } }); }); return result; } function isAcyclic(graph) { let hasCycle = {"value": false}; let visitedNodes = new Set(); let currentStackNodes = new Set(); let visitNode = function visitNodeFn(nodeName) { if (visitedNodes.has(nodeName)) { return; } visitedNodes.add(nodeName); currentStackNodes.add(nodeName); graph.get(nodeName).edges.forEach(connectedNode => { if (currentStackNodes.has(connectedNode)) { hasCycle.value = true; } else if (!visitedNodes.has(connectedNode)) { visitNode(connectedNode); } }); currentStackNodes.delete(nodeName); } graph.forEach((_, nodeName) => { if (!visitedNodes.has(nodeName)) { visitNode(nodeName); } }); return !hasCycle.value; } return isAcyclic(convertDatasetToGraph(dataset)); };35:Td82,class Graph { constructor(linearDataset, keepReferences) { var nodes = new Map(); let initNodeIfNecessary = function(nodeName) { if (!nodes.has(nodeName)) { nodes.set(nodeName, { "name": nodeName, "outgoing_edges": new Map(), "incoming_edges": new Map(), }); } } linearDataset.forEach(entry => { initNodeIfNecessary(entry.name); entry.connections.forEach(connectedEntry => { const connectedName = connectedEntry.type; initNodeIfNecessary(connectedName); const connectionKind = connectedEntry.kind; if (keepReferences || (connectionKind != "reference")) { nodes.get(entry.name).outgoing_edges.set(connectedName, connectionKind); nodes.get(connectedName).incoming_edges.set(entry.name, connectionKind); } }); }); this.nodes = nodes; } get size() { return this.nodes.size; } get nodeNames() { return Array.from(this.nodes.keys()); } getIncomingEdges(nodeName) { return Array.from(this.nodes.get(nodeName).incoming_edges.keys()); } getIncomingEdgeEntries(nodeName) { return Array.from(this.nodes.get(nodeName).incoming_edges.entries()); } getOutgoingEdges(nodeName) { return Array.from(this.nodes.get(nodeName).outgoing_edges.keys()); } getOutgoingEdgeEntries(nodeName) { return Array.from(this.nodes.get(nodeName).outgoing_edges.entries()); } containsNode(nodeName) { return this.nodes.has(nodeName); } containsEdge(fromNodeName, toNodeName) { return this.nodes.get(fromNodeName).outgoing_edges.has(toNodeName); } deleteNode(nodeName) { let node = this.nodes.get(nodeName); if (node.outgoing_edges.size > 0) { throw new Error("Deleted node '" + nodeName + "' is not empty, has outgoing edges"); } if (node.incoming_edges.size > 0) { throw new Error("Deleted node '" + nodeName + "' is not empty, has incoming edges"); } this.nodes.delete(nodeName); } deleteEdge(fromNodeName, toNodeName) { this.nodes.get(fromNodeName).outgoing_edges.delete(toNodeName); this.nodes.get(toNodeName).incoming_edges.delete(fromNodeName); } addNode(nodeName) { if (this.nodes.has(nodeName)) { throw new Error("Duplicate node '" + nodeName + "'"); } this.nodes.set(nodeName, { "name": nodeName, "outgoing_edges": new Map(), "incoming_edges": new Map(), }); } addEdge(fromNodeName, toNodeName, edgeKind) { if (this.containsEdge(fromNodeName, toNodeName)) { throw new Error("Duplicating edge '" + fromNodeName + "' -> '" + toNodeName + "'"); } this.nodes.get(fromNodeName).outgoing_edges.set(toNodeName, edgeKind); this.nodes.get(toNodeName).incoming_edges.set(fromNodeName, edgeKind); } clone() { let result = new Graph([], /*keepReferences=*/true); this.nodes.forEach((nodeDict, nodeName) => { let cloneNode = { "name": nodeName, "outgoing_edges": new Map(), "incoming_edges": new Map(), }; nodeDict.outgoing_edges.forEach((connectionKind, connectionName) => { cloneNode.outgoing_edges.set(connectionName, connectionKind); }); nodeDict.incoming_edges.forEach((connectionKind, connectionName) => { cloneNode.incoming_edges.set(connectionName, connectionKind); }); result.nodes.set(nodeName, cloneNode); }); return result; } }36:Tadf,function convertDAGToLayers(graph) { function isAllEdgesReferences(edgeEntries) { for (const edgeEntry of edgeEntries) { if (edgeEntry[1] != "reference") return false; } return true; } let adjustedEdgesGraph = graph.clone(); let distanceFromRoot = new Map(); let workList = []; graph.nodeNames.forEach(nodeName => { distanceFromRoot.set(nodeName, 0); if (graph.getIncomingEdges(nodeName).length == 0) { workList.push(nodeName); } }); while (graph.size > 0) { while (workList.length > 0) { let nodeName = workList.shift(); let nodeDistance = distanceFromRoot.get(nodeName); graph.getOutgoingEdges(nodeName).forEach(connectedNodeName => { graph.deleteEdge(nodeName, connectedNodeName); if (graph.getIncomingEdges(connectedNodeName).length == 0) { workList.push(connectedNodeName); } let newDistance = nodeDistance + 1; if (newDistance > distanceFromRoot.get(connectedNodeName)) { distanceFromRoot.set(connectedNodeName, newDistance); } }); graph.deleteNode(nodeName); } if (graph.size == 0) { break; } // We have encountered a cycle-like situation induced by "reference". // Instead of an optimal cycle breaking, just use a greedy approach and reverse the smallest amount of edges. let cycleBreakCandidates = []; graph.nodeNames.forEach(nodeName => { if (isAllEdgesReferences(graph.getIncomingEdgeEntries(nodeName))) { cycleBreakCandidates.push(nodeName); } }); if (cycleBreakCandidates.length == 0) { throw new Error("Wrong assumptions, no nodes with reference-only incoming edges.") } let minNodeName = cycleBreakCandidates[0]; let minNodeIncomingEdgesSize = graph.getIncomingEdges(minNodeName).length; cycleBreakCandidates.forEach(nodeName => { let nodeIncomingEdgesSize = graph.getIncomingEdges(nodeName).length; if (nodeIncomingEdgesSize < minNodeIncomingEdgesSize) { minNodeName = nodeName; minNodeIncomingEdgesSize = nodeIncomingEdgesSize; } }); let fromNodeEntries = graph.getIncomingEdges(minNodeName); fromNodeEntries.forEach(fromNodeName => { graph.deleteEdge(fromNodeName, minNodeName); adjustedEdgesGraph.deleteEdge(fromNodeName, minNodeName); if (!graph.containsEdge(minNodeName, fromNodeName)) { // If there is no existing edge in reverse direction already, // add minNode -> fromNode. graph.addEdge(minNodeName, fromNodeName, "reverse-reference"); adjustedEdgesGraph.addEdge(minNodeName, fromNodeName, "reverse-reference"); } }); workList.push(minNodeName); } return [distanceFromRoot, adjustedEdgesGraph]; }37:T807,function arrangeExistingNodeLayersToMinimizeCrossings(layerByName, graph) { // Not checking if intermediate nodes are required. let layerArrays = convertLayerByNameToArrayOfArrays(layerByName); let nodeOrderByName = new Map(); layerArrays.forEach(singleLayer => { for (let i = 0; i < singleLayer.length; i++) { nodeOrderByName.set(singleLayer[i], i); } }); const layersCount = layerArrays.length; for (let iterationIndex = 0; iterationIndex < 8; iterationIndex++) { // "Forward" pass. for (let layerIndex = 0; layerIndex + 1 < layersCount; layerIndex++) { layerArrays[layerIndex].forEach(layerNodeName => { let neighboursCount = 0; let neighboursTotal = 0; graph.getOutgoingEdges(layerNodeName).forEach(connectedNodeName => { neighboursCount += 1; neighboursTotal += nodeOrderByName.get(connectedNodeName); }); if (neighboursCount > 0) { nodeOrderByName.set(layerNodeName, neighboursTotal / neighboursCount); } }); } // "Backward" pass. for (let layerIndex = layersCount - 1; layerIndex > 0; layerIndex--) { layerArrays[layerIndex].forEach(layerNodeName => { let neighboursCount = 0; let neighboursTotal = 0; graph.getIncomingEdges(layerNodeName).forEach(connectedNodeName => { neighboursCount += 1; neighboursTotal += nodeOrderByName.get(connectedNodeName); }); if (neighboursCount > 0) { nodeOrderByName.set(layerNodeName, neighboursTotal / neighboursCount); } }); } } let orderedLayers = new Array(layersCount); for (let layerIndex = 0; layerIndex < layersCount; layerIndex++) { let namesWithOrderLayer = layerArrays[layerIndex].map(nodeName => { return [nodeName, nodeOrderByName.get(nodeName)]; }); namesWithOrderLayer.sort(function compare(lhs, rhs) { return lhs[1] - rhs[1]; }); orderedLayers[layerIndex] = namesWithOrderLayer.map(pair => pair[0]); } return orderedLayers; }38:Tbe4,function arrangeLayersToMinimizeCrossings(layerByName, graph) { let layerSpanningEdges = []; // Collect edges first and then modify the graph because modifying the graph during iteration is too tricky. graph.nodeNames.forEach(nodeName => { graph.getOutgoingEdges(nodeName).forEach(toNodeName => { if (layerByName.get(toNodeName) > layerByName.get(nodeName) + 1) { layerSpanningEdges.push([nodeName, toNodeName]); } }); }); layerSpanningEdges.forEach(edge => { let fromNodeName = edge[0]; let toNodeName = edge[1]; graph.deleteEdge(fromNodeName, toNodeName); var connectionNodeName = fromNodeName; for (let layer = layerByName.get(fromNodeName) + 1; layer < layerByName.get(toNodeName); layer += 1) { let intermediateName = fromNodeName + "-" + toNodeName + "-" + layer; graph.addNode(intermediateName); graph.addEdge(connectionNodeName, intermediateName, "intermediate"); layerByName.set(intermediateName, layer); connectionNodeName = intermediateName; } graph.addEdge(connectionNodeName, toNodeName); }); let layerArrays = convertLayerByNameToArrayOfArrays(layerByName); let nodeOrderByName = new Map(); layerArrays.forEach(singleLayer => { for (let i = 0; i < singleLayer.length; i++) { nodeOrderByName.set(singleLayer[i], i); } }); const layersCount = layerArrays.length; for (let iterationIndex = 0; iterationIndex < layersCount * 2; iterationIndex++) { // "Forward" pass. for (let layerIndex = 0; layerIndex + 1 < layersCount; layerIndex++) { layerArrays[layerIndex].forEach(layerNodeName => { let neighboursCount = 0; let neighboursTotal = 0; graph.getOutgoingEdges(layerNodeName).forEach(connectedNodeName => { neighboursCount += 1; neighboursTotal += nodeOrderByName.get(connectedNodeName); }); if (neighboursCount > 0) { nodeOrderByName.set(layerNodeName, neighboursTotal / neighboursCount); } }); } // "Backward" pass. for (let layerIndex = layersCount - 1; layerIndex > 0; layerIndex--) { layerArrays[layerIndex].forEach(layerNodeName => { let neighboursCount = 0; let neighboursTotal = 0; graph.getIncomingEdges(layerNodeName).forEach(connectedNodeName => { neighboursCount += 1; neighboursTotal += nodeOrderByName.get(connectedNodeName); }); if (neighboursCount > 0) { nodeOrderByName.set(layerNodeName, neighboursTotal / neighboursCount); } }); } } let orderedLayers = new Array(layersCount); for (let layerIndex = 0; layerIndex < layersCount; layerIndex++) { let namesWithOrderLayer = layerArrays[layerIndex].map(nodeName => { return [nodeName, nodeOrderByName.get(nodeName)]; }); namesWithOrderLayer.sort(function compare(lhs, rhs) { return lhs[1] - rhs[1]; }); orderedLayers[layerIndex] = namesWithOrderLayer.map(pair => pair[0]); } return orderedLayers; }39:T625,{ const chartWidth = width + 800; let svg = d3.create("svg") .attr("viewBox", [0, 0, chartWidth, height]); let layerWidth = chartWidth / orderedLayers.length; let labelCoordinates = new Map(); orderedLayers.forEach((singleLayer, layerIndex) => { let heightGap = height / (singleLayer.length + 1); singleLayer.forEach((nodeName, nodeIndex) => { let yOffset = heightGap + nodeIndex * heightGap; svg.append("text") .attr("x", layerIndex * layerWidth) .attr("y", yOffset) .text(nodeName); labelCoordinates.set(nodeName, [layerIndex, yOffset]); }); }); let graph = new Graph(dataset, /*keepReferences=*/true); graph.nodeNames.forEach(nodeName => { if (nodeName == "CompilerInstance") { graph.getOutgoingEdges(nodeName).forEach(toNodeName => { let fromCoordinates = labelCoordinates.get(nodeName); let toCoordinates = labelCoordinates.get(toNodeName); if (fromCoordinates[0] == toCoordinates[0]) { throw new Error("connected nodes in the same layer"); } if (fromCoordinates[0] > toCoordinates[0]) { let tmp = fromCoordinates; fromCoordinates = toCoordinates; toCoordinates = tmp; } svg.append("line") .attr("x1", (fromCoordinates[0] + 1) * layerWidth - 50) .attr("y1", fromCoordinates[1]) .attr("x2", toCoordinates[0] * layerWidth + 0) .attr("y2", toCoordinates[1]) .attr("stroke", "lightsteelblue"); }); } }); return svg.node(); }3a:T2c49,reduced_dataset = [ { "name": "CompilerInstance", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1CompilerInstance.html", "connections": [ {"name": "Invocation", "type": "CompilerInvocation", "kind": "shared"}, {"name": "Diagnostics", "type": "DiagnosticsEngine", "kind": "shared"}, {"name": "Target", "type": "TargetInfo", "kind": "shared"}, {"name": "AuxTarget", "type": "TargetInfo", "kind": "shared"}, {"name": "FileMgr", "type": "FileManager", "kind": "shared"}, {"name": "SourceMgr", "type": "SourceManager", "kind": "shared"}, {"name": "ModuleCache", "type": "InMemoryModuleCache", "kind": "shared"}, {"name": "PP", "type": "Preprocessor", "kind": "shared"}, {"name": "Context", "type": "ASTContext", "kind": "shared"}, {"name": "ExternalSemaSrc", "type": "ExternalSemaSource", "kind": "shared"}, {"name": "Consumer", "type": "ASTConsumer", "kind": "owns"}, //{"name": "CompletionConsumer", "type": "CodeCompleteConsumer", "kind": "owns"}, {"name": "TheSema", "type": "Sema", "kind": "owns"}, //{"name": "FrontendTimerGroup", "type": "TimerGroup", "kind": "owns"}, //{"name": "FrontendTimer", "type": "Timer", "kind": "owns"}, {"name": "TheASTReader", "type": "ASTReader", "kind": "shared"}, //{"name": "ModuleDepCollector", "type": "ModuleDependencyCollector", "kind": "shared"}, //{"name": "ThePCHContainerOperations", "type": "PCHContainerOperations", "kind": "shared"}, {"name": "DependencyCollectors", "type": "DependencyCollector", "kind": "shared"}, // ignore it is a vector, really //{"name": "OwnedVerboseOutputStream", "type": "raw_ostream", "kind": "owns"}, //{"name": "OutputStream", "type": "raw_pwrite_stream", "kind": "owns"}, ], }, { "name": "CompilerInvocation", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1CompilerInvocation.html", "connections": [ {"name": "LangOpts", "type": "LangOptions", "kind": "shared"}, //{"name": "TargetOpts", "type": "TargetOptions", "kind": "shared"}, {"name": "DiagnosticOpts", "type": "DiagnosticOptions", "kind": "shared"}, {"name": "HeaderSearchOpts", "type": "HeaderSearchOptions", "kind": "shared"}, {"name": "PreprocessorOpts", "type": "PreprocessorOptions", "kind": "shared"}, //{"name": "AnalyzerOpts", "type": "AnalyzerOptionsRef", "kind": "reference"}, //{"name": "MigratorOpts", "type": "MigratorOptions", "kind": "copy"}, //{"name": "CodeGenOpts", "type": "CodeGenOptions", "kind": "copy"}, //{"name": "DependencyOutputOpts", "type": "DependencyOutputOptions", "kind": "copy"}, {"name": "FileSystemOpts", "type": "FileSystemOptions", "kind": "copy"}, //{"name": "FrontendOpts", "type": "FrontendOptions", "kind": "copy"}, //{"name": "PreprocessorOutputOpts", "type": "PreprocessorOutputOptions", "kind": "copy"}, ], }, { "name": "DiagnosticsEngine", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1DiagnosticsEngine.html", "connections": [ //{"name": "Diags", "type": "DiagnosticIDs", "kind": "shared"}, {"name": "DiagOpts", "type": "DiagnosticOptions", "kind": "shared"}, //{"name": "Client", "type": "DiagnosticConsumer", "kind": "reference"}, //{"name": "Owner", "type": "DiagnosticConsumer", "kind": "owns"}, {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, ], }, { "name": "FileManager", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1FileManager.html", "connections": [ {"name": "FS", "type": "FileSystem", "kind": "shared"}, {"name": "FileSystemOpts", "type": "FileSystemOptions", "kind": "copy"}, {"name": "StatCache", "type": "FileSystemStatCache", "kind": "owns"}, ], }, { "name": "SourceManager", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1SourceManager.html", "connections": [ {"name": "Diag", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "FileMgr", "type": "FileManager", "kind": "reference"}, //{"name": "LineTable", "type": "LineTableInfo", "kind": "owns"}, ], }, { "name": "Preprocessor", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1Preprocessor.html", "connections": [ {"name": "PPOpts", "type": "PreprocessorOptions", "kind": "shared"}, {"name": "Diags", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "LangOpts", "type": "LangOptions", "kind": "reference"}, {"name": "Target", "type": "TargetInfo", "kind": "reference"}, {"name": "AuxTarget", "type": "TargetInfo", "kind": "reference"}, {"name": "FileMgr", "type": "FileManager", "kind": "reference"}, {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, //{"name": "ScratchBuf", "type": "ScratchBuffer", "kind": "owns"}, {"name": "HeaderInfo", "type": "HeaderSearch", "kind": "reference"}, {"name": "TheModuleLoader", "type": "ModuleLoader", "kind": "reference"}, {"name": "ExternalSource", "type": "ExternalPreprocessorSource", "kind": "reference"}, {"name": "Identifiers", "type": "IdentifierTable", "kind": "copy"}, //{"name": "PragmaHandlers", "type": "PragmaNamespace", "kind": "owns"}, //{"name": "PragmaHandlersBackup", "type": "PragmaNamespace", "kind": "owns"}, {"name": "CurLexer", "type": "Lexer", "kind": "owns"}, //{"name": "CurPPLexer", "type": "PreprocessorLexer", "kind": "reference"}, {"name": "CurTokenLexer", "type": "TokenLexer", "kind": "owns"}, //{"name": "Callbacks", "type": "PPCallbacks", "kind": "owns"}, {"name": "TokenLexerCache", "type": "TokenLexer", "kind": "owns"}, ], }, { "name": "ASTContext", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1ASTContext.html", "connections": [ {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, {"name": "LangOpts", "type": "LangOptions", "kind": "reference"}, //{"name": "NoSanitizeL", "type": "NoSanitizeList", "kind": "owns"}, //{"name": "XRayFilter", "type": "XRayFunctionFilter", "kind": "owns"}, //{"name": "ProfList", "type": "ProfileList", "kind": "owns"}, //{"name": "ABI", "type": "CXXABI", "kind": "owns"}, {"name": "Target", "type": "TargetInfo", "kind": "reference"}, {"name": "AuxTarget", "type": "TargetInfo", "kind": "reference"}, //{"name": "InterpContext", "type": "interp::Context", "kind": "owns"}, //{"name": "ParentMapCtx", "type": "ParentMapContext", "kind": "owns"}, {"name": "Idents", "type": "IdentifierTable", "kind": "reference"}, {"name": "ExternalSource", "type": "ExternalASTSource", "kind": "shared"}, // ASTContext stores lots of other useful data but it's not interesting for our purposes. ], }, { "name": "Sema", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1Sema.html", "connections": [ {"name": "ExternalSource", "type": "ExternalSemaSource", "kind": "reference"}, {"name": "LangOpts", "type": "LangOptions", "kind": "reference"}, {"name": "PP", "type": "Preprocessor", "kind": "reference"}, {"name": "Context", "type": "ASTContext", "kind": "reference"}, {"name": "Consumer", "type": "ASTConsumer", "kind": "reference"}, {"name": "Diags", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, //{"name": "SemaPPCallbackHandler", "type": "SemaPPCallbacks", "kind": "reference"}, // Sema stores lots of other useful data but it's not interesting for our purposes. ], }, { "name": "ASTReader", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1ASTReader.html", "connections": [ {"name": "SourceMgr", "type": "SourceManager", "kind": "reference"}, {"name": "FileMgr", "type": "FileManager", "kind": "reference"}, //{"name": "PCHContainerRdr", "type": "PCHContainerReader", "kind": "reference"}, {"name": "Diags", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "SemaObj", "type": "Sema", "kind": "reference"}, {"name": "PP", "type": "Preprocessor", "kind": "reference"}, {"name": "ContextObj", "type": "ASTContext", "kind": "reference"}, {"name": "Consumer", "type": "ASTConsumer", "kind": "reference"}, {"name": "ModuleMgr", "type": "ModuleManager", "kind": "copy"}, ], }, { "name": "HeaderSearch", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1HeaderSearch.html", "connections": [ {"name": "HSOpts", "type": "HeaderSearchOptions", "kind": "shared"}, {"name": "Diags", "type": "DiagnosticsEngine", "kind": "reference"}, {"name": "FileMgr", "type": "FileManager", "kind": "reference"}, {"name": "ModMap", "type": "ModuleMap", "kind": "copy"}, {"name": "ExternalLookup", "type": "ExternalPreprocessorSource", "kind": "reference"}, {"name": "ExternalSource", "type": "ExternalHeaderFileInfoSource", "kind": "reference"}, // HeaderSearch also stores other information but it's not useful for us now. ], }, { "name": "Lexer", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1Lexer.html", "connections": [ {"name": "PP", "type": "Preprocessor", "kind": "reference"}, {"name": "LangOpts", "type": "LangOptions", "kind": "reference"}, ], }, { "name": "TokenLexer", "doclink": "https://clang.llvm.org/doxygen/classclang_1_1TokenLexer.html", "connections": [ {"name": "PP", "type": "Preprocessor", "kind": "reference"}, ], }, ]3b:Tb4d,{ let graph = new Graph(reduced_dataset, /*keepReferences=*/true); let graphLayersAndAdjustedGraph = convertDAGToLayers(graph.clone()); let layerByName = graphLayersAndAdjustedGraph[0]; let adjustedGraph = graphLayersAndAdjustedGraph[1]; let layers = arrangeLayersToMinimizeCrossings(layerByName, adjustedGraph); const chartWidth = width + 800; const chartHeight = 900; let svg = d3.create("svg") .attr("viewBox", [0, 0, chartWidth, chartHeight]); let layerWidth = chartWidth / layers.length; let labelCoordinates = new Map(); let selectedNodeSummary = document.createElement("pre"); layers.forEach((singleLayer, layerIndex) => { let heightGap = chartHeight / (singleLayer.length + 1); singleLayer.forEach((nodeName, nodeIndex) => { let yOffset = heightGap + nodeIndex * heightGap; labelCoordinates.set(nodeName, [layerIndex, yOffset]); if (!graph.containsNode(nodeName)) { // Don't display intermediate nodes. return; } let textNode = svg.append("text") textNode .attr("x", layerIndex * layerWidth) .attr("y", yOffset) .text(nodeName); let incomingEntries = graph.getIncomingEdgeEntries(nodeName); let outgoingEntries = graph.getOutgoingEdgeEntries(nodeName); textNode.on("mouseover", function() { let text = ""; incomingEntries.forEach(entry => { text += entry[0] + " -> " + nodeName + " / as " + entry[1] + "\n"; }); text += "---\n"; outgoingEntries.forEach(entry => { text += nodeName + " -> " + entry[0] + " / as " + entry[1] + "\n"; }); selectedNodeSummary.textContent = text; }); }); }); graph.nodeNames.forEach(nodeName => { if (true || (nodeName == "FileManager")) { graph.getOutgoingEdgeEntries(nodeName).forEach(toNodeEntry => { let toNodeName = toNodeEntry[0]; let toNodeKind = toNodeEntry[1]; let fromCoordinates = labelCoordinates.get(nodeName); let toCoordinates = labelCoordinates.get(toNodeName); if (fromCoordinates[0] == toCoordinates[0]) { throw new Error("connected nodes in the same layer"); } if (fromCoordinates[0] > toCoordinates[0]) { let tmp = fromCoordinates; fromCoordinates = toCoordinates; toCoordinates = tmp; } svg.append("line") .attr("x1", (fromCoordinates[0] + 1) * layerWidth - 50) .attr("y1", fromCoordinates[1]) .attr("x2", toCoordinates[0] * layerWidth + 0) .attr("y2", toCoordinates[1]) .attr("class", "edge-kind-" + toNodeKind) .attr("stroke", "red"); // to catch missing styles }); } }); let result = document.createElement("div"); result.appendChild(svg.node()); result.appendChild(selectedNodeSummary); return result; }3c:T4ca,// 1.1. Reverse edges to eliminate cycles. // 1.2. Partition vertices into layers (levels). // 1.3. Introduce dummy vertices along long-span edges. // 2. For each layer specify the order of vertices to minimize edge crossings. // 3. Determine the [x-]coordinates. // 4. Draw the graph. stepByStepChart = { /* So far * learned to avoid 'reference' edges to avoid cycles */ // TODONE: implement longest-path for layering, see if it's enough // TODONE: add dummy vertices // for dummy vertices need to iterate through all edges and need to know a layer for each node // Q: Do I need new edges? Do I need to iterate through them too? // A: Yes, need to adjust some edges. // TODONE: implement iterated barycenter algorithm to minimize edge crossings // for each layer, for each node in the layer // find all the neighbours in the required layer and their positions // TODONE: create `graph` abstraction, working with `Map` directly is perilous // TODONE: decide on actual graph positions and draw it // TODO: create intermediate nodes, use them in positioning but don't draw them // TODO: make drawings of edges spanning multiple layers be jagged return "TODO" };3d:T49c,/** * Converts the original dataset to the form required by the force layout API. */ function prepareDataset(originalDataset) { let nodes = []; let typeIndices = new Map(); let links = []; originalDataset.forEach(entry => { const entryType = entry.name; if (!typeIndices.has(entryType)) { typeIndices.set(entryType, nodes.length); nodes.push({"name": entryType}); } let containedTypes = new Set(); entry.connections.forEach(element => { let connectionType = element.type; // For now I'm not being entirely precise and if there are // multiple connections between types, I'll take only the first one. // It is sufficient for a high-level picture. if (containedTypes.has(connectionType)) { return; } containedTypes.add(connectionType); if (!typeIndices.has(connectionType)) { typeIndices.set(connectionType, nodes.length); nodes.push({"name": connectionType}); } links.push({ "source": typeIndices.get(entryType), "target": typeIndices.get(connectionType), }); }); }); return { "nodes": nodes, "links": links, }; }3e:[] 2f:{"id":"c5ca1435a8cc78e6","slug":null,"title":"Connections between core Clang classes (WIP)","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2021-07-01T20:53:12.922Z","update_time":"$D2023-09-25T20:10:15.873Z","view_time":null,"first_public_time":"$D2023-07-23T01:13:32.068Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"1f82dc7abcd624aa","login":"vsapsai","name":"Volodymyr Sapsai","avatar_url":"https://avatars-next.observableusercontent.com/1096bd42d3a4a4d751175e6412b3ba9cb3953484eff42de6acc5e5cfda6a89b5","tier":"starter_2024"},"version":445,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"126cbc11c5978fc8","login":"vsapsai","name":"Volodymyr Sapsai","avatar_url":"https://avatars-next.observableusercontent.com/1096bd42d3a4a4d751175e6412b3ba9cb3953484eff42de6acc5e5cfda6a89b5","tier":null}],"members":[{"type":"individual","id":"126cbc11c5978fc8","login":"vsapsai","name":"Volodymyr Sapsai","avatar_url":"https://avatars-next.observableusercontent.com/1096bd42d3a4a4d751175e6412b3ba9cb3953484eff42de6acc5e5cfda6a89b5","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Connections between core Clang classes (WIP)","cells":[{"id":0,"value":"# Connections between core Clang classes (WIP)","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":28,"value":"md`**Methodology restrictions:** Don't drill down into data containers like LangOptions. Also omit primitive value types like int or bool. Also omit various caches, which might be useful in other cases but not now.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":11,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":113,"value":"md`On the plot below turned out the force simulation doesn't look useful for this DAG (though aesthetically fairly pleasing). What I've learned is that force simulation might work better for undirected graphs.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"$32","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":102,"value":"html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"md`On the chart below we can see the hierarchical drawing seems to convey more meaning. Though it is still fairly noisy. Also we can see the graph is more shallow than deep and there will be no space for node labels if we have 10 nodes on the same level. Probably switching the drawing to left-to-right would work better for this data.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":110,"value":"https://observablehq.com/@erikbrinkman/d3-dag-sugiyama","pinned":true,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":150,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":194,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":341,"value":"$36","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":156,"value":"graphLayersAndAdjustedGraph = {\n let graph = new Graph(dataset, /*keepReferences=*/true);\n return convertDAGToLayers(graph);\n};","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":256,"value":"function convertLayerByNameToArrayOfArrays(layerByName) {\n let layersNumber = 0;\n for (let layerValue of layerByName.values()) {\n if (layerValue > layersNumber) {\n layersNumber = layerValue;\n }\n }\n layersNumber += 1; // Number of layers is by 1 bigger than the biggest layer number.\n let layers = new Array(layersNumber);\n for (let i = 0; i < layersNumber; ++i) {\n layers[i] = [];\n }\n layerByName.forEach((layerValue, nodeName) => {\n layers[layerValue].push(nodeName);\n });\n return layers;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":345,"value":"$37","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":421,"value":"$38","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":253,"value":"orderedLayers = {\n let layerByName = graphLayersAndAdjustedGraph[0];\n let graph = graphLayersAndAdjustedGraph[1];\n return arrangeExistingNodeLayersToMinimizeCrossings(layerByName, graph);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":352,"value":"This drawing is more legible but still pretty noisy. There are elements that help to understand detailed ownership information. But I think the ownership of data containers isn't particularly challenging. It is the relationships between classes that carry behaviour that I'm after. For example, owning components like `FrontendOptions`, `CodeGenOptions` is not interesting to me. But interaction between `Sema`, `ASTContext`, `SourceManager` is something I want to learn more about.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":298,"value":"$39","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":370,"value":"Here are classes that don't have outgoing edges and referenced only once. In addition to cleaning some of those decided not to distinguish between `PreprocessorLexer` and `Lexer`.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":356,"value":"{\n let leafByParent = new Map();\n let graph = new Graph(dataset, /*keepReferences=*/true);\n graph.nodeNames.forEach(nodeName => {\n if ((graph.getOutgoingEdges(nodeName).length == 0) && (graph.getIncomingEdges(nodeName).length == 1)) {\n let parentName = graph.getIncomingEdges(nodeName)[0];\n if (!leafByParent.has(parentName)) {\n leafByParent.set(parentName, []);\n }\n leafByParent.get(parentName).push(nodeName);\n }\n });\n\n var output = \"\";\n let parents = Array.from(leafByParent.keys());\n parents.sort();\n parents.forEach(parentName => {\n output += parentName + \"\\n\";\n let children = leafByParent.get(parentName);\n children.sort();\n children.forEach(childName => {\n output += \" \" + childName + \"\\n\";\n });\n });\n let result = document.createElement(\"pre\");\n result.textContent = output;\n return result;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":373,"value":"$3a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":397,"value":"html``","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":440,"value":"This still looks messy and visuals can be improved but I think it is sufficient to make conclusions. `CompilerInstance` owns a lot of other components, `Sema` references many others, `HeaderSearch` references others, `ASTContext` references others, `ASTReader` references others, `Preprocessor` references others and is referenced by others; `SourceManager` is referenced by others.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":381,"value":"$3b","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"$3c","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"height = 600","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"$3d","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"d3 = require(\"d3@6\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"cola = require(\"webcola@3/WebCola/cola.min.js\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W3e","stdlib":"1","titling":"auto"}} 30:"$2f:body"