def perform_diff(text_1, text_2):
  if text_1 == text_2:
    return []

  lines_1 = text_1.split('\n')
  lines_2 = text_2.split('\n')

  trimmed_front = 0
  trimmed_back = 0

  # Remove identical lines at the beginning and end of the file
  while len(lines_1) > trimmed_front and len(lines_2) > trimmed_front and lines_1[trimmed_front] == lines_2[trimmed_front]:
    trimmed_front += 1
  lines_1 = lines_1[trimmed_front:]
  lines_2 = lines_2[trimmed_front:]

  while len(lines_1) > trimmed_back and len(lines_2) > trimmed_back and lines_1[-1 - trimmed_back] == lines_2[-1 - trimmed_back]:
    trimmed_back += 1
  lines_1 = lines_1[:-trimmed_back]
  lines_2 = lines_2[:-trimmed_back]

  length_1 = len(lines_1)
  length_2 = len(lines_2)

  grid = []

  for x in range(length_2 + 1):
    column = []
    for y in range(length_1 + 1):
      column.append(None)
    grid.append(column)

  # Perform levenshtein difference
  # each grid cell will consist of a tuple: (diff-size, previous-path: up|left|diag)

  # Each step to the right indicates taking a line from lines 2
  # Each step downwards indicates taking a line from lines 1

  # Prepopulate the left and top rows indicating starting the diff by removing all
  # lines from lines 1 and adding all lines from lines 2.
  for x in range(length_2 + 1):
    grid[x][0] = (x, 'left')
  for y in range(length_1 + 1):
    grid[0][y] = (y, 'up')
  grid[0][0] = (0, 'diag')

  # Populate the grid. Figure out the minimum diff to get to each point.
  for y in range(1, length_1 + 1):
    for x in range(1, length_2 + 1):
      if lines_1[y - 1] == lines_2[x - 1]:
        grid[x][y] = (grid[x - 1][y - 1][0], 'diag')
      elif (grid[x - 1][y][0] <= grid[x][y - 1][0]):
        grid[x][y] = (grid[x - 1][y][0] + 1, 'left')
      else:
        grid[x][y] = (grid[x][y - 1][0] + 1, 'up')

  # Start from the bottom right corner and walk backwards to the origin
  x = length_2
  y = length_1
  diff_chain = []
  ellipsis_used = False
  while x != 0 and y != 0:
    node = grid[x][y]
    if node[1] == 'diag':
      if not ellipsis_used:
        diff_chain.append('...')
        ellipsis_used = True
      x -= 1
      y -= 1
    elif node[1] == 'left':
      diff_chain.append('+ [' + str(trimmed_front + x) + '] ' + lines_2[x - 1])
      x -= 1
      ellipsis_used = False
    else:
      diff_chain.append('- [' + str(trimmed_front + y) + '] ' + lines_1[y - 1])
      y -= 1
      ellipsis_used = False

  diff_chain.reverse()

  return diff_chain