stdlib/public/core/StringComparison.swift - third_party/swift - Git at Google

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

 import SwiftShims

 @inlinable @inline(__always) // top-level fastest-paths
 @_effects(readonly)
 internal func _stringCompare(
   _ lhs: _StringGuts, _ rhs: _StringGuts, expecting: _StringComparisonResult
 ) -> Bool {
   if lhs.rawBits == rhs.rawBits { return expecting == .equal }
   return _stringCompareWithSmolCheck(lhs, rhs, expecting: expecting)
 }

 @usableFromInline
 @_effects(readonly)
 internal func _stringCompareWithSmolCheck(
   _ lhs: _StringGuts, _ rhs: _StringGuts, expecting: _StringComparisonResult
 ) -> Bool {
   // ASCII small-string fast-path:
   if lhs.isSmallASCII && rhs.isSmallASCII {
     let lhsRaw = lhs.asSmall._storage
     let rhsRaw = rhs.asSmall._storage

     if lhsRaw.0 != rhsRaw.0 {
       return _lexicographicalCompare(
         lhsRaw.0.bigEndian, rhsRaw.0.bigEndian, expecting: expecting)
     }
     return _lexicographicalCompare(
       lhsRaw.1.bigEndian, rhsRaw.1.bigEndian, expecting: expecting)
   }

   return _stringCompareInternal(lhs, rhs, expecting: expecting)
 }

 @inline(never) // Keep `_stringCompareWithSmolCheck` fast-path fast
 @usableFromInline
 @_effects(readonly)
 internal func _stringCompareInternal(
   _ lhs: _StringGuts, _ rhs: _StringGuts, expecting: _StringComparisonResult
 ) -> Bool {
   guard _fastPath(lhs.isFastUTF8 && rhs.isFastUTF8) else {
     return _stringCompareSlow(lhs, rhs, expecting: expecting)
   }

   let isNFC = lhs.isNFC && rhs.isNFC
   return lhs.withFastUTF8 { lhsUTF8 in
     return rhs.withFastUTF8 { rhsUTF8 in
       return _stringCompareFastUTF8(
         lhsUTF8, rhsUTF8, expecting: expecting, bothNFC: isNFC)
     }
   }
 }

 @inlinable @inline(__always) // top-level fastest-paths
 @_effects(readonly)
 internal func _stringCompare(
   _ lhs: _StringGuts, _ lhsRange: Range<Int>,
   _ rhs: _StringGuts, _ rhsRange: Range<Int>,
   expecting: _StringComparisonResult
 ) -> Bool {
   if lhs.rawBits == rhs.rawBits && lhsRange == rhsRange {
     return expecting == .equal
   }
   return _stringCompareInternal(
     lhs, lhsRange, rhs, rhsRange, expecting: expecting)
 }

 @usableFromInline
 @_effects(readonly)
 internal func _stringCompareInternal(
   _ lhs: _StringGuts, _ lhsRange: Range<Int>,
   _ rhs: _StringGuts, _ rhsRange: Range<Int>,
   expecting: _StringComparisonResult
 ) -> Bool {
   guard _fastPath(lhs.isFastUTF8 && rhs.isFastUTF8) else {
     return _stringCompareSlow(
       lhs, lhsRange, rhs, rhsRange, expecting: expecting)
   }

   let isNFC = lhs.isNFC && rhs.isNFC
   return lhs.withFastUTF8(range: lhsRange) { lhsUTF8 in
     return rhs.withFastUTF8(range: rhsRange) { rhsUTF8 in
       return _stringCompareFastUTF8(
         lhsUTF8, rhsUTF8, expecting: expecting, bothNFC: isNFC)
     }
   }
 }

 @_effects(readonly)
 private func _stringCompareFastUTF8(
   _ utf8Left: UnsafeBufferPointer<UInt8>,
   _ utf8Right: UnsafeBufferPointer<UInt8>,
   expecting: _StringComparisonResult,
   bothNFC: Bool
 ) -> Bool {
   if _fastPath(bothNFC) {
     let cmp = _binaryCompare(utf8Left, utf8Right)
     return _lexicographicalCompare(cmp, 0, expecting: expecting)
   }

   return _stringCompareFastUTF8Abnormal(
     utf8Left, utf8Right, expecting: expecting)
 }

 @_effects(readonly)
 private func _stringCompareFastUTF8Abnormal(
   _ utf8Left: UnsafeBufferPointer<UInt8>,
   _ utf8Right: UnsafeBufferPointer<UInt8>,
   expecting: _StringComparisonResult
 ) -> Bool {
   // Do a binary-equality prefix scan, to skip over long common prefixes.
   guard let diffIdx = _findDiffIdx(utf8Left, utf8Right) else {
     // We finished one of our inputs.
     //
     // TODO: This gives us a consistent and good ordering, but technically it
     // could differ from our stated ordering if combination with a prior scalar
     // did not produce a greater-value scalar. Consider checking normality.
     return _lexicographicalCompare(
       utf8Left.count, utf8Right.count, expecting: expecting)
   }

   let scalarDiffIdx = _scalarAlign(utf8Left, diffIdx)
   _internalInvariant(scalarDiffIdx == _scalarAlign(utf8Right, diffIdx))

   let (leftScalar, leftLen) = _decodeScalar(utf8Left, startingAt: scalarDiffIdx)
   let (rightScalar, rightLen) = _decodeScalar(
     utf8Right, startingAt: scalarDiffIdx)

   // Very frequent fast-path: point of binary divergence is a NFC single-scalar
   // segment. Check that we diverged at the start of a segment, and the next
   // scalar is both NFC and its own segment.
   if _fastPath(
     leftScalar._isNFCStarter && rightScalar._isNFCStarter &&
     utf8Left.hasNormalizationBoundary(before: scalarDiffIdx &+ leftLen) &&
     utf8Right.hasNormalizationBoundary(before: scalarDiffIdx &+ rightLen)
   ) {
     guard expecting == .less else {
       // We diverged
       _internalInvariant(expecting == .equal)
       return false
     }
     return _lexicographicalCompare(
       leftScalar.value, rightScalar.value, expecting: .less)
   }

   // Back up to the nearest normalization boundary before doing a slow
   // normalizing compare.
   let boundaryIdx = Swift.min(
     _findBoundary(utf8Left, before: diffIdx),
     _findBoundary(utf8Right, before: diffIdx))
   _internalInvariant(boundaryIdx <= diffIdx)

   return _stringCompareSlow(
     UnsafeBufferPointer(rebasing: utf8Left[boundaryIdx...]),
     UnsafeBufferPointer(rebasing: utf8Right[boundaryIdx...]),
     expecting: expecting)
 }

 @_effects(readonly)
 private func _stringCompareSlow(
   _ lhs: _StringGuts, _ rhs: _StringGuts, expecting: _StringComparisonResult
 ) -> Bool {
   return _stringCompareSlow(
     lhs, 0..<lhs.count, rhs, 0..<rhs.count, expecting: expecting)
 }

 @_effects(readonly)
 private func _stringCompareSlow(
   _ lhs: _StringGuts, _ lhsRange: Range<Int>,
   _ rhs: _StringGuts, _ rhsRange: Range<Int>,
   expecting: _StringComparisonResult
 ) -> Bool {
   // TODO: Just call the normalizer directly with range

   return _StringGutsSlice(lhs, lhsRange).compare(
     with: _StringGutsSlice(rhs, rhsRange),
     expecting: expecting)
 }

 @_effects(readonly)
 private func _stringCompareSlow(
   _ leftUTF8: UnsafeBufferPointer<UInt8>,
   _ rightUTF8: UnsafeBufferPointer<UInt8>,
   expecting: _StringComparisonResult
 ) -> Bool {
   // TODO: Just call the normalizer directly

   let left = _StringGutsSlice(_StringGuts(leftUTF8, isASCII: false))
   let right = _StringGutsSlice(_StringGuts(rightUTF8, isASCII: false))
   return left.compare(with: right, expecting: expecting)
 }

 // Return the point of binary divergence. If they have no binary difference
 // (even if one is longer), returns nil.
 @_effects(readonly)
 private func _findDiffIdx(
   _ left: UnsafeBufferPointer<UInt8>, _ right: UnsafeBufferPointer<UInt8>
 ) -> Int? {
   let count = Swift.min(left.count, right.count)
   var idx = 0
   while idx < count {
     guard left[_unchecked: idx] == right[_unchecked: idx] else {
       return idx
     }
     idx &+= 1
   }
   return nil
 }

 @_effects(readonly)
 @inline(__always)
 private func _lexicographicalCompare<I: FixedWidthInteger>(
   _ lhs: I, _ rhs: I, expecting: _StringComparisonResult
 ) -> Bool {
   return expecting == .equal ? lhs == rhs : lhs < rhs
 }

 @_effects(readonly)
 private func _findBoundary(
   _ utf8: UnsafeBufferPointer<UInt8>, before: Int
 ) -> Int {
   var idx = before
   _internalInvariant(idx >= 0)

   // End of string is a normalization boundary
   guard idx < utf8.count else {
     _internalInvariant(before == utf8.count)
     return utf8.count
   }

   // Back up to scalar boundary
   while UTF8.isContinuation(utf8[_unchecked: idx]) {
     idx &-= 1
   }

   while true {
     if idx == 0 { return 0 }

     let scalar = _decodeScalar(utf8, startingAt: idx).0
     if scalar._hasNormalizationBoundaryBefore { return idx }

     idx &-= _utf8ScalarLength(utf8, endingAt: idx)
   }
 }

 @_frozen
 @usableFromInline
 internal enum _StringComparisonResult {
   case equal
   case less

   @inlinable @inline(__always)
   internal init(signedNotation int: Int) {
     _internalInvariant(int <= 0)
     self = int == 0 ? .equal : .less
   }

   @inlinable @inline(__always)
   static func ==(
     _ lhs: _StringComparisonResult, _ rhs: _StringComparisonResult
   ) -> Bool {
     switch (lhs, rhs) {
       case (.equal, .equal): return true
       case (.less, .less): return true
       default: return false
     }
   }
 }

 // Perform a binary comparison of bytes in memory. Return value is negative if
 // less, 0 if equal, positive if greater.
 @_effects(readonly)
 internal func _binaryCompare<UInt8>(
   _ lhs: UnsafeBufferPointer<UInt8>, _ rhs: UnsafeBufferPointer<UInt8>
 ) -> Int {
   var cmp = Int(truncatingIfNeeded:
     _swift_stdlib_memcmp(
       lhs.baseAddress._unsafelyUnwrappedUnchecked,
       rhs.baseAddress._unsafelyUnwrappedUnchecked,
       Swift.min(lhs.count, rhs.count)))
   if cmp == 0 {
     cmp = lhs.count &- rhs.count
   }
   return cmp
 }

 // Double dispatch functions
 extension _StringGutsSlice {
   @_effects(readonly)
   internal func compare(
     with other: _StringGutsSlice, expecting: _StringComparisonResult
   ) -> Bool {
     if _fastPath(self.isFastUTF8 && other.isFastUTF8) {
       Builtin.onFastPath() // aggressively inline / optimize
       let isEqual = self.withFastUTF8 { utf8Self in
         return other.withFastUTF8 { utf8Other in
           return 0 == _binaryCompare(utf8Self, utf8Other)
         }
       }
       if isEqual { return expecting == .equal }
     }

     return _slowCompare(with: other, expecting: expecting)
   }

   @inline(never) // opaque slow-path
   @_effects(readonly)
   internal func _slowCompare(
     with other: _StringGutsSlice,
     expecting: _StringComparisonResult
   ) -> Bool {
     var left_output = _FixedArray16<UInt8>(allZeros: ())
     var left_icuInput = _FixedArray16<UInt16>(allZeros: ())
     var left_icuOutput = _FixedArray16<UInt16>(allZeros: ())
     var right_output = _FixedArray16<UInt8>(allZeros: ())
     var right_icuInput = _FixedArray16<UInt16>(allZeros: ())
     var right_icuOutput = _FixedArray16<UInt16>(allZeros: ())
     if _fastPath(self.isFastUTF8 && other.isFastUTF8) {
       return self.withFastUTF8 { leftUTF8 in
         other.withFastUTF8 { rightUTF8 in
           let leftStartIndex = String.Index(_encodedOffset: 0)
           let rightStartIndex = String.Index(_encodedOffset: 0)
           let leftEndIndex = String.Index(_encodedOffset: leftUTF8.count)
           let rightEndIndex = String.Index(_encodedOffset: rightUTF8.count)
           return _normalizedCompareImpl(
             left_outputBuffer: _castOutputBuffer(&left_output),
             left_icuInputBuffer: _castOutputBuffer(&left_icuInput),
             left_icuOutputBuffer: _castOutputBuffer(&left_icuOutput),
             right_outputBuffer: _castOutputBuffer(&right_output),
             right_icuInputBuffer: _castOutputBuffer(&right_icuInput),
             right_icuOutputBuffer: _castOutputBuffer(&right_icuOutput),
             left_range: leftStartIndex..<leftEndIndex,
             right_range: rightStartIndex..<rightEndIndex,
             expecting: expecting,
             normalizeLeft: { readIndex, outputBuffer, icuInputBuffer, icuOutputBuffer in
               _fastNormalize(
                 readIndex: readIndex,
                 sourceBuffer: leftUTF8,
                 outputBuffer: &outputBuffer,
                 icuInputBuffer: &icuInputBuffer,
                 icuOutputBuffer: &icuOutputBuffer)
             },
             normalizeRight: { readIndex, outputBuffer, icuInputBuffer, icuOutputBuffer in
               _fastNormalize(
                 readIndex: readIndex,
                 sourceBuffer: rightUTF8,
                 outputBuffer: &outputBuffer,
                 icuInputBuffer: &icuInputBuffer,
                 icuOutputBuffer: &icuOutputBuffer)
             })
         }
       }
     } else {
       return _normalizedCompareImpl(
         left_outputBuffer: _castOutputBuffer(&left_output),
         left_icuInputBuffer: _castOutputBuffer(&left_icuInput),
         left_icuOutputBuffer: _castOutputBuffer(&left_icuOutput),
         right_outputBuffer: _castOutputBuffer(&right_output),
         right_icuInputBuffer: _castOutputBuffer(&right_icuInput),
         right_icuOutputBuffer: _castOutputBuffer(&right_icuOutput),
         left_range: range,
         right_range: other.range,
         expecting: expecting,
         normalizeLeft: { readIndex, outputBuffer, icuInputBuffer, icuOutputBuffer in
           _foreignNormalize(
             readIndex: readIndex,
             endIndex: range.upperBound,
             guts: _guts,
             outputBuffer: &outputBuffer,
             icuInputBuffer: &icuInputBuffer,
             icuOutputBuffer: &icuOutputBuffer)
         },
         normalizeRight: { readIndex, outputBuffer, icuInputBuffer, icuOutputBuffer in
           _foreignNormalize(
             readIndex: readIndex,
             endIndex: other.range.upperBound,
             guts: other._guts,
             outputBuffer: &outputBuffer,
             icuInputBuffer: &icuInputBuffer,
             icuOutputBuffer: &icuOutputBuffer)
         })
     }
   }


   @inline(__always) //Avoid unecessary overhead from the closures.
   internal func _normalizedCompareImpl(
     left_outputBuffer: UnsafeMutableBufferPointer<UInt8>,
     left_icuInputBuffer: UnsafeMutableBufferPointer<UInt16>,
     left_icuOutputBuffer: UnsafeMutableBufferPointer<UInt16>,
     right_outputBuffer: UnsafeMutableBufferPointer<UInt8>,
     right_icuInputBuffer: UnsafeMutableBufferPointer<UInt16>,
     right_icuOutputBuffer: UnsafeMutableBufferPointer<UInt16>,
     left_range: Range<String.Index>,
     right_range: Range<String.Index>,
     expecting: _StringComparisonResult,
     normalizeLeft: (
       _ readIndex: String.Index,
       _ outputBuffer: inout UnsafeMutableBufferPointer<UInt8>,
       _ icuInputBuffer: inout UnsafeMutableBufferPointer<UInt16>,
       _ icuOutputBuffer: inout UnsafeMutableBufferPointer<UInt16>) -> NormalizationResult,
     normalizeRight: (
       _ readIndex: String.Index,
       _ outputBuffer: inout UnsafeMutableBufferPointer<UInt8>,
       _ icuInputBuffer: inout UnsafeMutableBufferPointer<UInt16>,
       _ icuOutputBuffer: inout UnsafeMutableBufferPointer<UInt16>) -> NormalizationResult
   ) -> Bool {
     var left_outputBuffer = left_outputBuffer
     var left_icuInputBuffer = left_icuInputBuffer
     var left_icuOutputBuffer = left_icuOutputBuffer
     var right_outputBuffer = right_outputBuffer
     var right_icuInputBuffer = right_icuInputBuffer
     var right_icuOutputBuffer = right_icuOutputBuffer

     var leftNextReadPosition = left_range.lowerBound
     var rightNextReadPosition = right_range.lowerBound
     var leftOutputBufferIndex = 0
     var rightOutputBufferIndex = 0
     var leftOutputBufferCount = 0
     var rightOutputBufferCount = 0
     let leftEndIndex = left_range.upperBound
     let rightEndIndex = right_range.upperBound

     var hasLeftBufferOwnership = false
     var hasRightBufferOwnership = false

     if left_range.isEmpty && right_range.isEmpty {
       return expecting == .equal
     }
     if left_range.isEmpty {
       return expecting == .less
     }
     if right_range.isEmpty {
       return false
     }

     defer {
       if hasLeftBufferOwnership {
         left_outputBuffer.deallocate()
         left_icuInputBuffer.deallocate()
         left_icuOutputBuffer.deallocate()
       }
       if hasRightBufferOwnership {
         right_outputBuffer.deallocate()
         right_icuInputBuffer.deallocate()
         right_icuOutputBuffer.deallocate()
       }
     }

     repeat {
       if leftOutputBufferIndex == leftOutputBufferCount {
         let result = normalizeLeft(
           leftNextReadPosition,
           &left_outputBuffer,
           &left_icuInputBuffer,
           &left_icuOutputBuffer)
         _internalInvariant(result.nextReadPosition != leftNextReadPosition)
         leftOutputBufferCount = result.amountFilled
         leftOutputBufferIndex = 0
         leftNextReadPosition = result.nextReadPosition
         if result.allocatedBuffers {
           _internalInvariant(!hasLeftBufferOwnership)
           hasLeftBufferOwnership = true
         }
       }
       if rightOutputBufferIndex == rightOutputBufferCount {
         let result = normalizeRight(
           rightNextReadPosition,
           &right_outputBuffer,
           &right_icuInputBuffer,
           &right_icuOutputBuffer)
         _internalInvariant(result.nextReadPosition != rightNextReadPosition)
         rightOutputBufferCount = result.amountFilled
         rightOutputBufferIndex = 0
         rightNextReadPosition = result.nextReadPosition
         if result.allocatedBuffers {
           _internalInvariant(!hasRightBufferOwnership)
           hasRightBufferOwnership = true
         }
       }
       while leftOutputBufferIndex < leftOutputBufferCount && rightOutputBufferIndex < rightOutputBufferCount {
         let leftCU = left_outputBuffer[leftOutputBufferIndex]
         let rightCU = right_outputBuffer[rightOutputBufferIndex]
         if leftCU == rightCU {
           leftOutputBufferIndex += 1
           rightOutputBufferIndex += 1
           continue
         } else if leftCU < rightCU {
           return expecting == .less
         } else {
           return false
         }
       }
     } while (leftNextReadPosition < leftEndIndex
     || leftOutputBufferIndex < leftOutputBufferCount)
     && (rightNextReadPosition < rightEndIndex
     || rightOutputBufferIndex < rightOutputBufferCount)


     //At least one of them ran out of code units, whichever it was is the "smaller" string
     if leftNextReadPosition < leftEndIndex
     || leftOutputBufferIndex < leftOutputBufferCount {
       return false
     } else if rightNextReadPosition < rightEndIndex
     || rightOutputBufferIndex < rightOutputBufferCount {
       return expecting == .less
     } else {
       //They both ran out
       return expecting == .equal
     }
   }
 }
	//===----------------------------------------------------------------------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2018 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//

	import SwiftShims

	@inlinable @inline(__always) // top-level fastest-paths
	@_effects(readonly)
	internal func _stringCompare(
	_ lhs: _StringGuts, _ rhs: _StringGuts, expecting: _StringComparisonResult
	) -> Bool {
	if lhs.rawBits == rhs.rawBits { return expecting == .equal }
	return _stringCompareWithSmolCheck(lhs, rhs, expecting: expecting)
	}

	@usableFromInline
	@_effects(readonly)
	internal func _stringCompareWithSmolCheck(
	_ lhs: _StringGuts, _ rhs: _StringGuts, expecting: _StringComparisonResult
	) -> Bool {
	// ASCII small-string fast-path:
	if lhs.isSmallASCII && rhs.isSmallASCII {
	let lhsRaw = lhs.asSmall._storage
	let rhsRaw = rhs.asSmall._storage

	if lhsRaw.0 != rhsRaw.0 {
	return _lexicographicalCompare(
	lhsRaw.0.bigEndian, rhsRaw.0.bigEndian, expecting: expecting)
	}
	return _lexicographicalCompare(
	lhsRaw.1.bigEndian, rhsRaw.1.bigEndian, expecting: expecting)
	}

	return _stringCompareInternal(lhs, rhs, expecting: expecting)
	}

	@inline(never) // Keep `_stringCompareWithSmolCheck` fast-path fast
	@usableFromInline
	@_effects(readonly)
	internal func _stringCompareInternal(
	_ lhs: _StringGuts, _ rhs: _StringGuts, expecting: _StringComparisonResult
	) -> Bool {
	guard _fastPath(lhs.isFastUTF8 && rhs.isFastUTF8) else {
	return _stringCompareSlow(lhs, rhs, expecting: expecting)
	}

	let isNFC = lhs.isNFC && rhs.isNFC
	return lhs.withFastUTF8 { lhsUTF8 in
	return rhs.withFastUTF8 { rhsUTF8 in
	return _stringCompareFastUTF8(
	lhsUTF8, rhsUTF8, expecting: expecting, bothNFC: isNFC)
	}
	}
	}

	@inlinable @inline(__always) // top-level fastest-paths
	@_effects(readonly)
	internal func _stringCompare(
	_ lhs: _StringGuts, _ lhsRange: Range<Int>,
	_ rhs: _StringGuts, _ rhsRange: Range<Int>,
	expecting: _StringComparisonResult
	) -> Bool {
	if lhs.rawBits == rhs.rawBits && lhsRange == rhsRange {
	return expecting == .equal
	}
	return _stringCompareInternal(
	lhs, lhsRange, rhs, rhsRange, expecting: expecting)
	}

	@usableFromInline
	@_effects(readonly)
	internal func _stringCompareInternal(
	_ lhs: _StringGuts, _ lhsRange: Range<Int>,
	_ rhs: _StringGuts, _ rhsRange: Range<Int>,
	expecting: _StringComparisonResult
	) -> Bool {
	guard _fastPath(lhs.isFastUTF8 && rhs.isFastUTF8) else {
	return _stringCompareSlow(
	lhs, lhsRange, rhs, rhsRange, expecting: expecting)
	}

	let isNFC = lhs.isNFC && rhs.isNFC
	return lhs.withFastUTF8(range: lhsRange) { lhsUTF8 in
	return rhs.withFastUTF8(range: rhsRange) { rhsUTF8 in
	return _stringCompareFastUTF8(
	lhsUTF8, rhsUTF8, expecting: expecting, bothNFC: isNFC)
	}
	}
	}

	@_effects(readonly)
	private func _stringCompareFastUTF8(
	_ utf8Left: UnsafeBufferPointer<UInt8>,
	_ utf8Right: UnsafeBufferPointer<UInt8>,
	expecting: _StringComparisonResult,
	bothNFC: Bool
	) -> Bool {
	if _fastPath(bothNFC) {
	let cmp = _binaryCompare(utf8Left, utf8Right)
	return _lexicographicalCompare(cmp, 0, expecting: expecting)
	}

	return _stringCompareFastUTF8Abnormal(
	utf8Left, utf8Right, expecting: expecting)
	}

	@_effects(readonly)
	private func _stringCompareFastUTF8Abnormal(
	_ utf8Left: UnsafeBufferPointer<UInt8>,
	_ utf8Right: UnsafeBufferPointer<UInt8>,
	expecting: _StringComparisonResult
	) -> Bool {
	// Do a binary-equality prefix scan, to skip over long common prefixes.
	guard let diffIdx = _findDiffIdx(utf8Left, utf8Right) else {
	// We finished one of our inputs.
	//
	// TODO: This gives us a consistent and good ordering, but technically it
	// could differ from our stated ordering if combination with a prior scalar
	// did not produce a greater-value scalar. Consider checking normality.
	return _lexicographicalCompare(
	utf8Left.count, utf8Right.count, expecting: expecting)
	}

	let scalarDiffIdx = _scalarAlign(utf8Left, diffIdx)
	_internalInvariant(scalarDiffIdx == _scalarAlign(utf8Right, diffIdx))

	let (leftScalar, leftLen) = _decodeScalar(utf8Left, startingAt: scalarDiffIdx)
	let (rightScalar, rightLen) = _decodeScalar(
	utf8Right, startingAt: scalarDiffIdx)

	// Very frequent fast-path: point of binary divergence is a NFC single-scalar
	// segment. Check that we diverged at the start of a segment, and the next
	// scalar is both NFC and its own segment.
	if _fastPath(
	leftScalar._isNFCStarter && rightScalar._isNFCStarter &&
	utf8Left.hasNormalizationBoundary(before: scalarDiffIdx &+ leftLen) &&
	utf8Right.hasNormalizationBoundary(before: scalarDiffIdx &+ rightLen)
	) {
	guard expecting == .less else {
	// We diverged
	_internalInvariant(expecting == .equal)
	return false
	}
	return _lexicographicalCompare(
	leftScalar.value, rightScalar.value, expecting: .less)
	}

	// Back up to the nearest normalization boundary before doing a slow
	// normalizing compare.
	let boundaryIdx = Swift.min(
	_findBoundary(utf8Left, before: diffIdx),
	_findBoundary(utf8Right, before: diffIdx))
	_internalInvariant(boundaryIdx <= diffIdx)

	return _stringCompareSlow(
	UnsafeBufferPointer(rebasing: utf8Left[boundaryIdx...]),
	UnsafeBufferPointer(rebasing: utf8Right[boundaryIdx...]),
	expecting: expecting)
	}

	@_effects(readonly)
	private func _stringCompareSlow(
	_ lhs: _StringGuts, _ rhs: _StringGuts, expecting: _StringComparisonResult
	) -> Bool {
	return _stringCompareSlow(
	lhs, 0..<lhs.count, rhs, 0..<rhs.count, expecting: expecting)
	}

	@_effects(readonly)
	private func _stringCompareSlow(
	_ lhs: _StringGuts, _ lhsRange: Range<Int>,
	_ rhs: _StringGuts, _ rhsRange: Range<Int>,
	expecting: _StringComparisonResult
	) -> Bool {
	// TODO: Just call the normalizer directly with range

	return _StringGutsSlice(lhs, lhsRange).compare(
	with: _StringGutsSlice(rhs, rhsRange),
	expecting: expecting)
	}

	@_effects(readonly)
	private func _stringCompareSlow(
	_ leftUTF8: UnsafeBufferPointer<UInt8>,
	_ rightUTF8: UnsafeBufferPointer<UInt8>,
	expecting: _StringComparisonResult
	) -> Bool {
	// TODO: Just call the normalizer directly

	let left = _StringGutsSlice(_StringGuts(leftUTF8, isASCII: false))
	let right = _StringGutsSlice(_StringGuts(rightUTF8, isASCII: false))
	return left.compare(with: right, expecting: expecting)
	}

	// Return the point of binary divergence. If they have no binary difference
	// (even if one is longer), returns nil.
	@_effects(readonly)
	private func _findDiffIdx(
	_ left: UnsafeBufferPointer<UInt8>, _ right: UnsafeBufferPointer<UInt8>
	) -> Int? {
	let count = Swift.min(left.count, right.count)
	var idx = 0
	while idx < count {
	guard left[_unchecked: idx] == right[_unchecked: idx] else {
	return idx
	}
	idx &+= 1
	}
	return nil
	}

	@_effects(readonly)
	@inline(__always)
	private func _lexicographicalCompare<I: FixedWidthInteger>(
	_ lhs: I, _ rhs: I, expecting: _StringComparisonResult
	) -> Bool {
	return expecting == .equal ? lhs == rhs : lhs < rhs
	}

	@_effects(readonly)
	private func _findBoundary(
	_ utf8: UnsafeBufferPointer<UInt8>, before: Int
	) -> Int {
	var idx = before
	_internalInvariant(idx >= 0)

	// End of string is a normalization boundary
	guard idx < utf8.count else {
	_internalInvariant(before == utf8.count)
	return utf8.count
	}

	// Back up to scalar boundary
	while UTF8.isContinuation(utf8[_unchecked: idx]) {
	idx &-= 1
	}

	while true {
	if idx == 0 { return 0 }

	let scalar = _decodeScalar(utf8, startingAt: idx).0
	if scalar._hasNormalizationBoundaryBefore { return idx }

	idx &-= _utf8ScalarLength(utf8, endingAt: idx)
	}
	}

	@_frozen
	@usableFromInline
	internal enum _StringComparisonResult {
	case equal
	case less

	@inlinable @inline(__always)
	internal init(signedNotation int: Int) {
	_internalInvariant(int <= 0)
	self = int == 0 ? .equal : .less
	}

	@inlinable @inline(__always)
	static func ==(
	_ lhs: _StringComparisonResult, _ rhs: _StringComparisonResult
	) -> Bool {
	switch (lhs, rhs) {
	case (.equal, .equal): return true
	case (.less, .less): return true
	default: return false
	}
	}
	}

	// Perform a binary comparison of bytes in memory. Return value is negative if
	// less, 0 if equal, positive if greater.
	@_effects(readonly)
	internal func _binaryCompare<UInt8>(
	_ lhs: UnsafeBufferPointer<UInt8>, _ rhs: UnsafeBufferPointer<UInt8>
	) -> Int {
	var cmp = Int(truncatingIfNeeded:
	_swift_stdlib_memcmp(
	lhs.baseAddress._unsafelyUnwrappedUnchecked,
	rhs.baseAddress._unsafelyUnwrappedUnchecked,
	Swift.min(lhs.count, rhs.count)))
	if cmp == 0 {
	cmp = lhs.count &- rhs.count
	}
	return cmp
	}

	// Double dispatch functions
	extension _StringGutsSlice {
	@_effects(readonly)
	internal func compare(
	with other: _StringGutsSlice, expecting: _StringComparisonResult
	) -> Bool {
	if _fastPath(self.isFastUTF8 && other.isFastUTF8) {
	Builtin.onFastPath() // aggressively inline / optimize
	let isEqual = self.withFastUTF8 { utf8Self in
	return other.withFastUTF8 { utf8Other in
	return 0 == _binaryCompare(utf8Self, utf8Other)
	}
	}
	if isEqual { return expecting == .equal }
	}

	return _slowCompare(with: other, expecting: expecting)
	}

	@inline(never) // opaque slow-path
	@_effects(readonly)
	internal func _slowCompare(
	with other: _StringGutsSlice,
	expecting: _StringComparisonResult
	) -> Bool {
	var left_output = _FixedArray16<UInt8>(allZeros: ())
	var left_icuInput = _FixedArray16<UInt16>(allZeros: ())
	var left_icuOutput = _FixedArray16<UInt16>(allZeros: ())
	var right_output = _FixedArray16<UInt8>(allZeros: ())
	var right_icuInput = _FixedArray16<UInt16>(allZeros: ())
	var right_icuOutput = _FixedArray16<UInt16>(allZeros: ())
	if _fastPath(self.isFastUTF8 && other.isFastUTF8) {
	return self.withFastUTF8 { leftUTF8 in
	other.withFastUTF8 { rightUTF8 in
	let leftStartIndex = String.Index(_encodedOffset: 0)
	let rightStartIndex = String.Index(_encodedOffset: 0)
	let leftEndIndex = String.Index(_encodedOffset: leftUTF8.count)
	let rightEndIndex = String.Index(_encodedOffset: rightUTF8.count)
	return _normalizedCompareImpl(
	left_outputBuffer: _castOutputBuffer(&left_output),
	left_icuInputBuffer: _castOutputBuffer(&left_icuInput),
	left_icuOutputBuffer: _castOutputBuffer(&left_icuOutput),
	right_outputBuffer: _castOutputBuffer(&right_output),
	right_icuInputBuffer: _castOutputBuffer(&right_icuInput),
	right_icuOutputBuffer: _castOutputBuffer(&right_icuOutput),
	left_range: leftStartIndex..<leftEndIndex,
	right_range: rightStartIndex..<rightEndIndex,
	expecting: expecting,
	normalizeLeft: { readIndex, outputBuffer, icuInputBuffer, icuOutputBuffer in
	_fastNormalize(
	readIndex: readIndex,
	sourceBuffer: leftUTF8,
	outputBuffer: &outputBuffer,
	icuInputBuffer: &icuInputBuffer,
	icuOutputBuffer: &icuOutputBuffer)
	},
	normalizeRight: { readIndex, outputBuffer, icuInputBuffer, icuOutputBuffer in
	_fastNormalize(
	readIndex: readIndex,
	sourceBuffer: rightUTF8,
	outputBuffer: &outputBuffer,
	icuInputBuffer: &icuInputBuffer,
	icuOutputBuffer: &icuOutputBuffer)
	})
	}
	}
	} else {
	return _normalizedCompareImpl(
	left_outputBuffer: _castOutputBuffer(&left_output),
	left_icuInputBuffer: _castOutputBuffer(&left_icuInput),
	left_icuOutputBuffer: _castOutputBuffer(&left_icuOutput),
	right_outputBuffer: _castOutputBuffer(&right_output),
	right_icuInputBuffer: _castOutputBuffer(&right_icuInput),
	right_icuOutputBuffer: _castOutputBuffer(&right_icuOutput),
	left_range: range,
	right_range: other.range,
	expecting: expecting,
	normalizeLeft: { readIndex, outputBuffer, icuInputBuffer, icuOutputBuffer in
	_foreignNormalize(
	readIndex: readIndex,
	endIndex: range.upperBound,
	guts: _guts,
	outputBuffer: &outputBuffer,
	icuInputBuffer: &icuInputBuffer,
	icuOutputBuffer: &icuOutputBuffer)
	},
	normalizeRight: { readIndex, outputBuffer, icuInputBuffer, icuOutputBuffer in
	_foreignNormalize(
	readIndex: readIndex,
	endIndex: other.range.upperBound,
	guts: other._guts,
	outputBuffer: &outputBuffer,
	icuInputBuffer: &icuInputBuffer,
	icuOutputBuffer: &icuOutputBuffer)
	})
	}
	}


	@inline(__always) //Avoid unecessary overhead from the closures.
	internal func _normalizedCompareImpl(
	left_outputBuffer: UnsafeMutableBufferPointer<UInt8>,
	left_icuInputBuffer: UnsafeMutableBufferPointer<UInt16>,
	left_icuOutputBuffer: UnsafeMutableBufferPointer<UInt16>,
	right_outputBuffer: UnsafeMutableBufferPointer<UInt8>,
	right_icuInputBuffer: UnsafeMutableBufferPointer<UInt16>,
	right_icuOutputBuffer: UnsafeMutableBufferPointer<UInt16>,
	left_range: Range<String.Index>,
	right_range: Range<String.Index>,
	expecting: _StringComparisonResult,
	normalizeLeft: (
	_ readIndex: String.Index,
	_ outputBuffer: inout UnsafeMutableBufferPointer<UInt8>,
	_ icuInputBuffer: inout UnsafeMutableBufferPointer<UInt16>,
	_ icuOutputBuffer: inout UnsafeMutableBufferPointer<UInt16>) -> NormalizationResult,
	normalizeRight: (
	_ readIndex: String.Index,
	_ outputBuffer: inout UnsafeMutableBufferPointer<UInt8>,
	_ icuInputBuffer: inout UnsafeMutableBufferPointer<UInt16>,
	_ icuOutputBuffer: inout UnsafeMutableBufferPointer<UInt16>) -> NormalizationResult
	) -> Bool {
	var left_outputBuffer = left_outputBuffer
	var left_icuInputBuffer = left_icuInputBuffer
	var left_icuOutputBuffer = left_icuOutputBuffer
	var right_outputBuffer = right_outputBuffer
	var right_icuInputBuffer = right_icuInputBuffer
	var right_icuOutputBuffer = right_icuOutputBuffer

	var leftNextReadPosition = left_range.lowerBound
	var rightNextReadPosition = right_range.lowerBound
	var leftOutputBufferIndex = 0
	var rightOutputBufferIndex = 0
	var leftOutputBufferCount = 0
	var rightOutputBufferCount = 0
	let leftEndIndex = left_range.upperBound
	let rightEndIndex = right_range.upperBound

	var hasLeftBufferOwnership = false
	var hasRightBufferOwnership = false

	if left_range.isEmpty && right_range.isEmpty {
	return expecting == .equal
	}
	if left_range.isEmpty {
	return expecting == .less
	}
	if right_range.isEmpty {
	return false
	}

	defer {
	if hasLeftBufferOwnership {
	left_outputBuffer.deallocate()
	left_icuInputBuffer.deallocate()
	left_icuOutputBuffer.deallocate()
	}
	if hasRightBufferOwnership {
	right_outputBuffer.deallocate()
	right_icuInputBuffer.deallocate()
	right_icuOutputBuffer.deallocate()
	}
	}

	repeat {
	if leftOutputBufferIndex == leftOutputBufferCount {
	let result = normalizeLeft(
	leftNextReadPosition,
	&left_outputBuffer,
	&left_icuInputBuffer,
	&left_icuOutputBuffer)
	_internalInvariant(result.nextReadPosition != leftNextReadPosition)
	leftOutputBufferCount = result.amountFilled
	leftOutputBufferIndex = 0
	leftNextReadPosition = result.nextReadPosition
	if result.allocatedBuffers {
	_internalInvariant(!hasLeftBufferOwnership)
	hasLeftBufferOwnership = true
	}
	}
	if rightOutputBufferIndex == rightOutputBufferCount {
	let result = normalizeRight(
	rightNextReadPosition,
	&right_outputBuffer,
	&right_icuInputBuffer,
	&right_icuOutputBuffer)
	_internalInvariant(result.nextReadPosition != rightNextReadPosition)
	rightOutputBufferCount = result.amountFilled
	rightOutputBufferIndex = 0
	rightNextReadPosition = result.nextReadPosition
	if result.allocatedBuffers {
	_internalInvariant(!hasRightBufferOwnership)
	hasRightBufferOwnership = true
	}
	}
	while leftOutputBufferIndex < leftOutputBufferCount && rightOutputBufferIndex < rightOutputBufferCount {
	let leftCU = left_outputBuffer[leftOutputBufferIndex]
	let rightCU = right_outputBuffer[rightOutputBufferIndex]
	if leftCU == rightCU {
	leftOutputBufferIndex += 1
	rightOutputBufferIndex += 1
	continue
	} else if leftCU < rightCU {
	return expecting == .less
	} else {
	return false
	}
	}
	} while (leftNextReadPosition < leftEndIndex
	\|\| leftOutputBufferIndex < leftOutputBufferCount)
	&& (rightNextReadPosition < rightEndIndex
	\|\| rightOutputBufferIndex < rightOutputBufferCount)


	//At least one of them ran out of code units, whichever it was is the "smaller" string
	if leftNextReadPosition < leftEndIndex
	\|\| leftOutputBufferIndex < leftOutputBufferCount {
	return false
	} else if rightNextReadPosition < rightEndIndex
	\|\| rightOutputBufferIndex < rightOutputBufferCount {
	return expecting == .less
	} else {
	//They both ran out
	return expecting == .equal
	}
	}
	}