feature: DDG control comprehension

[Domiii]

Control Comprehension Basics

Goal: produce ControlStatements/ControlGroups that user can use to comprehend control flow.

Vis

Summarization ops

• non-loop branches
  • [x] hide/collapse/expand any branch
• Loops
  • [x] hide/show loop
  • [x] collapse/expand individual iterations
• [ ] Render control edges

Instrumentation

• [x] add controlId to every staticTrace, indicating its innermost parent control trace
• [x] add controlBlockId and controlStatementId
• [x] statement nesting: nest certain control statements into one control tree → share outermost controlStatementId
  • [x] else if
  • [ ] TernaryExpression
• [ ] insert new {push,pop}Control info to staticTraces and add traces where necessary:
  • If:
  • add push to test
  • new pop
  • Switch/case:
  • add push to discrimnant
  • new pop
  • Ternary:
  • add push to test
  • add pop to itself
  • For:
  • add push to test
  • new pop
  • For+:
  • new push (since left can be pattern)
  • new pop
  • While + DoWhile:
  • new push
  • new pop
• [x] add a getControlBlockLabel(controlTraceId) function
  • produce label based of statement type + trace value

DDG.buildGraph:

• [x] change iteration from dataNode to trace (so we don't miss control traces)
• [x] keep controlGroupStack
  • add some RootGroup initially
• [x] set controlGroupId for each node
• [x] also keep ControlGroup tree (ControlGroupNode)
  • add ddgNodes and controlGroups in order to each group's children property to stack top
• [x] make sure, each decision node has a DDGNode (should never skip)

Utils:

getControlStaticIdsByRootId(dp, staticControlStatementId) {
  TODO
},

getControlIdsByRootId(dp, controlRootTraceId) {
  TODO
},

Indexes:

• staticControlBlockTraceIdsByRootId

More Data Structures + Queries

class Queries {
  getBranchBlockLabel(blockOrStatementStaticTraceId) {
    // TODO: label is unambiguous for loops, but requires knowing the block for `NonLoop`s
    // NOTE: block information can be determined by `statement type` + `controlTrace.value`
  }
}

By syntax

Conditional statements generate complex conditional trees. Each such tree has a single controlStatementId.

• [x] if
  • NOTE: only one consequent of an arbitrarily nested if/else tree can be visited, but all prior conditions do execute
  • merge nested if/elses into one ControlTree?
  • only has one enteredBlock
  • depends on all preceding conditionTraceIds
• [ ] TernaryExpression
  • basically like if (also same nesting semantics)
• [ ] switch/case
  • can have multiple enteredBlocks
  • all blocks depend on the same set of conditionTraceIds
  • NOTE: if a block is executed because the prior block did not break, its condition does not get evaluated, and thus depends on the same set of conditionTraceIds as the previous block.

Loops

• [ ] For
• [ ] While
• [ ] ForIn
• [ ] ForOf
• [ ] (later) DoWhile
  • separate into two groups: first iteration (not controlled) and all following iterations

HOFs

NOTE: Higher-order functions, such as map don't have specific grammar, but instead require customized monkey-patching

• [ ] map
• [ ] filter
• [ ] etc.

Generators

TODO

Future Work

Proper Error Handling

• [ ] fix: branch expressions: pop is not wrapped in try/finally
• [ ] fix: branch statements: pop might be called before push, because an error was raised before push (e.g. in for (ERR; ; ) { })

[Domiii]

We have most control groups done, but control dependencies are not a thing for now.