def assert_all_valid_keys(symbol_input_dict, symbol_set):
    """Assert that all keys in the passed input dict are valid.

    Valid keys are considered those that are present in the passed set of
    symbols and that map to valid Boolean values. Dictionaries cannot have
    duplicate keys, so no duplicate checking is necessary.

    :param symbol_input_dict: A dict containing symbol names mapping to what
        should be Boolean values.
    :type symbol_input_dict: Dict{:class:`str <python:str>`: truthy}

    :param symbol_set: A set of the symbol names expected to be present as keys
        in ``symbol_input_dict``.
    :type symbol_set: Set[:class:`str <python:str>`]

    :raises ExtraSymbolError: If any keys in the passed input dict are not
        present in the passed set of symbols.
    :raises InvalidBooleanValueError: If any values in the passed input dict
        are not valid Boolean values (``1``, ``0``, ``True``, or ``False``).

    This assert is used for validation of user-specified kwargs which map
    symbols to expected values.

    """
    for k, v in symbol_input_dict.items():
        if k not in symbol_set:
            raise ExtraSymbolError(
                '"{}" is not a symbol in this expression'.format(k))

        if v not in BOOLEAN_VALUES:
            raise InvalidBooleanValueError(
                '"{}" passed as value for "{}" is not a valid Boolean '
                'value'.format(v, k)) def assert_iterable_contains_all_expr_symbols(iter_of_strs, reference_set):
    """Assert a one-to-one presence of all symbols in the passed iterable.

    :param iter_of_strs: An iterable of strings to assert.
    :type iter_of_strs: Iterable[:class:`str <python:str>`]

    :param reference_set: A set of strings, each of which will be asserted to
        be present in the passed iterable.
    :type reference_set: Set[:class:`str <python:str>`]

    .. note::

        This function will consume ``iter_of_strs``.

    :raises DuplicateSymbolError: If the passed iterable contains more than one
        of a given symbol.
    :raises ExtraSymbolError: If the passed iterable contains symbols not
        present in the reference set.
    :raises MissingSymbolError: If the passed iterable is missing symbols
        present in the reference set.

    This assertion is used for validation of user-specified sets of symbols.

    """
    passed_symbol_list = list(iter_of_strs)
    passed_symbol_set = set(passed_symbol_list)
    if len(passed_symbol_list) != len(passed_symbol_set):
        raise DuplicateSymbolError('Received duplicate symbols')

    passed_excess_set = passed_symbol_set - reference_set
    reference_excess_set = reference_set - passed_symbol_set

    if reference_excess_set:
        msg = 'Did not receive value for the following symbols: '
        msg += ', '.join('"{}"'.format(sym) for sym in reference_excess_set)
        raise MissingSymbolError(msg)

    if passed_excess_set:
        msg = 'Received unexpected symbols: '
        msg += ', '.join('"{}"'.format(sym) for sym in passed_excess_set)
        raise ExtraSymbolError(msg) def boolean_variables_factory(symbols):
    """Returns a class for namedtuple-like objects for holding boolean values.

    :param symbols: A list of the symbol names for which instances of this
        class will hold an entry.
    :type symbols: List[:class:`str <python:str>`]

    :returns: An object where the passed ``symbols`` can be accessed as
        attributes.
    :rtype: :func:`namedtuple <python:collections.namedtuple>`-like object

    This functionality is best demonstrated with an example::

        >>> from tt import boolean_variables_factory
        >>> factory = boolean_variables_factory(['op1', 'op2', 'op3'])
        >>> instance = factory(op1=True, op2=False, op3=False)
        >>> instance.op1
        True
        >>> instance.op2
        False
        >>> print(instance)
        op1=1, op2=0, op3=0
        >>> instance = factory(op1=0, op2=0, op3=1)
        >>> instance.op3
        1
        >>> print(instance)
        op1=0, op2=0, op3=1

    It should be noted that this function is used internally within
    functionality where the validity of inputs is already checked. As such,
    this class won't enforce the Boolean-ness of input values::

        >>> factory = boolean_variables_factory(['A', 'B'])
        >>> instance = factory(A=-1, B='value')
        >>> print(instance)
        A=-1, B=value

    Instances produced from the generated factory are descendants of
    :func:`namedtuple <python:collections.namedtuple>` generated classes; some
    of the inherited attributes may be useful::

        >>> instance = factory(A=True, B=False)
        >>> instance._fields
        ('A', 'B')
        >>> dict(instance._asdict())
        {'A': True, 'B': False}

    """
    class _bvf(namedtuple('_bvf', symbols)):
        __slots__ = ()

        def __str__(self):
            pairs = []
            for field, val in self._asdict().items():
                val = int(val) if isinstance(val, bool) else val
                pairs.append(field + '=' + str(val))
            return ', '.join(pairs)

        def __repr__(self):
            return '<BooleanValues [{}]>'.format(str(self))

    return _bvf DONT_CARE_VALUE = 'x' def is_valid_identifier(identifier_name):
    """Returns whether the string is a valid symbol identifier.

    Valid identifiers are those that follow Python variable naming conventions,
    are not Python keywords, and do not begin with an underscore.

    :param identifier_name: The string to test.
    :type identifier_name: :class:`str <python:str>`

    :returns: True if the passed string is valid identifier, otherwise False.
    :rtype: :class:`bool <python:bool>`

    :raises InvalidArgumentTypeError: If ``identifier_name`` is not a string.
    :raises InvalidArgumentValueError: If ``identifier_name`` is an empty
        string.

    As an example::

        >>> from tt import is_valid_identifier
        >>> is_valid_identifier('$var')
        False
        >>> is_valid_identifier('va#r')
        False
        >>> is_valid_identifier('for')
        False
        >>> is_valid_identifier('False')
        False
        >>> is_valid_identifier('var')
        True
        >>> is_valid_identifier('')
        Traceback (most recent call last):
            ...
        tt.errors.arguments.InvalidArgumentValueError: identifier_name cannot \
be empty
        >>> is_valid_identifier(None)
        Traceback (most recent call last):
            ...
        tt.errors.arguments.InvalidArgumentTypeError: identifier_name must be \
a string

    """
    if not isinstance(identifier_name, str):
        raise InvalidArgumentTypeError('identifier_name must be a string')

    if not identifier_name:
        raise InvalidArgumentValueError('identifier_name cannot be empty')

    if identifier_name.startswith('_'):
        return False

    if identifier_name in _tt_keywords:
        return False

    identifier_re = re.compile(r'^[^\d\W]\w*\Z', re.UNICODE)
    if re.match(identifier_re, identifier_name) is None:
        return False

    return True class ConflictingArgumentsError(ArgumentError):
    """An exception type for two or more conflicting arguments.

    This error type can be seen in action by passing both an expression and a
    set of values to the :class:`TruthTable <tt.tables.truth_table.TruthTable>`
    class::

        >>> from tt import TruthTable
        >>> t = TruthTable('A or B', from_values='1111')
        Traceback (most recent call last):
            ...
        tt.errors.arguments.ConflictingArgumentsError: `expr` and \
`from_values` are mutually exclusive arguments

    """ class InvalidArgumentTypeError(ArgumentError):
    """An exception type for invalid argument types.

    To illustrate this error type, let's try passing an invalid argument when
    creating a :class:`TruthTable <tt.tables.truth_table.TruthTable>`::

        >>> from tt import TruthTable
        >>> t = TruthTable(7)
        Traceback (most recent call last):
            ...
        tt.errors.arguments.InvalidArgumentTypeError: Arg `expr` must be of \
type `str` or `BooleanExpression`

    """ class InvalidArgumentValueError(ArgumentError):
    """An exception type for invalid argument values.

    Here's an example where we pass a non-power of 2 number of values when
    attempting to create a :class:`TruthTable \
    <tt.tables.truth_table.TruthTable>`::

        >>> from tt import TruthTable
        >>> t = TruthTable(from_values='01x')
        Traceback (most recent call last):
            ...
        tt.errors.arguments.InvalidArgumentValueError: Must specify a number \
of input values that is a power of 2

    """ class RequiredArgumentError(ArgumentError):
    """An exception for when a required argument is missing.

    Let's try an example where we omit all arguments when attempting to make
    a new :class:`TruthTable <tt.tables.truth_table.TruthTable>` object::

        >>> from tt import TruthTable
        >>> t = TruthTable()
        Traceback (most recent call last):
            ...
        tt.errors.arguments.RequiredArgumentError: Must specify either `expr` \
or `from_values`

    """ class InvalidBooleanValueError(EvaluationError):
    """An exception for when an invalid truth or don't care value is passed.

    Here's an example where we attempt to evaluate a \
    :class:`BooleanExpression <tt.expressions.bexpr.BooleanExpression>` with
    an invalid value passed through ``kwargs``::

        >>> from tt import BooleanExpression
        >>> b = BooleanExpression('A or B')
        >>> b.evaluate(A=1, B='brian')
        Traceback (most recent call last):
            ...
        tt.errors.evaluation.InvalidBooleanValueError: "brian" passed as \
value for "B" is not a valid Boolean value

    """ class NoEvaluationVariationError(EvaluationError):
    """An exception type for when evaluation of an expression will not vary.

    Let's see an example where we attempt to make a :class:`TruthTable \
    <tt.tables.truth_table.TruthTable>` from an expression that has no
    symbols nor variation in its results::

        >>> from tt import TruthTable
        >>> t = TruthTable('1 or 0')
        Traceback (most recent call last):
            ...
        tt.errors.evaluation.NoEvaluationVariationError: This expression is \
composed only of constant values

    """ class InvalidIdentifierError(GrammarError):
    """An exception type for invalid operand names. Invalid operand names are
    determined via the :func:`is_valid_identifier \
    <tt.definitions.operands.is_valid_identifier>` function.

    Here are a couple of examples, for both expressions and tables::

        >>> from tt import BooleanExpression, TruthTable
        >>> b = BooleanExpression('__A xor B')
        Traceback (most recent call last):
            ...
        tt.errors.grammar.InvalidIdentifierError: Invalid operand name "__A"
        >>> t = TruthTable(from_values='0x11', ordering=['for', 'operand'])
        Traceback (most recent call last):
            ...
        tt.errors.grammar.InvalidIdentifierError: "for" in ordering is not a \
    valid symbol name

    """ class AlreadyFullTableError(StateError):
    """An exception to be raised when attempting to fill an already-full table.

    .. code-block:: python

        >>> from tt import TruthTable
        >>> t = TruthTable('A or B', fill_all=False)
        >>> t.fill()
        >>> t.is_full
        True
        >>> t.fill()
        Traceback (most recent call last):
        tt.errors.state.AlreadyFullTableError: Cannot fill an already-full \
table

    """ class RequiresFullTableError(StateError):
    """An exception to be raised when a full table is required.

    .. code-block:: python

        >>> from tt import TruthTable
        >>> t = TruthTable('A or B', fill_all=False)
        >>> t.equivalent_to('A or B')
        Traceback (most recent call last):
        tt.errors.state.RequiresFullTableError: Equivalence can only be \
checked on full truth tables

    """ class ExtraSymbolError(SymbolError):
    """An exception for a passed token that is not a parsed symbol.

    Here's a quick table example::

        >>> from tt import TruthTable
        >>> t = TruthTable('A or B', ordering=['A', 'B', 'C'])
        Traceback (most recent call last):
            ...
        tt.errors.symbols.ExtraSymbolError: Received unexpected symbols: "C"

    """ class MissingSymbolError(SymbolError):
    """An exception type for a missing token value in evaluation.

    .. code-block:: python

        >>> from tt import BooleanExpression
        >>> b = BooleanExpression('A and B')
        >>> b.evaluate(A=1)
        Traceback (most recent call last):
            ...
        tt.errors.symbols.MissingSymbolError: Did not receive value for the \
following symbols: "B"

    """ class BooleanExpression(object):

    """An interface for interacting with a Boolean expression.

    Instances of ``BooleanExpression`` are meant to be immutable and can be
    instantiated from a few different representations of expressions. The
    simplest way to make an expression object is from a string::

        >>> from tt import BooleanExpression
        >>> BooleanExpression('(A or B) iff (C and D)')
        <BooleanExpression "(A or B) iff (C and D)">

    If you already have an instance of :class:`ExpressionTreeNode \
    <tt.trees.tree_node.ExpressionTreeNode>` laying around, you can make a
    new expression object from that, too::

        >>> from tt import ExpressionTreeNode
        >>> tree_root = ExpressionTreeNode.build_tree(
        ...     ['A', 'B', 'or',
        ...      'C', 'D', 'and',
        ...      'iff'])
        >>> BooleanExpression(tree_root)
        <BooleanExpression "(A or B) iff (C and D)">

    Additionally, any sub-tree node can be used to build an expression object.
    Continuing from above, let's make a new expression object for each of the
    sub-expressions wrapped in parentheses::

        >>> BooleanExpression(tree_root.l_child)
        <BooleanExpression "A or B">
        >>> BooleanExpression(tree_root.r_child)
        <BooleanExpression "C and D">

    Expressions also implement the equality and inequality operators (``==``
    and ``!=``). Equality is determined by the same semantic structure and the
    same operand names; the string used to represent the operators in two
    expressions is not taken into account. Here's a few examples::

        >>> from tt import BooleanExpression as be
        >>> be('A or B or C') == be('A or B or C')
        True
        >>> be('A or B or C') == be('A || B || C')
        True
        >>> be('A or B or C') == be('A or C or B')
        False

    :param expr: The expression representation from which this object is
        derived.
    :type expr: :class:`str <python:str>` or :class:`ExpressionTreeNode \
        <tt.trees.tree_node.ExpressionTreeNode>`

    :raises BadParenPositionError: If the passed expression contains a
        parenthesis in an invalid position.
    :raises EmptyExpressionError: If the passed expressions contains nothing
        other than whitespace.
    :raises ExpressionOrderError: If the expression contains invalid
        consecutive operators or operands.
    :raises InvalidArgumentTypeError: If ``expr`` is not an acceptable type.
    :raises InvalidIdentifierError: If any parsed variable symbols in the
        expression are invalid identifiers.
    :raises UnbalancedParenError: If any parenthesis pairs remain unbalanced.

    It is important to note that aside from :exc:`InvalidArgumentTypeError \
    <tt.errors.arguments.InvalidArgumentTypeError>`, all exceptions raised in
    expression initialization will be descendants of :exc:`GrammarError \
    <tt.errors.grammar.GrammarError>`.

    """

    def __init__(self, expr):
        if not isinstance(expr, (str, ExpressionTreeNode)):
            raise InvalidArgumentTypeError(
                'expr must be a str or ExpressionTreeNode')

        self._symbols = []
        self._symbol_set = set()
        self._tokens = []
        self._postfix_tokens = []

        if isinstance(expr, str):
            self._init_from_str(expr)
        elif isinstance(expr, ExpressionTreeNode):
            self._init_from_expr_node(expr)

        self._symbol_vals_factory = boolean_variables_factory(self._symbols)
        self._tree = ExpressionTreeNode.build_tree(self._postfix_tokens)
        self._constraints = {}
        self._constrained_symbol_set = set()

    def _init_from_expr_node(self, expr_node):
        """Initalize this object from an expression node."""
        self._raw_expr = ''

        with self._symbol_set_includes_constant_values():
            self._init_from_expr_node_recursive_helper(expr_node)

    def _init_from_expr_node_recursive_helper(self, expr_node, parent=None):
        """Recursive helper for initializing from an expression node.

        This method will populate the ``_symbols``, ``_symbol_set``,
        ``_postfix_tokens``, ``_tokens``, and ``_raw_expr`` attributes of this
         object.

        """
        if isinstance(expr_node, OperandExpressionTreeNode):
            operand_str = expr_node.symbol_name

            self._tokens.append(operand_str)
            self._postfix_tokens.append(operand_str)
            self._raw_expr += operand_str
            if operand_str not in self._symbol_set:
                self._symbols.append(operand_str)
                self._symbol_set.add(operand_str)
        elif isinstance(expr_node, UnaryOperatorExpressionTreeNode):
            operator_str = expr_node.symbol_name

            self._tokens.append(operator_str)

            self._raw_expr += operator_str
            if operator_str not in SYMBOLIC_OPERATOR_MAPPING:
                self._raw_expr += ' '

            self._init_from_expr_node_recursive_helper(
                expr_node.l_child, parent=expr_node)
            self._postfix_tokens.append(operator_str)
        elif isinstance(expr_node, BinaryOperatorExpressionTreeNode):
            operator_str = expr_node.symbol_name
            include_parens = True

            if parent is None:
                include_parens = False
            elif isinstance(parent, BinaryOperatorExpressionTreeNode):
                this_operator = OPERATOR_MAPPING[operator_str]
                parent_operator = OPERATOR_MAPPING[parent.symbol_name]
                if (expr_node is parent.r_child and
                        this_operator == parent_operator):
                    include_parens = False
                elif (expr_node is parent.l_child and
                        this_operator == parent_operator and
                        (parent.r_child.is_really_unary or
                            this_operator == parent.r_child.operator)):
                    include_parens = False

            if include_parens:
                self._tokens.append('(')
                self._raw_expr += '('

            self._init_from_expr_node_recursive_helper(
                expr_node.l_child, parent=expr_node)

            self._tokens.append(operator_str)
            self._raw_expr += (' ' + operator_str + ' ')

            self._init_from_expr_node_recursive_helper(
                expr_node.r_child, parent=expr_node)

            if include_parens:
                self._tokens.append(')')
                self._raw_expr += ')'

            self._postfix_tokens.append(operator_str)

    def _init_from_str(self, raw_expr_str):
        """Initalize this object from a raw expression string."""
        self._raw_expr = raw_expr_str.strip()

        with self._symbol_set_includes_constant_values():
            self._tokenize()
            self._to_postfix()

    @property
    def is_cnf(self):
        """Whether this expression is in conjunctive norma form or not.

        :type: :class:`bool <python:bool>`

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('(A or ~B) and (~C or D or E) and F')
            >>> b.is_cnf
            True
            >>> b = BooleanExpression('A nand B')
            >>> b.is_cnf
            False

        """
        return self._tree.is_cnf

    @property
    def is_dnf(self):
        """Whether this expression is in conjunctive normal form or not.

        :type: :class:`bool <python:bool>`

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('(A and B) or (~C and D)')
            >>> b.is_dnf
            True
            >>> b = BooleanExpression('(op1 or !op2) and (op3 or op4)')
            >>> b.is_dnf
            False

        """
        return self._tree.is_dnf

    @property
    def raw_expr(self):
        """The raw string expression, parsed upon initialization.

        This is what you pass into the ``BooleanExpression`` constructor; it is
        kept on the object as an attribute for convenience.

        :type: :class:`str <python:str>`

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('A nand B')
            >>> b.raw_expr
            'A nand B'

        """
        return self._raw_expr

    @property
    def symbols(self):
        """The list of unique symbols present in this expression.

        The order of the symbols in this list matches the order of symbol
        appearance in the original expression.

        :type: List[:class:`str <python:str>`]

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('A xor (B or C)')
            >>> b.symbols
            ['A', 'B', 'C']

        """
        return self._symbols

    @property
    def tokens(self):
        """The parsed, non-whitespace tokens of an expression.

        :type: List[:class:`str <python:str>`]

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('A xor (B or C)')
            >>> b.tokens
            ['A', 'xor', '(', 'B', 'or', 'C', ')']

        """
        return self._tokens

    @property
    def postfix_tokens(self):
        """Similar to the ``tokens`` attribute, but in postfix order.

        :type: List[:class:`str <python:str>`]

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('A xor (B or C)')
            >>> b.postfix_tokens
            ['A', 'B', 'C', 'or', 'xor']

        """
        return self._postfix_tokens

    @property
    def tree(self):
        """The tree node representing the root of the tree of this expression.

        :type: :class:`ExpressionTreeNode \
            <tt.trees.tree_node.ExpressionTreeNode>`

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('A xor (B or C)')
            >>> print(b.tree)
            xor
            `----A
            `----or
                 `----B
                 `----C

        """
        return self._tree

    def __eq__(self, other):
        if isinstance(other, BooleanExpression):
            return self._tree == other._tree
        else:
            return NotImplemented

    def __ne__(self, other):
        return not (self == other)

    def __str__(self):
        return self._raw_expr

    def __repr__(self):
        return '<BooleanExpression "{}">'.format(self._raw_expr)

    @contextmanager
    def constrain(self, **kwargs):
        """A context manager to impose satisfiability constraints.

        This is the interface for adding assumptions to the satisfiability
        solving functionality provided through the :func:`sat_one` and
        :func:`sat_all` methods.

        It should be noted that this context manager is only designed to work
        with the satisfiability-related functionality of this class.
        Constrained symbol values will not have an effect on non-sat methods of
        this class. For example::

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('(A or B) and (C or D)')
            >>> with b.constrain(A=1):
            ...     b.evaluate(A=0, B=1, C=1, D=0)
            ...
            True

        This context manager returns a reference to the same object upon which
        it is called. This behavior is designed with the following use case in
        mind::

            >>> from tt import BooleanExpression
            >>> with BooleanExpression('A or B').constrain(A=1, B=0) as b:
            ...     b.sat_one()
            ...
            <BooleanValues [A=1, B=0]>

        :param kwargs: Keys are names of symbols in this expression; the
            specified value for each of these keys will be added to the
            ``constraints`` attribute of this object for the duration of the
            context manager.

        :returns: A reference to the same object that called this method
            (i.e., ``self`` in the context of this method).
        :rtype: :class:`BooleanExpression`

        :raises AlreadyConstrainedSymbolError: If trying to constrain this
            expression with multiple context managers.
        :raises ExtraSymbolError: If a symbol not in this expression is passed
            through ``kwargs``.
        :raises InvalidArgumentValueError: If no contraints are specified
            (i.e., ``kwargs`` is empty).
        :raises InvalidBooleanValueError: If any values from ``kwargs`` are not
            valid Boolean inputs.

        """
        if not kwargs:
            raise InvalidArgumentValueError(
                'Must specify at least one constraint')

        assert_all_valid_keys(kwargs, self._symbol_set)

        kwarg_key_set = set(kwargs.keys())
        conflicts = self._constrained_symbol_set & kwarg_key_set
        if conflicts:
            symbols_str = ', '.join('"{}"'.format(s) for s in
                                    sorted(conflicts))
            raise AlreadyConstrainedSymbolError(
                'Symbol' + (' ' if len(conflicts) == 1 else 's ') +
                symbols_str + ' cannot be constrained multiple times')

        self._constraints.update(kwargs)
        self._constrained_symbol_set |= kwarg_key_set
        yield self
        self._constrained_symbol_set -= kwarg_key_set
        self._constraints = {}

    def sat_one(self):
        """Find a combination of inputs that satisfies this expression.

        Under the hood, this method is using the functionality exposed in tt's
        :mod:`satisfiability.picosat <tt.satisfiability.picosat>` module.

        Here's a simple example of satisfying an expression::

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('A xor 1')
            >>> b.sat_one()
            <BooleanValues [A=0]>

        Don't forget about the utility provided by the :func:`constrain`
        context manager::

            >>> b = BooleanExpression('(A nand B) iff C')
            >>> with b.constrain(A=1, C=1):
            ...     b.sat_one()
            ...
            <BooleanValues [A=1, B=0, C=1]>

        Finally, here's an example when the expression cannot be satisfied::

            >>> with BooleanExpression('A xor 1').constrain(A=1) as b:
            ...     b.sat_one() is None
            ...
            True

        :returns: :func:`namedtuple <python:collections.namedtuple>`-like
            object representing a satisfying set of values (see
            :func:`boolean_variables_factory \
            <tt.definitions.operands.boolean_variables_factory>` for more
            information about the type of object returned); ``None``
            will be returned if no satisfiable set of inputs exists.
        :rtype: :func:`namedtuple <python:collections.namedtuple>`-like object
            or ``None``

        :raises NoEvaluationVariationError: If this is an expression of only
            constants.

        """
        if not self._symbols:
            raise NoEvaluationVariationError(
                'Cannot attempt to satisfy an expression of only constants')

        if not (self._symbol_set - self._constrained_symbol_set):
            # shortcut if all symbols are constrained
            if self.evaluate_unchecked(**self._constraints):
                return self._symbol_vals_factory(**self._constraints)
            else:
                return None

        clauses, assumptions, symbol_to_index_map, index_to_symbol_map = \
            self._to_picosat_clauses_assumptions_and_symbol_mappings()
        if not assumptions:
            # cannot pass empty list of assumptions to picosat
            assumptions = None

        picosat_result = picosat.sat_one(clauses, assumptions=assumptions)
        if picosat_result is None:
            return None

        result_dict = self._picosat_result_as_dict(
            picosat_result, symbol_to_index_map, index_to_symbol_map)
        return self._symbol_vals_factory(**result_dict)

    def sat_all(self):
        """Find all combinations of inputs that satisfy this expression.

        Under the hood, this method is using the functionality exposed in tt's
        :mod:`satisfiability.picosat <tt.satisfiability.picosat>` module.

        Here's a simple example of iterating through a few SAT solutions::

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('(A xor B) and (C xor D)')
            >>> for solution in b.sat_all():
            ...     print(solution)
            ...
            A=1, B=0, C=1, D=0
            A=1, B=0, C=0, D=1
            A=0, B=1, C=0, D=1
            A=0, B=1, C=1, D=0

        We can also constrain away a few of those solutions::

            >>> with b.constrain(A=1, C=0):
            ...     for solution in b.sat_all():
            ...         print(solution)
            ...
            A=1, B=0, C=0, D=1

        :returns: An iterator of
            :func:`namedtuple <python:collections.namedtuple>`-like objects
            representing satisfying combinations of inputs; if no satisfying
            solutions exist, the iterator will be empty.
        :rtype: Iterator[:func:`namedtuple <python:collections.namedtuple>`
            -like objects]

        :raises NoEvaluationVariationError: If this is an expression of only
            constants.

        """
        if not self._symbols:
            raise NoEvaluationVariationError(
                'Cannot attempt to satisfy an expression of only constants')

        if not (self._symbol_set - self._constrained_symbol_set):
            # shortcut if all symbols are constrained
            if self.evaluate_unchecked(**self._constraints):
                yield self._symbol_vals_factory(**self._constraints)
            else:
                # empty iterator
                while False:
                    yield None
            return

        clauses, assumptions, symbol_to_index_map, index_to_symbol_map = \
            self._to_picosat_clauses_assumptions_and_symbol_mappings()
        if not assumptions:
            # cannot pass empty list of assumptions to picosat
            assumptions = None

        for picosat_sol in picosat.sat_all(clauses, assumptions=assumptions):
            result_dict = self._picosat_result_as_dict(
                picosat_sol, symbol_to_index_map, index_to_symbol_map)
            yield self._symbol_vals_factory(**result_dict)

    def _picosat_result_as_dict(self, results, symbol_to_index_map,
                                index_to_symbol_map):
        """Convert a PicoSAT result into a BooleanValues tuple."""
        result_dict = {}
        signed_symbol_indices = (index for index in results if abs(index) in
                                 index_to_symbol_map)
        for index in signed_symbol_indices:
            symbol_name = index_to_symbol_map[abs(index)]
            result_dict[symbol_name] = index > 0

        return result_dict

    def _to_picosat_clauses_assumptions_and_symbol_mappings(self):
        """Return a PicoSAT-compatible representation and helpful metadata."""
        cnf_tree = self.tree if self.is_cnf else self.tree.to_cnf()
        index = 1
        symbol_to_index_map = {}
        index_to_symbol_map = {}
        clauses = []
        assumptions = []

        for clause_root in cnf_tree.iter_cnf_clauses():
            clause_indices = []
            for node in clause_root.iter_dnf_clauses():
                is_negated = isinstance(node, UnaryOperatorExpressionTreeNode)
                symbol_str = (node.l_child.symbol_name if is_negated else
                              node.symbol_name)

                if symbol_str in symbol_to_index_map:
                    pos = symbol_to_index_map[symbol_str]
                    if is_negated:
                        clause_indices.append(-pos)
                    else:
                        clause_indices.append(pos)
                elif symbol_str == '0':
                    clause_indices.append(index)
                    if is_negated:
                        assumptions.append(index)
                    else:
                        assumptions.append(-index)
                    index += 1
                elif symbol_str == '1':
                    clause_indices.append(index)
                    if is_negated:
                        assumptions.append(-index)
                    else:
                        assumptions.append(index)
                    index += 1
                else:
                    symbol_to_index_map[symbol_str] = index
                    index_to_symbol_map[index] = symbol_str
                    if is_negated:
                        clause_indices.append(-index)
                    else:
                        clause_indices.append(index)
                    index += 1

            clauses.append(clause_indices)

        for symbol_str, assumed_val in self._constraints.items():
            index = symbol_to_index_map[symbol_str]
            if assumed_val:
                assumptions.append(index)
            else:
                assumptions.append(-index)

        return clauses, assumptions, symbol_to_index_map, index_to_symbol_map

    def evaluate(self, **kwargs):
        """Evaluate the Boolean expression for the passed keyword arguments.

        This is a checked wrapper around the :func:`evaluate_unchecked`
        function.

        :param kwargs: Keys are names of symbols in this expression; the
            specified value for each of these keys will be substituted into the
            expression for evaluation.

        :returns: The result of evaluating the expression.
        :rtype: :class:`bool <python:bool>`

        :raises ExtraSymbolError: If a symbol not in this expression is passed
            through ``kwargs``.
        :raises MissingSymbolError: If any symbols in this expression are not
            passed through ``kwargs``.
        :raises InvalidBooleanValueError: If any values from ``kwargs`` are not
            valid Boolean inputs.
        :raises InvalidIdentifierError: If any symbol names are invalid
            identifiers.

        Usage::

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('A or B')
            >>> b.evaluate(A=0, B=0)
            False
            >>> b.evaluate(A=1, B=0)
            True

        """
        assert_all_valid_keys(kwargs, self._symbol_set)
        assert_iterable_contains_all_expr_symbols(
            kwargs.keys(), self._symbol_set)

        return self.evaluate_unchecked(**kwargs)

    def evaluate_unchecked(self, **kwargs):
        """Evaluate the Boolean expression without checking the input.

        This is used for evaluation by the :func:`evaluate` method, which
        validates the input ``kwargs`` before passing them to this method.

        :param kwargs: Keys are names of symbols in this expression; the
            specified value for each of these keys will be substituted into the
            expression for evaluation.

        :returns: The Boolean result of evaluating the expression.
        :rtype: :class:`bool <python:bool>`

        """
        truthy = self._tree.evaluate(kwargs)
        return bool(truthy)

    def iter_clauses(self):
        """Iterate over the clauses in this expression.

        An expression must be in conjunctive normal form (CNF) or disjunctive
        normal form (DNF) in order to iterate over its clauses. Here's a simple
        example::

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('(~A or B) and (C or D) and (~E or ~F)')
            >>> for clause in b.iter_clauses():
            ...     clause
            ...
            <BooleanExpression "~A or B">
            <BooleanExpression "C or D">
            <BooleanExpression "~E or ~F">

        In the case of an ambiguous expression form (between CNF and DNF), the
        clauses will be interpreted to be in CNF form. For example::

            >>> b = BooleanExpression('A and ~B and C')
            >>> b.is_cnf
            True
            >>> b.is_dnf
            True
            >>> print(', '.join(str(clause) for clause in b.iter_clauses()))
            A, ~B, C

        If you want to enforce a specific CNF or DNF interpretation of the
        clauses, take a look at :func:`iter_cnf_clauses` and
        :func:`iter_dnf_clauses`.

        :returns: An iterator of expression objects, each representing a
            separate clause of this expression.
        :rtype: Iterator[:class:`BooleanExpression`]

        :raises RequiresNormalFormError: If this expression is not in
            conjunctive or disjunctive normal form.

        """
        for node in self._tree.iter_clauses():
            yield BooleanExpression(node)

    def iter_cnf_clauses(self):
        """Iterate over the CNF clauses in this expression.

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('(A or B) and ~C')
            >>> for clause in b.iter_cnf_clauses():
            ...     print(clause)
            ...
            A or B
            ~C

        :returns: An iterator of expression objects, each representing a
            separate CNF clause of this expression.
        :rtype: Iterator[:class:`BooleanExpression`]

        :raises RequiresNormalFormError: If this expression is not in
            conjunctive normal form.

        """
        for node in self._tree.iter_cnf_clauses():
            yield BooleanExpression(node)

    def iter_dnf_clauses(self):
        """Iterate over the DNF clauses in this expression.

        .. code-block:: python

            >>> from tt import BooleanExpression
            >>> b = BooleanExpression('(A and ~B) or (C and D and E)')
            >>> for clause in b.iter_dnf_clauses():
            ...     print(clause)
            ...
            A and ~B
            C and D and E

        :returns: An iterator of expression objects, each representing a
            separate DNF clause of this expression.
        :rtype: Iterator[:class:`BooleanExpression`]

        :raises RequiresNormalFormError: If this expression is not in
            disjunctive normal form.

        """
        for node in self._tree.iter_dnf_clauses():
            yield BooleanExpression(node)

    def _tokenize(self):
        """Make the first pass through the expression, tokenizing it.

        This method is a helper for initializing an expression object from a
        string and will populate the ``_symbols``, ``_symbol_set``, and
        ``_tokens`` attributes of this object.

        :raises GrammarError: If a malformed expression is received.

        """
        operator_strs = [k for k in OPERATOR_MAPPING.keys()]
        is_symbolic = {op: not op[0].isalpha() for op in operator_strs}
        operator_search_list = sorted(operator_strs, key=len, reverse=True)
        delimiters = DELIMITERS | set(k[0] for k, v in is_symbolic.items()
                                      if v)
        EXPECTING_OPERAND = 1
        EXPECTING_OPERATOR = 2
        grammar_state = EXPECTING_OPERAND

        idx = 0
        open_paren_count = 0
        num_chars = len(self._raw_expr)

        while idx < num_chars:
            c = self._raw_expr[idx].strip()

            if not c:
                # do nothing
                idx += 1
            elif c == '(':
                if grammar_state != EXPECTING_OPERAND:
                    raise BadParenPositionError('Unexpected parenthesis',
                                                self._raw_expr, idx)

                open_paren_count += 1
                self._tokens.append(c)
                idx += 1
            elif c == ')':
                if grammar_state != EXPECTING_OPERATOR:
                    raise BadParenPositionError('Unexpected parenthesis',
                                                self._raw_expr, idx)
                elif not open_paren_count:
                    raise UnbalancedParenError('Unbalanced parenthesis',
                                               self._raw_expr, idx)

                open_paren_count -= 1
                self._tokens.append(c)
                idx += 1
            else:
                is_operator = False
                num_chars_remaining = num_chars - idx

                matching_operators = [
                    operator for operator in operator_search_list
                    if len(operator) <= num_chars_remaining and
                    self._raw_expr[idx:(idx+len(operator))] == operator]

                if matching_operators:
                    match = matching_operators[0]
                    match_length = len(match)
                    next_c_pos = idx + match_length
                    next_c = (None if next_c_pos >= num_chars else
                              self._raw_expr[idx + match_length])

                    if next_c is None:
                        # trailing operator
                        raise ExpressionOrderError(
                            'Unexpected operator "{}"'.format(match),
                            self._raw_expr, idx)

                    if next_c in delimiters or is_symbolic[match]:
                        if OPERATOR_MAPPING[match] == TT_NOT_OP:
                            if grammar_state != EXPECTING_OPERAND:
                                raise ExpressionOrderError(
                                    'Unexpected unary operator "{}"'.format(
                                        match), self._raw_expr, idx)
                        else:
                            if grammar_state != EXPECTING_OPERATOR:
                                raise ExpressionOrderError(
                                    'Unexpected binary operator "{}"'.format(
                                        match), self._raw_expr, idx)
                            grammar_state = EXPECTING_OPERAND

                        is_operator = True
                        self._tokens.append(match)
                        idx += match_length

                if not is_operator:
                    if grammar_state != EXPECTING_OPERAND:
                        raise ExpressionOrderError('Unexpected operand',
                                                   self._raw_expr, idx)

                    operand_end_idx = idx + 1
                    while (operand_end_idx < num_chars and
                           self._raw_expr[operand_end_idx] not in delimiters):
                        operand_end_idx += 1

                    operand = self._raw_expr[idx:operand_end_idx]
                    if (operand not in CONSTANT_VALUES and
                            not is_valid_identifier(operand)):
                        raise InvalidIdentifierError(
                            'Invalid operand name "{}"'.format(operand),
                            self._raw_expr, idx)

                    self._tokens.append(operand)
                    if operand not in self._symbol_set:
                        self._symbols.append(operand)
                        self._symbol_set.add(operand)

                    idx = operand_end_idx
                    grammar_state = EXPECTING_OPERATOR

        if open_paren_count:
            left_paren_positions = [m.start() for m in
                                    re.finditer(r'\(', self._raw_expr)]
            raise UnbalancedParenError(
                'Unbalanced left parenthesis', self._raw_expr,
                left_paren_positions[open_paren_count-1])

        if not self._tokens:
            raise EmptyExpressionError('Empty expression is invalid')

    def _to_postfix(self):
        """Populate the ``_postfix_tokens`` attribute."""
        stack = []

        for token in self._tokens:
            if token in self._symbol_set:
                self._postfix_tokens.append(token)
            elif token == '(':
                stack.append(token)
            elif token in OPERATOR_MAPPING.keys():
                if not stack:
                    stack.append(token)
                else:
                    while (stack and stack[-1] != '(' and
                            OPERATOR_MAPPING[stack[-1]].precedence >
                            OPERATOR_MAPPING[token].precedence):
                        self._postfix_tokens.append(stack.pop())
                    stack.append(token)
            elif token == ')':
                while stack and stack[-1] != '(':
                    self._postfix_tokens.append(stack.pop())
                stack.pop()

        for token in reversed(stack):
            self._postfix_tokens.append(token)

    @contextmanager
    def _symbol_set_includes_constant_values(self):
        """Context manager to include CONSTANT_VALUES in _symbol_set."""
        self._symbol_set |= CONSTANT_VALUES
        yield
        self._symbol_set -= CONSTANT_VALUES
