diff --git a/rust/treedirstate/src/dirstate.rs b/rust/treedirstate/src/dirstate.rs
--- a/rust/treedirstate/src/dirstate.rs
+++ b/rust/treedirstate/src/dirstate.rs
@@ -269,6 +269,10 @@
     pub fn has_removed_dir(&mut self, name: KeyRef) -> Result<bool> {
         self.removed.has_dir(self.store.store_view(), name)
     }
+
+    pub fn clear_filtered_keys(&mut self) {
+        self.tracked.clear_filtered_keys();
+    }
 }
 
 #[cfg(test)]
diff --git a/rust/treedirstate/src/python.rs b/rust/treedirstate/src/python.rs
--- a/rust/treedirstate/src/python.rs
+++ b/rust/treedirstate/src/python.rs
@@ -32,6 +32,7 @@
 py_class!(class RustDirstateMap |py| {
     data repodir: PathBuf;
     data dirstate: RefCell<Dirstate<FileState>>;
+    data casefolderid: RefCell<Option<usize>>;
 
     def __new__(
         _cls,
@@ -43,7 +44,8 @@
         RustDirstateMap::create_instance(
             py,
             repodir.into(),
-            RefCell::new(dirstate))
+            RefCell::new(dirstate),
+            RefCell::new(None))
     }
 
     def clear(&self) -> PyResult<PyObject> {
@@ -357,9 +359,11 @@
     def getcasefoldedtracked(
         &self,
         filename: PyBytes,
-        casefolder: PyObject
+        casefolder: PyObject,
+        casefolderid: usize
     ) -> PyResult<Option<PyObject>> {
         let mut dirstate = self.dirstate(py).borrow_mut();
+        let mut curcasefolderid = self.casefolderid(py).borrow_mut();
         let mut filter = |filename: KeyRef| -> errors::Result<Key> {
             let unfolded = PyBytes::new(py, filename);
             let folded = casefolder.call(py, (unfolded,), None)
@@ -369,6 +373,12 @@
             Ok(folded.data(py).to_vec())
         };
 
+        if let Some(id) = *curcasefolderid {
+            if id != casefolderid {
+                dirstate.clear_filtered_keys();
+            }
+        }
+        *curcasefolderid = Some(casefolderid);
         dirstate
             .get_tracked_filtered_key(filename.data(py), &mut filter)
             .map(|o| o.map(|k| PyBytes::new(py, &k).into_object()))
diff --git a/rust/treedirstate/src/tree.rs b/rust/treedirstate/src/tree.rs
--- a/rust/treedirstate/src/tree.rs
+++ b/rust/treedirstate/src/tree.rs
@@ -49,7 +49,8 @@
 
     /// A map from keys that have been filtered through a case-folding filter function to the
     /// original key.  This is used for case-folded look-ups.  Filtered values are cached, so
-    /// only a single filter function can be used with a tree.
+    /// only a single filter function can be used with a tree.  Call `clear_filtered_keys` to
+    /// clear the cache in order to use a different filter function.
     filtered_keys: Option<VecMap<Key, Key>>,
 }
 
@@ -534,6 +535,17 @@
             )
         }
     }
+
+    fn clear_filtered_keys(&mut self) {
+        self.filtered_keys = None;
+        if let Some(ref mut entries) = self.entries {
+            for (_k, v) in entries.iter_mut() {
+                if let &mut NodeEntry::Directory(ref mut node) = v {
+                    node.clear_filtered_keys();
+                }
+            }
+        }
+    }
 }
 
 impl<T: Storable + Clone> Tree<T> {
@@ -651,6 +663,10 @@
             },
         ))
     }
+
+    pub fn clear_filtered_keys(&mut self) {
+        self.root.clear_filtered_keys();
+    }
 }
 
 #[cfg(test)]
diff --git a/treedirstate/__init__.py b/treedirstate/__init__.py
--- a/treedirstate/__init__.py
+++ b/treedirstate/__init__.py
@@ -71,6 +71,29 @@
         self.writeuint(len(v))
         self.buffer.write(v)
 
+class _overlaydict(dict):
+    def __init__(self, lookup, *args, **kwargs):
+        super(_overlaydict, self).__init__(*args, **kwargs)
+        self.lookup = lookup
+
+    def get(self, key, default=None):
+        s = super(_overlaydict, self)
+        if s.__contains__(key):
+            return s.__getitem__(key)
+        r = self.lookup(key)
+        if r is not None:
+            return r
+        return default
+
+    def __getitem__(self, key):
+        s = super(_overlaydict, self)
+        if s.__contains__(key):
+            return s[key]
+        r = self.lookup(key)
+        if r is not None:
+            return r
+        raise KeyError(key)
+
 # The treedirstatemap iterator uses the getnext method on the dirstatemap
 # to find the next item on each call.  This involves searching down the
 # tree each time.  A future improvement is to keep the state between each
@@ -128,6 +151,8 @@
         self._nonnormalset.clear()
         self._otherparentset.clear()
         self.setparents(node.nullid, node.nullid)
+        util.clearcachedproperty(self, "filefoldmap")
+        util.clearcachedproperty(self, "dirfoldmap")
 
     def __len__(self):
         """Returns the number of files, including removed files."""
@@ -161,7 +186,7 @@
                 self._rmap.getremoved(filename, default))
 
     def getcasefoldedtracked(self, filename, foldfunc):
-        return self._rmap.getcasefoldedtracked(filename, foldfunc)
+        return self._rmap.getcasefoldedtracked(filename, foldfunc, id(foldfunc))
 
     def __getitem__(self, filename):
         item = (self._rmap.gettracked(filename, None) or
@@ -299,18 +324,32 @@
             self._computenonnormals()
         return self._otherparentset
 
-    def getfilefoldmap(self):
+    @util.propertycache
+    def filefoldmap(self):
         """Returns a dictionary mapping normalized case paths to their
         non-normalized versions.
         """
-        raise NotImplementedError()
+        def lookup(key):
+            f = self.getcasefoldedtracked(key, util.normcase)
+            if f is not None and self._rmap.hastrackedfile(f):
+                return f
+            else:
+                return None
+        return _overlaydict(lookup)
 
-    def getdirfoldmap(self):
+    @util.propertycache
+    def dirfoldmap(self):
         """
         Returns a dictionary mapping normalized case paths to their
         non-normalized versions for directories.
         """
-        raise NotImplementedError()
+        def lookup(key):
+            d = self.getcasefoldedtracked(key + '/', util.normcase)
+            if d is not None and self._rmap.hastrackeddir(d):
+                return d.rstrip('/')
+            else:
+                return None
+        return _overlaydict(lookup)
 
     def identity(self):
         if self._identity is None: