Merge pull request #12303 from jckarter/keypath-subscript-coerce-index-4.0

[4.0] Sema: Coerce the type of the index expression in a key path component to match the subscript decl's index type.
diff --git a/lib/IDE/CodeCompletion.cpp b/lib/IDE/CodeCompletion.cpp
index 292c561..ed2f647 100644
--- a/lib/IDE/CodeCompletion.cpp
+++ b/lib/IDE/CodeCompletion.cpp
@@ -1537,7 +1537,7 @@
   case CodeCompletionLiteralKind::NilLiteral:
     return KnownProtocolKind::ExpressibleByNilLiteral;
   case CodeCompletionLiteralKind::StringLiteral:
-    return KnownProtocolKind::ExpressibleByStringLiteral;
+    return KnownProtocolKind::ExpressibleByUnicodeScalarLiteral;
   case CodeCompletionLiteralKind::Tuple:
     llvm_unreachable("no such protocol kind");
   }
diff --git a/stdlib/public/SDK/Foundation/NSStringAPI.swift b/stdlib/public/SDK/Foundation/NSStringAPI.swift
index c23bdbd..5746850 100644
--- a/stdlib/public/SDK/Foundation/NSStringAPI.swift
+++ b/stdlib/public/SDK/Foundation/NSStringAPI.swift
@@ -30,12 +30,6 @@
   return result
 }
 
-func _toNSRange(_ r: Range<String.Index>) -> NSRange {
-  return NSRange(
-    location: r.lowerBound.encodedOffset,
-    length: r.upperBound.encodedOffset - r.lowerBound.encodedOffset)
-}
-
 // We only need this for UnsafeMutablePointer, but there's not currently a way
 // to write that constraint.
 extension Optional {
@@ -417,10 +411,26 @@
     return self._ephemeralString as NSString
   }
 
+  // self can be a Substring so we need to subtract/add this offset when
+  // passing _ns to the Foundation APIs. Will be 0 if self is String.
+  @_inlineable
+  @_versioned
+  internal var _substringOffset: Int {
+    return self.startIndex.encodedOffset
+  }
+
   /// Return an `Index` corresponding to the given offset in our UTF-16
   /// representation.
   func _index(_ utf16Index: Int) -> Index {
-    return Index(encodedOffset: utf16Index)
+    return Index(encodedOffset: utf16Index + _substringOffset)
+  }
+
+  @_inlineable
+  @_versioned
+  internal func _toRelativeNSRange(_ r: Range<String.Index>) -> NSRange {
+    return NSRange(
+      location: r.lowerBound.encodedOffset - _substringOffset,
+      length: r.upperBound.encodedOffset - r.lowerBound.encodedOffset)
   }
 
   /// Return a `Range<Index>` corresponding to the given `NSRange` of
@@ -581,7 +591,7 @@
     return locale != nil ? _ns.compare(
       aString,
       options: mask,
-      range: _toNSRange(
+      range: _toRelativeNSRange(
         range ?? startIndex..<endIndex
       ),
       locale: locale
@@ -590,7 +600,7 @@
     : range != nil ? _ns.compare(
       aString,
       options: mask,
-      range: _toNSRange(range!)
+      range: _toRelativeNSRange(range!)
     )
 
     : !mask.isEmpty ? _ns.compare(aString, options: mask)
@@ -1008,7 +1018,7 @@
     T : StringProtocol, R : RangeExpression
   >(in range: R, with replacement: T) -> String where R.Bound == Index {
     return _ns.replacingCharacters(
-      in: _toNSRange(range.relative(to: self)),
+      in: _toRelativeNSRange(range.relative(to: self)),
       with: replacement._ephemeralString)
   }
 
@@ -1041,7 +1051,7 @@
       of: target,
       with: replacement,
       options: options,
-      range: _toNSRange(
+      range: _toRelativeNSRange(
         searchRange ?? startIndex..<endIndex
       )
     )
@@ -1163,7 +1173,7 @@
   ) where R.Bound == Index {
     let range = range.relative(to: self)
     _ns.enumerateLinguisticTags(
-      in: _toNSRange(range),
+      in: _toRelativeNSRange(range),
       scheme: tagScheme._ephemeralString,
       options: opts,
       orthography: orthography != nil ? orthography! : nil
@@ -1227,7 +1237,7 @@
     ) -> Void
   ) where R.Bound == Index {
     _ns.enumerateSubstrings(
-      in: _toNSRange(range.relative(to: self)), options: opts) {
+      in: _toRelativeNSRange(range.relative(to: self)), options: opts) {
       var stop_ = false
 
       body($0,
@@ -1300,7 +1310,7 @@
         usedLength: usedBufferCount,
         encoding: encoding.rawValue,
         options: options,
-        range: _toNSRange(range.relative(to: self)),
+        range: _toRelativeNSRange(range.relative(to: self)),
         remaining: $0)
     }
   }
@@ -1327,7 +1337,7 @@
           contentsEnd in self._ns.getLineStart(
             start, end: end,
             contentsEnd: contentsEnd,
-            for: _toNSRange(range.relative(to: self)))
+            for: _toRelativeNSRange(range.relative(to: self)))
         }
       }
     }
