`974f2c15c0a2`

3 files changed

modifiedcrates/jrsonnet-stdlib/src/lib.rsdiff before after both

40pub use strings::*;40pub use strings::*;
41mod misc;41mod misc;
42pub use misc::*;42pub use misc::*;
43mod sets;
44pub use sets::*;
4345
44pub fn stdlib_uncached(settings: Rc<RefCell<Settings>>) -> ObjValue {46pub fn stdlib_uncached(settings: Rc<RefCell<Settings>>) -> ObjValue {
45	let mut builder = ObjValueBuilder::new();47	let mut builder = ObjValueBuilder::new();
141		("length", builtin_length::INST),143		("length", builtin_length::INST),
142		("startsWith", builtin_starts_with::INST),144		("startsWith", builtin_starts_with::INST),
143		("endsWith", builtin_ends_with::INST),145		("endsWith", builtin_ends_with::INST),
146		// Sets
147		("setMember", builtin_set_member::INST),
144	]148	]
145	.iter()149	.iter()
146	.cloned()150	.cloned()

addedcrates/jrsonnet-stdlib/src/sets.rsdiff before after both

--- /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)
+}

modifiedcrates/jrsonnet-stdlib/src/std.jsonnetdiff before after both

--- 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) =