Basic support for negative searches with parentheses (#4503)

* Basic support for negative searches with parentheses
* `!((author:Alice intitle:hello) OR (author:Bob intitle:world))`
* `(author:Alice intitle:hello) !(author:Bob intitle:world)`
* `!(S:1 OR S:2)`

* Minor documentation / comment

* Remove syslog debug line

6 files changed, 40 insertions, 6 deletions

diff --git a/app/Models/BooleanSearch.php b/app/Models/BooleanSearch.php
index 332757556..b1c7bbd3b 100644
--- a/app/Models/BooleanSearch.php
+++ b/app/Models/BooleanSearch.php
@@ -10,7 +10,7 @@ class FreshRSS_BooleanSearch {
 	/** @var array<FreshRSS_BooleanSearch|FreshRSS_Search> */
 	private $searches = array();
 
-	/** @var string 'AND' or 'OR' */
+	/** @var string 'AND' or 'OR' or 'AND NOT' */
 	private $operator;
 
 	public function __construct(string $input, int $level = 0, $operator = 'AND') {
@@ -123,7 +123,20 @@ class FreshRSS_BooleanSearch {
 				$hasParenthesis = true;
 
 				$before = trim($before);
-				if (preg_match('/\bOR$/i', $before)) {
+				if (preg_match('/[!-]$/i', $before)) {
+					// Trim trailing negation
+					$before = substr($before, 0, -1);
+
+					// The text prior to the negation is a BooleanSearch
+					$searchBefore = new FreshRSS_BooleanSearch($before, $level + 1, $nextOperator);
+					if (count($searchBefore->searches()) > 0) {
+						$this->searches[] = $searchBefore;
+					}
+					$before = '';
+
+					// The next BooleanSearch will have to be combined with AND NOT instead of default AND
+					$nextOperator = 'AND NOT';
+				} elseif (preg_match('/\bOR$/i', $before)) {
 					// Trim trailing OR
 					$before = substr($before, 0, -2);
 
diff --git a/app/Models/Entry.php b/app/Models/Entry.php
index d20f5f2a7..8d20e5412 100644
--- a/app/Models/Entry.php
+++ b/app/Models/Entry.php
@@ -364,10 +364,12 @@ class FreshRSS_Entry extends Minz_Model {
 		$ok = true;
 		foreach ($booleanSearch->searches() as $filter) {
 			if ($filter instanceof FreshRSS_BooleanSearch) {
-				// BooleanSearches are combined by AND (default) or OR (special case) operator and are recursive
+				// BooleanSearches are combined by AND (default) or OR or AND NOT (special cases) operators and are recursive
 				if ($filter->operator() === 'OR') {
 					$ok |= $this->matches($filter);
-				} else {
+				} elseif ($filter->operator() === 'AND NOT') {
+					$ok &= !$this->matches($filter);
+				} else {	// AND
 					$ok &= $this->matches($filter);
 				}
 			} elseif ($filter instanceof FreshRSS_Search) {
diff --git a/app/Models/EntryDAO.php b/app/Models/EntryDAO.php
index d69702c60..02552affe 100644
--- a/app/Models/EntryDAO.php
+++ b/app/Models/EntryDAO.php
@@ -770,6 +770,9 @@ SQL;
 				if ($filterSearch !== '') {
 					if ($search !== '') {
 						$search .= $filter->operator();
+					} elseif ($filter->operator() === 'AND NOT') {
+						// Special case if we start with a negation (there is already the default AND before)
+						$search .= ' NOT';
 					}
 					$search .= ' (' . $filterSearch . ') ';
 					$values = array_merge($values, $filterValues);
diff --git a/docs/en/users/03_Main_view.md b/docs/en/users/03_Main_view.md
index a5a2afe34..eb8fe0f01 100644
--- a/docs/en/users/03_Main_view.md
+++ b/docs/en/users/03_Main_view.md
@@ -239,10 +239,13 @@ can be used to combine several search criteria with a logical *or* instead: `aut
 You don’t have to do anything special to combine multiple negative operators. Writing `!intitle:'thing1' !intitle:'thing2'` implies AND, see above. For more pointers on how AND and OR interact with negation, see [this GitHub comment](https://github.com/FreshRSS/FreshRSS/issues/3236#issuecomment-891219460).
 Additional reading: [De Morgan's laws](https://en.wikipedia.org/wiki/De_Morgan%27s_laws).
 
-Finally, parentheses may be used to express more complex queries:
+Finally, parentheses may be used to express more complex queries, with basic negation support:
 
 * `(author:Alice OR intitle:hello) (author:Bob OR intitle:world)`
 * `(author:Alice intitle:hello) OR (author:Bob intitle:world)`
+* `!((author:Alice intitle:hello) OR (author:Bob intitle:world))`
+* `(author:Alice intitle:hello) !(author:Bob intitle:world)`
+* `!(S:1 OR S:2)`
 
 ### By sorting by date
 
diff --git a/docs/fr/users/03_Main_view.md b/docs/fr/users/03_Main_view.md
index 11df737b7..3a65c1f7f 100644
--- a/docs/fr/users/03_Main_view.md
+++ b/docs/fr/users/03_Main_view.md
@@ -268,7 +268,10 @@ encore plus précis, et il est autorisé d’avoir plusieurs instances de :
 Combiner plusieurs critères implique un *et* logique, mais le mot clef `OR`
 peut être utilisé pour combiner plusieurs critères avec un *ou* logique : `author:Dupont OR author:Dupond`
 
-Enfin, les parenthèses peuvent être utilisées pour des expressions plus complexes :
+Enfin, les parenthèses peuvent être utilisées pour des expressions plus complexes, avec un support basique de la négation :
 
 * `(author:Alice OR intitle:bonjour) (author:Bob OR intitle:monde)`
 * `(author:Alice intitle:bonjour) OR (author:Bob intitle:monde)`
+* `!((author:Alice intitle:bonjour) OR (author:Bob intitle:monde))`
+* `(author:Alice intitle:bonjour) !(author:Bob intitle:monde)`
+* `!(S:1 OR S:2)`
diff --git a/tests/app/Models/SearchTest.php b/tests/app/Models/SearchTest.php
index 74c1596f6..3fb5a144f 100644
--- a/tests/app/Models/SearchTest.php
+++ b/tests/app/Models/SearchTest.php
@@ -330,6 +330,16 @@ class SearchTest extends PHPUnit\Framework\TestCase {
 					' ((e.id IN (SELECT et.id_entry FROM `_entrytag` et, `_tag` t WHERE et.id_tag = t.id AND t.name IN (?)) )) ',
 				['%tag%','%Hello%','%Alice%','%example%','3','%World%', 'Bleu']
 			],
+			[
+				'!((author:Alice intitle:hello) OR (author:Bob intitle:world))',
+				' NOT (((e.author LIKE ? AND e.title LIKE ? )) OR ((e.author LIKE ? AND e.title LIKE ? ))) ',
+				['%Alice%', '%hello%', '%Bob%', '%world%'],
+			],
+			[
+				'(author:Alice intitle:hello) !(author:Bob intitle:world)',
+				' ((e.author LIKE ? AND e.title LIKE ? )) AND NOT ((e.author LIKE ? AND e.title LIKE ? )) ',
+				['%Alice%', '%hello%', '%Bob%', '%world%'],
+			]
 		];
 	}
 }