MBOX-Line: From tss at iki.fi  Fri May  3 03:55:52 2013
To: imap-protocol@u.washington.edu
From: Timo Sirainen <tss@iki.fi>
Date: Fri Jun  8 12:34:51 2018
Subject: [Imap-protocol] Imap Search Command Parse Logic
In-Reply-To: <000001ce47e7$4c7bead0$e573c070$@i-freelancer.net>
References: <000001ce47e7$4c7bead0$e573c070$@i-freelancer.net>
Message-ID: <5EC8241E-F964-43EE-85EA-0DCD76E021A4@iki.fi>

On 3.5.2013, at 13.16, ??? <ayluen@i-freelancer.net> wrote:

> I'm currently working on implementing IMAP protocol on our mail server.  This is my first time implementing such a big project and I've so far coded a majority of IMAP commands in the RFC, except the Search command.
> I've been searching on the internet and studied postfix(RPN) algorithm for weeks to see how to parse the search command correctly.
> It seems Postfix would work until I encountered something like OR OR A B C D ==> (OR (OR A B) C) D
> Could anyone point me a direction on how to implement the Search command when there are multiple ORs?
> Should I even consider using Postfix(RPN) algorithm to parse search command?

Did you notice that it's also possible to use parenthesis explicitly in the search query? I implemented it by parsing the search command to a tree structure and then iterating through the tree. There are quite a lot of optimizations you can then also do with the tree structure, like first trying to see if the search can even match the message sequence or UID, next checking for flags, then checking for slower ones. I'm not sure if there are any other reasonable ways to even implement it.

BTW. You should test your implementation's RFC compliancy with http://imapwiki.org/ImapTest


