Write out RTTI

4 files changed, 93 insertions, 6 deletions

diff --git a/src/main/java/org/shedlang/compiler/patio/types/PatioDataValues.java b/src/main/java/org/shedlang/compiler/patio/types/PatioDataValues.java
index 767d1786..1c62e0c8 100644
--- a/src/main/java/org/shedlang/compiler/patio/types/PatioDataValues.java
+++ b/src/main/java/org/shedlang/compiler/patio/types/PatioDataValues.java
@@ -1,6 +1,7 @@
 package org.shedlang.compiler.patio.types;
 
 import org.shedlang.compiler.patio.values.PatioDataPtrValueNull;
+import org.shedlang.compiler.patio.values.PatioIntValue;
 import org.shedlang.compiler.patio.values.PatioIntValueLiteral;
 
 import java.util.List;
@@ -32,7 +33,11 @@ public class PatioDataValues {
     }
 
     public static PatioDataValue int32(int value) {
-        return new PatioDataValueInt32(new PatioIntValueLiteral(value));
+        return int32(new PatioIntValueLiteral(value));
+    }
+
+    public static PatioDataValue int32(PatioIntValue intValue) {
+        return new PatioDataValueInt32(intValue);
     }
 
     public static PatioDataValue struct(List<PatioDataValue> elements) {
diff --git a/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatio.java b/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatio.java
index 3575cdc8..0831fd71 100644
--- a/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatio.java
+++ b/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatio.java
@@ -1,12 +1,16 @@
 package org.shedlang.compiler.shidtopatio;
 
 import org.shedlang.compiler.patio.PatioCompilationUnit;
+import org.shedlang.compiler.patio.PatioDataElementImmutable;
 import org.shedlang.compiler.patio.PatioVisibility;
 import org.shedlang.compiler.patio.instructions.*;
 import org.shedlang.compiler.patio.operands.PatioIntConst;
 import org.shedlang.compiler.patio.operands.PatioLocalRef;
 import org.shedlang.compiler.patio.operands.PatioOperand;
+import org.shedlang.compiler.patio.types.PatioDataLayouts;
+import org.shedlang.compiler.patio.types.PatioDataValues;
 import org.shedlang.compiler.patio.types.PatioTypes;
+import org.shedlang.compiler.patio.values.PatioIntValueByteOffsetOf;
 import org.shedlang.compiler.shid.ShidNamespace;
 import org.shedlang.compiler.shid.instructions.*;
 import org.shedlang.compiler.sources.Source;
@@ -1016,6 +1020,28 @@ public class ShidToPatio {
         Source source,
         ShidToPatioContext context
     ) {
+        var runtimeTypeTags = context.runtimeTypeTags();
+
+        context = context.addCompilationUnitElement(new PatioDataElementImmutable(
+            "shed__rtti",
+            PatioDataValues.array(
+                PatioDataLayouts.struct(List.of(
+                    PatioDataLayouts.INT32,
+                    PatioDataLayouts.INT32
+                )),
+                runtimeTypeTags.stream()
+                    .map(runtimeType -> PatioDataValues.struct(List.of(
+                        PatioDataValues.int32(new PatioIntValueByteOffsetOf(
+                            runtimeType.layout(),
+                            runtimeType.gcChildrenOffset()
+                        )),
+                        PatioDataValues.int32(runtimeType.gcChildrenCount())
+                    )))
+                    .toList()
+            ),
+            source
+        ));
+
         return context;
     }
 
diff --git a/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioContext.java b/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioContext.java
index ae8bc615..dd187acc 100644
--- a/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioContext.java
+++ b/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioContext.java
@@ -19,9 +19,7 @@ import org.shedlang.compiler.types.*;
 import org.shedlang.compiler.util.CheckReturnValue;
 import org.shedlang.compiler.util.P;
 
-import java.util.ArrayList;
-import java.util.List;
-import java.util.Optional;
+import java.util.*;
 import java.util.function.Function;
 
 public record ShidToPatioContext(
@@ -33,7 +31,8 @@ public record ShidToPatioContext(
     public record GlobalContext(
         TypeInfos typeInfos,
         PMap<SimpleStructType, Integer> structTags,
-        PMap<UserDefinedEffect, Integer> effectTags
+        PMap<UserDefinedEffect, Integer> effectTags,
+        OrderedPMap<RuntimeType, Integer> runtimeTypeTags
     ) {
         public static final GlobalContext EMPTY = forTypeInfos(TypeInfos.EMPTY);
 
@@ -41,11 +40,13 @@ public record ShidToPatioContext(
         public static GlobalContext forTypeInfos(TypeInfos typeInfos) {
             var structTags = generateStructTags(typeInfos);
             var effectTags = generateEffectTags(typeInfos);
+            var runtimeTypeTags = P.<RuntimeType, Integer>orderedPMap();
 
             return new GlobalContext(
                 typeInfos,
                 structTags,
-                effectTags
+                effectTags,
+                runtimeTypeTags
             );
         }
 
@@ -113,6 +114,31 @@ public record ShidToPatioContext(
                 return tag;
             }
         }
+
+        @CheckReturnValue
+        private GlobalContext addRuntimeTypeTag(RuntimeType runtimeType, Integer tag) {
+            return new GlobalContext(
+                this.typeInfos,
+                this.structTags,
+                this.effectTags,
+                this.runtimeTypeTags.plus(runtimeType, tag)
+            );
+        }
+
+        @CheckReturnValue
+        public Result<Integer> runtimeTypeTag(RuntimeType runtimeType) {
+            var globalContext = this.runtimeTypeTags.containsKey(runtimeType)
+                ? this
+                : this.addRuntimeTypeTag(runtimeType, this.runtimeTypeTags.size());
+
+            return globalContext.toResult(globalContext.runtimeTypeTags.get(runtimeType));
+        }
+
+        private <T> Result<T> toResult(T value) {
+            return new Result<>(value, this);
+        }
+
+        public record Result<T>(T value, GlobalContext context) {}
     }
 
     public record CompilationUnitContext(
@@ -514,6 +540,16 @@ public record ShidToPatioContext(
     }
 
     @CheckReturnValue
+    public ShidToPatioResult<Integer> runtimeTypeTag(RuntimeType runtimeType) {
+        return withGlobalContextResult(this.globalContext.runtimeTypeTag(runtimeType));
+    }
+
+    @CheckReturnValue
+    public Set<RuntimeType> runtimeTypeTags() {
+        return this.globalContext.runtimeTypeTags.keySet();
+    }
+
+    @CheckReturnValue
     public ShidToPatioResult<String> allocateCompilationUnitElementName(
         ShidToPatioCompilationUnitElementSpace space,
         String name
@@ -840,6 +876,22 @@ public record ShidToPatioContext(
     }
 
     @CheckReturnValue
+    private ShidToPatioContext withGlobalContext(GlobalContext globalContext) {
+        return new ShidToPatioContext(
+            globalContext,
+            this.compilationUnitContext,
+            this.blockStack,
+            this.functionContext
+        );
+    }
+
+
+    @CheckReturnValue
+    private <T> ShidToPatioResult<T> withGlobalContextResult(GlobalContext.Result<T> result) {
+        return withGlobalContext(result.context).toResult(result.value);
+    }
+
+    @CheckReturnValue
     private ShidToPatioContext withCompilationUnitContext(CompilationUnitContext compilationUnitContext) {
         return new ShidToPatioContext(this.globalContext, compilationUnitContext, this.blockStack, this.functionContext);
     }
diff --git a/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioGc.java b/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioGc.java
index 0deafa80..4d62f082 100644
--- a/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioGc.java
+++ b/src/main/java/org/shedlang/compiler/shidtopatio/ShidToPatioGc.java
@@ -148,6 +148,10 @@ public class ShidToPatioGc {
         var childrenOffset = runtimeType.gcChildrenOffset();
         var childrenCount = runtimeType.gcChildrenCount();
 
+        var runtimeTypeTagResult = context.runtimeTypeTag(runtimeType);
+        var runtimeTypeTag = runtimeTypeTagResult.value();
+        context = runtimeTypeTagResult.context();
+
         context = context.ensureCompilationUnitElement(ALLOC);
 
         var size = new PatioIntConst(new PatioIntValueByteSizeOf(layout));