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