#!/usr/bin/python

#

# CDDL HEADER START

#

# 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 http://www.opensolaris.org/os/licensing.

# 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]

#

# CDDL HEADER END

#

#

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

#

"""Provides the interfaces and exceptions needed to determine which packages

should be installed, updated, or removed to perform a requested operation."""

import operator

import six

import time

import pkg.actions

import pkg.catalog           as catalog

import pkg.client.api_errors as api_errors

import pkg.client.image

import pkg.fmri

import pkg.misc as misc

import pkg.solver

import pkg.version           as version

from collections import defaultdict

# Redefining built-in; pylint: disable=W0622

from functools import reduce

from itertools import chain

from pkg.client.debugvalues import DebugValues

from pkg.client.firmware import Firmware

from pkg.client.pkgdefs import PKG_OP_UNINSTALL, PKG_OP_UPDATE

from pkg.misc import EmptyI, EmptyDict, N_

SOLVER_INIT    = "Initialized"

SOLVER_OXY     = "Not possible"

SOLVER_FAIL    = "Failed"

SOLVER_SUCCESS = "Succeeded"

#

# Constants representing reasons why packages were trimmed from possible set.

# The reasons listed below do *not* always map 1:1 to the error text produced;

# instead, they indicate the 'type' of trim applied. Values below must be

# unique, but can be changed at any time.

#

_TRIM_DEP_MISSING = 0              # no matching pkg version found for dep

_TRIM_DEP_OBSOLETE = 1             # all versions allowed by dep are obsolete

_TRIM_DEP_TRIMMED = 2              # all versions allowed by dep already trimmed

_TRIM_FIRMWARE = 3                 # firmware version requirement

_TRIM_FREEZE = 4                   # pkg not allowed by freeze

_TRIM_INSTALLED_EXCLUDE = 5        # pkg excludes installed pkg

_TRIM_INSTALLED_INC = 6            # not allowed by installed pkg incorporation

_TRIM_INSTALLED_NEWER = 7          # newer version installed already

_TRIM_INSTALLED_ORIGIN = 8         # installed version in image too old

_TRIM_INSTALLED_ROOT_ORIGIN = 9    # installed version in root image too old

_TRIM_PARENT_MISSING = 10          # parent image must have this pkg too

_TRIM_PARENT_NEWER = 11            # parent image has newer version

_TRIM_PARENT_OLDER = 12            # parent image has older version

_TRIM_PARENT_PUB = 13              # parent image has different publisher

_TRIM_PROPOSED_INC = 14            # not allowed by requested pkg incorporation

_TRIM_PROPOSED_PUB = 15            # didn't match requested publisher

_TRIM_PROPOSED_VER = 16            # didn't match requested version

_TRIM_PUB_RANK = 17                # pkg from higher or lower ranked publisher

_TRIM_PUB_STICKY = 18              # pkg publisher != installed pkg publisher

_TRIM_REJECT = 19                  # --reject

_TRIM_UNSUPPORTED = 20             # invalid or unsupported actions

_TRIM_VARIANT = 21                 # unsupported variant (e.g. i386 on sparc)

_TRIM_EXPLICIT_INSTALL = 22        # pkg.depend.explicit-install is true.

_TRIM_SYNCED_INC = 23              # incorporation must be in sync with parent

_TRIM_MAX = 24                     # number of trim constants

class DependencyException(Exception):

        """local exception used to pass failure to match

        dependencies in packages out of nested evaluation"""

        def __init__(self, reason_id, reason, fmris=EmptyI):

                Exception.__init__(self)

                self.__fmris = fmris

                self.__reason_id = reason_id

                self.__reason = reason

        @property

        def fmris(self):

                """The FMRIs related to the exception."""

                return self.__fmris

        @property

        def reason_id(self):

                """A constant indicating why the related FMRIs were rejected."""

                return self.__reason_id

        @property

        def reason(self):

                """A string describing why the related FMRIs were rejected."""

                return self.__reason

