1package imapserver
2
3import (
4 "fmt"
5 "time"
6
7 "github.com/mjl-/mox/store"
8)
9
10type numSet struct {
11 searchResult bool // "$"
12 ranges []numRange
13}
14
15type numRange struct {
16 first setNumber
17 last *setNumber // if nil, this numRange is just a setNumber in "first" and first.star will be false
18}
19
20type setNumber struct {
21 number uint32
22 star bool // References last message (max sequence number/uid). ../rfc/9051:799
23}
24
25// containsSeq returns whether seq is in the numSet, given uids and (saved) searchResult.
26// uids and searchResult must be sorted. searchResult can have uids that are no longer in uids.
27func (ss numSet) containsSeq(seq msgseq, uids []store.UID, searchResult []store.UID) bool {
28 if len(uids) == 0 {
29 return false
30 }
31 if ss.searchResult {
32 uid := uids[int(seq)-1]
33 return uidSearch(searchResult, uid) > 0 && uidSearch(uids, uid) > 0
34 }
35 return ss.containsSeqCount(seq, uint32(len(uids)))
36}
37
38// containsSeqCount returns whether seq is contained in ss, which must not be a
39// searchResult, assuming the message count.
40func (ss numSet) containsSeqCount(seq msgseq, msgCount uint32) bool {
41 if msgCount == 0 {
42 return false
43 }
44 for _, r := range ss.ranges {
45 first := r.first.number
46 if r.first.star || first > msgCount {
47 first = msgCount
48 }
49
50 last := first
51 if r.last != nil {
52 last = r.last.number
53 if r.last.star || last > msgCount {
54 last = msgCount
55 }
56 }
57 if first > last {
58 first, last = last, first
59 }
60
61 if uint32(seq) >= first && uint32(seq) <= last {
62 return true
63 }
64 }
65 return false
66}
67
68// containsKnownUID returns whether uid, which is known to exist, matches the numSet.
69// highestUID must return the highest/last UID in the mailbox, or an error. A last UID must
70// exist, otherwise this method wouldn't have been called with a known uid.
71// highestUID is needed for interpreting UID sets like "<num>:*" where num is
72// higher than the uid to check.
73func (ss numSet) xcontainsKnownUID(uid store.UID, searchResult []store.UID, xhighestUID func() store.UID) bool {
74 if ss.searchResult {
75 return uidSearch(searchResult, uid) > 0
76 }
77
78 for _, r := range ss.ranges {
79 a := store.UID(r.first.number)
80 // Num in <num>:* can be larger than last, but it still matches the last...
81 // Similar for *:<num>. ../rfc/9051:4814
82 if r.first.star {
83 if r.last != nil && uid >= store.UID(r.last.number) {
84 return true
85 }
86 a = xhighestUID()
87 }
88 b := a
89 if r.last != nil {
90 b = store.UID(r.last.number)
91 if r.last.star {
92 if uid >= a {
93 return true
94 }
95 b = xhighestUID()
96 }
97 }
98 if a > b {
99 a, b = b, a
100 }
101 if uid >= a && uid <= b {
102 return true
103 }
104 }
105 return false
106}
107
108// xinterpretStar returns a numset that interprets stars in a uid set using
109// xlastUID, returning a new uid set without stars, with increasing first/last, and
110// without unneeded ranges (first.number != last.number).
111// If there are no messages in the mailbox, xlastUID must return zero and the
112// returned numSet will include 0.
113func (s numSet) xinterpretStar(xlastUID func() store.UID) numSet {
114 var ns numSet
115
116 for _, r := range s.ranges {
117 first := r.first.number
118 if r.first.star {
119 first = uint32(xlastUID())
120 }
121 last := first
122 if r.last != nil {
123 if r.last.star {
124 last = uint32(xlastUID())
125 } else {
126 last = r.last.number
127 }
128 }
129 if first > last {
130 first, last = last, first
131 }
132 nr := numRange{first: setNumber{number: first}}
133 if first != last {
134 nr.last = &setNumber{number: last}
135 }
136 ns.ranges = append(ns.ranges, nr)
137 }
138 return ns
139}
140
141// contains returns whether the numset contains the number.
142// only allowed on basic, strictly increasing numsets.
143func (ss numSet) contains(v uint32) bool {
144 for _, r := range ss.ranges {
145 if r.first.number == v || r.last != nil && v > r.first.number && v <= r.last.number {
146 return true
147 }
148 }
149 return false
150}
151
152func (ss numSet) empty() bool {
153 return !ss.searchResult && len(ss.ranges) == 0
154}
155
156// Strings returns the numset in zero or more strings of maxSize bytes. If
157// maxSize is <= 0, a single string is returned.
158func (ss numSet) Strings(maxSize int) []string {
159 if ss.searchResult {
160 return []string{"$"}
161 }
162 var l []string
163 var line string
164 for _, r := range ss.ranges {
165 s := ""
166 if r.first.star {
167 s += "*"
168 } else {
169 s += fmt.Sprintf("%d", r.first.number)
170 }
171 if r.last == nil {
172 if r.first.star {
173 panic("invalid numSet range first star without last")
174 }
175 } else {
176 s += ":"
177 if r.last.star {
178 s += "*"
179 } else {
180 s += fmt.Sprintf("%d", r.last.number)
181 }
182 }
183
184 nsize := len(line) + len(s)
185 if line != "" {
186 nsize++ // comma
187 }
188 if maxSize > 0 && nsize > maxSize {
189 l = append(l, line)
190 line = s
191 continue
192 }
193 if line != "" {
194 line += ","
195 }
196 line += s
197 }
198 if line != "" {
199 l = append(l, line)
200 }
201 return l
202}
203
204func (ss numSet) String() string {
205 l := ss.Strings(0)
206 if len(l) == 0 {
207 return ""
208 }
209 return l[0]
210}
211
212// whether numSet only has numbers (no star/search), and is strictly increasing.
213func (s *numSet) isBasicIncreasing() bool {
214 if s.searchResult {
215 return false
216 }
217 var last uint32
218 for _, r := range s.ranges {
219 if r.first.star || r.first.number <= last || r.last != nil && (r.last.star || r.last.number < r.first.number) {
220 return false
221 }
222 last = r.first.number
223 if r.last != nil {
224 last = r.last.number
225 }
226 }
227 return true
228}
229
230type numIter struct {
231 s numSet
232 i int
233 r *rangeIter
234}
235
236// newIter must only be called on a numSet that is basic (no star/search) and ascending.
237func (s numSet) newIter() *numIter {
238 return &numIter{s: s}
239}
240
241func (i *numIter) Next() (uint32, bool) {
242 if v, ok := i.r.Next(); ok {
243 return v, ok
244 }
245 if i.i >= len(i.s.ranges) {
246 return 0, false
247 }
248 i.r = i.s.ranges[i.i].newIter()
249 i.i++
250 return i.r.Next()
251}
252
253type rangeIter struct {
254 r numRange
255 o int
256}
257
258// newIter must only be called on a range in a numSet that is basic (no star/search) and ascending.
259func (r numRange) newIter() *rangeIter {
260 return &rangeIter{r: r, o: 0}
261}
262
263func (r *rangeIter) Next() (uint32, bool) {
264 if r == nil {
265 return 0, false
266 }
267 if r.o == 0 {
268 r.o++
269 return r.r.first.number, true
270 }
271 if r.r.last == nil || r.r.first.number+uint32(r.o) > r.r.last.number {
272 return 0, false
273 }
274 v := r.r.first.number + uint32(r.o)
275 r.o++
276 return v, true
277}
278
279// append adds a new number to the set, extending a range, or starting a new one (possibly the first).
280// can only be used on basic numsets, without star/searchResult.
281func (s *numSet) append(v uint32) {
282 if len(s.ranges) == 0 {
283 s.ranges = []numRange{{first: setNumber{number: v}}}
284 return
285 }
286 ri := len(s.ranges) - 1
287 r := s.ranges[ri]
288 if v == r.first.number+1 && r.last == nil {
289 s.ranges[ri].last = &setNumber{number: v}
290 } else if r.last != nil && v == r.last.number+1 {
291 r.last.number++
292 } else {
293 s.ranges = append(s.ranges, numRange{first: setNumber{number: v}})
294 }
295}
296
297type partial struct {
298 offset uint32
299 count uint32
300}
301
302type sectionPart struct {
303 part []uint32
304 text *sectionText
305}
306
307type sectionText struct {
308 mime bool // if "MIME"
309 msgtext *sectionMsgtext
310}
311
312// a non-nil *sectionSpec with nil msgtext & nil part means there were []'s, but nothing inside. e.g. "BODY[]".
313type sectionSpec struct {
314 msgtext *sectionMsgtext
315 part *sectionPart
316}
317
318type sectionMsgtext struct {
319 s string // "HEADER", "HEADER.FIELDS", "HEADER.FIELDS.NOT", "TEXT"
320 headers []string // for "HEADER.FIELDS"*
321}
322
323type fetchAtt struct {
324 field string // uppercase, eg "ENVELOPE", "BODY". ".PEEK" is removed.
325 peek bool
326 section *sectionSpec
327 sectionBinary []uint32
328 partial *partial
329 previewLazy bool // Not regular "PREVIEW", but "PREVIEW (LAZY)".
330}
331
332type searchKey struct {
333 // Only one of searchKeys, seqSet and op can be non-nil/non-empty.
334 searchKeys []searchKey // In case of nested/multiple keys. Also for the top-level command.
335 seqSet *numSet // In case of bare sequence set. For op UID, field uidSet contains the parameter.
336 op string // Determines which of the fields below are set.
337
338 headerField string
339 astring string
340 date time.Time
341 atom string
342 number int64
343 searchKey *searchKey
344 searchKey2 *searchKey
345 uidSet numSet
346 clientModseq *int64
347}
348
349// Whether we need message sequence numbers to evaluate. Sequence numbers are not
350// allowed with UIDONLY. And if we need sequence numbers we cannot optimize
351// searching for MAX with a query in reverse order.
352func (sk *searchKey) hasSequenceNumbers() bool {
353 for _, k := range sk.searchKeys {
354 if k.hasSequenceNumbers() {
355 return true
356 }
357 }
358 if sk.searchKey != nil && sk.searchKey.hasSequenceNumbers() || sk.searchKey2 != nil && sk.searchKey2.hasSequenceNumbers() {
359 return true
360 }
361 return sk.seqSet != nil && !sk.seqSet.searchResult
362}
363
364// hasModseq returns whether there is a modseq filter anywhere in the searchkey.
365func (sk *searchKey) hasModseq() bool {
366 if sk.clientModseq != nil {
367 return true
368 }
369 for _, e := range sk.searchKeys {
370 if e.hasModseq() {
371 return true
372 }
373 }
374 if sk.searchKey != nil && sk.searchKey.hasModseq() {
375 return true
376 }
377 if sk.searchKey2 != nil && sk.searchKey2.hasModseq() {
378 return true
379 }
380 return false
381}
382
383func compactUIDSet(l []store.UID) (r numSet) {
384 for len(l) > 0 {
385 e := 1
386 for ; e < len(l) && l[e] == l[e-1]+1; e++ {
387 }
388 first := setNumber{number: uint32(l[0])}
389 var last *setNumber
390 if e > 1 {
391 last = &setNumber{number: uint32(l[e-1])}
392 }
393 r.ranges = append(r.ranges, numRange{first, last})
394 l = l[e:]
395 }
396 return
397}
398