contentprovider_test.go

package zoekt

import (
	"bytes"
	"fmt"
	"testing"
	"testing/quick"
	"unicode/utf8"

	"github.com/google/go-cmp/cmp"
)

func getNewlines(data []byte) newlines {
	var locs []uint32
	for i, c := range data {
		if c == '\n' {
			locs = append(locs, uint32(i))
		}
	}
	return newlines{
		locs:     locs,
		fileSize: uint32(len(data)),
	}
}

func TestGetLines(t *testing.T) {
	contents := [][]byte{
		[]byte("one\ntwo\nthree\nfour"),
		[]byte("one\ntwo\nthree\nfour\n"),
		[]byte("one"),
		[]byte(""),
	}

	for _, content := range contents {
		t.Run("", func(t *testing.T) {
			newLines := getNewlines(content)
			lines := bytes.SplitAfter(content, []byte{'\n'})
			if len(lines) > 0 && len(lines[len(lines)-1]) == 0 {
				// A trailing newline does not delimit an empty line at the end of a file
				lines = lines[:len(lines)-1]
			}
			wantGetLines := func(low, high int) []byte {
				low--
				high--
				if low < 0 {
					low = 0
				}
				if low >= len(lines) {
					return nil
				}
				if high <= 0 {
					return nil
				}
				if high > len(lines) {
					high = len(lines)
				}
				return bytes.Join(lines[low:high], nil)
			}

			for low := -1; low <= len(lines)+2; low++ {
				for high := low; high <= len(lines)+2; high++ {
					want := wantGetLines(low, high)
					got := newLines.getLines(content, low, high)
					if d := cmp.Diff(string(want), string(got)); d != "" {
						t.Fatal(d)
					}
				}
			}
		})
	}
}

func TestAtOffset(t *testing.T) {
	cases := []struct {
		data       []byte
		offset     uint32
		lineNumber int
		lineStart  uint32
		lineEnd    uint32
	}{{
		data:       []byte("0.2.4.\n7.9.11.\n"),
		offset:     0,
		lineNumber: 1, lineStart: 0, lineEnd: 7,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		offset:     6,
		lineNumber: 1, lineStart: 0, lineEnd: 7,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		offset:     2,
		lineNumber: 1, lineStart: 0, lineEnd: 7,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		offset:     2,
		lineNumber: 1, lineStart: 0, lineEnd: 7,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		offset:     7,
		lineNumber: 2, lineStart: 7, lineEnd: 15,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		offset:     11,
		lineNumber: 2, lineStart: 7, lineEnd: 15,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		offset:     15,
		lineNumber: 3, lineStart: 15, lineEnd: 15,
	}, {
		data:       []byte("0.2.4.\n7.9.11."),
		offset:     7,
		lineNumber: 2, lineStart: 7, lineEnd: 14,
	}, {
		data:       []byte("\n\n"),
		offset:     0,
		lineNumber: 1, lineStart: 0, lineEnd: 1,
	}, {
		data:       []byte("\n\n"),
		offset:     1,
		lineNumber: 2, lineStart: 1, lineEnd: 2,
	}, {
		data:       []byte("\n\n"),
		offset:     3,
		lineNumber: 3, lineStart: 2, lineEnd: 2,
	}, {
		data:       []byte("line with no newlines"),
		offset:     3,
		lineNumber: 1, lineStart: 0, lineEnd: 21,
	}}

	for _, tt := range cases {
		t.Run("", func(t *testing.T) {
			nls := getNewlines(tt.data)
			gotLineNumber := nls.atOffset(tt.offset)
			if gotLineNumber != tt.lineNumber {
				t.Fatalf("expected line number %d, got %d", tt.lineNumber, gotLineNumber)
			}
			if gotLineStart := nls.lineStart(gotLineNumber); gotLineStart != tt.lineStart {
				t.Fatalf("expected line start %d, got %d", tt.lineStart, gotLineStart)
			}
			if gotLineEnd := nls.lineStart(gotLineNumber + 1); gotLineEnd != tt.lineEnd {
				t.Fatalf("expected line end %d, got %d", tt.lineEnd, gotLineEnd)
			}
		})
	}
}

