git.delta.rocks / jrsonnet / refs/commits / b89fdd32bd3a

1//! Static analysis of jsonnet IR.2//!3//! Walks the IR tree and produces a lowered IR (`LExpr`) with named locals resolved to numeric [`LocalId`] and4//! dependency analysis markers for every expression describing which objects and locals the expression depends on5//!6//! ```jsonnet7//! {8//!     a: $, // `a` is top-object-dependent.9//!     b: {10//!         // `b` is NOT object-dependent for the top object: it only references11//!         // things inside itself. `b` is built once per top-level object.12//!         a: $,13//!     },14//! }15//! ```1617use std::rc::Rc;1819use drop_bomb::DropBomb;20use jrsonnet_gcmodule::Acyclic;21use jrsonnet_interner::IStr;22use jrsonnet_ir::{23	ArgsDesc, AssertExpr, AssertStmt, BinaryOp, BinaryOpType, BindSpec, CompSpec, Destruct, Expr,24	ExprParams, FieldName, ForSpecData, IfElse, IfSpecData, ImportKind, LiteralType, NumValue,25	ObjBody, ObjComp, ObjMembers, Slice, SliceDesc, Span, Spanned, UnaryOpType, Visibility,26	function::FunctionSignature,27};28use rustc_hash::FxHashMap;29use smallvec::SmallVec;3031use crate::{32	arr::arridx,33	error::{format_found, suggest_names},34};3536#[derive(Debug, Clone, Copy)]37#[must_use]38pub struct AnalysisResult {39	/// Highest object, on which identity the value is dependent. `u32::MAX` = not dependent at all40	pub object_dependent_depth: u32,41	/// Highest local frame, on which this value depends. `u32::MAX` = not dependent at all42	pub local_dependent_depth: u32,43}4445impl Default for AnalysisResult {46	fn default() -> Self {47		Self {48			object_dependent_depth: u32::MAX,49			local_dependent_depth: u32::MAX,50		}51	}52}5354impl AnalysisResult {55	fn depend_on_object(&mut self, depth: u32) {56		if depth < self.object_dependent_depth {57			self.object_dependent_depth = depth;58		}59	}60	fn depend_on_local(&mut self, depth: u32) {61		if depth < self.local_dependent_depth {62			self.local_dependent_depth = depth;63		}64	}65	fn taint_by(&mut self, other: AnalysisResult) {66		self.depend_on_object(other.object_dependent_depth);67		self.depend_on_local(other.local_dependent_depth);68	}69}7071#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Acyclic)]72pub struct LocalId(pub u32);7374impl LocalId {75	fn idx(self) -> usize {76		self.0 as usize77	}78	fn defined_before(self, other: Self) -> bool {79		self.0 < other.080	}81}8283#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Acyclic)]84pub enum LSlot {85	/// Enclosing frame locals (sibling letrec, params, etc.).86	Local(LocalSlot),87	/// Enclosing closure's capture pack.88	Capture(CaptureSlot),89}9091#[derive(Debug, Acyclic)]92pub struct ClosureShape {93	pub captures: Box<[LSlot]>,94	pub n_locals: u16,95}9697struct LocalDefinition {98	name: IStr,99	span: Option<Span>,100	/// At which frame depth this local was defined101	defined_at_depth: u32,102	/// Min frame depth, at which this local was used. `u32::MAX` = not used at all.103	/// This check won't catch unused argument closures, i.e:104	/// ```jsonnet105	/// local106	///     a = b,107	///     b = a,108	/// ; 2 + 2109	///110	/// ```111	/// Both `a` and `b` here are "used", but the whole closure was not used here.112	used_at_depth: u32,113	/// Used as part of the current frame closure114	used_by_sibling: bool,115	/// Analysys result for value of this local116	analysis: AnalysisResult,117	/// Has `analysis` been filled in?118	/// For sanity checking, locals are initialized in batchs, use `first_uninitialized_local`119	analyzed: bool,120	/// During walk over uninitialized vars, we can't refer to analysis results of other locals,121	/// but we need to. To make that work, for each variable in variable frame we capture its closure,122	/// by looking at referenced variables.123	scratch_referenced: bool,124}125126impl LocalDefinition {127	fn use_at(&mut self, depth: u32) {128		if depth == self.defined_at_depth {129			self.used_by_sibling = true;130			return;131		}132		if depth < self.used_at_depth {133			self.used_at_depth = depth;134		}135	}136}137138#[derive(Debug, Acyclic)]139pub enum LExpr {140	Slot(LSlot),141	Null,142	Bool(bool),143	Str(IStr),144	Num(NumValue),145	Arr {146		shape: ClosureShape,147		items: Rc<Vec<LExpr>>,148	},149	ArrComp(Box<LArrComp>),150	Obj(LObjBody),151	ObjExtend(Box<LExpr>, LObjBody),152	UnaryOp(UnaryOpType, Box<LExpr>),153	BinaryOp {154		lhs: Box<LExpr>,155		op: BinaryOpType,156		rhs: Box<LExpr>,157	},158	AssertExpr {159		assert: Rc<LAssertStmt>,160		rest: Box<LExpr>,161	},162	Error(Span, Box<LExpr>),163	LocalExpr(Box<LLocalExpr>),164	Import {165		kind: Spanned<ImportKind>,166		kind_span: Span,167		path: IStr,168	},169	Apply {170		applicable: Box<LExpr>,171		args: Spanned<LArgsDesc>,172		tailstrict: bool,173	},174	Index {175		indexable: Box<LExpr>,176		parts: Vec<LIndexPart>,177	},178	Function(Rc<LFunction>),179	IdentityFunction,180	IfElse {181		cond: Box<LExpr>,182		cond_then: Box<LExpr>,183		cond_else: Option<Box<LExpr>>,184	},185	Slice(Box<LSliceExpr>),186	Super,187188	/// Allows partial evaluation of broken expression tree,189	/// expressions with failed static analysis end up here190	BadLocal(&'static str),191}192193#[derive(Debug, Acyclic)]194pub struct LLocalExpr {195	pub frame_shape: ClosureShape,196	pub binds: Vec<LBind>,197	pub body: LExpr,198}199200#[derive(Debug, Acyclic)]201pub struct LFunction {202	pub name: Option<IStr>,203	pub params: Vec<LParam>,204	pub signature: FunctionSignature,205206	pub body_shape: ClosureShape,207	pub body: Rc<LExpr>,208}209210#[derive(Debug, Acyclic)]211pub struct LParam {212	pub name: Option<IStr>,213	pub destruct: LDestruct,214215	pub default: Option<(ClosureShape, Rc<LExpr>)>,216}217218#[derive(Debug, Acyclic)]219pub struct LBind {220	pub destruct: LDestruct,221	pub value_shape: ClosureShape,222	pub value: Rc<LExpr>,223}224225#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, Acyclic)]226pub struct CaptureSlot(pub(crate) u16);227#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, Acyclic)]228pub struct LocalSlot(pub(crate) u16);229230#[derive(Debug, Acyclic)]231pub enum LDestruct {232	Full(LocalSlot),233	#[cfg(feature = "exp-destruct")]234	Skip,235	#[cfg(feature = "exp-destruct")]236	Array {237		start: Vec<LDestruct>,238		rest: Option<LDestructRest>,239		end: Vec<LDestruct>,240	},241	#[cfg(feature = "exp-destruct")]242	Object {243		fields: Vec<LDestructField>,244		rest: Option<LDestructRest>,245	},246}247248#[derive(Debug, Clone, Copy, Acyclic)]249pub enum LDestructRest {250	Keep(LocalSlot),251	Drop,252}253254#[derive(Debug, Acyclic)]255pub struct LDestructField {256	pub name: IStr,257	pub into: Option<LDestruct>,258	pub default: Option<(ClosureShape, Rc<LExpr>)>,259}260261impl LDestruct {262	pub fn each_slot<F: FnMut(LocalSlot)>(&self, f: &mut F) {263		match self {264			Self::Full(s) => f(*s),265			#[cfg(feature = "exp-destruct")]266			Self::Skip => {}267			#[cfg(feature = "exp-destruct")]268			Self::Array { start, rest, end } => {269				for d in start {270					d.each_slot(f);271				}272				if let Some(LDestructRest::Keep(s)) = rest {273					f(*s);274				}275				for d in end {276					d.each_slot(f);277				}278			}279			#[cfg(feature = "exp-destruct")]280			Self::Object { fields, rest } => {281				for field in fields {282					if let Some(into) = &field.into {283						into.each_slot(f);284					} else {285						unreachable!("shorthand object destruct must store `into`");286					}287				}288				if let Some(LDestructRest::Keep(s)) = rest {289					f(*s);290				}291			}292		}293	}294295	pub fn slots(&self) -> SmallVec<[LocalSlot; 1]> {296		let mut out = SmallVec::new();297		self.each_slot(&mut |s| out.push(s));298		out299	}300}301302#[derive(Debug, Acyclic)]303pub struct LSliceExpr {304	pub value: LExpr,305	pub start: Option<LExpr>,306	pub end: Option<LExpr>,307	pub step: Option<LExpr>,308}309310#[derive(Debug, Acyclic)]311pub struct LArgsDesc {312	pub unnamed: Vec<Rc<LExpr>>,313	pub names: Vec<IStr>,314	pub values: Vec<Rc<LExpr>>,315}316317#[derive(Debug, Acyclic)]318pub struct LAssertStmt {319	pub cond: Spanned<LExpr>,320	pub message: Option<LExpr>,321}322323#[derive(Debug, Acyclic)]324pub struct LIndexPart {325	pub span: Span,326	pub value: LExpr,327	#[cfg(feature = "exp-null-coaelse")]328	pub null_coaelse: bool,329}330331#[derive(Debug, Acyclic)]332pub enum LObjBody {333	MemberList(LObjMembers),334	ObjComp(Box<LObjComp>),335}336337#[derive(Debug, Acyclic)]338pub struct LObjMembers {339	pub frame_shape: ClosureShape,340	/// If current object identity (`super`/`this`/`$`) is used, `this` should341	/// be saved to the specified local slot.342	pub this: Option<LocalSlot>,343	/// Set if dollar should also be assigned to object identity, `this` should also be set (TODO: proper type-level validation)344	pub set_dollar: bool,345	/// True iff `super` is referenced by this object's members.346	pub uses_super: bool,347348	pub locals: Rc<Vec<LBind>>,349	pub asserts: Option<Rc<LObjAsserts>>,350	pub fields: Vec<LFieldMember>,351}352353#[derive(Debug, Acyclic)]354pub struct LObjComp {355	pub frame_shape: Rc<ClosureShape>,356	pub this: Option<LocalSlot>,357	pub set_dollar: bool,358	pub uses_super: bool,359360	pub locals: Rc<Vec<LBind>>,361	pub field: LFieldMember,362	pub compspecs: Vec<LCompSpec>,363}364365#[derive(Debug, Acyclic)]366pub struct LFieldMember {367	pub name: LFieldName,368	pub plus: bool,369	pub visibility: Visibility,370	pub value: Rc<(ClosureShape, LExpr)>,371}372373#[derive(Debug, Acyclic)]374pub struct LClosure<T: Acyclic> {375	pub shape: ClosureShape,376	pub value: T,377}378379#[derive(Debug, Acyclic)]380pub struct LObjAsserts {381	pub shape: ClosureShape,382	pub asserts: Vec<LAssertStmt>,383}384385#[derive(Debug, Acyclic)]386pub enum LFieldName {387	Fixed(IStr),388	Dyn(LExpr),389}390impl LFieldName {391	fn function_name(&self) -> Option<IStr> {392		match self {393			LFieldName::Fixed(istr) => Some(istr.clone()),394			LFieldName::Dyn(_) => None,395		}396	}397}398399#[derive(Debug, Acyclic)]400pub struct LArrComp {401	pub value_shape: ClosureShape,402	pub value: Rc<LExpr>,403	pub compspecs: Vec<LCompSpec>,404}405406#[derive(Debug, Acyclic)]407pub enum LCompSpec {408	If(LExpr),409	For {410		frame_shape: ClosureShape,411		destruct: LDestruct,412		over: LExpr,413		/// Is `over` does not depend on any variable introduced by an earlier for-spec in this comprehension chain414		loop_invariant: bool,415	},416	#[cfg(feature = "exp-object-iteration")]417	ForObj {418		frame_shape: ClosureShape,419		key: LocalSlot,420		visibility: jrsonnet_ir::Visibility,421		value: LDestruct,422		over: LExpr,423		loop_invariant: bool,424	},425}426427struct FrameAlloc<'s> {428	first_in_frame: LocalId,429	stack: &'s mut AnalysisStack,430	bomb: DropBomb,431}432impl<'s> FrameAlloc<'s> {433	fn new(stack: &'s mut AnalysisStack) -> Self {434		FrameAlloc {435			first_in_frame: stack.next_local_id(),436			stack,437			bomb: DropBomb::new("binding frame state"),438		}439	}440441	fn push_locals_closure(&mut self) -> ClosureOnStack {442		self.stack.push_closure_a(self.first_in_frame)443	}444445	fn define_local(&mut self, name: IStr, span: Option<Span>) -> Option<(LocalId, LocalSlot)> {446		let id = self.stack.next_local_id();447		let stack = self.stack.local_by_name.entry(name.clone()).or_default();448		if let Some(&existing) = stack.last()449			&& !existing.defined_before(self.first_in_frame)450		{451			self.stack.report_error(452				format!("local is already defined in the current frame: {name}"),453				span,454			);455			return None;456		}457		stack.push(id);458		self.stack.local_defs.push(LocalDefinition {459			name,460			span,461			defined_at_depth: self.stack.depth,462			used_at_depth: u32::MAX,463			used_by_sibling: false,464			analysis: AnalysisResult::default(),465			analyzed: false,466			scratch_referenced: false,467		});468		let def = self.stack.defining_closure_mut();469		Some((id, def.define_local(id)))470	}471	fn alloc_bind(&mut self, bind: &BindSpec) -> Option<LDestruct> {472		match bind {473			BindSpec::Field { into, .. } => self.alloc_destruct(into),474			BindSpec::Function { name, .. } => {475				let (_, id) = self.define_local(name.value.clone(), Some(name.span.clone()))?;476				Some(LDestruct::Full(id))477			}478		}479	}480	fn alloc_destruct(&mut self, destruct: &Destruct) -> Option<LDestruct> {481		Some(match destruct {482			Destruct::Full(name) => {483				let (_, id) = self.define_local(name.value.clone(), Some(name.span.clone()))?;484				LDestruct::Full(id)485			}486			#[cfg(feature = "exp-destruct")]487			Destruct::Skip => LDestruct::Skip,488			#[cfg(feature = "exp-destruct")]489			Destruct::Array { start, rest, end } => {490				let start = start491					.iter()492					.map(|d| self.alloc_destruct(d))493					.collect::<Option<Vec<_>>>()?;494				let rest = match rest {495					Some(jrsonnet_ir::DestructRest::Keep(name)) => {496						let (_, id) = self.define_local(name.clone(), None)?;497						Some(LDestructRest::Keep(id))498					}499					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),500					None => None,501				};502				let end = end503					.iter()504					.map(|d| self.alloc_destruct(d))505					.collect::<Option<Vec<_>>>()?;506				LDestruct::Array { start, rest, end }507			}508			#[cfg(feature = "exp-destruct")]509			Destruct::Object { fields, rest } => {510				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());511				// Allocate destruct LocalIds, then analyse defaults512				for (name, into, _default) in fields {513					let into = if let Some(inner) = into {514						self.alloc_destruct(inner)?515					} else {516						let (_, id) = self.define_local(name.clone(), None)?;517						LDestruct::Full(id)518					};519					l_fields.push((name.clone(), into));520				}521				// All locals exist, so defaults can reference any sibling.522				let l_fields: Vec<LDestructField> = l_fields523					.into_iter()524					.zip(fields.iter())525					.map(|((name, into), (_n, _i, default))| {526						let default = match default {527							Some(e) => {528								let mut default_taint = AnalysisResult::default();529								Some(self.stack.in_using_closure(|stack| {530									Rc::new(analyze(&e.value, stack, &mut default_taint))531								}))532							}533							None => None,534						};535						LDestructField {536							name,537							into: Some(into),538							default,539						}540					})541					.collect();542				let rest = match rest {543					Some(jrsonnet_ir::DestructRest::Keep(name)) => {544						let (_, id) = self.define_local(name.clone(), None)?;545						Some(LDestructRest::Keep(id))546					}547					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),548					None => None,549				};550				LDestruct::Object {551					fields: l_fields,552					rest,553				}554			}555		})556	}557558	fn finish(self) -> PendingInit<'s> {559		let Self {560			first_in_frame,561			stack,562			bomb,563		} = self;564		let first_after_frame = stack.next_local_id();565		PendingInit {566			first_after_frame,567			stack,568			closures: Closures {569				referenced: vec![],570				spec_shapes: vec![],571				first_in_frame,572			},573			bomb,574		}575	}576}577578/// Frame state: `LocalIds` allocated, values not yet analysed.579struct PendingInit<'s> {580	first_after_frame: LocalId,581	stack: &'s mut AnalysisStack,582	closures: Closures,583	bomb: DropBomb,584}585586impl<'s> PendingInit<'s> {587	/// Record the analysis of a spec's value: stamp every id bound by the588	/// spec with `analysis`, collect the spec's same-frame references, and589	/// append them to `closures`.590	fn record_spec_init(&mut self, destruct: &LDestruct, analysis: AnalysisResult) {591		let mut refs: SmallVec<[LocalId; 4]> = SmallVec::new();592		for i in self.closures.first_in_frame.0..self.first_after_frame.0 {593			let def = &mut self.stack.local_defs[i as usize];594			if def.scratch_referenced {595				refs.push(LocalId(i));596				def.scratch_referenced = false;597			}598		}599600		let mut ids_count = 0;601		let first_local = self.stack.top_defining_local();602		destruct.each_slot(&mut |slot| {603			ids_count += 1;604			let id = LocalId(first_local.0 + u32::from(slot.0));605			let def = &mut self.stack.local_defs[id.idx()];606			debug_assert!(!def.analyzed, "sanity: local {:?} analysed twice", def.name);607			def.analysis = analysis;608			def.analyzed = true;609		});610		self.closures.push_spec(ids_count, &refs);611	}612	/// After all specs are analysed, propagate dependency information between613	/// siblings to a fix-point, then switch to "body" mode.614	fn finish(self) -> PendingBody<'s> {615		let Self {616			first_after_frame,617			closures,618			stack,619			bomb,620		} = self;621622		debug_assert_eq!(623			first_after_frame,624			stack.next_local_id(),625			"frame initialisation left unfinished locals"626		);627628		debug_assert_eq!(629			closures.spec_shapes.iter().map(|(_, d)| *d).sum::<usize>(),630			(first_after_frame.0 - closures.first_in_frame.0) as usize,631			"closures destruct-id counts must match frame local count"632		);633634		let mut changed = true;635		while changed {636			changed = false;637			for spec in closures.iter_specs() {638				for id_raw in spec.ids.clone() {639					let user = LocalId(id_raw);640					for &used in spec.references {641						changed |= stack.propagate_analysis(user, used);642					}643				}644			}645		}646647		stack.depth += 1;648		PendingBody {649			first_after_frame,650			closures,651			stack,652			bomb,653		}654	}655}656657/// Frame state: values analysed, body not yet walked.658struct PendingBody<'s> {659	first_after_frame: LocalId,660	closures: Closures,661	stack: &'s mut AnalysisStack,662	bomb: DropBomb,663}664impl PendingBody<'_> {665	/// After the body is processed, drop the frame's locals and emit any666	/// "unused local" warnings.667	fn finish(self) {668		let PendingBody {669			first_after_frame,670			closures,671			stack,672			mut bomb,673		} = self;674		bomb.defuse();675		stack.depth -= 1;676677		debug_assert_eq!(678			first_after_frame,679			stack.next_local_id(),680			"nested scopes must be popped before outer frames"681		);682683		let mut changed = true;684		while changed {685			changed = false;686			for spec in closures.iter_specs() {687				// Effective used_at_depth for the spec = min over its ids.688				let mut min_used_at = u32::MAX;689				for id_raw in spec.ids.clone() {690					min_used_at = min_used_at.min(stack.local_defs[id_raw as usize].used_at_depth);691				}692				if min_used_at == u32::MAX {693					continue;694				}695				for &used in spec.references {696					let used_def = &mut stack.local_defs[used.idx()];697					if min_used_at < used_def.used_at_depth {698						used_def.used_at_depth = min_used_at;699						changed = true;700					}701				}702			}703		}704705		let drained: Vec<LocalDefinition> = stack706			.local_defs707			.drain(closures.first_in_frame.idx()..)708			.collect();709		for (i, def) in drained.iter().enumerate().rev() {710			let id = LocalId(closures.first_in_frame.0 + arridx(i));711			let stack_locals = stack712				.local_by_name713				.get_mut(&def.name)714				.expect("local must be in name map");715			let popped = stack_locals.pop().expect("name stack should not be empty");716			debug_assert_eq!(popped, id, "name stack integrity");717			if stack_locals.is_empty() {718				stack.local_by_name.remove(&def.name);719			}720721			if def.used_at_depth == u32::MAX {722				if def.used_by_sibling {723					stack.report_warning(724						format!("local is only referenced by unused siblings: {}", def.name),725						def.span.clone(),726					);727				} else {728					stack.report_warning(format!("unused local: {}", def.name), def.span.clone());729				}730			} else if def.analysis.local_dependent_depth > def.defined_at_depth731				&& def.analysis.object_dependent_depth > def.defined_at_depth732				&& def.defined_at_depth != 0733			{734				// The value doesn't depend on anything defined at or inside735				// this local's scope - can be hoisted, unfortunately not automatically.736				stack.report_warning(737					format!("local could be hoisted to an outer scope: {}", def.name),738					def.span.clone(),739				);740			}741		}742	}743}744745struct Closures {746	/// All the referenced locals, maybe repeated multiple times747	/// It is recorded as continous vec of sets, I.e we have748	/// a = 1, 2, 3749	/// b = 3, 4, 5, 6750	/// And in `referenced` we have `[ 1, 2, 3, 3, 4, 5, 6 ]`. To actually get, which closure refers to which element, see `spec_shapes`...751	/// Flat concatenation of sibling-local references across all specs.752	referenced: Vec<LocalId>,753	/// Amount of elements per closure, for the above case it is a = 3, b = 4, so here754	/// lies `[ 3, 4 ]`755	/// ~~closures: Vec<usize>,~~756	/// Finally, we have destructs.757	/// Because single destruct references single closure, but destructs to multiple locals, we have even more complicated structure.758	/// Luckly, every destruct is not interleaved with each other, so here we can have full list...759	/// Imagine having (LocalId(20), LocalId(21)), we need to save it to the Map, but we know that the numbers are sequential, so here we store number of consequent elements760	/// for each destruct starting from `first_destruct_local`761	/// ~~destructs: Vec<usize>,~~762	///763	/// => two of those fields were merged, as there is currently no per-destruct tracking of closures.764	/// For each spec in order: `(references_count, destruct_ids_count)`.765	/// `references_count` tells us how many entries of `referenced` belong766	/// to this spec; `destruct_ids_count` tells us how many `LocalIds` it767	/// binds.768	spec_shapes: Vec<(usize, usize)>,769	/// This is not a related doccomment, just a continuation of docs for previous fields.770	/// Having771	/// ```jsonnet772	/// local773	///     [a, b, c] = [d, e, f],774	///     [d, e, f] = [a, b, c, h],775	///     h = 1,776	/// ;777	/// ```778	///779	/// We have total of 7 locals780	/// First local here is `a` => `first_destruct_local` = `a`781	/// For first closure `[a, b, c] = [d, e, f]` we have 3 referenced locals = [d, e, f] => `referenced += [d, e, f]`, `closures += 3`; 3 destructs = [a, b, c] => `destructs += 3`782	/// [d, e, f] = [a, b, c, h], => `referenced += [a, b, c, h]`, `closures += 4`, `destructs += 3` (Note that this destruct will fail at runtime,783	///                                                                                               this thing should not care about that, it only captures what the value are referencing)784	/// h = 1 => referenced += [], closures += 0, destructs += 1785	/// And the result is786	///787	/// ```rust,ignore788	/// Closures {789	///     referenced: vec![d, e, f, a, b, c, h]790	///     spec_shapes: vec![(3, 3), (4, 3), (0, 1)],791	///     first_destruct_label: a,792	/// }793	/// ```794	///795	/// Reconstruction of that:796	///797	/// We know that we start with a798	/// We get the first number from destructs: `destructs.shift() == 3` => `destructs = [3, 1]`799	/// 3 elements counting from a => [a, b, c]800	/// Then we take first number from closures: `closures.shift() == 3` => `closures = [4, 0]`801	/// Then we take 3 items from referenced: `referenced.shift()x3 == d, e, f` => `referenced = [a, b, c, h]`802	///803	/// Thus we have [a, b, c] = [d, e, f]804	first_in_frame: LocalId,805}806807struct Closure<'a> {808	references: &'a [LocalId],809	ids: std::ops::Range<u32>,810}811812impl Closures {813	fn push_spec(&mut self, destruct_ids_count: usize, refs: &[LocalId]) {814		self.referenced.extend_from_slice(refs);815		self.spec_shapes.push((refs.len(), destruct_ids_count));816	}817818	fn iter_specs(&self) -> impl Iterator<Item = Closure<'_>> {819		let mut refs = self.referenced.as_slice();820		let mut next_id = self.first_in_frame.0;821		self.spec_shapes.iter().map(move |(refs_len, dest_count)| {822			let (this_refs, rest) = refs.split_at(*refs_len);823			refs = rest;824			let start = next_id;825			next_id += arridx(*dest_count);826			Closure {827				references: this_refs,828				ids: start..next_id,829			}830		})831	}832}833834#[derive(Debug, Clone, Copy, PartialEq, Eq)]835pub enum DiagLevel {836	Error,837	Warning,838}839840#[derive(Debug, Clone, Acyclic)]841pub struct Diagnostic {842	pub level: DiagLevel,843	pub message: String,844	pub span: Option<Span>,845}846847struct DefiningClosure {848	first_local: LocalId,849	n_locals: u16,850}851852impl DefiningClosure {853	fn resolve(&self, target: LocalId) -> Option<LocalSlot> {854		let end = self.first_local.0 + u32::from(self.n_locals);855		if target.0 >= self.first_local.0 && target.0 < end {856			Some(LocalSlot(857				u16::try_from(target.0 - self.first_local.0).expect("local slots overflow"),858			))859		} else {860			None861		}862	}863	fn define_local(&mut self, local: LocalId) -> LocalSlot {864		let slot = self.n_locals;865		let id = self.first_local.0 + u32::from(slot);866		debug_assert_eq!(local.0, id);867		self.n_locals = self.n_locals.checked_add(1).expect("local slots overflow");868		LocalSlot(slot)869	}870}871872/// Per-closure capture computation state.873struct ClosureFrame {874	/// Closure may allocate locals875	defining: Option<DefiningClosure>,876	/// `LocalId` => capture index877	captures: FxHashMap<LocalId, CaptureSlot>,878	/// Capture sources in insertion order; consumed by `pop_closure_frame`.879	capture_sources: Vec<LSlot>,880}881882#[allow(clippy::struct_excessive_bools)]883pub struct AnalysisStack {884	local_defs: Vec<LocalDefinition>,885	/// Shadowing isn't used in jsonnet much, 2 because `SmallVec` allows to store 2 ptr-sized without overhead.886	/// TODO: Add test for this assumption (sizeof(SmallVec<[usize; 1]>) == sizeof(SmallVec<[usize; 2]>))887	local_by_name: FxHashMap<IStr, SmallVec<[LocalId; 2]>>,888889	/// Depth of the current locals frame.890	depth: u32,891	/// Last depth, at which object has appeared. `u32::MAX` = not appeared at all892	last_object_depth: u32,893	/// First depth, at which object has appeared. `u32::MAX` = not appeared at all894	/// $ refers to this object.895	first_object_depth: u32,896897	/// `LocalId` bound to the innermost object's `this`898	this_local: Option<LocalId>,899	/// Outermost object `this`, aka `$`900	dollar_alias: Option<LocalId>,901	/// True iff `self` has been referenced in the current object immediate members (not nested children).902	cur_self_used: bool,903	/// True iff `super` has been referenced in the current object immediate members.904	cur_super_used: bool,905	/// True iff `$` has been referenced anywhere since the outermost object's scope was entered.906	dollar_used: bool,907908	/// Stack of closure frames (innermost on top).909	closure_stack: Vec<ClosureFrame>,910911	diagnostics: Vec<Diagnostic>,912	/// Whenever analysis would be broken due to static analysis error.913	errored: bool,914}915916#[must_use]917struct ClosureOnStack {918	bomb: DropBomb,919}920921impl AnalysisStack {922	pub fn new() -> Self {923		Self {924			local_defs: Vec::new(),925			local_by_name: FxHashMap::default(),926			depth: 0,927			last_object_depth: u32::MAX,928			first_object_depth: u32::MAX,929			this_local: None,930			dollar_alias: None,931			cur_self_used: false,932			cur_super_used: false,933			dollar_used: false,934			closure_stack: Vec::new(),935			diagnostics: Vec::new(),936			errored: false,937		}938	}939940	fn push_root_closure(&mut self, externals: u16) -> ClosureOnStack {941		assert!(942			self.closure_stack.is_empty(),943			"root is only possible with empty stack"944		);945946		self.closure_stack.push(ClosureFrame {947			defining: Some(DefiningClosure {948				first_local: LocalId(0),949				n_locals: externals,950			}),951			captures: FxHashMap::default(),952			capture_sources: Vec::new(),953		});954955		ClosureOnStack {956			bomb: DropBomb::new("root closure"),957		}958	}959960	fn push_closure_a(&mut self, first_local: LocalId) -> ClosureOnStack {961		self.closure_stack.push(ClosureFrame {962			defining: Some(DefiningClosure {963				first_local,964				n_locals: 0,965			}),966			captures: FxHashMap::default(),967			capture_sources: Vec::new(),968		});969		ClosureOnStack {970			bomb: DropBomb::new("closure with locals"),971		}972	}973974	#[inline]975	fn in_using_closure<T>(976		&mut self,977		inner: impl FnOnce(&mut AnalysisStack) -> T,978	) -> (ClosureShape, T) {979		fn push_closure_b(stack: &mut AnalysisStack) -> ClosureOnStack {980			stack.closure_stack.push(ClosureFrame {981				defining: None,982				captures: FxHashMap::default(),983				capture_sources: Vec::new(),984			});985			ClosureOnStack {986				bomb: DropBomb::new("closure with locals"),987			}988		}989		let closure = push_closure_b(self);990		let v = inner(self);991		let shape = self.pop_closure(closure);992		(shape, v)993	}994995	fn pop_closure(&mut self, mut closure: ClosureOnStack) -> ClosureShape {996		closure.bomb.defuse();997		let frame = self.closure_stack.pop().expect("closure frame");998		ClosureShape {999			captures: frame.capture_sources.into_boxed_slice(),1000			n_locals: frame.defining.map(|d| d.n_locals).unwrap_or_default(),1001		}1002	}10031004	/// Resolve a `LocalId` reference to an `LSlot` against the innermost1005	/// closure frame. May insert capture entries up the closure stack as1006	/// needed.1007	fn resolve_to_slot(&mut self, target: LocalId) -> LSlot {1008		let top = self.closure_stack.len();1009		debug_assert!(top > 0, "resolve_to_slot called with no closure frame");1010		Self::resolve_at(&mut self.closure_stack, top - 1, target)1011	}10121013	fn resolve_at(stack: &mut [ClosureFrame], idx: usize, target: LocalId) -> LSlot {1014		if let Some(def) = &stack[idx].defining {1015			if let Some(resolved) = def.resolve(target) {1016				return LSlot::Local(resolved);1017			}1018		} else {1019			// A sibling letrec slot must never be packed as a capture, or1020			// it would read an empty `OnceCell`.1021			for j in (0..idx).rev() {1022				if let Some(def) = &stack[j].defining {1023					if let Some(resolved) = def.resolve(target) {1024						return LSlot::Local(resolved);1025					}1026					break;1027				}1028			}1029		}1030		if let Some(&cap_idx) = stack[idx].captures.get(&target) {1031			return LSlot::Capture(cap_idx);1032		}1033		debug_assert!(idx > 0, "no enclosing closure frame for target {target:?}");1034		let parent_slot = Self::resolve_at(stack, idx - 1, target);1035		let frame = &mut stack[idx];1036		let cap_idx = CaptureSlot(1037			frame1038				.capture_sources1039				.len()1040				.try_into()1041				.expect("frame has more than u16::MAX captures"),1042		);1043		frame.capture_sources.push(parent_slot);1044		frame.captures.insert(target, cap_idx);1045		LSlot::Capture(cap_idx)1046	}10471048	fn next_local_id(&self) -> LocalId {1049		LocalId(arridx(self.local_defs.len()))1050	}10511052	fn report_error(&mut self, msg: impl Into<String>, span: Option<Span>) {1053		self.errored = true;1054		self.diagnostics.push(Diagnostic {1055			level: DiagLevel::Error,1056			message: msg.into(),1057			span,1058		});1059	}1060	fn report_warning(&mut self, msg: impl Into<String>, span: Option<Span>) {1061		self.diagnostics.push(Diagnostic {1062			level: DiagLevel::Warning,1063			message: msg.into(),1064			span,1065		});1066	}10671068	fn use_local(&mut self, name: &IStr, span: Span, taint: &mut AnalysisResult) -> Option<LSlot> {1069		let Some(ids) = self.local_by_name.get(name) else {1070			let names = suggest_names(name, self.local_by_name.keys());1071			self.report_error(1072				format!("undefined local: {name}{}", format_found(&names, "local")),1073				Some(span),1074			);1075			return None;1076		};1077		let id = *ids.last().expect("empty stacks should be removed");1078		let depth = self.depth;1079		let def = &mut self.local_defs[id.idx()];1080		def.use_at(depth);1081		taint.depend_on_local(def.defined_at_depth);1082		if def.analyzed {1083			taint.taint_by(def.analysis);1084		} else {1085			def.scratch_referenced = true;1086		}1087		Some(self.resolve_to_slot(id))1088	}10891090	/// Assign name to the value provided externally, e.g `std`.1091	pub fn define_external_local(&mut self, name: IStr, id: LocalId) {1092		assert!(1093			self.local_defs.iter().all(|d| d.analyzed),1094			"external locals must be defined before the root expression is analysed"1095		);1096		assert_eq!(1097			id,1098			self.next_local_id(),1099			"external local id mismatch for {name} (externals must be defined in allocation order)"1100		);1101		self.local_defs.push(LocalDefinition {1102			name: name.clone(),1103			span: None,1104			defined_at_depth: 0,1105			used_at_depth: u32::MAX,1106			used_by_sibling: false,1107			analysis: AnalysisResult::default(),1108			analyzed: true,1109			scratch_referenced: false,1110		});1111		self.local_by_name.entry(name).or_default().push(id);1112	}11131114	fn defining_closure_mut(&mut self) -> &mut DefiningClosure {1115		self.closure_stack1116			.iter_mut()1117			.rev()1118			.find_map(|c| c.defining.as_mut())1119			.expect("no enclosing defining closure frame")1120	}1121	fn defining_closure(&self) -> &DefiningClosure {1122		self.closure_stack1123			.iter()1124			.rev()1125			.find_map(|c| c.defining.as_ref())1126			.expect("no enclosing defining closure frame")1127	}1128}11291130impl Default for AnalysisStack {1131	fn default() -> Self {1132		Self::new()1133	}1134}11351136impl AnalysisStack {1137	fn top_defining_local(&self) -> LocalId {1138		self.defining_closure().first_local1139	}11401141	/// Merge `used`'s analysis into `user`'s analysis and record that `user`1142	/// transitively depends on `used` (same-frame sibling reference).1143	/// Returns `true` if `user`'s analysis changed.1144	fn propagate_analysis(&mut self, user: LocalId, used: LocalId) -> bool {1145		let (used_analysis, used_defined_at_depth) = {1146			let u = &self.local_defs[used.idx()];1147			(u.analysis, u.defined_at_depth)1148		};1149		let user_def = &mut self.local_defs[user.idx()];1150		let before_obj = user_def.analysis.object_dependent_depth;1151		let before_loc = user_def.analysis.local_dependent_depth;1152		user_def.analysis.taint_by(used_analysis);1153		user_def.analysis.depend_on_local(used_defined_at_depth);1154		before_obj != user_def.analysis.object_dependent_depth1155			|| before_loc != user_def.analysis.local_dependent_depth1156	}1157}11581159mod names {1160	use crate::names;11611162	names! {1163		this: "this",1164	}1165}11661167// Object scope helpers1168impl AnalysisStack {1169	#[inline]1170	fn in_object_scope<T>(1171		&mut self,1172		inner: impl FnOnce(&mut AnalysisStack) -> T,1173	) -> (ObjectUsage, ClosureShape, T) {1174		fn enter_object_scope(stack: &mut AnalysisStack) -> ObjectScope {1175			let is_outermost = stack.first_object_depth == u32::MAX;1176			let this_id = stack.next_local_id();1177			let closure = stack.push_closure_a(this_id);1178			let pushed = stack.push_pseudo_local(names::this());1179			debug_assert_eq!(pushed, this_id, "this pseudo-local id");1180			let scope = ObjectScope {1181				this_id,1182				is_outermost,1183				prev_this_local: stack.this_local,1184				prev_dollar_alias: stack.dollar_alias,1185				prev_cur_self_used: stack.cur_self_used,1186				prev_cur_super_used: stack.cur_super_used,1187				prev_dollar_used: is_outermost.then_some(stack.dollar_used),1188				prev_last_object: stack.last_object_depth,1189				prev_first_object: stack.first_object_depth,1190				closure,1191			};11921193			stack.this_local = Some(scope.this_id);1194			if is_outermost {1195				stack.dollar_alias = Some(scope.this_id);1196				stack.first_object_depth = stack.depth;1197				stack.dollar_used = false;1198			}1199			stack.last_object_depth = stack.depth;1200			stack.cur_self_used = false;1201			stack.cur_super_used = false;1202			scope1203		}12041205		fn leave_object_scope(1206			stack: &mut AnalysisStack,1207			scope: ObjectScope,1208		) -> (ObjectUsage, ClosureShape) {1209			let ObjectScope {1210				this_id,1211				is_outermost,1212				prev_this_local,1213				prev_dollar_alias,1214				prev_cur_self_used,1215				prev_cur_super_used,1216				prev_dollar_used,1217				prev_last_object,1218				prev_first_object,1219				closure,1220			} = scope;1221			let _ = stack.local_defs.pop().expect("this pseudo-local exists");1222			debug_assert_eq!(stack.local_defs.len(), this_id.0 as usize);12231224			let set_dollar = is_outermost && stack.dollar_used;1225			let usage = ObjectUsage {1226				this_used: stack.cur_self_used || stack.cur_super_used || set_dollar,1227				uses_super: stack.cur_super_used,1228				set_dollar,1229			};12301231			stack.this_local = prev_this_local;1232			stack.dollar_alias = prev_dollar_alias;1233			stack.cur_self_used = prev_cur_self_used;1234			stack.cur_super_used = prev_cur_super_used;1235			if let Some(prev) = prev_dollar_used {1236				stack.dollar_used = prev;1237			}1238			stack.last_object_depth = prev_last_object;1239			stack.first_object_depth = prev_first_object;12401241			let frame_shape = stack.pop_closure(closure);1242			(usage, frame_shape)1243		}1244		let scope = enter_object_scope(self);1245		let v = inner(self);1246		let (usage, shape) = leave_object_scope(self, scope);1247		(usage, shape, v)1248	}12491250	fn push_pseudo_local(&mut self, name: IStr) -> LocalId {1251		let id = self.next_local_id();1252		self.local_defs.push(LocalDefinition {1253			name,1254			span: None,1255			defined_at_depth: self.depth,1256			used_at_depth: u32::MAX,1257			used_by_sibling: false,1258			analysis: AnalysisResult::default(),1259			analyzed: true,1260			scratch_referenced: false,1261		});1262		{1263			let def = self.defining_closure_mut();1264			let _ = def.define_local(id);1265		}1266		id1267	}12681269	fn use_this(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1270		let id = self.this_local?;1271		self.cur_self_used = true;1272		self.use_pseudo_local(id, taint);1273		Some(self.resolve_to_slot(id))1274	}12751276	fn use_super(&mut self, taint: &mut AnalysisResult) -> Option<()> {1277		let id = self.this_local?;1278		self.cur_super_used = true;1279		self.use_pseudo_local(id, taint);1280		Some(())1281	}12821283	fn use_dollar(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1284		let id = self.dollar_alias?;1285		self.dollar_used = true;1286		self.use_pseudo_local(id, taint);1287		Some(self.resolve_to_slot(id))1288	}12891290	// TODO: Dedicated type for object references instead of "pseudo local" BS, idk1291	fn use_pseudo_local(&mut self, id: LocalId, taint: &mut AnalysisResult) {1292		let depth = self.depth;1293		let def = &mut self.local_defs[id.idx()];1294		def.use_at(depth);1295		taint.depend_on_local(def.defined_at_depth);1296		taint.depend_on_object(def.defined_at_depth);1297	}1298}12991300#[must_use]1301struct ObjectScope {1302	this_id: LocalId,1303	is_outermost: bool,1304	prev_this_local: Option<LocalId>,1305	prev_dollar_alias: Option<LocalId>,1306	prev_cur_self_used: bool,1307	prev_cur_super_used: bool,1308	prev_dollar_used: Option<bool>,1309	prev_last_object: u32,1310	prev_first_object: u32,1311	closure: ClosureOnStack,1312}13131314struct ObjectUsage {1315	this_used: bool,1316	uses_super: bool,1317	set_dollar: bool,1318}13191320fn analyze_assert(1321	stmt: &AssertStmt,1322	stack: &mut AnalysisStack,1323	taint: &mut AnalysisResult,1324) -> LAssertStmt {1325	let cond = analyze(&stmt.assertion.value, stack, taint);1326	let message = stmt.message.as_ref().map(|m| analyze(m, stack, taint));1327	LAssertStmt {1328		cond: Spanned::new(cond, stmt.assertion.span.clone()),1329		message,1330	}1331}13321333#[allow(clippy::too_many_lines)]1334pub fn analyze_named(1335	name: IStr,1336	expr: &Expr,1337	stack: &mut AnalysisStack,1338	taint: &mut AnalysisResult,1339) -> LExpr {1340	if let Expr::Function(span, params, body) = expr {1341		return analyze_function(Some(name), &span, &params, body, stack, taint);1342	}1343	analyze(expr, stack, taint)1344}1345#[allow(clippy::too_many_lines)]1346pub fn analyze(expr: &Expr, stack: &mut AnalysisStack, taint: &mut AnalysisResult) -> LExpr {1347	match expr {1348		Expr::Literal(span, l) => match l {1349			LiteralType::This => stack.use_this(taint).map_or_else(1350				|| {1351					stack.report_error("`self` used outside of object", Some(span.clone()));1352					LExpr::BadLocal("self")1353				},1354				LExpr::Slot,1355			),1356			LiteralType::Super => {1357				if stack.use_super(taint).is_some() {1358					LExpr::Super1359				} else {1360					stack.report_error("`super` used outside of object", Some(span.clone()));1361					LExpr::BadLocal("super")1362				}1363			}1364			LiteralType::Dollar => stack.use_dollar(taint).map_or_else(1365				|| {1366					stack.report_error("`$` used outside of object", Some(span.clone()));1367					LExpr::BadLocal("$")1368				},1369				LExpr::Slot,1370			),1371			LiteralType::Null => LExpr::Null,1372			LiteralType::True => LExpr::Bool(true),1373			LiteralType::False => LExpr::Bool(false),1374		},1375		Expr::Str(s) => LExpr::Str(s.clone()),1376		Expr::Num(n) => LExpr::Num(*n),1377		Expr::Var(v) => stack1378			.use_local(&v.value, v.span.clone(), taint)1379			.map_or_else(|| LExpr::BadLocal("ref"), LExpr::Slot),1380		Expr::Arr(a) => {1381			let (shape, items) = stack1382				.in_using_closure(|stack| a.iter().map(|v| analyze(v, stack, taint)).collect());1383			LExpr::Arr {1384				shape,1385				items: Rc::new(items),1386			}1387		}1388		Expr::ArrComp(inner, comp) => analyze_arr_comp(inner, comp, stack, taint),1389		Expr::Obj(obj) => LExpr::Obj(analyze_obj_body(obj, stack, taint)),1390		Expr::ObjExtend(base, obj) => LExpr::ObjExtend(1391			Box::new(analyze(base, stack, taint)),1392			analyze_obj_body(obj, stack, taint),1393		),1394		Expr::UnaryOp(op, value) => LExpr::UnaryOp(*op, Box::new(analyze(value, stack, taint))),1395		Expr::BinaryOp(op) => {1396			let BinaryOp {1397				lhs,1398				op: optype,1399				rhs,1400			} = &**op;1401			LExpr::BinaryOp {1402				lhs: Box::new(analyze(lhs, stack, taint)),1403				op: *optype,1404				rhs: Box::new(analyze(rhs, stack, taint)),1405			}1406		}1407		Expr::AssertExpr(assert) => {1408			let AssertExpr { assert, rest } = &**assert;1409			let assert = Rc::new(analyze_assert(assert, stack, taint));1410			let rest = Box::new(analyze(rest, stack, taint));1411			LExpr::AssertExpr { assert, rest }1412		}1413		Expr::LocalExpr(binds, body) => analyze_local_expr(binds, body, stack, taint),1414		Expr::Import(kind, path_expr) => {1415			let Expr::Str(path) = &**path_expr else {1416				stack.report_error(1417					"import path must be a string literal",1418					Some(kind.span.clone()),1419				);1420				return LExpr::BadLocal("bad import");1421			};1422			LExpr::Import {1423				kind: kind.clone(),1424				kind_span: kind.span.clone(),1425				path: path.clone(),1426			}1427		}1428		Expr::ErrorStmt(span, inner) => {1429			LExpr::Error(span.clone(), Box::new(analyze(inner, stack, taint)))1430		}1431		Expr::Apply(applicable, args, tailstrict) => {1432			let app = analyze(applicable, stack, taint);1433			let ArgsDesc {1434				unnamed,1435				names,1436				values,1437			} = &args.value;1438			let unnamed_l = unnamed1439				.iter()1440				.map(|a| Rc::new(analyze(a, stack, taint)))1441				.collect();1442			let values_l = values1443				.iter()1444				.map(|a| Rc::new(analyze(a, stack, taint)))1445				.collect();1446			LExpr::Apply {1447				applicable: Box::new(app),1448				args: Spanned::new(1449					LArgsDesc {1450						unnamed: unnamed_l,1451						names: names.clone(),1452						values: values_l,1453					},1454					args.span.clone(),1455				),1456				tailstrict: *tailstrict,1457			}1458		}1459		Expr::Index { indexable, parts } => {1460			let idx = analyze(indexable, stack, taint);1461			let parts_l = parts1462				.iter()1463				.map(|p| {1464					let value = analyze(&p.value, stack, taint);1465					LIndexPart {1466						span: p.span.clone(),1467						value,1468						#[cfg(feature = "exp-null-coaelse")]1469						null_coaelse: p.null_coaelse,1470					}1471				})1472				.collect();1473			LExpr::Index {1474				indexable: Box::new(idx),1475				parts: parts_l,1476			}1477		}1478		Expr::Function(span, params, body) => {1479			analyze_function(None, span, params, body, stack, taint)1480		}1481		Expr::IfElse(ifelse) => {1482			let IfElse {1483				cond,1484				cond_then,1485				cond_else,1486			} = &**ifelse;1487			let cond_l = analyze(&cond.cond, stack, taint);1488			let then_l = analyze(cond_then, stack, taint);1489			let else_l = cond_else1490				.as_ref()1491				.map(|e| Box::new(analyze(e, stack, taint)));1492			LExpr::IfElse {1493				cond: Box::new(cond_l),1494				cond_then: Box::new(then_l),1495				cond_else: else_l,1496			}1497		}1498		Expr::Slice(slice) => {1499			let Slice {1500				value,1501				slice: SliceDesc { start, end, step },1502			} = &**slice;1503			let value_l = analyze(value, stack, taint);1504			let start_l = start.as_ref().map(|e| analyze(&e.value, stack, taint));1505			let end_l = end.as_ref().map(|e| analyze(&e.value, stack, taint));1506			let step_l = step.as_ref().map(|e| analyze(&e.value, stack, taint));1507			LExpr::Slice(Box::new(LSliceExpr {1508				value: value_l,1509				start: start_l,1510				end: end_l,1511				step: step_l,1512			}))1513		}1514	}1515}15161517fn analyze_local_expr(1518	binds: &[BindSpec],1519	body: &Expr,1520	stack: &mut AnalysisStack,1521	taint: &mut AnalysisResult,1522) -> LExpr {1523	if binds.is_empty() {1524		return analyze(body, stack, taint);1525	}1526	let frame_start = stack.next_local_id();1527	let closure = stack.push_closure_a(frame_start);1528	let (l_binds, body_expr) = process_local_frame(binds, stack, taint, |stack, taint| {1529		analyze(body, stack, taint)1530	});1531	let frame_shape = stack.pop_closure(closure);1532	LExpr::LocalExpr(Box::new(LLocalExpr {1533		frame_shape,1534		binds: l_binds,1535		body: body_expr,1536	}))1537}15381539fn analyze_bind_value(1540	bind: &BindSpec,1541	stack: &mut AnalysisStack,1542	taint: &mut AnalysisResult,1543) -> LExpr {1544	match bind {1545		BindSpec::Field {1546			value: Expr::Function(span, params, value),1547			into: Destruct::Full(name),1548		} => analyze_function(Some(name.value.clone()), &span, params, value, stack, taint),1549		BindSpec::Field { value, .. } => analyze(value, stack, taint),1550		BindSpec::Function {1551			params,1552			value,1553			name,1554		} => analyze_function(1555			Some(name.value.clone()),1556			&name.span,1557			params,1558			value,1559			stack,1560			taint,1561		),1562	}1563}15641565fn process_local_frame<R>(1566	binds: &[BindSpec],1567	stack: &mut AnalysisStack,1568	taint: &mut AnalysisResult,1569	body_fn: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1570) -> (Vec<LBind>, R) {1571	let mut alloc = FrameAlloc::new(stack);15721573	let mut destructs: Vec<Option<LDestruct>> = Vec::with_capacity(binds.len());1574	for bind in binds {1575		destructs.push(alloc.alloc_bind(bind));1576	}1577	let mut pending = alloc.finish();15781579	let mut l_binds: Vec<LBind> = Vec::with_capacity(binds.len());1580	for (bind, destruct) in binds.iter().zip(destructs) {1581		let mut value_taint = AnalysisResult::default();1582		let (value_shape, value) = pending1583			.stack1584			.in_using_closure(|stack| analyze_bind_value(bind, stack, &mut value_taint));1585		taint.taint_by(value_taint);1586		if let Some(destruct) = destruct {1587			pending.record_spec_init(&destruct, value_taint);1588			l_binds.push(LBind {1589				destruct,1590				value_shape,1591				value: Rc::new(value),1592			});1593		} else {1594			pending.closures.push_spec(0, &[]);1595		}1596	}15971598	let body_frame = pending.finish();1599	let result = body_fn(body_frame.stack, taint);1600	body_frame.finish();16011602	(l_binds, result)1603}16041605fn analyze_function(1606	name: Option<IStr>,1607	span: &Span,1608	params: &ExprParams,1609	body: &Expr,1610	stack: &mut AnalysisStack,1611	taint: &mut AnalysisResult,1612) -> LExpr {1613	let mut alloc = FrameAlloc::new(stack);1614	let closure = alloc.push_locals_closure();16151616	let mut param_destructs: Vec<Option<LDestruct>> = Vec::with_capacity(params.exprs.len());1617	for p in &params.exprs {1618		param_destructs.push(alloc.alloc_destruct(&p.destruct));1619	}16201621	let mut pending = alloc.finish();16221623	let mut l_params: Vec<LParam> = Vec::with_capacity(params.exprs.len());1624	for (p, destruct) in params.exprs.iter().zip(param_destructs) {1625		let mut value_taint = AnalysisResult::default();1626		let default = p.default.as_ref().map_or_else(1627			|| None,1628			|d| {1629				Some(1630					pending1631						.stack1632						.in_using_closure(|stack| Rc::new(analyze(d, stack, &mut value_taint))),1633				)1634			},1635		);1636		taint.taint_by(value_taint);1637		if let Some(destruct) = destruct {1638			let name = match &p.destruct {1639				Destruct::Full(n) => Some(n.value.clone()),1640				#[cfg(feature = "exp-destruct")]1641				_ => None,1642			};1643			pending.record_spec_init(&destruct, value_taint);1644			l_params.push(LParam {1645				name,1646				destruct,1647				default,1648			});1649		} else {1650			pending.closures.push_spec(0, &[]);1651		}1652	}16531654	let body_frame = pending.finish();1655	let body_expr = analyze(body, body_frame.stack, taint);1656	body_frame.finish();1657	let body_shape = stack.pop_closure(closure);16581659	// function(x) x is an identity function1660	if l_params.len() == 1 && l_params[0].default.is_none() {1661		#[allow(irrefutable_let_patterns, reason = "refutable with exp-destruct")]1662		if let LDestruct::Full(param_slot) = &l_params[0].destruct1663			&& let LExpr::Slot(LSlot::Local(s)) = &body_expr1664			&& s == param_slot1665		{1666			stack.report_warning(1667				"do not define identity functions manually, use std.id instead",1668				Some(span.clone()),1669			);1670			return LExpr::IdentityFunction {};1671		}1672	}16731674	LExpr::Function(Rc::new(LFunction {1675		name,1676		params: l_params,1677		signature: params.signature.clone(),1678		body_shape,1679		body: Rc::new(body_expr),1680	}))1681}16821683fn analyze_obj_body(1684	obj: &ObjBody,1685	stack: &mut AnalysisStack,1686	taint: &mut AnalysisResult,1687) -> LObjBody {1688	match obj {1689		ObjBody::MemberList(members) => {1690			LObjBody::MemberList(analyze_obj_members(members, stack, taint))1691		}1692		ObjBody::ObjComp(comp) => LObjBody::ObjComp(Box::new(analyze_obj_comp(comp, stack, taint))),1693	}1694}16951696fn analyze_obj_members(1697	members: &ObjMembers,1698	stack: &mut AnalysisStack,1699	taint: &mut AnalysisResult,1700) -> LObjMembers {1701	let ObjMembers {1702		locals,1703		asserts,1704		fields,1705	} = members;17061707	// Names are analyzed in enclosing scope, they can't depend on locals or self/super1708	let field_names: Vec<LFieldName> = fields1709		.iter()1710		.map(|f| match &f.name.value {1711			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1712			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1713		})1714		.collect();17151716	let (usage, frame_shape, (l_binds, (l_asserts_opt, l_fields))) =1717		stack.in_object_scope(|stack| {1718			process_local_frame(locals, stack, taint, |stack, taint| {1719				let l_asserts_opt = if asserts.is_empty() {1720					None1721				} else {1722					let (shape, l_asserts) = stack.in_using_closure(|stack| {1723						let mut l_asserts = Vec::with_capacity(asserts.len());1724						for a in asserts {1725							let mut assert_taint = AnalysisResult::default();1726							l_asserts.push(analyze_assert(a, stack, &mut assert_taint));1727							taint.taint_by(assert_taint);1728						}1729						l_asserts1730					});1731					Some(Rc::new(LObjAsserts {1732						shape,1733						asserts: l_asserts,1734					}))1735				};1736				let mut l_fields = Vec::with_capacity(fields.len());1737				for (f, name) in fields.iter().zip(field_names) {1738					let value = stack.in_using_closure(|stack| {1739						if let Some(params) = &f.params {1740							analyze_function(1741								name.function_name(),1742								&f.name.span,1743								params,1744								&f.value,1745								stack,1746								taint,1747							)1748						} else {1749							analyze(&f.value, stack, taint)1750						}1751					});1752					l_fields.push(LFieldMember {1753						name,1754						plus: f.plus,1755						visibility: f.visibility,1756						value: Rc::new(value),1757					});1758				}1759				(l_asserts_opt, l_fields)1760			})1761		});1762	// `this` was allocated as the first local of the object's frame,1763	// so its slot is 0 within that frame.1764	let this_slot = usage.this_used.then_some(LocalSlot(0));1765	LObjMembers {1766		frame_shape,1767		this: this_slot,1768		set_dollar: usage.set_dollar,1769		uses_super: usage.uses_super,1770		locals: Rc::new(l_binds),1771		asserts: l_asserts_opt,1772		fields: l_fields,1773	}1774}17751776fn analyze_obj_comp(1777	comp: &ObjComp,1778	stack: &mut AnalysisStack,1779	taint: &mut AnalysisResult,1780) -> LObjComp {1781	let res = analyze_comp_specs(&comp.compspecs, stack, taint, |stack, taint| {1782		let field_name = match &comp.field.name.value {1783			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1784			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1785		};17861787		let (usage, frame_shape, body) = stack.in_object_scope(|stack| {1788			process_local_frame(&comp.locals, stack, taint, |stack, taint| {1789				let value = stack.in_using_closure(|stack| {1790					if let Some(params) = &comp.field.params {1791						analyze_function(1792							None,1793							&comp.field.name.span,1794							params,1795							&comp.field.value,1796							stack,1797							taint,1798						)1799					} else {1800						analyze(&comp.field.value, stack, taint)1801					}1802				});1803				LFieldMember {1804					name: field_name,1805					plus: comp.field.plus,1806					visibility: comp.field.visibility,1807					value: Rc::new(value),1808				}1809			})1810		});1811		(usage, frame_shape, body)1812	});1813	let (usage, frame_shape, (locals, field)) = res.inner;1814	let this_slot = usage.this_used.then_some(LocalSlot(0));1815	LObjComp {1816		frame_shape: Rc::new(frame_shape),1817		this: this_slot,1818		set_dollar: usage.set_dollar,1819		uses_super: usage.uses_super,1820		locals: Rc::new(locals),1821		field,1822		compspecs: res.compspecs,1823	}1824}18251826fn analyze_arr_comp(1827	inner: &Expr,1828	specs: &[CompSpec],1829	stack: &mut AnalysisStack,1830	taint: &mut AnalysisResult,1831) -> LExpr {1832	let res = analyze_comp_specs(specs, stack, taint, |stack, taint| {1833		stack.in_using_closure(|stack| analyze(inner, stack, taint))1834	});1835	let (value_shape, value) = res.inner;1836	LExpr::ArrComp(Box::new(LArrComp {1837		value_shape,1838		value: Rc::new(value),1839		compspecs: res.compspecs,1840	}))1841}18421843fn analyze_comp_specs<R>(1844	specs: &[CompSpec],1845	stack: &mut AnalysisStack,1846	taint: &mut AnalysisResult,1847	inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1848) -> CompSpecResult<R> {1849	fn go<R>(1850		idx: usize,1851		specs: &[CompSpec],1852		outer_depth: u32,1853		stack: &mut AnalysisStack,1854		taint: &mut AnalysisResult,1855		inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1856	) -> (R, Vec<LCompSpec>) {1857		if idx >= specs.len() {1858			return (inside(stack, taint), Vec::new());1859		}1860		match &specs[idx] {1861			CompSpec::IfSpec(IfSpecData { cond, .. }) => {1862				let cond_l = analyze(cond, stack, taint);1863				let (r, mut rest) = go(idx + 1, specs, outer_depth, stack, taint, inside);1864				rest.insert(0, LCompSpec::If(cond_l));1865				(r, rest)1866			}1867			CompSpec::ForSpec(ForSpecData { destruct, over }) => {1868				let mut over_taint = AnalysisResult::default();1869				let over_l = analyze(over, stack, &mut over_taint);1870				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1871				taint.taint_by(over_taint);18721873				let mut alloc = FrameAlloc::new(stack);1874				let closure = alloc.push_locals_closure();1875				let Some(l_destruct) = alloc.alloc_destruct(destruct) else {1876					stack.pop_closure(closure);1877					return go(idx + 1, specs, outer_depth, stack, taint, inside);1878				};1879				let mut pending = alloc.finish();18801881				let var_analysis = AnalysisResult::default();1882				pending.record_spec_init(&l_destruct, var_analysis);18831884				let body_frame = pending.finish();1885				let (r, mut rest) =1886					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);1887				body_frame.finish();1888				let frame_shape = stack.pop_closure(closure);18891890				rest.insert(1891					0,1892					LCompSpec::For {1893						frame_shape,1894						destruct: l_destruct,1895						over: over_l,1896						loop_invariant,1897					},1898				);1899				(r, rest)1900			}1901			#[cfg(feature = "exp-object-iteration")]1902			CompSpec::ForObjSpec(data) => {1903				let mut over_taint = AnalysisResult::default();1904				let over_l = analyze(&data.over, stack, &mut over_taint);1905				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1906				taint.taint_by(over_taint);19071908				let mut alloc = FrameAlloc::new(stack);1909				let closure = alloc.push_locals_closure();1910				let Some((_, key_slot)) = alloc.define_local(data.key.clone(), None) else {1911					stack.pop_closure(closure);1912					return go(idx + 1, specs, outer_depth, stack, taint, inside);1913				};1914				let Some(l_value) = alloc.alloc_destruct(&data.value) else {1915					stack.pop_closure(closure);1916					return go(idx + 1, specs, outer_depth, stack, taint, inside);1917				};1918				let mut pending = alloc.finish();19191920				let var_analysis = AnalysisResult::default();1921				pending.record_spec_init(&LDestruct::Full(key_slot), var_analysis);1922				pending.record_spec_init(&l_value, var_analysis);19231924				let body_frame = pending.finish();1925				let (r, mut rest) =1926					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);1927				body_frame.finish();1928				let frame_shape = stack.pop_closure(closure);19291930				rest.insert(1931					0,1932					LCompSpec::ForObj {1933						frame_shape,1934						key: key_slot,1935						visibility: data.visibility,1936						value: l_value,1937						over: over_l,1938						loop_invariant,1939					},1940				);1941				(r, rest)1942			}1943		}1944	}1945	let outer_depth = stack.depth;1946	let (r, compspecs) = go(0, specs, outer_depth, stack, taint, inside);1947	CompSpecResult {1948		inner: r,1949		compspecs,1950	}1951}19521953struct CompSpecResult<R> {1954	inner: R,1955	compspecs: Vec<LCompSpec>,1956}19571958pub fn analyze_root(expr: &Expr, ctx: Vec<(IStr, LocalId)>) -> AnalysisReport {1959	let mut stack = AnalysisStack::new();1960	for (name, id) in ctx {1961		stack.define_external_local(name, id);1962	}19631964	let externals_count: u16 = stack1965		.local_defs1966		.len()1967		.try_into()1968		.expect("more than u16::MAX externals");1969	let closure = stack.push_root_closure(externals_count);19701971	let mut taint = AnalysisResult::default();1972	let lir = analyze(expr, &mut stack, &mut taint);19731974	let root_shape = stack.pop_closure(closure);1975	debug_assert!(1976		stack.closure_stack.is_empty(),1977		"closure stack imbalance after analyze"1978	);19791980	AnalysisReport {1981		lir,1982		root_shape,1983		root_analysis: taint,1984		diagnostics_list: stack.diagnostics,1985		errored: stack.errored,1986	}1987}19881989pub struct AnalysisReport {1990	pub lir: LExpr,1991	pub root_shape: ClosureShape,1992	pub root_analysis: AnalysisResult,1993	pub diagnostics_list: Vec<Diagnostic>,1994	pub errored: bool,1995}19961997#[cfg(test)]1998mod tests {1999	#[test]2000	#[cfg(not(feature = "exp-null-coaelse"))]2001	fn snapshots() {2002		use std::fs;20032004		use insta::{assert_snapshot, glob};2005		use jrsonnet_ir::Source;20062007		use super::*;20082009		fn render_diagnostics(src: &str, diags: &[Diagnostic]) -> String {2010			use std::fmt::Write;20112012			use hi_doc::{Formatting, SnippetBuilder, Text};20132014			let mut out = String::new();2015			let mut unspanned = Vec::new();2016			let mut spanned: Vec<&Diagnostic> = Vec::new();2017			for d in diags {2018				if d.span.is_some() {2019					spanned.push(d);2020				} else {2021					unspanned.push(d);2022				}2023			}2024			if !spanned.is_empty() {2025				let mut builder = SnippetBuilder::new(src);2026				for d in spanned {2027					let span = d.span.as_ref().expect("spanned");2028					let ab = match d.level {2029						DiagLevel::Error => {2030							builder.error(Text::fragment(d.message.clone(), Formatting::default()))2031						}2032						DiagLevel::Warning => builder2033							.warning(Text::fragment(d.message.clone(), Formatting::default())),2034					};2035					ab.range(span.range()).build();2036				}2037				out.push_str(&hi_doc::source_to_ansi(&builder.build()));2038			}2039			for d in unspanned {2040				let prefix = match d.level {2041					DiagLevel::Error => "error",2042					DiagLevel::Warning => "warning",2043				};2044				writeln!(out, "{prefix}: {}", d.message).expect("fmt");2045			}2046			out2047		}2048		fn fmt_depth(d: u32) -> String {2049			if d == u32::MAX {2050				"none".into()2051			} else {2052				d.to_string()2053			}2054		}20552056		glob!("analysis_tests/*.jsonnet", |path| {2057			let code = fs::read_to_string(path).expect("read test file");2058			let src = Source::new_virtual("<test>".into(), code.clone().into());2059			let expr = crate::parse_jsonnet(&code, src.clone()).expect("parse");2060			let report = analyze_root(&expr, Vec::new());20612062			let diagnostics = render_diagnostics(src.code(), &report.diagnostics_list);2063			// Strip ANSI escapes from diagnostics so snapshots are readable.2064			let diagnostics = strip_ansi_escapes::strip_str(&diagnostics);2065			let rendered = format!(2066				"--- source ---\n{}\n--- root analysis ---\nobject_dependent_depth: {}\nlocal_dependent_depth: {}\nerrored: {}\n--- diagnostics ---\n{}--- lir ---\n{:#?}\n",2067				code.trim_end(),2068				fmt_depth(report.root_analysis.object_dependent_depth),2069				fmt_depth(report.root_analysis.local_dependent_depth),2070				report.errored,2071				diagnostics,2072				report.lir,2073			);2074			assert_snapshot!(rendered);2075		});2076	}2077}