Issue #2377: Make importlib the implementation of __import__().

importlib._bootstrap is now frozen into Python/importlib.h and stored
as _frozen_importlib in sys.modules. Py_Initialize() loads the frozen
code along with sys and imp and then uses _frozen_importlib._install()
to set builtins.__import__() w/ _frozen_importlib.__import__().
diff --git a/Lib/importlib/_bootstrap.py b/Lib/importlib/_bootstrap.py
index 7bf07eb..12b4219 100644
--- a/Lib/importlib/_bootstrap.py
+++ b/Lib/importlib/_bootstrap.py
@@ -160,6 +160,13 @@
 
 # Finder/loader utility code ##################################################
 
+def verbose_message(message, *args):
+    """Print the message to stderr if -v/PYTHONVERBOSE is turned on."""
+    if sys.flags.verbose:
+        if not message.startswith('#') and not message.startswith('import '):
+            message = '# ' + message
+        print(message.format(*args), file=sys.stderr)
+
 
 def set_package(fxn):
     """Set __package__ on the returned module."""
@@ -388,9 +395,13 @@
             raise ImportError("bad magic number in {}".format(fullname),
                               name=fullname, path=bytecode_path)
         elif len(raw_timestamp) != 4:
-            raise EOFError("bad timestamp in {}".format(fullname))
+            message = 'bad timestamp in {}'.format(fullname)
+            verbose_message(message)
+            raise EOFError(message)
         elif len(raw_size) != 4:
-            raise EOFError("bad size in {}".format(fullname))
+            message = 'bad size in {}'.format(fullname)
+            verbose_message(message)
+            raise EOFError(message)
         if source_stats is not None:
             try:
                 source_mtime = int(source_stats['mtime'])
@@ -398,9 +409,10 @@
                 pass
             else:
                 if _r_long(raw_timestamp) != source_mtime:
-                    raise ImportError(
-                        "bytecode is stale for {}".format(fullname),
-                        name=fullname, path=bytecode_path)
+                    message = 'bytecode is stale for {}'.format(fullname)
+                    verbose_message(message)
+                    raise ImportError(message, name=fullname,
+                                      path=bytecode_path)
             try:
                 source_size = source_stats['size'] & 0xFFFFFFFF
             except KeyError:
@@ -506,9 +518,13 @@
                     except (ImportError, EOFError):
                         pass
                     else:
+                        verbose_message('{} matches {}', bytecode_path,
+                                        source_path)
                         found = marshal.loads(bytes_data)
                         if isinstance(found, code_type):
                             imp._fix_co_filename(found, source_path)
+                            verbose_message('code object from {}',
+                                            bytecode_path)
                             return found
                         else:
                             msg = "Non-code object in {}"
@@ -517,6 +533,7 @@
         source_bytes = self.get_data(source_path)
         code_object = compile(source_bytes, source_path, 'exec',
                                 dont_inherit=True)
+        verbose_message('code object from {}', source_path)
         if (not sys.dont_write_bytecode and bytecode_path is not None and
             source_mtime is not None):
             # If e.g. Jython ever implements imp.cache_from_source to have
@@ -528,6 +545,7 @@
             data.extend(marshal.dumps(code_object))
             try:
                 self.set_data(bytecode_path, data)
+                verbose_message('wrote {!r}', bytecode_path)
             except NotImplementedError:
                 pass
         return code_object
@@ -596,6 +614,7 @@
                 return
         try:
             _write_atomic(path, data)
+            verbose_message('created {!r}', path)
         except (PermissionError, FileExistsError):
             # Don't worry if you can't write bytecode or someone is writing
             # it at the same time.
@@ -615,6 +634,7 @@
         bytes_data = self._bytes_from_bytecode(fullname, data, path, None)
         found = marshal.loads(bytes_data)
         if isinstance(found, code_type):