import itertools
from math import log
from string import ascii_uppercase as ALPHABET
from tt._assertions import (
    assert_all_valid_keys,
    assert_iterable_contains_all_expr_symbols)
from tt.definitions import (
    boolean_variables_factory,
    DONT_CARE_VALUE,
    is_valid_identifier)
from tt.errors import (
    AlreadyFullTableError,
    ConflictingArgumentsError,
    ExtraSymbolError,
    InvalidArgumentTypeError,
    InvalidArgumentValueError,
    InvalidBooleanValueError,
    InvalidIdentifierError,
    MissingSymbolError,
    NoEvaluationVariationError,
    RequiredArgumentError,
    RequiresFullTableError)
from tt.expressions import BooleanExpression
        +---+---+---+
        | A | B |   |
        +---+---+---+
        | 0 | 0 | 0 |
        +---+---+---+
        | 0 | 1 | 1 |
        +---+---+---+
        | 1 | 0 | 1 |
        +---+---+---+
        | 1 | 1 | 0 |
        +---+---+---+

    When manually specifying the values tt can generate the symbols for you::

        >>> from tt import TruthTable
        >>> t = TruthTable(from_values='0110')
        >>> print(t)
        +---+---+---+
        | A | B |   |
        +---+---+---+
        | 0 | 0 | 0 |
        +---+---+---+
        | 0 | 1 | 1 |
        +---+---+---+
        | 1 | 0 | 1 |
        +---+---+---+
        | 1 | 1 | 0 |
        +---+---+---+

    You can also specify the symbol names yourself, if you'd like::

        >>> from tt import TruthTable
        >>> t = TruthTable(from_values='0110', ordering=['tt', 'rocks'])
        >>> print(t)
        +----+-------+---+
        | tt | rocks |   |
        +----+-------+---+
        | 0  |   0   | 0 |
        +----+-------+---+
        | 0  |   1   | 1 |
        +----+-------+---+
        | 1  |   0   | 1 |
        +----+-------+---+
        | 1  |   1   | 0 |
        +----+-------+---+

    :param expr: The expression with which to populate this truth table. If
        this argument is omitted, then the ``from_values`` argument must be
        properly set.
    :type expr: :class:`str <python:str>` or :class:`BooleanExpression\
        <tt.expressions.bexpr.BooleanExpression>`

    :param from_values: A string of 1's, 0's, and x's representing the values
        to be stored in the table; the length of this string must be a power
        of 2 and is the complete set of values (in sequential order) to be
        stored in table.
    :type from_values: :class:`str <python:str>`

    :param fill_all: A flag indicating whether the entirety of the table should
        be filled on initialization; defaults to ``True``.
    :type fill_all: :class:`bool <python:bool>`, optional

    :param ordering: An input that maps to this class's :attr:`ordering`
        property. If omitted, the ordering of symbols in the table will match
        that of the symbols' appearance in the original expression.
    :type ordering: List[:class:`str <python:str>`], optional

    :raises ConflictingArgumentsError: If both ``expr`` and ``from_values`` are
        specified in the initalization; a table can only be instantiated from
        one or the other.
    :raises DuplicateSymbolError: If multiple symbols of the same name are
        passed into the ``ordering`` list.
    :raises ExtraSymbolError: If a symbol not present in the expression is
        passed into the ``ordering`` list.
    :raises MissingSymbolError: If a symbol present in the expression is
        omitted from the ``ordering`` list.
    :raises InvalidArgumentTypeError: If an unexpected parameter type is
        encountered.
    :raises InvalidArgumentValueError: If the number of values specified via
        ``from_values`` is not a power of 2 or the ``ordering`` list (when
        filling the table using ``from_values``) is empty.
    :raises InvalidIdentifierError: If any symbol names specified in
        ``ordering`` are not valid identifiers.
    :raises NoEvaluationVariationError: If an expression without any unqiue
        symbols (i.e., one merely composed of constant operands) is specified.
    :raises RequiredArgumentError: If neither the ``expr`` or ``from_values``
        arguments are specified.

    """

    def __init__(self, expr=None, from_values=None, fill_all=True,
                 ordering=None):
        if expr is not None and from_values is not None:
            raise ConflictingArgumentsError(
                '`expr` and `from_values` are mutually exclusive arguments')
        elif expr is None and from_values is None:
            raise RequiredArgumentError(
                'Must specify either `expr` or `from_values`')

        self._num_filled_slots = 0

        if expr is not None:
            self._init_from_expression(expr, fill_all, ordering)
        else:
            self._init_from_values(from_values, ordering)

        self._symbol_vals_factory = boolean_variables_factory(self._ordering)

    def _init_from_expression(self, expr, fill_all, ordering):
        if isinstance(expr, str):
            self._expr = BooleanExpression(expr)
        elif isinstance(expr, BooleanExpression):
            self._expr = expr
        else:
            raise InvalidArgumentTypeError(
                'Arg `expr` must be of type `str` or `BooleanExpression`')

        if ordering is None:
            self._ordering = self._expr.symbols
        else:

            assert_iterable_contains_all_expr_symbols(