prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Wrong Tooltip with shift-tab
  @andram opened jupyter/notebook#520 at 2015-10-01 10:09:29 UTC
  
  If a notebook cell starts with a multiline string, then shift-tab gets confused and shows the wrong tooltips for following lines. For example consider a cell containing the following 5 lines:
  
  ```
  """
  Docstring
  """
  max()
  min()
  ```
  
  now position the cursor inside the brackets of max(). Expected behaviour is that the docstring for `max` is shown. Actual behaviour is that the docstring for min is shown. (see attached screenshot for current github version of jupyter notebook)
  
  ![notebook_tooltip_problem](https://cloud.githubusercontent.com/assets/3459178/10218173/b2415676-682c-11e5-8551-708c1dc1ab53.png)
  
  
  </issue>
  <code>
  [start of IPython/utils/tokenutil.py]
  1 """Token-related utilities"""
  2 
  3 # Copyright (c) IPython Development Team.
  4 # Distributed under the terms of the Modified BSD License.
  5 
  6 from __future__ import absolute_import, print_function
  7 
  8 from collections import namedtuple
  9 from io import StringIO
  10 from keyword import iskeyword
  11 
  12 from . import tokenize2
  13 from .py3compat import cast_unicode_py2
  14 
  15 Token = namedtuple('Token', ['token', 'text', 'start', 'end', 'line'])
  16 
  17 def generate_tokens(readline):
  18     """wrap generate_tokens to catch EOF errors"""
  19     try:
  20         for token in tokenize2.generate_tokens(readline):
  21             yield token
  22     except tokenize2.TokenError:
  23         # catch EOF error
  24         return
  25 
  26 def line_at_cursor(cell, cursor_pos=0):
  27     """Return the line in a cell at a given cursor position
  28     
  29     Used for calling line-based APIs that don't support multi-line input, yet.
  30     
  31     Parameters
  32     ----------
  33     
  34     cell: text
  35         multiline block of text
  36     cursor_pos: integer
  37         the cursor position
  38     
  39     Returns
  40     -------
  41     
  42     (line, offset): (text, integer)
  43         The line with the current cursor, and the character offset of the start of the line.
  44     """
  45     offset = 0
  46     lines = cell.splitlines(True)
  47     for line in lines:
  48         next_offset = offset + len(line)
  49         if next_offset >= cursor_pos:
  50             break
  51         offset = next_offset
  52     else:
  53         line = ""
  54     return (line, offset)
  55 
  56 def token_at_cursor(cell, cursor_pos=0):
  57     """Get the token at a given cursor
  58     
  59     Used for introspection.
  60     
  61     Function calls are prioritized, so the token for the callable will be returned
  62     if the cursor is anywhere inside the call.
  63     
  64     Parameters
  65     ----------
  66     
  67     cell : unicode
  68         A block of Python code
  69     cursor_pos : int
  70         The location of the cursor in the block where the token should be found
  71     """
  72     cell = cast_unicode_py2(cell)
  73     names = []
  74     tokens = []
  75     offset = 0
  76     call_names = []
  77     for tup in generate_tokens(StringIO(cell).readline):
  78         
  79         tok = Token(*tup)
  80         
  81         # token, text, start, end, line = tup
  82         start_col = tok.start[1]
  83         end_col = tok.end[1]
  84         # allow '|foo' to find 'foo' at the beginning of a line
  85         boundary = cursor_pos + 1 if start_col == 0 else cursor_pos
  86         if offset + start_col >= boundary:
  87             # current token starts after the cursor,
  88             # don't consume it
  89             break
  90         
  91         if tok.token == tokenize2.NAME and not iskeyword(tok.text):
  92             if names and tokens and tokens[-1].token == tokenize2.OP and tokens[-1].text == '.':
  93                 names[-1] = "%s.%s" % (names[-1], tok.text)
  94             else:
  95                 names.append(tok.text)
  96         elif tok.token == tokenize2.OP:
  97             if tok.text == '=' and names:
  98                 # don't inspect the lhs of an assignment
  99                 names.pop(-1)
  100             if tok.text == '(' and names:
  101                 # if we are inside a function call, inspect the function
  102                 call_names.append(names[-1])
  103             elif tok.text == ')' and call_names:
  104                 call_names.pop(-1)
  105         
  106         if offset + end_col > cursor_pos:
  107             # we found the cursor, stop reading
  108             break
  109         
  110         tokens.append(tok)
  111         if tok.token in (tokenize2.NEWLINE, tokenize2.NL):
  112             offset += len(tok.line)
  113     
  114     if call_names:
  115         return call_names[-1]
  116     elif names:
  117         return names[-1]
  118     else:
  119         return ''
  120     
  121 
  122
  [end of IPython/utils/tokenutil.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/IPython/utils/tokenutil.py b/IPython/utils/tokenutil.py
  --- a/IPython/utils/tokenutil.py
  +++ b/IPython/utils/tokenutil.py
  @@ -72,15 +72,24 @@
       cell = cast_unicode_py2(cell)
       names = []
       tokens = []
  -    offset = 0
       call_names = []
  +    
  +    offsets = {1: 0} # lines start at 1
       for tup in generate_tokens(StringIO(cell).readline):
           
           tok = Token(*tup)
           
           # token, text, start, end, line = tup
  -        start_col = tok.start[1]
  -        end_col = tok.end[1]
  +        start_line, start_col = tok.start
  +        end_line, end_col = tok.end
  +        if end_line + 1 not in offsets:
  +            # keep track of offsets for each line
  +            lines = tok.line.splitlines(True)
  +            for lineno, line in zip(range(start_line + 1, end_line + 2), lines):
  +                if lineno not in offsets:
  +                    offsets[lineno] = offsets[lineno-1] + len(line)
  +        
  +        offset = offsets[start_line]
           # allow '|foo' to find 'foo' at the beginning of a line
           boundary = cursor_pos + 1 if start_col == 0 else cursor_pos
           if offset + start_col >= boundary:
  @@ -103,14 +112,12 @@
               elif tok.text == ')' and call_names:
                   call_names.pop(-1)
           
  -        if offset + end_col > cursor_pos:
  +        tokens.append(tok)
  +        
  +        if offsets[end_line] + end_col > cursor_pos:
               # we found the cursor, stop reading
               break
           
  -        tokens.append(tok)
  -        if tok.token in (tokenize2.NEWLINE, tokenize2.NL):
  -            offset += len(tok.line)
  -    
       if call_names:
           return call_names[-1]
       elif names:
  
verification_info: {"golden_diff": "diff --git a/IPython/utils/tokenutil.py b/IPython/utils/tokenutil.py\n--- a/IPython/utils/tokenutil.py\n+++ b/IPython/utils/tokenutil.py\n@@ -72,15 +72,24 @@\n     cell = cast_unicode_py2(cell)\n     names = []\n     tokens = []\n-    offset = 0\n     call_names = []\n+    \n+    offsets = {1: 0} # lines start at 1\n     for tup in generate_tokens(StringIO(cell).readline):\n         \n         tok = Token(*tup)\n         \n         # token, text, start, end, line = tup\n-        start_col = tok.start[1]\n-        end_col = tok.end[1]\n+        start_line, start_col = tok.start\n+        end_line, end_col = tok.end\n+        if end_line + 1 not in offsets:\n+            # keep track of offsets for each line\n+            lines = tok.line.splitlines(True)\n+            for lineno, line in zip(range(start_line + 1, end_line + 2), lines):\n+                if lineno not in offsets:\n+                    offsets[lineno] = offsets[lineno-1] + len(line)\n+        \n+        offset = offsets[start_line]\n         # allow '|foo' to find 'foo' at the beginning of a line\n         boundary = cursor_pos + 1 if start_col == 0 else cursor_pos\n         if offset + start_col >= boundary:\n@@ -103,14 +112,12 @@\n             elif tok.text == ')' and call_names:\n                 call_names.pop(-1)\n         \n-        if offset + end_col > cursor_pos:\n+        tokens.append(tok)\n+        \n+        if offsets[end_line] + end_col > cursor_pos:\n             # we found the cursor, stop reading\n             break\n         \n-        tokens.append(tok)\n-        if tok.token in (tokenize2.NEWLINE, tokenize2.NL):\n-            offset += len(tok.line)\n-    \n     if call_names:\n         return call_names[-1]\n     elif names:\n", "issue": "Wrong Tooltip with shift-tab\n@andram opened jupyter/notebook#520 at 2015-10-01 10:09:29 UTC\n\nIf a notebook cell starts with a multiline string, then shift-tab gets confused and shows the wrong tooltips for following lines. For example consider a cell containing the following 5 lines:\n\n```\n\"\"\"\nDocstring\n\"\"\"\nmax()\nmin()\n```\n\nnow position the cursor inside the brackets of max(). Expected behaviour is that the docstring for `max` is shown. Actual behaviour is that the docstring for min is shown. (see attached screenshot for current github version of jupyter notebook)\n\n![notebook_tooltip_problem](https://cloud.githubusercontent.com/assets/3459178/10218173/b2415676-682c-11e5-8551-708c1dc1ab53.png)\n\n", "before_files": [{"content": "\"\"\"Token-related utilities\"\"\"\n\n# Copyright (c) IPython Development Team.\n# Distributed under the terms of the Modified BSD License.\n\nfrom __future__ import absolute_import, print_function\n\nfrom collections import namedtuple\nfrom io import StringIO\nfrom keyword import iskeyword\n\nfrom . import tokenize2\nfrom .py3compat import cast_unicode_py2\n\nToken = namedtuple('Token', ['token', 'text', 'start', 'end', 'line'])\n\ndef generate_tokens(readline):\n    \"\"\"wrap generate_tokens to catch EOF errors\"\"\"\n    try:\n        for token in tokenize2.generate_tokens(readline):\n            yield token\n    except tokenize2.TokenError:\n        # catch EOF error\n        return\n\ndef line_at_cursor(cell, cursor_pos=0):\n    \"\"\"Return the line in a cell at a given cursor position\n    \n    Used for calling line-based APIs that don't support multi-line input, yet.\n    \n    Parameters\n    ----------\n    \n    cell: text\n        multiline block of text\n    cursor_pos: integer\n        the cursor position\n    \n    Returns\n    -------\n    \n    (line, offset): (text, integer)\n        The line with the current cursor, and the character offset of the start of the line.\n    \"\"\"\n    offset = 0\n    lines = cell.splitlines(True)\n    for line in lines:\n        next_offset = offset + len(line)\n        if next_offset >= cursor_pos:\n            break\n        offset = next_offset\n    else:\n        line = \"\"\n    return (line, offset)\n\ndef token_at_cursor(cell, cursor_pos=0):\n    \"\"\"Get the token at a given cursor\n    \n    Used for introspection.\n    \n    Function calls are prioritized, so the token for the callable will be returned\n    if the cursor is anywhere inside the call.\n    \n    Parameters\n    ----------\n    \n    cell : unicode\n        A block of Python code\n    cursor_pos : int\n        The location of the cursor in the block where the token should be found\n    \"\"\"\n    cell = cast_unicode_py2(cell)\n    names = []\n    tokens = []\n    offset = 0\n    call_names = []\n    for tup in generate_tokens(StringIO(cell).readline):\n        \n        tok = Token(*tup)\n        \n        # token, text, start, end, line = tup\n        start_col = tok.start[1]\n        end_col = tok.end[1]\n        # allow '|foo' to find 'foo' at the beginning of a line\n        boundary = cursor_pos + 1 if start_col == 0 else cursor_pos\n        if offset + start_col >= boundary:\n            # current token starts after the cursor,\n            # don't consume it\n            break\n        \n        if tok.token == tokenize2.NAME and not iskeyword(tok.text):\n            if names and tokens and tokens[-1].token == tokenize2.OP and tokens[-1].text == '.':\n                names[-1] = \"%s.%s\" % (names[-1], tok.text)\n            else:\n                names.append(tok.text)\n        elif tok.token == tokenize2.OP:\n            if tok.text == '=' and names:\n                # don't inspect the lhs of an assignment\n                names.pop(-1)\n            if tok.text == '(' and names:\n                # if we are inside a function call, inspect the function\n                call_names.append(names[-1])\n            elif tok.text == ')' and call_names:\n                call_names.pop(-1)\n        \n        if offset + end_col > cursor_pos:\n            # we found the cursor, stop reading\n            break\n        \n        tokens.append(tok)\n        if tok.token in (tokenize2.NEWLINE, tokenize2.NL):\n            offset += len(tok.line)\n    \n    if call_names:\n        return call_names[-1]\n    elif names:\n        return names[-1]\n    else:\n        return ''\n    \n\n", "path": "IPython/utils/tokenutil.py"}]}