One last refactoring of the import handling:

* Create an import resolving stage. Currently this involves a copy of the ast,
  we can probably revisit this once we revisit doing full copies of the ast in
  general.

* Don't repeat work. Once we resolve a import, put it on a hash table and use
  it next time we are asked for it. This solves a O(n^2) behaviour in
  degenerated cases.

* Once import resolution is done, the target of an import is stored on the
  import itself.

4 files changed, 121 insertions, 88 deletions

diff --git a/src/comp/front/ast.rs b/src/comp/front/ast.rs
index 1ee50c2a..1fad1c1a 100644
--- a/src/comp/front/ast.rs
+++ b/src/comp/front/ast.rs
@@ -229,7 +229,7 @@ type variant = rec(str name, vec[variant_arg] args, def_id id, ann ann);
 type view_item = spanned[view_item_];
 tag view_item_ {
     view_item_use(ident, vec[@meta_item], def_id);
-    view_item_import(vec[ident], def_id);
+    view_item_import(vec[ident], def_id, option.t[def]);
 }
 
 type item = spanned[item_];
@@ -247,7 +247,7 @@ fn index_view_item(mod_index index, @view_item it) {
         case(ast.view_item_use(?id, _, _)) {
             index.insert(id, ast.mie_view_item(it));
         }
-        case(ast.view_item_import(?ids,_)) {
+        case(ast.view_item_import(?ids,_,_)) {
             auto len = _vec.len[ast.ident](ids);
             auto last_id = ids.(len - 1u);
             index.insert(last_id, ast.mie_view_item(it));
diff --git a/src/comp/front/parser.rs b/src/comp/front/parser.rs
index c44da8f1..0e8d1dc7 100644
--- a/src/comp/front/parser.rs
+++ b/src/comp/front/parser.rs
@@ -1704,7 +1704,8 @@ impure fn parse_rest_import_name(parser p, ast.ident id) -> @ast.view_item {
         identifiers += i;
     }
     p.bump();
-    auto import_decl = ast.view_item_import(identifiers, p.next_def_id());
+    auto import_decl = ast.view_item_import(identifiers, p.next_def_id(),
+                                            none[ast.def]);
     ret @spanned(lo, hi, import_decl);
 }
 
diff --git a/src/comp/middle/fold.rs b/src/comp/middle/fold.rs
index b96ca938..f81b7a52 100644
--- a/src/comp/middle/fold.rs
+++ b/src/comp/middle/fold.rs
@@ -210,7 +210,7 @@ type ast_fold[ENV] =
          def_id id) -> @view_item)                fold_view_item_use,
 
      (fn(&ENV e, &span sp, vec[ident] idents,
-         def_id id) -> @view_item)                fold_view_item_import,
+         def_id id, option.t[def]) -> @view_item) fold_view_item_import,
 
      // Additional nodes.
      (fn(&ENV e, &span sp,
@@ -705,9 +705,10 @@ fn fold_view_item[ENV](&ENV env, ast_fold[ENV] fld, @view_item vi)
             ret fld.fold_view_item_use(env_, vi.span, ident, meta_items,
                                        def_id);
         }
-        case (ast.view_item_import(?idents, ?def_id)) {
+        case (ast.view_item_import(?idents, ?def_id, ?target_def)) {
             // FIXME: what other folding should be done in here?
-            ret fld.fold_view_item_import(env_, vi.span, idents, def_id);
+            ret fld.fold_view_item_import(env_, vi.span, idents, def_id,
+                                          target_def);
         }
     }
 
@@ -1086,8 +1087,9 @@ fn identity_fold_view_item_use[ENV](&ENV e, &span sp, ident i,
 }
 
 fn identity_fold_view_item_import[ENV](&ENV e, &span sp, vec[ident] is,
-                                       def_id id) -> @view_item {
-    ret @respan(sp, ast.view_item_import(is, id));
+                                       def_id id, option.t[def] target_def)
+    -> @view_item {
+    ret @respan(sp, ast.view_item_import(is, id, target_def));
 }
 
 // Additional identities.
@@ -1236,7 +1238,7 @@ fn new_identity_fold[ENV]() -> ast_fold[ENV] {
          fold_view_item_use =
              bind identity_fold_view_item_use[ENV](_,_,_,_,_),
          fold_view_item_import =
-             bind identity_fold_view_item_import[ENV](_,_,_,_),
+             bind identity_fold_view_item_import[ENV](_,_,_,_,_),
 
          fold_block = bind identity_fold_block[ENV](_,_,_),
          fold_fn = bind identity_fold_fn[ENV](_,_,_,_,_),
diff --git a/src/comp/middle/resolve.rs b/src/comp/middle/resolve.rs
index 2ea3fa0a..7d4def49 100644
--- a/src/comp/middle/resolve.rs
+++ b/src/comp/middle/resolve.rs
@@ -25,7 +25,7 @@ tag scope {
 type env = rec(list[scope] scopes,
                session.session sess);
 
-type import_map = std.map.hashmap[ast.def_id,def];
+type import_map = std.map.hashmap[ast.def_id,def_wrap];
 
 // A simple wrapper over defs that stores a bit more information about modules
 // and uses so that we can use the regular lookup_name when resolving imports.
@@ -34,68 +34,74 @@ tag def_wrap {
     def_wrap_import(@ast.view_item);
     def_wrap_mod(@ast.item);
     def_wrap_other(def);
+    def_wrap_resolving;
 }
 
-fn lookup_name(&env e, import_map index,
-               ast.ident i) -> option.t[def] {
-    auto d_ = lookup_name_wrapped(e, i);
-    alt (d_) {
-        case (none[tup(@env, def_wrap)]) {
-            ret none[def];
-        }
-        case (some[tup(@env, def_wrap)](?d)) {
-            alt (d._1) {
-                case (def_wrap_use(?it)) {
-                    alt (it.node) {
-                        case (ast.view_item_use(_, _, ?id)) {
-                            ret some[def](ast.def_use(id));
-                        }
-                    }
+fn unwrap_def(def_wrap d) -> def {
+    alt (d) {
+        case (def_wrap_use(?it)) {
+            alt (it.node) {
+                case (ast.view_item_use(_, _, ?id)) {
+                    ret ast.def_use(id);
                 }
-                case (def_wrap_import(?it)) {
-                    alt (it.node) {
-                        case (ast.view_item_import(_, ?id)) {
-                            ret index.find(id);
+            }
+        }
+        case (def_wrap_import(?it)) {
+            alt (it.node) {
+                case (ast.view_item_import(_, ?id, ?target_def)) {
+                    alt (target_def) {
+                        case (some[def](?d)) {
+                            ret d;
                         }
-                    }
-                }
-                case (def_wrap_mod(?i)) {
-                    alt (i.node) {
-                        case (ast.item_mod(_, _, ?id)) {
-                            ret some[def](ast.def_mod(id));
+                        case (none[def]) {
+                            fail;
                         }
                     }
                 }
-                case (def_wrap_other(?d)) {
-                    ret some[def](d);
+            }
+        }
+        case (def_wrap_mod(?m)) {
+            alt (m.node) {
+                case (ast.item_mod(_, _, ?id)) {
+                    ret ast.def_mod(id);
                 }
             }
         }
+        case (def_wrap_other(?d)) {
+            ret d;
+        }
+    }
+}
+
+fn lookup_name(&env e, ast.ident i) -> option.t[def] {
+    auto d_ = lookup_name_wrapped(e, i);
+    alt (d_) {
+        case (none[tup(@env, def_wrap)]) {
+            ret none[def];
+        }
+        case (some[tup(@env, def_wrap)](?d)) {
+            ret some(unwrap_def(d._1));
+        }
     }
 }
 
 // Follow the path of an import and return what it ultimately points to.
 
-fn find_final_def(&env e, &span sp, vec[ident] idents) -> def_wrap {
+fn find_final_def(&env e, import_map index,
+                  &span sp, vec[ident] idents,
+                  ast.def_id import_id) -> def_wrap {
 
     // We are given a series of identifiers (a.b.c.d) and we know that
     // in the environment 'e' the identifier 'a' was resolved to 'd'. We
     // should return what a.b.c.d points to in the end.
-    fn found_something(&env e, std.map.hashmap[ast.def_id, bool] pending,
+    fn found_something(&env e, import_map index,
                        &span sp, vec[ident] idents, def_wrap d) -> def_wrap {
         alt (d) {
             case (def_wrap_import(?imp)) {
                 alt (imp.node) {
-                    case (ast.view_item_import(?new_idents, ?d)) {
-                        if (pending.contains_key(d)) {
-                            e.sess.span_err(sp,
-                                            "cyclic import");
-                            fail;
-                        }
-                        pending.insert(d, true);
-                        auto x = inner(e, pending, sp, new_idents);
-                        pending.remove(d);
-                        ret found_something(e, pending, sp, idents, x);
+                    case (ast.view_item_import(?new_idents, ?d, _)) {
+                        auto x = inner(e, index, sp, new_idents, d);
+                        ret found_something(e, index, sp, idents, x);
                     }
                 }
             }
@@ -121,7 +127,7 @@ fn find_final_def(&env e, &span sp, vec[ident] idents) -> def_wrap {
                     }
                     case (some[tup(@env, def_wrap)](?next)) {
                         auto combined_e = update_env_for_item(e, i);
-                        ret found_something(combined_e, pending, sp,
+                        ret found_something(combined_e, index, sp,
                                             rest_idents, next._1);
                     }
                 }
@@ -136,9 +142,26 @@ fn find_final_def(&env e, &span sp, vec[ident] idents) -> def_wrap {
         }
         fail;
     }
-    fn inner(&env e, std.map.hashmap[ast.def_id, bool] pending,
-             &span sp, vec[ident] idents) -> def_wrap {
+
+    fn inner(&env e, import_map index, &span sp, vec[ident] idents,
+             ast.def_id import_id) -> def_wrap {
+        alt (index.find(import_id)) {
+            case (some[def_wrap](?x)) {
+                alt (x) {
+                    case (def_wrap_resolving) {
+                        e.sess.span_err(sp, "cyclic import");
+                        fail;
+                    }
+                    case (_) {
+                        ret x;
+                    }
+                }
+            }
+            case (none[def_wrap]) {
+            }
+        }
         auto first = idents.(0);
+        index.insert(import_id, def_wrap_resolving);
         auto d_ = lookup_name_wrapped(e, first);
         alt (d_) {
             case (none[tup(@env, def_wrap)]) {
@@ -146,12 +169,13 @@ fn find_final_def(&env e, &span sp, vec[ident] idents) -> def_wrap {
                 fail;
             }
             case (some[tup(@env, def_wrap)](?d)) {
-                ret found_something(*d._0, pending, sp, idents, d._1);
+                auto x = found_something(*d._0, index, sp, idents, d._1);
+                index.insert(import_id, x);
+                ret x;
             }
         }
     }
-    auto pending = new_def_hash[bool]();
-    ret inner(e, pending, sp, idents);
+    ret inner(e, index, sp, idents, import_id);
 }
 
 fn lookup_name_wrapped(&env e, ast.ident i) -> option.t[tup(@env, def_wrap)] {
@@ -203,7 +227,7 @@ fn lookup_name_wrapped(&env e, ast.ident i) -> option.t[tup(@env, def_wrap)] {
             case (ast.view_item_use(_, _, ?id)) {
                 ret def_wrap_use(i);
             }
-            case (ast.view_item_import(?idents,?d)) {
+            case (ast.view_item_import(?idents,?d, _)) {
                 ret def_wrap_import(i);
             }
         }
@@ -327,11 +351,11 @@ fn lookup_name_wrapped(&env e, ast.ident i) -> option.t[tup(@env, def_wrap)] {
     }
 }
 
-fn fold_pat_tag(&env e, &span sp, import_map index, ident i,
-                vec[@ast.pat] args, option.t[ast.variant_def] old_def,
+fn fold_pat_tag(&env e, &span sp, ident i, vec[@ast.pat] args,
+                option.t[ast.variant_def] old_def,
                 ann a) -> @ast.pat {
     auto new_def;
-    alt (lookup_name(e, index, i)) {
+    alt (lookup_name(e, i)) {
         case (some[def](?d)) {
             alt (d) {
                 case (ast.def_variant(?did, ?vid)) {
@@ -372,8 +396,8 @@ fn fold_pat_tag(&env e, &span sp, import_map index, ident i,
 // and split that off as the 'primary' expr_path, with secondary expr_field
 // expressions tacked on the end.
 
-fn fold_expr_path(&env e, &span sp, import_map index,
-                  &ast.path p, &option.t[def] d, ann a) -> @ast.expr {
+fn fold_expr_path(&env e, &span sp, &ast.path p, &option.t[def] d,
+                  ann a) -> @ast.expr {
 
     if (_vec.len[@ast.ty](p.node.types) > 0u) {
         e.sess.unimpl("resolving name expr with ty params");
@@ -384,7 +408,7 @@ fn fold_expr_path(&env e, &span sp, import_map index,
     check (n_idents != 0u);
     auto id0 = p.node.idents.(0);
 
-    auto d_ = lookup_name(e, index, id0);
+    auto d_ = lookup_name(e, id0);
 
     alt (d_) {
         case (some[def](_)) {
@@ -413,30 +437,19 @@ fn fold_expr_path(&env e, &span sp, import_map index,
 
 fn fold_view_item_import(&env e, &span sp,
                          import_map index,
-                         vec[ident] is, ast.def_id id) -> @ast.view_item {
+                         vec[ident] is, ast.def_id id,
+                         option.t[def] target_id) -> @ast.view_item {
     // Produce errors for invalid imports
     auto len = _vec.len[ast.ident](is);
     auto last_id = is.(len - 1u);
-    auto d = find_final_def(e, sp, is);
-    alt (d) {
-        case (def_wrap_mod(?m)) {
-            alt (m.node) {
-                case (ast.item_mod(_, _, ?id)) {
-                    index.insert(id, ast.def_mod(id));
-                }
-            }
-        }
-        case (def_wrap_other(?target_def)) {
-            index.insert(id, target_def);
-        }
-    }
-
-    ret @fold.respan[ast.view_item_](sp, ast.view_item_import(is, id));
+    auto d = find_final_def(e, index, sp, is, id);
+    let option.t[def] target_def = some(unwrap_def(d));
+    ret @fold.respan[ast.view_item_](sp, ast.view_item_import(is, id,
+                                                              target_def));
 }
 
 
-fn fold_ty_path(&env e, &span sp, import_map index, ast.path p,
-                &option.t[def] d) -> @ast.ty {
+fn fold_ty_path(&env e, &span sp, ast.path p, &option.t[def] d) -> @ast.ty {
 
     let uint len = _vec.len[ast.ident](p.node.idents);
     check (len != 0u);
@@ -448,7 +461,7 @@ fn fold_ty_path(&env e, &span sp, import_map index, ast.path p,
         e.sess.unimpl("resolving path ty with ty params");
     }
 
-    auto d_ = lookup_name(e, index, p.node.idents.(0));
+    auto d_ = lookup_name(e, p.node.idents.(0));
 
     alt (d_) {
         case (some[def](?d)) {
@@ -478,16 +491,33 @@ fn update_env_for_arm(&env e, &ast.arm p) -> env {
     ret rec(scopes = cons[scope](scope_arm(p), @e.scopes) with e);
 }
 
+fn resolve_imports(session.session sess, @ast.crate crate) -> @ast.crate {
+    let fold.ast_fold[env] fld = fold.new_identity_fold[env]();
+
+    auto import_index = new_def_hash[def_wrap]();
+    fld = @rec( fold_view_item_import
+                    = bind fold_view_item_import(_,_,import_index,_,_,_),
+                update_env_for_crate = bind update_env_for_crate(_,_),
+                update_env_for_item = bind update_env_for_item(_,_),
+                update_env_for_block = bind update_env_for_block(_,_),
+                update_env_for_arm = bind update_env_for_arm(_,_)
+                with *fld );
+
+    auto e = rec(scopes = nil[scope],
+                 sess = sess);
+
+    ret fold.fold_crate[env](e, fld, crate);
+}
+
 fn resolve_crate(session.session sess, @ast.crate crate) -> @ast.crate {
 
     let fold.ast_fold[env] fld = fold.new_identity_fold[env]();
 
-    auto import_index = new_def_hash[def]();
-    fld = @rec( fold_pat_tag = bind fold_pat_tag(_,_,import_index,_,_,_,_),
-                fold_expr_path = bind fold_expr_path(_,_,import_index,_,_,_),
-                fold_view_item_import
-                    = bind fold_view_item_import(_,_,import_index,_,_),
-                fold_ty_path = bind fold_ty_path(_,_,import_index,_,_),
+    auto new_crate = resolve_imports(sess, crate);
+
+    fld = @rec( fold_pat_tag = bind fold_pat_tag(_,_,_,_,_,_),
+                fold_expr_path = bind fold_expr_path(_,_,_,_,_),
+                fold_ty_path = bind fold_ty_path(_,_,_,_),
                 update_env_for_crate = bind update_env_for_crate(_,_),
                 update_env_for_item = bind update_env_for_item(_,_),
                 update_env_for_block = bind update_env_for_block(_,_),
@@ -497,7 +527,7 @@ fn resolve_crate(session.session sess, @ast.crate crate) -> @ast.crate {
     auto e = rec(scopes = nil[scope],
                  sess = sess);
 
-    ret fold.fold_crate[env](e, fld, crate);
+    ret fold.fold_crate[env](e, fld, new_crate);
 }
 
 // Local Variables: