Skip to content

-B/-C before-context count is rounded up to a power of two #66

Closed

Description

@sylvestre

grep - -B/-C before-context count is rounded up to a power of two

Found by the differential fuzzer with args grep ["-e", "l", "-B", "3"].

-B N (and the before half of -C N) should print exactly N lines of context before each
match. uu_grep instead prints up to the next power of two: -B 3 prints 4 before-context
lines, -B 5/-B 6/-B 7 print 8. Values that are already powers of two (1, 2, 4, 8)
are correct, which is what makes the bug intermittent.

Reproduction

Input is ten numbered lines 01..10 followed by a matching line MM.

Rust (incorrect)

$ printf '01\n02\n03\n04\n05\n06\n07\n08\n09\n10\nMM\n' | ./target/release/grep -e MM -B 3
# Output:
# 07
# 08
# 09
# 10
# MM
# (four before-context lines instead of three)

GNU (correct)

$ printf '01\n02\n03\n04\n05\n06\n07\n08\n09\n10\nMM\n' | LC_ALL=C /usr/bin/grep -e MM -B 3
# Output:
# 08
# 09
# 10
# MM
# (three before-context lines)

Before-context line counts observed for -B 1..7 (match has 10 preceding lines):

-B uu_grep GNU
1 1 1
2 2 2
3 4 3
4 4 4
5 8 5
6 8 6
7 8 7

The counts follow 1, 2, 4, 4, 8, 8, 8 — i.e. the requested size rounded up to a power of two.
The context ring buffer is allocated with capacity.next_power_of_two() slots and then retains
up to that many lines, rather than capping retention at the requested count.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions