BOMBOLOM.COM

(python) Scanner de S-expressions em python

Este é um post de Helder Guerreiro.

No último ano e meio tenho andado a fazer (lenta e vagarosamente) um cliente de mail em Python, cujo objectivo é ter mais ou menos o mesmo conjunto de características do Squirrelmail. Podem verificar o resultado do meu ligeiro esforço nesta matéria no site do WebPyMail (atenção este software está ainda longe de ser utilizável e só foi testado com o Cyrus IMAP). Este cliente utiliza um servidor de IMAP como backend. Como o IMAP compõe a suas respostas aos comandos enviados ao servidor como Expressões Simbólicas necessitava de ter um processo para fazer o parse destas respostas de uma forma rápida e eficiente dado que por vezes podemos ter respostas muito extensas e complexas.

Neste artigo mostro a minha solução para este problema.

Por exemplo o resultado de um comando FETCH a um servidor IMAP pode ser:

266 FETCH (FLAGS (\Seen) UID 31608 INTERNALDATE "30-Jan-2008 02:48:01 +0000" RFC822.SIZE 4509 ENVELOPE ("Tue, 29 Jan 2008 14:00:24 +0000" "Aprenda as tXcnicas e os truques da cozinha mais doce..." (("Ediclube" NIL "ediclube" "sigmathis.info")) (("Ediclube" NIL "ediclube" "sigmathis.info")) ((NIL NIL "ediclube" "sigmathis.info")) ((NIL NIL "helder" "example.com")) NIL NIL NIL "<64360f85d83238281a27b921fd3e7eb3@localhost.localdomain>"))

Esta string depois de ser lida deve ser convertida em qualquer coisa como:

[266, 'FETCH', ['FLAGS', ['\\Seen'], 'UID', 31608, 'INTERNALDATE', '30-Jan-2008 02:48:01 +0000', 'RFC822.SIZE', 4509, 'ENVELOPE', ['Tue, 29 Jan 2008 14:00:24 +0000', 'Aprenda as tXcnicas e os truques da cozinha mais doce...', [['Ediclube', None, 'ediclube', 'sigmathis.info']], [['Ediclube', None, 'ediclube', 'sigmathis.info']], [[None, None, 'ediclube', 'sigmathis.info']], [[None, None, 'helder', 'example.com']], None, None, None, '<64360f85d83238281a27b921fd3e7eb3@localhost.localdomain>']]]

Neste caso fez-se o fetch de FLAGS, UID, RFC822.SIZE e o ENVELOPE. Este é um comando IMAP normal para se apresentar o cabeçalho de uma mensagem numa lista de mensagens.Isto quer dizer que este comando pode ser repetido milhares de vezes para mostrar uma lista de mensagens extensa, logo tenho de reforçar a ideia de que este procedimento tem de ser suficientemente rápido, caso contrário o programa não é utilizável.

A solução que encontrei pode ser obtida aqui.

A função relevante é:

# -*- coding: utf-8 -*-
#
# Helder Guerreiro <helder em paxjulia.com>
#
# $Id: sexp.py 364 2008-06-16 11:46:37Z helder $
#

# Global imports
import re, string

# Regexp
literal_re = re.compile(r'^{(\d+)}\r\n')
simple_re = re.compile(r'^([^ ()]+)')
quoted_re = re.compile(r'^"((?:[^"\\]|\\")*?)"')

# Errors
class SError(Exception): pass

def scan_sexp(text):
    '''S-Expression scanner.

    This is a non-recursive version. It uses the lists property of assigning
    only by reference to assemble the s-exp.

    @param text: text to be scanned.
    @type  text: s-exp string

    @return result: s-exp in a python list.
    '''

    # Initialization
    pos = 0
    lenght = len(text)
    current = ''
    result = []
    cur_result = result
    level = [ cur_result ]

    # Scanner
    while pos < lenght:

        # Quoted literal:
        if text[pos] == '"':
            quoted = quoted_re.match(text[pos:])
            if quoted:
                cur_result.append( quoted.groups()[0] )
                pos += quoted.end() - 1

        # Numbered literal:
        elif text[pos] == '{':
            lit = literal_re.match(text[pos:])
            if lit:
                 start = pos+lit.end()
                 end = pos+lit.end()+int(lit.groups()[0])
                 pos = end - 1
                 cur_result.append( text[ start:end ] )

        # Simple literal
        elif text[pos] not in '() ':
            simple = simple_re.match(text[pos:])
            if simple:
                tmp = simple.groups()[0]
                if tmp.isdigit():
                    tmp = int(tmp)
                elif tmp == 'NIL':
                    tmp = None
                cur_result.append( tmp )
                pos += simple.end() - 1

        # Level handling, if we find a '(' we must add another list, if we
        # find a ')' we must return to the previous list.
        elif text[pos] == '(':
            cur_result.append([])
            cur_result = cur_result[-1]
            level.append(cur_result)

        elif text[pos] == ')':
            try:
                cur_result = level[-2]
                del level[-1]
            except IndexError:
                raise SError('Unexpected parenthesis at pos %d' % pos)

        pos += 1

    return result

Este scanner considera três tipos de átomos (para além das possíveis sub-expressões que possam existir):

Além disto convertem-se os inteiros directamente para inteiros e a palavra chave 'NIL' para 'None'.

Funcionamento

Para transformar a string numa lista de Python, percorre-se a string caracter a caracter. De modo a termos uma função relativamente rápida utiliza-se expressões regulares para identificar os átomos que se se estão a ler. Estas expressões regulares identificam imediatamente a posição do fim do átomo, pelo que em vez de percorrermos caracter a caracter estes átomos podemos extrair o átomo da string inicial usando a notação de 'slice' do python e saltar imediatamente para a posição final. Assim mesmo que tenhamos uma resposta longa (como por exemplo o corpo de uma mensagem de correio electrónico, o parsing da string é sempre muito rápido.

As listas dentro de listas são extraídas aproveitando o facto do python usar sempre referências para apontar para as listas (muito à semelhança de pointers em outras linguagens de mais baixo nível). Assim, quando encontramos um parênteses de abertura '(', passamos a acrescentar os átomos que formos encontrando a uma lista vazia. Além disso guardamos numa lista (level) a referência à lista de nível inferior. Quando encontramos o parênteses de fecho, acrescentamos à lista anterior (cuja referência estava armazenada na lista 'level') a lista que estávamos compor, a lista corrente passa a ser a lista que retirámos de 'level' e apaga-se o último elemento de level.

Usando o Python 2.5 num Pentium D a 3.40GHz, esta função leva 0.3ms, em média, a fazer o parse à linha que usei como exemplo. Este nível de performance é perfeitamente aceitável para o fim que tenho em vista.

28.01.2009 | Ler mais | Comentários | Tags

Voltar à Página principal | Made with PyBlosxom