Changeset 146552 in webkit

Timestamp:

Mar 21, 2013 6:56:17 PM (11 years ago)

Author:

mark.lam@apple.com

Message:

Source/JavaScriptCore: Fix O(n^{2) op_debug bytecode charPosition to column computation.
​https://bugs.webkit.org/show_bug.cgi?id=112957.}

Reviewed by Geoffrey Garen.

The previous algorithm does a linear reverse scan of the source string
to find the line start for any given char position. This results in a
O(n^{2) algortithm when the source string has no line breaks.}

The new algorithm computes a line start column table for a
SourceProvider on first use. This line start table is used to fix up
op_debug's charPosition operand into a column operand when an
UnlinkedCodeBlock is linked into a CodeBlock. The initialization of
the line start table is O(n), and the CodeBlock column fix up is
O(log(n)).

• bytecode/CodeBlock.cpp:

(JSC::CodeBlock::dumpBytecode):
(JSC::CodeBlock::CodeBlock): - do column fix up.

• interpreter/Interpreter.cpp:

(JSC::Interpreter::debug): - no need to do column fixup anymore.

• interpreter/Interpreter.h:
• jit/JITStubs.cpp:

(JSC::DEFINE_STUB_FUNCTION):

• llint/LLIntSlowPaths.cpp:

(JSC::LLInt::LLINT_SLOW_PATH_DECL):

• parser/SourceProvider.cpp:

(JSC::SourceProvider::lineStarts):
(JSC::charPositionExtractor):
(JSC::SourceProvider::charPositionToColumnNumber):

• initialize line start column table if needed.
• look up line start for the given char position.
• parser/SourceProvider.h:

Source/WTF: Introducing String::findNextLineStart().
​https://bugs.webkit.org/show_bug.cgi?id=112957.

Reviewed by Geoffrey Garen.

This is replaces String::reverseFindLineTerminator() in the JSC
debugger's code for computing column numbers.

• wtf/text/StringImpl.cpp:

(WTF::StringImpl::findNextLineStart):

• wtf/text/StringImpl.h:

(WTF::findNextLineStart):

• wtf/text/WTFString.h:

(WTF::String::findNextLineStart):

Location:

trunk/Source

Files:

• JavaScriptCore/ChangeLog (modified) (1 diff)
• JavaScriptCore/bytecode/CodeBlock.cpp (modified) (2 diffs)
• JavaScriptCore/interpreter/Interpreter.cpp (modified) (1 diff)
• JavaScriptCore/interpreter/Interpreter.h (modified) (1 diff)
• JavaScriptCore/jit/JITStubs.cpp (modified) (1 diff)
• JavaScriptCore/llint/LLIntSlowPaths.cpp (modified) (1 diff)
• JavaScriptCore/parser/SourceProvider.cpp (modified) (2 diffs)
• JavaScriptCore/parser/SourceProvider.h (modified) (2 diffs)
• WTF/ChangeLog (modified) (1 diff)
• WTF/wtf/text/StringImpl.cpp (modified) (1 diff)
• WTF/wtf/text/StringImpl.h (modified) (2 diffs)
• WTF/wtf/text/WTFString.h (modified) (1 diff)

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2013-03-21  Mark Lam  <mark.lam@apple.com>
+
+        Fix O(n^2) op_debug bytecode charPosition to column computation.
+        https://bugs.webkit.org/show_bug.cgi?id=112957.
+
+        Reviewed by Geoffrey Garen.
+
+        The previous algorithm does a linear reverse scan of the source string
+        to find the line start for any given char position. This results in a
+        O(n^2) algortithm when the source string has no line breaks.
+
+        The new algorithm computes a line start column table for a
+        SourceProvider on first use. This line start table is used to fix up
+        op_debug's charPosition operand into a column operand when an
+        UnlinkedCodeBlock is linked into a CodeBlock. The initialization of
+        the line start table is O(n), and the CodeBlock column fix up is
+        O(log(n)).
+
+        * bytecode/CodeBlock.cpp:
+        (JSC::CodeBlock::dumpBytecode): 
+        (JSC::CodeBlock::CodeBlock): - do column fix up.
+        * interpreter/Interpreter.cpp:
+        (JSC::Interpreter::debug): - no need to do column fixup anymore.
+        * interpreter/Interpreter.h:
+        * jit/JITStubs.cpp:
+        (JSC::DEFINE_STUB_FUNCTION):
+        * llint/LLIntSlowPaths.cpp:
+        (JSC::LLInt::LLINT_SLOW_PATH_DECL):
+        * parser/SourceProvider.cpp:
+        (JSC::SourceProvider::lineStarts):
+        (JSC::charPositionExtractor):
+        (JSC::SourceProvider::charPositionToColumnNumber):
+        - initialize line start column table if needed.
+        - look up line start for the given char position.
+        * parser/SourceProvider.h:
+
 2013-03-21  Filip Pizlo  <fpizlo@apple.com>
 

trunk/Source/JavaScriptCore/bytecode/CodeBlock.cpp

@@ -1474 +1474 @@
             int firstLine = (++it)->u.operand;
             int lastLine = (++it)->u.operand;
-            int charPosition = (++it)->u.operand;
-            out.printf("[%4d] debug\t\t %s, %d, %d, %d", location, debugHookName(debugHookID), firstLine, lastLine, charPosition);
+            int column = (++it)->u.operand;
+            out.printf("[%4d] debug\t\t %s, %d, %d, %d", location, debugHookName(debugHookID), firstLine, lastLine, column);
             break;
         }
