Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_tui/src/lib_tui/term/parse.rs

18.7 KiB, 6 runs

created by r1870400018:20809, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The byte stream state machine.
2//!
3//! A pseudoterminal hands over bytes in whatever sizes the kernel happens to deliver, so the
4//! parser is fed slices of arbitrary length and must survive being cut anywhere: in the middle of
5//! a UTF-8 character, between the `ESC` and the `[` of a control sequence, halfway through a
6//! parameter list. All of the machine's state therefore lives in [`Parser`] and persists between
7//! calls to [`Parser::advance`].
8//!
9//! The structure follows the VT500 parser of Paul Williams, reduced to the states a modern
10//! application actually drives. The rule that matters most is the one about the unrecognised: a
11//! sequence the machine does not understand is consumed to its end and dropped. It is never
12//! allowed to fall through and be printed, which is what produces the familiar screenful of
13//! `[38;5;196m` when a terminal gets this wrong.
14//!
15//! Memory is bounded by construction. Parameters go into a fixed array and further ones are
16//! counted but not stored; a string payload longer than [`MAX_STRING_BYTES`] is dropped while the
17//! scan for its terminator continues, so a runaway sequence costs time but not space. `CAN`, `SUB`
18//! and a fresh `ESC` abandon whatever was in progress.
19
20use oxedyne_fe2o3_core::prelude::*;
21
22
23/// The largest number of parameters a control sequence may carry.
24pub const MAX_PARAMS: usize = 32;
25
26/// The largest value a single parameter may take.
27pub const MAX_PARAM_VALUE: u32 = 65535;
28
29/// The largest string payload, in bytes, that an `OSC` or other string sequence may carry before
30/// the payload is discarded.
31pub const MAX_STRING_BYTES: usize = 8192;
32
33/// The character substituted for a malformed UTF-8 sequence.
34pub const REPLACEMENT: char = '\u{FFFD}';
35
36/// The parameters of a control sequence.
37///
38/// Parameters are separated by `;`. A parameter may itself be subdivided by `:`, which is how the
39/// modern form of the colour selection `38:2::r:g:b` is written; [`Params::is_sub`] reports which
40/// separator preceded a value.
41#[derive(Clone, Copy, Debug)]
42pub struct Params {
43 /// The values, in order.
44 vals: [u32; MAX_PARAMS],
45 /// Whether each value was introduced by `:` rather than `;`.
46 subs: [bool; MAX_PARAMS],
47 /// How many values are held.
48 len: usize,
49 /// Whether the sequence carried more parameters, or a larger value, than can be represented.
50 over: bool,
51}
52
53impl Default for Params {
54 fn default() -> Self {
55 Self {
56 vals: [0; MAX_PARAMS],
57 subs: [false; MAX_PARAMS],
58 len: 0,
59 over: false,
60 }
61 }
62}
63
64impl Params {
65 /// How many parameters were given.
66 pub fn len(&self) -> usize {
67 self.len
68 }
69
70 /// Whether no parameter was given at all.
71 pub fn is_empty(&self) -> bool {
72 self.len == 0
73 }
74
75 /// The parameter at `i`, if it was given.
76 pub fn get(&self, i: usize) -> Option<u32> {
77 if i < self.len {
78 Some(self.vals[i])
79 } else {
80 None
81 }
82 }
83
84 /// The parameter at `i`, or `dflt` if it was absent or written as an empty field.
85 ///
86 /// An empty field and a zero are the same thing to nearly every sequence, which is why they are
87 /// folded together here.
88 pub fn get_or(&self, i: usize, dflt: u32) -> u32 {
89 match self.get(i) {
90 Some(0) | None => dflt,
91 Some(v) => v,
92 }
93 }
94
95 /// Whether the parameter at `i` was introduced by `:` rather than `;`.
96 pub fn is_sub(&self, i: usize) -> bool {
97 i < self.len && self.subs[i]
98 }
99
100 /// Whether the sequence overflowed the representable parameter space.
101 pub fn overflowed(&self) -> bool {
102 self.over
103 }
104
105 /// Starts a value if none has been started, then folds in a decimal digit.
106 fn digit(&mut self, d: u32) {
107 if self.len == 0 {
108 self.push(false);
109 }
110 if self.over {
111 return;
112 }
113 let v = self.vals[self.len - 1] * 10 + d;
114 if v > MAX_PARAM_VALUE {
115 self.over = true;
116 } else {
117 self.vals[self.len - 1] = v;
118 }
119 }
120
121 /// Closes the current value and opens the next.
122 fn separate(&mut self, sub: bool) {
123 if self.len == 0 {
124 self.push(false);
125 }
126 self.push(sub);
127 }
128
129 /// Appends an empty value, noting overflow if there is no room for it.
130 fn push(&mut self, sub: bool) {
131 if self.len >= MAX_PARAMS {
132 self.over = true;
133 return;
134 }
135 self.vals[self.len] = 0;
136 self.subs[self.len] = sub;
137 self.len += 1;
138 }
139}
140
141/// A C0 control the screen acts on.
142#[derive(Clone, Copy, Debug, Eq, PartialEq)]
143pub enum C0 {
144 /// `BEL`, 0x07.
145 Bell,
146 /// `BS`, 0x08.
147 Backspace,
148 /// `HT`, 0x09.
149 Tab,
150 /// `LF`, `VT` or `FF`, 0x0A to 0x0C.
151 LineFeed,
152 /// `CR`, 0x0D.
153 CarriageReturn,
154 /// `SO`, 0x0E, which maps G1 over the printable range.
155 ShiftOut,
156 /// `SI`, 0x0F, which maps G0 over the printable range.
157 ShiftIn,
158}
159
160/// A control sequence introduced by `CSI`.
161#[derive(Clone, Copy, Debug)]
162pub struct Csi {
163 /// The private parameter marker `<`, `=`, `>` or `?`, if one was given.
164 pub private: Option<u8>,
165 /// The intermediate byte in the range 0x20 to 0x2F, if one was given.
166 pub inter: Option<u8>,
167 /// The parameters.
168 pub params: Params,
169 /// The final byte, which names the sequence.
170 pub fin: u8,
171}
172
173/// An escape sequence with no `CSI`.
174#[derive(Clone, Copy, Debug)]
175pub struct Esc {
176 /// The intermediate byte in the range 0x20 to 0x2F, if one was given.
177 pub inter: Option<u8>,
178 /// The final byte.
179 pub fin: u8,
180}
181
182/// An operating system command.
183#[derive(Clone, Debug)]
184pub struct Osc {
185 /// The leading numeric identifier, or `None` if the command did not begin with one.
186 pub ident: Option<u32>,
187 /// Everything after the first `;`.
188 pub text: String,
189}
190
191/// One thing the parser has decided the stream is asking for.
192#[derive(Clone, Debug)]
193pub enum Act {
194 /// A character to place on the screen.
195 Print(char),
196 /// A C0 control.
197 Ctrl(C0),
198 /// A control sequence.
199 Csi(Csi),
200 /// An escape sequence.
201 Esc(Esc),
202 /// An operating system command.
203 Osc(Osc),
204}
205
206/// Where the machine is in the stream.
207#[derive(Clone, Copy, Debug, Eq, PartialEq)]
208enum State {
209 /// Ordinary text.
210 Ground,
211 /// `ESC` has been seen.
212 Escape,
213 /// `ESC` and an intermediate have been seen.
214 EscapeInter,
215 /// `CSI` has been seen and nothing follows it yet.
216 CsiEntry,
217 /// `CSI` parameters are being collected.
218 CsiParam,
219 /// A `CSI` intermediate has been seen.
220 CsiInter,
221 /// The sequence is malformed and is being consumed to its end.
222 CsiIgnore,
223 /// An `OSC` payload is being collected.
224 OscString,
225 /// An `OSC` payload has grown too long and is being consumed to its end.
226 OscIgnore,
227 /// An `ESC` has been seen inside a string payload, which may be the start of `ST`.
228 StringEsc,
229 /// A `DCS`, `SOS`, `PM` or `APC` payload is being consumed to its end.
230 StringIgnore,
231 /// An `ESC` has been seen inside a payload that is already being ignored.
232 StringIgnoreEsc,
233}
234
235/// The byte stream state machine.
236///
237/// Feed it bytes with [`Parser::advance`] and it appends to a caller supplied vector of [`Act`].
238/// The caller owns the vector so that it can be reused between feeds and cost no allocation.
239#[derive(Clone, Debug)]
240pub struct Parser {
241 /// Where the machine is.
242 state: State,
243 /// The private marker of the sequence being collected.
244 private: Option<u8>,
245 /// The intermediate of the sequence being collected.
246 inter: Option<u8>,
247 /// Whether more than one intermediate was seen, which makes the sequence malformed.
248 inter_over: bool,
249 /// The parameters of the sequence being collected.
250 params: Params,
251 /// The payload of the string sequence being collected.
252 string: Vec<u8>,
253 /// The partial UTF-8 character held over from an earlier feed.
254 utf8: [u8; 4],
255 /// How many bytes of the partial character are held.
256 utf8_len: usize,
257 /// How many bytes the partial character needs in total.
258 utf8_need: usize,
259}
260
261impl Default for Parser {
262 fn default() -> Self {
263 Self::new()
264 }
265}
266
267impl Parser {
268
269 /// A parser at the start of a stream.
270 pub fn new() -> Self {
271 Self {
272 state: State::Ground,
273 private: None,
274 inter: None,
275 inter_over: false,
276 params: Params::default(),
277 string: Vec::new(),
278 utf8: [0; 4],
279 utf8_len: 0,
280 utf8_need: 0,
281 }
282 }
283
284 /// Returns the machine to the start of a stream, discarding anything half collected.
285 pub fn reset(&mut self) {
286 *self = Self::new();
287 }
288
289 /// Whether a character or sequence is half collected, waiting on more bytes.
290 pub fn is_partial(&self) -> bool {
291 self.state != State::Ground || self.utf8_len > 0
292 }
293
294 /// Consumes `bytes`, appending what they ask for to `out`.
295 pub fn advance(&mut self, bytes: &[u8], out: &mut Vec<Act>) {
296 for b in bytes {
297 self.byte(*b, out);
298 }
299 }
300
301 /// Consumes one byte.
302 fn byte(&mut self, b: u8, out: &mut Vec<Act>) {
303 match self.state {
304 State::Ground => self.ground(b, out),
305 State::Escape => self.escape(b, out),
306 State::EscapeInter => self.escape_inter(b, out),
307 State::CsiEntry => self.csi_entry(b, out),
308 State::CsiParam => self.csi_param(b, out),
309 State::CsiInter => self.csi_inter(b, out),
310 State::CsiIgnore => self.csi_ignore(b, out),
311 State::OscString => self.osc_string(b, out),
312 State::OscIgnore => self.osc_ignore(b, out),
313 State::StringEsc => self.string_esc(b, out),
314 State::StringIgnore => self.string_ignore(b, out),
315 State::StringIgnoreEsc => self.string_ignore_esc(b, out),
316 }
317 }
318
319 // ┌─────────────────────────────┐
320 // │ GROUND │
321 // └─────────────────────────────┘
322
323 /// Ordinary text, where UTF-8 is decoded and C0 controls are acted on.
324 fn ground(&mut self, b: u8, out: &mut Vec<Act>) {
325 if self.utf8_len > 0 {
326 // A character is part collected. Only a continuation byte may follow.
327 if b & 0xC0 == 0x80 {
328 self.utf8[self.utf8_len] = b;
329 self.utf8_len += 1;
330 if self.utf8_len == self.utf8_need {
331 self.emit_utf8(out);
332 }
333 return;
334 }
335 // Anything else truncates the character.
336 out.push(Act::Print(REPLACEMENT));
337 self.utf8_len = 0;
338 self.utf8_need = 0;
339 // Fall through and reconsider this byte as a fresh one.
340 }
341 if b < 0x20 || b == 0x7F {
342 self.control(b, out);
343 return;
344 }
345 if b < 0x80 {
346 out.push(Act::Print(b as char));
347 return;
348 }
349 // A UTF-8 lead byte, or a stray continuation byte.
350 let need = if b & 0xE0 == 0xC0 {
351 2
352 } else if b & 0xF0 == 0xE0 {
353 3
354 } else if b & 0xF8 == 0xF0 {
355 4
356 } else {
357 out.push(Act::Print(REPLACEMENT));
358 return;
359 };
360 self.utf8[0] = b;
361 self.utf8_len = 1;
362 self.utf8_need = need;
363 }
364
365 /// Turns the held bytes into a character, or into a replacement if they are not valid.
366 fn emit_utf8(&mut self, out: &mut Vec<Act>) {
367 let c = match std::str::from_utf8(&self.utf8[..self.utf8_len]) {
368 Ok(s) => match s.chars().next() {
369 Some(c) => c,
370 None => REPLACEMENT,
371 },
372 Err(_) => REPLACEMENT,
373 };
374 out.push(Act::Print(c));
375 self.utf8_len = 0;
376 self.utf8_need = 0;
377 }
378
379 /// Acts on a C0 control byte, wherever in the stream it appears.
380 fn control(&mut self, b: u8, out: &mut Vec<Act>) {
381 match b {
382 0x07 => out.push(Act::Ctrl(C0::Bell)),
383 0x08 => out.push(Act::Ctrl(C0::Backspace)),
384 0x09 => out.push(Act::Ctrl(C0::Tab)),
385 0x0A | 0x0B | 0x0C => out.push(Act::Ctrl(C0::LineFeed)),
386 0x0D => out.push(Act::Ctrl(C0::CarriageReturn)),
387 0x0E => out.push(Act::Ctrl(C0::ShiftOut)),
388 0x0F => out.push(Act::Ctrl(C0::ShiftIn)),
389 0x18 | 0x1A => self.abandon(),
390 0x1B => self.begin_escape(),
391 // Everything else is consumed without effect.
392 _ => {}
393 }
394 }
395
396 /// Drops whatever sequence is in progress and returns to ordinary text.
397 fn abandon(&mut self) {
398 self.state = State::Ground;
399 self.private = None;
400 self.inter = None;
401 self.inter_over = false;
402 self.params = Params::default();
403 self.string.clear();
404 }
405
406 /// Starts a fresh escape sequence, dropping anything already in progress.
407 fn begin_escape(&mut self) {
408 self.abandon();
409 self.state = State::Escape;
410 }
411
412 // ┌─────────────────────────────┐
413 // │ ESCAPE │
414 // └─────────────────────────────┘
415
416 /// Immediately after `ESC`.
417 fn escape(&mut self, b: u8, out: &mut Vec<Act>) {
418 match b {
419 0x00..=0x17 | 0x19 | 0x1C..=0x1F => self.control(b, out),
420 0x18 | 0x1A => self.abandon(),
421 0x1B => self.begin_escape(),
422 0x20..=0x2F => {
423 self.inter = Some(b);
424 self.state = State::EscapeInter;
425 }
426 0x5B => {
427 // CSI.
428 self.state = State::CsiEntry;
429 }
430 0x5D => {
431 // OSC.
432 self.string.clear();
433 self.state = State::OscString;
434 }
435 0x50 | 0x58 | 0x5E | 0x5F => {
436 // DCS, SOS, PM and APC, none of which the screen model acts on.
437 self.state = State::StringIgnore;
438 }
439 _ => {
440 out.push(Act::Esc(Esc { inter: None, fin: b }));
441 self.state = State::Ground;
442 }
443 }
444 }
445
446 /// After `ESC` and one intermediate, as in `ESC # 8`.
447 fn escape_inter(&mut self, b: u8, out: &mut Vec<Act>) {
448 match b {
449 0x00..=0x17 | 0x19 | 0x1C..=0x1F => self.control(b, out),
450 0x18 | 0x1A => self.abandon(),
451 0x1B => self.begin_escape(),
452 // A second intermediate is collected but not stored; the sequence is still consumed.
453 0x20..=0x2F => self.inter_over = true,
454 _ => {
455 if !self.inter_over {
456 out.push(Act::Esc(Esc { inter: self.inter, fin: b }));
457 }
458 self.abandon();
459 }
460 }
461 }
462
463 // ┌─────────────────────────────┐
464 // │ CSI │
465 // └─────────────────────────────┘
466
467 /// Immediately after `CSI`, where a private marker may still appear.
468 fn csi_entry(&mut self, b: u8, out: &mut Vec<Act>) {
469 match b {
470 0x00..=0x17 | 0x19 | 0x1C..=0x1F => self.control(b, out),
471 0x18 | 0x1A => self.abandon(),
472 0x1B => self.begin_escape(),
473 0x3C..=0x3F => {
474 self.private = Some(b);
475 self.state = State::CsiParam;
476 }
477 0x30..=0x39 => {
478 self.params.digit((b - 0x30) as u32);
479 self.state = State::CsiParam;
480 }
481 0x3A => {
482 self.params.separate(true);
483 self.state = State::CsiParam;
484 }
485 0x3B => {
486 self.params.separate(false);
487 self.state = State::CsiParam;
488 }
489 0x20..=0x2F => {
490 self.inter = Some(b);
491 self.state = State::CsiInter;
492 }
493 0x40..=0x7E => self.dispatch_csi(b, out),
494 _ => self.state = State::CsiIgnore,
495 }
496 }
497
498 /// Collecting `CSI` parameters.
499 fn csi_param(&mut self, b: u8, out: &mut Vec<Act>) {
500 match b {
501 0x00..=0x17 | 0x19 | 0x1C..=0x1F => self.control(b, out),
502 0x18 | 0x1A => self.abandon(),
503 0x1B => self.begin_escape(),
504 0x30..=0x39 => self.params.digit((b - 0x30) as u32),
505 0x3A => self.params.separate(true),
506 0x3B => self.params.separate(false),
507 // A private marker after the parameters have started is malformed.
508 0x3C..=0x3F => self.state = State::CsiIgnore,
509 0x20..=0x2F => {
510 self.inter = Some(b);
511 self.state = State::CsiInter;
512 }
513 0x40..=0x7E => self.dispatch_csi(b, out),
514 _ => self.state = State::CsiIgnore,
515 }
516 }
517
518 /// After a `CSI` intermediate, where no further parameter may appear.
519 fn csi_inter(&mut self, b: u8, out: &mut Vec<Act>) {
520 match b {
521 0x00..=0x17 | 0x19 | 0x1C..=0x1F => self.control(b, out),
522 0x18 | 0x1A => self.abandon(),
523 0x1B => self.begin_escape(),
524 0x20..=0x2F => self.inter_over = true,
525 0x30..=0x3F => self.state = State::CsiIgnore,
526 0x40..=0x7E => self.dispatch_csi(b, out),
527 _ => self.state = State::CsiIgnore,
528 }
529 }
530
531 /// Consuming a malformed `CSI` to its end.
532 fn csi_ignore(&mut self, b: u8, out: &mut Vec<Act>) {
533 match b {
534 0x00..=0x17 | 0x19 | 0x1C..=0x1F => self.control(b, out),
535 0x18 | 0x1A => self.abandon(),
536 0x1B => self.begin_escape(),
537 0x40..=0x7E => self.abandon(),
538 _ => {}
539 }
540 }
541
542 /// Hands a completed `CSI` to the caller, unless it was malformed.
543 ///
544 /// A sequence whose parameters overflowed is dropped rather than acted on with clamped values.
545 /// A terminal that clamps `CSI 99999999999 ; 1 H` moves the cursor somewhere the sender never
546 /// asked for; dropping it leaves the screen alone, which is what tmux and xterm do.
547 fn dispatch_csi(&mut self, fin: u8, out: &mut Vec<Act>) {
548 if !self.params.overflowed() && !self.inter_over {
549 out.push(Act::Csi(Csi {
550 private: self.private,
551 inter: self.inter,
552 params: self.params,
553 fin,
554 }));
555 }
556 self.abandon();
557 }
558
559 // ┌─────────────────────────────┐
560 // │ STRING PAYLOADS │
561 // └─────────────────────────────┘
562
563 /// Collecting an `OSC` payload.
564 fn osc_string(&mut self, b: u8, out: &mut Vec<Act>) {
565 match b {
566 0x07 => {
567 self.dispatch_osc(out);
568 self.state = State::Ground;
569 }
570 0x1B => self.state = State::StringEsc,
571 0x18 | 0x1A => self.abandon(),
572 // Other C0 controls end the payload without dispatching it and are then acted on,
573 // which is how a stream that lost its terminator recovers at the next line break
574 // instead of swallowing everything after it.
575 0x00..=0x06 | 0x08..=0x17 | 0x19 | 0x1C..=0x1F => {
576 self.abandon();
577 self.control(b, out);
578 }
579 _ => {
580 if self.string.len() >= MAX_STRING_BYTES {
581 // Too long to be a command anyone meant. Keep scanning for the
582 // terminator, but store nothing more.
583 self.string.clear();
584 self.state = State::OscIgnore;
585 } else {
586 self.string.push(b);
587 }
588 }
589 }
590 }
591
592 /// Consuming an over long `OSC` to its end.
593 fn osc_ignore(&mut self, b: u8, out: &mut Vec<Act>) {
594 match b {
595 0x07 => self.abandon(),
596 0x1B => self.state = State::StringIgnoreEsc,
597 0x18 | 0x1A => self.abandon(),
598 0x00..=0x06 | 0x08..=0x17 | 0x19 | 0x1C..=0x1F => {
599 self.abandon();
600 self.control(b, out);
601 }
602 _ => {}
603 }
604 }
605
606 /// An `ESC` inside an `OSC` payload, which is `ST` if a backslash follows.
607 fn string_esc(&mut self, b: u8, out: &mut Vec<Act>) {
608 if b == 0x5C {
609 self.dispatch_osc(out);
610 self.state = State::Ground;
611 } else {
612 // Not a terminator, so the payload is over and a new escape sequence has begun.
613 self.dispatch_osc(out);
614 self.begin_escape();
615 self.escape(b, out);
616 }
617 }
618
619 /// Consuming a `DCS`, `SOS`, `PM` or `APC` payload to its end.
620 fn string_ignore(&mut self, b: u8, _out: &mut Vec<Act>) {
621 match b {
622 0x1B => self.state = State::StringIgnoreEsc,
623 0x18 | 0x1A => self.abandon(),
624 _ => {}
625 }
626 }
627
628 /// An `ESC` inside a payload that is being ignored.
629 fn string_ignore_esc(&mut self, b: u8, out: &mut Vec<Act>) {
630 if b == 0x5C {
631 self.abandon();
632 } else {
633 self.begin_escape();
634 self.escape(b, out);
635 }
636 }
637
638 /// Splits a collected `OSC` payload into its identifier and its text, and hands it over.
639 fn dispatch_osc(&mut self, out: &mut Vec<Act>) {
640 let raw = String::from_utf8_lossy(&self.string).into_owned();
641 self.string.clear();
642 let (ident, text) = match raw.find(';') {
643 Some(i) => {
644 let head = &raw[..i];
645 let tail = &raw[i + 1..];
646 (head.parse::<u32>().ok(), tail.to_string())
647 }
648 None => (raw.parse::<u32>().ok(), fmt!("")),
649 };
650 out.push(Act::Osc(Osc { ident, text }));
651 }
652}