+            verbose_message('code object from {!r}', path)
             return found
         else:
             raise ImportError("Non-code object in {}".format(path),
@@ -644,7 +664,9 @@
         """Load an extension module."""
         is_reload = fullname in sys.modules
         try:
-            return imp.load_dynamic(fullname, self._path)
+            module = imp.load_dynamic(fullname, self._path)
+            verbose_message('extension module loaded from {!r}', self._path)
+            return module
         except:
             if not is_reload and fullname in sys.modules:
                 del sys.modules[fullname]
@@ -953,6 +975,7 @@
     elif name not in sys.modules:
         # The parent import may have already imported this module.
         loader.load_module(name)
+        verbose_message('import {!r} # {!r}', name, loader)
     # Backwards-compatibility; be nicer to skip the dict lookup.
     module = sys.modules[name]
     if parent:
diff --git a/Lib/importlib/test/import_/test_path.py b/Lib/importlib/test/import_/test_path.py
index 5713319..a211bdf 100644
--- a/Lib/importlib/test/import_/test_path.py
+++ b/Lib/importlib/test/import_/test_path.py
@@ -87,7 +87,7 @@
 
 class DefaultPathFinderTests(unittest.TestCase):
 
-    """Test importlib._bootstrap._DefaultPathFinder."""
+    """Test _bootstrap._DefaultPathFinder."""
 
     def test_implicit_hooks(self):
         # Test that the implicit path hooks are used.
diff --git a/Lib/importlib/test/import_/util.py b/Lib/importlib/test/import_/util.py
index 649c5ed..86ac065 100644
--- a/Lib/importlib/test/import_/util.py
+++ b/Lib/importlib/test/import_/util.py
@@ -1,6 +1,5 @@
 import functools
 import importlib
-import importlib._bootstrap
 import unittest
 
 
diff --git a/Lib/importlib/test/regrtest.py b/Lib/importlib/test/regrtest.py
index dc0eb97..9cc9ee7 100644
--- a/Lib/importlib/test/regrtest.py
+++ b/Lib/importlib/test/regrtest.py
@@ -13,16 +13,4 @@
 if __name__ == '__main__':
     __builtins__.__import__ = importlib.__import__
 
-    exclude = ['--exclude',
-                'test_frozen', # Does not expect __loader__ attribute
-                'test_pkg',  # Does not expect __loader__ attribute
-                'test_pydoc', # Does not expect __loader__ attribute
-              ]
-
-    # Switching on --exclude implies running all test but the ones listed, so
-    # only use it when one is not running an explicit test
-    if len(sys.argv) == 1:
-        # No programmatic way to specify tests to exclude
-        sys.argv.extend(exclude)
-
     regrtest.main(quiet=True, verbose2=True)
diff --git a/Lib/importlib/test/source/test_file_loader.py b/Lib/importlib/test/source/test_file_loader.py
index cb1c317..710339c 100644
--- a/Lib/importlib/test/source/test_file_loader.py
+++ b/Lib/importlib/test/source/test_file_loader.py
@@ -1,5 +1,5 @@
+from ... import _bootstrap
 import importlib
-from importlib import _bootstrap
 from .. import abc
 from .. import util
 from . import util as source_util
diff --git a/Lib/importlib/test/source/test_finder.py b/Lib/importlib/test/source/test_finder.py
index 68e9ae7..315aa77 100644
--- a/Lib/importlib/test/source/test_finder.py
+++ b/Lib/importlib/test/source/test_finder.py
@@ -1,10 +1,11 @@
-from importlib import _bootstrap
 from .. import abc
 from . import util as source_util
-from test.support import make_legacy_pyc
-import os
+
+from importlib import _bootstrap
 import errno
+import os
 import py_compile
+from test.support import make_legacy_pyc
 import unittest
 import warnings
 
diff --git a/Lib/importlib/test/source/test_path_hook.py b/Lib/importlib/test/source/test_path_hook.py
index 374f7b6..3de822c 100644
--- a/Lib/importlib/test/source/test_path_hook.py
+++ b/Lib/importlib/test/source/test_path_hook.py
@@ -1,5 +1,6 @@
-from importlib import _bootstrap
 from . import util as source_util
+
+from importlib import _bootstrap
 import unittest
 
 
diff --git a/Lib/importlib/test/source/test_source_encoding.py b/Lib/importlib/test/source/test_source_encoding.py
index 794a3df..72a1360 100644
--- a/Lib/importlib/test/source/test_source_encoding.py
+++ b/Lib/importlib/test/source/test_source_encoding.py
@@ -1,6 +1,6 @@
-from importlib import _bootstrap
 from . import util as source_util
 
+from importlib import _bootstrap
 import codecs
 import re
 import sys
@@ -36,7 +36,7 @@
             with open(mapping[self.module_name], 'wb') as file:
                 file.write(source)
             loader = _bootstrap._SourceFileLoader(self.module_name,
-                                       mapping[self.module_name])
+                                                  mapping[self.module_name])
             return loader.load_module(self.module_name)
 
     def create_source(self, encoding):
