* Refactoring: combine functions that take an attribute set and

  functions that take a single argument (plain lambdas) into one AST
  node (Function) that contains a Pattern node describing the
  arguments.  Current patterns are single lazy arguments (VarPat) and
  matching against an attribute set (AttrsPat).

  This refactoring allows other kinds of patterns to be added easily,
  such as Haskell-style @-patterns, or list pattern matching.

7 files changed, 165 insertions, 135 deletions

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 15cccc6b7f56..95a70ac2736b 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -74,63 +74,87 @@ LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2,
 }
 
 
-/* Substitute an argument set into the body of a function. */
-static Expr substArgs(EvalState & state,
-    Expr body, ATermList formals, Expr arg)
+static void patternMatch(EvalState & state,
+    Pattern pat, Expr arg, ATermMap & subs)
 {
-    unsigned int nrFormals = ATgetLength(formals);
-    ATermMap subs(nrFormals);
-
-    /* Get the actual arguments and put them in the substitution. */
-    ATermMap args;
-    queryAllAttrs(arg, args);
-    for (ATermMap::const_iterator i = args.begin(); i != args.end(); ++i)
-        subs.set(i->key, i->value);
+    ATerm name;
+    ATermList formals;
     
-    /* Get the formal arguments. */
-    ATermVector defsUsed;
-    ATermList recAttrs = ATempty;
-    for (ATermIterator i(formals); i; ++i) {
-        Expr name, def;
-        DefaultValue def2;
-        if (!matchFormal(*i, name, def2)) abort(); /* can't happen */
-
-        Expr value = subs[name];
-        
-        if (value == 0) {
-            if (!matchDefaultValue(def2, def)) def = 0;
-            if (def == 0) throw TypeError(format("the argument named `%1%' required by the function is missing")
-                % aterm2String(name));
-            value = def;
-            defsUsed.push_back(name);
-            recAttrs = ATinsert(recAttrs, makeBind(name, def, makeNoPos()));
-        }
-    }
+    if (matchVarPat(pat, name)) 
+        subs.set(name, arg);
+
+    else if (matchAttrsPat(pat, formals)) {
+
+        arg = evalExpr(state, arg);
+
+        unsigned int nrFormals = ATgetLength(formals);
 
-    /* Make a recursive attribute set out of the (argument-name,
-       value) tuples.  This is so that we can support default
-       parameters that refer to each other, e.g.  ({x, y ? x + x}: y)
-       {x = "foo";} evaluates to "foofoo". */
-    if (defsUsed.size() != 0) {
+        /* Get the actual arguments and put them in the substitution.
+           !!! shouldn't do this once we add `...'.*/
+        ATermMap args;
+        queryAllAttrs(arg, args);
         for (ATermMap::const_iterator i = args.begin(); i != args.end(); ++i)
-            recAttrs = ATinsert(recAttrs, makeBind(i->key, i->value, makeNoPos()));
-        Expr rec = makeRec(recAttrs, ATempty);
-        for (ATermVector::iterator i = defsUsed.begin(); i != defsUsed.end(); ++i)
-            subs.set(*i, makeSelect(rec, *i));
-    }
-    
-    if (subs.size() != nrFormals) {
-        /* One or more actual arguments were not declared as formal
-           arguments.  Find out which. */
+            subs.set(i->key, i->value);
+        
+        /* Get the formal arguments. */
+        ATermVector defsUsed;
+        ATermList recAttrs = ATempty;
         for (ATermIterator i(formals); i; ++i) {
-            Expr name; ATerm d1;
-            if (!matchFormal(*i, name, d1)) abort();
-            subs.remove(name);
+            Expr name, def;
+            DefaultValue def2;
+            if (!matchFormal(*i, name, def2)) abort(); /* can't happen */
+
+            Expr value = subs[name];
+        
+            if (value == 0) {
+                if (!matchDefaultValue(def2, def)) def = 0;
+                if (def == 0) throw TypeError(format("the argument named `%1%' required by the function is missing")
+                    % aterm2String(name));
+                value = def;
+                defsUsed.push_back(name);
+                recAttrs = ATinsert(recAttrs, makeBind(name, def, makeNoPos()));
+            }
+
+        }
+        
+        /* Make a recursive attribute set out of the (argument-name,
+           value) tuples.  This is so that we can support default
+           parameters that refer to each other, e.g.  ({x, y ? x + x}:
+           y) {x = "foo";} evaluates to "foofoo". */
+        if (defsUsed.size() != 0) {
+            for (ATermMap::const_iterator i = args.begin(); i != args.end(); ++i)
+                recAttrs = ATinsert(recAttrs, makeBind(i->key, i->value, makeNoPos()));
+            Expr rec = makeRec(recAttrs, ATempty);
+            for (ATermVector::iterator i = defsUsed.begin(); i != defsUsed.end(); ++i)
+                subs.set(*i, makeSelect(rec, *i));
+        }
+    
+        if (subs.size() != nrFormals) {
+            /* One or more actual arguments were not declared as
+               formal arguments.  Find out which. */
+            for (ATermIterator i(formals); i; ++i) {
+                Expr name; ATerm d1;
+                if (!matchFormal(*i, name, d1)) abort();
+                subs.remove(name);
+            }
+            throw TypeError(format("the function does not expect an argument named `%1%'")
+                % aterm2String(subs.begin()->key));
         }
-        throw TypeError(format("the function does not expect an argument named `%1%'")
-            % aterm2String(subs.begin()->key));
+
     }
 
+    else abort();
+}
+
+
+/* Substitute an argument set into the body of a function. */
+static Expr substArgs(EvalState & state,
+    Expr body, Pattern pat, Expr arg)
+{
+    ATermMap subs(16);
+    
+    patternMatch(state, pat, arg, subs);
+
     return substitute(Substitution(0, &subs), body);
 }
 
@@ -370,10 +394,12 @@ Path coerceToPath(EvalState & state, Expr e, PathSet & context)
 
 Expr autoCallFunction(Expr e, const ATermMap & args)
 {
-    ATermList formals;
+    Pattern pat;
     ATerm body, pos;
-    
-    if (matchFunction(e, formals, body, pos)) {
+    ATermList formals;
+
+    /* !!! this should be more general */
+    if (matchFunction(e, pat, body, pos) && matchAttrsPat(pat, formals)) {
         ATermMap actualArgs(ATgetLength(formals));
         
         for (ATermIterator i(formals); i; ++i) {
@@ -418,8 +444,8 @@ LocalNoInline(Expr evalVar(EvalState & state, ATerm name))
 
 LocalNoInline(Expr evalCall(EvalState & state, Expr fun, Expr arg))
 {
-    ATermList formals;
-    ATerm pos, name;
+    Pattern pat;
+    ATerm pos;
     Expr body;
         
     /* Evaluate the left-hand side. */
@@ -445,10 +471,9 @@ LocalNoInline(Expr evalCall(EvalState & state, Expr fun, Expr arg))
             return makePrimOp(arity, funBlob, args);
     }
 
-    else if (matchFunction(fun, formals, body, pos)) {
-        arg = evalExpr(state, arg);
+    else if (matchFunction(fun, pat, body, pos)) {
         try {
-            return evalExpr(state, substArgs(state, body, formals, arg));
+            return evalExpr(state, substArgs(state, body, pat, arg));
         } catch (Error & e) {
             addErrorPrefix(e, "while evaluating the function at %1%:\n",
                 showPos(pos));
@@ -456,18 +481,6 @@ LocalNoInline(Expr evalCall(EvalState & state, Expr fun, Expr arg))
         }
     }
         
-    else if (matchFunction1(fun, name, body, pos)) {
-        try {
-            ATermMap subs(1);
-            subs.set(name, arg);
-            return evalExpr(state, substitute(Substitution(0, &subs), body));
-        } catch (Error & e) {
-            addErrorPrefix(e, "while evaluating the function at %1%:\n",
-                showPos(pos));
-            throw;
-        }
-    }
-
     else throwTypeError(
         "attempt to call something which is neither a function nor a primop (built-in operation) but %1%",
         showType(fun));
@@ -624,7 +637,6 @@ Expr evalExpr2(EvalState & state, Expr e)
         sym == symInt ||
         sym == symBool ||
         sym == symFunction ||
-        sym == symFunction1 ||
         sym == symAttrs ||
         sym == symList ||
         sym == symPrimOp)
diff --git a/src/libexpr/expr-to-xml.cc b/src/libexpr/expr-to-xml.cc
index c47f24e6c0f9..5aa537b200ee 100644
--- a/src/libexpr/expr-to-xml.cc
+++ b/src/libexpr/expr-to-xml.cc
@@ -40,6 +40,23 @@ static void showAttrs(const ATermMap & attrs, XMLWriter & doc,
 }
 
 
+static void printPatternAsXML(Pattern pat, XMLWriter & doc, PathSet & context)
+{
+    ATerm name;
+    ATermList formals;
+    if (matchVarPat(pat, name))
+        doc.writeEmptyElement("varpat", singletonAttrs("name", aterm2String(name)));
+    else if (matchAttrsPat(pat, formals)) {
+        XMLOpenElement _(doc, "attrspat");
+        for (ATermIterator i(formals); i; ++i) {
+            Expr name; ATerm dummy;
+            if (!matchFormal(*i, name, dummy)) abort();
+            doc.writeEmptyElement("attr", singletonAttrs("name", aterm2String(name)));
+        }
+    }
+}
+
+
 static void printTermAsXML(Expr e, XMLWriter & doc, PathSet & context,
     ExprSet & drvsSeen)
 {
@@ -47,8 +64,8 @@ static void printTermAsXML(Expr e, XMLWriter & doc, PathSet & context,
     string s;
     ATerm s2;
     int i;
-    ATermList as, es, formals;
-    ATerm body, pos;
+    ATermList as, es;
+    ATerm pat, body, pos;
 
     checkInterrupt();
 
@@ -109,14 +126,9 @@ static void printTermAsXML(Expr e, XMLWriter & doc, PathSet & context,
             printTermAsXML(*i, doc, context, drvsSeen);
     }
 
-    else if (matchFunction(e, formals, body, pos)) {
+    else if (matchFunction(e, pat, body, pos)) {
         XMLOpenElement _(doc, "function");
-        
-        for (ATermIterator i(formals); i; ++i) {
-            Expr name; ATerm dummy;
-            if (!matchFormal(*i, name, dummy)) abort();
-            XMLOpenElement _(doc, "arg", singletonAttrs("name", aterm2String(name)));
-        }
+        printPatternAsXML(pat, doc, context);
     }
 
     else
diff --git a/src/libexpr/nixexpr-ast.def b/src/libexpr/nixexpr-ast.def
index a57a48613e53..6b9cf95faf99 100644
--- a/src/libexpr/nixexpr-ast.def
+++ b/src/libexpr/nixexpr-ast.def
@@ -3,8 +3,7 @@ init initNixExprHelpers
 Pos | string int int | Pos |
 NoPos | | Pos |
 
-Function | ATermList Expr Pos | Expr |
-Function1 | string Expr Pos | Expr |
+Function | Pattern Expr Pos | Expr |
 Assert | Expr Expr Pos | Expr |
 With | Expr Expr Pos | Expr |
 If | Expr Expr Expr | Expr |
@@ -76,6 +75,9 @@ Inherit | Expr ATermList Pos | ATerm |
 
 Scope | | Expr |
 
+VarPat | string | Pattern |
+AttrsPat | ATermList | Pattern |
+
 Formal | string DefaultValue | ATerm |
 
 DefaultValue | Expr | DefaultValue |
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 310f714718fe..4744cdde39ad 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -110,6 +110,25 @@ Expr makeAttrs(const ATermMap & attrs)
 }
 
 
+static void varsBoundByPattern(ATermMap & map, Pattern pat)
+{
+    ATerm name;
+    ATermList formals;
+    /* Use makeRemoved() so that it can be used directly in
+       substitute(). */
+    if (matchVarPat(pat, name))
+        map.set(name, makeRemoved());
+    else if (matchAttrsPat(pat, formals)) { 
+        for (ATermIterator i(formals); i; ++i) {
+            ATerm d1;
+            if (!matchFormal(*i, name, d1)) abort();
+            map.set(name, makeRemoved());
+        }
+    }
+    else abort();
+}
+
+
 Expr substitute(const Substitution & subs, Expr e)
 {
     checkInterrupt();
@@ -135,27 +154,17 @@ Expr substitute(const Substitution & subs, Expr e)
 
     /* In case of a function, filter out all variables bound by this
        function. */
-    ATermList formals;
+    Pattern pat;
     ATerm body;
-    if (matchFunction(e, formals, body, pos)) {
-        ATermMap map(ATgetLength(formals));
-        for (ATermIterator i(formals); i; ++i) {
-            ATerm d1;
-            if (!matchFormal(*i, name, d1)) abort();
-            map.set(name, makeRemoved());
-        }
+    if (matchFunction(e, pat, body, pos)) {
+        ATermMap map(16);
+        varsBoundByPattern(map, pat);
         Substitution subs2(&subs, &map);
         return makeFunction(
-            (ATermList) substitute(subs2, (ATerm) formals),
+            (Pattern) substitute(subs2, (Expr) pat),
             substitute(subs2, body), pos);
     }
 
-    if (matchFunction1(e, name, body, pos)) {
-        ATermMap map(1);
-        map.set(name, makeRemoved());
-        return makeFunction1(name, substitute(Substitution(&subs, &map), body), pos);
-    }
-        
     /* Idem for a mutually recursive attribute set. */
     ATermList rbnds, nrbnds;
     if (matchRec(e, rbnds, nrbnds)) {
@@ -213,9 +222,9 @@ static void checkVarDefs2(set<Expr> & done, const ATermMap & defs, Expr e)
     done.insert(e);
     
     ATerm name, pos, value;
-    ATermList formals;
     ATerm with, body;
     ATermList rbnds, nrbnds;
+    Pattern pat;
 
     /* Closed terms don't have free variables, so we don't have to
        check by definition. */
@@ -227,27 +236,11 @@ static void checkVarDefs2(set<Expr> & done, const ATermMap & defs, Expr e)
                 % aterm2String(name));
     }
 
-    else if (matchFunction(e, formals, body, pos)) {
-        ATermMap defs2(defs);
-        for (ATermIterator i(formals); i; ++i) {
-            ATerm d1;
-            if (!matchFormal(*i, name, d1)) abort();
-            defs2.set(name, (ATerm) ATempty);
-        }
-        for (ATermIterator i(formals); i; ++i) {
-            ATerm deflt;
-            set<Expr> done2;
-            if (!matchFormal(*i, name, deflt)) abort();
-            checkVarDefs2(done2, defs2, deflt);
-        }
-        set<Expr> done2;
-        checkVarDefs2(done2, defs2, body);
-    }
-        
-    else if (matchFunction1(e, name, body, pos)) {
+    else if (matchFunction(e, pat, body, pos)) {
         ATermMap defs2(defs);
-        defs2.set(name, (ATerm) ATempty);
+        varsBoundByPattern(defs2, pat);
         set<Expr> done2;
+        checkVarDefs2(done2, defs2, pat);
         checkVarDefs2(done2, defs2, body);
     }
         
@@ -365,13 +358,13 @@ string showType(Expr e)
     ATermList l1;
     ATermBlob b1;
     int i1;
+    Pattern p1;
     if (matchStr(e, t1, l1)) return "a string";
     if (matchPath(e, t1)) return "a path";
     if (matchNull(e)) return "null";
     if (matchInt(e, i1)) return "an integer";
     if (matchBool(e, t1)) return "a boolean";
-    if (matchFunction(e, l1, t1, t2)) return "a function";
-    if (matchFunction1(e, t1, t2, t3)) return "a function";
+    if (matchFunction(e, p1, t1, t2)) return "a function";
     if (matchAttrs(e, l1)) return "an attribute set";
     if (matchList(e, l1)) return "a list";
     if (matchPrimOp(e, i1, b1, l1)) return "a partially applied built-in function";
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index dabbaa323710..320d1dc977c5 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -21,11 +21,9 @@ MakeError(TypeError, EvalError)
    property of the ATerm library allows us to implement caching of
    normals forms efficiently. */
 typedef ATerm Expr;
-
 typedef ATerm DefaultValue;
-typedef ATerm ValidValues;
-
 typedef ATerm Pos;
+typedef ATerm Pattern;
 
 
 /* A STL vector of ATerms.  Should be used with great care since it's
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index 9c941bb7d446..067a0f8d54da 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -237,9 +237,9 @@ expr: expr_function;
 
 expr_function
   : '{' formals '}' ':' expr_function
-    { $$ = makeFunction($2, $5, CUR_POS); }
+    { $$ = makeFunction(makeAttrsPat($2), $5, CUR_POS); }
   | ID ':' expr_function
-    { $$ = makeFunction1($1, $3, CUR_POS); }
+    { $$ = makeFunction(makeVarPat($1), $3, CUR_POS); }
   | ASSERT expr ';' expr_function
     { $$ = makeAssert($2, $4, CUR_POS); }
   | WITH expr ';' expr_function
@@ -387,22 +387,37 @@ static void checkAttrs(ATermMap & names, ATermList bnds)
 }
 
 
-static void checkAttrSets(ATerm e)
+static void checkPatternVars(ATerm pos, ATermMap & map, Pattern pat)
 {
+    ATerm name;
     ATermList formals;
-    ATerm body, pos;
-    if (matchFunction(e, formals, body, pos)) {
-        ATermMap names(ATgetLength(formals));
+    if (matchVarPat(pat, name)) {
+        if (map.get(name))
+            throw EvalError(format("duplicate formal function argument `%1%' at %2%")
+                % aterm2String(name) % showPos(pos));
+        map.set(name, name);
+    }
+    else if (matchAttrsPat(pat, formals)) { 
         for (ATermIterator i(formals); i; ++i) {
-            ATerm name;
             ATerm d1;
             if (!matchFormal(*i, name, d1)) abort();
-            if (names.get(name))
+            if (map.get(name))
                 throw EvalError(format("duplicate formal function argument `%1%' at %2%")
                     % aterm2String(name) % showPos(pos));
-            names.set(name, name);
+            map.set(name, name);
         }
     }
+    else abort();
+}
+
+
+static void checkAttrSets(ATerm e)
+{
+    ATerm pat, body, pos;
+    if (matchFunction(e, pat, body, pos)) {
+        ATermMap map(16);
+        checkPatternVars(pos, map, pat);
+    }
 
     ATermList bnds;
     if (matchAttrs(e, bnds)) {
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index c747f46c4677..50a64167004d 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -120,11 +120,9 @@ static Expr prim_isNull(EvalState & state, const ATermVector & args)
 static Expr prim_isFunction(EvalState & state, const ATermVector & args)
 {
     Expr e = evalExpr(state, args[0]);
-    ATermList formals;
-    ATerm name, body, pos;
-    return makeBool(
-        matchFunction(e, formals, body, pos) ||
-        matchFunction1(e, name, body, pos));
+    Pattern pat;
+    ATerm body, pos;
+    return makeBool(matchFunction(e, pat, body, pos));
 }