Skip to content
ConstrainedSubsumedTabularAlgorithm.java 2.02 KiB
Newer Older
package edg.slicing;

import edg.graph.EDG;

/**
 * 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.
 */
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<Work, Set<Work>> subLookupMap;
    public ConstrainedSubsumedTabularAlgorithm(EDG edg) {
        super(edg);
    }

    @Override
    public Set<Node> slice(Node node) {
        subLookupMap = new HashMap<>();
        return super.slice(node);
    }

    @Override
    protected void propagate(Work work) {
            Work wns = cloneNclearCurrentStack(work);
            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
                    if (work.current().stack().isSuffix(w.current().stack()))
                // 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());