ashvardanian / ashvardanian/StringZilla
Bug: result of find_all() cannot obtain the position of the substring within the parent string
- Dominant language
- C
- Stars
- 3.6k
- Forks
- 135
- PR merge metrics
- No merged PRs in 30d
Description
### Describe the bug
This issue may be related to the previously closed issue #268 . The following code is tested against the latest main branch.
Typically, we use `find_all()` to get the positions where substrings appear in the main string. Therefore, I would use sz::find_all() as follows:
```cpp
namespace sz = ashvardanian::stringzilla;
void test_1()
{
sz::string_view m ("hello world, hello cpp");
sz::string_view n ("hello");
auto r = sz::find_all(m, n);
for (auto i : r)
{
auto start = std::distance(m.cbegin(), i.cbegin());
std::cout << "[" << start << ", " << start + i.size() << ")\n";
}
}
```
The output will be:
```
[0, 5)
[13, 18)
```
However, the same operation applied to sz::string will produce chaotic results:
```cpp
void test_2()
{
// Now, both m and n are sz::string
sz::string m ("hello world, hello cpp");
sz::string n ("hello");
auto r = sz::find_all(m, n);
for (auto i : r)
{
auto start = std::distance(m.cbegin(), i.cbegin());
std::cout << "[" << start << ", " << start + i.size() << ")\n";
}
}
```
Possible output:
```
[-64, 18446744073709551557)
[-51, 18446744073709551570)
```
The issue arises because the return type of find_all (range_matches) is bound to the input parameter type. When string_type_ is sz_string, it does not conform to the documentation of range_matches, which states:
> ... similar to a pair of boost::algorithm::find_iterator
If we forcibly use the `range_matches` to receive the result of `find_all`, everything works correctly:
```cpp
void test_3()
{
sz::string m ("hello world, hello cpp");
sz::string n ("hello");
auto r = sz::find_all(m, n);
for (auto i : r)
{
auto start = std::distance(m.cbegin(), i.cbegin());
std::cout << "[" << start << ", " << start + i.size() << ")\n";
}
}
```
The above code will produce the correct result.
Additionally, using the standard library's std::string_view with sz::find_all() naturally yields correct results, so we skip that.
What about using std::string? I found that using the C++ standard library's std::string to call `sz::find_all()` ** fails ** to compile:
```cpp
// Note: switched to C++ std::string
std::string m ("hello world, hello cpp");
std::string n ("hello");
auto r = sz::find_all(m,n); // Compilation fails
```
I believe this compilation failure is user-friendly. As long as users understand the lifecycle considerations related to stringzilla, they can quickly use std::string to write:
```cpp
void test_4()
{
std::string m ("hello world, hello cpp");
std::string n ("hello");
// auto r = sz::find_all(m, n);
auto r = sz::find_all(sz::string_view(m), sz::string_view(n));
for (auto i : r)
{
auto start = std::distance(m.cbegin().base(), i.cbegin());
std::cout << "[" << start << ", " << start + i.size() << ")\n";
}
}
```
This also produces the correct result (note that in `std::distance()`, we need to call `.base()`).
Based on the different compilation results when passing `std::string` or `std::string_view` to `sz::find_all()`, my suggestions are:
Option 1: Explicitly prevent find_all() from being used with `sz::string` objects, forcing users to use `sz::string_view` (or `std::string_view`). This would make it easier for users to notice the lifecycle of `string_view`.
Option 2: Fix `range_matches` to always be `range_matches>`.
Personally, I lean toward Option 1.
### Steps to reproduce
-
### Expected behavior
-
### StringZilla version
main
### Operating System
Windows 11
### Hardware architecture
x86
### Which interface are you using?
C++ bindings
### Contact Details
-
### Are you open to being tagged as a contributor?
- [ ] I am open to being mentioned in the project `.git` history as a contributor
### Is there an existing issue for this?
- [x] I have searched the existing issues
### Code of Conduct
- [x] I agree to follow this project's Code of Conduct
Contributor guide
Research direction
Reproduce the issue with the test_1, test_2, and test_3 examples, then inspect the C++ find_all and range_matches types. Compare how sz::string and string_view determine match iterator positions, and resolve whether the API should reject sz::string or return string_view-based matches. Done means the behavior is documented and covered by a regression check.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- backend-api-design
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100