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