git.delta.rocks / jrsonnet / refs/commits / 75beb619a12f

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	Error, ObjValue, Result, Val, bail,11	error::{ErrorKind::*, format_found, suggest_object_fields},12	typed::FromUntyped,13};1415#[derive(Debug, Clone, Error, Trace)]16pub enum FormatError {17	#[error("truncated format code")]18	TruncatedFormatCode,19	#[error("unrecognized conversion type: {0}")]20	UnrecognizedConversionType(char),2122	#[error("not enough values")]23	NotEnoughValues,2425	#[error("cannot use * width with object")]26	CannotUseStarWidthWithObject,27	#[error("mapping keys required")]28	MappingKeysRequired,29	#[error("no such format field: {0}")]30	NoSuchFormatField(IStr),3132	#[error("expected subfield <{0}> to be an object, got {1} instead")]33	SubfieldDidntYieldAnObject(IStr, ValType),34	#[error("subfield not found: <[{full}]{current}>{}", format_found(.found, "subfield"))]35	SubfieldNotFound {36		current: IStr,37		full: IStr,38		found: Box<Vec<IStr>>,39	},40}4142impl From<FormatError> for Error {43	fn from(e: FormatError) -> Self {44		Self::new(Format(e))45	}46}4748use FormatError::*;4950type ParseResult<'t, T> = std::result::Result<(T, &'t str), FormatError>;5152pub fn try_parse_mapping_key(str: &str) -> ParseResult<'_, &str> {53	if str.is_empty() {54		return Err(TruncatedFormatCode);55	}56	let bytes = str.as_bytes();57	if bytes[0] == b'(' {58		let mut i = 1;59		while i < bytes.len() {60			if bytes[i] == b')' {61				return Ok((&str[1..i], &str[i + 1..]));62			}63			i += 1;64		}65		Err(TruncatedFormatCode)66	} else {67		Ok(("", str))68	}69}7071#[cfg(test)]72pub mod tests_key {73	use super::*;7475	#[test]76	fn parse_key() {77		assert_eq!(78			try_parse_mapping_key("(hello ) world").unwrap(),79			("hello ", " world")80		);81		assert_eq!(try_parse_mapping_key("() world").unwrap(), ("", " world"));82		assert_eq!(try_parse_mapping_key(" world").unwrap(), ("", " world"));83		assert_eq!(84			try_parse_mapping_key(" () world").unwrap(),85			("", " () world")86		);87	}8889	#[test]90	#[should_panic = "TruncatedFormatCode"]91	fn parse_key_missing_start() {92		try_parse_mapping_key("").unwrap();93	}9495	#[test]96	#[should_panic = "TruncatedFormatCode"]97	fn parse_key_missing_end() {98		try_parse_mapping_key("(   ").unwrap();99	}100}101102#[allow(clippy::struct_excessive_bools)]103#[derive(Default, Debug)]104pub struct CFlags {105	pub alt: bool,106	pub zero: bool,107	pub left: bool,108	pub blank: bool,109	pub sign: bool,110}111112pub fn try_parse_cflags(str: &str) -> ParseResult<'_, CFlags> {113	if str.is_empty() {114		return Err(TruncatedFormatCode);115	}116	let bytes = str.as_bytes();117	let mut i = 0;118	let mut out = CFlags::default();119	loop {120		if bytes.len() == i {121			return Err(TruncatedFormatCode);122		}123		match bytes[i] {124			b'#' => out.alt = true,125			b'0' => out.zero = true,126			b'-' => out.left = true,127			b' ' => out.blank = true,128			b'+' => out.sign = true,129			_ => break,130		}131		i += 1;132	}133	Ok((out, &str[i..]))134}135136#[derive(Debug, PartialEq, Eq)]137pub enum Width {138	Star,139	Fixed(u16),140}141pub fn try_parse_field_width(str: &str) -> ParseResult<'_, Width> {142	if str.is_empty() {143		return Err(TruncatedFormatCode);144	}145	let bytes = str.as_bytes();146	if bytes[0] == b'*' {147		return Ok((Width::Star, &str[1..]));148	}149	let mut out: u16 = 0;150	let mut digits = 0;151	while let Some(digit) = (bytes[digits] as char).to_digit(10) {152		out *= 10;153		out += digit as u16;154		digits += 1;155		if digits == bytes.len() {156			return Err(TruncatedFormatCode);157		}158	}159	Ok((Width::Fixed(out), &str[digits..]))160}161162pub fn try_parse_precision(str: &str) -> ParseResult<'_, Option<Width>> {163	if str.is_empty() {164		return Err(TruncatedFormatCode);165	}166	let bytes = str.as_bytes();167	if bytes[0] == b'.' {168		try_parse_field_width(&str[1..]).map(|(r, s)| (Some(r), s))169	} else {170		Ok((None, str))171	}172}173174// Only skips175pub fn try_parse_length_modifier(str: &str) -> ParseResult<'_, ()> {176	if str.is_empty() {177		return Err(TruncatedFormatCode);178	}179	let bytes = str.as_bytes();180	let mut idx = 0;181	while bytes[idx] == b'h' || bytes[idx] == b'l' || bytes[idx] == b'L' {182		idx += 1;183		if bytes.len() == idx {184			return Err(TruncatedFormatCode);185		}186	}187	Ok(((), &str[idx..]))188}189190#[derive(Debug, PartialEq, Eq)]191pub enum ConvTypeV {192	Decimal,193	Octal,194	Hexadecimal,195	Scientific,196	Float,197	Shorter,198	Char,199	String,200	Percent,201}202pub struct ConvType {203	v: ConvTypeV,204	caps: bool,205}206207pub fn parse_conversion_type(str: &str) -> ParseResult<'_, ConvType> {208	if str.is_empty() {209		return Err(TruncatedFormatCode);210	}211212	let code = str.as_bytes()[0];213	let v: (ConvTypeV, bool) = match code {214		b'd' | b'i' | b'u' => (ConvTypeV::Decimal, false),215		b'o' => (ConvTypeV::Octal, false),216		b'x' => (ConvTypeV::Hexadecimal, false),217		b'X' => (ConvTypeV::Hexadecimal, true),218		b'e' => (ConvTypeV::Scientific, false),219		b'E' => (ConvTypeV::Scientific, true),220		b'f' => (ConvTypeV::Float, false),221		b'F' => (ConvTypeV::Float, true),222		b'g' => (ConvTypeV::Shorter, false),223		b'G' => (ConvTypeV::Shorter, true),224		b'c' => (ConvTypeV::Char, false),225		b's' => (ConvTypeV::String, false),226		b'%' => (ConvTypeV::Percent, false),227		c => return Err(UnrecognizedConversionType(c as char)),228	};229230	Ok((ConvType { v: v.0, caps: v.1 }, &str[1..]))231}232233#[derive(Debug)]234pub struct Code<'s> {235	mkey: &'s str,236	cflags: CFlags,237	width: Width,238	precision: Option<Width>,239	convtype: ConvTypeV,240	caps: bool,241}242pub fn parse_code(str: &str) -> ParseResult<'_, Code<'_>> {243	if str.is_empty() {244		return Err(TruncatedFormatCode);245	}246	let (mkey, str) = try_parse_mapping_key(str)?;247	let (cflags, str) = try_parse_cflags(str)?;248	let (width, str) = try_parse_field_width(str)?;249	let (precision, str) = try_parse_precision(str)?;250	let ((), str) = try_parse_length_modifier(str)?;251	let (convtype, str) = parse_conversion_type(str)?;252253	Ok((254		Code {255			mkey,256			cflags,257			width,258			precision,259			convtype: convtype.v,260			caps: convtype.caps,261		},262		str,263	))264}265266#[derive(Debug)]267pub enum Element<'s> {268	String(&'s str),269	Code(Code<'s>),270}271pub fn parse_codes(mut str: &str) -> Result<Vec<Element<'_>>> {272	let mut bytes = str.as_bytes();273	let mut out = vec![];274	let mut offset = 0;275276	loop {277		while offset != bytes.len() && bytes[offset] != b'%' {278			offset += 1;279		}280		if offset != 0 {281			out.push(Element::String(&str[0..offset]));282		}283		if offset == bytes.len() {284			return Ok(out);285		}286		str = &str[offset + 1..];287		let code;288		(code, str) = parse_code(str)?;289		bytes = str.as_bytes();290		offset = 0;291292		out.push(Element::Code(code));293	}294}295296const NUMBERS: &[u8] = b"0123456789abcdefghijklmnopqrstuvwxyz";297298#[inline]299#[allow(clippy::fn_params_excessive_bools)]300pub fn render_integer(301	out: &mut String,302	neg: bool,303	iv: f64,304	padding: u16,305	precision: u16,306	blank: bool,307	sign: bool,308	radix: i64,309	zero_prefix: &str,310	prefix_in_padding: bool,311	caps: bool,312) {313	debug_assert!(iv >= 0.0, "render_integer receives sign using arg");314	let iv = iv.floor() as i64;315	// Digit char indexes in reverse order, i.e316	// for radix = 16 and n = 12f: [15, 2, 1]317	let digits = if iv == 0 {318		vec![0u8]319	} else {320		let mut v = iv.abs();321		let mut nums = Vec::with_capacity(1);322		while v != 0 {323			nums.push((v % radix) as u8);324			v /= radix;325		}326		nums327	};328	#[allow(clippy::bool_to_int_with_if)]329	let zp = padding.saturating_sub(if neg || blank || sign { 1 } else { 0 });330331	let pref_len = zero_prefix.len() as u16;332	let zp2 = zp333		.saturating_sub(if prefix_in_padding { 0 } else { pref_len })334		.max(precision)335		.saturating_sub(if prefix_in_padding { pref_len } else { 0 } + digits.len() as u16);336337	if neg {338		out.push('-');339	} else if sign {340		out.push('+');341	} else if blank {342		out.push(' ');343	}344345	out.reserve(zp2 as usize);346	if iv != 0 {347		out.push_str(zero_prefix);348	}349	for _ in 0..zp2 {350		out.push('0');351	}352353	for digit in digits.into_iter().rev() {354		let ch = NUMBERS[digit as usize] as char;355		out.push(if caps { ch.to_ascii_uppercase() } else { ch });356	}357}358359pub fn render_decimal(360	out: &mut String,361	neg: bool,362	iv: f64,363	padding: u16,364	precision: u16,365	blank: bool,366	sign: bool,367) {368	render_integer(369		out, neg, iv, padding, precision, blank, sign, 10, "", false, false,370	);371}372#[allow(clippy::fn_params_excessive_bools)]373pub fn render_octal(374	out: &mut String,375	neg: bool,376	iv: f64,377	padding: u16,378	precision: u16,379	alt: bool,380	blank: bool,381	sign: bool,382) {383	render_integer(384		out,385		neg,386		iv,387		padding,388		precision,389		blank,390		sign,391		8,392		if alt && iv != 0.0 { "0" } else { "" },393		true,394		false,395	);396}397398#[allow(clippy::fn_params_excessive_bools)]399pub fn render_hexadecimal(400	out: &mut String,401	iv: f64,402	padding: u16,403	precision: u16,404	alt: bool,405	blank: bool,406	sign: bool,407	caps: bool,408) {409	render_integer(410		out,411		iv < 0.0,412		iv.abs(),413		padding,414		precision,415		blank,416		sign,417		16,418		match (alt, caps) {419			(true, true) => "0X",420			(true, false) => "0x",421			(false, _) => "",422		},423		false,424		caps,425	);426}427428#[allow(clippy::fn_params_excessive_bools)]429pub fn render_float(430	out: &mut String,431	n: f64,432	mut padding: u16,433	precision: u16,434	blank: bool,435	sign: bool,436	ensure_pt: bool,437	trailing: bool,438) {439	// Represent the rounded number as an integer * 1/10**prec.440	// Note that it can also be equal to 10**prec and we'll need to carry441	// over to the wholes.  We operate on the absolute numbers, so that we442	// don't have trouble with the rounding direction.443	let denominator = 10.0f64.powi(i32::from(precision));444	let numerator = n.abs().mul_add(denominator, 0.5);445	let whole = (numerator / denominator).floor();446	let frac = numerator.floor() % denominator;447448	#[allow(clippy::bool_to_int_with_if)]449	let dot_size = if precision == 0 && !ensure_pt { 0 } else { 1 };450	padding = padding.saturating_sub(dot_size + precision);451	render_decimal(out, n < 0.0, whole, padding, 0, blank, sign);452	if precision == 0 {453		if ensure_pt {454			out.push('.');455		}456		return;457	}458	if trailing || frac > 0.0 {459		out.push('.');460		let mut frac_str = String::new();461		render_decimal(&mut frac_str, false, frac, precision, 0, false, false);462		let mut trim = frac_str.len();463		if !trailing {464			for b in frac_str.as_bytes().iter().rev() {465				if *b == b'0' {466					trim -= 1;467				} else {468					break;469				}470			}471		}472		out.push_str(&frac_str[..trim]);473	} else if ensure_pt {474		out.push('.');475	}476}477478#[allow(clippy::fn_params_excessive_bools)]479pub fn render_float_sci(480	out: &mut String,481	n: f64,482	mut padding: u16,483	precision: u16,484	blank: bool,485	sign: bool,486	ensure_pt: bool,487	trailing: bool,488	caps: bool,489) {490	let exponent = if n == 0.0 {491		0.0492	} else {493		n.abs().log10().floor()494	};495496	let mantissa = if exponent as i16 == -324 {497		n * 10.0 / 10.0_f64.powf(exponent + 1.0)498	} else {499		n / 10.0_f64.powf(exponent)500	};501	let mut exponent_str = String::new();502	render_decimal(503		&mut exponent_str,504		exponent < 0.0,505		exponent.abs(),506		3,507		0,508		false,509		true,510	);511512	// +1 for e513	padding = padding.saturating_sub(exponent_str.len() as u16 + 1);514515	render_float(516		out, mantissa, padding, precision, blank, sign, ensure_pt, trailing,517	);518	out.push(if caps { 'E' } else { 'e' });519	out.push_str(&exponent_str);520}521522#[allow(clippy::too_many_lines)]523pub fn format_code(524	out: &mut String,525	value: &Val,526	code: &Code<'_>,527	width: u16,528	precision: Option<u16>,529) -> Result<()> {530	let clfags = &code.cflags;531	let (fpprec, iprec) = precision.map_or((6, 0), |v| (v, v));532	let padding = if clfags.zero && !clfags.left {533		width534	} else {535		0536	};537538	// TODO: If left padded, can optimize by writing directly to out539	let mut tmp_out = String::new();540541	match code.convtype {542		ConvTypeV::String => tmp_out.push_str(&value.clone().to_string()?),543		ConvTypeV::Decimal => {544			let value = f64::from_untyped(value.clone())?;545			render_decimal(546				&mut tmp_out,547				value <= -1.0,548				value.abs(),549				padding,550				iprec,551				clfags.blank,552				clfags.sign,553			);554		}555		ConvTypeV::Octal => {556			let value = f64::from_untyped(value.clone())?;557			render_octal(558				&mut tmp_out,559				value <= -1.0,560				value.abs(),561				padding,562				iprec,563				clfags.alt,564				clfags.blank,565				clfags.sign,566			);567		}568		ConvTypeV::Hexadecimal => {569			let value = f64::from_untyped(value.clone())?;570			render_hexadecimal(571				&mut tmp_out,572				value,573				padding,574				iprec,575				clfags.alt,576				clfags.blank,577				clfags.sign,578				code.caps,579			);580		}581		ConvTypeV::Scientific => {582			let value = f64::from_untyped(value.clone())?;583			render_float_sci(584				&mut tmp_out,585				value,586				padding,587				fpprec,588				clfags.blank,589				clfags.sign,590				clfags.alt,591				true,592				code.caps,593			);594		}595		ConvTypeV::Float => {596			let value = f64::from_untyped(value.clone())?;597			render_float(598				&mut tmp_out,599				value,600				padding,601				fpprec,602				clfags.blank,603				clfags.sign,604				clfags.alt,605				true,606			);607		}608		ConvTypeV::Shorter => {609			let value = f64::from_untyped(value.clone())?;610			let exponent = if value == 0.0 {611				0.0612			} else {613				value.abs().log10().floor()614			};615			if exponent < -4.0 || exponent >= f64::from(fpprec) {616				render_float_sci(617					&mut tmp_out,618					value,619					padding,620					fpprec - 1,621					clfags.blank,622					clfags.sign,623					clfags.alt,624					clfags.alt,625					code.caps,626				);627			} else {628				let digits_before_pt = 1.max(exponent as u16 + 1);629				render_float(630					&mut tmp_out,631					value,632					padding,633					fpprec - digits_before_pt,634					clfags.blank,635					clfags.sign,636					clfags.alt,637					clfags.alt,638				);639			}640		}641		ConvTypeV::Char => match value.clone() {642			Val::Num(n) => {643				let n = n.get();644				tmp_out.push(645					std::char::from_u32(n as u32)646						.ok_or_else(|| InvalidUnicodeCodepointGot(n as u32))?,647				);648			}649			Val::Str(s) => {650				let s = s.into_flat();651				if s.chars().count() != 1 {652					bail!("%c expected 1 char string, got {}", s.chars().count());653				}654				tmp_out.push_str(&s);655			}656			_ => {657				bail!(TypeMismatch(658					"%c requires number/string",659					vec![ValType::Num, ValType::Str],660					value.value_type(),661				));662			}663		},664		ConvTypeV::Percent => tmp_out.push('%'),665	}666667	let padding = width.saturating_sub(tmp_out.len() as u16);668669	if !clfags.left {670		for _ in 0..padding {671			out.push(' ');672		}673	}674	out.push_str(&tmp_out);675	if clfags.left {676		for _ in 0..padding {677			out.push(' ');678		}679	}680681	Ok(())682}683684pub fn format_arr(str: &str, mut values: &[Val]) -> Result<String> {685	let codes = parse_codes(str)?;686	let mut out = String::new();687	let value_count = values.len();688689	for code in codes {690		match code {691			Element::String(s) => {692				out.push_str(s);693			}694			Element::Code(c) => {695				let width = match c.width {696					Width::Star => {697						if values.is_empty() {698							bail!(NotEnoughValues);699						}700						let value = &values[0];701						values = &values[1..];702						u16::from_untyped(value.clone())?703					}704					Width::Fixed(n) => n,705				};706				let precision = match c.precision {707					Some(Width::Star) => {708						if values.is_empty() {709							bail!(NotEnoughValues);710						}711						let value = &values[0];712						values = &values[1..];713						Some(u16::from_untyped(value.clone())?)714					}715					Some(Width::Fixed(n)) => Some(n),716					None => None,717				};718719				// %% should not consume a value720				let value = if c.convtype == ConvTypeV::Percent {721					&Val::Null722				} else {723					if values.is_empty() {724						bail!(NotEnoughValues);725					}726					let value = &values[0];727					values = &values[1..];728					value729				};730731				format_code(&mut out, value, &c, width, precision)?;732			}733		}734	}735736	if !values.is_empty() {737		bail!(738			"too many values to format, expected {value_count}, got {}",739			value_count + values.len()740		)741	}742743	Ok(out)744}745746fn get_dotted_field(obj: ObjValue, field: &str) -> Result<Val> {747	let mut current = Val::Obj(obj);748	let mut name_offset = 0;749	for component in field.split('.') {750		let end_offset = name_offset + component.len();751		current = if let Val::Obj(obj) = current {752			if let Some(value) = obj.get(component.into())? {753				value754			} else {755				let current = &field[name_offset..end_offset];756				let full = &field[..name_offset];757				let found = Box::new(suggest_object_fields(&obj, current.into()));758				bail!(SubfieldNotFound {759					current: current.into(),760					full: full.into(),761					found,762				})763			}764		} else {765			// No underflow may happen, initially we always start with an object766			let subfield = &field[..name_offset - 1];767			bail!(SubfieldDidntYieldAnObject(768				subfield.into(),769				current.value_type()770			));771		};772		name_offset = end_offset + 1;773	}774	Ok(current)775}776777pub fn format_obj(str: &str, values: &ObjValue) -> Result<String> {778	let codes = parse_codes(str)?;779	let mut out = String::new();780781	for code in codes {782		match code {783			Element::String(s) => {784				out.push_str(s);785			}786			Element::Code(c) => {787				// TODO: Operate on ref788				let f: IStr = c.mkey.into();789				let width = match c.width {790					Width::Star => {791						bail!(CannotUseStarWidthWithObject);792					}793					Width::Fixed(n) => n,794				};795				let precision = match c.precision {796					Some(Width::Star) => {797						bail!(CannotUseStarWidthWithObject);798					}799					Some(Width::Fixed(n)) => Some(n),800					None => None,801				};802803				let value = if c.convtype == ConvTypeV::Percent {804					Val::Null805				} else {806					if f.is_empty() {807						bail!(MappingKeysRequired);808					}809					if let Some(v) = values.get(f.clone())? {810						v811					} else {812						get_dotted_field(values.clone(), &f)?813					}814				};815816				format_code(&mut out, &value, &c, width, precision)?;817			}818		}819	}820821	Ok(out)822}823824#[cfg(test)]825pub mod test_format {826	use super::*;827	use crate::val::NumValue;828829	#[test]830	fn parse() {831		assert_eq!(832			parse_codes(833				"How much error budget is left looking at our %.3f%% availability gurantees?"834			)835			.unwrap()836			.len(),837			4838		);839	}840841	fn num(v: f64) -> Val {842		Val::Num(NumValue::new(v).expect("finite"))843	}844845	#[test]846	fn octals() {847		assert_eq!(format_arr("%#o", &[num(8.0)]).unwrap(), "010");848		assert_eq!(format_arr("%#4o", &[num(8.0)]).unwrap(), " 010");849		assert_eq!(format_arr("%4o", &[num(8.0)]).unwrap(), "  10");850		assert_eq!(format_arr("%04o", &[num(8.0)]).unwrap(), "0010");851		assert_eq!(format_arr("%+4o", &[num(8.0)]).unwrap(), " +10");852		assert_eq!(format_arr("%+04o", &[num(8.0)]).unwrap(), "+010");853		assert_eq!(format_arr("%-4o", &[num(8.0)]).unwrap(), "10  ");854		assert_eq!(format_arr("%+-4o", &[num(8.0)]).unwrap(), "+10 ");855		assert_eq!(format_arr("%+-04o", &[num(8.0)]).unwrap(), "+10 ");856	}857858	#[test]859	fn percent_doesnt_consumes_values() {860		assert_eq!(861			format_arr(862				"How much error budget is left looking at our %.3f%% availability gurantees?",863				&[num(4.0)]864			)865			.unwrap(),866			"How much error budget is left looking at our 4.000% availability gurantees?"867		);868	}869}