git.delta.rocks / jrsonnet / refs/commits / 5df60b8b674f

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(u16),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: u16 = 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 u16;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]300#[allow(clippy::fn_params_excessive_bools)]301pub fn render_integer(302	out: &mut String,303	neg: bool,304	iv: f64,305	padding: u16,306	precision: u16,307	blank: bool,308	sign: bool,309	radix: i64,310	zero_prefix: &str,311	prefix_in_padding: bool,312	caps: bool,313) {314	debug_assert!(iv >= 0.0, "render_integer receives sign using arg");315	let iv = iv.floor() as i64;316	// Digit char indexes in reverse order, i.e317	// for radix = 16 and n = 12f: [15, 2, 1]318	let digits = if iv == 0 {319		vec![0u8]320	} else {321		let mut v = iv.abs();322		let mut nums = Vec::with_capacity(1);323		while v != 0 {324			nums.push((v % radix) as u8);325			v /= radix;326		}327		nums328	};329	#[allow(clippy::bool_to_int_with_if)]330	let zp = padding.saturating_sub(if neg || blank || sign { 1 } else { 0 });331332	let pref_len = zero_prefix.len() as u16;333	let zp2 = zp334		.saturating_sub(if prefix_in_padding { 0 } else { pref_len })335		.max(precision)336		.saturating_sub(if prefix_in_padding { pref_len } else { 0 } + digits.len() as u16);337338	if neg {339		out.push('-');340	} else if sign {341		out.push('+');342	} else if blank {343		out.push(' ');344	}345346	out.reserve(zp2 as usize);347	if iv != 0 {348		out.push_str(zero_prefix);349	}350	for _ in 0..zp2 {351		out.push('0');352	}353354	for digit in digits.into_iter().rev() {355		let ch = NUMBERS[digit as usize] as char;356		out.push(if caps { ch.to_ascii_uppercase() } else { ch });357	}358}359360pub fn render_decimal(361	out: &mut String,362	neg: bool,363	iv: f64,364	padding: u16,365	precision: u16,366	blank: bool,367	sign: bool,368) {369	render_integer(370		out, neg, iv, padding, precision, blank, sign, 10, "", false, false,371	);372}373#[allow(clippy::fn_params_excessive_bools)]374pub fn render_octal(375	out: &mut String,376	neg: bool,377	iv: f64,378	padding: u16,379	precision: u16,380	alt: bool,381	blank: bool,382	sign: bool,383) {384	render_integer(385		out,386		neg,387		iv,388		padding,389		precision,390		blank,391		sign,392		8,393		if alt && iv != 0.0 { "0" } else { "" },394		true,395		false,396	);397}398399#[allow(clippy::fn_params_excessive_bools)]400pub fn render_hexadecimal(401	out: &mut String,402	iv: f64,403	padding: u16,404	precision: u16,405	alt: bool,406	blank: bool,407	sign: bool,408	caps: bool,409) {410	render_integer(411		out,412		iv < 0.0,413		iv.abs(),414		padding,415		precision,416		blank,417		sign,418		16,419		match (alt, caps) {420			(true, true) => "0X",421			(true, false) => "0x",422			(false, _) => "",423		},424		false,425		caps,426	);427}428429#[allow(clippy::fn_params_excessive_bools)]430pub fn render_float(431	out: &mut String,432	n: f64,433	mut padding: u16,434	precision: u16,435	blank: bool,436	sign: bool,437	ensure_pt: bool,438	trailing: bool,439) {440	// Represent the rounded number as an integer * 1/10**prec.441	// Note that it can also be equal to 10**prec and we'll need to carry442	// over to the wholes.  We operate on the absolute numbers, so that we443	// don't have trouble with the rounding direction.444	let denominator = 10.0f64.powi(i32::from(precision));445	let numerator = n.abs().mul_add(denominator, 0.5);446	let whole = (numerator / denominator).floor();447	let frac = numerator.floor() % denominator;448449	#[allow(clippy::bool_to_int_with_if)]450	let dot_size = if precision == 0 && !ensure_pt { 0 } else { 1 };451	padding = padding.saturating_sub(dot_size + precision);452	render_decimal(out, n < 0.0, whole, padding, 0, blank, sign);453	if precision == 0 {454		if ensure_pt {455			out.push('.');456		}457		return;458	}459	if trailing || frac > 0.0 {460		out.push('.');461		let mut frac_str = String::new();462		render_decimal(&mut frac_str, false, frac, precision, 0, false, false);463		let mut trim = frac_str.len();464		if !trailing {465			for b in frac_str.as_bytes().iter().rev() {466				if *b == b'0' {467					trim -= 1;468				} else {469					break;470				}471			}472		}473		out.push_str(&frac_str[..trim]);474	} else if ensure_pt {475		out.push('.');476	}477}478479#[allow(clippy::fn_params_excessive_bools)]480pub fn render_float_sci(481	out: &mut String,482	n: f64,483	mut padding: u16,484	precision: u16,485	blank: bool,486	sign: bool,487	ensure_pt: bool,488	trailing: bool,489	caps: bool,490) {491	let exponent = if n == 0.0 {492		0.0493	} else {494		n.abs().log10().floor()495	};496497	let mantissa = if exponent as i16 == -324 {498		n * 10.0 / 10.0_f64.powf(exponent + 1.0)499	} else {500		n / 10.0_f64.powf(exponent)501	};502	let mut exponent_str = String::new();503	render_decimal(504		&mut exponent_str,505		exponent < 0.0,506		exponent.abs(),507		3,508		0,509		false,510		true,511	);512513	// +1 for e514	padding = padding.saturating_sub(exponent_str.len() as u16 + 1);515516	render_float(517		out, mantissa, padding, precision, blank, sign, ensure_pt, trailing,518	);519	out.push(if caps { 'E' } else { 'e' });520	out.push_str(&exponent_str);521}522523#[allow(clippy::too_many_lines)]524pub fn format_code(525	out: &mut String,526	value: &Val,527	code: &Code<'_>,528	width: u16,529	precision: Option<u16>,530) -> Result<()> {531	let clfags = &code.cflags;532	let (fpprec, iprec) = precision.map_or((6, 0), |v| (v, v));533	let padding = if clfags.zero && !clfags.left {534		width535	} else {536		0537	};538539	// TODO: If left padded, can optimize by writing directly to out540	let mut tmp_out = String::new();541542	match code.convtype {543		ConvTypeV::String => tmp_out.push_str(&value.clone().to_string()?),544		ConvTypeV::Decimal => {545			let value = f64::from_untyped(value.clone())?;546			render_decimal(547				&mut tmp_out,548				value <= -1.0,549				value.abs(),550				padding,551				iprec,552				clfags.blank,553				clfags.sign,554			);555		}556		ConvTypeV::Octal => {557			let value = f64::from_untyped(value.clone())?;558			render_octal(559				&mut tmp_out,560				value <= -1.0,561				value.abs(),562				padding,563				iprec,564				clfags.alt,565				clfags.blank,566				clfags.sign,567			);568		}569		ConvTypeV::Hexadecimal => {570			let value = f64::from_untyped(value.clone())?;571			render_hexadecimal(572				&mut tmp_out,573				value,574				padding,575				iprec,576				clfags.alt,577				clfags.blank,578				clfags.sign,579				code.caps,580			);581		}582		ConvTypeV::Scientific => {583			let value = f64::from_untyped(value.clone())?;584			render_float_sci(585				&mut tmp_out,586				value,587				padding,588				fpprec,589				clfags.blank,590				clfags.sign,591				clfags.alt,592				true,593				code.caps,594			);595		}596		ConvTypeV::Float => {597			let value = f64::from_untyped(value.clone())?;598			render_float(599				&mut tmp_out,600				value,601				padding,602				fpprec,603				clfags.blank,604				clfags.sign,605				clfags.alt,606				true,607			);608		}609		ConvTypeV::Shorter => {610			let value = f64::from_untyped(value.clone())?;611			let exponent = if value == 0.0 {612				0.0613			} else {614				value.abs().log10().floor()615			};616			if exponent < -4.0 || exponent >= f64::from(fpprec) {617				render_float_sci(618					&mut tmp_out,619					value,620					padding,621					fpprec - 1,622					clfags.blank,623					clfags.sign,624					clfags.alt,625					clfags.alt,626					code.caps,627				);628			} else {629				let digits_before_pt = 1.max(exponent as u16 + 1);630				render_float(631					&mut tmp_out,632					value,633					padding,634					fpprec - digits_before_pt,635					clfags.blank,636					clfags.sign,637					clfags.alt,638					clfags.alt,639				);640			}641		}642		ConvTypeV::Char => match value.clone() {643			Val::Num(n) => {644				let n = n.get();645				tmp_out.push(646					std::char::from_u32(n as u32)647						.ok_or_else(|| InvalidUnicodeCodepointGot(n as u32))?,648				);649			}650			Val::Str(s) => {651				let s = s.into_flat();652				if s.chars().count() != 1 {653					bail!("%c expected 1 char string, got {}", s.chars().count());654				}655				tmp_out.push_str(&s);656			}657			_ => {658				bail!(TypeMismatch(659					"%c requires number/string",660					vec![ValType::Num, ValType::Str],661					value.value_type(),662				));663			}664		},665		ConvTypeV::Percent => tmp_out.push('%'),666	}667668	let padding = width.saturating_sub(tmp_out.len() as u16);669670	if !clfags.left {671		for _ in 0..padding {672			out.push(' ');673		}674	}675	out.push_str(&tmp_out);676	if clfags.left {677		for _ in 0..padding {678			out.push(' ');679		}680	}681682	Ok(())683}684685pub fn format_arr(str: &str, mut values: &[Val]) -> Result<String> {686	let codes = parse_codes(str)?;687	let mut out = String::new();688	let value_count = values.len();689690	for code in codes {691		match code {692			Element::String(s) => {693				out.push_str(s);694			}695			Element::Code(c) => {696				let width = match c.width {697					Width::Star => {698						if values.is_empty() {699							bail!(NotEnoughValues);700						}701						let value = &values[0];702						values = &values[1..];703						u16::from_untyped(value.clone())?704					}705					Width::Fixed(n) => n,706				};707				let precision = match c.precision {708					Some(Width::Star) => {709						if values.is_empty() {710							bail!(NotEnoughValues);711						}712						let value = &values[0];713						values = &values[1..];714						Some(u16::from_untyped(value.clone())?)715					}716					Some(Width::Fixed(n)) => Some(n),717					None => None,718				};719720				// %% should not consume a value721				let value = if c.convtype == ConvTypeV::Percent {722					&Val::Null723				} else {724					if values.is_empty() {725						bail!(NotEnoughValues);726					}727					let value = &values[0];728					values = &values[1..];729					value730				};731732				format_code(&mut out, value, &c, width, precision)?;733			}734		}735	}736737	if !values.is_empty() {738		bail!(739			"too many values to format, expected {value_count}, got {}",740			value_count + values.len()741		)742	}743744	Ok(out)745}746747fn get_dotted_field(obj: ObjValue, field: &str) -> Result<Val> {748	let mut current = Val::Obj(obj);749	let mut name_offset = 0;750	for component in field.split('.') {751		let end_offset = name_offset + component.len();752		current = if let Val::Obj(obj) = current {753			if let Some(value) = obj.get(component.into())? {754				value755			} else {756				let current = &field[name_offset..end_offset];757				let full = &field[..name_offset];758				let found = Box::new(suggest_object_fields(&obj, current.into()));759				bail!(SubfieldNotFound {760					current: current.into(),761					full: full.into(),762					found,763				})764			}765		} else {766			// No underflow may happen, initially we always start with an object767			let subfield = &field[..name_offset - 1];768			bail!(SubfieldDidntYieldAnObject(769				subfield.into(),770				current.value_type()771			));772		};773		name_offset = end_offset + 1;774	}775	Ok(current)776}777778pub fn format_obj(str: &str, values: &ObjValue) -> Result<String> {779	let codes = parse_codes(str)?;780	let mut out = String::new();781782	for code in codes {783		match code {784			Element::String(s) => {785				out.push_str(s);786			}787			Element::Code(c) => {788				// TODO: Operate on ref789				let f: IStr = c.mkey.into();790				let width = match c.width {791					Width::Star => {792						bail!(CannotUseStarWidthWithObject);793					}794					Width::Fixed(n) => n,795				};796				let precision = match c.precision {797					Some(Width::Star) => {798						bail!(CannotUseStarWidthWithObject);799					}800					Some(Width::Fixed(n)) => Some(n),801					None => None,802				};803804				let value = if c.convtype == ConvTypeV::Percent {805					Val::Null806				} else {807					if f.is_empty() {808						bail!(MappingKeysRequired);809					}810					if let Some(v) = values.get(f.clone())? {811						v812					} else {813						get_dotted_field(values.clone(), &f)?814					}815				};816817				format_code(&mut out, &value, &c, width, precision)?;818			}819		}820	}821822	Ok(out)823}824825#[cfg(test)]826pub mod test_format {827	use super::*;828	use crate::val::NumValue;829830	#[test]831	fn parse() {832		assert_eq!(833			parse_codes(834				"How much error budget is left looking at our %.3f%% availability gurantees?"835			)836			.unwrap()837			.len(),838			4839		);840	}841842	fn num(v: f64) -> Val {843		Val::Num(NumValue::new(v).expect("finite"))844	}845846	#[test]847	fn octals() {848		assert_eq!(format_arr("%#o", &[num(8.0)]).unwrap(), "010");849		assert_eq!(format_arr("%#4o", &[num(8.0)]).unwrap(), " 010");850		assert_eq!(format_arr("%4o", &[num(8.0)]).unwrap(), "  10");851		assert_eq!(format_arr("%04o", &[num(8.0)]).unwrap(), "0010");852		assert_eq!(format_arr("%+4o", &[num(8.0)]).unwrap(), " +10");853		assert_eq!(format_arr("%+04o", &[num(8.0)]).unwrap(), "+010");854		assert_eq!(format_arr("%-4o", &[num(8.0)]).unwrap(), "10  ");855		assert_eq!(format_arr("%+-4o", &[num(8.0)]).unwrap(), "+10 ");856		assert_eq!(format_arr("%+-04o", &[num(8.0)]).unwrap(), "+10 ");857	}858859	#[test]860	fn percent_doesnt_consumes_values() {861		assert_eq!(862			format_arr(863				"How much error budget is left looking at our %.3f%% availability gurantees?",864				&[num(4.0)]865			)866			.unwrap(),867			"How much error budget is left looking at our 4.000% availability gurantees?"868		);869	}870}