Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-02-14 12:54:34

0001 #include "DataFormats/Provenance/interface/ThinnedAssociationsHelper.h"
0002 #include "DataFormats/Provenance/interface/BranchDescription.h"
0003 #include "FWCore/Utilities/interface/EDMException.h"
0004 #include <algorithm>
0005 
0006 #include <fmt/format.h>
0007 
0008 namespace edm {
0009 
0010   ThinnedAssociationBranches::ThinnedAssociationBranches() {}
0011 
0012   ThinnedAssociationBranches::ThinnedAssociationBranches(BranchID const& parent,
0013                                                          BranchID const& association,
0014                                                          BranchID const& thinned,
0015                                                          bool slimmed)
0016       : parent_(parent), association_(association), thinned_(thinned), slimmed_(slimmed) {}
0017 
0018   ThinnedAssociationsHelper::ThinnedAssociationsHelper() {}
0019 
0020   std::vector<ThinnedAssociationBranches>::const_iterator ThinnedAssociationsHelper::begin() const {
0021     return vThinnedAssociationBranches_.begin();
0022   }
0023 
0024   std::vector<ThinnedAssociationBranches>::const_iterator ThinnedAssociationsHelper::end() const {
0025     return vThinnedAssociationBranches_.end();
0026   }
0027 
0028   std::vector<ThinnedAssociationBranches>::const_iterator ThinnedAssociationsHelper::parentBegin(
0029       BranchID const& parent) const {
0030     ThinnedAssociationBranches target(parent, BranchID(), BranchID(), false);
0031     return std::lower_bound(vThinnedAssociationBranches_.begin(),
0032                             vThinnedAssociationBranches_.end(),
0033                             target,
0034                             [](ThinnedAssociationBranches const& x, ThinnedAssociationBranches const& y) {
0035                               return x.parent() < y.parent();
0036                             });
0037   }
0038 
0039   std::vector<ThinnedAssociationBranches>::const_iterator ThinnedAssociationsHelper::parentEnd(
0040       BranchID const& parent) const {
0041     ThinnedAssociationBranches target(parent, BranchID(), BranchID(), false);
0042     return std::upper_bound(vThinnedAssociationBranches_.begin(),
0043                             vThinnedAssociationBranches_.end(),
0044                             target,
0045                             [](ThinnedAssociationBranches const& x, ThinnedAssociationBranches const& y) {
0046                               return x.parent() < y.parent();
0047                             });
0048   }
0049 
0050   std::vector<ThinnedAssociationBranches>::const_iterator ThinnedAssociationsHelper::lower_bound(
0051       ThinnedAssociationBranches const& branches) const {
0052     return std::lower_bound(
0053         vThinnedAssociationBranches_.begin(),
0054         vThinnedAssociationBranches_.end(),
0055         branches,
0056         [](ThinnedAssociationBranches const& x, ThinnedAssociationBranches const& y) {
0057           return x.parent() < y.parent() ? true : y.parent() < x.parent() ? false : x.association() < y.association();
0058         });
0059   }
0060 
0061   void ThinnedAssociationsHelper::addAssociation(BranchID const& parent,
0062                                                  BranchID const& association,
0063                                                  BranchID const& thinned,
0064                                                  bool slimmed) {
0065     addAssociation(ThinnedAssociationBranches(parent, association, thinned, slimmed));
0066   }
0067 
0068   void ThinnedAssociationsHelper::addAssociation(ThinnedAssociationBranches const& branches) {
0069     vThinnedAssociationBranches_.insert(lower_bound(branches), branches);
0070     if (branches.isSlimmed()) {
0071       try {
0072         ensureSlimmingConstraints();
0073       } catch (edm::Exception& ex) {
0074         ex.addContext("Calling ThinnedAssociationsHelper::addAssociation()");
0075         ex.addAdditionalInfo(fmt::format("When adding a slimmed collection with BranchID {}", branches.thinned().id()));
0076         throw ex;
0077       }
0078     }
0079   }
0080 }  // namespace edm
0081 
0082 namespace {
0083   struct SlimmedCount {
0084     edm::BranchID parent;
0085     int slimmedChildrenCount;
0086   };
0087 
0088   int countSlimmingChildren(edm::ThinnedAssociationsHelper const& helper,
0089                             edm::BranchID const& parent,
0090                             std::vector<SlimmedCount> const& counts);
0091   void addSlimmingChildrenCount(edm::ThinnedAssociationsHelper const& helper,
0092                                 edm::ThinnedAssociationBranches const& branches,
0093                                 std::vector<SlimmedCount> const& counts,
0094                                 int& slimmedCount) {
0095     int slimmingChildren = countSlimmingChildren(helper, branches.thinned(), counts);
0096     if (slimmingChildren > 1) {
0097       throw edm::Exception(edm::errors::LogicError)
0098           << "Encountered a parent collection with BranchID " << branches.thinned().id()
0099           << " that has more than one thinned children that are either themselves slimmed, or have further thinned "
0100              "children that are slimmed. This is not allowed, but this particular check should not fire (it should "
0101              "have been caught earlier). Please contact framework developers.";
0102     }
0103 
0104     if (slimmingChildren == 0 and branches.isSlimmed()) {
0105       ++slimmingChildren;
0106     }
0107 
0108     slimmedCount += slimmingChildren;
0109     if (slimmedCount > 1) {
0110       throw edm::Exception(edm::errors::LogicError)
0111           << "Encountered a parent collection with BranchID " << branches.parent().id()
0112           << " that has more than one thinned children that are either themselves slimmed, or have further thinned "
0113              "children that are slimmed. This is not allowed. In the thinning parentage tree, any parent may have "
0114              "slimmed collections in at most one path to any leaf thinned collections of that parent.";
0115     }
0116   }
0117 
0118   int countSlimmingChildren(edm::ThinnedAssociationsHelper const& helper,
0119                             edm::BranchID const& parent,
0120                             std::vector<SlimmedCount> const& counts) {
0121     auto begin = helper.parentBegin(parent);
0122     auto end = helper.parentEnd(parent);
0123     if (begin == end)
0124       return 0;
0125 
0126     // if already visited, can just return the count
0127     auto pos =
0128         std::lower_bound(counts.begin(), counts.end(), parent, [](SlimmedCount const& c, edm::BranchID const& b) {
0129           return c.parent < b;
0130         });
0131     if (pos != counts.end() && pos->parent == parent) {
0132       return pos->slimmedChildrenCount;
0133     }
0134 
0135     int slimmedCount = 0;
0136     for (auto iItem = begin; iItem != end; ++iItem) {
0137       addSlimmingChildrenCount(helper, *iItem, counts, slimmedCount);
0138     }
0139     return slimmedCount;
0140   }
0141 }  // namespace
0142 
0143 namespace edm {
0144   void ThinnedAssociationsHelper::ensureSlimmingConstraints() const {
0145     // ThinnedAssociationBranches defines an edge between a parent and
0146     // a thinned collection in the parentage tree of the thinned
0147     // collections. It is required that for a given parentage tree
0148     // there is at most one path from the root node to any leaf nodes
0149     // that has slimming edges.
0150 
0151     std::vector<::SlimmedCount> counts;
0152     BranchID prevParent;
0153     std::vector<SlimmedCount>::iterator currentCount;
0154     for (auto iItem = begin(), iEnd = end(); iItem != iEnd; ++iItem) {
0155       if (iItem->parent() == BranchID()) {
0156         continue;
0157       }
0158       if (iItem->parent() == prevParent) {
0159         addSlimmingChildrenCount(*this, *iItem, counts, currentCount->slimmedChildrenCount);
0160       } else {
0161         currentCount = std::lower_bound(
0162             counts.begin(), counts.end(), iItem->parent(), [](SlimmedCount const& c, BranchID const& b) {
0163               return c.parent < b;
0164             });
0165         // has the tree with iItem->parent() as root node already been counted?
0166         if (currentCount != counts.end() && currentCount->parent == iItem->parent()) {
0167           continue;
0168         }
0169         currentCount = counts.insert(currentCount, ::SlimmedCount{iItem->parent(), 0});
0170         addSlimmingChildrenCount(*this, *iItem, counts, currentCount->slimmedChildrenCount);
0171         prevParent = iItem->parent();
0172       }
0173     }
0174   }
0175 
0176   std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> ThinnedAssociationsHelper::associationToBranches()
0177       const {
0178     std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> temp;
0179     for (auto const& item : vThinnedAssociationBranches_) {
0180       temp.push_back(std::make_pair(item.association(), &item));
0181     }
0182     std::sort(temp.begin(),
0183               temp.end(),
0184               [](std::pair<BranchID, ThinnedAssociationBranches const*> const& x,
0185                  std::pair<BranchID, ThinnedAssociationBranches const*> const& y) { return x.first < y.first; });
0186     return temp;
0187   }
0188 
0189   void ThinnedAssociationsHelper::selectAssociationProducts(
0190       std::vector<BranchDescription const*> const& associationDescriptions,
0191       std::set<BranchID> const& keptProductsInEvent,
0192       std::map<BranchID, bool>& keepAssociation) const {
0193     keepAssociation.clear();
0194     // Copy the elements in vThinnedAssociationBranches_ into a vector sorted on
0195     // the association BranchID so we can do searches on that BranchID faster.
0196     std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> assocToBranches = associationToBranches();
0197 
0198     for (auto association : associationDescriptions) {
0199       if (association
0200               ->isAlias()) {  // There is no reason to configure an association product with an EDAlias (ignore and drop them if they exist)
0201         keepAssociation.insert(std::make_pair(association->branchID(), false));
0202       } else {
0203         std::set<BranchID> branchesInRecursion;
0204         shouldKeepAssociation(
0205             association->branchID(), assocToBranches, branchesInRecursion, keptProductsInEvent, keepAssociation);
0206       }
0207     }
0208   }
0209 
0210   bool ThinnedAssociationsHelper::shouldKeepAssociation(
0211       BranchID const& association,
0212       std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> const& associationToBranches,
0213       std::set<BranchID>& branchesInRecursion,
0214       std::set<BranchID> const& keptProductsInEvent,
0215       std::map<BranchID, bool>& keepAssociation) const {
0216     // If we already decided to keep or drop this one, then
0217     // return the same decision.
0218     auto decision = keepAssociation.find(association);
0219     if (decision != keepAssociation.end()) {
0220       return decision->second;
0221     }
0222 
0223     // Be careful not to fall into an infinite loop because
0224     // of a circular recursion.
0225     if (!branchesInRecursion.insert(association).second) {
0226       return false;
0227     }
0228 
0229     // If the thinned collection is being kept then keep the association
0230     auto branches = std::lower_bound(
0231         associationToBranches.begin(),
0232         associationToBranches.end(),
0233         std::make_pair(association, static_cast<ThinnedAssociationBranches const*>(nullptr)),
0234         [](std::pair<BranchID, ThinnedAssociationBranches const*> const& x,
0235            std::pair<BranchID, ThinnedAssociationBranches const*> const& y) { return x.first < y.first; });
0236     // This should never happen
0237     if (branches == associationToBranches.end() || branches->first != association) {
0238       throw edm::Exception(errors::LogicError,
0239                            "ThinnedAssociationHelper::shouldKeepAssociation could not find branches information, "
0240                            "contact Framework developers");
0241     }
0242     BranchID const& thinnedCollection = branches->second->thinned();
0243     if (keptProductsInEvent.find(thinnedCollection) != keptProductsInEvent.end()) {
0244       keepAssociation.insert(std::make_pair(association, true));
0245       return true;
0246     }
0247     // otherwise loop over any associations where the thinned collection
0248     // is also a parent collection and recursively examine those to see
0249     // if their thinned collections are being kept.
0250     auto iterEnd = parentEnd(thinnedCollection);
0251     for (auto match = parentBegin(thinnedCollection); match != iterEnd; ++match) {
0252       if (shouldKeepAssociation(
0253               match->association(), associationToBranches, branchesInRecursion, keptProductsInEvent, keepAssociation)) {
0254         keepAssociation.insert(std::make_pair(association, true));
0255         return true;
0256       }
0257     }
0258     // drop the association
0259     keepAssociation.insert(std::make_pair(association, false));
0260     return false;
0261   }
0262 
0263   void ThinnedAssociationsHelper::requireMatch(ThinnedAssociationBranches const& input) const {
0264     bool foundMatch = false;
0265     for (auto entry = parentBegin(input.parent()), iEnd = parentEnd(input.parent()); entry != iEnd; ++entry) {
0266       if (entry->association() == input.association() && entry->thinned() == input.thinned()) {
0267         foundMatch = true;
0268         break;
0269       }
0270     }
0271     if (!foundMatch) {
0272       throw edm::Exception(
0273           errors::MismatchedInputFiles,
0274           "ThinnedAssociationHelper::requireMatch, Illegal attempt to merge files with different ThinnedAssociations");
0275     }
0276   }
0277 
0278   void ThinnedAssociationsHelper::updateFromPrimaryInput(ThinnedAssociationsHelper const& helper) {
0279     if (vThinnedAssociationBranches_.empty()) {
0280       vThinnedAssociationBranches_ = helper.data();
0281       return;
0282     }
0283     std::vector<ThinnedAssociationBranches> const& inputData = helper.data();
0284     for (auto const& inputEntry : inputData) {
0285       requireMatch(inputEntry);
0286     }
0287   }
0288 
0289   void ThinnedAssociationsHelper::updateFromSecondaryInput(ThinnedAssociationsHelper const& helper,
0290                                                            std::vector<BranchID> const& associationsFromSecondary) {
0291     if (associationsFromSecondary.empty())
0292       return;
0293 
0294     std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> assocToBranches =
0295         helper.associationToBranches();
0296 
0297     for (BranchID const& association : associationsFromSecondary) {
0298       auto branches = std::lower_bound(
0299           assocToBranches.begin(),
0300           assocToBranches.end(),
0301           std::make_pair(association, static_cast<ThinnedAssociationBranches const*>(nullptr)),
0302           [](std::pair<BranchID, ThinnedAssociationBranches const*> const& x,
0303              std::pair<BranchID, ThinnedAssociationBranches const*> const& y) { return x.first < y.first; });
0304       // This should never happen
0305       if (branches == assocToBranches.end() || branches->first != association) {
0306         throw edm::Exception(errors::LogicError,
0307                              "ThinnedAssociationHelper::initAssociationsFromSecondary could not find branches "
0308                              "information, contact Framework developers");
0309       }
0310       requireMatch(*(branches->second));
0311     }
0312   }
0313 
0314   void ThinnedAssociationsHelper::updateFromParentProcess(
0315       ThinnedAssociationsHelper const& parentThinnedAssociationsHelper,
0316       std::map<BranchID, bool> const& keepAssociation,
0317       std::map<BranchID::value_type, BranchID::value_type> const& droppedBranchIDToKeptBranchID) {
0318     clear();
0319     for (auto const& associationBranches : parentThinnedAssociationsHelper.data()) {
0320       auto keep = keepAssociation.find(associationBranches.association());
0321       if (keep != keepAssociation.end() && keep->second) {
0322         BranchID parent = associationBranches.parent();
0323         auto iter = droppedBranchIDToKeptBranchID.find(parent.id());
0324         if (iter != droppedBranchIDToKeptBranchID.end()) {
0325           parent = BranchID(iter->second);
0326         }
0327         BranchID thinned = associationBranches.thinned();
0328         iter = droppedBranchIDToKeptBranchID.find(thinned.id());
0329         if (iter != droppedBranchIDToKeptBranchID.end()) {
0330           thinned = BranchID(iter->second);
0331         }
0332         addAssociation(parent, associationBranches.association(), thinned, associationBranches.isSlimmed());
0333       }
0334     }
0335   }
0336 
0337   void ThinnedAssociationsHelper::initAssociationsFromSecondary(
0338       std::vector<BranchID> const& associationsFromSecondary, ThinnedAssociationsHelper const& fileAssociationsHelper) {
0339     if (associationsFromSecondary.empty())
0340       return;
0341 
0342     std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> assocToBranches =
0343         fileAssociationsHelper.associationToBranches();
0344 
0345     for (BranchID const& association : associationsFromSecondary) {
0346       auto branches = std::lower_bound(
0347           assocToBranches.begin(),
0348           assocToBranches.end(),
0349           std::make_pair(association, static_cast<ThinnedAssociationBranches const*>(nullptr)),
0350           [](std::pair<BranchID, ThinnedAssociationBranches const*> const& x,
0351              std::pair<BranchID, ThinnedAssociationBranches const*> const& y) { return x.first < y.first; });
0352       // This should never happen
0353       if (branches == assocToBranches.end() || branches->first != association) {
0354         throw edm::Exception(errors::LogicError,
0355                              "ThinnedAssociationHelper::initAssociationsFromSecondary could not find branches "
0356                              "information, contact Framework developers");
0357       }
0358       addAssociation(*(branches->second));
0359     }
0360   }
0361 }  // namespace edm