Multi-Schema XML Validator (MSV)

Design & Native API

This document describes the design and how you can use the native API of MSV to drive it to the limit.

Contents

  1. Design Overview
  2. Loading Schemata
  3. Playing with AGM
  4. Controlling Parsing of Schemata
  5. Validating Documents
  6. Type Assignment

Design Overview

MSV comprises six components.

Component Description
Abstract grammar model (AGM) Schema-independent grammar model. All supported schemata are parsed into this internal representation. This model, coupled with the grammar reader, may be useful for other applications.
Grammar reader Component used to parse schemata by using SAX to construct AGMs.
Verification grammar model (VGM) Bridge between AGM and Validator. It works as an abstraction layer between them, thereby makeing non-automaton-based algorithms possible.
Validator Component to validate an XML instance with a VGM by using SAX.
Datatype validator Component separately available as the Sun XML Datatypes Library.
RELAX Namespace ("divide&validate" framework) Component that allows multiple schema languages to cooperatively validate one instance. The mplementation of this component is likely to change substantially in the future.

Loading Schemata

If you need finer control, then you may want to control MSV directly instead of using the generic JARV interface. This section and following sections will focus on the direct use of MSV.

The easiest way to load a grammar is to use the loadSchema method of com.sun.msv.reader.util.GrammarLoader.

Grammar loadGrammar( String schemaFileNameOrURL )
{
  SAXParserFactory factory = new javax.xml.parsers.SAXParserFactory();
  // or you can use different parser like Xerces-J by
  // new org.apache.xerces.parsers.jaxp.SAXParserFactoryImpl();

  factory.setNamespaceAware(true);

  return GrammarLoader.loadSchema(
                        schemaFileNameOrURL,
                        new com.sun.msv.reader.util.IgnoreController(),
                        factory );
}

GrammarLoader automatically detects the type of schema (RELAX Core/TREX/RELAX Namespace/RELAX NG/W3C) and handles it appropriately.

The second parameter specifies a controller object that receives notifications and controls the loading behavior. IgnoreController does nothing, but by providing a different object, you can control the parsing process.

The third parameter specifies SAXParserFactory to be used. Factory has to be configured as namespace-aware.

Alternatively, to load a specific language:

import com.sun.msv.grammar.Grammar;
import com.sun.msv.reader.trex.ng.RELAXNGReader;
import javax.xml.parsers.SAXParserFactory;

TREXGrammar loadRELAXNG( String schemaFileNameOrURL )
{
  SAXParserFactory factory = new javax.xml.parsers.SAXParserFactory();
  factory.setNamespaceAware(true);

  return RELAXNGReader.parse(
                        schemaFileNameOrURL,
                        factory,
                        new com.sun.msv.reader.util.IgnoreController() );
}

The parse method also accepts several other forms of arguments (e.g., InputSource). If loading fails, the parse method returns null.

Grammar readers implements ContentHandler, so you can also parse a grammar by the following way:

TREXGrammar loadRELAXNG( String schemaFileNameOrURL )
{
  RELAXNGReader reader = new RELAXNGReader( factory, new IgnoreController() );

  XMLReader xmlParser = new YourFavoriteXMLReader();

  xmlParser.setContentHandler(reader);
  xmlParser.parse(schemaFileNameOrURL);  // parse

  // this method returns null if loading fails.
  return reader.getResult();
}

In these ways, you can parse the XML representation of the specific language into MSV's AGM.

Since XML DTDs are not written in XML format, they have to be parsed differently. To parse an XML DTD, do as follows

Grammar loadDTD( String schemaFileNameOrURL )
{
  return DTDReader.parse(
    new InputSource(schemaFileNameOrURL),
    new com.sun.msv.reader.util.IgnoreController() );
}

The first parameter specifies the InputSource object from which the DTD is read. The second paramter controls the parsing behavior. Currently, MSV cannot parse an internal DTD subset.

Playing with AGM

The AGM is the internal representation of a schema used by MSV. It is a binarized regular expression commonly seen in many validating processors.

Schema Language Dependency

The AGM consists of two parts.

  1. Core: common part of various languages. e.g., ChoiceExp, SequenceExp, MixedExp, and more. Also contains several abstract classes (ReferenceExp and ElementExp).

  2. Language-specific stubs: concrete implementations of abstract classes and composite expressions of the specific language.

Several primitives in the core set (concur, list, and interleave) are not used by some languages. Those primitives are still placed in the core set, but the application may want to refuse to process such primitives. For example, AGMs from RELAX Core never contain ConcurExp or InterleaveExp. So an application that only processes RELAX Core can safely skip implementing concur related operations.

You should also note that the AGM is designed to handle differences between schema languages.

Generally speaking, you may want to avoid dependency on the stub parts. If your code only depends on the core part, then your code will work with AGMs created from any language. com.sun.msv.verifier.regexp is one of such code that works with any AGM.

InterleaveExp is used only by RELAX NG, TREX, and W3C XML Schema Part1. ConcurExp is used solely by TREX. Application may reject those primitives if your target schema language does not use them.

