Merge WebKit at r76408: Initial merge by git.

Change-Id: I5b91decbd693ccbf5c1b8354b37cd68cc9a1ea53

9 files changed, 177 insertions, 26 deletions

diff --git a/Source/JavaScriptCore/parser/ASTBuilder.h b/Source/JavaScriptCore/parser/ASTBuilder.h
index 337c87e..0e18d1d 100644
--- a/Source/JavaScriptCore/parser/ASTBuilder.h
+++ b/Source/JavaScriptCore/parser/ASTBuilder.h
@@ -108,6 +108,7 @@ public:
     
     static const bool CreatesAST = true;
     static const bool NeedsFreeVariableInfo = true;
+    static const bool CanUseFunctionCache = true;
 
     ExpressionNode* makeBinaryNode(int token, std::pair<ExpressionNode*, BinaryOpInfo>, std::pair<ExpressionNode*, BinaryOpInfo>);
     ExpressionNode* makeFunctionCallNode(ExpressionNode* func, ArgumentsNode* args, int start, int divot, int end);
diff --git a/Source/JavaScriptCore/parser/JSParser.cpp b/Source/JavaScriptCore/parser/JSParser.cpp
index 37b7f90..cb59f93 100644
--- a/Source/JavaScriptCore/parser/JSParser.cpp
+++ b/Source/JavaScriptCore/parser/JSParser.cpp
@@ -33,6 +33,7 @@ using namespace JSC;
 #include "JSGlobalData.h"
 #include "NodeInfo.h"
 #include "ASTBuilder.h"
+#include "SourceProvider.h"
 #include <wtf/HashFunctions.h>
 #include <wtf/WTFThreadData.h>
 #include <utility>
@@ -94,6 +95,39 @@ private:
         StringImpl* m_ident;
         bool m_isLoop;
     };
+    
+    struct CachedFunctionInfo : public SourceProviderCache::Item {
+        CachedFunctionInfo(int closeBraceLine, int closeBracePos)
+            : closeBraceLine(closeBraceLine) 
+            , closeBracePos(closeBracePos)
+        {
+        }
+        unsigned approximateByteSize() const
+        {
+            // The identifiers are uniqued strings so most likely there are few names that actually use any additional memory.
+            static const unsigned assummedAverageIdentifierSize = sizeof(RefPtr<StringImpl>) + 2;
+            unsigned size = sizeof(*this);
+            size += usedVariables.size() * assummedAverageIdentifierSize;
+            size += writtenVariables.size() * assummedAverageIdentifierSize;
+            return size;
+        }
+        JSToken closeBraceToken() const 
+        {
+            JSToken token;
+            token.m_type = CLOSEBRACE;
+            token.m_data.intValue = closeBracePos;
+            token.m_info.startOffset = closeBracePos;
+            token.m_info.endOffset = closeBracePos + 1;
+            token.m_info.line = closeBraceLine; 
+            return token;
+        }
+
+        int closeBraceLine;
+        int closeBracePos;
+        bool usesEval;
+        Vector<RefPtr<StringImpl> > usedVariables;
+        Vector<RefPtr<StringImpl> > writtenVariables;
+    };
 
     void next(Lexer::LexType lexType = Lexer::IdentifyReservedWords)
     {
@@ -417,6 +451,37 @@ private:
         bool strictMode() const { return m_strictMode; }
         bool isValidStrictMode() const { return m_isValidStrictMode; }
         bool shadowsArguments() const { return m_shadowsArguments; }
+        
+        void copyCapturedVariablesToVector(const IdentifierSet& capturedVariables, Vector<RefPtr<StringImpl> >& vector)
+        {
+            IdentifierSet::iterator end = capturedVariables.end();
+            for (IdentifierSet::iterator it = capturedVariables.begin(); it != end; ++it) {
+                if (m_declaredVariables.contains(*it))
+                    continue;
+                vector.append(*it);
+            }
+            vector.shrinkToFit();
+        }
+
+        void saveFunctionInfo(CachedFunctionInfo* info)
+        {
+            ASSERT(m_isFunction);
+            info->usesEval = m_usesEval;
+            copyCapturedVariablesToVector(m_writtenVariables, info->writtenVariables);
+            copyCapturedVariablesToVector(m_usedVariables, info->usedVariables);
+        }
+
+        void restoreFunctionInfo(const CachedFunctionInfo* info)
+        {
+            ASSERT(m_isFunction);
+            m_usesEval = info->usesEval;
+            unsigned size = info->usedVariables.size();
+            for (unsigned i = 0; i < size; ++i)
+                m_usedVariables.add(info->usedVariables[i]);
+            size = info->writtenVariables.size();
+            for (unsigned i = 0; i < size; ++i)
+                m_writtenVariables.add(info->writtenVariables[i]);
+        }
 
     private:
         JSGlobalData* m_globalData;
@@ -543,6 +608,13 @@ private:
     }
 
     ScopeStack m_scopeStack;
