PrismJS / PrismJS/prism

Fix greedy lookbehinds with sticky regexes

Open
#2,907 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

bug language-definitions
Dominant language
JavaScript
Stars
13k
Forks
1.4k
Avg merge
15h 36m
Merged PRs (30d)
3

Description

The problem

Right now, greedy patterns with lookbehinds have a problem: the lookbehinds don't work properly.

Here's an example:

image

JavaScript (and many other C-like languages) use(s) the C-like comment patterns:

Prism.languages.clike = {
	'comment': [
		{
			pattern: /(^|[^\\])\/\*[\s\S]*?(?:\*\/|$)/,
			lookbehind: true,
			greedy: true
		},
		...

Why does this bug occur? It's actually pretty simple. Let's step through our matching algorithm!

  1. Let text be the string "/**//**/" and let pattern be the C-like comment regex.
  2. First we set pattern.lastIndex = 0.
  3. Let m be pattern.exec(text). m is now the match ["/**/", "", index: 0]. The lookbehind group is empty because it accepted using the ^ assertion. pattern.lastIndex is now 4.
  4. Create the token for the first /**/. Then we get ready for the next iteration.
  5. Let m be pattern.exec(text). m is null now. The pattern rejected text because of the lookbehind group. The ^ alternative obviously rejects because the second /**/ isn't at the start of the string. The [^\\] alternative accepts but leads nowhere because it consumes the first / of the second /**/.
  6. The matching algorithm moves on to other patterns.

The reason why the second line in the example gets highlighted correctly is the space between the two comments. The [^\\] alternative can consume the space and so the comment can be detected.

I highlighted the problem with this simple example but this is a bit more general. All greedy patterns with lookbehinds are affected.

Note: Non-greedy patterns are not affected by this problem at all because the matching algorithm works differently for them.

The solution

We can fix this with the ES6 sticky y flag.

Here is the fixed version of the above example:

Prism.languages.clike = {
	'comment': [
		{
			pattern: /(|[\s\S]*?[^\\])\/\*[\s\S]*?(?:\*\/|$)/y,
			lookbehind: true,
			greedy: true
		},
		...

I haven't performance-tested this yet, so it might be slower.

An even better solution would be to use ES2018 lookbehind assertions. See #1708 as for why this isn't possible right now.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the C-like comment definition in components/prism-clike.js and reproduce the linked test case at prismjs.com/test.html. Trace the matching algorithm for greedy patterns with lookbehinds, then verify that adjacent C-like comments are highlighted correctly without breaking the existing behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
tooling
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.