Changeset 146552 in webkit for trunk/Source/JavaScriptCore/parser/SourceProvider.h

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/parser/SourceProvider.h (modified) (2 diffs)

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;
     };