26408720365

Committed 25 May 2026 03:47PM UTC coverage: 97.379% (-1.5%) from 98.896%

Build # 26408720365

Build Type

Pull #1338

github

Committed by

web-flow

Commit Message

Merge ef449721d into 416c61480

Pull Request Pull Request #1338: Native LazySeq implementation with PyO3

Coverage Stats

1093 of 1113 branches covered (98.2%)

Branch coverage included in aggregate %.

24 of 28 new or added lines in 3 files covered. (85.71%)

1 existing line in 1 file now uncovered.

9162 of 9418 relevant lines covered (97.28%)

0.97 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/src/basilisp/lang/seq/_pyseq.py

import functools
import threading
from typing import Callable, Iterable, TypeVar, overload

from basilisp.lang.interfaces import (
    IPersistentMap,
    ISeq,
    ISeqable,
    ISequential,
    IWithMeta,
)

T = TypeVar("T")


class _EmptySequence(IWithMeta, ISequential, ISeq[T]):
    __slots__ = ("_meta",)

    def __init__(self, meta: IPersistentMap | None = None):
        self._meta = meta

    def __repr__(self):
        return "()"

    def __bool__(self):
        return True

    def seq(self) -> ISeq[T] | None:
        return None

    @property
    def meta(self) -> IPersistentMap | None:
        return self._meta

    def with_meta(self, meta: IPersistentMap | None) -> "_EmptySequence[T]":
        return _EmptySequence(meta=meta)

    @property
    def is_empty(self) -> bool:
        return True

    @property
    def first(self) -> T | None:
        return None

    @property
    def rest(self) -> ISeq[T]:
        return self

    def cons(self, *elems: T) -> ISeq[T]:  # type: ignore[override]
        l: ISeq = self
        for elem in elems:
            l = Cons(elem, l)
        return l

    def empty(self):
        return EMPTY


EMPTY: ISeq = _EmptySequence()


class Cons(ISeq[T], ISequential, IWithMeta):
    __slots__ = ("_first", "_rest", "_meta")

    def __init__(
        self,
        first: T,
        seq: ISeq[T] | None = None,
        meta: IPersistentMap | None = None,
    ) -> None:
        self._first = first
        self._rest = EMPTY if seq is None else seq
        self._meta = meta

    @property
    def is_empty(self) -> bool:
        return False

    @property
    def first(self) -> T | None:
        return self._first

    @property
    def rest(self) -> ISeq[T]:
        return self._rest

    def cons(self, *elems: T) -> "Cons[T]":
        l = self
        for elem in elems:
            l = Cons(elem, l)
        return l

    def empty(self):
        return EMPTY

    @property
    def meta(self) -> IPersistentMap | None:
        return self._meta

    def with_meta(self, meta: IPersistentMap | None) -> "Cons[T]":
        return Cons(self._first, seq=self._rest, meta=meta)


LazySeqGenerator = Callable[[], ISeq[T] | None]


