ConstrainedSubsumedTabularAlgorithm.java

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<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) {
        if (!pathEdge.contains(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
                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());
    }
}