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 "fmt" 19 "sort" 20 "strings" 21) 22 23type treeFile struct { 24 tcm TestCoverageMap 25 spangroups map[SpanGroupID]SpanGroup 26 allSpans SpanList 27} 28 29func newTreeFile() *treeFile { 30 return &treeFile{ 31 tcm: TestCoverageMap{}, 32 spangroups: map[SpanGroupID]SpanGroup{}, 33 } 34} 35 36// Tree represents source code coverage across a tree of different processes. 37// Each tree node is addressed by a Path. 38type Tree struct { 39 initialized bool 40 strings Strings 41 spans map[Span]SpanID 42 testRoot Test 43 files map[string]*treeFile 44} 45 46func (t *Tree) init() { 47 if !t.initialized { 48 t.strings.m = map[string]StringID{} 49 t.spans = map[Span]SpanID{} 50 t.testRoot = newTest() 51 t.files = map[string]*treeFile{} 52 t.initialized = true 53 } 54} 55 56// Spans returns all the spans used by the tree 57func (t *Tree) Spans() SpanList { 58 out := make(SpanList, len(t.spans)) 59 for span, id := range t.spans { 60 out[id] = span 61 } 62 return out 63} 64 65// FileSpanGroups returns all the span groups for the given file 66func (t *Tree) FileSpanGroups(path string) map[SpanGroupID]SpanGroup { 67 return t.files[path].spangroups 68} 69 70// FileCoverage returns the TestCoverageMap for the given file 71func (t *Tree) FileCoverage(path string) TestCoverageMap { 72 return t.files[path].tcm 73} 74 75// Tests returns the root test 76func (t *Tree) Tests() *Test { return &t.testRoot } 77 78// Strings returns the string table 79func (t *Tree) Strings() Strings { return t.strings } 80 81func (t *Tree) index(path Path) []indexedTest { 82 out := make([]indexedTest, len(path)) 83 test := &t.testRoot 84 for i, p := range path { 85 name := t.strings.index(p) 86 test, out[i] = test.index(name) 87 } 88 return out 89} 90 91func (t *Tree) addSpans(spans SpanList) SpanSet { 92 out := make(SpanSet, len(spans)) 93 for _, s := range spans { 94 id, ok := t.spans[s] 95 if !ok { 96 id = SpanID(len(t.spans)) 97 t.spans[s] = id 98 } 99 out[id] = struct{}{} 100 } 101 return out 102} 103 104// Add adds the coverage information cov to the tree node addressed by path. 105func (t *Tree) Add(path Path, cov *Coverage) { 106 t.init() 107 108 tests := t.index(path) 109 110nextFile: 111 // For each file with coverage... 112 for _, file := range cov.Files { 113 // Lookup or create the file's test coverage map 114 tf, ok := t.files[file.Path] 115 if !ok { 116 tf = newTreeFile() 117 t.files[file.Path] = tf 118 } 119 120 for _, span := range file.Covered { 121 tf.allSpans.Add(span) 122 } 123 for _, span := range file.Uncovered { 124 tf.allSpans.Add(span) 125 } 126 127 // Add all the spans to the map, get the span ids 128 spans := t.addSpans(file.Covered) 129 130 // Starting from the test root, walk down the test tree. 131 tcm, test := tf.tcm, t.testRoot 132 parent := (*TestCoverage)(nil) 133 for _, indexedTest := range tests { 134 if indexedTest.created { 135 if parent != nil && len(test.children) == 1 { 136 parent.Spans = parent.Spans.addAll(spans) 137 delete(parent.Children, indexedTest.index) 138 } else { 139 tc := tcm.index(indexedTest.index) 140 tc.Spans = spans 141 } 142 continue nextFile 143 } 144 145 test = test.children[indexedTest.index] 146 tc := tcm.index(indexedTest.index) 147 148 // If the tree node contains spans that are not in this new test, 149 // we need to push those spans down to all the other children. 150 if lower := tc.Spans.removeAll(spans); len(lower) > 0 { 151 // push into each child node 152 for i := range test.children { 153 child := tc.Children.index(TestIndex(i)) 154 child.Spans = child.Spans.addAll(lower) 155 } 156 // remove from node 157 tc.Spans = tc.Spans.removeAll(lower) 158 } 159 160 // The spans that are in the new test, but are not part of the tree 161 // node carry propagating down. 162 spans = spans.removeAll(tc.Spans) 163 if len(spans) == 0 { 164 continue nextFile 165 } 166 167 tcm = tc.Children 168 parent = tc 169 } 170 } 171} 172 173// allSpans returns all the spans in use by the TestCoverageMap and its children. 174func (t *Tree) allSpans(tf *treeFile, tcm TestCoverageMap) SpanSet { 175 spans := SpanSet{} 176 for _, tc := range tcm { 177 for id := tc.Group; id != nil; id = tf.spangroups[*id].Extend { 178 group := tf.spangroups[*id] 179 spans = spans.addAll(group.Spans) 180 } 181 spans = spans.addAll(tc.Spans) 182 183 spans = spans.addAll(spans.invertAll(t.allSpans(tf, tc.Children))) 184 } 185 return spans 186} 187 188// StringID is an identifier of a string 189type StringID int 190 191// Strings holds a map of string to identifier 192type Strings struct { 193 m map[string]StringID 194 s []string 195} 196 197func (s *Strings) index(str string) StringID { 198 i, ok := s.m[str] 199 if !ok { 200 i = StringID(len(s.s)) 201 s.s = append(s.s, str) 202 s.m[str] = i 203 } 204 return i 205} 206 207// TestIndex is an child test index 208type TestIndex int 209 210// Test is an collection of named sub-tests 211type Test struct { 212 indices map[StringID]TestIndex 213 children []Test 214} 215 216func newTest() Test { 217 return Test{ 218 indices: map[StringID]TestIndex{}, 219 } 220} 221 222type indexedTest struct { 223 index TestIndex 224 created bool 225} 226 227func (t *Test) index(name StringID) (*Test, indexedTest) { 228 idx, ok := t.indices[name] 229 if !ok { 230 idx = TestIndex(len(t.children)) 231 t.children = append(t.children, newTest()) 232 t.indices[name] = idx 233 } 234 return &t.children[idx], indexedTest{idx, !ok} 235} 236 237type namedIndex struct { 238 name string 239 idx TestIndex 240} 241 242func (t Test) byName(s Strings) []namedIndex { 243 out := make([]namedIndex, len(t.children)) 244 for id, idx := range t.indices { 245 out[idx] = namedIndex{s.s[id], idx} 246 } 247 sort.Slice(out, func(i, j int) bool { return out[i].name < out[j].name }) 248 return out 249} 250 251func (t Test) String(s Strings) string { 252 sb := strings.Builder{} 253 for i, n := range t.byName(s) { 254 child := t.children[n.idx] 255 if i > 0 { 256 sb.WriteString(" ") 257 } 258 sb.WriteString(n.name) 259 if len(child.children) > 0 { 260 sb.WriteString(fmt.Sprintf(":%v", child.String(s))) 261 } 262 } 263 return "{" + sb.String() + "}" 264} 265 266// TestCoverage holds the coverage information for a deqp test group / leaf. 267// For example: 268// The deqp test group may hold spans that are common for all children, and may 269// also optionally hold child nodes that describe coverage that differs per 270// child test. 271type TestCoverage struct { 272 Spans SpanSet 273 Group *SpanGroupID 274 Children TestCoverageMap 275} 276 277func (tc TestCoverage) String(t *Test, s Strings) string { 278 sb := strings.Builder{} 279 sb.WriteString("{") 280 if len(tc.Spans) > 0 { 281 sb.WriteString(tc.Spans.String()) 282 } 283 if tc.Group != nil { 284 sb.WriteString(" <") 285 sb.WriteString(fmt.Sprintf("%v", *tc.Group)) 286 sb.WriteString(">") 287 } 288 if len(tc.Children) > 0 { 289 sb.WriteString(" ") 290 sb.WriteString(tc.Children.String(t, s)) 291 } 292 sb.WriteString("}") 293 return sb.String() 294} 295 296// deletable returns true if the TestCoverage provides no data. 297func (tc TestCoverage) deletable() bool { 298 return len(tc.Spans) == 0 && tc.Group == nil && len(tc.Children) == 0 299} 300 301// TestCoverageMap is a map of TestIndex to *TestCoverage. 302type TestCoverageMap map[TestIndex]*TestCoverage 303 304// traverse performs a depth first traversal of the TestCoverage tree. 305func (tcm TestCoverageMap) traverse(cb func(*TestCoverage)) { 306 for _, tc := range tcm { 307 cb(tc) 308 tc.Children.traverse(cb) 309 } 310} 311 312func (tcm TestCoverageMap) String(t *Test, s Strings) string { 313 sb := strings.Builder{} 314 for _, n := range t.byName(s) { 315 if child, ok := tcm[n.idx]; ok { 316 sb.WriteString(fmt.Sprintf("\n%v: %v", n.name, child.String(&t.children[n.idx], s))) 317 } 318 } 319 if sb.Len() > 0 { 320 sb.WriteString("\n") 321 } 322 return indent(sb.String()) 323} 324 325func newTestCoverage() *TestCoverage { 326 return &TestCoverage{ 327 Children: TestCoverageMap{}, 328 Spans: SpanSet{}, 329 } 330} 331 332func (tcm TestCoverageMap) index(idx TestIndex) *TestCoverage { 333 tc, ok := tcm[idx] 334 if !ok { 335 tc = newTestCoverage() 336 tcm[idx] = tc 337 } 338 return tc 339} 340 341// SpanID is an identifier of a span in a Tree. 342type SpanID int 343 344// SpanSet is a set of SpanIDs. 345type SpanSet map[SpanID]struct{} 346 347// SpanIDList is a list of SpanIDs 348type SpanIDList []SpanID 349 350// Compare returns -1 if l comes before o, 1 if l comes after o, otherwise 0. 351func (l SpanIDList) Compare(o SpanIDList) int { 352 switch { 353 case len(l) < len(o): 354 return -1 355 case len(l) > len(o): 356 return 1 357 } 358 for i, a := range l { 359 b := o[i] 360 switch { 361 case a < b: 362 return -1 363 case a > b: 364 return 1 365 } 366 } 367 return 0 368} 369 370// List returns the full list of sorted span ids. 371func (s SpanSet) List() SpanIDList { 372 out := make(SpanIDList, 0, len(s)) 373 for span := range s { 374 out = append(out, span) 375 } 376 sort.Slice(out, func(i, j int) bool { return out[i] < out[j] }) 377 return out 378} 379 380func (s SpanSet) String() string { 381 sb := strings.Builder{} 382 sb.WriteString(`[`) 383 l := s.List() 384 for i, span := range l { 385 if i > 0 { 386 sb.WriteString(`, `) 387 } 388 sb.WriteString(fmt.Sprintf("%v", span)) 389 } 390 sb.WriteString(`]`) 391 return sb.String() 392} 393 394func (s SpanSet) contains(rhs SpanID) bool { 395 _, found := s[rhs] 396 return found 397} 398 399func (s SpanSet) containsAll(rhs SpanSet) bool { 400 for span := range rhs { 401 if !s.contains(span) { 402 return false 403 } 404 } 405 return true 406} 407 408func (s SpanSet) remove(rhs SpanID) SpanSet { 409 out := make(SpanSet, len(s)) 410 for span := range s { 411 if span != rhs { 412 out[span] = struct{}{} 413 } 414 } 415 return out 416} 417 418func (s SpanSet) removeAll(rhs SpanSet) SpanSet { 419 out := make(SpanSet, len(s)) 420 for span := range s { 421 if _, found := rhs[span]; !found { 422 out[span] = struct{}{} 423 } 424 } 425 return out 426} 427 428func (s SpanSet) add(rhs SpanID) SpanSet { 429 out := make(SpanSet, len(s)+1) 430 for span := range s { 431 out[span] = struct{}{} 432 } 433 out[rhs] = struct{}{} 434 return out 435} 436 437func (s SpanSet) addAll(rhs SpanSet) SpanSet { 438 out := make(SpanSet, len(s)+len(rhs)) 439 for span := range s { 440 out[span] = struct{}{} 441 } 442 for span := range rhs { 443 out[span] = struct{}{} 444 } 445 return out 446} 447 448func (s SpanSet) invert(rhs SpanID) SpanSet { 449 if s.contains(rhs) { 450 return s.remove(rhs) 451 } 452 return s.add(rhs) 453} 454 455func (s SpanSet) invertAll(rhs SpanSet) SpanSet { 456 out := make(SpanSet, len(s)+len(rhs)) 457 for span := range s { 458 if !rhs.contains(span) { 459 out[span] = struct{}{} 460 } 461 } 462 for span := range rhs { 463 if !s.contains(span) { 464 out[span] = struct{}{} 465 } 466 } 467 return out 468} 469 470// SpanGroupID is an identifier of a SpanGroup. 471type SpanGroupID int 472 473// SpanGroup holds a number of spans, potentially extending from another 474// SpanGroup. 475type SpanGroup struct { 476 Spans SpanSet 477 Extend *SpanGroupID 478} 479 480func newSpanGroup() SpanGroup { 481 return SpanGroup{Spans: SpanSet{}} 482} 483 484func indent(s string) string { 485 return strings.TrimSuffix(strings.ReplaceAll(s, "\n", "\n "), " ") 486} 487