Eu e o Thiago Ferreira estavámos mais uma vez na Caelum passando pela situação de gravar as senhas do usuário no banco de dados. Ainda hoje alguns grandes sites cometem o grave erro de guardar as senhas dos usuários em texto puro, fazendo com que um possível roubo de dados acarrete num problema ainda maior.

O processo clássico é guardar um hash (chamado também de digest nesse caso) da senha do usuário, usando algum algoritmo de hash unidirecional. Isso pode ser feito utilizando uma chamada de função na query do banco de dados (como MD5()no MySQL), ou, o mais utilizado para não ter de trafegar a senha entre o servidor web e o banco de dados: com o MessageDigest do javax.security. Através dessa classe você pode facilmente gerar o hash de uma senha:

MessageDigest algorithm = MessageDigest.getInstance("MD5");
byte messageDigest[] = algorithm.digest("senha".getBytes("UTF-8"));

Agora temos um array de bytes que podemos guardar no banco de dados. Quando o usuário logar, basta digerirmos novamente a senha colocada no formulário web, e comparar o hash resultante com o que há no banco. Você poderia guardar esse array de byte como uma String fazendo new String(bytes, encoding), porém muito mais usual é guardar os hexadecimais desses bytes dentro de uma String:

StringBuilder hexString = new StringBuilder();
for (byte b : messageDigest) {
	hexString.append(String.format("%02X", 0xFF & b));
}
String senha = hexString.toString();

Isso gerará e8d95a51f3af4a3b134bf6bb68a213a.

Apesar de muito usado, o MD5 já é considerado um algoritmo de hash quebrado, pois hoje em dia podemos rapidamente, através de força bruta, descobrir uma String que gere o mesmo hash, já que neste algoritmo ocorrem mais colisões do que o que foi inicialmente imaginado por seus criadores. Muitos passaram a usar o SHA-1, porém este já da sinais de que, num futuro próximo, será quebrado com força bruta. O próprio governo americano já evita utilizar a família SHA-1, priorizando o uso do SHA-2. Logo, o procedimento completo mais adequado atualmente seria usar algo como:

			MessageDigest algorithm = MessageDigest.getInstance("SHA-256");
			byte messageDigest[] = algorithm.digest(original.getBytes("UTF-8"));

			StringBuilder hexString = new StringBuilder();
			for (byte b : messageDigest) {
				hexString.append(String.format("%02X", 0xFF & b));
			}
			String senha = hexString.toString();

Para tornar seu sistema ainda mais seguro em relação as senhas guardadas, pode-se ainda adicionar salts, mais iterações de hash e outras técnicas que tornaria ainda mais difícil um possível ataque de força bruta contra uma base de dados roubada, se protegendo também contra o provável uso de senhas fracas por parte de seus usuários.

São incontáveis os posts no GUJ com uma pergunta semelhante: “Posso extrair o nome de um tipo genérico?“, “Não consigo extrair tipo do genérico!“, “Utilizando generics para instanciar objetos“, entre outros. Curioso que esse tipo de pergunta tem aumentado muito nos últimos tempos, identificando um possível crescimento no uso do Java 5 em diante. Já era a hora!

Eu já havia postado sobre isso quando falei de reificação de tipos parametrizados, mas de uma maneira mais geral.

A questão básica é a seguinte: Se eu tenho um tipo genérico, que recebe um tipo parametrizado T como argumento, eu posso instanciar T de alguma forma?

Quem sabe tentar assim:

class Dao<T> {
  public T cria() {
    return new T();
  }  
}

Essa forma não funciona. Você não tem garantias sobre os construtores que o tipo T possui. E então se tentarmos assim:

class Dao<T> {
  public T cria() {
    return T.class.newInstance();
  }  
}

Aqui a sintaxe até poderia ser possível, mas infelizmente o java não sabe quem é T nem mesmo em tempo de execução. Nem mesmo com manipulação de bytecode ou qualquer outro recurso. Isso porque o compilador “apaga” essa informação depois de utilizada: é a tal da mal falada erasure.

Qual seria a vantagem da erasure?

Antes de mais nada: erasure não serve para poder rodar código do Java 5 em VMs Java 1.4 ou menor! Não é esse o objetivo.

