Subversion Repositories openrisc

/* FullSyntaxBuilder.java --

   Copyright (C) 2006  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., 51 Franklin Street, Fifth Floor, Boston, MA

02110-1301 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.validation.relaxng;

import java.io.InputStream;

import java.io.IOException;

import java.io.UnsupportedEncodingException;

import java.net.URL;

import java.net.URLEncoder;

import java.util.Collections;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

import java.util.Set;

import javax.xml.XMLConstants;

import javax.xml.parsers.DocumentBuilder;

import javax.xml.parsers.DocumentBuilderFactory;

import javax.xml.parsers.ParserConfigurationException;

import org.relaxng.datatype.DatatypeException;

import org.relaxng.datatype.DatatypeLibrary;

import org.relaxng.datatype.helpers.DatatypeLibraryLoader;

import org.w3c.dom.Document;

import org.w3c.dom.Element;

import org.w3c.dom.NamedNodeMap;

import org.w3c.dom.Node;

import org.xml.sax.SAXException;

import gnu.xml.stream.XMLParser;

/**

 * Parses a RELAX NG XML DOM tree, constructing a compiled internal

 * representation.

 *

 * @author <a href='mailto:dog@gnu.org'>Chris Burdess</a>

 */

class FullSyntaxBuilder

{

  /**

   * Complete vocabulary (elements and attributes) of the full syntax.

   */

  static final Map VOCABULARY = new HashMap();

  static final Set STRIPPED_ATTRIBUTES = new HashSet();

  static final Set PATTERN_ELEMENTS = new HashSet();

  static

  {

    Set elementAttrs = Collections.singleton("name");

    Set dataAttrs = new HashSet();

    dataAttrs.add("type");

    dataAttrs.add("datatypeLibrary");

    Set valueAttrs = new HashSet();

    valueAttrs.add("type");

    valueAttrs.add("datatypeLibrary");

    valueAttrs.add("ns");

    Set externalAttrs = Collections.singleton("href");

    Set startAttrs = Collections.singleton("combine");

    Set defineAttrs = new HashSet();

    defineAttrs.add("name");

    defineAttrs.add("combine");

    Set nsAttrs = Collections.singleton("ns");

    VOCABULARY.put("element", elementAttrs);

    VOCABULARY.put("attribute", elementAttrs);

    VOCABULARY.put("group", Collections.EMPTY_SET);

    VOCABULARY.put("interleave", Collections.EMPTY_SET);

    VOCABULARY.put("choice", Collections.EMPTY_SET);

    VOCABULARY.put("optional", Collections.EMPTY_SET);

    VOCABULARY.put("zeroOrMore", Collections.EMPTY_SET);

    VOCABULARY.put("oneOrMore", Collections.EMPTY_SET);

    VOCABULARY.put("list", Collections.EMPTY_SET);

    VOCABULARY.put("mixed", Collections.EMPTY_SET);

    VOCABULARY.put("ref", elementAttrs);

    VOCABULARY.put("parentRef", elementAttrs);

    VOCABULARY.put("empty", Collections.EMPTY_SET);

    VOCABULARY.put("text", Collections.EMPTY_SET);

    VOCABULARY.put("value", valueAttrs);

    VOCABULARY.put("data", dataAttrs);

    VOCABULARY.put("notAllowed", Collections.EMPTY_SET);

    VOCABULARY.put("externalRef", externalAttrs);

    VOCABULARY.put("grammar", Collections.EMPTY_SET);

    VOCABULARY.put("param", elementAttrs);

    VOCABULARY.put("except", Collections.EMPTY_SET);

    VOCABULARY.put("div", Collections.EMPTY_SET);

    VOCABULARY.put("include", externalAttrs);

    VOCABULARY.put("start", startAttrs);

    VOCABULARY.put("define", defineAttrs);

    VOCABULARY.put("name", nsAttrs);

    VOCABULARY.put("anyName", Collections.EMPTY_SET);

    VOCABULARY.put("nsName", nsAttrs);

    STRIPPED_ATTRIBUTES.add("name");

    STRIPPED_ATTRIBUTES.add("type");

    STRIPPED_ATTRIBUTES.add("combine");

    PATTERN_ELEMENTS.add("element");

    PATTERN_ELEMENTS.add("attribute");

    PATTERN_ELEMENTS.add("group");

    PATTERN_ELEMENTS.add("interleave");

    PATTERN_ELEMENTS.add("choice");

    PATTERN_ELEMENTS.add("optional");

    PATTERN_ELEMENTS.add("zeroOrMore");

    PATTERN_ELEMENTS.add("oneOrMore");

    PATTERN_ELEMENTS.add("list");

    PATTERN_ELEMENTS.add("mixed");

    PATTERN_ELEMENTS.add("ref");

    PATTERN_ELEMENTS.add("parentRef");

    PATTERN_ELEMENTS.add("empty");

    PATTERN_ELEMENTS.add("text");

    PATTERN_ELEMENTS.add("value");

    PATTERN_ELEMENTS.add("data");

    PATTERN_ELEMENTS.add("notAllowed");

    PATTERN_ELEMENTS.add("externalRef");

    PATTERN_ELEMENTS.add("grammar");

  }

  private Set urls; // recursion checking

  private int refCount; // creation of ref names

  private Map datatypeLibraries;

  /**

   * Parse the specified document into a grammar.

   */

  synchronized Grammar parse(Document doc)

    throws IOException

  {

    urls = new HashSet();

    refCount = 1;

    doc.normalizeDocument(); // Normalize XML document

    transform(doc); // Apply transformation rules to provide simple syntax

    // 4.18. grammar element

    Element p = doc.getDocumentElement();

    Element grammar =

      doc.createElementNS(XMLConstants.RELAXNG_NS_URI, "grammar");

    Element start =

      doc.createElementNS(XMLConstants.RELAXNG_NS_URI, "start");

    doc.removeChild(p);

    doc.appendChild(grammar);

    grammar.appendChild(start);

    start.appendChild(p);

    transformGrammar(grammar, p);

    Element define = getNextSiblingElement(start);

    while (define != null)

      {

        Element next = getNextSiblingElement(define);

        String name = define.getAttribute("new-name");

        if (name != null)

          {

            define.setAttribute("name", name);

            define.removeAttribute("new-name");

          }

        else

          grammar.removeChild(define); // unreferenced

        define = next;

      }

    // 4.19. define and ref elements

    Set allDefines = new HashSet(), reachableDefines = new HashSet();

    getDefines(allDefines, grammar, grammar, false);

    getDefines(reachableDefines, grammar, start, true);

    allDefines.removeAll(reachableDefines);

    for (Iterator i = allDefines.iterator(); i.hasNext(); )

      {

        // remove unreachable defines

        Element d = (Element) i.next();

        Node parent = d.getParentNode();

        parent.removeChild(d);

      }

    // replace all elements that are not children of defines by refs to new

    // defines

    Set elements = new HashSet();

    getElements(elements, grammar, grammar);

    for (Iterator i = elements.iterator(); i.hasNext(); )

      {

        Element element = (Element) i.next();

        Node parent = element.getParentNode();

        if (!reachableDefines.contains(parent))

          {

            define =

              doc.createElementNS(XMLConstants.RELAXNG_NS_URI, "define");

            Element ref =

              doc.createElementNS(XMLConstants.RELAXNG_NS_URI, "ref");

            String name = createRefName();

            define.setAttribute("name", name);

            ref.setAttribute("name", name);

            parent.insertBefore(ref, element);

            define.appendChild(element);

            grammar.appendChild(define);

            reachableDefines.add(define);

          }

      }

    // Get defines that don't have element children

    for (Iterator i = reachableDefines.iterator(); i.hasNext(); )

      {

        Element d = (Element) i.next();

        Element child = getFirstChildElement(d);

        if (child != null && "element".equals(child.getLocalName()))

          i.remove();

      }

    // Expand refs that refer to these defines

    expandRefs(reachableDefines, grammar);

    // Remove any defines that don't have element children

    for (Iterator i = reachableDefines.iterator(); i.hasNext(); )

      {

        Element d = (Element) i.next();

        Node parent = d.getParentNode();

        parent.removeChild(d);

      }

    transform2(p); // Apply second stage transformation rules

    Grammar ret = parseGrammar(grammar);

    datatypeLibraries = null; // free datatype libraries cache

    return ret;

  }

