GCC Code Coverage Report

ernie/
Coverage:
low: ≥ 0%
medium: ≥ 75.0%
high: ≥ 90.0%
Lines:
118 / 125
94.4%
Branches:
127 / 168
75.6%
Functions:
27 / 28
96.4%
scene/path.cpp
Line Branch Exec Source
1 // SPDX-License-Identifier: BSD-3-Clause
2 /// @file path.cpp
3 /// @brief Path parsing, token interning and the path table.
4 #include "ernie/scene/path.h"
5
6 #include "ernie/util/random.h"
7 #include "ernie/util/text.h"
8
9 #include <algorithm>
10 #include <stdexcept>
11
12 namespace ernie {
13
14 namespace {
15
16 /// Calls `visit(name)` for each name of an absolute path's text; "/a/" ends in an empty name.
17
5/6
void ernie::(anonymous namespace)::ForEachName<ernie::Path::Path(std::basic_string_view<char, std::char_traits<char> >)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::Path::Path(std::basic_string_view<char, std::char_traits<char> >)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 9144 times.
✓ Branch 1 taken 46 times.
void ernie::(anonymous namespace)::ForEachName<ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 3932 times.
✓ Branch 1 taken 1 time.
void ernie::(anonymous namespace)::ForEachName<ernie::PathTable::Intern(ernie::Path const&)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::PathTable::Intern(ernie::Path const&)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 3112 times.
✗ Branch 1 not taken.
 16235 template <typename Visit> void ForEachName(std::string_view text, const Visit& visit) {
18
5/6
void ernie::(anonymous namespace)::ForEachName<ernie::Path::Path(std::basic_string_view<char, std::char_traits<char> >)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::Path::Path(std::basic_string_view<char, std::char_traits<char> >)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 9144 times.
✓ Branch 1 taken 46 times.
void ernie::(anonymous namespace)::ForEachName<ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 3932 times.
✓ Branch 1 taken 1 time.
void ernie::(anonymous namespace)::ForEachName<ernie::PathTable::Intern(ernie::Path const&)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::PathTable::Intern(ernie::Path const&)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 3112 times.
✗ Branch 1 not taken.
 16235 if (text.size() <= 1) {
19 return;
20 }
21
6/6
void ernie::(anonymous namespace)::ForEachName<ernie::Path::Path(std::basic_string_view<char, std::char_traits<char> >)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::Path::Path(std::basic_string_view<char, std::char_traits<char> >)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 12477 times.
✓ Branch 1 taken 9138 times.
void ernie::(anonymous namespace)::ForEachName<ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 5359 times.
✓ Branch 1 taken 3932 times.
void ernie::(anonymous namespace)::ForEachName<ernie::PathTable::Intern(ernie::Path const&)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::PathTable::Intern(ernie::Path const&)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 4137 times.
✓ Branch 1 taken 3112 times.
 38155 for (std::size_t start = 1; start <= text.size();) {
22
6/6
void ernie::(anonymous namespace)::ForEachName<ernie::Path::Path(std::basic_string_view<char, std::char_traits<char> >)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::Path::Path(std::basic_string_view<char, std::char_traits<char> >)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 9142 times.
✓ Branch 1 taken 3335 times.
void ernie::(anonymous namespace)::ForEachName<ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::PathTable::Find(ernie::Path const&) const::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 3932 times.
✓ Branch 1 taken 1427 times.
void ernie::(anonymous namespace)::ForEachName<ernie::PathTable::Intern(ernie::Path const&)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1}>(std::basic_string_view<char, std::char_traits<char> >, ernie::PathTable::Intern(ernie::Path const&)::{lambda(std::basic_string_view<char, std::char_traits<char> >)#1} const&):
✓ Branch 0 taken 3112 times.
✓ Branch 1 taken 1025 times.
 21973 const std::size_t end = std::min(text.find('/', start), text.size());
23 21973 visit(text.substr(start, end - start));
24 21967 start = end + 1;
25 }
26 }
27
28 } // namespace
29
30 12482 bool Path::IsValidName(std::string_view name) {
31 12482 return IsIdentifier(name);
32 }
33
34
2/2
✓ Branch 0 taken 9191 times.
✓ Branch 1 taken 1 time.
 9192 Path::Path(std::string_view text) {
35
4/4
✓ Branch 0 taken 9191 times.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 9190 times.
 9192 if (text.empty() || text.front() != '/') {
36
3/6
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
 6 throw std::invalid_argument("Prim path '" + std::string(text) + "' is not absolute");
37 }
38
2/2
✓ Branch 1 taken 9184 times.
✓ Branch 2 taken 6 times.
 9190 ForEachName(text, [&](std::string_view name) {
39
2/2
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 12471 times.
 12477 if (!IsValidName(name)) {
40
2/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
 12 throw std::invalid_argument("Prim path '" + std::string(text) +
41
2/4
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
 18 "' has an invalid name");
42 }
43 12471 });
44
1/2
✓ Branch 1 taken 9184 times.
✗ Branch 2 not taken.
 9184 text_ = text;
45 9192 }
46
47 44 Path Path::Root() {
48 44 return Path("/");
49 }
50
51 19 std::string_view Path::Name() const {
52
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 18 times.
 19 if (text_.size() <= 1) {
53 1 return {};
54 }
55 18 return std::string_view(text_).substr(text_.rfind('/') + 1);
56 }
57
58 7 Path Path::Parent() const {
59
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 5 times.
 7 if (text_.size() <= 1) {
60 2 return {};
61 }
62 5 const std::size_t slash = text_.rfind('/');
63
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
 5 return slash == 0 ? Root() : Path(std::string_view(text_).substr(0, slash));
64 }
65
66 4 Path Path::Child(std::string_view name) const {
67
4/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 time.
✓ Branch 3 taken 1 time.
✓ Branch 4 taken 2 times.
 4 if (IsEmpty() || !IsValidName(name)) {
68
4/8
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 2 times.
✗ Branch 12 not taken.
 8 throw std::invalid_argument("Cannot append '" + std::string(name) + "' to '" + text_ + "'");
69 }
70
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
 2 Path child;
71
13/24
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 1 time.
✓ Branch 3 taken 1 time.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 time.
✗ Branch 7 not taken.
✓ Branch 9 taken 1 time.
✗ Branch 10 not taken.
✓ Branch 12 taken 1 time.
✗ Branch 13 not taken.
✓ Branch 15 taken 1 time.
✗ Branch 16 not taken.
✓ Branch 19 taken 1 time.
✓ Branch 20 taken 1 time.
✓ Branch 21 taken 1 time.
✓ Branch 22 taken 1 time.
✓ Branch 23 taken 1 time.
✓ Branch 24 taken 1 time.
✗ Branch 25 not taken.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
✗ Branch 30 not taken.
 5 child.text_ = IsRoot() ? "/" + std::string(name) : text_ + "/" + std::string(name);
72 2 return child;
73 ✗ }
74
75 6 bool Path::HasPrefix(const Path& ancestor) const {
76
4/4
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 1 time.
 6 if (ancestor.IsEmpty() || IsEmpty()) {
77 return false;
78 }
79
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 time.
 4 if (ancestor.IsRoot()) {
80 return true;
81 }
82
3/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 1 time.
 3 return text_.starts_with(ancestor.text_) &&
83
4/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 time.
✓ Branch 2 taken 1 time.
✓ Branch 3 taken 1 time.
 3 (text_.size() == ancestor.text_.size() || text_[ancestor.text_.size()] == '/');
84 }
85
86
1/2
✓ Branch 2 taken 244 times.
✗ Branch 3 not taken.
 244 TokenTable::TokenTable() {
87
1/2
✓ Branch 1 taken 244 times.
✗ Branch 2 not taken.
 244 Intern("");
88 244 }
89
90 27019 Token TokenTable::Intern(std::string_view text) {
91 27019 const auto next = static_cast<Token>(texts_.size());
92 27019 const Token token = index_.Insert(std::hash<std::string_view>()(text), next,
93 43708 [&](Token other) { return texts_[other] == text; });
94
2/2
✓ Branch 0 taken 10330 times.
✓ Branch 1 taken 16689 times.
 27019 if (token == next) {
95 10330 texts_.emplace_back(text);
96 }
97 27019 return token;
98 }
99
100 27092 std::optional<Token> TokenTable::Find(std::string_view text) const {
101 27092 return index_.Find(std::hash<std::string_view>()(text),
102 53845 [&](Token other) { return texts_[other] == text; });
103 }
104
105
1/2
✓ Branch 2 taken 243 times.
✗ Branch 3 not taken.
 243 PathTable::PathTable() : nodes_(1) {}
106
107 9480 std::uint64_t PathTable::Hash(PathId parent, Token name) {
108 9480 return Mix64(std::uint64_t{parent} << 32 | name);
109 }
110
111 ✗ void PathTable::Reserve(std::size_t count) {
112 ✗ nodes_.reserve(nodes_.size() + count);
113 ✗ children_.Reserve(children_.Size() + count);
114 ✗ names_.Reserve(count);
115 ✗ }
116
117 4138 PathId PathTable::Child(PathId parent, Token name) {
118 4138 const auto next = static_cast<PathId>(nodes_.size());
119 4138 const PathId id = children_.Insert(Hash(parent, name), next, [&](PathId other) {
120
2/4
✓ Branch 0 taken 931 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 931 times.
 931 return nodes_[other].parent == parent && nodes_[other].name == name;
121 });
122
2/2
✓ Branch 0 taken 3207 times.
✓ Branch 1 taken 931 times.
 4138 if (id != next) {
123 return id;
124 }
125 3207 nodes_.push_back({parent, name});
126
2/2
✓ Branch 0 taken 703 times.
✓ Branch 1 taken 2504 times.
 3207 Node& above = nodes_[parent];
127
2/2
✓ Branch 0 taken 703 times.
✓ Branch 1 taken 2504 times.
 3207 if (above.firstChild == kNoPath) {
128 703 above.firstChild = id;
129 } else {
130 2504 nodes_[above.lastChild].nextSibling = id;
131 }
132 3207 above.lastChild = id;
133 3207 return id;
134 }
135
136 3113 PathId PathTable::Intern(const Path& path) {
137
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 3112 times.
 3113 if (path.IsEmpty()) {
138
1/2
✓ Branch 2 taken 1 time.
✗ Branch 3 not taken.
 1 throw std::invalid_argument("An empty path names no prim");
139 }
140 3112 PathId id = kRootPath;
141 7249 ForEachName(path.String(), [&](std::string_view name) { id = Child(id, name); });
142 3112 return id;
143 }
144
145 3933 std::optional<PathId> PathTable::Find(const Path& path) const {
146
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 3933 times.
 3933 if (path.IsEmpty()) {
147 ✗ return std::nullopt;
148 }
149 3933 PathId id = kRootPath;
150 3933 bool found = true;
151 3933 ForEachName(path.String(), [&](std::string_view name) {
152
1/2
✓ Branch 0 taken 5359 times.
✗ Branch 1 not taken.
 5359 const std::optional<Token> token = found ? names_.Find(name) : std::nullopt;
153
2/2
✓ Branch 0 taken 5342 times.
✓ Branch 1 taken 17 times.
 5359 const std::optional<PathId> child =
154
2/2
✓ Branch 0 taken 5342 times.
✓ Branch 1 taken 17 times.
 5359 token ? children_.Find(Hash(id, *token),
155 5342 [&](PathId other) {
156
2/4
✓ Branch 0 taken 5342 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 5342 times.
 5342 return nodes_[other].parent == id &&
157
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 5342 times.
 5342 nodes_[other].name == *token;
158 })
159 17 : std::nullopt;
160
2/2
✓ Branch 0 taken 5342 times.
✓ Branch 1 taken 17 times.
 5359 found = child.has_value();
161
2/2
✓ Branch 0 taken 5342 times.
✓ Branch 1 taken 17 times.
 5359 if (found) {
162 5342 id = *child;
163 }
164 5359 });
165
2/2
✓ Branch 0 taken 3916 times.
✓ Branch 1 taken 17 times.
 3933 return found ? std::optional(id) : std::nullopt;
166 }
167
168 4161 Path PathTable::ToPath(PathId id) const {
169
2/2
✓ Branch 0 taken 1 time.
✓ Branch 1 taken 4160 times.
 4161 if (id == kRootPath) {
170 1 return Path::Root();
171 }
172 4160 std::vector<std::string_view> names;
173
2/2
✓ Branch 0 taken 5709 times.
✓ Branch 1 taken 4160 times.
 9869 for (; id != kRootPath; id = nodes_[id].parent) {
174
1/2
✓ Branch 2 taken 5709 times.
✗ Branch 3 not taken.
 5709 names.push_back(names_.Text(nodes_[id].name));
175 }
176 4160 std::string text;
177
2/2
✓ Branch 0 taken 5709 times.
✓ Branch 1 taken 4160 times.
 9869 for (auto name = names.rbegin(); name != names.rend(); ++name) {
178
1/2
✓ Branch 1 taken 5709 times.
✗ Branch 2 not taken.
 5709 text += '/';
179
1/2
✓ Branch 1 taken 5709 times.
✗ Branch 2 not taken.
 5709 text += *name;
180 }
181
1/2
✓ Branch 1 taken 4160 times.
✗ Branch 2 not taken.
 4160 return Path(text);
182 4160 }
183
184 3 bool PathTable::HasPrefix(PathId id, PathId ancestor) const {
185
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 1 time.
 10 for (; id != kNoPath; id = nodes_[id].parent) {
186
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 2 times.
 9 if (id == ancestor) {
187 return true;
188 }
189 }
190 return false;
191 }
192
193 } // namespace ernie
194