code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/KeywordLookupGenerator.py

   1 # Copyright (C) 2011 Apple Inc. All rights reserved.
   2 #
   3 # Redistribution and use in source and binary forms, with or without
   4 # modification, are permitted provided that the following conditions
   5 # are met:
   6 # 1. Redistributions of source code must retain the above copyright
   7 #    notice, this list of conditions and the following disclaimer.
   8 # 2. Redistributions in binary form must reproduce the above copyright
   9 #    notice, this list of conditions and the following disclaimer in the
  10 #    documentation and/or other materials provided with the distribution.
  11 #
  12 # THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  13 # EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  14 # IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  15 # PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  16 # CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  17 # EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  18 # PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  19 # PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  20 # OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  21 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  22 # OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  23
  24 import sys
  25 import string
  26 import operator
  27
  28 keywordsText = open(sys.argv[1]).read()
  29
  30 # Observed weights of the most common keywords, rounded to 2.s.d
  31 keyWordWeights = {
  32     "catch": 0.01,
  33     "try": 0.01,
  34     "while": 0.01,
  35     "case": 0.01,
  36     "break": 0.01,
  37     "new": 0.01,
  38     "in": 0.01,
  39     "typeof": 0.02,
  40     "true": 0.02,
  41     "false": 0.02,
  42     "for": 0.03,
  43     "null": 0.03,
  44     "else": 0.03,
  45     "return": 0.13,
  46     "var": 0.13,
  47     "if": 0.16,
  48     "function": 0.18,
  49     "this": 0.18,
  50 }
  51
  52
  53 def allWhitespace(str):
  54     for c in str:
  55         if not(c in string.whitespace):
  56             return False
  57     return True
  58
  59
  60 def parseKeywords(keywordsText):
  61     lines = keywordsText.split("\n")
  62     lines = [line.split("#")[0] for line in lines]
  63     lines = [line for line in lines if (not allWhitespace(line))]
  64     name = lines[0].split()
  65     terminator = lines[-1]
  66     if not name[0] == "@begin":
  67         raise Exception("expected description beginning with @begin")
  68     if not terminator == "@end":
  69         raise Exception("expected description ending with @end")
  70
  71     lines = lines[1:-1]  # trim off the old heading
  72     return [line.split() for line in lines]
  73
  74
  75 def makePadding(size):
  76     str = ""
  77     for i in range(size):
  78         str = str + " "
  79     return str
  80
  81
  82 class Trie:
  83     def __init__(self, prefix):
  84         self.prefix = prefix
  85         self.keys = {}
  86         self.value = None
  87
  88     def insert(self, key, value):
  89         if len(key) == 0:
  90             self.value = value
  91             return
  92         if not (key[0] in self.keys):
  93             self.keys[key[0]] = Trie(key[0])
  94         self.keys[key[0]].insert(key[1:], value)
  95
  96     def coalesce(self):
  97         keys = {}
  98         for k, v in self.keys.items():
  99             t = v.coalesce()
 100             keys[t.prefix] = t
 101         self.keys = keys
 102         if self.value != None:
 103             return self
 104         if len(self.keys) != 1:
 105             return self
 106         # Python 3: for() loop for compatibility. Use next() when Python 2.6 is the baseline.
 107         for (prefix, suffix) in self.keys.items():
 108             res = Trie(self.prefix + prefix)
 109             res.value = suffix.value
 110             res.keys = suffix.keys
 111             return res
 112
 113     def fillOut(self, prefix=""):
 114         self.fullPrefix = prefix + self.prefix
 115         weight = 0
 116         if self.fullPrefix in keyWordWeights:
 117             weight = weight + keyWordWeights[self.fullPrefix]
 118         self.selfWeight = weight
 119         for trie in self.keys.values():
 120             trie.fillOut(self.fullPrefix)
 121             weight = weight + trie.weight
 122         self.keys = [(trie.prefix, trie) for trie in sorted(self.keys.values(), key=operator.attrgetter('weight'), reverse=True)]
 123         self.weight = weight
 124
 125     def printSubTreeAsC(self, indent):
 126         str = makePadding(indent)
 127
 128         if self.value != None:
 129             print(str + "if (!isIdentPart(code[%d])) {" % (len(self.fullPrefix)))
 130             print(str + "    internalShift<%d, DoNotBoundsCheck>();" % len(self.fullPrefix))
 131             print(str + "    if (shouldCreateIdentifier)")
 132             print(str + ("        data->ident = &m_globalData->propertyNames->%sKeyword;" % self.fullPrefix))
 133             print(str + "    return " + self.value + ";")
 134             print(str + "}")
 135         rootIndex = len(self.fullPrefix)
 136         itemCount = 0
 137         for k, trie in self.keys:
 138             baseIndex = rootIndex
 139             if (baseIndex > 0) and (len(k) == 3):
 140                 baseIndex = baseIndex - 1
 141                 k = trie.fullPrefix[baseIndex] + k
 142             test = [("'%s'" % c) for c in k]
 143             if len(test) == 1:
 144                 comparison = "code[%d] == %s" % (baseIndex, test[0])
 145             else:
 146                 base = "code"
 147                 if baseIndex > 0:
 148                     base = "code + %d" % baseIndex
 149                 comparison = ("COMPARE_CHARACTERS%d(%s, " % (len(test), base)) + ", ".join(test) + ")"
 150             if itemCount == 0:
 151                 print(str + "if (" + comparison + ") {")
 152             else:
 153                 print(str + "} else if (" + comparison + ") {")
 154
 155             trie.printSubTreeAsC(indent + 4)
 156             itemCount = itemCount + 1
 157
 158             if itemCount == len(self.keys):
 159                 print(str + "}")
 160
 161     def maxLength(self):
 162         max = len(self.fullPrefix)
 163         for (_, trie) in self.keys:
 164             l = trie.maxLength()
 165             if l > max:
 166                 max = l
 167         return max
 168
 169     def printAsC(self):
 170         print("namespace JSC {")
 171         print("")
 172         print("static ALWAYS_INLINE bool isIdentPart(int c);")
 173         # max length + 1 so we don't need to do any bounds checking at all
 174         print("static const int maxTokenLength = %d;" % (self.maxLength() + 1))
 175         print("")
 176         print("template <bool shouldCreateIdentifier> ALWAYS_INLINE JSTokenType Lexer::parseKeyword(JSTokenData* data)")
 177         print("{")
 178         print("    ASSERT(m_codeEnd - m_code >= maxTokenLength);")
 179         print("")
 180         print("    const UChar* code = m_code;")
 181         self.printSubTreeAsC(4)
 182         print("    return IDENT;")
 183         print("}")
 184         print("")
 185         print("} // namespace JSC")
 186
 187 keywords = parseKeywords(keywordsText)
 188 trie = Trie("")
 189 for k, v in keywords:
 190     trie.insert(k, v)
 191 trie.coalesce()
 192 trie.fillOut()
 193 print("// This file was generated by KeywordLookupGenerator.py.  Do not edit.")
 194 print("""
 195 #if CPU(NEEDS_ALIGNED_ACCESS)
 196
 197 #define COMPARE_CHARACTERS2(address, char1, char2) \\
 198     (((address)[0] == char1) && ((address)[1] == char2))
 199 #define COMPARE_CHARACTERS4(address, char1, char2, char3, char4) \\
 200     (COMPARE_CHARACTERS2(address, char1, char2) && COMPARE_CHARACTERS2((address) + 2, char3, char4))
 201
 202 #else // CPU(NEEDS_ALIGNED_ACCESS)
 203
 204 #if CPU(BIG_ENDIAN)
 205
 206 #define CHARPAIR_TOUINT32(a, b) \\
 207     ((((uint32_t)(a)) << 16) + (uint32_t)(b))
 208 #define CHARQUAD_TOUINT64(a, b, c, d) \\
 209     ((((uint64_t)(CHARPAIR_TOUINT32(a, b))) << 32) + CHARPAIR_TOUINT32(c, d))
 210
 211 #else // CPU(BIG_ENDIAN)
 212
 213 #define CHARPAIR_TOUINT32(a, b) \\
 214     ((((uint32_t)(b)) << 16) + (uint32_t)(a))
 215 #define CHARQUAD_TOUINT64(a, b, c, d) \\
 216     ((((uint64_t)(CHARPAIR_TOUINT32(c, d))) << 32) + CHARPAIR_TOUINT32(a, b))
 217
 218 #endif // CPU(BIG_ENDIAN)
 219
 220
 221 #define COMPARE_CHARACTERS2(address, char1, char2) \\
 222     (((uint32_t*)(address))[0] == CHARPAIR_TOUINT32(char1, char2))
 223
 224 #if CPU(X86_64)
 225
 226 #define COMPARE_CHARACTERS4(address, char1, char2, char3, char4) \\
 227     (((uint64_t*)(address))[0] == CHARQUAD_TOUINT64(char1, char2, char3, char4))
 228
 229 #else // CPU(X86_64)
 230
 231 #define COMPARE_CHARACTERS4(address, char1, char2, char3, char4) \\
 232     (COMPARE_CHARACTERS2(address, char1, char2) && COMPARE_CHARACTERS2((address) + 2, char3, char4))
 233
 234 #endif // CPU(X86_64)
 235
 236 #endif // CPU(NEEDS_ALIGNED_ACCESS)
 237
 238 #define COMPARE_CHARACTERS3(address, char1, char2, char3) \\
 239     (COMPARE_CHARACTERS2(address, char1, char2) && ((address)[2] == (char3)))
 240 #define COMPARE_CHARACTERS5(address, char1, char2, char3, char4, char5) \\
 241     (COMPARE_CHARACTERS4(address, char1, char2, char3, char4) && ((address)[4] == (char5)))
 242 #define COMPARE_CHARACTERS6(address, char1, char2, char3, char4, char5, char6) \\
 243     (COMPARE_CHARACTERS4(address, char1, char2, char3, char4) && COMPARE_CHARACTERS2(address + 4, char5, char6))
 244 #define COMPARE_CHARACTERS7(address, char1, char2, char3, char4, char5, char6, char7) \\
 245     (COMPARE_CHARACTERS4(address, char1, char2, char3, char4) && COMPARE_CHARACTERS4(address + 3, char4, char5, char6, char7))
 246 #define COMPARE_CHARACTERS8(address, char1, char2, char3, char4, char5, char6, char7, char8) \\
 247     (COMPARE_CHARACTERS4(address, char1, char2, char3, char4) && COMPARE_CHARACTERS4(address + 4, char5, char6, char7, char8))
 248 """)
 249
 250 trie.printAsC()