class LazySeq(IWithMeta, ISequential, ISeq[T]):
    """LazySeqs are wrappers for delaying sequence computation. Create a LazySeq
    with a function that can either return None or a Seq. If a Seq is returned,
    the LazySeq is a proxy to that Seq.

    Callers should never provide the `seq` argument -- this is provided only to
    support `with_meta` returning a new LazySeq instance."""

    __slots__ = ("_gen", "_obj", "_seq", "_lock", "_meta")

    def __init__(
        self,
        gen: LazySeqGenerator | None,
        seq: ISeq[T] | None = None,
        *,
        meta: IPersistentMap | None = None,
    ) -> None:
        self._gen: LazySeqGenerator | None = gen
        self._obj: ISeq[T] | None = None
        self._seq: ISeq[T] | None = seq
        self._lock = threading.RLock()
        self._meta = meta

    @property
    def meta(self) -> IPersistentMap | None:
        return self._meta

    def with_meta(self, meta: IPersistentMap | None) -> "LazySeq[T]":
        return LazySeq(None, seq=self.seq(), meta=meta)

    # LazySeqs have a fairly complex inner state, in spite of the simple interface.
    # Calls from Basilisp code should be providing the only generator seed function.
    # Calls to `(seq ...)` cause the LazySeq to cache the generator function locally
    # (as explained in _compute_seq), clear the _gen attribute, and cache the results
    # of that generator function call as _obj. _obj may be None, some other ISeq, or
    # perhaps another LazySeq. Finally, the LazySeq attempts to consume all returned
    # LazySeq objects before calling `(seq ...)` on the result, which is cached in the
    # _seq attribute.

    def _compute_seq(self) -> ISeq[T] | None:
        if self._gen is not None:
            # This local caching of the generator function and clearing of self._gen
            # is absolutely critical for supporting co-recursive lazy sequences.
            #
            # The original example that prompted this change is below:
            #
            #   (def primes (remove
            #                (fn [x] (some #(zero? (mod x %)) primes))
            #                (iterate inc 2)))
            #
            #   (take 5 primes)  ;; => stack overflow
            #
            # If we don't clear self._gen, each successive call to (some ... primes)
            # will end up forcing the primes LazySeq object to call self._gen, rather
            # than caching the results, allowing examination of the partial seq
            # computed up to that point.
            gen = self._gen
            self._gen = None
            self._obj = gen()
        return self._obj if self._obj is not None else self._seq

    def seq(self) -> ISeq[T] | None:
        with self._lock:
            self._compute_seq()
            if self._obj is not None:
                o = self._obj
                self._obj = None
                # Consume any additional lazy sequences returned immediately, so we
                # have a "real" concrete sequence to proxy to.
                #
                # The common idiom with LazySeqs is to return
                # (cons value (lazy-seq ...)) from the generator function, so this will
                # only result in evaluating away instances where _another_ LazySeq is
                # returned rather than a cons cell with a concrete first value. This
                # loop will not consume the LazySeq in the rest position of the cons.
                while isinstance(o, LazySeq):
                    o = o._compute_seq()  # type: ignore
                self._seq = to_seq(o)
            return self._seq

    @property
    def is_empty(self) -> bool:
        return self.seq() is None

    @property
    def first(self) -> T | None:
        if self.is_empty:
            return None
        return self.seq().first  # type: ignore[union-attr]

    @property
    def rest(self) -> "ISeq[T]":
        if self.is_empty:
            return EMPTY
        return self.seq().rest  # type: ignore[union-attr]

    def cons(self, *elems: T) -> ISeq[T]:  # type: ignore[override]
        l: ISeq = self
        for elem in elems:
            l = Cons(elem, l)
        return l

    @property
    def is_realized(self):
        with self._lock:
            return self._gen is None

    def empty(self):
        return EMPTY


def sequence(s: Iterable[T], support_single_use: bool = False) -> ISeq[T]:
    """Create a Sequence from Iterable `s`.

    By default, raise a ``TypeError`` if `s` is a single-use
    Iterable, unless `fail_single_use` is ``True``.

    """
    i = iter(s)

    if not support_single_use and i is s:
        raise TypeError(
            f"Can't create sequence out of single-use iterable object, please use iterator-seq instead. Iterable Object type: {type(s)}"
        )

    def _next_elem() -> ISeq[T]:
        try:
            e = next(i)
        except StopIteration:
            return EMPTY
        else:
            return Cons(e, LazySeq(_next_elem))

    return LazySeq(_next_elem)


@overload
def _seq_or_nil(s: None) -> None: ...


@overload
def _seq_or_nil(s: ISeq) -> ISeq | None: ...


def _seq_or_nil(s):
    """Return None if a ISeq is empty, the ISeq otherwise."""
    if s is None or s.is_empty:
        return None
    return s


@functools.singledispatch
def to_seq(o) -> ISeq | None:
    """Coerce the argument o to a ISeq. If o is None, return None."""
    return _seq_or_nil(sequence(o))


@to_seq.register(type(None))
def _to_seq_none(_) -> None:
    return None


@to_seq.register(ISeq)
def _to_seq_iseq(o: ISeq) -> ISeq | None:
    return _seq_or_nil(o)


@to_seq.register(LazySeq)
def _to_seq_lazyseq(o: LazySeq) -> ISeq | None:
    # Force evaluation of the LazySeq by calling o.seq() directly.
    return o.seq()


@to_seq.register(ISeqable)
def _to_seq_iseqable(o: ISeqable) -> ISeq | None:
    return _seq_or_nil(o.seq())

