33 size_t total_length = 0;
38 class TokenHistoryBuffer {
40 std::array<Token, 2> buffer;
44 TokenHistoryBuffer(
Token invalid) : buffer({invalid, invalid}) {}
49 head = (head + 1) % buffer.size();
56 int actual_index = (head + buffer.size() -
index - 1) % buffer.size();
57 return buffer[actual_index];
61 struct FunctionDeclaration {
62 Token type, name, end;
65 struct FunctionGraph {
84 bits::BitVector<> builtin_atoms;
92 : token_history(invalid_tok),
93 return_atom(return_atom),
94 thread_atom(thread_atom),
95 device_atom(device_atom),
97 builtin_atoms(0x10000)
99 for (
auto atom : builtin_atoms) {
101 this->builtin_atoms[atom / 2].set(
true);
116 if (
str.is_empty()) {
120 if (!stream.is_empty()) {
134 total_length +=
str.size();
143 parse_token_impl(set_start_char(tok));
156 parse_token_impl(set_start_char(tok));
161 parse_token_impl(set_start_char(tok, start_char));
170 for (
int i : range) {
172 case TokenType::ParOpen:
178 prev_1 = prev_1.
prev();
182 prev_2 = prev_2.
prev();
184 token_history.push(set_start_char(prev_2, start_char));
185 token_history.push(set_start_char(prev_1, start_char));
189 case TokenType::BracketOpen:
190 stack_depth += (current_fn != 0);
192 case TokenType::BracketClose:
193 stack_depth -= (current_fn != 0);
195 case TokenType::SemiColon:
198 register_function_end(set_start_char(tok.
next(i), start_char));
206 token_history.push(set_start_char(end.
prev(), start_char));
207 token_history.push(set_start_char(end, start_char));
212 if (total_length == 0) {
217 result.reserve(total_length);
219 size_t global_offset = 0;
220 const auto *rem_it = removals.begin();
222 for (
const auto &segment : stream) {
225 while (seg_idx < segment.size()) {
226 size_t current_global_pos = global_offset + seg_idx;
228 if (rem_it == removals.end()) {
229 result.append(segment, seg_idx, std::string::npos);
233 auto [r_start, r_end] = *rem_it;
237 if (current_global_pos < r_start) {
240 size_t len = std::min(
size_t(segment.size()) - seg_idx, r_start - current_global_pos);
248 size_t len = std::min(
size_t(segment.size()) - seg_idx, r_end - current_global_pos);
250 std::string_view chunk(segment.data() + seg_idx,
len);
251 size_t newlines = std::count(chunk.begin(), chunk.end(),
'\n');
252 result.append(newlines,
'\n');
255 if (global_offset + seg_idx >= r_end) {
260 global_offset += segment.size();
268 prune_unused_functions(entry_points);
272 Token set_start_char(
Token tok,
const char *start_offset =
nullptr)
281 switch (tok.type()) {
282 case TokenType::NewLine:
284 case TokenType::ParOpen:
287 case TokenType::BracketOpen:
288 stack_depth += (current_fn != 0);
290 case TokenType::BracketClose:
291 stack_depth -= (current_fn != 0);
293 case TokenType::SemiColon:
296 register_function_end(tok);
301 token_history.push(tok);
304 void process_function()
306 Token name_tok = token_history[0];
307 if (name_tok.type() != TokenType::Word) {
311 Token type_tok = token_history[1];
314 if (type_tok.atom() == thread_atom || type_tok.atom() == device_atom) {
317 if (builtin_atoms[name_tok.atom() / 2]) {
321 if (type_tok.type() == TokenType::Word && type_tok.atom() != return_atom) {
322 register_function_declaration(type_tok, name_tok);
324 else if (current_fn != 0) {
325 register_function_call(name_tok);
331 if (stack_depth == 0 && current_fn != 0) {
332 graph.declarations.last().end = tok;
340 void register_function_declaration(
Token type_tok,
Token name_tok)
343 graph.declarations.last().name.flag != graph.declarations.last().end.flag,
344 "Missing call to register_function_end");
346 graph.declarations.append(FunctionDeclaration{type_tok, name_tok, name_tok});
347 current_fn = name_tok.atom();
352 void register_function_call(
Token name_tok)
354 graph.edges.append_as(current_fn, name_tok.atom());
357 Map<TokenAtom, Vector<TokenAtom>> build_adjacency()
359 Map<TokenAtom, Vector<TokenAtom>> adj;
360 adj.reserve(graph.declarations.size());
361 for (
const auto &[from, to] : graph.edges) {
362 adj.lookup_or_add_default(from).append(to);
367 Set<TokenAtom> compute_used_functions(Span<TokenAtom> &roots)
370 used.reserve(graph.declarations.size());
372 auto adj = build_adjacency();
374 std::vector<TokenAtom> stack;
378 if (used.add(root)) {
379 stack.push_back(root);
382 while (!stack.empty()) {
386 const auto *calls = adj.lookup_ptr(f);
387 if (calls ==
nullptr) {
392 if (used.add(callee)) {
393 stack.push_back(callee);
402 void prune_unused_functions(Span<TokenAtom> entry_points)
404 Set<TokenAtom> used = compute_used_functions(entry_points);
406 for (
auto [type_tok, name_tok, end_tok] : graph.declarations) {
407 if (used.contains(name_tok.atom())) {
411 if (name_tok.flag == end_tok.flag) {
413 BLI_assert(
"Bug in parser, function name not detected");
417 remove_range(type_tok.flag, end_tok.flag + 1);
422 void remove_range(
int start_char,
int end_char)
424 removals.append_as(start_char, end_char);