schema-loader.c++ 75.2 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:
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:
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.
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.
21

Kenton Varda's avatar
Kenton Varda committed
22
#define CAPNP_PRIVATE
23 24
#include "schema-loader.h"
#include <unordered_map>
25
#include <unordered_set>
26 27 28
#include <map>
#include "message.h"
#include "arena.h"
Kenton Varda's avatar
Kenton Varda committed
29
#include <kj/debug.h>
30
#include <kj/exception.h>
31
#include <kj/arena.h>
32 33
#include <kj/vector.h>
#include <algorithm>
34

35
namespace capnp {
36

37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
namespace {

struct ByteArrayHash {
  size_t operator()(kj::ArrayPtr<const byte> bytes) const {
    // FNV hash. Probably sucks, but the code is simple.
    //
    // TODO(perf): Add CityHash or something to KJ and use it here.

    uint64_t hash = 0xcbf29ce484222325ull;
    for (byte b: bytes) {
      hash = hash * 0x100000001b3ull;
      hash ^= b;
    }
    return hash;
  }
};

struct ByteArrayEq {
  bool operator()(kj::ArrayPtr<const byte> a, kj::ArrayPtr<const byte> b) const {
    return a.size() == b.size() && memcmp(a.begin(), b.begin(), a.size()) == 0;
  }
};

struct SchemaBindingsPair {
  const _::RawSchema* schema;
  const _::RawBrandedSchema::Scope* scopeBindings;

  inline bool operator==(const SchemaBindingsPair& other) const {
    return schema == other.schema && scopeBindings == other.scopeBindings;
  }
};

struct SchemaBindingsPairHash {
  size_t operator()(SchemaBindingsPair pair) const {
    return 31 * reinterpret_cast<uintptr_t>(pair.schema) +
                reinterpret_cast<uintptr_t>(pair.scopeBindings);
  }
};

}  // namespace

78 79 80 81
bool hasDiscriminantValue(const schema::Field::Reader& reader) {
  return reader.getDiscriminantValue() != schema::Field::NO_DISCRIMINANT;
}

82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
class SchemaLoader::InitializerImpl: public _::RawSchema::Initializer {
public:
  inline explicit InitializerImpl(const SchemaLoader& loader): loader(loader), callback(nullptr) {}
  inline InitializerImpl(const SchemaLoader& loader, const LazyLoadCallback& callback)
      : loader(loader), callback(callback) {}

  inline kj::Maybe<const LazyLoadCallback&> getCallback() const { return callback; }

  void init(const _::RawSchema* schema) const override;

  inline bool operator==(decltype(nullptr)) const { return callback == nullptr; }

private:
  const SchemaLoader& loader;
  kj::Maybe<const LazyLoadCallback&> callback;
};

99 100 101 102 103 104 105 106 107 108
class SchemaLoader::BrandedInitializerImpl: public _::RawBrandedSchema::Initializer {
public:
  inline explicit BrandedInitializerImpl(const SchemaLoader& loader): loader(loader) {}

  void init(const _::RawBrandedSchema* schema) const override;

private:
  const SchemaLoader& loader;
};

109 110
class SchemaLoader::Impl {
public:
111 112
  inline explicit Impl(const SchemaLoader& loader)
      : initializer(loader), brandedInitializer(loader) {}
113
  inline Impl(const SchemaLoader& loader, const LazyLoadCallback& callback)
114
      : initializer(loader, callback), brandedInitializer(loader) {}
115

Kenton Varda's avatar
Kenton Varda committed
116
  _::RawSchema* load(const schema::Node::Reader& reader, bool isPlaceholder);
117

118
  _::RawSchema* loadNative(const _::RawSchema* nativeSchema);
119

120 121
  _::RawSchema* loadEmpty(uint64_t id, kj::StringPtr name, schema::Node::Which kind,
                          bool isPlaceholder);
122 123
  // Create a dummy empty schema of the given kind for the given id and load it.

124 125
  const _::RawBrandedSchema* makeBranded(
      const _::RawSchema* schema, schema::Brand::Reader proto,
126
      kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> clientBrand);
127

128 129 130 131 132 133
  struct TryGetResult {
    _::RawSchema* schema;
    kj::Maybe<const LazyLoadCallback&> callback;
  };

  TryGetResult tryGet(uint64_t typeId) const;
134

135 136
  const _::RawBrandedSchema* getUnbound(const _::RawSchema* schema);

137
  kj::Array<Schema> getAllLoaded() const;
138

139
  void requireStructSize(uint64_t id, uint dataWordCount, uint pointerCount);
140 141 142 143 144 145
  // Require any struct nodes loaded with this ID -- in the past and in the future -- to have at
  // least the given sizes.  Struct nodes that don't comply will simply be rewritten to comply.
  // This is used to ensure that parents of group nodes have at least the size of the group node,
  // so that allocating a struct that contains a group then getting the group node and setting
  // its fields can't possibly write outside of the allocated space.

146
  kj::Arena arena;
147 148

private:
149 150 151 152
  std::unordered_set<kj::ArrayPtr<const byte>, ByteArrayHash, ByteArrayEq> dedupTable;
  // Records raw segments of memory in the arena against which we my want to de-dupe later
  // additions. Specifically, RawBrandedSchema binding tables are de-duped.

153
  std::unordered_map<uint64_t, _::RawSchema*> schemas;
154
  std::unordered_map<SchemaBindingsPair, _::RawBrandedSchema*, SchemaBindingsPairHash> brands;
155
  std::unordered_map<const _::RawSchema*, _::RawBrandedSchema*> unboundBrands;
156

157 158 159 160 161 162
  struct RequiredSize {
    uint16_t dataWordCount;
    uint16_t pointerCount;
  };
  std::unordered_map<uint64_t, RequiredSize> structSizeRequirements;

163
  InitializerImpl initializer;
164
  BrandedInitializerImpl brandedInitializer;
165

Kenton Varda's avatar
Kenton Varda committed
166
  kj::ArrayPtr<word> makeUncheckedNode(schema::Node::Reader node);
167 168 169
  // Construct a copy of the given schema node, allocated as a single-segment ("unchecked") node
  // within the loader's arena.

Kenton Varda's avatar
Kenton Varda committed
170
  kj::ArrayPtr<word> makeUncheckedNodeEnforcingSizeRequirements(schema::Node::Reader node);
171 172 173 174 175 176 177
  // Like makeUncheckedNode() but if structSizeRequirements has a requirement for this node which
  // is larger than the node claims to be, the size will be edited to comply.  This should be rare.
  // If the incoming node is not a struct, any struct size requirements will be ignored, but if
  // such requirements exist, this indicates an inconsistency that could cause exceptions later on
  // (but at least can't cause memory corruption).

  kj::ArrayPtr<word> rewriteStructNodeWithSizes(
178
      schema::Node::Reader node, uint dataWordCount, uint pointerCount);
179 180 181 182 183
  // Make a copy of the given node (which must be a struct node) and set its sizes to be the max
  // of what it said already and the given sizes.

  // If the encoded node does not meet the given struct size requirements, make a new copy that
  // does.
184
  void applyStructSizeRequirement(_::RawSchema* raw, uint dataWordCount, uint pointerCount);
185

186
  const _::RawBrandedSchema* makeBranded(const _::RawSchema* schema,
187 188 189
      kj::ArrayPtr<const _::RawBrandedSchema::Scope> scopes);

  kj::ArrayPtr<const _::RawBrandedSchema::Dependency> makeBrandedDependencies(
190 191
      const _::RawSchema* schema,
      kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> bindings);
192

Kenton Varda's avatar
Kenton Varda committed
193
  void makeDep(_::RawBrandedSchema::Binding& result,
194
      schema::Type::Reader type, kj::StringPtr scopeName,
195
      kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> brandBindings);
Kenton Varda's avatar
Kenton Varda committed
196
  void makeDep(_::RawBrandedSchema::Binding& result,
197
      uint64_t typeId, schema::Type::Which whichType, schema::Node::Which expectedKind,
198
      schema::Brand::Reader brand, kj::StringPtr scopeName,
199
      kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> brandBindings);
200
  // Looks up the schema and brand for a dependency, or creates lazily-evaluated placeholders if
Kenton Varda's avatar
Kenton Varda committed
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217
  // they don't already exist, and fills in `result`. `scopeName` is a human-readable name of the
  // place where the type appeared.
  //
  // Note that we don't simply return a Binding because we need to be careful about initialization
  // to ensure that our byte-based de-duplification works. If we constructed a Binding on the stack
  // and returned it, padding bytes in that Binding could go uninitialized, causing it to appear
  // unique when it's not. It is expected that `result` has been zero'd via memset() before these
  // methods are called.

  const _::RawBrandedSchema* makeDepSchema(
      schema::Type::Reader type, kj::StringPtr scopeName,
      kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> brandBindings);
  const _::RawBrandedSchema* makeDepSchema(
      uint64_t typeId, schema::Type::Which whichType, schema::Node::Which expectedKind,
      schema::Brand::Reader brand, kj::StringPtr scopeName,
      kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> brandBindings);
  // Invoke makeDep() then return the result's schema, or nullptr if it's a primitive type.
218 219 220 221 222 223 224 225 226

  template <typename T>
  kj::ArrayPtr<const T> copyDeduped(kj::ArrayPtr<const T> values);
  template <typename T>
  kj::ArrayPtr<const T> copyDeduped(kj::ArrayPtr<T> values);
  // Copy the given array into the arena and return the copy -- unless an identical array
  // was copied previously, in which case the existing copy is returned.

  friend class SchemaLoader::BrandedInitializerImpl;
227 228 229 230
};

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

231 232 233 234
inline static void verifyVoid(Void value) {}
// Calls to this will break if the parameter type changes to non-void.  We use this to detect
// when the code needs updating.

235 236 237 238
class SchemaLoader::Validator {
public:
  Validator(SchemaLoader::Impl& loader): loader(loader) {}

Kenton Varda's avatar
Kenton Varda committed
239
  bool validate(const schema::Node::Reader& node) {
240 241 242 243
    isValid = true;
    nodeName = node.getDisplayName();
    dependencies.clear();

244
    KJ_CONTEXT("validating schema node", nodeName, (uint)node.which());
245

246 247 248 249 250 251 252
    if (node.getParameters().size() > 0) {
      KJ_REQUIRE(node.getIsGeneric(), "if parameter list is non-empty, isGeneric must be true") {
        isValid = false;
        return false;
      }
    }

253
    switch (node.which()) {
Kenton Varda's avatar
Kenton Varda committed
254
      case schema::Node::FILE:
255
        verifyVoid(node.getFile());
256
        break;
Kenton Varda's avatar
Kenton Varda committed
257
      case schema::Node::STRUCT:
258
        validate(node.getStruct(), node.getScopeId());
259
        break;
Kenton Varda's avatar
Kenton Varda committed
260
      case schema::Node::ENUM:
261
        validate(node.getEnum());
262
        break;
Kenton Varda's avatar
Kenton Varda committed
263
      case schema::Node::INTERFACE:
264
        validate(node.getInterface());
265
        break;
Kenton Varda's avatar
Kenton Varda committed
266
      case schema::Node::CONST:
267
        validate(node.getConst());
268
        break;
Kenton Varda's avatar
Kenton Varda committed
269
      case schema::Node::ANNOTATION:
270
        validate(node.getAnnotation());
271 272 273 274 275 276 277
        break;
    }

    // We accept and pass through node types we don't recognize.
    return isValid;
  }

278
  const _::RawSchema** makeDependencyArray(uint32_t* count) {
279
    *count = dependencies.size();
280 281
    kj::ArrayPtr<const _::RawSchema*> result =
        loader.arena.allocateArray<const _::RawSchema*>(*count);
282 283 284 285
    uint pos = 0;
    for (auto& dep: dependencies) {
      result[pos++] = dep.second;
    }
286
    KJ_DASSERT(pos == *count);
287
    return result.begin();
288 289
  }

290
  const uint16_t* makeMemberInfoArray(uint32_t* count) {
291
    *count = members.size();
292
    kj::ArrayPtr<uint16_t> result = loader.arena.allocateArray<uint16_t>(*count);
293 294
    uint pos = 0;
    for (auto& member: members) {
295
      result[pos++] = member.second;
296
    }
297
    KJ_DASSERT(pos == *count);
298
    return result.begin();
299 300
  }

301 302 303 304
  const uint16_t* makeMembersByDiscriminantArray() {
    return membersByDiscriminant.begin();
  }

305 306 307 308
private:
  SchemaLoader::Impl& loader;
  Text::Reader nodeName;
  bool isValid;
309
  std::map<uint64_t, _::RawSchema*> dependencies;
310

311 312 313 314
  // Maps name -> index for each member.
  std::map<Text::Reader, uint> members;

