Bug#685215: Apt pinning is broken

[Kernc <kerncece@gmail.com>]

I'd like to propose an algorithm that, if I'm not mistaken, results in above
policy.

Presuppositions
---------------
A general form rule or stanza is one that has "Package: *" AND "Pin:
<anything-except version>".

A specific form rule or stanza is one that has "Package: <package-list>" OR
"Pin: version" where <package-list> is a space-separated list of glob() or
regular expressions.

Above is in accordance with current documentation.

Algorithm
---------
Input = list of actionable packages, e.g. the space-separated list of
packages passed to apt-get install/remove/... along with all dependencies

Preferences = parse all Dir::Etc::preferences and Dir::Etc::preferencesparts,
sorting all general forms before all specific forms. Preferences must also
contain rules for APT::Default-Release or matching command-line switch.

for package in Input:
  for rule in Preferences.general_form_rules:
    if contains(rule.source, package):
      set_priority(<package,
                    package_version_in(package, rule.source),
                    rule.source>, rule.priority)

  # more specific rules may overwrite general ones
  for rule in Preferences.specific_form_rules:
    if (rule.is_version_pin &&
        versions_match(package, rule.version)):
      if matches(package, rule.name):
        for source in get_sources_for(package,
                                      versions_match(package,
                                                     rule.version)):
          set_priority(<package,
                        versions_match(package, rule.version),
                        source>, rule.priority)
    else:  # not rule.is_version_pin
      if matches(package, rule.name):
        set_priority(<package,
                      package_version_in(package, rule.source),
                      rule.source>, rule.priority)

  package.candidate = max_version(max_priority(package))


  # the rest is as currently implemented...
  if (package.candidate.version < package.installed_version &&
      package.candidate.priority < 1000):
    error 'need priority over 1000 to downgrade'
  ...


I'd like to comment briefly on some of the above functions:
package_version_in(pkg, src) --- returns the version of pkg in src
versions_match(pkg, ver) --- returns pkg versions that matches ver glob if any
get_sources_for(pkg, ver) --- returns sources that contain pkg with version
in ver
matches(pkg, name) --- name can be a list of glob-like expressions

This is my take on what the algorithm roughly could look like. I agree it
looks kind of scripty, and I don't know exactly how easily this translates to
C++. Further, I'm not sure the algorithm works with all apt actions besides
simple install or upgrade. But I promise to implement an external solver
working as proposed in comment #2 if someone fixes the policy so that
EDSP/CUDF dump contains appropriate package pins.

I believe that with above-like algorithm, and some further documentation
effort, the bugs listed in OP can be finally marked as fixed, apt leading
Debian, as it always has, to an even brighter future.

But I fully admit to having little knowledge about apt inner working, Debian
packaging, Debian packaging policy, Debian release cycle, etc., I just want
to help the issue get resolved. :-)

Please contribute your views, questions, concerns, ideas...
And my $50 offer remains wide open. Please feel free to chip in.