FlowChart.java
/*
** Module : FlowChart.java
** Abstract : Computes the flow chart associated with a top-level block.
**
** Copyright (c) 2018-2023, Golden Code Development Corporation.
**
** -#- -I- --Date-- ---------------------------------Description----------------------------------
** 001 CA 20181003 First version.
** 002 CA 20200428 Some changes to process DEFINE ENUM. Untested.
** 003 TJD 20220504 Java 11 compatibility minor changes
** 004 OM 20230115 Replaced absolutePath(), relativePath(), upPath() and downPath() with faster
** versions, based on node types rather on string paths.
*/
/*
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU Affero General Public License as
** published by the Free Software Foundation, either version 3 of the
** License, or (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU Affero General Public License for more details.
**
** You may find a copy of the GNU Affero GPL version 3 at the following
** location: https://www.gnu.org/licenses/agpl-3.0.en.html
**
** Additional terms under GNU Affero GPL version 3 section 7:
**
** Under Section 7 of the GNU Affero GPL version 3, the following additional
** terms apply to the works covered under the License. These additional terms
** are non-permissive additional terms allowed under Section 7 of the GNU
** Affero GPL version 3 and may not be removed by you.
**
** 0. Attribution Requirement.
**
** You must preserve all legal notices or author attributions in the covered
** work or Appropriate Legal Notices displayed by works containing the covered
** work. You may not remove from the covered work any author or developer
** credit already included within the covered work.
**
** 1. No License To Use Trademarks.
**
** This license does not grant any license or rights to use the trademarks
** Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
** of Golden Code Development Corporation. You are not authorized to use the
** name Golden Code, FWD, or the names of any author or contributor, for
** publicity purposes without written authorization.
**
** 2. No Misrepresentation of Affiliation.
**
** You may not represent yourself as Golden Code Development Corporation or FWD.
**
** You may not represent yourself for publicity purposes as associated with
** Golden Code Development Corporation, FWD, or any author or contributor to
** the covered work, without written authorization.
**
** 3. No Misrepresentation of Source or Origin.
**
** You may not represent the covered work as solely your work. All modified
** versions of the covered work must be marked in a reasonable way to make it
** clear that the modified work is not originating from Golden Code Development
** Corporation or FWD. All modified versions must contain the notices of
** attribution required in this license.
*/
package com.goldencode.p2j.report.server;
import java.util.*;
import java.util.concurrent.atomic.*;
import java.util.function.*;
import org.apache.tinkerpop.gremlin.structure.Direction;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import com.goldencode.ast.*;
import com.goldencode.p2j.uast.*;
/**
* Process a top-level block and compute the associated flow chart.
* <p>
* Each block will have only one START node; for nested blocks, there will be only 1 END node;
* for the top-level block there will be 1 or more EXIT nodes (if the EXIT is performed from a
* deeply nested block, then a new EXIT node will be added at that level, to avoid making the
* top-level block's EXIT node a super-node).
* <p>
* Each block is processed recursively, and all direct child nodes of this block will have as
* group ID the block's ID.
* <p>
* When branching, it is important to specify for each branch's statement the ID of the first
* node in the branch - as the branch nodes will start from the same depth, this will allow the
* nodes to be ordered by their parent ID and placed on the same parent's side.
* <p>
* Loop blocks with WHILE and/or TO expressions will have the expression expanded, to mimic the
* execution of the loop: for WHILE, there will be a 'backlink' to the WHILE condition, and for
* TO expression, there will be additional assignment and loop incrementation nodes added - see
* {@link #loadBlockFlow}'s comments for more details.
*/
public class FlowChart
implements ProgressParserTokenTypes
{
/** Map labels with their associated blocks. */
private final Map<String, Aast> labelTargets = new HashMap<>();
/** Maps AST IDs to their {@link FlowAstNode node} counterpart. */
private final Map<Long, FlowAstNode> astsToNodes = new HashMap<>();
/** For each node, map the block's ID to its associated START node. */
private final Map<Integer, FlowNode> startNodes = new HashMap<>();
/** Flag identifying the flow chart direction - when <code>true</code>, vertical flow. */
private final boolean flowDir;
/** The created nodes. */
private List<FlowNode> nodes;
/** The created links. */
private List<FlowLink> links;
/** A set of statement types explicitly included in the chart, which are not INNER_BLOCK. */
private Set<Integer> statementTypes = new HashSet<>(Arrays.asList(KW_IF,
KW_CASE,
KW_LEAVE,
KW_NEXT,
KW_RETRY,
KW_RETURN,
KW_UNDO,
KW_STOP,
KW_QUIT,
KW_CATCH,
KW_FINALLY));
/** The set of block types. */
private Set<Integer> blockTypes = new HashSet<>(Arrays.asList(KW_DO, KW_REPEAT, KW_FOR));
/** Used when branching: track the creation order of each same-depth node. */
private Map<Integer, AtomicInteger> depthOrder = new HashMap<>();
/** The top-level AST block, for which the flow-chart will be computed. */
private Aast topLevelBlock;
/** The stack with blocks having ON STOP phrases. */
private Deque<FlowAstNode> stopStack = new ArrayDeque<>();
/** The stack with blocks having ON QUIT phrases. */
private Deque<FlowAstNode> quitStack = new ArrayDeque<>();
/** The stack of created EXIT nodes. */
private Stack<FlowNode> exitStack = new Stack<>();
/** Map of AST IDs to the callgraph vertex. */
private Map<Long, Vertex> callsites = null;
/**
* Setup a new flow chart for the given ast.
*
* @param ast
* The top-level AST.
* @param flowDir
* The flow direction: vertical (when <code>true</code>) or horizontal, otherwise.
*/
FlowChart(Aast ast, boolean flowDir)
{
// get all call-sites parented by this top level block
callsites = CallGraphHelper.findCallSites(ast);
this.flowDir = flowDir;
topLevelBlock = ast;
nodes = new LinkedList<>();
links = new LinkedList<>();
}
/**
* Build the flow chart snippet, starting from the {@link #topLevelBlock} block.
*
* @return The {@link FlowChartSnippet}.
*/
FlowChartSnippet build()
{
// in some cases, the AST needs to be prepared
int type = topLevelBlock.getType();
if (type == KW_PROC ||
type == KW_FUNCT ||
type == METHOD_DEF ||
type == KW_CONSTRUC ||
type == KW_DESTRUCT ||
type == KW_CLASS ||
type == KW_INTERFAC ||
type == KW_ENUM)
{
topLevelBlock = topLevelBlock.getParent();
}
loadFlowNodes(null, topLevelBlock, 0);
// some sanitize - remove links for which target/source are the same
Iterator<FlowLink> iter = links.iterator();
while (iter.hasNext())
{
FlowLink l = iter.next();
if (l.getSource() == l.getTarget())
{
iter.remove();
}
}
return new FlowChartSnippet(nodes, links);
}
/**
* Load the flow chart starting from the given root node.
*
* @param froot
* The current root node (may be a block or a branching statement). For the top-level
* block, this will be <code>null</code>.
* @param root
* The root AST node.
*
* @return The new depth.
*/
private int loadFlowNodes(FlowAstNode froot, Aast root, int depth)
{
return loadFlowNodes(froot, root, "", depth);
}
/**
* Load the flow chart starting from the given root node.
*
* @param froot
* The current root node (may be a block or a branching statement). For the top-level
* block, this will be <code>null</code>.
* @param root
* The root AST node.
* @param label
* The label used to link the exit nodes to the next statement.
* @param depth
* The current depth in the flow.
*
* @return The new depth.
*/
private int loadFlowNodes(FlowAstNode froot, Aast root, String label, int depth)
{
if (root == null)
{
throw new NullPointerException("Invalid root node!");
}
Aast flowRoot = root;
if (flowRoot.getType() == INNER_BLOCK)
{
flowRoot = root.getImmediateChild(blockTypes, null);
}
if (flowRoot == null)
{
return depth;
}
int rtype = root.getType();
boolean isBlock = rtype == INNER_BLOCK || froot == null;
if (rtype == KW_METHOD || rtype == KW_CONSTRUC || rtype == KW_DESTRUCT)
{
if (root.getParent().downPath(BLOCK))
{
root = root.getParent().getImmediateChild(BLOCK, null);
}
}
// the start node is created before the normal node
if (root.getType() != BLOCK && root.downPath(BLOCK))
{
root = root.getImmediateChild(BLOCK, null);
}
Integer groupId = (froot == null ? null
: (isBlock ? Integer.valueOf(froot.getId())
: froot.getGroupId()));
Integer parentId = (froot == null ? null : froot.getId());
// create the start/end nodes
FlowNode start = null;
if (isBlock)
{
if (froot == null)
{
start = createNode(root, depth++, parentId, groupId, false);
start.setType("START");
}
else
{
start = startNodes.get(froot.getId());
if (start == null)
{
start = createNode("START", depth++, groupId);
start.setParentId(parentId);
startNodes.put(froot.getId(), start);
}
else
{
start.setGroupId(groupId);
start.setParentId(parentId);
}
}
}
int numChildren = root.getNumImmediateChildren();
FlowNode lastFlow = (isBlock ? start : froot);
boolean isLastFlowExit = true;
if (froot != null)
{
if (froot.ast.downPath(KW_ON, KW_QUIT))
{
quitStack.push(froot);
}
if (froot.ast.downPath(KW_ON, KW_STOP))
{
stopStack.push(froot);
}
}
exitStack.push(null);
int firstNode = nodes.size();
// the 'root' AST is always a BLOCK node - this ensures that what we are walking are always
// STATEMENT or INNER_BLOCK - this will not allow to go inside another node, like a
// PROCEDDURE or FUNCTION defined within another block
for (int i = 0; i < numChildren; i++)
{
Aast child = root.getChildAt(i);
Aast flowAst = findFlowAst(child);
if (flowAst == null)
{
continue;
}
FlowAstNode node = astsToNodes.get(flowAst.getId());
if (node == null)
{
if (froot == null || flowAst.getId() != froot.ast.getId())
{
node = createNode(flowAst, depth++, parentId, groupId);
}
else
{
node = froot;
}
}
Set<FlowNode> lastExits = lastFlow.exits();
if (!lastExits.isEmpty())
{
linkExitNodes(lastExits, node, label);
}
else
{
FlowLink link = createLink(lastFlow, node, label, null);
link.setExit(true);
}
lastFlow = node;
isLastFlowExit = flowAst.getType() != KW_NEXT;
// from common-progress.rules:flow_control_usage
switch (flowAst.getType())
{
// flow_control_usage
case KW_IF:
{
int ibegin = nodes.size();
Aast aThen = null;
Aast aElse = null;
// we need the IF and first child of THEN and ELSE
String expr = dumpExpression((Aast) flowAst.getFirstChild());
node.setText("IF (" + expr + ")");
int ifDepth = depth;
aThen = findBlock(flowAst.getImmediateChild(KW_THEN, null));
aElse = findBlock(flowAst.getImmediateChild(KW_ELSE, null));
if (aElse != null && flowDir)
{
depth = processBranch(aElse, ifDepth, depth, node, groupId, "ELSE", "ELSE");
}
if (aThen != null)
{
depth = processBranch(aThen, ifDepth, depth, node, groupId, "THEN", "THEN");
}
if (aElse != null && !flowDir)
{
depth = processBranch(aElse, ifDepth, depth, node, groupId, "ELSE", "ELSE");
}
if (aElse == null)
{
// no ELSE, this needs to link to the next statement. we treat the IF as its
// own exit
node.addExit(node);
}
else
{
isLastFlowExit = false;
}
if (ibegin != nodes.size())
{
node.setBegin(ibegin);
node.setEnd(nodes.size() - 1);
}
break;
}
case KW_CASE:
{
int cbegin = nodes.size();
int caseDepth = depth;
Aast aOther = findBlock(flowAst.getImmediateChild(KW_OTHER, null));
if (aOther != null && flowDir)
{
depth = processBranch(aOther, caseDepth, depth, node, groupId, "OTHERWISE", "ELSE");
}
// we need the CASE and all the KW_THEN plus KW_OTHER
// KW_WHEN will be the label (condition) for the KW_CASE -WHEN-> KW_THEN links
String expr = dumpExpression((Aast) flowAst.getFirstChild());
node.setText("CASE (" + expr + ")");
Aast aThen = flowAst.getImmediateChild(KW_THEN, null);
while (aThen != null)
{
expr = dumpExpression((Aast) aThen.getPrevSibling().getFirstChild());
Aast bThen = findBlock(aThen);
depth = processBranch(bThen, caseDepth, depth, node, groupId, "WHEN " + expr, "THEN");
aThen = flowAst.getImmediateChild(KW_THEN, aThen);
}
if (aOther != null && !flowDir)
{
depth = processBranch(aOther, caseDepth, depth, node, groupId, "OTHERWISE", "ELSE");
}
if (aOther == null)
{
// no otherwise, we treat the CASE as its own exit
node.addExit(node);
}
else
{
isLastFlowExit = false;
}
node.setBegin(cbegin);
node.setEnd(nodes.size() - 1);
break;
}
case KW_LEAVE:
case KW_NEXT:
case KW_RETURN:
node.setText(node.getText().toUpperCase());
// no other sibling of this node will get executed
i = numChildren;
depth = processTarget(froot, node, flowAst, depth);
break;
case KW_STOP:
case KW_QUIT:
// no other sibling of this node will get executed
node.setText(node.getText().toUpperCase());
i = numChildren;
depth = processTarget(froot, node, flowAst, depth);
break;
// structured_error_block_ref - these are block-type statements
case KW_CATCH:
node.setText(node.getText().toUpperCase());
depth = Math.max(depth, loadFlowNodes(node, child, "CATCH", depth));
break;
case KW_FINALLY:
node.setText(node.getText().toUpperCase());
depth = Math.max(depth, loadFlowNodes(node, child, "FINALLY", depth));
break;
// inner_block_ref - these are block-type statements
case KW_DO:
case KW_REPEAT:
case KW_FOR:
depth = loadBlockFlow(depth, flowAst, child, (FlowBlockNode) node);
break;
default:
// in this case, we have a call-site statement
Vertex v = callsites.get(node.ast.getId());
if (v != null)
{
// find the target edge
Vertex[] target = new Vertex[1];
v.edges(Direction.OUT, "raises", "calls")
.forEachRemaining(e -> target[0] = e.inVertex());
if (target[0] != null)
{
node.setCallSite(CallGraphApi.buildCallSite(target[0]));
}
int callType = (Integer) CallGraphHelper.property(v, "node-type");
node.setType(ProgressParser.lookupTokenName(callType));
}
node.setText(dumpExpression(node.ast));
lastFlow.addExit(node);
break;
}
}
if (isBlock)
{
Aast whileAst = null;
Aast toAst = null;
boolean isLoop = false;
FlowNode end = null;
if (froot != null)
{
Aast flowRootAst = froot.ast;
whileAst = flowRootAst.getImmediateChild(KW_WHILE, null);
toAst = flowRootAst.getImmediateChild(KW_TO, null);
isLoop = (whileAst != null || toAst != null);
}
if (froot != null && !isLoop && start == nodes.get(nodes.size() - 1))
{
// this is a block with no control flow
nodes.remove(nodes.size() - 1);
depth = depth - 1;
start = null;
startNodes.remove(froot.getId());
}
else if (lastFlow != null && (isLoop || froot == null || !lastFlow.exits().isEmpty()))
{
if (froot == null)
{
if (exitStack.peek() == null)
{
end = createNode("EXIT", depth++, groupId);
exitStack.pop();
exitStack.push(end);
}
else
{
end = exitStack.peek();
}
}
else
{
end = createNode("END", depth++, groupId);
}
end.setParentId(lastFlow.getParentId());
linkExitNodes(lastFlow.exits(), end, "");
end.addExits(lastFlow.exits());
// link the exits to the end node
if (isLastFlowExit)
{
FlowLink link = createLink(lastFlow, end);
link.setExit(true);
}
}
}
if (froot != null &&
(!isBlock || !lastFlow.exits().isEmpty() || start == null) &&
(exitStack.peek() == null || !exitStack.peek().exits().contains(froot)))
{
froot.addExit(froot);
}
exitStack.pop();
if (froot != null)
{
if (froot.ast.downPath(KW_ON, KW_QUIT))
{
quitStack.pop();
}
if (froot.ast.downPath(KW_ON, KW_STOP))
{
stopStack.pop();
}
}
int lastNode = nodes.size();
if (froot != null)
{
froot.setBegin(firstNode);
froot.setEnd(lastNode - 1);
}
return depth;
}
/**
* Load the specified block in the flow chart.
*
* @param depth
* The current depth.
* @param flowAst
* The AST to be included in the flow.
* @param child
* The flowAst's ancestor, which was iterated originally in current block's children.
* @param node
* A new block node, for which the entire code set needs to be loaded.
*
* @return The new depth.
*/
private int loadBlockFlow( int depth,
final Aast flowAst,
final Aast child,
final FlowBlockNode node)
{
int begin = nodes.size();
Aast lblDef = flowAst.getParent().getImmediateChild(LABEL_DEF, null);
if (lblDef != null)
{
String lbl = lblDef.getText().toUpperCase();
labelTargets.put(lbl, child);
node.setBlockLabel(lbl);
}
Aast whileAst = flowAst.getImmediateChild(KW_WHILE, null);
Aast toAst = flowAst.getImmediateChild(KW_TO, null);
boolean isLoop = (whileAst != null || toAst != null);
// data for "WHILE expr"
FlowAstNode whileFlow = null;
// data for "v = ex1 TO ex2 [ BY k ]"
FlowAstNode assignFlow = null;
FlowAstNode exprFlow = null;
FlowNode incFlow = null;
FlowNode start = null;
// the nodes are created now, but the links are created after the body is processed
if (isLoop)
{
if (whileAst != null)
{
start = startNodes.get(node.getId());
if (start == null)
{
start = createNode("START", depth++, null);
startNodes.put(node.getId(), start);
}
whileFlow = createNode(whileAst, depth++, null,null);
String expr = dumpExpression((Aast) whileAst.getFirstChild());
whileFlow.setText("WHILE (" + expr + ")");
whileFlow.setType("KW_IF");
whileFlow.setLoop(true);
}
if (toAst != null)
{
start = startNodes.get(node.getId());
if (start == null)
{
start = createNode("START", depth++, null);
startNodes.put(node.getId(), start);
}
Aast toExpr1Ast = (Aast) toAst.getFirstChild();
Aast toExpr2Ast = (Aast) toExpr1Ast.getNextSibling();
assignFlow = createNode(toExpr1Ast, depth++, null, null);
String expr = dumpExpression(toExpr1Ast);
assignFlow.setText(expr);
exprFlow = createNode(toExpr2Ast, depth++, null, null);
expr = dumpExpression(toExpr2Ast);
exprFlow.setType("KW_IF");
Aast toCounterAst = (Aast) toAst.getFirstChild().getFirstChild();
String txt = toCounterAst.getText();
exprFlow.setText("IF (" + txt + " <= " + expr + ")");
assignFlow.setLoop(true);
exprFlow.setLoop(true);
}
}
int prevSize = nodes.size();
depth = Math.max(depth, loadFlowNodes(node, child, depth));
int nextSize = nodes.size();
FlowNode bstart = start;
FlowNode bend;
FlowLink bstartLink = null;
if (isLoop)
{
bend = nodes.get(nextSize - 1);
// find the link from bstart
for (int j = links.size() - 1; j >= 0; j--)
{
FlowLink l = links.get(j);
if (bstartLink == null && l.getSource() == start.getId())
{
bstartLink = l;
break;
}
}
}
else
{
bend = null;
}
if (whileAst != null)
{
// re-adjust parent/group IDs
whileFlow.setParentId(start.getParentId());
whileFlow.setGroupId(start.getGroupId());
// re-link the start/end and other nodes
// WHILE expr
/*
[start]
|
| /------------------------------------\
v V v-----------------[next] |
/-----------\ | |
| expr | -- yes -> [the block's code] --/
\-----------/ /
| |
no leave]
v |
[end] <----------------/
*/
whileFlow.setBegin(prevSize);
whileFlow.setEnd(nextSize - 2);
// link the start to the expr
createLink(start, whileFlow);
// re-link the start, instead of [start] -> [block], use [expr] -then-> [block]
bstartLink.setSource(whileFlow.getId());
bstartLink.setExit(false);
bstartLink.setType("THEN");
bstartLink.setText("THEN");
int parentId = nodes.get(bstartLink.getTarget()).getParentId();
for (int i = prevSize; i < nextSize; i++)
{
FlowNode n = nodes.get(i);
// all block code is parented at the THEN
if (n.getParentId() == parentId)
{
n.setParentId(whileFlow.getId());
}
// remove the END from the block's code, and leave it at the block
if (n instanceof FlowAstNode)
{
FlowAstNode anode = (FlowAstNode) n;
if (anode.getEnd() != null && anode.getEnd() == nextSize - 1)
{
anode.setEnd(anode.getEnd() - 1);
}
}
}
// TODO: if there is no code, add the first statement line
// TODO: this code needs to have the depth between START and END
// re-link the NEXT and RETRY links which target the START node
int whileFlowId = whileFlow.getId();
links.stream()
.filter(l -> l.getTarget() == bstart.getId() &&
("KW_NEXT".equals(l.getType()) || "KW_RETRY".equals(l.getType())))
.forEach(l -> l.setTarget(whileFlowId));
// normal, non-LEAVE links targeting END must link to the whileFlowId
links.stream()
.filter(l -> l.getTarget() == bend.getId() &&
!"KW_LEAVE".equals(nodes.get(l.getSource()).getType()))
.forEach(l -> { l.setTarget(whileFlowId); l.setType("KW_NEXT"); });
// create a ELSE link to the END node
FlowLink link = createLink(whileFlow, bend, "", "");
link.setExit(true);
}
if (toAst != null)
{
// create the 'incexpr'
Aast toByAst = toAst.getImmediateChild(KW_BY, null);
Aast toCounterAst = (Aast) toAst.getFirstChild().getFirstChild();
String txt = toCounterAst.getText();
String incTxt = "1";
if (toByAst != null)
{
incTxt = dumpExpression((Aast) toByAst.getFirstChild());
}
incTxt = txt + " = " + txt + " + " + incTxt;
incFlow = createNode(incTxt, depth++, null);
incFlow.setLoop(true);
// switch the depth between the end and incFlow nodes
int d1 = bend.getDepth();
int d2 = incFlow.getDepth();
bend.setDepth(d2);
incFlow.setDepth(d1);
// re-adjust parent/group IDs
assignFlow.setParentId(start.getParentId());
assignFlow.setGroupId(start.getGroupId());
exprFlow.setParentId(start.getParentId());
exprFlow.setGroupId(start.getGroupId());
incFlow.setParentId(start.getParentId());
incFlow.setGroupId(start.getGroupId());
// re-link the start/end and other nodes
// v = expr1 to expr2 [by k]
/*
[start]
|
|
V
[v = expr1]
|
| /------------------------------------------------------\
v V |
/-----------\ |
| v <= expr2 | -- yes -> [the block's code] --> [ v = v + k ] /
\-----------/ / \-------[next]----------^
| |
no |
v /
[end] <-------[leave]--
*/
exprFlow.setBegin(prevSize);
exprFlow.setEnd(nextSize - 1);
// link the start to the assignFlow
createLink(start, assignFlow);
// link the assignFlow to the exprFlow
createLink(assignFlow, exprFlow);
// link the incFlow to the exprFlow - this is a NEXT
createLink(incFlow, exprFlow, "", "KW_NEXT");
// re-link the start, instead of [start] -> [block], use [expr] -then-> [block]
bstartLink.setSource(exprFlow.getId());
bstartLink.setExit(false);
bstartLink.setType("THEN");
bstartLink.setText("THEN");
int parentId = nodes.get(bstartLink.getTarget()).getParentId();
for (int i = prevSize; i < nextSize; i++)
{
FlowNode n = nodes.get(i);
// all block code is parented at the THEN
if (n.getParentId() == parentId)
{
n.setParentId(exprFlow.getId());
}
// remove the END from the block's code, and leave it at the block
if (n instanceof FlowAstNode)
{
FlowAstNode anode = (FlowAstNode) n;
if (anode.getEnd() != null && anode.getEnd() == nextSize - 1)
{
anode.setEnd(anode.getEnd() - 1);
}
}
}
int exprFlowId = exprFlow.getId();
int incFlowId = incFlow.getId();
// re-link the NEXT links which target the START node - these will target incFlow
links.stream()
.filter(l -> l.getTarget() == bstart.getId() && "KW_NEXT".equals(l.getType()))
.forEach(l -> l.setTarget(incFlowId));
// RETRY links which target the START node will be target exprFlow
links.stream()
.filter(l -> l.getTarget() == bstart.getId() && "KW_RETRY".equals(l.getType()))
.forEach(l -> l.setTarget(exprFlowId));
// normal, non-LEAVE links targeting END must link to the incFlow
links.stream()
.filter(l -> l.getTarget() == bend.getId() &&
!"KW_LEAVE".equals(nodes.get(l.getSource()).getType()))
.forEach(l -> l.setTarget(incFlowId));
// create a ELSE link to the END node
FlowLink link = createLink(exprFlow, bend, "", "");
link.setExit(true);
}
node.setBegin(begin);
node.setEnd(nodes.size() - 1);
if (node.getBlockLabel() != null)
{
labelTargets.remove(node.getBlockLabel());
}
return depth;
}
/**
* Dump this ASTs as a 4GL code snippet.
*
* TODO: replace with anti-parser code.
*
* @param node
* The AST to dump.
*
* @return The anti-parsed AST text.
*/
private String dumpExpression(Aast node)
{
if (node.getParent().getType() == STATEMENT)
{
String txt = node.getText();
Aast child = (Aast) node.getFirstChild();
while (child != null)
{
txt = txt + " " + dumpExpression(child);
child = (Aast) child.getNextSibling();
}
return txt;
}
if (node.getType() != EXPRESSION)
{
return node.getText();
}
String txt = "";
if (node.getLine() != 0 && node.getColumn() != 0 && node.getFirstChild() == null)
{
txt = node.getText();
}
Aast child = (Aast) node.getFirstChild();
while (child != null)
{
int type = child.getType();
if (type >= BEGIN_FUNCTYPES && type <= END_FUNCTYPES)
{
txt = txt + child.getText() + "(";
Aast fchild = (Aast) child.getFirstChild();
boolean first = true;
while (fchild != null)
{
String expr = dumpExpression(fchild);
if (expr == null)
{
continue;
}
txt = txt + (first ? "" : ",") + expr;
first = false;
fchild = (Aast) fchild.getNextSibling();
}
txt = txt + ")";
}
else if (type == EQUALS || type == NOT_EQ ||
type == GT || type == LT || type == GTE || type == LTE ||
type == PLUS || type == MINUS || type == MULTIPLY || type == DIVIDE ||
type == KW_MOD ||
type == KW_OR || type == KW_AND ||
type == COLON || type == ASSIGN)
{
txt = txt + dumpExpression((Aast) child.getFirstChild()) + " ";
txt = txt + child.getText() + " ";
txt = txt + dumpExpression((Aast) child.getFirstChild().getNextSibling()) + " ";
}
else if (type == KW_NOT)
{
txt = txt + child.getText() + " ";
txt = txt + dumpExpression((Aast) child.getFirstChild()) + " ";
}
else
{
txt = txt + dumpExpression(child);
}
child = (Aast) child.getNextSibling();
}
return txt.trim();
}
/**
* If an AST which can be included in the flow chart, from the specified node's descendants.
*
* @param node
* The node which needs to be processed.
*
* @return If the node has a direct descendant one of the {@link #statementTypes},
* {@link #blockTypes} or {@link #callsites} ASTs, return it.
* Otherwise, return <code>null</code>.
*/
private Aast findFlowAst(Aast node)
{
int type = node.getType();
if (type == STATEMENT)
{
Aast ret = node.getImmediateChild(statementTypes, null);
if (ret != null && ret.getType() == KW_UNDO)
{
// discard the UNDO, use only its associated LEAVE/NEXT/RETRY/RETURN
ret = ret.getImmediateChild(statementTypes, null);
}
if (ret == null)
{
ret = (Aast) node.getFirstChild();
ret = callsites.containsKey(ret.getId()) ? ret : null;
}
return ret;
}
else if (type == INNER_BLOCK)
{
return node.getImmediateChild(blockTypes, null);
}
else
{
return null;
}
}
/**
* Find the block associated with this AST.
*
* @param node
* The source AST.
*
* @return The {@link ProgressParserTokenTypes#BLOCK} AST.
*/
private Aast findBlock(Aast node)
{
if (node == null)
{
return null;
}
int type = node.getType();
if (type == BLOCK || type == INNER_BLOCK)
{
return node;
}
if (node.downPath(INNER_BLOCK))
{
node = node.getImmediateChild(INNER_BLOCK, null);
}
else if (type != KW_FINALLY && type != KW_CATCH)
{
node = node.getImmediateChild(BLOCK, null);
}
return node;
}
/**
* Process a THEN/ELSE or WHEN/OTHERWISE branch, recursively, until the branch has finished.
*
* @param ast
* The first AST in the branch.
* @param pdepth
* The parent's depth.
* @param depth
* The current depth.
* @param node
* The node from which branching originates.
* @param groupId
* The group to which the branch belongs.
* @param elabel
* The edge label to link the node to the branch.
* @param etype
* The edge type to link the node to the branch.
*
* @return The new depth.
*/
private int processBranch(Aast ast,
int pdepth,
int depth,
FlowAstNode node,
Integer groupId,
String elabel,
String etype)
{
FlowAstNode fnode = createNode(ast, pdepth, node.getId(), groupId);
createLink(node, fnode, elabel, etype);
int begin = nodes.size();
if (fnode instanceof FlowBlockNode)
{
depth = Math.max(depth, loadBlockFlow(pdepth + 1, fnode.ast, ast, (FlowBlockNode) fnode));
}
else
{
depth = Math.max(depth, loadFlowNodes(fnode, ast, pdepth + 1));
}
node.addExits(fnode.exits());
if (begin != nodes.size())
{
fnode.setBegin(begin);
fnode.setEnd(nodes.size() - 1);
}
else
{
fnode.setBegin(null);
fnode.setEnd(null);
}
return depth;
}
/**
* Given a statement which may switch execution to a previous statement in a flow, find the
* target and link to it.
*
* @param block
* The block to which this node belongs.
* @param node
* The statement node.
* @param ast
* The associated AST.
* @param depth
* The next depth value.
*
* @return The new depth value.
*/
private int processTarget(FlowNode block, FlowNode node, Aast ast, int depth)
{
Aast targetAst = null;
int type = ast.getType();
String edgeLbl = "";
if (type == KW_QUIT)
{
if (!quitStack.isEmpty())
{
targetAst = quitStack.peek().ast;
}
edgeLbl = "QUIT";
}
else if (type == KW_STOP)
{
if (!stopStack.isEmpty())
{
targetAst = stopStack.peek().ast;
}
edgeLbl = "STOP";
}
else if (type == KW_RETURN)
{
// no label here
}
else
{
// in LEAVE/NEXT case, resolve the label
Aast lbl = ast.getImmediateChild(LABEL, null);
if (lbl == null && type == KW_RETRY)
{
// if not specified, inherit from UNDO
lbl = ast.getParent().getImmediateChild(LABEL, null);
}
if (lbl != null)
{
targetAst = labelTargets.get(lbl.getText().toUpperCase());
edgeLbl = lbl.getText().toUpperCase();
}
if (targetAst == null)
{
// see block_properties.rules lines 1280 and 1325 for conversion-time resolution for
// LEAVE and NEXT without a label
if (type == KW_NEXT || type == KW_RETRY)
{
// find first loop block
targetAst = findBlockAncestor(ast, a -> a.downPath(KW_REPEAT) ||
a.downPath(KW_FOR, KW_EACH) ||
a.downPath(KW_DO, KW_TO) ||
a.downPath(KW_DO, KW_WHILE));
// if not found, find first FOR FIRST/LAST block
if (targetAst == null)
{
targetAst = findBlockAncestor(ast, a -> a.downPath(KW_FOR, KW_FIRST) ||
a.downPath(KW_FOR, KW_LAST));
}
// if still not found, act like RETURN
}
else if (type == KW_LEAVE)
{
targetAst = findBlockAncestor(ast, a -> a.downPath(KW_REPEAT) ||
a.downPath(KW_FOR) ||
a.downPath(KW_DO, KW_TO) ||
a.downPath(KW_DO, KW_WHILE));
// if still not found, act like RETURN
}
}
if (targetAst != null)
{
int ttype = targetAst.getType();
if (type == KW_NEXT &&
ttype == KW_FOR &&
(targetAst.downPath(KW_FIRST) || targetAst.downPath(KW_LAST)))
{
// this is a leave
targetAst = null;
}
}
if (targetAst == null)
{
edgeLbl = "RETURN";
}
else if (type == KW_NEXT)
{
edgeLbl = "NEXT " + edgeLbl;
node.setText(edgeLbl);
}
else if (type == KW_LEAVE)
{
edgeLbl = "LEAVE " + edgeLbl;
node.setText(edgeLbl);
}
else if (type == KW_RETRY)
{
edgeLbl = "RETRY " + edgeLbl;
node.setText(edgeLbl);
}
node.setText(node.getText().trim());
edgeLbl = edgeLbl.trim();
}
if (targetAst == null)
{
// in this case, we are exiting the start node (RETURN or LEAVE/NEXT converted to RETURN)
FlowNode target = createNode("EXIT", depth++, node.getGroupId());
target.setParentId(node.getParentId());
FlowLink link = createLink(node, target, edgeLbl, null);
link.setExit(true);
exitStack.pop();
exitStack.push(target);
target.addExit(node);
}
else
{
targetAst = findFlowAst(targetAst);
FlowNode target = astsToNodes.get(targetAst.getId());
// depending on the statement, we are targeting the target or the target's sibling...
if (type == KW_NEXT || type == KW_RETRY)
{
target = startNodes.get(target.getId());
// this is a 'next' iteration, linking to the START node
String stype = type == KW_NEXT ? "KW_NEXT" : "KW_RETRY";
createLink(node, target, edgeLbl, stype);
target.setLoop(true);
}
else if (type == KW_LEAVE)
{
target.addExit(node);
}
else if(type == KW_STOP || type == KW_QUIT)
{
// we are targeting the next statement, this is an exit for the current block
block.addExit(node);
}
}
return depth;
}
/**
* Find an AST node with line/column annotations referring to a valid legacy code.
*
* @param ast
* The AST node.
*
* @return An AST node indicating the line/column of this code.
*/
private Aast findNodeSource(Aast ast)
{
// find first node which has the parent annotated with line/column
Aast prevParent = ast;
Aast lastp = ast;
while (lastp != null)
{
if (lastp.getLine() != 0)
{
break;
}
if (lastp.getType() == INNER_BLOCK)
{
Aast ch = lastp.getImmediateChild(Arrays.asList(KW_DO, KW_FOR, KW_REPEAT), null);
if (ch != null)
{
prevParent = ch;
}
else
{
prevParent = lastp;
}
break;
}
prevParent = lastp;
lastp = lastp.getParent();
}
// find first child which has line/column
if (prevParent.getLine() == 0)
{
lastp = (Aast) prevParent.getFirstChild();
while (lastp != null && lastp.getLine() == 0)
{
lastp = (Aast) lastp.getFirstChild();
}
if (lastp != null)
{
// failed to find, fallback
ast = lastp;
}
}
else
{
ast = prevParent;
}
return ast;
}
/**
* Create a new {@link FlowNode node} and add it to the {@link #nodes} list.
*
* @param type
* The node's type.
* @param depth
* The node's depth.
* @param groupId
* The node's group ID - may be <code>null</code>.
*
* @return The created node.
*/
private FlowNode createNode(String type, int depth, Integer groupId)
{
int nextId = nodes.size();
FlowNode node = new FlowNode(nextId, type);
node.setDepth(depth);
node.setGroupId(groupId);
nodes.add(node);
return node;
}
/**
* Create a new {@link FlowAstNode ast} or {@link FlowBlockNode block} node and add it to the
* {@link #nodes} list. Only FINALLY, CATCH, DO, REPEAT or FOR blocks will create a
* {@link FlowBlockNode} instance.
*
* @param ast
* The associated AST.
* @param depth
* The node's depth.
* @param parentId
* The node's parent ID - may be <code>null</code>.
* @param groupId
* The node's group ID - may be <code>null</code>.
*
* @return The created node.
*/
private FlowAstNode createNode(Aast ast, int depth, Integer parentId, Integer groupId)
{
return createNode(ast, depth, parentId, groupId, true);
}
/**
* Create a new {@link FlowAstNode ast} or {@link FlowBlockNode block} node and add it to the
* {@link #nodes} list. Only FINALLY, CATCH, DO, REPEAT or FOR blocks will create a
* {@link FlowBlockNode} instance.
*
* @param ast
* The associated AST.
* @param depth
* The node's depth.
* @param parentId
* The node's parent ID - may be <code>null</code>.
* @param groupId
* The node's group ID - may be <code>null</code>.
* @param resolve
* When set, this flag will not allow to create a new node for an AST existing in the
* {@link #astsToNodes} map.
*
* @return The created node.
*/
private FlowAstNode createNode(Aast ast,
int depth,
Integer parentId,
Integer groupId,
boolean resolve)
{
if (ast == null)
{
return null;
}
Aast srcAst = ast;
if (resolve)
{
if (ast.getType() == INNER_BLOCK)
{
ast = ast.getImmediateChild(blockTypes, null);
}
if (astsToNodes.containsKey(ast.getId()))
{
return astsToNodes.get(ast.getId());
}
srcAst = findNodeSource(ast);
if (statementTypes.contains(srcAst.getType()))
{
ast = srcAst;
}
}
else
{
srcAst = (ast.isRoot() ? ast
: ast.getType() == BLOCK ? ast.getIndexPos() == 0 ? ast.getParent()
: ast.getPrevSibling()
: (Aast) ast.getFirstChild());
if (srcAst.getType() == TRIGGER_BLOCK)
{
srcAst = srcAst.getParent();
}
}
int nextId = nodes.size();
FlowAstNode node = null;
int type = ast.getType();
if (type == KW_FINALLY ||
type == KW_CATCH ||
type == KW_DO ||
type == KW_REPEAT ||
type == KW_FOR)
{
node = new FlowBlockNode(nextId,
srcAst,
ProgressParser.lookupTokenName(srcAst.getType()),
srcAst.getText(),
srcAst.getLine(),
srcAst.getColumn());
computeBlockHeader((FlowBlockNode) node);
}
else
{
node = new FlowAstNode(nextId,
srcAst,
ProgressParser.lookupTokenName(srcAst.getType()),
srcAst.getText(),
srcAst.getLine(),
srcAst.getColumn());
}
nodes.add(node);
node.setDepth(depth);
AtomicInteger order = depthOrder.get(depth);
if (order == null)
{
depthOrder.put(depth, order = new AtomicInteger(0));
}
node.setOrder(order.getAndIncrement());
astsToNodes.put(ast.getId(), node);
node.setParentId(parentId);
node.setGroupId(groupId);
return node;
}
/**
* Compute the header for this block node - this includes resolving any ON phrases, WHERE or
* TO expression, FRAME name or buffer details.
*
* @param node
* The block node to augment with header details.
*/
private void computeBlockHeader(FlowBlockNode node)
{
Aast ast = node.ast;
// ON phrases: QUIT, STOP, ENDKEY, ENDERROR
Aast on = ast.getImmediateChild(KW_ON, null);
while (on != null)
{
String phrase = "";
Aast undoAst = on.getChildAt(on.getNumImmediateChildren() - 2);
Aast actionAst = on.getChildAt(on.getNumImmediateChildren() - 1);
phrase = undoAst.getText().toUpperCase();
if (undoAst.downPath(LABEL))
{
phrase = phrase + " " + undoAst.getFirstChild().getText();
}
phrase = phrase + ", " + actionAst.getText().toUpperCase();
if (actionAst.downPath(LABEL))
{
phrase = phrase + " " + actionAst.getFirstChild().getText();
}
if (on.downPath(KW_QUIT))
{
node.setOnQuit(phrase);
}
else if (on.downPath(KW_STOP))
{
node.setOnStop(phrase);
}
else if (on.downPath(KW_ERROR))
{
node.setOnError(phrase);
}
else if (on.downPath(KW_ENDKEY))
{
node.setOnEndkey(phrase);
}
node.setWithHeader(true);
on = ast.getImmediateChild(KW_ON, on);
}
// LOOP expr: WHILE, TO
if (ast.downPath(KW_WHILE))
{
Aast whileAst = ast.getImmediateChild(KW_WHILE, null);
node.setWhileExpr(dumpExpression((Aast) whileAst.getFirstChild()));
node.setWithHeader(true);
}
if (ast.downPath(KW_TO))
{
Aast toAst = ast.getImmediateChild(KW_TO, null);
node.setToExpr(dumpExpression((Aast) toAst.getFirstChild()));
node.setWithHeader(true);
}
// buffers: RECORD_PHRASE gives the buffer, prev sibling gives the type
Aast bast = ast.downPath(KW_PRESEL) ? ast.getImmediateChild(KW_PRESEL, null) : ast;
Aast recordPhrase = bast.getImmediateChild(RECORD_PHRASE, null);
String buffers = null;
while (recordPhrase != null)
{
Aast prev = recordPhrase.getPrevSibling();
String phrase = prev.getText().toUpperCase() + " " + recordPhrase.getFirstChild().getText();
if (buffers == null)
{
buffers = phrase;
}
else
{
buffers = buffers + ", " + phrase;
}
recordPhrase = ast.getImmediateChild(RECORD_PHRASE, recordPhrase);
}
node.setBuffers(buffers);
if (buffers != null)
{
node.setWithHeader(true);
node.setText(node.getText() + " " + buffers);
}
// TRANSACTION:
node.setTransaction(ast.downPath(KW_TRANS));
if (node.isTransaction())
{
node.setWithHeader(true);
}
// frame phrase
if (ast.downPath(FRAME_PHRASE, KW_FRAME, WID_FRAME))
{
node.setFrame(ast.getImmediateChild(FRAME_PHRASE, null)
.getImmediateChild(KW_FRAME, null)
.getImmediateChild(WID_FRAME, null)
.getText());
node.setWithHeader(true);
}
}
/**
* Create a new link between the specified source and target nodes, and add it to the
* {@link #links} list. Use an empty label and a <code>null</code> link type.
*
* @param source
* The source node.
* @param target
* The target node.
*
* @return The created link.
*/
private FlowLink createLink(FlowNode source, FlowNode target)
{
return createLink(source, target, "", null);
}
/**
* Create a new link between the specified source and target nodes, and add it to the
* {@link #links} list.
*
* @param source
* The source node.
* @param target
* The target node.
* @param label
* The link's label.
* @param type
* The link's type - may be <code>null</code>.
*
* @return The created link.
*/
private FlowLink createLink(FlowNode source, FlowNode target, String label, String type)
{
int nextId = links.size();
FlowLink link = new FlowLink(nextId, source.getId(), target.getId(), label, type);
links.add(link);
return link;
}
/**
* Link the specified exit nodes to the given target and mark the links as exits.
*
* @param sources
* The list of exit nodes.
* @param target
* The next reachable node (may be a START, END or EXIT node).
* @param label
* The link's label.
*/
private void linkExitNodes(Collection<FlowNode> sources, FlowNode target, String label)
{
// all remaining roots are linked to END
for (FlowNode src : sources)
{
FlowLink link = createLink(src, target, label, null);
link.setExit(true);
}
}
/**
* Find the nearest block ancestor satisfying the given predicate, without going outside of the
* {@link #topLevelBlock}. The explicit check of 'not going outside' of the top-level block
* is required because procedures may be defined within other blocks (but not nested).
*
* @param ast
* The ast from which to start looking.
* @param eval
* The predicate which needs to be evaluated.
*
* @return The found ancestor satisfying the predicate, or <code>null</code> if not found.
*/
private Aast findBlockAncestor(Aast ast, Predicate<Aast> eval)
{
// find first non-"simple DO block" ancestor; if non exists, convert to RETURN
Aast targetAst = ast.getAncestor(-1, INNER_BLOCK);
while (true)
{
if (targetAst == null)
{
break;
}
if (!topLevelBlock.isAncestorOf(0, targetAst))
{
// all found INNER_BLOCK nodes must be a child of the top-level-block we are
// exploring; if going above it, convert to RETURN
targetAst = null;
break;
}
if (eval.test(targetAst))
{
// found the required block, use it
break;
}
if (targetAst.isRoot())
{
// can't happen, but protect anyway
targetAst = null;
break;
}
targetAst = targetAst.getParent().getAncestor(-1, INNER_BLOCK);
}
return targetAst;
}
}