Prism: Differential Highlighting

Created on 18 Mar 2020 · 15Comments · Source: PrismJS/prism

Motivation
If a sample string that is supposed to be highlighted is huge, it takes some time for the highlighter to tokenize it. By having a differential highlighting method, a small change in this string is not triggering an entire new tokenizing method.

Description
Include a range where changes are occurred in an input string and tokenize that section only instead of the entire string from scratch.

Alternatives
none

enhancement

Source

belaviyo

Most helpful comment

I actually have an idea for how to accomplish differential highlighting but it's not easy.

The main problem is that we don't know where to start highlighting because changes in one line might affect tokens which span more than one line. Patterns with lookarounds are also affected.

My idea is the following: We split the patterns of a language into two groups: greedy and non-greedy.
(The problem here is that this assumes that all greedy patterns come before all non-greedy patterns in a given language. Most languages actually are of that form (and I think that you can transform any Prism language into that form), so let's run with that assumption.)

If the language is of that form, we can think about all greedy tokens as one token. We can do this because Prism's greedy matching is really just a way to split a regex of the form /token1|token2/ into two tokens while retaining the left to right matching. So we just reverse that process here.

So let's replace all greedy tokens in the language with one non-greedy token representing all greedy tokens, let's call it $greedy. What we're left with, is a language with only non-greedy tokens. ($greedy has to be the union of all greedy tokens which might be impossible because of the limitations of Prism's lookbehinds. I will just assume, it's possible.)

To implement differential highlighting, we need the token stream of the old text, the complete changed text, and the range of the changes.

I will now, only describe the basic idea because the actual algorithm isn't easy enough to be described in only a few paragraphs.

The idea is that we go through the patterns of our language in order and try to increase the lower boundary of the text, we have to re-highlight by using the fact that Prism doesn't match tokens from left to right in a greedy fashion but in a first-come-first-served fashion. So if we find a token in the changed text which is the same as a token in the old token stream and is between the current lower boundary and the start of the changes, we can increase the lower boundary to the end position of the token. Like this, we increase the lower boundary iteratively for all patterns until either tokens always change or we reached the start of the changes.
The same idea can be applied to lower the upper boundary of the text we have to re-highlight.

I'll be honest: While possible, differential highlighting is horribly complex to implement and IMO simply out of the scope of Prism. And with that, I will close the issue.

RunDevelopment on 20 Mar 2020

👀1 ❤1 👍1

All 15 comments

You could probably implement this yourself if you know upfront what part of the string changed and could focus on rehighlighting maybe a couple lines before and after, but I'm not sure how Prism could do this.

mAAdhaTTah on 18 Mar 2020

Yes, I know the changed boundary. The issue is I am not sure how to find the boundary that is acceptable to perform a new tokenizing on.

I was hoping to have a function that returns the minimum boundary that needs to be retokenized. This is not something I can do without knowing the language structure.

Example:

Before:

After:

belaviyo on 19 Mar 2020

To me, this is the only missing API to use Prims.js for efficient dynamic highlighting.

belaviyo on 19 Mar 2020

I was hoping to have a function that returns the minimum boundary that needs to be retokenized. This is not something I can do without knowing the language structure.

Yeah, this is probably going to be different per language. I don't think it's possible to do in a generic way.

mAAdhaTTah on 19 Mar 2020

Maybe some insight on the highlighting performance of Prism:

This actual tokenization of a string is usually quite fast (in the range of a few milliseconds for 1k lines of code). Generating the HTML code for those tokens usually takes about the same time as creating the token stream (so another few milliseconds). The browser then parsing the generated HTML code and updating the DOM, now that takes time (usually tens of milliseconds for 1k lines of code).
The actual times heavily depend on the code, its language, and the machine you're using, but the orders of magnitude generally hold.

Your issue is performance, right? In that case, you could probably get away to tokenizing the whole string, figuring what parts of the token streams changed, and then partially updating the DOM.
You still have to tokenize the whole string, but it should be quite fast.

RunDevelopment on 19 Mar 2020

@RunDevelopment

This actual tokenization of a string is usually quite fast

This is the only function that I was hoping to be fast. I can do the rest partially and efficiently. However, I've tried the following code on JQuery and it took around 1 second which is not acceptable for dynamic highlighting. (p.s. on the same machine, the same code gets highlighted on CodeMirror almost immediately)

<!DOCTYPE html>
<html>
<body>
  <script type="text/javascript" src="prism.js"></script>
  <script type="text/javascript">
    fetch('https://code.jquery.com/jquery-3.4.1.js').then(r => r.text()).then(string => {
      console.time();
      const tokens = Prism.tokenize(string, Prism.languages.javascript);
      console.timeEnd();
    });
  </script>
</body>
</html>

outputs:
1. default: 653.635986328125ms
2. default: 780.9658203125ms
3. default: 1258.4541015625ms

belaviyo on 20 Mar 2020

I looked at the example and found why it takes so long. The TLDR; is the JQuery source is a worst-case for Prism's array-based token stream implementation meaning that a lot of operations which normally take O(1) time, now take O(n) time (the browser optimizes a lot, so it's probably closer to O(log n)).
For the kind of small files (up to 1k lines) Prism was originally intended to be used on, this usually isn't a problem but for bigger files, it can be.

