difftreelog
feat change preserved field ordering sort
in: master
Per discussion in https://github.com/google/jsonnet/issues/903
1 file changed
crates/jrsonnet-evaluator/src/obj.rsdiffbeforeafterboth1use std::{2 cell::RefCell,3 fmt::Debug,4 hash::{Hash, Hasher},5 ptr::addr_of,6};78use gcmodule::{Cc, Trace, Weak};9use jrsonnet_interner::IStr;10use jrsonnet_parser::{ExprLocation, Visibility};11use rustc_hash::FxHashMap;1213use crate::{14 cc_ptr_eq,15 error::{Error::*, LocError},16 function::CallLocation,17 gc::{GcHashMap, GcHashSet, TraceBox},18 operator::evaluate_add_op,19 throw, weak_ptr_eq, weak_raw, LazyBinding, Result, State, Thunk, Unbound, Val,20};2122#[cfg(not(feature = "exp-preserve-order"))]23mod ordering {24 #![allow(25 // This module works as stub for preserve-order feature26 clippy::unused_self,27 )]2829 use gcmodule::Trace;3031 #[derive(Clone, Copy, Default, Debug, Trace)]32 pub struct FieldIndex;33 impl FieldIndex {34 pub const fn next(self) -> Self {35 Self36 }37 }3839 #[derive(Clone, Copy, Default, Debug, Trace)]40 pub struct SuperDepth;41 impl SuperDepth {42 pub const fn deeper(self) -> Self {43 Self44 }45 }4647 #[derive(Clone, Copy)]48 pub struct FieldSortKey;49 impl FieldSortKey {50 pub const fn new(_: SuperDepth, _: FieldIndex) -> Self {51 Self52 }53 }54}5556#[cfg(feature = "exp-preserve-order")]57mod ordering {58 use std::cmp::Reverse;5960 use gcmodule::Trace;6162 #[derive(Clone, Copy, Default, Debug, Trace, PartialEq, Eq, PartialOrd, Ord)]63 pub struct FieldIndex(u32);64 impl FieldIndex {65 pub fn next(self) -> Self {66 Self(self.0 + 1)67 }68 }6970 #[derive(Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Debug)]71 pub struct SuperDepth(u32);72 impl SuperDepth {73 pub fn deeper(self) -> Self {74 Self(self.0 + 1)75 }76 }7778 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]79 pub struct FieldSortKey(Reverse<SuperDepth>, FieldIndex);80 impl FieldSortKey {81 pub fn new(depth: SuperDepth, index: FieldIndex) -> Self {82 Self(Reverse(depth), index)83 }84 pub fn collide(self, other: Self) -> Self {85 if self.0 .0 > other.0 .0 {86 self87 } else if self.0 .0 < other.0 .0 {88 other89 } else {90 unreachable!("object can't have two fields with same name")91 }92 }93 }94}9596use ordering::*;9798#[allow(clippy::module_name_repetitions)]99#[derive(Debug, Trace)]100pub struct ObjMember {101 pub add: bool,102 pub visibility: Visibility,103 original_index: FieldIndex,104 pub invoke: LazyBinding,105 pub location: Option<ExprLocation>,106}107108pub trait ObjectAssertion: Trace {109 fn run(&self, s: State, super_obj: Option<ObjValue>, this: Option<ObjValue>) -> Result<()>;110}111112// Field => This113type CacheKey = (IStr, WeakObjValue);114115#[derive(Trace)]116enum CacheValue {117 Cached(Val),118 NotFound,119 Pending,120 Errored(LocError),121}122123#[allow(clippy::module_name_repetitions)]124#[derive(Trace)]125#[force_tracking]126pub struct ObjValueInternals {127 sup: Option<ObjValue>,128 this: Option<ObjValue>,129130 assertions: Cc<Vec<TraceBox<dyn ObjectAssertion>>>,131 assertions_ran: RefCell<GcHashSet<ObjValue>>,132 this_entries: Cc<GcHashMap<IStr, ObjMember>>,133 value_cache: RefCell<GcHashMap<CacheKey, CacheValue>>,134}135136#[derive(Clone, Trace)]137pub struct WeakObjValue(#[skip_trace] pub(crate) Weak<ObjValueInternals>);138139impl PartialEq for WeakObjValue {140 fn eq(&self, other: &Self) -> bool {141 weak_ptr_eq(self.0.clone(), other.0.clone())142 }143}144145impl Eq for WeakObjValue {}146impl Hash for WeakObjValue {147 fn hash<H: Hasher>(&self, hasher: &mut H) {148 hasher.write_usize(weak_raw(self.0.clone()) as usize);149 }150}151152#[allow(clippy::module_name_repetitions)]153#[derive(Clone, Trace)]154pub struct ObjValue(pub(crate) Cc<ObjValueInternals>);155impl Debug for ObjValue {156 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {157 if let Some(super_obj) = self.0.sup.as_ref() {158 if f.alternate() {159 write!(f, "{:#?}", super_obj)?;160 } else {161 write!(f, "{:?}", super_obj)?;162 }163 write!(f, " + ")?;164 }165 let mut debug = f.debug_struct("ObjValue");166 for (name, member) in self.0.this_entries.iter() {167 debug.field(name, member);168 }169 debug.finish_non_exhaustive()170 }171}172173impl ObjValue {174 pub fn new(175 sup: Option<Self>,176 this_entries: Cc<GcHashMap<IStr, ObjMember>>,177 assertions: Cc<Vec<TraceBox<dyn ObjectAssertion>>>,178 ) -> Self {179 Self(Cc::new(ObjValueInternals {180 sup,181 this: None,182 assertions,183 assertions_ran: RefCell::new(GcHashSet::new()),184 this_entries,185 value_cache: RefCell::new(GcHashMap::new()),186 }))187 }188 pub fn new_empty() -> Self {189 Self::new(None, Cc::new(GcHashMap::new()), Cc::new(Vec::new()))190 }191 #[must_use]192 pub fn extend_from(&self, sup: Self) -> Self {193 match &self.0.sup {194 None => Self::new(195 Some(sup),196 self.0.this_entries.clone(),197 self.0.assertions.clone(),198 ),199 Some(v) => Self::new(200 Some(v.extend_from(sup)),201 self.0.this_entries.clone(),202 self.0.assertions.clone(),203 ),204 }205 }206 pub(crate) fn extend_with_raw_member(self, key: IStr, value: ObjMember) -> Self {207 let mut new = GcHashMap::with_capacity(1);208 new.insert(key, value);209 Self::new(Some(self), Cc::new(new), Cc::new(Vec::new()))210 }211 pub fn extend_field(&mut self, name: IStr) -> ObjMemberBuilder<ExtendBuilder> {212 ObjMemberBuilder::new(ExtendBuilder(self), name, FieldIndex::default())213 }214215 #[must_use]216 pub fn with_this(&self, this: Self) -> Self {217 Self(Cc::new(ObjValueInternals {218 sup: self.0.sup.clone(),219 assertions: self.0.assertions.clone(),220 assertions_ran: RefCell::new(GcHashSet::new()),221 this: Some(this),222 this_entries: self.0.this_entries.clone(),223 value_cache: RefCell::new(GcHashMap::new()),224 }))225 }226227 pub fn len(&self) -> usize {228 self.fields_visibility()229 .into_iter()230 .filter(|(_, (visible, _))| *visible)231 .count()232 }233234 pub fn is_empty(&self) -> bool {235 if !self.0.this_entries.is_empty() {236 return false;237 }238 self.0.sup.as_ref().map_or(true, Self::is_empty)239 }240241 /// Run callback for every field found in object242 pub(crate) fn enum_fields(243 &self,244 depth: SuperDepth,245 handler: &mut impl FnMut(SuperDepth, &IStr, &ObjMember) -> bool,246 ) -> bool {247 if let Some(s) = &self.0.sup {248 if s.enum_fields(depth.deeper(), handler) {249 return true;250 }251 }252 for (name, member) in self.0.this_entries.iter() {253 if handler(depth, name, member) {254 return true;255 }256 }257 false258 }259260 pub fn fields_visibility(&self) -> FxHashMap<IStr, (bool, FieldSortKey)> {261 let mut out = FxHashMap::default();262 self.enum_fields(SuperDepth::default(), &mut |depth, name, member| {263 let new_sort_key = FieldSortKey::new(depth, member.original_index);264 match member.visibility {265 Visibility::Normal => {266 let entry = out.entry(name.clone());267 let v = entry.or_insert((true, new_sort_key));268 v.1 = new_sort_key;269 }270 Visibility::Hidden => {271 out.insert(name.clone(), (false, new_sort_key));272 }273 Visibility::Unhide => {274 out.insert(name.clone(), (true, new_sort_key));275 }276 };277 false278 });279 out280 }281 pub fn fields_ex(282 &self,283 include_hidden: bool,284 #[cfg(feature = "exp-preserve-order")] preserve_order: bool,285 ) -> Vec<IStr> {286 #[cfg(feature = "exp-preserve-order")]287 if preserve_order {288 let (mut fields, mut keys): (Vec<_>, Vec<_>) = self289 .fields_visibility()290 .into_iter()291 .filter(|(_, (visible, _))| include_hidden || *visible)292 .enumerate()293 .map(|(idx, (k, (_, sk)))| (k, (sk, idx)))294 .unzip();295 keys.sort_unstable_by_key(|v| v.0);296 // Reorder in-place by resulting indexes297 for i in 0..fields.len() {298 let x = fields[i].clone();299 let mut j = i;300 loop {301 let k = keys[j].1;302 keys[j].1 = j;303 if k == i {304 break;305 }306 fields[j] = fields[k].clone();307 j = k308 }309 fields[j] = x;310 }311 return fields;312 }313314 let mut fields: Vec<_> = self315 .fields_visibility()316 .into_iter()317 .filter(|(_, (visible, _))| include_hidden || *visible)318 .map(|(k, _)| k)319 .collect();320 fields.sort_unstable();321 fields322 }323 pub fn fields(&self, #[cfg(feature = "exp-preserve-order")] preserve_order: bool) -> Vec<IStr> {324 self.fields_ex(325 false,326 #[cfg(feature = "exp-preserve-order")]327 preserve_order,328 )329 }330331 pub fn field_visibility(&self, name: IStr) -> Option<Visibility> {332 if let Some(m) = self.0.this_entries.get(&name) {333 Some(match &m.visibility {334 Visibility::Normal => self335 .0336 .sup337 .as_ref()338 .and_then(|super_obj| super_obj.field_visibility(name))339 .unwrap_or(Visibility::Normal),340 v => *v,341 })342 } else if let Some(super_obj) = &self.0.sup {343 super_obj.field_visibility(name)344 } else {345 None346 }347 }348349 fn has_field_include_hidden(&self, name: IStr) -> bool {350 if self.0.this_entries.contains_key(&name) {351 true352 } else if let Some(super_obj) = &self.0.sup {353 super_obj.has_field_include_hidden(name)354 } else {355 false356 }357 }358359 pub fn has_field_ex(&self, name: IStr, include_hidden: bool) -> bool {360 if include_hidden {361 self.has_field_include_hidden(name)362 } else {363 self.has_field(name)364 }365 }366 pub fn has_field(&self, name: IStr) -> bool {367 self.field_visibility(name)368 .map_or(false, |v| v.is_visible())369 }370371 pub fn get(&self, s: State, key: IStr) -> Result<Option<Val>> {372 self.run_assertions(s.clone())?;373 self.get_raw(s, key, self.0.this.clone().unwrap_or_else(|| self.clone()))374 }375376 // pub fn extend_with(self, key: )377378 fn get_raw(&self, s: State, key: IStr, real_this: Self) -> Result<Option<Val>> {379 let cache_key = (key.clone(), WeakObjValue(real_this.0.downgrade()));380381 if let Some(v) = self.0.value_cache.borrow().get(&cache_key) {382 return Ok(match v {383 CacheValue::Cached(v) => Some(v.clone()),384 CacheValue::NotFound => None,385 CacheValue::Pending => throw!(InfiniteRecursionDetected),386 CacheValue::Errored(e) => return Err(e.clone()),387 });388 }389 self.0390 .value_cache391 .borrow_mut()392 .insert(cache_key.clone(), CacheValue::Pending);393 let fill_error = |e: LocError| {394 self.0395 .value_cache396 .borrow_mut()397 .insert(cache_key.clone(), CacheValue::Errored(e.clone()));398 e399 };400 let value = match (self.0.this_entries.get(&key), &self.0.sup) {401 (Some(k), None) => Ok(Some(402 self.evaluate_this(s, k, real_this).map_err(fill_error)?,403 )),404 (Some(k), Some(super_obj)) => {405 let our = self406 .evaluate_this(s.clone(), k, real_this.clone())407 .map_err(fill_error)?;408 if k.add {409 super_obj410 .get_raw(s.clone(), key, real_this)411 .map_err(fill_error)?412 .map_or(Ok(Some(our.clone())), |v| {413 Ok(Some(evaluate_add_op(s.clone(), &v, &our)?))414 })415 } else {416 Ok(Some(our))417 }418 }419 (None, Some(super_obj)) => super_obj.get_raw(s, key, real_this),420 (None, None) => Ok(None),421 }422 .map_err(fill_error)?;423 self.0.value_cache.borrow_mut().insert(424 cache_key,425 match &value {426 Some(v) => CacheValue::Cached(v.clone()),427 None => CacheValue::NotFound,428 },429 );430 Ok(value)431 }432 fn evaluate_this(&self, s: State, v: &ObjMember, real_this: Self) -> Result<Val> {433 v.invoke434 .evaluate(s.clone(), self.0.sup.clone(), Some(real_this))?435 .evaluate(s)436 }437438 fn run_assertions_raw(&self, s: State, real_this: &Self) -> Result<()> {439 if self.0.assertions_ran.borrow_mut().insert(real_this.clone()) {440 for assertion in self.0.assertions.iter() {441 if let Err(e) =442 assertion.run(s.clone(), self.0.sup.clone(), Some(real_this.clone()))443 {444 self.0.assertions_ran.borrow_mut().remove(real_this);445 return Err(e);446 }447 }448 if let Some(super_obj) = &self.0.sup {449 super_obj.run_assertions_raw(s, real_this)?;450 }451 }452 Ok(())453 }454 pub fn run_assertions(&self, s: State) -> Result<()> {455 self.run_assertions_raw(s, self)456 }457458 pub fn ptr_eq(a: &Self, b: &Self) -> bool {459 cc_ptr_eq(&a.0, &b.0)460 }461 pub fn downgrade(self) -> WeakObjValue {462 WeakObjValue(self.0.downgrade())463 }464}465466impl PartialEq for ObjValue {467 fn eq(&self, other: &Self) -> bool {468 cc_ptr_eq(&self.0, &other.0)469 }470}471472impl Eq for ObjValue {}473impl Hash for ObjValue {474 fn hash<H: Hasher>(&self, hasher: &mut H) {475 hasher.write_usize(addr_of!(*self.0) as usize);476 }477}478479#[allow(clippy::module_name_repetitions)]480pub struct ObjValueBuilder {481 sup: Option<ObjValue>,482 map: GcHashMap<IStr, ObjMember>,483 assertions: Vec<TraceBox<dyn ObjectAssertion>>,484 next_field_index: FieldIndex,485}486impl ObjValueBuilder {487 pub fn new() -> Self {488 Self::with_capacity(0)489 }490 pub fn with_capacity(capacity: usize) -> Self {491 Self {492 sup: None,493 map: GcHashMap::with_capacity(capacity),494 assertions: Vec::new(),495 next_field_index: FieldIndex::default(),496 }497 }498 pub fn reserve_asserts(&mut self, capacity: usize) -> &mut Self {499 self.assertions.reserve_exact(capacity);500 self501 }502 pub fn with_super(&mut self, super_obj: ObjValue) -> &mut Self {503 self.sup = Some(super_obj);504 self505 }506507 pub fn assert(&mut self, assertion: TraceBox<dyn ObjectAssertion>) -> &mut Self {508 self.assertions.push(assertion);509 self510 }511 pub fn member(&mut self, name: IStr) -> ObjMemberBuilder<ValueBuilder> {512 let field_index = self.next_field_index;513 self.next_field_index = self.next_field_index.next();514 ObjMemberBuilder::new(ValueBuilder(self), name, field_index)515 }516517 pub fn build(self) -> ObjValue {518 ObjValue::new(self.sup, Cc::new(self.map), Cc::new(self.assertions))519 }520}521impl Default for ObjValueBuilder {522 fn default() -> Self {523 Self::with_capacity(0)524 }525}526527#[allow(clippy::module_name_repetitions)]528#[must_use = "value not added unless binding() was called"]529pub struct ObjMemberBuilder<Kind> {530 kind: Kind,531 name: IStr,532 add: bool,533 visibility: Visibility,534 original_index: FieldIndex,535 location: Option<ExprLocation>,536}537538#[allow(clippy::missing_const_for_fn)]539impl<Kind> ObjMemberBuilder<Kind> {540 pub(crate) fn new(kind: Kind, name: IStr, original_index: FieldIndex) -> Self {541 Self {542 kind,543 name,544 original_index,545 add: false,546 visibility: Visibility::Normal,547 location: None,548 }549 }550551 pub const fn with_add(mut self, add: bool) -> Self {552 self.add = add;553 self554 }555 pub fn add(self) -> Self {556 self.with_add(true)557 }558 pub fn with_visibility(mut self, visibility: Visibility) -> Self {559 self.visibility = visibility;560 self561 }562 pub fn hide(self) -> Self {563 self.with_visibility(Visibility::Hidden)564 }565 pub fn with_location(mut self, location: ExprLocation) -> Self {566 self.location = Some(location);567 self568 }569 fn build_member(self, binding: LazyBinding) -> (Kind, IStr, ObjMember) {570 (571 self.kind,572 self.name,573 ObjMember {574 add: self.add,575 visibility: self.visibility,576 original_index: self.original_index,577 invoke: binding,578 location: self.location,579 },580 )581 }582}583584pub struct ValueBuilder<'v>(&'v mut ObjValueBuilder);585impl<'v> ObjMemberBuilder<ValueBuilder<'v>> {586 pub fn value(self, s: State, value: Val) -> Result<()> {587 self.binding(s, LazyBinding::Bound(Thunk::evaluated(value)))588 }589 pub fn bindable(590 self,591 s: State,592 bindable: TraceBox<dyn Unbound<Bound = Thunk<Val>>>,593 ) -> Result<()> {594 self.binding(s, LazyBinding::Bindable(Cc::new(bindable)))595 }596 pub fn binding(self, s: State, binding: LazyBinding) -> Result<()> {597 let (receiver, name, member) = self.build_member(binding);598 let location = member.location.clone();599 let old = receiver.0.map.insert(name.clone(), member);600 if old.is_some() {601 s.push(602 CallLocation(location.as_ref()),603 || format!("field <{}> initializtion", name.clone()),604 || throw!(DuplicateFieldName(name.clone())),605 )?;606 }607 Ok(())608 }609}610611pub struct ExtendBuilder<'v>(&'v mut ObjValue);612impl<'v> ObjMemberBuilder<ExtendBuilder<'v>> {613 pub fn value(self, value: Val) {614 self.binding(LazyBinding::Bound(Thunk::evaluated(value)));615 }616 pub fn bindable(self, bindable: TraceBox<dyn Unbound<Bound = Thunk<Val>>>) {617 self.binding(LazyBinding::Bindable(Cc::new(bindable)));618 }619 pub fn binding(self, binding: LazyBinding) {620 let (receiver, name, member) = self.build_member(binding);621 let new = receiver.0.clone();622 *receiver.0 = new.extend_with_raw_member(name, member);623 }624}