Repository: emersion/go-imap
Pull request #578 (2024-01-02 10:25:54)

Add SeqSet and UIDSet
Note, `SearchRes` needs to return a `UIDSet` so that it can be used in `UID EXPUNGE`.

- [x] Docs
- [x] Double-check SEARCHRES implications (is it fine to hardcode `$` to `UIDSet`?)
- [ ] Some values can be either seq num or UID, how to represent these? Examples: `SearchData.Min/Max`, `SortCommand.Wait`, `ThreadData.Chain`. Should we add separate UID types for each?
- [x] `SearchData.AllNums` returns a `[]uint32`, should we add `SearchData.AllUIDs` as well?

Closes: https://github.com/emersion/go-imap/issues/526


Patch:
diff --git a/copy.go b/copy.go
index c8430d7..f685a60 100644
--- a/copy.go
+++ b/copy.go
@@ -4,6 +4,6 @@ package imap
 type CopyData struct {
 	// requires UIDPLUS or IMAP4rev2
 	UIDValidity uint32
-	SourceUIDs  NumSet
-	DestUIDs    NumSet
+	SourceUIDs  UIDSet
+	DestUIDs    UIDSet
 }
diff --git a/imapclient/client.go b/imapclient/client.go
index 7c97d0a..a7d9a5f 100644
--- a/imapclient/client.go
+++ b/imapclient/client.go
@@ -975,11 +975,14 @@ func (c *Client) Unsubscribe(mailbox string) *Command {
 	return cmd
 }
 
