Changeset 94207 in webkit for trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp

Timestamp:

Aug 31, 2011, 11:16:11 AM (14 years ago)

Author:

[email protected]

Message:

Add support for checked arithmetic
​https://bugs.webkit.org/show_bug.cgi?id=67095

Reviewed by Sam Weinig.

../../../../Volumes/Data/git/WebKit/OpenSource/Source/JavaScriptCore:

Add a checked arithmetic class Checked<T> that provides overflow-safe
arithmetic over all integral types. Checked<T> supports addition, subtraction
and multiplication, along with "bool" conversions and equality operators.

Checked<> can be used in either CRASH() on overflow or delayed failure modes,
although the default is to CRASH().

To ensure the code is actually in use (rather than checking in dead code) I've
made a couple of properties in YARR use Checked<int> and Checked<unsigned>
instead of raw value arithmetic. This has resulted in a moderate set of changes,
to YARR - mostly adding .get() calls, but a couple of casts from unsigned long
to unsigned for some uses of sizeof, as Checked<> currently does not support
mixed signed-ness of types wider that 32 bits.

Happily the increased type safety of Checked<> means that it's not possible to
accidentally assign away precision, nor accidentally call integer overload of
a function instead of the bool version.

No measurable regression in performance, and SunSpider claims this patch to be
a progression of 0.3%.

• GNUmakefile.list.am:
• JavaScriptCore.gypi:
• JavaScriptCore.vcproj/WTF/WTF.vcproj:
• JavaScriptCore.xcodeproj/project.pbxproj:
• wtf/CheckedArithmetic.h: Added.

(WTF::CrashOnOverflow::overflowed):
(WTF::CrashOnOverflow::clearOverflow):
(WTF::CrashOnOverflow::hasOverflowed):
(WTF::RecordOverflow::RecordOverflow):
(WTF::RecordOverflow::overflowed):
(WTF::RecordOverflow::clearOverflow):
(WTF::RecordOverflow::hasOverflowed):
(WTF::isInBounds):
(WTF::safeAdd):
(WTF::safeSub):
(WTF::safeMultiply):
(WTF::safeEquals):
(WTF::workAroundClangBug):
(WTF::Checked::Checked):
(WTF::Checked::operator=):
(WTF::Checked::operator++):
(WTF::Checked::operator--):
(WTF::Checked::operator!):
(WTF::Checked::operator UnspecifiedBoolType*):
(WTF::Checked::get):
(WTF::Checked::operator+=):
(WTF::Checked::operator-=):
(WTF::Checked::operator*=):
(WTF::Checked::operator==):
(WTF::Checked::operator!=):
(WTF::operator+):
(WTF::operator-):
(WTF::operator*):

• yarr/YarrInterpreter.cpp:

(JSC::Yarr::ByteCompiler::atomPatternCharacter):
(JSC::Yarr::ByteCompiler::atomCharacterClass):
(JSC::Yarr::ByteCompiler::atomBackReference):
(JSC::Yarr::ByteCompiler::atomParentheticalAssertionEnd):
(JSC::Yarr::ByteCompiler::atomParenthesesSubpatternEnd):
(JSC::Yarr::ByteCompiler::atomParenthesesOnceEnd):
(JSC::Yarr::ByteCompiler::atomParenthesesTerminalEnd):

• yarr/YarrInterpreter.h:

(JSC::Yarr::ByteTerm::ByteTerm):
(JSC::Yarr::ByteTerm::CheckInput):
(JSC::Yarr::ByteTerm::UncheckInput):

• yarr/YarrJIT.cpp:

(JSC::Yarr::YarrGenerator::generateAssertionEOL):
(JSC::Yarr::YarrGenerator::generatePatternCharacterFixed):
(JSC::Yarr::YarrGenerator::generatePatternCharacterGreedy):
(JSC::Yarr::YarrGenerator::backtrackPatternCharacterNonGreedy):
(JSC::Yarr::YarrGenerator::generateCharacterClassOnce):
(JSC::Yarr::YarrGenerator::generateCharacterClassFixed):
(JSC::Yarr::YarrGenerator::generateCharacterClassGreedy):
(JSC::Yarr::YarrGenerator::backtrackCharacterClassNonGreedy):

