Be sure to lock purely optional dependencies

Previously all features were traversed when adding information to the lockfile,
but the traversal forgot to add optional dependencies that did not have a
corresponding feature.

Closes #801

This is temporarily rebased on #776 to build.