schema-loader.c++ 53.6 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
// Copyright (c) 2013, Kenton Varda <temporal@gmail.com>
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
//    list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
// ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
// ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

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

36
namespace capnp {
37

38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
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;
};

55 56
class SchemaLoader::Impl {
public:
57 58 59 60
  inline explicit Impl(const SchemaLoader& loader): initializer(loader) {}
  inline Impl(const SchemaLoader& loader, const LazyLoadCallback& callback)
      : initializer(loader, callback) {}

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

63
  _::RawSchema* loadNative(const _::RawSchema* nativeSchema);
64

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

69 70 71 72 73 74
  struct TryGetResult {
    _::RawSchema* schema;
    kj::Maybe<const LazyLoadCallback&> callback;
  };

  TryGetResult tryGet(uint64_t typeId) const;
75
  kj::Array<Schema> getAllLoaded() const;
76

Kenton Varda's avatar
Kenton Varda committed
77
  void requireStructSize(uint64_t id, uint dataWordCount, uint pointerCount,
Kenton Varda's avatar
Kenton Varda committed
78
                         schema::ElementSize preferredListEncoding);
79 80 81 82 83 84
  // 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.

85
  kj::Arena arena;
86 87

private:
88
  std::unordered_map<uint64_t, _::RawSchema*> schemas;
89

90 91 92
  struct RequiredSize {
    uint16_t dataWordCount;
    uint16_t pointerCount;
Kenton Varda's avatar
Kenton Varda committed
93
    schema::ElementSize preferredListEncoding;
94 95 96
  };
  std::unordered_map<uint64_t, RequiredSize> structSizeRequirements;

97
  InitializerImpl initializer;
98

Kenton Varda's avatar
Kenton Varda committed
99
  kj::ArrayPtr<word> makeUncheckedNode(schema::Node::Reader node);
100 101 102
  // 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
103
  kj::ArrayPtr<word> makeUncheckedNodeEnforcingSizeRequirements(schema::Node::Reader node);
104 105 106 107 108 109 110
  // 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(
Kenton Varda's avatar
Kenton Varda committed
111 112
      schema::Node::Reader node, uint dataWordCount, uint pointerCount,
      schema::ElementSize preferredListEncoding);
113 114 115 116 117
  // 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.
Kenton Varda's avatar
Kenton Varda committed
118
  void applyStructSizeRequirement(_::RawSchema* raw, uint dataWordCount, uint pointerCount,
Kenton Varda's avatar
Kenton Varda committed
119
                                  schema::ElementSize preferredListEncoding);
120 121 122 123
};

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

124 125 126 127
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.

