# Copyright 2015 Google Inc. All Rights Reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Decide what the format for the code should be.

The `logical_line.LogicalLine`s are now ready to be formatted. LogicalLInes that
can be merged together are. The best formatting is returned as a string.

  Reformat(): the main function exported by this module.
"""

from __future__ import unicode_literals
import collections
import heapq
import re

from lib2to3 import pytree
from lib2to3.pgen2 import token

from yapf.yapflib import format_decision_state
from yapf.yapflib import format_token
from yapf.yapflib import line_joiner
from yapf.yapflib import pytree_utils
from yapf.yapflib import style
from yapf.yapflib import verifier


def Reformat(llines, verify=False, lines=None):
  """Reformat the logical lines.

  Arguments:
    llines: (list of logical_line.LogicalLine) Lines we want to format.
    verify: (bool) True if reformatted code should be verified for syntax.
    lines: (set of int) The lines which can be modified or None if there is no
      line range restriction.

  Returns:
    A string representing the reformatted code.
  """
  final_lines = []
  prev_line = None  # The previous line.
  indent_width = style.Get('INDENT_WIDTH')

  for lline in _SingleOrMergedLines(llines):
    first_token = lline.first
    _FormatFirstToken(first_token, lline.depth, prev_line, final_lines)

    indent_amt = indent_width * lline.depth
    state = format_decision_state.FormatDecisionState(lline, indent_amt)
    state.MoveStateToNextToken()

    if not lline.disable:
      if lline.first.is_comment:
        lline.first.node.value = lline.first.node.value.rstrip()
      elif lline.last.is_comment:
        lline.last.node.value = lline.last.node.value.rstrip()
      if prev_line and prev_line.disable:
        # Keep the vertical spacing between a disabled and enabled formatting
        # region.
        _RetainRequiredVerticalSpacingBetweenTokens(lline.first, prev_line.last,
                                                    lines)
      if any(tok.is_comment for tok in lline.tokens):
        _RetainVerticalSpacingBeforeComments(lline)

    if lline.disable or _LineHasContinuationMarkers(lline):
      _RetainHorizontalSpacing(lline)
      _RetainRequiredVerticalSpacing(lline, prev_line, lines)
      _EmitLineUnformatted(state)

    elif (_LineContainsPylintDisableLineTooLong(lline) or
          _LineContainsI18n(lline)):
      # Don't modify vertical spacing, but fix any horizontal spacing issues.
      _RetainRequiredVerticalSpacing(lline, prev_line, lines)
      _EmitLineUnformatted(state)

    elif _CanPlaceOnSingleLine(lline) and not any(tok.must_break_before
                                                  for tok in lline.tokens):
      # The logical line fits on one line.
      while state.next_token:
        state.AddTokenToState(newline=False, dry_run=False)

    elif not _AnalyzeSolutionSpace(state):
      # Failsafe mode. If there isn't a solution to the line, then just emit
      # it as is.
      state = format_decision_state.FormatDecisionState(lline, indent_amt)
      state.MoveStateToNextToken()
      _RetainHorizontalSpacing(lline)
      _RetainRequiredVerticalSpacing(lline, prev_line, None)
      _EmitLineUnformatted(state)

    final_lines.append(lline)
    prev_line = lline

  _AlignTrailingComments(final_lines)
  return _FormatFinalLines(final_lines, verify)


def _RetainHorizontalSpacing(line):
  """Retain all horizontal spacing between tokens."""
  for tok in line.tokens:
    tok.RetainHorizontalSpacing(line.first.column, line.depth)


def _RetainRequiredVerticalSpacing(cur_line, prev_line, lines):
  """Retain all vertical spacing between lines."""
  prev_tok = None
  if prev_line is not None:
    prev_tok = prev_line.last

  if cur_line.disable:
    # After the first token we are acting on a single line. So if it is
    # disabled we must not reformat.
    lines = set()

  for cur_tok in cur_line.tokens:
    _RetainRequiredVerticalSpacingBetweenTokens(cur_tok, prev_tok, lines)
    prev_tok = cur_tok


def _RetainRequiredVerticalSpacingBetweenTokens(cur_tok, prev_tok, lines):
  """Retain vertical spacing between two tokens if not in editable range."""
  if prev_tok is None:
    return

  if prev_tok.is_string:
    prev_lineno = prev_tok.lineno + prev_tok.value.count('\n')
  elif prev_tok.is_pseudo:
    if not prev_tok.previous_token.is_multiline_string:
      prev_lineno = prev_tok.previous_token.lineno
    else:
      prev_lineno = prev_tok.lineno
  else:
    prev_lineno = prev_tok.lineno

  if cur_tok.is_comment:
    cur_lineno = cur_tok.lineno - cur_tok.value.count('\n')
  else:
    cur_lineno = cur_tok.lineno

  if not prev_tok.is_comment and prev_tok.value.endswith('\\'):
    prev_lineno += prev_tok.value.count('\n')

  required_newlines = cur_lineno - prev_lineno
  if cur_tok.is_comment and not prev_tok.is_comment:
    # Don't adjust between a comment and non-comment.
    pass
  elif lines and lines.intersection(range(prev_lineno, cur_lineno + 1)):
    desired_newlines = cur_tok.whitespace_prefix.count('\n')
    whitespace_lines = range(prev_lineno + 1, cur_lineno)
    deletable_lines = len(lines.intersection(whitespace_lines))
    required_newlines = max(required_newlines - deletable_lines,
                            desired_newlines)

  cur_tok.AdjustNewlinesBefore(required_newlines)


def _RetainVerticalSpacingBeforeComments(line):
  """Retain vertical spacing before comments."""
  prev_token = None
  for tok in line.tokens:
    if tok.is_comment and prev_token:
      if tok.lineno - tok.value.count('\n') - prev_token.lineno > 1:
        tok.AdjustNewlinesBefore(ONE_BLANK_LINE)

    prev_token = tok


def _EmitLineUnformatted(state):
  """Emit the line without formatting.

  The line contains code that if reformatted would break a non-syntactic
  convention. E.g., i18n comments and function calls are tightly bound by
  convention. Instead, we calculate when / if a newline should occur and honor
  that. But otherwise the code emitted will be the same as the original code.

  Arguments:
    state: (format_decision_state.FormatDecisionState) The format decision
      state.
  """
  while state.next_token:
    previous_token = state.next_token.previous_token
    previous_lineno = previous_token.lineno

    if previous_token.is_multiline_string or previous_token.is_string:
      previous_lineno += previous_token.value.count('\n')

    if previous_token.is_continuation:
      newline = False
    else:
      newline = state.next_token.lineno > previous_lineno

    state.AddTokenToState(newline=newline, dry_run=False)


def _LineContainsI18n(line):
  """Return true if there are i18n comments or function calls in the line.

  I18n comments and pseudo-function calls are closely related. They cannot
  be moved apart without breaking i18n.

  Arguments:
    line: (logical_line.LogicalLine) The line currently being formatted.

  Returns:
    True if the line contains i18n comments or function calls. False otherwise.
  """
  if style.Get('I18N_COMMENT'):
    for tok in line.tokens:
      if tok.is_comment and re.match(style.Get('I18N_COMMENT'), tok.value):
        # Contains an i18n comment.
        return True

  if style.Get('I18N_FUNCTION_CALL'):
    length = len(line.tokens)
    for index in range(length - 1):
      if (line.tokens[index + 1].value == '(' and
          line.tokens[index].value in style.Get('I18N_FUNCTION_CALL')):
        return True
  return False


def _LineContainsPylintDisableLineTooLong(line):
  """Return true if there is a "pylint: disable=line-too-long" comment."""
  return re.search(r'\bpylint:\s+disable=line-too-long\b', line.last.value)


def _LineHasContinuationMarkers(line):
  """Return true if the line has continuation markers in it."""
  return any(tok.is_continuation for tok in line.tokens)


def _CanPlaceOnSingleLine(line):
  """Determine if the logical line can go on a single line.

  Arguments:
    line: (logical_line.LogicalLine) The line currently being formatted.

  Returns:
    True if the line can or should be added to a single line. False otherwise.
  """
  token_names = [x.name for x in line.tokens]
  if (style.Get('FORCE_MULTILINE_DICT') and 'LBRACE' in token_names):
    return False
  indent_amt = style.Get('INDENT_WIDTH') * line.depth
  last = line.last
  last_index = -1
  if (last.is_pylint_comment or last.is_pytype_comment or
      last.is_copybara_comment):
    last = last.previous_token
    last_index = -2
  if last is None:
    return True
  return (last.total_length + indent_amt <= style.Get('COLUMN_LIMIT') and
          not any(tok.is_comment for tok in line.tokens[:last_index]))


def _AlignTrailingComments(final_lines):
  """Align trailing comments to the same column."""
  final_lines_index = 0
  while final_lines_index < len(final_lines):
    line = final_lines[final_lines_index]
    assert line.tokens

    processed_content = False

    for tok in line.tokens:
      if (tok.is_comment and isinstance(tok.spaces_required_before, list) and
          tok.value.startswith('#')):
        # All trailing comments and comments that appear on a line by themselves
        # in this block should be indented at the same level. The block is
        # terminated by an empty line or EOF. Enumerate through each line in
        # the block and calculate the max line length. Once complete, use the
        # first col value greater than that value and create the necessary for
        # each line accordingly.
        all_pc_line_lengths = []  # All pre-comment line lengths
        max_line_length = 0

        while True:
          # EOF
          if final_lines_index + len(all_pc_line_lengths) == len(final_lines):
            break

          this_line = final_lines[final_lines_index + len(all_pc_line_lengths)]

          # Blank line - note that content is preformatted so we don't need to
          # worry about spaces/tabs; a blank line will always be '\n\n'.
          assert this_line.tokens
          if (all_pc_line_lengths and
              this_line.tokens[0].formatted_whitespace_prefix.startswith('\n\n')
             ):
            break

          if this_line.disable:
            all_pc_line_lengths.append([])
            continue

          # Calculate the length of each line in this logical line.
          line_content = ''
          pc_line_lengths = []

          for line_tok in this_line.tokens:
            whitespace_prefix = line_tok.formatted_whitespace_prefix

            newline_index = whitespace_prefix.rfind('\n')
            if newline_index != -1:
              max_line_length = max(max_line_length, len(line_content))
              line_content = ''

              whitespace_prefix = whitespace_prefix[newline_index + 1:]

            if line_tok.is_comment:
              pc_line_lengths.append(len(line_content))
            else:
              line_content += '{}{}'.format(whitespace_prefix, line_tok.value)

          if pc_line_lengths:
            max_line_length = max(max_line_length, max(pc_line_lengths))

          all_pc_line_lengths.append(pc_line_lengths)

        # Calculate the aligned column value
        max_line_length += 2

        aligned_col = None
        for potential_col in tok.spaces_required_before:
          if potential_col > max_line_length:
            aligned_col = potential_col
            break

        if aligned_col is None:
          aligned_col = max_line_length

        # Update the comment token values based on the aligned values
        for all_pc_line_lengths_index, pc_line_lengths in enumerate(
            all_pc_line_lengths):
          if not pc_line_lengths:
            continue

          this_line = final_lines[final_lines_index + all_pc_line_lengths_index]

          pc_line_length_index = 0
          for line_tok in this_line.tokens:
            if line_tok.is_comment:
              assert pc_line_length_index < len(pc_line_lengths)
              assert pc_line_lengths[pc_line_length_index] < aligned_col

              # Note that there may be newlines embedded in the comments, so
              # we need to apply a whitespace prefix to each line.
              whitespace = ' ' * (
                  aligned_col - pc_line_lengths[pc_line_length_index] - 1)
              pc_line_length_index += 1

              line_content = []

              for comment_line_index, comment_line in enumerate(
                  line_tok.value.split('\n')):
                line_content.append('{}{}'.format(whitespace,
                                                  comment_line.strip()))

                if comment_line_index == 0:
                  whitespace = ' ' * (aligned_col - 1)

              line_content = '\n'.join(line_content)

              # Account for initial whitespace already slated for the
              # beginning of the line.
              existing_whitespace_prefix = \
                line_tok.formatted_whitespace_prefix.lstrip('\n')

              if line_content.startswith(existing_whitespace_prefix):
                line_content = line_content[len(existing_whitespace_prefix):]

              line_tok.value = line_content

          assert pc_line_length_index == len(pc_line_lengths)

        final_lines_index += len(all_pc_line_lengths)

        processed_content = True
        break

    if not processed_content:
      final_lines_index += 1


def _FormatFinalLines(final_lines, verify):
  """Compose the final output from the finalized lines."""
  formatted_code = []
  for line in final_lines:
    formatted_line = []
    for tok in line.tokens:
      if not tok.is_pseudo:
        formatted_line.append(tok.formatted_whitespace_prefix)
        formatted_line.append(tok.value)
      elif (not tok.next_token.whitespace_prefix.startswith('\n') and
            not tok.next_token.whitespace_prefix.startswith(' ')):
        if (tok.previous_token.value == ':' or
            tok.next_token.value not in ',}])'):
          formatted_line.append(' ')

    formatted_code.append(''.join(formatted_line))
    if verify:
      verifier.VerifyCode(formatted_code[-1])

  return ''.join(formatted_code) + '\n'


class _StateNode(object):
  """An edge in the solution space from 'previous.state' to 'state'.

  Attributes:
    state: (format_decision_state.FormatDecisionState) The format decision state
      for this node.
    newline: If True, then on the edge from 'previous.state' to 'state' a
      newline is inserted.
    previous: (_StateNode) The previous state node in the graph.
  """

  # TODO(morbo): Add a '__cmp__' method.

  def __init__(self, state, newline, previous):
    self.state = state.Clone()
    self.newline = newline
    self.previous = previous

  def __repr__(self):  # pragma: no cover
    return 'StateNode(state=[\n{0}\n], newline={1})'.format(
        self.state, self.newline)


# A tuple of (penalty, count) that is used to prioritize the BFS. In case of
# equal penalties, we prefer states that were inserted first. During state
# generation, we make sure that we insert states first that break the line as
# late as possible.
_OrderedPenalty = collections.namedtuple('OrderedPenalty', ['penalty', 'count'])

# An item in the prioritized BFS search queue. The 'StateNode's 'state' has
# the given '_OrderedPenalty'.
_QueueItem = collections.namedtuple('QueueItem',
                                    ['ordered_penalty', 'state_node'])


def _AnalyzeSolutionSpace(initial_state):
  """Analyze the entire solution space starting from initial_state.

  This implements a variant of Dijkstra's algorithm on the graph that spans
  the solution space (LineStates are the nodes). The algorithm tries to find
  the shortest path (the one with the lowest penalty) from 'initial_state' to
  the state where all tokens are placed.

  Arguments:
    initial_state: (format_decision_state.FormatDecisionState) The initial state
      to start the search from.

  Returns:
    True if a formatting solution was found. False otherwise.
  """
  count = 0
  seen = set()
  p_queue = []

  # Insert start element.
  node = _StateNode(initial_state, False, None)
  heapq.heappush(p_queue, _QueueItem(_OrderedPenalty(0, count), node))

  count += 1
  while p_queue:
    item = p_queue[0]
    penalty = item.ordered_penalty.penalty
    node = item.state_node
    if not node.state.next_token:
      break
    heapq.heappop(p_queue)

    if count > 10000:
      node.state.ignore_stack_for_comparison = True

    # Unconditionally add the state and check if it was present to avoid having
    # to hash it twice in the common case (state hashing is expensive).
    before_seen_count = len(seen)
    seen.add(node.state)
    # If seen didn't change size, the state was already present.
    if before_seen_count == len(seen):
      continue

    # FIXME(morbo): Add a 'decision' element?

    count = _AddNextStateToQueue(penalty, node, False, count, p_queue)
    count = _AddNextStateToQueue(penalty, node, True, count, p_queue)

  if not p_queue:
    # We weren't able to find a solution. Do nothing.
    return False

  _ReconstructPath(initial_state, heapq.heappop(p_queue).state_node)
  return True


def _AddNextStateToQueue(penalty, previous_node, newline, count, p_queue):
  """Add the following state to the analysis queue.

  Assume the current state is 'previous_node' and has been reached with a
  penalty of 'penalty'. Insert a line break if 'newline' is True.

  Arguments:
    penalty: (int) The penalty associated with the path up to this point.
    previous_node: (_StateNode) The last _StateNode inserted into the priority
      queue.
    newline: (bool) Add a newline if True.
    count: (int) The number of elements in the queue.
    p_queue: (heapq) The priority queue representing the solution space.

  Returns:
    The updated number of elements in the queue.
  """
  must_split = previous_node.state.MustSplit()
  if newline and not previous_node.state.CanSplit(must_split):
    # Don't add a newline if the token cannot be split.
    return count
  if not newline and must_split:
    # Don't add a token we must split but where we aren't splitting.
    return count

  node = _StateNode(previous_node.state, newline, previous_node)
  penalty += node.state.AddTokenToState(
      newline=newline, dry_run=True, must_split=must_split)
  heapq.heappush(p_queue, _QueueItem(_OrderedPenalty(penalty, count), node))
  return count + 1


def _ReconstructPath(initial_state, current):
  """Reconstruct the path through the queue with lowest penalty.

  Arguments:
    initial_state: (format_decision_state.FormatDecisionState) The initial state
      to start the search from.
    current: (_StateNode) The node in the decision graph that is the end point
      of the path with the least penalty.
  """
  path = collections.deque()

  while current.previous:
    path.appendleft(current)
    current = current.previous

  for node in path:
    initial_state.AddTokenToState(newline=node.newline, dry_run=False)


NESTED_DEPTH = []


def _FormatFirstToken(first_token, indent_depth, prev_line, final_lines):
  """Format the first token in the logical line.

  Add a newline and the required indent before the first token of the logical
  line.

  Arguments:
    first_token: (format_token.FormatToken) The first token in the logical line.
    indent_depth: (int) The line's indentation depth.
    prev_line: (list of logical_line.LogicalLine) The logical line previous to
      this line.
    final_lines: (list of logical_line.LogicalLine) The logical lines that have
      already been processed.
  """
  global NESTED_DEPTH
  while NESTED_DEPTH and NESTED_DEPTH[-1] > indent_depth:
    NESTED_DEPTH.pop()

  first_nested = False
  if _IsClassOrDef(first_token):
    if not NESTED_DEPTH:
      NESTED_DEPTH = [indent_depth]
    elif NESTED_DEPTH[-1] < indent_depth:
      first_nested = True
      NESTED_DEPTH.append(indent_depth)

  first_token.AddWhitespacePrefix(
      _CalculateNumberOfNewlines(first_token, indent_depth, prev_line,
                                 final_lines, first_nested),
      indent_level=indent_depth)


NO_BLANK_LINES = 1
ONE_BLANK_LINE = 2
TWO_BLANK_LINES = 3


def _IsClassOrDef(tok):
  if tok.value in {'class', 'def', '@'}:
    return True
  return (tok.next_token and tok.value == 'async' and
          tok.next_token.value == 'def')


def _CalculateNumberOfNewlines(first_token, indent_depth, prev_line,
                               final_lines, first_nested):
  """Calculate the number of newlines we need to add.

  Arguments:
    first_token: (format_token.FormatToken) The first token in the logical
      line.
    indent_depth: (int) The line's indentation depth.
    prev_line: (list of logical_line.LogicalLine) The logical line previous to
      this line.
    final_lines: (list of logical_line.LogicalLine) The logical lines that have
      already been processed.
    first_nested: (boolean) Whether this is the first nested class or function.

  Returns:
    The number of newlines needed before the first token.
  """
  # TODO(morbo): Special handling for imports.
  # TODO(morbo): Create a knob that can tune these.
  if prev_line is None:
    # The first line in the file. Don't add blank lines.
    # FIXME(morbo): Is this correct?
    if first_token.newlines is not None:
      first_token.newlines = None
    return 0

  if first_token.is_docstring:
    if (prev_line.first.value == 'class' and
        style.Get('BLANK_LINE_BEFORE_CLASS_DOCSTRING')):
      # Enforce a blank line before a class's docstring.
      return ONE_BLANK_LINE
    elif (prev_line.first.value.startswith('#') and
          style.Get('BLANK_LINE_BEFORE_MODULE_DOCSTRING')):
      # Enforce a blank line before a module's docstring.
      return ONE_BLANK_LINE
    # The docstring shouldn't have a newline before it.
    return NO_BLANK_LINES

  if first_token.is_name and not indent_depth:
    if prev_line.first.value in {'from', 'import'}:
      # Support custom number of blank lines between top-level imports and
      # variable definitions.
      return 1 + style.Get(
          'BLANK_LINES_BETWEEN_TOP_LEVEL_IMPORTS_AND_VARIABLES')

  prev_last_token = prev_line.last
  if prev_last_token.is_docstring:
    if (not indent_depth and first_token.value in {'class', 'def', 'async'}):
      # Separate a class or function from the module-level docstring with
      # appropriate number of blank lines.
      return 1 + style.Get('BLANK_LINES_AROUND_TOP_LEVEL_DEFINITION')
    if (first_nested and
        not style.Get('BLANK_LINE_BEFORE_NESTED_CLASS_OR_DEF') and
        _IsClassOrDef(first_token)):
      first_token.newlines = None
      return NO_BLANK_LINES
    if _NoBlankLinesBeforeCurrentToken(prev_last_token.value, first_token,
                                       prev_last_token):
      return NO_BLANK_LINES
    else:
      return ONE_BLANK_LINE

  if _IsClassOrDef(first_token):
    # TODO(morbo): This can go once the blank line calculator is more
    # sophisticated.
    if not indent_depth:
      # This is a top-level class or function.
      is_inline_comment = prev_last_token.whitespace_prefix.count('\n') == 0
      if (not prev_line.disable and prev_last_token.is_comment and
          not is_inline_comment):
        # This token follows a non-inline comment.
        if _NoBlankLinesBeforeCurrentToken(prev_last_token.value, first_token,
                                           prev_last_token):
          # Assume that the comment is "attached" to the current line.
          # Therefore, we want two blank lines before the comment.
          index = len(final_lines) - 1
          while index > 0:
            if not final_lines[index - 1].is_comment:
              break
            index -= 1
          if final_lines[index - 1].first.value == '@':
            final_lines[index].first.AdjustNewlinesBefore(NO_BLANK_LINES)
          else:
            prev_last_token.AdjustNewlinesBefore(
                1 + style.Get('BLANK_LINES_AROUND_TOP_LEVEL_DEFINITION'))
          if first_token.newlines is not None:
            first_token.newlines = None
          return NO_BLANK_LINES
    elif _IsClassOrDef(prev_line.first):
      if first_nested and not style.Get(
          'BLANK_LINE_BEFORE_NESTED_CLASS_OR_DEF'):
        first_token.newlines = None
        return NO_BLANK_LINES

  # Calculate how many newlines were between the original lines. We want to
  # retain that formatting if it doesn't violate one of the style guide rules.
  if first_token.is_comment:
    first_token_lineno = first_token.lineno - first_token.value.count('\n')
  else:
    first_token_lineno = first_token.lineno

  prev_last_token_lineno = prev_last_token.lineno
  if prev_last_token.is_multiline_string:
    prev_last_token_lineno += prev_last_token.value.count('\n')

  if first_token_lineno - prev_last_token_lineno > 1:
    return ONE_BLANK_LINE

  return NO_BLANK_LINES


def _SingleOrMergedLines(lines):
  """Generate the lines we want to format.

  Arguments:
    lines: (list of logical_line.LogicalLine) Lines we want to format.

  Yields:
    Either a single line, if the current line cannot be merged with the
    succeeding line, or the next two lines merged into one line.
  """
  index = 0
  last_was_merged = False
  while index < len(lines):
    if lines[index].disable:
      line = lines[index]
      index += 1
      while index < len(lines):
        column = line.last.column + 2
        if lines[index].lineno != line.lineno:
          break
        if line.last.value != ':':
          leaf = pytree.Leaf(
              type=token.SEMI, value=';', context=('', (line.lineno, column)))
          line.AppendToken(format_token.FormatToken(leaf))
        for tok in lines[index].tokens:
          line.AppendToken(tok)
        index += 1
      yield line
    elif line_joiner.CanMergeMultipleLines(lines[index:], last_was_merged):
      # TODO(morbo): This splice is potentially very slow. Come up with a more
      # performance-friendly way of determining if two lines can be merged.
      next_line = lines[index + 1]
      for tok in next_line.tokens:
        lines[index].AppendToken(tok)
      if (len(next_line.tokens) == 1 and next_line.first.is_multiline_string):
        # This may be a multiline shebang. In that case, we want to retain the
        # formatting. Otherwise, it could mess up the shell script's syntax.
        lines[index].disable = True
      yield lines[index]
      index += 2
      last_was_merged = True
    else:
      yield lines[index]
      index += 1
      last_was_merged = False


def _NoBlankLinesBeforeCurrentToken(text, cur_token, prev_token):
  """Determine if there are no blank lines before the current token.

  The previous token is a docstring or comment. The prev_token_lineno is the
  start of the text of that token. Counting the number of newlines in its text
  gives us the extent and thus where the line number of the end of the
  docstring or comment. After that, we just compare it to the current token's
  line number to see if there are blank lines between them.

  Arguments:
    text: (unicode) The text of the docstring or comment before the current
      token.
    cur_token: (format_token.FormatToken) The current token in the logical line.
    prev_token: (format_token.FormatToken) The previous token in the logical
      line.

  Returns:
    True if there is no blank line before the current token.
  """
  cur_token_lineno = cur_token.lineno
  if cur_token.is_comment:
    cur_token_lineno -= cur_token.value.count('\n')
  num_newlines = text.count('\n') if not prev_token.is_comment else 0
  return prev_token.lineno + num_newlines == cur_token_lineno - 1