diff options
-rw-r--r-- | Makefile | 7 | ||||
-rw-r--r-- | tests/test_def.c | 13 | ||||
-rw-r--r-- | upb/pb/textprinter.c | 6 | ||||
-rw-r--r-- | upb/structdefs.int.h | 2 | ||||
-rw-r--r-- | upb/symtab.c | 61 | ||||
-rw-r--r-- | upb/upb.h | 4 |
6 files changed, 68 insertions, 25 deletions
@@ -46,6 +46,7 @@ UPB_FAIL_WARNINGS?=no # We are C89/C++98, with the one exception that we need stdint and "long long." CC?=cc CXX?=c++ +AR?=ar CFLAGS= CXXFLAGS= INCLUDE=-I. @@ -221,11 +222,11 @@ endif $(UPB_PICLIBS): lib/lib%_pic.a: $(call make_objs,lo) $(E) AR $@ - $(Q) mkdir -p lib && ar rcs $@ $^ + $(Q) mkdir -p lib && $(AR) rcs $@ $^ $(UPB_LIBS): lib/lib%.a: $(call make_objs,o) $(E) AR $@ - $(Q) mkdir -p lib && ar rcs $@ $^ + $(Q) mkdir -p lib && $(AR) rcs $@ $^ obj/upb/%.o: upb/%.c | $$(@D)/. @@ -370,7 +371,7 @@ googlepbtests: googlepb $(GOOGLEPB_TESTS) lib/libupb.bindings.googlepb.a: $(upb_bindings_googlepb_SRCS:upb/%.cc=obj/upb/%.o) $(E) AR $@ - $(Q) mkdir -p lib && ar rcs $@ $^ + $(Q) mkdir -p lib && $(AR) rcs $@ $^ # Generate C++ with Google's protobuf compiler, to test and benchmark against. tests/google_messages.proto.pb: tests/google_messages.proto diff --git a/tests/test_def.c b/tests/test_def.c index 4f9fcff..c33d584 100644 --- a/tests/test_def.c +++ b/tests/test_def.c @@ -246,6 +246,18 @@ static void test_replacement() { upb_symtab_unref(s, &s); } +static void test_cycles_in_replacement() { + upb_symtab *s = upb_symtab_new(&s); + upb_msgdef *m = upb_msgdef_newnamed("M", &s); + upb_status status = UPB_STATUS_INIT; + + upb_msgdef_addfield(m, newfield("m", 1, UPB_TYPE_MESSAGE, + UPB_LABEL_OPTIONAL, ".M", &s), + &s, NULL); + ASSERT_STATUS(upb_symtab_add(s, (upb_def**)&m, 1, &s, &status), &status); + ASSERT_STATUS(upb_symtab_add(s, NULL, 0, &s, &status), &status); +} + static void test_freeze_free() { bool ok; @@ -459,6 +471,7 @@ int run_tests(int argc, char *argv[]) { test_fielddef(); test_fielddef_unref(); test_replacement(); + test_cycles_in_replacement(); test_freeze_free(); test_partial_freeze(); test_noreftracking(); diff --git a/upb/pb/textprinter.c b/upb/pb/textprinter.c index 269881b..4932468 100644 --- a/upb/pb/textprinter.c +++ b/upb/pb/textprinter.c @@ -96,10 +96,6 @@ static int putescaped(upb_textprinter *p, const char *buf, size_t len, return 0; } -#ifdef __GNUC__ -#define va_copy(a, b) __va_copy(a, b) -#endif - bool putf(upb_textprinter *p, const char *fmt, ...) { va_list args; va_list args_copy; @@ -111,7 +107,7 @@ bool putf(upb_textprinter *p, const char *fmt, ...) { va_start(args, fmt); /* Run once to get the length of the string. */ - va_copy(args_copy, args); + _upb_va_copy(args_copy, args); len = _upb_vsnprintf(NULL, 0, fmt, args_copy); va_end(args_copy); diff --git a/upb/structdefs.int.h b/upb/structdefs.int.h index 2fa2972..b3dcfa0 100644 --- a/upb/structdefs.int.h +++ b/upb/structdefs.int.h @@ -19,7 +19,7 @@ * flag. */ -#include <upb/def.h> +#include "upb/def.h" #ifndef UPB_STATICINIT_H_ #define UPB_STATICINIT_H_ diff --git a/upb/symtab.c b/upb/symtab.c index 6e6b6b8..0ce3e18 100644 --- a/upb/symtab.c +++ b/upb/symtab.c @@ -91,24 +91,48 @@ 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. +/* Starts a depth-first traversal at "def", recursing into any subdefs + * (ie. submessage types). Adds duplicates of existing defs to addtab + * wherever necessary, so that the resulting symtab will be consistent once + * addtab is added. * - * 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. */ + * More specifically, if any def D is found in the DFS that: + * + * 1. can reach a def that is being replaced by something in addtab, AND + * + * 2. is not itself being replaced already (ie. this name doesn't already + * exist in addtab) + * + * ...then a duplicate (new copy) of D will be added to addtab. + * + * Returns true if this happened for any def reachable from "def." + * + * It is slightly tricky to do this correctly in the presence of cycles. If we + * detect that our DFS has hit a cycle, we might not yet know if any SCCs on + * our stack can reach a def in addtab or not. Once we figure this out, that + * answer needs to apply to *all* defs in these SCCs, even if we visited them + * already. So a straight up one-pass cycle-detecting DFS won't work. + * + * To work around this problem, we traverse each SCC (which we already + * computed, since these defs are frozen) as a single node. We first compute + * whether the SCC as a whole can reach any def in addtab, then we dup (or not) + * the entire SCC. This requires breaking the encapsulation of upb_refcounted, + * since that is where we get the data about what SCC we are in. */ 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). */ upb_value v; bool need_dup; const upb_def *base; + const void* memoize_key; + + /* Memoize results of this function for efficiency (since we're traversing a + * DAG this is not needed to limit the depth of the search). + * + * We memoize by SCC instead of by individual def. */ + memoize_key = def->base.group; - if (upb_inttable_lookup(seen, (uintptr_t)def, &v)) + if (upb_inttable_lookupptr(seen, memoize_key, &v)) return upb_value_getbool(v); /* Visit submessages for all messages in the SCC. */ @@ -124,7 +148,8 @@ static bool upb_resolve_dfs(const upb_def *def, upb_strtable *addtab, need_dup = true; } - /* For messages, continue the recursion by visiting all subdefs. */ + /* For messages, continue the recursion by visiting all subdefs, but only + * ones in different SCCs. */ m = upb_dyncast_msgdef(def); if (m) { upb_msg_field_iter i; @@ -132,17 +157,23 @@ static bool upb_resolve_dfs(const upb_def *def, upb_strtable *addtab, !upb_msg_field_done(&i); upb_msg_field_next(&i)) { upb_fielddef *f = upb_msg_iter_field(&i); + const upb_def *subdef; + if (!upb_fielddef_hassubdef(f)) continue; + subdef = upb_fielddef_subdef(f); + + /* Skip subdefs in this SCC. */ + if (def->base.group == subdef->base.group) continue; + /* |= to avoid short-circuit; we need its side-effects. */ - need_dup |= upb_resolve_dfs( - upb_fielddef_subdef(f), addtab, new_owner, seen, s); + need_dup |= upb_resolve_dfs(subdef, addtab, new_owner, seen, s); if (!upb_ok(s)) return false; } } } while ((def = (upb_def*)def->base.next) != base); if (need_dup) { - /* Dup any defs that don't already have entries in addtab. */ + /* Dup all defs in this SCC that don't already have entries in addtab. */ def = base; do { const char *name; @@ -159,7 +190,7 @@ static bool upb_resolve_dfs(const upb_def *def, upb_strtable *addtab, } while ((def = (upb_def*)def->base.next) != base); } - upb_inttable_insert(seen, (uintptr_t)def, upb_value_bool(need_dup)); + upb_inttable_insertptr(seen, memoize_key, upb_value_bool(need_dup)); return need_dup; oom: @@ -52,12 +52,14 @@ #ifdef __GNUC__ #define _upb_snprintf __builtin_snprintf #define _upb_vsnprintf __builtin_vsnprintf +#define _upb_va_copy(a, b) __va_copy(a, b) #elif __STDC_VERSION__ >= 199901L /* C99 versions. */ #define _upb_snprintf snprintf #define _upb_vsnprintf vsnprintf +#define _upb_va_copy(a, b) va_copy(a, b) #else -#error Need implementations of [v]snprintf +#error Need implementations of [v]snprintf and va_copy #endif |