Make memoize!() a function instead

4 files changed, 192 insertions, 212 deletions

diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs
index e3b6e5e0176..6d5cd6061cf 100644
--- a/src/librustc/lib.rs
+++ b/src/librustc/lib.rs
@@ -29,12 +29,9 @@ This API is completely unstable and subject to change.
       html_root_url = "http://doc.rust-lang.org/nightly/")]
 
 #![allow(deprecated)]
-#![allow(unknown_features)]
-#![feature(macro_rules, globs, struct_variant, quote)]
-#![feature(default_type_params, phase, unsafe_destructor, slicing_syntax)]
-
+#![feature(default_type_params, globs, if_let, import_shadowing, macro_rules, phase, quote)]
+#![feature(slicing_syntax, struct_variant, unsafe_destructor)]
 #![feature(rustc_diagnostic_macros)]
-#![feature(import_shadowing)]
 
 extern crate arena;
 extern crate debug;
@@ -97,7 +94,6 @@ pub mod middle {
     pub mod intrinsicck;
     pub mod lang_items;
     pub mod liveness;
-    pub mod macros;
     pub mod mem_categorization;
     pub mod pat_util;
     pub mod privacy;
diff --git a/src/librustc/middle/macros.rs b/src/librustc/middle/macros.rs
deleted file mode 100644
index 3d38e0fd5ed..00000000000
--- a/src/librustc/middle/macros.rs
+++ /dev/null
@@ -1,71 +0,0 @@
-// Copyright 2014 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-#![macro_escape]
-
-macro_rules! memoize_expand_block(
-    ($cache_map:expr, $cache_key:expr, $($param_name:ident: $param_ty:ty),*) => { {
-        match ($cache_map).borrow().find(&$cache_key) {
-            Some(ref result) => return (*result).clone(),
-            None => {}
-        }
-        let result = inner($($param_name), *);
-        ($cache_map).borrow_mut().insert($cache_key, result.clone());
-        result
-    } }
-)
-
-/// Memoizes a function using a cache that is available by evaluating the
-/// `$cache_map` exression in the context of the function's arguments.
-/// `$cache_key` is the expression that will be used to compute the cache key
-/// for each function invocation.
-///
-/// The macro assumes the cache to be a RefCell containing a HashMap,
-/// which is in practice how most caching in rustc is currently carried out.
-///
-/// # Example
-///
-/// ```
-/// struct Context {
-///     fibonacci_cache: RefCell<HashMap<uint, uint>>
-/// }
-///
-/// memoize!(context.fibonacci_cache, n,
-/// fn fibonacci(context: &Context, n: uint) -> uint {
-///     match n {
-///         0 | 1 => n,
-///         _ => fibonacci(n - 2) + fibonacci(n - 1)
-///     }
-/// }
-/// )
-/// ```
-macro_rules! memoize(
-    ($cache_map:expr, $cache_key:expr,
-        fn $name:ident(
-            $($param_name:ident: $param_ty:ty),*
-        ) -> $output_ty:ty $block:block
-    ) => {
-        fn $name($($param_name: $param_ty), *) -> $output_ty {
-            fn inner($($param_name: $param_ty), *) -> $output_ty $block
-            memoize_expand_block!($cache_map, $cache_key, $($param_name: $param_ty), *)
-        }
-    };
-
-    ($cache_map:expr, $cache_key:expr,
-        pub fn $name:ident(
-            $($param_name:ident: $param_ty:ty),*
-        ) -> $output_ty:ty $block:block
-    ) => {
-        pub fn $name($($param_name: $param_ty), *) -> $output_ty {
-            fn inner($($param_name: $param_ty), *) -> $output_ty $block
-            memoize_expand_block!($cache_map, $cache_key, $($param_name: $param_ty), *)
-        }
-    }
-)
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 21d65c1e8ee..06d36230068 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -33,7 +33,7 @@ use middle;
 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_string};
 use util::ppaux::{trait_store_to_string, ty_to_string};
 use util::ppaux::{Repr, UserString};
-use util::common::{indenter};
+use util::common::{indenter, memoized, memoized_with_key};
 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet, FnvHashMap};
 
 use std::cell::{Cell, RefCell};