  private void getDefines(Set defines, Element grammar, Element node,

                          boolean followRefs)

  {

    String elementName = node.getLocalName();

    if ("define".equals(elementName))

      defines.add(node);

    else if ("ref".equals(elementName) && followRefs)

      {

        String rname = node.getAttribute("name");

        Element define = getFirstChildElement(grammar);

        define = getNextSiblingElement(define);

        while (define != null)

          {

            String dname = define.getAttribute("name");

            if (rname.equals(dname))

              {

                getDefines(defines, grammar, node, followRefs);

                break;

              }

            define = getNextSiblingElement(define);

          }

      }

    for (Element child = getFirstChildElement(node); child != null;

         child = getNextSiblingElement(child))

      getDefines(defines, grammar, child, followRefs);

  }

  private void getElements(Set elements, Element grammar, Element node)

  {

    String elementName = node.getLocalName();

    if ("element".equals(elementName))

      elements.add(node);

    for (Element child = getFirstChildElement(node); child != null;

         child = getNextSiblingElement(child))

      getElements(elements, grammar, child);

  }

  private void expandRefs(Set defines, Element node)

    throws GrammarException

  {

    String elementName = node.getLocalName();

    if ("ref".equals(elementName))

      {

        String rname = node.getAttribute("name");

        for (Iterator i = defines.iterator(); i.hasNext(); )

          {

            Element define = (Element) i.next();

            String dname = define.getAttribute("name");

            if (rname.equals(dname))

              {

                Element child = getFirstChildElement(define);

                forbidRefs(child, rname);

                Element refChild = (Element) child.cloneNode(true);

                Node parent = node.getParentNode();

                parent.insertBefore(refChild, node);

                parent.removeChild(node);

                node = refChild;

                break;

              }

          }

      }

    for (Element child = getFirstChildElement(node); child != null;

         child = getNextSiblingElement(child))

      expandRefs(defines, child);

  }

  private void forbidRefs(Element node, String name)

    throws GrammarException

  {

    String elementName = node.getLocalName();

    if ("ref".equals(elementName))

      {

        String rname = node.getAttribute("name");

        if (name.equals(rname))

          throw new GrammarException("cannot expand ref with name '" + name +

                                     "' due to circularity");

      }

    for (Element child = getFirstChildElement(node); child != null;

         child = getNextSiblingElement(child))

      forbidRefs(child, name);

  }

  private void transform(Node node)

    throws IOException

