Jak działa uzupełnianie kodu?

84

Wiele edytorów i IDE ma uzupełnianie kodu. Niektórzy z nich są bardzo „inteligentni”, inni nie. Interesuje mnie typ bardziej inteligentny. Na przykład widziałem IDE, które oferują funkcję tylko wtedy, gdy jest a) dostępna w obecnym zakresie b) jej wartość zwracana jest prawidłowa. (Na przykład po "5 + foo [tab]" oferuje tylko funkcje, które zwracają coś, co można dodać do liczb całkowitych lub nazw zmiennych odpowiedniego typu.) Widziałem również, że umieszczają one częściej używaną lub najdłuższą opcję przed listy.

Zdaję sobie sprawę, że musisz przeanalizować kod. Ale zwykle podczas edycji bieżącego kodu są nieprawidłowe, występują w nim błędy składniowe. Jak parsować coś, co jest niekompletne i zawiera błędy?

Istnieje również ograniczenie czasowe. Zakończenie jest bezużyteczne, jeśli utworzenie listy zajmuje kilka sekund. Czasami algorytm uzupełniania obsługuje tysiące klas.

Jakie są dobre algorytmy i struktury danych do tego celu?

stribika
źródło
1
Dobre pytanie. Możesz rzucić okiem na kod niektórych IDE open source, które to implementują, takich jak Code :: Blocks na codeblocks.org .
1
Oto artykuł dotyczący tworzenia uzupełniania kodu w języku C # Tworzenie uzupełniania kodu w języku C #
Pritam Zope

Odpowiedzi:

64

Mechanizm IntelliSense w moim produkcie usługowym w języku UnrealScript jest skomplikowany, ale przedstawię tutaj możliwie najlepszy przegląd. Usługa języka C # w VS2008 SP1 jest moim celem wydajnościowym (nie bez powodu). Jeszcze go tam nie ma, ale jest wystarczająco szybki / dokładny, że mogę bezpiecznie proponować sugestie po wpisaniu pojedynczego znaku, bez czekania na ctrl + spację lub wpisanie przez użytkownika .(kropki). Im więcej osób [pracujących nad usługami językowymi] zdobywają na ten temat, tym lepsze wrażenia uzyskuję, gdybym kiedykolwiek korzystał z ich produktów. Istnieje wiele produktów, z którymi miałem niefortunne doświadczenie podczas pracy, które nie zwracały tak dużej uwagi na szczegóły, w wyniku czego bardziej walczyłem z IDE niż kodowałem.

W mojej usłudze językowej wygląda to następująco:

  1. Pobierz wyrażenie w miejscu kursora. Spowoduje to przejście od początku wyrażenia dostępu do elementu członkowskiego do końca identyfikatora, nad którym znajduje się kursor. Wyrażenie dostępu do elementu członkowskiego ma zwykle postać aa.bb.cc, ale może również zawierać wywołania metod, takie jak aa.bb(3+2).cc.
  2. Uzyskaj kontekst otaczający kursor. Jest to bardzo trudne, ponieważ nie zawsze przestrzega tych samych zasad, co kompilator (długa historia), ale tutaj załóżmy, że tak. Generalnie oznacza to pobranie z pamięci podręcznej informacji o metodzie / klasie, w której znajduje się kursor.
  3. Powiedz, że implementuje obiekt kontekstu IDeclarationProvider, w którym możesz wywołać, GetDeclarations()aby uzyskać IEnumerable<IDeclaration>wszystkie elementy widoczne w zakresie. W moim przypadku ta lista zawiera lokalne / parametry (jeśli są w metodzie), składowe (pola i metody, tylko statyczne, chyba że w metodzie instancji, i żadnych prywatnych członków typów bazowych), globalne (typy i stałe dla języka I nad którym pracuję) i słowa kluczowe. Na tej liście będzie pozycja o nazwie aa. Jako pierwszy krok w ocenie wyrażenia w # 1, wybieramy element z wyliczenia kontekstu z nazwą aa, dając nam IDeclarationdo następnego kroku.
  4. Następnie stosuję operator do IDeclarationreprezentacji, aaaby uzyskać inny IEnumerable<IDeclaration>zawierający „członków” (w pewnym sensie) aa. Ponieważ .operator różni się od ->operatora, dzwonię declaration.GetMembers(".")i oczekuję, że IDeclarationobiekt poprawnie zastosuje wymieniony operator.
  5. Trwa to dopóki nie trafię cc, gdzie lista deklaracji może zawierać obiekt z nazwą lub niecc . Jestem pewien, że wiesz, że jeśli wiele elementów zaczyna się od cc, powinny również się pojawić. Rozwiązuję to, biorąc ostateczne wyliczenie i przepuszczając je przez mój udokumentowany algorytm, aby zapewnić użytkownikowi możliwie najbardziej pomocne informacje.

