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
32s_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
41s_list::s_list()
42{
43}
44
45static void
46skip_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
60static s_expression *
61read_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
101static 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
131s_expression *
132s_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
150void s_int::print()
151{
152   printf("%d", this->val);
153}
154
155void s_float::print()
156{
157   printf("%f", this->val);
158}
159
160void s_symbol::print()
161{
162   printf("%s", this->str);
163}
164
165void 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
178bool
179s_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
198bool
199s_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}
221