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"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY DIRECT,
20 * 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/util/required_fields.h"
29
30 #include <inttypes.h>
31 #include <stdarg.h>
32
33 #include "upb/collections/map.h"
34 #include "upb/port/vsnprintf_compat.h"
35 #include "upb/reflection/message.h"
36
37 // Must be last.
38 #include "upb/port/def.inc"
39
40 ////////////////////////////////////////////////////////////////////////////////
41 // upb_FieldPath_ToText()
42 ////////////////////////////////////////////////////////////////////////////////
43
44 typedef struct {
45 char* buf;
46 char* ptr;
47 char* end;
48 size_t overflow;
49 } upb_PrintfAppender;
50
51 UPB_PRINTF(2, 3)
upb_FieldPath_Printf(upb_PrintfAppender * a,const char * fmt,...)52 static void upb_FieldPath_Printf(upb_PrintfAppender* a, const char* fmt, ...) {
53 size_t n;
54 size_t have = a->end - a->ptr;
55 va_list args;
56
57 va_start(args, fmt);
58 n = _upb_vsnprintf(a->ptr, have, fmt, args);
59 va_end(args);
60
61 if (UPB_LIKELY(have > n)) {
62 // We can't end up here if the user passed (NULL, 0), therefore ptr is known
63 // to be non-NULL, and UPB_PTRADD() is not necessary.
64 assert(a->ptr);
65 a->ptr += n;
66 } else {
67 a->ptr = UPB_PTRADD(a->ptr, have);
68 a->overflow += (n - have);
69 }
70 }
71
upb_FieldPath_NullTerminate(upb_PrintfAppender * d,size_t size)72 static size_t upb_FieldPath_NullTerminate(upb_PrintfAppender* d, size_t size) {
73 size_t ret = d->ptr - d->buf + d->overflow;
74
75 if (size > 0) {
76 if (d->ptr == d->end) d->ptr--;
77 *d->ptr = '\0';
78 }
79
80 return ret;
81 }
82
upb_FieldPath_PutMapKey(upb_PrintfAppender * a,upb_MessageValue map_key,const upb_FieldDef * key_f)83 static void upb_FieldPath_PutMapKey(upb_PrintfAppender* a,
84 upb_MessageValue map_key,
85 const upb_FieldDef* key_f) {
86 switch (upb_FieldDef_CType(key_f)) {
87 case kUpb_CType_Int32:
88 upb_FieldPath_Printf(a, "[%" PRId32 "]", map_key.int32_val);
89 break;
90 case kUpb_CType_Int64:
91 upb_FieldPath_Printf(a, "[%" PRId64 "]", map_key.int64_val);
92 break;
93 case kUpb_CType_UInt32:
94 upb_FieldPath_Printf(a, "[%" PRIu32 "]", map_key.uint32_val);
95 break;
96 case kUpb_CType_UInt64:
97 upb_FieldPath_Printf(a, "[%" PRIu64 "]", map_key.uint64_val);
98 break;
99 case kUpb_CType_Bool:
100 upb_FieldPath_Printf(a, "[%s]", map_key.bool_val ? "true" : "false");
101 break;
102 case kUpb_CType_String:
103 upb_FieldPath_Printf(a, "[\"");
104 for (size_t i = 0; i < map_key.str_val.size; i++) {
105 char ch = map_key.str_val.data[i];
106 if (ch == '"') {
107 upb_FieldPath_Printf(a, "\\\"");
108 } else {
109 upb_FieldPath_Printf(a, "%c", ch);
110 }
111 }
112 upb_FieldPath_Printf(a, "\"]");
113 break;
114 default:
115 UPB_UNREACHABLE(); // Other types can't be map keys.
116 }
117 }
118
upb_FieldPath_ToText(upb_FieldPathEntry ** path,char * buf,size_t size)119 size_t upb_FieldPath_ToText(upb_FieldPathEntry** path, char* buf, size_t size) {
120 upb_FieldPathEntry* ptr = *path;
121 upb_PrintfAppender appender;
122 appender.buf = buf;
123 appender.ptr = buf;
124 appender.end = UPB_PTRADD(buf, size);
125 appender.overflow = 0;
126 bool first = true;
127
128 while (ptr->field) {
129 const upb_FieldDef* f = ptr->field;
130
131 upb_FieldPath_Printf(&appender, first ? "%s" : ".%s", upb_FieldDef_Name(f));
132 first = false;
133 ptr++;
134
135 if (upb_FieldDef_IsMap(f)) {
136 const upb_FieldDef* key_f =
137 upb_MessageDef_Field(upb_FieldDef_MessageSubDef(f), 0);
138 upb_FieldPath_PutMapKey(&appender, ptr->map_key, key_f);
139 ptr++;
140 } else if (upb_FieldDef_IsRepeated(f)) {
141 upb_FieldPath_Printf(&appender, "[%zu]", ptr->array_index);
142 ptr++;
143 }
144 }
145
146 // Advance beyond terminating NULL.
147 ptr++;
148 *path = ptr;
149 return upb_FieldPath_NullTerminate(&appender, size);
150 }
151
152 ////////////////////////////////////////////////////////////////////////////////
153 // upb_util_HasUnsetRequired()
154 ////////////////////////////////////////////////////////////////////////////////
155
156 typedef struct {
157 upb_FieldPathEntry* path;
158 size_t size;
159 size_t cap;
160 } upb_FieldPathVector;
161
162 typedef struct {
163 upb_FieldPathVector stack;
164 upb_FieldPathVector out_fields;
165 const upb_DefPool* ext_pool;
166 jmp_buf err;
167 bool has_unset_required;
168 bool save_paths;
169 } upb_FindContext;
170
upb_FieldPathVector_Init(upb_FieldPathVector * vec)171 static void upb_FieldPathVector_Init(upb_FieldPathVector* vec) {
172 vec->path = NULL;
173 vec->size = 0;
174 vec->cap = 0;
175 }
176
upb_FieldPathVector_Reserve(upb_FindContext * ctx,upb_FieldPathVector * vec,size_t elems)177 static void upb_FieldPathVector_Reserve(upb_FindContext* ctx,
178 upb_FieldPathVector* vec,
179 size_t elems) {
180 if (vec->cap - vec->size < elems) {
181 size_t need = vec->size + elems;
182 vec->cap = UPB_MAX(4, vec->cap);
183 while (vec->cap < need) vec->cap *= 2;
184 vec->path = realloc(vec->path, vec->cap * sizeof(*vec->path));
185 if (!vec->path) {
186 UPB_LONGJMP(ctx->err, 1);
187 }
188 }
189 }
190
upb_FindContext_Push(upb_FindContext * ctx,upb_FieldPathEntry ent)191 static void upb_FindContext_Push(upb_FindContext* ctx, upb_FieldPathEntry ent) {
192 if (!ctx->save_paths) return;
193 upb_FieldPathVector_Reserve(ctx, &ctx->stack, 1);
194 ctx->stack.path[ctx->stack.size++] = ent;
195 }
196
upb_FindContext_Pop(upb_FindContext * ctx)197 static void upb_FindContext_Pop(upb_FindContext* ctx) {
198 if (!ctx->save_paths) return;
199 assert(ctx->stack.size != 0);
200 ctx->stack.size--;
201 }
202
upb_util_FindUnsetInMessage(upb_FindContext * ctx,const upb_Message * msg,const upb_MessageDef * m)203 static void upb_util_FindUnsetInMessage(upb_FindContext* ctx,
204 const upb_Message* msg,
205 const upb_MessageDef* m) {
206 // Iterate over all fields to see if any required fields are missing.
207 for (int i = 0, n = upb_MessageDef_FieldCount(m); i < n; i++) {
208 const upb_FieldDef* f = upb_MessageDef_Field(m, i);
209 if (upb_FieldDef_Label(f) != kUpb_Label_Required) continue;
210
211 if (!msg || !upb_Message_HasFieldByDef(msg, f)) {
212 // A required field is missing.
213 ctx->has_unset_required = true;
214
215 if (ctx->save_paths) {
216 // Append the contents of the stack to the out array, then
217 // NULL-terminate.
218 upb_FieldPathVector_Reserve(ctx, &ctx->out_fields, ctx->stack.size + 2);
219 if (ctx->stack.size) {
220 memcpy(&ctx->out_fields.path[ctx->out_fields.size], ctx->stack.path,
221 ctx->stack.size * sizeof(*ctx->stack.path));
222 }
223 ctx->out_fields.size += ctx->stack.size;
224 ctx->out_fields.path[ctx->out_fields.size++] =
225 (upb_FieldPathEntry){.field = f};
226 ctx->out_fields.path[ctx->out_fields.size++] =
227 (upb_FieldPathEntry){.field = NULL};
228 }
229 }
230 }
231 }
232
upb_util_FindUnsetRequiredInternal(upb_FindContext * ctx,const upb_Message * msg,const upb_MessageDef * m)233 static void upb_util_FindUnsetRequiredInternal(upb_FindContext* ctx,
234 const upb_Message* msg,
235 const upb_MessageDef* m) {
236 // OPT: add markers in the schema for where we can avoid iterating:
237 // 1. messages with no required fields.
238 // 2. messages that cannot possibly reach any required fields.
239
240 upb_util_FindUnsetInMessage(ctx, msg, m);
241 if (!msg) return;
242
243 // Iterate over all present fields to find sub-messages that might be missing
244 // required fields. This may revisit some of the fields already inspected
245 // in the previous loop. We do this separately because this loop will also
246 // find present extensions, which the previous loop will not.
247 //
248 // TODO(haberman): consider changing upb_Message_Next() to be capable of
249 // visiting extensions only, for example with a kUpb_Message_BeginEXT
250 // constant.
251 size_t iter = kUpb_Message_Begin;
252 const upb_FieldDef* f;
253 upb_MessageValue val;
254 while (upb_Message_Next(msg, m, ctx->ext_pool, &f, &val, &iter)) {
255 // Skip non-submessage fields.
256 if (!upb_FieldDef_IsSubMessage(f)) continue;
257
258 upb_FindContext_Push(ctx, (upb_FieldPathEntry){.field = f});
259 const upb_MessageDef* sub_m = upb_FieldDef_MessageSubDef(f);
260
261 if (upb_FieldDef_IsMap(f)) {
262 // Map field.
263 const upb_FieldDef* val_f = upb_MessageDef_Field(sub_m, 1);
264 const upb_MessageDef* val_m = upb_FieldDef_MessageSubDef(val_f);
265 if (!val_m) continue;
266 const upb_Map* map = val.map_val;
267 size_t iter = kUpb_Map_Begin;
268 upb_MessageValue key, map_val;
269 while (upb_Map_Next(map, &key, &map_val, &iter)) {
270 upb_FindContext_Push(ctx, (upb_FieldPathEntry){.map_key = key});
271 upb_util_FindUnsetRequiredInternal(ctx, map_val.msg_val, val_m);
272 upb_FindContext_Pop(ctx);
273 }
274 } else if (upb_FieldDef_IsRepeated(f)) {
275 // Repeated field.
276 const upb_Array* arr = val.array_val;
277 for (size_t i = 0, n = upb_Array_Size(arr); i < n; i++) {
278 upb_MessageValue elem = upb_Array_Get(arr, i);
279 upb_FindContext_Push(ctx, (upb_FieldPathEntry){.array_index = i});
280 upb_util_FindUnsetRequiredInternal(ctx, elem.msg_val, sub_m);
281 upb_FindContext_Pop(ctx);
282 }
283 } else {
284 // Scalar sub-message field.
285 upb_util_FindUnsetRequiredInternal(ctx, val.msg_val, sub_m);
286 }
287
288 upb_FindContext_Pop(ctx);
289 }
290 }
291
upb_util_HasUnsetRequired(const upb_Message * msg,const upb_MessageDef * m,const upb_DefPool * ext_pool,upb_FieldPathEntry ** fields)292 bool upb_util_HasUnsetRequired(const upb_Message* msg, const upb_MessageDef* m,
293 const upb_DefPool* ext_pool,
294 upb_FieldPathEntry** fields) {
295 upb_FindContext ctx;
296 ctx.has_unset_required = false;
297 ctx.save_paths = fields != NULL;
298 ctx.ext_pool = ext_pool;
299 upb_FieldPathVector_Init(&ctx.stack);
300 upb_FieldPathVector_Init(&ctx.out_fields);
301 upb_util_FindUnsetRequiredInternal(&ctx, msg, m);
302 free(ctx.stack.path);
303 if (fields) {
304 upb_FieldPathVector_Reserve(&ctx, &ctx.out_fields, 1);
305 ctx.out_fields.path[ctx.out_fields.size] =
306 (upb_FieldPathEntry){.field = NULL};
307 *fields = ctx.out_fields.path;
308 }
309 return ctx.has_unset_required;
310 }
311