Как я могу реорганизовать это рекурсивное выражение стратегии Strategy для параметризации его длины?

Question

Context

Во-первых, спасибо за гипотезу. Это очень мощный и очень полезный!

Я написал стратегию гипотез для создания монотонных (ANDS и ORs) выражений политики в форме:

(A and (B or C))

Это можно рассматривать как древовидную структуру, где A, B и C являются атрибутами в конечных узлах, тогда как 'и' и 'или' являются неконцевыми узлами.

Стратегия, кажется, генерирует выражения по желанию.

>>> find(policy_expressions(), lambda x: len(x.split()) > 3)
'(A or (A or A))'

(Возможно, статистическое разнообразие примеров можно улучшить, но это не суть этого вопроса).

Неравенства также действительны. Например:

(N or (WlIorO and (nX <= 55516 and e)))

Я хочу ограничить или отфильтровать примеры, чтобы я мог генерировать выражения политики с указанным числом конечных узлов (то есть атрибутов).

Для теста производительности я попытался использовать data.draw() с filter примерно так:

@given(data=data())
def test_keygen_encrypt_proxy_decrypt_decrypt_execution_time(data, n):
    """
    :param n: the input size n. Number of attributes or leaf nodes in policy tree.
    """

    policy_str = data.draw(strategy=policy_expressions().filter(lambda x: len(extract_attributes(group, x)) == n),
                           label="policy string")

Где extract_attributes() подсчитывает количество вершин листьев в выражении, а n - желаемое количество листьев.

Проблема с этим решением состоит в том, что когда n> 16, гипотеза выдает:

hypothesis.errors.Unsatisfiable: Unable to satisfy assumptions of hypothesis test_keygen_encrypt_proxy_decrypt_decrypt_execution_time.

Я хочу создать допустимые выражения политики с сотнями конечных узлов.

Другим недостатком этого подхода было то, что гипотеза сообщала HealthCheck.filter_too_much и HealthCheck.too_slow, а @settings становился безобразным.

Я бы предпочел параметр, чтобы сказать policy_expressions(leaf_nodes=4), чтобы получить пример, подобный этому:

(N or (WlIorO and (nX <= 55516 and e)))

Сначала я этого избегал, потому что не могу понять, как это сделать с помощью рекурсивного кода стратегии.

Вопрос

Можете ли вы предложить способ рефакторинга этой стратегии, чтобы ее можно было параметрировать для числа конечных узлов?

Вот код стратегии (в любом случае его открытый источник в Charm Crypto)

from hypothesis.strategies import text, composite, sampled_from, characters, one_of, integers


def policy_expressions():
    return one_of(attributes(), inequalities(), policy_expression())


@composite
def policy_expression(draw):
    left = draw(policy_expressions())
    right = draw(policy_expressions())
    gate = draw(gates())
    return u'(' + u' '.join((left, gate, right)) + u')'


def attributes():
    return text(min_size=1, alphabet=characters(whitelist_categories='L', max_codepoint=0x7e))


@composite
def inequalities(draw):
    attr = draw(attributes())
    oper = draw(inequality_operators())
    numb = draw(integers(min_value=1))
    return u' '.join((attr, oper, str(numb)))


def inequality_operators():
    return sampled_from((u'<', u'>', u'<=', u'>='))


def gates():
    return sampled_from((u'or', u'and'))


def assert_valid(policy_expression):
    assert policy_expression  # not empty
    assert policy_expression.count(u'(') == policy_expression.count(u')')

https://github.com/JHUISI/charm/blob/dev/charm/toolbox/policy_expression_spec.py

Answer 1

Я бы предложил явно встроить количество листов в построение данных, а затем передать желаемое количество листьев:

from hypothesis.strategies import text, composite, sampled_from, characters, one_of, integers


def policy_expressions_of_size(num_leaves):
    if num_leaves == 1:
        return attributes()
    elif num_leaves == 2:
        return one_of(inequalities(), policy_expression(num_leaves))
    else:
        return policy_expression(num_leaves)


policy_expressions = integers(min_value=1, max_value=500).flatmap(policy_expressions_of_size)


@composite
def policy_expression(draw, num_leaves):
    left_leaves = draw(integers(min_value=1, max_value=num_leaves - 1))
    right_leaves = num_leaves - left_leaves
    left = draw(policy_expressions_of_size(left_leaves))
    right = draw(policy_expressions_of_size(right_leaves))
    gate = draw(gates())
    return u'(' + u' '.join((left, gate, right)) + u')'


def attributes():
    return text(min_size=1, alphabet=characters(whitelist_categories='L', max_codepoint=0x7e))


@composite
def inequalities(draw):
    attr = draw(attributes())
    oper = draw(inequality_operators())
    numb = draw(integers(min_value=1))
    return u' '.join((attr, oper, str(numb)))


def inequality_operators():
    return sampled_from((u'<', u'>', u'<=', u'>='))


def gates():
    return sampled_from((u'or', u'and'))

Затем вы можете точно указать, насколько большим должно быть выражение политики:

>>> policy_expressions.example()
'((((((oOjFo or (((cH and (Q or (uO > 18 and byy))) and kS) or pqKUUZ > 74)) and (gi or mwsrU <= 4115)) and qLkVSTqXZxgScTj) and (vNJ > 969 and (Drwvh or (((xhmsWhHpc or hQSMnfgyiYnblLFJ) or sesfHbQ) and jt)))) or xS) and ((V and (mArqYR or qY)) or (((uVf and bbtKUCnecMKjRJD > 18944) and nerVkPSs < 29292) and (UlOJebfbgcJz or (bxfVfjgmfulSB > 71 or (jqGLlr or (zQqj and zqUGwc < 24845)))))))'
>>> 
>>> policy_expressions_of_size(1).example()
'Eo'
>>> 
>>> policy_expressions_of_size(2).example()
'KJAitOKC > 18179'
>>> policy_expressions_of_size(10).example()
'(((htjdVy or (((XTfZil or (rqZw and DEOeER)) and xGVsdeQJLTJxLsC < 388312303) or LxLfUPljUTH)) or (Kb or EoipoYzjncAGKTE)) or bc)'
>>> policy_expressions_of_size(100).example()
'(((((CxySeUrNW or bZG) or (gzSUGgTG and (((V or n) or wqA) or veuTEnjGKwIpkDDDBiQkMwsNbxrBv))) or (((SKgQSXtAg or ChCHcEsVavy) and (((Yxj and xcCX) or QrILGAWxVKXWRb > 98817811688973569232860005374239659122) or JD <= 28510)) and KhrGfZciz > 4057857855522854443)) and (ZMIzFELKAKDMrH and (((MOmAZ and J <= 22052) or (Scy >= 17563 and (VCS and ((FFLa and EtZvqwNymnZNnjlREM) or pU)))) or A))) and ((((kaYzzIXIu and (lwos and (vp and GqG))) and ((Nh and lb) or ((TbNZWYOpYmj and (AQs or w)) or NjFYLBr > 228431293))) or ((((FTSXkXGZyKXD or zXeVEqNgkyXI) or mNGI) or ((cGOGK or gjcI) and DQzYonXszfSrZMB)) and JI > 3802)) or (((jIREd and IVzFB >= 28149) and (UdCBg < 20 or (VSGxr or XBuiS <= 1615))) and (rE > 10511139808015932 and ((((((((W and u) or yslVZ) or (eVGlz < 7033 or UiE)) and ((trOmArBc and Zx) or mPKva)) or ((qqDmKUpAnW or yvSkhTgqXQaLnxL) or Z)) or snXcMDhhf) and ((Wu or XSjbKdsZqEiXXvOb) and (DNZg and qv >= 7503))) and ((rnffxTLThwvw >= 24460 and ((oO or y <= 24926) and (NjM and vEHukii))) or ((((BTdpW and rP) or (rjUylCZwJzGobXZR or MNoBdEEIuLbTRvZHMb < 7958346708112664935)) and ((YU or gY >= 15498) and (s and GnOydthO > 103))) or ((caumKPjp < 27 and OQoFXscbD) or ((qaxYwfnelmetYqHKnatQ or P) and (ixzsvX and mYROpqoHAqeEy))))))))))'