1// Copyright 2013 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// Package cover provides support for parsing coverage profiles
6// generated by "go test -coverprofile=cover.out".
7package cover // import "golang.org/x/tools/cover"
8
9import (
10	"bufio"
11	"errors"
12	"fmt"
13	"math"
14	"os"
15	"sort"
16	"strconv"
17	"strings"
18)
19
20// Profile represents the profiling data for a specific file.
21type Profile struct {
22	FileName string
23	Mode     string
24	Blocks   []ProfileBlock
25}
26
27// ProfileBlock represents a single block of profiling data.
28type ProfileBlock struct {
29	StartLine, StartCol int
30	EndLine, EndCol     int
31	NumStmt, Count      int
32}
33
34type byFileName []*Profile
35
36func (p byFileName) Len() int           { return len(p) }
37func (p byFileName) Less(i, j int) bool { return p[i].FileName < p[j].FileName }
38func (p byFileName) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
39
40// ParseProfiles parses profile data in the specified file and returns a
41// Profile for each source file described therein.
42func ParseProfiles(fileName string) ([]*Profile, error) {
43	pf, err := os.Open(fileName)
44	if err != nil {
45		return nil, err
46	}
47	defer pf.Close()
48
49	files := make(map[string]*Profile)
50	buf := bufio.NewReader(pf)
51	// First line is "mode: foo", where foo is "set", "count", or "atomic".
52	// Rest of file is in the format
53	//	encoding/base64/base64.go:34.44,37.40 3 1
54	// where the fields are: name.go:line.column,line.column numberOfStatements count
55	s := bufio.NewScanner(buf)
56	mode := ""
57	for s.Scan() {
58		line := s.Text()
59		if mode == "" {
60			const p = "mode: "
61			if !strings.HasPrefix(line, p) || line == p {
62				return nil, fmt.Errorf("bad mode line: %v", line)
63			}
64			mode = line[len(p):]
65			continue
66		}
67		fn, b, err := parseLine(line)
68		if err != nil {
69			return nil, fmt.Errorf("line %q doesn't match expected format: %v", line, err)
70		}
71		p := files[fn]
72		if p == nil {
73			p = &Profile{
74				FileName: fn,
75				Mode:     mode,
76			}
77			files[fn] = p
78		}
79		p.Blocks = append(p.Blocks, b)
80	}
81	if err := s.Err(); err != nil {
82		return nil, err
83	}
84	for _, p := range files {
85		sort.Sort(blocksByStart(p.Blocks))
86		// Merge samples from the same location.
87		j := 1
88		for i := 1; i < len(p.Blocks); i++ {
89			b := p.Blocks[i]
90			last := p.Blocks[j-1]
91			if b.StartLine == last.StartLine &&
92				b.StartCol == last.StartCol &&
93				b.EndLine == last.EndLine &&
94				b.EndCol == last.EndCol {
95				if b.NumStmt != last.NumStmt {
96					return nil, fmt.Errorf("inconsistent NumStmt: changed from %d to %d", last.NumStmt, b.NumStmt)
97				}
98				if mode == "set" {
99					p.Blocks[j-1].Count |= b.Count
100				} else {
101					p.Blocks[j-1].Count += b.Count
102				}
103				continue
104			}
105			p.Blocks[j] = b
106			j++
107		}
108		p.Blocks = p.Blocks[:j]
109	}
110	// Generate a sorted slice.
111	profiles := make([]*Profile, 0, len(files))
112	for _, profile := range files {
113		profiles = append(profiles, profile)
114	}
115	sort.Sort(byFileName(profiles))
116	return profiles, nil
117}
118
119// parseLine parses a line from a coverage file.
120// It is equivalent to the regex
121// ^(.+):([0-9]+)\.([0-9]+),([0-9]+)\.([0-9]+) ([0-9]+) ([0-9]+)$
122//
123// However, it is much faster: https://golang.org/cl/179377
124func parseLine(l string) (fileName string, block ProfileBlock, err error) {
125	end := len(l)
126
127	b := ProfileBlock{}
128	b.Count, end, err = seekBack(l, ' ', end, "Count")
129	if err != nil {
130		return "", b, err
131	}
132	b.NumStmt, end, err = seekBack(l, ' ', end, "NumStmt")
133	if err != nil {
134		return "", b, err
135	}
136	b.EndCol, end, err = seekBack(l, '.', end, "EndCol")
137	if err != nil {
138		return "", b, err
139	}
140	b.EndLine, end, err = seekBack(l, ',', end, "EndLine")
141	if err != nil {
142		return "", b, err
143	}
144	b.StartCol, end, err = seekBack(l, '.', end, "StartCol")
145	if err != nil {
146		return "", b, err
147	}
148	b.StartLine, end, err = seekBack(l, ':', end, "StartLine")
149	if err != nil {
150		return "", b, err
151	}
152	fn := l[0:end]
153	if fn == "" {
154		return "", b, errors.New("a FileName cannot be blank")
155	}
156	return fn, b, nil
157}
158
159// seekBack searches backwards from end to find sep in l, then returns the
160// value between sep and end as an integer.
161// If seekBack fails, the returned error will reference what.
162func seekBack(l string, sep byte, end int, what string) (value int, nextSep int, err error) {
163	// Since we're seeking backwards and we know only ASCII is legal for these values,
164	// we can ignore the possibility of non-ASCII characters.
165	for start := end - 1; start >= 0; start-- {
166		if l[start] == sep {
167			i, err := strconv.Atoi(l[start+1 : end])
168			if err != nil {
169				return 0, 0, fmt.Errorf("couldn't parse %q: %v", what, err)
170			}
171			if i < 0 {
172				return 0, 0, fmt.Errorf("negative values are not allowed for %s, found %d", what, i)
173			}
174			return i, start, nil
175		}
176	}
177	return 0, 0, fmt.Errorf("couldn't find a %s before %s", string(sep), what)
178}
179
180type blocksByStart []ProfileBlock
181
182func (b blocksByStart) Len() int      { return len(b) }
183func (b blocksByStart) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
184func (b blocksByStart) Less(i, j int) bool {
185	bi, bj := b[i], b[j]
186	return bi.StartLine < bj.StartLine || bi.StartLine == bj.StartLine && bi.StartCol < bj.StartCol
187}
188
189// Boundary represents the position in a source file of the beginning or end of a
190// block as reported by the coverage profile. In HTML mode, it will correspond to
191// the opening or closing of a <span> tag and will be used to colorize the source
192type Boundary struct {
193	Offset int     // Location as a byte offset in the source file.
194	Start  bool    // Is this the start of a block?
195	Count  int     // Event count from the cover profile.
196	Norm   float64 // Count normalized to [0..1].
197	Index  int     // Order in input file.
198}
199
200// Boundaries returns a Profile as a set of Boundary objects within the provided src.
201func (p *Profile) Boundaries(src []byte) (boundaries []Boundary) {
202	// Find maximum count.
203	max := 0
204	for _, b := range p.Blocks {
205		if b.Count > max {
206			max = b.Count
207		}
208	}
209	// Divisor for normalization.
210	divisor := math.Log(float64(max))
211
212	// boundary returns a Boundary, populating the Norm field with a normalized Count.
213	index := 0
214	boundary := func(offset int, start bool, count int) Boundary {
215		b := Boundary{Offset: offset, Start: start, Count: count, Index: index}
216		index++
217		if !start || count == 0 {
218			return b
219		}
220		if max <= 1 {
221			b.Norm = 0.8 // Profile is in"set" mode; we want a heat map. Use cov8 in the CSS.
222		} else if count > 0 {
223			b.Norm = math.Log(float64(count)) / divisor
224		}
225		return b
226	}
227
228	line, col := 1, 2 // TODO: Why is this 2?
229	for si, bi := 0, 0; si < len(src) && bi < len(p.Blocks); {
230		b := p.Blocks[bi]
231		if b.StartLine == line && b.StartCol == col {
232			boundaries = append(boundaries, boundary(si, true, b.Count))
233		}
234		if b.EndLine == line && b.EndCol == col || line > b.EndLine {
235			boundaries = append(boundaries, boundary(si, false, 0))
236			bi++
237			continue // Don't advance through src; maybe the next block starts here.
238		}
239		if src[si] == '\n' {
240			line++
241			col = 0
242		}
243		col++
244		si++
245	}
246	sort.Sort(boundariesByPos(boundaries))
247	return
248}
249
250type boundariesByPos []Boundary
251
252func (b boundariesByPos) Len() int      { return len(b) }
253func (b boundariesByPos) Swap(i, j int) { b[i], b[j] = b[j], b[i] }
254func (b boundariesByPos) Less(i, j int) bool {
255	if b[i].Offset == b[j].Offset {
256		// Boundaries at the same offset should be ordered according to
257		// their original position.
258		return b[i].Index < b[j].Index
259	}
260	return b[i].Offset < b[j].Offset
261}
262