| 0,0 → 1,671 |
|---|
| /* |
| * input 2072160977 bytes; AMD Athlon 3100+, disk speed 38.0 MB/s |
| * 59.18s user 9.77s system 92% cpu 1:14.72 total; RES 9420K (empty java - 8200K) |
| */ |
| import java.io.*; |
| |
| public class XmlParser |
| { |
| public static void main(String[] args) |
| throws Exception |
| { |
| if(args.length < 1) { |
| System.err.println("Need file name as parameter"); |
| return; |
| } |
| |
| long startTime = System.nanoTime(); |
| |
| FileInputStream in = new FileInputStream(args[0]); |
| |
| try { |
| XmlDocument doc = new XmlDocument(); |
| |
| doc.parse(in); |
| } |
| catch(XmlException ex) { |
| System.out.println(ex); |
| } |
| finally { |
| in.close(); |
| } |
| |
| System.err.println("Elapsed: " + (System.nanoTime() - startTime) / 1000000 + "ms"); |
| } |
| } |
| |
| // -------------------------------------------------------------------------------------------------------------------- |
| class XmlException |
| extends Exception |
| { |
| static final long serialVersionUID = 1; |
| |
| private long line; |
| private long linePos; |
| |
| public XmlException(String message, long line, long linePos) |
| { |
| super(message); |
| |
| this.line = line; |
| this.linePos = linePos; |
| } |
| |
| public long getLine() { return line; } |
| |
| public long getLinePos() { return linePos; } |
| |
| public String toString() |
| { |
| return "Error: " + getMessage() + " at " + line + ":" + linePos; |
| } |
| } |
| |
| // -------------------------------------------------------------------------------------------------------------------- |
| class XmlSelection |
| { |
| public long begin; |
| public long end; |
| |
| public long getLength() { return end - begin; } |
| } |
| |
| // -------------------------------------------------------------------------------------------------------------------- |
| class XmlElement |
| { |
| public boolean isEmpty = false; |
| } |
| |
| // -------------------------------------------------------------------------------------------------------------------- |
| class XmlBuffer |
| { |
| private InputStream in; |
| private byte[] buf = new byte[2048]; // (buf.length % 16 == 0) |
| private int len; |
| private int pos; |
| private long offset; |
| private int marked = -1; |
| |
| public XmlBuffer(InputStream in) |
| { |
| if(buf.length % 16 != 0) { |
| throw new RuntimeException("wrong buffer size: " + buf.length); |
| } |
| |
| this.in = in; |
| this.len = 0; |
| this.pos = 0; |
| this.offset = 0; |
| } |
| |
| public byte cur() |
| throws XmlException, IOException |
| { |
| if(pos >= len) { |
| if(!ensureNext(1)) return 0; |
| } |
| |
| return buf[pos]; |
| } |
| |
| public byte at(int n) |
| throws XmlException, IOException |
| { |
| if(pos + n >= len) { |
| if(!ensureNext(n+1)) return 0; |
| } |
| |
| return buf[pos + n]; |
| } |
| |
| public void toNext() |
| { |
| ++pos; |
| } |
| |
| public boolean isEnd() |
| throws XmlException, IOException |
| { |
| return (pos >= len && !ensureNext(1)); |
| } |
| |
| public void skip(int n) |
| { |
| pos += n; |
| } |
| |
| public long getOffset() |
| { |
| return offset; |
| } |
| |
| public int getPosition() |
| { |
| return pos; |
| } |
| |
| public long getAbsPosition() |
| { |
| return (offset + pos); |
| } |
| |
| public void mark() |
| { |
| marked = pos; |
| } |
| |
| public void reset() |
| { |
| if(marked < 0) { |
| throw new RuntimeException("no position saved"); |
| } |
| else { |
| pos = marked; |
| marked = -1; |
| } |
| } |
| |
| public boolean ensureNext(int count) |
| throws IOException |
| { |
| if(pos + count >= len) { |
| //log("ensureNext start " + pos + " " + count); |
| if(len == 0) { |
| // read full buffer at begin |
| len = in.read(buf); |
| pos = 0; |
| } |
| else if(len < buf.length) { |
| // we could not fill full buffer last time - no more data |
| return false; |
| } |
| else { |
| // move last 1/16 of data to begin, fill rest with new data |
| System.arraycopy(buf, buf.length / 16 * 15, buf, 0, buf.length / 16); |
| int read = in.read(buf, buf.length / 16, buf.length / 16 * 15); |
| len = buf.length / 16 + read; |
| pos -= buf.length / 16 * 15; |
| if(marked >= 0) { |
| marked -= buf.length / 16 * 15; |
| if(marked < 0) marked = -1; |
| } |
| offset += buf.length / 16 * 15; |
| } |
| |
| return (pos + count < len); |
| } |
| else { |
| return true; |
| } |
| } |
| |
| public String toString(long begin, int length) |
| throws IOException |
| { |
| return new String(buf, (int)(begin - offset), length, "UTF-8"); |
| } |
| } |
| |
| // -------------------------------------------------------------------------------------------------------------------- |
| class XmlDocument |
| { |
| private XmlBuffer buf; |
| private long line; |
| private long linePos; |
| |
| public void parse(InputStream in) |
| throws XmlException, IOException |
| { |
| this.buf = new XmlBuffer(in); |
| this.line = 1; |
| this.linePos = 0; |
| |
| if(parseProlog()) { |
| parseElement(); |
| |
| while(parseMisc()); |
| /* |
| if(this.pos < this.len) throwException("trash at end of text"); |
| */ |
| } |
| } |
| |
| private void throwException(String message) |
| throws XmlException, IOException |
| { |
| throw new XmlException(message, line, /*linePos*/ buf.getAbsPosition()); |
| } |
| |
| private void log(String message) |
| { |
| System.out.println(message); |
| } |
| |
| private String toString(XmlSelection sel) |
| throws IOException |
| { |
| return buf.toString(sel.begin, (int)sel.getLength()); |
| } |
| |
| private void saveSelBegin(XmlSelection sel) |
| { |
| sel.begin = buf.getAbsPosition(); |
| } |
| |
| private void saveSelEnd(XmlSelection sel) |
| { |
| sel.end = buf.getAbsPosition(); |
| } |
| |
| private boolean parseProlog() |
| throws XmlException, IOException |
| { |
| parseDecl(); |
| while(parseMisc()); |
| if(parseDoctype()) { |
| while(parseMisc()); |
| } |
| |
| return true; |
| } |
| |
| private boolean skipSpaces() |
| throws XmlException, IOException |
| { |
| //log("skipSpaces begin " + bufPos); |
| boolean found = false; |
| |
| for(;;) { |
| byte c = buf.cur(); |
| if(c == 0) { |
| break; |
| } |
| else if(c == ' ' || c == '\t' || c == '\n' || c == '\r') { |
| found = true; |
| buf.toNext(); |
| } |
| else { |
| break; |
| } |
| } |
| |
| //log("skipSpaces " + found + " " + bufPos); |
| return found; |
| } |
| |
| private boolean parseDecl() |
| throws XmlException, IOException |
| { |
| //log("parseDecl begin " + bufPos); |
| |
| // begin |
| if(!testChar('<') || !testChar('?') || !testChar('x') |
| || !testChar('m') || !testChar('l')) |
| { |
| //log("parseDecl no 'xml' " + bufPos); |
| return false; |
| } |
| |
| // attributes |
| XmlSelection selName = new XmlSelection(); |
| XmlSelection selValue = new XmlSelection(); |
| for(;;) { |
| if(!skipSpaces()) break; |
| if(!parseAttribute(selName, selValue)) break; |
| } |
| |
| // end |
| if(!testChar('?') || !testChar('>')) { |
| throwException("end of XML declaration expected"); |
| } |
| |
| //log("parseDecl ok " + bufPos); |
| return true; |
| } |
| |
| private boolean parseDoctype() |
| throws XmlException, IOException |
| { |
| // FIXME not implemented |
| |
| return true; |
| } |
| |
| private boolean parseName(XmlSelection sel) |
| throws XmlException, IOException |
| { |
| //log("parseName begin " + bufPos); |
| saveSelBegin(sel); |
| |
| byte c = buf.cur(); |
| if(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') || c == '_' || c == ':') { |
| buf.toNext(); |
| } |
| else { |
| //log("parseName not a name " + bufPos); |
| return false; |
| } |
| |
| for(;;) { |
| if(buf.isEnd()) { |
| throwException("unexpected EoF"); |
| } |
| |
| c = buf.cur(); |
| if(('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z') || ('0' <= c && c <= '9') |
| || c == '.' || c == '-' || c == '_' || c == ':') |
| { |
| buf.toNext(); |
| } |
| else { |
| break; |
| } |
| } |
| saveSelEnd(sel); |
| |
| //log("parseName ok " + bufPos); |
| return true; |
| } |
| |
| private boolean testChar(char c) |
| throws XmlException, IOException |
| { |
| if(buf.cur() != c) { |
| return false; |
| } |
| else { |
| buf.toNext(); |
| return true; |
| } |
| } |
| |
| private boolean parseAttribute(XmlSelection selName, XmlSelection selValue) |
| throws XmlException, IOException |
| { |
| //log("parseAttribute begin " + bufPos); |
| // name |
| buf.mark(); |
| if(!parseName(selName)) { |
| //log("parseAttribute no name " + bufPos); |
| buf.reset(); |
| return false; |
| } |
| |
| // eq |
| skipSpaces(); |
| if(!testChar('=')) { |
| throwException("equal sign expected"); |
| } |
| skipSpaces(); |
| |
| // FIXME allow 'Reference' here |
| |
| // value |
| if(!testChar('"')) { |
| throwException("quoted string expected"); |
| } |
| |
| saveSelBegin(selValue); |
| for(;; buf.toNext()) { |
| if(buf.isEnd()) { |
| throwException("unexpected EoF"); |
| } |
| |
| byte c = buf.cur(); |
| if(c == '<' || c == '&' || c == '"') { |
| break; |
| } |
| } |
| saveSelEnd(selValue); |
| |
| if(!testChar('"')) { |
| throwException("end of quoted string expected"); |
| } |
| |
| // FIXME check '[WFC: No External Entity References]' |
| |
| //log("parseAttribute ok " + bufPos); |
| return true; |
| } |
| |
| private boolean parseMisc() |
| throws XmlException, IOException |
| { |
| //log("parseMisc begin " + bufPos); |
| if(parseComment()) { |
| //log("parseMisc comment ok " + bufPos); |
| return true; |
| } |
| else if(parseProcessInstruction()) { |
| //log("parseMisc pi ok " + bufPos); |
| return true; |
| } |
| else if(skipSpaces()) { |
| //log("parseMisc spaces ok " + bufPos); |
| return true; |
| } |
| else { |
| //log("parseMisc false " + bufPos); |
| return false; |
| } |
| } |
| |
| private boolean parseComment() |
| throws XmlException, IOException |
| { |
| //log("parseComment begin " + bufPos); |
| if(buf.at(0) != '<' || buf.at(1) != '!' || buf.at(2) != '-' || buf.at(3) != '-') { |
| //log("parseComment no signature " + bufPos); |
| return false; |
| } |
| |
| buf.skip(4); |
| for(;; buf.toNext()) { |
| if(buf.isEnd()) { |
| throwException("unexpected EoF"); |
| } |
| |
| if(buf.at(0) == '-' && buf.at(1) == '-') { |
| if(buf.at(2) == '>') { |
| buf.skip(3); |
| //log("parseComment ok " + bufPos); |
| return true; |
| } |
| else { |
| throwException("Sequence '--' is not allowed in comment"); |
| } |
| } |
| } |
| } |
| |
| private boolean parseProcessInstruction() |
| throws XmlException, IOException |
| { |
| if(buf.at(0) != '<' || buf.at(1) != '?') { |
| return false; |
| } |
| |
| buf.skip(2); |
| for(;; buf.toNext()) { |
| if(buf.isEnd()) { |
| throwException("unexpected EoF"); |
| } |
| |
| if(buf.at(0) == '?' && buf.at(1) == '>') { |
| buf.skip(2); |
| return true; |
| } |
| } |
| } |
| |
| private XmlElement parseElement() |
| throws XmlException, IOException |
| { |
| //log("parseElement begin " + bufPos); |
| |
| XmlElement element = new XmlElement(); |
| |
| if(!parseStartTag(element)) { |
| //log("parseElement no start tag " + bufPos); |
| return null; |
| } |
| |
| if(!element.isEmpty) { |
| if(!parseTagContent(element)) { |
| throwException("cannot parse tag content"); |
| } |
| |
| XmlSelection selEndName = new XmlSelection(); |
| parseEndTag(selEndName); |
| |
| //if(element.name != selEndName |
| // throwException("tag names do not match"); |
| } |
| |
| //log("parseElement ok " + bufPos); |
| return element; |
| } |
| |
| private boolean parseStartTag(XmlElement element) |
| throws XmlException, IOException |
| { |
| //log("parseStartTag begin " + bufPos); |
| // begin |
| if(!testChar('<')) { |
| //log("parseStartTag no signature " + bufPos); |
| return false; |
| } |
| |
| // name |
| buf.mark(); |
| XmlSelection sel = new XmlSelection(); |
| if(!parseName(sel)) { |
| buf.reset(); |
| return false; |
| } |
| //System.out.print("[" + toString(sel) + "]"); |
| |
| // attributes |
| XmlSelection selName = new XmlSelection(); |
| XmlSelection selValue = new XmlSelection(); |
| for(;;) { |
| if(!skipSpaces()) break; |
| if(!parseAttribute(selName, selValue)) break; |
| //System.out.print(" [" + toString(selName) + "]=[" + toString(selValue) + "]"); |
| } |
| //System.out.println(); |
| |
| // end |
| element.isEmpty = testChar('/'); |
| if(!testChar('>')) { |
| throwException("end of tag expected"); |
| } |
| |
| //log("parseStartTag ok " + bufPos); |
| return true; |
| } |
| |
| private void parseEndTag(XmlSelection sel) |
| throws XmlException, IOException |
| { |
| //log("parseEndTag begin " + bufPos); |
| // begin |
| if(!testChar('<') || !testChar('/')) { |
| throwException("cannot find tag end"); |
| } |
| |
| // name |
| if(!parseName(sel)) { |
| throwException("tag name expected"); |
| } |
| |
| // spaces |
| skipSpaces(); |
| |
| // end |
| if(!testChar('>')) { |
| throwException("end of tag expected"); |
| } |
| |
| //log("parseEndTag ok " + bufPos); |
| } |
| |
| private boolean parseTagContent(XmlElement element) |
| throws XmlException, IOException |
| { |
| //log("parseTagContent begin " + bufPos); |
| XmlSelection sel = new XmlSelection(); |
| for(;;) { |
| if(buf.isEnd()) { |
| throwException("unexpected EoF"); |
| } |
| if(buf.at(0) == '<' && buf.at(1) == '/') break; |
| |
| if(parseElement() != null) { |
| } |
| else if(parseComment()) { |
| } |
| else if(parseCData(sel)) { |
| } |
| else if(parseProcessInstruction()) { |
| } |
| else if(parseCharData(sel)) { |
| } |
| |
| // FIXME allow 'Reference' here |
| } |
| |
| //log("parseTagContent ok " + bufPos); |
| return true; |
| } |
| |
| // FIXME not fully conform the standard |
| private boolean parseCharData(XmlSelection sel) |
| throws XmlException, IOException |
| { |
| //log("parseCharData begin " + bufPos); |
| boolean found = false; |
| saveSelBegin(sel); |
| |
| for(;; buf.toNext()) { |
| byte c = buf.cur(); |
| if(c == 0 || c == '<') { |
| break; |
| } |
| |
| found = true; |
| } |
| |
| //log("parseCharData " + found + " " + bufPos); |
| saveSelEnd(sel); |
| return found; |
| } |
| |
| private boolean parseCData(XmlSelection sel) |
| throws XmlException, IOException |
| { |
| if(buf.at(0) != '<' || buf.at(1) != '!' |
| || buf.at(2) != '[' || buf.at(3) != 'C' |
| || buf.at(4) != 'D' || buf.at(5) != 'A' |
| || buf.at(6) != 'T' || buf.at(7) != 'A' |
| || buf.at(8) != '[') |
| { |
| return false; |
| } |
| |
| buf.skip(9); |
| saveSelBegin(sel); |
| |
| for(;; buf.toNext()) { |
| if(buf.isEnd()) { |
| throwException("unexpected EoF"); |
| } |
| |
| if(buf.at(0) == ']' && buf.at(1) == ']' && buf.at(2) == '>') { |
| saveSelEnd(sel); |
| buf.skip(3); |
| return true; |
| } |
| } |
| } |
| } |