APIdia Launch Partner
Top Description Fields Constructors Methods
com.sun.org.apache.xerces.internal.impl.dtd.models

public Class DFAContentModel

extends Object
implements ContentModelValidator
Class Inheritance
All Implemented Interfaces
com.sun.org.apache.xerces.internal.impl.dtd.models.ContentModelValidator
Imports
com.sun.org.apache.xerces.internal.impl.dtd.XMLContentSpec, com.sun.org.apache.xerces.internal.xni.QName, java.util.HashMap, .Map
DFAContentModel is the derivative of ContentModel that does all of the non-trivial element content validation. This class does the conversion from the regular expression to the DFA that it then uses in its validation algorithm.

Note

Upstream work insures that this class will never see a content model with PCDATA in it. Any model with PCDATA is 'mixed' and is handled via the MixedContentModel class since mixed models are very constrained in form and easily handled via a special case. This also makes implementation of this class much easier.

Field Summary

Modifier and TypeField and Description
private static final boolean
DEBUG_VALIDATE_CONTENT

Set to true to debug content model validation.

private QName[]
fElemMap

This is the map of unique input symbol elements to indices into each state's per-input symbol transition table entry.

private int
fElemMapSize

The element map size.

private int[]
fElemMapType

This is a map of whether the element map contains information related to ANY models.

private boolean
fEmptyContentIsValid

Flag that indicates that even though we have a "complicated" content model, it is valid to have no content.

private int
fEOCPos

The NFA position of the special EOC (end of content) node.

private static String
fEOCString

End-of-content string.

private static String
fEpsilonString

Epsilon string.

private boolean[]
fFinalStateFlags

This is an array of booleans, one per state (there are fTransTableSize states in the DFA) that indicates whether that state is a final state.

private CMStateSet[]
fFollowList

The list of follow positions for each NFA position (i.e. for each non-epsilon leaf node.) This is only used during the building of the DFA, and is let go afterwards.

private CMNode
fHeadNode

This is the head node of our intermediate representation.

private int
fLeafCount

The count of leaf nodes.

private CMLeaf[]
fLeafList

An array of non-epsilon leaf nodes, which is used during the DFA build operation, then dropped.

private int[]
fLeafListType

Array mapping ANY types to the leaf list.

private boolean
fMixed

Boolean to distinguish Schema Mixed Content

private final QName
fQName

Temporary qualified name.

private int[][]
fTransTable

This is the transition table that is the main by product of all of the effort here.

private int
fTransTableSize

The number of valid entries in the transition table, and in the other related tables such as fFinalStateFlags.

Constructor Summary

AccessConstructor and Description
public
DFAContentModel(CMNode
The syntax tree of the content model.
syntaxTree, int
The number of leaves.
leafCount, boolean mixed)

Constructs a DFA content model.

Method Summary

Modifier and TypeMethod and Description
private void
buildDFA(CMNode
The syntax tree.
syntaxTree)

Builds the internal DFA transition table from the given syntax tree.

private void
calcFollowList(CMNode
The curent node.
nodeCur)

Calculates the follow list of the current node.

private void
dumpTree(CMNode
The current node.
nodeCur, int
The maximum levels to output.
level)

Dumps the tree of the current node to standard output.

private int[]
makeDefStateList()

-1 is used to represent bad transitions in the transition table entry for each state.

private int
postTreeBuildInit(CMNode nodeCur, int curIndex)

Post tree build initialization.

public int

Returns:

The value -1 if fully valid, else the 0 based index of the child that first failed. If the value returned is equal to the number of children, then the specified children are valid but additional content is required to reach a valid ending state.
validate(QName[]
The children of this element. Each integer is an index within the StringPool of the child element name. An index of -1 is used to indicate an occurrence of non-whitespace character data.
children, int
Offset into the array where the children starts.
offset, int
The number of entries in the children array.
length)

Implements com.sun.org.apache.xerces.internal.impl.dtd.models.ContentModelValidator.validate.

Check that the specified content is valid according to this content model.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

DEBUG_VALIDATE_CONTENTback to summary
private static final boolean DEBUG_VALIDATE_CONTENT

Set to true to debug content model validation.

fElemMapback to summary
private QName[] fElemMap

This is the map of unique input symbol elements to indices into each state's per-input symbol transition table entry. This is part of the built DFA information that must be kept around to do the actual validation.

fElemMapSizeback to summary
private int fElemMapSize

The element map size.

fElemMapTypeback to summary
private int[] fElemMapType

This is a map of whether the element map contains information related to ANY models.

