Beginnings of support for constrained types

Programs with constrained types now parse and typecheck, but
typestate doesn't check them specially, so the one relevant test
case so far is XFAILed.

Also rewrote all of the constraint-related data structures in the
process (again), for some reason. I got rid of a superfluous
data structure in the context that was mapping front-end constraints
to resolved constraints, instead handling constraints in the same
way in which everything else gets resolved.

5 files changed, 131 insertions, 76 deletions

diff --git a/src/comp/syntax/ast.rs b/src/comp/syntax/ast.rs
index 745aa4e1fcd..e2b2e53df07 100644
--- a/src/comp/syntax/ast.rs
+++ b/src/comp/syntax/ast.rs
@@ -444,7 +444,7 @@ tag ty_ {
     ty_obj(ty_method[]);
     ty_path(path, node_id);
     ty_type;
-    ty_constr(@ty, (@constr)[]);
+    ty_constr(@ty, (@ty_constr)[]);
     ty_mac(mac);
 }
 
@@ -459,16 +459,26 @@ declarations, and ident for uses.
 */
 tag constr_arg_general_[T] { carg_base; carg_ident(T); carg_lit(@lit); }
 
-type constr_arg = constr_arg_general[uint];
+type fn_constr_arg = constr_arg_general_[uint];
+type sp_constr_arg[T] = spanned[constr_arg_general_[T]];
+type ty_constr_arg = sp_constr_arg[path];
+type constr_arg = spanned[fn_constr_arg];
 
-type constr_arg_general[T] = spanned[constr_arg_general_[T]];
+// Constrained types' args are parameterized by paths, since
+// we refer to paths directly and not by indices.
+// The implicit root of such path, in the constraint-list for a
+// constrained type, is * (referring to the base record)
 
-type constr_ = rec(path path,
-                   (@constr_arg_general[uint])[] args,
-                   node_id id);
-
-type constr = spanned[constr_];
+type constr_general_[ARG, ID] = rec(path path,
+     (@(spanned[constr_arg_general_[ARG]]))[] args, ID id);
 
