Blender V5.3
intermediate.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2025 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
9
10#include "intermediate.hh"
11#include "scope.hh"
12#include "token.hh"
13#include "token_stream.hh"
14
15#include "lexit/lexit.hh"
16#include "lexit/tables.hh"
17
18#if defined(_MSC_VER)
19# include <malloc.h>
20#endif
21
22#include <algorithm>
23#include <array>
24#include <cstdlib>
25#include <cstring>
26
27#if defined(_MSC_VER)
28# define always_inline __forceinline
29#else
30# define always_inline inline __attribute__((always_inline))
31#endif
32
34
35size_t line_number(const std::string_view &str, size_t pos)
36{
37 std::string_view directive = "#line ";
38 /* String to count the number of line. */
39 std::string_view sub_str = str.substr(0, pos);
40 size_t nearest_line_directive = sub_str.rfind(directive);
41 size_t line_count = 1;
42 if (nearest_line_directive != std::string::npos) {
43 sub_str = sub_str.substr(nearest_line_directive + directive.size());
44 line_count = std::stoll(std::string(sub_str)) - 1;
45 }
46 return line_count + std::count(sub_str.begin(), sub_str.end(), '\n');
47}
48
49size_t char_number(const std::string_view &str, size_t pos)
50{
51 std::string_view sub_str = str.substr(0, pos);
52 size_t nearest_line_directive = sub_str.rfind('\n');
53 return (nearest_line_directive == std::string::npos) ?
54 (sub_str.size()) :
55 (sub_str.size() - nearest_line_directive - 1);
56}
57
58std::string filename(const std::string_view &str, size_t pos)
59{
60 std::string_view directive = "#line ";
61 std::string_view sub_str = str.substr(0, pos);
62
63 while (!sub_str.empty()) {
64 size_t nearest_line_directive = sub_str.rfind(directive);
65 /* If no directive is found, break and return an empty string. */
66 if (nearest_line_directive == std::string_view::npos) {
67 break;
68 }
69 /* Extract just the line containing the directive. */
70 size_t line_end = sub_str.find('\n', nearest_line_directive);
71 std::string_view directive_line = sub_str.substr(nearest_line_directive,
72 line_end - nearest_line_directive);
73 /* Look for the quotes containing the filepath. */
74 size_t first_quote = directive_line.find('"');
75 if (first_quote != std::string_view::npos) {
76 size_t second_quote = directive_line.find('"', first_quote + 1);
77 if (second_quote != std::string_view::npos) {
78 return std::string(directive_line.substr(first_quote + 1, second_quote - first_quote - 1));
79 }
80 }
81 /* If this directive didn't have a filename, shrink the search space to look further up. */
82 if (nearest_line_directive == 0) {
83 break;
84 }
85 sub_str = sub_str.substr(0, nearest_line_directive);
86 }
87 return "";
88}
89
90std::string line_str(const std::string_view &str, size_t pos)
91{
92 size_t start = str.rfind('\n', pos);
93 size_t end = str.find('\n', pos);
94 start = (start != std::string::npos) ? start + 1 : 0;
95 return std::string(str.substr(start, end - start));
96}
97
98Scope Token::scope() const
99{
100 const ParserBase &parser = static_cast<const ParserBase &>(*buf_);
101 if (this->is_invalid()) {
102 return Scope(parser, -1);
103 }
104 return Scope(parser, parser.token_scope[index_]);
105}
106
107Scope Token::attribute_before() const
108{
109 const ParserBase &parser = static_cast<const ParserBase &>(*buf_);
110 if (is_invalid()) {
111 return Scope(parser, -1);
112 }
113 Token prev = this->prev();
114 if (prev == ']' && prev.prev().scope().type() == ScopeType::Attributes) {
115 return prev.prev().scope();
116 }
117 return Scope(parser, -1);
118}
119
120Scope Token::attribute_after() const
121{
122 const ParserBase &parser = static_cast<const ParserBase &>(*buf_);
123 if (is_invalid()) {
124 return Scope(parser, -1);
125 }
126 Token next = this->next();
127 if (next == '[' && next.next().scope().type() == ScopeType::Attributes) {
128 return next.next().scope();
129 }
130 return Scope(parser, -1);
131}
132
133void ErrorHandler::report(Token tok, std::string_view message)
134{
135 /* Only log the first error. */
136 if (err) {
137 return;
138 }
139
140 std::string token_filename = tok.filename();
141 std::string full_report = token_filename.empty() ? default_filename : token_filename;
142 full_report += ":" + std::to_string(tok.line_number());
143 full_report += ":" + std::to_string(tok.char_number() + 1);
144 full_report += ": " + std::string(message);
145 if (tok.is_valid()) {
146 full_report += "\n";
147 full_report += tok.line_str() + "\n";
148 if (!tok.str().empty()) {
149 full_report += std::string(tok.char_number(), ' ') + "^" +
150 std::string(tok.str().size() - 1, '~');
151 }
152 }
153 err = {std::string(message), full_report};
154}
155
156void ErrorHandler::report(const std::vector<std::pair<Token, std::string>> &reports)
157{
158 /* Only log the first error. */
159 if (err) {
160 return;
161 }
162
163 std::string message = reports.front().second;
164 std::string full_report;
165
166 for (const auto &[tok, msg] : reports) {
167 report(tok, msg);
168 full_report += "\n" + err->full_report;
169 err = std::nullopt;
170 }
171
172 err = {message, full_report};
173}
174
175void ErrorHandler::report(int row, int column, std::string line, std::string_view message)
176{
177 /* Only log the first error. */
178 if (err) {
179 return;
180 }
181
182 std::string full_report = default_filename;
183 full_report += ":" + std::to_string(row);
184 full_report += ":" + std::to_string(column + 1);
185 full_report += ": " + std::string(message) + "\n";
186 full_report += line;
187 err = {std::string(message), full_report};
188}
189
190alignas(128) const std::array<CharClass, 128> LexerBase::default_char_class_table = [] {
191 std::array<CharClass, 128> table;
192 memcpy(table.data(), lexit::char_class_table, sizeof(lexit::char_class_table));
193 return table;
194}();
195
196/* Same thing as default table but consider numbers as words to avoid second merging pass. */
197alignas(128) const std::array<CharClass, 128> LexerBase::bsl_char_class_table = [] {
198 std::array<CharClass, 128> table;
199 memcpy(table.data(), lexit::char_class_table, sizeof(lexit::char_class_table));
200
201 table['\n'] = CharClass::WhiteSpace;
202 /* Make < and > separators in order to support template.
203 * That means >= and <= need to be manually handled. */
204 table['<'] = CharClass::Separator;
205 table['>'] = CharClass::Separator;
206 return table;
207}();
208
209static always_inline TokenType multi_tok_lookup(TokenType input, std::string_view s)
210{
211 switch (s.size()) {
212 case 2:
213 switch (s[0]) {
214 case '=':
215 return (s[1] == '=') ? Equal : input;
216 case '!':
217 return (s[1] == '=') ? NotEqual : input;
218 case '|':
219 return (s[1] == '|') ? LogicalOr : input;
220 case '&':
221 return (s[1] == '&') ? LogicalAnd : input;
222 case '<':
223 return (s[1] == '<') ? LShift : ((s[1] == '=') ? LEqual : input);
224 case '>':
225 return (s[1] == '>') ? RShift : ((s[1] == '=') ? GEqual : input);
226 case '+':
227 return (s[1] == '+') ? Increment : ((s[1] == '=') ? AssignAdd : input);
228 case '-':
229 return (s[1] == '-') ? Decrement : ((s[1] == '=') ? AssignSub : input);
230 case '*':
231 return (s[1] == '=') ? AssignMul : input;
232 case '/':
233 return (s[1] == '=') ? AssignDiv : input;
234 case '#':
235 return (s[1] == '#') ? DoubleHash : input;
236 default:
237 return input;
238 }
239 case 3:
240 switch (s[0]) {
241 case '<':
242 return (s[1] == '<' && s[2] == '=') ? AssignLShift : input;
243 case '>':
244 return (s[1] == '>' && s[2] == '=') ? AssignRShift : input;
245 default:
246 return input;
247 }
248 default:
249 return input;
250 }
251}
252
253constexpr always_inline uint8_t perfect_hash(std::string_view s)
254{
255 int sz = s.size();
256 return s.size() * (s[0] - s[std::min(1, sz - 1)] * 2 - s.back() * 2);
257}
258
259static always_inline TokenType type_lookup(std::string_view s)
260{
261 switch (perfect_hash(s)) {
262 case perfect_hash("do"):
263 return (s == "do") ? Do : Word;
264 case perfect_hash("if"):
265 return (s == "if") ? If : Word;
266 case perfect_hash("for"):
267 return (s == "for") ? For : Word;
268 case perfect_hash("case"):
269 return (s == "case") ? Case : Word;
270 case perfect_hash("else"):
271 return (s == "else") ? Else : Word;
272 case perfect_hash("enum"):
273 return (s == "enum") ? Enum : Word;
274 case perfect_hash("this"):
275 return (s == "this") ? This : Word;
276 case perfect_hash("break"):
277 return (s == "break") ? Break : Word;
278 case perfect_hash("class"):
279 return (s == "class") ? Class : Word;
280 case perfect_hash("const"):
281 return (s == "const") ? Const : Word;
282 case perfect_hash("union"):
283 return (s == "union") ? Union : Word;
284 case perfect_hash("using"):
285 return (s == "using") ? Using : Word;
286 case perfect_hash("while"):
287 return (s == "while") ? While : Word;
288 case perfect_hash("inline"):
289 return (s == "inline") ? Inline : Word;
290 case perfect_hash("public"):
291 return (s == "public") ? Public : Word;
292 case perfect_hash("return"):
293 return (s == "return") ? Return : Word;
294 case perfect_hash("static"):
295 return (s == "static") ? Static : Word;
296 case perfect_hash("struct"):
297 return (s == "struct") ? Struct : Word;
298 case perfect_hash("switch"):
299 return (s == "switch") ? Switch : Word;
300 case perfect_hash("default"):
301 return (s == "default") ? Default : Word;
302 case perfect_hash("private"):
303 return (s == "private") ? Private : Word;
304 case perfect_hash("continue"):
305 return (s == "continue") ? Continue : Word;
306 case perfect_hash("template"):
307 return (s == "template") ? Template : Word;
308 case perfect_hash("typename"):
309 return (s == "typename") ? Typename : Word;
310 case perfect_hash("constexpr"):
311 return (s == "constexpr") ? Constexpr : Word;
312 case perfect_hash("namespace"):
313 return (s == "namespace") ? Namespace : Word;
314 default:
315 return Word;
316 }
317}
318
320{
321 for (auto tok : *this) {
322 switch (tok.type()) {
323 case Word:
324 tok.type() = type_lookup(tok.str());
325 break;
326 case Number:
327 break;
328 default:
329 tok.type() = multi_tok_lookup(tok.type(), tok.str());
330 break;
331 }
332 }
333}
334
336{
337 for (int i = 1; i < size(); ++i) {
338 TokenMut tok = (*this)[i];
339 TokenType type = tok.type();
340 if (type == '<' || type == '>') {
341 Token prev = (*this)[i - 1];
342 const bool preceded_by_space = prev.followed_by_whitespace();
343 /* Rely on the fact that template are formatted without spaces but comparison isn't. */
344 if (type == '<') {
345 if ((!preceded_by_space && prev != AngleOpen) || prev == Template) {
346 tok.type() = TemplateOpen;
347 }
348 }
349 else {
350 if (!preceded_by_space && (prev != AngleClose) && (prev != Minus)) {
351 tok.type() = TemplateClose;
352 }
353 }
354 }
355 }
356}
357
359{
360 for (int i = 1; i < size(); ++i) {
361 TokenMut tok = (*this)[i];
362 switch (tok.type()) {
363 case TemplateOpen:
364 tok.type() = lexit::AngleOpen;
365 break;
366 case TemplateClose:
367 tok.type() = lexit::AngleClose;
368 break;
369 default:
370 break;
371 }
372 }
373}
374
376 struct Item {
378 size_t start;
379 int index;
380 };
381
382 int scope_index = 0;
383 std::vector<ScopeStack::Item> scopes;
384 /* Output. */
385 std::vector<IndexRange> ranges;
386 std::vector<ScopeType> types;
387
388 ScopeStack(size_t predicted_scope_count)
389 {
390 /* Predicted max nesting depth. */
391 scopes.reserve(128);
392
393 ranges.reserve(predicted_scope_count);
394 types.reserve(predicted_scope_count);
395 }
396
397 void always_inline enter_scope(ScopeType type, size_t start_tok_id)
398 {
399 scopes.emplace_back(Item{type, start_tok_id, scope_index++});
400 ranges.emplace_back(start_tok_id, 1);
401 types.emplace_back(type);
402 };
403
404 void always_inline exit_scope(int end_tok_id)
405 {
406 if (scopes.empty()) {
407 return;
408 }
409 Item scope = scopes.back();
410 ranges[scope.index].size = end_tok_id - scope.start + 1;
411 scopes.pop_back();
412 };
413
415 {
416 return scopes.back();
417 }
418
419 bool always_inline empty() const
420 {
421 return scopes.empty();
422 }
423};
424
426{
427 token_scope.clear();
428 token_scope.resize(this->size() + 1);
429
430 int scope_id = 0;
431 for (const IndexRange &range : scope_ranges) {
432 std::fill(token_scope.begin() + range.start,
433 token_scope.begin() + range.start + range.size,
434 scope_id);
435 scope_id++;
436 }
437
438 update_string_view();
439}
440
442{
443 return Token(*this, i);
444}
445
446void ParserBase::update_string_view()
447{
448 assert(this->scope_types.data() != nullptr);
449 assert(!this->scope_types.empty());
450 this->scope_types_str = std::string_view(reinterpret_cast<char *>(this->scope_types.data()),
451 this->scope_types.size());
452}
453
454bool MutableString::apply_mutations(LexerBase &lexer, const bool all_mutation_ordered)
455{
456 if (mutations_.empty()) {
457 return false;
458 }
459
460 if (!all_mutation_ordered) {
461 /* Order mutations so that they can be applied in one pass. */
462 std::stable_sort(mutations_.begin(), mutations_.end());
463 }
464#ifndef NDEBUG
465 else {
466 assert(std::is_sorted(mutations_.begin(), mutations_.end()));
467 }
468#endif
469
470 /* Make sure to pad the input string in case of insertion after the last char. */
471 bool added_trailing_new_line = false;
472 if (str_.back() != '\n') {
473 str_ += '\n';
474 added_trailing_new_line = true;
475 }
476
477 std::string result;
478 result.reserve(str_.size());
479
480 int64_t offset = 0;
481 for (const Mutation &mut : mutations_) {
482 size_t start = mut.src_range.start;
483 size_t end = start + mut.src_range.size;
484 /* Copy unchanged text. */
485 result.append(str_.data() + offset, start - offset);
486 /* Append replacement. */
487 result.append(mut.replacement);
488 offset = end;
489 }
490 result.append(str_.data() + offset, str_.size() - offset);
491
492 str_ = std::move(result);
493
494 mutations_.clear();
495
496 if (added_trailing_new_line) {
497 str_.pop_back();
498 }
499 /* String have changed. Update string view. */
500 lexer.str_ = str_;
501 return true;
502}
503
504} // namespace blender::gpu::shader::parser
#define str(s)
#define always_inline
size_t line_number(const std::string_view &str, size_t pos)
static always_inline TokenType type_lookup(std::string_view s)
std::string filename(const std::string_view &str, size_t pos)
size_t char_number(const std::string_view &str, size_t pos)
std::string line_str(const std::string_view &str, size_t pos)
constexpr always_inline uint8_t perfect_hash(std::string_view s)
static always_inline TokenType multi_tok_lookup(TokenType input, std::string_view s)
__int64 int64_t
Definition BKE_text.h:90
unsigned char uint8_t
Definition BKE_text.h:79
TokenType
Definition types.hh:41
@ RShift
Definition types.hh:126
@ Default
Definition types.hh:129
@ While
Definition types.hh:92
@ Private
Definition types.hh:123
@ AssignSub
Definition types.hh:135
@ For
Definition types.hh:91
@ LogicalOr
Definition types.hh:93
@ Return
Definition types.hh:115
@ Do
Definition types.hh:87
@ Static
Definition types.hh:105
@ Enum
Definition types.hh:106
@ Struct
Definition types.hh:117
@ Union
Definition types.hh:109
@ AssignAdd
Definition types.hh:133
@ LogicalAnd
Definition types.hh:81
@ Switch
Definition types.hh:95
@ AssignLShift
Definition types.hh:138
@ Case
Definition types.hh:96
@ Else
Definition types.hh:98
@ AssignRShift
Definition types.hh:139
@ LEqual
Definition types.hh:104
@ Namespace
Definition types.hh:107
@ TemplateOpen
Definition types.hh:130
@ Break
Definition types.hh:83
@ Continue
Definition types.hh:110
@ TemplateClose
Definition types.hh:131
@ Using
Definition types.hh:121
@ Decrement
Definition types.hh:88
@ Increment
Definition types.hh:112
@ Constexpr
Definition types.hh:86
@ AssignDiv
Definition types.hh:137
@ NotEqual
Definition types.hh:89
@ If
Definition types.hh:97
@ Const
Definition types.hh:85
@ Number
Definition types.hh:44
@ Equal
Definition types.hh:90
@ LShift
Definition types.hh:125
@ Inline
Definition types.hh:103
@ Minus
Definition types.hh:69
@ AngleOpen
Definition types.hh:59
@ Word
Definition types.hh:43
@ This
Definition types.hh:120
@ Typename
Definition types.hh:84
@ AssignMul
Definition types.hh:136
@ AngleClose
Definition types.hh:60
@ Public
Definition types.hh:124
@ GEqual
Definition types.hh:94
@ Template
Definition types.hh:119
@ DoubleHash
Definition types.hh:114
@ Class
Definition types.hh:118
const CharClass char_class_table[128]
Definition tables.hh:12
void report(Token tok, std::string_view message)
static const std::array< CharClass, 128 > default_char_class_table
static const std::array< CharClass, 128 > bsl_char_class_table
bool apply_mutations(LexerBase &lexer, const bool all_mutation_ordered=false)
std::vector< IndexRange > scope_ranges
void always_inline exit_scope(int end_tok_id)
void always_inline enter_scope(ScopeType type, size_t start_tok_id)
ScopeStack(size_t predicted_scope_count)
std::vector< ScopeStack::Item > scopes
Token next(int i=1) const
Definition token.hh:33
Token(const lexit::Token &tok)
Definition token.hh:23
Token prev(int i=1) const
Definition token.hh:29
std::string_view str_
Definition lexit.hh:123
uint32_t size() const
Return the amount of token inside the buffer.
Definition lexit.hh:214
TokenType & type()
Definition lexit.hh:358
bool is_invalid() const
Definition lexit.hh:69
std::string_view str() const
Definition lexit.hh:381
int32_t index_
Definition lexit.hh:51
Token(const TokenBuffer *buf, int32_t index)
Definition lexit.hh:337
const TokenType & type() const
Definition lexit.hh:354
bool is_valid() const
Definition lexit.hh:65
Token next(int i=1) const
Definition lexit.hh:372