domingo, 9 de dezembro de 2007

Splitting hairs

split hairs: to argue about whether unimportant details are correct

Sou fã de Perl porque me permite ser sucinto como em nenhuma outra linguagem.

Esta semana descobri um bug num velho script que eu uso pra processar o relatório produzido pelo comando " bpdbjobs -report -all_columns" do NetBackup. O relatório é um arquivo texto no qual cada linha tem um número variável de campos separados por vírgulas.

Até aí, nada demais. Se eu tiver a linha na variável $line, a função "split" separa os campos nas vírgulas e os atribui ao array @fields trivialmente:

@fields = split /,/, $line;

Só que alguns campos deste relatório podem conter vírgulas, as quais são "escapadas" com barras invertidas, i.e., "\,". O split anterior não entende essas vírgulas escapadas e vai tratá-las indevidamente como separadoras de campos.

O que queremos, então, é quebrar a linha nas vírgulas, mas apenas naquelas que não sejam precedidas de uma barra invertida. Sem problemas... hora de complicar um pouquinho a expressão regular.

@fields = split /(?<!\\),/, $line;

O "ruído" entre parêntesis é um zero-width negative lookbehind (ZWiNLoB). Ele indica que antes da vírgula não pode haver uma barra invertida. Note que o caractere com o qual o ZWiNLoB vai "casar" não fará parte do separador de linha, que continuará a ser somente a vírgula.

Muito bem, parecia tudo certo até que eu rodei novamente o script e percebi que ainda havia problemas. Algumas linhas ainda não estavam sendo quebradas corretamente. Desta vez o problema eram alguns campos que terminavam com uma barra invertida, a qual também era escapada por outra barra invertida. Por exemplo:

...,C:\\,...

Note que a vírgula não está escapada, sendo efetivamente um separador de campo.

E agora? A primeira coisa que pensei foi em usar um ZWiNLoB que case com uma barra não precedida por outra.

@fields = split /(?<![^\\]\\),/, $line;

Hmmm... mas não iria funcionar. E se o campo terminasse em duas barras?

...,C:\\\\,...

Por outro lado, se o campo termina em uma ou mais barras, como cada uma delas deve ser escapada o número total de barras antes da vírgula deve ser necessariamente par, certo? Portanto, o que eu preciso é de um ZWiNLoB que case com um número ímpar de barras. (Lembre que o ZWiNLoB é "negativo".)

@fields = split /(?<![^\\](?:\\\\)*\\),/, $line;

Só que o Perl reclamou:

Variable length lookbehind not implemented in regex; marked by <-- HERE in m/(?<![^\\](?:\\\\)*\\), <-- HERE /

Os ZWiNLoBs têm uma restrição forte: eles devem especificar strings de tamanho fixo, o que significa que eu não vou conseguir usá-los pra indicar uma vírgula não precedida por um número ímpar de barras...

OK, o ZWiNLoB na expressão anterior tinha a função de garantir que eventuais barras invertidas em um campo não precedam uma vírgula escapando-a. Mas a expressão como um todo quer mesmo é casar com uma vírgula, i.e., com o separador dos campos, pois eu a estou usando como argumento da função split.

E se eu tentar uma abordagem inversa? E se ao invés de tentar encontrar os separadores eu tentasse encontrar os campos? Nesse caso, a parte de tamanho variável da expressão não estaria num ZWiNLoB.

Pensei de cara numa abordagem interativa:

push @fields, $1 while $line =~ s/(.*?(?<!\\)(?:\\\\)*),//;
push @fields, $line;

A primeira linha remove o primeiro campo de $line e o anexa ao array @fields, até que sobre apenas o último campo, que não é sucedido por uma vírgula, e que é anexado na segunda linha. Ainda há um ZWiNLoB, mas ele tem um tamanho fixo, casando com um caractere diferente de barra invertida.

Não gostei muito. Eu preferiria não ter que tratar o último campo de modo especial. Logo percebi que com um pequeno ajuste na expressão regular isso seria possível.

push @fields, $1 while $line =~ s/(.*?(?<!\\)(?:\\\\)*)(?:,|$)//;

Desse modo, os campos podem ser sucedidos por uma vírgula ou pelo final da string.

Eu estava quase satizfeito, pois a solução acabou tendo uma linha apenas, mas o split era tão mais simples...

De qualquer modo, eu ainda precisava testar. E qual não foi a minha surpresa quando o script passou a demorar dezenas de segundos a mais que a versão anterior. Por um lado ele parecia estar correto, o que era um avanço. Mas alguma coisa o havia tornado muito lento e só podia ser aquele loop.

