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
29s_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
38s_list::s_list()
39{
40}
41
42static void
43skip_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
57static s_expression *
58read_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
98static 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
128s_expression *
129s_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
147void s_int::print()
148{
149   printf("%d", this->val);
150}
151
152void s_float::print()
153{
154   printf("%f", this->val);
155}
156
157void s_symbol::print()
158{
159   printf("%s", this->str);
160}
161
162void 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
176bool
177s_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
196bool
197s_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}
220