diff options
Diffstat (limited to 'libgimpwidgets/gimpeevl.c')
| -rw-r--r-- | libgimpwidgets/gimpeevl.c | 666 |
1 files changed, 666 insertions, 0 deletions
diff --git a/libgimpwidgets/gimpeevl.c b/libgimpwidgets/gimpeevl.c new file mode 100644 index 0000000..55bf323 --- /dev/null +++ b/libgimpwidgets/gimpeevl.c @@ -0,0 +1,666 @@ +/* LIBGIMP - The GIMP Library + * Copyright (C) 1995-1997 Peter Mattis and Spencer Kimball + * + * gimpeevl.c + * Copyright (C) 2008 Fredrik Alstromer <roe@excu.se> + * Copyright (C) 2008 Martin Nordholts <martinn@svn.gnome.org> + * + * This library is free software: you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 3 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see + * <https://www.gnu.org/licenses/>. + */ + +/* Introducing eevl eva, the evaluator. A straightforward recursive + * descent parser, no fuss, no new dependencies. The lexer is hand + * coded, tedious, not extremely fast but works. It evaluates the + * expression as it goes along, and does not create a parse tree or + * anything, and will not optimize anything. It uses doubles for + * precision, with the given use case, that's enough to combat any + * rounding errors (as opposed to optimizing the evaluation). + * + * It relies on external unit resolving through a callback and does + * elementary dimensionality constraint check (e.g. "2 mm + 3 px * 4 + * in" is an error, as L + L^2 is a mismatch). It uses setjmp/longjmp + * for try/catch like pattern on error, it uses g_strtod() for numeric + * conversions and it's non-destructive in terms of the parameters, and + * it's reentrant. + * + * EBNF: + * + * expression ::= term { ('+' | '-') term }* | + * <empty string> ; + * + * term ::= ratio { ( '*' | '/' ) ratio }* ; + * + * ratio ::= signed factor { ':' signed factor }* ; + * + * signed factor ::= ( '+' | '-' )? factor ; + * + * factor ::= quantity ( '^' signed factor )? ; + * + * quantity ::= number unit? | '(' expression ')' ; + * + * number ::= ? what g_strtod() consumes ? ; + * + * unit ::= simple unit ( '^' signed factor )? ; + * + * simple unit ::= ? what not g_strtod() consumes and not whitespace ? ; + * + * The code should match the EBNF rather closely (except for the + * non-terminal unit factor, which is inlined into factor) for + * maintainability reasons. + * + * It will allow 1++1 and 1+-1 (resulting in 2 and 0, respectively), + * but I figured one might want that, and I don't think it's going to + * throw anyone off. + */ + +#include "config.h" + +#include <setjmp.h> +#include <string.h> + +#include <glib-object.h> + +#include "libgimpmath/gimpmath.h" + +#include "gimpeevl.h" +#include "gimpwidgets-error.h" + +#include "libgimp/libgimp-intl.h" + + +typedef enum +{ + GIMP_EEVL_TOKEN_NUM = 30000, + GIMP_EEVL_TOKEN_IDENTIFIER = 30001, + + GIMP_EEVL_TOKEN_ANY = 40000, + + GIMP_EEVL_TOKEN_END = 50000 +} GimpEevlTokenType; + + +typedef struct +{ + GimpEevlTokenType type; + + union + { + gdouble fl; + + struct + { + const gchar *c; + gint size; + }; + + } value; + +} GimpEevlToken; + +typedef struct +{ + const gchar *string; + GimpEevlOptions options; + + GimpEevlToken current_token; + const gchar *start_of_current_token; + + jmp_buf catcher; + const gchar *error_message; + +} GimpEevl; + + +static void gimp_eevl_init (GimpEevl *eva, + const gchar *string, + const GimpEevlOptions *options); +static GimpEevlQuantity gimp_eevl_complete (GimpEevl *eva); +static GimpEevlQuantity gimp_eevl_expression (GimpEevl *eva); +static GimpEevlQuantity gimp_eevl_term (GimpEevl *eva); +static GimpEevlQuantity gimp_eevl_ratio (GimpEevl *eva); +static GimpEevlQuantity gimp_eevl_signed_factor (GimpEevl *eva); +static GimpEevlQuantity gimp_eevl_factor (GimpEevl *eva); +static GimpEevlQuantity gimp_eevl_quantity (GimpEevl *eva); +static gboolean gimp_eevl_accept (GimpEevl *eva, + GimpEevlTokenType token_type, + GimpEevlToken *consumed_token); +static void gimp_eevl_lex (GimpEevl *eva); +static void gimp_eevl_lex_accept_count (GimpEevl *eva, + gint count, + GimpEevlTokenType token_type); +static void gimp_eevl_lex_accept_to (GimpEevl *eva, + gchar *to, + GimpEevlTokenType token_type); +static void gimp_eevl_move_past_whitespace (GimpEevl *eva); +static gboolean gimp_eevl_unit_identifier_start (gunichar c); +static gboolean gimp_eevl_unit_identifier_continue (gunichar c); +static gint gimp_eevl_unit_identifier_size (const gchar *s, + gint start); +static void gimp_eevl_expect (GimpEevl *eva, + GimpEevlTokenType token_type, + GimpEevlToken *value); +static void gimp_eevl_error (GimpEevl *eva, + gchar *msg); + + +/** + * gimp_eevl_evaluate: + * @string: The NULL-terminated string to be evaluated. + * @options: Evaluations options. + * @result: Result of evaluation. + * @error_pos: Will point to the position within the string, + * before which the parse / evaluation error + * occurred. Will be set to null of no error occurred. + * @error_message: Will point to a static string with a semi-descriptive + * error message if parsing / evaluation failed. + * + * Evaluates the given arithmetic expression, along with an optional dimension + * analysis, and basic unit conversions. + * + * All units conversions factors are relative to some implicit + * base-unit (which in GIMP is inches). This is also the unit of the + * returned value. + * + * Returns: A #GimpEevlQuantity with a value given in the base unit along with + * the order of the dimension (i.e. if the base unit is inches, a dimension + * order of two means in^2). + **/ +gboolean +gimp_eevl_evaluate (const gchar *string, + const GimpEevlOptions *options, + GimpEevlQuantity *result, + const gchar **error_pos, + GError **error) +{ + GimpEevl eva; + + g_return_val_if_fail (g_utf8_validate (string, -1, NULL), FALSE); + g_return_val_if_fail (options != NULL, FALSE); + g_return_val_if_fail (options->unit_resolver_proc != NULL, FALSE); + g_return_val_if_fail (result != NULL, FALSE); + g_return_val_if_fail (error == NULL || *error == NULL, FALSE); + + gimp_eevl_init (&eva, + string, + options); + + if (!setjmp (eva.catcher)) /* try... */ + { + *result = gimp_eevl_complete (&eva); + + return TRUE; + } + else /* catch.. */ + { + if (error_pos) + *error_pos = eva.start_of_current_token; + + g_set_error_literal (error, + GIMP_WIDGETS_ERROR, + GIMP_WIDGETS_PARSE_ERROR, + eva.error_message); + + return FALSE; + } +} + +static void +gimp_eevl_init (GimpEevl *eva, + const gchar *string, + const GimpEevlOptions *options) +{ + eva->string = string; + eva->options = *options; + + eva->current_token.type = GIMP_EEVL_TOKEN_END; + + eva->error_message = NULL; + + /* Preload symbol... */ + gimp_eevl_lex (eva); +} + +static GimpEevlQuantity +gimp_eevl_complete (GimpEevl *eva) +{ + GimpEevlQuantity result = {0, 0}; + GimpEevlQuantity default_unit_factor; + gdouble default_unit_offset; + + /* Empty expression evaluates to 0 */ + if (gimp_eevl_accept (eva, GIMP_EEVL_TOKEN_END, NULL)) + return result; + + result = gimp_eevl_expression (eva); + + /* There should be nothing left to parse by now */ + gimp_eevl_expect (eva, GIMP_EEVL_TOKEN_END, 0); + + eva->options.unit_resolver_proc (NULL, + &default_unit_factor, + &default_unit_offset, + eva->options.data); + + /* Entire expression is dimensionless, apply default unit if + * applicable + */ + if (result.dimension == 0 && default_unit_factor.dimension != 0) + { + result.value /= default_unit_factor.value; + result.value += default_unit_offset; + result.dimension = default_unit_factor.dimension; + } + return result; +} + +static GimpEevlQuantity +gimp_eevl_expression (GimpEevl *eva) +{ + gboolean subtract; + GimpEevlQuantity evaluated_terms; + + evaluated_terms = gimp_eevl_term (eva); + + /* continue evaluating terms, chained with + or -. */ + for (subtract = FALSE; + gimp_eevl_accept (eva, '+', NULL) || + (subtract = gimp_eevl_accept (eva, '-', NULL)); + subtract = FALSE) + { + GimpEevlQuantity new_term = gimp_eevl_term (eva); + + /* If dimensions mismatch, attempt default unit assignment */ + if (new_term.dimension != evaluated_terms.dimension) + { + GimpEevlQuantity default_unit_factor; + gdouble default_unit_offset; + + eva->options.unit_resolver_proc (NULL, + &default_unit_factor, + &default_unit_offset, + eva->options.data); + + if (new_term.dimension == 0 && + evaluated_terms.dimension == default_unit_factor.dimension) + { + new_term.value /= default_unit_factor.value; + new_term.value += default_unit_offset; + new_term.dimension = default_unit_factor.dimension; + } + else if (evaluated_terms.dimension == 0 && + new_term.dimension == default_unit_factor.dimension) + { + evaluated_terms.value /= default_unit_factor.value; + evaluated_terms.value += default_unit_offset; + evaluated_terms.dimension = default_unit_factor.dimension; + } + else + { + gimp_eevl_error (eva, "Dimension mismatch during addition"); + } + } + + evaluated_terms.value += (subtract ? -new_term.value : new_term.value); + } + + return evaluated_terms; +} + +static GimpEevlQuantity +gimp_eevl_term (GimpEevl *eva) +{ + gboolean division; + GimpEevlQuantity evaluated_ratios; + + evaluated_ratios = gimp_eevl_ratio (eva); + + for (division = FALSE; + gimp_eevl_accept (eva, '*', NULL) || + (division = gimp_eevl_accept (eva, '/', NULL)); + division = FALSE) + { + GimpEevlQuantity new_ratio = gimp_eevl_ratio (eva); + + if (division) + { + evaluated_ratios.value /= new_ratio.value; + evaluated_ratios.dimension -= new_ratio.dimension; + } + else + { + evaluated_ratios.value *= new_ratio.value; + evaluated_ratios.dimension += new_ratio.dimension; + } + } + + return evaluated_ratios; +} + +static GimpEevlQuantity +gimp_eevl_ratio (GimpEevl *eva) +{ + GimpEevlQuantity evaluated_signed_factors; + + if (! eva->options.ratio_expressions) + return gimp_eevl_signed_factor (eva); + + evaluated_signed_factors = gimp_eevl_signed_factor (eva); + + while (gimp_eevl_accept (eva, ':', NULL)) + { + GimpEevlQuantity new_signed_factor = gimp_eevl_signed_factor (eva); + + if (eva->options.ratio_invert) + { + GimpEevlQuantity temp; + + temp = evaluated_signed_factors; + evaluated_signed_factors = new_signed_factor; + new_signed_factor = temp; + } + + evaluated_signed_factors.value *= eva->options.ratio_quantity.value / + new_signed_factor.value; + evaluated_signed_factors.dimension += eva->options.ratio_quantity.dimension - + new_signed_factor.dimension; + } + + return evaluated_signed_factors; +} + +static GimpEevlQuantity +gimp_eevl_signed_factor (GimpEevl *eva) +{ + GimpEevlQuantity result; + gboolean negate = FALSE; + + if (! gimp_eevl_accept (eva, '+', NULL)) + negate = gimp_eevl_accept (eva, '-', NULL); + + result = gimp_eevl_factor (eva); + + if (negate) result.value = -result.value; + + return result; +} + +static GimpEevlQuantity +gimp_eevl_factor (GimpEevl *eva) +{ + GimpEevlQuantity evaluated_factor; + + evaluated_factor = gimp_eevl_quantity (eva); + + if (gimp_eevl_accept (eva, '^', NULL)) + { + GimpEevlQuantity evaluated_exponent; + + evaluated_exponent = gimp_eevl_signed_factor (eva); + + if (evaluated_exponent.dimension != 0) + gimp_eevl_error (eva, "Exponent is not a dimensionless quantity"); + + evaluated_factor.value = pow (evaluated_factor.value, + evaluated_exponent.value); + evaluated_factor.dimension *= evaluated_exponent.value; + } + + return evaluated_factor; +} + +static GimpEevlQuantity +gimp_eevl_quantity (GimpEevl *eva) +{ + GimpEevlQuantity evaluated_quantity = { 0, 0 }; + GimpEevlToken consumed_token; + + if (gimp_eevl_accept (eva, + GIMP_EEVL_TOKEN_NUM, + &consumed_token)) + { + evaluated_quantity.value = consumed_token.value.fl; + } + else if (gimp_eevl_accept (eva, '(', NULL)) + { + evaluated_quantity = gimp_eevl_expression (eva); + gimp_eevl_expect (eva, ')', 0); + } + else + { + gimp_eevl_error (eva, "Expected number or '('"); + } + + if (eva->current_token.type == GIMP_EEVL_TOKEN_IDENTIFIER) + { + gchar *identifier; + GimpEevlQuantity factor; + gdouble offset; + + gimp_eevl_accept (eva, + GIMP_EEVL_TOKEN_ANY, + &consumed_token); + + identifier = g_newa (gchar, consumed_token.value.size + 1); + + strncpy (identifier, consumed_token.value.c, consumed_token.value.size); + identifier[consumed_token.value.size] = '\0'; + + if (eva->options.unit_resolver_proc (identifier, + &factor, + &offset, + eva->options.data)) + { + if (gimp_eevl_accept (eva, '^', NULL)) + { + GimpEevlQuantity evaluated_exponent; + + evaluated_exponent = gimp_eevl_signed_factor (eva); + + if (evaluated_exponent.dimension != 0) + { + gimp_eevl_error (eva, + "Exponent is not a dimensionless quantity"); + } + + if (offset != 0.0) + { + gimp_eevl_error (eva, + "Invalid unit exponent"); + } + + factor.value = pow (factor.value, evaluated_exponent.value); + factor.dimension *= evaluated_exponent.value; + } + + evaluated_quantity.value /= factor.value; + evaluated_quantity.value += offset; + evaluated_quantity.dimension += factor.dimension; + } + else + { + gimp_eevl_error (eva, "Unit was not resolved"); + } + } + + return evaluated_quantity; +} + +static gboolean +gimp_eevl_accept (GimpEevl *eva, + GimpEevlTokenType token_type, + GimpEevlToken *consumed_token) +{ + gboolean existed = FALSE; + + if (token_type == eva->current_token.type || + token_type == GIMP_EEVL_TOKEN_ANY) + { + existed = TRUE; + + if (consumed_token) + *consumed_token = eva->current_token; + + /* Parse next token */ + gimp_eevl_lex (eva); + } + + return existed; +} + +static void +gimp_eevl_lex (GimpEevl *eva) +{ + const gchar *s; + + gimp_eevl_move_past_whitespace (eva); + s = eva->string; + eva->start_of_current_token = s; + + if (! s || s[0] == '\0') + { + /* We're all done */ + eva->current_token.type = GIMP_EEVL_TOKEN_END; + } + else if (s[0] == '+' || s[0] == '-') + { + /* Snatch these before the g_strtod() does, otherwise they might + * be used in a numeric conversion. + */ + gimp_eevl_lex_accept_count (eva, 1, s[0]); + } + else + { + /* Attempt to parse a numeric value */ + gchar *endptr = NULL; + gdouble value = g_strtod (s, &endptr); + + if (endptr && endptr != s) + { + /* A numeric could be parsed, use it */ + eva->current_token.value.fl = value; + + gimp_eevl_lex_accept_to (eva, endptr, GIMP_EEVL_TOKEN_NUM); + } + else if (gimp_eevl_unit_identifier_start (s[0])) + { + /* Unit identifier */ + eva->current_token.value.c = s; + eva->current_token.value.size = gimp_eevl_unit_identifier_size (s, 0); + + gimp_eevl_lex_accept_count (eva, + eva->current_token.value.size, + GIMP_EEVL_TOKEN_IDENTIFIER); + } + else + { + /* Everything else is a single character token */ + gimp_eevl_lex_accept_count (eva, 1, s[0]); + } + } +} + +static void +gimp_eevl_lex_accept_count (GimpEevl *eva, + gint count, + GimpEevlTokenType token_type) +{ + eva->current_token.type = token_type; + eva->string += count; +} + +static void +gimp_eevl_lex_accept_to (GimpEevl *eva, + gchar *to, + GimpEevlTokenType token_type) +{ + eva->current_token.type = token_type; + eva->string = to; +} + +static void +gimp_eevl_move_past_whitespace (GimpEevl *eva) +{ + if (! eva->string) + return; + + while (g_ascii_isspace (*eva->string)) + eva->string++; +} + +static gboolean +gimp_eevl_unit_identifier_start (gunichar c) +{ + return (g_unichar_isalpha (c) || + c == (gunichar) '%' || + c == (gunichar) '\''); +} + +static gboolean +gimp_eevl_unit_identifier_continue (gunichar c) +{ + return (gimp_eevl_unit_identifier_start (c) || + g_unichar_isdigit (c)); +} + +/** + * gimp_eevl_unit_identifier_size: + * @s: + * @start: + * + * Returns: Size of identifier in bytes (not including NULL + * terminator). + **/ +static gint +gimp_eevl_unit_identifier_size (const gchar *string, + gint start_offset) +{ + const gchar *start = g_utf8_offset_to_pointer (string, start_offset); + const gchar *s = start; + gunichar c = g_utf8_get_char (s); + gint length = 0; + + if (gimp_eevl_unit_identifier_start (c)) + { + s = g_utf8_next_char (s); + c = g_utf8_get_char (s); + length++; + + while (gimp_eevl_unit_identifier_continue (c)) + { + s = g_utf8_next_char (s); + c = g_utf8_get_char (s); + length++; + } + } + + return g_utf8_offset_to_pointer (start, length) - start; +} + +static void +gimp_eevl_expect (GimpEevl *eva, + GimpEevlTokenType token_type, + GimpEevlToken *value) +{ + if (! gimp_eevl_accept (eva, token_type, value)) + gimp_eevl_error (eva, "Unexpected token"); +} + +static void +gimp_eevl_error (GimpEevl *eva, + gchar *msg) +{ + eva->error_message = msg; + longjmp (eva->catcher, 1); +} |