  {

    Node parent = node.getParentNode();

    switch (node.getNodeType())

      {

      case Node.ELEMENT_NODE:

        // 4.1 Annotations

        String elementNs = node.getNamespaceURI();

        String elementName = node.getLocalName();

        if (!XMLConstants.RELAXNG_NS_URI.equals(elementNs) ||

            !VOCABULARY.containsKey(elementName))

          parent.removeChild(node);

        else

          {

            Set allowedAttrs = (Set) VOCABULARY.get(elementName);

            NamedNodeMap attrs = node.getAttributes();

            int len = attrs.getLength();

            for (int i = len - 1; i >= 0; i--)

              {

                Node attr = attrs.item(i);

                String attrNs = attr.getNamespaceURI();

                String attrName = attr.getLocalName();

                if (XMLConstants.XMLNS_ATTRIBUTE_NS_URI.equals(attrNs))

                  continue; // ignore namespace nodes

                if (!(XMLConstants.RELAXNG_NS_URI.equals(attrNs) ||

                      attrNs == null) ||

                    !allowedAttrs.contains(attrName))

                  attrs.removeNamedItemNS(attrNs, attrName);

                else

                  {

                    // 4.2 Whitespace

                    if (STRIPPED_ATTRIBUTES.contains(attrName))

                      attr.setNodeValue(attr.getNodeValue().trim());

                    // 4.3 datatypeLibrary attribute

                    else if ("datatypeLibrary".equals(attrName))

                      {

                        String dl = attr.getNodeValue();

                        attr.setNodeValue(escapeURL(dl));

                      }

                    // 4.5. href attribute

                    else if ("href".equals(attrName))

                      {

                        String href = attr.getNodeValue();

                        href = XMLParser.absolutize(node.getBaseURI(),

                                                    escapeURL(href));

                        attr.setNodeValue(href);

                      }

                  }

              }

            // 4.3 datatypeLibrary attribute

            if ("data".equals(elementName) || "value".equals(elementName))

              {

                Element element = (Element) node;

                String dl = element.getAttribute("datatypeLibrary");

                if (dl == null)

                  {

                    Node p = parent;

                    while (dl == null && p != null &&

                           p.getNodeType() == Node.ELEMENT_NODE)

                      {

                        dl = ((Element) p)

                          .getAttribute("datatypeLibrary");

                        p = p.getParentNode();

                      }

                    if (dl == null)

                      dl = "";

                    element.setAttribute("datatypeLibrary", dl);

                  }

                // 4.4. type attribute of value element

                if ("value".equals(elementName))

                  {

                    String type = element.getAttribute("type");

                    if (type == null)

                      {

                        element.setAttribute("type", "token");

                        element.setAttribute("datatypeLibrary", "");

                      }

                  }

                // 4.16. Constraints

                // TODO validate type

              }

            // 4.6. externalRef element

            else if ("externalRef".equals(elementName))

              {

                Element externalRef = (Element) node;

                String href = externalRef.getAttribute("href");

                // check for recursion

                if (urls.contains(href))

                  throw new GrammarException("recursive href");

                urls.add(href);

                Element element = resolve(href);

                String eNs = element.getNamespaceURI();

                String eName = element.getLocalName();

                if (!(XMLConstants.RELAXNG_NS_URI.equals(eNs) ||

                      eNs == null) ||

                    !PATTERN_ELEMENTS.contains(eName))

                  throw new GrammarException("externally referenced element " +

                                             "is not a pattern");

                transform(element);

                urls.remove(href);

                String ns = element.getAttribute("ns");

                if (ns != null)

                  element.setAttribute("ns",

                                       externalRef.getAttribute("ns"));

                element = (Element) externalRef.getOwnerDocument()

                  .importNode(element, true);

                parent.replaceChild(element, externalRef);

                return;

              }

            // 4.7 include element

            else if ("include".equals(elementName))

              {

                Element include = (Element) node;

                String href = include.getAttribute("href");

                // check for recursion

                if (urls.contains(href))

                  throw new GrammarException("recursive href");

                urls.add(href);

                Element element = resolve(href);

                String eNs = element.getNamespaceURI();

                String eName = element.getLocalName();

                if (!(XMLConstants.RELAXNG_NS_URI.equals(eNs) ||

                      eNs == null) ||

                    !"grammar".equals(eName))

                  throw new GrammarException("included element is not " +

                                             "a grammar");

                transform(element);

                urls.remove(href);

                // handle components

                List includeComponents = getComponents(include);

                List grammarComponents = getComponents(element);

                for (Iterator i = includeComponents.iterator(); i.hasNext(); )

                  {

                    Element comp = (Element) i.next();

                    String compName = comp.getLocalName();

                    if ("start".equals(compName))

                      {

                        boolean found = false;

                        for (Iterator j = grammarComponents.iterator();

                             j.hasNext(); )

                          {

                            Element c2 = (Element) j.next();

                            if ("start".equals(c2.getLocalName()))

                              {

                                c2.getParentNode().removeChild(c2);

                                found = true;

                              }

                          }

                        if (!found)

                          throw new GrammarException("no start component in " +

                                                     "included grammar");

                      }

                    else if ("define".equals(compName))

                      {

                        String name = comp.getAttribute("name");

                        boolean found = false;

                        for (Iterator j = grammarComponents.iterator();

                             j.hasNext(); )

                          {

                            Element c2 = (Element) j.next();

                            if ("define".equals(c2.getLocalName()) &&

                                name.equals(c2.getAttribute("name")))

                              {

                                c2.getParentNode().removeChild(c2);

                                found = true;

                              }

                          }

                        if (!found)

                          throw new GrammarException("no define component " +

                                                     "with name '" + name +

                                                     "' in included grammar");

                      }

                  }

                // transform to div element

                Document doc = include.getOwnerDocument();

                Element includeDiv =

                  doc.createElementNS(XMLConstants.RELAXNG_NS_URI, "div");

                Element grammarDiv =

                  doc.createElementNS(XMLConstants.RELAXNG_NS_URI, "div");

                // XXX copy include non-href attributes (none defined?)

                element = (Element) doc.importNode(element, true);

                Node ctx = element.getFirstChild();

                while (ctx != null)

                  {

                    Node next = ctx.getNextSibling();

                    grammarDiv.appendChild(ctx);

                    ctx = next;

                  }

                includeDiv.appendChild(grammarDiv);

                ctx = include.getFirstChild();

                while (ctx != null)

                  {

                    Node next = ctx.getNextSibling();

                    includeDiv.appendChild(ctx);

                    ctx = next;

                  }

                parent.replaceChild(includeDiv, include);

                transform(includeDiv);

                return;

              }

            // 4.8. name attribute of element and attribute elements

            else if ("attribute".equals(elementName) ||

                     "element".equals(elementName))

              {

                Element element = (Element) node;

                String name = element.getAttribute("name");

                if (name != null)

                  {

                    Document doc = element.getOwnerDocument();

                    Element n =

                      doc.createElementNS(XMLConstants.RELAXNG_NS_URI, "name");

                    n.appendChild(doc.createTextNode(name));

                    Node first = element.getFirstChild();

                    if (first != null)

                      element.insertBefore(n, first);

                    else

                      element.appendChild(n);

                    if ("attribute".equals(elementName))

                      {

                        String ns = element.getAttribute("ns");

                        if (ns != null)

                          {

                            n.setAttribute("ns", ns);

                            element.removeAttribute("ns");

                          }

                      }

                    element.removeAttribute("name");

                  }

                // 4.12. Number of child elements

                if ("attribute".equals(elementName))

                  {

                    if (getComponents(node).size() == 1)

                      {

                        Document doc = node.getOwnerDocument();

                        Element text =

                          doc.createElementNS(XMLConstants.RELAXNG_NS_URI,

                                              "text");

                        node.appendChild(text);

                      }

                  }

                else // element

                  {

                    if (node.getChildNodes().getLength() > 2)

                      {

                        // transform to 2 child elements

                        Document doc = node.getOwnerDocument();

                        Element child =

                          doc.createElementNS(XMLConstants.RELAXNG_NS_URI,

                                              "group");

                        Node ctx = getFirstChildElement(node);

                        ctx = getNextSiblingElement(ctx); // skip 1

                        while (ctx != null)

                          {

                            Node next = getNextSiblingElement(ctx);

                            child.appendChild(ctx);

                            ctx = next;