algorithm - ¿Cómo funciona la finalización del código?

autocomplete code-completion

Question

Muchos editores e IDE tienen código de finalización. Algunos de ellos son muy "inteligentes", otros no lo son en realidad. Estoy interesado en el tipo más inteligente. Por ejemplo, he visto IDE que solo ofrecen una función si está a) disponible en el alcance actual b) su valor de retorno es válido. (Por ejemplo, después de "5 + foo [tab]" solo ofrece funciones que devuelven algo que se puede agregar a un entero o nombres de variables del tipo correcto.) También he visto que colocan la opción más utilizada o más larga por delante de la lista.

Me doy cuenta de que necesitas analizar el código. Pero generalmente, al editar el código actual no es válido, hay errores de sintaxis en él. ¿Cómo se analiza algo cuando está incompleto y contiene errores?

También hay una restricción de tiempo. La finalización es inútil si lleva unos segundos crear una lista. A veces, el algoritmo de finalización trata con miles de clases.

¿Cuáles son los buenos algoritmos y estructuras de datos para esto?

Answer 1

El siguiente enlace te ayudará a avanzar ...

Resaltado de sintaxis: TextBox de color rápido para realzar la sintaxis

Answer 2

No puedo decir exactamente qué algoritmos utiliza una implementación en particular, pero puedo hacer algunas conjeturas. Un trie es una estructura de datos muy útil para este problema: el IDE puede mantener un trie grande en la memoria de todos los símbolos en su proyecto, con algunos metadatos adicionales en cada nodo.

Cuando escribe un personaje, camina por un camino en el trie. Todos los descendientes de un nodo trie particular son posibles terminaciones. El IDE solo necesita filtrar esos por los que tienen sentido en el contexto actual, pero solo necesita calcular todos los que se pueden mostrar en la ventana emergente de finalización de pestañas.

La finalización de pestañas más avanzada requiere un trie más complicado. Por ejemplo, Visual Assist X tiene una función en la que solo necesita escribir las letras mayúsculas de los símbolos de CamelCase; por ejemplo, si escribe SFN, le muestra el símbolo SomeFunctionName en su ventana de finalización de pestañas.

La computación de trie (u otras estructuras de datos) requiere analizar todo su código para obtener una lista de todos los símbolos en su proyecto. Visual Studio almacena esto en su base de datos IntelliSense, un archivo .ncb almacenado junto a su proyecto, para que no tenga que volver a analizar todo cada vez que cierre y vuelva a abrir su proyecto. La primera vez que abre un proyecto grande (por ejemplo, uno que acaba de sincronizar desde el control de fuente), VS se tomará el tiempo para analizar todo y generar la base de datos.

No sé cómo maneja los cambios incrementales. Como dijiste, cuando escribes código, la sintaxis es inválida el 90% del tiempo, y repasando todo cuando estás inactivo supondría un enorme impuesto a tu CPU para muy poco beneficio, especialmente si estás modificando un archivo de cabecera incluido por una gran cantidad de archivos fuente

Sospecho que (a) solo reparses cuando realmente construyes tu proyecto (o posiblemente cuando lo cierras / abres), o (b) hace algún tipo de análisis local donde solo analiza el código donde acabas de escribir editado de alguna manera limitada, solo para obtener los nombres de los símbolos relevantes. Como C ++ tiene una gramática increíblemente complicada, puede comportarse de forma extraña en las esquinas oscuras si está utilizando una metaprogramación de plantillas pesadas y cosas similares.

Answer 3

El motor de IntelliSense en mi producto de servicio de lenguaje UnrealScript es complicado, pero daré aquí la mejor visión general que pueda. El servicio de lenguaje C # en VS2008 SP1 es mi objetivo de rendimiento (por una buena razón). Todavía no está allí, pero es lo suficientemente rápido y preciso como para poder ofrecer sugerencias de forma segura después de que se escribe un solo carácter, sin esperar ctrl + espacio o que el usuario escriba a . (punto). Cuanta más información obtengan las personas [que trabajan en servicios de idiomas] sobre este tema, mejor experiencia de usuario final obtendré si alguna vez uso sus productos. Hay una cantidad de productos con los que he tenido la desafortunada experiencia de trabajar y que no prestaron tanta atención a los detalles, y como resultado, estaba peleando con el IDE más de lo que estaba codificando.

En mi servicio de idiomas, se presenta de la siguiente manera:

