From f55a53ef2d861b634ad83622edc5e26430baeae0 Mon Sep 17 00:00:00 2001 From: Matthew Petroff Date: Sun, 15 Sep 2013 23:59:14 -0400 Subject: C++ify expression evaluator. (bzr r12475.1.23) --- src/util/expression-evaluator.cpp | 647 +++++++++++++++----------------------- 1 file changed, 246 insertions(+), 401 deletions(-) (limited to 'src/util/expression-evaluator.cpp') diff --git a/src/util/expression-evaluator.cpp b/src/util/expression-evaluator.cpp index dc59c67f4..2e2ec02f1 100644 --- a/src/util/expression-evaluator.cpp +++ b/src/util/expression-evaluator.cpp @@ -6,6 +6,7 @@ * Copyright (C) 2008 Martin Nordholts * Modified for Inkscape by Johan Engelen * Copyright (C) 2011 Johan Engelen + * Copyright (C) 2013 Matthew Petroff * * This library is free software: you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -34,106 +35,28 @@ using Inkscape::Util::unit_table; namespace Inkscape { namespace Util { -enum +EvaluatorQuantity::EvaluatorQuantity(double value, unsigned int dimension) : + value(value), + dimension(dimension) { - GIMP_EEVL_TOKEN_NUM = 30000, - GIMP_EEVL_TOKEN_IDENTIFIER = 30001, - - GIMP_EEVL_TOKEN_ANY = 40000, - - GIMP_EEVL_TOKEN_END = 50000 -}; - -typedef int GimpEevlTokenType; - - -typedef struct -{ - GimpEevlTokenType type; - - union - { - gdouble fl; - - struct - { - const gchar *c; - gint size; - }; - - } value; - -} GimpEevlToken; +} -typedef struct +EvaluatorToken::EvaluatorToken() { - const gchar *string; - GimpEevlUnitResolverProc unit_resolver_proc; - Unit *unit; - - GimpEevlToken current_token; - const gchar *start_of_current_token; -} GimpEevl; + type = 0; + value.fl = 0; +} -/** Unit Resolver... - */ -static bool unitresolverproc (const gchar* identifier, GimpEevlQuantity *result, Unit* unit) +ExpressionEvaluator::ExpressionEvaluator(const char *string, Unit *unit) : + string(string), + unit(unit) { - if (!unit) { - result->value = 1; - result->dimension = 1; - return true; - }else if (!identifier) { - result->value = 1; - result->dimension = unit->isAbsolute() ? 1 : 0; - return true; - } else if (unit_table.hasUnit(identifier)) { - Unit identifier_unit = unit_table.getUnit(identifier); - - // Catch the case of zero or negative unit factors (error!) - if (identifier_unit.factor < 0.0000001) { - return false; - } - - result->value = unit->factor / identifier_unit.factor; - result->dimension = identifier_unit.isAbsolute() ? 1 : 0; - return true; - } else { - return false; - } + current_token.type = TOKEN_END; + + // Preload symbol + parseNextToken(); } -static void gimp_eevl_init (GimpEevl *eva, - const gchar *string, - GimpEevlUnitResolverProc unit_resolver_proc, - Unit *unit); -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_signed_factor (GimpEevl *eva); -static GimpEevlQuantity gimp_eevl_factor (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, - const char *msg); - - /** * Evaluates the given arithmetic expression, along with an optional dimension * analysis, and basic unit conversions. @@ -142,387 +65,309 @@ static void gimp_eevl_error (GimpEevl * @param unit_resolver_proc Unit resolver callback. * * 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. + * base-unit. 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 menas in^2). + * Returns: An EvaluatorQuantity with a value given in the base unit along with + * the order of the dimension (e.g. if the base unit is inches, a dimension + * order of two means in^2). * * @return Result of evaluation. * @throws Inkscape::Util::EvaluatorException There was a parse error. **/ -GimpEevlQuantity -gimp_eevl_evaluate (const gchar* string, Unit* unit) +EvaluatorQuantity ExpressionEvaluator::evaluate() { - if (! g_utf8_validate (string, -1, NULL)) { + if (!g_utf8_validate(string, -1, NULL)) { throw EvaluatorException("Invalid UTF8 string", NULL); } - - GimpEevl eva; - gimp_eevl_init (&eva, string, unitresolverproc, unit); - - return gimp_eevl_complete(&eva); -} - -static void -gimp_eevl_init (GimpEevl *eva, - const gchar *string, - GimpEevlUnitResolverProc unit_resolver_proc, - Unit *unit) -{ - eva->string = string; - eva->unit_resolver_proc = unit_resolver_proc; - eva->unit = unit; - - eva->current_token.type = GIMP_EEVL_TOKEN_END; - - /* Preload symbol... */ - gimp_eevl_lex (eva); -} - -static GimpEevlQuantity -gimp_eevl_complete (GimpEevl *eva) -{ - GimpEevlQuantity result = {0, 0}; - GimpEevlQuantity default_unit_factor; - - /* 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->unit_resolver_proc (NULL, &default_unit_factor, eva->unit); - - /* 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.dimension = default_unit_factor.dimension; + + EvaluatorQuantity result = EvaluatorQuantity(); + EvaluatorQuantity default_unit_factor; + + // Empty expression evaluates to 0 + if (acceptToken(TOKEN_END, NULL)) { + return result; + } + + result = evaluateExpression(); + + // There should be nothing left to parse by now + isExpected(TOKEN_END, 0); + + resolveUnit(NULL, &default_unit_factor, unit); + + // 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.dimension = default_unit_factor.dimension; } - return result; + return result; } -static GimpEevlQuantity -gimp_eevl_expression (GimpEevl *eva) +EvaluatorQuantity ExpressionEvaluator::evaluateExpression() { - 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) + bool subtract; + EvaluatorQuantity evaluated_terms; + + evaluated_terms = evaluateTerm(); + + // Continue evaluating terms, chained with + or -. + for (subtract = FALSE; + acceptToken('+', NULL) || (subtract = acceptToken('-', NULL)); + subtract = FALSE) { - GimpEevlQuantity new_term = gimp_eevl_term (eva); - - /* If dimensions missmatch, attempt default unit assignent */ - if (new_term.dimension != evaluated_terms.dimension) - { - GimpEevlQuantity default_unit_factor; - - eva->unit_resolver_proc (NULL, - &default_unit_factor, - eva->unit); - - if (new_term.dimension == 0 && - evaluated_terms.dimension == default_unit_factor.dimension) + EvaluatorQuantity new_term = evaluateTerm(); + + // If dimensions missmatch, attempt default unit assignent + if ( new_term.dimension != evaluated_terms.dimension ) { + EvaluatorQuantity default_unit_factor; + + resolveUnit(NULL, &default_unit_factor, unit); + + if ( new_term.dimension == 0 + && evaluated_terms.dimension == default_unit_factor.dimension ) { - new_term.value /= default_unit_factor.value; - 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.dimension = default_unit_factor.dimension; - } - else + new_term.value /= default_unit_factor.value; + new_term.dimension = default_unit_factor.dimension; + } else if ( evaluated_terms.dimension == 0 + && new_term.dimension == default_unit_factor.dimension ) { - gimp_eevl_error (eva, "Dimension missmatch during addition"); + evaluated_terms.value /= default_unit_factor.value; + evaluated_terms.dimension = default_unit_factor.dimension; + } else { + throwError("Dimension missmatch during addition"); } } - - evaluated_terms.value += (subtract ? -new_term.value : new_term.value); + + evaluated_terms.value += (subtract ? -new_term.value : new_term.value); } - - return evaluated_terms; + + return evaluated_terms; } -static GimpEevlQuantity -gimp_eevl_term (GimpEevl *eva) +EvaluatorQuantity ExpressionEvaluator::evaluateTerm() { - gboolean division; - GimpEevlQuantity evaluated_signed_factors; - - evaluated_signed_factors = gimp_eevl_signed_factor (eva); - - for (division = FALSE; - gimp_eevl_accept (eva, '*', NULL) || - (division = gimp_eevl_accept (eva, '/', NULL)); - division = FALSE) + bool division; + EvaluatorQuantity evaluated_signed_factors; + + evaluated_signed_factors = evaluateSignedFactor(); + + for ( division = FALSE; + acceptToken('*', NULL) || (division = acceptToken ('/', NULL)); + division = FALSE ) { - GimpEevlQuantity new_signed_factor = gimp_eevl_signed_factor (eva); - - if (division) - { - evaluated_signed_factors.value /= new_signed_factor.value; - evaluated_signed_factors.dimension -= new_signed_factor.dimension; - - } - else - { - evaluated_signed_factors.value *= new_signed_factor.value; - evaluated_signed_factors.dimension += new_signed_factor.dimension; + EvaluatorQuantity new_signed_factor = evaluateSignedFactor(); + + if (division) { + evaluated_signed_factors.value /= new_signed_factor.value; + evaluated_signed_factors.dimension -= new_signed_factor.dimension; + } else { + evaluated_signed_factors.value *= new_signed_factor.value; + evaluated_signed_factors.dimension += new_signed_factor.dimension; } } - - return evaluated_signed_factors; + + return evaluated_signed_factors; } -static GimpEevlQuantity -gimp_eevl_signed_factor (GimpEevl *eva) +EvaluatorQuantity ExpressionEvaluator::evaluateSignedFactor() { - 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; + EvaluatorQuantity result; + bool negate = FALSE; + + if (!acceptToken('+', NULL)) { + negate = acceptToken ('-', NULL); + } + + result = evaluateFactor(); + + if (negate) { + result.value = -result.value; + } + + return result; } -static GimpEevlQuantity -gimp_eevl_factor (GimpEevl *eva) +EvaluatorQuantity ExpressionEvaluator::evaluateFactor() { - GimpEevlQuantity evaluated_factor = { 0, 0 }; - GimpEevlToken consumed_token; - - if (gimp_eevl_accept (eva, - GIMP_EEVL_TOKEN_NUM, - &consumed_token)) - { - evaluated_factor.value = consumed_token.value.fl; - } - else if (gimp_eevl_accept (eva, '(', NULL)) - { - evaluated_factor = gimp_eevl_expression (eva); - gimp_eevl_expect (eva, ')', 0); - } - else - { - gimp_eevl_error (eva, "Expected number or '('"); + EvaluatorQuantity evaluated_factor = EvaluatorQuantity(); + EvaluatorToken consumed_token = EvaluatorToken(); + + if (acceptToken(TOKEN_NUM, &consumed_token)) { + evaluated_factor.value = consumed_token.value.fl; + } else if (acceptToken('(', NULL)) { + evaluated_factor = evaluateExpression(); + isExpected(')', 0); + } else { + throwError("Expected number or '('"); } - - if (eva->current_token.type == GIMP_EEVL_TOKEN_IDENTIFIER) - { - gchar *identifier; - GimpEevlQuantity result; - - 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->unit_resolver_proc (identifier, - &result, - eva->unit)) - { - evaluated_factor.value /= result.value; - evaluated_factor.dimension += result.dimension; - } - else - { - gimp_eevl_error (eva, "Unit was not resolved"); + + if ( current_token.type == TOKEN_IDENTIFIER ) { + char *identifier; + EvaluatorQuantity result; + + acceptToken(TOKEN_ANY, &consumed_token); + + identifier = g_newa(char, consumed_token.value.size + 1); + + strncpy(identifier, consumed_token.value.c, consumed_token.value.size); + identifier[consumed_token.value.size] = '\0'; + + if (resolveUnit(identifier, &result, unit)) { + evaluated_factor.value /= result.value; + evaluated_factor.dimension += result.dimension; + } else { + throwError("Unit was not resolved"); } } - - return evaluated_factor; + + return evaluated_factor; } -static gboolean -gimp_eevl_accept (GimpEevl *eva, - GimpEevlTokenType token_type, - GimpEevlToken *consumed_token) +bool ExpressionEvaluator::acceptToken(TokenType token_type, + EvaluatorToken *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); + bool existed = FALSE; + + if ( token_type == current_token.type || token_type == TOKEN_ANY ) { + existed = TRUE; + + if (consumed_token) { + *consumed_token = current_token; + } + + // Parse next token + parseNextToken(); } - - return existed; + + return existed; } -static void -gimp_eevl_lex (GimpEevl *eva) +void ExpressionEvaluator::parseNextToken() { - 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, othewise they might - * be used in a numeric conversion. - */ - gimp_eevl_lex_accept_count (eva, 1, s[0]); - } - else + const char *s; - { - /* 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]); + movePastWhiteSpace(); + s = string; + start_of_current_token = s; + + if ( !s || s[0] == '\0' ) { + // We're all done + current_token.type = TOKEN_END; + } else if ( s[0] == '+' || s[0] == '-' ) { + // Snatch these before the g_strtod() does, othewise they might + // be used in a numeric conversion. + acceptTokenCount(1, s[0]); + } else { + // Attempt to parse a numeric value + char *endptr = NULL; + gdouble value = g_strtod(s, &endptr); + + if ( endptr && endptr != s ) { + // A numeric could be parsed, use it + current_token.value.fl = value; + + current_token.type = TOKEN_NUM; + string = endptr; + } else if (isUnitIdentifierStart(s[0])) { + // Unit identifier + current_token.value.c = s; + current_token.value.size = getIdentifierSize(s, 0); + + acceptTokenCount(current_token.value.size, TOKEN_IDENTIFIER); + } else { + // Everything else is a single character token + acceptTokenCount(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) +void ExpressionEvaluator::acceptTokenCount (int count, TokenType token_type) { - eva->current_token.type = token_type; - eva->string = to; + current_token.type = token_type; + string += count; } -static void -gimp_eevl_move_past_whitespace (GimpEevl *eva) +void ExpressionEvaluator::isExpected(TokenType token_type, + EvaluatorToken *value) { - if (! eva->string) - return; - - while (g_ascii_isspace (*eva->string)) - eva->string++; + if (!acceptToken(token_type, value)) { + throwError("Unexpected token"); + } } -static gboolean -gimp_eevl_unit_identifier_start (gunichar c) +void ExpressionEvaluator::movePastWhiteSpace() { - return (g_unichar_isalpha (c) || - c == (gunichar) '%' || - c == (gunichar) '\''); + if (!string) { + return; + } + + while (g_ascii_isspace(*string)) { + string++; + } } -static gboolean -gimp_eevl_unit_identifier_continue (gunichar c) +bool ExpressionEvaluator::isUnitIdentifierStart(gunichar c) { - return (gimp_eevl_unit_identifier_start (c) || - g_unichar_isdigit (c)); + return (g_unichar_isalpha (c) + || c == (gunichar) '%' + || c == (gunichar) '\''); } /** - * gimp_eevl_unit_identifier_size: + * getIdentifierSize: * @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) +int ExpressionEvaluator::getIdentifierSize(const char *string, int 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++; + const char *start = g_utf8_offset_to_pointer(string, start_offset); + const char *s = start; + gunichar c = g_utf8_get_char(s); + int length = 0; + + if (isUnitIdentifierStart(c)) { + s = g_utf8_next_char (s); + c = g_utf8_get_char (s); + length++; + + while ( isUnitIdentifierStart (c) || g_unichar_isdigit (c) ) { + s = g_utf8_next_char(s); + c = g_utf8_get_char(s); + length++; } } - - return g_utf8_offset_to_pointer (start, length) - start; + + return g_utf8_offset_to_pointer(start, length) - start; } -static void -gimp_eevl_expect (GimpEevl *eva, - GimpEevlTokenType token_type, - GimpEevlToken *value) +bool ExpressionEvaluator::resolveUnit (const char* identifier, + EvaluatorQuantity *result, + Unit* unit) { - if (! gimp_eevl_accept (eva, token_type, value)) - gimp_eevl_error (eva, "Unexpected token"); + if (!unit) { + result->value = 1; + result->dimension = 1; + return true; + }else if (!identifier) { + result->value = 1; + result->dimension = unit->isAbsolute() ? 1 : 0; + return true; + } else if (unit_table.hasUnit(identifier)) { + Unit identifier_unit = unit_table.getUnit(identifier); + result->value = Quantity::convert(1, *unit, identifier_unit); + result->dimension = identifier_unit.isAbsolute() ? 1 : 0; + return true; + } else { + return false; + } } -static void -gimp_eevl_error (GimpEevl *eva, - const char *msg) +void ExpressionEvaluator::throwError(const char *msg) { - throw EvaluatorException(msg, eva->start_of_current_token); + throw EvaluatorException(msg, start_of_current_token); } } // namespace Util -- cgit v1.2.3