Public
Edited
Sep 25, 2023
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"},
],
},
]
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();
}
html`<style>
.node {
stroke: #fff;
stroke-width: 1.5px;
}
.link {
fill: none;
stroke: #000;
stroke-width: 1.5px;
opacity: 0.4;
marker-end: url(#end-arrow);
}
</style>`
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();
}
https://observablehq.com/@erikbrinkman/d3-dag-sugiyama
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));
};
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;
}
}
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];
}
graphLayersAndAdjustedGraph = {
let graph = new Graph(dataset, /*keepReferences=*/true);
return convertDAGToLayers(graph);
};
function convertLayerByNameToArrayOfArrays(layerByName) {
let layersNumber = 0;
for (let layerValue of layerByName.values()) {
if (layerValue > layersNumber) {
layersNumber = layerValue;
}
}
layersNumber += 1; // Number of layers is by 1 bigger than the biggest layer number.
let layers = new Array(layersNumber);
for (let i = 0; i < layersNumber; ++i) {
layers[i] = [];
}
layerByName.forEach((layerValue, nodeName) => {
layers[layerValue].push(nodeName);
});
return layers;
}
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;
}
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;
}
orderedLayers = {
let layerByName = graphLayersAndAdjustedGraph[0];
let graph = graphLayersAndAdjustedGraph[1];
return arrangeExistingNodeLayersToMinimizeCrossings(layerByName, graph);
}
{
let leafByParent = new Map();
let graph = new Graph(dataset, /*keepReferences=*/true);
graph.nodeNames.forEach(nodeName => {
if ((graph.getOutgoingEdges(nodeName).length == 0) && (graph.getIncomingEdges(nodeName).length == 1)) {
let parentName = graph.getIncomingEdges(nodeName)[0];
if (!leafByParent.has(parentName)) {
leafByParent.set(parentName, []);
}
leafByParent.get(parentName).push(nodeName);
}
});
var output = "";
let parents = Array.from(leafByParent.keys());
parents.sort();
parents.forEach(parentName => {
output += parentName + "\n";
let children = leafByParent.get(parentName);
children.sort();
children.forEach(childName => {
output += " " + childName + "\n";
});
});
let result = document.createElement("pre");
result.textContent = output;
return result;
}
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"},
],
},
]
html`<style>
.edge-kind-owns {
stroke: #000;
stroke-width: 1.0px;
}
.edge-kind-copy {
stroke: darkblue;
stroke-width: 1.0px;
}
.edge-kind-reference {
stroke: lightblue;
stroke-width: 1.0px;
}
.edge-kind-shared {
stroke: olive;
stroke-dasharray: 4;
stroke-width: 1.0px;
}
.link-tmp {
fill: none;
stroke: #000;
stroke-width: 1.5px;
opacity: 0.4;
marker-end: url(#end-arrow);
}
</style>`
{
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;
}
// 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"
};
height = 600
/**
* 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,
};
}
d3 = require("d3@6")
cola = require("webcola@3/WebCola/cola.min.js")
One platform to build and deploy the best data apps
Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.