pkg/cover: support compiler frontend coverage

Currently we only support compiler middle/backenend coverage
where we can map coverage points to source line.
Support better frontend coverage where coverage points map
to source code ranges start line:col - end line:col.

5 files changed, 222 insertions, 63 deletions

diff --git a/pkg/cover/backend/backend.go b/pkg/cover/backend/backend.go
index 6df629d74..13ae3b400 100644
--- a/pkg/cover/backend/backend.go
+++ b/pkg/cover/backend/backend.go
@@ -6,7 +6,6 @@ package backend
 import (
 	"fmt"
 
-	"github.com/google/syzkaller/pkg/symbolizer"
 	"github.com/google/syzkaller/sys/targets"
 )
 
@@ -34,10 +33,21 @@ type Symbol struct {
 }
 
 type Frame struct {
-	symbolizer.Frame
+	PC   uint64
+	Name string
 	Path string
+	Range
+}
+
+type Range struct {
+	StartLine int
+	StartCol  int
+	EndLine   int
+	EndCol    int
 }
 
+const LineEnd = 1 << 30
+
 func Make(target *targets.Target, vm, objDir, srcDir, buildDir string) (*Impl, error) {
 	if objDir == "" {
 		return nil, fmt.Errorf("kernel obj directory is not specified")
diff --git a/pkg/cover/backend/elf.go b/pkg/cover/backend/elf.go
index 848422c76..12231c2d0 100644
--- a/pkg/cover/backend/elf.go
+++ b/pkg/cover/backend/elf.go
@@ -293,9 +293,18 @@ func symbolize(target *targets.Target, objDir, srcDir, buildDir, obj string, pcs
 			err0 = res.err
 		}
 		for _, frame := range res.frames {
-			wrap := Frame{frame, ""}
-			wrap.File, wrap.Path = cleanPath(frame.File, objDir, srcDir, buildDir)
-			frames = append(frames, wrap)
+			name, path := cleanPath(frame.File, objDir, srcDir, buildDir)
+			frames = append(frames, Frame{
+				PC:   frame.PC,
+				Name: name,
+				Path: path,
+				Range: Range{
+					StartLine: frame.Line,
+					StartCol:  0,
+					EndLine:   frame.Line,
+					EndCol:    LineEnd,
+				},
+			})
 		}
 	}
 	if err0 != nil {
diff --git a/pkg/cover/cover_test.go b/pkg/cover/cover_test.go
index 7244ca186..2124fb3c8 100644
--- a/pkg/cover/cover_test.go
+++ b/pkg/cover/cover_test.go
@@ -9,6 +9,7 @@ import (
 	"testing"
 
 	"github.com/google/go-cmp/cmp"
+	"github.com/google/syzkaller/pkg/cover/backend"
 )
 
 func TestMergeDiff(t *testing.T) {
@@ -62,3 +63,58 @@ func TestMergeDiff(t *testing.T) {
 		})
 	}
 }
