contrib/libucl/src/ucl_schema.c

   1 /*
   2  * Copyright (c) 2014, Vsevolod Stakhov
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are met:
   8  *       * Redistributions of source code must retain the above copyright
   9  *         notice, this list of conditions and the following disclaimer.
  10  *       * Redistributions in binary form must reproduce the above copyright
  11  *         notice, this list of conditions and the following disclaimer in the
  12  *         documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY AUTHOR ''AS IS'' AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  17  * DISCLAIMED. IN NO EVENT SHALL AUTHOR BE LIABLE FOR ANY
  18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  21  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  23  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "ucl.h"
  27 #include "ucl_internal.h"
  28 #include "tree.h"
  29 #include "utlist.h"
  30 #ifdef HAVE_STDARG_H
  31 #include <stdarg.h>
  32 #endif
  33 #ifdef HAVE_STDIO_H
  34 #include <stdio.h>
  35 #endif
  36 #ifdef HAVE_REGEX_H
  37 #include <regex.h>
  38 #endif
  39 #ifdef HAVE_MATH_H
  40 #include <math.h>
  41 #endif
  42
  43 static bool ucl_schema_validate (const ucl_object_t *schema,
  44                 const ucl_object_t *obj, bool try_array,
  45                 struct ucl_schema_error *err,
  46                 const ucl_object_t *root);
  47
  48 static bool
  49 ucl_string_to_type (const char *input, ucl_type_t *res)
  50 {
  51         if (strcasecmp (input, "object") == 0) {
  52                 *res = UCL_OBJECT;
  53         }
  54         else if (strcasecmp (input, "array") == 0) {
  55                 *res = UCL_ARRAY;
  56         }
  57         else if (strcasecmp (input, "integer") == 0) {
  58                 *res = UCL_INT;
  59         }
  60         else if (strcasecmp (input, "number") == 0) {
  61                 *res = UCL_FLOAT;
  62         }
  63         else if (strcasecmp (input, "string") == 0) {
  64                 *res = UCL_STRING;
  65         }
  66         else if (strcasecmp (input, "boolean") == 0) {
  67                 *res = UCL_BOOLEAN;
  68         }
  69         else if (strcasecmp (input, "null") == 0) {
  70                 *res = UCL_NULL;
  71         }
  72         else {
  73                 return false;
  74         }
  75
  76         return true;
  77 }
  78
  79 static const char *
  80 ucl_object_type_to_string (ucl_type_t type)
  81 {
  82         const char *res = "unknown";
  83
  84         switch (type) {
  85         case UCL_OBJECT:
  86                 res = "object";
  87                 break;
  88         case UCL_ARRAY:
  89                 res = "array";
  90                 break;
  91         case UCL_INT:
  92                 res = "integer";
  93                 break;
  94         case UCL_FLOAT:
  95         case UCL_TIME:
  96                 res = "number";
  97                 break;
  98         case UCL_STRING:
  99                 res = "string";
 100                 break;
 101         case UCL_BOOLEAN:
 102                 res = "boolean";
 103                 break;
 104         case UCL_NULL:
 105         case UCL_USERDATA:
 106                 res = "null";
 107                 break;
 108         }
 109
 110         return res;
 111 }
 112
 113 /*
 114  * Create validation error
 115  */
 116 static void
 117 ucl_schema_create_error (struct ucl_schema_error *err,
 118                 enum ucl_schema_error_code code, const ucl_object_t *obj,
 119                 const char *fmt, ...)
 120 {
 121         va_list va;
 122
 123         if (err != NULL) {
 124                 err->code = code;
 125                 err->obj = obj;
 126                 va_start (va, fmt);
 127                 vsnprintf (err->msg, sizeof (err->msg), fmt, va);
 128                 va_end (va);
 129         }
 130 }
 131
 132 /*
 133  * Check whether we have a pattern specified
 134  */
 135 static const ucl_object_t *
 136 ucl_schema_test_pattern (const ucl_object_t *obj, const char *pattern)
 137 {
 138         const ucl_object_t *res = NULL;
 139 #ifdef HAVE_REGEX_H
 140         regex_t reg;
 141         const ucl_object_t *elt;
 142         ucl_object_iter_t iter = NULL;
 143
 144         if (regcomp (&reg, pattern, REG_EXTENDED | REG_NOSUB) == 0) {
 145                 while ((elt = ucl_iterate_object (obj, &iter, true)) != NULL) {
 146                         if (regexec (&reg, ucl_object_key (elt), 0, NULL, 0) == 0) {
 147                                 res = elt;
 148                                 break;
 149                         }
 150                 }
 151                 regfree (&reg);
 152         }
 153 #endif
 154         return res;
 155 }
 156
 157 /*
 158  * Check dependencies for an object
 159  */
 160 static bool
 161 ucl_schema_validate_dependencies (const ucl_object_t *deps,
 162                 const ucl_object_t *obj, struct ucl_schema_error *err,
 163                 const ucl_object_t *root)
 164 {
 165         const ucl_object_t *elt, *cur, *cur_dep;
 166         ucl_object_iter_t iter = NULL, piter;
 167         bool ret = true;
 168
 169         while (ret && (cur = ucl_iterate_object (deps, &iter, true)) != NULL) {
 170                 elt = ucl_object_find_key (obj, ucl_object_key (cur));
 171                 if (elt != NULL) {
 172                         /* Need to check dependencies */
 173                         if (cur->type == UCL_ARRAY) {
 174                                 piter = NULL;
 175                                 while (ret && (cur_dep = ucl_iterate_object (cur, &piter, true)) != NULL) {
 176                                         if (ucl_object_find_key (obj, ucl_object_tostring (cur_dep)) == NULL) {
 177                                                 ucl_schema_create_error (err, UCL_SCHEMA_MISSING_DEPENDENCY, elt,
 178                                                                 "dependency %s is missing for key %s",
 179                                                                 ucl_object_tostring (cur_dep), ucl_object_key (cur));
 180                                                 ret = false;
 181                                                 break;
 182                                         }
 183                                 }
 184                         }
 185                         else if (cur->type == UCL_OBJECT) {
 186                                 ret = ucl_schema_validate (cur, obj, true, err, root);
 187                         }
 188                 }
 189         }
 190
 191         return ret;
 192 }
 193
 194 /*
 195  * Validate object
 196  */
 197 static bool
 198 ucl_schema_validate_object (const ucl_object_t *schema,
 199                 const ucl_object_t *obj, struct ucl_schema_error *err,
 200                 const ucl_object_t *root)
 201 {
 202         const ucl_object_t *elt, *prop, *found, *additional_schema = NULL,
 203                         *required = NULL, *pat, *pelt;
 204         ucl_object_iter_t iter = NULL, piter = NULL;
 205         bool ret = true, allow_additional = true;
 206         int64_t minmax;
 207
 208         while (ret && (elt = ucl_iterate_object (schema, &iter, true)) != NULL) {
 209                 if (elt->type == UCL_OBJECT &&
 210                                 strcmp (ucl_object_key (elt), "properties") == 0) {
 211                         piter = NULL;
 212                         while (ret && (prop = ucl_iterate_object (elt, &piter, true)) != NULL) {
 213                                 found = ucl_object_find_key (obj, ucl_object_key (prop));
 214                                 if (found) {
 215                                         ret = ucl_schema_validate (prop, found, true, err, root);
 216                                 }
 217                         }
 218                 }
 219                 else if (strcmp (ucl_object_key (elt), "additionalProperties") == 0) {
 220                         if (elt->type == UCL_BOOLEAN) {
 221                                 if (!ucl_object_toboolean (elt)) {
 222                                         /* Deny additional fields completely */
 223                                         allow_additional = false;
 224                                 }
 225                         }
 226                         else if (elt->type == UCL_OBJECT) {
 227                                 /* Define validator for additional fields */
 228                                 additional_schema = elt;
 229                         }
 230                         else {
 231                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, elt,
 232                                                 "additionalProperties attribute is invalid in schema");
 233                                 ret = false;
 234                                 break;
 235                         }
 236                 }
 237                 else if (strcmp (ucl_object_key (elt), "required") == 0) {
 238                         if (elt->type == UCL_ARRAY) {
 239                                 required = elt;
 240                         }
 241                         else {
 242                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, elt,
 243                                                 "required attribute is invalid in schema");
 244                                 ret = false;
 245                                 break;
 246                         }
 247                 }
 248                 else if (strcmp (ucl_object_key (elt), "minProperties") == 0
 249                                 && ucl_object_toint_safe (elt, &minmax)) {
 250                         if (obj->len < minmax) {
 251                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 252                                                 "object has not enough properties: %u, minimum is: %u",
 253                                                 obj->len, (unsigned)minmax);
 254                                 ret = false;
 255                                 break;
 256                         }
 257                 }
 258                 else if (strcmp (ucl_object_key (elt), "maxProperties") == 0
 259                                 && ucl_object_toint_safe (elt, &minmax)) {
 260                         if (obj->len > minmax) {
 261                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 262                                                 "object has too many properties: %u, maximum is: %u",
 263                                                 obj->len, (unsigned)minmax);
 264                                 ret = false;
 265                                 break;
 266                         }
 267                 }
 268                 else if (strcmp (ucl_object_key (elt), "patternProperties") == 0) {
 269                         piter = NULL;
 270                         while (ret && (prop = ucl_iterate_object (elt, &piter, true)) != NULL) {
 271                                 found = ucl_schema_test_pattern (obj, ucl_object_key (prop));
 272                                 if (found) {
 273                                         ret = ucl_schema_validate (prop, found, true, err, root);
 274                                 }
 275                         }
 276                 }
 277                 else if (elt->type == UCL_OBJECT &&
 278                                 strcmp (ucl_object_key (elt), "dependencies") == 0) {
 279                         ret = ucl_schema_validate_dependencies (elt, obj, err, root);
 280                 }
 281         }
 282
 283         if (ret) {
 284                 /* Additional properties */
 285                 if (!allow_additional || additional_schema != NULL) {
 286                         /* Check if we have exactly the same properties in schema and object */
 287                         iter = NULL;
 288                         prop = ucl_object_find_key (schema, "properties");
 289                         while ((elt = ucl_iterate_object (obj, &iter, true)) != NULL) {
 290                                 found = ucl_object_find_key (prop, ucl_object_key (elt));
 291                                 if (found == NULL) {
 292                                         /* Try patternProperties */
 293                                         piter = NULL;
 294                                         pat = ucl_object_find_key (schema, "patternProperties");
 295                                         while ((pelt = ucl_iterate_object (pat, &piter, true)) != NULL) {
 296                                                 found = ucl_schema_test_pattern (obj, ucl_object_key (pelt));
 297                                                 if (found != NULL) {
 298                                                         break;
 299                                                 }
 300                                         }
 301                                 }
 302                                 if (found == NULL) {
 303                                         if (!allow_additional) {
 304                                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 305                                                                 "object has non-allowed property %s",
 306                                                                 ucl_object_key (elt));
 307                                                 ret = false;
 308                                                 break;
 309                                         }
 310                                         else if (additional_schema != NULL) {
 311                                                 if (!ucl_schema_validate (additional_schema, elt, true, err, root)) {
 312                                                         ret = false;
 313                                                         break;
 314                                                 }
 315                                         }
 316                                 }
 317                         }
 318                 }
 319                 /* Required properties */
 320                 if (required != NULL) {
 321                         iter = NULL;
 322                         while ((elt = ucl_iterate_object (required, &iter, true)) != NULL) {
 323                                 if (ucl_object_find_key (obj, ucl_object_tostring (elt)) == NULL) {
 324                                         ucl_schema_create_error (err, UCL_SCHEMA_MISSING_PROPERTY, obj,
 325                                                         "object has missing property %s",
 326                                                         ucl_object_tostring (elt));
 327                                         ret = false;
 328                                         break;
 329                                 }
 330                         }
 331                 }
 332         }
 333
 334
 335         return ret;
 336 }
 337
 338 static bool
 339 ucl_schema_validate_number (const ucl_object_t *schema,
 340                 const ucl_object_t *obj, struct ucl_schema_error *err)
 341 {
 342         const ucl_object_t *elt, *test;
 343         ucl_object_iter_t iter = NULL;
 344         bool ret = true, exclusive = false;
 345         double constraint, val;
 346         const double alpha = 1e-16;
 347
 348         while (ret && (elt = ucl_iterate_object (schema, &iter, true)) != NULL) {
 349                 if ((elt->type == UCL_FLOAT || elt->type == UCL_INT) &&
 350                                 strcmp (ucl_object_key (elt), "multipleOf") == 0) {
 351                         constraint = ucl_object_todouble (elt);
 352                         if (constraint <= 0) {
 353                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, elt,
 354                                                 "multipleOf must be greater than zero");
 355                                 ret = false;
 356                                 break;
 357                         }
 358                         val = ucl_object_todouble (obj);
 359                         if (fabs (remainder (val, constraint)) > alpha) {
 360                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 361                                                 "number %.4f is not multiple of %.4f, remainder is %.7f",
 362                                                 val, constraint);
 363                                 ret = false;
 364                                 break;
 365                         }
 366                 }
 367                 else if ((elt->type == UCL_FLOAT || elt->type == UCL_INT) &&
 368                         strcmp (ucl_object_key (elt), "maximum") == 0) {
 369                         constraint = ucl_object_todouble (elt);
 370                         test = ucl_object_find_key (schema, "exclusiveMaximum");
 371                         if (test && test->type == UCL_BOOLEAN) {
 372                                 exclusive = ucl_object_toboolean (test);
 373                         }
 374                         val = ucl_object_todouble (obj);
 375                         if (val > constraint || (exclusive && val >= constraint)) {
 376                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 377                                                 "number is too big: %.3f, maximum is: %.3f",
 378                                                 val, constraint);
 379                                 ret = false;
 380                                 break;
 381                         }
 382                 }
 383                 else if ((elt->type == UCL_FLOAT || elt->type == UCL_INT) &&
 384                                 strcmp (ucl_object_key (elt), "minimum") == 0) {
 385                         constraint = ucl_object_todouble (elt);
 386                         test = ucl_object_find_key (schema, "exclusiveMinimum");
 387                         if (test && test->type == UCL_BOOLEAN) {
 388                                 exclusive = ucl_object_toboolean (test);
 389                         }
 390                         val = ucl_object_todouble (obj);
 391                         if (val < constraint || (exclusive && val <= constraint)) {
 392                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 393                                                 "number is too small: %.3f, minimum is: %.3f",
 394                                                 val, constraint);
 395                                 ret = false;
 396                                 break;
 397                         }
 398                 }
 399         }
 400
 401         return ret;
 402 }
 403
 404 static bool
 405 ucl_schema_validate_string (const ucl_object_t *schema,
 406                 const ucl_object_t *obj, struct ucl_schema_error *err)
 407 {
 408         const ucl_object_t *elt;
 409         ucl_object_iter_t iter = NULL;
 410         bool ret = true;
 411         int64_t constraint;
 412 #ifdef HAVE_REGEX_H
 413         regex_t re;
 414 #endif
 415
 416         while (ret && (elt = ucl_iterate_object (schema, &iter, true)) != NULL) {
 417                 if (elt->type == UCL_INT &&
 418                         strcmp (ucl_object_key (elt), "maxLength") == 0) {
 419                         constraint = ucl_object_toint (elt);
 420                         if (obj->len > constraint) {
 421                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 422                                                 "string is too big: %.3f, maximum is: %.3f",
 423                                                 obj->len, constraint);
 424                                 ret = false;
 425                                 break;
 426                         }
 427                 }
 428                 else if (elt->type == UCL_INT &&
 429                                 strcmp (ucl_object_key (elt), "minLength") == 0) {
 430                         constraint = ucl_object_toint (elt);
 431                         if (obj->len < constraint) {
 432                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 433                                                 "string is too short: %.3f, minimum is: %.3f",
 434                                                 obj->len, constraint);
 435                                 ret = false;
 436                                 break;
 437                         }
 438                 }
 439 #ifdef HAVE_REGEX_H
 440                 else if (elt->type == UCL_STRING &&
 441                                 strcmp (ucl_object_key (elt), "pattern") == 0) {
 442                         if (regcomp (&re, ucl_object_tostring (elt),
 443                                         REG_EXTENDED | REG_NOSUB) != 0) {
 444                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, elt,
 445                                                 "cannot compile pattern %s", ucl_object_tostring (elt));
 446                                 ret = false;
 447                                 break;
 448                         }
 449                         if (regexec (&re, ucl_object_tostring (obj), 0, NULL, 0) != 0) {
 450                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 451                                                 "string doesn't match regexp %s",
 452                                                 ucl_object_tostring (elt));
 453                                 ret = false;
 454                         }
 455                         regfree (&re);
 456                 }
 457 #endif
 458         }
 459
 460         return ret;
 461 }
 462
 463 struct ucl_compare_node {
 464         const ucl_object_t *obj;
 465         TREE_ENTRY(ucl_compare_node) link;
 466         struct ucl_compare_node *next;
 467 };
 468
 469 typedef TREE_HEAD(_tree, ucl_compare_node) ucl_compare_tree_t;
 470
 471 TREE_DEFINE(ucl_compare_node, link)
 472
 473 static int
 474 ucl_schema_elt_compare (struct ucl_compare_node *n1, struct ucl_compare_node *n2)
 475 {
 476         const ucl_object_t *o1 = n1->obj, *o2 = n2->obj;
 477
 478         return ucl_object_compare (o1, o2);
 479 }
 480
 481 static bool
 482 ucl_schema_array_is_unique (const ucl_object_t *obj, struct ucl_schema_error *err)
 483 {
 484         ucl_compare_tree_t tree = TREE_INITIALIZER (ucl_schema_elt_compare);
 485         ucl_object_iter_t iter = NULL;
 486         const ucl_object_t *elt;
 487         struct ucl_compare_node *node, test, *nodes = NULL, *tmp;
 488         bool ret = true;
 489
 490         while ((elt = ucl_iterate_object (obj, &iter, true)) != NULL) {
 491                 test.obj = elt;
 492                 node = TREE_FIND (&tree, ucl_compare_node, link, &test);
 493                 if (node != NULL) {
 494                         ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, elt,
 495                                         "duplicate values detected while uniqueItems is true");
 496                         ret = false;
 497                         break;
 498                 }
 499                 node = calloc (1, sizeof (*node));
 500                 if (node == NULL) {
 501                         ucl_schema_create_error (err, UCL_SCHEMA_UNKNOWN, elt,
 502                                         "cannot allocate tree node");
 503                         ret = false;
 504                         break;
 505                 }
 506                 node->obj = elt;
 507                 TREE_INSERT (&tree, ucl_compare_node, link, node);
 508                 LL_PREPEND (nodes, node);
 509         }
 510
 511         LL_FOREACH_SAFE (nodes, node, tmp) {
 512                 free (node);
 513         }
 514
 515         return ret;
 516 }
 517
 518 static bool
 519 ucl_schema_validate_array (const ucl_object_t *schema,
 520                 const ucl_object_t *obj, struct ucl_schema_error *err,
 521                 const ucl_object_t *root)
 522 {
 523         const ucl_object_t *elt, *it, *found, *additional_schema = NULL,
 524                         *first_unvalidated = NULL;
 525         ucl_object_iter_t iter = NULL, piter = NULL;
 526         bool ret = true, allow_additional = true, need_unique = false;
 527         int64_t minmax;
 528
 529         while (ret && (elt = ucl_iterate_object (schema, &iter, true)) != NULL) {
 530                 if (strcmp (ucl_object_key (elt), "items") == 0) {
 531                         if (elt->type == UCL_ARRAY) {
 532                                 found = obj->value.av;
 533                                 while (ret && (it = ucl_iterate_object (elt, &piter, true)) != NULL) {
 534                                         if (found) {
 535                                                 ret = ucl_schema_validate (it, found, false, err, root);
 536                                                 found = found->next;
 537                                         }
 538                                 }
 539                                 if (found != NULL) {
 540                                         /* The first element that is not validated */
 541                                         first_unvalidated = found;
 542                                 }
 543                         }
 544                         else if (elt->type == UCL_OBJECT) {
 545                                 /* Validate all items using the specified schema */
 546                                 while (ret && (it = ucl_iterate_object (obj, &piter, true)) != NULL) {
 547                                         ret = ucl_schema_validate (elt, it, false, err, root);
 548                                 }
 549                         }
 550                         else {
 551                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, elt,
 552                                                 "items attribute is invalid in schema");
 553                                 ret = false;
 554                                 break;
 555                         }
 556                 }
 557                 else if (strcmp (ucl_object_key (elt), "additionalItems") == 0) {
 558                         if (elt->type == UCL_BOOLEAN) {
 559                                 if (!ucl_object_toboolean (elt)) {
 560                                         /* Deny additional fields completely */
 561                                         allow_additional = false;
 562                                 }
 563                         }
 564                         else if (elt->type == UCL_OBJECT) {
 565                                 /* Define validator for additional fields */
 566                                 additional_schema = elt;
 567                         }
 568                         else {
 569                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, elt,
 570                                                 "additionalItems attribute is invalid in schema");
 571                                 ret = false;
 572                                 break;
 573                         }
 574                 }
 575                 else if (elt->type == UCL_BOOLEAN &&
 576                                 strcmp (ucl_object_key (elt), "uniqueItems") == 0) {
 577                         need_unique = ucl_object_toboolean (elt);
 578                 }
 579                 else if (strcmp (ucl_object_key (elt), "minItems") == 0
 580                                 && ucl_object_toint_safe (elt, &minmax)) {
 581                         if (obj->len < minmax) {
 582                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 583                                                 "array has not enough items: %u, minimum is: %u",
 584                                                 obj->len, (unsigned)minmax);
 585                                 ret = false;
 586                                 break;
 587                         }
 588                 }
 589                 else if (strcmp (ucl_object_key (elt), "maxItems") == 0
 590                                 && ucl_object_toint_safe (elt, &minmax)) {
 591                         if (obj->len > minmax) {
 592                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 593                                                 "array has too many items: %u, maximum is: %u",
 594                                                 obj->len, (unsigned)minmax);
 595                                 ret = false;
 596                                 break;
 597                         }
 598                 }
 599         }
 600
 601         if (ret) {
 602                 /* Additional properties */
 603                 if (!allow_additional || additional_schema != NULL) {
 604                         if (first_unvalidated != NULL) {
 605                                 if (!allow_additional) {
 606                                         ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 607                                                         "array has undefined item");
 608                                         ret = false;
 609                                 }
 610                                 else if (additional_schema != NULL) {
 611                                         elt = first_unvalidated;
 612                                         while (elt) {
 613                                                 if (!ucl_schema_validate (additional_schema, elt, false,
 614                                                                 err, root)) {
 615                                                         ret = false;
 616                                                         break;
 617                                                 }
 618                                                 elt = elt->next;
 619                                         }
 620                                 }
 621                         }
 622                 }
 623                 /* Required properties */
 624                 if (ret && need_unique) {
 625                         ret = ucl_schema_array_is_unique (obj, err);
 626                 }
 627         }
 628
 629         return ret;
 630 }
 631
 632 /*
 633  * Returns whether this object is allowed for this type
 634  */
 635 static bool
 636 ucl_schema_type_is_allowed (const ucl_object_t *type, const ucl_object_t *obj,
 637                 struct ucl_schema_error *err)
 638 {
 639         ucl_object_iter_t iter = NULL;
 640         const ucl_object_t *elt;
 641         const char *type_str;
 642         ucl_type_t t;
 643
 644         if (type == NULL) {
 645                 /* Any type is allowed */
 646                 return true;
 647         }
 648
 649         if (type->type == UCL_ARRAY) {
 650                 /* One of allowed types */
 651                 while ((elt = ucl_iterate_object (type, &iter, true)) != NULL) {
 652                         if (ucl_schema_type_is_allowed (elt, obj, err)) {
 653                                 return true;
 654                         }
 655                 }
 656         }
 657         else if (type->type == UCL_STRING) {
 658                 type_str = ucl_object_tostring (type);
 659                 if (!ucl_string_to_type (type_str, &t)) {
 660                         ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, type,
 661                                         "Type attribute is invalid in schema");
 662                         return false;
 663                 }
 664                 if (obj->type != t) {
 665                         /* Some types are actually compatible */
 666                         if (obj->type == UCL_TIME && t == UCL_FLOAT) {
 667                                 return true;
 668                         }
 669                         else if (obj->type == UCL_INT && t == UCL_FLOAT) {
 670                                 return true;
 671                         }
 672                         else {
 673                                 ucl_schema_create_error (err, UCL_SCHEMA_TYPE_MISMATCH, obj,
 674                                                 "Invalid type of %s, expected %s",
 675                                                 ucl_object_type_to_string (obj->type),
 676                                                 ucl_object_type_to_string (t));
 677                         }
 678                 }
 679                 else {
 680                         /* Types are equal */
 681                         return true;
 682                 }
 683         }
 684
 685         return false;
 686 }
 687
 688 /*
 689  * Check if object is equal to one of elements of enum
 690  */
 691 static bool
 692 ucl_schema_validate_enum (const ucl_object_t *en, const ucl_object_t *obj,
 693                 struct ucl_schema_error *err)
 694 {
 695         ucl_object_iter_t iter = NULL;
 696         const ucl_object_t *elt;
 697         bool ret = false;
 698
 699         while ((elt = ucl_iterate_object (en, &iter, true)) != NULL) {
 700                 if (ucl_object_compare (elt, obj) == 0) {
 701                         ret = true;
 702                         break;
 703                 }
 704         }
 705
 706         if (!ret) {
 707                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 708                                 "object is not one of enumerated patterns");
 709         }
 710
 711         return ret;
 712 }
 713
 714
 715 /*
 716  * Check a single ref component
 717  */
 718 static const ucl_object_t *
 719 ucl_schema_resolve_ref_component (const ucl_object_t *cur,
 720                 const char *refc, int len,
 721                 struct ucl_schema_error *err)
 722 {
 723         const ucl_object_t *res = NULL;
 724         char *err_str;
 725         int num, i;
 726
 727         if (cur->type == UCL_OBJECT) {
 728                 /* Find a key inside an object */
 729                 res = ucl_object_find_keyl (cur, refc, len);
 730                 if (res == NULL) {
 731                         ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, cur,
 732                                         "reference %s is invalid, missing path component", refc);
 733                         return NULL;
 734                 }
 735         }
 736         else if (cur->type == UCL_ARRAY) {
 737                 /* We must figure out a number inside array */
 738                 num = strtoul (refc, &err_str, 10);
 739                 if (err_str != NULL && *err_str != '/' && *err_str != '\0') {
 740                         ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, cur,
 741                                         "reference %s is invalid, invalid item number", refc);
 742                         return NULL;
 743                 }
 744                 res = cur->value.av;
 745                 i = 0;
 746                 while (res != NULL) {
 747                         if (i == num) {
 748                                 break;
 749                         }
 750                         res = res->next;
 751                 }
 752                 if (res == NULL) {
 753                         ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, cur,
 754                                         "reference %s is invalid, item number %d does not exist",
 755                                         refc, num);
 756                         return NULL;
 757                 }
 758         }
 759         else {
 760                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, res,
 761                                 "reference %s is invalid, contains primitive object in the path",
 762                                 refc);
 763                 return NULL;
 764         }
 765
 766         return res;
 767 }
 768 /*
 769  * Find reference schema
 770  */
 771 static const ucl_object_t *
 772 ucl_schema_resolve_ref (const ucl_object_t *root, const char *ref,
 773                 struct ucl_schema_error *err)
 774 {
 775         const char *p, *c;
 776         const ucl_object_t *res = NULL;
 777
 778
 779         if (ref[0] != '#') {
 780                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, root,
 781                                 "reference %s is invalid, not started with #", ref);
 782                 return NULL;
 783         }
 784         if (ref[1] == '/') {
 785                 p = &ref[2];
 786         }
 787         else if (ref[1] == '\0') {
 788                 return root;
 789         }
 790         else {
 791                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, root,
 792                                 "reference %s is invalid, not started with #/", ref);
 793                 return NULL;
 794         }
 795
 796         c = p;
 797         res = root;
 798
 799         while (*p != '\0') {
 800                 if (*p == '/') {
 801                         if (p - c == 0) {
 802                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, res,
 803                                                 "reference %s is invalid, empty path component", ref);
 804                                 return NULL;
 805                         }
 806                         /* Now we have some url part, so we need to figure out where we are */
 807                         res = ucl_schema_resolve_ref_component (res, c, p - c, err);
 808                         if (res == NULL) {
 809                                 return NULL;
 810                         }
 811                         c = p + 1;
 812                 }
 813                 p ++;
 814         }
 815
 816         if (p - c != 0) {
 817                 res = ucl_schema_resolve_ref_component (res, c, p - c, err);
 818         }
 819
 820         if (res == NULL || res->type != UCL_OBJECT) {
 821                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, res,
 822                                 "reference %s is invalid, cannot find specified object",
 823                                 ref);
 824                 return NULL;
 825         }
 826
 827         return res;
 828 }
 829
 830 static bool
 831 ucl_schema_validate_values (const ucl_object_t *schema, const ucl_object_t *obj,
 832                 struct ucl_schema_error *err)
 833 {
 834         const ucl_object_t *elt, *cur;
 835         int64_t constraint, i;
 836
 837         elt = ucl_object_find_key (schema, "maxValues");
 838         if (elt != NULL && elt->type == UCL_INT) {
 839                 constraint = ucl_object_toint (elt);
 840                 cur = obj;
 841                 i = 0;
 842                 while (cur) {
 843                         if (i > constraint) {
 844                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 845                                         "object has more values than defined: %ld",
 846                                         (long int)constraint);
 847                                 return false;
 848                         }
 849                         i ++;
 850                         cur = cur->next;
 851                 }
 852         }
 853         elt = ucl_object_find_key (schema, "minValues");
 854         if (elt != NULL && elt->type == UCL_INT) {
 855                 constraint = ucl_object_toint (elt);
 856                 cur = obj;
 857                 i = 0;
 858                 while (cur) {
 859                         if (i >= constraint) {
 860                                 break;
 861                         }
 862                         i ++;
 863                         cur = cur->next;
 864                 }
 865                 if (i < constraint) {
 866                         ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 867                                         "object has less values than defined: %ld",
 868                                         (long int)constraint);
 869                         return false;
 870                 }
 871         }
 872
 873         return true;
 874 }
 875
 876 static bool
 877 ucl_schema_validate (const ucl_object_t *schema,
 878                 const ucl_object_t *obj, bool try_array,
 879                 struct ucl_schema_error *err,
 880                 const ucl_object_t *root)
 881 {
 882         const ucl_object_t *elt, *cur;
 883         ucl_object_iter_t iter = NULL;
 884         bool ret;
 885
 886         if (schema->type != UCL_OBJECT) {
 887                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, schema,
 888                                 "schema is %s instead of object", ucl_object_type_to_string (schema->type));
 889                 return false;
 890         }
 891
 892         if (try_array) {
 893                 /*
 894                  * Special case for multiple values
 895                  */
 896                 if (!ucl_schema_validate_values (schema, obj, err)) {
 897                         return false;
 898                 }
 899                 LL_FOREACH (obj, cur) {
 900                         if (!ucl_schema_validate (schema, cur, false, err, root)) {
 901                                 return false;
 902                         }
 903                 }
 904                 return true;
 905         }
 906
 907         elt = ucl_object_find_key (schema, "enum");
 908         if (elt != NULL && elt->type == UCL_ARRAY) {
 909                 if (!ucl_schema_validate_enum (elt, obj, err)) {
 910                         return false;
 911                 }
 912         }
 913
 914         elt = ucl_object_find_key (schema, "allOf");
 915         if (elt != NULL && elt->type == UCL_ARRAY) {
 916                 iter = NULL;
 917                 while ((cur = ucl_iterate_object (elt, &iter, true)) != NULL) {
 918                         ret = ucl_schema_validate (cur, obj, true, err, root);
 919                         if (!ret) {
 920                                 return false;
 921                         }
 922                 }
 923         }
 924
 925         elt = ucl_object_find_key (schema, "anyOf");
 926         if (elt != NULL && elt->type == UCL_ARRAY) {
 927                 iter = NULL;
 928                 while ((cur = ucl_iterate_object (elt, &iter, true)) != NULL) {
 929                         ret = ucl_schema_validate (cur, obj, true, err, root);
 930                         if (ret) {
 931                                 break;
 932                         }
 933                 }
 934                 if (!ret) {
 935                         return false;
 936                 }
 937                 else {
 938                         /* Reset error */
 939                         err->code = UCL_SCHEMA_OK;
 940                 }
 941         }
 942
 943         elt = ucl_object_find_key (schema, "oneOf");
 944         if (elt != NULL && elt->type == UCL_ARRAY) {
 945                 iter = NULL;
 946                 ret = false;
 947                 while ((cur = ucl_iterate_object (elt, &iter, true)) != NULL) {
 948                         if (!ret) {
 949                                 ret = ucl_schema_validate (cur, obj, true, err, root);
 950                         }
 951                         else if (ucl_schema_validate (cur, obj, true, err, root)) {
 952                                 ret = false;
 953                                 break;
 954                         }
 955                 }
 956                 if (!ret) {
 957                         return false;
 958                 }
 959         }
 960
 961         elt = ucl_object_find_key (schema, "not");
 962         if (elt != NULL && elt->type == UCL_OBJECT) {
 963                 if (ucl_schema_validate (elt, obj, true, err, root)) {
 964                         return false;
 965                 }
 966                 else {
 967                         /* Reset error */
 968                         err->code = UCL_SCHEMA_OK;
 969                 }
 970         }
 971
 972         elt = ucl_object_find_key (schema, "$ref");
 973         if (elt != NULL) {
 974                 cur = ucl_schema_resolve_ref (root, ucl_object_tostring (elt), err);
 975                 if (cur == NULL) {
 976                         return false;
 977                 }
 978                 if (!ucl_schema_validate (cur, obj, try_array, err, root)) {
 979                         return false;
 980                 }
 981         }
 982
 983         elt = ucl_object_find_key (schema, "type");
 984         if (!ucl_schema_type_is_allowed (elt, obj, err)) {
 985                 return false;
 986         }
 987
 988         switch (obj->type) {
 989         case UCL_OBJECT:
 990                 return ucl_schema_validate_object (schema, obj, err, root);
 991                 break;
 992         case UCL_ARRAY:
 993                 return ucl_schema_validate_array (schema, obj, err, root);
 994                 break;
 995         case UCL_INT:
 996         case UCL_FLOAT:
 997                 return ucl_schema_validate_number (schema, obj, err);
 998                 break;
 999         case UCL_STRING:
1000                 return ucl_schema_validate_string (schema, obj, err);
1001                 break;
1002         default:
1003                 break;
1004         }
1005
1006         return true;
1007 }
1008
1009 bool
1010 ucl_object_validate (const ucl_object_t *schema,
1011                 const ucl_object_t *obj, struct ucl_schema_error *err)
1012 {
1013         return ucl_schema_validate (schema, obj, true, err, schema);
1014 }