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