Comment fonctionne la complétion de code?

https://stackoverflow.com/questions/1220099

10-07-2019
|

Question

De nombreux éditeurs et IDE ont l’achèvement du code. Certains d'entre eux sont très & "Intelligents &"; d'autres ne sont pas vraiment. Je suis intéressé par le type le plus intelligent. Par exemple, j'ai vu des IDE n'offrant une fonction que si elle est a) disponible dans l'étendue actuelle b) sa valeur de retour est valide. (Par exemple, après & "5 + foo [tab] &"; Il n'offre que des fonctions qui renvoient quelque chose qui peut être ajouté à un entier ou à des noms de variables du type correct.) J'ai également vu qu'ils plaçaient l'option la plus souvent utilisée ou la plus longue devant la liste.

Je réalise que vous devez analyser le code. Mais généralement, lors de l'édition du code actuel n'est pas valide, il contient des erreurs de syntaxe. Comment analyser quelque chose qui est incomplet et contient des erreurs?

Il existe également une contrainte de temps. L’achèvement est inutile s’il faut quelques secondes pour dresser une liste. Parfois, l'algorithme d'achèvement traite avec des milliers de classes.

Quels sont les bons algorithmes et structures de données pour cela?

La solution

Le moteur IntelliSense de mon produit de service de langage UnrealScript est compliqué, mais je vais vous donner le meilleur aperçu possible ici. Le service en langage C # dans VS2008 SP1 est mon objectif de performance (pour une bonne raison). Ce n'est pas encore là, mais c'est assez rapide / précis pour pouvoir offrir des suggestions en toute sécurité après la saisie d'un seul caractère, sans attendre ctrl + espace ou si l'utilisateur tape un . (point). Plus les gens [travaillant sur les services linguistiques] obtiennent des informations sur ce sujet, meilleure sera l'expérience des utilisateurs finaux si jamais j'utilisais leurs produits. J'ai eu la malheureuse expérience de travailler avec un certain nombre de produits qui ne prêtaient pas une attention toute particulière aux détails et, par conséquent, je me suis beaucoup plus battu avec l'IDE que je ne l'avais programmé.

Dans mon service linguistique, il est présenté comme suit:

