mds-kbdc: most of the structure validation

Signed-off-by: Mattias Andrée <maandree@operamail.com>

6 files changed, 588 insertions, 4 deletions

diff --git a/src/mds-kbdc/make-tree.c b/src/mds-kbdc/make-tree.c
index 5c644b4..567f5a5 100644
--- a/src/mds-kbdc/make-tree.c
+++ b/src/mds-kbdc/make-tree.c
@@ -88,7 +88,7 @@
 
 
 /**
- * Add an error the to error list
+ * Add an error to the error list
  * 
  * @param  ERROR_IS_IN_FILE:int           Whether the error is in the layout code
  * @param  SEVERITY:identifier            * in `MDS_KBDC_PARSE_ERROR_*` to indicate severity
diff --git a/src/mds-kbdc/mds-kbdc.c b/src/mds-kbdc/mds-kbdc.c
index 318fc3c..9c668c8 100644
--- a/src/mds-kbdc/mds-kbdc.c
+++ b/src/mds-kbdc/mds-kbdc.c
@@ -55,9 +55,10 @@ int main(int argc_, char** argv_)
   process (parse_to_tree(argv[1], &result));
   process (simplify_tree(&result));
   process (process_includes(&result));
-  /* TODO process (validate_tree(&result)); */
+  process (validate_tree(&result));
   /* TODO process (eliminate_dead_code(&result)); */
   /* TODO process (compile_layout(&result)); */
+  /* TODO process (assemble_layout(&result)); */
  stop:
   mds_kbdc_tree_print(result.tree, stderr);
   mds_kbdc_parsed_print_errors(&result, stderr);