@@ -2004 +2004 @@
             break;
         }
+
+        case op_debug: {
+            size_t charPosition = pc[i + 4].u.operand;
+            size_t actualCharPosition = charPosition + m_sourceOffset;
+            size_t column = m_source->charPositionToColumnNumber(actualCharPosition);
+            instructions[i + 4] = column;
+            break;
+        }
+
         default:
             break;

trunk/Source/JavaScriptCore/interpreter/Interpreter.cpp

@@ -1334 +1334 @@
 }
 
-NEVER_INLINE void Interpreter::debug(CallFrame* callFrame, DebugHookID debugHookID, int firstLine, int lastLine, int charPosition)
+NEVER_INLINE void Interpreter::debug(CallFrame* callFrame, DebugHookID debugHookID, int firstLine, int lastLine, int column)
 {
     Debugger* debugger = callFrame->dynamicGlobalObject()->debugger();
     if (!debugger)
         return;
-
-    CodeBlock* codeBlock = callFrame->codeBlock();
-    size_t actualCharPosition = charPosition + codeBlock->sourceOffset();
-
-    SourceProvider* provider = codeBlock->source();
-    String source = provider->source();
-    size_t lineTerminatorPosition = source.reverseFindLineTerminator(actualCharPosition);
-    int column;
-    if (lineTerminatorPosition != notFound)
-        column = actualCharPosition - (lineTerminatorPosition + 1);
-    else
-        column = actualCharPosition;
 
     switch (debugHookID) {

trunk/Source/JavaScriptCore/interpreter/Interpreter.h

@@ -231 +231 @@
 
         NEVER_INLINE HandlerInfo* throwException(CallFrame*&, JSValue&, unsigned bytecodeOffset);
-        NEVER_INLINE void debug(CallFrame*, DebugHookID, int firstLine, int lastLine, int charPosition);
+        NEVER_INLINE void debug(CallFrame*, DebugHookID, int firstLine, int lastLine, int column);
         static const String getTraceLine(CallFrame*, StackFrameCodeType, const String&, int);
         JS_EXPORT_PRIVATE static void getStackTrace(JSGlobalData*, Vector<StackFrame>& results);

trunk/Source/JavaScriptCore/jit/JITStubs.cpp

@@ -3469 +3469 @@
     int firstLine = stackFrame.args[1].int32();
     int lastLine = stackFrame.args[2].int32();
-    int charPosition = stackFrame.args[3].int32();
-
-    stackFrame.globalData->interpreter->debug(callFrame, static_cast<DebugHookID>(debugHookID), firstLine, lastLine, charPosition);
+    int column = stackFrame.args[3].int32();
+
+    stackFrame.globalData->interpreter->debug(callFrame, static_cast<DebugHookID>(debugHookID), firstLine, lastLine, column);
 }
 

trunk/Source/JavaScriptCore/llint/LLIntSlowPaths.cpp

@@ -1638 +1638 @@
     int firstLine = pc[2].u.operand;
     int lastLine = pc[3].u.operand;
-    int charPosition = pc[4].u.operand;
-
-    globalData.interpreter->debug(exec, static_cast<DebugHookID>(debugHookID), firstLine, lastLine, charPosition);
+    int column = pc[4].u.operand;
+
+    globalData.interpreter->debug(exec, static_cast<DebugHookID>(debugHookID), firstLine, lastLine, column);
     
     LLINT_END();

trunk/Source/JavaScriptCore/parser/SourceProvider.cpp

@@ -26 +26 @@
 #include "config.h"
 #include "SourceProvider.h"
+#include <wtf/StdLibExtras.h>
 #include <wtf/TCSpinLock.h>
 
@@ -42 +43 @@
 }
 
+Vector<size_t>& SourceProvider::lineStarts()
+{
+    if (!m_lineStarts) {
+        m_lineStarts = adoptPtr(new Vector<size_t>());
+        String source = this->source();
+        size_t index = 0;
+        do {
+            m_lineStarts->append(index);
+            index = source.findNextLineStart(index);
+        } while (index != notFound);
+        m_lineStarts->shrinkToFit();
+    }
+    return *m_lineStarts;
+}
+
+
+static inline size_t charPositionExtractor(const size_t* value)
+{
+    return *value;
+}
+
+size_t SourceProvider::charPositionToColumnNumber(size_t charPosition)
+{
+    Vector<size_t>& lineStarts = this->lineStarts();
+    size_t* data = lineStarts.data();
+    size_t dataSize = lineStarts.size();
+
+    // Get the nearest line start entry (which could be to the left or to the
+    // right of the requested charPosition.
+    const size_t* line = approximateBinarySearch<size_t, size_t>(data, dataSize, charPosition, charPositionExtractor);
+    size_t lineStartPosition = *line;
+
+    if (lineStartPosition > charPosition) {
+        if (data < line) {
+            line--;
+            lineStartPosition = *line;
+        }
+    }
+
+    ASSERT(data <= line);
+    ASSERT(lineStartPosition <= charPosition);
+    return charPosition - lineStartPosition;
+}
+
 static TCMalloc_SpinLock providerIdLock = SPINLOCK_INITIALIZER;
 

