dk.brics.xact.analysis.xmlgraph
Class FirstRootAnalysis

java.lang.Object
  dk.brics.xact.analysis.xmlgraph.ForwardsXGAnalyzer<EBooleanLattice>
      dk.brics.xact.analysis.xmlgraph.FirstRootAnalysis

public class FirstRootAnalysis
extends ForwardsXGAnalyzer<EBooleanLattice>

Determines which elements may occur as first root in some unfolding of an XML graph.

More specifically, a node N may be marked "first root=YES" if the following holds:

For every unfolding of the XML graph and for every occurence X of an unfolding of N inside the unfolded document, the first node in X is the first root in the unfolded document.

Conversely, a node N may be marked "first root=NO" if the following holds:

For every unfolding of the XML graph and for every occurence X of an unfolding of N inside the unfolded document, the first node in X is not the first root in the unfolded document.

If both properties are dissatisfied, then "first root=MAYBE" is the correct answer.

This definition means that a sequence node can be marked "first root" even though it unfolds to a sequence of nodes, of which only the first is the first root. For example:

  (root)
  SequenceNode (first root = YES)
    |
    +-> ChoiceNode (first root = YES)
    |       |
    |       +-> ElementNode (first root = YES)   
    |
    +-> ChoiceNode (first root = NO)
            |
            +-> ElementNode (first root = NO)   
 

An example where "first root" is MAYBE would be:

          (root)
       SequenceNode (first root = YES)
        /         \
  ChoiceNode    ChoiceNode
        \         /
        ElementNode (first root = MAYBE)
 

The analysis can be configured to consider attributes, elements, text nodes and gaps specially through its underlying emptiness analysis. Properly configured, it can answer questions such as "which nodes can occur as the first element root".

Constructor Summary

FirstRootAnalysis(XMLGraph xg, Emptiness emptiness, boolean allowText)

Method Summary

protected EBooleanLattice	bottom() Returns BOTTOM element.
protected EBooleanLattice	initial(Node node) Returns initial value for the specified node.
protected Set<Integer>	initialNodes() Returns the initial nodes.
protected void	transfer(EBooleanLattice src, Node node) Transfer data from the specified node to its children.

Methods inherited from class dk.brics.xact.analysis.xmlgraph.ForwardsXGAnalyzer

doAnalysis, get, get, getXmlGraph, put

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FirstRootAnalysis

public FirstRootAnalysis(XMLGraph xg,
                         Emptiness emptiness,
                         boolean allowText)

Method Detail

bottom

protected EBooleanLattice bottom()

Description copied from class: ForwardsXGAnalyzer

Returns BOTTOM element.

Specified by:

bottom in class ForwardsXGAnalyzer<EBooleanLattice>

Returns:

a lattice point

initial

protected EBooleanLattice initial(Node node)

Description copied from class: ForwardsXGAnalyzer

Returns initial value for the specified node.

Specified by:

initial in class ForwardsXGAnalyzer<EBooleanLattice>

Parameters:

node - one of the nodes whose index was returned by ForwardsXGAnalyzer.initialNodes()

Returns:

a lattice point

initialNodes

protected Set<Integer> initialNodes()

Description copied from class: ForwardsXGAnalyzer

Returns the initial nodes. This will typically be the root nodes in the XML graph. All initial nodes must be reachable from the graph's root nodes.

Specified by:

initialNodes in class ForwardsXGAnalyzer<EBooleanLattice>

Returns:

read-only set

transfer

protected void transfer(EBooleanLattice src,
                        Node node)

Description copied from class: ForwardsXGAnalyzer

Transfer data from the specified node to its children. Update node data using ForwardsXGAnalyzer.put(int, Object).

Specified by:

transfer in class ForwardsXGAnalyzer<EBooleanLattice>

Parameters:

src - lattice point for the specified node, provided for convenience

node - the node to transfer from