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#include "fidl/flat_ast.h" 6 7#include <assert.h> 8#include <stdio.h> 9 10#include <algorithm> 11#include <regex> 12#include <sstream> 13 14#include "fidl/attributes.h" 15#include "fidl/lexer.h" 16#include "fidl/names.h" 17#include "fidl/parser.h" 18#include "fidl/raw_ast.h" 19 20namespace fidl { 21namespace flat { 22 23namespace { 24 25class ScopeInsertResult { 26public: 27 explicit ScopeInsertResult(std::unique_ptr<SourceLocation> previous_occurance) 28 : previous_occurance_(std::move(previous_occurance)) {} 29 30 static ScopeInsertResult Ok() { return ScopeInsertResult(nullptr); } 31 static ScopeInsertResult FailureAt(SourceLocation previous) { 32 return ScopeInsertResult(std::make_unique<SourceLocation>(previous)); 33 } 34 35 bool ok() const { 36 return previous_occurance_ == nullptr; 37 } 38 39 const SourceLocation& previous_occurance() const { 40 assert(!ok()); 41 return *previous_occurance_; 42 } 43 44private: 45 std::unique_ptr<SourceLocation> previous_occurance_; 46}; 47 48template <typename T> 49class Scope { 50public: 51 ScopeInsertResult Insert(const T& t, SourceLocation location) { 52 auto iter = scope_.find(t); 53 if (iter != scope_.end()) { 54 return ScopeInsertResult::FailureAt(iter->second); 55 } else { 56 scope_.emplace(t, location); 57 return ScopeInsertResult::Ok(); 58 } 59 } 60 61 typename std::map<T, SourceLocation>::const_iterator begin() const { 62 return scope_.begin(); 63 } 64 65 typename std::map<T, SourceLocation>::const_iterator end() const { 66 return scope_.end(); 67 } 68 69private: 70 std::map<T, SourceLocation> scope_; 71}; 72 73struct MethodScope { 74 Scope<uint32_t> ordinals; 75 Scope<StringView> names; 76 Scope<const Interface*> interfaces; 77}; 78 79// A helper class to track when a Decl is compiling and compiled. 80class Compiling { 81public: 82 explicit Compiling(Decl* decl) 83 : decl_(decl) { 84 decl_->compiling = true; 85 } 86 ~Compiling() { 87 decl_->compiling = false; 88 decl_->compiled = true; 89 } 90 91private: 92 Decl* decl_; 93}; 94 95constexpr TypeShape kHandleTypeShape = TypeShape(4u, 4u, 0u, 1u); 96constexpr TypeShape kInt8TypeShape = TypeShape(1u, 1u); 97constexpr TypeShape kInt16TypeShape = TypeShape(2u, 2u); 98constexpr TypeShape kInt32TypeShape = TypeShape(4u, 4u); 99constexpr TypeShape kInt64TypeShape = TypeShape(8u, 8u); 100constexpr TypeShape kUint8TypeShape = TypeShape(1u, 1u); 101constexpr TypeShape kUint16TypeShape = TypeShape(2u, 2u); 102constexpr TypeShape kUint32TypeShape = TypeShape(4u, 4u); 103constexpr TypeShape kUint64TypeShape = TypeShape(8u, 8u); 104constexpr TypeShape kBoolTypeShape = TypeShape(1u, 1u); 105constexpr TypeShape kFloat32TypeShape = TypeShape(4u, 4u); 106constexpr TypeShape kFloat64TypeShape = TypeShape(8u, 8u); 107 108uint32_t AlignTo(uint64_t size, uint64_t alignment) { 109 auto mask = alignment - 1; 110 size += mask; 111 size &= ~mask; 112 if (size > std::numeric_limits<uint32_t>::max()) { 113 size = std::numeric_limits<uint32_t>::max(); 114 } 115 return size; 116} 117 118uint32_t ClampedMultiply(uint32_t a, uint32_t b) { 119 uint64_t product = (uint64_t)a * b; 120 return std::min(product, (uint64_t)std::numeric_limits<uint32_t>::max()); 121} 122 123uint32_t ClampedAdd(uint32_t a, uint32_t b) { 124 uint64_t sum = (uint64_t)a + b; 125 return std::min(sum, (uint64_t)std::numeric_limits<uint32_t>::max()); 126} 127 128TypeShape CStructTypeShape(std::vector<FieldShape*>* fields, uint32_t extra_handles = 0u) { 129 uint32_t size = 0u; 130 uint32_t alignment = 1u; 131 uint32_t depth = 0u; 132 uint32_t max_handles = 0u; 133 uint32_t max_out_of_line = 0u; 134 135 for (FieldShape* field : *fields) { 136 TypeShape typeshape = field->Typeshape(); 137 alignment = std::max(alignment, typeshape.Alignment()); 138 size = AlignTo(size, typeshape.Alignment()); 139 field->SetOffset(size); 140 size += typeshape.Size(); 141 depth = std::max(depth, typeshape.Depth()); 142 max_handles = ClampedAdd(max_handles, typeshape.MaxHandles()); 143 max_out_of_line = ClampedAdd(max_out_of_line, typeshape.MaxOutOfLine()); 144 } 145 146 max_handles = ClampedAdd(max_handles, extra_handles); 147 148 size = AlignTo(size, alignment); 149 return TypeShape(size, alignment, depth, max_handles, max_out_of_line); 150} 151 152TypeShape CUnionTypeShape(const std::vector<flat::Union::Member>& members) { 153 uint32_t size = 0u; 154 uint32_t alignment = 1u; 155 uint32_t depth = 0u; 156 uint32_t max_handles = 0u; 157 uint32_t max_out_of_line = 0u; 158 159 for (const auto& member : members) { 160 const auto& fieldshape = member.fieldshape; 161 size = std::max(size, fieldshape.Size()); 162 alignment = std::max(alignment, fieldshape.Alignment()); 163 depth = std::max(depth, fieldshape.Depth()); 164 max_handles = std::max(max_handles, fieldshape.Typeshape().MaxHandles()); 165 max_out_of_line = std::max(max_out_of_line, fieldshape.Typeshape().MaxOutOfLine()); 166 } 167 168 size = AlignTo(size, alignment); 169 return TypeShape(size, alignment, depth, max_handles, max_out_of_line); 170} 171 172TypeShape FidlStructTypeShape(std::vector<FieldShape*>* fields) { 173 return CStructTypeShape(fields); 174} 175 176TypeShape PointerTypeShape(TypeShape element, uint32_t max_element_count = 1u) { 177 // Because FIDL supports recursive data structures, we might not have 178 // computed the TypeShape for the element we're pointing to. In that case, 179 // the size will be zero and we'll use |numeric_limits<uint32_t>::max()| as 180 // the depth. We'll never see a zero size for a real TypeShape because empty 181 // structs are banned. 182 // 183 // We're careful to check for saturation before incrementing the depth 184 // because recursive data structures have a depth pegged at the numeric 185 // limit. 186 uint32_t depth = std::numeric_limits<uint32_t>::max(); 187 if (element.Size() > 0 && element.Depth() < std::numeric_limits<uint32_t>::max()) 188 depth = ClampedAdd(element.Depth(), 1); 189 190 // The element(s) will be stored out-of-line. 191 uint32_t elements_size = ClampedMultiply(element.Size(), max_element_count); 192 // Out-of-line data is aligned to 8 bytes. 193 elements_size = AlignTo(elements_size, 8); 194 // The elements may each carry their own out-of-line data. 195 uint32_t elements_out_of_line = ClampedMultiply(element.MaxOutOfLine(), max_element_count); 196 197 uint32_t max_handles = ClampedMultiply(element.MaxHandles(), max_element_count); 198 uint32_t max_out_of_line = ClampedAdd(elements_size, elements_out_of_line); 199 200 return TypeShape(8u, 8u, depth, max_handles, max_out_of_line); 201} 202 203TypeShape CEnvelopeTypeShape(TypeShape contained_type) { 204 auto packed_sizes_field = FieldShape(kUint64TypeShape); 205 auto pointer_type = FieldShape(PointerTypeShape(contained_type)); 206 std::vector<FieldShape*> header{&packed_sizes_field, &pointer_type}; 207 return CStructTypeShape(&header); 208} 209 210TypeShape CTableTypeShape(std::vector<TypeShape*>* fields, uint32_t extra_handles = 0u) { 211 uint32_t element_depth = 0u; 212 uint32_t max_handles = 0u; 213 uint32_t max_out_of_line = 0u; 214 uint32_t array_size = 0u; 215 for (auto field : *fields) { 216 if (field == nullptr) { 217 continue; 218 } 219 auto envelope = CEnvelopeTypeShape(*field); 220 element_depth = std::max(element_depth, envelope.Depth()); 221 array_size = ClampedAdd(array_size, envelope.Size()); 222 max_handles = ClampedAdd(max_handles, envelope.MaxHandles()); 223 max_out_of_line = ClampedAdd(max_out_of_line, envelope.MaxOutOfLine()); 224 assert(envelope.Alignment() == 8u); 225 } 226 auto pointer_element = TypeShape(array_size, 8u, 1 + element_depth, 227 max_handles, max_out_of_line); 228 auto num_fields = FieldShape(kUint32TypeShape); 229 auto data_field = FieldShape(PointerTypeShape(pointer_element)); 230 std::vector<FieldShape*> header{&num_fields, &data_field}; 231 return CStructTypeShape(&header, extra_handles); 232} 233 234TypeShape ArrayTypeShape(TypeShape element, uint32_t count) { 235 return TypeShape(element.Size() * count, 236 element.Alignment(), 237 element.Depth(), 238 ClampedMultiply(element.MaxHandles(), count)); 239} 240 241TypeShape VectorTypeShape(TypeShape element, uint32_t max_element_count) { 242 auto size = FieldShape(kUint64TypeShape); 243 auto data = FieldShape(PointerTypeShape(element, max_element_count)); 244 std::vector<FieldShape*> header{&size, &data}; 245 return CStructTypeShape(&header); 246} 247 248TypeShape StringTypeShape(uint32_t max_length) { 249 auto size = FieldShape(kUint64TypeShape); 250 auto data = FieldShape(PointerTypeShape(kUint8TypeShape, max_length)); 251 std::vector<FieldShape*> header{&size, &data}; 252 return CStructTypeShape(&header, 0); 253} 254 255TypeShape PrimitiveTypeShape(types::PrimitiveSubtype type) { 256 switch (type) { 257 case types::PrimitiveSubtype::kInt8: 258 return kInt8TypeShape; 259 case types::PrimitiveSubtype::kInt16: 260 return kInt16TypeShape; 261 case types::PrimitiveSubtype::kInt32: 262 return kInt32TypeShape; 263 case types::PrimitiveSubtype::kInt64: 264 return kInt64TypeShape; 265 case types::PrimitiveSubtype::kUint8: 266 return kUint8TypeShape; 267 case types::PrimitiveSubtype::kUint16: 268 return kUint16TypeShape; 269 case types::PrimitiveSubtype::kUint32: 270 return kUint32TypeShape; 271 case types::PrimitiveSubtype::kUint64: 272 return kUint64TypeShape; 273 case types::PrimitiveSubtype::kBool: 274 return kBoolTypeShape; 275 case types::PrimitiveSubtype::kFloat32: 276 return kFloat32TypeShape; 277 case types::PrimitiveSubtype::kFloat64: 278 return kFloat64TypeShape; 279 } 280} 281 282std::unique_ptr<PrimitiveType> MakePrimitiveType(const raw::PrimitiveType* primitive_type) { 283 return std::make_unique<PrimitiveType>(primitive_type->subtype); 284} 285 286} // namespace 287 288bool Decl::HasAttribute(fidl::StringView name) const { 289 if (!attributes) 290 return false; 291 return attributes->HasAttribute(name); 292} 293 294fidl::StringView Decl::GetAttribute(fidl::StringView name) const { 295 if (!attributes) 296 return fidl::StringView(); 297 for (const auto& attribute : attributes->attributes_->attributes_) { 298 if (StringView(attribute->name) == name) { 299 if (attribute->value != "") { 300 const auto& value = attribute->value; 301 return fidl::StringView(value.data(), value.size()); 302 } 303 // Don't search for another attribute with the same name. 304 break; 305 } 306 } 307 return fidl::StringView(); 308} 309 310std::string Decl::GetName() const { 311 return name.name().data(); 312} 313 314bool Interface::Method::Parameter::IsSimple() const { 315 switch (type->kind) { 316 case Type::Kind::kVector: { 317 auto vector_type = static_cast<VectorType*>(type.get()); 318 if (vector_type->element_count.Value() == Size::Max().Value()) 319 return false; 320 switch (vector_type->element_type->kind) { 321 case Type::Kind::kHandle: 322 case Type::Kind::kRequestHandle: 323 case Type::Kind::kPrimitive: 324 return true; 325 case Type::Kind::kArray: 326 case Type::Kind::kVector: 327 case Type::Kind::kString: 328 case Type::Kind::kIdentifier: 329 return false; 330 } 331 } 332 case Type::Kind::kString: { 333 auto string_type = static_cast<StringType*>(type.get()); 334 return string_type->max_size.Value() < Size::Max().Value(); 335 } 336 case Type::Kind::kArray: 337 case Type::Kind::kHandle: 338 case Type::Kind::kRequestHandle: 339 case Type::Kind::kPrimitive: 340 return fieldshape.Depth() == 0u; 341 case Type::Kind::kIdentifier: { 342 auto identifier_type = static_cast<IdentifierType*>(type.get()); 343 switch (identifier_type->nullability) { 344 case types::Nullability::kNullable: 345 // If the identifier is nullable, then we can handle a depth of 1 346 // because the secondary object is directly accessible. 347 return fieldshape.Depth() <= 1u; 348 case types::Nullability::kNonnullable: 349 return fieldshape.Depth() == 0u; 350 } 351 } 352 } 353} 354 355bool Libraries::Insert(std::unique_ptr<Library> library) { 356 std::vector<fidl::StringView> library_name = library->name(); 357 auto iter = all_libraries_.emplace(library_name, std::move(library)); 358 return iter.second; 359} 360 361bool Libraries::Lookup(const std::vector<StringView>& library_name, 362 Library** out_library) const { 363 auto iter = all_libraries_.find(library_name); 364 if (iter == all_libraries_.end()) { 365 return false; 366 } 367 368 *out_library = iter->second.get(); 369 return true; 370} 371 372bool Dependencies::Register(StringView filename, Library* dep_library, 373 const std::unique_ptr<raw::Identifier>& maybe_alias) { 374 auto library_name = dep_library->name(); 375 if (!InsertByName(filename, library_name, dep_library)) { 376 return false; 377 } 378 379 if (maybe_alias) { 380 std::vector<StringView> alias_name = {maybe_alias->location().data()}; 381 if (!InsertByName(filename, alias_name, dep_library)) { 382 return false; 383 } 384 } 385 386 dependencies_aggregate_.insert(dep_library); 387 388 return true; 389} 390 391bool Dependencies::InsertByName(StringView filename, const std::vector<StringView>& name, 392 Library* library) { 393 auto iter = dependencies_.find(filename); 394 if (iter == dependencies_.end()) { 395 dependencies_.emplace(filename, std::make_unique<ByName>()); 396 } 397 398 iter = dependencies_.find(filename); 399 assert(iter != dependencies_.end()); 400 401 auto insert = iter->second->emplace(name, library); 402 return insert.second; 403} 404 405bool Dependencies::Lookup(StringView filename, const std::vector<StringView>& name, 406 Library** out_library) { 407 auto iter1 = dependencies_.find(filename); 408 if (iter1 == dependencies_.end()) { 409 return false; 410 } 411 412 auto iter2 = iter1->second->find(name); 413 if (iter2 == iter1->second->end()) { 414 return false; 415 } 416 417 *out_library = iter2->second; 418 return true; 419} 420 421// Consuming the AST is primarily concerned with walking the tree and 422// flattening the representation. The AST's declaration nodes are 423// converted into the Library's foo_declaration structures. This means pulling 424// a struct declaration inside an interface out to the top level and 425// so on. 426 427std::string LibraryName(const Library* library, StringView separator) { 428 if (library != nullptr) { 429 return StringJoin(library->name(), separator); 430 } 431 return std::string(); 432} 433 434bool Library::Fail(StringView message) { 435 error_reporter_->ReportError(message); 436 return false; 437} 438 439bool Library::Fail(const SourceLocation& location, StringView message) { 440 error_reporter_->ReportError(location, message); 441 return false; 442} 443 444bool Library::CompileCompoundIdentifier(const raw::CompoundIdentifier* compound_identifier, 445 SourceLocation location, Name* name_out) { 446 const auto& components = compound_identifier->components; 447 assert(components.size() >= 1); 448 449 SourceLocation decl_name = components.back()->location(); 450 451 if (components.size() == 1) { 452 *name_out = Name(this, decl_name); 453 return true; 454 } 455 456 std::vector<StringView> library_name; 457 for (auto iter = components.begin(); 458 iter != components.end() - 1; 459 ++iter) { 460 library_name.push_back((*iter)->location().data()); 461 } 462 463 auto filename = location.source_file().filename(); 464 Library* dep_library = nullptr; 465 if (!dependencies_.Lookup(filename, library_name, &dep_library)) { 466 std::string message("Unknown dependent library "); 467 message += NameLibrary(library_name); 468 message += ". Did you require it with `using`?"; 469 const auto& location = components[0]->location(); 470 return Fail(location, message); 471 } 472 473 // Resolve the name. 474 *name_out = Name(dep_library, decl_name); 475 return true; 476} 477 478bool Library::ParseSize(std::unique_ptr<Constant> constant, Size* out_size) { 479 uint32_t value; 480 if (!ParseIntegerConstant(constant.get(), &value)) { 481 *out_size = Size(); 482 return false; 483 } 484 *out_size = Size(std::move(constant), value); 485 return true; 486} 487 488void Library::RegisterConst(Const* decl) { 489 const Name* name = &decl->name; 490 constants_.emplace(name, decl); 491 switch (decl->type->kind) { 492 case Type::Kind::kString: 493 string_constants_.emplace(name, decl); 494 break; 495 case Type::Kind::kPrimitive: 496 primitive_constants_.emplace(name, decl); 497 break; 498 default: 499 break; 500 } 501} 502 503bool Library::RegisterDecl(Decl* decl) { 504 const Name* name = &decl->name; 505 auto iter = declarations_.emplace(name, decl); 506 if (!iter.second) { 507 std::string message = "Name collision: "; 508 message.append(name->name().data()); 509 return Fail(*name, message); 510 } 511 return true; 512} 513 514bool Library::ConsumeConstant(std::unique_ptr<raw::Constant> raw_constant, SourceLocation location, 515 std::unique_ptr<Constant>* out_constant) { 516 switch (raw_constant->kind) { 517 case raw::Constant::Kind::kIdentifier: { 518 auto identifier = static_cast<raw::IdentifierConstant*>(raw_constant.get()); 519 Name name; 520 if (!CompileCompoundIdentifier(identifier->identifier.get(), location, &name)) { 521 return false; 522 } 523 *out_constant = std::make_unique<IdentifierConstant>(std::move(name)); 524 break; 525 } 526 case raw::Constant::Kind::kLiteral: { 527 auto literal = static_cast<raw::LiteralConstant*>(raw_constant.get()); 528 *out_constant = std::make_unique<LiteralConstant>(std::move(literal->literal)); 529 break; 530 } 531 } 532 return true; 533} 534 535bool Library::ConsumeType(std::unique_ptr<raw::Type> raw_type, SourceLocation location, 536 std::unique_ptr<Type>* out_type) { 537 switch (raw_type->kind) { 538 case raw::Type::Kind::kArray: { 539 auto array_type = static_cast<raw::ArrayType*>(raw_type.get()); 540 std::unique_ptr<Type> element_type; 541 if (!ConsumeType(std::move(array_type->element_type), location, &element_type)) 542 return false; 543 std::unique_ptr<Constant> constant; 544 if (!ConsumeConstant(std::move(array_type->element_count), location, &constant)) 545 return false; 546 Size element_count; 547 if (!ParseSize(std::move(constant), &element_count)) 548 return Fail(location, "Unable to parse array element count"); 549 uint32_t size; 550 if (__builtin_mul_overflow(element_count.Value(), element_type->size, &size)) { 551 return Fail(location, "The array's size overflows a uint32_t"); 552 } 553 *out_type = 554 std::make_unique<ArrayType>(size, std::move(element_type), std::move(element_count)); 555 break; 556 } 557 case raw::Type::Kind::kVector: { 558 auto vector_type = static_cast<raw::VectorType*>(raw_type.get()); 559 std::unique_ptr<Type> element_type; 560 if (!ConsumeType(std::move(vector_type->element_type), location, &element_type)) 561 return false; 562 Size element_count = Size::Max(); 563 if (vector_type->maybe_element_count) { 564 std::unique_ptr<Constant> constant; 565 if (!ConsumeConstant(std::move(vector_type->maybe_element_count), location, &constant)) 566 return false; 567 if (!ParseSize(std::move(constant), &element_count)) 568 return Fail(location, "Unable to parse vector size bound"); 569 } 570 *out_type = std::make_unique<VectorType>(std::move(element_type), std::move(element_count), 571 vector_type->nullability); 572 break; 573 } 574 case raw::Type::Kind::kString: { 575 auto string_type = static_cast<raw::StringType*>(raw_type.get()); 576 Size element_count = Size::Max(); 577 if (string_type->maybe_element_count) { 578 std::unique_ptr<Constant> constant; 579 if (!ConsumeConstant(std::move(string_type->maybe_element_count), location, &constant)) 580 return false; 581 if (!ParseSize(std::move(constant), &element_count)) 582 return Fail(location, "Unable to parse string size bound"); 583 } 584 *out_type = 585 std::make_unique<StringType>(std::move(element_count), string_type->nullability); 586 break; 587 } 588 case raw::Type::Kind::kHandle: { 589 auto handle_type = static_cast<raw::HandleType*>(raw_type.get()); 590 *out_type = std::make_unique<HandleType>(handle_type->subtype, handle_type->nullability); 591 break; 592 } 593 case raw::Type::Kind::kRequestHandle: { 594 auto request_type = static_cast<raw::RequestHandleType*>(raw_type.get()); 595 Name name; 596 if (!CompileCompoundIdentifier(request_type->identifier.get(), location, &name)) { 597 return false; 598 } 599 *out_type = std::make_unique<RequestHandleType>(std::move(name), request_type->nullability); 600 break; 601 } 602 case raw::Type::Kind::kPrimitive: { 603 auto primitive_type = static_cast<raw::PrimitiveType*>(raw_type.get()); 604 *out_type = MakePrimitiveType(primitive_type); 605 break; 606 } 607 case raw::Type::Kind::kIdentifier: { 608 auto identifier_type = static_cast<raw::IdentifierType*>(raw_type.get()); 609 Name name; 610 if (!CompileCompoundIdentifier(identifier_type->identifier.get(), location, &name)) { 611 return false; 612 } 613 auto primitive_type = LookupTypeAlias(name); 614 if (primitive_type != nullptr) { 615 *out_type = std::make_unique<PrimitiveType>(*primitive_type); 616 } else { 617 *out_type = std::make_unique<IdentifierType>(std::move(name), identifier_type->nullability); 618 } 619 break; 620 } 621 } 622 return true; 623} 624 625bool Library::ConsumeUsing(std::unique_ptr<raw::Using> using_directive) { 626 if (using_directive->maybe_primitive) 627 return ConsumeTypeAlias(std::move(using_directive)); 628 629 std::vector<StringView> library_name; 630 for (const auto& component : using_directive->using_path->components) { 631 library_name.push_back(component->location().data()); 632 } 633 634 Library* dep_library = nullptr; 635 if (!all_libraries_->Lookup(library_name, &dep_library)) { 636 std::string message("Could not find library named "); 637 message += NameLibrary(library_name); 638 message += ". Did you include its sources with --files?"; 639 const auto& location = using_directive->using_path->components[0]->location(); 640 return Fail(location, message); 641 } 642 643 auto filename = using_directive->location().source_file().filename(); 644 if (!dependencies_.Register(filename, dep_library, using_directive->maybe_alias)) { 645 std::string message("Library "); 646 message += NameLibrary(library_name); 647 message += " already imported. Did you require it twice?"; 648 return Fail(message); 649 } 650 651 // Import declarations, and type aliases of dependent library. 652 const auto& declarations = dep_library->declarations_; 653 declarations_.insert(declarations.begin(), declarations.end()); 654 const auto& type_aliases = dep_library->type_aliases_; 655 type_aliases_.insert(type_aliases.begin(), type_aliases.end()); 656 return true; 657} 658 659bool Library::ConsumeTypeAlias(std::unique_ptr<raw::Using> using_directive) { 660 assert(using_directive->maybe_primitive); 661 auto location = using_directive->using_path->components[0]->location(); 662 auto name = Name(this, location); 663 auto using_dir = std::make_unique<Using>(std::move(name), MakePrimitiveType(using_directive->maybe_primitive.get())); 664 type_aliases_.emplace(&using_dir->name, using_dir.get()); 665 using_.push_back(std::move(using_dir)); 666 return true; 667} 668 669bool Library::ConsumeConstDeclaration(std::unique_ptr<raw::ConstDeclaration> const_declaration) { 670 auto attributes = std::move(const_declaration->attributes); 671 auto location = const_declaration->identifier->location(); 672 auto name = Name(this, location); 673 std::unique_ptr<Type> type; 674 if (!ConsumeType(std::move(const_declaration->type), location, &type)) 675 return false; 676 677 std::unique_ptr<Constant> constant; 678 if (!ConsumeConstant(std::move(const_declaration->constant), location, &constant)) 679 return false; 680 681 const_declarations_.push_back(std::make_unique<Const>(std::move(attributes), std::move(name), 682 std::move(type), std::move(constant))); 683 auto decl = const_declarations_.back().get(); 684 RegisterConst(decl); 685 return RegisterDecl(decl); 686} 687 688bool Library::ConsumeEnumDeclaration(std::unique_ptr<raw::EnumDeclaration> enum_declaration) { 689 std::vector<Enum::Member> members; 690 for (auto& member : enum_declaration->members) { 691 auto location = member->identifier->location(); 692 std::unique_ptr<Constant> value; 693 if (!ConsumeConstant(std::move(member->value), location, &value)) 694 return false; 695 auto attributes = std::move(member->attributes); 696 members.emplace_back(location, std::move(value), std::move(attributes)); 697 } 698 auto type = types::PrimitiveSubtype::kUint32; 699 if (enum_declaration->maybe_subtype) 700 type = enum_declaration->maybe_subtype->subtype; 701 702 auto attributes = std::move(enum_declaration->attributes); 703 auto name = Name(this, enum_declaration->identifier->location()); 704 705 enum_declarations_.push_back( 706 std::make_unique<Enum>(std::move(attributes), std::move(name), type, std::move(members))); 707 return RegisterDecl(enum_declarations_.back().get()); 708} 709 710bool Library::ConsumeInterfaceDeclaration( 711 std::unique_ptr<raw::InterfaceDeclaration> interface_declaration) { 712 auto attributes = std::move(interface_declaration->attributes); 713 auto name = Name(this, interface_declaration->identifier->location()); 714 715 std::vector<Name> superinterfaces; 716 for (auto& superinterface : interface_declaration->superinterfaces) { 717 Name superinterface_name; 718 auto location = superinterface->components[0]->location(); 719 if (!CompileCompoundIdentifier(superinterface.get(), location, &superinterface_name)) { 720 return false; 721 } 722 superinterfaces.push_back(std::move(superinterface_name)); 723 } 724 725 std::vector<Interface::Method> methods; 726 for (auto& method : interface_declaration->methods) { 727 auto attributes = std::move(method->attributes); 728 auto ordinal_literal = std::move(method->ordinal); 729 uint32_t value; 730 if (!ParseOrdinal<decltype(value)>(ordinal_literal.get(), &value)) 731 return Fail(ordinal_literal->location(), "Unable to parse ordinal"); 732 if (value == 0u) 733 return Fail(ordinal_literal->location(), "Fidl ordinals cannot be 0"); 734 Ordinal ordinal(std::move(ordinal_literal), value); 735 736 SourceLocation method_name = method->identifier->location(); 737 738 std::unique_ptr<Interface::Method::Message> maybe_request; 739 if (method->maybe_request != nullptr) { 740 maybe_request.reset(new Interface::Method::Message()); 741 for (auto& parameter : method->maybe_request->parameter_list) { 742 SourceLocation parameter_name = parameter->identifier->location(); 743 std::unique_ptr<Type> type; 744 if (!ConsumeType(std::move(parameter->type), parameter_name, &type)) 745 return false; 746 maybe_request->parameters.emplace_back(std::move(type), std::move(parameter_name)); 747 } 748 } 749 750 std::unique_ptr<Interface::Method::Message> maybe_response; 751 if (method->maybe_response != nullptr) { 752 maybe_response.reset(new Interface::Method::Message()); 753 for (auto& parameter : method->maybe_response->parameter_list) { 754 SourceLocation parameter_name = parameter->identifier->location(); 755 std::unique_ptr<Type> type; 756 if (!ConsumeType(std::move(parameter->type), parameter_name, &type)) 757 return false; 758 maybe_response->parameters.emplace_back(std::move(type), parameter_name); 759 } 760 } 761 762 assert(maybe_request != nullptr || maybe_response != nullptr); 763 764 methods.emplace_back(std::move(attributes), 765 std::move(ordinal), 766 std::move(method_name), std::move(maybe_request), 767 std::move(maybe_response)); 768 } 769 770 interface_declarations_.push_back( 771 std::make_unique<Interface>(std::move(attributes), std::move(name), 772 std::move(superinterfaces), std::move(methods))); 773 return RegisterDecl(interface_declarations_.back().get()); 774} 775 776bool Library::ConsumeStructDeclaration(std::unique_ptr<raw::StructDeclaration> struct_declaration) { 777 auto attributes = std::move(struct_declaration->attributes); 778 auto name = Name(this, struct_declaration->identifier->location()); 779 780 std::vector<Struct::Member> members; 781 for (auto& member : struct_declaration->members) { 782 std::unique_ptr<Type> type; 783 auto location = member->identifier->location(); 784 if (!ConsumeType(std::move(member->type), location, &type)) 785 return false; 786 std::unique_ptr<Constant> maybe_default_value; 787 if (member->maybe_default_value != nullptr) { 788 if (!ConsumeConstant(std::move(member->maybe_default_value), location, 789 &maybe_default_value)) 790 return false; 791 } 792 auto attributes = std::move(member->attributes); 793 members.emplace_back(std::move(type), member->identifier->location(), 794 std::move(maybe_default_value), std::move(attributes)); 795 } 796 797 struct_declarations_.push_back( 798 std::make_unique<Struct>(std::move(attributes), std::move(name), std::move(members))); 799 return RegisterDecl(struct_declarations_.back().get()); 800} 801 802bool Library::ConsumeTableDeclaration(std::unique_ptr<raw::TableDeclaration> table_declaration) { 803 auto attributes = std::move(table_declaration->attributes); 804 auto name = Name(this, table_declaration->identifier->location()); 805 806 std::vector<Table::Member> members; 807 for (auto& member : table_declaration->members) { 808 auto ordinal_literal = std::move(member->ordinal); 809 uint32_t value; 810 if (!ParseOrdinal<decltype(value)>(ordinal_literal.get(), &value)) 811 return Fail(ordinal_literal->location(), "Unable to parse ordinal"); 812 if (value == 0u) 813 return Fail(ordinal_literal->location(), "Fidl ordinals cannot be 0"); 814 auto ordinal = std::make_unique<Ordinal>(std::move(ordinal_literal), value); 815 816 if (member->maybe_used) { 817 std::unique_ptr<Type> type; 818 if (!ConsumeType(std::move(member->maybe_used->type), member->location(), &type)) 819 return false; 820 std::unique_ptr<Constant> maybe_default_value; 821 if (member->maybe_used->maybe_default_value != nullptr) { 822 if (!ConsumeConstant(std::move(member->maybe_used->maybe_default_value), 823 member->location(), &maybe_default_value)) 824 return false; 825 } 826 if (type->nullability != types::Nullability::kNonnullable) { 827 return Fail(member->location(), "Table members cannot be nullable"); 828 } 829 auto attributes = std::move(member->maybe_used->attributes); 830 members.emplace_back(std::move(ordinal), std::move(type), 831 member->maybe_used->identifier->location(), 832 std::move(maybe_default_value), std::move(attributes)); 833 } else { 834 members.emplace_back(std::move(ordinal)); 835 } 836 } 837 838 table_declarations_.push_back( 839 std::make_unique<Table>(std::move(attributes), std::move(name), std::move(members))); 840 return RegisterDecl(table_declarations_.back().get()); 841} 842 843bool Library::ConsumeUnionDeclaration(std::unique_ptr<raw::UnionDeclaration> union_declaration) { 844 std::vector<Union::Member> members; 845 for (auto& member : union_declaration->members) { 846 auto location = member->identifier->location(); 847 std::unique_ptr<Type> type; 848 if (!ConsumeType(std::move(member->type), location, &type)) 849 return false; 850 auto attributes = std::move(member->attributes); 851 members.emplace_back(std::move(type), location, std::move(attributes)); 852 } 853 854 auto attributes = std::move(union_declaration->attributes); 855 auto name = Name(this, union_declaration->identifier->location()); 856 857 union_declarations_.push_back( 858 std::make_unique<Union>(std::move(attributes), std::move(name), std::move(members))); 859 return RegisterDecl(union_declarations_.back().get()); 860} 861 862bool Library::ConsumeFile(std::unique_ptr<raw::File> file) { 863 if (file->attributes) { 864 if (!attributes_) { 865 attributes_ = std::move(file->attributes); 866 } else { 867 for (auto& attribute : std::move(file->attributes)->attributes_->attributes_) { 868 auto attribute_name = attribute->name; 869 auto loc = attribute->location(); 870 if (!attributes_->Insert(std::move(attribute))) { 871 std::string message("Duplicate attribute with name '"); 872 message += attribute_name; 873 message += "'"; 874 return Fail(loc, message); 875 } 876 } 877 } 878 } 879 880 // All fidl files in a library should agree on the library name. 881 std::vector<StringView> new_name; 882 for (const auto& part : file->library_name->components) { 883 new_name.push_back(part->location().data()); 884 } 885 if (!library_name_.empty()) { 886 if (new_name != library_name_) { 887 return Fail(file->library_name->components[0]->location(), 888 "Two files in the library disagree about the name of the library"); 889 } 890 } else { 891 library_name_ = new_name; 892 } 893 894 auto using_list = std::move(file->using_list); 895 for (auto& using_directive : using_list) { 896 if (!ConsumeUsing(std::move(using_directive))) { 897 return false; 898 } 899 } 900 901 auto const_declaration_list = std::move(file->const_declaration_list); 902 for (auto& const_declaration : const_declaration_list) { 903 if (!ConsumeConstDeclaration(std::move(const_declaration))) { 904 return false; 905 } 906 } 907 908 auto enum_declaration_list = std::move(file->enum_declaration_list); 909 for (auto& enum_declaration : enum_declaration_list) { 910 if (!ConsumeEnumDeclaration(std::move(enum_declaration))) { 911 return false; 912 } 913 } 914 915 auto interface_declaration_list = std::move(file->interface_declaration_list); 916 for (auto& interface_declaration : interface_declaration_list) { 917 if (!ConsumeInterfaceDeclaration(std::move(interface_declaration))) { 918 return false; 919 } 920 } 921 922 auto struct_declaration_list = std::move(file->struct_declaration_list); 923 for (auto& struct_declaration : struct_declaration_list) { 924 if (!ConsumeStructDeclaration(std::move(struct_declaration))) { 925 return false; 926 } 927 } 928 929 auto table_declaration_list = std::move(file->table_declaration_list); 930 for (auto& table_declaration : table_declaration_list) { 931 if (!ConsumeTableDeclaration(std::move(table_declaration))) { 932 return false; 933 } 934 } 935 936 auto union_declaration_list = std::move(file->union_declaration_list); 937 for (auto& union_declaration : union_declaration_list) { 938 if (!ConsumeUnionDeclaration(std::move(union_declaration))) { 939 return false; 940 } 941 } 942 943 return true; 944} 945 946// Library resolution is concerned with resolving identifiers to their 947// declarations, and with computing type sizes and alignments. 948 949bool Library::TypecheckString(const IdentifierConstant* identifier) { 950 auto iter = string_constants_.find(&identifier->name); 951 if (iter == string_constants_.end()) 952 return Fail(identifier->name.name(), "Unable to find string constant"); 953 // TODO(kulakowski) Check string bounds. 954 return true; 955} 956 957bool Library::TypecheckPrimitive(const IdentifierConstant* identifier) { 958 auto iter = primitive_constants_.find(&identifier->name); 959 if (iter == primitive_constants_.end()) 960 return Fail(identifier->name.name(), "Unable to find primitive constant"); 961 // TODO(kulakowski) Check numeric values. 962 return true; 963} 964 965bool Library::TypecheckConst(const Const* const_declaration) { 966 auto type = const_declaration->type.get(); 967 auto constant = const_declaration->value.get(); 968 switch (type->kind) { 969 case Type::Kind::kArray: 970 return Fail("Tried to generate an array constant"); 971 case Type::Kind::kVector: 972 return Fail("Tried to generate an vector constant"); 973 case Type::Kind::kHandle: 974 return Fail("Tried to generate a handle constant"); 975 case Type::Kind::kRequestHandle: 976 return Fail("Tried to generate a request handle constant"); 977 case Type::Kind::kString: { 978 switch (constant->kind) { 979 case Constant::Kind::kIdentifier: { 980 auto identifier_constant = static_cast<const IdentifierConstant*>(constant); 981 return TypecheckString(identifier_constant); 982 } 983 case Constant::Kind::kLiteral: { 984 auto literal_constant = static_cast<const LiteralConstant*>(constant); 985 switch (literal_constant->literal->kind) { 986 case raw::Literal::Kind::kString: 987 return true; 988 case raw::Literal::Kind::kNumeric: 989 return Fail("Tried to assign a numeric literal into a string"); 990 case raw::Literal::Kind::kTrue: 991 case raw::Literal::Kind::kFalse: 992 return Fail("Tried to assign a bool literal into a string"); 993 } 994 } 995 } 996 } 997 case Type::Kind::kPrimitive: { 998 auto primitive_type = static_cast<const PrimitiveType*>(type); 999 switch (constant->kind) { 1000 case Constant::Kind::kIdentifier: { 1001 auto identifier_constant = static_cast<const IdentifierConstant*>(constant); 1002 return TypecheckPrimitive(identifier_constant); 1003 } 1004 case Constant::Kind::kLiteral: { 1005 auto literal_constant = static_cast<const LiteralConstant*>(constant); 1006 switch (literal_constant->literal->kind) { 1007 case raw::Literal::Kind::kString: 1008 return Fail("Tried to assign a string literal to a numeric constant"); 1009 case raw::Literal::Kind::kNumeric: 1010 // TODO(kulakowski) Check the constants of numbers. 1011 switch (primitive_type->subtype) { 1012 case types::PrimitiveSubtype::kUint8: 1013 case types::PrimitiveSubtype::kUint16: 1014 case types::PrimitiveSubtype::kUint32: 1015 case types::PrimitiveSubtype::kUint64: 1016 case types::PrimitiveSubtype::kInt8: 1017 case types::PrimitiveSubtype::kInt16: 1018 case types::PrimitiveSubtype::kInt32: 1019 case types::PrimitiveSubtype::kInt64: 1020 case types::PrimitiveSubtype::kFloat32: 1021 case types::PrimitiveSubtype::kFloat64: 1022 return true; 1023 case types::PrimitiveSubtype::kBool: 1024 return Fail("Tried to assign a numeric literal into a bool"); 1025 } 1026 case raw::Literal::Kind::kTrue: 1027 case raw::Literal::Kind::kFalse: 1028 switch (primitive_type->subtype) { 1029 case types::PrimitiveSubtype::kBool: 1030 return true; 1031 case types::PrimitiveSubtype::kUint8: 1032 case types::PrimitiveSubtype::kUint16: 1033 case types::PrimitiveSubtype::kUint32: 1034 case types::PrimitiveSubtype::kUint64: 1035 case types::PrimitiveSubtype::kInt8: 1036 case types::PrimitiveSubtype::kInt16: 1037 case types::PrimitiveSubtype::kInt32: 1038 case types::PrimitiveSubtype::kInt64: 1039 case types::PrimitiveSubtype::kFloat32: 1040 case types::PrimitiveSubtype::kFloat64: 1041 return Fail("Tried to assign a bool into a numeric type"); 1042 } 1043 } 1044 } 1045 } 1046 } 1047 case Type::Kind::kIdentifier: { 1048 auto identifier_type = static_cast<const IdentifierType*>(type); 1049 auto decl = LookupDeclByType(identifier_type, LookupOption::kIgnoreNullable); 1050 switch (decl->kind) { 1051 case Decl::Kind::kConst: 1052 assert(false && "const declarations don't make types!"); 1053 return false; 1054 case Decl::Kind::kEnum: 1055 return true; 1056 case Decl::Kind::kInterface: 1057 return Fail("Tried to create a const declaration of interface type"); 1058 case Decl::Kind::kStruct: 1059 return Fail("Tried to create a const declaration of struct type"); 1060 case Decl::Kind::kTable: 1061 return Fail("Tried to create a const declaration of table type"); 1062 case Decl::Kind::kUnion: 1063 return Fail("Tried to create a const declaration of union type"); 1064 } 1065 } 1066 } 1067} 1068 1069Decl* Library::LookupConstant(const Type* type, const Name& name) { 1070 auto decl = LookupDeclByType(type, LookupOption::kIgnoreNullable); 1071 if (decl == nullptr) { 1072 // This wasn't a named type. Thus we are looking up a 1073 // top-level constant, of string or primitive type. 1074 assert(type->kind == Type::Kind::kString || type->kind == Type::Kind::kPrimitive); 1075 auto iter = constants_.find(&name); 1076 if (iter == constants_.end()) { 1077 return nullptr; 1078 } 1079 return iter->second; 1080 } 1081 // We must otherwise be looking for an enum member. 1082 if (decl->kind != Decl::Kind::kEnum) { 1083 return nullptr; 1084 } 1085 auto enum_decl = static_cast<Enum*>(decl); 1086 for (auto& member : enum_decl->members) { 1087 if (member.name.data() == name.name().data()) { 1088 return enum_decl; 1089 } 1090 } 1091 // The enum didn't have a member of that name! 1092 return nullptr; 1093} 1094 1095PrimitiveType* Library::LookupTypeAlias(const Name& name) const { 1096 auto it = type_aliases_.find(&name); 1097 if (it == type_aliases_.end()) 1098 return nullptr; 1099 return it->second->type.get(); 1100} 1101 1102Decl* Library::LookupDeclByType(const Type* type, LookupOption option) const { 1103 for (;;) { 1104 switch (type->kind) { 1105 case flat::Type::Kind::kString: 1106 case flat::Type::Kind::kHandle: 1107 case flat::Type::Kind::kRequestHandle: 1108 case flat::Type::Kind::kPrimitive: 1109 return nullptr; 1110 case flat::Type::Kind::kVector: { 1111 type = static_cast<const flat::VectorType*>(type)->element_type.get(); 1112 continue; 1113 } 1114 case flat::Type::Kind::kArray: { 1115 type = static_cast<const flat::ArrayType*>(type)->element_type.get(); 1116 continue; 1117 } 1118 case flat::Type::Kind::kIdentifier: { 1119 auto identifier_type = static_cast<const flat::IdentifierType*>(type); 1120 if (identifier_type->nullability == types::Nullability::kNullable && option == LookupOption::kIgnoreNullable) { 1121 return nullptr; 1122 } 1123 return LookupDeclByName(identifier_type->name); 1124 } 1125 } 1126 } 1127} 1128 1129Decl* Library::LookupDeclByName(const Name& name) const { 1130 auto iter = declarations_.find(&name); 1131 if (iter == declarations_.end()) { 1132 return nullptr; 1133 } 1134 return iter->second; 1135} 1136 1137// An edge from D1 to D2 means that a C needs to see the declaration 1138// of D1 before the declaration of D2. For instance, given the fidl 1139// struct D2 { D1 d; }; 1140// struct D1 { int32 x; }; 1141// D1 has an edge pointing to D2. Note that struct and union pointers, 1142// unlike inline structs or unions, do not have dependency edges. 1143bool Library::DeclDependencies(Decl* decl, std::set<Decl*>* out_edges) { 1144 std::set<Decl*> edges; 1145 auto maybe_add_decl = [this, &edges](const Type* type, LookupOption option) { 1146 auto type_decl = LookupDeclByType(type, option); 1147 if (type_decl != nullptr) { 1148 edges.insert(type_decl); 1149 } 1150 }; 1151 auto maybe_add_name = [this, &edges](const Name& name) { 1152 auto type_decl = LookupDeclByName(name); 1153 if (type_decl != nullptr) { 1154 edges.insert(type_decl); 1155 } 1156 }; 1157 auto maybe_add_constant = [this, &edges](const Type* type, const Constant* constant) -> bool { 1158 switch (constant->kind) { 1159 case Constant::Kind::kIdentifier: { 1160 auto identifier = static_cast<const flat::IdentifierConstant*>(constant); 1161 auto decl = LookupConstant(type, identifier->name); 1162 if (decl == nullptr) { 1163 std::string message("Unable to find the constant named: "); 1164 message += identifier->name.name().data(); 1165 return Fail(identifier->name, message.data()); 1166 } 1167 edges.insert(decl); 1168 break; 1169 } 1170 case Constant::Kind::kLiteral: { 1171 // Literals have no dependencies on other declarations. 1172 break; 1173 } 1174 } 1175 return true; 1176 }; 1177 switch (decl->kind) { 1178 case Decl::Kind::kConst: { 1179 auto const_decl = static_cast<const Const*>(decl); 1180 if (!maybe_add_constant(const_decl->type.get(), const_decl->value.get())) 1181 return false; 1182 break; 1183 } 1184 case Decl::Kind::kEnum: { 1185 break; 1186 } 1187 case Decl::Kind::kInterface: { 1188 auto interface_decl = static_cast<const Interface*>(decl); 1189 for (const auto& superinterface : interface_decl->superinterfaces) { 1190 maybe_add_name(superinterface); 1191 } 1192 for (const auto& method : interface_decl->methods) { 1193 if (method.maybe_request != nullptr) { 1194 for (const auto& parameter : method.maybe_request->parameters) { 1195 maybe_add_decl(parameter.type.get(), LookupOption::kIncludeNullable); 1196 } 1197 } 1198 if (method.maybe_response != nullptr) { 1199 for (const auto& parameter : method.maybe_response->parameters) { 1200 maybe_add_decl(parameter.type.get(), LookupOption::kIncludeNullable); 1201 } 1202 } 1203 } 1204 break; 1205 } 1206 case Decl::Kind::kStruct: { 1207 auto struct_decl = static_cast<const Struct*>(decl); 1208 for (const auto& member : struct_decl->members) { 1209 maybe_add_decl(member.type.get(), LookupOption::kIgnoreNullable); 1210 if (member.maybe_default_value) { 1211 if (!maybe_add_constant(member.type.get(), member.maybe_default_value.get())) 1212 return false; 1213 } 1214 } 1215 break; 1216 } 1217 case Decl::Kind::kTable: { 1218 auto table_decl = static_cast<const Table*>(decl); 1219 for (const auto& member : table_decl->members) { 1220 if (!member.maybe_used) 1221 continue; 1222 maybe_add_decl(member.maybe_used->type.get(), LookupOption::kIgnoreNullable); 1223 if (member.maybe_used->maybe_default_value) { 1224 if (!maybe_add_constant(member.maybe_used->type.get(), 1225 member.maybe_used->maybe_default_value.get())) 1226 return false; 1227 } 1228 } 1229 break; 1230 } 1231 case Decl::Kind::kUnion: { 1232 auto union_decl = static_cast<const Union*>(decl); 1233 for (const auto& member : union_decl->members) { 1234 maybe_add_decl(member.type.get(), LookupOption::kIgnoreNullable); 1235 } 1236 break; 1237 } 1238 } 1239 *out_edges = std::move(edges); 1240 return true; 1241} 1242 1243namespace { 1244// To compare two Decl's in the same library, it suffices to compare the unqualified names of the Decl's. 1245struct CmpDeclInLibrary { 1246 bool operator()(const Decl* a, const Decl* b) const { 1247 assert(a->name != b->name || a == b); 1248 return a->name < b->name; 1249 } 1250}; 1251} // namespace 1252 1253bool Library::SortDeclarations() { 1254 // |degree| is the number of undeclared dependencies for each decl. 1255 std::map<Decl*, uint32_t, CmpDeclInLibrary> degrees; 1256 // |inverse_dependencies| records the decls that depend on each decl. 1257 std::map<Decl*, std::vector<Decl*>, CmpDeclInLibrary> inverse_dependencies; 1258 for (auto& name_and_decl : declarations_) { 1259 Decl* decl = name_and_decl.second; 1260 degrees[decl] = 0u; 1261 } 1262 for (auto& name_and_decl : declarations_) { 1263 Decl* decl = name_and_decl.second; 1264 std::set<Decl*> deps; 1265 if (!DeclDependencies(decl, &deps)) 1266 return false; 1267 degrees[decl] += deps.size(); 1268 for (Decl* dep : deps) { 1269 inverse_dependencies[dep].push_back(decl); 1270 } 1271 } 1272 1273 // Start with all decls that have no incoming edges. 1274 std::vector<Decl*> decls_without_deps; 1275 for (const auto& decl_and_degree : degrees) { 1276 if (decl_and_degree.second == 0u) { 1277 decls_without_deps.push_back(decl_and_degree.first); 1278 } 1279 } 1280 1281 while (!decls_without_deps.empty()) { 1282 // Pull one out of the queue. 1283 auto decl = decls_without_deps.back(); 1284 decls_without_deps.pop_back(); 1285 assert(degrees[decl] == 0u); 1286 declaration_order_.push_back(decl); 1287 1288 // Decrement the incoming degree of all the other decls it 1289 // points to. 1290 auto& inverse_deps = inverse_dependencies[decl]; 1291 for (Decl* inverse_dep : inverse_deps) { 1292 uint32_t& degree = degrees[inverse_dep]; 1293 assert(degree != 0u); 1294 degree -= 1; 1295 if (degree == 0u) 1296 decls_without_deps.push_back(inverse_dep); 1297 } 1298 } 1299 1300 if (declaration_order_.size() != degrees.size()) { 1301 // We didn't visit all the edges! There was a cycle. 1302 return Fail("There is an includes-cycle in declarations"); 1303 } 1304 1305 return true; 1306} 1307 1308bool Library::CompileConst(Const* const_declaration) { 1309 Compiling guard(const_declaration); 1310 TypeShape typeshape; 1311 if (!CompileType(const_declaration->type.get(), &typeshape)) { 1312 return false; 1313 } 1314 if (!TypecheckConst(const_declaration)) { 1315 return false; 1316 } 1317 return true; 1318} 1319 1320bool Library::CompileEnum(Enum* enum_declaration) { 1321 Compiling guard(enum_declaration); 1322 switch (enum_declaration->type) { 1323 case types::PrimitiveSubtype::kInt8: 1324 case types::PrimitiveSubtype::kInt16: 1325 case types::PrimitiveSubtype::kInt32: 1326 case types::PrimitiveSubtype::kInt64: 1327 case types::PrimitiveSubtype::kUint8: 1328 case types::PrimitiveSubtype::kUint16: 1329 case types::PrimitiveSubtype::kUint32: 1330 case types::PrimitiveSubtype::kUint64: 1331 // These are allowed as enum subtypes. Compile the size and alignment. 1332 enum_declaration->typeshape = PrimitiveTypeShape(enum_declaration->type); 1333 break; 1334 1335 case types::PrimitiveSubtype::kBool: 1336 case types::PrimitiveSubtype::kFloat32: 1337 case types::PrimitiveSubtype::kFloat64: 1338 // These are not allowed as enum subtypes. 1339 return Fail(*enum_declaration, "Enums cannot be bools, statuses, or floats"); 1340 } 1341 1342 // TODO(TO-702) Validate values. 1343 return true; 1344} 1345 1346bool Library::CompileInterface(Interface* interface_declaration) { 1347 Compiling guard(interface_declaration); 1348 MethodScope method_scope; 1349 auto CheckScopes = [this, &interface_declaration, &method_scope](const Interface* interface, auto Visitor) -> bool { 1350 for (const auto& name : interface->superinterfaces) { 1351 auto decl = LookupDeclByName(name); 1352 if (decl == nullptr) 1353 return Fail(name, "There is no declaration with this name"); 1354 if (decl->kind != Decl::Kind::kInterface) 1355 return Fail(name, "This superinterface declaration is not an interface"); 1356 auto superinterface = static_cast<const Interface*>(decl); 1357 if (method_scope.interfaces.Insert(superinterface, superinterface->name.name()).ok()) { 1358 if (!Visitor(superinterface, Visitor)) 1359 return false; 1360 } else { 1361 // Otherwise we have already seen this interface in 1362 // the inheritance graph. 1363 } 1364 } 1365 for (const auto& method : interface->methods) { 1366 auto name_result = method_scope.names.Insert(method.name.data(), method.name); 1367 if (!name_result.ok()) 1368 return Fail(method.name, 1369 "Multiple methods with the same name in an interface; last occurance was at " + 1370 name_result.previous_occurance().position()); 1371 auto ordinal_result = method_scope.ordinals.Insert(method.ordinal.Value(), method.name); 1372 if (!ordinal_result.ok()) 1373 return Fail(method.name, 1374 "Mulitple methods with the same ordinal in an interface; last occurance was at " + 1375 ordinal_result.previous_occurance().position()); 1376 1377 // Add a pointer to this method to the interface_declarations list. 1378 interface_declaration->all_methods.push_back(&method); 1379 } 1380 return true; 1381 }; 1382 if (!CheckScopes(interface_declaration, CheckScopes)) 1383 return false; 1384 1385 for (auto& method : interface_declaration->methods) { 1386 auto CreateMessage = [&](Interface::Method::Message* message) -> bool { 1387 Scope<StringView> scope; 1388 auto header_field_shape = FieldShape(TypeShape(16u, 4u)); 1389 std::vector<FieldShape*> message_struct; 1390 message_struct.push_back(&header_field_shape); 1391 for (auto& param : message->parameters) { 1392 if (!scope.Insert(param.name.data(), param.name).ok()) 1393 return Fail(param.name, "Multiple parameters with the same name in a method"); 1394 if (!CompileType(param.type.get(), ¶m.fieldshape.Typeshape())) 1395 return false; 1396 message_struct.push_back(¶m.fieldshape); 1397 } 1398 message->typeshape = FidlStructTypeShape(&message_struct); 1399 return true; 1400 }; 1401 if (method.maybe_request) { 1402 if (!CreateMessage(method.maybe_request.get())) 1403 return false; 1404 } 1405 if (method.maybe_response) { 1406 if (!CreateMessage(method.maybe_response.get())) 1407 return false; 1408 } 1409 } 1410 1411 if (HasSimpleLayout(interface_declaration)) { 1412 for (const auto& method_pointer : interface_declaration->all_methods) { 1413 auto CheckSimpleMessage = [&](const Interface::Method::Message* message) -> bool { 1414 for (const auto& parameter : message->parameters) { 1415 if (!parameter.IsSimple()) 1416 return Fail(parameter.name, "Non-simple parameter in interface with [Layout=\"Simple\"]"); 1417 } 1418 return true; 1419 }; 1420 if (method_pointer->maybe_request) { 1421 if (!CheckSimpleMessage(method_pointer->maybe_request.get())) 1422 return false; 1423 } 1424 if (method_pointer->maybe_response) { 1425 if (!CheckSimpleMessage(method_pointer->maybe_response.get())) 1426 return false; 1427 } 1428 } 1429 } 1430 1431 return true; 1432} 1433 1434bool Library::CompileStruct(Struct* struct_declaration) { 1435 Compiling guard(struct_declaration); 1436 Scope<StringView> scope; 1437 std::vector<FieldShape*> fidl_struct; 1438 1439 uint32_t max_member_handles = 0; 1440 for (auto& member : struct_declaration->members) { 1441 auto name_result = scope.Insert(member.name.data(), member.name); 1442 if (!name_result.ok()) 1443 return Fail(member.name, 1444 "Multiple struct fields with the same name; previous was at " + 1445 name_result.previous_occurance().position()); 1446 if (!CompileType(member.type.get(), &member.fieldshape.Typeshape())) 1447 return false; 1448 fidl_struct.push_back(&member.fieldshape); 1449 } 1450 1451 if (struct_declaration->recursive) { 1452 max_member_handles = std::numeric_limits<uint32_t>::max(); 1453 } else { 1454 // Member handles will be counted by CStructTypeShape. 1455 max_member_handles = 0; 1456 } 1457 1458 struct_declaration->typeshape = CStructTypeShape(&fidl_struct, max_member_handles); 1459 1460 return true; 1461} 1462 1463bool Library::CompileTable(Table* table_declaration) { 1464 Compiling guard(table_declaration); 1465 Scope<StringView> name_scope; 1466 Scope<uint32_t> ordinal_scope; 1467 1468 uint32_t max_member_handles = 0; 1469 for (auto& member : table_declaration->members) { 1470 auto ordinal_result = ordinal_scope.Insert(member.ordinal->Value(), member.ordinal->source_element()->location()); 1471 if (!ordinal_result.ok()) 1472 return Fail(member.ordinal->source_element()->location(), 1473 "Multiple table fields with the same ordinal; previous was at " + 1474 ordinal_result.previous_occurance().position()); 1475 if (member.maybe_used) { 1476 auto name_result = name_scope.Insert(member.maybe_used->name.data(), member.maybe_used->name); 1477 if (!name_result.ok()) 1478 return Fail(member.maybe_used->name, 1479 "Multiple table fields with the same name; previous was at " + 1480 name_result.previous_occurance().position()); 1481 if (!CompileType(member.maybe_used->type.get(), &member.maybe_used->typeshape)) 1482 return false; 1483 } 1484 } 1485 1486 uint32_t last_ordinal_seen = 0; 1487 for (const auto& ordinal_and_loc : ordinal_scope) { 1488 if (ordinal_and_loc.first != last_ordinal_seen + 1) { 1489 return Fail(ordinal_and_loc.second, 1490 "Missing ordinal (table ordinals do not form a dense space)"); 1491 } 1492 last_ordinal_seen = ordinal_and_loc.first; 1493 } 1494 1495 if (table_declaration->recursive) { 1496 max_member_handles = std::numeric_limits<uint32_t>::max(); 1497 } else { 1498 // Member handles will be counted by CTableTypeShape. 1499 max_member_handles = 0; 1500 } 1501 1502 std::vector<TypeShape*> fields(table_declaration->members.size()); 1503 for (auto& member : table_declaration->members) { 1504 if (member.maybe_used) { 1505 fields[member.ordinal->Value() - 1] = &member.maybe_used->typeshape; 1506 } 1507 } 1508 1509 table_declaration->typeshape = CTableTypeShape(&fields, max_member_handles); 1510 1511 return true; 1512} 1513 1514bool Library::CompileUnion(Union* union_declaration) { 1515 Compiling guard(union_declaration); 1516 Scope<StringView> scope; 1517 for (auto& member : union_declaration->members) { 1518 auto name_result = scope.Insert(member.name.data(), member.name); 1519 if (!name_result.ok()) 1520 return Fail(member.name, 1521 "Multiple union members with the same name; previous was at " + 1522 name_result.previous_occurance().position()); 1523 if (!CompileType(member.type.get(), &member.fieldshape.Typeshape())) 1524 return false; 1525 } 1526 1527 auto tag = FieldShape(kUint32TypeShape); 1528 union_declaration->membershape = FieldShape(CUnionTypeShape(union_declaration->members)); 1529 uint32_t extra_handles = 0; 1530 if (union_declaration->recursive && union_declaration->membershape.MaxHandles()) { 1531 extra_handles = std::numeric_limits<uint32_t>::max(); 1532 } 1533 std::vector<FieldShape*> fidl_union = {&tag, &union_declaration->membershape}; 1534 union_declaration->typeshape = CStructTypeShape(&fidl_union, extra_handles); 1535 1536 // This is either 4 or 8, depending on whether any union members 1537 // have alignment 8. 1538 auto offset = union_declaration->membershape.Offset(); 1539 for (auto& member : union_declaration->members) { 1540 member.fieldshape.SetOffset(offset); 1541 } 1542 1543 return true; 1544} 1545 1546bool Library::CompileLibraryName() { 1547 const std::regex pattern("^[a-z][a-z0-9]*$"); 1548 for (const auto& part_view : library_name_) { 1549 std::string part = part_view; 1550 if (!std::regex_match(part, pattern)) { 1551 return Fail("Invalid library name part " + part); 1552 } 1553 } 1554 return true; 1555} 1556 1557bool Library::Compile() { 1558 for (const auto& dep_library : dependencies_.dependencies()) { 1559 constants_.insert(dep_library->constants_.begin(), dep_library->constants_.end()); 1560 } 1561 1562 // Verify that the library's name is valid. 1563 if (!CompileLibraryName()) { 1564 return false; 1565 } 1566 1567 if (!SortDeclarations()) { 1568 return false; 1569 } 1570 1571 // We process declarations in topologically sorted order. For 1572 // example, we process a struct member's type before the entire 1573 // struct. 1574 for (Decl* decl : declaration_order_) { 1575 switch (decl->kind) { 1576 case Decl::Kind::kConst: { 1577 auto const_decl = static_cast<Const*>(decl); 1578 if (!CompileConst(const_decl)) { 1579 return false; 1580 } 1581 break; 1582 } 1583 case Decl::Kind::kEnum: { 1584 auto enum_decl = static_cast<Enum*>(decl); 1585 if (!CompileEnum(enum_decl)) { 1586 return false; 1587 } 1588 break; 1589 } 1590 case Decl::Kind::kInterface: { 1591 auto interface_decl = static_cast<Interface*>(decl); 1592 if (!CompileInterface(interface_decl)) { 1593 return false; 1594 } 1595 break; 1596 } 1597 case Decl::Kind::kStruct: { 1598 auto struct_decl = static_cast<Struct*>(decl); 1599 if (!CompileStruct(struct_decl)) { 1600 return false; 1601 } 1602 break; 1603 } 1604 case Decl::Kind::kTable: { 1605 auto table_decl = static_cast<Table*>(decl); 1606 if (!CompileTable(table_decl)) { 1607 return false; 1608 } 1609 break; 1610 } 1611 case Decl::Kind::kUnion: { 1612 auto union_decl = static_cast<Union*>(decl); 1613 if (!CompileUnion(union_decl)) { 1614 return false; 1615 } 1616 break; 1617 } 1618 default: 1619 abort(); 1620 } 1621 assert(!decl->compiling); 1622 assert(decl->compiled); 1623 } 1624 1625 return true; 1626} 1627 1628bool Library::CompileArrayType(flat::ArrayType* array_type, TypeShape* out_typeshape) { 1629 TypeShape element_typeshape; 1630 if (!CompileType(array_type->element_type.get(), &element_typeshape)) 1631 return false; 1632 *out_typeshape = ArrayTypeShape(element_typeshape, array_type->element_count.Value()); 1633 return true; 1634} 1635 1636bool Library::CompileVectorType(flat::VectorType* vector_type, TypeShape* out_typeshape) { 1637 // All we need from the element typeshape is the maximum number of handles. 1638 TypeShape element_typeshape; 1639 if (!CompileType(vector_type->element_type.get(), &element_typeshape)) 1640 return false; 1641 uint32_t max_element_count = vector_type->element_count.Value(); 1642 if (max_element_count == Size::Max().Value()) { 1643 // No upper bound specified on vector. 1644 max_element_count = std::numeric_limits<uint32_t>::max(); 1645 } 1646 *out_typeshape = VectorTypeShape(element_typeshape, max_element_count); 1647 return true; 1648} 1649 1650bool Library::CompileStringType(flat::StringType* string_type, TypeShape* out_typeshape) { 1651 *out_typeshape = StringTypeShape(string_type->max_size.Value()); 1652 return true; 1653} 1654 1655bool Library::CompileHandleType(flat::HandleType* handle_type, TypeShape* out_typeshape) { 1656 // Nothing to check. 1657 *out_typeshape = kHandleTypeShape; 1658 return true; 1659} 1660 1661bool Library::CompileRequestHandleType(flat::RequestHandleType* request_type, 1662 TypeShape* out_typeshape) { 1663 auto named_decl = LookupDeclByName(request_type->name); 1664 if (!named_decl || named_decl->kind != Decl::Kind::kInterface) { 1665 std::string message = "Undefined reference \""; 1666 message.append(request_type->name.name().data()); 1667 message.append("\" in request handle name"); 1668 return Fail(request_type->name, message); 1669 } 1670 1671 *out_typeshape = kHandleTypeShape; 1672 return true; 1673} 1674 1675bool Library::CompilePrimitiveType(flat::PrimitiveType* primitive_type, TypeShape* out_typeshape) { 1676 *out_typeshape = PrimitiveTypeShape(primitive_type->subtype); 1677 return true; 1678} 1679 1680bool Library::CompileIdentifierType(flat::IdentifierType* identifier_type, 1681 TypeShape* out_typeshape) { 1682 TypeShape typeshape; 1683 1684 auto named_decl = LookupDeclByName(identifier_type->name); 1685 if (!named_decl) { 1686 std::string message("Undefined reference \""); 1687 message.append(identifier_type->name.name().data()); 1688 message.append("\" in identifier type name"); 1689 return Fail(identifier_type->name, message); 1690 } 1691 1692 switch (named_decl->kind) { 1693 case Decl::Kind::kConst: { 1694 // A constant isn't a type! 1695 return Fail(identifier_type->name, 1696 "The name of a constant was used where a type was expected"); 1697 } 1698 case Decl::Kind::kEnum: { 1699 if (identifier_type->nullability == types::Nullability::kNullable) { 1700 // Enums aren't nullable! 1701 return Fail(identifier_type->name, "An enum was referred to as 'nullable'"); 1702 } else { 1703 typeshape = static_cast<const Enum*>(named_decl)->typeshape; 1704 } 1705 break; 1706 } 1707 case Decl::Kind::kInterface: { 1708 typeshape = kHandleTypeShape; 1709 break; 1710 } 1711 case Decl::Kind::kStruct: { 1712 Struct* struct_decl = static_cast<Struct*>(named_decl); 1713 if (!struct_decl->compiled) { 1714 if (struct_decl->compiling) { 1715 struct_decl->recursive = true; 1716 } else { 1717 if (!CompileStruct(struct_decl)) { 1718 return false; 1719 } 1720 } 1721 } 1722 typeshape = struct_decl->typeshape; 1723 if (identifier_type->nullability == types::Nullability::kNullable) 1724 typeshape = PointerTypeShape(typeshape); 1725 break; 1726 } 1727 case Decl::Kind::kTable: { 1728 Table* table_decl = static_cast<Table*>(named_decl); 1729 if (!table_decl->compiled) { 1730 if (table_decl->compiling) { 1731 table_decl->recursive = true; 1732 } else { 1733 if (!CompileTable(table_decl)) { 1734 return false; 1735 } 1736 } 1737 } 1738 typeshape = table_decl->typeshape; 1739 if (identifier_type->nullability == types::Nullability::kNullable) 1740 typeshape = PointerTypeShape(typeshape); 1741 break; 1742 } 1743 case Decl::Kind::kUnion: { 1744 Union* union_decl = static_cast<Union*>(named_decl); 1745 if (!union_decl->compiled) { 1746 if (union_decl->compiling) { 1747 union_decl->recursive = true; 1748 } else { 1749 if (!CompileUnion(union_decl)) { 1750 return false; 1751 } 1752 } 1753 } 1754 typeshape = union_decl->typeshape; 1755 if (identifier_type->nullability == types::Nullability::kNullable) 1756 typeshape = PointerTypeShape(typeshape); 1757 break; 1758 } 1759 default: { abort(); } 1760 } 1761 1762 identifier_type->size = typeshape.Size(); 1763 *out_typeshape = typeshape; 1764 return true; 1765} 1766 1767bool Library::CompileType(Type* type, TypeShape* out_typeshape) { 1768 switch (type->kind) { 1769 case Type::Kind::kArray: { 1770 auto array_type = static_cast<ArrayType*>(type); 1771 return CompileArrayType(array_type, out_typeshape); 1772 } 1773 1774 case Type::Kind::kVector: { 1775 auto vector_type = static_cast<VectorType*>(type); 1776 return CompileVectorType(vector_type, out_typeshape); 1777 } 1778 1779 case Type::Kind::kString: { 1780 auto string_type = static_cast<StringType*>(type); 1781 return CompileStringType(string_type, out_typeshape); 1782 } 1783 1784 case Type::Kind::kHandle: { 1785 auto handle_type = static_cast<HandleType*>(type); 1786 return CompileHandleType(handle_type, out_typeshape); 1787 } 1788 1789 case Type::Kind::kRequestHandle: { 1790 auto request_type = static_cast<RequestHandleType*>(type); 1791 return CompileRequestHandleType(request_type, out_typeshape); 1792 } 1793 1794 case Type::Kind::kPrimitive: { 1795 auto primitive_type = static_cast<PrimitiveType*>(type); 1796 return CompilePrimitiveType(primitive_type, out_typeshape); 1797 } 1798 1799 case Type::Kind::kIdentifier: { 1800 auto identifier_type = static_cast<IdentifierType*>(type); 1801 return CompileIdentifierType(identifier_type, out_typeshape); 1802 } 1803 } 1804} 1805 1806bool Library::HasAttribute(fidl::StringView name) const { 1807 if (!attributes_) 1808 return false; 1809 return attributes_->HasAttribute(name); 1810} 1811 1812const std::set<Library*>& Library::dependencies() const { 1813 return dependencies_.dependencies(); 1814} 1815 1816} // namespace flat 1817} // namespace fidl 1818