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         unsigned int idx = 0;
 529
 530         while (ret && (elt = ucl_iterate_object (schema, &iter, true)) != NULL) {
 531                 if (strcmp (ucl_object_key (elt), "items") == 0) {
 532                         if (elt->type == UCL_ARRAY) {
 533                                 found = ucl_array_head (obj);
 534                                 while (ret && (it = ucl_iterate_object (elt, &piter, true)) != NULL) {
 535                                         if (found) {
 536                                                 ret = ucl_schema_validate (it, found, false, err, root);
 537                                                 found = ucl_array_find_index (obj, ++idx);
 538                                         }
 539                                 }
 540                                 if (found != NULL) {
 541                                         /* The first element that is not validated */
 542                                         first_unvalidated = found;
 543                                 }
 544                         }
 545                         else if (elt->type == UCL_OBJECT) {
 546                                 /* Validate all items using the specified schema */
 547                                 while (ret && (it = ucl_iterate_object (obj, &piter, true)) != NULL) {
 548                                         ret = ucl_schema_validate (elt, it, false, err, root);
 549                                 }
 550                         }
 551                         else {
 552                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, elt,
 553                                                 "items attribute is invalid in schema");
 554                                 ret = false;
 555                                 break;
 556                         }
 557                 }
 558                 else if (strcmp (ucl_object_key (elt), "additionalItems") == 0) {
 559                         if (elt->type == UCL_BOOLEAN) {
 560                                 if (!ucl_object_toboolean (elt)) {
 561                                         /* Deny additional fields completely */
 562                                         allow_additional = false;
 563                                 }
 564                         }
 565                         else if (elt->type == UCL_OBJECT) {
 566                                 /* Define validator for additional fields */
 567                                 additional_schema = elt;
 568                         }
 569                         else {
 570                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, elt,
 571                                                 "additionalItems attribute is invalid in schema");
 572                                 ret = false;
 573                                 break;
 574                         }
 575                 }
 576                 else if (elt->type == UCL_BOOLEAN &&
 577                                 strcmp (ucl_object_key (elt), "uniqueItems") == 0) {
 578                         need_unique = ucl_object_toboolean (elt);
 579                 }
 580                 else if (strcmp (ucl_object_key (elt), "minItems") == 0
 581                                 && ucl_object_toint_safe (elt, &minmax)) {
 582                         if (obj->len < minmax) {
 583                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 584                                                 "array has not enough items: %u, minimum is: %u",
 585                                                 obj->len, (unsigned)minmax);
 586                                 ret = false;
 587                                 break;
 588                         }
 589                 }
 590                 else if (strcmp (ucl_object_key (elt), "maxItems") == 0
 591                                 && ucl_object_toint_safe (elt, &minmax)) {
 592                         if (obj->len > minmax) {
 593                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 594                                                 "array has too many items: %u, maximum is: %u",
 595                                                 obj->len, (unsigned)minmax);
 596                                 ret = false;
 597                                 break;
 598                         }
 599                 }
 600         }
 601
 602         if (ret) {
 603                 /* Additional properties */
 604                 if (!allow_additional || additional_schema != NULL) {
 605                         if (first_unvalidated != NULL) {
 606                                 if (!allow_additional) {
 607                                         ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 608                                                         "array has undefined item");
 609                                         ret = false;
 610                                 }
 611                                 else if (additional_schema != NULL) {
 612                                         elt = ucl_array_find_index (obj, idx);
 613                                         while (elt) {
 614                                                 if (!ucl_schema_validate (additional_schema, elt, false,
 615                                                                 err, root)) {
 616                                                         ret = false;
 617                                                         break;
 618                                                 }
 619                                                 elt = ucl_array_find_index (obj, idx ++);
 620                                         }
 621                                 }
 622                         }
 623                 }
 624                 /* Required properties */
 625                 if (ret && need_unique) {
 626                         ret = ucl_schema_array_is_unique (obj, err);
 627                 }
 628         }
 629
 630         return ret;
 631 }
 632
 633 /*
 634  * Returns whether this object is allowed for this type
 635  */
 636 static bool
 637 ucl_schema_type_is_allowed (const ucl_object_t *type, const ucl_object_t *obj,
 638                 struct ucl_schema_error *err)
 639 {
 640         ucl_object_iter_t iter = NULL;
 641         const ucl_object_t *elt;
 642         const char *type_str;
 643         ucl_type_t t;
 644
 645         if (type == NULL) {
 646                 /* Any type is allowed */
 647                 return true;
 648         }
 649
 650         if (type->type == UCL_ARRAY) {
 651                 /* One of allowed types */
 652                 while ((elt = ucl_iterate_object (type, &iter, true)) != NULL) {
 653                         if (ucl_schema_type_is_allowed (elt, obj, err)) {
 654                                 return true;
 655                         }
 656                 }
 657         }
 658         else if (type->type == UCL_STRING) {
 659                 type_str = ucl_object_tostring (type);
 660                 if (!ucl_string_to_type (type_str, &t)) {
 661                         ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, type,
 662                                         "Type attribute is invalid in schema");
 663                         return false;
 664                 }
 665                 if (obj->type != t) {
 666                         /* Some types are actually compatible */
 667                         if (obj->type == UCL_TIME && t == UCL_FLOAT) {
 668                                 return true;
 669                         }
 670                         else if (obj->type == UCL_INT && t == UCL_FLOAT) {
 671                                 return true;
 672                         }
 673                         else {
 674                                 ucl_schema_create_error (err, UCL_SCHEMA_TYPE_MISMATCH, obj,
 675                                                 "Invalid type of %s, expected %s",
 676                                                 ucl_object_type_to_string (obj->type),
 677                                                 ucl_object_type_to_string (t));
 678                         }
 679                 }
 680                 else {
 681                         /* Types are equal */
 682                         return true;
 683                 }
 684         }
 685
 686         return false;
 687 }
 688
 689 /*
 690  * Check if object is equal to one of elements of enum
 691  */
 692 static bool
 693 ucl_schema_validate_enum (const ucl_object_t *en, const ucl_object_t *obj,
 694                 struct ucl_schema_error *err)
 695 {
 696         ucl_object_iter_t iter = NULL;
 697         const ucl_object_t *elt;
 698         bool ret = false;
 699
 700         while ((elt = ucl_iterate_object (en, &iter, true)) != NULL) {
 701                 if (ucl_object_compare (elt, obj) == 0) {
 702                         ret = true;
 703                         break;
 704                 }
 705         }
 706
 707         if (!ret) {
 708                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 709                                 "object is not one of enumerated patterns");
 710         }
 711
 712         return ret;
 713 }
 714
 715
 716 /*
 717  * Check a single ref component
 718  */
 719 static const ucl_object_t *
 720 ucl_schema_resolve_ref_component (const ucl_object_t *cur,
 721                 const char *refc, int len,
 722                 struct ucl_schema_error *err)
 723 {
 724         const ucl_object_t *res = NULL;
 725         char *err_str;
 726         int num, i;
 727
 728         if (cur->type == UCL_OBJECT) {
 729                 /* Find a key inside an object */
 730                 res = ucl_object_find_keyl (cur, refc, len);
 731                 if (res == NULL) {
 732                         ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, cur,
 733                                         "reference %s is invalid, missing path component", refc);
 734                         return NULL;
 735                 }
 736         }
 737         else if (cur->type == UCL_ARRAY) {
 738                 /* We must figure out a number inside array */
 739                 num = strtoul (refc, &err_str, 10);
 740                 if (err_str != NULL && *err_str != '/' && *err_str != '\0') {
 741                         ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, cur,
 742                                         "reference %s is invalid, invalid item number", refc);
 743                         return NULL;
 744                 }
 745                 res = ucl_array_head (cur);
 746                 i = 0;
 747                 while (res != NULL) {
 748                         if (i == num) {
 749                                 break;
 750                         }
 751                         res = res->next;
 752                 }
 753                 if (res == NULL) {
 754                         ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, cur,
 755                                         "reference %s is invalid, item number %d does not exist",
 756                                         refc, num);
 757                         return NULL;
 758                 }
 759         }
 760         else {
 761                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, res,
 762                                 "reference %s is invalid, contains primitive object in the path",
 763                                 refc);
 764                 return NULL;
 765         }
 766
 767         return res;
 768 }
 769 /*
 770  * Find reference schema
 771  */
 772 static const ucl_object_t *
 773 ucl_schema_resolve_ref (const ucl_object_t *root, const char *ref,
 774                 struct ucl_schema_error *err)
 775 {
 776         const char *p, *c;
 777         const ucl_object_t *res = NULL;
 778
 779
 780         if (ref[0] != '#') {
 781                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, root,
 782                                 "reference %s is invalid, not started with #", ref);
 783                 return NULL;
 784         }
 785         if (ref[1] == '/') {
 786                 p = &ref[2];
 787         }
 788         else if (ref[1] == '\0') {
 789                 return root;
 790         }
 791         else {
 792                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, root,
 793                                 "reference %s is invalid, not started with #/", ref);
 794                 return NULL;
 795         }
 796
 797         c = p;
 798         res = root;
 799
 800         while (*p != '\0') {
 801                 if (*p == '/') {
 802                         if (p - c == 0) {
 803                                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, res,
 804                                                 "reference %s is invalid, empty path component", ref);
 805                                 return NULL;
 806                         }
 807                         /* Now we have some url part, so we need to figure out where we are */
 808                         res = ucl_schema_resolve_ref_component (res, c, p - c, err);
 809                         if (res == NULL) {
 810                                 return NULL;
 811                         }
 812                         c = p + 1;
 813                 }
 814                 p ++;
 815         }
 816
 817         if (p - c != 0) {
 818                 res = ucl_schema_resolve_ref_component (res, c, p - c, err);
 819         }
 820
 821         if (res == NULL || res->type != UCL_OBJECT) {
 822                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, res,
 823                                 "reference %s is invalid, cannot find specified object",
 824                                 ref);
 825                 return NULL;
 826         }
 827
 828         return res;
 829 }
 830
 831 static bool
 832 ucl_schema_validate_values (const ucl_object_t *schema, const ucl_object_t *obj,
 833                 struct ucl_schema_error *err)
 834 {
 835         const ucl_object_t *elt, *cur;
 836         int64_t constraint, i;
 837
 838         elt = ucl_object_find_key (schema, "maxValues");
 839         if (elt != NULL && elt->type == UCL_INT) {
 840                 constraint = ucl_object_toint (elt);
 841                 cur = obj;
 842                 i = 0;
 843                 while (cur) {
 844                         if (i > constraint) {
 845                                 ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 846                                         "object has more values than defined: %ld",
 847                                         (long int)constraint);
 848                                 return false;
 849                         }
 850                         i ++;
 851                         cur = cur->next;
 852                 }
 853         }
 854         elt = ucl_object_find_key (schema, "minValues");
 855         if (elt != NULL && elt->type == UCL_INT) {
 856                 constraint = ucl_object_toint (elt);
 857                 cur = obj;
 858                 i = 0;
 859                 while (cur) {
 860                         if (i >= constraint) {
 861                                 break;
 862                         }
 863                         i ++;
 864                         cur = cur->next;
 865                 }
 866                 if (i < constraint) {
 867                         ucl_schema_create_error (err, UCL_SCHEMA_CONSTRAINT, obj,
 868                                         "object has less values than defined: %ld",
 869                                         (long int)constraint);
 870                         return false;
 871                 }
 872         }
 873
 874         return true;
 875 }
 876
 877 static bool
 878 ucl_schema_validate (const ucl_object_t *schema,
 879                 const ucl_object_t *obj, bool try_array,
 880                 struct ucl_schema_error *err,
 881                 const ucl_object_t *root)
 882 {
 883         const ucl_object_t *elt, *cur;
 884         ucl_object_iter_t iter = NULL;
 885         bool ret;
 886
 887         if (schema->type != UCL_OBJECT) {
 888                 ucl_schema_create_error (err, UCL_SCHEMA_INVALID_SCHEMA, schema,
 889                                 "schema is %s instead of object", ucl_object_type_to_string (schema->type));
 890                 return false;
 891         }
 892
 893         if (try_array) {
 894                 /*
 895                  * Special case for multiple values
 896                  */
 897                 if (!ucl_schema_validate_values (schema, obj, err)) {
 898                         return false;
 899                 }
 900                 LL_FOREACH (obj, cur) {
 901                         if (!ucl_schema_validate (schema, cur, false, err, root)) {
 902                                 return false;
 903                         }
 904                 }
 905                 return true;
 906         }
 907
 908         elt = ucl_object_find_key (schema, "enum");
 909         if (elt != NULL && elt->type == UCL_ARRAY) {
 910                 if (!ucl_schema_validate_enum (elt, obj, err)) {
 911                         return false;
 912                 }
 913         }
 914
 915         elt = ucl_object_find_key (schema, "allOf");
 916         if (elt != NULL && elt->type == UCL_ARRAY) {
 917                 iter = NULL;
 918                 while ((cur = ucl_iterate_object (elt, &iter, true)) != NULL) {
 919                         ret = ucl_schema_validate (cur, obj, true, err, root);
 920                         if (!ret) {
 921                                 return false;
 922                         }
 923                 }
 924         }
 925
 926         elt = ucl_object_find_key (schema, "anyOf");
 927         if (elt != NULL && elt->type == UCL_ARRAY) {
 928                 iter = NULL;
 929                 while ((cur = ucl_iterate_object (elt, &iter, true)) != NULL) {
 930                         ret = ucl_schema_validate (cur, obj, true, err, root);
 931                         if (ret) {
 932                                 break;
 933                         }
 934                 }
 935                 if (!ret) {
 936                         return false;
 937                 }
 938                 else {
 939                         /* Reset error */
 940                         err->code = UCL_SCHEMA_OK;
 941                 }
 942         }
 943
 944         elt = ucl_object_find_key (schema, "oneOf");
 945         if (elt != NULL && elt->type == UCL_ARRAY) {
 946                 iter = NULL;
 947                 ret = false;
 948                 while ((cur = ucl_iterate_object (elt, &iter, true)) != NULL) {
 949                         if (!ret) {
 950                                 ret = ucl_schema_validate (cur, obj, true, err, root);
 951                         }
 952                         else if (ucl_schema_validate (cur, obj, true, err, root)) {
 953                                 ret = false;
 954                                 break;
 955                         }
 956                 }
 957                 if (!ret) {
 958                         return false;
 959                 }
 960         }
 961
 962         elt = ucl_object_find_key (schema, "not");
 963         if (elt != NULL && elt->type == UCL_OBJECT) {
 964                 if (ucl_schema_validate (elt, obj, true, err, root)) {
 965                         return false;
 966                 }
 967                 else {
 968                         /* Reset error */
 969                         err->code = UCL_SCHEMA_OK;
 970                 }
 971         }
 972
 973         elt = ucl_object_find_key (schema, "$ref");
 974         if (elt != NULL) {
 975                 cur = ucl_schema_resolve_ref (root, ucl_object_tostring (elt), err);
 976                 if (cur == NULL) {
 977                         return false;
 978                 }
 979                 if (!ucl_schema_validate (cur, obj, try_array, err, root)) {
 980                         return false;
 981                 }
 982         }
 983
 984         elt = ucl_object_find_key (schema, "type");
 985         if (!ucl_schema_type_is_allowed (elt, obj, err)) {
 986                 return false;
 987         }
 988
 989         switch (obj->type) {
 990         case UCL_OBJECT:
 991                 return ucl_schema_validate_object (schema, obj, err, root);
 992                 break;
 993         case UCL_ARRAY:
 994                 return ucl_schema_validate_array (schema, obj, err, root);
 995                 break;
 996         case UCL_INT:
 997         case UCL_FLOAT:
 998                 return ucl_schema_validate_number (schema, obj, err);
 999                 break;
1000         case UCL_STRING:
1001                 return ucl_schema_validate_string (schema, obj, err);
1002                 break;
1003         default:
1004                 break;
1005         }
1006
1007         return true;
1008 }
1009
1010 bool
1011 ucl_object_validate (const ucl_object_t *schema,
1012                 const ucl_object_t *obj, struct ucl_schema_error *err)
1013 {
1014         return ucl_schema_validate (schema, obj, true, err, schema);
1015 }