Line data Source code
1 : /***************************************************************************\
2 : * Name : ast render *
3 : * Description : resolve types in ast tree *
4 : * Author : antonin.kriz@gmail.com *
5 : * ------------------------------------------------------------------------- *
6 : * This is free software; you can redistribute it and/or modify it under the *
7 : * terms of the MIT license. A copy of the license can be found in the file *
8 : * "LICENSE" at the root of this distribution. *
9 : \***************************************************************************/
10 :
11 : #include "ast-types.h"
12 : #include "dumper/header.h"
13 : #include "proto-field.h"
14 : #include "proto-file.h"
15 : #include "proto-message.h"
16 : #include <algorithm>
17 : #include <array>
18 : #include <cerrno>
19 : #include <cstddef>
20 : #include <parser/char_stream.h>
21 : #include <string_view>
22 :
23 : namespace
24 : {
25 :
26 : struct search_state
27 : {
28 : enum resolve_mode
29 : {
30 : //- only check if type is already defined
31 : dependencies_only,
32 : //- for optional fields create an std::unique_ptr< T > type and forward declare T
33 : //- to break cyclic dependency
34 : optional_pointers,
35 : };
36 :
37 : resolve_mode mode = dependencies_only;
38 : size_t resolved_messages = 0;
39 : const proto_files & imports;
40 : const proto_file & file;
41 : };
42 :
43 : /**
44 : * @brief search ctx to hold relation 'message -> parent_message'
45 : * the relation is not stored in proto_message because its not needed until now
46 : * and the messages get sorted (moved) later so the parent pointers will be invalid anyways
47 : * the parent relation is used for type dependency check and for proper order of structs
48 : * definition in the generated *.pb.h header file, because C++ needs proper order of type
49 : * dependencies. The proper order is defined by the value of `.resolved` for every message
50 : *
51 : */
52 : struct search_ctx
53 : {
54 : proto_message & message;
55 : //- parent message (can be null for top level)
56 : search_ctx * p_parent;
57 : search_state & state;
58 : };
59 :
60 : [[nodiscard]]
61 3581 : auto type_parts( std::string_view type_name ) -> size_t
62 : {
63 3581 : return size_t( std::count( type_name.cbegin( ), type_name.cend( ), '.' ) );
64 : }
65 :
66 : [[nodiscard]]
67 3579 : auto is_last_part( const proto_field & field, size_t type_part ) -> bool
68 : {
69 3579 : return type_part == type_parts( field.type_name );
70 : }
71 :
72 : [[nodiscard]]
73 9410 : auto get_type_part( const proto_field & field, size_t type_part ) -> std::string_view
74 : {
75 9410 : auto type_name = field.type_name;
76 9501 : for( ; type_part > 0; type_part-- )
77 : {
78 91 : const auto dot_index = type_name.find( '.' );
79 91 : if( dot_index == type_name.npos )
80 0 : return { };
81 :
82 91 : type_name.remove_prefix( dot_index + 1 );
83 : }
84 :
85 9410 : return type_name.substr( 0, type_name.find( '.' ) );
86 : }
87 :
88 : /**
89 : * @brief if the field is self-referencing and can be forward declared
90 : * field label must be LABEL_OPTIONAL or LABEL_PTR or LABEL_REPEATED
91 : *
92 : * @param field filed
93 : * @param ctx search context
94 : * @return true if field can be forward declared
95 : */
96 : [[nodiscard]]
97 1447 : auto is_self( const search_ctx & ctx, proto_field & field, size_t type_part ) -> bool
98 : {
99 1447 : if( field.type != proto_field::Type::MESSAGE )
100 232 : return false;
101 :
102 1215 : if( !is_last_part( field, type_part ) )
103 101 : return false;
104 :
105 1114 : if( get_type_part( field, type_part ) != ctx.message.name )
106 1107 : return false;
107 :
108 7 : switch( field.label )
109 : {
110 0 : case proto_field::Label::NONE:
111 0 : throw_parse_error( ctx.state.file, field.name,
112 0 : "Field '" + std::string( field.name ) +
113 0 : "' cannot be self-referencing (make it optional)" );
114 3 : case proto_field::Label::OPTIONAL:
115 3 : field.label = proto_field::Label::PTR;
116 3 : return true;
117 4 : case proto_field::Label::REPEATED:
118 : case proto_field::Label::PTR:
119 4 : return true;
120 : }
121 :
122 0 : return false;
123 : }
124 :
125 : [[nodiscard]]
126 105 : auto is_self( const search_ctx & ctx, const proto_field & field, size_t type_part ) -> bool
127 : {
128 105 : if( field.type != proto_field::Type::MESSAGE )
129 57 : return false;
130 :
131 48 : if( !is_last_part( field, type_part ) )
132 7 : return false;
133 :
134 41 : if( get_type_part( field, type_part ) != ctx.message.name )
135 41 : return false;
136 :
137 0 : switch( field.label )
138 : {
139 0 : case proto_field::Label::REPEATED:
140 : case proto_field::Label::PTR:
141 0 : return true;
142 0 : default:
143 0 : return false;
144 : }
145 : }
146 :
147 : /**
148 : * @brief if this dependency can be forward declared, do it
149 : * field label must be LABEL_REPEATED or LABEL_PTR
150 : *
151 : * @param ctx search context
152 : * @param field field
153 : * @return true if field can be forward declared
154 : */
155 : [[nodiscard]]
156 440 : auto is_forwarded( search_ctx & ctx, proto_field & field, size_t type_part ) -> bool
157 : {
158 440 : if( ctx.p_parent == nullptr )
159 190 : return false;
160 :
161 250 : if( !is_last_part( field, type_part ) )
162 37 : return false;
163 :
164 5476 : for( const auto & message : ctx.p_parent->message.messages )
165 : {
166 5414 : if( get_type_part( field, type_part ) != message.name )
167 5263 : continue;
168 :
169 151 : switch( field.label )
170 : {
171 15 : case proto_field::Label::NONE:
172 151 : return false;
173 67 : case proto_field::Label::OPTIONAL:
174 67 : switch( ctx.state.mode )
175 : {
176 66 : case search_state::dependencies_only:
177 66 : return false;
178 :
179 1 : case search_state::optional_pointers:
180 1 : field.label = proto_field::Label::PTR;
181 : //
182 : //- revert the mode to dependencies_only and try again
183 : //- reason is to create as little pointers as possible
184 : //
185 1 : ctx.state.mode = search_state::dependencies_only;
186 : }
187 : [[fallthrough]];
188 : case proto_field::Label::REPEATED:
189 : case proto_field::Label::PTR:
190 70 : ctx.p_parent->message.forwards.insert( message.name );
191 70 : return true;
192 : }
193 : }
194 62 : return false;
195 : }
196 :
197 : [[nodiscard]]
198 1414 : auto get_sub_message( const proto_message & message, const proto_field & field, size_t type_part )
199 : -> const proto_message *
200 : {
201 1414 : const auto type_name = get_type_part( field, type_part );
202 : const auto index =
203 1414 : std::find_if( message.messages.begin( ), message.messages.end( ),
204 21790 : [ type_name ]( const auto & sub_message ) -> bool
205 21790 : { return type_name == sub_message.name && sub_message.resolved > 0; } );
206 1414 : return ( index != message.messages.end( ) ) ? &*index : nullptr;
207 : }
208 :
209 : [[nodiscard]]
210 521 : auto all_types_are_resolved( const proto_messages & messages ) -> bool
211 : {
212 521 : return std::all_of( messages.begin( ), messages.end( ),
213 1473 : []( const auto & message ) { return message.resolved > 0; } );
214 : }
215 :
216 466 : void mark_message_as_resolved( search_ctx & ctx )
217 : {
218 466 : assert( ctx.message.resolved == 0 );
219 :
220 466 : ctx.message.resolved = ++ctx.state.resolved_messages;
221 466 : }
222 :
223 : [[nodiscard]]
224 1592 : auto is_enum( const proto_message & message, const proto_field & field, size_t type_part ) -> bool
225 : {
226 1592 : if( !is_last_part( field, type_part ) )
227 165 : return false;
228 :
229 1427 : const auto type_name = get_type_part( field, type_part );
230 :
231 1427 : return std::any_of( message.enums.begin( ), message.enums.end( ),
232 1923 : [ type_name ]( const auto & enum_ ) -> bool
233 3350 : { return type_name == enum_.name; } );
234 : }
235 :
236 : [[nodiscard]]
237 1592 : auto resolve_from_message( const proto_message & message, const proto_field & field,
238 : size_t type_part ) -> bool
239 : {
240 1592 : if( const auto type = is_enum( message, field, type_part ); type )
241 178 : return type;
242 :
243 1414 : if( const auto * sub_message = get_sub_message( message, field, type_part ); sub_message )
244 : {
245 474 : if( is_last_part( field, type_part ) )
246 429 : return true;
247 :
248 45 : return resolve_from_message( *sub_message, field, type_part + 1 );
249 : }
250 :
251 940 : return false;
252 : }
253 :
254 : [[nodiscard]]
255 : auto resolve_field( search_ctx & ctx, proto_field & field, size_t type_part ) -> bool;
256 :
257 : [[nodiscard]]
258 : auto resolve_field( const search_ctx & ctx, const proto_field & field, size_t type_part ) -> bool;
259 :
260 : [[nodiscard]]
261 886 : auto resolve_from_parent( const search_ctx & self, proto_field & field, size_t type_part ) -> bool
262 : {
263 886 : if( !self.p_parent || type_part > 0 )
264 192 : return false;
265 :
266 694 : return resolve_field( *self.p_parent, field, type_part );
267 : }
268 :
269 : [[nodiscard]]
270 54 : auto resolve_from_parent( const search_ctx & self, const proto_field & field, size_t type_part )
271 : -> bool
272 : {
273 54 : if( !self.p_parent || type_part > 0 )
274 0 : return false;
275 :
276 54 : return resolve_field( *self.p_parent, field, type_part );
277 : }
278 :
279 : [[nodiscard]]
280 10 : auto resolve_from_import( const proto_file & import, const proto_field & field ) -> bool
281 : {
282 10 : if( import.package.name.empty( ) )
283 : {
284 0 : return resolve_from_message( import.package, field, 0 );
285 : }
286 :
287 10 : if( field.type_name.size( ) > import.package.name.size( ) &&
288 12 : field.type_name[ import.package.name.size( ) ] == '.' &&
289 2 : field.type_name.starts_with( import.package.name ) )
290 : {
291 2 : return resolve_from_message( import.package, field, type_parts( import.package.name ) + 1 );
292 : }
293 :
294 8 : return false;
295 : }
296 :
297 : [[nodiscard]]
298 442 : auto resolve_from_imports( const search_ctx & self, const proto_field & field, size_t type_part )
299 : -> bool
300 : {
301 442 : if( type_part > 0 )
302 0 : return false;
303 :
304 450 : for( const auto & import : self.state.imports )
305 : {
306 10 : if( resolve_from_import( import, field ) )
307 2 : return true;
308 : }
309 :
310 440 : return false;
311 : }
312 :
313 : [[nodiscard]]
314 117 : auto resolve_field( const search_ctx & ctx, const proto_field & field, size_t type_part ) -> bool
315 : {
316 117 : if( is_scalar( field.type ) || is_self( ctx, field, type_part ) )
317 12 : return true;
318 :
319 105 : if( resolve_from_message( ctx.message, field, type_part ) )
320 51 : return true;
321 :
322 54 : if( resolve_from_parent( ctx, field, type_part ) )
323 54 : return true;
324 :
325 0 : return resolve_from_imports( ctx, field, type_part );
326 : }
327 :
328 : [[nodiscard]]
329 2452 : auto resolve_field( search_ctx & ctx, proto_field & field, size_t type_part ) -> bool
330 : {
331 2452 : if( is_scalar( field.type ) || is_self( ctx, field, type_part ) )
332 1012 : return true;
333 :
334 1440 : if( resolve_from_message( ctx.message, field, type_part ) )
335 554 : return true;
336 :
337 886 : if( resolve_from_parent( ctx, field, type_part ) )
338 444 : return true;
339 :
340 442 : if( resolve_from_imports( ctx, field, type_part ) )
341 2 : return true;
342 :
343 440 : return is_forwarded( ctx, field, type_part );
344 : }
345 :
346 603 : void resolve_message_fields( search_ctx & ctx )
347 : {
348 603 : if( ctx.message.resolved > 0 )
349 0 : return;
350 :
351 2241 : for( auto & field : ctx.message.fields )
352 : {
353 1758 : if( !resolve_field( ctx, field, 0 ) )
354 120 : return;
355 : }
356 :
357 535 : for( const auto & map : ctx.message.maps )
358 : {
359 52 : if( !resolve_field( ctx, map.value, 0 ) )
360 0 : return;
361 : }
362 :
363 487 : for( const auto & oneof : ctx.message.oneofs )
364 : {
365 15 : for( const auto & field : oneof.fields )
366 : {
367 11 : if( !resolve_field( ctx, field, 0 ) )
368 0 : return;
369 : }
370 : }
371 :
372 483 : if( all_types_are_resolved( ctx.message.messages ) )
373 466 : mark_message_as_resolved( ctx );
374 : }
375 :
376 931 : void resolve_message_dependencies( search_ctx & ctx )
377 : {
378 931 : if( ctx.message.resolved > 0 )
379 328 : return;
380 :
381 1510 : for( auto & message : ctx.message.messages )
382 : {
383 : auto sub_ctx = search_ctx{
384 : .message = message,
385 : .p_parent = &ctx,
386 907 : .state = ctx.state,
387 907 : };
388 :
389 907 : resolve_message_dependencies( sub_ctx );
390 : }
391 603 : resolve_message_fields( ctx );
392 : }
393 :
394 0 : [[noreturn]] void dump_unresolved_message( const proto_messages & messages,
395 : const proto_file & file )
396 : {
397 0 : for( const auto & message : messages )
398 : {
399 0 : if( message.resolved == 0 )
400 : {
401 0 : throw_parse_error( file, message.name, "type dependency can't be resolved" );
402 : }
403 : }
404 0 : throw_parse_error( file, file.content, "type dependency can't be resolved" );
405 : }
406 :
407 466 : void sort_messages( proto_messages & messages )
408 : {
409 466 : std::sort( messages.begin( ), messages.end( ),
410 2513 : []( const auto & a, const auto & b ) { return a.resolved < b.resolved; } );
411 :
412 918 : for( auto & message : messages )
413 : {
414 452 : sort_messages( message.messages );
415 : }
416 466 : }
417 :
418 : }// namespace
419 :
420 14 : void resolve_messages_order( proto_file & file )
421 : {
422 14 : auto state = search_state{
423 : .mode = search_state::dependencies_only,
424 : .resolved_messages = 0,
425 14 : .imports = file.file_imports,
426 : .file = file,
427 14 : };
428 :
429 38 : while( !all_types_are_resolved( file.package.messages ) )
430 : {
431 24 : const auto resolved_messages = state.resolved_messages;
432 :
433 24 : auto top_level_ctx = search_ctx{
434 24 : .message = file.package,
435 : .p_parent = nullptr,
436 : .state = state,
437 24 : };
438 :
439 24 : resolve_message_dependencies( top_level_ctx );
440 :
441 24 : if( resolved_messages == state.resolved_messages )
442 : {
443 1 : if( state.mode == search_state::dependencies_only )
444 : {
445 : //- no messages were resolved using only dependencies?
446 : //- try to break cyclic dependency by using forward pointers declaration
447 1 : state.mode = search_state::optional_pointers;
448 1 : continue;
449 : }
450 :
451 0 : dump_unresolved_message( file.package.messages, file );
452 : }
453 : }
454 :
455 14 : sort_messages( file.package.messages );
456 14 : }
|
