evolution-test.c++ 29.4 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 22 23 24 25 26 27 28 29 30 31 32 33 34 35 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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167

// This is a fuzz test which randomly generates a schema for a struct one change at a time.
// Each modification is known a priori to be compatible or incompatible.  The type is compiled
// before and after the change and both versions are loaded into a SchemaLoader with the
// expectation that this will succeed if they are compatible and fail if they are not.  If
// the types are expected to be compatible, the test also constructs an instance of the old
// type and reads it as the new type, and vice versa.

#include <capnp/compiler/grammar.capnp.h>
#include <capnp/schema-loader.h>
#include <capnp/message.h>
#include <capnp/pretty-print.h>
#include "compiler.h"
#include <kj/function.h>
#include <kj/debug.h>
#include <stdlib.h>
#include <time.h>
#include <kj/main.h>
#include <kj/io.h>
#include <unistd.h>

namespace capnp {
namespace compiler {
namespace {

static const kj::StringPtr RFC3092[] = {"foo", "bar", "baz", "qux"};

template <typename T, size_t size>
T& chooseFrom(T (&arr)[size]) {
  return arr[rand() % size];
}
template <typename T>
auto chooseFrom(T arr) -> decltype(arr[0]) {
  return arr[rand() % arr.size()];
}

static Declaration::Builder addNested(Declaration::Builder parent) {
  auto oldNestedOrphan = parent.disownNestedDecls();
  auto oldNested = oldNestedOrphan.get();
  auto newNested = parent.initNestedDecls(oldNested.size() + 1);

  uint index = rand() % (oldNested.size() + 1);

  for (uint i = 0; i < index; i++) {
    newNested.setWithCaveats(i, oldNested[i]);
  }
  for (uint i = index + 1; i < newNested.size(); i++) {
    newNested.setWithCaveats(i, oldNested[i - 1]);
  }

  return newNested[index];
}

struct TypeOption {
  kj::StringPtr name;
  kj::ConstFunction<void(ValueExpression::Builder)> makeValue;
};

static const TypeOption TYPE_OPTIONS[] = {
  { "Int32",
    [](ValueExpression::Builder builder) {
      builder.setPositiveInt(rand() % (1 << 24));
    }},
  { "Float64",
    [](ValueExpression::Builder builder) {
      builder.setPositiveInt(rand());
    }},
  { "Int8",
    [](ValueExpression::Builder builder) {
      builder.setPositiveInt(rand() % 128);
    }},
  { "UInt16",
    [](ValueExpression::Builder builder) {
      builder.setPositiveInt(rand() % (1 << 16));
    }},
  { "Bool",
    [](ValueExpression::Builder builder) {
      builder.initName().getBase().initRelativeName().setValue("true");
    }},
  { "Text",
    [](ValueExpression::Builder builder) {
      builder.setString(chooseFrom(RFC3092));
    }},
  { "StructType",
    [](ValueExpression::Builder builder) {
      auto assignment = builder.initStruct(1)[0];
      assignment.initFieldName().setValue("i");
      assignment.initValue().setPositiveInt(rand() % (1 << 24));
    }},
  { "EnumType",
    [](ValueExpression::Builder builder) {
      builder.initName().getBase().initRelativeName().setValue(chooseFrom(RFC3092));
    }},
};

void setDeclName(DeclName::Builder decl, kj::StringPtr name) {
  decl.getBase().initRelativeName().setValue(name);
}

static kj::ConstFunction<void(ValueExpression::Builder)> randomizeType(
    TypeExpression::Builder type) {
  auto option = &chooseFrom(TYPE_OPTIONS);

  if (rand() % 4 == 0) {
    setDeclName(type.initName(), "List");
    setDeclName(type.initParams(1)[0].initName(), option->name);
    return [option](ValueExpression::Builder builder) {
      for (auto element: builder.initList(rand() % 4 + 1)) {
        option->makeValue(element);
      }
    };
  } else {
    setDeclName(type.initName(), option->name);
    return option->makeValue.reference();
  }
}

enum ChangeKind {
  NO_CHANGE,
  COMPATIBLE,
  INCOMPATIBLE,

