Skip to main content

Source code file content

Revision: 2918

17178428 pkg history is not capturing release notes
» Project Revision History

» Checkout URL

pkg-gate / src / modules /

Size: 23404 bytes, 1 line
# The contents of this file are subject to the terms of the
# Common Development and Distribution License (the "License").
# You may not use this file except in compliance with the License.
# You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
# or
# See the License for the specific language governing permissions
# and limitations under the License.
# When distributing Covered Code, include this CDDL HEADER in each
# file and include the License file at usr/src/OPENSOLARIS.LICENSE.
# If applicable, add the following below this CDDL HEADER, with the
# fields enclosed by brackets "[]" replaced with your own identifying
# information: Portions Copyright [yyyy] [name of copyright owner]

# Copyright (c) 2009, 2012, Oracle and/or its affiliates. All rights reserved.

# basic variant support

import copy
import itertools
import types

from collections import namedtuple
from pkg._varcet import _allow_variant
from pkg.misc import EmptyI

class Variants(dict):
        # store information on variants; subclass dict
        # and maintain set of keys for performance reasons

        def __init__(self, init=EmptyI):
                self.__keyset = set()
                for i in init:
                        self[i] = init[i]

        def __setitem__(self, item, value):
                dict.__setitem__(self, item, value)

        def __delitem__(self, item):
                dict.__delitem__(self, item)

        # allow_action is provided as a native function (see end of class
        # declaration).

        def pop(self, item, default=None):
                return dict.pop(self, item, default)

        def popitem(self):
                popped = dict.popitem(self)
                return popped

        def setdefault(self, item, default=None):
                if item not in self:
                        self[item] = default
                return self[item]

        def update(self, d):
                for a in d:
                        self[a] = d[a]

        def copy(self):
                return Variants(self)

        def clear(self):
                self.__keyset = set()

Variants.allow_action = types.MethodType(_allow_variant, None, Variants)

# The two classes which follow are used during dependency calculation when
# actions have variants, or the packages they're contained in do.  The
# VariantCombinationTemplate corresponds to information that is encoded in
# the actions.  Specifically, it records what types of variants exist
# (variant.arch or variant.debug) and what values are known to exist for them
# (x86/sparc or debug/non-debug).  The variant types are the keys of the
# dictionary while the variant values are what the keys map to.
# The VariantCombinations class serves a different purpose.  In order to
# determine whether a dependency is satisfied under all combinations of
# variants, it is necessary to track whether each combination has been
# satisfied.  When a VariantCombinations is created, it is provided a
# VariantCombinationTemplate which it uses to seed the combinations of variants.
# To make a single combination instance, for each type of variant, it chooses
# one value and adds it to the instance.  It creates all possible combination
# instances and these are what it uses to track whether all combinations have
# been satisfied.  The class also provides methods for manipulating the
# instances while maintaining consistency between the satisfied set and the
# unsatisfied set.

class VariantCombinationTemplate(Variants):
        """Class for holding a template of variant types and their potential

        def __copy__(self):
                return VariantCombinationTemplate(self)

        def __setitem__(self, item, value):
                """Overrides Variants.__setitem__ to ensure that all values are

                if isinstance(value, list):
                        value = set(value)
                elif not isinstance(value, set):
                        value = set([value])
                Variants.__setitem__(self, item, value)

        def issubset(self, var):
                """Returns whether self is a subset of variant var."""
                res = self.difference(var)
                return not res.type_diffs and not res.value_diffs

        def difference(self, var):
                res = VCTDifference([], [])
                for k in self:
                        if k not in var:
                                for v in self[k] - var[k]:
                                        res.value_diffs.append((k, v))
                return res

        def merge_unknown(self, var):
                """Pull the values for unknown keys in var into self."""
                for name in var:
                        if name not in self:
                                self[name] = var[name]

        def merge_values(self, var):
                """Pull all unknown values of all keys in var into self."""
                for name in var:
                        self.setdefault(name, set([])).update(var[name])

        def __repr__(self):
                return "VariantTemplate(%s)" % dict.__repr__(self)

        def __str__(self):
                s = ""
                for k in sorted(self):
                        t = ",".join(['"%s"' % v for v in sorted(self[k])])
                        s += " %s=%s" % (k, t)
                if s:
                        return s
                        return " <none>"

