From c730780164e644077bb9cb3906a6519824a67de4 Mon Sep 17 00:00:00 2001
From: david <david@xwt.org>
Date: Fri, 30 Jan 2004 07:43:12 +0000
Subject: [PATCH] 2003/12/25 08:09:21

darcs-hash:20040130074312-0c9ea-f997e84bf8771129239eedf48c94e067fab880af.gz
---
 src/org/xwt/Template.java |  146 +++++++++--------
 src/org/xwt/XMLRPC.java   |    6 +-
 src/org/xwt/XWT.java      |   12 +-
 src/org/xwt/util/Vec.java |   62 +++++---
 src/org/xwt/util/XML.java |  380 ++++++++++++++++++++++-----------------------
 5 files changed, 312 insertions(+), 294 deletions(-)

diff --git a/src/org/xwt/Template.java b/src/org/xwt/Template.java
index af84178..dbd39cc 100644
--- a/src/org/xwt/Template.java
+++ b/src/org/xwt/Template.java
@@ -179,7 +179,7 @@ public class Template {
         Template t = null;          ///< the template we're currently working on
 
         /** parse an XML input stream, building a Template tree off of <tt>root</tt> */
-        void parseit(InputStream is, Template root) throws XML.XMLException, IOException {
+        void parseit(InputStream is, Template root) throws XML.Exn, IOException {
             state = STATE_INITIAL;
             nameOfHeaderNodeBeingProcessed = null;
             nodeStack.setSize(0);
@@ -187,32 +187,37 @@ public class Template {
             parse(new InputStreamReader(is)); 
         }
 
-        public void startElement(XML.Element c) throws XML.SchemaException {
+        public void startElement(XML.Element c) throws XML.Exn {
             switch(state) {
             case STATE_INITIAL:
-                if (!"xwt".equals(c.localName)) throw new XML.SchemaException("root element was not <xwt>");
-                if (c.len != 0) throw new XML.SchemaException("root element must not have attributes");
+                if (!"xwt".equals(c.getLocalName()))
+                    throw new XML.Exn("root element was not <xwt>", XML.Exn.SCHEMA, getLine(), getCol());
+                if (c.getAttrLen() != 0)
+                    throw new XML.Exn("root element must not have attributes", XML.Exn.SCHEMA, getLine(), getCol());
                 state = STATE_IN_XWT_NODE;
                 return;
 
             case STATE_IN_XWT_NODE:
-                if (nameOfHeaderNodeBeingProcessed != null) throw new XML.SchemaException("can't nest header nodes");
-                nameOfHeaderNodeBeingProcessed = c.localName;
-                if (c.localName.equals("doc")) {
+                if (nameOfHeaderNodeBeingProcessed != null)
+                    throw new XML.Exn("can't nest header nodes", XML.Exn.SCHEMA, getLine(), getCol());
+                nameOfHeaderNodeBeingProcessed = c.getLocalName();
+                //#switch(c.getLocalName())
+                case "doc":
                     // FEATURE
-                } else if (c.localName.equals("static")) {
+                    return;
+                case "static":
                     if (t.staticscript != null)
-                        throw new XML.SchemaException("the <static> header node may not appear more than once");
-                    if (c.len > 0)
-                        throw new XML.SchemaException("the <static> node may not have attributes");
-                } else if (c.localName.equals("template")) {
+                        throw new XML.Exn("the <static> header node may only appear once", XML.Exn.SCHEMA, getLine(), getCol());
+                    if (c.getAttrLen() > 0)
+                        throw new XML.Exn("the <static> node may not have attributes", XML.Exn.SCHEMA, getLine(), getCol());
+                    return;
+                case "template":
                     t.startLine = getLine();
                     state = STATE_IN_TEMPLATE_NODE;
                     processBodyElement(c);
-                } else {
-                    throw new XML.SchemaException("unrecognized header node \"" + c.localName + "\"");
-                }
-                return;
+                    return;
+                //#end
+                throw new XML.Exn("unrecognized header node \"" + c.getLocalName() + "\"", XML.Exn.SCHEMA, getLine(), getCol());
 
             case STATE_IN_TEMPLATE_NODE:
                 // push the last node we were in onto the stack
@@ -220,66 +225,71 @@ public class Template {
                 // instantiate a new node, and set its fileName/importlist/preapply
                 Template t2 = new Template(t.r);
                 t2.startLine = getLine();
-                if (!c.localName.equals("box") && !c.localName.equals("template"))
-                    t2.preapply.addElement((c.uri == null ? "" : (c.uri + ".")) + c.localName);
+                if (!c.getLocalName().equals("box") && !c.getLocalName().equals("template"))
+                    t2.preapply.addElement((c.getUri().equals("") ? "" : (c.getUri() + ".")) + c.getLocalName());
                 // make the new node the current node
                 t = t2;
                 processBodyElement(c);
                 return;
 
             case STATE_FINISHED_TEMPLATE_NODE:
-                throw new XML.SchemaException("no elements may appear after the <template> node");
+                throw new XML.Exn("no elements may appear after the <template> node", XML.Exn.SCHEMA, getLine(), getCol());
             }
         }        
 
         private void processBodyElement(XML.Element c) {
-            Hash h = new Hash(c.len * 2, 3);
-
-            // WARNING: c.keys.length != c.len; USE c.len
-            for(int i=0; i<c.len; i++) {
-                if (c.keys[i] == null) throw new RuntimeException("XML parser returned a null key position="+i);
-                else if (c.keys[i].equals("font") && c.uris[i] != null) c.vals[i] = c.uris[i] + "." + c.vals[i];
-                else if (c.keys[i].equals("fill") && c.uris[i] != null && !c.vals[i].startsWith("#")
-                        && SVG.colors.get(c.vals[i]) == null) c.vals[i] = c.uris[i] + "." + c.vals[i];
-                else if (c.keys[i].equals("preapply")) {
-                    // process preapply and 'remove' from array
-                    String uri = c.uris[i] == null ? "" : c.uris[i] + '.';
-                    StringTokenizer tok = new StringTokenizer(c.vals[i].toString(), " ");
+            Vec keys = new Vec(c.getAttrLen());
+            Vec vals = new Vec(c.getAttrLen());
+
+            // process attributes into Vecs, dealing with any XML Namespaces in the process
+            ATTR: for (int i=0; i < c.getAttrLen(); i++) {
+                //#switch(c.getAttrKey(i))
+                case "font":
+                    keys.addElement(c.getAttrKey(i));
+                    if (c.getAttrUri(i) != null) vals.addElement(c.getAttrUri(i) + "." + c.getAttrVal(i));
+                    else vals.addElement(c.getAttrVal(i));
+                    continue ATTR;
+
+                case "fill":
+                    keys.addElement(c.getAttrKey(i));
+                    if (c.getAttrUri(i) != null && !c.getAttrVal(i).startsWith("#") && SVG.colors.get(c.getAttrVal(i)) == null)
+                        vals.addElement(c.getAttrUri(i) + "." + c.getAttrVal(i));
+                    else vals.addElement(c.getAttrVal(i));
+                    continue ATTR;
+
+                // process and do not add to box attributes
+
+                case "preapply":
+                    String uri = c.getAttrUri(i); if (!uri.equals("")) uri += ".";
+                    StringTokenizer tok = new StringTokenizer(c.getAttrVal(i).toString(), " ");
                     while(tok.hasMoreTokens()) t.preapply.addElement(uri + tok.nextToken());
+                    continue ATTR;
 
-                    if (i < c.len - 1) { // not the last attribute
-                        c.keys[i] = c.keys[c.len - 1];
-                        c.vals[i] = c.vals[c.len - 1];
-                        c.uris[i] = c.uris[c.len - 1];
-                    }
-                    c.len--; i--;
-                    continue;
-                }
-                h.put(c.keys[i], c.vals[i]);
-            }
-            t.keys = new String[h.size()];
-            t.vals = new Object[h.size()];
-
-            Vec v = new Vec(h.size(), c.keys);
-            v.sort(new Vec.CompareFunc() { public int compare(Object a, Object b) { return ((String)a).compareTo((String)b); } });
-            for(int i=0; i<h.size(); i++) {
-                if (c.keys[i].equals("thisbox")) {
-                    for(int j=i; j>0; j--) { t.keys[j] = t.keys[j - 1]; t.vals[j] = t.vals[j - 1]; }
-                    t.keys[0] = (String)v.elementAt(i);
-                    t.vals[0] = h.get(t.keys[0]);
-                } else {
-                    t.keys[i] = (String)v.elementAt(i);
-                    t.vals[i] = h.get(t.keys[i]);
-                }
+                case "id":
+                    t.id = c.getAttrVal(i).toString().intern();
+                    continue ATTR;
+                //#end
+
+                keys.addElement(c.getAttrKey(i));
+                vals.addElement(c.getAttrVal(i));
             }
 
-            for(int i=0; i<t.keys.length; i++) {
-                if (t.keys[i].equals("id")) {
-                    t.id = t.vals[i].toString().intern();
-                    t.keys[i] = null;
-                    continue;
-                }
+            if (keys.size() == 0) return;
+
+            // sort the attributes lexicographically
+            Vec.sort(keys, vals, new Vec.CompareFunc() { public int compare(Object a, Object b) {
+                return ((String)a).compareTo((String)b);
+            } });
 
+
+            // merge attributes into template
+            t.keys = new String[keys.size()];
+            t.vals = new Object[vals.size()];
+            keys.copyInto(t.keys);
+            vals.copyInto(t.vals);
+
+            // convert attributes to appropriate types and intern strings
+            for(int i=0; i<t.keys.length; i++) {
                 t.keys[i] = t.keys[i].intern();
 
                 String valString = t.vals[i].toString();
@@ -316,7 +326,7 @@ public class Template {
             return thisscript;
         }
 
-        public void endElement(XML.Element c) throws XML.SchemaException, IOException {
+        public void endElement(XML.Element c) throws XML.Exn, IOException {
             if (state == STATE_IN_XWT_NODE) {
                 if ("static".equals(nameOfHeaderNodeBeingProcessed) && t.content != null) t.staticscript = parseScript(true);
                 nameOfHeaderNodeBeingProcessed = null;
@@ -340,10 +350,10 @@ public class Template {
             }
          }
 
-        public void characters(char[] ch, int start, int length) throws XML.SchemaException {
+        public void characters(char[] ch, int start, int length) throws XML.Exn {
             // invoke the no-tab crusade
-            for (int i=0; length >i; i++) if (ch[start+i] == '\t') throw new XML.SchemaException(
-                t.fileName+ ":" + getLine() + "," + getCol() + ": tabs are not allowed in XWT files");
+            for (int i=0; length >i; i++) if (ch[start+i] == '\t')
+                throw new XML.Exn("tabs are not allowed in XWT files", XML.Exn.SCHEMA, getLine(), getCol());
 
             if ("static".equals(nameOfHeaderNodeBeingProcessed) || state == STATE_IN_TEMPLATE_NODE) {
                 if (t.content == null) {
@@ -353,12 +363,12 @@ public class Template {
 
                 t.content.append(ch, start, length);
 
-            } else if (nameOfHeaderNodeBeingProcessed != null && state != STATE_FINISHED_TEMPLATE_NODE) {
-                throw new XML.SchemaException("header node <" + nameOfHeaderNodeBeingProcessed + "> cannot have text content");
+            } else if (nameOfHeaderNodeBeingProcessed != null && state != STATE_FINISHED_TEMPLATE_NODE) { throw new XML.Exn(
+                "header node <" +nameOfHeaderNodeBeingProcessed+ "> cannot have text content", XML.Exn.SCHEMA, getLine(), getCol());
             }
         }
 
-        public void whitespace(char[] ch, int start, int length) throws XML.SchemaException { }
+        public void whitespace(char[] ch, int start, int length) throws XML.Exn { }
     }
 
     private static class PerInstantiationJSScope extends JSScope {
diff --git a/src/org/xwt/XMLRPC.java b/src/org/xwt/XMLRPC.java
index b38fdfd..a5ef850 100644
--- a/src/org/xwt/XMLRPC.java
+++ b/src/org/xwt/XMLRPC.java
@@ -77,7 +77,7 @@ class XMLRPC extends JS {
 
         public void startElement(XML.Element c) {
             content.reset();
-            //#switch(c.localName)
+            //#switch(c.getLocalName())
             case "fault": fault = true;
             case "struct": objects.setElementAt(new JS(), objects.size() - 1);
             case "array": objects.setElementAt(null, objects.size() - 1);
@@ -86,7 +86,7 @@ class XMLRPC extends JS {
         }
         
         public void endElement(XML.Element c) {
-            //#switch(c.localName)
+            //#switch(c.getLocalName())
             case "int": objects.setElementAt(new Integer(new String(content.getBuf(), 0, content.size())), objects.size() - 1);
             case "i4": objects.setElementAt(new Integer(new String(content.getBuf(), 0, content.size())), objects.size() - 1);
             case "boolean": objects.setElementAt(content.getBuf()[0] == '1' ? Boolean.TRUE : Boolean.FALSE, objects.size() - 1);
@@ -333,7 +333,7 @@ class XMLRPC extends JS {
             Scheduler.add(new Scheduler.Task() { public void perform() throws Exception { callback.unpause(e); }});
         } catch (final IOException e) {
             Scheduler.add(new Scheduler.Task() { public void perform() throws Exception { callback.unpause(new JSExn(e)); }});
-        } catch (final XML.XMLException e) {
+        } catch (final XML.Exn e) {
             Scheduler.add(new Scheduler.Task() { public void perform() throws Exception { callback.unpause(new JSExn(e)); }});
         }
     }
diff --git a/src/org/xwt/XWT.java b/src/org/xwt/XWT.java
index fe306af..43178da 100644
--- a/src/org/xwt/XWT.java
+++ b/src/org/xwt/XWT.java
@@ -243,18 +243,18 @@ public final class XWT extends JS {
     private class XMLHelper extends XML {
         Vector obStack = new Vector();
         public XMLHelper() { super(BUFFER_SIZE); }
-        public void startElement(XML.Element c) throws XML.SchemaException {
+        public void startElement(XML.Element c) throws XML.Exn {
             try {
                 JS o = new JS();
-                o.put("$name", c.localName);
-                for(int i=0; i<c.len; i++) o.put(c.keys[i], c.vals[i]);
+                o.put("$name", c.getLocalName());
+                for(int i=0; i < c.getAttrLen(); i++) o.put(c.getAttrKey(i), c.getAttrVal(i));
                 o.put("$numchildren", new Integer(0));
                 obStack.addElement(o);
             } catch (JSExn jse) {
                 throw new Error("this should never happen");
             }
         }
-        public void endElement(XML.Element c) throws XML.SchemaException {
+        public void endElement(XML.Element c) throws XML.Exn {
             try {
                 if (obStack.size() == 1) return;
                 JS me = (JS)obStack.lastElement();
@@ -267,7 +267,7 @@ public final class XWT extends JS {
                 throw new Error("this should never happen");
             }
         }
-        public void characters(char[] ch, int start, int length) throws XML.SchemaException {
+        public void characters(char[] ch, int start, int length) throws XML.Exn {
             try {
                 String s = new String(ch, start, length);
                 JS parent = (JS)obStack.lastElement();
@@ -288,7 +288,7 @@ public final class XWT extends JS {
             try { 
                 BufferedReader r = new BufferedReader(new InputStreamReader(is));
                 parse(r);
-            } catch (XML.XMLException e) {
+            } catch (XML.Exn e) {
                 throw new JSExn("error parsing XML: " + e.toString());
             } catch (IOException e) {
                 if (Log.on) Log.log(this, "IO Exception while reading from file");
diff --git a/src/org/xwt/util/Vec.java b/src/org/xwt/util/Vec.java
index e04be25..846473b 100644
--- a/src/org/xwt/util/Vec.java
+++ b/src/org/xwt/util/Vec.java
@@ -122,48 +122,62 @@ public final class Vec implements Serializable {
         store[at] = o;
         size++;
     }
-    
+
     public interface CompareFunc {
         public int compare(Object a, Object b);
     }
-    
+
     public void sort(CompareFunc c) {
-        sort(c,0,size-1);
+        sort(this, null, c, 0, size-1);
     }
-    
-    private final void swap(int a, int b) {
-        if(a != b) {
-            Object tmp = store[a];
-            store[a] = store[b];
-            store[b] = tmp;
-        }
+
+    public static void sort(Vec a, Vec b, CompareFunc c) {
+        if (b != null && a.size != b.size) throw new IllegalArgumentException("Vec a and b must be of equal size");
+        sort(a, b, c, 0, a.size-1);
     }
-    
-    private void sort(CompareFunc c, int start, int end) {
-        Object tmp;
+
+    private static final void sort(Vec a, Vec b, CompareFunc c, int start, int end) {
+        Object tmpa, tmpb = null;
         if(start >= end) return;
         if(end-start <= 6) {
             for(int i=start+1;i<=end;i++) {
-                tmp = store[i];
+                tmpa = a.store[i];
+                if (b != null) tmpb = b.store[i];
                 int j;
                 for(j=i-1;j>=start;j--) {
-                    if(c.compare(store[j],tmp) <= 0) break;
-                    store[j+1] = store[j];
+                    if(c.compare(a.store[j],tmpa) <= 0) break;
+                    a.store[j+1] = a.store[j];
+                    if (b != null) b.store[j+1] = b.store[j];
                 }
-                store[j+1] = tmp;
+                a.store[j+1] = tmpa;
+                if (b != null) b.store[j+1] = tmpb;
             }
             return;
         }
-        Object pivot = store[end];
+
+        Object pivot = a.store[end];
         int lo = start - 1;
         int hi = end;
+
         do {
-            while(c.compare(store[++lo],pivot) < 0) { }
-            while((hi > lo) && c.compare(store[--hi],pivot) > 0) { }
-            swap(lo,hi);
+            while(c.compare(a.store[++lo],pivot) < 0) { }
+            while((hi > lo) && c.compare(a.store[--hi],pivot) > 0) { }
+            swap(a, lo,hi);
+            if (b != null) swap(b, lo,hi);
         } while(lo < hi);
-        swap(lo,end);
-        sort(c,start,lo-1);
-        sort(c,lo+1,end);
+
+        swap(a, lo,end);
+        if (b != null) swap(b, lo,end);
+
+        sort(a, b, c, start, lo-1);
+        sort(a, b, c, lo+1, end);
+    }
+
+    private static final void swap(Vec vec, int a, int b) {
+        if(a != b) {
+            Object tmp = vec.store[a];
+            vec.store[a] = vec.store[b];
+            vec.store[b] = tmp;
+        }
     }
 }
diff --git a/src/org/xwt/util/XML.java b/src/org/xwt/util/XML.java
index ca1d713..8744cf4 100644
--- a/src/org/xwt/util/XML.java
+++ b/src/org/xwt/util/XML.java
@@ -18,7 +18,7 @@ import java.io.EOFException;
  * about an xml file as it is parsed. To initate a parse, use the parse()
  * function. 
  *
- * <h3>IMPLEMENTATION NOTES</h3>
+ * <h3>Implementation Notes</h3>
  * <p>As the parser traverses into an element, it adds it to the linked list
  * called <tt>elements</tt>. However, <tt>elements</tt> has been pre-filled
  * with instances of the Element inner class. So in the vast majority of
@@ -32,22 +32,20 @@ import java.io.EOFException;
  * will be run through a test on every single unicode character range before 
  * being declared invalid.</p> 
  *
- * <h3>IMPLEMENTATION RULES</h3> 
  * <ul>
  *  <li>Each time the buffer offset <tt>off</tt> is moved, the length
  *   <tt>len</tt> must be decreased.</li>
  *  <li>Each time the buffer length is decreased, it must be checked to make
  *   sure it is &gt;0.</li>
- * </ul> 
- *
- * <h3>Other Notes</h3>
- * <ul>
- *  <li><i>error</i> is defined as a Validity Constraint Violation and is recoverable</li>
- *  <li><i>fatal error</i> is defined as a Well-formedness Constraint Violation and is not recoverable</li>
+ *  <li><i>error</i> is defined as a Validity Constraint Violation and
+ *   is recoverable</li>
+ *  <li><i>fatal error</i> is defined as a Well-formedness Constraint
+ *   Violation and is not recoverable</li>
  * </ul> 
  *
  * @author David Crawshaw 
- * @see XML-Specification-1.0 http://w3.org/TR/REC-xml
+ * @see <a href="http://w3.org/TR/REC-xml">XML Specification</a> 
+ * @see <a href="http://w3.org/TR/REC-xml-names">XML Namespaces</a>
  */
 public abstract class XML
 {
@@ -57,8 +55,7 @@ public abstract class XML
 
     public static final int BUFFER_SIZE = 255;
 
-    /** static pool of XML.Element instances shared by all XML Parsers.
-     * elements in the queue have dirty prev and next references, that need cleaning before use. */
+    /** static pool of XML.Element instances shared by all XML Parsers. */
     private static final Queue elements = new Queue(30);
 
     private static final char[] single_amp  = new char[] { '&'  };
@@ -88,7 +85,6 @@ public abstract class XML
 
         current = (Element)elements.remove(false);
         if (current == null) current = new Element();
-        current.prev = current.next = null;
     }
 
 
@@ -103,36 +99,39 @@ public abstract class XML
      *
      * Careful with threading, as this function is not synchronized.
      */ 
-    public final void parse(Reader reader) throws IOException, XMLException {
+    public final void parse(Reader reader) throws IOException, Exn {
         in  = reader;
         off = len = 0;
         line = col = 1;
 
-        clean(); // clean up possible mid-way linked-list element
+        clear(); // clean up possible mid-way linked-list element
 
         try {
             // process the stream
             while (true) {
                 if (!buffer(1)) {
                     if (current.qName == null) break;
-                    throw new WFCException("reached eof without closing <"+current.qName+"> element", getLine(), getCol());
+                    throw new Exn("reached eof without closing <"+current.qName+"> element", Exn.WFC, getLine(), getCol());
                 }
 
                 if (buf[off] == '<') readTag();
                 readChars(current.qName != null);
             }
-        } finally { clean(); } // clean up elements
+        } finally { clear(); } // clean up elements
     }
 
     /** remove any leftover elements from the linked list and queue them */
-    private final void clean() {
-        while (current.prev != null) elements.append((current = current.prev).next);
-        current.next = null;
-        current.qName = null;
+    private final void clear() {
+        for (Element last = current; current.parent != null; ) {
+            current = current.parent;
+            last.clear();
+            elements.append(last);
+        }
+        current.clear();
     }
 
     /** reads in a tag. expects <tt>buf[off] == '&#60;'</tt> */
-    private final void readTag() throws IOException, XMLException {
+    private final void readTag() throws IOException, Exn {
         // Start Tag    '<' Name (S Attribute)* S? '>'
         boolean starttag  = true;
 
@@ -228,7 +227,7 @@ public abstract class XML
                 default: bad = true;
             }
 
-            if (bad) throw new MarkupException("element tag start character is invalid", getLine(), getCol());
+            if (bad) throw new Exn("element tag start character is invalid", Exn.MARKUP, getLine(), getCol());
 
         } else if (s == '?') {
             // PI (Ignored)   '<?'  (Char* - (Char* '?>' Char*))  '?>'
@@ -261,7 +260,7 @@ public abstract class XML
                 s = buf[off];
             }
 
-            if (!Name(s)) throw new MarkupException("invalid starting character in element name", getLine(), getCol()); 
+            if (!Name(s)) throw new Exn("invalid starting character in element name", Exn.MARKUP, getLine(), getCol()); 
 
             // find the element name (defined in XML Spec: section 2.3)
             for (namelen = 0; ; namelen++) {
@@ -278,12 +277,12 @@ public abstract class XML
                     // we have a definition of the prefix range available
                     prefix = namelen; 
                 } else if (!NameChar(s)) {
-                    throw new MarkupException("element name contains invalid character", getLine(), getCol());
+                    throw new Exn("element name contains invalid character", Exn.MARKUP, getLine(), getCol());
                 }
             }
 
             // process name (based on calculated region)
-            if (namelen < 1) throw new MarkupException("element name is null", getLine(), getCol()); 
+            if (namelen < 1) throw new Exn("element name is null", Exn.MARKUP, getLine(), getCol()); 
 
             // we have marked out the name region, so turn it into a string and move on
             String qName = new String(buf, off, namelen);
@@ -294,19 +293,14 @@ public abstract class XML
                 // create the in-memory element representation of this beast
                 // if current.qName == null then this is the root element we're dealing with
                 if (current.qName != null) {
-                    if (current.next == null)  {
-                        // we're at the end of the default element depth
-                        current.next = (Element)elements.remove(false);
-                        if (current.next == null) current.next = new Element();
-                        current.next.prev = current;
-                        current.next.next = null;
-                    }
-                    current = current.next;
+                    Element next = (Element)elements.remove(false);
+                    if (next == null) next = new Element();
+                    //next.clear(); // TODO: remove as elements now checked as they're added to the queue
+                    next.parent = current;
+                    current = next;
                 }
 
-                current.clear();
                 current.qName = qName;
-                current.defaultUri = current.uri = null;
 
                 if (prefix > 0) {
                     current.prefix = current.qName.substring(0, prefix);
@@ -325,27 +319,15 @@ public abstract class XML
                     readWhitespace();
                 }
 
-                // inherit namespace default uri if attribute was not provided
-                if (current.defaultUri == null) {
-                    current.defaultUri = (current.prev != null) ? current.prev.defaultUri : null;
-                }
-
                 // work out the uri of this element
-                if (current.prefix == null) {
-                    // element has no prefix, therefore is the default uri
-                    current.uri = current.defaultUri;
-                } else {
-                    // work back through the hashtables until uri is found
-                    for (Element e = current; e != null && current.uri == null; e = e.prev) {
-                        current.uri = (String)e.urimap.get(current.prefix);
-                    }
-                    if (current.uri == null) current.addError(new NCException("undefined prefix '"+current.prefix+"'", getLine(), getCol()));
-                }
+                current.uri = current.getUri(current.getPrefix()); 
+                if (current.getUri().equals("") && current.getPrefix() != null)
+                    current.addError(new Exn("undefined prefix '"+current.getPrefix()+"'", Exn.NC, getLine(), getCol()));
 
             } else {
                 // this is an end-of-element tag
-                if (!qName.equals(current.qName)) throw new WFCException(
-                    "end tag </"+qName+"> does not line up with start tag <"+current.qName+">", getLine(), getCol()
+                if (!qName.equals(current.getQName())) throw new Exn(
+                    "end tag </"+qName+"> does not line up with start tag <"+current.getQName()+">", Exn.WFC, getLine(), getCol()
                 );
             }
 
@@ -362,7 +344,7 @@ public abstract class XML
             if (buf[off] == '>') {
                 off++; len--; col++;
             } else {
-                throw new MarkupException("missing '>' character from element '"+qName+"'", getLine(), getCol());
+                throw new Exn("missing '>' character from element '"+qName+"'", Exn.MARKUP, getLine(), getCol());
             }
 
             // send element signals
@@ -371,19 +353,21 @@ public abstract class XML
                 endElement(current);
 
                 // we just closed an element, so remove it from the element 'stack'
-                if (current.prev == null) {
+                if (current.getParent() == null) {
                     // we just finished the root element
-                    current.qName = null;
+                    current.clear(); 
                 } else {
-                    elements.append((current = current.prev).next);
-                    current.next = null;
+                    Element last = current;
+                    current = current.parent;
+                    last.clear();
+                    elements.append(last);
                 }
             }
         }
     }
 
     /** reads in an attribute of an element. expects Name(buf[off]) */
-    private final void readAttribute() throws IOException, XMLException {
+    private final void readAttribute() throws IOException, Exn {
         int ref = 0;
         int prefix = 0;
         String n, v, p, u; // attribute name, value, prefix and uri respectively
@@ -402,7 +386,7 @@ public abstract class XML
                 // we have a definition of the prefix range available
                 prefix = ref+1;
             } else if (!NameChar(s)) {
-                throw new MarkupException("attribute name contains invalid characters", getLine(), getCol());
+                throw new Exn("attribute name contains invalid characters", Exn.MARKUP, getLine(), getCol());
             }
         }
 
@@ -417,7 +401,7 @@ public abstract class XML
         // find name/value divider ('=')
         readWhitespace();
         if (!buffer(1)) throw new EOFException("Unexpected EOF before attribute '=' divider");
-        if (buf[off] != '=') throw new MarkupException("attribute name not followed by '=' sign", getLine(), getCol());
+        if (buf[off] != '=') throw new Exn("attribute name not followed by '=' sign", Exn.MARKUP, getLine(), getCol());
 
         col++; off++; len--;
         readWhitespace();
@@ -428,7 +412,7 @@ public abstract class XML
         if (buf[off] == '\'' || buf[off] == '"') {
             wrap = buf[off];
         } else {
-            throw new MarkupException("attribute '"+n+"' must have attribute wrapped in ' or \"", getLine(), getCol());
+            throw new Exn("attribute '"+n+"' must have attribute wrapped in ' or \"", Exn.MARKUP, getLine(), getCol());
         }
         col++; off++; len--;
 
@@ -439,7 +423,7 @@ public abstract class XML
             if (buf[off+ref] == wrap) {
                 break attval;
             } else if (buf[off+ref] == '<') {
-                throw new WFCException("attribute value for '"+n+"' must not contain '<'", getLine(), getCol());
+                throw new Exn("attribute value for '"+n+"' must not contain '<'", Exn.WFC, getLine(), getCol());
             } 
         }
 
@@ -451,38 +435,29 @@ public abstract class XML
 
         // process attribute
         if (p != null && p.equals("xmlns")) {
-            current.urimap.put(n, v);
+            current.addUri(n, v);
         } else if (n.equals("xmlns")) {
-            if (current.defaultUri != null) {
-                current.addError(new NCException("default namespace definition repeated", getLine(), getCol()));
+            if (current.getUri().equals("")) {
+                current.addUri("", v);
             } else {
-                current.defaultUri = v;
+                current.addError(new Exn("default namespace definition repeated", Exn.NC, getLine(), getCol()));
             }
         } else {
             // find attribute uri
-            if (p == null) {
-                for (Element e = current; e != null && u == null; e = e.prev) { u = e.uri; }
-            } else {
-                for (Element e = current; e != null && u == null; e = e.prev) { u = (String)e.urimap.get(p); }
-                if (u == null) current.addError(new NCException("undefined attribute prefix '"+current.prefix+"'", getLine(), getCol()));
-            }
+            u = current.getUri(p); 
+            if (p != null && u.equals("")) current.addError(new Exn("undefined attribute prefix '"+p+"'", Exn.NC, getLine(), getCol()));
 
             // check to see if attribute is a repeat
-            for (int i=0; current.len > i; i++) if (n.equals(current.keys[i]) && u.equals(current.uris[i])) throw new WFCException(
-                "attribute name '"+n+"' may not appear more than once in the same element tag", getLine(), getCol()
+            for (int i=0; current.len > i; i++) if (n.equals(current.getAttrKey(i)) && u.equals(current.getAttrUri(i))) throw new Exn(
+                "attribute name '"+n+"' may not appear more than once in the same element tag", Exn.WFC, getLine(), getCol()
             );
 
-            // add attribute to the attribute arrays
-            if (current.len == current.keys.length) current.morekeys();
-            current.keys[current.len] = n;
-            current.vals[current.len] = v;
-            current.uris[current.len] = u;
-            current.len++;
+            current.addAttr(n, v, u); 
         }
     }
 
     /** reads an entity and processes out its value. expects buf[off] == '&amp;' */
-    private final void readEntity() throws IOException, XMLException {
+    private final void readEntity() throws IOException, Exn {
         off++; len--;
         if (!buffer(2)) throw new EOFException("Unexpected EOF reading entity");
 
@@ -501,7 +476,7 @@ public abstract class XML
                     if (!buffer(1)) throw new EOFException("Unexpected EOF reading entity");
                     int d = Character.digit(buf[off], radix);
                     if (d == -1) {
-                        if (buf[off] != ';') throw new WFCException("illegal characters in entity reference", getLine(), getCol());
+                        if (buf[off] != ';') throw new Exn("illegal characters in entity reference", Exn.WFC, getLine(), getCol());
                         off++; len--; col++;
                         break findchar;
                     }
@@ -556,11 +531,11 @@ public abstract class XML
             // TODO: check a parser-level Hash of defined entities
         }
 
-        if (unknown) throw new WFCException("unknown entity (<!ENTITY> not supported)", getLine(), getCol());
+        if (unknown) throw new Exn("unknown entity (<!ENTITY> not supported)", Exn.WFC, getLine(), getCol());
     }
 
     /** reads until the passed string is encountered. */
-    private final void readChars(boolean p, String match, boolean entities) throws IOException, XMLException {
+    private final void readChars(boolean p, String match, boolean entities) throws IOException, Exn {
         int ref;
         char[] end = match.toCharArray();
 
@@ -615,7 +590,7 @@ public abstract class XML
      * reads until a <tt>&#60;</tt> symbol is encountered
      * @param p If true call the characters(char[],int,int) funciton for the processed characters 
      */
-    private final void readChars(boolean p) throws IOException, XMLException {
+    private final void readChars(boolean p) throws IOException, Exn {
         int ref;
 
         for (boolean more = true; more;) {
@@ -662,7 +637,7 @@ public abstract class XML
     }
 
     /** reads until a non-whitespace symbol is encountered */
-    private final void readWhitespace() throws IOException, XMLException {
+    private final void readWhitespace() throws IOException, Exn {
         int ref;
 
         for (boolean more = true; more;) {
@@ -742,17 +717,13 @@ public abstract class XML
     /**
      * Called when the start of an element is processed.
      *
-     * <p>The array of Attribute names and values may be longer than the
-     * number of entries they contain, but all the entries will be
-     * packed at the top.</p>
-     *
-     * <p><b>DO NOT</b> store a reference to the attribute arrays, as
-     * they are reused by other elements.</p>
+     * <p><b>DO NOT</b> store a reference to the Element object, as
+     * they are reused by XML Parser.</p>
      */ 
-    public abstract void startElement(Element e) throws SchemaException;
+    public abstract void startElement(Element e) throws Exn;
 
     /**
-     * Represents a line of character data. 
+     * Represents up to a line of character data. 
      *
      * <p>Newlines are all normalised to the Unix \n as per the XML Spec,
      * and a newline will only appear as the last character in the passed
@@ -762,13 +733,13 @@ public abstract class XML
      * beginning of this character segment, which can be processed in a
      * line-by-line fashion due to the above newline restriction.</p>
      */
-    public abstract void characters(char[] ch, int start, int length) throws SchemaException, IOException;
+    public abstract void characters(char[] ch, int start, int length) throws Exn, IOException;
 
-    /** Represents a line of ignorable whitespace. */
-    public abstract void whitespace(char[] ch, int start, int length) throws SchemaException, IOException;
+    /** Represents up to a line of ignorable whitespace. */
+    public abstract void whitespace(char[] ch, int start, int length) throws Exn, IOException;
 
     /** Represents the end of an Element. */
-    public abstract void endElement(Element e) throws SchemaException, IOException;
+    public abstract void endElement(Element e) throws Exn, IOException;
 
 
     /////////////////////////////////////////////////////////////////////////////////////////////
@@ -776,142 +747,165 @@ public abstract class XML
     /////////////////////////////////////////////////////////////////////////////////////////////
 
     /**
-     * Used as a struct for holding information about a current element,
-     * and acts as a linked list entry.
-     *
-     * <p>Each element stores a hashtable of namespace definitions against
-     * their respective prefix, and a variable holding their default
-     * uri. If they did not specify a default uri, their
-     * parent's uri is copied in to keep up the sembelence of speedy
-     * parsing.</p>
+     * Represents an element in an XML document. Stores a reference to its
+     * parent, forming a one-way linked list.
      *
-     * <h3>SLOWEST PART OF THE XML PARSER</h3> 
-     * <p>To implement the Namespace Specification exactly, we have to
-     * store prefix mappings for elements away from its parents and
-     * siblings. This means if a child of a child of-a child uses
-     * a prefix defined in the root, we have to search each Hashtable
-     * in each Element until we get to the root.</p> 
-     *
-     * <p>Unfortunetally, every other solution I can think of requires
-     * more work than this one, shifted to different parts of the
-     * parser.</p>
+     * Element objects are reused, so client code making use of them must
+     * drop their references after the specific element process function
+     * has returned.
      */
-    public static final class Element
-    {
-        public Element next, prev;
+    public static final class Element {
 
-        /** A hashtable of all namespace prefixes that are defined by this element. */
-        public Hash urimap;
+        private static final int DEFAULT_ATTR_SIZE = 10;
 
-        /** An array of attribute names. */
-        public String[] keys;
+        protected Element parent = null;
 
-        /** An array of attribute values. */
-        public String[] vals;
-
-        /** An array of attribute uris. */
-        public String[] uris;
+        protected String uri = null;
+        protected String localName = null;
+        protected String qName = null;
+        protected String prefix = null;
 
-        /** An array of non-fatal errors related to this element. */
-        public XMLException[] errors;
+        protected Hash urimap = new Hash(3,3);
 
-        /** Current number of attributes in the <tt>keys</tt> and <tt>vals</tt> arrays. */
-        public int len;
+        protected String[] keys = new String[DEFAULT_ATTR_SIZE];
+        protected String[] vals = new String[DEFAULT_ATTR_SIZE];
+        protected String[] uris = new String[DEFAULT_ATTR_SIZE];
+        protected int len = 0;
 
-        /** Default URI for this element and its children with no prefix. */
-        public String defaultUri;
+        protected Exn[] errors = new Exn[] {};
 
-        /** URI of current tag. XML Namespace Spec 14-Jan-1999 section 1 */
-        public String uri;
 
-        /** LocalPart of current element. XML Namespace Spec 14-Jan-1999 [8] */
-        public String localName;
+        /** Parent of current element. */
+        public Element getParent() { return parent; }
 
         /** Qualified Name of current element.  XML Namespace Spec 14-Jan-1999 [6] */
-        public String qName;
+        public String getQName() { return qName; }
+
+        /** LocalPart of current element. XML Namespace Spec 14-Jan-1999 [8] */
+        public String getLocalName() { return localName; }
 
         /** Prefix of current element. Substring of qName. XML Namespace Spec 14-Jan-1999 [7] */
-        public String prefix;
-
-        public Element() {
-            defaultUri = uri = prefix = localName = qName = null;
-            urimap = new Hash(3,3);
-            keys = new String[10];
-            vals = new String[10];
-            uris = new String[10];
-            errors = new XMLException[] {};
-            len = 0;
+        public String getPrefix() { return prefix; }
+
+        /** URI of current tag. XML Namespace Spec 14-Jan-1999 section 1 */
+        public String getUri() { return getUri(null); }
+
+        /** URI of a given prefix. Never returns null, instead gives "". */
+        public String getUri(String p) {
+            String ret = null;
+            for (Element e = this; e != null && ret == null; e = e.getParent()) {
+                ret = (String)e.urimap.get(p == null ? "" : p);
+            }
+            return ret == null ? "" : ret;
         }
 
-        /** increase the size of the attributes arrays */
-        void morekeys() {
-            String[] newkeys = new String[keys.length+5];
-            String[] newvals = new String[vals.length+5];
-            String[] newuris = new String[uris.length+5];
-            System.arraycopy(keys, 0, newkeys, 0, keys.length);
-            System.arraycopy(vals, 0, newvals, 0, vals.length);
-            System.arraycopy(uris, 0, newuris, 0, uris.length);
-            keys = newkeys; vals = newvals; uris = newuris;
+        /** An array of attribute names. */
+        public String getAttrKey(int pos) { return len > pos ? keys[pos] : null; }
+
+        /** An array of attribute values. */
+        public String getAttrVal(int pos) { return len > pos ? vals[pos] : null; }
+
+        /** An array of attribute uris. */
+        public String getAttrUri(int pos) { return len > pos ? uris[pos] : null; }
+
+        /** Current number of attributes in the element. */
+        public int getAttrLen() { return len; }
+
+        /** An array of non-fatal errors related to this element. */
+        public Exn[] getErrors() { return errors; }
+
+
+        protected Element() { }
+
+        /** Add (replace if exists in current element) a Namespace prefix/uri map. */
+        protected void addUri(String name, String value) {
+            urimap.put(name, value);
         }
 
-        /** empty out the arrays */
-        void clear() {
-            if (keys.length != vals.length || vals.length != uris.length) {
-                keys = new String[10]; vals = new String[10]; uris = new String[10];
-            } else {
-                for (int i=0; keys.length > i; i++) { keys[i] = null; vals[i] = null; uris[i] = null; }; len = 0;
+        /** Add an attribute. */
+        protected void addAttr(String key, String val, String uri) {
+            if (len == keys.length) {
+                // increase the size of the attributes arrays
+                String[] newkeys = new String[keys.length*2];
+                String[] newvals = new String[vals.length*2];
+                String[] newuris = new String[uris.length*2];
+                System.arraycopy(keys, 0, newkeys, 0, keys.length);
+                System.arraycopy(vals, 0, newvals, 0, vals.length);
+                System.arraycopy(uris, 0, newuris, 0, uris.length);
+                keys = newkeys; vals = newvals; uris = newuris;
             }
-            errors = new XMLException[] {};
+
+            keys[len] = key;
+            vals[len] = val;
+            uris[len] = uri;
+            len++;
         }
 
-        /** add an error to the errors array */
-        void addError(XMLException e) {
+        /** Add an error. */
+        protected void addError(Exn e) {
             // it doesn't really matter about continually expanding the array, as this case is quite rare
-            XMLException[] newe = new XMLException[errors.length+1];
+            Exn[] newe = new Exn[errors.length+1];
             System.arraycopy(errors, 0, newe, 0, errors.length);
             newe[errors.length] = e;
             errors = newe;
         }
+
+        /** Empty out all the data from the Element. */
+        protected void clear() {
+            parent = null;
+            uri = localName = qName = prefix = null;
+            urimap.clear();
+
+            if (keys.length != vals.length || vals.length != uris.length) {
+                keys = new String[DEFAULT_ATTR_SIZE];
+                vals = new String[DEFAULT_ATTR_SIZE];
+                uris = new String[DEFAULT_ATTR_SIZE];
+            } else {
+                for (int i=0; keys.length > i; i++) { keys[i] = null; vals[i] = null; uris[i] = null; };
+            }
+            len = 0;
+
+            errors = new Exn[] {};
+        }
     }
 
     /** Parse or Structural Error */
-    public static class XMLException extends Exception
-    {
+    public static class Exn extends Exception {
+        /** Violation of Markup restrictions in XML Specification - Fatal Error */
+        public static final int MARKUP = 1;
+
+        /** Well-Formedness Constraint Violation - Fatal Error */
+        public static final int WFC = 2;
+
+        /** Namespace Constraint Violation - Recoverable Error */
+        public static final int NC = 3;
+
+        /** Schema Violation - Fatal Error */
+        public static final int SCHEMA = 4;
+
+        private String error;
+        private int type;
         private int line;
         private int col;
-        private String error;
 
-        public XMLException(String e) { this(e, -1, -1); }
+        public Exn(String e) { this(e, MARKUP, -1, -1); }
 
-        public XMLException(String e, int l, int c) {
+        public Exn(String e, int type, int line, int col) {
             this.error = e;
-            this.line  = l;
-            this.col   = c;
+            this.type  = type;
+            this.line  = line;
+            this.col   = col;
         }
 
-        public int getLine()     { return this.line;  }
-        public int getCol()      { return this.col;   }
+        public int getType() { return this.type; }
+        public int getLine() { return this.line; }
+        public int getCol()  { return this.col;  }
         public String getMessage() { return this.error; }
     }
 
-    /** Violation of Markup restrictions in XML Specification - Fatal Error */
-    public static class MarkupException extends XMLException { public MarkupException(String e, int l, int c) { super(e,l,c); } }
-
-    /** Well-Formedness Constraint Violation - Fatal Error */
-    public static final class WFCException extends MarkupException { public WFCException(String e, int l, int c) { super(e,l,c); } }
-
-    /** Namespace Constraint Violation - Recoverable Error */
-    public static final class NCException extends XMLException { public NCException(String e, int l, int c) { super(e,l,c); } }
-
-    /** Schema Violation - Fatal Error */
-    public static class SchemaException extends XMLException {
-        public SchemaException(String e) { this(e, -1, -1); }
-        public SchemaException(String e, int l, int c) { super(e,l,c); }
-    }
-
 
     /////////////////////////////////////////////////////////////////////////////////////////////
-    // Static Support JSFunctions for the XML Specification 
+    // Static Support Functions for the XML Specification 
     /////////////////////////////////////////////////////////////////////////////////////////////
  
     // attempt to avoid these functions unless you *expect* the input to fall in the given range.
-- 
1.7.10.4