aboutsummaryrefslogtreecommitdiff
path: root/libjava/gnu/xml/pipeline/ValidationConsumer.java
diff options
context:
space:
mode:
Diffstat (limited to 'libjava/gnu/xml/pipeline/ValidationConsumer.java')
-rw-r--r--libjava/gnu/xml/pipeline/ValidationConsumer.java1922
1 files changed, 1922 insertions, 0 deletions
diff --git a/libjava/gnu/xml/pipeline/ValidationConsumer.java b/libjava/gnu/xml/pipeline/ValidationConsumer.java
new file mode 100644
index 0000000..e73c0ff
--- /dev/null
+++ b/libjava/gnu/xml/pipeline/ValidationConsumer.java
@@ -0,0 +1,1922 @@
+/* ValidationConsumer.java --
+ Copyright (C) 1999,2000,2001 Free Software Foundation, Inc.
+
+This file is part of GNU Classpath.
+
+GNU Classpath is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Classpath is distributed in the hope that it will be useful, but
+WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Classpath; see the file COPYING. If not, write to the
+Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+02111-1307 USA.
+
+Linking this library statically or dynamically with other modules is
+making a combined work based on this library. Thus, the terms and
+conditions of the GNU General Public License cover the whole
+combination.
+
+As a special exception, the copyright holders of this library give you
+permission to link this library with independent modules to produce an
+executable, regardless of the license terms of these independent
+modules, and to copy and distribute the resulting executable under
+terms of your choice, provided that you also meet, for each linked
+independent module, the terms and conditions of the license of that
+module. An independent module is a module which is not derived from
+or based on this library. If you modify this library, you may extend
+this exception to your version of the library, but you are not
+obligated to do so. If you do not wish to do so, delete this
+exception statement from your version. */
+
+package gnu.xml.pipeline;
+
+import java.io.*;
+
+import java.util.EmptyStackException;
+import java.util.Enumeration;
+import java.util.Hashtable;
+import java.util.Stack;
+import java.util.StringTokenizer;
+import java.util.Vector;
+
+import org.xml.sax.*;
+import org.xml.sax.ext.*;
+import org.xml.sax.helpers.XMLReaderFactory;
+
+
+/**
+ * This class checks SAX2 events to report validity errors; it works as
+ * both a filter and a terminus on an event pipeline. It relies on the
+ * producer of SAX events to: </p> <ol>
+ *
+ * <li> Conform to the specification of a non-validating XML parser that
+ * reads all external entities, reported using SAX2 events. </li>
+ *
+ * <li> Report ignorable whitespace as such (through the ContentHandler
+ * interface). This is, strictly speaking, optional for nonvalidating
+ * XML processors. </li>
+ *
+ * <li> Make SAX2 DeclHandler callbacks, with default
+ * attribute values already normalized (and without "&lt;").</li>
+ *
+ * <li> Make SAX2 LexicalHandler startDTD() and endDTD ()
+ * callbacks. </li>
+ *
+ * <li> Act as if the <em>(URI)/namespace-prefixes</em> property were
+ * set to true, by providing XML 1.0 names and all <code>xmlns*</code>
+ * attributes (rather than omitting either or both). </li>
+ *
+ * </ol>
+ *
+ * <p> At this writing, the major SAX2 parsers (such as &AElig;lfred2,
+ * Crimson, and Xerces) meet these requirements, and this validation
+ * module is used by the optional &AElig;lfred2 validation support.
+ * </p>
+ *
+ * <p> Note that because this is a layered validator, it has to duplicate some
+ * work that the parser is doing; there are also other cost to layering.
+ * However, <em>because of layering it doesn't need a parser</em> in order
+ * to work! You can use it with anything that generates SAX events, such
+ * as an application component that wants to detect invalid content in
+ * a changed area without validating an entire document, or which wants to
+ * ensure that it doesn't write invalid data to a communications partner.</p>
+ *
+ * <p> Also, note that because this is a layered validator, the line numbers
+ * reported for some errors may seem strange. For example, if an element does
+ * not permit character content, the validator
+ * will use the locator provided to it.
+ * That might reflect the last character of a <em>characters</em> event
+ * callback, rather than the first non-whitespace character. </p>
+ *
+ * <hr />
+ *
+ * <!--
+ * <p> Of interest is the fact that unlike most currently known XML validators,
+ * this one can report some cases of non-determinism in element content models.
+ * It is a compile-time option, enabled by default. This will only report
+ * such XML errors if they relate to content actually appearing in a document;
+ * content models aren't aggressively scanned for non-deterministic structure.
+ * Documents which trigger such non-deterministic transitions may be handled
+ * differently by different validating parsers, without losing conformance
+ * to the XML specification. </p>
+ * -->
+ *
+ * <p> Current limitations of the validation performed are in roughly three
+ * categories. </p>
+ *
+ * <p> The first category represents constraints which demand violations
+ * of software layering: exposing lexical details, one of the first things
+ * that <em>application</em> programming interfaces (APIs) hide. These
+ * invariably relate to XML entity handling, and to historical oddities
+ * of the XML validation semantics. Curiously,
+ * recent (Autumn 1999) conformance testing showed that these constraints are
+ * among those handled worst by existing XML validating parsers. Arguments
+ * have been made that each of these VCs should be turned into WFCs (most
+ * of them) or discarded (popular for the standalone declaration); in short,
+ * that these are bugs in the XML specification (not all via SGML): </p><ul>
+ *
+ * <li> The <em>Proper Declaration/PE Nesting</em> and
+ * <em>Proper Group/PE Nesting</em> VCs can't be tested because they
+ * require access to particularly low level lexical level information.
+ * In essence, the reason XML isn't a simple thing to parse is that
+ * it's not a context free grammar, and these constraints elevate that
+ * SGML-derived context sensitivity to the level of a semantic rule.
+ *
+ * <li> The <em>Standalone Document Declaration</em> VC can't be
+ * tested. This is for two reasons. First, this flag isn't made
+ * available through SAX2. Second, it also requires breaking that
+ * lexical layering boundary. (If you ever wondered why classes
+ * in compiler construction or language design barely mention the
+ * existence of context-sensitive grammars, it's because of messy
+ * issues like these.)
+ *
+ * <li> The <em>Entity Declared</em> VC can't be tested, because it
+ * also requires breaking that lexical layering boundary! There's also
+ * another issue: the VC wording (and seemingly intent) is ambiguous.
+ * (This is still true in the "Second edition" XML spec.)
+ * Since there is a WFC of the same name, everyone's life would be
+ * easier if references to undeclared parsed entities were always well
+ * formedness errors, regardless of whether they're parameter entities
+ * or not. (Note that nonvalidating parsers are not required
+ * to report all such well formedness errors if they don't read external
+ * parameter entities, although currently most XML parsers read them
+ * in an attempt to avoid problems from inconsistent parser behavior.)
+ *
+ * </ul>
+ *
+ * <p> The second category of limitations on this validation represent
+ * constraints associated with information that is not guaranteed to be
+ * available (or in one case, <em>is guaranteed not to be available</em>,
+ * through the SAX2 API: </p><ul>
+ *
+ * <li> The <em>Unique Element Type Declaration</em> VC may not be
+ * reportable, if the underlying parser happens not to expose
+ * multiple declarations. (&AElig;lfred2 reports these validity
+ * errors directly.)</li>
+ *
+ * <li> Similarly, the <em>Unique Notation Name</em> VC, added in the
+ * 14-January-2000 XML spec errata to restrict typing models used by
+ * elements, may not be reportable. (&AElig;lfred reports these
+ * validity errors directly.) </li>
+ *
+ * </ul>
+ *
+ * <p> A third category relates to ease of implementation. (Think of this
+ * as "bugs".) The most notable issue here is character handling. Rather
+ * than attempting to implement the voluminous character tables in the XML
+ * specification (Appendix B), Unicode rules are used directly from
+ * the java.lang.Character class. Recent JVMs have begun to diverge from
+ * the original specification for that class (Unicode 2.0), meaning that
+ * different JVMs may handle that aspect of conformance differently.
+ * </p>
+ *
+ * <p> Note that for some of the validity errors that SAX2 does not
+ * expose, a nonvalidating parser is permitted (by the XML specification)
+ * to report validity errors. When used with a parser that does so for
+ * the validity constraints mentioned above (or any other SAX2 event
+ * stream producer that does the same thing), overall conformance is
+ * substantially improved.
+ *
+ * @see gnu.xml.aelfred2.SAXDriver
+ * @see gnu.xml.aelfred2.XmlReader
+ *
+ * @author David Brownell
+ */
+public final class ValidationConsumer extends EventFilter
+{
+ // report error if we happen to notice a non-deterministic choice?
+ // we won't report buggy content models; just buggy instances
+ private static final boolean warnNonDeterministic = false;
+
+ // for tracking active content models
+ private String rootName;
+ private Stack contentStack = new Stack ();
+
+ // flags for "saved DTD" processing
+ private boolean disableDeclarations;
+ private boolean disableReset;
+
+ //
+ // most VCs get tested when we see element start tags. the per-element
+ // info (including attributes) recorded here duplicates that found inside
+ // many nonvalidating parsers, hence dual lookups etc ... that's why a
+ // layered validator isn't going to be as fast as a non-layered one.
+ //
+
+ // key = element name; value = ElementInfo
+ private Hashtable elements = new Hashtable ();
+
+ // some VCs relate to ID/IDREF/IDREFS attributes
+ // key = id; value = boolean true (defd) or false (refd)
+ private Hashtable ids = new Hashtable ();
+
+ // we just record declared notation and unparsed entity names.
+ // the implementation here is simple/slow; these features
+ // are seldom used, one hopes they'll wither away soon
+ private Vector notations = new Vector (5, 5);
+ private Vector nDeferred = new Vector (5, 5);
+ private Vector unparsed = new Vector (5, 5);
+ private Vector uDeferred = new Vector (5, 5);
+
+ // note: DocBk 3.1.7 XML defines over 2 dozen notations,
+ // used when defining unparsed entities for graphics
+ // (and maybe in other places)
+
+
+
+ /**
+ * Creates a pipeline terminus which consumes all events passed to
+ * it; this will report validity errors as if they were fatal errors,
+ * unless an error handler is assigned.
+ *
+ * @see #setErrorHandler
+ */
+ // constructor used by PipelineFactory
+ // ... and want one taking system ID of an external subset
+ public ValidationConsumer ()
+ {
+ this (null);
+ }
+
+ /**
+ * Creates a pipeline filter which reports validity errors and then
+ * passes events on to the next consumer if they were not fatal.
+ *
+ * @see #setErrorHandler
+ */
+ // constructor used by PipelineFactory
+ // ... and want one taking system ID of an external subset
+ // (which won't send declaration events)
+ public ValidationConsumer (EventConsumer next)
+ {
+ super (next);
+
+ setContentHandler (this);
+ setDTDHandler (this);
+ try { setProperty (DECL_HANDLER, this); }
+ catch (Exception e) { /* "can't happen" */ }
+ try { setProperty (LEXICAL_HANDLER, this); }
+ catch (Exception e) { /* "can't happen" */ }
+ }
+
+
+ private static final String fakeRootName
+ = ":Nobody:in:their_Right.Mind_would:use:this-name:1x:";
+
+ /**
+ * Creates a validation consumer which is preloaded with the DTD provided.
+ * It does this by constructing a document with that DTD, then parsing
+ * that document and recording its DTD declarations. Then it arranges
+ * not to modify that information.
+ *
+ * <p> The resulting validation consumer will only validate against
+ * the specified DTD, regardless of whether some other DTD is found
+ * in a document being parsed.
+ *
+ * @param rootName The name of the required root element; if this is
+ * null, any root element name will be accepted.
+ * @param publicId If non-null and there is a non-null systemId, this
+ * identifier provides an alternate access identifier for the DTD's
+ * external subset.
+ * @param systemId If non-null, this is a URI (normally URL) that
+ * may be used to access the DTD's external subset.
+ * @param internalSubset If non-null, holds literal markup declarations
+ * comprising the DTD's internal subset.
+ * @param resolver If non-null, this will be provided to the parser for
+ * use when resolving parameter entities (including any external subset).
+ * @param resolver If non-null, this will be provided to the parser for
+ * use when resolving parameter entities (including any external subset).
+ * @param minimalElement If non-null, a minimal valid document.
+ *
+ * @exception SAXNotSupportedException If the default SAX parser does
+ * not support the standard lexical or declaration handlers.
+ * @exception SAXParseException If the specified DTD has either
+ * well-formedness or validity errors
+ * @exception IOException If the specified DTD can't be read for
+ * some reason
+ */
+ public ValidationConsumer (
+ String rootName,
+ String publicId,
+ String systemId,
+ String internalSubset,
+ EntityResolver resolver,
+ String minimalDocument
+ ) throws SAXException, IOException
+ {
+ this (null);
+
+ disableReset = true;
+ if (rootName == null)
+ rootName = fakeRootName;
+
+ //
+ // Synthesize document with that DTD; is it possible to do
+ // better for the declaration of the root element?
+ //
+ // NOTE: can't use SAX2 to write internal subsets.
+ //
+ StringWriter writer = new StringWriter ();
+
+ writer.write ("<!DOCTYPE ");
+ writer.write (rootName);
+ if (systemId != null) {
+ writer.write ("\n ");
+ if (publicId != null) {
+ writer.write ("PUBLIC '");
+ writer.write (publicId);
+ writer.write ("'\n\t'");
+ } else
+ writer.write ("SYSTEM '");
+ writer.write (systemId);
+ writer.write ("'");
+ }
+ writer.write (" [ ");
+ if (rootName == fakeRootName) {
+ writer.write ("\n<!ELEMENT ");
+ writer.write (rootName);
+ writer.write (" EMPTY>");
+ }
+ if (internalSubset != null)
+ writer.write (internalSubset);
+ writer.write ("\n ]>");
+
+ if (minimalDocument != null) {
+ writer.write ("\n");
+ writer.write (minimalDocument);
+ writer.write ("\n");
+ } else {
+ writer.write (" <");
+ writer.write (rootName);
+ writer.write ("/>\n");
+ }
+ minimalDocument = writer.toString ();
+
+ //
+ // OK, load it
+ //
+ XMLReader producer;
+
+ producer = XMLReaderFactory.createXMLReader ();
+ bind (producer, this);
+
+ if (resolver != null)
+ producer.setEntityResolver (resolver);
+
+ InputSource in;
+
+ in = new InputSource (new StringReader (minimalDocument));
+ producer.parse (in);
+
+ disableDeclarations = true;
+ if (rootName == fakeRootName)
+ this.rootName = null;
+ }
+
+ private void resetState ()
+ {
+ if (!disableReset) {
+ rootName = null;
+ contentStack.removeAllElements ();
+ elements.clear ();
+ ids.clear ();
+
+ notations.removeAllElements ();
+ nDeferred.removeAllElements ();
+ unparsed.removeAllElements ();
+ uDeferred.removeAllElements ();
+ }
+ }
+
+
+ private void warning (String description)
+ throws SAXException
+ {
+ ErrorHandler errHandler = getErrorHandler ();
+ Locator locator = getDocumentLocator ();
+ SAXParseException err;
+
+ if (errHandler == null)
+ return;
+
+ if (locator == null)
+ err = new SAXParseException (description, null, null, -1, -1);
+ else
+ err = new SAXParseException (description, locator);
+ errHandler.warning (err);
+ }
+
+ // package private (for ChildrenRecognizer)
+ private void error (String description)
+ throws SAXException
+ {
+ ErrorHandler errHandler = getErrorHandler ();
+ Locator locator = getDocumentLocator ();
+ SAXParseException err;
+
+ if (locator == null)
+ err = new SAXParseException (description, null, null, -1, -1);
+ else
+ err = new SAXParseException (description, locator);
+ if (errHandler != null)
+ errHandler.error (err);
+ else // else we always treat it as fatal!
+ throw err;
+ }
+
+ private void fatalError (String description)
+ throws SAXException
+ {
+ ErrorHandler errHandler = getErrorHandler ();
+ Locator locator = getDocumentLocator ();
+ SAXParseException err;
+
+ if (locator != null)
+ err = new SAXParseException (description, locator);
+ else
+ err = new SAXParseException (description, null, null, -1, -1);
+ if (errHandler != null)
+ errHandler.fatalError (err);
+ // we always treat this as fatal, regardless of the handler
+ throw err;
+ }
+
+
+ private static boolean isExtender (char c)
+ {
+ // [88] Extender ::= ...
+ return c == 0x00b7 || c == 0x02d0 || c == 0x02d1 || c == 0x0387
+ || c == 0x0640 || c == 0x0e46 || c == 0x0ec6 || c == 0x3005
+ || (c >= 0x3031 && c <= 0x3035)
+ || (c >= 0x309d && c <= 0x309e)
+ || (c >= 0x30fc && c <= 0x30fe);
+ }
+
+
+ // use augmented Unicode rules, not full XML rules
+ private boolean isName (String name, String context, String id)
+ throws SAXException
+ {
+ char buf [] = name.toCharArray ();
+ boolean pass = true;
+
+ if (!Character.isUnicodeIdentifierStart (buf [0])
+ && ":_".indexOf (buf [0]) == -1)
+ pass = false;
+ else {
+ int max = buf.length;
+ for (int i = 1; pass && i < max; i++) {
+ char c = buf [i];
+ if (!Character.isUnicodeIdentifierPart (c)
+ && ":-_.".indexOf (c) == -1
+ && !isExtender (c))
+ pass = false;
+ }
+ }
+
+ if (!pass)
+ error ("In " + context + " for " + id
+ + ", '" + name + "' is not a name");
+ return pass; // true == OK
+ }
+
+ // use augmented Unicode rules, not full XML rules
+ private boolean isNmtoken (String nmtoken, String context, String id)
+ throws SAXException
+ {
+ char buf [] = nmtoken.toCharArray ();
+ boolean pass = true;
+ int max = buf.length;
+
+ // XXX make this share code with isName
+
+ for (int i = 0; pass && i < max; i++) {
+ char c = buf [i];
+ if (!Character.isUnicodeIdentifierPart (c)
+ && ":-_.".indexOf (c) == -1
+ && !isExtender (c))
+ pass = false;
+ }
+
+ if (!pass)
+ error ("In " + context + " for " + id
+ + ", '" + nmtoken + "' is not a name token");
+ return pass; // true == OK
+ }
+
+ private void checkEnumeration (String value, String type, String name)
+ throws SAXException
+ {
+ if (!hasMatch (value, type))
+ // VC: Enumeration
+ error ("Value '" + value
+ + "' for attribute '" + name
+ + "' is not permitted: " + type);
+ }
+
+ // used to test enumerated attributes and mixed content models
+ // package private
+ static boolean hasMatch (String value, String orList)
+ {
+ int len = value.length ();
+ int max = orList.length () - len;
+
+ for (int start = 0;
+ (start = orList.indexOf (value, start)) != -1;
+ start++) {
+ char c;
+
+ if (start > max)
+ break;
+ c = orList.charAt (start - 1);
+ if (c != '|' && c != '('/*)*/)
+ continue;
+ c = orList.charAt (start + len);
+ if (c != '|' && /*(*/ c != ')')
+ continue;
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * <b>LexicalHandler</b> Records the declaration of the root
+ * element, so it can be verified later.
+ * Passed to the next consumer, unless this one was
+ * preloaded with a particular DTD.
+ */
+ public void startDTD (String name, String publicId, String systemId)
+ throws SAXException
+ {
+ if (disableDeclarations)
+ return;
+
+ rootName = name;
+ super.startDTD (name, publicId, systemId);
+ }
+
+ /**
+ * <b>LexicalHandler</b> Verifies that all referenced notations
+ * and unparsed entities have been declared.
+ * Passed to the next consumer, unless this one was
+ * preloaded with a particular DTD.
+ */
+ public void endDTD ()
+ throws SAXException
+ {
+ if (disableDeclarations)
+ return;
+
+ // this is a convenient hook for end-of-dtd checks, but we
+ // could also trigger it in the first startElement call.
+ // locator info is more appropriate here though.
+
+ // VC: Notation Declared (NDATA can refer to them before decls,
+ // as can NOTATION attribute enumerations and defaults)
+ int length = nDeferred.size ();
+ for (int i = 0; i < length; i++) {
+ String notation = (String) nDeferred.elementAt (i);
+ if (!notations.contains (notation)) {
+ error ("A declaration referred to notation '" + notation
+ + "' which was never declared");
+ }
+ }
+ nDeferred.removeAllElements ();
+
+ // VC: Entity Name (attribute values can refer to them
+ // before they're declared); VC Attribute Default Legal
+ length = uDeferred.size ();
+ for (int i = 0; i < length; i++) {
+ String entity = (String) uDeferred.elementAt (i);
+ if (!unparsed.contains (entity)) {
+ error ("An attribute default referred to entity '" + entity
+ + "' which was never declared");
+ }
+ }
+ uDeferred.removeAllElements ();
+ super.endDTD ();
+ }
+
+
+ // These are interned, so we can rely on "==" to find the type of
+ // all attributes except enumerations ...
+ // "(this|or|that|...)" and "NOTATION (this|or|that|...)"
+ static final String types [] = {
+ "CDATA",
+ "ID", "IDREF", "IDREFS",
+ "NMTOKEN", "NMTOKENS",
+ "ENTITY", "ENTITIES"
+ };
+
+
+ /**
+ * <b>DecllHandler</b> Records attribute declaration for later use
+ * in validating document content, and checks validity constraints
+ * that are applicable to attribute declarations.
+ * Passed to the next consumer, unless this one was
+ * preloaded with a particular DTD.
+ */
+ public void attributeDecl (
+ String eName,
+ String aName,
+ String type,
+ String mode,
+ String value
+ ) throws SAXException
+ {
+ if (disableDeclarations)
+ return;
+
+ ElementInfo info = (ElementInfo) elements.get (eName);
+ AttributeInfo ainfo = new AttributeInfo ();
+ boolean checkOne = false;
+ boolean interned = false;
+
+ // cheap interning of type names and #FIXED, #REQUIRED
+ // for faster startElement (we can use "==")
+ for (int i = 0; i < types.length; i++) {
+ if (types [i].equals (type)) {
+ type = types [i];
+ interned = true;
+ break;
+ }
+ }
+ if ("#FIXED".equals (mode))
+ mode = "#FIXED";
+ else if ("#REQUIRED".equals (mode))
+ mode = "#REQUIRED";
+
+ ainfo.type = type;
+ ainfo.mode = mode;
+ ainfo.value = value;
+
+ // we might not have seen the content model yet
+ if (info == null) {
+ info = new ElementInfo (eName);
+ elements.put (eName, info);
+ }
+ if ("ID" == type) {
+ checkOne = true;
+ if (!("#REQUIRED" == mode || "#IMPLIED".equals (mode))) {
+ // VC: ID Attribute Default
+ error ("ID attribute '" + aName
+ + "' must be #IMPLIED or #REQUIRED");
+ }
+
+ } else if (!interned && type.startsWith ("NOTATION ")) {
+ checkOne = true;
+
+ // VC: Notation Attributes (notations must be declared)
+ StringTokenizer tokens = new StringTokenizer (
+ type.substring (10, type.lastIndexOf (')')),
+ "|");
+ while (tokens.hasMoreTokens ()) {
+ String token = tokens.nextToken ();
+ if (!notations.contains (token))
+ nDeferred.addElement (token);
+ }
+ }
+ if (checkOne) {
+ for (Enumeration e = info.attributes.keys ();
+ e.hasMoreElements ();
+ /* NOP */) {
+ String name;
+ AttributeInfo ainfo2;
+
+ name = (String) e.nextElement ();
+ ainfo2 = (AttributeInfo) info.attributes.get (name);
+ if (type == ainfo2.type || !interned /* NOTATION */) {
+ // VC: One ID per Element Type
+ // VC: One Notation per Element TYpe
+ error ("Element '" + eName
+ + "' already has an attribute of type "
+ + (interned ? "NOTATION" : type)
+ + " ('" + name
+ + "') so '" + aName
+ + "' is a validity error");
+ }
+ }
+ }
+
+ // VC: Attribute Default Legal
+ if (value != null) {
+
+ if ("CDATA" == type) {
+ // event source rejected '<'
+
+ } else if ("NMTOKEN" == type) {
+ // VC: Name Token (is a nmtoken)
+ isNmtoken (value, "attribute default", aName);
+
+ } else if ("NMTOKENS" == type) {
+ // VC: Name Token (is a nmtoken; at least one value)
+ StringTokenizer tokens = new StringTokenizer (value);
+ if (!tokens.hasMoreTokens ())
+ error ("Default for attribute '" + aName
+ + "' must have at least one name token.");
+ else do {
+ String token = tokens.nextToken ();
+ isNmtoken (token, "attribute default", aName);
+ } while (tokens.hasMoreTokens ());
+
+ } else if ("IDREF" == type || "ENTITY" == type) {
+ // VC: Entity Name (is a name)
+ // VC: IDREF (is a name) (is declared)
+ isName (value, "attribute default", aName);
+ if ("ENTITY" == type && !unparsed.contains (value))
+ uDeferred.addElement (value);
+
+ } else if ("IDREFS" == type || "ENTITIES" == type) {
+ // VC: Entity Name (is a name; at least one value)
+ // VC: IDREF (is a name; at least one value)
+ StringTokenizer names = new StringTokenizer (value);
+ if (!names.hasMoreTokens ())
+ error ("Default for attribute '" + aName
+ + "' must have at least one name.");
+ else do {
+ String name = names.nextToken ();
+ isName (name, "attribute default", aName);
+ if ("ENTITIES" == type && !unparsed.contains (name))
+ uDeferred.addElement (value);
+ } while (names.hasMoreTokens ());
+
+ } else if (type.charAt (0) == '(' /*)*/ ) {
+ // VC: Enumeration (must match)
+ checkEnumeration (value, type, aName);
+
+ } else if (!interned && checkOne) { /* NOTATION */
+ // VC: Notation attributes (must be names)
+ isName (value, "attribute default", aName);
+
+ // VC: Notation attributes (must be declared)
+ if (!notations.contains (value))
+ nDeferred.addElement (value);
+
+ // VC: Enumeration (must match)
+ checkEnumeration (value, type, aName);
+
+ } else if ("ID" != type)
+ throw new RuntimeException ("illegal attribute type: " + type);
+ }
+
+ if (info.attributes.get (aName) == null)
+ info.attributes.put (aName, ainfo);
+ /*
+ else
+ warning ("Element '" + eName
+ + "' already has an attribute named '" + aName + "'");
+ */
+
+ if ("xml:space".equals (aName)) {
+ if (!("(default|preserve)".equals (type)
+ || "(preserve|default)".equals (type)
+ // these next two are arguable; XHTML's DTD doesn't
+ // deserve errors. After all, it's not like any
+ // illegal _value_ could pass ...
+ || "(preserve)".equals (type)
+ || "(default)".equals (type)
+ ))
+ error (
+ "xml:space attribute type must be like '(default|preserve)'"
+ + " not '" + type + "'"
+ );
+
+ }
+ super.attributeDecl (eName, aName, type, mode, value);
+ }
+
+ /**
+ * <b>DecllHandler</b> Records the element declaration for later use
+ * when checking document content, and checks validity constraints that
+ * apply to element declarations. Passed to the next consumer, unless
+ * this one was preloaded with a particular DTD.
+ */
+ public void elementDecl (String name, String model)
+ throws SAXException
+ {
+ if (disableDeclarations)
+ return;
+
+ ElementInfo info = (ElementInfo) elements.get (name);
+
+ // we might have seen an attribute decl already
+ if (info == null) {
+ info = new ElementInfo (name);
+ elements.put (name, info);
+ }
+ if (info.model != null) {
+ // NOTE: not all parsers can report such duplicates.
+ // VC: Unique Element Type Declaration
+ error ("Element type '" + name
+ + "' was already declared.");
+ } else {
+ info.model = model;
+
+ // VC: No Duplicate Types (in mixed content models)
+ if (model.charAt (1) == '#') // (#PCDATA...
+ info.getRecognizer (this);
+ }
+ super.elementDecl (name, model);
+ }
+
+ /**
+ * <b>DecllHandler</b> passed to the next consumer, unless this
+ * one was preloaded with a particular DTD
+ */
+ public void internalEntityDecl (String name, String value)
+ throws SAXException
+ {
+ if (!disableDeclarations)
+ super.internalEntityDecl (name, value);
+ }
+
+ /**
+ * <b>DecllHandler</b> passed to the next consumer, unless this
+ * one was preloaded with a particular DTD
+ */
+ public void externalEntityDecl (String name,
+ String publicId, String systemId)
+ throws SAXException
+ {
+ if (!disableDeclarations)
+ super.externalEntityDecl (name, publicId, systemId);
+ }
+
+
+ /**
+ * <b>DTDHandler</b> Records the notation name, for checking
+ * NOTATIONS attribute values and declararations of unparsed
+ * entities. Passed to the next consumer, unless this one was
+ * preloaded with a particular DTD.
+ */
+ public void notationDecl (String name, String publicId, String systemId)
+ throws SAXException
+ {
+ if (disableDeclarations)
+ return;
+
+ notations.addElement (name);
+ super.notationDecl (name, publicId, systemId);
+ }
+
+ /**
+ * <b>DTDHandler</b> Records the entity name, for checking
+ * ENTITY and ENTITIES attribute values; records the notation
+ * name if it hasn't yet been declared. Passed to the next consumer,
+ * unless this one was preloaded with a particular DTD.
+ */
+ public void unparsedEntityDecl (
+ String name,
+ String publicId,
+ String systemId,
+ String notationName
+ ) throws SAXException
+ {
+ if (disableDeclarations)
+ return;
+
+ unparsed.addElement (name);
+ if (!notations.contains (notationName))
+ nDeferred.addElement (notationName);
+ super.unparsedEntityDecl (name, publicId, systemId, notationName);
+ }
+
+
+ /**
+ * <b>ContentHandler</b> Ensures that state from any previous parse
+ * has been deleted.
+ * Passed to the next consumer.
+ */
+ public void startDocument ()
+ throws SAXException
+ {
+ resetState ();
+ super.startDocument ();
+ }
+
+
+ private static boolean isAsciiLetter (char c)
+ {
+ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
+ }
+
+
+ /**
+ * <b>ContentHandler</b> Reports a fatal exception. Validating
+ * XML processors may not skip any entities.
+ */
+ public void skippedEntity (String name)
+ throws SAXException
+ {
+ fatalError ("may not skip entities");
+ }
+
+ /*
+ * SAX2 doesn't expand non-PE refs in attribute defaults...
+ */
+ private String expandDefaultRefs (String s)
+ throws SAXException
+ {
+ if (s.indexOf ('&') < 0)
+ return s;
+
+// FIXME: handle &#nn; &#xnn; &name;
+ String message = "Can't expand refs in attribute default: " + s;
+ warning (message);
+
+ return s;
+ }
+
+ /**
+ * <b>ContentHandler</b> Performs validity checks against element
+ * (and document) content models, and attribute values.
+ * Passed to the next consumer.
+ */
+ public void startElement (
+ String uri,
+ String localName,
+ String qName,
+ Attributes atts
+ ) throws SAXException
+ {
+ //
+ // First check content model for the enclosing scope.
+ //
+ if (contentStack.isEmpty ()) {
+ // VC: Root Element Type
+ if (!qName.equals (rootName)) {
+ if (rootName == null)
+ warning ("This document has no DTD, can't be valid");
+ else
+ error ("Root element type '" + qName
+ + "' was declared to be '" + rootName + "'");
+ }
+ } else {
+ Recognizer state = (Recognizer) contentStack.peek ();
+
+ if (state != null) {
+ Recognizer newstate = state.acceptElement (qName);
+
+ if (newstate == null)
+ error ("Element type '" + qName
+ + "' in element '" + state.type.name
+ + "' violates content model " + state.type.model
+ );
+ if (newstate != state) {
+ contentStack.pop ();
+ contentStack.push (newstate);
+ }
+ }
+ }
+
+ //
+ // Then check that this element was declared, and push the
+ // object used to validate its content model onto our stack.
+ //
+ // This is where the recognizer gets created, if needed; if
+ // it's a "children" (elements) content model, an NDFA is
+ // created. (One recognizer is used per content type, no
+ // matter how complex that recognizer is.)
+ //
+ ElementInfo info;
+
+ info = (ElementInfo) elements.get (qName);
+ if (info == null || info.model == null) {
+ // VC: Element Valid (base clause)
+ error ("Element type '" + qName + "' was not declared");
+ contentStack.push (null);
+
+ // for less diagnostic noise, fake a declaration.
+ elementDecl (qName, "ANY");
+ } else
+ contentStack.push (info.getRecognizer (this));
+
+ //
+ // Then check each attribute present
+ //
+ int len;
+ String aname;
+ AttributeInfo ainfo;
+
+ if (atts != null)
+ len = atts.getLength ();
+ else
+ len = 0;
+
+ for (int i = 0; i < len; i++) {
+ aname = atts.getQName (i);
+
+ if (info == null
+ || (ainfo = (AttributeInfo) info.attributes.get (aname))
+ == null) {
+ // VC: Attribute Value Type
+ error ("Attribute '" + aname
+ + "' was not declared for element type " + qName);
+ continue;
+ }
+
+ String value = atts.getValue (i);
+
+ // note that "==" for type names and "#FIXED" is correct
+ // (and fast) since we've interned those literals.
+
+ if ("#FIXED" == ainfo.mode) {
+ String expanded = expandDefaultRefs (ainfo.value);
+
+ // VC: Fixed Attribute Default
+ if (!value.equals (expanded)) {
+ error ("Attribute '" + aname
+ + "' must match " + expanded
+ );
+ continue;
+ }
+ }
+
+ if ("CDATA" == ainfo.type)
+ continue;
+
+ //
+ // For all other attribute types, there are various
+ // rules to follow.
+ //
+
+ if ("ID" == ainfo.type) {
+ // VC: ID (must be a name)
+ if (isName (value, "ID attribute", aname)) {
+ if (Boolean.TRUE == ids.get (value))
+ // VC: ID (appears once)
+ error ("ID attribute " + aname
+ + " uses an ID value '" + value
+ + "' which was already declared.");
+ else
+ // any forward refs are no longer problems
+ ids.put (value, Boolean.TRUE);
+ }
+ continue;
+ }
+
+ if ("IDREF" == ainfo.type) {
+ // VC: IDREF (value must be a name)
+ if (isName (value, "IDREF attribute", aname)) {
+ // VC: IDREF (must match some ID attribute)
+ if (ids.get (value) == null)
+ // new -- assume it's a forward ref
+ ids.put (value, Boolean.FALSE);
+ }
+ continue;
+ }
+
+ if ("IDREFS" == ainfo.type) {
+ StringTokenizer tokens = new StringTokenizer (value, " ");
+
+ if (!tokens.hasMoreTokens ()) {
+ // VC: IDREF (one or more values)
+ error ("IDREFS attribute " + aname
+ + " must have at least one ID ref");
+ } else do {
+ String id = tokens.nextToken ();
+
+ // VC: IDREF (value must be a name)
+ if (isName (id, "IDREFS attribute", aname)) {
+ // VC: IDREF (must match some ID attribute)
+ if (ids.get (id) == null)
+ // new -- assume it's a forward ref
+ ids.put (id, Boolean.FALSE);
+ }
+ } while (tokens.hasMoreTokens ());
+ continue;
+ }
+
+ if ("NMTOKEN" == ainfo.type) {
+ // VC: Name Token (is a name token)
+ isNmtoken (value, "NMTOKEN attribute", aname);
+ continue;
+ }
+
+ if ("NMTOKENS" == ainfo.type) {
+ StringTokenizer tokens = new StringTokenizer (value, " ");
+
+ if (!tokens.hasMoreTokens ()) {
+ // VC: Name Token (one or more values)
+ error ("NMTOKENS attribute " + aname
+ + " must have at least one name token");
+ } else do {
+ String token = tokens.nextToken ();
+
+ // VC: Name Token (is a name token)
+ isNmtoken (token, "NMTOKENS attribute", aname);
+ } while (tokens.hasMoreTokens ());
+ continue;
+ }
+
+ if ("ENTITY" == ainfo.type) {
+ if (!unparsed.contains (value))
+ // VC: Entity Name
+ error ("Value of attribute '" + aname
+ + "' refers to unparsed entity '" + value
+ + "' which was not declared.");
+ continue;
+ }
+
+ if ("ENTITIES" == ainfo.type) {
+ StringTokenizer tokens = new StringTokenizer (value, " ");
+
+ if (!tokens.hasMoreTokens ()) {
+ // VC: Entity Name (one or more values)
+ error ("ENTITIES attribute " + aname
+ + " must have at least one name token");
+ } else do {
+ String entity = tokens.nextToken ();
+
+ if (!unparsed.contains (entity))
+ // VC: Entity Name
+ error ("Value of attribute '" + aname
+ + "' refers to unparsed entity '" + entity
+ + "' which was not declared.");
+ } while (tokens.hasMoreTokens ());
+ continue;
+ }
+
+ //
+ // check for enumerations last; more expensive
+ //
+ if (ainfo.type.charAt (0) == '(' /*)*/
+ || ainfo.type.startsWith ("NOTATION ")
+ ) {
+ // VC: Enumeration (value must be defined)
+ checkEnumeration (value, ainfo.type, aname);
+ continue;
+ }
+ }
+
+ //
+ // Last, check that all #REQUIRED attributes were provided
+ //
+ if (info != null) {
+ Hashtable table = info.attributes;
+
+ if (table.size () != 0) {
+ Enumeration e = table.keys ();
+
+ // XXX table.keys uses the heap, bleech -- slows things
+
+ while (e.hasMoreElements ()) {
+ aname = (String) e.nextElement ();
+ ainfo = (AttributeInfo) table.get (aname);
+
+ // "#REQUIRED" mode was interned in attributeDecl
+ if ("#REQUIRED" == ainfo.mode
+ && atts.getValue (aname) == null) {
+ // VC: Required Attribute
+ error ("Attribute '" + aname + "' must be specified "
+ + "for element type " + qName);
+ }
+ }
+ }
+ }
+ super.startElement (uri, localName, qName, atts);
+ }
+
+ /**
+ * <b>ContentHandler</b> Reports a validity error if the element's content
+ * model does not permit character data.
+ * Passed to the next consumer.
+ */
+ public void characters (char ch [], int start, int length)
+ throws SAXException
+ {
+ Recognizer state;
+
+ if (contentStack.empty ())
+ state = null;
+ else
+ state = (Recognizer) contentStack.peek ();
+
+ // NOTE: if this ever supports with SAX parsers that don't
+ // report ignorable whitespace as such (only XP?), this class
+ // needs to morph it into ignorableWhitespace() as needed ...
+
+ if (state != null && !state.acceptCharacters ())
+ // VC: Element Valid (clauses three, four -- see recognizer)
+ error ("Character content not allowed in element "
+ + state.type.name);
+
+ super.characters (ch, start, length);
+ }
+
+
+ /**
+ * <b>ContentHandler</b> Reports a validity error if the element's content
+ * model does not permit end-of-element yet, or a well formedness error
+ * if there was no matching startElement call.
+ * Passed to the next consumer.
+ */
+ public void endElement (String uri, String localName, String qName)
+ throws SAXException
+ {
+ try {
+ Recognizer state = (Recognizer) contentStack.pop ();
+
+ if (state != null && !state.completed ())
+ // VC: Element valid (clauses two, three, four; see Recognizer)
+ error ("Premature end for element '"
+ + state.type.name
+ + "', content model "
+ + state.type.model);
+
+ // could insist on match of start element, but that's
+ // something the input stream must to guarantee.
+
+ } catch (EmptyStackException e) {
+ fatalError ("endElement without startElement: " + qName
+ + ((uri == null)
+ ? ""
+ : ( " { '" + uri + "', " + localName + " }")));
+ }
+ super.endElement (uri, localName, qName);
+ }
+
+ /**
+ * <b>ContentHandler</b> Checks whether all ID values that were
+ * referenced have been declared, and releases all resources.
+ * Passed to the next consumer.
+ *
+ * @see #setDocumentLocator
+ */
+ public void endDocument ()
+ throws SAXException
+ {
+ for (Enumeration idNames = ids.keys ();
+ idNames.hasMoreElements ();
+ /* NOP */) {
+ String id = (String) idNames.nextElement ();
+
+ if (Boolean.FALSE == ids.get (id)) {
+ // VC: IDREF (must match ID)
+ error ("Undeclared ID value '" + id
+ + "' was referred to by an IDREF/IDREFS attribute");
+ }
+ }
+
+ resetState ();
+ super.endDocument ();
+ }
+
+
+ /** Holds per-element declarations */
+ static private final class ElementInfo
+ {
+ String name;
+ String model;
+
+ // key = attribute name; value = AttributeInfo
+ Hashtable attributes = new Hashtable (11);
+
+ ElementInfo (String n) { name = n; }
+
+ private Recognizer recognizer;
+
+ // for validating content models: one per type, shared,
+ // and constructed only on demand ... so unused elements do
+ // not need to consume resources.
+ Recognizer getRecognizer (ValidationConsumer consumer)
+ throws SAXException
+ {
+ if (recognizer == null) {
+ if ("ANY".equals (model))
+ recognizer = ANY;
+ else if ("EMPTY".equals (model))
+ recognizer = new EmptyRecognizer (this);
+ else if ('#' == model.charAt (1))
+ // n.b. this constructor does a validity check
+ recognizer = new MixedRecognizer (this, consumer);
+ else
+ recognizer = new ChildrenRecognizer (this, consumer);
+ }
+ return recognizer;
+ }
+ }
+
+ /** Holds per-attribute declarations */
+ static private final class AttributeInfo
+ {
+ String type;
+ String mode; // #REQUIRED, etc (or null)
+ String value; // or null
+ }
+
+
+ //
+ // Content model validation
+ //
+
+ static private final Recognizer ANY = new Recognizer (null);
+
+
+ // Base class defines the calls used to validate content,
+ // and supports the "ANY" content model
+ static private class Recognizer
+ {
+ final ElementInfo type;
+
+ Recognizer (ElementInfo t) { type = t; }
+
+ // return true iff character data is legal here
+ boolean acceptCharacters ()
+ throws SAXException
+ // VC: Element Valid (third and fourth clauses)
+ { return true; }
+
+ // null return = failure
+ // otherwise, next state (like an FSM)
+ // prerequisite: tested that name was declared
+ Recognizer acceptElement (String name)
+ throws SAXException
+ // VC: Element Valid (fourth clause)
+ { return this; }
+
+ // return true iff model is completed, can finish
+ boolean completed ()
+ throws SAXException
+ // VC: Element Valid (fourth clause)
+ { return true; }
+
+ public String toString ()
+ // n.b. "children" is the interesting case!
+ { return (type == null) ? "ANY" : type.model; }
+ }
+
+ // "EMPTY" content model -- no characters or elements
+ private static final class EmptyRecognizer extends Recognizer
+ {
+ public EmptyRecognizer (ElementInfo type)
+ { super (type); }
+
+ // VC: Element Valid (first clause)
+ boolean acceptCharacters ()
+ { return false; }
+
+ // VC: Element Valid (first clause)
+ Recognizer acceptElement (String name)
+ { return null; }
+ }
+
+ // "Mixed" content model -- ANY, but restricts elements
+ private static final class MixedRecognizer extends Recognizer
+ {
+ private String permitted [];
+
+ // N.B. constructor tests for duplicated element names (VC)
+ public MixedRecognizer (ElementInfo t, ValidationConsumer v)
+ throws SAXException
+ {
+ super (t);
+
+ // (#PCDATA...)* or (#PCDATA) ==> ... or empty
+ // with the "..." being "|elname|..."
+ StringTokenizer tokens = new StringTokenizer (
+ t.model.substring (8, t.model.lastIndexOf (')')),
+ "|");
+ Vector vec = new Vector ();
+
+ while (tokens.hasMoreTokens ()) {
+ String token = tokens.nextToken ();
+
+ if (vec.contains (token))
+ v.error ("element " + token
+ + " is repeated in mixed content model: "
+ + t.model);
+ else
+ vec.addElement (token.intern ());
+ }
+ permitted = new String [vec.size ()];
+ for (int i = 0; i < permitted.length; i++)
+ permitted [i] = (String) vec.elementAt (i);
+
+ // in one large machine-derived DTD sample, most of about
+ // 250 mixed content models were empty, and 25 had ten or
+ // more entries. 2 had over a hundred elements. Linear
+ // search isn't obviously wrong.
+ }
+
+ // VC: Element Valid (third clause)
+ Recognizer acceptElement (String name)
+ {
+ int length = permitted.length;
+
+ // first pass -- optimistic w.r.t. event source interning
+ // (and document validity)
+ for (int i = 0; i < length; i++)
+ if (permitted [i] == name)
+ return this;
+ // second pass -- pessimistic w.r.t. event source interning
+ for (int i = 0; i < length; i++)
+ if (permitted [i].equals (name))
+ return this;
+ return null;
+ }
+ }
+
+
+ // recognizer loop flags, see later
+ private static final int F_LOOPHEAD = 0x01;
+ private static final int F_LOOPNEXT = 0x02;
+
+ // for debugging -- used to label/count nodes in toString()
+ private static int nodeCount;
+
+ /**
+ * "Children" content model -- these are nodes in NDFA state graphs.
+ * They work in fixed space. Note that these graphs commonly have
+ * cycles, handling features such as zero-or-more and one-or-more.
+ *
+ * <p>It's readonly, so only one copy is ever needed. The content model
+ * stack may have any number of pointers into each graph, when a model
+ * happens to be needed more than once due to element nesting. Since
+ * traversing the graph just moves to another node, and never changes
+ * 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 (">");
+ }
+/**/
+ }
+}