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])