src/glsl/s_expression.cpp

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright © 2010 Intel Corporation
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice (including the next
  13  * paragraph) shall be included in all copies or substantial portions of the
  14  * Software.
  15  *
  16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  22  * DEALINGS IN THE SOFTWARE.
  23  */
  24
  25 #include <assert.h>
  26 #include <limits>
  27 #include "s_expression.h"
  28
  29 s_symbol::s_symbol(const char *str, size_t n)
  30 {
  31    /* Assume the given string is already nul-terminated and in memory that
  32     * will live as long as this node.
  33     */
  34    assert(str[n] == '\0');
  35    this->str = str;
  36 }
  37
  38 s_list::s_list()
  39 {
  40 }
  41
  42 static void
  43 skip_whitespace(const char *&src, char *&symbol_buffer)
  44 {
  45    size_t n = strspn(src, " \v\t\r\n");
  46    src += n;
  47    symbol_buffer += n;
  48    /* Also skip Scheme-style comments: semi-colon 'til end of line */
  49    if (src[0] == ';') {
  50       n = strcspn(src, "\n");
  51       src += n;
  52       symbol_buffer += n;
  53       skip_whitespace(src, symbol_buffer);
  54    }
  55 }
  56
  57 static s_expression *
  58 read_atom(void *ctx, const char *&src, char *&symbol_buffer)
  59 {
  60    s_expression *expr = NULL;
  61
  62    skip_whitespace(src, symbol_buffer);
  63
  64    size_t n = strcspn(src, "( \v\t\r\n);");
  65    if (n == 0)
  66       return NULL; // no atom
  67
  68    // Check for the special symbol '+INF', which means +Infinity.  Note: C99
  69    // requires strtod to parse '+INF' as +Infinity, but we still support some
  70    // non-C99-compliant compilers (e.g. MSVC).
  71    if (n == 4 && strncmp(src, "+INF", 4) == 0) {
  72       expr = new(ctx) s_float(std::numeric_limits<float>::infinity());
  73    } else {
  74       // Check if the atom is a number.
  75       char *float_end = NULL;
  76       double f = glsl_strtod(src, &float_end);
  77       if (float_end != src) {
  78          char *int_end = NULL;
  79          int i = strtol(src, &int_end, 10);
  80          // If strtod matched more characters, it must have a decimal part
  81          if (float_end > int_end)
  82             expr = new(ctx) s_float(f);
  83          else
  84             expr = new(ctx) s_int(i);
  85       } else {
  86          // Not a number; return a symbol.
  87          symbol_buffer[n] = '\0';
  88          expr = new(ctx) s_symbol(symbol_buffer, n);
  89       }
  90    }
  91
  92    src += n;
  93    symbol_buffer += n;
  94
  95    return expr;
  96 }
  97
  98 static s_expression *
  99 __read_expression(void *ctx, const char *&src, char *&symbol_buffer)
 100 {
 101    s_expression *atom = read_atom(ctx, src, symbol_buffer);
 102    if (atom != NULL)
 103       return atom;
 104
 105    skip_whitespace(src, symbol_buffer);
 106    if (src[0] == '(') {
 107       ++src;
 108       ++symbol_buffer;
 109
 110       s_list *list = new(ctx) s_list;
 111       s_expression *expr;
 112
 113       while ((expr = __read_expression(ctx, src, symbol_buffer)) != NULL) {
 114          list->subexpressions.push_tail(expr);
 115       }
 116       skip_whitespace(src, symbol_buffer);
 117       if (src[0] != ')') {
 118          printf("Unclosed expression (check your parenthesis).\n");
 119          return NULL;
 120       }
 121       ++src;
 122       ++symbol_buffer;
 123       return list;
 124    }
 125    return NULL;
 126 }
 127
 128 s_expression *
 129 s_expression::read_expression(void *ctx, const char *&src)
 130 {
 131    assert(src != NULL);
 132
 133    /* When we encounter a Symbol, we need to save a nul-terminated copy of
 134     * the string.  However, ralloc_strndup'ing every individual Symbol is
 135     * extremely expensive.  We could avoid this by simply overwriting the
 136     * next character (guaranteed to be whitespace, parens, or semicolon) with
 137     * a nul-byte.  But overwriting non-whitespace would mess up parsing.
 138     *
 139     * So, just copy the whole buffer ahead of time.  Walk both, leaving the
 140     * original source string unmodified, and altering the copy to contain the
 141     * necessary nul-bytes whenever we encounter a symbol.
 142     */
 143    char *symbol_buffer = ralloc_strdup(ctx, src);
 144    return __read_expression(ctx, src, symbol_buffer);
 145 }
 146
 147 void s_int::print()
 148 {
 149    printf("%d", this->val);
 150 }
 151
 152 void s_float::print()
 153 {
 154    printf("%f", this->val);
 155 }
 156
 157 void s_symbol::print()
 158 {
 159    printf("%s", this->str);
 160 }
 161
 162 void s_list::print()
 163 {
 164    printf("(");
 165    foreach_iter(exec_list_iterator, it, this->subexpressions) {
 166       s_expression *expr = (s_expression*) it.get();
 167       expr->print();
 168       if (!expr->next->is_tail_sentinel())
 169          printf(" ");
 170    }
 171    printf(")");
 172 }
 173
 174 // --------------------------------------------------
 175
 176 bool
 177 s_pattern::match(s_expression *expr)
 178 {
 179    switch (type)
 180    {
 181    case EXPR:   *p_expr = expr; break;
 182    case LIST:   if (expr->is_list())   *p_list   = (s_list *)   expr; break;
 183    case SYMBOL: if (expr->is_symbol()) *p_symbol = (s_symbol *) expr; break;
 184    case NUMBER: if (expr->is_number()) *p_number = (s_number *) expr; break;
 185    case INT:    if (expr->is_int())    *p_int    = (s_int *)    expr; break;
 186    case STRING:
 187       s_symbol *sym = SX_AS_SYMBOL(expr);
 188       if (sym != NULL && strcmp(sym->value(), literal) == 0)
 189          return true;
 190       return false;
 191    };
 192
 193    return *p_expr == expr;
 194 }
 195
 196 bool
 197 s_match(s_expression *top, unsigned n, s_pattern *pattern, bool partial)
 198 {
 199    s_list *list = SX_AS_LIST(top);
 200    if (list == NULL)
 201       return false;
 202
 203    unsigned i = 0;
 204    foreach_iter(exec_list_iterator, it, list->subexpressions) {
 205       if (i >= n)
 206          return partial; /* More actual items than the pattern expected */
 207
 208       s_expression *expr = (s_expression *) it.get();
 209       if (expr == NULL || !pattern[i].match(expr))
 210          return false;
 211
 212       i++;
 213    }
 214
 215    if (i < n)
 216       return false; /* Less actual items than the pattern expected */
 217
 218    return true;
 219 }