root/1.8.3/trunk/src/boolexp.c

/**
 * \file boolexp.c
 *
 * \brief Boolean expression parser.
 *
 * This code implements a parser for boolean expressions of the form
 * used in locks. Summary of parsing rules, lowest to highest precedence:
 * \verbatim
 * E -> T; E -> T | E                   (or)
 * T -> F; T -> F & T                   (and)
 * F -> !F;F -> A                       (not)
 * A -> @L; A -> I                      (indirect)
 * I -> =Identifier ; I -> C            (equality)
 * C -> +Identifier ; C -> O            (carry)
 * O -> $Identifier ; O -> L            (owner)
 * L -> (E); L -> eval/attr/flag lock   (parens, special atoms)
 * L -> E, L is an object name or dbref or #t* or #f*   (simple atoms)
 * \endverbatim
 *
 * Previously, the boolexp code just used a parse tree of the
 * boolexp. Now, it turns the parse tree into bytecode that can be
 * stored in the chunk manager. It probably also evaluates faster, but
 * no profiling has been done to support this claim. It certainly
 * involves less non-tail recursion and better cache behavior.
 *
 * It's a three-stage process. First, the lock string is turned into a
 * parse tree. Second, the tree is walked and "assembler" instructions
 * are generated, including labels for jumps. Third, the "assembly" is
 * stepped through and bytecode emitted, with labeled jumps replaced
 * by distances that are offsets from the start of the
 * bytecode. Pretty standard stuff.
 *
 * Each bytecode instruction is 5 bytes long (1 byte opcode + 4 byte
 * int argument), and the minimum number of instructions in a compiled
 * boolexp is 2, for a minimum size of 10 bytes. Compare this to the
 * size of one parse-tree node, 16 bytes. Savings appear to be
 * substantial, especially with complex locks with lots of ors or
 * ands.
 *
 * Many lock keys have string arguments. The strings are standard
 * 0-terminated C strings stored in a section of the same string as
 * the bytecode instructions, starting right after the last
 * instruction. They're accessed by offset from the start of the
 * bytecode string. If the same string appears multiple times in the
 * lock, only one copy is actually present in the string section.
 *
 * The VM for the bytecode is a simple register-based one.  The
 * registers are R, the result register, set by test instructions and
 * a few others, and S, the string register, which holds the extra
 * string in the few tests that need two (A:B, A/B). There are
 * instructions for each lock key type. There's a few extra ones to
 * make decompiling back into a string dead easy. Nothing very
 * complex.
 *
 * Future directions?
 * \verbatim
 * [Development] Raevnos is tempted in passing to re-write the boolexp parser in
 * lex and yacc.
 * [Development] Brazil laughs.
 * [Development] Brazil says, "That might not be a bad idea."
 * [Development] Raevnos has redone everything else in boolexp.c in Penn, so why
 * not? :)
 * [Development] Raevnos says, "Using the justification that it's a lot easier to
 * expand the langage by adding new key types that way."
 * \endverbatim
 *
 * So now you know who to blame if that particular item appears in a
 * changelog for Penn or MUX.
 *
 * On a more serious note, a) #1234 is equivalent to b)
 * =#1234|+#1234. Detecting b and turning it into a, or vis versa,
 * would be easy to do. a is a common key, but turning it into b gets
 * rid of a test instruction in the VM, at the cost of more
 * instructions in generated lock bytecode. CISC or RISC? :) It's also
 * easy to turn !!foo into foo, but nobody makes locks like that. Same
 * with !#true and !#false. Of possibly more interest is rearranging
 * the logic when ands, ors and nots are being used together. For
 * example, !a|!b can become !(a&b).
 *
 * The only optimization done right now is thread jumping: If a jump
 * would move the program counter to another jump operation, it instead
 * goes to that jump's destination.
 * 
 * There's more useful room for improvement in the lock
 * @warnings. Checking things like flag and power keys for valid flags
 * comes to mind.
 *
 */

#include "copyrite.h"
#include "config.h"

