src/compiler/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 <stdio.h>
  27 #include <math.h>
  28 #include <string.h>
  29 #include <stdlib.h>
  30 #include "s_expression.h"
  31
  32 s_symbol::s_symbol(const char *str, size_t n)
  33 {
  34    /* Assume the given string is already nul-terminated and in memory that
  35     * will live as long as this node.
  36     */
  37    assert(str[n] == '\0');
  38    this->str = str;
  39 }
  40
  41 s_list::s_list()
  42 {
  43 }
  44
  45 static void
  46 skip_whitespace(const char *&src, char *&symbol_buffer)
  47 {
  48    size_t n = strspn(src, " \v\t\r\n");
  49    src += n;
  50    symbol_buffer += n;
  51    /* Also skip Scheme-style comments: semi-colon 'til end of line */
  52    if (src[0] == ';') {
  53       n = strcspn(src, "\n");
  54       src += n;
  55       symbol_buffer += n;
  56       skip_whitespace(src, symbol_buffer);
  57    }
  58 }
  59
  60 static s_expression *
  61 read_atom(void *ctx, const char *&src, char *&symbol_buffer)
  62 {
  63    s_expression *expr = NULL;
  64
  65    skip_whitespace(src, symbol_buffer);
  66
  67    size_t n = strcspn(src, "( \v\t\r\n);");
  68    if (n == 0)
  69       return NULL; // no atom
  70
  71    // Check for the special symbol '+INF', which means +Infinity.  Note: C99
  72    // requires strtof to parse '+INF' as +Infinity, but we still support some
  73    // non-C99-compliant compilers (e.g. MSVC).
  74    if (n == 4 && strncmp(src, "+INF", 4) == 0) {
  75       expr = new(ctx) s_float(INFINITY);
  76    } else {
  77       // Check if the atom is a number.
  78       char *float_end = NULL;
  79       float f = _mesa_strtof(src, &float_end);
  80       if (float_end != src) {
  81          char *int_end = NULL;
  82          int i = strtol(src, &int_end, 10);
  83          // If strtof matched more characters, it must have a decimal part
  84          if (float_end > int_end)
  85             expr = new(ctx) s_float(f);
  86          else
  87             expr = new(ctx) s_int(i);
  88       } else {
  89          // Not a number; return a symbol.
  90          symbol_buffer[n] = '\0';
  91          expr = new(ctx) s_symbol(symbol_buffer, n);
  92       }
  93    }
  94
  95    src += n;
  96    symbol_buffer += n;
  97
  98    return expr;
  99 }
 100
 101 static s_expression *
 102 __read_expression(void *ctx, const char *&src, char *&symbol_buffer)
 103 {
 104    s_expression *atom = read_atom(ctx, src, symbol_buffer);
 105    if (atom != NULL)
 106       return atom;
 107
 108    skip_whitespace(src, symbol_buffer);
 109    if (src[0] == '(') {
 110       ++src;
 111       ++symbol_buffer;
 112
 113       s_list *list = new(ctx) s_list;
 114       s_expression *expr;
 115
 116       while ((expr = __read_expression(ctx, src, symbol_buffer)) != NULL) {
 117          list->subexpressions.push_tail(expr);
 118       }
 119       skip_whitespace(src, symbol_buffer);
 120       if (src[0] != ')') {
 121          printf("Unclosed expression (check your parenthesis).\n");
 122          return NULL;
 123       }
 124       ++src;
 125       ++symbol_buffer;
 126       return list;
 127    }
 128    return NULL;
 129 }
 130
 131 s_expression *
 132 s_expression::read_expression(void *ctx, const char *&src)
 133 {
 134    assert(src != NULL);
 135
 136    /* When we encounter a Symbol, we need to save a nul-terminated copy of
 137     * the string.  However, ralloc_strndup'ing every individual Symbol is
 138     * extremely expensive.  We could avoid this by simply overwriting the
 139     * next character (guaranteed to be whitespace, parens, or semicolon) with
 140     * a nul-byte.  But overwriting non-whitespace would mess up parsing.
 141     *
 142     * So, just copy the whole buffer ahead of time.  Walk both, leaving the
 143     * original source string unmodified, and altering the copy to contain the
 144     * necessary nul-bytes whenever we encounter a symbol.
 145     */
 146    char *symbol_buffer = ralloc_strdup(ctx, src);
 147    return __read_expression(ctx, src, symbol_buffer);
 148 }
 149
 150 void s_int::print()
 151 {
 152    printf("%d", this->val);
 153 }
 154
 155 void s_float::print()
 156 {
 157    printf("%f", this->val);
 158 }
 159
 160 void s_symbol::print()
 161 {
 162    printf("%s", this->str);
 163 }
 164
 165 void s_list::print()
 166 {
 167    printf("(");
 168    foreach_in_list(s_expression, expr, &this->subexpressions) {
 169       expr->print();
 170       if (!expr->next->is_tail_sentinel())
 171          printf(" ");
 172    }
 173    printf(")");
 174 }
 175
 176 // --------------------------------------------------
 177
 178 bool
 179 s_pattern::match(s_expression *expr)
 180 {
 181    switch (type)
 182    {
 183    case EXPR:   *p_expr = expr; break;
 184    case LIST:   if (expr->is_list())   *p_list   = (s_list *)   expr; break;
 185    case SYMBOL: if (expr->is_symbol()) *p_symbol = (s_symbol *) expr; break;
 186    case NUMBER: if (expr->is_number()) *p_number = (s_number *) expr; break;
 187    case INT:    if (expr->is_int())    *p_int    = (s_int *)    expr; break;
 188    case STRING:
 189       s_symbol *sym = SX_AS_SYMBOL(expr);
 190       if (sym != NULL && strcmp(sym->value(), literal) == 0)
 191          return true;
 192       return false;
 193    };
 194
 195    return *p_expr == expr;
 196 }
 197
 198 bool
 199 s_match(s_expression *top, unsigned n, s_pattern *pattern, bool partial)
 200 {
 201    s_list *list = SX_AS_LIST(top);
 202    if (list == NULL)
 203       return false;
 204
 205    unsigned i = 0;
 206    foreach_in_list(s_expression, expr, &list->subexpressions) {
 207       if (i >= n)
 208          return partial; /* More actual items than the pattern expected */
 209
 210       if (expr == NULL || !pattern[i].match(expr))
 211          return false;
 212
 213       i++;
 214    }
 215
 216    if (i < n)
 217       return false; /* Less actual items than the pattern expected */
 218
 219    return true;
 220 }