  kj::ArrayPtr<uint16_t> membersByDiscriminant;
315 316

#define VALIDATE_SCHEMA(condition, ...) \
317
  KJ_REQUIRE(condition, ##__VA_ARGS__) { isValid = false; return; }
318
#define FAIL_VALIDATE_SCHEMA(...) \
319
  KJ_FAIL_REQUIRE(__VA_ARGS__) { isValid = false; return; }
320

321 322 323
  void validateMemberName(kj::StringPtr name, uint index) {
    bool isNewName = members.insert(std::make_pair(name, index)).second;
    VALIDATE_SCHEMA(isNewName, "duplicate name", name);
Kenton Varda's avatar
Kenton Varda committed
324 325
  }

Kenton Varda's avatar
Kenton Varda committed
326
  void validate(const schema::Node::Struct::Reader& structNode, uint64_t scopeId) {
327 328
    uint dataSizeInBits = structNode.getDataWordCount() * 64;
    uint pointerCount = structNode.getPointerCount();
329

330
    auto fields = structNode.getFields();
331

332
    KJ_STACK_ARRAY(bool, sawCodeOrder, fields.size(), 32, 256);
333 334
    memset(sawCodeOrder.begin(), 0, sawCodeOrder.size() * sizeof(sawCodeOrder[0]));

335 336 337 338 339 340 341 342 343 344 345 346
    KJ_STACK_ARRAY(bool, sawDiscriminantValue, structNode.getDiscriminantCount(), 32, 256);
    memset(sawDiscriminantValue.begin(), 0,
           sawDiscriminantValue.size() * sizeof(sawDiscriminantValue[0]));

    if (structNode.getDiscriminantCount() > 0) {
      VALIDATE_SCHEMA(structNode.getDiscriminantCount() != 1,
                      "union must have at least two members");
      VALIDATE_SCHEMA(structNode.getDiscriminantCount() <= fields.size(),
                      "struct can't have more union fields than total fields");

      VALIDATE_SCHEMA((structNode.getDiscriminantOffset() + 1) * 16 <= dataSizeInBits,
                      "union discriminant is out-of-bounds");
347 348
    }

349 350 351
    membersByDiscriminant = loader.arena.allocateArray<uint16_t>(fields.size());
    uint discriminantPos = 0;
    uint nonDiscriminantPos = structNode.getDiscriminantCount();
352

353 354 355 356
    uint index = 0;
    uint nextOrdinal = 0;
    for (auto field: fields) {
      KJ_CONTEXT("validating struct field", field.getName());
357

358 359 360 361 362
      validateMemberName(field.getName(), index);
      VALIDATE_SCHEMA(field.getCodeOrder() < sawCodeOrder.size() &&
                      !sawCodeOrder[field.getCodeOrder()],
                      "invalid codeOrder");
      sawCodeOrder[field.getCodeOrder()] = true;
363

364
      auto ordinal = field.getOrdinal();
365
      if (ordinal.isExplicit()) {
366 367 368
        VALIDATE_SCHEMA(ordinal.getExplicit() >= nextOrdinal,
                        "fields were not ordered by ordinal");
        nextOrdinal = ordinal.getExplicit() + 1;
369
      }
Kenton Varda's avatar
Kenton Varda committed
370

371
      if (hasDiscriminantValue(field)) {
372 373 374 375 376 377 378 379 380 381 382
        VALIDATE_SCHEMA(field.getDiscriminantValue() < sawDiscriminantValue.size() &&
                        !sawDiscriminantValue[field.getDiscriminantValue()],
                        "invalid discriminantValue");
        sawDiscriminantValue[field.getDiscriminantValue()] = true;

        membersByDiscriminant[discriminantPos++] = index;
      } else {
        VALIDATE_SCHEMA(nonDiscriminantPos <= fields.size(),
                        "discriminantCount did not match fields");
        membersByDiscriminant[nonDiscriminantPos++] = index;
      }
Kenton Varda's avatar
Kenton Varda committed
383

384
      switch (field.which()) {
385 386
        case schema::Field::SLOT: {
          auto slot = field.getSlot();
Kenton Varda's avatar
Kenton Varda committed
387

388 389
          uint fieldBits = 0;
          bool fieldIsPointer = false;
390 391 392
          validate(slot.getType(), slot.getDefaultValue(), &fieldBits, &fieldIsPointer);
          VALIDATE_SCHEMA(fieldBits * (slot.getOffset() + 1) <= dataSizeInBits &&
                          fieldIsPointer * (slot.getOffset() + 1) <= pointerCount,
393
                          "field offset out-of-bounds",
394
                          slot.getOffset(), dataSizeInBits, pointerCount);
Kenton Varda's avatar
Kenton Varda committed
395

396
          break;
Kenton Varda's avatar
Kenton Varda committed
397 398
        }

Kenton Varda's avatar
Kenton Varda committed
399
        case schema::Field::GROUP:
400
          // Require that the group is a struct node.
401
          validateTypeId(field.getGroup().getTypeId(), schema::Node::STRUCT);
402
          break;
Kenton Varda's avatar
Kenton Varda committed
403
      }
404 405

      ++index;
406 407
    }

408 409 410 411 412 413
    // If the above code is correct, these should pass.
    KJ_ASSERT(discriminantPos == structNode.getDiscriminantCount());
    KJ_ASSERT(nonDiscriminantPos == fields.size());

    if (structNode.getIsGroup()) {
      VALIDATE_SCHEMA(scopeId != 0, "group node missing scopeId");
414

415 416
      // Require that the group's scope has at least the same size as the group, so that anyone
      // constructing an instance of the outer scope can safely read/write the group.
417
      loader.requireStructSize(scopeId, structNode.getDataWordCount(),
418
                               structNode.getPointerCount());
419 420

      // Require that the parent type is a struct.
Kenton Varda's avatar
Kenton Varda committed
421
      validateTypeId(scopeId, schema::Node::STRUCT);
422 423 424
    }
  }

425 426
  void validate(const schema::Node::Enum::Reader& enumNode) {
    auto enumerants = enumNode.getEnumerants();
427
    KJ_STACK_ARRAY(bool, sawCodeOrder, enumerants.size(), 32, 256);
428 429 430 431
    memset(sawCodeOrder.begin(), 0, sawCodeOrder.size() * sizeof(sawCodeOrder[0]));

    uint index = 0;
    for (auto enumerant: enumerants) {
432
      validateMemberName(enumerant.getName(), index++);
433 434 435 436 437 438 439 440

      VALIDATE_SCHEMA(enumerant.getCodeOrder() < enumerants.size() &&
                      !sawCodeOrder[enumerant.getCodeOrder()],
                      "invalid codeOrder", enumerant.getName());
      sawCodeOrder[enumerant.getCodeOrder()] = true;
    }
  }

441
  void validate(const schema::Node::Interface::Reader& interfaceNode) {
442
    for (auto extend: interfaceNode.getSuperclasses()) {
Kenton Varda's avatar
Kenton Varda committed
443
      validateTypeId(extend.getId(), schema::Node::INTERFACE);
444
      validate(extend.getBrand());
445 446
    }

447
    auto methods = interfaceNode.getMethods();
448
    KJ_STACK_ARRAY(bool, sawCodeOrder, methods.size(), 32, 256);
449 450 451 452
    memset(sawCodeOrder.begin(), 0, sawCodeOrder.size() * sizeof(sawCodeOrder[0]));

    uint index = 0;
    for (auto method: methods) {
453
      KJ_CONTEXT("validating method", method.getName());
454
      validateMemberName(method.getName(), index++);
455 456 457 458 459 460

      VALIDATE_SCHEMA(method.getCodeOrder() < methods.size() &&
                      !sawCodeOrder[method.getCodeOrder()],
                      "invalid codeOrder");
      sawCodeOrder[method.getCodeOrder()] = true;

461
      validateTypeId(method.getParamStructType(), schema::Node::STRUCT);
462
      validate(method.getParamBrand());
463
      validateTypeId(method.getResultStructType(), schema::Node::STRUCT);
464
      validate(method.getResultBrand());
465 466 467
    }
  }

Kenton Varda's avatar
Kenton Varda committed
468
  void validate(const schema::Node::Const::Reader& constNode) {
469 470 471 472 473
    uint dummy1;
    bool dummy2;
    validate(constNode.getType(), constNode.getValue(), &dummy1, &dummy2);
  }

Kenton Varda's avatar
Kenton Varda committed
474
  void validate(const schema::Node::Annotation::Reader& annotationNode) {
475 476 477
    validate(annotationNode.getType());
  }

Kenton Varda's avatar
Kenton Varda committed
478
  void validate(const schema::Type::Reader& type, const schema::Value::Reader& value,
479 480 481
                uint* dataSizeInBits, bool* isPointer) {
    validate(type);

Kenton Varda's avatar
Kenton Varda committed
482
    schema::Value::Which expectedValueType = schema::Value::VOID;
483
    bool hadCase = false;
484
    switch (type.which()) {
485
#define HANDLE_TYPE(name, bits, ptr) \
Kenton Varda's avatar
Kenton Varda committed
486 487
      case schema::Type::name: \
        expectedValueType = schema::Value::name; \
488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508
        *dataSizeInBits = bits; *isPointer = ptr; \
        hadCase = true; \
        break;
      HANDLE_TYPE(VOID, 0, false)
      HANDLE_TYPE(BOOL, 1, false)
      HANDLE_TYPE(INT8, 8, false)
      HANDLE_TYPE(INT16, 16, false)
      HANDLE_TYPE(INT32, 32, false)
      HANDLE_TYPE(INT64, 64, false)
      HANDLE_TYPE(UINT8, 8, false)
      HANDLE_TYPE(UINT16, 16, false)
      HANDLE_TYPE(UINT32, 32, false)
      HANDLE_TYPE(UINT64, 64, false)
      HANDLE_TYPE(FLOAT32, 32, false)
      HANDLE_TYPE(FLOAT64, 64, false)
      HANDLE_TYPE(TEXT, 0, true)
      HANDLE_TYPE(DATA, 0, true)
      HANDLE_TYPE(LIST, 0, true)
      HANDLE_TYPE(ENUM, 16, false)
      HANDLE_TYPE(STRUCT, 0, true)
      HANDLE_TYPE(INTERFACE, 0, true)
509
      HANDLE_TYPE(ANY_POINTER, 0, true)
510 511 512 513
#undef HANDLE_TYPE
    }

    if (hadCase) {
514 515
      VALIDATE_SCHEMA(value.which() == expectedValueType, "Value did not match type.",
                      (uint)value.which(), (uint)expectedValueType);
516 517 518
    }
  }

Kenton Varda's avatar
Kenton Varda committed
519
  void validate(const schema::Type::Reader& type) {
520
    switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
521 522 523 524 525 526 527 528 529 530 531 532 533 534
      case schema::Type::VOID:
      case schema::Type::BOOL:
      case schema::Type::INT8:
      case schema::Type::INT16:
      case schema::Type::INT32:
      case schema::Type::INT64:
      case schema::Type::UINT8:
      case schema::Type::UINT16:
      case schema::Type::UINT32:
      case schema::Type::UINT64:
      case schema::Type::FLOAT32:
      case schema::Type::FLOAT64:
      case schema::Type::TEXT:
      case schema::Type::DATA:
535
      case schema::Type::ANY_POINTER:
536 537
        break;

538 539 540
      case schema::Type::STRUCT: {
        auto structType = type.getStruct();
        validateTypeId(structType.getTypeId(), schema::Node::STRUCT);
541
        validate(structType.getBrand());
542
        break;
543 544 545 546
      }
      case schema::Type::ENUM: {
        auto enumType = type.getEnum();
        validateTypeId(enumType.getTypeId(), schema::Node::ENUM);
547
        validate(enumType.getBrand());
548
        break;
549 550 551 552
      }
      case schema::Type::INTERFACE: {
        auto interfaceType = type.getInterface();
        validateTypeId(interfaceType.getTypeId(), schema::Node::INTERFACE);
553
        validate(interfaceType.getBrand());
554
        break;
555
      }
556

Kenton Varda's avatar
Kenton Varda committed
557
      case schema::Type::LIST:
558
        validate(type.getList().getElementType());
559 560 561 562 563 564
        break;
    }

    // We intentionally allow unknown types.
  }

565 566
  void validate(const schema::Brand::Reader& brand) {
    for (auto scope: brand.getScopes()) {
567
      switch (scope.which()) {
568
        case schema::Brand::Scope::BIND:
569 570
          for (auto binding: scope.getBind()) {
            switch (binding.which()) {
571
              case schema::Brand::Binding::UNBOUND:
572
                break;
573
              case schema::Brand::Binding::TYPE: {
574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610
                auto type = binding.getType();
                validate(type);
                bool isPointer = true;
                switch (type.which()) {
                  case schema::Type::VOID:
                  case schema::Type::BOOL:
                  case schema::Type::INT8:
                  case schema::Type::INT16:
                  case schema::Type::INT32:
                  case schema::Type::INT64:
                  case schema::Type::UINT8:
                  case schema::Type::UINT16:
                  case schema::Type::UINT32:
                  case schema::Type::UINT64:
                  case schema::Type::FLOAT32:
                  case schema::Type::FLOAT64:
                  case schema::Type::ENUM:
                    isPointer = false;
                    break;

                  case schema::Type::TEXT:
                  case schema::Type::DATA:
                  case schema::Type::ANY_POINTER:
                  case schema::Type::STRUCT:
                  case schema::Type::INTERFACE:
                  case schema::Type::LIST:
                    isPointer = true;
                    break;
                }
                VALIDATE_SCHEMA(isPointer,
                    "generic type parameter must be a pointer type", type);

                break;
              }
            }
          }
          break;
611
        case schema::Brand::Scope::INHERIT:
612 613 614 615 616
          break;
      }
    }
  }

Kenton Varda's avatar
Kenton Varda committed
617
  void validateTypeId(uint64_t id, schema::Node::Which expectedKind) {
618
    _::RawSchema* existing = loader.tryGet(id).schema;
619
    if (existing != nullptr) {
Kenton Varda's avatar
Kenton Varda committed
620
      auto node = readMessageUnchecked<schema::Node>(existing->encodedNode);
621
      VALIDATE_SCHEMA(node.which() == expectedKind,
622
          "expected a different kind of node for this ID",
623
          id, (uint)expectedKind, (uint)node.which(), node.getDisplayName());
624 625 626 627 628
      dependencies.insert(std::make_pair(id, existing));
      return;
    }

    dependencies.insert(std::make_pair(id, loader.loadEmpty(
629
        id, kj::str("(unknown type used by ", nodeName , ")"), expectedKind, true)));
630 631 632 633 634 635 636 637 638 639 640 641
  }

#undef VALIDATE_SCHEMA
#undef FAIL_VALIDATE_SCHEMA
};

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

class SchemaLoader::CompatibilityChecker {
public:
  CompatibilityChecker(SchemaLoader::Impl& loader): loader(loader) {}

Kenton Varda's avatar
Kenton Varda committed
642 643
  bool shouldReplace(const schema::Node::Reader& existingNode,
                     const schema::Node::Reader& replacement,
644
                     bool preferReplacementIfEquivalent) {
645 646 647
    this->existingNode = existingNode;
    this->replacementNode = replacement;

648 649
    KJ_CONTEXT("checking compatibility with previously-loaded node of the same id",
               existingNode.getDisplayName());
650

651
    KJ_DREQUIRE(existingNode.getId() == replacement.getId());
652 653 654 655 656 657

    nodeName = existingNode.getDisplayName();
    compatibility = EQUIVALENT;

    checkCompatibility(existingNode, replacement);

658 659
    // Prefer the newer schema.
    return preferReplacementIfEquivalent ? compatibility != OLDER : compatibility == NEWER;
660 661 662 663 664
  }

private:
  SchemaLoader::Impl& loader;
  Text::Reader nodeName;
665 666
  schema::Node::Reader existingNode;
  schema::Node::Reader replacementNode;
667 668 669 670 671 672 673 674 675 676