@@ -1355,7 +1365,7 @@
           contentsEnd in self._ns.getParagraphStart(
             start, end: end,
             contentsEnd: contentsEnd,
-            for: _toNSRange(range.relative(to: self)))
+            for: _toRelativeNSRange(range.relative(to: self)))
         }
       }
     }
@@ -1382,7 +1392,8 @@
   public func lineRange<
     R : RangeExpression
   >(for aRange: R) -> Range<Index> where R.Bound == Index {
-    return _range(_ns.lineRange(for: _toNSRange(aRange.relative(to: self))))
+    return _range(_ns.lineRange(
+      for: _toRelativeNSRange(aRange.relative(to: self))))
   }
 
   // - (NSArray *)
@@ -1406,7 +1417,7 @@
     var nsTokenRanges: NSArray?
     let result = tokenRanges._withNilOrAddress(of: &nsTokenRanges) {
       self._ns.linguisticTags(
-        in: _toNSRange(range.relative(to: self)),
+        in: _toRelativeNSRange(range.relative(to: self)),
         scheme: tagScheme._ephemeralString,
         options: opts,
         orthography: orthography,
@@ -1430,7 +1441,7 @@
     R : RangeExpression
   >(for aRange: R) -> Range<Index> where R.Bound == Index {
     return _range(
-      _ns.paragraphRange(for: _toNSRange(aRange.relative(to: self))))
+      _ns.paragraphRange(for: _toRelativeNSRange(aRange.relative(to: self))))
   }
 
   // - (NSRange)rangeOfCharacterFromSet:(NSCharacterSet *)aSet
@@ -1456,7 +1467,7 @@
       _ns.rangeOfCharacter(
         from: aSet,
         options: mask,
-        range: _toNSRange(
+        range: _toRelativeNSRange(
           aRange ?? startIndex..<endIndex
         )
       )
@@ -1487,7 +1498,7 @@
     // and output ranges due (if nothing else) to locale changes
     return _range(
       _ns.rangeOfComposedCharacterSequences(
-        for: _toNSRange(range.relative(to: self))))
+        for: _toRelativeNSRange(range.relative(to: self))))
   }
 
   // - (NSRange)rangeOfString:(NSString *)aString
@@ -1522,13 +1533,13 @@
       locale != nil ? _ns.range(
         of: aString,
         options: mask,
-        range: _toNSRange(
+        range: _toRelativeNSRange(
           searchRange ?? startIndex..<endIndex
         ),
         locale: locale
       )
       : searchRange != nil ? _ns.range(
-        of: aString, options: mask, range: _toNSRange(searchRange!)
+        of: aString, options: mask, range: _toRelativeNSRange(searchRange!)
       )
       : !mask.isEmpty ? _ns.range(of: aString, options: mask)
       : _ns.range(of: aString)
@@ -1637,7 +1648,7 @@
   @available(swift, deprecated: 4.0,
     message: "Please use String slicing subscript.")
   public func substring(with aRange: Range<Index>) -> String {
-    return _ns.substring(with: _toNSRange(aRange))
+    return _ns.substring(with: _toRelativeNSRange(aRange))
   }
 }
 
diff --git a/test/IDE/complete_value_literals.swift b/test/IDE/complete_value_literals.swift
index 6f02d3e..d4363ea 100644
--- a/test/IDE/complete_value_literals.swift
+++ b/test/IDE/complete_value_literals.swift
@@ -14,6 +14,9 @@
 // RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=STRING_0 | %FileCheck %s -check-prefix=STRING_0
 // RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=STRING_1 | %FileCheck %s -check-prefix=STRING_1
 // RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=STRING_2 | %FileCheck %s -check-prefix=STRING_2
+// RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=STRING_3 | %FileCheck %s -check-prefix=STRING_3
+// RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=STRING_4 | %FileCheck %s -check-prefix=STRING_4
+// RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=STRING_5 | %FileCheck %s -check-prefix=STRING_5
 // RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=ARRAY_0 | %FileCheck %s -check-prefix=ARRAY_0
 // RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=ARRAY_1 | %FileCheck %s -check-prefix=ARRAY_1
 // RUN: %target-swift-ide-test -code-completion -source-filename=%s -code-completion-token=ARRAY_2 | %FileCheck %s -check-prefix=ARRAY_2
