validate/validate.c

   1 /*
   2  * Copyright (C) 2013 Jo-Philipp Wich <jow@openwrt.org>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2.1
   6  * as published by the Free Software Foundation
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU General Public License for more details.
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include <stdbool.h>
  18 #include <ctype.h>
  19
  20 #include <arpa/inet.h>
  21 #include <netinet/ether.h>
  22 #include <sys/stat.h>
  23
  24 #include "libvalidate.h"
  25
  26 enum dt_optype {
  27         OP_UNKNOWN,
  28         OP_NUMBER,
  29         OP_STRING,
  30         OP_FUNCTION
  31 };
  32
  33 struct dt_fun;
  34
  35 struct dt_op {
  36         enum dt_optype type;
  37         const char *next;
  38         int length;
  39         int nextop;
  40         union {
  41                 bool boolean;
  42                 double number;
  43                 const char *string;
  44                 struct dt_fun *function;
  45         } value;
  46 };
  47
  48 struct dt_state {
  49         int pos;
  50         int depth;
  51         const char *value;
  52         enum dt_type valtype;
  53         struct dt_op stack[32];
  54 };
  55
  56 struct dt_fun {
  57         const char *name;
  58         enum dt_type valtype;
  59         bool (*call)(struct dt_state *s, int nargs);
  60 };
  61
  62 static bool
  63 dt_test_number(double number, const char *value)
  64 {
  65         char *e;
  66         double n;
  67
  68         n = strtod(value, &e);
  69
  70         return (e > value && *e == 0 && n == number);
  71 }
  72
  73 static bool
  74 dt_test_string(const char *s, const char *end, const char *value)
  75 {
  76         bool esc = false;
  77
  78         while (*value)
  79         {
  80                 if (s > end)
  81                         return false;
  82
  83                 if (!esc && *s == '\\')
  84                 {
  85                         s++;
  86
  87                         if (s >= end)
  88                                 break;
  89
  90                         esc = true;
  91                         continue;
  92                 }
  93
  94                 if (*s != *value)
  95                         return false;
  96
  97                 esc = false;
  98                 value++;
  99                 s++;
 100         }
 101
 102         return (*s == *value || (s >= end && *value == 0));
 103 }
 104
 105 static bool
 106 dt_step(struct dt_state *s);
 107
 108 static bool
 109 dt_call(struct dt_state *s);
 110
 111 static bool
 112 dt_type_or(struct dt_state *s, int nargs)
 113 {
 114         while (nargs--)
 115                 if (dt_step(s))
 116                         return true;
 117
 118         return false;
 119 }
 120
 121 static bool
 122 dt_type_and(struct dt_state *s, int nargs)
 123 {
 124         while (nargs--)
 125                 if (!dt_step(s))
 126                         return false;
 127
 128         return true;
 129 }
 130
 131 static bool
 132 dt_type_not(struct dt_state *s, int nargs)
 133 {
 134         if (!nargs)
 135                 return false;
 136
 137         return !dt_step(s);
 138 }
 139
 140 static bool
 141 dt_type_neg(struct dt_state *s, int nargs)
 142 {
 143         bool rv;
 144         const char *value = s->value;
 145
 146         if (!nargs)
 147                 return false;
 148
 149         if (*s->value == '!')
 150                 while (isspace(*++s->value));
 151
 152         rv = dt_step(s);
 153         s->value = value;
 154
 155         return rv;
 156 }
 157
 158 static bool
 159 dt_type_list(struct dt_state *s, int nargs)
 160 {
 161         bool rv = true;
 162         int pos = s->pos;
 163         char *p, *str = strdup(s->value);
 164         const char *value = s->value;
 165
 166         if (!str || !nargs)
 167                 return false;
 168
 169         for (p = strtok(str, " \t"); p; p = strtok(NULL, " \t"))
 170         {
 171                 s->value = p;
 172
 173                 if (!dt_step(s))
 174                 {
 175                         rv = false;
 176                         break;
 177                 }
 178
 179                 s->pos = pos;
 180         }
 181
 182         s->value = value;
 183         free(str);
 184
 185         return rv;
 186 }
 187
 188 static bool
 189 dt_type_min(struct dt_state *s, int nargs)
 190 {
 191         int n;
 192         char *e;
 193
 194         if (nargs >= 1 && s->stack[s->pos].type == OP_NUMBER)
 195         {
 196                 n = strtol(s->value, &e, 0);
 197
 198                 return (e > s->value && *e == 0 &&
 199                         n >= s->stack[s->pos].value.number);
 200         }
 201
 202         return false;
 203 }
 204
 205 static bool
 206 dt_type_max(struct dt_state *s, int nargs)
 207 {
 208         int n;
 209         char *e;
 210
 211         if (nargs >= 1 && s->stack[s->pos].type == OP_NUMBER)
 212         {
 213                 n = strtol(s->value, &e, 0);
 214
 215                 return (e > s->value && *e == 0 &&
 216                         n <= s->stack[s->pos].value.number);
 217         }
 218
 219         return false;
 220 }
 221
 222 static bool
 223 dt_type_range(struct dt_state *s, int nargs)
 224 {
 225         int n;
 226         char *e;
 227
 228         if (nargs >= 2 &&
 229             s->stack[s->pos].type == OP_NUMBER &&
 230             s->stack[s->pos + 1].type == OP_NUMBER)
 231         {
 232                 n = strtol(s->value, &e, 0);
 233
 234                 return (e > s->value && *e == 0 &&
 235                         n >= s->stack[s->pos].value.number &&
 236                         n <= s->stack[s->pos + 1].value.number);
 237         }
 238
 239         return false;
 240 }
 241
 242 static bool
 243 dt_type_minlen(struct dt_state *s, int nargs)
 244 {
 245         if (nargs >= 1 && s->stack[s->pos].type == OP_NUMBER)
 246                 return (strlen(s->value) >= s->stack[s->pos].value.number);
 247
 248         return false;
 249 }
 250
 251 static bool
 252 dt_type_maxlen(struct dt_state *s, int nargs)
 253 {
 254         if (nargs >= 1 && s->stack[s->pos].type == OP_NUMBER)
 255                 return (strlen(s->value) <= s->stack[s->pos].value.number);
 256
 257         return false;
 258 }
 259
 260 static bool
 261 dt_type_rangelen(struct dt_state *s, int nargs)
 262 {
 263         if (nargs >= 2 &&
 264             s->stack[s->pos].type == OP_NUMBER &&
 265             s->stack[s->pos + 1].type == OP_NUMBER)
 266                 return (strlen(s->value) >= s->stack[s->pos].value.number &&
 267                                 strlen(s->value) <= s->stack[s->pos + 1].value.number);
 268
 269         return false;
 270 }
 271
 272 static bool
 273 dt_type_int(struct dt_state *s, int nargs)
 274 {
 275         char *e;
 276
 277         strtol(s->value, &e, 0);
 278
 279         return (e > s->value && *e == 0);
 280 }
 281
 282 static bool
 283 dt_type_uint(struct dt_state *s, int nargs)
 284 {
 285         int n;
 286         char *e;
 287
 288         n = strtol(s->value, &e, 0);
 289
 290         return (e > s->value && *e == 0 && n >= 0);
 291 }
 292
 293 static bool
 294 dt_type_float(struct dt_state *s, int nargs)
 295 {
 296         char *e;
 297
 298         strtod(s->value, &e);
 299
 300         return (e > s->value && *e == 0);
 301 }
 302
 303 static bool
 304 dt_type_ufloat(struct dt_state *s, int nargs)
 305 {
 306         int n;
 307         char *e;
 308
 309         n = strtod(s->value, &e);
 310
 311         return (e > s->value && *e == 0 && n >= 0.0);
 312 }
 313
 314 static bool
 315 dt_type_bool(struct dt_state *s, int nargs)
 316 {
 317         int i;
 318         const char *values[] = {
 319                 "0", "off", "false", "no",
 320                 "1", "on", "true", "yes"
 321         };
 322
 323         for (i = 0; i < sizeof(values) / sizeof(values[0]); i++)
 324                 if (!strcasecmp(values[i], s->value))
 325                         return true;
 326
 327         return false;
 328 }
 329
 330 static bool
 331 dt_type_string(struct dt_state *s, int nargs)
 332 {
 333         return true;
 334 }
 335
 336 static bool
 337 dt_type_ip4addr(struct dt_state *s, int nargs)
 338 {
 339         struct in6_addr a;
 340         return inet_pton(AF_INET, s->value, &a);
 341 }
 342
 343 static bool
 344 dt_type_ip6addr(struct dt_state *s, int nargs)
 345 {
 346         struct in6_addr a;
 347         return inet_pton(AF_INET6, s->value, &a);
 348 }
 349
 350 static bool
 351 dt_type_ipaddr(struct dt_state *s, int nargs)
 352 {
 353         return (dt_type_ip4addr(s, 0) || dt_type_ip6addr(s, 0));
 354 }
 355
 356 static bool
 357 dt_type_netmask4(struct dt_state *s, int nargs)
 358 {
 359         int i;
 360         struct in_addr a;
 361
 362         if (!inet_pton(AF_INET, s->value, &a))
 363                 return false;
 364
 365         if (a.s_addr == 0)
 366                 return true;
 367
 368         a.s_addr = ntohl(a.s_addr);
 369
 370         for (i = 0; (i < 32) && !(a.s_addr & (1 << i)); i++);
 371
 372         return ((uint32_t)(~((1 << i) - 1)) == a.s_addr);
 373 }
 374
 375 static bool
 376 dt_type_netmask6(struct dt_state *s, int nargs)
 377 {
 378         int i;
 379         struct in6_addr a;
 380
 381         if (!inet_pton(AF_INET6, s->value, &a))
 382                 return false;
 383
 384         for (i = 0; (i < 16) && (a.s6_addr[i] == 0xFF); i++);
 385
 386         if (i == 16)
 387                 return true;
 388
 389         if ((a.s6_addr[i] != 255) && (a.s6_addr[i] != 254) &&
 390                 (a.s6_addr[i] != 252) && (a.s6_addr[i] != 248) &&
 391                 (a.s6_addr[i] != 240) && (a.s6_addr[i] != 224) &&
 392                 (a.s6_addr[i] != 192) && (a.s6_addr[i] != 128) &&
 393                 (a.s6_addr[i] != 0))
 394                 return false;
 395
 396         for (; (i < 16) && (a.s6_addr[i] == 0); i++);
 397
 398         return (i == 16);
 399 }
 400
 401 static bool
 402 dt_type_cidr4(struct dt_state *s, int nargs)
 403 {
 404         int n;
 405         struct in_addr a;
 406         char *p, buf[sizeof("255.255.255.255/32\0")];
 407
 408         if (strlen(s->value) >= sizeof(buf))
 409                 return false;
 410
 411         strcpy(buf, s->value);
 412         p = strchr(buf, '/');
 413
 414         if (p)
 415         {
 416                 *p++ = 0;
 417
 418                 n = strtoul(p, &p, 10);
 419
 420                 if ((*p != 0) || (n > 32))
 421                         return false;
 422         }
 423
 424         return inet_pton(AF_INET, buf, &a);
 425 }
 426
 427 static bool
 428 dt_type_cidr6(struct dt_state *s, int nargs)
 429 {
 430         int n;
 431         struct in6_addr a;
 432         char *p, buf[sizeof("FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:255.255.255.255/128\0")];
 433
 434         if (strlen(s->value) >= sizeof(buf))
 435                 return false;
 436
 437         strcpy(buf, s->value);
 438         p = strchr(buf, '/');
 439
 440         if (p)
 441         {
 442                 *p++ = 0;
 443
 444                 n = strtoul(p, &p, 10);
 445
 446                 if ((*p != 0) || (n > 128))
 447                         return false;
 448         }
 449
 450         return inet_pton(AF_INET6, buf, &a);
 451 }
 452
 453 static bool
 454 dt_type_cidr(struct dt_state *s, int nargs)
 455 {
 456         return (dt_type_cidr4(s, 0) || dt_type_cidr6(s, 0));
 457 }
 458
 459 static bool
 460 dt_type_ipmask4(struct dt_state *s, int nargs)
 461 {
 462         bool rv;
 463         struct in_addr a;
 464         const char *value;
 465         char *p, buf[sizeof("255.255.255.255/255.255.255.255\0")];
 466
 467         if (strlen(s->value) >= sizeof(buf))
 468                 return false;
 469
 470         strcpy(buf, s->value);
 471         p = strchr(buf, '/');
 472
 473         if (p)
 474         {
 475                 *p++ = 0;
 476
 477                 value = s->value;
 478                 s->value = p;
 479                 rv = dt_type_netmask4(s, 0);
 480                 s->value = value;
 481
 482                 if (!rv)
 483                         return false;
 484         }
 485
 486         return inet_pton(AF_INET, buf, &a);
 487 }
 488
 489 static bool
 490 dt_type_ipmask6(struct dt_state *s, int nargs)
 491 {
 492         bool rv;
 493         struct in6_addr a;
 494         const char *value;
 495         char *p, buf[sizeof("FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:255.255.255.255/"
 496                             "FFFF:FFFF:FFFF:FFFF:FFFF:FFFF:255.255.255.255\0")];
 497
 498         if (strlen(s->value) >= sizeof(buf))
 499                 return false;
 500
 501         strcpy(buf, s->value);
 502         p = strchr(buf, '/');
 503
 504         if (p)
 505         {
 506                 *p++ = 0;
 507
 508                 value = s->value;
 509                 s->value = p;
 510                 rv = dt_type_netmask6(s, 0);
 511                 s->value = value;
 512
 513                 if (!rv)
 514                         return false;
 515         }
 516
 517         return inet_pton(AF_INET6, buf, &a);
 518 }
 519
 520 static bool
 521 dt_type_ipmask(struct dt_state *s, int nargs)
 522 {
 523         return (dt_type_ipmask4(s, 0) || dt_type_ipmask6(s, 0));
 524 }
 525
 526 static bool
 527 dt_type_port(struct dt_state *s, int nargs)
 528 {
 529         int n;
 530         char *e;
 531
 532         n = strtoul(s->value, &e, 10);
 533
 534         return (e > s->value && *e == 0 && n <= 65535);
 535 }
 536
 537 static bool
 538 dt_type_portrange(struct dt_state *s, int nargs)
 539 {
 540         int n, m;
 541         char *e;
 542
 543         n = strtoul(s->value, &e, 10);
 544
 545         if (e == s->value || *e != '-')
 546                 return false;
 547
 548         m = strtoul(e + 1, &e, 10);
 549
 550         return (*e == 0 && n <= 65535 && m <= 65535 && n <= m);
 551 }
 552
 553 static bool
 554 dt_type_macaddr(struct dt_state *s, int nargs)
 555 {
 556         return !!ether_aton(s->value);
 557 }
 558
 559 static bool
 560 dt_type_uciname(struct dt_state *s, int nargs)
 561 {
 562         const char *p;
 563
 564         for (p = s->value;
 565              *p && ((*p >= 'A' && *p <= 'Z') || (*p >= 'a' && *p <= 'z') ||
 566                     (*p >= '0' && *p <= '9') || (*p == '_'));
 567                  p++);
 568
 569         return (*p == 0);
 570 }
 571
 572 static bool
 573 dt_type_wpakey(struct dt_state *s, int nargs)
 574 {
 575         int len = strlen(s->value);
 576         const char *p = s->value;
 577
 578         if (len == 64)
 579         {
 580                 while (isxdigit(*p))
 581                         p++;
 582
 583                 return (*p == 0);
 584         }
 585
 586         return (len >= 8 && len <= 63);
 587 }
 588
 589 static bool
 590 dt_type_wepkey(struct dt_state *s, int nargs)
 591 {
 592         int len = strlen(s->value);
 593         const char *p = s->value;
 594
 595         if (!strncmp(p, "s:", 2))
 596         {
 597                 len -= 2;
 598                 p += 2;
 599         }
 600
 601         if (len == 10 || len == 26)
 602         {
 603                 while (isxdigit(*p))
 604                         p++;
 605
 606                 return (*p == 0);
 607         }
 608
 609         return (len == 5 || len == 13);
 610 }
 611
 612 static bool
 613 dt_type_hostname(struct dt_state *s, int nargs)
 614 {
 615         const char *p, *last;
 616
 617         for (p = last = s->value; *p; p++)
 618         {
 619                 if (*p == '.')
 620                 {
 621                         if ((p - last) == 0 || (p - last) > 63)
 622                                 return false;
 623
 624                         last = p + 1;
 625                         continue;
 626                 }
 627                 else if ((*p >= 'A' && *p <= 'Z') || (*p >= 'a' && *p <= 'z') ||
 628                          (*p >= '0' && *p <= '9') || (*p == '_') || (*p == '-'))
 629                 {
 630                         continue;
 631                 }
 632
 633                 return false;
 634         }
 635
 636         return ((p - last) > 0 && (p - last) <= 255);
 637 }
 638
 639 static bool
 640 dt_type_host(struct dt_state *s, int nargs)
 641 {
 642         return (dt_type_hostname(s, 0) || dt_type_ipaddr(s, 0));
 643 }
 644
 645 static bool
 646 dt_type_network(struct dt_state *s, int nargs)
 647 {
 648         return (dt_type_uciname(s, 0) || dt_type_host(s, 0));
 649 }
 650
 651 static bool
 652 dt_type_phonedigit(struct dt_state *s, int nargs)
 653 {
 654         const char *p;
 655
 656         for (p = s->value;
 657              *p && ((*p >= '0' && *p <= '9') || (*p == '*') || (*p == '#') ||
 658                     (*p == '!') || (*p == '.'));
 659                  p++);
 660
 661         return (*p == 0);
 662 }
 663
 664 static bool
 665 dt_type_directory(struct dt_state *s, int nargs)
 666 {
 667         struct stat st;
 668         return (!stat(s->value, &st) && S_ISDIR(st.st_mode));
 669 }
 670
 671
 672 static bool
 673 dt_type_device(struct dt_state *s, int nargs)
 674 {
 675         struct stat st;
 676         return (!stat(s->value, &st) &&
 677                 (S_ISBLK(st.st_mode) || S_ISCHR(st.st_mode)));
 678 }
 679
 680 static bool
 681 dt_type_file(struct dt_state *s, int nargs)
 682 {
 683         struct stat st;
 684         return (!stat(s->value, &st) && S_ISREG(st.st_mode));
 685 }
 686
 687
 688 static struct dt_fun dt_types[] = {
 689         { "or",                         DT_INVALID,             dt_type_or                      },
 690         { "and",                        DT_INVALID,             dt_type_and                     },
 691         { "not",                        DT_INVALID,             dt_type_not                     },
 692         { "neg",                        DT_INVALID,             dt_type_neg                     },
 693         { "list",                       DT_INVALID,             dt_type_list            },
 694         { "min",                        DT_NUMBER,              dt_type_min                     },
 695         { "max",                        DT_NUMBER,              dt_type_max                     },
 696         { "range",                      DT_NUMBER,              dt_type_range           },
 697         { "minlength",          DT_STRING,              dt_type_minlen          },
 698         { "maxlength",          DT_STRING,              dt_type_maxlen          },
 699         { "rangelength",        DT_STRING,              dt_type_rangelen        },
 700         { "integer",            DT_NUMBER,              dt_type_int                     },
 701         { "uinteger",           DT_NUMBER,              dt_type_uint            },
 702         { "float",                      DT_NUMBER,              dt_type_float           },
 703         { "ufloat",                     DT_NUMBER,              dt_type_ufloat          },
 704         { "bool",                       DT_BOOL,                dt_type_bool            },
 705         { "string",                     DT_STRING,              dt_type_string          },
 706         { "ip4addr",            DT_STRING,              dt_type_ip4addr         },
 707         { "ip6addr",            DT_STRING,              dt_type_ip6addr         },
 708         { "ipaddr",                     DT_STRING,              dt_type_ipaddr          },
 709         { "cidr4",                      DT_STRING,              dt_type_cidr4           },
 710         { "cidr6",                      DT_STRING,              dt_type_cidr6           },
 711         { "cidr",                       DT_STRING,              dt_type_cidr            },
 712         { "netmask4",           DT_STRING,              dt_type_netmask4        },
 713         { "netmask6",           DT_STRING,              dt_type_netmask6        },
 714         { "ipmask4",            DT_STRING,              dt_type_ipmask4         },
 715         { "ipmask6",            DT_STRING,              dt_type_ipmask6         },
 716         { "ipmask",                     DT_STRING,              dt_type_ipmask          },
 717         { "port",                       DT_NUMBER,              dt_type_port            },
 718         { "portrange",          DT_STRING,              dt_type_portrange       },
 719         { "macaddr",            DT_STRING,              dt_type_macaddr         },
 720         { "uciname",            DT_STRING,              dt_type_uciname         },
 721         { "wpakey",                     DT_STRING,              dt_type_wpakey          },
 722         { "wepkey",                     DT_STRING,              dt_type_wepkey          },
 723         { "hostname",           DT_STRING,              dt_type_hostname        },
 724         { "host",                       DT_STRING,              dt_type_host            },
 725         { "network",            DT_STRING,              dt_type_network         },
 726         { "phonedigit",         DT_STRING,              dt_type_phonedigit      },
 727         { "directory",          DT_STRING,              dt_type_directory       },
 728         { "device",                     DT_STRING,              dt_type_device          },
 729         { "file",                       DT_STRING,              dt_type_file            },
 730
 731         { }
 732 };
 733
 734 static struct dt_fun *
 735 dt_lookup_function(const char *s, const char *e)
 736 {
 737         struct dt_fun *fun = dt_types;
 738
 739         while (fun->name)
 740         {
 741                 if (!strncmp(fun->name, s, e - s) && *(fun->name + (e - s)) == '\0')
 742                         return fun;
 743
 744                 fun++;
 745         }
 746
 747         return NULL;
 748 }
 749
 750 static bool
 751 dt_parse_atom(struct dt_state *s, const char *label, const char *end)
 752 {
 753         char q, *e;
 754         const char *p;
 755         bool esc;
 756         double dval;
 757         struct dt_fun *func;
 758         struct dt_op *op = &s->stack[s->depth];
 759
 760         if ((s->depth + 1) >= (sizeof(s->stack) / sizeof(s->stack[0])))
 761         {
 762                 printf("Syntax error, expression too long\n");
 763                 return false;
 764         }
 765
 766         while (isspace(*label))
 767                 label++;
 768
 769         /* test whether label is a float */
 770         dval = strtod(label, &e);
 771
 772         if (e > label)
 773         {
 774                 op->next = e;
 775                 op->type = OP_NUMBER;
 776                 op->value.number = dval;
 777                 op->nextop = ++s->depth;
 778
 779                 return true;
 780         }
 781         else if ((*label == '"') || (*label == '\''))
 782         {
 783                 for (p = label + 1, q = *label, esc = false; p <= end; p++)
 784                 {
 785                         if (esc)
 786                         {
 787                                 esc = false;
 788                                 continue;
 789                         }
 790                         else if (*p == '\\')
 791                         {
 792                                 esc = true;
 793                                 continue;
 794                         }
 795                         else if (*p == q)
 796                         {
 797                                 op->next = p + 1;
 798                                 op->type = OP_STRING;
 799                                 op->length = (p - label) - 1;
 800                                 op->value.string = label + 1;
 801                                 op->nextop = ++s->depth;
 802
 803                                 return true;
 804                         }
 805                 }
 806
 807                 printf("Syntax error, unterminated string\n");
 808                 return false;
 809         }
 810         else if (*label)
 811         {
 812                 for (p = label;
 813                      p <= end && ((*p >= 'A' && *p <= 'Z') ||
 814                                   (*p >= 'a' && *p <= 'z') ||
 815                                   (*p >= '0' && *p <= '9') ||
 816                                   (*p == '_'));
 817                      p++);
 818
 819                 func = dt_lookup_function(label, p);
 820
 821                 if (!func)
 822                 {
 823                         printf("Syntax error, unrecognized function\n");
 824                         return false;
 825                 }
 826
 827                 op->next = p;
 828                 op->type = OP_FUNCTION;
 829                 op->value.function = func;
 830                 op->nextop = ++s->depth;
 831
 832                 return true;
 833         }
 834
 835         printf("Syntax error, unexpected EOF\n");
 836         return false;
 837 }
 838
 839 static bool
 840 dt_parse_list(struct dt_state *s, const char *code, const char *end);
 841
 842 static bool
 843 dt_parse_expr(const char *code, const char *end, struct dt_state *s)
 844 {
 845         struct dt_op *tok;
 846
 847         if (!dt_parse_atom(s, code, end))
 848                 return false;
 849
 850         tok = &s->stack[s->depth - 1];
 851
 852         while (isspace(*tok->next))
 853                 tok->next++;
 854
 855         if (tok->type == OP_FUNCTION)
 856         {
 857                 if (*tok->next == '(')
 858                 {
 859                         end--;
 860
 861                         while (isspace(*end) && end > tok->next + 1)
 862                                 end--;
 863
 864                         return dt_parse_list(s, tok->next + 1, end);
 865                 }
 866                 else if (tok->next == end)
 867                 {
 868                         return dt_parse_list(s, tok->next, tok->next);
 869                 }
 870
 871                 printf("Syntax error, expected '(' or EOF after function label\n");
 872                 return false;
 873         }
 874         else if (tok->next == end)
 875         {
 876                 return true;
 877         }
 878
 879         printf("Syntax error, expected ',' after literal\n");
 880         return false;
 881 }
 882
 883 static bool
 884 dt_parse_list(struct dt_state *s, const char *code, const char *end)
 885 {
 886         char c;
 887         bool esc;
 888         int nest;
 889         const char *p, *last;
 890         struct dt_op *fptr;
 891
 892         if (!code)
 893                 return false;
 894
 895         fptr = &s->stack[s->depth - 1];
 896
 897         for (nest = 0, p = last = code, esc = false, c = *p;
 898              p <= end;
 899              p++, c = (p < end) ? *p : '\0')
 900         {
 901                 if (esc)
 902                 {
 903                         esc = false;
 904                         continue;
 905                 }
 906
 907                 switch (c)
 908                 {
 909                 case '\\':
 910                         esc = true;
 911                         break;
 912
 913                 case '(':
 914                         nest++;
 915                         break;
 916
 917                 case ')':
 918                         nest--;
 919                         break;
 920
 921                 case ',':
 922                 case '\0':
 923                         if (nest <= 0)
 924                         {
 925                                 if (p > last)
 926                                 {
 927                                         if (!dt_parse_expr(last, p, s))
 928                                                 return false;
 929
 930                                         fptr->length++;
 931                                 }
 932
 933                                 last = p + 1;
 934                         }
 935
 936                         break;
 937                 }
 938         }
 939
 940         fptr->nextop = s->depth;
 941         return true;
 942 }
 943
 944 static bool
 945 dt_step(struct dt_state *s)
 946 {
 947         bool rv;
 948         struct dt_op *op = &s->stack[s->pos];
 949
 950         switch (op->type)
 951         {
 952         case OP_NUMBER:
 953                 rv = dt_test_number(op->value.number, s->value);
 954                 if (rv)
 955                         s->valtype = DT_NUMBER;
 956                 break;
 957
 958         case OP_STRING:
 959                 rv = dt_test_string(op->value.string, op->value.string + op->length, s->value);
 960                 if (rv)
 961                         s->valtype = DT_STRING;
 962                 break;
 963
 964         case OP_FUNCTION:
 965                 rv = dt_call(s);
 966                 break;
 967
 968         default:
 969                 rv = false;
 970                 break;
 971         }
 972
 973         s->pos = op->nextop;
 974         return rv;
 975 }
 976
 977 static bool
 978 dt_call(struct dt_state *s)
 979 {
 980         bool rv;
 981         struct dt_op *fptr = &s->stack[s->pos];
 982         struct dt_fun *func = fptr->value.function;
 983
 984         s->pos++;
 985
 986         rv = func->call(s, fptr->length);
 987
 988         if (rv && func->valtype)
 989                 s->valtype = func->valtype;
 990
 991         s->pos = fptr->nextop;
 992
 993         return rv;
 994 }
 995
 996 enum dt_type
 997 dt_parse(const char *code, const char *value)
 998 {
 999         struct dt_state s = {
1000                 .depth = 1,
1001                 .stack = {
1002                         {
1003                                 .type = OP_FUNCTION,
1004                                 .value.function = &dt_types[0],
1005                                 .next = code
1006                         }
1007                 }
1008         };
1009
1010         if (!value || !*value)
1011                 return false;
1012
1013         if (!dt_parse_list(&s, code, code + strlen(code)))
1014                 return false;
1015
1016         s.value = value;
1017
1018         if (dt_call(&s))
1019                 return s.valtype;
1020
1021         return DT_INVALID;
1022 }