  enum Compatibility {
    EQUIVALENT,
    OLDER,
    NEWER,
    INCOMPATIBLE
  };
  Compatibility compatibility;

#define VALIDATE_SCHEMA(condition, ...) \
677
  KJ_REQUIRE(condition, ##__VA_ARGS__) { compatibility = INCOMPATIBLE; return; }
678
#define FAIL_VALIDATE_SCHEMA(...) \
679
  KJ_FAIL_REQUIRE(__VA_ARGS__) { compatibility = INCOMPATIBLE; return; }
680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712

  void replacementIsNewer() {
    switch (compatibility) {
      case EQUIVALENT:
        compatibility = NEWER;
        break;
      case OLDER:
        FAIL_VALIDATE_SCHEMA("Schema node contains some changes that are upgrades and some "
            "that are downgrades.  All changes must be in the same direction for compatibility.");
        break;
      case NEWER:
        break;
      case INCOMPATIBLE:
        break;
    }
  }

  void replacementIsOlder() {
    switch (compatibility) {
      case EQUIVALENT:
        compatibility = OLDER;
        break;
      case OLDER:
        break;
      case NEWER:
        FAIL_VALIDATE_SCHEMA("Schema node contains some changes that are upgrades and some "
            "that are downgrades.  All changes must be in the same direction for compatibility.");
        break;
      case INCOMPATIBLE:
        break;
    }
  }

Kenton Varda's avatar
Kenton Varda committed
713 714
  void checkCompatibility(const schema::Node::Reader& node,
                          const schema::Node::Reader& replacement) {
715 716 717
    // Returns whether `replacement` is equivalent, older than, newer than, or incompatible with
    // `node`.  If exceptions are enabled, this will throw an exception on INCOMPATIBLE.

718
    VALIDATE_SCHEMA(node.which() == replacement.which(),
719 720
                    "kind of declaration changed");

721
    // No need to check compatibility of most of the non-body parts of the node:
722 723 724
    // - Arbitrary renaming and moving between scopes is allowed.
    // - Annotations are ignored for compatibility purposes.

725 726 727 728 729 730
    if (replacement.getParameters().size() > node.getParameters().size()) {
      replacementIsNewer();
    } else if (replacement.getParameters().size() < node.getParameters().size()) {
      replacementIsOlder();
    }

731
    switch (node.which()) {
Kenton Varda's avatar
Kenton Varda committed
732
      case schema::Node::FILE:
733
        verifyVoid(node.getFile());
734
        break;
Kenton Varda's avatar
Kenton Varda committed
735
      case schema::Node::STRUCT:
736 737
        checkCompatibility(node.getStruct(), replacement.getStruct(),
                           node.getScopeId(), replacement.getScopeId());
738
        break;
Kenton Varda's avatar
Kenton Varda committed
739
      case schema::Node::ENUM:
740
        checkCompatibility(node.getEnum(), replacement.getEnum());
741
        break;
Kenton Varda's avatar
Kenton Varda committed
742
      case schema::Node::INTERFACE:
743
        checkCompatibility(node.getInterface(), replacement.getInterface());
744
        break;
Kenton Varda's avatar
Kenton Varda committed
745
      case schema::Node::CONST:
746
        checkCompatibility(node.getConst(), replacement.getConst());
747
        break;
Kenton Varda's avatar
Kenton Varda committed
748
      case schema::Node::ANNOTATION:
749
        checkCompatibility(node.getAnnotation(), replacement.getAnnotation());
750 751 752 753
        break;
    }
  }

Kenton Varda's avatar
Kenton Varda committed
754 755
  void checkCompatibility(const schema::Node::Struct::Reader& structNode,
                          const schema::Node::Struct::Reader& replacement,
756
                          uint64_t scopeId, uint64_t replacementScopeId) {
757
    if (replacement.getDataWordCount() > structNode.getDataWordCount()) {
758
      replacementIsNewer();
759
    } else if (replacement.getDataWordCount() < structNode.getDataWordCount()) {
760 761
      replacementIsOlder();
    }
762
    if (replacement.getPointerCount() > structNode.getPointerCount()) {
763
      replacementIsNewer();
764
    } else if (replacement.getPointerCount() < structNode.getPointerCount()) {
765 766
      replacementIsOlder();
    }
767 768 769 770 771 772 773 774 775 776 777
    if (replacement.getDiscriminantCount() > structNode.getDiscriminantCount()) {
      replacementIsNewer();
    } else if (replacement.getDiscriminantCount() < structNode.getDiscriminantCount()) {
      replacementIsOlder();
    }

    if (replacement.getDiscriminantCount() > 0 && structNode.getDiscriminantCount() > 0) {
      VALIDATE_SCHEMA(replacement.getDiscriminantOffset() == structNode.getDiscriminantOffset(),
                      "union discriminant position changed");
    }

778 779
    // The shared members should occupy corresponding positions in the member lists, since the
    // lists are sorted by ordinal.
780 781 782
    auto fields = structNode.getFields();
    auto replacementFields = replacement.getFields();
    uint count = std::min(fields.size(), replacementFields.size());
783

784
    if (replacementFields.size() > fields.size()) {
785
      replacementIsNewer();
786
    } else if (replacementFields.size() < fields.size()) {
787 788 789 790
      replacementIsOlder();
    }

    for (uint i = 0; i < count; i++) {
791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809
      checkCompatibility(fields[i], replacementFields[i]);
    }

    // For the moment, we allow "upgrading" from non-group to group, mainly so that the
    // placeholders we generate for group parents (which in the absence of more info, we assume to
    // be non-groups) can be replaced with groups.
    //
    // TODO(cleanup):  The placeholder approach is really breaking down.  Maybe we need to maintain
    //   a list of expectations for nodes we haven't loaded yet.
    if (structNode.getIsGroup()) {
      if (replacement.getIsGroup()) {
        VALIDATE_SCHEMA(replacementScopeId == scopeId, "group node's scope changed");
      } else {
        replacementIsOlder();
      }
    } else {
      if (replacement.getIsGroup()) {
        replacementIsNewer();
      }
810 811 812
    }
  }

Kenton Varda's avatar
Kenton Varda committed
813 814
  void checkCompatibility(const schema::Field::Reader& field,
                          const schema::Field::Reader& replacement) {
815
    KJ_CONTEXT("comparing struct field", field.getName());
816

817 818
    // A field that is initially not in a union can be upgraded to be in one, as long as it has
    // discriminant 0.
819
    uint discriminant = hasDiscriminantValue(field) ? field.getDiscriminantValue() : 0;
820
    uint replacementDiscriminant =
821
        hasDiscriminantValue(replacement) ? replacement.getDiscriminantValue() : 0;
822
    VALIDATE_SCHEMA(discriminant == replacementDiscriminant, "Field discriminant changed.");
823

824
    switch (field.which()) {
825 826
      case schema::Field::SLOT: {
        auto slot = field.getSlot();
827

828
        switch (replacement.which()) {
829 830
          case schema::Field::SLOT: {
            auto replacementSlot = replacement.getSlot();
831

832
            checkCompatibility(slot.getType(), replacementSlot.getType(),
833
                               NO_UPGRADE_TO_STRUCT);
834 835
            checkDefaultCompatibility(slot.getDefaultValue(),
                                      replacementSlot.getDefaultValue());
836

837
            VALIDATE_SCHEMA(slot.getOffset() == replacementSlot.getOffset(),
838 839 840 841
                            "field position changed");
            break;
          }
          case schema::Field::GROUP:
842
            checkUpgradeToStruct(slot.getType(), replacement.getGroup().getTypeId(),
843
                                 existingNode, field);
844 845
            break;
        }
846 847 848

        break;
      }
Kenton Varda's avatar
Kenton Varda committed
849

Kenton Varda's avatar
Kenton Varda committed
850
      case schema::Field::GROUP:
851
        switch (replacement.which()) {
852 853
          case schema::Field::SLOT:
            checkUpgradeToStruct(replacement.getSlot().getType(), field.getGroup().getTypeId(),
854 855 856
                                 replacementNode, replacement);
            break;
          case schema::Field::GROUP:
857 858
            VALIDATE_SCHEMA(field.getGroup().getTypeId() == replacement.getGroup().getTypeId(),
                            "group id changed");
859 860
            break;
        }
861 862 863 864
        break;
    }
  }

865 866 867 868
  void checkCompatibility(const schema::Node::Enum::Reader& enumNode,
                          const schema::Node::Enum::Reader& replacement) {
    uint size = enumNode.getEnumerants().size();
    uint replacementSize = replacement.getEnumerants().size();
869 870 871 872 873 874 875
    if (replacementSize > size) {
      replacementIsNewer();
    } else if (replacementSize < size) {
      replacementIsOlder();
    }
  }

876 877
  void checkCompatibility(const schema::Node::Interface::Reader& interfaceNode,
                          const schema::Node::Interface::Reader& replacement) {
878 879 880
    {
      // Check superclasses.

881 882 883 884
      kj::Vector<uint64_t> superclasses;
      kj::Vector<uint64_t> replacementSuperclasses;
      for (auto superclass: interfaceNode.getSuperclasses()) {
        superclasses.add(superclass.getId());
885
      }
886 887
      for (auto superclass: replacement.getSuperclasses()) {
        replacementSuperclasses.add(superclass.getId());
888
      }
889 890
      std::sort(superclasses.begin(), superclasses.end());
      std::sort(replacementSuperclasses.begin(), replacementSuperclasses.end());
891

892 893
      auto iter = superclasses.begin();
      auto replacementIter = replacementSuperclasses.begin();
894

895 896
      while (iter != superclasses.end() || replacementIter != replacementSuperclasses.end()) {
        if (iter == superclasses.end()) {
897 898
          replacementIsNewer();
          break;
899
        } else if (replacementIter == replacementSuperclasses.end()) {
900 901 902 903 904 905 906 907 908 909 910 911 912 913 914
          replacementIsOlder();
          break;
        } else if (*iter < *replacementIter) {
          replacementIsOlder();
          ++iter;
        } else if (*iter > *replacementIter) {
          replacementIsNewer();
          ++replacementIter;
        } else {
          ++iter;
          ++replacementIter;
        }
      }
    }

915 916 917
    auto methods = interfaceNode.getMethods();
    auto replacementMethods = replacement.getMethods();

918 919 920 921 922 923 924 925 926 927 928 929 930
    if (replacementMethods.size() > methods.size()) {
      replacementIsNewer();
    } else if (replacementMethods.size() < methods.size()) {
      replacementIsOlder();
    }

    uint count = std::min(methods.size(), replacementMethods.size());

    for (uint i = 0; i < count; i++) {
      checkCompatibility(methods[i], replacementMethods[i]);
    }
  }

Kenton Varda's avatar
Kenton Varda committed
931 932
  void checkCompatibility(const schema::Method::Reader& method,
                          const schema::Method::Reader& replacement) {
933
    KJ_CONTEXT("comparing method", method.getName());
934

935 936 937 938 939
    // TODO(someday):  Allow named parameter list to be replaced by compatible struct type.
    VALIDATE_SCHEMA(method.getParamStructType() == replacement.getParamStructType(),
                    "Updated method has different parameters.");
    VALIDATE_SCHEMA(method.getResultStructType() == replacement.getResultStructType(),
                    "Updated method has different results.");
940 941
  }

Kenton Varda's avatar
Kenton Varda committed
942 943
  void checkCompatibility(const schema::Node::Const::Reader& constNode,
                          const schema::Node::Const::Reader& replacement) {
944 945 946
    // Who cares?  These don't appear on the wire.
  }

Kenton Varda's avatar
Kenton Varda committed
947 948
  void checkCompatibility(const schema::Node::Annotation::Reader& annotationNode,
                          const schema::Node::Annotation::Reader& replacement) {
949 950 951 952 953 954 955 956
    // Who cares?  These don't appear on the wire.
  }

  enum UpgradeToStructMode {
    ALLOW_UPGRADE_TO_STRUCT,
    NO_UPGRADE_TO_STRUCT
  };

Kenton Varda's avatar
Kenton Varda committed
957 958
  void checkCompatibility(const schema::Type::Reader& type,
                          const schema::Type::Reader& replacement,
959
                          UpgradeToStructMode upgradeToStructMode) {
960
    if (replacement.which() != type.which()) {
961
      // Check for allowed "upgrade" to Data or AnyPointer.
962
      if (replacement.isData() && canUpgradeToData(type)) {
963 964
        replacementIsNewer();
        return;
965
      } else if (type.isData() && canUpgradeToData(replacement)) {
966 967
        replacementIsOlder();
        return;
968
      } else if (replacement.isAnyPointer() && canUpgradeToAnyPointer(type)) {
969 970
        replacementIsNewer();
        return;
971
      } else if (type.isAnyPointer() && canUpgradeToAnyPointer(replacement)) {
972 973 974 975 976
        replacementIsOlder();
        return;
      }

      if (upgradeToStructMode == ALLOW_UPGRADE_TO_STRUCT) {
977
        if (type.isStruct()) {
978
          checkUpgradeToStruct(replacement, type.getStruct().getTypeId());
979
          return;
980
        } else if (replacement.isStruct()) {
981
          checkUpgradeToStruct(type, replacement.getStruct().getTypeId());
982 983 984 985 986 987 988
          return;
        }
      }

      FAIL_VALIDATE_SCHEMA("a type was changed");
    }

989
    switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003
      case schema::Type::VOID:
      case schema::Type::BOOL:
      case schema::Type::INT8:
      case schema::Type::INT16:
      case schema::Type::INT32:
      case schema::Type::INT64:
      case schema::Type::UINT8:
      case schema::Type::UINT16:
      case schema::Type::UINT32:
      case schema::Type::UINT64:
      case schema::Type::FLOAT32:
      case schema::Type::FLOAT64:
      case schema::Type::TEXT:
      case schema::Type::DATA:
1004
      case schema::Type::ANY_POINTER:
1005 1006
        return;

Kenton Varda's avatar
Kenton Varda committed
1007
      case schema::Type::LIST:
1008 1009
        checkCompatibility(type.getList().getElementType(), replacement.getList().getElementType(),
                           ALLOW_UPGRADE_TO_STRUCT);
1010
        return;
1011

Kenton Varda's avatar
Kenton Varda committed
1012
      case schema::Type::ENUM:
1013 1014
        VALIDATE_SCHEMA(replacement.getEnum().getTypeId() == type.getEnum().getTypeId(),
                        "type changed enum type");
1015 1016
        return;

Kenton Varda's avatar
Kenton Varda committed
1017
      case schema::Type::STRUCT:
1018 1019 1020 1021 1022 1023 1024
        // TODO(someday):  If the IDs don't match, we should compare the two structs for
        //   compatibility.  This is tricky, though, because the new type's target may not yet be
        //   loaded.  In that case we could take the old type, make a copy of it, assign the new
        //   ID to the copy, and load() that.  That forces any struct type loaded for that ID to
        //   be compatible.  However, that has another problem, which is that it could be that the
        //   whole reason the type was replaced was to fork that type, and so an incompatibility
        //   could be very much expected.  This could be a rat hole...
1025
        VALIDATE_SCHEMA(replacement.getStruct().getTypeId() == type.getStruct().getTypeId(),
1026 1027 1028
                        "type changed to incompatible struct type");
        return;

Kenton Varda's avatar
Kenton Varda committed
1029
      case schema::Type::INTERFACE:
1030
        VALIDATE_SCHEMA(replacement.getInterface().getTypeId() == type.getInterface().getTypeId(),
1031
                        "type changed to incompatible interface type");
1032 1033 1034 1035 1036 1037
        return;
    }

    // We assume unknown types (from newer versions of Cap'n Proto?) are equivalent.
  }

1038 1039 1040
  void checkUpgradeToStruct(const schema::Type::Reader& type, uint64_t structTypeId,
                            kj::Maybe<schema::Node::Reader> matchSize = nullptr,
                            kj::Maybe<schema::Field::Reader> matchPosition = nullptr) {
1041 1042 1043 1044 1045 1046 1047
    // We can't just look up the target struct and check it because it may not have been loaded
    // yet.  Instead, we contrive a struct that looks like what we want and load() that, which
    // guarantees that any incompatibility will be caught either now or when the real version of
    // that struct is loaded.

    word scratch[32];
    memset(scratch, 0, sizeof(scratch));
1048
    MallocMessageBuilder builder(scratch);
Kenton Varda's avatar
Kenton Varda committed
1049
    auto node = builder.initRoot<schema::Node>();
1050
    node.setId(structTypeId);
1051
    node.setDisplayName(kj::str("(unknown type used in ", nodeName, ")"));
1052
    auto structNode = node.initStruct();
1053

1054
    switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
1055
      case schema::Type::VOID:
1056 1057
        structNode.setDataWordCount(0);
        structNode.setPointerCount(0);
1058 1059
        break;

Kenton Varda's avatar
Kenton Varda committed
1060
      case schema::Type::BOOL:
1061 1062
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
1063 1064
        break;

Kenton Varda's avatar
Kenton Varda committed
1065 1066
      case schema::Type::INT8:
      case schema::Type::UINT8:
1067 1068
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
1069 1070
        break;

Kenton Varda's avatar
Kenton Varda committed
1071 1072 1073
      case schema::Type::INT16:
      case schema::Type::UINT16:
      case schema::Type::ENUM:
1074 1075
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
1076 1077
        break;

Kenton Varda's avatar
Kenton Varda committed
1078 1079 1080
      case schema::Type::INT32:
      case schema::Type::UINT32:
      case schema::Type::FLOAT32:
1081 1082
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
1083 1084
        break;

Kenton Varda's avatar
Kenton Varda committed
1085 1086 1087
      case schema::Type::INT64:
      case schema::Type::UINT64:
      case schema::Type::FLOAT64:
1088 1089
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
1090 1091
        break;

Kenton Varda's avatar
Kenton Varda committed
1092 1093 1094 1095 1096
      case schema::Type::TEXT:
      case schema::Type::DATA:
      case schema::Type::LIST:
      case schema::Type::STRUCT:
      case schema::Type::INTERFACE:
1097
      case schema::Type::ANY_POINTER:
1098 1099
        structNode.setDataWordCount(0);
        structNode.setPointerCount(1);
1100 1101 1102
        break;
    }

1103 1104 1105 1106 1107 1108
    KJ_IF_MAYBE(s, matchSize) {
      auto match = s->getStruct();
      structNode.setDataWordCount(match.getDataWordCount());
      structNode.setPointerCount(match.getPointerCount());
    }

1109 1110 1111
    auto field = structNode.initFields(1)[0];
    field.setName("member0");
    field.setCodeOrder(0);
1112 1113
    auto slot = field.initSlot();
    slot.setType(type);
1114 1115 1116 1117 1118 1119 1120

