package dk.brics.xact.analysis.xmlgraph;
import dk.brics.xmlgraph.AttributeNode;
import dk.brics.xmlgraph.ChoiceNode;
import dk.brics.xmlgraph.ElementNode;
import dk.brics.xmlgraph.InterleaveNode;
import dk.brics.xmlgraph.Node;
import dk.brics.xmlgraph.NodeProcessor;
import dk.brics.xmlgraph.OneOrMoreNode;
import dk.brics.xmlgraph.SequenceNode;
import dk.brics.xmlgraph.TextNode;
import dk.brics.xmlgraph.XMLGraph;
/**
* May/must backwards analysis that determines which nodes in an XML graph have empty
* sequence unfoldings.
* <p/>
* It can be configured to treat attributes, elements, and/or text nodes as "bottom"
* or "empty" elements to take advantage of additional information available outside
* the XML graph.
* <p/>
* <b>Note:</b> The emptiness analysis is forced to treat comments and processing instructions
* as empty sequences because they are invisible in the XML graph. Make sure that you
* consider the possibility of their presence.
*/
public class Emptiness extends BackwardsXGAnalyzer<EPresence> {
private EPresence attributes;
private EPresence elements;
private EPresence texts;
private EPresence gaps;
/**
* Performs emptiness analysis on the specified XML graph.
* <p/>
* Each of the {@link EPresence} arguments may be set to <tt>null</tt> to let {@code Emptiness}
* choose a sound value by itself.
* @param xg XML graph to analyze
* @param attributes lattice point to assign an {@link AttributeNode}; or <tt>null</tt>
* @param elements lattice point to assign an {@link ElementNode}; or <tt>null</tt>
* @param texts lattice point to assign a {@link TextNode}; or <tt>null</tt>
* @param gaps lattice point to assign to a {@link ChoiceNode} that is a gap; or <tt>null</tt>
*/
public Emptiness(XMLGraph xg, EPresence attributes, EPresence elements, EPresence texts, EPresence gaps) {
super(xg);
this.attributes = attributes == null ? EPresence.NONEMPTY : attributes;
this.elements = elements == null ? EPresence.NONEMPTY : elements;
this.texts = texts;
this.gaps = gaps == null ? EPresence.NONEMPTY : gaps;
doAnalysis();
}
@Override
protected EPresence bottom() {
return EPresence.BOTTOM;
}
@Override
protected EPresence initial(Node node) {
if (node instanceof TextNode) {
TextNode tn = (TextNode)node;
if (texts != null)
return texts;
if (tn.getText().isEmpty())
return null;
if (tn.getText().isEmptyString())
return EPresence.EMPTY;
if (tn.getText().run(""))
return EPresence.UNKNOWN;
return EPresence.NONEMPTY;
} else if (node instanceof SequenceNode) {
SequenceNode sn = (SequenceNode)node;
if (sn.getContents().size() == 0)
return EPresence.EMPTY;
else
return null;
} else if (node instanceof ChoiceNode) {
ChoiceNode cn = (ChoiceNode)node;
if (cn.isGap() && cn.isOpen())
return gaps;
else
return null;
} else {
return null;
}
}
@Override
protected EPresence transfer(Node node, EPresence currentValue) {
EPresence e = node.process(processor);
return e.leastUpperBound(currentValue);
}
Processor processor = new Processor();
private final class Processor extends NodeProcessor<EPresence> {
@Override
public EPresence process(SequenceNode n) {
EPresence p = EPresence.EMPTY;
for (int child : n.getContents()) {
p = p.concat(get(child));
if (p.definitelyNonEmpty())
break;
}
return p;
}
@Override
public EPresence process(ChoiceNode n) {
EPresence p = EPresence.BOTTOM;
for (int child : n.getContents()) {
p = p.leastUpperBound(get(child));
if (p == EPresence.UNKNOWN)
break;
}
return p;
}
@Override
public EPresence process(AttributeNode n) {
return attributes;
}
@Override
public EPresence process(ElementNode n) {
return elements;
}
@Override
public EPresence process(TextNode n) {
return null; // unreachable
}
@Override
public EPresence process(InterleaveNode n) {
EPresence p = EPresence.EMPTY;
for (int child : n.getContents()) {
p = p.concat(get(child));
if (p.definitelyNonEmpty())
break;
}
return p;
}
@Override
public EPresence process(OneOrMoreNode n) {
return get(n.getContent());
}
}
}