#include <ctype.h>
#include <string.h>
#ifdef HAVE_STDINT_H
#include <stdint.h>
#endif
#include "conf.h"
#include "dbdefs.h"
#include "mushdb.h"
#include "match.h"
#include "externs.h"
#include "lock.h"
#include "parse.h"
#include "attrib.h"
#include "flags.h"
#include "log.h"
#include "extchat.h"
#include "strtree.h"
#include "mymalloc.h"
#include "confmagic.h"

#ifdef WIN32
#pragma warning( disable : 4761)        /* disable warning re conversion */
#endif

/* #define DEBUG_BYTECODE */

/** Parse tree node types */
typedef enum boolexp_type {
  BOOLEXP_AND, /**< A&B */
  BOOLEXP_OR, /**< A|B */
  BOOLEXP_NOT, /**< !A */
  BOOLEXP_CONST, /**< A */
  BOOLEXP_ATR, /**< A:B */
  BOOLEXP_IND, /**< @A/B */
  BOOLEXP_CARRY, /**< +A */
  BOOLEXP_IS, /**< =A */
  BOOLEXP_OWNER, /**< $A */
  BOOLEXP_EVAL, /**< A/B */
  BOOLEXP_FLAG, /**< A^B */
  BOOLEXP_BOOL /**< #true, #false */
} boolexp_type;

/** An attribute lock specification for the parse tree.
 * This structure is a piece of a boolexp that's used to store 
 * attribute locks (CANDO:1), eval locks (CANDO/1), and flag locks
 * FLAG^WIZARD.
 */
struct boolatr {
  const char *name;             /**< Name of attribute, flag, etc. to test */
  char text[BUFFER_LEN];        /**< Value to test against */
};

/** A boolean expression parse tree node.
 * Boolean expressions are most widely used in locks. This structure
 * is a general representation of the possible boolean expressions
 * that can be specified in MUSHcode. It's used internally by the lock
 * compiler.
 */
struct boolexp_node {
  /** Type of expression.
   * The type of expressio is one of the boolexp_type's, such as
   * and, or, not, constant, attribute, indirect, carry, is,
   * owner, eval, flag, etc.
   */
  boolexp_type type;
  dbref thing;                  /**< An object, or a boolean val */
  /** The expression itself.
   * This union comprises the various possible types of data we
   * might need to represent any of the expression types.
   */
  union {
    /** And and or locks: combinations of boolexps.
     * This union member is used with and and or locks.
     */
    struct {
      struct boolexp_node *a;   /**< One boolean expression */
      struct boolexp_node *b;   /**< Another boolean expression */
    } sub;
    struct boolexp_node *n;             /**< Not locks: boolean expression to negate */
    struct boolatr *atr_lock;   /**< Atr, eval and flag locks */
    const char *ind_lock;       /**< Indirect locks */
  } data;
};


/** The opcodes supported by the boolexp virtual machine. */
typedef enum bvm_opcode {
  OP_JMPT, /**< Jump to ARG if R is true */
  OP_JMPF, /**< Jump to ARG if R is false */
  OP_TCONST, /**< Tests plain #ARG */
  OP_TATR, /**< Tests S:ARG */
  OP_TIND, /**< Tests @#ARG/S */
  OP_TCARRY, /**< Tests +#ARG */
  OP_TIS, /**< Tests =#ARG */
  OP_TOWNER, /**< Tests $#ARG */
  OP_TEVAL, /**< Tests S/ARG */
  OP_TFLAG, /**< Tests FLAG^ARG */
  OP_TTYPE, /**< Tests TYPE^ARG */
  OP_TPOWER, /**< Tests POWER^ARG */
  OP_TCHANNEL, /**< Tests CHANNEL^ARG */
  OP_TIP, /**< Tests IP^ARG */
  OP_THOSTNAME, /**< Tests HOSTNAME^ARG */
  OP_TOBJID, /**< Tests OBJID^ARG */
  OP_TDBREFLIST,        /**< Tests DBERFLIST^ARG */
  OP_LOADS, /**< Load ARG into S */
  OP_LOADR, /**< Load ARG into R */
  OP_NEGR,  /**< Negate R */
  OP_PAREN, /**< ARG = 0 for a (, ARG = 1 for a ) in decompiling */
  OP_LABEL, /**< A label. Not actually in compiled bytecode */
  OP_RET    /**< Stop evaluating bytecode */
} bvm_opcode;