    KJ_IF_MAYBE(p, matchPosition) {
      if (p->getOrdinal().isExplicit()) {
        field.getOrdinal().setExplicit(p->getOrdinal().getExplicit());
      } else {
        field.getOrdinal().setImplicit();
      }
1121 1122 1123
      auto matchSlot = p->getSlot();
      slot.setOffset(matchSlot.getOffset());
      slot.setDefaultValue(matchSlot.getDefaultValue());
1124 1125
    } else {
      field.getOrdinal().setExplicit(0);
1126
      slot.setOffset(0);
1127

1128
      schema::Value::Builder value = slot.initDefaultValue();
1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144
      switch (type.which()) {
        case schema::Type::VOID: value.setVoid(); break;
        case schema::Type::BOOL: value.setBool(false); break;
        case schema::Type::INT8: value.setInt8(0); break;
        case schema::Type::INT16: value.setInt16(0); break;
        case schema::Type::INT32: value.setInt32(0); break;
        case schema::Type::INT64: value.setInt64(0); break;
        case schema::Type::UINT8: value.setUint8(0); break;
        case schema::Type::UINT16: value.setUint16(0); break;
        case schema::Type::UINT32: value.setUint32(0); break;
        case schema::Type::UINT64: value.setUint64(0); break;
        case schema::Type::FLOAT32: value.setFloat32(0); break;
        case schema::Type::FLOAT64: value.setFloat64(0); break;
        case schema::Type::ENUM: value.setEnum(0); break;
        case schema::Type::TEXT: value.adoptText(Orphan<Text>()); break;
        case schema::Type::DATA: value.adoptData(Orphan<Data>()); break;
1145 1146
        case schema::Type::LIST: value.initList(); break;
        case schema::Type::STRUCT: value.initStruct(); break;
1147
        case schema::Type::INTERFACE: value.setInterface(); break;
1148
        case schema::Type::ANY_POINTER: value.initAnyPointer(); break;
1149 1150
      }
    }
1151

1152
    loader.load(node, true);
1153 1154
  }

Kenton Varda's avatar
Kenton Varda committed
1155
  bool canUpgradeToData(const schema::Type::Reader& type) {
1156
    if (type.isText()) {
1157
      return true;
1158
    } else if (type.isList()) {
1159
      switch (type.getList().getElementType().which()) {
Kenton Varda's avatar
Kenton Varda committed
1160 1161
        case schema::Type::INT8:
        case schema::Type::UINT8:
1162 1163 1164 1165 1166 1167 1168 1169 1170
          return true;
        default:
          return false;
      }
    } else {
      return false;
    }
  }

1171
  bool canUpgradeToAnyPointer(const schema::Type::Reader& type) {
1172
    switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185
      case schema::Type::VOID:
      case schema::Type::BOOL:
      case schema::Type::INT8:
      case schema::Type::INT16:
      case schema::Type::INT32:
      case schema::Type::INT64:
      case schema::Type::UINT8:
      case schema::Type::UINT16:
      case schema::Type::UINT32:
      case schema::Type::UINT64:
      case schema::Type::FLOAT32:
      case schema::Type::FLOAT64:
      case schema::Type::ENUM:
1186 1187
        return false;

Kenton Varda's avatar
Kenton Varda committed
1188 1189 1190 1191 1192
      case schema::Type::TEXT:
      case schema::Type::DATA:
      case schema::Type::LIST:
      case schema::Type::STRUCT:
      case schema::Type::INTERFACE:
1193
      case schema::Type::ANY_POINTER:
1194 1195 1196 1197 1198 1199 1200
        return true;
    }