func TestLineBounds(t *testing.T) {
	cases := []struct {
		data       []byte
		lineNumber int
		start      uint32
		end        uint32
	}{{
		data:       []byte("0.2.4.\n7.9.11.\n"),
		lineNumber: 1,
		start:      0, end: 7,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		lineNumber: 2,
		start:      7, end: 15,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		lineNumber: 0,
		start:      0, end: 0,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		lineNumber: -1,
		start:      0, end: 0,
	}, {
		data:       []byte("0.2.4.\n7.9.11.\n"),
		lineNumber: 202002,
		start:      15, end: 15,
	}, {
		data:       []byte("\n\n"),
		lineNumber: 1,
		start:      0, end: 1,
	}, {
		data:       []byte("\n\n"),
		lineNumber: 2,
		start:      1, end: 2,
	}, {
		data:       []byte("\n\n"),
		lineNumber: 3,
		start:      2, end: 2,
	}}

	for _, tt := range cases {
		t.Run("", func(t *testing.T) {
			nls := getNewlines(tt.data)
			gotStart := nls.lineStart(tt.lineNumber)
			if gotStart != tt.start {
				t.Fatalf("expected line start %d, got %d", tt.start, gotStart)
			}
			gotEnd := nls.lineStart(tt.lineNumber + 1)
			if gotEnd != tt.end {
				t.Fatalf("expected line end %d, got %d", tt.end, gotEnd)
			}
		})
	}
}

func TestChunkMatches(t *testing.T) {
	content := []byte(`0.2.4.6.8.10.
13.16.19.22.
26.29.32.35.
39.42.45.48.
52.55.58.61.
65.68.71.74.
78.81.84.87.
`)
	match_0_2 := &candidateMatch{byteOffset: 0, byteMatchSz: 2}
	match_6_10 := &candidateMatch{byteOffset: 6, byteMatchSz: 4}
	match_10_16 := &candidateMatch{byteOffset: 10, byteMatchSz: 6}
	match_19_42 := &candidateMatch{byteOffset: 19, byteMatchSz: 23}
	match_45_48 := &candidateMatch{byteOffset: 45, byteMatchSz: 3}
	match_71_72 := &candidateMatch{byteOffset: 71, byteMatchSz: 1}

	cases := []struct {
		candidateMatches []*candidateMatch
		numContextLines  int
		want             []candidateChunk
	}{{
		candidateMatches: []*candidateMatch{match_0_2},
		numContextLines:  0,
		want: []candidateChunk{{
			firstLine:  1,
			minOffset:  0,
			lastLine:   1,
			maxOffset:  2,
			candidates: []*candidateMatch{match_0_2},
		}},
	}, {
		candidateMatches: []*candidateMatch{match_0_2},
		numContextLines:  5,
		want: []candidateChunk{{
			firstLine:  1,
			minOffset:  0,
			lastLine:   1,
			maxOffset:  2,
			candidates: []*candidateMatch{match_0_2},
		}},
	}, {
		candidateMatches: []*candidateMatch{match_0_2, match_6_10},
		numContextLines:  0,
		want: []candidateChunk{{
			firstLine:  1,
			minOffset:  0,
			lastLine:   1,
			maxOffset:  10,
			candidates: []*candidateMatch{match_0_2, match_6_10},
		}},
	}, {
		candidateMatches: []*candidateMatch{match_0_2, match_10_16},
		numContextLines:  0,
		want: []candidateChunk{{
			firstLine:  1,
			minOffset:  0,
			lastLine:   2,
			maxOffset:  16,
			candidates: []*candidateMatch{match_0_2, match_10_16},
		}},
	}, {
		candidateMatches: []*candidateMatch{match_0_2, match_19_42},
		numContextLines:  0,
		want: []candidateChunk{{
			firstLine:  1,
			minOffset:  0,
			lastLine:   1,
			maxOffset:  2,
			candidates: []*candidateMatch{match_0_2},
		}, {
			firstLine:  2,
			minOffset:  19,
			lastLine:   4,
			maxOffset:  42,
			candidates: []*candidateMatch{match_19_42},
		}},
	}, {
		candidateMatches: []*candidateMatch{match_0_2, match_19_42},
		numContextLines:  1,
		want: []candidateChunk{{
			firstLine:  1,
			minOffset:  0,
			lastLine:   4,
			maxOffset:  42,
			candidates: []*candidateMatch{match_0_2, match_19_42},
		}},
	}, {
		candidateMatches: []*candidateMatch{
			match_0_2, match_19_42, match_45_48, match_71_72,
		},
		numContextLines: 0,
		want: []candidateChunk{{
			firstLine:  1,
			minOffset:  0,
			lastLine:   1,
			maxOffset:  2,
			candidates: []*candidateMatch{match_0_2},
		}, {
			firstLine:  2,
			minOffset:  19,
			lastLine:   4,
			maxOffset:  48,
			candidates: []*candidateMatch{match_19_42, match_45_48},
		}, {
			firstLine:  6,
			minOffset:  71,
			lastLine:   6,
			maxOffset:  72,
			candidates: []*candidateMatch{match_71_72},
		}},
	}, {
		candidateMatches: []*candidateMatch{
			match_0_2, match_19_42, match_45_48, match_71_72,
		},
		numContextLines: 100,
		want: []candidateChunk{{
			firstLine:  1,
			minOffset:  0,
			lastLine:   6,
			maxOffset:  72,
			candidates: []*candidateMatch{match_0_2, match_19_42, match_45_48, match_71_72},
		}},
	}}

	newlines := getNewlines(content)
	for _, tt := range cases {
		t.Run("", func(t *testing.T) {
			got := chunkCandidates(tt.candidateMatches, newlines, tt.numContextLines)
			if diff := cmp.Diff(fmt.Sprintf("%#v\n", tt.want), fmt.Sprintf("%#v\n", got)); diff != "" {
				t.Fatal(diff)
			}
		})
	}
}

