def pattern_to_statements(pattern):
    if isinstance(pattern, template):
        return lists(just(pattern), min_size=1, max_size=1)
    rule, value = pattern
    if rule == 'sequence':
        return tuples(*map(pattern_to_statements, value)).map(unpack_list).map(list)
    elif rule == 'alternates':
        return one_of(*map(pattern_to_statements, value))
    elif rule == 'zeroOrMore':
        return lists(pattern_to_statements(value)).map(unpack_list).map(list)
    elif rule == 'oneOrMore':
        return lists(pattern_to_statements(value), min_size=1).map(unpack_list).map(list)
    elif rule == 'optional':
        return lists(pattern_to_statements(value), min_size=0, max_size=1).map(unpack_list).map(list)
    else:
        raise Exception("impossible!", rule)



# this replicates the current scorm pattern, a realistic example of medium
# complexity. Note it has repeated elements, just not in ambiguous ways. 

def test_padding(ndim: int, data: st.DataObject):
    """Ensure that convolving a padding-only image with a commensurate kernel yields the single entry: 0"""
    padding = data.draw(
        st.integers(1, 3) | st.tuples(*[st.integers(1, 3)] * ndim), label="padding"
    )
    x = Tensor(
        data.draw(
            hnp.arrays(shape=(1, 1) + (0,) * ndim, dtype=float, elements=st.floats()),
            label="x",
        )
    )
    pad_tuple = padding if isinstance(padding, tuple) else (padding,) * ndim
    kernel = data.draw(
        hnp.arrays(
            shape=(1, 1) + tuple(2 * p for p in pad_tuple),
            dtype=float,
            elements=st.floats(allow_nan=False, allow_infinity=False),
        )
    )
    out = conv_nd(x, kernel, padding=padding, stride=1)
    assert out.shape == (1,) * x.ndim
    assert out.item() == 0.0

    out.sum().backward()
    assert x.grad.shape == x.shape 

def test_upcast_roundtrip(type_strategy, data: st.DataObject):
    thin, wide = data.draw(
        st.tuples(type_strategy, type_strategy).map(
            lambda x: sorted(x, key=lambda y: np.dtype(y).itemsize)
        )
    )
    orig_tensor = data.draw(
        hnp.arrays(
            dtype=thin,
            shape=hnp.array_shapes(),
            elements=hnp.from_dtype(thin).filter(np.isfinite),
        ).map(Tensor)
    )

    roundtripped_tensor = orig_tensor.astype(wide).astype(thin)
    assert_array_equal(orig_tensor, roundtripped_tensor) 

def ds_vars_dims_mixed():
    def build_it(vars_to_dims_):
        all_dims = list(set(sum((list(dd) for dd in vars_to_dims_.values()), [])))

        ds = fixed_datasets(vars_to_dims_)

        dims = subset_lists(all_dims)

        vars_ = sampled_from(list(vars_to_dims_.keys()))
        vars_dict = dictionaries(vars_, dims, dict_class=OrderedDict)
        vars_dict = vars_dict.map(OrderedDict.items).map(list)

        return tuples(ds, vars_dict, just(all_dims))

    vars_to_dims_st = vars_to_dims_dicts(min_vars=0, min_dims=0)

    S = vars_to_dims_st.flatmap(build_it)
    return S 

def sig_pair():
    def separate(D):
        signatures, signatures_ref = {}, {}
        for kk in D:
            if len(D[kk]) == 1:
                v_ref, = D[kk]
                signatures_ref[kk] = np.asarray(v_ref)
            elif len(D[kk]) == 2:
                v, v_ref = D[kk]
                signatures[kk] = np.asarray(v)
                signatures_ref[kk] = np.asarray(v_ref)
            else:
                assert False
        return signatures, signatures_ref

    sig_dict = dictionaries(text(), tuples(bsigs()) | tuples(bsigs(), bsigs()))
    S = sig_dict.map(separate)
    return S 

def fcall(fn, args=None, kwargs=None):
    """
    Call function with given positional and keyword args.
    """

    if args == () or args is None:
        args = st.just(())
    elif isinstance(args, (tuple, list)):
        args = st.tuples(*args)

    if kwargs == {} or kwargs is None:
        kwargs = st.just({})
    elif isinstance(kwargs, dict):
        ks = list(kwargs.keys())
        kwargs = st.builds(lambda *xs: dict(zip(ks, xs)), *kwargs.values())

    return st.builds(lambda xs, kw: fn(*xs, **kw), args, kwargs) 