    // Be lenient with unknown types.
    return true;
  }

Kenton Varda's avatar
Kenton Varda committed
1201 1202
  void checkDefaultCompatibility(const schema::Value::Reader& value,
                                 const schema::Value::Reader& replacement) {
1203 1204
    // Note that we test default compatibility only after testing type compatibility, and default
    // values have already been validated as matching their types, so this should pass.
1205
    KJ_ASSERT(value.which() == replacement.which()) {
1206 1207 1208 1209
      compatibility = INCOMPATIBLE;
      return;
    }

1210
    switch (value.which()) {
1211
#define HANDLE_TYPE(discrim, name) \
Kenton Varda's avatar
Kenton Varda committed
1212
      case schema::Value::discrim: \
1213
        VALIDATE_SCHEMA(value.get##name() == replacement.get##name(), "default value changed"); \
1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229
        break;
      HANDLE_TYPE(VOID, Void);
      HANDLE_TYPE(BOOL, Bool);
      HANDLE_TYPE(INT8, Int8);
      HANDLE_TYPE(INT16, Int16);
      HANDLE_TYPE(INT32, Int32);
      HANDLE_TYPE(INT64, Int64);
      HANDLE_TYPE(UINT8, Uint8);
      HANDLE_TYPE(UINT16, Uint16);
      HANDLE_TYPE(UINT32, Uint32);
      HANDLE_TYPE(UINT64, Uint64);
      HANDLE_TYPE(FLOAT32, Float32);
      HANDLE_TYPE(FLOAT64, Float64);
      HANDLE_TYPE(ENUM, Enum);
#undef HANDLE_TYPE

Kenton Varda's avatar
Kenton Varda committed
1230 1231 1232 1233 1234
      case schema::Value::TEXT:
      case schema::Value::DATA:
      case schema::Value::LIST:
      case schema::Value::STRUCT:
      case schema::Value::INTERFACE:
1235
      case schema::Value::ANY_POINTER:
1236 1237 1238 1239 1240 1241 1242 1243 1244
        // It's not a big deal if default values for pointers change, and it would be difficult for
        // us to compare these defaults here, so just let it slide.
        break;
    }
  }
};

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

Kenton Varda's avatar
Kenton Varda committed
1245
_::RawSchema* SchemaLoader::Impl::load(const schema::Node::Reader& reader, bool isPlaceholder) {
1246
  // Make a copy of the node which can be used unchecked.
1247
  kj::ArrayPtr<word> validated = makeUncheckedNodeEnforcingSizeRequirements(reader);
1248 1249 1250

  // Validate the copy.
  Validator validator(*this);
Kenton Varda's avatar
Kenton Varda committed
1251
  auto validatedReader = readMessageUnchecked<schema::Node>(validated.begin());
1252 1253 1254 1255 1256

  if (!validator.validate(validatedReader)) {
    // Not valid.  Construct an empty schema of the same type and return that.
    return loadEmpty(validatedReader.getId(),
                     validatedReader.getDisplayName(),
1257 1258
                     validatedReader.which(),
                     false);
1259 1260 1261
  }

  // Check if we already have a schema for this ID.
1262
  _::RawSchema*& slot = schemas[validatedReader.getId()];
1263
  bool shouldReplace;
1264
  bool shouldClearInitializer;
1265 1266
  if (slot == nullptr) {
    // Nope, allocate a new RawSchema.
1267
    slot = &arena.allocate<_::RawSchema>();
1268
    memset(&slot->defaultBrand, 0, sizeof(slot->defaultBrand));
1269 1270
    slot->id = validatedReader.getId();
    slot->canCastTo = nullptr;
1271
    slot->defaultBrand.generic = slot;
1272 1273
    slot->lazyInitializer = isPlaceholder ? &initializer : nullptr;
    slot->defaultBrand.lazyInitializer = isPlaceholder ? &brandedInitializer : nullptr;
1274
    shouldReplace = true;
1275
    shouldClearInitializer = false;
1276 1277
  } else {
    // Yes, check if it is compatible and figure out which schema is newer.
1278

1279 1280 1281
    // If the existing slot is a placeholder, but we're upgrading it to a non-placeholder, we
    // need to clear the initializer later.
    shouldClearInitializer = slot->lazyInitializer != nullptr && !isPlaceholder;
1282

Kenton Varda's avatar
Kenton Varda committed
1283
    auto existing = readMessageUnchecked<schema::Node>(slot->encodedNode);
1284
    CompatibilityChecker checker(*this);
1285 1286 1287 1288 1289

    // Prefer to replace the existing schema if the existing schema is a placeholder.  Otherwise,
    // prefer to keep the existing schema.
    shouldReplace = checker.shouldReplace(
        existing, validatedReader, slot->lazyInitializer != nullptr);
1290 1291
  }

1292 1293 1294
  if (shouldReplace) {
    // Initialize the RawSchema.
    slot->encodedNode = validated.begin();
Kenton Varda's avatar
Kenton Varda committed
1295
    slot->encodedSize = validated.size();
1296 1297
    slot->dependencies = validator.makeDependencyArray(&slot->dependencyCount);
    slot->membersByName = validator.makeMemberInfoArray(&slot->memberCount);
1298
    slot->membersByDiscriminant = validator.makeMembersByDiscriminantArray();
1299 1300 1301

    // Even though this schema isn't itself branded, it may have dependencies that are. So, we
    // need to set up the "dependencies" map under defaultBrand.
1302
    auto deps = makeBrandedDependencies(slot, kj::ArrayPtr<const _::RawBrandedSchema::Scope>());
1303 1304
    slot->defaultBrand.dependencies = deps.begin();
    slot->defaultBrand.dependencyCount = deps.size();
1305 1306
  }

1307
  if (shouldClearInitializer) {
1308 1309 1310 1311
    // If this schema is not newly-allocated, it may already be in the wild, specifically in the
    // dependency list of other schemas.  Once the initializer is null, it is live, so we must do
    // a release-store here.
    __atomic_store_n(&slot->lazyInitializer, nullptr, __ATOMIC_RELEASE);
1312
    __atomic_store_n(&slot->defaultBrand.lazyInitializer, nullptr, __ATOMIC_RELEASE);
1313
  }
1314 1315 1316 1317

  return slot;
}

