CharacterClassConstructor.cpp

/*
 * Copyright (C) 2008, 2009 Apple Inc. All rights reserved.
 *
 * 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 APPLE INC. ``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 APPLE INC. OR
 * CONTRIBUTORS 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 "CharacterClassConstructor.h"

#if ENABLE(WREC)

#include "pcre_internal.h"
#include <wtf/ASCIICType.h>

using namespace WTF;

namespace JSC { namespace WREC {

void CharacterClassConstructor::addSorted(Vector<UChar>& matches, UChar ch)
{
    unsigned pos = 0;
    unsigned range = matches.size();

    // binary chop, find position to insert char.
    while (range) {
        unsigned index = range >> 1;

        int val = matches[pos+index] - ch;
        if (!val)
            return;
        else if (val > 0)
            range = index;
        else {
            pos += (index+1);
            range -= (index+1);
        }
    }
    
    if (pos == matches.size())
        matches.append(ch);
    else
        matches.insert(pos, ch);
}

void CharacterClassConstructor::addSortedRange(Vector<CharacterRange>& ranges, UChar lo, UChar hi)
{
    unsigned end = ranges.size();
    
    // Simple linear scan - I doubt there are that many ranges anyway...
    // feel free to fix this with something faster (eg binary chop).
    for (unsigned i = 0; i < end; ++i) {
        // does the new range fall before the current position in the array
        if (hi < ranges[i].begin) {
            // optional optimization: concatenate appending ranges? - may not be worthwhile.
            if (hi == (ranges[i].begin - 1)) {
                ranges[i].begin = lo;
                return;
            }
            CharacterRange r = {lo, hi};
            ranges.insert(i, r);
            return;
        }
        // Okay, since we didn't hit the last case, the end of the new range is definitely at or after the begining
        // If the new range start at or before the end of the last range, then the overlap (if it starts one after the
        // end of the last range they concatenate, which is just as good.
        if (lo <= (ranges[i].end + 1)) {
            // found an intersect! we'll replace this entry in the array.
            ranges[i].begin = std::min(ranges[i].begin, lo);
            ranges[i].end = std::max(ranges[i].end, hi);

            // now check if the new range can subsume any subsequent ranges.
            unsigned next = i+1;
            // each iteration of the loop we will either remove something from the list, or break the loop.
            while (next < ranges.size()) {
                if (ranges[next].begin <= (ranges[i].end + 1)) {
                    // the next entry now overlaps / concatenates this one.
                    ranges[i].end = std::max(ranges[i].end, ranges[next].end);
                    ranges.remove(next);
                } else
                    break;
            }
            
            return;
        }
    }

    // CharacterRange comes after all existing ranges.
    CharacterRange r = {lo, hi};
    ranges.append(r);
}

void CharacterClassConstructor::put(UChar ch)
{
    // Parsing a regular expression like [a-z], we start in an initial empty state:
    //     ((m_charBuffer == -1) && !m_isPendingDash)
    // When buffer the 'a' sice it may be (and is in this case) part of a range:
    //     ((m_charBuffer != -1) && !m_isPendingDash)
    // Having parsed the hyphen we then record that the dash is also pending:
    //     ((m_charBuffer != -1) && m_isPendingDash)
    // The next change will always take us back to the initial state - either because
    // a complete range has been parsed (such as [a-z]), or because a flush is forced,
    // due to an early end in the regexp ([a-]), or a character class escape being added
    // ([a-\s]).  The fourth permutation of m_charBuffer and m_isPendingDash is not permitted.
    ASSERT(!((m_charBuffer == -1) && m_isPendingDash));

    if (m_charBuffer != -1) {
        if (m_isPendingDash) {
            // EXAMPLE: parsing [-a-c], the 'c' reaches this case - we have buffered a previous character and seen a hyphen, so this is a range.
            UChar lo = m_charBuffer;
            UChar hi = ch;
            // Reset back to the inital state.
            m_charBuffer = -1;
            m_isPendingDash = false;
            
            // This is an error, detected lazily.  Do not proceed.
            if (lo > hi) {
                m_isUpsideDown = true;
                return;
            }
            
            if (lo <= 0x7f) {
                char asciiLo = lo;
                char asciiHi = std::min(hi, (UChar)0x7f);
                addSortedRange(m_ranges, lo, asciiHi);
                
                if (m_isCaseInsensitive) {
                    if ((asciiLo <= 'Z') && (asciiHi >= 'A'))
                        addSortedRange(m_ranges, std::max(asciiLo, 'A')+('a'-'A'), std::min(asciiHi, 'Z')+('a'-'A'));
                    if ((asciiLo <= 'z') && (asciiHi >= 'a'))
                        addSortedRange(m_ranges, std::max(asciiLo, 'a')+('A'-'a'), std::min(asciiHi, 'z')+('A'-'a'));
                }
            }
            if (hi >= 0x80) {
                UChar unicodeCurr = std::max(lo, (UChar)0x80);
                addSortedRange(m_rangesUnicode, unicodeCurr, hi);
                
                if (m_isCaseInsensitive) {
                    // we're going to scan along, updating the start of the range
                    while (unicodeCurr <= hi) {
                        // Spin forwards over any characters that don't have two cases.
                        for (; jsc_pcre_ucp_othercase(unicodeCurr) == -1; ++unicodeCurr) {
                            // if this was the last character in the range, we're done.
                            if (unicodeCurr == hi)
                                return;
                        }
                        // if we fall through to here, unicodeCurr <= hi & has another case. Get the other case.
                        UChar rangeStart = unicodeCurr;
                        UChar otherCurr = jsc_pcre_ucp_othercase(unicodeCurr);
                        
                        // If unicodeCurr is not yet hi, check the next char in the range.  If it also has another case,
                        // and if it's other case value is one greater then the othercase value for the current last
                        // character included in the range, we can include next into the range.
                        while ((unicodeCurr < hi) && (jsc_pcre_ucp_othercase(unicodeCurr + 1) == (otherCurr + 1))) {
                            // increment unicodeCurr; it points to the end of the range.
                            // increment otherCurr, due to the check above other for next must be 1 greater than the currrent other value.
                            ++unicodeCurr;
                            ++otherCurr;
                        }
                        
                        // otherChar is the last in the range of other case chars, calculate offset to get back to the start.
                        addSortedRange(m_rangesUnicode, otherCurr-(unicodeCurr-rangeStart), otherCurr);
                        
                        // unicodeCurr has been added, move on to the next char.
                        ++unicodeCurr;
                    }
                }
            }
        } else if (ch == '-')
            // EXAMPLE: parsing [-a-c], the second '-' reaches this case - the hyphen is treated as potentially indicating a range.
            m_isPendingDash = true;
        else {
            // EXAMPLE: Parsing [-a-c], the 'a' reaches this case - we repace the previously buffered char with the 'a'.
            flush();
            m_charBuffer = ch;
        }
    } else
        // EXAMPLE: Parsing [-a-c], the first hyphen reaches this case - there is no buffered character
        // (the hyphen not treated as a special character in this case, same handling for any char).
        m_charBuffer = ch;
}

// When a character is added to the set we do not immediately add it to the arrays, in case it is actually defining a range.
// When we have determined the character is not used in specifing a range it is added, in a sorted fashion, to the appropriate
// array (either ascii or unicode).
// If the pattern is case insensitive we add entries for both cases.
void CharacterClassConstructor::flush()
{
    if (m_charBuffer != -1) {
        if (m_charBuffer <= 0x7f) {
            if (m_isCaseInsensitive && isASCIILower(m_charBuffer))
                addSorted(m_matches, toASCIIUpper(m_charBuffer));
            addSorted(m_matches, m_charBuffer);
            if (m_isCaseInsensitive && isASCIIUpper(m_charBuffer))
                addSorted(m_matches, toASCIILower(m_charBuffer));
        } else {
            addSorted(m_matchesUnicode, m_charBuffer);
            if (m_isCaseInsensitive) {
                int other = jsc_pcre_ucp_othercase(m_charBuffer);
                if (other != -1)
                    addSorted(m_matchesUnicode, other);
            }
        }
        m_charBuffer = -1;
    }
    
    if (m_isPendingDash) {
        addSorted(m_matches, '-');
        m_isPendingDash = false;
    }
}

void CharacterClassConstructor::append(const CharacterClass& other)
{
    // [x-\s] will add, 'x', '-', and all unicode spaces to new class (same as [x\s-]).
    // Need to check the spec, really, but think this matches PCRE behaviour.
    flush();
    
    if (other.numMatches) {
        for (size_t i = 0; i < other.numMatches; ++i)
            addSorted(m_matches, other.matches[i]);
    }
    if (other.numRanges) {
        for (size_t i = 0; i < other.numRanges; ++i)
            addSortedRange(m_ranges, other.ranges[i].begin, other.ranges[i].end);
    }
    if (other.numMatchesUnicode) {
        for (size_t i = 0; i < other.numMatchesUnicode; ++i)
            addSorted(m_matchesUnicode, other.matchesUnicode[i]);
    }
    if (other.numRangesUnicode) {
        for (size_t i = 0; i < other.numRangesUnicode; ++i)
            addSortedRange(m_rangesUnicode, other.rangesUnicode[i].begin, other.rangesUnicode[i].end);
    }
}

} } // namespace JSC::WREC

#endif // ENABLE(WREC)