compiler.c++ 44.9 KB
Newer Older
Kenton Varda's avatar
Kenton Varda committed
1 2
// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
// Licensed under the MIT License:
Kenton Varda's avatar
Kenton Varda committed
3
//
Kenton Varda's avatar
Kenton Varda committed
4 5 6 7 8 9
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
Kenton Varda's avatar
Kenton Varda committed
10
//
Kenton Varda's avatar
Kenton Varda committed
11 12
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
Kenton Varda's avatar
Kenton Varda committed
13
//
Kenton Varda's avatar
Kenton Varda committed
14 15 16 17 18 19 20
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
Kenton Varda's avatar
Kenton Varda committed
21 22

#include "compiler.h"
Kenton Varda's avatar
Kenton Varda committed
23
#include "parser.h"      // only for generateChildId()
Kenton Varda's avatar
Kenton Varda committed
24 25 26 27 28 29
#include <kj/mutex.h>
#include <kj/arena.h>
#include <kj/vector.h>
#include <kj/debug.h>
#include <capnp/message.h>
#include <map>
Kenton Varda's avatar
Kenton Varda committed
30
#include <set>
Kenton Varda's avatar
Kenton Varda committed
31 32 33 34 35 36 37 38 39
#include <unordered_map>
#include "node-translator.h"
#include "md5.h"

namespace capnp {
namespace compiler {

class Compiler::Alias {
public:
40 41
  Alias(CompiledModule& module, Node& parent, const Expression::Reader& targetName)
      : module(module), parent(parent), targetName(targetName) {}
Kenton Varda's avatar
Kenton Varda committed
42

43
  kj::Maybe<NodeTranslator::Resolver::ResolveResult> compile();
Kenton Varda's avatar
Kenton Varda committed
44 45

private:
46 47
  CompiledModule& module;
  Node& parent;
Kenton Varda's avatar
Kenton Varda committed
48
  Expression::Reader targetName;
49 50 51
  kj::Maybe<NodeTranslator::Resolver::ResolveResult> target;
  Orphan<schema::Brand> brandOrphan;
  bool initialized = false;
Kenton Varda's avatar
Kenton Varda committed
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
};

class Compiler::Node: public NodeTranslator::Resolver {
  // Passes through four states:
  // - Stub:  On initial construction, the Node is just a placeholder object.  Its ID has been
  //     determined, and it is placed in its parent's member table as well as the compiler's
  //     nodes-by-ID table.
  // - Expanded:  Nodes have been constructed for all of this Node's nested children.  This happens
  //     the first time a lookup is performed for one of those children.
  // - Bootstrap:  A NodeTranslator has been built and advanced to the bootstrap phase.
  // - Finished:  A final Schema object has been constructed.

public:
  explicit Node(CompiledModule& module);
  // Create a root node representing the given file.  May

68
  Node(Node& parent, const Declaration::Reader& declaration);
Kenton Varda's avatar
Kenton Varda committed
69 70
  // Create a child node.

Kenton Varda's avatar
Kenton Varda committed
71
  Node(kj::StringPtr name, Declaration::Which kind,
72
       List<Declaration::BrandParameter>::Reader genericParams);
Kenton Varda's avatar
Kenton Varda committed
73 74
  // Create a dummy node representing a built-in declaration, like "Int32" or "true".

75
  uint64_t getId() { return id; }
76
  uint getParameterCount() { return genericParamCount; }
77
  Declaration::Which getKind() { return kind; }
Kenton Varda's avatar
Kenton Varda committed
78

79 80 81
  kj::Maybe<Schema> getBootstrapSchema();
  kj::Maybe<schema::Node::Reader> getFinalSchema();
  void loadFinalSchema(const SchemaLoader& loader);
82

83 84
  void traverse(uint eagerness, std::unordered_map<Node*, uint>& seen,
                const SchemaLoader& finalLoader);
85 86
  // Get the final schema for this node, and also possibly traverse the node's children and
  // dependencies to ensure that they are loaded, depending on the mode.
Kenton Varda's avatar
Kenton Varda committed
87

88
  void addError(kj::StringPtr error);
Kenton Varda's avatar
Kenton Varda committed
89 90 91
  // Report an error on this Node.

  // implements NodeTranslator::Resolver -----------------------------
92 93 94 95
  kj::Maybe<ResolveResult> resolve(kj::StringPtr name) override;
  kj::Maybe<ResolveResult> resolveMember(kj::StringPtr name) override;
  ResolvedDecl resolveBuiltin(Declaration::Which which) override;
  ResolvedDecl resolveId(uint64_t id) override;
96
  kj::Maybe<ResolvedDecl> getParent() override;
Kenton Varda's avatar
Kenton Varda committed
97
  ResolvedDecl getTopScope() override;
98
  kj::Maybe<Schema> resolveBootstrapSchema(
99
      uint64_t id, schema::Brand::Reader brand) override;
100
  kj::Maybe<schema::Node::Reader> resolveFinalSchema(uint64_t id) override;
Kenton Varda's avatar
Kenton Varda committed
101
  kj::Maybe<ResolvedDecl> resolveImport(kj::StringPtr name) override;
102
  kj::Maybe<kj::Array<const byte>> readEmbed(kj::StringPtr name) override;
103
  kj::Maybe<Type> resolveBootstrapType(schema::Type::Reader type, Schema scope) override;
Kenton Varda's avatar
Kenton Varda committed
104 105

private:
106 107
  CompiledModule* module;  // null iff isBuiltin is true
  kj::Maybe<Node&> parent;
Kenton Varda's avatar
Kenton Varda committed
108 109 110 111 112 113 114 115 116 117 118 119 120

  Declaration::Reader declaration;
  // AST of the declaration parsed from the schema file.  May become invalid once the content
  // state has reached FINISHED.

  uint64_t id;
  // The ID of this node, either taken from the AST or computed based on the parent.  Or, a dummy
  // value, if duplicates were detected.

  kj::StringPtr displayName;
  // Fully-qualified display name for this node.  For files, this is just the file name, otherwise
  // it is "filename:Path.To.Decl".

121
  Declaration::Which kind;
Kenton Varda's avatar
Kenton Varda committed
122 123
  // Kind of node.

Kenton Varda's avatar
Kenton Varda committed
124 125 126
  uint genericParamCount;
  // Number of generic parameters.

Kenton Varda's avatar
Kenton Varda committed
127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143
  bool isBuiltin;
  // Whether this is a bulit-in declaration, like "Int32" or "true".

  uint32_t startByte;
  uint32_t endByte;
  // Start and end byte for reporting general errors.

  struct Content {
    inline Content(): state(STUB) {}

    enum State {
      STUB,
      EXPANDED,
      BOOTSTRAP,
      FINISHED
    };
    State state;
144
    // Indicates which fields below are valid.
Kenton Varda's avatar
Kenton Varda committed
145

146 147
    inline bool stateHasReached(State minimumState) {
      return state >= minimumState;
Kenton Varda's avatar
Kenton Varda committed
148 149
    }
    inline void advanceState(State newState) {
150
      state = newState;
Kenton Varda's avatar
Kenton Varda committed
151 152 153 154 155 156
    }

    // EXPANDED ------------------------------------

    typedef std::multimap<kj::StringPtr, kj::Own<Node>> NestedNodesMap;
    NestedNodesMap nestedNodes;
157
    kj::Vector<Node*> orderedNestedNodes;
Kenton Varda's avatar
Kenton Varda committed
158 159
    // multimap in case of duplicate member names -- we still want to compile them, even if it's an
    // error.
Kenton Varda's avatar
Kenton Varda committed
160 161 162

    typedef std::multimap<kj::StringPtr, kj::Own<Alias>> AliasMap;
    AliasMap aliases;
Kenton Varda's avatar
Kenton Varda committed
163
    // The "using" declarations.  These are just links to nodes elsewhere.
Kenton Varda's avatar
Kenton Varda committed
164 165 166 167 168 169

    // BOOTSTRAP -----------------------------------

