}
 
 static int store_updated_refs(const char *raw_url, const char *remote_name,
-               struct ref *ref_map)
+                             int connectivity_checked, struct ref *ref_map)
 {
        FILE *fp;
        struct commit *commit;
        else
                url = xstrdup("foreign");
 
-       rm = ref_map;
-       if (check_connected(iterate_ref_map, &rm, NULL)) {
-               rc = error(_("%s did not send all necessary objects\n"), url);
-               goto abort;
+       if (!connectivity_checked) {
+               rm = ref_map;
+               if (check_connected(iterate_ref_map, &rm, NULL)) {
+                       rc = error(_("%s did not send all necessary objects\n"), url);
+                       goto abort;
+               }
        }
 
        prepare_format_display(ref_map);
 /* Update local refs based on the ref values fetched from a remote */
 static int consume_refs(struct transport *transport, struct ref *ref_map)
 {
+       int connectivity_checked = transport->smart_options
+               ? transport->smart_options->connectivity_checked : 0;
        int ret = store_updated_refs(transport->url,
                                     transport->remote->name,
+                                    connectivity_checked,
                                     ref_map);
        transport_unlock_pack(transport);
        return ret;
 
        argv_array_push(&rev_list.args, "--stdin");
        if (repository_format_partial_clone)
                argv_array_push(&rev_list.args, "--exclude-promisor-objects");
-       argv_array_push(&rev_list.args, "--not");
-       argv_array_push(&rev_list.args, "--all");
+       if (!opt->is_deepening_fetch) {
+               argv_array_push(&rev_list.args, "--not");
+               argv_array_push(&rev_list.args, "--all");
+       }
        argv_array_push(&rev_list.args, "--quiet");
        if (opt->progress)
                argv_array_pushf(&rev_list.args, "--progress=%s",
 
         * Insert these variables into the environment of the child process.
         */
        const char **env;
+
+       /*
+        * If non-zero, check the ancestry chain completely, not stopping at
+        * any existing ref. This is necessary when deepening existing refs
+        * during a fetch.
+        */
+       unsigned is_deepening_fetch : 1;
 };
 
 #define CHECK_CONNECTED_INIT { 0 }
 
 #include "sha1-array.h"
 #include "oidset.h"
 #include "packfile.h"
+#include "connected.h"
 
 static int transfer_unpack_limit = -1;
 static int fetch_unpack_limit = -1;
        oid_array_clear(&ref);
 }
 
+static int iterate_ref_map(void *cb_data, struct object_id *oid)
+{
+       struct ref **rm = cb_data;
+       struct ref *ref = *rm;
+
+       if (!ref)
+               return -1; /* end of the list */
+       *rm = ref->next;
+       oidcpy(oid, &ref->old_oid);
+       return 0;
+}
+
 struct ref *fetch_pack(struct fetch_pack_args *args,
                       int fd[], struct child_process *conn,
                       const struct ref *ref,
                ref_cpy = do_fetch_pack(args, fd, ref, sought, nr_sought,
                                        &si, pack_lockfile);
        reprepare_packed_git(the_repository);
+
+       if (!args->cloning && args->deepen) {
+               struct check_connected_options opt = CHECK_CONNECTED_INIT;
+               struct ref *iterator = ref_cpy;
+               opt.shallow_file = alternate_shallow_file;
+               if (args->deepen)
+                       opt.is_deepening_fetch = 1;
+               if (check_connected(iterate_ref_map, &iterator, &opt)) {
+                       error(_("remote did not send all necessary objects"));
+                       free_refs(ref_cpy);
+                       ref_cpy = NULL;
+                       rollback_lock_file(&shallow_lock);
+                       goto cleanup;
+               }
+               args->connectivity_checked = 1;
+       }
+
        update_shallow(args, ref_cpy, &si);
+cleanup:
        clear_shallow_info(&si);
        return ref_cpy;
 }
 
         * regardless of which object flags it uses (if any).
         */
        unsigned no_dependents:1;
+
+       /*
+        * Because fetch_pack() overwrites the shallow file upon a
+        * successful deepening non-clone fetch, if this struct
+        * specifies such a fetch, fetch_pack() needs to perform a
+        * connectivity check before deciding if a fetch is successful
+        * (and overwriting the shallow file). fetch_pack() sets this
+        * field to 1 if such a connectivity check was performed.
+        *
+        * This is different from check_self_contained_and_connected
+        * in that the former allows existing objects in the
+        * repository to satisfy connectivity needs, whereas the
+        * latter doesn't.
+        */
+       unsigned connectivity_checked:1;
 };
 
 /*
 
        test_cmp expect actual
 '
 
+. "$TEST_DIRECTORY"/lib-httpd.sh
+start_httpd
+
+REPO="$HTTPD_DOCUMENT_ROOT_PATH/repo"
+
+test_expect_success 'shallow fetches check connectivity before writing shallow file' '
+       rm -rf "$REPO" client &&
+
+       git init "$REPO" &&
+       test_commit -C "$REPO" one &&
+       test_commit -C "$REPO" two &&
+       test_commit -C "$REPO" three &&
+
+       git init client &&
+
+       # Use protocol v2 to ensure that shallow information is sent exactly
+       # once by the server, since we are planning to manipulate it.
+       git -C "$REPO" config protocol.version 2 &&
+       git -C client config protocol.version 2 &&
+
+       git -C client fetch --depth=2 "$HTTPD_URL/one_time_sed/repo" master:a_branch &&
+
+       # Craft a situation in which the server sends back an unshallow request
+       # with an empty packfile. This is done by refetching with a shorter
+       # depth (to ensure that the packfile is empty), and overwriting the
+       # shallow line in the response with the unshallow line we want.
+       printf "s/0034shallow %s/0036unshallow %s/" \
+              "$(git -C "$REPO" rev-parse HEAD)" \
+              "$(git -C "$REPO" rev-parse HEAD^)" \
+              >"$HTTPD_ROOT_PATH/one-time-sed" &&
+       test_must_fail git -C client fetch --depth=1 "$HTTPD_URL/one_time_sed/repo" \
+               master:a_branch &&
+
+       # Ensure that the one-time-sed script was used.
+       ! test -e "$HTTPD_ROOT_PATH/one-time-sed" &&
+
+       # Ensure that the resulting repo is consistent, despite our failure to
+       # fetch.
+       git -C client fsck
+'
+
+stop_httpd
+
 test_done
 
        data->got_remote_heads = 0;
        data->options.self_contained_and_connected =
                args.self_contained_and_connected;
+       data->options.connectivity_checked = args.connectivity_checked;
 
        if (refs == NULL)
                ret = -1;
 
        unsigned deepen_relative : 1;
        unsigned from_promisor : 1;
        unsigned no_dependents : 1;
+
+       /*
+        * If this transport supports connect or stateless-connect,
+        * the corresponding field in struct fetch_pack_args is copied
+        * here after fetching.
+        *
+        * See the definition of connectivity_checked in struct
+        * fetch_pack_args for more information.
+        */
+       unsigned connectivity_checked:1;
+
        int depth;
        const char *deepen_since;
        const struct string_list *deepen_not;