Comment 3 for bug 148586

The problem we were having was that the order of the arguments specified
mattered.

If you tried to run:
apt-get install package1 package2
it put in a different package set than it did when you ran
apt-get install package2 package1

The problem came when package2 had a single dependency that was a
secondary member of an Or group for package1.

IE
Package: Package1
...
Depends: Package3 | Package4

Package: Package2
..
Depends: Package4, PackageX...

By the time it started processing dependencies for Package2 (the second
user-specified argument) it had already decided to install Package3 to
satisfy the (Package3 | Package4) Or group. Then when it saw that
Package2 depends on Package4, it marked that one for install but did not
un-mark Package3.

Since the problem was that the decision was being made to early, what I
did was postpone the decision. I modified
apt-pkg/depcache.cc::MarkInstall to skip Or groups instead of finding a
package to satisfy and recursing. Next I added a new function
apt-pkg/depcache.cc::MarkOrsInstall that is to be called after ALL of
the user-specified arguments had been through MarkInstall. At that point
I could tell if a secondary member of an Or group had already been
marked for install (in other words if it existed as a single dependency
elsewhere). Or groups that have a member already marked are considered
satisfied and only MarkOrsInstall is called for that package. Or groups
that do NOT have a member already marked are satisfied with their first
member and both MarkInstall and MarkOrsInstall are called for that
package.

In order to make this work I also had to make trivial modications to
cmdline/apt-get.cc. The loop in DoInstall now stores each package name
that it processes in a vector so that it may be passed to
TryToInstallOrs (made just for design-consistancy). TryToInstallOrs
calls MarkOrsInstall in apt-pkg/depcache.cc

At any rate, I've attached a diff file for your consideration.
Thank you.