// Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
//
// You may modify, copy, and redistribute this code under the terms of
// the GNU Library Public License version 2.1, with the exception of
// the portion of clause 6a after the semicolon (aka the "obnoxious
// relink clause")

package org.xwt.util;

import java.io.Reader;
import java.io.IOException;
import java.io.EOFException;

/**
 * An Event-Driving, Non-Validating XML Parser with Namespace support.
 *
 * A subclass can implement the abstract functions for receiving details
 * about an xml file as it is parsed. To initate a parse, use the parse()
 * function. 
 *
 * <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
 * cases, the pointer current is moved along one, and the values for the
 * new element are filled into the current object.</p>
 *
 * <p>This parser supports all the unicode ranges required by the XML
 * Specification. However, it is optimised for well-formed ASCII documents.
 * Documents containing unicode Names and Attributes will take much longer
 * to process, and invalid documents (badly formed Names or invalid attributes)
 * will be run through a test on every single unicode character range before 
 * being declared invalid.</p> 
 *
 * <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 >0.</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 <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
{
    /////////////////////////////////////////////////////////////////////////////////////////////
    // XML Parser
    /////////////////////////////////////////////////////////////////////////////////////////////

    public static final int BUFFER_SIZE = 255;

    /** 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[] { '&'  };
    private static final char[] single_apos = new char[] { '\'' };
    private static final char[] single_gt   = new char[] { '>'  };
    private static final char[] single_lt   = new char[] { '<'  };
    private static final char[] single_quot = new char[] { '"'  };

    private int line;
    private int col;

    private Reader in;
    private char[] buf;
    private int    off;
    private int    len;

    private Element current;

    // used in readEntity() to process a single character without creating a new array
    private char[] singlechar = new char[1];


    public XML() { this(BUFFER_SIZE); }

    public XML(int bSize) {
        buf = new char[bSize];

        current = (Element)elements.remove(false);
        if (current == null) current = new Element();
    }


    /** Returns the line number at the beginning of the last process call. */
    public int getLine() { return line; }

    /** Returns the column number at the beginning of the last process call. */
    public int getCol()  { return col; }

    /**
     * Parse given input and call the abstract event functions.
     *
     * Careful with threading, as this function is not synchronized.
     */ 
    public final void parse(Reader reader) throws IOException, Exn {
        in  = reader;
        off = len = 0;
        line = col = 1;

        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 Exn("reached eof without closing <"+current.qName+"> element", Exn.WFC, getLine(), getCol());
                }

                if (buf[off] == '<') readTag();
                readChars(current.qName != null);
            }
        } finally { clear(); } // clean up elements
    }

    /** remove any leftover elements from the linked list and queue them */
    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] == '<'</tt> */
    private final void readTag() throws IOException, Exn {
        // Start Tag    '<' Name (S Attribute)* S? '>'
        boolean starttag  = true;

        // End Tag     '</' Name S? '>'
        boolean endtag    = false;

        // if (starttag & endtag) then: EmptyElemTag '<' Name (S Attribute)* S? '/>'

        // Position in the name of the ':' namespace prefix
        int prefix = -1;

        int namelen   = 0;

        col++; off++; len--;
        if (!buffer(1)) throw new EOFException("Unexpected EOF processing element tag");

        // work out what we can from the beginning of the tag
        char s = buf[off]; 
        if (s == '!') {
            // definitions here don't necessarily conform to xml spec (as DTDs not yet implemented)
            col++; off++; len--; 
            if (!buffer(4)) throw new EOFException("Unexpected EOF processing <! element");

            boolean bad = false;
            switch (buf[off]) {
                case '-':
                    if (buf[off+1] != '-') { bad = true; break; }
                    col += 2; off += 2; len -= 2;

                    // Comment        '<!--'      ((Char - '-') | ('-' (Char - '-')))* '-->'
                    readChars(false, "-->", false); 
                    col += 3; off += 3; len -= 3;
                    break;

                // we don't care about the following definitions

                case 'A':
                    if (!buffer(7)
                            || buf[off+1] != 'T' || buf[off+2] != 'T' || buf[off+3] != 'L'
                            || buf[off+4] != 'I' || buf[off+5] != 'S' || buf[off+6] != 'T') {
                        bad = true; break;
                    } 
                    col += 7; off += 7; len -= 7; 

                    // ATTLIST        '<!ATTLIST'   (Char* - '>') '>'
                    readChars(false, ">", true); 
                    col++; off++; len--;
                    break;
                case 'D':
                    if (!buffer(7)
                            || buf[off+1] != 'O' || buf[off+2] != 'C' || buf[off+3] != 'T'
                            || buf[off+4] != 'Y' || buf[off+5] != 'P' || buf[off+6] != 'E') {
                        bad = true; break;
                    }
                    col += 7; off += 7; len -= 7;

                    // DTD            '<!DOCTYPE'   (Char* - '>') '>'
                    readChars(false, ">", true); 
                    col++; off++; len--;
                    break; 
                case 'E':
                    if (!buffer(7)) {
                        bad = true;
                    } else if (buf[off+1] == 'L' && buf[off+2] == 'E' && buf[off+3] == 'M'
                            && buf[off+4] == 'E' && buf[off+5] == 'N' && buf[off+6] == 'T') {
                        // ELEMENT        '<!ELEMENT'   (Char* - '>') '>'
                        readChars(false, ">", true); 
                        col++; off++; len--;

                    } else if (buf[off+1] == 'N' && buf[off+2] == 'T' && buf[off+3] == 'I'
                            && buf[off+4] == 'T' && buf[off+5] == 'Y') {
                        // ENTITY         '<!ENTITY'    (Char* - '>') '>'
                        readChars(false, ">", true); 
                        col++; off++; len--;

                    } else {
                        bad = true;
                    }
                    break;

                case 'N':
                    if (!buffer(8)
                            || buf[off+1] != 'O' || buf[off+2] != 'T' || buf[off+3] != 'A' || buf[off+4] != 'T'
                            || buf[off+5] != 'I' || buf[off+6] != 'O' || buf[off+7] != 'N') {
                        bad = true; break;
                    }
                    col += 8; off += 8; len -= 8;
                    // NOTATION       '<!NOTATION'  (Char* - '>') '>'
                    readChars(false, ">", true); 
                    col++; off++; len--;

                    break;
                default: bad = true;
            }

            if (bad) throw new Exn("element tag start character is invalid", Exn.MARKUP, getLine(), getCol());

        } else if (s == '?') {
            // PI (Ignored)   '<?'  (Char* - (Char* '?>' Char*))  '?>'
            col++; off++; len--;
            readChars(false, "?>", true);
            if (!buffer(2)) throw new EOFException("Unexpected EOF at end of Processing Instruction");
            col += 2; off += 2; len -= 2;

        } else if (s == '[') {
            if (!buffer(7)
                    || buf[off+1] != 'C' || buf[off+2] != 'D' || buf[off+3] != 'A'
                    || buf[off+4] != 'T' || buf[off+5] != 'A' || buf[off+6] != '[') {
                col++; off--; len++; 
                // Conditional    '<![' (Char* - (Char* ']]>' Char*)) ']]>'
                readChars(false, "]]>", false); 
            } else {
                col += 7; off += 7; len -=7;
                // CDATA          '<![CDATA[' (Char* - (Char* ']]>' Char*))        ']]>'
                readChars(true, "]]>", false);
            } 
            col += 3; off += 3; len -= 3;
        } else {
            if (s == '/') {
                // End Tag        '</' Name S? '>'
                starttag = false; 
                endtag = true;

                col++; off++; len--;
                if (!buffer(1)) throw new EOFException("Unexpected EOF processing end tag");
                s = buf[off];
            }

            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++) {
                if (!buffer(namelen+1)) throw new EOFException("Unexpected EOF in element tag name");

                s = buf[off+namelen];

                if (S(s) || s == '>') {
                    break;
                } else if (s == '/') {
                    endtag = true;
                    break;
                } else if (s == ':' && namelen > 0 && prefix < 1) {
                    // we have a definition of the prefix range available
                    prefix = namelen; 
                } else if (!NameChar(s)) {
                    throw new Exn("element name contains invalid character", Exn.MARKUP, getLine(), getCol());
                }
            }

            // process name (based on calculated region)
            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);

            col += namelen; off += namelen; len -= namelen;

            if (starttag) {
                // 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) {
                    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.qName = qName;

                if (prefix > 0) {
                    current.prefix = current.qName.substring(0, prefix);
                    current.localName = current.qName.substring(prefix+1);
                } else {
                    current.prefix = null;
                    current.localName = current.qName;
                }

                // process attributes
                readWhitespace(); 
                if (!buffer(1)) throw new EOFException("Unexpected EOF - processing attributes part 1");
                while (buf[off] != '/' && buf[off] != '>') {
                    readAttribute();
                    if (!buffer(1)) throw new EOFException("Unexpected EOF - processing attributes part 2");
                    readWhitespace();
                }

                // work out the uri of this element
                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.getQName())) throw new Exn(
                    "end tag </"+qName+"> does not line up with start tag <"+current.getQName()+">", Exn.WFC, getLine(), getCol()
                );
            }

            // deal with whitespace
            readWhitespace(); 

            // process tag close
            if (!buffer(1)) throw new EOFException("Unexpected EOF before end of tag"); 
            if (buf[off] == '/') {
                endtag = true;
                off++; len--; col++;
            }
            if (!buffer(1)) throw new EOFException("Unexpected EOF before end of endtag"); 
            if (buf[off] == '>') {
                off++; len--; col++;
            } else {
                throw new Exn("missing '>' character from element '"+qName+"'", Exn.MARKUP, getLine(), getCol());
            }

            // send element signals
            if (starttag) startElement(current);
            if (endtag) {
                endElement(current);

                // we just closed an element, so remove it from the element 'stack'
                if (current.getParent() == null) {
                    // we just finished the root element
                    current.clear(); 
                } else {
                    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, Exn {
        int ref = 0;
        int prefix = 0;
        String n, v, p, u; // attribute name, value, prefix and uri respectively
        n = v = p = u = null;
        char s;

        // find the element name (defined in XML Spec: section 2.3)
        for (ref= 0; ; ref++) {
            if (!buffer(ref+1)) throw new EOFException("Unexpected EOF in read attribute loop part 1");

            s = buf[off+ref];

            if (s == '=' || S(s)) {
                break;
            } else if (s == ':' && ref > 0 && prefix < 1) {
                // we have a definition of the prefix range available
                prefix = ref+1;
            } else if (!NameChar(s)) {
                throw new Exn("attribute name contains invalid characters", Exn.MARKUP, getLine(), getCol());
            }
        }

        // determine prefix and key name
        if (prefix > 0) {
            p = new String(buf, off, prefix-1);
            col += prefix; off += prefix; len -= prefix; ref -= prefix;
        }
        n = new String(buf, off, ref);
        col += ref; off += ref; len -= ref;

        // find name/value divider ('=')
        readWhitespace();
        if (!buffer(1)) throw new EOFException("Unexpected EOF before attribute '=' divider");
        if (buf[off] != '=') throw new Exn("attribute name not followed by '=' sign", Exn.MARKUP, getLine(), getCol());

        col++; off++; len--;
        readWhitespace();

        if (!buffer(1)) throw new EOFException("Unexpected EOF after attribute '=' divider");

        char wrap;
        if (buf[off] == '\'' || buf[off] == '"') {
            wrap = buf[off];
        } else {
            throw new Exn("attribute '"+n+"' must have attribute wrapped in ' or \"", Exn.MARKUP, getLine(), getCol());
        }
        col++; off++; len--;

        // find the attribute value
        attval: for (ref = 0; ; ref++) {
            if (!buffer(ref+1)) throw new EOFException("Unexpected EOF in attribute value");

            if (buf[off+ref] == wrap) {
                break attval;
            } else if (buf[off+ref] == '<') {
                throw new Exn("attribute value for '"+n+"' must not contain '<'", Exn.WFC, getLine(), getCol());
            } 
        }

        v = new String(buf, off, ref);
        col += ref; off += ref; len -= ref;

        // remove end wrapper character
        col++; off++; len--;

        // process attribute
        if (p != null && p.equals("xmlns")) {
            current.addUri(n, v);
        } else if (n.equals("xmlns")) {
            if (current.getUri().equals("")) {
                current.addUri("", v);
            } else {
                current.addError(new Exn("default namespace definition repeated", Exn.NC, getLine(), getCol()));
            }
        } else {
            // find attribute uri
            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.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()
            );

            current.addAttr(n, v, u); 
        }
    }

    /** reads an entity and processes out its value. expects buf[off] == '&' */
    private final void readEntity() throws IOException, Exn {
        off++; len--;
        if (!buffer(2)) throw new EOFException("Unexpected EOF reading entity");

        boolean unknown = false;
        switch (buf[off]) {
            case '#':
                off++; len--;

                int radix;
                if (buf[off] == 'x') { off++; len--; radix = 16; } else { radix = 10; }
                int c = 0;

                // read in each char, then shift total value to the left and add the extra
                // style of loop is slightly different from all the others, as this should run a limited number of times 
                findchar: while (true) {
                    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 Exn("illegal characters in entity reference", Exn.WFC, getLine(), getCol());
                        off++; len--; col++;
                        break findchar;
                    }
                    c = (c * radix) + d;

                    off++; len--;
                }

                singlechar[0] = Character.forDigit(c, radix);
                characters(singlechar, 0, 1);
                break;

            case 'a':
                if (buffer(4) && buf[off+1] == 'm' && buf[off+2] == 'p' && buf[off+3] == ';') {
                    characters(single_amp, 0, 1); // &
                    off += 4; len -= 4; col++;
                } else if (buffer(5) && buf[off+1] == 'p' && buf[off+2] == 'o' && buf[off+3] == 's' && buf[off+4] == ';') {
                    characters(single_apos, 0, 1); // '
                    off += 5; len -= 5; col++;
                } else {
                    unknown = true;
                }
                break;

            case 'g':
                if (buffer(3) && buf[off+1] == 't' && buf[off+2] == ';') {
                    characters(single_gt, 0, 1); // >
                    off += 3; len -= 3; col++;
                } else {
                    unknown = true;
                }
                break;

            case 'l':
                if (buffer(3) && buf[off+1] == 't' && buf[off+2] == ';') {
                    characters(single_lt, 0, 1); // <
                    off += 3; len -= 3; col++;
                } else {
                    unknown = true;
                }
                break;

            case 'q':
                if (buffer(5) && buf[off+1] == 'u' && buf[off+2] == 'o' && buf[off+3] == 't' && buf[off+4] == ';') {
                    characters(single_quot, 0, 1); // "
                    off += 5; len -= 5; col++;
                } else {
                    unknown = true;
                }
                break;

            // TODO: check a parser-level Hash of defined entities
        }

        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, Exn {
        int ref;
        char[] end = match.toCharArray();

        for (boolean more = true; more;) {
            if (!buffer(1)) return;

            buf: for (ref = 0; ref < len; ref++) {
                switch (buf[off+ref]) {
                    case '\r': // windows or macos9 newline
                        // normalise and process
                        buf[off+ref] = '\n'; ref++;
                        if (p) characters(buf, off, ref);
                        off += ref; len -= ref; ref = -1;
                        line++; col = 1;

                        // windows double-char newline; skip the next char
                        if (!buffer(1)) return;
                        if (buf[off] == '\n') { off++; len--; }
                        break;

                    case '\n': // unix newline
                        ref++;
                        if (p) characters(buf, off, ref);
                        off += ref; len -= ref; ref = -1;
                        line++; col = 1;
                        break;

                    case '&':  // entity
                        if (entities) {
                            if (p) {
                                if (ref > 0) characters(buf, off, ref);
                                off += ref; len -= ref; ref = -1;
                                readEntity();
                            }
                            break;
                        }

                    default:
                        if (!buffer(ref+end.length)) continue buf;
                        for (int i=0; end.length > i; i++) if (end[i] != buf[off+ref+i]) continue buf;
                        more = false;
                        break buf;
                }
            }

            if (p && ref > 0) characters(buf, off, ref);
            off += ref; len -= ref; col += ref;
        }
    }

    /**
     * reads until a <tt><</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, Exn {
        int ref;

        for (boolean more = true; more;) {
            if (!buffer(1)) return;

            buf: for (ref = 0; ref < len; ref++) {
                switch (buf[off+ref]) {
                    case '\r': // windows or macos9 newline
                        // normalise and process
                        buf[off+ref] = '\n'; ref++;
                        if (p) characters(buf, off, ref);
                        off += ref; len -= ref; ref = -1;
                        line++; col = 1;

                        // windows double-char newline; skip the next char
                        if (!buffer(1)) return;
                        if (buf[off] == '\n') { off++; len--; }
                        break;

                    case '\n': // unix newline
                        ref++;
                        if (p) characters(buf, off, ref);
                        off += ref; len -= ref; ref = -1;
                        line++; col = 1;
                        break;

                    case '&':  // entity
                        if (p) {
                            if (ref > 0) characters(buf, off, ref);
                            off += ref; len -= ref; ref = -1;
                            readEntity();
                        }
                        break;

                    case '<':  // end of chars section
                        more = false;
                        break buf;
                }
            }

            if (p && ref > 0) characters(buf, off, ref);
            off += ref; len -= ref; col += ref;
        }
    }

    /** reads until a non-whitespace symbol is encountered */
    private final void readWhitespace() throws IOException, Exn {
        int ref;

        for (boolean more = true; more;) {
            if (!buffer(1)) return;

            buf: for (ref = 0; ref < len; ref++) {
                switch (buf[off+ref]) {
                    case '\r': // windows or macos9 newline
                        // normalise and process
                        buf[off+ref] = '\n';
                        whitespace(buf, off, ++ref);
                        off += ref; len -= ref; ref = -1;
                        line++; col = 1;

                        // windows double-char newline; skip the next char
                        if (!buffer(1)) return;
                        if (buf[off] == '\n') { off++; len--; }
                        break;

                    case '\n': // unix newline
                        whitespace(buf, off, ++ref);
                        off += ref; len -= ref; ref = -1;
                        line++; col = 1;
                        break;

                    case ' ':  // space
                    case '\t': // tab
                        break;

                    default:   // end of whitespace
                        more = false;
                        break buf;
                }
            }

            off += ref; len -= ref; col += ref;
        }
    }

    /**
     * attempt to fill the buffer.
     *
     * @param min Minimum number of characters to read (even if we have to block to do it).
     * @return return false if min can't be reached.
     */
    private final boolean buffer(int min) throws IOException {
        if (len > min) return true;

        if (buf.length - (off+len) >= min) {
            // plenty of space left on the end of the buffer
        } else if (off >= min) {
            // moving offset data to start will leave enough free space on the end
            System.arraycopy(buf, off, buf, 0, len); 
            off = 0;
        } else {
            // buffer size will have to be increased
            char[] newbuf = new char[buf.length * 2];
            System.arraycopy(buf, off, newbuf, 0, len);
            buf = newbuf;
            off = 0;
        }

        while (min > len) {
            int newlen = in.read(buf, off+len, buf.length-(off+len));
            if (newlen < 0) return false; 
            len += newlen;
        }

        return true;
    }


    /////////////////////////////////////////////////////////////////////////////////////////////
    // Abstract SAX-Like Interface
    /////////////////////////////////////////////////////////////////////////////////////////////

    /**
     * Called when the start of an element is processed.
     *
     * <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 Exn;

    /**
     * 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
     * array segment.</p>
     *
     * <p>XML.getLine() and XML.getCol() report the position at the
     * 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 Exn, 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 Exn, IOException;


    /////////////////////////////////////////////////////////////////////////////////////////////
    // Inner Classes for Parser Support
    /////////////////////////////////////////////////////////////////////////////////////////////

    /**
     * Represents an element in an XML document. Stores a reference to its
     * parent, forming a one-way linked list.
     *
     * 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 {

        private static final int DEFAULT_ATTR_SIZE = 10;

        protected Element parent = null;

        protected String uri = null;
        protected String localName = null;
        protected String qName = null;
        protected String prefix = null;

        protected Hash urimap = new Hash(3,3);

        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;

        protected Exn[] errors = new Exn[] {};


        /** Parent of current element. */
        public Element getParent() { return parent; }

        /** Qualified Name of current element.  XML Namespace Spec 14-Jan-1999 [6] */
        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 getPrefix() { return prefix; }

        /** URI of current tag. XML Namespace Spec 14-Jan-1999 section 1 */
        public String getUri() { return getUri(prefix); }

        /** 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;
        }

        /** 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);
        }

        /** Add