Changeset 146552 in webkit for trunk/Source/JavaScriptCore/interpreter/Interpreter.cpp

Timestamp:

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

Author:

[email protected]

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):

File:

• trunk/Source/JavaScriptCore/interpreter/Interpreter.cpp (modified) (1 diff)

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) {