stdlib/public/core/Integers.swift.gyb

//===--- Integers.swift.gyb -----------------------------------*- swift -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 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
//
//===----------------------------------------------------------------------===//
 %{
#
# Utility code for later in this template
#

from string import maketrans, capitalize

# Number of bits in the Builtin.Word type
word_bits = int(CMAKE_SIZEOF_VOID_P) * 8

# Number of bits in integer literals.
builtinIntLiteralBits = 2048
IntLiteral = 'Int%s' % builtinIntLiteralBits

class struct(object):
  def __init__(self, **kw):
    self.__dict__ = kw
  def __repr__(self):
    return 'struct(%r)' % self.__dict__

binaryArithmetic = {
  'Arithmetic' : [
    struct(operator='+', name='adding',      mutatingName='add',      firstArg='_',  llvmName='add', kind='+'),
    struct(operator='-', name='subtracting', mutatingName='subtract', firstArg='_',  llvmName='sub', kind='-'),
    struct(operator='*', name='multiplied',  mutatingName='multiply', firstArg='by', llvmName='mul', kind='*'),
    struct(operator='/', name='divided',     mutatingName='divide',   firstArg='by', llvmName='div', kind='/'),
  ],
  'BinaryInteger' : [
    struct(operator='%', name='remainder',   mutatingName='formRemainder', firstArg='dividingBy', llvmName='rem', kind='/'),
  ],
}

binaryBitwise = [
    struct(operator='&', name='bitwiseAnd', llvmName='and'),
    struct(operator='|', name='bitwiseOr', llvmName='or'),
    struct(operator='^', name='bitwiseXor', llvmName='xor'),
]

maskingShifts = [
    struct(
      operator='&>>', nonMaskingOperator='>>', description='right shift',
      name='maskingShiftRight', llvmName=lambda s:['lshr','ashr'][s]),
    struct(
      operator='&<<', nonMaskingOperator='<<', description='left shift',
      name='maskingShiftLeft', llvmName=lambda _: 'shl'),
]
}%

infix operator &<< : BitwiseShiftPrecedence
infix operator &<<= : AssignmentPrecedence
infix operator &>> : BitwiseShiftPrecedence
infix operator &>>= : AssignmentPrecedence

//===----------------------------------------------------------------------===//
//===--- Bits for the Stdlib ----------------------------------------------===//
//===----------------------------------------------------------------------===//


// FIXME(integers): This should go in the stdlib separately, probably.
extension ExpressibleByIntegerLiteral
  where Self : _ExpressibleByBuiltinIntegerLiteral {
  /// Create an instance initialized to `value`.
  @_transparent
  public init(integerLiteral value: Self) {
    self = value
  }
}

//===----------------------------------------------------------------------===//
//===--- Arithmetic -------------------------------------------------------===//
//===----------------------------------------------------------------------===//

/// Declares methods backing binary arithmetic operators--such as `+`, `-` and
/// `*`--and their mutating counterparts.
///
/// It provides a suitable basis for arithmetic on scalars such as integers and
/// floating point numbers.
///
/// Both mutating and non-mutating operations are declared in the protocol,
/// however only the mutating ones are required, as default implementations of
/// the non-mutating ones are provided by a protocol extension.
///
/// The `Magnitude` associated type is able to hold the absolute value of any
/// possible value of `Self`. Concrete types do not have to provide a typealias
/// for it, as it can be inferred from the `magnitude` property. This property
/// can be useful in operations that are simpler to implement in terms of
/// unsigned values, for example, printing a value of an integer, which is just
/// printing a '-' character in front of an absolute value.
///
/// Please note that for ordinary work, the `magnitude` property **should not**
/// be preferred to the `abs(_)` function, whose return value is of the same
/// type as its argument.
public protocol Arithmetic : Equatable, ExpressibleByIntegerLiteral {
  // FIXME(integers): implement
  //init?<T : BinaryInteger>(exactly source: T)

  // FIXME(ABI)#44 (Recursive Protocol Constraints): should be just Arithmetic
  associatedtype Magnitude : Equatable, ExpressibleByIntegerLiteral

  var magnitude: Magnitude { get }


% for x in binaryArithmetic['Arithmetic']:
  // defaulted using an in-place counterpart, but can be used as an
  // optimization hook
  func ${x.name}(${x.firstArg} rhs: Self) -> Self

  // implementation hook
  mutating func ${x.mutatingName}(${x.firstArg} rhs: Self)
% end
}

extension Arithmetic {
  @_transparent
  public init() {
    self = 0
  }
}

