difftreelog
perf implement std.setMember 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::{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::*;4344pub fn stdlib_uncached(settings: Rc<RefCell<Settings>>) -> ObjValue {45 let mut builder = ObjValueBuilder::new();4647 let expr = expr::stdlib_expr();48 let eval = jrsonnet_evaluator::evaluate(ContextBuilder::dangerous_empty_state().build(), &expr)49 .expect("stdlib.jsonnet should have no errors")50 .as_obj()51 .expect("stdlib.jsonnet should evaluate to object");5253 builder.with_super(eval);5455 for (name, builtin) in [56 // Types57 ("type", builtin_type::INST),58 ("isString", builtin_is_string::INST),59 ("isNumber", builtin_is_number::INST),60 ("isBoolean", builtin_is_boolean::INST),61 ("isObject", builtin_is_object::INST),62 ("isArray", builtin_is_array::INST),63 ("isFunction", builtin_is_function::INST),64 // Arrays65 ("makeArray", builtin_make_array::INST),66 ("repeat", builtin_repeat::INST),67 ("slice", builtin_slice::INST),68 ("map", builtin_map::INST),69 ("flatMap", builtin_flatmap::INST),70 ("filter", builtin_filter::INST),71 ("foldl", builtin_foldl::INST),72 ("foldr", builtin_foldr::INST),73 ("range", builtin_range::INST),74 ("join", builtin_join::INST),75 ("reverse", builtin_reverse::INST),76 ("any", builtin_any::INST),77 ("all", builtin_all::INST),78 ("member", builtin_member::INST),79 ("count", builtin_count::INST),80 // Math81 ("abs", builtin_abs::INST),82 ("sign", builtin_sign::INST),83 ("max", builtin_max::INST),84 ("min", builtin_min::INST),85 ("modulo", builtin_modulo::INST),86 ("floor", builtin_floor::INST),87 ("ceil", builtin_ceil::INST),88 ("log", builtin_log::INST),89 ("pow", builtin_pow::INST),90 ("sqrt", builtin_sqrt::INST),91 ("sin", builtin_sin::INST),92 ("cos", builtin_cos::INST),93 ("tan", builtin_tan::INST),94 ("asin", builtin_asin::INST),95 ("acos", builtin_acos::INST),96 ("atan", builtin_atan::INST),97 ("exp", builtin_exp::INST),98 ("mantissa", builtin_mantissa::INST),99 ("exponent", builtin_exponent::INST),100 // Operator101 ("mod", builtin_mod::INST),102 ("primitiveEquals", builtin_primitive_equals::INST),103 ("equals", builtin_equals::INST),104 ("format", builtin_format::INST),105 // Sort106 ("sort", builtin_sort::INST),107 // Hash108 ("md5", builtin_md5::INST),109 #[cfg(feature = "exp-more-hashes")]110 ("sha256", builtin_sha256::INST),111 // Encoding112 ("encodeUTF8", builtin_encode_utf8::INST),113 ("decodeUTF8", builtin_decode_utf8::INST),114 ("base64", builtin_base64::INST),115 ("base64Decode", builtin_base64_decode::INST),116 ("base64DecodeBytes", builtin_base64_decode_bytes::INST),117 // Objects118 ("objectFieldsEx", builtin_object_fields_ex::INST),119 ("objectHasEx", builtin_object_has_ex::INST),120 // Manifest121 ("escapeStringJson", builtin_escape_string_json::INST),122 ("manifestJsonEx", builtin_manifest_json_ex::INST),123 ("manifestYamlDoc", builtin_manifest_yaml_doc::INST),124 ("manifestTomlEx", builtin_manifest_toml_ex::INST),125 // Parsing126 ("parseJson", builtin_parse_json::INST),127 ("parseYaml", builtin_parse_yaml::INST),128 // Strings129 ("codepoint", builtin_codepoint::INST),130 ("substr", builtin_substr::INST),131 ("char", builtin_char::INST),132 ("strReplace", builtin_str_replace::INST),133 ("splitLimit", builtin_splitlimit::INST),134 ("asciiUpper", builtin_ascii_upper::INST),135 ("asciiLower", builtin_ascii_lower::INST),136 ("findSubstr", builtin_find_substr::INST),137 ("parseInt", builtin_parse_int::INST),138 ("parseOctal", builtin_parse_octal::INST),139 ("parseHex", builtin_parse_hex::INST),140 // Misc141 ("length", builtin_length::INST),142 ("startsWith", builtin_starts_with::INST),143 ("endsWith", builtin_ends_with::INST),144 ]145 .iter()146 .cloned()147 {148 builder149 .member(name.into())150 .hide()151 .value(Val::Func(FuncVal::StaticBuiltin(builtin)))152 .expect("no conflict");153 }154155 builder156 .member("extVar".into())157 .hide()158 .value(Val::Func(FuncVal::builtin(builtin_ext_var {159 settings: settings.clone(),160 })))161 .expect("no conflict");162 builder163 .member("native".into())164 .hide()165 .value(Val::Func(FuncVal::builtin(builtin_native {166 settings: settings.clone(),167 })))168 .expect("no conflict");169 builder170 .member("trace".into())171 .hide()172 .value(Val::Func(FuncVal::builtin(builtin_trace { settings })))173 .expect("no conflict");174175 builder176 .member("id".into())177 .hide()178 .value(Val::Func(FuncVal::Id))179 .expect("no conflict");180181 builder.build()182}183184pub trait TracePrinter {185 fn print_trace(&self, loc: CallLocation, value: IStr);186}187188pub struct StdTracePrinter {189 resolver: PathResolver,190}191impl StdTracePrinter {192 pub fn new(resolver: PathResolver) -> Self {193 Self { resolver }194 }195}196impl TracePrinter for StdTracePrinter {197 fn print_trace(&self, loc: CallLocation, value: IStr) {198 eprint!("TRACE:");199 if let Some(loc) = loc.0 {200 let locs = loc.0.map_source_locations(&[loc.1]);201 eprint!(202 " {}:{}",203 match loc.0.source_path().path() {204 Some(p) => self.resolver.resolve(p),205 None => loc.0.source_path().to_string(),206 },207 locs[0].line208 );209 }210 eprintln!(" {}", value);211 }212}213214pub struct Settings {215 /// Used for `std.extVar`216 pub ext_vars: HashMap<IStr, TlaArg>,217 /// Used for `std.native`218 pub ext_natives: HashMap<IStr, Cc<TraceBox<dyn Builtin>>>,219 /// Helper to add globals without implementing custom ContextInitializer220 pub globals: GcHashMap<IStr, Thunk<Val>>,221 /// Used for `std.trace`222 pub trace_printer: Box<dyn TracePrinter>,223 /// Used for `std.thisFile`224 pub path_resolver: PathResolver,225}226227fn extvar_source(name: &str, code: impl Into<IStr>) -> Source {228 let source_name = format!("<extvar:{}>", name);229 Source::new_virtual(source_name.into(), code.into())230}231232#[derive(Trace)]233pub struct ContextInitializer {234 // When we don't need to support legacy-this-file, we can reuse same context for all files235 #[cfg(not(feature = "legacy-this-file"))]236 context: Context,237 // Otherwise, we can only keep first stdlib layer, and then stack thisFile on top of it238 #[cfg(feature = "legacy-this-file")]239 stdlib_obj: ObjValue,240 settings: Rc<RefCell<Settings>>,241}242impl ContextInitializer {243 pub fn new(s: State, resolver: PathResolver) -> Self {244 let settings = Settings {245 ext_vars: Default::default(),246 ext_natives: Default::default(),247 globals: Default::default(),248 trace_printer: Box::new(StdTracePrinter::new(resolver.clone())),249 path_resolver: resolver,250 };251 let settings = Rc::new(RefCell::new(settings));252 Self {253 #[cfg(not(feature = "legacy-this-file"))]254 context: {255 let mut context = ContextBuilder::with_capacity(s, 1);256 context.bind(257 "std".into(),258 Thunk::evaluated(Val::Obj(stdlib_uncached(settings.clone()))),259 );260 context.build()261 },262 #[cfg(feature = "legacy-this-file")]263 stdlib_obj: stdlib_uncached(settings.clone()),264 settings,265 }266 }267 pub fn settings(&self) -> Ref<Settings> {268 self.settings.borrow()269 }270 pub fn settings_mut(&self) -> RefMut<Settings> {271 self.settings.borrow_mut()272 }273 pub fn add_ext_var(&self, name: IStr, value: Val) {274 self.settings_mut()275 .ext_vars276 .insert(name, TlaArg::Val(value));277 }278 pub fn add_ext_str(&self, name: IStr, value: IStr) {279 self.settings_mut()280 .ext_vars281 .insert(name, TlaArg::String(value));282 }283 pub fn add_ext_code(&self, name: &str, code: impl Into<IStr>) -> Result<()> {284 let code = code.into();285 let source = extvar_source(name, code.clone());286 let parsed = jrsonnet_parser::parse(287 &code,288 &jrsonnet_parser::ParserSettings {289 source: source.clone(),290 },291 )292 .map_err(|e| ImportSyntaxError {293 path: source,294 error: Box::new(e),295 })?;296 // self.data_mut().volatile_files.insert(source_name, code);297 self.settings_mut()298 .ext_vars299 .insert(name.into(), TlaArg::Code(parsed));300 Ok(())301 }302 pub fn add_native(&self, name: IStr, cb: impl Builtin) {303 self.settings_mut()304 .ext_natives305 .insert(name, Cc::new(tb!(cb)));306 }307}308impl jrsonnet_evaluator::ContextInitializer for ContextInitializer {309 #[cfg(not(feature = "legacy-this-file"))]310 fn initialize(&self, _s: State, _source: Source) -> jrsonnet_evaluator::Context {311 let out = self.context.clone();312 let globals = &self.settings().globals;313 if globals.is_empty() {314 return out;315 }316317 let mut out = ContextBuilder::extend(out);318 for (k, v) in globals.iter() {319 out.bind(k.clone(), v.clone());320 }321 out.build()322 }323 #[cfg(feature = "legacy-this-file")]324 fn initialize(&self, s: State, source: Source) -> Context {325 use jrsonnet_evaluator::val::StrValue;326327 let mut builder = ObjValueBuilder::new();328 builder.with_super(self.stdlib_obj.clone());329 builder330 .member("thisFile".into())331 .hide()332 .value(Val::Str(StrValue::Flat(333 match source.source_path().path() {334 Some(p) => self.settings().path_resolver.resolve(p).into(),335 None => source.source_path().to_string().into(),336 },337 )))338 .expect("this object builder is empty");339 let stdlib_with_this_file = builder.build();340341 let mut context = ContextBuilder::with_capacity(s, 1);342 context.bind(343 "std".into(),344 Thunk::evaluated(Val::Obj(stdlib_with_this_file)),345 );346 for (k, v) in self.settings().globals.iter() {347 context.bind(k.clone(), v.clone());348 }349 context.build()350 }351 fn as_any(&self) -> &dyn std::any::Any {352 self353 }354}355356pub trait StateExt {357 /// This method was previously implemented in jrsonnet-evaluator itself358 fn with_stdlib(&self);359 fn add_global(&self, name: IStr, value: Thunk<Val>);360}361362impl StateExt for State {363 fn with_stdlib(&self) {364 let initializer = ContextInitializer::new(self.clone(), PathResolver::new_cwd_fallback());365 self.settings_mut().context_initializer = tb!(initializer)366 }367 fn add_global(&self, name: IStr, value: Thunk<Val>) {368 self.settings()369 .context_initializer370 .as_any()371 .downcast_ref::<ContextInitializer>()372 .expect("not standard context initializer")373 .settings_mut()374 .globals375 .insert(name, value);376 }377}crates/jrsonnet-stdlib/src/sets.rsdiffbeforeafterboth--- /dev/null
+++ b/crates/jrsonnet-stdlib/src/sets.rs
@@ -0,0 +1,31 @@
+use std::cmp::Ordering;
+
+use jrsonnet_evaluator::{
+ error::Result,
+ function::{builtin, FuncVal},
+ operator::evaluate_compare_op,
+ val::ArrValue,
+ Val,
+};
+use jrsonnet_parser::BinaryOpType;
+
+#[builtin]
+#[allow(non_snake_case)]
+pub fn builtin_set_member(x: Val, arr: ArrValue, keyF: Option<FuncVal>) -> Result<bool> {
+ let mut low = 0;
+ let mut high = arr.len();
+
+ let keyF = keyF.unwrap_or(FuncVal::Id).into_native::<((Val,), Val)>();
+
+ let x = keyF(x)?;
+
+ while low < high {
+ let middle = (high + low) / 2;
+ match evaluate_compare_op(&arr.get(middle)?.expect("in bounds"), &x, BinaryOpType::Lt)? {
+ Ordering::Less => low = middle + 1,
+ Ordering::Equal => return Ok(true),
+ Ordering::Greater => high = middle,
+ }
+ }
+ Ok(false)
+}
crates/jrsonnet-stdlib/src/std.jsonnetdiffbeforeafterboth--- a/crates/jrsonnet-stdlib/src/std.jsonnet
+++ b/crates/jrsonnet-stdlib/src/std.jsonnet
@@ -209,10 +209,6 @@
set(arr, keyF=id)::
std.uniq(std.sort(arr, keyF), keyF),
- setMember(x, arr, keyF=id)::
- // TODO(dcunnin): Binary chop for O(log n) complexity
- std.length(std.setInter([x], arr, keyF)) > 0,
-
setUnion(a, b, keyF=id)::
// NOTE: order matters, values in `a` win
local aux(a, b, i, j, acc) =