128 129 130 131
class SchemaLoader::Validator {
public:
  Validator(SchemaLoader::Impl& loader): loader(loader) {}

Kenton Varda's avatar
Kenton Varda committed
132
  bool validate(const schema::Node::Reader& node) {
133 134 135 136
    isValid = true;
    nodeName = node.getDisplayName();
    dependencies.clear();

137
    KJ_CONTEXT("validating schema node", nodeName, (uint)node.which());
138

139
    switch (node.which()) {
Kenton Varda's avatar
Kenton Varda committed
140
      case schema::Node::FILE:
141
        verifyVoid(node.getFile());
142
        break;
Kenton Varda's avatar
Kenton Varda committed
143
      case schema::Node::STRUCT:
144
        validate(node.getStruct(), node.getScopeId());
145
        break;
Kenton Varda's avatar
Kenton Varda committed
146
      case schema::Node::ENUM:
147
        validate(node.getEnum());
148
        break;
Kenton Varda's avatar
Kenton Varda committed
149
      case schema::Node::INTERFACE:
150
        validate(node.getInterface());
151
        break;
Kenton Varda's avatar
Kenton Varda committed
152
      case schema::Node::CONST:
153
        validate(node.getConst());
154
        break;
Kenton Varda's avatar
Kenton Varda committed
155
      case schema::Node::ANNOTATION:
156
        validate(node.getAnnotation());
157 158 159 160 161 162 163
        break;
    }

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

164
  const _::RawSchema** makeDependencyArray(uint32_t* count) {
165
    *count = dependencies.size();
166 167
    kj::ArrayPtr<const _::RawSchema*> result =
        loader.arena.allocateArray<const _::RawSchema*>(*count);
168 169 170 171
    uint pos = 0;
    for (auto& dep: dependencies) {
      result[pos++] = dep.second;
    }
172
    KJ_DASSERT(pos == *count);
173
    return result.begin();
174 175
  }

176
  const uint16_t* makeMemberInfoArray(uint32_t* count) {
177
    *count = members.size();
178
    kj::ArrayPtr<uint16_t> result = loader.arena.allocateArray<uint16_t>(*count);
179 180
    uint pos = 0;
    for (auto& member: members) {
181
      result[pos++] = member.second;
182
    }
183
    KJ_DASSERT(pos == *count);
184
    return result.begin();
185 186
  }

187 188 189 190
  const uint16_t* makeMembersByDiscriminantArray() {
    return membersByDiscriminant.begin();
  }

191 192 193 194
private:
  SchemaLoader::Impl& loader;
  Text::Reader nodeName;
  bool isValid;
195
  std::map<uint64_t, _::RawSchema*> dependencies;
196

197 198 199 200
  // Maps name -> index for each member.
  std::map<Text::Reader, uint> members;

  kj::ArrayPtr<uint16_t> membersByDiscriminant;
201 202

#define VALIDATE_SCHEMA(condition, ...) \
203
  KJ_REQUIRE(condition, ##__VA_ARGS__) { isValid = false; return; }
204
#define FAIL_VALIDATE_SCHEMA(...) \
205
  KJ_FAIL_REQUIRE(__VA_ARGS__) { isValid = false; return; }
206

207 208 209
  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
210 211
  }

Kenton Varda's avatar
Kenton Varda committed
212
  void validate(const schema::Node::Struct::Reader& structNode, uint64_t scopeId) {
213 214 215 216
    uint dataSizeInBits;
    uint pointerCount;

    switch (structNode.getPreferredListEncoding()) {
Kenton Varda's avatar
Kenton Varda committed
217
      case schema::ElementSize::EMPTY:
218 219 220
        dataSizeInBits = 0;
        pointerCount = 0;
        break;
Kenton Varda's avatar
Kenton Varda committed
221
      case schema::ElementSize::BIT:
222 223 224
        dataSizeInBits = 1;
        pointerCount = 0;
        break;
Kenton Varda's avatar
Kenton Varda committed
225
      case schema::ElementSize::BYTE:
226 227 228
        dataSizeInBits = 8;
        pointerCount = 0;
        break;
Kenton Varda's avatar
Kenton Varda committed
229
      case schema::ElementSize::TWO_BYTES:
230 231 232
        dataSizeInBits = 16;
        pointerCount = 0;
        break;
Kenton Varda's avatar
Kenton Varda committed
233
      case schema::ElementSize::FOUR_BYTES:
234 235 236
        dataSizeInBits = 32;
        pointerCount = 0;
        break;
Kenton Varda's avatar
Kenton Varda committed
237
      case schema::ElementSize::EIGHT_BYTES:
238 239 240
        dataSizeInBits = 64;
        pointerCount = 0;
        break;
Kenton Varda's avatar
Kenton Varda committed
241
      case schema::ElementSize::POINTER:
242 243 244
        dataSizeInBits = 0;
        pointerCount = 1;
        break;
Kenton Varda's avatar
Kenton Varda committed
245
      case schema::ElementSize::INLINE_COMPOSITE:
246 247
        dataSizeInBits = structNode.getDataWordCount() * 64;
        pointerCount = structNode.getPointerCount();
248 249
        break;
      default:
250
        FAIL_VALIDATE_SCHEMA("invalid preferredListEncoding");
251 252 253 254 255
        dataSizeInBits = 0;
        pointerCount = 0;
        break;
    }

256 257
    VALIDATE_SCHEMA(structNode.getDataWordCount() == (dataSizeInBits + 63) / 64 &&
                    structNode.getPointerCount() == pointerCount,
258
                    "struct size does not match preferredListEncoding");
259

260
    auto fields = structNode.getFields();
261

262
    KJ_STACK_ARRAY(bool, sawCodeOrder, fields.size(), 32, 256);
263 264
    memset(sawCodeOrder.begin(), 0, sawCodeOrder.size() * sizeof(sawCodeOrder[0]));

265 266 267 268 269 270 271 272 273 274 275 276
    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");
277 278
    }

279 280 281
    membersByDiscriminant = loader.arena.allocateArray<uint16_t>(fields.size());
    uint discriminantPos = 0;
    uint nonDiscriminantPos = structNode.getDiscriminantCount();
282

283 284 285 286
    uint index = 0;
    uint nextOrdinal = 0;
    for (auto field: fields) {
      KJ_CONTEXT("validating struct field", field.getName());
287

288 289 290 291 292
      validateMemberName(field.getName(), index);
      VALIDATE_SCHEMA(field.getCodeOrder() < sawCodeOrder.size() &&
                      !sawCodeOrder[field.getCodeOrder()],
                      "invalid codeOrder");
      sawCodeOrder[field.getCodeOrder()] = true;
293

294
      auto ordinal = field.getOrdinal();
295
      if (ordinal.isExplicit()) {
296 297 298
        VALIDATE_SCHEMA(ordinal.getExplicit() >= nextOrdinal,
                        "fields were not ordered by ordinal");
        nextOrdinal = ordinal.getExplicit() + 1;
299
      }
Kenton Varda's avatar
Kenton Varda committed
300

301 302 303 304 305 306 307 308 309 310 311 312
      if (field.hasDiscriminantValue()) {
        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
313

314
      switch (field.which()) {
315 316
        case schema::Field::SLOT: {
          auto slot = field.getSlot();
Kenton Varda's avatar
Kenton Varda committed
317

318 319
          uint fieldBits = 0;
          bool fieldIsPointer = false;
320 321 322
          validate(slot.getType(), slot.getDefaultValue(), &fieldBits, &fieldIsPointer);
          VALIDATE_SCHEMA(fieldBits * (slot.getOffset() + 1) <= dataSizeInBits &&
                          fieldIsPointer * (slot.getOffset() + 1) <= pointerCount,
323
                          "field offset out-of-bounds",
324
                          slot.getOffset(), dataSizeInBits, pointerCount);
Kenton Varda's avatar
Kenton Varda committed
325

326
          break;
Kenton Varda's avatar
Kenton Varda committed
327 328
        }

Kenton Varda's avatar
Kenton Varda committed
329
        case schema::Field::GROUP:
330
          // Require that the group is a struct node.
331
          validateTypeId(field.getGroup().getTypeId(), schema::Node::STRUCT);
332
          break;
Kenton Varda's avatar
Kenton Varda committed
333
      }
334 335

      ++index;
336 337
    }

338 339 340 341 342 343
    // 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");
344

345 346
      // 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.
347 348
      loader.requireStructSize(scopeId, structNode.getDataWordCount(),
                               structNode.getPointerCount(),
Kenton Varda's avatar
Kenton Varda committed
349
                               structNode.getPreferredListEncoding());
350 351

      // Require that the parent type is a struct.
Kenton Varda's avatar
Kenton Varda committed
352
      validateTypeId(scopeId, schema::Node::STRUCT);
353 354 355
    }
  }

356 357
  void validate(const schema::Node::Enum::Reader& enumNode) {
    auto enumerants = enumNode.getEnumerants();
358
    KJ_STACK_ARRAY(bool, sawCodeOrder, enumerants.size(), 32, 256);
359 360 361 362
    memset(sawCodeOrder.begin(), 0, sawCodeOrder.size() * sizeof(sawCodeOrder[0]));

    uint index = 0;
    for (auto enumerant: enumerants) {
363
      validateMemberName(enumerant.getName(), index++);
364 365 366 367 368 369 370 371

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

372
  void validate(const schema::Node::Interface::Reader& interfaceNode) {
373 374 375 376
    for (auto extend: interfaceNode.getExtends()) {
      validateTypeId(extend, schema::Node::INTERFACE);
    }

377
    auto methods = interfaceNode.getMethods();
378
    KJ_STACK_ARRAY(bool, sawCodeOrder, methods.size(), 32, 256);
379 380 381 382
    memset(sawCodeOrder.begin(), 0, sawCodeOrder.size() * sizeof(sawCodeOrder[0]));

    uint index = 0;
    for (auto method: methods) {
383
      KJ_CONTEXT("validating method", method.getName());
384
      validateMemberName(method.getName(), index++);
385 386 387 388 389 390

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

391 392
      validateTypeId(method.getParamStructType(), schema::Node::STRUCT);
      validateTypeId(method.getResultStructType(), schema::Node::STRUCT);
393 394 395
    }
  }

Kenton Varda's avatar
Kenton Varda committed
396
  void validate(const schema::Node::Const::Reader& constNode) {
397 398 399 400 401
    uint dummy1;
    bool dummy2;
    validate(constNode.getType(), constNode.getValue(), &dummy1, &dummy2);
  }

Kenton Varda's avatar
Kenton Varda committed
402
  void validate(const schema::Node::Annotation::Reader& annotationNode) {
403 404 405
    validate(annotationNode.getType());
  }

Kenton Varda's avatar
Kenton Varda committed
406
  void validate(const schema::Type::Reader& type, const schema::Value::Reader& value,
407 408 409
                uint* dataSizeInBits, bool* isPointer) {
    validate(type);

Kenton Varda's avatar
Kenton Varda committed
410
    schema::Value::Which expectedValueType = schema::Value::VOID;
411
    bool hadCase = false;
412
    switch (type.which()) {
413
#define HANDLE_TYPE(name, bits, ptr) \
Kenton Varda's avatar
Kenton Varda committed
414 415
      case schema::Type::name: \
        expectedValueType = schema::Value::name; \
416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441
        *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)
      HANDLE_TYPE(OBJECT, 0, true)
#undef HANDLE_TYPE
    }

    if (hadCase) {
442 443
      VALIDATE_SCHEMA(value.which() == expectedValueType, "Value did not match type.",
                      (uint)value.which(), (uint)expectedValueType);
444 445 446
    }
  }

Kenton Varda's avatar
Kenton Varda committed
447
  void validate(const schema::Type::Reader& type) {
448
    switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
449 450 451 452 453 454 455 456 457 458 459 460 461 462 463
      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:
      case schema::Type::OBJECT:
464 465
        break;

Kenton Varda's avatar
Kenton Varda committed
466
      case schema::Type::STRUCT:
467
        validateTypeId(type.getStruct().getTypeId(), schema::Node::STRUCT);
468
        break;
Kenton Varda's avatar
Kenton Varda committed
469
      case schema::Type::ENUM:
470
        validateTypeId(type.getEnum().getTypeId(), schema::Node::ENUM);
471
        break;
Kenton Varda's avatar
Kenton Varda committed
472
      case schema::Type::INTERFACE:
473
        validateTypeId(type.getInterface().getTypeId(), schema::Node::INTERFACE);
474 475
        break;

Kenton Varda's avatar
Kenton Varda committed
476
      case schema::Type::LIST:
477
        validate(type.getList().getElementType());
478 479 480 481 482 483
        break;
    }

    // We intentionally allow unknown types.
  }

Kenton Varda's avatar
Kenton Varda committed
484
  void validateTypeId(uint64_t id, schema::Node::Which expectedKind) {
485
    _::RawSchema* existing = loader.tryGet(id).schema;
486
    if (existing != nullptr) {
Kenton Varda's avatar
Kenton Varda committed
487
      auto node = readMessageUnchecked<schema::Node>(existing->encodedNode);
488
      VALIDATE_SCHEMA(node.which() == expectedKind,
489
          "expected a different kind of node for this ID",
490
          id, (uint)expectedKind, (uint)node.which(), node.getDisplayName());
491 492 493 494 495
      dependencies.insert(std::make_pair(id, existing));
      return;
    }

    dependencies.insert(std::make_pair(id, loader.loadEmpty(
496
        id, kj::str("(unknown type used by ", nodeName , ")"), expectedKind, true)));
497 498 499 500 501 502 503 504 505 506 507 508
  }

#undef VALIDATE_SCHEMA
#undef FAIL_VALIDATE_SCHEMA
};

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

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

