1use std::cell::RefCell;
3use std::rc::Rc;
4use std::borrow::{Borrow, Cow};
5use std::collections::{HashSet, VecDeque, LinkedList};
6use std::iter::FromIterator;
7use std::vec;
8use serde::{Serialize, Deserialize};
9use crate::frontend::data::*;
10
11#[derive(Debug, Clone, Copy, PartialEq, Hash, Serialize, Deserialize)]
16pub struct CharIndex {
17 pub byte_index: usize,
18 pub char_index: usize,
19}
20
21impl CharIndex {
22 pub fn zero() -> Self {
23 CharIndex{
24 byte_index: 0,
25 char_index: 0,
26 }
27 }
28}
29
30#[derive(Debug, Clone, Copy, PartialEq, Hash, Serialize, Deserialize)]
31pub struct CharRange {
32 pub start: CharIndex,
33 pub end: CharIndex,
34}
35
36impl CharRange {
37 pub fn join(start: Option<CharIndex>, end: Option<CharIndex>) -> Option<Self> {
38 if let Some(start) = start {
39 if let Some(end) = end {
40 return Some(CharRange{start, end})
41 }
42 }
43 None
44 }
45 pub fn new(start: CharIndex, end: CharIndex) -> Self {
46 CharRange{start, end}
47 }
48 pub fn byte_index_range<'a>(&self, source: &'a str) -> Option<(usize, usize)> {
49 fn find_utf8_end(s: &str, i: usize) -> Option<usize> {
50 s.char_indices().nth(i).map(|(_, x)| x.len_utf8())
51 }
52 let start_byte = self.start.byte_index;
53 let end_byte = self.end.byte_index;
54 let real_end_byte = source
55 .get(start_byte..=end_byte)
56 .map(|_| end_byte)
57 .or_else(|| {
58 let corrected_end = find_utf8_end(source, end_byte)?;
59 source
60 .get(start_byte..=corrected_end)
61 .map(|_| corrected_end)
62 });
63 real_end_byte.map(|l| (start_byte, l))
64 }
65 pub fn substrng<'a>(&self, source: &'a str) -> Option<&'a str> {
66 if let Some((start, end)) = self.byte_index_range(source) {
67 let sub_str = source.get(start..end).unwrap();
68 Some(sub_str)
69 } else {
70 None
71 }
72 }
73 pub fn into_annotated_tree<T>(self, data: T) -> Ann<T> {
74 Ann {
75 range: Some(self),
76 data,
77 }
78 }
79}
80
81#[derive(Debug, Clone, PartialEq)]
82pub struct Ann<T> {
83 range: Option<CharRange>,
84 pub data: T,
85}
86
87impl<T> Ann<T> {
88 pub fn unannotated(data: T) -> Self {
89 let range = None;
90 Ann {range, data}
91 }
92 pub fn new(range: CharRange, data: T) -> Self {
93 Ann {range: Some(range), data}
94 }
95 pub fn join(range: Option<CharRange>, data: T) -> Self {
96 Ann {range, data}
97 }
98 pub fn range(&self) -> Option<CharRange> {
99 self.range
100 }
101 pub fn start(&self) -> Option<CharIndex> {
102 if let Some(range) = self.range {
103 return Some(range.start)
104 }
105 None
106 }
107 pub fn end(&self) -> Option<CharIndex> {
108 if let Some(range) = self.range {
109 return Some(range.end)
110 }
111 None
112 }
113 pub fn map<U>(self, f: impl Fn(T) -> U) -> Ann<U> {
114 Ann {
115 range: self.range,
116 data: f(self.data),
117 }
118 }
119}
120
121
122#[derive(Debug, Clone)]
127pub struct Tag<'a> {
128 pub name: Ann<Atom<'a>>,
129 pub parameters: Option<Vec<Node<'a>>>,
130 pub children: Vec<Node<'a>>,
133 pub rewrite_rules: Vec<RewriteRule<Node<'a>>>,
134}
135
136impl<'a> Tag<'a> {
137 pub fn new(name: Ann<&'a str>, children: Vec<Node<'a>>) -> Self {
139 Tag{
140 name: Ann {
141 range: name.range,
142 data: Cow::Borrowed(name.data)
143 },
144 parameters: None,
145 children,
146 rewrite_rules: Vec::new(),
147 }
148 }
149 pub fn has_name(&self, name: &str) -> bool {
150 return self.name() == name
151 }
152 pub fn insert_parameter(&mut self, value: Ann<&str>) {
153 let mut args = self.parameters.clone().unwrap_or(Vec::new());
154 args.push(Node::String(Ann::join(
155 value.range,
156 Cow::Owned(value.data.to_owned()),
157 )));
158 self.parameters = Some(args);
159 }
160 pub fn insert_unannotated_parameter(&mut self, value: &str) {
161 let mut args = self.parameters.clone().unwrap_or(Vec::new());
162 args.push(Node::String(Ann::unannotated(
163 Cow::Owned(value.to_owned())
164 )));
165 self.parameters = Some(args);
166 }
167 pub fn get_parameter(&self, key: &str) -> Option<Ann<Atom<'a>>> {
172 self.parameters
173 .as_ref()
174 .unwrap_or(&Vec::new())
175 .iter()
176 .filter_map(Node::unwrap_string)
177 .find(|x| {
178 let str: &str = &x.data;
179 let str = str
180 .split_once("=")
181 .map(|(x, _)| x)
182 .unwrap_or(str);
183 return str.trim() == key
184 })
185 .map(Clone::clone)
186 }
187 pub fn name(&self) -> &str {
188 &self.name.data
189 }
190 pub fn to_string(&self) -> String {
191 Node::Tag(self.clone()).to_string()
192 }
193 pub fn is_heading_node(&self) -> bool {
194 HEADING_TAG_NAMES.contains(self.name())
195 }
196}
197
198#[derive(Debug, Clone, Default)]
199pub struct NodeEnvironment<'a> {
200 pub parents: Vec<Atom<'a>>,
201}
202
203impl<'a> NodeEnvironment<'a> {
204 pub fn push_parent(&mut self, name: Atom<'a>) {
205 self.parents.push(name)
206 }
207 pub fn is_math_env(&self) -> bool {
208 self.parents
209 .iter()
210 .any(|x| {
211 let option1 = x == INLINE_MATH_TAG;
212 let option2 = BLOCK_MATH_TAGS.iter().any(|y| {
213 x == y
214 });
215 option1 || option2
216 })
217 }
218 pub fn is_default_env(&self) -> bool {
219 !self.is_math_env()
220 }
221}
222
223
224#[derive(Debug, Clone)]
229pub enum Node<'a> {
230 Tag(Tag<'a>),
233 Ident(Ann<Atom<'a>>),
236 Enclosure(Ann<Enclosure<'a, Node<'a>>>),
244 String(Ann<Atom<'a>>),
246 InvalidToken(Ann<Atom<'a>>),
250}
251
252
253impl<'a> Node<'a> {
254 pub fn new_tag(name: Ann<&'a str>, children: Vec<Node<'a>>) -> Self {
256 Node::Tag(Tag::new(name, children))
257 }
258 pub fn new_ident(str: Ann<&'a str>) -> Self {
259 Node::Ident(str.map(|x| Cow::Borrowed(x)))
260 }
261 pub fn new_enclosure(
262 range: CharRange,
263 kind: EnclosureKind<'a>,
264 children: Vec<Node<'a>>,
265 ) -> Self {
266 Node::Enclosure(Ann::new(range, Enclosure {kind, children}))
267 }
268 pub fn new_string(str: Ann<&'a str>) -> Self {
269 Node::Ident(str.map(|x| Cow::Borrowed(x)))
270 }
271 pub fn unannotated_tag(name: &'a str, children: Vec<Node<'a>>) -> Self {
272 Node::Tag(Tag::new(
273 Ann::unannotated(name),
274 children
275 ))
276 }
277 pub fn unannotated_tag_(name: &'a str, child: Node<'a>) -> Self {
278 Node::Tag(Tag::new(
279 Ann::unannotated(name),
280 vec![child]
281 ))
282 }
283 pub fn unannotated_ident(str: &'a str) -> Self {
284 Node::Ident(Ann::unannotated(Cow::Borrowed(str)))
285 }
286 pub fn unannotated_enclosure(
287 kind: EnclosureKind<'a>,
288 children: Vec<Node<'a>>,
289 ) -> Self {
290 Node::Enclosure(Ann::unannotated(Enclosure {kind, children}))
291 }
292 pub fn unannotated_str(str: &'a str) -> Self {
293 Node::String(Ann::unannotated(Cow::Borrowed(str)))
294 }
295 pub fn unannotated_string(str: String) -> Self {
296 Node::String(Ann::unannotated(Cow::Owned(str)))
297 }
298
299 pub fn new_fragment(nodes: Vec<Self>) -> Self {
300 let data = Enclosure {
301 kind: EnclosureKind::Fragment,
302 children: nodes,
303 };
304 Node::Enclosure(Ann::unannotated(data))
305 }
306 pub fn is_whitespace(&self) -> bool {
307 match self {
308 Node::String(txt) => {
309 let x: &str = &txt.data;
310 x.trim().is_empty()
311 },
312 _ => false
313 }
314 }
315 pub fn is_tag(&self) -> bool {
316 match self {
317 Node::Tag(_) => true,
318 _ => false,
319 }
320 }
321 pub fn is_ident(&self) -> bool {
322 match self {
323 Node::Ident(_) => true,
324 _ => false,
325 }
326 }
327 pub fn is_enclosure(&self) -> bool {
328 match self {
329 Node::Enclosure(_) => true,
330 _ => false,
331 }
332 }
333 pub fn is_string(&self) -> bool {
334 match self {
335 Node::String(_) => true,
336 _ => false,
337 }
338 }
339 pub fn is_any_enclosure(&self) -> bool {
340 match self {
341 Node::Enclosure(_) => true,
342 _ => false,
343 }
344 }
345 pub fn is_enclosure_of_kind(&self, k: EnclosureKind) -> bool {
346 match self {
347 Node::Enclosure(Ann{data: Enclosure{kind, ..}, ..}) => {
348 kind == &k
349 },
350 _ => false,
351 }
352 }
353 pub fn is_named_block(&self, name: &str) -> bool {
354 self.unwrap_tag()
355 .map(|x| *x.name.data == *name)
356 .unwrap_or(false)
357 }
358 pub fn get_string(&'a self) -> Option<Ann<Atom<'a>>> {
359 match self {
360 Node::String(cow) => Some(cow.clone()),
361 _ => None,
362 }
363 }
364 pub fn get_enclosure_children(&self, kind: EnclosureKind) -> Option<&Vec<Node<'a>>> {
365 match self {
366 Node::Enclosure(Ann{
367 data: x,
368 ..
369 }) if x.kind == kind => {
370 Some(x.children.as_ref())
371 }
372 _ => None,
373 }
374 }
375 pub fn unblock(self) -> Vec<Self> {
376 match self {
377 Node::Enclosure(
378 Ann{data: block, ..}
379 ) if block.kind == EnclosureKind::CurlyBrace => {
380 block.children
381 }
382 x => vec![x]
383 }
384 }
385 pub fn into_fragment(self) -> Vec<Self> {
388 match self {
389 Node::Enclosure(Ann{
390 data: Enclosure{
391 kind: EnclosureKind::Fragment,
392 children
393 },
394 ..
395 }) => children,
396 x => vec![x]
397 }
398 }
399 pub fn unwrap_tag(&self) -> Option<&Tag<'a>> {
400 match self {
401 Node::Tag(x) => Some(x),
402 _ => None,
403 }
404 }
405 pub fn unwrap_tag_mut(&mut self) -> Option<&mut Tag<'a>> {
406 match self {
407 Node::Tag(x) => Some(x),
408 _ => None,
409 }
410 }
411 pub fn unwrap_ident<'b>(&'b self) -> Option<&'b Ann<Atom<'a>>> {
412 match self {
413 Node::Ident(x) => Some(x),
414 _ => None,
415 }
416 }
417 pub fn unwrap_enclosure<'b>(&'b self) -> Option<&'b Ann<Enclosure<'a, Node<'a>>>> {
418 match self {
419 Node::Enclosure(x) => Some(x),
420 _ => None,
421 }
422 }
423 pub fn unwrap_curly_brace<'b>(&'b self) -> Option<&'b Vec<Node<'a>>> {
424 match self {
425 Node::Enclosure(
426 Ann{data, ..}
427 ) if data.kind == EnclosureKind::CurlyBrace => Some(&data.children),
428 _ => None,
429 }
430 }
431 pub fn unwrap_string<'b>(&'b self) -> Option<&'b Ann<Atom<'a>>> {
432 match self {
433 Node::String(x) => Some(x),
434 _ => None,
435 }
436 }
437 pub fn unwrap_string_mut<'b>(&'b mut self) -> Option<&'b mut Ann<Atom<'a>>> {
438 match self {
439 Node::String(x) => Some(x),
440 _ => None,
441 }
442 }
443 pub fn into_tag(self) -> Option<Tag<'a>> {
444 match self {
445 Node::Tag(x) => Some(x),
446 _ => None,
447 }
448 }
449
450 pub fn transform<F: Fn(NodeEnvironment<'a>, Node<'a>) -> Node<'a>>(
452 self,
453 mut env: NodeEnvironment<'a>, f: Rc<F>
454 ) -> Self {
455 match self {
456 Node::Tag(node) => {
457 env.push_parent(node.name.data.clone());
458 let children = node.children
459 .into_iter()
460 .map(|x| x.transform(env.clone(), f.clone()))
461 .collect();
462 let rewrite_rules = node.rewrite_rules
463 .into_iter()
464 .map(|rule| -> RewriteRule<Node<'a>> {
465 RewriteRule {
466 from: rule.from.transform(env.clone(), f.clone()),
467 to: rule.to.transform(env.clone(), f.clone()),
468 }
469 })
470 .collect();
471 let node = Tag {
472 name: node.name,
473 parameters: node.parameters,
474 children,
475 rewrite_rules,
476 };
477 f(env.clone(), Node::Tag(node))
478 }
479 Node::Enclosure(node) => {
480 let kind = node.data.kind;
481 let range = node.range;
482 let children = node.data.children
483 .into_iter()
484 .map(|x| x.transform(env.clone(), f.clone()))
485 .collect();
486 let data = Enclosure{
487 kind,
488 children,
489 };
490 let node = Node::Enclosure(Ann::join(range, data));
491 f(env.clone(), node)
492 }
493 node @ Node::Ident(_) => {
494 f(env.clone(), node)
495 }
496 node @ Node::String(_) => {
497 f(env.clone(), node)
498 }
499 node @ Node::InvalidToken(_) => {
500 f(env.clone(), node)
501 }
502 }
503 }
504 pub fn transform_mut<F: FnMut(NodeEnvironment<'a>, Node<'a>) -> Node<'a>>(
552 self,
553 mut env: NodeEnvironment<'a>, f: Rc<RefCell<F>>
554 ) -> Self {
555 match self {
556 Node::Tag(node) => {
557 env.push_parent(node.name.data.clone());
558 let children = node.children
559 .into_iter()
560 .map(|x| x.transform_mut(env.clone(), f.clone()))
561 .collect();
562 let rewrite_rules = node.rewrite_rules
563 .into_iter()
564 .map(|rule| -> RewriteRule<Node<'a>> {
565 RewriteRule {
566 from: rule.from.transform_mut(env.clone(), f.clone()),
567 to: rule.to.transform_mut(env.clone(), f.clone()),
568 }
569 })
570 .collect();
571 let node = Tag {
572 name: node.name,
573 parameters: node.parameters,
574 children,
575 rewrite_rules,
576 };
577 (f.borrow_mut())(env.clone(), Node::Tag(node))
578 }
579 Node::Enclosure(node) => {
580 let kind = node.data.kind;
581 let range = node.range;
582 let children = node.data.children
583 .into_iter()
584 .map(|x| x.transform_mut(env.clone(), f.clone()))
585 .collect();
586 let data = Enclosure{
587 kind,
588 children,
589 };
590 let node = Node::Enclosure(Ann::join(range, data));
591 (f.borrow_mut())(env.clone(), node)
592 }
593 node @ Node::Ident(_) => {
594 (f.borrow_mut())(env.clone(), node)
595 }
596 node @ Node::String(_) => {
597 (f.borrow_mut())(env.clone(), node)
598 }
599 node @ Node::InvalidToken(_) => {
600 (f.borrow_mut())(env.clone(), node)
601 }
602 }
603 }
604 pub fn transform_children<F>(
606 self,
607 f: Rc<F>
608 ) -> Self where F: Fn(Vec<Node<'a>>) -> Vec<Node<'a>> {
609 match self {
610 Node::Tag(node) => {
611 let children = node.children
612 .into_iter()
613 .map(|x| -> Node {
614 x.transform_children(f.clone())
615 })
616 .collect::<Vec<_>>();
617 let children = f(children);
618 let rewrite_rules = node.rewrite_rules
619 .into_iter()
620 .map(|rule| -> RewriteRule<Node<'a>> {
621 RewriteRule {
622 from: rule.from.transform_children(f.clone()),
623 to: rule.to.transform_children(f.clone()),
624 }
625 })
626 .collect();
627 let parameters = node.parameters;
628 let node = Tag {
629 name: node.name,
630 parameters,
631 children,
632 rewrite_rules,
633 };
634 Node::Tag(node)
635 }
636 Node::Enclosure(node) => {
637 let range = node.range();
638 let children = node.data.children
639 .into_iter()
640 .map(|x| x.transform_children(f.clone()))
641 .collect();
642 let children = (f)(children);
643 let data = Enclosure{
644 kind: node.data.kind,
645 children,
646 };
647 Node::Enclosure(Ann::join(range, data))
648 }
649 node @ Node::Ident(_) => node,
650 node @ Node::String(_) => node,
651 node @ Node::InvalidToken(_) => node,
652 }
653 }
654 pub fn into_highlight_ranges(
656 self,
657 nesting: Vec<Atom<'a>>,
658 binder: Option<Atom<'a>>,
659 ) -> Vec<Highlight<'a>> {
660 match self {
661 Node::Tag(..) => {
662 unimplemented!()
663 }
664 Node::Enclosure(node) => {
665 let is_fragment = node.data.kind == EnclosureKind::Fragment;
666 let range = node.range;
667 let kind = match node.data.kind {
668 EnclosureKind::CurlyBrace => HighlightKind::CurlyBrace,
669 EnclosureKind::SquareParen => HighlightKind::SquareParen,
670 EnclosureKind::Parens => HighlightKind::Parens,
671 EnclosureKind::Fragment => HighlightKind::Fragment,
672 EnclosureKind::Error{open, close} => HighlightKind::Error{
673 open: open,
674 close: close,
675 },
676 };
677 let mut last_ident: Option<Atom> = None;
678 let mut child_nesting = nesting.clone();
679 if let Some(binder) = binder.clone() {
680 child_nesting.push(binder);
681 }
682 let children = node.data.children
683 .into_iter()
684 .flat_map(|x| {
685 if x.is_ident() {
686 let ident = x.unwrap_ident().unwrap().clone();
687 last_ident = Some(ident.data);
688 }
689 if x.is_string() && !x.is_whitespace() {
690 last_ident = None;
691 }
692 x.into_highlight_ranges(child_nesting.clone(), last_ident.clone())
693 })
694 .collect::<Vec<_>>();
695 let highlight = Highlight {
696 kind,
697 range,
698 binder: binder.clone(),
699 nesting,
700 };
701 if is_fragment {
702 children
703 } else {
704 let mut xs = vec![highlight];
705 xs.extend(children);
706 xs
707 }
708 }
709 Node::Ident(value) => {
710 let range = value.range;
711 let highlight = Highlight {
712 kind: HighlightKind::Ident(value.data),
713 range,
714 binder: binder.clone(),
715 nesting,
716 };
717 vec![highlight]
718 }
719 Node::InvalidToken(value) => {
720 let range = value.range;
721 let highlight = Highlight {
722 kind: HighlightKind::InvalidToken(value.data),
723 range,
724 binder: binder.clone(),
725 nesting,
726 };
727 vec![highlight]
728 }
729 Node::String(value) => Vec::new(),
730 }
731 }
732
733 pub fn to_string(&self) -> String {
734 fn pack<'a>(x: Cow<'a, str>) -> String {
735 match x {
736 Cow::Borrowed(x) => String::from(x),
737 Cow::Owned(x) => x,
738 }
739 }
740 fn ident<'a>(x: Cow<'a, str>) -> String {
741 let mut txt = pack(x);
742 txt.insert(0, '\\');
743 txt
744 }
745 fn enclosure<'a>(
746 start: Atom<'a>,
747 content: String,
748 end: Option<Atom<'a>>,
749 ) -> String {
750 let end = end
751 .map(|x| x.to_string())
752 .unwrap_or(String::new());
753 format!("{}{}{}", start, content, end)
754 }
755 fn enclosure_str<'a>(
756 start: &str,
757 content: String,
758 end: &str,
759 ) -> String {
760 format!("{}{}{}", start, content, end)
761 }
762 match self {
763 Node::Tag(tag) => {
764 let name = pack(tag.name.data.clone());
765 let children = tag.children
766 .iter()
767 .map(|x| x.to_string())
768 .collect::<Vec<_>>()
769 .join("");
770 format!("\\{}{}", name, children)
771 }
772 Node::Enclosure(Ann{data, ..}) => {
773 let children = data.children
774 .iter()
775 .map(|x| x.to_string())
776 .collect::<Vec<_>>()
777 .join("");
778 match data.kind.clone() {
779 EnclosureKind::Fragment => {
780 children
781 }
782 EnclosureKind::CurlyBrace => {
783 enclosure_str("{", children, "}")
784 }
785 EnclosureKind::Parens => {
786 enclosure_str("(", children, ")")
787 }
788 EnclosureKind::SquareParen => {
789 enclosure_str("[", children, "]")
790 }
791 EnclosureKind::Error{open, close} => {
792 enclosure(open, children, close)
793 }
794 }
795 }
796 Node::Ident(x) => ident(x.data.clone()),
797 Node::String(x) => pack(x.data.clone()),
798 Node::InvalidToken(x) => pack(x.data.clone()),
799 }
800 }
801 pub fn syntactically_equal(&self, other: &Self) -> bool {
802 match (self, other) {
803 (Node::Tag(x1), Node::Tag(x2)) => {
804 let check1 = x1.name() == x2.name();
805 let check2 = x1.children.len() == x2.children.len();
806 if check1 && check2 {
807 return x1.children
808 .iter()
809 .zip(x2.children.iter())
810 .all(|(x, y)| {
811 x.syntactically_equal(y)
812 })
813 }
814 false
815 }
816 (Node::Enclosure(x1), Node::Enclosure(x2)) => {
817 let check1 = x1.data.kind == x2.data.kind;
818 let check2 = x1.data.children.len() == x2.data.children.len();
819 if check1 && check2 {
820 return x1.data.children
821 .iter()
822 .zip(x2.data.children.iter())
823 .all(|(x, y)| {
824 x.syntactically_equal(y)
825 })
826 }
827 false
828 }
829 (Node::Ident(x1), Node::Ident(x2)) => {
830 &x1.data == &x2.data
831 }
832 (Node::String(x1), Node::String(x2)) => {
833 &x1.data == &x2.data
834 }
835 (Node::InvalidToken(x1), Node::InvalidToken(x2)) => {
836 &x1.data == &x2.data
837 }
838 (_, _) => unimplemented!()
839 }
840 }
841 pub fn push_child(self, child: Self) -> Self {
844 match self {
845 Node::Enclosure(mut node) if node.data.is_fragment() => {
846 node.data.children.push(child);
847 Node::Enclosure(node)
848 }
849 Node::Tag(mut tag) => {
850 tag.children.push(child);
851 Node::Tag(tag)
852 }
853 x => Node::new_fragment(vec![x, child])
854 }
855 }
856}
857
858
859#[derive(Debug, Clone, Serialize, Deserialize)]
864pub struct Highlight<'a> {
865 pub range: Option<CharRange>,
866 pub kind: HighlightKind<'a>,
867 pub binder: Option<Atom<'a>>,
868 pub nesting: Vec<Atom<'a>>,
869}
870
871#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
872pub enum HighlightKind<'a> {
873 CurlyBrace,
874 SquareParen,
875 Parens,
876 Fragment,
877 Error {
878 open: Atom<'a>,
879 close: Option<Atom<'a>>,
880 },
881 InvalidToken(Atom<'a>),
882 Ident(Atom<'a>),
883}
884