| 1 | // Copyright 2021 The Go Authors. All rights reserved. |
|---|---|
| 2 | // Use of this source code is governed by a BSD-style |
| 3 | // license that can be found in the LICENSE file. |
| 4 | |
| 5 | //go:build go1.13 |
| 6 | // +build go1.13 |
| 7 | |
| 8 | package trie |
| 9 | |
| 10 | import ( |
| 11 | "math/rand" |
| 12 | "testing" |
| 13 | ) |
| 14 | |
| 15 | func TestMask(t *testing.T) { |
| 16 | for _, c := range []struct { |
| 17 | p prefix |
| 18 | b bitpos |
| 19 | want prefix |
| 20 | }{ |
| 21 | { |
| 22 | p: 0b00001000, |
| 23 | b: 0b00000100, |
| 24 | want: 0b00001011, |
| 25 | }, { |
| 26 | p: 0b01011011, |
| 27 | b: 0b00000000, |
| 28 | want: ^prefix(0), |
| 29 | }, { |
| 30 | p: 0b01011011, |
| 31 | b: 0b00000001, |
| 32 | want: 0b01011010, |
| 33 | }, { |
| 34 | p: 0b01011011, |
| 35 | b: 0b00000010, |
| 36 | want: 0b01011001, |
| 37 | }, { |
| 38 | p: 0b01011011, |
| 39 | b: 0b00000100, |
| 40 | want: 0b01011011, |
| 41 | }, { |
| 42 | p: 0b01011011, |
| 43 | b: 0b00001000, |
| 44 | want: 0b01010111, |
| 45 | }, { |
| 46 | p: 0b01011011, |
| 47 | b: 0b00010000, |
| 48 | want: 0b01001111, |
| 49 | }, { |
| 50 | p: 0b01011011, |
| 51 | b: 0b00100000, |
| 52 | want: 0b01011111, |
| 53 | }, { |
| 54 | p: 0b01011011, |
| 55 | b: 0b01000000, |
| 56 | want: 0b00111111, |
| 57 | }, { |
| 58 | p: 0b01011011, |
| 59 | b: 0b01000000, |
| 60 | want: 0b00111111, |
| 61 | }, { |
| 62 | p: 0b01011011, |
| 63 | b: 0b10000000, |
| 64 | want: 0b01111111, |
| 65 | }, |
| 66 | } { |
| 67 | if got := mask(c.p, c.b); got != c.want { |
| 68 | t.Errorf("mask(%#b,%#b) got %#b. want %#b", c.p, c.b, got, c.want) |
| 69 | } |
| 70 | } |
| 71 | } |
| 72 | |
| 73 | func TestMaskImpotent(t *testing.T) { |
| 74 | // test mask(mask(p, b), b) == mask(p,b) |
| 75 | for _, p := range []prefix{ |
| 76 | 0b0, 0b1, 0b100, ^prefix(0b0), ^prefix(0b10), |
| 77 | } { |
| 78 | for _, b := range []bitpos{ |
| 79 | 0, 0b1, 1 << 2, 1 << 63, |
| 80 | } { |
| 81 | once := mask(p, b) |
| 82 | twice := mask(once, b) |
| 83 | if once != twice { |
| 84 | t.Errorf("mask(mask(%#b,%#b), %#b) != mask(%#b,%#b) got %#b. want %#b", |
| 85 | p, b, b, p, b, twice, once) |
| 86 | } |
| 87 | } |
| 88 | } |
| 89 | } |
| 90 | |
| 91 | func TestMatchPrefix(t *testing.T) { |
| 92 | for _, c := range []struct { |
| 93 | k prefix |
| 94 | p prefix |
| 95 | b bitpos |
| 96 | }{ |
| 97 | { |
| 98 | k: 0b1000, |
| 99 | p: 0b1011, |
| 100 | b: 0b0100, |
| 101 | }, { |
| 102 | k: 0b1001, |
| 103 | p: 0b1011, |
| 104 | b: 0b0100, |
| 105 | }, { |
| 106 | k: 0b1010, |
| 107 | p: 0b1011, |
| 108 | b: 0b0100, |
| 109 | }, { |
| 110 | k: 0b1011, |
| 111 | p: 0b1011, |
| 112 | b: 0b0100, |
| 113 | }, { |
| 114 | k: 0b1100, |
| 115 | p: 0b1011, |
| 116 | b: 0b0100, |
| 117 | }, { |
| 118 | k: 0b1101, |
| 119 | p: 0b1011, |
| 120 | b: 0b0100, |
| 121 | }, { |
| 122 | k: 0b1110, |
| 123 | p: 0b1011, |
| 124 | b: 0b0100, |
| 125 | }, { |
| 126 | k: 0b1111, |
| 127 | p: 0b1011, |
| 128 | b: 0b0100, |
| 129 | }, |
| 130 | } { |
| 131 | if !matchPrefix(c.k, c.p, c.b) { |
| 132 | t.Errorf("matchPrefix(%#b, %#b,%#b) should be true", c.k, c.p, c.b) |
| 133 | } |
| 134 | } |
| 135 | } |
| 136 | |
| 137 | func TestNotMatchPrefix(t *testing.T) { |
| 138 | for _, c := range []struct { |
| 139 | k prefix |
| 140 | p prefix |
| 141 | b bitpos |
| 142 | }{ |
| 143 | { |
| 144 | k: 0b0000, |
| 145 | p: 0b1011, |
| 146 | b: 0b0100, |
| 147 | }, { |
| 148 | k: 0b0010, |
| 149 | p: 0b1011, |
| 150 | b: 0b0100, |
| 151 | }, |
| 152 | } { |
| 153 | if matchPrefix(c.k, c.p, c.b) { |
| 154 | t.Errorf("matchPrefix(%#b, %#b,%#b) should be false", c.k, c.p, c.b) |
| 155 | } |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | func TestBranchingBit(t *testing.T) { |
| 160 | for _, c := range []struct { |
| 161 | x prefix |
| 162 | y prefix |
| 163 | want bitpos |
| 164 | }{ |
| 165 | { |
| 166 | x: 0b0000, |
| 167 | y: 0b1011, |
| 168 | want: 0b1000, |
| 169 | }, { |
| 170 | x: 0b1010, |
| 171 | y: 0b1011, |
| 172 | want: 0b0001, |
| 173 | }, { |
| 174 | x: 0b1011, |
| 175 | y: 0b1111, |
| 176 | want: 0b0100, |
| 177 | }, { |
| 178 | x: 0b1011, |
| 179 | y: 0b1001, |
| 180 | want: 0b0010, |
| 181 | }, |
| 182 | } { |
| 183 | if got := branchingBit(c.x, c.y); got != c.want { |
| 184 | t.Errorf("branchingBit(%#b, %#b,) is not expected value. got %#b want %#b", |
| 185 | c.x, c.y, got, c.want) |
| 186 | } |
| 187 | } |
| 188 | } |
| 189 | |
| 190 | func TestZeroBit(t *testing.T) { |
| 191 | for _, c := range []struct { |
| 192 | k prefix |
| 193 | b bitpos |
| 194 | }{ |
| 195 | { |
| 196 | k: 0b1000, |
| 197 | b: 0b0100, |
| 198 | }, { |
| 199 | k: 0b1001, |
| 200 | b: 0b0100, |
| 201 | }, { |
| 202 | k: 0b1010, |
| 203 | b: 0b0100, |
| 204 | }, |
| 205 | } { |
| 206 | if !zeroBit(c.k, c.b) { |
| 207 | t.Errorf("zeroBit(%#b, %#b) should be true", c.k, c.b) |
| 208 | } |
| 209 | } |
| 210 | } |
| 211 | func TestZeroBitFails(t *testing.T) { |
| 212 | for _, c := range []struct { |
| 213 | k prefix |
| 214 | b bitpos |
| 215 | }{ |
| 216 | { |
| 217 | k: 0b1000, |
| 218 | b: 0b1000, |
| 219 | }, { |
| 220 | k: 0b1001, |
| 221 | b: 0b0001, |
| 222 | }, { |
| 223 | k: 0b1010, |
| 224 | b: 0b0010, |
| 225 | }, { |
| 226 | k: 0b1011, |
| 227 | b: 0b0001, |
| 228 | }, |
| 229 | } { |
| 230 | if zeroBit(c.k, c.b) { |
| 231 | t.Errorf("zeroBit(%#b, %#b) should be false", c.k, c.b) |
| 232 | } |
| 233 | } |
| 234 | } |
| 235 | |
| 236 | func TestOrd(t *testing.T) { |
| 237 | a := bitpos(0b0010) |
| 238 | b := bitpos(0b1000) |
| 239 | if ord(a, b) { |
| 240 | t.Errorf("ord(%#b, %#b) should be false", a, b) |
| 241 | } |
| 242 | if !ord(b, a) { |
| 243 | t.Errorf("ord(%#b, %#b) should be true", b, a) |
| 244 | } |
| 245 | if ord(a, a) { |
| 246 | t.Errorf("ord(%#b, %#b) should be false", a, a) |
| 247 | } |
| 248 | if !ord(a, 0) { |
| 249 | t.Errorf("ord(%#b, %#b) should be true", a, 0) |
| 250 | } |
| 251 | } |
| 252 | |
| 253 | func TestPrefixesOverlapLemma(t *testing.T) { |
| 254 | // test |
| 255 | // mask(p, fbb) == mask(q, fbb) |
| 256 | // iff |
| 257 | // m > n && matchPrefix(q, p, m) or (note: big endian encoding) |
| 258 | // m < n && matchPrefix(p, q, n) or (note: big endian encoding) |
| 259 | // m ==n && p == q |
| 260 | |
| 261 | // Case 1: mask(p, fbb) == mask(q, fbb) => m > n && matchPrefix(q, p, m) |
| 262 | m, n := bitpos(1<<2), bitpos(1<<1) |
| 263 | p, q := mask(0b100, m), mask(0b010, n) |
| 264 | if !(prefixesOverlap(p, m, q, n) && m > n && matchPrefix(q, p, m)) { |
| 265 | t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold", |
| 266 | p, m, q, n) |
| 267 | } |
| 268 | // Case 2: mask(p, fbb) == mask(q, fbb) => m < n && matchPrefix(p, q, n) |
| 269 | m, n = bitpos(1<<2), bitpos(1<<3) |
| 270 | p, q = mask(0b100, m), mask(0b1000, n) |
| 271 | if !(prefixesOverlap(p, m, q, n) && m < n && matchPrefix(p, q, n)) { |
| 272 | t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold", |
| 273 | p, m, q, n) |
| 274 | } |
| 275 | // Case 3: mask(p, fbb) == mask(q, fbb) => m < n && matchPrefix(p, q, n) |
| 276 | m, n = bitpos(1<<2), bitpos(1<<2) |
| 277 | p, q = mask(0b100, m), mask(0b001, n) |
| 278 | if !(prefixesOverlap(p, m, q, n) && m == n && p == q) { |
| 279 | t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold", |
| 280 | p, m, q, n) |
| 281 | } |
| 282 | // Case 4: mask(p, fbb) != mask(q, fbb) |
| 283 | m, n = bitpos(1<<1), bitpos(1<<1) |
| 284 | p, q = mask(0b100, m), mask(0b001, n) |
| 285 | if prefixesOverlap(p, m, q, n) || |
| 286 | (m > n && matchPrefix(q, p, m)) || |
| 287 | (m < n && matchPrefix(p, q, n)) || |
| 288 | (m == n && p == q) { |
| 289 | t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) lemma does not hold", |
| 290 | p, m, q, n) |
| 291 | } |
| 292 | |
| 293 | // Do a few more random cases |
| 294 | r := rand.New(rand.NewSource(123)) |
| 295 | N := 2000 |
| 296 | for i := 0; i < N; i++ { |
| 297 | m := bitpos(1 << (r.Uint64() % (64 + 1))) |
| 298 | n := bitpos(1 << (r.Uint64() % (64 + 1))) |
| 299 | |
| 300 | p := mask(prefix(r.Uint64()), m) |
| 301 | q := mask(prefix(r.Uint64()), n) |
| 302 | |
| 303 | lhs := prefixesOverlap(p, m, q, n) |
| 304 | rhs := (m > n && matchPrefix(q, p, m)) || |
| 305 | (m < n && matchPrefix(p, q, n)) || |
| 306 | (m == n && p == q) |
| 307 | |
| 308 | if lhs != rhs { |
| 309 | t.Errorf("prefixesOverlap(%#b, %#b, %#b, %#b) != <lemma> got %v. want %v", |
| 310 | p, m, q, n, lhs, rhs) |
| 311 | } |
| 312 | } |
| 313 | } |
| 314 |
Members