// file : bpkg/pkg-build-collect.hxx -*- C++ -*- // license : MIT; see accompanying LICENSE file #ifndef BPKG_PKG_BUILD_COLLECT_HXX #define BPKG_PKG_BUILD_COLLECT_HXX #include #include #include #include #include #include #include #include #include #include #include #include // find_database_function() #include #include namespace bpkg { // The current configurations dependents being "repointed" to prerequisites // in other configurations, together with their replacement flags. The flag // is true for the replacement prerequisites ("new") and false for the // prerequisites being replaced ("old"). The unamended prerequisites have no // entries. // using repointed_dependents = std::map>; // A "dependency-ordered" list of packages and their prerequisites. // That is, every package on the list only possibly depending on the // ones after it. In a nutshell, the usage is as follows: we first // add one or more packages (the "initial selection"; for example, a // list of packages the user wants built). The list then satisfies all // the prerequisites of the packages that were added, recursively. At // the end of this process we have an ordered list of all the packages // that we have to build, from last to first, in order to build our // initial selection. // // This process is split into two phases: satisfaction of all the // dependencies (the collect_build() function) and ordering of the list // (the order() function). // // During the satisfaction phase, we collect all the packages, their // prerequisites (and so on, recursively) in a map trying to satisfy // any version constraints. Specifically, during this step, we may // "upgrade" or "downgrade" a package that is already in a map as a // result of another package depending on it and, for example, requiring // a different version. If that happens, we make sure that the replaced // package version doesn't apply constraints and/or configuration to its // own dependencies anymore and also that its non-shared dependencies are // gone from the map, recursively (see replaced_versions for details). // One notable side-effect of this process is that all the packages in the // map end up in the list. // // Note that we don't try to do exhaustive constraint satisfaction (i.e., // there is no backtracking). Specifically, if we have two candidate // packages each satisfying a constraint of its dependent package, then if // neither of them satisfy both constraints, then we give up and ask the // user to resolve this manually by explicitly specifying the version that // will satisfy both constraints. // // Also note that we rule out dependency alternatives with enable constraint // that evaluates to false and try to select one satisfactory alternative if // there are multiple of them. In the latter case we pick the first // alternative with packages that are already used (as a result of being // dependencies of other package, requested by the user, or already being // present in the configuration) and fail if such an alternative doesn't // exist. // struct build_package { enum action_type { // Available package is not NULL. // build, // Selected package is not NULL, available package is NULL. // drop, // Selected package is not NULL, available package is NULL. // // This is the "only adjustments" action for a selected package. // Adjustment flags (see below) are unhold (the package should be // treated as a dependency) and reconfigure (dependent package that // needs to be reconfigured because its prerequisite is being // up/down-graded or reconfigured). // // Note that this action is "replaceable" with either drop or build // action but in the latter case the adjustments must be copied over. // adjust }; // An object with an absent action is there to "pre-enter" information // about a package (constraints and flags) in case it is used. // optional action; reference_wrapper db; // Needs to be move-assignable. shared_ptr selected; // NULL if not selected. shared_ptr available; // Can be NULL, fake/transient. // Can be NULL (orphan) or root. If not NULL, then loaded from the // repository configuration database, which may differ from the // configuration the package is being built in. // lazy_shared_ptr repository_fragment; const package_name& name () const { return selected != nullptr ? selected->name : available->id.name; } // If we end up collecting the prerequisite builds for this package, then // this member stores copies of the selected dependency alternatives. The // dependency alternatives for toolchain build-time dependencies and for // dependencies which have all the alternatives disabled are represented // as empty dependency alternatives lists. If present, it is parallel to // the available package's dependencies member. // // Initially nullopt. Can be filled partially if the package prerequisite // builds collection is postponed for any reason (see postponed_packages // and postponed_configurations for possible reasons). // optional dependencies; // Indexes of the selected dependency alternatives stored in the above // dependencies member. // optional> alternatives; // If we end up collecting the prerequisite builds for this package, then // this member stores the skeleton of the package being built. // // Initially nullopt. Can potentially be loaded but with the reflection // configuration variables collected only partially if the package // prerequisite builds collection is postponed for any reason. Can also be // unloaded if the package has no conditional dependencies. // optional skeleton; // If the package prerequisite builds collection is postponed, then this // member stores the references to the enabled alternatives (in available // package) of a dependency being the cause of the postponement together // with their original indexes in the respective dependency alternatives // list. This, in particular, allows us not to re-evaluate conditions // multiple times on the re-collection attempts. // // Note: it shouldn't be very common for a dependency to contain more than // two true alternatives. // using dependency_alternatives_refs = small_vector, size_t>, 2>; optional postponed_dependency_alternatives; // True if the recursive collection of the package has been started or // performed. // // Used by the dependency configuration negotiation machinery which makes // sure that its configuration is negotiated between dependents before its // recursive collection is started (see postponed_configurations for // details). // // Note that the dependencies member cannot be used for that purpose since // it is not always created (think of a system dependency or an existing // dependency that doesn't need its prerequisites re-collection). In a // sense the recursive collection flag is a barrier for the dependency // configuration negotiation. // bool recursive_collection; // Return true if the recursive collection started but has been postponed // for any reason. // bool recursive_collection_postponed () const; // Hold flags. // // Note that we only "increase" the hold_package value that is already in // the selected package, unless the adjust_unhold flag is set (see below). // optional hold_package; // Note that it is perfectly valid for the hold_version flag to be false // while the command line constraint is present in the constraints list // (see below). This may happen if the package build is collected by the // unsatisfied dependency constraints resolution logic (see // try_replace_dependency() in pkg-build.cxx for details). // optional hold_version; // Constraint value plus, normally, the dependent package name/version // that placed this constraint but can also be some other name (in which // case the version is absent) for the initial selection. Currently, the // only valid non-package name is 'command line', which is used when the // package version is constrained by the user on the command line. // // Note that if the dependent is a package name, then this package is // expected to be collected (present in the map). // struct constraint_type { version_constraint value; package_version_key dependent; // False for non-packages. Otherwise, indicates whether the constraint // comes from the selected dependent or not. // bool selected_dependent; // Create constraint for a package dependent. // constraint_type (version_constraint v, database& db, package_name nm, version ver, bool s) : value (move (v)), dependent (db, move (nm), move (ver)), selected_dependent (s) {} // Create constraint for a non-package dependent. // constraint_type (version_constraint v, database& db, string nm) : value (move (v)), dependent (db, move (nm)), selected_dependent (false) {} }; vector constraints; // System package indicator. See also a note in the merge() function. // bool system; // Return the system/distribution package status if this is a system // package (re-)configuration and the package is being managed by the // system package manager (as opposed to user/fallback). Otherwise, return // NULL (so can be used as bool). // // Note on terminology: We call the bpkg package that is being configured // as available from the system as "system package" and we call the // underlying package managed by the system/distribution package manager // as "system/distribution package". See system-package-manager.hxx for // background. // const system_package_status* system_status () const; // As above but only return the status if the package needs to be // installed. // const system_package_status* system_install () const; // If this flag is set and the external package is being replaced with an // external one, then keep its output directory between upgrades and // downgrades. // bool keep_out; // If this flag is set then disfigure the package between upgrades and // downgrades effectively causing a from-scratch reconfiguration. // bool disfigure; // If this flag is set, then don't build this package, only configure. // // Note: use configure_only() to query. // bool configure_only_; // If present, then check out the package into the specified directory // rather than into the configuration directory, if it comes from a // version control-based repository. Optionally, remove this directory // when the package is purged. // optional checkout_root; bool checkout_purge; // Command line configuration variables. Only meaningful for non-system // packages. // strings config_vars; // If present, then the package is requested to be upgraded (true) or // patched (false). Can only be present if the package is already // selected. Can only be false if the selected package version is // patchable. Used by the unsatisfied dependency constraints resolution // logic (see try_replace_dependency() in pkg-build.cxx for details). // optional upgrade; // If true, then this package is requested to be deorphaned. Can only be // true if the package is already selected and is orphaned. Used by the // unsatisfied dependency constraints resolution logic (see // try_replace_dependency() in pkg-build.cxx for details). // bool deorphan; // Set of packages (dependents or dependencies but not a mix) that caused // this package to be built or adjusted. The 'command line' name signifies // user selection and can be present regardless of the // required_by_dependents flag value. // // Note that if this is a package name, then this package is expected to // be collected (present in the map), potentially just pre-entered if // required_by_dependents is false. If required_by_dependents is true, // then the packages in the set are all expected to be collected as builds // (action is build, available is not NULL, etc). // // Also note that if required_by_dependents is true, then all the // dependent package versions in the required_by set are expected to be // known (the version members are not empty). Otherwise (the required_by // set contains dependencies), since it's not always easy to deduce the // dependency versions at the time of collecting the dependent build (see // collect_repointed_dependents() implementation for details), the // dependency package versions are expected to all be unknown. // std::set required_by; // If this flag is true, then required_by contains dependents. // // We need this because required_by packages have different semantics for // different actions: the dependent for regular builds and dependency for // adjustments and repointed dependent reconfiguration builds. Mixing them // would break prompts/diagnostics. // bool required_by_dependents; // Consider a package as user-selected if it is specified on the command // line, is a held package being upgraded via the `pkg-build -u|-p` // command form, or is a dependency being upgraded via the recursively // upgraded dependent. // bool user_selection () const; // Consider a package as user-selected only if it is specified on the // command line as build to hold. // bool user_selection (const vector& hold_pkgs) const; // Return true if the configured package needs to be recollected // recursively. // // This is required if it is being built as a source package and needs to // be up/down-graded and/or reconfigured and has some buildfile clauses, // it is a repointed dependent, or it is already in the process of being // collected. Also configured dependents can be scheduled for recollection // explicitly (see postponed_packages and build_recollect flag for // details). // bool recollect_recursively (const repointed_dependents&) const; // State flags. // uint16_t flags; // Set if we also need to clear the hold package flag. // static const uint16_t adjust_unhold = 0x0001; bool unhold () const { return (flags & adjust_unhold) != 0; } // Set if we also need to reconfigure this package. Note that in some // cases reconfigure is naturally implied. For example, if an already // configured package is being up/down-graded. For such cases we don't // guarantee that the reconfigure flag is set. We only make sure to set it // for cases that would otherwise miss the need for reconfiguration. As a // result, use the reconfigure() predicate which detects both explicit and // implied cases. // // At first, it may seem that this flag is redundant and having the // available package set to NULL is sufficient. But consider the case // where the user asked us to build a package that is already in the // configured state (so all we have to do is pkg-update). Next, add to // this a prerequisite package that is being upgraded. Now our original // package has to be reconfigured. But without this flag we won't know // (available for our package won't be NULL). // static const uint16_t adjust_reconfigure = 0x0002; bool reconfigure () const; // Set if this build action is for repointing of prerequisite. // static const uint16_t build_repoint = 0x0004; // Set if this build action is for re-evaluating of an existing dependent. // static const uint16_t build_reevaluate = 0x0008; // Set if this build action is for recursive re-collecting of an existing // dependent due to deviation, detecting merge configuration cycle, etc. // static const uint16_t build_recollect = 0x0010; // Set if this build action is for replacing of an existing package due to // deorphaning or rebuilding as an archive or directory. // // Note that to replace a package we need to re-fetch it from an existing // repository fragment, archive, or directory (even if its version doesn't // change). // static const uint16_t build_replace = 0x0020; bool replace () const { return (flags & build_replace) != 0; } bool configure_only () const; // Return true if the resulting package will be configured as external. // Optionally, if the package is external, return its absolute and // normalized source root directory path. // bool external (dir_path* = nullptr) const; // If the resulting package will be configured as external, then return // its absolute and normalized source root directory path and nullopt // otherwise. // optional external_dir () const { dir_path r; return external (&r) ? optional (move (r)) : nullopt; } const version& available_version () const; string available_name_version () const { assert (available != nullptr); return package_string (available->id.name, available_version (), system); } string available_name_version_db () const; // Merge constraints, required-by package names, hold_* flags, state // flags, and user-specified options/variables. // void merge (build_package&&); // Initialize the skeleton of a being built package. // package_skeleton& init_skeleton (const common_options&, bool load_old_dependent_config = true, const shared_ptr& override = nullptr); }; using build_package_list = std::list>; using build_package_refs = small_vector, 16>; // Packages with postponed prerequisites collection, for one of the // following reasons: // // - Postponed due to the inability to find a dependency version satisfying // the pre-entered constraint from repositories available to this // package. The idea is that this constraint could still be satisfied from // a repository fragment of some other package (that we haven't processed // yet) that also depends on this prerequisite. // // - Postponed due to the inability to choose between two dependency // alternatives, both having dependency packages which are not yet // selected in the configuration nor being built. The idea is that this // ambiguity could still be resolved after some of those dependency // packages get built via some other dependents. // // - Postponed recollection of configured dependents whose dependencies // up/downgrade causes selection of different dependency alternatives. // This, in particular, may end up in resolving different dependency // packages and affect the dependent and dependency configurations. // // - Postponed recollection of configured dependents for resolving merge // configuration cycles and as a fallback for missed re-evaluations due to // the shadow-based configuration clusters merge (see // collect_build_prerequisites() for details). // // For the sake of testing, make sure the order in the set is stable. // struct compare_build_package { bool operator() (const build_package* x, const build_package* y) const { const package_name& nx (x->name ()); const package_name& ny (y->name ()); if (int d = nx.compare (ny)) return d < 0; return x->db.get () < y->db.get (); } }; using postponed_packages = std::set; // Base for exception types that indicate an inability to collect a package // build because it was collected prematurely (version needs to be replaced, // configuration requires further negotiation, etc). // struct scratch_collection { // Only used for tracing. // const char* description; const package_key* package = nullptr; // Could be NULL. explicit scratch_collection (const char* d): description (d) {} }; // Map of dependency packages whose recursive processing should be postponed // because they have dependents with configuration clauses. // // Note that dependents of such a package that don't have any configuration // clauses are processed right away (since the negotiated configuration may // not affect them) while those that do are postponed in the same way as // those with dependency alternatives (see above). // // Note that the latter kind of dependent is what eventually causes // recursive processing of the dependency packages. Which means we must // watch out for bogus entries in this map which we may still end up with // (e.g., because postponement caused cross-talk between dependency // alternatives). Thus we keep flags that indicate whether we have seen each // type of dependent and then just process dependencies that have the first // (without config) but not the second (with config). // // Note that if any of these flags is set to true, then the dependency is // expected to be collected (present in the build_packages's map; see below // for the class definition). // struct postponed_dependency { bool wout_config; // Has dependent without config. bool with_config; // Has dependent with config. postponed_dependency (bool woc, bool wic) : wout_config (woc), with_config (wic) {} bool bogus () const {return wout_config && !with_config;} }; class postponed_dependencies: public std::map { public: bool has_bogus () const { for (const auto& pd: *this) { if (pd.second.bogus ()) return true; } return false; } // Erase the bogus postponements and throw cancel_postponement, if any. // struct cancel_postponement: scratch_collection { cancel_postponement () : scratch_collection ( "bogus dependency collection postponement cancellation") {} }; void cancel_bogus (tracer& trace) { bool bogus (false); for (auto i (begin ()); i != end (); ) { const postponed_dependency& d (i->second); if (d.bogus ()) { bogus = true; l5 ([&]{trace << "erase bogus postponement " << i->first;}); i = erase (i); } else ++i; } if (bogus) { l5 ([&]{trace << "bogus postponements erased, throwing";}); throw cancel_postponement (); } } }; // Map of the dependencies whose recursive collection is postponed until // their existing dependents re-collection/re-evaluation to the lists of the // respective existing dependents (see collect_build_prerequisites() for // details). // using postponed_existing_dependencies = std::map>; // Set of dependency alternatives which were found unacceptable by the // configuration negotiation machinery and need to be ignored on re- // collection. // // Note that while negotiating the dependency alternative configuration for // a dependent it may turn out that the configuration required by other // dependents is not acceptable for this dependent. It can also happen that // this dependent is involved in a negotiation cycle when two dependents // continuously overwrite each other's configuration during re-negotiation. // Both situations end up with the failure, unless the dependent has some // other reused dependency alternative which can be tried instead. In the // latter case, we note the problematic alternative and re-collect from // scratch. On re-collection the unacceptable alternatives are ignored, // similar to the disabled alternatives. // struct unacceptable_alternative { package_key package; bpkg::version version; pair position; // depends + alternative (1-based) unacceptable_alternative (package_key pkg, bpkg::version ver, pair pos) : package (move (pkg)), version (move (ver)), position (pos) {} bool operator< (const unacceptable_alternative& v) const { if (package != v.package) return package < v.package; if (int r = version.compare (v.version)) return r < 0; return position < v.position; } }; using unacceptable_alternatives = std::set; struct unaccept_alternative: scratch_collection { unaccept_alternative (): scratch_collection ("unacceptable alternative") {} }; // Map of packages which need to be re-collected with the different version // and/or system flag or dropped. // // Note that the initial package version may be adjusted to satisfy // constraints of dependents discovered during the packages collection. It // may also be dropped if this is a dependency which turns out to be unused. // However, it may not always be possible to perform such an adjustment // in-place since the intermediate package version could already apply some // constraints and/or configuration to its own dependencies. Thus, we may // need to note the desired package version information and re-collect from // scratch. // // Also note that during re-collection such a desired version may turn out // to not be a final version and the adjustment/re-collection can repeat. // // And yet, it doesn't seem plausible to ever create a replacement for the // drop: replacing one drop with another is meaningless (all drops are the // same) and replacing the package drop with a package version build can // always been handled in-place. // // On the first glance, the map entries which have not been used for // replacement during the package collection (bogus entries) are harmless // and can be ignored. However, the dependency configuration negotiation // machinery refers to this map and skips existing dependents with // configuration clause which belong to it (see query_existing_dependents() // for details). Thus, if after collection of packages some bogus entries // are present in the map, then it means that we could have erroneously // skipped some existing dependents because of them and so need to erase // these entries and re-collect. // struct replaced_version { // Desired package version, repository fragment, and system flag. // // Both are NULL for the replacement with the drop. // shared_ptr available; lazy_shared_ptr repository_fragment; bool system; // Meaningless for the drop. // True if the entry has been inserted or used for the replacement during // the current (re-)collection iteration. Used to keep track of "bogus" // (no longer relevant) entries. // bool replaced; // Create replacement with the different version. // replaced_version (shared_ptr a, lazy_shared_ptr f, bool s) : available (move (a)), repository_fragment (move (f)), system (s), replaced (true) {} // Create replacement with the drop. // replaced_version (): system (false), replaced (true) {} }; class replaced_versions: public std::map { public: // Erase the bogus replacements and, if any, throw cancel_replacement, if // requested. // struct cancel_replacement: scratch_collection { cancel_replacement () : scratch_collection ("bogus version replacement cancellation") {} }; void cancel_bogus (tracer&, bool scratch); }; // Dependents with their unsatisfactory dependencies and the respective // ignored constraints. // // Note that during the collecting of all the explicitly specified packages // and their dependencies for the build, we may discover that a being // up/downgraded dependency doesn't satisfy all the being reconfigured, // up/downgraded, or newly built dependents. Rather than fail immediately in // such a case, we postpone the failure, add the unsatisfied dependents and // their respective constraints to the unsatisfied dependents list, and // continue the collection/ordering in the hope that these problems will be // resolved naturally as a result of the requested recollection from scratch // or execution plan refinement (dependents will also be up/downgraded or // dropped, dependencies will be up/downgraded to a different versions, // etc). // // Also note that after collecting/ordering of all the explicitly specified // packages and their dependencies for the build we also collect/order their // existing dependents for reconfiguration, recursively. It may happen that // some of the up/downgraded dependencies don't satisfy the version // constraints which some of the existing dependents impose on them. Rather // than fail immediately in such a case, we postpone the failure, add this // dependent and the unsatisfactory dependency to the unsatisfied dependents // list, and continue the collection/ordering in the hope that these // problems will be resolved naturally as a result of the execution plan // refinement. // // And yet, if these problems do not resolve naturally, then we still try to // resolve them by finding dependency versions which satisfy all the imposed // constraints. // // Specifically, we cache such unsatisfied dependents/constraints, pretend // that the dependents don't impose them and proceed with the remaining // collecting/ordering, simulating the plan execution, and evaluating the // dependency versions. After that, if scratch_collection exception has not // been thrown, we check if the execution plan is finalized or a further // refinement is required. In the latter case we drop the cache and proceed // with the next iteration of the execution plan refinement which may // resolve these problems naturally. Otherwise, we pick the first collected // unsatisfactory dependency and try to find the best available version, // considering all the constraints imposed by the user (explicit version // constraint, --patch and/or --deorphan options, etc) as well as by its new // and existing dependents. If the search succeeds, we update an existing // package spec or add the new one to the command line and recollect from // the very beginning. Note that we always add a new spec with the // hold_version flag set to false. If the search fails, then, similarily, we // try to find the replacement for some of the dependency's dependents, // recursively. Note that we track the package build replacements and never // repeat a replacement for the same command line state (which we adjust for // each replacement). If no replacement is deduced, then we roll back the // latest command line adjustment and recollect from the very beginning. If // there are no adjustments left to try, then we give up the resolution // search and report the first encountered unsatisfied (and ignored) // dependency constraint and fail. // // Note that while we are trying to pick a dependent replacement for the // subsequent re-collection, we cannot easily detect if the replacement is // satisfied with the currently collected dependencies since that would // effectively require to collect the replacement (select dependency // alternatives, potentially re-negotiate dependency configurations, // etc). Thus, we only verify that the replacement version satisfies its // currently collected dependents. To reduce the number of potential // dependent replacements to consider, we apply the heuristics and only // consider those dependents which have or may have some satisfaction // problems (not satisfied with a collected dependency, apply a dependency // constraint which is incompatible with other dependents, etc; see // try_replace_dependent() for details). // struct unsatisfied_constraint { // Note: also contains the unsatisfied dependent information. // build_package::constraint_type constraint; // Available package version which satisfies the above constraint. // version available_version; bool available_system; }; struct ignored_constraint { package_key dependency; version_constraint constraint; // Only specified when the failure is postponed during the collection of // the explicitly specified packages and their dependencies. // vector unsatisfied_constraints; vector dependency_chain; ignored_constraint (const package_key& d, const version_constraint& c, vector&& ucs = {}, vector&& dc = {}) : dependency (d), constraint (c), unsatisfied_constraints (move (ucs)), dependency_chain (move (dc)) {} }; struct unsatisfied_dependent { package_key dependent; vector ignored_constraints; }; struct build_packages; class unsatisfied_dependents: public vector { public: // Add a dependent together with the ignored dependency constraint and, // potentially, with the unsatisfied constraints and the dependency chain. // void add (const package_key& dependent, const package_key& dependency, const version_constraint&, vector&& ucs = {}, vector&& dc = {}); // Try to find the dependent entry and return NULL if not found. // unsatisfied_dependent* find_dependent (const package_key&); // Issue the diagnostics for the first unsatisfied (and ignored) // dependency constraint and throw failed. // [[noreturn]] void diag (const build_packages&); }; // List of dependency groups whose recursive processing should be postponed // due to dependents with configuration clauses, together with these // dependents (we will call them package clusters). // // The idea is that configuration for the dependencies in the cluster needs // to be negotiated between the dependents in the cluster. Note that at any // given time during collection a dependency can only belong to a single // cluster. For example, the following dependent/dependencies with // configuration clauses: // // foo: depends: libfoo // bar: depends: libfoo // depends: libbar // baz: depends: libbaz // // End up in the following clusters (see string() below for the cluster // representation): // // {foo bar | libfoo->{foo/1,1 bar/1,1}} // {bar | libbar->{bar/2,1}} // {baz | libbaz->{baz/1,1}} // // Or, another example: // // foo: depends: libfoo // bar: depends: libfoo libbar // baz: depends: libbaz // // {foo bar | libfoo->{foo/1,1 bar/1,1} libbar->{bar/1,1}} // {baz | libbaz->{baz/1,1}} // // Note that a dependent can belong to any given non-negotiated cluster with // only one `depends` position. However, if some dependency configuration is // up-negotiated for a dependent, then multiple `depends` positions will // correspond to this dependent in the same cluster. Naturally, such // clusters are always (being) negotiated. // // Note that adding new dependent/dependencies to the postponed // configurations can result in merging some of the existing clusters if the // dependencies being added intersect with multiple clusters. For example, // adding: // // fox: depends: libbar libbaz // // to the clusters in the second example will merge them into a single // cluster: // // {foo bar baz fox | libfoo->{foo/1,1 bar/1,1} libbar->{bar/1,1 fox/1,1} // libbaz->{baz/1,1 fox/1,1}} // // Also note that we keep track of packages which turn out to be // dependencies of existing (configured) dependents with configuration // clauses. The recursive processing of such packages should be postponed // until negotiation between all the existing and new dependents which may // or may not be present. // class postponed_configuration { public: // The id of the cluster plus the ids of all the clusters that have been // merged into it directly or as their components. // size_t id; small_vector merged_ids; using packages = small_vector; class dependency: public packages { public: pair position; // depends + alternative (1-based) // If true, then another dependency alternative is present and that can // potentially be considered instead of this one (see // unacceptable_alternatives for details). // // Initially nullopt for existing dependents until they are re-evaluated. // optional has_alternative; dependency (const pair& pos, packages deps, optional ha) : packages (move (deps)), position (pos), has_alternative (ha) {} }; class dependent_info { public: bool existing; small_vector dependencies; dependency* find_dependency (pair pos); void add (dependency&&); }; using dependents_map = std::map; dependents_map dependents; packages dependencies; // Dependency configuration. // // Note that this container may not yet contain some entries that are // already in the dependencies member above. And it may already contain // entries that are not yet in dependencies due to the retry_configuration // logic. // package_configurations dependency_configurations; // Shadow clusters. // // See the collect lambda in collect_build_prerequisites() for details. // using positions = small_vector, 1>; using shadow_dependents_map = std::map; shadow_dependents_map shadow_cluster; // Absent -- not negotiated yet, false -- being negotiated, true -- has // been negotiated. // optional negotiated; // The depth of the negotiating recursion (see collect_build_postponed() // for details). // // Note that non-zero depth for an absent negotiated member indicates that // the cluster is in the existing dependents re-evaluation or // configuration refinment phases. // size_t depth = 0; // Add dependencies of a new dependent. // postponed_configuration (size_t i, package_key&& dependent, bool existing, pair position, packages&& deps, optional has_alternative) : id (i) { add (move (dependent), existing, position, move (deps), has_alternative); } // Add dependency of an existing dependent. // postponed_configuration (size_t i, package_key&& dependent, pair position, package_key&& dep) : id (i) { add (move (dependent), true /* existing */, position, packages ({move (dep)}), nullopt /* has_alternative */); } // Add dependencies of a dependent. // // Note: adds the specified dependencies to the end of the configuration // dependencies list suppressing duplicates. // void add (package_key&& dependent, bool existing, pair position, packages&& deps, optional has_alternative); // Return true if any of the configuration's dependents depend on the // specified package. // bool contains_dependency (const package_key& d) const { return find (dependencies.begin (), dependencies.end (), d) != dependencies.end (); } // Return true if this configuration contains any of the specified // dependencies. // bool contains_dependency (const packages&) const; // Return true if this and specified configurations contain any common // dependencies. // bool contains_dependency (const postponed_configuration&) const; // Notes: // // - Adds dependencies of the being merged from configuration to the end // of the current configuration dependencies list suppressing // duplicates. // // - Doesn't change the negotiate member of this configuration. // void merge (postponed_configuration&&); void set_shadow_cluster (postponed_configuration&&); bool is_shadow_cluster (const postponed_configuration&); bool contains_in_shadow_cluster (package_key dependent, pair pos) const; // Return the postponed configuration string representation in the form: // // {[ ]* | [ ]*}['!'|'?'] // // = ['^'] // = ->{/[ /]*} // // The potential trailing '!' or '?' of the configuration representation // indicates that the configuration is negotiated or is being negotiated, // respectively. // // '^' character that may follow a dependent indicates that this is an // existing dependent. // // = ',' // // and are the 1-based serial numbers // of the respective depends value and the dependency alternative in the // dependent's manifest. // // See package_key for details on . // // For example: // // {foo^ bar | libfoo->{foo/2,3 bar/1,1} libbar->{bar/1,1}}! // std::string string () const; private: // Add the specified packages to the end of the dependencies list // suppressing duplicates. // void add_dependencies (packages&&); void add_dependencies (const packages&); }; inline ostream& operator<< (ostream& os, const postponed_configuration& c) { return os << c.string (); } // Note that we could be adding new/merging existing entries while // processing an entry. Thus we use a list. // class postponed_configurations: public std::forward_list { public: // Return the configuration the dependent is added to (after all the // potential configuration merges, etc). // // Also return in second absent if the merge happened due to the shadow // cluster logic (in which case the cluster was/is being negotiated), // false if any non-negotiated or being negotiated clusters has been // merged in, and true otherwise. // // If some configurations needs to be merged and this involves the (being) // negotiated configurations, then merge into the outermost-depth // negotiated configuration (with minimum non-zero depth). // pair> add (package_key dependent, bool existing, pair position, postponed_configuration::packages dependencies, optional has_alternative); // Add new postponed configuration cluster with a single dependency of an // existing dependent. // // Note that it's the caller's responsibility to make sure that the // dependency doesn't already belong to any existing cluster. // void add (package_key dependent, pair position, package_key dependency); postponed_configuration* find (size_t id); // Return address of the cluster the dependency belongs to and NULL if it // doesn't belong to any cluster. // const postponed_configuration* find_dependency (const package_key& d) const; // Return true if all the configurations have been negotiated. // bool negotiated () const; // Translate index to iterator and return the referenced configuration. // postponed_configuration& operator[] (size_t); size_t size () const; private: size_t next_id_ = 1; }; struct build_packages: build_package_list { build_packages () = default; // Copy-constructible and move-assignable (used for snapshoting). // build_packages (const build_packages&); build_packages (build_packages&&) = delete; build_packages& operator= (const build_packages&) = delete; build_packages& operator= (build_packages&&) noexcept (false); // Pre-enter a build_package without an action. No entry for this package // may already exists. // void enter (package_name, build_package); // Return the package pointer if it is already in the map and NULL // otherwise (so can be used as bool). // build_package* entered_build (database& db, const package_name& name) { auto i (map_.find (db, name)); return i != map_.end () ? &i->second.package : nullptr; } build_package* entered_build (const package_key& p) { return entered_build (p.db, p.name); } const build_package* entered_build (database& db, const package_name& name) const { auto i (map_.find (db, name)); return i != map_.end () ? &i->second.package : nullptr; } const build_package* entered_build (const package_key& p) const { return entered_build (p.db, p.name); } // Return NULL if the dependent in the constraint is not a package name // (command line, etc; see build_package::constraint_type for details). // Otherwise, return the dependent package build which is expected to be // collected. // const build_package* dependent_build (const build_package::constraint_type&) const; // Collect the package being built. Return its pointer if this package // version was, in fact, added to the map and NULL if it was already there // and the existing version was preferred or if the package build has been // replaced with the drop. So can be used as bool. // // Consult replaced_vers for an existing version replacement entry and // follow it, if present, potentially collecting the package drop instead. // Ignore the entry if its version doesn't satisfy the specified // dependency constraints or the entry is a package drop and the specified // required-by package names have the "required by dependents" semantics. // In this case it's likely that this replacement will be applied for some // later collect_build() call but can potentially turn out bogus. Note // that a version replacement for a specific package may only be applied // once during the collection iteration. // // Add entry to replaced_vers and throw replace_version if the // existing version needs to be replaced but the new version cannot be // re-collected recursively in-place (see replaced_versions for details). // // Optionally, pass the function which verifies the chosen package // version. It is called before replace_version is potentially thrown or // the recursive collection is performed. The scratch argument is true if // the package version needs to be replaced but in-place replacement is // not possible (see replaced_versions for details). // // Also, in the recursive mode (find database function is not NULL): // // - Use the custom search function to find the package dependency // databases. // // - For the repointed dependents collect the prerequisite replacements // rather than prerequisites being replaced. // // - Call add_priv_cfg_function callback for the created private // configurations. // // Note that postponed_* arguments must all be either specified or not. // The dep_chain argument can be specified in the non-recursive mode (for // the sake of the diagnostics) and must be specified in the recursive // mode. // struct replace_version: scratch_collection { replace_version (): scratch_collection ("package version replacement") {} }; using add_priv_cfg_function = void (database&, dir_path&&); using verify_package_build_function = void (const build_package&, bool scratch); build_package* collect_build (const pkg_build_options&, build_package, replaced_versions&, postponed_configurations&, unsatisfied_dependents&, build_package_refs* dep_chain = nullptr, const function& = nullptr, const function& = nullptr, const repointed_dependents* = nullptr, postponed_packages* postponed_repo = nullptr, postponed_packages* postponed_alts = nullptr, postponed_packages* postponed_recs = nullptr, postponed_existing_dependencies* = nullptr, postponed_dependencies* = nullptr, unacceptable_alternatives* = nullptr, const function& = nullptr); // Collect prerequisites of the package being built recursively. Return // nullopt, unless in the pre-reevaluation mode (see below). // // But first "prune" this process if the package we build is a system one // or is already configured, since that would mean all its prerequisites // are configured as well. Note that this is not merely an optimization: // the package could be an orphan in which case the below logic will fail // (no repository fragment in which to search for prerequisites). By // skipping the prerequisite check we are able to gracefully handle // configured orphans. // // There are, however, some cases when we still need to re-collect // prerequisites of a configured package: // // - For the repointed dependent we still need to collect its prerequisite // replacements to make sure its dependency constraints are satisfied. // // - If configuration variables are specified for the dependent which has // any buildfile clauses in the dependencies, then we need to // re-evaluate them. This can result in a different set of dependencies // required by this dependent (due to conditional dependencies, etc) // and, potentially, for its reconfigured existing prerequisites, // recursively. // // - For an existing dependent being re-evaluated to the specific // dependency position (reeval_pos argument is specified and is not // {0,0}). // // - For an existing dependent being pre-reevaluated (reeval_pos argument // is {0,0}). // // - For an existing dependent being re-collected due to the selected // dependency alternatives deviation, etc which may be caused by its // dependency up/downgrade (see postponed_packages and // build_package::build_recollect flag for details). // // Note that for these cases, as it was said above, we can potentially // fail if the dependent is an orphan, but this is exactly what we need to // do in that case, since we won't be able to re-collect its dependencies. // // Only a single true dependency alternative can be selected per function // call, unless we are (pre-)re-evaluating. Such an alternative can only // be selected if its index in the postponed alternatives list is less // than the specified maximum (used by the heuristics that determines in // which order to process packages with alternatives; if 0 is passed, then // no true alternative will be selected). // // The idea here is to postpone the true alternatives selection till the // end of the packages collection and then try to optimize the overall // resulting selection (over all the dependents) by selecting alternatives // with the lower indexes first (see collect_build_postponed() for // details). // // Always postpone recursive collection of dependencies for a dependent // with configuration clauses, recording them together with the dependent // in postponed_cfgs (see postponed_configurations for details). If it // turns out that some dependency of such a dependent has already been // collected via some other dependent without configuration clauses, then // record it in postponed_deps and throw the postpone_dependency // exception. This exception is handled via re-collecting packages from // scratch, but now with the knowledge about premature dependency // collection. If some dependency already belongs to some non or being // negotiated cluster then throw merge_configuration. If some dependencies // have existing dependents with config clauses which have not been // considered for the configuration negotiation yet, then throw // recollect_existing_dependents exception to re-collect these dependents. // If configuration has already been negotiated between some other // dependents, then up-negotiate the configuration and throw // retry_configuration exception so that the configuration refinement can // be performed. See the collect lambda implementation for details on the // configuration refinement machinery. // // If the reeval_pos argument is specified and is not {0,0}, then // re-evaluate the package to the specified position. In this mode perform // the regular dependency alternative selection and non-recursive // dependency collection. When the specified position is reached, postpone // the collection by recording the dependent together with the // dependencies at that position in postponed_cfgs (see // postponed_configurations for details). If the dependent/dependencies // are added to an already negotiated cluster, then throw // merge_configuration, similar to the regular collection mode (see // above). Also check for the merge configuration cycles (see the function // implementation for details) and throw the merge_configuration_cycle // exception if such a cycle is detected. // // If {0,0} is specified as the reeval_pos argument, then perform the // pre-reevaluation of an existing dependent, requested due to the // specific dependency up/down-grade or reconfiguration (must be passed as // the orig_dep; we call it originating dependency). The main purpose of // this read-only mode is to obtain the position of the earliest selected // dependency alternative with the config clause, if any, which the // re-evaluation needs to be performed to and to determine if such a // re-evaluation is optional (see pre_reevaluate_result for the full // information being retrieved). The re-evaluation is considered to be // optional if the existing dependent has no config clause for the // originating dependency and the enable and reflect clauses do not refer // to any of the dependency configuration variables (which can only be // those which the dependent has the configuration clauses for; see the // bpkg manual for details). The thinking here is that such an existing // dependent may not change any configuration it applies to its // dependencies and thus it doesn't call for any negotiations (note: if // there are config clauses for the upgraded originating dependency, then // the potentially different defaults for its config variables may affect // the configuration this dependent applies to its dependencies). Such a // dependent can also be reconfigured without pre-selection of its // dependency alternatives since pkg-configure is capable of doing that on // its own for such a simple case (see pkg_configure_prerequisites() for // details). Also look for any deviation in the dependency alternatives // selection and throw reevaluation_deviated exception if such a deviation // is detected. Return nullopt if no dependency alternative with the // config clause is selected. // // If the package is a dependency of configured dependents and needs to be // reconfigured (being upgraded, has configuration specified, etc), then // do the following for each such dependent prior to collecting its own // prerequisites: // // - If the dependent is not already being built/dropped, expected to be // built/dropped, and doesn't apply constraints which the dependency // doesn't satisfy anymore, then pre-reevaluate the dependent. // // - If the dependency alternative with configuration clause has been // encountered during the pre-reevaluation, then record it in // postponed_cfgs as a single-dependency cluster with an existing // dependent (see postponed_configurations for details). If the index of // the encountered depends clause is equal/less than the index of the // depends clause the dependency belongs to, then postpone the recursive // collection of this dependency assuming that it will be collected // later, during/after its existing dependent re-evaluation. // // - If the dependency alternatives selection has deviated, then record // the dependent in postponed_recs (so that it can be re-collected // later) and postpone recursive collection of this dependency assuming // that it will be collected later, during its existing dependent // re-collection. Also record this dependency in the postponed existing // dependencies map (postponed_existing_dependencies argument). This way // the caller can track if the postponed dependencies have never been // collected recursively (deviations are too large, etc) and handle this // situation (currently just fail). // // If a dependency alternative configuration cannot be negotiated between // all the dependents, then unaccept_alternative can be thrown (see // unacceptable_alternatives for details). // struct postpone_dependency: scratch_collection { package_key package; explicit postpone_dependency (package_key p) : scratch_collection ("prematurely collected dependency"), package (move (p)) { scratch_collection::package = &package; } }; struct retry_configuration { size_t depth; package_key dependent; }; struct merge_configuration { size_t depth; }; struct merge_configuration_cycle { size_t depth; }; struct reevaluation_deviated {}; struct pre_reevaluate_result { using packages = postponed_configuration::packages; pair reevaluation_position; packages reevaluation_dependencies; bool reevaluation_optional = true; pair originating_dependency_position; }; optional collect_build_prerequisites (const pkg_build_options&, build_package&, build_package_refs& dep_chain, const function&, const function&, const repointed_dependents&, replaced_versions&, postponed_packages* postponed_repo, postponed_packages* postponed_alts, size_t max_alt_index, postponed_packages& postponed_recs, postponed_existing_dependencies&, postponed_dependencies&, postponed_configurations&, unacceptable_alternatives&, unsatisfied_dependents&, optional> reeval_pos = nullopt, const optional& orig_dep = nullopt); void collect_build_prerequisites (const pkg_build_options&, database&, const package_name&, const function&, const function&, const repointed_dependents&, replaced_versions&, postponed_packages& postponed_repo, postponed_packages& postponed_alts, size_t max_alt_index, postponed_packages& postponed_recs, postponed_existing_dependencies&, postponed_dependencies&, postponed_configurations&, unacceptable_alternatives&, unsatisfied_dependents&); // Collect the repointed dependents and their replaced prerequisites, // recursively. // // If a repointed dependent is already pre-entered or collected with an // action other than adjustment, then just mark it for reconfiguration // unless it is already implied. Otherwise, collect the package build with // the repoint sub-action and reconfigure adjustment flag. // void collect_repointed_dependents (const pkg_build_options&, const repointed_dependents&, replaced_versions&, postponed_packages& postponed_repo, postponed_packages& postponed_alts, postponed_packages& postponed_recs, postponed_existing_dependencies&, postponed_dependencies&, postponed_configurations&, unacceptable_alternatives&, unsatisfied_dependents&, const function&, const function&); // Collect the package being dropped. Noop if the specified package is // already being built and its required-by package names have the // "required by dependents" semantics. // // Add entry to replaced_vers and throw replace_version if the existing // version needs to be dropped but this can't be done in-place (see // replaced_versions for details). // void collect_drop (const pkg_build_options&, database&, shared_ptr, replaced_versions&); // Collect the package being unheld. // void collect_unhold (database&, const shared_ptr&); void collect_build_postponed (const pkg_build_options&, replaced_versions&, postponed_packages& postponed_repo, postponed_packages& postponed_alts, postponed_packages& postponed_recs, postponed_existing_dependencies&, postponed_dependencies&, postponed_configurations&, strings& postponed_cfgs_history, unacceptable_alternatives&, unsatisfied_dependents&, const function&, const repointed_dependents&, const function&, postponed_configuration* = nullptr); // If a configured package is being up/down-graded or reconfigured then // that means all its configured dependents could be affected and we have // to reconfigure them. This function examines every such a package that // is already in the map and collects all its configured dependents. We // also need to make sure the dependents are ok with the up/downgrade. If // some dependency constraints are not satisfied, then cache them and // proceed further as if no problematic constraints are imposed (see // unsatisfied_dependents for details). Return the set of the collected // dependents. // // Should we reconfigure just the direct depends or also include indirect, // recursively? Consider this plausible scenario as an example: We are // upgrading a package to a version that provides an additional API. When // its direct dependent gets reconfigured, it notices this new API and // exposes its own extra functionality that is based on it. Now it would // make sense to let its own dependents (which would be our original // package's indirect ones) to also notice this. // std::set collect_dependents (const repointed_dependents&, unsatisfied_dependents&); // Order the previously-collected package with the specified name and // configuration returning its position. // // Recursively order the collected package dependencies, failing if a // dependency cycle is detected. If reorder is true, then reorder this // package to be considered as "early" as possible. // iterator order (database&, const package_name&, const function&, bool reorder = true); void clear (); void clear_order (); // Print all the version constraints (one per line) applied to this // package and its dependents, recursively. The specified package is // expected to be collected (present in the map). Don't print the version // constraints for the same package twice, printing "..." instead. Noop if // there are no constraints for this package. // // Optionally, only print constraints from the selected or being built // dependents (see build_package::constraint_type for details). // void print_constraints (diag_record&, const build_package&, string& indent, std::set& printed, optional selected_dependent = nullopt) const; void print_constraints (diag_record&, const package_key&, string& indent, std::set& printed, optional selected_dependent = nullopt) const; // Verify that builds ordering is consistent across all the data // structures and the ordering expectations are fulfilled (real build // actions are all ordered, etc). // void verify_ordering () const; private: // Return the list of existing dependents that has a configuration clause // for any of the selected alternatives together with the dependencies for // the earliest such an alternative and the originating dependency (for // which the function is called for) position. Return absent dependency // for those dependents which dependency alternatives selection has // deviated (normally due to the dependency up/downgrade). Skip dependents // which are being built and require recursive recollection or dropped // (present in the map) or expected to be built or dropped (present in // rpt_depts or replaced_vers). Also skip dependents which impose the // version constraint on this dependency and the dependency doesn't // satisfy this constraint. Optionally, skip the existing dependents for // which re-evaluation is considered optional (exclude_optional argument; // see pre-reevaluation mode of collect_build_prerequisites() for // details). // // Note that the originating dependency is expected to be collected // (present in the map). // struct existing_dependent { // Dependent. // reference_wrapper db; shared_ptr selected; // Earliest dependency with config clause. // optional dependency; pair dependency_position; // Originating dependency passed to the function call. // package_key originating_dependency; pair originating_dependency_position; }; // This exception is thrown by collect_build_prerequisites() and // collect_build_postponed() to resolve different kinds of existing // dependent re-evaluation related cycles by re-collecting the problematic // dependents from scratch. // struct recollect_existing_dependents { size_t depth; vector dependents; }; vector query_existing_dependents ( tracer&, const pkg_build_options&, database&, const package_name&, bool exclude_optional, const function&, const repointed_dependents&, const replaced_versions&); // Non-recursively collect the dependency of an existing dependent // previously returned by the query_existing_dependents() function call // with the build_package::build_reevaluate flag. // const build_package* collect_existing_dependent_dependency ( const pkg_build_options&, const existing_dependent&, replaced_versions&, postponed_configurations&, unsatisfied_dependents&); // Non-recursively collect an existing non-deviated dependent previously // returned by the query_existing_dependents() function call for the // subsequent re-evaluation. // void collect_existing_dependent ( const pkg_build_options&, const existing_dependent&, postponed_configuration::packages&& dependencies, replaced_versions&, postponed_configurations&, unsatisfied_dependents&); // Non-recursively collect an existing dependent previously returned by // the query_existing_dependents() function call with the // build_package::build_recollect flag and add it to the postponed package // recollections list. Also add the build_package::adjust_reconfigure flag // for the deviated dependents (existing_dependent::dependency is absent). // // Note that after this function call the existing dependent may not be // returned as a result by the query_existing_dependents() function // anymore (due to the build_package::build_recollect flag presence). // void recollect_existing_dependent (const pkg_build_options&, const existing_dependent&, replaced_versions&, postponed_packages& postponed_recs, postponed_configurations&, unsatisfied_dependents&, bool add_required_by); // Skip the dependents collection for the specified dependency if that has // already been done. // // Note that if this function has already been called for this dependency, // then all its dependents are already in the map and their dependency // constraints have been checked. // void collect_dependents (build_package&, const repointed_dependents&, unsatisfied_dependents&, std::set& visited_deps, std::set& result); struct package_ref { database& db; const package_name& name; bool operator== (const package_ref&); }; using package_refs = small_vector; iterator order (database&, const package_name&, package_refs& chain, const function&, bool reorder); private: struct data_type { iterator position; // Note: can be end(), see collect_build(). build_package package; }; class package_map: public std::map { public: using base_type = std::map; using base_type::find; iterator find (database& db, const package_name& pn) { return find (package_key {db, pn}); } const_iterator find (database& db, const package_name& pn) const { return find (package_key {db, pn}); } // Try to find a package build in the dependency configurations (see // database::dependency_configs() for details). Return the end iterator // if no build is found and issue diagnostics and fail if multiple // builds (in multiple configurations) are found. // iterator find_dependency (database&, const package_name&, bool buildtime); }; package_map map_; }; } #endif // BPKG_PKG_BUILD_COLLECT_HXX