diff options
Diffstat (limited to 'source/slang/slang-capability.cpp')
| -rw-r--r-- | source/slang/slang-capability.cpp | 703 |
1 files changed, 493 insertions, 210 deletions
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<ArrayView<CapabilityName>> 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<UnownedStringSlice>& ioNames) +void getCapabilityNames(List<UnownedStringSlice>& 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<CapabilityAtom> const& atoms) +CapabilityConjunctionSet::CapabilityConjunctionSet(List<CapabilityAtom> 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<CapabilityAtom>& 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<CapabilityAtom> 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<CapabilityAtom>& outAtoms) const +void CapabilityConjunctionSet::calcCompactedAtoms(List<CapabilityAtom>& 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<CapabilityAtom>& 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<CapabilityAtom>& 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<CapabilityName> 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<List<CapabilityAtom>>& outAtoms) const +{ + for (auto& c : m_conjunctions) + { + List<CapabilityAtom> 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<CapabilityConjunctionSet> 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<CapabilityConjunctionSet> thisSets = m_conjunctions.getArrayView(); + ArrayView<CapabilityConjunctionSet> 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<CapabilityConjunctionSet> set, List<ViableConjunctionIndex>& 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<ViableConjunctionIndex> viableConjunctionsThis; + List<ViableConjunctionIndex> 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; } } |