Index v2 📜

[flatcap]

This is a breakdown of how the Index works, what problems it has and what we need to do to fix it.

Everyone's invited to ask questions and make suggestions.
I really need as many people as possible to understand the problem with me.

---

Introduction

NeoMutt's code has changed a LOT since its split from Mutt.
We've refactored to create APIs and libraries to reduce the dependencies and the complexity of the code.
One stubborn area is the Index.

The Index displays a list of Emails contained in a Mailbox.
The Index can sort this list by $sort, etc.
When new mail arrives, the backend, e.g. Maildir, needs to update this list.

Maildir is the worst offender.
It sorts the Emails so that when it scans the directories it can work out if any files are new.
If it finds some new files, it creates new Emails and adds them to the list.
Then, it tries to restore the Index's sorting order.
If that sounds terrifying, then you're beginning to understand.

The backends can change the order of the Email list and the Index has to deal with it.
Not only that, the user doesn't want to see the focus jump around -- sound familiar?

Data

There are sets of data to consider: mail data and gui data.

We've made some big advances in separating the gui data out of the mail objects, but some still remains.
The plan is that we would have a shadow set of View objects, e.g.

• Email - data about the email: headers, etc
• EmailView - display data, such as its colour

Mail Data

The mail data is rooted at the NeoMutt object.

NeoMutt holds a list of Accounts, each of which holds a list of Mailboxs, which hold a list of Emails.

GUI Data

The gui data is rooted at the RootWindow object.

The screen is divided into a nested hierarchy of MuttWindows.
Each window can have some data associated with it.

Here are the windows that make up the Index Dialog:

This shows the names of the components and some of the data associated with them.

• Index Dialog - IndexSharedData
  • Sidebar
  • Container
    • Index Panel - IndexPrivateData
      • Index
      • Index Status Bar
    • Pager Panel
      • Pager
      • Pager Status Bar

Index Shared Data

The IndexSharedData is available to all of the associated windows.
For example, the Index has a selected Email in a particular Mailbox in an Account.
The Sidebar uses this information to highlight the current Mailbox.

struct IndexSharedData
{
  struct ConfigSubset *sub;         ///< Config set to use
  struct MailboxView *mailboxview;  ///< Current Mailbox view
  struct Account *account;          ///< Current Account
  struct Mailbox *mailbox;          ///< Current Mailbox
  struct Email *email;              ///< Currently selected Email
  size_t email_seq;                 ///< Sequence number of the current email
  struct Notify *notify;            ///< Notifications: #NotifyIndex, #IndexSharedData
};

There is one circumstance where there is more than one Index: attaching an Email from Compose.

This new Index Dialog has its own data and is independent of the original one.
e.g. Applying a limit won't affect the original Index.

Index Private Data

Much of the data required to work the Index is local to mutt_index_menu().
Some state data is required by other Index functions and that is stored in IndexPrivateData.

struct IndexPrivateData
{
  bool tag;                      ///< tag-prefix has been pressed
  int  oldcount;                 ///< Old count of Emails in the Mailbox
  int  newcount;                 ///< New count of Emails in the Mailbox
  bool do_mailbox_notify;        ///< Do we need to notify the user of new mail?
  bool attach_msg;               ///< Are we in "attach message" mode?

  struct IndexSharedData *shared; ///< Shared Index data
  struct Menu *menu;              ///< Menu controlling the index
  struct MuttWindow *win_index;   ///< Window for the Index
};

[flatcap]

The Actual Index Data

Above, you see who's holding all the data.
Now let's see the important bits:

• struct MailboxView - Display data for the Mailbox
  Contains: limit info, threads
• struct Mailbox - Folder of emails
  Contains: Emails, paths, message counts
• struct ThreadsContext - Threaded tree of Emails
  Contains: threads, hash table of message-ids, sort info
• struct MuttThread - Part of an email conversation
  Contains: Email, parent, child
• struct Email - An email
  Contains: envelope, body, tags

Opening the Mailbox

First, the user opens a mailbox.

First, the backend creates a struct Mailbox and a struct Email for each email.
The array Mailbox.emails contains pointers to each Email.
Its order depends on $sort, etc.

In this mailbox, there are 22 emails, 'a' to 'v' and the array has a few empty entries at the end.