/** The size of a single bytecode instruction. Probably 5 bytes
 * everywhere. */
#define INSN_LEN (1 + sizeof(int))

/** Information describing one VM instruction or label in the
 * intermediate "assembly" generated from a parse tree. The nodes are
 * part of a linked list.  */
struct bvm_asmnode {
  bvm_opcode op; /**< The opcode */
  int arg; /**< The arg value, or a label or string number */
  struct bvm_asmnode *next; /**< Pointer to the next node */
};

/** Information describing a string to emit in the string section of
 * the bytecode. The nodes are part of a linked list.  */
struct bvm_strnode {
  char *s; /**< The string */
  size_t len; /**< Its length */
  struct bvm_strnode *next; /**< Pointer to the next node */
};

/** A struct describing the complete assembly information needed to
 * generate bytecode */
struct bvm_asm {
  struct bvm_asmnode *head; /**< The start of the list of assembly instructions */
  struct bvm_asmnode *tail; /**< The end of the list */
  struct bvm_strnode *shead; /**< The start of the list of strings */
  struct bvm_strnode *stail; /**< The end of the list */
  int label; /**< The current label id to use */
  size_t strcount;      /**< The number of nodes in the string list */
};

/** The flag lock key (A^B) only allows a few values for A. This
 * struct and the the following table define the allowable ones. When
 * adding a new type here, a matching new bytecode instruction should
 * be added. */
struct flag_lock_types {
  const char *name; /**< The value of A */
  bvm_opcode op;  /**< The associated opcode */
};

/** What's allowed on the left-hand-side of LHS^RHS lock keys */
static struct flag_lock_types flag_locks[] = {
  {"FLAG", OP_TFLAG},
  {"POWER", OP_TPOWER},
  {"TYPE", OP_TTYPE},
  {"CHANNEL", OP_TCHANNEL},
  {"OBJID", OP_TOBJID},
  {"IP", OP_TIP},
  {"HOSTNAME", OP_THOSTNAME},
  {"DBREFLIST", OP_TDBREFLIST},
  {NULL, OP_RET}
};

static uint8_t *
safe_get_bytecode(boolexp b)
  __attribute_malloc__;
    static uint8_t *get_bytecode(boolexp b, uint16_t * storelen);
    static struct boolexp_node *alloc_bool(void) __attribute_malloc__;
    static struct boolatr *alloc_atr(const char *name,
                                     const char *s) __attribute_malloc__;
    static void skip_whitespace(void);
    static void free_bool(struct boolexp_node *b);
    static struct boolexp_node *test_atr(char *s, char c);
    static struct boolexp_node *parse_boolexp_R(void);
    static struct boolexp_node *parse_boolexp_L(void);
    static struct boolexp_node *parse_boolexp_O(void);
    static struct boolexp_node *parse_boolexp_C(void);
    static struct boolexp_node *parse_boolexp_I(void);
    static struct boolexp_node *parse_boolexp_A(void);
    static struct boolexp_node *parse_boolexp_F(void);
    static struct boolexp_node *parse_boolexp_T(void);
    static struct boolexp_node *parse_boolexp_E(void);
    static int check_attrib_lock(dbref player, dbref target,
                                 const char *atrname, const char *str);
    static void free_boolexp_node(struct boolexp_node *b);
    static int gen_label_id(struct bvm_asm *a);
    static void append_insn(struct bvm_asm *a, bvm_opcode op, int arg,
                            const char *s);
    static struct bvm_asm *generate_bvm_asm(struct boolexp_node *b)
 __attribute_malloc__;
    static void generate_bvm_asm1(struct bvm_asm *a, struct boolexp_node *b,
                                  boolexp_type outer);
    static size_t pos_of_label(struct bvm_asm *a, int label);
    static size_t offset_to_string(struct bvm_asm *a, int c);
    static struct bvm_asmnode *insn_after_label(struct bvm_asm *a, int label);
    static void opt_thread_jumps(struct bvm_asm *a);
    static void optimize_bvm_asm(struct bvm_asm *a);
    static boolexp emit_bytecode(struct bvm_asm *a, int derefs);
    static void free_bvm_asm(struct bvm_asm *a);
