1"""Logic expressions handling
2
3NOTE
4----
5
6at present this is mainly needed for facts.py , feel free however to improve
7this stuff for general purpose.
8"""
9
10from typing import Dict, Type, Union
11
12
13# Type of a fuzzy bool
14FuzzyBool = Union[bool, None]
15
16
17def _torf(args):
18    """Return True if all args are True, False if they
19    are all False, else None.
20
21    >>> from sympy.core.logic import _torf
22    >>> _torf((True, True))
23    True
24    >>> _torf((False, False))
25    False
26    >>> _torf((True, False))
27    """
28    sawT = sawF = False
29    for a in args:
30        if a is True:
31            if sawF:
32                return
33            sawT = True
34        elif a is False:
35            if sawT:
36                return
37            sawF = True
38        else:
39            return
40    return sawT
41
42
43def _fuzzy_group(args, quick_exit=False):
44    """Return True if all args are True, None if there is any None else False
45    unless ``quick_exit`` is True (then return None as soon as a second False
46    is seen.
47
48     ``_fuzzy_group`` is like ``fuzzy_and`` except that it is more
49    conservative in returning a False, waiting to make sure that all
50    arguments are True or False and returning None if any arguments are
51    None. It also has the capability of permiting only a single False and
52    returning None if more than one is seen. For example, the presence of a
53    single transcendental amongst rationals would indicate that the group is
54    no longer rational; but a second transcendental in the group would make the
55    determination impossible.
56
57
58    Examples
59    ========
60
61    >>> from sympy.core.logic import _fuzzy_group
62
63    By default, multiple Falses mean the group is broken:
64
65    >>> _fuzzy_group([False, False, True])
66    False
67
68    If multiple Falses mean the group status is unknown then set
69    `quick_exit` to True so None can be returned when the 2nd False is seen:
70
71    >>> _fuzzy_group([False, False, True], quick_exit=True)
72
73    But if only a single False is seen then the group is known to
74    be broken:
75
76    >>> _fuzzy_group([False, True, True], quick_exit=True)
77    False
78
79    """
80    saw_other = False
81    for a in args:
82        if a is True:
83            continue
84        if a is None:
85            return
86        if quick_exit and saw_other:
87            return
88        saw_other = True
89    return not saw_other
90
91
92def fuzzy_bool(x):
93    """Return True, False or None according to x.
94
95    Whereas bool(x) returns True or False, fuzzy_bool allows
96    for the None value and non-false values (which become None), too.
97
98    Examples
99    ========
100
101    >>> from sympy.core.logic import fuzzy_bool
102    >>> from sympy.abc import x
103    >>> fuzzy_bool(x), fuzzy_bool(None)
104    (None, None)
105    >>> bool(x), bool(None)
106    (True, False)
107
108    """
109    if x is None:
110        return None
111    if x in (True, False):
112        return bool(x)
113
114
115def fuzzy_and(args):
116    """Return True (all True), False (any False) or None.
117
118    Examples
119    ========
120
121    >>> from sympy.core.logic import fuzzy_and
122    >>> from sympy import Dummy
123
124    If you had a list of objects to test the commutivity of
125    and you want the fuzzy_and logic applied, passing an
126    iterator will allow the commutativity to only be computed
127    as many times as necessary. With this list, False can be
128    returned after analyzing the first symbol:
129
130    >>> syms = [Dummy(commutative=False), Dummy()]
131    >>> fuzzy_and(s.is_commutative for s in syms)
132    False
133
134    That False would require less work than if a list of pre-computed
135    items was sent:
136
137    >>> fuzzy_and([s.is_commutative for s in syms])
138    False
139    """
140
141    rv = True
142    for ai in args:
143        ai = fuzzy_bool(ai)
144        if ai is False:
145            return False
146        if rv:  # this will stop updating if a None is ever trapped
147            rv = ai
148    return rv
149
150
151def fuzzy_not(v):
152    """
153    Not in fuzzy logic
154
155    Return None if `v` is None else `not v`.
156
157    Examples
158    ========
159
160    >>> from sympy.core.logic import fuzzy_not
161    >>> fuzzy_not(True)
162    False
163    >>> fuzzy_not(None)
164    >>> fuzzy_not(False)
165    True
166
167    """
168    if v is None:
169        return v
170    else:
171        return not v
172
173
174def fuzzy_or(args):
175    """
176    Or in fuzzy logic. Returns True (any True), False (all False), or None
177
178    See the docstrings of fuzzy_and and fuzzy_not for more info.  fuzzy_or is
179    related to the two by the standard De Morgan's law.
180
181    >>> from sympy.core.logic import fuzzy_or
182    >>> fuzzy_or([True, False])
183    True
184    >>> fuzzy_or([True, None])
185    True
186    >>> fuzzy_or([False, False])
187    False
188    >>> print(fuzzy_or([False, None]))
189    None
190
191    """
192    rv = False
193    for ai in args:
194        ai = fuzzy_bool(ai)
195        if ai is True:
196            return True
197        if rv is False:  # this will stop updating if a None is ever trapped
198            rv = ai
199    return rv
200
201
202def fuzzy_xor(args):
203    """Return None if any element of args is not True or False, else
204    True (if there are an odd number of True elements), else False."""
205    t = f = 0
206    for a in args:
207        ai = fuzzy_bool(a)
208        if ai:
209            t += 1
210        elif ai is False:
211            f += 1
212        else:
213            return
214    return t % 2 == 1
215
216
217def fuzzy_nand(args):
218    """Return False if all args are True, True if they are all False,
219    else None."""
220    return fuzzy_not(fuzzy_and(args))
221
222
223class Logic:
224    """Logical expression"""
225    # {} 'op' -> LogicClass
226    op_2class = {}  # type: Dict[str, Type[Logic]]
227
228    def __new__(cls, *args):
229        obj = object.__new__(cls)
230        obj.args = args
231        return obj
232
233    def __getnewargs__(self):
234        return self.args
235
236    def __hash__(self):
237        return hash((type(self).__name__,) + tuple(self.args))
238
239    def __eq__(a, b):
240        if not isinstance(b, type(a)):
241            return False
242        else:
243            return a.args == b.args
244
245    def __ne__(a, b):
246        if not isinstance(b, type(a)):
247            return True
248        else:
249            return a.args != b.args
250
251    def __lt__(self, other):
252        if self.__cmp__(other) == -1:
253            return True
254        return False
255
256    def __cmp__(self, other):
257        if type(self) is not type(other):
258            a = str(type(self))
259            b = str(type(other))
260        else:
261            a = self.args
262            b = other.args
263        return (a > b) - (a < b)
264
265    def __str__(self):
266        return '%s(%s)' % (self.__class__.__name__,
267                           ', '.join(str(a) for a in self.args))
268
269    __repr__ = __str__
270
271    @staticmethod
272    def fromstring(text):
273        """Logic from string with space around & and | but none after !.
274
275           e.g.
276
277           !a & b | c
278        """
279        lexpr = None  # current logical expression
280        schedop = None  # scheduled operation
281        for term in text.split():
282            # operation symbol
283            if term in '&|':
284                if schedop is not None:
285                    raise ValueError(
286                        'double op forbidden: "%s %s"' % (term, schedop))
287                if lexpr is None:
288                    raise ValueError(
289                        '%s cannot be in the beginning of expression' % term)
290                schedop = term
291                continue
292            if '&' in term or '|' in term:
293                raise ValueError('& and | must have space around them')
294            if term[0] == '!':
295                if len(term) == 1:
296                    raise ValueError('do not include space after "!"')
297                term = Not(term[1:])
298
299            # already scheduled operation, e.g. '&'
300            if schedop:
301                lexpr = Logic.op_2class[schedop](lexpr, term)
302                schedop = None
303                continue
304
305            # this should be atom
306            if lexpr is not None:
307                raise ValueError(
308                    'missing op between "%s" and "%s"' % (lexpr, term))
309
310            lexpr = term
311
312        # let's check that we ended up in correct state
313        if schedop is not None:
314            raise ValueError('premature end-of-expression in "%s"' % text)
315        if lexpr is None:
316            raise ValueError('"%s" is empty' % text)
317
318        # everything looks good now
319        return lexpr
320
321
322class AndOr_Base(Logic):
323
324    def __new__(cls, *args):
325        bargs = []
326        for a in args:
327            if a == cls.op_x_notx:
328                return a
329            elif a == (not cls.op_x_notx):
330                continue    # skip this argument
331            bargs.append(a)
332
333        args = sorted(set(cls.flatten(bargs)), key=hash)
334
335        for a in args:
336            if Not(a) in args:
337                return cls.op_x_notx
338
339        if len(args) == 1:
340            return args.pop()
341        elif len(args) == 0:
342            return not cls.op_x_notx
343
344        return Logic.__new__(cls, *args)
345
346    @classmethod
347    def flatten(cls, args):
348        # quick-n-dirty flattening for And and Or
349        args_queue = list(args)
350        res = []
351
352        while True:
353            try:
354                arg = args_queue.pop(0)
355            except IndexError:
356                break
357            if isinstance(arg, Logic):
358                if isinstance(arg, cls):
359                    args_queue.extend(arg.args)
360                    continue
361            res.append(arg)
362
363        args = tuple(res)
364        return args
365
366
367class And(AndOr_Base):
368    op_x_notx = False
369
370    def _eval_propagate_not(self):
371        # !(a&b&c ...) == !a | !b | !c ...
372        return Or(*[Not(a) for a in self.args])
373
374    # (a|b|...) & c == (a&c) | (b&c) | ...
375    def expand(self):
376
377        # first locate Or
378        for i in range(len(self.args)):
379            arg = self.args[i]
380            if isinstance(arg, Or):
381                arest = self.args[:i] + self.args[i + 1:]
382
383                orterms = [And(*(arest + (a,))) for a in arg.args]
384                for j in range(len(orterms)):
385                    if isinstance(orterms[j], Logic):
386                        orterms[j] = orterms[j].expand()
387
388                res = Or(*orterms)
389                return res
390
391        return self
392
393
394class Or(AndOr_Base):
395    op_x_notx = True
396
397    def _eval_propagate_not(self):
398        # !(a|b|c ...) == !a & !b & !c ...
399        return And(*[Not(a) for a in self.args])
400
401
402class Not(Logic):
403
404    def __new__(cls, arg):
405        if isinstance(arg, str):
406            return Logic.__new__(cls, arg)
407
408        elif isinstance(arg, bool):
409            return not arg
410        elif isinstance(arg, Not):
411            return arg.args[0]
412
413        elif isinstance(arg, Logic):
414            # XXX this is a hack to expand right from the beginning
415            arg = arg._eval_propagate_not()
416            return arg
417
418        else:
419            raise ValueError('Not: unknown argument %r' % (arg,))
420
421    @property
422    def arg(self):
423        return self.args[0]
424
425
426Logic.op_2class['&'] = And
427Logic.op_2class['|'] = Or
428Logic.op_2class['!'] = Not
429