Re: [gentoo-portage-dev] DepSet

[Zac Medico]

Jason Stubbs wrote:
> On Thursday 08 December 2005 16:44, Zac Medico wrote:
>
>>The middle hunk fixes a problem with block atoms that do not match any
>>packages.  Previously, these atoms would not make it into the okay_atoms set
>>which caused unresolved dependencies.
>
>
> Are you sure about this?

Well, I'm pretty sure. You're analysis seems to be perfectly correct except for 2 points that you haven't accounted for:

1) The atom.key != child.key optimization prevents the atom.match(child) ^ atom.blocks bit from working in the case that my patch handles (block atom that does not match any package).

2) Without the atom.key != child.key optimization, the original algorithm would bail out early, before all packages have been checked.  We need to ensure that the atom does not block _any_ of the packages before we add it to okay_atoms, otherwise, we risk choosing the wrong atomset/combination.  Note that checking all the packages _does_ introduce a performance penalty for block atoms.

> For reference:
>
> @@ -58,12 +58,19 @@
>                                 all_atoms.union_update(atomset)
>                         okay_atoms = sets.Set()
>                         for atom in all_atoms:
> +                               have_blocker=False
>                                 for child in self.pkgs:
>                                         if atom.key != child.key:
>                                                 continue
> -                                       if atom.match(child) ^ atom.blocks:
> -                                               okay_atoms.add(atom)
> +                                       if atom.match(child):
> +                                               if atom.blocks:
> +                                                       have_blocker=True
> +                                               else:
> +                                                       okay_atoms.add(atom)
>                                                 break
> +                               if atom.blocks and not have_blocker:
> +                                       # block atom that does not match any
> packages
> +                                       okay_atoms.add(atom)
>                         for choice in self.pkgs[pkg][0]:
>                                 if choice.issubset(okay_atoms):
>                                         break
>
>
> if atom.match(child) ^ atom.blocks:
>     okay_atoms.add(atom)
>     break
>
> is the same as:
>
> if (atom.match(child) and not atom.blocks) or \
>         (not atom.match(child) or atom.blocks):
>     okay_atoms.add(atom)
>     break
>
>
> have_blocker = False
> ...
>     if atom.match(child):
>         if atom.blocks:
>             have_blocker=True
>         else:
>             okay_atoms.add(atom)
>         break
> if atom.blocks and not have_blocker:
>     okay_atoms.add(atom)
>
> Therefore:
>
> have_blocker = atom.blocks and atom.match(child)
>
> which makes the last check:
>
> if atom.blocks and not (atom.blocks and atom.match(child)):
>     okay_atoms.add(atom)
>
> which is equivalent to:
>
> if atom.blocks and (not atom.blocks or not atom.match(child)):
>     okay_atoms.add(atom)
>
> Removing the impossibility of "atom.blocks and not atom.blocks":
>
> if atom.blocks and not atom.match(child):
>     okay_atoms.add(atom)
>
> Within the loop you have:
>
>     if atom.match(child):
>         if atom.blocks:
>             ...
>         else:
>             okay_atoms.add(atom)
>         break
>
> Which could be represented as:
>
> if atom.match(child) and not atom.blocks:
>     okay_atoms.add(atom)
>
> Combining those two gives:
>
> if atom.blocks and not atom.match(child) or \
>         atom.match(child) and not atom.blocks:
>     okay_atoms.add(atom)
>
> Which is exactly the same thing as the original except seven lines longer...

As I've noted above, not quite the same, due to the atom.key != child.key optimization and checking of _all_ packages for block atoms (without bailing out early).

Zac
-- 
gentoo-portage-dev@g.o mailing list