@@ -2117,37 +2117,37 @@ pub fn type_needs_drop(cx: &ctxt, ty: t) -> bool {
 // task can free them all at once later. Currently only things
 // that only contain scalars and shared boxes can avoid unwind
 // cleanups.
-memoize!(cx.needs_unwind_cleanup_cache, ty,
-fn type_needs_unwind_cleanup_(cx: &ctxt, ty: t, tycache: &mut HashSet<t>) -> bool {
-    // Prevent infinite recursion
-    if !tycache.insert(ty) {
-        return false;
-    }
-
-    let mut needs_unwind_cleanup = false;
-    maybe_walk_ty(ty, |ty| {
-        needs_unwind_cleanup |= match get(ty).sty {
-            ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) |
-            ty_float(_) | ty_tup(_) | ty_ptr(_) => false,
-
-            ty_enum(did, ref substs) =>
-                enum_variants(cx, did).iter().any(|v|
-                    v.args.iter().any(|aty| {
-                        let t = aty.subst(cx, substs);
-                        type_needs_unwind_cleanup_(cx, t, tycache)
-                    })
-                ),
-
-            _ => true
-        };
-        !needs_unwind_cleanup
+pub fn type_needs_unwind_cleanup(cx: &ctxt, ty: t) -> bool {
+    return memoized(&cx.needs_unwind_cleanup_cache, ty, |ty| {
+        type_needs_unwind_cleanup_(cx, ty, &mut HashSet::new())
     });
-    needs_unwind_cleanup
-}
-)
 
-pub fn type_needs_unwind_cleanup(cx: &ctxt, ty: t) -> bool {
-    type_needs_unwind_cleanup_(cx, ty, &mut HashSet::new())
+    fn type_needs_unwind_cleanup_(cx: &ctxt, ty: t, tycache: &mut HashSet<t>) -> bool {
+        // Prevent infinite recursion
+        if !tycache.insert(ty) {
+            return false;
+        }
+
+        let mut needs_unwind_cleanup = false;
+        maybe_walk_ty(ty, |ty| {
+            needs_unwind_cleanup |= match get(ty).sty {
+                ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) |
+                ty_float(_) | ty_tup(_) | ty_ptr(_) => false,
+
+                ty_enum(did, ref substs) =>
+                    enum_variants(cx, did).iter().any(|v|
+                        v.args.iter().any(|aty| {
+                            let t = aty.subst(cx, substs);
+                            type_needs_unwind_cleanup_(cx, t, tycache)
+                        })
+                    ),
+
+                _ => true
+            };
+            !needs_unwind_cleanup
+        });
+        needs_unwind_cleanup
+    }
 }
 
 /**
@@ -2342,9 +2342,10 @@ pub fn type_interior_is_unsafe(cx: &ctxt, t: ty::t) -> bool {
     type_contents(cx, t).interior_unsafe()
 }
 
-memoize!(cx.tc_cache, type_id(ty),
 pub fn type_contents(cx: &ctxt, ty: t) -> TypeContents {
-    return tc_ty(cx, ty, &mut HashMap::new());
+    return memoized_with_key(&cx.tc_cache, ty, |ty| {
+        tc_ty(cx, ty, &mut HashMap::new())
+    }, |&ty| type_id(ty));
 
     fn tc_ty(cx: &ctxt,
              ty: t,
@@ -2659,7 +2660,6 @@ pub fn type_contents(cx: &ctxt, ty: t) -> TypeContents {
         }
     }
 }
-)
 
 pub fn type_moves_by_default(cx: &ctxt, ty: t) -> bool {
     type_contents(cx, ty).moves_by_default(cx)
@@ -4008,23 +4008,23 @@ pub fn impl_or_trait_item(cx: &ctxt, id: ast::DefId) -> ImplOrTraitItem {
 
 /// Returns true if the given ID refers to an associated type and false if it
 /// refers to anything else.
-memoize!(cx.associated_types, id,
 pub fn is_associated_type(cx: &ctxt, id: ast::DefId) -> bool {
-    if id.krate == ast::LOCAL_CRATE {
-        match cx.impl_or_trait_items.borrow().find(&id) {
-            Some(ref item) => {
-                match **item {
-                    TypeTraitItem(_) => true,
-                    MethodTraitItem(_) => false,
+    memoized(&cx.associated_types, id, |id: ast::DefId| {
+        if id.krate == ast::LOCAL_CRATE {
+            match cx.impl_or_trait_items.borrow().find(&id) {
+                Some(ref item) => {
+                    match **item {
+                        TypeTraitItem(_) => true,
+                        MethodTraitItem(_) => false,
+                    }
                 }
+                None => false,
             }
-            None => false,
+        } else {
+            csearch::is_associated_type(&cx.sess.cstore, id)
         }
-    } else {
-        csearch::is_associated_type(&cx.sess.cstore, id)
-    }
+    })
 }
-)
 
 /// Returns the parameter index that the given associated type corresponds to.
 pub fn associated_type_parameter_index(cx: &ctxt,
@@ -4080,31 +4080,31 @@ pub fn trait_item_def_ids(cx: &ctxt, id: ast::DefId)
     })
 }
 
-memoize!(cx.impl_trait_cache, id,
 pub fn impl_trait_ref(cx: &ctxt, id: ast::DefId) -> Option<Rc<TraitRef>> {
-    if id.krate == ast::LOCAL_CRATE {
-        debug!("(impl_trait_ref) searching for trait impl {:?}", id);
-        match cx.map.find(id.node) {
-            Some(ast_map::NodeItem(item)) => {
-                match item.node {
-                    ast::ItemImpl(_, ref opt_trait, _, _) => {
-                        match opt_trait {
-                            &Some(ref t) => {
-                                Some(ty::node_id_to_trait_ref(cx, t.ref_id))
+    memoized(&cx.impl_trait_cache, id, |id: ast::DefId| {
+        if id.krate == ast::LOCAL_CRATE {
+            debug!("(impl_trait_ref) searching for trait impl {:?}", id);
+            match cx.map.find(id.node) {
+                Some(ast_map::NodeItem(item)) => {
+                    match item.node {
+                        ast::ItemImpl(_, ref opt_trait, _, _) => {
+                            match opt_trait {
+                                &Some(ref t) => {
+                                    Some(ty::node_id_to_trait_ref(cx, t.ref_id))
+                                }
+                                &None => None
                             }
-                            &None => None
                         }
+                        _ => None
                     }
-                    _ => None
                 }
+                _ => None
             }
-            _ => None
+        } else {
+            csearch::get_impl_trait(cx, id)
         }
-    } else {
-        csearch::get_impl_trait(cx, id)
-    }
+    })
 }
-)
 
 pub fn trait_ref_to_def_id(tcx: &ctxt, tr: &ast::TraitRef) -> ast::DefId {
     let def = *tcx.def_map.borrow()
@@ -4288,66 +4288,67 @@ pub fn type_is_empty(cx: &ctxt, t: t) -> bool {
      }
 }
 
-memoize!(cx.enum_var_cache, id,
 pub fn enum_variants(cx: &ctxt, id: ast::DefId) -> Rc<Vec<Rc<VariantInfo>>> {
-    if ast::LOCAL_CRATE != id.krate {
-        Rc::new(csearch::get_enum_variants(cx, id))
-    } else {
-        /*
-          Although both this code and check_enum_variants in typeck/check
-          call eval_const_expr, it should never get called twice for the same
-          expr, since check_enum_variants also updates the enum_var_cache
-         */
-        match cx.map.get(id.node) {
-            ast_map::NodeItem(ref item) => {
-                match item.node {
-                    ast::ItemEnum(ref enum_definition, _) => {
-                        let mut last_discriminant: Option<Disr> = None;
-                        Rc::new(enum_definition.variants.iter().map(|variant| {
-
-                            let mut discriminant = match last_discriminant {
-                                Some(val) => val + 1,
-                                None => INITIAL_DISCRIMINANT_VALUE
-                            };
-
-                            match variant.node.disr_expr {
-                                Some(ref e) => match const_eval::eval_const_expr_partial(cx, &**e) {
-                                    Ok(const_eval::const_int(val)) => {
-                                        discriminant = val as Disr
-                                    }
-                                    Ok(const_eval::const_uint(val)) => {
-                                        discriminant = val as Disr
-                                    }
-                                    Ok(_) => {
-                                        cx.sess
-                                          .span_err(e.span,
-                                                    "expected signed integer constant");
-                                    }
-                                    Err(ref err) => {
-                                        cx.sess
-                                          .span_err(e.span,
-                                                    format!("expected constant: {}",
-                                                            *err).as_slice());
-                                    }
-                                },
-                                None => {}
-                            };
-
-                            last_discriminant = Some(discriminant);
-                            Rc::new(VariantInfo::from_ast_variant(cx, &**variant,
-                                                                  discriminant))
-                        }).collect())
-                    }
-                    _ => {
-                        cx.sess.bug("enum_variants: id not bound to an enum")
+    memoized(&cx.enum_var_cache, id, |id: ast::DefId| {
+        if ast::LOCAL_CRATE != id.krate {
+            Rc::new(csearch::get_enum_variants(cx, id))
+        } else {
+            /*
+              Although both this code and check_enum_variants in typeck/check
+              call eval_const_expr, it should never get called twice for the same
+              expr, since check_enum_variants also updates the enum_var_cache
+             */
+            match cx.map.get(id.node) {
+                ast_map::NodeItem(ref item) => {
+                    match item.node {
+                        ast::ItemEnum(ref enum_definition, _) => {
+                            let mut last_discriminant: Option<Disr> = None;
+                            Rc::new(enum_definition.variants.iter().map(|variant| {
+
+                                let mut discriminant = match last_discriminant {
+                                    Some(val) => val + 1,
+                                    None => INITIAL_DISCRIMINANT_VALUE
+                                };
+
+                                match variant.node.disr_expr {
+                                    Some(ref e) =>
+                                        match const_eval::eval_const_expr_partial(cx, &**e) {
+                                            Ok(const_eval::const_int(val)) => {
+                                                discriminant = val as Disr
+                                            }
+                                            Ok(const_eval::const_uint(val)) => {
+                                                discriminant = val as Disr
+                                            }
+                                            Ok(_) => {
+                                                cx.sess
+                                                  .span_err(e.span,
+                                                            "expected signed integer constant");
+                                            }
+                                            Err(ref err) => {
+                                                cx.sess
+                                                  .span_err(e.span,
+                                                            format!("expected constant: {}",
+                                                                    *err).as_slice());
+                                            }
+                                        },
+                                    None => {}
+                                };
+
+                                last_discriminant = Some(discriminant);
+                                Rc::new(VariantInfo::from_ast_variant(cx, &**variant,
+                                                                      discriminant))
+                            }).collect())
+                        }
+                        _ => {
+                            cx.sess.bug("enum_variants: id not bound to an enum")
+                        }
                     }
                 }
+                _ => cx.sess.bug("enum_variants: id not bound to an enum")
             }
-            _ => cx.sess.bug("enum_variants: id not bound to an enum")
         }
-    }
+    })
 }
-)
 
 // Returns information about the enum variant with the given ID:
 pub fn enum_variant_with_id(cx: &ctxt,
@@ -4372,12 +4373,12 @@ pub fn lookup_item_type(cx: &ctxt,
 }
 
 /// Given the did of a trait, returns its canonical trait ref.
-memoize!(cx.trait_defs, did,
-pub fn lookup_trait_def(cx: &ctxt, did: ast::DefId) -> Rc<ty::TraitDef> {
-    assert!(did.krate != ast::LOCAL_CRATE);
-    Rc::new(csearch::get_trait_def(cx, did))
+pub fn lookup_trait_def(cx: &ctxt, did: DefId) -> Rc<ty::TraitDef> {
+    memoized(&cx.trait_defs, did, |did: DefId| {
+        assert!(did.krate != ast::LOCAL_CRATE);
+        Rc::new(csearch::get_trait_def(cx, did))
+    })
 }
-)
 
 /// Given a reference to a trait, returns the bounds declared on the
 /// trait, with appropriate substitutions applied.
@@ -4436,21 +4437,21 @@ pub fn lookup_simd(tcx: &ctxt, did: DefId) -> bool {
 }
 
 /// Obtain the representation annotation for a struct definition.
-memoize!(tcx.repr_hint_cache, did,
 pub fn lookup_repr_hints(tcx: &ctxt, did: DefId) -> Rc<Vec<attr::ReprAttr>> {
-    Rc::new(if did.krate == LOCAL_CRATE {
-        let mut acc = Vec::new();
-        ty::each_attr(tcx, did, |meta| {
-            acc.extend(attr::find_repr_attrs(tcx.sess.diagnostic(),
-                                             meta).into_iter());
-            true
-        });
-        acc
-    } else {
-        csearch::get_repr_attrs(&tcx.sess.cstore, did)
+    memoized(&tcx.repr_hint_cache, did, |did: DefId| {
+        Rc::new(if did.krate == LOCAL_CRATE {
+            let mut acc = Vec::new();
+            ty::each_attr(tcx, did, |meta| {
+                acc.extend(attr::find_repr_attrs(tcx.sess.diagnostic(),
+                                                 meta).into_iter());
+                true
+            });
+            acc
+        } else {
+            csearch::get_repr_attrs(&tcx.sess.cstore, did)
+        })
     })
 }
-)
 
 // Look up a field ID, whether or not it's local
 // Takes a list of type substs in case the struct is generic
diff --git a/src/librustc/util/common.rs b/src/librustc/util/common.rs
index c39f011189a..8ea9015c05d 100644
--- a/src/librustc/util/common.rs
+++ b/src/librustc/util/common.rs
@@ -1,4 +1,4 @@
-// Copyright 2012 The Rust Project Developers. See the COPYRIGHT
+// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
 // http://rust-lang.org/COPYRIGHT.
 //
@@ -10,8 +10,9 @@
 
 #![allow(non_camel_case_types)]
 
-use std::hash::{Hash, Hasher};
+use std::cell::RefCell;
 use std::collections::HashMap;
+use std::hash::{Hash, Hasher};
 use syntax::ast;
 use syntax::visit;
 use syntax::visit::Visitor;
@@ -155,3 +156,56 @@ pub fn can_reach<S,H:Hasher<S>,T:Eq+Clone+Hash<S>>(
     }
     return false;
 }
+
+/// Memoizes a one-argument closure using the given RefCell containing
+/// a type implementing MutableMap to serve as a cache.
+///
+/// In the future the signature of this function is expected to be:
+/// ```
+/// pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>(
+///    cache: &RefCell<M>,
+///    f: &|&: T| -> U
+/// ) -> impl |&: T| -> U {
+/// ```
+/// but currently it is not possible.
+///
+/// # Example
+/// ```
+/// struct Context {
+///    cache: RefCell<HashMap<uint, uint>>
+/// }
+///
+/// fn factorial(ctxt: &Context, n: uint) -> uint {
+///     memoized(&ctxt.cache, n, |n| match n {
+///         0 | 1 => n,
+///         _ => factorial(ctxt, n - 2) + factorial(ctxt, n - 1)
+///     })
+/// }
+/// ```
+#[inline(always)]
+pub fn memoized<T: Clone, U: Clone, M: MutableMap<T, U>>(
+    cache: &RefCell<M>,
+    arg: T,
+    f: |T| -> U
+) -> U {
+    memoized_with_key(cache, arg, f, |arg| arg.clone())
+}
+
+#[inline(always)]
+pub fn memoized_with_key<T, K, U: Clone, M: MutableMap<K, U>>(
+    cache: &RefCell<M>,
+    arg: T,
+    f: |T| -> U,
+    k: |&T| -> K
+) -> U {
+    let key = k(&arg);
+    let result = cache.borrow().find(&key).map(|result| result.clone());
+    match result {
+        Some(result) => result,
+        None => {
+            let result = f(arg);
+            cache.borrow_mut().insert(key, result.clone());
+            result
+        }
+    }
+}