Texteditor - das ist nicht Ihre höchste Mathematik, dann müssen Sie denken

    Moderne Texteditoren können nicht nur bibikat und nicht aus dem Programm heraus geben. Es stellt sich heraus, dass ein sehr komplexer Stoffwechsel in ihnen siedet. Möchten Sie herausfinden, mit welchen Tricks die Koordinaten schnell neu berechnet werden, wie Stile, Falten und Soft-Wraps an den Text angehängt werden und wie alles aktualisiert wird, welche funktionalen Datenstrukturen und Prioritätswarteschlangen Sie verwenden und wie Sie den Benutzer betrügen - willkommen unter der Katze!



    Der Artikel basiert auf dem Bericht von Alexey Kudryavtsev mit Joker 2017. Alexey schreibt bereits seit 10 Jahren Intellij IDEA in JetBrains. Unter dem Schnitt finden Sie das Video und den Text des Berichts.



    Datenstrukturen in Texteditoren


    Um zu verstehen, wie der Editor arbeitet, schreiben wir ihn.



    Alles, unser elementarer Editor, ist fertig.

    Innerhalb des Editors kann der Text am einfachsten in einem Array von Zeichen oder (in Bezug auf die Speicherorganisation) in der StringBuffer-Java-Klasse gespeichert werden. Um ein beliebiges Zeichen durch Offset zu erhalten, rufen wir die Methode StringBuffer.charAt (i) auf. Rufen Sie zum Einfügen des auf der Tastatur eingegebenen Zeichens die Methode StringBuffer.insert () auf, die das Zeichen irgendwo in der Mitte einfügt.

    Was trotz der Einfachheit und Idiotie dieses Editors am interessantesten ist, ist die beste Präsentation, die Sie sich vorstellen können. Es ist einfach und fast immer schnell.

    Leider gibt es bei diesem Editor ein Skalenproblem. Stellen Sie sich vor, wir hätten eine Menge Text darin eingetippt und werden in der Mitte einen weiteren Buchstaben einfügen. Folgendes wird passieren. Wir müssen dringend etwas Platz für diesen Buchstaben schaffen, indem wir alle anderen Buchstaben um ein Zeichen vorrücken. Um dies zu tun, verschieben wir diesen Buchstaben um eine Position, dann die nächste usw. bis zum Ende des Textes.

    So wird es im Speicher aussehen: Das



    Verschieben all dieser zahlreichen Megabytes ist nicht sehr gut: Es ist langsam. Für einen modernen Computer ist dies natürlich eine triviale Angelegenheit - bewegen Sie einige miserable Megabytes hin und her. Bei einer sehr aktiven Textänderung kann sich dies jedoch bemerkbar machen.

    Um dieses Problem des Einfügens eines Symbols in der Mitte zu lösen, wurde vor langer Zeit ein Bypass-Manöver namens "Gap Buffer" erfunden.

    Lückenpuffer


    Lücke ist eine Lücke. Puffer ist, wie Sie sich vorstellen können, ein Puffer. Die "Gap Buffer" -Datenstruktur ist ein leerer Puffer, den wir für alle Fälle in der Mitte unseres Textes speichern. Wenn wir etwas drucken mussten, verwenden wir diesen kleinen Textpuffer für die schnelle Eingabe.



    Die Datenstruktur hat sich ein wenig geändert - das Array blieb an Ort und Stelle, aber es wurden zwei Zeiger angezeigt: am Anfang des Puffers und am Ende. Um ein Zeichen mit einem bestimmten Versatz aus dem Editor herauszunehmen, müssen wir wissen, ob es sich vor oder nach diesem Puffer befindet, und den Versatz ein wenig korrigieren. Um ein Symbol einzufügen, müssen wir zuerst den Lückenpuffer an diese Stelle schieben und mit diesen Symbolen füllen. Und wenn wir über unseren Puffer hinausgehen, wird es natürlich irgendwie neu erstellt. So sieht es auf dem Bild aus.



    Wie Sie sehen, bewegen wir uns zunächst eine lange Zeit in einem kleinen Lückenpuffer (ein blaues Rechteck) zur Bearbeitungsseite (einfach Zeichen abwechselnd links und rechts auswechseln). Dann benutzen wir diesen Puffer und geben die Zeichen dort ein.

    Wie Sie sehen, gibt es keine Bewegung von Megabytes an Zeichen, das Einfügen erfolgt sehr schnell und zu einer Zeitkonstante, und alles scheint glücklich zu sein. Alles scheint in Ordnung zu sein, aber wenn wir einen sehr langsamen Prozessor haben, werden der Lückenpuffer und der Text ziemlich merklich hin und her bewegt. Dies machte sich besonders in Zeiten sehr kleiner Megahertz bemerkbar.

    Stück Tisch


    Zu dieser Zeit schrieb ein Unternehmen namens Microsoft ein Word-Prozessor-Word. Sie beschlossen, eine andere Idee zu verwenden, um die Bearbeitung unter dem Namen "Piece Table" zu beschleunigen, das heißt "Piece Table". Sie schlugen vor, den Text des Editors in demselben einfachsten Array von Zeichen zu speichern, das sich nicht ändern wird, und alle Änderungen in eine separate Tabelle der am meisten bearbeiteten Teile einzufügen.



    Wenn wir also ein Symbol anhand eines Versatzes suchen müssen, müssen wir dieses Stück, das wir bearbeitet haben, finden und dieses Symbol daraus extrahieren. Wenn es nicht vorhanden ist, gehen Sie zum ursprünglichen Text. Das Einfügen eines Symbols wird einfacher, wir müssen dieses neue Element nur erstellen und der Tabelle hinzufügen. So sieht es auf dem Bild aus:



    Hier wollten wir das Leerzeichen am Versatz 5 entfernen. Dazu fügen wir der Stückliste zwei neue Teile hinzu: Einer zeigt auf das erste Fragment („Bummer“) und das zweite zeigt nach der Bearbeitung auf das Fragment („Schafe“). Es stellt sich heraus, dass der Raum von ihnen verschwindet, diese beiden Teile zusammengeklebt werden und wir erhalten einen neuen Text ohne Leerzeichen: „Oblomovtsy“. Dann fügen wir am Ende einen neuen Text hinzu („diejenigen, die unter Oblomovismus leiden“). Verwenden Sie den zusätzlichen Puffer und fügen Sie ein neues Stück zu der Tabelle der Teile (Stücktabelle) hinzu, die auf diesen neuesten hinzugefügten Text verweist.

    Wie Sie sehen, gibt es keine Hin- und Herbewegung, der gesamte Text bleibt erhalten. Das Schlechte ist, dass es schwieriger wird, zum Charakter zu gelangen, da das Sortieren all dieser Teile ziemlich schwierig ist.

    Zusammenzufassen.

    Was ist gut inStück tisch :

    • Schnell einfügen;
    • Einfach rückgängig machen;
    • Nur anhängen

    Was ist schlimm:

    • Fürchterlich schwer zugänglich.
    • Sehr schwer zu implementieren.

    Mal sehen, wer im Allgemeinen verwendet, was wir haben.

    NetBeans, Eclipse und Emacs verwenden Gap Buffer - großartig! Vi kümmert sich nicht und verwendet nur die Liste der Zeilen. Word verwendet den Piece Table (kürzlich haben sie ihre alten Zauberer ausgelegt und konnten dort sogar etwas verstehen).

    Mit Atom interessanter. Bis vor kurzem störten sie sich nicht und verwendeten eine JavaScript-Zeilenliste. Und dann haben wir uns entschieden, alles in C ++ umzuschreiben und haben mit einer ziemlich komplexen Struktur gespielt, die anscheinend der Piece Table ähnelt. Diese Stücke werden jedoch nicht in der Liste gespeichert, sondern in einem Baum und im sogenannten Splay-Baum. Dies ist ein Baum, der sich beim Einfügen selbst reguliert, so dass neuere Einfügungen schneller sind. Das sind sehr komplizierte Sachen.

    Was verwendet Intellij IDEA?
    Nein, kein Lückenpuffer. Nein, du liegst auch nicht ein Stück Tisch.
    Ja, das ist richtig, dein eigenes Fahrrad.

    Tatsache ist, dass die Anforderungen der IDE zum Speichern von Text etwas anders sind als in einem normalen Texteditor. Die IDE benötigt Unterstützung für verschiedene knifflige Dinge wie Parallelität, dh parallelen Zugriff auf Text aus dem Editor. Zum Beispiel könnten so viele verschiedene Fragen gelesen und ausgeführt werden. (Inspection ist ein kleines Stück Code, das ein Programm auf die eine oder andere Weise analysiert - beispielsweise nach Orten suchen, an denen eine NullPointerException ausgelöst wird). Die IDE benötigt auch Unterstützung für bearbeitbare Textversionen. Während Sie mit einem Dokument arbeiten, sind mehrere Versionen gleichzeitig im Arbeitsspeicher, sodass diese langen Prozesse die alte Version weiterhin analysieren.

    Probleme


    Wettbewerbsfähigkeit / Versionierung


    Um die Parallelität aufrechtzuerhalten, werden Textoperationen normalerweise in "synchronisiert" oder in Lese- / Schreibsperren eingeschlossen. Leider ist das nicht sehr gut skaliert. Der andere Ansatz ist unveränderlicher Text, dh unveränderlicher Textspeicher.



    So sieht ein Editor mit einem unveränderlichen Dokument als unterstützende Datenstruktur aus.

    Wie ist die Datenstruktur selbst?

    Anstelle eines Arrays von Zeichen haben wir ein neues ImmutableText-Objekt, das Text in Form einer Baumstruktur speichert, wobei Blätter in kleinen Teilzeichenketten gespeichert werden. Bei einer Art Verschiebung versucht er, das unterste Blatt in diesem Baum zu erreichen, und er muss bereits das Symbol fragen, an das wir gerichtet sind. Beim Einfügen von Text wird ein neuer Baum erstellt und an der alten Stelle gespeichert.



    Zum Beispiel haben wir ein Dokument mit dem Text "Kalorienfrei". Es ist als Baum mit zwei Hülsenblättern "Dämon" und "Hochkalorien" implementiert. Wenn wir die "hübsche" Zeile in der Mitte einfügen möchten, wird eine neue Version unseres Dokuments erstellt. Und genau genommen wird eine neue Wurzel angelegt, an der bereits drei Blätter angebracht sind: "Bes", "genug" und "kalorienreich". Zwei dieser neuen Blätter können sich auf die erste Version unseres Dokuments beziehen. Und für das Blatt, in das wir die Zeile "hübsch" eingefügt haben, wird ein neuer Scheitelpunkt zugewiesen. Hier sind sowohl die erste als auch die zweite Version gleichzeitig verfügbar und alle sind unveränderlich und unveränderlich. Alles sieht gut aus.

    Wer nutzt welche kniffligen Strukturen?



    In GNOME zum Beispiel verwendet ein Standard-Widget eine Struktur namens Seil. Xi-Editor ist ein brillanter neuer Editor vonRafa Leviena - verwendet persistentes Seil. Und Intellij IDEA verwendet den gleichen unveränderlichen Baum. Hinter all diesen Namen verbirgt sich tatsächlich mehr oder weniger dieselbe Datenstruktur mit einer Baumansicht des Textes. Abgesehen davon, dass GtkTextBuffer ein veränderbares Seil verwendet, d. H. Einen Baum mit variablen Scheitelpunkten, und Intellij IDEA und Xi-Editor - Immutable.

    Das nächste, was bei der Entwicklung eines Symbol-Repositorys in modernen IDEs zu beachten ist, wird als "Multi-Kalender" bezeichnet. Mit dieser Funktion können Sie an mehreren Stellen gleichzeitig mit mehreren Wagen drucken.



    Wir können etwas drucken und gleichzeitig an mehreren Stellen des Dokuments einfügen, was wir dort eingegeben haben. Wenn wir uns ansehen, wie unsere von uns überprüften Datenstrukturen auf Multicaret reagieren, werden wir etwas Interessantes sehen.



    Wenn wir ein Zeichen in unseren allerersten primitiven Editor einfügen, dauert es natürlich linear, eine Reihe von Zeichen hin und her zu bewegen. Dies wird als O (N) geschrieben. Für den auf Gap Buffer basierenden Editor wiederum dauert es bereits konstante Zeit, für die er erfunden wurde.

    Für einen unveränderlichen Baum hängt die Zeit logarithmisch von der Größe ab, da Sie zuerst vom oberen Rand des Baums bis zu seinem Blatt gehen müssen. Dies ist der Logarithmus. Anschließend müssen Sie für alle Scheitelpunkte neue Scheitelpunkte für den neuen Baum erstellen. Dies ist wiederum der Logarithmus. Piece Table erfordert auch eine Konstante.
    Aber alles ändert sich ein wenig, wenn wir versuchen, die Zeit des Einfügens eines Symbols in den Editor mit Mehrfachwagen zu messen, dh Einfügungen gleichzeitig an mehreren Stellen. Auf den ersten Blick scheint die Zeit proportional um das C-fache zuzunehmen - die Anzahl der Stellen, an denen das Symbol eingefügt wird. Mit Ausnahme von Gap Buffer geschieht alles. In diesem Fall wird die Zeit anstelle der C-Zeiten unerwartet um eine nicht nachvollziehbare C * L-Zeit erhöht, wobei L die durchschnittliche Entfernung zwischen den Wagen ist. Warum passiert das?

    Stellen Sie sich vor, wir müssen die Zeile ", bis" an zwei Stellen in unserem Dokument einfügen.



    Dies geschieht zu dieser Zeit im Editor.

    • Erstellen Sie einen Lückenpuffereditor (ein blaues Rechteck in der Abbildung).
    • Wir bekommen zwei Wagen (schwarze dicke senkrechte Linien);
    • Wir versuchen zu drucken;
    • Fügen Sie ein Komma in unseren Lückenpuffer ein.
    • Muss es jetzt anstelle des zweiten Wagens einsetzen;
    • Dazu müssen wir unseren Lückenpuffer in die Position des nächsten Wagens drücken.
    • Geben Sie an zweiter Stelle das Komma ein.
    • Jetzt müssen Sie das nächste Zeichen an der Position des ersten Wagens einfügen.
    • Und wir müssen unseren Lückenpuffer zurückschieben;
    • Geben Sie den Buchstaben "n" ein.
    • Und wir bewegen unseren langweiligen Puffer an die Stelle des zweiten Wagens;
    • Wir fügen dort unser "n" ein;
    • Bewegen Sie den Puffer zurück, um das nächste Zeichen einzufügen.

    Fühlen, was alles geht?

    Ja, es stellt sich heraus, dass durch diese zahlreichen Pufferbewegungen unsere Gesamtzeit zunimmt. Ehrlich gesagt ist es nicht so schrecklich, wie es zunimmt - es ist kein Problem, elende Megabytes für einen modernen Computer hin und her zu bewegen, aber es ist immer noch interessant, dass diese Datenstruktur bei Multicarets völlig anders funktioniert.

    Zu viele Zeilen? LineSet!


    Welche anderen Probleme gibt es in einem regulären Texteditor? Das schwierigste Problem ist das Scrollen, dh der Editor wird neu gezeichnet, während der Wagen in die nächste Zeile verschoben wird.



    Wenn der Editor einen Bildlauf durchführt, müssen wir verstehen, von welcher Zeile aus, von welchem ​​Zeichen aus wir den Text in unserem kleinen Fenster zeichnen müssen. Um dies zu erreichen, müssen wir schnell verstehen, welche Linie welchem ​​Versatz entspricht.



    Es gibt eine offensichtliche Schnittstelle dafür, wenn wir den Versatz im Text anhand der Zeilennummer verstehen müssen. Umgekehrt ist durch den Versatz im Text zu verstehen, in welcher Zeile es sich befindet. Wie geht das schnell?

    Zum Beispiel:

    Ordnen Sie diese Linien in einem Baum an und markieren Sie jeden Scheitelpunkt dieses Baums mit dem Versatz des Zeilenanfangs und dem Versatz des Zeilenendes. Und um dann zu verstehen, in welcher Zeile es sich befindet, müssen Sie nur eine logarithmische Suche in diesem Baum ausführen und finden.



    Ein anderer Weg ist noch einfacher.

    Schreiben Sie in die Tabelle den Versatz des Zeilenanfangs und des Zeilenendes. Um Anfang und Ende um die Zeilennummer zu ermitteln, müssen Sie sich auf den Index beziehen.



    Interessanterweise werden in der realen Welt beide verwendet.



    Zum Beispiel verwendet Eclipse eine Holzstruktur, die, wie Sie sehen, in logarithmischer Zeit sowohl zum Lesen als auch zum Aktualisieren arbeitet. IDEA verwendet eine Tabellenstruktur, für die das Lesen eine schnelle Konstante ist. Es handelt sich um einen Indexaufruf in der Tabelle. Die Neuerstellung ist jedoch relativ langsam, da Sie die gesamte Tabelle neu erstellen müssen, wenn Sie die Länge einer Zeile ändern.

    Noch zu viele Zeilen? Falten


    Was ist sonst noch schlimm, worauf stolpert man in Texteditoren? Zum Beispiel falten. Dies sind Textstücke, die "reduziert" werden können und stattdessen etwas anderes zeigen.



    Diese Ellipsen auf einem grünen Hintergrund im Bild verbergen viele Zeichen hinter uns, aber wenn wir sie nicht interessant betrachten (wie es bei den meist langweiligen Java-Dokumenten oder Importlisten der Fall ist), blenden wir sie aus und falten sie darin Punkte.

    Und auch hier müssen Sie verstehen, wann die Region endet und wann die Region beginnt, was wir zeigen müssen und wie Sie das alles schnell aktualisieren können? Wie es organisiert ist, werde ich später erzählen.

    Zu lange Zeilen? Weiche Umhüllung!




    Auch moderne Redakteure können ohne Soft Wrap nicht leben. Das Bild zeigt, dass der Entwickler die JavaScript-Datei nach der Minimierung geöffnet und sofort bereute. Diese riesige JavaScript-Zeichenfolge passt nicht in einen Bildschirm, wenn wir versuchen, sie im Editor anzuzeigen. Deshalb zerbricht es mit einer weichen Hülle gewaltsam in mehrere Zeilen und stopft sich in den Bildschirm.
    Wie es organisiert ist - später.

    Zu wenig Schönheit




    Und zum Schluss möchte ich noch Schönheit in Texteditoren bringen. Markieren Sie beispielsweise einige Wörter. In der Abbildung oben sind die Schlüsselwörter blau hervorgehoben, einige statische Methoden des Italieners, einige Anmerkungen sind auch in einer anderen Farbe dargestellt.

    Wie behalten und verarbeiten Sie Falten, weiche Umschläge und Hervorhebungen?
    Es stellt sich heraus, dass dies im Prinzip eine und dieselbe Aufgabe ist.

    Zu wenig Schönheit? Range Textmarker!




    Um all diese Funktionen zu unterstützen, müssen wir nur einige Textattribute anhängen, z. B. Farbe, Schriftart oder Text zum Falten, entsprechend einem bestimmten Versatz im Text. Darüber hinaus müssen diese Textattribute an dieser Stelle ständig aktualisiert werden, damit sie alle Arten von Einfügungen und Löschvorgängen erfahren.

    Wie wird das normalerweise umgesetzt? Natürlich in Form eines Baumes.

    Problem: zu viel Schönheit? Intervallbaum!




    Zum Beispiel haben wir hier einige gelbe Markierungen, die wir im Text behalten möchten. Wir fügen diese Hervorhebungsintervalle zum Suchbaum hinzu, den sogenannten Intervallbaum. Dies ist der gleiche Suchbaum, aber etwas komplizierter, da Intervalle anstelle von Zahlen gespeichert werden müssen.

    Und da es sowohl gesunde als auch kleine Intervalle gibt, ist es eine eher triviale Aufgabe, sie zu sortieren, miteinander zu vergleichen und in einen Baum zu falten. Obwohl in der Informatik sehr bekannt. Sieh dann irgendwie zu deiner Freizeit, wie es arrangiert ist. Also nehmen wir alle unsere Intervalle in einen Baum und fassen sie zusammen, und dann ändert sich jeder Text irgendwo in der Mitte zu einer logarithmischen Änderung dieses Baums. Das Einfügen eines Symbols sollte beispielsweise dazu führen, dass alle Intervalle rechts neben diesem Symbol aktualisiert werden. Dazu finden wir alle dominanten Ecken für dieses Symbol und zeigen an, dass alle ihre Unterbüsche um ein Zeichen nach rechts verschoben werden müssen.

    Sie wollen immer noch Schönheit? Ligaturen!




    Es gibt auch so eine schreckliche Sache - Ligaturen, die ich auch unterstützen möchte. Dies sind verschiedene Schönheiten, wie das "! =" - Zeichen in Form einer großen "ungleichen" Glyphe usw. gezeichnet wird. Glücklicherweise freuen wir uns hier auf einen Schwenkmechanismus, der diese Ligaturen unterstützt. Und er arbeitet nach unserer Erfahrung offenbar auf einfachste Weise. In der Schriftart befindet sich eine Liste all dieser Zeichenpaare, die zusammengefügt eine Art clevere Ligatur bilden. Wenn Sie dann eine Linie zeichnen, durchläuft Swing einfach alle diese Paare, findet die erforderlichen Paare und zeichnet sie entsprechend. Wenn die Schrift viele Ligaturen enthält, wird die Anzeige anscheinend proportional langsamer.

    Bremsen beim Tippen


    Und vor allem ist ein weiteres Problem, das in modernen komplexen Editoren auftritt, die Optimierung des Taiping, dh das Drücken der Tasten und das Anzeigen des Ergebnisses.



    Wenn Sie sich in Intellij IDEA befinden und sehen, was passiert, wenn Sie eine Taste drücken, geschieht der nächste Horror dort:

    • Wenn wir auf die Schaltfläche drücken, müssen wir sehen, ob wir uns im Abschluss-Popup befinden, um das Menü für die Fertigstellung zu schließen, wenn wir beispielsweise "Enter" eingeben.
    • Wir müssen prüfen, ob sich die Datei in einem komplizierten Versionskontrollsystem befindet, wie beispielsweise Perforce, das einige Aktionen ausführen muss, um mit der Bearbeitung zu beginnen.
    • Prüfen Sie, ob das Dokument einen bestimmten Bereich enthält, der nicht gedruckt werden kann, z. B. einige automatisch generierte Texte.
    • Wenn das Dokument durch einen Vorgang blockiert wird, der nicht beendet wurde, müssen Sie die Formatierung abschließen und dann fortfahren.
    • Suchen Sie ein eingespritztes Dokument, wenn es an dieser Stelle vorhanden ist, da die Sprache darin anders ist, müssen Sie alles völlig anders eingeben.
    • Rufen Sie alle Plug-Ins mit dem automatischen Popup-Handler auf, damit sie beispielsweise die schließenden und öffnenden Anführungszeichen an der richtigen Stelle eingeben können.
    • Aktualisieren Sie das Fenster für Infoparameter so, dass die erforderlichen Parameter angezeigt werden, wenn Sie dorthin verschoben werden. Entfernen Sie in diesen Plug-Ins die Auswahl "Auswahl", um die Auswahl je nach Sprache zu entfernen. Entfernen Sie diese Auswahl physisch, indem Sie sie aus dem Dokument entfernen.
    • Wählen Sie aus allen Plug-Ins-typisierten Handlern aus, damit sie das gewünschte Zeichen verarbeiten, um eine Klammer auf eine andere Klammer zu drucken.
    • Griff der strukturellen Halterung schließen.
    • Rückgängig machen, virtuelle Räume zählen und mit dem Schreiben beginnen.
    • Fügen Sie schließlich ein Zeichen in unser Dokument ein.

    Hooray!

    Hölle nein, das ist noch nicht alles. Löschen Sie das Zeichen, wenn unser Puffer voll ist. Rufen Sie beispielsweise in der Konsole einen Listener an, damit jeder weiß, dass sich etwas geändert hat. Bildlauf-Editoransicht Rufen Sie einige dumme Zuhörer an.

    Und was passiert jetzt im Editor, als er herausfand, dass sich das Dokument geändert hat und DocumentListener sich freiwillig gemeldet hat?

    In Editor.documentChanged () geschieht Folgendes:

    • Fehlercode aktualisieren;
    • Rinnengröße neu berechnen, neu zeichnen;
    • Nachzählen der Größe der Editor-Komponente, Senden von Ereignissen beim Ändern;
    • Berechnen Sie die modifizierten Linien und ihre Koordinaten.
    • Soft Wrap neu berechnen, wenn die Änderung ihn beeinflusst hat;
    • Repaint anrufen ().

    Diese Neuzeichnung () ist nur ein Hinweis für Swing, dass die Region auf dem Bildschirm neu gezeichnet werden soll. Eine echte Neuzeichnung tritt auf, wenn das Repaint-Ereignis von einer Swing-Nachrichtenwarteschlange verarbeitet wird.

    Das heißt, irgendwo in einer halben Stunde wird die Verarbeitungswarteschlange unseres Ereignisses auftauchen und die entsprechende Methode für das Repaint der entsprechenden Komponente wird



    aufgerufen . Dabei werden folgende Schritte ausgeführt : Eine Reihe verschiedener Paint-Methoden werden aufgerufen, die alles mögliche malen, was in diesem Fall möglich ist.

    Können wir das alles optimieren?



    Das ist alles, um es milde auszudrücken, ziemlich schwierig. Deshalb haben wir von Intellij IDEA beschlossen, den Benutzer zu täuschen.



    Vor all diesen Schrecken, die etwas zählen und aufschreiben, rufen wir eine kleine Methode auf, die diesen unglücklichen Buchstaben genau an die Stelle zieht, an der der Benutzer ihn prägt. Und alle! Der Benutzer ist glücklich, weil er der Meinung ist, dass sich bereits alles geändert hat, aber tatsächlich - nein! Es fängt noch unter der Haube an, aber der kleine Brief brennt schon davor. Und so ist jeder glücklich. Diese Funktion wird als "Null-Latenz-Typisierung" bezeichnet.

    Mitwirkende Redakteure


    Jetzt gibt es so etwas Modisches - die sogenannten kollaborativen Redakteure.

    Was ist das? Dies ist, wenn ein Benutzer in Indien sitzt, ein anderer - in Japan versucht er, etwas in dieselben Google Docs einzugeben und will ein vorhersagbares Ergebnis.

    Was ist das Besondere?

    • Tausende von Benutzern;
    • Große Verzögerung

    Die Besonderheit hier ist, dass eine große Anzahl von Benutzern dies gleichzeitig tun kann, und das Signal kann sehr lange von Indien nach Japan gehen.

    Und aus diesem Grund verwenden sie normalerweise in kollaborativen Redakteuren neue Dinge wie Immobilität. Und sie haben sich verschiedene Dinge ausgedacht, um sicherzustellen, dass alles so läuft, wie es sollte. Dies sind einige Kriterien. Das erste Kriterium ist die Bewahrung der Absicht, die Absichtserhaltung. Das heißt, wenn jemand das Symbol geprägt hat, wird das Symbol aus Indien früher oder später nach Japan kommen und die Japaner werden genau das sehen, was der Inder beabsichtigt hat. Das zweite Kriterium ist die Konvergenz. Dies bedeutet, dass Symbole aus Indien und Japan früher oder später in Japan und Indien gleich werden.

    Operationstransformation




    Der erste Algorithmus, der zur Unterstützung dieser Sache erfunden wurde, wird als "Operationstransformation" bezeichnet. So funktioniert es. Ein Inder und ein Japaner sitzen und tippen etwas: Einer löscht einen Buchstaben vom Ende, ein anderer zieht einen Buchstaben an den Anfang. Das Operationstransformations-Framework sendet diese Operationen an alle anderen Stellen. Er muss verstehen, wie er die Vorgänge überwinden kann, die zu ihm kommen, um zumindest etwas Vernünftiges zu erreichen. Zum Beispiel, wenn Sie gleichzeitig einen Brief gelöscht und angezeigt haben. Es sollte dort und dort mehr oder weniger konsequent funktionieren und zur selben Linie kommen. Wie aus meiner verwirrten Erklärung ersichtlich, ist dies leider eine ziemlich komplizierte Angelegenheit.

    Als die ersten Implementierungen dieses Frameworks aufkamen, entdeckten überraschte Entwickler, dass es ein universelles Beispiel gibt, das alles bricht. Dieses unglückliche Beispiel wurde als "TP2-Puzzle" bezeichnet.



    Ein Benutzer zieht einige Zeichen an den Anfang der Zeile, ein anderer entfernt das alles und der dritte zieht bis zum Ende. Nachdem all diese Operationstransformation versucht, in ein und dasselbe zu verschmelzen, sollte diese Linie hier theoretisch erhalten werden ("DANA"). Einige Implementierungen machten dies jedoch ("NADA"). Weil nicht klar ist, wo er eingefügt werden soll. Das Bild oben zeigt, auf welcher Ebene diese ganze Wissenschaft von der Operationstransformation handelt, wenn aufgrund eines solchen primitiven Beispiels alles kaputt ging.

    Trotzdem machen es manche Leute immer noch, wie Google Docs, Google Wave und einige verteilte Editoren von Etherpad. Sie verwenden die Operationstransformation trotz der aufgelisteten Probleme.

    Konfliktfrei replizierter Datentyp


    Die Leute hier hatten die Köpfe gequält und entschieden: "Machen wir es einfacher als OT!" Die Anzahl der komplizierten Kombinationen von Operationen, die verarbeitet und zusammengefügt werden müssen, wächst quadratisch. Anstatt alle Kombinationen zu verarbeiten, senden wir einfach unseren Status zusammen mit der Operation an alle anderen Hosts, damit er mit einer Garantie von 100% in denselben Text eingefügt werden kann. Dies wird als "CRDT" (Konfliktfrei replizierter Datentyp) bezeichnet.



    Damit dies funktioniert, benötigen Sie einen Zustand und eine Funktion, welcher der beiden Zustände zusammen mit der Operation einen neuen Zustand herstellt. Darüber hinaus sollte diese Funktion kommutativ, assoziativ, idempotent und monoton sein. Und dann ist klar, dass alles einfach und verstärkt funktioniert. Aufgrund dieser drakonischen Einschränkungen der Funktion haben wir keine Angst mehr, die Ordnung (die Funktion ist kommutativ), die Priorität (assoziativ) und den Paketverlust im Netzwerk (Idempotenz und Monotonie) zu stören.



    Gibt es solche Funktionen in der Natur und wie können sie angewendet werden?

    Ja Zum Beispiel für den Fall des sogenannten G-counter'ov, das sind Zähler, die nur wachsen. Sie können eine Funktion für diesen Zähler schreiben, die wirklich eintönig ist und so weiter. Wenn wir die Operation „+1“ aus Japan haben, die andere „+1“ aus Indien, ist es klar, wie man aus ihnen einen neuen Staat machen kann - fügen Sie einfach „2“ hinzu. Es stellt sich jedoch heraus, dass auf die gleiche Weise ein beliebiger Zähler erstellt werden kann, der inkrementiert und dekrementiert werden kann. Dazu genügt es, einen G-Counter zu nehmen, der ständig wächst, und alle Inkrementierungsoperationen darauf anzuwenden. Alle Dekremente werden auf einen anderen G-Counter angewendet, der nach unten wächst. Um den aktuellen Status zu erhalten, müssen Sie nur deren Inhalt abziehen, und wir erhalten dieselbe Monotonie. Dies ist alles möglich, um beliebige Sätze zu erweitern. Aber das Wichtigste ist für beliebige Saiten. Ja, das Bearbeiten von beliebigen Zeichenketten kann auch als CRDT ausgeführt werden. Es stellt sich heraus, dass es ziemlich einfach ist.

    Konfliktfreie replizierte Einfügungen




    Lassen Sie uns zunächst alle Zeichen im Dokument so benennen, dass sie auch nach allen Bearbeitungen eindeutig identifizierbar sind. Nun, zum Beispiel werden wir zusammen mit jedem Buchstaben eine eindeutige Nummer speichern.

    Statt nun allen Personen die Information zu senden, dass wir ein Symbol versetzt eingefügt haben, werden wir stattdessen sagen, welche Symbole wir dazwischen einfügen. Und dann ist klar, dass es keine Unstimmigkeiten geben kann, wo immer wir sie einsetzen, wir werden den Ort definitiv kennen, auch nach anderen Operationen. Anstatt zum Beispiel eine Operation zu senden, die "RLU" am Offset 2 eingefügt werden soll, senden wir die Information, dass wir "RLU" zwischen diesem "Y" und diesem "R" einfügen.

    Konfliktfreie replizierte Löschungen




    Sie können auch Zeichen implementieren und löschen. Da alle unsere Charaktere eindeutig umbenannt werden, sagen wir einfach genau, welcher Charakter gelöscht werden muss, anstelle irgendeiner Art von Offsets. Anstatt diese Zeichen physisch zu löschen, werden wir sie als gelöscht markieren. Damit nachfolgende parallele Einfügungen oder Löschungen wissen, ob sie sich auf diese gelöschten Zeichen auswirken, genau dahin, wohin sie gehen sollen.
    Und es stellt sich heraus, dass diese völlig neuartige Wissenschaft funktioniert.

    Konfliktfreie replizierte Bearbeitungen


    Tatsächlich wird CRDT sogar irgendwo implementiert, zum Beispiel im Xi-Editor, der in das neue Fuchsia-Geheimbetriebssystem eingefügt wird. Um ehrlich zu sein, ich kenne keine anderen Beispiele, aber es funktioniert definitiv.

    Reißverschluss


    Ich möchte Ihnen auch etwas über das sagen, was in dieser neuen, unveränderlichen Welt namens "Zipper" verwendet wird. Nachdem wir unsere Strukturen unveränderlich gemacht hatten, tauchten einige Nuancen der Arbeit mit ihnen auf. Hier haben wir zum Beispiel unseren unveränderlichen Baum mit Text. Wir möchten es ändern (mit "Änderung" hier meine ich "eine neue Version erstellen"). Darüber hinaus möchten wir es an einem bestimmten Ort und ganz aktiv verändern. In Editoren ist dies ziemlich üblich, wenn wir ständig am Cursor etwas drucken, einfügen und löschen. Zu diesem Zweck hatten die Funktionäre eine Struktur namens Zipper entwickelt.

    Es hat das Konzept des sogenannten Cursors oder den aktuellen Platz für die Bearbeitung, wobei die volle Immunität erhalten bleibt. So wird es gemacht.



    Erstellen Sie einen Reißverschluss für unser Dokument, der eine Zeile für die Bearbeitung enthält („Gut gemacht“). Rufen Sie den Vorgang an diesem Reißverschluss auf, um sich entlang der Linie zum Bearbeitungsbereich zu bewegen. In unserem Fall - gehen Sie ganz nach unten. Zu diesem Zweck erstellen wir einen neuen Scheitelpunkt (rot), der dem aktuellen Scheitelpunkt entspricht, und fügt ihm Links zu den untergeordneten Scheitelpunkten unseres Baums hinzu. Um den Zipper-Cursor zu bewegen, gehen wir nach unten und unten und erstellen einen neuen Scheitelpunkt anstelle desjenigen, auf dem wir standen. Fügen Sie gleichzeitig einen Link zum oberen Rand hinzu, um nicht zu vergessen, wo Sie herkommen (rote Pfeile). An diesem Ort der Bearbeitung angelangt, erstellen wir ein neues Blatt anstelle des bearbeiteten Textes (rotes Rechteck). Gehen Sie nun zurück, gehen Sie die roten Pfeile entlang nach oben und setzen Sie sie auf dem Weg zu den korrekten Links zu den Kinderknoten wieder ein.

    Beachten Sie, wie der Cursor uns hilft, das aktuelle Holzstück zu bearbeiten.

    Welche Schlussfolgerungen wollte ich Ihnen mitteilen? Erstens, seltsamerweise gibt es im Thema Texteditoren trotz seiner Verstopfung allerhand interessante Dinge. Außerdem tauchen im selben Thema manchmal neue, manchmal unerwartete Entdeckungen auf. Und drittens sind sie manchmal so neu, dass sie beim ersten Mal nicht funktionieren. Aber es ist interessant und man kann sich aufwärmen. Danke.

    Repository
    Mail

    Links


    Zipper Datenstruktur
    Wie funktioniert CRDT in Xi Editor
    Im Allgemeinen ist eine baumartige Datenstrukturen für Text
    Welche Drehungen im Atom

    Nachdem der Bericht eine lange Zeit, und Microsoft hatten ihre Wurzeln zu erinnern und die Visual Studio - Code - Editor auf dem Tisch Stück neu zu schreiben .
    Aus irgendeinem Grund waren viele Menschen zu Experimenten hingezogen .

    Möchten Sie noch leistungsfähigere Berichte, einschließlich Java 11? Dann erwarten wir Sie am Joker 2018 . Josh Long, John McClean, Marcus Hirt, Robert Scholte und andere ebenso coole Referenten werden dieses Jahr sprechen. Noch 17 Tage vor der Konferenz. Tickets vor Ort.

    Jetzt auch beliebt: