xonecas.io
719
Le

lextide / files

lextide / src / core / engine.ts

13.3 KB
1import type { GrammarDefinition } from "../types";
2import {
3	getInternalStates,
4	type InternalMatcher,
5	type InternalRule,
6	type MatchResult,
7} from "./grammar";
8
9const stickyExpressions = new WeakMap<RegExp, RegExp>();
10
11interface ResolvedRule {
12	children?: InternalRule[] | undefined;
13	emptyChildren?: { position: number; scopes: string[] }[] | undefined;
14	length: number;
15	pop: boolean;
16	push?: string | undefined;
17	pushScope?: string | null | undefined;
18	relevance: number;
19	scope?: string | undefined;
20}
21
22interface ChildState {
23	defaultScope?: string | undefined;
24	rules: readonly InternalRule[];
25}
26
27export interface Segment {
28	text: string;
29	scopes: string[];
30	start: number;
31	end: number;
32	stateAfter: string[];
33}
34
35export interface ParseResult {
36	segments: Segment[];
37	relevance: number;
38	state: string[];
39}
40
41export interface SegmentGroup {
42	segments: Segment[];
43	end: number;
44	stateAfter: string[];
45}
46
47export function parseSource(
48	grammar: GrammarDefinition,
49	input: string,
50	initialState: readonly string[] = [grammar.startState],
51): ParseResult {
52	const states = getInternalStates(grammar);
53	const stack =
54		initialState.length > 0 ? [...initialState] : [grammar.startState];
55	const segments: Segment[] = [];
56	let relevance = 0;
57	let position = 0;
58
59	while (position < input.length) {
60		const state = currentState(states, stack);
61		const resolved = matchStateRules(state.rules, input, position);
62
63		if (!resolved) {
64			position = consumePlainSegment(states, stack, segments, input, position);
65			continue;
66		}
67
68		position = consumeResolvedSegment(
69			states,
70			stack,
71			segments,
72			input,
73			position,
74			resolved,
75		);
76		relevance += resolved.relevance;
77	}
78
79	return { segments, relevance, state: stack };
80}
81
82export function groupSegmentsByRootChild(
83	segments: readonly Segment[],
84): SegmentGroup[] {
85	if (segments.length === 0) {
86		return [];
87	}
88
89	const groups: SegmentGroup[] = [];
90	let currentKey = rootChildKey(segments[0]);
91	let currentSegments: Segment[] = [segments[0]];
92
93	for (let index = 1; index < segments.length; index += 1) {
94		const segment = segments[index];
95		const key = rootChildKey(segment);
96
97		if (key === currentKey) {
98			currentSegments.push(segment);
99			continue;
100		}
101
102		groups.push(createGroup(currentSegments));
103		currentSegments = [segment];
104		currentKey = key;
105	}
106
107	groups.push(createGroup(currentSegments));
108
109	return groups;
110}
111
112function consumePlainSegment(
113	states: ReturnType<typeof getInternalStates>,
114	stack: readonly string[],
115	segments: Segment[],
116	input: string,
117	position: number,
118): number {
119	const end = position + codePointLength(input, position);
120
121	pushSegment(
122		segments,
123		input.slice(position, end),
124		activeScopes(states, stack),
125		position,
126		end,
127		stack,
128	);
129
130	return end;
131}
132
133function consumeResolvedSegment(
134	states: ReturnType<typeof getInternalStates>,
135	stack: string[],
136	segments: Segment[],
137	input: string,
138	position: number,
139	resolved: ResolvedRule,
140): number {
141	const end = position + resolved.length;
142	const text = input.slice(position, end);
143	const scopes = activeScopes(
144		states,
145		stack,
146		resolved.pushScope,
147		resolved.scope,
148	);
149
150	emitResolvedSegments(
151		states,
152		segments,
153		text,
154		scopes,
155		position,
156		stack,
157		resolved,
158	);
159	applyStateTransition(stack, resolved);
160	updateTailState(segments, stack);
161
162	return end;
163}
164
165function currentState(
166	states: ReturnType<typeof getInternalStates>,
167	stack: readonly string[],
168) {
169	const stateName = stack[stack.length - 1];
170	const state = states[stateName];
171
172	if (!state) {
173		throw new Error(`Unknown grammar state: ${stateName}`);
174	}
175
176	return state;
177}
178
179function emitResolvedSegments(
180	states: ReturnType<typeof getInternalStates>,
181	segments: Segment[],
182	text: string,
183	scopes: readonly string[],
184	position: number,
185	stack: readonly string[],
186	resolved: ResolvedRule,
187): void {
188	if (
189		(resolved.children && resolved.children.length > 0) ||
190		(resolved.emptyChildren && resolved.emptyChildren.length > 0)
191	) {
192		const childSegments = expandResolvedSegments(
193			states,
194			text,
195			resolved.children,
196			resolved.emptyChildren,
197			scopes,
198			position,
199			stack,
200		);
201
202		for (const childSegment of childSegments) {
203			pushSegment(
204				segments,
205				childSegment.text,
206				childSegment.scopes,
207				childSegment.start,
208				childSegment.end,
209				stack,
210			);
211		}
212
213		return;
214	}
215
216	pushSegment(
217		segments,
218		text,
219		[...scopes],
220		position,
221		position + resolved.length,
222		stack,
223	);
224}
225
226function applyStateTransition(stack: string[], resolved: ResolvedRule): void {
227	if (resolved.push) {
228		stack.push(resolved.push);
229	}
230
231	if (resolved.pop && stack.length > 1) {
232		stack.pop();
233	}
234}
235
236function applyChildStateTransition(
237	states: ReturnType<typeof getInternalStates>,
238	stack: ChildState[],
239	resolved: ResolvedRule,
240): void {
241	if (resolved.push) {
242		const state = states[resolved.push];
243
244		if (!state) {
245			throw new Error(`Unknown grammar state: ${resolved.push}`);
246		}
247
248		stack.push(state);
249	}
250
251	if (resolved.pop && stack.length > 1) {
252		stack.pop();
253	}
254}
255
256function updateTailState(segments: Segment[], stack: readonly string[]): void {
257	const tail = segments[segments.length - 1];
258
259	if (tail) {
260		tail.stateAfter = [...stack];
261	}
262}
263
264function activeScopes(
265	states: ReturnType<typeof getInternalStates>,
266	stack: readonly string[],
267	pushScope?: string | null,
268	transientScope?: string,
269): string[] {
270	const scopes = stack
271		.map((stateName) => states[stateName]?.defaultScope)
272		.filter((scope): scope is string => typeof scope === "string");
273
274	if (typeof pushScope === "string") {
275		scopes.push(pushScope);
276	}
277
278	if (typeof transientScope === "string") {
279		scopes.push(transientScope);
280	}
281
282	return scopes;
283}
284
285function activeChildScopes(
286	baseScopes: readonly string[],
287	stack: readonly ChildState[],
288	pushScope?: string | null,
289	transientScope?: string,
290): string[] {
291	const scopes = [
292		...baseScopes,
293		...stack
294			.map((state) => state.defaultScope)
295			.filter((scope): scope is string => typeof scope === "string"),
296	];
297
298	if (typeof pushScope === "string") {
299		scopes.push(pushScope);
300	}
301
302	if (typeof transientScope === "string") {
303		scopes.push(transientScope);
304	}
305
306	return scopes;
307}
308
309function codePointLength(input: string, position: number): number {
310	const codePoint = input.codePointAt(position);
311
312	if (codePoint === undefined) {
313		return 1;
314	}
315
316	return codePoint > 0xffff ? 2 : 1;
317}
318
319function createGroup(segments: Segment[]): SegmentGroup {
320	const tail = segments[segments.length - 1];
321
322	return {
323		segments,
324		end: tail.end,
325		stateAfter: tail.stateAfter,
326	};
327}
328
329function matchExpression(
330	expression: RegExp,
331	input: string,
332	position: number,
333): string | null {
334	const sticky = getStickyExpression(expression);
335	sticky.lastIndex = position;
336	const match = sticky.exec(input);
337
338	if (!match || match[0].length === 0) {
339		return null;
340	}
341
342	return match[0];
343}
344
345function matchStateRules(
346	rules: readonly InternalRule[],
347	input: string,
348	position: number,
349): ResolvedRule | null {
350	for (const rule of rules) {
351		const resolved = resolveRule(rule, input, position);
352
353		if (resolved) {
354			return resolved;
355		}
356	}
357
358	return null;
359}
360
361function parseChildren(
362	states: ReturnType<typeof getInternalStates>,
363	input: string,
364	rules: readonly InternalRule[],
365	baseScopes: readonly string[],
366	offset: number,
367	stateAfter: readonly string[],
368): Segment[] {
369	const segments: Segment[] = [];
370	const childStack: ChildState[] = [{ rules }];
371	let position = 0;
372
373	while (position < input.length) {
374		const current = childStack[childStack.length - 1];
375		const resolved = matchStateRules(current.rules, input, position);
376
377		if (!resolved) {
378			const length = codePointLength(input, position);
379			const end = position + length;
380
381			pushSegment(
382				segments,
383				input.slice(position, end),
384				activeChildScopes(baseScopes, childStack),
385				offset + position,
386				offset + end,
387				stateAfter,
388			);
389
390			position = end;
391			continue;
392		}
393
394		const end = position + resolved.length;
395		const text = input.slice(position, end);
396		const scopes = activeChildScopes(
397			baseScopes,
398			childStack,
399			resolved.pushScope,
400			resolved.scope,
401		);
402
403		if (
404			(resolved.children && resolved.children.length > 0) ||
405			(resolved.emptyChildren && resolved.emptyChildren.length > 0)
406		) {
407			const childSegments = expandResolvedSegments(
408				states,
409				text,
410				resolved.children,
411				resolved.emptyChildren,
412				scopes,
413				offset + position,
414				stateAfter,
415			);
416
417			for (const childSegment of childSegments) {
418				pushSegment(
419					segments,
420					childSegment.text,
421					childSegment.scopes,
422					childSegment.start,
423					childSegment.end,
424					stateAfter,
425				);
426			}
427		} else {
428			pushSegment(
429				segments,
430				text,
431				scopes,
432				offset + position,
433				offset + end,
434				stateAfter,
435			);
436		}
437
438		applyChildStateTransition(states, childStack, resolved);
439		position = end;
440	}
441
442	return segments;
443}
444
445function expandResolvedSegments(
446	states: ReturnType<typeof getInternalStates>,
447	text: string,
448	rules: readonly InternalRule[] | undefined,
449	emptyChildren: readonly { position: number; scopes: string[] }[] | undefined,
450	baseScopes: readonly string[],
451	offset: number,
452	stateAfter: readonly string[],
453): Segment[] {
454	const segments = parseChildren(
455		states,
456		text,
457		rules ?? [],
458		baseScopes,
459		offset,
460		stateAfter,
461	);
462
463	if (!emptyChildren || emptyChildren.length === 0) {
464		return segments;
465	}
466
467	for (const emptyChild of emptyChildren) {
468		const position = offset + emptyChild.position;
469
470		splitSegmentsAtPosition(segments, position);
471		pushSegment(
472			segments,
473			"",
474			[...baseScopes, ...emptyChild.scopes],
475			position,
476			position,
477			stateAfter,
478		);
479	}
480
481	segments.sort(compareSegments);
482	return segments;
483}
484
485function splitSegmentsAtPosition(segments: Segment[], position: number): void {
486	for (let index = 0; index < segments.length; index += 1) {
487		const segment = segments[index];
488
489		if (position <= segment.start || position >= segment.end) {
490			continue;
491		}
492
493		const splitIndex = position - segment.start;
494		const left: Segment = {
495			text: segment.text.slice(0, splitIndex),
496			scopes: [...segment.scopes],
497			start: segment.start,
498			end: position,
499			stateAfter: [...segment.stateAfter],
500		};
501		const right: Segment = {
502			text: segment.text.slice(splitIndex),
503			scopes: [...segment.scopes],
504			start: position,
505			end: segment.end,
506			stateAfter: [...segment.stateAfter],
507		};
508
509		segments.splice(index, 1, left, right);
510		return;
511	}
512}
513
514function pushSegment(
515	segments: Segment[],
516	text: string,
517	scopes: string[],
518	start: number,
519	end: number,
520	stateAfter: readonly string[],
521): void {
522	const tail = segments[segments.length - 1];
523
524	if (tail && tail.end === start && sameScopes(tail.scopes, scopes)) {
525		tail.text += text;
526		tail.end = end;
527		tail.stateAfter = [...stateAfter];
528		return;
529	}
530
531	segments.push({
532		text,
533		scopes,
534		start,
535		end,
536		stateAfter: [...stateAfter],
537	});
538}
539
540function resolveRule(
541	rule: InternalRule,
542	input: string,
543	position: number,
544): ResolvedRule | null {
545	const matched = matchRule(rule, input, position);
546
547	if (!isValidMatch(matched)) {
548		return null;
549	}
550
551	if (typeof matched === "object" && matched !== null) {
552		return buildResolvedRuleFromObject(rule, matched);
553	}
554
555	return buildResolvedRuleFromLength(rule, matchLength(matched));
556}
557
558function matchRule(
559	rule: InternalRule,
560	input: string,
561	position: number,
562): MatchResult | string {
563	return rule.match instanceof RegExp
564		? matchExpression(rule.match, input, position)
565		: resolveMatcher(rule.match, input, position);
566}
567
568function resolveMatcher(
569	matcher: InternalMatcher,
570	input: string,
571	position: number,
572): MatchResult {
573	return matcher(input, position);
574}
575
576function buildResolvedRuleFromLength(
577	rule: InternalRule,
578	length: number,
579): ResolvedRule {
580	return {
581		length,
582		scope: rule.scope,
583		push: rule.push,
584		pop: rule.pop === true,
585		children: rule.children,
586		emptyChildren: undefined,
587		relevance: rule.relevance ?? 0,
588		pushScope: rule.pushScope,
589	};
590}
591
592function buildResolvedRuleFromObject(
593	rule: InternalRule,
594	matched: Exclude<MatchResult, number | null>,
595): ResolvedRule {
596	return {
597		length: matchLength(matched),
598		scope: matched.scope ?? rule.scope,
599		push: matched.push ?? rule.push,
600		pop: matched.pop ?? rule.pop === true,
601		children: matched.children ?? rule.children,
602		emptyChildren: matched.emptyChildren,
603		relevance: matched.relevance ?? rule.relevance ?? 0,
604		pushScope: matched.pushScope ?? rule.pushScope,
605	};
606}
607
608function isValidMatch(
609	matched: MatchResult | string,
610): matched is Exclude<MatchResult, null> | string {
611	if (!matched) {
612		return false;
613	}
614
615	return matchLength(matched) > 0;
616}
617
618function matchLength(matched: Exclude<MatchResult, null> | string): number {
619	return typeof matched === "number" ? matched : matched.length;
620}
621
622function rootChildKey(segment: Segment): string {
623	return segment.scopes[0] ?? "";
624}
625
626function compareSegments(left: Segment, right: Segment): number {
627	if (left.start !== right.start) {
628		return left.start - right.start;
629	}
630
631	if (left.end !== right.end) {
632		return left.end - right.end;
633	}
634
635	return left.scopes.length - right.scopes.length;
636}
637
638function sameScopes(
639	left: readonly string[],
640	right: readonly string[],
641): boolean {
642	if (left.length !== right.length) {
643		return false;
644	}
645
646	for (let index = 0; index < left.length; index += 1) {
647		if (left[index] !== right[index]) {
648			return false;
649		}
650	}
651
652	return true;
653}
654
655function getStickyExpression(expression: RegExp): RegExp {
656	const cached = stickyExpressions.get(expression);
657
658	if (cached) {
659		return cached;
660	}
661
662	const flags = expression.flags.replaceAll("g", "");
663	const sticky = new RegExp(
664		expression.source,
665		flags.includes("y") ? flags : `${flags}y`,
666	);
667
668	stickyExpressions.set(expression, sticky);
669
670	return sticky;
671}