mini_table/internal/message.h

0001 // Protocol Buffers - Google's data interchange format
0002 // Copyright 2023 Google LLC.  All rights reserved.
0003 //
0004 // Use of this source code is governed by a BSD-style
0005 // license that can be found in the LICENSE file or at
0006 // https://developers.google.com/open-source/licenses/bsd
0007
0008 #ifndef UPB_MINI_TABLE_INTERNAL_MESSAGE_H_
0009 #define UPB_MINI_TABLE_INTERNAL_MESSAGE_H_
0010
0011 #include <stddef.h>
0012 #include <stdint.h>
0013
0014 #include "upb/base/descriptor_constants.h"
0015 #include "upb/mini_table/internal/field.h"
0016 #include "upb/mini_table/internal/sub.h"
0017
0018 // Must be last.
0019 #include "upb/port/def.inc"
0020
0021 struct upb_Decoder;
0022 struct upb_Message;
0023
0024 typedef UPB_PRESERVE_NONE const char* _upb_FieldParser(
0025     struct upb_Decoder* d, const char* ptr, struct upb_Message* msg,
0026     intptr_t table, uint64_t hasbits, uint64_t data);
0027
0028 typedef struct {
0029   uint64_t field_data;
0030   _upb_FieldParser* field_parser;
0031 } _upb_FastTable_Entry;
0032
0033 typedef enum {
0034   kUpb_ExtMode_NonExtendable = 0,  // Non-extendable message.
0035   kUpb_ExtMode_Extendable = 1,     // Normal extendable message.
0036   kUpb_ExtMode_IsMessageSet = 2,   // MessageSet message.
0037   kUpb_ExtMode_IsMessageSet_ITEM =
0038       3,  // MessageSet item (temporary only, see decode.c)
0039
0040   // During table building we steal a bit to indicate that the message is a map
0041   // entry.  *Only* used during table building!
0042   kUpb_ExtMode_IsMapEntry = 4,
0043 } upb_ExtMode;
0044
0045 enum {
0046   kUpb_Message_Align = 8,
0047 };
0048
0049 // upb_MiniTable represents the memory layout of a given upb_MessageDef.
0050 // The members are public so generated code can initialize them,
0051 // but users MUST NOT directly read or write any of its members.
0052
0053 // LINT.IfChange(minitable_struct_definition)
0054 struct upb_MiniTable {
0055   const upb_MiniTableSubInternal* UPB_PRIVATE(subs);
0056   const struct upb_MiniTableField* UPB_ONLYBITS(fields);
0057
0058   // Must be aligned to kUpb_Message_Align. Doesn't include internal members
0059   // like unknown fields, extension dict, pointer to msglayout, etc.
0060   uint16_t UPB_PRIVATE(size);
0061
0062   uint16_t UPB_ONLYBITS(field_count);
0063
0064   uint8_t UPB_PRIVATE(ext);  // upb_ExtMode, uint8_t here so sizeof(ext) == 1
0065   uint8_t UPB_PRIVATE(dense_below);
0066   uint8_t UPB_PRIVATE(table_mask);
0067   uint8_t UPB_PRIVATE(required_count);  // Required fields have the low hasbits.
0068
0069 #ifdef UPB_TRACING_ENABLED
0070   const char* UPB_PRIVATE(full_name);
0071 #endif
0072
0073 #if UPB_FASTTABLE || !defined(__cplusplus)
0074   // Flexible array member is not supported in C++, but it is an extension in
0075   // every compiler that supports UPB_FASTTABLE.
0076   _upb_FastTable_Entry UPB_PRIVATE(fasttable)[];
0077 #endif
0078 };
0079 // LINT.ThenChange(//depot/google3/third_party/upb/bits/typescript/mini_table.ts)
0080
0081 #ifdef __cplusplus
0082 extern "C" {
0083 #endif
0084
0085 UPB_INLINE void UPB_PRIVATE(upb_MiniTable_CheckInvariants)(
0086     const struct upb_MiniTable* mt) {
0087   UPB_STATIC_ASSERT(UPB_MALLOC_ALIGN >= kUpb_Message_Align, "Under aligned");
0088   UPB_STATIC_ASSERT(kUpb_Message_Align >= UPB_ALIGN_OF(void*), "Under aligned");
0089   UPB_ASSERT(mt->UPB_PRIVATE(size) % kUpb_Message_Align == 0);
0090 }
0091
0092 UPB_INLINE const struct upb_MiniTable* UPB_PRIVATE(
0093     _upb_MiniTable_StrongReference)(const struct upb_MiniTable* mt) {
0094 #if defined(__GNUC__)
0095   __asm__("" : : "r"(mt));
0096 #else
0097   const struct upb_MiniTable* volatile unused = mt;
0098   (void)&unused;  // Use address to avoid an extra load of "unused".
0099 #endif
0100   return mt;
0101 }
0102
0103 UPB_INLINE const struct upb_MiniTable* UPB_PRIVATE(_upb_MiniTable_Empty)(void) {
0104   extern const struct upb_MiniTable UPB_PRIVATE(_kUpb_MiniTable_Empty);
0105
0106   return &UPB_PRIVATE(_kUpb_MiniTable_Empty);
0107 }
0108
0109 UPB_API_INLINE int upb_MiniTable_FieldCount(const struct upb_MiniTable* m) {
0110   return m->UPB_ONLYBITS(field_count);
0111 }
0112
0113 UPB_API_INLINE bool upb_MiniTable_IsMessageSet(const struct upb_MiniTable* m) {
0114   return m->UPB_PRIVATE(ext) == kUpb_ExtMode_IsMessageSet;
0115 }
0116
0117 UPB_API_INLINE
0118 const struct upb_MiniTableField* upb_MiniTable_FindFieldByNumber(
0119     const struct upb_MiniTable* m, uint32_t number) {
0120   const size_t i = ((size_t)number) - 1;  // 0 wraps to SIZE_MAX
0121
0122   // Ideal case: index into dense fields
0123   if (i < m->UPB_PRIVATE(dense_below)) {
0124     UPB_ASSERT(m->UPB_ONLYBITS(fields)[i].UPB_ONLYBITS(number) == number);
0125     return &m->UPB_ONLYBITS(fields)[i];
0126   }
0127
0128   // Early exit if the field number is out of range.
0129   int32_t hi = m->UPB_ONLYBITS(field_count) - 1;
0130   if (hi < 0 || number > m->UPB_ONLYBITS(fields)[hi].UPB_ONLYBITS(number)) {
0131     return NULL;
0132   }
0133
0134   // Slow case: binary search
0135   uint32_t lo = m->UPB_PRIVATE(dense_below);
0136   const struct upb_MiniTableField* base = m->UPB_ONLYBITS(fields);
0137   while (hi >= (int32_t)lo) {
0138     uint32_t mid = (hi + lo) / 2;
0139     uint32_t num = base[mid].UPB_ONLYBITS(number);
0140     // These comparison operations allow, on ARM machines, to fuse all these
0141     // branches into one comparison followed by two CSELs to set the lo/hi
0142     // values, followed by a BNE to continue or terminate the loop. Since binary
0143     // search branches are generally unpredictable (50/50 in each direction),
0144     // this is a good deal. We use signed for the high, as this decrement may
0145     // underflow if mid is 0.
0146     int32_t hi_mid = mid - 1;
0147     uint32_t lo_mid = mid + 1;
0148     if (num == number) {
0149       return &base[mid];
0150     }
0151     if (UPB_UNPREDICTABLE(num < number)) {
0152       lo = lo_mid;
0153     } else {
0154       hi = hi_mid;
0155     }
0156   }
0157
0158   return NULL;
0159 }
0160
0161 UPB_INLINE bool UPB_PRIVATE(_upb_MiniTable_IsEmpty)(
0162     const struct upb_MiniTable* m) {
0163   extern const struct upb_MiniTable UPB_PRIVATE(_kUpb_MiniTable_Empty);
0164
0165   return m == &UPB_PRIVATE(_kUpb_MiniTable_Empty);
0166 }
0167
0168 UPB_API_INLINE const struct upb_MiniTableField* upb_MiniTable_GetFieldByIndex(
0169     const struct upb_MiniTable* m, uint32_t i) {
0170   return &m->UPB_ONLYBITS(fields)[i];
0171 }
0172
0173 UPB_INLINE const struct upb_MiniTable* UPB_PRIVATE(
0174     _upb_MiniTable_GetSubTableByIndex)(const struct upb_MiniTable* m,
0175                                        uint32_t i) {
0176   return *m->UPB_PRIVATE(subs)[i].UPB_PRIVATE(submsg);
0177 }
0178
0179 UPB_API_INLINE const struct upb_MiniTable* upb_MiniTable_SubMessage(
0180     const struct upb_MiniTable* m, const struct upb_MiniTableField* f) {
0181   if (upb_MiniTableField_CType(f) != kUpb_CType_Message) {
0182     return NULL;
0183   }
0184   return UPB_PRIVATE(_upb_MiniTable_GetSubTableByIndex)(
0185       m, f->UPB_PRIVATE(submsg_index));
0186 }
0187
0188 UPB_API_INLINE const struct upb_MiniTable* upb_MiniTable_GetSubMessageTable(
0189     const struct upb_MiniTable* m, const struct upb_MiniTableField* f) {
0190   UPB_ASSUME(upb_MiniTableField_CType(f) == kUpb_CType_Message);
0191   const struct upb_MiniTable* ret = upb_MiniTable_SubMessage(m, f);
0192   UPB_ASSUME(ret);
0193   return UPB_PRIVATE(_upb_MiniTable_IsEmpty)(ret) ? NULL : ret;
0194 }
0195
0196 UPB_API_INLINE bool upb_MiniTable_FieldIsLinked(
0197     const struct upb_MiniTable* m, const struct upb_MiniTableField* f) {
0198   return upb_MiniTable_GetSubMessageTable(m, f) != NULL;
0199 }
0200
0201 UPB_API_INLINE const struct upb_MiniTable* upb_MiniTable_MapEntrySubMessage(
0202     const struct upb_MiniTable* m, const struct upb_MiniTableField* f) {
0203   UPB_ASSERT(upb_MiniTable_FieldIsLinked(m, f));  // Map entries must be linked.
0204   UPB_ASSERT(upb_MiniTableField_IsMap(f));        // Function precondition.
0205   return upb_MiniTable_SubMessage(m, f);
0206 }
0207
0208 UPB_API_INLINE const struct upb_MiniTableEnum* upb_MiniTable_GetSubEnumTable(
0209     const struct upb_MiniTable* m, const struct upb_MiniTableField* f) {
0210   UPB_ASSERT(upb_MiniTableField_CType(f) == kUpb_CType_Enum);
0211   return m->UPB_PRIVATE(subs)[f->UPB_PRIVATE(submsg_index)].UPB_PRIVATE(
0212       subenum);
0213 }
0214
0215 UPB_API_INLINE const struct upb_MiniTableField* upb_MiniTable_MapKey(
0216     const struct upb_MiniTable* m) {
0217   UPB_ASSERT(upb_MiniTable_FieldCount(m) == 2);
0218   const struct upb_MiniTableField* f = upb_MiniTable_GetFieldByIndex(m, 0);
0219   UPB_ASSERT(upb_MiniTableField_Number(f) == 1);
0220   return f;
0221 }
0222
0223 UPB_API_INLINE const struct upb_MiniTableField* upb_MiniTable_MapValue(
0224     const struct upb_MiniTable* m) {
0225   UPB_ASSERT(upb_MiniTable_FieldCount(m) == 2);
0226   const struct upb_MiniTableField* f = upb_MiniTable_GetFieldByIndex(m, 1);
0227   UPB_ASSERT(upb_MiniTableField_Number(f) == 2);
0228   return f;
0229 }
0230
0231 // Computes a bitmask in which the |m->required_count| lowest bits are set.
0232 //
0233 // Sample output:
0234 //    RequiredMask(1) => 0b1 (0x1)
0235 //    RequiredMask(5) => 0b11111 (0x1f)
0236 UPB_INLINE uint64_t
0237 UPB_PRIVATE(_upb_MiniTable_RequiredMask)(const struct upb_MiniTable* m) {
0238   int n = m->UPB_PRIVATE(required_count);
0239   UPB_ASSERT(0 < n && n <= 64);
0240   return (1ULL << n) - 1;
0241 }
0242
0243 #ifdef UPB_TRACING_ENABLED
0244 UPB_INLINE const char* upb_MiniTable_FullName(
0245     const struct upb_MiniTable* mini_table) {
0246   return mini_table->UPB_PRIVATE(full_name);
0247 }
0248 // Initializes tracing proto name from language runtimes that construct
0249 // mini tables dynamically at runtime. The runtime is responsible for passing
0250 // controlling lifetime of name such as storing in same arena as mini_table.
0251 UPB_INLINE void upb_MiniTable_SetFullName(struct upb_MiniTable* mini_table,
0252                                           const char* full_name) {
0253   mini_table->UPB_PRIVATE(full_name) = full_name;
0254 }
0255 #endif
0256
0257 #ifdef __cplusplus
0258 } /* extern "C" */
0259 #endif
0260
0261 #include "upb/port/undef.inc"
0262
0263 #endif /* UPB_MINI_TABLE_INTERNAL_MESSAGE_H_ */