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_test 16 17import ( 18 "reflect" 19 "strings" 20 "testing" 21 22 "swiftshader.googlesource.com/SwiftShader/tests/regres/cov" 23) 24 25var ( 26 fileA = "coverage/file/a" 27 fileB = "coverage/file/b" 28 fileC = "coverage/file/c" 29 fileD = "coverage/file/c" 30 31 span0 = cov.Span{cov.Location{3, 2}, cov.Location{3, 9}} 32 span1 = cov.Span{cov.Location{4, 1}, cov.Location{5, 1}} 33 span2 = cov.Span{cov.Location{5, 5}, cov.Location{5, 7}} 34 span3 = cov.Span{cov.Location{7, 2}, cov.Location{7, 7}} 35) 36 37// a 38// ╭───────┴───────╮ 39// b c 40// ╭───┴───╮ ╭───┴───╮ 41// d e f g 42// ╭─┴─╮ ╭─┴─╮ ╭─┴─╮ ╭─┴─╮ 43// h i j k l m n o 44// ╭┴╮ ╭┴╮ ╭┴╮ ╭┴╮ ╭┴╮ ╭╯ 45// p q r s t u v w x y z 46// 47 48func TestTree(t *testing.T) { 49 tree := &cov.Tree{} 50 51 t.Log("Add 'b' with the coverage [0,1]") 52 tree.Add(cov.Path{"a", "b"}, coverage(fileA, span0, span1)) 53 54 // [0,1] 55 // (a) 56 // ╭─────╯ 57 // b 58 59 checkSpans(t, tree.Spans(), span0, span1) 60 checkTests(t, tree, `{a:{b}}`) 61 checkCoverage(t, tree, fileA, `a:{[0,1]}`) 62 63 t.Log("Add 'i' with the coverage [0,1]") 64 tree.Add(cov.Path{"a", "b", "d", "i"}, coverage(fileA, span0, span1)) 65 66 // [0,1] 67 // (a) 68 // ╭─────╯ 69 // b 70 // ╭──╯ 71 // d 72 // ╰─╮ 73 // i 74 checkSpans(t, tree.Spans(), span0, span1) 75 checkTests(t, tree, `{a:{b:{d:{i}}}}`) 76 checkCoverage(t, tree, fileA, `a:{[0,1]}`) 77 78 t.Log("Add 'e' with the coverage [0,1,2]") 79 tree.Add(cov.Path{"a", "b", "e"}, coverage(fileA, span0, span1, span2)) 80 81 // [0,1] 82 // (a) 83 // ┏━━━━━┛ 84 // (b) 85 // ╭──┺━━┓ 86 // d (e)[2] 87 // ╰─╮ 88 // i 89 checkSpans(t, tree.Spans(), span0, span1, span2) 90 checkTests(t, tree, `{a:{b:{d:{i} e}}}`) 91 checkCoverage(t, tree, fileA, `a:{[0,1] b:{e:{[2]}}}`) 92 93 t.Log("Add 'n' with the coverage [0,3]") 94 tree.Add(cov.Path{"a", "c", "g", "n"}, coverage(fileA, span0, span3)) 95 96 // [0] 97 // (a) 98 // ┏━━━━━┻━━━━━┓ 99 // [1](b) (c)[3] 100 // ╭──┺━━┓ ╰──╮ 101 // d (e)[2] g 102 // ╰─╮ ╭─╯ 103 // i n 104 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 105 checkTests(t, tree, `{a:{b:{d:{i}e}c:{g:{n}}}}`) 106 checkCoverage(t, tree, fileA, `a:{[0] b:{[1] e:{[2]}} c:{[3]}}`) 107 108 t.Log("Add 'o' with the coverage [0, 3]") 109 tree.Add(cov.Path{"a", "c", "g", "o"}, coverage(fileA, span0, span3)) 110 111 // [0] 112 // (a) 113 // ┏━━━━━━━┻━━━━━━━┓ 114 // [1](b) (c)[3] 115 // ╭──┺━━┓ ╰──╮ 116 // d (e)[2] g 117 // ╰─╮ ╭─┴─╮ 118 // i n o 119 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 120 checkTests(t, tree, `{a:{b:{d:{i}e}c:{g:{n o}}}}`) 121 checkCoverage(t, tree, fileA, `a:{[0] b:{[1] e:{[2]}} c:{[3]}}`) 122 123 t.Log("Add 'f' with the coverage [1]") 124 tree.Add(cov.Path{"a", "c", "f"}, coverage(fileA, span1)) 125 126 // (a) 127 // ┏━━━━━━━━┻━━━━━━━━┓ 128 // [0,1](b) (c) 129 // ╭──┺━━┓ ┏━━┻━━┓ 130 // d (e)[2] [1](f) (g)[0,3] 131 // ╰─╮ ╭─┴─╮ 132 // i n o 133 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 134 checkTests(t, tree, `{a:{b:{d:{i} e} c:{f g:{n o}}}}`) 135 checkCoverage(t, tree, fileA, `a:{b:{[0,1] e:{[2]}} c:{f:{[1]} g:{[0,3]}}}`) 136 137 t.Log("Add 'j' with the coverage [3]") 138 tree.Add(cov.Path{"a", "b", "e", "j"}, coverage(fileA, span3)) 139 140 // (a) 141 // ┏━━━━━━━━┻━━━━━━━━┓ 142 // (b) (c) 143 // ┏━━━┻━━━┓ ┏━━┻━━┓ 144 // [0,1](d) (e)[3] [1](f) (g)[0,3] 145 // ╰─╮ ╭─╯ ╭─┴─╮ 146 // i j n o 147 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 148 checkTests(t, tree, `{a:{b:{d:{i} e:{j}} c:{f g:{n o}}}}`) 149 checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1]} g:{[0,3]}}}`) 150 151 t.Log("Add 'k' with the coverage [3]") 152 tree.Add(cov.Path{"a", "b", "e", "k"}, coverage(fileA, span3)) 153 154 // (a) 155 // ┏━━━━━━━━┻━━━━━━━━┓ 156 // (b) (c) 157 // ┏━━━┻━━━┓ ┏━━┻━━┓ 158 // [0,1](d) (e)[3] [1](f) (g)[0,3] 159 // ╰─╮ ╭─┴─╮ ╭─┴─╮ 160 // i j k n o 161 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 162 checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f g:{n o}}}}`) 163 checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1]} g:{[0,3]}}}`) 164 165 t.Log("Add 'v' with the coverage [1,2]") 166 tree.Add(cov.Path{"a", "c", "f", "l", "v"}, coverage(fileA, span1, span2)) 167 168 // (a) 169 // ┏━━━━━━━━┻━━━━━━━━━━┓ 170 // (b) (c) 171 // ┏━━━┻━━━┓ ┏━━┻━━┓ 172 // [0,1](d) (e)[3] [1,2](f) (g)[0,3] 173 // ╰─╮ ╭─┴─╮ ╭─╯ ╭─┴─╮ 174 // i j k l n o 175 // ╭╯ 176 // v 177 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 178 checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f:{l:{v}} g:{n o}}}}`) 179 checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1,2]} g:{[0,3]}}}`) 180 181 t.Log("Add 'x' with the coverage [1,2]") 182 tree.Add(cov.Path{"a", "c", "f", "l", "x"}, coverage(fileA, span1, span2)) 183 184 // (a) 185 // ┏━━━━━━━━┻━━━━━━━━━━┓ 186 // (b) (c) 187 // ┏━━━┻━━━┓ ┏━━┻━━┓ 188 // [0,1](d) (e)[3] [1,2](f) (g)[0,3] 189 // ╰─╮ ╭─┴─╮ ╭─╯ ╭─┴─╮ 190 // i j k l n o 191 // ╭┴╮ 192 // v x 193 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 194 checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f:{l:{v x}} g:{n o}}}}`) 195 checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1,2]} g:{[0,3]}}}`) 196 197 t.Log("Add 'z' with the coverage [2]") 198 tree.Add(cov.Path{"a", "c", "g", "n", "z"}, coverage(fileA, span2)) 199 200 // (a) 201 // ┏━━━━━━━━┻━━━━━━━━━━━━┓ 202 // (b) (c) 203 // ┏━━━┻━━━┓ ┏━━━━┻━━━━┓ 204 // [0,1](d) (e)[3] [1,2](f) (g) 205 // ╰─╮ ╭─┴─╮ ╭─╯ ┏━┻━┓ 206 // i j k l [2](n) (o)[0,3] 207 // ╭┴╮ ╭╯ 208 // v x z 209 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 210 checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f:{l:{v x}} g:{n: {z} o}}}}`) 211 checkCoverage(t, tree, fileA, `a:{b:{d:{[0,1]} e:{[3]}} c:{f:{[1,2]} g:{n:{[2]} o:{[0,3]}}}}`) 212 213 tree.Optimize() 214 215 // (a) 216 // ┏━━━━━━━━┻━━━━━━━━━━━━┓ 217 // (b) (c) 218 // ┏━━━┻━━━┓ ┏━━━━┻━━━━┓ 219 // <0>(d) (e)[3] <2>(f) (g) 220 // ╰─╮ ╭─┴─╮ ╭─╯ ┏━┻━┓ 221 // i j k l [2](n) (o)<1> 222 // ╭┴╮ ╭╯ 223 // v x z 224 checkSpans(t, tree.Spans(), span0, span1, span2, span3) 225 checkGroups(t, tree.FileSpanGroups(fileA), map[cov.SpanGroupID]cov.SpanGroup{ 226 0: cov.SpanGroup{Spans: spans(0, 1)}, 227 1: cov.SpanGroup{Spans: spans(0, 3)}, 228 2: cov.SpanGroup{Spans: spans(1, 2)}, 229 }) 230 checkTests(t, tree, `{a:{b:{d:{i} e:{j k}} c:{f:{l:{v x}} g:{n: {z} o}}}}`) 231 checkCoverage(t, tree, fileA, `a:{b:{d:{<0>} e:{[3]}} c:{f:{<2>} g:{n:{[2]} o:{<1>}}}}`) 232} 233 234func TestTreeOptInvertForCommon(t *testing.T) { 235 tree := &cov.Tree{} 236 237 tree.Add(cov.Path{"a", "b"}, coverage(fileA, span0)) 238 tree.Add(cov.Path{"a", "c"}, coverage(fileA, span0)) 239 tree.Add(cov.Path{"a", "d"}, coverage(fileA, span0)) 240 tree.Add(cov.Path{"a", "e"}, coverage(fileA, span1)) 241 tree.Add(cov.Path{"a", "f"}, coverage(fileA, span1)) 242 tree.Add(cov.Path{"a", "g"}, coverage(fileA, span0)) 243 tree.Add(cov.Path{"a", "h"}, coverage(fileA, span0)) 244 tree.Add(cov.Path{"a", "i"}, coverage(fileA, span0)) 245 246 // (a) 247 // ┏━━━┳━━━┳━━━┳━┻━┳━━━┳━━━┳━━━┓ 248 // (b) (c) (d) (e) (f) (g) (h) (i) 249 // [0] [0] [0] [1] [1] [0] [0] [0] 250 checkSpans(t, tree.Spans(), span0, span1) 251 checkTests(t, tree, `{a:{b c d e f g h i}}`) 252 checkCoverage(t, tree, fileA, `a:{b:{[0]} c:{[0]} d:{[0]} e:{[1]} f:{[1]} g:{[0]} h:{[0]} i:{[0]}}`) 253 254 tree.Optimize() 255 256 // [0] 257 // (a) 258 // ╭───┬───┬───┲━┻━┱───┬───┬───╮ 259 // b c d ┏┛ ┗┓ g h i 260 // (e) (f) 261 // <0> <0> 262 checkSpans(t, tree.Spans(), span0, span1) 263 checkGroups(t, tree.FileSpanGroups(fileA), map[cov.SpanGroupID]cov.SpanGroup{ 264 0: cov.SpanGroup{Spans: spans(0, 1)}, 265 }) 266 checkTests(t, tree, `{a:{b c d e f g h i}}`) 267 checkCoverage(t, tree, fileA, `a:{[0] e:{<0>} f:{<0>}}`) 268} 269 270func TestTreeOptDontInvertForCommon(t *testing.T) { 271 tree := &cov.Tree{} 272 273 tree.Add(cov.Path{"a", "b"}, coverage(fileA, span0)) 274 tree.Add(cov.Path{"a", "c"}, coverage(fileA, span0)) 275 tree.Add(cov.Path{"a", "d"}, coverage(fileA, span0)) 276 tree.Add(cov.Path{"a", "e"}, coverage(fileA, span1)) 277 tree.Add(cov.Path{"a", "f"}, coverage(fileA, span1)) 278 tree.Add(cov.Path{"a", "g"}, coverage(fileA, span2)) 279 tree.Add(cov.Path{"a", "h"}, coverage(fileA, span2)) 280 tree.Add(cov.Path{"a", "i"}, coverage(fileA, span2)) 281 282 // (a) 283 // ┏━━━┳━━━┳━━━┳━┻━┳━━━┳━━━┳━━━┓ 284 // (b) (c) (d) (e) (f) (g) (h) (i) 285 // [0] [0] [0] [1] [1] [2] [2] [2] 286 checkSpans(t, tree.Spans(), span0, span1, span2) 287 checkTests(t, tree, `{a:{b c d e f g h i}}`) 288 checkCoverage(t, tree, fileA, `a:{b:{[0]} c:{[0]} d:{[0]} e:{[1]} f:{[1]} g:{[2]} h:{[2]} i:{[2]}}`) 289 290 tree.Optimize() 291 292 // (a) 293 // ┏━━━┳━━━┳━━━┳━┻━┳━━━┳━━━┳━━━┓ 294 // (b) (c) (d) (e) (f) (g) (h) (i) 295 // [0] [0] [0] [1] [1] [2] [2] [2] 296 checkSpans(t, tree.Spans(), span0, span1, span2) 297 checkTests(t, tree, `{a:{b c d e f g h i}}`) 298 checkCoverage(t, tree, fileA, `a:{b:{[0]} c:{[0]} d:{[0]} e:{[1]} f:{[1]} g:{[2]} h:{[2]} i:{[2]}}`) 299} 300 301func checkSpans(t *testing.T, got []cov.Span, expect ...cov.Span) { 302 if !reflect.DeepEqual(got, expect) { 303 t.Errorf("Spans not as expected.\nGot: %+v\nExpect: %+v", got, expect) 304 } 305} 306 307func checkGroups(t *testing.T, got, expect map[cov.SpanGroupID]cov.SpanGroup) { 308 if !reflect.DeepEqual(got, expect) { 309 t.Errorf("SpanGroupss not as expected.\nGot: %+v\nExpect: %+v", got, expect) 310 } 311} 312 313func checkTests(t *testing.T, tree *cov.Tree, expect string) { 314 g, e := tree.Tests().String(tree.Strings()), expect 315 if tg, te := trimWS(g), trimWS(e); tg != te { 316 t.Errorf("Tests not as expected.\nGot:\n%v\nExpect:\n%v\n------\nGot: %v\nExpect: %v", g, e, tg, te) 317 } 318} 319 320func checkCoverage(t *testing.T, tree *cov.Tree, file string, expect string) { 321 g, e := tree.FileCoverage(file).String(tree.Tests(), tree.Strings()), expect 322 if tg, te := trimWS(g), trimWS(e); tg != te { 323 t.Errorf("Coverage not as expected.\nGot:\n%v\nExpect:\n%v\n------\nGot: %v\nExpect: %v", g, e, tg, te) 324 } 325} 326 327func trimWS(s string) string { 328 s = strings.ReplaceAll(s, " ", "") 329 s = strings.ReplaceAll(s, "\n", "") 330 return s 331} 332 333func coverage(file string, spans ...cov.Span) *cov.Coverage { 334 return &cov.Coverage{ 335 []cov.File{ 336 cov.File{ 337 Path: file, 338 Covered: spans, 339 }, 340 }, 341 } 342} 343 344func spans(ids ...cov.SpanID) cov.SpanSet { 345 out := make(cov.SpanSet, len(ids)) 346 for _, id := range ids { 347 out[id] = struct{}{} 348 } 349 return out 350} 351 352func TestTreeEncodeDecode(t *testing.T) { 353 orig := &cov.Tree{} 354 orig.Add(cov.Path{"a", "b"}, coverage(fileA, span0, span1)) 355 orig.Add(cov.Path{"a", "b", "d", "i"}, coverage(fileA, span0, span1)) 356 orig.Add(cov.Path{"a", "b", "e"}, coverage(fileA, span0, span1, span2)) 357 orig.Add(cov.Path{"a", "c", "g", "n"}, coverage(fileB, span0, span3)) 358 orig.Add(cov.Path{"a", "c", "g", "o"}, coverage(fileB, span0, span3)) 359 orig.Add(cov.Path{"a", "c", "f"}, coverage(fileA, span1)) 360 orig.Add(cov.Path{"a", "b", "e", "j"}, coverage(fileC, span3)) 361 orig.Add(cov.Path{"a", "b", "e", "k"}, coverage(fileA, span3)) 362 orig.Add(cov.Path{"a", "c", "f", "l", "v"}, coverage(fileA, span1, span2)) 363 orig.Add(cov.Path{"a", "c", "f", "l", "x"}, coverage(fileA, span1, span2)) 364 orig.Add(cov.Path{"a", "c", "g", "n", "z"}, coverage(fileC, span2)) 365 orig.Add(cov.Path{"a", "b"}, coverage(fileA, span0, span1)) 366 orig.Add(cov.Path{"a", "b"}, coverage(fileA, span0, span1)) 367 368 origJSON := orig.JSON("revision goes here") 369 read, revision, err := cov.ReadJSON(strings.NewReader(origJSON)) 370 if err != nil { 371 t.Fatalf("cov.ReadJSON() failed with: %v", err) 372 } 373 readJSON := read.JSON(revision) 374 if origJSON != readJSON { 375 t.Fatalf("Encode -> Decode -> Encode produced different results:\nOriginal:\n\n%v\n\nRead:\n\n%v", origJSON, readJSON) 376 } 377} 378