added graphvizParseTree in the C and Python runtimes

4 files changed, 267 insertions, 31 deletions

diff --git a/src/runtime/c/pgf/graphviz.c b/src/runtime/c/pgf/graphviz.c
index cf2346fee..2bc27c238 100644
--- a/src/runtime/c/pgf/graphviz.c
+++ b/src/runtime/c/pgf/graphviz.c
@@ -1,5 +1,6 @@
 #include "data.h"
 #include "graphviz.h"
+#include "linearizer.h"
 
 static int
 pgf_graphviz_abstract_tree_(PgfExpr expr, int *pid,
@@ -83,7 +84,7 @@ pgf_graphviz_abstract_tree_(PgfExpr expr, int *pid,
 }
 
 void
-pgf_graphviz_abstract_tree(PgfExpr expr, GuWriter* wtr, GuExn* err)
+pgf_graphviz_abstract_tree(PgfPGF* pgf, PgfExpr expr, GuWriter* wtr, GuExn* err)
 {
 	int id = 0;
 
@@ -91,3 +92,207 @@ pgf_graphviz_abstract_tree(PgfExpr expr, GuWriter* wtr, GuExn* err)
 	pgf_graphviz_abstract_tree_(expr, &id, wtr, err);
 	gu_puts("}", wtr, err);
 }
+
+typedef struct PgfParseNode PgfParseNode;
+	
+struct PgfParseNode {
+	int id;
+	PgfParseNode* parent;
+	GuString label;
+};
+
+typedef struct {
+	PgfLinFuncs* funcs;
+
+	GuPool* pool;
+	GuWriter* wtr;
+	GuExn* err;
+	
+	PgfParseNode* parent;
+	size_t level;
+	GuBuf* internals;
+	GuBuf* leaves;
+	GuString wildcard;
+} PgfBracketLznState;
+
+static void
+pgf_bracket_lzn_symbol_tokens(PgfLinFuncs** funcs, PgfTokens toks)
+{
+	PgfBracketLznState* state = gu_container(funcs, PgfBracketLznState, funcs);
+
+	size_t len = gu_seq_length(toks);
+	for (size_t i = 0; i < len; i++) {
+		PgfParseNode* node = gu_new(PgfParseNode, state->pool);
+		node->id     = 100000 + gu_buf_length(state->leaves);
+		node->parent = state->parent;
+		node->label  = gu_seq_get(toks, PgfToken, i);
+		gu_buf_push(state->leaves, PgfParseNode*, node);
+	}
+}
+
+static void
+pgf_bracket_lzn_expr_literal(PgfLinFuncs** funcs, PgfLiteral lit)
+{
+	PgfBracketLznState* state = gu_container(funcs, PgfBracketLznState, funcs);
+
+	GuString label;
+
+	GuVariantInfo i = gu_variant_open(lit);
+    switch (i.tag) {
+    case PGF_LITERAL_STR: {
+        PgfLiteralStr* lstr = i.data;
+        label = lstr->val;
+		break;
+	}
+    case PGF_LITERAL_INT: {
+        PgfLiteralInt* lint = i.data;
+        label = gu_format_string(state->pool, "%d", lint->val);
+		break;
+	}
+    case PGF_LITERAL_FLT: {
+        PgfLiteralFlt* lflt = i.data;
+        label = gu_format_string(state->pool, "%f", lflt->val);
+		break;
+	}
+	default:
+		gu_impossible();
+	}
+	
+	PgfParseNode* node = gu_new(PgfParseNode, state->pool);
+	node->id     = 100000 + gu_buf_length(state->leaves);
+	node->parent = state->parent;
+	node->label  = label;
+	gu_buf_push(state->leaves, PgfParseNode*, node);
+}
+
+static void
+pgf_bracket_lzn_begin_phrase(PgfLinFuncs** funcs, PgfCId cat, int fid, int lindex, PgfCId fun)
+{
+	PgfBracketLznState* state = gu_container(funcs, PgfBracketLznState, funcs);
+
+	if (gu_string_eq(cat, state->wildcard))
+		return;
+	
+	state->level++;
+
+	GuBuf* level;
+	if (state->level < gu_buf_length(state->internals))
+		level = gu_buf_get(state->internals, GuBuf*, state->level);
+	else {
+		level = gu_new_buf(PgfParseNode*, state->pool);
+		gu_buf_push(state->internals, GuBuf*, level);
+	}
+
+	size_t len = gu_buf_length(level);
+	for (size_t i = 0; i < len; i++) {
+		PgfParseNode* node = gu_buf_get(level, PgfParseNode*, i);
+		if (node->id == fid) {
+			state->parent = node;
+			return;
+		}
+	}
+	
+	PgfParseNode* node = gu_new(PgfParseNode, state->pool);
+	node->id     = fid;
+	node->parent = state->parent;
+	node->label  = cat;
+	gu_buf_push(level, PgfParseNode*, node);
+
+	state->parent = node;
+}
+
+static void
+pgf_bracket_lzn_end_phrase(PgfLinFuncs** funcs, PgfCId cat, int fid, int lindex, PgfCId fun)
+{
+	PgfBracketLznState* state = gu_container(funcs, PgfBracketLznState, funcs);
+
+	if (gu_string_eq(cat, state->wildcard))
+		return;
+
+	state->level--;
+	state->parent = state->parent->parent;
+}
+
+static PgfLinFuncs pgf_bracket_lin_funcs = {
+	.symbol_tokens = pgf_bracket_lzn_symbol_tokens,
+	.expr_literal  = pgf_bracket_lzn_expr_literal,
+	.begin_phrase  = pgf_bracket_lzn_begin_phrase,
+	.end_phrase    = pgf_bracket_lzn_end_phrase
+};
+
+void
+pgf_graphviz_parse_level(GuBuf* level, GuWriter* wtr, GuExn* err)
+{
+	gu_puts("\n  subgraph {rank=same;\n", wtr, err);
+
+	size_t len = gu_buf_length(level);
+	
+	if (len > 1)
+		gu_puts("    edge[style=invis]\n", wtr, err);
+
+	for (size_t i = 0; i < len; i++) {
+		PgfParseNode* node = gu_buf_get(level, PgfParseNode*, i);
+		gu_printf(wtr, err, "    n%d[label=\"", node->id);
+		gu_string_write(node->label, wtr, err);
+		gu_puts("\"]\n", wtr, err);		
+	}
+	
+	if (len > 1) {
+		for (size_t i = 0; i < len; i++) {
+			PgfParseNode* node = gu_buf_get(level, PgfParseNode*, i);		
+		
+			gu_puts((i == 0) ? "    " : " -- ", wtr, err);
+			gu_printf(wtr, err, "n%d", node->id);
+		}
+		gu_puts("\n", wtr, err);
+	}
+	
+	gu_puts("  }\n", wtr, err);
+
+	for (size_t i = 0; i < len; i++) {
+		PgfParseNode* node = gu_buf_get(level, PgfParseNode*, i);		
+		if (node->parent != NULL)
+			gu_printf(wtr, err, "  n%d -- n%d\n", node->parent->id, node->id);
+	}
+}
+
+void
+pgf_graphviz_parse_tree(PgfConcr* concr, PgfExpr expr, GuWriter* wtr, GuExn* err)
+{
+	GuPool* tmp_pool = gu_local_pool();
+	
+	GuEnum* cts = 
+		pgf_lzr_concretize(concr, expr, tmp_pool);
+	PgfCncTree ctree = gu_next(cts, PgfCncTree, tmp_pool);
+	if (gu_variant_is_null(ctree)) {
+		gu_pool_free(tmp_pool);
+		return;
+	}
+
+	gu_puts("graph {\n", wtr, err);
+	gu_puts("  node[shape=plaintext]\n", wtr, err);
+
+	PgfBracketLznState state;
+	state.funcs = &pgf_bracket_lin_funcs;
+	state.pool = tmp_pool;
+	state.wtr = wtr;
+	state.err = err;
+
+	state.parent    = NULL;
+	state.level     = -1;
+	state.internals = gu_new_buf(GuBuf*, tmp_pool);
+	state.leaves    = gu_new_buf(PgfParseNode*, tmp_pool);
+	state.wildcard  = gu_str_string("_", tmp_pool);
+	pgf_lzr_linearize(concr, ctree, 0, &state.funcs);
+
+	size_t len = gu_buf_length(state.internals);
+	for (size_t i = 0; i < len; i++) {
+		GuBuf* level = gu_buf_get(state.internals, GuBuf*, i);
+		pgf_graphviz_parse_level(level, wtr, err);
+	}
+	pgf_graphviz_parse_level(state.leaves, wtr, err);
+
+	gu_puts("}", wtr, err);
+
+	gu_pool_free(tmp_pool);
+}
diff --git a/src/runtime/c/pgf/graphviz.h b/src/runtime/c/pgf/graphviz.h
index 749c6ef5f..6f34bf500 100644
--- a/src/runtime/c/pgf/graphviz.h
+++ b/src/runtime/c/pgf/graphviz.h
@@ -2,6 +2,9 @@
 #define PGF_GRAPHVIZ_H_
 
 void
-pgf_graphviz_abstract_tree(PgfExpr expr, GuWriter* wtr, GuExn* err);
+pgf_graphviz_abstract_tree(PgfPGF* pgf, PgfExpr expr, GuWriter* wtr, GuExn* err);
+
+void
+pgf_graphviz_parse_tree(PgfConcr* concr, PgfExpr expr, GuWriter* wtr, GuExn* err);
 
 #endif
diff --git a/src/runtime/c/utils/pgf-service.c b/src/runtime/c/utils/pgf-service.c
index b0cb190b8..b18cfd603 100644
--- a/src/runtime/c/utils/pgf-service.c
+++ b/src/runtime/c/utils/pgf-service.c
@@ -56,7 +56,7 @@ url_escape(char *str)
 }
 
 static int
-render(PgfExpr expr, GuPool* pool)
+render(PgfPGF* pgf, PgfExpr expr, GuPool* pool)
 {
 	int pid;
 	int pc[2]; /* Parent to child pipe */
@@ -94,7 +94,7 @@ render(PgfExpr expr, GuPool* pool)
 		GuWriter* wtr = gu_new_utf8_writer(out, pool);
 		GuExn* err = gu_new_exn(NULL, gu_kind(type), pool);
 
-		pgf_graphviz_abstract_tree(expr, wtr, err);
+		pgf_graphviz_abstract_tree(pgf, expr, wtr, err);
 		fclose(fstream);
 
 		close(cp[1]);
@@ -275,7 +275,7 @@ int main ()
 			FCGI_printf("Status: 200 OK\r\n");
 			if (to_concr == NULL) {
 				FCGI_printf("Content-type: image/svg+xml\r\n\r\n");
-				render(ep->expr, ppool);
+				render(pgf, ep->expr, ppool);
 			} else {
 				FCGI_printf("Content-type: text/plain; charset=utf-8\r\n\r\n");
 				linearize(to_concr, ep->expr, ppool);
diff --git a/src/runtime/python/pypgf.c b/src/runtime/python/pypgf.c
index b623f6a81..e2fc0234e 100644
--- a/src/runtime/python/pypgf.c
+++ b/src/runtime/python/pypgf.c
@@ -1654,6 +1654,30 @@ Concr_getName(ConcrObject *self, void *closure)
     return gu2py_string(pgf_concrete_name(self->concr));
 }
 
+static PyObject*
+Concr_graphvizParseTree(ConcrObject* self, PyObject *args) {
+	ExprObject* pyexpr;
+	if (!PyArg_ParseTuple(args, "O!", &pgf_ExprType, &pyexpr))
+        return NULL;
+
+	GuPool* tmp_pool = gu_local_pool();
+	GuExn* err = gu_new_exn(NULL, gu_kind(type), tmp_pool);
+	GuStringBuf* sbuf = gu_string_buf(tmp_pool);
+	GuWriter* wtr = gu_string_buf_writer(sbuf);
+	
+	pgf_graphviz_parse_tree(self->concr, pyexpr->expr, wtr, err);
+	if (!gu_ok(err)) {
+		PyErr_SetString(PGFError, "The parse tree cannot be visualized");
+		return NULL;
+	}
+
+	GuString str = gu_string_buf_freeze(sbuf, tmp_pool);
+	PyObject* pystr = gu2py_string(str);
+
+	gu_pool_free(tmp_pool);
+	return pystr;
+}
+
 static PyGetSetDef Concr_getseters[] = {
     {"name", 
      (getter)Concr_getName, NULL,
@@ -1689,6 +1713,9 @@ static PyMethodDef Concr_methods[] = {
     {"bracketedLinearize", (PyCFunction)Concr_bracketedLinearize, METH_VARARGS,
      "Takes an abstract tree and linearizes it to a bracketed string"
     },
+    {"graphvizParseTree", (PyCFunction)Concr_graphvizParseTree, METH_VARARGS,
+     "Renders an abstract syntax tree as a parse tree in Graphviz format"
+    },
     {NULL}  /* Sentinel */
 };
 
@@ -2036,6 +2063,30 @@ PGF_compute(PGFObject* self, PyObject *args)
 	return py_expr;
 }
 
+static PyObject*
+PGF_graphvizAbstractTree(PGFObject* self, PyObject *args) {
+	ExprObject* pyexpr;
+	if (!PyArg_ParseTuple(args, "O!", &pgf_ExprType, &pyexpr))
+        return NULL;
+
+	GuPool* tmp_pool = gu_local_pool();
+	GuExn* err = gu_new_exn(NULL, gu_kind(type), tmp_pool);
+	GuStringBuf* sbuf = gu_string_buf(tmp_pool);
+	GuWriter* wtr = gu_string_buf_writer(sbuf);
+	
+	pgf_graphviz_abstract_tree(self->pgf, pyexpr->expr, wtr, err);
+	if (!gu_ok(err)) {
+		PyErr_SetString(PGFError, "The abstract tree cannot be visualized");
+		return NULL;
+	}
+
+	GuString str = gu_string_buf_freeze(sbuf, tmp_pool);
+	PyObject* pystr = gu2py_string(str);
+
+	gu_pool_free(tmp_pool);
+	return pystr;
+}
+
 static PyGetSetDef PGF_getseters[] = {
     {"abstractName", 
      (getter)PGF_getAbstractName, NULL,
@@ -2077,6 +2128,9 @@ static PyMethodDef PGF_methods[] = {
     {"compute", (PyCFunction)PGF_compute, METH_VARARGS,
      "Computes the normal form of an abstract syntax tree"
     },
+    {"graphvizAbstractTree", (PyCFunction)PGF_graphvizAbstractTree, METH_VARARGS,
+     "Renders an abstract syntax tree in a Graphviz format"
+    },
     {NULL}  /* Sentinel */
 };
 
@@ -2215,30 +2269,6 @@ pgf_readType(PyObject *self, PyObject *args) {
     return pytype;
 }
 
-static PyObject*
-pgf_graphvizAbstractTree(PyObject *self, PyObject *args) {
-	ExprObject* pyexpr;
-	if (!PyArg_ParseTuple(args, "O!", &pgf_ExprType, &pyexpr))
-        return NULL;
-
-	GuPool* tmp_pool = gu_local_pool();
-	GuExn* err = gu_new_exn(NULL, gu_kind(type), tmp_pool);
-	GuStringBuf* sbuf = gu_string_buf(tmp_pool);
-	GuWriter* wtr = gu_string_buf_writer(sbuf);
-	
-	pgf_graphviz_abstract_tree(pyexpr->expr, wtr, err);
-	if (!gu_ok(err)) {
-		PyErr_SetString(PGFError, "The abstract tree cannot be visualized");
-		return NULL;
-	}
-
-	GuString str = gu_string_buf_freeze(sbuf, tmp_pool);
-	PyObject* pystr = gu2py_string(str);
-
-	gu_pool_free(tmp_pool);
-	return pystr;
-}
-
 static PyMethodDef module_methods[] = {
     {"readPGF",  (void*)pgf_readPGF,  METH_VARARGS,
      "Reads a PGF file in memory"},
@@ -2246,8 +2276,6 @@ static PyMethodDef module_methods[] = {
      "Parses a string as an abstract tree"},
     {"readType", (void*)pgf_readType, METH_VARARGS,
      "Parses a string as an abstract type"},
-    {"graphvizAbstractTree", (void*)pgf_graphvizAbstractTree, METH_VARARGS,
-     "Renders an abstract syntax tree in a Graphviz format"},
     {NULL, NULL, 0, NULL}        /* Sentinel */
 };