• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1// Copyright 2020 The SwiftShader Authors. All Rights Reserved.
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.
14
15package cov
16
17import (
18	"bufio"
19	"compress/zlib"
20	"fmt"
21	"io"
22	"runtime/debug"
23	"sort"
24	"strconv"
25	"strings"
26)
27
28// ReadJSON parses the JSON Tree from r.
29func ReadJSON(r io.Reader) (*Tree, string, error) {
30	p := parser{r: bufio.NewReader(r)}
31	return p.parse()
32}
33
34// Encode zlib encodes the JSON coverage tree to w.
35func (t *Tree) Encode(revision string, w io.Writer) error {
36	t.Optimize()
37
38	zw := zlib.NewWriter(w)
39
40	_, err := zw.Write([]byte(t.JSON(revision)))
41	if err != nil {
42		return err
43	}
44
45	return zw.Close()
46}
47
48// JSON returns the full test tree serialized to JSON.
49func (t *Tree) JSON(revision string) string {
50	sb := &strings.Builder{}
51	sb.WriteString(`{`)
52
53	spansByID := map[SpanID]Span{}
54	for span, id := range t.spans {
55		spansByID[id] = span
56	}
57
58	// write the revision
59	sb.WriteString(`"r":"` + revision + `"`)
60
61	// write the strings
62	sb.WriteString(`,"n":[`)
63	for i, s := range t.strings.s {
64		if i > 0 {
65			sb.WriteString(`,`)
66		}
67		sb.WriteString(`"`)
68		sb.WriteString(s)
69		sb.WriteString(`"`)
70	}
71	sb.WriteString(`]`)
72
73	// write the tests
74	sb.WriteString(`,"t":`)
75	t.writeTestJSON(&t.testRoot, sb)
76
77	// write the spans
78	sb.WriteString(`,"s":`)
79	t.writeSpansJSON(sb)
80
81	// write the files
82	sb.WriteString(`,"f":`)
83	t.writeFilesJSON(spansByID, sb)
84
85	sb.WriteString(`}`)
86	return sb.String()
87}
88
89func (t *Tree) writeTestJSON(test *Test, sb *strings.Builder) {
90	names := map[int]StringID{}
91	for name, idx := range test.indices {
92		names[int(idx)] = name
93	}
94
95	sb.WriteString(`[`)
96	for i, child := range test.children {
97		if i > 0 {
98			sb.WriteString(`,`)
99		}
100		sb.WriteString(`[`)
101		sb.WriteString(fmt.Sprintf("%v,", names[i]))
102		t.writeTestJSON(&child, sb)
103		sb.WriteString(`]`)
104	}
105
106	sb.WriteString(`]`)
107}
108
109func (t *Tree) writeSpansJSON(sb *strings.Builder) {
110	type spanAndID struct {
111		span Span
112		id   SpanID
113	}
114	spans := make([]spanAndID, 0, len(t.spans))
115	for span, id := range t.spans {
116		spans = append(spans, spanAndID{span, id})
117	}
118	sort.Slice(spans, func(i, j int) bool { return spans[i].id < spans[j].id })
119
120	sb.WriteString(`[`)
121	for i, s := range spans {
122		if i > 0 {
123			sb.WriteString(`,`)
124		}
125		sb.WriteString(fmt.Sprintf("[%v,%v,%v,%v]",
126			s.span.Start.Line, s.span.Start.Column,
127			s.span.End.Line, s.span.End.Column))
128	}
129
130	sb.WriteString(`]`)
131}
132
133func (t *Tree) writeSpanJSON(span Span, sb *strings.Builder) {
134	sb.WriteString(fmt.Sprintf("[%v,%v,%v,%v]",
135		span.Start.Line, span.Start.Column,
136		span.End.Line, span.End.Column))
137}
138
139func (t *Tree) writeFilesJSON(spansByID map[SpanID]Span, sb *strings.Builder) {
140	paths := make([]string, 0, len(t.files))
141	for path := range t.files {
142		paths = append(paths, path)
143	}
144	sort.Strings(paths)
145
146	sb.WriteString(`{`)
147	for i, path := range paths {
148		file := t.files[path]
149
150		uncovered := append(SpanList{}, file.allSpans...)
151		for id := range t.allSpans(file, file.tcm) {
152			uncovered.Remove(spansByID[id])
153		}
154
155		if i > 0 {
156			sb.WriteString(`,`)
157		}
158		sb.WriteString(`"`)
159		sb.WriteString(path)
160		sb.WriteString(`":`)
161		sb.WriteString(`{`)
162		if totalLines := file.allSpans.NumLines(); totalLines > 0 {
163			uncoveredLines := uncovered.NumLines()
164			percentage := 1.0 - (float64(uncoveredLines) / float64(totalLines))
165			sb.WriteString(`"p":`)
166			sb.WriteString(fmt.Sprintf("%v", percentage))
167			sb.WriteString(`,`)
168		}
169		sb.WriteString(`"g":`)
170		t.writeSpanGroupsJSON(file.spangroups, sb)
171		sb.WriteString(`,"u":`)
172		t.writeUncoveredJSON(file, uncovered, sb)
173		sb.WriteString(`,"c":`)
174		t.writeCoverageMapJSON(file.tcm, sb)
175		sb.WriteString(`}`)
176	}
177
178	sb.WriteString(`}`)
179}
180
181func (t *Tree) writeSpanGroupsJSON(spangroups map[SpanGroupID]SpanGroup, sb *strings.Builder) {
182	type groupAndID struct {
183		group SpanGroup
184		id    SpanGroupID
185	}
186	groups := make([]groupAndID, 0, len(spangroups))
187	for id, group := range spangroups {
188		groups = append(groups, groupAndID{group, id})
189	}
190	sort.Slice(groups, func(i, j int) bool { return groups[i].id < groups[j].id })
191
192	sb.WriteString(`[`)
193	for i, g := range groups {
194		if i > 0 {
195			sb.WriteString(`,`)
196		}
197		t.writeSpanGroupJSON(g.group, sb)
198	}
199	sb.WriteString(`]`)
200}
201
202func (t *Tree) writeSpanGroupJSON(group SpanGroup, sb *strings.Builder) {
203	sb.WriteString(`{`)
204	sb.WriteString(`"s":[`)
205	for i, spanID := range group.Spans.List() {
206		if i > 0 {
207			sb.WriteString(`,`)
208		}
209		sb.WriteString(fmt.Sprintf("%v", spanID))
210	}
211	sb.WriteString(`]`)
212	if group.Extend != nil {
213		sb.WriteString(`,"e":`)
214		sb.WriteString(fmt.Sprintf("%v", *group.Extend))
215	}
216	sb.WriteString(`}`)
217}
218
219func (t *Tree) writeUncoveredJSON(tf *treeFile, uncovered SpanList, sb *strings.Builder) {
220	sb.WriteString(`[`)
221	for i, span := range uncovered {
222		if i > 0 {
223			sb.WriteString(`,`)
224		}
225		t.writeSpanJSON(span, sb)
226	}
227	sb.WriteString(`]`)
228}
229
230func (t *Tree) writeCoverageMapJSON(c TestCoverageMap, sb *strings.Builder) {
231	ids := make([]TestIndex, 0, len(c))
232	for id := range c {
233		ids = append(ids, id)
234	}
235	sort.Slice(ids, func(i, j int) bool { return ids[i] < ids[j] })
236
237	sb.WriteString(`[`)
238	for i, id := range ids {
239		if i > 0 {
240			sb.WriteString(`,`)
241		}
242
243		sb.WriteString(`[`)
244		sb.WriteString(fmt.Sprintf("%v", id))
245		sb.WriteString(`,`)
246		t.writeCoverageJSON(c[id], sb)
247		sb.WriteString(`]`)
248	}
249	sb.WriteString(`]`)
250}
251
252func (t *Tree) writeCoverageJSON(c *TestCoverage, sb *strings.Builder) {
253	sb.WriteString(`{`)
254	comma := false
255	if len(c.Spans) > 0 {
256		sb.WriteString(`"s":[`)
257		for i, spanID := range c.Spans.List() {
258			if i > 0 {
259				sb.WriteString(`,`)
260			}
261			sb.WriteString(fmt.Sprintf("%v", spanID))
262		}
263		sb.WriteString(`]`)
264		comma = true
265	}
266	if c.Group != nil {
267		sb.WriteString(`"g":`)
268		sb.WriteString(fmt.Sprintf("%v", *c.Group))
269		comma = true
270	}
271	if len(c.Children) > 0 {
272		if comma {
273			sb.WriteString(`,`)
274		}
275		sb.WriteString(`"c":`)
276		t.writeCoverageMapJSON(c.Children, sb)
277	}
278	sb.WriteString(`}`)
279}
280
281type parser struct {
282	r   *bufio.Reader
283	err error
284
285	revision string
286	tree     Tree
287}
288
289func (p *parser) parse() (*Tree, string, error) {
290	p.tree.init()
291	p.dict(func(key string) {
292		switch key {
293		case "r":
294			p.revision = p.str()
295		case "n":
296			p.parseStrings()
297		case "t":
298			p.parseTests(&p.tree.testRoot)
299		case "s":
300			p.parseSpans()
301		case "g":
302			p.parseSpanGroups()
303		case "f":
304			p.parseFiles()
305		default:
306			p.fail("Unknown root key '%v'", key)
307		}
308	})
309	if p.err != nil {
310		return nil, "", p.err
311	}
312
313	p.populateAllSpans(&p.tree)
314
315	return &p.tree, p.revision, nil
316}
317
318// populateAllSpans() adds all the coverage spans to each treeFile.allSpans.
319func (p *parser) populateAllSpans(tree *Tree) {
320	spansByID := map[SpanID]Span{}
321	for span, id := range tree.spans {
322		spansByID[id] = span
323	}
324	for _, file := range tree.files {
325		for spanID := range tree.allSpans(file, file.tcm) {
326			span := spansByID[spanID]
327			file.allSpans.Add(span)
328		}
329	}
330}
331
332func (p *parser) parseStrings() {
333	p.array(func(idx int) {
334		id := StringID(idx)
335		s := p.str()
336		p.tree.strings.m[s] = id
337		p.tree.strings.s = append(p.tree.strings.s, s)
338	})
339}
340
341func (p *parser) parseTests(t *Test) {
342	p.array(func(idx int) {
343		p.expect("[")
344		name := StringID(p.integer())
345		child, _ := t.index(name)
346		p.expect(",")
347		p.parseTests(child)
348		p.expect("]")
349	})
350}
351
352func (p *parser) parseSpans() {
353	p.array(func(idx int) {
354		p.tree.spans[p.parseSpan()] = SpanID(idx)
355	})
356}
357
358func (p *parser) parseSpan() Span {
359	p.expect("[")
360	s := Span{}
361	s.Start.Line = p.integer()
362	p.expect(",")
363	s.Start.Column = p.integer()
364	p.expect(",")
365	s.End.Line = p.integer()
366	p.expect(",")
367	s.End.Column = p.integer()
368	p.expect("]")
369	return s
370}
371
372func (p *parser) parseFiles() {
373	p.dict(func(path string) {
374		p.tree.files[path] = p.parseFile()
375	})
376}
377
378func (p *parser) parseFile() *treeFile {
379	file := newTreeFile()
380	if p.peek() == '{' {
381		p.dict(func(key string) {
382			switch key {
383			case "p":
384				p.double()
385			case "g":
386				file.spangroups = p.parseSpanGroups()
387			case "c":
388				p.parseCoverageMap(file.tcm)
389			case "u":
390				p.parseUncovered(file)
391			default:
392				p.fail("Unknown file key: '%s'", key)
393			}
394		})
395	} else { // backwards compatibility
396		p.parseCoverageMap(file.tcm)
397	}
398	return file
399}
400
401func (p *parser) parseSpanGroups() map[SpanGroupID]SpanGroup {
402	spangroups := map[SpanGroupID]SpanGroup{}
403	p.array(func(groupIdx int) {
404		g := newSpanGroup()
405		p.dict(func(key string) {
406			switch key {
407			case "s":
408				p.array(func(spanIdx int) {
409					id := SpanID(p.integer())
410					g.Spans[id] = struct{}{}
411				})
412			case "e":
413				extend := SpanGroupID(p.integer())
414				g.Extend = &extend
415			}
416		})
417		spangroups[SpanGroupID(groupIdx)] = g
418	})
419	return spangroups
420}
421
422func (p *parser) parseCoverageMap(tcm TestCoverageMap) {
423	p.array(func(int) {
424		p.expect("[")
425		idx := TestIndex(p.integer())
426		p.expect(",")
427		p.parseCoverage(tcm.index(idx))
428		p.expect("]")
429	})
430}
431
432func (p *parser) parseUncovered(tf *treeFile) {
433	p.array(func(int) {
434		tf.allSpans.Add(p.parseSpan())
435	})
436}
437
438func (p *parser) parseCoverage(tc *TestCoverage) {
439	p.dict(func(key string) {
440		switch key {
441		case "s":
442			p.array(func(int) {
443				id := SpanID(p.integer())
444				tc.Spans[id] = struct{}{}
445			})
446		case "g":
447			groupID := SpanGroupID(p.integer())
448			tc.Group = &groupID
449		case "c":
450			p.parseCoverageMap(tc.Children)
451		default:
452			p.fail("Unknown test key: '%s'", key)
453		}
454	})
455}
456
457func (p *parser) array(f func(idx int)) {
458	p.expect("[")
459	if p.match("]") {
460		return
461	}
462	idx := 0
463	for p.err == nil {
464		f(idx)
465		if !p.match(",") {
466			p.expect("]")
467			return
468		}
469		idx++
470	}
471	p.expect("]")
472}
473
474func (p *parser) dict(f func(key string)) {
475	p.expect("{")
476	if p.match("}") {
477		return
478	}
479	for p.err == nil {
480		key := p.str()
481		p.expect(`:`)
482		f(key)
483		if !p.match(",") {
484			p.expect("}")
485			return
486		}
487	}
488	p.expect("}")
489}
490
491func (p *parser) next() byte {
492	d := make([]byte, 1)
493	n, err := p.r.Read(d)
494	if err != nil || n != 1 {
495		p.err = err
496		return 0
497	}
498	return d[0]
499}
500
501func (p *parser) peek() byte {
502	d, err := p.r.Peek(1)
503	if err != nil {
504		p.err = err
505		return 0
506	}
507	return d[0]
508}
509
510func (p *parser) expect(s string) {
511	if p.err != nil {
512		return
513	}
514	d := make([]byte, len(s))
515	n, err := p.r.Read(d)
516	if err != nil {
517		p.err = err
518		return
519	}
520	got := string(d[:n])
521	if got != s {
522		p.fail("Expected '%v', got '%v'", s, got)
523		return
524	}
525}
526
527func (p *parser) match(s string) bool {
528	got, err := p.r.Peek(len(s))
529	if err != nil {
530		return false
531	}
532	if string(got) != s {
533		return false
534	}
535	p.r.Discard(len(s))
536	return true
537}
538
539func (p *parser) str() string {
540	p.expect(`"`)
541	sb := strings.Builder{}
542	for p.err == nil {
543		c := p.next()
544		if c == '"' {
545			return sb.String()
546		}
547		sb.WriteByte(c)
548	}
549	return ""
550}
551
552func (p *parser) integer() int {
553	sb := strings.Builder{}
554	for {
555		if c := p.peek(); c < '0' || c > '9' {
556			break
557		}
558		sb.WriteByte(p.next())
559	}
560	if sb.Len() == 0 {
561		p.fail("Expected integer, got '%c'", p.peek())
562		return 0
563	}
564	i, err := strconv.Atoi(sb.String())
565	if err != nil {
566		p.fail("Failed to parse integer: %v", err)
567		return 0
568	}
569	return i
570}
571
572func (p *parser) double() float64 {
573	sb := strings.Builder{}
574	for {
575		if c := p.peek(); c != '.' && (c < '0' || c > '9') {
576			break
577		}
578		sb.WriteByte(p.next())
579	}
580	if sb.Len() == 0 {
581		p.fail("Expected double, got '%c'", p.peek())
582		return 0
583	}
584	f, err := strconv.ParseFloat(sb.String(), 64)
585	if err != nil {
586		p.fail("Failed to parse double: %v", err)
587		return 0
588	}
589	return f
590}
591
592func (p *parser) fail(msg string, args ...interface{}) {
593	if p.err == nil {
594		msg = fmt.Sprintf(msg, args...)
595		stack := string(debug.Stack())
596		p.err = fmt.Errorf("%v\nCallstack:\n%v", msg, stack)
597	}
598}
599