aerc/worker/imap/seqmap.go

78 lines
1.5 KiB
Go
Raw Permalink Normal View History

package imap
import (
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
"sort"
"sync"
)
type SeqMap struct {
lock sync.Mutex
// map of IMAP sequence numbers to message UIDs
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
m []uint32
}
// Initialize sets the initial seqmap of the mailbox
func (s *SeqMap) Initialize(uids []uint32) {
s.lock.Lock()
s.m = make([]uint32, len(uids))
copy(s.m, uids)
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
s.sort()
s.lock.Unlock()
}
func (s *SeqMap) Size() int {
s.lock.Lock()
size := len(s.m)
s.lock.Unlock()
return size
}
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
// Get returns the UID of the given seqnum
func (s *SeqMap) Get(seqnum uint32) (uint32, bool) {
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
if int(seqnum) > s.Size() || seqnum < 1 {
return 0, false
}
s.lock.Lock()
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
uid := s.m[seqnum-1]
s.lock.Unlock()
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
return uid, true
}
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
// Put adds a UID to the slice. Put should only be used to add new messages
// into the slice
func (s *SeqMap) Put(uid uint32) {
s.lock.Lock()
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
for _, n := range s.m {
if n == uid {
// We already have this UID, don't insert it.
s.lock.Unlock()
return
}
}
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
s.m = append(s.m, uid)
s.sort()
s.lock.Unlock()
}
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
// Pop removes seqnum from the SeqMap. seqnum must be a valid seqnum, ie
// [1:size of mailbox]
func (s *SeqMap) Pop(seqnum uint32) (uint32, bool) {
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
if int(seqnum) > s.Size() || seqnum < 1 {
return 0, false
}
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
s.lock.Lock()
uid := s.m[seqnum-1]
s.m = append(s.m[:seqnum-1], s.m[seqnum:]...)
s.lock.Unlock()
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
return uid, true
}
seqmap: refactor seqmap to use slice instead of map The imap worker's seqmap is represented as a map of sequence number to UID. This presents a problem when expunging group of messages from the mailbox: each individual expunge decrements the sequence numbers by 1 (for every sequence number greater than the expunged). This requires a looping around the map to update the keys. The use of a map also requires that both the sequence number and the UID of a message be known in order to insert it into the map. This is only discovered by fetching individual message body parts (flags, headers, etc), leaving the seqmap to be empty until we have fetched information about each message. In certain instances (if a mailbox has recently been loaded), all information is loaded in memory and no new information is fetched - leaving the seqmap empty and the UI out of sync with the worker. Refactor the seqmap as a slice, so that any expunge automatically decrements the rest of the sequences. Use the results of FetchDirectoryContents or FetchDirectoryThreaded to initialize the seqmap with all discovered UIDs. Sort the UIDs in ascending order: IMAP specification requires that sequence numbers start at 1 increase in order of ascending UID. Add individual messages to the map if they come via a MessageUpdate and have a sequence number larger than our slice. Update seqmap tests with new logic. Reference: https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2 Fixes: https://todo.sr.ht/~rjarry/aerc/69 Signed-off-by: Tim Culverhouse <tim@timculverhouse.com> Acked-by: Robin Jarry <robin@jarry.cc>
2022-08-01 19:18:25 +02:00
// sort sorts the slice in ascending UID order. See:
// https://datatracker.ietf.org/doc/html/rfc3501#section-2.3.1.2
func (s *SeqMap) sort() {
// Always be sure the SeqMap is sorted
sort.Slice(s.m, func(i, j int) bool {
return s.m[i] < s.m[j]
})
}