| /* -*- c++ -*- */ |
| /* |
| * Copyright © 2010 Intel Corporation |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice (including the next |
| * paragraph) shall be included in all copies or substantial portions of the |
| * Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| * DEALINGS IN THE SOFTWARE. |
| */ |
| |
| #include <assert.h> |
| #include <stdio.h> |
| #include <math.h> |
| #include "s_expression.h" |
| |
| s_symbol::s_symbol(const char *str, size_t n) |
| { |
| /* Assume the given string is already nul-terminated and in memory that |
| * will live as long as this node. |
| */ |
| assert(str[n] == '\0'); |
| this->str = str; |
| } |
| |
| s_list::s_list() |
| { |
| } |
| |
| static void |
| skip_whitespace(const char *&src, char *&symbol_buffer) |
| { |
| size_t n = strspn(src, " \v\t\r\n"); |
| src += n; |
| symbol_buffer += n; |
| /* Also skip Scheme-style comments: semi-colon 'til end of line */ |
| if (src[0] == ';') { |
| n = strcspn(src, "\n"); |
| src += n; |
| symbol_buffer += n; |
| skip_whitespace(src, symbol_buffer); |
| } |
| } |
| |
| static s_expression * |
| read_atom(void *ctx, const char *&src, char *&symbol_buffer) |
| { |
| s_expression *expr = NULL; |
| |
| skip_whitespace(src, symbol_buffer); |
| |
| size_t n = strcspn(src, "( \v\t\r\n);"); |
| if (n == 0) |
| return NULL; // no atom |
| |
| // Check for the special symbol '+INF', which means +Infinity. Note: C99 |
| // requires strtof to parse '+INF' as +Infinity, but we still support some |
| // non-C99-compliant compilers (e.g. MSVC). |
| if (n == 4 && strncmp(src, "+INF", 4) == 0) { |
| expr = new(ctx) s_float(INFINITY); |
| } else { |
| // Check if the atom is a number. |
| char *float_end = NULL; |
| float f = _mesa_strtof(src, &float_end); |
| if (float_end != src) { |
| char *int_end = NULL; |
| int i = strtol(src, &int_end, 10); |
| // If strtof matched more characters, it must have a decimal part |
| if (float_end > int_end) |
| expr = new(ctx) s_float(f); |
| else |
| expr = new(ctx) s_int(i); |
| } else { |
| // Not a number; return a symbol. |
| symbol_buffer[n] = '\0'; |
| expr = new(ctx) s_symbol(symbol_buffer, n); |
| } |
| } |
| |
| src += n; |
| symbol_buffer += n; |
| |
| return expr; |
| } |
| |
| static s_expression * |
| __read_expression(void *ctx, const char *&src, char *&symbol_buffer) |
| { |
| s_expression *atom = read_atom(ctx, src, symbol_buffer); |
| if (atom != NULL) |
| return atom; |
| |
| skip_whitespace(src, symbol_buffer); |
| if (src[0] == '(') { |
| ++src; |
| ++symbol_buffer; |
| |
| s_list *list = new(ctx) s_list; |
| s_expression *expr; |
| |
| while ((expr = __read_expression(ctx, src, symbol_buffer)) != NULL) { |
| list->subexpressions.push_tail(expr); |
| } |
| skip_whitespace(src, symbol_buffer); |
| if (src[0] != ')') { |
| printf("Unclosed expression (check your parenthesis).\n"); |
| return NULL; |
| } |
| ++src; |
| ++symbol_buffer; |
| return list; |
| } |
| return NULL; |
| } |
| |
| s_expression * |
| s_expression::read_expression(void *ctx, const char *&src) |
| { |
| assert(src != NULL); |
| |
| /* When we encounter a Symbol, we need to save a nul-terminated copy of |
| * the string. However, ralloc_strndup'ing every individual Symbol is |
| * extremely expensive. We could avoid this by simply overwriting the |
| * next character (guaranteed to be whitespace, parens, or semicolon) with |
| * a nul-byte. But overwriting non-whitespace would mess up parsing. |
| * |
| * So, just copy the whole buffer ahead of time. Walk both, leaving the |
| * original source string unmodified, and altering the copy to contain the |
| * necessary nul-bytes whenever we encounter a symbol. |
| */ |
| char *symbol_buffer = ralloc_strdup(ctx, src); |
| return __read_expression(ctx, src, symbol_buffer); |
| } |
| |
| void s_int::print() |
| { |
| printf("%d", this->val); |
| } |
| |
| void s_float::print() |
| { |
| printf("%f", this->val); |
| } |
| |
| void s_symbol::print() |
| { |
| printf("%s", this->str); |
| } |
| |
| void s_list::print() |
| { |
| printf("("); |
| foreach_in_list(s_expression, expr, &this->subexpressions) { |
| expr->print(); |
| if (!expr->next->is_tail_sentinel()) |
| printf(" "); |
| } |
| printf(")"); |
| } |
| |
| // -------------------------------------------------- |
| |
| bool |
| s_pattern::match(s_expression *expr) |
| { |
| switch (type) |
| { |
| case EXPR: *p_expr = expr; break; |
| case LIST: if (expr->is_list()) *p_list = (s_list *) expr; break; |
| case SYMBOL: if (expr->is_symbol()) *p_symbol = (s_symbol *) expr; break; |
| case NUMBER: if (expr->is_number()) *p_number = (s_number *) expr; break; |
| case INT: if (expr->is_int()) *p_int = (s_int *) expr; break; |
| case STRING: |
| s_symbol *sym = SX_AS_SYMBOL(expr); |
| if (sym != NULL && strcmp(sym->value(), literal) == 0) |
| return true; |
| return false; |
| }; |
| |
| return *p_expr == expr; |
| } |
| |
| bool |
| s_match(s_expression *top, unsigned n, s_pattern *pattern, bool partial) |
| { |
| s_list *list = SX_AS_LIST(top); |
| if (list == NULL) |
| return false; |
| |
| unsigned i = 0; |
| foreach_in_list(s_expression, expr, &list->subexpressions) { |
| if (i >= n) |
| return partial; /* More actual items than the pattern expected */ |
| |
| if (expr == NULL || !pattern[i].match(expr)) |
| return false; |
| |
| i++; |
| } |
| |
| if (i < n) |
| return false; /* Less actual items than the pattern expected */ |
| |
| return true; |
| } |