Obtenez l'expression au curseur. Cela va du début de l'expression membre d'accès à la fin de l'identifiant sur lequel se trouve le curseur. L’expression d’accès aux membres se présente généralement sous la forme aa.bb.cc, mais peut également contenir des appels de méthode comme dans aa.bb(3+2).cc.
Obtenir le contexte entourant le curseur. C'est très délicat, car il ne suit pas toujours les mêmes règles que le compilateur (histoire longue), mais supposons que c'est le cas. Généralement, cela signifie obtenir les informations mises en cache sur la méthode / classe dans laquelle se trouve le curseur.
Dites que l'objet de contexte implémente IDeclarationProvider, où vous pouvez appeler GetDeclarations() pour obtenir un IEnumerable<IDeclaration> de tous les éléments visibles dans l'étendue. Dans mon cas, cette liste contient les locales / paramètres (si dans une méthode), membres (champs et méthodes, statiques uniquement sauf dans une méthode d'instance, et aucun membre privé de types de base), globals (types et constantes pour le langage I travaille sur), et des mots-clés. Dans cette liste sera un élément portant le nom aa. Lors de la première étape de l'évaluation de l'expression dans # 1, nous sélectionnons l'élément dans l'énumération de contexte avec le nom IDeclaration, ce qui nous donne un -> pour l'étape suivante.
Ensuite, j'applique l'opérateur sur le declaration.GetMembers(".") représentant cc pour obtenir un autre GetMembers contenant les " membres & "; (dans un certain sens) de List<IDeclaration>. Étant donné que l'opérateur List<Name> est différent de l'opérateur Name, j'appelle <=> et je m'attends à ce que l'objet <=> applique correctement l'opérateur répertorié.
Cela continue jusqu'à ce que je clique sur <=>, où la liste de déclarations peut contenir ou non un objet portant le nom <=>. Comme vous le savez sûrement, si plusieurs éléments commencent par <=>, ils doivent également apparaître. Je résous ce problème en prenant l'énumération finale et en la passant par mon algorithme documenté à fournir à l'utilisateur l'information la plus utile possible.

Voici quelques notes supplémentaires sur le backend IntelliSense:

J'utilise beaucoup les mécanismes d'évaluation paresseux de LINQ pour mettre en œuvre <=>. Chaque objet de mon cache est capable de fournir un foncteur qui évalue à ses membres, donc effectuer des actions compliquées avec l’arbre est presque trivial.
Au lieu que chaque objet conserve un <=> de ses membres, je conserve un <=>, où <=> est une structure contenant le hachage d'une chaîne spécialement formatée décrivant le membre. Il existe un énorme cache qui associe des noms à des objets. Ainsi, lorsque je réanalyse un fichier, je peux supprimer de la mémoire cache tous les éléments déclarés dans le fichier et le remplir à nouveau avec les membres mis à jour. En raison de la manière dont les foncteurs sont configurés, toutes les expressions s’appliquent immédiatement aux nouveaux éléments.

IntelliSense & "frontend &";

Lors de la saisie de l'utilisateur, le fichier est syntaxiquement incorrect plus souvent que correct. En tant que tel, je ne veux pas supprimer au hasard des sections du cache lorsque l'utilisateur tape. J'ai un grand nombre de règles de cas spéciaux en place pour gérer les mises à jour incrémentielles aussi rapidement que possible. Le cache incrémentiel n’est conservé que localement dans une mémoire ouverte.file et aide à s’assurer que l’utilisateur ne réalise pas que leur frappe est responsable du fait que le cache principal contient des informations de ligne / colonne incorrectes pour des éléments tels que chaque méthode du fichier.

Un des facteurs qui fait l’échange est que mon analyseur est rapide . Il peut gérer une mise à jour complète du cache d'un fichier source 20000 lignes en 150 ms tout en fonctionnant de manière autonome sur un thread en arrière-plan de priorité basse. Chaque fois que cet analyseur termine une passe sur un fichier ouvert avec succès (syntaxiquement), l'état actuel du fichier est déplacé dans le cache global.
Si le fichier n’est pas syntaxiquement correct, j’utilise un ANTLR. filtre analyseur (désolé pour le lien - la plupart des informations se trouvent sur la liste de diffusion ou ont été recueillies à la lecture du code source) pour analyser le fichier à la recherche de:
- Déclarations de variable / champ.
- La signature pour les définitions de classe / structure.
- La signature pour les définitions de méthode.
Dans le cache local, les définitions de classe / struct / méthode commencent à la signature et se terminent lorsque le niveau d'imbrication de l'accolade redevient pair. Les méthodes peuvent également se terminer si une autre déclaration de méthode est atteinte (pas de méthodes d'imbrication).
Dans le cache local, les variables / champs sont liés à l'élément non fermé immédiatement précédent. Voir le bref extrait de code ci-dessous pour obtenir un exemple de la raison pour laquelle cela est important.
De plus, en tant que type d'utilisateur, je conserve un tableau de remappage indiquant les plages de caractères ajoutées / supprimées. Ceci est utilisé pour:
- S'assurer que je peux identifier le contexte correct du curseur, puisqu’une méthode peut se déplacer dans le fichier entre les analyses complètes.
- Assurez-vous que Aller à Déclaration / Définition / Référence localise correctement les éléments dans les fichiers ouverts.

Extrait de code pour la section précédente:

class A
{
    int x; // linked to A

    void foo() // linked to A
    {
        int local; // linked to foo()

    // foo() ends here because bar() is starting
    void bar() // linked to A
    {
        int local2; // linked to bar()
    }

    int y; // linked again to A

J'ai pensé ajouter une liste des fonctionnalités IntelliSense que j'ai mises en œuvre avec cette présentation. Les images de chacun se trouvent ici.

Remplissage automatique
Conseils sur les outils
Conseils de méthode
Affichage des classes
Fenêtre Définition du code
Navigateur d'appels (VS 2010 l'ajoute enfin à C #)
Trouver toutes les références sémantiquement correctes

Autres conseils

Je ne peux pas dire exactement quels algorithmes sont utilisés par une implémentation particulière, mais je peux faire des suppositions éclairées. Une trie est une structure de données très utile pour résoudre ce problème: l'EDI peut conserver un grand fichier en mémoire de tous les symboles de votre projet, avec quelques métadonnées supplémentaires sur chaque nœud.

Lorsque vous tapez un caractère, celui-ci emprunte un chemin. Tous les descendants d'un noeud particulier sont des achèvements possibles. Il suffit ensuite à l'EDI de filtrer ceux-ci en fonction de ceux qui ont un sens dans le contexte actuel, mais il ne doit en calculer que le nombre pouvant être affiché dans la fenêtre contextuelle de complétion par des tabulations.

Le remplissage par onglet plus avancé nécessite un test plus compliqué. Par exemple, Visual Assist X dispose d'une fonction permettant de saisir uniquement les lettres majuscules des symboles CamelCase - par exemple: Si vous tapez SFN, le symbole SomeFunctionName s'affiche dans la fenêtre de complétion par tabulation.

Le calcul de la trie (ou d'autres structures de données) nécessite l'analyse de tout votre code pour obtenir une liste de tous les symboles de votre projet. Visual Studio enregistre cela dans sa base de données IntelliSense, un fichier .ncb stocké à côté de votre projet, de sorte qu'il ne soit pas obligé de tout réparer à chaque fermeture et réouverture de votre projet. La première fois que vous ouvrez un projet volumineux (par exemple, vous venez de synchroniser le contrôle de source de formulaire), VS prendra le temps de tout analyser et de générer la base de données.

Je ne sais pas comment il gère les modifications incrémentielles. Comme vous l'avez dit, lorsque vous écrivez du code, la syntaxe n'est pas valide 90% du temps, et tout remettre en ordre à chaque fois que vous étiez inactif ferait peser une énorme taxe sur votre processeur sans que vous en tiriez le moindre avantage, en particulier si vous modifiez un fichier d'en-tête inclus par un grand nombre de fichiers source.

Je soupçonne qu’il soit (a) ne répare que lorsque vous construisez réellement votre projet (ou éventuellement lorsque vous le fermez / ouvrez-le), ou (b) il effectue une sorte d’analyse locale où il n’analyse que le code Je viens de modifier de manière limitée, juste pour obtenir les noms des symboles pertinents. Comme C ++ possède une grammaire extrêmement complexe, il peut se comporter de manière étrange dans les coins sombres si vous utilisez une métaprogrammation de modèle complexe, etc.

Le lien suivant vous aidera à aller plus loin.

Mise en surbrillance de la syntaxe: Zone de texte colorée rapide pour la syntaxe en surbrillance

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow