We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Source map lookups wrong when location is first position in state array
Failing test here: https://github.com/getsentry/sentry/commit/289e4e664769173b3b9ef7eb34c3e2576a2a543f

Source of bug in [sentry.lang.javascript.sourcemaps#L158](https://github.com/getsentry/sentry/blob/master/src/sentry/lang/javascript/sourcemaps.py#L158):

``` python
def find_source(indexed_sourcemap, lineno, colno):
    # error says "line no 1, column no 56"
    assert lineno > 0, 'line numbers are 1-indexed'
    return indexed_sourcemap.states[bisect.bisect_left(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]
```

Fails because `bisect_left` will return the index to the left of a match if there is an exact match. In this test case, the match is the first state `(0, 0)`, after which we subtract `1` and access the array at location `-1` ... which is the last element in the array.

Me debugging the test case in pdb:

```
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
> sentry/src/sentry/lang/javascript/sourcemaps.py(157)find_source()
-> assert lineno > 0, 'line numbers are 1-indexed'
(Pdb) lineno
1
(Pdb) colno
0
(Pdb) bisect.bisect_left(indexed_sourcemap.keys, (lineno - 1, colno)) - 1
-1
(Pdb) indexed_sourcemap.keys
[(0, 0), (0, 8), (0, 13), (0, 15), ..., (0, 168), (0, 174), (0, 191)]
(Pdb) indexed_sourcemap.states[-1]
SourceMap(dst_line=0, dst_col=191, src='foo/file2.js', src_line=9, src_col=25, name='e')
```

---

It appears that @mattrobenolt's python-sourcemap [implementation](https://github.com/mattrobenolt/python-sourcemap/blob/master/sourcemap/objects.py#L70) uses `bisect_right`, but I haven't investigated to see if the bug is present there.


--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `src/sentry/lang/javascript/sourcemaps.py`
Content:
```
1 """
2 sentry.utils.sourcemaps
3 ~~~~~~~~~~~~~~~~~~~~~~~
4 
5 Originally based on https://github.com/martine/python-sourcemap
6 
7 :copyright: (c) 2010-2014 by the Sentry Team, see AUTHORS for more details.
8 :license: BSD, see LICENSE for more details.
9 """
10 from __future__ import absolute_import
11 
12 import bisect
13 
14 from collections import namedtuple
15 from urlparse import urljoin
16 
17 from sentry.utils import json
18 
19 
20 SourceMap = namedtuple('SourceMap', ['dst_line', 'dst_col', 'src', 'src_line', 'src_col', 'name'])
21 SourceMapIndex = namedtuple('SourceMapIndex', ['states', 'keys', 'sources', 'content'])
22 
23 # Mapping of base64 letter -> integer value.
24 B64 = dict(
25     (c, i) for i, c in
26     enumerate('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/')
27 )
28 
29 
30 def parse_vlq(segment):
31     """
32     Parse a string of VLQ-encoded data.
33 
34     Returns:
35       a list of integers.
36     """
37 
38     values = []
39 
40     cur, shift = 0, 0
41     for c in segment:
42         val = B64[c]
43         # Each character is 6 bits:
44         # 5 of value and the high bit is the continuation.
45         val, cont = val & 0b11111, val >> 5
46         cur += val << shift
47         shift += 5
48 
49         if not cont:
50             # The low bit of the unpacked value is the sign.
51             cur, sign = cur >> 1, cur & 1
52             if sign:
53                 cur = -cur
54             values.append(cur)
55             cur, shift = 0, 0
56 
57     if cur or shift:
58         raise Exception('leftover cur/shift in vlq decode')
59 
60     return values
61 
62 
63 def parse_sourcemap(smap):
64     """
65     Given a sourcemap json object, yield SourceMap objects as they are read from it.
66     """
67     sources = smap['sources']
68     sourceRoot = smap.get('sourceRoot')
69     names = smap.get('names', [])
70     mappings = smap['mappings']
71     lines = mappings.split(';')
72 
73     if sourceRoot:
74         # turn /foo/bar into /foo/bar/ so urljoin doesnt strip the last path
75         if not sourceRoot.endswith('/'):
76             sourceRoot = sourceRoot + '/'
77 
78         sources = [
79             urljoin(sourceRoot, src)
80             for src in sources
81         ]
82 
83     dst_col, src_id, src_line, src_col, name_id = 0, 0, 0, 0, 0
84     for dst_line, line in enumerate(lines):
85         segments = line.split(',')
86         dst_col = 0
87         for segment in segments:
88             if not segment:
89                 continue
90             parse = parse_vlq(segment)
91             dst_col += parse[0]
92 
93             src = None
94             name = None
95             if len(parse) > 1:
96                 src_id += parse[1]
97                 src = sources[src_id]
98                 src_line += parse[2]
99                 src_col += parse[3]
100 
101                 if len(parse) > 4:
102                     name_id += parse[4]
103                     name = names[name_id]
104 
105             assert dst_line >= 0
106             assert dst_col >= 0
107             assert src_line >= 0
108             assert src_col >= 0
109 
110             yield SourceMap(dst_line, dst_col, src, src_line, src_col, name)
111 
112 
113 def sourcemap_to_index(sourcemap):
114     smap = json.loads(sourcemap)
115 
116     state_list = []
117     key_list = []
118     src_list = set()
119     content = {}
120     sourceRoot = smap.get('sourceRoot')
121 
122     # turn /foo/bar into /foo/bar/ so urljoin doesnt strip the last path
123     if sourceRoot and not sourceRoot.endswith('/'):
124         sourceRoot = sourceRoot + '/'
125 
126     if smap.get('sourcesContent'):
127         for idx, source in enumerate(smap['sources']):
128             # Ensure we handle null files that may be specified outside of
129             # sourcesContent
130             try:
131                 value = smap['sourcesContent'][idx]
132             except IndexError:
133                 continue
134 
135             if value is None:
136                 continue
137 
138             # Apply the root to the source before shoving into the index
139             # so we can look it up correctly later
140             source = urljoin(sourceRoot, source)
141             content[source] = value.split('\n')
142 
143     for state in parse_sourcemap(smap):
144         state_list.append(state)
145         key_list.append((state.dst_line, state.dst_col))
146 
147         # Apparently it's possible to not have a src
148         # specified in the vlq segments
149         if state.src is not None:
150             src_list.add(state.src)
151 
152     return SourceMapIndex(state_list, key_list, src_list, content)
153 
154 
155 def find_source(indexed_sourcemap, lineno, colno):
156     # error says "line no 1, column no 56"
157     assert lineno > 0, 'line numbers are 1-indexed'
158     return indexed_sourcemap.states[bisect.bisect_left(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]
159
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/src/sentry/lang/javascript/sourcemaps.py b/src/sentry/lang/javascript/sourcemaps.py
--- a/src/sentry/lang/javascript/sourcemaps.py
+++ b/src/sentry/lang/javascript/sourcemaps.py
@@ -155,4 +155,5 @@
 def find_source(indexed_sourcemap, lineno, colno):
     # error says "line no 1, column no 56"
     assert lineno > 0, 'line numbers are 1-indexed'
-    return indexed_sourcemap.states[bisect.bisect_left(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]
+
+    return indexed_sourcemap.states[bisect.bisect_right(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]

{"golden_diff": "diff --git a/src/sentry/lang/javascript/sourcemaps.py b/src/sentry/lang/javascript/sourcemaps.py\n--- a/src/sentry/lang/javascript/sourcemaps.py\n+++ b/src/sentry/lang/javascript/sourcemaps.py\n@@ -155,4 +155,5 @@\n def find_source(indexed_sourcemap, lineno, colno):\n     # error says \"line no 1, column no 56\"\n     assert lineno > 0, 'line numbers are 1-indexed'\n-    return indexed_sourcemap.states[bisect.bisect_left(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]\n+\n+    return indexed_sourcemap.states[bisect.bisect_right(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]\n", "issue": "Source map lookups wrong when location is first position in state array\nFailing test here: https://github.com/getsentry/sentry/commit/289e4e664769173b3b9ef7eb34c3e2576a2a543f\n\nSource of bug in [sentry.lang.javascript.sourcemaps#L158](https://github.com/getsentry/sentry/blob/master/src/sentry/lang/javascript/sourcemaps.py#L158):\n\n``` python\ndef find_source(indexed_sourcemap, lineno, colno):\n    # error says \"line no 1, column no 56\"\n    assert lineno > 0, 'line numbers are 1-indexed'\n    return indexed_sourcemap.states[bisect.bisect_left(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]\n```\n\nFails because `bisect_left` will return the index to the left of a match if there is an exact match. In this test case, the match is the first state `(0, 0)`, after which we subtract `1` and access the array at location `-1` ... which is the last element in the array.\n\nMe debugging the test case in pdb:\n\n```\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>\n> sentry/src/sentry/lang/javascript/sourcemaps.py(157)find_source()\n-> assert lineno > 0, 'line numbers are 1-indexed'\n(Pdb) lineno\n1\n(Pdb) colno\n0\n(Pdb) bisect.bisect_left(indexed_sourcemap.keys, (lineno - 1, colno)) - 1\n-1\n(Pdb) indexed_sourcemap.keys\n[(0, 0), (0, 8), (0, 13), (0, 15), ..., (0, 168), (0, 174), (0, 191)]\n(Pdb) indexed_sourcemap.states[-1]\nSourceMap(dst_line=0, dst_col=191, src='foo/file2.js', src_line=9, src_col=25, name='e')\n```\n\n---\n\nIt appears that @mattrobenolt's python-sourcemap [implementation](https://github.com/mattrobenolt/python-sourcemap/blob/master/sourcemap/objects.py#L70) uses `bisect_right`, but I haven't investigated to see if the bug is present there.\n\n", "before_files": [{"content": "\"\"\"\nsentry.utils.sourcemaps\n~~~~~~~~~~~~~~~~~~~~~~~\n\nOriginally based on https://github.com/martine/python-sourcemap\n\n:copyright: (c) 2010-2014 by the Sentry Team, see AUTHORS for more details.\n:license: BSD, see LICENSE for more details.\n\"\"\"\nfrom __future__ import absolute_import\n\nimport bisect\n\nfrom collections import namedtuple\nfrom urlparse import urljoin\n\nfrom sentry.utils import json\n\n\nSourceMap = namedtuple('SourceMap', ['dst_line', 'dst_col', 'src', 'src_line', 'src_col', 'name'])\nSourceMapIndex = namedtuple('SourceMapIndex', ['states', 'keys', 'sources', 'content'])\n\n# Mapping of base64 letter -> integer value.\nB64 = dict(\n    (c, i) for i, c in\n    enumerate('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/')\n)\n\n\ndef parse_vlq(segment):\n    \"\"\"\n    Parse a string of VLQ-encoded data.\n\n    Returns:\n      a list of integers.\n    \"\"\"\n\n    values = []\n\n    cur, shift = 0, 0\n    for c in segment:\n        val = B64[c]\n        # Each character is 6 bits:\n        # 5 of value and the high bit is the continuation.\n        val, cont = val & 0b11111, val >> 5\n        cur += val << shift\n        shift += 5\n\n        if not cont:\n            # The low bit of the unpacked value is the sign.\n            cur, sign = cur >> 1, cur & 1\n            if sign:\n                cur = -cur\n            values.append(cur)\n            cur, shift = 0, 0\n\n    if cur or shift:\n        raise Exception('leftover cur/shift in vlq decode')\n\n    return values\n\n\ndef parse_sourcemap(smap):\n    \"\"\"\n    Given a sourcemap json object, yield SourceMap objects as they are read from it.\n    \"\"\"\n    sources = smap['sources']\n    sourceRoot = smap.get('sourceRoot')\n    names = smap.get('names', [])\n    mappings = smap['mappings']\n    lines = mappings.split(';')\n\n    if sourceRoot:\n        # turn /foo/bar into /foo/bar/ so urljoin doesnt strip the last path\n        if not sourceRoot.endswith('/'):\n            sourceRoot = sourceRoot + '/'\n\n        sources = [\n            urljoin(sourceRoot, src)\n            for src in sources\n        ]\n\n    dst_col, src_id, src_line, src_col, name_id = 0, 0, 0, 0, 0\n    for dst_line, line in enumerate(lines):\n        segments = line.split(',')\n        dst_col = 0\n        for segment in segments:\n            if not segment:\n                continue\n            parse = parse_vlq(segment)\n            dst_col += parse[0]\n\n            src = None\n            name = None\n            if len(parse) > 1:\n                src_id += parse[1]\n                src = sources[src_id]\n                src_line += parse[2]\n                src_col += parse[3]\n\n                if len(parse) > 4:\n                    name_id += parse[4]\n                    name = names[name_id]\n\n            assert dst_line >= 0\n            assert dst_col >= 0\n            assert src_line >= 0\n            assert src_col >= 0\n\n            yield SourceMap(dst_line, dst_col, src, src_line, src_col, name)\n\n\ndef sourcemap_to_index(sourcemap):\n    smap = json.loads(sourcemap)\n\n    state_list = []\n    key_list = []\n    src_list = set()\n    content = {}\n    sourceRoot = smap.get('sourceRoot')\n\n    # turn /foo/bar into /foo/bar/ so urljoin doesnt strip the last path\n    if sourceRoot and not sourceRoot.endswith('/'):\n        sourceRoot = sourceRoot + '/'\n\n    if smap.get('sourcesContent'):\n        for idx, source in enumerate(smap['sources']):\n            # Ensure we handle null files that may be specified outside of\n            # sourcesContent\n            try:\n                value = smap['sourcesContent'][idx]\n            except IndexError:\n                continue\n\n            if value is None:\n                continue\n\n            # Apply the root to the source before shoving into the index\n            # so we can look it up correctly later\n            source = urljoin(sourceRoot, source)\n            content[source] = value.split('\\n')\n\n    for state in parse_sourcemap(smap):\n        state_list.append(state)\n        key_list.append((state.dst_line, state.dst_col))\n\n        # Apparently it's possible to not have a src\n        # specified in the vlq segments\n        if state.src is not None:\n            src_list.add(state.src)\n\n    return SourceMapIndex(state_list, key_list, src_list, content)\n\n\ndef find_source(indexed_sourcemap, lineno, colno):\n    # error says \"line no 1, column no 56\"\n    assert lineno > 0, 'line numbers are 1-indexed'\n    return indexed_sourcemap.states[bisect.bisect_left(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]\n", "path": "src/sentry/lang/javascript/sourcemaps.py"}], "after_files": [{"content": "\"\"\"\nsentry.utils.sourcemaps\n~~~~~~~~~~~~~~~~~~~~~~~\n\nOriginally based on https://github.com/martine/python-sourcemap\n\n:copyright: (c) 2010-2014 by the Sentry Team, see AUTHORS for more details.\n:license: BSD, see LICENSE for more details.\n\"\"\"\nfrom __future__ import absolute_import\n\nimport bisect\n\nfrom collections import namedtuple\nfrom urlparse import urljoin\n\nfrom sentry.utils import json\n\n\nSourceMap = namedtuple('SourceMap', ['dst_line', 'dst_col', 'src', 'src_line', 'src_col', 'name'])\nSourceMapIndex = namedtuple('SourceMapIndex', ['states', 'keys', 'sources', 'content'])\n\n# Mapping of base64 letter -> integer value.\nB64 = dict(\n    (c, i) for i, c in\n    enumerate('ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/')\n)\n\n\ndef parse_vlq(segment):\n    \"\"\"\n    Parse a string of VLQ-encoded data.\n\n    Returns:\n      a list of integers.\n    \"\"\"\n\n    values = []\n\n    cur, shift = 0, 0\n    for c in segment:\n        val = B64[c]\n        # Each character is 6 bits:\n        # 5 of value and the high bit is the continuation.\n        val, cont = val & 0b11111, val >> 5\n        cur += val << shift\n        shift += 5\n\n        if not cont:\n            # The low bit of the unpacked value is the sign.\n            cur, sign = cur >> 1, cur & 1\n            if sign:\n                cur = -cur\n            values.append(cur)\n            cur, shift = 0, 0\n\n    if cur or shift:\n        raise Exception('leftover cur/shift in vlq decode')\n\n    return values\n\n\ndef parse_sourcemap(smap):\n    \"\"\"\n    Given a sourcemap json object, yield SourceMap objects as they are read from it.\n    \"\"\"\n    sources = smap['sources']\n    sourceRoot = smap.get('sourceRoot')\n    names = smap.get('names', [])\n    mappings = smap['mappings']\n    lines = mappings.split(';')\n\n    if sourceRoot:\n        # turn /foo/bar into /foo/bar/ so urljoin doesnt strip the last path\n        if not sourceRoot.endswith('/'):\n            sourceRoot = sourceRoot + '/'\n\n        sources = [\n            urljoin(sourceRoot, src)\n            for src in sources\n        ]\n\n    dst_col, src_id, src_line, src_col, name_id = 0, 0, 0, 0, 0\n    for dst_line, line in enumerate(lines):\n        segments = line.split(',')\n        dst_col = 0\n        for segment in segments:\n            if not segment:\n                continue\n            parse = parse_vlq(segment)\n            dst_col += parse[0]\n\n            src = None\n            name = None\n            if len(parse) > 1:\n                src_id += parse[1]\n                src = sources[src_id]\n                src_line += parse[2]\n                src_col += parse[3]\n\n                if len(parse) > 4:\n                    name_id += parse[4]\n                    name = names[name_id]\n\n            assert dst_line >= 0\n            assert dst_col >= 0\n            assert src_line >= 0\n            assert src_col >= 0\n\n            yield SourceMap(dst_line, dst_col, src, src_line, src_col, name)\n\n\ndef sourcemap_to_index(sourcemap):\n    smap = json.loads(sourcemap)\n\n    state_list = []\n    key_list = []\n    src_list = set()\n    content = {}\n    sourceRoot = smap.get('sourceRoot')\n\n    # turn /foo/bar into /foo/bar/ so urljoin doesnt strip the last path\n    if sourceRoot and not sourceRoot.endswith('/'):\n        sourceRoot = sourceRoot + '/'\n\n    if smap.get('sourcesContent'):\n        for idx, source in enumerate(smap['sources']):\n            # Ensure we handle null files that may be specified outside of\n            # sourcesContent\n            try:\n                value = smap['sourcesContent'][idx]\n            except IndexError:\n                continue\n\n            if value is None:\n                continue\n\n            # Apply the root to the source before shoving into the index\n            # so we can look it up correctly later\n            source = urljoin(sourceRoot, source)\n            content[source] = value.split('\\n')\n\n    for state in parse_sourcemap(smap):\n        state_list.append(state)\n        key_list.append((state.dst_line, state.dst_col))\n\n        # Apparently it's possible to not have a src\n        # specified in the vlq segments\n        if state.src is not None:\n            src_list.add(state.src)\n\n    return SourceMapIndex(state_list, key_list, src_list, content)\n\n\ndef find_source(indexed_sourcemap, lineno, colno):\n    # error says \"line no 1, column no 56\"\n    assert lineno > 0, 'line numbers are 1-indexed'\n\n    return indexed_sourcemap.states[bisect.bisect_right(indexed_sourcemap.keys, (lineno - 1, colno)) - 1]\n", "path": "src/sentry/lang/javascript/sourcemaps.py"}]}