Oto kilka dodatkowych uwag dotyczących zaplecza IntelliSense:

  • W implementacji szeroko korzystam z leniwych mechanizmów oceny LINQ GetMembers. Każdy obiekt w mojej pamięci podręcznej jest w stanie dostarczyć funktor, który ocenia swoje elementy, więc wykonywanie skomplikowanych działań na drzewie jest prawie trywialne.
  • Zamiast każdego obiektu przechowującego a List<IDeclaration>ze swoich składowych, zachowuję a List<Name>, gdzie Namejest strukturą zawierającą hash specjalnie sformatowanego ciągu opisującego członka. Istnieje ogromna pamięć podręczna, która odwzorowuje nazwy na obiekty. W ten sposób, kiedy ponownie analizuję plik, mogę usunąć wszystkie elementy zadeklarowane w pliku z pamięci podręcznej i ponownie wypełnić go zaktualizowanymi składnikami. Ze względu na sposób konfiguracji funktorów wszystkie wyrażenia są natychmiast przeliczane na nowe pozycje.

„Nakładka” IntelliSense

W miarę wpisywania przez użytkownika plik jest częściej składniowo niepoprawny niż poprawny. W związku z tym nie chcę przypadkowo usuwać sekcji pamięci podręcznej, gdy użytkownik pisze. Mam wiele reguł dotyczących przypadków specjalnych, aby jak najszybciej obsługiwać aktualizacje przyrostowe. Przyrostowa pamięć podręczna jest przechowywana lokalnie tylko dla otwartego pliku i pomaga upewnić się, że użytkownik nie zdaje sobie sprawy, że jego wpis powoduje, że pamięć podręczna zaplecza przechowuje nieprawidłowe informacje o wierszach / kolumnach dla rzeczy takich jak każda metoda w pliku.

  • Jednym z czynników odkupiających jest to, że mój parser jest szybki . Może obsługiwać pełną aktualizację pamięci podręcznej pliku źródłowego o długości 20000 linii w czasie 150 ms, działając samodzielnie w wątku o niskim priorytecie w tle. Za każdym razem, gdy ten parser pomyślnie zakończy przejście otwartego pliku (składniowo), bieżący stan pliku jest przenoszony do globalnej pamięci podręcznej.
  • Jeśli plik nie jest poprawny składniowo, używam parsera filtru ANTLR (przepraszam za link - większość informacji znajduje się na liście mailingowej lub zebrano z czytania źródła), aby ponownie przeanalizować plik w poszukiwaniu:
    • Deklaracje zmiennych / pól.
    • Sygnatura definicji klas / struktur.
    • Sygnatura definicji metod.
  • W lokalnej pamięci podręcznej definicje klas / struktur / metod zaczynają się od podpisu i kończą, gdy poziom zagnieżdżenia nawiasów klamrowych powraca do parzystości. Metody mogą również kończyć się, jeśli zostanie osiągnięta inna deklaracja metody (brak metod zagnieżdżania).
  • W lokalnej pamięci podręcznej zmienne / pola są połączone z bezpośrednio poprzedzającym niezamkniętym elementem. Zobacz krótki fragment kodu poniżej, aby zobaczyć, dlaczego jest to ważne.
  • Ponadto, gdy użytkownik pisze, utrzymuję tabelę przemapowań, w której zaznaczam dodane / usunięte zakresy znaków. Służy do:
    • Upewniam się, że mogę zidentyfikować prawidłowy kontekst kursora, ponieważ metoda może / nie porusza się w pliku między pełnymi analizami.
    • Upewnij się, że Przejdź do deklaracji / definicji / odniesienia prawidłowo lokalizuje elementy w otwartych plikach.