+
+    const CachedFunctionInfo* findCachedFunctionInfo(int openBracePos) 
+    {
+        return m_functionCache ? static_cast<const CachedFunctionInfo*>(m_functionCache->get(openBracePos)) : 0;
+    }
+
+    SourceProviderCache* m_functionCache;
 };
 
 const char* jsParse(JSGlobalData* globalData, FunctionParameters* parameters, JSParserStrictness strictness, JSParserMode parserMode, const SourceCode* source)
@@ -566,6 +638,7 @@ JSParser::JSParser(Lexer* lexer, JSGlobalData* globalData, FunctionParameters* p
     , m_statementDepth(0)
     , m_nonTrivialExpressionCount(0)
     , m_lastIdentifier(0)
+    , m_functionCache(m_lexer->sourceProvider()->cache())
 {
     ScopeRef scope = pushScope();
     if (isFunction)
@@ -582,6 +655,7 @@ JSParser::JSParser(Lexer* lexer, JSGlobalData* globalData, FunctionParameters* p
 
 const char* JSParser::parseProgram()
 {
+    unsigned oldFunctionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
     ASTBuilder context(m_globalData, m_lexer);
     if (m_lexer->isReparsing())
         m_statementDepth--;
@@ -596,6 +670,10 @@ const char* JSParser::parseProgram()
         features |= StrictModeFeature;
     if (scope->shadowsArguments())
         features |= ShadowsArgumentsFeature;
+    
+    unsigned functionCacheSize = m_functionCache ? m_functionCache->byteSize() : 0;
+    if (functionCacheSize != oldFunctionCacheSize)
+        m_lexer->sourceProvider()->notifyCacheSizeChanged(functionCacheSize - oldFunctionCacheSize);
 
     m_globalData->parser->didFinishParsing(sourceElements, context.varDeclarations(), context.funcDeclarations(), features,
                                            m_lastLine, context.numConstants(), capturedVariables);
@@ -1223,6 +1301,7 @@ template <JSParser::FunctionRequirements requirements, bool nameIsInContainingSc
     functionScope->setIsFunction();
     if (match(IDENT)) {
         name = m_token.m_data.ident;
+        failIfTrue(*name == m_globalData->propertyNames->underscoreProto);
         next();
         if (!nameIsInContainingScope)
             failIfFalseIfStrict(functionScope->declareVariable(name));
@@ -1238,6 +1317,23 @@ template <JSParser::FunctionRequirements requirements, bool nameIsInContainingSc
 
     openBracePos = m_token.m_data.intValue;
     bodyStartLine = tokenLine();
+
+    if (const CachedFunctionInfo* cachedInfo = TreeBuilder::CanUseFunctionCache ? findCachedFunctionInfo(openBracePos) : 0) {
+        // If we know about this function already, we can use the cached info and skip the parser to the end of the function.
+        body = context.createFunctionBody(strictMode());
+
+        functionScope->restoreFunctionInfo(cachedInfo);
+        failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
+
+        closeBracePos = cachedInfo->closeBracePos;
+        m_token = cachedInfo->closeBraceToken();
+        m_lexer->setOffset(m_token.m_info.endOffset);
+        m_lexer->setLineNumber(m_token.m_info.line);
+
+        next();
+        return true;
+    }
+
     next();
 
     body = parseFunctionBody(context);
@@ -1246,9 +1342,26 @@ template <JSParser::FunctionRequirements requirements, bool nameIsInContainingSc
         failIfTrue(m_globalData->propertyNames->arguments == *name);
         failIfTrue(m_globalData->propertyNames->eval == *name);
     }
+    closeBracePos = m_token.m_data.intValue;
+    
+    // Cache the tokenizer state and the function scope the first time the function is parsed.
+    // Any future reparsing can then skip the function.
+    static const int minimumFunctionLengthToCache = 64;
+    OwnPtr<CachedFunctionInfo> newInfo;
+    int functionLength = closeBracePos - openBracePos;
+    if (TreeBuilder::CanUseFunctionCache && m_functionCache && functionLength > minimumFunctionLengthToCache) {
+        newInfo = adoptPtr(new CachedFunctionInfo(m_token.m_info.line, closeBracePos));
+        functionScope->saveFunctionInfo(newInfo.get());
+    }
+    
     failIfFalse(popScope(functionScope, TreeBuilder::NeedsFreeVariableInfo));
     matchOrFail(CLOSEBRACE);
-    closeBracePos = m_token.m_data.intValue;
+
+    if (newInfo) {
+        unsigned approximateByteSize = newInfo->approximateByteSize();
+        m_functionCache->add(openBracePos, newInfo.release(), approximateByteSize);
+    }
+
     next();
     return true;
 }
diff --git a/Source/JavaScriptCore/parser/Lexer.h b/Source/JavaScriptCore/parser/Lexer.h
index 79987af..d4145c1 100644
--- a/Source/JavaScriptCore/parser/Lexer.h
+++ b/Source/JavaScriptCore/parser/Lexer.h
@@ -37,7 +37,8 @@ namespace JSC {
 
     class RegExp;
 
-    class Lexer : public Noncopyable {
+    class Lexer {
+        WTF_MAKE_NONCOPYABLE(Lexer); WTF_MAKE_FAST_ALLOCATED;
     public:
         // Character manipulation functions.
         static bool isWhiteSpace(int character);
@@ -73,7 +74,15 @@ namespace JSC {
             m_current = *m_code;
             m_buffer8.resize(0);
             m_buffer16.resize(0);
+            if (UNLIKELY(m_code == m_codeEnd))
+                m_current = -1;
         }
+        void setLineNumber(int line)
+        {
+            m_lineNumber = line;
+        }
+
+        SourceProvider* sourceProvider() const { return m_source->provider(); }
 
     private:
         friend class JSGlobalData;
diff --git a/Source/JavaScriptCore/parser/Nodes.h b/Source/JavaScriptCore/parser/Nodes.h
index 54b7231..6e73c00 100644
--- a/Source/JavaScriptCore/parser/Nodes.h
+++ b/Source/JavaScriptCore/parser/Nodes.h
@@ -1376,7 +1376,9 @@ namespace JSC {
         ParameterNode* m_next;
     };
 
-    struct ScopeNodeData : FastAllocBase {
+    struct ScopeNodeData {
+        WTF_MAKE_FAST_ALLOCATED;
+    public:
         typedef DeclarationStacks::VarStack VarStack;
         typedef DeclarationStacks::FunctionStack FunctionStack;
 
@@ -1472,6 +1474,7 @@ namespace JSC {
     };
 
     class FunctionParameters : public Vector<Identifier>, public RefCounted<FunctionParameters> {
+        WTF_MAKE_FAST_ALLOCATED;
     public:
         static PassRefPtr<FunctionParameters> create(ParameterNode* firstParameter) { return adoptRef(new FunctionParameters(firstParameter)); }
 
diff --git a/Source/JavaScriptCore/parser/Parser.h b/Source/JavaScriptCore/parser/Parser.h
index 213827b..58398d1 100644
--- a/Source/JavaScriptCore/parser/Parser.h
+++ b/Source/JavaScriptCore/parser/Parser.h
@@ -45,8 +45,10 @@ namespace JSC {
 
     template <typename T> struct ParserArenaData : ParserArenaDeletable { T data; };
 
-    class Parser : public Noncopyable {
+    class Parser {
+        WTF_MAKE_NONCOPYABLE(Parser); WTF_MAKE_FAST_ALLOCATED;
     public:
+        Parser() { }
         template <class ParsedNode>
         PassRefPtr<ParsedNode> parse(JSGlobalObject* lexicalGlobalObject, Debugger*, ExecState*, const SourceCode& source, FunctionParameters*, JSParserStrictness strictness, JSObject** exception);
 
@@ -119,7 +121,7 @@ namespace JSC {
         m_funcDeclarations = 0;
 
         if (debugger && !ParsedNode::scopeIsFunction)
-            debugger->sourceParsed(debuggerExecState, source, errLine, errMsg);
+            debugger->sourceParsed(debuggerExecState, source.provider(), errLine, errMsg);
         return result.release();
     }
 
diff --git a/Source/JavaScriptCore/parser/ParserArena.h b/Source/JavaScriptCore/parser/ParserArena.h
index 7c1809e..82fb808 100644
--- a/Source/JavaScriptCore/parser/ParserArena.h
+++ b/Source/JavaScriptCore/parser/ParserArena.h
@@ -34,7 +34,8 @@ namespace JSC {
     class ParserArenaDeletable;
     class ParserArenaRefCounted;
 
-    class IdentifierArena : public FastAllocBase {
+    class IdentifierArena {
+        WTF_MAKE_FAST_ALLOCATED;
     public:
         ALWAYS_INLINE const Identifier& makeIdentifier(JSGlobalData*, const UChar* characters, size_t length);
         const Identifier& makeNumericIdentifier(JSGlobalData*, double number);
@@ -59,7 +60,8 @@ namespace JSC {
         return m_identifiers.last();
     }
 
-    class ParserArena : Noncopyable {
+    class ParserArena {
+        WTF_MAKE_NONCOPYABLE(ParserArena);
     public:
         ParserArena();
         ~ParserArena();
diff --git a/Source/JavaScriptCore/parser/SourceCode.h b/Source/JavaScriptCore/parser/SourceCode.h
index a3ce759..9ba4da3 100644
--- a/Source/JavaScriptCore/parser/SourceCode.h
+++ b/Source/JavaScriptCore/parser/SourceCode.h
@@ -31,7 +31,6 @@
 
 #include "SourceProvider.h"
 #include <wtf/RefPtr.h>
-#include <wtf/text/TextPosition.h>
 
 namespace JSC {
 
@@ -42,34 +41,22 @@ namespace JSC {
             , m_startChar(0)
             , m_endChar(0)
             , m_firstLine(0)
-            , m_firstColumn(0)
         {
         }
 
-        SourceCode(PassRefPtr<SourceProvider> provider, int firstLine = 1, int firstColumn = 1)
+        SourceCode(PassRefPtr<SourceProvider> provider, int firstLine = 1)
             : m_provider(provider)
             , m_startChar(0)
             , m_endChar(m_provider->length())
             , m_firstLine(std::max(firstLine, 1))
-            , m_firstColumn(std::max(firstColumn, 1))
         {
         }
 
-        SourceCode(PassRefPtr<SourceProvider> provider, int start, int end, int firstLine, int firstColumn = 1)
+        SourceCode(PassRefPtr<SourceProvider> provider, int start, int end, int firstLine)
             : m_provider(provider)
             , m_startChar(start)
             , m_endChar(end)
             , m_firstLine(std::max(firstLine, 1))
-            , m_firstColumn(std::max(firstColumn, 1))
-        {
-        }
-
-        SourceCode(PassRefPtr<SourceProvider> provider, const TextPosition1& startPosition)
-            : m_provider(provider)
-            , m_startChar(0)
-            , m_endChar(m_provider->length())
-            , m_firstLine(startPosition.m_line.oneBasedInt())
-            , m_firstColumn(startPosition.m_column.oneBasedInt())
         {
         }
 
@@ -83,7 +70,6 @@ namespace JSC {
         bool isNull() const { return !m_provider; }
         SourceProvider* provider() const { return m_provider.get(); }
         int firstLine() const { return m_firstLine; }
-        int firstColumn() const { return m_firstColumn; }
         int startOffset() const { return m_startChar; }
         int endOffset() const { return m_endChar; }
         const UChar* data() const { return m_provider->data() + m_startChar; }
@@ -94,7 +80,6 @@ namespace JSC {
         int m_startChar;
         int m_endChar;
         int m_firstLine;
-        int m_firstColumn;
     };
 
     inline SourceCode makeSource(const UString& source, const UString& url = UString(), int firstLine = 1)
diff --git a/Source/JavaScriptCore/parser/SourceProvider.h b/Source/JavaScriptCore/parser/SourceProvider.h
index 5ff1d14..bcc445b 100644
--- a/Source/JavaScriptCore/parser/SourceProvider.h
+++ b/Source/JavaScriptCore/parser/SourceProvider.h
@@ -30,32 +30,67 @@
 #define SourceProvider_h
 
 #include "UString.h"
+#include <wtf/HashMap.h>
+#include <wtf/PassOwnPtr.h>
 #include <wtf/RefCounted.h>
+#include <wtf/UnusedParam.h>
+#include <wtf/text/TextPosition.h>
+
 
 namespace JSC {
 
+    class SourceProviderCache {
+    public:
+        struct Item {};
+
+        SourceProviderCache() : m_contentByteSize(0) {}
+        ~SourceProviderCache() { deleteAllValues(m_map); }
+        
+        unsigned byteSize() const { return m_contentByteSize + sizeof(*this) + m_map.capacity() * sizeof(Item*); } 
+        void add(int sourcePosition, PassOwnPtr<Item> item, unsigned size) { m_map.add(sourcePosition, item.leakPtr()); m_contentByteSize += size; }
+        const Item* get(int sourcePosition) const { return m_map.get(sourcePosition); }
+
+    private:
+        HashMap<int, Item*> m_map;
+        unsigned m_contentByteSize;
+    };
+
     class SourceProvider : public RefCounted<SourceProvider> {
     public:
-        SourceProvider(const UString& url)
+        SourceProvider(const UString& url, SourceProviderCache* cache = 0)
             : m_url(url)
             , m_validated(false)
+            , m_cache(cache ? cache : new SourceProviderCache)
+            , m_cacheOwned(!cache)
+        {
+        }
+        virtual ~SourceProvider()
         {
+            if (m_cacheOwned)
+                delete m_cache;
         }
-        virtual ~SourceProvider() { }
 
         virtual UString getRange(int start, int end) const = 0;
         virtual const UChar* data() const = 0;
         virtual int length() const = 0;
         
         const UString& url() { return m_url; }
+        virtual TextPosition1 startPosition() const { return TextPosition1::minimumPosition(); }
         intptr_t asID() { return reinterpret_cast<intptr_t>(this); }
 
         bool isValid() const { return m_validated; }
         void setValid() { m_validated = true; }
 
+        SourceProviderCache* cache() const { return m_cache; }
+        void notifyCacheSizeChanged(int delta) { if (!m_cacheOwned) cacheSizeChanged(delta); }
+        
     private:
+        virtual void cacheSizeChanged(int delta) { UNUSED_PARAM(delta); }
+
         UString m_url;
         bool m_validated;
+        SourceProviderCache* m_cache;
+        bool m_cacheOwned;
     };
 
     class UStringSourceProvider : public SourceProvider {
diff --git a/Source/JavaScriptCore/parser/SyntaxChecker.h b/Source/JavaScriptCore/parser/SyntaxChecker.h
index 1b5497a..8823566 100644
--- a/Source/JavaScriptCore/parser/SyntaxChecker.h
+++ b/Source/JavaScriptCore/parser/SyntaxChecker.h
@@ -112,6 +112,7 @@ public:
     
     static const bool CreatesAST = false;
     static const bool NeedsFreeVariableInfo = false;
+    static const bool CanUseFunctionCache = true;
 
     int createSourceElements() { return 1; }
     ExpressionType makeFunctionCallNode(int, int, int, int, int) { return CallExpr; }