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