1
\$\begingroup\$

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)
\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.