Repository: inetaf/netaddr
Pull request #49 (2020-11-22 06:07:00)

Add IPRange, IPRangeSet & friends to work on sets of prefixes/ranges
Not done, but you can see where I'm going. Just need to map ranges to a covering of `[]IPPrefix` now.

/cc @josharian @danderson @mdlayher @crawshaw 

josharian: Is this intended to replace the Cilium manipulation code I started hacking on on Friday?
bradfitz: It could. I needed a fun little exercise last night and had been thinking about it.
bradfitz: Okay, PTAL. The hard bits are all done now and the main function we need (albeit with a kinda ugly signature) is now there with tests. There are some API decisions to make, though:

* export `IPRange`? ... useful on its own probably?
* make a new IPRangeSet type that's opaque with methods like:
   - `func (s *IPRangeSet) AddPrefix(p IPPrefix)`
   - `func (s *IPRangeSet) AddRange(r IPRange)`
   - `func (s *IPRangeSet) Add(b IPRangeSet)`
   - `func (s *IPRangeSet) Sub(b IPRangeSet)`
   - `func (s *IPRangeSet) Prefixes() []IPPrefix`
   - `func (s *IPRangeSet) Ranges() []IPRange`
   - `func (s *IPRangeSet) Matcher() (contains func(IP) bool)` (could generate an optimized matcher for re-use, like `strings.NewReplacer`, `regexp.Compile`, etc)

If that API sounds good, doing it is easy now that all the necessary code is in this draft PR at this point (just unexported).

I could also unify some of the various code internally (use `ip16` type for more things, unify the `IPPrefix.Masked` impl, etc)


bradfitz: Ready for review.