-func uidCmdName(name string, uid bool) string {
-	if uid {
-		return "UID " + name
-	} else {
+func uidCmdName(name string, kind imapwire.NumKind) string {
+	switch kind {
+	case imapwire.NumKindSeq:
 		return name
+	case imapwire.NumKindUID:
+		return "UID " + name
+	default:
+		panic("imapclient: invalid imapwire.NumKind")
 	}
 }
 
diff --git a/imapclient/copy.go b/imapclient/copy.go
index cff96de..29e39b8 100644
--- a/imapclient/copy.go
+++ b/imapclient/copy.go
@@ -7,26 +7,15 @@ import (
 	"github.com/emersion/go-imap/v2/internal/imapwire"
 )
 
-func (c *Client) copy(uid bool, seqSet imap.NumSet, mailbox string) *CopyCommand {
+// Copy sends a COPY command.
+func (c *Client) Copy(numSet imap.NumSet, mailbox string) *CopyCommand {
 	cmd := &CopyCommand{}
-	enc := c.beginCommand(uidCmdName("COPY", uid), cmd)
-	enc.SP().NumSet(seqSet).SP().Mailbox(mailbox)
+	enc := c.beginCommand(uidCmdName("COPY", imapwire.NumSetKind(numSet)), cmd)
+	enc.SP().NumSet(numSet).SP().Mailbox(mailbox)
 	enc.end()
 	return cmd
 }
 
-// Copy sends a COPY command.
-func (c *Client) Copy(seqSet imap.NumSet, mailbox string) *CopyCommand {
-	return c.copy(false, seqSet, mailbox)
-}
-
-// UIDCopy sends a UID COPY command.
-//
-// See Copy.
-func (c *Client) UIDCopy(seqSet imap.NumSet, mailbox string) *CopyCommand {
-	return c.copy(true, seqSet, mailbox)
-}
-
 // CopyCommand is a COPY command.
 type CopyCommand struct {
 	cmd
@@ -37,8 +26,8 @@ func (cmd *CopyCommand) Wait() (*imap.CopyData, error) {
 	return &cmd.data, cmd.cmd.Wait()
 }
 
-func readRespCodeCopyUID(dec *imapwire.Decoder) (uidValidity uint32, srcUIDs, dstUIDs imap.NumSet, err error) {
-	if !dec.ExpectNumber(&uidValidity) || !dec.ExpectSP() || !dec.ExpectNumSet(&srcUIDs) || !dec.ExpectSP() || !dec.ExpectNumSet(&dstUIDs) {
+func readRespCodeCopyUID(dec *imapwire.Decoder) (uidValidity uint32, srcUIDs, dstUIDs imap.UIDSet, err error) {
+	if !dec.ExpectNumber(&uidValidity) || !dec.ExpectSP() || !dec.ExpectUIDSet(&srcUIDs) || !dec.ExpectSP() || !dec.ExpectUIDSet(&dstUIDs) {
 		return 0, nil, nil, dec.Err()
 	}
 	if srcUIDs.Dynamic() || dstUIDs.Dynamic() {
diff --git a/imapclient/expunge.go b/imapclient/expunge.go
index 50bcf71..d582d60 100644
--- a/imapclient/expunge.go
+++ b/imapclient/expunge.go
@@ -14,7 +14,7 @@ func (c *Client) Expunge() *ExpungeCommand {
 // UIDExpunge sends a UID EXPUNGE command.
 //
 // This command requires support for IMAP4rev2 or the UIDPLUS extension.
-func (c *Client) UIDExpunge(uids imap.NumSet) *ExpungeCommand {
+func (c *Client) UIDExpunge(uids imap.UIDSet) *ExpungeCommand {
 	cmd := &ExpungeCommand{seqNums: make(chan uint32, 128)}
 	enc := c.beginCommand("UID EXPUNGE", cmd)
 	enc.SP().NumSet(uids)
diff --git a/imapclient/fetch.go b/imapclient/fetch.go
index 675ff25..4588cc9 100644
--- a/imapclient/fetch.go
+++ b/imapclient/fetch.go
@@ -12,19 +12,26 @@ import (
 	"github.com/emersion/go-imap/v2/internal/imapwire"
 )
 
-func (c *Client) fetch(uid bool, seqSet imap.NumSet, options *imap.FetchOptions) *FetchCommand {
+// Fetch sends a FETCH command.
+//
+// The caller must fully consume the FetchCommand. A simple way to do so is to
+// defer a call to FetchCommand.Close.
+//
+// A nil options pointer is equivalent to a zero options value.
+func (c *Client) Fetch(numSet imap.NumSet, options *imap.FetchOptions) *FetchCommand {
 	if options == nil {
 		options = new(imap.FetchOptions)
 	}
 
+	numKind := imapwire.NumSetKind(numSet)
+
 	cmd := &FetchCommand{
-		uid:    uid,
-		seqSet: seqSet,
+		numSet: numSet,
 		msgs:   make(chan *FetchMessageData, 128),
 	}
-	enc := c.beginCommand(uidCmdName("FETCH", uid), cmd)
-	enc.SP().NumSet(seqSet).SP()
-	writeFetchItems(enc.Encoder, uid, options)
+	enc := c.beginCommand(uidCmdName("FETCH", numKind), cmd)
+	enc.SP().NumSet(numSet).SP()
+	writeFetchItems(enc.Encoder, numKind, options)
 	if options.ChangedSince != 0 {
 		enc.SP().Special('(').Atom("CHANGEDSINCE").SP().ModSeq(options.ChangedSince).Special(')')
 	}
@@ -32,29 +39,12 @@ func (c *Client) fetch(uid bool, seqSet imap.NumSet, options *imap.FetchOptions)
 	return cmd
 }
 
-// Fetch sends a FETCH command.
-//
-// The caller must fully consume the FetchCommand. A simple way to do so is to
-// defer a call to FetchCommand.Close.
-//
-// A nil options pointer is equivalent to a zero options value.
-func (c *Client) Fetch(seqSet imap.NumSet, options *imap.FetchOptions) *FetchCommand {
-	return c.fetch(false, seqSet, options)
-}
-
-// UIDFetch sends a UID FETCH command.
-//
-// See Fetch.
-func (c *Client) UIDFetch(seqSet imap.NumSet, options *imap.FetchOptions) *FetchCommand {
-	return c.fetch(true, seqSet, options)
-}
-
-func writeFetchItems(enc *imapwire.Encoder, uid bool, options *imap.FetchOptions) {
+func writeFetchItems(enc *imapwire.Encoder, numKind imapwire.NumKind, options *imap.FetchOptions) {
 	listEnc := enc.BeginList()
 
 	// Ensure we request UID as the first data item for UID FETCH, to be safer.
 	// We want to get it before any literal.
-	if options.UID || uid {
+	if options.UID || numKind == imapwire.NumKindUID {
 		listEnc.Item().Atom("UID")
 	}
 
@@ -159,14 +149,42 @@ func writeSectionPartial(enc *imapwire.Encoder, partial *imap.SectionPartial) {
 type FetchCommand struct {
 	cmd
 
-	uid        bool
-	seqSet     imap.NumSet
-	recvNumSet imap.NumSet
+	numSet     imap.NumSet
+	recvSeqSet imap.SeqSet
+	recvUIDSet imap.UIDSet
 
 	msgs chan *FetchMessageData
 	prev *FetchMessageData
 }
 
+func (cmd *FetchCommand) recvSeqNum(seqNum uint32) bool {
+	set, ok := cmd.numSet.(imap.SeqSet)
+	if !ok || !set.Contains(seqNum) {
+		return false
+	}
+
+	if cmd.recvSeqSet.Contains(seqNum) {
+		return false
+	}
+
+	cmd.recvSeqSet.AddNum(seqNum)
+	return true
+}
+
+func (cmd *FetchCommand) recvUID(uid imap.UID) bool {
+	set, ok := cmd.numSet.(imap.UIDSet)
+	if !ok || !set.Contains(uid) {
+		return false
+	}
+
+	if cmd.recvUIDSet.Contains(uid) {
+		return false
+	}
+
+	cmd.recvUIDSet.AddNum(uid)
+	return true
+}
+
 // Next advances to the next message.
 //
 // On success, the message is returned. On error or if there are no more
@@ -464,18 +482,11 @@ func (c *Client) handleFetch(seqNum uint32) error {
 			}
 
 			// Skip if we haven't requested or already handled this message
-			var num uint32
-			if cmd.uid {
-				num = uint32(uid)
+			if _, ok := cmd.numSet.(imap.UIDSet); ok {
+				return uid != 0 && cmd.recvUID(uid)
 			} else {
-				num = seqNum
-			}
-			if num == 0 || !cmd.seqSet.Contains(num) || cmd.recvNumSet.Contains(num) {
-				return false
+				return seqNum != 0 && cmd.recvSeqNum(seqNum)
 			}
-			cmd.recvNumSet.AddNum(num)
-
-			return true
 		})
 		if cmd != nil {
 			cmd := cmd.(*FetchCommand)
diff --git a/imapclient/move.go b/imapclient/move.go
index 446a94a..610f7b9 100644
--- a/imapclient/move.go
+++ b/imapclient/move.go
@@ -2,9 +2,14 @@ package imapclient
 
 import (
 	"github.com/emersion/go-imap/v2"
+	"github.com/emersion/go-imap/v2/internal/imapwire"
 )
 
-func (c *Client) move(uid bool, seqSet imap.NumSet, mailbox string) *MoveCommand {
+// Move sends a MOVE command.
+//
+// If the server doesn't support IMAP4rev2 nor the MOVE extension, a fallback
+// with COPY + STORE + EXPUNGE commands is used.
+func (c *Client) Move(numSet imap.NumSet, mailbox string) *MoveCommand {
 	// If the server doesn't support MOVE, fallback to [UID] COPY,
 	// [UID] STORE +FLAGS.SILENT \Deleted and [UID] EXPUNGE
 	cmdName := "MOVE"
@@ -13,18 +18,18 @@ func (c *Client) move(uid bool, seqSet imap.NumSet, mailbox string) *MoveCommand
 	}
 
 	cmd := &MoveCommand{}
-	enc := c.beginCommand(uidCmdName(cmdName, uid), cmd)
-	enc.SP().NumSet(seqSet).SP().Mailbox(mailbox)
+	enc := c.beginCommand(uidCmdName(cmdName, imapwire.NumSetKind(numSet)), cmd)
+	enc.SP().NumSet(numSet).SP().Mailbox(mailbox)
 	enc.end()
 
 	if cmdName == "COPY" {
-		cmd.store = c.store(uid, seqSet, &imap.StoreFlags{
+		cmd.store = c.Store(numSet, &imap.StoreFlags{
 			Op:     imap.StoreFlagsAdd,
 			Silent: true,
 			Flags:  []imap.Flag{imap.FlagDeleted},
 		}, nil)
-		if uid && c.Caps().Has(imap.CapUIDPlus) {
-			cmd.expunge = c.UIDExpunge(seqSet)
+		if uidSet, ok := numSet.(imap.UIDSet); ok && c.Caps().Has(imap.CapUIDPlus) {
+			cmd.expunge = c.UIDExpunge(uidSet)
 		} else {
 			cmd.expunge = c.Expunge()
 		}
@@ -33,21 +38,6 @@ func (c *Client) move(uid bool, seqSet imap.NumSet, mailbox string) *MoveCommand
 	return cmd
 }
 
-// Move sends a MOVE command.
-//
-// If the server doesn't support IMAP4rev2 nor the MOVE extension, a fallback
-// with COPY + STORE + EXPUNGE commands is used.
-func (c *Client) Move(seqSet imap.NumSet, mailbox string) *MoveCommand {
-	return c.move(false, seqSet, mailbox)
-}
-
-// UIDMove sends a UID MOVE command.
-//
-// See Move.
-func (c *Client) UIDMove(seqSet imap.NumSet, mailbox string) *MoveCommand {
-	return c.move(true, seqSet, mailbox)
-}
-
 // MoveCommand is a MOVE command.
 type MoveCommand struct {
 	cmd
diff --git a/imapclient/search.go b/imapclient/search.go
index ea38312..b70518c 100644
--- a/imapclient/search.go
+++ b/imapclient/search.go
@@ -32,7 +32,7 @@ func returnSearchOptions(options *imap.SearchOptions) []string {
 	return l
 }
 
-func (c *Client) search(uid bool, criteria *imap.SearchCriteria, options *imap.SearchOptions) *SearchCommand {
+func (c *Client) search(numKind imapwire.NumKind, criteria *imap.SearchCriteria, options *imap.SearchOptions) *SearchCommand {
 	// The IMAP4rev2 SEARCH charset defaults to UTF-8. For IMAP4rev1 the
 	// default is undefined and only US-ASCII support is required. What's more,
 	// some servers completely reject the CHARSET keyword. So, let's check if
@@ -46,8 +46,17 @@ func (c *Client) search(uid bool, criteria *imap.SearchCriteria, options *imap.S
 		charset = "UTF-8"
 	}
 
+	var all imap.NumSet
+	switch numKind {
+	case imapwire.NumKindSeq:
+		all = imap.SeqSet(nil)
+	case imapwire.NumKindUID:
+		all = imap.UIDSet(nil)
+	}
+
 	cmd := &SearchCommand{}
-	enc := c.beginCommand(uidCmdName("SEARCH", uid), cmd)
+	cmd.data.All = all
+	enc := c.beginCommand(uidCmdName("SEARCH", numKind), cmd)
 	if returnOpts := returnSearchOptions(options); len(returnOpts) > 0 {
 		enc.SP().Atom("RETURN").SP().List(len(returnOpts), func(i int) {
 			enc.Atom(returnOpts[i])
@@ -64,12 +73,12 @@ func (c *Client) search(uid bool, criteria *imap.SearchCriteria, options *imap.S
 
 // Search sends a SEARCH command.
 func (c *Client) Search(criteria *imap.SearchCriteria, options *imap.SearchOptions) *SearchCommand {
-	return c.search(false, criteria, options)
+	return c.search(imapwire.NumKindSeq, criteria, options)
 }
 
 // UIDSearch sends a UID SEARCH command.
 func (c *Client) UIDSearch(criteria *imap.SearchCriteria, options *imap.SearchOptions) *SearchCommand {
-	return c.search(true, criteria, options)
+	return c.search(imapwire.NumKindUID, criteria, options)
 }
 
 func (c *Client) handleSearch() error {
@@ -97,7 +106,14 @@ func (c *Client) handleSearch() error {
 			return c.dec.Err()
 		}
 		if cmd != nil {
-			cmd.data.All.AddNum(num)
+			switch all := cmd.data.All.(type) {
+			case imap.SeqSet:
+				all.AddNum(num)
+				cmd.data.All = all
+			case imap.UIDSet:
+				all.AddNum(imap.UID(num))
+				cmd.data.All = all
+			}
 		}
 	}
 	return nil
@@ -154,8 +170,8 @@ func writeSearchKey(enc *imapwire.Encoder, criteria *imap.SearchCriteria) {
 	for _, seqSet := range criteria.SeqNum {
 		encodeItem().NumSet(seqSet)
 	}
-	for _, seqSet := range criteria.UID {
-		encodeItem().Atom("UID").SP().NumSet(seqSet)
+	for _, uidSet := range criteria.UID {
+		encodeItem().Atom("UID").SP().NumSet(uidSet)
 	}
 
 	if !criteria.Since.IsZero() && !criteria.Before.IsZero() && criteria.Before.Sub(criteria.Since) == 24*time.Hour {
@@ -296,7 +312,11 @@ func readESearchResponse(dec *imapwire.Decoder) (tag string, data *imap.SearchDa
 			}
 			data.Max = num
 		case "ALL":
-			if !dec.ExpectNumSet(&data.All) {
+			numKind := imapwire.NumKindSeq
+			if data.UID {
+				numKind = imapwire.NumKindUID
+			}
+			if !dec.ExpectNumSet(numKind, &data.All) {
 				return "", nil, dec.Err()
 			}
 			if data.All.Dynamic() {
diff --git a/imapclient/sort.go b/imapclient/sort.go
index 2f59327..e903b58 100644
--- a/imapclient/sort.go
+++ b/imapclient/sort.go
@@ -2,6 +2,7 @@ package imapclient
 
 import (
 	"github.com/emersion/go-imap/v2"
+	"github.com/emersion/go-imap/v2/internal/imapwire"
 )
 
 type SortKey string
@@ -27,9 +28,9 @@ type SortOptions struct {
 	SortCriteria   []SortCriterion
 }
 
-func (c *Client) sort(uid bool, options *SortOptions) *SortCommand {
+func (c *Client) sort(numKind imapwire.NumKind, options *SortOptions) *SortCommand {
 	cmd := &SortCommand{}
-	enc := c.beginCommand(uidCmdName("SORT", uid), cmd)
+	enc := c.beginCommand(uidCmdName("SORT", numKind), cmd)
 	enc.SP().List(len(options.SortCriteria), func(i int) {
 		criterion := options.SortCriteria[i]
 		if criterion.Reverse {
@@ -61,14 +62,14 @@ func (c *Client) handleSort() error {
 //
 // This command requires support for the SORT extension.
 func (c *Client) Sort(options *SortOptions) *SortCommand {
-	return c.sort(false, options)
+	return c.sort(imapwire.NumKindSeq, options)
 }
 
 // UIDSort sends a UID SORT command.
 //
 // See Sort.
 func (c *Client) UIDSort(options *SortOptions) *SortCommand {
-	return c.sort(true, options)
+	return c.sort(imapwire.NumKindUID, options)
 }
 
 // SortCommand is a SORT command.
diff --git a/imapclient/store.go b/imapclient/store.go
index f986e13..a8be6d1 100644
--- a/imapclient/store.go
+++ b/imapclient/store.go
@@ -4,16 +4,21 @@ import (
 	"fmt"
 
 	"github.com/emersion/go-imap/v2"
+	"github.com/emersion/go-imap/v2/internal/imapwire"
 )
 
-func (c *Client) store(uid bool, seqSet imap.NumSet, store *imap.StoreFlags, options *imap.StoreOptions) *FetchCommand {
+// Store sends a STORE command.
+//
+// Unless StoreFlags.Silent is set, the server will return the updated values.
+//
+// A nil options pointer is equivalent to a zero options value.
+func (c *Client) Store(numSet imap.NumSet, store *imap.StoreFlags, options *imap.StoreOptions) *FetchCommand {
 	cmd := &FetchCommand{
-		uid:    uid,
-		seqSet: seqSet,
+		numSet: numSet,
 		msgs:   make(chan *FetchMessageData, 128),
 	}
-	enc := c.beginCommand(uidCmdName("STORE", uid), cmd)
-	enc.SP().NumSet(seqSet).SP()
+	enc := c.beginCommand(uidCmdName("STORE", imapwire.NumSetKind(numSet)), cmd)
+	enc.SP().NumSet(numSet).SP()
 	if options != nil && options.UnchangedSince != 0 {
 		enc.Special('(').Atom("UNCHANGEDSINCE").SP().ModSeq(options.UnchangedSince).Special(')').SP()
 	}
@@ -37,19 +42,3 @@ func (c *Client) store(uid bool, seqSet imap.NumSet, store *imap.StoreFlags, opt
 	enc.end()
 	return cmd
 }
-
-// Store sends a STORE command.
-//
-// Unless StoreFlags.Silent is set, the server will return the updated values.
-//
-// A nil options pointer is equivalent to a zero options value.
-func (c *Client) Store(seqSet imap.NumSet, store *imap.StoreFlags, options *imap.StoreOptions) *FetchCommand {
-	return c.store(false, seqSet, store, options)
-}
-
-// UIDStore sends a UID STORE command.
-//
-// See Store.
-func (c *Client) UIDStore(seqSet imap.NumSet, store *imap.StoreFlags, options *imap.StoreOptions) *FetchCommand {
-	return c.store(true, seqSet, store, options)
-}
diff --git a/imapclient/thread.go b/imapclient/thread.go
index 098d63b..a2f8af8 100644
--- a/imapclient/thread.go
+++ b/imapclient/thread.go
@@ -13,9 +13,9 @@ type ThreadOptions struct {
 	SearchCriteria *imap.SearchCriteria
 }
 
-func (c *Client) thread(uid bool, options *ThreadOptions) *ThreadCommand {
+func (c *Client) thread(numKind imapwire.NumKind, options *ThreadOptions) *ThreadCommand {
 	cmd := &ThreadCommand{}
-	enc := c.beginCommand(uidCmdName("THREAD", uid), cmd)
+	enc := c.beginCommand(uidCmdName("THREAD", numKind), cmd)
 	enc.SP().Atom(string(options.Algorithm)).SP().Atom("UTF-8").SP()
 	writeSearchKey(enc.Encoder, options.SearchCriteria)
 	enc.end()
@@ -26,14 +26,14 @@ func (c *Client) thread(uid bool, options *ThreadOptions) *ThreadCommand {
 //
 // This command requires support for the THREAD extension.
 func (c *Client) Thread(options *ThreadOptions) *ThreadCommand {
-	return c.thread(false, options)
+	return c.thread(imapwire.NumKindSeq, options)
 }
 
 // UIDThread sends a UID THREAD command.
 //
 // See Thread.
 func (c *Client) UIDThread(options *ThreadOptions) *ThreadCommand {
-	return c.thread(true, options)
+	return c.thread(imapwire.NumKindUID, options)
 }
 
 func (c *Client) handleThread() error {
diff --git a/imapserver/copy.go b/imapserver/copy.go
index c01864b..5c933a2 100644
--- a/imapserver/copy.go
+++ b/imapserver/copy.go
@@ -6,14 +6,14 @@ import (
 )
 
 func (c *Conn) handleCopy(tag string, dec *imapwire.Decoder, numKind NumKind) error {
-	seqSet, dest, err := readCopy(dec)
+	numSet, dest, err := readCopy(numKind, dec)
 	if err != nil {
 		return err
 	}
 	if err := c.checkState(imap.ConnStateSelected); err != nil {
 		return err
 	}
-	data, err := c.session.Copy(numKind, seqSet, dest)
+	data, err := c.session.Copy(numSet, dest)
 	if err != nil {
 		return err
 	}
@@ -47,9 +47,9 @@ func (c *Conn) writeCopyOK(tag string, data *imap.CopyData) error {
 	return enc.CRLF()
 }
 
-func readCopy(dec *imapwire.Decoder) (seqSet imap.NumSet, dest string, err error) {
-	if !dec.ExpectSP() || !dec.ExpectNumSet(&seqSet) || !dec.ExpectSP() || !dec.ExpectMailbox(&dest) || !dec.ExpectCRLF() {
+func readCopy(numKind NumKind, dec *imapwire.Decoder) (numSet imap.NumSet, dest string, err error) {
+	if !dec.ExpectSP() || !dec.ExpectNumSet(numKind.wire(), &numSet) || !dec.ExpectSP() || !dec.ExpectMailbox(&dest) || !dec.ExpectCRLF() {
 		return nil, "", dec.Err()
 	}
-	return seqSet, dest, nil
+	return numSet, dest, nil
 }
diff --git a/imapserver/expunge.go b/imapserver/expunge.go
index 78549d7..3e4d71b 100644
--- a/imapserver/expunge.go
+++ b/imapserver/expunge.go
@@ -13,14 +13,14 @@ func (c *Conn) handleExpunge(dec *imapwire.Decoder) error {
 }
 
 func (c *Conn) handleUIDExpunge(dec *imapwire.Decoder) error {
-	var seqSet imap.NumSet
-	if !dec.ExpectSP() || !dec.ExpectNumSet(&seqSet) || !dec.ExpectCRLF() {
+	var uidSet imap.UIDSet
+	if !dec.ExpectSP() || !dec.ExpectUIDSet(&uidSet) || !dec.ExpectCRLF() {
 		return dec.Err()
 	}
-	return c.expunge(&seqSet)
+	return c.expunge(&uidSet)
 }
 
-func (c *Conn) expunge(uids *imap.NumSet) error {
+func (c *Conn) expunge(uids *imap.UIDSet) error {
 	if err := c.checkState(imap.ConnStateSelected); err != nil {
 		return err
 	}
diff --git a/imapserver/fetch.go b/imapserver/fetch.go
index 73b5933..a2f42a7 100644
--- a/imapserver/fetch.go
+++ b/imapserver/fetch.go
@@ -24,8 +24,8 @@ type fetchWriterOptions struct {
 }
 
 func (c *Conn) handleFetch(dec *imapwire.Decoder, numKind NumKind) error {
-	var seqSet imap.NumSet
-	if !dec.ExpectSP() || !dec.ExpectNumSet(&seqSet) || !dec.ExpectSP() {
+	var numSet imap.NumSet
+	if !dec.ExpectSP() || !dec.ExpectNumSet(numKind.wire(), &numSet) || !dec.ExpectSP() {
 		return dec.Err()
 	}
 
@@ -88,7 +88,7 @@ func (c *Conn) handleFetch(dec *imapwire.Decoder, numKind NumKind) error {
 	}
 
 	w := &FetchWriter{conn: c, options: writerOptions}
-	if err := c.session.Fetch(w, numKind, seqSet, &options); err != nil {
+	if err := c.session.Fetch(w, numSet, &options); err != nil {
 		return err
 	}
 	return nil
diff --git a/imapserver/imapmemserver/mailbox.go b/imapserver/imapmemserver/mailbox.go
index 33a861d..120e8c9 100644
--- a/imapserver/imapmemserver/mailbox.go
+++ b/imapserver/imapmemserver/mailbox.go
@@ -203,11 +203,11 @@ func (mbox *Mailbox) flagsLocked() []imap.Flag {
 	return l
 }
 
-func (mbox *Mailbox) Expunge(w *imapserver.ExpungeWriter, uids *imap.NumSet) error {
+func (mbox *Mailbox) Expunge(w *imapserver.ExpungeWriter, uids *imap.UIDSet) error {
 	expunged := make(map[*message]struct{})
 	mbox.mutex.Lock()
 	for _, msg := range mbox.l {
-		if uids != nil && !uids.Contains(uint32(msg.uid)) {
+		if uids != nil && !uids.Contains(msg.uid) {
 			continue
 		}
 		if _, ok := msg.flags[canonicalFlag(imap.FlagDeleted)]; ok {
@@ -282,7 +282,7 @@ func (mbox *MailboxView) Close() {
 	mbox.tracker.Close()
 }
 
-func (mbox *MailboxView) Fetch(w *imapserver.FetchWriter, numKind imapserver.NumKind, seqSet imap.NumSet, options *imap.FetchOptions) error {
+func (mbox *MailboxView) Fetch(w *imapserver.FetchWriter, numSet imap.NumSet, options *imap.FetchOptions) error {
 	markSeen := false
 	for _, bs := range options.BodySection {
 		if !bs.Peek {
@@ -292,7 +292,7 @@ func (mbox *MailboxView) Fetch(w *imapserver.FetchWriter, numKind imapserver.Num
 	}
 
 	var err error
-	mbox.forEach(numKind, seqSet, func(seqNum uint32, msg *message) {
+	mbox.forEach(numSet, func(seqNum uint32, msg *message) {
 		if err != nil {
 			return
 		}
@@ -313,16 +313,18 @@ func (mbox *MailboxView) Search(numKind imapserver.NumKind, criteria *imap.Searc
 	defer mbox.mutex.Unlock()
 
 	for _, seqSet := range criteria.SeqNum {
-		mbox.staticNumSet(seqSet, imapserver.NumKindSeq)
+		mbox.staticNumSet(seqSet)
 	}
-	for _, seqSet := range criteria.UID {
-		mbox.staticNumSet(seqSet, imapserver.NumKindUID)
+	for _, uidSet := range criteria.UID {
+		mbox.staticNumSet(uidSet)
 	}
 
-	data := imap.SearchData{
-		UID: numKind == imapserver.NumKindUID,
-	}
+	data := imap.SearchData{UID: numKind == imapserver.NumKindUID}
 
+	var (
+		seqSet imap.SeqSet
+		uidSet imap.UIDSet
+	)
 	for i, msg := range mbox.l {
 		seqNum := mbox.tracker.EncodeSeqNum(uint32(i) + 1)
 
@@ -333,14 +335,15 @@ func (mbox *MailboxView) Search(numKind imapserver.NumKind, criteria *imap.Searc
 		var num uint32
 		switch numKind {
 		case imapserver.NumKindSeq:
+			if seqNum == 0 {
+				continue
+			}
+			seqSet.AddNum(seqNum)
 			num = seqNum
 		case imapserver.NumKindUID:
+			uidSet.AddNum(msg.uid)
 			num = uint32(msg.uid)
 		}
-		if num == 0 {
-			continue
-		}
-		data.All.AddNum(num)
 		if data.Min == 0 || num < data.Min {
 			data.Min = num
 		}
@@ -350,16 +353,23 @@ func (mbox *MailboxView) Search(numKind imapserver.NumKind, criteria *imap.Searc
 		data.Count++
 	}
 
+	switch numKind {
+	case imapserver.NumKindSeq:
+		data.All = seqSet
+	case imapserver.NumKindUID:
+		data.All = uidSet
+	}
+
 	return &data, nil
 }
 
-func (mbox *MailboxView) Store(w *imapserver.FetchWriter, numKind imapserver.NumKind, seqSet imap.NumSet, flags *imap.StoreFlags, options *imap.StoreOptions) error {
-	mbox.forEach(numKind, seqSet, func(seqNum uint32, msg *message) {
+func (mbox *MailboxView) Store(w *imapserver.FetchWriter, numSet imap.NumSet, flags *imap.StoreFlags, options *imap.StoreOptions) error {
+	mbox.forEach(numSet, func(seqNum uint32, msg *message) {
 		msg.store(flags)
 		mbox.Mailbox.tracker.QueueMessageFlags(seqNum, msg.uid, msg.flagList(), mbox.tracker)
 	})
 	if !flags.Silent {
-		return mbox.Fetch(w, numKind, seqSet, &imap.FetchOptions{Flags: true})
+		return mbox.Fetch(w, numSet, &imap.FetchOptions{Flags: true})
 	}
 	return nil
 }
@@ -372,28 +382,29 @@ func (mbox *MailboxView) Idle(w *imapserver.UpdateWriter, stop <-chan struct{})
 	return mbox.tracker.Idle(w, stop)
 }
 
-func (mbox *MailboxView) forEach(numKind imapserver.NumKind, seqSet imap.NumSet, f func(seqNum uint32, msg *message)) {
+func (mbox *MailboxView) forEach(numSet imap.NumSet, f func(seqNum uint32, msg *message)) {
 	mbox.mutex.Lock()
 	defer mbox.mutex.Unlock()
-	mbox.forEachLocked(numKind, seqSet, f)
+	mbox.forEachLocked(numSet, f)
 }
 
-func (mbox *MailboxView) forEachLocked(numKind imapserver.NumKind, seqSet imap.NumSet, f func(seqNum uint32, msg *message)) {
+func (mbox *MailboxView) forEachLocked(numSet imap.NumSet, f func(seqNum uint32, msg *message)) {
 	// TODO: optimize
 
-	mbox.staticNumSet(seqSet, numKind)
+	mbox.staticNumSet(numSet)
 
 	for i, msg := range mbox.l {
 		seqNum := uint32(i) + 1
 
-		var num uint32
-		switch numKind {
-		case imapserver.NumKindSeq:
-			num = mbox.tracker.EncodeSeqNum(seqNum)
-		case imapserver.NumKindUID:
-			num = uint32(msg.uid)
+		var contains bool
+		switch numSet := numSet.(type) {
+		case imap.SeqSet:
+			seqNum := mbox.tracker.EncodeSeqNum(seqNum)
+			contains = seqNum != 0 && numSet.Contains(seqNum)
+		case imap.UIDSet:
+			contains = numSet.Contains(msg.uid)
 		}
-		if num == 0 || !seqSet.Contains(num) {
+		if !contains {
 			continue
 		}
 
@@ -405,28 +416,34 @@ func (mbox *MailboxView) forEachLocked(numKind imapserver.NumKind, seqSet imap.N
 //
 // This is necessary to properly handle the special symbol "*", which
 // represents the maximum sequence number or UID in the mailbox.
-func (mbox *MailboxView) staticNumSet(seqSet imap.NumSet, numKind imapserver.NumKind) {
-	var max uint32
-	switch numKind {
-	case imapserver.NumKindSeq:
-		max = uint32(len(mbox.l))
-	case imapserver.NumKindUID:
-		max = uint32(mbox.uidNext) - 1
-	}
-
-	for i := range seqSet {
-		seq := &seqSet[i]
-		dyn := false
-		if seq.Start == 0 {
-			seq.Start = max
-			dyn = true
+func (mbox *MailboxView) staticNumSet(numSet imap.NumSet) {
+	switch numSet := numSet.(type) {
+	case imap.SeqSet:
+		max := uint32(len(mbox.l))
+		for i := range numSet {
+			r := &numSet[i]
+			staticNumRange(&r.Start, &r.Stop, max)
 		}
-		if seq.Stop == 0 {
-			seq.Stop = max
-			dyn = true
-		}
-		if dyn && seq.Start > seq.Stop {
-			seq.Start, seq.Stop = seq.Stop, seq.Start
+	case imap.UIDSet:
+		max := uint32(mbox.uidNext) - 1
+		for i := range numSet {
+			r := &numSet[i]
+			staticNumRange((*uint32)(&r.Start), (*uint32)(&r.Stop), max)
 		}
 	}
 }
+
+func staticNumRange(start, stop *uint32, max uint32) {
+	dyn := false
+	if *start == 0 {
+		*start = max
+		dyn = true
+	}
+	if *stop == 0 {
+		*stop = max
+		dyn = true
+	}
+	if dyn && *start > *stop {
+		*start, *stop = *stop, *start
+	}
+}
diff --git a/imapserver/imapmemserver/message.go b/imapserver/imapmemserver/message.go
index 5b87f50..04d1640 100644
--- a/imapserver/imapmemserver/message.go
+++ b/imapserver/imapmemserver/message.go
@@ -244,8 +244,8 @@ func (msg *message) search(seqNum uint32, criteria *imap.SearchCriteria) bool {
 			return false
 		}
 	}
-	for _, seqSet := range criteria.UID {
-		if !seqSet.Contains(uint32(msg.uid)) {
+	for _, uidSet := range criteria.UID {
+		if !uidSet.Contains(msg.uid) {
 			return false
 		}
 	}
diff --git a/imapserver/imapmemserver/session.go b/imapserver/imapmemserver/session.go
index b92fddc..70e9d2f 100644
--- a/imapserver/imapmemserver/session.go
+++ b/imapserver/imapmemserver/session.go
@@ -50,7 +50,7 @@ func (sess *UserSession) Unselect() error {
 	return nil
 }
 
-func (sess *UserSession) Copy(numKind imapserver.NumKind, seqSet imap.NumSet, destName string) (*imap.CopyData, error) {
+func (sess *UserSession) Copy(numSet imap.NumSet, destName string) (*imap.CopyData, error) {
 	dest, err := sess.user.mailbox(destName)
 	if err != nil {
 		return nil, &imap.Error{
@@ -65,11 +65,11 @@ func (sess *UserSession) Copy(numKind imapserver.NumKind, seqSet imap.NumSet, de
 		}
 	}
 
-	var sourceUIDs, destUIDs imap.NumSet
-	sess.mailbox.forEach(numKind, seqSet, func(seqNum uint32, msg *message) {
+	var sourceUIDs, destUIDs imap.UIDSet
+	sess.mailbox.forEach(numSet, func(seqNum uint32, msg *message) {
 		appendData := dest.copyMsg(msg)
-		sourceUIDs.AddNum(uint32(msg.uid))
-		destUIDs.AddNum(uint32(appendData.UID))
+		sourceUIDs.AddNum(msg.uid)
+		destUIDs.AddNum(appendData.UID)
 	})
 
 	return &imap.CopyData{
@@ -79,7 +79,7 @@ func (sess *UserSession) Copy(numKind imapserver.NumKind, seqSet imap.NumSet, de
 	}, nil
 }
 
-func (sess *UserSession) Move(w *imapserver.MoveWriter, numKind imapserver.NumKind, seqSet imap.NumSet, destName string) error {
+func (sess *UserSession) Move(w *imapserver.MoveWriter, numSet imap.NumSet, destName string) error {
 	dest, err := sess.user.mailbox(destName)
 	if err != nil {
 		return &imap.Error{
@@ -97,12 +97,12 @@ func (sess *UserSession) Move(w *imapserver.MoveWriter, numKind imapserver.NumKi
 	sess.mailbox.mutex.Lock()
 	defer sess.mailbox.mutex.Unlock()
 
-	var sourceUIDs, destUIDs imap.NumSet
+	var sourceUIDs, destUIDs imap.UIDSet
 	expunged := make(map[*message]struct{})
-	sess.mailbox.forEachLocked(numKind, seqSet, func(seqNum uint32, msg *message) {
+	sess.mailbox.forEachLocked(numSet, func(seqNum uint32, msg *message) {
 		appendData := dest.copyMsg(msg)
-		sourceUIDs.AddNum(uint32(msg.uid))
-		destUIDs.AddNum(uint32(appendData.UID))
+		sourceUIDs.AddNum(msg.uid)
+		destUIDs.AddNum(appendData.UID)
 		expunged[msg] = struct{}{}
 	})
 	seqNums := sess.mailbox.expungeLocked(expunged)
diff --git a/imapserver/move.go b/imapserver/move.go
index cb29925..1305a31 100644
--- a/imapserver/move.go
+++ b/imapserver/move.go
@@ -6,7 +6,7 @@ import (
 )
 
 func (c *Conn) handleMove(dec *imapwire.Decoder, numKind NumKind) error {
-	seqSet, dest, err := readCopy(dec)
+	numSet, dest, err := readCopy(numKind, dec)
 	if err != nil {
 		return err
 	}
@@ -18,7 +18,7 @@ func (c *Conn) handleMove(dec *imapwire.Decoder, numKind NumKind) error {
 		return newClientBugError("MOVE is not supported")
 	}
 	w := &MoveWriter{conn: c}
-	return session.Move(w, numKind, seqSet, dest)
+	return session.Move(w, numSet, dest)
 }
 
 // MoveWriter writes responses for the MOVE command.
diff --git a/imapserver/search.go b/imapserver/search.go
index 95ad0d5..f2cf42e 100644
--- a/imapserver/search.go
+++ b/imapserver/search.go
@@ -103,7 +103,7 @@ func (c *Conn) writeESearch(tag string, data *imap.SearchData, options *imap.Sea
 	if data.UID {
 		enc.SP().Atom("UID")
 	}
-	if options.ReturnAll && len(data.All) > 0 {
+	if options.ReturnAll && data.All != nil {
 		enc.SP().Atom("ALL").SP().NumSet(data.All)
 	}
 	if options.ReturnMin && data.Min > 0 {
@@ -118,19 +118,29 @@ func (c *Conn) writeESearch(tag string, data *imap.SearchData, options *imap.Sea
 	return enc.CRLF()
 }
 
-func (c *Conn) writeSearch(seqSet imap.NumSet) error {
+func (c *Conn) writeSearch(numSet imap.NumSet) error {
 	enc := newResponseEncoder(c)
 	defer enc.end()
 
-	nums, ok := seqSet.Nums()
+	enc.Atom("*").SP().Atom("SEARCH")
+	var ok bool
+	switch numSet := numSet.(type) {
+	case imap.SeqSet:
+		var nums []uint32
+		nums, ok = numSet.Nums()
+		for _, num := range nums {
+			enc.SP().Number(num)
+		}
+	case imap.UIDSet:
+		var uids []imap.UID
+		uids, ok = numSet.Nums()
+		for _, uid := range uids {
+			enc.SP().UID(uid)
+		}
+	}
 	if !ok {
 		return fmt.Errorf("imapserver: failed to enumerate message numbers in SEARCH response")
 	}
-
-	enc.Atom("*").SP().Atom("SEARCH")
-	for _, num := range nums {
-		enc.SP().Number(num)
-	}
 	return enc.CRLF()
 }
 
@@ -181,11 +191,11 @@ func readSearchKeyWithAtom(criteria *imap.SearchCriteria, dec *imapwire.Decoder,
 	case "ALL":
 		// nothing to do
 	case "UID":
-		var seqSet imap.NumSet
-		if !dec.ExpectSP() || !dec.ExpectNumSet(&seqSet) {
+		var uidSet imap.UIDSet
+		if !dec.ExpectSP() || !dec.ExpectUIDSet(&uidSet) {
 			return dec.Err()
 		}
-		criteria.UID = append(criteria.UID, seqSet)
+		criteria.UID = append(criteria.UID, uidSet)
 	case "ANSWERED", "DELETED", "DRAFT", "FLAGGED", "RECENT", "SEEN":
 		criteria.Flag = append(criteria.Flag, searchKeyFlag(key))
 	case "UNANSWERED", "UNDELETED", "UNDRAFT", "UNFLAGGED", "UNSEEN":
@@ -302,7 +312,7 @@ func readSearchKeyWithAtom(criteria *imap.SearchCriteria, dec *imapwire.Decoder,
 		}
 		criteria.Or = append(criteria.Or, or)
 	default:
-		seqSet, err := imapwire.ParseNumSet(key)
+		seqSet, err := imapwire.ParseSeqSet(key)
 		if err != nil {
 			return err
 		}
diff --git a/imapserver/session.go b/imapserver/session.go
index 5476430..873bdef 100644
--- a/imapserver/session.go
+++ b/imapserver/session.go
@@ -4,6 +4,7 @@ import (
 	"fmt"
 
 	"github.com/emersion/go-imap/v2"
+	"github.com/emersion/go-imap/v2/internal/imapwire"
 	"github.com/emersion/go-sasl"
 )
 
@@ -26,8 +27,8 @@ type GreetingData struct {
 type NumKind int
 
 const (
-	NumKindSeq NumKind = 1 + iota
-	NumKindUID
+	NumKindSeq = NumKind(imapwire.NumKindSeq)
+	NumKindUID = NumKind(imapwire.NumKindUID)
 )
 
 // String implements fmt.Stringer.
@@ -42,6 +43,10 @@ func (kind NumKind) String() string {
 	}
 }
 
+func (kind NumKind) wire() imapwire.NumKind {
+	return imapwire.NumKind(kind)
+}
+
 // Session is an IMAP session.
 type Session interface {
 	Close() error
@@ -64,11 +69,11 @@ type Session interface {
 
 	// Selected state
 	Unselect() error
-	Expunge(w *ExpungeWriter, uids *imap.NumSet) error
+	Expunge(w *ExpungeWriter, uids *imap.UIDSet) error
 	Search(kind NumKind, criteria *imap.SearchCriteria, options *imap.SearchOptions) (*imap.SearchData, error)
-	Fetch(w *FetchWriter, kind NumKind, seqSet imap.NumSet, options *imap.FetchOptions) error
-	Store(w *FetchWriter, kind NumKind, seqSet imap.NumSet, flags *imap.StoreFlags, options *imap.StoreOptions) error
-	Copy(kind NumKind, seqSet imap.NumSet, dest string) (*imap.CopyData, error)
+	Fetch(w *FetchWriter, numSet imap.NumSet, options *imap.FetchOptions) error
+	Store(w *FetchWriter, numSet imap.NumSet, flags *imap.StoreFlags, options *imap.StoreOptions) error
+	Copy(numSet imap.NumSet, dest string) (*imap.CopyData, error)
 }
 
 // SessionNamespace is an IMAP session which supports NAMESPACE.
@@ -84,7 +89,7 @@ type SessionMove interface {
 	Session
 
 	// Selected state
-	Move(w *MoveWriter, kind NumKind, seqSet imap.NumSet, dest string) error
+	Move(w *MoveWriter, numSet imap.NumSet, dest string) error
 }
 
 // SessionIMAP4rev2 is an IMAP session which supports IMAP4rev2.
diff --git a/imapserver/store.go b/imapserver/store.go
index 2b7704c..848fac5 100644
--- a/imapserver/store.go
+++ b/imapserver/store.go
@@ -10,10 +10,10 @@ import (
 
 func (c *Conn) handleStore(dec *imapwire.Decoder, numKind NumKind) error {
 	var (
-		seqSet imap.NumSet
+		numSet imap.NumSet
 		item   string
 	)
-	if !dec.ExpectSP() || !dec.ExpectNumSet(&seqSet) || !dec.ExpectSP() || !dec.ExpectAtom(&item) || !dec.ExpectSP() {
+	if !dec.ExpectSP() || !dec.ExpectNumSet(numKind.wire(), &numSet) || !dec.ExpectSP() || !dec.ExpectAtom(&item) || !dec.ExpectSP() {
 		return dec.Err()
 	}
 	var flags []imap.Flag
@@ -70,7 +70,7 @@ func (c *Conn) handleStore(dec *imapwire.Decoder, numKind NumKind) error {
 
 	w := &FetchWriter{conn: c}
 	options := imap.StoreOptions{}
-	return c.session.Store(w, numKind, seqSet, &imap.StoreFlags{
+	return c.session.Store(w, numSet, &imap.StoreFlags{
 		Op:     op,
 		Silent: silent,
 		Flags:  flags,
diff --git a/internal/imapnum/numset.go b/internal/imapnum/numset.go
new file mode 100644
index 0000000..25a4f29
--- /dev/null
+++ b/internal/imapnum/numset.go
@@ -0,0 +1,306 @@
+package imapnum
+
+import (
+	"fmt"
+	"strconv"
+	"strings"
+)
+
+// Range represents a single seq-number or seq-range value (RFC 3501 ABNF). Values
+// may be static (e.g. "1", "2:4") or dynamic (e.g. "*", "1:*"). A seq-number is
+// represented by setting Start = Stop. Zero is used to represent "*", which is
+// safe because seq-number uses nz-number rule. The order of values is always
+// Start <= Stop, except when representing "n:*", where Start = n and Stop = 0.
+type Range struct {
+	Start, Stop uint32
+}
+
+// Contains returns true if the seq-number q is contained in range value s.
+// The dynamic value "*" contains only other "*" values, the dynamic range "n:*"
+// contains "*" and all numbers >= n.
+func (s Range) Contains(q uint32) bool {
+	if q == 0 {
+		return s.Stop == 0 // "*" is contained only in "*" and "n:*"
+	}
+	return s.Start != 0 && s.Start <= q && (q <= s.Stop || s.Stop == 0)
+}
+
+// Less returns true if s precedes and does not contain seq-number q.
+func (s Range) Less(q uint32) bool {
+	return (s.Stop < q || q == 0) && s.Stop != 0
+}
+
+// Merge combines range values s and t into a single union if the two
+// intersect or one is a superset of the other. The order of s and t does not
+// matter. If the values cannot be merged, s is returned unmodified and ok is
+// set to false.
+func (s Range) Merge(t Range) (union Range, ok bool) {
+	union = s
+	if s == t {
+		return s, true
+	}
+	if s.Start != 0 && t.Start != 0 {
+		// s and t are any combination of "n", "n:m", or "n:*"
+		if s.Start > t.Start {
+			s, t = t, s
+		}
+		// s starts at or before t, check where it ends
+		if (s.Stop >= t.Stop && t.Stop != 0) || s.Stop == 0 {
+			return s, true // s is a superset of t
+		}
+		// s is "n" or "n:m", if m == ^uint32(0) then t is "n:*"
+		if s.Stop+1 >= t.Start || s.Stop == ^uint32(0) {
+			return Range{s.Start, t.Stop}, true // s intersects or touches t
+		}
+		return union, false
+	}
+	// exactly one of s and t is "*"
+	if s.Start == 0 {
+		if t.Stop == 0 {
+			return t, true // s is "*", t is "n:*"
+		}
+	} else if s.Stop == 0 {
+		return s, true // s is "n:*", t is "*"
+	}
+	return union, false
+}
+
+// String returns range value s as a seq-number or seq-range string.
+func (s Range) String() string {
+	if s.Start == s.Stop {
+		if s.Start == 0 {
+			return "*"
+		}
+		return strconv.FormatUint(uint64(s.Start), 10)
+	}
+	b := strconv.AppendUint(make([]byte, 0, 24), uint64(s.Start), 10)
+	if s.Stop == 0 {
+		return string(append(b, ':', '*'))
+	}
+	return string(strconv.AppendUint(append(b, ':'), uint64(s.Stop), 10))
+}
+
+func (s Range) append(nums []uint32) (out []uint32, ok bool) {
+	if s.Start == 0 || s.Stop == 0 {
+		return nil, false
+	}
+	for n := s.Start; n <= s.Stop; n++ {
+		nums = append(nums, n)
+	}
+	return nums, true
+}
+
+// Set is used to represent a set of message sequence numbers or UIDs (see
+// sequence-set ABNF rule). The zero value is an empty set.
+type Set []Range
+
+// AddNum inserts new numbers into the set. The value 0 represents "*".
+func (s *Set) AddNum(q ...uint32) {
+	for _, v := range q {
+		s.insert(Range{v, v})
+	}
+}
+
+// AddRange inserts a new range into the set.
+func (s *Set) AddRange(start, stop uint32) {
+	if (stop < start && stop != 0) || start == 0 {
+		s.insert(Range{stop, start})
+	} else {
+		s.insert(Range{start, stop})
+	}
+}
+
+// AddSet inserts all values from t into s.
+func (s *Set) AddSet(t Set) {
+	for _, v := range t {
+		s.insert(v)
+	}
+}
+
+// Dynamic returns true if the set contains "*" or "n:*" values.
+func (s Set) Dynamic() bool {
+	return len(s) > 0 && s[len(s)-1].Stop == 0
+}
+
+// Contains returns true if the non-zero sequence number or UID q is contained
+// in the set. The dynamic range "n:*" contains all q >= n. It is the caller's
+// responsibility to handle the special case where q is the maximum UID in the
+// mailbox and q < n (i.e. the set cannot match UIDs against "*:n" or "*" since
+// it doesn't know what the maximum value is).
+func (s Set) Contains(q uint32) bool {
+	if _, ok := s.search(q); ok {
+		return q != 0
+	}
+	return false
+}
+
+// Nums returns a slice of all numbers contained in the set.
+func (s Set) Nums() (nums []uint32, ok bool) {
+	for _, v := range s {
+		nums, ok = v.append(nums)
+		if !ok {
+			return nil, false
+		}
+	}
+	return nums, true
+}
+
+// String returns a sorted representation of all contained number values.
+func (s Set) String() string {
+	if len(s) == 0 {
+		return ""
+	}
+	b := make([]byte, 0, 64)
+	for _, v := range s {
+		b = append(b, ',')
+		if v.Start == 0 {
+			b = append(b, '*')
+			continue
+		}
+		b = strconv.AppendUint(b, uint64(v.Start), 10)
+		if v.Start != v.Stop {
+			if v.Stop == 0 {
+				b = append(b, ':', '*')
+				continue
+			}
+			b = strconv.AppendUint(append(b, ':'), uint64(v.Stop), 10)
+		}
+	}
+	return string(b[1:])
+}
+
+// insert adds range value v to the set.
+func (ptr *Set) insert(v Range) {
+	s := *ptr
+	defer func() {
+		*ptr = s
+	}()
+
+	i, _ := s.search(v.Start)
+	merged := false
+	if i > 0 {
+		// try merging with the preceding entry (e.g. "1,4".insert(2), i == 1)
+		s[i-1], merged = s[i-1].Merge(v)
+	}
+	if i == len(s) {
+		// v was either merged with the last entry or needs to be appended
+		if !merged {
+			s.insertAt(i, v)
+		}
+		return
+	} else if merged {
+		i--
+	} else if s[i], merged = s[i].Merge(v); !merged {
+		s.insertAt(i, v) // insert in the middle (e.g. "1,5".insert(3), i == 1)
+		return
+	}
+	// v was merged with s[i], continue trying to merge until the end
+	for j := i + 1; j < len(s); j++ {
+		if s[i], merged = s[i].Merge(s[j]); !merged {
+			if j > i+1 {
+				// cut out all entries between i and j that were merged
+				s = append(s[:i+1], s[j:]...)
+			}
+			return
+		}
+	}
+	// everything after s[i] was merged
+	s = s[:i+1]
+}
+
+// insertAt inserts a new range value v at index i, resizing s.Set as needed.
+func (ptr *Set) insertAt(i int, v Range) {
+	s := *ptr
+	defer func() {
+		*ptr = s
+	}()
+
+	if n := len(s); i == n {
+		// insert at the end
+		s = append(s, v)
+		return
+	} else if n < cap(s) {
+		// enough space, shift everything at and after i to the right
+		s = s[:n+1]
+		copy(s[i+1:], s[i:])
+	} else {
+		// allocate new slice and copy everything, n is at least 1
+		set := make([]Range, n+1, n*2)
+		copy(set, s[:i])
+		copy(set[i+1:], s[i:])
+		s = set
+	}
+	s[i] = v
+}
+
+// search attempts to find the index of the range set value that contains q.
+// If no values contain q, the returned index is the position where q should be
+// inserted and ok is set to false.
+func (s Set) search(q uint32) (i int, ok bool) {
+	min, max := 0, len(s)-1
+	for min < max {
+		if mid := (min + max) >> 1; s[mid].Less(q) {
+			min = mid + 1
+		} else {
+			max = mid
+		}
+	}
+	if max < 0 || s[min].Less(q) {
+		return len(s), false // q is the new largest value
+	}
+	return min, s[min].Contains(q)
+}
+
+// errBadNumSet is used to report problems with the format of a number set
+// value.
+type errBadNumSet string
+
+func (err errBadNumSet) Error() string {
+	return fmt.Sprintf("imap: bad number set value %q", string(err))
+}
+
+// parseNum parses a single seq-number value (non-zero uint32 or "*").
+func parseNum(v string) (uint32, error) {
+	if n, err := strconv.ParseUint(v, 10, 32); err == nil && v[0] != '0' {
+		return uint32(n), nil
+	} else if v == "*" {
+		return 0, nil
+	}
+	return 0, errBadNumSet(v)
+}
+
+// parseNumRange creates a new seq instance by parsing strings in the format
+// "n" or "n:m", where n and/or m may be "*". An error is returned for invalid
+// values.
+func parseNumRange(v string) (Range, error) {
+	var (
+		r   Range
+		err error
+	)
+	if sep := strings.IndexRune(v, ':'); sep < 0 {
+		r.Start, err = parseNum(v)
+		r.Stop = r.Start
+		return r, err
+	} else if r.Start, err = parseNum(v[:sep]); err == nil {
+		if r.Stop, err = parseNum(v[sep+1:]); err == nil {
+			if (r.Stop < r.Start && r.Stop != 0) || r.Start == 0 {
+				r.Start, r.Stop = r.Stop, r.Start
+			}
+			return r, nil
+		}
+	}
+	return r, errBadNumSet(v)
+}
+
+// ParseSet returns a new Set after parsing the set string.
+func ParseSet(set string) (Set, error) {
+	var s Set
+	for _, sv := range strings.Split(set, ",") {
+		r, err := parseNumRange(sv)
+		if err != nil {
+			return s, err
+		}
+		s.AddRange(r.Start, r.Stop)
+	}
+	return s, nil
+}
diff --git a/internal/imapwire/decoder.go b/internal/imapwire/decoder.go
index 3dfe8e2..6b0a980 100644
--- a/internal/imapwire/decoder.go
+++ b/internal/imapwire/decoder.go
@@ -9,6 +9,7 @@ import (
 	"unicode"
 
 	"github.com/emersion/go-imap/v2"
+	"github.com/emersion/go-imap/v2/internal/imapnum"
 	"github.com/emersion/go-imap/v2/internal/utf7"
 )
 
@@ -487,7 +488,7 @@ func (dec *Decoder) ExpectUID(ptr *imap.UID) bool {
 	return true
 }
 
-func (dec *Decoder) ExpectNumSet(ptr *imap.NumSet) bool {
+func (dec *Decoder) ExpectNumSet(kind NumKind, ptr *imap.NumSet) bool {
 	if dec.Special('$') {
 		*ptr = imap.SearchRes()
 		return true
@@ -497,11 +498,27 @@ func (dec *Decoder) ExpectNumSet(ptr *imap.NumSet) bool {
 	if !dec.Expect(dec.Func(&s, isNumSetChar), "sequence-set") {
 		return false
 	}
-	seqSet, err := ParseNumSet(s)
-	if err == nil {
-		*ptr = seqSet
+	numSet, err := imapnum.ParseSet(s)
+	if err != nil {
+		return dec.returnErr(err)
 	}
-	return dec.returnErr(err)
+
+	switch kind {
+	case NumKindSeq:
+		*ptr = seqSetFromNumSet(numSet)
+	case NumKindUID:
+		*ptr = uidSetFromNumSet(numSet)
+	}
+	return true
+}
+
+func (dec *Decoder) ExpectUIDSet(ptr *imap.UIDSet) bool {
+	var numSet imap.NumSet
+	ok := dec.ExpectNumSet(NumKindUID, &numSet)
+	if ok {
+		*ptr = numSet.(imap.UIDSet)
+	}
+	return ok
 }
 
 func isNumSetChar(ch byte) bool {
diff --git a/internal/imapwire/encoder.go b/internal/imapwire/encoder.go
index 1166f41..2891b4b 100644
--- a/internal/imapwire/encoder.go
+++ b/internal/imapwire/encoder.go
@@ -158,8 +158,8 @@ func (enc *Encoder) Mailbox(name string) *Encoder {
 	}
 }
 
-func (enc *Encoder) NumSet(seqSet imap.NumSet) *Encoder {
-	s := seqSet.String()
+func (enc *Encoder) NumSet(numSet imap.NumSet) *Encoder {
+	s := numSet.String()
 	if s == "" {
 		enc.setErr(fmt.Errorf("imapwire: cannot encode empty sequence set"))
 		return enc
diff --git a/internal/imapwire/num.go b/internal/imapwire/num.go
new file mode 100644
index 0000000..270afe1
--- /dev/null
+++ b/internal/imapwire/num.go
@@ -0,0 +1,39 @@
+package imapwire
+
+import (
+	"unsafe"
+
+	"github.com/emersion/go-imap/v2"
+	"github.com/emersion/go-imap/v2/internal/imapnum"
+)
+
+type NumKind int
+
+const (
+	NumKindSeq NumKind = iota + 1
+	NumKindUID
+)
+
+func seqSetFromNumSet(s imapnum.Set) imap.SeqSet {
+	return *(*imap.SeqSet)(unsafe.Pointer(&s))
+}
+
+func uidSetFromNumSet(s imapnum.Set) imap.UIDSet {
+	return *(*imap.UIDSet)(unsafe.Pointer(&s))
+}
+
+func NumSetKind(numSet imap.NumSet) NumKind {
+	switch numSet.(type) {
+	case imap.SeqSet:
+		return NumKindSeq
+	case imap.UIDSet:
+		return NumKindUID
+	default:
+		panic("imap: invalid NumSet type")
+	}
+}
+
+func ParseSeqSet(s string) (imap.SeqSet, error) {
+	numSet, err := imapnum.ParseSet(s)
+	return seqSetFromNumSet(numSet), err
+}
diff --git a/internal/imapwire/numset.go b/internal/imapwire/numset.go
deleted file mode 100644
index a3dd2c9..0000000
--- a/internal/imapwire/numset.go
+++ /dev/null
@@ -1,63 +0,0 @@
-package imapwire
-
-import (
-	"fmt"
-	"strconv"
-	"strings"
-
-	"github.com/emersion/go-imap/v2"
-)
-
-// errBadNumSet is used to report problems with the format of a number set
-// value.
-type errBadNumSet string
-
-func (err errBadNumSet) Error() string {
-	return fmt.Sprintf("imap: bad number set value %q", string(err))
-}
-
-// parseNum parses a single seq-number value (non-zero uint32 or "*").
-func parseNum(v string) (uint32, error) {
-	if n, err := strconv.ParseUint(v, 10, 32); err == nil && v[0] != '0' {
-		return uint32(n), nil
-	} else if v == "*" {
-		return 0, nil
-	}
-	return 0, errBadNumSet(v)
-}
-
-// parseNumRange creates a new seq instance by parsing strings in the format
-// "n" or "n:m", where n and/or m may be "*". An error is returned for invalid
-// values.
-func parseNumRange(v string) (imap.NumRange, error) {
-	var (
-		s   imap.NumRange
-		err error
-	)
-	if sep := strings.IndexRune(v, ':'); sep < 0 {
-		s.Start, err = parseNum(v)
-		s.Stop = s.Start
-		return s, err
-	} else if s.Start, err = parseNum(v[:sep]); err == nil {
-		if s.Stop, err = parseNum(v[sep+1:]); err == nil {
-			if (s.Stop < s.Start && s.Stop != 0) || s.Start == 0 {
-				s.Start, s.Stop = s.Stop, s.Start
-			}
-			return s, nil
-		}
-	}
-	return s, errBadNumSet(v)
-}
-
-// ParseNumSet returns a new NumSet after parsing the set string.
-func ParseNumSet(set string) (imap.NumSet, error) {
-	var s imap.NumSet
-	for _, sv := range strings.Split(set, ",") {
-		v, err := parseNumRange(sv)
-		if err != nil {
-			return s, err
-		}
-		s.AddRange(v.Start, v.Stop)
-	}
-	return s, nil
-}
diff --git a/numset.go b/numset.go
index faa4e27..a96b181 100644
--- a/numset.go
+++ b/numset.go
@@ -1,267 +1,149 @@
 package imap
 
 import (
-	"strconv"
+	"unsafe"
+
+	"github.com/emersion/go-imap/v2/internal/imapnum"
 )
 
-// NumRange represents a single seq-number or seq-range value (RFC 3501 ABNF). Values
-// may be static (e.g. "1", "2:4") or dynamic (e.g. "*", "1:*"). A seq-number is
-// represented by setting Start = Stop. Zero is used to represent "*", which is
-// safe because seq-number uses nz-number rule. The order of values is always
-// Start <= Stop, except when representing "n:*", where Start = n and Stop = 0.
-type NumRange struct {
-	Start, Stop uint32
-}
+// NumSet is a set of numbers identifying messages. NumSet is either a SeqSet
+// or a UIDSet.
+type NumSet interface {
+	// String returns the IMAP representation of the message number set.
+	String() string
+	// Dynamic returns true if the set contains "*" or "n:*" ranges or if the
+	// set represents the special SEARCHRES marker.
+	Dynamic() bool
 
-// Contains returns true if the seq-number q is contained in range value s.
-// The dynamic value "*" contains only other "*" values, the dynamic range "n:*"
-// contains "*" and all numbers >= n.
-func (s NumRange) Contains(q uint32) bool {
-	if q == 0 {
-		return s.Stop == 0 // "*" is contained only in "*" and "n:*"
-	}
-	return s.Start != 0 && s.Start <= q && (q <= s.Stop || s.Stop == 0)
+	numSet() imapnum.Set
 }
 
-// Less returns true if s precedes and does not contain seq-number q.
-func (s NumRange) Less(q uint32) bool {
-	return (s.Stop < q || q == 0) && s.Stop != 0
+var (
+	_ NumSet = SeqSet(nil)
+	_ NumSet = UIDSet(nil)
+)
+
+// SeqSet is a set of message sequence numbers.
+type SeqSet []SeqRange
+
+// SeqSetNum returns a new SeqSet containing the specified sequence numbers.
+func SeqSetNum(nums ...uint32) SeqSet {
+	var s SeqSet
+	s.AddNum(nums...)
+	return s
 }
 
-// Merge combines range values s and t into a single union if the two
-// intersect or one is a superset of the other. The order of s and t does not
-// matter. If the values cannot be merged, s is returned unmodified and ok is
-// set to false.
-func (s NumRange) Merge(t NumRange) (union NumRange, ok bool) {
-	union = s
-	if s == t {
-		return s, true
-	}
-	if s.Start != 0 && t.Start != 0 {
-		// s and t are any combination of "n", "n:m", or "n:*"
-		if s.Start > t.Start {
-			s, t = t, s
-		}
-		// s starts at or before t, check where it ends
-		if (s.Stop >= t.Stop && t.Stop != 0) || s.Stop == 0 {
-			return s, true // s is a superset of t
-		}
-		// s is "n" or "n:m", if m == ^uint32(0) then t is "n:*"
-		if s.Stop+1 >= t.Start || s.Stop == ^uint32(0) {
-			return NumRange{s.Start, t.Stop}, true // s intersects or touches t
-		}
-		return union, false
-	}
-	// exactly one of s and t is "*"
-	if s.Start == 0 {
-		if t.Stop == 0 {
-			return t, true // s is "*", t is "n:*"
-		}
-	} else if s.Stop == 0 {
-		return s, true // s is "n:*", t is "*"
-	}
-	return union, false
+func (s *SeqSet) numSetPtr() *imapnum.Set {
+	return (*imapnum.Set)(unsafe.Pointer(s))
 }
 
-// String returns range value s as a seq-number or seq-range string.
-func (s NumRange) String() string {
-	if s.Start == s.Stop {
-		if s.Start == 0 {
-			return "*"
-		}
-		return strconv.FormatUint(uint64(s.Start), 10)
-	}
-	b := strconv.AppendUint(make([]byte, 0, 24), uint64(s.Start), 10)
-	if s.Stop == 0 {
-		return string(append(b, ':', '*'))
-	}
-	return string(strconv.AppendUint(append(b, ':'), uint64(s.Stop), 10))
+func (s SeqSet) numSet() imapnum.Set {
+	return *s.numSetPtr()
 }
 
-func (s NumRange) append(nums []uint32) (out []uint32, ok bool) {
-	if s.Start == 0 || s.Stop == 0 {
-		return nil, false
-	}
-	for n := s.Start; n <= s.Stop; n++ {
-		nums = append(nums, n)
-	}
-	return nums, true
+func (s SeqSet) String() string {
+	return s.numSet().String()
 }
 
-// NumSet is used to represent a set of message sequence numbers or UIDs (see
-// sequence-set ABNF rule). The zero value is an empty set.
-type NumSet []NumRange
+func (s SeqSet) Dynamic() bool {
+	return s.numSet().Dynamic()
+}
 
-// NumSetNum returns a new NumSet containing the specified numbers.
-func NumSetNum(q ...uint32) NumSet {
-	var s NumSet
-	s.AddNum(q...)
-	return s
+// Contains returns true if the non-zero sequence number num is contained in
+// the set.
+func (s *SeqSet) Contains(num uint32) bool {
+	return s.numSet().Contains(num)
 }
 
-// NumSetRange returns a new NumSet containing the specified range.
-func NumSetRange(start, stop uint32) NumSet {
-	var s NumSet
-	s.AddRange(start, stop)
-	return s
+// Nums returns a slice of all sequence numbers contained in the set.
+func (s *SeqSet) Nums() ([]uint32, bool) {
+	return s.numSet().Nums()
 }
 
-// AddNum inserts new numbers into the set. The value 0 represents "*".
-func (s *NumSet) AddNum(q ...uint32) {
-	for _, v := range q {
-		s.insert(NumRange{v, v})
-	}
+// AddNum inserts new sequence numbers into the set. The value 0 represents "*".
+func (s *SeqSet) AddNum(nums ...uint32) {
+	s.numSetPtr().AddNum(nums...)
 }
 
 // AddRange inserts a new range into the set.
-func (s *NumSet) AddRange(start, stop uint32) {
-	if (stop < start && stop != 0) || start == 0 {
-		s.insert(NumRange{stop, start})
-	} else {
-		s.insert(NumRange{start, stop})
-	}
+func (s *SeqSet) AddRange(start, stop uint32) {
+	s.numSetPtr().AddRange(start, stop)
 }
 
-// AddSet inserts all values from t into s.
-func (s *NumSet) AddSet(t NumSet) {
-	for _, v := range t {
-		s.insert(v)
-	}
+// AddSet inserts all sequence numbers from other into s.
+func (s *SeqSet) AddSet(other SeqSet) {
+	s.numSetPtr().AddSet(other.numSet())
 }
 
-// Dynamic returns true if the set contains "*" or "n:*" values.
-func (s NumSet) Dynamic() bool {
-	return len(s) > 0 && s[len(s)-1].Stop == 0
+// SeqRange is a range of message sequence numbers.
+type SeqRange struct {
+	Start, Stop uint32
 }
 
-// Contains returns true if the non-zero sequence number or UID q is contained
-// in the set. The dynamic range "n:*" contains all q >= n. It is the caller's
-// responsibility to handle the special case where q is the maximum UID in the
-// mailbox and q < n (i.e. the set cannot match UIDs against "*:n" or "*" since
-// it doesn't know what the maximum value is).
-func (s NumSet) Contains(q uint32) bool {
-	if _, ok := s.search(q); ok {
-		return q != 0
-	}
-	return false
+// UIDSet is a set of message UIDs.
+type UIDSet []UIDRange
+
+// UIDSetNum returns a new UIDSet containing the specified UIDs.
+func UIDSetNum(uids ...UID) UIDSet {
+	var s UIDSet
+	s.AddNum(uids...)
+	return s
 }
 
-// Nums returns a slice of all numbers contained in the set.
-func (s NumSet) Nums() (nums []uint32, ok bool) {
-	for _, v := range s {
-		nums, ok = v.append(nums)
-		if !ok {
-			return nil, false
-		}
-	}
-	return nums, true
+func (s *UIDSet) numSetPtr() *imapnum.Set {
+	return (*imapnum.Set)(unsafe.Pointer(s))
+}
+
+func (s UIDSet) numSet() imapnum.Set {
+	return *s.numSetPtr()
 }
 
-// String returns a sorted representation of all contained number values.
-func (s NumSet) String() string {
+func (s UIDSet) String() string {
 	if IsSearchRes(s) {
 		return "$"
 	}
-	if len(s) == 0 {
-		return ""
-	}
-	b := make([]byte, 0, 64)
-	for _, v := range s {
-		b = append(b, ',')
-		if v.Start == 0 {
-			b = append(b, '*')
-			continue
-		}
-		b = strconv.AppendUint(b, uint64(v.Start), 10)
-		if v.Start != v.Stop {
-			if v.Stop == 0 {
-				b = append(b, ':', '*')
-				continue
-			}
-			b = strconv.AppendUint(append(b, ':'), uint64(v.Stop), 10)
-		}
-	}
-	return string(b[1:])
+	return s.numSet().String()
 }
 
-// insert adds range value v to the set.
-func (ptr *NumSet) insert(v NumRange) {
-	s := *ptr
-	defer func() {
-		*ptr = s
-	}()
+func (s UIDSet) Dynamic() bool {
+	return s.numSet().Dynamic() || IsSearchRes(s)
+}
 
-	i, _ := s.search(v.Start)
-	merged := false
-	if i > 0 {
-		// try merging with the preceding entry (e.g. "1,4".insert(2), i == 1)
-		s[i-1], merged = s[i-1].Merge(v)
-	}
-	if i == len(s) {
-		// v was either merged with the last entry or needs to be appended
-		if !merged {
-			s.insertAt(i, v)
-		}
-		return
-	} else if merged {
-		i--
-	} else if s[i], merged = s[i].Merge(v); !merged {
-		s.insertAt(i, v) // insert in the middle (e.g. "1,5".insert(3), i == 1)
-		return
-	}
-	// v was merged with s[i], continue trying to merge until the end
-	for j := i + 1; j < len(s); j++ {
-		if s[i], merged = s[i].Merge(s[j]); !merged {
-			if j > i+1 {
-				// cut out all entries between i and j that were merged
-				s = append(s[:i+1], s[j:]...)
-			}
-			return
-		}
-	}
-	// everything after s[i] was merged
-	s = s[:i+1]
+// Contains returns true if the non-zero UID uid is contained in the set.
+func (s UIDSet) Contains(uid UID) bool {
+	return s.numSet().Contains(uint32(uid))
 }
 
-// insertAt inserts a new range value v at index i, resizing s.Set as needed.
-func (ptr *NumSet) insertAt(i int, v NumRange) {
-	s := *ptr
-	defer func() {
-		*ptr = s
-	}()
+// Nums returns a slice of all UIDs contained in the set.
+func (s UIDSet) Nums() ([]UID, bool) {
+	nums, ok := s.numSet().Nums()
+	return uidListFromNumList(nums), ok
+}
 
-	if n := len(s); i == n {
-		// insert at the end
-		s = append(s, v)
-		return
-	} else if n < cap(s) {
-		// enough space, shift everything at and after i to the right
-		s = s[:n+1]
-		copy(s[i+1:], s[i:])
-	} else {
-		// allocate new slice and copy everything, n is at least 1
-		set := make([]NumRange, n+1, n*2)
-		copy(set, s[:i])
-		copy(set[i+1:], s[i:])
-		s = set
-	}
-	s[i] = v
+// AddNum inserts new UIDs into the set. The value 0 represents "*".
+func (s *UIDSet) AddNum(uids ...UID) {
+	s.numSetPtr().AddNum(numListFromUIDList(uids)...)
 }
 
-// search attempts to find the index of the range set value that contains q.
-// If no values contain q, the returned index is the position where q should be
-// inserted and ok is set to false.
-func (s NumSet) search(q uint32) (i int, ok bool) {
-	min, max := 0, len(s)-1
-	for min < max {
-		if mid := (min + max) >> 1; s[mid].Less(q) {
-			min = mid + 1
-		} else {
-			max = mid
-		}
-	}
-	if max < 0 || s[min].Less(q) {
-		return len(s), false // q is the new largest value
-	}
-	return min, s[min].Contains(q)
+// AddRange inserts a new range into the set.
+func (s *UIDSet) AddRange(start, stop UID) {
+	s.numSetPtr().AddRange(uint32(start), uint32(stop))
+}
+
+// AddSet inserts all UIDs from other into s.
+func (s *UIDSet) AddSet(other UIDSet) {
+	s.numSetPtr().AddSet(other.numSet())
+}
+
+// UIDRange is a range of message UIDs.
+type UIDRange struct {
+	Start, Stop UID
+}
+
+func numListFromUIDList(uids []UID) []uint32 {
+	return *(*[]uint32)(unsafe.Pointer(&uids))
+}
+
+func uidListFromNumList(nums []uint32) []UID {
+	return *(*[]UID)(unsafe.Pointer(&nums))
 }
diff --git a/search.go b/search.go
index 502f88d..e5b7720 100644
--- a/search.go
+++ b/search.go
@@ -36,8 +36,8 @@ type SearchOptions struct {
 //		{Body: []string{"world"}},
 //	}}}
 type SearchCriteria struct {
-	SeqNum []NumSet
-	UID    []NumSet
+	SeqNum []SeqSet
+	UID    []UIDSet
 
 	// Only the date is used, the time and timezone are ignored
 	Since      time.Time
@@ -147,33 +147,56 @@ type SearchData struct {
 	ModSeq uint64
 }
 
-// AllNums returns All as a slice of numbers.
-func (data *SearchData) AllNums() []uint32 {
+// AllSeqNums returns All as a slice of sequence numbers.
+func (data *SearchData) AllSeqNums() []uint32 {
+	seqSet, ok := data.All.(SeqSet)
+	if !ok {
+		return nil
+	}
+
 	// Note: a dynamic sequence set would be a server bug
-	nums, ok := data.All.Nums()
+	nums, ok := seqSet.Nums()
 	if !ok {
 		panic("imap: SearchData.All is a dynamic number set")
 	}
 	return nums
 }
 
-// searchRes is a special empty NumSet which can be used as a marker. It has
+// AllUIDs returns All as a slice of UIDs.
+func (data *SearchData) AllUIDs() []UID {
+	uidSet, ok := data.All.(UIDSet)
+	if !ok {
+		return nil
+	}
+
+	// Note: a dynamic sequence set would be a server bug
+	uids, ok := uidSet.Nums()
+	if !ok {
+		panic("imap: SearchData.All is a dynamic number set")
+	}
+	return uids
+}
+
+// searchRes is a special empty UIDSet which can be used as a marker. It has
 // a non-zero cap so that its data pointer is non-nil and can be compared.
+//
+// It's a UIDSet rather than a SeqSet so that it can be passed to the
+// UID EXPUNGE command.
 var (
-	searchRes     = make(NumSet, 0, 1)
+	searchRes     = make(UIDSet, 0, 1)
 	searchResAddr = reflect.ValueOf(searchRes).Pointer()
 )
 
-// SearchRes returns a special marker which can be used instead of a NumSet to
+// SearchRes returns a special marker which can be used instead of a UIDSet to
 // reference the last SEARCH result. On the wire, it's encoded as '$'.
 //
 // It requires IMAP4rev2 or the SEARCHRES extension.
-func SearchRes() NumSet {
+func SearchRes() UIDSet {
 	return searchRes
 }
 
 // IsSearchRes checks whether a sequence set is a reference to the last SEARCH
 // result. See SearchRes.
-func IsSearchRes(seqSet NumSet) bool {
-	return reflect.ValueOf(seqSet).Pointer() == searchResAddr
+func IsSearchRes(numSet NumSet) bool {
+	return reflect.ValueOf(numSet).Pointer() == searchResAddr
 }


Test patch:
diff --git a/imapclient/append_test.go b/imapclient/append_test.go
new file mode 100644
index 0000000..c5a30dc
--- /dev/null
+++ b/imapclient/append_test.go
@@ -0,0 +1,28 @@
+package imapclient_test
+
+import (
+	"testing"
+
+	"github.com/emersion/go-imap/v2"
+)
+
+func TestAppend(t *testing.T) {
+	client, server := newClientServerPair(t, imap.ConnStateSelected)
+	defer client.Close()
+	defer server.Close()
+
+	body := "This is a test message."
+
+	appendCmd := client.Append("INBOX", int64(len(body)), nil)
+	if _, err := appendCmd.Write([]byte(body)); err != nil {
+		t.Fatalf("AppendCommand.Write() = %v", err)
+	}
+	if err := appendCmd.Close(); err != nil {
+		t.Fatalf("AppendCommand.Close() = %v", err)
+	}
+	if _, err := appendCmd.Wait(); err != nil {
+		t.Fatalf("AppendCommand.Wait() = %v", err)
+	}
+
+	// TODO: fetch back message and check body
+}
diff --git a/imapclient/client_test.go b/imapclient/client_test.go
index 1c732f4..a954848 100644
--- a/imapclient/client_test.go
+++ b/imapclient/client_test.go
@@ -119,7 +119,7 @@ func TestFetch_invalid(t *testing.T) {
 	defer client.Close()
 	defer server.Close()
 
-	_, err := client.UIDFetch(imap.NumSetNum(), nil).Collect()
+	_, err := client.Fetch(imap.UIDSet(nil), nil).Collect()
 	if err == nil {
 		t.Fatalf("UIDFetch().Collect() = %v", err)
 	}
@@ -130,7 +130,7 @@ func TestFetch_closeUnreadBody(t *testing.T) {
 	defer client.Close()
 	defer server.Close()
 
-	fetchCmd := client.UIDFetch(imap.NumSetNum(1), &imap.FetchOptions{
+	fetchCmd := client.Fetch(imap.SeqSetNum(1), &imap.FetchOptions{
 		BodySection: []*imap.FetchItemBodySection{
 			{
 				Specifier: imap.PartSpecifierNone,
diff --git a/imapclient/example_test.go b/imapclient/example_test.go
index 712fff2..3f3d25e 100644
--- a/imapclient/example_test.go
+++ b/imapclient/example_test.go
@@ -39,7 +39,7 @@ func ExampleClient() {
 	log.Printf("INBOX contains %v messages", selectedMbox.NumMessages)
 
 	if selectedMbox.NumMessages > 0 {
-		seqSet := imap.NumSetNum(1)
+		seqSet := imap.SeqSetNum(1)
 		fetchOptions := &imap.FetchOptions{Envelope: true}
 		messages, err := c.Fetch(seqSet, fetchOptions).Collect()
 		if err != nil {
@@ -56,13 +56,13 @@ func ExampleClient() {
 func ExampleClient_pipelining() {
 	var c *imapclient.Client
 
-	uid := uint32(42)
+	uid := imap.UID(42)
 	fetchOptions := &imap.FetchOptions{Envelope: true}
 
 	// Login, select and fetch a message in a single roundtrip
 	loginCmd := c.Login("root", "root")
 	selectCmd := c.Select("INBOX", nil)
-	fetchCmd := c.UIDFetch(imap.NumSetNum(uid), fetchOptions)
+	fetchCmd := c.Fetch(imap.UIDSetNum(uid), fetchOptions)
 
 	if err := loginCmd.Wait(); err != nil {
 		log.Fatalf("failed to login: %v", err)
@@ -130,7 +130,7 @@ func ExampleClient_List_stream() {
 func ExampleClient_Store() {
 	var c *imapclient.Client
 
-	seqSet := imap.NumSetNum(1)
+	seqSet := imap.SeqSetNum(1)
 	storeFlags := imap.StoreFlags{
 		Op:     imap.StoreFlagsAdd,
 		Flags:  []imap.Flag{imap.FlagFlagged},
@@ -144,7 +144,7 @@ func ExampleClient_Store() {
 func ExampleClient_Fetch() {
 	var c *imapclient.Client
 
-	seqSet := imap.NumSetNum(1)
+	seqSet := imap.SeqSetNum(1)
 	fetchOptions := &imap.FetchOptions{
 		Flags:    true,
 		Envelope: true,
@@ -172,7 +172,7 @@ func ExampleClient_Fetch() {
 func ExampleClient_Fetch_streamBody() {
 	var c *imapclient.Client
 
-	seqSet := imap.NumSetNum(1)
+	seqSet := imap.SeqSetNum(1)
 	fetchOptions := &imap.FetchOptions{
 		UID:         true,
 		BodySection: []*imap.FetchItemBodySection{{}},
@@ -214,7 +214,7 @@ func ExampleClient_Fetch_parseBody() {
 	var c *imapclient.Client
 
 	// Send a FETCH command to fetch the message body
-	seqSet := imap.NumSetNum(1)
+	seqSet := imap.SeqSetNum(1)
 	fetchOptions := &imap.FetchOptions{
 		BodySection: []*imap.FetchItemBodySection{{}},
 	}
@@ -302,7 +302,7 @@ func ExampleClient_Search() {
 	if err != nil {
 		log.Fatalf("UID SEARCH command failed: %v", err)
 	}
-	log.Fatalf("UIDs matching the search criteria: %v", data.AllNums())
+	log.Fatalf("UIDs matching the search criteria: %v", data.AllUIDs())
 }
 
 func ExampleClient_Idle() {
diff --git a/imapclient/store_test.go b/imapclient/store_test.go
index 84c7a81..5ecbeb9 100644
--- a/imapclient/store_test.go
+++ b/imapclient/store_test.go
@@ -11,7 +11,7 @@ func TestStore(t *testing.T) {
 	defer client.Close()
 	defer server.Close()
 
-	seqSet := imap.NumSetNum(1)
+	seqSet := imap.SeqSetNum(1)
 	storeFlags := imap.StoreFlags{
 		Op:    imap.StoreFlagsAdd,
 		Flags: []imap.Flag{imap.FlagDeleted},
diff --git a/internal/imapwire/numset_test.go b/internal/imapnum/numset_test.go
similarity index 83%
rename from internal/imapwire/numset_test.go
rename to internal/imapnum/numset_test.go
index 91f244b..440abbb 100644
--- a/internal/imapwire/numset_test.go
+++ b/internal/imapnum/numset_test.go
@@ -1,11 +1,9 @@
-package imapwire
+package imapnum
 
 import (
 	"math/rand"
 	"strings"
 	"testing"
-
-	"github.com/emersion/go-imap/v2"
 )
 
 const max = ^uint32(0)
@@ -13,73 +11,73 @@ const max = ^uint32(0)
 func TestParseNumRange(t *testing.T) {
 	tests := []struct {
 		in  string
-		out imap.NumRange
+		out Range
 		ok  bool
 	}{
 		// Invalid number
-		{"", imap.NumRange{}, false},
-		{" ", imap.NumRange{}, false},
-		{"A", imap.NumRange{}, false},
-		{"0", imap.NumRange{}, false},
-		{" 1", imap.NumRange{}, false},
-		{"1 ", imap.NumRange{}, false},
-		{"*1", imap.NumRange{}, false},
-		{"1*", imap.NumRange{}, false},
-		{"-1", imap.NumRange{}, false},
-		{"01", imap.NumRange{}, false},
-		{"0x1", imap.NumRange{}, false},
-		{"1 2", imap.NumRange{}, false},
-		{"1,2", imap.NumRange{}, false},
-		{"1.2", imap.NumRange{}, false},
-		{"4294967296", imap.NumRange{}, false},
+		{"", Range{}, false},
+		{" ", Range{}, false},
+		{"A", Range{}, false},
+		{"0", Range{}, false},
+		{" 1", Range{}, false},
+		{"1 ", Range{}, false},
+		{"*1", Range{}, false},
+		{"1*", Range{}, false},
+		{"-1", Range{}, false},
+		{"01", Range{}, false},
+		{"0x1", Range{}, false},
+		{"1 2", Range{}, false},
+		{"1,2", Range{}, false},
+		{"1.2", Range{}, false},
+		{"4294967296", Range{}, false},
 
 		// Valid number
-		{"*", imap.NumRange{0, 0}, true},
-		{"1", imap.NumRange{1, 1}, true},
-		{"42", imap.NumRange{42, 42}, true},
-		{"1000", imap.NumRange{1000, 1000}, true},
-		{"4294967295", imap.NumRange{max, max}, true},
+		{"*", Range{0, 0}, true},
+		{"1", Range{1, 1}, true},
+		{"42", Range{42, 42}, true},
+		{"1000", Range{1000, 1000}, true},
+		{"4294967295", Range{max, max}, true},
 
 		// Invalid range
-		{":", imap.NumRange{}, false},
-		{"*:", imap.NumRange{}, false},
-		{":*", imap.NumRange{}, false},
-		{"1:", imap.NumRange{}, false},
-		{":1", imap.NumRange{}, false},
-		{"0:0", imap.NumRange{}, false},
-		{"0:*", imap.NumRange{}, false},
-		{"0:1", imap.NumRange{}, false},
-		{"1:0", imap.NumRange{}, false},
-		{"1:2 ", imap.NumRange{}, false},
-		{"1: 2", imap.NumRange{}, false},
-		{"1:2:", imap.NumRange{}, false},
-		{"1:2,", imap.NumRange{}, false},
-		{"1:2:3", imap.NumRange{}, false},
-		{"1:2,3", imap.NumRange{}, false},
-		{"*:4294967296", imap.NumRange{}, false},
-		{"0:4294967295", imap.NumRange{}, false},
-		{"1:4294967296", imap.NumRange{}, false},
-		{"4294967296:*", imap.NumRange{}, false},
-		{"4294967295:0", imap.NumRange{}, false},
-		{"4294967296:1", imap.NumRange{}, false},
-		{"4294967295:4294967296", imap.NumRange{}, false},
+		{":", Range{}, false},
+		{"*:", Range{}, false},
+		{":*", Range{}, false},
+		{"1:", Range{}, false},
+		{":1", Range{}, false},
+		{"0:0", Range{}, false},
+		{"0:*", Range{}, false},
+		{"0:1", Range{}, false},
+		{"1:0", Range{}, false},
+		{"1:2 ", Range{}, false},
+		{"1: 2", Range{}, false},
+		{"1:2:", Range{}, false},
+		{"1:2,", Range{}, false},
+		{"1:2:3", Range{}, false},
+		{"1:2,3", Range{}, false},
+		{"*:4294967296", Range{}, false},
+		{"0:4294967295", Range{}, false},
+		{"1:4294967296", Range{}, false},
+		{"4294967296:*", Range{}, false},
+		{"4294967295:0", Range{}, false},
+		{"4294967296:1", Range{}, false},
+		{"4294967295:4294967296", Range{}, false},
 
 		// Valid range
-		{"*:*", imap.NumRange{0, 0}, true},
-		{"1:*", imap.NumRange{1, 0}, true},
-		{"*:1", imap.NumRange{1, 0}, true},
-		{"2:2", imap.NumRange{2, 2}, true},
-		{"2:42", imap.NumRange{2, 42}, true},
-		{"42:2", imap.NumRange{2, 42}, true},
-		{"*:4294967294", imap.NumRange{max - 1, 0}, true},
-		{"*:4294967295", imap.NumRange{max, 0}, true},
-		{"4294967294:*", imap.NumRange{max - 1, 0}, true},
-		{"4294967295:*", imap.NumRange{max, 0}, true},
-		{"1:4294967294", imap.NumRange{1, max - 1}, true},
-		{"1:4294967295", imap.NumRange{1, max}, true},
-		{"4294967295:1000", imap.NumRange{1000, max}, true},
-		{"4294967294:4294967295", imap.NumRange{max - 1, max}, true},
-		{"4294967295:4294967295", imap.NumRange{max, max}, true},
+		{"*:*", Range{0, 0}, true},
+		{"1:*", Range{1, 0}, true},
+		{"*:1", Range{1, 0}, true},
+		{"2:2", Range{2, 2}, true},
+		{"2:42", Range{2, 42}, true},
+		{"42:2", Range{2, 42}, true},
+		{"*:4294967294", Range{max - 1, 0}, true},
+		{"*:4294967295", Range{max, 0}, true},
+		{"4294967294:*", Range{max - 1, 0}, true},
+		{"4294967295:*", Range{max, 0}, true},
+		{"1:4294967294", Range{1, max - 1}, true},
+		{"1:4294967295", Range{1, max}, true},
+		{"4294967295:1000", Range{1000, max}, true},
+		{"4294967294:4294967295", Range{max - 1, max}, true},
+		{"4294967295:4294967295", Range{max, max}, true},
 	}
 	for _, test := range tests {
 		out, err := parseNumRange(test.in)
@@ -188,7 +186,7 @@ func TestNumRangeMerge(T *testing.T) {
 		{"*", "4294967295", ""},
 		{"*", "*", "*"},
 
-		// NumRange with number
+		// Range with number
 		{"1:3", "1", "1:3"},
 		{"1:3", "2", "1:3"},
 		{"1:3", "3", "1:3"},
@@ -254,7 +252,7 @@ func TestNumRangeMerge(T *testing.T) {
 		{"1:*", "4294967295", "1:*"},
 		{"1:*", "*", "1:*"},
 
-		// NumRange with range
+		// Range with range
 		{"5:8", "1:2", ""},
 		{"5:8", "1:3", ""},
 		{"5:8", "1:4", "1:8"},
@@ -368,7 +366,7 @@ func TestNumRangeMerge(T *testing.T) {
 	}
 }
 
-func checkNumSet(s imap.NumSet, t *testing.T) {
+func checkNumSet(s Set, t *testing.T) {
 	n := len(s)
 	for i, v := range s {
 		if v.Start == 0 {
@@ -533,7 +531,7 @@ func TestNumSetInfo(t *testing.T) {
 		{"1,3:5,7,9,42,60:70,100:*", max, true},
 	}
 	for _, test := range tests {
-		s, _ := ParseNumSet(test.s)
+		s, _ := ParseSet(test.s)
 		checkNumSet(s, t)
 		if s.Contains(test.q) != test.contains {
 			t.Errorf("%q.Contains(%v) expected %v", test.s, test.q, test.contains)
@@ -675,7 +673,7 @@ func TestParseNumSet(t *testing.T) {
 	}
 	for _, test := range tests {
 		for i := 0; i < 100 && test.in != ""; i++ {
-			s, err := ParseNumSet(test.in)
+			s, err := ParseSet(test.in)
 			if err != nil {
 				t.Errorf("Add(%q) unexpected error; %v", test.in, err)
 				i = 100
@@ -694,24 +692,24 @@ func TestNumSetAddNumRangeSet(t *testing.T) {
 	type num []uint32
 	tests := []struct {
 		num num
-		rng imap.NumRange
+		rng Range
 		set string
 		out string
 	}{
-		{num{5}, imap.NumRange{1, 3}, "1:2,5,7:13,15,17:*", "1:3,5,7:13,15,17:*"},
-		{num{5}, imap.NumRange{3, 1}, "2:3,7:13,15,17:*", "1:3,5,7:13,15,17:*"},
+		{num{5}, Range{1, 3}, "1:2,5,7:13,15,17:*", "1:3,5,7:13,15,17:*"},
+		{num{5}, Range{3, 1}, "2:3,7:13,15,17:*", "1:3,5,7:13,15,17:*"},
 
-		{num{15}, imap.NumRange{17, 0}, "1:3,5,7:13", "1:3,5,7:13,15,17:*"},
-		{num{15}, imap.NumRange{0, 17}, "1:3,5,7:13", "1:3,5,7:13,15,17:*"},
+		{num{15}, Range{17, 0}, "1:3,5,7:13", "1:3,5,7:13,15,17:*"},
+		{num{15}, Range{0, 17}, "1:3,5,7:13", "1:3,5,7:13,15,17:*"},
 
-		{num{1, 3, 5, 7, 9, 11, 0}, imap.NumRange{8, 13}, "2,15,17:*", "1:3,5,7:13,15,17:*"},
-		{num{5, 1, 7, 3, 9, 0, 11}, imap.NumRange{8, 13}, "2,15,17:*", "1:3,5,7:13,15,17:*"},
-		{num{5, 1, 7, 3, 9, 0, 11}, imap.NumRange{13, 8}, "2,15,17:*", "1:3,5,7:13,15,17:*"},
+		{num{1, 3, 5, 7, 9, 11, 0}, Range{8, 13}, "2,15,17:*", "1:3,5,7:13,15,17:*"},
+		{num{5, 1, 7, 3, 9, 0, 11}, Range{8, 13}, "2,15,17:*", "1:3,5,7:13,15,17:*"},
+		{num{5, 1, 7, 3, 9, 0, 11}, Range{13, 8}, "2,15,17:*", "1:3,5,7:13,15,17:*"},
 	}
 	for _, test := range tests {
-		other, _ := ParseNumSet(test.set)
+		other, _ := ParseSet(test.set)
 
-		var s imap.NumSet
+		var s Set
 		s.AddNum(test.num...)
 		checkNumSet(s, t)
 		s.AddRange(test.rng.Start, test.rng.Stop)