wiki:JooPo algorithms

Version 4 (modified by schuhmac, 9 years ago) (diff)


JooPo algorithms

  1. Block recognition

Block recognition

JooPo performs block recognition in four steps.

  1. (Block Graph) an initial depth first traversal explores the basic structure of the routine
  2. (Block Fit) a second depth first traversal tries to construct a consistent scope logic hypothesis
  3. (Block Ken) afterwards various additional information is collected
  4. (Block Tree) the information is constrained towards a clean block logic outline

Block Graph

In block structured code blocks open up and close for loops or branch and reunite for conditionals. Thus we traverse the flow graph registering recurring intercepts as cycles or unites. Cycles are induced by those intercepts already met on this path, unites by others.

Block Fit

Cycles and unites must be subject to a consistent logic. They consecutively subdivide code into scopes inducing a treelike structure. If there is such structure in the code, a depth first traversal classifying intercepts into scopes should greedily recognize it. Thus we try to introduce a scope for every cycle and unite.

Basically we check whether the intercept of beginning and end of the new scope both belong to the same old scope, then associate all intermediate intercepts that are not within a nested scope with the new scope.

Yet we also have to take into account the additional constructs allowed. Exits yield branches not united with scope not further subdivided. Breaks lead us to consider also the scopes of enclosing cycles and to check whether we encounter an intercept that closes a scope on higher level. Collapses lead us to having to check whether we encounter the unite of a superscope.

Block Ken

If we have succeeded in constructing a consistent scope hypothesis, we need some further information about the code.

We need the main axes of the scopes, which we get by tracing the traversal backwards from scope end to beginning.

For collapses we need to collect all branchings that collapse in one unite in a treelike structure to traverse them afterwards in Block Tree.

For branches that do not unite, we bundle all subbranchings on same scope with other subbranchings with all branches diverging to traverse them also afterwards additionally to collapse, simulating uniting behaviour.

Block Tree

Finally we condense uniting branchings to conditional seeds called switches, cycles to loop seeds called recurrences and construct a unique traversal called succeed during which the code is consistently scoped.

For branchings we check whether they have no subcases as would be induced by nonbroken switch statement cases, then check whether they unite in a unique intercept that is also on their scope's main axis. Diverging branches are also associated with their unite.

Then we construct the information by depth first traversing the all branchings that collapse in one unite and connecting and propagating their succession information.

Attachments (10)

Download all attachments as: .zip