1. Obtén la expresión en el cursor. Esto se inicia desde el comienzo de la expresión de acceso del miembro hasta el final del identificador donde se encuentra el cursor. La expresión de acceso miembro generalmente tiene el formato aa.bb.cc , pero también puede contener llamadas a métodos como en aa.bb(3+2).cc .
2. Obtenga el contexto que rodea al cursor. Esto es muy complicado, porque no siempre sigue las mismas reglas que el compilador (historia larga), pero por aquí, supongo que sí. En general, esto significa obtener la información en caché sobre el método / clase en el que se encuentra el cursor.
3. Supongamos que el objeto de contexto implementa IDeclarationProvider , donde puede llamar a GetDeclarations() para obtener un IEnumerable<IDeclaration> de todos los elementos visibles en el alcance. En mi caso, esta lista contiene los locales / parámetros (si hay un método), miembros (campos y métodos, estáticos solo a menos que sea en un método de instancia, y no miembros privados de tipos base), globales (tipos y constantes para el lenguaje I estoy trabajando en) y palabras clave. En esta lista, habrá un artículo con el nombre aa . Como primer paso para evaluar la expresión en el n. ° 1, seleccionamos el ítem de la enumeración de contexto con el nombre aa , dándonos una IDeclaration para el siguiente paso.
4. A continuación, aplico el operador a la IDeclaration representa aa para obtener otra IEnumerable<IDeclaration> contiene los "miembros" (en cierto sentido) de aa . Desde el . operador es diferente del operador -> , llamo declaration.GetMembers(".") y espero que el objeto IDeclaration aplique correctamente el operador indicado.
5. Esto continúa hasta que toco cc , donde la lista de declaraciones puede contener o no un objeto con el nombre cc . Como estoy seguro de que sabe, si varios elementos comienzan con cc , también deberían aparecer. Resuelvo esto tomando la enumeración final y pasando a través de mi algoritmo documentado para proporcionar al usuario la información más útil posible.

Aquí hay algunas notas adicionales para el backend de IntelliSense:

• Hago un uso extensivo de los mecanismos de evaluación perezosa de LINQ al implementar GetMembers . Cada objeto en mi caché puede proporcionar un functor que evalúa a sus miembros, por lo que realizar acciones complicadas con el árbol es casi trivial.
• En lugar de que cada objeto List<IDeclaration> una List<IDeclaration> de sus miembros, guardo una List<Name> , donde Name es una estructura que contiene el hash de una cadena especialmente formateada que describe al miembro. Hay un enorme caché que asigna nombres a los objetos. De esta forma, cuando vuelva a analizar un archivo, puedo eliminar todos los elementos declarados en el archivo del caché y volver a llenarlo con los miembros actualizados. Debido a la forma en que se configuran los funtores, todas las expresiones evalúan inmediatamente los nuevos elementos.

IntelliSense "frontend"

A medida que el usuario escribe, el archivo es sintácticamente incorrecto con más frecuencia de lo que es correcto. Como tal, no quiero eliminar secciones de la memoria caché al azar cuando el usuario escribe. Tengo una gran cantidad de reglas de casos especiales para manejar las actualizaciones incrementales lo más rápido posible. La memoria caché incremental solo se mantiene local en un archivo abierto y ayuda a garantizar que el usuario no se dé cuenta de que su escritura está causando que la memoria caché de back-end contenga información incorrecta de línea / columna para cosas como cada método en el archivo.

• Un factor redentor es que mi analizador es rápido . Puede manejar una actualización de caché completa de un archivo de origen de línea de 20000 en 150 ms mientras funciona de manera autónoma en una cadena de fondo de baja prioridad. Cada vez que este analizador completa una pasada en un archivo abierto con éxito (sintácticamente), el estado actual del archivo se mueve a la memoria caché global.
• Si el archivo no es sintácticamente correcto, utilizo un analizador de filtro ANTLR (lo siento sobre el enlace; la mayoría de la información está en la lista de correo o se recopiló al leer el código fuente) para volver a analizar el archivo que busca:
  • Declaraciones de variables / campos.
  • La firma para las definiciones de clase / estructura.
  • La firma para definiciones de métodos.
• En la memoria caché local, las definiciones de clase / estructura / método comienzan en la firma y finalizan cuando el nivel de anidación de llaves vuelve a ser par. Los métodos también pueden finalizar si se alcanza otra declaración de método (sin métodos de anidamiento).
• En la memoria caché local, las variables / campos están vinculados al elemento no cerrado inmediatamente anterior. Consulte el breve fragmento de código a continuación para ver un ejemplo de por qué esto es importante.
• Además, a medida que el usuario escribe, conservo una tabla de reasignación que marca los rangos de caracteres agregados / eliminados. Esto se usa para:
  • Asegurándome de que puedo identificar el contexto correcto del cursor, ya que un método puede / se mueve en el archivo entre análisis completos.
  • Asegurándose de que Ir a Declaración / Definición / Referencia encuentra los elementos correctamente en archivos abiertos.

Fragmento de código para la sección anterior:

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

Pensé que agregaría una lista de las funciones de IntelliSense que implementé con este diseño. Fotos de cada uno se encuentran aquí.

• Autocompletar
• Consejos de herramientas
• Consejos de método
• Vista de clase
• Ventana de definición de código
• Explorador de llamadas (VS 2010 finalmente lo agrega a C #)
• Semánticamente correcto Buscar todas las referencias