Expression and ExpressionPool

Expression and most of the derived classes are immutable, and they have to be created through ExpressionPool. Internally, every Expression is memorized by ExpressionPool so that sub expressions can be shared and reused.

Mixing two expressions created from two different pools is possible, but not recommended. If you are going to use MSV in a multithreaded environment, or you are going to use it in a daemon process, see "Multithreaded Environment" and "Daemon Process" respectively.

Creating AGM From Scratch

RELAXCoreReader/TREXGrammarReader/RELAXNSReader/XMLSchemaReader/DTDReader is just one way to create an AGM. Alternatively, you can create it from scratch.

import com.sun.msv.grammar.trex.*;
import com.sun.msv.grammar.*;

TREXGrammar create()
{
  ExpressionPool pool = new ExpressionPool();
  TREXGrammar g = new TREXGrammar(pool); // create an empty grammar

  g.start = new ElementPattern(
    // name class that constrains tag name
    new SimpleNameClass("http://namespace.uri/","tagname"),
    // content model
      pool.createMixed(
        pool.createSequence(
          new ElementPattern(
            new SimpleNameClass("http://namespace.uri/","tagname2"),
            pool.createEpsilon() // empty
          ),
          pool.createAttribute(
            new SimpleNameClass("","attr"),
            pool.createAnyString()
          )
        )
      )
    );
  // ElementPatterns are created outside ExpressionPool

  return g;
}

The AGM created by the above example is equivalent to the following TREX grammar.

<element name="tagname" ns="http://namespace.uri/">
  <mixed>
    <group>
      <element name="tagname2">
        <empty />
      </element>
      <attribute name="attr" />
    </group>
  </mixed>
</element>

As you see, you have to use the ExpressionPool to create a tree of Expression. All the primitive operators are immutable.

Also, all associative operators like choice and sequence are binary (they can only have two operands): to create an expression of (A|B|C), create (A|(B|C)) or ((A|B)|C). For more, see the JavaDoc for ExpressionPool.

A named expression can be created as follows:

{
  ExpressionPool pool = new ExpressionPool();
  TREXGrammar g = new TREXGrammar(pool); // create an empty grammar

  g.start = pool.createZeroOrMore( g.namedPatterns.getOrCreate("label") );

  g.namedPatterns.getOrCreate("label").exp =
      pool.createChoice( ... ); // whatever expression you like
}

You can refer to the named expression before the actual definition is provided. It is the responsibility of the application to ensure that every named expression has a definition. The grammar created by this example is equivalent to the following TREX pattern:

<xmp>
<grammar>
  <start>
    <zeroormore>
      <ref name="label" />
    </zeroormore>
  </start>
  <define name="label">
    <choice>
      ...
    </choice>
  </define>
</grammar>
</xmp>

To create a RELAX AGM, use RELAXGrammar and RELAXModule as a starting point.

Accessing AGM

One feature that you may find useful is the "visitor" design pattern support. You can write your own visitor by implementing ExpressionVisitor. See the JavaDoc for ExpressionVisitor for details.

Usually, this is the easiest way to access AGMs

Manipulating AGM

Due to the immutability of the AGM, you cannot "modify" an AGM. Instead, you create a modified AGM. To do this, use ExpressionCloner. The following example creates a new AGM that changes ChoiceExp to SequenceExp and SequenceExp to ChoiceExp. 

class SwitchChoiceAndSequence extends com.sun.msv.grammar.ExpressionCloner {

  private ExpressionPool pool;

  public Expression onSequence( SequenceExp exp ) {
    return pool.createChoice( exp.exp1, exp.exp2 );
  }
  public Expression onChoice( ChoiceExp exp ) {
    return pool.createSequence( exp.exp1, exp.exp2 );
  }
}

// usage
Expression modifiedExp = originalExp.visit( new SwitchChoiceAndSequence() );

See javadoc of ExpressionCloner for details.

Controlling Parsing of Schemata

Any application can use GrammarReaderController to control how a grammar is parsed. For example, it can:

See GrammarReaderController and IgnoreController for details.

Validating Documents

Validation Grammar Model (VGM)

To validate documents with a AGM, you have to "wrap" it in a VGM. The VGM can be understood as an abstraction of an AGM for the validator.

The VGM is a simple model which consists of two interfaces only: Acceptor and DocumentDeclaration. Any VGM implementation can be used as long as it implements them.

Currently, only one VGM implementation is available, which is placed under the com.sun.msv.verifier.regexp package.

The following example creates a RegExp VGM from a Grammar object. Grammar is an interface implemented by RELAXGrammar, RELAXModule, TREXGrammar, and XMLSchemaGrammar.

import com.sun.msv.verifier.regexp.REDocumentDeclaration;
import com.sun.msv.grammar.Grammar;

DocumentDeclaration createVGM( Grammar g ) {
  return new REDocumentDeclaration(g);
}

Alternatively, you can pass an arbitrary expression as the first parameter and a newly created pool as the second parameter.

