Parsing statique: Dire si deux fonctions Javascript sont les mêmes

Question

Je cherche un moyen, en utilisant l'analyse statique de deux fonctions JavaScript, de dire si elles sont identiques. Laissez-moi définir plusieurs définitions de "pareil".

Niveau 1: Les fonctions sont les mêmes, à l'exception d'espaces blancs différents, par ex. TABS, CR, LF et ESPACES.

Niveau 2 Les fonctions peuvent avoir des espaces différents comme le niveau 1, mais peuvent aussi avoir des noms de variables différents.

Niveau 3 ???

---

Pour le niveau un, je pense que je pouvais supprimer tous les (non-littérale, ce qui peut être difficile) des espaces de chaque chaîne contenant les deux définitions de fonction JS, puis comparer les cordes. Pour le niveau deux, je pense que je devrais utiliser quelque chose comme SpiderMonkey's parser pour générer deux arbres d'analyse, puis écrire un comparateur qui marche les arbres et permet aux variables d'avoir des noms différents.

---

[Modifier] Williham, fait un bon point ci-dessous. Je veux dire identique. Maintenant, je cherche des stratégies pratiques, particulièrement en ce qui concerne l'utilisation d'arbres d'analyse.

Answer 1

remodifier:

Pour disserter sur ma suggestion pour déterminer des fonctions identiques, le flux suivant peut être proposé:

Niveau 1: Retirez les espaces blancs qui ne fait pas partie d'une chaîne littérale; insérer des lignes après chaque {, ; et } et comparer. Si égal; les fonctions sont identiques, sinon:

Niveau 2: Déplacer toutes les déclarations de variables et affectations qui ne dépendent pas de l'état d'autres variables définies dans la même portée au début de la portée dans laquelle elles sont déclarées (ou si ne voulant pas réellement analyser le JS, le début des accolades); et les commander par longueur de ligne; traiter tous les noms de variables comme étant de 4 caractères, et revenir à l'ordre alphabétique en ignorant les noms de variables en cas de longueurs liées. Réorganisez toutes les collections par ordre alphabétique et renommez toutes les variables vSNN, où v est littéral, S le nombre d'accolades imbriquées et NN l'ordre dans lequel la variable a été rencontrée.

Comparer; en cas d'égalité, les fonctions sont identiques, sinon:

Niveau 3: Remplacer toutes les chaînes littérales avec "sNN", où " et s sont littérale et NN est l'ordre dans lequel la chaîne a été rencontrée. Comparer; si égales, les fonctions sont identiques, sinon:

Niveau 4: Normaliser les noms de toutes les fonctions connues pour être identiques en utilisant le nom de la fonction ayant la priorité la plus élevée selon l'ordre alphabétique (dans l'exemple ci-dessous, les appels à p_strlen() seraient remplacés par c_strlen() Répéter ré-ordonnancements selon le niveau 1 si nécessaire comparer,.. en cas d'égalité, les fonctions sont identiques, sinon, les

---

fonctions sont presque certainement pas identiques. Réponse originale:

Je pense que vous trouverez que vous voulez dire "identique", pas "le même".

La différence, que vous trouverez, est essentiel:

Deux fonctions sont identiques si, suivant une certaine manière de la normalisation, (suppression des espaces non littérale, renommer et les variables de réordonnancement à un ordre normalisé, en remplaçant les littéraux de chaînes par des espaces réservés, ...) ils se comparent à littéralement égal.

Deux fonctions sont le même si, lorsqu'elles sont appelées pour une valeur d'entrée donnée, elles donnent la même valeur de retour. Considérons, dans le cas général, un langage de programmation qui a compté des chaînes terminées par zéro (chaînes hybrides Pascal/C, si vous voulez). Une fonction p_strlen(str) peut regarder le nombre de caractères de la chaîne et retourner cela. Une fonction c_strlen(str) peut compter le nombre de caractères dans la chaîne et renvoyer cela.

Bien que ces fonctions ne seront certainement pas identiques, elles seront les mêmes: Pour toute valeur d'entrée donnée (valide), elles donneront la même valeur.

---

Mon point est:

Détermination wether deux fonctions sont identiques (ce que vous semblez vouloir réaliser) est un (modérément) problème trivial, fait que vous décrivez.

Déterminer si deux fonctions sont vraiment les mêmes (ce que vous pourriez réellement vouloir réaliser) est non-trivial; en fait, c'est carrément dur, probablement lié au Halting Problem, et pas quelque chose qui peut être fait avec l'analyse statique.

---

Edit: Bien sûr, les fonctions qui sont identiques sont également les mêmes; mais d'une manière très spécifique et rarement utile pour une analyse complète.

Answer 2

Votre approche pour le niveau 1 semble raisonnable.

Pour le niveau 2, qu'en est-il de la substitution de variables rudimentaires sur chaque fonction, puis de l'approche pour le niveau 1? Commencez par le début et, pour chaque déclaration de variable, renommez-les en var1, var2, ... varX. Cela n'aide pas si les fonctions déclarent des variables dans différents ordres ... var i et var j peuvent être utilisés de la même manière dans les deux fonctions mais sont déclarés dans des ordres différents. Alors vous êtes probablement laissé faire une comparaison des arbres d'analyse comme vous mentionnez.

Answer 3

Voir l'outil (sémantique) Smart Differencer de mon entreprise. Cette famille d'outils analyse le code source en fonction de la grammaire du niveau de compilation pour la langue d'intérêt (dans votre cas, JavaScript), construit des ASTs, puis compare les AST (qui ignore effectivement les espaces et les commentaires). Les valeurs littérales sont normalisées, donc peu importe comment elles sont "épelées"; 10E17 a la même valeur normalisée que 1E18.

Si les deux arbres sont les mêmes, il vous dira "pas de différences". Si elles diffèrent par un renommage cohérent d'un identifiant, l'outil vous indiquera le changement de nom et le bloc dans lequel il se produit. D'autres différences sont signalées par des insertions, des suppressions, des copies ou des déplacements d'éléments de langage (identificateur, instruction, bloc, classe, ...). L'objectif est de rapporter le petit ensemble de deltas qui expliquent de façon plausible les différences. Vous pouvez voir des exemples pour un certain nombre de langues sur le site Web.

Vous ne pouvez pas aller beaucoup plus loin dans la pratique; Pour déterminer si deux fonctions calculent la même réponse, vous devez en principe résoudre le problème d'arrêt. Vous pourriez être capable de détecter où deux éléments de langage qui sont des éléments d'une liste commutative, peuvent être commutés sans effet; nous travaillons là-dessus. Vous pourriez être en mesure d'appliquer des réécritures de normalisation pour canoniser certains formulaires (par exemple, mapper toutes les déclarations multiples en une séquence de déclarations uniques triées lexicalement). Vous pourriez être en mesure de convertir le code source en son ensemble de flux de données équivalent, et faire une correspondance isomorphisme graphique (l'apprenti programmeur du MIT dans les années 1980 a proposé de le faire, mais je ne pense pas qu'ils y sont arrivés).

Il y a plus de travail à faire que prévu.