11.3.2021, 9:00 - 11:00: Due to updates GitLab may be unavailable for some minutes between 09:00 and 11:00.

stringview.py 8.24 KB
Newer Older
1 2
"""cstringview.pyx - a cython-version of the stringview class for speedup
                     slicing strings without copying
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Copyright 2016  by Eckhart Arnold (arnold@badw.de)
                Bavarian Academy of Sciences an Humanities (badw.de)

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
implied.  See the License for the specific language governing
permissions and limitations under the License.

StringView provides string-slicing without copying.
Slicing Python-strings always yields copies of a segment of the original
string. See: https://mail.python.org/pipermail/python-dev/2008-May/079699.html
However, this becomes costly (in terms of space and as a consequence also
time) when parsing longer documents. Unfortunately, Python's `memoryview`
does not work for unicode strings. Hence, the StringView class.
"""
26 27
import collections
from typing import Optional, Iterable, Tuple
28

29
try:
30
    import cython
31
except ImportError:
32 33 34 35 36 37 38
    # from DHParser import foreign_cython as cython
    pass
# needs to be imported because otherwise cython hickups on
# cpdef-functions with cython parameter annotations, like
# cpdef real_indices(begin, end, len: cython.int):
#                                     ^
from DHParser import foreign_cython as cython
39

40
__all__ = ('StringView', 'EMPTY_STRING_VIEW')
41 42 43


@cython.cfunc
Eckhart Arnold's avatar
Eckhart Arnold committed
44
@cython.inline
45 46 47 48 49
def pack_index(index: cython.int, len: cython.int) -> cython.int:
    index = index if index >= 0 else index + len
    return 0 if index < 0 else len if index > len else index


50
@cython.ccall
Eckhart Arnold's avatar
Eckhart Arnold committed
51
@cython.locals(cbegin=cython.int, cend=cython.int)
52 53 54 55 56 57 58 59 60 61 62 63 64 65
def real_indices(begin, end, len: cython.int):
    cbegin = 0 if begin is None else begin
    cend = len if end is None else end
    return pack_index(cbegin, len), pack_index(cend, len)


class StringView(collections.abc.Sized):
    """
    A rudimentary StringView class, just enough for the use cases
    in parser.py. The difference between a StringView and the python
    builtin strings is that StringView-objects do slicing without
    copying, i.e. slices are just a view on a section of the sliced
    string.
    """
Eckhart Arnold's avatar
Eckhart Arnold committed
66
    cython.declare(begin=cython.int, end=cython.int, len=cython.int, fullstring_flag=cython.bint)
67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110
    __slots__ = ['text', 'begin', 'end', 'len', 'fullstring_flag']

    def __init__(self, text: str, begin: Optional[int] = 0, end: Optional[int] = None) -> None:
        self.text = text  # type: str
        self.begin, self.end = real_indices(begin, end, len(text))
        self.len = max(self.end - self.begin, 0)  # type: int
        self.fullstring_flag = (self.begin == 0 and self.len == len(self.text))  # type: bool

    def __bool__(self):
        return self.end > self.begin  # and bool(self.text)

    def __len__(self):
        return self.len

    def __str__(self):
        if self.fullstring_flag:  # optimization: avoid slicing/copying
            return self.text
        # since the slice is being copyied now, anyway, the copy might
        # as well be stored in the string view
        self.text = self.text[self.begin:self.end]
        self.begin = 0
        self.len = len(self.text)
        self.end = self.len
        self.fullstring_flag = True
        return self.text

    def __eq__(self, other):
        return len(other) == len(self) and str(self) == str(other)  # PERFORMANCE WARNING: This creates copies of the strings

    def __hash__(self):
        return hash(str(self))  # PERFORMANCE WARNING: This creates a copy of the string-slice

    def __add__(self, other):
        if isinstance(other, str):
            return (str(self) + other)
        else:
            return StringView(str(self) + str(other))

    def __radd__(self, other):
        if isinstance(other, str):
            return (other + str(self))
        else:
            return StringView(str(other) + str(self))

Eckhart Arnold's avatar
Eckhart Arnold committed
111
    @cython.locals(start=cython.int, stop=cython.int)
112 113 114 115
    def __getitem__(self, index):
        # assert isinstance(index, slice), "As of now, StringView only allows slicing."
        # assert index.step is None or index.step == 1, \
        #     "Step sizes other than 1 are not yet supported by StringView"
Eckhart Arnold's avatar
Eckhart Arnold committed
116 117 118
        # start, stop = real_indices(index.start, index.stop, self.len)
        start = pack_index(0 if index.start is None else index.start, self.len)
        stop = pack_index(self.len if index.stop is None else index.stop, self.len)
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
        return StringView(self.text, self.begin + start, self.begin + stop)

    def count(self, sub, start=None, end=None) -> int:
        if self.fullstring_flag:
            return self.text.count(sub, start, end)
        elif start is None and end is None:
            return self.text.count(sub, self.begin, self.end)
        else:
            start, end = real_indices(start, end, self.len)
            return self.text.count(sub, self.begin + start, self.begin + end)

    def find(self, sub, start=None, end=None) -> int:
        if self.fullstring_flag:
            return self.text.find(sub, start, end)
        elif start is None and end is None:
            return self.text.find(sub, self.begin, self.end) - self.begin
        else:
            start, end = real_indices(start, end, self.len)
            return self.text.find(sub, self.begin + start, self.begin + end) - self.begin

    def rfind(self, sub, start=None, end=None) -> int:
        if self.fullstring_flag:
            return self.text.rfind(sub, start, end)
        if start is None and end is None:
            return self.text.rfind(sub, self.begin, self.end) - self.begin
        else:
            start, end = real_indices(start, end, self.len)
            return self.text.rfind(sub, self.begin + start, self.begin + end) - self.begin

    def startswith(self, prefix: str, start: int = 0, end: Optional[int] = None) -> bool:
        start += self.begin
        end = self.end if end is None else self.begin + end
        return self.text.startswith(prefix, start, end)

    def match(self, regex):
        return regex.match(self.text, pos=self.begin, endpos=self.end)

    def index(self, absolute_index: int) -> int:
        """
        Converts an index for a string watched by a StringView object
        to an index relative to the string view object, e.g.:
        >>> import re
        >>> sv = StringView('xxIxx')[2:3]
        >>> match = sv.match(re.compile('I'))
        >>> match.end()
        3
        >>> sv.index(match.end())
        1
        """
        return absolute_index - self.begin

    def indices(self, absolute_indices: Iterable[int]) -> Tuple[int, ...]:
        """Converts indices for a string watched by a StringView object
        to indices relative to the string view object. See also: `sv_index()`
        """
        return tuple(index - self.begin for index in absolute_indices)

    def search(self, regex):
        return regex.search(self.text, pos=self.begin, endpos=self.end)

Eckhart Arnold's avatar
Eckhart Arnold committed
179
    @cython.locals(begin=cython.int, end=cython.int)
180 181 182 183 184 185 186 187 188 189 190 191 192
    def strip(self):
        if self.fullstring_flag:
            return self.text.strip()
        else:
            begin = self.begin
            end = self.end
            while begin < end and self.text[begin] in ' \n\t':
                begin += 1
            while end > begin and self.text[end] in ' \n\t':
                end -= 1
            return self.text[begin:end]
        # return str(self).strip()  # PERFORMANCE WARNING: This creates a copy of the string

Eckhart Arnold's avatar
Eckhart Arnold committed
193
    @cython.locals(i=cython.int, k=cython.int, l=cython.int)
194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209
    def split(self, sep=None):
        if self.fullstring_flag:
            return self.text.split(sep)
        else:
            pieces = []
            l = len(sep)
            k = 0
            i = self.find(sep, k)
            while i >= 0:
                pieces.append(self.text[self.begin + k : self.begin + i])
                k = i + l
                i = self.find(sep, k)
            pieces.append(self.text[self.begin + k : self.end])
            return pieces
        # return str(self).split(sep, maxsplit)  # PERFORMANCE WARNING: This creates a copy of the string

210

211
EMPTY_STRING_VIEW = StringView('')