O problema é que o relatório tem algumas linhas realmente grandes, com quase um milhão de caracteres. Como a cada iteração a linha tem um campo removido, toda essa manipulação de strings parece ser bastante pesada.

Mas eu não preciso realmente remover os campos. Basta começar a procurar um campo a partir do final do campo anterior. (Eu não estou sendo fiel à história aqui, pois não cheguei a pensar nessa solução antes de começar a escrever isso aqui. Mas, em retrospecto, acho que ela cabe logicamente entre as duas últimas.)

push @fields, $1 while $line =~ /(.*?(?<!\\)(?:\\\\)*)(?:,|$)/g;

A mudança é sutil. Troquei apanas o operador "s///" pelo "//g". Como a expressão está sendo avaliada num contexto escalar, a cada iteração a busca começa a partir do final do trecho encontrado na iteração anterior. A vantagem é que a linha não precisa ser modificada, o que deve evitar grande parte da ineficiência anterior.

Mas, se eu quero uma lista de campos eu não preciso necessariamente encontrá-los um a um. Afinal, a mesma expressão regular anterior, quando avaliada num contexto de lista, retorna de uma vez todos os trechos encontrados dentro dos parêntesis.

Et voilá, eis minha solução final.

@fields = $line =~ /(.*?(?<!\\)(?:\\\\)*)(?:,|$)/g;

Ah, mas é claro que no script eu não usei uma variável explícita chamada $line. A linha estava realmente na variável implítica $_, o que me permitiu escrever a solução assim.

@fields = /(.*?(?<!\\)(?:\\\\)*)(?:,|$)/g;

Linda, não? E sucinta. E eficiente também. Como convém a um script Perl que se preze.

7 comentários:

  1. Caracas... Mais do que nunca perl significa "Pathologically Eclectic Rubbish Lister"!!!

    BTW, mesmo em casos extremos como este sempre TIMTOWTDI? :-P

    ResponderExcluir
  2. NetBackup?
    QUe feio Gu, usando software proprietário...
    O AMANDA é melhor que esse aí.

    ResponderExcluir
  3. @benê: Às vezes software é que nem família: a gente não escolhe. :-)

    Já li há muito tempo sobre o AMANDA e confesso que não fiquei muito impressionado. Recentemente andei pesquisando sobre o Bacula. Esse parece que tem mais chance de vingar. Já ouviu falar nele?

    ResponderExcluir
  4. Eu já usei o NetBackup quando ainda era Veritas. Tentei a tempos usar o ArcServe mas ele e o Linux não se deram muito bem.
    Acabei desistindo e indo pro AMANDA, que tem atendido bem os requisitos daqui. Já tinha usado ele na UNICAMP.

    Já ouvi falar do Bacula sim, mas não sei de muitos detalhes. Tlavez tenha que voltar a dar uma olhada, já que talvez eu mude o padrão de tapes daqui e aí o AMANDA vai desperdiçar muita fita. Aliás, esse é o único grande problema do AMANDA: é pelo menos uma fita por dia, independe se a fita "encheu" ou não. Se sua taxa de backup diário é pouco menos que a capacidade de "n" fitas, tudo bem. O problema surge quando sua fita é muito grande (uma LTO4, por exemplo) para seu volume de backup.

    ResponderExcluir
  5. @benê: Você já leu sobre deduplication?

    Eu estou lendo bastante sobre o assunto e estou achando que essa tecnologia tem muito futuro.

    Ela promete reduzir de 20 a 100 vezes a necessidade de armazenamento dos backups tornando "cost effective" trocar o backup em fita por backup em disco. Além disso, ela possibilita a manutenção de backups off-site via rede.

    Estou ansioso pra estudar mais.

    ResponderExcluir
  6. Olá,

    Você poderia ter usado o módulo Text::CSV_XS para ler este seu arquivo. Ele é optimizado para estes casos toscos de arquivos CSV com conteúdo incluindo o separador...

    Espero que ajude :-)

    -- Igor

    ResponderExcluir
  7. Obrigado pela dica, Igor. Eu não me lembro de já ter usado o Text::CSV_XS. Dei uma olhada na documentação e gostei... vou mantê-lo no meu arsenal de módulos.

    Mas acho que ele não daria conta desse problema específico. Pelo que entendi, se o caractere separador de campos precisa aparecer "escaped" dentro de um campo, todo o valor precisa estar devidamente "quoted". Mas o arquivo que eu preciso processar não vem assim e eu não tenho controle sobre isso.

    ResponderExcluir