Backport r59480.
Fix issue #1313119.
diff --git a/Lib/test/test_urlparse.py b/Lib/test/test_urlparse.py
index 5cee458..dcb89f7 100644
--- a/Lib/test/test_urlparse.py
+++ b/Lib/test/test_urlparse.py
@@ -287,6 +287,16 @@
         self.assertEqual(p.port, None)
         self.assertEqual(p.geturl(), uri)
 
+    def test_caching(self):
+        # Test case for bug #1313119
+        uri = "http://example.com/doc/"
+        unicode_uri = unicode(uri)
+
+        urlparse.urlparse(unicode_uri)
+        p = urlparse.urlparse(uri)
+        self.assertEqual(type(p.scheme), type(uri))
+        self.assertEqual(type(p.hostname), type(uri))
+        self.assertEqual(type(p.path), type(uri))
 
 def test_main():
     test_support.run_unittest(UrlParseTestCase)
diff --git a/Lib/urlparse.py b/Lib/urlparse.py
index eade040..ad5d75f 100644
--- a/Lib/urlparse.py
+++ b/Lib/urlparse.py
@@ -184,7 +184,7 @@
     Note that we don't break the components up in smaller bits
     (e.g. netloc is a single string) and we don't expand % escapes."""
     allow_fragments = bool(allow_fragments)
-    key = url, scheme, allow_fragments
+    key = url, scheme, allow_fragments, type(url), type(scheme)
     cached = _parse_cache.get(key, None)
     if cached:
         return cached