#GENERATOR: "KeywordLookup.h": keyword decision tree used by the lexer

ADD_CUSTOM_COMMAND(

    OUTPUT ${DERIVED_SOURCES_JAVASCRIPTCORE_DIR}/KeywordLookup.h

    MAIN_DEPENDENCY ${JAVASCRIPTCORE_DIR}/KeywordLookupGenerator.py

    COMMAND ${PYTHON_EXECUTABLE} ${JAVASCRIPTCORE_DIR}/KeywordLookupGenerator.py ${JAVASCRIPTCORE_DIR}/parser/Keywords.table > ${DERIVED_SOURCES_JAVASCRIPTCORE_DIR}/KeywordLookup.h

    VERBATIM)

ADD_SOURCE_DEPENDENCIES(${JAVASCRIPTCORE_DIR}/parser/Lexer.cpp ${DERIVED_SOURCES_JAVASCRIPTCORE_DIR}/KeywordLookup.h)

2011-06-03  Oliver Hunt  <oliver@apple.com>

        Reviewed by NOBODY (OOPS!).

        Improve keyword lookup

        https://bugs.webkit.org/show_bug.cgi?id=61913

        Rather than doing multiple hash lookups as we currently

        do when trying to identify keywords we now use an 

        automatically generated decision tree (essentially it's

        a hard coded patricia trie).  We still use the regular

        lookup table for the last few characters of an input as

        this allows us to completely skip all bounds checks.

        * CMakeLists.txt:

        * DerivedSources.make:

        * DerivedSources.pro:

        * GNUmakefile.am:

        * JavaScriptCore.gyp/JavaScriptCore.gyp:

        * JavaScriptCore.xcodeproj/project.pbxproj:

        * KeywordLookupGenerator.py: Added.

        * make-generated-sources.sh:

        * parser/Lexer.cpp:

        (JSC::Lexer::internalShift):

        (JSC::Lexer::shift):

        (JSC::Lexer::parseIdentifier):

        * parser/Lexer.h:

    KeywordLookup.h \

KeywordLookup.h: KeywordLookupGenerator.py Keywords.table

	python $^ > $@

#GENERATOR: "KeywordLookup.h": decision tree used by the lexer

klgen.output = $$JSC_GENERATED_SOURCES_DIR/KeywordLookup.h

klgen.wkScript = $$PWD/KeywordLookupGenerator.py 

klgen.input = KEYWORDLUT_FILES

klgen.commands = python $$klgen.wkScript ${QMAKE_FILE_NAME} > ${QMAKE_FILE_OUT}

addExtraCompiler(klgen)

Source/JavaScriptCore/KeywordLookup.h: $(srcdir)/Source/JavaScriptCore/KeywordLookupGenerator.py $(srcdir)/Source/JavaScriptCore/parser/Keywords.table

	$(AM_V_GEN)$(PYTHON) $^ > $@

        {

          'action_name': 'klgen',

          'inputs': [

            '../KeywordLookupGenerator.py',

            '../parser/Keywords.table'

          ],

          'arguments': [

          ],

          'outputs': [

            '<(INTERMEDIATE_DIR)/KeywordLookup.h',

          ],

          'action': ['python', '<@(_inputs)', '<@(_arguments)', '<@(_outputs)'],

        },

		A72FFD64139985A800E5365A /* KeywordLookup.h in Headers */ = {isa = PBXBuildFile; fileRef = A7C225CD1399849C00FF1662 /* KeywordLookup.h */; };

		A7C225CC139981F100FF1662 /* KeywordLookupGenerator.py */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.script.python; path = KeywordLookupGenerator.py; sourceTree = "<group>"; };

		A7C225CD1399849C00FF1662 /* KeywordLookup.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = KeywordLookup.h; sourceTree = "<group>"; };

				A7C225CC139981F100FF1662 /* KeywordLookupGenerator.py */,

				A7C225CD1399849C00FF1662 /* KeywordLookup.h */,

				A72FFD64139985A800E5365A /* KeywordLookup.h in Headers */,