  SUBTLY_COMPATIBLE
  // The change is technically compatible on the wire, but SchemaLoader will complain.
};

struct ChangeInfo {
  ChangeKind kind;
  kj::String description;

  ChangeInfo(): kind(NO_CHANGE) {}
  ChangeInfo(ChangeKind kind, kj::StringPtr description)
      : kind(kind), description(kj::str(description)) {}
  ChangeInfo(ChangeKind kind, kj::String&& description)
      : kind(kind), description(kj::mv(description)) {}
};

extern kj::ArrayPtr<kj::ConstFunction<ChangeInfo(Declaration::Builder, uint&, bool)>> STRUCT_MODS;
extern kj::ArrayPtr<kj::ConstFunction<ChangeInfo(Declaration::Builder, uint&, bool)>> FIELD_MODS;

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

static ChangeInfo declChangeName(Declaration::Builder decl, uint& nextOrdinal,
                                 bool scopeHasUnion) {
  auto name = decl.getName();
  if (name.getValue().size() == 0) {
    // Naming an unnamed union.
168
    name.setValue(kj::str("unUnnamed", nextOrdinal));
169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265
    return { SUBTLY_COMPATIBLE, "Assign name to unnamed union." };
  } else {
    name.setValue(kj::str(name.getValue(), "Xx"));
    return { COMPATIBLE, "Rename declaration." };
  }
}

static ChangeInfo structAddField(Declaration::Builder decl, uint& nextOrdinal, bool scopeHasUnion) {
  auto fieldDecl = addNested(decl);

  uint ordinal = nextOrdinal++;

  fieldDecl.initName().setValue(kj::str("f", ordinal));
  fieldDecl.getId().initOrdinal().setValue(ordinal);

  auto field = fieldDecl.initField();

  auto makeValue = randomizeType(field.initType());
  if (rand() % 4 == 0) {
    makeValue(field.getDefaultValue().initValue());
  } else {
    field.getDefaultValue().setNone();
  }
  return { COMPATIBLE, "Add field." };
}

static ChangeInfo structModifyField(Declaration::Builder decl, uint& nextOrdinal,
                                    bool scopeHasUnion) {
  auto nested = decl.getNestedDecls();

  if (nested.size() == 0) {
    return { NO_CHANGE, "Modify field, but there were none to modify." };
  }

  auto field = chooseFrom(nested);

  bool hasUnion = false;
  if (decl.isUnion()) {
    hasUnion = true;
  } else {
    for (auto n: nested) {
      if (n.isUnion() && n.getName().getValue().size() == 0) {
        hasUnion = true;
        break;
      }
    }
  }

  if (field.isGroup() || field.isUnion()) {
    return chooseFrom(STRUCT_MODS)(field, nextOrdinal, hasUnion);
  } else {
    return chooseFrom(FIELD_MODS)(field, nextOrdinal, hasUnion);
  }
}

static ChangeInfo structGroupifyFields(
    Declaration::Builder decl, uint& nextOrdinal, bool scopeHasUnion) {
  // Place a random subset of the fields into a group.

  if (decl.isUnion()) {
    return { NO_CHANGE,
      "Randomly make a group out of some fields, but I can't do this to a union." };
  }

  kj::Vector<Orphan<Declaration>> groupified;
  kj::Vector<Orphan<Declaration>> notGroupified;
  auto orphanage = Orphanage::getForMessageContaining(decl);

  for (auto nested: decl.getNestedDecls()) {
    if (rand() % 2) {
      groupified.add(orphanage.newOrphanCopy(nested.asReader()));
    } else {
      notGroupified.add(orphanage.newOrphanCopy(nested.asReader()));
    }
  }

  if (groupified.size() == 0) {
    return { NO_CHANGE,
      "Randomly make a group out of some fields, but I ended up choosing none of them." };
  }

  auto newNested = decl.initNestedDecls(notGroupified.size() + 1);
  uint index = rand() % (notGroupified.size() + 1);

  for (uint i = 0; i < index; i++) {
    newNested.adoptWithCaveats(i, kj::mv(notGroupified[i]));
  }
  for (uint i = index; i < notGroupified.size(); i++) {
    newNested.adoptWithCaveats(i + 1, kj::mv(notGroupified[i]));
  }

  auto newGroup = newNested[index];
  auto groupNested = newGroup.initNestedDecls(groupified.size());
  for (uint i = 0; i < groupified.size(); i++) {
    groupNested.adoptWithCaveats(i, kj::mv(groupified[i]));
  }

266
  newGroup.initName().setValue(kj::str("g", nextOrdinal, "x", groupNested[0].getName().getValue()));
267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 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 442 443 444 445 446 447
  newGroup.getId().setUnspecified();
  newGroup.setGroup();

  return { SUBTLY_COMPATIBLE, "Randomly group some set of existing fields." };
}

static ChangeInfo structPermuteFields(
    Declaration::Builder decl, uint& nextOrdinal, bool scopeHasUnion) {
  if (decl.getNestedDecls().size() == 0) {
    return { NO_CHANGE, "Permute field code order, but there were none." };
  }

  auto oldOrphan = decl.disownNestedDecls();
  auto old = oldOrphan.get();

  KJ_STACK_ARRAY(uint, mapping, old.size(), 16, 64);

  for (uint i = 0; i < mapping.size(); i++) {
    mapping[i] = i;
  }
  for (uint i = mapping.size() - 1; i > 0; i--) {
    uint j = rand() % i;
    uint temp = mapping[j];
    mapping[j] = mapping[i];
    mapping[i] = temp;
  }

  auto newNested = decl.initNestedDecls(old.size());
  for (uint i = 0; i < old.size(); i++) {
    newNested.setWithCaveats(i, old[mapping[i]]);
  }

  return { COMPATIBLE, "Permute field code order." };
}

kj::ConstFunction<ChangeInfo(Declaration::Builder, uint&, bool)> STRUCT_MODS_[] = {
  structAddField,
  structAddField,
  structAddField,
  structModifyField,
  structModifyField,
  structModifyField,
  structPermuteFields,
  declChangeName,
  structGroupifyFields     // do more rarely because it creates slowness
};
kj::ArrayPtr<kj::ConstFunction<ChangeInfo(Declaration::Builder, uint&, bool)>>
    STRUCT_MODS = STRUCT_MODS_;

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

static ChangeInfo fieldUpgradeList(Declaration::Builder decl, uint& nextOrdinal,
                                   bool scopeHasUnion) {
  // Upgrades a non-struct list to a struct list.

  auto field = decl.getField();
  if (field.getDefaultValue().isValue()) {
    return { NO_CHANGE, "Upgrade primitive list to struct list, but it had a default value." };
  }

  auto typeParams = field.getType().getParams();
  if (typeParams.size() != 1) {
    return { NO_CHANGE, "Upgrade primitive list to struct list, but it wasn't a list." };
  }

  auto elementType = typeParams[0];
  auto relativeName = elementType.getName().getBase().getRelativeName();
  auto nameText = relativeName.asReader().getValue();
  if (nameText == "StructType" || nameText.endsWith("Struct")) {
    return { NO_CHANGE, "Upgrade primitive list to struct list, but it was already a struct list."};
  }

  relativeName.setValue(kj::str(nameText, "Struct"));
  return { COMPATIBLE, "Upgrade primitive list to struct list" };
}

static ChangeInfo fieldExpandGroup(Declaration::Builder decl, uint& nextOrdinal,
                                   bool scopeHasUnion) {
  Declaration::Builder newDecl = decl.initNestedDecls(1)[0];
  newDecl.adoptName(decl.disownName());
  newDecl.getId().adoptOrdinal(decl.getId().disownOrdinal());

  auto field = decl.getField();
  auto newField = newDecl.initField();

  newField.adoptType(field.disownType());
  if (field.getDefaultValue().isValue()) {
    newField.getDefaultValue().adoptValue(field.getDefaultValue().disownValue());
  } else {
    newField.getDefaultValue().setNone();
  }

  decl.initName().setValue(kj::str("g", newDecl.getName().getValue()));
  decl.getId().setUnspecified();

  if (rand() % 2 == 0) {
    decl.setGroup();
  } else {
    decl.setUnion();
    if (!scopeHasUnion && rand() % 2 == 0) {
      // Make it an unnamed union.
      decl.getName().setValue("");
    }
    structAddField(decl, nextOrdinal, scopeHasUnion);  // union must have two members
  }

  return { COMPATIBLE, "Wrap a field in a singleton group." };
}

static ChangeInfo fieldChangeType(Declaration::Builder decl, uint& nextOrdinal,
                                  bool scopeHasUnion) {
  auto field = decl.getField();

  if (field.getDefaultValue().isNone()) {
    // Change the type.
    auto type = field.getType();
    while (type.getParams().size() > 0) {
      // Either change the list parameter, or revert to a non-list.
      if (rand() % 2) {
        type = type.getParams()[0];
      } else {
        type.disownParams();
      }
    }
    auto typeName = type.getName().getBase().getRelativeName();
    if (typeName.asReader().getValue().startsWith("Text")) {
      typeName.setValue("Int32");
    } else {
      typeName.setValue("Text");
    }
    return { INCOMPATIBLE, "Change the type of a field." };
  } else {
    // Change the default value.
    auto dval = field.getDefaultValue().getValue();
    switch (dval.which()) {
      case ValueExpression::UNKNOWN: KJ_FAIL_ASSERT("unknown value expression?");
      case ValueExpression::POSITIVE_INT: dval.setPositiveInt(dval.getPositiveInt() ^ 1); break;
      case ValueExpression::NEGATIVE_INT: dval.setNegativeInt(dval.getNegativeInt() ^ 1); break;
      case ValueExpression::FLOAT: dval.setFloat(-dval.getFloat()); break;
      case ValueExpression::NAME: {
        auto name = dval.getName().getBase().getRelativeName();
        auto nameText = name.asReader().getValue();
        if (nameText == "true") {
          name.setValue("false");
        } else if (nameText == "false") {
          name.setValue("true");
        } else if (nameText == "foo") {
          name.setValue("bar");
        } else {
          name.setValue("foo");
        }
        break;
      }
      case ValueExpression::STRING:
      case ValueExpression::LIST:
      case ValueExpression::STRUCT:
        return { NO_CHANGE, "Change the default value of a field, but it's a pointer field." };
    }
    return { INCOMPATIBLE, "Change the default value of a pritimive field." };
  }
}

kj::ConstFunction<ChangeInfo(Declaration::Builder, uint&, bool)> FIELD_MODS_[] = {
  fieldUpgradeList,
  fieldExpandGroup,
  fieldChangeType,
  declChangeName
};
kj::ArrayPtr<kj::ConstFunction<ChangeInfo(Declaration::Builder, uint&, bool)>>
    FIELD_MODS = FIELD_MODS_;

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

uint getOrdinal(StructSchema::Field field) {
  auto proto = field.getProto();
  if (proto.getOrdinal().isExplicit()) {
    return proto.getOrdinal().getExplicit();
  }

  KJ_ASSERT(proto.isGroup());

448
  auto group = field.getContainingStruct().getDependency(proto.getGroup().getTypeId()).asStruct();
449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466
  return getOrdinal(group.getFields()[0]);
}

Orphan<DynamicStruct> makeExampleStruct(
    Orphanage orphanage, StructSchema schema, uint sharedOrdinalCount);
void checkExampleStruct(DynamicStruct::Reader reader, uint sharedOrdinalCount);

Orphan<DynamicValue> makeExampleValue(
    Orphanage orphanage, Schema scope, uint ordinal, schema::Type::Reader type,
    uint sharedOrdinalCount) {
  switch (type.which()) {
    case schema::Type::INT32: return ordinal * 47327;
    case schema::Type::FLOAT64: return ordinal * 313.25;
    case schema::Type::INT8: return int(ordinal % 256) - 128;
    case schema::Type::UINT16: return ordinal * 13;
    case schema::Type::BOOL: return ordinal % 2 == 0;
    case schema::Type::TEXT: return orphanage.newOrphanCopy(Text::Reader(kj::str(ordinal)));
    case schema::Type::STRUCT: {
467
      auto structType = scope.getDependency(type.getStruct().getTypeId()).asStruct();
468 469 470 471 472 473 474 475 476 477
      auto result = orphanage.newOrphan(structType);
      auto builder = result.get();

      KJ_IF_MAYBE(fieldI, structType.findFieldByName("i")) {
        // Type is "StructType"
        builder.set(*fieldI, ordinal);
      } else {
        // Type is "Int32Struct" or the like.
        auto field = structType.getFieldByName("f0");
        builder.adopt(field, makeExampleValue(orphanage, structType, ordinal,
478
                                              field.getProto().getSlot().getType(),
479 480 481 482 483 484
                                              sharedOrdinalCount));
      }

      return kj::mv(result);
    }
    case schema::Type::ENUM: {
485
      auto enumerants = scope.getDependency(type.getEnum().getTypeId()).asEnum().getEnumerants();
486 487 488
      return DynamicEnum(enumerants[ordinal %enumerants.size()]);
    }
    case schema::Type::LIST: {
489
      auto elementType = type.getList().getElementType();
490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520
      auto listType = ListSchema::of(elementType, scope);
      auto result = orphanage.newOrphan(listType, 1);
      result.get().adopt(0, makeExampleValue(
          orphanage, scope, ordinal, elementType, sharedOrdinalCount));
      return kj::mv(result);
    }
    default:
      KJ_FAIL_ASSERT("You added a new possible field type!");
  }
}

void checkExampleValue(DynamicValue::Reader value, uint ordinal, schema::Type::Reader type,
                       uint sharedOrdinalCount) {
  switch (type.which()) {
    case schema::Type::INT32: KJ_ASSERT(value.as<int32_t>() == ordinal * 47327); break;
    case schema::Type::FLOAT64: KJ_ASSERT(value.as<double>() == ordinal * 313.25); break;
    case schema::Type::INT8: KJ_ASSERT(value.as<int8_t>() == int(ordinal % 256) - 128); break;
    case schema::Type::UINT16: KJ_ASSERT(value.as<uint16_t>() == ordinal * 13); break;
    case schema::Type::BOOL: KJ_ASSERT(value.as<bool>() == (ordinal % 2 == 0)); break;
    case schema::Type::TEXT: KJ_ASSERT(value.as<Text>() == kj::str(ordinal)); break;
    case schema::Type::STRUCT: {
      auto structValue = value.as<DynamicStruct>();
      auto structType = structValue.getSchema();

      KJ_IF_MAYBE(fieldI, structType.findFieldByName("i")) {
        // Type is "StructType"
        KJ_ASSERT(structValue.get(*fieldI).as<uint32_t>() == ordinal);
      } else {
        // Type is "Int32Struct" or the like.
        auto field = structType.getFieldByName("f0");
        checkExampleValue(structValue.get(field), ordinal,
521
                          field.getProto().getSlot().getType(), sharedOrdinalCount);
522 523 524 525 526 527 528 529 530 531
      }
      break;
    }
    case schema::Type::ENUM: {
      auto enumerant = KJ_ASSERT_NONNULL(value.as<DynamicEnum>().getEnumerant());
      KJ_ASSERT(enumerant.getIndex() ==
          ordinal % enumerant.getContainingEnum().getEnumerants().size());
      break;
    }
    case schema::Type::LIST:
532 533
      checkExampleValue(value.as<DynamicList>()[0], ordinal, type.getList().getElementType(),
                        sharedOrdinalCount);
534 535 536 537 538 539 540 541 542 543
      break;
    default:
      KJ_FAIL_ASSERT("You added a new possible field type!");
  }
}

void setExampleField(DynamicStruct::Builder builder, StructSchema::Field field,
                     uint sharedOrdinalCount) {
  auto fieldProto = field.getProto();
  switch (fieldProto.which()) {
544
    case schema::Field::SLOT:
545 546
      builder.adopt(field, makeExampleValue(
          Orphanage::getForMessageContaining(builder), field.getContainingStruct(),
547
          getOrdinal(field), fieldProto.getSlot().getType(), sharedOrdinalCount));
548 549 550 551
      break;
    case schema::Field::GROUP:
      builder.adopt(field, makeExampleStruct(
          Orphanage::getForMessageContaining(builder),
552
          field.getContainingStruct().getDependency(fieldProto.getGroup().getTypeId()).asStruct(),
553 554 555 556 557 558 559 560 561
          sharedOrdinalCount));
      break;
  }
}

void checkExampleField(DynamicStruct::Reader reader, StructSchema::Field field,
                       uint sharedOrdinalCount) {
  auto fieldProto = field.getProto();
  switch (fieldProto.which()) {
562
    case schema::Field::SLOT: {
563 564 565
      uint ordinal = getOrdinal(field);
      if (ordinal < sharedOrdinalCount) {
        checkExampleValue(reader.get(field), ordinal,
566
                          fieldProto.getSlot().getType(), sharedOrdinalCount);
567 568 569 570 571 572 573 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 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632
      }
      break;
    }
    case schema::Field::GROUP:
      checkExampleStruct(reader.get(field).as<DynamicStruct>(), sharedOrdinalCount);
      break;
  }
}

Orphan<DynamicStruct> makeExampleStruct(
    Orphanage orphanage, StructSchema schema, uint sharedOrdinalCount) {
  // Initialize all fields of the struct via reflection, such that they can be verified using
  // a different version of the struct.  sharedOrdinalCount is the number of ordinals shared by
  // the two versions.  This is used mainly to avoid setting union members that the other version
  // doesn't have.

  Orphan<DynamicStruct> result = orphanage.newOrphan(schema);
  auto builder = result.get();

  for (auto field: schema.getNonUnionFields()) {
    setExampleField(builder, field, sharedOrdinalCount);
  }

  auto unionFields = schema.getUnionFields();

  // Pretend the union doesn't have any fields that aren't in the shared ordinal range.
  uint range = unionFields.size();
  while (range > 0 && getOrdinal(unionFields[range - 1]) >= sharedOrdinalCount) {
    --range;
  }

  if (range > 0) {
    auto field = unionFields[getOrdinal(unionFields[0]) % range];
    setExampleField(builder, field, sharedOrdinalCount);
  }

  return kj::mv(result);
}

void checkExampleStruct(DynamicStruct::Reader reader, uint sharedOrdinalCount) {
  auto schema = reader.getSchema();

  for (auto field: schema.getNonUnionFields()) {
    checkExampleField(reader, field, sharedOrdinalCount);
  }

  auto unionFields = schema.getUnionFields();

  // Pretend the union doesn't have any fields that aren't in the shared ordinal range.
  uint range = unionFields.size();
  while (range > 0 && getOrdinal(unionFields[range - 1]) >= sharedOrdinalCount) {
    --range;
  }

  if (range > 0) {
    auto field = unionFields[getOrdinal(unionFields[0]) % range];
    checkExampleField(reader, field, sharedOrdinalCount);
  }
}

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

class ModuleImpl final: public Module {
public:
  explicit ModuleImpl(ParsedFile::Reader content): content(content) {}

633 634
  kj::StringPtr getSourceName() override { return "evolving-schema.capnp"; }
  Orphan<ParsedFile> loadContent(Orphanage orphanage) override {
635 636
    return orphanage.newOrphanCopy(content);
  }
637
  kj::Maybe<Module&> importRelative(kj::StringPtr importPath) override {
638 639 640
    return nullptr;
  }

641
  void addError(uint32_t startByte, uint32_t endByte, kj::StringPtr message) override {
642 643
    KJ_FAIL_ASSERT("Unexpected parse error.", startByte, endByte, message);
  }
644
  bool hadErrors() override {
645 646 647 648 649 650 651 652 653 654 655 656 657
    return false;
  }

private:
  ParsedFile::Reader content;
};

static void loadStructAndGroups(const SchemaLoader& src, SchemaLoader& dst, uint64_t id) {
  auto proto = src.get(id).getProto();
  dst.load(proto);

  for (auto field: proto.getStruct().getFields()) {
    if (field.isGroup()) {
658
      loadStructAndGroups(src, dst, field.getGroup().getTypeId());
659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676
    }
  }
}

static kj::Maybe<kj::Exception> loadFile(
    ParsedFile::Reader file, SchemaLoader& loader, bool allNodes,
    kj::Maybe<kj::Own<MallocMessageBuilder>>& messageBuilder,
    uint sharedOrdinalCount) {
  Compiler compiler;
  ModuleImpl module(file);
  KJ_ASSERT(compiler.add(module) == 0x8123456789abcdefllu);

  if (allNodes) {
    // Eagerly compile and load the whole thing.
    compiler.eagerlyCompile(0x8123456789abcdefllu, Compiler::ALL_RELATED_NODES);

    KJ_IF_MAYBE(m, messageBuilder) {
      // Build an example struct using the compiled schema.
677 678
      m->get()->adoptRoot(makeExampleStruct(
          m->get()->getOrphanage(), compiler.getLoader().get(0x823456789abcdef1llu).asStruct(),
679 680 681 682 683 684 685 686 687 688 689 690 691 692
          sharedOrdinalCount));
    }

    for (auto schema: compiler.getLoader().getAllLoaded()) {
      loader.load(schema.getProto());
    }
    return nullptr;
  } else {
    // Compile the file root so that the children are findable, then load the specific child
    // we want.
    compiler.eagerlyCompile(0x8123456789abcdefllu, Compiler::NODE);

    KJ_IF_MAYBE(m, messageBuilder) {
      // Check that the example struct matches the compiled schema.
693
      auto root = m->get()->getRoot<DynamicStruct>(
694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740
          compiler.getLoader().get(0x823456789abcdef1llu).asStruct()).asReader();
      KJ_CONTEXT(root);
      checkExampleStruct(root, sharedOrdinalCount);
    }

    return kj::runCatchingExceptions([&]() {
      loadStructAndGroups(compiler.getLoader(), loader, 0x823456789abcdef1llu);
    });
  }
}

bool checkChange(ParsedFile::Reader file1, ParsedFile::Reader file2, ChangeKind changeKind,
                 uint sharedOrdinalCount) {
  // Try loading file1 followed by file2 into the same SchemaLoader, expecting it to behave
  // according to changeKind.  Returns true if the files are both expected to be compatible and
  // actually are -- the main loop uses this to decide which version to keep

  kj::Maybe<kj::Own<MallocMessageBuilder>> exampleBuilder;

  if (changeKind != INCOMPATIBLE) {
    // For COMPATIBLE and SUBTLY_COMPATIBLE changes, build an example message with one schema
    // and check it with the other.
    exampleBuilder = kj::heap<MallocMessageBuilder>();
  }

  SchemaLoader loader;
  loadFile(file1, loader, true, exampleBuilder, sharedOrdinalCount);
  auto exception = loadFile(file2, loader, false, exampleBuilder, sharedOrdinalCount);

  if (changeKind == COMPATIBLE) {
    KJ_IF_MAYBE(e, exception) {
      kj::getExceptionCallback().onFatalException(kj::mv(*e));
      return false;
    } else {
      return true;
    }
  } else if (changeKind == INCOMPATIBLE) {
    KJ_ASSERT(exception != nullptr, file1, file2);
    return false;
  } else {
    KJ_ASSERT(changeKind == SUBTLY_COMPATIBLE);

    // SchemaLoader is allowed to throw an exception in this case, but we ignore it.
    return true;
  }
}

Kenton Varda's avatar
Kenton Varda committed
741
void doTest() {
742 743 744 745 746 747 748 749
  auto builder = kj::heap<MallocMessageBuilder>();

  {
    // Set up the basic file decl.
    auto parsedFile = builder->initRoot<ParsedFile>();
    auto file = parsedFile.initRoot();
    file.setFile();
    file.initId().initUid().setValue(0x8123456789abcdefllu);
750
    auto decls = file.initNestedDecls(3 + kj::size(TYPE_OPTIONS));
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

    {
      auto decl = decls[0];
      decl.initName().setValue("EvolvingStruct");
      decl.initId().initUid().setValue(0x823456789abcdef1llu);
      decl.setStruct();
    }
    {
      auto decl = decls[1];
      decl.initName().setValue("StructType");
      decl.setStruct();

      auto fieldDecl = decl.initNestedDecls(1)[0];
      fieldDecl.initName().setValue("i");
      fieldDecl.getId().initOrdinal().setValue(0);
      auto field = fieldDecl.initField();
      setDeclName(field.initType().initName(), "UInt32");
    }
    {
      auto decl = decls[2];
      decl.initName().setValue("EnumType");
      decl.setEnum();

      auto enumerants = decl.initNestedDecls(4);

776
      for (uint i = 0; i < kj::size(RFC3092); i++) {
777 778 779 780 781 782 783 784
        auto enumerantDecl = enumerants[i];
        enumerantDecl.initName().setValue(RFC3092[i]);
        enumerantDecl.getId().initOrdinal().setValue(i);
        enumerantDecl.setEnumerant();
      }
    }

    // For each of TYPE_OPTIONS, declare a struct type that contains that type as its @0 field.
785
    for (uint i = 0; i < kj::size(TYPE_OPTIONS); i++) {
786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807
      auto decl = decls[3 + i];
      auto& option = TYPE_OPTIONS[i];

      decl.initName().setValue(kj::str(option.name, "Struct"));
      decl.setStruct();

      auto fieldDecl = decl.initNestedDecls(1)[0];
      fieldDecl.initName().setValue("f0");
      fieldDecl.getId().initOrdinal().setValue(0);
      auto field = fieldDecl.initField();
      setDeclName(field.initType().initName(), option.name);

      uint ordinal = 1;
      for (auto j: kj::range(0, rand() % 4)) {
        (void)j;
        structAddField(decl, ordinal, false);
      }
    }
  }

  uint nextOrdinal = 0;

808
  for (uint i = 0; i < 96; i++) {
809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843
    uint oldOrdinalCount = nextOrdinal;

    auto newBuilder = kj::heap<MallocMessageBuilder>();
    newBuilder->setRoot(builder->getRoot<ParsedFile>().asReader());

    auto parsedFile = newBuilder->getRoot<ParsedFile>();
    Declaration::Builder decl = parsedFile.getRoot().getNestedDecls()[0];

    // Apply a random modification.
    ChangeInfo changeInfo;
    while (changeInfo.kind == NO_CHANGE) {
      auto& mod = chooseFrom(STRUCT_MODS);
      changeInfo = mod(decl, nextOrdinal, false);
    }

    KJ_CONTEXT(changeInfo.description);

    if (checkChange(builder->getRoot<ParsedFile>(), parsedFile, changeInfo.kind, oldOrdinalCount) &&
        checkChange(parsedFile, builder->getRoot<ParsedFile>(), changeInfo.kind, oldOrdinalCount)) {
      builder = kj::mv(newBuilder);
    }
  }
}

class EvolutionTestMain {
public:
  explicit EvolutionTestMain(kj::ProcessContext& context)
      : context(context) {}

