codegen_c_sorter.c (10873B)
1 #include "codegen_c.h" 2 3 #include "flatcc/flatcc_types.h" 4 5 /* -DFLATCC_PORTABLE may help if inttypes.h is missing. */ 6 #ifndef PRId64 7 #include <inttypes.h> 8 #endif 9 10 /* Used internally to identify sortable objects. */ 11 enum { 12 /* object contains at least one direct vector that needs sorting */ 13 direct_sortable = 1, 14 /* object contains at least one indirect vector that needs sorting */ 15 indirect_sortable = 1, 16 /* object contains at least one direct or indirect vector that needs sorting */ 17 sortable = 3, 18 }; 19 20 static int gen_union_sorter(fb_output_t *out, fb_compound_type_t *ct) 21 { 22 fb_symbol_t *sym; 23 fb_member_t *member; 24 fb_scoped_name_t snt, snref; 25 int n; 26 const char *s; 27 28 fb_clear(snt); 29 fb_clear(snref); 30 fb_compound_name(ct, &snt); 31 32 fprintf(out->fp, 33 "static void %s_sort(%s_mutable_union_t u)\n{\n switch (u.type) {\n", 34 snt.text, snt.text); 35 for (sym = ct->members; sym; sym = sym->link) { 36 member = (fb_member_t *)sym; 37 symbol_name(sym, &n, &s); 38 switch (member->type.type) { 39 case vt_compound_type_ref: 40 fb_compound_name(member->type.ct, &snref); 41 switch (member->type.ct->symbol.kind) { 42 case fb_is_table: 43 if (member->type.ct->export_index & sortable) { 44 fprintf(out->fp, 45 " case %s_%.*s: %s_sort(u.value); break;\n", 46 snt.text, n, s, snref.text); 47 } 48 break; 49 default: 50 break; 51 } 52 break; 53 default: 54 break; 55 } 56 } 57 fprintf(out->fp, 58 " default: break;\n }\n}\n\n"); 59 return 0; 60 } 61 62 static int gen_table_sorter(fb_output_t *out, fb_compound_type_t *ct) 63 { 64 fb_symbol_t *sym; 65 fb_member_t *member; 66 fb_scoped_name_t snt, snref; 67 const char *tname_prefix; 68 const char *nsc = out->nsc; 69 const char *s; 70 int n; 71 72 fb_clear(snt); 73 fb_clear(snref); 74 fb_compound_name(ct, &snt); 75 76 fprintf(out->fp, 77 "static void %s_sort(%s_mutable_table_t t)\n{\n", 78 snt.text, snt.text); 79 80 fprintf(out->fp, " if (!t) return;\n"); 81 /* sort all children before sorting current table */ 82 if (ct->export_index & indirect_sortable) 83 for (sym = ct->members; sym; sym = sym->link) { 84 member = (fb_member_t *)sym; 85 if (member->metadata_flags & fb_f_deprecated) { 86 continue; 87 } 88 symbol_name(sym, &n, &s); 89 switch (member->type.type) { 90 case vt_compound_type_ref: 91 fb_compound_name(member->type.ct, &snref); 92 switch (member->type.ct->symbol.kind) { 93 case fb_is_table: 94 if (!(member->type.ct->export_index & sortable)) continue; 95 fprintf(out->fp, 96 " __%ssort_table_field(%s, %.*s, %s, t);\n", 97 nsc, snt.text, n, s, snref.text); 98 break; 99 case fb_is_union: 100 if (!(member->type.ct->export_index & sortable)) continue; 101 fprintf(out->fp, 102 " __%ssort_union_field(%s, %.*s, %s, t);\n", 103 nsc, snt.text, n, s, snref.text); 104 break; 105 default: 106 continue; 107 } 108 break; 109 case vt_vector_compound_type_ref: 110 fb_compound_name(member->type.ct, &snref); 111 switch (member->type.ct->symbol.kind) { 112 case fb_is_table: 113 if (!(member->type.ct->export_index & sortable)) continue; 114 fprintf(out->fp, 115 " __%ssort_table_vector_field_elements(%s, %.*s, %s, t);\n", 116 nsc, snt.text, n, s, snref.text); 117 break; 118 case fb_is_union: 119 /* Although union vectors cannot be sorted, their content can be. */ 120 if (!(member->type.ct->export_index & sortable)) continue; 121 fprintf(out->fp, 122 " __%ssort_union_vector_field_elements(%s, %.*s, %s, t);\n", 123 nsc, snt.text, n, s, snref.text); 124 break; 125 default: 126 continue; 127 } 128 break; 129 } 130 } 131 if (ct->export_index & direct_sortable) 132 for (sym = ct->members; sym; sym = sym->link) { 133 member = (fb_member_t *)sym; 134 symbol_name(sym, &n, &s); 135 if (!(member->metadata_flags & fb_f_sorted)) continue; 136 switch (member->type.type) { 137 case vt_vector_type: 138 tname_prefix = scalar_type_prefix(member->type.st); 139 fprintf(out->fp, 140 " __%ssort_vector_field(%s, %.*s, %s%s, t)\n", 141 nsc, snt.text, n, s, nsc, tname_prefix); 142 break; 143 case vt_vector_string_type: 144 fprintf(out->fp, 145 " __%ssort_vector_field(%s, %.*s, %s%s, t)\n", 146 nsc, snt.text, n, s, nsc, "string"); 147 break; 148 case vt_vector_compound_type_ref: 149 if (!member->type.ct->primary_key) { 150 gen_panic(out, "internal error: unexpected type during code generation"); 151 return -1; 152 } 153 fb_compound_name(member->type.ct, &snref); 154 switch (member->type.ct->symbol.kind) { 155 case fb_is_table: 156 case fb_is_struct: 157 fprintf(out->fp, 158 " __%ssort_vector_field(%s, %.*s, %s, t)\n", 159 nsc, snt.text, n, s, snref.text); 160 break; 161 /* Union vectors cannot be sorted. */ 162 default: 163 break; 164 } 165 break; 166 } 167 } 168 fprintf(out->fp, "}\n\n"); 169 return 0; 170 } 171 172 static int gen_table_sorter_prototypes(fb_output_t *out) 173 { 174 fb_symbol_t *sym; 175 fb_scoped_name_t snt; 176 fb_compound_type_t *ct; 177 178 fb_clear(snt); 179 180 for (sym = out->S->symbols; sym; sym = sym->link) { 181 switch (sym->kind) { 182 case fb_is_table: 183 ct = (fb_compound_type_t *)sym; 184 if (ct->export_index & sortable) { 185 fb_compound_name(ct, &snt); 186 fprintf(out->fp, 187 "static void %s_sort(%s_mutable_table_t t);\n", 188 snt.text, snt.text); 189 } 190 } 191 } 192 fprintf(out->fp, "\n"); 193 return 0; 194 } 195 196 static int gen_union_sorters(fb_output_t *out) 197 { 198 fb_symbol_t *sym; 199 fb_compound_type_t *ct; 200 201 for (sym = out->S->symbols; sym; sym = sym->link) { 202 switch (sym->kind) { 203 case fb_is_union: 204 ct = (fb_compound_type_t *)sym; 205 if (ct->export_index & sortable) { 206 gen_union_sorter(out, ct); 207 } 208 break; 209 default: 210 break; 211 } 212 } 213 return 0; 214 } 215 216 static int gen_table_sorters(fb_output_t *out) 217 { 218 fb_symbol_t *sym; 219 fb_compound_type_t *ct; 220 221 for (sym = out->S->symbols; sym; sym = sym->link) { 222 switch (sym->kind) { 223 case fb_is_table: 224 ct = (fb_compound_type_t *)sym; 225 if (ct->export_index & sortable) { 226 gen_table_sorter(out, ct); 227 } 228 break; 229 default: 230 break; 231 } 232 } 233 return 0; 234 } 235 236 /* 237 * Return 1 if the table or union is known to be sortable, 238 * and 0 if that information is not available. 239 * 240 * Note that if neither a table nor its direct children have 241 * sortable vectors, the table might still be sortable via a 242 * union member or via deeper nested tables. By iterating 243 * repeatedly over all objects, the indirect_sortable 244 * property eventually propagetes to all affected objects. 245 * At that point no object will change its return value 246 * on repeated calls. 247 */ 248 static int mark_member_sortable(fb_compound_type_t *ct) 249 { 250 fb_symbol_t *sym; 251 fb_member_t *member; 252 253 for (sym = ct->members; sym; sym = sym->link) { 254 member = (fb_member_t *)sym; 255 if (member->metadata_flags & fb_f_deprecated) { 256 continue; 257 } 258 if (member->metadata_flags & fb_f_sorted) { 259 ct->export_index |= direct_sortable; 260 } 261 switch (member->type.type) { 262 case vt_compound_type_ref: 263 switch (member->type.ct->symbol.kind) { 264 case fb_is_table: 265 case fb_is_union: 266 break; 267 default: 268 continue; 269 } 270 break; 271 case vt_vector_compound_type_ref: 272 switch (member->type.ct->symbol.kind) { 273 case fb_is_table: 274 case fb_is_union: 275 break; 276 default: 277 continue; 278 } 279 break; 280 default: 281 continue; 282 } 283 if (member->type.ct->export_index & (sortable | indirect_sortable)) { 284 ct->export_index |= indirect_sortable; 285 } 286 } 287 return !!(ct->export_index & sortable); 288 } 289 290 static void init_sortable(fb_compound_type_t *ct) 291 { 292 fb_symbol_t *sym; 293 fb_member_t *member; 294 295 for (sym = ct->members; sym; sym = sym->link) { 296 member = (fb_member_t *)sym; 297 switch (member->type.type) { 298 case vt_compound_type_ref: 299 case vt_vector_compound_type_ref: 300 member->type.ct->export_index = 0; 301 break; 302 default: 303 continue; 304 } 305 } 306 ct->export_index = 0; 307 } 308 309 /* 310 * Use fix-point iteration to implement a breadth first 311 * search for tables and unions that can be sorted. The 312 * problem is slightly tricky due to self-referential types: 313 * a graph colored depth-first search might terminate before 314 * it is known whether any non-direct descendants are 315 * sortable. 316 */ 317 static int mark_sortable(fb_output_t *out) 318 { 319 fb_symbol_t *sym; 320 int old_count = -1, count = 0; 321 322 /* Initialize state kept in the custom export_index symbol table field. */ 323 for (sym = out->S->symbols; sym; sym = sym->link) { 324 switch (sym->kind) { 325 case fb_is_table: 326 case fb_is_union: 327 init_sortable((fb_compound_type_t *)sym); 328 break; 329 } 330 } 331 /* Perform fix-point iteration search. */ 332 while (old_count != count) { 333 old_count = count; 334 count = 0; 335 for (sym = out->S->symbols; sym; sym = sym->link) { 336 switch (sym->kind) { 337 case fb_is_table: 338 case fb_is_union: 339 count += mark_member_sortable((fb_compound_type_t *)sym); 340 break; 341 } 342 } 343 } 344 return 0; 345 } 346 347 /* To be generated towards the end of _reader.h when sort option is active. */ 348 int fb_gen_c_sorter(fb_output_t *out) 349 { 350 mark_sortable(out); 351 gen_table_sorter_prototypes(out); 352 gen_union_sorters(out); 353 gen_table_sorters(out); 354 return 0; 355 }