1 // Copyright 2018 The Fuchsia 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 ZIRCON_SYSTEM_HOST_FIDL_INCLUDE_FIDL_FLAT_AST_H_
6 #define ZIRCON_SYSTEM_HOST_FIDL_INCLUDE_FIDL_FLAT_AST_H_
7 
8 #include <assert.h>
9 #include <stdint.h>
10 
11 #include <iostream>
12 #include <limits>
13 #include <map>
14 #include <memory>
15 #include <set>
16 #include <type_traits>
17 #include <vector>
18 
19 #include <lib/fit/function.h>
20 
21 #include "attributes.h"
22 #include "error_reporter.h"
23 #include "raw_ast.h"
24 #include "type_shape.h"
25 
26 namespace fidl {
27 namespace flat {
28 
29 template <typename T>
30 struct PtrCompare {
operatorPtrCompare31     bool operator()(const T* left, const T* right) const { return *left < *right; }
32 };
33 
34 struct Decl;
35 class Library;
36 
37 bool HasSimpleLayout(const Decl* decl);
38 
39 // This is needed (for now) to work around declaration order issues.
40 std::string LibraryName(const Library* library, StringView separator);
41 
42 // Name represents a scope name, i.e. a name within the context of a library
43 // or in the 'global' context. Names either reference (or name) things which
44 // appear in source, or are synthesized by the compiler (e.g. an anonymous
45 // struct name).
46 struct Name {
NameName47     Name() {}
48 
NameName49     Name(const Library* library, const SourceLocation name)
50         : library_(library),
51           name_from_source_(std::make_unique<SourceLocation>(name)) {}
52 
NameName53     Name(const Library* library, const std::string& name)
54         : library_(library),
55           anonymous_name_(std::make_unique<std::string>(name)) {}
56 
57     Name(Name&&) = default;
58     Name& operator=(Name&&) = default;
59 
is_anonymousName60     bool is_anonymous() const { return name_from_source_ == nullptr; }
libraryName61     const Library* library() const { return library_; }
source_locationName62     const SourceLocation& source_location() const {
63         assert(!is_anonymous());
64         return *name_from_source_.get();
65     }
name_partName66     const StringView name_part() const {
67         if (is_anonymous())
68             return *anonymous_name_.get();
69         return name_from_source_->data();
70     }
71 
72     bool operator==(const Name& other) const {
73         // TODO(pascallouis): Why are we lenient, and allow a name comparison,
74         // rather than require the more stricter pointer equality here?
75         if (LibraryName(library_, ".") != LibraryName(other.library_, "."))
76             return false;
77         return name_part() == other.name_part();
78     }
79     bool operator!=(const Name& other) const { return !operator==(other); }
80 
81     bool operator<(const Name& other) const {
82         if (LibraryName(library_, ".") != LibraryName(other.library_, "."))
83             return LibraryName(library_, ".") < LibraryName(other.library_, ".");
84         return name_part() < other.name_part();
85     }
86 
87 private:
88     const Library* library_ = nullptr;
89     std::unique_ptr<SourceLocation> name_from_source_;
90     std::unique_ptr<std::string> anonymous_name_;
91 };
92 
93 struct ConstantValue {
~ConstantValueConstantValue94     virtual ~ConstantValue() {}
95 
96     enum struct Kind {
97         kInt8,
98         kInt16,
99         kInt32,
100         kInt64,
101         kUint8,
102         kUint16,
103         kUint32,
104         kUint64,
105         kFloat32,
106         kFloat64,
107         kBool,
108         kString,
109     };
110 
111     virtual bool Convert(Kind kind, std::unique_ptr<ConstantValue>* out_value) const = 0;
112 
113     const Kind kind;
114 
115 protected:
ConstantValueConstantValue116     explicit ConstantValue(Kind kind)
117         : kind(kind) {}
118 };
119 
120 template <typename ValueType>
121 struct NumericConstantValue : ConstantValue {
122     static_assert(std::is_arithmetic<ValueType>::value && !std::is_same<ValueType, bool>::value,
123                   "NumericConstantValue can only be used with a numeric ValueType!");
124 
NumericConstantValueNumericConstantValue125     NumericConstantValue(ValueType value)
126         : ConstantValue(GetKind()), value(value) {}
127 
ValueTypeNumericConstantValue128     operator ValueType() const { return value; }
129 
130     friend bool operator==(const NumericConstantValue<ValueType>& l,
131                            const NumericConstantValue<ValueType>& r) {
132         return l.value == r.value;
133     }
134 
135     friend bool operator<(const NumericConstantValue<ValueType>& l,
136                           const NumericConstantValue<ValueType>& r) {
137         return l.value < r.value;
138     }
139 
140     friend bool operator>(const NumericConstantValue<ValueType>& l,
141                           const NumericConstantValue<ValueType>& r) {
142         return l.value > r.value;
143     }
144 
145     friend bool operator!=(const NumericConstantValue<ValueType>& l,
146                            const NumericConstantValue<ValueType>& r) {
147         return l.value != r.value;
148     }
149 
150     friend bool operator<=(const NumericConstantValue<ValueType>& l,
151                            const NumericConstantValue<ValueType>& r) {
152         return l.value <= r.value;
153     }
154 
155     friend bool operator>=(const NumericConstantValue<ValueType>& l,
156                            const NumericConstantValue<ValueType>& r) {
157         return l.value >= r.value;
158     }
159 
160     friend std::ostream& operator<<(std::ostream& os, const NumericConstantValue<ValueType>& v) {
161         if constexpr (GetKind() == Kind::kInt8)
162             os << static_cast<int>(v.value);
163         else if constexpr (GetKind() == Kind::kUint8)
164             os << static_cast<unsigned>(v.value);
165         else
166             os << v.value;
167         return os;
168     }
169 
ConvertNumericConstantValue170     virtual bool Convert(Kind kind, std::unique_ptr<ConstantValue>* out_value) const override {
171         assert(out_value != nullptr);
172         switch (kind) {
173         case Kind::kInt8: {
174             if (std::is_floating_point<ValueType>::value ||
175                 value < std::numeric_limits<int8_t>::lowest() ||
176                 value > std::numeric_limits<int8_t>::max()) {
177                 return false;
178             }
179             *out_value = std::make_unique<NumericConstantValue<int8_t>>(
180                 static_cast<int8_t>(value));
181             return true;
182         }
183         case Kind::kInt16: {
184             if (std::is_floating_point<ValueType>::value ||
185                 value < std::numeric_limits<int16_t>::lowest() ||
186                 value > std::numeric_limits<int16_t>::max()) {
187                 return false;
188             }
189             *out_value = std::make_unique<NumericConstantValue<int16_t>>(
190                 static_cast<int16_t>(value));
191             return true;
192         }
193         case Kind::kInt32: {
194             if (std::is_floating_point<ValueType>::value ||
195                 value < std::numeric_limits<int32_t>::lowest() ||
196                 value > std::numeric_limits<int32_t>::max()) {
197                 return false;
198             }
199             *out_value = std::make_unique<NumericConstantValue<int32_t>>(
200                 static_cast<int32_t>(value));
201             return true;
202         }
203         case Kind::kInt64: {
204             if (std::is_floating_point<ValueType>::value ||
205                 value < std::numeric_limits<int64_t>::lowest() ||
206                 value > std::numeric_limits<int64_t>::max()) {
207                 return false;
208             }
209             *out_value = std::make_unique<NumericConstantValue<int64_t>>(
210                 static_cast<int64_t>(value));
211             return true;
212         }
213         case Kind::kUint8: {
214             if (std::is_floating_point<ValueType>::value ||
215                 value < 0 || value > std::numeric_limits<uint8_t>::max()) {
216                 return false;
217             }
218             *out_value = std::make_unique<NumericConstantValue<uint8_t>>(
219                 static_cast<uint8_t>(value));
220             return true;
221         }
222         case Kind::kUint16: {
223             if (std::is_floating_point<ValueType>::value ||
224                 value < 0 || value > std::numeric_limits<uint16_t>::max()) {
225                 return false;
226             }
227             *out_value = std::make_unique<NumericConstantValue<uint16_t>>(
228                 static_cast<uint16_t>(value));
229             return true;
230         }
231         case Kind::kUint32: {
232             if (std::is_floating_point<ValueType>::value ||
233                 value < 0 || value > std::numeric_limits<uint32_t>::max()) {
234                 return false;
235             }
236             *out_value = std::make_unique<NumericConstantValue<uint32_t>>(
237                 static_cast<uint32_t>(value));
238             return true;
239         }
240         case Kind::kUint64: {
241             if (std::is_floating_point<ValueType>::value ||
242                 value < 0 || value > std::numeric_limits<uint64_t>::max()) {
243                 return false;
244             }
245             *out_value = std::make_unique<NumericConstantValue<uint64_t>>(
246                 static_cast<uint64_t>(value));
247             return true;
248         }
249         case Kind::kFloat32: {
250             if (!std::is_floating_point<ValueType>::value ||
251                 value < std::numeric_limits<float>::lowest() ||
252                 value > std::numeric_limits<float>::max()) {
253                 return false;
254             }
255             *out_value = std::make_unique<NumericConstantValue<float>>(static_cast<float>(value));
256             return true;
257         }
258         case Kind::kFloat64: {
259             if (!std::is_floating_point<ValueType>::value ||
260                 value < std::numeric_limits<double>::lowest() ||
261                 value > std::numeric_limits<double>::max()) {
262                 return false;
263             }
264             *out_value = std::make_unique<NumericConstantValue<double>>(static_cast<double>(value));
265             return true;
266         }
267         case Kind::kString:
268         case Kind::kBool:
269             return false;
270         }
271     }
272 
MinNumericConstantValue273     static NumericConstantValue<ValueType> Min() {
274         return NumericConstantValue<ValueType>(std::numeric_limits<ValueType>::lowest());
275     }
276 
MaxNumericConstantValue277     static NumericConstantValue<ValueType> Max() {
278         return NumericConstantValue<ValueType>(std::numeric_limits<ValueType>::max());
279     }
280 
281     ValueType value;
282 
283 private:
GetKindNumericConstantValue284     constexpr static Kind GetKind() {
285         if constexpr (std::is_same_v<ValueType, uint64_t>)
286             return Kind::kUint64;
287         if constexpr (std::is_same_v<ValueType, int64_t>)
288             return Kind::kInt64;
289         if constexpr (std::is_same_v<ValueType, uint32_t>)
290             return Kind::kUint32;
291         if constexpr (std::is_same_v<ValueType, int32_t>)
292             return Kind::kInt32;
293         if constexpr (std::is_same_v<ValueType, uint16_t>)
294             return Kind::kUint16;
295         if constexpr (std::is_same_v<ValueType, int16_t>)
296             return Kind::kInt16;
297         if constexpr (std::is_same_v<ValueType, uint8_t>)
298             return Kind::kUint8;
299         if constexpr (std::is_same_v<ValueType, int8_t>)
300             return Kind::kInt8;
301         if constexpr (std::is_same_v<ValueType, double>)
302             return Kind::kFloat64;
303         if constexpr (std::is_same_v<ValueType, float>)
304             return Kind::kFloat32;
305     }
306 };
307 
308 using Size = NumericConstantValue<uint32_t>;
309 
310 struct BoolConstantValue : ConstantValue {
BoolConstantValueBoolConstantValue311     BoolConstantValue(bool value)
312         : ConstantValue(ConstantValue::Kind::kBool), value(value) {}
313 
314     operator bool() const { return value; }
315 
316     friend bool operator==(const BoolConstantValue& l, const BoolConstantValue& r) {
317         return l.value == r.value;
318     }
319 
320     friend bool operator!=(const BoolConstantValue& l, const BoolConstantValue& r) {
321         return l.value != r.value;
322     }
323 
324     friend std::ostream& operator<<(std::ostream& os, const BoolConstantValue& v) {
325         os << v.value;
326         return os;
327     }
328 
ConvertBoolConstantValue329     virtual bool Convert(Kind kind, std::unique_ptr<ConstantValue>* out_value) const override {
330         assert(out_value != nullptr);
331         switch (kind) {
332         case Kind::kBool:
333             *out_value = std::make_unique<BoolConstantValue>(value);
334             return true;
335         default:
336             return false;
337         }
338     }
339 
340     bool value;
341 };
342 
343 struct StringConstantValue : ConstantValue {
StringConstantValueStringConstantValue344     explicit StringConstantValue(StringView value)
345         : ConstantValue(ConstantValue::Kind::kString), value(value) {}
346 
347     friend std::ostream& operator<<(std::ostream& os, const StringConstantValue& v) {
348         os << v.value.data();
349         return os;
350     }
351 
ConvertStringConstantValue352     virtual bool Convert(Kind kind, std::unique_ptr<ConstantValue>* out_value) const override {
353         assert(out_value != nullptr);
354         switch (kind) {
355         case Kind::kString:
356             *out_value = std::make_unique<StringConstantValue>(StringView(value));
357             return true;
358         default:
359             return false;
360         }
361     }
362 
363     StringView value;
364 };
365 
366 struct Constant {
~ConstantConstant367     virtual ~Constant() {}
368 
369     enum struct Kind {
370         kIdentifier,
371         kLiteral,
372         kSynthesized,
373     };
374 
ConstantConstant375     explicit Constant(Kind kind)
376         : kind(kind), value_(nullptr) {}
377 
IsResolvedConstant378     bool IsResolved() const { return value_ != nullptr; }
379 
ResolveToConstant380     void ResolveTo(std::unique_ptr<ConstantValue> value) {
381         assert(value != nullptr);
382         assert(!IsResolved() && "Constants should only be resolved once!");
383         value_ = std::move(value);
384     }
385 
ValueConstant386     const ConstantValue& Value() const {
387         assert(IsResolved() && "Accessing the value of an unresolved Constant!");
388         return *value_;
389     }
390 
391     const Kind kind;
392 
393 protected:
394     std::unique_ptr<ConstantValue> value_;
395 };
396 
397 struct IdentifierConstant : Constant {
IdentifierConstantIdentifierConstant398     explicit IdentifierConstant(Name name)
399         : Constant(Kind::kIdentifier), name(std::move(name)) {}
400 
401     Name name;
402 };
403 
404 struct LiteralConstant : Constant {
LiteralConstantLiteralConstant405     explicit LiteralConstant(std::unique_ptr<raw::Literal> literal)
406         : Constant(Kind::kLiteral), literal(std::move(literal)) {}
407 
408     std::unique_ptr<raw::Literal> literal;
409 };
410 
411 struct SynthesizedConstant : Constant {
SynthesizedConstantSynthesizedConstant412     explicit SynthesizedConstant(std::unique_ptr<ConstantValue> value)
413         : Constant(Kind::kSynthesized) {
414         ResolveTo(std::move(value));
415     }
416 };
417 
418 struct Decl {
~DeclDecl419     virtual ~Decl() {}
420 
421     enum struct Kind {
422         kConst,
423         kEnum,
424         kInterface,
425         kStruct,
426         kTable,
427         kUnion,
428     };
429 
DeclDecl430     Decl(Kind kind, std::unique_ptr<raw::AttributeList> attributes, Name name)
431         : kind(kind), attributes(std::move(attributes)), name(std::move(name)) {}
432 
433     const Kind kind;
434 
435     std::unique_ptr<raw::AttributeList> attributes;
436     const Name name;
437 
438     bool HasAttribute(fidl::StringView name) const;
439     fidl::StringView GetAttribute(fidl::StringView name) const;
440     std::string GetName() const;
441 
442     bool compiling = false;
443     bool compiled = false;
444 };
445 
446 struct Type {
~TypeType447     virtual ~Type() {}
448 
449     enum struct Kind {
450         kArray,
451         kVector,
452         kString,
453         kHandle,
454         kRequestHandle,
455         kPrimitive,
456         kIdentifier,
457     };
458 
TypeType459     explicit Type(Kind kind, uint32_t size, types::Nullability nullability)
460         : kind(kind), size(size), nullability(nullability) {}
461 
462     const Kind kind;
463     // Set at construction time for most types. Identifier types get
464     // this set later, during compilation.
465     uint32_t size;
466     const types::Nullability nullability;
467 
468     // Comparison helper object.
469     class Comparison {
470     public:
471         Comparison() = default;
472         template <class T>
CompareType473         Comparison Compare(const T& a, const T& b) const {
474             if (result_ != 0)
475                 return Comparison(result_);
476             if (a < b)
477                 return Comparison(-1);
478             if (b < a)
479                 return Comparison(1);
480             return Comparison(0);
481         }
482 
IsLessThanType483         bool IsLessThan() const {
484             return result_ < 0;
485         }
486 
487     private:
ComparisonType488         Comparison(int result)
489             : result_(result) {}
490         const int result_ = 0;
491     };
492 
493     bool operator<(const Type& other) const {
494         if (kind != other.kind)
495             return kind < other.kind;
496         return Compare(other).IsLessThan();
497     }
498 
499     // Compare this object against 'other'.
500     // It's guaranteed that this->kind == other.kind.
501     // Return <0 if *this < other, ==0 if *this == other, and >0 if *this > other.
502     // Derived types should override this, but also call this implementation.
CompareType503     virtual Comparison Compare(const Type& other) const {
504         assert(kind == other.kind);
505         return Comparison()
506             .Compare(nullability, other.nullability);
507     }
508 };
509 
510 struct ArrayType : public Type {
ArrayTypeArrayType511     ArrayType(SourceLocation name, std::unique_ptr<Type> element_type,
512               std::unique_ptr<Constant> element_count)
513         : Type(Kind::kArray, 0u, types::Nullability::kNonnullable), name(name),
514           element_type(std::move(element_type)),
515           element_count(std::move(element_count)) {}
516 
517     SourceLocation name;
518     std::unique_ptr<Type> element_type;
519     std::unique_ptr<Constant> element_count;
520 
CompareArrayType521     Comparison Compare(const Type& other) const override {
522         const auto& o = static_cast<const ArrayType&>(other);
523         return Type::Compare(o)
524             .Compare(static_cast<const Size&>(element_count->Value()).value,
525                      static_cast<const Size&>(o.element_count->Value()).value)
526             .Compare(*element_type, *o.element_type);
527     }
528 };
529 
530 struct VectorType : public Type {
VectorTypeVectorType531     VectorType(SourceLocation name, std::unique_ptr<Type> element_type,
532                std::unique_ptr<Constant> element_count, types::Nullability nullability)
533         : Type(Kind::kVector, 16u, nullability), name(name), element_type(std::move(element_type)),
534           element_count(std::move(element_count)) {}
535 
536     SourceLocation name;
537     std::unique_ptr<Type> element_type;
538     std::unique_ptr<Constant> element_count;
539 
CompareVectorType540     Comparison Compare(const Type& other) const override {
541         const auto& o = static_cast<const VectorType&>(other);
542         return Type::Compare(o)
543             .Compare(static_cast<const Size&>(element_count->Value()).value,
544                      static_cast<const Size&>(o.element_count->Value()).value)
545             .Compare(*element_type, *o.element_type);
546     }
547 };
548 
549 struct StringType : public Type {
StringTypeStringType550     StringType(SourceLocation name, std::unique_ptr<Constant> max_size,
551                types::Nullability nullability)
552         : Type(Kind::kString, 16u, nullability), name(name), max_size(std::move(max_size)) {}
553 
554     SourceLocation name;
555     std::unique_ptr<Constant> max_size;
556 
CompareStringType557     Comparison Compare(const Type& other) const override {
558         const auto& o = static_cast<const StringType&>(other);
559         return Type::Compare(o)
560             .Compare(static_cast<const Size&>(max_size->Value()).value,
561                      static_cast<const Size&>(o.max_size->Value()).value);
562     }
563 };
564 
565 struct HandleType : public Type {
HandleTypeHandleType566     HandleType(types::HandleSubtype subtype, types::Nullability nullability)
567         : Type(Kind::kHandle, 4u, nullability), subtype(subtype) {}
568 
569     const types::HandleSubtype subtype;
570 
CompareHandleType571     Comparison Compare(const Type& other) const override {
572         const auto& o = *static_cast<const HandleType*>(&other);
573         return Type::Compare(o)
574             .Compare(subtype, o.subtype);
575     }
576 };
577 
578 struct RequestHandleType : public Type {
RequestHandleTypeRequestHandleType579     RequestHandleType(Name name, types::Nullability nullability)
580         : Type(Kind::kRequestHandle, 4u, nullability), name(std::move(name)) {}
581 
582     Name name;
583 
CompareRequestHandleType584     Comparison Compare(const Type& other) const override {
585         const auto& o = static_cast<const RequestHandleType&>(other);
586         return Type::Compare(o)
587             .Compare(name, o.name);
588     }
589 };
590 
591 struct PrimitiveType : public Type {
SubtypeSizePrimitiveType592     static uint32_t SubtypeSize(types::PrimitiveSubtype subtype) {
593         switch (subtype) {
594         case types::PrimitiveSubtype::kBool:
595         case types::PrimitiveSubtype::kInt8:
596         case types::PrimitiveSubtype::kUint8:
597             return 1u;
598 
599         case types::PrimitiveSubtype::kInt16:
600         case types::PrimitiveSubtype::kUint16:
601             return 2u;
602 
603         case types::PrimitiveSubtype::kFloat32:
604         case types::PrimitiveSubtype::kInt32:
605         case types::PrimitiveSubtype::kUint32:
606             return 4u;
607 
608         case types::PrimitiveSubtype::kFloat64:
609         case types::PrimitiveSubtype::kInt64:
610         case types::PrimitiveSubtype::kUint64:
611             return 8u;
612         }
613     }
614 
PrimitiveTypePrimitiveType615     explicit PrimitiveType(types::PrimitiveSubtype subtype)
616         : Type(Kind::kPrimitive, SubtypeSize(subtype), types::Nullability::kNonnullable),
617           subtype(subtype) {}
618 
619     types::PrimitiveSubtype subtype;
620 
ComparePrimitiveType621     Comparison Compare(const Type& other) const override {
622         const auto& o = static_cast<const PrimitiveType&>(other);
623         return Type::Compare(o)
624             .Compare(subtype, o.subtype);
625     }
626 };
627 
628 struct IdentifierType : public Type {
IdentifierTypeIdentifierType629     IdentifierType(Name name, types::Nullability nullability)
630         : Type(Kind::kIdentifier, 0u, nullability), name(std::move(name)) {}
631 
632     Name name;
633 
CompareIdentifierType634     Comparison Compare(const Type& other) const override {
635         const auto& o = static_cast<const RequestHandleType&>(other);
636         return Type::Compare(o)
637             .Compare(name, o.name);
638     }
639 };
640 
641 struct Using {
UsingUsing642     Using(Name name, const PrimitiveType* type)
643         : name(std::move(name)), type(type) {}
644 
645     const Name name;
646     const PrimitiveType* type;
647 };
648 
649 struct Const : public Decl {
ConstConst650     Const(std::unique_ptr<raw::AttributeList> attributes, Name name, std::unique_ptr<Type> type,
651           std::unique_ptr<Constant> value)
652         : Decl(Kind::kConst, std::move(attributes), std::move(name)), type(std::move(type)),
653           value(std::move(value)) {}
654     std::unique_ptr<Type> type;
655     std::unique_ptr<Constant> value;
656 };
657 
658 struct Enum : public Decl {
659     struct Member {
MemberEnum::Member660         Member(SourceLocation name, std::unique_ptr<Constant> value, std::unique_ptr<raw::AttributeList> attributes)
661             : name(name), value(std::move(value)), attributes(std::move(attributes)) {}
662         SourceLocation name;
663         std::unique_ptr<Constant> value;
664         std::unique_ptr<raw::AttributeList> attributes;
665     };
666 
EnumEnum667     Enum(std::unique_ptr<raw::AttributeList> attributes, Name name,
668          std::unique_ptr<raw::IdentifierType> maybe_subtype,
669          std::vector<Member> members)
670         : Decl(Kind::kEnum, std::move(attributes), std::move(name)),
671           maybe_subtype(std::move(maybe_subtype)),
672           members(std::move(members)) {}
673 
674     // Set during construction.
675     std::unique_ptr<raw::IdentifierType> maybe_subtype;
676     std::vector<Member> members;
677 
678     // Set during compilation.
679     const PrimitiveType* type = nullptr;
680     TypeShape typeshape;
681 };
682 
683 struct Struct : public Decl {
684     struct Member {
MemberStruct::Member685         Member(std::unique_ptr<Type> type, SourceLocation name,
686                std::unique_ptr<Constant> maybe_default_value,
687                std::unique_ptr<raw::AttributeList> attributes)
688             : type(std::move(type)), name(std::move(name)),
689               maybe_default_value(std::move(maybe_default_value)),
690               attributes(std::move(attributes)) {}
691         std::unique_ptr<Type> type;
692         SourceLocation name;
693         std::unique_ptr<Constant> maybe_default_value;
694         std::unique_ptr<raw::AttributeList> attributes;
695         FieldShape fieldshape;
696     };
697 
698     Struct(std::unique_ptr<raw::AttributeList> attributes, Name name,
699            std::vector<Member> members, bool anonymous = false)
DeclStruct700         : Decl(Kind::kStruct, std::move(attributes), std::move(name)),
701           members(std::move(members)), anonymous(anonymous) {
702     }
703 
704     std::vector<Member> members;
705     const bool anonymous;
706     TypeShape typeshape;
707     bool recursive = false;
708 };
709 
710 struct Table : public Decl {
711     struct Member {
MemberTable::Member712         Member(std::unique_ptr<raw::Ordinal> ordinal, std::unique_ptr<Type> type, SourceLocation name,
713                std::unique_ptr<Constant> maybe_default_value,
714                std::unique_ptr<raw::AttributeList> attributes)
715             : ordinal(std::move(ordinal)),
716               maybe_used(std::make_unique<Used>(std::move(type), std::move(name),
717                                                 std::move(maybe_default_value),
718                                                 std::move(attributes))) {}
MemberTable::Member719         Member(std::unique_ptr<raw::Ordinal> ordinal)
720             : ordinal(std::move(ordinal)) {}
721         std::unique_ptr<raw::Ordinal> ordinal;
722         struct Used {
UsedTable::Member::Used723             Used(std::unique_ptr<Type> type, SourceLocation name,
724                  std::unique_ptr<Constant> maybe_default_value,
725                  std::unique_ptr<raw::AttributeList> attributes)
726                 : type(std::move(type)), name(std::move(name)),
727                   maybe_default_value(std::move(maybe_default_value)),
728                   attributes(std::move(attributes)) {}
729             std::unique_ptr<Type> type;
730             SourceLocation name;
731             std::unique_ptr<Constant> maybe_default_value;
732             std::unique_ptr<raw::AttributeList> attributes;
733             TypeShape typeshape;
734         };
735         std::unique_ptr<Used> maybe_used;
736     };
737 
TableTable738     Table(std::unique_ptr<raw::AttributeList> attributes, Name name, std::vector<Member> members)
739         : Decl(Kind::kTable, std::move(attributes), std::move(name)), members(std::move(members)) {
740     }
741 
742     std::vector<Member> members;
743     TypeShape typeshape;
744     bool recursive = false;
745 };
746 
747 struct Union : public Decl {
748     struct Member {
MemberUnion::Member749         Member(std::unique_ptr<Type> type, SourceLocation name, std::unique_ptr<raw::AttributeList> attributes)
750             : type(std::move(type)), name(std::move(name)), attributes(std::move(attributes)) {}
751         std::unique_ptr<Type> type;
752         SourceLocation name;
753         std::unique_ptr<raw::AttributeList> attributes;
754         FieldShape fieldshape;
755     };
756 
UnionUnion757     Union(std::unique_ptr<raw::AttributeList> attributes, Name name, std::vector<Member> members)
758         : Decl(Kind::kUnion, std::move(attributes), std::move(name)), members(std::move(members)) {}
759 
760     std::vector<Member> members;
761     TypeShape typeshape;
762     // The offset of each of the union members is the same, so store
763     // it here as well.
764     FieldShape membershape;
765     bool recursive = false;
766 };
767 
768 struct Interface : public Decl {
769     struct Method {
770         Method(Method&&) = default;
771         Method& operator=(Method&&) = default;
772 
MethodInterface::Method773         Method(std::unique_ptr<raw::AttributeList> attributes,
774                std::unique_ptr<raw::Ordinal> ordinal, SourceLocation name,
775                Struct* maybe_request,
776                Struct* maybe_response)
777             : attributes(std::move(attributes)), ordinal(std::move(ordinal)), name(std::move(name)),
778               maybe_request(maybe_request), maybe_response(maybe_response) {
779             assert(this->maybe_request != nullptr || this->maybe_response != nullptr);
780         }
781 
782         std::unique_ptr<raw::AttributeList> attributes;
783         std::unique_ptr<raw::Ordinal> ordinal;
784         SourceLocation name;
785         Struct* maybe_request;
786         Struct* maybe_response;
787     };
788 
InterfaceInterface789     Interface(std::unique_ptr<raw::AttributeList> attributes, Name name,
790               std::vector<Name> superinterfaces, std::vector<Method> methods)
791         : Decl(Kind::kInterface, std::move(attributes), std::move(name)),
792           superinterfaces(std::move(superinterfaces)), methods(std::move(methods)) {}
793 
794     std::vector<Name> superinterfaces;
795     std::vector<Method> methods;
796     // Pointers here are set after superinterfaces are compiled, and
797     // are owned by the correspending superinterface.
798     std::vector<const Method*> all_methods;
799 };
800 
801 // Typespace provides builders for all types (e.g. array, vector, string), and
802 // ensures canonicalization, i.e. the same type is represented by one object,
803 // shared amongst all uses of said type. For instance, while the text
804 // `vector<uint8>:7` may appear multiple times in source, these all indicate
805 // the same type.
806 class Typespace {
807 public:
808     enum LookupMode {
809         kNoForwardReferences,
810         kAllowForwardReferences,
811     };
812 
813     // Lookup looks up a type by its name, or alias, and returns the type
814     // which corresponds, whilst respecting the nullability qualifier.
815     // If the type exists, returns the type, otherwise returns nullptr.
816     //
817     // If forward references are allowed, a placeholder type is returned
818     // if the type does not exist yet. This allows forward references to be
819     // made, and later resolved.
820     //
821     // See also RegisterDecl, RegisterAlias, and
822     // EnsureAllTypesHaveBeenResolved.
823     Type* Lookup(const flat::Name& name, types::Nullability nullability,
824                  LookupMode lookup_mode);
825 
826     // ArrayType creates or returns an array type for the |element_type|,
827     // and |element_count|.
828     ArrayType* ArrayType(Type* element_type, Size element_count);
829 
830     // VectorType creates or returns a vector type for the |element_type|,
831     // |max_size|, and |nullability|.
832     VectorType* VectorType(Type* element_type, Size max_size,
833                            types::Nullability nullability);
834 
835     // StringType creates or returns a string type for |max_size|,
836     // and |nullability|.
837     StringType* StringType(Size max_size, types::Nullability nullability);
838 
839     // HandleType creates or returns a handle type for the |subtype|,
840     // and |nullability|.
841     HandleType* HandleType(types::HandleSubtype subtype, types::Nullability nullability);
842 
843     // RequestType creates or returns an interface request type for the |name|,
844     // and |nullability|.
845     RequestHandleType* RequestType(Name name, types::Nullability nullability);
846 
847     // RegisterDecl registers a declaration under a specific name. Registering
848     // a declaration resolves all prior references to this named type, i.e.
849     // earlier lookups from forward references.
850     // This method returns true if there was no name conflict, false otherwise.
851     bool RegisterDecl(Name name, Decl* decl);
852 
853     // RegisterAlias registers a type alias, such as `using int = int32;`. An
854     // aliased type can be referenced by either name, with no behavioral
855     // difference.
856     // This method returns true if there was no name conflict, false otherwise.
857     bool RegisterAlias(Name name, Name alias);
858 
859     // EnsureAllTypesHaveBeenResolved checks that all forward references have
860     // been propertly resolved.
861     bool EnsureAllTypesHaveBeenResolved();
862 
863     // BoostrapRootTypes creates a instance with all primitive types. It is
864     // meant to be used as the top-level types lookup mechanism, providing
865     // definitional meaning to names such as `int64`, or `bool`.
RootTypes()866     static Typespace RootTypes() {
867         Typespace root_typespace;
868         ByName primitive_types;
869         auto add = [&](const std::string name, types::PrimitiveSubtype subtype) {
870             root_typespace.owned_names_.push_back(
871                 std::make_unique<Name>(nullptr, name));
872             primitive_types.emplace(
873                 root_typespace.owned_names_.back().get(),
874                 std::make_unique<PrimitiveType>(subtype));
875         };
876 
877         add("bool", types::PrimitiveSubtype::kBool);
878 
879         add("int8", types::PrimitiveSubtype::kInt8);
880         add("int16", types::PrimitiveSubtype::kInt16);
881         add("int32", types::PrimitiveSubtype::kInt32);
882         add("int64", types::PrimitiveSubtype::kInt64);
883         add("uint8", types::PrimitiveSubtype::kUint8);
884         add("uint16", types::PrimitiveSubtype::kUint16);
885         add("uint32", types::PrimitiveSubtype::kUint32);
886         add("uint64", types::PrimitiveSubtype::kUint64);
887 
888         add("float32", types::PrimitiveSubtype::kFloat32);
889         add("float64", types::PrimitiveSubtype::kFloat64);
890 
891         root_typespace.named_types_.emplace(
892             types::Nullability::kNonnullable, std::move(primitive_types));
893         return root_typespace;
894     }
895 
896 private:
897     // CreateForwardDeclaredType creates a placeholder for the named type. As
898     // the name suggest, this type must be resolved by registering a named type
899     // for it.
900     //
901     // See also RegisterDecl, RegisterAlias, and
902     // EnsureAllTypesHaveBeenResolved.
903     Type* CreateForwardDeclaredType(const flat::Name& name, types::Nullability nullability);
904 
905     struct cmpName {
operatorcmpName906         bool operator()(const flat::Name* a, const flat::Name* b) const {
907             return *a < *b;
908         }
909     };
910 
911     using BySize = std::map<const Size, std::unique_ptr<Type>>;
912     using ByNullability = std::map<types::Nullability, std::unique_ptr<Type>>;
913     using ByName = std::map<const flat::Name*, std::unique_ptr<Type>, cmpName>;
914     using ByHandleSubtype = std::map<types::HandleSubtype, std::unique_ptr<Type>>;
915 
916     using ByNullabilityThenBySize = std::map<types::Nullability, BySize>;
917     using ByNullabilityThenByName = std::map<types::Nullability, ByName>;
918     using ByNullabilityThenByHandleSubtype = std::map<types::Nullability, ByHandleSubtype>;
919 
920     std::map<const Type*, BySize> array_types_;
921     std::map<const Type*, ByNullabilityThenBySize> vector_types_;
922     ByNullabilityThenBySize string_types_;
923     ByNullabilityThenByHandleSubtype handle_types_;
924     ByNullabilityThenByName request_types_;
925     ByNullabilityThenByName named_types_;
926     ByName aliases_;
927 
928     std::vector<std::unique_ptr<Name>> owned_names_;
929 };
930 
931 // AttributeSchema defines a schema for attributes. This includes:
932 // - The allowed placement of an attribute (e.g. on a method, on a struct
933 //   declaration);
934 // - The allowed values which an attribute can take.
935 // For attributes which may be placed on declarations (e.g. interface, struct,
936 // union, table), a schema may additionally include:
937 // - A constraint which must be met by the declaration.
938 class AttributeSchema {
939 public:
940     using Constraint = fit::function<bool(ErrorReporter* error_reporter,
941                                           const raw::Attribute* attribute,
942                                           const Decl* decl)>;
943 
944     // Placement indicates the placement of an attribute, e.g. whether an
945     // attribute is placed on an enum declaration, method, or union
946     // member.
947     enum class Placement {
948         kConstDecl,
949         kEnumDecl,
950         kEnumMember,
951         kInterfaceDecl,
952         kLibrary,
953         kMethod,
954         kStructDecl,
955         kStructMember,
956         kTableDecl,
957         kTableMember,
958         kUnionDecl,
959         kUnionMember,
960     };
961 
962     AttributeSchema(const std::set<Placement>& allowed_placements,
963                     const std::set<std::string> allowed_values,
964                     Constraint constraint = NoOpConstraint);
965 
966     AttributeSchema(AttributeSchema&& schema) = default;
967 
968     void ValidatePlacement(ErrorReporter* error_reporter,
969                            const raw::Attribute* attribute,
970                            Placement placement) const;
971 
972     void ValidateValue(ErrorReporter* error_reporter,
973                        const raw::Attribute* attribute) const;
974 
975     void ValidateConstraint(ErrorReporter* error_reporter,
976                             const raw::Attribute* attribute,
977                             const Decl* decl) const;
978 
979 private:
NoOpConstraint(ErrorReporter * error_reporter,const raw::Attribute * attribute,const Decl * decl)980     static bool NoOpConstraint(ErrorReporter* error_reporter,
981                                const raw::Attribute* attribute,
982                                const Decl* decl) {
983         return true;
984     }
985 
986     std::set<Placement> allowed_placements_;
987     std::set<std::string> allowed_values_;
988     Constraint constraint_;
989 };
990 
991 class Libraries {
992 public:
993     Libraries();
994 
995     // Insert |library|.
996     bool Insert(std::unique_ptr<Library> library);
997 
998     // Lookup a library by its |library_name|.
999     bool Lookup(const std::vector<StringView>& library_name,
1000                 Library** out_library) const;
1001 
AddAttributeSchema(const std::string & name,AttributeSchema schema)1002     void AddAttributeSchema(const std::string& name, AttributeSchema schema) {
1003         auto iter = attribute_schemas_.emplace(name, std::move(schema));
1004         assert(iter.second && "do not add schemas twice");
1005     }
1006 
1007     const AttributeSchema* RetrieveAttributeSchema(ErrorReporter* error_reporter,
1008                                                    const raw::Attribute* attribute) const;
1009 
1010 private:
1011     std::map<std::vector<StringView>, std::unique_ptr<Library>> all_libraries_;
1012     std::map<std::string, AttributeSchema> attribute_schemas_;
1013 };
1014 
1015 class Dependencies {
1016 public:
1017     // Register a dependency to a library. The newly recorded dependent library
1018     // will be referenced by its name, and may also be optionally be referenced
1019     // by an alias.
1020     bool Register(StringView filename, Library* dep_library,
1021                   const std::unique_ptr<raw::Identifier>& maybe_alias);
1022 
1023     // Lookup a dependent library by |filename| and |name|.
1024     bool Lookup(StringView filename, const std::vector<StringView>& name,
1025                 Library** out_library);
1026 
dependencies()1027     const std::set<Library*>& dependencies() const { return dependencies_aggregate_; };
1028 
1029 private:
1030     bool InsertByName(StringView filename, const std::vector<StringView>& name,
1031                       Library* library);
1032 
1033     using ByName = std::map<std::vector<StringView>, Library*>;
1034     using ByFilename = std::map<std::string, std::unique_ptr<ByName>>;
1035 
1036     ByFilename dependencies_;
1037     std::set<Library*> dependencies_aggregate_;
1038 };
1039 
1040 class Library {
1041 public:
Library(const Libraries * all_libraries,ErrorReporter * error_reporter,Typespace * typespace)1042     Library(const Libraries* all_libraries, ErrorReporter* error_reporter, Typespace* typespace)
1043         : all_libraries_(all_libraries), error_reporter_(error_reporter), typespace_(typespace) {}
1044 
1045     bool ConsumeFile(std::unique_ptr<raw::File> file);
1046     bool Compile();
1047 
name()1048     const std::vector<StringView>& name() const { return library_name_; }
errors()1049     const std::vector<std::string>& errors() const { return error_reporter_->errors(); }
1050 
1051 private:
1052     bool Fail(StringView message);
1053     bool Fail(const SourceLocation& location, StringView message);
Fail(const Name & name,StringView message)1054     bool Fail(const Name& name, StringView message) {
1055         if (name.is_anonymous()) {
1056             return Fail(message);
1057         }
1058         return Fail(name.source_location(), message);
1059     }
Fail(const Decl & decl,StringView message)1060     bool Fail(const Decl& decl, StringView message) { return Fail(decl.name, message); }
1061 
1062     void ValidateAttributesPlacement(AttributeSchema::Placement placement,
1063                                      const raw::AttributeList* attributes);
1064     void ValidateAttributesConstraints(const Decl* decl,
1065                                        const raw::AttributeList* attributes);
1066 
1067     Name NextAnonymousName();
1068 
1069     bool CompileCompoundIdentifier(const raw::CompoundIdentifier* compound_identifier,
1070                                    SourceLocation location, Name* out_name);
1071     void RegisterConst(Const* decl);
1072     bool RegisterDecl(Decl* decl);
1073 
1074     bool ConsumeConstant(std::unique_ptr<raw::Constant> raw_constant, SourceLocation location,
1075                          std::unique_ptr<Constant>* out_constant);
1076     bool ConsumeType(std::unique_ptr<raw::Type> raw_type, SourceLocation location,
1077                      std::unique_ptr<Type>* out_type);
1078 
1079     bool ConsumeUsing(std::unique_ptr<raw::Using> using_directive);
1080     bool ConsumeTypeAlias(std::unique_ptr<raw::Using> using_directive);
1081     bool ConsumeConstDeclaration(std::unique_ptr<raw::ConstDeclaration> const_declaration);
1082     bool ConsumeEnumDeclaration(std::unique_ptr<raw::EnumDeclaration> enum_declaration);
1083     bool
1084     ConsumeInterfaceDeclaration(std::unique_ptr<raw::InterfaceDeclaration> interface_declaration);
1085     bool ConsumeParameterList(std::unique_ptr<raw::ParameterList> parameter_list,
1086                               Struct** out_struct_decl);
1087     bool ConsumeStructDeclaration(std::unique_ptr<raw::StructDeclaration> struct_declaration);
1088     bool ConsumeTableDeclaration(std::unique_ptr<raw::TableDeclaration> table_declaration);
1089     bool ConsumeUnionDeclaration(std::unique_ptr<raw::UnionDeclaration> union_declaration);
1090 
1091     bool TypeCanBeConst(const Type* type);
1092     const Type* TypeResolve(const Type* type);
1093     bool TypeIsConvertibleTo(const Type* from_type, const Type* to_type);
1094 
1095     // Given a const declaration of the form
1096     //     const type foo = name;
1097     // return the declaration corresponding to name.
1098     Decl* LookupConstant(const Type* type, const Name& name);
1099 
1100     // Given a name, checks whether that name corresponds to a primitive type. If
1101     // so, returns the type. Otherwise, returns nullptr.
1102     const PrimitiveType* LookupPrimitiveType(const Name& name) const;
1103 
1104     // Given a name, checks whether that name corresponds to a type alias. If
1105     // so, returns the type. Otherwise, returns nullptr.
1106     const PrimitiveType* LookupTypeAlias(const Name& name) const;
1107 
1108     // Returns nullptr when |type| does not correspond directly to a
1109     // declaration. For example, if |type| refers to int32 or if it is
1110     // a struct pointer, this will return null. If it is a struct, it
1111     // will return a pointer to the declaration of the type.
1112     enum class LookupOption {
1113         kIgnoreNullable,
1114         kIncludeNullable,
1115     };
1116     Decl* LookupDeclByType(const flat::Type* type, LookupOption option) const;
1117 
1118     bool DeclDependencies(Decl* decl, std::set<Decl*>* out_edges);
1119 
1120     bool SortDeclarations();
1121 
1122     bool CompileLibraryName();
1123 
1124     bool CompileConst(Const* const_declaration);
1125     bool CompileEnum(Enum* enum_declaration);
1126     bool CompileInterface(Interface* interface_declaration);
1127     bool CompileStruct(Struct* struct_declaration);
1128     bool CompileTable(Table* table_declaration);
1129     bool CompileUnion(Union* union_declaration);
1130 
1131     // Compiling a type both validates the type, and computes shape
1132     // information for the type. In particular, we validate that
1133     // optional identifier types refer to things that can in fact be
1134     // nullable (ie not enums).
1135     bool CompileArrayType(ArrayType* array_type, TypeShape* out_type_metadata);
1136     bool CompileVectorType(VectorType* vector_type, TypeShape* out_type_metadata);
1137     bool CompileStringType(StringType* string_type, TypeShape* out_type_metadata);
1138     bool CompileHandleType(HandleType* handle_type, TypeShape* out_type_metadata);
1139     bool CompileRequestHandleType(RequestHandleType* request_type, TypeShape* out_type_metadata);
1140     bool CompilePrimitiveType(PrimitiveType* primitive_type, TypeShape* out_type_metadata);
1141     bool CompileIdentifierType(IdentifierType* identifier_type, TypeShape* out_type_metadata);
1142     bool CompileType(Type* type, TypeShape* out_type_metadata);
1143 
1144     bool ResolveConstant(Constant* constant, const Type* type);
1145     bool ResolveIdentifierConstant(IdentifierConstant* identifier_constant, const Type* type);
1146     bool ResolveLiteralConstant(LiteralConstant* literal_constant, const Type* type);
1147 
1148     template <typename MemberType>
1149     bool ValidateEnumMembers(Enum* enum_decl);
1150 
1151 public:
1152     // Returns nullptr when the |name| cannot be resolved to a
1153     // Name. Otherwise it returns the declaration.
1154     Decl* LookupDeclByName(const Name& name) const;
1155 
1156     template <typename NumericType>
1157     bool ParseNumericLiteral(const raw::NumericLiteral* literal, NumericType* out_value) const;
1158 
1159     bool HasAttribute(fidl::StringView name) const;
1160 
1161     const std::set<Library*>& dependencies() const;
1162 
1163     std::vector<StringView> library_name_;
1164 
1165     std::vector<std::unique_ptr<Using>> using_;
1166     std::vector<std::unique_ptr<Const>> const_declarations_;
1167     std::vector<std::unique_ptr<Enum>> enum_declarations_;
1168     std::vector<std::unique_ptr<Interface>> interface_declarations_;
1169     std::vector<std::unique_ptr<Struct>> struct_declarations_;
1170     std::vector<std::unique_ptr<Table>> table_declarations_;
1171     std::vector<std::unique_ptr<Union>> union_declarations_;
1172 
1173     // All Decl pointers here are non-null and are owned by the
1174     // various foo_declarations_.
1175     std::vector<Decl*> declaration_order_;
1176 
1177 private:
1178     const PrimitiveType kSizeType = PrimitiveType(types::PrimitiveSubtype::kUint32);
1179 
1180     std::unique_ptr<raw::AttributeList> attributes_;
1181 
1182     Dependencies dependencies_;
1183     const Libraries* all_libraries_;
1184 
1185     // All Name, Constant, Using, and Decl pointers here are non-null and are
1186     // owned by the various foo_declarations_.
1187     std::map<const Name*, Using*, PtrCompare<Name>> type_aliases_;
1188     std::map<const Name*, Decl*, PtrCompare<Name>> declarations_;
1189     std::map<const Name*, Const*, PtrCompare<Name>> constants_;
1190 
1191     ErrorReporter* error_reporter_;
1192     Typespace* typespace_;
1193 
1194     uint32_t anon_counter_ = 0;
1195 };
1196 
1197 } // namespace flat
1198 } // namespace fidl
1199 
1200 #endif // ZIRCON_SYSTEM_HOST_FIDL_INCLUDE_FIDL_FLAT_AST_H_
1201