    NodeTranslator* translator;
    // Node translator, allocated in the bootstrap arena.

170 171
    kj::Maybe<Schema> bootstrapSchema;
    // The schema built in the bootstrap loader.  Null if the bootstrap loader threw an exception.
Kenton Varda's avatar
Kenton Varda committed
172 173 174

    // FINISHED ------------------------------------

175 176
    kj::Maybe<schema::Node::Reader> finalSchema;
    // The completed schema, ready to load into the real schema loader.
Kenton Varda's avatar
Kenton Varda committed
177

178
    kj::Array<schema::Node::Reader> auxSchemas;
Kenton Varda's avatar
Kenton Varda committed
179
    // Schemas for all auxiliary nodes built by the NodeTranslator.
Kenton Varda's avatar
Kenton Varda committed
180 181
  };

182 183
  Content guardedContent;     // Read using getContent() only!
  bool inGetContent = false;  // True while getContent() is running; detects cycles.
Kenton Varda's avatar
Kenton Varda committed
184

Kenton Varda's avatar
Kenton Varda committed
185 186 187 188
  kj::Maybe<schema::Node::Reader> loadedFinalSchema;
  // Copy of `finalSchema` as loaded into the final schema loader.  This doesn't go away if the
  // workspace is destroyed.

Kenton Varda's avatar
Kenton Varda committed
189 190 191 192 193 194 195
  // ---------------------------------------------

  static uint64_t generateId(uint64_t parentId, kj::StringPtr declName,
                             Declaration::Id::Reader declId);
  // Extract the ID from the declaration, or if it has none, generate one based on the name and
  // parent ID.

196
  static kj::StringPtr joinDisplayName(kj::Arena& arena, Node& parent, kj::StringPtr declName);
Kenton Varda's avatar
Kenton Varda committed
197 198 199
  // Join the parent's display name with the child's unqualified name to construct the child's
  // display name.

200 201 202 203
  kj::Maybe<Content&> getContent(Content::State minimumState);
  // Advances the content to at least the given state and returns it.  Returns null if getContent()
  // is being called recursively and the given state has not yet been reached, as this indicates
  // that the declaration recursively depends on itself.
204

Kenton Varda's avatar
Kenton Varda committed
205
  void traverseNodeDependencies(const schema::Node::Reader& schemaNode, uint eagerness,
206 207
                                std::unordered_map<Node*, uint>& seen,
                                const SchemaLoader& finalLoader);
Kenton Varda's avatar
Kenton Varda committed
208
  void traverseType(const schema::Type::Reader& type, uint eagerness,
209 210
                    std::unordered_map<Node*, uint>& seen,
                    const SchemaLoader& finalLoader);
211 212 213
  void traverseBrand(const schema::Brand::Reader& brand, uint eagerness,
                     std::unordered_map<Node*, uint>& seen,
                     const SchemaLoader& finalLoader);
Kenton Varda's avatar
Kenton Varda committed
214
  void traverseAnnotations(const List<schema::Annotation>::Reader& annotations, uint eagerness,
215 216
                           std::unordered_map<Node*, uint>& seen,
                           const SchemaLoader& finalLoader);
217
  void traverseDependency(uint64_t depId, uint eagerness,
218 219 220
                          std::unordered_map<Node*, uint>& seen,
                          const SchemaLoader& finalLoader,
                          bool ignoreIfNotFound = false);
221
  // Helpers for traverse().
Kenton Varda's avatar
Kenton Varda committed
222 223 224 225
};

class Compiler::CompiledModule {
public:
226
  CompiledModule(Compiler::Impl& compiler, Module& parserModule);
Kenton Varda's avatar
Kenton Varda committed
227

228
  Compiler::Impl& getCompiler() { return compiler; }
Kenton Varda's avatar
Kenton Varda committed
229

230 231 232 233
  ErrorReporter& getErrorReporter() { return parserModule; }
  ParsedFile::Reader getParsedFile() { return content.getReader(); }
  Node& getRootNode() { return rootNode; }
  kj::StringPtr getSourceName() { return parserModule.getSourceName(); }
Kenton Varda's avatar
Kenton Varda committed
234

235
  kj::Maybe<CompiledModule&> importRelative(kj::StringPtr importPath);
236
  kj::Maybe<kj::Array<const byte>> embedRelative(kj::StringPtr importPath);
Kenton Varda's avatar
Kenton Varda committed
237

Kenton Varda's avatar
Kenton Varda committed
238
  Orphan<List<schema::CodeGeneratorRequest::RequestedFile::Import>>
239
      getFileImportTable(Orphanage orphanage);
Kenton Varda's avatar
Kenton Varda committed
240

Kenton Varda's avatar
Kenton Varda committed
241
private:
242 243
  Compiler::Impl& compiler;
  Module& parserModule;
Kenton Varda's avatar
Kenton Varda committed
244
  MallocMessageBuilder contentArena;
245
  Orphan<ParsedFile> content;
Kenton Varda's avatar
Kenton Varda committed
246 247 248 249 250
  Node rootNode;
};

class Compiler::Impl: public SchemaLoader::LazyLoadCallback {
public:
251
  explicit Impl(AnnotationFlag annotationFlag);
252
  virtual ~Impl() noexcept(false);
Kenton Varda's avatar
Kenton Varda committed
253

254 255
  uint64_t add(Module& module);
  kj::Maybe<uint64_t> lookup(uint64_t parent, kj::StringPtr childName);
Kenton Varda's avatar
Kenton Varda committed
256
  Orphan<List<schema::CodeGeneratorRequest::RequestedFile::Import>>
257 258 259
      getFileImportTable(Module& module, Orphanage orphanage);
  void eagerlyCompile(uint64_t id, uint eagerness, const SchemaLoader& loader);
  CompiledModule& addInternal(Module& parsedModule);
Kenton Varda's avatar
Kenton Varda committed
260 261 262 263 264 265 266

  struct Workspace {
    // Scratch space where stuff can be allocated while working.  The Workspace is available
    // whenever nodes are actively being compiled, then is destroyed once control exits the
    // compiler.  Note that since nodes are compiled lazily, a new Workspace may have to be
    // constructed in order to compile more nodes later.

267
    MallocMessageBuilder message;
Kenton Varda's avatar
Kenton Varda committed
268 269 270
    Orphanage orphanage;
    // Orphanage for allocating temporary Cap'n Proto objects.

271 272 273 274 275
    kj::Arena arena;
    // Arena for allocating temporary native objects.  Note that objects in `arena` may contain
    // pointers into `message` that will be manipulated on destruction, so `arena` must be declared
    // after `message`.

Kenton Varda's avatar
Kenton Varda committed
276 277 278 279 280 281
    SchemaLoader bootstrapLoader;
    // Loader used to load bootstrap schemas.  The bootstrap schema nodes are similar to the final
    // versions except that any value expressions which depend on knowledge of other types (e.g.
    // default values for struct fields) are left unevaluated (the values in the schema are empty).
    // These bootstrap schemas can then be plugged into the dynamic API and used to evaluate these
    // remaining values.
282

283 284 285
    inline explicit Workspace(const SchemaLoader::LazyLoadCallback& loaderCallback)
        : orphanage(message.getOrphanage()),
          bootstrapLoader(loaderCallback) {}
Kenton Varda's avatar
Kenton Varda committed
286 287
  };

288
  kj::Arena& getNodeArena() { return nodeArena; }
Kenton Varda's avatar
Kenton Varda committed
289 290
  // Arena where nodes and other permanent objects should be allocated.

291
  Workspace& getWorkspace() { return workspace; }
292
  // Temporary workspace that can be used to construct bootstrap objects.
Kenton Varda's avatar
Kenton Varda committed
293

294
  inline bool shouldCompileAnnotations() {
295 296 297
    return annotationFlag == AnnotationFlag::COMPILE_ANNOTATIONS;
  }

298 299
  void clearWorkspace();
  // Reset the temporary workspace.
Kenton Varda's avatar
Kenton Varda committed
300

301
  uint64_t addNode(uint64_t desiredId, Node& node);
Kenton Varda's avatar
Kenton Varda committed
302 303 304 305
  // Add the given node to the by-ID map under the given ID.  If another node with the same ID
  // already exists, choose a new one arbitrarily and use that instead.  Return the ID that was
  // finally used.

306
  kj::Maybe<Node&> findNode(uint64_t id);
Kenton Varda's avatar
Kenton Varda committed
307

308
  kj::Maybe<Node&> lookupBuiltin(kj::StringPtr name);
309
  Node& getBuiltin(Declaration::Which which);
Kenton Varda's avatar
Kenton Varda committed
310 311

