# HG changeset patch
# User David Anderson <dvander@alliedmods.net>
# Date 1341718109 25200
# Node ID 8e22792a392165e46e7f9e4e8bb3802863bc33dc
# Parent  13bd3a8df3340e28095639055d8499c611b6e0c7
Convert Name and StringPool to a GC-safe symbol table.

diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/AST.h
--- a/jitcraft/AST.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/AST.h	Sat Jul 07 20:28:29 2012 -0700
@@ -20,8 +20,8 @@
 
 #include "PoolAllocator.h"
 #include "Token.h"
-#include "StringPool.h"
 #include "NameBinding.h"
+#include <vector>
 
 namespace jc {
 
@@ -160,10 +160,10 @@
     Variable *variable_;
     Expression *initialization_;
     ExpressionList *postDimensions_;
-    Name *tag_;
+    ScopedRoot<String> tag_;
 
   public:
-    VariableDeclaration(const SourcePosition &pos, Variable *var, Name *tag,
+    VariableDeclaration(const SourcePosition &pos, Variable *var, Handle<String> tag,
                         ExpressionList *postDimensions, Expression *initialization)
       : Statement(pos),
         variable_(var),
@@ -173,7 +173,7 @@
     {
     }
 
-    Name *tag() const {
+    String *tag() const {
         return tag_;
     }
     Kind kind() const {
@@ -196,18 +196,18 @@
 class Parameter : public PoolObject
 {
     Variable *variable_;
-    Name *tag_;
+    ScopedRoot<String> tag_;
     bool reference_;
 
   public:
-    Parameter(Variable *var, Name *tag, bool reference)
+    Parameter(Variable *var, Handle<String> tag, bool reference)
       : variable_(var),
         tag_(tag),
         reference_(reference)
     {
     }
 
-    Name *tag() const {
+    String *tag() const {
         return tag_;
     }
     Variable *variable() const {
@@ -220,11 +220,11 @@
 
 class NameProxy : public Expression
 {
-    Name *name_;
+    ScopedRoot<String> name_;
     BoundName *binding_;
 
   public:
-    NameProxy(const SourcePosition &pos, Name *name, BoundName *binding)
+    NameProxy(const SourcePosition &pos, Handle<String> name, BoundName *binding)
       : Expression(pos),
         name_(name),
         binding_(binding)
@@ -234,7 +234,7 @@
     Kind kind() const {
         return kNameProxy;
     }
-    Name *name() const {
+    String *name() const {
         return name_;
     }
     void accept(AstVisitor *visitor) {
@@ -688,7 +688,7 @@
 
 class EnumStatement : public Statement
 {
-    Name *name_;
+    ScopedRoot<String> name_;
 
   public:
     struct Entry {
@@ -705,7 +705,7 @@
     typedef std::vector<Entry> EntryList;
 
   public:
-    EnumStatement(const SourcePosition &pos, Name *name, EntryList *entries)
+    EnumStatement(const SourcePosition &pos, Handle<String> name, EntryList *entries)
       : Statement(pos),
         name_(name),
         entries_(entries)
@@ -715,7 +715,7 @@
     Kind kind() const {
         return kEnumStatement;
     }
-    Name *name() const {
+    String *name() const {
         return name_;
     }
     EntryList *entries() const {
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/AllocatorPolicies.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jitcraft/AllocatorPolicies.h	Sat Jul 07 20:28:29 2012 -0700
@@ -0,0 +1,45 @@
+/*
+ * Copyright (C) 2012 David Anderson
+ *
+ * This file is part of JITCraft.
+ *
+ * JITCraft 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.
+ * 
+ * Foobar 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
+ * JITCraft. If not, see http://www.gnu.org/licenses/.
+ */
+#ifndef _include_jc_allocators_h_
+#define _include_jc_allocators_h_
+
+#include <stdlib.h>
+
+namespace jc {
+
+class ZoneAllocatorPolicy
+{
+  protected:
+    void reportOutOfMemory();
+    void reportAllocationOverflow();
+
+  public:
+    void free(void *memory) {
+        ::free(memory);
+    }
+    void *malloc(size_t bytes) {
+        void *ptr = ::malloc(bytes);
+        if (!ptr)
+            reportOutOfMemory();
+        return ptr;
+    }
+};
+
+}
+
+#endif // _include_jc_allocators_h_
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/BytecodeCompiler.cpp
--- a/jitcraft/BytecodeCompiler.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/BytecodeCompiler.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -21,6 +21,7 @@
 #include "Modules.h"
 #include "Types.h"
 #include "Array.h"
+#include "Strings.h"
 #include "Zone.h"
 #include "Heap-inl.h"
 
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/FixedArray.h
--- a/jitcraft/FixedArray.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/FixedArray.h	Sat Jul 07 20:28:29 2012 -0700
@@ -1,4 +1,5 @@
-/*
+/* vim: set ts=4 sw=4 tw=99 et
+ *
  * Copyright (C) 2012 David Anderson
  *
  * This file is part of JITCraft.
@@ -62,11 +63,6 @@
 {
     uint32 length_;
 
-  private:
-    Object **vec() {
-        return reinterpret_cast<Object **>(this + 1);
-    }
-
   public:
     static ByteArray *New(Zone *zone, unsigned length, Heap::Tenure tenure = Heap::Tenure_Default);
 
@@ -78,7 +74,7 @@
     }
 
     static size_t SizeFor(unsigned length) {
-        return sizeof(FixedArray) + sizeof(uint8) * length;
+        return Align(sizeof(ByteArray) + sizeof(uint8) * length, kObjectAlignment);
     }
 
     static inline ByteArray *cast(Object *obj) {
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Handles.h
--- a/jitcraft/Handles.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Handles.h	Sat Jul 07 20:28:29 2012 -0700
@@ -112,6 +112,9 @@
     Object * const *address() const {
         return (Object * const *)&thing_;
     }
+    T **ref() {
+        return &thing_;
+    }
     operator T *() {
         return thing_;
     }
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/HashTable.h
--- a/jitcraft/HashTable.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/HashTable.h	Sat Jul 07 20:28:29 2012 -0700
@@ -1,23 +1,28 @@
-// vim: set ts=4 sw=4 tw=99 et:
-//
-//  
-// (C) Copyright 2010-2011 AlliedModders LLC
-//
-// Initial Author: David Anderson
-// Contributors:
-//
-//
-
+/*
+ * Copyright (C) 2012 David Anderson
+ *
+ * This file is part of JITCraft.
+ *
+ * JITCraft 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.
+ * 
+ * Foobar 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
+ * JITCraft. If not, see http://www.gnu.org/licenses/.
+ */
 #ifndef _INCLUDE_KEIMA_HASHTABLE_H_
 #define _INCLUDE_KEIMA_HASHTABLE_H_
 
 #include <new>
 #include <limits.h>
-#include "Object.h"
-#include "vm/Array.h"
-#include "Environment.h"
+#include "Utility.h"
 
-namespace ke {
+namespace jc {
 
 template <typename T>
 class HashTableEntry
@@ -38,9 +43,10 @@
     }
     void setRemoved() {
         hash_ = kRemovedHash;
-        destruct();
+        t_ = T();
     }
     void construct() {
+        hash_ = kFreeHash;
         new (&t_) T();
     }
     void destruct() {
@@ -66,6 +72,8 @@
 template <typename HashPolicy, typename AllocPolicy>
 class HashTable : public AllocPolicy
 {
+    friend class iterator;
+
     typedef typename HashPolicy::Payload Payload;
     typedef HashTableEntry<Payload> Entry;
 
@@ -73,6 +81,7 @@
     uint32 nelements_;
     uint32 ndeleted_;
     Entry *table_;
+    uint32 minCapacity_;
 
   private:
     static const uint32 kMinCapacity = 16;
@@ -88,7 +97,7 @@
     }
 
     Entry *createTable(uint32 capacity) {
-        KE_ASSERT(capacity <= kMaxCapacity);
+        assert(capacity <= kMaxCapacity);
 
         Entry *table = (Entry *)this->malloc(capacity * sizeof(Entry));
         if (!table)
@@ -154,7 +163,7 @@
           : hash_(hash),
             capacity_(capacity)
         {
-            KE_ASSERT(IsPowerOfTwo(capacity_)); 
+            assert(IsPowerOfTwo(capacity_)); 
         }
 
         uint32 entry() const {
@@ -176,11 +185,13 @@
     }
 
     bool shrink() {
+        if ((capacity_ >> 1) < minCapacity_)
+            return true;
         return changeCapacity(capacity_ >> 1);
     }
     
     bool grow() {
-        KE_ASSERT(IsPowerOfTwo(kMaxCapacity));
+        assert(IsPowerOfTwo(kMaxCapacity));
         if (capacity_ >= kMaxCapacity) {
             this->reportAllocationOverflow();
             return false;
@@ -188,16 +199,8 @@
         return changeCapacity(capacity_ << 1);
     }
 
-    bool checkDensity() {
-        if (underloaded())
-            return shrink(); 
-        if (overloaded())
-            return grow();
-        return true;
-    }
-
     bool changeCapacity(uint32 newCapacity) {
-        KE_ASSERT(newCapacity <= kMaxCapacity);
+        assert(newCapacity <= kMaxCapacity);
 
         Entry *newTable = createTable(newCapacity);
         if (!newTable)
@@ -219,7 +222,7 @@
             }
             oldEntry.destruct();
         }
-        this->free(table_);
+        this->free(oldTable);
 
         return true;
     }
@@ -277,7 +280,7 @@
     }
 
     bool add(Insert &i) {
-        KE_ASSERT(!i.found());
+        assert(!i.found());
 
         // If the entry is deleted, just re-use the slot.
         if (i.entry().removed()) {
@@ -310,13 +313,21 @@
         return true;
     }
 
+    void remove(Entry &e) {
+        assert(!e.isLive());
+        e.setRemoved();
+        ndeleted_++;
+        nelements_--;
+    }
+
   public:
     HashTable(AllocPolicy ap)
       : AllocPolicy(ap),
         capacity_(0),
         nelements_(0),
         ndeleted_(0),
-        table_(NULL)
+        table_(NULL),
+        minCapacity_(kMinCapacity)
     {
     }
 
@@ -333,7 +344,9 @@
         else if (capacity > kMaxCapacity)
             capacity = kMaxCapacity;
 
-        KE_ASSERT(IsPowerOfTwo(capacity));
+        minCapacity_ = capacity;
+
+        assert(IsPowerOfTwo(capacity));
         capacity_ = capacity;
 
         table_ = createTable(capacity_);
@@ -359,9 +372,52 @@
         *i = payload;
         return true;
     }
+
+    bool checkDensity() {
+        if (underloaded())
+            return shrink(); 
+        if (overloaded())
+            return grow();
+        return true;
+    }
+
+  public:
+    class iterator
+    {
+        HashTable *table_;
+        Entry *i_;
+        Entry *end_;
+
+      public:
+        iterator(HashTable *table)
+          : table_(table),
+            i_(table->table_),
+            end_(table->table_ + table->capacity_)
+        {
+            while (i_ < end_ && !i_->isLive())
+                i_++;
+        }
+
+        bool empty() const {
+            return i_ == end_;
+        }
+
+        void erase() {
+            assert(!empty());
+            table_->remove(*i_);
+        }
+
+        const Payload &operator *() const {
+            return i_->payload();
+        }
+
+        void next() {
+            while (i_ < end_ && !i_->isLive())
+                i_++;
+        }
+    };
 };
 
 }
 
 #endif // _INCLUDE_KEIMA_HASHTABLE_H_
-
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Heap.cpp
--- a/jitcraft/Heap.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Heap.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -22,6 +22,7 @@
 #include "VirtualObjectVisitor.h"
 #include "ObjectVisitor.h"
 #include "Zone.h"
+#include "StringPool.h"
 
 using namespace jc;
 
@@ -351,6 +352,9 @@
 void
 Heap::sweep()
 {
+    // Before destroying mark bits, sweep weak roots.
+    zone_->symbols()->sweep();
+
     // Note: we don't bother sweeping the LIFO space.
     SweepOldSpace(&mapSpace_);
     SweepOldSpace(&oldSpace_);
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/NameBinding.cpp
--- a/jitcraft/NameBinding.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/NameBinding.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -16,11 +16,12 @@
  * JITCraft. If not, see http://www.gnu.org/licenses/.
  */
 #include "NameBinding.h"
+#include "Strings.h"
 #include "Zone.h"
 
 using namespace jc;
 
-BoundName::BoundName(Scope *scope, Name *name, const SourcePosition &pos)
+BoundName::BoundName(Scope *scope, Handle<String> name, const SourcePosition &pos)
   : scope_(scope),
     name_(name),
     type_(NULL),
@@ -28,12 +29,12 @@
 {
 }
 
-NamedFunction::NamedFunction(Scope *scope, Name *name, const SourcePosition &pos)
+NamedFunction::NamedFunction(Scope *scope, Handle<String> name, const SourcePosition &pos)
   : BoundName(scope, name, pos)
 {
 }
 
-Variable::Variable(Scope *scope, Name *name, const SourcePosition &pos)
+Variable::Variable(Scope *scope, Handle<String> name, const SourcePosition &pos)
   : BoundName(scope, name, pos),
     location_(UNALLOCATED)
 {
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/NameBinding.h
--- a/jitcraft/NameBinding.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/NameBinding.h	Sat Jul 07 20:28:29 2012 -0700
@@ -19,7 +19,6 @@
 #define _include_name_binding_h_
 
 #include "PoolAllocator.h"
-#include "StringPool.h"
 #include "Types.h"
 #include "Scanner.h"
 
@@ -31,11 +30,12 @@
 class Type;
 class NamedEnum;
 class NamedConstant;
+class String;
 
 class BoundName : public PoolObject
 {
     Scope *scope_;
-    Name *name_;
+    ScopedRoot<String> name_;
     ScopedRoot<Type> type_;
     SourcePosition pos_;
 
@@ -47,11 +47,11 @@
       CONSTANT
     };
 
-    BoundName(Scope *scope, Name *name, const SourcePosition &pos);
+    BoundName(Scope *scope, Handle<String> name, const SourcePosition &pos);
 
     virtual Kind kind() const = 0;
 
-    Name *name() const {
+    String *name() const {
         return name_;
     }
     Scope *scope() const {
@@ -85,7 +85,7 @@
     unsigned slot_;
 
   public:
-    NamedFunction(Scope *scope, Name *name, const SourcePosition &pos);
+    NamedFunction(Scope *scope, Handle<String> name, const SourcePosition &pos);
 
     Kind kind() const {
         return FUNCTION;
@@ -101,7 +101,7 @@
 class NamedEnum : public BoundName
 {
   public:
-    NamedEnum(Scope *scope, Name *name, const SourcePosition &pos)
+    NamedEnum(Scope *scope, Handle<String> name, const SourcePosition &pos)
       : BoundName(scope, name, pos)
     {
     }
@@ -117,7 +117,7 @@
     Type *type_;
 
   public:
-    NamedConstant(Scope *scope, Name *name, const SourcePosition &pos)
+    NamedConstant(Scope *scope, Handle<String> name, const SourcePosition &pos)
       : BoundName(scope, name, pos),
         type_(NULL)
     {
@@ -147,7 +147,7 @@
         PARAMETER
     };
 
-    Variable(Scope *scope, Name *name, const SourcePosition &pos);
+    Variable(Scope *scope, Handle<String> name, const SourcePosition &pos);
 
     Kind kind() const {
         return VARIABLE;
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/ObjectVisitor.h
--- a/jitcraft/ObjectVisitor.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/ObjectVisitor.h	Sat Jul 07 20:28:29 2012 -0700
@@ -27,6 +27,7 @@
 #include "Modules.h"
 #include "Functions.h"
 #include "Array.h"
+#include "Strings.h"
 
 namespace jc {
 
@@ -45,6 +46,7 @@
         visitField(obj, Type::offsetOfContained());
         visitField(obj, Type::offsetOfReturnType());
         visitField(obj, Type::offsetOfParameters());
+        visitField(obj, Type::offsetOfTag());
         return sizeof(Type);
     }
 
@@ -86,6 +88,10 @@
         return sizeof(Function);
     }
 
+    size_t iterateString(Object *obj) {
+        return String::SizeFor(String::cast(obj)->length());
+    }
+
     size_t iterateArray(Array *array, ArrayMap *map) {
         if (map->type()->isArray()) {
             unsigned length = array->nelements();
@@ -117,7 +123,7 @@
             return iterateFixedArray(FixedArray::cast(obj));
 
           case MapKind_ByteArray:
-            return Align(iterateByteArray(ByteArray::cast(obj)), kObjectAlignment);
+            return iterateByteArray(ByteArray::cast(obj));
 
           case MapKind_Code:
             return iterateCode(obj);
@@ -131,6 +137,9 @@
           case MapKind_Function:
             return iterateFunction(obj);
 
+          case MapKind_String:
+            return iterateString(obj);
+
           case MapKind_Array:
             return Align(iterateArray(Array::cast(obj), ArrayMap::cast(map)), kObjectAlignment);
 
@@ -155,7 +164,7 @@
         return FixedArray::SizeFor(FixedArray::cast(obj)->length());
 
       case MapKind_ByteArray:
-        return Align(ByteArray::SizeFor(ByteArray::cast(obj)->length()), kObjectAlignment);
+        return ByteArray::SizeFor(ByteArray::cast(obj)->length());
 
       case MapKind_Code:
         return sizeof(Code);
@@ -169,6 +178,9 @@
       case MapKind_Function:
         return sizeof(Function);
 
+      case MapKind_String:
+        return String::SizeFor(String::cast(obj)->length());
+
       case MapKind_Array:
         return Align(Array::SizeOf(Array::cast(obj)), kObjectAlignment);
 
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Objects.h
--- a/jitcraft/Objects.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Objects.h	Sat Jul 07 20:28:29 2012 -0700
@@ -45,6 +45,7 @@
     MapKind_Reference,
     MapKind_Module,
     MapKind_Function,
+    MapKind_String,
     MapKind_FreeRegion,     // Special map denoting freed space.
 
     // Used to represent Arrays. This does not have a canonical map.
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Opcodes.cpp
--- a/jitcraft/Opcodes.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Opcodes.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -16,11 +16,13 @@
  * You should have received a copy of the GNU General Public License along with
  * JITCraft. If not, see http://www.gnu.org/licenses/.
  */
+#include <stdlib.h>
 #include "Opcodes.h"
 #include "Utility.h"
 #include "Code.h"
 #include "Zone.h"
 #include "Array.h"
+#include "Strings.h"
 #include "Heap-inl.h"
 
 using namespace jc;
@@ -186,7 +188,7 @@
           {
             ArrayMap *map = ArrayMap::cast(code->map(READ_UINT32(pc)));
             fprintf(fp, "%s:", map->type()->innermost()->tag()
-                               ? map->type()->innermost()->tag()
+                               ? map->type()->innermost()->tag()->chars()
                                : "_");
             for (; map; map = map->contained()) {
                 Type *type = map->type();
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Parser.cpp
--- a/jitcraft/Parser.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Parser.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -20,14 +20,15 @@
 #include "Parser.h"
 #include "FixedArray.h"
 #include "Heap.h"
+#include "Strings.h"
 #include "Heap-inl.h"
 
 using namespace jc;
 
-Parser::Parser(CompileContext &cc, const char *stream, size_t length)
-  : cc_(cc),
-    pool_(ZONE()->pool()),
-    strings_(pool_),
+Parser::Parser(Zone *zone, CompileContext &cc, const char *stream, size_t length)
+  : zone_(zone),
+    cc_(cc),
+    pool_(zone_->pool()),
     scanner_(cc, stream, length),
     scope_(NULL),
     unbound_(NULL)
@@ -64,7 +65,7 @@
 }
 
 NameProxy *
-Parser::bind(Name *name)
+Parser::bind(Handle<String> name)
 {
     BoundName *bound = scope_->lookup(name);
     NameProxy *proxy = new (pool_) NameProxy(scanner_.begin(), name, bound);
@@ -74,22 +75,22 @@
 }
 
 bool
-Parser::matchName(Name **name, TokenKind kind)
+Parser::matchName(String **name, TokenKind kind)
 {
     assert(kind == TOK_NAME || kind == TOK_LABEL);
     *name = NULL;
     if (!match(kind))
         return false;
-    *name = strings_.add(scanner_.literal());
+    *name = zone_->makeSymbol(scanner_.literal(), scanner_.literal_length());
     return true;
 }
 
-Name *
+String *
 Parser::expectName()
 {
     if (!expect(TOK_NAME))
         return NULL;
-    return strings_.add(scanner_.literal());
+    return zone_->makeSymbol(scanner_.literal(), scanner_.literal_length());
 }
 
 void
@@ -105,8 +106,9 @@
     switch (kind) {
       case TOK_NAME:
       {
-        scanner_.scan();
-        Name *name = strings_.add(scanner_.literal());
+        Local<String> name(zone_, expectName());
+        if (!name)
+            return NULL;
         return bind(name);
       }
 
@@ -127,10 +129,10 @@
       case TOK_STRING_LITERAL:
       {
         scanner_.scan();
-        Local<ByteArray> array(ZONE(), ByteArray::New(ZONE(), scanner_.literal_length()));
+        Local<ByteArray> array(zone_, ByteArray::New(zone_, scanner_.literal_length() + 1));
         if (!array)
             return NULL;
-        memcpy(array->raw(), scanner_.literal(), scanner_.literal_length());
+        memcpy(array->raw(), scanner_.literal(), scanner_.literal_length() + 1);
         return new (pool_) StringLiteral(scanner_.begin(), array);
       }
 
@@ -562,11 +564,11 @@
     if (!expect(TOK_NEW))
         return NULL;
 
-    Name *tag;
-    if (matchName(&tag, TOK_LABEL) && !tag)
+    Local<String> tag(zone_);
+    if (matchName(tag.ref(), TOK_LABEL) && !tag)
         return NULL;
 
-    Name *name = expectName();
+    Local<String> name(zone_, expectName());
     if (!name)
         return NULL;
 
@@ -785,9 +787,9 @@
 
     SourcePosition pos = scanner_.begin();
 
-    Name *name = NULL;
-    if (match(TOK_NAME)) {
-        if ((name = strings_.add(scanner_.literal())) == NULL)
+    Local<String> name(zone_);
+    if (matchName(name.ref())) {
+        if (!name)
             return NULL;
 
         if (BoundName *other = scope_->localLookup(name)) {
@@ -808,7 +810,7 @@
         if (scanner_.peek() == TOK_RBRACE)
             break;
 
-        Name *name = expectName();
+        Local<String> name(zone_, expectName());
         if (!name)
             return NULL;
 
@@ -838,7 +840,7 @@
 Statement *
 Parser::function()
 {
-    Name *name = expectName();
+    Local<String> name(zone_, expectName());
     if (!name)
         return NULL;
 
@@ -867,7 +869,7 @@
         while (true) {
             bool ref = match(TOK_AMPERSAND);
 
-            Name *name = expectName();
+            Local<String> name(zone_, expectName());
             if (!name)
                 return NULL;
 
@@ -879,7 +881,8 @@
             if (!arg)
                 return NULL;
 
-            Parameter *parameter = new (pool_) Parameter(arg, NULL, ref);
+            Local<String> tag(zone_);
+            Parameter *parameter = new (pool_) Parameter(arg, tag, ref);
             parameters->push_back(parameter);
 
             if (!match(TOK_COMMA))
@@ -966,7 +969,7 @@
 
     void visit(NameProxy *name) {
         prefix();
-        fprintf(fp_, "[ NameProxy (%s)%s\n", name->name(),
+        fprintf(fp_, "[ NameProxy (%s)%s\n", name->name()->chars(),
                 (name->binding() ? "" : " unbound"));
     }
     void visit(CallExpression *node) {
@@ -980,7 +983,7 @@
     }
     void visit(FunctionStatement *node) {
         prefix();
-        fprintf(fp_, "[ FunctionStatement (%s)\n", node->fun()->name());
+        fprintf(fp_, "[ FunctionStatement (%s)\n", node->fun()->name()->chars());
         indent();
         node->body()->accept(this);
         unindent();
@@ -1038,7 +1041,7 @@
     }
     void visit(VariableDeclaration *node) {
         prefix();
-        fprintf(fp_, "[ VariableDeclaration (%s)\n", node->variable()->name());
+        fprintf(fp_, "[ VariableDeclaration (%s)\n", node->variable()->name()->chars());
         indent();
         if (node->initialization())
             node->initialization()->accept(this);
@@ -1071,11 +1074,11 @@
     }
     void visit(EnumStatement *node) {
         prefix();
-        fprintf(fp_, "[ EnumStatement (%s)\n", node->name() ? node->name() : "<anonymous>");
+        fprintf(fp_, "[ EnumStatement (%s)\n", node->name() ? node->name()->chars() : "<anonymous>");
         indent();
         for (size_t i = 0; i < node->entries()->size(); i++) {
             prefix();
-            fprintf(fp_, "%s =\n", node->entries()->at(i).name->name());
+            fprintf(fp_, "%s =\n", node->entries()->at(i).name->name()->chars());
             if (node->entries()->at(i).expr) {
                 indent();
                 node->entries()->at(i).expr->accept(this);
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Parser.h
--- a/jitcraft/Parser.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Parser.h	Sat Jul 07 20:28:29 2012 -0700
@@ -21,17 +21,17 @@
 #include <stdio.h>
 #include <vector>
 #include "AST.h"
-#include "StringPool.h"
 #include "Scanner.h"
 #include "Scopes.h"
+#include "Strings.h"
 
 namespace jc {
 
 class Parser
 {
+    Zone *zone_;
     CompileContext &cc_;
     PoolAllocator &pool_;
-    StringPool strings_;
     Scanner scanner_;
     Scope *scope_;
     std::vector<NameProxy *> *unbound_;
@@ -44,9 +44,9 @@
     Scope *enterScope(Scope::Kind kind);
 
     VariableDeclaration *variableDeclaration();
-    bool matchName(Name **name, TokenKind kind = TOK_NAME);
-    Name *expectName();
-    NameProxy *bind(Name *name);
+    bool matchName(String **name, TokenKind kind = TOK_NAME);
+    String *expectName();
+    NameProxy *bind(Handle<String> name);
     Expression *primitive();
     Expression *call(Expression *callee);
     Expression *index(Expression *left);
@@ -77,7 +77,7 @@
     Statement *returnStatement();
 
   public:
-    Parser(CompileContext &cc, const char *stream, size_t length);
+    Parser(Zone *zone, CompileContext &cc, const char *stream, size_t length);
 
     ParseTree *parse();
 };
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Scanner.h
--- a/jitcraft/Scanner.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Scanner.h	Sat Jul 07 20:28:29 2012 -0700
@@ -72,7 +72,7 @@
         return literal_.c_str();
     }
     size_t literal_length() const {
-        return literal_.size() + 1;
+        return literal_.size();
     }
 };
 
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Scopes.cpp
--- a/jitcraft/Scopes.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Scopes.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -20,6 +20,7 @@
 #include "Zone.h"
 #include "Types.h"
 #include "TypeManager.h"
+#include "Strings.h"
 
 using namespace jc;
 
@@ -65,7 +66,7 @@
 }
 
 BoundName *
-Scope::localLookup(Name *name)
+Scope::localLookup(Handle<String> name)
 {
     for (size_t i = 0; i < names_.size(); i++) {
         if (names_[i]->name() == name)
@@ -75,7 +76,7 @@
 }
 
 BoundName *
-Scope::lookup(Name *name)
+Scope::lookup(Handle<String> name)
 {
     for (Scope *scope = this; scope; scope = scope->enclosing()) {
         if (BoundName *bound = scope->localLookup(name))
@@ -85,7 +86,7 @@
 }
 
 Variable *
-Scope::declareVariable(Name *name, const SourcePosition &pos)
+Scope::declareVariable(Handle<String> name, const SourcePosition &pos)
 {
     assert(!localLookup(name));
     
@@ -95,7 +96,7 @@
 }
 
 Variable *
-Scope::declareArgument(Name *name, const SourcePosition &pos)
+Scope::declareArgument(Handle<String> name, const SourcePosition &pos)
 {
     assert(kind() == FUNCTION);
     Variable *var = declareVariable(name, pos);
@@ -105,7 +106,7 @@
 }
 
 NamedFunction *
-Scope::declareFunction(Name *name, const SourcePosition &pos)
+Scope::declareFunction(Handle<String> name, const SourcePosition &pos)
 {
     assert(!localLookup(name));
     assert(kind() == GLOBAL);
@@ -116,7 +117,7 @@
 }
 
 NamedEnum *
-Scope::declareEnum(Name *name, const SourcePosition &pos)
+Scope::declareEnum(Handle<String> name, const SourcePosition &pos)
 {
     NamedEnum *e = new (pool_) NamedEnum(this, name, pos);
     names_.push_back(e);
@@ -124,7 +125,7 @@
 }
 
 NamedConstant *
-Scope::declareConstant(Name *name, const SourcePosition &pos)
+Scope::declareConstant(Handle<String> name, const SourcePosition &pos)
 {
     NamedConstant *constant = new (pool_) NamedConstant(this, name, pos);
     names_.push_back(constant);
@@ -190,15 +191,17 @@
 bool
 Scope::Bind(ParseTree *tree)
 {
+    Local<String> name(ZONE());
     for (size_t i = 0; i < tree->unbound()->size(); i++) {
         NameProxy *proxy = tree->unbound()->at(i);
-        BoundName *name = tree->scope()->lookup(proxy->name());
-        if (!name) {
+        name = proxy->name();
+        BoundName *binding = tree->scope()->lookup(name);
+        if (!binding) {
             assert(false);
             return false;
         }
 
-        proxy->bind(name);
+        proxy->bind(binding);
     }
     return true;
 }
@@ -227,6 +230,7 @@
     if (!type)
         return;
 
-    lifoSlot_ = new (pool_) Variable(this, NULL, SourcePosition());
+    Local<String> name(ZONE());
+    lifoSlot_ = new (pool_) Variable(this, name, SourcePosition());
     lifoSlot_->setType(type);
 }
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Scopes.h
--- a/jitcraft/Scopes.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Scopes.h	Sat Jul 07 20:28:29 2012 -0700
@@ -79,14 +79,14 @@
     void setUsesLifoHeap();
 
     Scope *unlinkIfEmpty();
-    BoundName *localLookup(Name *name);
-    BoundName *lookup(Name *name);
+    BoundName *localLookup(Handle<String> name);
+    BoundName *lookup(Handle<String> name);
 
-    NamedFunction *declareFunction(Name *name, const SourcePosition &pos);
-    Variable *declareVariable(Name *name, const SourcePosition &pos);
-    Variable *declareArgument(Name *name, const SourcePosition &pos);
-    NamedEnum *declareEnum(Name *name, const SourcePosition &pos);
-    NamedConstant *declareConstant(Name *name, const SourcePosition &pos);
+    NamedFunction *declareFunction(Handle<String> name, const SourcePosition &pos);
+    Variable *declareVariable(Handle<String> name, const SourcePosition &pos);
+    Variable *declareArgument(Handle<String> name, const SourcePosition &pos);
+    NamedEnum *declareEnum(Handle<String> name, const SourcePosition &pos);
+    NamedConstant *declareConstant(Handle<String> name, const SourcePosition &pos);
 
     void allocate(Variable *var);
     void allocate();
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/SemanticAnalysis.cpp
--- a/jitcraft/SemanticAnalysis.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/SemanticAnalysis.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -22,6 +22,7 @@
 #include "TypeManager.h"
 #include "Scopes.h"
 #include "Heap-inl.h"
+#include "Strings.h"
 
 using namespace jc;
 
@@ -158,6 +159,7 @@
     return expression->type();
 }
 
+// :TODO: this leaks an interior pointer.
 static inline const char *
 GetTypeName(Type *type)
 {
@@ -168,7 +170,7 @@
     if (type->isReference())
         type = type->contained();
     if (type->tag())
-        return type->tag();
+        return type->tag()->chars();
     return "int";
 }
 
@@ -388,7 +390,8 @@
 void
 SemanticAnalysis::visit(VariableDeclaration *node)
 {
-    Local<Type> type(zone_, zone_->types()->getPrimitiveForTag(node->tag()));
+    Local<String> tag(zone_, node->tag());
+    Local<Type> type(zone_, zone_->types()->getPrimitiveForTag(tag));
     if (!type)
         return;
 
@@ -528,7 +531,8 @@
     for (size_t i = 0; i < node->parameters()->size(); i++) {
         Parameter *parameter = node->parameters()->at(i);
         
-        Local<Type> type(zone_, zone_->types()->getPrimitiveForTag(parameter->tag()));
+        Local<String> tag(zone_, parameter->tag());
+        Local<Type> type(zone_, zone_->types()->getPrimitiveForTag(tag));
         if (!type)
             return false;
 
@@ -617,8 +621,9 @@
     }
 
     if (given->primitive() != actual->primitive()) {
-        const char *givenTag = given->tag() ? given->tag() : "_";
-        const char *actualTag = given->tag() ? given->tag() : "_";
+        // :TODO: leaks an interior pointer.
+        const char *givenTag = given->tag() ? given->tag()->chars() : "_";
+        const char *actualTag = given->tag() ? given->tag()->chars() : "_";
         cc_.reportError(node->pos(), Message_TagMismatch, actualTag, givenTag);
         return false;
     }
@@ -652,8 +657,9 @@
     }
     
     if (given->primitive() != actual->primitive()) {
-        const char *givenTag = given->tag() ? given->tag() : "_";
-        const char *actualTag = given->tag() ? given->tag() : "_";
+        // :TODO: leaks an interior pointer
+        const char *givenTag = given->tag() ? given->tag()->chars() : "_";
+        const char *actualTag = given->tag() ? given->tag()->chars() : "_";
         cc_.reportError(node->pos(), Message_TagMismatch, actualTag, givenTag);
         return false;
     }
@@ -746,11 +752,11 @@
 SemanticAnalysis::visit(EnumStatement *node)
 {
     // Forbid the blessed types.
-    Name *tag = node->name();
-    if (!strcmp(tag, "Float") ||
-        !strcmp(tag, "String") ||
-        !strcmp(tag, "any") ||
-        !strcmp(tag, "bool"))
+    Local<String> tag(zone_, node->name());
+    if (!strcmp(tag->chars(), "Float") ||
+        !strcmp(tag->chars(), "String") ||
+        !strcmp(tag->chars(), "any") ||
+        !strcmp(tag->chars(), "bool"))
     {
         cc_.reportError(node->pos(), Message_InvalidEnumName);
         return;
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/StringPool.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jitcraft/StringPool.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -0,0 +1,69 @@
+/*
+ * Copyright (C) 2012 David Anderson
+ *
+ * This file is part of JITCraft.
+ *
+ * JITCraft 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.
+ * 
+ * Foobar 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
+ * JITCraft. If not, see http://www.gnu.org/licenses/.
+ */
+#include "StringPool.h"
+#include "Strings.h"
+#include "Spaces.h"
+
+using namespace jc;
+
+StringPool::StringPool(Zone *zone)
+  : zone_(zone),
+    set_(ZoneAllocatorPolicy())
+{
+}
+
+StringPool::~StringPool()
+{
+}
+
+bool
+StringPool::initialize()
+{
+    if (!set_.init(32))
+        return false;
+    return true;
+}
+
+String *
+StringPool::add(const char *str, size_t length)
+{
+    StringSet::Insert i = set_.findForAdd(CharsAndLength(str, length));
+    if (i.found())
+        return *i;
+
+    String *obj = String::New(zone_, str, length, Heap::Tenure_Old);
+    if (!obj)
+        return NULL;
+
+    set_.add(i, obj);
+    return obj;
+}
+
+void
+StringPool::sweep()
+{
+    for (StringSet::iterator i(&set_); !i.empty(); i.next()) {
+        String *obj = *i;
+        MarkBit bits = HeapChunk::GetMarkBit(obj);
+        if (HeapChunk::IsWhite(bits))
+            i.erase();
+        else
+            assert(HeapChunk::IsBlack(bits));
+    }
+    set_.checkDensity();
+}
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/StringPool.h
--- a/jitcraft/StringPool.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/StringPool.h	Sat Jul 07 20:28:29 2012 -0700
@@ -18,37 +18,66 @@
 #ifndef _include_jitcraft_string_pool_h_
 #define _include_jitcraft_string_pool_h_
 
-#include <vector>
-#include <string.h>
-#include "PoolAllocator.h"
+#include "AllocatorPolicies.h"
+#include "HashTable.h"
+#include "Strings.h"
 
 namespace jc {
 
-typedef const char Name;
+class Zone;
+class String;
 
-// Guarantee that strings with the same contents will map to one pointer. The
-// strings are pool allocated, and search is linear for simplicity.
+// Guarantee that strings with the same contents will map to one pointer. 
 class StringPool
 {
-    PoolAllocator &pool_;
-    std::vector<Name *> strings_;
+    class CharsAndLength {
+        const char *str_;
+        size_t length_;
+
+      public:
+        CharsAndLength(const char *str, size_t length)
+          : str_(str),
+            length_(length)
+        {
+        }
+
+        const char *str() const {
+            return str_;
+        }
+        size_t length() const {
+            return length_;
+        }
+    };
+
+    struct Policy
+    {
+        typedef String * Payload;
+
+        static uint32 hash(const CharsAndLength &key) {
+            return HashCharSequence(key.str(), key.length());
+        }
+        
+        static bool matches(const CharsAndLength &key, String *string) {
+            if (string->length() != key.length())
+                return false;
+            return memcmp(string->chars(), key.str(), key.length() * sizeof(char)) == 0;
+        }
+    };
+
+    typedef HashTable<Policy, ZoneAllocatorPolicy> StringSet;
 
   public:
-    StringPool(PoolAllocator &pool)
-      : pool_(pool)
-    {
-    }
+    StringPool(Zone *zone);
+    ~StringPool();
+    bool initialize();
 
-    Name *add(const char *string) {
-        for (size_t i = 0; i < strings_.size(); i++) {
-            if (strcmp(strings_[i], string) == 0)
-                return strings_[i];
-        }
-        char *name = (char *)pool_.allocate(strlen(string) + 1);
-        strcpy(name, string);
-        strings_.push_back(name);
-        return name;
-    }
+  public:
+    String *add(const char *str, size_t len);
+    void sweep();
+
+  private:
+    Zone *zone_;
+    StringSet set_;
 };
 
 }
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Strings.cpp
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jitcraft/Strings.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -0,0 +1,43 @@
+/* vim: set ts=4 sw=4 tw=99 et:
+ *
+ * Copyright (C) 2012 David Anderson
+ *
+ * This file is part of JITCraft.
+ *
+ * JITCraft 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.
+ * 
+ * Foobar 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
+ * JITCraft. If not, see http://www.gnu.org/licenses/.
+ */
+#include "Strings.h"
+#include "Zone.h"
+#include "Heap-inl.h"
+
+using namespace jc;
+
+String *
+String::New(Zone *zone, const char *from, Heap::Tenure tenure)
+{
+    return New(zone, from, strlen(from), tenure);
+}
+
+String *
+String::New(Zone *zone, const char *from, size_t length, Heap::Tenure tenure)
+{
+    size_t bytes = SizeFor(length);
+    Local<String> string(zone, String::cast(zone->allocate(MapKind_String, bytes, tenure)));
+    if (!string)
+        return NULL;
+
+    string->length_ = length;
+    memcpy(string->chars(), from, length + 1);
+
+    return string;
+}
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Strings.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/jitcraft/Strings.h	Sat Jul 07 20:28:29 2012 -0700
@@ -0,0 +1,54 @@
+/* vim: set ts=4 sw=4 tw=99 et:
+ *
+ * Copyright (C) 2012 David Anderson
+ *
+ * This file is part of JITCraft.
+ *
+ * JITCraft 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.
+ * 
+ * Foobar 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
+ * JITCraft. If not, see http://www.gnu.org/licenses/.
+ */
+#ifndef _include_jitcraft_string_h_
+#define _include_jitcraft_string_h_
+
+#include "Heap.h"
+
+namespace jc {
+
+// A fixed-length string containing UTF-8 characters.
+class String : public Object
+{
+    uint32 length_;
+    
+  public:
+    static String *New(Zone *zone, const char *from, Heap::Tenure tenure = Heap::Tenure_Default);
+    static String *New(Zone *zone, const char *from, size_t length, Heap::Tenure tenure = Heap::Tenure_Default);
+
+    unsigned length() {
+        return length_;
+    }
+    char *chars() {
+        return reinterpret_cast<char *>(this + 1);
+    }
+
+    static size_t SizeFor(unsigned length) {
+        return Align(sizeof(String) + sizeof(char) * (length + 1), kObjectAlignment);
+    }
+
+    static inline String *cast(Object *obj) {
+        assert(!obj || obj->is(MapKind_String));
+        return reinterpret_cast<String *>(obj);
+    }
+};
+
+}
+
+#endif // _include_jitcraft_string_h_
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/TypeManager.cpp
--- a/jitcraft/TypeManager.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/TypeManager.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -19,6 +19,7 @@
 #include "Types.h"
 #include "TypeManager.h"
 #include "Zone.h"
+#include "Strings.h"
 
 using namespace jc;
 
@@ -31,13 +32,23 @@
 bool
 TypeManager::initialize()
 {
-    if ((primitiveTypes_[PrimitiveType_Int32] = Type::NewPrimitive(zone_, NULL)) == NULL)
+    Local<String> floatTag(zone_, zone_->makeSymbol("Float"));
+    if (!floatTag)
+        return false;
+
+    Local<String> stringTag(zone_, zone_->makeSymbol("String"));
+    if (!stringTag)
         return false;
-    if ((primitiveTypes_[PrimitiveType_Float] = Type::NewPrimitive(zone_, "Float")) == NULL)
+
+    Local<String> nullTag(zone_);
+
+    if ((primitiveTypes_[PrimitiveType_Int32] = Type::NewPrimitive(zone_, nullTag)) == NULL)
+        return false;
+    if ((primitiveTypes_[PrimitiveType_Float] = Type::NewPrimitive(zone_, floatTag)) == NULL)
         return false;
     if ((primitiveTypes_[PrimitiveType_Native] = Type::NewPrimitive(zone_, PrimitiveType_Native)) == NULL)
         return false;
-    if ((primitiveTypes_[PrimitiveType_Char] = Type::NewPrimitive(zone_, "String")) == NULL)
+    if ((primitiveTypes_[PrimitiveType_Char] = Type::NewPrimitive(zone_, stringTag)) == NULL)
         return false;
 
     Local<Type> type(zone_);
@@ -51,13 +62,13 @@
 }
 
 Type *
-TypeManager::getPrimitiveForTag(Name *tag)
+TypeManager::getPrimitiveForTag(Handle<String> tag)
 {
-    if (tag == NULL)
+    if (!tag)
         return getPrimitive(PrimitiveType_Int32);
-    if (strcmp(tag, "Float") == 0)
+    if (strcmp(tag->chars(), "Float") == 0)
         return getPrimitive(PrimitiveType_Float);
-    if (strcmp(tag, "String") == 0)
+    if (strcmp(tag->chars(), "String") == 0)
         return getPrimitive(PrimitiveType_Char);
     return NULL;
 }
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/TypeManager.h
--- a/jitcraft/TypeManager.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/TypeManager.h	Sat Jul 07 20:28:29 2012 -0700
@@ -24,6 +24,8 @@
 
 namespace jc {
 
+class String;
+
 class TypeManager
 {
     Zone *zone_;
@@ -37,7 +39,7 @@
 
     bool initialize();
 
-    Type *getPrimitiveForTag(Name *tag);
+    Type *getPrimitiveForTag(Handle<String>);
     Type *getPrimitive(PrimitiveType type) {
         return primitiveTypes_[type];
     }
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Types.cpp
--- a/jitcraft/Types.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Types.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -17,12 +17,13 @@
  */
 #include "Types.h"
 #include "Zone.h"
+#include "Strings.h"
 #include "Heap-inl.h"
 
 using namespace jc;
 
 Type *
-Type::NewPrimitive(Zone *zone, Name *tag)
+Type::NewPrimitive(Zone *zone, Handle<String> tag)
 {
     Local<Type> type(zone, Type::cast(zone->allocate(MapKind_Type, sizeof(Type), Heap::Tenure_Old)));
     if (!type)
@@ -34,9 +35,9 @@
     type->returnType_ = NULL;
     type->parameters_ = NULL;
 
-    if (tag && strcmp(tag, "Float") == 0)
+    if (tag && strcmp(tag->chars(), "Float") == 0)
         type->primitive_ = PrimitiveType_Float;
-    else if (tag && strcmp(tag, "String") == 0)
+    else if (tag && strcmp(tag->chars(), "String") == 0)
         type->primitive_ = PrimitiveType_Char;
     else
         type->primitive_ = PrimitiveType_Int32;
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Types.h
--- a/jitcraft/Types.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Types.h	Sat Jul 07 20:28:29 2012 -0700
@@ -19,13 +19,14 @@
 #ifndef _include_jc_types_h_
 #define _include_jc_types_h_
 
-#include "StringPool.h"
 #include "Heap.h"
 #include "Barriers.h"
 #include "FixedArray.h"
 
 namespace jc {
 
+class String;
+
 enum PrimitiveType
 {
     PrimitiveType_Char,         // signed, 8-bit character
@@ -53,7 +54,7 @@
     static const int UNKNOWN_SIZE = -1;
     static const size_t MAX_UNSAFE_ARRAY_DEPTH = 5;
     
-    static Type *NewPrimitive(Zone *zone, Name *tag);
+    static Type *NewPrimitive(Zone *zone, Handle<String> tag);
     static Type *NewPrimitive(Zone *zone, PrimitiveType type);
     static Type *NewArray(Zone *zone, Handle<Type> contained, int elements, bool isConst);
     static Type *NewReference(Zone *zone, Handle<Type> contained);
@@ -92,7 +93,7 @@
         assert(isArray());
         return levels_;
     }
-    Name *tag() {
+    String *tag() {
         assert(isPrimitive());
         return tag_;
     }
@@ -143,12 +144,15 @@
     static inline size_t offsetOfParameters() {
         return offsetof(Type, parameters_);
     }
+    static inline size_t offsetOfTag() {
+        return offsetof(Type, tag_);
+    }
     // End GC Descriptor.
 
   private:
     Kind kind_;
     PrimitiveType primitive_;
-    Name *tag_;
+    Barriered<String> tag_;
 
     // Arrays only.
     int32 elements_;
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Utility.h
--- a/jitcraft/Utility.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Utility.h	Sat Jul 07 20:28:29 2012 -0700
@@ -70,6 +70,45 @@
     }
 };
 
+// Bob Jenkin's one-at-a-time hash function[1].
+//
+// [1] http://burtleburtle.net/bob/hash/doobs.html
+class CharacterStreamHasher
+{
+    uint32 hash;
+
+  public:
+    CharacterStreamHasher()
+      : hash(0)
+    { }
+
+    void add(char c) {
+        hash += c;
+        hash += (hash << 10);
+        hash ^= (hash >> 6);
+    }
+
+    void add(const char *s, size_t length) {
+        for (size_t i = 0; i < length; i++)
+            add(s[i]);
+    }
+
+    uint32 result() {
+        hash += (hash << 3);
+        hash ^= (hash >> 11);
+        hash += (hash << 15);
+        return hash;
+    }
+};
+
+static inline uint32
+HashCharSequence(const char *s, size_t length)
+{
+    CharacterStreamHasher hasher;
+    hasher.add(s, length);
+    return hasher.result();
+}
+
 static inline size_t
 Log2(size_t number)
 {
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Zone.cpp
--- a/jitcraft/Zone.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Zone.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -17,7 +17,9 @@
  * JITCraft. If not, see http://www.gnu.org/licenses/.
  */
 #include "Zone.h"
+#include "StringPool.h"
 #include "TypeManager.h"
+#include "AllocatorPolicies.h"
 
 using namespace jc;
 
@@ -30,6 +32,12 @@
 {
 }
 
+Zone::~Zone()
+{
+    delete symbols_;
+    delete types_;
+}
+
 bool
 Zone::initialize()
 {
@@ -38,6 +46,10 @@
     if (!heap_.initialize())
         return false;
 
+    symbols_ = new StringPool(this);
+    if (!symbols_ || !symbols_->initialize())
+        return false;
+
     maps_[MapKind_Meta] = heap_.metaMap();
     if ((maps_[MapKind_Type] = allocateMap(MapKind_Type, sizeof(Map))) == NULL)
         return false;
@@ -55,6 +67,8 @@
         return false;
     if ((maps_[MapKind_Function] = allocateMap(MapKind_Function, sizeof(Map))) == NULL)
         return false;
+    if ((maps_[MapKind_String] = allocateMap(MapKind_String, sizeof(Map))) == NULL)
+        return false;
     if ((maps_[MapKind_FreeRegion] = allocateMap(MapKind_FreeRegion, sizeof(Map))) == NULL)
         return false;
 
@@ -94,3 +108,28 @@
     stack_.accept(visitor);
 }
 
+String *
+Zone::makeSymbol(const char *str, size_t length)
+{
+    return symbols_->add(str, length);
+}
+
+String *
+Zone::makeSymbol(const char *str)
+{
+    return makeSymbol(str, strlen(str));
+}
+
+void
+ZoneAllocatorPolicy::reportOutOfMemory()
+{
+    // :TODO: report
+    assert(false);
+}
+
+void
+ZoneAllocatorPolicy::reportAllocationOverflow()
+{
+    // :TODO: report
+    assert(false);
+}
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/Zone.h
--- a/jitcraft/Zone.h	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/Zone.h	Sat Jul 07 20:28:29 2012 -0700
@@ -30,6 +30,8 @@
 namespace jc {
 
 class TypeManager;
+class String;
+class StringPool;
 
 class Zone
 {
@@ -41,6 +43,7 @@
     Unbarriered<Map> maps_[MapKinds_Total];
 
     TypeManager *types_;
+    StringPool *symbols_;
 
     // Root list.
     Local<Object> *lastLocalRoot_;
@@ -48,6 +51,7 @@
 
   public:
     Zone();
+    ~Zone();
     bool initialize();
 
     PoolAllocator &pool() {
@@ -84,6 +88,12 @@
     RootScopeManager &rootScopes() {
         return rootScopes_;
     }
+    StringPool *symbols() {
+        return symbols_;
+    }
+
+    String *makeSymbol(const char *string, size_t length);
+    String *makeSymbol(const char *string);
 
     void accept(VirtualObjectVisitor *visitor);
 };
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/jitcraft.vcxproj
--- a/jitcraft/jitcraft.vcxproj	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/jitcraft.vcxproj	Sat Jul 07 20:28:29 2012 -0700
@@ -98,11 +98,14 @@
     <ClCompile Include="SemanticAnalysis.cpp" />
     <ClCompile Include="Spaces.cpp" />
     <ClCompile Include="Stack.cpp" />
+    <ClCompile Include="StringPool.cpp" />
+    <ClCompile Include="Strings.cpp" />
     <ClCompile Include="TypeManager.cpp" />
     <ClCompile Include="Types.cpp" />
     <ClCompile Include="Zone.cpp" />
   </ItemGroup>
   <ItemGroup>
+    <ClInclude Include="AllocatorPolicies.h" />
     <ClInclude Include="Array.h" />
     <ClInclude Include="AST.h" />
     <ClInclude Include="Barriers.h" />
@@ -134,6 +137,7 @@
     <ClInclude Include="Spaces-inl.h" />
     <ClInclude Include="Spaces.h" />
     <ClInclude Include="Stack.h" />
+    <ClInclude Include="Strings.h" />
     <ClInclude Include="StringPool.h" />
     <ClInclude Include="TypeManager.h" />
     <ClInclude Include="Types.h" />
diff -r 13bd3a8df334 -r 8e22792a3921 jitcraft/main.cpp
--- a/jitcraft/main.cpp	Sat Jul 07 17:11:31 2012 -0700
+++ b/jitcraft/main.cpp	Sat Jul 07 20:28:29 2012 -0700
@@ -62,7 +62,7 @@
     RootScope roots(ZONE());
     CompileContext cc(ZONE());
 
-    Parser parser(cc, stream, length);
+    Parser parser(ZONE(), cc, stream, length);
     ParseTree *tree = parser.parse();
     if (!tree)
         return false;