difftreelog
perf implement std.setDiff in 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::TraceBox,11 tb,12 trace::PathResolver,13 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::*;45mod compat;46pub use compat::*;4748pub fn stdlib_uncached(settings: Rc<RefCell<Settings>>) -> ObjValue {49 let mut builder = ObjValueBuilder::new();5051 let expr = expr::stdlib_expr();52 let eval = jrsonnet_evaluator::evaluate(ContextBuilder::dangerous_empty_state().build(), &expr)53 .expect("stdlib.jsonnet should have no errors")54 .as_obj()55 .expect("stdlib.jsonnet should evaluate to object");5657 builder.with_super(eval);5859 for (name, builtin) in [60 // Types61 ("type", builtin_type::INST),62 ("isString", builtin_is_string::INST),63 ("isNumber", builtin_is_number::INST),64 ("isBoolean", builtin_is_boolean::INST),65 ("isObject", builtin_is_object::INST),66 ("isArray", builtin_is_array::INST),67 ("isFunction", builtin_is_function::INST),68 // Arrays69 ("makeArray", builtin_make_array::INST),70 ("repeat", builtin_repeat::INST),71 ("slice", builtin_slice::INST),72 ("map", builtin_map::INST),73 ("flatMap", builtin_flatmap::INST),74 ("filter", builtin_filter::INST),75 ("foldl", builtin_foldl::INST),76 ("foldr", builtin_foldr::INST),77 ("range", builtin_range::INST),78 ("join", builtin_join::INST),79 ("reverse", builtin_reverse::INST),80 ("any", builtin_any::INST),81 ("all", builtin_all::INST),82 ("member", builtin_member::INST),83 ("contains", builtin_contains::INST),84 ("count", builtin_count::INST),85 ("avg", builtin_avg::INST),86 ("removeAt", builtin_remove_at::INST),87 ("remove", builtin_remove::INST),88 // Math89 ("abs", builtin_abs::INST),90 ("sign", builtin_sign::INST),91 ("max", builtin_max::INST),92 ("min", builtin_min::INST),93 ("sum", builtin_sum::INST),94 ("modulo", builtin_modulo::INST),95 ("floor", builtin_floor::INST),96 ("ceil", builtin_ceil::INST),97 ("log", builtin_log::INST),98 ("pow", builtin_pow::INST),99 ("sqrt", builtin_sqrt::INST),100 ("sin", builtin_sin::INST),101 ("cos", builtin_cos::INST),102 ("tan", builtin_tan::INST),103 ("asin", builtin_asin::INST),104 ("acos", builtin_acos::INST),105 ("atan", builtin_atan::INST),106 ("exp", builtin_exp::INST),107 ("mantissa", builtin_mantissa::INST),108 ("exponent", builtin_exponent::INST),109 ("round", builtin_round::INST),110 ("isEven", builtin_is_even::INST),111 ("isOdd", builtin_is_odd::INST),112 ("isInteger", builtin_is_integer::INST),113 ("isDecimal", builtin_is_decimal::INST),114 // Operator115 ("mod", builtin_mod::INST),116 ("primitiveEquals", builtin_primitive_equals::INST),117 ("equals", builtin_equals::INST),118 ("xor", builtin_xor::INST),119 ("xnor", builtin_xnor::INST),120 ("format", builtin_format::INST),121 // Sort122 ("sort", builtin_sort::INST),123 ("uniq", builtin_uniq::INST),124 ("set", builtin_set::INST),125 ("minArray", builtin_min_array::INST),126 ("maxArray", builtin_max_array::INST),127 // Hash128 ("md5", builtin_md5::INST),129 ("sha1", builtin_sha1::INST),130 ("sha256", builtin_sha256::INST),131 ("sha512", builtin_sha512::INST),132 ("sha3", builtin_sha3::INST),133 // Encoding134 ("encodeUTF8", builtin_encode_utf8::INST),135 ("decodeUTF8", builtin_decode_utf8::INST),136 ("base64", builtin_base64::INST),137 ("base64Decode", builtin_base64_decode::INST),138 ("base64DecodeBytes", builtin_base64_decode_bytes::INST),139 // Objects140 ("objectFieldsEx", builtin_object_fields_ex::INST),141 ("objectValues", builtin_object_values::INST),142 ("objectValuesAll", builtin_object_values_all::INST),143 ("objectKeysValues", builtin_object_keys_values::INST),144 ("objectKeysValuesAll", builtin_object_keys_values_all::INST),145 ("objectHasEx", builtin_object_has_ex::INST),146 ("objectRemoveKey", builtin_object_remove_key::INST),147 // Manifest148 ("escapeStringJson", builtin_escape_string_json::INST),149 ("manifestJsonEx", builtin_manifest_json_ex::INST),150 ("manifestYamlDoc", builtin_manifest_yaml_doc::INST),151 ("manifestTomlEx", builtin_manifest_toml_ex::INST),152 // Parsing153 ("parseJson", builtin_parse_json::INST),154 ("parseYaml", builtin_parse_yaml::INST),155 // Strings156 ("codepoint", builtin_codepoint::INST),157 ("substr", builtin_substr::INST),158 ("char", builtin_char::INST),159 ("strReplace", builtin_str_replace::INST),160 ("isEmpty", builtin_is_empty::INST),161 ("equalsIgnoreCase", builtin_equals_ignore_case::INST),162 ("splitLimit", builtin_splitlimit::INST),163 ("asciiUpper", builtin_ascii_upper::INST),164 ("asciiLower", builtin_ascii_lower::INST),165 ("findSubstr", builtin_find_substr::INST),166 ("parseInt", builtin_parse_int::INST),167 #[cfg(feature = "exp-bigint")]168 ("bigint", builtin_bigint::INST),169 ("parseOctal", builtin_parse_octal::INST),170 ("parseHex", builtin_parse_hex::INST),171 // Misc172 ("length", builtin_length::INST),173 ("startsWith", builtin_starts_with::INST),174 ("endsWith", builtin_ends_with::INST),175 // Sets176 ("setMember", builtin_set_member::INST),177 ("setInter", builtin_set_inter::INST),178 ("setDiff", builtin_set_diff::INST),179 // Compat180 ("__compare", builtin___compare::INST),181 ]182 .iter()183 .cloned()184 {185 builder186 .member(name.into())187 .hide()188 .value(Val::Func(FuncVal::StaticBuiltin(builtin)))189 .expect("no conflict");190 }191192 builder193 .member("extVar".into())194 .hide()195 .value(Val::Func(FuncVal::builtin(builtin_ext_var {196 settings: settings.clone(),197 })))198 .expect("no conflict");199 builder200 .member("native".into())201 .hide()202 .value(Val::Func(FuncVal::builtin(builtin_native {203 settings: settings.clone(),204 })))205 .expect("no conflict");206 builder207 .member("trace".into())208 .hide()209 .value(Val::Func(FuncVal::builtin(builtin_trace { settings })))210 .expect("no conflict");211212 builder213 .member("id".into())214 .hide()215 .value(Val::Func(FuncVal::Id))216 .expect("no conflict");217218 builder.build()219}220221pub trait TracePrinter {222 fn print_trace(&self, loc: CallLocation, value: IStr);223}224225pub struct StdTracePrinter {226 resolver: PathResolver,227}228impl StdTracePrinter {229 pub fn new(resolver: PathResolver) -> Self {230 Self { resolver }231 }232}233impl TracePrinter for StdTracePrinter {234 fn print_trace(&self, loc: CallLocation, value: IStr) {235 eprint!("TRACE:");236 if let Some(loc) = loc.0 {237 let locs = loc.0.map_source_locations(&[loc.1]);238 eprint!(239 " {}:{}",240 match loc.0.source_path().path() {241 Some(p) => self.resolver.resolve(p),242 None => loc.0.source_path().to_string(),243 },244 locs[0].line245 );246 }247 eprintln!(" {value}");248 }249}250251pub struct Settings {252 /// Used for `std.extVar`253 pub ext_vars: HashMap<IStr, TlaArg>,254 /// Used for `std.native`255 pub ext_natives: HashMap<IStr, Cc<TraceBox<dyn Builtin>>>,256 /// Used for `std.trace`257 pub trace_printer: Box<dyn TracePrinter>,258 /// Used for `std.thisFile`259 pub path_resolver: PathResolver,260}261262fn extvar_source(name: &str, code: impl Into<IStr>) -> Source {263 let source_name = format!("<extvar:{name}>");264 Source::new_virtual(source_name.into(), code.into())265}266267#[derive(Trace, Clone)]268pub struct ContextInitializer {269 /// When we don't need to support legacy-this-file, we can reuse same context for all files270 #[cfg(not(feature = "legacy-this-file"))]271 context: jrsonnet_evaluator::Context,272 /// For `populate`273 #[cfg(not(feature = "legacy-this-file"))]274 stdlib_thunk: Thunk<Val>,275 /// Otherwise, we can only keep first stdlib layer, and then stack thisFile on top of it276 #[cfg(feature = "legacy-this-file")]277 stdlib_obj: ObjValue,278 settings: Rc<RefCell<Settings>>,279}280impl ContextInitializer {281 pub fn new(_s: State, resolver: PathResolver) -> Self {282 let settings = Settings {283 ext_vars: Default::default(),284 ext_natives: Default::default(),285 trace_printer: Box::new(StdTracePrinter::new(resolver.clone())),286 path_resolver: resolver,287 };288 let settings = Rc::new(RefCell::new(settings));289 let stdlib_obj = stdlib_uncached(settings.clone());290 #[cfg(not(feature = "legacy-this-file"))]291 let stdlib_thunk = Thunk::evaluated(Val::Obj(stdlib_obj));292 Self {293 #[cfg(not(feature = "legacy-this-file"))]294 context: {295 let mut context = ContextBuilder::with_capacity(_s, 1);296 context.bind("std".into(), stdlib_thunk.clone());297 context.build()298 },299 #[cfg(not(feature = "legacy-this-file"))]300 stdlib_thunk,301 #[cfg(feature = "legacy-this-file")]302 stdlib_obj,303 settings,304 }305 }306 pub fn settings(&self) -> Ref<Settings> {307 self.settings.borrow()308 }309 pub fn settings_mut(&self) -> RefMut<Settings> {310 self.settings.borrow_mut()311 }312 pub fn add_ext_var(&self, name: IStr, value: Val) {313 self.settings_mut()314 .ext_vars315 .insert(name, TlaArg::Val(value));316 }317 pub fn add_ext_str(&self, name: IStr, value: IStr) {318 self.settings_mut()319 .ext_vars320 .insert(name, TlaArg::String(value));321 }322 pub fn add_ext_code(&self, name: &str, code: impl Into<IStr>) -> Result<()> {323 let code = code.into();324 let source = extvar_source(name, code.clone());325 let parsed = jrsonnet_parser::parse(326 &code,327 &jrsonnet_parser::ParserSettings {328 source: source.clone(),329 },330 )331 .map_err(|e| ImportSyntaxError {332 path: source,333 error: Box::new(e),334 })?;335 // self.data_mut().volatile_files.insert(source_name, code);336 self.settings_mut()337 .ext_vars338 .insert(name.into(), TlaArg::Code(parsed));339 Ok(())340 }341 pub fn add_native(&self, name: IStr, cb: impl Builtin) {342 self.settings_mut()343 .ext_natives344 .insert(name, Cc::new(tb!(cb)));345 }346}347impl jrsonnet_evaluator::ContextInitializer for ContextInitializer {348 fn reserve_vars(&self) -> usize {349 1350 }351 #[cfg(not(feature = "legacy-this-file"))]352 fn initialize(&self, _s: State, _source: Source) -> jrsonnet_evaluator::Context {353 self.context.clone()354 }355 #[cfg(not(feature = "legacy-this-file"))]356 fn populate(&self, _for_file: Source, builder: &mut ContextBuilder) {357 builder.bind("std".into(), self.stdlib_thunk.clone());358 }359 #[cfg(feature = "legacy-this-file")]360 fn populate(&self, source: Source, builder: &mut ContextBuilder) {361 use jrsonnet_evaluator::val::StrValue;362363 let mut std = ObjValueBuilder::new();364 std.with_super(self.stdlib_obj.clone());365 std.member("thisFile".into())366 .hide()367 .value(Val::Str(StrValue::Flat(368 match source.source_path().path() {369 Some(p) => self.settings().path_resolver.resolve(p).into(),370 None => source.source_path().to_string().into(),371 },372 )))373 .expect("this object builder is empty");374 let stdlib_with_this_file = std.build();375376 builder.bind(377 "std".into(),378 Thunk::evaluated(Val::Obj(stdlib_with_this_file)),379 );380 }381 fn as_any(&self) -> &dyn std::any::Any {382 self383 }384}385386pub trait StateExt {387 /// This method was previously implemented in jrsonnet-evaluator itself388 fn with_stdlib(&self);389}390391impl StateExt for State {392 fn with_stdlib(&self) {393 let initializer = ContextInitializer::new(self.clone(), PathResolver::new_cwd_fallback());394 self.settings_mut().context_initializer = tb!(initializer)395 }396}crates/jrsonnet-stdlib/src/sets.rsdiffbeforeafterboth--- a/crates/jrsonnet-stdlib/src/sets.rs
+++ b/crates/jrsonnet-stdlib/src/sets.rs
@@ -71,3 +71,48 @@
}
Ok(ArrValue::lazy(out))
}
+#[builtin]
+#[allow(non_snake_case, clippy::redundant_closure)]
+pub fn builtin_set_diff(a: ArrValue, b: ArrValue, keyF: Option<FuncVal>) -> Result<ArrValue> {
+ let mut a = a.iter_lazy();
+ let mut b = b.iter_lazy();
+
+ let keyF = keyF
+ .unwrap_or(FuncVal::identity())
+ .into_native::<((Thunk<Val>,), Val)>();
+ let keyF = |v| keyF(v);
+
+ let mut av = a.next();
+ let mut bv = b.next();
+ let mut ak = av.clone().map(keyF).transpose()?;
+ let mut bk = bv.map(keyF).transpose()?;
+
+ let mut out = Vec::new();
+ while let (Some(ac), Some(bc)) = (&ak, &bk) {
+ match evaluate_compare_op(ac, bc, BinaryOpType::Lt)? {
+ Ordering::Less => {
+ // In a, but not in b
+ out.push(av.clone().expect("ak != None"));
+ av = a.next();
+ ak = av.clone().map(keyF).transpose()?;
+ }
+ Ordering::Greater => {
+ bv = b.next();
+ bk = bv.map(keyF).transpose()?;
+ }
+ Ordering::Equal => {
+ av = a.next();
+ ak = av.clone().map(keyF).transpose()?;
+ bv = b.next();
+ bk = bv.map(keyF).transpose()?;
+ }
+ };
+ }
+ while let Some(ac) = &ak {
+ // In a, but not in b
+ out.push(av.clone().expect("ak != None"));
+ av = a.next();
+ ak = av.clone().map(keyF).transpose()?;
+ }
+ Ok(ArrValue::lazy(out))
+}
crates/jrsonnet-stdlib/src/std.jsonnetdiffbeforeafterboth--- a/crates/jrsonnet-stdlib/src/std.jsonnet
+++ b/crates/jrsonnet-stdlib/src/std.jsonnet
@@ -214,21 +214,6 @@
aux(a, b, i, j + 1, acc + [b[j]]) tailstrict;
aux(a, b, 0, 0, []),
- setDiff(a, b, keyF=id)::
- local aux(a, b, i, j, acc) =
- if i >= std.length(a) then
- acc
- else if j >= std.length(b) then
- acc + a[i:]
- else
- if keyF(a[i]) == keyF(b[j]) then
- aux(a, b, i + 1, j + 1, acc) tailstrict
- else if keyF(a[i]) < keyF(b[j]) then
- aux(a, b, i + 1, j, acc + [a[i]]) tailstrict
- else
- aux(a, b, i, j + 1, acc) tailstrict;
- aux(a, b, 0, 0, []) tailstrict,
-
mergePatch(target, patch)::
if std.isObject(patch) then
local target_object =