From 919fea438a5ac5366684cfa26d2bb3d17519cb60 Mon Sep 17 00:00:00 2001 From: Josh Haberman Date: Mon, 18 May 2015 10:55:20 -0700 Subject: Ported upb to C89, for greater portability. A large part of this change contains surface-level porting, like moving variable declarations to the top of the block. However there are a few more substantial things too: - moved internal-only struct definitions to a separate file (structdefs.int.h), for greater encapsulation and ABI compatibility. - removed the UPB_UPCAST macro, since it requires access to the internal-only struct definitions. Replaced uses with calls to inline, type-safe casting functions. - removed the UPB_DEFINE_CLASS/UPB_DEFINE_STRUCT macros. Class and struct definitions are now more explicit -- you get to see the actual class/struct keywords in the source. The casting convenience functions have been moved into UPB_DECLARE_DERIVED_TYPE() and UPB_DECLARE_DERIVED_TYPE2(). - the new way that we duplicate base methods in derived types is also more convenient and requires less duplication. It is also less greppable, but hopefully that is not too big a problem. Compiler flags (-std=c89 -pedantic) should help to rigorously enforce that the code is free of C99-isms. A few functions are not available in C89 (strtoll). There are temporary, hacky solutions in place. --- upb/symtab.c | 214 +++++++++++++++++++++++++++++------------------------------ 1 file changed, 107 insertions(+), 107 deletions(-) (limited to 'upb/symtab.c') diff --git a/upb/symtab.c b/upb/symtab.c index 817a581..6e6b6b8 100644 --- a/upb/symtab.c +++ b/upb/symtab.c @@ -5,32 +5,12 @@ * Author: Josh Haberman */ +#include "upb/structdefs.int.h" #include "upb/symtab.h" #include #include -bool upb_symtab_isfrozen(const upb_symtab *s) { - return upb_refcounted_isfrozen(UPB_UPCAST(s)); -} - -void upb_symtab_ref(const upb_symtab *s, const void *owner) { - upb_refcounted_ref(UPB_UPCAST(s), owner); -} - -void upb_symtab_unref(const upb_symtab *s, const void *owner) { - upb_refcounted_unref(UPB_UPCAST(s), owner); -} - -void upb_symtab_donateref( - const upb_symtab *s, const void *from, const void *to) { - upb_refcounted_donateref(UPB_UPCAST(s), from, to); -} - -void upb_symtab_checkref(const upb_symtab *s, const void *owner) { - upb_refcounted_checkref(UPB_UPCAST(s), owner); -} - static void upb_symtab_free(upb_refcounted *r) { upb_symtab *s = (upb_symtab*)r; upb_strtable_iter i; @@ -47,18 +27,21 @@ static void upb_symtab_free(upb_refcounted *r) { upb_symtab *upb_symtab_new(const void *owner) { static const struct upb_refcounted_vtbl vtbl = {NULL, &upb_symtab_free}; upb_symtab *s = malloc(sizeof(*s)); - upb_refcounted_init(UPB_UPCAST(s), &vtbl, owner); + upb_refcounted_init(upb_symtab_upcast_mutable(s), &vtbl, owner); upb_strtable_init(&s->symtab, UPB_CTYPE_PTR); return s; } void upb_symtab_freeze(upb_symtab *s) { + upb_refcounted *r; + bool ok; + assert(!upb_symtab_isfrozen(s)); - upb_refcounted *r = UPB_UPCAST(s); - // The symtab does not take ref2's (see refcounted.h) on the defs, because - // defs cannot refer back to the table and therefore cannot create cycles. So - // 0 will suffice for maxdepth here. - bool ok = upb_refcounted_freeze(&r, 1, NULL, 0); + r = upb_symtab_upcast_mutable(s); + /* The symtab does not take ref2's (see refcounted.h) on the defs, because + * defs cannot refer back to the table and therefore cannot create cycles. So + * 0 will suffice for maxdepth here. */ + ok = upb_refcounted_freeze(&r, 1, NULL, 0); UPB_ASSERT_VAR(ok, ok); } @@ -83,19 +66,19 @@ const upb_enumdef *upb_symtab_lookupenum(const upb_symtab *s, const char *sym) { return def ? upb_dyncast_enumdef(def) : NULL; } -// Given a symbol and the base symbol inside which it is defined, find the -// symbol's definition in t. +/* Given a symbol and the base symbol inside which it is defined, find the + * symbol's definition in t. */ static upb_def *upb_resolvename(const upb_strtable *t, const char *base, const char *sym) { if(strlen(sym) == 0) return NULL; if(sym[0] == '.') { - // Symbols starting with '.' are absolute, so we do a single lookup. - // Slice to omit the leading '.' + /* Symbols starting with '.' are absolute, so we do a single lookup. + * Slice to omit the leading '.' */ upb_value v; return upb_strtable_lookup(t, sym + 1, &v) ? upb_value_getptr(v) : NULL; } else { - // Remove components from base until we find an entry or run out. - // TODO: This branch is totally broken, but currently not used. + /* Remove components from base until we find an entry or run out. + * TODO: This branch is totally broken, but currently not used. */ (void)base; assert(false); return NULL; @@ -108,36 +91,41 @@ const upb_def *upb_symtab_resolve(const upb_symtab *s, const char *base, return ret; } -// Searches def and its children to find defs that have the same name as any -// def in "addtab." Returns true if any where found, and as a side-effect adds -// duplicates of these defs into addtab. -// -// We use a modified depth-first traversal that traverses each SCC (which we -// already computed) as if it were a single node. This allows us to traverse -// the possibly-cyclic graph as if it were a DAG and to dup the correct set of -// nodes with O(n) time. +/* Searches def and its children to find defs that have the same name as any + * def in "addtab." Returns true if any where found, and as a side-effect adds + * duplicates of these defs into addtab. + * + * We use a modified depth-first traversal that traverses each SCC (which we + * already computed) as if it were a single node. This allows us to traverse + * the possibly-cyclic graph as if it were a DAG and to dup the correct set of + * nodes with O(n) time. */ static bool upb_resolve_dfs(const upb_def *def, upb_strtable *addtab, const void *new_owner, upb_inttable *seen, upb_status *s) { - // Memoize results of this function for efficiency (since we're traversing a - // DAG this is not needed to limit the depth of the search). + /* Memoize results of this function for efficiency (since we're traversing a + * DAG this is not needed to limit the depth of the search). */ upb_value v; + bool need_dup; + const upb_def *base; + if (upb_inttable_lookup(seen, (uintptr_t)def, &v)) return upb_value_getbool(v); - // Visit submessages for all messages in the SCC. - bool need_dup = false; - const upb_def *base = def; + /* Visit submessages for all messages in the SCC. */ + need_dup = false; + base = def; do { + upb_value v; + const upb_msgdef *m; + assert(upb_def_isfrozen(def)); if (def->type == UPB_DEF_FIELD) continue; - upb_value v; if (upb_strtable_lookup(addtab, upb_def_fullname(def), &v)) { need_dup = true; } - // For messages, continue the recursion by visiting all subdefs. - const upb_msgdef *m = upb_dyncast_msgdef(def); + /* For messages, continue the recursion by visiting all subdefs. */ + m = upb_dyncast_msgdef(def); if (m) { upb_msg_field_iter i; for(upb_msg_field_begin(&i, m); @@ -145,7 +133,7 @@ static bool upb_resolve_dfs(const upb_def *def, upb_strtable *addtab, upb_msg_field_next(&i)) { upb_fielddef *f = upb_msg_iter_field(&i); if (!upb_fielddef_hassubdef(f)) continue; - // |= to avoid short-circuit; we need its side-effects. + /* |= to avoid short-circuit; we need its side-effects. */ need_dup |= upb_resolve_dfs( upb_fielddef_subdef(f), addtab, new_owner, seen, s); if (!upb_ok(s)) return false; @@ -154,11 +142,13 @@ static bool upb_resolve_dfs(const upb_def *def, upb_strtable *addtab, } while ((def = (upb_def*)def->base.next) != base); if (need_dup) { - // Dup any defs that don't already have entries in addtab. + /* Dup any defs that don't already have entries in addtab. */ def = base; do { + const char *name; + if (def->type == UPB_DEF_FIELD) continue; - const char *name = upb_def_fullname(def); + name = upb_def_fullname(def); if (!upb_strtable_lookup(addtab, name, NULL)) { upb_def *newdef = upb_def_dup(def, new_owner); if (!newdef) goto oom; @@ -177,34 +167,41 @@ oom: return false; } -// TODO(haberman): we need a lot more testing of error conditions. -// The came_from_user stuff in particular is not tested. +/* TODO(haberman): we need a lot more testing of error conditions. + * The came_from_user stuff in particular is not tested. */ bool upb_symtab_add(upb_symtab *s, upb_def *const*defs, int n, void *ref_donor, upb_status *status) { - assert(!upb_symtab_isfrozen(s)); + int i; + upb_strtable_iter iter; upb_def **add_defs = NULL; upb_strtable addtab; + upb_inttable seen; + + assert(!upb_symtab_isfrozen(s)); if (!upb_strtable_init(&addtab, UPB_CTYPE_PTR)) { upb_status_seterrmsg(status, "out of memory"); return false; } - // Add new defs to our "add" set. - for (int i = 0; i < n; i++) { + /* Add new defs to our "add" set. */ + for (i = 0; i < n; i++) { upb_def *def = defs[i]; + const char *fullname; + upb_fielddef *f; + if (upb_def_isfrozen(def)) { upb_status_seterrmsg(status, "added defs must be mutable"); goto err; } assert(!upb_def_isfrozen(def)); - const char *fullname = upb_def_fullname(def); + fullname = upb_def_fullname(def); if (!fullname) { upb_status_seterrmsg( status, "Anonymous defs cannot be added to a symtab"); goto err; } - upb_fielddef *f = upb_dyncast_fielddef_mutable(def); + f = upb_dyncast_fielddef_mutable(def); if (f) { if (!upb_fielddef_containingtypename(f)) { @@ -218,8 +215,8 @@ bool upb_symtab_add(upb_symtab *s, upb_def *const*defs, int n, void *ref_donor, upb_status_seterrf(status, "Conflicting defs named '%s'", fullname); goto err; } - // We need this to back out properly, because if there is a failure we - // need to donate the ref back to the caller. + /* We need this to back out properly, because if there is a failure we + * need to donate the ref back to the caller. */ def->came_from_user = true; upb_def_donateref(def, ref_donor, s); if (!upb_strtable_insert(&addtab, fullname, upb_value_ptr(def))) @@ -227,31 +224,33 @@ bool upb_symtab_add(upb_symtab *s, upb_def *const*defs, int n, void *ref_donor, } } - // Add standalone fielddefs (ie. extensions) to the appropriate messages. - // If the appropriate message only exists in the existing symtab, duplicate - // it so we have a mutable copy we can add the fields to. - for (int i = 0; i < n; i++) { + /* Add standalone fielddefs (ie. extensions) to the appropriate messages. + * If the appropriate message only exists in the existing symtab, duplicate + * it so we have a mutable copy we can add the fields to. */ + for (i = 0; i < n; i++) { upb_def *def = defs[i]; upb_fielddef *f = upb_dyncast_fielddef_mutable(def); + const char *msgname; + upb_value v; + upb_msgdef *m; + if (!f) continue; - const char *msgname = upb_fielddef_containingtypename(f); - // We validated this earlier in this function. + msgname = upb_fielddef_containingtypename(f); + /* We validated this earlier in this function. */ assert(msgname); - // If the extendee name is absolutely qualified, move past the initial ".". - // TODO(haberman): it is not obvious what it would mean if this was not - // absolutely qualified. + /* If the extendee name is absolutely qualified, move past the initial ".". + * TODO(haberman): it is not obvious what it would mean if this was not + * absolutely qualified. */ if (msgname[0] == '.') { msgname++; } - upb_value v; - upb_msgdef *m; if (upb_strtable_lookup(&addtab, msgname, &v)) { - // Extendee is in the set of defs the user asked us to add. + /* Extendee is in the set of defs the user asked us to add. */ m = upb_value_getptr(v); } else { - // Need to find and dup the extendee from the existing symtab. + /* Need to find and dup the extendee from the existing symtab. */ const upb_msgdef *frozen_m = upb_symtab_lookupmsg(s, msgname); if (!frozen_m) { upb_status_seterrf(status, @@ -273,37 +272,37 @@ bool upb_symtab_add(upb_symtab *s, upb_def *const*defs, int n, void *ref_donor, } } - // Add dups of any existing def that can reach a def with the same name as - // anything in our "add" set. - upb_inttable seen; + /* Add dups of any existing def that can reach a def with the same name as + * anything in our "add" set. */ if (!upb_inttable_init(&seen, UPB_CTYPE_BOOL)) goto oom_err; - upb_strtable_iter i; - upb_strtable_begin(&i, &s->symtab); - for (; !upb_strtable_done(&i); upb_strtable_next(&i)) { - upb_def *def = upb_value_getptr(upb_strtable_iter_value(&i)); + upb_strtable_begin(&iter, &s->symtab); + for (; !upb_strtable_done(&iter); upb_strtable_next(&iter)) { + upb_def *def = upb_value_getptr(upb_strtable_iter_value(&iter)); upb_resolve_dfs(def, &addtab, s, &seen, status); if (!upb_ok(status)) goto err; } upb_inttable_uninit(&seen); - // Now using the table, resolve symbolic references for subdefs. - upb_strtable_begin(&i, &addtab); - for (; !upb_strtable_done(&i); upb_strtable_next(&i)) { - upb_def *def = upb_value_getptr(upb_strtable_iter_value(&i)); + /* Now using the table, resolve symbolic references for subdefs. */ + upb_strtable_begin(&iter, &addtab); + for (; !upb_strtable_done(&iter); upb_strtable_next(&iter)) { + const char *base; + upb_def *def = upb_value_getptr(upb_strtable_iter_value(&iter)); upb_msgdef *m = upb_dyncast_msgdef_mutable(def); + upb_msg_field_iter j; + if (!m) continue; - // Type names are resolved relative to the message in which they appear. - const char *base = upb_msgdef_fullname(m); + /* Type names are resolved relative to the message in which they appear. */ + base = upb_msgdef_fullname(m); - upb_msg_field_iter j; for(upb_msg_field_begin(&j, m); !upb_msg_field_done(&j); upb_msg_field_next(&j)) { upb_fielddef *f = upb_msg_iter_field(&j); const char *name = upb_fielddef_subdefname(f); if (name && !upb_fielddef_subdef(f)) { - // Try the lookup in the current set of to-be-added defs first. If not - // there, try existing defs. + /* Try the lookup in the current set of to-be-added defs first. If not + * there, try existing defs. */ upb_def *subdef = upb_resolvename(&addtab, base, name); if (subdef == NULL) { subdef = upb_resolvename(&s->symtab, base, name); @@ -319,31 +318,33 @@ bool upb_symtab_add(upb_symtab *s, upb_def *const*defs, int n, void *ref_donor, } } - // We need an array of the defs in addtab, for passing to upb_def_freeze. + /* We need an array of the defs in addtab, for passing to upb_def_freeze. */ add_defs = malloc(sizeof(void*) * upb_strtable_count(&addtab)); if (add_defs == NULL) goto oom_err; - upb_strtable_begin(&i, &addtab); - for (n = 0; !upb_strtable_done(&i); upb_strtable_next(&i)) { - add_defs[n++] = upb_value_getptr(upb_strtable_iter_value(&i)); + upb_strtable_begin(&iter, &addtab); + for (n = 0; !upb_strtable_done(&iter); upb_strtable_next(&iter)) { + add_defs[n++] = upb_value_getptr(upb_strtable_iter_value(&iter)); } if (!upb_def_freeze(add_defs, n, status)) goto err; - // This must be delayed until all errors have been detected, since error - // recovery code uses this table to cleanup defs. + /* This must be delayed until all errors have been detected, since error + * recovery code uses this table to cleanup defs. */ upb_strtable_uninit(&addtab); - // TODO(haberman) we don't properly handle errors after this point (like - // OOM in upb_strtable_insert() below). - for (int i = 0; i < n; i++) { + /* TODO(haberman) we don't properly handle errors after this point (like + * OOM in upb_strtable_insert() below). */ + for (i = 0; i < n; i++) { upb_def *def = add_defs[i]; const char *name = upb_def_fullname(def); upb_value v; + bool success; + if (upb_strtable_remove(&s->symtab, name, &v)) { const upb_def *def = upb_value_getptr(v); upb_def_unref(def, s); } - bool success = upb_strtable_insert(&s->symtab, name, upb_value_ptr(def)); + success = upb_strtable_insert(&s->symtab, name, upb_value_ptr(def)); UPB_ASSERT_VAR(success, success == true); } free(add_defs); @@ -352,12 +353,11 @@ bool upb_symtab_add(upb_symtab *s, upb_def *const*defs, int n, void *ref_donor, oom_err: upb_status_seterrmsg(status, "out of memory"); err: { - // For defs the user passed in, we need to donate the refs back. For defs - // we dup'd, we need to just unref them. - upb_strtable_iter i; - upb_strtable_begin(&i, &addtab); - for (; !upb_strtable_done(&i); upb_strtable_next(&i)) { - upb_def *def = upb_value_getptr(upb_strtable_iter_value(&i)); + /* For defs the user passed in, we need to donate the refs back. For defs + * we dup'd, we need to just unref them. */ + upb_strtable_begin(&iter, &addtab); + for (; !upb_strtable_done(&iter); upb_strtable_next(&iter)) { + upb_def *def = upb_value_getptr(upb_strtable_iter_value(&iter)); bool came_from_user = def->came_from_user; def->came_from_user = false; if (came_from_user) { @@ -373,7 +373,7 @@ err: { return false; } -// Iteration. +/* Iteration. */ static void advance_to_matching(upb_symtab_iter *iter) { if (iter->type == UPB_DEF_ANY) -- cgit v1.2.3