Merge branch 'scopes' into types

14 files changed, 421 insertions, 35 deletions

diff --git a/check/main.p b/check/main.p
new file mode 100644
index 0000000..f05808b
--- /dev/null
+++ b/check/main.p
@@ -0,0 +1,34 @@
+program main ( input, output );
+
+        var a, b: integer;
+        var x,y,z: real;
+	var ai :array [1..10] of integer;
+	procedure boo (n: integer);
+	var a,c: integer;
+	begin
+		a := n
+	end;
+	function bar (a: integer) : real;
+	var test:integer;
+	begin
+		test := 2;
+		a := 2
+	end;
+	procedure foo;
+	begin
+		a := 33333;
+		x := 1e10;
+		z := 1e-10;
+		y := 2.5543e-2
+	end;
+begin
+{ TEST }
+
+	a := 1;
+        x := 3.14;
+	b := a + 35;
+	(* test *)
+	for c := 0 to 10 do begin
+		for a:= 10 downto 0 do b := a - c
+	end
+end.
diff --git a/check/nesting.p b/check/nesting.p
new file mode 100644
index 0000000..6d24b6b
--- /dev/null
+++ b/check/nesting.p
@@ -0,0 +1,69 @@
+
+program main ( input, output );
+
+        var a, b: integer;
+        var x,y,z: real;
+	var ai :array [1..10] of integer;
+	procedure boo (n: integer);
+	var a,c: integer;
+	begin
+		a := n
+	end;
+	function bar (a: integer) : real;
+	var test:integer;
+	begin
+		test := 2;
+		a := 2
+	end;
+	procedure foo;
+                procedure foo2;
+                        procedure foo13;
+                                procedure foo4;
+                                        procedure foo5;
+                                                procedure foo6;
+                                                        procedure foo7;
+                                                                procedure foo46;
+                                                                        procedure fooaoesut;
+                                                                                procedure foosathst;
+                                                                                        procedure foothsth;
+                                                                                        begin
+                                                                                                a := 33333
+                                                                                        end;
+                                                                                begin
+                                                                                        a := 33333
+                                                                                end;
+                                                                        begin
+                                                                                a := 33333
+                                                                        end;
+                                                                begin
+                                                                        a := 33333
+                                                                end;
+                                                        begin
+                                                                a := 33333
+                                                        end;
+                                                begin
+                                                        a := 33333
+                                                end;
+                                        begin
+                                                a := 33333
+                                        end;
+                                begin
+                                        a := 33333
+                                end;
+                        begin
+                                a := 33333
+                        end;
+                begin
+                        a := 33333
+                end;
+	begin
+		a := 33333
+	end;
+begin
+{ TEST }
+
+	a := 1;
+        x := 3.14;
+	b := a + 35
+	(* test *)
+end.
diff --git a/main.c b/main.c
index 3d1401c..dba3b7f 100644
--- a/main.c
+++ b/main.c
@@ -2,12 +2,16 @@
 #include <stdlib.h>
 #include <assert.h>
 
+#include "node.h"
+#include "scope.h"
 #include "y.tab.h"
 #include "pc.h"
 
 extern char *yytext;
 extern int line_num;
 