In #1909, I implemented a solution that guarantees O(1) time for all token stream operations, but it's kinda stuck (as I said, this isn't the usual use case).
A quick benchmark shows that it will help quite a bit for your test file.

benchmark

  https://code.jquery.com/jquery-3.4.1.js (274 kB)
  | PrismJS@master                    805.30ms ± 46%   19smp 27.04x
  | RunDevelopment@core-linked-list    29.78ms ±  0%  326smp

@mAAdhaTTah Maybe we could try to get #1909 merged? I already resolved the merge conflicts.

RunDevelopment on 20 Mar 2020

Looking back at #1909, my initial thought was if the issue doesn't affect most users, it's not worth the extra bytes. Highlighting the entirety of the jQuery source seems like an edge case; doing so _multiple times_, even more so.

If you're going to be tokenizing a large string, I almost want to suggest taking advantage of Prism's Worker functionality and doing it off-thread. It won't make it faster, but it will keep the main thread from locking up while Prism does its tokenization.

mAAdhaTTah on 20 Mar 2020

Highlighting the entirety of the jQuery source seems like an edge case; doing so multiple times, even more so.

I can agree with the multiple times part but users might highlight big files (like the jQuery source). When publishing documentation, they often provide a "jump to source" option, where the whole file is displayed.
Admittedly, it's rare compared to highlighting a few lines of code in a blog article but I still think that Prism should scale well with larger text files.

Also, doing the highlighting in the off thread will unblock the UI, but you won't get the results any faster, so your text editor is responsive but it still lags.

it's not worth the extra bytes

Right now, it adds ~700bytes which is a ~10% increase. I can probably get it down a little more but I think it's worth the 2x and up performance improvements.

RunDevelopment on 20 Mar 2020

Going to continue the convo over on that PR.

mAAdhaTTah on 20 Mar 2020

That said, for this issue, I'm not sure "differential highlighting" is something we can accomplish. @RunDevelopment If you agree, you can close this issue.

mAAdhaTTah on 20 Mar 2020

I actually have an idea for how to accomplish differential highlighting but it's not easy.

The main problem is that we don't know where to start highlighting because changes in one line might affect tokens which span more than one line. Patterns with lookarounds are also affected.

To implement differential highlighting, we need the token stream of the old text, the complete changed text, and the range of the changes.

I will now, only describe the basic idea because the actual algorithm isn't easy enough to be described in only a few paragraphs.

