git.pond.sub.org Git - empserver/blob - src/lib/subs/nstr.c

   1 /*
   2  *  Empire - A multi-player, client/server Internet based war game.
   3  *  Copyright (C) 1986-2015, Dave Pare, Jeff Bailey, Thomas Ruschak,
   4  *                Ken Stevens, Steve McClure, Markus Armbruster
   5  *
   6  *  Empire is free software: you can redistribute it and/or modify
   7  *  it under the terms of the GNU General Public License as published by
   8  *  the Free Software Foundation, either version 3 of the License, or
   9  *  (at your option) any later version.
  10  *
  11  *  This program is distributed in the hope that it will be useful,
  12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  *  GNU General Public License for more details.
  15  *
  16  *  You should have received a copy of the GNU General Public License
  17  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  18  *
  19  *  ---
  20  *
  21  *  See files README, COPYING and CREDITS in the root of the source
  22  *  tree for related information and legal notices.  It is expected
  23  *  that future projects/authors will amend these files as needed.
  24  *
  25  *  ---
  26  *
  27  *  nstr.c: compile and execute the item selections on sectors
  28  *
  29  *  Known contributors to this file:
  30  *     Dave Pare, 1989
  31  *     Steve McClure, 1997
  32  *     Markus Armbruster, 2004-2014
  33  */
  34
  35 #include <config.h>
  36
  37 #include <ctype.h>
  38 #include <limits.h>
  39 #include "file.h"
  40 #include "match.h"
  41 #include "nsc.h"
  42 #include "player.h"
  43 #include "prototypes.h"
  44
  45 static char *nstr_parse_val(char *, struct valstr *);
  46 static int nstr_match_ca(struct valstr *, struct castr *);
  47 static int nstr_is_name_of_ca(struct valstr *, struct castr *, int);
  48 static int nstr_ca_comparable(struct castr *, int, int);
  49 static int nstr_match_val(struct valstr *, struct castr *, int);
  50 static struct valstr *nstr_resolve_id(struct valstr *, struct castr *, int);
  51 static struct valstr *nstr_resolve_val(struct valstr *, int, struct castr *);
  52 static int nstr_optype(enum nsc_type, enum nsc_type);
  53
  54 /*
  55  * Compile conditions into array NP[LEN].
  56  * Return number of conditions, or -1 on error.
  57  * It is an error if there are more than LEN conditions.
  58  * TYPE is the context type, a file type.
  59  * STR is the condition string, in Empire syntax, without the leading
  60  * '?'.
  61  */
  62 int
  63 nstr_comp(struct nscstr *np, int len, int type, char *str)
  64 {
  65     struct castr *ca = ef_cadef(type);
  66     char *cond;
  67     char *tail;
  68     int i;
  69     struct nscstr dummy;
  70     int lft_caidx, rgt_caidx;
  71     int lft_val, rgt_val;
  72     int two_sels;
  73
  74     cond = str;
  75     for (i = 0; ; ++i, ++np) {
  76         if (i >= len)
  77             np = &dummy;
  78
  79         /* left operand */
  80         if (!*cond) {
  81             pr("%s -- %scondition expected\n", str, i ? "another " : "");
  82             return -1;
  83         }
  84         tail = nstr_parse_val(cond, &np->lft);
  85         lft_caidx = nstr_match_ca(&np->lft, ca);
  86
  87         /* operator */
  88         if (*tail != '<' && *tail != '=' && *tail != '>' && *tail != '#') {
  89             if (*tail)
  90                 pr("%s -- expected condition operator\n", cond);
  91             else
  92                 pr("%s -- missing condition operator\n", cond);
  93             return -1;
  94         }
  95         np->operator = *tail;
  96         ++tail;
  97
  98         /* right operand */
  99         if (!*tail) {
 100             pr("%s -- operand expected\n", cond);
 101             return -1;
 102         }
 103         tail = nstr_parse_val(tail, &np->rgt);
 104         rgt_caidx = nstr_match_ca(&np->rgt, ca);
 105
 106         /*
 107          * Resolve identifiers
 108          *
 109          * If just one operand is an identifier, it names a selector.
 110          * If both operands are identifiers, things get complicated:
 111          * either can then name a selector or a symbolic value for the
 112          * selector named by the other operand.
 113          */
 114         if (np->lft.val_cat == NSC_ID && np->rgt.val_cat == NSC_ID) {
 115             lft_val = nstr_match_val(&np->lft, ca, rgt_caidx);
 116             rgt_val = nstr_match_val(&np->rgt, ca, lft_caidx);
 117             two_sels = nstr_ca_comparable(ca, lft_caidx, rgt_caidx);
 118             /*
 119              * If lft_val >= 0 interpreting rgt as a selector and lft
 120              * as one of its values works.  Likewise for rgt_val >= 0.
 121              * If two_sels, interpreting both lft and rgt as selector
 122              * works.
 123              */
 124             switch ((lft_val >= 0) + (rgt_val >= 0) + !!two_sels) {
 125             case 0:             /* no interpretation */
 126                 if (lft_caidx >= 0 && rgt_caidx >= 0) {
 127                     /*
 128                      * Both identifiers name selectors.  Since
 129                      * !two_sels, they can't be comparable.
 130                      * Example: type=civil.
 131                      */
 132                     pr("%.*s -- not comparable\n", (int)(tail-cond), cond);
 133                     return -1;
 134                 }
 135                 /*
 136                  * At least one identifier doesn't name a selector,
 137                  * and nstr_resolve_id() will fail for it below
 138                  */
 139                 break;
 140             case 1:             /* one unambigous interpretation */
 141                 break;
 142             default:            /* multiple interpretations */
 143                 /*
 144                  * Last-resort disambiguation: if the identifier is
 145                  * the unabbreviated name of a selector, discard
 146                  * value, else discard selector interpretation.
 147                  * Example: resolve wing=g to wing='g', not wing=group
 148                  * or 'wing'=group.
 149                  */
 150                 if (nstr_is_name_of_ca(&np->lft, ca, lft_caidx))
 151                     lft_val = -1;
 152                 else
 153                     two_sels = 0;
 154                 if (nstr_is_name_of_ca(&np->rgt, ca, rgt_caidx))
 155                     rgt_val = -1;
 156                 else
 157                     two_sels = 0;
 158                 if ((lft_val >= 0) + (rgt_val >= 0) + !!two_sels == 1)
 159                     break;      /* last-resort disambiguation worked */
 160                 /*
 161                  * Example: n<n for sectors could mean newdes<n or
 162                  * n<newdes.
 163                  */
 164                 pr("%.*s -- condition ambiguous\n", (int)(tail-cond), cond);
 165                 return -1;
 166             }
 167             /* resolve identifiers naming values */
 168             if (lft_val >= 0)
 169                 nstr_resolve_val(&np->lft, lft_val, &ca[rgt_caidx]);
 170             if (rgt_val >= 0)
 171                 nstr_resolve_val(&np->rgt, rgt_val, &ca[lft_caidx]);
 172         }
 173         /* remaining identifiers name selectors */
 174         if (!nstr_resolve_id(&np->lft, ca, lft_caidx))
 175             return -1;
 176         if (!nstr_resolve_id(&np->rgt, ca, rgt_caidx))
 177             return -1;
 178
 179         /* find operator type */
 180         np->optype = nstr_optype(np->lft.val_type, np->rgt.val_type);
 181         if (np->optype == NSC_NOTYPE) {
 182             pr("%.*s -- not comparable\n", (int)(tail-cond), cond);
 183             return -1;
 184         }
 185
 186         /* another condition? */
 187         if (*tail == 0)
 188             break;
 189         if (*tail != '&') {
 190             pr("%s -- expected `&'\n", cond);
 191             return -1;
 192         }
 193         cond = tail + 1;
 194     }
 195
 196     if (i >= len) {
 197         /* could just return I and let caller gripe or enlarge buffer */
 198         pr("%s -- too many conditions\n", str);
 199         return -1;
 200     }
 201
 202     return i + 1;
 203 }
 204
 205 /* Like strcmp(S1, S2), but limit length of S1 to SZ1 and of S2 to SZ2.  */
 206 static int
 207 strnncmp(char *s1, size_t sz1, char *s2, size_t sz2)
 208 {
 209     int res;
 210     if (sz1 == sz2)
 211         return strncmp(s1, s2, sz2);
 212     if (sz1 < sz2)
 213         return -strnncmp(s2, sz2, s1, sz1);
 214     res = strncmp(s1, s2, sz2);
 215     return res ? res : s1[sz2];
 216 }
 217
 218 #define EVAL(op, lft, rgt)                      \
 219     ((op) == '<' ? (lft) < (rgt)                \
 220      : (op) == '=' ? (lft) == (rgt)             \
 221      : (op) == '>' ? (lft) > (rgt)              \
 222      : (op) == '#' ? (lft) != (rgt)             \
 223      : (CANT_REACH(), 0))
 224
 225 /*
 226  * Evaluate compiled conditions in array NP[NCOND].
 227  * Return non-zero iff they are all true.
 228  * PTR points to a context object of the type that was used to compile
 229  * the conditions.
 230  */
 231 int
 232 nstr_exec(struct nscstr *np, int ncond, void *ptr)
 233 {
 234     int i, op, cmp;
 235     enum nsc_type optype;
 236     struct valstr lft, rgt;
 237
 238     for (i = 0; i < ncond; ++i) {
 239         op = np[i].operator;
 240         optype = np[i].optype;
 241         if (np[i].lft.val_cat == NSC_NOCAT || np[i].rgt.val_cat == NSC_NOCAT)
 242             return 0;
 243         lft = np[i].lft;
 244         nstr_eval(&lft, player->cnum, ptr, optype);
 245         rgt = np[i].rgt;
 246         nstr_eval(&rgt, player->cnum, ptr, optype);
 247         if (CANT_HAPPEN(lft.val_type != optype || rgt.val_type != optype))
 248             return 0;
 249         switch (optype) {
 250         case NSC_LONG:
 251             if (!EVAL(op, lft.val_as.lng, rgt.val_as.lng))
 252                 return 0;
 253             break;
 254         case NSC_DOUBLE:
 255             if (!EVAL(op, lft.val_as.dbl, rgt.val_as.dbl))
 256                 return 0;
 257             break;
 258         case NSC_STRING:
 259             cmp = strnncmp(lft.val_as.str.base, lft.val_as.str.maxsz,
 260                            rgt.val_as.str.base, rgt.val_as.str.maxsz);
 261             if (!EVAL(op, cmp, 0))
 262                 return 0;
 263             break;
 264         default:
 265             CANT_REACH();
 266             return 0;
 267         }
 268     }
 269
 270     return 1;
 271 }
 272
 273 /*
 274  * Parse a value in STR into VAL.
 275  * Return a pointer to the first character after the value.
 276  * Value is either evaluated into NSC_STRING, NSC_DOUBLE or NSC_LONG,
 277  * or an identifier.
 278  */
 279 static char *
 280 nstr_parse_val(char *str, struct valstr *val)
 281 {
 282     long l;
 283     double d;
 284     char *tail, *tail2;
 285
 286     /* string */
 287     if (str[0] == '\'') {
 288         for (tail = str + 1; *tail && *tail != '\''; ++tail) ;
 289         /* FIXME implement \ quoting */
 290         val->val_type = NSC_STRING;
 291         val->val_cat = NSC_VAL;
 292         val->val_as.str.base = str + 1;
 293         val->val_as.str.maxsz = tail - (str + 1);
 294         if (*tail)
 295             ++tail;
 296         /* FIXME else unclosed string */
 297         return tail;
 298     }
 299
 300     /* identifier */
 301     if (isalpha(str[0])) {
 302         for (tail = str+1; isalnum(*tail) || *tail == '_'; ++tail) ;
 303         val->val_type = NSC_NOTYPE;
 304         val->val_cat = NSC_ID;
 305         val->val_as.str.base = str;
 306         val->val_as.str.maxsz = tail - str;
 307         return tail;
 308     }
 309
 310     /* number */
 311     l = strtol(str, &tail, 0);
 312     d = strtod(str, &tail2);
 313     if (tail2 > tail) {
 314         val->val_type = NSC_DOUBLE;
 315         val->val_cat = NSC_VAL;
 316         val->val_as.dbl = d;
 317         return tail2;
 318     }
 319     if (tail != str) {
 320         val->val_type = NSC_LONG;
 321         val->val_cat = NSC_VAL;
 322         val->val_as.lng = l;
 323         return tail;
 324     }
 325
 326     /* funny character, interpret as identifier */
 327     tail = CANT_HAPPEN(!*str) ? str : str + 1;
 328     val->val_type = NSC_NOTYPE;
 329     val->val_cat = NSC_ID;
 330     val->val_as.str.base = str;
 331     val->val_as.str.maxsz = tail - str;
 332     return tail;
 333 }
 334
 335 /*
 336  * Match VAL in table of selector descriptors CA, return index.
 337  * Return M_NOTFOUND if there are no matches, M_NOTUNIQUE if there are
 338  * several.
 339  * A VAL that is not an identifier doesn't match anything.  A null CA
 340  * is considered empty.
 341  */
 342 static int
 343 nstr_match_ca(struct valstr *val, struct castr *ca)
 344 {
 345     char id[32];
 346
 347     if (val->val_cat != NSC_ID || val->val_as.str.maxsz >= sizeof(id))
 348         return M_NOTFOUND;
 349
 350     if (!ca)
 351         return M_NOTFOUND;
 352
 353     memcpy(id, val->val_as.str.base, val->val_as.str.maxsz);
 354     id[val->val_as.str.maxsz] = 0;
 355
 356     return stmtch(id, ca, offsetof(struct castr, ca_name),
 357                   sizeof(struct castr));
 358 }
 359
 360 /*
 361  * Is identifier VAL the name of the selector given by CA and IDX?
 362  * Return non-zero if and only if IDX is non-negative and VAL is the
 363  * name of CA[IDX].
 364  * IDX must have been obtained from nstr_match_ca(VAL, CA).
 365  */
 366 static int
 367 nstr_is_name_of_ca(struct valstr *val, struct castr *ca, int idx)
 368 {
 369     if (CANT_HAPPEN(val->val_cat != NSC_ID && idx >= 0))
 370         return 0;
 371     return idx >= 0 && strlen(ca[idx].ca_name) == val->val_as.str.maxsz;
 372 }
 373
 374 /*
 375  * Do we have two comparable selectors?
 376  * Check selector descriptors CA[LFT_IDX] (unless LFT_IDX is negative)
 377  * and CA[RGT_IDX] (unless RGT_IDX is negative).  CA may be null when
 378  * both are negative.
 379  */
 380 static int
 381 nstr_ca_comparable(struct castr *ca, int lft_idx, int rgt_idx)
 382 {
 383     if (lft_idx < 0 || rgt_idx < 0)
 384         return 0;
 385     if (ca[lft_idx].ca_table != ca[rgt_idx].ca_table)
 386         return 0;               /* Example: land type=spy */
 387     return nstr_optype(ca[lft_idx].ca_type, ca[rgt_idx].ca_type)
 388         != NSC_NOTYPE;          /* Example: ship name=effic */
 389 }
 390
 391 /*
 392  * Match VAL in a selector's values, return its (non-negative) value.
 393  * Match values of selector descriptor CA[IDX], provided IDX is not
 394  * negative.  CA may be null when IDX is negative.
 395  * Return M_NOTFOUND if there are no matches, M_NOTUNIQUE if there are
 396  * several.
 397  */
 398 static int
 399 nstr_match_val(struct valstr *val, struct castr *ca, int idx)
 400 {
 401     char id[32];
 402     enum nsc_type type;
 403
 404     if (val->val_cat != NSC_ID || idx < 0)
 405         return M_NOTFOUND;
 406
 407     type = nstr_promote(ca[idx].ca_type);
 408     if (type == NSC_STRING)
 409         return 0;
 410
 411     if (ca[idx].ca_table == EF_BAD || CANT_HAPPEN(type != NSC_LONG))
 412         return M_NOTFOUND;
 413
 414     if (val->val_as.str.maxsz >= sizeof(id))
 415         return M_NOTFOUND;
 416     memcpy(id, val->val_as.str.base, val->val_as.str.maxsz);
 417     id[val->val_as.str.maxsz] = 0;
 418     return ef_elt_byname(ca[idx].ca_table, id);
 419 }
 420
 421 /*
 422  * Change VAL to resolve identifier to selector.
 423  * Return VAL on success, NULL on error.
 424  * No change if VAL is not an identifier.
 425  * Else change VAL into symbolic value for selector CA[IDX] if IDX >=
 426  * 0, and error if not.
 427  */
 428 static struct valstr *
 429 nstr_resolve_id(struct valstr *val, struct castr *ca, int idx)
 430 {
 431     if (val->val_cat != NSC_ID)
 432         return val;
 433
 434     if (idx == M_NOTUNIQUE) {
 435         pr("%.*s -- ambiguous name\n",
 436            (int)val->val_as.str.maxsz, val->val_as.str.base);
 437         val->val_cat = NSC_NOCAT;
 438         return NULL;
 439     }
 440
 441     if (idx == M_NOTFOUND) {
 442         pr("%.*s -- unknown name\n",
 443            (int)val->val_as.str.maxsz, val->val_as.str.base);
 444         val->val_cat = NSC_NOCAT;
 445         return NULL;
 446     }
 447
 448     if (CA_IS_ARRAY(&ca[idx])) {
 449         pr("%.*s -- not usable here\n",
 450            (int)val->val_as.str.maxsz, val->val_as.str.base);
 451         val->val_cat = NSC_NOCAT;
 452         return NULL;
 453     }
 454
 455     if ((ca[idx].ca_flags & NSC_DEITY) && !player->god) {
 456         pr("%.*s -- not accessible to mortals\n",
 457            (int)val->val_as.str.maxsz, val->val_as.str.base);
 458         val->val_cat = NSC_NOCAT;
 459         return NULL;
 460     }
 461
 462     return nstr_mksymval(val, &ca[idx], 0);
 463 }
 464
 465 /*
 466  * Change VAL to resolve identifier to value SELVAL for selector CA.
 467  * Return VAL.
 468  * VAL must be an identifier, and SELVAL must have been obtained from
 469  * nstr_match_val(VAL, CA0, IDX), where CA = &CA0[IDX].
 470  */
 471 static struct valstr *
 472 nstr_resolve_val(struct valstr *val, int selval, struct castr *ca)
 473 {
 474     enum nsc_type type = nstr_promote(ca->ca_type);
 475
 476     if (CANT_HAPPEN(val->val_cat != NSC_ID)) {
 477         val->val_cat = NSC_NOCAT;
 478         return val;
 479     }
 480
 481     if (type == NSC_STRING) {
 482         val->val_type = NSC_STRING;
 483         val->val_cat = NSC_VAL;
 484         /* map identifier ~ to empty string, like some commands do */
 485         if (val->val_as.str.maxsz == 1 && val->val_as.str.base[0] == '~')
 486             val->val_as.str.maxsz = 0;
 487         return val;
 488     }
 489
 490     if (CANT_HAPPEN(type != NSC_LONG || ca->ca_table == EF_BAD)) {
 491         val->val_type = NSC_NOTYPE;
 492         val->val_cat = NSC_NOCAT;
 493         return val;
 494     }
 495
 496     val->val_type = type;
 497     val->val_cat = NSC_VAL;
 498     val->val_as.lng = selval;
 499     return val;
 500 }
 501
 502 /*
 503  * Return operator type for operand types LFT, RGT.
 504  */
 505 static int
 506 nstr_optype(enum nsc_type lft, enum nsc_type rgt)
 507 {
 508     lft = nstr_promote(lft);
 509     rgt = nstr_promote(rgt);
 510     if (lft == rgt)
 511         return lft;
 512     if (lft == NSC_DOUBLE && rgt == NSC_LONG)
 513         return NSC_DOUBLE;
 514     if (rgt == NSC_DOUBLE && lft == NSC_LONG)
 515         return NSC_DOUBLE;
 516     return NSC_NOTYPE;
 517 }
 518
 519 /*
 520  * Compile a value in STR into VAL.
 521  * Return a pointer to the first character after the value on success,
 522  * NULL on error.
 523  * TYPE is the context type, a file type.
 524  */
 525 char *
 526 nstr_comp_val(char *str, struct valstr *val, int type)
 527 {
 528     struct castr *ca = ef_cadef(type);
 529     char *tail = nstr_parse_val(str, val);
 530     if (!nstr_resolve_id(val, ca, nstr_match_ca(val, ca)))
 531         return NULL;
 532     return tail;
 533 }