Merge pull request #18820 from rjmccall/devirtualize-begin-apply
Update SIL devirtualization to handle begin_apply instructions
diff --git a/include/swift/Basic/LLVM.h b/include/swift/Basic/LLVM.h
index 7411d4b..1bd8a16 100644
--- a/include/swift/Basic/LLVM.h
+++ b/include/swift/Basic/LLVM.h
@@ -37,6 +37,7 @@
template <typename T> class SmallVectorImpl;
template <typename T, unsigned N> class SmallVector;
template <unsigned N> class SmallString;
+ template <typename T, unsigned N> class SmallSetVector;
template<typename T> class ArrayRef;
template<typename T> class MutableArrayRef;
template<typename T> class TinyPtrVector;
@@ -73,6 +74,7 @@
using llvm::MutableArrayRef;
using llvm::TinyPtrVector;
using llvm::PointerUnion;
+ using llvm::SmallSetVector;
// Other common classes.
using llvm::raw_ostream;
diff --git a/lib/Sema/CSApply.cpp b/lib/Sema/CSApply.cpp
index 5a4d1db..59b5508 100644
--- a/lib/Sema/CSApply.cpp
+++ b/lib/Sema/CSApply.cpp
@@ -7764,6 +7764,8 @@
llvm::SmallDenseMap<Expr *, SmallVector<const ConstraintFix *, 4>>
fixesPerExpr;
+ applySolution(solution);
+
for (auto *fix : solution.Fixes)
fixesPerExpr[fix->getAnchor()].push_back(fix);
diff --git a/lib/Sema/CSDiag.cpp b/lib/Sema/CSDiag.cpp
index 1c3c255..e829eb8 100644
--- a/lib/Sema/CSDiag.cpp
+++ b/lib/Sema/CSDiag.cpp
@@ -738,7 +738,7 @@
.fixItReplaceChars(startLoc, endLoc, scratch);
}
-static void diagnoseSubElementFailure(Expr *destExpr,
+void swift::diagnoseSubElementFailure(Expr *destExpr,
SourceLoc loc,
ConstraintSystem &CS,
Diag<StringRef> diagID,
@@ -883,7 +883,8 @@
}
}
- TC.diagnose(loc, unknownDiagID, CS.getType(destExpr))
+ auto type = destExpr->getType() ?: CS.simplifyType(CS.getType(destExpr));
+ TC.diagnose(loc, unknownDiagID, type)
.highlight(immInfo.first->getSourceRange());
}
@@ -6153,33 +6154,6 @@
if (!argExpr)
return true; // already diagnosed.
- // A common error is to apply an operator that only has inout forms (e.g. +=)
- // to non-lvalues (e.g. a local let). Produce a nice diagnostic for this
- // case.
- if (calleeInfo.closeness == CC_NonLValueInOut) {
- Diag<StringRef> subElementDiagID;
- Diag<Type> rvalueDiagID;
- Expr *diagExpr = nullptr;
-
- if (isa<PrefixUnaryExpr>(callExpr) || isa<PostfixUnaryExpr>(callExpr)) {
- subElementDiagID = diag::cannot_apply_lvalue_unop_to_subelement;
- rvalueDiagID = diag::cannot_apply_lvalue_unop_to_rvalue;
- diagExpr = argExpr;
- } else if (isa<BinaryExpr>(callExpr)) {
- subElementDiagID = diag::cannot_apply_lvalue_binop_to_subelement;
- rvalueDiagID = diag::cannot_apply_lvalue_binop_to_rvalue;
-
- if (auto argTuple = dyn_cast<TupleExpr>(argExpr))
- diagExpr = argTuple->getElement(0);
- }
-
- if (diagExpr) {
- diagnoseSubElementFailure(diagExpr, callExpr->getFn()->getLoc(), CS,
- subElementDiagID, rvalueDiagID);
- return true;
- }
- }
-
// Handle argument label mismatches when we have multiple candidates.
if (calleeInfo.closeness == CC_ArgumentLabelMismatch) {
auto args = decomposeArgType(CS.getType(argExpr), argLabels);
diff --git a/lib/Sema/CSDiag.h b/lib/Sema/CSDiag.h
index 82eb774..d278402 100644
--- a/lib/Sema/CSDiag.h
+++ b/lib/Sema/CSDiag.h
@@ -26,7 +26,12 @@
/// UnresolvedType.
Type replaceTypeParametersWithUnresolved(Type ty);
Type replaceTypeVariablesWithUnresolved(Type ty);
-
+
+ /// Diagnose lvalue expr error.
+ void diagnoseSubElementFailure(Expr *destExpr, SourceLoc loc,
+ constraints::ConstraintSystem &CS,
+ Diag<StringRef> diagID,
+ Diag<Type> unknownDiagID);
};
#endif /* SWIFT_SEMA_CSDIAG_H */
diff --git a/lib/Sema/CSDiagnostics.cpp b/lib/Sema/CSDiagnostics.cpp
index 1b1d9cd..7031109 100644
--- a/lib/Sema/CSDiagnostics.cpp
+++ b/lib/Sema/CSDiagnostics.cpp
@@ -16,6 +16,7 @@
#include "CSDiagnostics.h"
#include "ConstraintSystem.h"
+#include "CSDiag.h"
#include "MiscDiagnostics.h"
#include "swift/AST/Expr.h"
#include "swift/AST/GenericSignature.h"
@@ -532,3 +533,44 @@
.fixItReplace({tryExpr->getTryLoc(), tryExpr->getQuestionLoc()}, "try!");
return true;
}
+
+bool RValueTreatedAsLValueFailure::diagnose() {
+ Diag<StringRef> subElementDiagID;
+ Diag<Type> rvalueDiagID;
+ Expr *diagExpr = getLocator()->getAnchor();
+ SourceLoc loc;
+
+ auto callExpr = dyn_cast<ApplyExpr>(diagExpr);
+ if (!callExpr)
+ return false; // currently only creating these for args, so should be
+ // unreachable
+
+ Expr *argExpr = callExpr->getArg();
+ loc = callExpr->getFn()->getLoc();
+
+ if (isa<PrefixUnaryExpr>(callExpr) || isa<PostfixUnaryExpr>(callExpr)) {
+ subElementDiagID = diag::cannot_apply_lvalue_unop_to_subelement;
+ rvalueDiagID = diag::cannot_apply_lvalue_unop_to_rvalue;
+ diagExpr = argExpr;
+ } else if (isa<BinaryExpr>(callExpr)) {
+ subElementDiagID = diag::cannot_apply_lvalue_binop_to_subelement;
+ rvalueDiagID = diag::cannot_apply_lvalue_binop_to_rvalue;
+ auto argTuple = dyn_cast<TupleExpr>(argExpr);
+ diagExpr = argTuple->getElement(0);
+ } else {
+ auto lastPathElement = getLocator()->getPath().back();
+ assert(lastPathElement.getKind() ==
+ ConstraintLocator::PathElementKind::ApplyArgToParam);
+
+ subElementDiagID = diag::cannot_pass_rvalue_inout_subelement;
+ rvalueDiagID = diag::cannot_pass_rvalue_inout;
+ if (auto argTuple = dyn_cast<TupleExpr>(argExpr))
+ diagExpr = argTuple->getElement(lastPathElement.getValue());
+ else if (auto parens = dyn_cast<ParenExpr>(argExpr))
+ diagExpr = parens->getSubExpr();
+ }
+
+ diagnoseSubElementFailure(diagExpr, loc, getConstraintSystem(),
+ subElementDiagID, rvalueDiagID);
+ return true;
+}
diff --git a/lib/Sema/CSDiagnostics.h b/lib/Sema/CSDiagnostics.h
index 934163c..6101e00 100644
--- a/lib/Sema/CSDiagnostics.h
+++ b/lib/Sema/CSDiagnostics.h
@@ -345,6 +345,17 @@
bool diagnose() override;
};
+/// Diagnose errors associated with rvalues in positions
+/// where an lvalue is required, such as inout arguments.
+class RValueTreatedAsLValueFailure final : public FailureDiagnostic {
+
+public:
+ RValueTreatedAsLValueFailure(const Solution &solution, ConstraintLocator *locator)
+ : FailureDiagnostic(nullptr, solution, locator) {}
+
+ bool diagnose() override;
+};
+
} // end namespace constraints
} // end namespace swift
diff --git a/lib/Sema/CSFix.cpp b/lib/Sema/CSFix.cpp
index 84e5915..bb837ef 100644
--- a/lib/Sema/CSFix.cpp
+++ b/lib/Sema/CSFix.cpp
@@ -104,6 +104,17 @@
return new (cs.getAllocator()) AddAddressOf(locator);
}
+bool TreatRValueAsLValue::diagnose(Expr *root, const Solution &solution) const {
+ RValueTreatedAsLValueFailure failure(solution, getLocator());
+ return failure.diagnose();
+}
+
+TreatRValueAsLValue *TreatRValueAsLValue::create(ConstraintSystem &cs,
+ ConstraintLocator *locator) {
+ return new (cs.getAllocator()) TreatRValueAsLValue(locator);
+}
+
+
bool CoerceToCheckedCast::diagnose(Expr *root, const Solution &solution) const {
MissingForcedDowncastFailure failure(root, solution, getLocator());
return failure.diagnose();
diff --git a/lib/Sema/CSFix.h b/lib/Sema/CSFix.h
index 155396b..84ecc8f 100644
--- a/lib/Sema/CSFix.h
+++ b/lib/Sema/CSFix.h
@@ -68,6 +68,9 @@
/// Add a new conformance to the type to satisfy a requirement.
AddConformance,
+
+ /// Treat rvalue as lvalue
+ TreatRValueAsLValue,
};
class ConstraintFix {
@@ -168,6 +171,20 @@
static AddAddressOf *create(ConstraintSystem &cs, ConstraintLocator *locator);
};
+// Treat rvalue as if it was an lvalue
+class TreatRValueAsLValue final : public ConstraintFix {
+ TreatRValueAsLValue(ConstraintLocator *locator)
+ : ConstraintFix(FixKind::TreatRValueAsLValue, locator) {}
+
+public:
+ std::string getName() const override { return "treat rvalue as lvalue"; }
+
+ bool diagnose(Expr *root, const Solution &solution) const override;
+
+ static TreatRValueAsLValue *create(ConstraintSystem &cs, ConstraintLocator *locator);
+};
+
+
/// Replace a coercion ('as') with a forced checked cast ('as!').
class CoerceToCheckedCast final : public ConstraintFix {
CoerceToCheckedCast(ConstraintLocator *locator)
diff --git a/lib/Sema/CSSimplify.cpp b/lib/Sema/CSSimplify.cpp
index bd80bc3..92fe7e9 100644
--- a/lib/Sema/CSSimplify.cpp
+++ b/lib/Sema/CSSimplify.cpp
@@ -2439,10 +2439,16 @@
ForceDowncast::create(*this, type2, getConstraintLocator(locator)));
}
- // If we're converting an lvalue to an inout type, add the missing '&'.
- if (type2->getRValueType()->is<InOutType>() && type1->is<LValueType>()) {
- conversionsOrFixes.push_back(
+ if (type2->getRValueType()->is<InOutType>()) {
+ if (type1->is<LValueType>()) {
+ // If we're converting an lvalue to an inout type, add the missing '&'.
+ conversionsOrFixes.push_back(
AddAddressOf::create(*this, getConstraintLocator(locator)));
+ } else if (!isTypeVarOrMember1) {
+ // If we have a concrete type that's an rvalue, "fix" it.
+ conversionsOrFixes.push_back(
+ TreatRValueAsLValue::create(*this, getConstraintLocator(locator)));
+ }
}
}
@@ -4980,6 +4986,16 @@
return result;
}
+ case FixKind::TreatRValueAsLValue: {
+ auto result = matchTypes(LValueType::get(type1), type2,
+ matchKind, subflags, locator);
+ if (result == SolutionKind::Solved)
+ if (recordFix(fix))
+ return SolutionKind::Error;
+
+ return result;
+ }
+
case FixKind::ExplicitlyEscaping:
case FixKind::CoerceToCheckedCast:
case FixKind::RelabelArguments:
diff --git a/lib/Sema/ConstraintLocator.h b/lib/Sema/ConstraintLocator.h
index bd0c193..52b0ff5 100644
--- a/lib/Sema/ConstraintLocator.h
+++ b/lib/Sema/ConstraintLocator.h
@@ -343,7 +343,7 @@
return PathElement(NamedTupleElement, position);
}
- /// Retrieve a patch element for an argument/parameter comparison in a
+ /// Retrieve a path element for an argument/parameter comparison in a
/// function application.
static PathElement getApplyArgToParam(unsigned argIdx, unsigned paramIdx) {
return PathElement(ApplyArgToParam, argIdx, paramIdx);
diff --git a/lib/Sema/TypeCheckProtocol.cpp b/lib/Sema/TypeCheckProtocol.cpp
index 1c575c2..2e52012 100644
--- a/lib/Sema/TypeCheckProtocol.cpp
+++ b/lib/Sema/TypeCheckProtocol.cpp
@@ -3486,6 +3486,10 @@
auto witness = Conformance->getWitness(requirement, nullptr).getDecl();
if (!witness) return;
+ // Make sure that we finalize the witness, so we can emit this
+ // witness table.
+ TC.DeclsToFinalize.insert(witness);
+
// Objective-C checking for @objc requirements.
if (requirement->isObjC() &&
requirement->getFullName() == witness->getFullName() &&
diff --git a/stdlib/public/core/RangeReplaceableCollection.swift b/stdlib/public/core/RangeReplaceableCollection.swift
index b2c22bf..e42a205 100644
--- a/stdlib/public/core/RangeReplaceableCollection.swift
+++ b/stdlib/public/core/RangeReplaceableCollection.swift
@@ -343,7 +343,16 @@
/// - Complexity: O(*n*), where *n* is the length of the collection.
mutating func removeAll(keepingCapacity keepCapacity: Bool /*= false*/)
- /// Removes from the collection all elements that satisfy the given predicate.
+ /// Removes all the elements that satisfy the given predicate.
+ ///
+ /// Use this method to remove every element in a collection that meets
+ /// particular criteria. The order of the remaining elements is preserved.
+ /// This example removes all the odd values from an
+ /// array of numbers:
+ ///
+ /// var numbers = [5, 6, 7, 8, 9, 10, 11]
+ /// numbers.removeAll(where: { $0 % 2 != 0 })
+ /// // numbers == [6, 8, 10]
///
/// - Parameter shouldBeRemoved: A closure that takes an element of the
/// sequence as its argument and returns a Boolean value indicating
@@ -1083,11 +1092,12 @@
/// Removes all the elements that satisfy the given predicate.
///
/// Use this method to remove every element in a collection that meets
- /// particular criteria. This example removes all the odd values from an
+ /// particular criteria. The order of the remaining elements is preserved.
+ /// This example removes all the odd values from an
/// array of numbers:
///
/// var numbers = [5, 6, 7, 8, 9, 10, 11]
- /// numbers.removeAll(where: { $0 % 2 == 1 })
+ /// numbers.removeAll(where: { $0 % 2 != 0 })
/// // numbers == [6, 8, 10]
///
/// - Parameter shouldBeRemoved: A closure that takes an element of the
@@ -1108,7 +1118,8 @@
/// Removes all the elements that satisfy the given predicate.
///
/// Use this method to remove every element in a collection that meets
- /// particular criteria. This example removes all the vowels from a string:
+ /// particular criteria. The order of the remaining elements is preserved.
+ /// This example removes all the vowels from a string:
///
/// var phrase = "The rain in Spain stays mainly in the plain."
///
diff --git a/stdlib/public/core/Sort.swift b/stdlib/public/core/Sort.swift
index 5d8ddfe..f3d3fe1 100644
--- a/stdlib/public/core/Sort.swift
+++ b/stdlib/public/core/Sort.swift
@@ -45,9 +45,7 @@
/// - Complexity: O(*n* log *n*), where *n* is the length of the sequence.
@inlinable
public func sorted() -> [Element] {
- var result = ContiguousArray(self)
- result.sort()
- return Array(result)
+ return sorted(by: <)
}
}
@@ -142,7 +140,6 @@
extension MutableCollection
where Self: RandomAccessCollection, Element: Comparable {
-
/// Sorts the collection in place.
///
/// You can sort any mutable collection of elements that conform to the
@@ -171,13 +168,7 @@
/// - Complexity: O(*n* log *n*), where *n* is the length of the collection.
@inlinable
public mutating func sort() {
- let didSortUnsafeBuffer = _withUnsafeMutableBufferPointerIfSupported {
- buffer -> Void? in
- buffer.sort()
- }
- if didSortUnsafeBuffer == nil {
- _introSort(&self, subRange: startIndex..<endIndex, by: <)
- }
+ sort(by: <)
}
}
@@ -261,333 +252,306 @@
try buffer.sort(by: areInIncreasingOrder)
}
if didSortUnsafeBuffer == nil {
- try _introSort(
- &self,
- subRange: startIndex..<endIndex,
- by: areInIncreasingOrder)
+ try _introSort(within: startIndex..<endIndex, by: areInIncreasingOrder)
}
}
}
-@inlinable
-internal func _insertionSort<C: MutableCollection & BidirectionalCollection>(
- _ elements: inout C,
- subRange range: Range<C.Index>,
- by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool
-) rethrows {
+extension MutableCollection where Self: BidirectionalCollection {
+ @inlinable
+ internal mutating func _insertionSort(
+ within range: Range<Index>,
+ by areInIncreasingOrder: (Element, Element) throws -> Bool
+ ) rethrows {
- if !range.isEmpty {
+ guard !range.isEmpty else { return }
+
let start = range.lowerBound
- // Keep track of the end of the initial sequence of sorted
- // elements.
- var sortedEnd = start
+ // Keep track of the end of the initial sequence of sorted elements. One
+ // element is trivially already-sorted, thus pre-increment Continue until
+ // the sorted elements cover the whole sequence
+ var sortedEnd = index(after: start)
- // One element is trivially already-sorted, thus pre-increment
- // Continue until the sorted elements cover the whole sequence
- elements.formIndex(after: &sortedEnd)
while sortedEnd != range.upperBound {
// get the first unsorted element
- let x: C.Element = elements[sortedEnd]
+ // FIXME: by stashing the element, instead of using indexing and swapAt,
+ // this method won't work for collections of move-only types.
+ let x = self[sortedEnd]
// Look backwards for x's position in the sorted sequence,
// moving elements forward to make room.
var i = sortedEnd
repeat {
- let predecessor: C.Element = elements[elements.index(before: i)]
+ let j = index(before: i)
+ let predecessor = self[j]
- // If clouser throws the error, We catch the error put the element at right
- // place and rethrow the error.
+ // If closure throws, put the element at right place and rethrow.
do {
// if x doesn't belong before y, we've found its position
- if !(try areInIncreasingOrder(x, predecessor)) {
+ if try !areInIncreasingOrder(x, predecessor) {
break
}
} catch {
- elements[i] = x
+ self[i] = x
throw error
}
// Move y forward
- elements[i] = predecessor
- elements.formIndex(before: &i)
+ self[i] = predecessor
+ i = j
} while i != start
if i != sortedEnd {
// Plop x into position
- elements[i] = x
+ self[i] = x
}
- elements.formIndex(after: &sortedEnd)
+ formIndex(after: &sortedEnd)
}
}
}
-/// Sorts the elements at `elements[a]`, `elements[b]`, and `elements[c]`.
-/// Stable.
-///
-/// The indices passed as `a`, `b`, and `c` do not need to be consecutive, but
-/// must be in strict increasing order.
-///
-/// - Precondition: `a < b && b < c`
-/// - Postcondition: `elements[a] <= elements[b] && elements[b] <= elements[c]`
-@inlinable
-public // @testable
-func _sort3<C: MutableCollection & RandomAccessCollection>(
- _ elements: inout C,
- _ a: C.Index, _ b: C.Index, _ c: C.Index,
- by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool
-) rethrows {
- // There are thirteen possible permutations for the original ordering of
- // the elements at indices `a`, `b`, and `c`. The comments in the code below
- // show the relative ordering of the three elements using a three-digit
- // number as shorthand for the position and comparative relationship of
- // each element. For example, "312" indicates that the element at `a` is the
- // largest of the three, the element at `b` is the smallest, and the element
- // at `c` is the median. This hypothetical input array has a 312 ordering for
- // `a`, `b`, and `c`:
- //
- // [ 7, 4, 3, 9, 2, 0, 3, 7, 6, 5 ]
- // ^ ^ ^
- // a b c
- //
- // - If each of the three elements is distinct, they could be ordered as any
- // of the permutations of 1, 2, and 3: 123, 132, 213, 231, 312, or 321.
- // - If two elements are equivalent and one is distinct, they could be
- // ordered as any permutation of 1, 1, and 2 or 1, 2, and 2: 112, 121, 211,
- // 122, 212, or 221.
- // - If all three elements are equivalent, they are already in order: 111.
+extension MutableCollection {
+ /// Sorts the elements at `elements[a]`, `elements[b]`, and `elements[c]`.
+ /// Stable.
+ ///
+ /// The indices passed as `a`, `b`, and `c` do not need to be consecutive, but
+ /// must be in strict increasing order.
+ ///
+ /// - Precondition: `a < b && b < c`
+ /// - Postcondition: `self[a] <= self[b] && self[b] <= self[c]`
+ @inlinable
+ public // @testable
+ mutating func _sort3(
+ _ a: Index, _ b: Index, _ c: Index,
+ by areInIncreasingOrder: (Element, Element) throws -> Bool
+ ) rethrows {
+ // There are thirteen possible permutations for the original ordering of
+ // the elements at indices `a`, `b`, and `c`. The comments in the code below
+ // show the relative ordering of the three elements using a three-digit
+ // number as shorthand for the position and comparative relationship of
+ // each element. For example, "312" indicates that the element at `a` is the
+ // largest of the three, the element at `b` is the smallest, and the element
+ // at `c` is the median. This hypothetical input array has a 312 ordering for
+ // `a`, `b`, and `c`:
+ //
+ // [ 7, 4, 3, 9, 2, 0, 3, 7, 6, 5 ]
+ // ^ ^ ^
+ // a b c
+ //
+ // - If each of the three elements is distinct, they could be ordered as any
+ // of the permutations of 1, 2, and 3: 123, 132, 213, 231, 312, or 321.
+ // - If two elements are equivalent and one is distinct, they could be
+ // ordered as any permutation of 1, 1, and 2 or 1, 2, and 2: 112, 121, 211,
+ // 122, 212, or 221.
+ // - If all three elements are equivalent, they are already in order: 111.
- switch ((try areInIncreasingOrder(elements[b], elements[a])),
- (try areInIncreasingOrder(elements[c], elements[b]))) {
- case (false, false):
- // 0 swaps: 123, 112, 122, 111
- break
-
- case (true, true):
- // 1 swap: 321
- // swap(a, c): 312->123
- elements.swapAt(a, c)
-
- case (true, false):
- // 1 swap: 213, 212 --- 2 swaps: 312, 211
- // swap(a, b): 213->123, 212->122, 312->132, 211->121
- elements.swapAt(a, b)
-
- if (try areInIncreasingOrder(elements[c], elements[b])) {
- // 132 (started as 312), 121 (started as 211)
- // swap(b, c): 132->123, 121->112
- elements.swapAt(b, c)
- }
-
- case (false, true):
- // 1 swap: 132, 121 --- 2 swaps: 231, 221
- // swap(b, c): 132->123, 121->112, 231->213, 221->212
- elements.swapAt(b, c)
-
- if (try areInIncreasingOrder(elements[b], elements[a])) {
- // 213 (started as 231), 212 (started as 221)
- // swap(a, b): 213->123, 212->122
- elements.swapAt(a, b)
- }
- }
-}
-
-/// Reorders `elements` and returns an index `p` such that every element in
-/// `elements[range.lowerBound..<p]` is less than every element in
-/// `elements[p..<range.upperBound]`.
-///
-/// - Precondition: The count of `range` must be >= 3:
-/// `elements.distance(from: range.lowerBound, to: range.upperBound) >= 3`
-@inlinable
-internal func _partition<C: MutableCollection & RandomAccessCollection>(
- _ elements: inout C,
- subRange range: Range<C.Index>,
- by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool
-) rethrows -> C.Index {
- var lo = range.lowerBound
- var hi = elements.index(before: range.upperBound)
-
- // Sort the first, middle, and last elements, then use the middle value
- // as the pivot for the partition.
- let half = numericCast(elements.distance(from: lo, to: hi)) as UInt / 2
- let mid = elements.index(lo, offsetBy: numericCast(half))
- try _sort3(&elements, lo, mid, hi
- , by: areInIncreasingOrder)
- let pivot = elements[mid]
-
- // Loop invariants:
- // * lo < hi
- // * elements[i] < pivot, for i in range.lowerBound..<lo
- // * pivot <= elements[i] for i in hi..<range.upperBound
- Loop: while true {
- FindLo: do {
- elements.formIndex(after: &lo)
- while lo != hi {
- if !(try areInIncreasingOrder(elements[lo], pivot)) { break FindLo }
- elements.formIndex(after: &lo)
- }
- break Loop
- }
-
- FindHi: do {
- elements.formIndex(before: &hi)
- while hi != lo {
- if (try areInIncreasingOrder(elements[hi], pivot)) { break FindHi }
- elements.formIndex(before: &hi)
- }
- break Loop
- }
-
- elements.swapAt(lo, hi)
- }
-
- return lo
-}
-
-@inlinable
-public // @testable
-func _introSort<C: MutableCollection & RandomAccessCollection>(
- _ elements: inout C,
- subRange range: Range<C.Index>
- , by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool
-) rethrows {
-
- let count = elements.distance(from: range.lowerBound, to: range.upperBound)
- if count < 2 {
- return
- }
- // Set max recursion depth to 2*floor(log(N)), as suggested in the introsort
- // paper: http://www.cs.rpi.edu/~musser/gp/introsort.ps
- let depthLimit = 2 * count._binaryLogarithm()
- try _introSortImpl(
- &elements,
- subRange: range,
- by: areInIncreasingOrder,
- depthLimit: depthLimit)
-}
-
-@inlinable
-internal func _introSortImpl<C: MutableCollection & RandomAccessCollection>(
- _ elements: inout C,
- subRange range: Range<C.Index>
- , by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool,
- depthLimit: Int
-) rethrows {
-
- // Insertion sort is better at handling smaller regions.
- if elements.distance(from: range.lowerBound, to: range.upperBound) < 20 {
- try _insertionSort(
- &elements,
- subRange: range
- , by: areInIncreasingOrder)
- return
- }
- if depthLimit == 0 {
- try _heapSort(
- &elements,
- subRange: range
- , by: areInIncreasingOrder)
- return
- }
-
- // Partition and sort.
- // We don't check the depthLimit variable for underflow because this variable
- // is always greater than zero (see check above).
- let partIdx: C.Index = try _partition(
- &elements,
- subRange: range
- , by: areInIncreasingOrder)
- try _introSortImpl(
- &elements,
- subRange: range.lowerBound..<partIdx,
- by: areInIncreasingOrder,
- depthLimit: depthLimit &- 1)
- try _introSortImpl(
- &elements,
- subRange: partIdx..<range.upperBound,
- by: areInIncreasingOrder,
- depthLimit: depthLimit &- 1)
-}
-
-@inlinable
-internal func _siftDown<C: MutableCollection & RandomAccessCollection>(
- _ elements: inout C,
- index: C.Index,
- subRange range: Range<C.Index>,
- by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool
-) rethrows {
- var i = index
- var countToIndex = elements.distance(from: range.lowerBound, to: i)
- var countFromIndex = elements.distance(from: i, to: range.upperBound)
- // Check if left child is within bounds. If not, stop iterating, because there are
- // no children of the given node in the heap.
- while countToIndex + 1 < countFromIndex {
- let left = elements.index(i, offsetBy: countToIndex + 1)
- var largest = i
- if try areInIncreasingOrder(elements[largest], elements[left]) {
- largest = left
- }
- // Check if right child is also within bounds before trying to examine it.
- if countToIndex + 2 < countFromIndex {
- let right = elements.index(after: left)
- if try areInIncreasingOrder(elements[largest], elements[right]) {
- largest = right
- }
- }
- // If a child is bigger than the current node, swap them and continue sifting
- // down.
- if largest != i {
- elements.swapAt(index, largest)
- i = largest
- countToIndex = elements.distance(from: range.lowerBound, to: i)
- countFromIndex = elements.distance(from: i, to: range.upperBound)
- } else {
+ switch try (areInIncreasingOrder(self[b], self[a]),
+ areInIncreasingOrder(self[c], self[b])) {
+ case (false, false):
+ // 0 swaps: 123, 112, 122, 111
break
+
+ case (true, true):
+ // 1 swap: 321
+ // swap(a, c): 312->123
+ swapAt(a, c)
+
+ case (true, false):
+ // 1 swap: 213, 212 --- 2 swaps: 312, 211
+ // swap(a, b): 213->123, 212->122, 312->132, 211->121
+ swapAt(a, b)
+
+ if try areInIncreasingOrder(self[c], self[b]) {
+ // 132 (started as 312), 121 (started as 211)
+ // swap(b, c): 132->123, 121->112
+ swapAt(b, c)
+ }
+
+ case (false, true):
+ // 1 swap: 132, 121 --- 2 swaps: 231, 221
+ // swap(b, c): 132->123, 121->112, 231->213, 221->212
+ swapAt(b, c)
+
+ if try areInIncreasingOrder(self[b], self[a]) {
+ // 213 (started as 231), 212 (started as 221)
+ // swap(a, b): 213->123, 212->122
+ swapAt(a, b)
+ }
}
}
}
-@inlinable
-internal func _heapify<C: MutableCollection & RandomAccessCollection>(
- _ elements: inout C,
- subRange range: Range<C.Index>,
- by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool
-) rethrows {
- // Here we build a heap starting from the lowest nodes and moving to the root.
- // On every step we sift down the current node to obey the max-heap property:
- // parent >= max(leftChild, rightChild)
- //
- // We skip the rightmost half of the array, because these nodes don't have
- // any children.
- let root = range.lowerBound
- var node = elements.index(
- root,
- offsetBy: elements.distance(
- from: range.lowerBound, to: range.upperBound) / 2)
+extension MutableCollection where Self: RandomAccessCollection {
+ /// Reorders the collection and returns an index `p` such that every element
+ /// in `range.lowerBound..<p` is less than every element in
+ /// `p..<range.upperBound`.
+ ///
+ /// - Precondition: The count of `range` must be >= 3 i.e.
+ /// `distance(from: range.lowerBound, to: range.upperBound) >= 3`
+ @inlinable
+ internal mutating func _partition(
+ within range: Range<Index>,
+ by areInIncreasingOrder: (Element, Element) throws -> Bool
+ ) rethrows -> Index {
+ var lo = range.lowerBound
+ var hi = index(before: range.upperBound)
- while node != root {
- elements.formIndex(before: &node)
- try _siftDown(
- &elements,
- index: node,
- subRange: range
- , by: areInIncreasingOrder)
+ // Sort the first, middle, and last elements, then use the middle value
+ // as the pivot for the partition.
+ let half = distance(from: lo, to: hi) / 2
+ let mid = index(lo, offsetBy: half)
+ try _sort3(lo, mid, hi, by: areInIncreasingOrder)
+ let pivot = self[mid]
+
+ // Loop invariants:
+ // * lo < hi
+ // * self[i] < pivot, for i in range.lowerBound..<lo
+ // * pivot <= self[i] for i in hi..<range.upperBound
+ Loop: while true {
+ FindLo: do {
+ formIndex(after: &lo)
+ while lo != hi {
+ if try !areInIncreasingOrder(self[lo], pivot) { break FindLo }
+ formIndex(after: &lo)
+ }
+ break Loop
+ }
+
+ FindHi: do {
+ formIndex(before: &hi)
+ while hi != lo {
+ if try areInIncreasingOrder(self[hi], pivot) { break FindHi }
+ formIndex(before: &hi)
+ }
+ break Loop
+ }
+
+ swapAt(lo, hi)
+ }
+
+ return lo
}
-}
-@inlinable
-internal func _heapSort<C: MutableCollection & RandomAccessCollection>(
- _ elements: inout C,
- subRange range: Range<C.Index>
- , by areInIncreasingOrder: (C.Element, C.Element) throws -> Bool
-) rethrows {
- var hi = range.upperBound
- let lo = range.lowerBound
- try _heapify(&elements, subRange: range, by: areInIncreasingOrder)
- elements.formIndex(before: &hi)
- while hi != lo {
- elements.swapAt(lo, hi)
- try _siftDown(&elements, index: lo, subRange: lo..<hi, by: areInIncreasingOrder)
- elements.formIndex(before: &hi)
+ @inlinable
+ public // @testable
+ mutating func _introSort(
+ within range: Range<Index>,
+ by areInIncreasingOrder: (Element, Element) throws -> Bool
+ ) rethrows {
+
+ let n = distance(from: range.lowerBound, to: range.upperBound)
+ guard n > 1 else { return }
+
+ // Set max recursion depth to 2*floor(log(N)), as suggested in the introsort
+ // paper: http://www.cs.rpi.edu/~musser/gp/introsort.ps
+ let depthLimit = 2 * n._binaryLogarithm()
+ try _introSortImpl(
+ within: range,
+ by: areInIncreasingOrder,
+ depthLimit: depthLimit)
+ }
+
+ @inlinable
+ internal mutating func _introSortImpl(
+ within range: Range<Index>,
+ by areInIncreasingOrder: (Element, Element) throws -> Bool,
+ depthLimit: Int
+ ) rethrows {
+
+ // Insertion sort is better at handling smaller regions.
+ if distance(from: range.lowerBound, to: range.upperBound) < 20 {
+ try _insertionSort(within: range, by: areInIncreasingOrder)
+ } else if depthLimit == 0 {
+ try _heapSort(within: range, by: areInIncreasingOrder)
+ } else {
+ // Partition and sort.
+ // We don't check the depthLimit variable for underflow because this
+ // variable is always greater than zero (see check above).
+ let partIdx = try _partition(within: range, by: areInIncreasingOrder)
+ try _introSortImpl(
+ within: range.lowerBound..<partIdx,
+ by: areInIncreasingOrder,
+ depthLimit: depthLimit &- 1)
+ try _introSortImpl(
+ within: partIdx..<range.upperBound,
+ by: areInIncreasingOrder,
+ depthLimit: depthLimit &- 1)
+ }
+ }
+
+ @inlinable
+ internal mutating func _siftDown(
+ _ idx: Index,
+ within range: Range<Index>,
+ by areInIncreasingOrder: (Element, Element) throws -> Bool
+ ) rethrows {
+ var i = idx
+ var countToIndex = distance(from: range.lowerBound, to: i)
+ var countFromIndex = distance(from: i, to: range.upperBound)
+ // Check if left child is within bounds. If not, stop iterating, because
+ // there are no children of the given node in the heap.
+ while countToIndex + 1 < countFromIndex {
+ let left = index(i, offsetBy: countToIndex + 1)
+ var largest = i
+ if try areInIncreasingOrder(self[largest], self[left]) {
+ largest = left
+ }
+ // Check if right child is also within bounds before trying to examine it.
+ if countToIndex + 2 < countFromIndex {
+ let right = index(after: left)
+ if try areInIncreasingOrder(self[largest], self[right]) {
+ largest = right
+ }
+ }
+ // If a child is bigger than the current node, swap them and continue sifting
+ // down.
+ if largest != i {
+ swapAt(idx, largest)
+ i = largest
+ countToIndex = distance(from: range.lowerBound, to: i)
+ countFromIndex = distance(from: i, to: range.upperBound)
+ } else {
+ break
+ }
+ }
+ }
+
+ @inlinable
+ internal mutating func _heapify(
+ within range: Range<Index>,
+ by areInIncreasingOrder: (Element, Element) throws -> Bool
+ ) rethrows {
+ // Here we build a heap starting from the lowest nodes and moving to the
+ // root. On every step we sift down the current node to obey the max-heap
+ // property:
+ // parent >= max(leftChild, rightChild)
+ //
+ // We skip the rightmost half of the array, because these nodes don't have
+ // any children.
+ let root = range.lowerBound
+ let half = distance(from: range.lowerBound, to: range.upperBound) / 2
+ var node = index(root, offsetBy: half)
+
+ while node != root {
+ formIndex(before: &node)
+ try _siftDown(node, within: range, by: areInIncreasingOrder)
+ }
+ }
+
+ @inlinable
+ internal mutating func _heapSort(
+ within range: Range<Index>,
+ by areInIncreasingOrder: (Element, Element) throws -> Bool
+ ) rethrows {
+ var hi = range.upperBound
+ let lo = range.lowerBound
+ try _heapify(within: range, by: areInIncreasingOrder)
+ formIndex(before: &hi)
+ while hi != lo {
+ swapAt(lo, hi)
+ try _siftDown(lo, within: lo..<hi, by: areInIncreasingOrder)
+ formIndex(before: &hi)
+ }
}
}
diff --git a/test/Constraints/diagnostics.swift b/test/Constraints/diagnostics.swift
index f90fd8d..8c1ac62 100644
--- a/test/Constraints/diagnostics.swift
+++ b/test/Constraints/diagnostics.swift
@@ -719,14 +719,13 @@
}
postfix operator +++
-postfix func +++ <T>(_: inout T) -> T { fatalError() } // expected-note {{in call to operator '+++'}}
+postfix func +++ <T>(_: inout T) -> T { fatalError() }
// <rdar://problem/21523291> compiler error message for mutating immutable field is incorrect
func r21523291(_ bytes : UnsafeMutablePointer<UInt8>) {
- let i = 42
+ let i = 42 // expected-note {{change 'let' to 'var' to make it mutable}}
- // FIXME: rdar://41416382
- _ = bytes[i+++] // expected-error {{generic parameter 'T' could not be inferred}}
+ _ = bytes[i+++] // expected-error {{cannot pass immutable value to mutating operator: 'i' is a 'let' constant}}
}
diff --git a/test/Constraints/lvalues.swift b/test/Constraints/lvalues.swift
index e4e2fda..2ac45f7 100644
--- a/test/Constraints/lvalues.swift
+++ b/test/Constraints/lvalues.swift
@@ -76,14 +76,14 @@
f1(&non_settable_x) // expected-error{{cannot pass immutable value as inout argument: 'non_settable_x' is a get-only property}}
// - inout assignment
non_settable_x += x // expected-error{{left side of mutating operator isn't mutable: 'non_settable_x' is a get-only property}}
-+++non_settable_x // expected-error{{cannot pass immutable value as inout argument: 'non_settable_x' is a get-only property}}
++++non_settable_x // expected-error{{cannot pass immutable value to mutating operator: 'non_settable_x' is a get-only property}}
// non-settable property is non-settable:
z.non_settable_x = x // expected-error{{cannot assign to property: 'non_settable_x' is a get-only property}}
f2(&z.non_settable_x) // expected-error{{cannot pass immutable value as inout argument: 'non_settable_x' is a get-only property}}
f1(&z.non_settable_x) // expected-error{{cannot pass immutable value as inout argument: 'non_settable_x' is a get-only property}}
z.non_settable_x += x // expected-error{{left side of mutating operator isn't mutable: 'non_settable_x' is a get-only property}}
-+++z.non_settable_x // expected-error{{cannot pass immutable value as inout argument: 'non_settable_x' is a get-only property}}
++++z.non_settable_x // expected-error{{cannot pass immutable value to mutating operator: 'non_settable_x' is a get-only property}}
// non-settable subscript is non-settable:
z[0] = 0.0 // expected-error{{cannot assign through subscript: subscript is get-only}}
@@ -97,7 +97,7 @@
f2(&fz().settable_x) // expected-error{{cannot pass immutable value as inout argument: 'fz' returns immutable value}}
f1(&fz().settable_x) // expected-error{{cannot pass immutable value as inout argument: 'fz' returns immutable value}}
fz().settable_x += x // expected-error{{left side of mutating operator isn't mutable: 'fz' returns immutable value}}
-+++fz().settable_x // expected-error{{cannot pass immutable value as inout argument: 'fz' returns immutable value}}
++++fz().settable_x // expected-error{{cannot pass immutable value to mutating operator: 'fz' returns immutable value}}
// settable property of an rvalue reference type IS SETTABLE:
fref().property = 0.0
diff --git a/test/expr/cast/array_iteration.swift b/test/expr/cast/array_iteration.swift
index a9e51ce..61e98e5 100644
--- a/test/expr/cast/array_iteration.swift
+++ b/test/expr/cast/array_iteration.swift
@@ -16,9 +16,7 @@
doFoo()
}
-// FIXME: Diagnostic below should be "'AnyObject' is not convertible to
-// 'View'", but IUO type gets in the way of proper diagnosis.
-for view:View in rootView.subviews { // expected-error{{type 'Array<AnyObject>?' does not conform to protocol 'Sequence'}}
+for view:View in rootView.subviews { // expected-error{{'AnyObject' is not convertible to 'View'}}
doFoo()
}
diff --git a/test/expr/expressions.swift b/test/expr/expressions.swift
index b8aeeeb..4a38054 100644
--- a/test/expr/expressions.swift
+++ b/test/expr/expressions.swift
@@ -614,7 +614,7 @@
i64 += 1
i8 -= 1
- Int64(5) += 1 // expected-error{{left side of mutating operator isn't mutable: function call returns immutable value}}
+ Int64(5) += 1 // expected-error{{left side of mutating operator has immutable type 'Int64'}}
// <rdar://problem/17691565> attempt to modify a 'let' variable with ++ results in typecheck error not being able to apply ++ to Float
let a = i8 // expected-note {{change 'let' to 'var' to make it mutable}} {{3-6=var}}
diff --git a/test/multifile/Inputs/require-finalize-witness-other.swift b/test/multifile/Inputs/require-finalize-witness-other.swift
new file mode 100644
index 0000000..eec03ff
--- /dev/null
+++ b/test/multifile/Inputs/require-finalize-witness-other.swift
@@ -0,0 +1,5 @@
+import Foundation
+
+extension C {
+ @objc func foo(_: String) { }
+}
diff --git a/test/multifile/require-finalize-witness.swift b/test/multifile/require-finalize-witness.swift
new file mode 100644
index 0000000..7c8b96a
--- /dev/null
+++ b/test/multifile/require-finalize-witness.swift
@@ -0,0 +1,14 @@
+// RUN: %target-swift-frontend -module-name test -emit-ir -primary-file %s %S/Inputs/require-finalize-witness-other.swift -sdk %sdk -o - | %FileCheck %s
+
+// REQUIRES: objc_interop
+
+import Foundation
+
+@objc class C: NSObject { }
+
+protocol P {
+ func foo(_: String)
+}
+
+// CHECK: define {{.*}} @"$S4test1CCAA1PA2aDP3fooyySSFTW"
+extension C: P { }
diff --git a/validation-test/stdlib/Algorithm.swift b/validation-test/stdlib/Algorithm.swift
index ef15ea3..e3405a6 100644
--- a/validation-test/stdlib/Algorithm.swift
+++ b/validation-test/stdlib/Algorithm.swift
@@ -243,7 +243,7 @@
]) {
// decorate with offset, but sort by value
var input = Array($0.enumerated())
- _sort3(&input, 0, 1, 2) { $0.element < $1.element }
+ input._sort3(0, 1, 2) { $0.element < $1.element }
// offsets should still be ordered for equal values
expectTrue(isSorted(input) {
if $0.element == $1.element {
diff --git a/validation-test/stdlib/FixedPointDiagnostics.swift.gyb b/validation-test/stdlib/FixedPointDiagnostics.swift.gyb
index 48d776b..164a162 100644
--- a/validation-test/stdlib/FixedPointDiagnostics.swift.gyb
+++ b/validation-test/stdlib/FixedPointDiagnostics.swift.gyb
@@ -95,7 +95,8 @@
x += Stride(1) // expected-error {{'+=' is unavailable: Please use explicit type conversions or Strideable methods for mixed-type arithmetics.}}
x -= Stride(1) // expected-error {{'-=' is unavailable: Please use explicit type conversions or Strideable methods for mixed-type arithmetics.}}
- _ = (x - x) as Stride // expected-error {{ambiguous reference to member '-'}}
+ // Terrible over-specific error, but at least disabled
+ _ = (x - x) as Stride // expected-error {{'(@lvalue ${T}, @lvalue ${T}) -> ${T}' is not convertible to '(${T}, ${T}) -> ${T}'}}
//===------------------------------------------------------------------===//
// The following errors are different because they're not being
diff --git a/validation-test/stdlib/Sort.swift.gyb b/validation-test/stdlib/Sort.swift.gyb
index 3ebd3e9..6cdd31c 100644
--- a/validation-test/stdlib/Sort.swift.gyb
+++ b/validation-test/stdlib/Sort.swift.gyb
@@ -120,7 +120,7 @@
let i1 = 400
let i2 = 700
sortedAry2 = ary
- _introSort(&sortedAry2, subRange: i1..<i2, by: <)
+ sortedAry2._introSort(within: i1..<i2, by: <)
expectEqual(ary[0..<i1], sortedAry2[0..<i1])
expectSortedCollection(sortedAry2[i1..<i2], ary[i1..<i2])
expectEqual(ary[i2..<count], sortedAry2[i2..<count])
