1 /* 2 * Copyright (C) 2010 Google Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #include "config.h" 27 #include "modules/indexeddb/IDBKeyPath.h" 28 29 #include "wtf/ASCIICType.h" 30 #include "wtf/dtoa.h" 31 #include "wtf/unicode/Unicode.h" 32 33 namespace WebCore { 34 35 class IDBKeyPathLexer { 36 public: 37 enum TokenType { 38 TokenIdentifier, 39 TokenDot, 40 TokenEnd, 41 TokenError 42 }; 43 44 explicit IDBKeyPathLexer(const String& s) 45 : m_string(s) 46 , m_index(0) 47 , m_length(s.length()) 48 , m_currentTokenType(TokenError) 49 { 50 } 51 52 TokenType currentTokenType() const { return m_currentTokenType; } 53 54 TokenType nextTokenType() 55 { 56 m_currentTokenType = lex(m_currentElement); 57 return m_currentTokenType; 58 } 59 60 const String& currentElement() { return m_currentElement; } 61 62 private: 63 TokenType lex(String&); 64 TokenType lexIdentifier(String&); 65 String m_currentElement; 66 const String m_string; 67 const unsigned m_length; 68 unsigned m_index; 69 TokenType m_currentTokenType; 70 }; 71 72 IDBKeyPathLexer::TokenType IDBKeyPathLexer::lex(String& element) 73 { 74 if (m_index >= m_length) 75 return TokenEnd; 76 ASSERT(m_index < m_length); 77 78 if (m_string[m_index] == '.') { 79 ++m_index; 80 return TokenDot; 81 } 82 return lexIdentifier(element); 83 } 84 85 namespace { 86 87 using namespace WTF::Unicode; 88 89 // The following correspond to grammar in ECMA-262. 90 const uint32_t unicodeLetter = Letter_Uppercase | Letter_Lowercase | Letter_Titlecase | Letter_Modifier | Letter_Other | Number_Letter; 91 const uint32_t unicodeCombiningMark = Mark_NonSpacing | Mark_SpacingCombining; 92 const uint32_t unicodeDigit = Number_DecimalDigit; 93 const uint32_t unicodeConnectorPunctuation = Punctuation_Connector; 94 const UChar ZWNJ = 0x200C; 95 const UChar ZWJ = 0x200D; 96 97 static inline bool isIdentifierStartCharacter(UChar c) 98 { 99 return (category(c) & unicodeLetter) || (c == '$') || (c == '_'); 100 } 101 102 static inline bool isIdentifierCharacter(UChar c) 103 { 104 return (category(c) & (unicodeLetter | unicodeCombiningMark | unicodeDigit | unicodeConnectorPunctuation)) || (c == '$') || (c == '_') || (c == ZWNJ) || (c == ZWJ); 105 } 106 107 } // namespace 108 109 IDBKeyPathLexer::TokenType IDBKeyPathLexer::lexIdentifier(String& element) 110 { 111 unsigned start = m_index; 112 if (m_index < m_length && isIdentifierStartCharacter(m_string[m_index])) 113 ++m_index; 114 else 115 return TokenError; 116 117 while (m_index < m_length && isIdentifierCharacter(m_string[m_index])) 118 ++m_index; 119 120 element = m_string.substring(start, m_index - start); 121 return TokenIdentifier; 122 } 123 124 bool IDBIsValidKeyPath(const String& keyPath) 125 { 126 IDBKeyPathParseError error; 127 Vector<String> keyPathElements; 128 IDBParseKeyPath(keyPath, keyPathElements, error); 129 return error == IDBKeyPathParseErrorNone; 130 } 131 132 void IDBParseKeyPath(const String& keyPath, Vector<String>& elements, IDBKeyPathParseError& error) 133 { 134 // IDBKeyPath ::= EMPTY_STRING | identifier ('.' identifier)* 135 // The basic state machine is: 136 // Start => {Identifier, End} 137 // Identifier => {Dot, End} 138 // Dot => {Identifier} 139 // It bails out as soon as it finds an error, but doesn't discard the bits it managed to parse. 140 enum ParserState { Identifier, Dot, End }; 141 142 IDBKeyPathLexer lexer(keyPath); 143 IDBKeyPathLexer::TokenType tokenType = lexer.nextTokenType(); 144 ParserState state; 145 if (tokenType == IDBKeyPathLexer::TokenIdentifier) 146 state = Identifier; 147 else if (tokenType == IDBKeyPathLexer::TokenEnd) 148 state = End; 149 else { 150 error = IDBKeyPathParseErrorStart; 151 return; 152 } 153 154 while (1) { 155 switch (state) { 156 case Identifier : { 157 IDBKeyPathLexer::TokenType tokenType = lexer.currentTokenType(); 158 ASSERT(tokenType == IDBKeyPathLexer::TokenIdentifier); 159 160 String element = lexer.currentElement(); 161 elements.append(element); 162 163 tokenType = lexer.nextTokenType(); 164 if (tokenType == IDBKeyPathLexer::TokenDot) 165 state = Dot; 166 else if (tokenType == IDBKeyPathLexer::TokenEnd) 167 state = End; 168 else { 169 error = IDBKeyPathParseErrorIdentifier; 170 return; 171 } 172 break; 173 } 174 case Dot: { 175 IDBKeyPathLexer::TokenType tokenType = lexer.currentTokenType(); 176 ASSERT(tokenType == IDBKeyPathLexer::TokenDot); 177 178 tokenType = lexer.nextTokenType(); 179 if (tokenType == IDBKeyPathLexer::TokenIdentifier) 180 state = Identifier; 181 else { 182 error = IDBKeyPathParseErrorDot; 183 return; 184 } 185 break; 186 } 187 case End: { 188 error = IDBKeyPathParseErrorNone; 189 return; 190 } 191 } 192 } 193 } 194 195 IDBKeyPath::IDBKeyPath(const String& string) 196 : m_type(StringType) 197 , m_string(string) 198 { 199 ASSERT(!m_string.isNull()); 200 } 201 202 IDBKeyPath::IDBKeyPath(const Vector<String>& array) 203 : m_type(ArrayType) 204 , m_array(array) 205 { 206 #ifndef NDEBUG 207 for (size_t i = 0; i < m_array.size(); ++i) 208 ASSERT(!m_array[i].isNull()); 209 #endif 210 } 211 212 bool IDBKeyPath::isValid() const 213 { 214 switch (m_type) { 215 case NullType: 216 return false; 217 218 case StringType: 219 return IDBIsValidKeyPath(m_string); 220 221 case ArrayType: 222 if (m_array.isEmpty()) 223 return false; 224 for (size_t i = 0; i < m_array.size(); ++i) { 225 if (!IDBIsValidKeyPath(m_array[i])) 226 return false; 227 } 228 return true; 229 } 230 ASSERT_NOT_REACHED(); 231 return false; 232 } 233 234 bool IDBKeyPath::operator==(const IDBKeyPath& other) const 235 { 236 if (m_type != other.m_type) 237 return false; 238 239 switch (m_type) { 240 case NullType: 241 return true; 242 case StringType: 243 return m_string == other.m_string; 244 case ArrayType: 245 return m_array == other.m_array; 246 } 247 ASSERT_NOT_REACHED(); 248 return false; 249 } 250 251 } // namespace WebCore 252