Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
2963463002:
[Zucchini] Generic suffix array algorithms. (Closed)
Description[Zucchini] Generic suffix array algorithms.
This introduces interface, implementation and unittests for:
- suffix array construction using naive sort
- suffix array construction using SA-IS
- binary search in a suffix array
BUG=729154
Review-Url: https://codereview.chromium.org/2963463002
Cr-Commit-Position: refs/heads/master@{#485769}
Committed: https://chromium.googlesource.com/chromium/src/+/a1b45802a88101e23d1c0e485165255807702ca7
Patch Set 1 #Patch Set 2 : Make gcc happy #
Total comments: 13
Patch Set 3 : CR-huangs #Patch Set 4 : Fix SearchExact performance #
Total comments: 7
Patch Set 5 : Make ustring conversions pretty #
Total comments: 29
Patch Set 6 : CR-huangs-34 #Patch Set 7 : NIT corrections in comments #
Total comments: 60
Patch Set 8 : CR-huangs-79 #Patch Set 9 : Fix comment issue #
Total comments: 2
Patch Set 10 : Fix comment #Patch Set 11 : Rebase #Patch Set 12 : Fix trybots #Patch Set 13 : Rebase #
Total comments: 6
Messages
Total messages: 67 (41 generated)
Description was changed from ========== Generic suffix array algorithms for Zucchini. This introduces interface, implementation and unittests for: - suffix array construction using naive sort - suffix array construction using SA-IS - binary search in a suffix array BUG= ========== to ========== Generic suffix array algorithms for Zucchini. This introduces interface, implementation and unittests for: - suffix array construction using naive sort - suffix array construction using SA-IS - binary search in a suffix array BUG= ==========
etiennep@google.com changed reviewers: + huangs@chromium.org
The CQ bit was checked by etiennep@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: linux_chromium_compile_dbg_ng on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
The CQ bit was checked by etiennep@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...
self review https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... File chrome/installer/zucchini/suffix_array_unittest.cc (right): https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:7: #include <string> #include <initializer_list>
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
Superficial comments, and comments to add more tests.
To be thorough, might be worthwhile to ensure every branch in the algo is
covered. Maybe use something like
struct IAmHere {
IAmHere(int line_in) : line(line_in) {}
~IAmHere() {
printf("Line never reached: %d\n", line);
}
void touch() { touched = true; }
int line;
bool touched = false;
};
...
if (blah) {
static IAmHere iah(__LINE__); iah.touch(); // Put into every branch.
...
} else {
static IAmHere iah(__LINE__); iah.touch(); // Put into every branch.
...
}
https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi...
File chrome/installer/zucchini/suffix_array.h (right):
https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi...
chrome/installer/zucchini/suffix_array.h:69: // This sentinel does not exist in
memory and is only treated implicitely.
Unwrap comments to fit.
TYPO: implicitly
Period at end.
https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi...
chrome/installer/zucchini/suffix_array.h:350: if (length < 2)
Should |suffix_array| be assigned [0] for the case length == 1?
https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi...
chrome/installer/zucchini/suffix_array.h:419: std::vector<typename
StrRng::size_type> MakeSuffixArray(Algorithm algorithm,
|algorithm| is unused?
https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi...
File chrome/installer/zucchini/suffix_array_unittest.cc (right):
https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi...
chrome/installer/zucchini/suffix_array_unittest.cc:7: #include <string>
#include <cstddef> for size_t
https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi...
chrome/installer/zucchini/suffix_array_unittest.cc:226:
Please also adapt the more comprehensive test in
https://cs.chromium.org/chromium/src/courgette/third_party/bsdiff/bsdiff_sear...
Note that the test assumes the empty string was included into the SA, so some
adjustment is needed.
Also,
https://cs.chromium.org/chromium/src/courgette/third_party/divsufsort/divsufs...
has an "all char" test. Can try this with a different number of alphabets (e.g.,
257).
Description was changed from ========== Generic suffix array algorithms for Zucchini. This introduces interface, implementation and unittests for: - suffix array construction using naive sort - suffix array construction using SA-IS - binary search in a suffix array BUG= ========== to ========== [Zucchini] Generic suffix array algorithms. This introduces interface, implementation and unittests for: - suffix array construction using naive sort - suffix array construction using SA-IS - binary search in a suffix array BUG= ==========
Regarding test coverage using IAmHere, I'm not sure if you mean I should do this locally, or add this as part of the implementation. https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:69: // This sentinel does not exist in memory and is only treated implicitely. On 2017/06/27 20:31:21, huangs wrote: > Unwrap comments to fit. > > TYPO: implicitly > > Period at end. Done. https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:350: if (length < 2) On 2017/06/27 20:31:21, huangs wrote: > Should |suffix_array| be assigned [0] for the case length == 1? That sounds like a good idea https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:419: std::vector<typename StrRng::size_type> MakeSuffixArray(Algorithm algorithm, On 2017/06/27 20:31:21, huangs wrote: > |algorithm| is unused? It is used as a tag and allows the template parameter Algorithm to be inferred. Instead of MakeSuffixSort<Sais>(...), we're using MakeSuffxSort(Sais(), ...) https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... File chrome/installer/zucchini/suffix_array_unittest.cc (right): https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:7: #include <string> On 2017/06/27 18:07:09, etiennep1 wrote: > #include <initializer_list> Done. https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:7: #include <string> On 2017/06/27 20:31:21, huangs wrote: > #include <cstddef> for size_t Done. https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:226: On 2017/06/27 20:31:21, huangs wrote: > Please also adapt the more comprehensive test in > > https://cs.chromium.org/chromium/src/courgette/third_party/bsdiff/bsdiff_sear... > > Note that the test assumes the empty string was included into the SA, so some > adjustment is needed. > > Also, > > https://cs.chromium.org/chromium/src/courgette/third_party/divsufsort/divsufs... > > has an "all char" test. Can try this with a different number of alphabets (e.g., > 257). I added more search unittest based on these test case. Note that this search function does not return the longest matching substring, but just the lower bound, so results can be confusing. As such, I'm just doing the check in TestSearchSuffixArray that the result correctly lies on the lower bound. Also, the SearchExact seems to take a LOT of time in debug (~2 sec) because it computes 4000+ search in suffix array. Not sure we want to do this...
On 2017/06/28 19:26:09, etiennep1 wrote: > Regarding test coverage using IAmHere, I'm not sure if you mean I should do this > locally, or add this as part of the implementation. > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > File chrome/installer/zucchini/suffix_array.h (right): > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > chrome/installer/zucchini/suffix_array.h:69: // This sentinel does not exist in > memory and is only treated implicitely. > On 2017/06/27 20:31:21, huangs wrote: > > Unwrap comments to fit. > > > > TYPO: implicitly > > > > Period at end. > > Done. > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > chrome/installer/zucchini/suffix_array.h:350: if (length < 2) > On 2017/06/27 20:31:21, huangs wrote: > > Should |suffix_array| be assigned [0] for the case length == 1? > > That sounds like a good idea > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > chrome/installer/zucchini/suffix_array.h:419: std::vector<typename > StrRng::size_type> MakeSuffixArray(Algorithm algorithm, > On 2017/06/27 20:31:21, huangs wrote: > > |algorithm| is unused? > > It is used as a tag and allows the template parameter Algorithm to be inferred. > Instead of MakeSuffixSort<Sais>(...), we're using MakeSuffxSort(Sais(), ...) > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > File chrome/installer/zucchini/suffix_array_unittest.cc (right): > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > chrome/installer/zucchini/suffix_array_unittest.cc:7: #include <string> > On 2017/06/27 18:07:09, etiennep1 wrote: > > #include <initializer_list> > > Done. > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > chrome/installer/zucchini/suffix_array_unittest.cc:7: #include <string> > On 2017/06/27 20:31:21, huangs wrote: > > #include <cstddef> for size_t > > Done. > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > chrome/installer/zucchini/suffix_array_unittest.cc:226: > On 2017/06/27 20:31:21, huangs wrote: > > Please also adapt the more comprehensive test in > > > > > https://cs.chromium.org/chromium/src/courgette/third_party/bsdiff/bsdiff_sear... > > > > Note that the test assumes the empty string was included into the SA, so some > > adjustment is needed. > > > > Also, > > > > > https://cs.chromium.org/chromium/src/courgette/third_party/divsufsort/divsufs... > > > > has an "all char" test. Can try this with a different number of alphabets > (e.g., > > 257). > > I added more search unittest based on these test case. Note that this search > function does not return the longest matching substring, but just the lower > bound, so results can be confusing. As such, I'm just doing the check in > TestSearchSuffixArray that the result correctly lies on the lower bound. > Also, the SearchExact seems to take a LOT of time in debug (~2 sec) because it > computes 4000+ search in suffix array. Not sure we want to do this... Update: every branch in the algo is visited from unittests.
Re. IAmHere: Just local hack to ensure test coverage, to guide finding examples to cover all cases. Re. Unittest: Ultimately we want the longest substring, and if the interface is not supported then it should be added so it can be tested. Re. SearchExact: In this case, determine whether the search is "reasonable" or not, e.g., compare with Courgette's unittests in debug. If it's strangely slow then we've uncovered a performance bug. If reasonable, then you can nerf the test a bit.
https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:419: std::vector<typename StrRng::size_type> MakeSuffixArray(Algorithm algorithm, I think the first form is preferred, since it's better to be explicit, and the second form instantialization.
On 2017/06/28 20:02:56, huangs wrote: > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > File chrome/installer/zucchini/suffix_array.h (right): > > https://codereview.chromium.org/2963463002/diff/20001/chrome/installer/zucchi... > chrome/installer/zucchini/suffix_array.h:419: std::vector<typename > StrRng::size_type> MakeSuffixArray(Algorithm algorithm, > I think the first form is preferred, since it's better to be explicit, and the > second form instantialization. SearchExact was computing suffix array everytime, turns out that was the bottleneck. It now finish reasonably fast. + I switched to template argument form.
Comments on tests. I think you accidentally changed Courgette file. https://codereview.chromium.org/2963463002/diff/60001/chrome/installer/zucchi... File chrome/installer/zucchini/suffix_array_unittest.cc (right): https://codereview.chromium.org/2963463002/diff/60001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:230: void TestSearchSuffixArray(std::string base_str, std::string search_str) { Make this take const ustring&, and update all callers to pass that. https://codereview.chromium.org/2963463002/diff/60001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:258: TestSearchSuffixArray("", ""); using us = MakeUnsignedString; TestSearchSuffixArray(us(""), us("a")); ... https://codereview.chromium.org/2963463002/diff/60001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:267: const char* sentence = "the quick brown fox jumps over the lazy dog."; ustring sentence = us("..."); https://codereview.chromium.org/2963463002/diff/60001/courgette/BUILD.gn File courgette/BUILD.gn (left): https://codereview.chromium.org/2963463002/diff/60001/courgette/BUILD.gn#oldc... courgette/BUILD.gn:163: "adjustment_method_unittest.cc", Why change this file?? If you want to run a test by itself, you can do courgette_unittest --gtest_filter=BSDiffSearchTest.SearchExact
courgette BUILD was definitely a mistake. I tried to make ustring conversions more elegant. https://codereview.chromium.org/2963463002/diff/60001/chrome/installer/zucchi... File chrome/installer/zucchini/suffix_array_unittest.cc (right): https://codereview.chromium.org/2963463002/diff/60001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:230: void TestSearchSuffixArray(std::string base_str, std::string search_str) { On 2017/06/28 22:30:35, huangs wrote: > Make this take const ustring&, and update all callers to pass that. Probably more clean like that. https://codereview.chromium.org/2963463002/diff/60001/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array_unittest.cc:267: const char* sentence = "the quick brown fox jumps over the lazy dog."; On 2017/06/28 22:30:35, huangs wrote: > ustring sentence = us("..."); Done. https://codereview.chromium.org/2963463002/diff/60001/courgette/BUILD.gn File courgette/BUILD.gn (left): https://codereview.chromium.org/2963463002/diff/60001/courgette/BUILD.gn#oldc... courgette/BUILD.gn:163: "adjustment_method_unittest.cc", On 2017/06/28 22:30:35, huangs wrote: > Why change this file?? > > If you want to run a test by itself, you can do > > courgette_unittest --gtest_filter=BSDiffSearchTest.SearchExact That was a mistake, sorry! Also, thanks for the tip.
I haven't grokked the algorithm yet. Meanwhile, here are some NITs. Please also format all comments, with nice capitalization, spacing, and punctuation. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:22: // Characters found in |str| must be in the range [0, |max_key|) NIT: |max_key| is a misnomer, since it's not a "maximally allowed key", but a bound on valid key. Maybe |key_bound|? https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:30: size_type n = str.end() - str.begin(); std::end(str) - std::begin(str)? Same below. Also, does this need static_cast<size_type>() like below? https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:35: std::sort(suffix_array, suffix_array + n, [&str](size_type i, size_type j) { Note that you're using lambda with capture here. Style guide: https://chromium-cpp.appspot.com/ Of course, you can make a case on the discussion thread. Now is the time! Let's discuss this off-line. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:49: // |suffix_array| is a random access mutable range containing the result. Mention that |suffix_array| should have length at least same as |str|? Same above. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:62: Implementation<size_type, typename std::make_unsigned<KeyType>::type>:: Do we need std::make_unsigned<>? We used static_assert already. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:69: // suf(S,i) the suffix formed by S[i, n). NIT: suf(S,i) has inconsistent spacing with later usage. Personally, I'd prefer the one without space, since it's more compact. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:82: // An LMS-substring is a substring S[i..j) with both S[i] and S[j], being LMS S[i..j): Inconsistent notatoin with S[i,n) above. Please choose one and stick with it. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:155: size_type j = 0; Do we need |j|? Can we just omit it, and have *(lms_indices++) = i; below? https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:167: // Occurence of every unique character is counted in |buckets| Typo: Occurrence. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:191: // for each leftmost S-type suffix suf(S, i) found in |lms_indices| NIT: Replace "leftmost S-type" with LMS, since we've defined it already. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:199: bucket_bounds[0] = buckets[0]; Use std::partial_sum() for this? https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:216: bucket_bounds[0] = 0; Is this step needed? I'd think that after the previous loop, bucket_bounds[] would end up with this already! Need comment though. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:221: // been place at the beginning of |suffix_array| since $ is always NIT: s/place/placed/ https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:361: // Given |lms_indices| in order of apparition, induce LMS substrings "apparition" means "ghost"? 2 more instances below.
PTAnL https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:21: // |str| must be a random access input range. Split argument description and type requirements. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:22: // Characters found in |str| must be in the range [0, |max_key|) On 2017/06/30 04:57:32, huangs wrote: > NIT: |max_key| is a misnomer, since it's not a "maximally allowed key", but a > bound on valid key. Maybe |key_bound|? Agreed https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:30: size_type n = str.end() - str.begin(); On 2017/06/30 04:57:32, huangs wrote: > std::end(str) - std::begin(str)? Same below. > > Also, does this need static_cast<size_type>() like below? Done. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:35: std::sort(suffix_array, suffix_array + n, [&str](size_type i, size_type j) { On 2017/06/30 04:57:32, huangs wrote: > Note that you're using lambda with capture here. Style guide: > > https://chromium-cpp.appspot.com/ > > Of course, you can make a case on the discussion thread. Now is the time! Let's > discuss this off-line. I disagree. From the link: "Be careful with default captures ([=], [&]), and do not bind or store any capturing lambdas outside the lifetime of the stack frame they are defined in; use base::Callback for this instead" Note that 2 things are banned: - use of std::function - lambda with bound variable whose lifetime goes beyond the scope of those variable. base::Callback should be used for that instead. I believe that the current usage is legitimate. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:49: // |suffix_array| is a random access mutable range containing the result. On 2017/06/30 04:57:32, huangs wrote: > Mention that |suffix_array| should have length at least same as |str|? Same > above. Done. Same for NaiveSuffixSort. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:62: Implementation<size_type, typename std::make_unsigned<KeyType>::type>:: On 2017/06/30 04:57:32, huangs wrote: > Do we need std::make_unsigned<>? We used static_assert already. We don't. That comes from an failed attempt to support signed values. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:69: // suf(S,i) the suffix formed by S[i, n). On 2017/06/30 04:57:32, huangs wrote: > NIT: suf(S,i) has inconsistent spacing with later usage. > > Personally, I'd prefer the one without space, since it's more compact. Done. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:82: // An LMS-substring is a substring S[i..j) with both S[i] and S[j], being LMS On 2017/06/30 04:57:32, huangs wrote: > S[i..j): Inconsistent notatoin with S[i,n) above. Please choose one and stick > with it. Done. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:155: size_type j = 0; On 2017/06/30 04:57:32, huangs wrote: > Do we need |j|? Can we just omit it, and have > > *(lms_indices++) = i; > > below? Good point. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:167: // Occurence of every unique character is counted in |buckets| On 2017/06/30 04:57:32, huangs wrote: > Typo: Occurrence. Done. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:191: // for each leftmost S-type suffix suf(S, i) found in |lms_indices| On 2017/06/30 04:57:33, huangs wrote: > NIT: Replace "leftmost S-type" with LMS, since we've defined it already. Done. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:199: bucket_bounds[0] = buckets[0]; On 2017/06/30 04:57:32, huangs wrote: > Use std::partial_sum() for this? Done. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:216: bucket_bounds[0] = 0; On 2017/06/30 04:57:33, huangs wrote: > Is this step needed? I'd think that after the previous loop, bucket_bounds[] > would end up with this already! Need comment though. This step is needed, yes. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:221: // been place at the beginning of |suffix_array| since $ is always On 2017/06/30 04:57:32, huangs wrote: > NIT: s/place/placed/ Done. https://codereview.chromium.org/2963463002/diff/70005/chrome/installer/zucchi... chrome/installer/zucchini/suffix_array.h:361: // Given |lms_indices| in order of apparition, induce LMS substrings On 2017/06/30 04:57:32, huangs wrote: > "apparition" means "ghost"? 2 more instances below. Wrong translation, meant appearance
More comments. It seems SearchSuffixArray() is broken? https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:21: // |str| is the input string on which suffix sort is applied. It's a bit odd that the variables are mentioned before the types... How about: // |InputRng| ... // ... template<>... // |str|... // ... void operator()(...) ? Also, for |InputRng| and |SAIt|, should mention that they are types. Same below. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:75: // Given the string S of length n. We assume S is terminated by a unique NIT: Remove "the" in "the string". NIT: In the paper, |n| counts the sentinel $. But in our code it seems |n| doesn't? https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:87: // A character S[i], i is called LMS (leftmost S-type), if S[i] is S-type and ", i" seems redundant? https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:91: // An LMS-substring is a substring S[i..j) with both S[i] and S[j], being LMS // A substring S[i..j) is an LMS-substring if (1) S[i] is LMS, S[j] is LMS or the sentinel $, and S[i..j) has no other LMS characters, or (2) S[i..j) is the sentinel $. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:106: // Partition every suffix based on SL-type. // ... Returns the number of LMS suffixes. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:135: // S[i] > S[i + 1] or S[i] is last character NIT: Period at end. Please apply to all comments below. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:151: *sl_partition = previous_type; These 3 cases can be combined by assigning |previous_type|, then finally: *sl_partition = previous_type; previous_key = current_key; https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:160: static void FindLmsSuffixes(const std::vector<SLType>& sl_partition, This is called once, and not tested independently. May as well embed into call site, with comment applied for the code block? https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:173: static std::vector<size_type> MakeBucketCount(StrIt str, Same: Embed into call site? https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:184: // Apply induced sort from |lms_indices| to |suffix_array| associated with Now called |lms_substrings|? Please reconcile the inconsistency. I'm using |lms_indices| in my comments, as placeholder. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:193: // All indices are first marked as unset with 0. 0 is a valid final value. It's better for error checking to use an illegal value |kUnassigned| instead. This may be |length| or static_cast<SAIt::value_type>(-1), and if using the latter, add a check to ensure |length| is strictly smaller. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:195: DCHECK(!buckets.empty()); (reason: We use buckets.end() - 1, bucket_bounds[0], and bucket_bounds.begin() + 1). https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:199: // Step 1 // Step 1: Assign indices for LMS suffixes, populating the end of respective buckets but keeping relative order. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:208: // Process each |lms_indices| backward, and assign them to the end of their respective buckets, so relative order is preserved. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:229: // From Step 1, the sentinel $, which we treat implicitely, would have TYPO: implicitely -> implicitly https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:240: // While the original algorithm marks unset suffixes with -1, Update comment if we use kUnassigned. Inconsistent spacing |suf(S, 0)| (vs. suf(S,0)). https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:257: // only L-type suffixes where inserted in |suffix_array| during Step21, Step21? https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:258: // |bucket_bounds| does not contains the end of each bucket and needs to s/contains/contain/ https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:307: SLType current_lms_type = SType, previous_lms_type = SType; Break into separate lines. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:312: bool current_lms_end = false, previous_lms_end = false; Break into separate lines. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:348: return ++label; Style: Should be |label + 1|: The side effect of updating |label| is unneeded. And if done for optimization (which doubtfully applies in this case), a comment would be needed. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:410: for (size_type i = 0; i < lms_indices.size(); ++i) std::copy()? https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:457: return it; What happened to the code that uses SA to solve maximal substring matching? Note that binary search is insufficient: In the end you'd need neighbourhood search to find best matching sequence. For example, let |str2| = "aaaam" ======== Suffix list 1 ======== ... a aaz <= lower_bound result. ... ======== Suffix list 2 ======== ... aaaa aaz <= lower_bound result. ... ================ Binary search in both cases point to "aaz", but for Suffix list 1, the best match is "aaz", whereas for Suffix list 2, the best match is the string before, i.e., "aaaa". https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array_unittest.cc (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array_unittest.cc:242: if (pos != suffix_array.begin()) { This code looks like hack to make test work? Please fix maximal substring matching in SA library, and just call it there. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array_unittest.cc:310: for (int lo = 0; lo < test_str.size(); ++lo) { |lo| and |hi| should be size_t?
https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:457: return it; For a more realistic example: Query "aaaam" in ["aaza", "aazaaaa"]: ======== Sorted suffixes of "aaza" ======== a aaza <= lower_bound() for "aaaam", and best match. aza za ======== Sorted suffixes of "aazaaaa" ======== a aa aaa aaaa <= Best match. aazaaaa <= lower_bound() for "aaaam". azaaaa zaaaa ================
https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:112: std::vector<SLType>::reverse_iterator sl_partition) { NIT: |sl_partition| is actually an interator, and should be named as such. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:160: static void FindLmsSuffixes(const std::vector<SLType>& sl_partition, NVM, keep it the way it is. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:173: static std::vector<size_type> MakeBucketCount(StrIt str, NVM, keep it the way it is. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:404: label_count, suffix_array); |suffix_array| is SAIt, but in recursion it's now size_type?
Updated. Should I wait for this CL to land before committing integration in google3? https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:21: // |str| is the input string on which suffix sort is applied. On 2017/07/05 05:51:58, huangs wrote: > It's a bit odd that the variables are mentioned before the types... How about: > > // |InputRng| ... > // ... > template<>... > // |str|... > // ... > void operator()(...) > > ? > Also, for |InputRng| and |SAIt|, should mention that they are types. > > Same below. Following reference for stl, I added "Type requirements:" https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:75: // Given the string S of length n. We assume S is terminated by a unique On 2017/07/05 05:51:57, huangs wrote: > NIT: Remove "the" in "the string". > > NIT: In the paper, |n| counts the sentinel $. But in our code it seems |n| > doesn't? Done. |n| (or |length|) does not count the sentinel in the implementation, I added a comment about it. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:87: // A character S[i], i is called LMS (leftmost S-type), if S[i] is S-type and On 2017/07/05 05:51:58, huangs wrote: > ", i" seems redundant? Yeah, don't know how it got there. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:91: // An LMS-substring is a substring S[i..j) with both S[i] and S[j], being LMS On 2017/07/05 05:51:58, huangs wrote: > // A substring S[i..j) is an LMS-substring if (1) S[i] is LMS, S[j] is LMS or > the sentinel $, and S[i..j) has no other LMS characters, or (2) S[i..j) is the > sentinel $. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:106: // Partition every suffix based on SL-type. On 2017/07/05 05:51:57, huangs wrote: > // ... Returns the number of LMS suffixes. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:112: std::vector<SLType>::reverse_iterator sl_partition) { On 2017/07/10 02:45:29, huangs wrote: > NIT: |sl_partition| is actually an interator, and should be named as such. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:135: // S[i] > S[i + 1] or S[i] is last character On 2017/07/05 05:51:58, huangs wrote: > NIT: Period at end. Please apply to all comments below. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:151: *sl_partition = previous_type; On 2017/07/05 05:51:58, huangs wrote: > These 3 cases can be combined by assigning |previous_type|, then finally: > > *sl_partition = previous_type; > previous_key = current_key; Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:160: static void FindLmsSuffixes(const std::vector<SLType>& sl_partition, On 2017/07/05 05:51:58, huangs wrote: > This is called once, and not tested independently. May as well embed into call > site, with comment applied for the code block? It is called once, but is tested in TestSlPartition. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:173: static std::vector<size_type> MakeBucketCount(StrIt str, On 2017/07/05 05:51:57, huangs wrote: > Same: Embed into call site? This is also tested in BucketCount. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:184: // Apply induced sort from |lms_indices| to |suffix_array| associated with On 2017/07/05 05:51:58, huangs wrote: > Now called |lms_substrings|? Please reconcile the inconsistency. I'm using > |lms_indices| in my comments, as placeholder. I switched to lms_indices. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:193: // All indices are first marked as unset with 0. On 2017/07/05 05:51:58, huangs wrote: > 0 is a valid final value. It's better for error checking to use an illegal value > |kUnassigned| instead. This may be |length| or > static_cast<SAIt::value_type>(-1), and if using the latter, add a check to > ensure |length| is strictly smaller. I switched to |length| https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:195: On 2017/07/05 05:51:58, huangs wrote: > DCHECK(!buckets.empty()); > > (reason: We use buckets.end() - 1, bucket_bounds[0], and bucket_bounds.begin() + > 1). Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:199: // Step 1 On 2017/07/05 05:51:57, huangs wrote: > // Step 1: Assign indices for LMS suffixes, populating the end of respective > buckets but keeping relative order. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:208: On 2017/07/05 05:51:58, huangs wrote: > // Process each |lms_indices| backward, and assign them to the end of their > respective buckets, so relative order is preserved. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:229: // From Step 1, the sentinel $, which we treat implicitely, would have On 2017/07/05 05:51:58, huangs wrote: > TYPO: implicitely -> implicitly Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:240: // While the original algorithm marks unset suffixes with -1, On 2017/07/05 05:51:57, huangs wrote: > Update comment if we use kUnassigned. > > > Inconsistent spacing |suf(S, 0)| (vs. suf(S,0)). Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:257: // only L-type suffixes where inserted in |suffix_array| during Step21, On 2017/07/05 05:51:58, huangs wrote: > Step21? Step 2 https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:258: // |bucket_bounds| does not contains the end of each bucket and needs to On 2017/07/05 05:51:57, huangs wrote: > s/contains/contain/ Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:307: SLType current_lms_type = SType, previous_lms_type = SType; On 2017/07/05 05:51:57, huangs wrote: > Break into separate lines. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:312: bool current_lms_end = false, previous_lms_end = false; On 2017/07/05 05:51:58, huangs wrote: > Break into separate lines. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:348: return ++label; On 2017/07/05 05:51:58, huangs wrote: > Style: Should be |label + 1|: The side effect of updating |label| is unneeded. > And if done for optimization (which doubtfully applies in this case), a comment > would be needed. Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:404: label_count, suffix_array); On 2017/07/10 02:45:29, huangs wrote: > |suffix_array| is SAIt, but in recursion it's now size_type? Not sure what you mean. SAIt stays the same in the recursion because it is inferred from the argument. Implementation<size_type, size_type> means: SizeType = size_type KeyType = size_type So we switched KeyType to size_type because lms_str (the string being sorted) now contains indices. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:410: for (size_type i = 0; i < lms_indices.size(); ++i) On 2017/07/05 05:51:58, huangs wrote: > std::copy()? Done. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:457: return it; On 2017/07/05 05:51:58, huangs wrote: > What happened to the code that uses SA to solve maximal substring matching? Note > that binary search is insufficient: In the end you'd need neighbourhood search > to find best matching sequence. For example, let |str2| = "aaaam" > > ======== Suffix list 1 ======== > ... > a > aaz <= lower_bound result. > ... > > ======== Suffix list 2 ======== > ... > aaaa > aaz <= lower_bound result. > ... > ================ > > Binary search in both cases point to "aaz", but for Suffix list 1, the best > match is "aaz", whereas for Suffix list 2, the best match is the string before, > i.e., "aaaa". This is a lower level function, that only computes the lower bound. Rationale: when looking for equivalence, we are not necessarily interested in the longest exact matching seed (through encoded view). It would make more sense to minimize work done through encoded view, and let the the equivalence map layer decide what to do with it (since it is more aware of the problem). What I suggest is: 1- Expose lower bound as part of the api. For the purpose of integration in google3, we can have a wrapper function that searches the best string and use this in equivalence map. 2- Commit the refactored equivalence map construction (which use lower bound instead) in Chromium. I have a fully working prototype that I can submit in google3 at the same time to ensure integration. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array_unittest.cc (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array_unittest.cc:242: if (pos != suffix_array.begin()) { On 2017/07/05 05:51:59, huangs wrote: > This code looks like hack to make test work? Please fix maximal substring > matching in SA library, and just call it there. It tests lower bound. I updated the name. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array_unittest.cc:310: for (int lo = 0; lo < test_str.size(); ++lo) { On 2017/07/05 05:51:58, huangs wrote: > |lo| and |hi| should be size_t? Done.
LGTM % comments. Will look again if prompted. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:404: label_count, suffix_array); Note that |suffix_array| was a parameter into this function, with type SAIt. But in the recursion we pass it, but as size_type. This happens to works since SAIt == size_type? https://codereview.chromium.org/2963463002/diff/150001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/150001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:100: // A substring S[i..j) is an LMS-substring if I meant to have this replace the above comment -- but I'll leave it to you.
The CQ bit was checked by etiennep@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: ios-simulator on master.tryserver.chromium.mac (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.mac/builders/ios-simulator/bui...)
The CQ bit was checked by etiennep@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...
Rebasing and landing. https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:404: label_count, suffix_array); On 2017/07/10 20:01:18, huangs wrote: > Note that |suffix_array| was a parameter into this function, with type SAIt. But > in the recursion we pass it, but as size_type. This happens to works since SAIt > == size_type? We pass it as is (the last argument). SAIt is an iterator with value type == size_type. lms_str is a vector with value type == size_type. So in Implementation<size_type, size_type>, we use size_type both for indices and values. Also, static_cast<size_type>(lms_str.size()) is necessary to avoid warnings if size_type is smaller than size_t. https://codereview.chromium.org/2963463002/diff/150001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/150001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:100: // A substring S[i..j) is an LMS-substring if On 2017/07/10 20:01:18, huangs wrote: > I meant to have this replace the above comment -- but I'll leave it to you. Oops, I forgot to remove the above.
Description was changed from ========== [Zucchini] Generic suffix array algorithms. This introduces interface, implementation and unittests for: - suffix array construction using naive sort - suffix array construction using SA-IS - binary search in a suffix array BUG= ========== to ========== [Zucchini] Generic suffix array algorithms. This introduces interface, implementation and unittests for: - suffix array construction using naive sort - suffix array construction using SA-IS - binary search in a suffix array BUG=729154 ==========
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
The CQ bit was checked by etiennep@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.
https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/110001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:404: label_count, suffix_array); Oh I see, the full signature is Implementation<size_type, size_type>::SuffixSort<StrIt, SAIt>(...), but the last 2 are implicit.
The CQ bit was checked by etiennep@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from huangs@chromium.org Link to the patchset: https://codereview.chromium.org/2963463002/#ps210001 (title: "Fix trybots")
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
Try jobs failed on following builders: chromium_presubmit on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/chromium_presub...)
The CQ bit was checked by etiennep@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from huangs@chromium.org Link to the patchset: https://codereview.chromium.org/2963463002/#ps230001 (title: "Rebase")
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
Try jobs failed on following builders: linux_chromium_rel_ng on master.tryserver.chromium.linux (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
The CQ bit was checked by etiennep@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.
The CQ bit was checked by etiennep@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 etiennep@chromium.org
The CQ bit was checked by etiennep@chromium.org
CQ is trying da patch. Follow status at: https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
CQ is committing da patch.
Bot data: {"patchset_id": 230001, "attempt_start_ts": 1499817781662280,
"parent_rev": "2303f1d6f15af92835125298d092b6a19063b38a", "commit_rev":
"a1b45802a88101e23d1c0e485165255807702ca7"}
Message was sent while issue was closed.
Description was changed from ========== [Zucchini] Generic suffix array algorithms. This introduces interface, implementation and unittests for: - suffix array construction using naive sort - suffix array construction using SA-IS - binary search in a suffix array BUG=729154 ========== to ========== [Zucchini] Generic suffix array algorithms. This introduces interface, implementation and unittests for: - suffix array construction using naive sort - suffix array construction using SA-IS - binary search in a suffix array BUG=729154 Review-Url: https://codereview.chromium.org/2963463002 Cr-Commit-Position: refs/heads/master@{#485769} Committed: https://chromium.googlesource.com/chromium/src/+/a1b45802a88101e23d1c0e485165... ==========
Message was sent while issue was closed.
Committed patchset #13 (id:230001) as https://chromium.googlesource.com/chromium/src/+/a1b45802a88101e23d1c0e485165...
Message was sent while issue was closed.
grt@chromium.org changed reviewers: + grt@chromium.org
Message was sent while issue was closed.
https://codereview.chromium.org/2963463002/diff/230001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/230001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:52: class Sais { "Names should be descriptive; avoid abbreviation." (https://google.github.io/styleguide/cppguide.html#General_Naming_Rules) https://codereview.chromium.org/2963463002/diff/230001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:102: struct Implementation { should this be in a private: section of Sais? https://codereview.chromium.org/2963463002/diff/230001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:427: }; ? private: DISALLOW_IMPLICIT_CONSTRUCTORS(Implementation); };
Message was sent while issue was closed.
Publishing comments. Corrections are found at 590189. https://codereview.chromium.org/2963463002/diff/230001/chrome/installer/zucch... File chrome/installer/zucchini/suffix_array.h (right): https://codereview.chromium.org/2963463002/diff/230001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:52: class Sais { On 2017/07/24 09:09:42, grt (UTC plus 2) wrote: > "Names should be descriptive; avoid abbreviation." > (https://google.github.io/styleguide/cppguide.html#General_Naming_Rules) Done. https://codereview.chromium.org/2963463002/diff/230001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:102: struct Implementation { On 2017/07/24 09:09:42, grt (UTC plus 2) wrote: > should this be in a private: section of Sais? It would make sense to have this private, but it is convenient to have it public for unittest, and since everything is wrapped in Implementation class, it makes it pretty obvious this is an implementation detail. I also have a feeling friendship for unittest is frowned upon. Let me know if there's a better way to to this. https://codereview.chromium.org/2963463002/diff/230001/chrome/installer/zucch... chrome/installer/zucchini/suffix_array.h:427: }; On 2017/07/24 09:09:42, grt (UTC plus 2) wrote: > ? > private: > DISALLOW_IMPLICIT_CONSTRUCTORS(Implementation); > }; Done. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
