1package imap 2 3import ( 4 "fmt" 5 "strconv" 6 "strings" 7) 8 9// ErrBadSeqSet is used to report problems with the format of a sequence set 10// value. 11type ErrBadSeqSet string 12 13func (err ErrBadSeqSet) Error() string { 14 return fmt.Sprintf("imap: bad sequence set value %q", string(err)) 15} 16 17// Seq represents a single seq-number or seq-range value (RFC 3501 ABNF). Values 18// may be static (e.g. "1", "2:4") or dynamic (e.g. "*", "1:*"). A seq-number is 19// represented by setting Start = Stop. Zero is used to represent "*", which is 20// safe because seq-number uses nz-number rule. The order of values is always 21// Start <= Stop, except when representing "n:*", where Start = n and Stop = 0. 22type Seq struct { 23 Start, Stop uint32 24} 25 26// parseSeqNumber parses a single seq-number value (non-zero uint32 or "*"). 27func parseSeqNumber(v string) (uint32, error) { 28 if n, err := strconv.ParseUint(v, 10, 32); err == nil && v[0] != '0' { 29 return uint32(n), nil 30 } else if v == "*" { 31 return 0, nil 32 } 33 return 0, ErrBadSeqSet(v) 34} 35 36// parseSeq creates a new seq instance by parsing strings in the format "n" or 37// "n:m", where n and/or m may be "*". An error is returned for invalid values. 38func parseSeq(v string) (s Seq, err error) { 39 if sep := strings.IndexRune(v, ':'); sep < 0 { 40 s.Start, err = parseSeqNumber(v) 41 s.Stop = s.Start 42 return 43 } else if s.Start, err = parseSeqNumber(v[:sep]); err == nil { 44 if s.Stop, err = parseSeqNumber(v[sep+1:]); err == nil { 45 if (s.Stop < s.Start && s.Stop != 0) || s.Start == 0 { 46 s.Start, s.Stop = s.Stop, s.Start 47 } 48 return 49 } 50 } 51 return s, ErrBadSeqSet(v) 52} 53 54// Contains returns true if the seq-number q is contained in sequence value s. 55// The dynamic value "*" contains only other "*" values, the dynamic range "n:*" 56// contains "*" and all numbers >= n. 57func (s Seq) Contains(q uint32) bool { 58 if q == 0 { 59 return s.Stop == 0 // "*" is contained only in "*" and "n:*" 60 } 61 return s.Start != 0 && s.Start <= q && (q <= s.Stop || s.Stop == 0) 62} 63 64// Less returns true if s precedes and does not contain seq-number q. 65func (s Seq) Less(q uint32) bool { 66 return (s.Stop < q || q == 0) && s.Stop != 0 67} 68 69// Merge combines sequence values s and t into a single union if the two 70// intersect or one is a superset of the other. The order of s and t does not 71// matter. If the values cannot be merged, s is returned unmodified and ok is 72// set to false. 73func (s Seq) Merge(t Seq) (union Seq, ok bool) { 74 if union = s; s == t { 75 ok = true 76 return 77 } 78 if s.Start != 0 && t.Start != 0 { 79 // s and t are any combination of "n", "n:m", or "n:*" 80 if s.Start > t.Start { 81 s, t = t, s 82 } 83 // s starts at or before t, check where it ends 84 if (s.Stop >= t.Stop && t.Stop != 0) || s.Stop == 0 { 85 return s, true // s is a superset of t 86 } 87 // s is "n" or "n:m", if m == ^uint32(0) then t is "n:*" 88 if s.Stop+1 >= t.Start || s.Stop == ^uint32(0) { 89 return Seq{s.Start, t.Stop}, true // s intersects or touches t 90 } 91 return 92 } 93 // exactly one of s and t is "*" 94 if s.Start == 0 { 95 if t.Stop == 0 { 96 return t, true // s is "*", t is "n:*" 97 } 98 } else if s.Stop == 0 { 99 return s, true // s is "n:*", t is "*" 100 } 101 return 102} 103 104// String returns sequence value s as a seq-number or seq-range string. 105func (s Seq) String() string { 106 if s.Start == s.Stop { 107 if s.Start == 0 { 108 return "*" 109 } 110 return strconv.FormatUint(uint64(s.Start), 10) 111 } 112 b := strconv.AppendUint(make([]byte, 0, 24), uint64(s.Start), 10) 113 if s.Stop == 0 { 114 return string(append(b, ':', '*')) 115 } 116 return string(strconv.AppendUint(append(b, ':'), uint64(s.Stop), 10)) 117} 118 119// SeqSet is used to represent a set of message sequence numbers or UIDs (see 120// sequence-set ABNF rule). The zero value is an empty set. 121type SeqSet struct { 122 Set []Seq 123} 124 125// ParseSeqSet returns a new SeqSet instance after parsing the set string. 126func ParseSeqSet(set string) (s *SeqSet, err error) { 127 s = new(SeqSet) 128 return s, s.Add(set) 129} 130 131// Add inserts new sequence values into the set. The string format is described 132// by RFC 3501 sequence-set ABNF rule. If an error is encountered, all values 133// inserted successfully prior to the error remain in the set. 134func (s *SeqSet) Add(set string) error { 135 for _, sv := range strings.Split(set, ",") { 136 v, err := parseSeq(sv) 137 if err != nil { 138 return err 139 } 140 s.insert(v) 141 } 142 return nil 143} 144 145// AddNum inserts new sequence numbers into the set. The value 0 represents "*". 146func (s *SeqSet) AddNum(q ...uint32) { 147 for _, v := range q { 148 s.insert(Seq{v, v}) 149 } 150} 151 152// AddRange inserts a new sequence range into the set. 153func (s *SeqSet) AddRange(Start, Stop uint32) { 154 if (Stop < Start && Stop != 0) || Start == 0 { 155 s.insert(Seq{Stop, Start}) 156 } else { 157 s.insert(Seq{Start, Stop}) 158 } 159} 160 161// AddSet inserts all values from t into s. 162func (s *SeqSet) AddSet(t *SeqSet) { 163 for _, v := range t.Set { 164 s.insert(v) 165 } 166} 167 168// Clear removes all values from the set. 169func (s *SeqSet) Clear() { 170 s.Set = s.Set[:0] 171} 172 173// Empty returns true if the sequence set does not contain any values. 174func (s SeqSet) Empty() bool { 175 return len(s.Set) == 0 176} 177 178// Dynamic returns true if the set contains "*" or "n:*" values. 179func (s SeqSet) Dynamic() bool { 180 return len(s.Set) > 0 && s.Set[len(s.Set)-1].Stop == 0 181} 182 183// Contains returns true if the non-zero sequence number or UID q is contained 184// in the set. The dynamic range "n:*" contains all q >= n. It is the caller's 185// responsibility to handle the special case where q is the maximum UID in the 186// mailbox and q < n (i.e. the set cannot match UIDs against "*:n" or "*" since 187// it doesn't know what the maximum value is). 188func (s SeqSet) Contains(q uint32) bool { 189 if _, ok := s.search(q); ok { 190 return q != 0 191 } 192 return false 193} 194 195// String returns a sorted representation of all contained sequence values. 196func (s SeqSet) String() string { 197 if len(s.Set) == 0 { 198 return "" 199 } 200 b := make([]byte, 0, 64) 201 for _, v := range s.Set { 202 b = append(b, ',') 203 if v.Start == 0 { 204 b = append(b, '*') 205 continue 206 } 207 b = strconv.AppendUint(b, uint64(v.Start), 10) 208 if v.Start != v.Stop { 209 if v.Stop == 0 { 210 b = append(b, ':', '*') 211 continue 212 } 213 b = strconv.AppendUint(append(b, ':'), uint64(v.Stop), 10) 214 } 215 } 216 return string(b[1:]) 217} 218 219// insert adds sequence value v to the set. 220func (s *SeqSet) insert(v Seq) { 221 i, _ := s.search(v.Start) 222 merged := false 223 if i > 0 { 224 // try merging with the preceding entry (e.g. "1,4".insert(2), i == 1) 225 s.Set[i-1], merged = s.Set[i-1].Merge(v) 226 } 227 if i == len(s.Set) { 228 // v was either merged with the last entry or needs to be appended 229 if !merged { 230 s.insertAt(i, v) 231 } 232 return 233 } else if merged { 234 i-- 235 } else if s.Set[i], merged = s.Set[i].Merge(v); !merged { 236 s.insertAt(i, v) // insert in the middle (e.g. "1,5".insert(3), i == 1) 237 return 238 } 239 // v was merged with s.Set[i], continue trying to merge until the end 240 for j := i + 1; j < len(s.Set); j++ { 241 if s.Set[i], merged = s.Set[i].Merge(s.Set[j]); !merged { 242 if j > i+1 { 243 // cut out all entries between i and j that were merged 244 s.Set = append(s.Set[:i+1], s.Set[j:]...) 245 } 246 return 247 } 248 } 249 // everything after s.Set[i] was merged 250 s.Set = s.Set[:i+1] 251} 252 253// insertAt inserts a new sequence value v at index i, resizing s.Set as needed. 254func (s *SeqSet) insertAt(i int, v Seq) { 255 if n := len(s.Set); i == n { 256 // insert at the end 257 s.Set = append(s.Set, v) 258 return 259 } else if n < cap(s.Set) { 260 // enough space, shift everything at and after i to the right 261 s.Set = s.Set[:n+1] 262 copy(s.Set[i+1:], s.Set[i:]) 263 } else { 264 // allocate new slice and copy everything, n is at least 1 265 set := make([]Seq, n+1, n*2) 266 copy(set, s.Set[:i]) 267 copy(set[i+1:], s.Set[i:]) 268 s.Set = set 269 } 270 s.Set[i] = v 271} 272 273// search attempts to find the index of the sequence set value that contains q. 274// If no values contain q, the returned index is the position where q should be 275// inserted and ok is set to false. 276func (s SeqSet) search(q uint32) (i int, ok bool) { 277 min, max := 0, len(s.Set)-1 278 for min < max { 279 if mid := (min + max) >> 1; s.Set[mid].Less(q) { 280 min = mid + 1 281 } else { 282 max = mid 283 } 284 } 285 if max < 0 || s.Set[min].Less(q) { 286 return len(s.Set), false // q is the new largest value 287 } 288 return min, s.Set[min].Contains(q) 289} 290