@@ -62,6 +65,13 @@
   init(extendedGraphemeClusterLiteral value: String) {}
   init(stringLiteral value: String) {}
 }
+struct MyUnicodeScalar1: ExpressibleByUnicodeScalarLiteral {
+  init(unicodeScalarLiteral value: Character) {}
+}
+struct MyCharacter1: ExpressibleByExtendedGraphemeClusterLiteral {
+  init(unicodeScalarLiteral value: Character) {}
+  init(extendedGraphemeClusterLiteral value: String) {}
+}
 struct MyArray1<Element>: ExpressibleByArrayLiteral {
   init(arrayLiteral value: Element...) {}
 }
@@ -154,6 +164,19 @@
 }
 // STRING_2: Literal[String]/None/TypeRelation[Identical]: "{#(abc)#}"[#String#];
 
+func testString3() {
+  let x: MyUnicodeScalar1 = #^STRING_3^#
+}
+// STRING_3: Literal[String]/None/TypeRelation[Identical]: "{#(abc)#}"[#MyUnicodeScalar1#];
+func testString4() {
+  let x: MyCharacter1 = #^STRING_4^#
+}
+// STRING_4: Literal[String]/None/TypeRelation[Identical]: "{#(abc)#}"[#MyCharacter1#];
+func testString5() {
+  let x: Character = #^STRING_5^#
+}
+// STRING_5: Literal[String]/None/TypeRelation[Identical]: "{#(abc)#}"[#Character#];
+
 func testArray0() {
   let x: Int = #^ARRAY_0^#
 }
