threading: implement on-the-fly message threading

implement message threading on the message store level using the
jwz algorithm. Build threads on-the-fly when new message headers arrive.

Use the references header to create the threads and the in-reply-to
header as a fall-back option in case no references header is present.

Does not run when the worker provides its own threading (e.g. imap
server threads).

Include only those message headers that have been fetched and are
stored in the message store.

References: https://www.jwz.org/doc/threading.html
Signed-off-by: Koni Marti <koni.marti@gmail.com>
Tested-by: Inwit <inwit@sindominio.net>
Tested-by: akspecs <akspecs@gmail.com>
Acked-by: Robin Jarry <robin@jarry.cc>

10 files changed, 440 insertions, 4 deletions

diff --git a/commands/msg/toggle-threads.go b/commands/msg/toggle-threads.go
new file mode 100644
index 00000000..e93cb425
--- /dev/null
+++ b/commands/msg/toggle-threads.go
@@ -0,0 +1,39 @@
+package msg
+
+import (
+	"errors"
+
+	"git.sr.ht/~rjarry/aerc/widgets"
+)
+
+type ToggleThreads struct{}
+
+func init() {
+	register(ToggleThreads{})
+}
+
+func (ToggleThreads) Aliases() []string {
+	return []string{"toggle-threads"}
+}
+
+func (ToggleThreads) Complete(aerc *widgets.Aerc, args []string) []string {
+	return nil
+}
+
+func (ToggleThreads) Execute(aerc *widgets.Aerc, args []string) error {
+	if len(args) != 1 {
+		return errors.New("Usage: toggle-threads")
+	}
+	h := newHelper(aerc)
+	acct, err := h.account()
+	if err != nil {
+		return err
+	}
+	store, err := h.store()
+	if err != nil {
+		return err
+	}
+	store.SetBuildThreads(!store.BuildThreads())
+	acct.Messages().Invalidate()
+	return nil
+}
diff --git a/config/binds.conf b/config/binds.conf
index 7d8d32f9..ee58bb33 100644
--- a/config/binds.conf
+++ b/config/binds.conf
@@ -30,6 +30,8 @@ L = :expand-folder<Enter>
 v = :mark -t<Enter>
 V = :mark -v<Enter>
 
+T = :toggle-threads<Enter>
+
 <Enter> = :view<Enter>
 d = :prompt 'Really delete this message?' 'delete-message'<Enter>
 D = :delete<Enter>
diff --git a/doc/aerc.1.scd b/doc/aerc.1.scd
index 8b7be82c..648bde69 100644
--- a/doc/aerc.1.scd
+++ b/doc/aerc.1.scd
@@ -310,6 +310,9 @@ message list, the message in the message viewer, etc).
 |  to
 :- Addresses in the "to" field
 
+*toggle-threads*
+	Toggles between message threading and the normal message list.
+
 *view*
 	Opens the message viewer to display the selected message.
 
