Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2424453002:
Handle overflow, underflow in XPath substring position, length. (Closed)
|
Created:
4 years, 2 months ago by dominicc (has gone to gerrit) Modified:
4 years, 1 month ago Reviewers:
yosin_UTC9 CC:
blink-reviews, chromium-reviews, dominicc+watchlist_chromium.org Target Ref:
refs/pending/heads/master Project:
chromium Visibility:
Public. |
DescriptionHandle overflow, underflow in XPath substring position, length.
BUG=634167
Committed: https://crrev.com/047653201597a4e5c3912d8c2c35adaa2ed6e6ec
Cr-Commit-Position: refs/heads/master@{#428284}
Patch Set 1 #Patch Set 2 : Simplify by converting less. #Patch Set 3 : Make windows happy. #
Total comments: 10
Patch Set 4 : Try direct solution. More tests. #
Total comments: 10
Patch Set 5 : Feedback. #
Total comments: 1
Patch Set 6 : Address nit. #
Messages
Total messages: 42 (26 generated)
The CQ bit was checked by dominicc@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...)
The CQ bit was checked by dominicc@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: win_chromium_compile_dbg_ng on master.tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_comp...)
The CQ bit was checked by dominicc@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
dominicc@chromium.org changed reviewers: + yosin@chromium.org
PTAL
This is an interesting one; to *really* test this you need to do a ubsan build
and then load this file in content shell:
<!DOCTYPE html>
<script>
document.evaluate(
"substring(\'12345\', 0, 9223372036854775571)",
document, null, XPathResult.ANY_TYPE, null).stringValue);
</script>
Before this fix, UBSAN will complain:
../../third_party/WebKit/Source/core/xml/XPathFunctions.cpp:553:11: runtime
error: signed integer overflow: -9223372036854775808 - 1 cannot be represented
in type 'long'
#0 0x7f578ab03d1e
(/usr/local/google/work/ca/src/out/ubsan/./libblink_core.so+0x2496d1e)
... etc.
This basically avoids the issue by making the conversion to indices implicit by
searching for indexes with certain properties. This is basically how the spec
language has it.
I experimented with converting directly, but it quickly gets messy because the
number of cases explode with pos and len being +/- NaN, +/- Inf, representable
by unsigned or not, etc.
Oops: .stringValue); -> .stringValue; I was logging the value. The value should be "12345" of course and it is in either case; this is about avoiding the undefined behavior.
https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctions.cpp (right): https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:541: lo = mid + 1; Note: When |pos| is NaN, |mid >= pos| is false. So, this clause is executed. findSubstringStartIndex(1, 2, NaN) => 2 https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:569: String s = arg(0)->evaluate(context).toString(); nit: It is better to avoid using one letter variable name. https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:574: unsigned start = findSubstringStartIndex(1, s.length() + 1, pos); WDYT? Explicit handling of NaN and Infinity? In this way, we don't need to remember result of numeric comparison with NaN, e.g. 1 > NaN, 2 < NaN, Inifity < NaN, // |pos| and |len| can be NaN, +Inifity/-Infinity // |length| should be a finite number. std::pair<double, dobule> computeStartEnd(pos, len, length) { DCHECK(std::isfinite(length)) << length; const double posend = pos + len; if (std::isnnan(pos) && std::isnan(posend)) return std::make_pair(1, 1); if (std::isnan(pos)) return std::make_pair(1, std::max(1, std::min(posend, length)); if (std::isnan(posend)) return std::make_pair(1, 1); return std::make_pair(std::min(std::max(1, pos), length); } https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctionsTest.cpp (right): https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctionsTest.cpp:17: class XPathContext { Too avoid name crash, it is better to enclose XPathContext in anonymous namespace. https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctionsTest.cpp:27: Member<Document> m_document; nit: s/Member<Document>/const Member<Document>/ https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctionsTest.cpp:67: TEST(XPathFunctionsTest, substring_extremePositionLength) { We want to have test cases for NaN and +Inifity/-Ininity? We may want to have -0.
Thanks for your review. I'll work through your other feedback but I wanted to share some points with you--I really think searching for the bounds is simpler than handling explicit float cases. https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctions.cpp (right): https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:541: lo = mid + 1; On 2016/10/17 at 03:56:00, Yosi_UTC9 wrote: > Note: When |pos| is NaN, |mid >= pos| is false. So, this clause is executed. > findSubstringStartIndex(1, 2, NaN) => 2 What's wrong with that? https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:574: unsigned start = findSubstringStartIndex(1, s.length() + 1, pos); On 2016/10/17 at 03:56:00, Yosi_UTC9 wrote: > WDYT? Explicit handling of NaN and Infinity? > In this way, we don't need to remember result of numeric comparison with NaN, e.g. 1 > NaN, 2 < NaN, Inifity < NaN, > > // |pos| and |len| can be NaN, +Inifity/-Infinity > // |length| should be a finite number. > std::pair<double, dobule> computeStartEnd(pos, len, length) { > DCHECK(std::isfinite(length)) << length; > const double posend = pos + len; > if (std::isnnan(pos) && std::isnan(posend)) > return std::make_pair(1, 1); > if (std::isnan(pos)) > return std::make_pair(1, std::max(1, std::min(posend, length)); > if (std::isnan(posend)) > return std::make_pair(1, 1); > return std::make_pair(std::min(std::max(1, pos), length); > } I don't think this works. If pos is -inf and end is inf, then XPath says you should return the whole string but you will return the empty string. I've written the version that handles these cases explicitly. It's very complex. Searching for the bounds is simpler. The spec is defined in terms of < and >= so the implementation which searches is in some sense more direct.
https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctions.cpp (right): https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:541: lo = mid + 1; On 2016/10/21 at 05:28:45, dominicc wrote: > On 2016/10/17 at 03:56:00, Yosi_UTC9 wrote: > > Note: When |pos| is NaN, |mid >= pos| is false. So, this clause is executed. > > findSubstringStartIndex(1, 2, NaN) => 2 > > What's wrong with that? Sorry for confusion. This is my notes. https://codereview.chromium.org/2424453002/diff/40001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:574: unsigned start = findSubstringStartIndex(1, s.length() + 1, pos); On 2016/10/21 at 05:28:45, dominicc wrote: > On 2016/10/17 at 03:56:00, Yosi_UTC9 wrote: > > WDYT? Explicit handling of NaN and Infinity? > > In this way, we don't need to remember result of numeric comparison with NaN, e.g. 1 > NaN, 2 < NaN, Inifity < NaN, > > > > // |pos| and |len| can be NaN, +Inifity/-Infinity > > // |length| should be a finite number. > > std::pair<double, dobule> computeStartEnd(pos, len, length) { > > DCHECK(std::isfinite(length)) << length; > > const double posend = pos + len; > > if (std::isnnan(pos) && std::isnan(posend)) > > return std::make_pair(1, 1); > > if (std::isnan(pos)) > > return std::make_pair(1, std::max(1, std::min(posend, length)); > > if (std::isnan(posend)) > > return std::make_pair(1, 1); > > return std::make_pair(std::min(std::max(1, pos), length); > > } > > I don't think this works. If pos is -inf and end is inf, then XPath says you should return the whole string but you will return the empty string. > > I've written the version that handles these cases explicitly. It's very complex. Searching for the bounds is simpler. The spec is defined in terms of < and >= so the implementation which searches is in some sense more direct. OK. Simpler code is better.
The CQ bit was checked by dominicc@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
PTAL I took another run at handling NaN, etc. explicitly. I realized your code handles infinities quite elegantly with max(min(... Is there a -NaN and does std::isnan detect it?
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
On 2016/10/24 at 02:48:58, dominicc wrote: > PTAL > > I took another run at handling NaN, etc. explicitly. I realized your code handles infinities quite elegantly with max(min(... > > Is there a -NaN and does std::isnan detect it? Yes, there is -NaN. std::isnan() detects both.
https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctions.cpp (right): https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:537: static double clip(const double& lo, const double& value, const double& hi) { It is better to use |double| instead of |const double&|. x64 ABI passes first four(MSVC)/eight(GCC) floating-point value in register. https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:544: static std::pair<unsigned, unsigned> findSubstringStartEnd(double start, |computeSubstringStartEnd()|? as comment says? https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:552: start = clip(1., start, maxLen + 1); nit: s/1./1.0/ to avoid sequential punctuation. https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:553: end = clip(start, end, maxLen + 1); Better to use another variable rather than changing variable, e.g. clippedStart and clippedEnd https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:567: double pos = FunRound::round(arg(1)->evaluate(context).toNumber()); nit: s/double/const double/ https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:568: double len = argCount() == 3 nit: s/double/const double/ https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:571: auto bounds = findSubstringStartEnd(pos, len, sourceString.length()); nit: s/auto/const auto/ https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctionsTest.cpp (right): https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctionsTest.cpp:124: } Let's have tests for famous floating-point values: std::numeric_limits<double>::denorm_min() std::numeric_limits<double>::lowest() std::numeric_limits<double>::epsilon() std::numeric_limits<double>::min() std::numeric_limits<double>::max() std::numeric_limits<double>::quiet_NaN() c.f. http://en.cppreference.com/w/cpp/types/numeric_limits
https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctions.cpp (right): https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:537: static double clip(const double& lo, const double& value, const double& hi) { On 2016/10/24 at 05:45:36, Yosi_UTC9 wrote: > It is better to use |double| instead of |const double&|. > x64 ABI passes first four(MSVC)/eight(GCC) floating-point value in register. Oops, there is |std::clamp(v, lo, hi)|; all parameters should be finite number. http://en.cppreference.com/w/cpp/algorithm/clamp
https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctions.cpp (right): https://codereview.chromium.org/2424453002/diff/60001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:537: static double clip(const double& lo, const double& value, const double& hi) { On 2016/10/24 at 06:07:42, Yosi_UTC9 wrote: > On 2016/10/24 at 05:45:36, Yosi_UTC9 wrote: > > It is better to use |double| instead of |const double&|. > > x64 ABI passes first four(MSVC)/eight(GCC) floating-point value in register. > > Oops, there is |std::clamp(v, lo, hi)|; all parameters should be finite number. > http://en.cppreference.com/w/cpp/algorithm/clamp Sorry for confusion. |std::clamp()| is available from C++17
The CQ bit was checked by dominicc@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Thank you for the feedback PTAL
lgtm w/ nit s/clip/clamp/ to follow C++17 https://codereview.chromium.org/2424453002/diff/80001/third_party/WebKit/Sour... File third_party/WebKit/Source/core/xml/XPathFunctions.cpp (right): https://codereview.chromium.org/2424453002/diff/80001/third_party/WebKit/Sour... third_party/WebKit/Source/core/xml/XPathFunctions.cpp:537: static double clip(const double lo, const double value, const double hi) { Since C++17 introduces this function as |std::clamp()|, it is better to name |clamp()| and please add TODO to use |std::clamp()| on C++17.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
The CQ bit was checked by dominicc@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by dominicc@chromium.org
The CQ bit was checked by dominicc@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from yosin@chromium.org Link to the patchset: https://codereview.chromium.org/2424453002/#ps100001 (title: "Address nit.")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Message was sent while issue was closed.
Committed patchset #6 (id:100001)
Message was sent while issue was closed.
Description was changed from ========== Handle overflow, underflow in XPath substring position, length. BUG=634167 ========== to ========== Handle overflow, underflow in XPath substring position, length. BUG=634167 Committed: https://crrev.com/047653201597a4e5c3912d8c2c35adaa2ed6e6ec Cr-Commit-Position: refs/heads/master@{#428284} ==========
Message was sent while issue was closed.
Patchset 6 (id:??) landed as https://crrev.com/047653201597a4e5c3912d8c2c35adaa2ed6e6ec Cr-Commit-Position: refs/heads/master@{#428284} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
