21 files changed, 303 insertions, 11 deletions
diff --git a/configure.ac b/configure.ac
index 9d4b41b6bdba..a0ab10dc4dd9 100644
--- a/configure.ac
+++ b/configure.ac
@@ -31,9 +31,9 @@ AC_CONFIG_FILES([Makefile
    src/libutil/Makefile
    src/libstore/Makefile
    src/libmain/Makefile
-   src/nix/Makefile
+   src/nix-store/Makefile
    src/nix-hash/Makefile
-   src/fix-ng/Makefile
+   src/nix-instantiate/Makefile
    scripts/Makefile
    corepkgs/Makefile
    corepkgs/fetchurl/Makefile
diff --git a/src/Makefile.am b/src/Makefile.am
index ed989fed20b2..e35b82a889f0 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -1 +1 @@
-SUBDIRS = boost libutil libstore libmain nix nix-hash fix-ng
+SUBDIRS = boost libutil libstore libmain nix-store nix-hash nix-instantiate
diff --git a/src/fix-ng/Makefile.am b/src/nix-instantiate/Makefile.am
index d30a5b2ea065..cdaec1390d9e 100644
--- a/src/fix-ng/Makefile.am
+++ b/src/nix-instantiate/Makefile.am
@@ -1,7 +1,7 @@
-bin_PROGRAMS = fix-ng
+bin_PROGRAMS = nix-instantiate
 
-fix_ng_SOURCES = fixexpr.cc parser.cc eval.cc primops.cc fix.cc
-fix_ng_LDADD = ../libmain/libmain.a ../libstore/libstore.a ../libutil/libutil.a \
+nix_instantiate_SOURCES = fixexpr.cc parser.cc eval.cc primops.cc fix.cc
+nix_instantiate_LDADD = ../libmain/libmain.a ../libstore/libstore.a ../libutil/libutil.a \
  ../boost/format/libformat.a -L../../externals/inst/lib -ldb_cxx \
  -lsglr -lATB -lconversion -lasfix2 -lmept -lATerm
 
diff --git a/src/fix-ng/bin2c.c b/src/nix-instantiate/bin2c.c
index 18bf81d69e25..18bf81d69e25 100644
--- a/src/fix-ng/bin2c.c
+++ b/src/nix-instantiate/bin2c.c
diff --git a/src/fix-ng/eval.cc b/src/nix-instantiate/eval.cc
index b110c3a4a41c..b110c3a4a41c 100644
--- a/src/fix-ng/eval.cc
+++ b/src/nix-instantiate/eval.cc
diff --git a/src/fix-ng/eval.hh b/src/nix-instantiate/eval.hh
index 061c840a7576..061c840a7576 100644
--- a/src/fix-ng/eval.hh
+++ b/src/nix-instantiate/eval.hh
diff --git a/src/nix-instantiate/fix-expr.cc b/src/nix-instantiate/fix-expr.cc
new file mode 100644
index 000000000000..e9c5a3ba633f
--- /dev/null
+++ b/src/nix-instantiate/fix-expr.cc
@@ -0,0 +1,215 @@
+#include "fix-expr.hh"
+#include "expr.hh"
+
+
+ATermMap::ATermMap(unsigned int initialSize, unsigned int maxLoadPct)
+{
+    table = ATtableCreate(initialSize, maxLoadPct);
+    if (!table) throw Error("cannot create ATerm table");
+}
+
+
+ATermMap::ATermMap(const ATermMap & map)
+    : table(0)
+{
+    ATermList keys = map.keys();
+
+    /* !!! adjust allocation for load pct */
+    table = ATtableCreate(ATgetLength(keys), map.maxLoadPct);
+    if (!table) throw Error("cannot create ATerm table");
+
+    for (ATermIterator i(keys); i; ++i)
+        set(*i, map.get(*i));
+}
+
+
+ATermMap::~ATermMap()
+{
+    if (table) ATtableDestroy(table);
+}
+
+
+void ATermMap::set(ATerm key, ATerm value)
+{
+    return ATtablePut(table, key, value);
+}
+
+
+void ATermMap::set(const string & key, ATerm value)
+{
+    set(string2ATerm(key), value);
+}
+
+
+ATerm ATermMap::get(ATerm key) const
+{
+    return ATtableGet(table, key);
+}
+
+
+ATerm ATermMap::get(const string & key) const
+{
+    return get(string2ATerm(key));
+}
+
+
+void ATermMap::remove(ATerm key)
+{
+    ATtableRemove(table, key);
+}
+
+
+void ATermMap::remove(const string & key)
+{
+    remove(string2ATerm(key));
+}
+
+
+ATermList ATermMap::keys() const
+{
+    ATermList keys = ATtableKeys(table);
+    if (!keys) throw Error("cannot query aterm map keys");
+    return keys;
+}
+
+
+ATerm string2ATerm(const string & s)
+{
+    return (ATerm) ATmakeAppl0(ATmakeAFun((char *) s.c_str(), 0, ATtrue));
+}
+
+
+string aterm2String(ATerm t)
+{
+    return ATgetName(ATgetAFun(t));
+}
+    
+
+ATerm bottomupRewrite(TermFun & f, ATerm e)
+{
+    if (ATgetType(e) == AT_APPL) {
+        AFun fun = ATgetAFun(e);
+        int arity = ATgetArity(fun);
+        ATermList args = ATempty;
+
+        for (int i = arity - 1; i >= 0; i--)
+            args = ATinsert(args, bottomupRewrite(f, ATgetArgument(e, i)));
+        
+        e = (ATerm) ATmakeApplList(fun, args);
+    }
+
+    else if (ATgetType(e) == AT_LIST) {
+        ATermList in = (ATermList) e;
+        ATermList out = ATempty;
+
+        for (ATermIterator i(in); i; ++i)
+            out = ATinsert(out, bottomupRewrite(f, *i));
+
+        e = (ATerm) ATreverse(out);
+    }
+
+    return f(e);
+}
+
+
+void queryAllAttrs(Expr e, ATermMap & attrs)
+{
+    ATMatcher m;
+    ATermList bnds;
+    if (!(atMatch(m, e) >> "Attrs" >> bnds))
+        throw badTerm("expected attribute set", e);
+
+    for (ATermIterator i(bnds); i; ++i) {
+        string s;
+        Expr e;
+        if (!(atMatch(m, *i) >> "Bind" >> s >> e))
+            abort(); /* can't happen */
+        attrs.set(s, e);
+    }
+}
+
+
+Expr queryAttr(Expr e, const string & name)
+{
+    ATermMap attrs;
+    queryAllAttrs(e, attrs);
+    return attrs.get(name);
+}
+
+
+Expr makeAttrs(const ATermMap & attrs)
+{
+    ATermList bnds = ATempty;
+    for (ATermIterator i(attrs.keys()); i; ++i)
+        bnds = ATinsert(bnds, 
+            ATmake("Bind(<term>, <term>)", *i, attrs.get(*i)));
+    return ATmake("Attrs(<term>)", ATreverse(bnds));
+}
+
+
+Expr substitute(const ATermMap & subs, Expr e)
+{
+    ATMatcher m;
+    string s;
+
+    if (atMatch(m, e) >> "Var" >> s) {
+        Expr sub = subs.get(s);
+        return sub ? sub : e;
+    }
+
+    /* In case of a function, filter out all variables bound by this
+       function. */
+    ATermList formals;
+    ATerm body;
+    if (atMatch(m, e) >> "Function" >> formals >> body) {
+        ATermMap subs2(subs);
+        for (ATermIterator i(formals); i; ++i) {
+            Expr def;
+            if (!(atMatch(m, *i) >> "NoDefFormal" >> s) &&
+                !(atMatch(m, *i) >> "DefFormal" >> s >> def))
+                abort();
+            subs2.remove(s);
+        }
+        return ATmake("Function(<term>, <term>)", formals,
+            substitute(subs2, body));
+    }
+
+    /* Idem for a mutually recursive attribute set. */
+    ATermList bindings;
+    if (atMatch(m, e) >> "Rec" >> bindings) {
+        ATermMap subs2(subs);
+        for (ATermIterator i(bindings); i; ++i) {
+            Expr e;
+            if (!(atMatch(m, *i) >> "Bind" >> s >> e))
+                abort(); /* can't happen */
+            subs2.remove(s);
+        }
+        return ATmake("Rec(<term>)", substitute(subs2, (ATerm) bindings));
+    }
+
+    if (ATgetType(e) == AT_APPL) {
+        AFun fun = ATgetAFun(e);
+        int arity = ATgetArity(fun);
+        ATermList args = ATempty;
+
+        for (int i = arity - 1; i >= 0; i--)
+            args = ATinsert(args, substitute(subs, ATgetArgument(e, i)));
+        
+        return (ATerm) ATmakeApplList(fun, args);
+    }
+
+    if (ATgetType(e) == AT_LIST) {
+        ATermList out = ATempty;
+        for (ATermIterator i((ATermList) e); i; ++i)
+            out = ATinsert(out, substitute(subs, *i));
+        return (ATerm) ATreverse(out);
+    }
+
+    return e;
+}
+
+
+Expr makeBool(bool b)
+{
+    return b ? ATmake("Bool(True)") : ATmake("Bool(False)");
+}
diff --git a/src/fix-ng/fixexpr.hh b/src/nix-instantiate/fix-expr.hh
index 6c1e51d9ccd6..6c1e51d9ccd6 100644
--- a/src/fix-ng/fixexpr.hh
+++ b/src/nix-instantiate/fix-expr.hh
diff --git a/src/fix-ng/fix.cc b/src/nix-instantiate/fix.cc
index e407aaf44346..e407aaf44346 100644
--- a/src/fix-ng/fix.cc
+++ b/src/nix-instantiate/fix.cc
diff --git a/src/fix-ng/fix.sdf b/src/nix-instantiate/fix.sdf
index 54f5d5266f79..54f5d5266f79 100644
--- a/src/fix-ng/fix.sdf
+++ b/src/nix-instantiate/fix.sdf
diff --git a/src/fix-ng/fixexpr.cc b/src/nix-instantiate/fixexpr.cc
index 721fa8afa5f2..721fa8afa5f2 100644
--- a/src/fix-ng/fixexpr.cc
+++ b/src/nix-instantiate/fixexpr.cc
diff --git a/src/nix-instantiate/fixexpr.hh b/src/nix-instantiate/fixexpr.hh
new file mode 100644
index 000000000000..6c1e51d9ccd6
--- /dev/null
+++ b/src/nix-instantiate/fixexpr.hh
@@ -0,0 +1,75 @@
+#ifndef __FIXEXPR_H
+#define __FIXEXPR_H
+
+#include <map>
+
+#include <aterm2.h>
+
+#include "util.hh"
+
+
+/* Fix expressions are represented as ATerms.  The maximal sharing
+   property of the ATerm library allows us to implement caching of
+   normals forms efficiently. */
+typedef ATerm Expr;
+
+
+/* Mappings from ATerms to ATerms.  This is just a wrapper around
+   ATerm tables. */
+class ATermMap
+{
+private:
+    unsigned int maxLoadPct;
+    ATermTable table;
+    
+public:
+    ATermMap(unsigned int initialSize = 16, unsigned int maxLoadPct = 75);
+    ATermMap(const ATermMap & map);
+    ~ATermMap();
+
+    void set(ATerm key, ATerm value);
+    void set(const string & key, ATerm value);
+
+    ATerm get(ATerm key) const;
+    ATerm get(const string & key) const;
+
+    void remove(ATerm key);
+    void remove(const string & key);
+
+    ATermList keys() const;
+};
+
+
+/* Convert a string to an ATerm (i.e., a quoted nullary function
+   applicaton). */
+ATerm string2ATerm(const string & s);
+string aterm2String(ATerm t);
+
+/* Generic bottomup traversal over ATerms.  The traversal first
+   recursively descends into subterms, and then applies the given term
+   function to the resulting term. */
+struct TermFun
+{
+    virtual ATerm operator () (ATerm e) = 0;
+};
+ATerm bottomupRewrite(TermFun & f, ATerm e);
+
+/* Query all attributes in an attribute set expression.  The
+   expression must be in normal form. */
+void queryAllAttrs(Expr e, ATermMap & attrs);
+
+/* Query a specific attribute from an attribute set expression.  The
+   expression must be in normal form. */
+Expr queryAttr(Expr e, const string & name);
+
+/* Create an attribute set expression from an Attrs value. */
+Expr makeAttrs(const ATermMap & attrs);
+
+/* Perform a set of substitutions on an expression. */
+Expr substitute(const ATermMap & subs, Expr e);
+
+/* Create an expression representing a boolean. */
+Expr makeBool(bool b);
+
+
+#endif /* !__FIXEXPR_H */
diff --git a/src/fix-ng/parser.cc b/src/nix-instantiate/parser.cc
index eaa41b3963ef..eaa41b3963ef 100644
--- a/src/fix-ng/parser.cc
+++ b/src/nix-instantiate/parser.cc
diff --git a/src/fix-ng/parser.hh b/src/nix-instantiate/parser.hh
index e44987dd014b..e44987dd014b 100644
--- a/src/fix-ng/parser.hh
+++ b/src/nix-instantiate/parser.hh
diff --git a/src/fix-ng/primops.cc b/src/nix-instantiate/primops.cc
index 097933115342..097933115342 100644
--- a/src/fix-ng/primops.cc
+++ b/src/nix-instantiate/primops.cc
diff --git a/src/fix-ng/primops.hh b/src/nix-instantiate/primops.hh
index 76d587afdb1e..76d587afdb1e 100644
--- a/src/fix-ng/primops.hh
+++ b/src/nix-instantiate/primops.hh
diff --git a/src/nix/Makefile.am b/src/nix-store/Makefile.am
index 8a52be364f1a..a39d1e2ad985 100644
--- a/src/nix/Makefile.am
+++ b/src/nix-store/Makefile.am
@@ -1,7 +1,7 @@
-bin_PROGRAMS = nix
+bin_PROGRAMS = nix-store
 
-nix_SOURCES = nix.cc dotgraph.cc
-nix_LDADD = ../libmain/libmain.a ../libstore/libstore.a ../libutil/libutil.a \
+nix_store_SOURCES = nix.cc dotgraph.cc
+nix_store_LDADD = ../libmain/libmain.a ../libstore/libstore.a ../libutil/libutil.a \
  ../boost/format/libformat.a -L../../externals/inst/lib -ldb_cxx -lATerm
 
 nix.o: nix-help.txt.hh
@@ -22,6 +22,6 @@ install-data-local:
 	ln -sf $(localstatedir)/nix/links/current $(prefix)/current
 	$(INSTALL) -d $(localstatedir)/log/nix
 	$(INSTALL) -d $(prefix)/store
-	$(bindir)/nix --init
+	$(bindir)/nix-store --init
 
 EXTRA_DIST = *.hh
diff --git a/src/nix/dotgraph.cc b/src/nix-store/dotgraph.cc
index c670bf19e4c5..c670bf19e4c5 100644
--- a/src/nix/dotgraph.cc
+++ b/src/nix-store/dotgraph.cc
diff --git a/src/nix/dotgraph.hh b/src/nix-store/dotgraph.hh
index ef389b30d353..ef389b30d353 100644
--- a/src/nix/dotgraph.hh
+++ b/src/nix-store/dotgraph.hh
diff --git a/src/nix/nix-help.txt b/src/nix-store/nix-help.txt
index a2d9958ffe49..d7f977025440 100644
--- a/src/nix/nix-help.txt
+++ b/src/nix-store/nix-help.txt
@@ -1,4 +1,6 @@
-nix [OPTIONS...] [ARGUMENTS...]
+nix-store [OPTIONS...] [ARGUMENTS...]
+
+`nix-store' is a tool to manipulate the Nix store.
 
 Operations:
 
diff --git a/src/nix/nix.cc b/src/nix-store/nix.cc
index d1766de39b7e..d1766de39b7e 100644
--- a/src/nix/nix.cc
+++ b/src/nix-store/nix.cc