New issue
Advanced search Search tips
Note: Color blocks (like █ or █) mean that a user may not be available. Tooltip shows the reason.

Issue 756585 link

Starred by 1 user
Status: Fixed
Owner:
█ nick@chromium.org
not working at Google anymore
Closed: Sep 2017
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 3
Type: Bug



Sign in to add a comment

base::ReplaceSubstringsAfterOffset will get into an infinite loop if find string is empty.

Project Member Reported by cmumford@chromium.org, Aug 17 2017 
Chrome Version: (copy from chrome://version)
OS: All (verified on Linux)

What steps will reproduce the problem?
(1) Compile & run the following code:

std::string str("This is a test string.");
std::string find_this = "";
std::string replace_with = "...";
base::ReplaceSubstringsAfterOffset(&str, 0u, find_this, replace_with);

What is the expected result?
No infinite loop

What happens instead?
Infinite loop ON RELEASE BUILD.

Comment 1 by cmumford@chromium.org, Aug 17 2017 

The implementation of ReplaceSubstringsAfterOffset has a DCHECK to assert that find_this is not empty, but no release check. The header file (string_util.h) does not explicitly state that find_this cannot be empty - but it surely makes sense.

If there was another memory corruption bug then we could get into this infinite loop, so I wonder if we should convert this to a release check?
Project Member

Comment 2 by bugdroid1@chromium.org, Sep 26 2017 

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/b1e364df6b2f944f8879737a61e45a991a96f518

commit b1e364df6b2f944f8879737a61e45a991a96f518
Author: Nick Carter <nick@chromium.org>
Date: Tue Sep 26 18:28:45 2017

Fix O(n^2) performance in base::ReplaceChars() and base::RemoveChars()

ReplaceChars and RemoveChars can actually be implemented in terms of
the algorithm used for ReplaceSubstringsAfterOffset(), which is already
finely tuned to do this operation in linear time. The only difference
is to swap out which find function is used, which is accomplished here
by a boolean parameter.

Bug:  756585 
Bug:  760330 
Change-Id: I780dc996e360b75dc8845af90cfc7e2afed2cd6d
Reviewed-on: https://chromium-review.googlesource.com/642357
Commit-Queue: Nick Carter <nick@chromium.org>
Reviewed-by: Daniel Cheng <dcheng@chromium.org>
Cr-Commit-Position: refs/heads/master@{#504430}
[modify] https://crrev.com/b1e364df6b2f944f8879737a61e45a991a96f518/base/strings/string_util.cc
[modify] https://crrev.com/b1e364df6b2f944f8879737a61e45a991a96f518/base/strings/string_util_unittest.cc

Comment 3 by nick@chromium.org, Sep 26 2017

Owner: nick@chromium.org
Status: Fixed (was: Untriaged)
Fixed by https://chromium-review.googlesource.com/c/chromium/src/+/642357
►

Sign in to add a comment