Quando a JSR14 do generics foi proposta, eles queriam mais que compatibilidade para trás em relação a compilação, eles queriam também a possibilidade de migrar o código antigo para poder usar código novo: uma ArrayList precisa poder ser passada como argumento para alguém que receba List<QualquerClasse> como argumento!

Para ilustrar a situação, imagine que eu tenho uma aplicação grande X que usasse a classe ArrayList em muitos lugares (como a grande maioria das aplicações). Essa aplicação X usa a biblioteca B, que recebe List como argumento em muitos de seus métodos. Se um dia a bibioteca B passasse a usar List genérica, gostaríamos que a aplicação X atualizasse B sem maiores problemas: sem precisar recompilar nada, nem trocar nada no código fonte. O Neal Gafter escreveu muito sobre isso pouco antes da release do Java 5, dada as inúmeras críticas que eles estavam recebendo.

Se o Java tivesse optado por outra maneira de implementar generics, teria ou quebrado compatibilidade com o uso não genérico de classes que viraram genéricas, ou precisaria criar classes paralelas as atuais, praticamente copiadas e coladas, só que estas genéricas, tornando as antigas deprecated ou legadas.

Como o .NET resolveu o mesmo problema?

O .NET seguiu essa segunda forma, e criou uma hierarquia quase que paralela de coleções dentro do name space System.Collections.Generic.

A IList é a interface que define as operações em uma lista não genérica, e a ArrayList é sua implementação mais comumente usada. Quando entrou generics no .NET eles criaram uma outra interface para a lista, com mesmo nome, só que genérica: a IList<T>.

A classe List já é a implementação da interface genérica, e é ela quem você vai usar em vez de ArrayList. Ela possui uma definição bem estranha:

public class List : IList, ICollection,
    IEnumerable, IList, ICollection, IEnumerable

Ela implementa tanto a lista genérica como a não genérica. O .NET tem um recurso que nós não temos, que faz com que apesar dessa lista também implementar a interface não genérica, você só consegue invocar os métodos não genéricos (que trabalham com Object) se estiver se referenciando a ela explicitamente como uma lista não genérica, como o código abaixo:

IList x = new List<String>();
x.Add(2);

Apesar desse código compilar, no .NET temos essa informação dos tipos genéricos em tempo de execução, o que fará gerar uma exceção:

System.ArgumentException: The value "2" is not of type "System.String" e cannot be used in this generic collection


No Java teríamos apenas um unchecked warning na linha da declaração da referência, e uma possível ClassCastException mais a frente no código.

Aqui a vantagem é você poder passar uma List genérica para um código .NET antigo, que recebe como argumento uma IList não genérica. Além disso, no .NET você pode sim descobrir quem é T em tempo de execução:

class ClasseGenerica<T> {
  void metodo() {  Console.WriteLine(typeof(T)); }
}

Em resumo: o sistema de generics do .NET é realmente seguro, não temos como burlá-lo através de unchecked casts, como ocorre em Java. O Java novamente sacrificou alguns recursos interessantes em favor a compatibilidade de versões e interoperabilidade entre classes genéricas e as não genéricas já existentes. Cada um com sua vantagem. Como citei no outro artigo, existem algumas idéias de dar suporte a tipos genéricos reificados no Java, ao mesmo tempo que outros ficariam ainda com a erasure, sendo que você pode escolher qual o que te agrada para aquela classe genérica em particular. Talvez ter as duas opções adicione ainda mais complexidade a tipagem genérica do Java, mas eu particularmente gosto da idéia.

Mais uma vez um post que era para ser sucinto ficou longo. Agradeço ao Rafael Steil e Rodrigo Kumpera pela colaboração, e ao Lucas Cavalcanti e Guilherme Moreira pedindo para que fosse elaborado um post mais completo sobre esse assunto tão pertinente.

A Caelum está lançando hoje mais uma apostila disponível gratuitamente para download: Algoritmos e Estruturas de Dados em Java.

Ela vem sendo formulada há algum tempo, baseada na experiência do curso de versão do IME USP “Algoritmos e Estruturas de dados” que é ministrado por Paulo Silveira, Guilherme Silveira e por mim (Rafael Cosentino) desde 2005.

