Как работает завершение кода?

Question

Многие редакторы и IDE имеют код завершения. Некоторые из них очень «умны», другие - нет. Я заинтересован в более интеллектуальном типе. Например, я видел IDE, которые предлагают функцию, только если она а) доступна в текущей области b) ее возвращаемое значение является действительным. (Например, после «5 + foo [tab]» он предлагает только функции, которые возвращают что-то, что может быть добавлено к целому числу или имени переменной правильного типа.) Я также видел, что они помещают наиболее часто используемую или самую длинную опцию вперед списка.

Я понимаю, что вам нужно разобрать код. Но обычно при редактировании текущего кода недопустимы синтаксические ошибки. Как вы анализируете что-то, когда оно неполное и содержит ошибки?

Существует также ограничение по времени. Завершение бесполезно, если для составления списка требуется несколько секунд. Иногда алгоритм завершения работает с тысячами классов.

Каковы хорошие алгоритмы и структуры данных для этого?

Answer 1

Движок IntelliSense в моем продукте языкового сервиса UnrealScript сложен, но я дам здесь как можно лучший обзор. Служба языка C # в VS2008 SP1 - моя цель производительности (по уважительной причине). Его еще нет, но он достаточно быстрый / точный, поэтому я могу смело предлагать предложения после ввода одного символа, не дожидаясь нажатия клавиши Ctrl + пробел или ввода пользователем . (точка). Чем больше информации [люди, работающие над языковыми службами], получают по этому вопросу, тем лучше для конечного пользователя я могу пользоваться их продуктами. Есть ряд продуктов, с которыми я имел неудачный опыт работы, которые не уделяли такого пристального внимания деталям, и в результате я боролся с IDE больше, чем кодировал.

В моем языковом сервисе это выглядит следующим образом:

1. Получить выражение у курсора. Это идет от начала выражения доступа к элементу до конца идентификатора, над которым находится курсор. Выражение доступа к члену обычно имеет вид aa.bb.cc, но также может содержать вызовы методов, как в aa.bb(3+2).cc.
2. Получите контекст , окружающий курсор. Это очень сложно, потому что он не всегда следует тем же правилам, что и компилятор (длинная история), но здесь предположим, что это так. Обычно это означает получение кэшированной информации о методе / классе, в котором находится курсор.
3. Скажем, объект контекста реализует IDeclarationProvider, где вы можете вызвать GetDeclarations(), чтобы получить IEnumerable<IDeclaration> всех элементов, видимых в области действия. В моем случае этот список содержит локальные / параметры (если в методе), члены (поля и методы, только статические, если только не в методе экземпляра, и нет закрытых членов базовых типов), глобальные переменные (типы и константы для языка I работаю) и ключевые слова. В этом списке будет элемент с именем aa. В качестве первого шага при оценке выражения в # 1 мы выбираем элемент из перечисления контекста с именем aa, что дает нам IDeclaration для следующего шага.
4. Затем я применяю оператор к IDeclaration, представляющему aa, чтобы получить еще один IEnumerable<IDeclaration>, содержащий "членов" (в некотором смысле) aa. Поскольку оператор . отличается от оператора ->, я вызываю declaration.GetMembers(".") и ожидаю, что объект IDeclaration правильно применяет указанный оператор.
5. Это продолжается до тех пор, пока я не нажму cc, где список объявлений может содержать или не содержать объект с именем cc. Я уверен, что вы знаете, если несколько элементов начинаются с cc, они также должны отображаться. Я решаю эту проблему, беря окончательное перечисление и пропуская его через мой документированный алгоритм , чтобы предоставить пользователю максимально полезную информацию.

Вот некоторые дополнительные примечания для бэкэнда IntelliSense:

• Я широко использую ленивые механизмы оценки LINQ при реализации GetMembers. Каждый объект в моем кэше может предоставить функтор, который оценивает его элементы, поэтому выполнение сложных действий с деревом почти тривиально.
• Вместо каждого объекта, содержащего List<IDeclaration> его членов, я сохраняю List<Name>, где Name - это структура, содержащая хэш специально отформатированной строки, описывающей член. Существует огромный кэш, который отображает имена на объекты. Таким образом, когда я повторно анализирую файл, я могу удалить все элементы, объявленные в файле, из кэша и снова заполнить его обновленными членами. Благодаря тому, как функторы настроены, все выражения сразу же оцениваются для новых элементов.

IntelliSense "внешний интерфейс"

Когда пользователь печатает, файл синтаксически неверен чаще, чем правильный. Поэтому я не хочу беспорядочно удалять разделы кэша, когда пользователь печатает. У меня есть большое количество правил для особых случаев, чтобы обрабатывать инкрементные обновления как можно быстрее. Инкрементный кеш хранится только локально по отношению к открытому файлу и помогает гарантировать, что пользователь не понимает, что его типизация заставляет внутренний кеш содержать неверную информацию о строках / столбцах для таких вещей, как каждый метод в файле.