1	import functools	×
2	import threading	×
NEW 3	from typing import Callable, Iterable, TypeVar, overload	×
4
5	from basilisp.lang.interfaces import (	×
6	IPersistentMap,
7	ISeq,
8	ISeqable,
9	ISequential,
10	IWithMeta,
11	)
12
13	T = TypeVar("T")	×
14
15
16	class _EmptySequence(IWithMeta, ISequential, ISeq[T]):	×
17	__slots__ = ("_meta",)	×
18
19	def __init__(self, meta: IPersistentMap \| None = None):	×
20	self._meta = meta	×
21
22	def __repr__(self):
23	return "()"
24
25	def __bool__(self):	×
26	return True	×
27
28	def seq(self) -> ISeq[T] \| None:	×
29	return None	×
30
31	@property	×
32	def meta(self) -> IPersistentMap \| None:	×
33	return self._meta	×
34
35	def with_meta(self, meta: IPersistentMap \| None) -> "_EmptySequence[T]":	×
36	return _EmptySequence(meta=meta)	×
37
38	@property	×
39	def is_empty(self) -> bool:	×
40	return True	×
41
42	@property	×
43	def first(self) -> T \| None:	×
44	return None	×
45
46	@property	×
47	def rest(self) -> ISeq[T]:	×
48	return self	×
49
50	def cons(self, *elems: T) -> ISeq[T]: # type: ignore[override]	×
51	l: ISeq = self	×
52	for elem in elems:	×
53	l = Cons(elem, l)	×
54	return l	×
55
56	def empty(self):	×
57	return EMPTY	×
58
59
60	EMPTY: ISeq = _EmptySequence()	×
61
62
63	class Cons(ISeq[T], ISequential, IWithMeta):	×
64	__slots__ = ("_first", "_rest", "_meta")	×
65
66	def __init__(	×
67	self,
68	first: T,
69	seq: ISeq[T] \| None = None,
70	meta: IPersistentMap \| None = None,
71	) -> None:
72	self._first = first	×
73	self._rest = EMPTY if seq is None else seq	×
74	self._meta = meta	×
75
76	@property	×
77	def is_empty(self) -> bool:	×
78	return False	×
79
80	@property	×
81	def first(self) -> T \| None:	×
82	return self._first	×
83
84	@property	×
85	def rest(self) -> ISeq[T]:	×
86	return self._rest	×
87
88	def cons(self, *elems: T) -> "Cons[T]":	×
89	l = self	×
90	for elem in elems:	×
91	l = Cons(elem, l)	×
92	return l	×
93
94	def empty(self):	×
95	return EMPTY	×
96
97	@property	×
98	def meta(self) -> IPersistentMap \| None:	×
99	return self._meta	×
100
101	def with_meta(self, meta: IPersistentMap \| None) -> "Cons[T]":	×
102	return Cons(self._first, seq=self._rest, meta=meta)	×
103
104
NEW 105	LazySeqGenerator = Callable[[], ISeq[T] \| None]	×
106
107
108	class LazySeq(IWithMeta, ISequential, ISeq[T]):	×
109	"""LazySeqs are wrappers for delaying sequence computation. Create a LazySeq
110	with a function that can either return None or a Seq. If a Seq is returned,
111	the LazySeq is a proxy to that Seq.
112
113	Callers should never provide the `seq` argument -- this is provided only to
114	support `with_meta` returning a new LazySeq instance."""
115
116	__slots__ = ("_gen", "_obj", "_seq", "_lock", "_meta")	×
117
118	def __init__(	×
119	self,
120	gen: LazySeqGenerator \| None,
121	seq: ISeq[T] \| None = None,
122	*,
123	meta: IPersistentMap \| None = None,
124	) -> None:
125	self._gen: LazySeqGenerator \| None = gen	×
126	self._obj: ISeq[T] \| None = None	×
127	self._seq: ISeq[T] \| None = seq	×
128	self._lock = threading.RLock()	×
129	self._meta = meta	×
130
131	@property	×
132	def meta(self) -> IPersistentMap \| None:	×
133	return self._meta	×
134
135	def with_meta(self, meta: IPersistentMap \| None) -> "LazySeq[T]":	×
136	return LazySeq(None, seq=self.seq(), meta=meta)	×
137
138	# LazySeqs have a fairly complex inner state, in spite of the simple interface.
139	# Calls from Basilisp code should be providing the only generator seed function.
140	# Calls to `(seq ...)` cause the LazySeq to cache the generator function locally
141	# (as explained in _compute_seq), clear the _gen attribute, and cache the results
142	# of that generator function call as _obj. _obj may be None, some other ISeq, or
143	# perhaps another LazySeq. Finally, the LazySeq attempts to consume all returned
144	# LazySeq objects before calling `(seq ...)` on the result, which is cached in the
145	# _seq attribute.
146
147	def _compute_seq(self) -> ISeq[T] \| None:	×
148	if self._gen is not None:	×
149	# This local caching of the generator function and clearing of self._gen
150	# is absolutely critical for supporting co-recursive lazy sequences.
151	#
152	# The original example that prompted this change is below:
153	#
154	# (def primes (remove
155	# (fn [x] (some #(zero? (mod x %)) primes))
156	# (iterate inc 2)))
157	#
158	# (take 5 primes) ;; => stack overflow
159	#
160	# If we don't clear self._gen, each successive call to (some ... primes)
161	# will end up forcing the primes LazySeq object to call self._gen, rather
162	# than caching the results, allowing examination of the partial seq
163	# computed up to that point.
164	gen = self._gen	×
165	self._gen = None	×
166	self._obj = gen()	×
167	return self._obj if self._obj is not None else self._seq	×
168
169	def seq(self) -> ISeq[T] \| None:	×
170	with self._lock:	×
171	self._compute_seq()	×
172	if self._obj is not None:	×
173	o = self._obj	×
174	self._obj = None	×
175	# Consume any additional lazy sequences returned immediately, so we
176	# have a "real" concrete sequence to proxy to.
177	#
178	# The common idiom with LazySeqs is to return
179	# (cons value (lazy-seq ...)) from the generator function, so this will
180	# only result in evaluating away instances where _another_ LazySeq is
181	# returned rather than a cons cell with a concrete first value. This
182	# loop will not consume the LazySeq in the rest position of the cons.
183	while isinstance(o, LazySeq):	×
184	o = o._compute_seq() # type: ignore	×
185	self._seq = to_seq(o)	×
186	return self._seq	×
187
188	@property	×
189	def is_empty(self) -> bool:	×
190	return self.seq() is None	×
191
192	@property	×
193	def first(self) -> T \| None:	×
194	if self.is_empty:	×
195	return None	×
196	return self.seq().first # type: ignore[union-attr]	×
197
198	@property	×
199	def rest(self) -> "ISeq[T]":	×
200	if self.is_empty:	×
201	return EMPTY	×
202	return self.seq().rest # type: ignore[union-attr]	×
203
204	def cons(self, *elems: T) -> ISeq[T]: # type: ignore[override]	×
205	l: ISeq = self	×
206	for elem in elems:	×
207	l = Cons(elem, l)	×
208	return l	×
209
210	@property	×
211	def is_realized(self):	×
212	with self._lock:	×
213	return self._gen is None	×
214
215	def empty(self):	×
216	return EMPTY	×
217
218
219	def sequence(s: Iterable[T], support_single_use: bool = False) -> ISeq[T]:	×
220	"""Create a Sequence from Iterable `s`.
221
222	By default, raise a ``TypeError`` if `s` is a single-use
223	Iterable, unless `fail_single_use` is ``True``.
224
225	"""
226	i = iter(s)	×
227
228	if not support_single_use and i is s:	×
229	raise TypeError(	×
230	f"Can't create sequence out of single-use iterable object, please use iterator-seq instead. Iterable Object type: {type(s)}"
231	)
232
233	def _next_elem() -> ISeq[T]:	×
234	try:	×
235	e = next(i)	×
236	except StopIteration:	×
237	return EMPTY	×
238	else:
239	return Cons(e, LazySeq(_next_elem))	×
240
241	return LazySeq(_next_elem)	×
242
243
244	@overload	×
245	def _seq_or_nil(s: None) -> None: ...	×
246
247
248	@overload	×
249	def _seq_or_nil(s: ISeq) -> ISeq \| None: ...	×
250
251
252	def _seq_or_nil(s):	×
253	"""Return None if a ISeq is empty, the ISeq otherwise."""
254	if s is None or s.is_empty:	×
255	return None	×
256	return s	×
257
258
259	@functools.singledispatch	×
260	def to_seq(o) -> ISeq \| None:	×
261	"""Coerce the argument o to a ISeq. If o is None, return None."""
262	return _seq_or_nil(sequence(o))	×
263
264
265	@to_seq.register(type(None))	×
266	def _to_seq_none(_) -> None:	×
267	return None	×
268
269
270	@to_seq.register(ISeq)	×
271	def _to_seq_iseq(o: ISeq) -> ISeq \| None:	×
272	return _seq_or_nil(o)	×
273
274
275	@to_seq.register(LazySeq)	×
276	def _to_seq_lazyseq(o: LazySeq) -> ISeq \| None:	×
277	# Force evaluation of the LazySeq by calling o.seq() directly.
278	return o.seq()	×
279
280
281	@to_seq.register(ISeqable)	×
282	def _to_seq_iseqable(o: ISeqable) -> ISeq \| None:	×
283	return _seq_or_nil(o.seq())	×

basilisp-lang / basilisp / 26408720365

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous