GCC Code Coverage Report

chrono_batch_render/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
222 / 226
98.2%
Branches:
194 / 210
92.4%
Functions:
21 / 21
100.0%
stage/structure/paths.cpp
Line Branch Exec Source
1 // SPDX-License-Identifier: BSD-3-Clause
2 #include "chrono_batch_render/stage/structure/paths.h"
3
4 #include <algorithm>
5
6 #include "chrono_batch_render/util/error.h"
7 #include "chrono_batch_render/util/text.h"
8
9 namespace chrono::batch_render {
10
11 namespace {
12
13 59208 void CheckPath(std::string_view path) {
14
3/4
✓ Branch 0 taken 59208 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 59206 times.
 59208 if (path.empty() || path.front() != '/') {
15
1/1
✓ Branch 2 taken 2 times.
 2 throw Error("Path \"{}\" isn't absolute", path);
16 }
17
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 59205 times.
 59206 if (path == "/") {
18
2/2
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
 2 throw Error("The root, \"/\", isn't a prim");
19 }
20
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 59204 times.
 59205 if (path.back() == '/') {
21
1/1
✓ Branch 2 taken 1 time.
 1 throw Error("Path \"{}\" ends in /", path);
22 }
23 59204 }
24
25 }
26
27 138267 uint64_t Paths::Key(uint32_t parent, Token name) {
28 138267 return (uint64_t(parent) << 32) | name.id;
29 }
30
31 33147 const Paths::Node& Paths::Get(uint32_t prim) const {
32
3/4
✓ Branch 0 taken 33147 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 33146 times.
 33147 if (prim >= m_nodes.size() || !m_nodes[prim].used) {
33
1/1
✓ Branch 2 taken 1 time.
 1 throw Error("No prim {} in the hierarchy", prim);
34 }
35 33146 return m_nodes[prim];
36 }
37
38 206565 std::optional<Paths::Lazy> Paths::Locate(uint32_t prim) const {
39 206565 auto found = m_blockStarts.upper_bound(prim);
40
4/4
✓ Branch 0 taken 110890 times.
✓ Branch 1 taken 95675 times.
✓ Branch 2 taken 110359 times.
✓ Branch 3 taken 531 times.
 206565 if (prim == kNone || found == m_blockStarts.begin()) {
41 206034 return std::nullopt;
42 }
43
2/2
✓ Branch 1 taken 331 times.
✓ Branch 2 taken 200 times.
 531 const Block& block = m_blocks[std::prev(found)->second];
44
2/2
✓ Branch 0 taken 331 times.
✓ Branch 1 taken 200 times.
 531 const uint32_t count = uint32_t(block.shape.parent.size());
45 531 const uint32_t offset = prim - block.firstPrim;
46
4/4
✓ Branch 0 taken 331 times.
✓ Branch 1 taken 200 times.
✓ Branch 3 taken 299 times.
✓ Branch 4 taken 32 times.
 531 if (offset >= count * block.copies || block.explicitCopy[offset / count]) {
47 232 return std::nullopt;
48 }
49 299 return Lazy{&block, offset / count, offset % count};
50 }
51
52 35983 bool Paths::Contains(uint32_t prim) const {
53
4/4
✓ Branch 0 taken 995 times.
✓ Branch 1 taken 34988 times.
✓ Branch 2 taken 129 times.
✓ Branch 3 taken 866 times.
 35983 if (prim < m_nodes.size() && m_nodes[prim].used) {
54 return true;
55 }
56 35117 const std::optional<Lazy> lazy = Locate(prim);
57
3/4
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 35106 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 11 times.
 35117 return lazy && lazy->index > 0;
58 }
59
60 152623 uint32_t Paths::Child(uint32_t parent, std::string_view name) const {
61 152623 const Token token = m_tokens->Find(name);
62
2/2
✓ Branch 0 taken 102815 times.
✓ Branch 1 taken 49808 times.
 152623 if (token.id == 0) {
63 return kNone;
64 }
65
2/2
✓ Branch 1 taken 66 times.
✓ Branch 2 taken 102749 times.
 102815 if (const std::optional<Lazy> lazy = Locate(parent)) {
66 66 const auto found = lazy->block->shape.lookup.find(Key(lazy->index, token));
67
1/2
✓ Branch 0 taken 66 times.
✗ Branch 1 not taken.
 66 if (found == lazy->block->shape.lookup.end()) {
68 return kNone;
69 }
70 66 return lazy->block->firstPrim + lazy->copy * uint32_t(lazy->block->shape.parent.size()) +
71 66 found->second;
72 }
73 102749 const auto found = m_children.find(Key(parent, token));
74
2/2
✓ Branch 0 taken 93302 times.
✓ Branch 1 taken 9447 times.
 196051 return found == m_children.end() ? kNone : found->second;
75 }
76
77 35109 void Paths::Link(uint32_t prim, uint32_t parent, Token name) {
78
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 35109 times.
 35109 if (!m_children.emplace(Key(parent, name), prim).second) {
79
0/2
✗ Branch 2 not taken.
✗ Branch 5 not taken.
 ✗ throw Error("A prim named {} is already under prim {}", m_tokens->Text(name), parent);
80 }
81
2/2
✓ Branch 0 taken 34979 times.
✓ Branch 1 taken 130 times.
 35109 if (prim >= m_nodes.size()) {
82 34979 m_nodes.resize(size_t(prim) + 1);
83 }
84
2/2
✓ Branch 0 taken 12197 times.
✓ Branch 1 taken 22912 times.
 35109 Node& node = m_nodes[prim];
85 35109 node.parent = parent;
86 35109 node.name = name;
87
2/2
✓ Branch 0 taken 12197 times.
✓ Branch 1 taken 22912 times.
 35109 node.depth = parent == kRoot ? 0 : m_nodes[parent].depth + 1;
88 35109 node.used = true;
89 35109 node.children.clear();
90
2/2
✓ Branch 0 taken 22912 times.
✓ Branch 1 taken 12197 times.
 35109 (parent == kRoot ? m_roots : m_nodes[parent].children).push_back(prim);
91 35109 ++m_size;
92 35109 }
93
94 35360 void Paths::Materialize(uint32_t prim) {
95 35360 const std::optional<Lazy> lazy = Locate(prim);
96
2/2
✓ Branch 0 taken 35350 times.
✓ Branch 1 taken 10 times.
 35360 if (!lazy) {
97 35350 return;
98 }
99 10 Block& block = m_blocks[m_blockStarts.at(lazy->block->firstPrim)];
100 10 const uint32_t count = uint32_t(block.shape.parent.size());
101 10 const uint32_t first = block.firstPrim + lazy->copy * count;
102 10 block.explicitCopy[lazy->copy] = true;
103
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 10 times.
 23 for (uint32_t i = 1; i < count; ++i) {
104 13 Link(first + i, first + block.shape.parent[i], block.shape.name[i]);
105 }
106 10 m_lazy -= count - 1;
107 }
108
109 52 PathShape Paths::Shape(uint32_t source) {
110 52 const std::vector<uint32_t> subtree = Subtree(source);
111 52 PathShape shape;
112 52 std::unordered_map<uint32_t, uint32_t> index;
113
2/2
✓ Branch 0 taken 132 times.
✓ Branch 1 taken 52 times.
 184 for (uint32_t i = 0; i < subtree.size(); ++i) {
114
1/1
✓ Branch 1 taken 132 times.
 132 index[subtree[i]] = i;
115
4/4
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 52 times.
✓ Branch 3 taken 80 times.
✓ Branch 6 taken 80 times.
 132 const uint32_t parent = i == 0 ? kNone : index.at(Parent(subtree[i]));
116
1/1
✓ Branch 1 taken 132 times.
 132 shape.parent.push_back(parent);
117
2/2
✓ Branch 1 taken 132 times.
✓ Branch 4 taken 132 times.
 132 shape.name.push_back(m_tokens->Intern(Name(subtree[i])));
118
3/3
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 52 times.
✓ Branch 3 taken 132 times.
 132 shape.depth.push_back(i == 0 ? 0 : shape.depth[parent] + 1);
119
1/1
✓ Branch 1 taken 132 times.
 132 shape.children.emplace_back();
120
2/2
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 52 times.
 132 if (i > 0) {
121
1/1
✓ Branch 1 taken 80 times.
 80 shape.children[parent].push_back(i);
122
1/1
✓ Branch 1 taken 80 times.
 80 shape.lookup.emplace(Key(parent, shape.name[i]), i);
123 }
124 }
125 104 return shape;
126 52 }
127
128 51 void Paths::InsertClones(PathShape shape, std::span<const std::string> targets,
129 uint32_t firstPrim) {
130 51 const uint32_t count = uint32_t(shape.parent.size());
131 51 Block block;
132 51 block.shape = std::move(shape);
133 51 block.firstPrim = firstPrim;
134
1/1
✓ Branch 1 taken 51 times.
 51 block.copies = uint32_t(targets.size());
135
1/1
✓ Branch 1 taken 51 times.
 51 block.explicitCopy.assign(targets.size(), false);
136
2/2
✓ Branch 0 taken 1077 times.
✓ Branch 1 taken 51 times.
 1128 for (uint32_t copy = 0; copy < targets.size(); ++copy) {
137
1/1
✓ Branch 1 taken 1077 times.
 1077 Insert(targets[copy], firstPrim + copy * count);
138 }
139
1/1
✓ Branch 1 taken 51 times.
 51 m_blockStarts[firstPrim] = uint32_t(m_blocks.size());
140
1/1
✓ Branch 1 taken 51 times.
 51 m_blocks.push_back(std::move(block));
141 51 m_lazy += (count - 1) * uint32_t(targets.size());
142 51 }
143
144 118465 uint32_t Paths::Find(std::string_view path) const {
145
8/8
✓ Branch 0 taken 118464 times.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 118462 times.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 118461 times.
✓ Branch 5 taken 1 time.
✓ Branch 6 taken 2 times.
✓ Branch 7 taken 118459 times.
 118465 if (path.empty() || path.front() != '/' || path == "/" || path.back() == '/') {
146 6 return kNone;
147 }
148 118459 uint32_t prim = kRoot;
149
2/2
✓ Branch 2 taken 152623 times.
✓ Branch 3 taken 59204 times.
 211827 for (const std::string_view name : Split(path.substr(1), '/')) {
150
1/1
✓ Branch 1 taken 152623 times.
 152623 prim = Child(prim, name);
151
2/2
✓ Branch 0 taken 59255 times.
✓ Branch 1 taken 93368 times.
 152623 if (prim == kNone) {
152 59255 return kNone;
153 }
154 59255 }
155 59204 return prim;
156 }
157
158 24090 uint32_t Paths::FindParent(std::string_view path) const {
159 24090 CheckPath(path);
160 24089 const auto [parent, name] = SplitLast(path, '/');
161
2/2
✓ Branch 0 taken 1178 times.
✓ Branch 1 taken 22911 times.
 24089 return parent.empty() ? kRoot : Find(parent);
162 }
163
164 35107 void Paths::Insert(std::string_view path, uint32_t prim) {
165 35107 CheckPath(path);
166
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 35103 times.
 35104 if (prim == kNone) {
167
1/1
✓ Branch 2 taken 1 time.
 1 throw Error("Prim index {} is reserved", prim);
168 }
169
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 35102 times.
 35103 if (Contains(prim)) {
170
2/2
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
 2 throw Error("Prim {} is already at \"{}\"", prim, Path(prim));
171 }
172 35102 const auto [parentPath, text] = SplitLast(path, '/');
173
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 35100 times.
 35102 if (!IsIdentifier(text)) {
174 2 throw Error("\"{}\" in path \"{}\" isn't a name: names are letters, digits and _, and "
175 "don't start with a digit",
176
1/1
✓ Branch 2 taken 2 times.
 2 text, path);
177 }
178
4/4
✓ Branch 0 taken 12187 times.
✓ Branch 1 taken 22913 times.
✓ Branch 3 taken 22913 times.
✓ Branch 4 taken 2 times.
 35102 const uint32_t parent = parentPath.empty() ? kRoot : Find(parentPath);
179
4/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 12185 times.
✓ Branch 2 taken 22913 times.
✓ Branch 3 taken 2 times.
 35100 if (parent == kNone && !parentPath.empty()) {
180
1/1
✓ Branch 2 taken 2 times.
 2 throw Error("Path \"{}\" has no parent \"{}\"", path, parentPath);
181 }
182
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 35096 times.
 35098 if (Find(path) != kNone) {
183
1/1
✓ Branch 2 taken 2 times.
 2 throw Error("Path \"{}\" already has a prim", path);
184 }
185 35096 Materialize(parent);
186 35096 Link(prim, parent, m_tokens->Intern(text));
187 35096 }
188
189 248 void Paths::Erase(uint32_t prim) {
190
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 248 times.
 248 if (!Contains(prim)) {
191
0/1
✗ Branch 2 not taken.
 ✗ throw Error("No prim {} in the hierarchy", prim);
192 }
193 248 Materialize(prim);
194
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 247 times.
 248 Node& node = m_nodes[prim];
195
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 247 times.
 248 if (!node.children.empty()) {
196
1/1
✓ Branch 1 taken 1 time.
 1 throw Error("Prim \"{}\" has {} children; erase them first", Path(prim),
197
2/2
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
 2 node.children.size());
198 }
199 247 std::vector<uint32_t>& siblings =
200
2/2
✓ Branch 0 taken 228 times.
✓ Branch 1 taken 19 times.
 247 node.parent == kRoot ? m_roots : m_nodes[node.parent].children;
201 247 siblings.erase(std::ranges::find(siblings, prim));
202 247 m_children.erase(Key(node.parent, node.name));
203 247 m_nodes[prim] = {};
204 247 --m_size;
205 247 }
206
207 11 void Paths::Move(uint32_t prim, std::string_view path) {
208 11 CheckPath(path);
209
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 11 times.
 11 if (!Contains(prim)) {
210
0/1
✗ Branch 2 not taken.
 ✗ throw Error("No prim {} in the hierarchy", prim);
211 }
212 11 const auto [parentPath, text] = SplitLast(path, '/');
213
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 10 times.
 11 if (!IsIdentifier(text)) {
214 1 throw Error("\"{}\" in path \"{}\" isn't a name: names are letters, digits and _, and "
215 "don't start with a digit",
216
1/1
✓ Branch 2 taken 1 time.
 1 text, path);
217 }
218
3/4
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 5 times.
 10 const uint32_t parent = parentPath.empty() ? kRoot : Find(parentPath);
219
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 5 times.
 10 if (parent == kNone && !parentPath.empty()) {
220
0/1
✗ Branch 2 not taken.
 ✗ throw Error("Path \"{}\" has no parent \"{}\"", path, parentPath);
221 }
222
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 9 times.
 15 for (uint32_t at = parent; at != kRoot; at = Parent(at)) {
223
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 5 times.
 6 if (at == prim) {
224
2/2
✓ Branch 2 taken 1 time.
✓ Branch 5 taken 1 time.
 2 throw Error("\"{}\" can't move into its own subtree at \"{}\"", Path(prim), path);
225 }
226 }
227
2/2
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 8 times.
 9 if (Find(path) != kNone) {
228
1/1
✓ Branch 2 taken 1 time.
 1 throw Error("Path \"{}\" already has a prim", path);
229 }
230 8 Materialize(prim);
231 8 Materialize(parent);
232 8 const Token name = m_tokens->Intern(text);
233
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 Node& node = m_nodes[prim];
234 8 std::vector<uint32_t>& siblings =
235
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 node.parent == kRoot ? m_roots : m_nodes[node.parent].children;
236 8 siblings.erase(std::ranges::find(siblings, prim));
237 8 m_children.erase(Key(node.parent, node.name));
238 8 m_children.emplace(Key(parent, name), prim);
239 8 node.parent = parent;
240 8 node.name = name;
241
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
 8 (parent == kRoot ? m_roots : m_nodes[parent].children).push_back(prim);
242 8 std::vector<uint32_t> stack = {prim};
243
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 8 times.
 21 while (!stack.empty()) {
244 13 Node& at = m_nodes[stack.back()];
245 13 stack.pop_back();
246
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 4 times.
 13 at.depth = at.parent == kRoot ? 0 : m_nodes[at.parent].depth + 1;
247
1/1
✓ Branch 1 taken 13 times.
 13 stack.insert(stack.end(), at.children.begin(), at.children.end());
248 }
249 8 }
250
251 9985 std::string Paths::Path(uint32_t prim) const {
252 9985 std::vector<std::string_view> names;
253
2/2
✓ Branch 0 taken 14353 times.
✓ Branch 1 taken 9984 times.
 24337 for (uint32_t at = prim; at != kRoot; at = Parent(at)) {
254
2/2
✓ Branch 1 taken 14352 times.
✓ Branch 4 taken 14352 times.
 28705 names.push_back(Name(at));
255 }
256 9984 std::string path;
257
2/2
✓ Branch 0 taken 14352 times.
✓ Branch 1 taken 9984 times.
 24336 for (auto name = names.rbegin(); name != names.rend(); ++name) {
258
1/1
✓ Branch 1 taken 14352 times.
 14352 path += '/';
259
1/1
✓ Branch 1 taken 14352 times.
 14352 path += *name;
260 }
261 9984 return path;
262 9984 }
263
264 18006 std::string_view Paths::Name(uint32_t prim) const {
265
4/4
✓ Branch 1 taken 105 times.
✓ Branch 2 taken 17901 times.
✓ Branch 3 taken 60 times.
✓ Branch 4 taken 45 times.
 18006 if (const std::optional<Lazy> lazy = Locate(prim); lazy && lazy->index > 0) {
266 60 return m_tokens->Text(lazy->block->shape.name[lazy->index]);
267 }
268 17946 return m_tokens->Text(Get(prim).name);
269 }
270
271 14461 uint32_t Paths::Parent(uint32_t prim) const {
272
4/4
✓ Branch 1 taken 88 times.
✓ Branch 2 taken 14373 times.
✓ Branch 3 taken 48 times.
✓ Branch 4 taken 40 times.
 14461 if (const std::optional<Lazy> lazy = Locate(prim); lazy && lazy->index > 0) {
273 48 const uint32_t count = uint32_t(lazy->block->shape.parent.size());
274 48 return lazy->block->firstPrim + lazy->copy * count + lazy->block->shape.parent[lazy->index];
275 }
276 14413 return Get(prim).parent;
277 }
278
279 3 uint32_t Paths::Depth(uint32_t prim) const {
280
3/4
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 1 time.
✗ Branch 4 not taken.
 3 if (const std::optional<Lazy> lazy = Locate(prim); lazy && lazy->index > 0) {
281 1 const uint32_t count = uint32_t(lazy->block->shape.parent.size());
282 1 return Get(lazy->block->firstPrim + lazy->copy * count).depth +
283 1 lazy->block->shape.depth[lazy->index];
284 }
285 2 return Get(prim).depth;
286 }
287
288 1042 std::vector<uint32_t> Paths::Children(uint32_t prim) const {
289
2/2
✓ Branch 0 taken 239 times.
✓ Branch 1 taken 803 times.
 1042 if (prim == kRoot) {
290 239 return m_roots;
291 }
292
2/2
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 785 times.
 803 if (const std::optional<Lazy> lazy = Locate(prim)) {
293 18 const uint32_t first =
294 18 lazy->block->firstPrim + lazy->copy * uint32_t(lazy->block->shape.parent.size());
295 18 std::vector<uint32_t> children;
296
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 18 times.
 35 for (const uint32_t child : lazy->block->shape.children[lazy->index]) {
297
1/1
✓ Branch 1 taken 17 times.
 17 children.push_back(first + child);
298 }
299 18 return children;
300 18 }
301 785 return Get(prim).children;
302 }
303
304 376 std::vector<uint32_t> Paths::Subtree(uint32_t prim) const {
305 376 std::vector<uint32_t> order;
306
1/1
✓ Branch 1 taken 376 times.
 376 std::vector<uint32_t> stack = {prim};
307
4/4
✓ Branch 0 taken 375 times.
✓ Branch 1 taken 1 time.
✓ Branch 3 taken 1 time.
✓ Branch 4 taken 374 times.
 376 if (prim != kRoot && !Contains(prim)) {
308
1/1
✓ Branch 2 taken 1 time.
 1 throw Error("No prim {} in the hierarchy", prim);
309 }
310
2/2
✓ Branch 0 taken 578 times.
✓ Branch 1 taken 375 times.
 953 while (!stack.empty()) {
311 578 const uint32_t at = stack.back();
312 578 stack.pop_back();
313
2/2
✓ Branch 0 taken 577 times.
✓ Branch 1 taken 1 time.
 578 if (at != kRoot) {
314
1/1
✓ Branch 1 taken 577 times.
 577 order.push_back(at);
315 }
316
1/1
✓ Branch 1 taken 578 times.
 578 const std::vector<uint32_t> children = Children(at);
317
1/1
✓ Branch 1 taken 578 times.
 578 stack.insert(stack.end(), children.rbegin(), children.rend());
318 578 }
319 375 return order;
320 377 }
321
322 }
323