git.delta.rocks / jrsonnet / refs/commits / 7cd3ab4b3483

1//! faster std.format impl2#![allow(clippy::too_many_arguments)]34use jrsonnet_gcmodule::Trace;5use jrsonnet_interner::IStr;6use jrsonnet_types::ValType;7use thiserror::Error;89use crate::{10	bail,11	error::{format_found, suggest_object_fields, ErrorKind::*},12	typed::Typed,13	Error, ObjValue, Result, Val,14};1516#[derive(Debug, Clone, Error, Trace)]17pub enum FormatError {18	#[error("truncated format code")]19	TruncatedFormatCode,20	#[error("unrecognized conversion type: {0}")]21	UnrecognizedConversionType(char),2223	#[error("not enough values")]24	NotEnoughValues,2526	#[error("cannot use * width with object")]27	CannotUseStarWidthWithObject,28	#[error("mapping keys required")]29	MappingKeysRequired,30	#[error("no such format field: {0}")]31	NoSuchFormatField(IStr),3233	#[error("expected subfield <{0}> to be an object, got {1} instead")]34	SubfieldDidntYieldAnObject(IStr, ValType),35	#[error("subfield not found: <[{full}]{current}>{}", format_found(.found, "subfield"))]36	SubfieldNotFound {37		current: IStr,38		full: IStr,39		found: Box<Vec<IStr>>,40	},41}4243impl From<FormatError> for Error {44	fn from(e: FormatError) -> Self {45		Self::new(Format(e))46	}47}4849use FormatError::*;5051type ParseResult<'t, T> = std::result::Result<(T, &'t str), FormatError>;5253pub fn try_parse_mapping_key(str: &str) -> ParseResult<'_, &str> {54	if str.is_empty() {55		return Err(TruncatedFormatCode);56	}57	let bytes = str.as_bytes();58	if bytes[0] == b'(' {59		let mut i = 1;60		while i < bytes.len() {61			if bytes[i] == b')' {62				return Ok((&str[1..i], &str[i + 1..]));63			}64			i += 1;65		}66		Err(TruncatedFormatCode)67	} else {68		Ok(("", str))69	}70}7172#[cfg(test)]73pub mod tests_key {74	use super::*;7576	#[test]77	fn parse_key() {78		assert_eq!(79			try_parse_mapping_key("(hello ) world").unwrap(),80			("hello ", " world")81		);82		assert_eq!(try_parse_mapping_key("() world").unwrap(), ("", " world"));83		assert_eq!(try_parse_mapping_key(" world").unwrap(), ("", " world"));84		assert_eq!(85			try_parse_mapping_key(" () world").unwrap(),86			("", " () world")87		);88	}8990	#[test]91	#[should_panic = "TruncatedFormatCode"]92	fn parse_key_missing_start() {93		try_parse_mapping_key("").unwrap();94	}9596	#[test]97	#[should_panic = "TruncatedFormatCode"]98	fn parse_key_missing_end() {99		try_parse_mapping_key("(   ").unwrap();100	}101}102103#[allow(clippy::struct_excessive_bools)]104#[derive(Default, Debug)]105pub struct CFlags {106	pub alt: bool,107	pub zero: bool,108	pub left: bool,109	pub blank: bool,110	pub sign: bool,111}112113pub fn try_parse_cflags(str: &str) -> ParseResult<'_, CFlags> {114	if str.is_empty() {115		return Err(TruncatedFormatCode);116	}117	let bytes = str.as_bytes();118	let mut i = 0;119	let mut out = CFlags::default();120	loop {121		if bytes.len() == i {122			return Err(TruncatedFormatCode);123		}124		match bytes[i] {125			b'#' => out.alt = true,126			b'0' => out.zero = true,127			b'-' => out.left = true,128			b' ' => out.blank = true,129			b'+' => out.sign = true,130			_ => break,131		}132		i += 1;133	}134	Ok((out, &str[i..]))135}136137#[derive(Debug, PartialEq, Eq)]138pub enum Width {139	Star,140	Fixed(usize),141}142pub fn try_parse_field_width(str: &str) -> ParseResult<'_, Width> {143	if str.is_empty() {144		return Err(TruncatedFormatCode);145	}146	let bytes = str.as_bytes();147	if bytes[0] == b'*' {148		return Ok((Width::Star, &str[1..]));149	}150	let mut out: usize = 0;151	let mut digits = 0;152	while let Some(digit) = (bytes[digits] as char).to_digit(10) {153		out *= 10;154		out += digit as usize;155		digits += 1;156		if digits == bytes.len() {157			return Err(TruncatedFormatCode);158		}159	}160	Ok((Width::Fixed(out), &str[digits..]))161}162163pub fn try_parse_precision(str: &str) -> ParseResult<'_, Option<Width>> {164	if str.is_empty() {165		return Err(TruncatedFormatCode);166	}167	let bytes = str.as_bytes();168	if bytes[0] == b'.' {169		try_parse_field_width(&str[1..]).map(|(r, s)| (Some(r), s))170	} else {171		Ok((None, str))172	}173}174175// Only skips176pub fn try_parse_length_modifier(str: &str) -> ParseResult<'_, ()> {177	if str.is_empty() {178		return Err(TruncatedFormatCode);179	}180	let bytes = str.as_bytes();181	let mut idx = 0;182	while bytes[idx] == b'h' || bytes[idx] == b'l' || bytes[idx] == b'L' {183		idx += 1;184		if bytes.len() == idx {185			return Err(TruncatedFormatCode);186		}187	}188	Ok(((), &str[idx..]))189}190191#[derive(Debug, PartialEq, Eq)]192pub enum ConvTypeV {193	Decimal,194	Octal,195	Hexadecimal,196	Scientific,197	Float,198	Shorter,199	Char,200	String,201	Percent,202}203pub struct ConvType {204	v: ConvTypeV,205	caps: bool,206}207208pub fn parse_conversion_type(str: &str) -> ParseResult<'_, ConvType> {209	if str.is_empty() {210		return Err(TruncatedFormatCode);211	}212213	let code = str.as_bytes()[0];214	let v: (ConvTypeV, bool) = match code {215		b'd' | b'i' | b'u' => (ConvTypeV::Decimal, false),216		b'o' => (ConvTypeV::Octal, false),217		b'x' => (ConvTypeV::Hexadecimal, false),218		b'X' => (ConvTypeV::Hexadecimal, true),219		b'e' => (ConvTypeV::Scientific, false),220		b'E' => (ConvTypeV::Scientific, true),221		b'f' => (ConvTypeV::Float, false),222		b'F' => (ConvTypeV::Float, true),223		b'g' => (ConvTypeV::Shorter, false),224		b'G' => (ConvTypeV::Shorter, true),225		b'c' => (ConvTypeV::Char, false),226		b's' => (ConvTypeV::String, false),227		b'%' => (ConvTypeV::Percent, false),228		c => return Err(UnrecognizedConversionType(c as char)),229	};230231	Ok((ConvType { v: v.0, caps: v.1 }, &str[1..]))232}233234#[derive(Debug)]235pub struct Code<'s> {236	mkey: &'s str,237	cflags: CFlags,238	width: Width,239	precision: Option<Width>,240	convtype: ConvTypeV,241	caps: bool,242}243pub fn parse_code(str: &str) -> ParseResult<'_, Code<'_>> {244	if str.is_empty() {245		return Err(TruncatedFormatCode);246	}247	let (mkey, str) = try_parse_mapping_key(str)?;248	let (cflags, str) = try_parse_cflags(str)?;249	let (width, str) = try_parse_field_width(str)?;250	let (precision, str) = try_parse_precision(str)?;251	let ((), str) = try_parse_length_modifier(str)?;252	let (convtype, str) = parse_conversion_type(str)?;253254	Ok((255		Code {256			mkey,257			cflags,258			width,259			precision,260			convtype: convtype.v,261			caps: convtype.caps,262		},263		str,264	))265}266267#[derive(Debug)]268pub enum Element<'s> {269	String(&'s str),270	Code(Code<'s>),271}272pub fn parse_codes(mut str: &str) -> Result<Vec<Element<'_>>> {273	let mut bytes = str.as_bytes();274	let mut out = vec![];275	let mut offset = 0;276277	loop {278		while offset != bytes.len() && bytes[offset] != b'%' {279			offset += 1;280		}281		if offset != 0 {282			out.push(Element::String(&str[0..offset]));283		}284		if offset == bytes.len() {285			return Ok(out);286		}287		str = &str[offset + 1..];288		let code;289		(code, str) = parse_code(str)?;290		bytes = str.as_bytes();291		offset = 0;292293		out.push(Element::Code(code));294	}295}296297const NUMBERS: &[u8] = b"0123456789abcdefghijklmnopqrstuvwxyz";298299#[inline]300pub fn render_integer(301	out: &mut String,302	iv: f64,303	padding: usize,304	precision: usize,305	blank: bool,306	sign: bool,307	radix: i64,308	prefix: &str,309	caps: bool,310) {311	let iv = iv.floor() as i64;312	// Digit char indexes in reverse order, i.e313	// for radix = 16 and n = 12f: [15, 2, 1]314	let digits = if iv == 0 {315		vec![0u8]316	} else {317		let mut v = iv.abs();318		let mut nums = Vec::with_capacity(1);319		while v != 0 {320			nums.push((v % radix) as u8);321			v /= radix;322		}323		nums324	};325	let neg = iv < 0;326	#[allow(clippy::bool_to_int_with_if)]327	let zp = padding.saturating_sub(if neg || blank || sign { 1 } else { 0 });328	let zp2 = zp329		.max(precision)330		.saturating_sub(prefix.len() + digits.len());331332	if neg {333		out.push('-');334	} else if sign {335		out.push('+');336	} else if blank {337		out.push(' ');338	}339340	out.reserve(zp2);341	for _ in 0..zp2 {342		out.push('0');343	}344	out.push_str(prefix);345346	for digit in digits.into_iter().rev() {347		let ch = NUMBERS[digit as usize] as char;348		out.push(if caps { ch.to_ascii_uppercase() } else { ch });349	}350}351352pub fn render_decimal(353	out: &mut String,354	iv: f64,355	padding: usize,356	precision: usize,357	blank: bool,358	sign: bool,359) {360	render_integer(out, iv, padding, precision, blank, sign, 10, "", false);361}362pub fn render_octal(363	out: &mut String,364	iv: f64,365	padding: usize,366	precision: usize,367	alt: bool,368	blank: bool,369	sign: bool,370) {371	render_integer(372		out,373		iv,374		padding,375		precision,376		blank,377		sign,378		8,379		if alt && iv != 0.0 { "0" } else { "" },380		false,381	);382}383384#[allow(clippy::fn_params_excessive_bools)]385pub fn render_hexadecimal(386	out: &mut String,387	iv: f64,388	padding: usize,389	precision: usize,390	alt: bool,391	blank: bool,392	sign: bool,393	caps: bool,394) {395	render_integer(396		out,397		iv,398		padding,399		precision,400		blank,401		sign,402		16,403		match (alt, caps) {404			(true, true) => "0X",405			(true, false) => "0x",406			(false, _) => "",407		},408		caps,409	);410}411412#[allow(clippy::fn_params_excessive_bools)]413pub fn render_float(414	out: &mut String,415	n: f64,416	mut padding: usize,417	precision: usize,418	blank: bool,419	sign: bool,420	ensure_pt: bool,421	trailing: bool,422) {423	#[allow(clippy::bool_to_int_with_if)]424	let dot_size = if precision == 0 && !ensure_pt { 0 } else { 1 };425	padding = padding.saturating_sub(dot_size + precision);426	render_decimal(out, n.floor(), padding, 0, blank, sign);427	if precision == 0 {428		if ensure_pt {429			out.push('.');430		}431		return;432	}433	let frac = n434		.fract()435		.mul_add(10.0_f64.powf(precision as f64), 0.5)436		.floor();437	if trailing || frac > 0.0 {438		out.push('.');439		let mut frac_str = String::new();440		render_decimal(&mut frac_str, frac, precision, 0, false, false);441		let mut trim = frac_str.len();442		if !trailing {443			for b in frac_str.as_bytes().iter().rev() {444				if *b == b'0' {445					trim -= 1;446				} else {447					break;448				}449			}450		}451		out.push_str(&frac_str[..trim]);452	} else if ensure_pt {453		out.push('.');454	}455}456457#[allow(clippy::fn_params_excessive_bools)]458pub fn render_float_sci(459	out: &mut String,460	n: f64,461	mut padding: usize,462	precision: usize,463	blank: bool,464	sign: bool,465	ensure_pt: bool,466	trailing: bool,467	caps: bool,468) {469	let exponent = n.log10().floor();470	let mantissa = if exponent as i16 == -324 {471		n * 10.0 / 10.0_f64.powf(exponent + 1.0)472	} else {473		n / 10.0_f64.powf(exponent)474	};475	let mut exponent_str = String::new();476	render_decimal(&mut exponent_str, exponent, 3, 0, false, true);477478	// +1 for e479	padding = padding.saturating_sub(exponent_str.len() + 1);480481	render_float(482		out, mantissa, padding, precision, blank, sign, ensure_pt, trailing,483	);484	out.push(if caps { 'E' } else { 'e' });485	out.push_str(&exponent_str);486}487488#[allow(clippy::too_many_lines)]489pub fn format_code(490	out: &mut String,491	value: &Val,492	code: &Code<'_>,493	width: usize,494	precision: Option<usize>,495) -> Result<()> {496	let clfags = &code.cflags;497	let (fpprec, iprec) = precision.map_or((6, 0), |v| (v, v));498	let padding = if clfags.zero && !clfags.left {499		width500	} else {501		0502	};503504	// TODO: If left padded, can optimize by writing directly to out505	let mut tmp_out = String::new();506507	match code.convtype {508		ConvTypeV::String => tmp_out.push_str(&value.clone().to_string()?),509		ConvTypeV::Decimal => {510			let value = f64::from_untyped(value.clone())?;511			render_decimal(512				&mut tmp_out,513				value,514				padding,515				iprec,516				clfags.blank,517				clfags.sign,518			);519		}520		ConvTypeV::Octal => {521			let value = f64::from_untyped(value.clone())?;522			render_octal(523				&mut tmp_out,524				value,525				padding,526				iprec,527				clfags.alt,528				clfags.blank,529				clfags.sign,530			);531		}532		ConvTypeV::Hexadecimal => {533			let value = f64::from_untyped(value.clone())?;534			render_hexadecimal(535				&mut tmp_out,536				value,537				padding,538				iprec,539				clfags.alt,540				clfags.blank,541				clfags.sign,542				code.caps,543			);544		}545		ConvTypeV::Scientific => {546			let value = f64::from_untyped(value.clone())?;547			render_float_sci(548				&mut tmp_out,549				value,550				padding,551				fpprec,552				clfags.blank,553				clfags.sign,554				clfags.alt,555				true,556				code.caps,557			);558		}559		ConvTypeV::Float => {560			let value = f64::from_untyped(value.clone())?;561			render_float(562				&mut tmp_out,563				value,564				padding,565				fpprec,566				clfags.blank,567				clfags.sign,568				clfags.alt,569				true,570			);571		}572		ConvTypeV::Shorter => {573			let value = f64::from_untyped(value.clone())?;574			let exponent = if value == 0.0 {575				0.0576			} else {577				value.abs().log10().floor()578			};579			if exponent < -4.0 || exponent >= fpprec as f64 {580				render_float_sci(581					&mut tmp_out,582					value,583					padding,584					fpprec - 1,585					clfags.blank,586					clfags.sign,587					clfags.alt,588					clfags.alt,589					code.caps,590				);591			} else {592				let digits_before_pt = 1.max(exponent as usize + 1);593				render_float(594					&mut tmp_out,595					value,596					padding,597					fpprec - digits_before_pt,598					clfags.blank,599					clfags.sign,600					clfags.alt,601					clfags.alt,602				);603			}604		}605		ConvTypeV::Char => match value.clone() {606			Val::Num(n) => {607				let n = n.get();608				tmp_out.push(609					std::char::from_u32(n as u32)610						.ok_or_else(|| InvalidUnicodeCodepointGot(n as u32))?,611				);612			}613			Val::Str(s) => {614				let s = s.into_flat();615				if s.chars().count() != 1 {616					bail!("%c expected 1 char string, got {}", s.chars().count());617				}618				tmp_out.push_str(&s);619			}620			_ => {621				bail!(TypeMismatch(622					"%c requires number/string",623					vec![ValType::Num, ValType::Str],624					value.value_type(),625				));626			}627		},628		ConvTypeV::Percent => tmp_out.push('%'),629	};630631	let padding = width.saturating_sub(tmp_out.len());632633	if !clfags.left {634		for _ in 0..padding {635			out.push(' ');636		}637	}638	out.push_str(&tmp_out);639	if clfags.left {640		for _ in 0..padding {641			out.push(' ');642		}643	}644645	Ok(())646}647648pub fn format_arr(str: &str, mut values: &[Val]) -> Result<String> {649	let codes = parse_codes(str)?;650	let mut out = String::new();651	let value_count = values.len();652653	for code in codes {654		match code {655			Element::String(s) => {656				out.push_str(s);657			}658			Element::Code(c) => {659				let width = match c.width {660					Width::Star => {661						if values.is_empty() {662							bail!(NotEnoughValues);663						}664						let value = &values[0];665						values = &values[1..];666						usize::from_untyped(value.clone())?667					}668					Width::Fixed(n) => n,669				};670				let precision = match c.precision {671					Some(Width::Star) => {672						if values.is_empty() {673							bail!(NotEnoughValues);674						}675						let value = &values[0];676						values = &values[1..];677						Some(usize::from_untyped(value.clone())?)678					}679					Some(Width::Fixed(n)) => Some(n),680					None => None,681				};682683				// %% should not consume a value684				let value = if c.convtype == ConvTypeV::Percent {685					&Val::Null686				} else {687					if values.is_empty() {688						bail!(NotEnoughValues);689					}690					let value = &values[0];691					values = &values[1..];692					value693				};694695				format_code(&mut out, value, &c, width, precision)?;696			}697		}698	}699700	if !values.is_empty() {701		bail!(702			"too many values to format, expected {value_count}, got {}",703			value_count + values.len()704		)705	}706707	Ok(out)708}709710fn get_dotted_field(obj: ObjValue, field: &str) -> Result<Val> {711	let mut current = Val::Obj(obj);712	let mut name_offset = 0;713	for component in field.split('.') {714		let end_offset = name_offset + component.len();715		current = if let Val::Obj(obj) = current {716			if let Some(value) = obj.get(component.into())? {717				value718			} else {719				let current = &field[name_offset..end_offset];720				let full = &field[..name_offset];721				let found = Box::new(suggest_object_fields(&obj, current.into()));722				bail!(SubfieldNotFound {723					current: current.into(),724					full: full.into(),725					found,726				})727			}728		} else {729			// No underflow may happen, initially we always start with an object730			let subfield = &field[..name_offset - 1];731			bail!(SubfieldDidntYieldAnObject(732				subfield.into(),733				current.value_type()734			));735		};736		name_offset = end_offset + 1;737	}738	Ok(current)739}740741pub fn format_obj(str: &str, values: &ObjValue) -> Result<String> {742	let codes = parse_codes(str)?;743	let mut out = String::new();744745	for code in codes {746		match code {747			Element::String(s) => {748				out.push_str(s);749			}750			Element::Code(c) => {751				// TODO: Operate on ref752				let f: IStr = c.mkey.into();753				let width = match c.width {754					Width::Star => {755						bail!(CannotUseStarWidthWithObject);756					}757					Width::Fixed(n) => n,758				};759				let precision = match c.precision {760					Some(Width::Star) => {761						bail!(CannotUseStarWidthWithObject);762					}763					Some(Width::Fixed(n)) => Some(n),764					None => None,765				};766767				let value = if c.convtype == ConvTypeV::Percent {768					Val::Null769				} else {770					if f.is_empty() {771						bail!(MappingKeysRequired);772					}773					if let Some(v) = values.get(f.clone())? {774						v775					} else {776						get_dotted_field(values.clone(), &f)?777					}778				};779780				format_code(&mut out, &value, &c, width, precision)?;781			}782		}783	}784785	Ok(out)786}787788#[cfg(test)]789pub mod test_format {790	use super::*;791	use crate::val::NumValue;792793	#[test]794	fn parse() {795		assert_eq!(796			parse_codes(797				"How much error budget is left looking at our %.3f%% availability gurantees?"798			)799			.unwrap()800			.len(),801			4802		);803	}804805	fn num(v: f64) -> Val {806		Val::Num(NumValue::new(v).expect("finite"))807	}808809	#[test]810	fn octals() {811		assert_eq!(format_arr("%#o", &[num(8.0)]).unwrap(), "010");812		assert_eq!(format_arr("%#4o", &[num(8.0)]).unwrap(), " 010");813		assert_eq!(format_arr("%4o", &[num(8.0)]).unwrap(), "  10");814		assert_eq!(format_arr("%04o", &[num(8.0)]).unwrap(), "0010");815		assert_eq!(format_arr("%+4o", &[num(8.0)]).unwrap(), " +10");816		assert_eq!(format_arr("%+04o", &[num(8.0)]).unwrap(), "+010");817		assert_eq!(format_arr("%-4o", &[num(8.0)]).unwrap(), "10  ");818		assert_eq!(format_arr("%+-4o", &[num(8.0)]).unwrap(), "+10 ");819		assert_eq!(format_arr("%+-04o", &[num(8.0)]).unwrap(), "+10 ");820	}821822	#[test]823	fn percent_doesnt_consumes_values() {824		assert_eq!(825			format_arr(826				"How much error budget is left looking at our %.3f%% availability gurantees?",827				&[num(4.0)]828			)829			.unwrap(),830			"How much error budget is left looking at our 4.000% availability gurantees?"831		);832	}833}