Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-10-08 22:26:09

0001 #ifndef DataFormats_Common_getThinned_implementation_h
0002 #define DataFormats_Common_getThinned_implementation_h
0003 
0004 #include <algorithm>
0005 #include <cassert>
0006 #include <functional>
0007 #include <optional>
0008 #include <tuple>
0009 #include <variant>
0010 #include <limits>
0011 
0012 #include "DataFormats/Common/interface/ThinnedAssociation.h"
0013 #include "DataFormats/Provenance/interface/BranchID.h"
0014 #include "DataFormats/Provenance/interface/ProductID.h"
0015 #include "DataFormats/Provenance/interface/ThinnedAssociationsHelper.h"
0016 #include "FWCore/Utilities/interface/EDMException.h"
0017 
0018 namespace edm {
0019   class WrapperBase;
0020 
0021   namespace detail {
0022     constexpr unsigned int kThinningDoNotLookForThisIndex = std::numeric_limits<unsigned int>::max();
0023 
0024     class ThinnedOrSlimmedProduct {
0025     public:
0026       ThinnedOrSlimmedProduct() = default;
0027       explicit ThinnedOrSlimmedProduct(WrapperBase const* thinned, unsigned int key)
0028           : thinnedProduct_{thinned}, thinnedKey_{key} {}
0029       explicit ThinnedOrSlimmedProduct(ThinnedAssociation const* slimmed, unsigned int key)
0030           : slimmedAssociation_{slimmed}, thinnedKey_{key} {}
0031 
0032       bool hasThinned() const { return thinnedProduct_ != nullptr; }
0033       bool hasSlimmed() const { return slimmedAssociation_ != nullptr; }
0034 
0035       std::tuple<WrapperBase const*, unsigned int> thinnedProduct() const {
0036         return std::tuple(thinnedProduct_, thinnedKey_);
0037       }
0038 
0039       std::tuple<ThinnedAssociation const*, unsigned int> slimmedAssociation() const {
0040         return std::tuple(slimmedAssociation_, thinnedKey_);
0041       }
0042 
0043     private:
0044       WrapperBase const* thinnedProduct_ = nullptr;
0045       ThinnedAssociation const* slimmedAssociation_ = nullptr;
0046       unsigned int thinnedKey_ = 0;
0047     };
0048 
0049     // This is a helper function to recursively search for a thinned
0050     // product containing the parent key on the same "slimming depth". That
0051     // means that when the recursion encounters a slimmed collection,
0052     // the tree traversal does not proceed onto the children of the
0053     // slimmed collection. Instead, the slimmed ThinnedAssociation is
0054     // recorded for the case that the entire tree on a given "slimming
0055     // depth" does not have any thinned-only collections.
0056     //
0057     // Returns
0058     // - (WrapperBase, unsigned) in case a thinned collection
0059     //   containing the parent key was found.
0060     // - (ThinnedAssociation, unsigned) in case no thinned collections
0061     //   were encountered, but a slimmed collection containing the
0062     //   parent key was found
0063     // - otherwise "null" (i.e. only thinned collections without the
0064     //   parent key, or in absence of thinned collections the slimmed
0065     //   collection without the parent key, or no thinned or slimmed
0066     //   collections)
0067     template <typename F1, typename F2, typename F3>
0068     ThinnedOrSlimmedProduct getThinnedProductOnSlimmingDepth(ProductID const& pid,
0069                                                              unsigned int key,
0070                                                              ThinnedAssociationsHelper const& thinnedAssociationsHelper,
0071                                                              F1 pidToBid,
0072                                                              F2 getThinnedAssociation,
0073                                                              F3 getByProductID) {
0074       BranchID parent = pidToBid(pid);
0075 
0076       auto associatedBranches = thinnedAssociationsHelper.parentBegin(parent);
0077       auto const iEnd = thinnedAssociationsHelper.parentEnd(parent);
0078 
0079       if (associatedBranches == iEnd) {
0080         return ThinnedOrSlimmedProduct();
0081       }
0082       bool const slimmedAllowed = (associatedBranches + 1 == iEnd);
0083       if (slimmedAllowed and associatedBranches->isSlimmed()) {
0084         // Slimmed container can be considered only if it has no (thinned) siblings
0085         ThinnedAssociation const* slimmedAssociation = getThinnedAssociation(associatedBranches->association());
0086         if (slimmedAssociation == nullptr or
0087             associatedBranches->parent() != pidToBid(slimmedAssociation->parentCollectionID())) {
0088           return ThinnedOrSlimmedProduct();
0089         }
0090 
0091         // Does this slimmed container have the element referenced by key?
0092         auto slimmedIndex = slimmedAssociation->getThinnedIndex(key);
0093         if (slimmedIndex.has_value()) {
0094           return ThinnedOrSlimmedProduct(slimmedAssociation, *slimmedIndex);
0095         } else {
0096           return ThinnedOrSlimmedProduct();
0097         }
0098       }
0099 
0100       // Loop over thinned containers which were made by selecting elements from the parent container
0101       for (; associatedBranches != iEnd; ++associatedBranches) {
0102         if (associatedBranches->isSlimmed()) {
0103           continue;
0104         }
0105 
0106         ThinnedAssociation const* thinnedAssociation = getThinnedAssociation(associatedBranches->association());
0107         if (thinnedAssociation == nullptr)
0108           continue;
0109 
0110         if (associatedBranches->parent() != pidToBid(thinnedAssociation->parentCollectionID())) {
0111           continue;
0112         }
0113 
0114         // Does this thinned container have the element referenced by key?
0115         auto thinnedIndex = thinnedAssociation->getThinnedIndex(key);
0116         if (not thinnedIndex.has_value()) {
0117           continue;
0118         }
0119 
0120         // Return a pointer to thinned container if we can find it
0121         ProductID const& thinnedCollectionPID = thinnedAssociation->thinnedCollectionID();
0122         WrapperBase const* thinnedCollection = getByProductID(thinnedCollectionPID);
0123         if (thinnedCollection != nullptr) {
0124           return ThinnedOrSlimmedProduct(thinnedCollection, *thinnedIndex);
0125         }
0126 
0127         // Thinned container is not found, try looking recursively in thinned containers
0128         // which were made by selecting elements from this thinned container.
0129         auto thinnedOrSlimmed = getThinnedProductOnSlimmingDepth(thinnedCollectionPID,
0130                                                                  *thinnedIndex,
0131                                                                  thinnedAssociationsHelper,
0132                                                                  pidToBid,
0133                                                                  getThinnedAssociation,
0134                                                                  getByProductID);
0135         if (thinnedOrSlimmed.hasThinned() or (slimmedAllowed and thinnedOrSlimmed.hasSlimmed())) {
0136           return thinnedOrSlimmed;
0137         }
0138       }
0139 
0140       return ThinnedOrSlimmedProduct();
0141     }
0142 
0143     inline auto makeThinnedIndexes(std::vector<unsigned int> const& keys,
0144                                    std::vector<WrapperBase const*> const& foundContainers,
0145                                    ThinnedAssociation const* thinnedAssociation) {
0146       unsigned const nKeys = keys.size();
0147       std::vector<unsigned int> thinnedIndexes(nKeys, kThinningDoNotLookForThisIndex);
0148       bool hasAny = false;
0149       for (unsigned k = 0; k < nKeys; ++k) {
0150         // Already found this one
0151         if (foundContainers[k] != nullptr) {
0152           continue;
0153         }
0154         // Already know this one is not in this thinned container
0155         if (keys[k] == kThinningDoNotLookForThisIndex) {
0156           continue;
0157         }
0158         // Does the thinned container hold the entry of interest?
0159         if (auto thinnedIndex = thinnedAssociation->getThinnedIndex(keys[k]); thinnedIndex.has_value()) {
0160           thinnedIndexes[k] = *thinnedIndex;
0161           hasAny = true;
0162         }
0163       }
0164       return std::tuple(std::move(thinnedIndexes), hasAny);
0165     }
0166 
0167     // This is a helper function to recursive search ffor thinned
0168     // collections that contain some of the parent keys on the same
0169     // "slimming depth". That means that when the recursion encounters
0170     // a slimmed colleciton, the tree traversal does not proceed onto
0171     // the children of the slimmed collection. Instead, the slimmed
0172     // ThinnedAssociation is recorded for the case that the entire
0173     // tree on a given "slimming depth" does not have any thinned-only
0174     // collections.
0175     //
0176     // Returns a (ThinnedAssociation, vector<unsigned>) in case no
0177     // thinned collections were encountered, but a slimmed collection
0178     // containing at least one of the parent keys was found. The
0179     // returned vector contains keys to the slimmed collection, and
0180     // the output arguments foundContainers and keys are not modified
0181     // in this case.
0182     //
0183     // Otherwise returns a null optional (i.e. any thinned collection
0184     // was encountered, or in absence of thinned collections the
0185     // slimmed collection did not contain any parent keys, or there
0186     // were no thinned or slimmed collections)
0187     template <typename F1, typename F2, typename F3>
0188     std::optional<std::tuple<ThinnedAssociation const*, std::vector<unsigned int>>> getThinnedProductsOnSlimmingDepth(
0189         ProductID const& pid,
0190         ThinnedAssociationsHelper const& thinnedAssociationsHelper,
0191         F1 pidToBid,
0192         F2 getThinnedAssociation,
0193         F3 getByProductID,
0194         std::vector<WrapperBase const*>& foundContainers,
0195         std::vector<unsigned int>& keys) {
0196       BranchID parent = pidToBid(pid);
0197 
0198       auto associatedBranches = thinnedAssociationsHelper.parentBegin(parent);
0199       auto const iEnd = thinnedAssociationsHelper.parentEnd(parent);
0200 
0201       if (associatedBranches == iEnd) {
0202         return std::nullopt;
0203       }
0204       bool const slimmedAllowed = associatedBranches + 1 == iEnd;
0205       if (slimmedAllowed and associatedBranches->isSlimmed()) {
0206         // Slimmed container can be considered only if it has no (thinned) siblings
0207         ThinnedAssociation const* slimmedAssociation = getThinnedAssociation(associatedBranches->association());
0208         if (slimmedAssociation == nullptr or
0209             associatedBranches->parent() != pidToBid(slimmedAssociation->parentCollectionID())) {
0210           return std::nullopt;
0211         }
0212 
0213         auto [slimmedIndexes, hasAny] = makeThinnedIndexes(keys, foundContainers, slimmedAssociation);
0214         // Does this slimmed container have any of the elements referenced by keys?
0215         if (hasAny) {
0216           return std::tuple(slimmedAssociation, std::move(slimmedIndexes));
0217         } else {
0218           return std::nullopt;
0219         }
0220       }
0221 
0222       // Loop over thinned containers which were made by selecting elements from the parent container
0223       for (; associatedBranches != iEnd; ++associatedBranches) {
0224         if (associatedBranches->isSlimmed()) {
0225           continue;
0226         }
0227 
0228         ThinnedAssociation const* thinnedAssociation = getThinnedAssociation(associatedBranches->association());
0229         if (thinnedAssociation == nullptr)
0230           continue;
0231 
0232         if (associatedBranches->parent() != pidToBid(thinnedAssociation->parentCollectionID())) {
0233           continue;
0234         }
0235 
0236         auto [thinnedIndexes, hasAny] = makeThinnedIndexes(keys, foundContainers, thinnedAssociation);
0237         if (!hasAny) {
0238           continue;
0239         }
0240 
0241         // Set the pointers and indexes into the thinned container (if we can find it)
0242         ProductID thinnedCollectionPID = thinnedAssociation->thinnedCollectionID();
0243         WrapperBase const* thinnedCollection = getByProductID(thinnedCollectionPID);
0244         unsigned const nKeys = keys.size();
0245         if (thinnedCollection == nullptr) {
0246           // Thinned container is not found, try looking recursively in thinned containers
0247           // which were made by selecting elements from this thinned container.
0248           auto slimmed = getThinnedProductsOnSlimmingDepth(thinnedCollectionPID,
0249                                                            thinnedAssociationsHelper,
0250                                                            pidToBid,
0251                                                            getThinnedAssociation,
0252                                                            getByProductID,
0253                                                            foundContainers,
0254                                                            thinnedIndexes);
0255           if (slimmedAllowed and slimmed.has_value()) {
0256             return slimmed;
0257           }
0258           for (unsigned k = 0; k < nKeys; ++k) {
0259             if (foundContainers[k] == nullptr)
0260               continue;
0261             if (thinnedIndexes[k] == kThinningDoNotLookForThisIndex)
0262               continue;
0263             keys[k] = thinnedIndexes[k];
0264           }
0265         } else {
0266           for (unsigned k = 0; k < nKeys; ++k) {
0267             if (thinnedIndexes[k] == kThinningDoNotLookForThisIndex)
0268               continue;
0269             keys[k] = thinnedIndexes[k];
0270             foundContainers[k] = thinnedCollection;
0271           }
0272         }
0273       }
0274       return std::nullopt;
0275     }
0276 
0277     // This function provides a common implementation of
0278     // EDProductGetter::getThinnedProduct() for EventPrincipal,
0279     // DataGetterHelper, and BareRootProductGetter.
0280     //
0281     // getThinnedProduct assumes getIt was already called and failed to find
0282     // the product. The input key is the index of the desired element in the
0283     // container identified by ProductID (which cannot be found).
0284     // If the return value is not null, then the desired element was
0285     // found in a thinned container. If the desired element is not
0286     // found, then an optional without a value is returned.
0287     template <typename F1, typename F2, typename F3>
0288     std::optional<std::tuple<WrapperBase const*, unsigned int>> getThinnedProduct(
0289         ProductID const& pid,
0290         unsigned int key,
0291         ThinnedAssociationsHelper const& thinnedAssociationsHelper,
0292         F1 pidToBid,
0293         F2 getThinnedAssociation,
0294         F3 getByProductID) {
0295       auto thinnedOrSlimmed = getThinnedProductOnSlimmingDepth(
0296           pid, key, thinnedAssociationsHelper, pidToBid, getThinnedAssociation, getByProductID);
0297 
0298       if (thinnedOrSlimmed.hasThinned()) {
0299         return thinnedOrSlimmed.thinnedProduct();
0300       } else if (thinnedOrSlimmed.hasSlimmed()) {
0301         auto [slimmedAssociation, slimmedIndex] = thinnedOrSlimmed.slimmedAssociation();
0302         ProductID const& slimmedCollectionPID = slimmedAssociation->thinnedCollectionID();
0303         WrapperBase const* slimmedCollection = getByProductID(slimmedCollectionPID);
0304         if (slimmedCollection == nullptr) {
0305           // Slimmed container is not found, try looking recursively in thinned containers
0306           // which were made by selecting elements from this thinned container.
0307           return getThinnedProduct(slimmedCollectionPID,
0308                                    slimmedIndex,
0309                                    thinnedAssociationsHelper,
0310                                    pidToBid,
0311                                    getThinnedAssociation,
0312                                    getByProductID);
0313         }
0314         return std::tuple(slimmedCollection, slimmedIndex);
0315       }
0316       return std::nullopt;
0317     }
0318 
0319     // This function provides a common implementation of
0320     // EDProductGetter::getThinnedProducts() for EventPrincipal,
0321     // DataGetterHelper, and BareRootProductGetter.
0322     //
0323     // getThinnedProducts assumes getIt was already called and failed to find
0324     // the product. The input keys are the indexes into the container identified
0325     // by ProductID (which cannot be found). On input the WrapperBase pointers
0326     // must all be set to nullptr (except when the function calls itself
0327     // recursively where non-null pointers mark already found elements).
0328     // Thinned containers derived from the product are searched to see
0329     // if they contain the desired elements. For each that is
0330     // found, the corresponding WrapperBase pointer is set and the key
0331     // is modified to be the key into the container where the element
0332     // was found. The WrapperBase pointers might or might not all point
0333     // to the same thinned container.
0334     template <typename F1, typename F2, typename F3>
0335     void getThinnedProducts(ProductID const& pid,
0336                             ThinnedAssociationsHelper const& thinnedAssociationsHelper,
0337                             F1 pidToBid,
0338                             F2 getThinnedAssociation,
0339                             F3 getByProductID,
0340                             std::vector<WrapperBase const*>& foundContainers,
0341                             std::vector<unsigned int>& keys) {
0342       auto slimmed = getThinnedProductsOnSlimmingDepth(
0343           pid, thinnedAssociationsHelper, pidToBid, getThinnedAssociation, getByProductID, foundContainers, keys);
0344       if (slimmed.has_value()) {
0345         // no thinned procucts found, try out slimmed next if one is available
0346         auto [slimmedAssociation, slimmedIndexes] = std::move(*slimmed);
0347         ProductID const& slimmedCollectionPID = slimmedAssociation->thinnedCollectionID();
0348         WrapperBase const* slimmedCollection = getByProductID(slimmedCollectionPID);
0349         unsigned const nKeys = keys.size();
0350         if (slimmedCollection == nullptr) {
0351           getThinnedProducts(slimmedCollectionPID,
0352                              thinnedAssociationsHelper,
0353                              pidToBid,
0354                              getThinnedAssociation,
0355                              getByProductID,
0356                              foundContainers,
0357                              slimmedIndexes);
0358           for (unsigned k = 0; k < nKeys; ++k) {
0359             if (foundContainers[k] == nullptr)
0360               continue;
0361             if (slimmedIndexes[k] == kThinningDoNotLookForThisIndex)
0362               continue;
0363             keys[k] = slimmedIndexes[k];
0364           }
0365         } else {
0366           for (unsigned k = 0; k < nKeys; ++k) {
0367             if (slimmedIndexes[k] == kThinningDoNotLookForThisIndex)
0368               continue;
0369             keys[k] = slimmedIndexes[k];
0370             foundContainers[k] = slimmedCollection;
0371           }
0372         }
0373       }
0374     }
0375 
0376     using GetThinnedKeyFromExceptionFactory = std::function<edm::Exception()>;
0377 
0378     // This function provides a common implementation of
0379     // EDProductGetter::getThinnedKeyFrom() for EventPrincipal,
0380     // DataGetterHelper, and BareRootProductGetter.
0381     //
0382     // The thinned ProductID must come from an existing RefCore. The
0383     // input key is the index of the desired element in the container
0384     // identified by the parent ProductID. Returns an std::variant
0385     // whose contents can be
0386     // - unsigned int for the index in the thinned collection if the
0387     //   desired element was found in the thinned collection
0388     // - function creating an edm::Exception if parent is not a parent
0389     //   of any thinned collection, thinned is not really a thinned
0390     //   collection, or parent and thinned have no thinning
0391     //   relationship
0392     // - std::monostate if thinned is thinned from parent, but the key
0393     //   is not found in the thinned collection
0394     template <typename F>
0395     std::variant<unsigned int, GetThinnedKeyFromExceptionFactory, std::monostate> getThinnedKeyFrom_implementation(
0396         ProductID const& parentID,
0397         BranchID const& parent,
0398         unsigned int key,
0399         ProductID const& thinnedID,
0400         BranchID thinned,
0401         ThinnedAssociationsHelper const& thinnedAssociationsHelper,
0402         F&& getThinnedAssociation) {
0403       // need to explicitly check for equality of parent BranchID,
0404       // because ThinnedAssociationsHelper::parentBegin() uses
0405       // std::lower_bound() that returns a valid iterator in case the
0406       // parent is not found
0407       if (auto iParent = thinnedAssociationsHelper.parentBegin(parent);
0408           iParent == thinnedAssociationsHelper.parentEnd(parent) or iParent->parent() != parent) {
0409         return [parentID]() {
0410           return Exception(errors::InvalidReference)
0411                  << "Parent collection with ProductID " << parentID << " has not been thinned";
0412         };
0413       }
0414 
0415       bool foundParent = false;
0416       std::vector<ThinnedAssociation const*> thinnedAssociationParentage;
0417       while (not foundParent) {
0418         // TODO: be smarter than linear search every time?
0419         auto branchesToThinned = std::find_if(
0420             thinnedAssociationsHelper.begin(), thinnedAssociationsHelper.end(), [&thinned](auto& associatedBranches) {
0421               return associatedBranches.thinned() == thinned;
0422             });
0423         if (branchesToThinned == thinnedAssociationsHelper.end()) {
0424           return [parentID, thinnedID, thinnedIsThinned = not thinnedAssociationParentage.empty()]() {
0425             Exception ex(errors::InvalidReference);
0426             ex << "Requested thinned collection with ProductID " << thinnedID
0427                << " is not thinned from the parent collection with ProductID " << parentID
0428                << " or from any collection thinned from it.";
0429             if (not thinnedIsThinned) {
0430               ex << " In fact, the collection " << thinnedID
0431                  << " passed in as a 'thinned' collection has not been thinned at all.";
0432             }
0433             return ex;
0434           };
0435         }
0436 
0437         ThinnedAssociation const* thinnedAssociation = getThinnedAssociation(branchesToThinned->association());
0438         if (thinnedAssociation == nullptr) {
0439           Exception ex{errors::LogicError};
0440           if (thinnedAssociationParentage.empty()) {
0441             ex << "ThinnedAssociation corresponding to thinned collection with ProductID " << thinnedID
0442                << " not found.";
0443           } else {
0444             ex << "Intermediate ThinnedAssociation between the requested thinned ProductID " << thinnedID
0445                << " and parent " << parentID << " not found.";
0446           }
0447           ex << " This should not happen.\nPlease contact the core framework developers.";
0448           throw ex;
0449         }
0450 
0451         thinnedAssociationParentage.push_back(thinnedAssociation);
0452         if (branchesToThinned->parent() == parent) {
0453           foundParent = true;
0454         } else {
0455           // next iteration with current parent as the thinned collection
0456           thinned = branchesToThinned->parent();
0457         }
0458       }
0459 
0460       // found the parent, now need to rewind the parentage chain to
0461       // find the index in the requested thinned collection
0462       unsigned int thinnedIndex = key;
0463       for (auto iAssociation = thinnedAssociationParentage.rbegin(), iEnd = thinnedAssociationParentage.rend();
0464            iAssociation != iEnd;
0465            ++iAssociation) {
0466         auto optIndex = (*iAssociation)->getThinnedIndex(thinnedIndex);
0467         if (optIndex) {
0468           thinnedIndex = *optIndex;
0469         } else {
0470           return std::monostate{};
0471         }
0472       }
0473       return thinnedIndex;
0474     }
0475 
0476   }  // namespace detail
0477 }  // namespace edm
0478 
0479 #endif