xpathparser.cpp

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

/*
 * Copyright 2005 Maksim Orlovich <[e-mail]>
 * Copyright (C) 2006 Apple Computer, Inc.
 * Copyright (C) 2007 Alexey Proskuryakov <[e-mail]>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "XPathParser.h"

#if ENABLE(XPATH)

#include "ExceptionCode.h"
#include "StringHash.h"
#include "XPathEvaluator.h"
#include "XPathException.h"
#include "XPathNSResolver.h"
#include "XPathStep.h"
#include <wtf/StdLibExtras.h>

int xpathyyparse(void*);

using namespace WTF;
using namespace Unicode;

namespace WebCore {
namespace XPath {

class LocationPath;

#include "XPathGrammar.h"    

Parser* Parser::currentParser = 0;
    
enum XMLCat { NameStart, NameCont, NotPartOfName };

typedef HashMap<String, Step::Axis> AxisNamesMap;

static XMLCat charCat(UChar aChar)
{
    //### might need to add some special cases from the XML spec.

    if (aChar == '_')
        return NameStart;

    if (aChar == '.' || aChar == '-')
        return NameCont;
    CharCategory category = Unicode::category(aChar);
    if (category & (Letter_Uppercase | Letter_Lowercase | Letter_Other | Letter_Titlecase | Number_Letter))
        return NameStart;
    if (category & (Mark_NonSpacing | Mark_SpacingCombining | Mark_Enclosing | Letter_Modifier | Number_DecimalDigit))
        return NameCont;
    return NotPartOfName;
}

static void setUpAxisNamesMap(AxisNamesMap& axisNames)
{
    struct AxisName {
        const char* name;
        Step::Axis axis;
    };
    const AxisName axisNameList[] = {
        { "ancestor", Step::AncestorAxis },
        { "ancestor-or-self", Step::AncestorOrSelfAxis },
        { "attribute", Step::AttributeAxis },
        { "child", Step::ChildAxis },
        { "descendant", Step::DescendantAxis },
        { "descendant-or-self", Step::DescendantOrSelfAxis },
        { "following", Step::FollowingAxis },
        { "following-sibling", Step::FollowingSiblingAxis },
        { "namespace", Step::NamespaceAxis },
        { "parent", Step::ParentAxis },
        { "preceding", Step::PrecedingAxis },
        { "preceding-sibling", Step::PrecedingSiblingAxis },
        { "self", Step::SelfAxis }
    };
    for (unsigned i = 0; i < sizeof(axisNameList) / sizeof(axisNameList[0]); ++i)
        axisNames.set(axisNameList[i].name, axisNameList[i].axis);
}

static bool isAxisName(const String& name, Step::Axis& type)
{
    DEFINE_STATIC_LOCAL(AxisNamesMap, axisNames, ());

    if (axisNames.isEmpty())
        setUpAxisNamesMap(axisNames);

    AxisNamesMap::iterator it = axisNames.find(name);
    if (it == axisNames.end())
        return false;
    type = it->second;
    return true;
}

static bool isNodeTypeName(const String& name)
{
    DEFINE_STATIC_LOCAL(HashSet<String>, nodeTypeNames, ());
    if (nodeTypeNames.isEmpty()) {
        nodeTypeNames.add("comment");
        nodeTypeNames.add("text");
        nodeTypeNames.add("processing-instruction");
        nodeTypeNames.add("node");
    }
    return nodeTypeNames.contains(name);
}

/* Returns whether the last parsed token matches the [32] Operator rule
 * (check http://www.w3.org/TR/xpath#exprlex). Necessary to disambiguate
 * the tokens.
 */
bool Parser::isOperatorContext() const
{
    if (m_nextPos == 0)
        return false;

    switch (m_lastTokenType) {
        case AND: case OR: case MULOP:
        case '/': case SLASHSLASH: case '|': case PLUS: case MINUS:
        case EQOP: case RELOP:
        case '@': case AXISNAME:   case '(': case '[':
            return false;
        default:
            return true;
    }
}

void Parser::skipWS()
{
    while (m_nextPos < m_data.length() && isSpaceOrNewline(m_data[m_nextPos]))
        ++m_nextPos;
}

Token Parser::makeTokenAndAdvance(int code, int advance)
{
    m_nextPos += advance;
    return Token(code);
}

Token Parser::makeTokenAndAdvance(int code, NumericOp::Opcode val, int advance)
{
    m_nextPos += advance;
    return Token(code, val);
}

Token Parser::makeTokenAndAdvance(int code, EqTestOp::Opcode val, int advance)
{
    m_nextPos += advance;
    return Token(code, val);
}

// Returns next char if it's there and interesting, 0 otherwise
char Parser::peekAheadHelper()
{
    if (m_nextPos + 1 >= m_data.length())
        return 0;
    UChar next = m_data[m_nextPos + 1];
    if (next >= 0xff)
        return 0;
    return next;
}

char Parser::peekCurHelper()
{
    if (m_nextPos >= m_data.length())
        return 0;
    UChar next = m_data[m_nextPos];
    if (next >= 0xff)
        return 0;
    return next;
}

Token Parser::lexString()
{
    UChar delimiter = m_data[m_nextPos];
    int startPos = m_nextPos + 1;

    for (m_nextPos = startPos; m_nextPos < m_data.length(); ++m_nextPos) {
        if (m_data[m_nextPos] == delimiter) {
            String value = m_data.substring(startPos, m_nextPos - startPos);
            if (value.isNull())
                value = "";
            ++m_nextPos; // Consume the char.
            return Token(LITERAL, value);
        }
    }

    // Ouch, went off the end -- report error.
    return Token(XPATH_ERROR);
}

Token Parser::lexNumber()
{
    int startPos = m_nextPos;
    bool seenDot = false;

    // Go until end or a non-digits character.
    for (; m_nextPos < m_data.length(); ++m_nextPos) {
        UChar aChar = m_data[m_nextPos];
        if (aChar >= 0xff) break;

        if (aChar < '0' || aChar > '9') {
            if (aChar == '.' && !seenDot)
                seenDot = true;
            else
                break;
        }
    }

    return Token(NUMBER, m_data.substring(startPos, m_nextPos - startPos));
}

bool Parser::lexNCName(String& name)
{
    int startPos = m_nextPos;
    if (m_nextPos >= m_data.length())
        return false;

    if (charCat(m_data[m_nextPos]) != NameStart)
        return false;

    // Keep going until we get a character that's not good for names.
    for (; m_nextPos < m_data.length(); ++m_nextPos)
        if (charCat(m_data[m_nextPos]) == NotPartOfName)
            break;

    name = m_data.substring(startPos, m_nextPos - startPos);
    return true;
}

bool Parser::lexQName(String& name)
{
    String n1;
    if (!lexNCName(n1))
        return false;

    skipWS();

    // If the next character is :, what we just got it the prefix, if not,
    // it's the whole thing.
    if (peekAheadHelper() != ':') {
        name = n1;
        return true;
    }

    String n2;
    if (!lexNCName(n2))
        return false;

    name = n1 + ":" + n2;
    return true;
}

Token Parser::nextTokenInternal()
{
    skipWS();

    if (m_nextPos >= m_data.length())
        return Token(0);

    char code = peekCurHelper();
    switch (code) {
        case '(': case ')': case '[': case ']':
        case '@': case ',': case '|':
            return makeTokenAndAdvance(code);
        case '\'':
        case '\"':
            return lexString();
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
            return lexNumber();
        case '.': {
            char next = peekAheadHelper();
            if (next == '.')
                return makeTokenAndAdvance(DOTDOT, 2);
            if (next >= '0' && next <= '9')
                return lexNumber();
            return makeTokenAndAdvance('.');
        }
        case '/':
            if (peekAheadHelper() == '/')
                return makeTokenAndAdvance(SLASHSLASH, 2);
            return makeTokenAndAdvance('/');
        case '+':
            return makeTokenAndAdvance(PLUS);
        case '-':
            return makeTokenAndAdvance(MINUS);
        case '=':
            return makeTokenAndAdvance(EQOP, EqTestOp::OP_EQ);
        case '!':
            if (peekAheadHelper() == '=')
                return makeTokenAndAdvance(EQOP, EqTestOp::OP_NE, 2);
            return Token(XPATH_ERROR);
        case '<':
            if (peekAheadHelper() == '=')
                return makeTokenAndAdvance(RELOP, EqTestOp::OP_LE, 2);
            return makeTokenAndAdvance(RELOP, EqTestOp::OP_LT);
        case '>':
            if (peekAheadHelper() == '=')
                return makeTokenAndAdvance(RELOP, EqTestOp::OP_GE, 2);