diff --git a/Lib/importlib/test/util.py b/Lib/importlib/test/util.py
index 93b7cd2..7ba7a97 100644
--- a/Lib/importlib/test/util.py
+++ b/Lib/importlib/test/util.py
@@ -35,7 +35,7 @@
     for name in names:
         if name in ('sys', 'marshal', 'imp'):
             raise ValueError(
-                "cannot uncache {0} as it will break _importlib".format(name))
+                "cannot uncache {0}".format(name))
         try:
             del sys.modules[name]
         except KeyError:
diff --git a/Lib/os.py b/Lib/os.py
index fe6cb11..bd18023 100644
--- a/Lib/os.py
+++ b/Lib/os.py
@@ -42,6 +42,8 @@
     except AttributeError:
         return [n for n in dir(module) if n[0] != '_']
 
+# Any new dependencies of the os module and/or changes in path separator
+# requires updating importlib as well.
 if 'posix' in _names:
     name = 'posix'
     linesep = '\n'
diff --git a/Lib/pydoc.py b/Lib/pydoc.py
index cc22d73..8b94993 100755
--- a/Lib/pydoc.py
+++ b/Lib/pydoc.py
@@ -299,9 +299,8 @@
         elif exc is SyntaxError:
             # A SyntaxError occurred before we could execute the module.
             raise ErrorDuringImport(value.filename, info)
-        elif exc is ImportError and extract_tb(tb)[-1][2]=='safeimport':
-            # The import error occurred directly in this function,
-            # which means there is no such module in the path.
+        elif exc is ImportError and value.name == path:
+            # No such module in the path.
             return None
         else:
             # Some other error occurred during the importing process.
diff --git a/Lib/site.py b/Lib/site.py
index b83498e..c289f56 100644
--- a/Lib/site.py
+++ b/Lib/site.py
@@ -81,7 +81,8 @@
 def abs_paths():
     """Set all module __file__ and __cached__ attributes to an absolute path"""
     for m in set(sys.modules.values()):
-        if hasattr(m, '__loader__'):
+        if (getattr(getattr(m, '__loader__', None), '__module__', None) !=
+                '_frozen_importlib'):
             continue   # don't mess with a PEP 302-supplied __file__
         try:
             m.__file__ = os.path.abspath(m.__file__)
diff --git a/Lib/test/test_frozen.py b/Lib/test/test_frozen.py
index 5243ebb..dbd229b 100644
--- a/Lib/test/test_frozen.py
+++ b/Lib/test/test_frozen.py
@@ -5,6 +5,12 @@
 import sys
 
 class FrozenTests(unittest.TestCase):
+
+    module_attrs = frozenset(['__builtins__', '__cached__', '__doc__',
+                              '__file__', '__loader__', '__name__',
+                              '__package__'])
+    package_attrs = frozenset(list(module_attrs) + ['__path__'])
+
     def test_frozen(self):
         with captured_stdout() as stdout:
             try:
