Пориньте у Python 3/Детальніше про ітератори
"Великі блохи мають на спинах маленьких блох, щоб їх кусали.
А малі мають ще менших, і так до нескінченності."
Августус Де Морган
Занурення
[ред.]Так як регулярні вирази - це операції з рядками на стероїдах, так само модуль itertools - ітератори на стероїдах. Але спершу я хочу показати вам одну класичну головоломку:
HAWAII + IDAHO + IOWA + OHIO == STATES 510199 + 98153 + 9301 + 3593 == 621246 H = 5 A = 1 W = 0 I = 9 D = 8 O = 3 S = 6 T = 2 E = 4
Такі головоломки називаються математичними ребусами. Букви утворюють якісь слова, але якщо замінити кожну букву цифрою від 0 до 9, числа утворять правильну математичну тотожність. Задача в тому, аби вияснити яка цифра відповідає кожній букві. Всі випадки використання букви замінюються на одну й ту ж цифру, жодна цифра не замінює двох різних букв, і жодне "слово" не може починатись з цифри 0.
В цьому розділі ми розберемо неймовірну програму мовою Python, початково написану Реймондом Геттінґером. Ця програма розв’язує математичні ребуси використовуючи всього 14 рядків коду.
import re
import itertools
def solve(puzzle):
words = re.findall('[A-Z]+', puzzle.upper())
unique_characters = set(''.join(words))
assert len(unique_characters) <= 10, 'Too many letters'
first_letters = {word[0] for word in words}
n = len(first_letters)
sorted_characters = ''.join(first_letters) + \
''.join(unique_characters - first_letters)
characters = tuple(ord(c) for c in sorted_characters)
digits = tuple(ord(c) for c in '0123456789')
zero = digits[0]
for guess in itertools.permutations(digits, len(characters)):
if zero not in guess[:n]:
equation = puzzle.translate(dict(zip(characters, guess)))
if eval(equation):
return equation
if __name__ == '__main__':
import sys
for puzzle in sys.argv[1:]:
print(puzzle)
solution = solve(puzzle)
if solution:
print(solution)
Ви можете запустити програму з командного рядка. Як це виглядатиме в Лінукс продемонстровано нижче. (Пошук розв’язку може зайняти деякий час, тому наберіться терпіння).
you@localhost:~/diveintopython3/examples$ python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO == STATES" HAWAII + IDAHO + IOWA + OHIO = STATES 510199 + 98153 + 9301 + 3593 == 621246 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "I + LOVE + YOU == DORA" I + LOVE + YOU == DORA 1 + 2784 + 975 == 3760 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "SEND + MORE == MONEY" SEND + MORE == MONEY 9567 + 1085 == 10652
Пошук всіх входжень шаблону
[ред.]Перше що робить наш розв’язувач головоломок - знаходить всі великі латинські літери в умові:
>>> import re
>>> re.findall('[0-9]+', '16 2-by-4s in rows of 8')
['16', '2', '4', '8']
Модуль re містить реалізацію регулярних виразів мови Python. Він має вправну функцію findall(), яка отримує регулярний вираз, і рядок, та повертає список зі всіма входженнями шаблону в рядок. В нашому випадку шаблону відповідають послідовності цифр.
>>> re.findall('[A-Z]+', 'SEND + MORE == MONEY')
['SEND', 'MORE', 'MONEY']
Це шаблон якому відповідають послідовності літер. Знову ж таки значенням що повертається - список, кожен елемент якого співставний з регулярним виразом.
А ось ще один приклад, щоб дещо розім’яти ваш мозок:
>>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.")
[' sixth s', " sheikh's s", " sheep's s"]
Здивовані? Регулярний вираз шукає пробіл, s, найкорошту можливу послідовність довільних символів, знову пробіл, а потім іншу s. Але дивлячись на той рядок я бачу аж п’ять відповідностей:
The sixth sick sheikh's sixth sheep's sick.The sixth sick sheikh's sixth sheep's sick.The sixth sick sheikh's sixth sheep's sick.The sixth sick sheikh's sixth sheep's sick.The sixth sick sheikh's sixth sheep's sick.
А re.findall() повертає список з трьома співпадіннями. Якщо конкретно, то з першим, третім і п’ятим. Чому б це? Тому що вона не повертає співпадіння які перекриваються. Перше співпадіння перекривається з другим, тому друге пропускається. Наступне третє повертається, але воно перетинається з четвертим, тому четверте пропускається, і насамкінець повертається п’яте. Таким чином отримуємо п’ять співпадінь.
Але це не має жодного відношення до розв’язування ребусів. Я просто подумав що це може бути цікаво.
Пошук унікальних елементів послідовності
[ред.]Множини роблять пошук унікальних елементів тривіальною справою.
>>> a_list = ['The', 'sixth', 'sick', "sheik's", 'sixth', "sheep's", 'sick']
>>> set(a_list)
{'sixth', 'The', "sheep's", 'sick', "sheik's"}
Отримавши на вхід список елементів, функція set() поверне набір унікальних рядків в списку. Це можна собі уявити як цикл for: беремо перший елемент, додаємо в множину. Потім другий, третій, четвертий, п’ятий... Стоп! П’ятий вже є в множині, тому його пропускаємо. Додаємо ще шостий, і пропускаємо останній. В результаті отримуємо набір унікальних елементів списку. Для цього список навіть не довелось сортувати.
>>> a_string = 'EAST IS EAST'
>>> set(a_string)
{'A', ' ', 'E', 'I', 'S', 'T'}
Така ж техніка працює з рядками, тому що рядки - просто послідовності символів.
>>> words = ['SEND', 'MORE', 'MONEY']
>>> ''.join(words)
'SENDMOREMONEY'
.join(a_list) склеює список рядків a_list в один рядок.
>>> set(''.join(words))
{'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}
Цей код повертає множину унікальних символів в усіх рядках списку.
Розв’язувач ребусів використовує такий підхід при побудові множини всіх символів головоломки:
unique_characters = set(''.join(words))
Цей набір пізніше використовується щоб присвоювати символам числові значення, в процесі перебору розв’язків.
Пересвідчення (assert)
[ред.]Як і багато інших мов, Python містить інструкцію assert. Вона працює так:
>>> assert 1 + 1 == 2
Після інструкції assert іде довільний вираз мови Python. В цьому випадку твердження 1 + 1 == 2 істинне, тому інструкція assert нічого не робить.
>>> assert 1 + 1 == 3
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AssertionError
Тим не менш, якщо вираз приймає хибне значення в булевому контексті, assert згенерує виняток AssertionError
>>> assert 2 + 2 == 5, "Only for very large values of 2"
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AssertionError: Only for very large values of 2
Також ви можете додати після виразу пояснення того що сталось для інших людей.
Коротше кажучи, рядок коду:
assert len(unique_characters) <= 10, 'Too many letters'
... є еквівалентним оцьому:
if len(unique_characters) > 10:
raise AssertionError('Too many letters')
Розв’язувач ребусів використовує таке пересвідчення, щоб не почати розв’язувати головоломку, яка містить більше десяти різних символів. Бо так як цифр всього десять головоломка що має більше символів не може мати розв’язку.
Генераторні вирази
[ред.]Генераторні вирази - це як генераторні функції тільки без функцій.
>>> unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'}
>>> gen = (ord(c) for c in unique_characters)
Генераторний вираз схожий на анонімну функцію що генерує значення. Він схожий на списковий вираз, але замість квадратних дужок використовує круглі.
>>> gen
<generator object <genexpr> at 0x00BADC10>
Генераторний вираз повертає ітератор.
>>> next(gen) 69
>>> next(gen)
68
Виклик функції next повертає наступне значення переданого їй ітератора.
>>> tuple(ord(c) for c in unique_characters)
(69, 68, 77, 79, 78, 83, 82, 89)
За бажанням ви можете здійснити ітерацію крізь всі значення, та повернути список, кортеж, чи множину, передаючи генераторний вираз як аргумент у функції list(), tuple() чи set(). В цьому випадку вам навіть не потрібна зайва пара дужок - просто передайте "голий" вираз ord(c) for c in unique_characters в функцію tuple(), і Python сам здогадається що це генераторний вираз.
☞ Використання генераторних виразів замість спискових економить як пам’ять так і процесорний час. Якщо ви будуєте список тільки для того аби його невдовзі викинути (тобто передати функціям
tuple()чиset()) - краще натомість використовуйте генератори.
Ось інший спосіб досягнути того ж, використовуючи генераторну функцію:
def ord_map(a_string):
for c in a_string:
yield ord(c)
gen = ord_map(unique_characters)
Генераторний вираз набагато компактніший, хоча є функціонально еквівалентним.
Перебір перестановок... Спосіб для лінивих!
[ред.]Перш за все - що перестановки взагалі таке? Перестановки - це таке математичне поняття. (Взагалі то, існує кілька означень, залежно від того який розділ математики вам потрібен. Тут я розглядаю комбінаторику, але якщо це для вас взагалі нічого не означає - не хвилюйтесь. Як завжди - вікіпедія це ваша помічниця).
Ідея полягає в тому, що ви берете послідовність якихось об’єктів (чисел, рядків чи навіть танцюючих ведмедів) і перебираєте всі можливі способи утворити з неї менші послідовності. Ці менші послідовності повинні бути однакової, проте довільної довжини - від одного до кількості елементів в початковій послідовності. (Примітка: англійське слово permutations в українській комбінаторній термінології означає два поняття: розміщення та перестановки. Перестановки - це розміщення довжини n, де n - довжина початкової послідовності, тому надалі напевне краще буде перекладати термін permutations як розміщення. Не знаю.) Також - два однакові розміщення не повинні повторюватись. Математики кажуть: "давайте знайдемо всі розміщення з трьох елементів по два", що означає: давайте знайдемо всі різні послідовності довжини 2, з трьох можливих елементів.
>>> import itertools
Модуль itertools містить багато цікавих речей, і в тому числі функцію permutations(), яка робить за нас всю важку роботу з генерації розміщень.
>>> perms = itertools.permutations([1, 2, 3], 2)
Функція permutations() приймає на вхід послідовність (в даному випадку список з трьох чисел), і число - розмір розміщень які ми будемо генерувати. Функція повертає ітератор, який можна використовувати в циклах for, чи інших місцях де потрібні послідовності. Тут я перевірю всі значення ітератора вручну.
>>> next(perms)
(1, 2)
>>> next(perms)
(1, 3)
>>> next(perms)
(2, 1)
>>> next(perms)
(2, 3)
>>> next(perms)
(3, 1)
>>> next(perms)
(3, 2)
Зауважте що розміщення впорядковані. (2, 1) - це інша не те саме розміщення що й (1, 2).
>>> next(perms)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
І це всі розміщення з елементів [1, 2, 3] взятих поодинці. Такі пари як (1, 1) не з’являються, бо вони містять повторення, тому не є правильними розміщеннями. Коли ітерації закінчуються ітератор генерує виняток StopIteration
itertools містить ще купу цікавих речей.Функція permutations() приймає не тільки списки. Вона може приймати довільні послідовності - навіть рядки.
>>> import itertools
>>> perms = itertools.permutations('ABC', 3)
Рядок - це всього лиш послідовність символів. При генеруванні перестановок рядок 'ABC' еквівалентний списку ['A', 'B', 'C']
>>> next(perms)
('A', 'B', 'C')
>>> next(perms)
('A', 'C', 'B')
>>> next(perms)
('B', 'A', 'C')
>>> next(perms)
('B', 'C', 'A')
>>> next(perms)
('C', 'A', 'B')
>>> next(perms)
('C', 'B', 'A')
>>> next(perms)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
Перше розміщення (тут прийнятний і термін перестановка) з елементів ['A', 'B', 'C'], взятих по три штуки - ('A', 'B', 'C'). Решта п’ять - ці ж три елементи які розміщуються у всіх мислимих порядках.
>>> list(itertools.permutations('ABC', 3))
[('A', 'B', 'C'), ('A', 'C', 'B'),
('B', 'A', 'C'), ('B', 'C', 'A'),
('C', 'A', 'B'), ('C', 'B', 'A')]
Так як функція permutations() завжди повертає ітератор, то найпростіший спосіб її зневадження - передати цей ітератор функції list(), щоб отримати всі перестановки одразу.
Інші веселі речі з модуля itertools
[ред.]>>> import itertools
>>> list(itertools.product('ABC', '123'))
[('A', '1'), ('A', '2'), ('A', '3'),
('B', '1'), ('B', '2'), ('B', '3'),
('C', '1'), ('C', '2'), ('C', '3')]
itertools.product() повертає ітератор що генерує декартовий добуток двох послідовностей.
>>> list(itertools.combinations('ABC', 2))
[('A', 'B'), ('A', 'C'), ('B', 'C')]
Функція itertools.combinations() повертає ітератор що містить всі можливі комбінації певної кількості елементів даної послідовності. Це майже так само як itertools.permutations(), тільки до списку комбінацій не входять комбінації які містять такі ж елементи але в іншому порядку. Тобто itertools.permutations('ABC', 2) поверне як і ('A', 'B') так і ('B', 'A') (окрім інших), а itertools.combinations('ABC', 2) не поверне ('B', 'A') тому що це дублікат ('A', 'B') в іншому порядку.
>>> names = list(open('examples/favorite-people.txt', encoding='utf-8'))
>>> names ['Dora\n', 'Ethan\n', 'Wesley\n', 'John\n', 'Anne\n',
'Mike\n', 'Chris\n', 'Sarah\n', 'Alex\n', 'Lizzie\n']
У такий спосіб можна отримати список рядків файла.
>>> names = [name.rstrip() for name in names]
>>> names
['Dora', 'Ethan', 'Wesley', 'John', 'Anne',
'Mike', 'Chris', 'Sarah', 'Alex', 'Lizzie']
На жаль, попередній спосіб також читає з файлу символи переходу на новий рядок, тому ми застосовуємо списковий вираз та рядковий метод rstrip(), щоб видалити зайві розмежовувальні символи з кінця рядка. (Рядки також мають метод lstrip() для видалення їх на початку та метод strip() для очистки невидимих символів з обох кінців).
>>> names = sorted(names)
>>> names
['Alex', 'Anne', 'Chris', 'Dora', 'Ethan',
'John', 'Lizzie', 'Mike', 'Sarah', 'Wesley']
Функція sorted() приймає список, і повертає його відсортованим. За замовчуванням, вона сортує за алфавітом. В даному випадку ми передали функцію len(), тому рядки сортуються за довжиною.
>>> names = sorted(names, key=len)
>>> names ['Alex', 'Anne', 'Dora', 'John', 'Mike',
'Chris', 'Ethan', 'Sarah', 'Lizzie', 'Wesley']
Але також їй в параметр key функцію, і тоді список відсортується за зростанням значень цієї функції.
Але яким чином це пов’язано з модулем itertools? Радий що ви спитали.
…продовжуючи попередній сеанс інтерактивної оболонки…
>>> import itertools
>>> groups = itertools.groupby(names, len)
>>> groups
<itertools.groupby object at 0x00BB20C0>
>>> list(groups)
[(4, <itertools._grouper object at 0x00BA8BF0>),
(5, <itertools._grouper object at 0x00BB4050>),
(6, <itertools._grouper object at 0x00BB4030>)]
Функція itertools.groupby() приймає два значення - ітератор, і функцію, і повертає ітератор з парами. Першим елементом пари є значення функції, а другим - ітератор що містить всі елементи вхідної послідовності з таким самим значенням функції.
>>> groups = itertools.groupby(names, len)
Виклик функції list() "спорожнив" ітератор, тобто ви вже згенерували кожен елемент в ітераторі для того щоб утворити список, і більше їх там немає. Ніякої кнопки "перезавантажити" на ітераторі немає, і почати все заново неможливо, тому доводиться створювати ітератор спочатку.
>>> for name_length, name_iter in groups:
... print('Names with {0:d} letters:'.format(name_length))
... for name in name_iter:
... print(name)
...
Names with 4 letters:
Alex
Anne
Dora
John
Mike
Names with 5 letters:
Chris
Ethan
Sarah
Names with 6 letters:
Lizzie
Wesley
В цьому прикладі, коли функція itertools.groupby() отримує вже відсортований список значень names, і поміщає всі чотирибуквенні імена в один ітератор, всі п’ятибуквенні в інший, і так далі. Функція groupby цілком загальна. Вона може групувати рядки за першою буквою, числа за кількістю дільників, чи за будь-якою іншою функцією яку ви придумаєте.
☞ Функція
itertools.groupby()працює лише коли вхідна послідовність вже відсортована за фунцією за якою групується. В прикладі вище ми групували її за функцієюlen(). Це працювало лише тому, що вхідний список вже був відсортованим за цією функцією.
Ви дивитесь уважно?
>>> list(range(0, 3))
[0, 1, 2]
>>> list(range(10, 13))
[10, 11, 12]
>>> list(itertools.chain(range(0, 3), range(10, 13)))
[0, 1, 2, 10, 11, 12]
Функція chain() бере два ітератори, і повертає ітератор, який генерує спочатку всі елементи з першого ітератора, а потім з другого. (Взагалі вона може брати довільне число ітераторів і з’єднувати їх послідовно в тому порядку в якому їх передали).
>>> list(zip(range(0, 3), range(10, 13)))
[(0, 10), (1, 11), (2, 12)]
Функція zip() робить дещо прозаїчне, яке щоправда іноді виявляється надзвичайно корисним: вона бере довільне число послідовностей, і повертає ітератор який генерує кортежі що містять перші елементи всіх послідовностей, потім другі елементи, потім треті, і так далі.
>>> list(zip(range(0, 3), range(10, 14)))
[(0, 10), (1, 11), (2, 12)]
Функція zip() зупиняється на кінці найкоротшої послідовності. range(10, 14) має чотири елементи: (10, 11, 12, 13), а range(0, 3) всього лиш 3, тому функція zip() поверне ітератор з трьох елементів.
>>> list(itertools.zip_longest(range(0, 3), range(10, 14)))
[(0, 10), (1, 11), (2, 12), (None, 13)]
Правда є функція itertools.zip_longest(), яка повертає ітератор що містить стільки елементів, скільки їх є в найдовшій послідовності, заповнюючи нестачу в інших послідовностях значеннями None.
Гаразд, це все було дуже цікаво. Але як воно пов’язане з розв’язувачем ребусів? А ось як:
>>> characters = ('S', 'M', 'E', 'D', 'O', 'N', 'R', 'Y')
>>> guess = ('1', '2', '0', '3', '4', '5', '6', '7')
>>> tuple(zip(characters, guess))
(('S', '1'), ('M', '2'), ('E', '0'), ('D', '3'),
('O', '4'), ('N', '5'), ('R', '6'), ('Y', '7'))
Отримавши список букв та цифр, функція zip() створює впорядкований список пар.
>>> dict(zip(characters, guess))
{'E': '0', 'D': '3', 'M': '2', 'O': '4',
'N': '5', 'S': '1', 'R': '6', 'Y': '7'}
І це добре тому що така структура даних підходяща для функції dict() і створення словника, в якому кожній букві відповідає цифра. (Це не єдиний спосіб створити такий словник. Можна також використати словникові вирази, аби створити словник напряму). І хоча як видно з лістингу вище в словнику пари йдуть зовсім в іншому порядку (словники не мають порядку за означенням), але ми можемо бачити що кожному символу відповідає та буква, яка відповідала йому в порядку який був в оригінальних списках characters і guess.
Розв’язувач ребусів використовує такий метод щоб створити словник відповідностей між буквами в головоломці і цифрами в розв’язку.
characters = tuple(ord(c) for c in sorted_characters)
digits = tuple(ord(c) for c in '0123456789')
...
for guess in itertools.permutations(digits, len(characters)):
...
equation = puzzle.translate(dict(zip(characters, guess)))
Але що це за метод translate()? Ах, тут ми нарешті добрались до справді цікавої частини.
Новий спосіб маніпуляцій над рядками
[ред.]Рядки в мові Python мають багато методів. Ви дізнались про деякі з них в розділі Текст. Зараз я хочу показати вам зручну, проте маловідому техніку роботи з рядками: метод translate().
>>> translation_table = {ord('A'): ord('O')}
Перетворення рядка починається з створення таблиці перетворення, яка є простим словником який відображає один символ на інший. Щоправда вживати тут слово "символ" не цілком вірно. Таблиця насправді задає відношення між байтами.
>>> translation_table
{65: 79}
Пам’ятайте, байти в Python 3 - це цілі числа. Функція ord() повертає номер в символа в таблиці ASCII, який, у випадку символів від A до Z, завжди є байтом між 65 і 90.
>>> 'MARK'.translate(translation_table)
'MORK'
Метод рядка translate() отримує таблицю перетворення і пробігається по рядку з нею. Як тільки він значення для якого є ключ в таблиці, він замінює його значенням з таблиці. В даному випадку замінює рядок 'MARK' на 'MORK'.
І що тут має відношення до розв’язування ребусів? Як виявляється - все.
>>> characters = tuple(ord(c) for c in 'SMEDONRY')
>>> characters
(83, 77, 69, 68, 79, 78, 82, 89)
Використовуючи генераторний вираз ми швидко обчислюємо значення байтів для символів в рядку.
>>> guess = tuple(ord(c) for c in '91570682')
>>> guess
(57, 49, 53, 55, 48, 54, 56, 50)
Іншим генераторним виразом обчислюємо значення байтів для символів цифр які їм відповідають.
>>> translation_table = dict(zip(characters, guess))
>>> translation_table
{68: 55, 69: 53, 77: 49, 78: 54, 79: 48, 82: 56, 83: 57, 89: 50}
Таблиця перетворення будується за допомогою з’єдання цих двох послідовностей в пари, і конструювання з цих пар словника.
>>> 'SEND + MORE == MONEY'.translate(translation_table)
'9567 + 1085 == 10652'
І нарешті, ми передаємо таблицю перетврення в метод translate() оригінального тексту головоломки. Це перетворює кожну букву головоломки на відповідну цифру. Результатом є правильний вираз мови Python, записаний як рядок.
Це досить вражаюче. Але що робити з рядком який є правильним виразом мови Python?
Обчислення рядків як виразів Python
[ред.]Це остання частина головоломки (чи точніше остання частина розв'язувача головоломок). Після всіх тих незвичних маніпуляцій, ми отримуємо рядок на зразок '9567 + 1085 == 10652'. Але це рядок, а що доброго в рядку? Тут з’являється eval() - універсальний інструмент обчислень в Python.
>>> eval('1 + 1 == 2')
True
>>> eval('1 + 1 == 3')
False
>>> eval('9567 + 1085 == 10652')
True
Але зачекайте, є ще! eval() не обмежується булевими виразами. Вона може обробляти будь-який вираз, та повертати будь-який тип даних.
>>> eval('"A" + "B"')
'AB'
>>> eval('"MARK".translate({65: 79})')
'MORK'
>>> eval('"AAAAA".count("A")')
5
>>> eval('["*"] * 5')
['*', '*', '*', '*', '*']
Але зачекайте, це ще не все!
>>> x = 5
>>> eval("x * 5")
25
Вираз який показує, що eval() може використовувати глобальні змінні описані за його межами. А також локальні змінні, якщо виклик відбувається з функції.
>>> eval("pow(x, 2)")
25
Та функції.
>>> import math
>>> eval("math.sqrt(x)") ③
2.2360679774997898
Та модулі.
Ей, зачекайте хвилинку…
>>> import subprocess
>>> eval("subprocess.getoutput('ls ~')")
'Desktop Library Pictures \
Documents Movies Public \
Music Sites'
Модуль subprocess дозволяє запускати консольні команди, та отримувати результат в вигляді рядка.
>>> eval("subprocess.getoutput('rm /some/random/file')")
Деякі консольні команди можуть мати незворотні наслідки.
Ситуація стає ще гіршою від того, що існує глобальна функція __import__(), яка отримує ім'я модуля як рядок, імпортує модуль, та повертає посилання на нього. Якщо це поєднати з силою eval() можна створити один єдиний вираз що знищить всі ваші файли.
>>> eval("__import__('subprocess').getoutput('rm /some/random/file')")
Тепер уявіть вивід 'rm -rf ~'. Хоча насправді не буде ніякого виводу, але також у вас більше не буде ніяких файлів.
Емм, злою частиною є обчислення довільних виразів з ненадійних джерел. Ви маєте використовувати eval() тільки на довірених джерелах. Звичайно, фокус в тому щоб визначити що є "довіреним". Але є щось, що я знаю точно: ви НЕ маєте брати цей зручний калькулятор, та розміщувати його в інтернет як милий маленький веб-сервіс. Не робіть помилку думаючи, "Ох, функція робить багато маніпуляцій з рядками перед тим як почати їх обчислення; Важко уявити, як хтось може проексплоїтити це." Хтось ВИЯСНИТЬ як протягнути небезпечний код крізь всі маніпуляції з рядками (ставались і дивніші речі), а після цього ви можете попрощатись з сервером.
Чи існує хоч якийсь спосіб безпечного обчислення виразів? Щоб поставити eval() в певні обмеження, за які він не зможе вийти, щоб зашкодити зовнішньому світу? Ну, насправді і так, і ні.
>>> x = 5
>>> eval("x * 5", {}, {})
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name 'x' is not defined
Другий та третій параметри, що передаються функції eval(), стають глобальним та локальним просторами імен для виразу. В даному випадку вони обидва порожні. Це означає, що при обчисленні рядка "x * 5" немає посилання на змінну x ні в глобальному ні в локальному просторі імен, тому eval() закінчить роботу і згенерує виняток.
>>> eval("x * 5", {"x": x}, {})
Можна вибірково включати певні змінні в глобальний простір імен, перелічивши кожну індивідуально. Тоді ті, і тільки ті змінні будуть доступними під час обчислення.
>>> import math >>> eval("math.sqrt(x)", {"x": x}, {}) Traceback (most recent call last):
File "<stdin>", line 1, in <module> File "<string>", line 1, in <module>
NameError: name 'math' is not defined </syntaxhighlight>
Незважаючи на те, що ви імпортували модуль math, ви не додали його в простір імен, що передається функції eval(), тому обчислення не вдається.
Ех, це ж просто! Давайте я тепер зроблю веб-сервіс для розв’язування ребусів!
>>> eval("pow(5, 2)", {}, {})
25
Незважаючи на те, що ви передали порожні словники, як глобальний та локальний простори імен, всі вбудовані функції Python досі доступні в процесі обчислень. Тому pow(5,2), працює, тому що 5 та 2 - літерали, а pow() - вбудована функція.
>>> eval("__import__('math').sqrt(5)", {}, {}) ②
2.2360679774997898
На жаль (і якщо ви не зрозуміли чому "на жаль" - прочитайте розділ спочатку), функція __import__() - також є вбудованою, та також працює.
Ага, це означає, що ви все ще можете нашкодити, навіть якщо будете передавати в eval() порожні простори імен.
>>> eval("__import__('subprocess').getoutput('rm /some/random/file')", {}, {})
Ойойой, який я радий що ще не зробив веб-сервіс. Так чи існує якийсь спосіб безпечного використання eval()?
>>> eval("__import__('math').sqrt(5)",
... {"__builtins__":None}, {})
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name '__import__' is not defined
Щоб безпечно обчислити вирази яким не довіряєте, ви маєте описати глобальний простір імен, що присвоює "__builtins__" None, тобто відсутність будь-яких значень. Загалом всі вбудовані функції зберігаються всередині псевдо-модуля названого "__builtins__". Цей псевдо-модуль (набір вбудованих функцій) доступний функції eval() за замовчуванням, якщо ви не заміните його явно.
>>> eval("__import__('subprocess').getoutput('rm -rf /')",
... {"__builtins__":None}, {})
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<string>", line 1, in <module>
NameError: name '__import__' is not defined
Переконайтесь що ви перевантажили __builtins__. Не __builtin__, __built-ins__, чи ще якийсь варіант, що буде працювати прекрасно, але зовсім не зачепить набору вбудованих функцій.
То eval() тепер безпечний? Ну, і так і ні.
>>> eval("2 ** 2147483647",
... {"__builtins__":None}, {})
Навіть без доступу до __builtins__, все ще можна запустити DoS атаку. Наприклад спроба піднести 2 до великого степеня, повністю завантажить процесор вашого комп'ютера на деякий час. (Якщо ви пробуєте це в консолі інтерпретатора, натисніть Ctrl-C кілька разів, щоб перервати це). Технічно цей вираз швидко поверне значення, проте в той час ваш сервер не зможе робити нічого іншого.
В кінці кінців, можливо безпечно виконувати невідомі вирази Python, для певного визначення "безпеки", яке виявляється не надто корисним в реальному житті. Це нормально, якщо ви просто експериментуєте, і нормально, якщо ви передаєте на обчислення текст якому довіряєте. Але все інше - лиш напрошуватись на зайві неприємності.
Зібравши все до купи
[ред.]Нагадаю: ця програма розв’язує математичні ребуси грубою силою, тобто повним перебором всіх можливих розв’язків. Щоб це здійснити, вона:
- Знаходить всі букви головоломки за допомогою функції
re.findall(). - Знаходить множину різних букв за допомогою функції
set(). - Пересвідчується що букв не більше 10 (що означатиме нерозв’язність головоломки) за допомогою інструкції
assert - Генерує ASCII коди букв.
- Перебирає всі можливі розв’язки за допомогою функції
itertools.permutations() - Перетворює всі можливі розв’язки на вирази мови Python використовуючи метод рядкових об’єктів
translate(). - Перевіряє кожен розв’язок обчислюючи його вираз функцією
eval() - Повертає перший розв’язок вираз для якого є істинним.
... всього лише за 14 рядків коду.
Що читати далі?
[ред.]- Документація модуля
itertools - Вікіпедія про математичні ребуси
- Доповідь Реймонда Геттінґера "Easy AI with Python" на конференції PyCon 2009