% for Protocol in binaryArithmetic:
extension ${Protocol} {
%   for x in binaryArithmetic[Protocol]:
%     callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
  public func ${x.name}(${x.firstArg} rhs: Self) -> Self {
    var lhs = self
    lhs.${x.mutatingName}(${callLabel}rhs)
    return lhs
  }
%   end
}
% end

public protocol SignedArithmetic : Arithmetic {
  func negated() -> Self
  mutating func negate()
}

extension SignedArithmetic {
  public func negated() -> Self {
    return Self().subtracting(self)
  }
  public mutating func negate() {
    self = negated()
  }
}

//===----------------------------------------------------------------------===//
//===--- Arithmetic operators ---------------------------------------------===//
//===----------------------------------------------------------------------===//

% for Protocol in binaryArithmetic:
%   for x in binaryArithmetic[Protocol]:
%     callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
@_transparent
public func ${x.operator} <T: ${Protocol}>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}(${callLabel}rhs)
}

@_transparent
public func ${x.operator}= <T: ${Protocol}>(lhs: inout T, rhs: T) {
  lhs.${x.mutatingName}(${callLabel}rhs)
}
%   end
% end

@_transparent
public prefix func - <T: SignedArithmetic>(x: T) -> T {
  return x.negated()
}

//===----------------------------------------------------------------------===//
//===--- BinaryInteger ----------------------------------------------------===//
//===----------------------------------------------------------------------===//

public protocol BinaryInteger :
  Comparable, Arithmetic, CustomStringConvertible {

  static var isSigned: Bool { get }

  // Dispatching through these puts less stress on the user reading
  // the interface and error messages (and on the type checker) than
  // does having many operator overloads.
  func isEqual(to rhs: Self) -> Bool
  func isLess(than rhs: Self) -> Bool

  init?<T : FloatingPoint>(exactly source: T)

  init<T : FloatingPoint>(_ source: T)

  init<T : BinaryInteger>(_ source: T)

  init<T : BinaryInteger>(extendingOrTruncating source: T)

  init<T : BinaryInteger>(clamping source: T)

  func word(at n: Int) -> UInt

  var bitWidth : Int { get }

  var minimumSignedRepresentationBitWidth: Int { get }

% for x in binaryArithmetic['BinaryInteger']:
  // defaulted using an in-place counterpart, but can be used as an
  // optimization hook
  func ${x.name}(${x.firstArg} rhs: Self) -> Self

  // implementation hook
  mutating func ${x.mutatingName}(${x.firstArg} rhs: Self)
% end

  func quotientAndRemainder(dividingBy rhs: Self) -> (Self, Self)

  /// Returns `-1` if the value of `self` is negative, `1` if it's positive,
  /// `0` otherwise.
  func signum() -> Self
}

extension BinaryInteger {
  public init?<T : FloatingPoint>(exactly source: T) {
    // FIXME(integers): implement
    fatalError()
    return nil
  }

  public init<T : FloatingPoint>(_ source: T) {
    // FIXME(integers): implement
    fatalError()
  }

  public func signum() -> Self {
    // FIXME(integers): implement
    fatalError()
  }

  public var countRepresentedWords: Int {
    return (self.bitWidth + ${word_bits} - 1) / ${word_bits}
  }

  public func quotientAndRemainder(dividingBy rhs: Self) -> (Self, Self) {
    return (self.divided(by: rhs), self.remainder(dividingBy: rhs))
  }
}

//===----------------------------------------------------------------------===//
//===--- Homogeneous comparison -------------------------------------------===//
//===----------------------------------------------------------------------===//

@_transparent
public func == <T : BinaryInteger>(lhs: T, rhs: T) -> Bool {
  return lhs.isEqual(to: rhs)
}

@_transparent
public func < <T : BinaryInteger>(lhs: T, rhs: T) -> Bool {
  return lhs.isLess(than: rhs)
}

//===----------------------------------------------------------------------===//
//===--- Heterogeneous comparison -----------------------------------------===//
//===----------------------------------------------------------------------===//

@_transparent
public func == <T : BinaryInteger, U : BinaryInteger>(lhs: T, rhs: U) -> Bool {
  return (lhs > 0) == (rhs > 0)
    && T(extendingOrTruncating: rhs) == lhs
    && U(extendingOrTruncating: lhs) == rhs
}

@_transparent
public func != <T : BinaryInteger, U : BinaryInteger>(lhs:T, rhs: U) -> Bool {
  return !(lhs == rhs)
}