I'll be honest: While possible, differential highlighting is horribly complex to implement and IMO simply out of the scope of Prism. And with that, I will close the issue.

RunDevelopment on 20 Mar 2020

👀1 ❤1 👍1

Two questions:

Is it possible to have a function that returns the closest bounding token at a cursor position of a string?
Is it possible to have a signaling method for the tokenizer to get stopped before the entire string is tokenized? Something like an each(token) {return true/false} function that can break tokenizing in the middle of the operation.

To me, these are the minimum components that can help to deploy prim.js for more complex works without altering the basic usage of the library.

btw the speed of tokenizing on RunDevelopment@core-linked-list is considerably improved. If prims.js supports worker it implies that this library is capable of doing heavy duties.

belaviyo on 21 Mar 2020

No. Prism and its plugins only traverse the full token stream, so we never needed such a search function. Plugins sometimes heavily modify the token stream, so having to maintain a data structure for quick searches would actually slow down Prism for most users.
That being said, it's not very hard to implement this function yourself (see below).

No, but you can pass a different grammar. If you know beforehand at which token you want to break, you can do this:

const newGrammar = { };
for (const name in oldGrammar) {
    if (name === breakName) break;
    newGrammar[name] = oldGrammar[name];
}
Prism.tokenize(code, newGrammar);

Get token at or before a given index

// use the below functions like this
const tokens = Prism.tokenize(code, grammar);
assignIndexes(tokens); // has to be done once

const pos = getTokenAtOrBefore(tokens, someIndex);
if (pos === -1) {
    // not found
} else {
    const token = tokens[pos] as Token;
}

I haven't tested these functions, so please use them carefully!

interface Token {
    readonly type: string;
    readonly content: string | Token | (string | Token)[];
    length: number;
    index: number; // not a real property; we will add this later
}

/**
 * A token stream is not just a simple array. It is guaranteed to not contain adjacent string values.
 * This guarantee is assumed by the below methods.
 */
type TokenStream = (string | Token)[]

/**
 * Calculates the string length of a token.
 */
function getLength(value: string | Token): number {
    if (typeof value === "string") {
        return value.length;
    } else {
        if (Array.isArray(value.content)) {
            return value.content.reduce((total, x) => total + getLength(x), 0);
        } else {
            return getLength(value.content);
        }
    }
}

/**
 * Assigns the index value of all top-level tokens and returns the total string length of the token stream.
 */
function assignIndexes(stream: (string | Token)[]): number {
    let index = 0;
    for (const value of stream) {
        const length = getLength(value);
        if (typeof value !== "string") {
            value.index = index;
            value.length = length;
        }
        index += length;
    }
    return index;
}

/**
 * Returns the index of the token with the greatest index that is <= the given index.
 * 
 * If no such token exists, `-1` will be returned.
 */
function getTokenAtOrBefore(indexesStream: (string | Token)[], index: number): number {
    let low = 0, high = indexesStream.length;
    while (low < high) {
        // adjust bounds
        if (typeof indexesStream[low] === "string") {
            low++;
            continue;
        }
        if (typeof indexesStream[high - 1] === "string") {
            high--;
            continue;
        }

        let m = (low + high) >> 1;
        if (typeof indexesStream[m] === "string") {
            m--;
        }
        const mValue = indexesStream[m] as Token; // we know is has to be a Token but TS doesn't

        if (mValue.index <= index) {
            // find the next token. If that token does not contain the index and is right of it, m is the token
            // before the given index
            let next = m + 1;
            if (typeof indexesStream[next] === "string") next++; // skip string
            if (next >= indexesStream.length) {
                return m; // there is no token after this one, so m is the last token before the given index
            }
            const nextValue = indexesStream[next] as Token;
            if (index < nextValue.index) {
                return m;
            } else {
                low = next;
            }
        } else {
            high = m;
        }
    }
    return -1;
}

RunDevelopment on 21 Mar 2020

@belaviyo