parse_xml.C

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#include <math.h>

#include <exception>
#include <string>
#include <vector>
#include <map>

// XML parser library
#include <expat.h>

#include <archon/util/term.H>
#include <archon/util/time.H>
#include <archon/util/parse_values.H>
#include <archon/util/text.H>
#include <archon/util/image.H>

#include <archon/x3d/server/field_type.H>
#include <archon/x3d/server/custom_field.H>
#include <archon/x3d/server/server.H>
#include <archon/x3d/server/parse_xml.H>

using namespace std;

namespace Archon
{
  using namespace Math;
  using namespace Utilities;

  namespace X3D
  {
    namespace XML
    {
      struct Parser: X3D::Parser
      {
        XML_Parser xmlParser;
        ProgressTracker *progressTracker;
        Time creationTimeStamp;
        bool progressive;

        enum Element
        {
          elem_nil,      // An unrecognized or invalid element
          elem_toplevel, // The special element always in bottom of the stack
          elem_x3d,
          elem_head,
          elem_meta,
          elem_component,
          elem_scene,
          elem_route,
          elem_proto,
          elem_field,
          elem_node,     // An element corresponding to a X3D node
          elem_use       // An element exploiting the USE attribute
        };

        struct StackEntry
        {
          Element element;

          Ref<NodeBase> node;

          Ref<CustomFieldBase> field;

          const NodeFieldBase *containerField;

          int containerStackIndex;

          string cdata;

          StackEntry(): element(elem_nil), containerField(0), containerStackIndex(-1) {}
        };

        string getElementName(Element e, const NodeType *t = 0)
        {
          switch(e)
          {
          case elem_nil:       return "(nil)";
          case elem_toplevel:  return "(toplevel)";
          case elem_x3d:       return "X3D";
          case elem_head:      return "head";
          case elem_meta:      return "meta";
          case elem_component: return "component";
          case elem_scene:     return "Scene";
          case elem_route:     return "ROUTE";
          case elem_proto:     return "PROTO";
          case elem_field:     return "field";
          case elem_node:      return t ? t->getName() : "(node)";
          case elem_use:       return t ? t->getName() : "(use)";
          }
          ARCHON_THROW1(ArgumentException,
                        "Invalid element type");
        }

        string getElementName(const StackEntry &e)
        {
          return getElementName(e.element, e.node ? e.node->getType() : 0);
        }

        Element elementLookup(string name)
        {
          if(Text::compareIgnoreCase(name, "X3D"      )==0) return elem_x3d;
          if(Text::compareIgnoreCase(name, "head"     )==0) return elem_head;
          if(Text::compareIgnoreCase(name, "meta"     )==0) return elem_meta;
          if(Text::compareIgnoreCase(name, "component")==0) return elem_component;
          if(Text::compareIgnoreCase(name, "Scene"    )==0) return elem_scene;
          if(Text::compareIgnoreCase(name, "ROUTE"    )==0) return elem_route;
          if(Text::compareIgnoreCase(name, "PROTO"    )==0) return elem_proto;
          if(Text::compareIgnoreCase(name, "field"    )==0) return elem_field;
          return elem_nil;
        }

        vector<StackEntry> containmentStack;

        void warning(string message)
        {
          if(logger)
            logger->log(sourceName + ":" + Text::toString(XML_GetCurrentLineNumber(xmlParser)) + ": [Warning] "
                        + message);
        }

        Parser(Ref<ExecutionContext> context, Ref<GroupingNode> rootGroup,
               string sourceName, XML_Parser xmlParser,
               ProgressTracker *progressTracker, Logger *logger,
               Time creationTimeStamp, bool progressive):
          X3D::Parser(context, rootGroup, sourceName, logger),
          xmlParser(xmlParser), progressTracker(progressTracker),
          creationTimeStamp(creationTimeStamp), progressive(progressive)
        {
          StackEntry stackEntry;
          stackEntry.element = elem_toplevel;
          containmentStack.push_back(stackEntry);
          initialize();
        }


        bool isWhiteSpace(const char *s)
        {
          while(*s == ' ' || *s == '\t' || *s == '\n' ||
                *s == '\r' || *s == '\f' || *s == ',') ++s;
          return !*s;
        }

        bool eatWord(const char *&s, const char *&from)
        {
          const char *_s = s;
          while(*_s == ' ' || *_s == '\t' || *_s == '\n' ||
                *_s == '\r' || *_s == '\f' || *_s == ',') ++_s;
          if(!*_s) return false;
          from = _s;
          ++_s;
          while(*_s && *_s != ' ' && *_s != '\t' && *_s != '\n' &&
                *_s != '\r' && *_s != '\f' && *_s != ',') ++_s;
          s = _s;
          return true;
        }

        bool eat(const char *&s, bool &v, bool &more)
        {
          try
          {
            const char *from;
            if(!eatWord(s, from)) return (more = false);
            v = ParseValues::parseBoolean(false, from, s);
          }
          catch(ParseException &e)
          {
            warning(e.getMessage() + "(assuming false)");
            v = false;
          }
          return true;
        }

        bool eat(const char *&s, int &v, bool &more)
        {
          try
          {
            const char *from;
            if(!eatWord(s, from)) return (more = false);
            v = ParseValues::parseInteger(true, from, s);
          }
          catch(ParseException &e)
          {
            warning(e.getMessage() + "(assuming zero)");
            v = 0;
          }
          return true;
        }

