Fonctions de hachage sur l’espace des sous-arbres

Fonctions de hachage sur l’espace des sous-arbres

La recherche de similarité sur du code source représenté sous la forme d’arbres de syntaxe nécessite des méthodes efficaces et de complexité praticable pour mettre en évidence des sous-arbres similaires. La comparaison exhaustive de toutes les paires de sous-arbres, soit npaires pour deux projets représentés par des arbres de n nœuds, n’est pas envisageable en pratique, d’autant plus si au-delà de la détermination d’une similarité exacte, des techniques d’alignement d’arbres sont mises en oeuvre. Il devient alors indispensable de réduire le nombre de comparaisons coûteuses d’arbres en utilisant des métriques ou valeurs de hachage afin de regrouper des sous-arbres de similarité supposée.Dans ce chapitre, nous évoquons quelques métriques utilisables sur les sous-arbres ainsi que certaines méthodes de hachage. Nous présentons également quelques techniques d’abstraction d’arbres de syntaxe permettant ainsi l’obtention de valeurs de hachage communes pour des sous-arbres présentant la même abstraction.Les métriques sur des unités structurelles du code source sont des mesures permettant de quantifier certaines propriétés du code. Elles s’expriment le plus souvent dans un espace vecto- riel réel. Nous passons maintenant en revue quelques unes des métriques les plus couramment utilisées.

Quelques méthodes de hachage de sous-arbres

Mesurer la complexité du code source a toujours été une préoccupation majeure en ingénierie logicielle. Ces métriques permettraient d’estimer la complexité du code et donc son coût de maintenabilité. Nous présentons ici les métriques de Halstead et la métrique de complexité cyclomatique pour finir sur une métrique basée sur le vecteur de comptage des types de nœuds. La figure 9.1 présente deux versions d’un court code de calcul de moyenne sur lesquels les métriques présentées ont été appliquées.) et d’effort (produit du volume et de la difficulté) sont dérivées de ce vecteur. Les opérateurs sont alors définis comme l’ensemble des opérateurs arithmétiques, des appels de fonction et des opérations d’affectation. Les opérandes sont quant à eux les variables locales, membres de structures et constantes.Il est aisé de constater que l’ajout ou la suppression de code inutile ainsi que la réécriture d’expressions peut avoir un impact important sur le vecteur V . D’autre part, il existe des risques importants que plusieurs unités structurelles de vecteurs accidentellement proches n’abritent aucune similarité réelle.McCabe a proposé une métrique [110] sur le graphe de contrôle de flux d’une unité structurelle. Un tel graphe représente l’ensemble des instructions d’un programme (nœuds), deux instructions étant liées par une arête s’il existe un chemin d’exécution où ces deux instructions sont exécutées séquentiellement. La complexité cyclomatique C est définie par C = E − N + 2P où E est le nombre d’arêtes, N le nombre de nœuds et P le nombre de composantes connexes du graphe. Cette valeur reflète le nombre d’expressions conditionnelles issues de structures de contrôles présentes dans le code.

Si la complexité cyclomatique peut être difficilement réduite, une augmentation artifi- cielle par l’ajout de structures de contrôle inutiles (cf 4.6) est possible. Au-delà d’une analyse statique, une détermination de la complexité cyclomatique dynamique par le suivi des che- mins d’exécution serait plus fiable pour localiser les conditionnelles suspectées invariantes. D’autre part, cette métrique dispose d’un pouvoir discriminateur réduit : l’espace de valeurs de complexité cyclomatique est trop faible afin de pouvoir disposer de groupes de sous-arbres d’effectifs suffisamment petits. Il est en effet rare de trouver des fonctions dont la complexité cyclomatique est supérieure à 20.Étant donnée une unité structurelle représentée par un arbre de syntaxe, il est possible d’exprimer le nombre de chaque type de nœuds présents au sein de cet arbre : nous pouvons ainsi en extraire un vecteur de comptage de nœuds. La taille de ce vecteur, représentant lenombre de types de nœud différents peut être réduite par une opération d’abstraction des types : nous traiterons de ce procédé en 9.2. Ce vecteur de comptage peut être généralisé au comptage des différents sous-arbres de taille ou de hauteur bornée. Cette technique est no- tamment employée par l’outil de recherche de similitudes Deckard [70] qui génère pour chaque sous-arbre à hacher un vecteur caractéristique comptant les petits sous-arbres inclus. Les dif- férents sous-arbres vectorisés sont ensuite regroupés en utilisant une technique de hachage localement sensible (Locality Sensitive Hashing, LSH) [52]. Cette technique permet de regrou- per des vecteurs de distance faible et donc des sous-arbres suffisamment voisins dans l’espace vectoriel des effectifs de sous-arbres caractéristiques.