1// Copyright 2017 Google Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14package searchset 15 16import ( 17 "reflect" 18 "testing" 19 20 "github.com/google/licenseclassifier/stringclassifier/searchset/tokenizer" 21) 22 23const ( 24 shortPostmodernThesis = "In the works of Joyce, a predominant concept is the concept of semioticist" 25 postmodernThesis = `1. Joyce and neotextual modernist theory 26 27In the works of Joyce, a predominant concept is the concept of semioticist 28culture. The without/within distinction intrinsic to Finnegan's Wake emerges 29again in Ulysses, although in a more neomodern sense. 30` 31) 32 33func TestSearchSet_New(t *testing.T) { 34 tests := []struct { 35 description string 36 text string 37 granularity int 38 want *SearchSet 39 }{ 40 { 41 description: "Empty string", 42 text: "", 43 granularity: DefaultGranularity, 44 want: &SearchSet{ 45 Tokens: nil, 46 Hashes: make(tokenizer.Hash), 47 Checksums: nil, 48 ChecksumRanges: nil, 49 }, 50 }, 51 { 52 description: "Small string", 53 text: "Hello world", 54 granularity: 4, 55 want: &SearchSet{ 56 Tokens: tokenizer.Tokens{ 57 {Text: "Hello", Offset: 0}, 58 {Text: "world", Offset: 6}, 59 }, 60 Hashes: tokenizer.Hash{2346098258: tokenizer.TokenRanges{{Start: 0, End: 2}}}, 61 Checksums: []uint32{2346098258}, 62 ChecksumRanges: tokenizer.TokenRanges{{Start: 0, End: 2}}, 63 nodes: []*node{{2346098258, &tokenizer.TokenRange{Start: 0, End: 2}}}, 64 }, 65 }, 66 } 67 68 for _, tt := range tests { 69 if got := New(tt.text, tt.granularity); !reflect.DeepEqual(got, tt.want) { 70 t.Errorf("New(%q) = %+v, want %+v", tt.description, got, tt.want) 71 } 72 } 73} 74 75func TestSearchSet_NodeConstruction(t *testing.T) { 76 s := New(shortPostmodernThesis, DefaultGranularity) 77 want := []string{ 78 "[0:3]", "[1:4]", "[2:5]", "[3:6]", "[4:7]", "[5:8]", "[6:9]", 79 "[7:10]", "[8:11]", "[9:12]", "[10:13]", "[11:14]", 80 } 81 82 if len(s.nodes) != len(want) { 83 t.Errorf("Number of nodes %v, want %v", len(s.nodes), len(want)) 84 return 85 } 86 87 for i := 0; i < len(s.nodes); i++ { 88 if got := s.nodes[i].String(); got != want[i] { 89 t.Errorf("Nodes = got:\n%s\nwant:\n%s", got, want[i]) 90 } 91 } 92} 93 94func TestSearchSet_CoalesceTokenRanges(t *testing.T) { 95 tests := []struct { 96 description string 97 mr MatchRanges 98 want MatchRanges 99 }{ 100 { 101 description: "Non-overlapping Ranges", 102 mr: MatchRanges{ 103 {SrcStart: 0, SrcEnd: 27, TargetStart: 0, TargetEnd: 27}, 104 {SrcStart: 37, SrcEnd: 927, TargetStart: 37, TargetEnd: 927}, 105 }, 106 want: MatchRanges{ 107 {SrcStart: 0, SrcEnd: 27, TargetStart: 0, TargetEnd: 27}, 108 {SrcStart: 37, SrcEnd: 927, TargetStart: 37, TargetEnd: 927}, 109 }, 110 }, 111 { 112 description: "Identical Ranges", 113 mr: MatchRanges{ 114 {SrcStart: 0, SrcEnd: 37, TargetStart: 0, TargetEnd: 37}, 115 {SrcStart: 0, SrcEnd: 37, TargetStart: 0, TargetEnd: 37}, 116 }, 117 want: MatchRanges{{SrcStart: 0, SrcEnd: 37, TargetStart: 0, TargetEnd: 37}}, 118 }, 119 { 120 description: "Sequential Ranges", 121 mr: MatchRanges{ 122 {SrcStart: 0, SrcEnd: 37, TargetStart: 0, TargetEnd: 37}, 123 {SrcStart: 37, SrcEnd: 927, TargetStart: 37, TargetEnd: 927}, 124 }, 125 want: MatchRanges{{SrcStart: 0, SrcEnd: 927, TargetStart: 0, TargetEnd: 927}}, 126 }, 127 { 128 description: "Overlapping Ranges - Same Start", 129 mr: MatchRanges{ 130 {SrcStart: 0, SrcEnd: 37, TargetStart: 0, TargetEnd: 37}, 131 {SrcStart: 0, SrcEnd: 927, TargetStart: 0, TargetEnd: 927}, 132 }, 133 want: MatchRanges{{SrcStart: 0, SrcEnd: 927, TargetStart: 0, TargetEnd: 927}}, 134 }, 135 { 136 description: "Overlapping Ranges - Different Start", 137 mr: MatchRanges{ 138 {SrcStart: 0, SrcEnd: 37, TargetStart: 0, TargetEnd: 37}, 139 {SrcStart: 27, SrcEnd: 927, TargetStart: 27, TargetEnd: 927}, 140 }, 141 want: MatchRanges{{SrcStart: 0, SrcEnd: 927, TargetStart: 0, TargetEnd: 927}}, 142 }, 143 { 144 description: "Overlapping Ranges - Same End", 145 mr: MatchRanges{ 146 {SrcStart: 0, SrcEnd: 37, TargetStart: 0, TargetEnd: 37}, 147 {SrcStart: 27, SrcEnd: 37, TargetStart: 27, TargetEnd: 37}, 148 }, 149 want: MatchRanges{{SrcStart: 0, SrcEnd: 37, TargetStart: 0, TargetEnd: 37}}, 150 }, 151 { 152 description: "Completely Overlapping Ranges", 153 mr: MatchRanges{ 154 {SrcStart: 0, SrcEnd: 42, TargetStart: 0, TargetEnd: 42}, 155 {SrcStart: 27, SrcEnd: 37, TargetStart: 27, TargetEnd: 37}, 156 }, 157 want: MatchRanges{{SrcStart: 0, SrcEnd: 42, TargetStart: 0, TargetEnd: 42}}, 158 }, 159 } 160 161 for _, tt := range tests { 162 got := coalesceMatchRanges(tt.mr) 163 if !reflect.DeepEqual(got, tt.want) { 164 t.Errorf("CoalesceTokenRanges(%q) = %+v, want %+v", tt.description, got, tt.want) 165 } 166 } 167} 168 169func TestSearchSet_FindPotentialMatches(t *testing.T) { 170 known := New(postmodernThesis, DefaultGranularity) 171 172 size := len(postmodernThesis) 173 modified := "hello world " 174 modified += postmodernThesis[:size/3] + " hello world " 175 modified += postmodernThesis[size/3 : 2*size/3-4] 176 modified += postmodernThesis[2*size/3+7:] 177 unknown := New(modified, DefaultGranularity) 178 179 want := []MatchRanges{{ 180 {SrcStart: 0, SrcEnd: 15, TargetStart: 2, TargetEnd: 17}, 181 {SrcStart: 16, SrcEnd: 28, TargetStart: 21, TargetEnd: 33}, 182 {SrcStart: 31, SrcEnd: 46, TargetStart: 34, TargetEnd: 49}, 183 }} 184 185 got := FindPotentialMatches(known, unknown) 186 if len(got) != len(want) { 187 t.Errorf("Number of matches %v, want %v", len(got), len(want)) 188 } 189 if !reflect.DeepEqual(got, want) { 190 t.Errorf("Offsets = %+v, want %+v", got, want) 191 } 192 193 known = New(`again in Ulysses, although in a more neomodern sense. 194culture. The without/within distinction intrinsic to Finnegan's Wake emerges 195`, DefaultGranularity) 196 197 want = []MatchRanges{ 198 { 199 {SrcStart: 11, SrcEnd: 18, TargetStart: 26, TargetEnd: 33}, 200 {SrcStart: 21, SrcEnd: 25, TargetStart: 34, TargetEnd: 38}, 201 }, 202 {{SrcStart: 0, SrcEnd: 11, TargetStart: 38, TargetEnd: 49}}, 203 } 204 205 got = FindPotentialMatches(known, unknown) 206 if len(got) != len(want) { 207 t.Errorf("Number of matches %v, want %v", len(got), len(want)) 208 } 209 if !reflect.DeepEqual(got, want) { 210 t.Errorf("Offsets = %+v, want %+v", got, want) 211 } 212} 213 214func TestSearchSet_GetMatchedRanges(t *testing.T) { 215 const ( 216 source = "a b c d e f g c d e h i j" 217 target = "a b c _ _ c d e _ f g h _ c d e _ h i j" 218 ) 219 220 src := New(source, DefaultGranularity) 221 tar := New(target, DefaultGranularity) 222 223 want := []MatchRanges{ 224 { 225 {SrcStart: 0, SrcEnd: 3, TargetStart: 0, TargetEnd: 3}, 226 {SrcStart: 2, SrcEnd: 5, TargetStart: 5, TargetEnd: 8}, 227 {SrcStart: 7, SrcEnd: 10, TargetStart: 13, TargetEnd: 16}, 228 {SrcStart: 10, SrcEnd: 13, TargetStart: 17, TargetEnd: 20}, 229 }, 230 } 231 232 got := getMatchedRanges(src, tar) 233 if len(got) != len(want) { 234 t.Errorf("Number of matches %v, want %v", len(got), len(want)) 235 } 236 if !reflect.DeepEqual(got, want) { 237 t.Errorf("Match Ranges = %+v, want %+v", got, want) 238 } 239} 240 241func TestSearchSet_TargetMatchedRanges(t *testing.T) { 242 const ( 243 source = "a b c d e f g c d e h i j" 244 target = "a b c d e _ _ c d e _ f g h _ c d e _ h i j" 245 ) 246 247 src := New(source, DefaultGranularity) 248 tar := New(target, DefaultGranularity) 249 250 want := MatchRanges{ 251 {SrcStart: 0, SrcEnd: 3, TargetStart: 0, TargetEnd: 3}, 252 {SrcStart: 1, SrcEnd: 4, TargetStart: 1, TargetEnd: 4}, 253 {SrcStart: 2, SrcEnd: 5, TargetStart: 2, TargetEnd: 5}, 254 {SrcStart: 7, SrcEnd: 10, TargetStart: 2, TargetEnd: 5}, 255 {SrcStart: 2, SrcEnd: 5, TargetStart: 7, TargetEnd: 10}, 256 {SrcStart: 7, SrcEnd: 10, TargetStart: 7, TargetEnd: 10}, 257 {SrcStart: 2, SrcEnd: 5, TargetStart: 15, TargetEnd: 18}, 258 {SrcStart: 7, SrcEnd: 10, TargetStart: 15, TargetEnd: 18}, 259 {SrcStart: 10, SrcEnd: 13, TargetStart: 19, TargetEnd: 22}, 260 } 261 262 got := targetMatchedRanges(src, tar) 263 if len(got) != len(want) { 264 t.Errorf("Number of matches %v, want %v", len(got), len(want)) 265 } 266 if !reflect.DeepEqual(got, want) { 267 t.Errorf("Match Range = %+v, want %+v", got, want) 268 } 269} 270 271func TestSearchSet_UntangleSourceRanges(t *testing.T) { 272 tests := []struct { 273 description string 274 mr MatchRanges 275 want MatchRanges 276 }{ 277 { 278 description: "Single Match - In Order", 279 mr: MatchRanges{ 280 {SrcStart: 0, SrcEnd: 3, TargetStart: 10, TargetEnd: 13}, 281 {SrcStart: 5, SrcEnd: 10, TargetStart: 14, TargetEnd: 19}, 282 {SrcStart: 6, SrcEnd: 11, TargetStart: 15, TargetEnd: 20}, 283 }, 284 want: MatchRanges{ 285 {SrcStart: 0, SrcEnd: 3, TargetStart: 10, TargetEnd: 13}, 286 {SrcStart: 5, SrcEnd: 10, TargetStart: 14, TargetEnd: 19}, 287 {SrcStart: 6, SrcEnd: 11, TargetStart: 15, TargetEnd: 20}, 288 }, 289 }, 290 { 291 description: "Single Match - Out of Order", 292 mr: MatchRanges{ 293 {SrcStart: 0, SrcEnd: 3, TargetStart: 10, TargetEnd: 13}, 294 {SrcStart: 5, SrcEnd: 10, TargetStart: 14, TargetEnd: 19}, 295 {SrcStart: 15, SrcEnd: 20, TargetStart: 14, TargetEnd: 19}, 296 {SrcStart: 6, SrcEnd: 11, TargetStart: 15, TargetEnd: 20}, 297 {SrcStart: 5, SrcEnd: 10, TargetStart: 24, TargetEnd: 19}, 298 {SrcStart: 15, SrcEnd: 20, TargetStart: 24, TargetEnd: 19}, 299 {SrcStart: 23, SrcEnd: 29, TargetStart: 30, TargetEnd: 37}, 300 }, 301 want: MatchRanges{ 302 {SrcStart: 0, SrcEnd: 3, TargetStart: 10, TargetEnd: 13}, 303 {SrcStart: 5, SrcEnd: 10, TargetStart: 14, TargetEnd: 19}, 304 {SrcStart: 6, SrcEnd: 11, TargetStart: 15, TargetEnd: 20}, 305 {SrcStart: 15, SrcEnd: 20, TargetStart: 24, TargetEnd: 19}, 306 {SrcStart: 23, SrcEnd: 29, TargetStart: 30, TargetEnd: 37}, 307 }, 308 }, 309 { 310 description: "Multiple Match - In Order", 311 mr: MatchRanges{ 312 {SrcStart: 0, SrcEnd: 3, TargetStart: 10, TargetEnd: 13}, 313 {SrcStart: 5, SrcEnd: 10, TargetStart: 14, TargetEnd: 19}, 314 {SrcStart: 6, SrcEnd: 11, TargetStart: 15, TargetEnd: 20}, 315 {SrcStart: 0, SrcEnd: 3, TargetStart: 110, TargetEnd: 113}, 316 {SrcStart: 5, SrcEnd: 10, TargetStart: 114, TargetEnd: 119}, 317 {SrcStart: 6, SrcEnd: 11, TargetStart: 115, TargetEnd: 120}, 318 }, 319 want: MatchRanges{ 320 {SrcStart: 0, SrcEnd: 3, TargetStart: 10, TargetEnd: 13}, 321 {SrcStart: 5, SrcEnd: 10, TargetStart: 14, TargetEnd: 19}, 322 {SrcStart: 6, SrcEnd: 11, TargetStart: 15, TargetEnd: 20}, 323 {SrcStart: 0, SrcEnd: 3, TargetStart: 110, TargetEnd: 113}, 324 {SrcStart: 5, SrcEnd: 10, TargetStart: 114, TargetEnd: 119}, 325 {SrcStart: 6, SrcEnd: 11, TargetStart: 115, TargetEnd: 120}, 326 }, 327 }, 328 { 329 description: "Multiple Match - Out of Order", 330 mr: MatchRanges{ 331 {SrcStart: 0, SrcEnd: 3, TargetStart: 10, TargetEnd: 13}, 332 {SrcStart: 5, SrcEnd: 10, TargetStart: 14, TargetEnd: 19}, 333 {SrcStart: 15, SrcEnd: 20, TargetStart: 14, TargetEnd: 19}, 334 {SrcStart: 6, SrcEnd: 11, TargetStart: 15, TargetEnd: 20}, 335 {SrcStart: 5, SrcEnd: 10, TargetStart: 24, TargetEnd: 19}, 336 {SrcStart: 15, SrcEnd: 20, TargetStart: 24, TargetEnd: 19}, 337 {SrcStart: 23, SrcEnd: 29, TargetStart: 30, TargetEnd: 37}, 338 {SrcStart: 0, SrcEnd: 3, TargetStart: 110, TargetEnd: 113}, 339 {SrcStart: 5, SrcEnd: 10, TargetStart: 114, TargetEnd: 119}, 340 {SrcStart: 15, SrcEnd: 20, TargetStart: 114, TargetEnd: 119}, 341 {SrcStart: 6, SrcEnd: 11, TargetStart: 115, TargetEnd: 120}, 342 {SrcStart: 5, SrcEnd: 10, TargetStart: 124, TargetEnd: 119}, 343 {SrcStart: 15, SrcEnd: 20, TargetStart: 124, TargetEnd: 119}, 344 {SrcStart: 23, SrcEnd: 29, TargetStart: 130, TargetEnd: 137}, 345 }, 346 want: MatchRanges{ 347 {SrcStart: 0, SrcEnd: 3, TargetStart: 10, TargetEnd: 13}, 348 {SrcStart: 5, SrcEnd: 10, TargetStart: 14, TargetEnd: 19}, 349 {SrcStart: 6, SrcEnd: 11, TargetStart: 15, TargetEnd: 20}, 350 {SrcStart: 15, SrcEnd: 20, TargetStart: 24, TargetEnd: 19}, 351 {SrcStart: 23, SrcEnd: 29, TargetStart: 30, TargetEnd: 37}, 352 {SrcStart: 0, SrcEnd: 3, TargetStart: 110, TargetEnd: 113}, 353 {SrcStart: 5, SrcEnd: 10, TargetStart: 114, TargetEnd: 119}, 354 {SrcStart: 6, SrcEnd: 11, TargetStart: 115, TargetEnd: 120}, 355 {SrcStart: 15, SrcEnd: 20, TargetStart: 124, TargetEnd: 119}, 356 {SrcStart: 23, SrcEnd: 29, TargetStart: 130, TargetEnd: 137}, 357 }, 358 }, 359 } 360 361 for _, tt := range tests { 362 got := untangleSourceRanges(tt.mr) 363 if len(got) != len(tt.want) { 364 t.Errorf("Number of matches %v, want %v", len(got), len(tt.want)) 365 } 366 if !reflect.DeepEqual(got, tt.want) { 367 t.Errorf("UntangleSourceRanges(%q) = %v, want %v", tt.description, got, tt.want) 368 } 369 } 370} 371 372func TestSearchSet_SplitRanges(t *testing.T) { 373 tests := []struct { 374 description string 375 mr MatchRanges 376 want []MatchRanges 377 }{ 378 { 379 description: "Single Match Range", 380 mr: MatchRanges{ 381 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 382 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 383 }, 384 want: []MatchRanges{ 385 { 386 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 387 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 388 }, 389 }, 390 }, 391 { 392 description: "Two Match Ranges", 393 mr: MatchRanges{ 394 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 395 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 396 {SrcStart: 3, SrcEnd: 10, TargetStart: 108, TargetEnd: 115}, 397 {SrcStart: 23, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 398 }, 399 want: []MatchRanges{ 400 { 401 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 402 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 403 }, 404 { 405 {SrcStart: 3, SrcEnd: 10, TargetStart: 108, TargetEnd: 115}, 406 {SrcStart: 23, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 407 }, 408 }, 409 }, 410 } 411 412 for _, tt := range tests { 413 got := splitRanges(tt.mr) 414 if len(got) != len(tt.want) { 415 t.Errorf("Number of matches %v, want %v", len(got), len(tt.want)) 416 } 417 if !reflect.DeepEqual(got, tt.want) { 418 t.Errorf("SplitRanges(%q) = %v, want %v", tt.description, got, tt.want) 419 } 420 } 421} 422 423func TestSearchSet_MergeConsecutiveRanges(t *testing.T) { 424 tests := []struct { 425 description string 426 mr []MatchRanges 427 want []MatchRanges 428 }{ 429 { 430 description: "No Overlap", 431 mr: []MatchRanges{ 432 { 433 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 434 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 435 }, 436 { 437 {SrcStart: 3, SrcEnd: 10, TargetStart: 108, TargetEnd: 115}, 438 {SrcStart: 23, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 439 }, 440 }, 441 want: []MatchRanges{ 442 { 443 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 444 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 445 }, 446 { 447 {SrcStart: 3, SrcEnd: 10, TargetStart: 108, TargetEnd: 115}, 448 {SrcStart: 23, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 449 }, 450 }, 451 }, 452 { 453 description: "Consecutive Ranges No Overlap", 454 mr: []MatchRanges{ 455 { 456 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 457 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 458 }, 459 { 460 {SrcStart: 3, SrcEnd: 10, TargetStart: 35, TargetEnd: 41}, 461 {SrcStart: 23, SrcEnd: 30, TargetStart: 125, TargetEnd: 135}, 462 }, 463 }, 464 want: []MatchRanges{ 465 { 466 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 467 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 468 }, 469 { 470 {SrcStart: 3, SrcEnd: 10, TargetStart: 35, TargetEnd: 41}, 471 {SrcStart: 23, SrcEnd: 30, TargetStart: 125, TargetEnd: 135}, 472 }, 473 }, 474 }, 475 { 476 description: "Consecutive Ranges with First Element Overlap", 477 mr: []MatchRanges{ 478 { 479 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 480 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 481 }, 482 { 483 {SrcStart: 3, SrcEnd: 10, TargetStart: 34, TargetEnd: 41}, 484 {SrcStart: 33, SrcEnd: 40, TargetStart: 35, TargetEnd: 42}, 485 }, 486 }, 487 want: []MatchRanges{ 488 { 489 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 490 {SrcStart: 20, SrcEnd: 36, TargetStart: 25, TargetEnd: 41}, 491 {SrcStart: 33, SrcEnd: 40, TargetStart: 35, TargetEnd: 42}, 492 }, 493 }, 494 }, 495 { 496 description: "Consecutive Ranges with Overlap", 497 mr: []MatchRanges{ 498 { 499 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 500 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 501 }, 502 { 503 {SrcStart: 3, SrcEnd: 10, TargetStart: 34, TargetEnd: 41}, 504 {SrcStart: 33, SrcEnd: 40, TargetStart: 45, TargetEnd: 52}, 505 }, 506 }, 507 want: []MatchRanges{ 508 { 509 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 510 {SrcStart: 20, SrcEnd: 36, TargetStart: 25, TargetEnd: 41}, 511 {SrcStart: 33, SrcEnd: 40, TargetStart: 45, TargetEnd: 52}, 512 }, 513 }, 514 }, 515 { 516 description: "Consecutive Ranges with Previous Deep Overlap", 517 mr: []MatchRanges{ 518 { 519 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 520 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 521 {SrcStart: 120, SrcEnd: 130, TargetStart: 37, TargetEnd: 47}, 522 {SrcStart: 122, SrcEnd: 132, TargetStart: 39, TargetEnd: 49}, 523 }, 524 { 525 {SrcStart: 3, SrcEnd: 10, TargetStart: 34, TargetEnd: 41}, 526 {SrcStart: 33, SrcEnd: 40, TargetStart: 45, TargetEnd: 52}, 527 }, 528 }, 529 want: []MatchRanges{ 530 { 531 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 532 {SrcStart: 20, SrcEnd: 36, TargetStart: 25, TargetEnd: 41}, 533 {SrcStart: 33, SrcEnd: 40, TargetStart: 45, TargetEnd: 52}, 534 }, 535 }, 536 }, 537 { 538 description: "Consecutive Ranges with Deep Overlap", 539 mr: []MatchRanges{ 540 { 541 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 542 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 543 {SrcStart: 24, SrcEnd: 34, TargetStart: 29, TargetEnd: 39}, 544 {SrcStart: 120, SrcEnd: 130, TargetStart: 37, TargetEnd: 47}, 545 {SrcStart: 122, SrcEnd: 132, TargetStart: 39, TargetEnd: 49}, 546 }, 547 { 548 {SrcStart: 3, SrcEnd: 10, TargetStart: 26, TargetEnd: 33}, 549 {SrcStart: 5, SrcEnd: 12, TargetStart: 28, TargetEnd: 35}, 550 {SrcStart: 25, SrcEnd: 35, TargetStart: 31, TargetEnd: 41}, 551 }, 552 }, 553 want: []MatchRanges{ 554 { 555 {SrcStart: 0, SrcEnd: 10, TargetStart: 5, TargetEnd: 15}, 556 {SrcStart: 20, SrcEnd: 30, TargetStart: 25, TargetEnd: 35}, 557 {SrcStart: 24, SrcEnd: 34, TargetStart: 29, TargetEnd: 39}, 558 {SrcStart: 25, SrcEnd: 35, TargetStart: 31, TargetEnd: 41}, 559 }, 560 }, 561 }, 562 } 563 564 for _, tt := range tests { 565 got := mergeConsecutiveRanges(tt.mr) 566 if len(got) != len(tt.want) { 567 t.Errorf("Number of matches %v, want %v", len(got), len(tt.want)) 568 } 569 if !reflect.DeepEqual(got, tt.want) { 570 t.Errorf("SplitRanges(%q) = %v, want %v", tt.description, got, tt.want) 571 } 572 } 573} 574