diff --git a/test/stdlib/NSStringAPI+Substring.swift b/test/stdlib/NSStringAPI+Substring.swift
new file mode 100644
index 0000000..92c9444
--- /dev/null
+++ b/test/stdlib/NSStringAPI+Substring.swift
@@ -0,0 +1,146 @@
+// RUN: rm -rf %t ; mkdir -p %t
+// RUN: %target-build-swift %s -o %t/a.out4 -swift-version 4 && %target-run %t/a.out4
+// REQUIRES: executable_test
+
+// REQUIRES: objc_interop
+
+//
+// Tests for the NSString APIs on Substring
+//
+
+import StdlibUnittest
+
+import Foundation
+
+
+extension String {
+  func range(fromStart: Int, fromEnd: Int) -> Range<String.Index> {
+    return index(startIndex, offsetBy: fromStart) ..<
+           index(endIndex, offsetBy: fromEnd)
+  }
+  subscript(fromStart: Int, fromEnd: Int) -> SubSequence {
+    return self[range(fromStart: fromStart, fromEnd: fromEnd)]
+  }
+}
+
+var tests = TestSuite("NSStringAPIs/Substring")
+
+tests.test("range(of:)/NilRange") {
+  let ss = "aabcdd"[1, -1]
+  let range = ss.range(of: "bc")
+  expectOptionalEqual("bc", range.map { ss[$0] })
+}
+
+tests.test("range(of:)/NonNilRange") {
+  let s = "aabcdd"
+  let ss = s[1, -1]
+  let searchRange = s.range(fromStart: 2, fromEnd: -2)
+  let range = ss.range(of: "bc", range: searchRange)
+  expectOptionalEqual("bc", range.map { ss[$0] })
+}
+
+tests.test("rangeOfCharacter") {
+  let ss = "__hello__"[2, -2]
+  let range = ss.rangeOfCharacter(from: CharacterSet.alphanumerics)
+  expectOptionalEqual("h", range.map { ss[$0] })
+}
+
+tests.test("compare(_:options:range:locale:)/NilRange") {
+  let needle = "hello"
+  let haystack = "__hello__"[2, -2]
+  expectEqual(.orderedSame, haystack.compare(needle))
+}
+
+tests.test("compare(_:options:range:locale:)/NonNilRange") {
+  let needle = "hello"
+  let haystack = "__hello__"
+  let range = haystack.range(fromStart: 2, fromEnd: -2)
+  expectEqual(.orderedSame, haystack[range].compare(needle, range: range))
+}
+
+tests.test("replacingCharacters(in:with:)") {
+  let s = "__hello, world"
+  let range = s.range(fromStart: 2, fromEnd: -7)
+  let expected = "__goodbye, world"
+  let replacement = "goodbye"
+  expectEqual(expected,
+    s.replacingCharacters(in: range, with: replacement))
+  expectEqual(expected[2, 0],
+    s[2, 0].replacingCharacters(in: range, with: replacement))
+
+  expectEqual(replacement,
+    s.replacingCharacters(in: s.startIndex..., with: replacement))
+  expectEqual(replacement,
+    s.replacingCharacters(in: ..<s.endIndex, with: replacement))
+  expectEqual(expected[2, 0],
+    s[2, 0].replacingCharacters(in: range, with: replacement[...]))
+}
+
+tests.test("replacingOccurrences(of:with:options:range:)/NilRange") {
+  let s = "hello"
+
+  expectEqual("he11o", s.replacingOccurrences(of: "l", with: "1"))
+  expectEqual("he11o", s.replacingOccurrences(of: "l"[...], with: "1"))
+  expectEqual("he11o", s.replacingOccurrences(of: "l", with: "1"[...]))
+  expectEqual("he11o", s.replacingOccurrences(of: "l"[...], with: "1"[...]))
+
+  expectEqual("he11o",
+    s[...].replacingOccurrences(of: "l", with: "1"))
+  expectEqual("he11o",
+    s[...].replacingOccurrences(of: "l"[...], with: "1"))
+  expectEqual("he11o",
+    s[...].replacingOccurrences(of: "l", with: "1"[...]))
+  expectEqual("he11o",
+    s[...].replacingOccurrences(of: "l"[...], with: "1"[...]))
+}
+
+tests.test("replacingOccurrences(of:with:options:range:)/NonNilRange") {
+  let s = "hello"
+  let r = s.range(fromStart: 1, fromEnd: -2)
+
+  expectEqual("he1lo",
+    s.replacingOccurrences(of: "l", with: "1", range: r))
+  expectEqual("he1lo",
+    s.replacingOccurrences(of: "l"[...], with: "1", range: r))
+  expectEqual("he1lo",
+    s.replacingOccurrences(of: "l", with: "1"[...], range: r))
+  expectEqual("he1lo",
+    s.replacingOccurrences(of: "l"[...], with: "1"[...], range: r))
+
+  expectEqual("he1lo",
+    s[...].replacingOccurrences(of: "l", with: "1", range: r))
+  expectEqual("he1lo",
+    s[...].replacingOccurrences(of: "l"[...], with: "1", range: r))
+  expectEqual("he1lo",
+    s[...].replacingOccurrences(of: "l", with: "1"[...], range: r))
+  expectEqual("he1lo",
+    s[...].replacingOccurrences(of: "l"[...], with: "1"[...], range: r))
+
+  let ss = s[1, -1]
+  expectEqual("e1l",
+    ss.replacingOccurrences(of: "l", with: "1", range: r))
+  expectEqual("e1l",
+    ss.replacingOccurrences(of: "l"[...], with: "1", range: r))
+  expectEqual("e1l",
+    ss.replacingOccurrences(of: "l", with: "1"[...], range: r))
+  expectEqual("e1l",
+    ss.replacingOccurrences(of: "l"[...], with: "1"[...], range: r))
+}
+
+tests.test("substring(with:)") {
+  let s = "hello, world"
+  let r = s.range(fromStart: 7, fromEnd: 0)
+  expectEqual("world", s.substring(with: r))
+  expectEqual("world", s[...].substring(with: r))
+  expectEqual("world", s[1, 0].substring(with: r))
+}
+
+tests.test("substring(with:)/SubscriptEquivalence") {
+  let s = "hello, world"
+  let r = s.range(fromStart: 7, fromEnd: 0)
+  expectEqual(s[r], s.substring(with: r))
+  expectEqual(s[...][r], s[...].substring(with: r))
+  expectEqual(s[1, 0][r], s[1, 0].substring(with: r))
+}
+
+runAllTests()
diff --git a/test/stdlib/NSStringAPI.swift b/test/stdlib/NSStringAPI.swift
index 72e4376..4d7d2a7 100644
--- a/test/stdlib/NSStringAPI.swift
+++ b/test/stdlib/NSStringAPI.swift
@@ -1,4 +1,4 @@
-// RUN: %target-run-simple-swift -swift-version 3
+// RUN: %target-run-simple-swift
 // REQUIRES: executable_test
 
 // REQUIRES: objc_interop
@@ -1144,9 +1144,11 @@
       for: s.index(s.startIndex, offsetBy: 8)..<s.index(s.startIndex, offsetBy: 10))])
 }
 
-func toIntRange(
-  _ string: String, _ maybeRange: Range<String.Index>?
-) -> Range<Int>? {
+func toIntRange<
+  S : StringProtocol
+>(
+  _ string: S, _ maybeRange: Range<String.Index>?
+) -> Range<Int>? where S.Index == String.Index, S.IndexDistance == Int {
   guard let range = maybeRange else { return nil }
 
   return