#ifdef DEBUG_BYTECODE
    static int sizeof_boolexp_node(struct boolexp_node *b);
    static void print_bytecode(boolexp b);
#endif
    extern void complain
      (dbref player, dbref i, const char *name, const char *desc, ...)
  __attribute__ ((__format__(__printf__, 4, 5)));
    void check_lock(dbref player, dbref i, const char *name, boolexp be);
    int warning_lock_type(const boolexp l);


/** String tree of attribute names. Used in the parse tree. Might go
 * away as the trees aren't persistant any more. */
    extern StrTree atr_names;
/** String tree of lock names. Used in the parse tree. Might go away
 * as the trees aren't persistant any more. */
    extern StrTree lock_names;
/** Are we currently loading the db? If so, we avoid certain checks that
 * would create a circularity.
 */
    extern int loading_db;

/** Given a chunk id, return the bytecode for a boolexp.  
 * \param b the boolexp to retrieve.
 * \return a malloced copy of the bytecode.
 */
    static uint8_t *safe_get_bytecode(boolexp b)
{
  uint8_t *bytecode;
  uint16_t len;

  len = chunk_len(b);
  bytecode = mush_malloc(len, "boolexp.bytecode");
  chunk_fetch(b, bytecode, len);
  return bytecode;
}

/** Given a chunk id, return the bytecode for a boolexp.  
 * \param b The boolexp to retrieve.
 * \param storelen the length of the bytecode.
 * \return a static copy of the bytecode.
 */
static uint8_t *
get_bytecode(boolexp b, uint16_t * storelen)
{
  static uint8_t bytecode[BUFFER_LEN * 2];
  uint16_t len;

  len = chunk_fetch(b, bytecode, sizeof bytecode);
  if (storelen)
    *storelen = len;
  return bytecode;
}

/* Public functions */

/** Copy a boolexp.
 * This function makes a copy of a boolexp, allocating new memory for
 * the copy.
 * \param b a boolexp to copy.
 * \return an allocated copy of the boolexp.
 */
boolexp
dup_bool(boolexp b)
{
  boolexp r;
  uint8_t *bytecode;
  uint16_t len = 0;

  if (b == TRUE_BOOLEXP)
    return TRUE_BOOLEXP;

  bytecode = get_bytecode(b, &len);

  r = chunk_create(bytecode, len, 1);

  return r;
}

/** Free a boolexp
 * This function deallocates a boolexp
 * \param b a boolexp to delete
 */
void
free_boolexp(boolexp b)
{
  if (b != TRUE_BOOLEXP)
    chunk_delete(b);
}

/** Determine the memory usage of a boolexp.
 * This function computes the total memory usage of a boolexp.
 * \param b boolexp to analyze.
 * \return size of boolexp in bytes.
 */
int
sizeof_boolexp(boolexp b)
{

  if (b == TRUE_BOOLEXP)
    return 0;
  else
    return (int) chunk_len(b);
}

/** Evaluate a boolexp.
 * This is the main function to be called by other hardcode. It
 * determines whether a player can pass a boolexp lock on a given
 * object.
 * \param player the player trying to pass the lock.
 * \param b the boolexp to evaluate.
 * \param target the object with the lock.
 * \retval 0 player fails to pass lock.
 * \retval 1 player successfully passes lock.
 */
