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

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

 // MARK: Diff application to RangeReplaceableCollection

 @available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
 extension CollectionDifference {
   fileprivate func _fastEnumeratedApply(
     _ consume: (Change) throws -> Void
   ) rethrows {
     let totalRemoves = removals.count
     let totalInserts = insertions.count
     var enumeratedRemoves = 0
     var enumeratedInserts = 0

     while enumeratedRemoves < totalRemoves || enumeratedInserts < totalInserts {
       let change: Change
       if enumeratedRemoves < removals.count && enumeratedInserts < insertions.count {
         let removeOffset = removals[enumeratedRemoves]._offset
         let insertOffset = insertions[enumeratedInserts]._offset
         if removeOffset - enumeratedRemoves <= insertOffset - enumeratedInserts {
           change = removals[enumeratedRemoves]
         } else {
           change = insertions[enumeratedInserts]
         }
       } else if enumeratedRemoves < totalRemoves {
         change = removals[enumeratedRemoves]
       } else if enumeratedInserts < totalInserts {
         change = insertions[enumeratedInserts]
       } else {
         // Not reached, loop should have exited.
         preconditionFailure()
       }

       try consume(change)

       switch change {
       case .remove(_, _, _):
         enumeratedRemoves += 1
       case .insert(_, _, _):
         enumeratedInserts += 1
       }
     }
   }
 }

 // Error type allows the use of throw to unroll state on application failure
 private enum _ApplicationError : Error { case failed }

 extension RangeReplaceableCollection {
   /// Applies the given difference to this collection.
   ///
   /// - Parameter difference: The difference to be applied.
   ///
   /// - Returns: An instance representing the state of the receiver with the
   ///   difference applied, or `nil` if the difference is incompatible with
   ///   the receiver's state.
   ///
   /// - Complexity: O(*n* + *c*), where *n* is `self.count` and *c* is the
   ///   number of changes contained by the parameter.
   @available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
   public func applying(_ difference: CollectionDifference<Element>) -> Self? {

     func append(
       into target: inout Self,
       contentsOf source: Self,
       from index: inout Self.Index, count: Int
     ) throws {
       let start = index
       if !source.formIndex(&index, offsetBy: count, limitedBy: source.endIndex) {
         throw _ApplicationError.failed
       }
       target.append(contentsOf: source[start..<index])
     }

     var result = Self()
     do {
       var enumeratedRemoves = 0
       var enumeratedInserts = 0
       var enumeratedOriginals = 0
       var currentIndex = self.startIndex
       try difference._fastEnumeratedApply { change in
         switch change {
         case .remove(offset: let offset, element: _, associatedWith: _):
           let origCount = offset - enumeratedOriginals
           try append(into: &result, contentsOf: self, from: &currentIndex, count: origCount)
           if currentIndex == self.endIndex {
             // Removing nonexistent element off the end of the collection
             throw _ApplicationError.failed
           }
           enumeratedOriginals += origCount + 1 // Removal consumes an original element
           currentIndex = self.index(after: currentIndex)
           enumeratedRemoves += 1
         case .insert(offset: let offset, element: let element, associatedWith: _):
           let origCount = (offset + enumeratedRemoves - enumeratedInserts) - enumeratedOriginals
           try append(into: &result, contentsOf: self, from: &currentIndex, count: origCount)
           result.append(element)
           enumeratedOriginals += origCount
           enumeratedInserts += 1
         }
         _internalInvariant(enumeratedOriginals <= self.count)
       }
       if currentIndex < self.endIndex {
         result.append(contentsOf: self[currentIndex...])
       }
       _internalInvariant(result.count == self.count + enumeratedInserts - enumeratedRemoves)
     } catch {
       return nil
     }

     return result
   }
 }

 // MARK: Definition of API

 extension BidirectionalCollection {
   /// Returns the difference needed to produce this collection's ordered
   /// elements from the given collection, using the given predicate as an
   /// equivalence test.
   ///
   /// This function does not infer element moves. If you need to infer moves,
   /// call the `inferringMoves()` method on the resulting difference.
   ///
   /// - Parameters:
   ///   - other: The base state.
   ///   - areEquivalent: A closure that returns a Boolean value indicating
   ///     whether two elements are equivalent.
   ///
   /// - Returns: The difference needed to produce the reciever's state from
   ///   the parameter's state.
   ///
   /// - Complexity: Worst case performance is O(*n* * *m*), where *n* is the
   ///   count of this collection and *m* is `other.count`. You can expect
   ///   faster execution when the collections share many common elements.
   @available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
   public func difference<C: BidirectionalCollection>(
     from other: C,
     by areEquivalent: (C.Element, Element) -> Bool
   ) -> CollectionDifference<Element>
   where C.Element == Self.Element {
     return _myers(from: other, to: self, using: areEquivalent)
   }
 }

 extension BidirectionalCollection where Element: Equatable {
   /// Returns the difference needed to produce this collection's ordered
   /// elements from the given collection.
   ///
   /// This function does not infer element moves. If you need to infer moves,
   /// call the `inferringMoves()` method on the resulting difference.
   ///
   /// - Parameters:
   ///   - other: The base state.
   ///
   /// - Returns: The difference needed to produce this collection's ordered
   ///   elements from the given collection.
   ///
   /// - Complexity: Worst case performance is O(*n* * *m*), where *n* is the
   ///   count of this collection and *m* is `other.count`. You can expect
   ///   faster execution when the collections share many common elements, or
   ///   if `Element` conforms to `Hashable`.
   @available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
   public func difference<C: BidirectionalCollection>(
     from other: C
   ) -> CollectionDifference<Element> where C.Element == Self.Element {
     return difference(from: other, by: ==)
   }
 }

 // MARK: Internal implementation

 // _V is a rudimentary type made to represent the rows of the triangular matrix
 // type used by the Myer's algorithm.
 //
 // This type is basically an array that only supports indexes in the set
 // `stride(from: -d, through: d, by: 2)` where `d` is the depth of this row in
 // the matrix `d` is always known at allocation-time, and is used to preallocate
 // the structure.
 private struct _V {

   private var a: [Int]
 #if INTERNAL_CHECKS_ENABLED
   private let isOdd: Bool
 #endif

   // The way negative indexes are implemented is by interleaving them in the empty slots between the valid positive indexes
   @inline(__always) private static func transform(_ index: Int) -> Int {
     // -3, -1, 1, 3 -> 3, 1, 0, 2 -> 0...3
     // -2, 0, 2 -> 2, 0, 1 -> 0...2
     return (index <= 0 ? -index : index &- 1)
   }

   init(maxIndex largest: Int) {
 #if INTERNAL_CHECKS_ENABLED
     _internalInvariant(largest >= 0)
     isOdd = largest % 2 == 1
 #endif
     a = [Int](repeating: 0, count: largest + 1)
   }

   subscript(index: Int) -> Int {
     get {
 #if INTERNAL_CHECKS_ENABLED
       _internalInvariant(isOdd == (index % 2 != 0))
 #endif
       return a[_V.transform(index)]
     }
     set(newValue) {
 #if INTERNAL_CHECKS_ENABLED
       _internalInvariant(isOdd == (index % 2 != 0))
 #endif
       a[_V.transform(index)] = newValue
     }
   }
 }

 @available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
 private func _myers<C,D>(
   from old: C, to new: D,
   using cmp: (C.Element, D.Element) -> Bool
 ) -> CollectionDifference<C.Element>
   where
     C: BidirectionalCollection,
     D: BidirectionalCollection,
     C.Element == D.Element
 {

   // Core implementation of the algorithm described at http://www.xmailserver.org/diff2.pdf
   // Variable names match those used in the paper as closely as possible
   func _descent(from a: UnsafeBufferPointer<C.Element>, to b: UnsafeBufferPointer<D.Element>) -> [_V] {
     let n = a.count
     let m = b.count
     let max = n + m

     var result = [_V]()
     var v = _V(maxIndex: 1)
     v[1] = 0

     var x = 0
     var y = 0
     iterator: for d in 0...max {
       let prev_v = v
       result.append(v)
       v = _V(maxIndex: d)

       // The code in this loop is _very_ hot—the loop bounds increases in terms
       // of the iterator of the outer loop!
       for k in stride(from: -d, through: d, by: 2) {
         if k == -d {
           x = prev_v[k &+ 1]
         } else {
           let km = prev_v[k &- 1]

           if k != d {
             let kp = prev_v[k &+ 1]
             if km < kp {
               x = kp
             } else {
               x = km &+ 1
             }
           } else {
             x = km &+ 1
           }
         }
         y = x &- k

         while x < n && y < m {
           if !cmp(a[x], b[y]) {
             break;
           }
           x &+= 1
           y &+= 1
         }

         v[k] = x

         if x >= n && y >= m {
           break iterator
         }
       }
       if x >= n && y >= m {
         break
       }
     }

     _internalInvariant(x >= n && y >= m)

     return result
   }

   // Backtrack through the trace generated by the Myers descent to produce the changes that make up the diff
   func _formChanges(
     from a: UnsafeBufferPointer<C.Element>,
     to b: UnsafeBufferPointer<C.Element>,
     using trace: [_V]
   ) -> [CollectionDifference<C.Element>.Change] {
     var changes = [CollectionDifference<C.Element>.Change]()
     changes.reserveCapacity(trace.count)

     var x = a.count
     var y = b.count
     for d in stride(from: trace.count &- 1, to: 0, by: -1) {
       let v = trace[d]
       let k = x &- y
       let prev_k = (k == -d || (k != d && v[k &- 1] < v[k &+ 1])) ? k &+ 1 : k &- 1
       let prev_x = v[prev_k]
       let prev_y = prev_x &- prev_k

       while x > prev_x && y > prev_y {
         // No change at this position.
         x &-= 1
         y &-= 1
       }

       _internalInvariant((x == prev_x && y > prev_y) || (y == prev_y && x > prev_x))
       if y != prev_y {
         changes.append(.insert(offset: prev_y, element: b[prev_y], associatedWith: nil))
       } else {
         changes.append(.remove(offset: prev_x, element: a[prev_x], associatedWith: nil))
       }

       x = prev_x
       y = prev_y
     }

     return changes
   }

   /* Splatting the collections into contiguous storage has two advantages:
    *
    *   1) Subscript access is much faster
    *   2) Subscript index becomes Int, matching the iterator types in the algorithm
    *
    * Combined, these effects dramatically improves performance when
    * collections differ significantly, without unduly degrading runtime when
    * the parameters are very similar.
    *
    * In terms of memory use, the linear cost of creating a ContiguousArray (when
    * necessary) is significantly less than the worst-case n² memory use of the
    * descent algorithm.
    */
   func _withContiguousStorage<C: Collection, R>(
     for values: C,
     _ body: (UnsafeBufferPointer<C.Element>) throws -> R
   ) rethrows -> R {
     if let result = try values.withContiguousStorageIfAvailable(body) { return result }
     let array = ContiguousArray(values)
     return try array.withUnsafeBufferPointer(body)
   }

   return _withContiguousStorage(for: old) { a in
     return _withContiguousStorage(for: new) { b in
       return CollectionDifference(_formChanges(from: a, to: b, using:_descent(from: a, to: b)))!
     }
   }
 }
	//===----------------------------------------------------------------------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2015 - 2019 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//

	// MARK: Diff application to RangeReplaceableCollection

	@available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
	extension CollectionDifference {
	fileprivate func _fastEnumeratedApply(
	_ consume: (Change) throws -> Void
	) rethrows {
	let totalRemoves = removals.count
	let totalInserts = insertions.count
	var enumeratedRemoves = 0
	var enumeratedInserts = 0

	while enumeratedRemoves < totalRemoves \|\| enumeratedInserts < totalInserts {
	let change: Change
	if enumeratedRemoves < removals.count && enumeratedInserts < insertions.count {
	let removeOffset = removals[enumeratedRemoves]._offset
	let insertOffset = insertions[enumeratedInserts]._offset
	if removeOffset - enumeratedRemoves <= insertOffset - enumeratedInserts {
	change = removals[enumeratedRemoves]
	} else {
	change = insertions[enumeratedInserts]
	}
	} else if enumeratedRemoves < totalRemoves {
	change = removals[enumeratedRemoves]
	} else if enumeratedInserts < totalInserts {
	change = insertions[enumeratedInserts]
	} else {
	// Not reached, loop should have exited.
	preconditionFailure()
	}

	try consume(change)

	switch change {
	case .remove(_, _, _):
	enumeratedRemoves += 1
	case .insert(_, _, _):
	enumeratedInserts += 1
	}
	}
	}
	}

	// Error type allows the use of throw to unroll state on application failure
	private enum _ApplicationError : Error { case failed }

	extension RangeReplaceableCollection {
	/// Applies the given difference to this collection.
	///
	/// - Parameter difference: The difference to be applied.
	///
	/// - Returns: An instance representing the state of the receiver with the
	/// difference applied, or `nil` if the difference is incompatible with
	/// the receiver's state.
	///
	/// - Complexity: O(n + c), where n is `self.count` and c is the
	/// number of changes contained by the parameter.
	@available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
	public func applying(_ difference: CollectionDifference<Element>) -> Self? {

	func append(
	into target: inout Self,
	contentsOf source: Self,
	from index: inout Self.Index, count: Int
	) throws {
	let start = index
	if !source.formIndex(&index, offsetBy: count, limitedBy: source.endIndex) {
	throw _ApplicationError.failed
	}
	target.append(contentsOf: source[start..<index])
	}

	var result = Self()
	do {
	var enumeratedRemoves = 0
	var enumeratedInserts = 0
	var enumeratedOriginals = 0
	var currentIndex = self.startIndex
	try difference._fastEnumeratedApply { change in
	switch change {
	case .remove(offset: let offset, element: _, associatedWith: _):
	let origCount = offset - enumeratedOriginals
	try append(into: &result, contentsOf: self, from: &currentIndex, count: origCount)
	if currentIndex == self.endIndex {
	// Removing nonexistent element off the end of the collection
	throw _ApplicationError.failed
	}
	enumeratedOriginals += origCount + 1 // Removal consumes an original element
	currentIndex = self.index(after: currentIndex)
	enumeratedRemoves += 1
	case .insert(offset: let offset, element: let element, associatedWith: _):
	let origCount = (offset + enumeratedRemoves - enumeratedInserts) - enumeratedOriginals
	try append(into: &result, contentsOf: self, from: &currentIndex, count: origCount)
	result.append(element)
	enumeratedOriginals += origCount
	enumeratedInserts += 1
	}
	_internalInvariant(enumeratedOriginals <= self.count)
	}
	if currentIndex < self.endIndex {
	result.append(contentsOf: self[currentIndex...])
	}
	_internalInvariant(result.count == self.count + enumeratedInserts - enumeratedRemoves)
	} catch {
	return nil
	}

	return result
	}
	}

	// MARK: Definition of API

	extension BidirectionalCollection {
	/// Returns the difference needed to produce this collection's ordered
	/// elements from the given collection, using the given predicate as an
	/// equivalence test.
	///
	/// This function does not infer element moves. If you need to infer moves,
	/// call the `inferringMoves()` method on the resulting difference.
	///
	/// - Parameters:
	/// - other: The base state.
	/// - areEquivalent: A closure that returns a Boolean value indicating
	/// whether two elements are equivalent.
	///
	/// - Returns: The difference needed to produce the reciever's state from
	/// the parameter's state.
	///
	/// - Complexity: Worst case performance is O(n * m), where n is the
	/// count of this collection and m is `other.count`. You can expect
	/// faster execution when the collections share many common elements.
	@available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
	public func difference<C: BidirectionalCollection>(
	from other: C,
	by areEquivalent: (C.Element, Element) -> Bool
	) -> CollectionDifference<Element>
	where C.Element == Self.Element {
	return _myers(from: other, to: self, using: areEquivalent)
	}
	}

	extension BidirectionalCollection where Element: Equatable {
	/// Returns the difference needed to produce this collection's ordered
	/// elements from the given collection.
	///
	/// This function does not infer element moves. If you need to infer moves,
	/// call the `inferringMoves()` method on the resulting difference.
	///
	/// - Parameters:
	/// - other: The base state.
	///
	/// - Returns: The difference needed to produce this collection's ordered
	/// elements from the given collection.
	///
	/// - Complexity: Worst case performance is O(n * m), where n is the
	/// count of this collection and m is `other.count`. You can expect
	/// faster execution when the collections share many common elements, or
	/// if `Element` conforms to `Hashable`.
	@available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
	public func difference<C: BidirectionalCollection>(
	from other: C
	) -> CollectionDifference<Element> where C.Element == Self.Element {
	return difference(from: other, by: ==)
	}
	}

	// MARK: Internal implementation

	// _V is a rudimentary type made to represent the rows of the triangular matrix
	// type used by the Myer's algorithm.
	//
	// This type is basically an array that only supports indexes in the set
	// `stride(from: -d, through: d, by: 2)` where `d` is the depth of this row in
	// the matrix `d` is always known at allocation-time, and is used to preallocate
	// the structure.
	private struct _V {

	private var a: [Int]
	#if INTERNAL_CHECKS_ENABLED
	private let isOdd: Bool
	#endif

	// The way negative indexes are implemented is by interleaving them in the empty slots between the valid positive indexes
	@inline(__always) private static func transform(_ index: Int) -> Int {
	// -3, -1, 1, 3 -> 3, 1, 0, 2 -> 0...3
	// -2, 0, 2 -> 2, 0, 1 -> 0...2
	return (index <= 0 ? -index : index &- 1)
	}

	init(maxIndex largest: Int) {
	#if INTERNAL_CHECKS_ENABLED
	_internalInvariant(largest >= 0)
	isOdd = largest % 2 == 1
	#endif
	a = [Int](repeating: 0, count: largest + 1)
	}

	subscript(index: Int) -> Int {
	get {
	#if INTERNAL_CHECKS_ENABLED
	_internalInvariant(isOdd == (index % 2 != 0))
	#endif
	return a[_V.transform(index)]
	}
	set(newValue) {
	#if INTERNAL_CHECKS_ENABLED
	_internalInvariant(isOdd == (index % 2 != 0))
	#endif
	a[_V.transform(index)] = newValue
	}
	}
	}

	@available(macOS 10.15, iOS 13, tvOS 13, watchOS 6, *)
	private func _myers<C,D>(
	from old: C, to new: D,
	using cmp: (C.Element, D.Element) -> Bool
	) -> CollectionDifference<C.Element>
	where
	C: BidirectionalCollection,
	D: BidirectionalCollection,
	C.Element == D.Element
	{

	// Core implementation of the algorithm described at http://www.xmailserver.org/diff2.pdf
	// Variable names match those used in the paper as closely as possible
	func _descent(from a: UnsafeBufferPointer<C.Element>, to b: UnsafeBufferPointer<D.Element>) -> [_V] {
	let n = a.count
	let m = b.count
	let max = n + m

	var result = [_V]()
	var v = _V(maxIndex: 1)
	v[1] = 0

	var x = 0
	var y = 0
	iterator: for d in 0...max {
	let prev_v = v
	result.append(v)
	v = _V(maxIndex: d)

	// The code in this loop is _very_ hot—the loop bounds increases in terms
	// of the iterator of the outer loop!
	for k in stride(from: -d, through: d, by: 2) {
	if k == -d {
	x = prev_v[k &+ 1]
	} else {
	let km = prev_v[k &- 1]

	if k != d {
	let kp = prev_v[k &+ 1]
	if km < kp {
	x = kp
	} else {
	x = km &+ 1
	}
	} else {
	x = km &+ 1
	}
	}
	y = x &- k

	while x < n && y < m {
	if !cmp(a[x], b[y]) {
	break;
	}
	x &+= 1
	y &+= 1
	}

	v[k] = x

	if x >= n && y >= m {
	break iterator
	}
	}
	if x >= n && y >= m {
	break
	}
	}

	_internalInvariant(x >= n && y >= m)

	return result
	}

	// Backtrack through the trace generated by the Myers descent to produce the changes that make up the diff
	func _formChanges(
	from a: UnsafeBufferPointer<C.Element>,
	to b: UnsafeBufferPointer<C.Element>,
	using trace: [_V]
	) -> [CollectionDifference<C.Element>.Change] {
	var changes = [CollectionDifference<C.Element>.Change]()
	changes.reserveCapacity(trace.count)

	var x = a.count
	var y = b.count
	for d in stride(from: trace.count &- 1, to: 0, by: -1) {
	let v = trace[d]
	let k = x &- y
	let prev_k = (k == -d \|\| (k != d && v[k &- 1] < v[k &+ 1])) ? k &+ 1 : k &- 1
	let prev_x = v[prev_k]
	let prev_y = prev_x &- prev_k

	while x > prev_x && y > prev_y {
	// No change at this position.
	x &-= 1
	y &-= 1
	}

	_internalInvariant((x == prev_x && y > prev_y) \|\| (y == prev_y && x > prev_x))
	if y != prev_y {
	changes.append(.insert(offset: prev_y, element: b[prev_y], associatedWith: nil))
	} else {
	changes.append(.remove(offset: prev_x, element: a[prev_x], associatedWith: nil))
	}

	x = prev_x
	y = prev_y
	}

	return changes
	}

	/* Splatting the collections into contiguous storage has two advantages:
	*
	* 1) Subscript access is much faster
	* 2) Subscript index becomes Int, matching the iterator types in the algorithm
	*
	* Combined, these effects dramatically improves performance when
	* collections differ significantly, without unduly degrading runtime when
	* the parameters are very similar.
	*
	* In terms of memory use, the linear cost of creating a ContiguousArray (when
	* necessary) is significantly less than the worst-case n² memory use of the
	* descent algorithm.
	*/
	func _withContiguousStorage<C: Collection, R>(
	for values: C,
	_ body: (UnsafeBufferPointer<C.Element>) throws -> R
	) rethrows -> R {
	if let result = try values.withContiguousStorageIfAvailable(body) { return result }
	let array = ContiguousArray(values)
	return try array.withUnsafeBufferPointer(body)
	}

	return _withContiguousStorage(for: old) { a in
	return _withContiguousStorage(for: new) { b in
	return CollectionDifference(_formChanges(from: a, to: b, using:_descent(from: a, to: b)))!
	}
	}
	}