diff --git a/src/mds-kbdc/process-includes.c b/src/mds-kbdc/process-includes.c
index 9fe14a3..28d1652 100644
--- a/src/mds-kbdc/process-includes.c
+++ b/src/mds-kbdc/process-includes.c
@@ -35,7 +35,7 @@
 #define C(TYPE)  MDS_KBDC_TREE_TYPE_##TYPE
 
 /**
- * Add an error the to error list
+ * Add an error to the error list
  * 
  * @param  NODE:const mds_kbdc_tree_t*    The node the triggered the error
  * @param  SEVERITY:identifier            * in `MDS_KBDC_PARSE_ERROR_*` to indicate severity
diff --git a/src/mds-kbdc/simplify-tree.c b/src/mds-kbdc/simplify-tree.c
index 45e0837..b15fa62 100644
--- a/src/mds-kbdc/simplify-tree.c
+++ b/src/mds-kbdc/simplify-tree.c
@@ -37,7 +37,7 @@
 
 
 /**
- * Add an error the to error list
+ * Add an error to the error list
  * 
  * @param  NODE:const mds_kbdc_tree_t*    The node the triggered the error
  * @param  SEVERITY:identifier            * in `MDS_KBDC_PARSE_ERROR_*` to indicate severity
diff --git a/src/mds-kbdc/validate-tree.c b/src/mds-kbdc/validate-tree.c
new file mode 100644
index 0000000..98ec2ba
--- /dev/null
+++ b/src/mds-kbdc/validate-tree.c
@@ -0,0 +1,548 @@
+/**
+ * mds — A micro-display server
+ * Copyright © 2014  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * 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 3 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, see <http://www.gnu.org/licenses/>.
+ */
+#include "validate-tree.h"
+
+#include <stdlib.h>
+#include <errno.h>
+
+
+
+/**
+ * Tree type constant shortener
+ */
+#define C(TYPE)  MDS_KBDC_TREE_TYPE_##TYPE
+
+/**
+ * Add an error to the error list
+ * 
+ * @param  NODE:const mds_kbdc_tree_t*    The node the triggered the error
+ * @param  SEVERITY:identifier            * in `MDS_KBDC_PARSE_ERROR_*` to indicate severity
+ * @param  ...:const char*, ...           Error description format string and arguments
+ * @scope  error:mds_kbdc_parse_error_t*  Variable where the new error will be stored
+ */
+#define NEW_ERROR(NODE, SEVERITY, ...)					\
+  NEW_ERROR_(result, SEVERITY, 1, (NODE)->loc_line,			\
+	     (NODE)->loc_start, (NODE)->loc_end, 1, __VA_ARGS__)
+
+/**
+ * Add “included from here”-notes
+ * 
+ * @param  PTR:size_t  The number of “included from here”-notes
+ */
+#define DUMP_INCLUDE_STACK(PTR)		\
+  fail_if (dump_include_stack(PTR))
+
+/**
+ * Add an error with “included from here”-notes to the error list
+ * 
+ * @param  NODE:const mds_kbdc_tree_t*    The node the triggered the error
+ * @param  PTR:size_t                     The number of “included from here”-notes
+ * @param  SEVERITY:identifier            * in `MDS_KBDC_PARSE_ERROR_*` to indicate severity
+ * @param  ...:const char*, ...           Error description format string and arguments
+ * @scope  error:mds_kbdc_parse_error_t*  Variable where the new error will be stored
+ */
+#define NEW_ERROR_WITH_INCLUDES(NODE, PTR, SEVERITY, ...)	\
+  do								\
+    {								\
+      NEW_ERROR(NODE, SEVERITY, __VA_ARGS__);			\
+      DUMP_INCLUDE_STACK(PTR);					\
+    }								\
+  while (0)
+
+
+
+/**
+ * Variable whether the latest created error is stored
+ */
+static mds_kbdc_parse_error_t* error;
+
+/**
+ * The parameter of `process_includes`
+ */
+static mds_kbdc_parsed_t* restrict result;
+
+/**
+ * Stack of visited include-statements
+ */
+static mds_kbdc_tree_include_t** restrict includes = NULL;
+
+/**
+ * The number elements allocated for `includes`
+ */
+static size_t includes_size = 0;
+
+/**
+ * The number elements stored in `includes`
+ */
+static size_t includes_ptr = 0;
+
+/**
+ * Stack of visited for-statements
+ */
+static mds_kbdc_tree_for_t** restrict fors = NULL;
+
+/**
+ * The number elements allocated for `fors`
+ */
+static size_t fors_size = 0;
+
+/**
+ * The number elements stored in `fors`
+ */
+static size_t fors_ptr = 0;
+
+/**
+ * The function definition that is currently being visited
+ */
+static mds_kbdc_tree_function_t* function = NULL;
+
+/**
+ * The macro definition that is currently being visited
+ */
+static mds_kbdc_tree_macro_t* macro = NULL;
+
+/**
+ * The information clause that is currently being visited
+ */
+static mds_kbdc_tree_information_t* information = NULL;
+
+/**
+ * The assumption clause that is currently being visited
+ */
+static mds_kbdc_tree_assumption_t* assumption = NULL;
+
+/**
+ * The value `includes_ptr` had when `function`,
+ * `macro`, `information` or `assumption` was set
+ */
+static size_t def_includes_ptr = 0;
+
+
+
+/**
+ * Validate that a part of the structure of the compilation unit
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_subtree(mds_kbdc_tree_t* restrict tree);
+
+
+
+/**
+ * Add “included from here”-notes
+ * 
+ * @param   ptr  The number of “included from here”-notes
+ * @return       Zero on success, -1 on error
+ */
+static int dump_include_stack(size_t ptr)
+{
+  while (ptr--)
+    NEW_ERROR(includes[ptr], NOTE, "included from here");
+  return 0;
+ pfail:
+  return -1;
+} 
+
+  
+/**
+ * Validate an include-statement
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_include(mds_kbdc_tree_include_t* restrict tree)
+{
+  mds_kbdc_tree_include_t** old;
+  int r, saved_errno;
+  if (includes_ptr == includes_size)
+    if (xxrealloc(old, includes, includes_size += 4, mds_kbdc_tree_include_t*))
+      return saved_errno = errno, free(old), errno = saved_errno, -1;
+  includes[includes_ptr++] = tree;
+  r = validate_subtree(tree->inner);
+  return includes_ptr--, r;
+}
+
+
+/**
+ * Validate a function definition
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_function(mds_kbdc_tree_function_t* restrict tree)
+{
+  int r;
+  if (function)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "nested function definition");
+      NEW_ERROR_WITH_INCLUDES(function, def_includes_ptr, NOTE, "outer function defined here");
+      return 0;
+    }
+  else if (macro)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "function definition inside macro definition");
+      NEW_ERROR_WITH_INCLUDES(macro, def_includes_ptr, NOTE, "outer macro defined here");
+      return 0;
+    }
+  else if (information)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "function definition inside information clause");
+      NEW_ERROR_WITH_INCLUDES(information, def_includes_ptr, NOTE, "outer information clause defined here");
+      return 0;
+    }
+  else if (assumption)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "function definition inside assumption clause");
+      NEW_ERROR_WITH_INCLUDES(assumption, def_includes_ptr, NOTE, "outer assumption clause defined here");
+      return 0;
+    }
+  function = tree;
+  def_includes_ptr = includes_ptr;
+  r = validate_subtree(tree->inner);
+  return function = NULL, r;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate a macro definition
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_macro(mds_kbdc_tree_macro_t* restrict tree)
+{
+  int r;
+  if (function)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "macro definition inside function definition");
+      NEW_ERROR_WITH_INCLUDES(function, def_includes_ptr, NOTE, "outer function definition defined here");
+      return 0;
+    }
+  else if (macro)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "nested macro definition");
+      NEW_ERROR_WITH_INCLUDES(macro, def_includes_ptr, NOTE, "outer macro defined here");
+      return 0;
+    }
+  else if (information)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "macro definition inside information clause");
+      NEW_ERROR_WITH_INCLUDES(information, def_includes_ptr, NOTE, "outer information clause defined here");
+      return 0;
+    }
+  else if (assumption)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "macro definition inside assumption clause");
+      NEW_ERROR_WITH_INCLUDES(assumption, def_includes_ptr, NOTE, "outer assumption clause defined here");
+      return 0;
+    }
+  macro = tree;
+  def_includes_ptr = includes_ptr;
+  r = validate_subtree(tree->inner);
+  return macro = NULL, r;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate an information clause
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_information(mds_kbdc_tree_information_t* restrict tree)
+{
+  int r;
+  if (function)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "information clause inside function definition");
+      NEW_ERROR_WITH_INCLUDES(function, def_includes_ptr, NOTE, "outer function definition defined here");
+      return 0;
+    }
+  else if (macro)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "information clause inside macro definition");
+      NEW_ERROR_WITH_INCLUDES(macro, def_includes_ptr, NOTE, "outer macro defined here");
+      return 0;
+    }
+  else if (information)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "nested information clause");
+      NEW_ERROR_WITH_INCLUDES(information, def_includes_ptr, NOTE, "outer information clause defined here");
+      return 0;
+    }
+  else if (assumption)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "information clause inside assumption clause");
+      NEW_ERROR_WITH_INCLUDES(assumption, def_includes_ptr, NOTE, "outer assumption clause defined here");
+      return 0;
+    }
+  information = tree;
+  def_includes_ptr = includes_ptr;
+  r = validate_subtree(tree->inner);
+  return information = NULL, r;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate an assumption clause
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_assumption(mds_kbdc_tree_assumption_t* restrict tree)
+{
+  int r;
+  if (function)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "assumption clause inside function definition");
+      NEW_ERROR_WITH_INCLUDES(function, def_includes_ptr, NOTE, "outer function definition defined here");
+      return 0;
+    }
+  else if (macro)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "assumption clause inside macro definition");
+      NEW_ERROR_WITH_INCLUDES(macro, def_includes_ptr, NOTE, "outer macro defined here");
+      return 0;
+    }
+  else if (information)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "assumption clause inside information clause");
+      NEW_ERROR_WITH_INCLUDES(information, def_includes_ptr, NOTE, "outer information clause defined here");
+      return 0;
+    }
+  else if (assumption)
+    {
+      NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "nested assumption clause");
+      NEW_ERROR_WITH_INCLUDES(assumption, def_includes_ptr, NOTE, "outer assumption clause defined here");
+      return 0;
+    }
+  information = tree;
+  def_includes_ptr = includes_ptr;
+  r = validate_subtree(tree->inner);
+  return information = NULL, r;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate a mapping- or value-statement
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_map(mds_kbdc_tree_map_t* restrict tree)
+{
+  int is_value = tree->result == NULL;
+  if (information && is_value)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "value-statement inside information clause");
+  else if (information)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "mapping-statement inside information clause");
+  else if (assumption && is_value)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "value-statement inside assumption clause");
+  else if (assumption)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "mapping-statement inside assumption clause");
+  else if (function && !is_value)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "mapping-statement inside function definition");
+  else if ((function == NULL) && is_value)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "value-statement outside function definition");
+    /* FIXME \set outside function definition must be supported */
+  return 0;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate a macro call
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_macro_call(mds_kbdc_tree_macro_call_t* restrict tree)
+{
+  if (information)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "macro call inside information clause");
+  else if (assumption)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "macro call inside assumption clause");
+  else if (function)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "macro call inside function definition");
+  return 0;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate a for-statement
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_for(mds_kbdc_tree_for_t* restrict tree)
+{
+  mds_kbdc_tree_for_t** old;
+  int r, saved_errno;
+  if (fors_ptr == fors_size)
+    if (xxrealloc(old, fors, fors_size += 4, mds_kbdc_tree_for_t*))
+      return saved_errno = errno, free(old), errno = saved_errno, -1;
+  fors[fors_ptr++] = tree;
+  r = validate_subtree(tree->inner);
+  return fors_ptr--, r;
+}
+
+
+/**
+ * Validate a if-statement
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_if(mds_kbdc_tree_if_t* restrict tree)
+{
+  return -(validate_subtree(tree->inner) ||
+	   validate_subtree(tree->otherwise));
+}
+
+
+/**
+ * Validate a return-statement
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_return(mds_kbdc_tree_return_t* restrict tree)
+{
+  if ((function == NULL) && (macro == NULL))
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "‘return’ outside function and macro definition");
+  return 0;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate a break-statement
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_break(mds_kbdc_tree_break_t* restrict tree)
+{
+  if (fors_ptr == 0)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "‘break’ outside ‘for’");
+  return 0;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate a continue-statement
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_continue(mds_kbdc_tree_continue_t* restrict tree)
+{
+  if (fors_ptr == 0)
+    NEW_ERROR_WITH_INCLUDES(tree, includes_ptr, ERROR, "‘continue’ outside ‘for’");
+  return 0;
+ pfail:
+  return -1;
+}
+
+
+/**
+ * Validate that a part of the structure of the compilation unit
+ * 
+ * @param   tree  The tree to validate
+ * @return        Zero on success, -1 on error
+ */
+static int validate_subtree(mds_kbdc_tree_t* restrict tree)
+{
+#define v(type)  if ((r = validate_##type(&(tree->type))))     return r
+#define V(type)  if ((r = validate_##type(&(tree->type##_))))  return r
+  int r;
+ again:
+  if (tree == NULL)
+    return 0;
+  
+  switch (tree->type)
+    {
+    case C(INFORMATION):            v(information);            break;
+    //case C(INFORMATION_LANGUAGE):   v(information_language);   break;
+    //case C(INFORMATION_COUNTRY):    v(information_country);    break;
+    //case C(INFORMATION_VARIANT):    v(information_variant);    break;
+    case C(INCLUDE):                v(include);                break;
+    case C(FUNCTION):               v(function);               break;
+    case C(MACRO):                  v(macro);                  break;
+    case C(ASSUMPTION):             v(assumption);             break;
+    //case C(ASSUMPTION_HAVE):        v(assumption_have);        break;
+    //case C(ASSUMPTION_HAVE_CHARS):  v(assumption_have_chars);  break;
+    //case C(ASSUMPTION_HAVE_RANGE):  v(assumption_have_range);  break;
+    case C(FOR):                    V(for);                    break;
+    case C(IF):                     V(if);                     break;
+    case C(MAP):                    v(map);                    break;
+    case C(MACRO_CALL):             v(macro_call);             break;
+    case C(RETURN):                 V(return);                 break;
+    case C(BREAK):                  V(break);                  break;
+    case C(CONTINUE):               V(continue);               break;
+    default:
+      break;
+    }
+  
+  tree = tree->next;
+  goto again;
+#undef V
+#undef v
+}
+
+
+/**
+ * Validate that the structure of the compilation unit
+ * 
+ * @param   result_  `result` from `process_includes`, will be updated
+ * @return           -1 if an error occursed that cannot be stored in `result`, zero otherwise
+ */
+int validate_tree(mds_kbdc_parsed_t* restrict result_)
+{
+  int r, saved_errno;
+  result = result_;
+  r = validate_subtree(result_->tree);
+  saved_errno = errno;
+  free(includes), includes = NULL, includes_size = includes_ptr = 0;
+  free(fors),     fors     = NULL,     fors_size =     fors_ptr = 0;
+  return errno = saved_errno, r;
+}
+
+
+
+#undef NEW_ERROR_WITH_INCLUDES
+#undef DUMP_INCLUDE_STACK
+#undef NEW_ERROR
+#undef C
+
+ 
diff --git a/src/mds-kbdc/validate-tree.h b/src/mds-kbdc/validate-tree.h
new file mode 100644
index 0000000..7c92928
--- /dev/null
+++ b/src/mds-kbdc/validate-tree.h
@@ -0,0 +1,35 @@
+/**
+ * mds — A micro-display server
+ * Copyright © 2014  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * 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 3 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, see <http://www.gnu.org/licenses/>.
+ */
+#ifndef MDS_MDS_KBDC_VALIDATE_TREE_H
+#define MDS_MDS_KBDC_VALIDATE_TREE_H
+
+
+#include "parsed.h"
+
+
+/**
+ * Validate that the structure of the compilation unit
+ * 
+ * @param   result  `result` from `process_includes`, will be updated
+ * @return          -1 if an error occursed that cannot be stored in `result`, zero otherwise
+ */
+int validate_tree(mds_kbdc_parsed_t* restrict result);
+
+
+#endif
+