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

StackOverflow https://stackoverflow.com/questions/1220099

Вопрос

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

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

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

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

Это было полезно?

Решение

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

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

  1. Получите выражение по наведению курсора.Это начинается с самого начала выражение доступа к члену курсор находится над концом идентификатора.Выражение доступа к члену обычно имеет вид aa.bb.cc, но также может содержать вызовы методов , как в aa.bb(3+2).cc.
  2. Получить контекст окружающий курсор.Это очень сложно, потому что оно не всегда следует тем же правилам, что и компилятор (длинная история), но здесь предположим, что это так.Обычно это означает получение кэшированной информации о методе / классе, внутри которого находится курсор.
  3. Допустим, контекстный объект реализует IDeclarationProvider, куда вы можете позвонить GetDeclarations() чтобы получить IEnumerable<IDeclaration> из всех элементов, видимых в области видимости.В моем случае этот список содержит локальные / параметры (если в методе), члены (поля и методы, статические только за исключением случаев, когда в методе экземпляра, и никаких закрытых членов базовых типов), глобальные (типы и константы для языка, над которым я работаю) и ключевые слова.В этом списке будет элемент с таким названием 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 "интерфейс"

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

  • Одним из спасительных факторов является то, что мой синтаксический анализатор быстро.Он может обработать полное обновление кэша исходного файла длиной 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 #)
  • Семантически корректный Поиск Всех Ссылок

Другие советы

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

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

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

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

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

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

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

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

Не связан с StackOverflow
scroll top