class PkgSolver(object):

        """Provides a SAT-based solution solver to determine which packages

        should be installed, updated, or removed to perform a requested

        operation."""

        def __init__(self, cat, installed_dict, pub_ranks, variants, avoids,

            parent_pkgs, progtrack):

                """Create a PkgSolver instance; catalog should contain all

                known pkgs, installed fmris should be a dict of fmris indexed

                by name that define pkgs current installed in the image.

                Pub_ranks dict contains (rank, stickiness, enabled) for each

                publisher.  variants are the current image variants; avoids is

                the set of pkg stems being avoided in the image."""

                # check if we're allowed to use the solver

                if DebugValues["no_solver"]:

                        raise RuntimeError("no_solver set, but solver invoked")

                self.__catalog = cat

                self.__known_incs = set()       # stems with incorporate deps

                self.__publisher = {}           # indexed by stem

                self.__possible_dict = defaultdict(list) # indexed by stem

                self.__pub_ranks = pub_ranks    # rank indexed by pub

                self.__depend_ts = False        # flag used to indicate whether

                                                # any dependencies with

                                                # timestamps were seen; used in

                                                # error output generation

                self.__trim_dict = defaultdict(set) # fmris trimmed from

                                                # consideration

                self.__installed_dict = installed_dict.copy() # indexed by stem

                self.__installed_pkgs = frozenset(self.__installed_dict)

                self.__installed_fmris = frozenset(

                    self.__installed_dict.values())

                self.__pub_trim = {}            # pkg names already

                                                # trimmed by pub.

                self.__removal_fmris = set()    # installed fmris we're

                                                # going to remove

                self.__req_pkg_names = set()    # package names that must be

                                                # present in solution by spec.

                for f in self.__installed_fmris: # record only sticky pubs

                        pub = f.publisher

                        if self.__pub_ranks[pub][1]:

                                self.__publisher[f.pkg_name] = pub

                self.__id2fmri = {}             # map ids -> fmris

                self.__fmri2id = {}             # and reverse

                self.__solver = pkg.solver.msat_solver()

                self.__progtrack = progtrack    # progress tracker

                self.__progitem = None          # progress tracker plan item

                self.__addclause_failure = False

                self.__variant_dict = {}        # fmris -> variant cache

                self.__variants = variants      # variants supported by image

                self.__cache = {}

                self.__actcache = {}

                self.__trimdone = False         # indicate we're finished

                                                # trimming

                self.__fmri_state = {}          # cache of obsolete, renamed

                                                # bits so we can print something

                                                # reasonable

                self.__state = SOLVER_INIT

                self.__iterations = 0

                self.__clauses     = 0

                self.__variables   = 0

                self.__subphasename = None

                self.__timings = []

                self.__start_time = 0

                self.__inc_list = []

                self.__dependents = None

                self.__root_fmris = None        # set of fmris installed in root

                                                # image; used for origin

                                                # dependencies

                self.__avoid_set = avoids.copy()# set of stems we're avoiding

                self.__obs_set = None           # set of obsolete stems

                self.__reject_set = set()       # set of stems we're rejecting

                self.__linked_pkgs = set()      # pkgs that have parent deps

                # Internal cache of created fmri objects.  Used so that the same

                # PkgFmri doesn't need to be created more than once.  This isn't

                # a weakref dictionary because in two of the four places where

                # PkgFmri's are created, the name is extracted and the PkgFmri

                # object is immediately discarded.

                self.__fmridict = {}

                # Packages with explicit install action set to true.

                self.__expl_install_dict = {}

                assert isinstance(parent_pkgs, (type(None), frozenset))

                self.__parent_pkgs = parent_pkgs

                self.__parent_dict = dict()

                if self.__parent_pkgs != None:

                        self.__parent_dict = dict([

                            (f.pkg_name, f)

                            for f in self.__parent_pkgs

                        ])

                # cache of firmware dependencies

                self.__firmware = Firmware()

                self.__triggered_ops = {

                    PKG_OP_UNINSTALL : {

                        PKG_OP_UPDATE    : set(),

                        PKG_OP_UNINSTALL : set(),

                    },

                }

                self.__allowed_downgrades = set()  # allowed downrev FMRIs

                self.__dg_incorp_cache = {}        # cache for downgradable

                                                   # incorp deps

        def __str__(self):

                s = "Solver: ["

                if self.__state in [SOLVER_FAIL, SOLVER_SUCCESS]:

                        s += (" Variables: {0:d} Clauses: {1:d} Iterations: "

                            "{2:d}").format(self.__variables, self.__clauses,

                                self.__iterations)

                s += " State: {0}]".format(self.__state)

                s += "\nTimings: ["

                s += ", ".join([

                    "{0}: {1: 6.3f}".format(*a)

                    for a in self.__timings

                ])

                s += "]"

                if self.__inc_list:

                        incs = "\n\t".join([str(a) for a in self.__inc_list])

                else:

                        incs = "None"

                s += "\nMaintained incorporations: {0}\n".format(incs)

                return s

        def __cleanup(self, rval):

                """Discards all solver information except for that needed to

                show failure information or to stringify the solver object.

                This allows early garbage collection to take place, and should

                be performed after a solution is successfully returned."""

                self.__catalog = None

                self.__installed_dict = {}

                self.__installed_pkgs = frozenset()

                self.__installed_fmris = frozenset()

                self.__publisher = {}

                self.__possible_dict = {}

                self.__pub_ranks = None

                self.__pub_trim = {}

                self.__removal_fmris = set()

                self.__id2fmri = None

                self.__fmri2id = None

                self.__solver = None

                self.__progtrack = None

                self.__addclause_failure = False

                self.__variant_dict = None

                self.__variants = None

                self.__cache = None

                self.__actcache = None

                self.__trimdone = None

                self.__fmri_state = None

                self.__start_time = None

                self.__dependents = None

                self.__fmridict = {}

                self.__firmware = None

                self.__allowed_downgrades = None

                self.__dg_incorp_cache = None

                self.__linked_pkgs = set()

                if DebugValues["plan"]:

                        # Remaining data must be kept.

                        return rval

                self.__trim_dict = None

                return rval

        def __progress(self):

                """Bump progress tracker to indicate processing is active."""

                assert self.__progitem

                self.__progtrack.plan_add_progress(self.__progitem)

        def __start_subphase(self, subphase=None, reset=False):

                """Add timing records and tickle progress tracker.  Ends

                previous subphase if ongoing."""

                if reset:

                        self.__timings = []

                if self.__subphasename is not None:

                        self.__end_subphase()

                self.__start_time = time.time()

                self.__subphasename = "phase {0:d}".format(subphase)

                self.__progress()

        def __end_subphase(self):

                """Mark the end of a solver subphase, recording time taken."""

                now = time.time()

                self.__timings.append((self.__subphasename,

                    now - self.__start_time))

                self.__start_time = None

                self.__subphasename = None

        def __trim_frozen(self, existing_freezes):

                """Trim any packages we cannot update due to freezes."""

                for f, r, _t in existing_freezes:

                        if r:

                                reason = (N_("This version is excluded by a "

                                    "freeze on {0} at version {1}.  The "

                                    "reason for the freeze is: {2}"),

                                    (f.pkg_name, f.version.get_version(

                                        include_build=False), r))

                        else:

                                reason = (N_("This version is excluded by a "

                                    "freeze on {0} at version {1}."),

                                    (f.pkg_name, f.version.get_version(

                                        include_build=False)))

                        self.__trim(self.__comb_auto_fmris(f, dotrim=False)[1],

                            _TRIM_FREEZE, reason)

        def __raise_solution_error(self, no_version=EmptyI, no_solution=EmptyI):

                """Raise a plan exception due to solution errors."""

                solver_errors = None

                if DebugValues["plan"]:

                        solver_errors = self.get_trim_errors()

                raise api_errors.PlanCreationException(no_solution=no_solution,

                    no_version=no_version, solver_errors=solver_errors)

        def __trim_proposed(self, proposed_dict):

                """Remove any versions from proposed_dict that are in trim_dict

                and raise an exception if no matching version of a proposed

                package can be installed at this point."""

                if proposed_dict is None:

                        # Nothing to do.

                        return

                # Used to de-dup errors.

                already_seen = set()

                ret = []

                for name in proposed_dict:

                        tv = self.__dotrim(proposed_dict[name])

                        if tv:

                                proposed_dict[name] = tv

                                continue

                        ret.extend([_("No matching version of {0} can be "

                            "installed:").format(name)])

                        ret.extend(self.__fmri_list_errors(proposed_dict[name],

                            already_seen=already_seen))

                        # continue processing and accumulate all errors

                if ret:

                        self.__raise_solution_error(no_version=ret)

        def __set_removed_and_required_packages(self, rejected, proposed=None):

                """Sets the list of package to be removed from the image, the

                list of packages to reject, the list of packages to avoid

                during the operation, and the list of packages that must not be

                removed from the image.

                'rejected' is a set of package stems to reject.

                'proposed' is an optional set of FMRI objects representing

                packages to install or update.

                Upon return:

                  * self.__removal_fmris will contain the list of FMRIs to be

                    removed from the image due to user request or due to past

                    bugs that caused wrong variant to be installed by mistake.

                  * self.__reject_set will contain the list of packages to avoid

                    or that were rejected by user request as appropriate."""

                if proposed is None:

                        proposed = set()

                else:

                        # remove packages to be installed from avoid_set

                        self.__avoid_set -= proposed

                self.__removal_fmris |= set([

                    self.__installed_dict[name]

                    for name in rejected

                    if name in self.__installed_dict

                ] + [

                    f

                    for f in self.__installed_fmris

                    if not self.__trim_nonmatching_variants(f)

                ])

                self.__reject_set = rejected

                # trim fmris that user explicitly disallowed

                for name in rejected:

                        self.__trim(self.__get_catalog_fmris(name),

                            _TRIM_REJECT,

                            N_("This version rejected by user request"))

                self.__req_pkg_names = (self.__installed_pkgs |

                    proposed) - rejected

                self.__req_pkg_names -= set(

                    f.pkg_name

                    for f in self.__removal_fmris

                )

        def __update_possible_closure(self, possible, excludes,

            full_trim=False, filter_explicit=True):

                """Update the provided possible set of fmris with the transitive

                closure of dependencies that can be satisfied, trimming those

                packages that cannot be installed.

                'possible' is a set of FMRI objects representing all possible

                versions of packages to consider for the operation.

                'full_trim' is an optional boolean indicating whether a full

                trim of the dependency graph should be performed.  This is NOT

                required for the solver to find a solution.  Trimming is only

                needed to reduce the size of clauses and to provide error

                messages.  This requires multiple passes to determine if the

                transitive closure of dependencies can be satisfied.  This is

                not required for correctness (and it greatly increases runtime).

                However, it does greatly improve error messaging for some error

                cases.

                'filter_explicit' is an optional boolean indicating whether

                packages with pkg.depend.explicit-install set to true will be

                filtered out.

                An example of a case where full_trim will be useful (dueling

                incorporations):

                Installed:

                  entire

                    incorporates java-7-incorporation

                Proposed:

                  osnet-incorporation

                    incorporates system/resource-mgmt/dynamic-resource-pools

                  system/resource-mgmt/dynamic-resource-pools

                    requires new version of java not allowed by installed

                      java-7-incorporation"""

                first = True

                while True:

                        tsize = len(self.__trim_dict)

                        res = self.__generate_dependency_closure(

                            possible, excludes=excludes, full_trim=full_trim,

                            filter_explicit=filter_explicit)

                        if first:

                                # The first pass will return the transitive

                                # closure of all dependencies; subsequent passes

                                # are only done for trimming, so need to update

                                # the possible set only on first pass.

                                possible.update(res)

                                first = False

                        nsize = len(self.__trim_dict)

                        if not full_trim or nsize == tsize:

                                # Nothing more to trim.

                                break

                # Remove trimmed items from possible_set.

                possible.difference_update(six.iterkeys(self.__trim_dict))

        def __enforce_unique_packages(self, excludes):

                """Constrain the solver solution so that only one version of

                each package can be installed and generate dependency clauses

                for possible packages."""

                # Generate clauses for only one version of each package, and

                # for dependencies for each package.  Do so for all possible