otrie/otrie_test.go

/*
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

package otrie

import (
	"fmt"
	"strings"
	"testing"

	"idio.link/go/netaddr/v2"
)

var prefixesStr string = `10.3.3.0/24
10.55.254.0/24
10.11.16.0/24
10.11.1.0/24
10.11.4.0/24
10.51.2.0/24
10.51.3.0/24
10.52.3.0/24
10.52.2.0/24
10.55.254.0/26
10.130.20.0/24
10.130.21.0/24
10.55.254.0/23
10.130.22.0/24
10.130.24.0/24
10.130.25.0/24
10.130.26.0/24
10.130.30.0/24
10.130.41.0/24
10.130.42.0/24
10.130.43.0/24
10.130.44.0/24
10.130.80.0/24
10.130.90.0/24
10.130.96.0/29
10.130.100.0/24
10.130.101.0/24
10.130.102.0/24
10.130.109.0/24
10.130.110.0/24
10.130.111.0/24
10.130.128.0/24
10.130.130.0/24
10.130.190.0/24
10.130.200.0/24
10.130.98.0/23
10.130.145.0/24
10.130.245.0/24
10.131.30.0/24
10.131.100.0/24
10.131.101.0/24
10.131.102.0/24
10.131.111.0/24
10.131.145.0/24
10.131.200.0/24
10.131.245.0/24
10.131.98.0/23
10.131.80.0/24
10.255.250.76/31
10.255.250.78/31
10.255.250.88/30
10.255.250.92/30
10.255.251.8/30
10.255.251.12/30
10.255.251.32/30
10.255.251.36/30
10.255.251.48/30
10.255.251.52/30
10.51.4.0/24
10.52.4.0/24`

func populatePrefixes(
	trie OTrie,
	prefixes []*netaddr.NetAddr,
) error {
	for _, l := range strings.Split(prefixesStr, "\n") {
		na, _ := netaddr.IP(l)
		prefixes = append(prefixes, na)
		if err := trie.AddPrefix(na); err != nil {
			return fmt.Errorf("populate prefixes: %v", err)
		}
	}
	return nil
}

func TestOTrieAddsPrefix(t *testing.T) {
	trie := NewOTrie()
	na1, err := netaddr.IP("192.0.2.0/24")
	if err != nil {
		t.Errorf("wtf1: %v", err)
		return
	}
	if err := trie.AddPrefix(na1); err != nil {
		t.Errorf("test ipv4 trie adds prefix: %v", err)
		return
	}
	na2, err := netaddr.IP("192.0.0.0/22")
	if err != nil {
		t.Errorf("wtf2: %v", err)
		return
	}
	if err := trie.AddPrefix(na2); err != nil {
		t.Errorf("test ipv4 trie adds prefix: %v", err)
		return
	}
	if !trie.Overlaps(
		netaddr.NewNetAddr([]byte{192, 0, 2, 129}, 32),
	) {
		t.Errorf("wtf3")
		return
	}
	if !trie.Overlaps(
		netaddr.NewNetAddr([]byte{192, 0, 3, 129}, 32),
	) {
		t.Errorf("wtf4")
		return
	}
	if trie.Overlaps(
		netaddr.NewNetAddr([]byte{192, 0, 4, 0}, 32),
	) {
		t.Errorf("wtf5")
		return
	}
}

func TestOTrieMatchesManyPrefixes(t *testing.T) {
	trie := NewOTrie()
	prefixes := make([]*netaddr.NetAddr, 0, 128)
	if err := populatePrefixes(trie, prefixes); err != nil {
		t.Errorf("test ipv4 trie matches many prefixes: %v", err)
	}
	for _, p := range prefixes {
		if !trie.Overlaps(p) {
			t.Errorf("failed to match %s by `overlaps` relation", p.String())
		}
	}
	for _, p := range prefixes {
		if !trie.Contains(p) {
			t.Errorf("failed to match %s by `contains` relation", p.String())
		}
	}
	if trie.Contains(
		netaddr.NewNetAddr([]byte{10, 255, 250, 76}, 30),
	) {
		t.Errorf("10.255.250.76/30 should not match!")
	}
	if !trie.Overlaps(
		netaddr.NewNetAddr([]byte{10, 51, 4, 0}, 24),
	) {
		t.Errorf("failed to match 10.51.4.0/24")
	}
}

func TestOTrieDoesNotMatchWrongPrefix(t *testing.T) {
	trie := NewOTrie()
	na, _ := netaddr.IP("170.12.0.0/20")
	_ = trie.AddPrefix(
		netaddr.NewNetAddr([]byte{192, 168, 55, 67}, 32),
	)
	if trie.Overlaps(na) {
		t.Errorf("wtf9000")
	}
}

func TestOTrieMatchesRanges(t *testing.T) {
	trie := NewOTrie()
	prefixes := make([]*netaddr.NetAddr, 0, 128)
	if err := populatePrefixes(trie, prefixes); err != nil {
		t.Errorf("test ipv4 trie matches many prefixes: %v", err)
	}
	start := netaddr.NewNetAddr([]byte{10, 53, 129, 30}, 32)
	end := netaddr.NewNetAddr([]byte{10, 128, 20, 65}, 32)
	if !trie.OverlapsRange(start, end) {
		t.Errorf("failed to match range %s-%s", start, end)
		return
	}
	end = netaddr.NewNetAddr([]byte{10, 55, 254, 0}, 32)
	if !trie.OverlapsRange(start, end) {
		t.Errorf("failed to match range %s-%s", start, end)
	}
	end = netaddr.NewNetAddr([]byte{10, 55, 253, 255}, 32)
	if trie.OverlapsRange(start, end) {
		t.Errorf("should not match range %s-%s", start, end)
	}
	start = netaddr.NewNetAddr([]byte{10, 52, 2, 255}, 32)
	if !trie.OverlapsRange(start, end) {
		t.Errorf("failed to match range %s-%s", start, end)
	}
	trie.AddPrefix(
		netaddr.NewNetAddr([]byte{192, 168, 55, 19}, 32),
	)
	start = netaddr.NewNetAddr([]byte{192, 168, 55, 240}, 32)
	end = netaddr.NewNetAddr([]byte{192, 168, 55, 246}, 32)
	if trie.OverlapsRange(start, end) {
		t.Errorf("should not match range %s-%s", start, end)
	}
}