Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# This file is part of Hypothesis, which may be found at
2# https://github.com/HypothesisWorks/hypothesis/
3#
4# Copyright the Hypothesis Authors.
5# Individual contributors are listed in AUTHORS.rst and the git log.
6#
7# This Source Code Form is subject to the terms of the Mozilla Public License,
8# v. 2.0. If a copy of the MPL was not distributed with this file, You can
9# obtain one at https://mozilla.org/MPL/2.0/.
11import abc
12import contextlib
13import math
14import sys
15import warnings
16from collections.abc import Iterable
17from contextlib import AbstractContextManager, contextmanager
18from functools import cached_property
19from random import Random
20from sys import float_info
21from typing import (
22 TYPE_CHECKING,
23 Any,
24 ClassVar,
25 Literal,
26 Optional,
27 TypeAlias,
28 TypedDict,
29 TypeVar,
30)
32from sortedcontainers import SortedSet
34from hypothesis.errors import HypothesisWarning
35from hypothesis.internal.cache import LRUCache
36from hypothesis.internal.compat import WINDOWS, int_from_bytes
37from hypothesis.internal.conjecture.choice import (
38 ChoiceConstraintsT,
39 ChoiceT,
40 ChoiceTypeT,
41 FloatConstraints,
42 choice_constraints_key,
43 choice_permitted,
44)
45from hypothesis.internal.conjecture.floats import lex_to_float
46from hypothesis.internal.conjecture.junkdrawer import bits_to_bytes
47from hypothesis.internal.conjecture.utils import (
48 Sampler,
49 many,
50)
51from hypothesis.internal.constants_ast import (
52 Constants,
53 constants_from_module,
54 is_local_module_file,
55)
56from hypothesis.internal.floats import (
57 SIGNALING_NAN,
58 clamp,
59 float_to_int,
60 make_float_clamper,
61 next_down,
62 next_up,
63)
64from hypothesis.internal.intervalsets import IntervalSet
65from hypothesis.internal.observability import InfoObservationType, TestCaseObservation
66from hypothesis.internal.statistics import (
67 LogStudentTDistribution,
68 PiecewiseDistribution,
69 UniformDistribution,
70)
72if TYPE_CHECKING:
73 from hypothesis.internal.conjecture.data import ConjectureData
74 from hypothesis.internal.constants_ast import ConstantT
76T = TypeVar("T")
77LifetimeT: TypeAlias = Literal["test_case", "test_function"]
78COLLECTION_DEFAULT_MAX_SIZE = 10**10 # "arbitrarily large"
80# see https://github.com/HypothesisWorks/hypothesis/pull/4728 for details
81INTEGERS_DISTRIBUTION = PiecewiseDistribution(
82 inner=UniformDistribution(half_width=256),
83 outer=LogStudentTDistribution(scale_bits=13, df=2),
84 switchover=256,
85)
88#: Registered Hypothesis backends. This is a dictionary where keys are the name
89#: to be used in |settings.backend|. The value of a key can be either:
90#:
91#: * A string corresponding to an importable absolute path of a
92#: |PrimitiveProvider| subclass
93#: * A |PrimitiveProvider| subclass (the class itself, not an instance of the
94#: class)
95#:
96#: Hypothesis will instantiate the corresponding |PrimitiveProvider| subclass
97#: when the backend is requested by a test's |settings.backend| value.
98#:
99#: For example, the default Hypothesis backend is registered as:
100#:
101#: .. code-block:: python
102#:
103#: from hypothesis.internal.conjecture.providers import AVAILABLE_PROVIDERS
104#:
105#: AVAILABLE_PROVIDERS["hypothesis"] = "hypothesis.internal.conjecture.providers.HypothesisProvider"
106#: # or
107#: AVAILABLE_PROVIDERS["hypothesis"] = HypothesisProvider
108#:
109#: And can be used with:
110#:
111#: .. code-block:: python
112#:
113#: from hypothesis import given, settings, strategies as st
114#:
115#: @given(st.integers())
116#: @settings(backend="hypothesis")
117#: def f(n):
118#: pass
119#:
120#: Though, as ``backend="hypothesis"`` is the default setting, the above would
121#: typically not have any effect.
122#:
123#: For third-party backend authors, we strongly encourage ensuring that
124#: ``import hypothesis`` does not automatically import the expensive parts of
125#: your package, by:
126#:
127#: - setting a string path here, instead of a provider class
128#: - ensuring the registered hypothesis plugin path references a path which just
129#: sets AVAILABLE_PROVIDERS and does not import your package
130AVAILABLE_PROVIDERS: dict[str, str | type["PrimitiveProvider"]] = {
131 "hypothesis": "hypothesis.internal.conjecture.providers.HypothesisProvider",
132 "hypothesis-urandom": "hypothesis.internal.conjecture.providers.URandomProvider",
133}
134# cache the choice_permitted constants for a particular set of constraints.
135CacheKeyT: TypeAlias = tuple[ChoiceTypeT, tuple[Any, ...]]
136CacheValueT: TypeAlias = tuple[tuple["ConstantT", ...], tuple["ConstantT", ...]]
137CONSTANTS_CACHE: LRUCache[CacheKeyT, CacheValueT] = LRUCache(1024)
140_constants_integers = (
141 # powers of 2
142 [2**n for n in range(16, 66)]
143 # powers of 10
144 + [10**n for n in range(5, 20)]
145 # factorials
146 + [math.factorial(n) for n in range(9, 21)]
147 # a few primorial numbers https://en.wikipedia.org/wiki/Primorial
148 + [
149 510510,
150 6469693230,
151 304250263527210,
152 32589158477190044730,
153 ]
154)
155_constants_integers.extend(
156 [n - 1 for n in _constants_integers] + [n + 1 for n in _constants_integers]
157)
158_constants_integers.extend([-x for x in _constants_integers])
160# arbitrary cutoffs to keep our list bounded
161assert all(50_000 <= abs(n) <= 2**66 for n in _constants_integers)
163_constant_floats = (
164 [
165 0.5,
166 1.1,
167 1.5,
168 1.9,
169 1.0 / 3,
170 10e6,
171 10e-6,
172 1.175494351e-38,
173 next_up(0.0),
174 float_info.min,
175 float_info.max,
176 3.402823466e38,
177 9007199254740992.0,
178 1 - 10e-6,
179 2 + 10e-6,
180 1.192092896e-07,
181 2.2204460492503131e-016,
182 ]
183 + [2.0**-n for n in (24, 14, 149, 126)] # minimum (sub)normals for float16,32
184 + [float_info.min / n for n in (2, 10, 1000, 100_000)] # subnormal in float64
185)
186_constant_floats.extend([-x for x in _constant_floats])
187assert all(isinstance(f, float) for f in _constant_floats)
189_constant_strings = {
190 # strings which can be interpreted as code / logic
191 "undefined",
192 "null",
193 "NULL",
194 "nil",
195 "NIL",
196 "true",
197 "false",
198 "True",
199 "False",
200 "TRUE",
201 "FALSE",
202 "None",
203 "none",
204 "if",
205 "then",
206 "else",
207 "__dict__",
208 "__proto__", # javascript
209 # strings which can be interpreted as a number
210 "0",
211 "1e100",
212 "0..0",
213 "0/0",
214 "1/0",
215 "+0.0",
216 "Infinity",
217 "-Infinity",
218 "Inf",
219 "INF",
220 "NaN",
221 "9" * 30,
222 # common ascii characters
223 ",./;'[]\\-=<>?:\"{}|_+!@#$%^&*()`~",
224 # common unicode characters
225 "Ω≈ç√∫˜µ≤≥÷åß∂ƒ©˙∆˚¬…æœ∑´®†¥¨ˆøπ“‘¡™£¢∞§¶•ªº–≠¸˛Ç◊ı˜Â¯˘¿ÅÍÎÏ˝ÓÔÒÚÆ☃Œ„´‰ˇÁ¨ˆØ∏”’`⁄€‹›fifl‡°·‚—±",
226 # characters which increase in length when lowercased
227 "Ⱥ",
228 "Ⱦ",
229 # ligatures
230 "æœÆŒffʤʨß",
231 # emoticons
232 "(╯°□°）╯︵ ┻━┻)",
233 # emojis
234 "😍",
235 "🇺🇸",
236 # emoji modifiers
237 "🏻", # U+1F3FB Light Skin Tone,
238 "👍🏻", # 👍 followed by U+1F3FB
239 # RTL text
240 "الكل في المجمو عة",
241 # Ogham text, which contains the only character in the Space Separators
242 # unicode category (Zs) that isn't visually blank: . # noqa: RUF003
243 "᚛ᚄᚓᚐᚋᚒᚄ ᚑᚄᚂᚑᚏᚅ᚜",
244 # thai consonant + spacing vowel combinations, which have unusual visual combining behavior
245 "กา",
246 "ก ำกำ",
247 # readable variations on text (bolt/italic/script)
248 "𝐓𝐡𝐞 𝐪𝐮𝐢𝐜𝐤 𝐛𝐫𝐨𝐰𝐧 𝐟𝐨𝐱 𝐣𝐮𝐦𝐩𝐬 𝐨𝐯𝐞𝐫 𝐭𝐡𝐞 𝐥𝐚𝐳𝐲 𝐝𝐨𝐠",
249 "𝕿𝖍𝖊 𝖖𝖚𝖎𝖈𝖐 𝖇𝖗𝖔𝖜𝖓 𝖋𝖔𝖝 𝖏𝖚𝖒𝖕𝖘 𝖔𝖛𝖊𝖗 𝖙𝖍𝖊 𝖑𝖆𝖟𝖞 𝖉𝖔𝖌",
250 "𝑻𝒉𝒆 𝒒𝒖𝒊𝒄𝒌 𝒃𝒓𝒐𝒘𝒏 𝒇𝒐𝒙 𝒋𝒖𝒎𝒑𝒔 𝒐𝒗𝒆𝒓 𝒕𝒉𝒆 𝒍𝒂𝒛𝒚 𝒅𝒐𝒈",
251 "𝓣𝓱𝓮 𝓺𝓾𝓲𝓬𝓴 𝓫𝓻𝓸𝔀𝓷 𝓯𝓸𝔁 𝓳𝓾𝓶𝓹𝓼 𝓸𝓿𝓮𝓻 𝓽𝓱𝓮 𝓵𝓪𝔃𝔂 𝓭𝓸𝓰",
252 "𝕋𝕙𝕖 𝕢𝕦𝕚𝕔𝕜 𝕓𝕣𝕠𝕨𝕟 𝕗𝕠𝕩 𝕛𝕦𝕞𝕡𝕤 𝕠𝕧𝕖𝕣 𝕥𝕙𝕖 𝕝𝕒𝕫𝕪 𝕕𝕠𝕘",
253 # upsidown text
254 "ʇǝɯɐ ʇᴉs ɹolop ɯnsdᴉ ɯǝɹo˥",
255 # reserved strings in windows
256 "NUL",
257 "COM1",
258 "LPT1",
259 # scunthorpe problem
260 "Scunthorpe",
261 # zalgo text
262 "Ṱ̺̺̕o͞ ̷i̲̬͇̪͙n̝̗͕v̟̜̘̦͟o̶̙̰̠kè͚̮̺̪̹̱̤ ̖t̝͕̳̣̻̪͞h̼͓̲̦̳̘̲e͇̣̰̦̬͎ ̢̼̻̱̘h͚͎͙̜̣̲ͅi̦̲̣̰̤v̻͍e̺̭̳̪̰-m̢iͅn̖̺̞̲̯̰d̵̼̟͙̩̼̘̳ ̞̥̱̳̭r̛̗̘e͙p͠r̼̞̻̭̗e̺̠̣͟s̘͇̳͍̝͉e͉̥̯̞̲͚̬͜ǹ̬͎͎̟̖͇̤t͍̬̤͓̼̭͘ͅi̪̱n͠g̴͉ ͏͉ͅc̬̟h͡a̫̻̯͘o̫̟̖͍̙̝͉s̗̦̲.̨̹͈̣",
263 #
264 # examples from https://faultlore.com/blah/text-hates-you/
265 "मनीष منش",
266 "पन्ह पन्ह त्र र्च कृकृ ड्ड न्हृे إلا بسم الله",
267 "lorem لا بسم الله ipsum 你好1234你好",
268 # unicode charaacters causing unconditional line breaks, as defined by UAX #14:
269 # https://www.unicode.org/reports/tr14/.
270 #
271 # We've seen multiple bugs caused by assuming `str.splitlines` is equivalent to
272 # splitting over "\n", while it actually splits over all line breaks!
273 #
274 # We intersperse the line breaks with normal characters to increase the likelihood
275 # of triggering such a bug.
276 (
277 "a"
278 "\u000a" # line feed (class: LF)
279 "b"
280 "\u000d" # carriage return (class: CR)
281 "c"
282 "\u0085" # next line (class: NL)
283 "d"
284 "\u000b" # line tabulation (class: BK)
285 "e"
286 "\u000c" # form feed (class: BK)
287 "f"
288 "\u2028" # line separator (class: BK)
289 "g"
290 "\u2029" # paragraph separator (class: BK)
291 "h"
292 "\u000d\u000a" # CR+LF
293 "i"
294 ),
295}
298# we don't actually care what order the constants are sorted in, just that the
299# ordering is deterministic.
300GLOBAL_CONSTANTS = Constants(
301 integers=SortedSet(_constants_integers),
302 floats=SortedSet(_constant_floats, key=float_to_int),
303 bytes=SortedSet(),
304 strings=SortedSet(_constant_strings),
305)
307_local_constants = Constants(
308 integers=SortedSet(),
309 floats=SortedSet(key=float_to_int),
310 bytes=SortedSet(),
311 strings=SortedSet(),
312)
313# Modules that we've already seen and processed for local constants. These are
314# are all modules, not necessarily local ones. This lets us quickly see which
315# modules are new without an expensive path.resolve() or is_local_module_file
316# cache lookup.
317#
318# We track by id so we can handle users that put unhashable types like SimpleNamespace
319# into sys.modules. ModuleType.__hash__ falls back to id, so this is equivalent
320# in the standard case.
321_seen_modules: set[int] = set()
322_sys_modules_len: int | None = None
325def _get_local_constants() -> Constants:
326 global _sys_modules_len, _local_constants
328 if sys.platform == "emscripten": # pragma: no cover
329 # pyodide builds bundle the stdlib in a nonstandard location, like
330 # `/lib/python312.zip/heapq.py`. To avoid identifying the entirety of
331 # the stdlib as local code and slowing down on emscripten, instead return
332 # that nothing is local.
333 #
334 # pyodide may provide some way to distinguish stdlib/third-party/local
335 # code. I haven't looked into it. If they do, we should correctly implement
336 # ModuleLocation for pyodide instead of this.
337 return _local_constants
339 count_constants = len(_local_constants)
340 # We call this function once per HypothesisProvider instance, i.e. once per
341 # input, so it needs to be performant. The logic here is more complicated
342 # than necessary because of this.
343 #
344 # First, we check whether there are any new modules with a very cheap length
345 # check. This check can be fooled if a module is added while another module is
346 # removed, but the more correct check against tuple(sys.modules.keys()) is
347 # substantially more expensive. Such a new module would eventually be discovered
348 # if / when the length changes again in the future.
349 #
350 # If the length has changed, we find just modules we haven't seen before. Of
351 # those, we find the ones which correspond to local modules, and extract their
352 # constants.
354 # careful: store sys.modules length when we first check to avoid race conditions
355 # with other threads loading a module before we set _sys_modules_len.
356 if (sys_modules_len := len(sys.modules)) != _sys_modules_len:
357 new_modules = [
358 module
359 for module in list(sys.modules.values())
360 if id(module) not in _seen_modules
361 ]
362 # Repeated SortedSet unions are expensive. Do the initial unions on a
363 # set(), then do a one-time union with _local_constants after.
364 new_constants = Constants()
365 for module in new_modules:
366 if (
367 module_file := getattr(module, "__file__", None)
368 ) is not None and is_local_module_file(module_file):
369 new_constants |= constants_from_module(module)
370 _seen_modules.add(id(module))
371 _local_constants |= new_constants
372 _sys_modules_len = sys_modules_len
374 # if we add any new constant, invalidate the constant cache for permitted values.
375 # A more efficient approach would be invalidating just the keys with this
376 # choice_type.
377 if len(_local_constants) > count_constants:
378 CONSTANTS_CACHE.cache.clear()
380 return _local_constants
383@contextmanager
384def with_register_backend(name, provider_cls):
385 try:
386 AVAILABLE_PROVIDERS[name] = provider_cls
387 yield
388 finally:
389 del AVAILABLE_PROVIDERS[name]
392class _BackendInfoMsg(TypedDict):
393 type: InfoObservationType
394 title: str
395 content: str | dict[str, Any]
398# TODO_DOCS: link to choice sequence explanation page
401class PrimitiveProvider(abc.ABC):
402 """
403 |PrimitiveProvider| is the implementation interface of a
404 :ref:`Hypothesis backend <alternative-backends>`.
406 A |PrimitiveProvider| is required to implement the following five
407 ``draw_*`` methods:
409 * |PrimitiveProvider.draw_integer|
410 * |PrimitiveProvider.draw_boolean|
411 * |PrimitiveProvider.draw_float|
412 * |PrimitiveProvider.draw_string|
413 * |PrimitiveProvider.draw_bytes|
415 Each strategy in Hypothesis generates values by drawing a series of choices
416 from these five methods. By overriding them, a |PrimitiveProvider| can control
417 the distribution of inputs generated by Hypothesis.
419 For example, :pypi:`hypothesis-crosshair` implements a |PrimitiveProvider|
420 which uses an SMT solver to generate inputs that uncover new branches.
422 Once you implement a |PrimitiveProvider|, you can make it available for use
423 through |AVAILABLE_PROVIDERS|.
424 """
426 #: The lifetime of a |PrimitiveProvider| instance. Either ``test_function``
427 #: or ``test_case``.
428 #:
429 #: If ``test_function`` (the default), a single provider instance will be
430 #: instantiated and used for the entirety of each test function (i.e., roughly
431 #: one provider per |@given| annotation). This can be useful for tracking state
432 #: over the entirety of a test function.
433 #:
434 #: If ``test_case``, a new provider instance will be instantiated and used for
435 #: each input Hypothesis generates.
436 #:
437 #: The ``conjecturedata`` argument to ``PrimitiveProvider.__init__`` will
438 #: be ``None`` for a lifetime of ``test_function``, and an instance of
439 #: ``ConjectureData`` for a lifetime of ``test_case``.
440 #:
441 #: Third-party providers likely want to set a lifetime of ``test_function``.
442 lifetime: ClassVar[LifetimeT] = "test_function"
444 #: Solver-based backends such as ``hypothesis-crosshair`` use symbolic values
445 #: which record operations performed on them in order to discover new paths.
446 #: If ``avoid_realization`` is set to ``True``, hypothesis will avoid interacting
447 #: with symbolic choices returned by the provider in any way that would force
448 #: the solver to narrow the range of possible values for that symbolic.
449 #:
450 #: Setting this to ``True`` disables some hypothesis features and optimizations.
451 #: Only set this to ``True`` if it is necessary for your backend.
452 avoid_realization: ClassVar[bool] = False
454 #: If ``True``, |PrimitiveProvider.on_observation| will be added as a
455 #: callback via |add_observability_callback|, enabling observability during
456 # the lifetime of this provider. If ``False``, |PrimitiveProvider.on_observation|
457 #: will never be called by Hypothesis.
458 #:
459 #: The opt-in behavior of observability is because enabling observability
460 #: might increase runtime or memory usage.
461 add_observability_callback: ClassVar[bool] = False
463 def __init__(self, conjecturedata: Optional["ConjectureData"], /) -> None:
464 self._cd = conjecturedata
466 @abc.abstractmethod
467 def draw_boolean(
468 self,
469 p: float = 0.5,
470 ) -> bool:
471 """
472 Draw a boolean choice.
474 Parameters
475 ----------
476 p: float
477 The probability of returning ``True``. Between 0 and 1 inclusive.
479 Except for ``0`` and ``1``, the value of ``p`` is a hint provided by
480 Hypothesis, and may be ignored by the backend.
482 If ``0``, the provider must return ``False``. If ``1``, the provider
483 must return ``True``.
484 """
485 raise NotImplementedError
487 @abc.abstractmethod
488 def draw_integer(
489 self,
490 min_value: int | None = None,
491 max_value: int | None = None,
492 *,
493 weights: dict[int, float] | None = None,
494 shrink_towards: int = 0,
495 ) -> int:
496 """
497 Draw an integer choice.
499 Parameters
500 ----------
501 min_value : int | None
502 (Inclusive) lower bound on the integer value. If ``None``, there is
503 no lower bound.
504 max_value : int | None
505 (Inclusive) upper bound on the integer value. If ``None``, there is
506 no upper bound.
507 weights: dict[int, float] | None
508 Maps keys in the range [``min_value``, ``max_value``] to the probability
509 of returning that key.
510 shrink_towards: int
511 The integer to shrink towards. This is not used during generation and
512 can be ignored by backends.
513 """
514 raise NotImplementedError
516 @abc.abstractmethod
517 def draw_float(
518 self,
519 *,
520 min_value: float = -math.inf,
521 max_value: float = math.inf,
522 allow_nan: bool = True,
523 smallest_nonzero_magnitude: float,
524 ) -> float:
525 """
526 Draw a float choice.
528 Parameters
529 ----------
530 min_value : float
531 (Inclusive) lower bound on the float value.
532 max_value : float
533 (Inclusive) upper bound on the float value.
534 allow_nan : bool
535 If ``False``, it is invalid to return ``math.nan``.
536 smallest_nonzero_magnitude : float
537 The smallest allowed nonzero magnitude. ``draw_float`` should not
538 return a float ``f`` if ``abs(f) < smallest_nonzero_magnitude``.
539 """
540 raise NotImplementedError
542 @abc.abstractmethod
543 def draw_string(
544 self,
545 intervals: IntervalSet,
546 *,
547 min_size: int = 0,
548 max_size: int = COLLECTION_DEFAULT_MAX_SIZE,
549 ) -> str:
550 """
551 Draw a string choice.
553 Parameters
554 ----------
555 intervals : IntervalSet
556 The set of codepoints to sample from.
557 min_size : int
558 (Inclusive) lower bound on the string length.
559 max_size : int
560 (Inclusive) upper bound on the string length.
561 """
562 raise NotImplementedError
564 @abc.abstractmethod
565 def draw_bytes(
566 self,
567 min_size: int = 0,
568 max_size: int = COLLECTION_DEFAULT_MAX_SIZE,
569 ) -> bytes:
570 """
571 Draw a bytes choice.
573 Parameters
574 ----------
575 min_size : int
576 (Inclusive) lower bound on the bytes length.
577 max_size : int
578 (Inclusive) upper bound on the bytes length.
579 """
580 raise NotImplementedError
582 def per_test_case_context_manager(self) -> AbstractContextManager:
583 """
584 Returns a context manager which will be entered each time Hypothesis
585 starts generating and executing one |test case|, and exited when that test
586 case finishes generating and executing, including if any exception is
587 thrown.
589 In the lifecycle of a Hypothesis test, this is called before
590 generating strategy values for each test case. This is just before any
591 :ref:`custom executor <custom-function-execution>` is called.
593 Even if not returning a custom context manager, |PrimitiveProvider|
594 subclasses are welcome to override this method to know when Hypothesis
595 starts and ends the execution of a single test case.
596 """
597 return contextlib.nullcontext()
599 def realize(self, value: T, *, for_failure: bool = False) -> T:
600 """
601 Called whenever hypothesis requires a concrete (non-symbolic) value from
602 a potentially symbolic value. Hypothesis will not check that ``value`` is
603 symbolic before calling ``realize``, so you should handle the case where
604 ``value`` is non-symbolic.
606 The returned value should be non-symbolic. If you cannot provide a value,
607 raise |BackendCannotProceed| with a value of ``"discard_test_case"``.
609 If ``for_failure`` is ``True``, the value is associated with a |failing test case|.
610 In this case, the backend should spend substantially more effort when
611 attempting to realize the value, since it is important to avoid discarding
612 failing test cases. Backends may still raise |BackendCannotProceed| when
613 ``for_failure`` is ``True``, if realization is truly impossible or if
614 realization takes significantly longer than expected (say, 5 minutes).
615 """
616 return value
618 def replay_choices(self, choices: tuple[ChoiceT, ...]) -> None:
619 """
620 Called when Hypothesis has a |choice sequence| which the provider
621 may wish to enqueue to replay under its own instrumentation when we next
622 ask to generate a |test case|, rather than generating one from scratch.
624 The choice sequence may not correspond to the draws made by the current
625 test, for example if it comes from a stale corpus, so providers must
626 tolerate arbitrary choices of any type, in any order.
628 This is used to e.g. warm-start :pypi:`hypothesis-crosshair` with a corpus
629 of high-code-coverage inputs discovered by
630 `HypoFuzz <https://hypofuzz.com/>`_.
631 """
632 return None
634 def observe_test_case(self) -> dict[str, Any]:
635 """Called at the end of the |test case| when :ref:`observability
636 <observability>` is enabled.
638 The return value should be a non-symbolic json-encodable dictionary,
639 and will be included in observations as ``observation["metadata"]["backend"]``.
640 """
641 return {}
643 def observe_information_messages(
644 self, *, lifetime: LifetimeT
645 ) -> Iterable[_BackendInfoMsg]:
646 """Called at the end of each |test case| and again at end of the test function.
648 Return an iterable of ``{type: info/alert/error, title: str, content: str | dict}``
649 dictionaries to be delivered as individual information messages. Hypothesis
650 adds the ``run_start`` timestamp and ``property`` name for you.
651 """
652 assert lifetime in ("test_case", "test_function")
653 yield from []
655 def on_observation(self, observation: TestCaseObservation) -> None: # noqa: B027
656 """
657 Called at the end of each |test case| which uses this provider, with the same
658 ``observation["type"] == "test_case"`` observation that is passed to
659 other callbacks added via |add_observability_callback|. This method is not
660 called with ``observation["type"] in {"info", "alert", "error"}``
661 observations.
663 .. important::
665 For |PrimitiveProvider.on_observation| to be called by Hypothesis,
666 |PrimitiveProvider.add_observability_callback| must be set to ``True``.
668 |PrimitiveProvider.on_observation| is explicitly opt-in, as enabling
669 observability might increase runtime or memory usage.
671 Calls to this method are guaranteed to alternate with calls to
672 |PrimitiveProvider.per_test_case_context_manager|. For example:
674 .. code-block:: python
676 # test function starts
677 per_test_case_context_manager()
678 on_observation()
679 per_test_case_context_manager()
680 on_observation()
681 ...
682 # test function ends
684 Note that |PrimitiveProvider.on_observation| will not be called for test
685 cases which did not use this provider during generation, for example
686 during |Phase.reuse| or |Phase.shrink|, or because Hypothesis switched
687 to the standard Hypothesis backend after this backend raised too many
688 |BackendCannotProceed| exceptions.
689 """
691 def span_start(self, label: int, /) -> None: # noqa: B027 # non-abstract noop
692 """Marks the beginning of a semantically meaningful span of choices.
694 Spans are a depth-first tree structure. A span is opened by a call to
695 |PrimitiveProvider.span_start|, and a call to |PrimitiveProvider.span_end|
696 closes the most recently opened span. So the following sequence of calls:
698 .. code-block:: python
700 span_start(label=1)
701 n1 = draw_integer()
702 span_start(label=2)
703 b1 = draw_boolean()
704 n2 = draw_integer()
705 span_end()
706 f1 = draw_float()
707 span_end()
709 produces the following two spans of choices:
711 .. code-block::
713 1: [n1, b1, n2, f1]
714 2: [b1, n2]
716 Hypothesis uses spans to denote "semantically meaningful" sequences of
717 choices. For instance, Hypothesis opens a span for the sequence of choices
718 made while drawing from each strategy. Not every span corresponds to a
719 strategy; the generation of e.g. each element in |st.lists| is also marked
720 with a span, among others.
722 ``label`` is an opaque integer, which has no defined semantics.
723 The only guarantee made by Hypothesis is that all spans with the same
724 "meaning" will share the same ``label``. So all spans from the same
725 strategy will share the same label, as will e.g. the spans for |st.lists|
726 elements.
728 Providers can track calls to |PrimitiveProvider.span_start| and
729 |PrimitiveProvider.span_end| to learn something about the semantics of
730 the test's |choice sequence|. For instance, a provider could track the depth
731 of the span tree, or the number of unique labels, which says something about
732 the complexity of the choices being generated. Or a provider could track
733 the span tree across |test cases| in order to determine what strategies are
734 being used in what contexts.
736 It is possible for Hypothesis to start and immediately stop a span,
737 without calling a ``draw_*`` method in between. These spans contain zero
738 choices.
740 Hypothesis will always balance the number of calls to
741 |PrimitiveProvider.span_start| and |PrimitiveProvider.span_end|. A call
742 to |PrimitiveProvider.span_start| will always be followed by a call to
743 |PrimitiveProvider.span_end| before the end of the test case.
745 |PrimitiveProvider.span_start| is called from ``ConjectureData.start_span()``
746 internally.
747 """
749 def span_end(self, discard: bool, /) -> None: # noqa: B027
750 """Marks the end of a semantically meaningful span of choices.
752 ``discard`` is ``True`` when the draw was filtered out or otherwise marked
753 as unlikely to contribute to the input data as seen by the user's test.
754 Note however that side effects can make this determination unsound.
756 |PrimitiveProvider.span_end| is called from ``ConjectureData.stop_span()``
757 internally.
758 """
761class HypothesisProvider(PrimitiveProvider):
762 lifetime = "test_case"
764 def __init__(self, conjecturedata: Optional["ConjectureData"], /):
765 super().__init__(conjecturedata)
766 self._random = None if self._cd is None else self._cd._random
768 @cached_property
769 def _local_constants(self):
770 # defer computation of local constants until/if we need it
771 return _get_local_constants()
773 def _maybe_draw_constant(
774 self,
775 choice_type: ChoiceTypeT,
776 constraints: ChoiceConstraintsT,
777 *,
778 p: float = 0.05,
779 ) -> Optional["ConstantT"]:
780 assert self._random is not None
781 assert choice_type != "boolean"
782 # check whether we even want a constant before spending time computing
783 # and caching the allowed constants.
784 if self._random.random() > p:
785 return None
787 # note: this property access results in computation being done
788 assert self._local_constants is not None
790 key = (choice_type, choice_constraints_key(choice_type, constraints))
791 if key not in CONSTANTS_CACHE:
792 CONSTANTS_CACHE[key] = (
793 tuple(
794 choice
795 for choice in GLOBAL_CONSTANTS.set_for_type(choice_type)
796 if choice_permitted(choice, constraints)
797 ),
798 tuple(
799 choice
800 for choice in self._local_constants.set_for_type(choice_type)
801 if choice_permitted(choice, constraints)
802 ),
803 )
805 # split constants into two pools, so we still have a good chance to draw
806 # global constants even if there are many local constants.
807 global_constants, local_constants = CONSTANTS_CACHE[key]
808 constants_lists = ([global_constants] if global_constants else []) + (
809 [local_constants] if local_constants else []
810 )
811 if not constants_lists:
812 return None
814 # At this point, we've decided to use a constant. Now we select which pool
815 # to draw that constant from.
816 #
817 # Note that this approach has a different probability distribution than
818 # attempting a random.random for both global_constants and local_constants.
819 constants = self._random.choice(constants_lists)
820 return self._random.choice(constants)
822 def draw_boolean(
823 self,
824 p: float = 0.5,
825 ) -> bool:
826 assert self._random is not None
828 if p <= 0:
829 return False
830 if p >= 1:
831 return True
833 return self._random.random() < p
835 def draw_integer(
836 self,
837 min_value: int | None = None,
838 max_value: int | None = None,
839 *,
840 weights: dict[int, float] | None = None,
841 shrink_towards: int = 0,
842 ) -> int:
843 assert self._cd is not None
844 if (
845 constant := self._maybe_draw_constant(
846 "integer",
847 {
848 "min_value": min_value,
849 "max_value": max_value,
850 "weights": weights,
851 "shrink_towards": shrink_towards,
852 },
853 )
854 ) is not None:
855 assert isinstance(constant, int)
856 return constant
858 if weights is not None:
859 assert min_value is not None
860 assert max_value is not None
862 # format of weights is a mapping of ints to p, where sum(p) < 1.
863 # The remaining probability mass is uniformly distributed over
864 # *all* ints (not just the unmapped ones; this is somewhat undesirable,
865 # but simplifies things).
866 #
867 # We assert that sum(p) is strictly less than 1 because it simplifies
868 # handling forced values when we can force into the unmapped probability
869 # mass. We should eventually remove this restriction.
870 sampler = Sampler(
871 [1 - sum(weights.values()), *weights.values()], observe=False
872 )
873 # if we're forcing, it's easiest to force into the unmapped probability
874 # mass and then force the drawn value after.
875 idx = sampler.sample(self._cd)
877 if idx == 0:
878 return self._draw_integer_from_distribution(min_value, max_value)
879 # implicit reliance on dicts being sorted for determinism
880 return list(weights)[idx - 1]
882 return self._draw_integer_from_distribution(min_value, max_value)
884 def _draw_integer_from_distribution(
885 self, min_value: int | None, max_value: int | None
886 ) -> int:
887 assert self._random is not None
888 dist = INTEGERS_DISTRIBUTION
890 # Our integers distribution is defined over the full float64 range. If the user
891 # has not placed a lower and/or upper bound, we don't actually want to sample
892 # from this full range, because we might otherwise generate integers
893 # that are so large as to cause problems. For example python errors when passing
894 # a too-large integer to c APIs (common and implicit in some python stdlib APIs).
895 #
896 # * If the user asks for an unbounded range, we bound at [-2**128, 2**128].
897 # * If the user asks for a half-bounded range starting at n, we bound at
898 # [n, 2**128] for n < 2**127, and [n, 2n] otherwise, so we always support
899 # generating large integers if a user explicitly asks for integers around that
900 # magnitude. The choice of a factor of two here is arbitrary.
901 if min_value is None and max_value is None:
902 min_value = -(2**128)
903 max_value = 2**128
904 elif min_value is None:
905 assert max_value is not None
906 min_value = -max(2**128, 2 * abs(max_value))
907 elif max_value is None:
908 max_value = max(2**128, 2 * abs(min_value))
910 lo = 0.0
911 hi = 1.0
912 safe_bounds = True
913 try:
914 cdf_min = min_value - 0.5
915 cdf_max = max_value + 0.5
916 except OverflowError:
917 safe_bounds = False
918 else:
919 lo = dist.cdf(cdf_min)
920 hi = dist.cdf(cdf_max)
922 # if the bounds in CDF-space are too close together, there isn't enough room
923 # to stably sample between hi and lo. For example, in the extreme case of
924 # hi = lo (which can happen even if min_value != max_value due to either float
925 # imprecision or numerical instability), our sampling algorithm would collapse
926 # to always return the sample value.
927 #
928 # The choice of 1e-13 here is somewhat arbitrary. At 1.0, epsilon in float64
929 # is 2^-53 ~= 1e-16. We want some breathing room from epsilon, because we need
930 # some variation to actually sample in. I haven't put much thought into where
931 # the correct tradeoff lies. The downside risk to choosing a too-aggressive
932 # bound is some integers may literally not be representable in the `hi - lo`
933 # sampling space. The downside risk to a too-conservative bound is switching
934 # off our good distribution too early.
935 if hi - lo < 1e-13:
936 safe_bounds = False
938 if safe_bounds:
939 # inverse_cdf requires strictly 0 < p < 1. Resample until we get it.
940 while (p := lo + self._random.random() * (hi - lo)) in {0, 1}:
941 pass # pragma: no cover
942 n = round(dist.inverse_cdf(p))
943 # As an extra measure of safety, clamp our generated value to the requested
944 # range. It would of course be nice if we provably satisfied this by
945 # construction - I'm just not 100% confident that we do.
946 return clamp(min_value, n, max_value)
948 # We have determined the bounds [min_value, max_value] are not numerically safe
949 # to use. Fall back to a simpler and safer distribution: a uniform distribution
950 # on [min_value, max_value].
951 return self._random.randint(min_value, max_value)
953 def draw_float(
954 self,
955 *,
956 min_value: float = -math.inf,
957 max_value: float = math.inf,
958 allow_nan: bool = True,
959 smallest_nonzero_magnitude: float,
960 ) -> float:
961 assert self._random is not None
963 constraints: FloatConstraints = {
964 "min_value": min_value,
965 "max_value": max_value,
966 "allow_nan": allow_nan,
967 "smallest_nonzero_magnitude": smallest_nonzero_magnitude,
968 }
969 if (
970 constant := self._maybe_draw_constant("float", constraints, p=0.15)
971 ) is not None:
972 assert isinstance(constant, float)
973 return constant
975 # on top of the probability to draw a constant float, we independently
976 # upweight 0.0/-0.0, math.inf, -math.inf, nans, and boundary values.
977 weird_floats = [
978 f
979 for f in [
980 0.0,
981 -0.0,
982 math.inf,
983 -math.inf,
984 math.nan,
985 -math.nan,
986 SIGNALING_NAN,
987 -SIGNALING_NAN,
988 min_value,
989 next_up(min_value),
990 min_value + 1,
991 max_value - 1,
992 next_down(max_value),
993 max_value,
994 ]
995 if choice_permitted(f, constraints)
996 ]
998 if weird_floats and self._random.random() < 0.05:
999 return self._random.choice(weird_floats)
1001 clamper = make_float_clamper(
1002 min_value,
1003 max_value,
1004 smallest_nonzero_magnitude=smallest_nonzero_magnitude,
1005 allow_nan=allow_nan,
1006 )
1008 result = self._draw_float()
1009 if allow_nan and math.isnan(result):
1010 clamped = result # pragma: no cover
1011 else:
1012 clamped = clamper(result)
1013 if float_to_int(clamped) != float_to_int(result) and not (
1014 math.isnan(result) and allow_nan
1015 ):
1016 result = clamped
1017 return result
1019 def draw_string(
1020 self,
1021 intervals: IntervalSet,
1022 *,
1023 min_size: int = 0,
1024 max_size: int = COLLECTION_DEFAULT_MAX_SIZE,
1025 ) -> str:
1026 assert self._cd is not None
1027 assert self._random is not None
1029 if len(intervals) == 0:
1030 return ""
1032 if (
1033 constant := self._maybe_draw_constant(
1034 "string",
1035 {"intervals": intervals, "min_size": min_size, "max_size": max_size},
1036 )
1037 ) is not None:
1038 assert isinstance(constant, str)
1039 return constant
1041 average_size = min(
1042 max(min_size * 2, min_size + 5),
1043 0.5 * (min_size + max_size),
1044 )
1046 chars = []
1047 with many(
1048 self._cd,
1049 min_size=min_size,
1050 max_size=max_size,
1051 average_size=average_size,
1052 observe=False,
1053 ) as elements:
1054 for _ in elements:
1055 if len(intervals) > 256:
1056 if self.draw_boolean(0.2):
1057 i = self._random.randint(256, len(intervals) - 1)
1058 else:
1059 i = self._random.randint(0, 255)
1060 else:
1061 i = self._random.randint(0, len(intervals) - 1)
1063 chars.append(intervals.char_in_shrink_order(i))
1065 return "".join(chars)
1067 def draw_bytes(
1068 self,
1069 min_size: int = 0,
1070 max_size: int = COLLECTION_DEFAULT_MAX_SIZE,
1071 ) -> bytes:
1072 assert self._cd is not None
1073 assert self._random is not None
1075 if (
1076 constant := self._maybe_draw_constant(
1077 "bytes", {"min_size": min_size, "max_size": max_size}
1078 )
1079 ) is not None:
1080 assert isinstance(constant, bytes)
1081 return constant
1083 buf = bytearray()
1084 average_size = min(
1085 max(min_size * 2, min_size + 5),
1086 0.5 * (min_size + max_size),
1087 )
1088 with many(
1089 self._cd,
1090 min_size=min_size,
1091 max_size=max_size,
1092 average_size=average_size,
1093 observe=False,
1094 ) as elements:
1095 for _ in elements:
1096 buf += self._random.randbytes(1)
1098 return bytes(buf)
1100 def _draw_float(self) -> float:
1101 assert self._random is not None
1103 f = lex_to_float(self._random.getrandbits(64))
1104 sign = 1 if self._random.getrandbits(1) else -1
1105 return sign * f
1108# Masks for masking off the first byte of an n-bit buffer.
1109# The appropriate mask is stored at position n % 8.
1110BYTE_MASKS = [(1 << n) - 1 for n in range(8)]
1111BYTE_MASKS[0] = 255
1114class BytestringProvider(PrimitiveProvider):
1115 lifetime = "test_case"
1117 def __init__(
1118 self, conjecturedata: Optional["ConjectureData"], /, *, bytestring: bytes
1119 ):
1120 super().__init__(conjecturedata)
1121 self.bytestring = bytestring
1122 self.index = 0
1123 self.drawn = bytearray()
1125 def _draw_bits(self, n):
1126 if n == 0: # pragma: no cover
1127 return 0
1128 n_bytes = bits_to_bytes(n)
1129 if self.index + n_bytes > len(self.bytestring):
1130 self._cd.mark_overrun()
1131 buf = bytearray(self.bytestring[self.index : self.index + n_bytes])
1132 self.index += n_bytes
1134 buf[0] &= BYTE_MASKS[n % 8]
1135 buf = bytes(buf)
1136 self.drawn += buf
1137 return int_from_bytes(buf)
1139 def draw_boolean(
1140 self,
1141 p: float = 0.5,
1142 ) -> bool:
1143 if p <= 0:
1144 return False
1145 if p >= 1:
1146 return True
1148 # always use one byte for booleans to maintain constant draw size.
1149 # If a probability requires more than 8 bits to represent precisely,
1150 # the result will be slightly biased, but not badly.
1151 bits = 8
1152 size = 2**bits
1153 # always leave at least one value that can be true, even for very small
1154 # p.
1155 falsey = clamp(1, math.floor(size * (1 - p)), size - 1)
1156 n = self._draw_bits(bits)
1157 return n >= falsey
1159 def draw_integer(
1160 self,
1161 min_value: int | None = None,
1162 max_value: int | None = None,
1163 *,
1164 weights: dict[int, float] | None = None,
1165 shrink_towards: int = 0,
1166 ) -> int:
1167 assert self._cd is not None
1169 # we explicitly ignore integer weights for now, as they are likely net
1170 # negative on fuzzer performance.
1172 if min_value is None and max_value is None:
1173 min_value = -(2**127)
1174 max_value = 2**127 - 1
1175 elif min_value is None:
1176 assert max_value is not None
1177 min_value = max_value - 2**64
1178 elif max_value is None:
1179 assert min_value is not None
1180 max_value = min_value + 2**64
1182 if min_value == max_value:
1183 return min_value
1185 bits = (max_value - min_value).bit_length()
1186 value = min_value + self._draw_bits(bits)
1187 while value > max_value:
1188 value = min_value + self._draw_bits(bits)
1189 return value
1191 def draw_float(
1192 self,
1193 *,
1194 min_value: float = -math.inf,
1195 max_value: float = math.inf,
1196 allow_nan: bool = True,
1197 smallest_nonzero_magnitude: float,
1198 ) -> float:
1199 n = self._draw_bits(65)
1200 sign = -1 if n >> 64 else 1
1201 f = sign * lex_to_float(n & ((1 << 64) - 1))
1202 clamper = make_float_clamper(
1203 min_value,
1204 max_value,
1205 smallest_nonzero_magnitude=smallest_nonzero_magnitude,
1206 allow_nan=allow_nan,
1207 )
1208 return clamper(f)
1210 def _draw_collection(self, min_size, max_size, *, alphabet_size):
1211 if alphabet_size == 0:
1212 # the only valid value is the empty collection - don't draw for it.
1213 return []
1214 average_size = min(
1215 max(min_size * 2, min_size + 5),
1216 0.5 * (min_size + max_size),
1217 )
1218 with many(
1219 self._cd,
1220 min_size=min_size,
1221 max_size=max_size,
1222 average_size=average_size,
1223 observe=False,
1224 ) as elements:
1225 return [self.draw_integer(0, alphabet_size - 1) for _ in elements]
1227 def draw_string(
1228 self,
1229 intervals: IntervalSet,
1230 *,
1231 min_size: int = 0,
1232 max_size: int = COLLECTION_DEFAULT_MAX_SIZE,
1233 ) -> str:
1234 values = self._draw_collection(min_size, max_size, alphabet_size=len(intervals))
1235 return "".join(chr(intervals[v]) for v in values)
1237 def draw_bytes(
1238 self,
1239 min_size: int = 0,
1240 max_size: int = COLLECTION_DEFAULT_MAX_SIZE,
1241 ) -> bytes:
1242 values = self._draw_collection(min_size, max_size, alphabet_size=2**8)
1243 return bytes(values)
1246class URandom(Random):
1247 # we reimplement a Random instance instead of using SystemRandom, because
1248 # os.urandom is not guaranteed to read from /dev/urandom.
1250 @staticmethod
1251 def _urandom(size: int) -> bytes:
1252 # By default, we buffer more data from /dev/urandom than the actual `size` number
1253 # of bytes we requested. This trips up anyone (and particularly Antithesis)
1254 # hooking /dev/urandom reads to control randomness.
1255 #
1256 # buffering=0 disables this behavior.
1257 with open("/dev/urandom", "rb", buffering=0) as f:
1258 return f.read(size)
1260 def getrandbits(self, k: int) -> int:
1261 assert k >= 0
1262 size = bits_to_bytes(k)
1263 n = int_from_bytes(self._urandom(size))
1264 # trim excess bits
1265 return n >> (size * 8 - k)
1267 def random(self) -> float:
1268 # adapted from random.SystemRandom.random
1269 return (int_from_bytes(self._urandom(7)) >> 3) * (2**-53)
1272class URandomProvider(HypothesisProvider):
1273 # A provider which reads directly from /dev/urandom as its source of randomness.
1274 # This provider exists to provide better Hypothesis integration with Antithesis
1275 # (https://antithesis.com/), which interprets calls to /dev/urandom as the
1276 # randomness to mutate. This effectively gives Antithesis control over
1277 # the choices made by the URandomProvider.
1278 #
1279 # If you are not using Antithesis, you probably don't want to use this
1280 # provider.
1282 def __init__(self, conjecturedata: Optional["ConjectureData"], /):
1283 super().__init__(conjecturedata)
1284 if WINDOWS: # pragma: no cover
1285 warnings.warn(
1286 "/dev/urandom is not available on windows. Falling back to "
1287 'standard PRNG generation (equivalent to backend="hypothesis").',
1288 HypothesisWarning,
1289 stacklevel=1,
1290 )
1291 # don't overwrite the HypothesisProvider self._random attribute in
1292 # this case
1293 else:
1294 self._random = URandom()