add dynamic typing example

15 files changed, 324 insertions, 15 deletions

diff --git a/python/.gitignore b/python/.gitignore
new file mode 100644
index 0000000..787f638
--- /dev/null
+++ b/python/.gitignore
@@ -0,0 +1,2 @@
+.*.sw*
+*.o
diff --git a/python/README.txt b/python/README.txt
index 8129c48..3dd6a96 100644
--- a/python/README.txt
+++ b/python/README.txt
@@ -5,15 +5,39 @@ Example of using a pass:
     The examples/zero_init pass zero-initializes all local variables. It can be
     run by passing a --dietc-pass flag to dietcc:
 
-        $ /path/to/dietcc examples/test_files/zero_init.c -Wuninitialized
-        ... warning: _xyz_3 is used ininitialized ...
-        $ ./a.out
+        $ which dietcc
+        [make sure it's on your path!]
+        $ cd examples/zero_init
+        $ make
+        $ ./default
         Foo return value: 0
         Foo return value: 32765
         Foo return value: 32765
-        $ /path/to/dietcc examples/test_files/zero_init.c --dietc-pass $PWD/examples/zero_init -Wuninitialized
-        [no warnings]
-        $ ./a.out
+        $ ./instrumented
         Foo return value: 0
         Foo return value: 0
         Foo return value: 0
+
+    The examples/dynamic_typing pass adds a "dynamic_typeof" feature to C:
+
+        $ which dietcc
+        [make sure it's on your path!]
+        $ cd examples/dynamic_typeof
+        $ tail -n13 test.c
+        int main() {
+            struct {
+                char x;
+                int y;
+                int z[3];
+            } foo = {1, 2, {3, 4, 5}};
+            pprint(&foo);
+            struct {
+                char a;
+                int b;
+            } bar = {100, 200};
+            pprint(&bar);
+        }
+        $ make
+        $ ./test
+        { .x = (char)1, .y = (int)2, .z = { (int)3, (int)4, (int)5 } }
+        { .a = (char)100, .b = (int)200 }
diff --git a/python/dietc.py b/python/dietc.py
index b3a0326..1101062 100644
--- a/python/dietc.py
+++ b/python/dietc.py
@@ -2,28 +2,35 @@ import sys
 from dataclasses import *
 import re
 
+# TODO: these hashes are unsafe
+
 @dataclass
 class PointerType:
     base: any
+    def __hash__(self): return id(self)
 
 @dataclass
 class ArrayType:
     base: any
     length: int
+    def __hash__(self): return id(self)
 
 @dataclass
 class FunctionType:
     return_type: any
     params: [any]
     variadic: bool
+    def __hash__(self): return id(self)
 
 @dataclass
 class AggregateType:
     fields: [any]
+    def __hash__(self): return id(self)
 
 @dataclass
 class BasicType:
     name: str
+    def __hash__(self): return id(self)
 
 @dataclass
 class Function:
@@ -62,8 +69,8 @@ class Instruction:
     def lhs_type(self, program):
         assert "=" in self.tokens
         if self[0] == "*":
-            return self.program.object_types[self[1]].base
-        return self.program.object_types[self[0]]
+            return program.object_types[self[1]].base
+        return program.object_types[self[0]]
 
 class Program:
     def __init__(self, string):
@@ -74,7 +81,7 @@ class Program:
         while lines and not (lines[1:] and lines[1].startswith("\t")):
             self.preamble.append(lines.pop(0))
         for line in self.preamble:
-            if not line.startswith("typedef"): continue
+            if not (line.startswith("typedef") or line.startswith("struct") or line.startswith("union")): continue
             types = [t for t in line.split()
                      if any(t.startswith(k) for k in ("Type_", "Struct_", "Union_"))]
             if " * " in line:
@@ -86,22 +93,24 @@ class Program:
                 self.types[types[1]] = FunctionType(
                     self.types[types[0]], [self.types[t] for t in types[2:]],
                     "..." in line)
-            elif " struct " in line or " union " in line:
+            elif "struct " in line or "union " in line:
                 if " { " in line:
                     parts = line.split()
                     # typedef struct ___
                     # { Type_ [ident] ; Type_ [ident] ; ... } Type_ ;
                     field_names = [parts[i]
-                                   for i in range(5, len(parts) - 1, 3)]
-                    field_types = [self.types[t] for t in types[:-1]]
+                                   for i in range(4, len(parts) - 1, 3)]
+                    field_types = [self.types[t] for t in types[1:]]
                     assert len(field_names) == len(field_types)
-                    self.types[types[-1]].fields \
+                    name = "Type_" + types[0].split("_")[1]
+                    self.types[name].fields \
                         = list(zip(field_names, field_types))
                 else:
                     assert types[-1] not in self.types
                     self.types[types[-1]] = AggregateType([])
             else:
-                self.types[types[0]] = BasicType(line.split()[1:-2])
+                self.types[types[0]] = BasicType(' '.join(line.split()[1:-2]))
+        self.type_to_name = {v: k for k, v in self.types.items()}
         # assign object types for globals
         for line in self.preamble:
             if not line.startswith("extern"): continue
@@ -139,3 +148,9 @@ class Program:
 
     def print(self):
         print(self.to_c().strip())
+
+def count():
+    if not hasattr(count, "COUNT"):
+        count.COUNT = 0
+    count.COUNT += 1
+    return count.COUNT
diff --git a/python/examples/dynamic_typing/.gitignore b/python/examples/dynamic_typing/.gitignore
new file mode 100644
index 0000000..9daeafb
--- /dev/null
+++ b/python/examples/dynamic_typing/.gitignore
@@ -0,0 +1 @@
+test
diff --git a/python/examples/dynamic_typing/Makefile b/python/examples/dynamic_typing/Makefile
new file mode 100644
index 0000000..b32e6cb
--- /dev/null
+++ b/python/examples/dynamic_typing/Makefile
@@ -0,0 +1,8 @@
+test: test.c runtime/dynamic_typing.o
+	dietcc -I $(PWD)/runtime -o $@ $^ --dietc-pass $(PWD)/dietpass
+
+runtime/dynamic_typing.o: runtime/dynamic_typing.c
+	gcc -c -o $@ $^
+
+clean:
+	rm -f runtime/dynamic_typing.o test
diff --git a/python/examples/dynamic_typing/dietc.py b/python/examples/dynamic_typing/dietc.py
new file mode 120000
index 0000000..8cb9097
--- /dev/null
+++ b/python/examples/dynamic_typing/dietc.py
@@ -0,0 +1 @@
+../../dietc.py
\ No newline at end of file
diff --git a/python/examples/dynamic_typing/dietpass b/python/examples/dynamic_typing/dietpass
new file mode 100755
index 0000000..5d15e19
--- /dev/null
+++ b/python/examples/dynamic_typing/dietpass
@@ -0,0 +1,50 @@
+#!/bin/python3
+import os
+import sys
+from dietc import *
+
+def main():
+    prog = Program(open(sys.argv[1], "rb").read())
+    for function in prog.functions:
+        fn_locals = function.locals()
+        start_i = function.code_start()
+        new_body = []
+        for op in function.body:
+            new_body.append(op)
+            # only look for casts to void
+            if " = ( " not in op.line: continue
+            if op.lhs_type(prog) != PointerType(BasicType("void")): continue
+            # if one is found, construct & annotate its type
+            rhs_type = prog.object_types[op[-2]]
+            type_ptr = describe_type(prog, rhs_type, new_body)
+            new_body.append(Instruction(
+                f"annotate_type({op[0]}, {type_ptr});"))
+        function.body = new_body
+    prog.preamble.append("#include <stddef.h>")
+    prog.print()
+
+def describe_type(prog, type_, new_body):
+    name = f"type_{count()}"
+    if isinstance(type_, BasicType):
+        new_body.append(Instruction(
+            f"void *{name} = make_basic(\"{type_.name}\", sizeof({type_.name}));"))
+    elif isinstance(type_, ArrayType):
+        base = describe_type(prog, type_.base, new_body)
+        new_body.append(Instruction(
+            f"void *{name} = make_array({base}, {type_.length});"))
+    elif isinstance(type_, PointerType):
+        base = describe_type(prog, type_.base, new_body)
+        new_body.append(Instruction(
+            f"void *{name} = make_pointer({base});"))
+    elif isinstance(type_, AggregateType):
+        tname = prog.type_to_name[type_]
+        new_body.append(Instruction(
+            f"void *{name} = make_struct(sizeof({tname}));"))
+        for fn, ft in reversed(type_.fields):
+            field = describe_type(prog, ft, new_body)
+            new_body.append(Instruction(
+                f"prepend_member({name}, {field}, \"{fn}\", offsetof({tname}, {fn}));"))
+    else: raise NotImplementedError
+    return name
+
+main()
diff --git a/python/examples/dynamic_typing/runtime/dynamic_typing.c b/python/examples/dynamic_typing/runtime/dynamic_typing.c
new file mode 100644
index 0000000..4e47bc9
--- /dev/null
+++ b/python/examples/dynamic_typing/runtime/dynamic_typing.c
@@ -0,0 +1,72 @@
+#include <stdlib.h>
+#include "dynamic_typing.h"
+
+struct entry {
+    void *start;
+    void *end;
+    struct type *type;
+};
+
+static struct entry *ENTRIES;
+static unsigned long N_ENTRIES;
+
+void annotate_type(void *ptr, struct type *type) {
+    ENTRIES = realloc(ENTRIES, (++N_ENTRIES) * sizeof(ENTRIES[0]));
+    ENTRIES[N_ENTRIES - 1] = (struct entry){
+        .start = ptr,
+        .end = ptr + 1,
+        .type = type,
+    };
+}
+
+struct type *dynamic_typeof(void *ptr) {
+    for (unsigned long i = N_ENTRIES; i --> 0;)
+        if (ENTRIES[i].start <= ptr && ptr < ENTRIES[i].end)
+            return ENTRIES[i].type;
+    return 0;
+}
+
+struct type *make_basic(const char *type, unsigned long size) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_BASIC;
+    t->basic = type;
+    t->size = size;
+    return t;
+}
+
+struct type *make_array(struct type *base, unsigned long len) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_ARRAY;
+    t->base = base;
+    t->length = len;
+    t->size = len * t->base->size;
+    return t;
+}
+
+struct type *make_pointer(struct type *base) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_POINTER;
+    t->base = base;
+    t->size = sizeof(void*);
+    return t;
+}
+
+// function not supported yet
+// for struct & union, the members are initialized by the caller
+struct type *make_struct(unsigned long size) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_STRUCT;
+    return t;
+}
+
+struct type *make_union(unsigned long size) {
+    struct type *t = calloc(1, sizeof(*t));
+    t->kind = TY_UNION;
+    return t;
+}
+void prepend_member(struct type *aggregate, struct type *member, const char *name, unsigned long offset) {
+    member->offset = offset;
+    member->next_member = aggregate->members;
+    member->field_name = name;
+    aggregate->members = member;
+}
diff --git a/python/examples/dynamic_typing/runtime/dynamic_typing.h b/python/examples/dynamic_typing/runtime/dynamic_typing.h
new file mode 100644
index 0000000..4f7b1aa
--- /dev/null
+++ b/python/examples/dynamic_typing/runtime/dynamic_typing.h
@@ -0,0 +1,48 @@
+#ifndef DYNAMIC_TYPING_
+#define DYNAMIC_TYPING_
+
+enum TYPE_KIND {
+    TY_BASIC,
+    TY_ARRAY,
+    TY_POINTER,
+    TY_FUNCTION,
+    TY_STRUCT,
+    TY_UNION,
+};
+
+struct type {
+    enum TYPE_KIND kind;
+    unsigned long size;
+
+    // basic types:
+    const char *basic;
+
+    // array & pointer types:
+    struct type *base;
+    unsigned long length;
+
+    // struct & union types
+    struct type *members;
+    struct type *next_member;
+    unsigned long offset;
+    const char *field_name;
+
+    // function types:
+    struct type *return_type;
+    struct type *params;
+    struct type *next_param;
+};
+
+struct type *dynamic_typeof(void *ptr);
+
+struct type *make_basic(const char *type, unsigned long size);
+struct type *make_array(struct type *base, unsigned long len);
+struct type *make_pointer(struct type *base);
+// function not supported yet
+// for struct & union, the members are initialized by the caller
+struct type *make_struct(unsigned long size);
+struct type *make_union(unsigned long size);
+void prepend_member(struct type *aggregate, struct type *member, const char *name, unsigned long offset);
+void annotate_type(void *ptr, struct type *type);
+
+#endif
diff --git a/python/examples/dynamic_typing/test.c b/python/examples/dynamic_typing/test.c
new file mode 100644
index 0000000..86e2229
--- /dev/null
+++ b/python/examples/dynamic_typing/test.c
@@ -0,0 +1,76 @@
+#include <string.h>
+#include <stdio.h>
+#include <dynamic_typing.h>
+
+void pprint_(void *obj, struct type *type) {
+    switch (type->kind) {
+    case TY_BASIC:
+        switch (type->size) {
+        case sizeof(char):
+            printf("(%s)%lu", type->basic, (unsigned long)*(unsigned char *)obj);
+            break;
+        case sizeof(short):
+            printf("(%s)%lu", type->basic, (unsigned long)*(unsigned short *)obj);
+            break;
+        case sizeof(int):
+            printf("(%s)%lu", type->basic, (unsigned long)*(unsigned int *)obj);
+            break;
+        case sizeof(long):
+            printf("(%s)%lu", type->basic, (unsigned long)*(unsigned long *)obj);
+            break;
+        default:
+            printf("?");
+            break;
+        }
+        break;
+    case TY_ARRAY:
+        printf("{ ");
+        void *ptr = obj;
+        for (unsigned long i = 0; i < type->length; i++) {
+            pprint_(obj, type->base);
+            obj += type->base->size;
+            if (i + 1 < type->length) printf(", ");
+            else printf(" ");
+        }
+        printf("}");
+        break;
+    case TY_POINTER:
+        printf("%p[%ld]", *(void **)obj, type->length);
+        break;
+    case TY_FUNCTION:
+        printf("<function>");
+        break;
+    case TY_STRUCT:
+        printf("{ ");
+        for (struct type *member = type->members; member; member = member->next_member) {
+            printf(".%s = ", member->field_name);
+            pprint_((void*)obj + member->offset, member);
+            if (member->next_member) printf(", ");
+            else printf(" ");
+        }
+        printf("}");
+        break;
+    case TY_UNION:
+        printf("<union>");
+        break;
+    }
+}
+
+void pprint(void *obj) {
+    pprint_(obj, dynamic_typeof(obj)->base);
+    printf("\n");
+}
+
+int main() {
+    struct {
+        char x;
+        int y;
+        int z[3];
+    } foo = {1, 2, {3, 4, 5}};
+    pprint(&foo);
+    struct {
+        char a;
+        int b;
+    } bar = {100, 200};
+    pprint(&bar);
+}
diff --git a/python/examples/zero_init/.gitignore b/python/examples/zero_init/.gitignore
new file mode 100644
index 0000000..b74bd7f
--- /dev/null
+++ b/python/examples/zero_init/.gitignore
@@ -0,0 +1,2 @@
+default
+instrumented
diff --git a/python/examples/zero_init/Makefile b/python/examples/zero_init/Makefile
new file mode 100644
index 0000000..92f29b7
--- /dev/null
+++ b/python/examples/zero_init/Makefile
@@ -0,0 +1,10 @@
+all: default instrumented
+
+default: test.c
+	gcc -O0 $^ -o $@
+
+instrumented: test.c
+	dietcc -O0 $^ -o $@ --dietc-pass $(PWD)/dietpass
+
+clean:
+	rm -f default instrumented
diff --git a/python/examples/zero_init/dietc.py b/python/examples/zero_init/dietc.py
new file mode 120000
index 0000000..8cb9097
--- /dev/null
+++ b/python/examples/zero_init/dietc.py
@@ -0,0 +1 @@
+../../dietc.py
\ No newline at end of file
diff --git a/python/examples/zero_init b/python/examples/zero_init/dietpass
index e2ab92e..1984d81 100755
--- a/python/examples/zero_init
+++ b/python/examples/zero_init/dietpass
@@ -1,7 +1,6 @@
 #!/bin/python3
 import os
 import sys
-sys.path.append(os.path.dirname(os.path.dirname(os.path.realpath(__file__))))
 import dietc
 
 prog = dietc.Program(open(sys.argv[1], "rb").read())
diff --git a/python/examples/test_files/zero_init.c b/python/examples/zero_init/test.c
index 5db109a..5db109a 100644
--- a/python/examples/test_files/zero_init.c
+++ b/python/examples/zero_init/test.c