Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

mem.replacementSize adjacent matches bug #8454

Closed
jumpnbrownweasel opened this issue Apr 7, 2021 · 2 comments
Closed

mem.replacementSize adjacent matches bug #8454

jumpnbrownweasel opened this issue Apr 7, 2021 · 2 comments
Labels
bug Observed behavior contradicts documented or intended behavior standard library This issue involves writing Zig code for the standard library.
Milestone
0.8.0

Comments

@jumpnbrownweasel
Copy link
Contributor

Adjacent matches are not handled correctly by mem.replacementSize.

test "replacementSize" {
    std.testing.expectEqual(@as(usize, 2), std.mem.replacementSize(u8, "\\n\\n", "\\n", "\n"));
}

Result in: Test [1/42] test "replacementSize"... expected 2, found 3

This was reported on discord by @cryptocode here:
https://discord.com/channels/605571803288698900/605572581046747136/829096724500840488

I'm putting together a PR and will be working with cryptocode on it.
@jumpnbrownweasel
Copy link
Contributor Author

jumpnbrownweasel commented Apr 7, 2021 •
edited
Loading

@cryptocode Here is a draft PR to review: #8455

I added two tests for the 'replace' method as well as for 'replacementSize'. The changes to the existing tests for the 'replace' method were done because they were incorrect and just happened to work -- the size of two expected results just happened to be the same length.

I did not include any changes to address the O(n^2) problem that was pointed out on discord. The 'replace()' fn also has the same problem and I think it should be addressed separately with quite a bit more testing added.

I ran ./bin/zig build test-std -Dskip-release with my changes.

andrewrk pushed a commit that referenced this issue Apr 25, 2021
@jumpnbrownweasel
#8454 Fix for std.mem.replacementSize adjacent matches bug. (#8455)
bf67a3f 
* #8454 Fix for std.mem.replacementSize adjacent matches bug.

When two 'needle' values are adjacent in the 'input' slice, the size is not
counted correctly. The 2nd 'needle' value is not matched because the index is
incremented by one after changing the index to account for the first value.

The impact is the the size returned is incorrect, and could cause UB when this
amount is used to size of the buffer passed to std.mem.replace.

* Apply changes from PR review:

- Add assert checking that the needle is non-empty and doc for this.
- Add minimal test that an empty input works.
- Use testing.expectEqualStrings.
@andrewrk andrewrk added bug Observed behavior contradicts documented or intended behavior standard library This issue involves writing Zig code for the standard library. labels Apr 25, 2021
@andrewrk andrewrk added this to the 0.8.0 milestone Apr 25, 2021
@andrewrk
Copy link
Member

Thanks for the fix! Landed in bf67a3f.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Observed behavior contradicts documented or intended behavior standard library This issue involves writing Zig code for the standard library.
Projects
None yet
Milestone
0.8.0
Development

No branches or pull requests
2 participants
@andrewrk @jumpnbrownweasel