code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/runtime/RegExp.cpp

   1 /*
   2  *  Copyright (C) 1999-2001, 2004 Harri Porten (porten@kde.org)
   3  *  Copyright (c) 2007, 2008 Apple Inc. All rights reserved.
   4  *  Copyright (C) 2009 Torch Mobile, Inc.
   5  *  Copyright (C) 2010 Peter Varga (pvarga@inf.u-szeged.hu), University of Szeged
   6  *
   7  *  This library is free software; you can redistribute it and/or
   8  *  modify it under the terms of the GNU Lesser General Public
   9  *  License as published by the Free Software Foundation; either
  10  *  version 2 of the License, or (at your option) any later version.
  11  *
  12  *  This library is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  *  Lesser General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU Lesser General Public
  18  *  License along with this library; if not, write to the Free Software
  19  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  20  *
  21  */
  22
  23 #include "config.h"
  24 #include "RegExp.h"
  25
  26 #include "Lexer.h"
  27 #include "RegExpCache.h"
  28 #include "yarr/Yarr.h"
  29 #include "yarr/YarrJIT.h"
  30 #include <stdio.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33 #include <wtf/Assertions.h>
  34 #include <wtf/OwnArrayPtr.h>
  35
  36
  37 #define REGEXP_FUNC_TEST_DATA_GEN 0
  38
  39 namespace JSC {
  40
  41 const ClassInfo RegExp::s_info = { "RegExp", 0, 0, 0 };
  42
  43 RegExpFlags regExpFlags(const UString& string)
  44 {
  45     RegExpFlags flags = NoFlags;
  46
  47     for (unsigned i = 0; i < string.length(); ++i) {
  48         switch (string[i]) {
  49         case 'g':
  50             if (flags & FlagGlobal)
  51                 return InvalidFlags;
  52             flags = static_cast<RegExpFlags>(flags | FlagGlobal);
  53             break;
  54
  55         case 'i':
  56             if (flags & FlagIgnoreCase)
  57                 return InvalidFlags;
  58             flags = static_cast<RegExpFlags>(flags | FlagIgnoreCase);
  59             break;
  60
  61         case 'm':
  62             if (flags & FlagMultiline)
  63                 return InvalidFlags;
  64             flags = static_cast<RegExpFlags>(flags | FlagMultiline);
  65             break;
  66
  67         default:
  68             return InvalidFlags;
  69         }
  70     }
  71
  72     return flags;
  73 }
  74
  75 #if REGEXP_FUNC_TEST_DATA_GEN
  76 class RegExpFunctionalTestCollector {
  77     // This class is not thread safe.
  78 protected:
  79     static const char* const s_fileName;
  80
  81 public:
  82     static RegExpFunctionalTestCollector* get();
  83
  84     ~RegExpFunctionalTestCollector();
  85
  86     void outputOneTest(RegExp*, UString, int, int*, int);
  87     void clearRegExp(RegExp* regExp)
  88     {
  89         if (regExp == m_lastRegExp)
  90             m_lastRegExp = 0;
  91     }
  92
  93 private:
  94     RegExpFunctionalTestCollector();
  95
  96     void outputEscapedUString(const UString&, bool escapeSlash = false);
  97
  98     static RegExpFunctionalTestCollector* s_instance;
  99     FILE* m_file;
 100     RegExp* m_lastRegExp;
 101 };
 102
 103 const char* const RegExpFunctionalTestCollector::s_fileName = "/tmp/RegExpTestsData";
 104 RegExpFunctionalTestCollector* RegExpFunctionalTestCollector::s_instance = 0;
 105
 106 RegExpFunctionalTestCollector* RegExpFunctionalTestCollector::get()
 107 {
 108     if (!s_instance)
 109         s_instance = new RegExpFunctionalTestCollector();
 110
 111     return s_instance;
 112 }
 113
 114 void RegExpFunctionalTestCollector::outputOneTest(RegExp* regExp, UString s, int startOffset, int* ovector, int result)
 115 {
 116     if ((!m_lastRegExp) || (m_lastRegExp != regExp)) {
 117         m_lastRegExp = regExp;
 118         fputc('/', m_file);
 119         outputEscapedUString(regExp->pattern(), true);
 120         fputc('/', m_file);
 121         if (regExp->global())
 122             fputc('g', m_file);
 123         if (regExp->ignoreCase())
 124             fputc('i', m_file);
 125         if (regExp->multiline())
 126             fputc('m', m_file);
 127         fprintf(m_file, "\n");
 128     }
 129
 130     fprintf(m_file, " \"");
 131     outputEscapedUString(s);
 132     fprintf(m_file, "\", %d, %d, (", startOffset, result);
 133     for (unsigned i = 0; i <= regExp->numSubpatterns(); i++) {
 134         int subPatternBegin = ovector[i * 2];
 135         int subPatternEnd = ovector[i * 2 + 1];
 136         if (subPatternBegin == -1)
 137             subPatternEnd = -1;
 138         fprintf(m_file, "%d, %d", subPatternBegin, subPatternEnd);
 139         if (i < regExp->numSubpatterns())
 140             fputs(", ", m_file);
 141     }
 142
 143     fprintf(m_file, ")\n");
 144     fflush(m_file);
 145 }
 146
 147 RegExpFunctionalTestCollector::RegExpFunctionalTestCollector()
 148 {
 149     m_file = fopen(s_fileName, "r+");
 150     if  (!m_file)
 151         m_file = fopen(s_fileName, "w+");
 152
 153     fseek(m_file, 0L, SEEK_END);
 154 }
 155
 156 RegExpFunctionalTestCollector::~RegExpFunctionalTestCollector()
 157 {
 158     fclose(m_file);
 159     s_instance = 0;
 160 }
 161
 162 void RegExpFunctionalTestCollector::outputEscapedUString(const UString& s, bool escapeSlash)
 163 {
 164     int len = s.length();
 165
 166     for (int i = 0; i < len; ++i) {
 167         UChar c = s[i];
 168
 169         switch (c) {
 170         case '\0':
 171             fputs("\\0", m_file);
 172             break;
 173         case '\a':
 174             fputs("\\a", m_file);
 175             break;
 176         case '\b':
 177             fputs("\\b", m_file);
 178             break;
 179         case '\f':
 180             fputs("\\f", m_file);
 181             break;
 182         case '\n':
 183             fputs("\\n", m_file);
 184             break;
 185         case '\r':
 186             fputs("\\r", m_file);
 187             break;
 188         case '\t':
 189             fputs("\\t", m_file);
 190             break;
 191         case '\v':
 192             fputs("\\v", m_file);
 193             break;
 194         case '/':
 195             if (escapeSlash)
 196                 fputs("\\/", m_file);
 197             else
 198                 fputs("/", m_file);
 199             break;
 200         case '\"':
 201             fputs("\\\"", m_file);
 202             break;
 203         case '\\':
 204             fputs("\\\\", m_file);
 205             break;
 206         case '\?':
 207             fputs("\?", m_file);
 208             break;
 209         default:
 210             if (c > 0x7f)
 211                 fprintf(m_file, "\\u%04x", c);
 212             else
 213                 fputc(c, m_file);
 214             break;
 215         }
 216     }
 217 }
 218 #endif
 219
 220 struct RegExpRepresentation {
 221 #if ENABLE(YARR_JIT)
 222     Yarr::YarrCodeBlock m_regExpJITCode;
 223 #endif
 224     OwnPtr<Yarr::BytecodePattern> m_regExpBytecode;
 225 };
 226
 227 RegExp::RegExp(JSGlobalData& globalData, const UString& patternString, RegExpFlags flags)
 228     : JSCell(globalData, globalData.regExpStructure.get())
 229     , m_state(NotCompiled)
 230     , m_patternString(patternString)
 231     , m_flags(flags)
 232     , m_constructionError(0)
 233     , m_numSubpatterns(0)
 234 #if ENABLE(REGEXP_TRACING)
 235     , m_rtMatchCallCount(0)
 236     , m_rtMatchFoundCount(0)
 237 #endif
 238 {
 239 }
 240
 241 void RegExp::finishCreation(JSGlobalData& globalData)
 242 {
 243     Base::finishCreation(globalData);
 244     Yarr::YarrPattern pattern(m_patternString, ignoreCase(), multiline(), &m_constructionError);
 245     if (m_constructionError)
 246         m_state = ParseError;
 247     else
 248         m_numSubpatterns = pattern.m_numSubpatterns;
 249 }
 250
 251 RegExp::~RegExp()
 252 {
 253 #if REGEXP_FUNC_TEST_DATA_GEN
 254     RegExpFunctionalTestCollector::get()->clearRegExp(this);
 255 #endif
 256 }
 257
 258 RegExp* RegExp::createWithoutCaching(JSGlobalData& globalData, const UString& patternString, RegExpFlags flags)
 259 {
 260     RegExp* regExp = new (allocateCell<RegExp>(globalData.heap)) RegExp(globalData, patternString, flags);
 261     regExp->finishCreation(globalData);
 262     return regExp;
 263 }
 264
 265 RegExp* RegExp::create(JSGlobalData& globalData, const UString& patternString, RegExpFlags flags)
 266 {
 267     return globalData.regExpCache()->lookupOrCreate(patternString, flags);
 268 }
 269
 270 void RegExp::compile(JSGlobalData* globalData, Yarr::YarrCharSize charSize)
 271 {
 272     Yarr::YarrPattern pattern(m_patternString, ignoreCase(), multiline(), &m_constructionError);
 273     if (m_constructionError) {
 274         ASSERT_NOT_REACHED();
 275         m_state = ParseError;
 276         return;
 277     }
 278     ASSERT(m_numSubpatterns == pattern.m_numSubpatterns);
 279
 280     if (!m_representation) {
 281         ASSERT(m_state == NotCompiled);
 282         m_representation = adoptPtr(new RegExpRepresentation);
 283         globalData->regExpCache()->addToStrongCache(this);
 284         m_state = ByteCode;
 285     }
 286
 287 #if ENABLE(YARR_JIT)
 288     if (!pattern.m_containsBackreferences && globalData->canUseJIT()) {
 289         Yarr::jitCompile(pattern, charSize, globalData, m_representation->m_regExpJITCode);
 290 #if ENABLE(YARR_JIT_DEBUG)
 291         if (!m_representation->m_regExpJITCode.isFallBack())
 292             m_state = JITCode;
 293         else
 294             m_state = ByteCode;
 295 #else
 296         if (!m_representation->m_regExpJITCode.isFallBack()) {
 297             m_state = JITCode;
 298             return;
 299         }
 300 #endif
 301     }
 302 #else
 303     UNUSED_PARAM(charSize);
 304 #endif
 305
 306     m_representation->m_regExpBytecode = Yarr::byteCompile(pattern, &globalData->m_regExpAllocator);
 307 }
 308
 309 void RegExp::compileIfNecessary(JSGlobalData& globalData, Yarr::YarrCharSize charSize)
 310 {
 311     // If the state is NotCompiled or ParseError, then there is no representation.
 312     // If there is a representation, and the state must be either JITCode or ByteCode.
 313     ASSERT(!!m_representation == (m_state == JITCode || m_state == ByteCode));
 314
 315     if (m_representation) {
 316 #if ENABLE(YARR_JIT)
 317         if (m_state != JITCode)
 318             return;
 319         if ((charSize == Yarr::Char8) && (m_representation->m_regExpJITCode.has8BitCode()))
 320             return;
 321         if ((charSize == Yarr::Char16) && (m_representation->m_regExpJITCode.has16BitCode()))
 322             return;
 323 #else
 324         return;
 325 #endif
 326     }
 327
 328     compile(&globalData, charSize);
 329 }
 330
 331
 332 int RegExp::match(JSGlobalData& globalData, const UString& s, int startOffset, Vector<int, 32>* ovector)
 333 {
 334     if (startOffset < 0)
 335         startOffset = 0;
 336
 337 #if ENABLE(REGEXP_TRACING)
 338     m_rtMatchCallCount++;
 339 #endif
 340
 341     if (static_cast<unsigned>(startOffset) > s.length() || s.isNull())
 342         return -1;
 343
 344     if (m_state != ParseError) {
 345         compileIfNecessary(globalData, s.is8Bit() ? Yarr::Char8 : Yarr::Char16);
 346
 347         int offsetVectorSize = (m_numSubpatterns + 1) * 2;
 348         int* offsetVector;
 349         Vector<int, 32> nonReturnedOvector;
 350         if (ovector) {
 351             ovector->resize(offsetVectorSize);
 352             offsetVector = ovector->data();
 353         } else {
 354             nonReturnedOvector.resize(offsetVectorSize);
 355             offsetVector = nonReturnedOvector.data();
 356         }
 357
 358         ASSERT(offsetVector);
 359         // Initialize offsetVector with the return value (index 0) and the
 360         // first subpattern start indicies (even index values) set to -1.
 361         // No need to init the subpattern end indicies.
 362         for (unsigned j = 0, i = 0; i < m_numSubpatterns + 1; j += 2, i++)
 363             offsetVector[j] = -1;
 364
 365         int result;
 366 #if ENABLE(YARR_JIT)
 367         if (m_state == JITCode) {
 368             if (s.is8Bit())
 369                 result = Yarr::execute(m_representation->m_regExpJITCode, s.latin1().data(), startOffset, s.length(), offsetVector);
 370             else
 371                 result = Yarr::execute(m_representation->m_regExpJITCode, s.characters(), startOffset, s.length(), offsetVector);
 372 #if ENABLE(YARR_JIT_DEBUG)
 373             matchCompareWithInterpreter(s, startOffset, offsetVector, result);
 374 #endif
 375         } else
 376 #endif
 377             result = Yarr::interpret(m_representation->m_regExpBytecode.get(), s, startOffset, s.length(), offsetVector);
 378         ASSERT(result >= -1);
 379
 380 #if REGEXP_FUNC_TEST_DATA_GEN
 381         RegExpFunctionalTestCollector::get()->outputOneTest(this, s, startOffset, offsetVector, result);
 382 #endif
 383
 384 #if ENABLE(REGEXP_TRACING)
 385         if (result != -1)
 386             m_rtMatchFoundCount++;
 387 #endif
 388
 389         return result;
 390     }
 391
 392     return -1;
 393 }
 394
 395 void RegExp::invalidateCode()
 396 {
 397     if (!m_representation)
 398         return;
 399     m_state = NotCompiled;
 400     m_representation.clear();
 401 }
 402
 403 #if ENABLE(YARR_JIT_DEBUG)
 404 void RegExp::matchCompareWithInterpreter(const UString& s, int startOffset, int* offsetVector, int jitResult)
 405 {
 406     int offsetVectorSize = (m_numSubpatterns + 1) * 2;
 407     Vector<int, 32> interpreterOvector;
 408     interpreterOvector.resize(offsetVectorSize);
 409     int* interpreterOffsetVector = interpreterOvector.data();
 410     int interpreterResult = 0;
 411     int differences = 0;
 412
 413     // Initialize interpreterOffsetVector with the return value (index 0) and the
 414     // first subpattern start indicies (even index values) set to -1.
 415     // No need to init the subpattern end indicies.
 416     for (unsigned j = 0, i = 0; i < m_numSubpatterns + 1; j += 2, i++)
 417         interpreterOffsetVector[j] = -1;
 418
 419     interpreterResult = Yarr::interpret(m_representation->m_regExpBytecode.get(), s, startOffset, s.length(), interpreterOffsetVector);
 420
 421     if (jitResult != interpreterResult)
 422         differences++;
 423
 424     for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++)
 425         if ((offsetVector[j] != interpreterOffsetVector[j])
 426             || ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1])))
 427             differences++;
 428
 429     if (differences) {
 430         fprintf(stderr, "RegExp Discrepency for /%s/\n    string input ", pattern().utf8().data());
 431         unsigned segmentLen = s.length() - static_cast<unsigned>(startOffset);
 432
 433         fprintf(stderr, (segmentLen < 150) ? "\"%s\"\n" : "\"%148s...\"\n", s.utf8().data() + startOffset);
 434
 435         if (jitResult != interpreterResult) {
 436             fprintf(stderr, "    JIT result = %d, blah interpreted result = %d\n", jitResult, interpreterResult);
 437             differences--;
 438         } else {
 439             fprintf(stderr, "    Correct result = %d\n", jitResult);
 440         }
 441
 442         if (differences) {
 443             for (unsigned j = 2, i = 0; i < m_numSubpatterns; j +=2, i++) {
 444                 if (offsetVector[j] != interpreterOffsetVector[j])
 445                     fprintf(stderr, "    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j, offsetVector[j], j, interpreterOffsetVector[j]);
 446                 if ((offsetVector[j] >= 0) && (offsetVector[j+1] != interpreterOffsetVector[j+1]))
 447                     fprintf(stderr, "    JIT offset[%d] = %d, interpreted offset[%d] = %d\n", j+1, offsetVector[j+1], j+1, interpreterOffsetVector[j+1]);
 448             }
 449         }
 450     }
 451 }
 452 #endif
 453
 454 #if ENABLE(REGEXP_TRACING)
 455     void RegExp::printTraceData()
 456     {
 457         char formattedPattern[41];
 458         char rawPattern[41];
 459
 460         strncpy(rawPattern, pattern().utf8().data(), 40);
 461         rawPattern[40]= '\0';
 462
 463         int pattLen = strlen(rawPattern);
 464
 465         snprintf(formattedPattern, 41, (pattLen <= 38) ? "/%.38s/" : "/%.36s...", rawPattern);
 466
 467 #if ENABLE(YARR_JIT)
 468         Yarr::YarrCodeBlock& codeBlock = m_representation->m_regExpJITCode;
 469
 470         const size_t jitAddrSize = 20;
 471         char jitAddr[jitAddrSize];
 472         if (m_state == JITCode)
 473             snprintf(jitAddr, jitAddrSize, "fallback");
 474         else
 475             snprintf(jitAddr, jitAddrSize, "0x%014lx", reinterpret_cast<unsigned long int>(codeBlock.getAddr()));
 476 #else
 477         const char* jitAddr = "JIT Off";
 478 #endif
 479
 480         printf("%-40.40s %16.16s %10d %10d\n", formattedPattern, jitAddr, m_rtMatchCallCount, m_rtMatchFoundCount);
 481     }
 482 #endif
 483
 484 } // namespace JSC