Abordamos as principais estruturas de dados como Listas, Pilhas, Filas, Tabela de Espalhamento (Hash) e Mapas, e os algoritmos para a manipulação das mesmas. Há ainda tópicos como Recursão, Ordenação (selection-sort, insertion-sort, quick-sort e merge-sort), Pesquisa (sequencial e binária), Busca em Largura, Busca em Profundidade e Consumo de Tempo.

Normalmente, o desenvolvedor tem um conhecimento superficial sobre as estruturas de dados, sabendo mais ou menos como utilizar as que já estão prontas, sem saber como elas funcionam por dentro, e o que é muito pior, sem saber para quais tipos de problemas cada estrutura é eficiente. Esse conhecimento superficial não basta para desenvolver uma boa aplicação.

Na apostila, mostramos casos em que fica claro como a escolha de uma estrura errada para um determinado problema pode prejudicar o desempenho de uma aplicação ou até mesmo tornar inviável a utilização da mesma. Com alguns exemplos e só um pouquinho de teoria de Ciência da Computação veremos que alguns problemas levariam séculos (séculos de verdade!!!) para serem resolvidos pelo computador se a escolha da estrutura fosse errada e alguns segundos com uma estrutura adequada. E iremos mais afundo, veremos que uma implementação ruim de uma determinada estrutura pode obter resultados desastrosos.

Também, salientaremos a idéia do reaproveitamento. Não precisamos reinventar a roda: mostramos, por exemplo, como implementar uma Pilha ou uma Fila reaproveitando uma Lista. Além disso tudo, mostraremos as implementações do Java para as estrutura de dados do nosso curso. Essas implementações são bem semelhantes as que iremos fazer do zero durante o curso.

O material ainda está na versão beta, ainda faltam alguns poucos tópicos, algumas figuras e um pouco de texto. Além da qualidade técnica, estamos investindo muito na qualidade visual do material; o Tiago Allen Marques de Oliveira, nosso desinger, está preparando imagens fantásticas para apostila.

A alguns anos atrás fiz uma entrevista em uma grande empresa de Java, uma dessas com 3 letras, e a primeira frase que o entrevistador me dirigiu ao ver meu curriculum foi um sonoro:

“Essas competições de programação não dizem nada!”

Essas competições não dizem se o programador é um bom engenheiro de software ou profundo conhecedor de alguma tecnolgoia, é verdade. Nem é essa a intenção.
As questões dessas provas apresentam problemas mais complexos que o comumente exigido no mercado de TI, e não foca tanto na parte de desenvolvimento, mas mais na capacidade de encontrar soluções. Para um cientista da computação (ou um matemático, no meu caso), essa capacidade é mais importante do que o próprio desenvolvimento e codificação. Vou relatar aqui três competições as quais tiver a oportunidade de participar este ano. Em todas as três, grandes empresas como o Google e IBM, sempre estavam a caça de talentos. Pode-se dizer que um bom resultado nessas competições certamente atrairão diversas propostas de emprego, mestrado e doutorado.

Primeiro veio o Google Code Jam Latin America. Os problemas tinham o mesmo nível das competições internacionais, mas com menos fases. Na última etapa, em Belo Horizonte, tive a chance de encontrar alguns conhecidos e fazer novas amizades no meio dos 50 finalistas, dentre elas Jelani Nelson, aluno de PhD e técnico do MIT, participando pela Virgin Islands; Vinicius Fortuna ex-competidor e agora engenheiro de software do Google em Nova Iorque, que veio entrevistar os competidores; Wanderley Guimarães, atual técnico do IME-USP, além de já conhecidos e excelentes competidores do ITA e PUC-RIO. Pelo vídeo promocional, da para você ter uma idéia do quão a sério o Google leva essas competições:

Depois teve a final mundial da ACM (ACM-ICPC) em Tokyo, Japão, onde fui representando o time do IME-USP, depois da qualificação pela Maratona de Programação brasileira. Lá contamos com a presença de diversos nomes interessantes, como o criador do Ruby, Yukihiro Matsumoto, que palestrou sobre sua linguagem de programação. Entre seus comentários oportunos, disse que eficácia não é a grande preocupação de Ruby; 80% do design de uma linguagem está feito se o nome for curto, pequeno e bonito (Ruby). Outra frase dele foi “Web 2.0, o que é isso?”. Modesto.