trunk/Source/JavaScriptCore/parser/SourceProvider.h

@@ -67 +67 @@
         void setValid() { m_validated = true; }
 
+        size_t charPositionToColumnNumber(size_t charPosition);
+
     private:
 
         JS_EXPORT_PRIVATE void getID();
+        Vector<size_t>& lineStarts();
 
         String m_url;
@@ -75 +78 @@
         bool m_validated : 1;
         uintptr_t m_id : sizeof(uintptr_t) * 8 - 1;
+
+        OwnPtr<Vector<size_t> > m_lineStarts;
     };
 

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2013-03-21  Mark Lam  <mark.lam@apple.com>
+
+        Introducing String::findNextLineStart().
+        https://bugs.webkit.org/show_bug.cgi?id=112957.
+
+        Reviewed by Geoffrey Garen.
+
+        This is replaces String::reverseFindLineTerminator() in the JSC
+        debugger's code for computing column numbers.
+
+        * wtf/text/StringImpl.cpp:
+        (WTF::StringImpl::findNextLineStart):
+        * wtf/text/StringImpl.h:
+        (WTF::findNextLineStart):
+        * wtf/text/WTFString.h:
+        (WTF::String::findNextLineStart):
+
 2013-03-21  Adam Barth  <abarth@webkit.org>
 

trunk/Source/WTF/wtf/text/StringImpl.cpp

@@ -1117 +1117 @@
 }
 
-size_t StringImpl::reverseFindLineTerminator(unsigned index)
-{
-    if (is8Bit())
-        return WTF::reverseFindLineTerminator(characters8(), m_length, index);
-    return WTF::reverseFindLineTerminator(characters16(), m_length, index);
+size_t StringImpl::findNextLineStart(unsigned index)
+{
+    if (is8Bit())
+        return WTF::findNextLineStart(characters8(), m_length, index);
+    return WTF::findNextLineStart(characters16(), m_length, index);
 }
 

trunk/Source/WTF/wtf/text/StringImpl.h

@@ -698 +698 @@
     WTF_EXPORT_STRING_API size_t findIgnoringCase(StringImpl*, unsigned index = 0);
 
-    WTF_EXPORT_STRING_API size_t reverseFindLineTerminator(unsigned index = UINT_MAX);
+    WTF_EXPORT_STRING_API size_t findNextLineStart(unsigned index = UINT_MAX);
+
     WTF_EXPORT_STRING_API size_t reverseFind(UChar, unsigned index = UINT_MAX);
     WTF_EXPORT_STRING_API size_t reverseFind(StringImpl*, unsigned index = UINT_MAX);
@@ -1150 +1151 @@
 
 template<typename CharacterType>
+inline size_t findNextLineStart(const CharacterType* characters, unsigned length, unsigned index = 0)
+{
+    while (index < length) {
+        CharacterType c = characters[index++];
+        if ((c != '\n') && (c != '\r'))
+            continue;
+
+        // There can only be a start of a new line if there are more characters
+        // beyond the current character.
+        if (index < length) {
+            // The 3 common types of line terminators are 1. \r\n (Windows), 
+            // 2. \r (old MacOS) and 3. \n (Unix'es).
+
+            if (c == '\n')
+                return index; // Case 3: just \n.
+
+            CharacterType c2 = characters[index];
+            if (c2 != '\n')
+                return index; // Case 2: just \r.
+
+            // Case 1: \r\n.
+            // But, there's only a start of a new line if there are more
+            // characters beyond the \r\n.
+            if (++index < length)
+                return index; 
+        }
+    }
+    return notFound;
+}
+
+template<typename CharacterType>
 inline size_t reverseFindLineTerminator(const CharacterType* characters, unsigned length, unsigned index = UINT_MAX)
 {

trunk/Source/WTF/wtf/text/WTFString.h

@@ -262 +262 @@
         { return m_impl ? m_impl->find(str, start) : notFound; }
 
-    size_t reverseFindLineTerminator(unsigned start = UINT_MAX) const
-        { return m_impl ? m_impl->reverseFindLineTerminator(start) : notFound; }
+    size_t findNextLineStart(unsigned start = 0) const
+        { return m_impl ? m_impl->findNextLineStart(start) : notFound; }
 
     // Find the last instance of a single character or string.