Opened 3 weeks ago

Last modified 9 days ago

#857 new defect

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

Reported by: Adrian Ratiu Owned by: Olly Betts
Priority: normal Milestone: 2.1.1
Component: Matcher Version: 2.1.0
Severity: major Keywords: BoolWeight AND_NOT regression notmuch
Cc: Adrian Ratiu Blocked By:
Blocking: Operating System: All

Description

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

Attachments (3)

andnot-boolweight.cc​ (1.0 KB ) - added by Adrian Ratiu 3 weeks ago.
bug reproducer
0001-Fix-AndNotPostList-skip_to-before-it-has-been-positi.patch​ (6.3 KB ) - added by Adrian Ratiu 3 weeks ago.
claude-fix.patch
selectpostlist-skip_to.cc​ (1.5 KB ) - added by Adrian Ratiu 9 days ago.

Download all attachments as: .zip

Change History (5)

by Adrian Ratiu, 3 weeks ago

Attachment: andnot-boolweight.cc​ added

bug reproducer

by Adrian Ratiu, 3 weeks ago

claude-fix.patch

comment:1 by Olly Betts, 9 days ago

I'd prefer to avoid LLM patches at this point - they're generally more work to review, and often seem to miss important details. E.g. here it seems confused about use of NULL vs nullptr (main no longer uses NULL here) and with the indentation change it's easier for me to just make the change myself than to verify the patch makes it correctly.

The reproducer in the patch seems to be different to the standalone one, but the standalone version reproduces the problem and is simpler so I'll go with that unless there's something better about the other one which I'm missing.

SelectPostList::skip_to() has essentially the same problem, and should get the same treatment, but I still need to work out how to trigger it there.

comment:2 by Adrian Ratiu, 9 days ago

Thanks Olly. Claude created a short reproducer for SelectPostList::skip_to(), hope it helps.

by Adrian Ratiu, 9 days ago

Attachment: selectpostlist-skip_to.cc​ added
Note: See TracTickets for help on using tickets.