+scope *cur_scope;
+
 char* pretty_type(t)
 int t;
 {
@@ -134,6 +138,9 @@ char* msg;
 
 int main()
 {
+	cur_scope = mkscope();
+	assert(cur_scope);
+
 	yyparse();
 
 	return 0;
diff --git a/makefile b/makefile
index 2ae5ae0..27d0649 100644
--- a/makefile
+++ b/makefile
@@ -1,21 +1,24 @@
-CC = gcc
+CC = tcc
 FLAGS = -g
 YACC = yacc
 LEX = lex
 
-mypc: y.tab.o lex.yy.o tree.o node.o pc.o
-	$(CC) $(FLAGS) -o mypc main.o tree.o node.o y.tab.o lex.yy.o -lfl -ly
+mypc: y.tab.o lex.yy.o tree.o scope.o node.o pc.o sem_check.o
+	$(CC) $(FLAGS) -o mypc main.o tree.o scope.o sem_check.o node.o y.tab.o lex.yy.o -lfl -ly
 
-pc.o: main.c pc.h
+pc.o: main.c headers
 	$(CC) $(FLAGS) -c main.c
 
-tree.o: tree.c tree.h
+tree.o: tree.c headers
 	$(CC) $(FLAGS) -c tree.c
 
-hash.o: hash.c hash.h
-	$(CC) $(FLAGS) -c hash.c
+sem_check.o: sem_check.c headers
+	$(CC) $(FLAGS) -c sem_check.c
 
-node.o: node.c node.h
+scope.o: scope.c headers
+	$(CC) $(FLAGS) -c scope.c
+
+node.o: node.c headers
 	$(CC) $(FLAGS) -c node.c
 
 y.tab.o: y.tab.c
@@ -30,5 +33,7 @@ y.tab.c: pc.y
 lex.yy.c: pc.l
 	$(LEX) -l pc.l
 
+headers: pc.h tree.h sem_check.h y.tab.h scope.h node.h y.tab.c
+
 clean:
 	rm -f mypc *.o y.tab.* lex.yy.*
diff --git a/node.c b/node.c
index e1b7920..586ed52 100644
--- a/node.c
+++ b/node.c
@@ -19,7 +19,7 @@ char *str;
 }
 
 /* helpers */
-node* search(root, str)
+node* list_search(root, str)
 node *root;
 char *str;
 {
@@ -33,7 +33,7 @@ char *str;
 	return NULL;
 }
 
-node* insert(root, str) /*TODO change to accept double pointer*/
+node* list_insert(root, str) /*TODO change to accept double pointer*/
 node *root;
 char * str;
 {
@@ -41,3 +41,16 @@ char * str;
 	p->next = root;
 	return p;
 }
+
+void free_list(n)
+node *n;
+{
+	node *tmp;
+
+	for(tmp = n; tmp;) {
+		n = tmp->next;
+		free(tmp);
+		tmp = NULL;
+		tmp = n;
+	}
+}
diff --git a/node.h b/node.h
index 5206db4..90e3936 100644
--- a/node.h
+++ b/node.h
@@ -13,7 +13,9 @@ typedef struct node_s {
 node* mknode(char *);
 
 /* helpers */
-node* search(node*, char *);
-node* insert(node*, char*);
+node* list_search(node*, char *);
+node* list_insert(node*, char*);
+
+void free_list(node*);
 
 #endif
diff --git a/pc.l b/pc.l
index 1a686d3..657f080 100644
--- a/pc.l
+++ b/pc.l
@@ -1,9 +1,11 @@
 %{
-
+#include "node.h"
+#include "scope.h"
 #include "y.tab.h"
 #include "pc.h"
 
 int line_num=1;
+extern scope *cur_scope;
 
 %}
 
@@ -39,13 +41,13 @@ id	[A-Za-z][A-Za-z0-9_]*
 
 "procedure" {
 	debug_print(PROC, NULL);
-	/*s = push_scope(s);*/
+	push_scope(&cur_scope);
 	return PROC;
 }
 
 "function" {
 	debug_print(FUNC, NULL);
-	/*s = push_scope(s);*/
+	push_scope(&cur_scope);
 	return FUNC;
 }
 
diff --git a/pc.y b/pc.y
index 050aedc..8e0130c 100644
--- a/pc.y
+++ b/pc.y
@@ -3,17 +3,15 @@
 #include <stddef.h>
 
 #include "node.h"
+#include "scope.h"
 #include "tree.h"
 #include "y.tab.h"
 #include "pc.h"
-/*#include "sem_check.h"*/
+#include "sem_check.h"
 
-/*
-TODO:
-- Add checkid() to counter mkid()
-*/
 
 extern int yylex();
+extern scope *cur_scope;
 
 %}
 
@@ -71,6 +69,8 @@ extern int yylex();
 %type <tval> simple_expr
 
 %type <tval> id_list
+%type <tval> param_list
+%type <tval> arguments
 %type <tval> expr_list
 
 %type <tval> statement
@@ -98,11 +98,20 @@ program
 id_list
 	:ID
 	{
-		$$ = mkid($1);
+		/*TODO remove check_ids*/
+		node *tmp;
+		check_id(cur_scope, $1);
+
+		tmp = scope_insert(cur_scope, $1);
+		$$ = mkid(tmp);
 	}
 	|id_list ',' ID
 	{
-		$$ = mktree(LIST, $1, mkid($3));
+		node *tmp;
+
+		check_id(cur_scope, $3);
+		tmp = scope_insert(cur_scope, $3);
+		$$ = mktree(LIST, $1, mkid(tmp));
 	}
 ;
 
@@ -148,21 +157,31 @@ sub_prog_declaration
 	 sub_prog_declarations
 	 compound_statement
 	{
+		pop_scope(&cur_scope);
 	}
 ;
 
+/*push_scope called in pc.l*/
 sub_prog_head
 	:FUNC ID arguments ':' standard_type ';'
 	{
+		check_id(cur_scope->prev, $2);
+		scope_insert(cur_scope->prev, $2);
+
+		cur_scope->ret_var = scope_insert(cur_scope, $2);
+		cur_scope->ret_var->var_type = $5;
 	}
 	|PROC ID arguments ';'
 	{
+		check_id(cur_scope->prev, $2);
+		scope_insert(cur_scope->prev, $2);
 	}
 ;
 
 arguments
 	:'(' param_list ')'
 	{
+		$$ = $2;
 	}
 	|/*empty*/
 ;
@@ -170,9 +189,11 @@ arguments
 param_list
 	:id_list ':' type
 	{
+		$$ = $1;
 	}
 	|param_list ';' id_list ':' type
 	{
+		$$ = mktree(LIST, $1, $3);
 	}
 ;
 
@@ -238,22 +259,31 @@ TD: TO | DT;
 var
 	:ID
 	{
-		$$ = mkid($1);
+		$$ = mkid(scope_insert(cur_scope,$1));
 	}
 	|ID '[' expr ']'
 	{
-		$$ = mktree(ARRAY_ACCESS, mkid($1), $3);
+		node* tmp;
+		tmp = scope_insert(cur_scope, $1);
+
+		$$ = mktree(ARRAY_ACCESS, mkid(tmp), $3);
 	}
 ;
 
 proc_statement
 	:ID
 	{
-		$$ = mkid($1);
+		node *tmp;
+
+		tmp = check_exists(cur_scope, $1);
+		$$ = mktree(PCALL, mkid(tmp), NULL);
 	}
 	|ID '(' expr_list ')'
 	{
-		$$ = mktree(PCALL, mkid($1), $3);
+		node *tmp;
+
+		tmp = check_exists(cur_scope, $1);
+		$$ = mktree(PCALL, mkid(tmp), $3);
 	}
 ;
 
@@ -304,15 +334,24 @@ term
 factor
 	:ID
 	{
-		$$ = mkid($1);
+		node *tmp;
+
+		tmp = check_exists(cur_scope, $1);
+		$$ = mkid(tmp);
 	}
 	|ID '[' expr ']'
 	{
-		$$ = mktree(ARRAY_ACCESS, mkid($1), $3);
+		node *tmp;
+
+		tmp = check_exists(cur_scope, $1);
+		$$ = mktree(ARRAY_ACCESS, mkid(tmp), $3);
 	}
 	|ID '(' expr_list ')'
 	{
-		$$ = mktree(FCALL, mkid($1), $3);
+		node *tmp;
+
+		tmp = check_exists(cur_scope, $1);
+		$$ = mktree(FCALL, mkid(tmp), $3);
 	}
 	|INUM
 	{
diff --git a/scope.c b/scope.c
new file mode 100644
index 0000000..6706765
--- /dev/null
+++ b/scope.c
@@ -0,0 +1,146 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+#include <string.h>
+
+#include "node.h"
+#include "scope.h"
+
+scope* mkscope()
+{
+	int i;
+	
+	scope *p = malloc(sizeof(scope));
+	assert(p);
+
+	for (i = 0; i < HASH_SIZE; i++)
+		p->table[i] = NULL;
+
+	p->prev = NULL;
+	p->ret_var= NULL;
+
+	return p;
+}
+
+void free_scope(s)
+scope *s;
+{
+	int i;
+
+	if (!s)
+		return;
+
+	for (i = 0; i < HASH_SIZE; i++) {
+		free_list(s->table[i]);
+	}
+
+	free(s);
+	s = NULL;
+}
+
+/*Copied from Compilers, Aho*/
+#define EOS '\0'
+int hashpjw(s)
+char* s;
+{
+	char *p;
+	unsigned h = 0, g;
+
+	for (p = s; *p != EOS; p++) {
+		h = (h<<4) + *p;
+		if (g = h & 0xf0000000) {
+			h^= g>>24;
+			h^= g;
+		}
+	}
+
+	return h % HASH_SIZE;
+}
+
+void push_scope(root)
+scope **root;
+{
+	scope *tmp = mkscope();
+	
+	assert(tmp);
+
+	tmp->prev = *root;
+	*root = tmp;
+}
+
+void pop_scope(root)
+scope **root;
+{
+	scope *tmp;
+
+	if (!*root)
+		return;
+
+	tmp = *root;
+	*root = (*root)->prev;
+
+	free_scope(tmp);
+}
+
+node* scope_insert(root, name)
+scope *root;
+char *name;
+{
+	int hash = hashpjw(name);
+
+	node *tmp = root->table[hash];
+	return root->table[hash] = list_insert(tmp, name);
+}
+
+node* scope_search(root, name)
+scope *root;
+char *name;
+{
+	int hash = hashpjw(name);
+
+	node *tmp = root->table[hash];
+	return list_search(tmp, name);
+}
+
+node* scope_search_all(root, name)
+scope *root;
+char *name;
+{
+	scope *p;
+	node *tmp;
+
+	for (p = root; p; p = p->prev)
+		if (tmp = scope_search(p, name))
+			return tmp;
+
+	return NULL;
+}
+
+node* scope_safe_search(root, name)
+scope *root;
+char *name;
+{
+	scope *p;
+	node *tmp;
+
+	for (p = root; p; p = p->prev) {
+		if (tmp = scope_search(p, name))
+			return tmp;
+		if (p->ret_var)
+			return NULL;
+	}
+
+	return NULL;
+}
+
+void print_scope(s)
+scope *s;
+{
+	int i;
+	node * tmp;
+	for (i = 0; i < HASH_SIZE; i++) {
+		for( tmp=s->table[i]; tmp; tmp = tmp->next) {
+			fprintf(stderr, "\t%s\n", tmp->name);
+		}
+	}
+}
diff --git a/scope.h b/scope.h
new file mode 100644
index 0000000..0a07a26
--- /dev/null
+++ b/scope.h
@@ -0,0 +1,27 @@
+#ifndef SCOPE_H
+#define SCOPE_H
+
+#define HASH_SIZE 211
+
+typedef struct hash {
+	node* table[HASH_SIZE];
+	struct hash *prev;
+	node* ret_var;
+} scope;
+
+scope* mkscope();
+void free_scope(scope*);
+
+/*stack routines*/
+void pop_scope(scope**);
+void push_scope(scope**);
+
+/*helpers*/
+node* scope_insert(scope*, char*);
+node* scope_search_all(scope*, char*);
+node* scope_search(scope*, char*);
+node* scope_safe_search_all(scope*, char*);
+
+/*hash function*/
+int hashpjw(char*);
+#endif
diff --git a/sem_check.c b/sem_check.c
new file mode 100644
index 0000000..637d044
--- /dev/null
+++ b/sem_check.c
@@ -0,0 +1,36 @@
+#include <assert.h>
+#include <stdio.h>
+
+#include "node.h"
+#include "scope.h"
+#include "tree.h"
+#include "y.tab.h"
+#include "pc.h"
+#include "sem_check.h"
+
+void check_id(s, n)
+scope *s;
+char *n;
+{
+	char buf[100];
+
+	if (scope_search(s, n)) {
+		snprintf(buf, 100, "\"%s\" already defined in scope...\n", n);
+		yyerror(buf);
+	}
+}
+
+node* check_exists(s, n)
+scope *s;
+char *n;
+{
+	node *tmp;
+	char buf[100];
+
+	if(!(tmp = scope_search(s,n))) {
+		snprintf(buf, 100, "Cannot find \"%s\"\n", n);
+		yyerror(buf);
+	}
+
+	return tmp;
+}
diff --git a/sem_check.h b/sem_check.h
new file mode 100644
index 0000000..eef9e96
--- /dev/null
+++ b/sem_check.h
@@ -0,0 +1,8 @@
+#ifndef SEMCHECK_H
+#define SEMCHECK_H
+
+void check_id(scope*, char*);
+
+node* check_exists(scope*, char*);
+
+#endif
diff --git a/tree.c b/tree.c
index 3a2afcf..0e27d16 100644
--- a/tree.c
+++ b/tree.c
@@ -23,12 +23,11 @@ ptree *l, *r;
 	return t;
 }
 
-ptree* mkid(str)
-char *str;
+ptree* mkid(n)
+node *n;
 {
 	ptree *p = mktree(ID, NULL, NULL);
-	p->attr.nval = malloc(sizeof(node)); /*TODO fix hacky node create*/
-	p->attr.nval->name = strdup(str); /* memory leak? double strdup*/
+	p->attr.nval = n; /* memory leak? double strdup*/
 	return p;
 }
 
diff --git a/tree.h b/tree.h
index 5506657..0d94f6d 100644
--- a/tree.h
+++ b/tree.h
@@ -6,7 +6,6 @@ typedef struct parse_tree {
 	union {
 		int ival; /* NUM */
 		float rval; /* RNUM */
-		char *sval; /* ID */
 		node *nval;
 		int opval; /* RELOP: LT LE GT GE EQ NE
 			      ADDOP: PLUS MINUS OR
@@ -20,7 +19,7 @@ void aux_tree_print(ptree*, int);
 void print_tree(ptree*);
 
 ptree* mktree(int, ptree*, ptree*);
-ptree* mkid(char*);
+ptree* mkid(node*);
 ptree* mkinum(int);
 ptree* mkrnum(float);
 ptree* mkop(int, int, ptree*, ptree*);