+// In the front end, constraints have a node ID attached.
+// Typeck turns this to a def_id, using the output of resolve.
+type constr_general[ARG] = spanned[constr_general_[ARG, node_id]];
+type constr_ = constr_general_[uint, node_id];
+type constr = spanned[constr_general_[uint, node_id]];
+type ty_constr_ = ast::constr_general_[ast::path, ast::node_id];
+type ty_constr = spanned[ty_constr_];
 
 /* The parser generates ast::constrs; resolve generates
  a mapping from each function to a list of ty::constr_defs,
@@ -671,19 +681,6 @@ fn ternary_to_if(&@expr e) -> @ast::expr {
     }
 }
 
-// Path stringification
-fn path_to_str(&ast::path pth) -> str {
-    auto result = str::connect_ivec(pth.node.idents, "::");
-    if (ivec::len[@ast::ty](pth.node.types) > 0u) {
-        fn f(&@ast::ty t) -> str { ret print::pprust::ty_to_str(*t); }
-        result += "[";
-        result += str::connect_ivec(ivec::map(f, pth.node.types), ",");
-        result += "]";
-    }
-    ret result;
-}
-
-
 //
 // Local Variables:
 // mode: rust
diff --git a/src/comp/syntax/fold.rs b/src/comp/syntax/fold.rs
index a4921b46bca..a12a7da4aef 100644
--- a/src/comp/syntax/fold.rs
+++ b/src/comp/syntax/fold.rs
@@ -35,7 +35,7 @@ type ast_fold_precursor =
         fn (&decl_ d, ast_fold) -> decl_                  fold_decl,
         fn (&expr_ e, ast_fold) -> expr_                  fold_expr,
         fn (&ty_ t, ast_fold) -> ty_                      fold_ty,
-        fn (&constr_ c, ast_fold) -> constr_              fold_constr,
+        fn (&ast::constr_ c, ast_fold) -> constr_              fold_constr,
         fn (&_fn f, ast_fold) -> _fn                      fold_fn,
         fn (&_mod m, ast_fold) -> _mod                    fold_mod,
         fn (&native_mod, ast_fold) -> native_mod          fold_native_mod,
@@ -473,7 +473,7 @@ fn noop_fold_ty(&ty_ t, ast_fold fld) -> ty_ {
 }
 
 fn noop_fold_constr(&constr_ c, ast_fold fld) -> constr_ {
-    ret rec(path=fld.fold_path(c.path), args=c.args, id=c.id);
+    rec(path=fld.fold_path(c.path), args=c.args, id=c.id)
 }
 
 // functions just don't get spans, for some reason
@@ -664,7 +664,8 @@ fn make_fold(&ast_fold_precursor afp) -> ast_fold {
     fn f_ty(&ast_fold_precursor afp, ast_fold f, &@ty x) -> @ty {
         ret @rec(node=afp.fold_ty(x.node, f), span=x.span);
     }
-    fn f_constr(&ast_fold_precursor afp, ast_fold f, &@constr x) -> @constr {
+    fn f_constr(&ast_fold_precursor afp, ast_fold f, &@ast::constr x)
+        -> @ast::constr {
         ret @rec(node=afp.fold_constr(x.node, f), span=x.span);
     }
     fn f_fn(&ast_fold_precursor afp, ast_fold f, &_fn x) -> _fn {
diff --git a/src/comp/syntax/parse/parser.rs b/src/comp/syntax/parse/parser.rs
index 59dbf72f7c5..724fcd75386 100644
--- a/src/comp/syntax/parse/parser.rs
+++ b/src/comp/syntax/parse/parser.rs
@@ -14,6 +14,8 @@ import ex=ext::base;
 import codemap::span;
 import std::map::new_str_hash;
 import util::interner;
+import ast::node_id;
+import ast::spanned;
 
 tag restriction { UNRESTRICTED; RESTRICT_NO_CALL_EXPRS; }
 
@@ -22,9 +24,9 @@ tag file_type { CRATE_FILE; SOURCE_FILE; }
 tag ty_or_bang { a_ty(@ast::ty); a_bang; }
 
 type parse_sess = @rec(codemap::codemap cm,
-                       mutable ast::node_id next_id);
+                       mutable node_id next_id);
 
-fn next_node_id(&parse_sess sess) -> ast::node_id {
+fn next_node_id(&parse_sess sess) -> node_id {
     auto rv = sess.next_id;
     sess.next_id += 1;
     ret rv;
@@ -51,7 +53,7 @@ type parser =
         fn get_bad_expr_words() -> hashmap[str, ()] ;
         fn get_chpos() -> uint ;
         fn get_byte_pos() -> uint ;
-        fn get_id() -> ast::node_id ;
+        fn get_id() -> node_id ;
         fn get_sess() -> parse_sess;
     };
 
@@ -116,7 +118,7 @@ fn new_parser(parse_sess sess, ast::crate_cfg cfg, lexer::reader rdr,
         fn get_bad_expr_words() -> hashmap[str, ()] { ret bad_words; }
         fn get_chpos() -> uint { ret rdr.get_chpos(); }
         fn get_byte_pos() -> uint { ret rdr.get_byte_pos(); }
-        fn get_id() -> ast::node_id { ret next_node_id(sess); }
+        fn get_id() -> node_id { ret next_node_id(sess); }
         fn get_sess() -> parse_sess { ret sess; }
     }
 
@@ -188,7 +190,7 @@ fn expect(&parser p, token::token t) {
     }
 }
 
-fn spanned[T](uint lo, uint hi, &T node) -> ast::spanned[T] {
+fn spanned[T](uint lo, uint hi, &T node) -> spanned[T] {
     ret rec(node=node, span=rec(lo=lo, hi=hi));
 }
 
@@ -261,7 +263,9 @@ fn parse_ty_fn(ast::proto proto, &parser p, uint lo) -> ast::ty_ {
     auto inputs =
         parse_seq(token::LPAREN, token::RPAREN, some(token::COMMA),
                        parse_fn_input_ty, p);
-    auto constrs = parse_constrs(~[], p);
+    // FIXME: there's no syntax for this right now anyway
+    //  auto constrs = parse_constrs(~[], p);
+    let (@ast::constr)[] constrs = ~[];
     let @ast::ty output;
     auto cf = ast::return;
     if (p.peek() == token::RARROW) {
@@ -275,7 +279,7 @@ fn parse_ty_fn(ast::proto proto, &parser p, uint lo) -> ast::ty_ {
             }
         }
     } else { output = @spanned(lo, inputs.span.hi, ast::ty_nil); }
-    ret ast::ty_fn(proto, inputs.node, output, cf, constrs.node);
+    ret ast::ty_fn(proto, inputs.node, output, cf, constrs);
 }
 
 fn parse_proto(&parser p) -> ast::proto {
@@ -336,6 +340,20 @@ fn ident_index(&parser p, &ast::arg[] args, &ast::ident i) -> uint {
     p.fatal("Unbound variable " + i + " in constraint arg");
 }
 
+fn parse_type_constr_arg(&parser p) -> @ast::ty_constr_arg {
+    auto sp = p.get_span();
+    auto carg = ast::carg_base;
+    expect(p, token::BINOP(token::STAR));
+    if (p.peek() == token::DOT) {
+        // "*..." notation for record fields
+        p.bump();
+        let ast::path pth = parse_path(p);
+        carg = ast::carg_ident(pth);
+    }
+    // No literals yet, I guess?
+    ret @rec(node=carg, span=sp);
+}
+
 fn parse_constr_arg(&ast::arg[] args, &parser p) -> @ast::constr_arg {
     auto sp = p.get_span();
     auto carg = ast::carg_base;
@@ -355,43 +373,39 @@ fn parse_ty_constr(&ast::arg[] fn_args, &parser p) -> @ast::constr {
     let rec((@ast::constr_arg)[] node, span span) args =
         parse_seq(token::LPAREN, token::RPAREN, some(token::COMMA), pf,
                        p);
-    // FIXME fix the def_id
-
     ret @spanned(lo, args.span.hi,
                  rec(path=path, args=args.node, id=p.get_id()));
 }
 
-
-// Use the args list to translate each bound variable
-// mentioned in a constraint to an arg index.
-// Seems weird to do this in the parser, but I'm not sure how else to.
-fn parse_constrs(&ast::arg[] args, &parser p)
-        -> ast::spanned[(@ast::constr)[]] {
+fn parse_constr_in_type(&parser p) -> @ast::ty_constr {
     auto lo = p.get_lo_pos();
-    auto hi = p.get_hi_pos();
-    let (@ast::constr)[] constrs = ~[];
-    if (p.peek() == token::COLON) {
-        p.bump();
-        while (true) {
-            auto constr = parse_ty_constr(args, p);
-            hi = constr.span.hi;
-            constrs += ~[constr];
-            if (p.peek() == token::COMMA) { p.bump(); } else { break; }
-        }
-    }
-    ret spanned(lo, hi, constrs);
+    auto path = parse_path(p);
+    let (@ast::ty_constr_arg)[] args =
+        (parse_seq(token::LPAREN, token::RPAREN, some(token::COMMA),
+                        parse_type_constr_arg, p)).node;
+    auto hi = p.get_lo_pos();
+    let ast::ty_constr_ tc = rec(path=path, args=args, id=p.get_id());
+    ret @spanned(lo, hi, tc);
 }
 
-fn parse_ty_constrs(@ast::ty t, &parser p) -> @ast::ty {
-    if (p.peek() == token::COLON) {
-        auto constrs = parse_constrs(~[], p);
-        ret @spanned(t.span.lo, constrs.span.hi,
-                     ast::ty_constr(t, constrs.node));
+
+fn parse_constrs[T](fn(&parser p) ->
+                    (@ast::constr_general[T]) pser, &parser p)
+    ->  (@ast::constr_general[T])[] {
+    let (@ast::constr_general[T])[] constrs = ~[];
+    while (true) {
+        auto constr = pser(p);
+        constrs += ~[constr];
+        if (p.peek() == token::COMMA) { p.bump(); } else { break; }
     }
-    ret t;
+    constrs
+}
+
+fn parse_type_constraints(&parser p) -> (@ast::ty_constr)[] {
+    ret parse_constrs(parse_constr_in_type, p);
 }
 
-fn parse_ty_postfix(@ast::ty orig_t, &parser p) -> @ast::ty {
+fn parse_ty_postfix(ast::ty_ orig_t, &parser p) -> @ast::ty {
     auto lo = p.get_lo_pos();
     if (p.peek() == token::LBRACKET) {
         p.bump();
@@ -413,7 +427,7 @@ fn parse_ty_postfix(@ast::ty orig_t, &parser p) -> @ast::ty {
             auto seq = parse_seq_to_end(token::RBRACKET,
                                              some(token::COMMA), parse_ty, p);
 
-            alt (orig_t.node) {
+            alt (orig_t) {
                 case (ast::ty_path(?pth, ?ann)) {
                     auto hi = p.get_hi_pos();
                     ret @spanned(lo, hi,
@@ -432,10 +446,11 @@ fn parse_ty_postfix(@ast::ty orig_t, &parser p) -> @ast::ty {
 
         expect(p, token::RBRACKET);
         auto hi = p.get_hi_pos();
-        auto t = ast::ty_ivec(rec(ty=orig_t, mut=mut));
-        ret parse_ty_postfix(@spanned(lo, hi, t), p);
+        // FIXME: spans are probably wrong
+        auto t = ast::ty_ivec(rec(ty=@spanned(lo, hi, orig_t), mut=mut));
+        ret parse_ty_postfix(t, p);
     }
-    ret parse_ty_constrs(orig_t, p);
+    ret @spanned(lo, p.get_lo_pos(), orig_t);
 }
 
 fn parse_ty_or_bang(&parser p) -> ty_or_bang {
@@ -528,7 +543,15 @@ fn parse_ty(&parser p) -> @ast::ty {
             parse_seq(token::LPAREN, token::RPAREN, some(token::COMMA),
                            parse_ty_field, p);
         hi = elems.span.hi;
+        // possible constrs
+        // FIXME: something seems dodgy or at least repetitive
+        // about how constrained types get parsed
         t = ast::ty_rec(elems.node);
+        if (p.peek() == token::COLON) {
+            p.bump();
+            t = ast::ty_constr(@spanned(lo, hi, t),
+                               parse_type_constraints(p));
+        }
     } else if (eat_word(p, "fn")) {
         auto flo = p.get_last_lo_pos();
         t = parse_ty_fn(ast::proto_fn, p, flo);
@@ -559,7 +582,7 @@ fn parse_ty(&parser p) -> @ast::ty {
         t = ast::ty_path(path, p.get_id());
         hi = path.span.hi;
     } else { p.fatal("expecting type"); t = ast::ty_nil; fail; }
-    ret parse_ty_postfix(@spanned(lo, hi, t), p);
+    ret parse_ty_postfix(t, p);
 }
 
 fn parse_arg(&parser p) -> ast::arg {
@@ -593,7 +616,7 @@ fn parse_seq_to_end[T](token::token ket, option::t[token::token] sep,
 
 fn parse_seq[T](token::token bra, token::token ket,
                      option::t[token::token] sep,
-                     fn(&parser)->T  f, &parser p) -> ast::spanned[T[]] {
+                     fn(&parser)->T  f, &parser p) -> spanned[T[]] {
     auto lo = p.get_lo_pos();
     expect(p, bra);
     auto result = parse_seq_to_end[T](ket, sep, f, p);
@@ -1739,7 +1762,14 @@ fn parse_fn_decl(&parser p, ast::purity purity) -> ast::fn_decl {
         parse_seq(token::LPAREN, token::RPAREN, some(token::COMMA),
                        parse_arg, p);
     let ty_or_bang rslt;
-    auto constrs = parse_constrs(inputs.node, p).node;
+// Use the args list to translate each bound variable
+// mentioned in a constraint to an arg index.
+// Seems weird to do this in the parser, but I'm not sure how else to.
+    auto constrs = ~[];
+    if (p.peek() == token::COLON) {
+        p.bump();
+        constrs = parse_constrs(bind parse_ty_constr(inputs.node,_), p);
+    }
     if (p.peek() == token::RARROW) {
         p.bump();
         rslt = parse_ty_or_bang(p);
diff --git a/src/comp/syntax/print/pprust.rs b/src/comp/syntax/print/pprust.rs
index caeba63ffd5..6d79acd64a7 100644
--- a/src/comp/syntax/print/pprust.rs
+++ b/src/comp/syntax/print/pprust.rs
@@ -332,7 +332,7 @@ fn print_type(&ps s, &ast::ty ty) {
             space(s.s);
             word(s.s, ":");
             space(s.s);
-            word(s.s, ast_constrs_str(cs));
+            word(s.s, ast_ty_constrs_str(cs));
         }
     }
     end(s);
@@ -1521,10 +1521,10 @@ fn next_comment(&ps s) -> option::t[lexer::cmnt] {
 // Removing the aliases from the type of f in the next two functions
 // triggers memory corruption, but I haven't isolated the bug yet. FIXME
 fn constr_args_to_str[T](&fn(&T) -> str f,
-                         &(@ast::constr_arg_general[T])[] args) -> str {
+                         &(@ast::sp_constr_arg[T])[] args) -> str {
     auto comma = false;
     auto s = "(";
-    for (@ast::constr_arg_general[T] a in args) {
+    for (@ast::sp_constr_arg[T] a in args) {
         if (comma) { s += ", "; } else { comma = true; }
         s += constr_arg_to_str[T](f, a.node);
     }
@@ -1547,10 +1547,11 @@ fn constr_arg_to_str[T](&fn(&T) -> str f, &ast::constr_arg_general_[T] c) ->
 fn uint_to_str(&uint i) -> str { ret uint::str(i); }
 
 fn ast_constr_to_str(&@ast::constr c) -> str {
-    ret ast::path_to_str(c.node.path) +
-        constr_args_to_str(uint_to_str, c.node.args);
+    ret path_to_str(c.node.path) +
+          constr_args_to_str(uint_to_str, c.node.args);
 }
 
+// FIXME: fix repeated code
 fn ast_constrs_str(&(@ast::constr)[] constrs) -> str {
     auto s = "";
     auto colon = true;
@@ -1568,6 +1569,22 @@ fn proto_to_str(&ast::proto p) -> str {
     };
 }
 
+fn ty_constr_to_str(&@ast::ty_constr c) -> str {
+    ret path_to_str(c.node.path) +
+          constr_args_to_str[ast::path](path_to_str, c.node.args);
+}
+
+
+fn ast_ty_constrs_str(&(@ast::ty_constr)[] constrs) -> str {
+    auto s = "";
+    auto colon = true;
+    for (@ast::ty_constr c in constrs) {
+        if (colon) { s += " : "; colon = false; } else { s += ", "; }
+        s += ty_constr_to_str(c);
+    }
+    ret s;
+}
+
 //
 // Local Variables:
 // mode: rust
diff --git a/src/comp/syntax/visit.rs b/src/comp/syntax/visit.rs
index 83bf548efee..afb965bb496 100644
--- a/src/comp/syntax/visit.rs
+++ b/src/comp/syntax/visit.rs
@@ -30,7 +30,9 @@ type visitor[E] =
          fn(&@decl, &E, &vt[E])  visit_decl,
          fn(&@expr, &E, &vt[E])  visit_expr,
          fn(&@ty, &E, &vt[E])  visit_ty,
-         fn(&@constr, &E, &vt[E])  visit_constr,
+         // takes the components so that one function can be
+         // generic over constr and ty_constr
+         fn(&path, &span, node_id, &E, &vt[E])  visit_constr,
          fn(&_fn, &ty_param[], &span, &fn_ident, node_id, &E, &vt[E])
              visit_fn);
 
@@ -47,7 +49,7 @@ fn default_visitor[E]() -> visitor[E] {
              visit_decl=bind visit_decl[E](_, _, _),
              visit_expr=bind visit_expr[E](_, _, _),
              visit_ty=bind visit_ty[E](_, _, _),
-             visit_constr=bind visit_constr[E](_, _, _),
+             visit_constr=bind visit_constr[E](_, _, _, _, _),
              visit_fn=bind visit_fn[E](_, _, _, _, _, _, _));
 }
 
@@ -160,7 +162,8 @@ fn visit_ty[E](&@ty t, &E e, &vt[E] v) {
         }
         case (ty_fn(_, ?args, ?out, _, ?constrs)) {
             for (ty_arg a in args) { v.visit_ty(a.node.ty, e, v); }
-            for (@constr c in constrs) { v.visit_constr(c, e, v); }
+            for (@constr c in constrs) { v.visit_constr(c.node.path,
+                                            c.span, c.node.id, e, v); }
             v.visit_ty(out, e, v);
         }
         case (ty_obj(?tmeths)) {
@@ -175,7 +178,12 @@ fn visit_ty[E](&@ty t, &E e, &vt[E] v) {
             for (@ty tp in p.node.types) { v.visit_ty(tp, e, v); }
         }
         case (ty_type)          { /* no-op */ }