DocumentDeclaration createVGM( Expression exp ) {
  return new REDocumentDeclaration( exp, new ExpressionPool() );
}

Then VGM can be passed to the constructor of Verifier class to actually perform a validation.

Multithreaded Environment

AGMs are thread-safe because they are immutable. A thread can safely use an AGM parsed by a different thread; or two threads can safely share the same AGM. ExpressionPool is also thread-safe. Multiple threads can share the same pool, which is created by another thread.

VGM, on the other hand, is not thread-safe. Each thread has to create its own VGM and use its own. You should never share a VGM between threads. Verifier is another thread-unsafe component. Also, it's not reentrant, so you can only use one object to validate one document at a time.

When a new expression is found, it is stored to the pool. To do this, a thread has to acquire a lock. And the pool is very frequently called during validation. So you might think that sharing a pool might cause a performance bottleneck.

However, a casual experiment shows that this is not always the case. Yes, a thread has to acquire a lock to modify the pool, but this update can be done concurrently while other threads read the pool. And update is far less frequent than retrieval. So please benchmark by yourself if you need to achieve the optimal performance.

Daemon Process

Generally, it's a good practice to keep re-using the same ExpressionPool. Using the same pool makes it bigger, and a bigger pool contains more expressions, which in turn results in faster validation.

If you keep using the same ExpressionPool, it gradually expands. Its expansion is like a square-root function. It grows rapidly at first, but its growth becomes slower and slower as time goes by.

Its size will eventually reach a certain limit, and the growth stops there. If your schema is DTD, RELAX, TREX without <interleave>, or W3C XML Schema without <all>, then this size limit is mostly moderate, so you can keep using the same pool forever.

However, if a grammar is TREX with <interleave> patterns, or W3C XML Schema with <all>s, then the upper bound of a pool could be exponential to the size of the grammar (especially if interleave/all contains large patterns). If this is the case, and your application runs 24/7 as a daemon process, then you should occasionally throw away the pool to prevent its size from expanding indefinitely.

Note that pool expansion is slow; the size of a pool is proportional to the number of validated documents even in the worst case. So usually it takes quite a long time to make a pool explode.

To throw away ExpressionPool, simply create a new VGM with a brand-new pool, like this.

DocumentDeclaration vgm = new REDocumentDeclaration( grammar.getTopLevel(), new ExpressionPool() );

Type Assignment

MSV can report the element declaration which is applied to the current element, and what datatype is applied to text. This information is useful for deciding what to do with the reported element.

To retrieve these information, call the getCurrentElementType method of the Verifier class. This method returns the correct value only when called immediately after it processed the startElement method. If you are using com.sun.msv.verifier.VerifierFilter, then you can call this method only in your handler's startElement method.

The following code illustrates how to retrieve RELAX "label" from your own ContentHandler.

void startElement( .... )
{// SAX startElement event

  ElementRule er = (ElementRule)currentVerifier.getCurrentElementType();
  if( er==null )
    // this may happen when the schema is complex.
    // MSV is unable to determine label/role at this moment.
  else
  {
    // er holds a reference to ElementRule object which is applied to this element.

    if(er.getParent()==null )
      // this element is declared by inline <element> declaration.
      // so it doesn't have any role/label
    else
    {
      final String label = er.getParent().name; // obtain label name
      final String role = er.clause.name; // obtain role name

      ....
    }
  }

  ...
}

TREX extension

TREX doesn't have a mechanism to name the <element> pattern. Therefore, MSV introduces a proprietary extension to TREX that provides this naming mechanism.

Annotation is done by adding a "label" attribute to the <element> pattern. The "label" attribute has to be in the "http://www.sun.com/xml/msv/trex-type" namespace. These attributes will be ignored by other TREX validating processors.

<xmp>
<grammar xmlns:ext="http://www.sun.com/xml/msv/trex-type">
  <start>
    <element ext:label="rootLabel" name="root">
      ...
      <element name="child"> <!-- label attribute is optional -->
        ...
      </element>
    </element>
  </start>
</grammar>
</xmp>

The following example illustrates how to load an annotated TREX pattern.

TREXGrammarReader reader = new TREXGrammarReader(
    myGrammarReaderControllerObject,
    saxParserFactory,
    new com.sun.msv.reader.trex.typed.TypedTREXGrammarInterceptor(),
    new ExpressionPool() );
((XMLReader)reader).parse(schemaFileName);

// obtain parsed grammar object. it returns null in case of error
TREXGrammar grammar = reader.getResult();

The following example shows how to access TREX "label" information from your ContentHandler.

import com.sun.msv.grammar.trex.typed.TypedElementPattern;

void startElement( .... )
{// SAX startElement event

  Object o = currentVerifier.getCurrentElementType();
  if( o==null )
    // this may happen when the schema is complex.
    // MSV is unable to determine label/role at this moment.
  else
  if( o instanceod TypedElementPattern )
  {
    // the current element declaration has label attribute.

    final String label = ((TypedElementPattern)o).label;

    ....
  }
  else
    // the current element declaration has no label attribute.

  ...
}