Il modo migliore per salvare molte coppie di posizioni in Emacs Lisp

Question

Sono nel mezzo della trasformazione di un normale tokenizzatore di riavvio completo (portato dal parser della lingua originale, la lingua è irrilevante qui) in uno incrementale più avanzato. Ciò implica quanto segue:

a) deve essere veloce, molto veloce;

b) su ogni aggiornamento di testo (sia esso inserimento o cancellazione) deve trovare i token danneggiati e riparare di conseguenza l'elenco dei token.

La versione originale del tokenizzatore crea semplicemente un elenco di token mentre scorre il testo del buffer utilizzando espressioni regolari; ogni token nella lista è un vettore di 4 elementi (['TOKENTYPE "token-lexeme" linum charnum]). Linum/charnum sono numeri semplici che specificano la posizione del token nel buffer nel momento in cui è stata eseguita la lexing. Torta facile

Ora, al punto. Ogni volta (beh .. non ogni volta, ma abbastanza spesso) un utente aggiunge o cancella un carattere (o una stringa) il nuovo tokenizzatore deve trovare un token costruito usando il testo in una posizione di modifica e, probabilmente, i token dipendenti per dopo delezioni/aggiornamenti.

Ci sono due problemi qui:

a) posizioni token dovrebbero essere dinamica (vale a dire, se un utente aggiunge un testo all'inizio di un buffer -> non dobbiamo disturbare i token di fissaggio alla fine del buffer);

b) un modo per raggiungere un token danneggiato (o molti token in generale).

In questo momento sto cercando di utilizzare le sovrapposizioni per l'attività poiché le sovrapposizioni hanno un'interfaccia piacevole che soddisfa le mie esigenze: le funzioni sovrapposizioni/sovrapposizioni aiutano la ricerca; e sovrapposizione inizio/fine spostamento in un modo appropriato.

Posso farlo felicemente per un file più piccolo. Ma si scopre (e devo ammettere che sono stato avvertito dai documenti) che la soluzione non è scalabile: anche un file LOC medio di 1K può avere overlay CONST * LOC, che è troppo per Emacs.

Questo è stato il mio primo tentativo e non è stato un successo. Sto considerando alternative come:

1) gestire un albero di ricerca di token scritto a mano usando numeri semplici;

2) stesso albero, ma utilizzando i marcatori;

3) un tipo di approccio misto che include sia numeri semplici che indicatori.

Qualsiasi alternativa agli approcci citati? O forse c'è un modo migliore per gestire un sacco di sovrapposizioni?

Answer 1

Come Lindydancer, ti suggerisco di utilizzare le proprietà di testo anziché le sovrapposizioni. Le sovrapposizioni si ridimensionano come O (N^2) mentre le proprietà del testo si ridimensionano come O (N log N), quindi funziona molto meglio. Non userei il font-lock per nessuno di questi, comunque.

Ovviamente, una soluzione alternativa è quella di correggere gli overlay: il codice C può essere modificato per renderlo O (N log N). Ho saputo come farlo per un po 'ora, ma non ho trovato il tempo (e sono improbabile che trovi il tempo in un futuro prevedibile), quindi se qualcuno fosse interessato sarei molto felice di aiutarlo a farlo.

Answer 2

Un'alternativa agli overlay è proprietà di testo, sono allegate al testo in modo diverso da quelle di sovrapposizione, quindi sono molto più efficienti.

Un pacchetto che utilizza molto le proprietà del testo è font-lock. Normalmente, è usato per evidenziare i buffer, ma non c'è nulla che ti impedisca di fare il backup su di esso per i tuoi scopi. In questo modo si otterrà l'intero sistema per rilevare che l'utente ha modificato il contenuto del buffer gratuitamente.

Nel tuo caso, è possibile sostituire l'espressione regolare in una parola chiave blocco font con una funzione che verrà chiamata con un limite di ricerca.Tutto quello che devi fare è scansionare la relativa sezione breve, impostare le tue proprietà del testo e il gioco è fatto. (Inoltre, devi impostare il blocco dei caratteri su quale proprietà stai utilizzando font-lock-extra-managed-props.)