third_party/upb/upb/def.c

   1 /*
   2  * Copyright (c) 2009-2021, Google LLC
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are met:
   7  *     * Redistributions of source code must retain the above copyright
   8  *       notice, this list of conditions and the following disclaimer.
   9  *     * Redistributions in binary form must reproduce the above copyright
  10  *       notice, this list of conditions and the following disclaimer in the
  11  *       documentation and/or other materials provided with the distribution.
  12  *     * Neither the name of Google LLC nor the
  13  *       names of its contributors may be used to endorse or promote products
  14  *       derived from this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19  * DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY
  20  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include "upb/def.h"
  29
  30 #include <ctype.h>
  31 #include <errno.h>
  32 #include <setjmp.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 #include "google/protobuf/descriptor.upb.h"
  37 #include "upb/reflection.h"
  38
  39 /* Must be last. */
  40 #include "upb/port_def.inc"
  41
  42 typedef struct {
  43   size_t len;
  44   char str[1];  /* Null-terminated string data follows. */
  45 } str_t;
  46
  47 struct upb_fielddef {
  48   const upb_filedef *file;
  49   const upb_msgdef *msgdef;
  50   const char *full_name;
  51   const char *json_name;
  52   union {
  53     int64_t sint;
  54     uint64_t uint;
  55     double dbl;
  56     float flt;
  57     bool boolean;
  58     str_t *str;
  59   } defaultval;
  60   const upb_oneofdef *oneof;
  61   union {
  62     const upb_msgdef *msgdef;
  63     const upb_enumdef *enumdef;
  64     const google_protobuf_FieldDescriptorProto *unresolved;
  65   } sub;
  66   uint32_t number_;
  67   uint16_t index_;
  68   uint16_t layout_index;
  69   bool is_extension_;
  70   bool lazy_;
  71   bool packed_;
  72   bool proto3_optional_;
  73   upb_descriptortype_t type_;
  74   upb_label_t label_;
  75 };
  76
  77 struct upb_msgdef {
  78   const upb_msglayout *layout;
  79   const upb_filedef *file;
  80   const char *full_name;
  81
  82   /* Tables for looking up fields by number and name. */
  83   upb_inttable itof;
  84   upb_strtable ntof;
  85
  86   const upb_fielddef *fields;
  87   const upb_oneofdef *oneofs;
  88   int field_count;
  89   int oneof_count;
  90   int real_oneof_count;
  91
  92   /* Is this a map-entry message? */
  93   bool map_entry;
  94   upb_wellknowntype_t well_known_type;
  95
  96   /* TODO(haberman): proper extension ranges (there can be multiple). */
  97 };
  98
  99 struct upb_enumdef {
 100   const upb_filedef *file;
 101   const char *full_name;
 102   upb_strtable ntoi;
 103   upb_inttable iton;
 104   int32_t defaultval;
 105 };
 106
 107 struct upb_oneofdef {
 108   const upb_msgdef *parent;
 109   const char *full_name;
 110   int field_count;
 111   bool synthetic;
 112   const upb_fielddef **fields;
 113   upb_strtable ntof;
 114   upb_inttable itof;
 115 };
 116
 117 struct upb_filedef {
 118   const char *name;
 119   const char *package;
 120   const char *phpprefix;
 121   const char *phpnamespace;
 122
 123   const upb_filedef **deps;
 124   const upb_msgdef *msgs;
 125   const upb_enumdef *enums;
 126   const upb_fielddef *exts;
 127   const upb_symtab *symtab;
 128
 129   int dep_count;
 130   int msg_count;
 131   int enum_count;
 132   int ext_count;
 133   upb_syntax_t syntax;
 134 };
 135
 136 struct upb_symtab {
 137   upb_arena *arena;
 138   upb_strtable syms;  /* full_name -> packed def ptr */
 139   upb_strtable files;  /* file_name -> upb_filedef* */
 140   size_t bytes_loaded;
 141 };
 142
 143 /* Inside a symtab we store tagged pointers to specific def types. */
 144 typedef enum {
 145   UPB_DEFTYPE_FIELD = 0,
 146
 147   /* Only inside symtab table. */
 148   UPB_DEFTYPE_MSG = 1,
 149   UPB_DEFTYPE_ENUM = 2,
 150
 151   /* Only inside message table. */
 152   UPB_DEFTYPE_ONEOF = 1,
 153   UPB_DEFTYPE_FIELD_JSONNAME = 2
 154 } upb_deftype_t;
 155
 156 static const void *unpack_def(upb_value v, upb_deftype_t type) {
 157   uintptr_t num = (uintptr_t)upb_value_getconstptr(v);
 158   return (num & 3) == type ? (const void*)(num & ~3) : NULL;
 159 }
 160
 161 static upb_value pack_def(const void *ptr, upb_deftype_t type) {
 162   uintptr_t num = (uintptr_t)ptr | type;
 163   return upb_value_constptr((const void*)num);
 164 }
 165
 166 /* isalpha() etc. from <ctype.h> are locale-dependent, which we don't want. */
 167 static bool upb_isbetween(char c, char low, char high) {
 168   return c >= low && c <= high;
 169 }
 170
 171 static bool upb_isletter(char c) {
 172   return upb_isbetween(c, 'A', 'Z') || upb_isbetween(c, 'a', 'z') || c == '_';
 173 }
 174
 175 static bool upb_isalphanum(char c) {
 176   return upb_isletter(c) || upb_isbetween(c, '0', '9');
 177 }
 178
 179 static const char *shortdefname(const char *fullname) {
 180   const char *p;
 181
 182   if (fullname == NULL) {
 183     return NULL;
 184   } else if ((p = strrchr(fullname, '.')) == NULL) {
 185     /* No '.' in the name, return the full string. */
 186     return fullname;
 187   } else {
 188     /* Return one past the last '.'. */
 189     return p + 1;
 190   }
 191 }
 192
 193 /* All submessage fields are lower than all other fields.
 194  * Secondly, fields are increasing in order. */
 195 uint32_t field_rank(const upb_fielddef *f) {
 196   uint32_t ret = upb_fielddef_number(f);
 197   const uint32_t high_bit = 1 << 30;
 198   UPB_ASSERT(ret < high_bit);
 199   if (!upb_fielddef_issubmsg(f))
 200     ret |= high_bit;
 201   return ret;
 202 }
 203
 204 int cmp_fields(const void *p1, const void *p2) {
 205   const upb_fielddef *f1 = *(upb_fielddef*const*)p1;
 206   const upb_fielddef *f2 = *(upb_fielddef*const*)p2;
 207   return field_rank(f1) - field_rank(f2);
 208 }
 209
 210 static void upb_status_setoom(upb_status *status) {
 211   upb_status_seterrmsg(status, "out of memory");
 212 }
 213
 214 static void assign_msg_wellknowntype(upb_msgdef *m) {
 215   const char *name = upb_msgdef_fullname(m);
 216   if (name == NULL) {
 217     m->well_known_type = UPB_WELLKNOWN_UNSPECIFIED;
 218     return;
 219   }
 220   if (!strcmp(name, "google.protobuf.Any")) {
 221     m->well_known_type = UPB_WELLKNOWN_ANY;
 222   } else if (!strcmp(name, "google.protobuf.FieldMask")) {
 223     m->well_known_type = UPB_WELLKNOWN_FIELDMASK;
 224   } else if (!strcmp(name, "google.protobuf.Duration")) {
 225     m->well_known_type = UPB_WELLKNOWN_DURATION;
 226   } else if (!strcmp(name, "google.protobuf.Timestamp")) {
 227     m->well_known_type = UPB_WELLKNOWN_TIMESTAMP;
 228   } else if (!strcmp(name, "google.protobuf.DoubleValue")) {
 229     m->well_known_type = UPB_WELLKNOWN_DOUBLEVALUE;
 230   } else if (!strcmp(name, "google.protobuf.FloatValue")) {
 231     m->well_known_type = UPB_WELLKNOWN_FLOATVALUE;
 232   } else if (!strcmp(name, "google.protobuf.Int64Value")) {
 233     m->well_known_type = UPB_WELLKNOWN_INT64VALUE;
 234   } else if (!strcmp(name, "google.protobuf.UInt64Value")) {
 235     m->well_known_type = UPB_WELLKNOWN_UINT64VALUE;
 236   } else if (!strcmp(name, "google.protobuf.Int32Value")) {
 237     m->well_known_type = UPB_WELLKNOWN_INT32VALUE;
 238   } else if (!strcmp(name, "google.protobuf.UInt32Value")) {
 239     m->well_known_type = UPB_WELLKNOWN_UINT32VALUE;
 240   } else if (!strcmp(name, "google.protobuf.BoolValue")) {
 241     m->well_known_type = UPB_WELLKNOWN_BOOLVALUE;
 242   } else if (!strcmp(name, "google.protobuf.StringValue")) {
 243     m->well_known_type = UPB_WELLKNOWN_STRINGVALUE;
 244   } else if (!strcmp(name, "google.protobuf.BytesValue")) {
 245     m->well_known_type = UPB_WELLKNOWN_BYTESVALUE;
 246   } else if (!strcmp(name, "google.protobuf.Value")) {
 247     m->well_known_type = UPB_WELLKNOWN_VALUE;
 248   } else if (!strcmp(name, "google.protobuf.ListValue")) {
 249     m->well_known_type = UPB_WELLKNOWN_LISTVALUE;
 250   } else if (!strcmp(name, "google.protobuf.Struct")) {
 251     m->well_known_type = UPB_WELLKNOWN_STRUCT;
 252   } else {
 253     m->well_known_type = UPB_WELLKNOWN_UNSPECIFIED;
 254   }
 255 }
 256
 257
 258 /* upb_enumdef ****************************************************************/
 259
 260 const char *upb_enumdef_fullname(const upb_enumdef *e) {
 261   return e->full_name;
 262 }
 263
 264 const char *upb_enumdef_name(const upb_enumdef *e) {
 265   return shortdefname(e->full_name);
 266 }
 267
 268 const upb_filedef *upb_enumdef_file(const upb_enumdef *e) {
 269   return e->file;
 270 }
 271
 272 int32_t upb_enumdef_default(const upb_enumdef *e) {
 273   UPB_ASSERT(upb_enumdef_iton(e, e->defaultval));
 274   return e->defaultval;
 275 }
 276
 277 int upb_enumdef_numvals(const upb_enumdef *e) {
 278   return (int)upb_strtable_count(&e->ntoi);
 279 }
 280
 281 void upb_enum_begin(upb_enum_iter *i, const upb_enumdef *e) {
 282   /* We iterate over the ntoi table, to account for duplicate numbers. */
 283   upb_strtable_begin(i, &e->ntoi);
 284 }
 285
 286 void upb_enum_next(upb_enum_iter *iter) { upb_strtable_next(iter); }
 287 bool upb_enum_done(upb_enum_iter *iter) { return upb_strtable_done(iter); }
 288
 289 bool upb_enumdef_ntoi(const upb_enumdef *def, const char *name,
 290                       size_t len, int32_t *num) {
 291   upb_value v;
 292   if (!upb_strtable_lookup2(&def->ntoi, name, len, &v)) {
 293     return false;
 294   }
 295   if (num) *num = upb_value_getint32(v);
 296   return true;
 297 }
 298
 299 const char *upb_enumdef_iton(const upb_enumdef *def, int32_t num) {
 300   upb_value v;
 301   return upb_inttable_lookup(&def->iton, num, &v) ? upb_value_getcstr(v) : NULL;
 302 }
 303
 304 const char *upb_enum_iter_name(upb_enum_iter *iter) {
 305   return upb_strtable_iter_key(iter).data;
 306 }
 307
 308 int32_t upb_enum_iter_number(upb_enum_iter *iter) {
 309   return upb_value_getint32(upb_strtable_iter_value(iter));
 310 }
 311
 312
 313 /* upb_fielddef ***************************************************************/
 314
 315 const char *upb_fielddef_fullname(const upb_fielddef *f) {
 316   return f->full_name;
 317 }
 318
 319 upb_fieldtype_t upb_fielddef_type(const upb_fielddef *f) {
 320   switch (f->type_) {
 321     case UPB_DESCRIPTOR_TYPE_DOUBLE:
 322       return UPB_TYPE_DOUBLE;
 323     case UPB_DESCRIPTOR_TYPE_FLOAT:
 324       return UPB_TYPE_FLOAT;
 325     case UPB_DESCRIPTOR_TYPE_INT64:
 326     case UPB_DESCRIPTOR_TYPE_SINT64:
 327     case UPB_DESCRIPTOR_TYPE_SFIXED64:
 328       return UPB_TYPE_INT64;
 329     case UPB_DESCRIPTOR_TYPE_INT32:
 330     case UPB_DESCRIPTOR_TYPE_SFIXED32:
 331     case UPB_DESCRIPTOR_TYPE_SINT32:
 332       return UPB_TYPE_INT32;
 333     case UPB_DESCRIPTOR_TYPE_UINT64:
 334     case UPB_DESCRIPTOR_TYPE_FIXED64:
 335       return UPB_TYPE_UINT64;
 336     case UPB_DESCRIPTOR_TYPE_UINT32:
 337     case UPB_DESCRIPTOR_TYPE_FIXED32:
 338       return UPB_TYPE_UINT32;
 339     case UPB_DESCRIPTOR_TYPE_ENUM:
 340       return UPB_TYPE_ENUM;
 341     case UPB_DESCRIPTOR_TYPE_BOOL:
 342       return UPB_TYPE_BOOL;
 343     case UPB_DESCRIPTOR_TYPE_STRING:
 344       return UPB_TYPE_STRING;
 345     case UPB_DESCRIPTOR_TYPE_BYTES:
 346       return UPB_TYPE_BYTES;
 347     case UPB_DESCRIPTOR_TYPE_GROUP:
 348     case UPB_DESCRIPTOR_TYPE_MESSAGE:
 349       return UPB_TYPE_MESSAGE;
 350   }
 351   UPB_UNREACHABLE();
 352 }
 353
 354 upb_descriptortype_t upb_fielddef_descriptortype(const upb_fielddef *f) {
 355   return f->type_;
 356 }
 357
 358 uint32_t upb_fielddef_index(const upb_fielddef *f) {
 359   return f->index_;
 360 }
 361
 362 upb_label_t upb_fielddef_label(const upb_fielddef *f) {
 363   return f->label_;
 364 }
 365
 366 uint32_t upb_fielddef_number(const upb_fielddef *f) {
 367   return f->number_;
 368 }
 369
 370 bool upb_fielddef_isextension(const upb_fielddef *f) {
 371   return f->is_extension_;
 372 }
 373
 374 bool upb_fielddef_lazy(const upb_fielddef *f) {
 375   return f->lazy_;
 376 }
 377
 378 bool upb_fielddef_packed(const upb_fielddef *f) {
 379   return f->packed_;
 380 }
 381
 382 const char *upb_fielddef_name(const upb_fielddef *f) {
 383   return shortdefname(f->full_name);
 384 }
 385
 386 const char *upb_fielddef_jsonname(const upb_fielddef *f) {
 387   return f->json_name;
 388 }
 389
 390 const upb_filedef *upb_fielddef_file(const upb_fielddef *f) {
 391   return f->file;
 392 }
 393
 394 const upb_msgdef *upb_fielddef_containingtype(const upb_fielddef *f) {
 395   return f->msgdef;
 396 }
 397
 398 const upb_oneofdef *upb_fielddef_containingoneof(const upb_fielddef *f) {
 399   return f->oneof;
 400 }
 401
 402 const upb_oneofdef *upb_fielddef_realcontainingoneof(const upb_fielddef *f) {
 403   if (!f->oneof || upb_oneofdef_issynthetic(f->oneof)) return NULL;
 404   return f->oneof;
 405 }
 406
 407 upb_msgval upb_fielddef_default(const upb_fielddef *f) {
 408   UPB_ASSERT(!upb_fielddef_issubmsg(f));
 409   upb_msgval ret;
 410   if (upb_fielddef_isstring(f)) {
 411     str_t *str = f->defaultval.str;
 412     if (str) {
 413       ret.str_val.data = str->str;
 414       ret.str_val.size = str->len;
 415     } else {
 416       ret.str_val.size = 0;
 417     }
 418   } else {
 419     memcpy(&ret, &f->defaultval, 8);
 420   }
 421   return ret;
 422 }
 423
 424 static void chkdefaulttype(const upb_fielddef *f, int ctype) {
 425   UPB_UNUSED(f);
 426   UPB_UNUSED(ctype);
 427 }
 428
 429 int64_t upb_fielddef_defaultint64(const upb_fielddef *f) {
 430   chkdefaulttype(f, UPB_TYPE_INT64);
 431   return f->defaultval.sint;
 432 }
 433
 434 int32_t upb_fielddef_defaultint32(const upb_fielddef *f) {
 435   chkdefaulttype(f, UPB_TYPE_INT32);
 436   return (int32_t)f->defaultval.sint;
 437 }
 438
 439 uint64_t upb_fielddef_defaultuint64(const upb_fielddef *f) {
 440   chkdefaulttype(f, UPB_TYPE_UINT64);
 441   return f->defaultval.uint;
 442 }
 443
 444 uint32_t upb_fielddef_defaultuint32(const upb_fielddef *f) {
 445   chkdefaulttype(f, UPB_TYPE_UINT32);
 446   return (uint32_t)f->defaultval.uint;
 447 }
 448
 449 bool upb_fielddef_defaultbool(const upb_fielddef *f) {
 450   chkdefaulttype(f, UPB_TYPE_BOOL);
 451   return f->defaultval.boolean;
 452 }
 453
 454 float upb_fielddef_defaultfloat(const upb_fielddef *f) {
 455   chkdefaulttype(f, UPB_TYPE_FLOAT);
 456   return f->defaultval.flt;
 457 }
 458
 459 double upb_fielddef_defaultdouble(const upb_fielddef *f) {
 460   chkdefaulttype(f, UPB_TYPE_DOUBLE);
 461   return f->defaultval.dbl;
 462 }
 463
 464 const char *upb_fielddef_defaultstr(const upb_fielddef *f, size_t *len) {
 465   str_t *str = f->defaultval.str;
 466   UPB_ASSERT(upb_fielddef_type(f) == UPB_TYPE_STRING ||
 467          upb_fielddef_type(f) == UPB_TYPE_BYTES ||
 468          upb_fielddef_type(f) == UPB_TYPE_ENUM);
 469   if (str) {
 470     if (len) *len = str->len;
 471     return str->str;
 472   } else {
 473     if (len) *len = 0;
 474     return NULL;
 475   }
 476 }
 477
 478 const upb_msgdef *upb_fielddef_msgsubdef(const upb_fielddef *f) {
 479   return upb_fielddef_type(f) == UPB_TYPE_MESSAGE ? f->sub.msgdef : NULL;
 480 }
 481
 482 const upb_enumdef *upb_fielddef_enumsubdef(const upb_fielddef *f) {
 483   return upb_fielddef_type(f) == UPB_TYPE_ENUM ? f->sub.enumdef : NULL;
 484 }
 485
 486 const upb_msglayout_field *upb_fielddef_layout(const upb_fielddef *f) {
 487   return &f->msgdef->layout->fields[f->layout_index];
 488 }
 489
 490 bool upb_fielddef_issubmsg(const upb_fielddef *f) {
 491   return upb_fielddef_type(f) == UPB_TYPE_MESSAGE;
 492 }
 493
 494 bool upb_fielddef_isstring(const upb_fielddef *f) {
 495   return upb_fielddef_type(f) == UPB_TYPE_STRING ||
 496          upb_fielddef_type(f) == UPB_TYPE_BYTES;
 497 }
 498
 499 bool upb_fielddef_isseq(const upb_fielddef *f) {
 500   return upb_fielddef_label(f) == UPB_LABEL_REPEATED;
 501 }
 502
 503 bool upb_fielddef_isprimitive(const upb_fielddef *f) {
 504   return !upb_fielddef_isstring(f) && !upb_fielddef_issubmsg(f);
 505 }
 506
 507 bool upb_fielddef_ismap(const upb_fielddef *f) {
 508   return upb_fielddef_isseq(f) && upb_fielddef_issubmsg(f) &&
 509          upb_msgdef_mapentry(upb_fielddef_msgsubdef(f));
 510 }
 511
 512 bool upb_fielddef_hassubdef(const upb_fielddef *f) {
 513   return upb_fielddef_issubmsg(f) || upb_fielddef_type(f) == UPB_TYPE_ENUM;
 514 }
 515
 516 bool upb_fielddef_haspresence(const upb_fielddef *f) {
 517   if (upb_fielddef_isseq(f)) return false;
 518   return upb_fielddef_issubmsg(f) || upb_fielddef_containingoneof(f) ||
 519          f->file->syntax == UPB_SYNTAX_PROTO2;
 520 }
 521
 522 static bool between(int32_t x, int32_t low, int32_t high) {
 523   return x >= low && x <= high;
 524 }
 525
 526 bool upb_fielddef_checklabel(int32_t label) { return between(label, 1, 3); }
 527 bool upb_fielddef_checktype(int32_t type) { return between(type, 1, 11); }
 528 bool upb_fielddef_checkintfmt(int32_t fmt) { return between(fmt, 1, 3); }
 529
 530 bool upb_fielddef_checkdescriptortype(int32_t type) {
 531   return between(type, 1, 18);
 532 }
 533
 534 /* upb_msgdef *****************************************************************/
 535
 536 const char *upb_msgdef_fullname(const upb_msgdef *m) {
 537   return m->full_name;
 538 }
 539
 540 const upb_filedef *upb_msgdef_file(const upb_msgdef *m) {
 541   return m->file;
 542 }
 543
 544 const char *upb_msgdef_name(const upb_msgdef *m) {
 545   return shortdefname(m->full_name);
 546 }
 547
 548 upb_syntax_t upb_msgdef_syntax(const upb_msgdef *m) {
 549   return m->file->syntax;
 550 }
 551
 552 const upb_fielddef *upb_msgdef_itof(const upb_msgdef *m, uint32_t i) {
 553   upb_value val;
 554   return upb_inttable_lookup(&m->itof, i, &val) ? upb_value_getconstptr(val)
 555                                                 : NULL;
 556 }
 557
 558 const upb_fielddef *upb_msgdef_ntof(const upb_msgdef *m, const char *name,
 559                                     size_t len) {
 560   upb_value val;
 561
 562   if (!upb_strtable_lookup2(&m->ntof, name, len, &val)) {
 563     return NULL;
 564   }
 565
 566   return unpack_def(val, UPB_DEFTYPE_FIELD);
 567 }
 568
 569 const upb_oneofdef *upb_msgdef_ntoo(const upb_msgdef *m, const char *name,
 570                                     size_t len) {
 571   upb_value val;
 572
 573   if (!upb_strtable_lookup2(&m->ntof, name, len, &val)) {
 574     return NULL;
 575   }
 576
 577   return unpack_def(val, UPB_DEFTYPE_ONEOF);
 578 }
 579
 580 bool upb_msgdef_lookupname(const upb_msgdef *m, const char *name, size_t len,
 581                            const upb_fielddef **f, const upb_oneofdef **o) {
 582   upb_value val;
 583
 584   if (!upb_strtable_lookup2(&m->ntof, name, len, &val)) {
 585     return false;
 586   }
 587
 588   *o = unpack_def(val, UPB_DEFTYPE_ONEOF);
 589   *f = unpack_def(val, UPB_DEFTYPE_FIELD);
 590   return *o || *f;  /* False if this was a JSON name. */
 591 }
 592
 593 const upb_fielddef *upb_msgdef_lookupjsonname(const upb_msgdef *m,
 594                                               const char *name, size_t len) {
 595   upb_value val;
 596   const upb_fielddef* f;
 597
 598   if (!upb_strtable_lookup2(&m->ntof, name, len, &val)) {
 599     return NULL;
 600   }
 601
 602   f = unpack_def(val, UPB_DEFTYPE_FIELD);
 603   if (!f) f = unpack_def(val, UPB_DEFTYPE_FIELD_JSONNAME);
 604
 605   return f;
 606 }
 607
 608 int upb_msgdef_numfields(const upb_msgdef *m) {
 609   return m->field_count;
 610 }
 611
 612 int upb_msgdef_numoneofs(const upb_msgdef *m) {
 613   return m->oneof_count;
 614 }
 615
 616 int upb_msgdef_numrealoneofs(const upb_msgdef *m) {
 617   return m->real_oneof_count;
 618 }
 619
 620 int upb_msgdef_fieldcount(const upb_msgdef *m) {
 621   return m->field_count;
 622 }
 623
 624 int upb_msgdef_oneofcount(const upb_msgdef *m) {
 625   return m->oneof_count;
 626 }
 627
 628 int upb_msgdef_realoneofcount(const upb_msgdef *m) {
 629   return m->real_oneof_count;
 630 }
 631
 632 const upb_msglayout *upb_msgdef_layout(const upb_msgdef *m) {
 633   return m->layout;
 634 }
 635
 636 const upb_fielddef *upb_msgdef_field(const upb_msgdef *m, int i) {
 637   UPB_ASSERT(i >= 0 && i < m->field_count);
 638   return &m->fields[i];
 639 }
 640
 641 const upb_oneofdef *upb_msgdef_oneof(const upb_msgdef *m, int i) {
 642   UPB_ASSERT(i >= 0 && i < m->oneof_count);
 643   return &m->oneofs[i];
 644 }
 645
 646 bool upb_msgdef_mapentry(const upb_msgdef *m) {
 647   return m->map_entry;
 648 }
 649
 650 upb_wellknowntype_t upb_msgdef_wellknowntype(const upb_msgdef *m) {
 651   return m->well_known_type;
 652 }
 653
 654 bool upb_msgdef_isnumberwrapper(const upb_msgdef *m) {
 655   upb_wellknowntype_t type = upb_msgdef_wellknowntype(m);
 656   return type >= UPB_WELLKNOWN_DOUBLEVALUE &&
 657          type <= UPB_WELLKNOWN_UINT32VALUE;
 658 }
 659
 660 bool upb_msgdef_iswrapper(const upb_msgdef *m) {
 661   upb_wellknowntype_t type = upb_msgdef_wellknowntype(m);
 662   return type >= UPB_WELLKNOWN_DOUBLEVALUE &&
 663          type <= UPB_WELLKNOWN_BOOLVALUE;
 664 }
 665
 666 void upb_msg_field_begin(upb_msg_field_iter *iter, const upb_msgdef *m) {
 667   upb_inttable_begin(iter, &m->itof);
 668 }
 669
 670 void upb_msg_field_next(upb_msg_field_iter *iter) { upb_inttable_next(iter); }
 671
 672 bool upb_msg_field_done(const upb_msg_field_iter *iter) {
 673   return upb_inttable_done(iter);
 674 }
 675
 676 upb_fielddef *upb_msg_iter_field(const upb_msg_field_iter *iter) {
 677   return (upb_fielddef *)upb_value_getconstptr(upb_inttable_iter_value(iter));
 678 }
 679
 680 void upb_msg_field_iter_setdone(upb_msg_field_iter *iter) {
 681   upb_inttable_iter_setdone(iter);
 682 }
 683
 684 bool upb_msg_field_iter_isequal(const upb_msg_field_iter * iter1,
 685                                 const upb_msg_field_iter * iter2) {
 686   return upb_inttable_iter_isequal(iter1, iter2);
 687 }
 688
 689 void upb_msg_oneof_begin(upb_msg_oneof_iter *iter, const upb_msgdef *m) {
 690   upb_strtable_begin(iter, &m->ntof);
 691   /* We need to skip past any initial fields. */
 692   while (!upb_strtable_done(iter) &&
 693          !unpack_def(upb_strtable_iter_value(iter), UPB_DEFTYPE_ONEOF)) {
 694     upb_strtable_next(iter);
 695   }
 696 }
 697
 698 void upb_msg_oneof_next(upb_msg_oneof_iter *iter) {
 699   /* We need to skip past fields to return only oneofs. */
 700   do {
 701     upb_strtable_next(iter);
 702   } while (!upb_strtable_done(iter) &&
 703            !unpack_def(upb_strtable_iter_value(iter), UPB_DEFTYPE_ONEOF));
 704 }
 705
 706 bool upb_msg_oneof_done(const upb_msg_oneof_iter *iter) {
 707   return upb_strtable_done(iter);
 708 }
 709
 710 const upb_oneofdef *upb_msg_iter_oneof(const upb_msg_oneof_iter *iter) {
 711   return unpack_def(upb_strtable_iter_value(iter), UPB_DEFTYPE_ONEOF);
 712 }
 713
 714 void upb_msg_oneof_iter_setdone(upb_msg_oneof_iter *iter) {
 715   upb_strtable_iter_setdone(iter);
 716 }
 717
 718 bool upb_msg_oneof_iter_isequal(const upb_msg_oneof_iter *iter1,
 719                                 const upb_msg_oneof_iter *iter2) {
 720   return upb_strtable_iter_isequal(iter1, iter2);
 721 }
 722
 723 /* upb_oneofdef ***************************************************************/
 724
 725 const char *upb_oneofdef_name(const upb_oneofdef *o) {
 726   return shortdefname(o->full_name);
 727 }
 728
 729 const upb_msgdef *upb_oneofdef_containingtype(const upb_oneofdef *o) {
 730   return o->parent;
 731 }
 732
 733 int upb_oneofdef_fieldcount(const upb_oneofdef *o) {
 734   return o->field_count;
 735 }
 736
 737 const upb_fielddef *upb_oneofdef_field(const upb_oneofdef *o, int i) {
 738   UPB_ASSERT(i < o->field_count);
 739   return o->fields[i];
 740 }
 741
 742 int upb_oneofdef_numfields(const upb_oneofdef *o) {
 743   return o->field_count;
 744 }
 745
 746 uint32_t upb_oneofdef_index(const upb_oneofdef *o) {
 747   return o - o->parent->oneofs;
 748 }
 749
 750 bool upb_oneofdef_issynthetic(const upb_oneofdef *o) {
 751   return o->synthetic;
 752 }
 753
 754 const upb_fielddef *upb_oneofdef_ntof(const upb_oneofdef *o,
 755                                       const char *name, size_t length) {
 756   upb_value val;
 757   return upb_strtable_lookup2(&o->ntof, name, length, &val) ?
 758       upb_value_getptr(val) : NULL;
 759 }
 760
 761 const upb_fielddef *upb_oneofdef_itof(const upb_oneofdef *o, uint32_t num) {
 762   upb_value val;
 763   return upb_inttable_lookup(&o->itof, num, &val) ? upb_value_getptr(val)
 764                                                   : NULL;
 765 }
 766
 767 void upb_oneof_begin(upb_oneof_iter *iter, const upb_oneofdef *o) {
 768   upb_inttable_begin(iter, &o->itof);
 769 }
 770
 771 void upb_oneof_next(upb_oneof_iter *iter) {
 772   upb_inttable_next(iter);
 773 }
 774
 775 bool upb_oneof_done(upb_oneof_iter *iter) {
 776   return upb_inttable_done(iter);
 777 }
 778
 779 upb_fielddef *upb_oneof_iter_field(const upb_oneof_iter *iter) {
 780   return (upb_fielddef *)upb_value_getconstptr(upb_inttable_iter_value(iter));
 781 }
 782
 783 void upb_oneof_iter_setdone(upb_oneof_iter *iter) {
 784   upb_inttable_iter_setdone(iter);
 785 }
 786
 787 /* upb_filedef ****************************************************************/
 788
 789 const char *upb_filedef_name(const upb_filedef *f) {
 790   return f->name;
 791 }
 792
 793 const char *upb_filedef_package(const upb_filedef *f) {
 794   return f->package;
 795 }
 796
 797 const char *upb_filedef_phpprefix(const upb_filedef *f) {
 798   return f->phpprefix;
 799 }
 800
 801 const char *upb_filedef_phpnamespace(const upb_filedef *f) {
 802   return f->phpnamespace;
 803 }
 804
 805 upb_syntax_t upb_filedef_syntax(const upb_filedef *f) {
 806   return f->syntax;
 807 }
 808
 809 int upb_filedef_msgcount(const upb_filedef *f) {
 810   return f->msg_count;
 811 }
 812
 813 int upb_filedef_depcount(const upb_filedef *f) {
 814   return f->dep_count;
 815 }
 816
 817 int upb_filedef_enumcount(const upb_filedef *f) {
 818   return f->enum_count;
 819 }
 820
 821 const upb_filedef *upb_filedef_dep(const upb_filedef *f, int i) {
 822   return i < 0 || i >= f->dep_count ? NULL : f->deps[i];
 823 }
 824
 825 const upb_msgdef *upb_filedef_msg(const upb_filedef *f, int i) {
 826   return i < 0 || i >= f->msg_count ? NULL : &f->msgs[i];
 827 }
 828
 829 const upb_enumdef *upb_filedef_enum(const upb_filedef *f, int i) {
 830   return i < 0 || i >= f->enum_count ? NULL : &f->enums[i];
 831 }
 832
 833 const upb_symtab *upb_filedef_symtab(const upb_filedef *f) {
 834   return f->symtab;
 835 }
 836
 837 void upb_symtab_free(upb_symtab *s) {
 838   upb_arena_free(s->arena);
 839   upb_gfree(s);
 840 }
 841
 842 upb_symtab *upb_symtab_new(void) {
 843   upb_symtab *s = upb_gmalloc(sizeof(*s));
 844
 845   if (!s) {
 846     return NULL;
 847   }
 848
 849   s->arena = upb_arena_new();
 850   s->bytes_loaded = 0;
 851
 852   if (!upb_strtable_init(&s->syms, 32, s->arena) ||
 853       !upb_strtable_init(&s->files, 4, s->arena)) {
 854     upb_arena_free(s->arena);
 855     upb_gfree(s);
 856     s = NULL;
 857   }
 858   return s;
 859 }
 860
 861 const upb_msgdef *upb_symtab_lookupmsg(const upb_symtab *s, const char *sym) {
 862   upb_value v;
 863   return upb_strtable_lookup(&s->syms, sym, &v) ?
 864       unpack_def(v, UPB_DEFTYPE_MSG) : NULL;
 865 }
 866
 867 const upb_msgdef *upb_symtab_lookupmsg2(const upb_symtab *s, const char *sym,
 868                                         size_t len) {
 869   upb_value v;
 870   return upb_strtable_lookup2(&s->syms, sym, len, &v) ?
 871       unpack_def(v, UPB_DEFTYPE_MSG) : NULL;
 872 }
 873
 874 const upb_enumdef *upb_symtab_lookupenum(const upb_symtab *s, const char *sym) {
 875   upb_value v;
 876   return upb_strtable_lookup(&s->syms, sym, &v) ?
 877       unpack_def(v, UPB_DEFTYPE_ENUM) : NULL;
 878 }
 879
 880 const upb_filedef *upb_symtab_lookupfile(const upb_symtab *s, const char *name) {
 881   upb_value v;
 882   return upb_strtable_lookup(&s->files, name, &v) ? upb_value_getconstptr(v)
 883                                                   : NULL;
 884 }
 885
 886 const upb_filedef *upb_symtab_lookupfile2(
 887     const upb_symtab *s, const char *name, size_t len) {
 888   upb_value v;
 889   return upb_strtable_lookup2(&s->files, name, len, &v) ?
 890       upb_value_getconstptr(v) : NULL;
 891 }
 892
 893 int upb_symtab_filecount(const upb_symtab *s) {
 894   return (int)upb_strtable_count(&s->files);
 895 }
 896
 897 /* Code to build defs from descriptor protos. *********************************/
 898
 899 /* There is a question of how much validation to do here.  It will be difficult
 900  * to perfectly match the amount of validation performed by proto2.  But since
 901  * this code is used to directly build defs from Ruby (for example) we do need
 902  * to validate important constraints like uniqueness of names and numbers. */
 903
 904 #define CHK_OOM(x) if (!(x)) { symtab_oomerr(ctx); }
 905
 906 typedef struct {
 907   upb_symtab *symtab;
 908   upb_filedef *file;              /* File we are building. */
 909   upb_arena *arena;               /* Allocate defs here. */
 910   const upb_msglayout **layouts;  /* NULL if we should build layouts. */
 911   upb_status *status;             /* Record errors here. */
 912   jmp_buf err;                    /* longjmp() on error. */
 913 } symtab_addctx;
 914
 915 UPB_NORETURN UPB_NOINLINE UPB_PRINTF(2, 3)
 916 static void symtab_errf(symtab_addctx *ctx, const char *fmt, ...) {
 917   va_list argp;
 918   va_start(argp, fmt);
 919   upb_status_vseterrf(ctx->status, fmt, argp);
 920   va_end(argp);
 921   UPB_LONGJMP(ctx->err, 1);
 922 }
 923
 924 UPB_NORETURN UPB_NOINLINE
 925 static void symtab_oomerr(symtab_addctx *ctx) {
 926   upb_status_setoom(ctx->status);
 927   UPB_LONGJMP(ctx->err, 1);
 928 }
 929
 930 void *symtab_alloc(symtab_addctx *ctx, size_t bytes) {
 931   void *ret = upb_arena_malloc(ctx->arena, bytes);
 932   if (!ret) symtab_oomerr(ctx);
 933   return ret;
 934 }
 935
 936 static void check_ident(symtab_addctx *ctx, upb_strview name, bool full) {
 937   const char *str = name.data;
 938   size_t len = name.size;
 939   bool start = true;
 940   size_t i;
 941   for (i = 0; i < len; i++) {
 942     char c = str[i];
 943     if (c == '.') {
 944       if (start || !full) {
 945         symtab_errf(ctx, "invalid name: unexpected '.' (%.*s)", (int)len, str);
 946       }
 947       start = true;
 948     } else if (start) {
 949       if (!upb_isletter(c)) {
 950         symtab_errf(
 951             ctx,
 952             "invalid name: path components must start with a letter (%.*s)",
 953             (int)len, str);
 954       }
 955       start = false;
 956     } else {
 957       if (!upb_isalphanum(c)) {
 958         symtab_errf(ctx, "invalid name: non-alphanumeric character (%.*s)",
 959                     (int)len, str);
 960       }
 961     }
 962   }
 963   if (start) {
 964     symtab_errf(ctx, "invalid name: empty part (%.*s)", (int)len, str);
 965   }
 966 }
 967
 968 static size_t div_round_up(size_t n, size_t d) {
 969   return (n + d - 1) / d;
 970 }
 971
 972 static size_t upb_msgval_sizeof(upb_fieldtype_t type) {
 973   switch (type) {
 974     case UPB_TYPE_DOUBLE:
 975     case UPB_TYPE_INT64:
 976     case UPB_TYPE_UINT64:
 977       return 8;
 978     case UPB_TYPE_ENUM:
 979     case UPB_TYPE_INT32:
 980     case UPB_TYPE_UINT32:
 981     case UPB_TYPE_FLOAT:
 982       return 4;
 983     case UPB_TYPE_BOOL:
 984       return 1;
 985     case UPB_TYPE_MESSAGE:
 986       return sizeof(void*);
 987     case UPB_TYPE_BYTES:
 988     case UPB_TYPE_STRING:
 989       return sizeof(upb_strview);
 990   }
 991   UPB_UNREACHABLE();
 992 }
 993
 994 static uint8_t upb_msg_fielddefsize(const upb_fielddef *f) {
 995   if (upb_msgdef_mapentry(upb_fielddef_containingtype(f))) {
 996     upb_map_entry ent;
 997     UPB_ASSERT(sizeof(ent.k) == sizeof(ent.v));
 998     return sizeof(ent.k);
 999   } else if (upb_fielddef_isseq(f)) {
1000     return sizeof(void*);
1001   } else {
1002     return upb_msgval_sizeof(upb_fielddef_type(f));
1003   }
1004 }
1005
1006 static uint32_t upb_msglayout_place(upb_msglayout *l, size_t size) {
1007   uint32_t ret;
1008
1009   l->size = UPB_ALIGN_UP(l->size, size);
1010   ret = l->size;
1011   l->size += size;
1012   return ret;
1013 }
1014
1015 static int field_number_cmp(const void *p1, const void *p2) {
1016   const upb_msglayout_field *f1 = p1;
1017   const upb_msglayout_field *f2 = p2;
1018   return f1->number - f2->number;
1019 }
1020
1021 static void assign_layout_indices(const upb_msgdef *m, upb_msglayout *l,
1022                                   upb_msglayout_field *fields) {
1023   int i;
1024   int n = upb_msgdef_numfields(m);
1025   int dense_below = 0;
1026   for (i = 0; i < n; i++) {
1027     upb_fielddef *f = (upb_fielddef*)upb_msgdef_itof(m, fields[i].number);
1028     UPB_ASSERT(f);
1029     f->layout_index = i;
1030     if (i < UINT8_MAX && fields[i].number == i + 1 &&
1031         (i == 0 || fields[i-1].number == i)) {
1032       dense_below = i + 1;
1033     }
1034   }
1035   l->dense_below = dense_below;
1036 }
1037
1038 static void fill_fieldlayout(upb_msglayout_field *field, const upb_fielddef *f) {
1039   field->number = upb_fielddef_number(f);
1040   field->descriptortype = upb_fielddef_descriptortype(f);
1041
1042   if (field->descriptortype == UPB_DTYPE_STRING &&
1043       f->file->syntax == UPB_SYNTAX_PROTO2) {
1044     /* See TableDescriptorType() in upbc/generator.cc for details and
1045      * rationale. */
1046     field->descriptortype = UPB_DTYPE_BYTES;
1047   }
1048
1049   if (upb_fielddef_ismap(f)) {
1050     field->mode = _UPB_MODE_MAP;
1051   } else if (upb_fielddef_isseq(f)) {
1052     field->mode = _UPB_MODE_ARRAY;
1053   } else {
1054     field->mode = _UPB_MODE_SCALAR;
1055   }
1056
1057   if (upb_fielddef_packed(f)) {
1058     field->mode |= _UPB_MODE_IS_PACKED;
1059   }
1060 }
1061
1062 /* This function is the dynamic equivalent of message_layout.{cc,h} in upbc.
1063  * It computes a dynamic layout for all of the fields in |m|. */
1064 static void make_layout(symtab_addctx *ctx, const upb_msgdef *m) {
1065   upb_msglayout *l = (upb_msglayout*)m->layout;
1066   upb_msg_field_iter it;
1067   upb_msg_oneof_iter oit;
1068   size_t hasbit;
1069   size_t field_count = upb_msgdef_numfields(m);
1070   size_t submsg_count = 0;
1071   const upb_msglayout **submsgs;
1072   upb_msglayout_field *fields;
1073
1074   memset(l, 0, sizeof(*l) + sizeof(_upb_fasttable_entry));
1075
1076   /* Count sub-messages. */
1077   for (size_t i = 0; i < field_count; i++) {
1078     if (upb_fielddef_issubmsg(&m->fields[i])) {
1079       submsg_count++;
1080     }
1081   }
1082
1083   fields = symtab_alloc(ctx, field_count * sizeof(*fields));
1084   submsgs = symtab_alloc(ctx, submsg_count * sizeof(*submsgs));
1085
1086   l->field_count = upb_msgdef_numfields(m);
1087   l->fields = fields;
1088   l->submsgs = submsgs;
1089   l->table_mask = 0;
1090
1091   /* TODO(haberman): initialize fast tables so that reflection-based parsing
1092    * can get the same speeds as linked-in types. */
1093   l->fasttable[0].field_parser = &fastdecode_generic;
1094   l->fasttable[0].field_data = 0;
1095
1096   if (upb_msgdef_mapentry(m)) {
1097     /* TODO(haberman): refactor this method so this special case is more
1098      * elegant. */
1099     const upb_fielddef *key = upb_msgdef_itof(m, 1);
1100     const upb_fielddef *val = upb_msgdef_itof(m, 2);
1101     fields[0].number = 1;
1102     fields[1].number = 2;
1103     fields[0].mode = _UPB_MODE_SCALAR;
1104     fields[1].mode = _UPB_MODE_SCALAR;
1105     fields[0].presence = 0;
1106     fields[1].presence = 0;
1107     fields[0].descriptortype = upb_fielddef_descriptortype(key);
1108     fields[1].descriptortype = upb_fielddef_descriptortype(val);
1109     fields[0].offset = 0;
1110     fields[1].offset = sizeof(upb_strview);
1111     fields[1].submsg_index = 0;
1112
1113     if (upb_fielddef_type(val) == UPB_TYPE_MESSAGE) {
1114       submsgs[0] = upb_fielddef_msgsubdef(val)->layout;
1115     }
1116
1117     l->field_count = 2;
1118     l->size = 2 * sizeof(upb_strview);
1119     l->size = UPB_ALIGN_UP(l->size, 8);
1120     return;
1121   }
1122
1123   /* Allocate data offsets in three stages:
1124    *
1125    * 1. hasbits.
1126    * 2. regular fields.
1127    * 3. oneof fields.
1128    *
1129    * OPT: There is a lot of room for optimization here to minimize the size.
1130    */
1131
1132   /* Allocate hasbits and set basic field attributes. */
1133   submsg_count = 0;
1134   for (upb_msg_field_begin(&it, m), hasbit = 0;
1135        !upb_msg_field_done(&it);
1136        upb_msg_field_next(&it)) {
1137     upb_fielddef* f = upb_msg_iter_field(&it);
1138     upb_msglayout_field *field = &fields[upb_fielddef_index(f)];
1139
1140     fill_fieldlayout(field, f);
1141
1142     if (upb_fielddef_issubmsg(f)) {
1143       const upb_msgdef *subm = upb_fielddef_msgsubdef(f);
1144       field->submsg_index = submsg_count++;
1145       submsgs[field->submsg_index] = subm->layout;
1146     }
1147
1148     if (upb_fielddef_haspresence(f) && !upb_fielddef_realcontainingoneof(f)) {
1149       /* We don't use hasbit 0, so that 0 can indicate "no presence" in the
1150        * table. This wastes one hasbit, but we don't worry about it for now. */
1151       field->presence = ++hasbit;
1152     } else {
1153       field->presence = 0;
1154     }
1155   }
1156
1157   /* Account for space used by hasbits. */
1158   l->size = div_round_up(hasbit, 8);
1159
1160   /* Allocate non-oneof fields. */
1161   for (upb_msg_field_begin(&it, m); !upb_msg_field_done(&it);
1162        upb_msg_field_next(&it)) {
1163     const upb_fielddef* f = upb_msg_iter_field(&it);
1164     size_t field_size = upb_msg_fielddefsize(f);
1165     size_t index = upb_fielddef_index(f);
1166
1167     if (upb_fielddef_realcontainingoneof(f)) {
1168       /* Oneofs are handled separately below. */
1169       continue;
1170     }
1171
1172     fields[index].offset = upb_msglayout_place(l, field_size);
1173   }
1174
1175   /* Allocate oneof fields.  Each oneof field consists of a uint32 for the case
1176    * and space for the actual data. */
1177   for (upb_msg_oneof_begin(&oit, m); !upb_msg_oneof_done(&oit);
1178        upb_msg_oneof_next(&oit)) {
1179     const upb_oneofdef* o = upb_msg_iter_oneof(&oit);
1180     upb_oneof_iter fit;
1181
1182     size_t case_size = sizeof(uint32_t);  /* Could potentially optimize this. */
1183     size_t field_size = 0;
1184     uint32_t case_offset;
1185     uint32_t data_offset;
1186
1187     if (upb_oneofdef_issynthetic(o)) continue;
1188
1189     /* Calculate field size: the max of all field sizes. */
1190     for (upb_oneof_begin(&fit, o);
1191          !upb_oneof_done(&fit);
1192          upb_oneof_next(&fit)) {
1193       const upb_fielddef* f = upb_oneof_iter_field(&fit);
1194       field_size = UPB_MAX(field_size, upb_msg_fielddefsize(f));
1195     }
1196
1197     /* Align and allocate case offset. */
1198     case_offset = upb_msglayout_place(l, case_size);
1199     data_offset = upb_msglayout_place(l, field_size);
1200
1201     for (upb_oneof_begin(&fit, o);
1202          !upb_oneof_done(&fit);
1203          upb_oneof_next(&fit)) {
1204       const upb_fielddef* f = upb_oneof_iter_field(&fit);
1205       fields[upb_fielddef_index(f)].offset = data_offset;
1206       fields[upb_fielddef_index(f)].presence = ~case_offset;
1207     }
1208   }
1209
1210   /* Size of the entire structure should be a multiple of its greatest
1211    * alignment.  TODO: track overall alignment for real? */
1212   l->size = UPB_ALIGN_UP(l->size, 8);
1213
1214   /* Sort fields by number. */
1215   qsort(fields, upb_msgdef_numfields(m), sizeof(*fields), field_number_cmp);
1216   assign_layout_indices(m, l, fields);
1217 }
1218
1219 static char *strviewdup(symtab_addctx *ctx, upb_strview view) {
1220   return upb_strdup2(view.data, view.size, ctx->arena);
1221 }
1222
1223 static bool streql2(const char *a, size_t n, const char *b) {
1224   return n == strlen(b) && memcmp(a, b, n) == 0;
1225 }
1226
1227 static bool streql_view(upb_strview view, const char *b) {
1228   return streql2(view.data, view.size, b);
1229 }
1230
1231 static const char *makefullname(symtab_addctx *ctx, const char *prefix,
1232                                 upb_strview name) {
1233   if (prefix) {
1234     /* ret = prefix + '.' + name; */
1235     size_t n = strlen(prefix);
1236     char *ret = symtab_alloc(ctx, n + name.size + 2);
1237     strcpy(ret, prefix);
1238     ret[n] = '.';
1239     memcpy(&ret[n + 1], name.data, name.size);
1240     ret[n + 1 + name.size] = '\0';
1241     return ret;
1242   } else {
1243     return strviewdup(ctx, name);
1244   }
1245 }
1246
1247 static void finalize_oneofs(symtab_addctx *ctx, upb_msgdef *m) {
1248   int i;
1249   int synthetic_count = 0;
1250   upb_oneofdef *mutable_oneofs = (upb_oneofdef*)m->oneofs;
1251
1252   for (i = 0; i < m->oneof_count; i++) {
1253     upb_oneofdef *o = &mutable_oneofs[i];
1254
1255     if (o->synthetic && o->field_count != 1) {
1256       symtab_errf(ctx, "Synthetic oneofs must have one field, not %d: %s",
1257                   o->field_count, upb_oneofdef_name(o));
1258     }
1259
1260     if (o->synthetic) {
1261       synthetic_count++;
1262     } else if (synthetic_count != 0) {
1263       symtab_errf(ctx, "Synthetic oneofs must be after all other oneofs: %s",
1264                   upb_oneofdef_name(o));
1265     }
1266
1267     o->fields = symtab_alloc(ctx, sizeof(upb_fielddef *) * o->field_count);
1268     o->field_count = 0;
1269   }
1270
1271   for (i = 0; i < m->field_count; i++) {
1272     const upb_fielddef *f = &m->fields[i];
1273     upb_oneofdef *o = (upb_oneofdef*)f->oneof;
1274     if (o) {
1275       o->fields[o->field_count++] = f;
1276     }
1277   }
1278
1279   m->real_oneof_count = m->oneof_count - synthetic_count;
1280 }
1281
1282 size_t getjsonname(const char *name, char *buf, size_t len) {
1283   size_t src, dst = 0;
1284   bool ucase_next = false;
1285
1286 #define WRITE(byte) \
1287   ++dst; \
1288   if (dst < len) buf[dst - 1] = byte; \
1289   else if (dst == len) buf[dst - 1] = '\0'
1290
1291   if (!name) {
1292     WRITE('\0');
1293     return 0;
1294   }
1295
1296   /* Implement the transformation as described in the spec:
1297    *   1. upper case all letters after an underscore.
1298    *   2. remove all underscores.
1299    */
1300   for (src = 0; name[src]; src++) {
1301     if (name[src] == '_') {
1302       ucase_next = true;
1303       continue;
1304     }
1305
1306     if (ucase_next) {
1307       WRITE(toupper(name[src]));
1308       ucase_next = false;
1309     } else {
1310       WRITE(name[src]);
1311     }
1312   }
1313
1314   WRITE('\0');
1315   return dst;
1316
1317 #undef WRITE
1318 }
1319
1320 static char* makejsonname(symtab_addctx *ctx, const char* name) {
1321   size_t size = getjsonname(name, NULL, 0);
1322   char* json_name = symtab_alloc(ctx, size);
1323   getjsonname(name, json_name, size);
1324   return json_name;
1325 }
1326
1327 static void symtab_add(symtab_addctx *ctx, const char *name, upb_value v) {
1328   if (upb_strtable_lookup(&ctx->symtab->syms, name, NULL)) {
1329     symtab_errf(ctx, "duplicate symbol '%s'", name);
1330   }
1331   size_t len = strlen(name);
1332   CHK_OOM(upb_strtable_insert(&ctx->symtab->syms, name, len, v,
1333                               ctx->symtab->arena));
1334 }
1335
1336 /* Given a symbol and the base symbol inside which it is defined, find the
1337  * symbol's definition in t. */
1338 static const void *symtab_resolve(symtab_addctx *ctx, const upb_fielddef *f,
1339                                   const char *base, upb_strview sym,
1340                                   upb_deftype_t type) {
1341   const upb_strtable *t = &ctx->symtab->syms;
1342   if(sym.size == 0) goto notfound;
1343   if(sym.data[0] == '.') {
1344     /* Symbols starting with '.' are absolute, so we do a single lookup.
1345      * Slice to omit the leading '.' */
1346     upb_value v;
1347     if (!upb_strtable_lookup2(t, sym.data + 1, sym.size - 1, &v)) {
1348       goto notfound;
1349     }
1350
1351     const void *ret = unpack_def(v, type);
1352     if (!ret) {
1353       symtab_errf(ctx, "type mismatch when resolving field %s, name %s",
1354                   f->full_name, sym.data);
1355     }
1356     return ret;
1357   } else {
1358     /* Remove components from base until we find an entry or run out.
1359      * TODO: This branch is totally broken, but currently not used. */
1360     (void)base;
1361     UPB_ASSERT(false);
1362     goto notfound;
1363   }
1364
1365 notfound:
1366   symtab_errf(ctx, "couldn't resolve name '" UPB_STRVIEW_FORMAT "'",
1367               UPB_STRVIEW_ARGS(sym));
1368 }
1369
1370 static void create_oneofdef(
1371     symtab_addctx *ctx, upb_msgdef *m,
1372     const google_protobuf_OneofDescriptorProto *oneof_proto) {
1373   upb_oneofdef *o;
1374   upb_strview name = google_protobuf_OneofDescriptorProto_name(oneof_proto);
1375   upb_value v;
1376
1377   o = (upb_oneofdef*)&m->oneofs[m->oneof_count++];
1378   o->parent = m;
1379   o->full_name = makefullname(ctx, m->full_name, name);
1380   o->field_count = 0;
1381   o->synthetic = false;
1382
1383   v = pack_def(o, UPB_DEFTYPE_ONEOF);
1384   symtab_add(ctx, o->full_name, v);
1385   CHK_OOM(upb_strtable_insert(&m->ntof, name.data, name.size, v, ctx->arena));
1386
1387   CHK_OOM(upb_inttable_init(&o->itof, ctx->arena));
1388   CHK_OOM(upb_strtable_init(&o->ntof, 4, ctx->arena));
1389 }
1390
1391 static str_t *newstr(symtab_addctx *ctx, const char *data, size_t len) {
1392   str_t *ret = symtab_alloc(ctx, sizeof(*ret) + len);
1393   if (!ret) return NULL;
1394   ret->len = len;
1395   if (len) memcpy(ret->str, data, len);
1396   ret->str[len] = '\0';
1397   return ret;
1398 }
1399
1400 static void parse_default(symtab_addctx *ctx, const char *str, size_t len,
1401                           upb_fielddef *f) {
1402   char *end;
1403   char nullz[64];
1404   errno = 0;
1405
1406   switch (upb_fielddef_type(f)) {
1407     case UPB_TYPE_INT32:
1408     case UPB_TYPE_INT64:
1409     case UPB_TYPE_UINT32:
1410     case UPB_TYPE_UINT64:
1411     case UPB_TYPE_DOUBLE:
1412     case UPB_TYPE_FLOAT:
1413       /* Standard C number parsing functions expect null-terminated strings. */
1414       if (len >= sizeof(nullz) - 1) {
1415         symtab_errf(ctx, "Default too long: %.*s", (int)len, str);
1416       }
1417       memcpy(nullz, str, len);
1418       nullz[len] = '\0';
1419       str = nullz;
1420       break;
1421     default:
1422       break;
1423   }
1424
1425   switch (upb_fielddef_type(f)) {
1426     case UPB_TYPE_INT32: {
1427       long val = strtol(str, &end, 0);
1428       if (val > INT32_MAX || val < INT32_MIN || errno == ERANGE || *end) {
1429         goto invalid;
1430       }
1431       f->defaultval.sint = val;
1432       break;
1433     }
1434     case UPB_TYPE_ENUM: {
1435       const upb_enumdef *e = f->sub.enumdef;
1436       int32_t val;
1437       if (!upb_enumdef_ntoi(e, str, len, &val)) {
1438         goto invalid;
1439       }
1440       f->defaultval.sint = val;
1441       break;
1442     }
1443     case UPB_TYPE_INT64: {
1444       long long val = strtoll(str, &end, 0);
1445       if (val > INT64_MAX || val < INT64_MIN || errno == ERANGE || *end) {
1446         goto invalid;
1447       }
1448       f->defaultval.sint = val;
1449       break;
1450     }
1451     case UPB_TYPE_UINT32: {
1452       unsigned long val = strtoul(str, &end, 0);
1453       if (val > UINT32_MAX || errno == ERANGE || *end) {
1454         goto invalid;
1455       }
1456       f->defaultval.uint = val;
1457       break;
1458     }
1459     case UPB_TYPE_UINT64: {
1460       unsigned long long val = strtoull(str, &end, 0);
1461       if (val > UINT64_MAX || errno == ERANGE || *end) {
1462         goto invalid;
1463       }
1464       f->defaultval.uint = val;
1465       break;
1466     }
1467     case UPB_TYPE_DOUBLE: {
1468       double val = strtod(str, &end);
1469       if (errno == ERANGE || *end) {
1470         goto invalid;
1471       }
1472       f->defaultval.dbl = val;
1473       break;
1474     }
1475     case UPB_TYPE_FLOAT: {
1476       float val = strtof(str, &end);
1477       if (errno == ERANGE || *end) {
1478         goto invalid;
1479       }
1480       f->defaultval.flt = val;
1481       break;
1482     }
1483     case UPB_TYPE_BOOL: {
1484       if (streql2(str, len, "false")) {
1485         f->defaultval.boolean = false;
1486       } else if (streql2(str, len, "true")) {
1487         f->defaultval.boolean = true;
1488       } else {
1489       }
1490       break;
1491     }
1492     case UPB_TYPE_STRING:
1493       f->defaultval.str = newstr(ctx, str, len);
1494       break;
1495     case UPB_TYPE_BYTES:
1496       /* XXX: need to interpret the C-escaped value. */
1497       f->defaultval.str = newstr(ctx, str, len);
1498       break;
1499     case UPB_TYPE_MESSAGE:
1500       /* Should not have a default value. */
1501       symtab_errf(ctx, "Message should not have a default (%s)",
1502                   upb_fielddef_fullname(f));
1503   }
1504
1505   return;
1506
1507 invalid:
1508   symtab_errf(ctx, "Invalid default '%.*s' for field %s", (int)len, str,
1509               upb_fielddef_fullname(f));
1510 }
1511
1512 static void set_default_default(symtab_addctx *ctx, upb_fielddef *f) {
1513   switch (upb_fielddef_type(f)) {
1514     case UPB_TYPE_INT32:
1515     case UPB_TYPE_INT64:
1516     case UPB_TYPE_ENUM:
1517       f->defaultval.sint = 0;
1518       break;
1519     case UPB_TYPE_UINT64:
1520     case UPB_TYPE_UINT32:
1521       f->defaultval.uint = 0;
1522       break;
1523     case UPB_TYPE_DOUBLE:
1524     case UPB_TYPE_FLOAT:
1525       f->defaultval.dbl = 0;
1526       break;
1527     case UPB_TYPE_STRING:
1528     case UPB_TYPE_BYTES:
1529       f->defaultval.str = newstr(ctx, NULL, 0);
1530       break;
1531     case UPB_TYPE_BOOL:
1532       f->defaultval.boolean = false;
1533       break;
1534     case UPB_TYPE_MESSAGE:
1535       break;
1536   }
1537 }
1538
1539 static void create_fielddef(
1540     symtab_addctx *ctx, const char *prefix, upb_msgdef *m,
1541     const google_protobuf_FieldDescriptorProto *field_proto) {
1542   upb_fielddef *f;
1543   const google_protobuf_FieldOptions *options;
1544   upb_strview name;
1545   const char *full_name;
1546   const char *json_name;
1547   const char *shortname;
1548   uint32_t field_number;
1549
1550   if (!google_protobuf_FieldDescriptorProto_has_name(field_proto)) {
1551     symtab_errf(ctx, "field has no name (%s)", upb_msgdef_fullname(m));
1552   }
1553
1554   name = google_protobuf_FieldDescriptorProto_name(field_proto);
1555   check_ident(ctx, name, false);
1556   full_name = makefullname(ctx, prefix, name);
1557   shortname = shortdefname(full_name);
1558
1559   if (google_protobuf_FieldDescriptorProto_has_json_name(field_proto)) {
1560     json_name = strviewdup(
1561         ctx, google_protobuf_FieldDescriptorProto_json_name(field_proto));
1562   } else {
1563     json_name = makejsonname(ctx, shortname);
1564   }
1565
1566   field_number = google_protobuf_FieldDescriptorProto_number(field_proto);
1567
1568   if (field_number == 0 || field_number > UPB_MAX_FIELDNUMBER) {
1569     symtab_errf(ctx, "invalid field number (%u)", field_number);
1570   }
1571
1572   if (m) {
1573     /* direct message field. */
1574     upb_value v, field_v, json_v;
1575     size_t json_size;
1576
1577     f = (upb_fielddef*)&m->fields[m->field_count];
1578     f->index_ = m->field_count++;
1579     f->msgdef = m;
1580     f->is_extension_ = false;
1581
1582     if (upb_strtable_lookup(&m->ntof, shortname, NULL)) {
1583       symtab_errf(ctx, "duplicate field name (%s)", shortname);
1584     }
1585
1586     if (upb_strtable_lookup(&m->ntof, json_name, NULL)) {
1587       symtab_errf(ctx, "duplicate json_name (%s)", json_name);
1588     }
1589
1590     if (upb_inttable_lookup(&m->itof, field_number, NULL)) {
1591       symtab_errf(ctx, "duplicate field number (%u)", field_number);
1592     }
1593
1594     field_v = pack_def(f, UPB_DEFTYPE_FIELD);
1595     json_v = pack_def(f, UPB_DEFTYPE_FIELD_JSONNAME);
1596     v = upb_value_constptr(f);
1597     json_size = strlen(json_name);
1598
1599     CHK_OOM(upb_strtable_insert(&m->ntof, name.data, name.size, field_v,
1600                                 ctx->arena));
1601     CHK_OOM(upb_inttable_insert(&m->itof, field_number, v, ctx->arena));
1602
1603     if (strcmp(shortname, json_name) != 0) {
1604       upb_strtable_insert(&m->ntof, json_name, json_size, json_v, ctx->arena);
1605     }
1606
1607     if (ctx->layouts) {
1608       const upb_msglayout_field *fields = m->layout->fields;
1609       int count = m->layout->field_count;
1610       bool found = false;
1611       int i;
1612       for (i = 0; i < count; i++) {
1613         if (fields[i].number == field_number) {
1614           f->layout_index = i;
1615           found = true;
1616           break;
1617         }
1618       }
1619       UPB_ASSERT(found);
1620     }
1621   } else {
1622     /* extension field. */
1623     f = (upb_fielddef*)&ctx->file->exts[ctx->file->ext_count++];
1624     f->is_extension_ = true;
1625     symtab_add(ctx, full_name, pack_def(f, UPB_DEFTYPE_FIELD));
1626   }
1627
1628   f->full_name = full_name;
1629   f->json_name = json_name;
1630   f->file = ctx->file;
1631   f->type_ = (int)google_protobuf_FieldDescriptorProto_type(field_proto);
1632   f->label_ = (int)google_protobuf_FieldDescriptorProto_label(field_proto);
1633   f->number_ = field_number;
1634   f->oneof = NULL;
1635   f->proto3_optional_ =
1636       google_protobuf_FieldDescriptorProto_proto3_optional(field_proto);
1637
1638   /* We can't resolve the subdef or (in the case of extensions) the containing
1639    * message yet, because it may not have been defined yet.  We stash a pointer
1640    * to the field_proto until later when we can properly resolve it. */
1641   f->sub.unresolved = field_proto;
1642
1643   if (f->label_ == UPB_LABEL_REQUIRED && f->file->syntax == UPB_SYNTAX_PROTO3) {
1644     symtab_errf(ctx, "proto3 fields cannot be required (%s)", f->full_name);
1645   }
1646
1647   if (google_protobuf_FieldDescriptorProto_has_oneof_index(field_proto)) {
1648     int oneof_index =
1649         google_protobuf_FieldDescriptorProto_oneof_index(field_proto);
1650     upb_oneofdef *oneof;
1651     upb_value v = upb_value_constptr(f);
1652
1653     if (upb_fielddef_label(f) != UPB_LABEL_OPTIONAL) {
1654       symtab_errf(ctx, "fields in oneof must have OPTIONAL label (%s)",
1655                   f->full_name);
1656     }
1657
1658     if (!m) {
1659       symtab_errf(ctx, "oneof_index provided for extension field (%s)",
1660                   f->full_name);
1661     }
1662
1663     if (oneof_index >= m->oneof_count) {
1664       symtab_errf(ctx, "oneof_index out of range (%s)", f->full_name);
1665     }
1666
1667     oneof = (upb_oneofdef *)&m->oneofs[oneof_index];
1668     f->oneof = oneof;
1669
1670     oneof->field_count++;
1671     if (f->proto3_optional_) {
1672       oneof->synthetic = true;
1673     }
1674     CHK_OOM(upb_inttable_insert(&oneof->itof, f->number_, v, ctx->arena));
1675     CHK_OOM(
1676         upb_strtable_insert(&oneof->ntof, name.data, name.size, v, ctx->arena));
1677   } else {
1678     f->oneof = NULL;
1679     if (f->proto3_optional_) {
1680       symtab_errf(ctx, "field with proto3_optional was not in a oneof (%s)",
1681                   f->full_name);
1682     }
1683   }
1684
1685   options = google_protobuf_FieldDescriptorProto_has_options(field_proto) ?
1686     google_protobuf_FieldDescriptorProto_options(field_proto) : NULL;
1687
1688   if (options && google_protobuf_FieldOptions_has_packed(options)) {
1689     f->packed_ = google_protobuf_FieldOptions_packed(options);
1690   } else {
1691     /* Repeated fields default to packed for proto3 only. */
1692     f->packed_ = upb_fielddef_isprimitive(f) &&
1693         f->label_ == UPB_LABEL_REPEATED && f->file->syntax == UPB_SYNTAX_PROTO3;
1694   }
1695
1696   if (options) {
1697     f->lazy_ = google_protobuf_FieldOptions_lazy(options);
1698   } else {
1699     f->lazy_ = false;
1700   }
1701 }
1702
1703 static void create_enumdef(
1704     symtab_addctx *ctx, const char *prefix,
1705     const google_protobuf_EnumDescriptorProto *enum_proto) {
1706   upb_enumdef *e;
1707   const google_protobuf_EnumValueDescriptorProto *const *values;
1708   upb_strview name;
1709   size_t i, n;
1710
1711   name = google_protobuf_EnumDescriptorProto_name(enum_proto);
1712   check_ident(ctx, name, false);
1713
1714   e = (upb_enumdef*)&ctx->file->enums[ctx->file->enum_count++];
1715   e->full_name = makefullname(ctx, prefix, name);
1716   symtab_add(ctx, e->full_name, pack_def(e, UPB_DEFTYPE_ENUM));
1717
1718   values = google_protobuf_EnumDescriptorProto_value(enum_proto, &n);
1719   CHK_OOM(upb_strtable_init(&e->ntoi, n, ctx->arena));
1720   CHK_OOM(upb_inttable_init(&e->iton, ctx->arena));
1721
1722   e->file = ctx->file;
1723   e->defaultval = 0;
1724
1725   if (n == 0) {
1726     symtab_errf(ctx, "enums must contain at least one value (%s)",
1727                 e->full_name);
1728   }
1729
1730   for (i = 0; i < n; i++) {
1731     const google_protobuf_EnumValueDescriptorProto *value = values[i];
1732     upb_strview name = google_protobuf_EnumValueDescriptorProto_name(value);
1733     char *name2 = strviewdup(ctx, name);
1734     int32_t num = google_protobuf_EnumValueDescriptorProto_number(value);
1735     upb_value v = upb_value_int32(num);
1736
1737     if (i == 0 && e->file->syntax == UPB_SYNTAX_PROTO3 && num != 0) {
1738       symtab_errf(ctx, "for proto3, the first enum value must be zero (%s)",
1739                   e->full_name);
1740     }
1741
1742     if (upb_strtable_lookup(&e->ntoi, name2, NULL)) {
1743       symtab_errf(ctx, "duplicate enum label '%s'", name2);
1744     }
1745
1746     CHK_OOM(name2)
1747     CHK_OOM(upb_strtable_insert(&e->ntoi, name2, strlen(name2), v, ctx->arena));
1748
1749     if (!upb_inttable_lookup(&e->iton, num, NULL)) {
1750       upb_value v = upb_value_cstr(name2);
1751       CHK_OOM(upb_inttable_insert(&e->iton, num, v, ctx->arena));
1752     }
1753   }
1754
1755   upb_inttable_compact(&e->iton, ctx->arena);
1756 }
1757
1758 static void create_msgdef(symtab_addctx *ctx, const char *prefix,
1759                           const google_protobuf_DescriptorProto *msg_proto) {
1760   upb_msgdef *m;
1761   const google_protobuf_MessageOptions *options;
1762   const google_protobuf_OneofDescriptorProto *const *oneofs;
1763   const google_protobuf_FieldDescriptorProto *const *fields;
1764   const google_protobuf_EnumDescriptorProto *const *enums;
1765   const google_protobuf_DescriptorProto *const *msgs;
1766   size_t i, n_oneof, n_field, n;
1767   upb_strview name;
1768
1769   name = google_protobuf_DescriptorProto_name(msg_proto);
1770   check_ident(ctx, name, false);
1771
1772   m = (upb_msgdef*)&ctx->file->msgs[ctx->file->msg_count++];
1773   m->full_name = makefullname(ctx, prefix, name);
1774   symtab_add(ctx, m->full_name, pack_def(m, UPB_DEFTYPE_MSG));
1775
1776   oneofs = google_protobuf_DescriptorProto_oneof_decl(msg_proto, &n_oneof);
1777   fields = google_protobuf_DescriptorProto_field(msg_proto, &n_field);
1778
1779   CHK_OOM(upb_inttable_init(&m->itof, ctx->arena));
1780   CHK_OOM(upb_strtable_init(&m->ntof, n_oneof + n_field, ctx->arena));
1781
1782   m->file = ctx->file;
1783   m->map_entry = false;
1784
1785   options = google_protobuf_DescriptorProto_options(msg_proto);
1786
1787   if (options) {
1788     m->map_entry = google_protobuf_MessageOptions_map_entry(options);
1789   }
1790
1791   if (ctx->layouts) {
1792     m->layout = *ctx->layouts;
1793     ctx->layouts++;
1794   } else {
1795     /* Allocate now (to allow cross-linking), populate later. */
1796     m->layout = symtab_alloc(
1797         ctx, sizeof(*m->layout) + sizeof(_upb_fasttable_entry));
1798   }
1799
1800   m->oneof_count = 0;
1801   m->oneofs = symtab_alloc(ctx, sizeof(*m->oneofs) * n_oneof);
1802   for (i = 0; i < n_oneof; i++) {
1803     create_oneofdef(ctx, m, oneofs[i]);
1804   }
1805
1806   m->field_count = 0;
1807   m->fields = symtab_alloc(ctx, sizeof(*m->fields) * n_field);
1808   for (i = 0; i < n_field; i++) {
1809     create_fielddef(ctx, m->full_name, m, fields[i]);
1810   }
1811
1812   finalize_oneofs(ctx, m);
1813   assign_msg_wellknowntype(m);
1814   upb_inttable_compact(&m->itof, ctx->arena);
1815
1816   /* This message is built.  Now build nested messages and enums. */
1817
1818   enums = google_protobuf_DescriptorProto_enum_type(msg_proto, &n);
1819   for (i = 0; i < n; i++) {
1820     create_enumdef(ctx, m->full_name, enums[i]);
1821   }
1822
1823   msgs = google_protobuf_DescriptorProto_nested_type(msg_proto, &n);
1824   for (i = 0; i < n; i++) {
1825     create_msgdef(ctx, m->full_name, msgs[i]);
1826   }
1827 }
1828
1829 static void count_types_in_msg(const google_protobuf_DescriptorProto *msg_proto,
1830                                upb_filedef *file) {
1831   const google_protobuf_DescriptorProto *const *msgs;
1832   size_t i, n;
1833
1834   file->msg_count++;
1835
1836   msgs = google_protobuf_DescriptorProto_nested_type(msg_proto, &n);
1837   for (i = 0; i < n; i++) {
1838     count_types_in_msg(msgs[i], file);
1839   }
1840
1841   google_protobuf_DescriptorProto_enum_type(msg_proto, &n);
1842   file->enum_count += n;
1843
1844   google_protobuf_DescriptorProto_extension(msg_proto, &n);
1845   file->ext_count += n;
1846 }
1847
1848 static void count_types_in_file(
1849     const google_protobuf_FileDescriptorProto *file_proto,
1850     upb_filedef *file) {
1851   const google_protobuf_DescriptorProto *const *msgs;
1852   size_t i, n;
1853
1854   msgs = google_protobuf_FileDescriptorProto_message_type(file_proto, &n);
1855   for (i = 0; i < n; i++) {
1856     count_types_in_msg(msgs[i], file);
1857   }
1858
1859   google_protobuf_FileDescriptorProto_enum_type(file_proto, &n);
1860   file->enum_count += n;
1861
1862   google_protobuf_FileDescriptorProto_extension(file_proto, &n);
1863   file->ext_count += n;
1864 }
1865
1866 static void resolve_fielddef(symtab_addctx *ctx, const char *prefix,
1867                              upb_fielddef *f) {
1868   upb_strview name;
1869   const google_protobuf_FieldDescriptorProto *field_proto = f->sub.unresolved;
1870
1871   if (f->is_extension_) {
1872     if (!google_protobuf_FieldDescriptorProto_has_extendee(field_proto)) {
1873       symtab_errf(ctx, "extension for field '%s' had no extendee",
1874                   f->full_name);
1875     }
1876
1877     name = google_protobuf_FieldDescriptorProto_extendee(field_proto);
1878     f->msgdef = symtab_resolve(ctx, f, prefix, name, UPB_DEFTYPE_MSG);
1879   }
1880
1881   if ((upb_fielddef_issubmsg(f) || f->type_ == UPB_DESCRIPTOR_TYPE_ENUM) &&
1882       !google_protobuf_FieldDescriptorProto_has_type_name(field_proto)) {
1883     symtab_errf(ctx, "field '%s' is missing type name", f->full_name);
1884   }
1885
1886   name = google_protobuf_FieldDescriptorProto_type_name(field_proto);
1887
1888   if (upb_fielddef_issubmsg(f)) {
1889     f->sub.msgdef = symtab_resolve(ctx, f, prefix, name, UPB_DEFTYPE_MSG);
1890   } else if (f->type_ == UPB_DESCRIPTOR_TYPE_ENUM) {
1891     f->sub.enumdef = symtab_resolve(ctx, f, prefix, name, UPB_DEFTYPE_ENUM);
1892   }
1893
1894   /* Have to delay resolving of the default value until now because of the enum
1895    * case, since enum defaults are specified with a label. */
1896   if (google_protobuf_FieldDescriptorProto_has_default_value(field_proto)) {
1897     upb_strview defaultval =
1898         google_protobuf_FieldDescriptorProto_default_value(field_proto);
1899
1900     if (f->file->syntax == UPB_SYNTAX_PROTO3) {
1901       symtab_errf(ctx, "proto3 fields cannot have explicit defaults (%s)",
1902                   f->full_name);
1903     }
1904
1905     if (upb_fielddef_issubmsg(f)) {
1906       symtab_errf(ctx, "message fields cannot have explicit defaults (%s)",
1907                   f->full_name);
1908     }
1909
1910     parse_default(ctx, defaultval.data, defaultval.size, f);
1911   } else {
1912     set_default_default(ctx, f);
1913   }
1914 }
1915
1916 static void build_filedef(
1917     symtab_addctx *ctx, upb_filedef *file,
1918     const google_protobuf_FileDescriptorProto *file_proto) {
1919   const google_protobuf_FileOptions *file_options_proto;
1920   const google_protobuf_DescriptorProto *const *msgs;
1921   const google_protobuf_EnumDescriptorProto *const *enums;
1922   const google_protobuf_FieldDescriptorProto *const *exts;
1923   const upb_strview* strs;
1924   size_t i, n;
1925
1926   file->symtab = ctx->symtab;
1927
1928   /* One pass to count and allocate. */
1929   file->msg_count = 0;
1930   file->enum_count = 0;
1931   file->ext_count = 0;
1932   count_types_in_file(file_proto, file);
1933   file->msgs = symtab_alloc(ctx, sizeof(*file->msgs) * file->msg_count);
1934   file->enums = symtab_alloc(ctx, sizeof(*file->enums) * file->enum_count);
1935   file->exts = symtab_alloc(ctx, sizeof(*file->exts) * file->ext_count);
1936
1937   /* In the second pass we increment these as defs are added. */
1938   file->msg_count = 0;
1939   file->enum_count = 0;
1940   file->ext_count = 0;
1941
1942   if (!google_protobuf_FileDescriptorProto_has_name(file_proto)) {
1943     symtab_errf(ctx, "File has no name");
1944   }
1945
1946   file->name =
1947       strviewdup(ctx, google_protobuf_FileDescriptorProto_name(file_proto));
1948   file->phpprefix = NULL;
1949   file->phpnamespace = NULL;
1950
1951   if (google_protobuf_FileDescriptorProto_has_package(file_proto)) {
1952     upb_strview package =
1953         google_protobuf_FileDescriptorProto_package(file_proto);
1954     check_ident(ctx, package, true);
1955     file->package = strviewdup(ctx, package);
1956   } else {
1957     file->package = NULL;
1958   }
1959
1960   if (google_protobuf_FileDescriptorProto_has_syntax(file_proto)) {
1961     upb_strview syntax =
1962         google_protobuf_FileDescriptorProto_syntax(file_proto);
1963
1964     if (streql_view(syntax, "proto2")) {
1965       file->syntax = UPB_SYNTAX_PROTO2;
1966     } else if (streql_view(syntax, "proto3")) {
1967       file->syntax = UPB_SYNTAX_PROTO3;
1968     } else {
1969       symtab_errf(ctx, "Invalid syntax '" UPB_STRVIEW_FORMAT "'",
1970                   UPB_STRVIEW_ARGS(syntax));
1971     }
1972   } else {
1973     file->syntax = UPB_SYNTAX_PROTO2;
1974   }
1975
1976   /* Read options. */
1977   file_options_proto = google_protobuf_FileDescriptorProto_options(file_proto);
1978   if (file_options_proto) {
1979     if (google_protobuf_FileOptions_has_php_class_prefix(file_options_proto)) {
1980       file->phpprefix = strviewdup(
1981           ctx,
1982           google_protobuf_FileOptions_php_class_prefix(file_options_proto));
1983     }
1984     if (google_protobuf_FileOptions_has_php_namespace(file_options_proto)) {
1985       file->phpnamespace = strviewdup(
1986           ctx, google_protobuf_FileOptions_php_namespace(file_options_proto));
1987     }
1988   }
1989
1990   /* Verify dependencies. */
1991   strs = google_protobuf_FileDescriptorProto_dependency(file_proto, &n);
1992   file->deps = symtab_alloc(ctx, sizeof(*file->deps) * n);
1993
1994   for (i = 0; i < n; i++) {
1995     upb_strview dep_name = strs[i];
1996     upb_value v;
1997     if (!upb_strtable_lookup2(&ctx->symtab->files, dep_name.data,
1998                               dep_name.size, &v)) {
1999       symtab_errf(ctx,
2000                   "Depends on file '" UPB_STRVIEW_FORMAT
2001                   "', but it has not been loaded",
2002                   UPB_STRVIEW_ARGS(dep_name));
2003     }
2004     file->deps[i] = upb_value_getconstptr(v);
2005   }
2006
2007   /* Create messages. */
2008   msgs = google_protobuf_FileDescriptorProto_message_type(file_proto, &n);
2009   for (i = 0; i < n; i++) {
2010     create_msgdef(ctx, file->package, msgs[i]);
2011   }
2012
2013   /* Create enums. */
2014   enums = google_protobuf_FileDescriptorProto_enum_type(file_proto, &n);
2015   for (i = 0; i < n; i++) {
2016     create_enumdef(ctx, file->package, enums[i]);
2017   }
2018
2019   /* Create extensions. */
2020   exts = google_protobuf_FileDescriptorProto_extension(file_proto, &n);
2021   file->exts = symtab_alloc(ctx, sizeof(*file->exts) * n);
2022   for (i = 0; i < n; i++) {
2023     create_fielddef(ctx, file->package, NULL, exts[i]);
2024   }
2025
2026   /* Now that all names are in the table, build layouts and resolve refs. */
2027   for (i = 0; i < (size_t)file->ext_count; i++) {
2028     resolve_fielddef(ctx, file->package, (upb_fielddef*)&file->exts[i]);
2029   }
2030
2031   for (i = 0; i < (size_t)file->msg_count; i++) {
2032     const upb_msgdef *m = &file->msgs[i];
2033     int j;
2034     for (j = 0; j < m->field_count; j++) {
2035       resolve_fielddef(ctx, m->full_name, (upb_fielddef*)&m->fields[j]);
2036     }
2037   }
2038
2039   if (!ctx->layouts) {
2040     for (i = 0; i < (size_t)file->msg_count; i++) {
2041       const upb_msgdef *m = &file->msgs[i];
2042       make_layout(ctx, m);
2043     }
2044   }
2045 }
2046
2047 static void remove_filedef(upb_symtab *s, upb_filedef *file) {
2048   int i;
2049   for (i = 0; i < file->msg_count; i++) {
2050     const char *name = file->msgs[i].full_name;
2051     upb_strtable_remove(&s->syms, name, strlen(name), NULL);
2052   }
2053   for (i = 0; i < file->enum_count; i++) {
2054     const char *name = file->enums[i].full_name;
2055     upb_strtable_remove(&s->syms, name, strlen(name), NULL);
2056   }
2057   for (i = 0; i < file->ext_count; i++) {
2058     const char *name = file->exts[i].full_name;
2059     upb_strtable_remove(&s->syms, name, strlen(name), NULL);
2060   }
2061 }
2062
2063 static const upb_filedef *_upb_symtab_addfile(
2064     upb_symtab *s, const google_protobuf_FileDescriptorProto *file_proto,
2065     const upb_msglayout **layouts, upb_status *status) {
2066   symtab_addctx ctx;
2067   upb_strview name = google_protobuf_FileDescriptorProto_name(file_proto);
2068
2069   if (upb_strtable_lookup2(&s->files, name.data, name.size, NULL)) {
2070     upb_status_seterrf(status, "duplicate file name (%.*s)",
2071                        UPB_STRVIEW_ARGS(name));
2072     return NULL;
2073   }
2074
2075   ctx.symtab = s;
2076   ctx.layouts = layouts;
2077   ctx.status = status;
2078   ctx.file = NULL;
2079   ctx.arena = upb_arena_new();
2080
2081   if (!ctx.arena) {
2082     upb_status_setoom(status);
2083     return NULL;
2084   }
2085
2086   if (UPB_UNLIKELY(UPB_SETJMP(ctx.err))) {
2087     UPB_ASSERT(!upb_ok(status));
2088     if (ctx.file) {
2089       remove_filedef(s, ctx.file);
2090       ctx.file = NULL;
2091     }
2092   } else {
2093     ctx.file = symtab_alloc(&ctx, sizeof(*ctx.file));
2094     build_filedef(&ctx, ctx.file, file_proto);
2095     upb_strtable_insert(&s->files, name.data, name.size,
2096                         upb_value_constptr(ctx.file), ctx.arena);
2097     UPB_ASSERT(upb_ok(status));
2098     upb_arena_fuse(s->arena, ctx.arena);
2099   }
2100
2101   upb_arena_free(ctx.arena);
2102   return ctx.file;
2103 }
2104
2105 const upb_filedef *upb_symtab_addfile(
2106     upb_symtab *s, const google_protobuf_FileDescriptorProto *file_proto,
2107     upb_status *status) {
2108   return _upb_symtab_addfile(s, file_proto, NULL, status);
2109 }
2110
2111 /* Include here since we want most of this file to be stdio-free. */
2112 #include <stdio.h>
2113
2114 bool _upb_symtab_loaddefinit(upb_symtab *s, const upb_def_init *init) {
2115   /* Since this function should never fail (it would indicate a bug in upb) we
2116    * print errors to stderr instead of returning error status to the user. */
2117   upb_def_init **deps = init->deps;
2118   google_protobuf_FileDescriptorProto *file;
2119   upb_arena *arena;
2120   upb_status status;
2121
2122   upb_status_clear(&status);
2123
2124   if (upb_strtable_lookup(&s->files, init->filename, NULL)) {
2125     return true;
2126   }
2127
2128   arena = upb_arena_new();
2129
2130   for (; *deps; deps++) {
2131     if (!_upb_symtab_loaddefinit(s, *deps)) goto err;
2132   }
2133
2134   file = google_protobuf_FileDescriptorProto_parse_ex(
2135       init->descriptor.data, init->descriptor.size, NULL, UPB_DECODE_ALIAS,
2136       arena);
2137   s->bytes_loaded += init->descriptor.size;
2138
2139   if (!file) {
2140     upb_status_seterrf(
2141         &status,
2142         "Failed to parse compiled-in descriptor for file '%s'. This should "
2143         "never happen.",
2144         init->filename);
2145     goto err;
2146   }
2147
2148   if (!_upb_symtab_addfile(s, file, init->layouts, &status)) goto err;
2149
2150   upb_arena_free(arena);
2151   return true;
2152
2153 err:
2154   fprintf(stderr, "Error loading compiled-in descriptor: %s\n",
2155           upb_status_errmsg(&status));
2156   upb_arena_free(arena);
2157   return false;
2158 }
2159
2160 size_t _upb_symtab_bytesloaded(const upb_symtab *s) {
2161   return s->bytes_loaded;
2162 }
2163
2164 upb_arena *_upb_symtab_arena(const upb_symtab *s) {
2165   return s->arena;
2166 }
2167
2168 #undef CHK_OOM