Fragment kodu z poprzedniej sekcji:

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

Pomyślałem, że dodam listę funkcji IntelliSense, które zaimplementowałem w tym układzie. Zdjęcia każdego z nich znajdują się tutaj.

  • Autouzupełnienie
  • Wskazówki dotyczące narzędzi
  • Wskazówki dotyczące metod
  • Widok klasy
  • Okno definicji kodu
  • Call Browser (VS 2010 w końcu dodaje to do C #)
  • Semantycznie poprawne Znajdź wszystkie odwołania
Sam Harwell
źródło
To świetnie, dziękuję. Nigdy nie myślałem o rozróżnianiu wielkości liter podczas sortowania. Szczególnie podoba mi się to, że można sobie poradzić z niedopasowanymi szelkami.
stribika
15

Nie potrafię dokładnie powiedzieć, jakie algorytmy są używane w konkretnej implementacji, ale mogę zgadywać. Trie jest bardzo przydatnym struktura danych dla tego problemu: IDE może utrzymać dużą Trie w pamięci wszystkich symboli w projekcie, z pewnym dodatkowym metadanych w każdym węźle.

Kiedy wpisujesz znak, idzie on ścieżką w trie. Wszystkie elementy potomne określonego węzła trie są możliwymi uzupełnieniami. Następnie IDE musi tylko odfiltrować te, które mają sens w bieżącym kontekście, ale musi obliczyć tylko tyle, ile można wyświetlić w wyskakującym okienku uzupełniania tabulatorów.

Bardziej zaawansowane wypełnianie kart wymaga bardziej skomplikowanej próby. Na przykład Visual Assist X ma funkcję, dzięki której wystarczy wpisać wielkie litery symboli CamelCase - np. Jeśli wpiszesz SFN, pokaże ci symbol SomeFunctionNamew oknie uzupełniania tabulatora.

Obliczanie trie (lub innych struktur danych) wymaga przeanalizowania całego kodu w celu uzyskania listy wszystkich symboli w projekcie. Program Visual Studio przechowuje to w swojej bazie danych IntelliSense, .ncbpliku przechowywanym wraz z projektem, dzięki czemu nie musi ponownie analizować wszystkiego za każdym razem, gdy zamykasz i ponownie otwierasz projekt. Gdy pierwszy raz otworzysz duży projekt (powiedzmy, który właśnie zsynchronizowałeś z formantem kontroli źródła), VS zajmie trochę czasu, aby przeanalizować wszystko i wygenerować bazę danych.

Nie wiem, jak radzi sobie ze zmianami przyrostowymi. Jak powiedziałeś, kiedy piszesz kod, jego składnia jest nieprawidłowa w 90% przypadków, a ponowne parsowanie wszystkiego za każdym razem, gdy będziesz bezczynny, obciąży Twój procesor bardzo niewielkim podatkiem, szczególnie jeśli modyfikujesz plik nagłówkowy dołączony duża liczba plików źródłowych.

Podejrzewam, że albo (a) dokonuje ponownej analizy tylko wtedy, gdy faktycznie budujesz swój projekt (lub prawdopodobnie kiedy go zamykasz / otwierasz), albo (b) wykonuje jakąś lokalną analizę, w której analizuje kod tylko w miejscu, w którym zredagowane w pewien ograniczony sposób, aby uzyskać nazwy odpowiednich symboli. Ponieważ C ++ ma tak wyjątkowo skomplikowaną gramatykę, może zachowywać się dziwnie w ciemnych zakamarkach, jeśli używasz ciężkiego metaprogramowania szablonów i tym podobnych.

Adam Rosenfield
źródło
Próba to naprawdę dobry pomysł. Jeśli chodzi o zmiany przyrostowe, można najpierw spróbować ponownie przeanalizować plik, jeśli to nie zadziała, zignoruj ​​bieżący wiersz, a jeśli to nie zadziała, zignoruj ​​otaczający blok {...}. Jeśli wszystko inne zawiedzie, użyj ostatniej bazy danych.
stribika