metacity r4109 - in branches/rpnparser: . src/ui
- From: tthurman svn gnome org
- To: svn-commits-list gnome org
- Subject: metacity r4109 - in branches/rpnparser: . src/ui
- Date: Tue, 3 Feb 2009 01:53:35 +0000 (UTC)
Author: tthurman
Date: Tue Feb 3 01:53:35 2009
New Revision: 4109
URL: http://svn.gnome.org/viewvc/metacity?rev=4109&view=rev
Log:
and the actual parsing code!
* src/ui/rpn.c:
* src/ui/rpn.h:
* src/ui/rpn.c (added):
* src/ui/rpn.h (added):
Added:
branches/rpnparser/src/ui/rpn.c
branches/rpnparser/src/ui/rpn.h
Modified:
branches/rpnparser/ChangeLog
Added: branches/rpnparser/src/ui/rpn.c
==============================================================================
--- (empty file)
+++ branches/rpnparser/src/ui/rpn.c Tue Feb 3 01:53:35 2009
@@ -0,0 +1,651 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
+
+/*
+ * Copyright (C) 2009 Thomas Thurman
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program 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
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+/**
+ * \file rpn.c Internal representation of expressions
+ *
+ * Expressions found in theme files, such as
+ * "1 `max` ((height-title_height)/2)-1"
+ * are stored internally in reverse Polish notation, here as
+ * 1.000 height title_height - 2.000 / 1.000 - `max`
+ *
+ * This file provides functions for turning Metacity expressions
+ * into RPN, and for evaluating RPN.
+ */
+
+#include <config.h>
+#include "rpn.h"
+#include "util.h"
+#include <glib.h>
+#include <string.h>
+#include <stdio.h>
+
+/* integers are stored this many times larger.
+ * this lets us not use float arithmetic, for speed. */
+#define SCALE_BITS 16
+#define SCALE (1<<SCALE_BITS)
+
+/* this is the size of the stack used while converting expressions
+ * to RPN, and also the size of the evaluation stack, and the
+ * maximum size of the final result. if you go over this,
+ * a run-time error will result.
+ */
+#define STACK_SIZE 100
+
+enum MetaToken {
+ META_TOKEN_INT = 0x7FFFFFFF,
+ META_TOKEN_OP_BASE = 0x80000000,
+ META_TOKEN_DONE,
+ META_TOKEN_ADD,
+ META_TOKEN_SUBTRACT,
+ META_TOKEN_MULTIPLY,
+ META_TOKEN_DIVIDE,
+ META_TOKEN_MIN,
+ META_TOKEN_MAX,
+ META_TOKEN_OPEN, /* only during parse */
+ META_TOKEN_CLOSE, /* only during parse */
+ /* Variables, which are treated as 0-ary operators */
+ META_TOKEN_width,
+ META_TOKEN_height,
+ META_TOKEN_object_width,
+ META_TOKEN_object_height,
+ META_TOKEN_left_width,
+ META_TOKEN_right_width,
+ META_TOKEN_top_height,
+ META_TOKEN_bottom_height,
+ META_TOKEN_mini_icon_width,
+ META_TOKEN_mini_icon_height,
+ META_TOKEN_icon_width,
+ META_TOKEN_icon_height,
+ META_TOKEN_title_width,
+ META_TOKEN_title_height
+};
+
+#ifdef DEBUG_RPN
+static char *
+meta_token_as_string (MetaToken token)
+{
+ if (token & META_TOKEN_OP_BASE)
+ {
+ switch (token)
+ {
+ case META_TOKEN_ADD: return g_strdup_printf ("+");
+ case META_TOKEN_SUBTRACT: return g_strdup_printf ("-");
+ case META_TOKEN_MULTIPLY: return g_strdup_printf ("*");
+ case META_TOKEN_DIVIDE: return g_strdup_printf ("/");
+ case META_TOKEN_MIN: return g_strdup_printf ("`min`");
+ case META_TOKEN_MAX: return g_strdup_printf ("`max`");
+ case META_TOKEN_OPEN: return g_strdup_printf ("(");
+ case META_TOKEN_CLOSE: return g_strdup_printf (")");
+
+#define name_token(t) case META_TOKEN_##t: return g_strdup_printf(#t);
+ name_token (width);
+ name_token (height);
+ name_token (object_width);
+ name_token (object_height);
+ name_token (left_width);
+ name_token (right_width);
+ name_token (top_height);
+ name_token (bottom_height);
+ name_token (mini_icon_width);
+ name_token (mini_icon_height);
+ name_token (icon_width);
+ name_token (icon_height);
+ name_token (title_width);
+ name_token (title_height);
+#undef name_token
+ default: return g_strdup_printf ("unknown-op(%x)", token);
+ }
+ }
+ else
+ return g_strdup_printf ("%0.3f", ((double)token/SCALE));
+}
+
+static char *
+meta_token_list_as_string (MetaToken *token)
+{
+ char *result = NULL;
+
+ while (*token != META_TOKEN_DONE) {
+
+ gchar *temp = meta_token_as_string (*token);
+
+ gchar *new_result = g_strconcat (result? result: "",
+ result? " " : "",
+ temp,
+ NULL);
+ g_free (result);
+ result = new_result;
+
+ g_free (temp);
+
+ token++;
+ }
+
+ return result;
+}
+#endif
+
+static void
+parse_error (const char* message, GScanner *scanner, const char *expr)
+{
+ gchar *expr2 = g_strdup (expr);
+ gint position = g_scanner_cur_position (scanner);
+
+ expr2[position] = 0; /* why doesn't g_warning understand %*s? */
+
+ meta_bug ("%s at %s<-- %s %s",
+ message,
+ expr2,
+ /* Translators: This appears beside an error inside a
+ * theme to show where the error is.
+ */
+ _("HERE"),
+ expr+position);
+ g_free (expr2);
+}
+
+static guint64 add(guint64 a, guint64 b) { return a+b; }
+static guint64 subtract(guint64 a, guint64 b) { return b>a?0:a-b; }
+static guint64 multiply(guint64 a, guint64 b) { return a*(b>>SCALE_BITS); }
+static guint64 divide(guint64 a, guint64 b) { return b==0?0:a/(b>>SCALE_BITS); }
+static guint64 min(guint64 a, guint64 b) { return a<b?a:b; }
+static guint64 max(guint64 a, guint64 b) { return a>b?a:b; }
+
+static guint64 get_width(const MetaPositionExprEnv *env) { return env->rect.width; }
+static guint64 get_height(const MetaPositionExprEnv *env) { return env->rect.height; }
+#define name_token(t) static guint64 get_##t(const MetaPositionExprEnv *env) { return env->t; }
+name_token (object_width)
+name_token (object_height)
+name_token (left_width)
+name_token (right_width)
+name_token (top_height)
+name_token (bottom_height)
+name_token (mini_icon_width)
+name_token (mini_icon_height)
+name_token (icon_width)
+name_token (icon_height)
+name_token (title_width)
+name_token (title_height)
+#undef name_token
+
+typedef guint64 (BinaryOp (guint64, guint64));
+typedef guint64 (Variable (const MetaPositionExprEnv*));
+
+typedef struct TokenHandler {
+ BinaryOp *binary;
+ Variable *variable;
+} TokenHandler;
+
+const TokenHandler handlers[] = {
+ { NULL }, /* BASE */
+ { NULL }, /* DONE */
+ { add, NULL },
+ { subtract, NULL },
+ { multiply, NULL },
+ { divide, NULL },
+ { min, NULL },
+ { max, NULL },
+ { NULL }, /* OPEN */
+ { NULL }, /* CLOSE */
+#define name_token(t) { NULL, get_##t },
+name_token (width)
+name_token (height)
+name_token (object_width)
+name_token (object_height)
+name_token (left_width)
+name_token (right_width)
+name_token (top_height)
+name_token (bottom_height)
+name_token (mini_icon_width)
+name_token (mini_icon_height)
+name_token (icon_width)
+name_token (icon_height)
+name_token (title_width)
+name_token (title_height)
+#undef name_token
+};
+
+#ifdef DEBUG_RPN
+static void
+token_verbose_real (const char* message, MetaToken token)
+{
+ gchar *str = meta_token_as_string (token);
+ gchar *message2 = g_strconcat (message, ": %s\n", NULL);
+
+ g_print (message2, str);
+
+ g_free (message2);
+ g_free (str);
+}
+
+#define token_verbose(a,b) token_verbose_real(a,b)
+#else
+#define token_verbose(a,b) ;
+#endif
+
+/**
+ * If the top two entries on the output are constants, performs "op" on the
+ * constants, replaces them with the result, and returns META_TOKEN_DONE.
+ * Otherwise returns "tokenop".
+ * This means that we don't waste our time outputting, say, "2 2 add"
+ * when we could be outputting "4".
+ *
+ * @param output an array of MetaTokens
+ * @param output_pointer pointer to an index in the array
+ * (it's a pointer so that we can change its value)
+ * @param op what operation needs to be carried out
+ *
+ * @bug there is no effective way yet to debug this
+ */
+static void
+accept (MetaToken *output, gint *output_pointer, MetaToken item)
+{
+ if (
+ (item & META_TOKEN_OP_BASE) && /* it's an op */
+ handlers[item ^ META_TOKEN_OP_BASE].binary && /* it's a binary op */
+ *output_pointer >= 2 && /* there's more than two things output */
+ !(output[(*output_pointer)-1] & META_TOKEN_OP_BASE) &&
+ !(output[(*output_pointer)-2] & META_TOKEN_OP_BASE)
+ /* the most recent two are constants */
+ )
+ {
+ MetaToken result =
+ handlers[item ^ META_TOKEN_OP_BASE].binary(
+ output[(*output_pointer)-1],
+ output[(*output_pointer)-2]
+ );
+
+ token_verbose ("Accept calculated", result & META_TOKEN_INT);
+
+ output[(*output_pointer)-2] = result & META_TOKEN_INT;
+ (*output_pointer)--;
+ }
+ else
+ {
+ if (*output_pointer>STACK_SIZE)
+ meta_bug ("Parse stack overflow"); /* FIXME THIS IS BAD */
+
+ token_verbose ("Accept", item);
+ output[(*output_pointer)++] = item;
+ }
+}
+
+static gint
+precedence (MetaToken token)
+{
+ switch (token)
+ {
+ case META_TOKEN_MULTIPLY:
+ case META_TOKEN_DIVIDE:
+ return 4;
+ case META_TOKEN_ADD:
+ case META_TOKEN_SUBTRACT:
+ return 3;
+ case META_TOKEN_MIN:
+ case META_TOKEN_MAX:
+ return 2;
+ case META_TOKEN_OPEN:
+ case META_TOKEN_CLOSE:
+ return 1;
+ default:
+ return 0;
+ }
+}
+
+static gboolean
+is_bracket (MetaToken token)
+{
+ return token==META_TOKEN_OPEN || token==META_TOKEN_CLOSE;
+}
+
+#define check_for_overflow(v) { if (v+1>=STACK_SIZE) { \
+ parse_error ("Stack overflow", scanner, expr); return NULL; } }
+
+MetaToken *
+meta_rpn_parse (MetaTheme *theme,
+ const char *expr,
+ GError **err)
+{
+ GScannerConfig scanner_config = {
+ " \n\t", /* cset_skip_characters; */
+ G_CSET_a_2_z G_CSET_A_2_Z, /* cset_identifier_first */
+ G_CSET_a_2_z G_CSET_A_2_Z "_", /* cset_identifier_nth */
+ "", /* cpair_comment_single -- no comments! */
+ TRUE, /* case_sensitive */
+ FALSE, /* no comments */
+ FALSE, /* no comments */
+ FALSE, /* no comments */
+ TRUE, /* pick up identifiers */
+ TRUE, /* even single-char ones */
+ FALSE, /* "NULL" isn't special */
+ TRUE, /* we have symbols */
+ FALSE, /* no binary */
+ FALSE, /* no octal */
+ TRUE, /* we do have floats */
+ FALSE, /* but no hex */
+ FALSE, /* still no hex */
+ FALSE, /* also no strings */
+ FALSE, /* still no strings */
+ TRUE, /* makes no difference whether hex is an int */
+ FALSE, /* we don't allow chars anyway */
+ FALSE, /* return actual symbols */
+ FALSE, /* don't bother with default scope */
+ FALSE, /* just ordinary ints */
+ };
+ GScanner *scanner = g_scanner_new (&scanner_config);
+ MetaToken stack[STACK_SIZE];
+ gint stack_pointer = 0;
+ MetaToken result[STACK_SIZE];
+ gint result_pointer = 0;
+
+ char *identifiers[] = {
+ "min",
+ "max",
+#define name_token(t) #t,
+ name_token (width)
+ name_token (height)
+ name_token (object_width)
+ name_token (object_height)
+ name_token (left_width)
+ name_token (right_width)
+ name_token (top_height)
+ name_token (bottom_height)
+ name_token (mini_icon_width)
+ name_token (mini_icon_height)
+ name_token (icon_width)
+ name_token (icon_height)
+ name_token (title_width)
+ name_token (title_height)
+#undef name_token
+ NULL,
+ };
+ char **cursor;
+
+ for (cursor = identifiers; *cursor; cursor++) {
+ g_scanner_scope_add_symbol (scanner, 0, *cursor, *cursor);
+ }
+
+ g_scanner_input_text (scanner, expr, strlen (expr));
+
+ while (g_scanner_get_next_token (scanner))
+ {
+ MetaToken token;
+
+ switch (g_scanner_cur_token (scanner)) {
+ case G_TOKEN_FLOAT:
+ token =
+ (glong) (g_scanner_cur_value (scanner).v_float*SCALE) &
+ META_TOKEN_INT;
+
+ token_verbose ("Accept float", token);
+ check_for_overflow (result_pointer);
+ result[result_pointer++] = token;
+ break;
+ case G_TOKEN_INT:
+ token = g_scanner_cur_value (scanner).v_int<<SCALE_BITS &
+ META_TOKEN_INT;
+
+ token_verbose ("Accept integer", token);
+ check_for_overflow (result_pointer);
+ result[result_pointer++] = token;
+ break;
+ case G_TOKEN_CHAR:
+ switch (g_scanner_cur_value (scanner).v_char)
+ {
+
+ case '+': token = META_TOKEN_ADD; break;
+ case '-': token = META_TOKEN_SUBTRACT; break;
+ case '*': token = META_TOKEN_MULTIPLY; break;
+ case '/': token = META_TOKEN_DIVIDE; break;
+
+ case '(': token = META_TOKEN_OPEN; break;
+ case ')': token = META_TOKEN_CLOSE; break;
+ case '`':
+ /* used as a separator so people can continue to write "foo`max`bar" */
+ token = META_TOKEN_DONE; break;
+ default:
+ parse_error ("Unknown character", scanner, expr);
+ return NULL;
+ }
+
+ if (token==META_TOKEN_DONE) break; /* see above */
+
+ switch (token)
+ {
+ case META_TOKEN_OPEN:
+ /* do nothing */
+ break;
+
+ case META_TOKEN_CLOSE:
+ token_verbose ("Closing up", token);
+ while (stack_pointer>0 && stack[stack_pointer-1] != META_TOKEN_OPEN) {
+ stack_pointer--;
+ accept (result, &result_pointer, stack[stack_pointer]);
+ }
+
+ if (stack_pointer>0) stack_pointer--; /* and skip the open bracket */
+ break;
+
+ default:
+ while (stack_pointer>0 && precedence(stack[stack_pointer-1]) >= precedence(token)) {
+ stack_pointer--;
+ token_verbose ("Pop for precedence", stack[stack_pointer]);
+ if (!is_bracket(stack[stack_pointer])) {
+ accept (result, &result_pointer, stack[stack_pointer]);
+ }
+ }
+ }
+
+ if (token!=META_TOKEN_CLOSE) {
+ token_verbose ("Push", token);
+ check_for_overflow (stack_pointer);
+ stack[stack_pointer++] = token;
+ }
+ break;
+ case G_TOKEN_SYMBOL:
+
+#define check_token(t) (strcmp (g_scanner_cur_value (scanner).v_symbol, #t)==0) \
+ token=META_TOKEN_##t
+
+ if (strcmp (g_scanner_cur_value (scanner).v_symbol, "min")==0)
+ token = META_TOKEN_MIN;
+ else if (strcmp (g_scanner_cur_value (scanner).v_symbol, "max")==0)
+ token = META_TOKEN_MAX;
+ else if check_token (width);
+ else if check_token (height);
+ else if check_token (object_width);
+ else if check_token (object_height);
+ else if check_token (left_width);
+ else if check_token (right_width);
+ else if check_token (top_height);
+ else if check_token (bottom_height);
+ else if check_token (mini_icon_width);
+ else if check_token (mini_icon_height);
+ else if check_token (icon_width);
+ else if check_token (icon_height);
+ else if check_token (title_width);
+ else if check_token (title_height);
+
+#undef check_token
+
+ else
+ {
+ parse_error ("Unknown symbol", scanner, expr);
+ return NULL;
+ }
+
+ if (token==META_TOKEN_DONE) break; /* it was constant */
+
+ if (token==META_TOKEN_MIN || token==META_TOKEN_MAX)
+ {
+ while (stack_pointer>0 && precedence(stack[stack_pointer-1]) >= precedence(token)) {
+ stack_pointer--;
+ token_verbose ("Pop for precedence", stack[stack_pointer]);
+ if (!is_bracket(stack[stack_pointer])) {
+ token_verbose (" ... and accept", stack[stack_pointer]);
+ accept (result, &result_pointer, stack[stack_pointer]);
+ }
+ }
+ token_verbose ("Push", token);
+ check_for_overflow (stack_pointer);
+ stack[stack_pointer++] = token;
+ }
+ else {
+ token_verbose ("Accept token", token);
+ /* don't bother using accept(): it can never be >0-ary */
+ check_for_overflow (result_pointer);
+ result[result_pointer++] = token;
+ }
+ break;
+
+ case G_TOKEN_IDENTIFIER:
+ {
+ double f;
+ int i;
+
+ if (meta_theme_lookup_int_constant (theme,
+ g_scanner_cur_value (scanner).v_identifier,
+ &i))
+ {
+ token = i<<SCALE_BITS & META_TOKEN_INT;
+ token_verbose ("Accept const integer", token);
+ check_for_overflow (result_pointer);
+ result[result_pointer++] = token;
+ }
+ else if (meta_theme_lookup_float_constant (theme,
+ g_scanner_cur_value (scanner).v_identifier,
+ &f))
+ {
+ token = (glong)(f*SCALE) & META_TOKEN_INT;
+
+ token_verbose ("Accept const float", token);
+ check_for_overflow (result_pointer);
+ result[result_pointer++] = token;
+ }
+ else
+ {
+ parse_error ("Unknown identifier", scanner, expr);
+ return NULL;
+ }
+ }
+ break;
+
+ default:
+ parse_error ("Unknown state", scanner, expr);
+ return NULL;
+ }
+
+ }
+
+ while (stack_pointer>0)
+ if (!is_bracket (stack[--stack_pointer])) {
+ token_verbose ("Final accept", stack[stack_pointer]);
+ accept (result, &result_pointer, stack[stack_pointer]);
+ }
+
+ result[result_pointer++] = META_TOKEN_DONE;
+
+ g_scanner_destroy (scanner);
+
+ /*FIXME MetaPositionExprEnv env;
+
+ env.rect.width=10;
+ env.rect.height=10;
+ int r=0;
+
+ meta_rpn_eval (result, &env,
+ &r, NULL);*/
+
+ /*
+ meta_bug ("Okay, hold it there: %s %d",
+ meta_token_list_as_string (result), r);
+ */
+
+ return g_memdup (result, sizeof(MetaToken)*result_pointer);
+}
+
+gboolean inline
+meta_rpn_eval (MetaToken *expr,
+ const MetaPositionExprEnv *env,
+ int *result,
+ GError **err)
+{
+ if (*(expr+1) == META_TOKEN_DONE)
+ {
+ /* commonest case is "number, DONE";
+ * there must be at least two tokens, so we know
+ * we're okay to look ahead by one
+ */
+ if (*(expr) & META_TOKEN_OP_BASE)
+ {
+ /* must be a variable; you can't legally
+ * do, say, nothing but "add, DONE"
+ */
+ *result = handlers[*expr ^ META_TOKEN_OP_BASE].variable (env);
+ }
+ else
+ *result = (*expr) >> SCALE_BITS;
+
+ return TRUE;
+ }
+ else
+ {
+ MetaToken *cursor = expr;
+ /* This is not a stack of MetaTokens because... FIXME */
+ gint64 stack[STACK_SIZE];
+ gint64* stack_pointer = &(stack[0]);
+
+ while (*cursor != META_TOKEN_DONE)
+ {
+ if (*cursor & META_TOKEN_OP_BASE)
+ {
+ guint64 h = *cursor ^ META_TOKEN_OP_BASE;
+ if (handlers[h].binary)
+ {
+ *(stack_pointer-2) =
+ handlers[h].binary (*(stack_pointer-2),
+ *(stack_pointer-1));
+ stack_pointer--;
+ }
+ else if (handlers[h].variable)
+ {
+ *(stack_pointer++) =
+ handlers[h].variable (env) << SCALE_BITS;
+ }
+ else
+ {
+ /* should never happen */
+ meta_bug ("Invalid token found %x", (unsigned) h);
+ return FALSE;
+ }
+ }
+ else
+ *(stack_pointer++) = *cursor;
+
+ cursor++;
+ }
+
+ *result = *(--stack_pointer) >> SCALE_BITS;
+
+ return TRUE;
+ }
+}
Added: branches/rpnparser/src/ui/rpn.h
==============================================================================
--- (empty file)
+++ branches/rpnparser/src/ui/rpn.h Tue Feb 3 01:53:35 2009
@@ -0,0 +1,36 @@
+/* -*- mode: C; c-file-style: "gnu"; indent-tabs-mode: nil; -*- */
+
+/*
+ * Copyright (C) 2009 Thomas Thurman
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program 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
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+#ifndef META_RPN_H
+#define META_RPN_H
+
+#include "theme.h"
+
+MetaToken *meta_rpn_parse (MetaTheme *theme,
+ const char *expr,
+ GError **err);
+
+gboolean inline meta_rpn_eval (MetaToken *expr,
+ const MetaPositionExprEnv *env,
+ int *result,
+ GError **err);
+
+#endif
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
