Wrong set of entries returned for some search filters

[yaonos]

Issue Description
389 Directory Server doesn't return the correct set of entries when the search filter is expressed like this :

(|(attribute_1=value_1)(&(attribute_2=value_2)(!(|(attribute_3=value_3)(attribute_4=value_4)))))

This filter does not return the entries that match the (&(attribute_2=value_2)(!(|(attribute_3=value_3)(attribute_4=value_4)))) part of the filter.

Consequently a search with the filter (|(&(attribute_2=value_2)(!(|(attribute_3=value_3)(attribute_4=value_4))))) always returns zero entries.

Note : if the filter is rewitten as (|(attribute_1=value_1)(&(attribute_2=value_2)(!(attribute_3=value_3))(!(attribute_4=value_4)))), that is logicaly equivalet as the first filter, the server returns the expected set of entries.

Package Version and Platform:

• Platform: RedHat Enterprise Linux 8
• Package and version: observed with 389-ds-base-2.2.9-2.el8.x86_64, 389-ds-base-2.5.1-2.el8.x86_64 and 389-ds-base-3.1.1-1.el8.x86_64

RPM version 2.5.1 was adapted to RHEL 8 from RHEL 9's 389-ds-base-2.5.2-1.el9.src.rpm.
RPM version 3.3.1 was adapted to RHEL 8 from Fedora's 389-ds-base-3.1.1-2.fc41.src.rpm that I downloaded from https://koji.fedoraproject.org/koji/buildinfo?buildID=2519163

Steps to Reproduce

Steps to reproduce the behavior:

1. Configure a new suffix named dc=example,dc=com and initialize it with the content of the file example_ldif.txt that is attached to this bug report
2. Search the content of the directory whith these parameters :
   base : dc=example,dc=com
   scope : sub
   filter : (|(telephoneNumber=3456)(&(telephoneNumber=1234)(!(|(uid=user1)(uid=user4)))))
3. The LDAP server returns one entry : uid=user6,ou=person,dc=example,dc=com
4. Search the content of the directory whith these parameters :
   base : dc=example,dc=com
   scope : sub
   filter : (|(&(telephoneNumber=1234)(!(|(uid=user1)(uid=user4)))))
5. The LDAP server returns nothing

Expected results

The first search is expected to return these entries :

• uid=user2,ou=person,dc=example,dc=com
• uid=user3,ou=person,dc=example,dc=com
• uid=user6,ou=person,dc=example,dc=com
• uid=user8,ou=person,dc=example,dc=com
• uid=user9,ou=person,dc=example,dc=com

The second search is expected to return these entries :

• uid=user2,ou=person,dc=example,dc=com
• uid=user3,ou=person,dc=example,dc=com
• uid=user8,ou=person,dc=example,dc=com
• uid=user9,ou=person,dc=example,dc=com

Additional context

This bug has been discovered with other attributes and a slightly different search filter. The sample LDIF file and the filters have been crafted in order to be able to explain this issue.
example_ldif.txt

[tbordaz]

Thanks for the excellent testcase. JFR

"(&(telephoneNumber=1234)(!(|(uid=user1)(uid=user4))))"  returns the valid set

dn: uid=user2,ou=person,dc=example,dc=com
uid: user2

dn: uid=user3,ou=person,dc=example,dc=com
uid: user3

dn: uid=user8,ou=person,dc=example,dc=com
uid: user8

dn: uid=user9,ou=person,dc=example,dc=com
uid: user9

then

"(telephoneNumber=3456)" returns the valid set

dn: uid=user6,ou=person,dc=example,dc=com
uid: user6

So this is the result of both components that show the problem

[tbordaz]

The good news is that the indexes are safe, they return a valid candidate list (7 candidates) but because of the filter specificity, it evaluates the intended filter. The filter does not match some entries that it should match. So the bad news is that evaluation of the filter is possibly broken...