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	"log"
19	"sort"
20	"sync"
21)
22
23// Optimize optimizes the Tree by de-duplicating common spans into a tree of
24// SpanGroups.
25func (t *Tree) Optimize() {
26	log.Printf("Optimizing coverage tree...")
27
28	// Start by gathering all of the unique spansets
29	wg := sync.WaitGroup{}
30	wg.Add(len(t.files))
31	for _, file := range t.files {
32		file := file
33		go func() {
34			defer wg.Done()
35			o := optimizer{}
36			for idx, tc := range file.tcm {
37				o.invertForCommon(tc, &t.testRoot.children[idx])
38			}
39			o.createGroups(file)
40		}()
41	}
42	wg.Wait()
43}
44
45type optimizer struct{}
46
47// createGroups looks for common SpanSets, and creates indexable span groups
48// which are then used instead.
49func (o *optimizer) createGroups(f *treeFile) {
50	const minSpansInGroup = 2
51
52	type spansetKey string
53	spansetMap := map[spansetKey]SpanSet{}
54
55	f.tcm.traverse(func(tc *TestCoverage) {
56		if len(tc.Spans) >= minSpansInGroup {
57			key := spansetKey(tc.Spans.String())
58			if _, ok := spansetMap[key]; !ok {
59				spansetMap[key] = tc.Spans
60			}
61		}
62	})
63
64	if len(spansetMap) == 0 {
65		return
66	}
67
68	type spansetInfo struct {
69		key spansetKey
70		set SpanSet // fully expanded set
71		grp SpanGroup
72		id  SpanGroupID
73	}
74	spansets := make([]*spansetInfo, 0, len(spansetMap))
75	for key, set := range spansetMap {
76		spansets = append(spansets, &spansetInfo{
77			key: key,
78			set: set,
79			grp: SpanGroup{Spans: set},
80		})
81	}
82
83	// Sort by number of spans in each sets starting with the largest.
84	sort.Slice(spansets, func(i, j int) bool {
85		a, b := spansets[i].set, spansets[j].set
86		switch {
87		case len(a) > len(b):
88			return true
89		case len(a) < len(b):
90			return false
91		}
92		return a.List().Compare(b.List()) == -1 // Just to keep output stable
93	})
94
95	// Assign IDs now that we have stable order.
96	for i := range spansets {
97		spansets[i].id = SpanGroupID(i)
98	}
99
100	// Loop over the spanGroups starting from the largest, and try to fold them
101	// into the larger sets.
102	// This is O(n^2) complexity.
103nextSpan:
104	for i, a := range spansets[:len(spansets)-1] {
105		for _, b := range spansets[i+1:] {
106			if len(a.set) > len(b.set) && a.set.containsAll(b.set) {
107				extend := b.id // Do not take address of iterator!
108				a.grp.Spans = a.set.removeAll(b.set)
109				a.grp.Extend = &extend
110				continue nextSpan
111			}
112		}
113	}
114
115	// Rebuild a map of spansetKey to SpanGroup
116	spangroupMap := make(map[spansetKey]*spansetInfo, len(spansets))
117	for _, s := range spansets {
118		spangroupMap[s.key] = s
119	}
120
121	// Store the groups in the tree
122	f.spangroups = make(map[SpanGroupID]SpanGroup, len(spansets))
123	for _, s := range spansets {
124		f.spangroups[s.id] = s.grp
125	}
126
127	// Update all the uses.
128	f.tcm.traverse(func(tc *TestCoverage) {
129		key := spansetKey(tc.Spans.String())
130		if g, ok := spangroupMap[key]; ok {
131			tc.Spans = nil
132			tc.Group = &g.id
133		}
134	})
135}
136
137// invertCommon looks for tree nodes with the majority of the child nodes with
138// the same spans. This span is promoted up to the parent, and the children
139// have the span inverted.
140func (o *optimizer) invertForCommon(tc *TestCoverage, t *Test) {
141	wg := sync.WaitGroup{}
142	wg.Add(len(tc.Children))
143	for id, child := range tc.Children {
144		id, child := id, child
145		go func() {
146			defer wg.Done()
147			o.invertForCommon(child, &t.children[id])
148		}()
149	}
150	wg.Wait()
151
152	counts := map[SpanID]int{}
153	for _, child := range tc.Children {
154		for span := range child.Spans {
155			counts[span] = counts[span] + 1
156		}
157	}
158
159	for span, count := range counts {
160		if count > len(t.children)/2 {
161			tc.Spans = tc.Spans.invert(span)
162			for _, idx := range t.indices {
163				child := tc.Children.index(idx)
164				child.Spans = child.Spans.invert(span)
165				if child.deletable() {
166					delete(tc.Children, idx)
167				}
168			}
169		}
170	}
171}
172