1318
_::RawSchema* SchemaLoader::Impl::loadNative(const _::RawSchema* nativeSchema) {
1319 1320
  _::RawSchema*& slot = schemas[nativeSchema->id];
  bool shouldReplace;
1321
  bool shouldClearInitializer;
1322
  if (slot == nullptr) {
1323
    slot = &arena.allocate<_::RawSchema>();
1324
    memset(&slot->defaultBrand, 0, sizeof(slot->defaultBrand));
1325
    slot->defaultBrand.generic = slot;
1326 1327
    slot->lazyInitializer = nullptr;
    slot->defaultBrand.lazyInitializer = nullptr;
1328
    shouldReplace = true;
1329
    shouldClearInitializer = false;  // already cleared above
1330
  } else if (slot->canCastTo != nullptr) {
1331 1332
    // Already loaded natively, or we're currently in the process of loading natively and there
    // was a dependency cycle.
1333
    KJ_REQUIRE(slot->canCastTo == nativeSchema,
1334
        "two different compiled-in type have the same type ID",
1335
        nativeSchema->id,
Kenton Varda's avatar
Kenton Varda committed
1336 1337
        readMessageUnchecked<schema::Node>(nativeSchema->encodedNode).getDisplayName(),
        readMessageUnchecked<schema::Node>(slot->canCastTo->encodedNode).getDisplayName());
1338 1339
    return slot;
  } else {
Kenton Varda's avatar
Kenton Varda committed
1340 1341
    auto existing = readMessageUnchecked<schema::Node>(slot->encodedNode);
    auto native = readMessageUnchecked<schema::Node>(nativeSchema->encodedNode);
1342
    CompatibilityChecker checker(*this);
1343
    shouldReplace = checker.shouldReplace(existing, native, true);
1344
    shouldClearInitializer = slot->lazyInitializer != nullptr;
1345 1346
  }

1347 1348
  // Since we recurse below, the slot in the hash map could move around.  Copy out the pointer
  // for subsequent use.
1349 1350
  // TODO(cleanup): Above comment is actually not true of unordered_map. Leaving here to explain
  //   code pattern below.
1351 1352 1353
  _::RawSchema* result = slot;

  if (shouldReplace) {
1354 1355 1356 1357 1358
    // Set the schema to a copy of the native schema, but make sure not to null out lazyInitializer
    // yet.
    _::RawSchema temp = *nativeSchema;
    temp.lazyInitializer = result->lazyInitializer;
    *result = temp;
1359

1360 1361
    result->defaultBrand.generic = result;

1362 1363 1364 1365
    // Indicate that casting is safe.  Note that it's important to set this before recursively
    // loading dependencies, so that cycles don't cause infinite loops!
    result->canCastTo = nativeSchema;

1366
    // We need to set the dependency list to point at other loader-owned RawSchemas.
1367 1368 1369 1370 1371 1372
    kj::ArrayPtr<const _::RawSchema*> dependencies =
        arena.allocateArray<const _::RawSchema*>(result->dependencyCount);
    for (uint i = 0; i < nativeSchema->dependencyCount; i++) {
      dependencies[i] = loadNative(nativeSchema->dependencies[i]);
    }
    result->dependencies = dependencies.begin();
1373

1374
    // Also need to re-do the branded dependencies.
1375
    auto deps = makeBrandedDependencies(slot, kj::ArrayPtr<const _::RawBrandedSchema::Scope>());
1376 1377 1378
    slot->defaultBrand.dependencies = deps.begin();
    slot->defaultBrand.dependencyCount = deps.size();

1379 1380 1381 1382
    // If there is a struct size requirement, we need to make sure that it is satisfied.
    auto reqIter = structSizeRequirements.find(nativeSchema->id);
    if (reqIter != structSizeRequirements.end()) {
      applyStructSizeRequirement(result, reqIter->second.dataWordCount,
1383
                                 reqIter->second.pointerCount);
1384
    }
1385 1386
  } else {
    // The existing schema is newer.
1387

1388 1389 1390
    // Indicate that casting is safe.  Note that it's important to set this before recursively
    // loading dependencies, so that cycles don't cause infinite loops!
    result->canCastTo = nativeSchema;
1391

1392 1393 1394 1395
    // Make sure the dependencies are loaded and compatible.
    for (uint i = 0; i < nativeSchema->dependencyCount; i++) {
      loadNative(nativeSchema->dependencies[i]);
    }
1396 1397
  }

1398 1399 1400 1401 1402 1403 1404
  if (shouldClearInitializer) {
    // If this schema is not newly-allocated, it may already be in the wild, specifically in the
    // dependency list of other schemas.  Once the initializer is null, it is live, so we must do
    // a release-store here.
    __atomic_store_n(&result->lazyInitializer, nullptr, __ATOMIC_RELEASE);
    __atomic_store_n(&result->defaultBrand.lazyInitializer, nullptr, __ATOMIC_RELEASE);
  }
1405 1406

  return result;
1407 1408
}

1409
_::RawSchema* SchemaLoader::Impl::loadEmpty(
1410
    uint64_t id, kj::StringPtr name, schema::Node::Which kind, bool isPlaceholder) {
1411 1412
  word scratch[32];
  memset(scratch, 0, sizeof(scratch));
1413
  MallocMessageBuilder builder(scratch);
Kenton Varda's avatar
Kenton Varda committed
1414
  auto node = builder.initRoot<schema::Node>();
1415 1416 1417
  node.setId(id);
  node.setDisplayName(name);
  switch (kind) {
Kenton Varda's avatar
Kenton Varda committed
1418
    case schema::Node::STRUCT: node.initStruct(); break;
1419 1420
    case schema::Node::ENUM: node.initEnum(); break;
    case schema::Node::INTERFACE: node.initInterface(); break;
1421

Kenton Varda's avatar
Kenton Varda committed
1422 1423 1424
    case schema::Node::FILE:
    case schema::Node::CONST:
    case schema::Node::ANNOTATION:
1425
      KJ_FAIL_REQUIRE("Not a type.");
1426 1427 1428
      break;
  }

1429
  return load(node, isPlaceholder);
1430 1431
}

1432 1433
const _::RawBrandedSchema* SchemaLoader::Impl::makeBranded(
    const _::RawSchema* schema, schema::Brand::Reader proto,
1434
    kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> clientBrand) {
1435 1436 1437 1438 1439 1440
  kj::StringPtr scopeName =
      readMessageUnchecked<schema::Node>(schema->encodedNode).getDisplayName();

  auto srcScopes = proto.getScopes();

  KJ_STACK_ARRAY(_::RawBrandedSchema::Scope, dstScopes, srcScopes.size(), 16, 32);
1441
  memset(dstScopes.begin(), 0, dstScopes.size() * sizeof(dstScopes[0]));
1442 1443 1444 1445

  uint dstScopeCount = 0;
  for (auto srcScope: srcScopes) {
    switch (srcScope.which()) {
1446
      case schema::Brand::Scope::BIND: {
1447 1448
        auto srcBindings = srcScope.getBind();
        KJ_STACK_ARRAY(_::RawBrandedSchema::Binding, dstBindings, srcBindings.size(), 16, 32);
1449
        memset(dstBindings.begin(), 0, dstBindings.size() * sizeof(dstBindings[0]));
1450 1451 1452 1453 1454 1455 1456 1457 1458

        for (auto j: kj::indices(srcBindings)) {
          auto srcBinding = srcBindings[j];
          auto& dstBinding = dstBindings[j];

          memset(&dstBinding, 0, sizeof(dstBinding));
          dstBinding.which = schema::Type::ANY_POINTER;

          switch (srcBinding.which()) {
1459
            case schema::Brand::Binding::UNBOUND:
1460
              break;
1461
            case schema::Brand::Binding::TYPE: {
Kenton Varda's avatar
Kenton Varda committed
1462
              makeDep(dstBinding, srcBinding.getType(), scopeName, clientBrand);
1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473
              break;
            }
          }
        }

        auto& dstScope = dstScopes[dstScopeCount++];
        dstScope.typeId = srcScope.getScopeId();
        dstScope.bindingCount = dstBindings.size();
        dstScope.bindings = copyDeduped(dstBindings).begin();
        break;
      }
1474
      case schema::Brand::Scope::INHERIT: {
1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487
        // Inherit the whole scope from the client -- or if the client doesn't have it, at least
        // include an empty dstScope in the list just to show that this scope was specified as
        // inherited, as opposed to being unspecified (which would be treated as all AnyPointer).
        auto& dstScope = dstScopes[dstScopeCount++];
        dstScope.typeId = srcScope.getScopeId();

        KJ_IF_MAYBE(b, clientBrand) {
          for (auto& clientScope: *b) {
            if (clientScope.typeId == dstScope.typeId) {
              // Overwrite the whole thing.
              dstScope = clientScope;
              break;
            }
1488
          }
1489 1490
        } else {
          dstScope.isUnbound = true;
1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503
        }
        break;
      }
    }
  }

  dstScopes = dstScopes.slice(0, dstScopeCount);

  std::sort(dstScopes.begin(), dstScopes.end(),
      [](const _::RawBrandedSchema::Scope& a, const _::RawBrandedSchema::Scope& b) {
    return a.typeId < b.typeId;
  });

1504
  return makeBranded(schema, copyDeduped(dstScopes));
1505 1506
}

1507
const _::RawBrandedSchema* SchemaLoader::Impl::makeBranded(
1508
    const _::RawSchema* schema, kj::ArrayPtr<const _::RawBrandedSchema::Scope> bindings) {
1509 1510 1511 1512 1513 1514 1515
  // Note that even if `bindings` is empty, we never want to return defaultBrand here because
  // defaultBrand has special status. Normally, the lack of bindings means all parameters are
  // "unspecified", which means their bindings are unknown and should be treated as AnyPointer.
  // But defaultBrand represents a special case where all parameters are still parameters -- they
  // haven't been bound in the first place. defaultBrand is used to represent the unbranded generic
  // type, while a no-binding brand is equivalent to binding all parameters to AnyPointer.

1516 1517 1518 1519 1520 1521 1522 1523
  if (bindings.size() == 0) {
    return &schema->defaultBrand;
  }

  auto& slot = brands[SchemaBindingsPair { schema, bindings.begin() }];

  if (slot == nullptr) {
    auto& brand = arena.allocate<_::RawBrandedSchema>();
1524
    memset(&brand, 0, sizeof(brand));
1525 1526 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537
    slot = &brand;

    brand.generic = schema;
    brand.scopes = bindings.begin();
    brand.scopeCount = bindings.size();
    brand.lazyInitializer = &brandedInitializer;
  }

  return slot;
}

kj::ArrayPtr<const _::RawBrandedSchema::Dependency>
SchemaLoader::Impl::makeBrandedDependencies(
1538 1539
    const _::RawSchema* schema,
    kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> bindings) {
1540 1541 1542 1543 1544 1545 1546 1547 1548
  kj::StringPtr scopeName =
      readMessageUnchecked<schema::Node>(schema->encodedNode).getDisplayName();

  kj::Vector<_::RawBrandedSchema::Dependency> deps;

  schema::Node::Reader node = readMessageUnchecked<schema::Node>(schema->encodedNode);

#define ADD_ENTRY(kind, index, make) \
    if (const _::RawBrandedSchema* dep = make) { \
1549 1550 1551 1552 1553
      auto& slot = deps.add(); \
      memset(&slot, 0, sizeof(slot)); \
      slot.location = _::RawBrandedSchema::makeDepLocation( \
        _::RawBrandedSchema::DepKind::kind, index); \
      slot.schema = dep; \
1554 1555 1556 1557 1558 1559 1560 1561 1562
    }

  switch (node.which()) {
    case schema::Node::FILE:
    case schema::Node::ENUM:
    case schema::Node::ANNOTATION:
      break;

    case schema::Node::CONST:
Kenton Varda's avatar
Kenton Varda committed
1563 1564
      ADD_ENTRY(CONST_TYPE, 0, makeDepSchema(
          node.getConst().getType(), scopeName, bindings));
1565 1566 1567 1568 1569 1570 1571 1572
      break;

    case schema::Node::STRUCT: {
      auto fields = node.getStruct().getFields();
      for (auto i: kj::indices(fields)) {
        auto field = fields[i];
        switch (field.which()) {
          case schema::Field::SLOT:
Kenton Varda's avatar
Kenton Varda committed
1573 1574
            ADD_ENTRY(FIELD, i, makeDepSchema(
                field.getSlot().getType(), scopeName, bindings))
1575 1576 1577 1578 1579
            break;
          case schema::Field::GROUP: {
            const _::RawSchema* group = loadEmpty(
                field.getGroup().getTypeId(),
                "(unknown group type)", schema::Node::STRUCT, true);
1580 1581 1582 1583 1584
            KJ_IF_MAYBE(b, bindings) {
              ADD_ENTRY(FIELD, i, makeBranded(group, *b));
            } else {
              ADD_ENTRY(FIELD, i, getUnbound(group));
            }
1585 1586 1587 1588 1589 1590 1591 1592 1593 1594
            break;
          }
        }
      }
      break;
    }

    case schema::Node::INTERFACE: {
      auto interface = node.getInterface();
      {
1595
        auto superclasses = interface.getSuperclasses();
1596 1597
        for (auto i: kj::indices(superclasses)) {
          auto superclass = superclasses[i];
Kenton Varda's avatar
Kenton Varda committed
1598
          ADD_ENTRY(SUPERCLASS, i, makeDepSchema(
1599
              superclass.getId(), schema::Type::INTERFACE, schema::Node::INTERFACE,
Kenton Varda's avatar
Kenton Varda committed
1600
              superclass.getBrand(), scopeName, bindings))
1601 1602 1603 1604 1605 1606
        }
      }
      {
        auto methods = interface.getMethods();
        for (auto i: kj::indices(methods)) {
          auto method = methods[i];
Kenton Varda's avatar
Kenton Varda committed
1607
          ADD_ENTRY(METHOD_PARAMS, i, makeDepSchema(
1608
              method.getParamStructType(), schema::Type::STRUCT, schema::Node::STRUCT,
Kenton Varda's avatar
Kenton Varda committed
1609 1610
              method.getParamBrand(), scopeName, bindings))
          ADD_ENTRY(METHOD_RESULTS, i, makeDepSchema(
1611
              method.getResultStructType(), schema::Type::STRUCT, schema::Node::STRUCT,
Kenton Varda's avatar
Kenton Varda committed
1612
              method.getResultBrand(), scopeName, bindings))
1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628
        }
      }
      break;
    }
  }

#undef ADD_ENTRY

  std::sort(deps.begin(), deps.end(),
      [](const _::RawBrandedSchema::Dependency& a, const _::RawBrandedSchema::Dependency& b) {
    return a.location < b.location;
  });

  return copyDeduped(deps.asPtr());
}

Kenton Varda's avatar
Kenton Varda committed
1629
void SchemaLoader::Impl::makeDep(_::RawBrandedSchema::Binding& result,
1630
    schema::Type::Reader type, kj::StringPtr scopeName,
1631
    kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> brandBindings) {
1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646
  switch (type.which()) {
    case schema::Type::VOID:
    case schema::Type::BOOL:
    case schema::Type::INT8:
    case schema::Type::INT16:
    case schema::Type::INT32:
    case schema::Type::INT64:
    case schema::Type::UINT8:
    case schema::Type::UINT16:
    case schema::Type::UINT32:
    case schema::Type::UINT64:
    case schema::Type::FLOAT32:
    case schema::Type::FLOAT64:
    case schema::Type::TEXT:
    case schema::Type::DATA:
Kenton Varda's avatar
Kenton Varda committed
1647 1648
      result.which = static_cast<uint8_t>(type.which());
      return;
1649 1650 1651

    case schema::Type::STRUCT: {
      auto structType = type.getStruct();
Kenton Varda's avatar
Kenton Varda committed
1652 1653 1654
      makeDep(result, structType.getTypeId(), schema::Type::STRUCT, schema::Node::STRUCT,
              structType.getBrand(), scopeName, brandBindings);
      return;
1655 1656 1657
    }
    case schema::Type::ENUM: {
      auto enumType = type.getEnum();
Kenton Varda's avatar
Kenton Varda committed
1658 1659 1660
      makeDep(result, enumType.getTypeId(), schema::Type::ENUM, schema::Node::ENUM,
              enumType.getBrand(), scopeName, brandBindings);
      return;
1661 1662 1663
    }
    case schema::Type::INTERFACE: {
      auto interfaceType = type.getInterface();
Kenton Varda's avatar
Kenton Varda committed
1664 1665 1666
      makeDep(result, interfaceType.getTypeId(), schema::Type::INTERFACE, schema::Node::INTERFACE,
              interfaceType.getBrand(), scopeName, brandBindings);
      return;
1667 1668 1669
    }

    case schema::Type::LIST: {
Kenton Varda's avatar
Kenton Varda committed
1670
      makeDep(result, type.getList().getElementType(), scopeName, brandBindings);
1671
      ++result.listDepth;
Kenton Varda's avatar
Kenton Varda committed
1672
      return;
1673 1674 1675
    }

    case schema::Type::ANY_POINTER: {
Kenton Varda's avatar
Kenton Varda committed
1676
      result.which = static_cast<uint8_t>(schema::Type::ANY_POINTER);
1677 1678 1679
      auto anyPointer = type.getAnyPointer();
      switch (anyPointer.which()) {
        case schema::Type::AnyPointer::UNCONSTRAINED:
Kenton Varda's avatar
Kenton Varda committed
1680
          return;
1681 1682
        case schema::Type::AnyPointer::PARAMETER: {
          auto param = anyPointer.getParameter();
1683
          uint64_t id = param.getScopeId();
1684
          uint16_t index = param.getParameterIndex();
1685 1686 1687 1688 1689 1690 1691

          KJ_IF_MAYBE(b, brandBindings) {
            // TODO(perf): We could binary search here, but... bleh.
            for (auto& scope: *b) {
              if (scope.typeId == id) {
                if (scope.isUnbound) {
                  // Unbound brand parameter.
Kenton Varda's avatar
Kenton Varda committed
1692 1693 1694
                  result.scopeId = id;
                  result.paramIndex = index;
                  return;
1695 1696 1697 1698
                } else if (index >= scope.bindingCount) {
                  // Binding index out-of-range. Treat as AnyPointer. This is important to allow
                  // new type parameters to be added to existing types without breaking dependent
                  // schemas.
Kenton Varda's avatar
Kenton Varda committed
1699
                  return;
1700
                } else {
Kenton Varda's avatar
Kenton Varda committed
1701 1702
                  result = scope.bindings[index];
                  return;
1703
                }
1704 1705
              }
            }
Kenton Varda's avatar
Kenton Varda committed
1706
            return;
1707 1708
          } else {
            // Unbound brand parameter.
Kenton Varda's avatar
Kenton Varda committed
1709 1710 1711
            result.scopeId = id;
            result.paramIndex = index;
            return;
1712 1713
          }
        }
1714
        case schema::Type::AnyPointer::IMPLICIT_METHOD_PARAMETER:
Kenton Varda's avatar
Kenton Varda committed
1715 1716 1717
          result.isImplicitParameter = true;
          result.paramIndex = anyPointer.getImplicitMethodParameter().getParameterIndex();
          return;
1718
      }
1719
      KJ_UNREACHABLE;
1720 1721 1722 1723 1724 1725
    }
  }

  KJ_UNREACHABLE;
}

Kenton Varda's avatar
Kenton Varda committed
1726
void SchemaLoader::Impl::makeDep(_::RawBrandedSchema::Binding& result,
1727
    uint64_t typeId, schema::Type::Which whichType, schema::Node::Which expectedKind,
1728
    schema::Brand::Reader brand, kj::StringPtr scopeName,
1729
    kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> brandBindings) {
1730 1731 1732
  const _::RawSchema* schema = loadEmpty(typeId,
      kj::str("(unknown type; seen as dependency of ", scopeName, ")"),
      expectedKind, true);
Kenton Varda's avatar
Kenton Varda committed
1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753
  result.which = static_cast<uint8_t>(whichType);
  result.schema = makeBranded(schema, brand, brandBindings);
}

const _::RawBrandedSchema* SchemaLoader::Impl::makeDepSchema(
    schema::Type::Reader type, kj::StringPtr scopeName,
    kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> brandBindings) {
  _::RawBrandedSchema::Binding binding;
  memset(&binding, 0, sizeof(binding));
  makeDep(binding, type, scopeName, brandBindings);
  return binding.schema;
}

const _::RawBrandedSchema* SchemaLoader::Impl::makeDepSchema(
    uint64_t typeId, schema::Type::Which whichType, schema::Node::Which expectedKind,
    schema::Brand::Reader brand, kj::StringPtr scopeName,
    kj::Maybe<kj::ArrayPtr<const _::RawBrandedSchema::Scope>> brandBindings) {
  _::RawBrandedSchema::Binding binding;
  memset(&binding, 0, sizeof(binding));
  makeDep(binding, typeId, whichType, expectedKind, brand, scopeName, brandBindings);
  return binding.schema;
1754 1755 1756 1757 1758 1759 1760 1761
}

template <typename T>
kj::ArrayPtr<const T> SchemaLoader::Impl::copyDeduped(kj::ArrayPtr<const T> values) {
  if (values.size() == 0) {
    return kj::arrayPtr(kj::implicitCast<const T*>(nullptr), 0);
  }

1762
  auto bytes = values.asBytes();
1763 1764 1765 1766 1767 1768 1769 1770 1771 1772

  auto iter = dedupTable.find(bytes);
  if (iter != dedupTable.end()) {
    return kj::arrayPtr(reinterpret_cast<const T*>(iter->begin()), values.size());
  }

  // Need to make a new copy.
  auto copy = arena.allocateArray<T>(values.size());
  memcpy(copy.begin(), values.begin(), values.size() * sizeof(T));

1773
  KJ_ASSERT(dedupTable.insert(copy.asBytes()).second);
1774 1775 1776 1777 1778 1779 1780 1781 1782

  return copy;
}

template <typename T>
kj::ArrayPtr<const T> SchemaLoader::Impl::copyDeduped(kj::ArrayPtr<T> values) {
  return copyDeduped(kj::ArrayPtr<const T>(values));
}

1783
SchemaLoader::Impl::TryGetResult SchemaLoader::Impl::tryGet(uint64_t typeId) const {
1784 1785
  auto iter = schemas.find(typeId);
  if (iter == schemas.end()) {
1786
    return {nullptr, initializer.getCallback()};
1787
  } else {
1788
    return {iter->second, initializer.getCallback()};
1789 1790 1791
  }
}

1792 1793 1794 1795 1796 1797 1798 1799 1800
const _::RawBrandedSchema* SchemaLoader::Impl::getUnbound(const _::RawSchema* schema) {
  if (!readMessageUnchecked<schema::Node>(schema->encodedNode).getIsGeneric()) {
    // Not a generic type, so just return the default brand.
    return &schema->defaultBrand;
  }

  auto& slot = unboundBrands[schema];
  if (slot == nullptr) {
    slot = &arena.allocate<_::RawBrandedSchema>();
1801
    memset(slot, 0, sizeof(*slot));
1802 1803 1804 1805 1806 1807 1808 1809 1810
    slot->generic = schema;
    auto deps = makeBrandedDependencies(schema, nullptr);
    slot->dependencies = deps.begin();
    slot->dependencyCount = deps.size();
  }

  return slot;
}

1811
kj::Array<Schema> SchemaLoader::Impl::getAllLoaded() const {
1812 1813 1814 1815 1816 1817
  size_t count = 0;
  for (auto& schema: schemas) {
    if (schema.second->lazyInitializer == nullptr) ++count;
  }

  kj::Array<Schema> result = kj::heapArray<Schema>(count);
1818 1819
  size_t i = 0;
  for (auto& schema: schemas) {
1820 1821 1822
    if (schema.second->lazyInitializer == nullptr) {
      result[i++] = Schema(&schema.second->defaultBrand);
    }
1823 1824 1825 1826
  }
  return result;
}