fEmptyContentIsValidback to summary
private boolean fEmptyContentIsValid

Flag that indicates that even though we have a "complicated" content model, it is valid to have no content. In other words, all parts of the content model are optional. For example: 

     <!ELEMENT AllOptional (Optional*,NotRequired?)>
fEOCPosback to summary
private int fEOCPos

The NFA position of the special EOC (end of content) node. This is saved away since it's used during the DFA build.

fEOCStringback to summary
private static String fEOCString

End-of-content string.

fEpsilonStringback to summary
private static String fEpsilonString

Epsilon string.

fFinalStateFlagsback to summary
private boolean[] fFinalStateFlags

This is an array of booleans, one per state (there are fTransTableSize states in the DFA) that indicates whether that state is a final state.

fFollowListback to summary
private CMStateSet[] fFollowList

The list of follow positions for each NFA position (i.e. for each non-epsilon leaf node.) This is only used during the building of the DFA, and is let go afterwards.

fHeadNodeback to summary
private CMNode fHeadNode

This is the head node of our intermediate representation. It is only non-null during the building of the DFA (just so that it does not have to be passed all around.) Once the DFA is built, this is no longer required so its nulled out.

fLeafCountback to summary
private int fLeafCount

The count of leaf nodes. This is an important number that set some limits on the sizes of data structures in the DFA process.

fLeafListback to summary
private CMLeaf[] fLeafList

An array of non-epsilon leaf nodes, which is used during the DFA build operation, then dropped.

fLeafListTypeback to summary
private int[] fLeafListType

Array mapping ANY types to the leaf list.

fMixedback to summary
private boolean fMixed

Boolean to distinguish Schema Mixed Content

fQNameback to summary
private final QName fQName

Temporary qualified name.

fTransTableback to summary
private int[][] fTransTable

This is the transition table that is the main by product of all of the effort here. It is an array of arrays of ints. The first dimension is the number of states we end up with in the DFA. The second dimensions is the number of unique elements in the content model (fElemMapSize). Each entry in the second dimension indicates the new state given that input for the first dimension's start state.

The fElemMap array handles mapping from element indexes to positions in the second dimension of the transition table.

fTransTableSizeback to summary
private int fTransTableSize

The number of valid entries in the transition table, and in the other related tables such as fFinalStateFlags.

Constructor Detail

DFAContentModelback to summary
public DFAContentModel(CMNode syntaxTree, int leafCount, boolean mixed)

Constructs a DFA content model.

Parameters
syntaxTree:CMNode

The syntax tree of the content model.

leafCount:int

The number of leaves.

Method Detail

buildDFAback to summary
private void buildDFA(CMNode syntaxTree)

Builds the internal DFA transition table from the given syntax tree.

Parameters
syntaxTree:CMNode

The syntax tree.

Exceptions
CMException:
Thrown if DFA cannot be built.
calcFollowListback to summary
private void calcFollowList(CMNode nodeCur)

Calculates the follow list of the current node.

Parameters
nodeCur:CMNode

The curent node.

Exceptions
CMException:
Thrown if follow list cannot be calculated.
dumpTreeback to summary
private void dumpTree(CMNode nodeCur, int level)

Dumps the tree of the current node to standard output.

Parameters
nodeCur:CMNode

The current node.

level:int

The maximum levels to output.

Exceptions
CMException:
Thrown on error.
makeDefStateListback to summary
private int[] makeDefStateList()

-1 is used to represent bad transitions in the transition table entry for each state. So each entry is initialized to an all -1 array. This method creates a new entry and initializes it.

postTreeBuildInitback to summary
private int postTreeBuildInit(CMNode nodeCur, int curIndex)

Post tree build initialization.

validateback to summary
public int validate(QName[] children, int offset, int length)

Implements com.sun.org.apache.xerces.internal.impl.dtd.models.ContentModelValidator.validate.

Check that the specified content is valid according to this content model. This method can also be called to do 'what if' testing of content models just to see if they would be valid.

A value of -1 in the children array indicates a PCDATA node. All other indexes will be positive and represent child elements. The count can be zero, since some elements have the EMPTY content model and that must be confirmed.

Parameters
children:QName[]

The children of this element. Each integer is an index within the StringPool of the child element name. An index of -1 is used to indicate an occurrence of non-whitespace character data.

offset:int

Offset into the array where the children starts.

length:int

The number of entries in the children array.

Returns:int

The value -1 if fully valid, else the 0 based index of the child that first failed. If the value returned is equal to the number of children, then the specified children are valid but additional content is required to reach a valid ending state.