* Merged the `fast-eval' branch.

7 files changed, 57 insertions, 650 deletions

diff --git a/src/libutil/Makefile.am b/src/libutil/Makefile.am
index bd0996543..aa862208c 100644
--- a/src/libutil/Makefile.am
+++ b/src/libutil/Makefile.am
@@ -1,16 +1,16 @@
 pkglib_LTLIBRARIES = libutil.la
 
 libutil_la_SOURCES = util.cc hash.cc serialise.cc \
-  archive.cc aterm.cc aterm-map.cc xml-writer.cc
+  archive.cc xml-writer.cc
 
 libutil_la_LIBADD = ../boost/format/libformat.la
 
 pkginclude_HEADERS = util.hh hash.hh serialise.hh \
-  archive.hh aterm.hh aterm-map.hh xml-writer.hh types.hh
+  archive.hh xml-writer.hh types.hh
 
 if !HAVE_OPENSSL
 libutil_la_SOURCES += \
  md5.c md5.h sha1.c sha1.h sha256.c sha256.h md32_common.h
 endif
 
-AM_CXXFLAGS = -Wall -I$(srcdir)/.. ${aterm_include}
+AM_CXXFLAGS = -Wall -I$(srcdir)/..
diff --git a/src/libutil/aterm-map.cc b/src/libutil/aterm-map.cc
deleted file mode 100644
index c31fcdba3..000000000
--- a/src/libutil/aterm-map.cc
+++ /dev/null
@@ -1,332 +0,0 @@
-#include "aterm-map.hh"
-
-#include <iostream>
-
-#include <assert.h>
-#include <stdlib.h>
-
-#include <aterm2.h>
-
-
-namespace nix {
-
-
-static const unsigned int maxLoadFactor = /* 1 / */ 3;
-static unsigned int nrResizes = 0;
-static unsigned int sizeTotalAlloc = 0;
-static unsigned int sizeCurAlloc = 0;
-static unsigned int sizeMaxAlloc = 0;
-
-
-ATermMap::ATermMap(unsigned int expectedCount)
-{
-    init(expectedCount);
-}
-
-
-ATermMap::ATermMap(const ATermMap & map)
-{
-    init(map.maxCount);
-    copy(map.hashTable, map.capacity);
-}
-
-
-ATermMap & ATermMap::operator = (const ATermMap & map)
-{
-    if (this == &map) return *this;
-    free();
-    init(map.maxCount);
-    copy(map.hashTable, map.capacity);
-    return *this;
-}
-
-
-ATermMap::~ATermMap()
-{
-    free();
-}
-
-
-void ATermMap::init(unsigned int expectedCount)
-{
-    assert(sizeof(ATerm) * 2 == sizeof(KeyValue));
-    capacity = 0;
-    count = 0;
-    maxCount = 0;
-    hashTable = 0;
-    resizeTable(expectedCount);
-}
-
-
-void ATermMap::free()
-{
-    if (hashTable) {
-        ATunprotectArray((ATerm *) hashTable);
-        ::free(hashTable);
-        sizeCurAlloc -= sizeof(KeyValue) * capacity;
-        hashTable = 0;
-    }
-}
-
-
-static unsigned int roundToPowerOf2(unsigned int x)
-{
-    x--;
-    x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16;
-    x++;
-    return x;
-}
-
-
-void ATermMap::resizeTable(unsigned int expectedCount)
-{
-    if (expectedCount == 0) expectedCount = 1;
-//     cout << maxCount << " -> " << expectedCount << endl;
-//     cout << maxCount << " " << size << endl;
-//     cout << (double) size / maxCount << endl;
-
-    unsigned int oldCapacity = capacity;
-    KeyValue * oldHashTable = hashTable;
-
-    maxCount = expectedCount;
-    capacity = roundToPowerOf2(maxCount * maxLoadFactor);
-    hashTable = (KeyValue *) calloc(sizeof(KeyValue), capacity);
-    sizeTotalAlloc += sizeof(KeyValue) * capacity;
-    sizeCurAlloc += sizeof(KeyValue) * capacity;
-    if (sizeCurAlloc > sizeMaxAlloc) sizeMaxAlloc = sizeCurAlloc;
-    ATprotectArray((ATerm *) hashTable, capacity * 2);
-    
-//     cout << capacity << endl;
-
-    /* Re-hash the elements in the old table. */
-    if (oldCapacity != 0) {
-        count = 0;
-        copy(oldHashTable, oldCapacity);
-        ATunprotectArray((ATerm *) oldHashTable);
-        ::free(oldHashTable);
-        sizeCurAlloc -= sizeof(KeyValue) * oldCapacity;
-        nrResizes++;
-    }
-}
-
-
-void ATermMap::copy(KeyValue * elements, unsigned int capacity)
-{
-    for (unsigned int i = 0; i < capacity; ++i)
-        if (elements[i].value) /* i.e., non-empty, non-deleted element */
-            set(elements[i].key, elements[i].value);
-}
-
-
-/* !!! use a bigger shift for 64-bit platforms? */
-static const unsigned int shift = 16;
-static const unsigned long knuth = (unsigned long) (0.6180339887 * (1 << shift));
-
-
-unsigned long ATermMap::hash1(ATerm key) const
-{
-    /* Don't care about the least significant bits of the ATerm
-       pointer since they're always 0. */
-    unsigned long key2 = ((unsigned long) key) >> 2;
-
-    /* Approximately equal to:
-    double d = key2 * 0.6180339887;
-    unsigned int h = (int) (capacity * (d - floor(d)));
-    */
- 
-    unsigned long h = (capacity * ((key2 * knuth) & ((1 << shift) - 1))) >> shift;
-
-    return h;
-}
-
-
-unsigned long ATermMap::hash2(ATerm key) const
-{
-    unsigned long key2 = ((unsigned long) key) >> 2;
-    /* Note: the result must be relatively prime to `capacity' (which
-       is a power of 2), so we make sure that the result is always
-       odd. */
-    unsigned long h = ((key2 * 134217689) & (capacity - 1)) | 1;
-    return h;
-}
-
-
-static unsigned int nrItemsSet = 0;
-static unsigned int nrSetProbes = 0;
-
-
-void ATermMap::set(ATerm key, ATerm value)
-{
-    if (count == maxCount) resizeTable(capacity * 2 / maxLoadFactor);
-    
-    nrItemsSet++;
-    for (unsigned int i = 0, h = hash1(key); i < capacity;
-         ++i, h = (h + hash2(key)) & (capacity - 1))
-    {
-        // assert(h < capacity);
-        nrSetProbes++;
-        /* Note: to see whether a slot is free, we check
-           hashTable[h].value, not hashTable[h].key, since we use
-           value == 0 to mark deleted slots. */
-        if (hashTable[h].value == 0 || hashTable[h].key == key) {
-            if (hashTable[h].value == 0) count++;
-            hashTable[h].key = key;
-            hashTable[h].value = value;
-            return;
-        }
-    }
-        
-    abort();
-}
-
-
-static unsigned int nrItemsGet = 0;
-static unsigned int nrGetProbes = 0;
-
-
-ATerm ATermMap::get(ATerm key) const
-{
-    nrItemsGet++;
-    for (unsigned int i = 0, h = hash1(key); i < capacity;
-         ++i, h = (h + hash2(key)) & (capacity - 1))
-    {
-        nrGetProbes++;
-        if (hashTable[h].key == 0) return 0;
-        if (hashTable[h].key == key) return hashTable[h].value;
-    }
-    return 0;
-}
-
-
-void ATermMap::remove(ATerm key)
-{
-    for (unsigned int i = 0, h = hash1(key); i < capacity;
-         ++i, h = (h + hash2(key)) & (capacity - 1))
-    {
-        if (hashTable[h].key == 0) return;
-        if (hashTable[h].key == key) {
-            if (hashTable[h].value != 0) {
-                hashTable[h].value = 0;
-                count--;
-            }
-            return;
-        }
-    }
-}
-
-
-unsigned int ATermMap::size()
-{
-    return count; /* STL nomenclature */
-}
-
-
-void printATermMapStats()
-{
-    using std::cerr;
-    using std::endl;
-    
-    cerr << "RESIZES: " << nrResizes << " "
-         << sizeTotalAlloc << " "
-         << sizeCurAlloc << " "
-         << sizeMaxAlloc << endl;
-        
-    cerr << "SET: "
-         << nrItemsSet << " "
-         << nrSetProbes << " "
-         << (double) nrSetProbes / nrItemsSet << endl;
-
-    cerr << "GET: "
-         << nrItemsGet << " "
-         << nrGetProbes << " "
-         << (double) nrGetProbes / nrItemsGet << endl;
-}
-
-
-#if 0
-int main(int argc, char * * argv)
-{
-    ATerm bottomOfStack;
-    ATinit(argc, argv, &bottomOfStack);
-
-    /* Make test terms. */
-    int nrTestTerms = 100000;
-    ATerm testTerms[nrTestTerms];
-
-    for (int i = 0; i < nrTestTerms; ++i) {
-        char name[10];
-        sprintf(name, "%d", (int) random() % 37);
-
-        int arity = i == 0 ? 0 : (random() % 37);
-        ATerm kids[arity];
-        for (int j = 0; j < arity; ++j)
-            kids[j] = testTerms[random() % i];
-        
-        testTerms[i] = (ATerm) ATmakeApplArray(ATmakeAFun(name, arity, ATfalse), kids);
-//         ATwriteToSharedTextFile(testTerms[i], stdout);
-//         printf("\n");
-    }
-
-
-    cout << "testing...\n";
-
-    
-    #define someTerm() (testTerms[(int) random() % nrTestTerms])
-
-
-    for (int test = 0; test < 100000; ++test) {
-        //cerr << test << endl;
-        unsigned int n = 300;
-        ATermMap map(300);
-        ATerm keys[n], values[n];
-        for (unsigned int i = 0; i < n; ++i) {
-            keys[i] = someTerm();
-            values[i] = someTerm();
-            map.set(keys[i], values[i]);
-            //cerr << "INSERT: " << keys[i] << " " << values[i] << endl;
-        }
-
-        unsigned int size = map.size();
-        assert(size <= n);
-        values[n - 1] = 0;
-        map.remove(keys[n - 1]);
-        assert(map.size() == size - 1);
-
-        unsigned int checksum;
-        unsigned int count = 0;
-        for (ATermMap::const_iterator i = map.begin(); i != map.end(); ++i, ++count) {
-            assert(i->key);
-            assert(i->value);
-            checksum += (unsigned int) (*i).key;
-            checksum += (unsigned int) (*i).value;
-            // cout << (*i).key << " " << (*i).value << endl;
-        }
-        assert(count == size - 1);
-
-        for (unsigned int i = 0; i < n; ++i) {
-            for (unsigned int j = i + 1; j < n; ++j)
-                if (keys[i] == keys[j]) goto x;
-            if (map.get(keys[i]) != values[i]) {
-                cerr << "MISMATCH: " << keys[i] << " " << values[i] << " " << map.get(keys[i]) << " " << i << endl;
-                abort();
-            }
-            if (values[i] != 0) {
-                checksum -= (unsigned int) keys[i];
-                checksum -= (unsigned int) values[i];
-            }
-        x:  ;
-        }
-
-        assert(checksum == 0);
-        
-        for (unsigned int i = 0; i < 100; ++i)
-            map.get(someTerm());
-        
-    }
-
-    printATermMapStats();
-}
-#endif
-
- 
-}
diff --git a/src/libutil/aterm-map.hh b/src/libutil/aterm-map.hh
deleted file mode 100644
index b732453a7..000000000
--- a/src/libutil/aterm-map.hh
+++ /dev/null
@@ -1,129 +0,0 @@
-#ifndef __ATERM_MAP_H
-#define __ATERM_MAP_H
-
-#include <aterm1.h>
-#include <assert.h>
-
-
-namespace nix {
-
-
-class ATermMap
-{
-public:
-
-    struct KeyValue
-    {
-        ATerm key;
-        ATerm value;
-    };
-
-private:
-
-    /* Hash table for the map.  We use open addressing, i.e., all
-       key/value pairs are stored directly in the table, and there are
-       no pointers.  Collisions are resolved through probing. */
-    KeyValue * hashTable;
-
-    /* Current size of the hash table. */
-    unsigned int capacity;
-
-    /* Number of elements in the hash table. */
-    unsigned int count;
-
-    /* Maximum number of elements in the hash table.  If `count'
-       exceeds this number, the hash table is expanded. */
-    unsigned int maxCount;
-    
-public:
-
-    /* Create a map.  `expectedCount' is the number of elements the
-       map is expected to hold. */
-    ATermMap(unsigned int expectedCount = 16);
-    
-    ATermMap(const ATermMap & map);
-    
-    ~ATermMap();
-
-    ATermMap & operator = (const ATermMap & map);
-        
-    void set(ATerm key, ATerm value);
-
-    ATerm get(ATerm key) const;
-
-    ATerm operator [](ATerm key) const
-    {
-        return get(key);
-    }
-
-    void remove(ATerm key);
-
-    unsigned int size();
-
-    struct const_iterator
-    {
-        const ATermMap & map;
-        unsigned int pos;
-        const_iterator(const ATermMap & map, int pos) : map(map)
-        {
-            this->pos = pos;
-        }
-        bool operator !=(const const_iterator & i)
-        {
-            return pos != i.pos;
-        }
-        void operator ++()
-        {
-            if (pos == map.capacity) return;
-            do { ++pos; 
-            } while (pos < map.capacity && map.hashTable[pos].value == 0);
-        }
-        const KeyValue & operator *()
-        {
-            assert(pos < map.capacity);
-            return map.hashTable[pos];
-        }
-        const KeyValue * operator ->()
-        {
-            assert(pos < map.capacity);
-            return &map.hashTable[pos];
-        }
-    };
-
-    friend class ATermMap::const_iterator;
-    
-    const_iterator begin() const
-    {
-        unsigned int i = 0;
-        while (i < capacity && hashTable[i].value == 0) ++i;
-        return const_iterator(*this, i);
-    }
-    
-    const_iterator end() const
-    {
-        return const_iterator(*this, capacity);
-    }
-
-private:
-    
-    void init(unsigned int expectedCount);
-
-    void free();
-
-    void resizeTable(unsigned int expectedCount);
-
-    void copy(KeyValue * elements, unsigned int capacity);
-    
-    inline unsigned long hash1(ATerm key) const;
-    inline unsigned long hash2(ATerm key) const;
-};
-
-
-/* Hack. */
-void printATermMapStats();
-
- 
-}
-
-
-#endif /* !__ATERM_MAP_H */
diff --git a/src/libutil/aterm.cc b/src/libutil/aterm.cc
deleted file mode 100644
index 25d704785..000000000
--- a/src/libutil/aterm.cc
+++ /dev/null
@@ -1,55 +0,0 @@
-#include "aterm.hh"
-
-#include <cstring>
-
-using std::string;
-
-
-string nix::atPrint(ATerm t)
-{
-    if (!t) throw Error("attempt to print null aterm");
-    char * s = ATwriteToString(t);
-    if (!s) throw Error("cannot print term");
-    return s;
-}
-
-
-std::ostream & operator << (std::ostream & stream, ATerm e)
-{
-    return stream << nix::atPrint(e);
-}
-
-
-nix::Error nix::badTerm(const format & f, ATerm t)
-{
-    char * s = ATwriteToString(t);
-    if (!s) throw Error("cannot print term");
-    if (strlen(s) > 1000) {
-        int len;
-        s = ATwriteToSharedString(t, &len);
-        if (!s) throw Error("cannot print term");
-    }
-    return Error(format("%1%, in `%2%'") % f.str() % (string) s);
-}
-
-
-ATerm nix::toATerm(const char * s)
-{
-    return (ATerm) ATmakeAppl0(ATmakeAFun((char *) s, 0, ATtrue));
-}
-
-
-ATerm nix::toATerm(const string & s)
-{
-    return toATerm(s.c_str());
-}
-
-
-ATermList nix::toATermList(const StringSet & ss)
-{
-    ATermList l = ATempty;
-    for (StringSet::const_reverse_iterator i = ss.rbegin();
-         i != ss.rend(); ++i)
-        l = ATinsert(l, toATerm(*i));
-    return l;
-}
diff --git a/src/libutil/aterm.hh b/src/libutil/aterm.hh
deleted file mode 100644
index b1cbc3b6d..000000000
--- a/src/libutil/aterm.hh
+++ /dev/null
@@ -1,55 +0,0 @@
-#ifndef __ATERM_H
-#define __ATERM_H
-
-#include <aterm2.h>
-
-#include "types.hh"
-
-
-namespace nix {
-
-
-/* Print an ATerm. */
-string atPrint(ATerm t);
-
-class ATermIterator
-{
-    ATermList t;
-
-public:
-    ATermIterator(ATermList _t) : t(_t) { }
-    ATermIterator & operator ++ ()
-    {
-        t = ATgetNext(t);
-        return *this;
-    }
-    ATerm operator * ()
-    {
-        return ATgetFirst(t);
-    }
-    operator bool ()
-    {
-        return t != ATempty;
-    }
-};
-
-
-/* Throw an exception with an error message containing the given
-   aterm. */
-Error badTerm(const format & f, ATerm t);
-
-
-/* Convert strings to ATerms. */
-ATerm toATerm(const char * s);
-ATerm toATerm(const string & s);
-
-ATermList toATermList(const StringSet & ss);
- 
-}
-
-
-/* Write an ATerm to an output stream. */
-std::ostream & operator << (std::ostream & stream, ATerm e);
-
-
-#endif /* !__ATERM_H */
diff --git a/src/libutil/util.cc b/src/libutil/util.cc
index 790c25768..98912e7a0 100644
--- a/src/libutil/util.cc
+++ b/src/libutil/util.cc
@@ -951,53 +951,6 @@ void _interrupted()
 //////////////////////////////////////////////////////////////////////
 
 