def trees(*args, max_depth=None, allow_attrs=True, **kwargs):
    """
    Return random trees.
    """
    attrs = st.just([])
    kwargs["allow_attrs"] = allow_attrs
    if allow_attrs:
        keys = identifiers(allow_private=False, exclude=("children", "parent"))
        attr = st.tuples(keys, kwargs.get("attrs") or atoms())
        attrs = st.lists(attr)
    fn = partial(shape_tree, max_depth)
    return st.builds(fn, attrs, st.lists(leaves(*args, **kwargs)))


#
# Utility functions
# 

def _create_hyp_class(attrs_and_strategy):
    """
    A helper function for Hypothesis to generate attrs classes.

    The result is a tuple: an attrs class, and a tuple of values to
    instantiate it.
    """

    def key(t):
        return t[0].default is not NOTHING

    attrs_and_strat = sorted(attrs_and_strategy, key=key)
    attrs = [a[0] for a in attrs_and_strat]
    for i, a in enumerate(attrs):
        a.counter = i
    vals = tuple((a[1]) for a in attrs_and_strat)
    return st.tuples(
        st.just(
            make_class("HypClass", OrderedDict(zip(gen_attr_names(), attrs)))
        ),
        st.tuples(*vals),
    ) 

def _create_hyp_nested_strategy(simple_class_strategy):
    """
    Create a recursive attrs class.
    Given a strategy for building (simpler) classes, create and return
    a strategy for building classes that have as an attribute:
        * just the simpler class
        * a list of simpler classes
        * a dict mapping the string "cls" to a simpler class.
    """
    # A strategy producing tuples of the form ([list of attributes], <given
    # class strategy>).
    attrs_and_classes = st.tuples(
        lists_of_attrs(defaults=True), simple_class_strategy
    )

    return (
        attrs_and_classes.flatmap(just_class)
        | attrs_and_classes.flatmap(just_class_with_type)
        | attrs_and_classes.flatmap(list_of_class)
        | attrs_and_classes.flatmap(list_of_class_with_type)
        | attrs_and_classes.flatmap(dict_of_class)
    ) 

def _tuple_strategy(abi_type: TupleType) -> SearchStrategy:
    strategies = [strategy(i.to_type_str()) for i in abi_type.components]
    return st.tuples(*strategies) 

def init_default_strategies() -> None:
    """Register all default "format" strategies."""
    register_string_format("binary", st.binary())
    register_string_format("byte", st.binary().map(lambda x: b64encode(x).decode()))

    def make_basic_auth_str(item: Tuple[str, str]) -> str:
        return _basic_auth_str(*item)

    register_string_format("_basic_auth", st.tuples(st.text(), st.text()).map(make_basic_auth_str))  # type: ignore
    register_string_format("_bearer_auth", st.text().map("Bearer {}".format)) 

def remove_strategy(self):
        def get_address(service_name):
            return st.tuples(st.just(service_name), st.sampled_from(
                self.fake.services[service_name]))
        return st.tuples(st.just("remove"), (
                st.sampled_from(list(self.fake.services.keys())).flatmap(get_address))) 

def steps(self):
        result = add_strategy | replace_strategy
        # Replace or add to a known service cluster:
        if self.fake.services:
            result |= st.tuples(st.just("replace"),
                                st.tuples(st.sampled_from(list(self.fake.services.keys())),
                                          st.lists(nice_strings)))
            result |= st.tuples(st.just("add"),
                                st.tuples(st.sampled_from(list(self.fake.services.keys())),
                                          nice_strings))
        # Remove a known address from known cluster:
        if not self.fake.is_empty():
            result |= self.remove_strategy()
        return result 

def add_bools(list_of_lists):
    """
    Given recursive list that can contain other lists, return tuple of that plus
    a booleans strategy for each list.
    """
    l = []
    def count(recursive):
        l.append(1)
        for child in recursive:
            if isinstance(child, list):
                count(child)
    count(list_of_lists)
    return st.tuples(st.just(list_of_lists), st.tuples(*[st.sampled_from([True, False]) for i in l])) 

def random_reference(draw, prefix = random_prefix()):
    number = st.integers(min_value = 0)
    return draw(st.tuples(prefix, number)) 

def chromeReqResp ():
    # XXX: will this gnerated the same url for all testcases?
    reqid = st.shared (st.text (), 'reqresp')
    url = st.shared (urlsStr (), 'reqresp')
    return st.tuples (chromeRequestWillBeSent (reqid, url),
            chromeResponseReceived (reqid, url)) 

def test_sliding_window(data, x):
    """ Test variations of window-shape, step, and dilation for sliding window
        view of N-dimensional array."""

    win_dim = data.draw(st.integers(1, x.ndim), label="win_dim")
    win_shape = data.draw(
        st.tuples(*(st.integers(1, s) for s in x.shape[-win_dim:])), label="win_shape"
    )
    step = data.draw(
        st.tuples(*(st.integers(1, s) for s in x.shape[-win_dim:])), label="step"
    )

    max_dilation = np.array(x.shape[-win_dim:]) // win_shape
    dilation = data.draw(
        st.one_of(
            st.none()
            | st.integers(1, min(max_dilation))
            | st.tuples(*(st.integers(1, s) for s in max_dilation))
        ),
        label="dilation",
    )
    y = sliding_window_view(x, window_shape=win_shape, step=step, dilation=dilation)

    if dilation is None:
        dilation = np.ones((len(win_shape),), dtype=int)

    if isinstance(dilation, int):
        dilation = np.full((len(win_shape),), fill_value=dilation, dtype=int)

    for ind in np.ndindex(*y.shape[:win_dim]):
        slices = tuple(
            slice(i * s, i * s + w * d, d)
            for i, w, s, d in zip(ind, win_shape, step, dilation)
        )
        assert_allclose(actual=y[tuple([*ind])], desired=x[(..., *slices)]) 

def test_softmax_focal_loss(num_datum, num_classes, alpha, gamma, data, grad, target_type):
    scores = data.draw(
        hnp.arrays(shape=(num_datum, num_classes), dtype=float, elements=st.floats(1, 100))
    )
    assume((abs(scores.sum(axis=1)) > 0.001).all())

    scores_mygrad = Tensor(scores)
    scores_nn = Tensor(scores)

    truth = np.zeros((num_datum, num_classes))
    targets = data.draw(st.tuples(*(st.integers(0, num_classes - 1) for i in range(num_datum))))
    truth[range(num_datum), targets] = 1
    targets = target_type(targets)

    probs = softmax(scores_mygrad)
    mygrad_focal_loss = sum(truth * (-alpha * (1 - probs + 1e-14)**gamma * log(probs))) / num_datum
    mygrad_focal_loss.backward(grad)

    nn_loss = softmax_focal_loss(scores_nn, targets, alpha=alpha, gamma=gamma).mean()
    nn_loss.backward(grad)

    assert isinstance(nn_loss, Tensor) and nn_loss.ndim == 0
    assert_allclose(nn_loss.data, mygrad_focal_loss.data, atol=1e-4, rtol=1e-4)
    assert_allclose(scores_nn.grad, scores_mygrad.grad, atol=1e-4, rtol=1e-4)

    nn_loss.null_gradients()
    assert scores_nn.grad is None 

def test_focal_loss(num_datum, num_classes, alpha, gamma, data, grad, target_type):
    scores = data.draw(
        hnp.arrays(shape=(num_datum, num_classes), dtype=float, elements=st.floats(1, 100))
    )
    assume((abs(scores.sum(axis=1)) > 0.001).all())

    scores_mygrad = Tensor(scores)
    scores_nn = Tensor(scores)

    truth = np.zeros((num_datum, num_classes))
    targets = data.draw(st.tuples(*(st.integers(0, num_classes - 1) for i in range(num_datum))))
    truth[range(num_datum), targets] = 1
    targets = target_type(targets)

    fl = focal_loss(softmax(scores_mygrad), targets, alpha=alpha, gamma=gamma).mean()
    fl.backward(grad)

    nn_loss = softmax_focal_loss(scores_nn, targets, alpha=alpha, gamma=gamma).mean()
    nn_loss.backward(grad)

    assert isinstance(nn_loss, Tensor) and nn_loss.ndim == 0
    assert_allclose(nn_loss.data, fl.data, atol=1e-4, rtol=1e-4)
    assert_allclose(scores_nn.grad, scores_mygrad.grad, atol=1e-4, rtol=1e-4)

    nn_loss.null_gradients()
    assert scores_nn.grad is None 

def gen_tuple_repeat_args(draw: st.DataObject.draw, arr: Tensor):

    valid_axis = draw(
        st.none() | (st.integers(-arr.ndim, arr.ndim - 1) if arr.ndim else st.just(0))
    )

    num_repeats = (
        arr.shape[valid_axis] if valid_axis is not None and arr.ndim else arr.size
    )
    repeats = draw(st.tuples(*[st.integers(0, 5)] * num_repeats))
    return dict(repeats=repeats, axis=valid_axis,) 