1827
void SchemaLoader::Impl::requireStructSize(uint64_t id, uint dataWordCount, uint pointerCount) {
1828 1829 1830 1831 1832 1833
  auto& slot = structSizeRequirements[id];
  slot.dataWordCount = kj::max(slot.dataWordCount, dataWordCount);
  slot.pointerCount = kj::max(slot.pointerCount, pointerCount);

  auto iter = schemas.find(id);
  if (iter != schemas.end()) {
1834
    applyStructSizeRequirement(iter->second, dataWordCount, pointerCount);
1835 1836 1837
  }
}

Kenton Varda's avatar
Kenton Varda committed
1838
kj::ArrayPtr<word> SchemaLoader::Impl::makeUncheckedNode(schema::Node::Reader node) {
1839
  size_t size = node.totalSize().wordCount + 1;
1840 1841 1842 1843 1844 1845 1846
  kj::ArrayPtr<word> result = arena.allocateArray<word>(size);
  memset(result.begin(), 0, size * sizeof(word));
  copyToUnchecked(node, result);
  return result;
}

kj::ArrayPtr<word> SchemaLoader::Impl::makeUncheckedNodeEnforcingSizeRequirements(
Kenton Varda's avatar
Kenton Varda committed
1847
    schema::Node::Reader node) {
1848
  if (node.isStruct()) {
1849 1850 1851 1852
    auto iter = structSizeRequirements.find(node.getId());
    if (iter != structSizeRequirements.end()) {
      auto requirement = iter->second;
      auto structNode = node.getStruct();
1853
      if (structNode.getDataWordCount() < requirement.dataWordCount ||
1854
          structNode.getPointerCount() < requirement.pointerCount) {
1855
        return rewriteStructNodeWithSizes(node, requirement.dataWordCount,
1856
                                          requirement.pointerCount);
1857 1858 1859 1860 1861 1862 1863 1864
      }
    }
  }

  return makeUncheckedNode(node);
}

kj::ArrayPtr<word> SchemaLoader::Impl::rewriteStructNodeWithSizes(
1865
    schema::Node::Reader node, uint dataWordCount, uint pointerCount) {
1866 1867 1868
  MallocMessageBuilder builder;
  builder.setRoot(node);

Kenton Varda's avatar
Kenton Varda committed
1869
  auto root = builder.getRoot<schema::Node>();
1870
  auto newStruct = root.getStruct();
1871 1872
  newStruct.setDataWordCount(kj::max(newStruct.getDataWordCount(), dataWordCount));
  newStruct.setPointerCount(kj::max(newStruct.getPointerCount(), pointerCount));
1873 1874 1875 1876 1877

  return makeUncheckedNode(root);
}

void SchemaLoader::Impl::applyStructSizeRequirement(
1878
    _::RawSchema* raw, uint dataWordCount, uint pointerCount) {
Kenton Varda's avatar
Kenton Varda committed
1879
  auto node = readMessageUnchecked<schema::Node>(raw->encodedNode);
1880 1881

  auto structNode = node.getStruct();
1882
  if (structNode.getDataWordCount() < dataWordCount ||
1883
      structNode.getPointerCount() < pointerCount) {
1884
    // Sizes need to be increased.  Must rewrite.
1885
    kj::ArrayPtr<word> words = rewriteStructNodeWithSizes(node, dataWordCount, pointerCount);
1886 1887 1888 1889 1890 1891 1892 1893

    // We don't need to re-validate the node because we know this change could not possibly have
    // invalidated it.  Just remake the unchecked message.
    raw->encodedNode = words.begin();
    raw->encodedSize = words.size();
  }
}

1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904
void SchemaLoader::InitializerImpl::init(const _::RawSchema* schema) const {
  KJ_IF_MAYBE(c, callback) {
    c->load(loader, schema->id);
  }

  if (schema->lazyInitializer != nullptr) {
    // The callback declined to load a schema.  We need to disable the initializer so that it
    // doesn't get invoked again later, as we can no longer modify this schema once it is in use.

    // Lock the loader for read to make sure no one is concurrently loading a replacement for this
    // schema node.
1905
    auto lock = loader.impl.lockShared();
1906 1907 1908 1909 1910 1911 1912 1913

    // Get the mutable version of the schema.
    _::RawSchema* mutableSchema = lock->get()->tryGet(schema->id).schema;
    KJ_ASSERT(mutableSchema == schema,
              "A schema not belonging to this loader used its initializer.");

    // Disable the initializer.
    __atomic_store_n(&mutableSchema->lazyInitializer, nullptr, __ATOMIC_RELEASE);
1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925
    __atomic_store_n(&mutableSchema->defaultBrand.lazyInitializer, nullptr, __ATOMIC_RELEASE);
  }
}

void SchemaLoader::BrandedInitializerImpl::init(const _::RawBrandedSchema* schema) const {
  schema->generic->ensureInitialized();

  auto lock = loader.impl.lockExclusive();

  if (schema->lazyInitializer == nullptr) {
    // Never mind, someone beat us to it.
    return;
1926
  }
1927 1928 1929 1930 1931 1932 1933 1934

  // Get the mutable version.
  auto iter = lock->get()->brands.find(SchemaBindingsPair { schema->generic, schema->scopes });
  KJ_ASSERT(iter != lock->get()->brands.end());

  _::RawBrandedSchema* mutableSchema = iter->second;
  KJ_ASSERT(mutableSchema == schema);

1935
  // Construct its dependency map.
1936 1937 1938 1939 1940 1941 1942
  auto deps = lock->get()->makeBrandedDependencies(mutableSchema->generic,
      kj::arrayPtr(mutableSchema->scopes, mutableSchema->scopeCount));
  mutableSchema->dependencies = deps.begin();
  mutableSchema->dependencyCount = deps.size();

  // It's initialized now, so disable the initializer.
  __atomic_store_n(&mutableSchema->lazyInitializer, nullptr, __ATOMIC_RELEASE);
1943 1944
}

1945 1946
// =======================================================================================

1947 1948 1949
SchemaLoader::SchemaLoader(): impl(kj::heap<Impl>(*this)) {}
SchemaLoader::SchemaLoader(const LazyLoadCallback& callback)
    : impl(kj::heap<Impl>(*this, callback)) {}
1950
SchemaLoader::~SchemaLoader() noexcept(false) {}
1951

1952 1953
Schema SchemaLoader::get(uint64_t id, schema::Brand::Reader brand, Schema scope) const {
  KJ_IF_MAYBE(result, tryGet(id, brand, scope)) {
1954 1955
    return *result;
  } else {
Kenton Varda's avatar
Kenton Varda committed
1956
    KJ_FAIL_REQUIRE("no schema node loaded for id", kj::hex(id));
1957
  }
1958 1959
}

1960 1961
kj::Maybe<Schema> SchemaLoader::tryGet(
    uint64_t id, schema::Brand::Reader brand, Schema scope) const {
1962
  auto getResult = impl.lockShared()->get()->tryGet(id);
1963
  if (getResult.schema == nullptr || getResult.schema->lazyInitializer != nullptr) {
1964 1965
    // This schema couldn't be found or has yet to be lazily loaded. If we have a lazy loader
    // callback, invoke it now to try to get it to load this schema.
1966 1967 1968
    KJ_IF_MAYBE(c, getResult.callback) {
      c->load(*this, id);
    }
1969
    getResult = impl.lockShared()->get()->tryGet(id);
1970 1971
  }
  if (getResult.schema != nullptr && getResult.schema->lazyInitializer == nullptr) {
1972
    if (brand.getScopes().size() > 0) {
1973 1974 1975 1976
      auto brandedSchema = impl.lockExclusive()->get()->makeBranded(
          getResult.schema, brand, kj::arrayPtr(scope.raw->scopes, scope.raw->scopeCount));
      brandedSchema->ensureInitialized();
      return Schema(brandedSchema);
1977 1978 1979
    } else {
      return Schema(&getResult.schema->defaultBrand);
    }
1980
  } else {
1981
    return nullptr;
1982 1983 1984
  }
}

1985 1986 1987 1988 1989
Schema SchemaLoader::getUnbound(uint64_t id) const {
  auto schema = get(id);
  return Schema(impl.lockExclusive()->get()->getUnbound(schema.raw->generic));
}

1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009
Type SchemaLoader::getType(schema::Type::Reader proto, Schema scope) const {
  switch (proto.which()) {
    case schema::Type::VOID:
    case schema::Type::BOOL:
    case schema::Type::INT8:
    case schema::Type::INT16:
    case schema::Type::INT32:
    case schema::Type::INT64:
    case schema::Type::UINT8:
    case schema::Type::UINT16:
    case schema::Type::UINT32:
    case schema::Type::UINT64:
    case schema::Type::FLOAT32:
    case schema::Type::FLOAT64:
    case schema::Type::TEXT:
    case schema::Type::DATA:
      return proto.which();

    case schema::Type::STRUCT: {
      auto structType = proto.getStruct();
2010
      return get(structType.getTypeId(), structType.getBrand(), scope).asStruct();
2011 2012 2013 2014
    }

    case schema::Type::ENUM: {
      auto enumType = proto.getEnum();
2015
      return get(enumType.getTypeId(), enumType.getBrand(), scope).asEnum();
2016 2017 2018 2019
    }

    case schema::Type::INTERFACE: {
      auto interfaceType = proto.getInterface();
2020
      return get(interfaceType.getTypeId(), interfaceType.getBrand(), scope)
2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033
          .asInterface();
    }

    case schema::Type::LIST:
      return ListSchema::of(getType(proto.getList().getElementType(), scope));

    case schema::Type::ANY_POINTER: {
      auto anyPointer = proto.getAnyPointer();
      switch (anyPointer.which()) {
        case schema::Type::AnyPointer::UNCONSTRAINED:
          return schema::Type::ANY_POINTER;
        case schema::Type::AnyPointer::PARAMETER: {
          auto param = anyPointer.getParameter();
2034
          return scope.getBrandBinding(param.getScopeId(), param.getParameterIndex());
2035
        }
2036 2037 2038
        case schema::Type::AnyPointer::IMPLICIT_METHOD_PARAMETER:
          // We don't support binding implicit method params here.
          return schema::Type::ANY_POINTER;
2039 2040 2041 2042 2043 2044 2045 2046 2047
      }

      KJ_UNREACHABLE;
    }
  }

  KJ_UNREACHABLE;
}

Kenton Varda's avatar
Kenton Varda committed
2048
Schema SchemaLoader::load(const schema::Node::Reader& reader) {
2049
  return Schema(&impl.lockExclusive()->get()->load(reader, false)->defaultBrand);
2050 2051
}

Kenton Varda's avatar
Kenton Varda committed
2052
Schema SchemaLoader::loadOnce(const schema::Node::Reader& reader) const {
2053
  auto locked = impl.lockExclusive();
2054 2055 2056 2057
  auto getResult = locked->get()->tryGet(reader.getId());
  if (getResult.schema == nullptr || getResult.schema->lazyInitializer != nullptr) {
    // Doesn't exist yet, or the existing schema is a placeholder and therefore has not yet been
    // seen publicly.  Go ahead and load the incoming reader.
2058
    return Schema(&locked->get()->load(reader, false)->defaultBrand);
2059
  } else {
2060
    return Schema(&getResult.schema->defaultBrand);
2061
  }
2062 2063
}

2064
kj::Array<Schema> SchemaLoader::getAllLoaded() const {
2065
  return impl.lockShared()->get()->getAllLoaded();
2066 2067
}

2068
void SchemaLoader::loadNative(const _::RawSchema* nativeSchema) {
2069
  impl.lockExclusive()->get()->loadNative(nativeSchema);
2070 2071
}

2072
}  // namespace capnp