如何检测两个 Golang net.IPNet 对象是否相交？

Question

如何检测两个 Golang net.IPNet 对象是否存在交集？

也就是说，如何检查第一个网络是否是第二个网络的子网或者第二个网络是否是第一个网络的子网。

Go 是否提供了任何可用于此特定任务的实用程序函数？

请参见下面的测试代码。

package main

import (
    "fmt"
    "net"
)

func main() {
    _, net1, _ := net.ParseCIDR("1.1.1.1/24")
    _, net2, _ := net.ParseCIDR("1.1.0.2/16")
    _, net3, _ := net.ParseCIDR("1.1.1.3/25")
    _, net4, _ := net.ParseCIDR("1.2.0.4/16")

    test(net1, net2, true)
    test(net2, net1, true)
    test(net1, net3, true)
    test(net3, net1, true)
    test(net1, net4, false)
    test(net4, net1, false)
}

func test(n1, n2 *net.IPNet, expect bool) {
    result := intersect(n1, n2)
    var label string
    if result == expect {
        label = "good"
    } else {
        label = "FAIL"
    }
    fmt.Printf("test intersect(%v,%v)=%v expected=%v => %s\n", n1, n2, result, expect, label)
}

func intersect(n1, n2 *net.IPNet) bool {
    return false // FIXME WRITEME
}

在Go Playground上运行它

- Everton

Answer 1

如果（根据您的测试用例所示），您不关心哪一侧包含哪一侧，而只是存在重叠，那么这应该就足够了。

func intersect(n1, n2 *net.IPNet) bool {
    return n2.Contains(n1.IP) || n1.Contains(n2.IP)
}

- dahc

---

怎么做呢？我很确定IP的最终值永远不会相同...你需要比较子网掩码或IP的子字符串。 - evanmcdonnal

@evanmcdonnal 我不确定你的意思。IPNet.IP是网络号，而不是被解析的IP，我们只需要包含性。 - dahc

在这种情况下应该能正常工作。我猜我需要读一下文档。 - evanmcdonnal

Answer 2

你可以利用 IP 地址（`net.IP`）和子网掩码（`net.IPMask`）实际上是包含二进制 IP 地址的字节片段（`[]byte`）这一事实。你可以使用通常的位运算符来处理网络地址及其掩码，以确定一个网络是否为另一个子网：

func intersect(n1, n2 *net.IPNet) bool {
    for i := range n1.IP {
        if n1.IP[i] & n1.Mask[i] != n2.IP[i] & n2.Mask[i] & n1.Mask[i] {
            return false
        }
    }
    return true
}

该函数缺少一些基本的合法性检查（例如，传递一个IPv4和一个IPv6地址会导致函数崩溃），但这个例子应该足以理解其要点。除了第一个测试用例外，它在你的问题的所有测试用例中都成功了。但毕竟，“1.1.0.2/16”并不是“1.1.1.1/24”的子网（情况相反）。

https://play.golang.org/p/Kur5n2hfLg

- helmbert

---

它在你的问题的所有测试用例中都成功了，除了第一个。但毕竟，1.1.0.2/16不是1.1.1.1/24的子网（反过来也一样）。谢谢。然而，我真的需要检测任何交集，如果n1是n2的子网，或者如果n2是n1的子网。我会更新问题以明确这一点。 - Everton

Answer 3

不必逐个比较每一对，使用地址前缀树将每个CIDR与所有其他CIDR进行比较更加高效。您可以使用IPAddress Go库来实现此操作。请注意，此代码同样适用于IPv6地址字符串。

import (
    "fmt"
    "github.com/seancfoley/ipaddress-go/ipaddr"
)

func main() {
    blockStrs := []string{
        "1.1.1.1/24", "1.1.0.2/16", "1.1.1.3/25", "1.2.0.4/16",
    }
    blocks := make([]*ipaddr.IPAddress, 0, len(blockStrs))
    for _, str := range blockStrs {
        blocks = append(blocks,
            ipaddr.NewIPAddressString(str).GetAddress().ToPrefixBlock())
    }
    trie := ipaddr.AddressTrie{}
    for _, block := range blocks {
        trie.Add(block.ToAddressBase())
    }
    fmt.Printf("trie is %v\n", trie)
    for _, block := range blocks {
        intersecting(trie, block)
    }
}

func intersecting(trie ipaddr.AddressTrie, cidr *ipaddr.IPAddress) {
    intersecting := make([]*ipaddr.IPAddress, 0, trie.Size())

    addr := cidr.ToAddressBase() // convert IPAddress to Address
    containingBlocks := trie.ElementsContaining(addr)
    containedBlocks := trie.ElementsContainedBy(addr)

    for block := containingBlocks.ShortestPrefixMatch(); 
        block != nil; block = block.Next() {
        next := block.GetKey().ToIP()
        if !next.Equal(cidr) {
            intersecting = append(intersecting, next)
        }
    }
    iter := containedBlocks.Iterator()
    for block := iter.Next(); block != nil; block = iter.Next() {
        next := block.ToIP()
        if !next.Equal(cidr) {
            intersecting = append(intersecting, next)
        }
    }
    fmt.Printf("CIDR %s intersects with %v\n", cidr, intersecting)
}

输出：

○ 0.0.0.0/0 (4)
└─○ 1.0.0.0/14 (4)
  ├─● 1.1.0.0/16 (3)
  │ └─● 1.1.1.0/24 (2)
  │   └─● 1.1.1.0/25 (1)
  └─● 1.2.0.0/16 (1)

CIDR 1.1.1.0/24 intersects with [1.1.0.0/16 1.1.1.0/25]
CIDR 1.1.0.0/16 intersects with [1.1.1.0/25 1.1.1.0/24]
CIDR 1.1.1.0/25 intersects with [1.1.0.0/16 1.1.1.0/24]
CIDR 1.2.0.0/16 intersects with []

- Sean F