Provenance/src/ThinnedAssociationsHelper.cc

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     temp.reserve(vThinnedAssociationBranches_.size());
0180     for (auto const& item : vThinnedAssociationBranches_) {
0181       temp.push_back(std::make_pair(item.association(), &item));
0182     }
0183     std::sort(temp.begin(),
0184               temp.end(),
0185               [](std::pair<BranchID, ThinnedAssociationBranches const*> const& x,
0186                  std::pair<BranchID, ThinnedAssociationBranches const*> const& y) { return x.first < y.first; });
0187     return temp;
0188   }
0189
0190   void ThinnedAssociationsHelper::selectAssociationProducts(
0191       std::vector<BranchDescription const*> const& associationDescriptions,
0192       std::set<BranchID> const& keptProductsInEvent,
0193       std::map<BranchID, bool>& keepAssociation) const {
0194     keepAssociation.clear();
0195     // Copy the elements in vThinnedAssociationBranches_ into a vector sorted on
0196     // the association BranchID so we can do searches on that BranchID faster.
0197     std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> assocToBranches = associationToBranches();
0198
0199     for (auto association : associationDescriptions) {
0200       if (association
0201               ->isAlias()) {  // There is no reason to configure an association product with an EDAlias (ignore and drop them if they exist)
0202         keepAssociation.insert(std::make_pair(association->branchID(), false));
0203       } else {
0204         std::set<BranchID> branchesInRecursion;
0205         shouldKeepAssociation(
0206             association->branchID(), assocToBranches, branchesInRecursion, keptProductsInEvent, keepAssociation);
0207       }
0208     }
0209   }
0210
0211   bool ThinnedAssociationsHelper::shouldKeepAssociation(
0212       BranchID const& association,
0213       std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> const& associationToBranches,
0214       std::set<BranchID>& branchesInRecursion,
0215       std::set<BranchID> const& keptProductsInEvent,
0216       std::map<BranchID, bool>& keepAssociation) const {
0217     // If we already decided to keep or drop this one, then
0218     // return the same decision.
0219     auto decision = keepAssociation.find(association);
0220     if (decision != keepAssociation.end()) {
0221       return decision->second;
0222     }
0223
0224     // Be careful not to fall into an infinite loop because
0225     // of a circular recursion.
0226     if (!branchesInRecursion.insert(association).second) {
0227       return false;
0228     }
0229
0230     // If the thinned collection is being kept then keep the association
0231     auto branches = std::lower_bound(
0232         associationToBranches.begin(),
0233         associationToBranches.end(),
0234         std::make_pair(association, static_cast<ThinnedAssociationBranches const*>(nullptr)),
0235         [](std::pair<BranchID, ThinnedAssociationBranches const*> const& x,
0236            std::pair<BranchID, ThinnedAssociationBranches const*> const& y) { return x.first < y.first; });
0237     // This should never happen
0238     if (branches == associationToBranches.end() || branches->first != association) {
0239       throw edm::Exception(errors::LogicError,
0240                            "ThinnedAssociationHelper::shouldKeepAssociation could not find branches information, "
0241                            "contact Framework developers");
0242     }
0243     BranchID const& thinnedCollection = branches->second->thinned();
0244     if (keptProductsInEvent.find(thinnedCollection) != keptProductsInEvent.end()) {
0245       keepAssociation.insert(std::make_pair(association, true));
0246       return true;
0247     }
0248     // otherwise loop over any associations where the thinned collection
0249     // is also a parent collection and recursively examine those to see
0250     // if their thinned collections are being kept.
0251     auto iterEnd = parentEnd(thinnedCollection);
0252     for (auto match = parentBegin(thinnedCollection); match != iterEnd; ++match) {
0253       if (shouldKeepAssociation(
0254               match->association(), associationToBranches, branchesInRecursion, keptProductsInEvent, keepAssociation)) {
0255         keepAssociation.insert(std::make_pair(association, true));
0256         return true;
0257       }
0258     }
0259     // drop the association
0260     keepAssociation.insert(std::make_pair(association, false));
0261     return false;
0262   }
0263
0264   void ThinnedAssociationsHelper::requireMatch(ThinnedAssociationBranches const& input) const {
0265     bool foundMatch = false;
0266     for (auto entry = parentBegin(input.parent()), iEnd = parentEnd(input.parent()); entry != iEnd; ++entry) {
0267       if (entry->association() == input.association() && entry->thinned() == input.thinned()) {
0268         foundMatch = true;
0269         break;
0270       }
0271     }
0272     if (!foundMatch) {
0273       throw edm::Exception(
0274           errors::MismatchedInputFiles,
0275           "ThinnedAssociationHelper::requireMatch, Illegal attempt to merge files with different ThinnedAssociations");
0276     }
0277   }
0278
0279   void ThinnedAssociationsHelper::updateFromPrimaryInput(ThinnedAssociationsHelper const& helper) {
0280     if (vThinnedAssociationBranches_.empty()) {
0281       vThinnedAssociationBranches_ = helper.data();
0282       return;
0283     }
0284     std::vector<ThinnedAssociationBranches> const& inputData = helper.data();
0285     for (auto const& inputEntry : inputData) {
0286       requireMatch(inputEntry);
0287     }
0288   }
0289
0290   void ThinnedAssociationsHelper::updateFromSecondaryInput(ThinnedAssociationsHelper const& helper,
0291                                                            std::vector<BranchID> const& associationsFromSecondary) {
0292     if (associationsFromSecondary.empty())
0293       return;
0294
0295     std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> assocToBranches =
0296         helper.associationToBranches();
0297
0298     for (BranchID const& association : associationsFromSecondary) {
0299       auto branches = std::lower_bound(
0300           assocToBranches.begin(),
0301           assocToBranches.end(),
0302           std::make_pair(association, static_cast<ThinnedAssociationBranches const*>(nullptr)),
0303           [](std::pair<BranchID, ThinnedAssociationBranches const*> const& x,
0304              std::pair<BranchID, ThinnedAssociationBranches const*> const& y) { return x.first < y.first; });
0305       // This should never happen
0306       if (branches == assocToBranches.end() || branches->first != association) {
0307         throw edm::Exception(errors::LogicError,
0308                              "ThinnedAssociationHelper::initAssociationsFromSecondary could not find branches "
0309                              "information, contact Framework developers");
0310       }
0311       requireMatch(*(branches->second));
0312     }
0313   }
0314
0315   void ThinnedAssociationsHelper::updateFromParentProcess(
0316       ThinnedAssociationsHelper const& parentThinnedAssociationsHelper,
0317       std::map<BranchID, bool> const& keepAssociation,
0318       std::map<BranchID::value_type, BranchID::value_type> const& droppedBranchIDToKeptBranchID) {
0319     clear();
0320     for (auto const& associationBranches : parentThinnedAssociationsHelper.data()) {
0321       auto keep = keepAssociation.find(associationBranches.association());
0322       if (keep != keepAssociation.end() && keep->second) {
0323         BranchID parent = associationBranches.parent();
0324         auto iter = droppedBranchIDToKeptBranchID.find(parent.id());
0325         if (iter != droppedBranchIDToKeptBranchID.end()) {
0326           parent = BranchID(iter->second);
0327         }
0328         BranchID thinned = associationBranches.thinned();
0329         iter = droppedBranchIDToKeptBranchID.find(thinned.id());
0330         if (iter != droppedBranchIDToKeptBranchID.end()) {
0331           thinned = BranchID(iter->second);
0332         }
0333         addAssociation(parent, associationBranches.association(), thinned, associationBranches.isSlimmed());
0334       }
0335     }
0336   }
0337
0338   void ThinnedAssociationsHelper::initAssociationsFromSecondary(
0339       std::vector<BranchID> const& associationsFromSecondary, ThinnedAssociationsHelper const& fileAssociationsHelper) {
0340     if (associationsFromSecondary.empty())
0341       return;
0342
0343     std::vector<std::pair<BranchID, ThinnedAssociationBranches const*>> assocToBranches =
0344         fileAssociationsHelper.associationToBranches();
0345
0346     for (BranchID const& association : associationsFromSecondary) {
0347       auto branches = std::lower_bound(
0348           assocToBranches.begin(),
0349           assocToBranches.end(),
0350           std::make_pair(association, static_cast<ThinnedAssociationBranches const*>(nullptr)),
0351           [](std::pair<BranchID, ThinnedAssociationBranches const*> const& x,
0352              std::pair<BranchID, ThinnedAssociationBranches const*> const& y) { return x.first < y.first; });
0353       // This should never happen
0354       if (branches == assocToBranches.end() || branches->first != association) {
0355         throw edm::Exception(errors::LogicError,
0356                              "ThinnedAssociationHelper::initAssociationsFromSecondary could not find branches "
0357                              "information, contact Framework developers");
0358       }
0359       addAssociation(*(branches->second));
0360     }
0361   }
0362 }  // namespace edm