@@ -12,7 +18,9 @@
             except ImportError as x:
                 self.fail("import __hello__ failed:" + str(x))
             self.assertEqual(__hello__.initialized, True)
-            self.assertEqual(len(dir(__hello__)), 7, dir(__hello__))
+            expect = set(self.module_attrs)
+            expect.add('initialized')
+            self.assertEqual(set(dir(__hello__)), expect)
             self.assertEqual(stdout.getvalue(), 'Hello world!\n')
 
         with captured_stdout() as stdout:
@@ -21,10 +29,13 @@
             except ImportError as x:
                 self.fail("import __phello__ failed:" + str(x))
             self.assertEqual(__phello__.initialized, True)
+            expect = set(self.package_attrs)
+            expect.add('initialized')
             if not "__phello__.spam" in sys.modules:
-                self.assertEqual(len(dir(__phello__)), 8, dir(__phello__))
+                self.assertEqual(set(dir(__phello__)), expect)
             else:
-                self.assertEqual(len(dir(__phello__)), 9, dir(__phello__))
+                expect.add('spam')
+                self.assertEqual(set(dir(__phello__)), expect)
             self.assertEqual(__phello__.__path__, [__phello__.__name__])
             self.assertEqual(stdout.getvalue(), 'Hello world!\n')
 
@@ -34,8 +45,13 @@
             except ImportError as x:
                 self.fail("import __phello__.spam failed:" + str(x))
             self.assertEqual(__phello__.spam.initialized, True)
-            self.assertEqual(len(dir(__phello__.spam)), 7)
-            self.assertEqual(len(dir(__phello__)), 9)
+            spam_expect = set(self.module_attrs)
+            spam_expect.add('initialized')
+            self.assertEqual(set(dir(__phello__.spam)), spam_expect)
+            phello_expect = set(self.package_attrs)
+            phello_expect.add('initialized')
+            phello_expect.add('spam')
+            self.assertEqual(set(dir(__phello__)), phello_expect)
             self.assertEqual(stdout.getvalue(), 'Hello world!\n')
 
         try:
diff --git a/Lib/test/test_import.py b/Lib/test/test_import.py
index bd2da72..87409fc 100644
--- a/Lib/test/test_import.py
+++ b/Lib/test/test_import.py
@@ -73,6 +73,7 @@
 
             if TESTFN in sys.modules:
                 del sys.modules[TESTFN]
+            importlib.invalidate_caches()
             try:
                 try:
                     mod = __import__(TESTFN)
@@ -402,6 +403,7 @@
         py_compile.compile(self.file_name, dfile=target)
         os.remove(self.file_name)
         pyc_file = make_legacy_pyc(self.file_name)
+        importlib.invalidate_caches()
         mod = self.import_module()
         self.assertEqual(mod.module_filename, pyc_file)
         self.assertEqual(mod.code_filename, target)
@@ -509,7 +511,7 @@
 
         # Check relative import fails with package set to a non-string
         ns = dict(__package__=object())
-        self.assertRaises(ValueError, check_relative)
+        self.assertRaises(TypeError, check_relative)
 
     def test_absolute_import_without_future(self):
         # If explicit relative import syntax is used, then do not try
@@ -644,6 +646,7 @@
             pass
         unload('pep3147.foo')
         unload('pep3147')
+        importlib.invalidate_caches()
         m = __import__('pep3147.foo')
         init_pyc = imp.cache_from_source(
             os.path.join('pep3147', '__init__.py'))
@@ -666,9 +669,11 @@
             pass
         with open(os.path.join('pep3147', 'foo.py'), 'w'):
             pass
+        importlib.invalidate_caches()
         m = __import__('pep3147.foo')
         unload('pep3147.foo')
         unload('pep3147')
+        importlib.invalidate_caches()
         m = __import__('pep3147.foo')
         init_pyc = imp.cache_from_source(
             os.path.join('pep3147', '__init__.py'))
