IMAP search requires parentheses

IMAP protocol uses Polish notation (also known as prefix notation) for client queries. In general it means, that operator (in case of IMAP search it’s always a logical operator) is placed left of its operands.

Polish notation

Expression that would be written in conventional infix notation as:
(5 − 6) * 7
can be written in prefix/Polish notation as:
* (− 5 6) 7
As all mathematical operands are binary (or have defined number of operands) we don’t need parentheses to correctly evaluate this expression:
* − 5 6 7

Polish notation doesn’t require parentheses.

IMAP search needs parentheses

Although IMAP search syntax uses Polish notation it actually requires parentheses to be evaluated unambiguously.

This is because there is no explicitly defined AND operator, that takes exactly 2 operands.

RFC 3501:

When multiple keys are specified, the result is the intersection (AND function) of all the messages that match those keys.

So although it is true that Polish and reverse Polish notations don’t require parentheses, it is not true that IMAP search doesn’t require them.

‘OR/AND’ example

Expression 1a:

Regular notation:
(SUBJECT subject OR BODY body) AND FROM from

Polish notation:
AND OR SUBJECT subject BODY body FROM from

IMAP’s Polish notation (note there is no AND operator):
OR SUBJECT subject BODY body FROM from

Expression 1b:

Regular notation:
SUBJECT subject OR (BODY body AND FROM from)

Polish notation:
OR SUBJECT subject AND BODY body FROM from

IMAP’s Polish notation (note there is no AND operator):
OR SUBJECT subject BODY body FROM from

1a != 1b

Expression 1a is not equal to Expression 1b:
((a or b) and c) != (a or (b and c))

For:
a = true
b = true
c = false

We have:
((true or true) and false) != (true or (true and false))
false != true

Parentheses are needed

But when there is no AND operator, IMAP’s Polish notations look exactly the same, thus we need parentheses!

Expression 1a (IMAP’s Polish notation with parentheses):
(OR SUBJECT subject BODY body) FROM from

Expression 1b (IMAP’s Polish notation with parentheses):
OR SUBJECT subject (BODY body FROM from)

OR SUBJECT subject BODY body FROM from
is treated like
(OR SUBJECT subject BODY body) FROM from

‘NOT’ example

Expression 2a:

Regular notation:
NOT (SUBJECT subject AND BODY body)

Polish notation:
NOT AND SUBJECT subject BODY body

IMAP’s Polish notation (note there is no AND operator):
NOT SUBJECT subject BODY body

Expression 2b:

Regular notation:
(NOT SUBJECT subject) AND BODY body

Polish notation:
AND NOT SUBJECT subject BODY body

IMAP’s Polish notation (note there is no AND operator):
NOT SUBJECT subject BODY body

2a != 2b

Expression 2a is obviously not equal to Expression 2b.

Parentheses are needed

Again IMAP’s Polish notations look the same. We need parentheses!

Expression 2a (IMAP’s Polish notation with parentheses):
NOT (SUBJECT subject BODY body)

Expression 2b (IMAP’s Polish notation with parentheses):
(NOT SUBJECT subject) BODY body

NOT SUBJECT subject BODY body
is treated like
(NOT SUBJECT subject) BODY body

Tags: ,

Questions?

Consider using our Q&A forum for asking any questions.