int
eval_boolexp(dbref player /* The player trying to pass */ ,
             boolexp b /* The boolexp */ ,
             dbref target /* The object with the lock */ )
{
  static int boolexp_recursion = 0;

  if (!GoodObject(player))
    return 0;

  if (boolexp_recursion > MAX_DEPTH) {
    notify(player, T("Too much recursion in lock!"));
    return 0;
  }
  if (b == TRUE_BOOLEXP) {
    return 1;
  } else {
    bvm_opcode op;
    int arg;
    ATTR *a;
    int r = 0;
    char *s = NULL;
    uint8_t *bytecode, *pc;

    bytecode = pc = safe_get_bytecode(b);

    while (1) {
      op = (bvm_opcode) *pc;
      memcpy(&arg, pc + 1, sizeof arg);
      pc += INSN_LEN;
      switch (op) {
      case OP_RET:
        goto done;
      case OP_JMPT:
        if (r)
          pc = bytecode + arg;
        break;
      case OP_JMPF:
        if (!r)
          pc = bytecode + arg;
        break;
      case OP_LABEL:
      case OP_PAREN:
        break;
      case OP_LOADS:
        s = (char *) (bytecode + arg);
        break;
      case OP_LOADR:
        r = arg;
        break;
      case OP_NEGR:
        r = !r;
        break;
      case OP_TCONST:
        r = (GoodObject(arg)
             && !IsGarbage(arg)
             && (arg == player || member(arg, Contents(player))));
        break;
      case OP_TIS:
        r = (GoodObject(arg)
             && !IsGarbage(arg)
             && arg == player);
        break;
      case OP_TCARRY:
        r = (GoodObject(arg)
             && !IsGarbage(arg)
             && member(arg, Contents(player)));
        break;
      case OP_TOWNER:
        r = (GoodObject(arg)
             && !IsGarbage(arg)
             && Owner(arg) == Owner(player));
        break;
      case OP_TIND:
        /* We only allow evaluation of indirect locks if target can run
         * the lock on the referenced object.
         */
        boolexp_recursion++;
        if (!GoodObject(arg) || IsGarbage(arg))
          r = 0;
        else if (!Can_Read_Lock(target, arg, s))
          r = 0;
        else
          r = eval_boolexp(player, getlock(arg, s), arg);
        boolexp_recursion--;
        break;
      case OP_TATR:
        boolexp_recursion++;
        a = atr_get(player, s);
        if (!a || !Can_Read_Attr(target, player, a))
          r = 0;
        else {
          char tbuf[BUFFER_LEN];
          strcpy(tbuf, atr_value(a));
          r = local_wild_match((char *) bytecode + arg, tbuf);
        }
        boolexp_recursion--;
        break;
      case OP_TEVAL:
        boolexp_recursion++;
        r = check_attrib_lock(player, target, s, (char *) bytecode + arg);
        boolexp_recursion--;
        break;
      case OP_TFLAG:
        /* Note that both fields of a boolattr struct are upper-cased */
        if (sees_flag("FLAG", target, player, (char *) bytecode + arg))
          r = 1;
        else
          r = 0;
        break;
      case OP_TPOWER:
        if (sees_flag("POWER", target, player, (char *) bytecode + arg))
          r = 1;
        else
          r = 0;
        break;
      case OP_TOBJID:
        {
          dbref d;
          d = parse_objid((char *) bytecode + arg);
          r = (player == d);
          break;
        }
      case OP_TCHANNEL:
        {
          CHAN *chan;
          boolexp_recursion++;
          find_channel((char *) bytecode + arg, &chan, target);
          r = chan && onchannel(player, chan);
          boolexp_recursion--;
        }
        break;
      case OP_TIP:
        boolexp_recursion++;
        if (!Connected(Owner(player)))
          r = 0;
        else {
          /* We use the attribute for permission checks, but we
           * do the actual boolexp itself with the least idle
           * descriptor's ip address.
           */
          a = atr_get(Owner(player), "LASTIP");
          if (!a || !Can_Read_Attr(target, player, a))
            r = 0;
          else {
            char *p = least_idle_ip(Owner(player));
            r = p ? quick_wild((char *) bytecode + arg, p) : 0;
          }
        }
        boolexp_recursion--;
        break;
      case OP_THOSTNAME:
        boolexp_recursion++;
        if (!Connected(Owner(player)))
          r = 0;
        else {
          /* See comment for OP_TIP */
          a = atr_get(Owner(player), "LASTSITE");
          if (!a || !Can_Read_Attr(target, player, a))
            r = 0;
          else {
            char *p = least_idle_hostname(Owner(player));
            r = p ? quick_wild((char *) bytecode + arg, p) : 0;
          }
        }
        boolexp_recursion--;
        break;
      case OP_TTYPE:
        switch (bytecode[arg]) {
        case 'R':
          r = Typeof(player) == TYPE_ROOM;
          break;
        case 'E':
          r = Typeof(player) == TYPE_EXIT;
          break;
        case 'T':
          r = Typeof(player) == TYPE_THING;
          break;
        case 'P':
          r = Typeof(player) == TYPE_PLAYER;
          break;
        }
        break;
      case OP_TDBREFLIST: