IndexSubset.cpp

//===--- IndexSubset.cpp - Fixed-size subset of indices -------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2019 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//

#include"swift/AST/IndexSubset.h"
#include"swift/Basic/Assertions.h"

usingnamespaceswift;

IndexSubset *
IndexSubset::getFromString(ASTContext &ctx, StringRef string) {
unsigned capacity = string.size();
 llvm::SmallBitVector indices(capacity);
for (unsigned i : range(capacity)) {
if (string[i] == 'S')
 indices.set(i);
elseif (string[i] != 'U')
returnnullptr;
 }
returnget(ctx, indices);
}

std::string IndexSubset::getString() const {
 std::string result;
 result.reserve(capacity);
for (unsigned i : range(capacity))
 result += contains(i) ? 'S' : 'U';
return result;
}

boolIndexSubset::isSubsetOf(IndexSubset *other) const {
assert(capacity == other->capacity);
for (autoindex : range(numBitWords))
if (getBitWord(index) & ~other->getBitWord(index))
returnfalse;
returntrue;
}

boolIndexSubset::isSupersetOf(IndexSubset *other) const {
assert(capacity == other->capacity);
for (autoindex : range(numBitWords))
if (~getBitWord(index) & other->getBitWord(index))
returnfalse;
returntrue;
}

boolIndexSubset::isDisjointWith(IndexSubset *other) const {
assert(capacity == other->capacity);
for (autoindex : range(numBitWords))
if (getBitWord(index) & other->getBitWord(index))
returnfalse;
returntrue;
}

IndexSubset *IndexSubset::adding(unsigned index, ASTContext &ctx) const {
assert(index < getCapacity());
if (contains(index))
returnconst_cast<IndexSubset *>(this);
 SmallBitVector newIndices(capacity);
bool inserted = false;
for (auto curIndex : getIndices()) {
if (!inserted && curIndex > index) {
 newIndices.set(index);
 inserted = true;
 }
 newIndices.set(curIndex);
 }
returnget(ctx, newIndices);
}

IndexSubset *IndexSubset::extendingCapacity(
 ASTContext &ctx, unsigned newCapacity) const {
assert(newCapacity >= capacity);
if (newCapacity == capacity)
returnconst_cast<IndexSubset *>(this);
 SmallBitVector indices(newCapacity);
for (autoindex : getIndices())
 indices.set(index);
returnIndexSubset::get(ctx, indices);
}

voidIndexSubset::print(llvm::raw_ostream &s) const {
 s << '{';
llvm::interleave(
range(capacity), [this, &s](unsigned i) { s << contains(i); },
 [&s] { s << ", "; });
 s << '}';
}

voidIndexSubset::dump() const {
auto &s = llvm::errs();
 s << "(index_subset capacity=" << capacity << " indices=(";
interleave(getIndices(), [&s](unsigned i) { s << i; },
 [&s] { s << ", "; });
 s << "))\n";
}

intIndexSubset::findNext(int startIndex) const {
assert(startIndex < (int)capacity && "Start index cannot be past the end");
unsigned bitWordIndex = 0, offset = 0;
if (startIndex >= 0) {
auto indexAndOffset = getBitWordIndexAndOffset(startIndex);
 bitWordIndex = indexAndOffset.first;
 offset = indexAndOffset.second + 1;
 }
for (; bitWordIndex < numBitWords; ++bitWordIndex, offset = 0) {
for (; offset < numBitsPerBitWord; ++offset) {
autoindex = bitWordIndex * numBitsPerBitWord + offset;
auto bitWord = getBitWord(bitWordIndex);
if (!bitWord)
break;
if (index >= capacity)
return capacity;
if (bitWord & ((BitWord)1 << offset))
returnindex;
 }
 }
return capacity;
}

intIndexSubset::findPrevious(int endIndex) const {
assert(endIndex >= 0 && "End index cannot be before the start");
int bitWordIndex = numBitWords - 1, offset = numBitsPerBitWord - 1;
if (endIndex < (int)capacity) {
auto indexAndOffset = getBitWordIndexAndOffset(endIndex);
 bitWordIndex = (int)indexAndOffset.first;
 offset = (int)indexAndOffset.second - 1;
 }
for (; bitWordIndex >= 0; --bitWordIndex, offset = numBitsPerBitWord - 1) {
for (; offset >= 0; --offset) {
autoindex = bitWordIndex * (int)numBitsPerBitWord + offset;
auto bitWord = getBitWord(bitWordIndex);
if (!bitWord)
break;
if (index < 0)
return -1;
if (bitWord & ((BitWord)1 << offset))
returnindex;
 }
 }
return -1;
}