Também estava presente Stuart Feldman que, além de presidente da ACM e criador do primeiro compilador de Fotran 77, fez parte do grupo que criou o Unix e o make. Yuhichi Nakamura, criador do Xerces (xml4j), e diretor do IBM Tokyo Research Lab estava ajudando na coordenação do evento.

Nessa competição, mais de seis mil equipes participaram do evento nas competições regionais, de mais de 1700 universidades diferentes do mundo inteiro. A competição foi emocionante, com os quatro times brasileiros bem colocados. Além disso, dois times brasileiros resolveram 4 problemas, um marco na história da competição, onde o problema mais simples envolvia um algoritmo do tipo Longest Common Subsequence. Esse é um algoritmo muito usado em inúmeros lugares, como em biologia computacional para verificar padrões de sequencias de DNA. No fim das contas, os problemas dessas competições não são tão irreais assim! Alguns problemas são muito difíceis, sendo que nenhuma equipe do mundo conseguiu resolver. Você pode ver a prova da competição aqui.

O evento aconteceu no Hilton Tokyo Bay, um hotel dentro da Disney de Tokyo e muito bonito. Os quartos tinham vista para o monte Fuji e foi possível conhecer um pouco do país e de sua história.

O Fórum Internacional de Software Livre preparou esse ano uma competição diferente, a Arena de programação, composta por duas fases. Para poder se inscrever, era necessário resolver um problema de lógica no próprio site, no estilo python-challenge, mas bem mais simples. A idéia era encontrar o caminho para a inscrição usando de seus dotes “hackers”. O Dorneles postou a descrição de como se inscrever em detalhes.

Chegando no evento, pronto para a primeira fase, a Arena era um cercado de vidro, quase um aquário, onde os animais eram os programadores.

A primeira fase terminou com alguns conhecidos entre os top. O Hugo Corbucci, colega de viagem ao fisl pelo IME-USP, o Klaus Wustefeld e o Kalecser Kurtz, o Dornelles Tremea e eu nos qualificamos entre os top 12. A segunda fase começou no dia seguinte e era composta por, supostamente, 24 horas de programação non-stop. Os 12 primeiros da fase anterior foram divididos em quatro grupos de três competidores. Na minha equipe? Kalecser, expert em Java e Dornelles, expert em Python e linux em geral. A tarefa? Resolver quatro bugs ou feature requests do Debian. Isso mesmo. Eles deram quatro códigos de bugs que estão ocorrendo em pacotes do Debian ou que feature requests que os usuários postaram e pediram para as equipes resolverem. Excelente proposta!

O primeiro bug envolvia um problema com o teclado. Você que é fã incondicional do Debian pode alternar para o tty1 (Ctrl+alt+F1), ativar o CAPS LOCK e tentar digitar “ABCD”… se o resultado for “ABcD”, você reproduziu o bug – que só funciona com alguns layouts de teclado. Encontramos muitas informações sobre o assunto e não conseguimos resolvê-lo, fomos capazes de encontrar textos indicando que o problema era mais delicado. Tudo isso após passar por muito código fonte em bash, perl etc. O segundo bug estava no pacote cdebconf, que é responsável pelo processo de configuração de pacotes debian durante o processo de instalação dos mesmos. Após correr por diversos arquivos feitos em C, com um “quê” de orientação a objeto, fomos capazes de isolar o bug e corrigi-lo, e o patch deve se tornar disponível em breve.

O terceiro bug envolve o bugtracking do debian, que não apresentava os dados da maneira que era requisitado, enquanto o último problema estava ligado ao particionador, que encontrava problemas durante o redimensionamento em determinados casos. Muito código perl apareceu enquanto solucionávamos o terceiro bug, mas não houve tempo suficiente para sequer olhar com calma o último. No dia seguinte, a segunda parte dessa fase envolveu o desenvolvimento do zero de um programa para facilitar a internacionalização dos pacotes debian. Nosso objetivo era utilizar o Lucene para fazer o partial matching de palavras ou frases já traduzidas anteriormente em outros pacotes, mas devido ao padrão de i18n adotado pelo debian, o Java acabou segurando um pouco o desenvolvimento, mas ainda fomos capazes de mostrar algo funcional com uma implementação do Edit Distance para procurar palavras similares.