Kenton Varda's avatar
Kenton Varda committed
509 510
  bool shouldReplace(const schema::Node::Reader& existingNode,
                     const schema::Node::Reader& replacement,
511
                     bool preferReplacementIfEquivalent) {
512 513 514
    this->existingNode = existingNode;
    this->replacementNode = replacement;

515 516
    KJ_CONTEXT("checking compatibility with previously-loaded node of the same id",
               existingNode.getDisplayName());
517

518
    KJ_DREQUIRE(existingNode.getId() == replacement.getId());
519 520 521 522 523 524

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

    checkCompatibility(existingNode, replacement);

525 526
    // Prefer the newer schema.
    return preferReplacementIfEquivalent ? compatibility != OLDER : compatibility == NEWER;
527 528 529 530 531
  }

private:
  SchemaLoader::Impl& loader;
  Text::Reader nodeName;
532 533
  schema::Node::Reader existingNode;
  schema::Node::Reader replacementNode;
534 535 536 537 538 539 540 541 542 543

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

#define VALIDATE_SCHEMA(condition, ...) \
544
  KJ_REQUIRE(condition, ##__VA_ARGS__) { compatibility = INCOMPATIBLE; return; }
545
#define FAIL_VALIDATE_SCHEMA(...) \
546
  KJ_FAIL_REQUIRE(__VA_ARGS__) { compatibility = INCOMPATIBLE; return; }
547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579

  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
580 581
  void checkCompatibility(const schema::Node::Reader& node,
                          const schema::Node::Reader& replacement) {
582 583 584
    // Returns whether `replacement` is equivalent, older than, newer than, or incompatible with
    // `node`.  If exceptions are enabled, this will throw an exception on INCOMPATIBLE.

585
    VALIDATE_SCHEMA(node.which() == replacement.which(),
586 587 588 589 590 591
                    "kind of declaration changed");

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

592
    switch (node.which()) {
Kenton Varda's avatar
Kenton Varda committed
593
      case schema::Node::FILE:
594
        verifyVoid(node.getFile());
595
        break;
Kenton Varda's avatar
Kenton Varda committed
596
      case schema::Node::STRUCT:
597 598
        checkCompatibility(node.getStruct(), replacement.getStruct(),
                           node.getScopeId(), replacement.getScopeId());
599
        break;
Kenton Varda's avatar
Kenton Varda committed
600
      case schema::Node::ENUM:
601
        checkCompatibility(node.getEnum(), replacement.getEnum());
602
        break;
Kenton Varda's avatar
Kenton Varda committed
603
      case schema::Node::INTERFACE:
604
        checkCompatibility(node.getInterface(), replacement.getInterface());
605
        break;
Kenton Varda's avatar
Kenton Varda committed
606
      case schema::Node::CONST:
607
        checkCompatibility(node.getConst(), replacement.getConst());
608
        break;
Kenton Varda's avatar
Kenton Varda committed
609
      case schema::Node::ANNOTATION:
610
        checkCompatibility(node.getAnnotation(), replacement.getAnnotation());
611 612 613 614
        break;
    }
  }

Kenton Varda's avatar
Kenton Varda committed
615 616
  void checkCompatibility(const schema::Node::Struct::Reader& structNode,
                          const schema::Node::Struct::Reader& replacement,
617
                          uint64_t scopeId, uint64_t replacementScopeId) {
618
    if (replacement.getDataWordCount() > structNode.getDataWordCount()) {
619
      replacementIsNewer();
620
    } else if (replacement.getDataWordCount() < structNode.getDataWordCount()) {
621 622
      replacementIsOlder();
    }
623
    if (replacement.getPointerCount() > structNode.getPointerCount()) {
624
      replacementIsNewer();
625
    } else if (replacement.getPointerCount() < structNode.getPointerCount()) {
626 627 628 629 630 631 632 633 634 635 636 637 638
      replacementIsOlder();
    }

    // We can do a simple comparison of preferredListEncoding here because the only case where it
    // isn't correct to compare this way is when one side is BIT/BYTE/*_BYTES while the other side
    // is POINTER, and if that were the case then the above comparisons would already have failed
    // or one of the nodes would have failed validation.
    if (replacement.getPreferredListEncoding() > structNode.getPreferredListEncoding()) {
      replacementIsNewer();
    } else if (replacement.getPreferredListEncoding() < structNode.getPreferredListEncoding()) {
      replacementIsOlder();
    }

639 640 641 642 643 644 645 646 647 648 649
    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");
    }

650 651
    // The shared members should occupy corresponding positions in the member lists, since the
    // lists are sorted by ordinal.
652 653 654
    auto fields = structNode.getFields();
    auto replacementFields = replacement.getFields();
    uint count = std::min(fields.size(), replacementFields.size());
655

656
    if (replacementFields.size() > fields.size()) {
657
      replacementIsNewer();
658
    } else if (replacementFields.size() < fields.size()) {
659 660 661 662
      replacementIsOlder();
    }

    for (uint i = 0; i < count; i++) {
663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681
      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();
      }
682 683 684
    }
  }

