difftreelog
perf implement std.setMember in native
in: master
3 files changed
crates/jrsonnet-stdlib/src/lib.rsdiffbeforeafterboth--- a/crates/jrsonnet-stdlib/src/lib.rs
+++ b/crates/jrsonnet-stdlib/src/lib.rs
@@ -40,6 +40,8 @@
pub use strings::*;
mod misc;
pub use misc::*;
+mod sets;
+pub use sets::*;
pub fn stdlib_uncached(settings: Rc<RefCell<Settings>>) -> ObjValue {
let mut builder = ObjValueBuilder::new();
@@ -141,6 +143,8 @@
("length", builtin_length::INST),
("startsWith", builtin_starts_with::INST),
("endsWith", builtin_ends_with::INST),
+ // Sets
+ ("setMember", builtin_set_member::INST),
]
.iter()
.cloned()
crates/jrsonnet-stdlib/src/sets.rsdiffbeforeafterboth1use std::cmp::Ordering;23use jrsonnet_evaluator::{4 error::Result,5 function::{builtin, FuncVal},6 operator::evaluate_compare_op,7 val::ArrValue,8 Val,9};10use jrsonnet_parser::BinaryOpType;1112#[builtin]13#[allow(non_snake_case)]14pub fn builtin_set_member(x: Val, arr: ArrValue, keyF: Option<FuncVal>) -> Result<bool> {15 let mut low = 0;16 let mut high = arr.len();1718 let keyF = keyF.unwrap_or(FuncVal::Id).into_native::<((Val,), Val)>();1920 let x = keyF(x)?;2122 while low < high {23 let middle = (high + low) / 2;24 match evaluate_compare_op(&arr.get(middle)?.expect("in bounds"), &x, BinaryOpType::Lt)? {25 Ordering::Less => low = middle + 1,26 Ordering::Equal => return Ok(true),27 Ordering::Greater => high = middle,28 }29 }30 Ok(false)31}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) =