1// Copyright 2019 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! Parameterized string expansion
12
13use self::Param::*;
14use self::States::*;
15
16use std::iter::repeat;
17
18#[derive(Clone, Copy, PartialEq)]
19enum States {
20 Nothing,
21 Delay,
22 Percent,
23 SetVar,
24 GetVar,
25 PushParam,
26 CharConstant,
27 CharClose,
28 IntConstant(i32),
29 FormatPattern(Flags, FormatState),
30 SeekIfElse(usize),
31 SeekIfElsePercent(usize),
32 SeekIfEnd(usize),
33 SeekIfEndPercent(usize),
34}
35
36#[derive(Copy, PartialEq, Clone)]
37enum FormatState {
38 Flags,
39 Width,
40 Precision,
41}
42
43/// Types of parameters a capability can use
44#[allow(missing_docs)]
45#[derive(Clone)]
46pub enum Param {
47 Number(i32),
48 Words(String),
49}
50
51impl Default for Param {
52 fn default() -> Self {
53 Param::Number(0)
54 }
55}
56
57/// An error from interpreting a parameterized string.
58#[derive(Debug, Eq, PartialEq)]
59pub enum Error {
60 /// Data was requested from the stack, but the stack didn't have enough elements.
61 StackUnderflow,
62 /// The type of the element(s) on top of the stack did not match the type that the operator
63 /// wanted.
64 TypeMismatch,
65 /// An unrecognized format option was used.
66 UnrecognizedFormatOption(char),
67 /// An invalid variable name was used.
68 InvalidVariableName(char),
69 /// An invalid parameter index was used.
70 InvalidParameterIndex(char),
71 /// A malformed character constant was used.
72 MalformedCharacterConstant,
73 /// An integer constant was too large (overflowed an i32)
74 IntegerConstantOverflow,
75 /// A malformed integer constant was used.
76 MalformedIntegerConstant,
77 /// A format width constant was too large (overflowed a usize)
78 FormatWidthOverflow,
79 /// A format precision constant was too large (overflowed a usize)
80 FormatPrecisionOverflow,
81}
82
83impl ::std::fmt::Display for Error {
84 fn fmt(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
85 use self::Error::*;
86 match *self {
87 StackUnderflow => f.write_str(data:"not enough elements on the stack"),
88 TypeMismatch => f.write_str(data:"type mismatch"),
89 UnrecognizedFormatOption(_) => f.write_str(data:"unrecognized format option"),
90 InvalidVariableName(_) => f.write_str(data:"invalid variable name"),
91 InvalidParameterIndex(_) => f.write_str(data:"invalid parameter index"),
92 MalformedCharacterConstant => f.write_str(data:"malformed character constant"),
93 IntegerConstantOverflow => f.write_str(data:"integer constant computation overflowed"),
94 MalformedIntegerConstant => f.write_str(data:"malformed integer constant"),
95 FormatWidthOverflow => f.write_str(data:"format width constant computation overflowed"),
96 FormatPrecisionOverflow => {
97 f.write_str(data:"format precision constant computation overflowed")
98 }
99 }
100 }
101}
102
103impl ::std::error::Error for Error {}
104
105/// Container for static and dynamic variable arrays
106#[derive(Default)]
107pub struct Variables {
108 /// Static variables A-Z
109 sta_vars: [Param; 26],
110 /// Dynamic variables a-z
111 dyn_vars: [Param; 26],
112}
113
114impl Variables {
115 /// Return a new zero-initialized Variables
116 pub fn new() -> Variables {
117 Default::default()
118 }
119}
120
121/// Expand a parameterized capability
122///
123/// # Arguments
124/// * `cap` - string to expand
125/// * `params` - vector of params for %p1 etc
126/// * `vars` - Variables struct for %Pa etc
127///
128/// To be compatible with ncurses, `vars` should be the same between calls to `expand` for
129/// multiple capabilities for the same terminal.
130pub fn expand(cap: &[u8], params: &[Param], vars: &mut Variables) -> Result<Vec<u8>, Error> {
131 let mut state = Nothing;
132
133 // expanded cap will only rarely be larger than the cap itself
134 let mut output = Vec::with_capacity(cap.len());
135
136 let mut stack: Vec<Param> = Vec::new();
137
138 // Copy parameters into a local vector for mutability
139 let mut mparams = [
140 Number(0),
141 Number(0),
142 Number(0),
143 Number(0),
144 Number(0),
145 Number(0),
146 Number(0),
147 Number(0),
148 Number(0),
149 ];
150 for (dst, src) in mparams.iter_mut().zip(params.iter()) {
151 *dst = (*src).clone();
152 }
153
154 for &c in cap.iter() {
155 let cur = c as char;
156 let mut old_state = state;
157 match state {
158 Nothing => {
159 if cur == '%' {
160 state = Percent;
161 } else if cur == '$' {
162 state = Delay;
163 } else {
164 output.push(c);
165 }
166 }
167 Delay => {
168 old_state = Nothing;
169 if cur == '>' {
170 state = Nothing;
171 }
172 }
173 Percent => {
174 match cur {
175 '%' => {
176 output.push(c);
177 state = Nothing
178 }
179 'c' => {
180 match stack.pop() {
181 // if c is 0, use 0200 (128) for ncurses compatibility
182 Some(Number(0)) => output.push(128u8),
183 // Don't check bounds. ncurses just casts and truncates.
184 Some(Number(c)) => output.push(c as u8),
185 Some(_) => return Err(Error::TypeMismatch),
186 None => return Err(Error::StackUnderflow),
187 }
188 }
189 'p' => state = PushParam,
190 'P' => state = SetVar,
191 'g' => state = GetVar,
192 '\'' => state = CharConstant,
193 '{' => state = IntConstant(0),
194 'l' => match stack.pop() {
195 Some(Words(s)) => stack.push(Number(s.len() as i32)),
196 Some(_) => return Err(Error::TypeMismatch),
197 None => return Err(Error::StackUnderflow),
198 },
199 '+' | '-' | '/' | '*' | '^' | '&' | '|' | 'm' => {
200 match (stack.pop(), stack.pop()) {
201 (Some(Number(y)), Some(Number(x))) => stack.push(Number(match cur {
202 '+' => x + y,
203 '-' => x - y,
204 '*' => x * y,
205 '/' => x / y,
206 '|' => x | y,
207 '&' => x & y,
208 '^' => x ^ y,
209 'm' => x % y,
210 _ => unreachable!("logic error"),
211 })),
212 (Some(_), Some(_)) => return Err(Error::TypeMismatch),
213 _ => return Err(Error::StackUnderflow),
214 }
215 }
216 '=' | '>' | '<' | 'A' | 'O' => match (stack.pop(), stack.pop()) {
217 (Some(Number(y)), Some(Number(x))) => stack.push(Number(
218 if match cur {
219 '=' => x == y,
220 '<' => x < y,
221 '>' => x > y,
222 'A' => x > 0 && y > 0,
223 'O' => x > 0 || y > 0,
224 _ => unreachable!("logic error"),
225 } {
226 1
227 } else {
228 0
229 },
230 )),
231 (Some(_), Some(_)) => return Err(Error::TypeMismatch),
232 _ => return Err(Error::StackUnderflow),
233 },
234 '!' | '~' => match stack.pop() {
235 Some(Number(x)) => stack.push(Number(match cur {
236 '!' if x > 0 => 0,
237 '!' => 1,
238 '~' => !x,
239 _ => unreachable!("logic error"),
240 })),
241 Some(_) => return Err(Error::TypeMismatch),
242 None => return Err(Error::StackUnderflow),
243 },
244 'i' => match (&mparams[0], &mparams[1]) {
245 (&Number(x), &Number(y)) => {
246 mparams[0] = Number(x + 1);
247 mparams[1] = Number(y + 1);
248 }
249 (_, _) => return Err(Error::TypeMismatch),
250 },
251
252 // printf-style support for %doxXs
253 'd' | 'o' | 'x' | 'X' | 's' => {
254 if let Some(arg) = stack.pop() {
255 let flags = Flags::default();
256 let res = format(arg, FormatOp::from_char(cur), flags)?;
257 output.extend(res);
258 } else {
259 return Err(Error::StackUnderflow);
260 }
261 }
262 ':' | '#' | ' ' | '.' | '0'..='9' => {
263 let mut flags = Flags::default();
264 let mut fstate = FormatState::Flags;
265 match cur {
266 ':' => (),
267 '#' => flags.alternate = true,
268 ' ' => flags.space = true,
269 '.' => fstate = FormatState::Precision,
270 '0'..='9' => {
271 flags.width = cur as usize - '0' as usize;
272 fstate = FormatState::Width;
273 }
274 _ => unreachable!("logic error"),
275 }
276 state = FormatPattern(flags, fstate);
277 }
278
279 // conditionals
280 '?' | ';' => (),
281 't' => match stack.pop() {
282 Some(Number(0)) => state = SeekIfElse(0),
283 Some(Number(_)) => (),
284 Some(_) => return Err(Error::TypeMismatch),
285 None => return Err(Error::StackUnderflow),
286 },
287 'e' => state = SeekIfEnd(0),
288 c => return Err(Error::UnrecognizedFormatOption(c)),
289 }
290 }
291 PushParam => {
292 // params are 1-indexed
293 stack.push(
294 mparams[match cur.to_digit(10) {
295 Some(d) => d as usize - 1,
296 None => return Err(Error::InvalidParameterIndex(cur)),
297 }]
298 .clone(),
299 );
300 }
301 SetVar => {
302 if cur >= 'A' && cur <= 'Z' {
303 if let Some(arg) = stack.pop() {
304 let idx = (cur as u8) - b'A';
305 vars.sta_vars[idx as usize] = arg;
306 } else {
307 return Err(Error::StackUnderflow);
308 }
309 } else if cur >= 'a' && cur <= 'z' {
310 if let Some(arg) = stack.pop() {
311 let idx = (cur as u8) - b'a';
312 vars.dyn_vars[idx as usize] = arg;
313 } else {
314 return Err(Error::StackUnderflow);
315 }
316 } else {
317 return Err(Error::InvalidVariableName(cur));
318 }
319 }
320 GetVar => {
321 if cur >= 'A' && cur <= 'Z' {
322 let idx = (cur as u8) - b'A';
323 stack.push(vars.sta_vars[idx as usize].clone());
324 } else if cur >= 'a' && cur <= 'z' {
325 let idx = (cur as u8) - b'a';
326 stack.push(vars.dyn_vars[idx as usize].clone());
327 } else {
328 return Err(Error::InvalidVariableName(cur));
329 }
330 }
331 CharConstant => {
332 stack.push(Number(i32::from(c)));
333 state = CharClose;
334 }
335 CharClose => {
336 if cur != '\'' {
337 return Err(Error::MalformedCharacterConstant);
338 }
339 }
340 IntConstant(i) => {
341 if cur == '}' {
342 stack.push(Number(i));
343 state = Nothing;
344 } else if let Some(digit) = cur.to_digit(10) {
345 match i
346 .checked_mul(10)
347 .and_then(|i_ten| i_ten.checked_add(digit as i32))
348 {
349 Some(i) => {
350 state = IntConstant(i);
351 old_state = Nothing;
352 }
353 None => return Err(Error::IntegerConstantOverflow),
354 }
355 } else {
356 return Err(Error::MalformedIntegerConstant);
357 }
358 }
359 FormatPattern(ref mut flags, ref mut fstate) => {
360 old_state = Nothing;
361 match (*fstate, cur) {
362 (_, 'd') | (_, 'o') | (_, 'x') | (_, 'X') | (_, 's') => {
363 if let Some(arg) = stack.pop() {
364 let res = format(arg, FormatOp::from_char(cur), *flags)?;
365 output.extend(res);
366 // will cause state to go to Nothing
367 old_state = FormatPattern(*flags, *fstate);
368 } else {
369 return Err(Error::StackUnderflow);
370 }
371 }
372 (FormatState::Flags, '#') => {
373 flags.alternate = true;
374 }
375 (FormatState::Flags, '-') => {
376 flags.left = true;
377 }
378 (FormatState::Flags, '+') => {
379 flags.sign = true;
380 }
381 (FormatState::Flags, ' ') => {
382 flags.space = true;
383 }
384 (FormatState::Flags, '0'..='9') => {
385 flags.width = cur as usize - '0' as usize;
386 *fstate = FormatState::Width;
387 }
388 (FormatState::Width, '0'..='9') => {
389 flags.width = match flags
390 .width
391 .checked_mul(10)
392 .and_then(|w| w.checked_add(cur as usize - '0' as usize))
393 {
394 Some(width) => width,
395 None => return Err(Error::FormatWidthOverflow),
396 }
397 }
398 (FormatState::Width, '.') | (FormatState::Flags, '.') => {
399 *fstate = FormatState::Precision;
400 }
401 (FormatState::Precision, '0'..='9') => {
402 flags.precision = match flags
403 .precision
404 .checked_mul(10)
405 .and_then(|w| w.checked_add(cur as usize - '0' as usize))
406 {
407 Some(precision) => precision,
408 None => return Err(Error::FormatPrecisionOverflow),
409 }
410 }
411 _ => return Err(Error::UnrecognizedFormatOption(cur)),
412 }
413 }
414 SeekIfElse(level) => {
415 if cur == '%' {
416 state = SeekIfElsePercent(level);
417 }
418 old_state = Nothing;
419 }
420 SeekIfElsePercent(level) => {
421 if cur == ';' {
422 if level == 0 {
423 state = Nothing;
424 } else {
425 state = SeekIfElse(level - 1);
426 }
427 } else if cur == 'e' && level == 0 {
428 state = Nothing;
429 } else if cur == '?' {
430 state = SeekIfElse(level + 1);
431 } else {
432 state = SeekIfElse(level);
433 }
434 }
435 SeekIfEnd(level) => {
436 if cur == '%' {
437 state = SeekIfEndPercent(level);
438 }
439 old_state = Nothing;
440 }
441 SeekIfEndPercent(level) => {
442 if cur == ';' {
443 if level == 0 {
444 state = Nothing;
445 } else {
446 state = SeekIfEnd(level - 1);
447 }
448 } else if cur == '?' {
449 state = SeekIfEnd(level + 1);
450 } else {
451 state = SeekIfEnd(level);
452 }
453 }
454 }
455 if state == old_state {
456 state = Nothing;
457 }
458 }
459 Ok(output)
460}
461
462#[derive(Copy, PartialEq, Clone, Default)]
463struct Flags {
464 width: usize,
465 precision: usize,
466 alternate: bool,
467 left: bool,
468 sign: bool,
469 space: bool,
470}
471
472#[derive(Copy, Clone)]
473enum FormatOp {
474 Digit,
475 Octal,
476 Hex,
477 HEX,
478 String,
479}
480
481impl FormatOp {
482 fn from_char(c: char) -> FormatOp {
483 use self::FormatOp::*;
484 match c {
485 'd' => Digit,
486 'o' => Octal,
487 'x' => Hex,
488 'X' => HEX,
489 's' => String,
490 _ => panic!("bad FormatOp char"),
491 }
492 }
493}
494
495fn format(val: Param, op: FormatOp, flags: Flags) -> Result<Vec<u8>, Error> {
496 use self::FormatOp::*;
497 let mut s = match val {
498 Number(d) => {
499 match op {
500 Digit => {
501 if flags.sign {
502 format!("{:+01$}", d, flags.precision)
503 } else if d < 0 {
504 // C doesn't take sign into account in precision calculation.
505 format!("{:01$}", d, flags.precision + 1)
506 } else if flags.space {
507 format!(" {:01$}", d, flags.precision)
508 } else {
509 format!("{:01$}", d, flags.precision)
510 }
511 }
512 Octal => {
513 if flags.alternate {
514 // Leading octal zero counts against precision.
515 format!("0{:01$o}", d, flags.precision.saturating_sub(1))
516 } else {
517 format!("{:01$o}", d, flags.precision)
518 }
519 }
520 Hex => {
521 if flags.alternate && d != 0 {
522 format!("0x{:01$x}", d, flags.precision)
523 } else {
524 format!("{:01$x}", d, flags.precision)
525 }
526 }
527 HEX => {
528 if flags.alternate && d != 0 {
529 format!("0X{:01$X}", d, flags.precision)
530 } else {
531 format!("{:01$X}", d, flags.precision)
532 }
533 }
534 String => return Err(Error::TypeMismatch),
535 }
536 .into_bytes()
537 }
538 Words(s) => match op {
539 String => {
540 let mut s = s.into_bytes();
541 if flags.precision > 0 && flags.precision < s.len() {
542 s.truncate(flags.precision);
543 }
544 s
545 }
546 _ => return Err(Error::TypeMismatch),
547 },
548 };
549 if flags.width > s.len() {
550 let n = flags.width - s.len();
551 if flags.left {
552 s.extend(repeat(b' ').take(n));
553 } else {
554 let mut s_ = Vec::with_capacity(flags.width);
555 s_.extend(repeat(b' ').take(n));
556 s_.extend(s.into_iter());
557 s = s_;
558 }
559 }
560 Ok(s)
561}
562
563#[cfg(test)]
564mod test {
565 use super::Param::{self, Number, Words};
566 use super::{expand, Variables};
567 use std::result::Result::Ok;
568
569 #[test]
570 fn test_basic_setabf() {
571 let s = b"\\E[48;5;%p1%dm";
572 assert_eq!(
573 expand(s, &[Number(1)], &mut Variables::new()).unwrap(),
574 "\\E[48;5;1m".bytes().collect::<Vec<_>>()
575 );
576 }
577
578 #[test]
579 fn test_multiple_int_constants() {
580 assert_eq!(
581 expand(b"%{1}%{2}%d%d", &[], &mut Variables::new()).unwrap(),
582 "21".bytes().collect::<Vec<_>>()
583 );
584 }
585
586 #[test]
587 fn test_op_i() {
588 let mut vars = Variables::new();
589 assert_eq!(
590 expand(
591 b"%p1%d%p2%d%p3%d%i%p1%d%p2%d%p3%d",
592 &[Number(1), Number(2), Number(3)],
593 &mut vars
594 ),
595 Ok("123233".bytes().collect::<Vec<_>>())
596 );
597 assert_eq!(
598 expand(b"%p1%d%p2%d%i%p1%d%p2%d", &[], &mut vars),
599 Ok("0011".bytes().collect::<Vec<_>>())
600 );
601 }
602
603 #[test]
604 fn test_param_stack_failure_conditions() {
605 let mut varstruct = Variables::new();
606 let vars = &mut varstruct;
607 fn get_res(
608 fmt: &str,
609 cap: &str,
610 params: &[Param],
611 vars: &mut Variables,
612 ) -> Result<Vec<u8>, super::Error> {
613 let mut u8v: Vec<_> = fmt.bytes().collect();
614 u8v.extend(cap.as_bytes().iter().cloned());
615 expand(&u8v, params, vars)
616 }
617
618 let caps = ["%d", "%c", "%s", "%Pa", "%l", "%!", "%~"];
619 for &cap in &caps {
620 let res = get_res("", cap, &[], vars);
621 assert!(
622 res.is_err(),
623 "Op {} succeeded incorrectly with 0 stack entries",
624 cap
625 );
626 let p = if cap == "%s" || cap == "%l" {
627 Words("foo".to_owned())
628 } else {
629 Number(97)
630 };
631 let res = get_res("%p1", cap, &[p], vars);
632 assert!(
633 res.is_ok(),
634 "Op {} failed with 1 stack entry: {}",
635 cap,
636 res.err().unwrap()
637 );
638 }
639 let caps = ["%+", "%-", "%*", "%/", "%m", "%&", "%|", "%A", "%O"];
640 for &cap in &caps {
641 let res = expand(cap.as_bytes(), &[], vars);
642 assert!(
643 res.is_err(),
644 "Binop {} succeeded incorrectly with 0 stack entries",
645 cap
646 );
647 let res = get_res("%{1}", cap, &[], vars);
648 assert!(
649 res.is_err(),
650 "Binop {} succeeded incorrectly with 1 stack entry",
651 cap
652 );
653 let res = get_res("%{1}%{2}", cap, &[], vars);
654 assert!(
655 res.is_ok(),
656 "Binop {} failed with 2 stack entries: {}",
657 cap,
658 res.err().unwrap()
659 );
660 }
661 }
662
663 #[test]
664 fn test_push_bad_param() {
665 assert!(expand(b"%pa", &[], &mut Variables::new()).is_err());
666 }
667
668 #[test]
669 fn test_comparison_ops() {
670 let v = [
671 ('<', [1u8, 0u8, 0u8]),
672 ('=', [0u8, 1u8, 0u8]),
673 ('>', [0u8, 0u8, 1u8]),
674 ];
675 for &(op, bs) in &v {
676 let s = format!("%{{1}}%{{2}}%{}%d", op);
677 let res = expand(s.as_bytes(), &[], &mut Variables::new());
678 assert!(res.is_ok(), res.err().unwrap());
679 assert_eq!(res.unwrap(), vec![b'0' + bs[0]]);
680 let s = format!("%{{1}}%{{1}}%{}%d", op);
681 let res = expand(s.as_bytes(), &[], &mut Variables::new());
682 assert!(res.is_ok(), res.err().unwrap());
683 assert_eq!(res.unwrap(), vec![b'0' + bs[1]]);
684 let s = format!("%{{2}}%{{1}}%{}%d", op);
685 let res = expand(s.as_bytes(), &[], &mut Variables::new());
686 assert!(res.is_ok(), res.err().unwrap());
687 assert_eq!(res.unwrap(), vec![b'0' + bs[2]]);
688 }
689 }
690
691 #[test]
692 fn test_conditionals() {
693 let mut vars = Variables::new();
694 let s = b"\\E[%?%p1%{8}%<%t3%p1%d%e%p1%{16}%<%t9%p1%{8}%-%d%e38;5;%p1%d%;m";
695 let res = expand(s, &[Number(1)], &mut vars);
696 assert!(res.is_ok(), res.err().unwrap());
697 assert_eq!(res.unwrap(), "\\E[31m".bytes().collect::<Vec<_>>());
698 let res = expand(s, &[Number(8)], &mut vars);
699 assert!(res.is_ok(), res.err().unwrap());
700 assert_eq!(res.unwrap(), "\\E[90m".bytes().collect::<Vec<_>>());
701 let res = expand(s, &[Number(42)], &mut vars);
702 assert!(res.is_ok(), res.err().unwrap());
703 assert_eq!(res.unwrap(), "\\E[38;5;42m".bytes().collect::<Vec<_>>());
704 }
705
706 #[test]
707 fn test_format() {
708 let mut varstruct = Variables::new();
709 let vars = &mut varstruct;
710 assert_eq!(
711 expand(
712 b"%p1%s%p2%2s%p3%2s%p4%.2s",
713 &[
714 Words("foo".to_owned()),
715 Words("foo".to_owned()),
716 Words("f".to_owned()),
717 Words("foo".to_owned())
718 ],
719 vars
720 ),
721 Ok("foofoo ffo".bytes().collect::<Vec<_>>())
722 );
723 assert_eq!(
724 expand(b"%p1%:-4.2s", &[Words("foo".to_owned())], vars),
725 Ok("fo ".bytes().collect::<Vec<_>>())
726 );
727
728 assert_eq!(
729 expand(b"%p1%d%p1%.3d%p1%5d%p1%:+d", &[Number(1)], vars),
730 Ok("1001 1+1".bytes().collect::<Vec<_>>())
731 );
732 assert_eq!(
733 expand(
734 b"%p1%o%p1%#o%p2%6.4x%p2%#6.4X",
735 &[Number(15), Number(27)],
736 vars
737 ),
738 Ok("17017 001b0X001B".bytes().collect::<Vec<_>>())
739 );
740 }
741}
742