Skip to content

[Bug]: Grep: offset/head_limit pagination silently drops and duplicates matches because ripgrep output order is non-deterministic across invocations #2709

Closed

Description

@BlueX888

Prerequisites

  • I have searched the existing issues and discussions, and this is not a duplicate.
  • This is a bug, not a usage question.

Background / Description

What I was trying to do: page through Grep results with head_limit/offset — exactly what the tool's own output suffix ([Showing results with pagination = limit: N, offset: M]) tells a caller to do when results are truncated.

What actually happens: every Grep call re-runs rg with no sort flag, and rg's parallel directory walker returns matches in a different order on every invocation. _apply_head_limit then slices that unstable list with items[offset : offset + effective_limit], so paging with offset skips a different "first N" on each call: some matches are never returned on any page, while others appear on two pages. The agent silently believes it has seen every match.

Expected behaviour: paging through all matches with offset/head_limit returns each match exactly once, i.e. the result ordering must be stable across calls.

Basis (the tool's own documented contract):

  • input_schema in src/agentscope/tool/_builtin/_grep.py:135-147: head_limit — "Limit output to first N lines/entries. Defaults to 250 when unspecified. Pass 0 for unlimited."; offset — "Skip first N lines/entries before applying head_limit. Defaults to 0." Skipping a stable "first N" is only well-defined if the ordering is stable across calls, and Grep is stateless (it re-runs rg on every call).
  • The output suffix at src/agentscope/tool/_builtin/_grep.py:477 emits [Showing results with pagination = limit: N, offset: M], instructing the caller to re-call with a larger offset — only meaningful with a stable order.
  • The sibling Glob tool makes its output deterministic: its description (src/agentscope/tool/_builtin/_glob.py:52) promises "matching file paths sorted by modification time (newest first)" and src/agentscope/tool/_builtin/_scripts/_glob_helper.py:209 explicitly does matches.sort(key=_mtime, reverse=True). Grep adds no ordering at all.

Root cause: Grep._run_ripgrep builds the rg argv at src/agentscope/tool/_builtin/_grep.py:289 (command = ["rg", *args, search_path]) without any sort flag, so the match order is whatever rg's parallel walker happens to produce; _apply_head_limit (src/agentscope/tool/_builtin/_grep.py:259-273) then slices that unstable list at line 272. Passing --sort path in the argv (at least when offset/head_limit pagination is in use), or sorting the returned lines in Python before _apply_head_limit slices them, would make pagination stable — mirroring how Glob sorts its results.

Error Messages

No exception is raised — the tool silently returns incomplete, duplicated pages. Verbatim output of the script below, observed in an independent reproduction:

all matches    : ['NEEDLE0', 'NEEDLE1', 'NEEDLE2', 'NEEDLE3', 'NEEDLE4', 'NEEDLE5']
page1 offset=0 : ['NEEDLE0', 'NEEDLE2', 'NEEDLE4']
page2 offset=3 : ['NEEDLE1', 'NEEDLE4', 'NEEDLE5']
LOST by paging : ['NEEDLE3']

NEEDLE4 appears on both pages and NEEDLE3 on neither: 6 matches exist, paging loses one and duplicates another. A second independent reproduction on the same tree:

all matches    : ['NEEDLE0', 'NEEDLE1', 'NEEDLE2', 'NEEDLE3', 'NEEDLE4', 'NEEDLE5']
page1 offset=0 : ['NEEDLE0', 'NEEDLE2', 'NEEDLE4']
page2 offset=3 : ['NEEDLE0', 'NEEDLE1', 'NEEDLE5']
LOST by paging : ['NEEDLE3']

The underlying rg non-determinism — 8 identical bare rg NEEDLE . runs on the same flat 6-file tree give (at least) 5 different orders:

./f0.py:NEEDLE0 ./f2.py:NEEDLE2 ./f4.py:NEEDLE4 ./f3.py:NEEDLE3 ./f1.py:NEEDLE1 ./f5.py:NEEDLE5
./f2.py:NEEDLE2 ./f0.py:NEEDLE0 ./f4.py:NEEDLE4 ./f1.py:NEEDLE1 ./f3.py:NEEDLE3 ./f5.py:NEEDLE5
./f2.py:NEEDLE2 ./f0.py:NEEDLE0 ./f4.py:NEEDLE4 ./f3.py:NEEDLE3 ./f1.py:NEEDLE1 ./f5.py:NEEDLE5
./f2.py:NEEDLE2 ./f5.py:NEEDLE5 ./f0.py:NEEDLE0 ./f1.py:NEEDLE1 ./f4.py:NEEDLE4 ./f3.py:NEEDLE3
./f2.py:NEEDLE2 ./f0.py:NEEDLE0 ./f5.py:NEEDLE5 ./f1.py:NEEDLE1 ./f4.py:NEEDLE4 ./f3.py:NEEDLE3
./f2.py:NEEDLE2 ./f0.py:NEEDLE0 ./f4.py:NEEDLE4 ./f3.py:NEEDLE3 ./f1.py:NEEDLE1 ./f5.py:NEEDLE5
./f2.py:NEEDLE2 ./f0.py:NEEDLE0 ./f4.py:NEEDLE4 ./f3.py:NEEDLE3 ./f1.py:NEEDLE1 ./f5.py:NEEDLE5
./f2.py:NEEDLE2 ./f0.py:NEEDLE0 ./f4.py:NEEDLE4 ./f1.py:NEEDLE1 ./f5.py:NEEDLE5 ./f3.py:NEEDLE3

Because the loss depends on which two orders rg happens to pick, it is probabilistic (in one reproduction 5 of 7 runs lost at least one match; in my own rerun 1 of 8 did) — which is exactly what makes it silent and hard to notice.

Steps to Reproduce

  1. Code:
"""Grep offset-pagination loses matches: rg output order is not stable
across invocations, so each paginated call skips a different 'first N'."""
import asyncio, os, tempfile
from agentscope.tool import Grep

def matches(chunk):
    return {l.split(":")[-1] for l in chunk.content[0].text.splitlines() if ":NEEDLE" in l}

async def main():
    d = tempfile.mkdtemp()
    for i in range(6):
        with open(os.path.join(d, f"f{i}.py"), "w") as f:
            f.write(f"NEEDLE{i}\n")
    g = Grep()
    truth = matches(await g.call(pattern="NEEDLE", path=d, output_mode="content", head_limit=0))
    p1 = await g.call(pattern="NEEDLE", path=d, output_mode="content", head_limit=3, offset=0)
    p2 = await g.call(pattern="NEEDLE", path=d, output_mode="content", head_limit=3, offset=3)
    seen = matches(p1) | matches(p2)
    print("all matches    :", sorted(truth))
    print("page1 offset=0 :", sorted(matches(p1)))
    print("page2 offset=3 :", sorted(matches(p2)))
    print("LOST by paging :", sorted(truth - seen))

asyncio.run(main())
  1. Run: python repro_grep_pagination.py (retry a few times — the loss is order-dependent)
  2. See a needle listed in all matches but returned on neither page, while another needle is returned on both pages.

This is easy to hit in practice: head_limit defaults to 250 (DEFAULT_HEAD_LIMIT, src/agentscope/tool/_builtin/_grep.py:28), so any search with more than 250 hits is truncated with [Showing results with pagination = limit: 250] and the caller pages with offset=250, 500, ... — every page boundary then silently skips an arbitrary set of lines.

Environment

  • AgentScope Version: 2.0.8 (source at commit 61cdeae4ffe63182f3343229aa6fbd868e30b0c5; the unsorted argv is unchanged on current main at 5ff52f87)
  • Python Version: 3.12.14
  • OS: macOS 26.6.2, ripgrep 15.2.0

Related: I searched issues/discussions for "grep offset", "grep pagination", "grep sort", "head_limit" and "ripgrep" and found nothing covering this — nearest are #1936 (closed; negative pagination values accepted — a different validation bug) and #2571 (closed; Glob unbounded output). #2636 concerns workdir resolution, not ordering.

AI disclosure: this report was prepared with AI assistance; the reproduction, line references, and outputs above were each verified by direct run against the cited commit.

Happy to be assigned — I can open a PR adding --sort path to the rg argv built in _run_ripgrep (or sorting the returned lines before _apply_head_limit slices them), mirroring how _glob_helper.py sorts its results.

Activity

  1. added
    triage/verifyingA bot is verifying whether this bug is real
    triage/confirmedVerified: the reported defect exists
    and removed
    triage/verifyingA bot is verifying whether this bug is real
    on Sep 20, 2026
  2. BlueX888 commented on Sep 20, 2026

    @BlueX888
    ContributorAuthor

    Reproduced this. Root cause: src/agentscope/tool/_builtin/_grep.py:289 builds the rg argv with no sort flag, so rg's parallel walker returns matches in a different order on every invocation and _apply_head_limit (line 272) slices that unstable list — each paginated call skips a different "first N".

    Minimal reproduction:

    python repro_grep_pagination.py
    

    Observed output:

    all matches    : ['NEEDLE0', 'NEEDLE1', 'NEEDLE2', 'NEEDLE3', 'NEEDLE4', 'NEEDLE5']
    page1 offset=0 : ['NEEDLE0', 'NEEDLE2', 'NEEDLE4']
    page2 offset=3 : ['NEEDLE1', 'NEEDLE4', 'NEEDLE5']
    LOST by paging : ['NEEDLE3']
    

    Fix is ready on BlueX888:fix/prep-grep-offset-pagination-loses-matches (commit 924b1359). Passes --sort path to ripgrep so results come back in a stable, path-sorted order, making head_limit/offset paging return each match exactly once.
    Verified with: pytest tests/builtin_grep_test.py -k GrepPaginationTest

    Happy to open the PR once you confirm the approach or assign this to me.

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

    triage/confirmedVerified: the reported defect exists

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions