git.delta.rocks / jrsonnet / refs/commits / eea91c38b18b

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]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 { pref_len } else { 0 })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}372pub fn render_octal(373	out: &mut String,374	neg: bool,375	iv: f64,376	padding: u16,377	precision: u16,378	alt: bool,379	blank: bool,380	sign: bool,381) {382	render_integer(383		out,384		neg,385		iv,386		padding,387		precision,388		blank,389		sign,390		8,391		if alt && iv != 0.0 { "0" } else { "" },392		true,393		false,394	);395}396397#[allow(clippy::fn_params_excessive_bools)]398pub fn render_hexadecimal(399	out: &mut String,400	iv: f64,401	padding: u16,402	precision: u16,403	alt: bool,404	blank: bool,405	sign: bool,406	caps: bool,407) {408	render_integer(409		out,410		iv < 0.0,411		iv.abs(),412		padding,413		precision,414		blank,415		sign,416		16,417		match (alt, caps) {418			(true, true) => "0X",419			(true, false) => "0x",420			(false, _) => "",421		},422		false,423		caps,424	);425}426427#[allow(clippy::fn_params_excessive_bools)]428pub fn render_float(429	out: &mut String,430	n: f64,431	mut padding: u16,432	precision: u16,433	blank: bool,434	sign: bool,435	ensure_pt: bool,436	trailing: bool,437) {438	// Represent the rounded number as an integer * 1/10**prec.439	// Note that it can also be equal to 10**prec and we'll need to carry440	// over to the wholes.  We operate on the absolute numbers, so that we441	// don't have trouble with the rounding direction.442	let denominator = 10.0f64.powi(precision as i32);443	let numerator = n.abs() * denominator + 0.5;444	let whole = (numerator / denominator).floor();445	let frac = numerator.floor() % denominator;446447	#[allow(clippy::bool_to_int_with_if)]448	let dot_size = if precision == 0 && !ensure_pt { 0 } else { 1 };449	padding = padding.saturating_sub(dot_size + precision);450	render_decimal(out, n < 0.0, whole, padding, 0, blank, sign);451	if precision == 0 {452		if ensure_pt {453			out.push('.');454		}455		return;456	}457	if trailing || frac > 0.0 {458		out.push('.');459		let mut frac_str = String::new();460		render_decimal(&mut frac_str, false, frac, precision, 0, false, false);461		let mut trim = frac_str.len();462		if !trailing {463			for b in frac_str.as_bytes().iter().rev() {464				if *b == b'0' {465					trim -= 1;466				} else {467					break;468				}469			}470		}471		out.push_str(&frac_str[..trim]);472	} else if ensure_pt {473		out.push('.');474	}475}476477#[allow(clippy::fn_params_excessive_bools)]478pub fn render_float_sci(479	out: &mut String,480	n: f64,481	mut padding: u16,482	precision: u16,483	blank: bool,484	sign: bool,485	ensure_pt: bool,486	trailing: bool,487	caps: bool,488) {489	let exponent = if n == 0.0 {490		0.0491	} else {492		n.abs().log10().floor()493	};494495	let mantissa = if exponent as i16 == -324 {496		n * 10.0 / 10.0_f64.powf(exponent + 1.0)497	} else {498		n / 10.0_f64.powf(exponent)499	};500	let mut exponent_str = String::new();501	render_decimal(502		&mut exponent_str,503		exponent < 0.0,504		exponent.abs(),505		3,506		0,507		false,508		true,509	);510511	// +1 for e512	padding = padding.saturating_sub(exponent_str.len() as u16 + 1);513514	render_float(515		out, mantissa, padding, precision, blank, sign, ensure_pt, trailing,516	);517	out.push(if caps { 'E' } else { 'e' });518	out.push_str(&exponent_str);519}520521#[allow(clippy::too_many_lines)]522pub fn format_code(523	out: &mut String,524	value: &Val,525	code: &Code<'_>,526	width: u16,527	precision: Option<u16>,528) -> Result<()> {529	let clfags = &code.cflags;530	let (fpprec, iprec) = precision.map_or((6, 0), |v| (v, v));531	let padding = if clfags.zero && !clfags.left {532		width533	} else {534		0535	};536537	// TODO: If left padded, can optimize by writing directly to out538	let mut tmp_out = String::new();539540	match code.convtype {541		ConvTypeV::String => tmp_out.push_str(&value.clone().to_string()?),542		ConvTypeV::Decimal => {543			let value = f64::from_untyped(value.clone())?;544			render_decimal(545				&mut tmp_out,546				value <= -1.0,547				value.abs(),548				padding,549				iprec,550				clfags.blank,551				clfags.sign,552			);553		}554		ConvTypeV::Octal => {555			let value = f64::from_untyped(value.clone())?;556			render_octal(557				&mut tmp_out,558				value <= -1.0,559				value.abs(),560				padding,561				iprec,562				clfags.alt,563				clfags.blank,564				clfags.sign,565			);566		}567		ConvTypeV::Hexadecimal => {568			let value = f64::from_untyped(value.clone())?;569			render_hexadecimal(570				&mut tmp_out,571				value,572				padding,573				iprec,574				clfags.alt,575				clfags.blank,576				clfags.sign,577				code.caps,578			);579		}580		ConvTypeV::Scientific => {581			let value = f64::from_untyped(value.clone())?;582			render_float_sci(583				&mut tmp_out,584				value,585				padding,586				fpprec,587				clfags.blank,588				clfags.sign,589				clfags.alt,590				true,591				code.caps,592			);593		}594		ConvTypeV::Float => {595			let value = f64::from_untyped(value.clone())?;596			render_float(597				&mut tmp_out,598				value,599				padding,600				fpprec,601				clfags.blank,602				clfags.sign,603				clfags.alt,604				true,605			);606		}607		ConvTypeV::Shorter => {608			let value = f64::from_untyped(value.clone())?;609			let exponent = if value == 0.0 {610				0.0611			} else {612				value.abs().log10().floor()613			};614			if exponent < -4.0 || exponent >= fpprec as f64 {615				render_float_sci(616					&mut tmp_out,617					value,618					padding,619					fpprec - 1,620					clfags.blank,621					clfags.sign,622					clfags.alt,623					clfags.alt,624					code.caps,625				);626			} else {627				let digits_before_pt = 1.max(exponent as u16 + 1);628				render_float(629					&mut tmp_out,630					value,631					padding,632					fpprec - digits_before_pt,633					clfags.blank,634					clfags.sign,635					clfags.alt,636					clfags.alt,637				);638			}639		}640		ConvTypeV::Char => match value.clone() {641			Val::Num(n) => {642				let n = n.get();643				tmp_out.push(644					std::char::from_u32(n as u32)645						.ok_or_else(|| InvalidUnicodeCodepointGot(n as u32))?,646				);647			}648			Val::Str(s) => {649				let s = s.into_flat();650				if s.chars().count() != 1 {651					bail!("%c expected 1 char string, got {}", s.chars().count());652				}653				tmp_out.push_str(&s);654			}655			_ => {656				bail!(TypeMismatch(657					"%c requires number/string",658					vec![ValType::Num, ValType::Str],659					value.value_type(),660				));661			}662		},663		ConvTypeV::Percent => tmp_out.push('%'),664	};665666	let padding = width.saturating_sub(tmp_out.len() as u16);667668	if !clfags.left {669		for _ in 0..padding {670			out.push(' ');671		}672	}673	out.push_str(&tmp_out);674	if clfags.left {675		for _ in 0..padding {676			out.push(' ');677		}678	}679680	Ok(())681}682683pub fn format_arr(str: &str, mut values: &[Val]) -> Result<String> {684	let codes = parse_codes(str)?;685	let mut out = String::new();686	let value_count = values.len();687688	for code in codes {689		match code {690			Element::String(s) => {691				out.push_str(s);692			}693			Element::Code(c) => {694				let width = match c.width {695					Width::Star => {696						if values.is_empty() {697							bail!(NotEnoughValues);698						}699						let value = &values[0];700						values = &values[1..];701						u16::from_untyped(value.clone())?702					}703					Width::Fixed(n) => n,704				};705				let precision = match c.precision {706					Some(Width::Star) => {707						if values.is_empty() {708							bail!(NotEnoughValues);709						}710						let value = &values[0];711						values = &values[1..];712						Some(u16::from_untyped(value.clone())?)713					}714					Some(Width::Fixed(n)) => Some(n),715					None => None,716				};717718				// %% should not consume a value719				let value = if c.convtype == ConvTypeV::Percent {720					&Val::Null721				} else {722					if values.is_empty() {723						bail!(NotEnoughValues);724					}725					let value = &values[0];726					values = &values[1..];727					value728				};729730				format_code(&mut out, value, &c, width, precision)?;731			}732		}733	}734735	if !values.is_empty() {736		bail!(737			"too many values to format, expected {value_count}, got {}",738			value_count + values.len()739		)740	}741742	Ok(out)743}744745fn get_dotted_field(obj: ObjValue, field: &str) -> Result<Val> {746	let mut current = Val::Obj(obj);747	let mut name_offset = 0;748	for component in field.split('.') {749		let end_offset = name_offset + component.len();750		current = if let Val::Obj(obj) = current {751			if let Some(value) = obj.get(component.into())? {752				value753			} else {754				let current = &field[name_offset..end_offset];755				let full = &field[..name_offset];756				let found = Box::new(suggest_object_fields(&obj, current.into()));757				bail!(SubfieldNotFound {758					current: current.into(),759					full: full.into(),760					found,761				})762			}763		} else {764			// No underflow may happen, initially we always start with an object765			let subfield = &field[..name_offset - 1];766			bail!(SubfieldDidntYieldAnObject(767				subfield.into(),768				current.value_type()769			));770		};771		name_offset = end_offset + 1;772	}773	Ok(current)774}775776pub fn format_obj(str: &str, values: &ObjValue) -> Result<String> {777	let codes = parse_codes(str)?;778	let mut out = String::new();779780	for code in codes {781		match code {782			Element::String(s) => {783				out.push_str(s);784			}785			Element::Code(c) => {786				// TODO: Operate on ref787				let f: IStr = c.mkey.into();788				let width = match c.width {789					Width::Star => {790						bail!(CannotUseStarWidthWithObject);791					}792					Width::Fixed(n) => n,793				};794				let precision = match c.precision {795					Some(Width::Star) => {796						bail!(CannotUseStarWidthWithObject);797					}798					Some(Width::Fixed(n)) => Some(n),799					None => None,800				};801802				let value = if c.convtype == ConvTypeV::Percent {803					Val::Null804				} else {805					if f.is_empty() {806						bail!(MappingKeysRequired);807					}808					if let Some(v) = values.get(f.clone())? {809						v810					} else {811						get_dotted_field(values.clone(), &f)?812					}813				};814815				format_code(&mut out, &value, &c, width, precision)?;816			}817		}818	}819820	Ok(out)821}822823#[cfg(test)]824pub mod test_format {825	use super::*;826	use crate::val::NumValue;827828	#[test]829	fn parse() {830		assert_eq!(831			parse_codes(832				"How much error budget is left looking at our %.3f%% availability gurantees?"833			)834			.unwrap()835			.len(),836			4837		);838	}839840	fn num(v: f64) -> Val {841		Val::Num(NumValue::new(v).expect("finite"))842	}843844	#[test]845	fn octals() {846		assert_eq!(format_arr("%#o", &[num(8.0)]).unwrap(), "010");847		assert_eq!(format_arr("%#4o", &[num(8.0)]).unwrap(), " 010");848		assert_eq!(format_arr("%4o", &[num(8.0)]).unwrap(), "  10");849		assert_eq!(format_arr("%04o", &[num(8.0)]).unwrap(), "0010");850		assert_eq!(format_arr("%+4o", &[num(8.0)]).unwrap(), " +10");851		assert_eq!(format_arr("%+04o", &[num(8.0)]).unwrap(), "+010");852		assert_eq!(format_arr("%-4o", &[num(8.0)]).unwrap(), "10  ");853		assert_eq!(format_arr("%+-4o", &[num(8.0)]).unwrap(), "+10 ");854		assert_eq!(format_arr("%+-04o", &[num(8.0)]).unwrap(), "+10 ");855	}856857	#[test]858	fn percent_doesnt_consumes_values() {859		assert_eq!(860			format_arr(861				"How much error budget is left looking at our %.3f%% availability gurantees?",862				&[num(4.0)]863			)864			.unwrap(),865			"How much error budget is left looking at our 4.000% availability gurantees?"866		);867	}868}