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")
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