diff --git a/Lib/test/test_pkg.py b/Lib/test/test_pkg.py
index a4ddb15..4d0eee8 100644
--- a/Lib/test/test_pkg.py
+++ b/Lib/test/test_pkg.py
@@ -196,14 +196,15 @@
 
         import t5
         self.assertEqual(fixdir(dir(t5)),
-                         ['__cached__', '__doc__', '__file__', '__name__',
-                          '__package__', '__path__', 'foo', 'string', 't5'])
+                         ['__cached__', '__doc__', '__file__', '__loader__',
+                          '__name__', '__package__', '__path__', 'foo',
+                          'string', 't5'])
         self.assertEqual(fixdir(dir(t5.foo)),
-                         ['__cached__', '__doc__', '__file__', '__name__',
-                          '__package__', 'string'])
+                         ['__cached__', '__doc__', '__file__', '__loader__',
+                          '__name__', '__package__', 'string'])
         self.assertEqual(fixdir(dir(t5.string)),
-                         ['__cached__', '__doc__', '__file__', '__name__',
-                          '__package__', 'spam'])
+                         ['__cached__', '__doc__', '__file__', '__loader__',
+                          '__name__', '__package__', 'spam'])
 
     def test_6(self):
         hier = [
@@ -219,14 +220,14 @@
         import t6
         self.assertEqual(fixdir(dir(t6)),
                          ['__all__', '__cached__', '__doc__', '__file__',
-                          '__name__', '__package__', '__path__'])
+                          '__loader__', '__name__', '__package__', '__path__'])
         s = """
             import t6
             from t6 import *
             self.assertEqual(fixdir(dir(t6)),
                              ['__all__', '__cached__', '__doc__', '__file__',
-                              '__name__', '__package__', '__path__',
-                              'eggs', 'ham', 'spam'])
+                              '__loader__', '__name__', '__package__',
+                              '__path__', 'eggs', 'ham', 'spam'])
             self.assertEqual(dir(), ['eggs', 'ham', 'self', 'spam', 't6'])
             """
         self.run_code(s)
@@ -252,19 +253,19 @@
         t7, sub, subsub = None, None, None
         import t7 as tas
         self.assertEqual(fixdir(dir(tas)),
-                         ['__cached__', '__doc__', '__file__', '__name__',
-                          '__package__', '__path__'])
+                         ['__cached__', '__doc__', '__file__', '__loader__',
+                          '__name__', '__package__', '__path__'])
         self.assertFalse(t7)
         from t7 import sub as subpar
         self.assertEqual(fixdir(dir(subpar)),
-                         ['__cached__', '__doc__', '__file__', '__name__',
-                          '__package__', '__path__'])
+                         ['__cached__', '__doc__', '__file__', '__loader__',
+                          '__name__', '__package__', '__path__'])
         self.assertFalse(t7)
         self.assertFalse(sub)
         from t7.sub import subsub as subsubsub
         self.assertEqual(fixdir(dir(subsubsub)),
-                         ['__cached__', '__doc__', '__file__', '__name__',
-                         '__package__', '__path__', 'spam'])
+                         ['__cached__', '__doc__', '__file__', '__loader__',
+                          '__name__', '__package__', '__path__', 'spam'])
         self.assertFalse(t7)
         self.assertFalse(sub)
         self.assertFalse(subsub)
diff --git a/Lib/test/test_pydoc.py b/Lib/test/test_pydoc.py
index e805ed8..a9f75b9 100644
--- a/Lib/test/test_pydoc.py
+++ b/Lib/test/test_pydoc.py
@@ -383,11 +383,10 @@
         modname = 'testmod_xyzzy'
         testpairs = (
             ('i_am_not_here', 'i_am_not_here'),
-            ('test.i_am_not_here_either', 'i_am_not_here_either'),
-            ('test.i_am_not_here.neither_am_i', 'i_am_not_here.neither_am_i'),
-            ('i_am_not_here.{}'.format(modname),
-             'i_am_not_here.{}'.format(modname)),
-            ('test.{}'.format(modname), modname),
+            ('test.i_am_not_here_either', 'test.i_am_not_here_either'),
+            ('test.i_am_not_here.neither_am_i', 'test.i_am_not_here'),
+            ('i_am_not_here.{}'.format(modname), 'i_am_not_here'),
+            ('test.{}'.format(modname), 'test.{}'.format(modname)),
             )
 
         sourcefn = os.path.join(TESTFN, modname) + os.extsep + "py"