• yarr/YarrPattern.cpp:

(JSC::Yarr::YarrPatternConstructor::setupAlternativeOffsets):

• yarr/YarrPattern.h:

../../../../Volumes/Data/git/WebKit/OpenSource/Source/WebCore:

Add a forwarding header for CheckedArithmetic.h

• ForwardingHeaders/wtf/CheckedArithmetic.h: Added.

../../../../Volumes/Data/git/WebKit/OpenSource/Tools:

Add test cases for Checked<>

• TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
• TestWebKitAPI/Tests/CheckedArithmeticOperations.cpp: Added.

File:

• trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp (modified) (7 diffs)

trunk/Source/JavaScriptCore/yarr/YarrPattern.cpp

@@ -512 +512 @@
     {
         alternative->m_hasFixedSize = true;
-        unsigned currentInputPosition = initialInputPosition;
+        Checked<unsigned> currentInputPosition = initialInputPosition;
 
         for (unsigned i = 0; i < alternative->m_terms.size(); ++i) {
@@ -521 +521 @@
             case PatternTerm::TypeAssertionEOL:
             case PatternTerm::TypeAssertionWordBoundary:
-                term.inputPosition = currentInputPosition;
+                term.inputPosition = currentInputPosition.unsafeGet();
                 break;
 
             case PatternTerm::TypeBackReference:
-                term.inputPosition = currentInputPosition;
+                term.inputPosition = currentInputPosition.unsafeGet();
                 term.frameLocation = currentCallFrameSize;
                 currentCallFrameSize += YarrStackSpaceForBackTrackInfoBackReference;
@@ -535 +535 @@
 
             case PatternTerm::TypePatternCharacter:
-                term.inputPosition = currentInputPosition;
+                term.inputPosition = currentInputPosition.unsafeGet();
                 if (term.quantityType != QuantifierFixedCount) {
                     term.frameLocation = currentCallFrameSize;
@@ -545 +545 @@
 
             case PatternTerm::TypeCharacterClass:
-                term.inputPosition = currentInputPosition;
+                term.inputPosition = currentInputPosition.unsafeGet();
                 if (term.quantityType != QuantifierFixedCount) {
                     term.frameLocation = currentCallFrameSize;
@@ -560 +560 @@
                     if (term.quantityType != QuantifierFixedCount)
                         currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesOnce;
-                    currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
+                    currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet());
                     // If quantity is fixed, then pre-check its minimum size.
                     if (term.quantityType == QuantifierFixedCount)
                         currentInputPosition += term.parentheses.disjunction->m_minimumSize;
-                    term.inputPosition = currentInputPosition;
+                    term.inputPosition = currentInputPosition.unsafeGet();
                 } else if (term.parentheses.isTerminal) {
                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParenthesesTerminal;
-                    currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition);
-                    term.inputPosition = currentInputPosition;
+                    currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize, currentInputPosition.unsafeGet());
+                    term.inputPosition = currentInputPosition.unsafeGet();
                 } else {
-                    term.inputPosition = currentInputPosition;
-                    setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition);
+                    term.inputPosition = currentInputPosition.unsafeGet();
+                    setupDisjunctionOffsets(term.parentheses.disjunction, 0, currentInputPosition.unsafeGet());
                     currentCallFrameSize += YarrStackSpaceForBackTrackInfoParentheses;
                 }
@@ -579 +579 @@
 
             case PatternTerm::TypeParentheticalAssertion:
-                term.inputPosition = currentInputPosition;
+                term.inputPosition = currentInputPosition.unsafeGet();
                 term.frameLocation = currentCallFrameSize;
-                currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition);
+                currentCallFrameSize = setupDisjunctionOffsets(term.parentheses.disjunction, currentCallFrameSize + YarrStackSpaceForBackTrackInfoParentheticalAssertion, currentInputPosition.unsafeGet());
                 break;
 
@@ -591 +591 @@
         }
 
-        alternative->m_minimumSize = currentInputPosition - initialInputPosition;
+        alternative->m_minimumSize = (currentInputPosition - initialInputPosition).unsafeGet();
         return currentCallFrameSize;
     }