1use std::collections::HashMap;
4use std::{
5 num::NonZeroUsize,
6 ops::Range,
7 path::Path,
8 sync::{Arc, OnceLock},
9};
10
11use lsp_types::SemanticToken;
12use lsp_types::{SemanticTokenModifier, SemanticTokenType};
13use parking_lot::Mutex;
14use strum::EnumIter;
15use tinymist_std::ImmutPath;
16use typst::syntax::{LinkedNode, Source, SyntaxKind, ast};
17
18use crate::{
19 LspPosition, PositionEncoding,
20 adt::revision::{RevisionLock, RevisionManager, RevisionManagerLike, RevisionSlot},
21 analysis::SharedContext,
22 syntax::{Expr, ExprInfo},
23 ty::Ty,
24};
25
26pub type SemanticTokens = Arc<Vec<SemanticToken>>;
28
29#[typst_macros::time(span = source.root().span())]
31pub(crate) fn get_semantic_tokens(ctx: &Arc<SharedContext>, source: &Source) -> SemanticTokens {
32 let mut tokenizer = Tokenizer::new(
33 source.clone(),
34 ctx.expr_stage(source),
35 ctx.analysis.allow_multiline_token,
36 ctx.analysis.position_encoding,
37 );
38 tokenizer.tokenize_tree(&LinkedNode::new(source.root()), ModifierSet::empty());
39 SemanticTokens::new(tokenizer.output)
40}
41
42#[derive(Default)]
44pub struct SemanticTokenCache {
45 next_id: usize,
46 manager: HashMap<ImmutPath, RevisionManager<OnceLock<SemanticTokens>>>,
48}
49
50impl SemanticTokenCache {
51 pub(crate) fn clear(&mut self) {
52 self.next_id = 0;
53 self.manager.clear();
54 }
55
56 pub(crate) fn acquire(
58 cache: Arc<Mutex<Self>>,
59 path: &Path,
60 prev: Option<&str>,
61 ) -> SemanticTokenContext {
62 let that = cache.clone();
63 let mut that = that.lock();
64
65 that.next_id += 1;
66 let prev = prev.and_then(|id| {
67 id.parse::<NonZeroUsize>()
68 .inspect_err(|_| {
69 log::warn!("invalid previous id: {id}");
70 })
71 .ok()
72 });
73 let next = NonZeroUsize::new(that.next_id).expect("id overflow");
74
75 let path = ImmutPath::from(path);
76 let manager = that.manager.entry(path.clone()).or_default();
77 let _rev_lock = manager.lock(prev.unwrap_or(next));
78 let prev = prev.and_then(|prev| {
79 manager
80 .find_revision(prev, |_| OnceLock::new())
81 .data
82 .get()
83 .cloned()
84 });
85 let next = manager.find_revision(next, |_| OnceLock::new());
86
87 SemanticTokenContext {
88 _rev_lock,
89 cache,
90 path,
91 prev,
92 next,
93 }
94 }
95}
96
97pub(crate) struct SemanticTokenContext {
99 _rev_lock: RevisionLock,
100 cache: Arc<Mutex<SemanticTokenCache>>,
101 path: ImmutPath,
102 pub prev: Option<SemanticTokens>,
103 pub next: Arc<RevisionSlot<OnceLock<SemanticTokens>>>,
104}
105
106impl Drop for SemanticTokenContext {
107 fn drop(&mut self) {
108 let mut cache = self.cache.lock();
109 let manager = cache.manager.get_mut(&self.path);
110 if let Some(manager) = manager {
111 let min_rev = manager.unlock(&mut self._rev_lock);
112 if let Some(min_rev) = min_rev {
113 manager.gc(min_rev);
114 }
115 }
116 }
117}
118
119const BOOL: SemanticTokenType = SemanticTokenType::new("bool");
120const PUNCTUATION: SemanticTokenType = SemanticTokenType::new("punct");
121const ESCAPE: SemanticTokenType = SemanticTokenType::new("escape");
122const LINK: SemanticTokenType = SemanticTokenType::new("link");
123const RAW: SemanticTokenType = SemanticTokenType::new("raw");
124const LABEL: SemanticTokenType = SemanticTokenType::new("label");
125const REF: SemanticTokenType = SemanticTokenType::new("ref");
126const HEADING: SemanticTokenType = SemanticTokenType::new("heading");
127const LIST_MARKER: SemanticTokenType = SemanticTokenType::new("marker");
128const LIST_TERM: SemanticTokenType = SemanticTokenType::new("term");
129const DELIMITER: SemanticTokenType = SemanticTokenType::new("delim");
130const INTERPOLATED: SemanticTokenType = SemanticTokenType::new("pol");
131const ERROR: SemanticTokenType = SemanticTokenType::new("error");
132const TEXT: SemanticTokenType = SemanticTokenType::new("text");
133
134#[derive(Clone, Copy, Eq, PartialEq, EnumIter, Default)]
137#[repr(u32)]
138pub enum TokenType {
139 Comment,
142 String,
144 Keyword,
146 Operator,
148 Number,
150 Function,
152 Decorator,
154 Type,
156 Namespace,
158 Bool,
161 Punctuation,
163 Escape,
165 Link,
167 Raw,
169 Label,
171 Ref,
173 Heading,
175 ListMarker,
177 ListTerm,
179 Delimiter,
181 Interpolated,
183 Error,
185 Text,
192 #[default]
194 None,
195}
196
197impl From<TokenType> for SemanticTokenType {
198 fn from(token_type: TokenType) -> Self {
199 use TokenType::*;
200
201 match token_type {
202 Comment => Self::COMMENT,
203 String => Self::STRING,
204 Keyword => Self::KEYWORD,
205 Operator => Self::OPERATOR,
206 Number => Self::NUMBER,
207 Function => Self::FUNCTION,
208 Decorator => Self::DECORATOR,
209 Type => Self::TYPE,
210 Namespace => Self::NAMESPACE,
211 Bool => BOOL,
212 Punctuation => PUNCTUATION,
213 Escape => ESCAPE,
214 Link => LINK,
215 Raw => RAW,
216 Label => LABEL,
217 Ref => REF,
218 Heading => HEADING,
219 ListMarker => LIST_MARKER,
220 ListTerm => LIST_TERM,
221 Delimiter => DELIMITER,
222 Interpolated => INTERPOLATED,
223 Error => ERROR,
224 Text => TEXT,
225 None => unreachable!(),
226 }
227 }
228}
229
230const STRONG: SemanticTokenModifier = SemanticTokenModifier::new("strong");
231const EMPH: SemanticTokenModifier = SemanticTokenModifier::new("emph");
232const MATH: SemanticTokenModifier = SemanticTokenModifier::new("math");
233
234#[derive(Clone, Copy, EnumIter)]
236#[repr(u8)]
237pub enum Modifier {
238 Strong,
240 Emph,
242 Math,
244 ReadOnly,
246 Static,
248 DefaultLibrary,
250}
251
252impl Modifier {
253 pub const fn index(self) -> u8 {
255 self as u8
256 }
257
258 pub const fn bitmask(self) -> u32 {
260 0b1 << self.index()
261 }
262}
263
264impl From<Modifier> for SemanticTokenModifier {
265 fn from(modifier: Modifier) -> Self {
266 use Modifier::*;
267
268 match modifier {
269 Strong => STRONG,
270 Emph => EMPH,
271 Math => MATH,
272 ReadOnly => Self::READONLY,
273 Static => Self::STATIC,
274 DefaultLibrary => Self::DEFAULT_LIBRARY,
275 }
276 }
277}
278
279#[derive(Default, Clone, Copy)]
280pub(crate) struct ModifierSet(u32);
281
282impl ModifierSet {
283 pub fn empty() -> Self {
284 Self::default()
285 }
286
287 pub fn new(modifiers: &[Modifier]) -> Self {
288 let bits = modifiers
289 .iter()
290 .copied()
291 .map(Modifier::bitmask)
292 .fold(0, |bits, mask| bits | mask);
293 Self(bits)
294 }
295
296 pub fn bitset(self) -> u32 {
297 self.0
298 }
299}
300
301impl std::ops::BitOr for ModifierSet {
302 type Output = Self;
303
304 fn bitor(self, rhs: Self) -> Self::Output {
305 Self(self.0 | rhs.0)
306 }
307}
308
309pub(crate) struct Tokenizer {
310 curr_pos: LspPosition,
311 pos_offset: usize,
312 output: Vec<SemanticToken>,
313 source: Source,
314 ei: ExprInfo,
315 encoding: PositionEncoding,
316
317 allow_multiline_token: bool,
318
319 token: Option<Token>,
320}
321
322impl Tokenizer {
323 pub fn new(
324 source: Source,
325 ei: ExprInfo,
326 allow_multiline_token: bool,
327 encoding: PositionEncoding,
328 ) -> Self {
329 Self {
330 curr_pos: LspPosition::new(0, 0),
331 pos_offset: 0,
332 output: Vec::new(),
333 source,
334 ei,
335 allow_multiline_token,
336 encoding,
337
338 token: None,
339 }
340 }
341
342 fn tokenize_tree(&mut self, root: &LinkedNode, modifiers: ModifierSet) {
344 let is_leaf = root.get().children().len() == 0;
345 let mut modifiers = modifiers | modifiers_from_node(root);
346
347 let range = root.range();
348 let mut token = token_from_node(&self.ei, root, &mut modifiers)
349 .or_else(|| is_leaf.then_some(TokenType::Text))
350 .map(|token_type| Token::new(token_type, modifiers, range.clone()));
351
352 if let Some(prev_token) = self.token.as_mut()
354 && !prev_token.range.is_empty()
355 && prev_token.range.start < range.start
356 {
357 let end = prev_token.range.end.min(range.start);
358 let sliced = Token {
359 token_type: prev_token.token_type,
360 modifiers: prev_token.modifiers,
361 range: prev_token.range.start..end,
362 };
363 prev_token.range.start = end;
365 self.push(sliced);
366 }
367
368 if !is_leaf {
369 std::mem::swap(&mut self.token, &mut token);
370 for child in root.children() {
371 self.tokenize_tree(&child, modifiers);
372 }
373 std::mem::swap(&mut self.token, &mut token);
374 }
375
376 if let Some(token) = token.clone()
378 && !token.range.is_empty()
379 {
380 if let Some(prev_token) = self.token.as_mut() {
382 prev_token.range.start = token.range.end;
383 }
384 self.push(token);
385 }
386 }
387
388 fn push(&mut self, token: Token) {
389 let Token {
390 token_type,
391 modifiers,
392 range,
393 } = token;
394
395 use crate::lsp_typst_boundary;
396 use lsp_types::Position;
397 let utf8_start = range.start;
398 if self.pos_offset > utf8_start {
399 return;
400 }
401
402 let source_len = self.source.text().len();
404 let utf8_end = (range.end).min(source_len);
405 self.pos_offset = utf8_start;
406 if utf8_end <= utf8_start || utf8_start > source_len {
407 return;
408 }
409
410 let position = lsp_typst_boundary::to_lsp_position(utf8_start, self.encoding, &self.source);
411
412 let delta = self.curr_pos.delta(&position);
413
414 let encode_length = |s, t| {
415 match self.encoding {
416 PositionEncoding::Utf8 => t - s,
417 PositionEncoding::Utf16 => {
418 let utf16_start = self.source.lines().byte_to_utf16(s).unwrap();
420 let utf16_end = self.source.lines().byte_to_utf16(t).unwrap();
421 utf16_end - utf16_start
422 }
423 }
424 };
425
426 if self.allow_multiline_token {
427 self.output.push(SemanticToken {
428 delta_line: delta.delta_line,
429 delta_start: delta.delta_start,
430 length: encode_length(utf8_start, utf8_end) as u32,
431 token_type: token_type as u32,
432 token_modifiers_bitset: modifiers.bitset(),
433 });
434 self.curr_pos = position;
435 } else {
436 let final_line =
437 self.source
438 .lines()
439 .byte_to_line(utf8_end)
440 .unwrap_or_else(|| self.source.lines().len_lines()) as u32;
441 let next_offset = self
442 .source
443 .lines()
444 .line_to_byte((self.curr_pos.line + 1) as usize)
445 .unwrap_or(source_len);
446 let inline_length = encode_length(utf8_start, utf8_end.min(next_offset)) as u32;
447 if inline_length != 0 {
448 self.output.push(SemanticToken {
449 delta_line: delta.delta_line,
450 delta_start: delta.delta_start,
451 length: inline_length,
452 token_type: token_type as u32,
453 token_modifiers_bitset: modifiers.bitset(),
454 });
455 self.curr_pos = position;
456 }
457 if self.curr_pos.line >= final_line {
458 return;
459 }
460
461 let mut utf8_cursor = next_offset;
462 let mut delta_line = 0;
463 for line in self.curr_pos.line + 1..=final_line {
464 let next_offset = if line == final_line {
465 utf8_end
466 } else {
467 self.source
468 .lines()
469 .line_to_byte((line + 1) as usize)
470 .unwrap_or(source_len)
471 };
472
473 if utf8_cursor < next_offset {
474 let inline_length = encode_length(utf8_cursor, next_offset) as u32;
475 self.output.push(SemanticToken {
476 delta_line: delta_line + 1,
477 delta_start: 0,
478 length: inline_length,
479 token_type: token_type as u32,
480 token_modifiers_bitset: modifiers.bitset(),
481 });
482 delta_line = 0;
483 self.curr_pos.character = 0;
484 } else {
485 delta_line += 1;
486 }
487 self.pos_offset = utf8_cursor;
488 utf8_cursor = next_offset;
489 }
490 self.curr_pos.line = final_line - delta_line;
491 }
492
493 pub trait PositionExt {
494 fn delta(&self, to: &Self) -> PositionDelta;
495 }
496
497 impl PositionExt for Position {
498 fn delta(&self, to: &Self) -> PositionDelta {
504 let line_delta = to.line - self.line;
505 let char_delta = if line_delta == 0 {
506 to.character - self.character
507 } else {
508 to.character
509 };
510
511 PositionDelta {
512 delta_line: line_delta,
513 delta_start: char_delta,
514 }
515 }
516 }
517
518 #[derive(Debug, Eq, PartialEq, Ord, PartialOrd, Copy, Clone, Default)]
519 pub struct PositionDelta {
520 pub delta_line: u32,
521 pub delta_start: u32,
522 }
523 }
524}
525
526#[derive(Clone, Default)]
527struct Token {
528 pub token_type: TokenType,
529 pub modifiers: ModifierSet,
530 pub range: Range<usize>,
531}
532
533impl Token {
534 pub fn new(token_type: TokenType, modifiers: ModifierSet, range: Range<usize>) -> Self {
535 Self {
536 token_type,
537 modifiers,
538 range,
539 }
540 }
541}
542
543fn modifiers_from_node(node: &LinkedNode) -> ModifierSet {
548 match node.kind() {
549 SyntaxKind::Emph => ModifierSet::new(&[Modifier::Emph]),
550 SyntaxKind::Strong => ModifierSet::new(&[Modifier::Strong]),
551 SyntaxKind::Math | SyntaxKind::Equation => ModifierSet::new(&[Modifier::Math]),
552 _ => ModifierSet::empty(),
553 }
554}
555
556fn token_from_node(
564 ei: &ExprInfo,
565 node: &LinkedNode,
566 modifier: &mut ModifierSet,
567) -> Option<TokenType> {
568 use SyntaxKind::*;
569
570 match node.kind() {
571 Star if node.parent_kind() == Some(Strong) => Some(TokenType::Punctuation),
572 Star if node.parent_kind() == Some(ModuleImport) => Some(TokenType::Operator),
573
574 Underscore if node.parent_kind() == Some(Emph) => Some(TokenType::Punctuation),
575 Underscore if node.parent_kind() == Some(MathAttach) => Some(TokenType::Operator),
576
577 MathIdent | Ident => Some(token_from_ident(ei, node, modifier)),
578 Hash => token_from_hashtag(ei, node, modifier),
579
580 LeftBrace | RightBrace | LeftBracket | RightBracket | LeftParen | RightParen | Comma
581 | Semicolon | Colon => Some(TokenType::Punctuation),
582 Linebreak | Escape | Shorthand => Some(TokenType::Escape),
583 Link => Some(TokenType::Link),
584 Raw => Some(TokenType::Raw),
585 Label => Some(TokenType::Label),
586 RefMarker => Some(TokenType::Ref),
587 Heading | HeadingMarker => Some(TokenType::Heading),
588 ListMarker | EnumMarker | TermMarker => Some(TokenType::ListMarker),
589 Not | And | Or => Some(TokenType::Keyword),
590 MathAlignPoint | Plus | Minus | Slash | Hat | Dot | Eq | EqEq | ExclEq | Lt | LtEq | Gt
591 | GtEq | PlusEq | HyphEq | StarEq | SlashEq | Dots | Arrow => Some(TokenType::Operator),
592 Dollar => Some(TokenType::Delimiter),
593 None | Auto | Let | Show | If | Else | For | In | While | Break | Continue | Return
594 | Import | Include | As | Set | Context => Some(TokenType::Keyword),
595 Bool => Some(TokenType::Bool),
596 Int | Float | Numeric => Some(TokenType::Number),
597 Str => Some(TokenType::String),
598 LineComment | BlockComment => Some(TokenType::Comment),
599 Error => Some(TokenType::Error),
600
601 _ => Option::None,
603 }
604}
605
606fn token_from_ident(ei: &ExprInfo, ident: &LinkedNode, modifier: &mut ModifierSet) -> TokenType {
608 let resolved = ei.resolves.get(&ident.span());
609 let context = if let Some(resolved) = resolved {
610 match (&resolved.root, &resolved.term) {
611 (Some(root), term) => Some(token_from_decl_expr(root, term.as_ref(), modifier)),
612 (_, Some(ty)) => Some(token_from_term(ty, modifier)),
613 _ => None,
614 }
615 } else {
616 None
617 };
618
619 if !matches!(context, None | Some(TokenType::Interpolated)) {
620 return context.unwrap_or(TokenType::Interpolated);
621 }
622
623 let next = ident.next_leaf();
624 let next_is_adjacent = next
625 .as_ref()
626 .is_some_and(|n| n.range().start == ident.range().end);
627 let next_parent = next.as_ref().and_then(|n| n.parent_kind());
628 let next_kind = next.map(|n| n.kind());
629 let lexical_function_call = next_is_adjacent
630 && matches!(next_kind, Some(SyntaxKind::LeftParen))
631 && matches!(next_parent, Some(SyntaxKind::Args | SyntaxKind::Params));
632 if lexical_function_call {
633 return TokenType::Function;
634 }
635
636 let function_content = next_is_adjacent
637 && matches!(next_kind, Some(SyntaxKind::LeftBracket))
638 && matches!(next_parent, Some(SyntaxKind::ContentBlock));
639 if function_content {
640 return TokenType::Function;
641 }
642
643 TokenType::Interpolated
644}
645
646fn token_from_term(t: &Ty, modifier: &mut ModifierSet) -> TokenType {
647 use typst::foundations::Value::*;
648 match t {
649 Ty::Func(..) => TokenType::Function,
650 Ty::Value(v) => {
651 match &v.val {
652 Func(..) => TokenType::Function,
653 Type(..) => {
654 *modifier = *modifier | ModifierSet::new(&[Modifier::DefaultLibrary]);
655 TokenType::Function
656 }
657 Module(..) => ns(modifier),
658 _ => TokenType::Interpolated,
660 }
661 }
662 _ => TokenType::Interpolated,
663 }
664}
665
666fn token_from_decl_expr(expr: &Expr, term: Option<&Ty>, modifier: &mut ModifierSet) -> TokenType {
667 use crate::syntax::Decl::*;
668 match expr {
669 Expr::Type(term) => token_from_term(term, modifier),
670 Expr::Decl(decl) => match decl.as_ref() {
671 Func(..) => TokenType::Function,
672 Var(..) => TokenType::Interpolated,
673 Module(..) => ns(modifier),
674 ModuleAlias(..) => ns(modifier),
675 PathStem(..) => ns(modifier),
676 ImportAlias(..) => TokenType::Interpolated,
677 IdentRef(..) => TokenType::Interpolated,
678 ImportPath(..) => TokenType::Interpolated,
679 IncludePath(..) => TokenType::Interpolated,
680 Import(..) => TokenType::Interpolated,
681 ContentRef(..) => TokenType::Interpolated,
682 Label(..) => TokenType::Interpolated,
683 StrName(..) => TokenType::Interpolated,
684 ModuleImport(..) => TokenType::Interpolated,
685 Closure(..) => TokenType::Interpolated,
686 Pattern(..) => TokenType::Interpolated,
687 Spread(..) => TokenType::Interpolated,
688 Content(..) => TokenType::Interpolated,
689 Constant(..) => TokenType::Interpolated,
690 BibEntry(..) => TokenType::Interpolated,
691 Docs(..) => TokenType::Interpolated,
692 Generated(..) => TokenType::Interpolated,
693 },
694 _ => term
695 .map(|term| token_from_term(term, modifier))
696 .unwrap_or(TokenType::Interpolated),
697 }
698}
699
700fn ns(modifier: &mut ModifierSet) -> TokenType {
701 *modifier = *modifier | ModifierSet::new(&[Modifier::Static, Modifier::ReadOnly]);
702 TokenType::Namespace
703}
704
705fn get_expr_following_hashtag<'a>(hashtag: &LinkedNode<'a>) -> Option<LinkedNode<'a>> {
706 hashtag
707 .next_sibling()
708 .filter(|next| next.cast::<ast::Expr>().is_some_and(|expr| expr.hash()))
709 .and_then(|node| node.leftmost_leaf())
710}
711
712fn token_from_hashtag(
713 ei: &ExprInfo,
714 hashtag: &LinkedNode,
715 modifier: &mut ModifierSet,
716) -> Option<TokenType> {
717 get_expr_following_hashtag(hashtag)
718 .as_ref()
719 .and_then(|node| token_from_node(ei, node, modifier))
720}
721
722#[cfg(test)]
723mod tests {
724 use strum::IntoEnumIterator;
725
726 use super::*;
727
728 #[test]
729 fn ensure_not_too_many_modifiers() {
730 assert!(Modifier::iter().len() <= 32);
733 }
734}