Enabling threading

Next, the user enables threading: set sort=threads

The Index creates a struct ThreadsContext.
This holds a tree of struct MuttThread objects, each of which points to an Email.
The layout of the tree depends on the message-ids in the emails and config option $strict_threads.

This mailbox has two email threads, rooted at 'b' and 'o' and three individual emails, 'a', 'n' and 'v'.

Limiting to one thread

Next, the user does <limit-current-thread> on the 'b' thread.
Then, then collapse one of the sub-threads at email 'd'.

In the Mailbox, the array v2r ('virtual' to 'real') holds a list of visible emails.
Its order depends on $sort, etc.
After the limit, only the green emails are still visible.

Menu view

The Menu is an abstract view of some data, usually emails.
In the Index, the Menu is backed by the v2r array.

In this case, the window for the Menu is only five lines high, so only emails 'd', 'g', 'h', 'i' and 'j' are visible.

Note: The index numbers are the indexes in the emails array.

[flatcap]

@sassmann @vuori @navi-desu @rayfordshire @whitney-cumber @auouymous

You all seem keen to help improve NeoMutt (Thanks!), and the Index is the next step.
I'd like your input.

Above, is the current layout of the Index -- where the data is, who owns it, etc.
Please have a read and ask questions.

[vuori]

So I thought about the v2r stuff and moving display-related fields out of Email. From a memory-management perspective, the problem is the lifecycle and ownership of Email objects: we don't want them to get freed or moved around due to a mailbox updating its contents (looking at you, Maildir) while v2r or a hypothetical EmailView object is pointing at them.

I suggested a hash table on IRC to replace the current emails array, but I think there's a more lightweight solution: make the emails array append-only while the mailbox is open. If an updater (like maildir_mbox_check) sees new mails, it adds them to the end. If something has changed, it can update an existing Email. If a file is removed, set an internal flag that indicates that this Email is gone. When update is done, notify whoever is responsible for v2r that they should update it so that limit/sort is applied to the new emails content and gone-flagged mails are hidden.

This makes indexes to emails stay valid as long as the mailbox is open, which is a superset of the functinality that currently exists (indexes point to valid memory, but not necessarily to the expected Email). Deleting a huge amount of mails from a huge mailbox seems relatively uncommon, so the extra memory use of not discarding Email objects immediately probably won't be huge. Maybe sync-mailbox could also do the garbage collection if needed.

[navi-desu]

Maybe sync-mailbox could also do the garbage collection if needed.

If we do the removal at sync-mailbox, the case of wasted memory will only happens if the emails got deleted from outside neomutt (or is there any other case emails get deleted from inside neomutt aside from mark-to-delete + sync-mailbox?)

I suggested a hash table on IRC to replace the current emails array, but I think there's a more lightweight solution: make the emails array append-only while the mailbox is open.

How much heavier would it be? There's already a few <something> -> Email* HashTables in the Mailbox, and the table seems like a bit of a nicer solution than making sure the array is not modified while a mailbox is open...

Altho since (I think) we would index into the struct Email emails**, making emails[X] = NULL when deleting an email, and checking for null every time something wants to get an email, could work too and not need to keep track of to-be-deleted memory

[vuori]

Dunno about the performance, if the hash table implementation is good there's probably not a huge difference. Since there were questions about date parsing performance the other day these parts may be pretty speed-sensitive though.

NULLing on delete would effectively require a free at that point, which would invalidate any direct pointers to the Email. That's fine if an Email is always fetched by going through the array, but some previous Asan issues I debugged were due to what's effectively an ioloop yield point caused by progress callbacks, where references being held in "safe" code were not entirely safe. To guard against these kinds of async-concurrency issues without much effort, keeping a flagged version of Email around until a suitable GC moment arrives seems like a passable solution. (Alternatively, a refcount system could be introduced where necessary.)

[navi-desu]

I'm not sure what "ioloop yield point caused by progress callbacks" means but yeah, NULLing only works if either the array is the only entry point, or there's some kind of refcount.

[vuori]

If you think about Python or Javascript await statements, these yield control to the ioloop which will then maybe run other tasks before eventually returning to the awaiting function. Those tasks can change program state, almost as if you were using threads.