def _bidict_strat(bi_types, init_items=I_PAIRS_NODUP, _inv=attrgetter('inverse')):
    fwd_bidicts = st.tuples(bi_types, init_items).map(lambda i: i[0](i[1]))
    inv_bidicts = fwd_bidicts.map(_inv)
    return fwd_bidicts | inv_bidicts 

def _bi_and_map(bi_types, map_types, init_items=L_PAIRS_NODUP):
    return st.tuples(bi_types, map_types, init_items).map(
        lambda i: (i[0](i[2]), i[1](i[2]))
    ) 

def ds_vars_dims():
    def build_it(vars_to_dims_):
        all_dims = list(set(sum((list(dd) for dd in vars_to_dims_.values()), [])))

        ds = fixed_datasets(vars_to_dims_)
        vars_ = subset_lists(list(vars_to_dims_.keys()))
        dims = subset_lists(all_dims)
        return tuples(ds, vars_, dims)

    vars_to_dims_st = vars_to_dims_dicts()

    S = vars_to_dims_st.flatmap(build_it)
    return S 

def container_value_st(element_sequence):
    return st.tuples(*element_sequence)


#
# Strategies for basic sedes with corresponding value strategy
# 

def general_container_sedes_and_values_st(draw, element_sedes_and_elements_sequence):
    element_sedes, elements = zip(*element_sedes_and_elements_sequence)
    sedes = Container(element_sedes)
    values = st.tuples(*elements)
    return sedes, values


#
# Strategies for depth-1 composite sedes objects with corresponding value strategy
# 

def kwargs(values=atoms(), **kwargs):
    """
    Create dictionaries that represent valid keyword arguments.
    """
    names = identifiers(**kwargs)
    pairs = st.tuples(names, values)
    return st.lists(pairs).map(dict)


# noinspection PyShadowingNames 

def lists_of_primitives(draw):
    """Generate a strategy that yields tuples of list of primitives and types.

    For example, a sample value might be ([1,2], List[int]).
    """
    prim_strat, t = draw(primitive_strategies)
    list_t = draw(list_types.map(lambda list_t: list_t[t]) | list_types)
    return draw(st.lists(prim_strat)), list_t 

def create_dict_and_type(tuple_of_strats):
    """Map two primitive strategies into a strategy for dict and type."""
    (prim_strat_1, type_1), (prim_strat_2, type_2) = tuple_of_strats

    return st.tuples(
        st.dictionaries(prim_strat_1, prim_strat_2),
        create_generic_dict_type(type_1, type_2),
    ) 

def simple_classes(defaults=None, min_attrs=0):
    """
    Return a strategy that yields tuples of simple classes and values to
    instantiate them.
    """
    return lists_of_attrs(defaults, min_size=min_attrs).flatmap(
        _create_hyp_class
    )


# Ok, so st.recursive works by taking a base strategy (in this case,
# simple_classes) and a special function. This function receives a strategy,
# and returns another strategy (building on top of the base strategy). 

def rfc3339(name: str) -> st.SearchStrategy[str]:
    """Get a strategy for date or time strings in the given RFC3339 format.

    See https://tools.ietf.org/html/rfc3339#section-5.6
    """
    # Hmm, https://github.com/HypothesisWorks/hypothesis/issues/170
    # would make this a lot easier...
    assert name in RFC3339_FORMATS

    def zfill(width: int) -> Callable[[int], str]:
        return lambda v: str(v).zfill(width)

    simple = {
        "date-fullyear": st.integers(0, 9999).map(zfill(4)),
        "date-month": st.integers(1, 12).map(zfill(2)),
        "date-mday": st.integers(1, 28).map(zfill(2)),  # incomplete but valid
        "time-hour": st.integers(0, 23).map(zfill(2)),
        "time-minute": st.integers(0, 59).map(zfill(2)),
        "time-second": st.integers(0, 59).map(zfill(2)),  # ignore negative leap seconds
        "time-secfrac": st.from_regex(r"\.[0-9]+"),
    }
    if name in simple:
        return simple[name]
    if name == "time-numoffset":
        return st.tuples(
            st.sampled_from(["+", "-"]), rfc3339("time-hour"), rfc3339("time-minute")
        ).map("%s%s:%s".__mod__)
    if name == "time-offset":
        return st.one_of(st.just("Z"), rfc3339("time-numoffset"))
    if name == "partial-time":
        return st.times().map(str)
    if name == "date" or name == "full-date":
        return st.dates().map(str)
    if name == "time" or name == "full-time":
        return st.tuples(rfc3339("partial-time"), rfc3339("time-offset")).map("".join)
    assert name == "date-time"
    return st.tuples(rfc3339("full-date"), rfc3339("full-time")).map("T".join)