{"article":{"slug":"quality-imap-part-1-your-mailbox-is-a-database","title":"Quality IMAP, Part 1: Your Mailbox Is A Database","subtitle":null,"summary":"The first post in Aerogramme's series on implementing IMAP correctly, explaining why fine-grained email retrieval and querying make a mailbox behave like a database and how the server handles it.","content_type":"blog_post","language":"en","canonical_url":"https://aerogramme.deuxfleurs.fr/blog/2026-quality-imap-part-1/","author":{"name":"Aerogramme team","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Aerogramme","url":"https://aerogramme.deuxfleurs.fr/","listing_slug":null,"listing":null},"topics":[{"name":"email","slug":"email","url":"https://listedarticles.com/topics/email"},{"name":"databases","slug":"databases","url":"https://listedarticles.com/topics/databases"},{"name":"open-source","slug":"open-source","url":"https://listedarticles.com/topics/open-source"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":3563,"reading_minutes":15,"published_at":"2026-11-16T00:00:00.000Z","added_at":"2026-11-16T16:53:40.375Z","updated_at":"2026-11-16T16:53:40.375Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/quality-imap-part-1-your-mailbox-is-a-database","markdown_url":"https://listedarticles.com/articles/quality-imap-part-1-your-mailbox-is-a-database.md","example":false,"citation":"Aerogramme team, Aerogramme. \"Quality IMAP, Part 1: Your Mailbox Is A Database.\" 16 Nov 2026. https://aerogramme.deuxfleurs.fr/blog/2026-quality-imap-part-1/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://aerogramme.deuxfleurs.fr/blog/2026-quality-imap-part-1/"},"body_markdown":"# Quality IMAP, Part 1: Your Mailbox Is A Database\n\nPublished on\n\nNovember 16, 2026\n\n19 min reading time\n\n3704 words\n\n*During the past year, we have significantly improved the reliability and\ncorrectness of Aerogramme's IMAP implementation. This is the first part in a\nseries of blog posts elaborating on why implementing IMAP correctly is not so easy, and the set of\ntechniques we have been using to make our IMAP code as high-quality as\nwe can. In this first part, we focus on one challenging aspect of IMAP:\nfine-grained retrieval and querying of emails.*\n\n---\n\n*[Aerogramme](https://aerogramme.deuxfleurs.fr/) is an experimental email server\n(& calendar, contacts), designed to be geo-distributed, hosted outside of\ndatacenters, on refurbished hardware, and reliable even in presence of network\nissues and hardware failures. It is built on top of\n[Garage](https://garagehq.deuxfleurs.fr/) and shares the same philosophy.\nAerogramme is AI-free: we do not wish to use unethical technology and prefer to\nspend effort on careful craftmanship and community-building.*\n\n**Implementing an IMAP server is not easy.** Partly because IMAP is an\nold protocol, with a good number of extensions that has accumulated quite a bit\nof complexity over time. On top of that IMAP provides - for good reasons - two\nclasses of features that are fundamentally challenging to implement:\nfine-grained retrieval and querying of email contents and concurrent\nmulti-client multi-session access to mailboxes.\n\nThis is the first part in a series of posts discussing how we have been\napproaching IMAP access. In the past year, we have been\nrefining Aerogramme's IMAP implementation to be \"more correct\", in a context\nwhere \"correctness\" is unfortunately not always well specified: IMAP and email are defined in\ndocuments that are often vague, and furthermore, real-world implementations\ndo not always follow specifications.\n\nToday, we'll walk you though our work on the **correctness and reliability of\nAerogramme for retrieving and querying emails**, and explain why your mailbox is,\nin fact, a database...\n\n*This work was funded by [NLNet](https://nlnet.nl) under the \"[Aerogramme\n1.0](https://nlnet.nl/project/Aerogramme-1.0/)\" grant, and could not have been\npossible without their support.*\n\n*Feel free to join the Aerogramme [matrix\nchannel](https://matrix.to/#/#aerogramme:deuxfleurs.fr) for updates or if you\njust want to chat!*\n\n# Your mailbox is a database\n\nOne challenge of the IMAP specification is the rich feature-set it provides for\nretrieving mailbox and email contents. We may sometimes think of a mailbox as a\ndirectory containing plain email files; however, from the point of view of an\nIMAP server (or client), a mailbox is closer to a database, accessed using a\ndedicated query language.\n\nFor instance, mobile clients, which have slower and unreliable connectivity,\nbenefit from fine-grained querying of a mailbox contents. User experience is\nmuch better if an email client can selectively fetch the subject of new emails\n(to update the list of emails in the mailbox) without having to first download\nall of their attachments or doing a sync of the entire mailbox.\n\nTo facilitate the mobile client use-case, IMAP specifies two key mechanisms for querying and (partial) retrieval of\nemails in a mailbox:\n\n- [SEARCH](https://datatracker.ietf.org/doc/html/rfc3501#section-6.4.4) looks up\n  the emails in a mailbox that satisfy a given \"search criteria\"; it returns\n  their identifiers. Criteria can select emails based on the contents of specific\n  headers, date, text contents, or flags - metadata attached to emails that can be\n  edited by the client. It can also be any combination of those using OR/NOT/AND\n  boolean operators.\n- [FETCH](https://datatracker.ietf.org/doc/html/rfc3501#section-6.4.5) queries\n  the contents of an email given its identifier. Extremely versatile. On\n  top of fetching the entire email, it allows querying an email based on its\n  high-level structure (emails have a recursive structure with sub-parts\n  containing e.g. attachments or text+html alternative views of the same\n  contents), its raw byte-level representation, or a combination of both. It is\n  possible to selectively fetch sub-parts of an email (according to its\n  structure), obtain an \"abstract syntax tree\" (AST) for the email and the value\n  of some of its headers, and also fetch specific byte ranges for sub-parts.\n\nA direct consequence of these features is that **an IMAP server actually needs to parse\nthe emails, not just store them**. It then needs to (correctly) interpret the (sometimes\ntricky) query language of SEARCH and FETCH, and internally support a data\narchitecture that enable efficiently searching and querying over the emails.\n\n# Email querying in Aerogramme\n\nOur implementation of SEARCH and FETCH is backed by\nthe three following components:\n\n*The logic for SEARCH and FETCH is implemented as an interpreter* that takes\nalready parsed emails and walks down their AST to evaluate IMAP-specific\nqueries[1](#compile-queries). This separates email structure (email ASTs do not\ndepend on IMAP concepts) from IMAP-specific business logic. This layer has been\n*significantly reworked* in the last months, fixing a good number of logic bugs\nand edge cases in our implementation of the SEARCH and FETCH IMAP specification.\n\n*Email parsing is done using the\n[eml-codec](https://git.deuxfleurs.fr/deuxfleurs/eml-codec) companion library*,\nthat we also develop and maintain. The eml-codec library parses emails into a\nrich, structured AST while also giving access to raw input slices that\ncorrespond to relevant AST nodes; this is required for implementing FETCH. In\nthe past year, eml-codec has evolved from an email parsing library with\nIMAP-specific quirks to a robust, well-tested, general-purpose email library\nwith support for both parsing and printing of emails. You can read more about\nthe library design choices in our work-in-progress [design\ndocument](https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/src/branch/main/doc/DESIGN.md).\n\n*Aerogramme's internal data architecture splits mailbox state, email metadata,\nand email contents.* It is [briefly\ndescribed](https://aerogramme.deuxfleurs.fr/documentation/internals/mailbox/) in\nAerogramme's documentation. Mailbox state (emails IDs and flags) and email\nmetadata (parsed headers, date, size) are stored in Aerogramme's metadata\nstorage using [Garage\nK2V](https://garagehq.deuxfleurs.fr/documentation/reference-manual/features/#k2v-api-experimental),\nwhile email contents are stored in blob storage using [Garage\nS3](https://garagehq.deuxfleurs.fr/documentation/reference-manual/features/#s3-api).\nThis allows SEARCH to be efficient by only reading pre-computed information in\nmetadata storage. At the moment there are no other significant optimizations\nfor FETCH/SEARCH; the likely next step would be to add a full-text search\nengine.\n\nThese components are all quite non-trivial! Let's now talk about the strategies\nwe've deployed to make them as correct as we could.\n\n# Testing Aerogramme's FETCH and SEARCH query interpreter\n\nWe ran our implementation of FETCH and SEARCH through\n[ImapTest](https://dovecot.github.io/imaptest/): a testing tool for IMAP servers\nmaintained by the Dovecot developers. `ImapTest` was invaluable in surfacing issues\nwith FETCH and SEARCH, but is equally useful to test all other aspects of IMAP.\n\nMost relevant for FETCH and SEARCH was the test suite provided with `ImapTest`: a\ncollection of hand-crafted test scenarios testing many subtle or \"interesting\"\naspects of the IMAP specification. Each scenario consists of IMAP\ncommands to send to the server, and a specification of the corresponding\nexpected responses.\n\nRunning the ImapTest test suite found a small number of bugs in SEARCH, mostly\nin edge-cases of the specification. However, testing FETCH\nrevealed that our initial implementation of the `BODY[<section>]` subcommand was\nconceptually wrong in many cases! This subcommand of `FETCH` retrieves a\nsub-part of an email by following its structure, which we implement by walking\ndown the email's AST. Our initial implementation was done by reading the IMAP\nspecification and interpreting its sometimes vague wording as best as we could;\nonly testing with `ImapTest` made us realize that our best-guess interpretation\nwas wrong in many cases. More precisely: it did not match ImapTest's reading of\nthe spec, which, in doubt, is what we prefer to follow!\n\n`ImapTest` was also relatively pleasant to use to do manual \"differential testing\"\nfor any remaining edge-cases: when we had any doubt, we could easily write\nadditional scenarios and compare Aerogramme's output with Dovecot's; treating\nDovecot as an oracle. After a few rounds of bugfixing, Aerogramme's\nimplementation of FETCH and SEARCH is now in much better shape.\n\n**The lesson we learned is that the IMAP specification can leave room for\ninterpretation in surprising ways.** In fact, to further illustrate this point,\nlet's talk about one `ImapTest` scenario that we haven't \"fixed\" yet in Aerogramme\nbecause we just found it very confusing, and we are not sure what to do!\n\n### Example: the confusing case of `SEARCH` and structured fields\n\nHe's a tricky case. `SEARCH FROM <string>` returns the list of emails whose `From`\nheader \"contains\" the given string. Now, what does \"contains\" mean here,\nexactly? When running `SEARCH FROM foo@example.com` on the two following\nheaders, which ones should match?\n\n```\nFrom: Foo Bar <foo@example.com>\nFrom: Foo Bar < \"foo\" (comment) @ example.com>\n```\n\nSome additional context on email syntax is useful here: these two email addresses are\nequivalent. The local-part of the email (before the `@`) allows quoted strings,\nso `\"foo\"` can be used and simply denotes `foo`. Email syntax also allows\ncomments in various places; they are written between parentheses. Comments have\nno formal meaning but are shown by email clients and can be useful; they are\nsometimes used by mailing-list software to indicate the name of the list.\nAs an example [SYMPA](https://sympa.community) emits `From` headers of the form `From: Alice (via Super Friends List) <list-address@server.org>`).\n\nAt the moment, Aerogramme implements `SEARCH FROM` as plain substring search on\nthe text representation of the header: here, the first header matches, but not\nthe second. However, *the ImapTest test suite says that both headers should\nmatch*! So, what does the specification says?\n\nThe [IMAP specification](https://datatracker.ietf.org/doc/html/rfc3501)[2](#imap-search-from) for SEARCH says:\n\n```\nFROM <string>\n   Messages that contain the specified string in the envelope\n   structure's FROM field.\n```\n\nHmm, so, what is this \"envelope structure\"? Reading further:\n\n```\nAn envelope structure is a parsed representation of the [RFC5322] \nheader of the message. [...] The from, sender, reply-to, to, cc, \nand bcc fields are parenthesized lists of address structures. [...]\nAn address structure is a parenthesized list that describes an \nelectronic mail address. The fields of an address structure are in \nthe following order: display name, [SMTP] at-domain-list [...], \nmailbox name (local-part ABNF production from [RFC5322]), and hostname.\n```\n\nSo the FROM field of an email's \"envelope structure\" contains a *structured* representation of *parsed* email addresses.\nRegarding our two headers above, they are both represented in the envelope structure as:\n\n```\n(\"Foo Bar\" NIL \"foo\" \"example.com\")\n```\n\nWhat does it mean for this structured value to \"contain\" the string\n`foo@example.com`? Clearly none of the strings in the structure contain\n`foo@example.com`, so perhaps instead we should re-print the structure as an\nemail address and do a substring search on that? However, *there is not a unique\nway of printing a given email address*, and the IMAP specification does not\ndefine any...\n\nWe are quite curious to know if IMAP experts have more to say on this point!\n\nIn the meantime, our bugfixes for FETCH and SEARCH have been shipped in\n[Aerogramme 0.5.1](https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.5.1)\n(see the release notes for more details), with the exception of [two extra\nfixes](https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/pulls/195) shipped in\n[Aerogramme 0.6](https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.6.0).\n\n# Improving email parsing in Aerogramme\n\nFETCH and SEARCH operate on the *parsed* email ASTs produced by\n[eml-codec](https://git.deuxfleurs.fr/deuxfleurs/eml-codec). How do we\nensure that we have correctly implemented all the subtleties of the email format\nin eml-codec, which is itself described in an old and tricky set of\nspecifications? As often, the answer is: more testing.\n\n## Property-Based Testing for eml-codec\n\nTo ensure our implementation is correct, we performed fuzzer-guided Property-Based Testing (PBT) of the email parser and\nprinter in eml-codec. Specifically, [we tested the following \"roundtrip\"\nproperty](https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/src/commit/a317094811edaadbbd77657c0da05e3e771c1af6/fuzz/fuzz_targets/message_print_parse.rs#L8):\n\n> “for an arbitrary email value in eml-codec's internal AST, printing it then\n> parsing the printed output must yield an equivalent AST”\n\nThe starting AST is generated by a fuzzer as a structured value using the\n`Arbitrary` trait; the [cargo-fuzz tutorial](https://rust-fuzz.github.io/book/cargo-fuzz.html) calls this\n\"Structure-Aware Fuzzing\". A roundtrip in the other direction, i.e.\n\"parse then print then test for string equality\" would not generally hold, as\nthere are many equivalent ways of printing the same email, for instance because\nof line folding...\n\nWhile it may seem that any reasonable implementation would satisfy our roundtrip\nproperty, in practice, this methodology immediately surfaced a lot\nof bugs and edge cases.\n\nThe recurring theme was that the fuzzer would generate \"exotic\" AST values\nbreaking the roundtrip property, for which we had to clarify:\n\n- if these revealed an inconsistency/confusion between parser and printer,\n  where the value, after printing, could result in invalid syntax or syntax\n  that parsed into a different AST;\n- if these values should in fact be considered invalid; this means\n  strengthening the AST invariants and fixing the fuzzer-based generator\n  accordingly;\n- or whether the \"equivalence checking\" function for AST values needed to be\n  relaxed (in some cases, syntactically different values represent the \"same\"\n  conceptual value up to implementation details).\n\nIn the first case, this fixed bugs or potential security issues for users of the\nparser (like Aerogramme) or printer. In the second case, it improved the\ndefinition of internal AST types, which is relevant when using eml-codec to\nprogramatically compose emails, not something we use in Aerogramme itself, but relevant for an\nexperimental mailing-list server project in Deuxfleurs using the same library.\n\nTo illustrate the kind of issues that we are talking about here, let's look at\nan tricky example that was found using our fuzzing methodology.\n\n### Example: encoded words shenanigans\n\nThe [\"MIME Part Three\" specification\n(RFC2047)](https://datatracker.ietf.org/doc/html/rfc2047) specifies a way of\nusing non-ASCII text in selected places of email headers. (Full support for\nUTF-8 in headers, which eml-codec also supports, was only [introduced\nlater](https://datatracker.ietf.org/doc/html/rfc6532).) Where allowed by the\nspecification, ASCII text can be replaced by an \"encoded word\": an ASCII\nencoding of non-ASCII text using special syntax introduced by the specification.\n\nAs an example, the UTF-8 word `aérogramme` can be encoded as follows:\n\n```\n=?utf-8?q?a=C3=A9rogramme?=\n```\n\nMore generally, a MIME encoded word has the following structure:\n\n```\n=? <charset> ? <encoding> ? <encoded-text> ?=\n```\n\nWhen using the `q` encoding like above, *most* ASCII characters can be used\ndirectly in the encoded text, and other bytes must be encoded as `=` followed by\ntheir hexadecimal code.\n\nNow, let us consider the following `From` header:\n\n```\nFrom: =?utf-8?q?@[?= X]\n```\n\nThis looks like an encoded word followed by some extra junk; is this a valid\n`From` header? Perhaps surprisingly, *there is no encoded word in this header,\nand it is a valid email address!* The email address is `=?utf-8?q?` @ `[?= X]`\n(it is technically valid!), where the part after the '@' uses the uncommon\n\"domain-literal\" syntax.\n\nNow, consider the following `Subject` header with the same byte representation:\n\n```\nSubject: =?utf-8?q?@[?= X]\n```\n\nThis time, the first part of the header *is an encoded word*, and the whole\nheader tells us that the subject is the string `@[ X]`!\n\nThe explanation for this behavior follows from the specification (which is\n[fairly clear on this\naspect](https://datatracker.ietf.org/doc/html/rfc2047#section-5)): the set of\nASCII characters that can be used *unescaped* in `<encoded-text>` **depends on\nthe context in which the encoded word appears**.\n\nEncoded words *can appear* in `From` headers (for example `From: =?utf-8?q?a=C3=A9rogramme?= <aerogramme@deuxfleurs.fr>` is valid), but in that\ncontext they cannot use `@` or `[` unescaped, which is why the first example\ndoes not in fact contain a valid encoded word. In the context of a `Subject`\nheader, the set of valid unescaped characters is broader and includes both `@`\nand `[`, making `=?utf-8?q?@[?=` is a valid encoded word representing the string\n`@[`.\n\nTo implement this behavior, we needed to correctly track the context in which we\nparse encoded words, \"tokenize\" them according to that context, and also track\ncontext sensitivity in our email AST and during printing. Getting every detail\nto align properly between parsing, our internal AST, and printing took us\nseveral attempts! In that process, our property-testing setup was *extremely\nuseful*, as it could quickly come up with new convoluted examples like the one\nabove that revealed bugs in edge cases of our code.\n\nThe lesson here is that email specifications can be *quite complicated and\ntricky to implement*, even when they are clear! And, in our experience, without\nautomatic test generation (like our fuzzer setup), it is very hard to manually\ncome up with examples that actually cover edge cases...\n\nIf you want to see more details, the bulk of our PBT/fuzzing work on eml-codec\nwas done in [eml-codec\n0.3](https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/releases/tag/0.3) and\nshipped in [Aerogramme\n0.4](https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.4.0), with\nsome [additional\nimprovements](https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/pulls/84) shipped\nin [Aerogramme\n0.6](https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.6.0).\n\n## Testing eml-codec on real-world emails\n\nWe tested eml-codec on collections of real-world emails (more than 100k emails)\nto evaluate and improve the *recovery strategies* of eml-codec's parser on\ninvalid or broken syntax.\n\nMany legitimate emails found in the real world are, indeed, incorrect with\nrespect to [email\nspecifications](https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/#rfc-and-iana-references).\nOften, the use of invalid or broken syntax is local (to specific headers, or\nparts of a header); in some cases, it is \"only\" a minor deviation from the\nspecification.\n\n### Example: the many shapes of message IDs\n\nThe case of \"message IDs\" can be taken as an example. Emails can be given an\nidentifier (specified using the `Message-ID` header) so that later emails can\nreference it (using the `In-Reply-To` and `References` headers). This is useful\nto display email \"threads\" in email clients, for example. The message ID syntax\nis also used to identify attachments with the `Content-ID` header.\n\nReading the\n[specification](https://datatracker.ietf.org/doc/html/rfc5322#section-3.6.4), a\nmessage ID is of the form:\n\n```\n<foo.bar@baz.com>\n```\n\nand a list of message IDs as used by `In-Reply-To` and `References` separates message IDs with whitespace:\n\n```\n<msg1@foo.com> <msg2@bar.eu> <msg3@baz.fr>\n```\n\nThe specification also documents that, for the list syntax, \"obsolete\" syntax\n(that we must support) can include extra text surrounding message IDs...\n\nNow, what do we find in our sample of real-world emails?\n\n```\nContent-ID: <1855BC2C-077C-406B-AEA4-CAF088755676>\n```\n\n-> Emitted by apple-mail, and *invalid*: no `@`!\n\n```\nContent-ID: text-body\nMessage-ID: foo@bar.com\n```\n\n-> *Invalid*: no angle brackets `<`/`>`!\n\n```\nIn-Reply-To: <3DE2736D.F4FCC064@orcaware.com>; from redacted@orcaware.com on Mon, Nov 25, 2002 at 11:01:01AM -0800\nIn-Reply-To: Your message of Thu, 18 Mar 1993 22:28:19 GMT.\\n             <8280.9303182228@damsay.dcs.ed.ac.uk>\n```\n\n-> *Valid*: an instance of the \"obsolete\" syntax documented by the specification.\n\n```\nReferences: <abc@def>,<foo\\n\\tbar@outlook.com>,<baz@outlook.com>\n```\n\n-> Commas are valid as part of the obsolete syntax, but the second message-id is malformed because of incorrect line folding (`\\n\\t`) in the middle of a word.\n\n### Engineering eml-codec for real-world emails\n\nThe consequence is that eml-codec needs to be able to *recover from\nbroken syntax*: on an email containing invalid syntax, it should be able to\ndiscard the broken parts and parse as much as it can from the rest of the email,\ninstead of simply returning an error. It should also ideally be\nable to *parse invalid but common deviations from the specifications* in order\nto recover information instead of discarding them.\n\nWe first extended eml-codec with coarse-grained recovery strategies, such as\ndiscarding an entire header field if we couldn't parse it. This allowed us to\nquickly reach a state where the eml-codec parser is a *total function*: for any\ninput bytes, it always returns an email AST representing an RFC-compliant\nemail[3](#email-ast-compliant), discarding any part of the input it does not\nunderstand.\n\nWe then instrumented the parser to *log each time it discards broken input* when\nrecovering, and ran the instrumented parser on the email that we collected. This\ngave us a lot of examples of legitimate emails with broken syntax. In each case,\nthen, we manually looked at the piece of broken syntax, see if we could make\nsome sense of it, and decide whether:\n\n1. we could reasonably extend our parser to parse it;\n2. we could discard it more selectively (e.g. only discard a broken element in a\n   list instead of discarding the entire list);\n3. our existing discarding strategy was the best we could do.\n\nThis whole process was particularly interesting because it made us face the many\nsubtleties of real-world emails (sometimes far from the \"truth\" of\nspecifications); eml-codec is now much more robust operating on real-world emails!\n\nThis methodology involves a lot of\ntradeoffs and judgment calls: there is a limit to the amount of parsing hacks\nthat we can add in terms of code quality but also parsing ambiguity; and some\nclasses of emails are more critical than others (e.g. we should not spend too\nmuch effort supporting spam emails). A strong design constraint of\neml-codec is that, up to a few exceptions, we want its internal AST to only\nrepresent RFC-compliant emails, so we did not want to pollute it to include\nrandom broken syntax just for the sake of \"recovering more\". The whole process,\nin particular, helped us clarify the\n[design](https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/src/branch/main/doc/DESIGN.md)\nof eml-codec as a library.\n\nFor more details, you can look at the release notes of [eml-codec\n0.3.1](https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/releases/tag/0.3.1) where\nthe bulk of the work is done, building on [eml-codec\n0.2](https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/releases/tag/0.2) for the\ninitial setup of parsing recovery. Both shipped with [Aerogramme\n0.4](https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.4.0).\n\n---\n\nIMAP's search and retrieval features are essential because they allow clients to\nhave a snappy UX while handling mailboxes with thousands of emails. This post\nfocused on getting those basic features right. But, more broadly, we think that\nthe \"mailbox as database\" perspective is useful because it raises the question:\nwhich end-user workflows can we enable and support? Which features should we\nprioritize or optimize to best support the workflows of day-to-day email users?\n\n*Stay tuned for the next blogpost in the series where we discuss the other big\nchallenge for an IMAP server: mailbox concurrency!*\n\n---\n\n1\n\nFollowing the database analogy, the logical next step could be to optimize this by first \"pre-compiling\" queries before running them on emails. Right now we don't know if this optimization would actually matter in practice...\n\n2\n\nThis links to IMAP4rev1 but the more recent IMAP4rev2 isn't more specific on this subject\n\n3\n\nThe current eml-codec AST has a few selected exceptions to this rule, where it allows representing non-compliant data in well identified cases. One of such cases is non-compliant message IDs, such as message IDs without `@`...\n","body_html":"<h1 id=\"quality-imap-part-1-your-mailbox-is-a-database\">Quality IMAP, Part 1: Your Mailbox Is A Database</h1>\n<p>Published on</p>\n<p>November 16, 2026</p>\n<p>19 min reading time</p>\n<p>3704 words</p>\n<p>*During the past year, we have significantly improved the reliability and\ncorrectness of Aerogramme&#39;s IMAP implementation. This is the first part in a\nseries of blog posts elaborating on why implementing IMAP correctly is not so easy, and the set of\ntechniques we have been using to make our IMAP code as high-quality as\nwe can. In this first part, we focus on one challenging aspect of IMAP:\nfine-grained retrieval and querying of emails.*</p>\n<hr />\n<p>*<a href=\"https://aerogramme.deuxfleurs.fr/\" rel=\"nofollow ugc noopener\">Aerogramme</a> is an experimental email server\n(&amp; calendar, contacts), designed to be geo-distributed, hosted outside of\ndatacenters, on refurbished hardware, and reliable even in presence of network\nissues and hardware failures. It is built on top of\n<a href=\"https://garagehq.deuxfleurs.fr/\" rel=\"nofollow ugc noopener\">Garage</a> and shares the same philosophy.\nAerogramme is AI-free: we do not wish to use unethical technology and prefer to\nspend effort on careful craftmanship and community-building.*</p>\n<p><strong>Implementing an IMAP server is not easy.</strong> Partly because IMAP is an\nold protocol, with a good number of extensions that has accumulated quite a bit\nof complexity over time. On top of that IMAP provides - for good reasons - two\nclasses of features that are fundamentally challenging to implement:\nfine-grained retrieval and querying of email contents and concurrent\nmulti-client multi-session access to mailboxes.</p>\n<p>This is the first part in a series of posts discussing how we have been\napproaching IMAP access. In the past year, we have been\nrefining Aerogramme&#39;s IMAP implementation to be &quot;more correct&quot;, in a context\nwhere &quot;correctness&quot; is unfortunately not always well specified: IMAP and email are defined in\ndocuments that are often vague, and furthermore, real-world implementations\ndo not always follow specifications.</p>\n<p>Today, we&#39;ll walk you though our work on the <strong>correctness and reliability of\nAerogramme for retrieving and querying emails</strong>, and explain why your mailbox is,\nin fact, a database...</p>\n<p>*This work was funded by <a href=\"https://nlnet.nl\" rel=\"nofollow ugc noopener\">NLNet</a> under the &quot;<a href=\"https://nlnet.nl/project/Aerogramme-1.0/\" rel=\"nofollow ugc noopener\">Aerogramme\n1.0</a>&quot; grant, and could not have been\npossible without their support.*</p>\n<p>*Feel free to join the Aerogramme <a href=\"https://matrix.to/#/#aerogramme:deuxfleurs.fr\" rel=\"nofollow ugc noopener\">matrix\nchannel</a> for updates or if you\njust want to chat!*</p>\n<h1 id=\"your-mailbox-is-a-database\">Your mailbox is a database</h1>\n<p>One challenge of the IMAP specification is the rich feature-set it provides for\nretrieving mailbox and email contents. We may sometimes think of a mailbox as a\ndirectory containing plain email files; however, from the point of view of an\nIMAP server (or client), a mailbox is closer to a database, accessed using a\ndedicated query language.</p>\n<p>For instance, mobile clients, which have slower and unreliable connectivity,\nbenefit from fine-grained querying of a mailbox contents. User experience is\nmuch better if an email client can selectively fetch the subject of new emails\n(to update the list of emails in the mailbox) without having to first download\nall of their attachments or doing a sync of the entire mailbox.</p>\n<p>To facilitate the mobile client use-case, IMAP specifies two key mechanisms for querying and (partial) retrieval of\nemails in a mailbox:</p>\n<ul><li><p><a href=\"https://datatracker.ietf.org/doc/html/rfc3501#section-6.4.4\" rel=\"nofollow ugc noopener\">SEARCH</a> looks up</p><p>the emails in a mailbox that satisfy a given &quot;search criteria&quot;; it returns\ntheir identifiers. Criteria can select emails based on the contents of specific\nheaders, date, text contents, or flags - metadata attached to emails that can be\nedited by the client. It can also be any combination of those using OR/NOT/AND\nboolean operators.</p></li><li><p><a href=\"https://datatracker.ietf.org/doc/html/rfc3501#section-6.4.5\" rel=\"nofollow ugc noopener\">FETCH</a> queries</p><p>the contents of an email given its identifier. Extremely versatile. On\ntop of fetching the entire email, it allows querying an email based on its\nhigh-level structure (emails have a recursive structure with sub-parts\ncontaining e.g. attachments or text+html alternative views of the same\ncontents), its raw byte-level representation, or a combination of both. It is\npossible to selectively fetch sub-parts of an email (according to its\nstructure), obtain an &quot;abstract syntax tree&quot; (AST) for the email and the value\nof some of its headers, and also fetch specific byte ranges for sub-parts.</p></li></ul>\n<p>A direct consequence of these features is that <strong>an IMAP server actually needs to parse\nthe emails, not just store them</strong>. It then needs to (correctly) interpret the (sometimes\ntricky) query language of SEARCH and FETCH, and internally support a data\narchitecture that enable efficiently searching and querying over the emails.</p>\n<h1 id=\"email-querying-in-aerogramme\">Email querying in Aerogramme</h1>\n<p>Our implementation of SEARCH and FETCH is backed by\nthe three following components:</p>\n<p><em>The logic for SEARCH and FETCH is implemented as an interpreter</em> that takes\nalready parsed emails and walks down their AST to evaluate IMAP-specific\nqueries<a href=\"#compile-queries\">1</a>. This separates email structure (email ASTs do not\ndepend on IMAP concepts) from IMAP-specific business logic. This layer has been\n<em>significantly reworked</em> in the last months, fixing a good number of logic bugs\nand edge cases in our implementation of the SEARCH and FETCH IMAP specification.</p>\n<p>*Email parsing is done using the\n<a href=\"https://git.deuxfleurs.fr/deuxfleurs/eml-codec\" rel=\"nofollow ugc noopener\">eml-codec</a> companion library*,\nthat we also develop and maintain. The eml-codec library parses emails into a\nrich, structured AST while also giving access to raw input slices that\ncorrespond to relevant AST nodes; this is required for implementing FETCH. In\nthe past year, eml-codec has evolved from an email parsing library with\nIMAP-specific quirks to a robust, well-tested, general-purpose email library\nwith support for both parsing and printing of emails. You can read more about\nthe library design choices in our work-in-progress <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/src/branch/main/doc/DESIGN.md\" rel=\"nofollow ugc noopener\">design\ndocument</a>.</p>\n<p>*Aerogramme&#39;s internal data architecture splits mailbox state, email metadata,\nand email contents.* It is <a href=\"https://aerogramme.deuxfleurs.fr/documentation/internals/mailbox/\" rel=\"nofollow ugc noopener\">briefly\ndescribed</a> in\nAerogramme&#39;s documentation. Mailbox state (emails IDs and flags) and email\nmetadata (parsed headers, date, size) are stored in Aerogramme&#39;s metadata\nstorage using <a href=\"https://garagehq.deuxfleurs.fr/documentation/reference-manual/features/#k2v-api-experimental\" rel=\"nofollow ugc noopener\">Garage\nK2V</a>,\nwhile email contents are stored in blob storage using <a href=\"https://garagehq.deuxfleurs.fr/documentation/reference-manual/features/#s3-api\" rel=\"nofollow ugc noopener\">Garage\nS3</a>.\nThis allows SEARCH to be efficient by only reading pre-computed information in\nmetadata storage. At the moment there are no other significant optimizations\nfor FETCH/SEARCH; the likely next step would be to add a full-text search\nengine.</p>\n<p>These components are all quite non-trivial! Let&#39;s now talk about the strategies\nwe&#39;ve deployed to make them as correct as we could.</p>\n<h1 id=\"testing-aerogramme-s-fetch-and-search-query-interpreter\">Testing Aerogramme&#39;s FETCH and SEARCH query interpreter</h1>\n<p>We ran our implementation of FETCH and SEARCH through\n<a href=\"https://dovecot.github.io/imaptest/\" rel=\"nofollow ugc noopener\">ImapTest</a>: a testing tool for IMAP servers\nmaintained by the Dovecot developers. <code>ImapTest</code> was invaluable in surfacing issues\nwith FETCH and SEARCH, but is equally useful to test all other aspects of IMAP.</p>\n<p>Most relevant for FETCH and SEARCH was the test suite provided with <code>ImapTest</code>: a\ncollection of hand-crafted test scenarios testing many subtle or &quot;interesting&quot;\naspects of the IMAP specification. Each scenario consists of IMAP\ncommands to send to the server, and a specification of the corresponding\nexpected responses.</p>\n<p>Running the ImapTest test suite found a small number of bugs in SEARCH, mostly\nin edge-cases of the specification. However, testing FETCH\nrevealed that our initial implementation of the <code>BODY[&lt;section&gt;]</code> subcommand was\nconceptually wrong in many cases! This subcommand of <code>FETCH</code> retrieves a\nsub-part of an email by following its structure, which we implement by walking\ndown the email&#39;s AST. Our initial implementation was done by reading the IMAP\nspecification and interpreting its sometimes vague wording as best as we could;\nonly testing with <code>ImapTest</code> made us realize that our best-guess interpretation\nwas wrong in many cases. More precisely: it did not match ImapTest&#39;s reading of\nthe spec, which, in doubt, is what we prefer to follow!</p>\n<p><code>ImapTest</code> was also relatively pleasant to use to do manual &quot;differential testing&quot;\nfor any remaining edge-cases: when we had any doubt, we could easily write\nadditional scenarios and compare Aerogramme&#39;s output with Dovecot&#39;s; treating\nDovecot as an oracle. After a few rounds of bugfixing, Aerogramme&#39;s\nimplementation of FETCH and SEARCH is now in much better shape.</p>\n<p><strong>The lesson we learned is that the IMAP specification can leave room for\ninterpretation in surprising ways.</strong> In fact, to further illustrate this point,\nlet&#39;s talk about one <code>ImapTest</code> scenario that we haven&#39;t &quot;fixed&quot; yet in Aerogramme\nbecause we just found it very confusing, and we are not sure what to do!</p>\n<h3 id=\"example-the-confusing-case-of-search-and-structured-fields\">Example: the confusing case of <code>SEARCH</code> and structured fields</h3>\n<p>He&#39;s a tricky case. <code>SEARCH FROM &lt;string&gt;</code> returns the list of emails whose <code>From</code>\nheader &quot;contains&quot; the given string. Now, what does &quot;contains&quot; mean here,\nexactly? When running <code>SEARCH FROM foo@example.com</code> on the two following\nheaders, which ones should match?</p>\n<pre><code>From: Foo Bar &lt;foo@example.com&gt;\nFrom: Foo Bar &lt; &quot;foo&quot; (comment) @ example.com&gt;</code></pre>\n<p>Some additional context on email syntax is useful here: these two email addresses are\nequivalent. The local-part of the email (before the <code>@</code>) allows quoted strings,\nso <code>&quot;foo&quot;</code> can be used and simply denotes <code>foo</code>. Email syntax also allows\ncomments in various places; they are written between parentheses. Comments have\nno formal meaning but are shown by email clients and can be useful; they are\nsometimes used by mailing-list software to indicate the name of the list.\nAs an example <a href=\"https://sympa.community\" rel=\"nofollow ugc noopener\">SYMPA</a> emits <code>From</code> headers of the form <code>From: Alice (via Super Friends List) &lt;list-address@server.org&gt;</code>).</p>\n<p>At the moment, Aerogramme implements <code>SEARCH FROM</code> as plain substring search on\nthe text representation of the header: here, the first header matches, but not\nthe second. However, *the ImapTest test suite says that both headers should\nmatch*! So, what does the specification says?</p>\n<p>The <a href=\"https://datatracker.ietf.org/doc/html/rfc3501\" rel=\"nofollow ugc noopener\">IMAP specification</a><a href=\"#imap-search-from\">2</a> for SEARCH says:</p>\n<pre><code>FROM &lt;string&gt;\n   Messages that contain the specified string in the envelope\n   structure&#39;s FROM field.</code></pre>\n<p>Hmm, so, what is this &quot;envelope structure&quot;? Reading further:</p>\n<pre><code>An envelope structure is a parsed representation of the [RFC5322] \nheader of the message. [...] The from, sender, reply-to, to, cc, \nand bcc fields are parenthesized lists of address structures. [...]\nAn address structure is a parenthesized list that describes an \nelectronic mail address. The fields of an address structure are in \nthe following order: display name, [SMTP] at-domain-list [...], \nmailbox name (local-part ABNF production from [RFC5322]), and hostname.</code></pre>\n<p>So the FROM field of an email&#39;s &quot;envelope structure&quot; contains a <em>structured</em> representation of <em>parsed</em> email addresses.\nRegarding our two headers above, they are both represented in the envelope structure as:</p>\n<pre><code>(&quot;Foo Bar&quot; NIL &quot;foo&quot; &quot;example.com&quot;)</code></pre>\n<p>What does it mean for this structured value to &quot;contain&quot; the string\n<code>foo@example.com</code>? Clearly none of the strings in the structure contain\n<code>foo@example.com</code>, so perhaps instead we should re-print the structure as an\nemail address and do a substring search on that? However, *there is not a unique\nway of printing a given email address*, and the IMAP specification does not\ndefine any...</p>\n<p>We are quite curious to know if IMAP experts have more to say on this point!</p>\n<p>In the meantime, our bugfixes for FETCH and SEARCH have been shipped in\n<a href=\"https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.5.1\" rel=\"nofollow ugc noopener\">Aerogramme 0.5.1</a>\n(see the release notes for more details), with the exception of <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/pulls/195\" rel=\"nofollow ugc noopener\">two extra\nfixes</a> shipped in\n<a href=\"https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.6.0\" rel=\"nofollow ugc noopener\">Aerogramme 0.6</a>.</p>\n<h1 id=\"improving-email-parsing-in-aerogramme\">Improving email parsing in Aerogramme</h1>\n<p>FETCH and SEARCH operate on the <em>parsed</em> email ASTs produced by\n<a href=\"https://git.deuxfleurs.fr/deuxfleurs/eml-codec\" rel=\"nofollow ugc noopener\">eml-codec</a>. How do we\nensure that we have correctly implemented all the subtleties of the email format\nin eml-codec, which is itself described in an old and tricky set of\nspecifications? As often, the answer is: more testing.</p>\n<h2 id=\"property-based-testing-for-eml-codec\">Property-Based Testing for eml-codec</h2>\n<p>To ensure our implementation is correct, we performed fuzzer-guided Property-Based Testing (PBT) of the email parser and\nprinter in eml-codec. Specifically, <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/src/commit/a317094811edaadbbd77657c0da05e3e771c1af6/fuzz/fuzz_targets/message_print_parse.rs#L8\" rel=\"nofollow ugc noopener\">we tested the following &quot;roundtrip&quot;\nproperty</a>:</p>\n<blockquote><p>“for an arbitrary email value in eml-codec&#39;s internal AST, printing it then\nparsing the printed output must yield an equivalent AST”</p></blockquote>\n<p>The starting AST is generated by a fuzzer as a structured value using the\n<code>Arbitrary</code> trait; the <a href=\"https://rust-fuzz.github.io/book/cargo-fuzz.html\" rel=\"nofollow ugc noopener\">cargo-fuzz tutorial</a> calls this\n&quot;Structure-Aware Fuzzing&quot;. A roundtrip in the other direction, i.e.\n&quot;parse then print then test for string equality&quot; would not generally hold, as\nthere are many equivalent ways of printing the same email, for instance because\nof line folding...</p>\n<p>While it may seem that any reasonable implementation would satisfy our roundtrip\nproperty, in practice, this methodology immediately surfaced a lot\nof bugs and edge cases.</p>\n<p>The recurring theme was that the fuzzer would generate &quot;exotic&quot; AST values\nbreaking the roundtrip property, for which we had to clarify:</p>\n<ul><li><p>if these revealed an inconsistency/confusion between parser and printer,</p><p>where the value, after printing, could result in invalid syntax or syntax\nthat parsed into a different AST;</p></li><li><p>if these values should in fact be considered invalid; this means</p><p>strengthening the AST invariants and fixing the fuzzer-based generator\naccordingly;</p></li><li><p>or whether the &quot;equivalence checking&quot; function for AST values needed to be</p><p>relaxed (in some cases, syntactically different values represent the &quot;same&quot;\nconceptual value up to implementation details).</p></li></ul>\n<p>In the first case, this fixed bugs or potential security issues for users of the\nparser (like Aerogramme) or printer. In the second case, it improved the\ndefinition of internal AST types, which is relevant when using eml-codec to\nprogramatically compose emails, not something we use in Aerogramme itself, but relevant for an\nexperimental mailing-list server project in Deuxfleurs using the same library.</p>\n<p>To illustrate the kind of issues that we are talking about here, let&#39;s look at\nan tricky example that was found using our fuzzing methodology.</p>\n<h3 id=\"example-encoded-words-shenanigans\">Example: encoded words shenanigans</h3>\n<p>The <a href=\"https://datatracker.ietf.org/doc/html/rfc2047\" rel=\"nofollow ugc noopener\">&quot;MIME Part Three&quot; specification\n(RFC2047)</a> specifies a way of\nusing non-ASCII text in selected places of email headers. (Full support for\nUTF-8 in headers, which eml-codec also supports, was only <a href=\"https://datatracker.ietf.org/doc/html/rfc6532\" rel=\"nofollow ugc noopener\">introduced\nlater</a>.) Where allowed by the\nspecification, ASCII text can be replaced by an &quot;encoded word&quot;: an ASCII\nencoding of non-ASCII text using special syntax introduced by the specification.</p>\n<p>As an example, the UTF-8 word <code>aérogramme</code> can be encoded as follows:</p>\n<pre><code>=?utf-8?q?a=C3=A9rogramme?=</code></pre>\n<p>More generally, a MIME encoded word has the following structure:</p>\n<pre><code>=? &lt;charset&gt; ? &lt;encoding&gt; ? &lt;encoded-text&gt; ?=</code></pre>\n<p>When using the <code>q</code> encoding like above, <em>most</em> ASCII characters can be used\ndirectly in the encoded text, and other bytes must be encoded as <code>=</code> followed by\ntheir hexadecimal code.</p>\n<p>Now, let us consider the following <code>From</code> header:</p>\n<pre><code>From: =?utf-8?q?@[?= X]</code></pre>\n<p>This looks like an encoded word followed by some extra junk; is this a valid\n<code>From</code> header? Perhaps surprisingly, *there is no encoded word in this header,\nand it is a valid email address!* The email address is <code>=?utf-8?q?</code> @ <code>[?= X]</code>\n(it is technically valid!), where the part after the &#39;@&#39; uses the uncommon\n&quot;domain-literal&quot; syntax.</p>\n<p>Now, consider the following <code>Subject</code> header with the same byte representation:</p>\n<pre><code>Subject: =?utf-8?q?@[?= X]</code></pre>\n<p>This time, the first part of the header <em>is an encoded word</em>, and the whole\nheader tells us that the subject is the string <code>@[ X]</code>!</p>\n<p>The explanation for this behavior follows from the specification (which is\n<a href=\"https://datatracker.ietf.org/doc/html/rfc2047#section-5\" rel=\"nofollow ugc noopener\">fairly clear on this\naspect</a>): the set of\nASCII characters that can be used <em>unescaped</em> in <code>&lt;encoded-text&gt;</code> <strong>depends on\nthe context in which the encoded word appears</strong>.</p>\n<p>Encoded words <em>can appear</em> in <code>From</code> headers (for example <code>From: =?utf-8?q?a=C3=A9rogramme?= &lt;aerogramme@deuxfleurs.fr&gt;</code> is valid), but in that\ncontext they cannot use <code>@</code> or <code>[</code> unescaped, which is why the first example\ndoes not in fact contain a valid encoded word. In the context of a <code>Subject</code>\nheader, the set of valid unescaped characters is broader and includes both <code>@</code>\nand <code>[</code>, making <code>=?utf-8?q?@[?=</code> is a valid encoded word representing the string\n<code>@[</code>.</p>\n<p>To implement this behavior, we needed to correctly track the context in which we\nparse encoded words, &quot;tokenize&quot; them according to that context, and also track\ncontext sensitivity in our email AST and during printing. Getting every detail\nto align properly between parsing, our internal AST, and printing took us\nseveral attempts! In that process, our property-testing setup was *extremely\nuseful*, as it could quickly come up with new convoluted examples like the one\nabove that revealed bugs in edge cases of our code.</p>\n<p>The lesson here is that email specifications can be *quite complicated and\ntricky to implement*, even when they are clear! And, in our experience, without\nautomatic test generation (like our fuzzer setup), it is very hard to manually\ncome up with examples that actually cover edge cases...</p>\n<p>If you want to see more details, the bulk of our PBT/fuzzing work on eml-codec\nwas done in <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/releases/tag/0.3\" rel=\"nofollow ugc noopener\">eml-codec\n0.3</a> and\nshipped in <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.4.0\" rel=\"nofollow ugc noopener\">Aerogramme\n0.4</a>, with\nsome <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/pulls/84\" rel=\"nofollow ugc noopener\">additional\nimprovements</a> shipped\nin <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.6.0\" rel=\"nofollow ugc noopener\">Aerogramme\n0.6</a>.</p>\n<h2 id=\"testing-eml-codec-on-real-world-emails\">Testing eml-codec on real-world emails</h2>\n<p>We tested eml-codec on collections of real-world emails (more than 100k emails)\nto evaluate and improve the <em>recovery strategies</em> of eml-codec&#39;s parser on\ninvalid or broken syntax.</p>\n<p>Many legitimate emails found in the real world are, indeed, incorrect with\nrespect to <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/#rfc-and-iana-references\" rel=\"nofollow ugc noopener\">email\nspecifications</a>.\nOften, the use of invalid or broken syntax is local (to specific headers, or\nparts of a header); in some cases, it is &quot;only&quot; a minor deviation from the\nspecification.</p>\n<h3 id=\"example-the-many-shapes-of-message-ids\">Example: the many shapes of message IDs</h3>\n<p>The case of &quot;message IDs&quot; can be taken as an example. Emails can be given an\nidentifier (specified using the <code>Message-ID</code> header) so that later emails can\nreference it (using the <code>In-Reply-To</code> and <code>References</code> headers). This is useful\nto display email &quot;threads&quot; in email clients, for example. The message ID syntax\nis also used to identify attachments with the <code>Content-ID</code> header.</p>\n<p>Reading the\n<a href=\"https://datatracker.ietf.org/doc/html/rfc5322#section-3.6.4\" rel=\"nofollow ugc noopener\">specification</a>, a\nmessage ID is of the form:</p>\n<pre><code>&lt;foo.bar@baz.com&gt;</code></pre>\n<p>and a list of message IDs as used by <code>In-Reply-To</code> and <code>References</code> separates message IDs with whitespace:</p>\n<pre><code>&lt;msg1@foo.com&gt; &lt;msg2@bar.eu&gt; &lt;msg3@baz.fr&gt;</code></pre>\n<p>The specification also documents that, for the list syntax, &quot;obsolete&quot; syntax\n(that we must support) can include extra text surrounding message IDs...</p>\n<p>Now, what do we find in our sample of real-world emails?</p>\n<pre><code>Content-ID: &lt;1855BC2C-077C-406B-AEA4-CAF088755676&gt;</code></pre>\n<p>-&gt; Emitted by apple-mail, and <em>invalid</em>: no <code>@</code>!</p>\n<pre><code>Content-ID: text-body\nMessage-ID: foo@bar.com</code></pre>\n<p>-&gt; <em>Invalid</em>: no angle brackets <code>&lt;</code>/<code>&gt;</code>!</p>\n<pre><code>In-Reply-To: &lt;3DE2736D.F4FCC064@orcaware.com&gt;; from redacted@orcaware.com on Mon, Nov 25, 2002 at 11:01:01AM -0800\nIn-Reply-To: Your message of Thu, 18 Mar 1993 22:28:19 GMT.\\n             &lt;8280.9303182228@damsay.dcs.ed.ac.uk&gt;</code></pre>\n<p>-&gt; <em>Valid</em>: an instance of the &quot;obsolete&quot; syntax documented by the specification.</p>\n<pre><code>References: &lt;abc@def&gt;,&lt;foo\\n\\tbar@outlook.com&gt;,&lt;baz@outlook.com&gt;</code></pre>\n<p>-&gt; Commas are valid as part of the obsolete syntax, but the second message-id is malformed because of incorrect line folding (<code>\\n\\t</code>) in the middle of a word.</p>\n<h3 id=\"engineering-eml-codec-for-real-world-emails\">Engineering eml-codec for real-world emails</h3>\n<p>The consequence is that eml-codec needs to be able to *recover from\nbroken syntax*: on an email containing invalid syntax, it should be able to\ndiscard the broken parts and parse as much as it can from the rest of the email,\ninstead of simply returning an error. It should also ideally be\nable to <em>parse invalid but common deviations from the specifications</em> in order\nto recover information instead of discarding them.</p>\n<p>We first extended eml-codec with coarse-grained recovery strategies, such as\ndiscarding an entire header field if we couldn&#39;t parse it. This allowed us to\nquickly reach a state where the eml-codec parser is a <em>total function</em>: for any\ninput bytes, it always returns an email AST representing an RFC-compliant\nemail<a href=\"#email-ast-compliant\">3</a>, discarding any part of the input it does not\nunderstand.</p>\n<p>We then instrumented the parser to <em>log each time it discards broken input</em> when\nrecovering, and ran the instrumented parser on the email that we collected. This\ngave us a lot of examples of legitimate emails with broken syntax. In each case,\nthen, we manually looked at the piece of broken syntax, see if we could make\nsome sense of it, and decide whether:</p>\n<ol><li>we could reasonably extend our parser to parse it;</li><li><p>we could discard it more selectively (e.g. only discard a broken element in a</p><p> list instead of discarding the entire list);</p></li><li>our existing discarding strategy was the best we could do.</li></ol>\n<p>This whole process was particularly interesting because it made us face the many\nsubtleties of real-world emails (sometimes far from the &quot;truth&quot; of\nspecifications); eml-codec is now much more robust operating on real-world emails!</p>\n<p>This methodology involves a lot of\ntradeoffs and judgment calls: there is a limit to the amount of parsing hacks\nthat we can add in terms of code quality but also parsing ambiguity; and some\nclasses of emails are more critical than others (e.g. we should not spend too\nmuch effort supporting spam emails). A strong design constraint of\neml-codec is that, up to a few exceptions, we want its internal AST to only\nrepresent RFC-compliant emails, so we did not want to pollute it to include\nrandom broken syntax just for the sake of &quot;recovering more&quot;. The whole process,\nin particular, helped us clarify the\n<a href=\"https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/src/branch/main/doc/DESIGN.md\" rel=\"nofollow ugc noopener\">design</a>\nof eml-codec as a library.</p>\n<p>For more details, you can look at the release notes of <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/releases/tag/0.3.1\" rel=\"nofollow ugc noopener\">eml-codec\n0.3.1</a> where\nthe bulk of the work is done, building on <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/eml-codec/releases/tag/0.2\" rel=\"nofollow ugc noopener\">eml-codec\n0.2</a> for the\ninitial setup of parsing recovery. Both shipped with <a href=\"https://git.deuxfleurs.fr/Deuxfleurs/aerogramme/releases/tag/0.4.0\" rel=\"nofollow ugc noopener\">Aerogramme\n0.4</a>.</p>\n<hr />\n<p>IMAP&#39;s search and retrieval features are essential because they allow clients to\nhave a snappy UX while handling mailboxes with thousands of emails. This post\nfocused on getting those basic features right. But, more broadly, we think that\nthe &quot;mailbox as database&quot; perspective is useful because it raises the question:\nwhich end-user workflows can we enable and support? Which features should we\nprioritize or optimize to best support the workflows of day-to-day email users?</p>\n<p>*Stay tuned for the next blogpost in the series where we discuss the other big\nchallenge for an IMAP server: mailbox concurrency!*</p>\n<hr />\n<p>1</p>\n<p>Following the database analogy, the logical next step could be to optimize this by first &quot;pre-compiling&quot; queries before running them on emails. Right now we don&#39;t know if this optimization would actually matter in practice...</p>\n<p>2</p>\n<p>This links to IMAP4rev1 but the more recent IMAP4rev2 isn&#39;t more specific on this subject</p>\n<p>3</p>\n<p>The current eml-codec AST has a few selected exceptions to this rule, where it allows representing non-compliant data in well identified cases. One of such cases is non-compliant message IDs, such as message IDs without <code>@</code>...</p>","headings":[{"level":1,"text":"Quality IMAP, Part 1: Your Mailbox Is A Database","id":"quality-imap-part-1-your-mailbox-is-a-database"},{"level":1,"text":"Your mailbox is a database","id":"your-mailbox-is-a-database"},{"level":1,"text":"Email querying in Aerogramme","id":"email-querying-in-aerogramme"},{"level":1,"text":"Testing Aerogramme's FETCH and SEARCH query interpreter","id":"testing-aerogramme-s-fetch-and-search-query-interpreter"},{"level":3,"text":"Example: the confusing case of SEARCH and structured fields","id":"example-the-confusing-case-of-search-and-structured-fields"},{"level":1,"text":"Improving email parsing in Aerogramme","id":"improving-email-parsing-in-aerogramme"},{"level":2,"text":"Property-Based Testing for eml-codec","id":"property-based-testing-for-eml-codec"},{"level":3,"text":"Example: encoded words shenanigans","id":"example-encoded-words-shenanigans"},{"level":2,"text":"Testing eml-codec on real-world emails","id":"testing-eml-codec-on-real-world-emails"},{"level":3,"text":"Example: the many shapes of message IDs","id":"example-the-many-shapes-of-message-ids"},{"level":3,"text":"Engineering eml-codec for real-world emails","id":"engineering-eml-codec-for-real-world-emails"}]}}