@_transparent
public func < <T : BinaryInteger, U : BinaryInteger>(lhs: T, rhs: U) -> Bool {
  let lhsSign = lhs < 0 ? -1 : lhs > 0 ? 1 : 0
  let rhsSign = rhs < 0 ? -1 : rhs > 0 ? 1 : 0
  if lhsSign != rhsSign { return lhsSign < rhsSign }

  // if we get here, lhs and rhs have the same sign.  If they're
  // negative, then T and U are both signed types, and one of them can
  // represent values of the other type.  Otherwise, lhs and rhs are
  // positive, and one of T, U may be signed and the other unsigned.
  // In this case, we can conceptually subtract 1 from the bitWidth of
  // any signed type, and either the resulting bitWidths are the same
  // or one can represent every value of the other.

  let rT = T(extendingOrTruncating: rhs)

  // Can we round-trip rhs through T?
  if U(extendingOrTruncating: rT) == rhs {
    return lhs < rT
  }

  return U(extendingOrTruncating: lhs) < rhs
}

@inline(__always)
public func <= <T : BinaryInteger, U : BinaryInteger>(lhs: T, rhs: U) -> Bool {
  return !(rhs < lhs)
}

@inline(__always)
public func >= <T : BinaryInteger, U : BinaryInteger>(lhs: T, rhs: U) -> Bool {
  return !(lhs < rhs)
}

@inline(__always)
public func > <T : BinaryInteger, U : BinaryInteger>(lhs: T, rhs: U) -> Bool {
  return rhs < lhs
}

//===----------------------------------------------------------------------===//
//===--- Ambiguity breakers -----------------------------------------------===//
// These two versions of the operators are not ordered with respect to
// one another:
//
//     <T : Comparable>(T, T) -> Bool
//     <T : BinaryInteger, U : BinaryInteger>(T, U) -> Bool
//
// so we define:
//
//     <T : BinaryInteger>(T, T) -> Bool
//===----------------------------------------------------------------------===//

@_transparent
public func != <T : BinaryInteger>(lhs: T, rhs: T) -> Bool {
  return !(lhs == rhs)
}

@inline(__always)
public func <= <T : BinaryInteger>(lhs: T, rhs: T) -> Bool {
  return !(rhs < lhs)
}

@inline(__always)
public func >= <T : BinaryInteger>(lhs: T, rhs: T) -> Bool {
  return !(lhs < rhs)
}

@inline(__always)
public func > <T : BinaryInteger>(lhs: T, rhs: T) -> Bool {
  return rhs < lhs
}

//===----------------------------------------------------------------------===//
//===--- FixedWidthInteger ------------------------------------------------===//
//===----------------------------------------------------------------------===//

public enum ArithmeticOverflow {
  @_transparent
  public init(_ overflow: Bool) { self = overflow ? .overflow : .none }
  case none, overflow
}

public protocol FixedWidthInteger : BinaryInteger {
  static var bitWidth : Int { get }

  static var max: Self { get }
  static var min: Self { get }

% for x in binaryArithmetic['Arithmetic']:
%{
comment = '''
  /// Return a pair consisting of `self` {} `rhs`,
  /// truncated to fit if necessary, and a flag indicating whether an
  /// arithmetic overflow occurred.'''.format(x.operator) + ('''
  ///
  /// - Precondition: `rhs != 0`''' if x.kind == '/' else '')
}%
${comment}
  func ${x.name}WithOverflow(
    ${x.firstArg} rhs: Self
  ) -> (partialValue: Self, overflow: ArithmeticOverflow)
% end

% for x in binaryBitwise + maskingShifts:
  func ${x.name}(_ rhs: Self) -> Self
% end

  static func doubleWidthMultiply(_ lhs: Self, _ rhs: Self)
    -> (high: Self, low: Magnitude)
  static func doubleWidthDivide(
    _ lhs: (high: Self, low: Magnitude), _ rhs: Self)
    -> (quotient: Self, remainder: Self)

  init(_truncatingBits bits: UInt)

  var popcount: Int { get }
  var leadingZeros: Int { get }
}

//===----------------------------------------------------------------------===//
//===--- Operators on FixedWidthInteger -----------------------------------===//
//===----------------------------------------------------------------------===//

@inline(__always)
public prefix func ~ <T: FixedWidthInteger>(x: T) -> T {
  return 0 &- x &- 1
}

% for x in binaryBitwise:
@_transparent
public func ${x.operator} <T: FixedWidthInteger>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}(rhs)
}

@_transparent
public func ${x.operator}= <T: FixedWidthInteger>(lhs: inout T, rhs: T) {
  lhs = lhs.${x.name}(rhs)
}
% end

% for x in maskingShifts:

@_transparent
public func ${x.operator} <T: FixedWidthInteger>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}(rhs)
}