O resultado de tudo isso saiu no final do dia, durante o fechamento do evento, nossa equipe ficou em primeiro lugar! O que ganhei com tudo isso? Conheci novas pessoas que trabalham com projetos open source de áreas diferentes de Java, coloquei em prática o meu conhecimento de C que só usava na teoria, e ajudei com um projeto que jamais sonhei ser possível ajudar. Claro, o notebook que deram para cada um de nossa equipe também conta! Fui entrevistado a respeito dessa competição. Espero encontrar vocês nas próximas!

Os desenvolvedores costumam levar um susto com as assinaturas dos métodos das interfaces do framework das coleções pós-java5: muito mais difícil do que o monte de Es, supers, extends, ?s e &s são os métodos que ainda recebem Object como argumento.

Um exemplo é o método contains. Apesar dele estar na interface parametrizada Collection<E> ele recebe Object em vez de E! Parece um paradoxo: a vantagem do generics não seria exatamente ter uma tipagem mais forte nesses casos, em especial em classes containers? Algumas pessoas acham que é por compatibilidade binária, mas não é, porque a erasure de um método que recebe T é Object, e isso manteria a compatibilidade.

Para entender melhor a decisão da Sun em cada uma dessas assinaturas de métodos você sempre precisa levar em conta dois pontos: erasure e o uso do coringa. Antes vamos relembrar esses conceitos. Considere o código que imprime uma lista de objetos Comparable:

  void imprime(List<Comparable> lista) {
    for (Comparable c : lista)
      System.out.println(c);
  }

Podemos passar para esse método uma List<Comparable>. E uma List<String>? Não podemos, porque uma List<String> não é uma List<Comparable>. Se isso fosse possível, poderíamos adicionar objetos Comparable que não apenas Strings dentro de uma List<String>, quebrando o contrato! Para resolver esse problema, mudamos a assinatura do nosso método para:

  void imprime(List<? extends Comparable> lista) {
    for (Comparable c : lista)
      System.out.println(c);
  }

Agora podemos passar uma List<String>, pois isso é uma List<? extends Comparable>, isto é, uma lista de algum tipo que é compatível com Comparable. Porque então não usamos sempre esse idiomismo? Repare então no seguinte método:

  public void adicionaString(List<Comparable> lista) {
    lista.add("caelum");    
  }

Aqui temos o mesmo problema. Não podemos receber como referência uma List<String>! Vamos tentar aplicar o mesmo procedimento:

  public void adicionaString(List<? extends Comparable> lista) {
    lista.add("caelum"); // não podemos invocar métodos que recebem o tipo
      // parametrizado (a menos que seja passado null)
  }

O código acima não compila! Isso ocorre porque List<? extends Comparable> pode receber uma lista de qualquer tipo que seja Comparable. Se isso fosse possível, alguém poderia passar como argumento uma List<Integer>, e no fim do método esta lista de inteiro estaria contendo uma String, quebrando o contrato novamente!

Como resolver esse problema? Não tem como! Se você recebe um objeto parametrizado pelo coringa ?, você nunca poderá invocar um método desse objeto, porque você não sabe qual o tipo que ele realmente aceita! A linguagem não permite isso porque não sabe exatamente o que você vai fazer com esse objeto. Em alguns casos, semanticamente, apesar de um método receber um tipo parametrizado, não tem problema ele receber um objeto que não esteja de acordo com seu tipo parametrizado. Esse é exatamente o caso do método contains: não haveria problema de passar um Integer para o contains de uma List<String>! Mas se contains recebesse E, o seguinte código não compilaria:

  public boolean contemCaelum(List<? extends Comparable> lista) {
    return lista.contains("caelum"); // ok, recebe Object!
  }

Essa situação é a mesma para outros métodos, como o Collection.remove(Object), e o Map.get(Object). Ambos os casos seriam catastróficos se recebessem o tipo parametrizado como argumento.

A API de coleções traz assinaturas muito mais estranhas. Eu demorei bastante até entender por completo a assinatura de alguns métodos da Collections, como por exemplo o Collections.min:

public static <T extends Object & Comparable<? super T>> T 
    min(Collection<? extends T> coll);

em vez de simplesmente uma ingênua assinatura como:

public static <T extends Comparable<T>> T min(Collection<T> coll);

Fica aí o desafio para você também queimar neurônios…