src/third_party/WebKit/Source/platform/text/SegmentedString.h

   1 /*
   2     Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   3
   4     This library is free software; you can redistribute it and/or
   5     modify it under the terms of the GNU Library General Public
   6     License as published by the Free Software Foundation; either
   7     version 2 of the License, or (at your option) any later version.
   8
   9     This library is distributed in the hope that it will be useful,
  10     but WITHOUT ANY WARRANTY; without even the implied warranty of
  11     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12     Library General Public License for more details.
  13
  14     You should have received a copy of the GNU Library General Public License
  15     along with this library; see the file COPYING.LIB.  If not, write to
  16     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17     Boston, MA 02110-1301, USA.
  18 */
  19
  20 #ifndef SegmentedString_h
  21 #define SegmentedString_h
  22
  23 #include "platform/PlatformExport.h"
  24 #include "wtf/Deque.h"
  25 #include "wtf/text/StringBuilder.h"
  26 #include "wtf/text/TextPosition.h"
  27 #include "wtf/text/WTFString.h"
  28
  29 namespace blink {
  30
  31 class SegmentedString;
  32
  33 class PLATFORM_EXPORT SegmentedSubstring {
  34 public:
  35     SegmentedSubstring()
  36         : m_length(0)
  37         , m_doNotExcludeLineNumbers(true)
  38         , m_is8Bit(false)
  39     {
  40         m_data.string16Ptr = 0;
  41     }
  42
  43     SegmentedSubstring(const String& str)
  44         : m_length(str.length())
  45         , m_doNotExcludeLineNumbers(true)
  46         , m_string(str)
  47     {
  48         if (m_length) {
  49             if (m_string.is8Bit()) {
  50                 m_is8Bit = true;
  51                 m_data.string8Ptr = m_string.characters8();
  52             } else {
  53                 m_is8Bit = false;
  54                 m_data.string16Ptr = m_string.characters16();
  55             }
  56         } else {
  57             m_is8Bit = false;
  58         }
  59     }
  60
  61     void clear() { m_length = 0; m_data.string16Ptr = 0; m_is8Bit = false;}
  62
  63     bool is8Bit() { return m_is8Bit; }
  64
  65     bool excludeLineNumbers() const { return !m_doNotExcludeLineNumbers; }
  66     bool doNotExcludeLineNumbers() const { return m_doNotExcludeLineNumbers; }
  67
  68     void setExcludeLineNumbers() { m_doNotExcludeLineNumbers = false; }
  69
  70     int numberOfCharactersConsumed() const { return m_string.length() - m_length; }
  71
  72     void appendTo(StringBuilder& builder) const
  73     {
  74         int offset = m_string.length() - m_length;
  75
  76         if (!offset) {
  77             if (m_length)
  78                 builder.append(m_string);
  79         } else {
  80             builder.append(m_string.substring(offset, m_length));
  81         }
  82     }
  83
  84     UChar getCurrentChar8()
  85     {
  86         return *m_data.string8Ptr;
  87     }
  88
  89     UChar getCurrentChar16()
  90     {
  91         return m_data.string16Ptr ? *m_data.string16Ptr : 0;
  92     }
  93
  94     UChar incrementAndGetCurrentChar8()
  95     {
  96         ASSERT(m_data.string8Ptr);
  97         return *++m_data.string8Ptr;
  98     }
  99
 100     UChar incrementAndGetCurrentChar16()
 101     {
 102         ASSERT(m_data.string16Ptr);
 103         return *++m_data.string16Ptr;
 104     }
 105
 106     String currentSubString(unsigned length)
 107     {
 108         int offset = m_string.length() - m_length;
 109         return m_string.substring(offset, length);
 110     }
 111
 112     ALWAYS_INLINE UChar getCurrentChar()
 113     {
 114         ASSERT(m_length);
 115         if (is8Bit())
 116             return getCurrentChar8();
 117         return getCurrentChar16();
 118     }
 119
 120     ALWAYS_INLINE UChar incrementAndGetCurrentChar()
 121     {
 122         ASSERT(m_length);
 123         if (is8Bit())
 124             return incrementAndGetCurrentChar8();
 125         return incrementAndGetCurrentChar16();
 126     }
 127
 128 public:
 129     union {
 130         const LChar* string8Ptr;
 131         const UChar* string16Ptr;
 132     } m_data;
 133     int m_length;
 134
 135 private:
 136     bool m_doNotExcludeLineNumbers;
 137     bool m_is8Bit;
 138     String m_string;
 139 };
 140
 141 class PLATFORM_EXPORT SegmentedString {
 142 public:
 143     SegmentedString()
 144         : m_pushedChar1(0)
 145         , m_pushedChar2(0)
 146         , m_currentChar(0)
 147         , m_numberOfCharactersConsumedPriorToCurrentString(0)
 148         , m_numberOfCharactersConsumedPriorToCurrentLine(0)
 149         , m_currentLine(0)
 150         , m_closed(false)
 151         , m_empty(true)
 152         , m_fastPathFlags(NoFastPath)
 153         , m_advanceFunc(&SegmentedString::advanceEmpty)
 154         , m_advanceAndUpdateLineNumberFunc(&SegmentedString::advanceEmpty)
 155     {
 156     }
 157
 158     SegmentedString(const String& str)
 159         : m_pushedChar1(0)
 160         , m_pushedChar2(0)
 161         , m_currentString(str)
 162         , m_currentChar(0)
 163         , m_numberOfCharactersConsumedPriorToCurrentString(0)
 164         , m_numberOfCharactersConsumedPriorToCurrentLine(0)
 165         , m_currentLine(0)
 166         , m_closed(false)
 167         , m_empty(!str.length())
 168         , m_fastPathFlags(NoFastPath)
 169     {
 170         if (m_currentString.m_length)
 171             m_currentChar = m_currentString.getCurrentChar();
 172         updateAdvanceFunctionPointers();
 173     }
 174
 175     void clear();
 176     void close();
 177
 178     void append(const SegmentedString&);
 179     void prepend(const SegmentedString&);
 180
 181     bool excludeLineNumbers() const { return m_currentString.excludeLineNumbers(); }
 182     void setExcludeLineNumbers();
 183
 184     void push(UChar c)
 185     {
 186         if (!m_pushedChar1) {
 187             m_pushedChar1 = c;
 188             m_currentChar = m_pushedChar1 ? m_pushedChar1 : m_currentString.getCurrentChar();
 189             updateSlowCaseFunctionPointers();
 190         } else {
 191             ASSERT(!m_pushedChar2);
 192             m_pushedChar2 = c;
 193         }
 194     }
 195
 196     bool isEmpty() const { return m_empty; }
 197     unsigned length() const;
 198
 199     bool isClosed() const { return m_closed; }
 200
 201     enum LookAheadResult {
 202         DidNotMatch,
 203         DidMatch,
 204         NotEnoughCharacters,
 205     };
 206
 207     LookAheadResult lookAhead(const String& string) { return lookAheadInline(string, true); }
 208     LookAheadResult lookAheadIgnoringCase(const String& string) { return lookAheadInline(string, false); }
 209
 210     void advance()
 211     {
 212         if (m_fastPathFlags & Use8BitAdvance) {
 213             ASSERT(!m_pushedChar1);
 214             bool haveOneCharacterLeft = (--m_currentString.m_length == 1);
 215             m_currentChar = m_currentString.incrementAndGetCurrentChar8();
 216
 217             if (!haveOneCharacterLeft)
 218                 return;
 219
 220             updateSlowCaseFunctionPointers();
 221
 222             return;
 223         }
 224
 225         (this->*m_advanceFunc)();
 226     }
 227
 228     inline void advanceAndUpdateLineNumber()
 229     {
 230         if (m_fastPathFlags & Use8BitAdvance) {
 231             ASSERT(!m_pushedChar1);
 232
 233             bool haveNewLine = (m_currentChar == '\n') & !!(m_fastPathFlags & Use8BitAdvanceAndUpdateLineNumbers);
 234             bool haveOneCharacterLeft = (--m_currentString.m_length == 1);
 235
 236             m_currentChar = m_currentString.incrementAndGetCurrentChar8();
 237
 238             if (!(haveNewLine | haveOneCharacterLeft))
 239                 return;
 240
 241             if (haveNewLine) {
 242                 ++m_currentLine;
 243                 m_numberOfCharactersConsumedPriorToCurrentLine =  m_numberOfCharactersConsumedPriorToCurrentString + m_currentString.numberOfCharactersConsumed();
 244             }
 245
 246             if (haveOneCharacterLeft)
 247                 updateSlowCaseFunctionPointers();
 248
 249             return;
 250         }
 251
 252         (this->*m_advanceAndUpdateLineNumberFunc)();
 253     }
 254
 255     void advanceAndASSERT(UChar expectedCharacter)
 256     {
 257         ASSERT_UNUSED(expectedCharacter, currentChar() == expectedCharacter);
 258         advance();
 259     }
 260
 261     void advanceAndASSERTIgnoringCase(UChar expectedCharacter)
 262     {
 263         ASSERT_UNUSED(expectedCharacter, WTF::Unicode::foldCase(currentChar()) == WTF::Unicode::foldCase(expectedCharacter));
 264         advance();
 265     }
 266
 267     void advancePastNonNewline()
 268     {
 269         ASSERT(currentChar() != '\n');
 270         advance();
 271     }
 272
 273     void advancePastNewlineAndUpdateLineNumber()
 274     {
 275         ASSERT(currentChar() == '\n');
 276         if (!m_pushedChar1 && m_currentString.m_length > 1) {
 277             int newLineFlag = m_currentString.doNotExcludeLineNumbers();
 278             m_currentLine += newLineFlag;
 279             if (newLineFlag)
 280                 m_numberOfCharactersConsumedPriorToCurrentLine = numberOfCharactersConsumed() + 1;
 281             decrementAndCheckLength();
 282             m_currentChar = m_currentString.incrementAndGetCurrentChar();
 283             return;
 284         }
 285         advanceAndUpdateLineNumberSlowCase();
 286     }
 287
 288     // Writes the consumed characters into consumedCharacters, which must
 289     // have space for at least |count| characters.
 290     void advance(unsigned count, UChar* consumedCharacters);
 291
 292     bool escaped() const { return m_pushedChar1; }
 293
 294     int numberOfCharactersConsumed() const
 295     {
 296         int numberOfPushedCharacters = 0;
 297         if (m_pushedChar1) {
 298             ++numberOfPushedCharacters;
 299             if (m_pushedChar2)
 300                 ++numberOfPushedCharacters;
 301         }
 302         return m_numberOfCharactersConsumedPriorToCurrentString + m_currentString.numberOfCharactersConsumed() - numberOfPushedCharacters;
 303     }
 304
 305     String toString() const;
 306
 307     UChar currentChar() const { return m_currentChar; }
 308
 309     // The method is moderately slow, comparing to currentLine method.
 310     OrdinalNumber currentColumn() const;
 311     OrdinalNumber currentLine() const;
 312     // Sets value of line/column variables. Column is specified indirectly by a parameter columnAftreProlog
 313     // which is a value of column that we should get after a prolog (first prologLength characters) has been consumed.
 314     void setCurrentPosition(OrdinalNumber line, OrdinalNumber columnAftreProlog, int prologLength);
 315
 316 private:
 317     enum FastPathFlags {
 318         NoFastPath = 0,
 319         Use8BitAdvanceAndUpdateLineNumbers = 1 << 0,
 320         Use8BitAdvance = 1 << 1,
 321     };
 322
 323     void append(const SegmentedSubstring&);
 324     void prepend(const SegmentedSubstring&);
 325
 326     void advance8();
 327     void advance16();
 328     void advanceAndUpdateLineNumber8();
 329     void advanceAndUpdateLineNumber16();
 330     void advanceSlowCase();
 331     void advanceAndUpdateLineNumberSlowCase();
 332     void advanceEmpty();
 333     void advanceSubstring();
 334
 335     void updateSlowCaseFunctionPointers();
 336
 337     void decrementAndCheckLength()
 338     {
 339         ASSERT(m_currentString.m_length > 1);
 340         if (--m_currentString.m_length == 1)
 341             updateSlowCaseFunctionPointers();
 342     }
 343
 344     void updateAdvanceFunctionPointers()
 345     {
 346         if ((m_currentString.m_length > 1) && !m_pushedChar1) {
 347             if (m_currentString.is8Bit()) {
 348                 m_advanceFunc = &SegmentedString::advance8;
 349                 m_fastPathFlags = Use8BitAdvance;
 350                 if (m_currentString.doNotExcludeLineNumbers()) {
 351                     m_advanceAndUpdateLineNumberFunc = &SegmentedString::advanceAndUpdateLineNumber8;
 352                     m_fastPathFlags |= Use8BitAdvanceAndUpdateLineNumbers;
 353                 } else {
 354                     m_advanceAndUpdateLineNumberFunc = &SegmentedString::advance8;
 355                 }
 356                 return;
 357             }
 358
 359             m_advanceFunc = &SegmentedString::advance16;
 360             m_fastPathFlags = NoFastPath;
 361             if (m_currentString.doNotExcludeLineNumbers())
 362                 m_advanceAndUpdateLineNumberFunc = &SegmentedString::advanceAndUpdateLineNumber16;
 363             else
 364                 m_advanceAndUpdateLineNumberFunc = &SegmentedString::advance16;
 365             return;
 366         }
 367
 368         if (!m_currentString.m_length && !isComposite()) {
 369             m_advanceFunc = &SegmentedString::advanceEmpty;
 370             m_fastPathFlags = NoFastPath;
 371             m_advanceAndUpdateLineNumberFunc = &SegmentedString::advanceEmpty;
 372         }
 373
 374         updateSlowCaseFunctionPointers();
 375     }
 376
 377     inline LookAheadResult lookAheadInline(const String& string, bool caseSensitive)
 378     {
 379         if (!m_pushedChar1 && string.length() <= static_cast<unsigned>(m_currentString.m_length)) {
 380             String currentSubstring = m_currentString.currentSubString(string.length());
 381             if (currentSubstring.startsWith(string, caseSensitive))
 382                 return DidMatch;
 383             return DidNotMatch;
 384         }
 385         return lookAheadSlowCase(string, caseSensitive);
 386     }
 387
 388     LookAheadResult lookAheadSlowCase(const String& string, bool caseSensitive)
 389     {
 390         unsigned count = string.length();
 391         if (count > length())
 392             return NotEnoughCharacters;
 393         UChar* consumedCharacters;
 394         String consumedString = String::createUninitialized(count, consumedCharacters);
 395         advance(count, consumedCharacters);
 396         LookAheadResult result = DidNotMatch;
 397         if (consumedString.startsWith(string, caseSensitive))
 398             result = DidMatch;
 399         prepend(SegmentedString(consumedString));
 400         return result;
 401     }
 402
 403     bool isComposite() const { return !m_substrings.isEmpty(); }
 404
 405     UChar m_pushedChar1;
 406     UChar m_pushedChar2;
 407     SegmentedSubstring m_currentString;
 408     UChar m_currentChar;
 409     int m_numberOfCharactersConsumedPriorToCurrentString;
 410     int m_numberOfCharactersConsumedPriorToCurrentLine;
 411     int m_currentLine;
 412     Deque<SegmentedSubstring> m_substrings;
 413     bool m_closed;
 414     bool m_empty;
 415     unsigned char m_fastPathFlags;
 416     void (SegmentedString::*m_advanceFunc)();
 417     void (SegmentedString::*m_advanceAndUpdateLineNumberFunc)();
 418 };
 419
 420 }
 421
 422 #endif