better fixedepoint iter for gamma-gamma

7 files changed, 148 insertions, 42 deletions

diff --git a/README.txt b/README.txt
new file mode 100644
index 0000000..31591d5
--- /dev/null
+++ b/README.txt
@@ -0,0 +1 @@
+####### Gamma: Backwards-Compatible Templates for C #######
diff --git a/gamma_version/Makefile b/gamma_version/Makefile
index e0ced6a..81bd4e5 100644
--- a/gamma_version/Makefile
+++ b/gamma_version/Makefile
@@ -17,6 +17,7 @@ OBJS=build/main.o \
      build/fakeobj.o \
      build/hashmap.o \
      build/hash_functions.o \
+     build/vector.o \
      build/debug.o
 
 build/gc: $(OBJS)
diff --git a/gamma_version/gamma.h b/gamma_version/gamma.h
index ce35d7c..6ec36ce 100644
--- a/gamma_version/gamma.h
+++ b/gamma_version/gamma.h
@@ -23,11 +23,22 @@ int hashmap_contains::[type T](struct hashmap::[T] *hashmap, T *item);
 void hashmap_insert::[type T](struct hashmap::[T] *hashmap, T *item);
 T *heapify::[type T](T item);
 
+struct vector::[type T] {
+    T *data;
+    size_t count;
+    size_t cap;
+};
+uint32_t vector_push::[type T](struct vector::[T] *vector, T item);
+T vector_pop::[type T](struct vector::[T] *vector);
+struct vector::[T] *init_vector::[type T]();
+
 struct uniq_string {
     char *string;
     size_t len;
-    // macro idents have an associated set of concrete instantiations
-    struct hashmap::[struct call] set;
+    // macro idents have an associated list of instantiations
+    struct vector::[struct call *] instantiations;
+    // macro idents have an associated list of definitions
+    struct chunk *definitions;
 };
 
 struct arg {
@@ -51,6 +62,7 @@ struct chunk {
     struct call *defining_call;
     struct call *calls;
     struct chunk *next;
+    struct chunk *next_definition;
 };
 
 struct chunked_file {
diff --git a/gamma_version/main.c b/gamma_version/main.c
index 5cbcfaa..fcb1374 100644
--- a/gamma_version/main.c
+++ b/gamma_version/main.c
@@ -150,11 +150,10 @@ int main(int argc, char **argv) {
         char *dst_path = ARGV[file->id];
         for (struct chunk *chunk = file->chunks; chunk; chunk = chunk->next) {
             if (chunk->defining_call) {
-                struct hashmap::[struct call] *set = &(chunk->defining_call->name->set);
-                if (!set) continue;
-                for (size_t i = 0; i < set->cap; i++) {
-                    struct call *instantiation = set->data[i];
-                    if (!instantiation) continue;
+                struct vector::[struct call *] instantiations
+                    = chunk->defining_call->name->instantiations;
+                for (size_t i = 0; i < instantiations.count; i++) {
+                    struct call *instantiation = instantiations.data[i];
                     if (instantiation->n_args != chunk->defining_call->n_args) continue;
                     // needed for specialization
                     for (size_t j = 0; j < instantiation->n_args; j++) {
@@ -163,7 +162,7 @@ int main(int argc, char **argv) {
                                 != instantiation->args[j].string)
                             goto bad_instantiation;
                     }
-                    print_chunk(chunk, set->data[i], c_file);
+                    print_chunk(chunk, instantiation, c_file);
     bad_instantiation: continue;
                 }
             } else {
diff --git a/gamma_version/solve.c b/gamma_version/solve.c
index 3fcb5b9..3c89937 100644
--- a/gamma_version/solve.c
+++ b/gamma_version/solve.c
@@ -52,48 +52,47 @@ void solve(struct chunked_file *files) {
     }
     }
 
-    // (1) add all the concrete instantiations
-    for (struct chunked_file *file = files; file; file = file->next) {
+    // (0.5) link up chunk definitions
+    for (struct chunked_file *file = files; file; file = file->next)
     for (struct chunk *chunk = file->chunks; chunk; chunk = chunk->next) {
+        if (!chunk->defining_call) continue;
+        struct uniq_string *name = chunk->defining_call->name;
+        chunk->next_definition = name->definitions;
+        name->definitions = chunk;
+    }
+
+    // (1) add all the concrete instantiations
+    struct hashmap::[struct call] *memo = calloc(1, sizeof(*memo));
+    struct vector::[struct call *] *queue = init_vector::[struct call *]();
+    for (struct chunked_file *file = files; file; file = file->next)
+    for (struct chunk *chunk = file->chunks; chunk; chunk = chunk->next)
     for (struct call *call = chunk->calls; call; call = call->next) {
-        if (is_instantiation(call) && !hashmap_contains::[struct call](&(call->name->set), call)) {
-            hashmap_insert::[struct call](&(call->name->set), call);
+        if (is_instantiation(call) && !hashmap_contains::[struct call](memo, call)) {
+            hashmap_insert::[struct call](memo, call);
+            vector_push::[struct call *](queue, call);
         }
     }
-    }
-    }
 
     // (2) apply rules to fixedpoint
-    int keep_going = 1;
-    while (keep_going--) {
-        for (struct chunked_file *file = files; file; file = file->next) {
-        for (struct chunk *chunk = file->chunks; chunk; chunk = chunk->next) {
-            if (!(chunk->defining_call)) continue;
-            struct hashmap::[struct call] *set = &(chunk->defining_call->name->set);
-            if (!set) continue;
-
-            // iterate over all of the concrete instantiations required of this
-            // chunk/template.
-            for (size_t i = 0; i < set->cap; i++) {
-                struct call *instantiation = set->data[i];
-                if (!instantiation) continue;
-                for (struct call *call = chunk->calls; call; call = call->next) {
-                    struct call *new = replace_variables(chunk->defining_call, instantiation, call);
-                    if (!new) continue;
-                    if (hashmap_contains::[struct call](&(new->name->set), new)) {
-                        free(new->args);
-                        free(new);
-                        continue;
-                    }
-                    hashmap_insert::[struct call](&(new->name->set), new);
-                    // printf("Adding call: ");
-                    // print_call(new);
-                    // printf("\n");
-                    // print_set(new->name->set);
-                    keep_going = 1;
+    while (queue->count) {
+        struct call *instantiation = vector_pop::[struct call *](queue);
+        vector_push::[struct call *](&(instantiation->name->instantiations),
+                                     instantiation);
+        for (struct chunk *chunk = instantiation->name->definitions;
+                chunk; chunk = chunk->next_definition) {
+            assert(chunk->defining_call);
+            assert(chunk->defining_call->name == instantiation->name);
+            for (struct call *call = chunk->calls; call; call = call->next) {
+                struct call *new = replace_variables(chunk->defining_call, instantiation, call);
+                if (!new) continue;
+                if (hashmap_contains::[struct call](memo, new)) {
+                    free(new->args);
+                    free(new);
+                    continue;
                 }
+                hashmap_insert::[struct call](memo, new);
+                vector_push::[struct call *](queue, new);
             }
         }
-        }
     }
 }
diff --git a/gamma_version/vector.c b/gamma_version/vector.c
new file mode 100644
index 0000000..22d50b9
--- /dev/null
+++ b/gamma_version/vector.c
@@ -0,0 +1,18 @@
+#include "gamma.h"
+
+uint32_t vector_push::[type T](struct vector::[T] *vector, T item) {
+    if ((2 * vector->count) >= vector->cap) {
+        vector->cap *= 4;
+        vector->cap = vector->cap ? vector->cap : 128;
+        vector->data = realloc(vector->data, vector->cap * sizeof(vector->data[0]));
+    }
+    vector->data[vector->count++] = item;
+}
+
+T vector_pop::[type T](struct vector::[T] *vector) {
+    return vector->data[--(vector->count)];
+}
+
+struct vector::[T] *init_vector::[type T]() {
+    return calloc(1, sizeof(struct vector::[T]));
+}
diff --git a/py_version/README.md b/py_version/README.md
new file mode 100644
index 0000000..28f26f1
--- /dev/null
+++ b/py_version/README.md
@@ -0,0 +1,76 @@
+# User Instructions
+
+First, build the lexer:
+
+    $ make -C gamma
+
+Then, in your makefile:
+
+    CC=/path/to/gc gcc
+    LD=/path/to/gc gcc
+
+(any C compiler supporting the -E option can be used in place of 'gcc' above)
+
+# Known issues
+
+Searching for header files may not work properly.
+
+Paths with spaces will die
+
+Currently, the only input formats recognized are: .c, .o, and .a. We plan to
+support .so.
+
+If you declare a local/global array variable with the same name as a generic,
+it will be interpreted and instantiated as that generic. This behavior is
+similar to naming a function or variable the same thing as a preprocessor
+macro.
+
+    To help with this, Gamma will lex `ident.` as a single identifier. This
+    means you can use `ident.[int]` and `ident.[type T]` to place your
+    templates in a separate namespace from normal C identifiers.
+
+Line info will get completely butchered
+
+Your builds will slow down. There are currently two sources of this: (1) we
+serialize everything, and (2) the time it takes to actually
+preprocess/instantiate templates/etc. We have plans to fix the former, but the
+latter is a bit more unavoidable until we self-host in gamma.
+
+    As an initial help, if a file does not contain any template definitions,
+    declarations, or uses, it gets exempted from further processing (i.e., an
+    actual .o is made). On the sbase repository, our build slowdown with this
+    optimization is about 4x.
+
+If the .c file uses templates, then the .o files produced by `gc` will not
+proper ELF files, so you shouldn't try to objdump them/etc.
+
+# Gamma design
+
+## PARSER
+The PARSER is an internal method that takes a C file and identifies the
+following:
+
+    1. All the template definitions
+    2. All the template instantiations
+
+Instantiations can be nested within a definition.
+
+'Definitions' includes declarations; basically anything defined or declared at
+the global scope
+
+CURRENTLY, the parser rules are:
+
+    1. Anything at the top scope that sees a "] (" or "] {" before any other
+       open brace is considered a template definition
+    2. Anything of the form "X [ ... ]" where "X" is an earlier-defined
+       (declared) template is considered a use (call)
+
+## INSTANTIATOR:
+- Parse a file, splitting into 'calls' and 'rules'
+- Solve for the concrete instantiations (calls) needed
+- Rewrite the file, replacing each template definition with all of its concrete
+  instantiations
+
+## MANGLER
+Given a file, parses and it replaces every template use "X [ A, B, ...]" with
+"X_A_B_..."