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 <algorithm>
22 : #include <string_view>
23 :
24 : namespace
25 : {
26 192 : [[nodiscard]] auto is_imported( std::string_view full_type, const proto_files & imports ) -> bool
27 : {
28 192 : return std::any_of( imports.begin( ), imports.end( ),
29 6 : [ full_type ]( const auto & import ) -> bool
30 : {
31 6 : return full_type.size( ) > import.package.name.size( ) &&
32 8 : full_type[ import.package.name.size( ) ] == '.' &&
33 8 : full_type.starts_with( import.package.name );
34 192 : } );
35 : }
36 :
37 1710 : [[nodiscard]] auto is_enum( std::string_view type, const proto_enums & enums ) -> bool
38 : {
39 1710 : return std::any_of( enums.begin( ), enums.end( ), [ type ]( const auto & enum_field ) -> bool
40 4067 : { return type == enum_field.name; } );
41 : }
42 :
43 794 : [[nodiscard]] auto is_sub_message( std::string_view type, const proto_messages & messages ) -> bool
44 : {
45 794 : return std::any_of( messages.begin( ), messages.end( ),
46 1618 : [ type ]( const auto & message ) -> bool { return type == message.name; } );
47 : }
48 :
49 747 : [[nodiscard]] auto is_resolved_sub_message( std::string_view type, const proto_messages & messages )
50 : -> bool
51 : {
52 747 : return std::any_of( messages.begin( ), messages.end( ), [ type ]( const auto & message ) -> bool
53 22693 : { return type == message.name && message.resolved > 0; } );
54 : }
55 :
56 956 : [[nodiscard]] auto is_sub_oneof( std::string_view type, const proto_oneofs & oneofs ) -> bool
57 : {
58 956 : return std::any_of( oneofs.begin( ), oneofs.end( ),
59 962 : [ type ]( const auto & oneof ) -> bool { return type == oneof.name; } );
60 : }
61 :
62 : struct search_state
63 : {
64 : enum resolve_mode
65 : {
66 : //- only check if type is already defined
67 : dependencies_only,
68 : //- for optional fields create an std::unique_ptr< T > type and forward declare T
69 : //- to break cyclic dependency
70 : optional_pointers,
71 : };
72 :
73 : resolve_mode mode = dependencies_only;
74 : size_t resolved_messages = 0;
75 : const proto_files & imports;
76 : const proto_file & file;
77 : };
78 :
79 : /**
80 : * @brief search ctx to hold relation 'message -> parent_message'
81 : * the relation is not stored in proto_message because its not needed until now
82 : * and the messages get sorted (moved) later so the parent pointers will be invalid anyways
83 : * the parent relation is used for type dependency check and for proper order of structs
84 : * definition in the generated *.pb.h header file, because C++ needs proper order of type
85 : * dependencies. The proper order is defined by the value of `.resolved` for every message
86 : *
87 : */
88 : struct search_ctx
89 : {
90 : proto_message & message;
91 : //- parent message (can be null for top level)
92 : search_ctx * p_parent;
93 : search_state & state;
94 : };
95 :
96 : /**
97 : * @brief if the field is self-referencing and can be forward declared
98 : * field label must be LABEL_OPTIONAL or LABEL_PTR or LABEL_REPEATED
99 : *
100 : * @param field filed
101 : * @param ctx search context
102 : * @return true if field can be forward declared
103 : */
104 855 : [[nodiscard]] auto is_self( proto_field & field, const search_ctx & ctx ) -> bool
105 : {
106 855 : if( field.type == proto_field::Type::MESSAGE && field.type_name == ctx.message.name )
107 : {
108 6 : 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 2 : case proto_field::Label::OPTIONAL:
115 2 : field.label = proto_field::Label::PTR;
116 2 : return true;
117 4 : case proto_field::Label::REPEATED:
118 : case proto_field::Label::PTR:
119 4 : return true;
120 : }
121 : }
122 849 : return false;
123 : }
124 :
125 : /**
126 : * @brief if this dependency can be forward declared, do it
127 : * field label must be LABEL_REPEATED or LABEL_PTR
128 : *
129 : * @param field field
130 : * @param ctx search context
131 : * @return true if field can be forward declared
132 : */
133 190 : [[nodiscard]] auto is_forwarded( proto_field & field, search_ctx & ctx ) -> bool
134 : {
135 190 : if( ctx.p_parent == nullptr )
136 0 : return false;
137 :
138 5127 : for( auto & message : ctx.p_parent->message.messages )
139 : {
140 5062 : if( field.type_name == message.name )
141 : {
142 125 : switch( field.label )
143 : {
144 0 : case proto_field::Label::NONE:
145 125 : return false;
146 59 : case proto_field::Label::OPTIONAL:
147 59 : switch( ctx.state.mode )
148 : {
149 58 : case search_state::dependencies_only:
150 58 : return false;
151 :
152 1 : case search_state::optional_pointers:
153 1 : field.label = proto_field::Label::PTR;
154 : //
155 : //- revert the mode to dependencies_only and try again
156 : //- reason is to create as little pointers as possible
157 : //
158 1 : ctx.state.mode = search_state::dependencies_only;
159 : }
160 : [[fallthrough]];
161 : case proto_field::Label::REPEATED:
162 : case proto_field::Label::PTR:
163 67 : ctx.p_parent->message.forwards.insert( message.name );
164 67 : return true;
165 : }
166 : }
167 : }
168 65 : return false;
169 : }
170 :
171 : /**
172 : * @brief if this dependency references the parent message and can be forward declared
173 : * field label must be LABEL_OPTIONAL or LABEL_REPEATED or LABEL_PTR
174 : *
175 : * @param field field
176 : * @param ctx search context
177 : * @return true if field can be forward declared
178 : */
179 579 : [[nodiscard]] auto is_parent( proto_field & field, const search_ctx & ctx ) -> bool
180 : {
181 579 : if( ctx.p_parent == nullptr )
182 0 : return false;
183 :
184 579 : if( field.type_name == ctx.p_parent->message.name )
185 : {
186 1 : switch( field.label )
187 : {
188 0 : case proto_field::Label::NONE:
189 0 : throw_parse_error( ctx.state.file, field.name,
190 0 : "Field '" + std::string( field.name ) +
191 0 : "' cannot reference parent (make it optional)" );
192 1 : case proto_field::Label::OPTIONAL:
193 1 : field.label = proto_field::Label::PTR;
194 1 : return true;
195 0 : case proto_field::Label::REPEATED:
196 : case proto_field::Label::PTR:
197 0 : return true;
198 : }
199 : }
200 578 : return false;
201 : }
202 :
203 1002 : [[nodiscard]] auto is_defined_in_parents( std::string_view type, const search_ctx & ctx ) -> bool
204 : {
205 1002 : if( ctx.p_parent == nullptr )
206 192 : return false;
207 :
208 810 : const auto & message = ctx.p_parent->message;
209 1187 : if( is_enum( type, message.enums ) || is_resolved_sub_message( type, message.messages ) ||
210 377 : is_sub_oneof( type, message.oneofs ) )
211 : {
212 433 : return true;
213 : }
214 :
215 377 : return is_defined_in_parents( type, *ctx.p_parent );
216 : }
217 :
218 539 : [[nodiscard]] auto all_types_are_resolved( const proto_messages & messages ) -> bool
219 : {
220 539 : return std::all_of( messages.begin( ), messages.end( ),
221 1599 : []( const auto & message ) { return message.resolved > 0; } );
222 : }
223 :
224 466 : void mark_message_as_resolved( search_ctx & ctx )
225 : {
226 466 : assert( ctx.message.resolved == 0 );
227 :
228 466 : ctx.message.resolved = ++ctx.state.resolved_messages;
229 466 : }
230 :
231 1873 : [[nodiscard]] auto resolve_message_field( search_ctx & ctx, proto_field & field ) -> bool
232 : {
233 : //- check only the first type (before .) and leave the rest for the C++ compiler to check
234 : //- TODO: check full type name
235 1873 : const auto type_name = field.type_name.substr( 0, field.type_name.find( '.' ) );
236 :
237 2728 : return is_scalar( field.type ) || is_self( field, ctx ) ||
238 849 : is_enum( field.type_name, ctx.message.enums ) ||
239 744 : is_sub_message( type_name, ctx.message.messages ) ||
240 579 : is_sub_oneof( type_name, ctx.message.oneofs ) || is_parent( field, ctx ) ||
241 578 : is_defined_in_parents( type_name, ctx ) ||
242 4601 : is_imported( field.type_name, ctx.state.imports ) || is_forwarded( field, ctx );
243 : }
244 :
245 63 : [[nodiscard]] auto resolve_field( search_ctx & ctx, const proto_field & field ) -> bool
246 : {
247 63 : const auto type_name = field.type_name.substr( 0, field.type_name.find( '.' ) );
248 :
249 114 : return is_scalar( field.type ) || is_enum( field.type_name, ctx.message.enums ) ||
250 50 : is_sub_message( type_name, ctx.message.messages ) ||
251 114 : is_defined_in_parents( type_name, ctx ) ||
252 63 : is_imported( field.type_name, ctx.state.imports );
253 : }
254 :
255 623 : void resolve_message_fields( search_ctx & ctx )
256 : {
257 623 : if( ctx.message.resolved > 0 )
258 0 : return;
259 :
260 2373 : for( auto & field : ctx.message.fields )
261 : {
262 1873 : if( !resolve_message_field( ctx, field ) )
263 123 : return;
264 : }
265 :
266 552 : for( const auto & map : ctx.message.maps )
267 : {
268 52 : if( !resolve_field( ctx, map.value ) )
269 0 : return;
270 : }
271 :
272 504 : for( const auto & oneof : ctx.message.oneofs )
273 : {
274 15 : for( const auto & field : oneof.fields )
275 : {
276 11 : if( !resolve_field( ctx, field ) )
277 0 : return;
278 : }
279 : }
280 :
281 500 : if( all_types_are_resolved( ctx.message.messages ) )
282 466 : mark_message_as_resolved( ctx );
283 : }
284 :
285 1045 : void resolve_message_dependencies( search_ctx & ctx )
286 : {
287 1045 : if( ctx.message.resolved > 0 )
288 422 : return;
289 :
290 1643 : for( auto & message : ctx.message.messages )
291 : {
292 : auto sub_ctx = search_ctx{
293 : .message = message,
294 : .p_parent = &ctx,
295 1020 : .state = ctx.state,
296 1020 : };
297 :
298 1020 : resolve_message_dependencies( sub_ctx );
299 : }
300 623 : resolve_message_fields( ctx );
301 : }
302 :
303 0 : [[noreturn]] void dump_unresolved_message( const proto_messages & messages,
304 : const proto_file & file )
305 : {
306 0 : for( const auto & message : messages )
307 : {
308 0 : if( message.resolved == 0 )
309 : {
310 0 : throw_parse_error( file, message.name, "type dependency can't be resolved" );
311 : }
312 : }
313 0 : throw_parse_error( file, file.content, "type dependency can't be resolved" );
314 : }
315 :
316 466 : void sort_messages( proto_messages & messages )
317 : {
318 466 : std::sort( messages.begin( ), messages.end( ),
319 2541 : []( const auto & a, const auto & b ) { return a.resolved < b.resolved; } );
320 :
321 918 : for( auto & message : messages )
322 : {
323 452 : sort_messages( message.messages );
324 : }
325 466 : }
326 :
327 : }// namespace
328 :
329 14 : void resolve_messages_order( proto_file & file )
330 : {
331 14 : auto state = search_state{
332 : .mode = search_state::dependencies_only,
333 : .resolved_messages = 0,
334 14 : .imports = file.file_imports,
335 : .file = file,
336 14 : };
337 :
338 39 : while( !all_types_are_resolved( file.package.messages ) )
339 : {
340 25 : const auto resolved_messages = state.resolved_messages;
341 :
342 25 : auto top_level_ctx = search_ctx{
343 25 : .message = file.package,
344 : .p_parent = nullptr,
345 : .state = state,
346 25 : };
347 :
348 25 : resolve_message_dependencies( top_level_ctx );
349 :
350 25 : if( resolved_messages == state.resolved_messages )
351 : {
352 1 : if( state.mode == search_state::dependencies_only )
353 : {
354 : //- no messages were resolved using only dependencies?
355 : //- try to break cyclic dependency by using forward pointers declaration
356 1 : state.mode = search_state::optional_pointers;
357 1 : continue;
358 : }
359 :
360 0 : dump_unresolved_message( file.package.messages, file );
361 : }
362 : }
363 :
364 14 : sort_messages( file.package.messages );
365 14 : }
|
