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

1use std::cmp::Ordering;23use jrsonnet_evaluator::{4	error::Result,5	function::{builtin, FuncVal},6	operator::evaluate_compare_op,7	throw,8	val::{equals, ArrValue},9	Thunk, Val,10};11use jrsonnet_gcmodule::Cc;1213#[derive(Copy, Clone)]14enum SortKeyType {15	Number,16	String,17	Unknown,18}1920#[derive(PartialEq)]21struct NonNaNf64(f64);22impl PartialOrd for NonNaNf64 {23	fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {24		self.0.partial_cmp(&other.0)25	}26}27impl Eq for NonNaNf64 {}28impl Ord for NonNaNf64 {29	fn cmp(&self, other: &Self) -> std::cmp::Ordering {30		self.partial_cmp(other).expect("non nan")31	}32}3334fn get_sort_type<T>(values: &[T], key_getter: impl Fn(&T) -> &Val) -> Result<SortKeyType> {35	let mut sort_type = SortKeyType::Unknown;36	for i in values.iter() {37		let i = key_getter(i);38		match (i, sort_type) {39			(Val::Str(_), SortKeyType::Unknown) => sort_type = SortKeyType::String,40			(Val::Num(_), SortKeyType::Unknown) => sort_type = SortKeyType::Number,41			(Val::Str(_), SortKeyType::String) | (Val::Num(_), SortKeyType::Number) => {}42			(Val::Str(_) | Val::Num(_), _) => {43				throw!("sort elements should have the same types")44			}45			_ => {}46		}47	}48	Ok(sort_type)49}5051fn sort_identity(mut values: Vec<Val>) -> Result<Vec<Val>> {52	// Fast path, identity key getter53	let sort_type = get_sort_type(&values, |k| k)?;54	match sort_type {55		SortKeyType::Number => values.sort_unstable_by_key(|v| match v {56			Val::Num(n) => NonNaNf64(*n),57			_ => unreachable!(),58		}),59		SortKeyType::String => values.sort_unstable_by_key(|v| match v {60			Val::Str(s) => s.clone(),61			_ => unreachable!(),62		}),63		SortKeyType::Unknown => {64			let mut err = None;65			// evaluate_compare_op will never return equal on types, which are different from66			// jsonnet perspective67			values.sort_unstable_by(|a, b| {68				match evaluate_compare_op(a, b, jrsonnet_parser::BinaryOpType::Lt) {69					Ok(ord) => ord,70					Err(e) if err.is_none() => {71						let _ = err.insert(e);72						Ordering::Equal73					}74					Err(_) => Ordering::Equal,75				}76			});77			if let Some(err) = err {78				return Err(err);79			}80		}81	};82	Ok(values)83}8485fn sort_keyf(values: ArrValue, keyf: FuncVal) -> Result<Vec<Thunk<Val>>> {86	// Slow path, user provided key getter87	let mut vk = Vec::with_capacity(values.len());88	for value in values.iter_lazy() {89		vk.push((90			value.clone(),91			keyf.evaluate_simple(&(value.clone(),), false)?,92		));93	}94	let sort_type = get_sort_type(&vk, |v| &v.1)?;95	match sort_type {96		SortKeyType::Number => vk.sort_by_key(|v| match v.1 {97			Val::Num(n) => NonNaNf64(n),98			_ => unreachable!(),99		}),100		SortKeyType::String => vk.sort_by_key(|v| match &v.1 {101			Val::Str(s) => s.clone(),102			_ => unreachable!(),103		}),104		SortKeyType::Unknown => {105			let mut err = None;106			// evaluate_compare_op will never return equal on types, which are different from107			// jsonnet perspective108			vk.sort_by(|(_a, ak), (_b, bk)| {109				match evaluate_compare_op(ak, bk, jrsonnet_parser::BinaryOpType::Lt) {110					Ok(ord) => ord,111					Err(e) if err.is_none() => {112						let _ = err.insert(e);113						Ordering::Equal114					}115					Err(_) => Ordering::Equal,116				}117			});118			if let Some(err) = err {119				return Err(err);120			}121		}122	};123	Ok(vk.into_iter().map(|v| v.0).collect())124}125126/// * `key_getter` - None, if identity sort required127pub fn sort(values: ArrValue, key_getter: FuncVal) -> Result<ArrValue> {128	if values.len() <= 1 {129		return Ok(values);130	}131	if key_getter.is_identity() {132		Ok(ArrValue::eager(sort_identity(133			values.iter().collect::<Result<Vec<Val>>>()?,134		)?))135	} else {136		Ok(ArrValue::lazy(Cc::new(sort_keyf(values, key_getter)?)))137	}138}139140#[builtin]141#[allow(non_snake_case)]142pub fn builtin_sort(arr: ArrValue, keyF: Option<FuncVal>) -> Result<ArrValue> {143	super::sort::sort(arr, keyF.unwrap_or_else(FuncVal::identity))144}145146fn uniq_identity(arr: Vec<Val>) -> Result<Vec<Val>> {147	let mut out = Vec::new();148	let mut last = arr[0].clone();149	out.push(last.clone());150	for next in arr.into_iter().skip(1) {151		if !equals(&last, &next)? {152			out.push(next.clone());153		}154		last = next;155	}156	Ok(out)157}158159fn uniq_keyf(arr: ArrValue, keyf: FuncVal) -> Result<Vec<Thunk<Val>>> {160	let mut out = Vec::new();161	let last_value = arr.get_lazy(0).unwrap();162	let mut last_key = keyf.evaluate_simple(&(last_value.clone(),), false)?;163	out.push(last_value);164165	for next in arr.iter_lazy().skip(1) {166		let next_key = keyf.evaluate_simple(&(next.clone(),), false)?;167		if !equals(&last_key, &next_key)? {168			out.push(next.clone());169		}170		last_key = next_key;171	}172	Ok(out)173}174175#[builtin]176#[allow(non_snake_case)]177pub fn builtin_uniq(arr: ArrValue, keyF: Option<FuncVal>) -> Result<ArrValue> {178	if arr.len() <= 1 {179		return Ok(arr);180	}181	let keyF = keyF.unwrap_or(FuncVal::identity());182	if keyF.is_identity() {183		Ok(ArrValue::eager(uniq_identity(184			arr.iter().collect::<Result<Vec<Val>>>()?,185		)?))186	} else {187		Ok(ArrValue::lazy(Cc::new(uniq_keyf(arr, keyF)?)))188	}189}190191#[builtin]192#[allow(non_snake_case)]193pub fn builtin_set(arr: ArrValue, keyF: Option<FuncVal>) -> Result<ArrValue> {194	if arr.len() <= 1 {195		return Ok(arr);196	}197	let keyF = keyF.unwrap_or(FuncVal::identity());198	if keyF.is_identity() {199		let arr = arr.iter().collect::<Result<Vec<Val>>>()?;200		let arr = sort_identity(arr)?;201		let arr = uniq_identity(arr)?;202		Ok(ArrValue::eager(arr))203	} else {204		let arr = sort_keyf(arr, keyF.clone())?;205		let arr = uniq_keyf(ArrValue::lazy(Cc::new(arr)), keyF)?;206		Ok(ArrValue::lazy(Cc::new(arr)))207	}208}