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/compare.h"
29 
30 #include <stdint.h>
31 
32 #include <initializer_list>
33 #include <string>
34 #include <variant>
35 #include <vector>
36 
37 #include "gtest/gtest.h"
38 #include "upb/wire/swap_internal.h"
39 #include "upb/wire/types.h"
40 
41 struct UnknownField;
42 
43 using UnknownFields = std::vector<UnknownField>;
44 
45 struct Varint {
VarintVarint46   explicit Varint(uint64_t _val) : val(_val) {}
47   uint64_t val;
48 };
49 struct LongVarint {
LongVarintLongVarint50   explicit LongVarint(uint64_t _val) : val(_val) {}
51   uint64_t val;  // Over-encoded.
52 };
53 struct Delimited {
DelimitedDelimited54   explicit Delimited(std::string _val) : val(_val) {}
55   std::string val;
56 };
57 struct Fixed64 {
Fixed64Fixed6458   explicit Fixed64(uint64_t _val) : val(_val) {}
59   uint64_t val;
60 };
61 struct Fixed32 {
Fixed32Fixed3262   explicit Fixed32(uint32_t _val) : val(_val) {}
63   uint32_t val;
64 };
65 struct Group {
GroupGroup66   Group(std::initializer_list<UnknownField> _val) : val(_val) {}
67   UnknownFields val;
68 };
69 
70 struct UnknownField {
71   uint32_t field_number;
72   std::variant<Varint, LongVarint, Delimited, Fixed64, Fixed32, Group> value;
73 };
74 
EncodeVarint(uint64_t val,std::string * str)75 void EncodeVarint(uint64_t val, std::string* str) {
76   do {
77     char byte = val & 0x7fU;
78     val >>= 7;
79     if (val) byte |= 0x80U;
80     str->push_back(byte);
81   } while (val);
82 }
83 
ToBinaryPayload(const UnknownFields & fields)84 std::string ToBinaryPayload(const UnknownFields& fields) {
85   std::string ret;
86 
87   for (const auto& field : fields) {
88     if (const auto* val = std::get_if<Varint>(&field.value)) {
89       EncodeVarint(field.field_number << 3 | kUpb_WireType_Varint, &ret);
90       EncodeVarint(val->val, &ret);
91     } else if (const auto* val = std::get_if<LongVarint>(&field.value)) {
92       EncodeVarint(field.field_number << 3 | kUpb_WireType_Varint, &ret);
93       EncodeVarint(val->val, &ret);
94       ret.back() |= 0x80;
95       ret.push_back(0);
96     } else if (const auto* val = std::get_if<Delimited>(&field.value)) {
97       EncodeVarint(field.field_number << 3 | kUpb_WireType_Delimited, &ret);
98       EncodeVarint(val->val.size(), &ret);
99       ret.append(val->val);
100     } else if (const auto* val = std::get_if<Fixed64>(&field.value)) {
101       EncodeVarint(field.field_number << 3 | kUpb_WireType_64Bit, &ret);
102       uint64_t swapped = _upb_BigEndian_Swap64(val->val);
103       ret.append(reinterpret_cast<const char*>(&swapped), sizeof(swapped));
104     } else if (const auto* val = std::get_if<Fixed32>(&field.value)) {
105       EncodeVarint(field.field_number << 3 | kUpb_WireType_32Bit, &ret);
106       uint32_t swapped = _upb_BigEndian_Swap32(val->val);
107       ret.append(reinterpret_cast<const char*>(&swapped), sizeof(swapped));
108     } else if (const auto* val = std::get_if<Group>(&field.value)) {
109       EncodeVarint(field.field_number << 3 | kUpb_WireType_StartGroup, &ret);
110       ret.append(ToBinaryPayload(val->val));
111       EncodeVarint(field.field_number << 3 | kUpb_WireType_EndGroup, &ret);
112     }
113   }
114 
115   return ret;
116 }
117 
CompareUnknownWithMaxDepth(UnknownFields uf1,UnknownFields uf2,int max_depth)118 upb_UnknownCompareResult CompareUnknownWithMaxDepth(UnknownFields uf1,
119                                                     UnknownFields uf2,
120                                                     int max_depth) {
121   std::string buf1 = ToBinaryPayload(uf1);
122   std::string buf2 = ToBinaryPayload(uf2);
123   return upb_Message_UnknownFieldsAreEqual(buf1.data(), buf1.size(),
124                                            buf2.data(), buf2.size(), max_depth);
125 }
126 
CompareUnknown(UnknownFields uf1,UnknownFields uf2)127 upb_UnknownCompareResult CompareUnknown(UnknownFields uf1, UnknownFields uf2) {
128   return CompareUnknownWithMaxDepth(uf1, uf2, 64);
129 }
130 
TEST(CompareTest,UnknownFieldsReflexive)131 TEST(CompareTest, UnknownFieldsReflexive) {
132   EXPECT_EQ(kUpb_UnknownCompareResult_Equal, CompareUnknown({}, {}));
133   EXPECT_EQ(kUpb_UnknownCompareResult_Equal,
134             CompareUnknown({{1, Varint(123)}, {2, Fixed32(456)}},
135                            {{1, Varint(123)}, {2, Fixed32(456)}}));
136   EXPECT_EQ(
137       kUpb_UnknownCompareResult_Equal,
138       CompareUnknown(
139           {{1, Group({{2, Group({{3, Fixed32(456)}, {4, Fixed64(123)}})}})}},
140           {{1, Group({{2, Group({{3, Fixed32(456)}, {4, Fixed64(123)}})}})}}));
141 }
142 
TEST(CompareTest,UnknownFieldsOrdering)143 TEST(CompareTest, UnknownFieldsOrdering) {
144   EXPECT_EQ(kUpb_UnknownCompareResult_Equal,
145             CompareUnknown({{1, Varint(111)},
146                             {2, Delimited("ABC")},
147                             {3, Fixed32(456)},
148                             {4, Fixed64(123)},
149                             {5, Group({})}},
150                            {{5, Group({})},
151                             {4, Fixed64(123)},
152                             {3, Fixed32(456)},
153                             {2, Delimited("ABC")},
154                             {1, Varint(111)}}));
155   EXPECT_EQ(kUpb_UnknownCompareResult_NotEqual,
156             CompareUnknown({{1, Varint(111)},
157                             {2, Delimited("ABC")},
158                             {3, Fixed32(456)},
159                             {4, Fixed64(123)},
160                             {5, Group({})}},
161                            {{5, Group({})},
162                             {4, Fixed64(123)},
163                             {3, Fixed32(455)},  // Small difference.
164                             {2, Delimited("ABC")},
165                             {1, Varint(111)}}));
166   EXPECT_EQ(kUpb_UnknownCompareResult_Equal,
167             CompareUnknown({{3, Fixed32(456)}, {4, Fixed64(123)}},
168                            {{4, Fixed64(123)}, {3, Fixed32(456)}}));
169   EXPECT_EQ(
170       kUpb_UnknownCompareResult_Equal,
171       CompareUnknown(
172           {{1, Group({{2, Group({{3, Fixed32(456)}, {4, Fixed64(123)}})}})}},
173           {{1, Group({{2, Group({{4, Fixed64(123)}, {3, Fixed32(456)}})}})}}));
174 }
175 
TEST(CompareTest,LongVarint)176 TEST(CompareTest, LongVarint) {
177   EXPECT_EQ(kUpb_UnknownCompareResult_Equal,
178             CompareUnknown({{1, LongVarint(123)}, {2, LongVarint(456)}},
179                            {{1, Varint(123)}, {2, Varint(456)}}));
180   EXPECT_EQ(kUpb_UnknownCompareResult_Equal,
181             CompareUnknown({{2, LongVarint(456)}, {1, LongVarint(123)}},
182                            {{1, Varint(123)}, {2, Varint(456)}}));
183 }
184 
TEST(CompareTest,MaxDepth)185 TEST(CompareTest, MaxDepth) {
186   EXPECT_EQ(
187       kUpb_UnknownCompareResult_MaxDepthExceeded,
188       CompareUnknownWithMaxDepth(
189           {{1, Group({{2, Group({{3, Fixed32(456)}, {4, Fixed64(123)}})}})}},
190           {{1, Group({{2, Group({{4, Fixed64(123)}, {3, Fixed32(456)}})}})}},
191           2));
192 }
193