Newer
Older
package edg.slicing;
import edg.graph.EDG;
Carlos Galindo
committed
import edg.graph.Node;
import java.util.*;
/**
* Constraind tabular algorithm with subsumption.
* It uses stack ordering to disallow insertion into pathEdge and workList if a subsuming
* stack is included in them already.
* @see ConstrainedTabularAlgorithm
*/
public class ConstrainedSubsumedTabularAlgorithm extends ConstrainedTabularAlgorithm {
Carlos Galindo
committed
/** Lookup map for subsumption, to be able to search by
* context-current.node-lastEdgeType (current.stack=null in all keys). */
protected Map<Work, Set<Work>> subLookupMap;
Carlos Galindo
committed
public ConstrainedSubsumedTabularAlgorithm(EDG edg) {
super(edg);
}
Carlos Galindo
committed
@Override
public Set<Node> slice(Node node) {
subLookupMap = new HashMap<>();
return super.slice(node);
}
@Override
protected void propagate(Work work) {
if (!pathEdge.contains(work)) {
Work wns = cloneNclearCurrentStack(work);
Carlos Galindo
committed
Set<Work> matchedWorks = subLookupMap.getOrDefault(wns, Collections.emptySet());
if (work.current().stack().isEdgeConstraintsEmpty() ||
matchedWorks.stream()
.map(Work::current)
.map(State::stack)
.noneMatch(work.current().stack()::isSuffix)) {
// Removed subsumed copies that haven't been analyzed yet
Carlos Galindo
committed
for (Work w : matchedWorks)
if (work.current().stack().isSuffix(w.current().stack()))
Carlos Galindo
committed
workList.remove(w);
pathEdge.add(work);
workList.add(work);
// Populate subLookupMap
subLookupMap.computeIfAbsent(wns, k -> new HashSet<>()).add(work);
}
Carlos Galindo
committed
/** Create an object suitable as a {@link #subLookupMap} key. */
protected Work cloneNclearCurrentStack(Work work) {
return new Work(work.context(), new State(work.current().node(), null), work.lastEdgeType());
Carlos Galindo
committed
}