diff --git a/Lib/test/test_runpy.py b/Lib/test/test_runpy.py
index 2cede19..de44df0 100644
--- a/Lib/test/test_runpy.py
+++ b/Lib/test/test_runpy.py
@@ -5,6 +5,7 @@
 import sys
 import re
 import tempfile
+import importlib
 import py_compile
 from test.support import (
     forget, make_legacy_pyc, run_unittest, unload, verbose, no_tracing,
@@ -172,11 +173,13 @@
             self.assertIn("x", d1)
             self.assertEqual(d1["x"], 1)
             del d1 # Ensure __loader__ entry doesn't keep file open
+            importlib.invalidate_caches()
             __import__(mod_name)
             os.remove(mod_fname)
             make_legacy_pyc(mod_fname)
             unload(mod_name)  # In case loader caches paths
             if verbose: print("Running from compiled:", mod_name)
+            importlib.invalidate_caches()
             d2 = run_module(mod_name) # Read from bytecode
             self.assertIn("x", d2)
             self.assertEqual(d2["x"], 1)
@@ -196,11 +199,13 @@
             self.assertIn("x", d1)
             self.assertTrue(d1["x"] == 1)
             del d1 # Ensure __loader__ entry doesn't keep file open
+            importlib.invalidate_caches()
             __import__(mod_name)
             os.remove(mod_fname)
             make_legacy_pyc(mod_fname)
             unload(mod_name)  # In case loader caches paths
             if verbose: print("Running from compiled:", pkg_name)
+            importlib.invalidate_caches()
             d2 = run_module(pkg_name) # Read from bytecode
             self.assertIn("x", d2)
             self.assertTrue(d2["x"] == 1)
@@ -250,11 +255,13 @@
             self.assertIn("sibling", d1)
             self.assertIn("nephew", d1)
             del d1 # Ensure __loader__ entry doesn't keep file open
+            importlib.invalidate_caches()
             __import__(mod_name)
             os.remove(mod_fname)
             make_legacy_pyc(mod_fname)
             unload(mod_name)  # In case the loader caches paths
             if verbose: print("Running from compiled:", mod_name)
+            importlib.invalidate_caches()
             d2 = run_module(mod_name, run_name=run_name) # Read from bytecode
             self.assertIn("__package__", d2)
             self.assertTrue(d2["__package__"] == pkg_name)
diff --git a/Lib/test/test_support.py b/Lib/test/test_support.py
index 394e210..14fcdbf 100644
--- a/Lib/test/test_support.py
+++ b/Lib/test/test_support.py
@@ -1,5 +1,6 @@
 #!/usr/bin/env python
 
+import importlib
 import sys
 import os
 import unittest
@@ -59,6 +60,7 @@
         with open(mod_filename, 'w') as f:
             print('foo = 1', file=f)
         sys.path.insert(0, os.curdir)
+        importlib.invalidate_caches()
         try:
             mod = __import__(TESTFN)
             self.assertIn(TESTFN, sys.modules)
diff --git a/Lib/test/test_trace.py b/Lib/test/test_trace.py
index d9bef38..fa0d48c 100644
--- a/Lib/test/test_trace.py
+++ b/Lib/test/test_trace.py
@@ -322,7 +322,7 @@
             self._coverage(tracer)
         if os.path.exists(TESTFN):
             files = os.listdir(TESTFN)
-            self.assertEqual(files, [])
+            self.assertEqual(files, ['_importlib.cover'])  # Ignore __import__
 
     def test_issue9936(self):
         tracer = trace.Trace(trace=0, count=1)