VCTDifference = namedtuple("VCTDifference", ["type_diffs", "value_diffs"])
# Namedtuple used to store the results of VariantCombinationTemplate
# differences.  The type_diffs field stores the variant types which are in the
# caller and not in the argument to difference.  The value_diffs field stores
# the values for particular types which are in the caller and not in the
# argument to difference.

class VariantCombinations(object):
        """Class for keeping track of which combinations of variant values have
        and have not been satisfied for a particular action."""

        def __init__(self, vct, satisfied):
                """Create an instance of VariantCombinations based on the
                template provided.

                The 'vct' parameter is the template from which to build the

                The 'satisfied' parameter is a boolean which determines whether
                the combinations created from the template will be considered
                satisfied or unsatisfied."""

                assert(isinstance(vct, VariantCombinationTemplate))
                self.__sat_set = set()
                self.__not_sat_set = set()
                tmp = []
                # This builds all combinations of variant values presented in
                # vct.
                for k in sorted(vct):
                        if not tmp:
                                # Initialize tmp with the key-value pairs for
                                # the first key in vct.
                                tmp = [[(k, v)] for v in vct[k]]
                        # For each subsequent key in vct, append each of its
                        # key-value pairs to each of the existing combinations.
                        new_tmp = [
                            exist[:] + [(k, v)] for v in vct[k]
                            for exist in tmp
                        tmp = new_tmp
                # Here is an example of how the loop above would handle a vct
                # of { 1:["a", "b"], 2:["x", "y"], 3:["m", "n"] }
                # First, tmp would be initialized as [[(1, "a")], [(1, "b")]]
                # Next, a new list is created by adding (2, "x") to a copy
                # of each item in tmp, and then (2, "y"). This produces
                # [[(1, "a"), (2, "x")], [(1, "a"), (2, "y")],
                #  [(1, "b"), (2, "x")], [(1, "b"), (2, "y")]]
                # That process is repeated one more time for the 3 key,
                # resulting in:
                # [[(1, "a"), (2, "x"), (3, "m")],
                #  [(1, "a"), (2, "x"), (3, "n")],
                #  [(1, "a"), (2, "y"), (3, "m")],
                #  [(1, "a"), (2, "y"), (3, "n")],
                #  [(1, "b"), (2, "x"), (3, "m")],
                #  [(1, "b"), (2, "x"), (3, "n")],
                #  [(1, "b"), (2, "y"), (3, "m")],
                #  [(1, "b"), (2, "y"), (3, "n")]]
                self.__combinations = [frozenset(l) for l in tmp]
                res = set(self.__combinations)
                if satisfied:
                        self.__sat_set = res
                        self.__not_sat_set = res
                self.__template = copy.copy(vct)
                self.__simpl_template = None

        def template(self):
                return self.__template

        def sat_set(self):
                if not self.__simpl_template:
                        return self.__sat_set
                        return self.__calc_simple(True)

        def not_sat_set(self):
                if not self.__simpl_template:
                        return self.__not_sat_set
                        return self.__calc_simple(False)

        def __copy__(self):
                vc = VariantCombinations(self.__template, True)
                vc.__sat_set = copy.copy(self.__sat_set)
                vc.__not_sat_set = copy.copy(self.__not_sat_set)
                vc.__simpl_template = self.__simpl_template
                vc.__combinations = self.__combinations
                return vc

        def __eq__(self, other):
                return self.__template == other.__template and \
                    self.__sat_set == other.__sat_set and \
                    self.__not_sat_set == other.__not_sat_set and \
                    self.__simpl_template == other.__simpl_template and \
                    self.__combinations == other.__combinations

        def __ne__(self, other):
                return not self.__eq__(other)

        def is_empty(self):
                """Returns whether self was created with any potential variant

                return not self.__sat_set and not self.__not_sat_set
        def issubset(self, vc, satisfied):
                """Returns whether the instances in self are a subset of the
                instances in vc. 'satisfied' determines whether the instances
                compared are drawn from the set of satisfied instances or the
                set of unsatisfied instances."""

                if satisfied:
                        return self.__sat_set.issubset(vc.__sat_set)
                        return self.__not_sat_set.issubset(vc.__not_sat_set)

        def intersects(self, vc, only_not_sat=False):
                """Returns whether an action whose variants are vc could satisfy
                dependencies whose variants are self.

                'only_not_sat' determines whether only the unsatisfied set of
                variants for self is used for comparision.  When only_not_sat
                is True, then intersects returns wether vc would satisfy at
                least one instance which is currently unsatisfied."""

                if self.is_empty() or vc.is_empty():
                        return True
                tmp = self.intersection(vc)
                if only_not_sat:
                        return bool(tmp.__not_sat_set)
                return not tmp.is_empty()
        def intersection(self, vc):
                """Find those variant values in self that are also in var, and
                return them."""
                assert len(vc.not_sat_set) == 0
                res = copy.copy(self)
                res.__sat_set &= vc.__sat_set
                res.__not_sat_set &= vc.__sat_set
                return res

        def separate_satisfied(self, vc):
                """Find those combinations of variants that are satisfied only
                in self, in both self and vc, and only in vc."""

                intersect = None
                only_big = None
                only_small = None

                if self.is_empty() and vc.is_empty():
                        return None, self, None

                if vc.__template.issubset(self.__template):
                        big = self
                        small = vc
                elif self.__template.issubset(vc.__template):
                        big = vc
                        small = self
                        # If one template isn't a subset of, or identical to,
                        # the other, then no meaningful comparison can be
                        # performed.
                        return self, None, vc

                if big.__sat_set & small.__sat_set:
                        intersect = VariantCombinations(big.__template, False)
                        intersect.__sat_set = big.__sat_set & small.__sat_set
                        intersect.__not_sat_set -= intersect.__sat_set

                if big.__sat_set - small.__sat_set:
                        only_big = VariantCombinations(big.__template, False)
                        only_big.__sat_set = big.__sat_set - small.__sat_set
                        only_big.__not_sat_set -= only_big.__sat_set

                if small.__sat_set - big.__sat_set:
                        only_small = VariantCombinations(big.__template, False)
                        only_small.__sat_set = small.__sat_set - big.__sat_set
                        only_small.__not_sat_set -= only_small.__sat_set

                if big == self:
                        return only_big, intersect, only_small
                return only_small, intersect, only_big

        def mark_as_satisfied(self, vc):
                """For all instances in vc, mark those instances as being
                satisfied.  Returns a boolean indicating whether any changes
                have been made."""

                i = vc.__sat_set & self.__not_sat_set
                if not i:
                        return False
                self.__not_sat_set -= i
                self.__sat_set |= i
                return True

        def mark_as_unsatisfied(self, vc):
                """For all satisfied instances in vc, mark those instances as
                being unsatisfied."""

                i = vc.__sat_set & self.__sat_set
                if not i:
                        return False
                self.__sat_set -= i
                self.__not_sat_set |= i
                return True

        def mark_all_as_satisfied(self):
                """Mark all instances as being satisfied."""

                self.__sat_set |= self.__not_sat_set
                self.__not_sat_set = set()

        def is_satisfied(self):
                """Returns whether all variant combinations for this package
                have been satisfied."""

                return not self.__not_sat_set

        def simplify(self, vct, assert_on_different_domains=True):
                """Store the provided VariantCombinationTemplate as the template
                to use when simplifying the combinations."""

                if not self.__template.issubset(vct):
                        self.__simpl_template = {}                
                        if assert_on_different_domains:
                                assert self.__template.issubset(vct), \
                                    "template:%s\nvct:%s" % \
                                    (self.__template, vct)
                self.__simpl_template = vct

        def split_combinations(self):
                """Create one VariantCombination object for each possible
                combination of variants.  This is useful when each combination
                needs to be associated with other information."""

                tmp = []
                for c in self.__combinations:
                        vc = VariantCombinations(self.__template, False)
                        vc.__not_sat_set = set()
                # If there weren't any combinations, then this is an empty
                # variant combination, so just return a copy of ourselves.
                if not tmp:
                return tmp

        def unsatisfied_copy(self):
                """Create a copy of this variant combination, but make sure all
                the variant combinations are marked as unsatisifed."""

                return VariantCombinations(self.__template, False)

        def __calc_simple(self, sat):
                """Given VariantCombinationTemplate to be simplified against,
                reduce the instances to the empty set if the instances cover all
                possible combinations of the template provided.

                A general approach to simplification is currently deemed to
                difficult in the face of arbitrary numbers of variant types and
                arbitrary numbers of variant."""

                if not self.__simpl_template:
                        possibilities = 0
                        possibilities = 1
                        for k in self.__simpl_template:
                                possibilities *= len(self.__simpl_template[k])

                if sat:
                        rel_set = self.__sat_set
                        rel_set = self.__not_sat_set

                # If the size of sat_set or not_sat_set matches the number of
                # possibilities a template can produce, then it can be
                # simplified.
                if possibilities == len(rel_set):
                        return set()
                # If any dependencies are merged, then another pass over the
                # variant types is necessary.  'keep_going' tracks whether that
                # has happened.
                keep_going = True
                while keep_going:
                        keep_going = False
                        # For each variant type ...
                        for variant_name in self.__simpl_template:
                                def exclude_name(item):
                                        return [
                                            (k, v) for k, v in item
                                            if k != variant_name
                                # For sanity, instead of modifying rel_set on
                                # the fly, a new working set is created to which
                                # members or collapsed members of rel_set are
                                # added.
                                new_rel_set = set()

                                # Put the combinations of variant values into
                                # groups so that all members of the group are
                                # identical except for the values for
                                # variant_name.
                                for k, g in itertools.groupby(
                                    sorted(rel_set, key=exclude_name),
                                        g = set(g)

                                        # If there are fewer members in the
                                        # group than there are values, then
                                        # there's no way this value can be
                                        # collapsed.
                                        if len(g) < len(self.__simpl_template[
                                                new_rel_set |= g

                                        # 'expected' is the set of variant
                                        # values that will need to be seen to
                                        # collapse the combinations in g by
                                        # removing the values associated with
                                        # variant_name.
                                        expected = set(self.__simpl_template[

                                        # Check to see whether all possible
                                        # variant values are covered.
                                        for tup in g:
                                                for v_name, v_value in tup:
                                                        if v_name != \

                                        # If not all the possible values have
                                        # been seen, then the variant
                                        # combinations can't be collapsed.
                                        if expected:
                                                new_rel_set |= g
                                        # If they have, then the variant
                                        # combinations can be collapsed by
                                        # removing variant_name.  The key used
                                        # to group the variant combinations,
                                        # 'k', is identical to each of the
                                        # variant combinations with the value
                                        # for variant_name removed, so 'k' is
                                        # added to the new result set.  Since
                                        # some variant combinations have been
                                        # collapsed, then it's necessary to make
                                        # another pass over the variant types as
                                        # 'k' may be able to collapse with other
                                        # variant combinations.
                                        keep_going = True
                                rel_set = new_rel_set
                return rel_set

        def __repr__(self):
                return "VC Sat:%s Unsat:%s" % (sorted(self.__sat_set),
Please Confirm