  void load(const SchemaLoader& loader, uint64_t id) const override;
312 313 314 315
  // SchemaLoader callback for the bootstrap loader.

  void loadFinal(const SchemaLoader& loader, uint64_t id);
  // Called from the SchemaLoader callback for the final loader.
Kenton Varda's avatar
Kenton Varda committed
316 317

private:
318 319
  AnnotationFlag annotationFlag;

Kenton Varda's avatar
Kenton Varda committed
320 321 322
  kj::Arena nodeArena;
  // Arena used to allocate nodes and other permanent objects.

323
  Workspace workspace;
324
  // The temporary workspace.
Kenton Varda's avatar
Kenton Varda committed
325

326
  std::unordered_map<Module*, kj::Own<CompiledModule>> modules;
Kenton Varda's avatar
Kenton Varda committed
327 328
  // Map of parser modules to compiler modules.

329
  std::unordered_map<uint64_t, Node*> nodesById;
Kenton Varda's avatar
Kenton Varda committed
330 331 332
  // Map of nodes by ID.

  std::map<kj::StringPtr, kj::Own<Node>> builtinDecls;
333
  std::map<Declaration::Which, Node*> builtinDeclsByKind;
Kenton Varda's avatar
Kenton Varda committed
334 335
  // Map of built-in declarations, like "Int32" and "List", which make up the global scope.

336 337
  uint64_t nextBogusId = 1000;
  // Counter for assigning bogus IDs to nodes whose real ID is a duplicate.
Kenton Varda's avatar
Kenton Varda committed
338 339 340 341
};

// =======================================================================================

342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365
kj::Maybe<NodeTranslator::Resolver::ResolveResult> Compiler::Alias::compile() {
  if (!initialized) {
    initialized = true;

    auto& workspace = module.getCompiler().getWorkspace();
    brandOrphan = workspace.orphanage.newOrphan<schema::Brand>();

    // If the Workspace is destroyed, revert the alias to the uninitialized state, because the
    // orphan we created is no longer valid in this case.
    workspace.arena.copy(kj::defer([this]() {
      initialized = false;
      brandOrphan = Orphan<schema::Brand>();
    }));

    target = NodeTranslator::compileDecl(
        parent.getId(), parent.getParameterCount(), parent,
        module.getErrorReporter(), targetName, brandOrphan.get());
  }

  return target;
}

// =======================================================================================

Kenton Varda's avatar
Kenton Varda committed
366 367 368 369 370 371
Compiler::Node::Node(CompiledModule& module)
    : module(&module),
      parent(nullptr),
      declaration(module.getParsedFile().getRoot()),
      id(generateId(0, declaration.getName().getValue(), declaration.getId())),
      displayName(module.getSourceName()),
372
      kind(declaration.which()),
Kenton Varda's avatar
Kenton Varda committed
373
      genericParamCount(declaration.getParameters().size()),
Kenton Varda's avatar
Kenton Varda committed
374 375 376 377 378 379 380 381 382 383 384 385 386
      isBuiltin(false) {
  auto name = declaration.getName();
  if (name.getValue().size() > 0) {
    startByte = name.getStartByte();
    endByte = name.getEndByte();
  } else {
    startByte = declaration.getStartByte();
    endByte = declaration.getEndByte();
  }

  id = module.getCompiler().addNode(id, *this);
}

387
Compiler::Node::Node(Node& parent, const Declaration::Reader& declaration)
Kenton Varda's avatar
Kenton Varda committed
388 389 390 391 392 393
    : module(parent.module),
      parent(parent),
      declaration(declaration),
      id(generateId(parent.id, declaration.getName().getValue(), declaration.getId())),
      displayName(joinDisplayName(parent.module->getCompiler().getNodeArena(),
                                  parent, declaration.getName().getValue())),
394
      kind(declaration.which()),
Kenton Varda's avatar
Kenton Varda committed
395
      genericParamCount(declaration.getParameters().size()),
Kenton Varda's avatar
Kenton Varda committed
396 397 398 399 400 401 402 403 404 405 406 407 408
      isBuiltin(false) {
  auto name = declaration.getName();
  if (name.getValue().size() > 0) {
    startByte = name.getStartByte();
    endByte = name.getEndByte();
  } else {
    startByte = declaration.getStartByte();
    endByte = declaration.getEndByte();
  }

  id = module->getCompiler().addNode(id, *this);
}

Kenton Varda's avatar
Kenton Varda committed
409
Compiler::Node::Node(kj::StringPtr name, Declaration::Which kind,
410
                     List<Declaration::BrandParameter>::Reader genericParams)
Kenton Varda's avatar
Kenton Varda committed
411 412
    : module(nullptr),
      parent(nullptr),
Kenton Varda's avatar
Kenton Varda committed
413 414
      // It's helpful if these have unique IDs. Real type IDs can't be under 2^31 anyway.
      id(1000 + static_cast<uint>(kind)),
Kenton Varda's avatar
Kenton Varda committed
415 416
      displayName(name),
      kind(kind),
Kenton Varda's avatar
Kenton Varda committed
417
      genericParamCount(genericParams.size()),
Kenton Varda's avatar
Kenton Varda committed
418 419 420 421 422 423
      isBuiltin(true),
      startByte(0),
      endByte(0) {}

uint64_t Compiler::Node::generateId(uint64_t parentId, kj::StringPtr declName,
                                    Declaration::Id::Reader declId) {
424
  if (declId.isUid()) {
Kenton Varda's avatar
Kenton Varda committed
425 426 427
    return declId.getUid().getValue();
  }

Kenton Varda's avatar
Kenton Varda committed
428
  return generateChildId(parentId, declName);
Kenton Varda's avatar
Kenton Varda committed
429 430 431
}

kj::StringPtr Compiler::Node::joinDisplayName(
432
    kj::Arena& arena, Node& parent, kj::StringPtr declName) {
Kenton Varda's avatar
Kenton Varda committed
433 434 435 436 437 438 439 440
  kj::ArrayPtr<char> result = arena.allocateArray<char>(
      parent.displayName.size() + declName.size() + 2);

  size_t separatorPos = parent.displayName.size();
  memcpy(result.begin(), parent.displayName.begin(), separatorPos);
  result[separatorPos] = parent.parent == nullptr ? ':' : '.';
  memcpy(result.begin() + separatorPos + 1, declName.begin(), declName.size());
  result[result.size() - 1] = '\0';
441
  return kj::StringPtr(result.begin(), result.size() - 1);
Kenton Varda's avatar
Kenton Varda committed
442 443
}

444
kj::Maybe<Compiler::Node::Content&> Compiler::Node::getContent(Content::State minimumState) {
Kenton Varda's avatar
Kenton Varda committed
445 446
  KJ_REQUIRE(!isBuiltin, "illegal method call for built-in declaration");

447 448 449 450 451 452 453 454 455
  auto& content = guardedContent;

  if (content.stateHasReached(minimumState)) {
    return content;
  }

  if (inGetContent) {
    addError("Declaration recursively depends on itself.");
    return nullptr;
Kenton Varda's avatar
Kenton Varda committed
456 457
  }

458 459
  inGetContent = true;
  KJ_DEFER(inGetContent = false);
Kenton Varda's avatar
Kenton Varda committed
460

461
  switch (content.state) {
Kenton Varda's avatar
Kenton Varda committed
462 463 464 465 466 467 468
    case Content::STUB: {
      if (minimumState <= Content::STUB) break;

      // Expand the child nodes.
      auto& arena = module->getCompiler().getNodeArena();

      for (auto nestedDecl: declaration.getNestedDecls()) {
469 470 471 472 473 474 475
        switch (nestedDecl.which()) {
          case Declaration::FILE:
          case Declaration::CONST:
          case Declaration::ANNOTATION:
          case Declaration::ENUM:
          case Declaration::STRUCT:
          case Declaration::INTERFACE: {
Kenton Varda's avatar
Kenton Varda committed
476 477
            kj::Own<Node> subNode = arena.allocateOwn<Node>(*this, nestedDecl);
            kj::StringPtr name = nestedDecl.getName().getValue();
478 479
            content.orderedNestedNodes.add(subNode);
            content.nestedNodes.insert(std::make_pair(name, kj::mv(subNode)));
Kenton Varda's avatar
Kenton Varda committed
480 481 482
            break;
          }

483
          case Declaration::USING: {
Kenton Varda's avatar
Kenton Varda committed
484
            kj::Own<Alias> alias = arena.allocateOwn<Alias>(
485
                *module, *this, nestedDecl.getUsing().getTarget());
Kenton Varda's avatar
Kenton Varda committed
486
            kj::StringPtr name = nestedDecl.getName().getValue();
487
            content.aliases.insert(std::make_pair(name, kj::mv(alias)));
Kenton Varda's avatar
Kenton Varda committed
488 489
            break;
          }
490 491 492 493 494 495 496
          case Declaration::ENUMERANT:
          case Declaration::FIELD:
          case Declaration::UNION:
          case Declaration::GROUP:
          case Declaration::METHOD:
          case Declaration::NAKED_ID:
          case Declaration::NAKED_ANNOTATION:
Kenton Varda's avatar
Kenton Varda committed
497 498 499 500 501 502 503 504
            // Not a node.  Skip.
            break;
          default:
            KJ_FAIL_ASSERT("unknown declaration type", nestedDecl);
            break;
        }
      }

505
      content.advanceState(Content::EXPANDED);
Kenton Varda's avatar
Kenton Varda committed
506 507 508 509 510 511 512 513 514
      // no break
    }

    case Content::EXPANDED: {
      if (minimumState <= Content::EXPANDED) break;

      // Construct the NodeTranslator.
      auto& workspace = module->getCompiler().getWorkspace();

Kenton Varda's avatar
Kenton Varda committed
515
      auto schemaNode = workspace.orphanage.newOrphan<schema::Node>();
Kenton Varda's avatar
Kenton Varda committed
516 517 518
      auto builder = schemaNode.get();
      builder.setId(id);
      builder.setDisplayName(displayName);
519 520 521 522 523 524 525 526 527 528
      // TODO(cleanup):  Would be better if we could remember the prefix length from before we
      //   added this decl's name to the end.
      KJ_IF_MAYBE(lastDot, displayName.findLast('.')) {
        builder.setDisplayNamePrefixLength(*lastDot + 1);
      }
      KJ_IF_MAYBE(lastColon, displayName.findLast(':')) {
        if (*lastColon > builder.getDisplayNamePrefixLength()) {
          builder.setDisplayNamePrefixLength(*lastColon + 1);
        }
      }
Kenton Varda's avatar
Kenton Varda committed
529 530 531 532
      KJ_IF_MAYBE(p, parent) {
        builder.setScopeId(p->id);
      }

533
      auto nestedNodes = builder.initNestedNodes(content.orderedNestedNodes.size());
Kenton Varda's avatar
Kenton Varda committed
534
      auto nestedIter = nestedNodes.begin();
535
      for (auto node: content.orderedNestedNodes) {
536 537
        nestedIter->setName(node->declaration.getName().getValue());
        nestedIter->setId(node->id);
Kenton Varda's avatar
Kenton Varda committed
538 539 540
        ++nestedIter;
      }

541
      content.translator = &workspace.arena.allocate<NodeTranslator>(
542 543
          *this, module->getErrorReporter(), declaration, kj::mv(schemaNode),
          module->getCompiler().shouldCompileAnnotations());
544
      KJ_IF_MAYBE(exception, kj::runCatchingExceptions([&](){
545
        auto nodeSet = content.translator->getBootstrapNode();
Kenton Varda's avatar
Kenton Varda committed
546 547 548
        for (auto& auxNode: nodeSet.auxNodes) {
          workspace.bootstrapLoader.loadOnce(auxNode);
        }
549
        content.bootstrapSchema = workspace.bootstrapLoader.loadOnce(nodeSet.node);
550
      })) {
551
        content.bootstrapSchema = nullptr;
552 553 554 555 556 557
        // Only bother to report validation failures if we think we haven't seen any errors.
        // Otherwise we assume that the errors caused the validation failure.
        if (!module->getErrorReporter().hadErrors()) {
          addError(kj::str("Internal compiler bug: Bootstrap schema failed validation:\n",
                           *exception));
        }
558
      }
Kenton Varda's avatar
Kenton Varda committed
559

Kenton Varda's avatar
Kenton Varda committed
560 561
      // If the Workspace is destroyed, revert the node to the EXPANDED state, because the
      // NodeTranslator is no longer valid in this case.
562 563
      workspace.arena.copy(kj::defer([&content]() {
        content.bootstrapSchema = nullptr;
Kenton Varda's avatar
Kenton Varda committed
564
        if (content.state > Content::EXPANDED) {
565
          content.state = Content::EXPANDED;
Kenton Varda's avatar
Kenton Varda committed
566 567 568
        }
      }));

569
      content.advanceState(Content::BOOTSTRAP);
Kenton Varda's avatar
Kenton Varda committed
570 571 572 573 574 575 576
      // no break
    }

    case Content::BOOTSTRAP: {
      if (minimumState <= Content::BOOTSTRAP) break;

      // Create the final schema.
577 578 579
      auto nodeSet = content.translator->finish();
      content.finalSchema = nodeSet.node;
      content.auxSchemas = kj::mv(nodeSet.auxNodes);
580

581
      content.advanceState(Content::FINISHED);
Kenton Varda's avatar
Kenton Varda committed
582 583 584 585 586 587 588
      // no break
    }

    case Content::FINISHED:
      break;
  }

589
  return content;
Kenton Varda's avatar
Kenton Varda committed
590 591
}

592
kj::Maybe<Schema> Compiler::Node::getBootstrapSchema() {
Kenton Varda's avatar
Kenton Varda committed
593 594 595 596
  KJ_IF_MAYBE(schema, loadedFinalSchema) {
    // We don't need to rebuild the bootstrap schema if we already have a final schema.
    return module->getCompiler().getWorkspace().bootstrapLoader.loadOnce(*schema);
  } else KJ_IF_MAYBE(content, getContent(Content::BOOTSTRAP)) {
597 598 599 600 601 602 603 604 605
    if (content->state == Content::FINISHED && content->bootstrapSchema == nullptr) {
      // The bootstrap schema was discarded.  Copy it from the final schema.
      // (We can't just return the final schema because using it could trigger schema loader
      // callbacks that would deadlock.)
      KJ_IF_MAYBE(finalSchema, content->finalSchema) {
        return module->getCompiler().getWorkspace().bootstrapLoader.loadOnce(*finalSchema);
      } else {
        return nullptr;
      }
606
    } else {
607
      return content->bootstrapSchema;
608
    }
Kenton Varda's avatar
Kenton Varda committed
609
  } else {
610 611 612 613
    return nullptr;
  }
}
kj::Maybe<schema::Node::Reader> Compiler::Node::getFinalSchema() {
Kenton Varda's avatar
Kenton Varda committed
614 615 616
  KJ_IF_MAYBE(schema, loadedFinalSchema) {
    return *schema;
  } else KJ_IF_MAYBE(content, getContent(Content::FINISHED)) {
617 618 619
    return content->finalSchema;
  } else {
    return nullptr;
Kenton Varda's avatar
Kenton Varda committed
620 621
  }
}
622 623 624 625 626 627 628
void Compiler::Node::loadFinalSchema(const SchemaLoader& loader) {
  KJ_IF_MAYBE(content, getContent(Content::FINISHED)) {
    KJ_IF_MAYBE(exception, kj::runCatchingExceptions([&](){
      KJ_IF_MAYBE(finalSchema, content->finalSchema) {
        KJ_MAP(auxSchema, content->auxSchemas) {
          return loader.loadOnce(auxSchema);
        };
Kenton Varda's avatar
Kenton Varda committed
629
        loadedFinalSchema = loader.loadOnce(*finalSchema).getProto();
630 631
      }
    })) {
Kenton Varda's avatar
Kenton Varda committed
632 633
      // Schema validation threw an exception.

634 635 636 637 638 639 640 641 642 643
      // Don't try loading this again.
      content->finalSchema = nullptr;

      // Only bother to report validation failures if we think we haven't seen any errors.
      // Otherwise we assume that the errors caused the validation failure.
      if (!module->getErrorReporter().hadErrors()) {
        addError(kj::str("Internal compiler bug: Schema failed validation:\n", *exception));
      }
    }
  }
Kenton Varda's avatar
Kenton Varda committed
644 645
}

646 647
void Compiler::Node::traverse(uint eagerness, std::unordered_map<Node*, uint>& seen,
                              const SchemaLoader& finalLoader) {
648 649 650 651 652 653 654
  uint& slot = seen[this];
  if ((slot & eagerness) == eagerness) {
    // We've already covered this node.
    return;
  }
  slot |= eagerness;

655 656
  KJ_IF_MAYBE(content, getContent(Content::FINISHED)) {
    loadFinalSchema(finalLoader);
657

658 659 660 661 662 663 664 665 666 667
    KJ_IF_MAYBE(schema, getFinalSchema()) {
      if (eagerness / DEPENDENCIES != 0) {
        // For traversing dependencies, discard the bits lower than DEPENDENCIES and replace
        // them with the bits above DEPENDENCIES shifted over.
        uint newEagerness = (eagerness & ~(DEPENDENCIES - 1)) | (eagerness / DEPENDENCIES);

        traverseNodeDependencies(*schema, newEagerness, seen, finalLoader);
        for (auto& aux: content->auxSchemas) {
          traverseNodeDependencies(aux, newEagerness, seen, finalLoader);
        }
668 669 670 671 672 673
      }
    }
  }

  if (eagerness & PARENTS) {
    KJ_IF_MAYBE(p, parent) {
674
      p->traverse(eagerness, seen, finalLoader);
675 676 677 678
    }
  }

  if (eagerness & CHILDREN) {
679 680 681 682
    KJ_IF_MAYBE(content, getContent(Content::EXPANDED)) {
      for (auto& child: content->orderedNestedNodes) {
        child->traverse(eagerness, seen, finalLoader);
      }
683 684 685 686
    }
  }
}

Kenton Varda's avatar
Kenton Varda committed
687
void Compiler::Node::traverseNodeDependencies(
Kenton Varda's avatar
Kenton Varda committed
688
    const schema::Node::Reader& schemaNode, uint eagerness,
689 690
    std::unordered_map<Node*, uint>& seen,
    const SchemaLoader& finalLoader) {
Kenton Varda's avatar
Kenton Varda committed
691
  switch (schemaNode.which()) {
Kenton Varda's avatar
Kenton Varda committed
692
    case schema::Node::STRUCT:
Kenton Varda's avatar
Kenton Varda committed
693 694
      for (auto field: schemaNode.getStruct().getFields()) {
        switch (field.which()) {
695
          case schema::Field::SLOT:
696
            traverseType(field.getSlot().getType(), eagerness, seen, finalLoader);
Kenton Varda's avatar
Kenton Varda committed
697
            break;
Kenton Varda's avatar
Kenton Varda committed
698
          case schema::Field::GROUP:
Kenton Varda's avatar
Kenton Varda committed
699 700 701 702
            // Aux node will be scanned later.
            break;
        }

703
        traverseAnnotations(field.getAnnotations(), eagerness, seen, finalLoader);
Kenton Varda's avatar
Kenton Varda committed
704 705 706
      }
      break;

Kenton Varda's avatar
Kenton Varda committed
707
    case schema::Node::ENUM:
708
      for (auto enumerant: schemaNode.getEnum().getEnumerants()) {
709
        traverseAnnotations(enumerant.getAnnotations(), eagerness, seen, finalLoader);
Kenton Varda's avatar
Kenton Varda committed
710 711 712
      }
      break;

713 714
    case schema::Node::INTERFACE: {
      auto interface = schemaNode.getInterface();
715 716 717 718
      for (auto superclass: interface.getSuperclasses()) {
        uint64_t superclassId = superclass.getId();
        if (superclassId != 0) {  // if zero, we reported an error earlier
          traverseDependency(superclassId, eagerness, seen, finalLoader);
719
        }
720
        traverseBrand(superclass.getBrand(), eagerness, seen, finalLoader);
721 722
      }
      for (auto method: interface.getMethods()) {
723
        traverseDependency(method.getParamStructType(), eagerness, seen, finalLoader, true);
724
        traverseBrand(method.getParamBrand(), eagerness, seen, finalLoader);
725
        traverseDependency(method.getResultStructType(), eagerness, seen, finalLoader, true);
726
        traverseBrand(method.getResultBrand(), eagerness, seen, finalLoader);
727
        traverseAnnotations(method.getAnnotations(), eagerness, seen, finalLoader);
Kenton Varda's avatar
Kenton Varda committed
728 729
      }
      break;
730
    }
Kenton Varda's avatar
Kenton Varda committed
731

Kenton Varda's avatar
Kenton Varda committed
732 733 734 735 736 737 738 739
    case schema::Node::CONST:
      traverseType(schemaNode.getConst().getType(), eagerness, seen, finalLoader);
      break;

    case schema::Node::ANNOTATION:
      traverseType(schemaNode.getAnnotation().getType(), eagerness, seen, finalLoader);
      break;

Kenton Varda's avatar
Kenton Varda committed
740 741 742 743
    default:
      break;
  }

744
  traverseAnnotations(schemaNode.getAnnotations(), eagerness, seen, finalLoader);
Kenton Varda's avatar
Kenton Varda committed
745 746
}

Kenton Varda's avatar
Kenton Varda committed
747
void Compiler::Node::traverseType(const schema::Type::Reader& type, uint eagerness,
748 749
                                  std::unordered_map<Node*, uint>& seen,
                                  const SchemaLoader& finalLoader) {
750
  uint64_t id = 0;
751
  schema::Brand::Reader brand;
Kenton Varda's avatar
Kenton Varda committed
752
  switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
753
    case schema::Type::STRUCT:
754
      id = type.getStruct().getTypeId();
755
      brand = type.getStruct().getBrand();
756
      break;
Kenton Varda's avatar
Kenton Varda committed
757
    case schema::Type::ENUM:
758
      id = type.getEnum().getTypeId();
759
      brand = type.getEnum().getBrand();
760
      break;
Kenton Varda's avatar
Kenton Varda committed
761
    case schema::Type::INTERFACE:
762
      id = type.getInterface().getTypeId();
763
      brand = type.getInterface().getBrand();
764
      break;
Kenton Varda's avatar
Kenton Varda committed
765
    case schema::Type::LIST:
766
      traverseType(type.getList().getElementType(), eagerness, seen, finalLoader);
767 768 769 770 771
      return;
    default:
      return;
  }

772
  traverseDependency(id, eagerness, seen, finalLoader);
773
  traverseBrand(brand, eagerness, seen, finalLoader);
Kenton Varda's avatar
Kenton Varda committed
774 775
}

776 777
void Compiler::Node::traverseBrand(
    const schema::Brand::Reader& brand, uint eagerness,
Kenton Varda's avatar
Kenton Varda committed
778 779
    std::unordered_map<Node*, uint>& seen,
    const SchemaLoader& finalLoader) {
780
  for (auto scope: brand.getScopes()) {
781
    switch (scope.which()) {
782
      case schema::Brand::Scope::BIND:
783 784
        for (auto binding: scope.getBind()) {
          switch (binding.which()) {
785
            case schema::Brand::Binding::UNBOUND:
786
              break;
787
            case schema::Brand::Binding::TYPE:
788 789 790 791 792
              traverseType(binding.getType(), eagerness, seen, finalLoader);
              break;
          }
        }
        break;
793
      case schema::Brand::Scope::INHERIT:
794
        break;
Kenton Varda's avatar
Kenton Varda committed
795 796
    }
  }
797 798 799
}

void Compiler::Node::traverseDependency(uint64_t depId, uint eagerness,
800 801 802
                                        std::unordered_map<Node*, uint>& seen,
                                        const SchemaLoader& finalLoader,
                                        bool ignoreIfNotFound) {
803
  KJ_IF_MAYBE(node, module->getCompiler().findNode(depId)) {
804
    node->traverse(eagerness, seen, finalLoader);
805
  } else if (!ignoreIfNotFound) {
806
    KJ_FAIL_ASSERT("Dependency ID not present in compiler?", depId);
807 808 809
  }
}

Kenton Varda's avatar
Kenton Varda committed
810
void Compiler::Node::traverseAnnotations(const List<schema::Annotation>::Reader& annotations,
811
                                         uint eagerness,
812 813
                                         std::unordered_map<Node*, uint>& seen,
                                         const SchemaLoader& finalLoader) {
814 815
  for (auto annotation: annotations) {
    KJ_IF_MAYBE(node, module->getCompiler().findNode(annotation.getId())) {
816
      node->traverse(eagerness, seen, finalLoader);
817 818 819 820 821
    }
  }
}


822
void Compiler::Node::addError(kj::StringPtr error) {
Kenton Varda's avatar
Kenton Varda committed
823 824 825
  module->getErrorReporter().addError(startByte, endByte, error);
}

826
kj::Maybe<NodeTranslator::Resolver::ResolveResult>
Kenton Varda's avatar
Kenton Varda committed
827 828 829
Compiler::Node::resolve(kj::StringPtr name) {
  // Check members.
  KJ_IF_MAYBE(member, resolveMember(name)) {
830
    return *member;
Kenton Varda's avatar
Kenton Varda committed
831 832 833 834 835 836 837
  }

  // Check parameters.
  // TODO(perf): Maintain a map?
  auto params = declaration.getParameters();
  for (uint i: kj::indices(params)) {
    if (params[i].getName() == name) {
838
      ResolveResult result;
Kenton Varda's avatar
Kenton Varda committed
839 840 841 842 843 844 845 846 847
      result.init<ResolvedParameter>(ResolvedParameter {id, i});
      return result;
    }
  }

  // Check parent scope.
  KJ_IF_MAYBE(p, parent) {
    return p->resolve(name);
  } else KJ_IF_MAYBE(b, module->getCompiler().lookupBuiltin(name)) {
848
    ResolveResult result;
849
    result.init<ResolvedDecl>(ResolvedDecl { b->id, b->genericParamCount, 0, b->kind, b, nullptr });
Kenton Varda's avatar
Kenton Varda committed
850 851 852 853 854 855
    return result;
  } else {
    return nullptr;
  }
}

856
kj::Maybe<NodeTranslator::Resolver::ResolveResult>
Kenton Varda's avatar
Kenton Varda committed
857 858 859 860 861 862 863 864
Compiler::Node::resolveMember(kj::StringPtr name) {
  if (isBuiltin) return nullptr;

  KJ_IF_MAYBE(content, getContent(Content::EXPANDED)) {
    {
      auto iter = content->nestedNodes.find(name);
      if (iter != content->nestedNodes.end()) {
        Node* node = iter->second;
865
        ResolveResult result;
Kenton Varda's avatar
Kenton Varda committed
866
        result.init<ResolvedDecl>(ResolvedDecl {
867
            node->id, node->genericParamCount, id, node->kind, node, nullptr });
Kenton Varda's avatar
Kenton Varda committed
868 869 870 871 872 873
        return result;
      }
    }
    {
      auto iter = content->aliases.find(name);
      if (iter != content->aliases.end()) {
874
        return iter->second->compile();
Kenton Varda's avatar
Kenton Varda committed
875 876 877 878 879 880
      }
    }
  }
  return nullptr;
}

881 882
NodeTranslator::Resolver::ResolvedDecl Compiler::Node::resolveBuiltin(Declaration::Which which) {
  auto& b = module->getCompiler().getBuiltin(which);
883
  return { b.id, b.genericParamCount, 0, b.kind, &b, nullptr };
884 885 886 887 888
}

NodeTranslator::Resolver::ResolvedDecl Compiler::Node::resolveId(uint64_t id) {
  auto& n = KJ_ASSERT_NONNULL(module->getCompiler().findNode(id));
  uint64_t parentId = n.parent.map([](Node& n) { return n.id; }).orDefault(0);
889
  return { n.id, n.genericParamCount, parentId, n.kind, &n, nullptr };
890 891
}

892 893 894
kj::Maybe<NodeTranslator::Resolver::ResolvedDecl> Compiler::Node::getParent() {
  return parent.map([](Node& parent) {
    uint64_t scopeId = parent.parent.map([](Node& gp) { return gp.id; }).orDefault(0);
895
    return ResolvedDecl { parent.id, parent.genericParamCount, scopeId, parent.kind, &parent, nullptr };
896 897 898
  });
}

Kenton Varda's avatar
Kenton Varda committed
899 900
NodeTranslator::Resolver::ResolvedDecl Compiler::Node::getTopScope() {
  Node& node = module->getRootNode();
901
  return ResolvedDecl { node.id, 0, 0, node.kind, &node, nullptr };
Kenton Varda's avatar
Kenton Varda committed
902 903
}

904
kj::Maybe<Schema> Compiler::Node::resolveBootstrapSchema(
905
    uint64_t id, schema::Brand::Reader brand) {
Kenton Varda's avatar
Kenton Varda committed
906
  KJ_IF_MAYBE(node, module->getCompiler().findNode(id)) {
907 908 909 910 911
    // Make sure the bootstrap schema is loaded into the SchemaLoader.
    if (node->getBootstrapSchema() == nullptr) {
      return nullptr;
    }

912 913
    // Now we actually invoke get() to evaluate the brand.
    return module->getCompiler().getWorkspace().bootstrapLoader.get(id, brand);
Kenton Varda's avatar
Kenton Varda committed
914 915 916
  } else {
    KJ_FAIL_REQUIRE("Tried to get schema for ID we haven't seen before.");
  }
Kenton Varda's avatar
Kenton Varda committed
917 918
}

919
kj::Maybe<schema::Node::Reader> Compiler::Node::resolveFinalSchema(uint64_t id) {
Kenton Varda's avatar
Kenton Varda committed
920 921 922 923 924
  KJ_IF_MAYBE(node, module->getCompiler().findNode(id)) {
    return node->getFinalSchema();
  } else {
    KJ_FAIL_REQUIRE("Tried to get schema for ID we haven't seen before.");
  }
Kenton Varda's avatar
Kenton Varda committed
925 926
}

Kenton Varda's avatar
Kenton Varda committed
927 928
kj::Maybe<NodeTranslator::Resolver::ResolvedDecl>
Compiler::Node::resolveImport(kj::StringPtr name) {
929
  KJ_IF_MAYBE(m, module->importRelative(name)) {
Kenton Varda's avatar
Kenton Varda committed
930
    Node& root = m->getRootNode();
931
    return ResolvedDecl { root.id, 0, 0, root.kind, &root, nullptr };
932 933 934 935 936
  } else {
    return nullptr;
  }
}

937 938 939 940
kj::Maybe<kj::Array<const byte>> Compiler::Node::readEmbed(kj::StringPtr name) {
  return module->embedRelative(name);
}

941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956
kj::Maybe<Type> Compiler::Node::resolveBootstrapType(schema::Type::Reader type, Schema scope) {
  // TODO(someday): Arguably should return null if the type or its dependencies are placeholders.

  kj::Maybe<Type> result;
  KJ_IF_MAYBE(exception, kj::runCatchingExceptions([&]() {
    result = module->getCompiler().getWorkspace().bootstrapLoader.getType(type, scope);
  })) {
    result = nullptr;
    if (!module->getErrorReporter().hadErrors()) {
      addError(kj::str("Internal compiler bug: Bootstrap schema failed to load:\n",
                       *exception));
    }
  }
  return result;
}

Kenton Varda's avatar
Kenton Varda committed
957 958
// =======================================================================================

959
Compiler::CompiledModule::CompiledModule(Compiler::Impl& compiler, Module& parserModule)
Kenton Varda's avatar
Kenton Varda committed
960 961 962 963
    : compiler(compiler), parserModule(parserModule),
      content(parserModule.loadContent(contentArena.getOrphanage())),
      rootNode(*this) {}

964 965
kj::Maybe<Compiler::CompiledModule&> Compiler::CompiledModule::importRelative(
    kj::StringPtr importPath) {
Kenton Varda's avatar
Kenton Varda committed
966
  return parserModule.importRelative(importPath).map(
967
      [this](Module& module) -> Compiler::CompiledModule& {
968
        return compiler.addInternal(module);
Kenton Varda's avatar
Kenton Varda committed
969 970 971
      });
}

972 973 974 975
kj::Maybe<kj::Array<const byte>> Compiler::CompiledModule::embedRelative(kj::StringPtr embedPath) {
  return parserModule.embedRelative(embedPath);
}

Kenton Varda's avatar
Kenton Varda committed
976 977 978 979 980 981 982 983 984 985
static void findImports(Expression::Reader exp, std::set<kj::StringPtr>& output) {
  switch (exp.which()) {
    case Expression::UNKNOWN:
    case Expression::POSITIVE_INT:
    case Expression::NEGATIVE_INT:
    case Expression::FLOAT:
    case Expression::STRING:
    case Expression::BINARY:
    case Expression::RELATIVE_NAME:
    case Expression::ABSOLUTE_NAME:
986
    case Expression::EMBED:
Kenton Varda's avatar
Kenton Varda committed
987 988 989 990 991 992 993 994 995 996 997
      break;

    case Expression::IMPORT:
      output.insert(exp.getImport().getValue());
      break;

    case Expression::LIST:
      for (auto element: exp.getList()) {
        findImports(element, output);
      }
      break;
Kenton Varda's avatar
Kenton Varda committed
998

Kenton Varda's avatar
Kenton Varda committed
999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017
    case Expression::TUPLE:
      for (auto element: exp.getTuple()) {
        findImports(element.getValue(), output);
      }
      break;

    case Expression::APPLICATION: {
      auto app = exp.getApplication();
      findImports(app.getFunction(), output);
      for (auto param: app.getParams()) {
        findImports(param.getValue(), output);
      }
      break;
    }

    case Expression::MEMBER: {
      findImports(exp.getMember().getParent(), output);
      break;
    }
Kenton Varda's avatar
Kenton Varda committed
1018 1019 1020 1021
  }
}

static void findImports(Declaration::Reader decl, std::set<kj::StringPtr>& output) {
1022 1023 1024
  switch (decl.which()) {
    case Declaration::USING:
      findImports(decl.getUsing().getTarget(), output);
Kenton Varda's avatar
Kenton Varda committed
1025
      break;
1026 1027
    case Declaration::CONST:
      findImports(decl.getConst().getType(), output);
Kenton Varda's avatar
Kenton Varda committed
1028
      break;
1029 1030
    case Declaration::FIELD:
      findImports(decl.getField().getType(), output);
Kenton Varda's avatar
Kenton Varda committed
1031
      break;
1032
    case Declaration::INTERFACE:
1033 1034
      for (auto superclass: decl.getInterface().getSuperclasses()) {
        findImports(superclass, output);
1035 1036
      }
      break;
1037 1038
    case Declaration::METHOD: {
      auto method = decl.getMethod();
1039 1040 1041 1042 1043 1044 1045 1046

      auto params = method.getParams();
      if (params.isNamedList()) {
        for (auto param: params.getNamedList()) {
          findImports(param.getType(), output);
          for (auto ann: param.getAnnotations()) {
            findImports(ann.getName(), output);
          }
Kenton Varda's avatar
Kenton Varda committed
1047
        }
1048 1049
      } else {
        findImports(params.getType(), output);
Kenton Varda's avatar
Kenton Varda committed
1050
      }
1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063

      if (method.getResults().isExplicit()) {
        auto results = method.getResults().getExplicit();
        if (results.isNamedList()) {
          for (auto param: results.getNamedList()) {
            findImports(param.getType(), output);
            for (auto ann: param.getAnnotations()) {
              findImports(ann.getName(), output);
            }
          }
        } else {
          findImports(results.getType(), output);
        }
Kenton Varda's avatar
Kenton Varda committed
1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079
      }
      break;
    }
    default:
      break;
  }

  for (auto ann: decl.getAnnotations()) {
    findImports(ann.getName(), output);
  }

  for (auto nested: decl.getNestedDecls()) {
    findImports(nested, output);
  }
}

Kenton Varda's avatar
Kenton Varda committed
1080
Orphan<List<schema::CodeGeneratorRequest::RequestedFile::Import>>
1081
    Compiler::CompiledModule::getFileImportTable(Orphanage orphanage) {
1082 1083 1084 1085 1086
  // Build a table of imports for CodeGeneratorRequest.RequestedFile.imports. Note that we only
  // care about type imports, not constant value imports, since constant values (including default
  // values) are already embedded in full in the schema. In other words, we only need the imports
  // that would need to be #included in the generated code.

Kenton Varda's avatar
Kenton Varda committed
1087 1088 1089
  std::set<kj::StringPtr> importNames;
  findImports(content.getReader().getRoot(), importNames);

Kenton Varda's avatar
Kenton Varda committed
1090
  auto result = orphanage.newOrphan<List<schema::CodeGeneratorRequest::RequestedFile::Import>>(
Kenton Varda's avatar
Kenton Varda committed
1091 1092 1093 1094 1095 1096
      importNames.size());
  auto builder = result.get();

  uint i = 0;
  for (auto name: importNames) {
    // We presumably ran this import before, so it shouldn't throw now.
1097
    auto entry = builder[i++];
Kenton Varda's avatar
Kenton Varda committed
1098 1099 1100 1101 1102 1103 1104
    entry.setId(KJ_ASSERT_NONNULL(importRelative(name)).rootNode.getId());
    entry.setName(name);
  }

  return result;
}

Kenton Varda's avatar
Kenton Varda committed
1105 1106
// =======================================================================================

1107
Compiler::Impl::Impl(AnnotationFlag annotationFlag)
1108
    : annotationFlag(annotationFlag), workspace(*this) {
Kenton Varda's avatar
Kenton Varda committed
1109 1110
  // Reflectively interpret the members of Declaration.body.  Any member prefixed by "builtin"
  // defines a builtin declaration visible in the global scope.
1111

1112 1113 1114
  StructSchema declSchema = Schema::from<Declaration>();
  for (auto field: declSchema.getFields()) {
    auto fieldProto = field.getProto();
1115
    if (fieldProto.getDiscriminantValue() != schema::Field::NO_DISCRIMINANT) {
1116 1117 1118
      auto name = fieldProto.getName();
      if (name.startsWith("builtin")) {
        kj::StringPtr symbolName = name.slice(strlen("builtin"));
Kenton Varda's avatar
Kenton Varda committed
1119

1120
        List<Declaration::BrandParameter>::Reader params;
Kenton Varda's avatar
Kenton Varda committed
1121 1122
        for (auto annotation: fieldProto.getAnnotations()) {
          if (annotation.getId() == 0x94099c3f9eb32d6bull) {
1123
            params = annotation.getValue().getList().getAs<List<Declaration::BrandParameter>>();
Kenton Varda's avatar
Kenton Varda committed
1124 1125 1126 1127
            break;
          }
        }

1128 1129 1130 1131 1132
        Declaration::Which which =
            static_cast<Declaration::Which>(fieldProto.getDiscriminantValue());
        kj::Own<Node> newNode = nodeArena.allocateOwn<Node>(symbolName, which, params);
        builtinDeclsByKind[which] = newNode;
        builtinDecls[symbolName] = kj::mv(newNode);
1133
      }
Kenton Varda's avatar
Kenton Varda committed
1134 1135 1136 1137
    }
  }
}

1138
Compiler::Impl::~Impl() noexcept(false) {}
1139

1140 1141
void Compiler::Impl::clearWorkspace() {
  // Make sure we reconstruct the workspace even if destroying it throws an exception.
1142 1143
  KJ_DEFER(kj::ctor(workspace, *this));
  kj::dtor(workspace);
1144 1145
}

1146 1147
Compiler::CompiledModule& Compiler::Impl::addInternal(Module& parsedModule) {
  kj::Own<CompiledModule>& slot = modules[&parsedModule];
1148 1149 1150 1151 1152 1153 1154
  if (slot.get() == nullptr) {
    slot = kj::heap<CompiledModule>(*this, parsedModule);
  }

  return *slot;
}

1155
uint64_t Compiler::Impl::addNode(uint64_t desiredId, Node& node) {
Kenton Varda's avatar
Kenton Varda committed
1156
  for (;;) {
1157
    auto insertResult = nodesById.insert(std::make_pair(desiredId, &node));
Kenton Varda's avatar
Kenton Varda committed
1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171
    if (insertResult.second) {
      return desiredId;
    }

    // Only report an error if this ID is not bogus.  Actual IDs specified in the original source
    // code are required to have the upper bit set.  Anything else must have been manufactured
    // at some point to cover up an error.
    if (desiredId & (1ull << 63)) {
      node.addError(kj::str("Duplicate ID @0x", kj::hex(desiredId), "."));
      insertResult.first->second->addError(
          kj::str("ID @0x", kj::hex(desiredId), " originally used here."));
    }

    // Assign a new bogus ID.
1172
    desiredId = nextBogusId++;
Kenton Varda's avatar
Kenton Varda committed
1173 1174 1175
  }
}

1176 1177 1178
kj::Maybe<Compiler::Node&> Compiler::Impl::findNode(uint64_t id) {
  auto iter = nodesById.find(id);
  if (iter == nodesById.end()) {
Kenton Varda's avatar
Kenton Varda committed
1179 1180 1181 1182 1183 1184
    return nullptr;
  } else {
    return *iter->second;
  }
}

1185
kj::Maybe<Compiler::Node&> Compiler::Impl::lookupBuiltin(kj::StringPtr name) {
Kenton Varda's avatar
Kenton Varda committed
1186 1187 1188 1189 1190 1191 1192 1193
  auto iter = builtinDecls.find(name);
  if (iter == builtinDecls.end()) {
    return nullptr;
  } else {
    return *iter->second;
  }
}

1194 1195 1196 1197 1198 1199
Compiler::Node& Compiler::Impl::getBuiltin(Declaration::Which which) {
  auto iter = builtinDeclsByKind.find(which);
  KJ_REQUIRE(iter != builtinDeclsByKind.end(), "invalid builtin", (uint)which);
  return *iter->second;
}

1200
uint64_t Compiler::Impl::add(Module& module) {
1201
  return addInternal(module).getRootNode().getId();
1202 1203
}

1204
kj::Maybe<uint64_t> Compiler::Impl::lookup(uint64_t parent, kj::StringPtr childName) {
1205
  // Looking up members does not use the workspace, so we don't need to lock it.
1206
  KJ_IF_MAYBE(parentNode, findNode(parent)) {
Kenton Varda's avatar
Kenton Varda committed
1207 1208 1209 1210 1211 1212 1213
    KJ_IF_MAYBE(child, parentNode->resolveMember(childName)) {
      if (child->is<NodeTranslator::Resolver::ResolvedDecl>()) {
        return child->get<NodeTranslator::Resolver::ResolvedDecl>().id;
      } else {
        // An alias. We don't support looking up aliases with this method.
        return nullptr;
      }
1214 1215 1216
    } else {
      return nullptr;
    }
1217 1218 1219 1220 1221
  } else {
    KJ_FAIL_REQUIRE("lookup()s parameter 'parent' must be a known ID.", parent);
  }
}

Kenton Varda's avatar
Kenton Varda committed
1222
Orphan<List<schema::CodeGeneratorRequest::RequestedFile::Import>>
1223
    Compiler::Impl::getFileImportTable(Module& module, Orphanage orphanage) {
Kenton Varda's avatar
Kenton Varda committed
1224 1225 1226
  return addInternal(module).getFileImportTable(orphanage);
}

1227 1228
void Compiler::Impl::eagerlyCompile(uint64_t id, uint eagerness,
                                    const SchemaLoader& finalLoader) {
1229
  KJ_IF_MAYBE(node, findNode(id)) {
1230 1231
    std::unordered_map<Node*, uint> seen;
    node->traverse(eagerness, seen, finalLoader);
1232 1233 1234 1235 1236
  } else {
    KJ_FAIL_REQUIRE("id did not come from this Compiler.", id);
  }
}

Kenton Varda's avatar
Kenton Varda committed
1237
void Compiler::Impl::load(const SchemaLoader& loader, uint64_t id) const {
1238 1239 1240 1241 1242 1243 1244 1245 1246 1247
  // We know that this load() is only called from the bootstrap loader which is already protected
  // by our mutex, so we can drop thread-safety.
  auto& self = const_cast<Compiler::Impl&>(*this);

  KJ_IF_MAYBE(node, self.findNode(id)) {
    node->getBootstrapSchema();
  }
}

void Compiler::Impl::loadFinal(const SchemaLoader& loader, uint64_t id) {
Kenton Varda's avatar
Kenton Varda committed
1248
  KJ_IF_MAYBE(node, findNode(id)) {
1249
    node->loadFinalSchema(loader);
Kenton Varda's avatar
Kenton Varda committed
1250 1251 1252
  }
}

1253 1254
// =======================================================================================

1255 1256 1257
Compiler::Compiler(AnnotationFlag annotationFlag)
    : impl(kj::heap<Impl>(annotationFlag)),
      loader(*this) {}
1258
Compiler::~Compiler() noexcept(false) {}
1259

1260 1261
uint64_t Compiler::add(Module& module) const {
  return impl.lockExclusive()->get()->add(module);
1262 1263
}

1264
kj::Maybe<uint64_t> Compiler::lookup(uint64_t parent, kj::StringPtr childName) const {
1265
  return impl.lockExclusive()->get()->lookup(parent, childName);
1266 1267
}

Kenton Varda's avatar
Kenton Varda committed
1268
Orphan<List<schema::CodeGeneratorRequest::RequestedFile::Import>>
1269 1270
    Compiler::getFileImportTable(Module& module, Orphanage orphanage) const {
  return impl.lockExclusive()->get()->getFileImportTable(module, orphanage);
Kenton Varda's avatar
Kenton Varda committed
1271 1272
}

1273
void Compiler::eagerlyCompile(uint64_t id, uint eagerness) const {
1274
  impl.lockExclusive()->get()->eagerlyCompile(id, eagerness, loader);
1275 1276
}

1277 1278
void Compiler::clearWorkspace() const {
  impl.lockExclusive()->get()->clearWorkspace();
1279 1280
}

1281 1282
void Compiler::load(const SchemaLoader& loader, uint64_t id) const {
  impl.lockExclusive()->get()->loadFinal(loader, id);
1283 1284
}

Kenton Varda's avatar
Kenton Varda committed
1285 1286
}  // namespace compiler
}  // namespace capnp