# Copyright (C) 2010 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.

import sys

import string

import operator

keywordsText = open(sys.argv[1]).read()

# Observed weights of the most common keywords, rounded to 2.s.d

keyWordWeights = {

    "catch": 0.01,

    "try": 0.01,

    "while": 0.01,

    "case": 0.01,

    "break": 0.01,

    "new": 0.01,

    "in": 0.01,

    "typeof": 0.02,

    "true": 0.02,

    "false": 0.02,

    "for": 0.03,

    "null": 0.03,

    "else": 0.03,

    "return": 0.13,

    "var": 0.13,

    "if": 0.16,

    "function": 0.18,

    "this": 0.18,

}

def allWhitespace(str):

    for c in str:

        if not(c in string.whitespace):

            return False

    return True

def parseKeywords(keywordsText):

    lines = keywordsText.split("\n")

    lines = [line.split("#")[0] for line in lines]

    lines = [line for line in lines if (not allWhitespace(line))]

    name = lines[0].split()

    terminator = lines[-1]

    if not name[0] == "@begin":

        raise Exception("expected description beginning with @begin")

    if not terminator == "@end":

        raise Exception("expected description ending with @end")

    lines = lines[1:-1]  # trim off the old heading

    return [line.split() for line in lines]

def makePadding(size):

    str = ""

    for i in range(size):

        str = str + " "

    return str

class Trie:

    def __init__(self, prefix):

        self.prefix = prefix

        self.keys = {}

        self.value = None

    def insert(self, key, value):

        if len(key) == 0:

            self.value = value

            return

        if not (key[0] in self.keys):

            self.keys[key[0]] = Trie(key[0])

        self.keys[key[0]].insert(key[1:], value)

    def coalesce(self):

        keys = {}

        for k, v in self.keys.items():

            t = v.coalesce()

            keys[t.prefix] = t

        self.keys = keys

        if self.value != None:

            return self

        if len(self.keys) != 1:

            return self

        (prefix, suffix) = self.keys.items()[0]

        res = Trie(self.prefix + prefix)

        res.value = suffix.value

        res.keys = suffix.keys

        return res

    def fillOut(self, prefix=""):

        self.fullPrefix = prefix + self.prefix

        weight = 0

        if self.fullPrefix in keyWordWeights:

            weight = weight + keyWordWeights[self.fullPrefix]

        self.selfWeight = weight

        for trie in self.keys.values():

            trie.fillOut(self.fullPrefix)

            weight = weight + trie.weight

        self.keys = [(trie.prefix, trie) for trie in sorted(self.keys.values(), key=operator.attrgetter('weight'), reverse=True)]

        self.weight = weight

    def printSubTreeAsC(self, indent):

        str = makePadding(indent)

        if self.value != None:

            print(str + "if (!isIdentPart(code[%d])) {" % (len(self.fullPrefix)))

            print(str + "    internalShift<%d, false>();" % len(self.fullPrefix))

            print(str + "    return " + self.value + ";")

            print(str + "}")

        rootIndex = len(self.fullPrefix)

        itemCount = 0

        for k, trie in self.keys:

            baseIndex = rootIndex

            if (baseIndex > 0) and ((len(k) % 2) == 1) and (len(k) > 2) and (len(k) != 5):

                baseIndex = baseIndex - 1

                k = trie.fullPrefix[baseIndex] + k

            test = [("'%s'" % c) for c in k]

            if len(test) == 1:

                comparison = "code[%d] == %s" % (baseIndex, test[0])

            else:

                base = "code"

                if baseIndex > 0:

                    base = "code + %d" % baseIndex

                comparison = ("COMPARE_CHARACTERS%d(%s, " % (len(test), base)) + ", ".join(test) + ")"

            if itemCount == 0:

                print(str + "if (" + comparison + ") {")

            else:

                print(str + "else if (" + comparison + ") {")

            trie.printSubTreeAsC(indent + 4)

            itemCount = itemCount + 1

            print(str + "}")

    def maxLength(self):

        max = len(self.fullPrefix)

        for (_, trie) in self.keys:

            l = trie.maxLength()

            if l > max:

                max = l

        return max

    def printAsC(self):

        # max length + 1 so we don't need to do any bounds checking at all

        print("static const int maxTokenLength = %d;" % (self.maxLength() + 1))

        print("const ptrdiff_t remaining = m_codeEnd - m_code;")

        print("if ((remaining >= maxTokenLength) && !(lexType & IgnoreReservedWords)) {")

        print("    const UChar* code = m_code;")

        self.printSubTreeAsC(4)

        print("}")