diff --git a/go.mod b/go.mod
index 954e7840..4be2d836 100644
--- a/go.mod
+++ b/go.mod
@@ -16,6 +16,7 @@ require (
 	github.com/emersion/go-sasl v0.0.0-20211008083017-0b9dcfb154ac
 	github.com/emersion/go-smtp v0.15.0
 	github.com/fsnotify/fsnotify v1.5.1
+	github.com/gatherstars-com/jwz v1.3.0 // indirect
 	github.com/gdamore/tcell/v2 v2.4.0
 	github.com/go-ini/ini v1.63.2
 	github.com/golang/protobuf v1.5.2 // indirect
diff --git a/go.sum b/go.sum
index c1f3d6e5..b828719f 100644
--- a/go.sum
+++ b/go.sum
@@ -43,6 +43,7 @@ github.com/ProtonMail/go-crypto v0.0.0-20211221144345-a4f6767435ab/go.mod h1:z4/
 github.com/brunnre8/go.notmuch v0.0.0-20201126061756-caa2daf7093c h1:dh58QrW3/S/aCnQPFoeRRE9zMauKooDFd5zh1dLtxXs=
 github.com/brunnre8/go.notmuch v0.0.0-20201126061756-caa2daf7093c/go.mod h1:zJtFvR3NinVdmBiLyB4MyXKmqyVfZEb2cK97ISfTgV8=
 github.com/census-instrumentation/opencensus-proto v0.2.1/go.mod h1:f6KPmirojxKA12rnyqOA5BBL4O983OfeGPqjHWSTneU=
+github.com/cention-sany/utf7 v0.0.0-20170124080048-26cad61bd60a/go.mod h1:2GxOXOlEPAMFPfp014mK1SWq8G8BN8o7/dfYqJrVGn8=
 github.com/chzyer/logex v1.1.10/go.mod h1:+Ywpsq7O8HXn0nuIou7OrIPyXbp3wmkHB+jjWRnGsAI=
 github.com/chzyer/readline v0.0.0-20180603132655-2972be24d48e/go.mod h1:nSuG5e5PlCu98SY8svDHJxuZscDgtXS6KTTbou5AhLI=
 github.com/chzyer/test v0.0.0-20180213035817-a1ea475d72b1/go.mod h1:Q3SI9o4m/ZMnBNeIyt5eFwwo7qiLfzFZmjNmxjkiQlU=
@@ -84,8 +85,11 @@ github.com/envoyproxy/go-control-plane v0.9.4/go.mod h1:6rpuAdCZL397s3pYoYcLgu1m
 github.com/envoyproxy/protoc-gen-validate v0.1.0/go.mod h1:iSmxcyjqTsJpI2R4NaDN7+kN2VEUnK/pcBlmesArF7c=
 github.com/fsnotify/fsnotify v1.5.1 h1:mZcQUHVQUQWoPXXtuf9yuEXKudkV2sx1E06UadKWpgI=
 github.com/fsnotify/fsnotify v1.5.1/go.mod h1:T3375wBYaZdLLcVNkcVbzGHY7f1l/uK5T5Ai1i3InKU=
+github.com/gatherstars-com/jwz v1.3.0 h1:+lVRjWDsLupLL3tJneimJ7VRBCZ6x59R2OW9zB8Wvb4=
+github.com/gatherstars-com/jwz v1.3.0/go.mod h1:FkR8I1cfoVwXI+EAZsWfHIBi4duECJZ3A5teFPxmJnI=
 github.com/gdamore/encoding v1.0.0 h1:+7OoQ1Bc6eTm5niUzBa0Ctsh6JbMW6Ra+YNuAtDBdko=
 github.com/gdamore/encoding v1.0.0/go.mod h1:alR0ol34c49FCSBLjhosxzcPHQbf2trDkoo5dl+VrEg=
+github.com/gdamore/tcell/v2 v2.3.3/go.mod h1:cTTuF84Dlj/RqmaCIV5p4w8uG1zWdk0SF6oBpwHp4fU=
 github.com/gdamore/tcell/v2 v2.4.0 h1:W6dxJEmaxYvhICFoTY3WrLLEXsQ11SaFnKGVEXW57KM=
 github.com/gdamore/tcell/v2 v2.4.0/go.mod h1:cTTuF84Dlj/RqmaCIV5p4w8uG1zWdk0SF6oBpwHp4fU=
 github.com/go-gl/glfw v0.0.0-20190409004039-e6da0acd62b1/go.mod h1:vR7hzQXu2zJy9AVAgeJqvqgH9Q5CA+iKCZ2gyEVpxRU=
@@ -93,6 +97,8 @@ github.com/go-gl/glfw/v3.3/glfw v0.0.0-20191125211704-12ad95a8df72/go.mod h1:tQ2
 github.com/go-gl/glfw/v3.3/glfw v0.0.0-20200222043503-6f7a984d4dc4/go.mod h1:tQ2UAYgL5IevRw8kRxooKSPJfGvJ9fJQFa0TUsXzTg8=
 github.com/go-ini/ini v1.63.2 h1:kwN3umicd2HF3Tgvap4um1ZG52/WyKT9GGdPx0CJk6Y=
 github.com/go-ini/ini v1.63.2/go.mod h1:ByCAeIL28uOIIG0E3PJtZPDL8WnHpFKFOtgjp+3Ies8=
+github.com/go-test/deep v1.0.7/go.mod h1:QV8Hv/iy04NyLBxAdO9njL0iVPN1S4d/A3NVv1V36o8=
+github.com/gogs/chardet v0.0.0-20191104214054-4b6791f73a28/go.mod h1:Pcatq5tYkCW2Q6yrR2VRHlbHpZ/R4/7qyL1TCF7vl14=
 github.com/golang/glog v0.0.0-20160126235308-23def4e6c14b/go.mod h1:SBH7ygxi8pfUlaOkMMuAQtPIUF8ecWP5IEl/CR7VP2Q=
 github.com/golang/groupcache v0.0.0-20190702054246-869f871628b6/go.mod h1:cIg4eruTrX1D+g88fzRXU5OdNfaM+9IcxsU14FzY7Hc=
 github.com/golang/groupcache v0.0.0-20191227052852-215e87163ea7/go.mod h1:cIg4eruTrX1D+g88fzRXU5OdNfaM+9IcxsU14FzY7Hc=
@@ -150,6 +156,8 @@ github.com/hashicorp/golang-lru v0.5.1/go.mod h1:/m3WP610KZHVQ1SGc6re/UDhFvYD7pJ
 github.com/ianlancetaylor/demangle v0.0.0-20181102032728-5e5cf60278f6/go.mod h1:aSSvb/t6k1mPoxDqO4vJh6VOCGPwU4O0C2/Eqndh1Sc=
 github.com/imdario/mergo v0.3.12 h1:b6R2BslTbIEToALKP7LxUvijTsNI9TAe80pLWN2g/HU=
 github.com/imdario/mergo v0.3.12/go.mod h1:jmQim1M+e3UYxmgPu/WyfjB3N3VflVyUjjjwH0dnCYA=
+github.com/jaytaylor/html2text v0.0.0-20200412013138-3577fbdbcff7/go.mod h1:CVKlgaMiht+LXvHG173ujK6JUhZXKb2u/BQtjPDIvyk=
+github.com/jhillyerd/enmime v0.9.1/go.mod h1:S5ge4lnv/dDDBbAWwtoOFlj14NHiXdw/EqMB2lJz3b8=
 github.com/jstemmer/go-junit-report v0.0.0-20190106144839-af01ea7f8024/go.mod h1:6v2b51hI/fHJwM22ozAgKL4VKDeJcHhJFhtBdhmNjmU=
 github.com/jstemmer/go-junit-report v0.9.1/go.mod h1:Brl9GWCQeLvo8nXZwPNNblvFj/XSXhF0NWZEnDohbsk=
 github.com/kisielk/gotool v1.0.0/go.mod h1:XhKaO+MFFWcvkIS/tQcRk01m1F5IRFswLeQ+oQHNcck=
@@ -169,24 +177,29 @@ github.com/mattn/go-isatty v0.0.14/go.mod h1:7GGIvUiUoEMVVmxf/4nioHXj79iQHKdU27k
 github.com/mattn/go-pointer v0.0.0-20180825124634-49522c3f3791/go.mod h1:2zXcozF6qYGgmsG+SeTZz3oAbFLdD3OWqnUbNvJZAlc=
 github.com/mattn/go-pointer v0.0.1 h1:n+XhsuGeVO6MEAp7xyEukFINEa+Quek5psIR/ylA6o0=
 github.com/mattn/go-pointer v0.0.1/go.mod h1:2zXcozF6qYGgmsG+SeTZz3oAbFLdD3OWqnUbNvJZAlc=
+github.com/mattn/go-runewidth v0.0.9/go.mod h1:H031xJmbD/WCDINGzjvQ9THkh0rPKHF+m2gUSrubnMI=
 github.com/mattn/go-runewidth v0.0.10/go.mod h1:RAqKPSqVFrSLVXbA8x7dzmKdmGzieGRCM46jaSJTDAk=
+github.com/mattn/go-runewidth v0.0.12/go.mod h1:RAqKPSqVFrSLVXbA8x7dzmKdmGzieGRCM46jaSJTDAk=
 github.com/mattn/go-runewidth v0.0.13 h1:lTGmDsbAYt5DmK6OnoV7EuIF1wEIFAcxld6ypU4OSgU=
 github.com/mattn/go-runewidth v0.0.13/go.mod h1:Jdepj2loyihRzMpdS35Xk/zdY8IAYHsh153qUoGf23w=
 github.com/miolini/datacounter v1.0.2 h1:mGTL0vqEAtH7mwNJS1JIpd6jwTAP6cBQQ2P8apaCIm8=
 github.com/miolini/datacounter v1.0.2/go.mod h1:C45dc2hBumHjDpEU64IqPwR6TDyPVpzOqqRTN7zmBUA=
 github.com/mitchellh/go-homedir v1.1.0 h1:lukF9ziXFxDFPkA1vsr5zpc1XuPDn/wFntq5mG+4E0Y=
 github.com/mitchellh/go-homedir v1.1.0/go.mod h1:SfyaCUpYCn1Vlf4IUYiD9fPX4A5wJrkLzIz1N1q0pr0=
+github.com/olekukonko/tablewriter v0.0.5/go.mod h1:hPp6KlRPjbx+hW8ykQs1w3UBbZlj6HuIJcUGPhkA7kY=
 github.com/pkg/errors v0.9.1 h1:FEBLx1zS214owpjy7qsBeixbURkuhQAwrK5UwLGTwt4=
 github.com/pkg/errors v0.9.1/go.mod h1:bwawxfHBFNV+L2hUp1rHADufV3IMtnDRdf1r5NINEl0=
 github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
 github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
 github.com/prometheus/client_model v0.0.0-20190812154241-14fe0d1b01d4/go.mod h1:xMI15A0UPsDsEKsMN9yxemIoYk6Tm2C1GtYGdfGttqA=
+github.com/rivo/tview v0.0.0-20210624165335-29d673af0ce2/go.mod h1:IxQujbYMAh4trWr0Dwa8jfciForjVmxyHpskZX6aydQ=
 github.com/rivo/uniseg v0.1.0/go.mod h1:J6wj4VEh+S6ZtnVlnTBMWIodfgj8LQOQFoIToxlJtxc=
 github.com/rivo/uniseg v0.2.0 h1:S1pD9weZBuJdFmowNwbpi7BJ8TNftyUImj/0WQi72jY=
 github.com/rivo/uniseg v0.2.0/go.mod h1:J6wj4VEh+S6ZtnVlnTBMWIodfgj8LQOQFoIToxlJtxc=
 github.com/riywo/loginshell v0.0.0-20200815045211-7d26008be1ab h1:ZjX6I48eZSFetPb41dHudEyVr5v953N15TsNZXlkcWY=
 github.com/riywo/loginshell v0.0.0-20200815045211-7d26008be1ab/go.mod h1:/PfPXh0EntGc3QAAyUaviy4S9tzy4Zp0e2ilq4voC6E=
 github.com/rogpeppe/go-internal v1.3.0/go.mod h1:M8bDsm7K2OlrFYOpmOWEs/qY81heoFRclV5y23lUDJ4=
+github.com/ssor/bom v0.0.0-20170718123548-6386211fdfcf/go.mod h1:RJID2RhlZKId02nZ62WenDCkgHFerpIOmW0iT7GKmXM=
 github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
 github.com/stretchr/testify v1.3.0/go.mod h1:M5WIy9Dh21IEIfnGCwXGc5bZfKNJtfHm1UVUgZn+9EI=
 github.com/stretchr/testify v1.4.0 h1:2E4SXV/wtOkTonXsotYi4li6zVWxYlZuYNCXe9XRJyk=
@@ -258,6 +271,7 @@ golang.org/x/net v0.0.0-20200520182314-0ba52f642ac2/go.mod h1:qpuaurCH72eLCgpAm/
 golang.org/x/net v0.0.0-20200625001655-4c5254603344/go.mod h1:/O7V0waA8r7cgGh81Ro3o1hOxt32SMVPicZroKQ2sZA=
 golang.org/x/net v0.0.0-20200707034311-ab3426394381/go.mod h1:/O7V0waA8r7cgGh81Ro3o1hOxt32SMVPicZroKQ2sZA=
 golang.org/x/net v0.0.0-20200822124328-c89045814202/go.mod h1:/O7V0waA8r7cgGh81Ro3o1hOxt32SMVPicZroKQ2sZA=
+golang.org/x/net v0.0.0-20210501142056-aec3718b3fa0/go.mod h1:OJAsFXCWl8Ukc7SiCT/9KSuxbyM7479/AVlXFRxuMCk=
 golang.org/x/net v0.0.0-20211029224645-99673261e6eb h1:pirldcYWx7rx7kE5r+9WsOXPXK0+WH5+uZ7uPmJ44uM=
 golang.org/x/net v0.0.0-20211029224645-99673261e6eb/go.mod h1:9nx3DQGgdP8bBQD5qxJ1jj9UTztislL4KSBs9R2vV5Y=
 golang.org/x/oauth2 v0.0.0-20180821212333-d2e6202438be/go.mod h1:N/0e6XlmueqKjAGxoOufVs8QHGRruUQn6yWY3a++T0U=
@@ -301,6 +315,7 @@ golang.org/x/sys v0.0.0-20200515095857-1151b9dac4a9/go.mod h1:h1NjWce9XRLGQEsW7w
 golang.org/x/sys v0.0.0-20200523222454-059865788121/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20200803210538-64077c9b5642/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20201119102817-f84b799fce68/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
+golang.org/x/sys v0.0.0-20210309074719-68d13333faf2/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20210423082822-04245dca01da/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/sys v0.0.0-20210615035016-665e8c7367d1/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/sys v0.0.0-20210630005230-0f9fa26af87c/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
@@ -308,6 +323,7 @@ golang.org/x/sys v0.0.0-20211030160813-b3129d9d1021 h1:giLT+HuUP/gXYrG2Plg9WTjj4
 golang.org/x/sys v0.0.0-20211030160813-b3129d9d1021/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
 golang.org/x/term v0.0.0-20201126162022-7de9c90e9dd1/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
 golang.org/x/term v0.0.0-20201210144234-2321bbc49cbf/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
+golang.org/x/term v0.0.0-20210220032956-6a3ed077a48d/go.mod h1:bj7SfCRtBDWHUb9snDiAeCFNEtKQo2Wmx5Cou7ajbmo=
 golang.org/x/term v0.0.0-20210927222741-03fcf44c2211 h1:JGgROgKl9N8DuW20oFS5gxc+lE67/N3FcwmBPMe7ArY=
 golang.org/x/term v0.0.0-20210927222741-03fcf44c2211/go.mod h1:jbD1KX2456YbFQfuXm/mYQcufACuNUgVhRMnK/tPxf8=
 golang.org/x/text v0.0.0-20170915032832-14c0d48ead0c/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
@@ -315,6 +331,7 @@ golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
 golang.org/x/text v0.3.1-0.20180807135948-17ff2d5776d2/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
 golang.org/x/text v0.3.2/go.mod h1:bEr9sfX3Q8Zfm5fL9x+3itogRgK3+ptLWKqgva+5dAk=
 golang.org/x/text v0.3.3/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
+golang.org/x/text v0.3.5/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
 golang.org/x/text v0.3.6/go.mod h1:5Zoc/QRtKVWzQhOtBMvqHzDpF6irO9z98xDceosuGiQ=
 golang.org/x/text v0.3.7 h1:olpwvP2KacW1ZWvsR7uQhoyTYvKAupfQrRGBFM352Gk=
 golang.org/x/text v0.3.7/go.mod h1:u+2+/6zg+i71rQMx5EYifcz6MCKuco9NR6JIITiCfzQ=
diff --git a/lib/msgstore.go b/lib/msgstore.go
index 051a7d2c..369f4b45 100644
--- a/lib/msgstore.go
+++ b/lib/msgstore.go
@@ -2,6 +2,7 @@ package lib
 
 import (
 	"io"
+	gosort "sort"
 	"time"
 
 	"git.sr.ht/~rjarry/aerc/lib/sort"
@@ -36,7 +37,9 @@ type MessageStore struct {
 
 	defaultSortCriteria []*types.SortCriterion
 
-	thread bool
+	thread       bool
+	buildThreads bool
+	builder      *ThreadBuilder
 
 	// Map of uids we've asked the worker to fetch
 	onUpdate       func(store *MessageStore) // TODO: multiple onUpdate handlers
@@ -242,6 +245,9 @@ func (store *MessageStore) Update(msg types.WorkerMessage) {
 				}
 			}
 		}
+		if store.builder != nil {
+			store.builder.Update(msg.Info)
+		}
 		update = true
 	case *types.FullMessage:
 		if _, ok := store.pendingBodies[msg.Content.Uid]; ok {
@@ -320,6 +326,74 @@ func (store *MessageStore) update() {
 	if store.onUpdateDirs != nil {
 		store.onUpdateDirs()
 	}
+	if store.BuildThreads() {
+		store.runThreadBuilder()
+	}
+}
+
+func (store *MessageStore) SetBuildThreads(buildThreads bool) {
+	// if worker provides threading, don't build our own threads
+	if store.thread {
+		return
+	}
+	store.buildThreads = buildThreads
+	if store.BuildThreads() {
+		store.runThreadBuilder()
+	} else {
+		store.rebuildUids()
+	}
+}
+
+func (store *MessageStore) BuildThreads() bool {
+	// if worker provides threading, don't build our own threads
+	if store.thread {
+		return false
+	}
+	return store.buildThreads
+}
+
+func (store *MessageStore) runThreadBuilder() {
+	if store.builder == nil {
+		store.builder = NewThreadBuilder(store, store.worker.Logger)
+		for _, msg := range store.Messages {
+			store.builder.Update(msg)
+		}
+	}
+	store.Threads = store.builder.Threads()
+	store.rebuildUids()
+}
+
+func (store *MessageStore) rebuildUids() {
+	start := time.Now()
+
+	uids := make([]uint32, 0, len(store.Uids()))
+
+	if store.BuildThreads() {
+		gosort.Sort(types.ByUID(store.Threads))
+		for i := len(store.Threads) - 1; i >= 0; i-- {
+			store.Threads[i].Walk(func(t *types.Thread, level int, currentErr error) error {
+				uids = append(uids, t.Uid)
+				return nil
+			})
+		}
+		uidsReversed := make([]uint32, len(uids))
+		for i := 0; i < len(uids); i++ {
+			uidsReversed[i] = uids[len(uids)-1-i]
+		}
+		uids = uidsReversed
+	} else {
+		uids = store.Uids()
+		gosort.SliceStable(uids, func(i, j int) bool { return uids[i] < uids[j] })
+	}
+
+	if store.filter {
+		store.results = uids
+	} else {
+		store.uids = uids
+	}
+
+	elapsed := time.Since(start)
+	store.worker.Logger.Println("Store: Rebuilding UIDs took", elapsed)
 }
 
 func (store *MessageStore) Delete(uids []uint32,
@@ -594,6 +668,9 @@ func (store *MessageStore) ApplyFilter(results []uint32) {
 func (store *MessageStore) ApplyClear() {
 	store.results = nil
 	store.filter = false
+	if store.BuildThreads() {
+		store.runThreadBuilder()
+	}
 }
 
 func (store *MessageStore) nextPrevResult(delta int) {
diff --git a/lib/threadbuilder.go b/lib/threadbuilder.go
new file mode 100644
index 00000000..c87d0bfb
--- /dev/null
+++ b/lib/threadbuilder.go
@@ -0,0 +1,242 @@
+package lib
+
+import (
+	"log"
+	"time"
+
+	"git.sr.ht/~rjarry/aerc/models"
+	"git.sr.ht/~rjarry/aerc/worker/types"
+	"github.com/gatherstars-com/jwz"
+)
+
+type UidStorer interface {
+	Uids() []uint32
+}
+
+type ThreadBuilder struct {
+	threadBlocks   map[uint32]jwz.Threadable
+	messageidToUid map[string]uint32
+	seen           map[uint32]bool
+	store          UidStorer
+	logger         *log.Logger
+}
+
+func NewThreadBuilder(store UidStorer, logger *log.Logger) *ThreadBuilder {
+	tb := &ThreadBuilder{
+		threadBlocks:   make(map[uint32]jwz.Threadable),
+		messageidToUid: make(map[string]uint32),
+		seen:           make(map[uint32]bool),
+		store:          store,
+		logger:         logger,
+	}
+	return tb
+}
+
+func (builder *ThreadBuilder) Update(msg *models.MessageInfo) {
+	if msg != nil {
+		if threadable := newThreadable(msg); threadable != nil {
+			builder.messageidToUid[threadable.MessageThreadID()] = msg.Uid
+			builder.threadBlocks[msg.Uid] = threadable
+		}
+	}
+}
+
+func (builder *ThreadBuilder) Threads() []*types.Thread {
+	start := time.Now()
+
+	threads := builder.buildAercThreads(builder.generateStructure())
+
+	elapsed := time.Since(start)
+	builder.logger.Println("ThreadBuilder:", len(threads), "threads created in", elapsed)
+
+	return threads
+}
+
+func (builder *ThreadBuilder) generateStructure() jwz.Threadable {
+	jwzThreads := make([]jwz.Threadable, 0, len(builder.threadBlocks))
+	for _, uid := range builder.store.Uids() {
+		if thr, ok := builder.threadBlocks[uid]; ok {
+			jwzThreads = append(jwzThreads, thr)
+		}
+	}
+
+	threader := jwz.NewThreader()
+	threadStructure, err := threader.ThreadSlice(jwzThreads)
+	if err != nil {
+		builder.logger.Printf("ThreadBuilder: threading operation return error: %#v", err)
+	}
+	return threadStructure
+}
+
+func (builder *ThreadBuilder) buildAercThreads(structure jwz.Threadable) []*types.Thread {
+	threads := make([]*types.Thread, 0, len(builder.threadBlocks))
+	if structure == nil {
+		for _, uid := range builder.store.Uids() {
+			threads = append(threads, &types.Thread{Uid: uid})
+		}
+	} else {
+		// fill threads with nil messages
+		for _, uid := range builder.store.Uids() {
+			if _, ok := builder.threadBlocks[uid]; !ok {
+				threads = append(threads, &types.Thread{Uid: uid})
+			}
+		}
+		// append the on-the-fly created aerc threads
+		root := &types.Thread{Uid: 0}
+		builder.seen = make(map[uint32]bool)
+		builder.buildTree(structure, root)
+		for iter := root.FirstChild; iter != nil; iter = iter.NextSibling {
+			iter.Parent = nil
+			threads = append(threads, iter)
+		}
+	}
+	return threads
+}
+
+// buildTree recursively translates the jwz threads structure into aerc threads
+// builder.seen is used to avoid potential double-counting and should be empty
+// on first call of this function
+func (builder *ThreadBuilder) buildTree(treeNode jwz.Threadable, target *types.Thread) {
+	if treeNode == nil {
+		return
+	}
+
+	// deal with child
+	uid, ok := builder.messageidToUid[treeNode.MessageThreadID()]
+	if _, seen := builder.seen[uid]; ok && !seen {
+		builder.seen[uid] = true
+		childNode := &types.Thread{Uid: uid, Parent: target}
+		target.OrderedInsert(childNode)
+		builder.buildTree(treeNode.GetChild(), childNode)
+	} else {
+		builder.buildTree(treeNode.GetChild(), target)
+	}
+
+	// deal with siblings
+	for next := treeNode.GetNext(); next != nil; next = next.GetNext() {
+
+		uid, ok := builder.messageidToUid[next.MessageThreadID()]
+		if _, seen := builder.seen[uid]; ok && !seen {
+			builder.seen[uid] = true
+			nn := &types.Thread{Uid: uid, Parent: target}
+			target.OrderedInsert(nn)
+			builder.buildTree(next.GetChild(), nn)
+		} else {
+			builder.buildTree(next.GetChild(), target)
+		}
+	}
+}
+
+// threadable implements the jwz.threadable interface which is required for the
+// jwz threading algorithm
+type threadable struct {
+	MsgInfo   *models.MessageInfo
+	MessageId string
+	Next      jwz.Threadable
+	Parent    jwz.Threadable
+	Child     jwz.Threadable
+	Dummy     bool
+}
+
+func newThreadable(msg *models.MessageInfo) *threadable {
+	msgid, err := msg.MsgId()
+	if err != nil {
+		return nil
+	}
+	return &threadable{
+		MessageId: msgid,
+		MsgInfo:   msg,
+		Next:      nil,
+		Parent:    nil,
+		Child:     nil,
+		Dummy:     false,
+	}
+}
+
+func (t *threadable) MessageThreadID() string {
+	return t.MessageId
+}
+
+func (t *threadable) MessageThreadReferences() []string {
+	if t.IsDummy() || t.MsgInfo == nil {
+		return nil
+	}
+	refs, err := t.MsgInfo.References()
+	if err != nil || len(refs) == 0 {
+		inreplyto, err := t.MsgInfo.InReplyTo()
+		if err != nil {
+			return nil
+		}
+		refs = []string{inreplyto}
+	}
+	return refs
+}
+
+func (t *threadable) Subject() string {
+	// deactivate threading by subject for now
+	return ""
+
+	if t.IsDummy() || t.MsgInfo == nil || t.MsgInfo.Envelope == nil {
+		return ""
+	}
+	return t.MsgInfo.Envelope.Subject
+}
+
+func (t *threadable) SimplifiedSubject() string {
+	return ""
+}
+
+func (t *threadable) SubjectIsReply() bool {
+	return false
+}
+
+func (t *threadable) SetNext(next jwz.Threadable) {
+	t.Next = next
+}
+
+func (t *threadable) SetChild(kid jwz.Threadable) {
+	t.Child = kid
+	if kid != nil {
+		kid.SetParent(t)
+	}
+}
+
+func (t *threadable) SetParent(parent jwz.Threadable) {
+	t.Parent = parent
+}
+
+func (t *threadable) GetNext() jwz.Threadable {
+	return t.Next
+}
+
+func (t *threadable) GetChild() jwz.Threadable {
+	return t.Child
+}
+
+func (t *threadable) GetParent() jwz.Threadable {
+	return t.Parent
+}
+
+func (t *threadable) GetDate() time.Time {
+	if t.IsDummy() {
+		if t.GetChild() != nil {
+			return t.GetChild().GetDate()
+		}
+		return time.Unix(0, 0)
+	}
+	if t.MsgInfo == nil || t.MsgInfo.Envelope == nil {
+		return time.Unix(0, 0)
+	}
+	return t.MsgInfo.Envelope.Date
+}
+
+func (t *threadable) MakeDummy(forID string) jwz.Threadable {
+	return &threadable{
+		MessageId: forID,
+		Dummy:     true,
+	}
+}
+
+func (t *threadable) IsDummy() bool {
+	return t.Dummy
+}
diff --git a/models/models.go b/models/models.go
index 45f3b9de..4087c9d3 100644
--- a/models/models.go
+++ b/models/models.go
@@ -1,6 +1,7 @@
 package models
 
 import (
+	"errors"
 	"fmt"
 	"io"
 	"time"
@@ -65,6 +66,50 @@ type MessageInfo struct {
 	Error         error
 }
 
+func (mi *MessageInfo) MsgId() (msgid string, err error) {
+	if mi == nil {
+		return "", errors.New("msg is nil")
+	}
+	if mi.Envelope == nil {
+		return "", errors.New("envelope is nil")
+	}
+	return mi.Envelope.MessageId, nil
+}
+
+func (mi *MessageInfo) InReplyTo() (msgid string, err error) {
+	if mi == nil {
+		return "", errors.New("msg is nil")
+	}
+	if mi.RFC822Headers == nil {
+		return "", errors.New("header is nil")
+	}
+	list, err := mi.RFC822Headers.MsgIDList("In-Reply-To")
+	if err != nil {
+		return "", err
+	}
+	if len(list) == 0 {
+		return "", errors.New("no results")
+	}
+	return list[0], err
+}
+
+func (mi *MessageInfo) References() ([]string, error) {
+	if mi == nil {
+		return []string{}, errors.New("msg is nil")
+	}
+	if mi.RFC822Headers == nil {
+		return []string{}, errors.New("header is nil")
+	}
+	list, err := mi.RFC822Headers.MsgIDList("References")
+	if err != nil {
+		return []string{}, err
+	}
+	if len(list) == 0 {
+		return []string{}, errors.New("no results")
+	}
+	return list, err
+}
+
 // A MessageBodyPart can be displayed in the message viewer
 type MessageBodyPart struct {
 	Reader io.Reader
diff --git a/widgets/msglist.go b/widgets/msglist.go
index 6163d0e5..50ce24ee 100644
--- a/widgets/msglist.go
+++ b/widgets/msglist.go
@@ -89,7 +89,7 @@ func (ml *MessageList) Draw(ctx *ui.Context) {
 		row          int = 0
 	)
 
-	if ml.aerc.SelectedAccount().UiConfig().ThreadingEnabled {
+	if ml.aerc.SelectedAccount().UiConfig().ThreadingEnabled || store.BuildThreads() {
 		threads := store.Threads
 		counter := len(store.Uids())
 
diff --git a/worker/types/thread.go b/worker/types/thread.go
index 18b31e94..48e4a002 100644
--- a/worker/types/thread.go
+++ b/worker/types/thread.go
@@ -17,14 +17,24 @@ type Thread struct {
 }
 
 func (t *Thread) AddChild(child *Thread) {
+	t.insertCmp(child, func(child, iter *Thread) bool { return true })
+}
+
+func (t *Thread) OrderedInsert(child *Thread) {
+	t.insertCmp(child, func(child, iter *Thread) bool { return child.Uid > iter.Uid })
+}
+
+func (t *Thread) insertCmp(child *Thread, cmp func(*Thread, *Thread) bool) {
 	if t.FirstChild == nil {
 		t.FirstChild = child
 	} else {
+		start := &Thread{Uid: t.FirstChild.Uid, NextSibling: t.FirstChild}
 		var iter *Thread
-		for iter = t.FirstChild; iter.NextSibling != nil; iter = iter.NextSibling {
+		for iter = start; iter.NextSibling != nil && cmp(child, iter); iter = iter.NextSibling {
 		}
-		child.PrevSibling = iter
+		child.NextSibling = iter.NextSibling
 		iter.NextSibling = child
+		t.FirstChild = start.NextSibling
 	}
 	child.Parent = t
 }