Base case re #717 works now.

Huge ass squashed commit because I was experimenting
with "commit entire feature at once so you do not leave
broken tests around to break bisecting". Not sure it's worth it,
at least not for large-ish, overhauling-existing-code feature adds.

Breaking the work up over months did not help either, L M A O

52 files changed, 892 insertions, 160 deletions

diff --git a/.travis.yml b/.travis.yml
index 84b73bd6..079baba9 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -36,10 +36,12 @@ install:
     if [[ -n "$OLDEST_CRYPTO" ]]; then
       pip install "cryptography==${OLDEST_CRYPTO}"
     fi
-  # Self-install for setup.py-driven deps
-  - pip install -e .
+  # Self-install for setup.py-driven deps (plus additional
+  # safe-enough-for-all-matrix-cells optional deps)
+  - pip install -e ".[ed25519,invoke]"
   # Dev (doc/test running) requirements
-  # TODO: use pipenv + whatever contexty-type stuff it has
+  # TODO: use poetry + whatever contexty-type stuff it has, should be more than
+  # just prod/dev split. Also apply to the above re: extras_require.
   - pip install codecov # For codecov specifically
   - pip install -r dev-requirements.txt
   - |
diff --git a/paramiko/__init__.py b/paramiko/__init__.py
index d8e60bb2..8642f84a 100644
--- a/paramiko/__init__.py
+++ b/paramiko/__init__.py
@@ -40,6 +40,7 @@ from paramiko.ssh_exception import (
     BadAuthenticationType,
     BadHostKeyException,
     ChannelException,
+    ConfigParseError,
     CouldNotCanonicalize,
     PasswordRequiredException,
     ProxyCommandFailure,
@@ -105,6 +106,7 @@ __all__ = [
     "BufferedFile",
     "Channel",
     "ChannelException",
+    "ConfigParseError",
     "CouldNotCanonicalize",
     "DSSKey",
     "ECDSAKey",
diff --git a/paramiko/config.py b/paramiko/config.py
index 5336454c..b668be69 100644
--- a/paramiko/config.py
+++ b/paramiko/config.py
@@ -22,14 +22,22 @@ Configuration file (aka ``ssh_config``) support.
 """
 
 import fnmatch
+import getpass
 import os
 import re
 import shlex
 import socket
+from functools import partial
 
 from .py3compat import StringIO
 
-from .ssh_exception import CouldNotCanonicalize
+invoke, invoke_import_error = None, None
+try:
+    import invoke
+except ImportError as e:
+    invoke_import_error = e
+
+from .ssh_exception import CouldNotCanonicalize, ConfigParseError
 
 
 SSH_PORT = 22
@@ -48,6 +56,17 @@ class SSHConfig(object):
 
     SETTINGS_REGEX = re.compile(r"(\w+)(?:\s*=\s*|\s+)(.+)")
 
+    # TODO: do a full scan of ssh.c & friends to make sure we're fully
+    # compatible across the board, e.g. OpenSSH 8.1 added %n to ProxyCommand.
+    TOKENS_BY_CONFIG_KEY = {
+        "controlpath": ["%h", "%l", "%L", "%n", "%p", "%r", "%u"],
+        "identityfile": ["~", "%d", "%h", "%l", "%u", "%r"],
+        "proxycommand": ["~", "%h", "%p", "%r"],
+        # Doesn't seem worth making this 'special' for now, it will fit well
+        # enough (no actual match-exec config key to be confused with).
+        "match-exec": ["%d", "%h", "%L", "%l", "%n", "%p", "%r", "%u"],
+    }
+
     def __init__(self):
         """
         Create a new OpenSSH config object.
@@ -105,28 +124,44 @@ class SSHConfig(object):
 
         :param file_obj: a file-like object to read the config file from
         """
-        host = {"host": ["*"], "config": {}}
+        # Start out w/ implicit/anonymous global host-like block to hold
+        # anything not contained by an explicit one.
+        context = {"host": ["*"], "config": {}}
         for line in file_obj:
             # Strip any leading or trailing whitespace from the line.
             # Refer to https://github.com/paramiko/paramiko/issues/499
             line = line.strip()
+            # Skip blanks, comments
             if not line or line.startswith("#"):
                 continue
 
+            # Parse line into key, value
             match = re.match(self.SETTINGS_REGEX, line)
             if not match:
-                raise Exception("Unparsable line {}".format(line))
+                raise ConfigParseError("Unparsable line {}".format(line))
             key = match.group(1).lower()
             value = match.group(2)
 
-            if key == "host":
-                self._config.append(host)
-                host = {"host": self._get_hosts(value), "config": {}}
+            # Host keyword triggers switch to new block/context
+            if key in ("host", "match"):
+                self._config.append(context)
+                context = {"config": {}}
+                if key == "host":
+                    # TODO 3.0: make these real objects or at least name this
+                    # "hosts" to acknowledge it's an iterable. (Doing so prior
+                    # to 3.0, despite it being a private API, feels bad -
+                    # surely such an old codebase has folks actually relying on
+                    # these keys.)
+                    context["host"] = self._get_hosts(value)
+                else:
+                    context["matches"] = self._get_matches(value)
+            # Special-case for noop ProxyCommands
             elif key == "proxycommand" and value.lower() == "none":
                 # Store 'none' as None; prior to 3.x, it will get stripped out
                 # at the end (for compatibility with issue #415). After 3.x, it
                 # will simply not get stripped, leaving a nice explicit marker.
-                host["config"][key] = None
+                context["config"][key] = None
+            # All other keywords get stored, directly or via append
             else:
                 if value.startswith('"') and value.endswith('"'):
                     value = value[1:-1]
@@ -135,13 +170,14 @@ class SSHConfig(object):
                 # cases, since they are allowed to be specified multiple times
                 # and they should be tried in order of specification.
                 if key in ["identityfile", "localforward", "remoteforward"]:
-                    if key in host["config"]:
-                        host["config"][key].append(value)
+                    if key in context["config"]:
+                        context["config"][key].append(value)
                     else:
-                        host["config"][key] = [value]
-                elif key not in host["config"]:
-                    host["config"][key] = value
-        self._config.append(host)
+                        context["config"][key] = [value]
+                elif key not in context["config"]:
+                    context["config"][key] = value
+        # Store last 'open' block and we're done
+        self._config.append(context)
 
     def lookup(self, hostname):
         """
@@ -149,9 +185,9 @@ class SSHConfig(object):
 
         The host-matching rules of OpenSSH's ``ssh_config`` man page are used:
         For each parameter, the first obtained value will be used.  The
-        configuration files contain sections separated by ``Host``
-        specifications, and that section is only applied for hosts that match
-        one of the patterns given in the specification.
+        configuration files contain sections separated by ``Host`` and/or
+        ``Match`` specifications, and that section is only applied for hosts
+        which match the given patterns or keywords
 
         Since the first obtained value for each parameter is used, more host-
         specific declarations should be given near the beginning of the file,
@@ -168,15 +204,26 @@ class SSHConfig(object):
             assert conf['passwordauthentication'] == 'yes'
             assert conf.as_bool('passwordauthentication') is True
 
+        .. note::
+            If there is no explicitly configured ``HostName`` value, it will be
+            set to the being-looked-up hostname, which is as close as we can
+            get to OpenSSH's behavior around that particular option.
+
         :param str hostname: the hostname to lookup
 
         .. versionchanged:: 2.5
             Returns `SSHConfigDict` objects instead of dict literals.
         .. versionchanged:: 2.7
             Added canonicalization support.
+        .. versionchanged:: 2.7
+            Added ``Match`` support.
         """
         # First pass
         options = self._lookup(hostname=hostname)
+        # Inject HostName if it was not set (this used to be done incidentally
+        # during tokenization, for some reason).
+        if "hostname" not in options:
+            options["hostname"] = hostname
         # Handle canonicalization
         canon = options.get("canonicalizehostname", None) in ("yes", "always")
         maxdots = int(options.get("canonicalizemaxdots", 1))
@@ -185,21 +232,26 @@ class SSHConfig(object):
             # implementation for CanonicalDomains is 'split on any whitespace'.
             domains = options["canonicaldomains"].split()
             hostname = self.canonicalize(hostname, options, domains)
+            # Overwrite HostName again here (this is also what OpenSSH does)
             options["hostname"] = hostname
-            options = self._lookup(hostname, options)
+            options = self._lookup(hostname, options, canonical=True)
         return options
 
-    def _lookup(self, hostname, options=None):
-        matches = [
-            config
-            for config in self._config
-            if self._allowed(config["host"], hostname)
-        ]
-
+    def _lookup(self, hostname, options=None, canonical=False):
+        # Init
         if options is None:
             options = SSHConfigDict()
-        for match in matches:
-            for key, value in match["config"].items():
+        # Iterate all stanzas, applying any that match, in turn (so that things
+        # like Match can reference currently understood state)
+        for context in self._config:
+            if not (
+                self._pattern_matches(context.get("host", []), hostname)
+                or self._does_match(
+                    context.get("matches", []), hostname, canonical, options
+                )
+            ):
+                continue
+            for key, value in context["config"].items():
                 if key not in options:
                     # Create a copy of the original value,
                     # else it will reference the original list
@@ -210,6 +262,8 @@ class SSHConfig(object):
                     options[key].extend(
                         x for x in value if x not in options[key]
                     )
+        # Expand variables in resulting values (besides 'Match exec' which was
+        # already handled above)
         options = self._expand_variables(options, hostname)
         # TODO: remove in 3.x re #670
         if "proxycommand" in options and options["proxycommand"] is None:
@@ -267,86 +321,176 @@ class SSHConfig(object):
             hosts.update(entry["host"])
         return hosts
 
-    def _allowed(self, hosts, hostname):
+    def _pattern_matches(self, patterns, target):
+        # Convenience auto-splitter if not already a list
+        if hasattr(patterns, "split"):
+            patterns = patterns.split(",")
         match = False
-        for host in hosts:
-            if host.startswith("!") and fnmatch.fnmatch(hostname, host[1:]):
+        for pattern in patterns:
+            # Short-circuit if target matches a negated pattern
+            if pattern.startswith("!") and fnmatch.fnmatch(
+                target, pattern[1:]
+            ):
                 return False
-            elif fnmatch.fnmatch(hostname, host):
+            # Flag a match, but continue (in case of later negation) if regular
+            # match occurs
+            elif fnmatch.fnmatch(target, pattern):
                 match = True
         return match
 
-    def _expand_variables(self, config, hostname):
+    # TODO 3.0: remove entirely (is now unused internally)
+    def _allowed(self, hosts, hostname):
+        return self._pattern_matches(hosts, hostname)
+
+    def _does_match(self, match_list, target_hostname, canonical, options):
+        matched = []
+        candidates = match_list[:]
+        local_username = getpass.getuser()
+        while candidates:
+            candidate = candidates.pop(0)
+            # Obtain latest host/user value every loop, so later Match may
+            # reference values assigned within a prior Match.
+            configured_host = options.get("hostname", None)
+            configured_user = options.get("user", None)
+            type_, param = candidate["type"], candidate["param"]
+            # Canonical is a hard pass/fail based on whether this is a
+            # canonicalized re-lookup.
+            if type_ == "canonical":
+                if self._should_fail(canonical, candidate):
+                    return False
+            # The parse step ensures we only see this by itself or after
+            # canonical, so it's also an easy hard pass. (No negation here as
+            # that would be uh, pretty weird?)
+            if type_ == "all":
+                return True
+            # From here, we are testing various non-hard criteria,
+            # short-circuiting only on fail
+            if type_ == "host":
+                hostval = configured_host or target_hostname
+                passed = self._pattern_matches(param, hostval)
+                if self._should_fail(passed, candidate):
+                    return False
+            if type_ == "originalhost":
+                passed = self._pattern_matches(param, target_hostname)
+                if self._should_fail(passed, candidate):
+                    return False
+            if type_ == "user":
+                user = configured_user or local_username
+                passed = self._pattern_matches(param, user)
+                if self._should_fail(passed, candidate):
+                    return False
+            if type_ == "localuser":
+                passed = self._pattern_matches(param, local_username)
+                if self._should_fail(passed, candidate):
+                    return False
+            if type_ == "exec":
+                exec_cmd = self._tokenize(
+                    options, target_hostname, "match-exec", param
+                )
+                # Like OpenSSH, we 'redirect' stdout but let stderr bubble up
+                passed = invoke.run(exec_cmd, hide="stdout", warn=True).ok
+                if self._should_fail(passed, candidate):
+                    return False
+            # Made it all the way here? Everything matched!
+            matched.append(candidate)
+        # Did anything match? (To be treated as bool, usually.)
+        return matched
+
+    def _should_fail(self, would_pass, candidate):
+        return would_pass if candidate["negate"] else not would_pass
+
+    def _tokenize(self, config, target_hostname, key, value):
         """
-        Return a dict of config options with expanded substitutions
-        for a given hostname.
+        Tokenize a string based on current config/hostname data.
 
-        Please refer to man ``ssh_config`` for the parameters that
-        are replaced.
+        :param config: Current config data.
+        :param target_hostname: Original target connection hostname.
+        :param key: Config key being tokenized (used to filter token list).
+        :param value: Config value being tokenized.
 
-        :param dict config: the config for the hostname
-        :param str hostname: the hostname that the config belongs to
+        :returns: The tokenized version of the input ``value`` string.
         """
-
+        allowed_tokens = self._allowed_tokens(key)
+        # Short-circuit if no tokenization possible
+        if not allowed_tokens:
+            return value
+        # Obtain potentially configured (and even possibly itself tokenized)
+        # hostname, for use with %h in other values.
+        configured_hostname = target_hostname
         if "hostname" in config:
-            config["hostname"] = config["hostname"].replace("%h", hostname)
-        else:
-            config["hostname"] = hostname
-
+            configured_hostname = config["hostname"].replace(
+                "%h", target_hostname
+            )
+        # Ditto the rest of the source values
         if "port" in config:
             port = config["port"]
         else:
             port = SSH_PORT
-
-        user = os.getenv("USER")
+        user = getpass.getuser()
         if "user" in config:
             remoteuser = config["user"]
         else:
             remoteuser = user
-
-        host = socket.gethostname().split(".")[0]
-        fqdn = LazyFqdn(config, host)
+        local_hostname = socket.gethostname().split(".")[0]
+        local_fqdn = LazyFqdn(config, local_hostname)
         homedir = os.path.expanduser("~")
+        # The actual tokens!
         replacements = {
-            "controlpath": [
-                ("%h", config["hostname"]),
-                ("%l", fqdn),
-                ("%L", host),
-                ("%n", hostname),
-                ("%p", port),
-                ("%r", remoteuser),
-                ("%u", user),
-            ],
-            "identityfile": [
-                ("~", homedir),
-                ("%d", homedir),
-                ("%h", config["hostname"]),
-                ("%l", fqdn),
-                ("%u", user),
-                ("%r", remoteuser),
-            ],
-            "proxycommand": [
-                ("~", homedir),
-                ("%h", config["hostname"]),
-                ("%p", port),
-                ("%r", remoteuser),
-            ],
+            # TODO: %%???
+            # TODO: %C?
+            "%d": homedir,
+            "%h": configured_hostname,
+            # TODO: %i?
+            "%L": local_hostname,
+            "%l": local_fqdn,
+            # also this is pseudo buggy when not in Match exec mode so document
+            # that. also WHY is that the case?? don't we do all of this late?
+            "%n": target_hostname,
+            "%p": port,
+            "%r": remoteuser,
+            # TODO: %T? don't believe this is possible however
+            "%u": user,
+            "~": homedir,
         }
+        # Do the thing with the stuff
+        tokenized = value
+        for find, replace in replacements.items():
+            if find not in allowed_tokens:
+                continue
+            tokenized = tokenized.replace(find, str(replace))
+        # TODO: log? eg that value -> tokenized
+        return tokenized
 
+    def _allowed_tokens(self, key):
+        """
+        Given config ``key``, return list of token strings to tokenize.
+
+        .. note::
+            This feels like it wants to eventually go away, but is used to
+            preserve as-strict-as-possible compatibility with OpenSSH, which
+            for whatever reason only applies some tokens to some config keys.
+        """
+        return self.TOKENS_BY_CONFIG_KEY.get(key, [])
+
+    def _expand_variables(self, config, target_hostname):
+        """
+        Return a dict of config options with expanded substitutions
+        for a given original & current target hostname.
+
+        Please refer to :doc:`/api/config` for details.
+
+        :param dict config: the currently parsed config
+        :param str hostname: the hostname whose config is being looked up
+        """
         for k in config:
             if config[k] is None:
                 continue
-            if k in replacements:
-                for find, replace in replacements[k]:
-                    if isinstance(config[k], list):
-                        for item in range(len(config[k])):
-                            if find in config[k][item]:
-                                config[k][item] = config[k][item].replace(
-                                    find, str(replace)
-                                )
-                    else:
-                        if find in config[k]:
-                            config[k] = config[k].replace(find, str(replace))
+            tokenizer = partial(self._tokenize, config, target_hostname, k)
+            if isinstance(config[k], list):
+                for i, value in enumerate(config[k]):
+                    config[k][i] = tokenizer(value)
+            else:
+                config[k] = tokenizer(config[k])
         return config
 
     def _get_hosts(self, host):
@@ -356,7 +500,51 @@ class SSHConfig(object):
         try:
             return shlex.split(host)
         except ValueError:
-            raise Exception("Unparsable host {}".format(host))
+            raise ConfigParseError("Unparsable host {}".format(host))
+
+    def _get_matches(self, match):
+        """
+        Parse a specific Match config line into a list-of-dicts for its values.
+
+        Performs some parse-time validation as well.
+        """
+        matches = []
+        tokens = shlex.split(match)
+        while tokens:
+            match = {"type": None, "param": None, "negate": False}
+            type_ = tokens.pop(0)
+            # Handle per-keyword negation
+            if type_.startswith("!"):
+                match["negate"] = True
+                type_ = type_[1:]
+            match["type"] = type_
+            # all/canonical have no params (everything else does)
+            if type_ in ("all", "canonical"):
+                matches.append(match)
+                continue
+            if not tokens:
+                raise ConfigParseError(
+                    "Missing parameter to Match '{}' keyword".format(type_)
+                )
+            match["param"] = tokens.pop(0)
+            matches.append(match)
+        # Perform some (easier to do now than in the middle) validation that is
+        # better handled here than at lookup time.
+        keywords = [x["type"] for x in matches]
+        if "all" in keywords:
+            allowable = ("all", "canonical")
+            ok, bad = (
+                list(filter(lambda x: x in allowable, keywords)),
+                list(filter(lambda x: x not in allowable, keywords)),
+            )
+            err = None
+            if any(bad):
+                err = "Match does not allow 'all' mixed with anything but 'canonical'"  # noqa
+            elif "canonical" in ok and ok.index("canonical") > ok.index("all"):
+                err = "Match does not allow 'all' before 'canonical'"
+            if err is not None:
+                raise ConfigParseError(err)
+        return matches
 
 
 def _addressfamily_host_lookup(hostname, options):
diff --git a/paramiko/ssh_exception.py b/paramiko/ssh_exception.py
index a8ec4cdd..2789be99 100644
--- a/paramiko/ssh_exception.py
+++ b/paramiko/ssh_exception.py
@@ -201,6 +201,22 @@ class NoValidConnectionsError(socket.error):
 class CouldNotCanonicalize(SSHException):
     """
     Raised when hostname canonicalization fails & fallback is disabled.
+
+    .. versionadded:: 2.7
+    """
+
+    pass
+
+
+class ConfigParseError(SSHException):
+    """
+    A fatal error was encountered trying to parse SSH config data.
+
+    Typically this means a config file violated the ``ssh_config``
+    specification in a manner that requires exiting immediately, such as not
+    matching ``key = value`` syntax or misusing certain ``Match`` keywords.
+
+    .. versionadded:: 2.7
     """
 
     pass
diff --git a/setup.py b/setup.py
index abe04472..2eb4cd46 100644
--- a/setup.py
+++ b/setup.py
@@ -50,6 +50,7 @@ extras_require = {
         'pywin32>=2.1.8;platform_system=="Windows"',
     ],
     "ed25519": ["pynacl>=1.0.1", "bcrypt>=3.1.3"],
+    "invoke": ["invoke>=1.3"],
 }
 everything = []
 for subdeps in extras_require.values():
diff --git a/sites/docs/api/config.rst b/sites/docs/api/config.rst
index 579fb913..8ee0b444 100644
--- a/sites/docs/api/config.rst
+++ b/sites/docs/api/config.rst
@@ -61,6 +61,14 @@ Paramiko releases) are included. A keyword by itself means no known departures.
 
 - ``Host``
 - ``HostName``: used in ``%h`` :ref:`token expansion <TOKENS>`
+- ``Match``: fully supported, with the usual caveat that connection-time
+  information is not present during config lookup, and thus cannot be used to
+  determine matching. This primarily impacts ``Match user``, which can match
+  against loaded ``User`` values but has no knowledge about connection-time
+  usernames.
+
+    .. versionadded:: 2.7
+
 - ``Port``: supplies potential values for ``%p`` :ref:`token expansion
   <TOKENS>`.
 - ``ProxyCommand``: see our `.ProxyCommand` class for an easy
@@ -94,7 +102,8 @@ OpenSSH, ``%L`` works in ``ControlPath`` but not elsewhere):
 - ``%n``
 - ``%p``
 - ``%r``
-- ``%u``
+- ``%u``: substitutes the configured ``User`` value, or the local user (as seen
+  by ``getpass.getuser``) if not specified.
 
 In addition, we extend OpenSSH's tokens as follows:
 
diff --git a/sites/www/changelog.rst b/sites/www/changelog.rst
index 23e9a567..67ba6554 100644
--- a/sites/www/changelog.rst
+++ b/sites/www/changelog.rst
@@ -2,9 +2,30 @@
 Changelog
 =========
 
+- :bug:`- major` ``ssh_config`` :ref:`token expansion <TOKENS>` used a
+  different method of determining the local username (``$USER`` env var),
+  compared to what the (much older) client connection code does
+  (``getpass.getuser``, which includes ``$USER`` but may check other variables
+  first, and is generally much more comprehensive). Both modules now use
+  ``getpass.getuser``.
+- :feature:`-` A couple of outright `~paramiko.config.SSHConfig` parse errors
+  were previously represented as vanilla ``Exception`` instances; as part of
+  recent feature work a more specific exception class,
+  `~paramiko.ssh_exception.ConfigParseError`, has been created. It is now also
+  used in those older spots, which is naturally backwards compatible.
+- :feature:`717` Implement support for the ``Match`` keyword in ``ssh_config``
+  files. Previously, this keyword was simply ignored & keywords inside such
+  blocks were treated as if they were part of the previous block. Thanks to
+  Michael Leinartas for the initial patchset.
+
+  .. note::
+    This feature adds a new :doc:`optional install dependency </installing>`,
+    `Invoke <https://www.pyinvoke.org>`_, for managing ``Match exec``
+    subprocesses.
+
 - :support:`-` Additional :doc:`installation </installing>` ``extras_require``
-  "flavors" (``ed25519`` and ``everything``) have been added to our packaging
-  metadata; see the install docs for details.
+  "flavors" (``ed25519``, ``invoke``, and ``everything``) have been added to
+  our packaging metadata; see the install docs for details.
 - :bug:`- major` Paramiko's use of ``subprocess`` for ``ProxyCommand`` support
   is conditionally imported to prevent issues on limited interpreter platforms
   like Google Compute Engine. However, any resulting ``ImportError`` was lost
diff --git a/sites/www/installing.rst b/sites/www/installing.rst
index 26637e16..ee57bdfc 100644
--- a/sites/www/installing.rst
+++ b/sites/www/installing.rst
@@ -33,9 +33,11 @@ There are also a number of **optional dependencies** you may install using
 `setuptools 'extras'
 <https://packaging.python.org/tutorials/installing-packages/#installing-setuptools-extras>`_:
 
+.. TODO 3.0: tweak the invoke line to mention proxycommand too
 .. TODO 3.0: tweak the ed25519 line to remove the caveat
 
 - If you want all optional dependencies at once, use ``paramiko[everything]``.
+- For ``Match exec`` config support, use ``paramiko[invoke]``.
 - For GSS-API / SSPI support, use ``paramiko[gssapi]``, though also see
   :ref:`the below subsection on it <gssapi>` for details.
 - ``paramiko[ed25519]`` references the dependencies for Ed25519 key support.
diff --git a/tests/configs/basic.config b/tests/configs/basic
index 1ae37cc6..73872b47 100644
--- a/tests/configs/basic.config
+++ b/tests/configs/basic
@@ -3,4 +3,3 @@ CanonicalDomains paramiko.org
 Host www.paramiko.org
     User rando
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/canon.config b/tests/configs/canon
index 7a7ce6c6..3a3cc66a 100644
--- a/tests/configs/canon.config
+++ b/tests/configs/canon
@@ -8,4 +8,3 @@ Host www.paramiko.org
     IdentityFile canonicalized.key
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/canon-always.config b/tests/configs/canon-always
index 85058a14..fdaeabd4 100644
--- a/tests/configs/canon-always.config
+++ b/tests/configs/canon-always
@@ -5,4 +5,3 @@ Host www.paramiko.org
     User rando
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/canon-ipv4.config b/tests/configs/canon-ipv4
index 9f48273e..b29766a3 100644
--- a/tests/configs/canon-ipv4.config
+++ b/tests/configs/canon-ipv4
@@ -6,4 +6,3 @@ Host www.paramiko.org
     User rando
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/canon-local.config b/tests/configs/canon-local
index 418f7723..0b5588ca 100644
--- a/tests/configs/canon-local.config
+++ b/tests/configs/canon-local
@@ -6,4 +6,3 @@ Host www
     CanonicalizeHostname yes
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/canon-local-always.config b/tests/configs/canon-local-always
index c821d113..5c059ae1 100644
--- a/tests/configs/canon-local-always.config
+++ b/tests/configs/canon-local-always
@@ -6,4 +6,3 @@ Host www
     CanonicalizeHostname always
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/deep-canon.config b/tests/configs/deep-canon
index 3c111f48..bb3ed5ad 100644
--- a/tests/configs/deep-canon.config
+++ b/tests/configs/deep-canon
@@ -10,4 +10,3 @@ Host sub.www.paramiko.org
 Host subber.sub.www.paramiko.org
     User deeper
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/deep-canon-maxdots.config b/tests/configs/deep-canon-maxdots
index 37a82e72..9262cc58 100644
--- a/tests/configs/deep-canon-maxdots.config
+++ b/tests/configs/deep-canon-maxdots
@@ -11,4 +11,3 @@ Host sub.www.paramiko.org
 Host subber.sub.www.paramiko.org
     User deeper
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/empty-canon.config b/tests/configs/empty-canon
index f268a2ca..d29b30fa 100644
--- a/tests/configs/empty-canon.config
+++ b/tests/configs/empty-canon
@@ -6,4 +6,3 @@ Host www.paramiko.org
     User rando
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/fallback-no.config b/tests/configs/fallback-no
index 86b6a484..d68bfe66 100644
--- a/tests/configs/fallback-no.config
+++ b/tests/configs/fallback-no
@@ -6,4 +6,3 @@ Host www.paramiko.org
     User rando
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/fallback-yes.config b/tests/configs/fallback-yes
index a07064a0..a87764a8 100644
--- a/tests/configs/fallback-yes.config
+++ b/tests/configs/fallback-yes
@@ -5,4 +5,3 @@ CanonicalizeFallbackLocal yes
 Host www.paramiko.org
     User rando
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/invalid b/tests/configs/invalid
new file mode 100644
index 00000000..81332fe8
--- /dev/null
+++ b/tests/configs/invalid
@@ -0,0 +1 @@
+lolwut
diff --git a/tests/configs/match-all b/tests/configs/match-all
new file mode 100644
index 00000000..7673e0a0
--- /dev/null
+++ b/tests/configs/match-all
@@ -0,0 +1,2 @@
+Match all
+    User awesome
diff --git a/tests/configs/match-all-after-canonical b/tests/configs/match-all-after-canonical
new file mode 100644
index 00000000..2acc3a6e
--- /dev/null
+++ b/tests/configs/match-all-after-canonical
@@ -0,0 +1,6 @@
+CanonicalizeHostname yes
+CanonicalDomains paramiko.org
+
+Match canonical all
+    User awesome
+
diff --git a/tests/configs/match-all-and-more b/tests/configs/match-all-and-more
new file mode 100644
index 00000000..2281d238
--- /dev/null
+++ b/tests/configs/match-all-and-more
@@ -0,0 +1,3 @@
+Match all exec "lol nope"
+    HostName whatever
+
diff --git a/tests/configs/match-all-and-more-before b/tests/configs/match-all-and-more-before
new file mode 100644
index 00000000..89a737ee
--- /dev/null
+++ b/tests/configs/match-all-and-more-before
@@ -0,0 +1,3 @@
+Match exec "lol nope" all
+    HostName whatever
+
diff --git a/tests/configs/match-all-before-canonical b/tests/configs/match-all-before-canonical
new file mode 100644
index 00000000..fe0e6646
--- /dev/null
+++ b/tests/configs/match-all-before-canonical
@@ -0,0 +1,6 @@
+CanonicalizeHostname yes
+CanonicalDomains paramiko.org
+
+Match all canonical
+    User oops
+
diff --git a/tests/configs/match-canonical-no b/tests/configs/match-canonical-no
new file mode 100644
index 00000000..e528dc64
--- /dev/null
+++ b/tests/configs/match-canonical-no
@@ -0,0 +1,7 @@
+CanonicalizeHostname no
+
+Match canonical all
+    User awesome
+
+Match !canonical host specific
+    User overload
diff --git a/tests/configs/match-canonical-yes b/tests/configs/match-canonical-yes
new file mode 100644
index 00000000..5c5759c7
--- /dev/null
+++ b/tests/configs/match-canonical-yes
@@ -0,0 +1,6 @@
+CanonicalizeHostname yes
+CanonicalDomains paramiko.org
+
+Match !canonical host www*
+    User hidden
+
diff --git a/tests/configs/match-complex b/tests/configs/match-complex
new file mode 100644
index 00000000..63634039
--- /dev/null
+++ b/tests/configs/match-complex
@@ -0,0 +1,17 @@
+HostName bogus
+
+Match originalhost target host bogus
+    User rand
+
+Match originalhost remote localuser rando
+    User calrissian
+
+# Just to set user for subsequent match
+Match originalhost www
+    User calrissian
+
+Match !canonical originalhost www host bogus localuser rando user calrissian
+    Port 7777
+
+Match !canonical !originalhost www host bogus localuser rando !user calrissian
+    Port 1234
diff --git a/tests/configs/match-exec b/tests/configs/match-exec
new file mode 100644
index 00000000..88d3f769
--- /dev/null
+++ b/tests/configs/match-exec
@@ -0,0 +1,8 @@
+Match exec "quoted"
+    User benjamin
+
+Match exec unquoted
+    User rando
+
+Match exec "quoted spaced"
+    User neil
diff --git a/tests/configs/match-host b/tests/configs/match-host
new file mode 100644
index 00000000..8259fc6b
--- /dev/null
+++ b/tests/configs/match-host
@@ -0,0 +1,3 @@
+Match host target
+    User rand
+
diff --git a/tests/configs/match-host-canonicalized b/tests/configs/match-host-canonicalized
new file mode 100644
index 00000000..347242a0
--- /dev/null
+++ b/tests/configs/match-host-canonicalized
@@ -0,0 +1,10 @@
+CanonicalizeHostname yes
+CanonicalDomains paramiko.org
+
+Match host www.paramiko.org
+    User rand
+
+Match canonical host docs.paramiko.org
+    User eric
+
+
diff --git a/tests/configs/match-host-from-match b/tests/configs/match-host-from-match
new file mode 100644
index 00000000..64b4c4b5
--- /dev/null
+++ b/tests/configs/match-host-from-match
@@ -0,0 +1,6 @@
+Match host original-host
+    HostName substituted-host
+
+Match host substituted-host
+    User inner
+
diff --git a/tests/configs/match-host-glob b/tests/configs/match-host-glob
new file mode 100644
index 00000000..9c198ce3
--- /dev/null
+++ b/tests/configs/match-host-glob
@@ -0,0 +1,4 @@
+Match host *ever
+    User matrim
+
+
diff --git a/tests/configs/match-host-glob-list b/tests/configs/match-host-glob-list
new file mode 100644
index 00000000..76796777
--- /dev/null
+++ b/tests/configs/match-host-glob-list
@@ -0,0 +1,10 @@
+Match host *ever
+    User matrim
+
+Match host somehost,someotherhost
+    User thom
+
+Match host goo*,!goof
+    User perrin
+
+
diff --git a/tests/configs/match-host-name b/tests/configs/match-host-name
new file mode 100644
index 00000000..5b4adb84
--- /dev/null
+++ b/tests/configs/match-host-name
@@ -0,0 +1,5 @@
+HostName default-host
+
+Match host default-host
+    User silly
+
diff --git a/tests/configs/match-host-negated b/tests/configs/match-host-negated
new file mode 100644
index 00000000..7c5d3f3e
--- /dev/null
+++ b/tests/configs/match-host-negated
@@ -0,0 +1,2 @@
+Match !host www
+    User jeff
diff --git a/tests/configs/match-host-no-arg b/tests/configs/match-host-no-arg
new file mode 100644
index 00000000..e9936844
--- /dev/null
+++ b/tests/configs/match-host-no-arg
@@ -0,0 +1,3 @@
+Match host
+    User oops
+
diff --git a/tests/configs/match-localuser b/tests/configs/match-localuser
new file mode 100644
index 00000000..fe4a276c
--- /dev/null
+++ b/tests/configs/match-localuser
@@ -0,0 +1,14 @@
+Match localuser gandalf
+    HostName gondor
+
+Match localuser b*
+    HostName shire
+
+Match localuser aragorn,frodo
+    HostName moria
+
+Match localuser gimli,!legolas
+    Port 7373
+
+Match !localuser sauron
+    HostName mordor
diff --git a/tests/configs/match-localuser-no-arg b/tests/configs/match-localuser-no-arg
new file mode 100644
index 00000000..6623553a
--- /dev/null
+++ b/tests/configs/match-localuser-no-arg
@@ -0,0 +1,2 @@
+Match localuser
+    User oops
diff --git a/tests/configs/match-orighost b/tests/configs/match-orighost
new file mode 100644
index 00000000..10541993
--- /dev/null
+++ b/tests/configs/match-orighost
@@ -0,0 +1,16 @@
+HostName bogus
+
+Match originalhost target
+    User tuon
+
+Match originalhost what*
+    User matrim
+
+Match originalhost comma,sep*
+    User chameleon
+
+Match originalhost yep,!nope
+    User skipped
+
+Match !originalhost www !originalhost nope
+    User thom
diff --git a/tests/configs/match-orighost-canonical b/tests/configs/match-orighost-canonical
new file mode 100644
index 00000000..737345e8
--- /dev/null
+++ b/tests/configs/match-orighost-canonical
@@ -0,0 +1,5 @@
+CanonicalizeHostname yes
+CanonicalDomains paramiko.org
+
+Match originalhost www
+    User tuon
diff --git a/tests/configs/match-orighost-no-arg b/tests/configs/match-orighost-no-arg
new file mode 100644
index 00000000..ebf81fa0
--- /dev/null
+++ b/tests/configs/match-orighost-no-arg
@@ -0,0 +1,3 @@
+Match originalhost
+    User oops
+
diff --git a/tests/configs/match-user b/tests/configs/match-user
new file mode 100644
index 00000000..14d6ac12
--- /dev/null
+++ b/tests/configs/match-user
@@ -0,0 +1,14 @@
+Match user gandalf
+    HostName gondor
+
+Match user b*
+    HostName shire
+
+Match user aragorn,frodo
+    HostName moria
+
+Match user gimli,!legolas
+    Port 7373
+
+Match !user sauron
+    HostName mordor
diff --git a/tests/configs/match-user-explicit b/tests/configs/match-user-explicit
new file mode 100644
index 00000000..9a2b1d82
--- /dev/null
+++ b/tests/configs/match-user-explicit
@@ -0,0 +1,4 @@
+User explicit
+
+Match user explicit
+    HostName dumb
diff --git a/tests/configs/match-user-no-arg b/tests/configs/match-user-no-arg
new file mode 100644
index 00000000..65a11ab4
--- /dev/null
+++ b/tests/configs/match-user-no-arg
@@ -0,0 +1,2 @@
+Match user
+    User oops
diff --git a/tests/configs/multi-canon-domains.config b/tests/configs/multi-canon-domains
index f0cf521d..0fe98e31 100644
--- a/tests/configs/multi-canon-domains.config
+++ b/tests/configs/multi-canon-domains
@@ -5,4 +5,3 @@ Host www.paramiko.org
     User rando
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/no-canon.config b/tests/configs/no-canon
index bd48b790..62e8f713 100644
--- a/tests/configs/no-canon.config
+++ b/tests/configs/no-canon
@@ -5,4 +5,3 @@ Host www.paramiko.org
     User rando
 
 
-# vim: set ft=sshconfig :
diff --git a/tests/configs/robey.config b/tests/configs/robey
index 2175182f..b2026224 100644
--- a/tests/configs/robey.config
+++ b/tests/configs/robey
@@ -15,4 +15,3 @@ Host *
 Host spoo.example.com
 Crazy something else
 
-# vim: set ft=sshconfig list :
diff --git a/tests/configs/zero-maxdots.config b/tests/configs/zero-maxdots
index c7a095ab..eae90285 100644
--- a/tests/configs/zero-maxdots.config
+++ b/tests/configs/zero-maxdots
@@ -8,4 +8,3 @@ Host www.paramiko.org
 Host sub.www.paramiko.org
     User deep
 
-# vim: set ft=sshconfig :
diff --git a/tests/test_config.py b/tests/test_config.py
index f8312b12..bc700f94 100644
--- a/tests/test_config.py
+++ b/tests/test_config.py
@@ -4,15 +4,47 @@
 from os.path import expanduser
 from socket import gaierror
 
+from paramiko.py3compat import string_types
+
+from invoke import Result
 from mock import patch
 from pytest import raises, mark, fixture
 
-from paramiko import SSHConfig, SSHConfigDict, CouldNotCanonicalize
-from paramiko.util import lookup_ssh_host_config
+from paramiko import (
+    SSHConfig,
+    SSHConfigDict,
+    CouldNotCanonicalize,
+    ConfigParseError,
+)
 
 from .util import _config
 
 
+@fixture
+def socket():
+    """
+    Patch all of socket.* in our config module to prevent eg real DNS lookups.
+
+    Also forces getaddrinfo (used in our addressfamily lookup stuff) to always
+    fail by default to mimic usual lack of AddressFamily related crap.
+
+    Callers who want to mock DNS lookups can then safely assume gethostbyname()
+    will be in use.
+    """
+    with patch("paramiko.config.socket") as mocket:
+        # Reinstate gaierror as an actual exception and not a sub-mock.
+        # (Presumably this would work with any exception, but why not use the
+        # real one?)
+        mocket.gaierror = gaierror
+        # Patch out getaddrinfo, used to detect family-specific IP lookup -
+        # only useful for a few specific tests.
+        mocket.getaddrinfo.side_effect = mocket.gaierror
+        # Patch out getfqdn to return some real string for when it gets called;
+        # some code (eg tokenization) gets mad w/ MagicMocks
+        mocket.getfqdn.return_value = "some.fake.fqdn"
+        yield mocket
+
+
 def load_config(name):
     return SSHConfig.from_path(_config(name))
 
@@ -61,41 +93,42 @@ class TestSSHConfig(object):
         ]
         assert self.config._config == expected
 
-    @mark.parametrize("host,values", (
-        (
-            "irc.danger.com",
-            {
-                "crazy": "something dumb",
-                "hostname": "irc.danger.com",
-                "user": "robey",
-            },
-        ),
-        (
-            "irc.example.com",
-            {
-                "crazy": "something dumb",
-                "hostname": "irc.example.com",
-                "user": "robey",
-                "port": "3333",
-            },
-        ),
+    @mark.parametrize(
+        "host,values",
         (
-            "spoo.example.com",
-            {
-                "crazy": "something dumb",
-                "hostname": "spoo.example.com",
-                "user": "robey",
-                "port": "3333",
-            },
+            (
+                "irc.danger.com",
+                {
+                    "crazy": "something dumb",
+                    "hostname": "irc.danger.com",
+                    "user": "robey",
+                },
+            ),
+            (
+                "irc.example.com",
+                {
+                    "crazy": "something dumb",
+                    "hostname": "irc.example.com",
+                    "user": "robey",
+                    "port": "3333",
+                },
+            ),
+            (
+                "spoo.example.com",
+                {
+                    "crazy": "something dumb",
+                    "hostname": "spoo.example.com",
+                    "user": "robey",
+                    "port": "3333",
+                },
+            ),
         ),
-    ))
+    )
     def test_host_config(self, host, values):
         expected = dict(
-            values,
-            hostname=host,
-            identityfile=[expanduser("~/.ssh/id_rsa")],
+            values, hostname=host, identityfile=[expanduser("~/.ssh/id_rsa")]
         )
-        assert lookup_ssh_host_config(host, self.config) == expected
+        assert self.config.lookup(host) == expected
 
     def test_fabric_issue_33(self):
         config = SSHConfig.from_text(
@@ -112,7 +145,7 @@ Host *
         )
         host = "www13.example.com"
         expected = {"hostname": host, "port": "22"}
-        assert lookup_ssh_host_config(host, config) == expected
+        assert config.lookup(host) == expected
 
     def test_proxycommand_config_equals_parsing(self):
         """
@@ -128,7 +161,7 @@ Host equals-delimited
 """
         )
         for host in ("space-delimited", "equals-delimited"):
-            value = lookup_ssh_host_config(host, config)["proxycommand"]
+            value = config.lookup(host)["proxycommand"]
             assert value == "foo bar=biz baz"
 
     def test_proxycommand_interpolation(self):
@@ -154,7 +187,7 @@ Host *
             ("specific", "host specific port 37 lol"),
             ("portonly", "host portonly port 155"),
         ):
-            assert lookup_ssh_host_config(host, config)["proxycommand"] == val
+            assert config.lookup(host)["proxycommand"] == val
 
     def test_proxycommand_tilde_expansion(self):
         """
@@ -169,9 +202,30 @@ Host test
         expected = "ssh -F {}/.ssh/test_config bastion nc test 22".format(
             expanduser("~")
         )
-        got = lookup_ssh_host_config("test", config)["proxycommand"]
+        got = config.lookup("test")["proxycommand"]
         assert got == expected
 
+    @patch("paramiko.config.getpass")
+    def test_controlpath_token_expansion(self, getpass):
+        getpass.getuser.return_value = "gandalf"
+        config = SSHConfig.from_text(
+            """
+Host explicit_user
+    User root
+    ControlPath user %u remoteuser %r
+
+Host explicit_host
+    HostName ohai
+    ControlPath remoteuser %r host %h orighost %n
+        """
+        )
+        result = config.lookup("explicit_user")["controlpath"]
+        # Remote user is User val, local user is User val
+        assert result == "user gandalf remoteuser root"
+        result = config.lookup("explicit_host")["controlpath"]
+        # Remote user falls back to local user; host and orighost may differ
+        assert result == "remoteuser gandalf host ohai orighost explicit_host"
+
     def test_negation(self):
         config = SSHConfig.from_text(
             """
@@ -190,7 +244,7 @@ Host *
         )
         host = "www13.example.com"
         expected = {"hostname": host, "port": "8080"}
-        assert lookup_ssh_host_config(host, config) == expected
+        assert config.lookup(host) == expected
 
     def test_proxycommand(self):
         config = SSHConfig.from_text(
@@ -220,7 +274,7 @@ ProxyCommand foo=bar:%h-%p
             },
         }.items():
 
-            assert lookup_ssh_host_config(host, config) == values
+            assert config.lookup(host) == values
 
     def test_identityfile(self):
         config = SSHConfig.from_text(
@@ -250,7 +304,7 @@ IdentityFile id_dsa22
             },
         }.items():
 
-            assert lookup_ssh_host_config(host, config) == values
+            assert config.lookup(host) == values
 
     def test_config_addressfamily_and_lazy_fqdn(self):
         """
@@ -308,7 +362,7 @@ Host param4 "p a r" "p" "par" para
             "para": {"hostname": "para", "port": "4444"},
         }
         for host, values in res.items():
-            assert lookup_ssh_host_config(host, config) == values
+            assert config.lookup(host) == values
 
     def test_quoted_params_in_config(self):
         config = SSHConfig.from_text(
@@ -339,7 +393,7 @@ Host param3 parara
             },
         }
         for host, values in res.items():
-            assert lookup_ssh_host_config(host, config) == values
+            assert config.lookup(host) == values
 
     def test_quoted_host_in_config(self):
         conf = SSHConfig()
@@ -360,9 +414,13 @@ Host param3 parara
         for host, values in correct_data.items():
             assert conf._get_hosts(host) == values
         for host in incorrect_data:
-            with raises(Exception):
+            with raises(ConfigParseError):
                 conf._get_hosts(host)
 
+    def test_invalid_line_format_excepts(self):
+        with raises(ConfigParseError):
+            load_config("invalid")
+
     def test_proxycommand_none_issue_418(self):
         config = SSHConfig.from_text(
             """
@@ -382,7 +440,7 @@ Host proxycommand-with-equals-none
             },
         }.items():
 
-            assert lookup_ssh_host_config(host, config) == values
+            assert config.lookup(host) == values
 
     def test_proxycommand_none_masking(self):
         # Re: https://github.com/paramiko/paramiko/issues/670
@@ -469,19 +527,6 @@ Host *
         assert config.lookup("anything-else").as_int("port") == 3333
 
 
-@fixture
-def socket():
-    with patch("paramiko.config.socket") as mocket:
-        # Reinstate gaierror as an actual exception and not a sub-mock.
-        # (Presumably this would work with any exception, but why not use the
-        # real one?)
-        mocket.gaierror = gaierror
-        # Patch out getaddrinfo, used to detect family-specific IP lookup -
-        # only useful for a few specific tests.
-        mocket.getaddrinfo.side_effect = mocket.gaierror
-        yield mocket
-
-
 class TestHostnameCanonicalization(object):
     # NOTE: this class uses on-disk configs, and ones with real (at time of
     # writing) DNS names, so that one can easily test OpenSSH's behavior using
@@ -605,3 +650,301 @@ class TestCanonicalizationOfCNAMEs(object):
     def test_permitted_cnames_may_be_multiple_complex_mappings(self):
         # Same as prev but with multiple patterns on both ends in both args
         pass
+
+
+class TestMatchAll(object):
+    def test_always_matches(self):
+        result = load_config("match-all").lookup("general")
+        assert result["user"] == "awesome"
+
+    def test_may_not_mix_with_non_canonical_keywords(self):
+        for config in ("match-all-and-more", "match-all-and-more-before"):
+            with raises(ConfigParseError):
+                load_config(config).lookup("whatever")
+
+    def test_may_come_after_canonical(self, socket):
+        result = load_config("match-all-after-canonical").lookup("www")
+        assert result["user"] == "awesome"
+
+    def test_may_not_come_before_canonical(self, socket):
+        with raises(ConfigParseError):
+            load_config("match-all-before-canonical")
+
+    def test_after_canonical_not_loaded_when_non_canonicalized(self, socket):
+        result = load_config("match-canonical-no").lookup("a-host")
+        assert "user" not in result
+
+
+def _expect(success_on):
+    """
+    Returns a side_effect-friendly Invoke success result for given command(s).
+
+    Ensures that any other commands fail; this is useful for testing 'Match
+    exec' because it means all other such clauses under test act like no-ops.
+
+    :param success_on:
+        Single string or list of strings, noting commands that should appear to
+        succeed.
+    """
+    if isinstance(success_on, string_types):
+        success_on = [success_on]
+
+    def inner(command, *args, **kwargs):
+        # Sanity checking - we always expect that invoke.run is called with
+        # these.
+        assert kwargs.get("hide", None) == "stdout"
+        assert kwargs.get("warn", None) is True
+        # Fake exit
+        exit = 0 if command in success_on else 1
+        return Result(exited=exit)
+    return inner
+
+
+class TestMatchExec(object):
+    @patch("paramiko.config.invoke.run")
+    @mark.parametrize(
+        "cmd,user",
+        [
+            ("unquoted", "rando"),
+            ("quoted", "benjamin"),
+            ("quoted spaced", "neil"),
+        ],
+    )
+    def test_accepts_single_possibly_quoted_argument(self, run, cmd, user):
+        run.side_effect = _expect(cmd)
+        result = load_config("match-exec").lookup("whatever")
+        assert result["user"] == user
+
+    @patch("paramiko.config.invoke.run")
+    def test_does_not_match_nonzero_exit_codes(self, run):
+        # Nothing will succeed -> no User ever gets loaded
+        run.return_value = Result(exited=1)
+        result = load_config("match-exec").lookup("whatever")
+        assert "user" not in result
+
+    def test_tokenizes_argument(self):
+        # TODO: spot check a few common ones like %h, %p, %l?
+        assert False
+
+    def test_works_with_canonical(self, socket):
+        # TODO: before AND after. same file, different key/values, prove both
+        # show up?
+        assert False
+
+    def test_may_be_negated(self):
+        assert False
+
+    def test_requires_an_argument(self):
+        assert False
+
+
+class TestMatchHost(object):
+    def test_matches_target_name_when_no_hostname(self):
+        result = load_config("match-host").lookup("target")
+        assert result["user"] == "rand"
+
+    def test_matches_hostname_from_global_setting(self):
+        # Also works for ones set in regular Host stanzas
+        result = load_config("match-host-name").lookup("anything")
+        assert result["user"] == "silly"
+
+    def test_matches_hostname_from_earlier_match(self):
+        # Corner case: one Match matches original host, sets HostName,
+        # subsequent Match matches the latter.
+        result = load_config("match-host-from-match").lookup("original-host")
+        assert result["user"] == "inner"
+
+    def test_may_be_globbed(self):
+        result = load_config("match-host-glob-list").lookup("whatever")
+        assert result["user"] == "matrim"
+
+    def test_may_be_comma_separated_list(self):
+        for target in ("somehost", "someotherhost"):
+            result = load_config("match-host-glob-list").lookup(target)
+            assert result["user"] == "thom"
+
+    def test_comma_separated_list_may_have_internal_negation(self):
+        conf = load_config("match-host-glob-list")
+        assert conf.lookup("good")["user"] == "perrin"
+        assert "user" not in conf.lookup("goof")
+
+    def test_matches_canonicalized_name(self, socket):
+        # Without 'canonical' explicitly declared, mind.
+        result = load_config("match-host-canonicalized").lookup("www")
+        assert result["user"] == "rand"
+
+    def test_works_with_canonical_keyword(self, socket):
+        # NOTE: distinct from 'happens to be canonicalized' above
+        # TODO: before AND after. same file, different key/values, prove both
+        # show up?
+        result = load_config("match-host-canonicalized").lookup("docs")
+        assert result["user"] == "eric"
+
+    def test_may_be_negated(self):
+        conf = load_config("match-host-negated")
+        assert conf.lookup("docs")["user"] == "jeff"
+        assert "user" not in conf.lookup("www")
+
+    def test_requires_an_argument(self):
+        with raises(ConfigParseError):
+            load_config("match-host-no-arg")
+
+
+class TestMatchOriginalHost(object):
+    def test_matches_target_host_not_hostname(self):
+        result = load_config("match-orighost").lookup("target")
+        assert result["hostname"] == "bogus"
+        assert result["user"] == "tuon"
+
+    def test_matches_target_host_not_canonicalized_name(self, socket):
+        result = load_config("match-orighost-canonical").lookup("www")
+        assert result["hostname"] == "www.paramiko.org"
+        assert result["user"] == "tuon"
+
+    def test_may_be_globbed(self):
+        result = load_config("match-orighost").lookup("whatever")
+        assert result["user"] == "matrim"
+
+    def test_may_be_comma_separated_list(self):
+        for target in ("comma", "separated"):
+            result = load_config("match-orighost").lookup(target)
+            assert result["user"] == "chameleon"
+
+    def test_comma_separated_list_may_have_internal_negation(self):
+        result = load_config("match-orighost").lookup("nope")
+        assert "user" not in result
+
+    def test_may_be_negated(self):
+        result = load_config("match-orighost").lookup("docs")
+        assert result["user"] == "thom"
+
+    def test_requires_an_argument(self):
+        with raises(ConfigParseError):
+            load_config("match-orighost-no-arg")
+
+
+class TestMatchUser(object):
+    def test_matches_configured_username(self):
+        result = load_config("match-user-explicit").lookup("anything")
+        assert result["hostname"] == "dumb"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_matches_local_username_by_default(self, getuser):
+        getuser.return_value = "gandalf"
+        result = load_config("match-user").lookup("anything")
+        assert result["hostname"] == "gondor"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_may_be_globbed(self, getuser):
+        for user in ("bilbo", "bombadil"):
+            getuser.return_value = user
+            result = load_config("match-user").lookup("anything")
+            assert result["hostname"] == "shire"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_may_be_comma_separated_list(self, getuser):
+        for user in ("aragorn", "frodo"):
+            getuser.return_value = user
+            result = load_config("match-user").lookup("anything")
+            assert result["hostname"] == "moria"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_comma_separated_list_may_have_internal_negation(self, getuser):
+        getuser.return_value = "legolas"
+        result = load_config("match-user").lookup("anything")
+        assert "port" not in result
+        getuser.return_value = "gimli"
+        result = load_config("match-user").lookup("anything")
+        assert result["port"] == "7373"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_may_be_negated(self, getuser):
+        getuser.return_value = "saruman"
+        result = load_config("match-user").lookup("anything")
+        assert result["hostname"] == "mordor"
+
+    def test_requires_an_argument(self):
+        with raises(ConfigParseError):
+            load_config("match-user-no-arg")
+
+
+# NOTE: highly derivative of previous suite due to the former's use of
+# localuser fallback. Doesn't seem worth conflating/refactoring right now.
+class TestMatchLocalUser(object):
+    @patch("paramiko.config.getpass.getuser")
+    def test_matches_local_username(self, getuser):
+        getuser.return_value = "gandalf"
+        result = load_config("match-localuser").lookup("anything")
+        assert result["hostname"] == "gondor"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_may_be_globbed(self, getuser):
+        for user in ("bilbo", "bombadil"):
+            getuser.return_value = user
+            result = load_config("match-localuser").lookup("anything")
+            assert result["hostname"] == "shire"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_may_be_comma_separated_list(self, getuser):
+        for user in ("aragorn", "frodo"):
+            getuser.return_value = user
+            result = load_config("match-localuser").lookup("anything")
+            assert result["hostname"] == "moria"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_comma_separated_list_may_have_internal_negation(self, getuser):
+        getuser.return_value = "legolas"
+        result = load_config("match-localuser").lookup("anything")
+        assert "port" not in result
+        getuser.return_value = "gimli"
+        result = load_config("match-localuser").lookup("anything")
+        assert result["port"] == "7373"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_may_be_negated(self, getuser):
+        getuser.return_value = "saruman"
+        result = load_config("match-localuser").lookup("anything")
+        assert result["hostname"] == "mordor"
+
+    def test_requires_an_argument(self):
+        with raises(ConfigParseError):
+            load_config("match-localuser-no-arg")
+
+
+class TestComplexMatching(object):
+    # NOTE: this is still a cherry-pick of a few levels of complexity, there's
+    # no point testing literally all possible combinations.
+
+    def test_canonical_exec(self, socket):
+        assert False
+
+    def test_originalhost_host(self):
+        result = load_config("match-complex").lookup("target")
+        assert result["hostname"] == "bogus"
+        assert result["user"] == "rand"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_originalhost_localuser(self, getuser):
+        getuser.return_value = "rando"
+        result = load_config("match-complex").lookup("remote")
+        assert result["user"] == "calrissian"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_everything_but_all(self, getuser):
+        getuser.return_value = "rando"
+        result = load_config("match-complex").lookup("www")
+        assert result["port"] == "7777"
+
+    @patch("paramiko.config.getpass.getuser")
+    def test_everything_but_all_with_some_negated(self, getuser):
+        getuser.return_value = "rando"
+        result = load_config("match-complex").lookup("docs")
+        assert result["port"] == "1234"
+
+    def test_negated_canonical(self, socket):
+        # !canonical in a config that is not canonicalized - does match
+        result = load_config("match-canonical-no").lookup("specific")
+        assert result["user"] == "overload"
+        # !canonical in a config that is canonicalized - does NOT match
+        result = load_config("match-canonical-yes").lookup("www")
+        assert result["user"] == "hidden"
diff --git a/tests/test_util.py b/tests/test_util.py
index 84a48bd3..8ce260d1 100644
--- a/tests/test_util.py
+++ b/tests/test_util.py
@@ -56,6 +56,7 @@ class UtilTest(unittest.TestCase):
             "BufferedFile",
             "Channel",
             "ChannelException",
+            "ConfigParseError",
             "CouldNotCanonicalize",
             "DSSKey",
             "HostKeys",
diff --git a/tests/util.py b/tests/util.py
index 339677aa..9057f516 100644
--- a/tests/util.py
+++ b/tests/util.py
@@ -17,7 +17,7 @@ def _support(filename):
 
 
 def _config(name):
-    return join(tests_dir, "configs", "{}.config".format(name))
+    return join(tests_dir, "configs", name)
 
 
 needs_gssapi = pytest.mark.skipif(