PDG: Program Dependency Graph

WIP

Dbux-PDG is still in an early stage of development. It has several issues and will not work on all programs. If you really like what you see, or you want to use this for your own algorithms, please contact us on Discord, so we know which parts to prioritize.

NOTE: The parts that are still missing are not necessarily that much work, but simply have been downgraded in priority. That is why we encourage anyone interested to reach out to us and let us know. It matters.

How to use the PDG?

First, make sure that Dbux is installed and activated.

There are currently two ways of using the PDG. Both can be accessed via VSCode commands:

1. Open the PDG View → pick an algorithm → open its PDG
2. Show PDG of your own algorithm (function)

Option 1: PDG View

The PDG view currently lists all test cases of all algorithms of the javascript-algorithms repository.

The PDG view lists all potential PDGs by algorithm category, then algorithm, then test case, then algorithm invocation (see screenshot above). You can:

1. Click a test case to open the test location in the VSCode code editor.
2. Click an algorithm sample to open its PDG.
3. You can re-run any test using the little button next to each test case (see screenshot above).
4. You can find all exported files via the Dbux: Open Export Folder command.

Notes:

• If javascript-algorithms was not previously installed, it will be cloned and installed upon clicking.
• If it was not previously executed, it will first ask to run the test case and export the application file.
• Running most test cases with Dbux takes around 10s, while importing feels almost instantaneous.

Option 2: Show PDG of any function

If you want to roll

1. Run Application with Dbux Enabled
2. Select a trace of any function
3. Use the Dbux: Open PDG for Selected Function command
   • 

Examples

We illustrate using the PDG on two algorithms (BubbleSort and Dijkstra) in this video:

Why do we need a PDG?

We designed the Program Dependency Graph (PDG) to allow the developer stay oriented while seeking answers to questions about data flow and data dependencies between memory addresses, statements and control blocks, with a specific focus on data structures and algorithms.

TODO: more to be said here.

How does the PDG work?

We illustrate using the PDG on two algorithms (BubbleSort and Dijkstra) in this video:

In its fully summarized form, the PDG only shows a selected function's inputs, outputs and their dependency relationships. Many bugs become obvious on this level already. To understand causality, you can further zoom into or out of nested control flow blocks, all the way down to the statement level.

The immense complexity of dynamic execution behavior of even simple applications presents a major design challenge standing in the way of widespread adoption of novel developer tools such as this. Visualizing everything can help identify high-level patterns, but makes it inherently difficult to investigate causality. We argue that it is important to allow the developer zoom out to see a complete representation of the system in a single screen, but also be able to zoom in on regions of interest, in order to investigate exactly what the recorded control flow is and where each value is computed or accessed, and where it is moved.

Thus, you start at a fully zoomed out view, where all relevant data flow is fully summarized into only the watched nodes and the connections between them. While you can also choose to fully expand the graph, in most scenarios, this view would obstruct comprehension due to the immense amount of detail presented at once. Instead, when looking for details, you can first investigate the summarized top-level of control flow blocks and then zoom in on individual blocks, all the way down to the individual statement level. You can (and probably should) do this incrementally, one step at a time, as you are honing in on a particular point of interest.