difftreelog
perf move std.uniq/std.set to native
in: master
3 files changed
crates/jrsonnet-stdlib/src/lib.rsdiffbeforeafterboth1use std::{2 cell::{Ref, RefCell, RefMut},3 collections::HashMap,4 rc::Rc,5};67use jrsonnet_evaluator::{8 error::{ErrorKind::*, Result},9 function::{builtin::Builtin, CallLocation, FuncVal, TlaArg},10 gc::{GcHashMap, TraceBox},11 tb,12 trace::PathResolver,13 Context, ContextBuilder, IStr, ObjValue, ObjValueBuilder, State, Thunk, Val,14};15use jrsonnet_gcmodule::{Cc, Trace};16use jrsonnet_parser::Source;1718mod expr;19mod types;20pub use types::*;21mod arrays;22pub use arrays::*;23mod math;24pub use math::*;25mod operator;26pub use operator::*;27mod sort;28pub use sort::*;29mod hash;30pub use hash::*;31mod encoding;32pub use encoding::*;33mod objects;34pub use objects::*;35mod manifest;36pub use manifest::*;37mod parse;38pub use parse::*;39mod strings;40pub use strings::*;41mod misc;42pub use misc::*;43mod sets;44pub use sets::*;4546pub fn stdlib_uncached(settings: Rc<RefCell<Settings>>) -> ObjValue {47 let mut builder = ObjValueBuilder::new();4849 let expr = expr::stdlib_expr();50 let eval = jrsonnet_evaluator::evaluate(ContextBuilder::dangerous_empty_state().build(), &expr)51 .expect("stdlib.jsonnet should have no errors")52 .as_obj()53 .expect("stdlib.jsonnet should evaluate to object");5455 builder.with_super(eval);5657 for (name, builtin) in [58 // Types59 ("type", builtin_type::INST),60 ("isString", builtin_is_string::INST),61 ("isNumber", builtin_is_number::INST),62 ("isBoolean", builtin_is_boolean::INST),63 ("isObject", builtin_is_object::INST),64 ("isArray", builtin_is_array::INST),65 ("isFunction", builtin_is_function::INST),66 // Arrays67 ("makeArray", builtin_make_array::INST),68 ("repeat", builtin_repeat::INST),69 ("slice", builtin_slice::INST),70 ("map", builtin_map::INST),71 ("flatMap", builtin_flatmap::INST),72 ("filter", builtin_filter::INST),73 ("foldl", builtin_foldl::INST),74 ("foldr", builtin_foldr::INST),75 ("range", builtin_range::INST),76 ("join", builtin_join::INST),77 ("reverse", builtin_reverse::INST),78 ("any", builtin_any::INST),79 ("all", builtin_all::INST),80 ("member", builtin_member::INST),81 ("count", builtin_count::INST),82 // Math83 ("abs", builtin_abs::INST),84 ("sign", builtin_sign::INST),85 ("max", builtin_max::INST),86 ("min", builtin_min::INST),87 ("modulo", builtin_modulo::INST),88 ("floor", builtin_floor::INST),89 ("ceil", builtin_ceil::INST),90 ("log", builtin_log::INST),91 ("pow", builtin_pow::INST),92 ("sqrt", builtin_sqrt::INST),93 ("sin", builtin_sin::INST),94 ("cos", builtin_cos::INST),95 ("tan", builtin_tan::INST),96 ("asin", builtin_asin::INST),97 ("acos", builtin_acos::INST),98 ("atan", builtin_atan::INST),99 ("exp", builtin_exp::INST),100 ("mantissa", builtin_mantissa::INST),101 ("exponent", builtin_exponent::INST),102 // Operator103 ("mod", builtin_mod::INST),104 ("primitiveEquals", builtin_primitive_equals::INST),105 ("equals", builtin_equals::INST),106 ("format", builtin_format::INST),107 // Sort108 ("sort", builtin_sort::INST),109 // Hash110 ("md5", builtin_md5::INST),111 #[cfg(feature = "exp-more-hashes")]112 ("sha256", builtin_sha256::INST),113 // Encoding114 ("encodeUTF8", builtin_encode_utf8::INST),115 ("decodeUTF8", builtin_decode_utf8::INST),116 ("base64", builtin_base64::INST),117 ("base64Decode", builtin_base64_decode::INST),118 ("base64DecodeBytes", builtin_base64_decode_bytes::INST),119 // Objects120 ("objectFieldsEx", builtin_object_fields_ex::INST),121 ("objectHasEx", builtin_object_has_ex::INST),122 // Manifest123 ("escapeStringJson", builtin_escape_string_json::INST),124 ("manifestJsonEx", builtin_manifest_json_ex::INST),125 ("manifestYamlDoc", builtin_manifest_yaml_doc::INST),126 ("manifestTomlEx", builtin_manifest_toml_ex::INST),127 // Parsing128 ("parseJson", builtin_parse_json::INST),129 ("parseYaml", builtin_parse_yaml::INST),130 // Strings131 ("codepoint", builtin_codepoint::INST),132 ("substr", builtin_substr::INST),133 ("char", builtin_char::INST),134 ("strReplace", builtin_str_replace::INST),135 ("splitLimit", builtin_splitlimit::INST),136 ("asciiUpper", builtin_ascii_upper::INST),137 ("asciiLower", builtin_ascii_lower::INST),138 ("findSubstr", builtin_find_substr::INST),139 ("parseInt", builtin_parse_int::INST),140 ("parseOctal", builtin_parse_octal::INST),141 ("parseHex", builtin_parse_hex::INST),142 // Misc143 ("length", builtin_length::INST),144 ("startsWith", builtin_starts_with::INST),145 ("endsWith", builtin_ends_with::INST),146 // Sets147 ("setMember", builtin_set_member::INST),148 ]149 .iter()150 .cloned()151 {152 builder153 .member(name.into())154 .hide()155 .value(Val::Func(FuncVal::StaticBuiltin(builtin)))156 .expect("no conflict");157 }158159 builder160 .member("extVar".into())161 .hide()162 .value(Val::Func(FuncVal::builtin(builtin_ext_var {163 settings: settings.clone(),164 })))165 .expect("no conflict");166 builder167 .member("native".into())168 .hide()169 .value(Val::Func(FuncVal::builtin(builtin_native {170 settings: settings.clone(),171 })))172 .expect("no conflict");173 builder174 .member("trace".into())175 .hide()176 .value(Val::Func(FuncVal::builtin(builtin_trace { settings })))177 .expect("no conflict");178179 builder180 .member("id".into())181 .hide()182 .value(Val::Func(FuncVal::Id))183 .expect("no conflict");184185 builder.build()186}187188pub trait TracePrinter {189 fn print_trace(&self, loc: CallLocation, value: IStr);190}191192pub struct StdTracePrinter {193 resolver: PathResolver,194}195impl StdTracePrinter {196 pub fn new(resolver: PathResolver) -> Self {197 Self { resolver }198 }199}200impl TracePrinter for StdTracePrinter {201 fn print_trace(&self, loc: CallLocation, value: IStr) {202 eprint!("TRACE:");203 if let Some(loc) = loc.0 {204 let locs = loc.0.map_source_locations(&[loc.1]);205 eprint!(206 " {}:{}",207 match loc.0.source_path().path() {208 Some(p) => self.resolver.resolve(p),209 None => loc.0.source_path().to_string(),210 },211 locs[0].line212 );213 }214 eprintln!(" {value}");215 }216}217218pub struct Settings {219 /// Used for `std.extVar`220 pub ext_vars: HashMap<IStr, TlaArg>,221 /// Used for `std.native`222 pub ext_natives: HashMap<IStr, Cc<TraceBox<dyn Builtin>>>,223 /// Helper to add globals without implementing custom ContextInitializer224 pub globals: GcHashMap<IStr, Thunk<Val>>,225 /// Used for `std.trace`226 pub trace_printer: Box<dyn TracePrinter>,227 /// Used for `std.thisFile`228 pub path_resolver: PathResolver,229}230231fn extvar_source(name: &str, code: impl Into<IStr>) -> Source {232 let source_name = format!("<extvar:{name}>");233 Source::new_virtual(source_name.into(), code.into())234}235236#[derive(Trace, Clone)]237pub struct ContextInitializer {238 // When we don't need to support legacy-this-file, we can reuse same context for all files239 #[cfg(not(feature = "legacy-this-file"))]240 context: Context,241 // Otherwise, we can only keep first stdlib layer, and then stack thisFile on top of it242 #[cfg(feature = "legacy-this-file")]243 stdlib_obj: ObjValue,244 settings: Rc<RefCell<Settings>>,245}246impl ContextInitializer {247 pub fn new(_s: State, resolver: PathResolver) -> Self {248 let settings = Settings {249 ext_vars: Default::default(),250 ext_natives: Default::default(),251 globals: Default::default(),252 trace_printer: Box::new(StdTracePrinter::new(resolver.clone())),253 path_resolver: resolver,254 };255 let settings = Rc::new(RefCell::new(settings));256 Self {257 #[cfg(not(feature = "legacy-this-file"))]258 context: {259 let mut context = ContextBuilder::with_capacity(_s, 1);260 context.bind(261 "std".into(),262 Thunk::evaluated(Val::Obj(stdlib_uncached(settings.clone()))),263 );264 context.build()265 },266 #[cfg(feature = "legacy-this-file")]267 stdlib_obj: stdlib_uncached(settings.clone()),268 settings,269 }270 }271 pub fn settings(&self) -> Ref<Settings> {272 self.settings.borrow()273 }274 pub fn settings_mut(&self) -> RefMut<Settings> {275 self.settings.borrow_mut()276 }277 pub fn add_ext_var(&self, name: IStr, value: Val) {278 self.settings_mut()279 .ext_vars280 .insert(name, TlaArg::Val(value));281 }282 pub fn add_ext_str(&self, name: IStr, value: IStr) {283 self.settings_mut()284 .ext_vars285 .insert(name, TlaArg::String(value));286 }287 pub fn add_ext_code(&self, name: &str, code: impl Into<IStr>) -> Result<()> {288 let code = code.into();289 let source = extvar_source(name, code.clone());290 let parsed = jrsonnet_parser::parse(291 &code,292 &jrsonnet_parser::ParserSettings {293 source: source.clone(),294 },295 )296 .map_err(|e| ImportSyntaxError {297 path: source,298 error: Box::new(e),299 })?;300 // self.data_mut().volatile_files.insert(source_name, code);301 self.settings_mut()302 .ext_vars303 .insert(name.into(), TlaArg::Code(parsed));304 Ok(())305 }306 pub fn add_native(&self, name: IStr, cb: impl Builtin) {307 self.settings_mut()308 .ext_natives309 .insert(name, Cc::new(tb!(cb)));310 }311}312impl jrsonnet_evaluator::ContextInitializer for ContextInitializer {313 #[cfg(not(feature = "legacy-this-file"))]314 fn initialize(&self, _s: State, _source: Source) -> jrsonnet_evaluator::Context {315 let out = self.context.clone();316 let globals = &self.settings().globals;317 if globals.is_empty() {318 return out;319 }320321 let mut out = ContextBuilder::extend(out);322 for (k, v) in globals.iter() {323 out.bind(k.clone(), v.clone());324 }325 out.build()326 }327 #[cfg(feature = "legacy-this-file")]328 fn initialize(&self, s: State, source: Source) -> Context {329 use jrsonnet_evaluator::val::StrValue;330331 let mut builder = ObjValueBuilder::new();332 builder.with_super(self.stdlib_obj.clone());333 builder334 .member("thisFile".into())335 .hide()336 .value(Val::Str(StrValue::Flat(337 match source.source_path().path() {338 Some(p) => self.settings().path_resolver.resolve(p).into(),339 None => source.source_path().to_string().into(),340 },341 )))342 .expect("this object builder is empty");343 let stdlib_with_this_file = builder.build();344345 let mut context = ContextBuilder::with_capacity(s, 1);346 context.bind(347 "std".into(),348 Thunk::evaluated(Val::Obj(stdlib_with_this_file)),349 );350 for (k, v) in self.settings().globals.iter() {351 context.bind(k.clone(), v.clone());352 }353 context.build()354 }355 fn as_any(&self) -> &dyn std::any::Any {356 self357 }358}359360pub trait StateExt {361 /// This method was previously implemented in jrsonnet-evaluator itself362 fn with_stdlib(&self);363 fn add_global(&self, name: IStr, value: Thunk<Val>);364}365366impl StateExt for State {367 fn with_stdlib(&self) {368 let initializer = ContextInitializer::new(self.clone(), PathResolver::new_cwd_fallback());369 self.settings_mut().context_initializer = tb!(initializer)370 }371 fn add_global(&self, name: IStr, value: Thunk<Val>) {372 self.settings()373 .context_initializer374 .as_any()375 .downcast_ref::<ContextInitializer>()376 .expect("not standard context initializer")377 .settings_mut()378 .globals379 .insert(name, value);380 }381}crates/jrsonnet-stdlib/src/sort.rsdiffbeforeafterboth--- a/crates/jrsonnet-stdlib/src/sort.rs
+++ b/crates/jrsonnet-stdlib/src/sort.rs
@@ -1,10 +1,11 @@
use jrsonnet_evaluator::{
error::Result,
- function::{builtin, CallLocation, FuncVal},
+ function::{builtin, FuncVal},
throw,
- val::ArrValue,
- Context, Val,
+ val::{equals, ArrValue},
+ Thunk, Val,
};
+use jrsonnet_gcmodule::Cc;
#[derive(Copy, Clone)]
enum SortKeyType {
@@ -27,12 +28,9 @@
}
}
-fn get_sort_type<T>(
- values: &mut [T],
- key_getter: impl Fn(&mut T) -> &mut Val,
-) -> Result<SortKeyType> {
+fn get_sort_type<T>(values: &[T], key_getter: impl Fn(&T) -> &Val) -> Result<SortKeyType> {
let mut sort_type = SortKeyType::Unknown;
- for i in values.iter_mut() {
+ for i in values.iter() {
let i = key_getter(i);
match (i, sort_type) {
(Val::Str(_), SortKeyType::Unknown) => sort_type = SortKeyType::String,
@@ -47,65 +45,130 @@
Ok(sort_type)
}
+fn sort_identity(mut values: Vec<Val>) -> Result<Vec<Val>> {
+ // Fast path, identity key getter
+ let sort_type = get_sort_type(&values, |k| k)?;
+ match sort_type {
+ SortKeyType::Number => values.sort_unstable_by_key(|v| match v {
+ Val::Num(n) => NonNaNf64(*n),
+ _ => unreachable!(),
+ }),
+ SortKeyType::String => values.sort_unstable_by_key(|v| match v {
+ Val::Str(s) => s.clone(),
+ _ => unreachable!(),
+ }),
+ SortKeyType::Unknown => unreachable!(),
+ };
+ Ok(values)
+}
+
+fn sort_keyf(values: ArrValue, keyf: FuncVal) -> Result<Vec<Thunk<Val>>> {
+ // Slow path, user provided key getter
+ let mut vk = Vec::with_capacity(values.len());
+ for value in values.iter_lazy() {
+ vk.push((
+ value.clone(),
+ keyf.evaluate_simple(&(value.clone(),), false)?,
+ ));
+ }
+ let sort_type = get_sort_type(&mut vk, |v| &v.1)?;
+ match sort_type {
+ SortKeyType::Number => vk.sort_by_key(|v| match v.1 {
+ Val::Num(n) => NonNaNf64(n),
+ _ => unreachable!(),
+ }),
+ SortKeyType::String => vk.sort_by_key(|v| match &v.1 {
+ Val::Str(s) => s.clone(),
+ _ => unreachable!(),
+ }),
+ SortKeyType::Unknown => unreachable!(),
+ };
+ Ok(vk.into_iter().map(|v| v.0).collect())
+}
+
/// * `key_getter` - None, if identity sort required
-pub fn sort(ctx: Context, mut values: Vec<Val>, key_getter: FuncVal) -> Result<Vec<Val>> {
+pub fn sort(values: ArrValue, key_getter: FuncVal) -> Result<ArrValue> {
if values.len() <= 1 {
return Ok(values);
}
if key_getter.is_identity() {
- // Fast path, identity key getter
- let sort_type = get_sort_type(&mut values, |k| k)?;
- match sort_type {
- SortKeyType::Number => values.sort_unstable_by_key(|v| match v {
- Val::Num(n) => NonNaNf64(*n),
- _ => unreachable!(),
- }),
- SortKeyType::String => values.sort_unstable_by_key(|v| match v {
- Val::Str(s) => s.clone(),
- _ => unreachable!(),
- }),
- SortKeyType::Unknown => unreachable!(),
- };
- Ok(values)
+ Ok(ArrValue::eager(sort_identity(
+ values.iter().collect::<Result<Vec<Val>>>()?,
+ )?))
} else {
- // Slow path, user provided key getter
- let mut vk = Vec::with_capacity(values.len());
- for value in values.iter() {
- vk.push((
- value.clone(),
- key_getter.evaluate(
- ctx.clone(),
- CallLocation::native(),
- &(value.clone(),),
- true,
- )?,
- ));
- }
- let sort_type = get_sort_type(&mut vk, |v| &mut v.1)?;
- match sort_type {
- SortKeyType::Number => vk.sort_by_key(|v| match v.1 {
- Val::Num(n) => NonNaNf64(n),
- _ => unreachable!(),
- }),
- SortKeyType::String => vk.sort_by_key(|v| match &v.1 {
- Val::Str(s) => s.clone(),
- _ => unreachable!(),
- }),
- SortKeyType::Unknown => unreachable!(),
- };
- Ok(vk.into_iter().map(|v| v.0).collect())
+ Ok(ArrValue::lazy(Cc::new(sort_keyf(values, key_getter)?)))
}
}
#[builtin]
#[allow(non_snake_case)]
-pub fn builtin_sort(ctx: Context, arr: ArrValue, keyF: Option<FuncVal>) -> Result<ArrValue> {
+pub fn builtin_sort(arr: ArrValue, keyF: Option<FuncVal>) -> Result<ArrValue> {
if arr.len() <= 1 {
return Ok(arr);
}
- Ok(ArrValue::eager(super::sort::sort(
- ctx,
- arr.iter().collect::<Result<Vec<_>>>()?,
+ Ok(super::sort::sort(
+ arr,
keyF.unwrap_or_else(FuncVal::identity),
- )?))
+ )?)
+}
+
+fn uniq_identity(arr: Vec<Val>) -> Result<Vec<Val>> {
+ let mut out = Vec::new();
+ let mut last = arr[0].clone();
+ out.push(last.clone());
+ for next in arr.into_iter().skip(1) {
+ if !equals(&last, &next)? {
+ out.push(next.clone());
+ }
+ last = next;
+ }
+ Ok(out)
+}
+
+fn uniq_keyf(arr: ArrValue, keyf: FuncVal) -> Result<Vec<Thunk<Val>>> {
+ let mut out = Vec::new();
+ let last_value = arr.get_lazy(0).unwrap();
+ let mut last_key = keyf.evaluate_simple(&(last_value.clone(),), false)?;
+ out.push(last_value.clone());
+
+ for next in arr.iter_lazy().skip(1) {
+ let next_key = keyf.evaluate_simple(&(next.clone(),), false)?;
+ if !equals(&last_key, &next_key)? {
+ out.push(next.clone());
+ }
+ last_key = next_key;
+ }
+ Ok(out)
+}
+
+#[builtin]
+#[allow(non_snake_case)]
+pub fn builtin_uniq(arr: ArrValue, keyF: Option<FuncVal>) -> Result<ArrValue> {
+ if arr.len() <= 1 {
+ return Ok(arr);
+ }
+ let keyF = keyF.unwrap_or(FuncVal::identity());
+ if keyF.is_identity() {
+ Ok(ArrValue::eager(uniq_identity(
+ arr.iter().collect::<Result<Vec<Val>>>()?,
+ )?))
+ } else {
+ Ok(ArrValue::lazy(Cc::new(uniq_keyf(arr, keyF)?)))
+ }
+}
+
+#[builtin]
+#[allow(non_snake_case)]
+pub fn builtin_set(arr: ArrValue, keyF: Option<FuncVal>) -> Result<ArrValue> {
+ let keyF = keyF.unwrap_or(FuncVal::identity());
+ if keyF.is_identity() {
+ let arr = arr.iter().collect::<Result<Vec<Val>>>()?;
+ let arr = sort_identity(arr)?;
+ let arr = uniq_identity(arr)?;
+ Ok(ArrValue::eager(arr))
+ } else {
+ let arr = sort_keyf(arr, keyF.clone())?;
+ let arr = uniq_keyf(ArrValue::lazy(Cc::new(arr)), keyF)?;
+ Ok(ArrValue::lazy(Cc::new(arr)))
+ }
}
crates/jrsonnet-stdlib/src/std.jsonnetdiffbeforeafterboth--- a/crates/jrsonnet-stdlib/src/std.jsonnet
+++ b/crates/jrsonnet-stdlib/src/std.jsonnet
@@ -196,19 +196,6 @@
aux(value),
- uniq(arr, keyF=id)::
- local f(a, b) =
- if std.length(a) == 0 then
- [b]
- else if keyF(a[std.length(a) - 1]) == keyF(b) then
- a
- else
- a + [b];
- std.foldl(f, arr, []),
-
- set(arr, keyF=id)::
- std.uniq(std.sort(arr, keyF), keyF),
-
setUnion(a, b, keyF=id)::
// NOTE: order matters, values in `a` win
local aux(a, b, i, j, acc) =