1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2023 Google LLC. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7
8 #include "upb/mini_table/compat.h"
9
10 #include <stddef.h>
11 #include <stdint.h>
12
13 #include "upb/base/descriptor_constants.h"
14 #include "upb/hash/common.h"
15 #include "upb/hash/int_table.h"
16 #include "upb/mem/arena.h"
17 #include "upb/mini_table/field.h"
18 #include "upb/mini_table/message.h"
19
20 // Must be last.
21 #include "upb/port/def.inc"
22
23 // Checks if source and target mini table fields are identical.
24 //
25 // If the field is a sub message and sub messages are identical we record
26 // the association in table.
27 //
28 // Hashing the source sub message mini table and it's equivalent in the table
29 // stops recursing when a cycle is detected and instead just checks if the
30 // destination table is equal.
upb_deep_check(const upb_MiniTable * src,const upb_MiniTable * dst,upb_inttable * table,upb_Arena ** arena)31 static upb_MiniTableEquals_Status upb_deep_check(const upb_MiniTable* src,
32 const upb_MiniTable* dst,
33 upb_inttable* table,
34 upb_Arena** arena) {
35 if (src->UPB_PRIVATE(field_count) != dst->UPB_PRIVATE(field_count))
36 return kUpb_MiniTableEquals_NotEqual;
37 bool marked_src = false;
38 for (int i = 0; i < upb_MiniTable_FieldCount(src); i++) {
39 const upb_MiniTableField* src_field = upb_MiniTable_GetFieldByIndex(src, i);
40 const upb_MiniTableField* dst_field = upb_MiniTable_FindFieldByNumber(
41 dst, upb_MiniTableField_Number(src_field));
42
43 if (upb_MiniTableField_CType(src_field) !=
44 upb_MiniTableField_CType(dst_field))
45 return false;
46 if (src_field->UPB_PRIVATE(mode) != dst_field->UPB_PRIVATE(mode))
47 return false;
48 if (src_field->UPB_PRIVATE(offset) != dst_field->UPB_PRIVATE(offset))
49 return false;
50 if (src_field->presence != dst_field->presence) return false;
51 if (src_field->UPB_PRIVATE(submsg_index) !=
52 dst_field->UPB_PRIVATE(submsg_index))
53 return kUpb_MiniTableEquals_NotEqual;
54
55 // Go no further if we are only checking for compatibility.
56 if (!table) continue;
57
58 if (upb_MiniTableField_CType(src_field) == kUpb_CType_Message) {
59 if (!*arena) {
60 *arena = upb_Arena_New();
61 if (!upb_inttable_init(table, *arena)) {
62 return kUpb_MiniTableEquals_OutOfMemory;
63 }
64 }
65 if (!marked_src) {
66 marked_src = true;
67 upb_value val;
68 val.val = (uint64_t)dst;
69 if (!upb_inttable_insert(table, (uintptr_t)src, val, *arena)) {
70 return kUpb_MiniTableEquals_OutOfMemory;
71 }
72 }
73 const upb_MiniTable* sub_src =
74 upb_MiniTable_GetSubMessageTable(src, src_field);
75 const upb_MiniTable* sub_dst =
76 upb_MiniTable_GetSubMessageTable(dst, dst_field);
77 if (sub_src != NULL) {
78 upb_value cmp;
79 if (upb_inttable_lookup(table, (uintptr_t)sub_src, &cmp)) {
80 // We already compared this src before. Check if same dst.
81 if (cmp.val != (uint64_t)sub_dst) {
82 return kUpb_MiniTableEquals_NotEqual;
83 }
84 } else {
85 // Recurse if not already visited.
86 upb_MiniTableEquals_Status s =
87 upb_deep_check(sub_src, sub_dst, table, arena);
88 if (s != kUpb_MiniTableEquals_Equal) {
89 return s;
90 }
91 }
92 }
93 }
94 }
95 return kUpb_MiniTableEquals_Equal;
96 }
97
upb_MiniTable_Compatible(const upb_MiniTable * src,const upb_MiniTable * dst)98 bool upb_MiniTable_Compatible(const upb_MiniTable* src,
99 const upb_MiniTable* dst) {
100 return upb_deep_check(src, dst, NULL, NULL);
101 }
102
upb_MiniTable_Equals(const upb_MiniTable * src,const upb_MiniTable * dst)103 upb_MiniTableEquals_Status upb_MiniTable_Equals(const upb_MiniTable* src,
104 const upb_MiniTable* dst) {
105 // Arena allocated on demand for hash table.
106 upb_Arena* arena = NULL;
107 // Table to keep track of visited mini tables to guard against cycles.
108 upb_inttable table;
109 upb_MiniTableEquals_Status status = upb_deep_check(src, dst, &table, &arena);
110 if (arena) {
111 upb_Arena_Free(arena);
112 }
113 return status;
114 }
115