[PATCH] Summary by thread in rmail

[PATCH] Summary by thread in rmail

[Andrea Monaco]

I had some code ready.  This only looks at the Subject field.  You can
invoke it with rmail-thread-summary and it creates a buffer called
e.g. RMAIL-thread-summary that is independent of RMAIL-summary.  There's
still no code to update the summary after getting new mail.  It's basic,
but it works.


Let me know,

Andrea Monaco



diff --git a/lisp/mail/rmailthread.el b/lisp/mail/rmailthread.el
new file mode 100644
index 0000000000..a06d0ab144
--- /dev/null
+++ b/lisp/mail/rmailthread.el
@@ -0,0 +1,147 @@
+
+(defvar rmail-thread-summary-buffer nil)
+(put 'rmail-thread-summary-buffer 'permanent-local t)
+
+
+
+
+(defun rmail-get-create-thread-summary-buffer ()
+  "Return the Rmail thread summary buffer.
+If necessary, it is created and undo is disabled."
+  (if (and rmail-thread-summary-buffer (buffer-name rmail-thread-summary-buffer))
+      rmail-thread-summary-buffer
+    (let ((buff (generate-new-buffer (concat (buffer-name) "-thread-summary"))))
+      (with-current-buffer buff
+	(setq buffer-undo-list t))
+      buff)))
+
+
+
+(defun rmail-new-thread-summary (desc redo function &rest args)
+  "Create a summary of selected messages by thread."
+  (message "Computing thread summary lines...")
+  (unless rmail-buffer
+    (error "No RMAIL buffer found"))
+  (let (mesg was-in-summary sumbuf)
+    (if (derived-mode-p 'rmail-summary-mode)
+	(setq was-in-summary t))
+    (with-current-buffer rmail-buffer
+      (setq rmail-thread-summary-buffer (rmail-new-thread-summary-1 desc redo function args)
+	    ;; r-s-b is buffer-local.
+	    sumbuf rmail-thread-summary-buffer
+	    mesg rmail-current-message))
+    ;; Now display the summary buffer and go to the right place in it.
+    (unless was-in-summary
+      (if (and (one-window-p)
+	       pop-up-windows
+	       (not pop-up-frames))
+	  ;; If there is just one window, put the summary on the top.
+	  (progn
+	    (split-window (selected-window) rmail-summary-window-size)
+	    (select-window (next-window (frame-first-window)))
+	    (rmail-pop-to-buffer sumbuf)
+	    ;; If pop-to-buffer did not use that window, delete that
+	    ;; window.  (This can happen if it uses another frame.)
+	    (if (not (eq sumbuf (window-buffer (frame-first-window))))
+		(delete-other-windows)))
+	(rmail-pop-to-buffer sumbuf))
+      (set-buffer rmail-buffer))
+      ;; This is how rmail makes the summary buffer reappear.
+      ;; We do this here to make the window the proper size.
+      ;(rmail-select-summary nil)
+					;(set-buffer sumbuf))
+    (switch-to-buffer sumbuf)
+    ;(rmail-summary-goto-msg mesg t t)
+    ;(rmail-summary-construct-io-menu)
+    (message "Computing thread summary lines... done")))
+
+
+
+(defun rmail-new-thread-summary-1 (description redo function args)
+  (let ((summary-msgs ())
+	(rmail-new-thread-summary-line-count 0)
+	ordered-threads
+	(threadbuf (rmail-get-create-thread-summary-buffer)))
+    ;; Scan the messages, getting their summary strings
+    ;; and putting the list of them in SUMMARY-MSGS.
+    (let* ((msgnum 1)
+	   (main-buffer (current-buffer))
+	   (total rmail-total-messages)
+	   (rmail-thread-hash-table (make-hash-table :test 'equal :size 1024))
+	   (inhibit-read-only t))
+      (save-excursion
+	;; Go where the mbox text is.
+	(if (rmail-buffers-swapped-p)
+	    (set-buffer rmail-view-buffer))
+	(let ((old-min (point-min-marker))
+	      (old-max (point-max-marker)))
+	  (unwind-protect
+	      ;; Can't use save-restriction here; that doesn't work if we
+	      ;; plan to modify text outside the original restriction.
+	      (save-excursion
+		(widen)
+		(goto-char (point-min))
+		(while (>= total msgnum)
+		  (with-current-buffer main-buffer
+		    ;; First test whether to include this message.
+		    (if (or (null function)
+			    (apply function msgnum args))
+			(let* ((subject (rmail-simplified-subject msgnum))
+			       (cell (gethash subject rmail-thread-hash-table))
+			       (th cell)
+			       thread)
+			  (while (and (not thread) th)
+			    (if (equal (caar th) subject)
+				(setq thread (car th)))
+			    (setq th (cdr th)))
+			  (if thread
+			      (setcdr thread
+				      (cons (cons msgnum (rmail-get-summary msgnum)) (cdr thread)))
+			    (progn
+			      (let* ((newthread (list subject (cons msgnum (rmail-get-summary msgnum))))
+				     (newcell (cons newthread cell)))
+				(setq cell newcell)
+				(puthash subject newcell rmail-thread-hash-table)
+				(setq ordered-threads (cons newthread ordered-threads)))))
+			  (setq msgnum (1+ msgnum))
+			  (if (and (not (zerop msgnum))
+				   (zerop (% msgnum 10)))
+			      (message "Computing thread summary lines... %d"
+				       msgnum))))))
+		(setq ordered-threads (nreverse ordered-threads))))
+	  (narrow-to-region old-min old-max))))
+    (setq rmail-thread-summary-buffer nil)
+    (save-excursion
+      (let ((rbuf (current-buffer))
+	    (total rmail-total-messages))
+	(set-buffer threadbuf)
+	;; Set up the summary buffer's contents.
+	(let ((buffer-read-only nil))
+	  (erase-buffer)
+	  (while ordered-threads
+	    (let ((thread-message (cdar ordered-threads)))
+	      (setq thread-message (nreverse thread-message))
+	      (princ (cdar thread-message) threadbuf)
+	      (setq thread-message (cdr thread-message))
+	      (while thread-message
+		(let* ((suml (cdar thread-message))
+		       (newsuml (concat (substring suml 0 42) "  " (substring suml 42))))
+		  (princ newsuml threadbuf))
+		(setq thread-message (cdr thread-message))))
+	    (setq ordered-threads (cdr ordered-threads)))
+	  (goto-char (point-min)))
+	;; Set up the rest of its state and local variables.
+	(setq buffer-read-only t)
+	(rmail-summary-mode)
+	(setq-local minor-mode-alist (list (list t (concat ": " description))))
+	(setq rmail-buffer rbuf
+	      rmail-summary-redo redo
+	      rmail-total-messages total)))
+    threadbuf))
+
+
+
+(defun rmail-thread-summary ()
+  "Display a summary of all messages by thread, one line per message."
+  (interactive)
+  (rmail-new-thread-summary "All" '(rmail-thread-summary) nil))

Re: [PATCH] Summary by thread in rmail

[Eli Zaretskii]

> From: Andrea Monaco <andrea.monaco@autistici.org>
> Date: Wed, 05 Oct 2022 23:57:49 +0200
> 
> I had some code ready.  This only looks at the Subject field.  You can
> invoke it with rmail-thread-summary and it creates a buffer called
> e.g. RMAIL-thread-summary that is independent of RMAIL-summary.  There's
> still no code to update the summary after getting new mail.  It's basic,
> but it works.

Thanks.  However, I wonder: why would we need two commands that
produce a summary by Subject?  IOW, what is the use case for this new
command that the existing C-M-t doesn't support?

Re: [PATCH] Summary by thread in rmail

[Andrea Monaco]

  > Great, but you are aware of Emacs Gnus?

Yes, but I prefer rmail, because I find the interface clearer.


  > IOW, what is the use case for this new command that the existing
  > C-M-t doesn't support?

That seems obvious to me.  C-M-t only shows a single thread, while my
patch shows all mail this way.  This is useful to me, and is a common
feature among mail clients.  I think Gnome Evolution shows mail by
thread by default.



Andrea Monaco

Re: [PATCH] Summary by thread in rmail

[tomas]

[-- Attachment #1: Type: text/plain, Size: 718 bytes --]

On Thu, Oct 06, 2022 at 09:21:23AM +0200, Andrea Monaco wrote:
> 
>   > Great, but you are aware of Emacs Gnus?
> 
> Yes, but I prefer rmail, because I find the interface clearer.
> 
> 
>   > IOW, what is the use case for this new command that the existing
>   > C-M-t doesn't support?
> 
> That seems obvious to me.  C-M-t only shows a single thread, while my
> patch shows all mail this way.  This is useful to me, and is a common
> feature among mail clients.  I think Gnome Evolution shows mail by
> thread by default.

Still a pity that it guesses its threads by Subject: instead of using
In-Reply-To: and References:

In this way not better than the Microsoft "products" :-(

Cheers
-- 
t

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 195 bytes --]

Re: [PATCH] Summary by thread in rmail

[Emanuel Berg]

tomas wrote:

> Still a pity that it guesses its threads by Subject: instead
> of using In-Reply-To: and References:

Yes, but one would be clear that and nothing else is what
happens ...

-- 
underground experts united
https://dataswamp.org/~incal

Re: [PATCH] Summary by thread in rmail

[Eli Zaretskii]

> From: Andrea Monaco <andrea.monaco@autistici.org>
> Cc: emacs-devel@gnu.org
> Date: Thu, 06 Oct 2022 09:21:23 +0200
> 
>   > IOW, what is the use case for this new command that the existing
>   > C-M-t doesn't support?
> 
> That seems obvious to me.  C-M-t only shows a single thread, while my
> patch shows all mail this way.

Ah, please forgive me my misunderstanding.

I will review your patch soon.

Also, your patch is large enough to require copyright assignment.  I
see you have several assignments on file, but none of them for Emacs.
Would you like to start your legal paperwork at this time, so that we
could accept your contribution now and in the future?

Re: [PATCH] Summary by thread in rmail

[Andrea Monaco]

  > Still a pity that it guesses its threads by Subject: instead of
  > using In-Reply-To: and References:

I think recognizing threads based on the Subject field is correct in
most cases.  Anyway, that is a possible enhancement.


  > Would you like to start your legal paperwork at this time, so that
  > we could accept your contribution now and in the future?

Thanks.  Could you please send me the paperwork off-list?



Andrea Monaco

Re: [PATCH] Summary by thread in rmail

[Eli Zaretskii]

> From: Andrea Monaco <andrea.monaco@autistici.org>
> Cc: incal@dataswamp.org, emacs-devel@gnu.org
> Date: Thu, 06 Oct 2022 12:55:14 +0200
> 
>   > Would you like to start your legal paperwork at this time, so that
>   > we could accept your contribution now and in the future?
> 
> Thanks.  Could you please send me the paperwork off-list?

Form sent off-list.

Re: [PATCH] Summary by thread in rmail

[Emanuel Berg]

Andrea Monaco wrote:

>> Still a pity that it guesses its threads by Subject:
>> instead of using In-Reply-To: and References:
>
> I think recognizing threads based on the Subject field is
> correct in most cases. Anyway, that is
> a possible enhancement.

There are problems associated with it as we have seen even in
this thread (sorry :P) ...

So it is obvious the discussion can go both ways ...

But if you find a good name for it - maybe use the word
"subject" in the command is enough - and also say something to
this end in the docstring that it isn't the other method that
some people maybe would expect otherwise ... 

-- 
underground experts united
https://dataswamp.org/~incal

Re: [PATCH] Summary by thread in rmail

[Emanuel Berg]

Andrea Monaco wrote:

>> Still a pity that it guesses its threads by Subject:
>> instead of using In-Reply-To: and References:
>
> I think recognizing threads based on the Subject field is
> correct in most cases. Anyway, that is
> a possible enhancement.

Can you implement this in a generic way maybe so then you'd
just have the header or list of headers supplied as arguments?

And you'd set up interface functions for the most common
choices :)

-- 
underground experts united
https://dataswamp.org/~incal

Re: [PATCH] Summary by thread in rmail

[Eli Zaretskii]

> From: Andrea Monaco <andrea.monaco@autistici.org>
> Date: Wed, 05 Oct 2022 23:57:49 +0200
> 
> I had some code ready.  This only looks at the Subject field.  You can
> invoke it with rmail-thread-summary and it creates a buffer called
> e.g. RMAIL-thread-summary that is independent of RMAIL-summary.  There's
> still no code to update the summary after getting new mail.  It's basic,
> but it works.

Thanks.  Please see some comments below.

Richard, I'd appreciate your review as well.

> --- /dev/null
> +++ b/lisp/mail/rmailthread.el

Please add this to rmailsum.el, instead of making a new file.

> +(defun rmail-get-create-thread-summary-buffer ()
> +  "Return the Rmail thread summary buffer.
> +If necessary, it is created and undo is disabled."
> +  (if (and rmail-thread-summary-buffer (buffer-name rmail-thread-summary-buffer))
                                          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

We nowadays have the buffer-live-p function to make such tests.

> +    (let ((buff (generate-new-buffer (concat (buffer-name) "-thread-summary"))))

I think "-summary-by-thread" is a better name.  "Thread-summary" hints
that it is a summary of a single thread, which is not the case here.

> +(defun rmail-new-thread-summary (desc redo function &rest args)
> +  "Create a summary of selected messages by thread."

The "selected" part here is misleading, I think.  The truth is, the
messages can be "selected" by the FUNCTION argument, but what kind of
FUNCTION can make sense for this summary?  And in any case, if we keep
the FUNCTION arg, the doc string should explain how messages are
"selected" for the summary.

> +    (with-current-buffer rmail-buffer
> +      (setq rmail-thread-summary-buffer (rmail-new-thread-summary-1 desc redo function args)
> +	    ;; r-s-b is buffer-local.

What is "r-s-b" here?  Please don't use abbreviated symbol names, they
make reading the code harder.

> +      ;; This is how rmail makes the summary buffer reappear.
> +      ;; We do this here to make the window the proper size.
> +      ;(rmail-select-summary nil)
> +					;(set-buffer sumbuf))

Is this commented-out code necessary?

> +    ;(rmail-summary-goto-msg mesg t t)
> +    ;(rmail-summary-construct-io-menu)

And this?

> +			  (if thread
> +			      (setcdr thread
> +				      (cons (cons msgnum (rmail-get-summary msgnum)) (cdr thread)))
> +			    (progn
> +			      (let* ((newthread (list subject (cons msgnum (rmail-get-summary msgnum))))
> +				     (newcell (cons newthread cell)))
> +				(setq cell newcell)
> +				(puthash subject newcell rmail-thread-hash-table)
> +				(setq ordered-threads (cons newthread ordered-threads)))))

Is progn really necessary here?

> +				(setq ordered-threads (cons newthread ordered-threads)))))

Maybe using 'push' here will make the code more concise and readable?

> +			  (setq msgnum (1+ msgnum))
> +			  (if (and (not (zerop msgnum))
> +				   (zerop (% msgnum 10)))
> +			      (message "Computing thread summary lines... %d"
> +				       msgnum))))))

"Computing by-thread summary lines... %d" is a better message, I
think.

> +	      (while thread-message
> +		(let* ((suml (cdar thread-message))
> +		       (newsuml (concat (substring suml 0 42) "  " (substring suml 42))))

Why are you truncating the subject at the 42nd character? and why is
42 hard-coded?

This:

> +	(setq-local minor-mode-alist (list (list t (concat ": " description))))

together with this:

> +  (rmail-new-thread-summary "All" '(rmail-thread-summary) nil))

Will AFAIU display "RMAIL Summary: All" in the mode line.  However, I
think the mode line should in this case show something like this
instead:

  RMAIL Summary: By-Thread

Thanks again for working on this.

[PATCH] Add command rmail-summary-by-thread (was: Summary by thread in rmail)

[Andrea Monaco]

This patch adds a new command rmail-summary-by-thread.  It shows a
summary of all messages that are in the same thread as a given message,
defaulting to current message.

Admittedly it's a bit complex but it works like a charm (in my tests).

First it fills rmail-summary-message-ids-hash-table, that is a hash
table linking Message-Ids with rmail message indices.

Then it fills rmail-summary-subjects-hash-table, that links simplified
Subject fields with the index of the first message having that subject.
(Yeah, I'm totally in love with hash tables!)

Then it uses those to fill rmail-summary-message-parents-vector, a
vector holding the "parents" of each message, that is the messages
referenced in the References and In-reply-to fields of that message,
plus the first message with the same subject.

With all this information, building the thread is just a matter of
walking the graph recursively, traversing parents and descendants of
each message and ticking their index in a local vector.


Andrea Monaco



diff --git a/lisp/mail/rmailsum.el b/lisp/mail/rmailsum.el
index 0144a34e5e..3e3207e974 100644
--- a/lisp/mail/rmailsum.el
+++ b/lisp/mail/rmailsum.el
@@ -67,6 +67,18 @@ rmail-summary-currently-displayed-msgs
 by `rmail-summary-fill-displayed-messages'.")
 (put 'rmail-summary-currently-displayed-msgs 'permanent-local t)
 
+(defvar rmail-summary-message-ids-hash-table nil
+  "Hash table linking Message IDs of messages with their indices.")
+
+(defvar rmail-summary-subjects-hash-table nil
+  "Hash table linking subjects with the index of the first message with that subject.")
+
+(defvar rmail-summary-message-parents-vector nil
+  "Vector that holds a list of indices of parents for each message.
+Message A is parent to message B if the id of A appear in the
+References or In-reply-to fields of B, or if A is the first
+message with the same subject as B.  First element is ignored.")
+
 (defvar rmail-summary-font-lock-keywords
   '(("^ *[0-9]+D.*" . font-lock-string-face)			; Deleted.
     ("^ *[0-9]+-.*" . font-lock-type-face)			; Unread.
@@ -297,6 +309,47 @@ rmail-summary-fill-displayed-messages
 	      ?y)
 	(forward-line 1)))))
 
+(defun rmail-summary-fill-message-ids-hash-table ()
+  "Fill `rmail-summary-message-ids-hash-table'."
+  (with-current-buffer rmail-buffer
+    (setq rmail-summary-message-ids-hash-table (make-hash-table :test 'equal :size 1024))
+    (let ((msgnum 1))
+      (while (<= msgnum rmail-total-messages)
+	(let ((id (rmail-get-header "Message-ID" msgnum)))
+	  (puthash id (cons (cons id msgnum) (gethash id rmail-summary-message-ids-hash-table))
+		   rmail-summary-message-ids-hash-table))
+	(setq msgnum (1+ msgnum))))))
+
+(defun rmail-summary--split-header-field (name &optional msgnum)
+  (let ((header (rmail-get-header name msgnum)))
+    (if header
+	(split-string header "[ \f\t\n\r\v,;]+"))))
+
+(defun rmail-summary-fill-message-parents-vector ()
+  "Fill `rmail-summary-message-parents-vector'."
+  (with-current-buffer rmail-buffer
+    (rmail-summary-fill-message-ids-hash-table)
+    (setq rmail-summary-subjects-hash-table (make-hash-table :test 'equal :size 1024))
+    (setq rmail-summary-message-parents-vector (make-vector (1+ rmail-total-messages) nil))
+    (let ((msgnum 1))
+      (while (<= msgnum rmail-total-messages)
+	(let* ((parents nil)
+	       (subject (rmail-simplified-subject msgnum))
+	       (subj-cell (gethash subject rmail-summary-subjects-hash-table))
+	       (subj-par (assoc subject subj-cell))
+	       (refs (rmail-summary--split-header-field "References" msgnum))
+	       (reply-to (rmail-summary--split-header-field "In-reply-to" msgnum)))
+	  (if subj-par
+	      (setq parents (cons (cdr subj-par) parents))
+	    (puthash subject (cons (cons subject msgnum) subj-cell)
+		     rmail-summary-subjects-hash-table))
+	  (dolist (id (append refs reply-to))
+	    (let ((ent (assoc id (gethash id rmail-summary-message-ids-hash-table))))
+	      (if ent
+		  (setq parents (cons (cdr ent) parents)))))
+	  (aset rmail-summary-message-parents-vector msgnum parents)
+	  (setq msgnum (1+ msgnum)))))))
+
 (defun rmail-summary-negate ()
   "Toggle display of messages that match the summary and those which do not."
   (interactive)
@@ -318,6 +371,57 @@ rmail-summary
   (interactive)
   (rmail-new-summary "All" '(rmail-summary) nil))
 
+(defun rmail-summary-direct-descendants (msgnum encountered-msgs)
+  "Find all direct descendants of MSGNUM.
+Assumes `rmail-summary-message-parents-vector' is filled.  Ignores messages
+already ticked in ENCOUNTERED-MSGS."
+  (let (desc
+	(msg 1))
+    (while (<= msg rmail-total-messages)
+      (when (and
+	     (eq nil (aref encountered-msgs msg))
+	     (memq msgnum (aref rmail-summary-message-parents-vector msg)))
+	(setq desc (cons msg desc)))
+      (setq msg (1+ msg)))
+    desc))
+
+(defun rmail-summary--walk-thread-message-recursively (msgnum encountered-msgs)
+  "Walk message MSGNUM by ticking parents and descendants in ENCOUNTERED-MSGS recursively."
+  (unless (eq (aref encountered-msgs msgnum) t)
+    (aset encountered-msgs msgnum t)
+    (let ((walk-thread-msg (lambda (msg) (rmail-summary--walk-thread-message-recursively msg encountered-msgs))))
+      (mapcar walk-thread-msg (aref rmail-summary-message-parents-vector msgnum))
+      (mapcar walk-thread-msg (rmail-summary-direct-descendants msgnum encountered-msgs)))))
+
+;;;###autoload
+(defun rmail-summary-by-thread (&optional msgnum)
+  "Display a summary of messages in the same thread as MSGNUM, or current message.
+Threads are based on the Subject, References and In-reply-to
+fields."
+  (interactive
+   (let* ((msg rmail-current-message)
+	  (prompt (concat "Show thread containing message number")))
+     (list (read-number prompt msg))))
+  (with-current-buffer rmail-buffer
+    (unless msgnum
+      (setq msgnum rmail-current-message))
+    (unless (and rmail-summary-message-parents-vector
+		 (= (length rmail-summary-message-parents-vector)
+		    (1+ rmail-total-messages)))
+      (rmail-summary-fill-message-parents-vector))
+    (let ((enc-msgs (make-bool-vector (1+ rmail-total-messages) nil)))
+      (rmail-summary--walk-thread-message-recursively msgnum enc-msgs)
+      (rmail-new-summary (format "thread containing message %d" msgnum)
+			 (list 'rmail-summary-by-thread msgnum)
+			 (if (and rmail-summary-intersect-consecutive-filters
+				  (rmail-summary--exists-1))
+			     (lambda (msg msgnum)
+			       (and (eq (aref rmail-summary-currently-displayed-msgs msg)
+					t)
+				    (eq (aref enc-msgs msg) t)))
+			   (lambda (msg msgnum) (eq (aref enc-msgs msg) t)))
+			 msgnum))))
+
 ;;;###autoload
 (defun rmail-summary-by-labels (labels)
   "Display a summary of all messages with one or more LABELS.

Re: [PATCH] Add command rmail-summary-by-thread (was: Summary by thread in rmail)

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

This is a feature people have asked for.  Thank you for implementing it.

-- 
Dr Richard Stallman (https://stallman.org)
Chief GNUisance of the GNU Project (https://gnu.org)
Founder, Free Software Foundation (https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

Re: [PATCH] Add command rmail-summary-by-thread (was: Summary by thread in rmail)

[Eli Zaretskii]

> From: Andrea Monaco <andrea.monaco@autistici.org>
> Cc: rms@gnu.org, emacs-devel@gnu.org
> Date: Tue, 15 Nov 2022 20:07:18 +0100
> 
> 
> This patch adds a new command rmail-summary-by-thread.  It shows a
> summary of all messages that are in the same thread as a given message,
> defaulting to current message.

Thanks, installed.

[PATCH] Make rmail-summary-by-thread faster

[Andrea Monaco]

I found the first implementation of rmail-summary-by-thread a bit slow.
There's an optimization that escaped me at first: generate another
vector called rmail-summary-message-descendants-vector that holds the
direct descendants of each message, that is the symmetric relation to
rmail-summary-message-parents-vector.  Now it is much faster.


Andrea Monaco



diff --git a/lisp/mail/rmailsum.el b/lisp/mail/rmailsum.el
index b30c32aaffd..9d9c6d16988 100644
--- a/lisp/mail/rmailsum.el
+++ b/lisp/mail/rmailsum.el
@@ -84,6 +84,11 @@ rmail-summary-message-parents-vector
 References or In-reply-to fields of B, or if A is the first
 message with the same subject as B.  First element is ignored.")
 
+(defvar rmail-summary-message-descendants-vector nil
+  "Vector that holds the direct descendants of each message.
+This is the symmetric relation to `rmail-summary-message-parents-vector'.
+  First element is ignored.")
+
 (defvar rmail-summary-font-lock-keywords
   '(("^ *[0-9]+D.*" . font-lock-string-face)			; Deleted.
     ("^ *[0-9]+-.*" . font-lock-type-face)			; Unread.
@@ -331,14 +336,16 @@ rmail-summary--split-header-field
     (if header
 	(split-string header "[ \f\t\n\r\v,;]+"))))
 
-(defun rmail-summary-fill-message-parents-vector ()
-  "Fill `rmail-summary-message-parents-vector'."
+(defun rmail-summary-fill-message-parents-and-descs-vectors ()
+  "Fill `rmail-summary-message-parents-vector' and `rmail-summary-message-descendants-vector'."
   (with-current-buffer rmail-buffer
     (rmail-summary-fill-message-ids-hash-table)
     (setq rmail-summary-subjects-hash-table
           (make-hash-table :test 'equal :size 1024))
     (setq rmail-summary-message-parents-vector
           (make-vector (1+ rmail-total-messages) nil))
+    (setq rmail-summary-message-descendants-vector
+          (make-vector (1+ rmail-total-messages) nil))
     (let ((msgnum 1))
       (while (<= msgnum rmail-total-messages)
 	(let* ((parents nil)
@@ -346,18 +353,23 @@ rmail-summary-fill-message-parents-vector
 	       (subj-cell (gethash subject rmail-summary-subjects-hash-table))
 	       (subj-par (assoc subject subj-cell))
 	       (refs (rmail-summary--split-header-field "References" msgnum))
-	       (reply-to (rmail-summary--split-header-field "In-reply-to"
+	       (reply-tos (rmail-summary--split-header-field "In-reply-to"
                                                             msgnum)))
 	  (if subj-par
-	      (setq parents (cons (cdr subj-par) parents))
+	      (progn
+		(setq parents (cons (cdr subj-par) nil))
+		(aset rmail-summary-message-descendants-vector (cdr subj-par)
+		      (cons msgnum (aref rmail-summary-message-descendants-vector (cdr subj-par)))))
 	    (puthash subject (cons (cons subject msgnum) subj-cell)
 		     rmail-summary-subjects-hash-table))
-	  (dolist (id (append refs reply-to))
+	  (dolist (id (append refs reply-tos))
 	    (let ((ent
                    (assoc id
                           (gethash id rmail-summary-message-ids-hash-table))))
-	      (if ent
-		  (setq parents (cons (cdr ent) parents)))))
+	      (when ent
+		(setq parents (cons (cdr ent) parents))
+		(aset rmail-summary-message-descendants-vector (cdr ent)
+		      (cons msgnum (aref rmail-summary-message-descendants-vector (cdr ent)))))))
 	  (aset rmail-summary-message-parents-vector msgnum parents)
 	  (setq msgnum (1+ msgnum)))))))
 
@@ -387,20 +399,6 @@ rmail-summary
   (interactive)
   (rmail-new-summary "All" '(rmail-summary) nil))
 
-(defun rmail-summary-direct-descendants (msgnum encountered-msgs)
-  "Find all direct descendants of MSGNUM, ignoring ENCOUNTERED-MSGS.
-Assumes `rmail-summary-message-parents-vector' is filled.  Ignores messages
-already ticked in ENCOUNTERED-MSGS."
-  (let (desc
-	(msg 1))
-    (while (<= msg rmail-total-messages)
-      (when (and
-	     (not (aref encountered-msgs msg))
-	     (memq msgnum (aref rmail-summary-message-parents-vector msg)))
-	(setq desc (cons msg desc)))
-      (setq msg (1+ msg)))
-    desc))
-
 (defun rmail-summary--walk-thread-message-recursively (msgnum encountered-msgs)
   "Add parents and descendants of message MSGNUM to ENCOUNTERED-MSGS, recursively."
   (unless (aref encountered-msgs msgnum)
@@ -412,7 +410,7 @@ rmail-summary--walk-thread-message-recursively
       (mapc walk-thread-msg
             (aref rmail-summary-message-parents-vector msgnum))
       (mapc walk-thread-msg
-            (rmail-summary-direct-descendants msgnum encountered-msgs)))))
+            (aref rmail-summary-message-descendants-vector msgnum)))))
 
 ;;;###autoload
 (defun rmail-summary-by-thread (&optional msgnum)
@@ -430,7 +428,7 @@ rmail-summary-by-thread
     (unless (and rmail-summary-message-parents-vector
 		 (= (length rmail-summary-message-parents-vector)
 		    (1+ rmail-total-messages)))
-      (rmail-summary-fill-message-parents-vector))
+      (rmail-summary-fill-message-parents-and-descs-vectors))
     (let ((enc-msgs (make-bool-vector (1+ rmail-total-messages) nil)))
       (rmail-summary--walk-thread-message-recursively msgnum enc-msgs)
       (rmail-new-summary (format "thread containing message %d" msgnum)

Re: [PATCH] Make rmail-summary-by-thread faster

[Eli Zaretskii]

> From: Andrea Monaco <andrea.monaco@autistici.org>
> Cc: rms@gnu.org, emacs-devel@gnu.org
> Date: Fri, 09 Dec 2022 21:22:22 +0100
> 
> 
> I found the first implementation of rmail-summary-by-thread a bit slow.
> There's an optimization that escaped me at first: generate another
> vector called rmail-summary-message-descendants-vector that holds the
> direct descendants of each message, that is the symmetric relation to
> rmail-summary-message-parents-vector.  Now it is much faster.

Thanks, I installed this on the emacs-29 branch.

P.S. You consistently post patches without commit log messages, which
requires me to add the log when installing the changes.  Please make a
habit of accompanying the patches with the appropriate commit log
messages, formatted according to our conventions, as described in the
file CONTRIBUTE that you can find in the Emacs source tree.  TIA.