Repository: inetaf/netaddr
Pull request #48 (2020-10-30 18:19:03)

Add method IPPrefix.Overlaps(IPPrefix) bool

bradfitz: cc @sailorfrag
bradfitz: PTAL

Patch:
diff --git a/netaddr.go b/netaddr.go
index 5bb5712..ea96436 100644
--- a/netaddr.go
+++ b/netaddr.go
@@ -471,6 +471,8 @@ func (ip IP) Prefix(bits uint8) (IPPrefix, error) {
 	if ip.ipImpl == nil {
 		return IPPrefix{}, nil
 	}
+	// TODO: optimize this to return ip directly if it's already
+	// masked and to not allocate a new IP.ipImpl.
 	return ip.prefix(bits)
 }
 
@@ -737,7 +739,7 @@ func (p IPPrefix) IPNet() *net.IPNet {
 // Contains reports whether the network p includes addr.
 //
 // An IPv4 address will not match an IPv6 prefix.
-// A 4-in-6 IP will not match an IPv4 prefix.
+// A v6-mapped IPv6 address will not match an IPv4 prefix.
 // A zero-value IP will not match any prefix.
 func (p IPPrefix) Contains(addr IP) bool {
 	var nn, ip []byte // these do not escape and so do not allocate
@@ -778,6 +780,46 @@ func (p IPPrefix) Contains(addr IP) bool {
 	return true
 }
 
+// Overlaps reports whether p and o overlap at all.
+//
+// If p and o are of different address families or either have a zero
+// IP, it reports false. Like the Contains method, a prefix with a
+// v6-mapped IPv4 IP is still treated as an IPv6 mask.
+//
+// If either has a Bits of zero, it returns true.
+func (p IPPrefix) Overlaps(o IPPrefix) bool {
+	if p.IP.IsZero() || o.IP.IsZero() {
+		return false
+	}
+	if p == o {
+		return true
+	}
+	if p.IP.Is4() != o.IP.Is4() {
+		return false
+	}
+	var minBits uint8
+	if p.Bits < o.Bits {
+		minBits = p.Bits
+	} else {
+		minBits = o.Bits
+	}
+	if minBits == 0 {
+		return true
+	}
+	// One of these Prefix calls might look redundant, but we don't require
+	// that p and o values are normalized (via IPPrefix.Masked) first,
+	// so the Prefix call on the one that's already minBits serves to zero
+	// out any remaining bits in IP.
+	var err error
+	if p, err = p.IP.Prefix(minBits); err != nil {
+		return false
+	}
+	if o, err = o.IP.Prefix(minBits); err != nil {
+		return false
+	}
+	return p.IP == o.IP
+}
+
 // MarshalText implements the encoding.TextMarshaler interface,
 // The encoding is the same as returned by String, with one exception:
 // If p is the zero value, the encoding is the empty string.


Test patch:
diff --git a/netaddr_test.go b/netaddr_test.go
index 93bfbb8..1970724 100644
--- a/netaddr_test.go
+++ b/netaddr_test.go
@@ -1323,3 +1323,45 @@ func TestAs4(t *testing.T) {
 		}
 	}
 }
+
+func TestIPPrefixOverlaps(t *testing.T) {
+	pfx := mustIPPrefix
+	tests := []struct {
+		a, b IPPrefix
+		want bool
+	}{
+		{IPPrefix{}, pfx("1.2.0.0/16"), false},  // first zero
+		{pfx("1.2.0.0/16"), IPPrefix{}, false},  // second zero
+		{pfx("::0/3"), pfx("0.0.0.0/3"), false}, // different families
+
+		{pfx("1.2.0.0/16"), pfx("1.2.0.0/16"), true}, // equal
+
+		{pfx("1.2.0.0/16"), pfx("1.2.3.0/24"), true},
+		{pfx("1.2.3.0/24"), pfx("1.2.0.0/16"), true},
+
+		{pfx("1.2.0.0/16"), pfx("1.2.3.0/32"), true},
+		{pfx("1.2.3.0/32"), pfx("1.2.0.0/16"), true},
+
+		// Match /0 either order
+		{pfx("1.2.3.0/32"), pfx("0.0.0.0/0"), true},
+		{pfx("0.0.0.0/0"), pfx("1.2.3.0/32"), true},
+
+		{pfx("1.2.3.0/32"), pfx("5.5.5.5/0"), true}, // normalization not required; /0 means true
+
+		// IPv6 overlapping
+		{pfx("5::1/128"), pfx("5::0/8"), true},
+		{pfx("5::0/8"), pfx("5::1/128"), true},
+
+		// IPv6 not overlapping
+		{pfx("1::1/128"), pfx("2::2/128"), false},
+		{pfx("0100::0/8"), pfx("::1/128"), false},
+
+		// v6-mapped v4 should not overlap with IPv4.
+		{IPPrefix{IP: IPv6Raw(mustIP("1.2.0.0").As16()), Bits: 16}, pfx("1.2.3.0/24"), false},
+	}
+	for i, tt := range tests {
+		if got := tt.a.Overlaps(tt.b); got != tt.want {
+			t.Errorf("%d. (%v).Overlaps(%v) = %v; want %v", i, tt.a, tt.b, got, tt.want)
+		}
+	}
+}