validationconsumer.java

gcc的组建

     * it, traversals never interfere with each other.
     *
     * <p>There is an option to report non-deterministic models.  These are
     * always XML errors, but ones which are not often reported despite the
     * fact that they can lead to different validating parsers giving
     * different results for the same input.  (The XML spec doesn't require
     * them to be reported.)
     *
     * <p><b>FIXME</b> There's currently at least one known bug here, in that
     * it's not actually detecting the non-determinism it tries to detect.
     * (Of the "optional.xml" test, the once-or-twice-2* tests are all non-D;
     * maybe some others.)  This may relate to the issue flagged below as
     * "should not" happen (but it was), which showed up when patching the
     * graph to have one exit node (or more EMPTY nodes).
     */
    private static final class ChildrenRecognizer extends Recognizer
	implements Cloneable
    {
	// for reporting non-deterministic content models
	// ... a waste of space if we're not reporting those!
	// ... along with the 'model' member (in base class)
	private ValidationConsumer	consumer;

	// for CHOICE nodes -- each component is an arc that
	// accepts a different NAME (or is EMPTY indicating
	// NDFA termination).
	private Recognizer		components [];

	// for NAME/SEQUENCE nodes -- accepts that NAME and
	// then goes to the next node (CHOICE, NAME, EMPTY).
	private String			name;
	private Recognizer		next;

	// loops always point back to a CHOICE node. we mark such choice
	// nodes (F_LOOPHEAD) for diagnostics and faster deep cloning.
	// We also mark nodes before back pointers (F_LOOPNEXT), to ensure
	// termination when we patch sequences and loops.
	private int			flags;


	// prevent a needless indirection between 'this' and 'node'
	private void copyIn (ChildrenRecognizer node)
	{
	    // model & consumer are already set
	    components = node.components;
	    name = node.name;
	    next = node.next;
	    flags = node.flags;
	}

	// used to construct top level "children" content models,
	public ChildrenRecognizer (ElementInfo type, ValidationConsumer vc)
	{
	    this (vc, type);
	    populate (type.model.toCharArray (), 0);
	    patchNext (new EmptyRecognizer (type), null);
	}

	// used internally; populating is separate
	private ChildrenRecognizer (ValidationConsumer vc, ElementInfo type)
	{
	    super (type);
	    consumer = vc;
	}


	//
	// When rewriting some graph nodes we need deep clones in one case;
	// mostly shallow clones (what the JVM handles for us) are fine.
	//
	private ChildrenRecognizer shallowClone ()
	{
	    try {
		return (ChildrenRecognizer) clone ();
	    } catch (CloneNotSupportedException e) {
		throw new Error ("clone");
	    }
	}

	private ChildrenRecognizer deepClone ()
	{
	    return deepClone (new Hashtable (37));
	}

	private ChildrenRecognizer deepClone (Hashtable table)
	{
	    ChildrenRecognizer retval;

	    if ((flags & F_LOOPHEAD) != 0) {
		retval = (ChildrenRecognizer) table.get (this);
		if (retval != null)
		    return this;

		retval = shallowClone ();
		table.put (this, retval);
	    } else
		retval = shallowClone ();

	    if (next != null) {
		if (next instanceof ChildrenRecognizer)
		    retval.next = ((ChildrenRecognizer)next)
			    .deepClone (table);
		else if (!(next instanceof EmptyRecognizer))
		    throw new RuntimeException ("deepClone");
	    }

	    if (components != null) {
		retval.components = new Recognizer [components.length];
		for (int i = 0; i < components.length; i++) {
		    Recognizer temp = components [i];

		    if (temp == null)
			retval.components [i] = null;
		    else if (temp instanceof ChildrenRecognizer)
			retval.components [i] = ((ChildrenRecognizer)temp)
				.deepClone (table);
		    else if (!(temp instanceof EmptyRecognizer))
			throw new RuntimeException ("deepClone");
		}
	    }

	    return retval;
	}

	// connect subgraphs, first to next (sequencing)
	private void patchNext (Recognizer theNext, Hashtable table)
	{
	    // backpointers must not be repatched or followed
	    if ((flags & F_LOOPNEXT) != 0)
		return;

	    // XXX this table "shouldn't" be needed, right?
	    // but some choice nodes looped if it isn't there.
	    if (table != null && table.get (this) != null)
		return;
	    if (table == null)
		table = new Hashtable ();

	    // NAME/SEQUENCE
	    if (name != null) {
		if (next == null)
		    next = theNext;
		else if (next instanceof ChildrenRecognizer) {
		    ((ChildrenRecognizer)next).patchNext (theNext, table);
		} else if (!(next instanceof EmptyRecognizer))
		    throw new RuntimeException ("patchNext");
		return;
	    }

	    // CHOICE
	    for (int i = 0; i < components.length; i++) {
		if (components [i] == null)
		    components [i] = theNext;
		else if (components [i] instanceof ChildrenRecognizer) {
		    ((ChildrenRecognizer)components [i])
			    .patchNext (theNext, table);
		} else if (!(components [i] instanceof EmptyRecognizer))
		    throw new RuntimeException ("patchNext");
	    }

	    if (table != null && (flags & F_LOOPHEAD) != 0)
		table.put (this, this);
	}

	/**
	 * Parses a 'children' spec (or recursively 'cp') and makes this
	 * become a regular graph node.
	 *
	 * @return index after this particle
	 */
	private int populate (char parseBuf [], int startPos)
	{
	    int		nextPos = startPos + 1;
	    char	c;

	    if (nextPos < 0 || nextPos >= parseBuf.length)
		throw new IndexOutOfBoundsException ();

	    // Grammar of the string is from the XML spec, but
	    // with whitespace removed by the SAX parser.

	    // children ::= (choice | seq) ('?' | '*' | '+')?
	    // cp ::= (Name | choice | seq) ('?' | '*' | '+')?
	    // choice ::= '(' cp ('|' choice)* ')'
	    // seq ::= '(' cp (',' choice)* ')'

	    // interior nodes only
	    //   cp ::= name ...
	    if (parseBuf [startPos] != '('/*)*/) {
		boolean		done = false;
		do {
		    switch (c = parseBuf [nextPos]) {
			case '?': case '*': case '+':
			case '|': case ',':
			case /*(*/ ')':
			    done = true;
			    continue;
			default:
			    nextPos++;
			    continue;
		    }
		} while (!done);
		name = new String (parseBuf, startPos, nextPos - startPos);

	    // interior OR toplevel nodes
	    //   cp ::= choice ..
	    //   cp ::= seq ..
	    } else {
		// collect everything as a separate list, and merge it
		// into "this" later if we can (SEQUENCE or singleton)
		ChildrenRecognizer	first;
	       
		first = new ChildrenRecognizer (consumer, type);
		nextPos = first.populate (parseBuf, nextPos);
		c = parseBuf [nextPos++];

		if (c == ',' || c == '|') {
		    ChildrenRecognizer	current = first;
		    char		separator = c;
		    Vector		v = null;

		    if (separator == '|') {
			v = new Vector ();
			v.addElement (first);
		    }

		    do {
			ChildrenRecognizer link;

			link = new ChildrenRecognizer (consumer, type);
			nextPos = link.populate (parseBuf, nextPos);

			if (separator == ',') {
			    current.patchNext (link, null);
			    current = link;
			} else
			    v.addElement (link);

			c = parseBuf [nextPos++];
		    } while (c == separator);

		    // choice ... collect everything into one array.
		    if (separator == '|') {
			// assert v.size() > 1
			components = new Recognizer [v.size ()];
			for (int i = 0; i < components.length; i++) {
			    components [i] = (Recognizer)
				    v.elementAt (i);
			}
			// assert flags == 0

		    // sequence ... merge into "this" to be smaller.
		    } else
			copyIn (first);

		// treat singletons like one-node sequences.
		} else
		    copyIn (first);

		if (c != /*(*/ ')')
		    throw new RuntimeException ("corrupt content model");
	    }

	    //
	    // Arity is optional, and the root of all fun.  We keep the
	    // FSM state graph simple by only having NAME/SEQUENCE and
	    // CHOICE nodes (or EMPTY to terminate a model), easily
	    // evaluated.  So we rewrite each node that has arity, using
	    // those primitives.  We create loops here, if needed.
	    //
	    if (nextPos < parseBuf.length) {
		c = parseBuf [nextPos];
		if (c == '?' || c == '*' || c == '+') {
		    nextPos++;

		    // Rewrite 'zero-or-one' "?" arity to a CHOICE:
		    //   - SEQUENCE (clone, what's next)
		    //   - or, what's next
		    // Size cost: N --> N + 1
		    if (c == '?') {
			Recognizer		once = shallowClone ();

			components = new Recognizer [2];
			components [0] = once;
			// components [1] initted to null
			name = null;
			next = null;
			flags = 0;

			    
		    // Rewrite 'zero-or-more' "*" arity to a CHOICE.
		    //   - LOOP (clone, back to this CHOICE)
		    //   - or, what's next
		    // Size cost: N --> N + 1
		    } else if (c == '*') {
			ChildrenRecognizer	loop = shallowClone ();

			loop.patchNext (this, null);
			loop.flags |= F_LOOPNEXT;
			flags = F_LOOPHEAD;

			components = new Recognizer [2];
			components [0] = loop;
			// components [1] initted to null
			name = null;
			next = null;


		    // Rewrite 'one-or-more' "+" arity to a SEQUENCE.
		    // Basically (a)+ --> ((a),(a)*).
		    //   - this
		    //   - CHOICE
		    //	    * LOOP (clone, back to the CHOICE)
		    //	    * or, whatever's next
		    // Size cost: N --> 2N + 1
		    } else if (c == '+') {
			ChildrenRecognizer loop = deepClone ();
			ChildrenRecognizer choice;

			choice = new ChildrenRecognizer (consumer, type);
			loop.patchNext (choice, null);
			loop.flags |= F_LOOPNEXT;
			choice.flags = F_LOOPHEAD;

			choice.components = new Recognizer [2];
			choice.components [0] = loop;
			// choice.components [1] initted to null
			// choice.name, choice.next initted to null

			patchNext (choice, null);
		    }
		}
	    }

	    return nextPos;
	}

	// VC: Element Valid (second clause)
	boolean acceptCharacters ()
	    { return false; }

	// VC: Element Valid (second clause)
	Recognizer acceptElement (String type)
	throws SAXException
	{
	    // NAME/SEQUENCE
	    if (name != null) {
		if (name.equals (type))
		    return next;
		return null;
	    }

	    // CHOICE ... optionally reporting nondeterminism we
	    // run across.  we won't check out every transition
	    // for nondeterminism; only the ones we follow.
	    Recognizer	retval = null;

	    for (int i = 0; i < components.length; i++) {
		Recognizer temp = components [i].acceptElement (type);

		if (temp == null)
		    continue;
		else if (!warnNonDeterministic)
		    return temp;
		else if (retval == null)
		    retval = temp;
		else if (retval != temp)
		    consumer.error ("Content model " + this.type.model
			+ " is non-deterministic for " + type);
	    }
	    return retval;
	}

	// VC: Element Valid (second clause)
	boolean completed ()
	throws SAXException
	{
	    // expecting a specific element
	    if (name != null)
		return false;
	    
	    // choice, some sequences
	    for (int i = 0; i < components.length; i++) {
		if (components [i].completed ())
		    return true;
	    }

	    return false;
	}

/** /
	// FOR DEBUGGING ... flattens the graph for printing.

	public String toString ()
	{
	    StringBuffer buf = new StringBuffer ();

	    // only one set of loop labels can be generated
	    // at a time...
	    synchronized (ANY) {
		nodeCount = 0;

		toString (buf, new Hashtable ());
		return buf.toString ();
	    }
	}

	private void toString (StringBuffer buf, Hashtable table)
	{
	    // When we visit a node, label and count it.
	    // Nodes are never visited/counted more than once.
	    // For small models labels waste space, but if arity
	    // mappings were used the savings are substantial.
	    // (Plus, the output can be more readily understood.)
	    String temp = (String) table.get (this);

	    if (temp != null) {
		buf.append ('{');
		buf.append (temp);
		buf.append ('}');
		return;
	    } else {
		StringBuffer scratch = new StringBuffer (15);

		if ((flags & F_LOOPHEAD) != 0)
		    scratch.append ("loop");
		else
		    scratch.append ("node");
		scratch.append ('-');
		scratch.append (++nodeCount);
		temp = scratch.toString ();

		table.put (this, temp);
		buf.append ('[');
		buf.append (temp);
		buf.append (']');
		buf.append (':');
	    }

	    // NAME/SEQUENCE
	    if (name != null) {
		// n.b. some output encodings turn some name chars into '?'
		// e.g. with Japanese names and ASCII output
		buf.append (name);
		if (components != null)		// bug!
		    buf.append ('$');
		if (next == null)
		    buf.append (",*");
		else if (next instanceof EmptyRecognizer) // patch-to-next
		    buf.append (",{}");
		else if (next instanceof ChildrenRecognizer) {
		    buf.append (',');
		    ((ChildrenRecognizer)next).toString (buf, table);
		} else				// bug!
		    buf.append (",+");
		return;
	    }

	    // CHOICE
	    buf.append ("<");
	    for (int i = 0; i < components.length; i++) {
		if (i != 0)
		    buf.append ("|");
		if (components [i] instanceof EmptyRecognizer) {
		    buf.append ("{}");
		} else if (components [i] == null) {	// patch-to-next
		    buf.append ('*');
		} else {
		    ChildrenRecognizer r;

		    r = (ChildrenRecognizer) components [i];
		    r.toString (buf, table);
		}
	    }
	    buf.append (">");
	}
/**/
    }
}