· 7 years ago · Nov 16, 2018, 08:58 PM
1# coding: utf8
2#
3# AlgoPy.py
4#
5# Author : SCR 05/2016, 06/2018
6#
7# Intégration des types algorithmiques
8#
9# versions Python : 2.7, 3.4
10#
11# v3: intégration pour 2.7
12# v4: type file, suppression str.ecrire, lecture booléen, typage tableaux
13# v5: anglicisation
14
15# from forbiddenfruit import curse
16#
17# Intégration directe de la fonction curse du module forbiddenfruit
18# pour faciliter la distribution
19#
20# Author: Lincoln de Sousa
21# Home Page: https://github.com/clarete/forbiddenfruit
22#
23# Copyright (C) 2013 Lincoln Clarete <lincoln@comum.org>
24
25from __future__ import print_function
26
27import ctypes
28import inspect
29from functools import wraps
30from collections import defaultdict
31
32try:
33 import __builtin__
34except ImportError:
35 # Python 3 support
36 import builtins as __builtin__
37#import builtins as __builtin__
38
39#__version__ = '0.1.2'
40
41#__all__ = 'curse', 'curses', 'reverse'
42
43
44Py_ssize_t = \
45 hasattr(ctypes.pythonapi, 'Py_InitModule4_64') \
46 and ctypes.c_int64 or ctypes.c_int
47
48
49class PyObject(ctypes.Structure):
50 pass
51
52PyObject._fields_ = [
53 ('ob_refcnt', Py_ssize_t),
54 ('ob_type', ctypes.POINTER(PyObject)),
55]
56
57class SlotsProxy(PyObject):
58 _fields_ = [('dict', ctypes.POINTER(PyObject))]
59
60def patchable_builtin(klass):
61 # It's important to create variables here, we want those objects alive
62 # within this whole scope.
63 name = klass.__name__
64 target = klass.__dict__
65
66 # Hardcore introspection to find the `PyProxyDict` object that contains the
67 # precious `dict` attribute.
68 proxy_dict = SlotsProxy.from_address(id(target))
69 namespace = {}
70
71 # This is the way I found to `cast` this `proxy_dict.dict` into a python
72 # object, cause the `from_address()` function returns the `py_object`
73 # version
74 ctypes.pythonapi.PyDict_SetItem(
75 ctypes.py_object(namespace),
76 ctypes.py_object(name),
77 proxy_dict.dict,
78 )
79 return namespace[name]
80
81
82@wraps(__builtin__.dir)
83def __filtered_dir__(obj=None):
84 name = hasattr(obj, '__name__') and obj.__name__ or obj.__class__.__name__
85 if obj is None:
86 # Return names from the local scope of the calling frame, taking into
87 # account indirection added by __filtered_dir__
88 calling_frame = inspect.currentframe().f_back
89 return sorted(calling_frame.f_locals.keys())
90 return sorted(set(__dir__(obj)).difference(__hidden_elements__[name]))
91
92# Switching to the custom dir impl declared above
93__hidden_elements__ = defaultdict(list)
94__dir__ = dir
95__builtin__.dir = __filtered_dir__
96
97
98def curse(klass, attr, value, hide_from_dir=False):
99 """Curse a built-in `klass` with `attr` set to `value`
100
101 This function monkey-patches the built-in python object `attr` adding a new
102 attribute to it. You can add any kind of argument to the `class`.
103
104 It's possible to attach methods as class methods, just do the following:
105
106 >>> def myclassmethod(cls):
107 ... return cls(1.5)
108 >>> curse(float, "myclassmethod", classmethod(myclassmethod))
109 >>> float.myclassmethod()
110 1.5
111
112 Methods will be automatically bound, so don't forget to add a self
113 parameter to them, like this:
114
115 >>> def hello(self):
116 ... return self * 2
117 >>> curse(str, "hello", hello)
118 >>> "yo".hello()
119 "yoyo"
120 """
121 dikt = patchable_builtin(klass)
122
123 old_value = dikt.get(attr, None)
124 old_name = '_c_%s' % attr # do not use .format here, it breaks py2.{5,6}
125 if old_value:
126 dikt[old_name] = old_value
127
128 if old_value:
129 dikt[attr] = value
130
131 try:
132 dikt[attr].__name__ = old_value.__name__
133 except (AttributeError, TypeError): # py2.5 will raise `TypeError`
134 pass
135 try:
136 dikt[attr].__qualname__ = old_value.__qualname__
137 except AttributeError:
138 pass
139 else:
140 dikt[attr] = value
141
142 if hide_from_dir:
143 __hidden_elements__[klass.__name__].append(attr)
144#
145#
146# Fin extrait de forbiddenfruit
147#
148
149import sys
150import math
151import random
152
153#
154# lecture, écriture avec type :
155# input, lire, écrire, écrireF
156#
157
158if sys.version_info[0] > 2:
159 _input = __builtin__.input
160else:
161 _input = __builtin__.raw_input
162
163def _input_bool(*args):
164 inputString = _input(*args)
165 res = inputString.lower() == str(True).lower()
166 if not (res or inputString.lower() == str(False).lower()):
167 raise TypeError("Expected " + str(True) + " or " + str(False)
168 + ", but found : " + inputString)
169 return res
170
171def input(*args):
172 n = len(args)
173 if n > 2:
174 raise TypeError("Expected 0 to 2 parameters, but found : "
175 + str(len(args)))
176 elif n == 0 or (n == 1 and isinstance(args[0], str)):
177 res = _input(*args)
178 elif args[-1] == bool:
179 res = _input_bool(*args[0:-1])
180 else:
181 res = args[-1](_input(*args[0:-1]))
182 return res
183
184
185def printf(form, *args, **kwargs):
186 s = form.format(*args)
187 __builtin__.print(s, **kwargs)
188
189
190#
191# caractères : classe char sous-classe de str
192#
193
194class char(str):
195 def __new__(cls, arg):
196 if (type(arg) is int):
197 self = chr(arg)
198 else:
199 self = super(char, cls).__new__(cls, arg)
200 if len(self) != 1:
201 raise TypeError("Expected a character, but string of length 2 "
202 + "found : " + repr(self))
203 return self
204
205#
206# implémentation des chaînes par intégration du TDA dans la classe native str
207# Limites : impossibilité de surcharger l'opérateur | avec forbiddenfruit
208#
209
210def _size(self):
211 return __builtin__.len(self)
212curse(str, "size", _size)
213
214def _isEmpty(self):
215 return __builtin__.len(self) == 0
216curse(str, "isEmpty", _isEmpty)
217
218def _substring(self, p, n):
219 if p < 0 or p > self.size():
220 raise IndexError("Index out of range : " + str(p))
221 if n < 0:
222 raise ValueError("Number of characters is not positive or null : "
223 + str(n))
224 if p + n > self.size():
225 raise IndexError("Index plus number of characters is out of range : "
226 + str(p) + " + " + str(n))
227 return self[p:p+n]
228curse(str, "substring", _substring)
229
230def _add(self, c):
231 if not isinstance(c, str):
232 raise TypeError("add() expected a character, but "
233 + repr(type(c).__name__) + " found")
234 if len(c) != 1:
235 raise ValueError("add() expected a single character, "
236 "but string of length "
237 + str(len(c)) + " found")
238 return self + c
239curse(str, "add", _add)
240
241def _get(self, k):
242 if k < 0 or k >= self.size():
243 raise IndexError("Index out of range : " + str(k))
244 return self[k]
245curse(str, "get", _get)
246
247
248# Tableaux :
249
250class arrayMeta(type):
251 def __getitem__(self, index):
252 res = __builtin__.object.__new__(array)
253 if type(index) is tuple:
254 res.__init__(*index)
255 else:
256 res.__init__(index)
257 return res
258
259 def __call__(self, *args):
260 res = object.__new__(array)
261 dim = len(args)
262 if dim == 0:
263 res = array[0]
264 else:
265 if not type(args[0]) is tuple:
266 t0 = args[0]
267 dims = ()
268 else:
269 t0 = array(*args[0])
270 dims = t0._array__dims
271 res = array[(len(args),) + dims]
272 res._array__data[0] = t0;
273 for i in range(1, dim):
274 if type(args[i]) is tuple:
275 ti = array(*args[i])
276 dimi = ti._array__dims
277 else:
278 ti = args[i]
279 dimi = ()
280 if (dimi != dims):
281 raise TypeError("Inconsistent dimensions : " + str(args[i]))
282 res._array__data[i] = ti
283 return res
284
285
286# extrait de future.utils ; compatibilité Python 2 et 3 pour les métaclasses
287
288def with_metaclass(meta, *bases):
289 """
290 Function from jinja2/_compat.py. License: BSD.
291 Use it like this::
292 class BaseForm(object):
293 pass
294 class FormType(type):
295 pass
296 class Form(with_metaclass(FormType, BaseForm)):
297 pass
298 This requires a bit of explanation: the basic idea is to make a
299 dummy metaclass for one level of class instantiation that replaces
300 itself with the actual metaclass. Because of internal type checks
301 we also need to make sure that we downgrade the custom metaclass
302 for one level to something closer to type (that's why __call__ and
303 __init__ comes back from type etc.).
304 This has the advantage over six.with_metaclass of not introducing
305 dummy classes into the final MRO.
306 """
307 class metaclass(meta):
308 __call__ = type.__call__
309 __init__ = type.__init__
310 def __new__(cls, name, this_bases, d):
311 if this_bases is None:
312 return type.__new__(cls, name, (), d)
313 return meta(name, bases, d)
314
315 return metaclass('temporary_class', None, {})
316
317
318#class array(metaclass=arrayMeta):
319class array(with_metaclass(arrayMeta)):
320
321 """ le type tableau :
322 - implémenté avec des listes
323 - peut être multidimensionnel et dans ce cas est représenté par un tableau
324 de tableau ;
325 - peut être initialisé
326 """
327
328 def __init__(self, *dims):
329 rank = len(dims)
330 self.__dims = dims
331 dim = self.__dims[0]
332 if rank > 1: # tableau multidimensionnel
333 self.__data = [ array[dims[1:]]
334 for i in range(dim) ]
335 else:
336 self.__data = [ None for i in range(dim) ]
337
338 def _verifindex(self, index):
339 if not type(index) is int:
340 raise TypeError("Bad index type : expecting 'int'"
341 + " but was "
342 + repr(type(index).__name__))
343 if index < 0 or index >= self.__dims[0]:
344 raise IndexError("Index out of range : " + str(index))
345
346 def _getitemloc(self, index):
347 if type(index) is tuple and len(index) != self.rank():
348 raise IndexError("Bad dimension count : expecting "
349 + str(self.rank()) + " but was "
350 + str(len(index)))
351 if type(index) is int and self.rank() != 1:
352 raise IndexError("Bad dimension count : expecting "
353 + str(self.rank()) + " but was 1")
354
355 t = self
356 if type(index) is tuple:
357 for i in index[:-1]:
358 t._verifindex(i)
359 t = t.__data[i]
360 index = index[-1]
361 t._verifindex(index)
362 return t.__data, index
363
364 def __getitem__(self, index):
365 data, index = self._getitemloc(index)
366 return data[index]
367
368 def __setitem__(self, index, val):
369 data, index = self._getitemloc(index)
370 data[index] = val
371
372 def rank(self):
373 return len(self.__dims)
374
375 def size(self, *index):
376 t = len(index)
377 if t > 1:
378 raise TypeError("size() takes 0 or 1 positional arguments but "
379 + str(len(index)) + " was given")
380 if t == 0:
381 produit = self.__dims[0]
382 for i in range(1, self.rank()):
383 produit = produit * self.__dims[i]
384 res = produit
385 else:
386 index = index[0]
387 if index >= self.rank():
388 raise IndexError("Index of dimensions out of range : "
389 + str(index))
390 res = self.__dims[index]
391 return res
392
393 def _str(self):
394 if self.rank() > 1:
395 res = '(' + ", ".join(p._str() for p in self.__data)+ ')'
396 else:
397 res = '(' + ", ".join(repr(p) for p in self.__data)+ ')'
398 return res
399
400 def __repr__(self):
401 return (self.__class__.__name__ + self._str())
402
403 __str__ = __repr__
404
405 def __iter__(self):
406 def _array_iter():
407 for t in self.__data:
408 for elt in t:
409 yield elt
410 if self.rank() == 1:
411 res = iter(self.__data)
412 else:
413 res = _array_iter()
414 return res
415
416
417#
418# comportement commun pile, file, liste
419#
420
421class _container(object):
422
423 def __init__(self, data, *vals):
424 self.__data = data
425 for val in vals:
426 self.add(val)
427
428 def isEmpty(self):
429 return self.size() == 0
430
431 def add(self, element):
432 self.__data.append(element)
433
434 def size(self):
435 return len(self.__data)
436
437 def __str__(self):
438 return (self.__class__.__name__
439 + '(' + ", ".join(repr(p) for p in self.__data)+ ')')
440
441 __repr__ = __str__
442
443
444
445#
446# stack : implémentation de pile par délégation à la classe native deque
447#
448
449from collections import deque
450
451class stack(_container):
452 """ le type stack """
453 def __init__(self, *vals):
454 super(stack, self).__init__(deque(), *vals)
455 self.__data = self._container__data
456
457 def get(self):
458 if self.isEmpty():
459 raise IndexError("get() on empty stack")
460 return self.__data[-1]
461
462 def remove(self):
463 if self.isEmpty():
464 raise IndexError("remove() on empty stack")
465 self.__data.pop()
466
467#
468# queue : implémentation de file par délégation à la classe native deque
469#
470
471class queue(_container):
472 """ le type queue """
473 def __init__(self, *vals):
474 super(queue, self).__init__(deque(), *vals)
475 self.__data = self._container__data
476
477 def get(self):
478 if self.isEmpty():
479 raise IndexError("get() on empty queue")
480 return self.__data[0]
481
482 def remove(self):
483 if self.isEmpty():
484 raise IndexError("remove() on empty queue")
485 self.__data.popleft()
486
487#
488# implémentation des listes par délégation à la classe native list
489#
490
491class list(_container):
492 """ le type liste """
493 def __init__(self, *vals):
494 super(list, self).__init__(__builtin__.list(), *vals)
495 self.__data = self._container__data
496
497 def _verifindex(self, pos, inc = 0):
498 if not type(pos) is int:
499 raise TypeError("Bad index type : expecting 'int' "
500 + "but was "
501 + repr(type(pos).__name__))
502 if pos < 0 or pos >= self.size() + inc:
503 raise IndexError("Index out of range : " + str(pos))
504
505 def get(self, pos):
506 self._verifindex(pos)
507 return self.__data[pos]
508
509 def set(self, pos, val):
510 self._verifindex(pos)
511 self.__data[pos] = val
512
513 def insert(self, pos, val):
514 self._verifindex(pos, 1)
515 self.__data.insert(pos, val)
516
517 def remove(self, pos):
518 self._verifindex(pos)
519 self.__data.pop(pos)
520
521 def __iter__(self):
522 return self.__data.__iter__()
523
524class dict():
525 """ le type table """
526 def __init__(self, *vals):
527 try:
528 self.__data = __builtin__.dict(*vals)
529 except (TypeError, ValueError):
530 self.__data = __builtin__.dict(vals)
531
532 def isEmpty(self):
533 return self.size() == 0
534
535 def size(self):
536 return len(self.__data)
537
538 def get(self, key):
539 return self.__data[key]
540
541 def set(self, key, val):
542 if (not self.contains(key)):
543 raise KeyError(key)
544 self.__data[key] = val
545
546 def contains(self, key):
547 return key in self.__data
548
549 def add(self, key, val):
550 if (key in self.__data):
551 raise KeyError("Key already exists : " + repr(key))
552 self.__data[key] = val
553
554 def remove(self, key):
555 self.__data.pop(key)
556
557 def items(self):
558 return list(*self.__data.items())
559
560 def __str__(self):
561 return (self.__class__.__name__
562 + '('
563 + ", ".join(repr((k, v)) for k,v in self.__data.items())
564 + ')')
565
566 __repr__ = __str__
567
568
569#
570# Exécution
571#
572
573def execute(prog, nb=1):
574 if prog.__module__ == "__main__":
575 module = sys.modules["__main__"]
576 filename = module.__file__
577 print("AlgoPy: Analyse du code source de", filename)
578 if sys.version_info[0] > 2:
579 with open(filename, encoding='utf-8') as f:
580 code = f.read()
581 else:
582 with open(filename, "rb") as f:
583 code = f.read()
584
585 print()
586 RestrictionVisitor(code).visit()
587 print()
588
589 import doctest
590 failure_count, test_count = doctest.testmod(verbose=False)
591 print("AlgoPy: Exécution des tests de documentation:",
592 failure_count, "erreur(s) pour",
593 test_count, "test(s)."
594 )
595 print()
596
597 print("Algopy: Exécution de", prog.__name__, "dans", filename)
598 print()
599
600 import timeit
601 time = timeit.timeit(
602 prog.__name__+"()",
603 setup="from __main__ import " + prog.__name__,
604 number=nb
605 )
606 print("\nAlgoPy: Temps d'exécution:",
607 "{:f}".format(time)
608 ,
609 "seconde(s)"
610 )
611 print()
612
613# analyse du code source
614
615import ast
616
617def _message(lineno, *s):
618 print("Ligne", lineno, ":", *s)
619
620class RestrictionVisitor(ast.NodeVisitor):
621 _function_def = False
622 _function_ret = None
623 _lineno = 0
624
625 def __init__(self, code):
626 self._tree = ast.parse(code)
627 self._lines = [None] + code.splitlines() # None at [0] so we can index lines from 1
628
629 def visit(self, node = None):
630 super(RestrictionVisitor, self).visit(node if node else self._tree)
631
632 def visit_Str(self, node):
633 line = self._lines[node.lineno]
634 apostrophe = line[node.col_offset]
635 if len(node.s) != 1 and apostrophe == "'":
636 _message(node.lineno,
637 "l'apostrophe simple doit être réservée",
638 "à l'écriture des caractères")
639
640 def visit_In(self, node):
641 _message(self._lineno,
642 "l'opérateur conditionnel 'in' ne doit pas être utilisé")
643 self.generic_visit(node)
644
645 def visit_NotIn(self, node):
646 _message(self._lineno,
647 "l'opérateur conditionnel 'not in' ne doit pas être utilisé")
648 self.generic_visit(node)
649
650 def visit_Compare(self, node):
651 if len(node.ops) > 1:
652 _message(node.lineno,
653 "les comparaisons ne doivent utiliser qu'un seul opérateur")
654 self._lineno = node.lineno
655 self.generic_visit(node)
656
657 def visit_IfExp(self, node):
658 _message(node.lineno,
659 "l'expression conditionnelle ne doit pas être utilisée")
660 self.generic_visit(node)
661
662 def visit_Subscript(self, node):
663 if not isinstance(node.slice, ast.Index):
664 _message(node.lineno,
665 "les indices par tranches ne doivent pas être utilisées")
666 self.generic_visit(node)
667
668 def visit_Break(self, node):
669 _message(node.lineno,
670 "l'instruction 'break' ne doit pas être utilisée")
671
672 def visit_Continue(self, node):
673 _message(node.lineno,
674 "l'instruction 'continue' ne doit pas être utilisée")
675
676 def visit_For(self, node):
677 if node.orelse:
678 _message(node.lineno,
679 "l'instruction 'for/else' ne doit pas être utilisée")
680 self.generic_visit(node)
681
682 def visit_While(self, node):
683 if node.orelse:
684 _message(node.lineno,
685 "l'instruction 'while/else' ne doit pas être utilisée")
686 self.generic_visit(node)
687
688 def visit_If(self, node):
689 if not node.orelse:
690 _message(node.lineno,
691 "l'instruction 'else' est absente")
692 self.generic_visit(node)
693
694 def visit_FunctionDef(self, node):
695 function_def = self._function_def
696 function_ret = self._function_ret
697 if function_def:
698 _message(node.lineno,
699 "les fonctions imbriquées ne doivent pas être utilisées")
700 else:
701 self._function_def = True
702 if isinstance(node.body[-1], ast.Return):
703 self._function_ret = node.body[-1]
704 if (node.args.vararg
705 or (sys.version_info[0] > 2 and node.args.kwonlyargs)
706 or node.args.kwarg):
707 _message(node.lineno,
708 "les sous-programmes doivent être définies",
709 "avec des paramètres positionnels uniquement")
710 if (node.args.defaults
711 or (sys.version_info[0] > 2 and node.args.kw_defaults)):
712 _message(node.lineno,
713 "les sous-programmes ne doivent pas comporter",
714 "des paramètres initialisés par défaut")
715 if not ast.get_docstring(node, False):
716 _message(node.lineno,
717 "le sous-programme", repr(node.name),
718 "n'a pas de commentaire de documentation")
719
720
721 self.generic_visit(node)
722 self._function_def = function_def
723 self._function_ret = function_ret
724
725 def visit_Return(self, node):
726 if self._function_ret != node:
727 _message(node.lineno,
728 "l'instruction 'return' doit être la dernière instruction",
729 "d'un sous-programme")
730
731 def visit_Global(self, node):
732 _message(node.lineno,
733 "les variables déclarées 'global' ne doivent pas être utilisées")
734
735 def visit_Nonlocal(self, node):
736 _message(node.lineno,
737 "les variables déclarées 'nonlocal' ne doivent pas être utilisées")
738
739if __name__ == "__main__":
740 import doctest
741 doctest.testfile("AlgoPyV5Test.txt", verbose=True)