From c5c1a25ab6d0e509e893d737a679ac47949df2f6 Mon Sep 17 00:00:00 2001 From: Yong He Date: Thu, 18 Jan 2024 16:46:00 -0800 Subject: Capability def parsing & codegen + disjoint sets (#3451) * Capability def parsing & codegen + disjoint sets This change adds a capability definition file, and a code generator to produce C++ code that defines the capability enums and necessary data structures around the capabilities. Extends the existing CapabilitySet class to support expressing disjoint sets of capabilities. This sets up for the next change that will enhance our type checking with reasoning of capability requirements. * Fix cmake. * Fix warning. * Fix. * Fix isBetterForTarget to prefer less specialized option. * Fix. * Fix premake. * Fix intrinsic. * Fix vs sln file. --------- Co-authored-by: Yong He --- source/slang/slang-capability.cpp | 703 ++++++++++++++++++++++++++------------ 1 file changed, 493 insertions(+), 210 deletions(-) (limited to 'source/slang/slang-capability.cpp') diff --git a/source/slang/slang-capability.cpp b/source/slang/slang-capability.cpp index 28dea8d23..a3f8157e7 100644 --- a/source/slang/slang-capability.cpp +++ b/source/slang/slang-capability.cpp @@ -14,7 +14,7 @@ namespace Slang // We are going to divide capability atoms into a few categories. // -enum class CapabilityAtomFlavor : int32_t +enum class CapabilityNameFlavor : int32_t { // A concrete capability atom is something that a target // can directly support, where the presence of the feature @@ -42,102 +42,68 @@ enum class CapabilityAtomFlavor : int32_t Alias, }; -// Certain capability atoms will conflict with one another, -// such that a concrete target should never be able to support -// both. -// -// It is possible in theory to define "conflicting" capabilities -// in terms of the inheritance graph, but that makes checking -// for conflicts more difficult. -// -// Instead, we are going to allow each capability to define a -// mask to indicate group(s) of conflicting capabilities it -// belongs to. Two different capability atoms that have -// overlapping masks will be considered to conflict. -// -enum class CapabilityAtomConflictMask : uint32_t -{ - // By default, most capability atoms do not conflict with one another. - None = 0, - - // Capability atoms that reprsent target code generation formats always conflict. - // (e.g., you cannot generate both HLSL and C++ output at once) - TargetFormat = 1 << 0, - - // Capability atoms that represent GLSL ray tracing extensions conflict with - // one another (we only want to use one such extension at a time). - RayTracingExtension = 1 << 1, - - // Capability atoms that represent GLSL fragment shader barycentric extensions conflict with - // one another (we only want to use one such extension at a time). - FragmentShaderBarycentricExtension = 1 << 2, -}; - -// For simplicity in building up our data structure representing -// all capability atoms, we will limit the number of bases that -// a capability atom is allowed to inherit from. -// -static const int kCapabilityAtom_MaxBases = 4; - // The macros in the `slang-capability-defs.h` file will be used // to fill out a `static const` array of information about each // capability atom. // struct CapabilityAtomInfo { - /// The API-/language-exposed name of the capability. - char const* name; + /// The API-/language-exposed name of the capability. + char const* name; - /// Flavor of atom: concrete, abstract, or alias - CapabilityAtomFlavor flavor; + /// Flavor of atom: concrete, abstract, or alias + CapabilityNameFlavor flavor; - /// A mask to indicate which other categories of atoms this one conflicts with - CapabilityAtomConflictMask conflictMask; + /// If the atom is a direct descendent of an abstract base, keep that for reference here. + CapabilityName abstractBase; - /// Ranking to use when deciding if this atom is a "better" one to select. + /// Ranking to use when deciding if this atom is a "better" one to select. uint32_t rank; - /// Base atoms this one "inherits" from (terminated with `Invalid` if not all entries used). - CapabilityAtom bases[kCapabilityAtom_MaxBases]; + /// Canonical representation in the form of disjunction-of-conjunction of atoms. + ArrayView> canonicalRepresentation; }; -// -static const CapabilityAtomInfo kCapabilityAtoms[Int(CapabilityAtom::Count)] = -{ - { "invalid", CapabilityAtomFlavor::Concrete, CapabilityAtomConflictMask::None, 0, { CapabilityAtom::Invalid, CapabilityAtom::Invalid, CapabilityAtom::Invalid, CapabilityAtom::Invalid } }, -#define SLANG_CAPABILITY_ATOM(ENUMERATOR, NAME, FLAVOR, CONFLICT, RANK, BASE0, BASE1, BASE2, BASE3) \ - { #NAME, CapabilityAtomFlavor::FLAVOR, CapabilityAtomConflictMask::CONFLICT, RANK, { CapabilityAtom::BASE0, CapabilityAtom::BASE1, CapabilityAtom::BASE2, CapabilityAtom::BASE3 } }, -#include "slang-capability-defs.h" -}; +#include "slang-generated-capability-defs-impl.h" - /// Get the extended information structure for the given capability `atom` +static CapabilityAtom asAtom(CapabilityName name) +{ + SLANG_ASSERT((CapabilityAtom)name < CapabilityAtom::Count); + return (CapabilityAtom)name; +} + +/// Get the extended information structure for the given capability `atom` +static CapabilityAtomInfo const& _getInfo(CapabilityName atom) +{ + SLANG_ASSERT(Int(atom) < Int(CapabilityName::Count)); + return kCapabilityNameInfos[Int(atom)]; +} static CapabilityAtomInfo const& _getInfo(CapabilityAtom atom) { SLANG_ASSERT(Int(atom) < Int(CapabilityAtom::Count)); - return kCapabilityAtoms[Int(atom)]; + return kCapabilityNameInfos[Int(atom)]; } -void getCapabilityAtomNames(List& ioNames) +void getCapabilityNames(List& ioNames) { - ioNames.setCount(Count(CapabilityAtom::Count)); - for (Index i = 0; i < Count(CapabilityAtom::Count); ++i) + ioNames.reserve(Count(CapabilityName::Count)); + for (Index i = 0; i < Count(CapabilityName::Count); ++i) { - ioNames[i] = UnownedStringSlice(_getInfo(CapabilityAtom(i)).name); + if (_getInfo(CapabilityName(i)).flavor != CapabilityNameFlavor::Abstract) + { + ioNames.add(UnownedStringSlice(_getInfo(CapabilityName(i)).name)); + } } } -CapabilityAtom findCapabilityAtom(UnownedStringSlice const& name) +bool lookupCapabilityName(const UnownedStringSlice& str, CapabilityName& value); + +CapabilityName findCapabilityName(UnownedStringSlice const& name) { - // For now we are implementing a linear search over the - // array of capability atoms to perform name lookup. - // - for( Index i = 0; i < Index(CapabilityAtom::Count); ++i ) - { - auto& capInfo = _getInfo(CapabilityAtom(i)); - if(name == UnownedTerminatedStringSlice(capInfo.name)) - return CapabilityAtom(i); - } - return CapabilityAtom::Invalid; + CapabilityName result; + if (!lookupCapabilityName(name, result)) + return CapabilityName::Invalid; + return result; } bool isCapabilityDerivedFrom(CapabilityAtom atom, CapabilityAtom base) @@ -147,29 +113,22 @@ bool isCapabilityDerivedFrom(CapabilityAtom atom, CapabilityAtom base) return true; } - const auto& info = kCapabilityAtoms[Index(atom)]; - - for (auto cur : info.bases) + const auto& info = kCapabilityNameInfos[Index(atom)]; + for (auto cur : info.canonicalRepresentation) { - if (cur == CapabilityAtom::Invalid) - { - return false; - } - - if (isCapabilityDerivedFrom(cur, base)) - { - return true; - } + for (auto cbase : cur) + if (asAtom(cbase) == base) + return true; } return false; } // -// CapabilitySet +// CapabilityConjunctionSet // -// The current design choice in `CapabilitySet` is that it stores +// The current design choice in `CapabilityConjunctionSet` is that it stores // an expanded, deduplicated, and sorted list of the capability // atoms in the set. "Expanded" here means that it includes the // transitive closure of the inheritance graph of those atoms. @@ -179,90 +138,64 @@ bool isCapabilityDerivedFrom(CapabilityAtom atom, CapabilityAtom base) // binary searches to efficiently detect whether an atom // is present in a set. -CapabilitySet::CapabilitySet() +CapabilityConjunctionSet::CapabilityConjunctionSet() {} -CapabilitySet::CapabilitySet(Int atomCount, CapabilityAtom const* atoms) +CapabilityConjunctionSet::CapabilityConjunctionSet(Int atomCount, CapabilityAtom const* atoms) { _init(atomCount, atoms); } -CapabilitySet::CapabilitySet(CapabilityAtom atom) +CapabilityConjunctionSet::CapabilityConjunctionSet(CapabilityAtom atom) { _init(1, &atom); } -CapabilitySet::CapabilitySet(List const& atoms) +CapabilityConjunctionSet::CapabilityConjunctionSet(List const& atoms) { _init(atoms.getCount(), atoms.getBuffer()); } -CapabilitySet CapabilitySet::makeEmpty() +CapabilityConjunctionSet CapabilityConjunctionSet::makeEmpty() { - return CapabilitySet(); + return CapabilityConjunctionSet(); } -CapabilitySet CapabilitySet::makeInvalid() +CapabilityConjunctionSet CapabilityConjunctionSet::makeInvalid() { // An invalid capability set will always be a singleton // set of the `Invalid` atom, and we will construct // the set directly rather than use the more expensive // logic in `_init()`. // - CapabilitySet result; + CapabilityConjunctionSet result; result.m_expandedAtoms.add(CapabilityAtom::Invalid); return result; } - /// Helper routine for `CapabilitySet::_init`. - /// - /// Recursively add all atoms implied by `atom` to `ioExpandedAtoms`. - /// -static void _addAtomsRec( - CapabilityAtom atom, - HashSet& ioExpandedAtoms) +void CapabilityConjunctionSet::_init(Int atomCount, CapabilityAtom const* atoms) { - auto& atomInfo = _getInfo(atom); - - // The first step is to add `atom` itself, *unless* - // it is an alias, because an alias shouldn't impact - // whether one set is considered a subset/superset of - // another. - // - if(atomInfo.flavor != CapabilityAtomFlavor::Alias) - { - ioExpandedAtoms.add(atom); - } - - // Next we add all the atoms transitively implied by `atom`. - // - for(auto baseAtom : atomInfo.bases) - { - // Note: the list of `bases` is a fixed-size array, but - // can be terminated with `Invalid` to indicate that - // not all of the entries are being used. - // - // If we see the sentinel, then we know we are at the end - // of the list. - // - if(baseAtom == CapabilityAtom::Invalid) - break; - - _addAtomsRec(baseAtom, ioExpandedAtoms); - } -} - -void CapabilitySet::_init(Int atomCount, CapabilityAtom const* atoms) -{ - // In order to fill in the expanded and deduplicated - // set of atoms, we will use an explicit hash set - // and then recursively walk the tree of atoms and - // their bases. + // We will use an explicit hash set to deduplicate input atoms. // HashSet expandedAtomsSet; for(Int i = 0; i < atomCount; ++i) { - _addAtomsRec(atoms[i], expandedAtomsSet); + if (expandedAtomsSet.add(atoms[i])) + { + auto& info = _getInfo(atoms[i]); + + // Add the base items that this atom implies. + if (info.canonicalRepresentation.getCount() == 1) + { + // The atom must have only one conjunction. + SLANG_ASSERT(info.canonicalRepresentation.getCount() == 1); + + for (auto base : info.canonicalRepresentation[0]) + { + expandedAtomsSet.add(asAtom(base)); + } + } + } } // We can then translate the set of atoms into a list, @@ -276,7 +209,7 @@ void CapabilitySet::_init(Int atomCount, CapabilityAtom const* atoms) m_expandedAtoms.sort(); } -void CapabilitySet::calcCompactedAtoms(List& outAtoms) const +void CapabilityConjunctionSet::calcCompactedAtoms(List& outAtoms) const { // A "compacted" list of atoms is one that starts with // the "expanded" list and removes any atoms that are @@ -294,13 +227,18 @@ void CapabilitySet::calcCompactedAtoms(List& outAtoms) const for( auto atom : m_expandedAtoms ) { auto& atomInfo = _getInfo(atom); - for(auto baseAtom : atomInfo.bases) + if (atomInfo.canonicalRepresentation.getCount() != 1) { - // Note: dealing with possible early termination of the `bases` list. - if(baseAtom == CapabilityAtom::Invalid) - break; + // If the atom is not a single conjunction, skip. + continue; + } + for(auto baseAtom : atomInfo.canonicalRepresentation[0]) + { + // Note: don't add atom itself into redundant set. + if(asAtom(baseAtom) == atom) + continue; - redundantAtomsSet.add(baseAtom); + redundantAtomsSet.add(asAtom(baseAtom)); } } @@ -318,7 +256,7 @@ void CapabilitySet::calcCompactedAtoms(List& outAtoms) const } } -bool CapabilitySet::isEmpty() const +bool CapabilityConjunctionSet::isEmpty() const { // Checking if a capability set is empty is trivial in any representation; // all we need to know is if it has zero atoms in its definition. @@ -326,7 +264,7 @@ bool CapabilitySet::isEmpty() const return m_expandedAtoms.getCount() == 0; } -bool CapabilitySet::isInvalid() const +bool CapabilityConjunctionSet::isInvalid() const { // We will assume here that there is only one canonical representation of // an invalid capability set, which is a singleton set of the `Invalid` @@ -342,32 +280,47 @@ bool CapabilitySet::isInvalid() const return m_expandedAtoms[0] == CapabilityAtom::Invalid; } -bool CapabilitySet::isIncompatibleWith(CapabilityAtom that) const +bool CapabilityConjunctionSet::isIncompatibleWith(CapabilityAtom that) const { // Checking for incompatibility is complicated, and it is best // to only implement it for full (expanded) sets. // - return isIncompatibleWith(CapabilitySet(that)); + return isIncompatibleWith(CapabilityConjunctionSet(that)); } -uint32_t CapabilitySet::_calcConflictMask() const +static UIntSet _calcConflictMask(CapabilityAtom atom) +{ + UIntSet mask; + auto abstractBase = _getInfo(atom).abstractBase; + if (abstractBase != CapabilityName::Invalid) + { + mask.add((UInt)abstractBase); + } + return mask; +} + +static UIntSet _calcConflictMask(const CapabilityConjunctionSet& set) { // Given a capbility set, we want to compute the mask representing // all groups of features for which it holds a potentially-conflicting atom. // - uint32_t mask = 0; - for( auto atom : m_expandedAtoms ) + UIntSet mask; + for (auto atom : set.getExpandedAtoms()) { - mask |= uint32_t(_getInfo(atom).conflictMask); + auto abstractBase = _getInfo(atom).abstractBase; + if (abstractBase != CapabilityName::Invalid) + { + mask.add((UInt)abstractBase); + } } return mask; } -bool CapabilitySet::isIncompatibleWith(CapabilitySet const& that) const +bool CapabilityConjunctionSet::isIncompatibleWith(CapabilityConjunctionSet const& that) const { // The `this` and `that` sets are incompatible if there exists // an atom A in `this` and an atom `B` in `that` such that - // A and B are not equal, but the two have overlapping "conflict mask." + // A and B are not equal, but the two have overlapping "conflict group." // // Equivalently, we can say that the two are in conflict if // @@ -382,8 +335,8 @@ bool CapabilitySet::isIncompatibleWith(CapabilitySet const& that) const // We start by identifying the OR of the conflict masks for // all features in `this` and `that`. // - uint32_t thisMask = this->_calcConflictMask(); - uint32_t thatMask = that._calcConflictMask(); + UIntSet thisMask = _calcConflictMask(*this); + UIntSet thatMask = _calcConflictMask(that); // Note: there is a possible early-exit opportunity here if // `thisMask` and `thatMask` have no overlap: there could @@ -422,8 +375,8 @@ bool CapabilitySet::isIncompatibleWith(CapabilitySet const& that) const // include something with an overlapping mask // (we don't know what at this point in the code). // - auto thisAtomMask = uint32_t(_getInfo(thisAtom).conflictMask); - if(thisAtomMask & thatMask) + auto thisConflictMask = Slang::_calcConflictMask(thisAtom); + if(UIntSet::hasIntersection(thisConflictMask, thatMask)) return true; thisIndex++; } @@ -435,8 +388,8 @@ bool CapabilitySet::isIncompatibleWith(CapabilitySet const& that) const // // The logic here is the mirror image of the case above. // - auto thatAtomMask = uint32_t(_getInfo(thatAtom).conflictMask); - if(thatAtomMask & thisMask) + auto thatConflictMask = Slang::_calcConflictMask(thatAtom); + if(UIntSet::hasIntersection(thatConflictMask, thisMask)) return true; thatIndex++; } @@ -445,7 +398,7 @@ bool CapabilitySet::isIncompatibleWith(CapabilitySet const& that) const return false; } -bool CapabilitySet::implies(CapabilitySet const& that) const +bool CapabilityConjunctionSet::implies(CapabilityConjunctionSet const& that) const { // One capability set implies another if it is a super-set // of the other one. Think of it this way: if your target @@ -541,37 +494,19 @@ struct CapabilityAtomComparator } }; -bool CapabilitySet::implies(CapabilityAtom atom) const +bool CapabilityConjunctionSet::implies(CapabilityAtom atom) const { - // The common case here is when `atom` is not an alias. + // Every non-alias atom that `this` implies should + // be presented in the `m_expandedAtoms` list. // - if( _getInfo(atom).flavor != CapabilityAtomFlavor::Alias ) - { - // Every non-alias atom that `this` implies should - // be presented in the `m_expandedAtoms` list. - // - // Because the list is sorted, we can find out whether - // it contains `atom` with a binary search. - // - Index result = m_expandedAtoms.binarySearch(atom, CapabilityAtomComparator()); - return result >= 0; - } - else - { - // In the case where `atom` is an alias, then it won't - // appear in the expanded list, and we need to check - // whether `this` set implies everything that `atom` - // transitively inherits from. - // - // The simplest way to do that is to expand `atom` - // into the full capability set it stands for and - // check that. - // - return implies(CapabilitySet(atom)); - } + // Because the list is sorted, we can find out whether + // it contains `atom` with a binary search. + // + Index result = m_expandedAtoms.binarySearch(atom, CapabilityAtomComparator()); + return result >= 0; } -Int CapabilitySet::countIntersectionWith(CapabilitySet const& that) const +Int CapabilityConjunctionSet::countIntersectionWith(CapabilityConjunctionSet const& that) const { // The goal of this subroutine is to count the number of // elements in the intersection of `this` and `that`, @@ -626,9 +561,9 @@ Int CapabilitySet::countIntersectionWith(CapabilitySet const& that) const return intersectionCount; } -bool CapabilitySet::isBetterForTarget( - CapabilitySet const& existingCaps, - CapabilitySet const& targetCaps) +bool CapabilityConjunctionSet::isBetterForTarget( + CapabilityConjunctionSet const& existingCaps, + CapabilityConjunctionSet const& targetCaps) const { auto& candidateCaps = *this; @@ -720,14 +655,12 @@ bool CapabilitySet::isBetterForTarget( // All preceding factors being equal, we prefer // a candidate that is strictly more specialized than the other. // - // TODO: This logic has the negative effect of always preferring - // to enable optional features even if they aren't necessary. - // It would prefer the set {glsl, optionalFeature} over the set - // {glsl}, even though we might argue that a default implementaton - // that works without any optional features is "obviously" what - // the user means if they didn't enable those features. + // We want to avoid choosing the candidate that uses + // optional features if they aren't necessary. + // For example, the set {glsl, optionalFeature} should not be preferred + // over the set {glsl}, if optionalFeature isn't requested explictly. // - // TODO: The right answer is possibly that we want to partition + // The solution here is that we want to partition // `candidateCaps` and `existingCaps` into two parts: their // intersection with `targetCaps` and their difference with it. // @@ -736,8 +669,28 @@ bool CapabilitySet::isBetterForTarget( // part we'd actually wnat to favor a definition that is less // specialized. // - if(candidateCaps.implies(existingCaps)) return true; - if(existingCaps.implies(candidateCaps)) return true; + CapabilityConjunctionSet candidateCapsIntersection; + CapabilityConjunctionSet candidateCapsDifference; + for (auto atom : candidateCaps.m_expandedAtoms) + { + if (targetCaps.implies(atom)) + candidateCapsIntersection.m_expandedAtoms.add(atom); + else + candidateCapsDifference.m_expandedAtoms.add(atom); + } + CapabilityConjunctionSet existingCapsIntersection; + CapabilityConjunctionSet existingCapsDifference; + for (auto atom : existingCaps.m_expandedAtoms) + { + if (targetCaps.implies(atom)) + existingCapsIntersection.m_expandedAtoms.add(atom); + else + existingCapsDifference.m_expandedAtoms.add(atom); + } + auto scoreCandidate = candidateCapsIntersection.m_expandedAtoms.getCount() - candidateCapsDifference.m_expandedAtoms.getCount(); + auto scoreExisting = existingCapsIntersection.m_expandedAtoms.getCount() - existingCapsDifference.m_expandedAtoms.getCount(); + if (scoreCandidate != scoreExisting) + return scoreCandidate > scoreExisting; // At this point we have the problem that neither candidate // appears to be "obviously" better for the target, but we @@ -747,18 +700,15 @@ bool CapabilitySet::isBetterForTarget( // different from the other, and see if anything in either case // has a ranking that should make it be preferred. // - // TODO: This should probably *not* be considering anything that - // is implied/supported by the target. - // - auto candidateScore = candidateCaps._calcDifferenceScoreWith(existingCaps); - auto existingScore = existingCaps._calcDifferenceScoreWith(candidateCaps); + auto candidateScore = candidateCapsDifference._calcDifferenceScoreWith(existingCapsDifference); + auto existingScore = existingCapsDifference._calcDifferenceScoreWith(candidateCapsDifference); if(candidateScore != existingScore) return candidateScore > existingScore; return false; } -uint32_t CapabilitySet::_calcDifferenceScoreWith(CapabilitySet const& that) const +uint32_t CapabilityConjunctionSet::_calcDifferenceScoreWith(CapabilityConjunctionSet const& that) const { uint32_t score = 0; @@ -811,12 +761,345 @@ uint32_t CapabilitySet::_calcDifferenceScoreWith(CapabilitySet const& that) cons } -bool CapabilitySet::operator==(CapabilitySet const& other) const +bool CapabilityConjunctionSet::operator==(CapabilityConjunctionSet const& other) const +{ + return m_expandedAtoms == other.m_expandedAtoms; +} + +bool CapabilityConjunctionSet::operator<(CapabilityConjunctionSet const& that) const +{ + for (Index i = 0; i < Math::Min(m_expandedAtoms.getCount(), that.m_expandedAtoms.getCount()); i++) + { + if (m_expandedAtoms[i] < that.m_expandedAtoms[i]) + return true; + else if (m_expandedAtoms[i] > that.m_expandedAtoms[i]) + return false; + } + return m_expandedAtoms.getCount() < that.m_expandedAtoms.getCount(); +} + + +CapabilitySet::CapabilitySet() +{} + +CapabilitySet::CapabilitySet(Int atomCount, CapabilityName const* atoms) +{ + for (Int i = 0; i < atomCount; i++) + addCapability(atoms[i]); +} + +CapabilitySet::CapabilitySet(CapabilityName atom) +{ + auto info = _getInfo(atom); + for (auto conjunction : info.canonicalRepresentation) + { + CapabilityConjunctionSet set; + for (auto atomName : conjunction) + set.getExpandedAtoms().add(asAtom(atomName)); + m_conjunctions.add(_Move(set)); + } +} + +CapabilitySet::CapabilitySet(List const& atoms) +{ + for (auto atom : atoms) + addCapability(atom); +} + +CapabilitySet CapabilitySet::makeEmpty() +{ + return CapabilitySet(); +} + +CapabilitySet CapabilitySet::makeInvalid() +{ + // An invalid capability set will always be a singleton + // set of the `Invalid` atom, and we will construct + // the set directly rather than use the more expensive + // logic in `_init()`. + // + CapabilitySet result; + result.m_conjunctions.add(CapabilityConjunctionSet(CapabilityAtom::Invalid)); + return result; +} + +void CapabilitySet::addCapability(CapabilityName name) +{ + join(CapabilitySet(name)); +} + +bool CapabilitySet::isEmpty() const +{ + return m_conjunctions.getCount() == 0; +} + +bool CapabilitySet::isInvalid() const +{ + return m_conjunctions.getCount() == 1 && m_conjunctions[0].isInvalid(); +} + +bool CapabilitySet::isIncompatibleWith(CapabilityAtom other) const +{ + if (isEmpty()) + return false; + + // If all conjunctions are incompatible with the atom, then we are incompatible. + for (auto& c : m_conjunctions) + if (!c.isIncompatibleWith(other)) + return false; + return true; +} + +bool CapabilitySet::isIncompatibleWith(CapabilityName other) const +{ + if (isEmpty()) + return false; + auto otherSet = CapabilitySet(other); + return isIncompatibleWith(otherSet); +} + +bool CapabilitySet::isIncompatibleWith(CapabilityConjunctionSet const& other) const { - // TODO: We should be able to implement this more efficiently - // by scanning over the two sets in tandem. + if (isEmpty()) + return false; + + // If all conjunctions are incompatible with the atom, then we are incompatible. + for (auto& c : m_conjunctions) + if (!c.isIncompatibleWith(other)) + return false; + return true; +} + +bool CapabilitySet::isIncompatibleWith(CapabilitySet const& other) const +{ + if (isEmpty()) + return false; + if (other.isEmpty()) + return false; + + // If all conjunctions in other are incompatible with the this set, then we are incompatible. + for (auto& oc : other.m_conjunctions) + for (auto& c : m_conjunctions) + if (!c.isIncompatibleWith(oc)) + return false; + return true; +} + +bool CapabilitySet::implies(CapabilityAtom atom) const +{ + if (isEmpty()) + return false; + + for (auto& c : m_conjunctions) + if (c.implies(atom)) + return true; + + return false; +} + +bool CapabilitySet::implies(const CapabilityConjunctionSet& set) const +{ + if (isEmpty()) + return false; + + for (auto& c : m_conjunctions) + if (c.implies(set)) + return true; - return this->implies(other) && other.implies(*this); + return false; +} + +bool CapabilitySet::implies(CapabilitySet const& other) const +{ + // x implies (c | d) only if (x implies c) and (x implies d). + if (other.isEmpty()) + return true; + for (auto& c : other.m_conjunctions) + if (!implies(c)) + return false; + return true; +} + +bool CapabilitySet::operator==(CapabilitySet const& that) const +{ + return m_conjunctions == that.m_conjunctions; +} + +void CapabilitySet::calcCompactedAtoms(List>& outAtoms) const +{ + for (auto& c : m_conjunctions) + { + List atoms; + c.calcCompactedAtoms(atoms); + outAtoms.add(atoms); + } +} + +void CapabilitySet::join(const CapabilitySet& other) +{ + if (isEmpty() || other.isInvalid()) + { + *this = other; + return; + } + if (isInvalid()) + return; + if (other.isEmpty()) + return; + + List resultSet; + for (auto& thatConjunction : other.m_conjunctions) + { + for (auto& thisConjunction : m_conjunctions) + { + if (thisConjunction.isIncompatibleWith(thatConjunction)) + continue; + + CapabilityConjunctionSet conjunction; + CapabilityConjunctionSet *conjunctionToAdd = nullptr; + + // Add atoms from thatConjunction that are not existant in thisConjunction. + for (auto atom : thatConjunction.getExpandedAtoms()) + { + if (thisConjunction.getExpandedAtoms().binarySearch(atom, CapabilityAtomComparator()) == -1) + { + conjunction.getExpandedAtoms().add(atom); + } + } + + if (conjunction.getExpandedAtoms().getCount() != 0) + { + // If we find any capabilities in thatConjunction that is missing from thisConjunction, + // create a new ConjunctionSet that contains atoms from both, and add it to the disjunction set. + conjunction.getExpandedAtoms().addRange(thisConjunction.getExpandedAtoms()); + conjunction.getExpandedAtoms().sort(); + conjunctionToAdd = &conjunction; + } + else + { + // Otherwise, thisConjunction implies thatConjunction, so we just add thisConjunction to resultSet. + conjunctionToAdd = &thisConjunction; + } + // We add conjunctionToAdd to resultSet only if it does not imply any existing conjunctions. + // For example, if `resultSet` is (a), and conjunctionToAdd is (ab), then we don't want to add the conjunction + // to form (a | ab) because that would reduce to (a). + bool skipAdd = false; + for (auto& c : resultSet) + { + if (conjunctionToAdd->implies(c)) + { + skipAdd = true; + break; + } + } + if (!skipAdd) + { + // Once we added the new conjunction, any existing conjunctions that implies the new one can be + // removed. + // For example, if resultSet was (ab), and we are adding (a), the result should be just (a). + for (Index i = 0; i < resultSet.getCount();) + { + if (resultSet[i].implies(*conjunctionToAdd)) + { + resultSet.fastRemoveAt(i); + } + else + { + i++; + } + } + resultSet.add(*conjunctionToAdd); + } + } + } + m_conjunctions = _Move(resultSet); + + // Make sure conjunctions are sorted so equality tests are trivial. + m_conjunctions.sort(); +} + +bool CapabilitySet::isBetterForTarget(CapabilitySet const& that, CapabilitySet const& targetCaps) const +{ + if (targetCaps.isIncompatibleWith(*this)) + return false; + if (targetCaps.isIncompatibleWith(that)) + return true; + + ArrayView thisSets = m_conjunctions.getArrayView(); + ArrayView thatSets = that.m_conjunctions.getArrayView(); + CapabilityConjunctionSet emtpySet = CapabilityConjunctionSet::makeEmpty(); + + if (isEmpty()) + thisSets = makeArrayViewSingle(emtpySet); + if (that.isEmpty()) + thatSets = makeArrayViewSingle(emtpySet); + + // It is hard to think about what it means exactly to compare a general disjunction set to another with regard + // to a target that itself is also a disjunction set. + // Instead of trying to find a meaning for the general case, we just want to extend the logic + // for conjunction sets to disjunction sets in a way that common situations are handled correctly. + // Note that when we reach here, most of these sets are likely to contain only one conjunction, so + // we just need to make sure the more general logic here yields correct result for that case. + // + // Right now, we define betterness for disjunctions as follows: + // A capability set X is determined to be better for a target T than capability set Y, + // if we find a conjunction A in X and a conjunction B in Y and a conjunction C in T such that + // A is better then B for target C. + // + struct ViableConjunctionIndex + { + Index index; + UIntSet targetConjunctionIndices; + }; + auto getViableConjunction = [&](ArrayView set, List& outList) + { + for (Index i = 0; i < set.getCount(); i++) + { + auto& conjunction = set[i]; + ViableConjunctionIndex viableConjunction; + viableConjunction.index = i; + for (Index j = 0; j < targetCaps.m_conjunctions.getCount(); j++) + { + auto& targetConjunction = targetCaps.m_conjunctions[j]; + if (conjunction.isIncompatibleWith(targetConjunction)) + continue; + viableConjunction.targetConjunctionIndices.add(j); + } + if (!viableConjunction.targetConjunctionIndices.isEmpty()) + { + outList.add(viableConjunction); + } + } + }; + List viableConjunctionsThis; + List viableConjunctionsThat; + + getViableConjunction(thisSets, viableConjunctionsThis); + getViableConjunction(thatSets, viableConjunctionsThat); + + for (auto& thisConjunctionIndex : viableConjunctionsThis) + { + auto& thisConjunction = thisSets[thisConjunctionIndex.index]; + for (auto& thatConjunctionIndex : viableConjunctionsThat) + { + auto& thatConjunction = thatSets[thatConjunctionIndex.index]; + UIntSet intersection = thisConjunctionIndex.targetConjunctionIndices; + intersection.intersectWith(thatConjunctionIndex.targetConjunctionIndices); + if (!intersection.isEmpty()) + { + for (Index targetConjunctionIndex = 0; targetConjunctionIndex < targetCaps.m_conjunctions.getCount(); targetConjunctionIndex++) + { + if (!intersection.contains((UInt)targetConjunctionIndex)) + continue; + if (thisConjunction.isBetterForTarget(thatConjunction, targetCaps.m_conjunctions[targetConjunctionIndex])) + { + return true; + } + } + } + } + } + return false; } } -- cgit v1.2.3