1 // Copyright 2018 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef TOOLS_CDDL_SEMA_H_ 6 #define TOOLS_CDDL_SEMA_H_ 7 8 #include <cstdint> 9 #include <iostream> 10 #include <map> 11 #include <memory> 12 #include <string> 13 #include <utility> 14 #include <vector> 15 16 #include "absl/algorithm/container.h" 17 #include "absl/types/optional.h" 18 #include "tools/cddl/parse.h" 19 20 struct CddlGroup; 21 22 // Represents a type defined in CDDL. 23 struct CddlType { 24 // Type of assignment being represented by this CDDL node. 25 enum class Which { 26 kDirectChoice, 27 kValue, 28 kId, 29 kMap, 30 kArray, 31 kGroupChoice, 32 kGroupnameChoice, 33 kTaggedType, 34 }; 35 enum class Op { 36 kNone, // not specified 37 kInclusiveRange, // .. 38 kExclusiveRange, // ... 39 kSize, // .size 40 kBits, // .bits 41 kRegexp, // .regexp 42 kCbor, // .cbor 43 kCborseq, // .cborseq 44 kWithin, // .within 45 kAnd, // .and 46 kLess, // .lt 47 kLessOrEqual, // .lt 48 kGreater, // .gt 49 kGreaterOrEqual, // .ge 50 kEqual, // .eq 51 kNotEqual, // .ne 52 kDefault, // .default 53 }; 54 struct TaggedType { 55 uint64_t tag_value; 56 CddlType* type; 57 }; 58 CddlType(); 59 ~CddlType(); 60 61 Which which; 62 union { 63 // A direct choice comes from the CDDL syntax "a-type / b-type / c-type". 64 // This is in contrast to a "group choice". 65 std::vector<CddlType*> direct_choice; 66 67 // A literal value (number, text, or bytes) stored as its original string 68 // form. 69 std::string value; 70 71 std::string id; 72 CddlGroup* map; 73 CddlGroup* array; 74 75 // A group choice comes from the CDDL syntax: 76 // a-group = ( 77 // key1: uint, key2: text // 78 // key3: float, key4: bytes // 79 // key5: text 80 // ) 81 CddlGroup* group_choice; 82 TaggedType tagged_type; 83 }; 84 85 Op op; 86 CddlType* constraint_type; 87 absl::optional<uint64_t> type_key; 88 }; 89 90 // Override for << operator to simplify logging. 91 // NOTE: If a new enum value is added without modifying this operator, it will 92 // lead to a compilation failure because an enum class is used. 93 inline std::ostream& operator<<(std::ostream& os, 94 const CddlType::Which& which) { 95 switch (which) { 96 case CddlType::Which::kDirectChoice: 97 os << "kDirectChoice"; 98 break; 99 case CddlType::Which::kValue: 100 os << "kValue"; 101 break; 102 case CddlType::Which::kId: 103 os << "kId"; 104 break; 105 case CddlType::Which::kMap: 106 os << "kMap"; 107 break; 108 case CddlType::Which::kArray: 109 os << "kArray"; 110 break; 111 case CddlType::Which::kGroupChoice: 112 os << "kGroupChoice"; 113 break; 114 case CddlType::Which::kGroupnameChoice: 115 os << "kGroupnameChoice"; 116 break; 117 case CddlType::Which::kTaggedType: 118 os << "kTaggedType"; 119 break; 120 } 121 return os; 122 } 123 124 // Represets a group defined in CDDL. 125 // TODO(btolsch): group choices 126 struct CddlGroup { 127 struct Entry { 128 enum class Which { 129 kUninitialized = 0, 130 kType, 131 kGroup, 132 }; 133 struct EntryType { 134 std::string opt_key; 135 absl::optional<uint64_t> integer_key; 136 CddlType* value; 137 }; 138 Entry(); 139 ~Entry(); 140 141 // Minimum number of times that this entry can be repeated. 142 uint32_t opt_occurrence_min; 143 144 // Maximum number of times that this entry can be repeated. 145 uint32_t opt_occurrence_max; 146 147 // Signifies whether an occurrence opperator is present or not. 148 bool occurrence_specified; 149 150 // Value to represent when opt_occurrence_min is unbounded. 151 static constexpr uint32_t kOccurrenceMinUnbounded = 0; 152 153 // Value to represent when opt_occurrence_max is unbounded. 154 static constexpr uint32_t kOccurrenceMaxUnbounded = 155 std::numeric_limits<uint32_t>::max(); 156 157 Which which = Which::kUninitialized; 158 union { 159 EntryType type; 160 CddlGroup* group; 161 }; 162 HasOccurrenceOperatorCddlGroup::Entry163 bool HasOccurrenceOperator() const { return occurrence_specified; } 164 }; 165 166 std::vector<std::unique_ptr<Entry>> entries; 167 }; 168 169 // Override for << operator to simplify logging. 170 // NOTE: If a new enum value is added without modifying this operator, it will 171 // lead to a compilation failure because an enum class is used. 172 inline std::ostream& operator<<(std::ostream& os, 173 const CddlGroup::Entry::Which& which) { 174 switch (which) { 175 case CddlGroup::Entry::Which::kUninitialized: 176 os << "kUninitialized"; 177 break; 178 case CddlGroup::Entry::Which::kType: 179 os << "kType"; 180 break; 181 case CddlGroup::Entry::Which::kGroup: 182 os << "kGroup"; 183 break; 184 } 185 return os; 186 } 187 188 // Represents all CDDL definitions. 189 struct CddlSymbolTable { 190 // Set of all CDDL types. 191 std::vector<std::unique_ptr<CddlType>> types; 192 193 // Set of all CDDL groups. 194 std::vector<std::unique_ptr<CddlGroup>> groups; 195 196 // Map from name of a type to the object that represents it. 197 std::map<std::string, CddlType*> type_map; 198 199 // Map from name of a group to the object that represents it. 200 std::map<std::string, CddlGroup*> group_map; 201 }; 202 203 // Represents a C++ Type, as translated from CDDL. 204 struct CppType { 205 // Data type for this C++ type. 206 enum class Which { 207 kUninitialized = 0, 208 kUint64, 209 kString, 210 kBytes, 211 kVector, 212 kEnum, 213 kStruct, 214 kOptional, 215 kDiscriminatedUnion, 216 kTaggedType, 217 }; 218 219 struct Vector { 220 CppType* element_type; 221 222 // Minimum length for the vector. 223 uint32_t min_length; 224 225 // Maximum length for the vector. 226 uint32_t max_length; 227 228 // Value to represent when opt_occurrence_min is unbounded. 229 static constexpr uint32_t kMinLengthUnbounded = 230 CddlGroup::Entry::kOccurrenceMinUnbounded; 231 232 // Value to represent when opt_occurrence_max is unbounded. 233 static constexpr uint32_t kMaxLengthUnbounded = 234 CddlGroup::Entry::kOccurrenceMaxUnbounded; 235 }; 236 237 struct Enum { 238 std::string name; 239 std::vector<CppType*> sub_members; 240 std::vector<std::pair<std::string, uint64_t>> members; 241 }; 242 243 // Represents a C++ Struct. 244 struct Struct { 245 enum class KeyType { 246 kMap, 247 kArray, 248 kPlainGroup, 249 }; 250 // Contains a member of a C++ Struct. 251 struct CppMember { 252 // Constructs a new CppMember from the required fields. This constructor 253 // is needed for vector::emplace_back(...). CppMemberCppType::Struct::CppMember254 CppMember(std::string name, 255 absl::optional<uint64_t> integer_key, 256 CppType* type) { 257 this->name = std::move(name); 258 this->integer_key = integer_key; 259 this->type = type; 260 } 261 262 // Name visible to callers of the generated C++ methods. 263 std::string name; 264 265 // When present, this key is used in place of the name for serialialized 266 // messages. This should only be the case for integer-keyed group entries. 267 absl::optional<uint64_t> integer_key; 268 269 // C++ Type this member represents. 270 CppType* type; 271 }; 272 273 // Set of all members in this Struct. 274 std::vector<CppMember> members; 275 276 // Type of data structure being represented. 277 KeyType key_type; 278 }; 279 280 struct DiscriminatedUnion { 281 std::vector<CppType*> members; 282 }; 283 284 struct Bytes { 285 absl::optional<size_t> fixed_size; 286 }; 287 288 struct TaggedType { 289 uint64_t tag; 290 CppType* real_type; 291 }; 292 293 CppType(); 294 ~CppType(); 295 296 void InitVector(); 297 void InitEnum(); 298 void InitStruct(); 299 void InitDiscriminatedUnion(); 300 void InitBytes(); 301 302 Which which = Which::kUninitialized; 303 std::string name; 304 absl::optional<uint64_t> type_key; 305 union { 306 Vector vector_type; 307 Enum enum_type; 308 Struct struct_type; 309 CppType* optional_type; 310 DiscriminatedUnion discriminated_union; 311 Bytes bytes_type; 312 TaggedType tagged_type; 313 }; 314 }; 315 316 // Override for << operator to simplify logging. 317 // NOTE: If a new enum value is added without modifying this operator, it will 318 // lead to a compilation failure because an enum class is used. 319 inline std::ostream& operator<<(std::ostream& os, const CppType::Which& which) { 320 switch (which) { 321 case CppType::Which::kUint64: 322 os << "kUint64"; 323 break; 324 case CppType::Which::kString: 325 os << "kString"; 326 break; 327 case CppType::Which::kBytes: 328 os << "kBytes"; 329 break; 330 case CppType::Which::kVector: 331 os << "kVector"; 332 break; 333 case CppType::Which::kEnum: 334 os << "kEnum"; 335 break; 336 case CppType::Which::kStruct: 337 os << "kStruct"; 338 break; 339 case CppType::Which::kOptional: 340 os << "kOptional"; 341 break; 342 case CppType::Which::kDiscriminatedUnion: 343 os << "kDiscriminatedUnion"; 344 break; 345 case CppType::Which::kTaggedType: 346 os << "kTaggedType"; 347 break; 348 case CppType::Which::kUninitialized: 349 os << "kUninitialized"; 350 break; 351 } 352 return os; 353 } 354 355 struct CppSymbolTable { 356 public: 357 std::vector<std::unique_ptr<CppType>> cpp_types; 358 std::map<std::string, CppType*> cpp_type_map; 359 360 std::vector<CppType*> TypesWithId(); 361 362 private: 363 std::vector<CppType*> TypesWithId_; 364 }; 365 366 std::pair<bool, CddlSymbolTable> BuildSymbolTable(const AstNode& rules); 367 std::pair<bool, CppSymbolTable> BuildCppTypes( 368 const CddlSymbolTable& cddl_table); 369 bool ValidateCppTypes(const CppSymbolTable& cpp_symbols); 370 void DumpType(CddlType* type, int indent_level = 0); 371 void DumpGroup(CddlGroup* group, int indent_level = 0); 372 void DumpSymbolTable(CddlSymbolTable* table); 373 374 #endif // TOOLS_CDDL_SEMA_H_ 375