BoolWeight: ((A AND_NOT B) OR C) AND D can return documents that the AND_NOT should exclude

[Adrian Ratiu]

Hello,

This only affects version 2.1.0 and current main, not 1.4.

With BoolWeight, the query "((A AND_NOT B) OR C) AND D" returns a document that has A, B and D. It shouldn't, because the document has B.

With the default weighting scheme the result is correct.

I hit this through notmuch, which uses BoolWeight for all its searches and counts. A search like (x and not y) or z, combined with and tag:unread, returned mail that and not y should have excluded.

To reproduce, see the attached andnot-boolweight.cc: on 2.1.0 it prints "1 matches (expected 0)".

Possible root cause:

AndNotPostList::skip_to() does nothing if the target docid isn't after pl->get_docid(). But before the postlist has been positioned, that value isn't meaningful, and a term postlist may already return its first docid. So the first skip_to() can stop on a document without checking it against the right side.

With BoolWeight, the OR is a BoolOrPostList, which calls skip_to() on the AND_NOT before anything else has positioned it, so the bug shows up.

This seems to have come in when AndNotPostList was reimplemented using WrapperPostList. 1.4 tracked the position itself.

Possible fix:

I have a patch with a regression test done with the assistence of Claude code, that makes skip_to() always pass the call on to the left side and then check the result against the right side. make check passes with it.

I can send it on the mailing list or open a github PR if it looks acceptable. Feel free to land another fix for this

[Adrian Ratiu]

bug reproducer

[Adrian Ratiu]

claude-fix.patch