       # In case no lock was given, we will use the local lock
       # which is potentially stale. So remote.deps/2 needs to always
       # check if the data it finds in the lock is actually valid.
-      all(main, apps, callback, rest, lock, env, fn dep ->
-        if cached = deps[dep.app] do
-          {:loaded, cached}
-        else
-          {:unloaded, dep, remote.deps(dep, lock)}
-        end
-      end)
+      {deps, rest, lock} =
+        all(main, apps, callback, rest, lock, env, fn dep ->
+          if cached = deps[dep.app] do
+            {:loaded, cached}
+          else
+            {:unloaded, dep, remote.deps(dep, lock)}
+          end
+        end)
+
+      {reject_non_fullfilled_optional(deps), rest, lock}
     else
-      {deps, rest, lock}
+      {reject_non_fullfilled_optional(deps), rest, lock}
     end
   end
 

    Enum.all?(keys, &(Keyword.fetch(opts1, &1) == Keyword.fetch(opts2, &1)))
  end

  defp reject_non_fullfilled_optional(children, upper_breadths) do
    Enum.reject children, fn %Mix.Dep{app: app, opts: opts} ->
      opts[:optional] && not(app in upper_breadths)

              {Mix.Dep.Loader.load(dep, children), rest, lock}
          end

        {acc, rest, lock} =
          all(t, [dep|acc], upper_breadths, current_breadths, callback, rest, lock, env, cache)

        deps = reject_non_fullfilled_optional(dep.deps, current_breadths)
        new_breadths = Enum.map(deps, &(&1.app)) ++ current_breadths
        all(deps, acc, current_breadths, new_breadths, callback, rest, lock, env, cache)
    end
  end