@_transparent
public func ${x.operator}= <T: FixedWidthInteger>(lhs: inout T, rhs: T) {
  lhs = lhs ${x.operator} rhs
}

@_transparent
public func ${x.operator} <
  T: FixedWidthInteger, U: BinaryInteger
>(lhs: T, rhs: U) -> T {
  return lhs.${x.name}(T(extendingOrTruncating: rhs))
}

@_transparent
public func ${x.operator}= <
  T: FixedWidthInteger, U: BinaryInteger
>(lhs: inout T, rhs: U) {
  lhs = lhs ${x.operator} rhs
}

@_transparent
public func ${x.nonMaskingOperator} <
  T: FixedWidthInteger, U: BinaryInteger
>(lhs: T, rhs: U) -> T {
  // FIXME(integers): uncomment once Int conforms to BinaryInteger
  //let shift = rhs < -T.bitWidth ? -T.bitWidth
            //: rhs > T.bitWidth ? T.bitWidth
            //: Int(rhs)
  //return lhs ${x.nonMaskingOperator} shift
  fatalError()
}

//===----------------------------------------------------------------------===//
//=== "Smart ${x.description}", supporting overshifts and negative shifts -===//
//===----------------------------------------------------------------------===//

@_transparent
public func ${x.nonMaskingOperator} <
  T: FixedWidthInteger
>(lhs: T, rhs: Int) -> T {
  // FIXME(integers): uncomment once Int conforms to BinaryInteger
  fatalError()
  //let overshiftR = T.isSigned ? lhs &>> (T.bitWidth - 1) : 0
  //let overshiftL: T = 0
  //if _fastPath(rhs >= 0) {
    //if _fastPath(rhs < T.bitWidth) {
      //return lhs.${x.name}(T(extendingOrTruncating: rhs))
    //}
    //return overshift${'LR'['R' in x.name]}
  //}

  //if _slowPath(rhs <= -T.bitWidth) {
    //return overshift${'RL'['R' in x.name]}
  //}
  //return lhs ${x.operator.translate(maketrans('<>', '><'))} -rhs
}

@_transparent
public func ${x.nonMaskingOperator}= <
  T: FixedWidthInteger
>(lhs: inout T, rhs: T) {
  lhs = lhs ${x.nonMaskingOperator} rhs
}

@_transparent
public func ${x.nonMaskingOperator}= <
  T: FixedWidthInteger, U: BinaryInteger
>(lhs: inout T, rhs: U) {
  lhs = lhs ${x.nonMaskingOperator} rhs
}

% end # maskingShifts


extension FixedWidthInteger {
  public init<Other: BinaryInteger>(clamping source: Other) {
    if _slowPath(source < Self.min) {
      self = Self.min
    }
    else if _slowPath(source > Self.max) {
      self = Self.max
    }
    else { self = Self(extendingOrTruncating: source) }
  }

% for x in binaryArithmetic['Arithmetic']:
%   callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
  @_transparent
  // FIXME(integers): rename `rhs` to `other`
  public mutating func ${x.mutatingName}(${x.firstArg} rhs: Self) {
    let (result, _ /*overflow*/) = self.${x.name}WithOverflow(${callLabel}rhs)
    // FIXME(integers): overflow check
    //_assertCond(overflow == .none, "overflow in ${x.name}")
    self = result
  }

  /// Return `self ${x.operator} rhs`.  If an arithmetic overflow
  /// occurs, the behavior is undefined.
  ///
  /// Note: use this function to avoid the cost of overflow checking
  /// when you are sure that the operation won't overflow.
  @_transparent
  public func unsafe${capitalize(x.name)}(rhs: Self) -> Self {
    let (result, overflow) = self.${x.name}WithOverflow(${callLabel}rhs)

    if (overflow != .none) {
      if (_isDebugAssertConfiguration()) {
        _preconditionFailure("overflow in unsafe${capitalize(x.name)}")
      }
      else {
        Builtin.conditionallyUnreachable()
      }
    }
    return result
  }
% end

  @_transparent
  public mutating func formRemainder(dividingBy other: Self) {
    // FIXME(integers): implement
    fatalError()
  }

  @_transparent
  public init<T : BinaryInteger>(extendingOrTruncating source: T) {
    if Self.bitWidth <= ${word_bits} {
      self = Self.init(_truncatingBits: source.word(at: 0))
    }
    else {
      var result: Self = source < 0 ? ~0 : 0
      // start with the most significant word
      var n = source.countRepresentedWords
      while n >= 0 {
        // masking is OK here because this we have already ensured
        // that Self.bitWidth > ${word_bits}.  Not masking results in
        // infinite recursion.
        result &<<= ${word_bits}
        result |= Self(_truncatingBits: source.word(at: n))
        n -= 1
      }

      self = result
    }
  }