• Один из факторов выкупа - мой синтаксический анализатор fast . Он может обрабатывать полное обновление кэша исходного файла размером 20000 строк за 150 мс, работая автономно в фоновом потоке с низким приоритетом. Всякий раз, когда этот синтаксический анализатор успешно завершает передачу открытого файла (синтаксически), текущее состояние файла перемещается в глобальный кэш.
• Если файл не является синтаксически правильным, я использую синтаксический анализатор ANTLR (извините за ссылку - большая часть информации находится в списке рассылки или собрана из чтения источника) для повторного анализа файла, ищущего:
  • Объявления переменных / полей.
  • Подпись для определений класса / структуры.
  • Подпись для определений методов.
• В локальном кэше определения классов / структур / методов начинаются с сигнатуры и заканчиваются, когда уровень вложенности фигурных скобок возвращается к четному. Методы также могут заканчиваться, если достигнуто другое объявление метода (без вложенных методов).
• В локальном кэше переменные / поля связаны с непосредственно предшествующим незамкнутым элементом. Смотрите пример краткого кода ниже, чтобы узнать, почему это важно.
• Кроме того, по мере ввода пользователем я сохраняю таблицу переназначения, отмечающую добавленные / удаленные диапазоны символов. Это используется для:
  • Убедившись, что я могу определить правильный контекст курсора, поскольку метод может / действительно перемещается в файле между полными разборками.
  • Убедитесь, что в разделе «Перейти к объявлению / определению / справочнику» правильно размещены элементы в открытых файлах.

Фрагмент кода для предыдущего раздела:

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

Я рассчитывал добавить список функций IntelliSense, которые я реализовал с помощью этого макета. Фотографии каждого находятся здесь.

• Автозаполнение
• Подсказки для инструментов
• Метод Советы
• Класс просмотра
• Окно определения кода
• Обозреватель вызовов (VS 2010 наконец добавляет это в C #)
• Семантически правильно Найти все ссылки

Answer 2

Я не могу точно сказать, какие алгоритмы используются какой-либо конкретной реализацией, но я могу сделать некоторые обоснованные предположения. trie - очень полезная структура данных для этой проблемы: IDE может поддерживать большой объем памяти в памяти всех символов в вашем проекте с некоторыми дополнительными метаданными на каждом узле.

Когда вы набираете символ, он идет по пути в дереве.Все потомки конкретного узла Trie являются возможными дополнениями.Затем в среде IDE просто необходимо отфильтровать их по тем, которые имеют смысл в текущем контексте, но нужно только вычислить столько, сколько можно отобразить во всплывающем окне завершения вкладок.

Более продвинутыйЗавершение табуляции требует более сложной процедуры.Например, Visual Assist X имеет функцию, с помощью которой вам нужно всего лишь вводить заглавные буквы символов CamelCase - например, если вы набираете SFN, он показывает символ SomeFunctionName в своем окне завершения табуляции.

Для вычисления дерева (или других структур данных) требуется анализ всего вашего кода, чтобы получить список всех символов в вашем проекте.Visual Studio хранит это в своей базе данных IntelliSense, файле .ncb, который хранится рядом с вашим проектом, так что ему не нужно повторно анализировать все при каждом закрытии и повторном открытии проекта.В первый раз, когда вы открываете большой проект (скажем, тот, который вы только что синхронизировали с управлением исходным кодом), VS займет время, чтобы проанализировать все и сгенерировать базу данных.

Я не знаю, как он обрабатывает постепенные изменения.Как вы уже сказали, когда вы пишете код, 90% времени он имеет неправильный синтаксис, и повторная обработка всего, когда вы бездействуете, приведет к огромным налогам на ваш ЦП с очень небольшой выгодой, особенно если вы изменяете заголовочный файл, включенныйбольшое количество исходных файлов.

Я подозреваю, что он либо (а) выполняет повторный анализ, только когда вы на самом деле строите свой проект (или, возможно, когда вы закрываете / открываете его), либо (б) выполняет какой-то локальныйсинтаксический анализ, где он анализирует только тот код, где вы только что отредактировали, ограниченным образом, просто чтобы получить имена соответствующих символов.Поскольку C ++ имеет такую ​​чрезвычайно сложную грамматику, она может вести себя странно в темных углах, если вы используете тяжелое шаблонное метапрограммирование и тому подобное.

Answer 3

Следующая ссылка поможет вам в дальнейшем ..

Подсветка синтаксиса: Быстроокрашенный текстовый блок для подсветки синтаксиса