+
+func TestPerLineCoverage(t *testing.T) {
+	const End = backend.LineEnd
+	// Start line:col - end line:col.
+	// nolint
+	covered := []backend.Range{
+		// Just covered.
+		{1, 2, 1, 10},
+		{2, 1, 4, 10},
+		// Both covered and uncovered.
+		{10, 0, 10, 10},
+		{11, 20, 11, 30},
+		{12, 0, 12, End},
+		// Broken debug data.
+		{30, 10, 29, 20},
+		{31, 20, 30, 10},
+		{32, 10, 32, 5},
+		// Double covered.
+		{40, 10, 40, 20},
+		{40, 12, 40, 18},
+		{41, 10, 41, 20},
+		{41, 15, 41, 30},
+		{42, 20, 42, 30},
+		{42, 10, 42, 25},
+	}
+	// nolint
+	uncovered := []backend.Range{
+		{10, 20, 10, 30},
+		{11, 0, 11, 20},
+		{12, 0, 12, End},
+		// Only uncovered.
+		{20, 20, 21, 10},
+	}
+	want := map[int][]lineCoverChunk{
+		1:  {{2, false, false}, {10, true, false}, {End, false, false}},
+		2:  {{1, false, false}, {End, true, false}},
+		3:  {{End, true, false}},
+		4:  {{10, true, false}, {End, false, false}},
+		10: {{10, true, false}, {20, false, false}, {30, false, true}, {End, false, false}},
+		11: {{20, false, true}, {30, true, false}, {End, false, false}},
+		12: {{End, true, true}},
+		20: {{20, false, false}, {End, false, true}},
+		21: {{10, false, true}, {End, false, false}},
+		30: {{10, false, false}, {20, true, false}, {End, false, false}},
+		31: {{20, false, false}, {End, true, false}},
+		32: {{10, false, false}, {End, true, false}},
+		40: {{10, false, false}, {20, true, false}, {End, false, false}},
+		41: {{10, false, false}, {20, true, false}, {30, true, false}, {End, false, false}},
+		42: {{10, false, false}, {20, true, false}, {30, true, false}, {End, false, false}},
+	}
+	got := perLineCoverage(covered, uncovered)
+	if diff := cmp.Diff(want, got); diff != "" {
+		t.Fatal(diff)
+	}
+}
diff --git a/pkg/cover/html.go b/pkg/cover/html.go
index fb4f2ccf0..3b4d5ec43 100644
--- a/pkg/cover/html.go
+++ b/pkg/cover/html.go
@@ -16,6 +16,8 @@ import (
 	"sort"
 	"strconv"
 	"strings"
+
+	"github.com/google/syzkaller/pkg/cover/backend"
 )
 
 func (rg *ReportGenerator) DoHTML(w io.Writer, progs []Prog) error {
@@ -59,12 +61,12 @@ func (rg *ReportGenerator) DoHTML(w io.Writer, progs []Prog) error {
 			templateBase: templateBase{
 				Path:    path,
 				Name:    fname,
-				Total:   file.pcs,
-				Covered: file.covered,
+				Total:   file.totalPCs,
+				Covered: file.coveredPCs,
 			},
 		}
 		pos.Files = append(pos.Files, f)
-		if file.covered == 0 {
+		if file.coveredPCs == 0 {
 			continue
 		}
 		addFunctionCoverage(file, d)
@@ -138,35 +140,119 @@ func (rg *ReportGenerator) DoCSV(w io.Writer, progs []Prog) error {
 
 func fileContents(file *file, lines [][]byte) string {
 	var buf bytes.Buffer
+	lineCover := perLineCoverage(file.covered, file.uncovered)
+	htmlReplacer := strings.NewReplacer(">", "&gt;", "<", "&lt;", "&", "&amp;", "\t", "        ")
 	for i, ln := range lines {
-		cov, ok := file.lines[i+1]
-		prog, class, count := "", "", "     "
-		if ok {
-			if len(cov.count) != 0 {
-				if cov.prog != -1 {
-					prog = fmt.Sprintf("onclick='onProgClick(%v)'", cov.prog)
-				}
-				count = fmt.Sprintf("% 5v", len(cov.count))
+		prog, count := "", "     "
+		if line := file.lines[i+1]; len(line.progCount) != 0 {
+			prog = fmt.Sprintf("onclick='onProgClick(%v)'", line.progIndex)
+			count = fmt.Sprintf("% 5v", len(line.progCount))
+		}
+		buf.WriteString(fmt.Sprintf("<span class='count' %v>%v</span> ", prog, count))
+
+		start := 0
+		cover := append(lineCover[i+1], lineCoverChunk{End: backend.LineEnd})
+		for _, cov := range cover {
+			end := cov.End - 1
+			if end > len(ln) {
+				end = len(ln)
+			}
+			if end == start {
+				continue
+			}
+			chunk := htmlReplacer.Replace(string(ln[start:end]))
+			start = end
+			class := ""
+			if cov.Covered && cov.Uncovered {
+				class = "both"
+			} else if cov.Covered {
 				class = "covered"
-				if cov.uncovered {
-					class = "both"
-				}
-			} else {
+			} else if cov.Uncovered {
 				class = "uncovered"
+			} else {
+				buf.WriteString(chunk)
+				continue
 			}
+			buf.WriteString(fmt.Sprintf("<span class='%v'>%v</span>", class, chunk))
 		}
-		buf.WriteString(fmt.Sprintf("<span class='count' %v>%v</span>", prog, count))
-		if class == "" {
-			buf.WriteByte(' ')
-			buf.Write(ln)
-			buf.WriteByte('\n')
+		buf.WriteByte('\n')
+	}
+	return buf.String()
+}
+
+type lineCoverChunk struct {
+	End       int
+	Covered   bool
+	Uncovered bool
+}
+
+func perLineCoverage(covered, uncovered []backend.Range) map[int][]lineCoverChunk {
+	lines := make(map[int][]lineCoverChunk)
+	for _, r := range covered {
+		mergeRange(lines, r, true)
+	}
+	for _, r := range uncovered {
+		mergeRange(lines, r, false)
+	}
+	return lines
+}
+
+func mergeRange(lines map[int][]lineCoverChunk, r backend.Range, covered bool) {
+	// Don't panic on broken debug info, it is frequently broken.
+	if r.EndLine < r.StartLine {
+		r.EndLine = r.StartLine
+	}
+	if r.EndLine == r.StartLine && r.EndCol <= r.StartCol {
+		r.EndCol = backend.LineEnd
+	}
+	for line := r.StartLine; line <= r.EndLine; line++ {
+		start := 0
+		if line == r.StartLine {
+			start = r.StartCol
+		}
+		end := backend.LineEnd
+		if line == r.EndLine {
+			end = r.EndCol
+		}
+		ln := lines[line]
+		if ln == nil {
+			ln = append(ln, lineCoverChunk{End: backend.LineEnd})
+		}
+		lines[line] = mergeLine(ln, start, end, covered)
+	}
+}
+
+func mergeLine(chunks []lineCoverChunk, start, end int, covered bool) []lineCoverChunk {
+	var res []lineCoverChunk
+	chunkStart := 0
+	for _, chunk := range chunks {
+		if chunkStart >= end || chunk.End <= start {
+			res = append(res, chunk)
+		} else if covered && chunk.Covered || !covered && chunk.Uncovered {
+			res = append(res, chunk)
+		} else if chunkStart >= start && chunk.End <= end {
+			if covered {
+				chunk.Covered = true
+			} else {
+				chunk.Uncovered = true
+			}
+			res = append(res, chunk)
 		} else {
-			buf.WriteString(fmt.Sprintf("<span class='%v'> ", class))
-			buf.Write(ln)
-			buf.WriteString("</span>\n")
+			if chunkStart < start {
+				res = append(res, lineCoverChunk{start, chunk.Covered, chunk.Uncovered})
+			}
+			mid := end
+			if mid > chunk.End {
+				mid = chunk.End
+			}
+			res = append(res, lineCoverChunk{mid, chunk.Covered || covered, chunk.Uncovered || !covered})
+			if chunk.End > end {
+				res = append(res, lineCoverChunk{chunk.End, chunk.Covered, chunk.Uncovered})
+			}
 		}
+		chunkStart = chunk.End
 	}
-	return buf.String()
+	return res
 }
 
 func addFunctionCoverage(file *file, data *templateData) {
@@ -227,14 +313,13 @@ func parseFile(fn string) ([][]byte, error) {
 	if err != nil {
 		return nil, err
 	}
-	htmlReplacer := strings.NewReplacer(">", "&gt;", "<", "&lt;", "&", "&amp;", "\t", "        ")
 	var lines [][]byte
 	for {
 		idx := bytes.IndexByte(data, '\n')
 		if idx == -1 {
 			break
 		}
-		lines = append(lines, []byte(htmlReplacer.Replace(string(data[:idx]))))
+		lines = append(lines, data[:idx])
 		data = data[idx+1:]
 	}
 	if len(data) != 0 {
diff --git a/pkg/cover/report.go b/pkg/cover/report.go
index e7cf639fc..f4e88954e 100644
--- a/pkg/cover/report.go
+++ b/pkg/cover/report.go
@@ -42,11 +42,13 @@ func MakeReportGenerator(target *targets.Target, vm, objDir, srcDir, buildDir st
 }
 
 type file struct {
-	filename  string
-	lines     map[int]line
-	functions []*function
-	pcs       int
-	covered   int
+	filename   string
+	lines      map[int]line
+	functions  []*function
+	covered    []backend.Range
+	uncovered  []backend.Range
+	totalPCs   int
+	coveredPCs int
 }
 
 type function struct {
@@ -56,9 +58,8 @@ type function struct {
 }
 
 type line struct {
-	count     map[int]bool
-	prog      int
-	uncovered bool
+	progCount map[int]bool // program indices that cover this line
+	progIndex int          // example program index that covers this line
 }
 
 func (rg *ReportGenerator) prepareFileMap(progs []Prog) (map[string]*file, error) {
@@ -70,7 +71,7 @@ func (rg *ReportGenerator) prepareFileMap(progs []Prog) (map[string]*file, error
 		files[unit.Name] = &file{
 			filename: unit.Path,
 			lines:    make(map[int]line),
-			pcs:      len(unit.PCs),
+			totalPCs: len(unit.PCs),
 		}
 	}
 	progPCs := make(map[uint64]map[int]bool)
@@ -84,29 +85,27 @@ func (rg *ReportGenerator) prepareFileMap(progs []Prog) (map[string]*file, error
 	}
 	matchedPC := false
 	for _, frame := range rg.Frames {
-		f := getFile(files, frame.File, frame.Path)
-		ln := f.lines[frame.Line]
+		f := getFile(files, frame.Name, frame.Path)
+		ln := f.lines[frame.StartLine]
 		coveredBy := progPCs[frame.PC]
-		if len(coveredBy) != 0 {
-			// Covered frame.
-			matchedPC = true
-			if ln.count == nil {
-				ln.count = make(map[int]bool)
-				ln.prog = -1
-			}
-			for progIdx := range coveredBy {
-				ln.count[progIdx] = true
-				if ln.prog == -1 || len(progs[progIdx].Data) < len(progs[ln.prog].Data) {
-					ln.prog = progIdx
-				}
-			}
-		} else {
-			// Uncovered frame.
-			if !frame.Inline || len(ln.count) == 0 {
-				ln.uncovered = true
+		if len(coveredBy) == 0 {
+			f.uncovered = append(f.uncovered, frame.Range)
+			continue
+		}
+		// Covered frame.
+		f.covered = append(f.covered, frame.Range)
+		matchedPC = true
+		if ln.progCount == nil {
+			ln.progCount = make(map[int]bool)
+			ln.progIndex = -1
+		}
+		for progIndex := range coveredBy {
+			ln.progCount[progIndex] = true
+			if ln.progIndex == -1 || len(progs[progIndex].Data) < len(progs[ln.progIndex].Data) {
+				ln.progIndex = progIndex
 			}
 		}
-		f.lines[frame.Line] = ln
+		f.lines[frame.StartLine] = ln
 	}
 	if !matchedPC {
 		return nil, fmt.Errorf("coverage doesn't match any coverage callbacks")
@@ -115,7 +114,7 @@ func (rg *ReportGenerator) prepareFileMap(progs []Prog) (map[string]*file, error
 		f := files[unit.Name]
 		for _, pc := range unit.PCs {
 			if progPCs[pc] != nil {
-				f.covered++
+				f.coveredPCs++
 			}
 		}
 	}
@@ -187,8 +186,8 @@ func getFile(files map[string]*file, name, path string) *file {
 			filename: path,
 			lines:    make(map[int]line),
 			// Special mark for header files, if a file does not have coverage at all it is not shown.
-			pcs:     1,
-			covered: 1,
+			totalPCs:   1,
+			coveredPCs: 1,
 		}
 		files[name] = f
 	}