home *** CD-ROM | disk | FTP | other *** search
/ Dynamic HTML in Action / Dynamicke-HTML-v-akci-covermount.bin / XML / PARSER / XMLINST.EXE / classes / com / ms / xml / parser / ContentModel.java < prev    next >
Encoding:
Java Source  |  1998-05-26  |  31.3 KB  |  1,157 lines
  1. /*
  2.  * @(#)ContentModel.java 1.0 6/3/97
  3.  * 
  4.  * Copyright (c) 1997 Microsoft, Corp. All Rights Reserved.
  5.  * 
  6.  */
  7.  
  8. package com.ms.xml.parser;
  9.  
  10. import com.ms.xml.om.Element;
  11. import com.ms.xml.om.ElementImpl;
  12. import com.ms.xml.util.Name;
  13. import com.ms.xml.util.Atom;
  14. import com.ms.xml.util.XMLOutputStream;
  15. import com.ms.xml.parser.ElementDecl;
  16. import com.ms.xml.parser.Entity;
  17.  
  18. import java.lang.String;
  19. import java.util.Vector;
  20. import java.util.BitSet;
  21. import java.util.Hashtable;
  22. import java.util.Enumeration;
  23. import java.io.IOException;
  24.  
  25. /**
  26.  * This class represents the content model definition for a given
  27.  * XML element. The content model is defined in the element
  28.  * declaration in the Document Type Definition (DTD); for example, 
  29.  * (a,(b|c)*,d). The
  30.  * content model is stored in an expression tree of <code>Node</code> objects
  31.  * for use by the XML parser during validation.
  32.  * 
  33.  */
  34. public class ContentModel
  35. {
  36.     /**
  37.      * content model
  38.      * points to syntax tree 
  39.      * @see Node
  40.      */    
  41.     Node content;
  42.  
  43.     /**
  44.      * end node
  45.      */
  46.     Terminal end;
  47.  
  48.     /** 
  49.      * terminal nodes
  50.      */
  51.     Vector terminalnodes;
  52.  
  53.     /**
  54.      * unique terminal names
  55.      */
  56.     Hashtable symboltable;
  57.  
  58.     /**
  59.      * symbol array
  60.     */
  61.     Vector symbols;
  62.  
  63.     /**
  64.      * transition table
  65.      */
  66.     Vector Dtrans;
  67.  
  68.     /**
  69.      * content type
  70.      */    
  71.     public static final byte EMPTY       = 1;
  72.     public static final byte ANY         = 2;
  73.     public static final byte ELEMENTS    = 4;
  74.     byte type;
  75.  
  76.     public byte getType()
  77.     {
  78.         return type;
  79.     }
  80.  
  81.     /**
  82.      * Retrieves a string representation of the content type.
  83.      * @return a <A>String</A>. 
  84.      */    
  85.     public String toString()
  86.     {
  87.         String s;
  88.         switch(type)
  89.         {
  90.             case EMPTY:
  91.                 s = "EMPTY";
  92.                 break;
  93.             case ANY:
  94.                 s = "ANY";
  95.                 break;
  96.             case ELEMENTS:
  97.                 s = "ELEMENTS";
  98.                 break;
  99.             default:
  100.                 s = "*UNKNOWN*";
  101.         }
  102.         return "Content: type=" + s;
  103.     }
  104.     
  105.     /**
  106.      *  parse content model in an element declaration, and build up the state
  107.      *  transation table for element content checking
  108.      */
  109.     final void parseModel(Parser parser) throws ParseException
  110.     {
  111.         terminalnodes = new Vector();
  112.         symboltable = new Hashtable();
  113.         symbols = new Vector();
  114.         // create parse tree for content expression
  115.         content = parseRootNode(parser);
  116.         // add end node
  117.         end = new Terminal(this, null);
  118.         content = new Sequence(content, end);
  119.  
  120.         // calculate followpos for terminal nodes
  121.         int terminals = terminalnodes.size();
  122.         BitSet[] followpos = new BitSet[terminals];
  123.         for (int i = 0; i < terminals; i++)
  124.         {
  125.             followpos[i] = new BitSet(terminals);
  126.         }
  127.         content.calcfollowpos(followpos);
  128.  
  129.         // state table
  130.         Vector Dstates = new Vector();
  131.         // transition table
  132.         Dtrans = new Vector();
  133.         // lists unmarked states
  134.         Vector unmarked = new Vector();
  135.         // state lookup table
  136.         Hashtable statetable = new Hashtable();
  137.  
  138.         BitSet empty = new BitSet(terminals);
  139.         statetable.put(empty, new Integer(-1));
  140.     
  141.         // current state processed
  142.         int state = 0;                
  143.  
  144.         // start with firstpos at the root                
  145.         BitSet set = content.firstpos(terminals);
  146.         statetable.put(set, new Integer(Dstates.size()));
  147.         unmarked.addElement(set);
  148.         Dstates.addElement(set);
  149.         int[] a = new int[symbols.size() + 1];
  150.         Dtrans.addElement(a);
  151.         if (set.get(end.pos))
  152.         {
  153.             a[symbols.size()] = 1;   // accepting
  154.         }
  155.  
  156.         // check all unmarked states
  157.         while (unmarked.size() > 0)
  158.         {
  159.             int[] t = (int[])Dtrans.elementAt(state);
  160.         
  161.             set = (BitSet)unmarked.elementAt(0);
  162.             unmarked.removeElementAt(0);
  163.  
  164.             // check all input symbols
  165.             for (int sym = 0; sym < symbols.size(); sym++)
  166.             {
  167.                 Name n = (Name)symbols.elementAt(sym);
  168.  
  169.                 BitSet newset = new BitSet(terminals);
  170.                 // if symbol is in the set add followpos to new set
  171.                 for (int i = 0; i < terminals; i++)
  172.                 {
  173.                     if (set.get(i) && ((Terminal)terminalnodes.elementAt(i)).name == n)
  174.                     {
  175.                         newset.or(followpos[i]);
  176.                     }
  177.                 }
  178.  
  179.                 Integer lookup = (Integer)statetable.get(newset);                        
  180.                 // this state will transition to
  181.                 int transitionTo;
  182.                 // if new set is not in states add it                        
  183.                 if (lookup == null)
  184.                 {
  185.                     transitionTo = Dstates.size();            
  186.                     statetable.put(newset, new Integer(transitionTo));
  187.                     unmarked.addElement(newset);
  188.                     Dstates.addElement(newset);
  189.                     a = new int[symbols.size() + 1];
  190.                     Dtrans.addElement(a);
  191.                     if (newset.get(end.pos))
  192.                     {
  193.                         a[symbols.size()] = 1;   // accepting
  194.                     }
  195.                 }
  196.                 else
  197.                 {
  198.                     transitionTo = lookup.intValue();                            
  199.                 }
  200.                 // set the transition for the symbol
  201.                 t[sym] = transitionTo;
  202.             }
  203.             state++;
  204.         }
  205.     }
  206.  
  207.     /**
  208.      *  parse a list of content nodes
  209.      */
  210.     final Node parseList(Parser parser) throws ParseException
  211.     {
  212.         //use Hashtable to check name uniqueness  
  213.         Hashtable symbols = new Hashtable(); 
  214.         symbols.put(parser.name, parser.name);
  215.  
  216.         Node n = parseNode(parser);
  217.         int cpType = parser.token;
  218.  
  219.         switch (parser.token)
  220.         {
  221.             case Parser.COMMA:
  222.                 parser.nextToken();
  223.                 n = new Sequence(n, parseNode(parser));
  224.                 break;
  225.             case Parser.OR:
  226.                 parser.nextToken();
  227.                 if (parser.token == parser.NAME) {
  228.                     if (symbols.contains(parser.name)) 
  229.                         parser.error("Warning: Repeated element in content model: " + parser.name );
  230.                     else symbols.put(parser.name, parser.name);
  231.                 }
  232.                 n = new Choice(n, parseNode(parser));
  233.                 break;
  234.             case Parser.RPAREN:
  235.                 return n;
  236.             default:
  237.                 parser.error("Illegal token in content model: " + parser.tokenString(parser.token));
  238.         }
  239.  
  240.         for (;;)
  241.         {
  242.             if (parser.token == Parser.RPAREN)
  243.                 return n;
  244.             else if (cpType == Parser.COMMA && parser.token == Parser.COMMA)
  245.             {
  246.                 parser.nextToken();
  247.                 n = new Sequence(n, parseNode(parser));
  248.             }
  249.             else if (cpType == Parser.OR && parser.token == Parser.OR)
  250.             {
  251.                 parser.nextToken();
  252.                 if (parser.token == parser.NAME) {
  253.                     if (symbols.contains(parser.name)) 
  254.                         parser.error("Repeated element in content model: " + parser.name );
  255.                     else symbols.put(parser.name, parser.name);
  256.                 }
  257.                 n = new Choice(n, parseNode(parser));
  258.             }
  259.             else parser.error("Illegal token in content model: " + parser.tokenString(parser.token));
  260.         }
  261.     }
  262.  
  263.     /**
  264.      *  parse a node in an element content model declaration 
  265.      */
  266.     final Node parseNode(Parser parser) throws ParseException
  267.     {
  268.         Node n;
  269.  
  270.         switch (parser.token)
  271.         {
  272.             case Parser.LPAREN:
  273.                 parser.nextToken();
  274.                 n = parseList(parser);
  275.                 break;
  276.             case Parser.NAME:
  277.                 n = new Terminal(this, parser.name);
  278.                 break;
  279.             default:
  280.                 n = null;
  281.                 parser.error("Illegal token in content model: " + parser.tokenString(parser.token));
  282.         }
  283.         return finishNode(parser, n);
  284.     }
  285.  
  286.     final Node finishNode(Parser parser, Node m) throws ParseException
  287.     {
  288.         Node n;
  289.  
  290.         switch (parser.lookahead) 
  291.         {
  292.             case Parser.ASTERISK:
  293.                 parser.nextToken();
  294.                 n = new Closure(m);
  295.                 break;
  296.             case Parser.PLUS:
  297.                 parser.nextToken();
  298.                 n = new ClosurePlus(m);
  299.                 break;
  300.             case Parser.QMARK:
  301.                 parser.nextToken();
  302.                 n = new Qmark(m);
  303.                 break;
  304.             default:
  305.                 n = m;
  306.         }
  307.         parser.nextToken();
  308.         return n;
  309.     }
  310.  
  311.     /**
  312.      *  parse the root node in an element content model declaration
  313.      */
  314.     final Node parseRootNode(Parser parser) throws ParseException
  315.     {
  316.         Node n;
  317.  
  318.         switch (parser.token)
  319.         {
  320.             case Parser.LPAREN:
  321.                 parser.nextToken();
  322.                 if (parser.token == Parser.HASH) 
  323.                     return parseMixed(parser); 
  324.                 else n = parseList(parser);
  325.                 break;
  326.             case Parser.NAME:
  327.                 n = new Terminal(this, parser.name);
  328.                 break;
  329.             default:
  330.                 n = null;
  331.                 parser.error("Expected ANY, EMPTY or '(' instead of: " + parser.tokenString(parser.token));
  332.         }
  333.         return finishNode(parser, n);
  334.     }
  335.  
  336.     /**
  337.      *  parser mixed element content model 
  338.      */
  339.     final Node parseMixed(Parser parser) throws ParseException
  340.     {
  341.         Node n;
  342.         Hashtable symbols= new Hashtable();
  343.         parser.parseKeyword(Parser.PCDATA, "PCDATA");
  344.         n = new Terminal(this, parser.name);
  345.         symbols.put(parser.name, parser.name);
  346.         parser.nextToken();
  347.         switch (parser.token)
  348.         {
  349.             case Parser.RPAREN:
  350.                 // create a closure even if there is no asterisk.
  351.                 n = new Closure(n);
  352.                 if (parser.lookahead == Parser.ASTERISK)
  353.                 {
  354.                     parser.nextToken();
  355.                 }
  356.                 break;
  357.             case Parser.OR:             
  358.                 for (;;)
  359.                 {
  360.                     if (parser.token == Parser.OR)
  361.                     {
  362.                         parser.nextToken();
  363.                         if (parser.token == parser.NAME) {
  364.                             if (symbols.contains(parser.name)) 
  365.                                 parser.error("Repeated element in content model: " + parser.name);
  366.                             else symbols.put(parser.name, parser.name);
  367.                         }
  368.                         n = new Choice(n, parseNode(parser));
  369.                     }
  370.                     else if (parser.token == Parser.RPAREN) {
  371.                         if (parser.lookahead == Parser.ASTERISK)
  372.                         {
  373.                             parser.nextToken();
  374.                             n = new Closure(n);
  375.                         }
  376.                         else parser.error("Expected '*' instead of: " + parser.tokenString(parser.token));
  377.                         break;
  378.                     }
  379.                     else {
  380.                         parser.error("Illegal token in content model: " + parser.tokenString(parser.token));
  381.                         break;
  382.                     }
  383.                 }
  384.                 break;
  385.             default:
  386.                 parser.error("Illegal token in content model: " + parser.tokenString(parser.token));
  387.         }
  388.         parser.nextToken();
  389.         return n;
  390.     }
  391.  
  392.     /**
  393.      *  set inital state for context
  394.      */
  395.     final void initContent(Context context, Parser parser) throws ParseException
  396.     {
  397.         context.state = 0;
  398.         if (Dtrans != null && Dtrans.size() > 0)
  399.         {
  400.             context.matched = ((int[])Dtrans.elementAt(context.state))[symbols.size()] > 0;
  401.         }
  402.         else
  403.         {
  404.             context.matched = true;
  405.         }
  406.     }
  407.  
  408.     /**
  409.      * check whether the content model allows empty content
  410.      */
  411.     final boolean acceptEmpty(Context context)
  412.     {
  413.         if (type == ANY || type == EMPTY)
  414.             return true;
  415.  
  416.         return (((int[])Dtrans.elementAt(context.state))[symbols.size()] > 0);
  417.     }
  418.  
  419.  
  420.     /**
  421.      *  returns names of all legal elements following the specified state
  422.      */
  423.     final Vector expectedElements(int state)
  424.     {
  425.         int[] t = (int[])Dtrans.elementAt(state);
  426.         Vector names = new Vector();
  427.  
  428.         for (Enumeration e = terminalnodes.elements(); e.hasMoreElements();)
  429.         {
  430.             Name n = ((Terminal)e.nextElement()).name;
  431.             if (n != null && !names.contains(n))
  432.             {
  433.                 Integer lookup = (Integer)symboltable.get(n);
  434.                 if (lookup != null && t[lookup.intValue()] != -1)
  435.                 {
  436.                     names.addElement(n);
  437.                 }
  438.             }
  439.         }
  440.        
  441.         return names;
  442.     }
  443.  
  444.  
  445.     /**
  446.      * check whether the specified element matches current context, and if matched, change
  447.      * the context state
  448.      */
  449.     final boolean checkContent(Context context, Element e, Parser parser) throws ParseException
  450.     {
  451.         if (type == ANY)
  452.         {
  453.             context.matched = true;
  454.             return true;
  455.         }
  456.         Name n = null;
  457.         if (e.getType() == Element.ENTITYREF)
  458.         {
  459.             Entity en = parser.dtd.findEntity(e.getTagName());
  460.             if (en.getLength() == -1)
  461.                 n = Parser.namePCDATA; // this entity is PCDATA
  462.             else
  463.                 return true; // have to wait until entity itself is parsed.
  464.         }
  465.         else if (e.getType() == Element.PCDATA)
  466.         {
  467.             n = Parser.namePCDATA;
  468.         } else {
  469.             n = e.getTagName();
  470.         }
  471.  
  472.         if (n != null)
  473.         {
  474.             Integer lookup = (Integer)symboltable.get(n);
  475.             if (lookup != null)
  476.             {
  477.                 int sym = lookup.intValue();
  478.                 int state = ((int[])Dtrans.elementAt(context.state))[sym];
  479.                 if (state == -1)
  480.                 {
  481.                     parser.error("Pattern mismatch in content of '" + e.getParent().getTagName() + "'. Expected " + expectedElements(context.state));
  482.                 }
  483.                 else
  484.                 {
  485.                     context.state = state;
  486.                     context.matched = ((int[])Dtrans.elementAt(context.state))[symbols.size()] > 0;
  487.                 }
  488.                 return true;
  489.             }
  490.             else
  491.             {
  492.                 Vector v = expectedElements(context.state);
  493.                 if (v.isEmpty())
  494.                     parser.error("Invalid element '" + n + "' in content of '" + context.ed.name + "'.  Expected closing tag.");
  495.                 else
  496.                     parser.error("Invalid element '" + n + "' in content of '" + context.ed.name + "'.  Expected " + v);
  497.             }
  498.         }
  499.         else
  500.         {
  501.             parser.error("Invalid element in content of '" + context.ed.name + "'");
  502.         }
  503.         return false;
  504.     }
  505.  
  506.     public Element toSchema()
  507.     {
  508.         Element elementContent = null;
  509.  
  510.         switch (type)
  511.         {
  512.             case EMPTY:
  513.                 elementContent = new ElementImpl( nameEMPTY, Element.ELEMENT ); 
  514.                 break;
  515.             case ANY:
  516.                 elementContent = new ElementImpl( nameANY, Element.ELEMENT );
  517.                 break;
  518.             case ELEMENTS:
  519.                 if (content != null) 
  520.                 {                    
  521.                     Element dummyNode = new ElementImpl( Name.create("DUMMYNODE"), Element.ELEMENT );
  522.                     ((Sequence)content).left.toSchema(Parser.HASH, 0, dummyNode); 
  523.                     elementContent = dummyNode.getChild(0);
  524.                 }
  525.                 break;
  526.         }
  527.  
  528.         return elementContent;
  529.     }
  530.  
  531.     static Name nameEMPTY = Name.create("EMPTY","XML");
  532.     static Name nameANY = Name.create("ANY","XML");
  533.  
  534.     public void save(Atom ns, XMLOutputStream o) throws IOException
  535.     {
  536.         switch (type)
  537.         {
  538.             case EMPTY:
  539.                 o.writeChars("EMPTY");
  540.                 break;
  541.             case ANY:
  542.                 o.writeChars("ANY");
  543.                 break;
  544.             case ELEMENTS:
  545.                 if (content != null) 
  546.                     ((Sequence)content).left.save(o, Parser.HASH, 0, ns); // skip outer sequence node
  547.                 break;
  548.         }
  549.     }
  550. }
  551.     
  552. /**
  553.  * This is the node object on the syntax tree describing element 
  554.  * content model
  555.  */
  556. class Node
  557. {
  558.     /**
  559.      * firstpos
  560.      */    
  561.     BitSet first;
  562.     
  563.     /**
  564.      * lastpos
  565.      */    
  566.     BitSet last;
  567.  
  568.     boolean nullable() 
  569.     {
  570.         return true;
  571.     }
  572.     
  573.     Node clone(ContentModel cm)
  574.     {
  575.         return new Node();
  576.     }
  577.  
  578.     BitSet firstpos(int positions)
  579.     {
  580.         if (empty == null)
  581.         {
  582.             empty = new BitSet(positions);
  583.         }
  584.         return empty;
  585.     }
  586.     
  587.     BitSet lastpos(int positions)
  588.     {
  589.         return firstpos(positions);
  590.     }
  591.     
  592.     void calcfollowpos(BitSet[] followpos)
  593.     {
  594.     }
  595.  
  596.     Element toSchema(int parentType, int level, Element currElement)
  597.     {      
  598.         return null;
  599.     }
  600.  
  601.     void save(XMLOutputStream o, int parentType, int level, Atom ns) throws IOException
  602.     {
  603.     }
  604.     
  605.     static BitSet empty;
  606.  
  607.     static Name namePCDATA = Name.create("PCDATA");
  608. }    
  609.  
  610. class Terminal extends Node
  611. {
  612.     /**
  613.      * numbering the node
  614.      */
  615.     int pos;
  616.     
  617.     /**
  618.      * name it refers to
  619.      */    
  620.     Name name;
  621.  
  622.     
  623.     Terminal(ContentModel cm, Name name)
  624.     {
  625.         this.name = name;
  626.         this.pos = cm.terminalnodes.size();
  627.         
  628.         cm.terminalnodes.addElement(this);
  629.         if (name != null && cm.symboltable.get(name) == null)
  630.         {
  631.             cm.symboltable.put(name, new Integer(cm.symbols.size()));
  632.             cm.symbols.addElement(name);
  633.         }
  634.     }
  635.     
  636.     Node clone(ContentModel cm)
  637.     {
  638.         return new Terminal(cm, name);
  639.     }
  640.  
  641.     boolean nullable() 
  642.     {
  643.         if (name == null)
  644.             return true;
  645.         else return false;
  646.     }
  647.     
  648.     BitSet firstpos(int positions)
  649.     {
  650.         if (first == null)
  651.         {
  652.             first = new BitSet(positions);
  653.             first.set(pos);
  654.         }
  655.  
  656.         return first;
  657.     }
  658.     
  659.     BitSet lastpos(int positions)
  660.     {
  661.         if (last == null)
  662.         {
  663.             last = new BitSet(positions);
  664.             last.set(pos);
  665.         }
  666.  
  667.         return last;
  668.     }
  669.     
  670.     void calcfollowpos(BitSet[] followpos)
  671.     {
  672.     }
  673.  
  674.     Element toSchema(int parentType, int level, Element currElement)
  675.     {
  676.         if (name.getName() == namePCDATA.getName()) 
  677.         {
  678.             if (level == 0 || level == 1 && parentType == Parser.ASTERISK)
  679.             {
  680.                 currElement.addChild(new ElementImpl(Name.create("PCDATA","XML"), Element.ELEMENT), null);
  681.                 return currElement;
  682.             }
  683.             else 
  684.             {
  685.                 Element mixedElement = new ElementImpl( Name.create("MIXED","XML"), Element.ELEMENT );
  686.                 currElement.addChild(mixedElement, null);
  687.                 return mixedElement;
  688.             }
  689.         }
  690.         else 
  691.         {   
  692.             Element eltElement = new ElementImpl( Name.create("ELT","XML"), Element.ELEMENT );
  693.  
  694.             eltElement.setAttribute(Name.create("HREF","XML"), "#" + name);
  695.  
  696.             if (parentType == Parser.QMARK)
  697.                 eltElement.setAttribute(Name.create("OCCURS","XML"), "OPTIONAL");
  698.             else if (parentType == Parser.ASTERISK)
  699.                 eltElement.setAttribute(Name.create("OCCURS","XML"), "STAR");
  700.             else if (parentType == Parser.PLUS)
  701.                 eltElement.setAttribute(Name.create("OCCURS","XML"), "PLUS");
  702.  
  703.             currElement.addChild(eltElement, null);
  704.             return currElement;
  705.         }
  706.     }
  707.  
  708.     void save(XMLOutputStream o, int parentType, int level, Atom ns) throws IOException
  709.     {
  710.         if (name.getName() == namePCDATA.getName()) 
  711.         {
  712.             if (level == 0 || level == 1 && parentType == Parser.ASTERISK)
  713.                 o.writeChars("(#PCDATA)");
  714.             else o.writeChars("#PCDATA");
  715.         }
  716.         else 
  717.         {
  718.             if (parentType == Parser.HASH || level == 1 && (parentType == Parser.QMARK || parentType == Parser.ASTERISK)) {
  719.                 o.writeChars("(");
  720.                 o.writeQualifiedName(name, ns);
  721.                 o.writeChars(")");
  722.             }
  723.             else o.writeQualifiedName(name, ns);
  724.         }
  725.     }
  726.  
  727. }
  728.  
  729. class Sequence extends Node
  730. {
  731.     /**
  732.      * left node
  733.      */    
  734.     Node left;
  735.     
  736.     /**
  737.      * right node
  738.      */    
  739.     Node right;
  740.     
  741.     Sequence(Node left, Node right)
  742.     {
  743.         this.left = left;
  744.         this.right = right;
  745.     }
  746.     
  747.     Node clone(ContentModel cm)
  748.     {
  749.         return new Sequence(left.clone(cm), right.clone(cm));
  750.     }
  751.  
  752.     boolean nullable() 
  753.     {
  754.         return left.nullable() && right.nullable();
  755.     }
  756.     
  757.     BitSet firstpos(int positions)
  758.     {
  759.         if (first == null)
  760.         {
  761.             if (left.nullable())
  762.             {
  763.                 first = (BitSet)left.firstpos(positions).clone();
  764.                 first.or(right.firstpos(positions));
  765.             }
  766.             else
  767.             {
  768.                 first = left.firstpos(positions);
  769.             }
  770.         }
  771.  
  772.         return first;
  773.     }
  774.     
  775.     BitSet lastpos(int positions)
  776.     {
  777.         if (last == null)
  778.         {
  779.             if (right.nullable())
  780.             {
  781.                 last = (BitSet)left.lastpos(positions).clone();
  782.                 last.or(right.lastpos(positions));
  783.             }
  784.             else
  785.             {
  786.                 last = right.lastpos(positions);
  787.             }
  788.         }
  789.  
  790.         return last;
  791.     }
  792.     
  793.     void calcfollowpos(BitSet[] followpos)
  794.     {
  795.         left.calcfollowpos(followpos);
  796.         right.calcfollowpos(followpos);
  797.         
  798.         int l = followpos.length;        
  799.         BitSet lp = left.lastpos(l);
  800.         BitSet fp = right.firstpos(l);        
  801.         for (int i = followpos.length - 1; i >= 0; i--)
  802.         {
  803.             if (lp.get(i))
  804.             {
  805.                 followpos[i].or(fp);
  806.             }
  807.         }
  808.     }
  809.  
  810.     Element toSchema( int parentType, int level, Element currElement)
  811.     {
  812.         Element tempCurr;
  813.         Element seqElement;       
  814.  
  815.         level++;
  816.         if (parentType == Parser.COMMA) {
  817.             currElement = left.toSchema(Parser.COMMA, level, currElement);
  818.             right.toSchema(Parser.COMMA, level, currElement);            
  819.         }
  820.         else {
  821.             seqElement = new ElementImpl( Name.create("GROUP","XML"), Element.ELEMENT );        
  822.             seqElement.setAttribute(Name.create("GROUPTYPE","XML"), "SEQ");
  823.             
  824.             if (parentType == Parser.QMARK)
  825.                 seqElement.setAttribute(Name.create("OCCURS","XML"), "OPTIONAL");
  826.             else if (parentType == Parser.ASTERISK)
  827.                 seqElement.setAttribute(Name.create("OCCURS","XML"), "STAR");
  828.             else if (parentType == Parser.PLUS)
  829.                 seqElement.setAttribute(Name.create("OCCURS","XML"), "PLUS");
  830.             
  831.             seqElement = left.toSchema(Parser.COMMA, level, seqElement);
  832.             right.toSchema(Parser.COMMA, level, seqElement);
  833.  
  834.             currElement.addChild(seqElement, null);
  835.         }     
  836.         level--;
  837.  
  838.         return currElement;
  839.     }
  840.  
  841.     void save(XMLOutputStream o, int parentType, int level, Atom ns) throws IOException
  842.     {
  843.         level++;
  844.         if (parentType == Parser.COMMA) {
  845.             left.save(o, Parser.COMMA, level, ns);
  846.             o.write(',');
  847.             right.save(o, Parser.COMMA, level, ns);
  848.         }
  849.         else {
  850.             o.write('(');
  851.             left.save(o, Parser.COMMA, level, ns);
  852.             o.write(',');
  853.             right.save(o, Parser.COMMA, level, ns);
  854.             o.write(')');
  855.         }
  856.         level--;
  857.     }
  858. }    
  859.  
  860. class Choice extends Node
  861. {
  862.     /**
  863.      * left node
  864.      */    
  865.     Node left;
  866.     
  867.     /**
  868.      * right node
  869.      */    
  870.     Node right;
  871.     
  872.     Choice(Node left, Node right)
  873.     {
  874.         this.left = left;
  875.         this.right = right;
  876.     }
  877.     
  878.     Node clone(ContentModel cm)
  879.     {
  880.         return new Choice(left.clone(cm), right.clone(cm));
  881.     }
  882.  
  883.     boolean nullable() 
  884.     {
  885.         return left.nullable() || right.nullable();
  886.     }
  887.     
  888.     BitSet firstpos(int positions)
  889.     {
  890.         if (first == null)
  891.         {
  892.             first = (BitSet)left.firstpos(positions).clone();
  893.             first.or(right.firstpos(positions));
  894.         }
  895.         return first;
  896.     }
  897.     
  898.     BitSet lastpos(int positions)
  899.     {
  900.         if (last == null)
  901.         {
  902.             last = (BitSet)left.lastpos(positions).clone();
  903.             last.or(right.lastpos(positions));
  904.         }
  905.  
  906.         return last;
  907.     }
  908.     
  909.     void calcfollowpos(BitSet[] followpos)
  910.     {
  911.         left.calcfollowpos(followpos);
  912.         right.calcfollowpos(followpos);
  913.     }
  914.  
  915.     Element toSchema(int parentType, int level, Element currElement)
  916.     {   
  917.         Element tempCurr;
  918.         Element orElement;
  919.  
  920.         if (parentType == Parser.OR) {
  921.             currElement = left.toSchema(Parser.OR, level,currElement);
  922.             right.toSchema(Parser.OR, level,currElement);
  923.         }
  924.         else {
  925.  
  926.             orElement = new ElementImpl( Name.create("GROUP","XML"), Element.ELEMENT );
  927.             orElement.setAttribute(Name.create("GROUPTYPE","XML"), "OR");
  928.  
  929.             if (parentType == Parser.QMARK)
  930.                 orElement.setAttribute(Name.create("OCCURS","XML"), "OPTIONAL");
  931.             else if (parentType == Parser.ASTERISK)
  932.                 orElement.setAttribute(Name.create("OCCURS","XML"), "STAR");
  933.             else if (parentType == Parser.PLUS)
  934.                 orElement.setAttribute(Name.create("OCCURS","XML"), "PLUS");
  935.  
  936.             orElement = left.toSchema(Parser.OR, level, orElement);
  937.             right.toSchema(Parser.OR, level, orElement);
  938.  
  939.             currElement.addChild(orElement, null);
  940.         }     
  941.         level--;
  942.  
  943.         return currElement;
  944.     }
  945.  
  946.     void save(XMLOutputStream o, int parentType, int level, Atom ns) throws IOException
  947.     {
  948.         level++;
  949.         if (parentType == Parser.OR) {
  950.             left.save(o, Parser.OR, level, ns);
  951.             o.write('|');
  952.             right.save(o, Parser.OR, level, ns);
  953.         }
  954.         else {
  955.             o.write('(');
  956.             left.save(o, Parser.OR, level, ns);
  957.             o.write('|');
  958.             right.save(o, Parser.OR, level, ns);
  959.             o.write(')');
  960.         }        
  961.         level--;
  962.     }
  963. }    
  964.  
  965. class Qmark extends Node
  966. {
  967.     /**
  968.      * node
  969.      */
  970.     Node node;
  971.     
  972.     Qmark(Node node)
  973.     {
  974.         this.node = node;
  975.     }
  976.     
  977.     Node clone(ContentModel cm)
  978.     {
  979.         return new Qmark(node.clone(cm));
  980.     }
  981.  
  982.     boolean nullable() 
  983.     {
  984.         return true;
  985.     }
  986.     
  987.     BitSet firstpos(int positions)
  988.     {
  989.         if (first == null)
  990.         {
  991.             first = node.firstpos(positions);
  992.         }
  993.         return first;
  994.     }
  995.     
  996.     BitSet lastpos(int positions)
  997.     {
  998.         if (last == null)
  999.         {
  1000.             last = node.lastpos(positions);
  1001.         }
  1002.  
  1003.         return last;
  1004.     }
  1005.     
  1006.     void calcfollowpos(BitSet[] followpos)
  1007.     {
  1008.         node.calcfollowpos(followpos);
  1009.     }
  1010.  
  1011.     Element toSchema(int parentType, int level, Element currElement)
  1012.     {
  1013.         level++;       
  1014.         node.toSchema(Parser.QMARK, level, currElement);
  1015.         level--;
  1016.  
  1017.         return currElement;
  1018.     }
  1019.  
  1020.     void save(XMLOutputStream o, int parentType, int level, Atom ns) throws IOException
  1021.     {
  1022.         level++;
  1023.         if (parentType == Parser.QMARK || parentType == Parser.ASTERISK)
  1024.             o.writeChars("(");          
  1025.         node.save(o, Parser.QMARK, level, ns);
  1026.         o.write('?');
  1027.         if (parentType == Parser.QMARK || parentType == Parser.ASTERISK)
  1028.             o.writeChars(")");
  1029.         level--;
  1030.     }
  1031. }
  1032.  
  1033.  
  1034. class Closure extends Node
  1035. {
  1036.     /**
  1037.      * node
  1038.      */    
  1039.     Node node;
  1040.     
  1041.     Closure(Node node)
  1042.     {
  1043.         this.node = node;
  1044.     }
  1045.     
  1046.     Closure()
  1047.     {
  1048.     }
  1049.  
  1050.     Node clone(ContentModel cm)
  1051.     {
  1052.         return new Closure(node.clone(cm));
  1053.     }
  1054.  
  1055.     boolean nullable() 
  1056.     {
  1057.         return true;
  1058.     }
  1059.     
  1060.     BitSet firstpos(int positions)
  1061.     {
  1062.         if (first == null)
  1063.         {
  1064.             first = node.firstpos(positions);
  1065.         }
  1066.         return first;
  1067.     }
  1068.     
  1069.     BitSet lastpos(int positions)
  1070.     {
  1071.         if (last == null)
  1072.         {
  1073.            last = node.lastpos(positions);
  1074.         }
  1075.         return last;
  1076.     }
  1077.     
  1078.     void calcfollowpos(BitSet[] followpos)
  1079.     {
  1080.         node.calcfollowpos(followpos);
  1081.         
  1082.         int l = followpos.length;        
  1083.         lastpos(l);
  1084.         firstpos(l);        
  1085.  
  1086.         for (int i = followpos.length - 1; i >= 0; i--)
  1087.         {
  1088.             if (last.get(i))
  1089.             {
  1090.                 followpos[i].or(first);
  1091.             }
  1092.         }
  1093.     }
  1094.  
  1095.     Element toSchema(int parentType, int level, Element currElement)
  1096.     {
  1097.  
  1098.         level++;       
  1099.         node.toSchema(Parser.ASTERISK, level, currElement);
  1100.         level--;
  1101.  
  1102.         return currElement;
  1103.     }
  1104.  
  1105.     void save(XMLOutputStream o, int parentType, int level, Atom ns) throws IOException
  1106.     {
  1107.         if (parentType == Parser.QMARK || parentType == Parser.ASTERISK)
  1108.             o.writeChars("(");
  1109.         level++;
  1110.         node.save(o, Parser.ASTERISK, level, ns);
  1111.         level--; 
  1112.  
  1113.         o.write('*');
  1114.         if (parentType == Parser.QMARK || parentType == Parser.ASTERISK)
  1115.             o.writeChars(")");
  1116.     }
  1117. }    
  1118.  
  1119.  
  1120. class ClosurePlus extends Closure
  1121. {
  1122.     ClosurePlus(Node node)
  1123.     {
  1124.         this.node = node;
  1125.     }
  1126.     
  1127.     Node clone(ContentModel cm)
  1128.     {
  1129.         return new ClosurePlus(node.clone(cm));
  1130.     }
  1131.  
  1132.     boolean nullable() 
  1133.     {
  1134.         return node.nullable();
  1135.     }    
  1136.  
  1137.     Element toSchema(int parentType, int level, Element currElement)
  1138.     {
  1139.         level++;       
  1140.         node.toSchema(Parser.PLUS, level, currElement);
  1141.         level--;
  1142.  
  1143.         return currElement;
  1144.     }
  1145.  
  1146.     void save(XMLOutputStream o, int parentType, int level, Atom ns) throws IOException
  1147.     {
  1148.         if (parentType == Parser.QMARK || parentType == Parser.ASTERISK)
  1149.             o.writeChars("(");
  1150.         level++;
  1151.         node.save(o, Parser.ASTERISK, level, ns);
  1152.         level--; 
  1153.         o.write('+');
  1154.         if (parentType == Parser.QMARK || parentType == Parser.ASTERISK)
  1155.             o.writeChars(")");
  1156.     }
  1157. }