1 /**
2 * \file z-expression.c
3 * \brief Creating, storing, and deserializing simple math expressions
4 *
5 * Copyright (c) 2013 Ben Semmler
6 *
7 * This work is free software; you can redistribute it and/or modify it
8 * under the terms of either:
9 *
10 * a) the GNU General Public License as published by the Free Software
11 * Foundation, version 2, or
12 *
13 * b) the "Angband licence":
14 * This software may be copied and distributed for educational, research,
15 * and not for profit purposes provided that this copyright and statement
16 * are included in all such copies. Other copyrights may also apply.
17 */
18
19 #include "z-expression.h"
20 #include "z-virt.h"
21 #include "z-util.h"
22
23 struct expression_operation_s {
24 byte operator;
25 s16b operand;
26 };
27
28 struct expression_s {
29 expression_base_value_f base_value;
30 size_t operation_count;
31 size_t operations_size;
32 expression_operation_t *operations;
33 };
34
35 /**
36 * Operator types.
37 */
38 typedef enum expression_operator_e {
39 OPERATOR_NONE,
40 OPERATOR_ADD,
41 OPERATOR_SUB,
42 OPERATOR_MUL,
43 OPERATOR_DIV,
44 OPERATOR_NEG,
45 } expression_operator_t;
46
47 /**
48 * States for parser state table.
49 */
50 typedef enum expression_state_e {
51 EXPRESSION_STATE_START,
52 EXPRESSION_STATE_OPERATOR,
53 EXPRESSION_STATE_OPERAND,
54 EXPRESSION_STATE_MAX,
55 } expression_state_t;
56
57 /**
58 * Input types for parser state table.
59 */
60 typedef enum expression_input_e {
61 EXPRESSION_INPUT_INVALID,
62 EXPRESSION_INPUT_NEEDS_OPERANDS,
63 EXPRESSION_INPUT_UNARY_OPERATOR,
64 EXPRESSION_INPUT_VALUE,
65 EXPRESSION_INPUT_MAX,
66 } expression_input_t;
67
68 /**
69 * Allocation block size for the operations array in expression_t.
70 */
71 #define EXPRESSION_ALLOC_SIZE 5
72
73 /**
74 * Token delimiter for the parser.
75 */
76 #define EXPRESSION_DELIMITER " "
77
78 /**
79 * Maximum number of operations in an expression. This number is used in the
80 * parser to allocate an array of expression_operation_t.
81 */
82 #define EXPRESSION_MAX_OPERATIONS 50
83
84 /**
85 * Return an operator type based on the input token.
86 */
expression_operator_from_token(const char * token)87 static expression_operator_t expression_operator_from_token(const char *token)
88 {
89 switch (token[0]) {
90 case '+':
91 return OPERATOR_ADD;
92 case '-':
93 return OPERATOR_SUB;
94 case '*':
95 return OPERATOR_MUL;
96 case '/':
97 return OPERATOR_DIV;
98 case 'n':
99 case 'N':
100 return OPERATOR_NEG;
101 }
102
103 return OPERATOR_NONE;
104 }
105
106 /**
107 * Return the state table input type for a given operator type.
108 */
expression_input_for_operator(expression_operator_t operator)109 static expression_input_t expression_input_for_operator(expression_operator_t operator)
110 {
111 switch (operator) {
112 case OPERATOR_NONE:
113 return EXPRESSION_INPUT_INVALID;
114 case OPERATOR_ADD:
115 case OPERATOR_SUB:
116 case OPERATOR_MUL:
117 case OPERATOR_DIV:
118 return EXPRESSION_INPUT_NEEDS_OPERANDS;
119 case OPERATOR_NEG:
120 return EXPRESSION_INPUT_UNARY_OPERATOR;
121 }
122
123 return EXPRESSION_INPUT_INVALID;
124 }
125
126 /**
127 * Allocate and initialize a new expression object. Returns NULL if it was
128 * unable to be created.
129 */
expression_new(void)130 expression_t *expression_new(void)
131 {
132 expression_t *expression = mem_zalloc(sizeof(expression_t));
133
134 if (expression == NULL)
135 return NULL;
136
137 expression->base_value = NULL;
138 expression->operation_count = 0;
139 expression->operations_size = EXPRESSION_ALLOC_SIZE;
140 expression->operations = mem_zalloc(expression->operations_size *
141 sizeof(expression_operation_t));
142
143 if (expression->operations == NULL) {
144 mem_free(expression);
145 return NULL;
146 }
147
148 return expression;
149 }
150
151 /**
152 * Deallocate an expression object.
153 */
expression_free(expression_t * expression)154 void expression_free(expression_t *expression)
155 {
156 if (expression == NULL)
157 return;
158
159 if (expression->operations != NULL) {
160 mem_free(expression->operations);
161 expression->operations = NULL;
162 }
163
164 mem_free(expression);
165 }
166
167 /**
168 * Return a deep copy of the given expression.
169 */
expression_copy(const expression_t * source)170 expression_t *expression_copy(const expression_t *source)
171 {
172 size_t i;
173 expression_t *copy = mem_zalloc(sizeof(expression_t));
174
175 if (copy == NULL)
176 return NULL;
177
178 copy->base_value = source->base_value;
179 copy->operation_count = source->operation_count;
180 copy->operations_size = source->operations_size;
181
182 if (copy->operations_size == 0) {
183 copy->operations = NULL;
184 return copy;
185 }
186
187 copy->operations = mem_zalloc(copy->operations_size *
188 sizeof(expression_operation_t));
189
190 if (copy->operations == NULL && source->operations != NULL) {
191 mem_free(copy);
192 return NULL;
193 }
194
195 for (i = 0; i < copy->operation_count; i++) {
196 copy->operations[i].operand = source->operations[i].operand;
197 copy->operations[i].operator = source->operations[i].operator;
198 }
199
200 return copy;
201 }
202
203 /**
204 * Set the base value function that the operations operate on.
205 */
expression_set_base_value(expression_t * expression,expression_base_value_f function)206 void expression_set_base_value(expression_t *expression,
207 expression_base_value_f function)
208 {
209 expression->base_value = function;
210 }
211
212 /**
213 * Evaluate the given expression. If the base value function is NULL,
214 * expression is evaluated from zero.
215 */
expression_evaluate(expression_t const * const expression)216 s32b expression_evaluate(expression_t const * const expression)
217 {
218 size_t i;
219 s32b value = 0;
220
221 if (expression->base_value != NULL)
222 value = expression->base_value();
223
224 for (i = 0; i < expression->operation_count; i++) {
225 switch (expression->operations[i].operator) {
226 case OPERATOR_ADD:
227 value += expression->operations[i].operand;
228 break;
229 case OPERATOR_SUB:
230 value -= expression->operations[i].operand;
231 break;
232 case OPERATOR_MUL:
233 value *= expression->operations[i].operand;
234 break;
235 case OPERATOR_DIV:
236 value /= expression->operations[i].operand;
237 break;
238 case OPERATOR_NEG:
239 value = -value;
240 break;
241 default:
242 break;
243 }
244 }
245
246 return value;
247 }
248
249 /**
250 * Add an operation to an expression, allocating more memory as needed.
251 */
expression_add_operation(expression_t * expression,const expression_operation_t operation)252 static void expression_add_operation(expression_t *expression,
253 const expression_operation_t operation)
254 {
255 if (expression->operation_count >= expression->operations_size) {
256 expression->operations_size += EXPRESSION_ALLOC_SIZE;
257 expression->operations = mem_realloc(expression->operations, expression->operations_size * sizeof(expression_operation_t));
258 }
259
260 expression->operations[expression->operation_count] = operation;
261 expression->operation_count++;
262 }
263
264 /**
265 * Parse a string and add operations and operands to an expression.
266 *
267 * The string must be in prefix notation and must start with an operator.
268 * Basic operators (add, subtract, multiply, and divide) can have multiple
269 * operands after the operator. Unary operators (negation) must be followed
270 * by another operator. Parsing is done using a state table which is
271 * contained in the function.
272 *
273 * \param expression is an initialized expression object.
274 * \param string is the string to be parsed.
275 * \return The number of operations added to the expression or an error (expression_err_e).
276 */
expression_add_operations_string(expression_t * expression,const char * string)277 s16b expression_add_operations_string(expression_t *expression,
278 const char *string)
279 {
280 char *parse_string;
281 expression_operation_t operations[EXPRESSION_MAX_OPERATIONS];
282 size_t count = 0, i = 0;
283 char *token = NULL;
284 expression_operator_t parsed_operator = OPERATOR_NONE;
285 expression_operator_t current_operator = OPERATOR_NONE;
286 expression_input_t current_input = EXPRESSION_INPUT_INVALID;
287 int state = EXPRESSION_STATE_START;
288
289 /* The named initializers are left commented out for when this all goes
290 * to C99. */
291 static int state_table[EXPRESSION_STATE_MAX][EXPRESSION_INPUT_MAX] = {
292 /*[EXPRESSION_STATE_START] = */{
293 /*[EXPRESSION_INPUT_INVALID] = */ EXPRESSION_ERR_INVALID_OPERATOR,
294 /*[EXPRESSION_INPUT_NEEDS_OPERANDS] = */ EXPRESSION_STATE_OPERATOR,
295 /*[EXPRESSION_INPUT_UNARY_OPERATOR] = */ EXPRESSION_STATE_START,
296 /*[EXPRESSION_INPUT_VALUE] = */ EXPRESSION_ERR_EXPECTED_OPERATOR,
297 },
298
299 /* found operator */
300 /*[EXPRESSION_STATE_OPERATOR] = */{
301 /*[EXPRESSION_INPUT_INVALID] = */ EXPRESSION_ERR_INVALID_OPERATOR,
302 /*[EXPRESSION_INPUT_NEEDS_OPERANDS] = */ EXPRESSION_ERR_EXPECTED_OPERAND,
303 /*[EXPRESSION_INPUT_UNARY_OPERATOR] = */ EXPRESSION_ERR_EXPECTED_OPERAND,
304 /*[EXPRESSION_INPUT_VALUE] = */ EXPRESSION_STATE_OPERAND,
305 },
306
307 /* found one operand */
308 /*[EXPRESSION_STATE_OPERAND] = */{
309 /*[EXPRESSION_INPUT_INVALID] = */ EXPRESSION_ERR_INVALID_OPERATOR,
310 /*[EXPRESSION_INPUT_NEEDS_OPERANDS] = */ EXPRESSION_STATE_OPERATOR,
311 /*[EXPRESSION_INPUT_UNARY_OPERATOR] = */ EXPRESSION_STATE_START,
312 /*[EXPRESSION_INPUT_VALUE] = */ EXPRESSION_STATE_OPERAND,
313 },
314 };
315
316 if (expression == NULL || string == NULL)
317 return EXPRESSION_ERR_GENERIC;
318
319 /* Empty string is an identity operation. */
320 if (my_stricmp(string, "") == 0)
321 return 0;
322
323 parse_string = string_make(string);
324 token = strtok(parse_string, EXPRESSION_DELIMITER);
325
326 while (token != NULL) {
327 char *end = NULL;
328 s16b value = strtol(token, &end, 0);
329
330 if (end == token) {
331 parsed_operator = expression_operator_from_token(token);
332 current_input = expression_input_for_operator(parsed_operator);
333 state = state_table[state][current_input];
334 }
335 else {
336 state = state_table[state][EXPRESSION_INPUT_VALUE];
337 }
338
339 /* Perform actions based on the new state. */
340 if (state < EXPRESSION_STATE_START) {
341 /* An error occurred, according to the state table. */
342 string_free(parse_string);
343 return state;
344 }
345 else if (state == EXPRESSION_STATE_START) {
346 /* Flush the operation, since we are restarting or using a
347 * unary operator. */
348 operations[count].operator = parsed_operator;
349 operations[count].operand = 0;
350 count++;
351 }
352 else if (state == EXPRESSION_STATE_OPERATOR) {
353 /* Remember the operator, since we found an operator which needs
354 * operands. */
355 current_operator = parsed_operator;
356 }
357 else if (state == EXPRESSION_STATE_OPERAND) {
358 /* Try to catch divide by zero. */
359 if (current_operator == OPERATOR_DIV && value == 0) {
360 string_free(parse_string);
361 return EXPRESSION_ERR_DIVIDE_BY_ZERO;
362 }
363
364 /* Flush the operator and operand pair. */
365 operations[count].operator = current_operator;
366 operations[count].operand = value;
367 count++;
368 }
369
370 /* Limit the number of expressions, saving what we have. */
371 if (count >= N_ELEMENTS(operations))
372 break;
373
374 token = strtok(NULL, EXPRESSION_DELIMITER);
375 }
376
377 for (i = 0; i < count; i++) {
378 expression_add_operation(expression, operations[i]);
379 }
380
381 string_free(parse_string);
382 return count;
383 }
384
385 /**
386 * Test to make sure that the deep copy from expression_copy() is equal in value
387 */
expression_test_copy(const expression_t * a,const expression_t * b)388 bool expression_test_copy(const expression_t *a, const expression_t *b)
389 {
390 size_t i;
391 bool success = true;
392
393 if (a == NULL || b == NULL)
394 return false;
395
396 success &= (a != b);
397 success &= (a->base_value == b->base_value);
398 success &= (a->operation_count == b->operation_count);
399 success &= (a->operations_size == b->operations_size);
400 success &= (a->operations != b->operations);
401
402 if (a->operation_count != b->operation_count)
403 return false;
404
405 for (i = 0; i < a->operation_count; i++) {
406 success &= (a->operations[i].operand == b->operations[i].operand);
407 success &= (a->operations[i].operator == b->operations[i].operator);
408 }
409
410 return success;
411 }
412