Kenton Varda's avatar
Kenton Varda committed
685 686
  void checkCompatibility(const schema::Field::Reader& field,
                          const schema::Field::Reader& replacement) {
687
    KJ_CONTEXT("comparing struct field", field.getName());
688

689 690 691 692 693 694
    // A field that is initially not in a union can be upgraded to be in one, as long as it has
    // discriminant 0.
    uint discriminant = field.hasDiscriminantValue() ? field.getDiscriminantValue() : 0;
    uint replacementDiscriminant =
        replacement.hasDiscriminantValue() ? replacement.getDiscriminantValue() : 0;
    VALIDATE_SCHEMA(discriminant == replacementDiscriminant, "Field discriminant changed.");
695

696
    switch (field.which()) {
697 698
      case schema::Field::SLOT: {
        auto slot = field.getSlot();
699

700
        switch (replacement.which()) {
701 702
          case schema::Field::SLOT: {
            auto replacementSlot = replacement.getSlot();
703

704
            checkCompatibility(slot.getType(), replacementSlot.getType(),
705
                               NO_UPGRADE_TO_STRUCT);
706 707
            checkDefaultCompatibility(slot.getDefaultValue(),
                                      replacementSlot.getDefaultValue());
708

709
            VALIDATE_SCHEMA(slot.getOffset() == replacementSlot.getOffset(),
710 711 712 713
                            "field position changed");
            break;
          }
          case schema::Field::GROUP:
714
            checkUpgradeToStruct(slot.getType(), replacement.getGroup().getTypeId(),
715
                                 existingNode, field);
716 717
            break;
        }
718 719 720

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

Kenton Varda's avatar
Kenton Varda committed
722
      case schema::Field::GROUP:
723
        switch (replacement.which()) {
724 725
          case schema::Field::SLOT:
            checkUpgradeToStruct(replacement.getSlot().getType(), field.getGroup().getTypeId(),
726 727 728
                                 replacementNode, replacement);
            break;
          case schema::Field::GROUP:
729 730
            VALIDATE_SCHEMA(field.getGroup().getTypeId() == replacement.getGroup().getTypeId(),
                            "group id changed");
731 732
            break;
        }
733 734 735 736
        break;
    }
  }

737 738 739 740
  void checkCompatibility(const schema::Node::Enum::Reader& enumNode,
                          const schema::Node::Enum::Reader& replacement) {
    uint size = enumNode.getEnumerants().size();
    uint replacementSize = replacement.getEnumerants().size();
741 742 743 744 745 746 747
    if (replacementSize > size) {
      replacementIsNewer();
    } else if (replacementSize < size) {
      replacementIsOlder();
    }
  }

748 749
  void checkCompatibility(const schema::Node::Interface::Reader& interfaceNode,
                          const schema::Node::Interface::Reader& replacement) {
750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786
    {
      // Check superclasses.

      kj::Vector<uint64_t> extends;
      kj::Vector<uint64_t> replacementExtends;
      for (uint64_t extend: interfaceNode.getExtends()) {
        extends.add(extend);
      }
      for (uint64_t extend: replacement.getExtends()) {
        replacementExtends.add(extend);
      }
      std::sort(extends.begin(), extends.end());
      std::sort(replacementExtends.begin(), replacementExtends.end());

      auto iter = extends.begin();
      auto replacementIter = replacementExtends.begin();

      while (iter != extends.end() || replacementIter != replacementExtends.end()) {
        if (iter == extends.end()) {
          replacementIsNewer();
          break;
        } else if (replacementIter == replacementExtends.end()) {
          replacementIsOlder();
          break;
        } else if (*iter < *replacementIter) {
          replacementIsOlder();
          ++iter;
        } else if (*iter > *replacementIter) {
          replacementIsNewer();
          ++replacementIter;
        } else {
          ++iter;
          ++replacementIter;
        }
      }
    }

787 788 789
    auto methods = interfaceNode.getMethods();
    auto replacementMethods = replacement.getMethods();

790 791 792 793 794 795 796 797 798 799 800 801 802
    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
803 804
  void checkCompatibility(const schema::Method::Reader& method,
                          const schema::Method::Reader& replacement) {
805
    KJ_CONTEXT("comparing method", method.getName());
806

807 808 809 810 811
    // 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.");
812 813
  }

Kenton Varda's avatar
Kenton Varda committed
814 815
  void checkCompatibility(const schema::Node::Const::Reader& constNode,
                          const schema::Node::Const::Reader& replacement) {
816 817 818
    // Who cares?  These don't appear on the wire.
  }

Kenton Varda's avatar
Kenton Varda committed
819 820
  void checkCompatibility(const schema::Node::Annotation::Reader& annotationNode,
                          const schema::Node::Annotation::Reader& replacement) {
821 822 823 824 825 826 827 828
    // 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
829 830
  void checkCompatibility(const schema::Type::Reader& type,
                          const schema::Type::Reader& replacement,
831
                          UpgradeToStructMode upgradeToStructMode) {
832
    if (replacement.which() != type.which()) {
833
      // Check for allowed "upgrade" to Data or Object.
834
      if (replacement.isData() && canUpgradeToData(type)) {
835 836
        replacementIsNewer();
        return;
837
      } else if (type.isData() && canUpgradeToData(replacement)) {
838 839
        replacementIsOlder();
        return;
840
      } else if (replacement.isObject() && canUpgradeToObject(type)) {
841 842
        replacementIsNewer();
        return;
843
      } else if (type.isObject() && canUpgradeToObject(replacement)) {
844 845 846 847 848
        replacementIsOlder();
        return;
      }

      if (upgradeToStructMode == ALLOW_UPGRADE_TO_STRUCT) {
849
        if (type.isStruct()) {
850
          checkUpgradeToStruct(replacement, type.getStruct().getTypeId());
851
          return;
852
        } else if (replacement.isStruct()) {
853
          checkUpgradeToStruct(type, replacement.getStruct().getTypeId());
854 855 856 857 858 859 860
          return;
        }
      }

      FAIL_VALIDATE_SCHEMA("a type was changed");
    }

861
    switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
862 863 864 865 866 867 868 869 870 871 872 873 874 875 876
      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:
      case schema::Type::OBJECT:
877 878
        return;

Kenton Varda's avatar
Kenton Varda committed
879
      case schema::Type::LIST:
880 881
        checkCompatibility(type.getList().getElementType(), replacement.getList().getElementType(),
                           ALLOW_UPGRADE_TO_STRUCT);
882
        return;
883

Kenton Varda's avatar
Kenton Varda committed
884
      case schema::Type::ENUM:
885 886
        VALIDATE_SCHEMA(replacement.getEnum().getTypeId() == type.getEnum().getTypeId(),
                        "type changed enum type");
887 888
        return;

Kenton Varda's avatar
Kenton Varda committed
889
      case schema::Type::STRUCT:
890 891 892 893 894 895 896
        // 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...
897
        VALIDATE_SCHEMA(replacement.getStruct().getTypeId() == type.getStruct().getTypeId(),
898 899 900
                        "type changed to incompatible struct type");
        return;

Kenton Varda's avatar
Kenton Varda committed
901
      case schema::Type::INTERFACE:
902
        VALIDATE_SCHEMA(replacement.getInterface().getTypeId() == type.getInterface().getTypeId(),
903
                        "type changed to incompatible interface type");
904 905 906 907 908 909
        return;
    }

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

910 911 912
  void checkUpgradeToStruct(const schema::Type::Reader& type, uint64_t structTypeId,
                            kj::Maybe<schema::Node::Reader> matchSize = nullptr,
                            kj::Maybe<schema::Field::Reader> matchPosition = nullptr) {
913 914 915 916 917 918 919
    // 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));
920
    MallocMessageBuilder builder(scratch);
Kenton Varda's avatar
Kenton Varda committed
921
    auto node = builder.initRoot<schema::Node>();
922
    node.setId(structTypeId);
923
    node.setDisplayName(kj::str("(unknown type used in ", nodeName, ")"));
924
    auto structNode = node.initStruct();
925

926
    switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
927
      case schema::Type::VOID:
928 929
        structNode.setDataWordCount(0);
        structNode.setPointerCount(0);
Kenton Varda's avatar
Kenton Varda committed
930
        structNode.setPreferredListEncoding(schema::ElementSize::EMPTY);
931 932
        break;

Kenton Varda's avatar
Kenton Varda committed
933
      case schema::Type::BOOL:
934 935
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
Kenton Varda's avatar
Kenton Varda committed
936
        structNode.setPreferredListEncoding(schema::ElementSize::BIT);
937 938
        break;

Kenton Varda's avatar
Kenton Varda committed
939 940
      case schema::Type::INT8:
      case schema::Type::UINT8:
941 942
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
Kenton Varda's avatar
Kenton Varda committed
943
        structNode.setPreferredListEncoding(schema::ElementSize::BYTE);
944 945
        break;

Kenton Varda's avatar
Kenton Varda committed
946 947 948
      case schema::Type::INT16:
      case schema::Type::UINT16:
      case schema::Type::ENUM:
949 950
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
Kenton Varda's avatar
Kenton Varda committed
951
        structNode.setPreferredListEncoding(schema::ElementSize::TWO_BYTES);
952 953
        break;

Kenton Varda's avatar
Kenton Varda committed
954 955 956
      case schema::Type::INT32:
      case schema::Type::UINT32:
      case schema::Type::FLOAT32:
957 958
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
Kenton Varda's avatar
Kenton Varda committed
959
        structNode.setPreferredListEncoding(schema::ElementSize::FOUR_BYTES);
960 961
        break;

Kenton Varda's avatar
Kenton Varda committed
962 963 964
      case schema::Type::INT64:
      case schema::Type::UINT64:
      case schema::Type::FLOAT64:
965 966
        structNode.setDataWordCount(1);
        structNode.setPointerCount(0);
Kenton Varda's avatar
Kenton Varda committed
967
        structNode.setPreferredListEncoding(schema::ElementSize::EIGHT_BYTES);
968 969
        break;

Kenton Varda's avatar
Kenton Varda committed
970 971 972 973 974 975
      case schema::Type::TEXT:
      case schema::Type::DATA:
      case schema::Type::LIST:
      case schema::Type::STRUCT:
      case schema::Type::INTERFACE:
      case schema::Type::OBJECT:
976 977
        structNode.setDataWordCount(0);
        structNode.setPointerCount(1);
Kenton Varda's avatar
Kenton Varda committed
978
        structNode.setPreferredListEncoding(schema::ElementSize::POINTER);
979 980 981
        break;
    }

982 983 984 985 986 987 988
    KJ_IF_MAYBE(s, matchSize) {
      auto match = s->getStruct();
      structNode.setDataWordCount(match.getDataWordCount());
      structNode.setPointerCount(match.getPointerCount());
      structNode.setPreferredListEncoding(match.getPreferredListEncoding());
    }

989 990 991
    auto field = structNode.initFields(1)[0];
    field.setName("member0");
    field.setCodeOrder(0);
992 993
    auto slot = field.initSlot();
    slot.setType(type);
994 995 996 997 998 999 1000

    KJ_IF_MAYBE(p, matchPosition) {
      if (p->getOrdinal().isExplicit()) {
        field.getOrdinal().setExplicit(p->getOrdinal().getExplicit());
      } else {
        field.getOrdinal().setImplicit();
      }
1001 1002 1003
      auto matchSlot = p->getSlot();
      slot.setOffset(matchSlot.getOffset());
      slot.setDefaultValue(matchSlot.getDefaultValue());
1004 1005
    } else {
      field.getOrdinal().setExplicit(0);
1006
      slot.setOffset(0);
1007

1008
      schema::Value::Builder value = slot.initDefaultValue();
1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024
      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;
1025 1026
        case schema::Type::LIST: value.initList(); break;
        case schema::Type::STRUCT: value.initStruct(); break;
1027
        case schema::Type::INTERFACE: value.setInterface(); break;
1028
        case schema::Type::OBJECT: value.initObject(); break;
1029 1030
      }
    }
1031

1032
    loader.load(node, true);
1033 1034
  }

Kenton Varda's avatar
Kenton Varda committed
1035
  bool canUpgradeToData(const schema::Type::Reader& type) {
1036
    if (type.isText()) {
1037
      return true;
1038
    } else if (type.isList()) {
1039
      switch (type.getList().getElementType().which()) {
Kenton Varda's avatar
Kenton Varda committed
1040 1041
        case schema::Type::INT8:
        case schema::Type::UINT8:
1042 1043 1044 1045 1046 1047 1048 1049 1050
          return true;
        default:
          return false;
      }
    } else {
      return false;
    }
  }

Kenton Varda's avatar
Kenton Varda committed
1051
  bool canUpgradeToObject(const schema::Type::Reader& type) {
1052
    switch (type.which()) {
Kenton Varda's avatar
Kenton Varda committed
1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065
      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:
1066 1067
        return false;

Kenton Varda's avatar
Kenton Varda committed
1068 1069 1070 1071 1072 1073
      case schema::Type::TEXT:
      case schema::Type::DATA:
      case schema::Type::LIST:
      case schema::Type::STRUCT:
      case schema::Type::INTERFACE:
      case schema::Type::OBJECT:
1074 1075 1076 1077 1078 1079 1080
        return true;
    }

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

Kenton Varda's avatar
Kenton Varda committed
1081 1082
  void checkDefaultCompatibility(const schema::Value::Reader& value,
                                 const schema::Value::Reader& replacement) {
1083 1084
    // 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.
1085
    KJ_ASSERT(value.which() == replacement.which()) {
1086 1087 1088 1089
      compatibility = INCOMPATIBLE;
      return;
    }

1090
    switch (value.which()) {
1091
#define HANDLE_TYPE(discrim, name) \
Kenton Varda's avatar
Kenton Varda committed
1092
      case schema::Value::discrim: \
1093
        VALIDATE_SCHEMA(value.get##name() == replacement.get##name(), "default value changed"); \
1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109
        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
1110 1111 1112 1113 1114 1115
      case schema::Value::TEXT:
      case schema::Value::DATA:
      case schema::Value::LIST:
      case schema::Value::STRUCT:
      case schema::Value::INTERFACE:
      case schema::Value::OBJECT:
1116 1117 1118 1119 1120 1121 1122 1123 1124
        // 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
1125
_::RawSchema* SchemaLoader::Impl::load(const schema::Node::Reader& reader, bool isPlaceholder) {
1126
  // Make a copy of the node which can be used unchecked.
1127
  kj::ArrayPtr<word> validated = makeUncheckedNodeEnforcingSizeRequirements(reader);
1128 1129 1130

  // Validate the copy.
  Validator validator(*this);
Kenton Varda's avatar
Kenton Varda committed
1131
  auto validatedReader = readMessageUnchecked<schema::Node>(validated.begin());
1132 1133 1134 1135 1136

  if (!validator.validate(validatedReader)) {
    // Not valid.  Construct an empty schema of the same type and return that.
    return loadEmpty(validatedReader.getId(),
                     validatedReader.getDisplayName(),
1137 1138
                     validatedReader.which(),
                     false);
1139 1140 1141
  }

  // Check if we already have a schema for this ID.
1142
  _::RawSchema*& slot = schemas[validatedReader.getId()];
1143
  bool shouldReplace;
1144 1145
  if (slot == nullptr) {
    // Nope, allocate a new RawSchema.
1146
    slot = &arena.allocate<_::RawSchema>();
1147 1148 1149
    slot->id = validatedReader.getId();
    slot->canCastTo = nullptr;
    shouldReplace = true;
1150 1151
  } else {
    // Yes, check if it is compatible and figure out which schema is newer.
1152 1153 1154 1155 1156 1157 1158

    if (slot->lazyInitializer == nullptr) {
      // The existing slot is not a placeholder, so whether we overwrite it or not, we cannot
      // end up with a placeholder.
      isPlaceholder = false;
    }

Kenton Varda's avatar
Kenton Varda committed
1159
    auto existing = readMessageUnchecked<schema::Node>(slot->encodedNode);
1160
    CompatibilityChecker checker(*this);
1161 1162 1163 1164 1165

    // 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);
1166 1167
  }

1168 1169 1170
  if (shouldReplace) {
    // Initialize the RawSchema.
    slot->encodedNode = validated.begin();
Kenton Varda's avatar
Kenton Varda committed
1171
    slot->encodedSize = validated.size();
1172 1173
    slot->dependencies = validator.makeDependencyArray(&slot->dependencyCount);
    slot->membersByName = validator.makeMemberInfoArray(&slot->memberCount);
1174
    slot->membersByDiscriminant = validator.makeMembersByDiscriminantArray();
1175 1176 1177 1178 1179 1180 1181 1182 1183 1184
  }

  if (isPlaceholder) {
    slot->lazyInitializer = &initializer;
  } else {
    // 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);
  }
1185 1186 1187 1188

  return slot;
}

1189
_::RawSchema* SchemaLoader::Impl::loadNative(const _::RawSchema* nativeSchema) {
1190 1191
  _::RawSchema*& slot = schemas[nativeSchema->id];
  bool shouldReplace;
1192
  if (slot == nullptr) {
1193
    slot = &arena.allocate<_::RawSchema>();
1194
    shouldReplace = true;
1195
  } else if (slot->canCastTo != nullptr) {
1196 1197
    // Already loaded natively, or we're currently in the process of loading natively and there
    // was a dependency cycle.
1198
    KJ_REQUIRE(slot->canCastTo == nativeSchema,
1199
        "two different compiled-in type have the same type ID",
1200
        nativeSchema->id,
Kenton Varda's avatar
Kenton Varda committed
1201 1202
        readMessageUnchecked<schema::Node>(nativeSchema->encodedNode).getDisplayName(),
        readMessageUnchecked<schema::Node>(slot->canCastTo->encodedNode).getDisplayName());
1203 1204
    return slot;
  } else {
Kenton Varda's avatar
Kenton Varda committed
1205 1206
    auto existing = readMessageUnchecked<schema::Node>(slot->encodedNode);
    auto native = readMessageUnchecked<schema::Node>(nativeSchema->encodedNode);
1207
    CompatibilityChecker checker(*this);
1208
    shouldReplace = checker.shouldReplace(existing, native, true);
1209 1210
  }

1211 1212 1213 1214 1215
  // Since we recurse below, the slot in the hash map could move around.  Copy out the pointer
  // for subsequent use.
  _::RawSchema* result = slot;

  if (shouldReplace) {
1216 1217 1218 1219 1220
    // 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;
1221 1222 1223 1224 1225

    // 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;

1226
    // We need to set the dependency list to point at other loader-owned RawSchemas.
1227 1228 1229 1230 1231 1232
    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();
1233 1234 1235 1236 1237

    // 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,
Kenton Varda's avatar
Kenton Varda committed
1238 1239
                                 reqIter->second.pointerCount,
                                 reqIter->second.preferredListEncoding);
1240
    }
1241 1242
  } else {
    // The existing schema is newer.
1243

1244 1245 1246
    // 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;
1247

1248 1249 1250 1251
    // Make sure the dependencies are loaded and compatible.
    for (uint i = 0; i < nativeSchema->dependencyCount; i++) {
      loadNative(nativeSchema->dependencies[i]);
    }
1252 1253
  }

1254 1255 1256 1257 1258 1259
  // 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);

  return result;
1260 1261
}

1262
_::RawSchema* SchemaLoader::Impl::loadEmpty(
1263
    uint64_t id, kj::StringPtr name, schema::Node::Which kind, bool isPlaceholder) {
1264 1265
  word scratch[32];
  memset(scratch, 0, sizeof(scratch));
1266
  MallocMessageBuilder builder(scratch);
Kenton Varda's avatar
Kenton Varda committed
1267
  auto node = builder.initRoot<schema::Node>();
1268 1269 1270
  node.setId(id);
  node.setDisplayName(name);
  switch (kind) {
Kenton Varda's avatar
Kenton Varda committed
1271
    case schema::Node::STRUCT: node.initStruct(); break;
1272 1273
    case schema::Node::ENUM: node.initEnum(); break;
    case schema::Node::INTERFACE: node.initInterface(); break;
1274

Kenton Varda's avatar
Kenton Varda committed
1275 1276 1277
    case schema::Node::FILE:
    case schema::Node::CONST:
    case schema::Node::ANNOTATION:
1278
      KJ_FAIL_REQUIRE("Not a type.");
1279 1280 1281
      break;
  }

1282
  return load(node, isPlaceholder);
1283 1284
}

1285
SchemaLoader::Impl::TryGetResult SchemaLoader::Impl::tryGet(uint64_t typeId) const {
1286 1287
  auto iter = schemas.find(typeId);
  if (iter == schemas.end()) {
1288
    return {nullptr, initializer.getCallback()};
1289
  } else {
1290
    return {iter->second, initializer.getCallback()};
1291 1292 1293
  }
}

1294
kj::Array<Schema> SchemaLoader::Impl::getAllLoaded() const {
1295 1296 1297 1298 1299 1300
  size_t count = 0;
  for (auto& schema: schemas) {
    if (schema.second->lazyInitializer == nullptr) ++count;
  }

  kj::Array<Schema> result = kj::heapArray<Schema>(count);
1301 1302
  size_t i = 0;
  for (auto& schema: schemas) {
1303
    if (schema.second->lazyInitializer == nullptr) result[i++] = Schema(schema.second);
1304 1305 1306 1307
  }
  return result;
}

Kenton Varda's avatar
Kenton Varda committed
1308
void SchemaLoader::Impl::requireStructSize(uint64_t id, uint dataWordCount, uint pointerCount,
Kenton Varda's avatar
Kenton Varda committed
1309
                                           schema::ElementSize preferredListEncoding) {
1310 1311 1312 1313
  auto& slot = structSizeRequirements[id];
  slot.dataWordCount = kj::max(slot.dataWordCount, dataWordCount);
  slot.pointerCount = kj::max(slot.pointerCount, pointerCount);

Kenton Varda's avatar
Kenton Varda committed
1314
  if (slot.dataWordCount + slot.pointerCount >= 2) {
Kenton Varda's avatar
Kenton Varda committed
1315
    slot.preferredListEncoding = schema::ElementSize::INLINE_COMPOSITE;
Kenton Varda's avatar
Kenton Varda committed
1316 1317 1318 1319
  } else {
    slot.preferredListEncoding = kj::max(slot.preferredListEncoding, preferredListEncoding);
  }

1320 1321
  auto iter = schemas.find(id);
  if (iter != schemas.end()) {
Kenton Varda's avatar
Kenton Varda committed
1322
    applyStructSizeRequirement(iter->second, dataWordCount, pointerCount, preferredListEncoding);
1323 1324 1325
  }
}

Kenton Varda's avatar
Kenton Varda committed
1326
kj::ArrayPtr<word> SchemaLoader::Impl::makeUncheckedNode(schema::Node::Reader node) {
1327 1328 1329 1330 1331 1332 1333 1334
  size_t size = node.totalSizeInWords() + 1;
  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
1335
    schema::Node::Reader node) {
1336
  if (node.isStruct()) {
1337 1338 1339 1340
    auto iter = structSizeRequirements.find(node.getId());
    if (iter != structSizeRequirements.end()) {
      auto requirement = iter->second;
      auto structNode = node.getStruct();
1341 1342
      if (structNode.getDataWordCount() < requirement.dataWordCount ||
          structNode.getPointerCount() < requirement.pointerCount ||
Kenton Varda's avatar
Kenton Varda committed
1343
          structNode.getPreferredListEncoding() < requirement.preferredListEncoding) {
1344
        return rewriteStructNodeWithSizes(node, requirement.dataWordCount,
Kenton Varda's avatar
Kenton Varda committed
1345 1346
                                          requirement.pointerCount,
                                          requirement.preferredListEncoding);
1347 1348 1349 1350 1351 1352 1353 1354
      }
    }
  }

  return makeUncheckedNode(node);
}

kj::ArrayPtr<word> SchemaLoader::Impl::rewriteStructNodeWithSizes(
Kenton Varda's avatar
Kenton Varda committed
1355 1356
    schema::Node::Reader node, uint dataWordCount, uint pointerCount,
    schema::ElementSize preferredListEncoding) {
1357 1358 1359
  MallocMessageBuilder builder;
  builder.setRoot(node);

Kenton Varda's avatar
Kenton Varda committed
1360
  auto root = builder.getRoot<schema::Node>();
1361
  auto newStruct = root.getStruct();
1362 1363
  newStruct.setDataWordCount(kj::max(newStruct.getDataWordCount(), dataWordCount));
  newStruct.setPointerCount(kj::max(newStruct.getPointerCount(), pointerCount));
1364

1365
  if (newStruct.getDataWordCount() + newStruct.getPointerCount() >= 2) {
Kenton Varda's avatar
Kenton Varda committed
1366
    newStruct.setPreferredListEncoding(schema::ElementSize::INLINE_COMPOSITE);
Kenton Varda's avatar
Kenton Varda committed
1367 1368 1369 1370 1371
  } else {
    newStruct.setPreferredListEncoding(
        kj::max(newStruct.getPreferredListEncoding(), preferredListEncoding));
  }

1372 1373 1374 1375
  return makeUncheckedNode(root);
}

void SchemaLoader::Impl::applyStructSizeRequirement(
Kenton Varda's avatar
Kenton Varda committed
1376
    _::RawSchema* raw, uint dataWordCount, uint pointerCount,
Kenton Varda's avatar
Kenton Varda committed
1377 1378
    schema::ElementSize preferredListEncoding) {
  auto node = readMessageUnchecked<schema::Node>(raw->encodedNode);
1379 1380

  auto structNode = node.getStruct();
1381 1382
  if (structNode.getDataWordCount() < dataWordCount ||
      structNode.getPointerCount() < pointerCount ||
Kenton Varda's avatar
Kenton Varda committed
1383
      structNode.getPreferredListEncoding() < preferredListEncoding) {
1384
    // Sizes need to be increased.  Must rewrite.
Kenton Varda's avatar
Kenton Varda committed
1385 1386
    kj::ArrayPtr<word> words = rewriteStructNodeWithSizes(
        node, dataWordCount, pointerCount, preferredListEncoding);
1387 1388 1389 1390 1391 1392 1393 1394

    // 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();
  }
}

1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 1405
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.
1406
    auto lock = loader.impl.lockShared();
1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417

    // 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);
  }
}

1418 1419
// =======================================================================================

1420 1421 1422
SchemaLoader::SchemaLoader(): impl(kj::heap<Impl>(*this)) {}
SchemaLoader::SchemaLoader(const LazyLoadCallback& callback)
    : impl(kj::heap<Impl>(*this, callback)) {}
1423
SchemaLoader::~SchemaLoader() noexcept(false) {}
1424 1425

Schema SchemaLoader::get(uint64_t id) const {
1426 1427 1428 1429 1430
  KJ_IF_MAYBE(result, tryGet(id)) {
    return *result;
  } else {
    KJ_FAIL_REQUIRE("no schema node loaded for id", id);
  }
1431 1432
}

1433
kj::Maybe<Schema> SchemaLoader::tryGet(uint64_t id) const {
1434
  auto getResult = impl.lockShared()->get()->tryGet(id);
1435 1436 1437 1438
  if (getResult.schema == nullptr || getResult.schema->lazyInitializer != nullptr) {
    KJ_IF_MAYBE(c, getResult.callback) {
      c->load(*this, id);
    }
1439
    getResult = impl.lockShared()->get()->tryGet(id);
1440 1441 1442
  }
  if (getResult.schema != nullptr && getResult.schema->lazyInitializer == nullptr) {
    return Schema(getResult.schema);
1443
  } else {
1444
    return nullptr;
1445 1446 1447
  }
}

Kenton Varda's avatar
Kenton Varda committed
1448
Schema SchemaLoader::load(const schema::Node::Reader& reader) {
1449
  return Schema(impl.lockExclusive()->get()->load(reader, false));
1450 1451
}

Kenton Varda's avatar
Kenton Varda committed
1452
Schema SchemaLoader::loadOnce(const schema::Node::Reader& reader) const {
1453
  auto locked = impl.lockExclusive();
1454 1455 1456 1457 1458 1459 1460 1461
  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.
    return Schema(locked->get()->load(reader, false));
  } else {
    return Schema(getResult.schema);
  }
1462 1463
}

1464
kj::Array<Schema> SchemaLoader::getAllLoaded() const {
1465
  return impl.lockShared()->get()->getAllLoaded();
1466 1467
}

1468
void SchemaLoader::loadNative(const _::RawSchema* nativeSchema) {
1469
  impl.lockExclusive()->get()->loadNative(nativeSchema);
1470 1471
}

1472
}  // namespace capnp