Patch:
diff --git a/netaddr.go b/netaddr.go
index 7bab6ef..af633da 100644
--- a/netaddr.go
+++ b/netaddr.go
@@ -11,7 +11,9 @@ import (
 	"bytes"
 	"errors"
 	"fmt"
+	"log"
 	"net"
+	"sort"
 	"strconv"
 	"strings"
 	"sync"
@@ -45,7 +47,7 @@ type ipImpl interface {
 	is4() bool
 	is6() bool
 	is4in6() bool
-	as16() [16]byte
+	as16() ip16
 	// prefix is the type-specific implementation of IP.Prefix.
 	prefix(uint8) (IPPrefix, error)
 	String() string
@@ -56,8 +58,8 @@ type v4Addr [4]byte
 func (v4Addr) is4() bool    { return true }
 func (v4Addr) is6() bool    { return false }
 func (v4Addr) is4in6() bool { return false }
-func (ip v4Addr) as16() [16]byte {
-	return [16]byte{
+func (ip v4Addr) as16() ip16 {
+	return ip16{
 		10: 0xff,
 		11: 0xff,
 		12: ip[0],
@@ -92,10 +94,10 @@ const (
 
 type v6Addr [16]byte
 
-func (v6Addr) is4() bool         { return false }
-func (v6Addr) is6() bool         { return true }
-func (ip v6Addr) is4in6() bool   { return string(ip[:len(mapped4Prefix)]) == mapped4Prefix }
-func (ip v6Addr) as16() [16]byte { return ip }
+func (v6Addr) is4() bool       { return false }
+func (v6Addr) is6() bool       { return true }
+func (ip v6Addr) is4in6() bool { return string(ip[:len(mapped4Prefix)]) == mapped4Prefix }
+func (ip v6Addr) as16() ip16   { return ip16(ip) }
 func (ip v6Addr) prefix(bits uint8) (IPPrefix, error) {
 	if bits > 128 {
 		return IPPrefix{}, fmt.Errorf("netaddr: prefix length %d too large for IP address family", bits)
@@ -288,36 +290,48 @@ func (ip IP) Zone() string {
 	return ""
 }
 
-// Less reports whether ip sorts before ip2.
-// IP addresses sort first by length, then their address.
-// IPv6 addresses with zones sort just after the same address without a zone.
-func (ip IP) Less(ip2 IP) bool {
+// Compare returns an integer comparing two IPs.
+// The result will be 0 if ip==ip2, -1 if ip < ip2, and +1 if ip > ip2.
+// The definition of "less than" is the same as the IP.Less method.
+func (ip IP) Compare(ip2 IP) int {
 	a, b := ip, ip2
 	// Zero value sorts first.
 	if a.ipImpl == nil {
-		return b.ipImpl != nil
+		if b.ipImpl == nil {
+			return 0
+		}
+		return -1
 	}
 	if b.ipImpl == nil {
-		return false
+		return 1
 	}
 
 	a4, b4 := a.Is4(), b.Is4()
 	if a4 != b4 {
-		// When address families differ, IPv4 sorts first.
-		return a4
+		if a4 {
+			return -1
+		}
+		return 1
 	}
 
 	aa, ba := a.As16(), b.As16()
-	switch bytes.Compare(aa[:], ba[:]) {
-	case -1:
-		return true
-	case 1:
-		return false
-	default: // case 0 (bytes.Compare only returns -1, 1, or 0)
-		return !a4 && a.Zone() < b.Zone()
+	c := bytes.Compare(aa[:], ba[:])
+	if c == 0 && !a4 {
+		za, zb := a.Zone(), b.Zone()
+		if za < zb {
+			c = -1
+		} else if za > zb {
+			c = 1
+		}
 	}
+	return c
 }
 
+// Less reports whether ip sorts before ip2.
+// IP addresses sort first by length, then their address.
+// IPv6 addresses with zones sort just after the same address without a zone.
+func (ip IP) Less(ip2 IP) bool { return ip.Compare(ip2) == -1 }
+
 // ipZone returns the standard library net.IP from ip, as well
 // as the zone.
 // The optional reuse IP provides memory to reuse.
@@ -715,6 +729,17 @@ func (p IPPrefix) Masked() IPPrefix {
 	return IPPrefix{}
 }
 
+// Range returns the inclusive range of IPs that p covers.
+//
+// If p is zero or otherwise invalid, Range returns the zero value.
+func (p IPPrefix) Range() IPRange {
+	p = p.Masked()
+	if p.IsZero() {
+		return IPRange{}
+	}
+	return IPRange{From: p.IP, To: p.LastIP()}
+}
+
 // IPNet returns the net.IPNet representation of an IPPrefix.
 // The returned value is always non-nil.
 // Any zone identifier is dropped in the conversion.
@@ -846,3 +871,422 @@ func (p *IPPrefix) UnmarshalText(text []byte) error {
 func (p IPPrefix) String() string {
 	return fmt.Sprintf("%s/%d", p.IP, p.Bits)
 }
+
+// LastIP returns the last IP in the prefix.
+func (p IPPrefix) LastIP() IP {
+	if p.IP.IsZero() {
+		return IP{}
+	}
+	a16 := p.IP.As16()
+	var off uint8
+	var bits uint8 = 128
+	if p.IP.Is4() {
+		off = 12
+		bits = 32
+	}
+	for b := p.Bits; b < bits; b++ {
+		byteNum, bitInByte := b/8, 7-(b%8)
+		a16[off+byteNum] |= 1 << uint(bitInByte)
+	}
+	if p.IP.Is4() {
+		return IPFrom16(a16)
+	} else {
+		return IPv6Raw(a16) // doesn't unmap
+	}
+}
+
+// IPRange represents an inclusive range of IP addresses
+// from the same address family.
+type IPRange struct {
+	// From is the starting IP address in the range.
+	// It must have the same address family (IPv4 vs IPv6) as To
+	// and be less than or equal to To.
+	// From is an inclusive bound; it is included in the set.
+	From IP
+
+	// To is the ending IP address in the range.
+	// It must have the same address family (IPv4 vs IPv6) as From
+	// and be greater than or equal to From.
+	// To is an inclusive bound; it is included in the set.
+	To IP
+}
+
+// Valid reports whether r.From and r.To are both non-zero and obey
+// the documented requirements: address families match, and From is
+// less than or equal to To.
+func (r IPRange) Valid() bool {
+	return !r.From.IsZero() && !r.To.IsZero() &&
+		r.From.Is4() == r.To.Is4() &&
+		!r.To.Less(r.From)
+}
+
+// ip16 represents a mutable IP address, either IPv4 (in IPv6-mapped
+// form) or IPv6.
+type ip16 [16]byte
+
+// bitSet reports whether the given bit in the address is set.
+// (bit 0 is the most significant bit in ip[0]; bit 127 is last)
+func (ip ip16) bitSet(bit uint8) bool {
+	i, s := bit/8, 7-(bit%8)
+	return ip[i]&(1<<s) != 0
+}
+
+func (ip *ip16) set(bit uint8) {
+	i, s := bit/8, 7-(bit%8)
+	ip[i] |= 1 << s
+}
+
+func (ip *ip16) clear(bit uint8) {
+	i, s := bit/8, 7-(bit%8)
+	ip[i] &^= 1 << s
+}
+
+// lastWithBitZero returns a copy of ip with the given bit
+// cleared and the following all set.
+func (ip ip16) lastWithBitZero(bit uint8) ip16 {
+	ip.clear(bit)
+	for ; bit < 128; bit++ {
+		ip.set(bit)
+	}
+	return ip
+}
+
+// firstWithBitOne returns a copy of ip with the given bit
+// set and the following all cleared.
+func (ip ip16) firstWithBitOne(bit uint8) ip16 {
+	ip.set(bit)
+	for ; bit < 128; bit++ {
+		ip.clear(bit)
+	}
+	return ip
+}
+
+// prefixMaker returns a address-family-corrected IPPrefix from ip16 and bits,
+// where the input bits is always in the IPv6-mapped form for IPv4 addresses.
+type prefixMaker func(ip16 ip16, bits uint8) IPPrefix
+
+// Prefixes returns the set of IPPrefix entries that covers r.
+//
+// If either of r's bounds are invalid, in the wrong order, or if
+// they're of different address families, then Prefixes returns nil.
+func (r IPRange) Prefixes() []IPPrefix {
+	if !r.Valid() {
+		return nil
+	}
+	var makePrefix prefixMaker
+	if r.From.Is4() {
+		makePrefix = func(ip16 ip16, bits uint8) IPPrefix {
+			return IPPrefix{IPFrom16([16]byte(ip16)), bits - 12*8}
+		}
+	} else {
+		makePrefix = func(ip16 ip16, bits uint8) IPPrefix {
+			return IPPrefix{IPv6Raw([16]byte(ip16)), bits}
+		}
+	}
+	a16, b16 := ip16(r.From.As16()), ip16(r.To.As16())
+	return appendRangePrefixes(nil, makePrefix, a16, b16)
+}
+
+func appendRangePrefixes(dst []IPPrefix, makePrefix prefixMaker, a16, b16 ip16) []IPPrefix {
+	common := uint8(0)
+	for common < 128 && a16.bitSet(common) == b16.bitSet(common) {
+		common++
+	}
+	// See whether a16 and b16, after their common shared bits, end
+	// in all zero bits or all one bits, respectively.
+	aAllZero, bAllSet := true, true
+	for i := common; i < 128; i++ {
+		if a16.bitSet(i) {
+			aAllZero = false
+			break
+		}
+	}
+	for i := common; i < 128; i++ {
+		if !b16.bitSet(i) {
+			bAllSet = false
+			break
+		}
+	}
+	if aAllZero && bAllSet {
+		// a16 to b16 represents a whole range, like 10.50.0.0/16.
+		// (a16 being 10.50.0.0 and b16 being 10.50.255.255)
+		return append(dst, makePrefix(a16, common))
+	}
+	// Otherwise recursively do both halves.
+	dst = appendRangePrefixes(dst, makePrefix, a16, a16.lastWithBitZero(common+1))
+	dst = appendRangePrefixes(dst, makePrefix, b16.firstWithBitOne(common+1), b16)
+	return dst
+}
+
+func addOne(a []byte, i int) bool {
+	if v := a[i]; v < 0xff {
+		a[i]++
+		return true
+	}
+	if i == 0 {
+		return false
+	}
+	a[i] = 0
+	return addOne(a, i-1)
+}
+
+func subOne(a []byte, i int) bool {
+	if v := a[i]; v > 0 {
+		a[i]--
+		return true
+	}
+	if i == 0 {
+		return false
+	}
+	a[i] = 0xff
+	return subOne(a, i-1)
+}
+
+// ipFrom16Match returns an IP address from a with address family
+// matching ip.
+func ipFrom16Match(ip IP, a [16]byte) IP {
+	if ip.Is6() {
+		return IPv6Raw(a) // doesn't unwrap
+	}
+	return IPFrom16(a)
+}
+
+// Next returns the IP following ip.
+// If there is none, it returns the IP zero value.
+func (ip IP) Next() IP {
+	var ok bool
+	a := ip.As16()
+	if ip.Is4() {
+		ok = addOne(a[12:], 3)
+	} else {
+		ok = addOne(a[:], 15)
+	}
+	if ok {
+		return ipFrom16Match(ip, a)
+	}
+	return IP{}
+}
+
+// Prior returns the IP before ip.
+// If there is none, it returns the IP zero value.
+func (ip IP) Prior() IP {
+	var ok bool
+	a := ip.As16()
+	if ip.Is4() {
+		ok = subOne(a[12:], 3)
+	} else {
+		ok = subOne(a[:], 15)
+	}
+	if ok {
+		return ipFrom16Match(ip, a)
+	}
+	return IP{}
+}
+
+// IPRangeSet represents a set of IPRanges.
+//
+// The zero value is a valid value representing a set of no IP ranges.
+//
+// The Add and Remove methods add or remove ranges to the set.  Add
+// methods should be called first, as a remove operation does nothing
+// on an empty set. Ranges may be fully, partially, or not
+// overlapping.
+type IPRangeSet struct {
+	// in are the ranges in the set.
+	in []IPRange
+
+	// out are the ranges to be removed from 'in'.
+	out []IPRange
+}
+
+// AddPrefix adds p's range to s.
+func (s *IPRangeSet) AddPrefix(p IPPrefix) { s.AddRange(p.Range()) }
+
+// AddRange adds r to s.
+func (s *IPRangeSet) AddRange(r IPRange) {
+	if !r.Valid() {
+		return
+	}
+	// If there are any removals (s.out), then we need to compact the set
+	// first to get the order right.
+	if len(s.out) > 0 {
+		s.in = s.Ranges()
+		s.out = nil
+	}
+	s.in = append(s.in, r)
+}
+
+// RemovePrefix removes p's range from s.
+func (s *IPRangeSet) RemovePrefix(p IPPrefix) { s.RemoveRange(p.Range()) }
+
+// RemoveRange removes r from s.
+func (s *IPRangeSet) RemoveRange(r IPRange) {
+	if r.Valid() {
+		s.out = append(s.out, r)
+	}
+}
+
+// AddSet adds all ranges in b to s.
+func (s *IPRangeSet) AddSet(b *IPRangeSet) {
+	for _, r := range b.Ranges() {
+		s.AddRange(r)
+	}
+}
+
+// RemoveSet removes all ranges in b from s.
+func (s *IPRangeSet) RemoveSet(b *IPRangeSet) {
+	for _, r := range b.Ranges() {
+		s.RemoveRange(r)
+	}
+}
+
+// point is either the start or end of IP range of wanted or unwanted
+// IPs.
+type point struct {
+	ip    IP
+	want  bool // true for 'add', false for remove
+	start bool // true for start of range, false for (inclusive) end
+}
+
+func debugLogPoints(points []point) {
+	for _, p := range points {
+		emo := "✅"
+		if !p.want {
+			emo = "❌"
+		}
+		if p.start {
+			log.Printf(" {  %-15s %s\n", p.ip, emo)
+		} else {
+			log.Printf("  } %-15s %s\n", p.ip, emo)
+		}
+	}
+}
+
+// Ranges removes the minimum and sorted set of IP
+// ranges that covers s.
+func (s *IPRangeSet) Ranges() []IPRange {
+	var points []point
+	for _, r := range s.in {
+		points = append(points, point{r.From, true, true}, point{r.To, true, false})
+	}
+	for _, r := range s.out {
+		points = append(points, point{r.From, false, true}, point{r.To, false, false})
+	}
+	sort.Slice(points, func(i, j int) bool {
+		pi, pj := &points[i], &points[j]
+		cmp := pi.ip.Compare(pj.ip)
+		if cmp != 0 {
+			return cmp < 0
+		}
+		if pi.want != pj.want {
+			// Unwanted first.
+			return !pi.want
+		}
+		if pi.start != pj.start {
+			return pi.start
+		}
+		return false
+	})
+	const debug = false
+	if debug {
+		log.Printf("post-sort:")
+		debugLogPoints(points)
+		log.Printf("merging...")
+	}
+
+	// Now build 'want', like points but with "remove" ranges removed
+	// and adjancent blocks merged, and all elements alternating between
+	// start and end.
+	want := points[:0]
+	var addDepth, removeDepth int
+	for i, p := range points {
+		depth := &addDepth
+		if !p.want {
+			depth = &removeDepth
+		}
+		if p.start {
+			*depth++
+		} else {
+			*depth--
+		}
+		if debug {
+			log.Printf("at[%d] (%+v), add=%v, remove=%v", i, p, addDepth, removeDepth)
+		}
+		if p.start && *depth != 1 {
+			continue
+		}
+		if !p.start && *depth != 0 {
+			continue
+		}
+		if !p.want && addDepth > 0 {
+			if p.start {
+				// If we're transitioning from a range of
+				// addresses we want to ones we don't, insert
+				// an end marker for the IP before the one we
+				// don't.
+				want = append(want, point{
+					ip:    p.ip.Prior(),
+					want:  true,
+					start: false,
+				})
+			} else {
+				want = append(want, point{
+					ip:    p.ip.Next(),
+					want:  true,
+					start: true,
+				})
+			}
+		}
+		if !p.want || removeDepth > 0 {
+			continue
+		}
+		// Merge adjacent ranges. Remove prior and skip this
+		// start.
+		if p.start && len(want) > 0 {
+			prior := &want[len(want)-1]
+			if !prior.start && prior.ip == p.ip.Prior() {
+				want = want[:len(want)-1]
+				continue
+			}
+		}
+		want = append(want, p)
+	}
+	if debug {
+		log.Printf("post-merge:")
+		debugLogPoints(want)
+	}
+
+	if len(want)%2 == 1 {
+		panic("internal error; odd number")
+	}
+
+	out := make([]IPRange, 0, len(want)/2)
+	for i := 0; i < len(want); i += 2 {
+		if !want[i].want {
+			panic("internal error; non-want in range")
+		}
+		if !want[i].start {
+			panic("internal error; odd not start")
+		}
+		if want[i+1].start {
+			panic("internal error; even not end")
+		}
+		out = append(out, IPRange{
+			From: want[i].ip,
+			To:   want[i+1].ip,
+		})
+	}
+	return out
+}
+
+// Prefixes returns the minimum and sorted set of IP prefixes
+// that covers s.
+// returning a new slice of prefixes that covers all of the given 'add'
+// prefixes with all the 'remove' prefixes removed.
+func (s *IPRangeSet) Prefixes() []IPPrefix {
+	var out []IPPrefix
+	for _, r := range s.Ranges() {
+		out = append(out, r.Prefixes()...)
+	}
+	return out
+}


Test patch:
diff --git a/netaddr_test.go b/netaddr_test.go
index 88358d6..dc0fa6c 100644
--- a/netaddr_test.go
+++ b/netaddr_test.go
@@ -427,7 +427,7 @@ func TestIPWellKnown(t *testing.T) {
 	}
 }
 
-func TestLess(t *testing.T) {
+func TestLessCompare(t *testing.T) {
 	tests := []struct {
 		a, b IP
 		want bool
@@ -447,12 +447,29 @@ func TestLess(t *testing.T) {
 
 		{mustIP("::"), mustIP("0.0.0.0"), false},
 		{mustIP("0.0.0.0"), mustIP("::"), true},
+
+		{mustIP("::1%a"), mustIP("::1%b"), true},
+		{mustIP("::1%a"), mustIP("::1%a"), false},
+		{mustIP("::1%b"), mustIP("::1%a"), false},
 	}
 	for _, tt := range tests {
 		got := tt.a.Less(tt.b)
 		if got != tt.want {
 			t.Errorf("Less(%q, %q) = %v; want %v", tt.a, tt.b, got, tt.want)
 		}
+		cmp := tt.a.Compare(tt.b)
+		if got && cmp != -1 {
+			t.Errorf("Less(%q, %q) = true, but Compare = %v (not -1)", tt.a, tt.b, cmp)
+		}
+		if cmp < -1 || cmp > 1 {
+			t.Errorf("bogus Compare return value %v", cmp)
+		}
+		if cmp == 0 && tt.a != tt.b {
+			t.Errorf("Compare(%q, %q) = 0; but not equal", tt.a, tt.b)
+		}
+		if cmp == 1 && !tt.b.Less(tt.a) {
+			t.Errorf("Compare(%q, %q) = 1; but b.Less(a) isn't true", tt.a, tt.b)
+		}
 
 		// Also check inverse.
 		if got == tt.want && got {
@@ -1327,6 +1344,26 @@ func TestAs4(t *testing.T) {
 	}
 }
 
+func TestIPPrefixLastIP(t *testing.T) {
+	tests := []struct {
+		prefix, want string
+	}{
+		{"10.0.0.0/8", "10.255.255.255"},
+		{"10.0.0.0/9", "10.127.255.255"},
+		{"0.0.0.0/0", "255.255.255.255"},
+		{"0.0.0.0/32", "0.0.0.0"},
+		{"::/0", "ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff"},
+		{"::/128", "::"},
+	}
+	for _, tt := range tests {
+		p := mustIPPrefix(tt.prefix)
+		got := p.LastIP()
+		if got != mustIP(tt.want) {
+			t.Errorf("LastIP(%v) = %v; want %v", tt.prefix, got, tt.want)
+		}
+	}
+}
+
 func TestIPPrefixOverlaps(t *testing.T) {
 	pfx := mustIPPrefix
 	tests := []struct {
@@ -1368,3 +1405,299 @@ func TestIPPrefixOverlaps(t *testing.T) {
 		}
 	}
 }
+
+func pxv(cidrStrs ...string) (out []IPPrefix) {
+	for _, s := range cidrStrs {
+		out = append(out, mustIPPrefix(s))
+	}
+	return
+}
+
+func TestIPRangeSet(t *testing.T) {
+	tests := []struct {
+		name         string
+		f            func(s *IPRangeSet)
+		wantRanges   []IPRange
+		wantPrefixes []IPPrefix // non-nil to test
+	}{
+		{
+			name: "mix_family",
+			f: func(s *IPRangeSet) {
+				s.AddPrefix(mustIPPrefix("10.0.0.0/8"))
+				s.AddPrefix(mustIPPrefix("::/0"))
+				s.RemovePrefix(mustIPPrefix("10.2.0.0/16"))
+			},
+			wantRanges: []IPRange{
+				{mustIP("10.0.0.0"), mustIP("10.1.255.255")},
+				{mustIP("10.3.0.0"), mustIP("10.255.255.255")},
+				{mustIP("::"), mustIP("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff")},
+			},
+		},
+		{
+			name: "merge_adjacent",
+			f: func(s *IPRangeSet) {
+				s.AddPrefix(mustIPPrefix("10.0.0.0/8"))
+				s.AddPrefix(mustIPPrefix("11.0.0.0/8"))
+			},
+			wantRanges: []IPRange{
+				{mustIP("10.0.0.0"), mustIP("11.255.255.255")},
+			},
+			wantPrefixes: pxv("10.0.0.0/7"),
+		},
+		{
+			name: "remove_32",
+			f: func(s *IPRangeSet) {
+				s.AddPrefix(mustIPPrefix("10.0.0.0/8"))
+				s.RemovePrefix(mustIPPrefix("10.1.2.3/32"))
+			},
+			wantRanges: []IPRange{
+				{mustIP("10.0.0.0"), mustIP("10.1.2.2")},
+				{mustIP("10.1.2.4"), mustIP("10.255.255.255")},
+			},
+			wantPrefixes: pxv(
+				"10.0.0.0/16",
+				"10.1.0.0/23",
+				"10.1.2.0/31",
+				"10.1.2.2/32",
+				"10.1.2.4/30",
+				"10.1.2.8/29",
+				"10.1.2.16/28",
+				"10.1.2.32/27",
+				"10.1.2.64/26",
+				"10.1.2.128/25",
+				"10.1.3.0/24",
+				"10.1.4.0/22",
+				"10.1.8.0/21",
+				"10.1.16.0/20",
+				"10.1.32.0/19",
+				"10.1.64.0/18",
+				"10.1.128.0/17",
+				"10.2.0.0/15",
+				"10.4.0.0/14",
+				"10.8.0.0/13",
+				"10.16.0.0/12",
+				"10.32.0.0/11",
+				"10.64.0.0/10",
+				"10.128.0.0/9",
+			),
+		},
+		{
+			name: "remove_32_and_first_16",
+			f: func(s *IPRangeSet) {
+				s.AddPrefix(mustIPPrefix("10.0.0.0/8"))
+				s.RemovePrefix(mustIPPrefix("10.1.2.3/32"))
+				s.RemovePrefix(mustIPPrefix("10.0.0.0/16"))
+			},
+			wantRanges: []IPRange{
+				{mustIP("10.1.0.0"), mustIP("10.1.2.2")},
+				{mustIP("10.1.2.4"), mustIP("10.255.255.255")},
+			},
+			wantPrefixes: pxv(
+				"10.1.0.0/23",
+				"10.1.2.0/31",
+				"10.1.2.2/32",
+				"10.1.2.4/30",
+				"10.1.2.8/29",
+				"10.1.2.16/28",
+				"10.1.2.32/27",
+				"10.1.2.64/26",
+				"10.1.2.128/25",
+				"10.1.3.0/24",
+				"10.1.4.0/22",
+				"10.1.8.0/21",
+				"10.1.16.0/20",
+				"10.1.32.0/19",
+				"10.1.64.0/18",
+				"10.1.128.0/17",
+				"10.2.0.0/15",
+				"10.4.0.0/14",
+				"10.8.0.0/13",
+				"10.16.0.0/12",
+				"10.32.0.0/11",
+				"10.64.0.0/10",
+				"10.128.0.0/9",
+			),
+		},
+		{
+			name: "add_dup",
+			f: func(s *IPRangeSet) {
+				s.AddPrefix(mustIPPrefix("10.0.0.0/8"))
+				s.AddPrefix(mustIPPrefix("10.0.0.0/8"))
+			},
+			wantRanges: []IPRange{
+				{mustIP("10.0.0.0"), mustIP("10.255.255.255")},
+			},
+		},
+		{
+			name: "add_dup_subet",
+			f: func(s *IPRangeSet) {
+				s.AddPrefix(mustIPPrefix("10.0.0.0/8"))
+				s.AddPrefix(mustIPPrefix("10.0.0.0/16"))
+			},
+			wantRanges: []IPRange{
+				{mustIP("10.0.0.0"), mustIP("10.255.255.255")},
+			},
+		},
+		{
+			name: "add_remove_add",
+			f: func(s *IPRangeSet) {
+				s.AddPrefix(mustIPPrefix("10.0.0.0/8"))
+				s.RemovePrefix(mustIPPrefix("10.1.2.3/32"))
+				s.AddPrefix(mustIPPrefix("10.1.0.0/16")) // undoes prior line
+			},
+			wantRanges: []IPRange{
+				{mustIP("10.0.0.0"), mustIP("10.255.255.255")},
+			},
+		},
+		{
+			name: "remove_then_add",
+			f: func(s *IPRangeSet) {
+				s.RemovePrefix(mustIPPrefix("1.2.3.4/32")) // no-op
+				s.AddPrefix(mustIPPrefix("1.2.3.4/32"))
+			},
+			wantRanges: []IPRange{
+				{mustIP("1.2.3.4"), mustIP("1.2.3.4")},
+			},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			var s IPRangeSet
+			tt.f(&s)
+			got := s.Ranges()
+			t.Run("ranges", func(t *testing.T) {
+				if reflect.DeepEqual(got, tt.wantRanges) {
+					return
+				}
+				t.Error("failed. got:\n")
+				for _, v := range got {
+					t.Errorf("  %s -> %s", v.From, v.To)
+				}
+				t.Error("want:\n")
+				for _, v := range tt.wantRanges {
+					t.Errorf("  %s -> %s", v.From, v.To)
+				}
+			})
+			if tt.wantPrefixes != nil {
+				t.Run("prefixes", func(t *testing.T) {
+					got := s.Prefixes()
+					if got == nil {
+						got = []IPPrefix{}
+					}
+					if reflect.DeepEqual(got, tt.wantPrefixes) {
+						return
+					}
+					t.Error("failed. got:\n")
+					for _, v := range got {
+						t.Errorf("  %v", v)
+					}
+					t.Error("want:\n")
+					for _, v := range tt.wantPrefixes {
+						t.Errorf("  %v", v)
+					}
+				})
+			}
+		})
+	}
+}
+
+func TestRangePrefixes(t *testing.T) {
+	tests := []struct {
+		from string
+		to   string
+		want []IPPrefix
+	}{
+		{"0.0.0.0", "255.255.255.255", pxv("0.0.0.0/0")},
+		{"::", "ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff", pxv("::/0")},
+		{"10.0.0.0", "10.255.255.255", pxv("10.0.0.0/8")},
+		{"10.0.0.0", "10.127.255.255", pxv("10.0.0.0/9")},
+		{"0.0.0.4", "0.0.0.11", pxv(
+			// 4 0100
+			// 5 0101
+			// 6 0110
+			// 7 0111
+			// 8 1000
+			// 9 1001
+			//10 1010
+			//11 1011
+			"0.0.0.4/30",
+			"0.0.0.8/30",
+		)},
+		{"10.0.0.0", "11.10.255.255", pxv(
+			"10.0.0.0/8",
+			"11.0.0.0/13",
+			"11.8.0.0/15",
+			"11.10.0.0/16",
+		)},
+		{"1.2.3.5", "5.6.7.8", pxv(
+			"1.2.3.5/32",
+			"1.2.3.6/31",
+			"1.2.3.8/29",
+			"1.2.3.16/28",
+			"1.2.3.32/27",
+			"1.2.3.64/26",
+			"1.2.3.128/25",
+			"1.2.4.0/22",
+			"1.2.8.0/21",
+			"1.2.16.0/20",
+			"1.2.32.0/19",
+			"1.2.64.0/18",
+			"1.2.128.0/17",
+			"1.3.0.0/16",
+			"1.4.0.0/14",
+			"1.8.0.0/13",
+			"1.16.0.0/12",
+			"1.32.0.0/11",
+			"1.64.0.0/10",
+			"1.128.0.0/9",
+			"2.0.0.0/7",
+			"4.0.0.0/8",
+			"5.0.0.0/14",
+			"5.4.0.0/15",
+			"5.6.0.0/22",
+			"5.6.4.0/23",
+			"5.6.6.0/24",
+			"5.6.7.0/29",
+			"5.6.7.8/32",
+		)},
+	}
+	for _, tt := range tests {
+		r := IPRange{From: mustIP(tt.from), To: mustIP(tt.to)}
+		got := r.Prefixes()
+		if !reflect.DeepEqual(got, tt.want) {
+			t.Errorf("failed %s->%s. got:", tt.from, tt.to)
+			for _, v := range got {
+				t.Errorf("  %v", v)
+			}
+			t.Error("want:\n")
+			for _, v := range tt.want {
+				t.Errorf("  %v", v)
+			}
+		}
+	}
+}
+
+func TestIPNextPrior(t *testing.T) {
+	tests := []struct {
+		ip    IP
+		next  IP
+		prior IP
+	}{
+		{mustIP("10.0.0.1"), mustIP("10.0.0.2"), mustIP("10.0.0.0")},
+		{mustIP("10.0.0.255"), mustIP("10.0.1.0"), mustIP("10.0.0.254")},
+		{mustIP("254.255.255.255"), mustIP("255.0.0.0"), mustIP("254.255.255.254")},
+		{mustIP("255.255.255.255"), IP{}, mustIP("255.255.255.254")},
+		{mustIP("0.0.0.0"), mustIP("0.0.0.1"), IP{}},
+		{mustIP("::"), mustIP("::1"), IP{}},
+		{mustIP("ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff"), IP{}, mustIP("ffff:ffff:ffff:ffff:ffff:ffff:ffff:fffe")},
+	}
+	for _, tt := range tests {
+		gnext, gprior := tt.ip.Next(), tt.ip.Prior()
+		if gnext != tt.next {
+			t.Errorf("IP(%v).Next = %v; want %v", tt.ip, gnext, tt.next)
+		}
+		if gprior != tt.prior {
+			t.Errorf("IP(%v).Prior = %v; want %v", tt.ip, gprior, tt.prior)
+		}
+	}
+}