  kj::MainFunc getMain() {
    return kj::MainBuilder(context, "(unknown version)",
        "Integration test / fuzzer which randomly modifies schemas is backwards-compatible ways "
        "and verifies that they do actually remain compatible.")
        .addOptionWithArg({"seed"}, KJ_BIND_METHOD(*this, setSeed), "<num>",
            "Set random number seed to <num>.  By default, time() is used.")
Kenton Varda's avatar
Kenton Varda committed
844
        .callAfterParsing(KJ_BIND_METHOD(*this, run))
845 846 847 848 849 850 851 852 853 854 855 856 857
        .build();
  }

  kj::MainBuilder::Validity setSeed(kj::StringPtr value) {
    char* end;
    seed = strtol(value.cStr(), &end, 0);
    if (value.size() == 0 || *end != '\0') {
      return "not an integer";
    } else {
      return true;
    }
  }

Kenton Varda's avatar
Kenton Varda committed
858 859 860 861 862
  kj::MainBuilder::Validity run() {
    srand(seed);

    {
      kj::String text = kj::str(
863
          "Randomly testing backwards-compatibility scenarios with seed: ", seed, "\n");
Kenton Varda's avatar
Kenton Varda committed
864 865 866 867 868 869 870 871 872 873
      kj::FdOutputStream(STDOUT_FILENO).write(text.begin(), text.size());
    }

    KJ_CONTEXT(seed, "PLEASE REPORT THIS FAILURE AND INCLUDE THE SEED");

    doTest();

    return true;
  }

874 875 876 877 878 879 880 881 882 883
private:
  kj::ProcessContext& context;
  uint seed = time(nullptr);
};

}  // namespace
}  // namespace compiler
}  // namespace capnp

KJ_MAIN(capnp::compiler::EvolutionTestMain);