Refactored string search code.

Refactored string search code.
Made string search state explicit for repreated calls (a StringSearch class).

[Erik Corry, 2010-09-22 13:36:00]

I'm not very keen on this one.  The idea of having an array with constants to
define what the various offsets mean seems like a second best solution compared
with just having a set of different classes and virtual functions.  Instead of
the array you would have objects of the correct instance.

http://codereview.chromium.org/3467010/diff/1/3
File src/runtime.cc (right):

http://codereview.chromium.org/3467010/diff/1/3#newcode4743
src/runtime.cc:4743: index = search.Search(subject, index);
this is probably not getting inlined...

http://codereview.chromium.org/3467010/diff/1/4
File src/string-search.h (right):

http://codereview.chromium.org/3467010/diff/1/4#newcode69
src/string-search.h:69: static const int kStrategyOffset = 0;
This is nasty.  Instead of an integer that indicates the strategy, how about a
pointer to an object that implements the strategy?

http://codereview.chromium.org/3467010/diff/1/4#newcode91
src/string-search.h:91: static inline bool NonAsciiString(Vector<const char>) {
It is preferable for predicate functions to be positively named so you don't get
if (!Not....

http://codereview.chromium.org/3467010/diff/1/4#newcode105
src/string-search.h:105: // for later use.
The comment should reflect the fact that that is currently always the case.

http://codereview.chromium.org/3467010/diff/1/4#newcode152
src/string-search.h:152: // UC16 Needle.
Instead of this comment it is better to have an ASSERT on the sizeof.

http://codereview.chromium.org/3467010/diff/1/4#newcode162
src/string-search.h:162: typedef int (*SearchStrategy)(StringSearch<PatternChar,
SubjectChar>*,  // NOLINT - it's not a cast!
The NOLINT is masking an overlong line here.

http://codereview.chromium.org/3467010/diff/1/4#newcode392
src/string-search.h:392: static int InitialStrategy(StringSearch<PatternChar,
SubjectChar>* search,
This is named like a sort of a getter, but it mutates the object.  Should it be
called "InitializeStrategy"?

http://codereview.chromium.org/3467010/diff/1/4#newcode438
src/string-search.h:438: switch (id) {
This could be a lookup in a static const array.

[Lasse Reichstein, 2010-09-24 08:21:21]

I have removed all the strategy-id-code. It wasn't used for anything yet.
I'm not storing the strategy in the backing-store at all. Eventually I'll want
to use heap-allocated ByteArrays for backing-stores, and I'd prefer not to store
a C-function pointer in those.

I'll have removed the backing store completely for now, and just use default
buffers for each table.

http://codereview.chromium.org/3467010/diff/1/3
File src/runtime.cc (right):

http://codereview.chromium.org/3467010/diff/1/3#newcode4743
src/runtime.cc:4743: index = search.Search(subject, index);
Can you explain why you don't expect it to be inlined?

http://codereview.chromium.org/3467010/diff/1/4
File src/string-search.h (right):

http://codereview.chromium.org/3467010/diff/1/4#newcode69
src/string-search.h:69: static const int kStrategyOffset = 0;
This is done in anticipation of having the backing store supplied by the caller
in some cases, so, e.g., Atom RegExps can keep their BoyerMoore tables between
calls.

I have made accessors on the search object to get the int* of the buffers, so
each search/populate function doesn't need to know about the backing store.

http://codereview.chromium.org/3467010/diff/1/4#newcode91
src/string-search.h:91: static inline bool NonAsciiString(Vector<const char>) {
Done.

http://codereview.chromium.org/3467010/diff/1/4#newcode105
src/string-search.h:105: // for later use.
Done.

http://codereview.chromium.org/3467010/diff/1/4#newcode152
src/string-search.h:152: // UC16 Needle.
Done.

http://codereview.chromium.org/3467010/diff/1/4#newcode162
src/string-search.h:162: typedef int (*SearchStrategy)(StringSearch<PatternChar,
SubjectChar>*,  // NOLINT - it's not a cast!
Rewrapped.

http://codereview.chromium.org/3467010/diff/1/4#newcode392
src/string-search.h:392: static int InitialStrategy(StringSearch<PatternChar,
SubjectChar>* search,
No, this should be a noun, it is the strategy, not a getter for it, or an
initializer for anything. It is the initial strategy for complex searching -
it's the strategy for linear search with bailout to BMH (the name sucks,
though).
I have removed the strategy objects and use pointers to the search functions
themselves now (which means that the function is now called InitialSearch - a
better name will be appreciated).

http://codereview.chromium.org/3467010/diff/1/4#newcode438
src/string-search.h:438: switch (id) {
Ids have been removed (eventually we'll want to keep BoyerMoore tables between
calls, and then the current state of those needs to be stored and the strategy
should be initialized based on that state, but no need to complicate the code
yet.

[Lasse Reichstein, 2010-09-24 08:23:27]

I have removed all the strategy-id-code. It wasn't used for anything yet.
I'm not storing the strategy in the backing-store at all. Eventually I'll want
to use heap-allocated ByteArrays for backing-stores, and I'd prefer not to store
a C-function pointer in those.

I'll have removed the backing store completely for now, and just use default
buffers for each table.

I have also made more functions methods of the search object, instead of static
functions. 

And I have reintroduced the single-character search. Using pointers to search
implementations, the dispatch only happens once, so there is less overhead of
specialized searches.

[Erik Corry, 2010-09-28 13:16:41]

LGTM

http://codereview.chromium.org/3467010/diff/9001/10001
File src/SConscript (right):

http://codereview.chromium.org/3467010/diff/9001/10001#newcode103
src/SConscript:103: string-search.cc
What about xcode and MSVC?

http://codereview.chromium.org/3467010/diff/9001/10003
File src/string-search.h (right):

http://codereview.chromium.org/3467010/diff/9001/10003#newcode85
src/string-search.h:85: // Table used temporarily while building the BoyerMoore
goodsuffix
goodsuffix -> good suffix

http://codereview.chromium.org/3467010/diff/9001/10003#newcode121
src/string-search.h:121: // ASCII Needle;
Needle -> needle
and below.

http://codereview.chromium.org/3467010/diff/9001/10003#newcode353
src/string-search.h:353: 
Double space here and lots of other places.

http://codereview.chromium.org/3467010/diff/9001/10003#newcode415
src/string-search.h:415: strategy_ = &BoyerMooreSearch;
This is non-intuitive.  The name of this function doesn't suggest that the
strategy is changed when the tables are calculated.  I think this should be done
explicitly at the points where the Populate... method is called.

http://codereview.chromium.org/3467010/diff/9001/10003#newcode498
src/string-search.h:498: strategy_ = &BoyerMooreHorspoolSearch;
And here.

http://codereview.chromium.org/3467010/diff/9001/10003#newcode559
src/string-search.h:559: // object should only be constructed once and then
called multiple times.
Is this comment accurate?  It seems like the fields and methods are all static. 
Is an object being created?

[Lasse Reichstein, 2010-09-29 11:01:20]

http://codereview.chromium.org/3467010/diff/9001/10001
File src/SConscript (right):

http://codereview.chromium.org/3467010/diff/9001/10001#newcode103
src/SConscript:103: string-search.cc
I added the files to the visual-studio projects.
I see no way to manually edit the xcode project.

http://codereview.chromium.org/3467010/diff/9001/10003
File src/string-search.h (right):

http://codereview.chromium.org/3467010/diff/9001/10003#newcode85
src/string-search.h:85: // Table used temporarily while building the BoyerMoore
goodsuffix
On 2010/09/28 13:16:49, Erik Corry wrote:
> goodsuffix -> good suffix

Done.

http://codereview.chromium.org/3467010/diff/9001/10003#newcode121
src/string-search.h:121: // ASCII Needle;
On 2010/09/28 13:16:49, Erik Corry wrote:
> Needle -> needle
> and below.

Done.

http://codereview.chromium.org/3467010/diff/9001/10003#newcode353
src/string-search.h:353: 
Done.

http://codereview.chromium.org/3467010/diff/9001/10003#newcode415
src/string-search.h:415: strategy_ = &BoyerMooreSearch;
Moved to just after the call to Populate...

http://codereview.chromium.org/3467010/diff/9001/10003#newcode498
src/string-search.h:498: strategy_ = &BoyerMooreHorspoolSearch;
Too.

http://codereview.chromium.org/3467010/diff/9001/10003#newcode559
src/string-search.h:559: // object should only be constructed once and then
called multiple times.
The Search function isn't static, nor are the pattern_ and strategy_ fields. An
object should be created.
Rewording the comment to be more clear.