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}