keywords = parseKeywords(keywordsText)

trie = Trie("")

for k, v in keywords:

    trie.insert(k, v)

trie.coalesce()

trie.fillOut()

print("// This file was generated by KeywordLookupGenerator.py.  Do not edit.")

trie.printAsC()

export CREATE_KEYWORD_LOOKUP="$SRCROOT/KeywordLookupGenerator.py"

#if CPU(NEEDS_ALIGNED_ACCESS)

#define COMPARE_CHARACTERS2(address, char1, char2) \

    (((address)[0] == char1) && ((address)[1] == char2))

#define COMPARE_CHARACTERS4(address, char1, char2, char3, char4) \

    (COMPARE_CHARACTERS2(address, char1, char2) && COMPARE_CHARACTERS2((address) + 2, char3, char4))

#else

#if CPU(BIG_ENDIAN)

#define CHARPAIR_TOUINT32(a, b) ((((uint32_t)(a)) << 16) + (uint32_t)(b))

#define CHARQUAD_TOUINT64(a, b, c, d) ((((uint64_t)(CHARPAIR_TOUINT32(a, b))) << 32) + CHARPAIR_TOUINT32(c, d))

#else

#define CHARPAIR_TOUINT32(a, b) ((((uint32_t)(b)) << 16) + (uint32_t)(a))

#define CHARQUAD_TOUINT64(a, b, c, d) ((((uint64_t)(CHARPAIR_TOUINT32(c, d))) << 32) + CHARPAIR_TOUINT32(a, b))

#endif

#define COMPARE_CHARACTERS2(address, char1, char2) \

    (((uint32_t*)(address))[0] == CHARPAIR_TOUINT32(char1, char2))

#if CPU(X86_64)

#define COMPARE_CHARACTERS4(address, char1, char2, char3, char4) \

    (((uint64_t*)(address))[0] == CHARQUAD_TOUINT64(char1, char2, char3, char4))

#else

#define COMPARE_CHARACTERS4(address, char1, char2, char3, char4) \

    (COMPARE_CHARACTERS2(address, char1, char2) && COMPARE_CHARACTERS2((address) + 2, char3, char4))

#endif

#endif

#define COMPARE_CHARACTERS3(address, char1, char2, char3) \

    (COMPARE_CHARACTERS2(address, char1, char2) && ((address)[2] == (char3)))

#define COMPARE_CHARACTERS5(address, char1, char2, char3, char4, char5) \

    (COMPARE_CHARACTERS4(address, char1, char2, char3, char4) && ((address)[4] == (char5)))

#define COMPARE_CHARACTERS6(address, char1, char2, char3, char4, char5, char6) \

    (COMPARE_CHARACTERS4(address, char1, char2, char3, char4) && COMPARE_CHARACTERS2(address + 4, char5, char6))

#define COMPARE_CHARACTERS8(address, char1, char2, char3, char4, char5, char6, char7, char8) \

    (COMPARE_CHARACTERS4(address, char1, char2, char3, char4) && COMPARE_CHARACTERS4(address + 4, char5, char6, char7, char8))

    }

}

ALWAYS_INLINE void Lexer::shift()

{

    internalShift<1, true>();

        template <int shiftAmount, bool shouldBoundsCheck> void internalShift();