-        case (ty_constr(?t, _)) { v.visit_ty(t, e, v); }
+        case (ty_constr(?t, ?cs)) {
+            v.visit_ty(t, e, v);
+            for (@spanned[constr_general_[path, node_id]] tc in cs) {
+                v.visit_constr(tc.node.path, tc.span, tc.node.id, e, v);
+            }
+        }
     }
 }
 
@@ -186,7 +194,7 @@ fn visit_ty_opt[E](&option::t[@ty] ot, &E e, &vt[E] v) {
     }
 }
 
-fn visit_constr[E](&@constr c, &E e, &vt[E] v) {
+fn visit_constr[E](&path operator, &span sp, node_id id, &E e, &vt[E] v) {
     // default
 
 }
@@ -214,7 +222,9 @@ fn visit_native_item[E](&@native_item ni, &E e, &vt[E] v) {
 
 fn visit_fn_decl[E](&fn_decl fd, &E e, &vt[E] v) {
     for (arg a in fd.inputs) { v.visit_ty(a.ty, e, v); }
-    for (@constr c in fd.constraints) { v.visit_constr(c, e, v); }
+    for (@constr c in fd.constraints) {
+        v.visit_constr(c.node.path, c.span, c.node.id, e, v);
+    }
     v.visit_ty(fd.output, e, v);
 }