        bool eat(const char *&s, double &v, bool &more)
        {
          try
          {
            const char *from;
            if(!eatWord(s, from)) return (more = false);
            v = ParseValues::parseDouble(from, s);
          }
          catch(ParseException &e)
          {
            warning(e.getMessage() + "(assuming zero)");
            v = 0;
          }
          return true;
        }

        bool eat(const char *&s, Vector2 &v, bool &more)
        {
          try
          {
            const char *from;
            if(!eatWord(s, from)) return (more = false);
            v[0] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "2nd component missing");
            v[1] = ParseValues::parseDouble(from, s);
          }
          catch(ParseException &e)
          {
            warning(e.getMessage() + "(assuming zero)");
            v = Vector2::zero();
          }
          return true;
        }

        bool eat(const char *&s, Vector3 &v, bool &more)
        {
          try
          {
            const char *from;
            if(!eatWord(s, from)) return (more = false);
            v[0] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "2nd component missing");
            v[1] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "3rd component missing");
            v[2] = ParseValues::parseDouble(from, s);
          }
          catch(ParseException &e)
          {
            warning(e.getMessage() + "(assuming zero)");
            v = Vector3::zero();
          }
          return true;
        }

        bool eat(const char *&s, Vector4 &v, bool &more)
        {
          try
          {
            const char *from;
            if(!eatWord(s, from)) return (more = false);
            v[0] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "2nd component missing");
            v[1] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "3rd component missing");
            v[2] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "4th component missing");
            v[3] = ParseValues::parseDouble(from, s);
          }
          catch(ParseException &e)
          {
            warning(e.getMessage() + "(assuming zero)");
            v = Vector4::zero();
          }
          return true;
        }

        bool eat(const char *&s, Rotation3 &v, bool &more)
        {
          try
          {
            const char *from;
            if(!eatWord(s, from)) return (more = false);
            v.axis[0] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "y component missing");
            v.axis[1] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "z component missing");
            v.axis[2] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "angle missing");
            v.angle = ParseValues::parseDouble(from, s);
          }
          catch(ParseException &e)
          {
            warning(e.getMessage() + "(assuming no rotation)");
            v = Rotation3::zero();
          }
          return true;
        }


        bool eat(const char *&s, Image &v, bool &more)
        {
          try
          {
            const char *from;
            if(!eatWord(s, from)) return (more = false);
            /*
            v.axis[0] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "y component missing");
            v.axis[1] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "z component missing");
            v.axis[2] = ParseValues::parseDouble(from, s);
            if(!eatWord(s, from))
              ARCHON_THROW1(ParseException, "angle missing");
            v.angle = ParseValues::parseDouble(from, s);
            */
          }
          catch(ParseException &e)
          {
            warning(e.getMessage() + "(assuming no rotation)");
            //      v = Rotation3::zero();
          }
          return true;
        }

        bool eat(const char *&s, Time &v, bool &more)
        {
          double w;
          if(!eat(s, w, more)) return false;
          v = Time(w);
          return true;
        }


        template<class T>
        bool parseValue(const char *s, T &v)
        {
          T w;
          bool m;
          if(!eat(s, w, m))
          {
            warning("Empty string");
            return false;
          }
          if(!isWhiteSpace(s)) warning("Trailing garbage");
          v = w;
          return true;
        }

        template<class T>
        bool parseValue(const char *s, vector<T> &l)
        {
          l.clear();
          T v;
          bool m = true;
          while(m) if(eat(s, v, m)) l.push_back(v);
          return true;
        }

        bool parseValue(const char *s, string &v)
        {
          v = s;
          return true;
        }

        bool parseValue(const char *s, vector<string> &v)
        {
          for(;;)
          {
            while(*s == ' ' || *s == '\t' || *s == '\n' ||
                  *s == '\r' || *s == '\f' || *s == ',') ++s;
            if(!*s) break;
            if(*s == '"' || *s == '\'')
            {
              const char *to = strchr(s+1, *s);
              ++s;
              int n = to ? to - s : strlen(s);
              v.push_back(string(s, n));
              if(!to)
              {
                warning("Unpaired quotation");
                break;
              }
              s += n+1;
              continue;
            }

            const char *to = s+1;
            while(*to && *to != '"' && *to != '\'') ++to;
            --to;
            while(*to == ' ' || *to == '\t' || *to == '\n' ||
                  *to == '\r' || *to == '\f' || *to == ',') --to;
            ++to;
            int n = to - s;
            v.push_back(string(s, n));
            s = to;
          }

          return true;
        }



        struct ValueParserBase
        {
          virtual void parse(const char *, NodeBase *,
                             const FieldBase *, Parser *) const = 0;

          virtual Ref<CustomFieldBase>
          newCustomField(CustomFieldNode *c,
                         int i, string n, const FieldType *t,
                         bool isEventTarget, bool isEventSource,
                         Parser *p, const char *s) const = 0;

        protected:
          virtual ~ValueParserBase() {}
        };

        template<typename T>
        struct SingleValueParser: ValueParserBase
        {
          void parse(const char *s, NodeBase *n, const FieldBase *f,
                     Parser *p) const
          {
            T v;
            if(p->parseValue(s, v))
            {
              Ref<SimpleValue<T> > w = new SimpleValue<T>(f->getType(), v);
              Event e(w.get(), p->creationTimeStamp);

              /*
               * Note that we do not want the value assignment to
               * initiate an event cascade, but this is guaranteed not
               * to happen since this field is brand new and cannot
               * have any routes added to it yet. This is because we
               * are currently parsing the attributes of the start tag
               * of the node in question.
               */
              n->set(f, &e);
            }
          }

          Ref<CustomFieldBase>
          newCustomField(CustomFieldNode *c,
                         int i, string n, const FieldType *t,
                         bool isEventTarget, bool isEventSource,
                         Parser *p, const char *s) const
          {
            T v;
            if(s && p->parseValue(s, v))
            {
              return new SimpleCustomField<T>(c, i, n, t, isEventTarget,
                                              isEventSource, v);
            }
            return new SimpleCustomField<T>(c, i, n, t, isEventTarget,
                                            isEventSource, defaultValue);
          }

          SingleValueParser(const T &v): defaultValue(v) {}

        private:
          T defaultValue;
        };

        template<typename T>
        struct SequenceValueParser: ValueParserBase
        {
          typedef vector<T> V;

          void parse(const char *s, NodeBase *n, const FieldBase *f,
                     Parser *p) const
          {
            V v;
            if(p->parseValue(s, v))
            {
              Ref<SimpleValue<V> > w = new SimpleValue<V>(f->getType(), v);
              Event e(w.get(), p->creationTimeStamp);

              /*
               * Note that we do not want the value assignment to
               * initiate an event cascade, but this is guaranteed not
               * to happen since this field is brand new and cannot
               * have any routes added to it yet. This is because we
               * are currently parsing the attributes of the start tag
               * of the node in question.
               */
              n->set(f, &e);
            }
          }

          Ref<CustomFieldBase>
          newCustomField(CustomFieldNode *c,
                         int i, string n, const FieldType *t,
                         bool isEventTarget, bool isEventSource,
                         Parser *p, const char *s) const
          {
            V v;
            if(s && p->parseValue(s, v))
            {
              return new SimpleSeqCustomField<T>(c, i, n, t, isEventTarget,
                                                 isEventSource, v);
            }
            return new SimpleSeqCustomField<T>(c, i, n, t, isEventTarget,
                                               isEventSource, defaultValue);
          }

        private:
          V defaultValue;
        };

        map<const FieldType *, const ValueParserBase *> valueParsers;

        map<string, string> compatibilityFieldTypeNameMap;

        void initialize()
        {
          Vector4 one4;
          one4[0] = one4[1] = one4[2] = one4[3] = 1;

          valueParsers[SFBool::type]      = new SingleValueParser<bool>(false);
          valueParsers[MFBool::type]      = new SequenceValueParser<bool>;

          valueParsers[SFColor::type]     = new SingleValueParser<Vector3>(Vector3(1, 1, 1));
          valueParsers[MFColor::type]     = new SequenceValueParser<Vector3>;

          valueParsers[SFColorRGBA::type] = new SingleValueParser<Vector4>(one4);
          valueParsers[MFColorRGBA::type] = new SequenceValueParser<Vector4>;

          valueParsers[SFDouble::type]    = new SingleValueParser<double>(0);
          valueParsers[MFDouble::type]    = new SequenceValueParser<double>;

          valueParsers[SFFloat::type]     = new SingleValueParser<double>(0);
          valueParsers[MFFloat::type]     = new SequenceValueParser<double>;

          valueParsers[SFImage::type]     = new SingleValueParser<Image>(Image());
          valueParsers[MFImage::type]     = new SequenceValueParser<Image>;

          valueParsers[SFInt32::type]     = new SingleValueParser<int>(0);
          valueParsers[MFInt32::type]     = new SequenceValueParser<int>;

          valueParsers[SFRotation::type]  = new SingleValueParser<Rotation3>(Rotation3(Vector3(0, 0, 1), 0));
          valueParsers[MFRotation::type]  = new SequenceValueParser<Rotation3>;

          valueParsers[SFString::type]    = new SingleValueParser<string>(string());
          valueParsers[MFString::type]    = new SequenceValueParser<string>;

          valueParsers[SFTime::type]      = new SingleValueParser<Time>(Time());
          valueParsers[MFTime::type]      = new SequenceValueParser<Time>;

          valueParsers[SFVec2d::type]     = new SingleValueParser<Vector2>(Vector2(0, 0));
          valueParsers[MFVec2d::type]     = new SequenceValueParser<Vector2>;

          valueParsers[SFVec2f::type]     = new SingleValueParser<Vector2>(Vector2(0, 0));
          valueParsers[MFVec2f::type]     = new SequenceValueParser<Vector2>;

          valueParsers[SFVec3d::type]     = new SingleValueParser<Vector3>(Vector3(0, 0, 0));
          valueParsers[MFVec3d::type]     = new SequenceValueParser<Vector3>;

          valueParsers[SFVec3f::type]     = new SingleValueParser<Vector3>(Vector3(0, 0, 0));
          valueParsers[MFVec3f::type]     = new SequenceValueParser<Vector3>;


          compatibilityFieldTypeNameMap["Boolean"]            = "SFBool";
          compatibilityFieldTypeNameMap["Booleans"]           = "MFBool";
          compatibilityFieldTypeNameMap["Color"]              = "SFColor";
          compatibilityFieldTypeNameMap["Colors"]             = "MFColor";
          compatibilityFieldTypeNameMap["Double"]             = "SFDouble";
          compatibilityFieldTypeNameMap["Doubles"]            = "MFDouble";
          compatibilityFieldTypeNameMap["Float"]              = "SFFloat";
          compatibilityFieldTypeNameMap["Floats"]             = "MFFloat";
          compatibilityFieldTypeNameMap["Image"]              = "SFImage";
          compatibilityFieldTypeNameMap["Images"]             = "MFImage";
          compatibilityFieldTypeNameMap["Integer"]            = "SFInt32";
          compatibilityFieldTypeNameMap["Integers"]           = "MFInt32";
          compatibilityFieldTypeNameMap["Node"]               = "SFNode";
          compatibilityFieldTypeNameMap["Nodes"]              = "MFNode";
          compatibilityFieldTypeNameMap["Rotation"]           = "SFRotation";
          compatibilityFieldTypeNameMap["Rotations"]          = "MFRotation";
          compatibilityFieldTypeNameMap["String"]             = "SFString";
          compatibilityFieldTypeNameMap["Strings"]            = "MFString";
          compatibilityFieldTypeNameMap["Time"]               = "SFTime";
          compatibilityFieldTypeNameMap["Times"]              = "MFTime";
          compatibilityFieldTypeNameMap["Vector2Float"]       = "SFVec2f";
          compatibilityFieldTypeNameMap["Vector2FloatArray"]  = "MFVec2f";
          compatibilityFieldTypeNameMap["Vector3Float"]       = "SFVec3f";
          compatibilityFieldTypeNameMap["Vector3FloatArray"]  = "MFVec3f";
          compatibilityFieldTypeNameMap["Vector2Double"]      = "SFVec2f";
          compatibilityFieldTypeNameMap["Vector2DoubleArray"] = "MFVec2f";
          compatibilityFieldTypeNameMap["Vector3Double"]      = "SFVec3d";
          compatibilityFieldTypeNameMap["Vector3DoubleArray"] = "MFVec3d";
        }

        Ref<NodeBase> lookupUseNode(string name, const NodeType *type)
        {
          Ref<NodeBase> node = lookupNode(name);
          if(!node)
          {
            warning("Undefined name '" + name + "' in 'USE'");
            return 0;
          }
          if(node->getType() != type)
          {
            warning("Attempt to use '" + node->getType()->getName() + "' as '" + type->getName() + "'");
            return 0;
          }
          return node;
        }

        Ref<NodeBase> checkUseAttribute(const char *atts[], const NodeType *nodeType)
        {
          Ref<NodeBase> n;
          bool noUse = false;
          for(int i=0; atts[i] && atts[i+1]; i+=2)
          {
            if(Text::compareIgnoreCase(atts[i], "USE") == 0)
            {
              if(string(atts[i]) != "USE")
                warning("Attribute '" + string(atts[i]) + "' should be spelled 'USE'");
              n = lookupUseNode(atts[i+1], nodeType);
            }
            else if(Text::compareIgnoreCase(atts[i], "containerField") != 0)
              noUse = true;
            if(noUse && n)
            {
              warning("Only the 'containerField' attributes is accepted in conjunction with 'USE'");
              break;
            }
          }
          return n;
        }

        void displayStack(bool push)
        {
          vector<double> columnWidthFractions;
          columnWidthFractions.push_back(2);
          columnWidthFractions.push_back(5);
          columnWidthFractions.push_back(10);
          columnWidthFractions.push_back(10);
          columnWidthFractions.push_back(2);
          columnWidthFractions.push_back(2);
          columnWidthFractions.push_back(10);
          columnWidthFractions.push_back(10);
          Text::Table<string> table(containmentStack.size()+1, columnWidthFractions);
          for(unsigned i=0; i<containmentStack.size(); ++i)
          {
            StackEntry &e = containmentStack[i];
            table(i, 0) = Text::toString(i);
            table(i, 1) = getElementName(e.element);
            table(i, 2) = e.node ? e.node->getType()->getName() : "";
            table(i, 3) = e.node ? e.node->getName() : "";
            table(i, 4) = "->";
            table(i, 5) = Text::toString(e.containerStackIndex);
            table(i, 6) = e.containerField ? e.containerField->getName() : "";
            table(i, 7) = e.containerField ? e.containerField->getType()->getName() : "";
          }

          logger->log("Stack " + string(push?"push":"pop") + ":\n" +
                      Text::format(table, Term::getWidth(), 2, false));
        }

        bool attr_cmp(string s, string attribute, Element element,
                      bool deprecated = false)
        {
          if(Text::compareIgnoreCase(s, attribute)==0)
          {
            if(s != attribute)
              warning("Attribute '" + s + "' of element '" +
                      getElementName(element) + "' should be spelled '" +
                      attribute + "'");
            if(deprecated)
              warning("Use of attribute '" + s + "' in element '" +
                      getElementName(element) + "' is deprecated.");
            return true;
          }
          return false;
        }

        /*
         * Rules for verification of element containment:
         *
         * The X3D element may be contained in the imaginary top-level
         * element only.
         *
         * The special non-node hierachical elements such as head, meta,
         * component & Scene may never be contained in any node-type
         * element.
         *
         * Route and Proto elements may be contained in the scene element
         * or in any element contained directly or indirectly in the scene
         * element.
         *
         * Node-type elements may be contained in other node-type elements
         * according to their runtime type information only with the
         * exception that those derived from the ChildNode may be
         * contained in the special Scene element.
         *
         * Nothing may be contained in a node-type element that utilizes
         * the USE attribute.
         *
         * When verifying the containment rules, the containment stack is
         * consulted. The element at the top of the stack is always the
         * element that imediately encloses the currently encountered
         * element. If this element at the top of the stack is a valid
         * container for the new element, then all is fine. If not, then
         * the stack is traversed from top to bottom, to see if any
         * non-immediately enclosing element complies as a container. If
         * such a container is found then it will be used but a warning
         * will be issued.
         *
         * Any encountered element that does not have a compliant
         * container on the stack will be ignored
         */
        void parseStartElement(const char *name, const char *atts[],
                               StackEntry *stackEntry)
        {
          // Determine the type of element
          Element element = elementLookup(name);
          const NodeType *nodeType = 0;

          if(element == elem_nil)
          {
            nodeType = NodeType::lookup(name);

            if(!nodeType || !nodeType->isUserInstantiable())
            {
              warning("Unknown element '" + string(name) + "' (element ignored)");
              return;
            }

            if(nodeType->getName() != name)
              warning("Element '" + string(name) + "' should be spelled '" +
                      nodeType->getName() + "'");

            element = elem_node; // May later become 'elem_use'
          }
          else if(getElementName(element) != name)
            warning("Element '" + string(name) + "' should be spelled '" +
                    getElementName(element) + "'");


          // For elements of node type determine the desired name of
          // the container field
          string containerFieldName;
          if(nodeType)
          {
            bool found = false;
            for(int i=0; atts[i] && atts[i+1]; i+=2)
            {
              if(Text::compareIgnoreCase(atts[i], "containerField") == 0)
              {
                if(string(atts[i]) != "containerField")
                  warning("Attribute '" + string(atts[i]) + "' should be spelled 'containerField'");
                containerFieldName = atts[i+1];
                found = true;
                break;
              }
            }
            if(!found) containerFieldName = nodeType->getContainerField();
          }

          /*
           * Find the container element (and the target field for
           * node-type elements):
           *
           * See the note on containment verification rules above!
           *
           * When the search terminates 'containerStackIndex == -1'
           * indicates 'not found', else if 'containerField == 0' the the
           * new element is a child of the Scene element.
           */
          int containerStackIndex = -1;
          const NodeFieldBase *containerField = 0;
          bool fallThrough = false;
          for(int i = int(containmentStack.size())-1; i>=0; --i)
          {
            if(i < int(containmentStack.size())-1) fallThrough = true;

            Element containerElement = containmentStack[i].element;

            // Get rid of impossible containers
            if(containerElement == elem_nil ||
               containerElement == elem_route ||
               containerElement == elem_proto ||
               containerElement == elem_use) continue;

            // Handle new node-type elements
            if(element == elem_node)
            {
              if(containerElement == elem_field)
              {
                if(NodeFieldBase *f = dynamic_cast<NodeFieldBase *>(containmentStack[i].field.get()))
                {
                  containerStackIndex = containmentStack[i].containerStackIndex;
                  containerField = f;
                  break;
                }
                continue;
              }

              if(containerElement == elem_scene &&
                 nodeType->isDerivedFrom(ChildNode::type))
              {
                containerStackIndex = i;
                break;
              }

              if(containerElement != elem_node) break;

              Ref<NodeBase> n = containmentStack[i].node;
              if(!n) ARCHON_THROW1(InternalException,
                                   "x3d/parse_xml: Stack entry "
                                   "unexpectedly had no node");
              const NodeType *t = n->getType();
              containerField = dynamic_cast<const NodeFieldBase *>(t->lookupField(containerFieldName));
              if(!containerField)
              {
                containerField = t->lookupNodeField(nodeType);
                if(containerField)
                  warning("Bad container field '" + containerFieldName +
                          "' (using '" + containerField->getName() + "')");
              }
              if(containerField)
              {
                containerStackIndex = i;
                break;
              }
              continue;
            }

            // Handle Script fields
            if(element == elem_field)
            {
              if(containerElement != elem_node) continue;

              Ref<NodeBase> n = containmentStack[i].node;
              if(!n) ARCHON_THROW1(InternalException,
                                   "XML::Parser::parseStartElement: "
                                   "Stack entry unexpectedly had no "
                                   "node");
              if(!dynamic_cast<CustomFieldNode *>(n.get())) continue;
              containerStackIndex = i;
              break;
            }

            // Handle Route and PROTO
            if(element == elem_route || element == elem_proto)
            {
              if(containerElement == elem_scene ||
                 containerElement == elem_node)
              {
                containerStackIndex = i;
                break;
              }
              continue;
            }

            // Handle special non-node hierachical elements
            if(element == elem_x3d && containerElement == elem_toplevel ||
               element == elem_head && containerElement == elem_x3d ||
               element == elem_meta && containerElement == elem_head ||
               element == elem_component && containerElement == elem_head ||
               element == elem_scene && containerElement == elem_x3d)
            {
              containerStackIndex = i;
              break;
            }
          }


          /*
           * If we didn't find a compatible container element or
           * the container element wasn't the imediately enclosing element
           *
           * Note: this should be converted to a switch statement!
           */
          if(containerStackIndex < 0 || fallThrough)
          {
            string message;
            switch(containmentStack.back().element)
            {
            case elem_toplevel:
              message = "Element '" + getElementName(element, nodeType) +
                "' is not allowed as the top level element";
              break;
            case elem_use:
              message = "Element '" + getElementName(element, nodeType) +
                "' is not allowed in elements that employ the USE "
                "attribute";
              break;
            case elem_nil:
              message = "Ill placed element '" +
                getElementName(element, nodeType) + "'";
              break;
            case elem_field:
              message = "Node elements are not allowed in field elements "
                "of type '" +
                containmentStack.back().field->getType()->getName() + "'";
              break;
            default:
              message = "Element '" + getElementName(element, nodeType) +
                "' is not allowed in '" +
                getElementName(containmentStack.back()) + "'";
            }

            if(containerStackIndex == -1)
            {
              warning(message + " (element ignored)");
              return;
            }

            warning(message + " (fall-through to closest '" +
                    getElementName(containmentStack[containerStackIndex]) +
                    "' established)");
          }


          Ref<NodeBase> node;
          Ref<CustomFieldBase> field;

          if(element == elem_route)
          {
            string fromNode;
            string fromField;
            string toNode;
            string toField;
            bool gotFromNode  = false;
            bool gotFromField = false;
            bool gotToNode    = false;
            bool gotToField   = false;
          
            for(int i=0; atts[i] && atts[i+1]; i+=2)
            {
              if(attr_cmp(atts[i], "fromNode", element))
              {
                gotFromNode = parseValue(atts[i+1], fromNode);
              }
              else if(attr_cmp(atts[i], "fromField", element))
              {
                gotFromField = parseValue(atts[i+1], fromField);
              }
              else if(attr_cmp(atts[i], "toNode", element))
              {
                gotToNode = parseValue(atts[i+1], toNode);
              }
              else if(attr_cmp(atts[i], "toField", element))
              {
                gotToField = parseValue(atts[i+1], toField);
              }
              else
              {
                warning("Unrecognized attribute '" + string(atts[i]) +
                        "' of element '" + getElementName(element) + "' (attribute ignored)");
              }
            }

            bool skip = false;
            if(!gotFromNode)
            {
              warning("Required attribute 'fromNode' of element '" +
                      getElementName(element) + "' is missing (element ignored)");
              skip = true;
            }
            if(!gotFromField)
            {
              warning("Required attribute 'fromField' of element '" +
                      getElementName(element) + "' is missing (element ignored)");
              skip = true;
            }
            if(!gotToNode)
            {
              warning("Required attribute 'toNode' of element '" +
                      getElementName(element) + "' is missing (element ignored)");
              skip = true;
            }
            if(!gotToField)
            {
              warning("Required attribute 'toField' of element '" +
                      getElementName(element) + "' is missing (element ignored)");
              skip = true;
            }
            if(!skip) addRoute(fromNode, fromField, toNode, toField);
          }
          else if(element == elem_proto)
          {
            warning("Element '" + getElementName(element) + "' is not supported yet (ignored)");
          }
          else if(element == elem_field)
          {
            string name;
            string accessType;
            string type;
            string use;

            bool gotName       = false;
            bool gotAccessType = false;
            bool gotType       = false;
            int  gotValue      = -1; // If >= 0 value is atts[gotValue]
            bool gotUse        = false;
          
            for(int i=0; atts[i] && atts[i+1]; i+=2)
            {
              if(attr_cmp(atts[i], "name", element))
              {
                gotName = parseValue(atts[i+1], name);
              }
              else if(attr_cmp(atts[i], "accessType", element))
              {
                gotAccessType = parseValue(atts[i+1], accessType);
              }
              else if(attr_cmp(atts[i], "type", element))
              {
                gotType = parseValue(atts[i+1], type);
              }
              else if(attr_cmp(atts[i], "value", element))
              {
                gotValue = i+1;
              }
              else if(attr_cmp(atts[i], "USE", element, true))
              {
                // This attribute is deprecated
                gotUse = parseValue(atts[i+1], use);
              }
              else
              {
                warning("Unrecognized attribute '" + string(atts[i]) +
                        "' of element '" + getElementName(element) + "' (attribute ignored)");
              }
            }

            bool isEventTarget = false;
            bool isEventSource = false;

            bool skip = false;
            if(gotName && !validateIdentifier(name))
            {
              warning("Illegal value '" + name + "' of attribute 'name' "
                      "in element 'field' (element ignored)");
              skip = true;            
            }

            if(gotAccessType)
            {
              if(Text::compareIgnoreCase("initializeOnly", accessType) == 0 ||
                 Text::compareIgnoreCase("field", accessType) == 0);
              else if(Text::compareIgnoreCase("inputOnly", accessType) == 0 ||
                      Text::compareIgnoreCase("eventIn", accessType) == 0)
                isEventTarget = true;
              else if(Text::compareIgnoreCase("outputOnly", accessType) == 0 ||
                      Text::compareIgnoreCase("eventOut", accessType) == 0)
                isEventSource = true;
              else if(Text::compareIgnoreCase("inputOutput", accessType) == 0 ||
                      Text::compareIgnoreCase("exposedField", accessType) == 0)
                isEventTarget = isEventSource = true;
              else
              {
                warning("Unrecognized attribute value '" + accessType +
                        "' of attribute 'accessType' of element 'field' "
                        "(assuming 'initializeOnly')");
                accessType = "initializeOnly";
              }

              if(!isEventTarget && !isEventSource &&
                 accessType != "initializeOnly")
                warning("Attribute value '" + accessType + "' of attribute "
                        "'accessType' of element 'field' should be spelled "
                        "'initializeOnly'");
              if(isEventTarget && !isEventSource && accessType != "inputOnly")
                warning("Attribute value '" + accessType + "' of attribute "
                        "'accessType' of element 'field' should be spelled "
                        "'inputOnly'");
              if(!isEventTarget && isEventSource && accessType != "outputOnly")
                warning("Attribute value '" + accessType + "' of attribute "
                        "'accessType' of element 'field' should be spelled "
                        "'outputOnly'");
              if(isEventTarget && isEventSource && accessType != "inputOutput")
                warning("Attribute value '" + accessType + "' of attribute "
                        "'accessType' of element 'field' should be spelled "
                        "'inputOutput'");
            }

            const FieldType *fieldType = 0;
            if(gotType)
            {
              string mappedType = type;
              map<string, string>::iterator i =
                compatibilityFieldTypeNameMap.find(type);
              if(i != compatibilityFieldTypeNameMap.end())
                mappedType = i->second;

              fieldType = FieldType::lookup(mappedType);
              if(!fieldType)
              {
                warning("Unrecognized attribute value '" + type + "' of attribute "
                        "'type' of element 'field' (element ignored)");
                skip = true;
              }
              else if(fieldType->getName() != type)
                warning("Attribute value '" + type + "' of attribute "
                        "'type' of element 'field' should be spelled "
                        "'" + fieldType->getName() + "'");
            }

            if(!gotName)
            {
              warning("Required attribute 'Name' of element '" +
                      getElementName(element) + "' is missing (element ignored)");
              skip = true;
            }
            if(!gotAccessType)
              warning("Required attribute 'accessType' of element '" +
                      getElementName(element) + "' is missing (assuming 'initializeOnly')");
            if(!gotType)
            {
              warning("Required attribute 'type' of element '" +
                      getElementName(element) + "' is missing (element ignored)");
              skip = true;
            }

            // Instantiate a field object for the element stack
            if(!skip && fieldType)
            {
              CustomFieldNode *n = dynamic_cast<CustomFieldNode *>
                (containmentStack[containerStackIndex].node.get());
              if(!n) ARCHON_THROW1(InternalException,
                                   "XML::Parser::parseStartElement: "
                                   "Custom field container was not a "
                                   "CustumFieldNode");
              int customFieldIndex = getNextCustomFieldIndex(n);

              Ref<Node> useNode;
              if(gotUse)
              {
                Ref<NodeBase> u = lookupNode(use);
                useNode = dynamic_cast<Node *>(u.get());
                if(!useNode)
                  warning("Undefined node name '" + use + "' in 'USE' "
                          "attribute of field element");
              }

              if(fieldType == SFNode::type)
                field = new NodeCustomField<Node>
                  (n, customFieldIndex, name, Node::type,
                   isEventTarget, isEventSource, useNode);
              else if(fieldType == MFNode::type)
              {
                vector<Ref<Node> > v;
                if(useNode) v.push_back(useNode);
                field = new NodeSequenceCustomField<Node>
                  (n, customFieldIndex, name, Node::type,
                   isEventTarget, isEventSource, v);
              }
              else
              {
                field = valueParsers[fieldType]->newCustomField
                  (n, customFieldIndex, name, fieldType,
                   isEventTarget, isEventSource,
                   this, gotValue >= 0 ? atts[gotValue] : 0);
                if(useNode)
                  warning("The USE attribute may not be used in field "
                          "elements with type '" + fieldType->getName() +
                          "' (attribute ignored)");
              }
            }
          }
          else if(element == elem_node)
          {
            // Is it a "reuse" element refering to an already instantiated named node?
            node = checkUseAttribute(atts, nodeType);


            /*
             * Instantiate a node of the desired type if it wasn't a
             * "reuse" element.
             */
            if(node) element = elem_use;
            else node = nodeType->instantiate(context);


            // Parse attributes
            if(element != elem_use) for(int i=0; atts[i] && atts[i+1]; i+=2)
            {
              if(Text::compareIgnoreCase(atts[i], "DEF") == 0)
              {
                if(string(atts[i]) != "DEF")
                  warning("Attribute '" + string(atts[i]) + "' should be spelled 'DEF'");

                const string name = atts[i+1];
                if(validateIdentifier(name)) addNamedNode(name, node);
                else
                  warning("Illegal value '" + name + "' of attribute 'DEF' "
                          "in element '" + nodeType->getName() + "' (attribute ignored)");
              }
              else if(Text::compareIgnoreCase(atts[i], "containerField") != 0)
              {
                const FieldBase *field = nodeType->lookupField(atts[i]);
                if(!field)
                {
                  warning("Unrecognized attribute '" + string(atts[i]) +
                          "' of element '" + nodeType->getName() + "' (attribute ignored)");
                  continue;
                }
                if(field->getType() == SFNode::type || field->getType() == MFNode::type)
                {
                  warning("Illegal node type attribute '" + string(atts[i]) +
                          "' of element '" + nodeType->getName() + "' (attribute ignored)");
                  continue;
                }

                if(field->getName() != atts[i])
                  warning("Attribute '" + string(atts[i]) + "' should be spelled '" +
                          field->getName() + "'");

                valueParsers[field->getType()]->parse(atts[i+1], node.get(), field, this);
              }
            }
          }

          stackEntry->element = element;
          stackEntry->node = node;
          stackEntry->field = field;
          stackEntry->containerField = containerField;
          stackEntry->containerStackIndex = containerStackIndex;

          if(progressive &&
             (element == elem_node || element == elem_use) &&
             !dynamic_cast<CustomFieldNode *>(node.get()))
            injectChild(stackEntry);
        }

        void startElement(const char *name, const char *atts[])
        {
          StackEntry stackEntry;
          parseStartElement(name, atts, &stackEntry);
          containmentStack.push_back(stackEntry);
          //displayStack(true);
        }

        void endElement()
        {
          StackEntry stackEntry = containmentStack.back();
          containmentStack.pop_back();
          //displayStack(false);

          // Is it a field element?
          if(stackEntry.element == elem_field)
          {
            if(!stackEntry.field) return;
            if(stackEntry.containerStackIndex < 0) return;
            Ref<CustomFieldNode> n = dynamic_cast<CustomFieldNode *>
              (containmentStack[stackEntry.containerStackIndex].node.get());
            if(!n) ARCHON_THROW1(InternalException,
                                 "XML::Parser::endElement: "
                                 "Custom field container was not a "
                                 "CustomFieldNode");

            addScriptField(n, stackEntry.field);

            return;
          }

          // Skip all non-node elements
          if(stackEntry.element != elem_node &&
             stackEntry.element != elem_use) return;

          // Inject XML/CDATA into CDATA nodes
          if(stackEntry.element == elem_node)
            if(CDATANode *n = dynamic_cast<CDATANode *>(stackEntry.node.get()))
            {
              string s = Text::trim(stackEntry.cdata);
              if(s.size()) n->handleCDATA(s, creationTimeStamp);
            }

          if(!progressive ||
             dynamic_cast<CustomFieldNode *>(stackEntry.node.get()))
            injectChild(&stackEntry);
        }

        void injectChild(StackEntry *stackEntry)
        {
          // Is it a Scene child?
          if(!stackEntry->containerField)
          {
            addRootGroupChild(dynamic_cast<ChildNode *>
                              (stackEntry->node.get()), creationTimeStamp);
            return;
          }

          // Is there room for another node in the target field? Try
          // to inject it!
          if(!containmentStack[stackEntry->containerStackIndex].node->inject
               (stackEntry->containerField, stackEntry->node, creationTimeStamp))
            warning("Element '" +
                    containmentStack[stackEntry->containerStackIndex].node->
                    getType()->getName() +
                    "' already contains a '" +
                    stackEntry->node->getType()->getName() +
                    "' (additional element ignored)");
        }

        void characterDataHandler(const char *s, int n)
        {
          StackEntry &stackEntry = containmentStack.back();
          if(dynamic_cast<const CDATANode *>(stackEntry.node.get()))
            stackEntry.cdata.append(s, n);
        }
      };

      namespace
      {
        void startElement(void *userData, const char *name, const char *atts[]) throw()
        {
          Parser *p = static_cast<Parser *>(userData);
          p->startElement(name, atts);
        }

        void endElement(void *userData, const char *) throw()
        {
          Parser *p = static_cast<Parser *>(userData);
          p->endElement();
        }

        void characterData(void *userData, const char *s, int n)
        {
          Parser *p = static_cast<Parser *>(userData);
          p->characterDataHandler(s, n);
        }

        struct XmlParserWrapper
        {
          const XML_Parser ptr;

          XmlParserWrapper(XML_Parser ptr):ptr(ptr) {}

          ~XmlParserWrapper()
          {{ // The extra scope is needed to work around gcc3.2 bug #8287
            if(ptr) XML_ParserFree(ptr);
          }}
        };
      }


      void parse(Ref<ExecutionContext> context, Ref<GroupingNode> group,
                 Ref<Stream::Reader> reader, bool progressive, Logger *logger,
                 string sourceName, ProgressTracker *progressTracker)
      {
        Ref<Server> server;
        try { server = context->server.getRef(); }
        catch(ForwardDestroyedException &) { return; }

        XmlParserWrapper p(XML_ParserCreate(0));
        XML_SetElementHandler(p.ptr, startElement, endElement);
        XML_SetCharacterDataHandler(p.ptr, characterData);

        Parser parser(context, group,
                      sourceName.empty() ? context->getBaseUri().getFile() :
                      sourceName, p.ptr, progressTracker,
                      logger ? logger : server->getLogger(),
                      server->getNextTimeStamp(), progressive);
        XML_SetUserData(p.ptr, &parser);

        const unsigned bufferSize = 1024;
        char buffer[bufferSize];

        int progress = 0;
        for(;;)
        {
          const int n = reader->read(buffer, bufferSize);
          if(!XML_Parse(p.ptr, buffer, n, n==0))
            ARCHON_THROW1(ParseException, XML_ErrorString(XML_GetErrorCode(p.ptr)));
          if(n==0) break;
          progress += n;
          if(progressTracker) progressTracker->progress(progress);
        }
      }
    }
  }
}

---