-string packStrings(const Strings & strings)
-{
-    string d;
-    for (Strings::const_iterator i = strings.begin();
-         i != strings.end(); ++i)
-    {
-        unsigned int len = i->size();
-        d += len & 0xff;
-        d += (len >> 8) & 0xff;
-        d += (len >> 16) & 0xff;
-        d += (len >> 24) & 0xff;
-        d += *i;
-    }
-    return d;
-}
-
-    
-Strings unpackStrings(const string & s)
-{
-    Strings strings;
-    
-    string::const_iterator i = s.begin();
-    
-    while (i != s.end()) {
-
-        if (i + 4 > s.end())
-            throw Error(format("short db entry: `%1%'") % s);
-        
-        unsigned int len;
-        len = (unsigned char) *i++;
-        len |= ((unsigned char) *i++) << 8;
-        len |= ((unsigned char) *i++) << 16;
-        len |= ((unsigned char) *i++) << 24;
-
-        if (len == 0xffffffff) return strings; /* explicit end-of-list */
-        
-        if (i + len > s.end())
-            throw Error(format("short db entry: `%1%'") % s);
-
-        strings.push_back(string(i, i + len));
-        i += len;
-    }
-    
-    return strings;
-}
-
-
 Strings tokenizeString(const string & s, const string & separators)
 {
     Strings result;
@@ -1053,6 +1006,47 @@ bool hasSuffix(const string & s, const string & suffix)
 }
 
 