  @_transparent
  // FIXME(integers): give it a better name. _highBitIndex is **NOT** what it is
  public // transparent
  static var _highBitIndex: Self {
    // FIXME(integers): uncomment once UInt conforms to BinaryInteger
    //return Self.init(_truncatingBits: UInt(Self.bitWidth._storage) &- 1)
    fatalError()
  }

  public var popcount: Int {
    fatalError()
  }

  public static func doubleWidthDivide(
    _ lhs: (high: Self, low: Magnitude), _ rhs: Self)
    -> (quotient: Self, remainder: Self) {
    fatalError()
  }
}

% for x in [op for ops in binaryArithmetic.values() for op in ops]:
%   callLabel = x.firstArg + ': ' if not x.firstArg == '_' else ''
%   if x.kind != '/':
public func &${x.operator} <T: FixedWidthInteger>(lhs: T, rhs: T) -> T {
  return lhs.${x.name}WithOverflow(${callLabel}rhs).partialValue
}
%   end
% end

//===----------------------------------------------------------------------===//
//===--- UnsignedInteger --------------------------------------------------===//
//===----------------------------------------------------------------------===//

public protocol UnsignedInteger_ : BinaryInteger {
  associatedtype Magnitude : BinaryInteger
}

extension UnsignedInteger_ {
  @_transparent
  public var magnitude: Self { return self }

  @_transparent
  public static var isSigned: Bool { return false }

  public var description: String {
    // FIXME(integers): uncomment once Int conforms to BinaryInteger
    fatalError()
    //if self == 0 {
      //return "0"
    //}

    //let ascii0 = 48
    //var buf: [UnicodeScalar] = []

    //var x = self
    //repeat {
      //let r = x % 10
      //x /= 10
      //buf.append(
        //UnicodeScalar(
          //ascii0 + Int(Word(extendingOrTruncating: r)._storage)))
    //}
    //while x != 0
    //return String(buf.reversed().lazy.map { Character($0) })
  }
}

extension UnsignedInteger_ where Self : FixedWidthInteger {
  @_transparent
  public init<T : BinaryInteger>(_ source: T) {
    // FIXME(integers): uncomment checks
    //_assertCond(
      //source >= 0, "negative value \(source) not representable by \(Self.self)")
    //let requiredBits = source.minimumSignedRepresentationBitWidth - 1
    //_assertCond(
      //requiredBits <= Self.bitWidth,
      //"\(Self.self) cannot store all \(requiredBits)  bits "
      //+ "needed for unsigned representation of \(source)")
    self.init(extendingOrTruncating: source)
  }

  @_transparent
  public init?<T : BinaryInteger>(exactly source: T) {
    // FIXME(integers): uncomment checks
    //_assertCond(
      //source >= 0, "negative value \(source) not representable by \(Self.self)")
    let requiredBits = source.minimumSignedRepresentationBitWidth - 1
    if requiredBits > Self.bitWidth {
      return nil
    }
    self.init(extendingOrTruncating: source)
  }

  @_transparent
  public static var max: Self {
    return ~0
  }

  @_transparent
  public static var min: Self {
    return 0
  }

}


//===----------------------------------------------------------------------===//
//===--- SignedInteger ----------------------------------------------------===//
//===----------------------------------------------------------------------===//

public protocol SignedInteger_ : BinaryInteger, SignedArithmetic {
  associatedtype Magnitude : BinaryInteger
}

extension SignedInteger_ {
  public var description: String {
    let base = String(describing: magnitude)
    return self < 0 ? "-" + base : base
  }

  @_transparent
  public static var isSigned: Bool { return true }
}

extension SignedInteger_ where Self : FixedWidthInteger {
  @_transparent
  public init<T : BinaryInteger>(_ source: T) {
    // FIXME(integers): uncomment checks
    //let requiredBits = source.minimumSignedRepresentationBitWidth
    //_assertCond(
      //requiredBits <= Self.bitWidth,
      //"\(Self.self) cannot store all \(requiredBits) bits "
      //+ "needed for signed representation of \(source)")
    self.init(extendingOrTruncating: source)
  }

  @_transparent
  public init?<T : BinaryInteger>(exactly source: T) {
    let requiredBits = source.minimumSignedRepresentationBitWidth
    if requiredBits > Self.bitWidth {
      return nil
    }
    self.init(extendingOrTruncating: source)
  }

  @_transparent
  public static var max: Self {
    return ~min
  }

  @_transparent
  public static var min: Self {
    return -1 &<< Self._highBitIndex
  }
}