This is a Python library for efficiently tracking span information while parsing source code, and generating errors on those spans.
I intend to use it in my rewrite of mypy's Python parser to add column tracking and better diagnostics, but this code could be used by any parser.
I am using PEP 484 type hinting (which can be checked by mypy itself).
If you want to run this code:
git clone git://github.com/o11c/mypy.git -b syntax
You'll need to add lib-typing/3.2 to PYTHONPATH, or else run ./travis.py span to run all matching tests.
File: mypy/syntax/span.py
"""Utility classes needed to efficiently store location info.
Significant care is taken here to ensure minimal memory usage.
Absolutely nothing in this module is specific to the language being parsed.
"""
from typing import (
Any,
Callable,
Dict,
Generic,
IO,
Iterable,
List,
Optional,
Tuple,
TypeVar,
Union,
)
from abc import abstractmethod, ABCMeta
from bisect import bisect_right
T = TypeVar('T')
class EnsureSlotsMeta(type):
"""Metaclass to ensure that subclasses can't omit `__slots__`.
There will be a *lot* of the objects during parsing ...
"""
# Not annotated because mypy gets *really* confused with metaclasses.
def __new__(mcls, name, bases, dct):
slots = dct.setdefault('__slots__', ())
if isinstance(slots, str):
slots = (slots,)
dct['__slots__'] = slots
return type.__new__(mcls, name, bases, dct)
def _all_slots(cls):
rv = []
for clz in cls.mro()[:-1]:
rv.extend(clz.__slots__)
return rv
class Span(tuple):
"""Source locations, packed as an immutable pair of integers.
In order to support empty spans, `end` must be exclusive.
See `CodeMap` for how to interpret this.
"""
__slots__ = ()
@property
def begin(self) -> int:
return self[0]
@property
def end(self) -> int:
return self[1]
def __new__(cls: type, begin: int, end) -> 'Span':
assert begin <= end
return tuple.__new__(Span, (begin, end)) # type: ignore
@staticmethod
def make(begin: 'Span', end: 'Span') -> 'Span':
return Span(begin.begin, end.end)
if False:
# mypy doesn't support __new__ yet.
def __init__(self, begin: int, end: int) -> None:
...
class HasSpan(metaclass=EnsureSlotsMeta):
"""Base class for everything that has a location for reporting errors."""
__slots__ = ('_span')
def __init__(self, span: Span) -> None:
self._span = span
# TODO put blank Node/Tree/Token/BaseComment/EmptyToken/Eof classes here.
#
# Below this point, objects are either rare or short-lived.
#
class HumanLocation:
"""A human-readable location.
These should *not* be long-lived!
"""
__slots__ = ('filename', 'line', 'column', 'width', 'text')
def __init__(self, filename: str, line: int, column: int, width: int, text: str) -> None:
self.filename = filename
self.line = line
self.column = column
self.width = width
self.text = text
def caret(self) -> str:
# TODO fix off-by-one errors EVERYWHERE, this needs unit tests bad!
width = self.width - 1
column = self.column
max_width = len(self.text) + 1 - column
head = ' ' * (column - 1) + '^'
tail = ''
if width > max_width:
width = max_width
tail = ' ...'
return head + ('~' * width) + tail
def _as_tuple(self) -> Tuple[str, int, int, int, str]:
return (
self.filename,
self.line,
self.column,
self.width,
self.text,
)
def __repr__(self):
return 'HumanLocation(%r, %r, %r, %r, %r)' % self._as_tuple()
def __eq__(self, other):
return self._as_tuple() == other._as_tuple()
def __ne__(self, other):
return not (self == other)
# acceptable values for `level`.
DIAG_NOTE = 'note'
DIAG_WARNING = 'warning'
DIAG_ERROR = 'error'
class SingleDiagnostic:
"""A single diagnostic message, attached to a span.
Not intended to be constructed directly.
"""
__slots__ = ('location', 'level', 'message')
def __init__(self, location: HumanLocation, level: str, message: str) -> None:
self.location = location
self.level = level
self.message = message
def format(self) -> str:
file = self.location.filename
line = self.location.line
column = self.location.column
level = self.level
message = self.message
return '%s:%s:%s: %s: %s' % (file, line, column, level, message)
class MultipleDiagnostics:
"""A sequence of related diagnostics messages.
Not intended to be constructed directly.
"""
__slots__ = ('pre', 'main', 'post', 'option')
def __init__(self, pre: List[SingleDiagnostic], main: SingleDiagnostic, post: List[SingleDiagnostic], option: Optional[str]) -> None:
# Typically, `pre` is used for "in this context"
# and `post` is used for "look at this instead".
self.pre = pre
self.main = main
self.post = post
self.option = option
class ErrorStream(metaclass=ABCMeta):
"""Abstract base class for a sink for diagnostic messages.
Despite the name, not all might be errors.
"""
__slots__ = ()
@abstractmethod
def emit(self, error: MultipleDiagnostics) -> None:
pass
class FileErrorStream(ErrorStream):
"""Implementation of an error stream that writes to a file-like object.
The main diagnostic is written with a copy of the line text and a caret.
"""
# TODO color?
__slots__ = ('stream',)
def __init__(self, stream: IO[str]) -> None:
self.stream = stream
def emit(self, error: MultipleDiagnostics) -> None:
for d in error.pre:
msg = d.format()
self.stream.writelines([msg, '\n'])
if error.option:
d = error.main
msg = d.format()
self.stream.writelines([msg, ' [', error.option, ']\n'])
else:
d = error.main
msg = d.format()
self.stream.writelines([msg, '\n'])
msg = d.location.text
caret = d.location.caret()
self.stream.writelines([msg, '\n', caret, '\n'])
for d in error.post:
msg = d.format()
self.stream.writelines([msg, '\n'])
class Bisector(Generic[T]):
"""Append-only implementation of range_map.
Objects are appended with a size. Any index can then be looked up
to show which object it's in, where in it, and the bounds of the object.
"""
__slots__ = ('offsets', 'data')
def __init__(self):
self.offsets = [0]
self.data = [] # type: List[T]
def add(self, length: int, value: T) -> None:
# TODO should this return start offset?
assert length > 0
self.offsets.append(self.offsets[-1] + length)
self.data.append(value)
def lookup(self, offset: int) -> Tuple[T, int, int, int]:
if not (0 <= offset < self.offsets[-1]):
raise KeyError(offset)
index = bisect_right(self.offsets, offset)
assert self.offsets[index - 1] <= offset < self.offsets[index]
data = self.data[index - 1]
soff = self.offsets[index - 1]
eoff = self.offsets[index]
# Technically this is redundant, but it keeps callers simpler.
return (data, offset - soff, soff, eoff)
# TODO provide a way to drop the content, in which case `HumanLocation` will
# have `text=None`. Possibly even drop the line numbers?
class FileInfo:
"""Information about a single source file.
Contains the name, entire contents, and line map.
"""
__slots__ = ('name', 'content', 'lines')
def __init__(self, name: str, content: str) -> None:
self.name = name
self.content = content
lines = self.lines = Bisector() # type: Bisector[int]
assert content.endswith('\n')
sol = 0
eof = len(content)
last_nl = len(content) - 1
line_no = 1
while sol != eof:
next_sol = content.find('\n', sol) + 1
delta = next_sol - sol
lines.add(delta, line_no)
sol = next_sol
line_no += 1
def lookup(self, offset: int) -> Tuple[int, int, int, int]:
if offset == len(self.content):
return (len(self.lines.offsets), 0, offset, offset)
# returns `(line, raw column, sol, eol)`
return self.lines.lookup(offset)
class CodeMap:
"""Keep track of all the sources.
Typically there is only one of these at a time.
"""
__slots__ = ('errors', 'files')
def __init__(self, errors: Optional[ErrorStream] = None) -> None:
if errors is None:
import sys
errors = FileErrorStream(sys.stderr)
self.errors = errors
self.files = Bisector() # type: Bisector[FileInfo]
def add(self, name: str, content: str):
# Canonicalize line endings to `'\n'` for simplicity.
# Make sure that there is a `'\n'` at EOF (and forbid empty files).
# Note that tabs are *not* canonicalized here.
content = content.replace('\r\n', '\n').replace('\r', '\n')
if not content.endswith('\n'):
content += '\n'
self.files.add(len(content) + 1, FileInfo(name, content))
def lookup(self, span: Span) -> HumanLocation:
file, file_offset, sof, eof = self.files.lookup(span.begin)
line, line_offset, sol, eol = file.lookup(file_offset)
file_size = eof - sof
line_size = eol - sol
filename = file.name
# TODO use the `wcwidth` module to correctly calculate the display
# width of two-column (mostly Asian) and combining characters.
column = line_offset + 1
width = span.end - span.begin
if file_offset + width >= file_size:
# Note, this is the *adjusted* file size, i.e. including EOF.
raise KeyError(span)
# Negative slicing (at EOF only) is the same as empty in python.
text = file.content[sol:eol-1]
return HumanLocation(filename, line, column, width, text)
def emit_multiple(self, diags: MultipleDiagnostics) -> None:
self.errors.emit(diags)
def emit_one(self, diag: SingleDiagnostic) -> None:
self.emit_multiple(MultipleDiagnostics([], diag, [], None))
# The below convenience functions may change as error-reporting grows.
# In particular, they should probably take advantage of `HasSpan`.
def diag(self, location: Span, level: str, message: str, option: str = None, pre: List[Tuple[Span, str]] = [], post: List[Tuple[Span, str]] = []) -> None:
pres = [SingleDiagnostic(self.lookup(sp), 'note', m) for (sp, m) in pre]
main = SingleDiagnostic(self.lookup(location), level, message)
posts = [SingleDiagnostic(self.lookup(sp), 'note', m) for (sp, m) in post]
self.emit_multiple(MultipleDiagnostics(pres, main, posts, option))
def error(self, location: Span, message: str, option: str = None, pre: List[Tuple[Span, str]] = [], post: List[Tuple[Span, str]] = []) -> None:
self.diag(location, 'error', message, option, pre, post)
def warning(self, location: Span, message: str, option: str = None, pre: List[Tuple[Span, str]] = [], post: List[Tuple[Span, str]] = []) -> None:
self.diag(location, 'warning', message, option, pre, post)
# Planned: an option manager that automatically calls error, warning,
# or nothing, as appropriate for the flags passed on the command-line.
# Flags may be -Wno-foo, -Wfoo, or -Werror=foo. Each flag has a default,
# which may be an expression, e.g. default -Wfoo = (-Wextra or -Wunused).
# Doing it this way is important so that -Wno-foo -Wextra DTRT.
# Note that there will always be errors (but not warnings) that are not
# controlled by any option.
File: mypy/syntax/test/test_span.py
from io import StringIO
import typing
from mypy.myunit import Suite, assert_equal, assert_raises
from mypy.syntax.span import (
Bisector,
CodeMap,
ErrorStream,
FileErrorStream,
MultipleDiagnostics,
HumanLocation,
Span,
)
class ForbidErrorStream(ErrorStream):
def emit(self, error: MultipleDiagnostics) -> None:
raise ValueError(error)
def CM() -> CodeMap:
return CodeMap(ForbidErrorStream())
class BisectorSuite(Suite):
def test_empty(self):
b = Bisector() # type: Bisector[str]
assert_raises(KeyError, -2, b.lookup, [-2])
assert_raises(KeyError, -1, b.lookup, [-1])
assert_raises(KeyError, 0, b.lookup, [0])
assert_raises(KeyError, 1, b.lookup, [1])
def test_single(self):
b = Bisector() # type: Bisector[str]
b.add(3, 'hello')
assert_raises(KeyError, -2, b.lookup, [-2])
assert_raises(KeyError, -1, b.lookup, [-1])
assert_equal(b.lookup(0), ('hello', 0, 0, 3))
assert_equal(b.lookup(1), ('hello', 1, 0, 3))
assert_equal(b.lookup(2), ('hello', 2, 0, 3))
assert_raises(KeyError, 3, b.lookup, [3])
assert_raises(KeyError, 4, b.lookup, [4])
def test_double(self):
b = Bisector() # type: Bisector[str]
b.add(3, 'hello')
b.add(4, 'world')
assert_raises(KeyError, -2, b.lookup, [-2])
assert_raises(KeyError, -1, b.lookup, [-1])
assert_equal(b.lookup(0), ('hello', 0, 0, 3))
assert_equal(b.lookup(1), ('hello', 1, 0, 3))
assert_equal(b.lookup(2), ('hello', 2, 0, 3))
assert_equal(b.lookup(3), ('world', 0, 3, 7))
assert_equal(b.lookup(4), ('world', 1, 3, 7))
assert_equal(b.lookup(5), ('world', 2, 3, 7))
assert_equal(b.lookup(6), ('world', 3, 3, 7))
assert_raises(KeyError, 7, b.lookup, [7])
assert_raises(KeyError, 8, b.lookup, [8])
class CodeMapSuite(Suite):
def test_no_file(self):
cm = CM()
assert_raises(KeyError, -1, cm.lookup, [Span(-1, -1)])
assert_raises(KeyError, 0, cm.lookup, [Span(0, 0)])
def test_one_empty_file(self):
cm = CM()
cm.add('file1', '')
# text becomes '\n', with two valid locations: at the \n and after.
assert_raises(KeyError, -1, cm.lookup, [Span(-1, -1)])
cm.lookup(Span(0, 0))
cm.lookup(Span(0, 1))
cm.lookup(Span(1, 1))
assert_raises(KeyError, 2, cm.lookup, [Span(2, 2)])
def test_two_empty_files(self):
cm = CM()
cm.add('file1', '')
cm.add('file2', '')
assert_raises(KeyError, -1, cm.lookup, [Span(-1, -1)])
assert_equal(cm.lookup(Span(0, 0)), HumanLocation('file1', 1, 1, 0, ''))
assert_equal(cm.lookup(Span(0, 1)), HumanLocation('file1', 1, 1, 1, ''))
assert_equal(cm.lookup(Span(1, 1)), HumanLocation('file1', 2, 1, 0, ''))
assert_raises(KeyError, Span(1, 2), cm.lookup, [Span(1, 2)])
assert_equal(cm.lookup(Span(2, 2)), HumanLocation('file2', 1, 1, 0, ''))
assert_equal(cm.lookup(Span(2, 3)), HumanLocation('file2', 1, 1, 1, ''))
assert_equal(cm.lookup(Span(3, 3)), HumanLocation('file2', 2, 1, 0, ''))
assert_raises(KeyError, 4, cm.lookup, [Span(4, 4)])
def test_caret(self):
capture = StringIO()
cm = CodeMap(FileErrorStream(capture))
# 0123 4567 8901 2
cm.add('test_caret', 'abc\ndef\nghi\n')
cm.error(Span(4, 4), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:1: error: xyzzy\ndef\n^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(4, 5), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:1: error: xyzzy\ndef\n^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(4, 6), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:1: error: xyzzy\ndef\n^~\n')
capture.seek(0)
capture.truncate()
cm.error(Span(4, 7), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:1: error: xyzzy\ndef\n^~~\n')
capture.seek(0)
capture.truncate()
cm.error(Span(4, 8), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:1: error: xyzzy\ndef\n^~~~\n')
capture.seek(0)
capture.truncate()
cm.error(Span(4, 9), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:1: error: xyzzy\ndef\n^~~~ ...\n')
capture.seek(0)
capture.truncate()
cm.error(Span(5, 5), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:2: error: xyzzy\ndef\n ^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(5, 6), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:2: error: xyzzy\ndef\n ^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(5, 7), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:2: error: xyzzy\ndef\n ^~\n')
capture.seek(0)
capture.truncate()
cm.error(Span(5, 8), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:2: error: xyzzy\ndef\n ^~~\n')
capture.seek(0)
capture.truncate()
cm.error(Span(5, 9), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:2: error: xyzzy\ndef\n ^~~ ...\n')
capture.seek(0)
capture.truncate()
cm.error(Span(6, 6), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:3: error: xyzzy\ndef\n ^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(6, 7), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:3: error: xyzzy\ndef\n ^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(6, 8), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:3: error: xyzzy\ndef\n ^~\n')
capture.seek(0)
capture.truncate()
cm.error(Span(6, 9), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:3: error: xyzzy\ndef\n ^~ ...\n')
capture.seek(0)
capture.truncate()
cm.error(Span(7, 7), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:4: error: xyzzy\ndef\n ^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(7, 8), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:4: error: xyzzy\ndef\n ^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(7, 9), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:2:4: error: xyzzy\ndef\n ^ ...\n')
capture.seek(0)
capture.truncate()
cm.error(Span(8, 8), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:3:1: error: xyzzy\nghi\n^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(11, 11), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:3:4: error: xyzzy\nghi\n ^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(11, 12), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:3:4: error: xyzzy\nghi\n ^\n')
capture.seek(0)
capture.truncate()
cm.error(Span(12, 12), 'xyzzy')
assert_equal(capture.getvalue(), 'test_caret:4:1: error: xyzzy\n\n^\n')
capture.seek(0)
capture.truncate()
def test_context(self):
capture = StringIO()
cm = CodeMap(FileErrorStream(capture))
# 0 1
# 0123456789012
cm.add('ctx1', 'import ctx2')
# 1 2 3
# 3456789012345678901234567
cm.add('ctx2', 'import alt1, main, alt2')
# 3 4
# 890123
cm.add('main', 'oops')
# 4
# 45678
cm.add('alt1', 'foo')
# 45
# 90123
cm.add('alt2', 'bar')
cm.warning(Span(38, 42), 'xyzzy',
option='-Wfoo',
pre=[(Span(7, 11), 'from here'), (Span(26, 30), 'from there')],
post=[(Span(44, 47), 'try this'), (Span(49, 52), 'try that')])
expected = '''\
ctx1:1:8: note: from here
ctx2:1:14: note: from there
main:1:1: warning: xyzzy [-Wfoo]
oops
^~~~
alt1:1:1: note: try this
alt2:1:1: note: try that
'''
assert_equal(capture.getvalue(), expected)
