package edg.slicing; import edg.graph.EDG; 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 { /** Lookup map for subsumption, to be able to search by * context-current.node-lastEdgeType (current.stack=null in all keys). */ protected Map> subLookupMap; public ConstrainedSubsumedTabularAlgorithm(EDG edg) { super(edg); } @Override public Set slice(Node node) { subLookupMap = new HashMap<>(); return super.slice(node); } @Override protected void propagate(Work work) { if (!pathEdge.contains(work)) { Work wns = cloneNclearCurrentStack(work); Set 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 for (Work w : matchedWorks) if (work.current().stack().isSuffix(w.current().stack())) workList.remove(w); // Original behaviour pathEdge.add(work); workList.add(work); // Populate subLookupMap subLookupMap.computeIfAbsent(wns, k -> new HashSet<>()).add(work); } } } /** 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()); } }