+void expect(std::istream & str, const string & s)
+{
+    char s2[s.size()];
+    str.read(s2, s.size());
+    if (string(s2, s.size()) != s)
+        throw Error(format("expected string `%1%'") % s);
+}
+
+
+string parseString(std::istream & str)
+{
+    string res;
+    expect(str, "\"");
+    int c;
+    while ((c = str.get()) != '"')
+        if (c == '\\') {
+            c = str.get();
+            if (c == 'n') res += '\n';
+            else if (c == 'r') res += '\r';
+            else if (c == 't') res += '\t';
+            else res += c;
+        }
+        else res += c;
+    return res;
+}
+
+
+bool endOfList(std::istream & str)
+{
+    if (str.peek() == ',') {
+        str.get();
+        return false;
+    }
+    if (str.peek() == ']') {
+        str.get();
+        return true;
+    }
+    return false;
+}
+
+
 void ignoreException()
 {
     try {
diff --git a/src/libutil/util.hh b/src/libutil/util.hh
index f609e8944..ff710077c 100644
--- a/src/libutil/util.hh
+++ b/src/libutil/util.hh
@@ -15,7 +15,7 @@ namespace nix {
 
 
 #define foreach(it_type, it, collection)                                \
-    for (it_type it = collection.begin(); it != collection.end(); ++it)
+    for (it_type it = (collection).begin(); it != (collection).end(); ++it)
 
 
 /* Return an environment variable. */
@@ -276,11 +276,6 @@ void inline checkInterrupt()
 MakeError(Interrupted, BaseError)
 
 
-/* String packing / unpacking. */
-string packStrings(const Strings & strings);
-Strings unpackStrings(const string & s);
-
-
 /* String tokenizer. */
 Strings tokenizeString(const string & s, const string & separators = " \t\n\r");
 
@@ -307,32 +302,21 @@ string int2String(int n);
 bool hasSuffix(const string & s, const string & suffix);
 
 
-/* Exception handling in destructors: print an error message, then
-   ignore the exception. */
-void ignoreException();
+/* Read string `s' from stream `str'. */
+void expect(std::istream & str, const string & s);
 
 
-/* STL functions such as sort() pass a binary function object around
-   by value, so it gets cloned a lot.  This is bad if the function
-   object has state or is simply large.  This adapter wraps the
-   function object to simulate passing by reference. */
-template<class F>
-struct binary_function_ref_adapter
-{
-    F * p;
+/* Read a C-style string from stream `str'. */
+string parseString(std::istream & str);
 
-    binary_function_ref_adapter(F * _p)
-    {
-        p = _p;
-    }
-    
-    typename F::result_type operator () (
-        const typename F::first_argument_type & x,
-        const typename F::second_argument_type & y)
-    {
-        return (*p)(x, y);
-    }
-};
+
+/* Utility function used to parse legacy ATerms. */
+bool endOfList(std::istream & str);
+
+
+/* Exception handling in destructors: print an error message, then
+   ignore the exception. */
+void ignoreException();
 
 
 }