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

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 radix = radix as f64;312	let iv = iv.floor();313	// Digit char indexes in reverse order, i.e314	// for radix = 16 and n = 12f: [15, 2, 1]315	let digits = if iv == 0.0 {316		vec![0u8]317	} else {318		let mut v = iv.abs();319		let mut nums = Vec::with_capacity(1);320		while v != 0.0 {321			nums.push((v % radix) as u8);322			v = (v / radix).floor();323		}324		nums325	};326	let neg = iv < 0.0;327	#[allow(clippy::bool_to_int_with_if)]328	let zp = padding.saturating_sub(if neg || blank || sign { 1 } else { 0 });329	let zp2 = zp330		.max(precision)331		.saturating_sub(prefix.len() + digits.len());332333	if neg {334		out.push('-');335	} else if sign {336		out.push('+');337	} else if blank {338		out.push(' ');339	}340341	out.reserve(zp2);342	for _ in 0..zp2 {343		out.push('0');344	}345	out.push_str(prefix);346347	for digit in digits.into_iter().rev() {348		let ch = NUMBERS[digit as usize] as char;349		out.push(if caps { ch.to_ascii_uppercase() } else { ch });350	}351}352353pub fn render_decimal(354	out: &mut String,355	iv: f64,356	padding: usize,357	precision: usize,358	blank: bool,359	sign: bool,360) {361	render_integer(out, iv, padding, precision, blank, sign, 10, "", false);362}363pub fn render_octal(364	out: &mut String,365	iv: f64,366	padding: usize,367	precision: usize,368	alt: bool,369	blank: bool,370	sign: bool,371) {372	render_integer(373		out,374		iv,375		padding,376		precision,377		blank,378		sign,379		8,380		if alt && iv != 0.0 { "0" } else { "" },381		false,382	);383}384385#[allow(clippy::fn_params_excessive_bools)]386pub fn render_hexadecimal(387	out: &mut String,388	iv: f64,389	padding: usize,390	precision: usize,391	alt: bool,392	blank: bool,393	sign: bool,394	caps: bool,395) {396	render_integer(397		out,398		iv,399		padding,400		precision,401		blank,402		sign,403		16,404		match (alt, caps) {405			(true, true) => "0X",406			(true, false) => "0x",407			(false, _) => "",408		},409		caps,410	);411}412413#[allow(clippy::fn_params_excessive_bools)]414pub fn render_float(415	out: &mut String,416	n: f64,417	mut padding: usize,418	precision: usize,419	blank: bool,420	sign: bool,421	ensure_pt: bool,422	trailing: bool,423) {424	#[allow(clippy::bool_to_int_with_if)]425	let dot_size = if precision == 0 && !ensure_pt { 0 } else { 1 };426	padding = padding.saturating_sub(dot_size + precision);427	render_decimal(out, n.floor(), padding, 0, blank, sign);428	if precision == 0 {429		if ensure_pt {430			out.push('.');431		}432		return;433	}434	let frac = n435		.fract()436		.mul_add(10.0_f64.powf(precision as f64), 0.5)437		.floor();438	if trailing || frac > 0.0 {439		out.push('.');440		let mut frac_str = String::new();441		render_decimal(&mut frac_str, frac, precision, 0, false, false);442		let mut trim = frac_str.len();443		if !trailing {444			for b in frac_str.as_bytes().iter().rev() {445				if *b == b'0' {446					trim -= 1;447				} else {448					break;449				}450			}451		}452		out.push_str(&frac_str[..trim]);453	} else if ensure_pt {454		out.push('.');455	}456}457458#[allow(clippy::fn_params_excessive_bools)]459pub fn render_float_sci(460	out: &mut String,461	n: f64,462	mut padding: usize,463	precision: usize,464	blank: bool,465	sign: bool,466	ensure_pt: bool,467	trailing: bool,468	caps: bool,469) {470	let exponent = n.log10().floor();471	let mantissa = if exponent as i16 == -324 {472		n * 10.0 / 10.0_f64.powf(exponent + 1.0)473	} else {474		n / 10.0_f64.powf(exponent)475	};476	let mut exponent_str = String::new();477	render_decimal(&mut exponent_str, exponent, 3, 0, false, true);478479	// +1 for e480	padding = padding.saturating_sub(exponent_str.len() + 1);481482	render_float(483		out, mantissa, padding, precision, blank, sign, ensure_pt, trailing,484	);485	out.push(if caps { 'E' } else { 'e' });486	out.push_str(&exponent_str);487}488489#[allow(clippy::too_many_lines)]490pub fn format_code(491	out: &mut String,492	value: &Val,493	code: &Code<'_>,494	width: usize,495	precision: Option<usize>,496) -> Result<()> {497	let clfags = &code.cflags;498	let (fpprec, iprec) = precision.map_or((6, 0), |v| (v, v));499	let padding = if clfags.zero && !clfags.left {500		width501	} else {502		0503	};504505	// TODO: If left padded, can optimize by writing directly to out506	let mut tmp_out = String::new();507508	match code.convtype {509		ConvTypeV::String => tmp_out.push_str(&value.clone().to_string()?),510		ConvTypeV::Decimal => {511			let value = f64::from_untyped(value.clone())?;512			render_decimal(513				&mut tmp_out,514				value,515				padding,516				iprec,517				clfags.blank,518				clfags.sign,519			);520		}521		ConvTypeV::Octal => {522			let value = f64::from_untyped(value.clone())?;523			render_octal(524				&mut tmp_out,525				value,526				padding,527				iprec,528				clfags.alt,529				clfags.blank,530				clfags.sign,531			);532		}533		ConvTypeV::Hexadecimal => {534			let value = f64::from_untyped(value.clone())?;535			render_hexadecimal(536				&mut tmp_out,537				value,538				padding,539				iprec,540				clfags.alt,541				clfags.blank,542				clfags.sign,543				code.caps,544			);545		}546		ConvTypeV::Scientific => {547			let value = f64::from_untyped(value.clone())?;548			render_float_sci(549				&mut tmp_out,550				value,551				padding,552				fpprec,553				clfags.blank,554				clfags.sign,555				clfags.alt,556				true,557				code.caps,558			);559		}560		ConvTypeV::Float => {561			let value = f64::from_untyped(value.clone())?;562			render_float(563				&mut tmp_out,564				value,565				padding,566				fpprec,567				clfags.blank,568				clfags.sign,569				clfags.alt,570				true,571			);572		}573		ConvTypeV::Shorter => {574			let value = f64::from_untyped(value.clone())?;575			let exponent = if value == 0.0 {576				0.0577			} else {578				value.abs().log10().floor()579			};580			if exponent < -4.0 || exponent >= fpprec as f64 {581				render_float_sci(582					&mut tmp_out,583					value,584					padding,585					fpprec - 1,586					clfags.blank,587					clfags.sign,588					clfags.alt,589					clfags.alt,590					code.caps,591				);592			} else {593				let digits_before_pt = 1.max(exponent as usize + 1);594				render_float(595					&mut tmp_out,596					value,597					padding,598					fpprec - digits_before_pt,599					clfags.blank,600					clfags.sign,601					clfags.alt,602					clfags.alt,603				);604			}605		}606		ConvTypeV::Char => match value.clone() {607			Val::Num(n) => {608				let n = n.get();609				tmp_out.push(610					std::char::from_u32(n as u32)611						.ok_or_else(|| InvalidUnicodeCodepointGot(n as u32))?,612				);613			}614			Val::Str(s) => {615				let s = s.into_flat();616				if s.chars().count() != 1 {617					bail!("%c expected 1 char string, got {}", s.chars().count());618				}619				tmp_out.push_str(&s);620			}621			_ => {622				bail!(TypeMismatch(623					"%c requires number/string",624					vec![ValType::Num, ValType::Str],625					value.value_type(),626				));627			}628		},629		ConvTypeV::Percent => tmp_out.push('%'),630	};631632	let padding = width.saturating_sub(tmp_out.len());633634	if !clfags.left {635		for _ in 0..padding {636			out.push(' ');637		}638	}639	out.push_str(&tmp_out);640	if clfags.left {641		for _ in 0..padding {642			out.push(' ');643		}644	}645646	Ok(())647}648649pub fn format_arr(str: &str, mut values: &[Val]) -> Result<String> {650	let codes = parse_codes(str)?;651	let mut out = String::new();652	let value_count = values.len();653654	for code in codes {655		match code {656			Element::String(s) => {657				out.push_str(s);658			}659			Element::Code(c) => {660				let width = match c.width {661					Width::Star => {662						if values.is_empty() {663							bail!(NotEnoughValues);664						}665						let value = &values[0];666						values = &values[1..];667						usize::from_untyped(value.clone())?668					}669					Width::Fixed(n) => n,670				};671				let precision = match c.precision {672					Some(Width::Star) => {673						if values.is_empty() {674							bail!(NotEnoughValues);675						}676						let value = &values[0];677						values = &values[1..];678						Some(usize::from_untyped(value.clone())?)679					}680					Some(Width::Fixed(n)) => Some(n),681					None => None,682				};683684				// %% should not consume a value685				let value = if c.convtype == ConvTypeV::Percent {686					&Val::Null687				} else {688					if values.is_empty() {689						bail!(NotEnoughValues);690					}691					let value = &values[0];692					values = &values[1..];693					value694				};695696				format_code(&mut out, value, &c, width, precision)?;697			}698		}699	}700701	if !values.is_empty() {702		bail!(703			"too many values to format, expected {value_count}, got {}",704			value_count + values.len()705		)706	}707708	Ok(out)709}710711fn get_dotted_field(obj: ObjValue, field: &str) -> Result<Val> {712	let mut current = Val::Obj(obj);713	let mut name_offset = 0;714	for component in field.split('.') {715		let end_offset = name_offset + component.len();716		current = if let Val::Obj(obj) = current {717			if let Some(value) = obj.get(component.into())? {718				value719			} else {720				let current = &field[name_offset..end_offset];721				let full = &field[..name_offset];722				let found = Box::new(suggest_object_fields(&obj, current.into()));723				bail!(SubfieldNotFound {724					current: current.into(),725					full: full.into(),726					found,727				})728			}729		} else {730			// No underflow may happen, initially we always start with an object731			let subfield = &field[..name_offset - 1];732			bail!(SubfieldDidntYieldAnObject(733				subfield.into(),734				current.value_type()735			));736		};737		name_offset = end_offset + 1;738	}739	Ok(current)740}741742pub fn format_obj(str: &str, values: &ObjValue) -> Result<String> {743	let codes = parse_codes(str)?;744	let mut out = String::new();745746	for code in codes {747		match code {748			Element::String(s) => {749				out.push_str(s);750			}751			Element::Code(c) => {752				// TODO: Operate on ref753				let f: IStr = c.mkey.into();754				let width = match c.width {755					Width::Star => {756						bail!(CannotUseStarWidthWithObject);757					}758					Width::Fixed(n) => n,759				};760				let precision = match c.precision {761					Some(Width::Star) => {762						bail!(CannotUseStarWidthWithObject);763					}764					Some(Width::Fixed(n)) => Some(n),765					None => None,766				};767768				let value = if c.convtype == ConvTypeV::Percent {769					Val::Null770				} else {771					if f.is_empty() {772						bail!(MappingKeysRequired);773					}774					if let Some(v) = values.get(f.clone())? {775						v776					} else {777						get_dotted_field(values.clone(), &f)?778					}779				};780781				format_code(&mut out, &value, &c, width, precision)?;782			}783		}784	}785786	Ok(out)787}788789#[cfg(test)]790pub mod test_format {791	use super::*;792	use crate::val::NumValue;793794	#[test]795	fn parse() {796		assert_eq!(797			parse_codes(798				"How much error budget is left looking at our %.3f%% availability gurantees?"799			)800			.unwrap()801			.len(),802			4803		);804	}805806	fn num(v: f64) -> Val {807		Val::Num(NumValue::new(v).expect("finite"))808	}809810	#[test]811	fn octals() {812		assert_eq!(format_arr("%#o", &[num(8.0)]).unwrap(), "010");813		assert_eq!(format_arr("%#4o", &[num(8.0)]).unwrap(), " 010");814		assert_eq!(format_arr("%4o", &[num(8.0)]).unwrap(), "  10");815		assert_eq!(format_arr("%04o", &[num(8.0)]).unwrap(), "0010");816		assert_eq!(format_arr("%+4o", &[num(8.0)]).unwrap(), " +10");817		assert_eq!(format_arr("%+04o", &[num(8.0)]).unwrap(), "+010");818		assert_eq!(format_arr("%-4o", &[num(8.0)]).unwrap(), "10  ");819		assert_eq!(format_arr("%+-4o", &[num(8.0)]).unwrap(), "+10 ");820		assert_eq!(format_arr("%+-04o", &[num(8.0)]).unwrap(), "+10 ");821	}822823	#[test]824	fn percent_doesnt_consumes_values() {825		assert_eq!(826			format_arr(827				"How much error budget is left looking at our %.3f%% availability gurantees?",828				&[num(4.0)]829			)830			.unwrap(),831			"How much error budget is left looking at our 4.000% availability gurantees?"832		);833	}834}