func BenchmarkColumnHelper(b *testing.B) {
	// We simulate looking up columns of evenly spaced matches
	const matches = 10_000
	const match = "match"
	const space = "         "
	const dist = uint32(len(match) + len(space))
	data := bytes.Repeat([]byte(match+space), matches)

	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		columnHelper := columnHelper{data: data}

		lineOffset := 0
		offset := uint32(0)
		for offset < uint32(len(data)) {
			col := columnHelper.get(lineOffset, offset)
			if col != offset+1 {
				b.Fatal("column is not offset even though data is ASCII")
			}
			offset += dist
		}
	}
}

func TestColumnHelper(t *testing.T) {
	f := func(line0, line1 string) bool {
		data := []byte(line0 + line1)
		lineOffset := len(line0)

		columnHelper := columnHelper{data: data}

		// We check every second rune returns the correct answer
		offset := lineOffset
		column := 1
		for offset < len(data) {
			if column%2 == 0 {
				got := columnHelper.get(lineOffset, uint32(offset))
				if got != uint32(column) {
					return false
				}
			}
			_, size := utf8.DecodeRune(data[offset:])
			offset += size
			column++
		}

		return true
	}

	if err := quick.Check(f, nil); err != nil {
		t.Fatal(err)
	}

	// Corner cases

	// empty data, shouldn't happen but just in case it slips through
	ch := columnHelper{data: nil}
	if got := ch.get(0, 0); got != 1 {
		t.Fatal("empty data didn't return 1", got)
	}

	// Repeating a call to get should return the same value
	// empty data, shouldn't happen but just in case it slips through
	ch = columnHelper{data: []byte("hello\nworld")}
	if got := ch.get(6, 8); got != 3 {
		t.Fatal("unexpected value for third column on second line", got)
	}
	if got := ch.get(6, 8); got != 3 {
		t.Fatal("unexpected value for repeated call for third column on second line", got)
	}

	// Now make sure if we go backwards we do not incorrectly use the cache
	if got := ch.get(6, 6); got != 1 {
		t.Fatal("unexpected value for backwards call for first column on second line", got)
	}
}

func TestFindMaxOverlappingSection(t *testing.T) {
	secs := []DocumentSection{
		{Start: 0, End: 5},
		{Start: 8, End: 19},
		{Start: 22, End: 26},
	}
	// 012345678901234567890123456
	// [....[
	//         [..........[
	//                       [...[

	testcases := []struct {
		name        string
		off         uint32
		sz          uint32
		wantSecIdx  uint32
		wantOverlap bool
	}{
		{off: 0, sz: 1, wantSecIdx: 0, wantOverlap: true},
		{off: 0, sz: 5, wantSecIdx: 0, wantOverlap: true},
		{off: 2, sz: 5, wantSecIdx: 0, wantOverlap: true},
		{off: 2, sz: 50, wantSecIdx: 1, wantOverlap: true},
		{off: 4, sz: 10, wantSecIdx: 1, wantOverlap: true},
		{off: 5, sz: 15, wantSecIdx: 1, wantOverlap: true},
		{off: 18, sz: 10, wantSecIdx: 2, wantOverlap: true},

		// Prefer full overlap, break ties by preferring the earlier section
		{off: 10, sz: 20, wantSecIdx: 2, wantOverlap: true},
		{off: 0, sz: 100, wantSecIdx: 0, wantOverlap: true},
		{off: 8, sz: 100, wantSecIdx: 1, wantOverlap: true},
		{off: 0, sz: 10, wantSecIdx: 0, wantOverlap: true},
		{off: 16, sz: 10, wantSecIdx: 2, wantOverlap: true},

		// No overlap
		{off: 5, sz: 2, wantOverlap: false},
		{off: 20, sz: 1, wantOverlap: false},
		{off: 99, sz: 1, wantOverlap: false},
		{off: 0, sz: 0, wantOverlap: false},
	}

	for _, tt := range testcases {
		t.Run(fmt.Sprintf("off=%d size=%d", tt.off, tt.sz), func(t *testing.T) {
			got, haveOverlap := findMaxOverlappingSection(secs, tt.off, tt.sz)
			if haveOverlap != tt.wantOverlap {
				t.Fatalf("expected overlap %v, got %v", tt.wantOverlap, haveOverlap)
			}
			if got != tt.wantSecIdx {
				t.Fatalf("expected section %d, got %d", tt.wantSecIdx, got)
			}
		})
	}
}