Neomutt doesn't have a formal ioloop, but the view-redraw machinery effectively acts like one: when you yield control to that machinery (like progress_update calls ultimately do), various pending actions can run. For example mailbox stats checking, which can touch the emails array that you were in the middle of updating when you called progress_update.

[flatcap]

This ugly diagram shows the main objects and their members.
The ones shown in red are GUI-specific and should be in objects on the left-hand-side.

Mailbox Parts

• emails[] - A simple array of Email*
  The backends routinely alter this array, sorting it, adding to it, removing from it.

• v2r[] - Array of ints that index entries in emails[]
  This gives us the flexibility to show subsets of the Email list

• ThreadsContext - A tree of MuttThread
  This maps the threaded tree layout to the emails.
  It's independent of emails[] and v2r.

• Hash Tables - Four lookup tables for efficient searching

  • Mailbox: "message-id" -> Email
  • Mailbox: "subject" -> Email
  • Mailbox: "x-labels" -> Email
  • ThreadsContext: "message-id" -> MuttThread

Frontend Events

What do we need to be able to do?

• Cold setup - Mailbox is opened for the first time.
  We want to setup v2r from empty.
  This will depend on $sort, etc.

• User alters $sort, etc
  emails will be re-ordered.
  v2r will be reconstructed to match emails

• User applies a <limit>
  Flag non-matching emails in v2r
  Remove the non-matching emails
  Squash down v2r

• User applies collapses a thread
  Lookup the current email in the ThreadsContext
  Recursively remove each of its children from v2r
  Squash down v2r

• User removes a ''
  Reconstruct v2r from emails

• User removes uncollapses a thread
  Lookup the current email in the ThreadsContext
  Recursively insert each of its children into v2r

Backend Events

The external events can be broken down into:

• New emails arrive
• Emails are deleted
• Mailbox is synchronised

New Mail

The frontend typically calls mx_mbox_check() to check for new mail.

This is the simple case.
The backend creates new Emails and adds them to the end of emails (resizing it if necessary).
If there's new mail, it causes the Index to be resorted.

Unfortunately, after the Emails are added, the backend "helpfully" resorts the array.

Deleted Mail

This gets a bit trickier.
The backend will delete the Email, then squash down the emails array.
The Index is notified after the changes have happened.
It needs to be sure it's not going to use any deleted emails and the v2r is
now out of date, so must be reconstructed.

Synchronise Mailbox

In theory, this should be a combination of new mails arriving and old emails
being deleted. In practice, anything could change and the Index tries to
keep the same focussed email, etc.

Problems

What are the problems?

The Index is given too little information, too late.
The emails array can change without warning, and Emails can appear or disappear.

The v2r is tightly bound to emails.
Almost everything the backend does, means it needs to get rebuilt.

The ThreadsContext is entirely separate.
Any new Emails need inserting into the tree and any deleted Emails removing.

Ideal Behaviour

The Index's data is separate and independent of the backend's data.

The Index is notified of changes with a list of emails.

• After new emails arrive or emails are changed.
• Before emails are deleted.

Changes to the Index shouldn't affect:

• The current selection (unless it's deleted)
• Contents or position of the Pager (unless it's deleted)
• The state of collapsed threads

[vuori]

Does sorting need to change emails? Isn't reordering v2r enough, with the backing Email objects referenced as sort keys?

[flatcap]

No it doesn't, but there's never been a push to separate data from view.

[flatcap]

Just a placeholder while I think...

[flatcap]

#3845 - Refactor MxOps->msg_open() to eliminate msgno

A big step towards moving msgno out of Email and into EmailView.

[flatcap]

I've pushed my work branch to [flatcap/views].
It doesn't do anything yet, but it has NeoMuttView, AccountView and EmailView placeholders.

I'm currently looking at some problem config usage:

imap/command.c:897:36:    $mail_check_recent
imap/imap.c:959:32:       $sort
imap/imap.c:969:7:        $sort
imap/imap.c:999:5:        $sort
imap/imap.c:1660:32:      $sort
imap/imap.c:1669:7:       $sort
imap/imap.c:1686:5:       $sort
imap/message.c:1807:33:   $delete_untag

maildir/maildir.c:100:36: $mail_check_recent
maildir/mh.c:198:36:      $mail_check_recent
maildir/mh.c:673:32:      $sort

mbox/mbox.c:558:32:       $sort
mbox/mbox.c:561:5:        $sort
mbox/mbox.c:563:5:        $sort
mbox/mbox.c:868:36:       $mail_check_recent
mbox/mbox.c:1189:32:      $sort
mbox/mbox.c:1190:39:      $use_threads
mbox/mbox.c:1193:5:       $sort
mbox/mbox.c:1194:5:       $use_threads
mbox/mbox.c:1196:5:       $sort
mbox/mbox.c:1197:5:       $use_threads
mbox/mbox.c:1818:38:      $mail_check_recent

nntp/newsrc.c:309:32:     $sort
nntp/newsrc.c:312:5:      $sort
nntp/newsrc.c:380:5:      $sort

[flatcap]

**** me! It works!
It compiles and some basic operations, using Maildir, don't crash.

In branch [flatcap/views] I've managed to move Mailbox->v2r and ->vcount into MailboxView.

The branch is a mess of overlapping changes, but the important points are:

Big Changes

• Change v2r from an int array (indexing into Mailbox->emails[]) into an Email array.
  This breaks the direct dependency on the Mailbox.

• Change v2r from Email array into an EmailView array.
  The EmailView is just a shell for now holding an Email*.
  The EmailViews are created and destroyed frequently for simplicity.
  Eventually, they'll have the same lifetime as the Emails.

• Track down all uses of v2r and vcount which hold the sorted list of Emails.
  Every user of v2r or vcount needs to be either eliminated, or changed to use MailboxView.
  Every function that needs access to v2r or vcount needs to be passed a MailboxView.

Problems

• There are two problem functions: nm_tags_commit() and mutt_set_flag().
  They call mutt_set_header_color() which calls mutt_pattern_exec() which needs access to the MailboxView.
  Somehow, these functions need cause the colours to be reset without doing it themselves.

• The pattern functions are very complicated.
  Many of the patterns are applied to an Email, so we pass in an Email.
  Some of them apply to Mailboxes.
  Patterns like ~m which match message numbers will need the MailboxView.
  These patterns need splitting up along domain lines. Somehow.

Other Changes

• Sorting the Mailbox now works on MailboxView->v2r only.
  This is independent of the backends' Mailbox->emails[] array.

• Add NeoMuttView (placeholder for now)
  The NeoMuttView is the GUI complement to NeoMutt.
  It's empty for now, but will possibly hold all the GUI globals.

• Add AccountView (placeholder for now)
  The AccountView is the GUI complement to Account.
  It's empty for now, but will possibly hold the cached MailboxViews.

MailboxViews

When the MailboxView and EmailView hold all the Mailbox's and Email's GUI data, then some new features become possible.

• Caching the GUI attributes of a mailbox.
  If you switch between multiple mailboxes, the cursor position and the state of the folded threads, in each, could be remembered.

• When attaching an email, from the Compose screen, the Index's view could be cloned from the original.
  This would start identical to the Index, but be independent of it.

[flatcap]

I've merged a ton of non-functional changes that passed MailboxView parameters to functions.
I've also stripped out the NeoMuttView, AccountView and sorting -- we don't need them yet.

This leaves four much-simpler commits:

• 7ffebd4 create EmailView
• a0ce296 mailbox: convert v2r to an array of Emails
• 47e84df mailbox: convert v2r to an array of EmailViews
• 8c94d73 MailboxView: move v2r,vcount out of Mailbox

36 files changed, 295 insertions(+), 197 deletions(-)

[flatcap]

Work is ongoing...

#3877 imap: factor out tagged emails
This changes the IMAP backend to take an array of Emails to work on, rather than using Email.tagged.
(it shouldn't know about tagging, which is a front-end thing)

[flatcap]

Meanwhile, I realised something about struct Mailbox.
There are lots of members that should be in MailboxView instead.

When updating Mailbox.emails[], the backends update members like:
(there are probably more)

int msg_deleted; ///< Number of deleted messages
int msg_flagged; ///< Number of flagged messages
int msg_new;     ///< Number of new messages
int msg_unread;  ///< Number of unread messages

These fields only matter to the user, so it should be the front-end's responsibility to own and update them.