New immutable list implementation

3 files changed, 86 insertions, 101 deletions

diff --git a/src/List.vala b/src/List.vala
index e215db4..7637998 100644
--- a/src/List.vala
+++ b/src/List.vala
@@ -1,31 +1,56 @@
 namespace Eva {
   public class List : Object, Term {
+    private static List _empty;
+    
+    private Term? _head;
     private Term? _tail;
     
-    public Gee.List<Term?> list {get; construct;}
-    public Term? tail {
+    public static List empty {
+      get {
+        if(_empty == null)
+          _empty = new List.create_empty();
+
+        return _empty;
+      }
+    }
+    
+    public Term head {
       get {
+        assert(!is_empty);
+        return _head;
+      }
+    }
+    public Term tail {
+      get {
+        assert(!is_empty);
         return _tail;
       }
-      set {
-        if(value is List) {
-          List l = value as List;
-          
-          list.add_all(l.list);
-          _tail = l._tail;
+    }
+    
+    public bool is_empty {
+      get {
+        if(this == _empty) {
+          assert(_head == null && _tail == null);
+          return true;
         }
         else {
-          _tail = value;
+          assert(_head != null && _tail != null);
+          return false;
         }
       }
     }
     
-    public List() {
-      Gee.List<Term?> list0 = new Gee.LinkedList<Term?>();
-      Object(list: list0);
-      tail = null;
+    public List(Term head0, Term tail0 = empty) {
+      _head = head0;
+      _tail = tail0;
+    }
+    
+    private List.create_empty() {
+      _head = null;
+      _tail = null;
     }
     
+    
     protected bool do_match(Term o, Gee.Map<string, Term> vars, Gee.Map<string, string> aliases) {
       if(o is Var) {
         return o.do_match(this, vars, aliases);
@@ -33,59 +58,19 @@ namespace Eva {
       
       if(o is List) {
         List l = o as List;
+        if(is_empty && l.is_empty)
+          return true;
         
-        if(list.size != l.list.size)
-          return false;
-        if((tail == null) != (l.tail == null))
-          return false;
-        if(tail != null && !tail.do_match(l.tail, vars, aliases))
+        if(is_empty && !l.is_empty)
           return false;
         
-        Gee.Iterator<Term> lt = l.list.iterator();
-        lt.first();
-        foreach(Term t in list) {
-          if(!t.do_match(lt.get(), vars, aliases))
-            return false;
-          
-          lt.next();
-        }
+        if(!is_empty && l.is_empty)
+          return false;
         
-        return true;
+        return (_head.do_match(l.head, vars, aliases) && _tail.do_match(l.tail, vars, aliases));
       }
       else if(o is String) {
-        if(tail != null)
-          return false;
-        
-        string s = "";
-        
-        foreach(Term t in list) {
-          unichar c;
-          
-          if(t is Int) {
-            Int i = t as Int;
-            if(i.value < 0 || i.value > 255)
-              return false;
-            
-            c = (unichar)i.value;
-          }
-          else if(t is UInt) {
-            UInt i = t as UInt;
-            if(i.value > 255)
-              return false;
-            
-            c = (unichar)i.value;
-          }
-          else {
-            return false;
-          }
-          
-          string buf = string.nfill(6, 0);
-          c.to_utf8(buf);
-          
-          s += buf;
-        }
-        
-        return (s == (o as String).value);
+        return do_match(string_to_list((o as String).value), vars, aliases);
       }
       else {
         return false;
@@ -93,38 +78,32 @@ namespace Eva {
     }
     
     public string to_string() {
-      string ret = "[";
-      bool first = true;
+      if(is_empty)
+        return "[]";
       
-      foreach(Term term in list) {
-        if(first) {
-          first = false;
-          ret += term.to_string();
-        }
-        else {
-          ret += "," + term.to_string();
-        }
+      string ret = "[" + _head.to_string();
+      
+      Term rest = _tail;
+      for(rest = _tail; rest is List && rest != List.empty; rest = (rest as List)._tail) {
+        ret += "," + (rest as List)._head.to_string();
       }
       
-      if(tail != null)
-        ret += "|" + tail.to_string();
+      if(rest != List.empty) {
+        ret += "|" + rest.to_string();
+      }
       
       return ret + "]";
     }
     
     public void encode(Erl.Buffer buffer) {
-      if(!list.is_empty) {
-        buffer.encode_list_header(list.size);
-      
-        foreach(Term term in list) {
-          term.encode(buffer);
-        }
-      }
-      
-      if(tail == null)
+      if(is_empty) {
         buffer.encode_empty_list();
-      else
-        tail.encode(buffer);
+      }
+      else {
+        buffer.encode_list_header(1);
+        _head.encode(buffer);
+        _tail.encode(buffer);
+      }
     }
   }
 }
diff --git a/src/Term.vala b/src/Term.vala
index 6b08730..698bfc2 100644
--- a/src/Term.vala
+++ b/src/Term.vala
@@ -75,18 +75,14 @@ namespace Eva {
         
       case Erl.TermType.NIL:
       case Erl.TermType.LIST:
-        List term = new List();
-        
         assert(Erl.decode_list_header(buffer, ref index, out size) == 0);
-        if(size != 0) {
-          for(int i = 0; i < size; ++i) {
-            term.list.add(do_decode(buffer, ref index));
-          }
         
-          term.tail = do_decode(buffer, ref index);
+        if(size == 0) {
+          return List.empty;
+        }
+        else {
+          return decode_list(buffer, ref index, size);
         }
-        
-        return term;
         
       case Erl.TermType.STRING:
         char[] value = new char[size+1];
@@ -119,6 +115,19 @@ namespace Eva {
         assert_not_reached();
       }
     }
+    
+    private static List decode_list(void *buffer, ref int index, int n) {
+      Term head = do_decode(buffer, ref index);
+      Term tail;
+    
+      if(n > 1) {
+        tail = decode_list(buffer, ref index, n-1);
+      }
+      else {
+        tail = do_decode(buffer, ref index);
+      }
+      
+      return new List(head, tail);
+    }
   }
-  
 }
diff --git a/src/Util.vala b/src/Util.vala
index 3666f96..7c704fb 100644
--- a/src/Util.vala
+++ b/src/Util.vala
@@ -32,14 +32,11 @@ namespace Eva {
   }
   
   private List string_to_list(string str) {
-    List ret = new List();
-    
-    for(unowned string rest = str; rest.length > 0; rest = rest.next_char()) {
-      unichar c = rest.get_char();
-      
-      ret.list.add(new UInt(c));
+    if(str.length == 0) {
+      return List.empty;
+    }
+    else {
+      return new List(new UInt(str.get_char()), string_to_list(str.next_char()));
     }
-    
-    return ret;
   }
 }