/**
 * Combine a number of boolean expressions into a balanced expression tree. These expressions are
 * either combined by a logical [[And]] or a logical [[Or]].
 *
 * A balanced binary tree is created because regular left recursive trees cause considerable
 * performance degradations and can cause stack overflows.
 */
override def visitLogicalBinary(ctx: LogicalBinaryContext): Expression = withOrigin(ctx) {
  val expressionType = ctx.operator.getType
  val expressionCombiner = expressionType match {
    case SqlBaseParser.AND => And.apply _
    case SqlBaseParser.OR => Or.apply _
  }

  // Collect all similar left hand contexts.
  val contexts = ArrayBuffer(ctx.right)
  var current = ctx.left
  def collectContexts: Boolean = current match {
    case lbc: LogicalBinaryContext if lbc.operator.getType == expressionType =>
      contexts += lbc.right
      current = lbc.left
      true
    case _ =>
      contexts += current
      false
  }
  while (collectContexts) {
    // No body - all updates take place in the collectContexts.
  }

  // Reverse the contexts to have them in the same sequence as in the SQL statement & turn them
  // into expressions.
  val expressions = contexts.reverseMap(expression)

  // Create a balanced tree.
  def reduceToExpressionTree(low: Int, high: Int): Expression = high - low match {
    case 0 =>
      expressions(low)
    case 1 =>
      expressionCombiner(expressions(low), expressions(high))
    case x =>
      val mid = low + x / 2
      expressionCombiner(
        reduceToExpressionTree(low, mid),
        reduceToExpressionTree(mid + 1, high))
  }
  reduceToExpressionTree(0, expressions.size - 1)
}

/**
 * A column expression that generates monotonically increasing 64-bit integers.
 *
 * The generated ID is guaranteed to be monotonically increasing and unique, but not consecutive.
 * The current implementation puts the partition ID in the upper 31 bits, and the record number
 * within each partition in the lower 33 bits. The assumption is that the data frame has
 * less than 1 billion partitions, and each partition has less than 8 billion records.
 *
 * As an example, consider a `DataFrame` with two partitions, each with 3 records.
 * This expression would return the following IDs:
 *
 * {{{
 * 0, 1, 2, 8589934592 (1L << 33), 8589934593, 8589934594.
 * }}}
 *
 * @group normal_funcs
 * @since 1.6.0
 */
def monotonically_increasing_id(): Column = withExpr { MonotonicallyIncreasingID() }