git.delta.rocks / jrsonnet / refs/commits / 7bd5bbd0756a

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, IdentityKind, IfElse, IfSpecData, ImportKind, ObjBody,25	ObjComp, ObjMembers, Slice, SliceDesc, Span, Spanned, TrivialVal, UnaryOpType, Visibility,26	function::FunctionSignature,27};28use rustc_hash::{FxHashMap, FxHashSet};29use smallvec::SmallVec;3031use crate::{32	arr::arridx,33	error::{format_found, suggest_names},34	gc::WithCapacityExt as _,35	obj::{ObjFieldFlags, ObjShape, ShapeField, ordering::FieldIndex},36};3738#[derive(Debug, Clone, Copy)]39#[must_use]40pub struct AnalysisResult {41	/// Highest object, on which identity the value is dependent. `u32::MAX` = not dependent at all42	pub object_dependent_depth: u32,43	/// Highest local frame, on which this value depends. `u32::MAX` = not dependent at all44	pub local_dependent_depth: u32,45}4647impl Default for AnalysisResult {48	fn default() -> Self {49		Self {50			object_dependent_depth: u32::MAX,51			local_dependent_depth: u32::MAX,52		}53	}54}5556impl AnalysisResult {57	fn depend_on_object(&mut self, depth: u32) {58		if depth < self.object_dependent_depth {59			self.object_dependent_depth = depth;60		}61	}62	fn depend_on_local(&mut self, depth: u32) {63		if depth < self.local_dependent_depth {64			self.local_dependent_depth = depth;65		}66	}67	fn taint_by(&mut self, other: AnalysisResult) {68		self.depend_on_object(other.object_dependent_depth);69		self.depend_on_local(other.local_dependent_depth);70	}71}7273#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Acyclic)]74pub struct LocalId(pub u32);7576impl LocalId {77	fn idx(self) -> usize {78		self.0 as usize79	}80	fn defined_before(self, other: Self) -> bool {81		self.0 < other.082	}83}8485#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Acyclic)]86pub enum LSlot {87	/// Enclosing frame locals (sibling letrec, params, etc.).88	Local(LocalSlot),89	/// Enclosing closure's capture pack.90	Capture(CaptureSlot),91}9293#[derive(Debug, Acyclic)]94pub struct ClosureShape {95	pub captures: Box<[LSlot]>,96	pub n_locals: u16,97}9899struct LocalDefinition {100	name: IStr,101	span: Option<Span>,102	/// At which frame depth this local was defined103	defined_at_depth: u32,104	/// Min frame depth, at which this local was used. `u32::MAX` = not used at all.105	/// This check won't catch unused argument closures, i.e:106	/// ```jsonnet107	/// local108	///     a = b,109	///     b = a,110	/// ; 2 + 2111	///112	/// ```113	/// Both `a` and `b` here are "used", but the whole closure was not used here.114	used_at_depth: u32,115	/// Used as part of the current frame closure116	used_by_sibling: bool,117	/// Analysys result for value of this local118	analysis: AnalysisResult,119	/// Has `analysis` been filled in?120	/// For sanity checking, locals are initialized in batchs, use `first_uninitialized_local`121	analyzed: bool,122	/// During walk over uninitialized vars, we can't refer to analysis results of other locals,123	/// but we need to. To make that work, for each variable in variable frame we capture its closure,124	/// by looking at referenced variables.125	scratch_referenced: bool,126}127128impl LocalDefinition {129	fn use_at(&mut self, depth: u32) {130		if depth == self.defined_at_depth {131			self.used_by_sibling = true;132			return;133		}134		if depth < self.used_at_depth {135			self.used_at_depth = depth;136		}137	}138}139140#[derive(Debug, Acyclic)]141pub enum LExpr {142	Slot(LSlot),143	Trivial(TrivialVal),144	Arr {145		shape: ClosureShape,146		items: Rc<Vec<LExpr>>,147	},148	ArrConst(Rc<Vec<TrivialVal>>),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	StaticMembers(Box<LObjStaticMembers>),335	ObjComp(Box<LObjComp>),336}337338#[derive(Debug, Acyclic)]339pub struct LObjMembers {340	pub frame_shape: ClosureShape,341	/// If current object identity (`super`/`this`/`$`) is used, `this` should342	/// be saved to the specified local slot.343	pub this: Option<LocalSlot>,344	/// Set if dollar should also be assigned to object identity, `this` should also be set (TODO: proper type-level validation)345	pub set_dollar: bool,346	/// True iff `super` is referenced by this object's members.347	pub uses_super: bool,348349	pub locals: Rc<Vec<LBind>>,350	pub asserts: Option<Rc<LObjAsserts>>,351	pub fields: Vec<LFieldMember>,352}353354#[derive(Debug, Acyclic)]355pub struct LObjStaticMembers {356	pub frame_shape: ClosureShape,357	pub this: Option<LocalSlot>,358	pub set_dollar: bool,359	pub uses_super: bool,360361	pub locals: Rc<Vec<LBind>>,362	pub asserts: Option<Rc<LObjAsserts>>,363364	pub shape: Rc<ObjShape>,365	pub bindings: Vec<Rc<(ClosureShape, LExpr)>>,366}367368#[derive(Debug, Acyclic)]369pub struct LObjComp {370	pub frame_shape: Rc<ClosureShape>,371	pub this: Option<LocalSlot>,372	pub set_dollar: bool,373	pub uses_super: bool,374375	pub locals: Rc<Vec<LBind>>,376	pub field: LFieldMember,377	pub compspecs: Vec<LCompSpec>,378}379380#[derive(Debug, Acyclic)]381pub struct LFieldMember {382	pub name: LFieldName,383	pub plus: bool,384	pub visibility: Visibility,385	pub value: Rc<(ClosureShape, LExpr)>,386}387388#[derive(Debug, Acyclic)]389pub struct LClosure<T: Acyclic> {390	pub shape: ClosureShape,391	pub value: T,392}393394#[derive(Debug, Acyclic)]395pub struct LObjAsserts {396	pub shape: ClosureShape,397	pub asserts: Vec<LAssertStmt>,398}399400#[derive(Debug, Acyclic)]401pub enum LFieldName {402	Fixed(IStr),403	Dyn(LExpr),404}405impl LFieldName {406	fn function_name(&self) -> Option<IStr> {407		match self {408			LFieldName::Fixed(istr) => Some(istr.clone()),409			LFieldName::Dyn(_) => None,410		}411	}412}413414#[derive(Debug, Acyclic)]415pub struct LArrComp {416	pub value_shape: ClosureShape,417	pub value: Rc<LExpr>,418	pub compspecs: Vec<LCompSpec>,419}420421#[derive(Debug, Acyclic)]422pub enum LCompSpec {423	If(LExpr),424	For {425		frame_shape: ClosureShape,426		destruct: LDestruct,427		over: LExpr,428		/// Is `over` does not depend on any variable introduced by an earlier for-spec in this comprehension chain429		loop_invariant: bool,430	},431	#[cfg(feature = "exp-object-iteration")]432	ForObj {433		frame_shape: ClosureShape,434		key: LocalSlot,435		visibility: jrsonnet_ir::Visibility,436		value: LDestruct,437		over: LExpr,438		loop_invariant: bool,439	},440}441442struct FrameAlloc<'s> {443	first_in_frame: LocalId,444	stack: &'s mut AnalysisStack,445	bomb: DropBomb,446}447impl<'s> FrameAlloc<'s> {448	fn new(stack: &'s mut AnalysisStack) -> Self {449		FrameAlloc {450			first_in_frame: stack.next_local_id(),451			stack,452			bomb: DropBomb::new("binding frame state"),453		}454	}455456	fn push_locals_closure(&mut self) -> ClosureOnStack {457		self.stack.push_closure_a(self.first_in_frame)458	}459460	fn define_local(&mut self, name: IStr, span: Option<Span>) -> Option<(LocalId, LocalSlot)> {461		let id = self.stack.next_local_id();462		let stack = self.stack.local_by_name.entry(name.clone()).or_default();463		if let Some(&existing) = stack.last()464			&& !existing.defined_before(self.first_in_frame)465		{466			self.stack.report_error(467				format!("local is already defined in the current frame: {name}"),468				span,469			);470			return None;471		}472		stack.push(id);473		self.stack.local_defs.push(LocalDefinition {474			name,475			span,476			defined_at_depth: self.stack.depth,477			used_at_depth: u32::MAX,478			used_by_sibling: false,479			analysis: AnalysisResult::default(),480			analyzed: false,481			scratch_referenced: false,482		});483		let def = self.stack.defining_closure_mut();484		Some((id, def.define_local(id)))485	}486	fn alloc_bind(&mut self, bind: &BindSpec) -> Option<LDestruct> {487		match bind {488			BindSpec::Field { into, .. } => self.alloc_destruct(into),489			BindSpec::Function { name, .. } => {490				let (_, id) = self.define_local(name.value.clone(), Some(name.span.clone()))?;491				Some(LDestruct::Full(id))492			}493		}494	}495	fn alloc_destruct(&mut self, destruct: &Destruct) -> Option<LDestruct> {496		Some(match destruct {497			Destruct::Full(name) => {498				let (_, id) = self.define_local(name.value.clone(), Some(name.span.clone()))?;499				LDestruct::Full(id)500			}501			#[cfg(feature = "exp-destruct")]502			Destruct::Skip => LDestruct::Skip,503			#[cfg(feature = "exp-destruct")]504			Destruct::Array { start, rest, end } => {505				let start = start506					.iter()507					.map(|d| self.alloc_destruct(d))508					.collect::<Option<Vec<_>>>()?;509				let rest = match rest {510					Some(jrsonnet_ir::DestructRest::Keep(name)) => {511						let (_, id) = self.define_local(name.clone(), None)?;512						Some(LDestructRest::Keep(id))513					}514					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),515					None => None,516				};517				let end = end518					.iter()519					.map(|d| self.alloc_destruct(d))520					.collect::<Option<Vec<_>>>()?;521				LDestruct::Array { start, rest, end }522			}523			#[cfg(feature = "exp-destruct")]524			Destruct::Object { fields, rest } => {525				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());526				// Allocate destruct LocalIds, then analyse defaults527				for (name, into, _default) in fields {528					let into = if let Some(inner) = into {529						self.alloc_destruct(inner)?530					} else {531						let (_, id) = self.define_local(name.clone(), None)?;532						LDestruct::Full(id)533					};534					l_fields.push((name.clone(), into));535				}536				// All locals exist, so defaults can reference any sibling.537				let l_fields: Vec<LDestructField> = l_fields538					.into_iter()539					.zip(fields.iter())540					.map(|((name, into), (_n, _i, default))| {541						let default = match default {542							Some(e) => {543								let mut default_taint = AnalysisResult::default();544								Some(self.stack.in_using_closure(|stack| {545									Rc::new(analyze(&e.value, stack, &mut default_taint))546								}))547							}548							None => None,549						};550						LDestructField {551							name,552							into: Some(into),553							default,554						}555					})556					.collect();557				let rest = match rest {558					Some(jrsonnet_ir::DestructRest::Keep(name)) => {559						let (_, id) = self.define_local(name.clone(), None)?;560						Some(LDestructRest::Keep(id))561					}562					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),563					None => None,564				};565				LDestruct::Object {566					fields: l_fields,567					rest,568				}569			}570		})571	}572573	fn finish(self) -> PendingInit<'s> {574		let Self {575			first_in_frame,576			stack,577			bomb,578		} = self;579		let first_after_frame = stack.next_local_id();580		PendingInit {581			first_after_frame,582			stack,583			closures: Closures {584				referenced: vec![],585				spec_shapes: vec![],586				first_in_frame,587			},588			bomb,589		}590	}591}592593/// Frame state: `LocalIds` allocated, values not yet analysed.594struct PendingInit<'s> {595	first_after_frame: LocalId,596	stack: &'s mut AnalysisStack,597	closures: Closures,598	bomb: DropBomb,599}600601impl<'s> PendingInit<'s> {602	/// Record the analysis of a spec's value: stamp every id bound by the603	/// spec with `analysis`, collect the spec's same-frame references, and604	/// append them to `closures`.605	fn record_spec_init(&mut self, destruct: &LDestruct, analysis: AnalysisResult) {606		let mut refs: SmallVec<[LocalId; 4]> = SmallVec::new();607		for i in self.closures.first_in_frame.0..self.first_after_frame.0 {608			let def = &mut self.stack.local_defs[i as usize];609			if def.scratch_referenced {610				refs.push(LocalId(i));611				def.scratch_referenced = false;612			}613		}614615		let mut ids_count = 0;616		let first_local = self.stack.top_defining_local();617		destruct.each_slot(&mut |slot| {618			ids_count += 1;619			let id = LocalId(first_local.0 + u32::from(slot.0));620			let def = &mut self.stack.local_defs[id.idx()];621			debug_assert!(!def.analyzed, "sanity: local {:?} analysed twice", def.name);622			def.analysis = analysis;623			def.analyzed = true;624		});625		self.closures.push_spec(ids_count, &refs);626	}627	/// After all specs are analysed, propagate dependency information between628	/// siblings to a fix-point, then switch to "body" mode.629	fn finish(self) -> PendingBody<'s> {630		let Self {631			first_after_frame,632			closures,633			stack,634			bomb,635		} = self;636637		debug_assert_eq!(638			first_after_frame,639			stack.next_local_id(),640			"frame initialisation left unfinished locals"641		);642643		debug_assert_eq!(644			closures.spec_shapes.iter().map(|(_, d)| *d).sum::<usize>(),645			(first_after_frame.0 - closures.first_in_frame.0) as usize,646			"closures destruct-id counts must match frame local count"647		);648649		let mut changed = true;650		while changed {651			changed = false;652			for spec in closures.iter_specs() {653				for id_raw in spec.ids.clone() {654					let user = LocalId(id_raw);655					for &used in spec.references {656						changed |= stack.propagate_analysis(user, used);657					}658				}659			}660		}661662		stack.depth += 1;663		PendingBody {664			first_after_frame,665			closures,666			stack,667			bomb,668		}669	}670}671672/// Frame state: values analysed, body not yet walked.673struct PendingBody<'s> {674	first_after_frame: LocalId,675	closures: Closures,676	stack: &'s mut AnalysisStack,677	bomb: DropBomb,678}679impl PendingBody<'_> {680	/// After the body is processed, drop the frame's locals and emit any681	/// "unused local" warnings.682	fn finish(self) {683		let PendingBody {684			first_after_frame,685			closures,686			stack,687			mut bomb,688		} = self;689		bomb.defuse();690		stack.depth -= 1;691692		debug_assert_eq!(693			first_after_frame,694			stack.next_local_id(),695			"nested scopes must be popped before outer frames"696		);697698		let mut changed = true;699		while changed {700			changed = false;701			for spec in closures.iter_specs() {702				// Effective used_at_depth for the spec = min over its ids.703				let mut min_used_at = u32::MAX;704				for id_raw in spec.ids.clone() {705					min_used_at = min_used_at.min(stack.local_defs[id_raw as usize].used_at_depth);706				}707				if min_used_at == u32::MAX {708					continue;709				}710				for &used in spec.references {711					let used_def = &mut stack.local_defs[used.idx()];712					if min_used_at < used_def.used_at_depth {713						used_def.used_at_depth = min_used_at;714						changed = true;715					}716				}717			}718		}719720		let drained: Vec<LocalDefinition> = stack721			.local_defs722			.drain(closures.first_in_frame.idx()..)723			.collect();724		for (i, def) in drained.iter().enumerate().rev() {725			let id = LocalId(closures.first_in_frame.0 + arridx(i));726			let stack_locals = stack727				.local_by_name728				.get_mut(&def.name)729				.expect("local must be in name map");730			let popped = stack_locals.pop().expect("name stack should not be empty");731			debug_assert_eq!(popped, id, "name stack integrity");732			if stack_locals.is_empty() {733				stack.local_by_name.remove(&def.name);734			}735736			if def.used_at_depth == u32::MAX {737				if def.used_by_sibling {738					stack.report_warning(739						format!("local is only referenced by unused siblings: {}", def.name),740						def.span.clone(),741					);742				} else {743					stack.report_warning(format!("unused local: {}", def.name), def.span.clone());744				}745			} else if def.analysis.local_dependent_depth > def.defined_at_depth746				&& def.analysis.object_dependent_depth > def.defined_at_depth747				&& def.defined_at_depth != 0748			{749				// The value doesn't depend on anything defined at or inside750				// this local's scope - can be hoisted, unfortunately not automatically.751				stack.report_warning(752					format!("local could be hoisted to an outer scope: {}", def.name),753					def.span.clone(),754				);755			}756		}757	}758}759760struct Closures {761	/// All the referenced locals, maybe repeated multiple times762	/// It is recorded as continous vec of sets, I.e we have763	/// a = 1, 2, 3764	/// b = 3, 4, 5, 6765	/// And in `referenced` we have `[ 1, 2, 3, 3, 4, 5, 6 ]`. To actually get, which closure refers to which element, see `spec_shapes`...766	/// Flat concatenation of sibling-local references across all specs.767	referenced: Vec<LocalId>,768	/// Amount of elements per closure, for the above case it is a = 3, b = 4, so here769	/// lies `[ 3, 4 ]`770	/// ~~closures: Vec<usize>,~~771	/// Finally, we have destructs.772	/// Because single destruct references single closure, but destructs to multiple locals, we have even more complicated structure.773	/// Luckly, every destruct is not interleaved with each other, so here we can have full list...774	/// 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 elements775	/// for each destruct starting from `first_destruct_local`776	/// ~~destructs: Vec<usize>,~~777	///778	/// => two of those fields were merged, as there is currently no per-destruct tracking of closures.779	/// For each spec in order: `(references_count, destruct_ids_count)`.780	/// `references_count` tells us how many entries of `referenced` belong781	/// to this spec; `destruct_ids_count` tells us how many `LocalIds` it782	/// binds.783	spec_shapes: Vec<(usize, usize)>,784	/// This is not a related doccomment, just a continuation of docs for previous fields.785	/// Having786	/// ```jsonnet787	/// local788	///     [a, b, c] = [d, e, f],789	///     [d, e, f] = [a, b, c, h],790	///     h = 1,791	/// ;792	/// ```793	///794	/// We have total of 7 locals795	/// First local here is `a` => `first_destruct_local` = `a`796	/// 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`797	/// [d, e, f] = [a, b, c, h], => `referenced += [a, b, c, h]`, `closures += 4`, `destructs += 3` (Note that this destruct will fail at runtime,798	///                                                                                               this thing should not care about that, it only captures what the value are referencing)799	/// h = 1 => referenced += [], closures += 0, destructs += 1800	/// And the result is801	///802	/// ```rust,ignore803	/// Closures {804	///     referenced: vec![d, e, f, a, b, c, h]805	///     spec_shapes: vec![(3, 3), (4, 3), (0, 1)],806	///     first_destruct_label: a,807	/// }808	/// ```809	///810	/// Reconstruction of that:811	///812	/// We know that we start with a813	/// We get the first number from destructs: `destructs.shift() == 3` => `destructs = [3, 1]`814	/// 3 elements counting from a => [a, b, c]815	/// Then we take first number from closures: `closures.shift() == 3` => `closures = [4, 0]`816	/// Then we take 3 items from referenced: `referenced.shift()x3 == d, e, f` => `referenced = [a, b, c, h]`817	///818	/// Thus we have [a, b, c] = [d, e, f]819	first_in_frame: LocalId,820}821822struct Closure<'a> {823	references: &'a [LocalId],824	ids: std::ops::Range<u32>,825}826827impl Closures {828	fn push_spec(&mut self, destruct_ids_count: usize, refs: &[LocalId]) {829		self.referenced.extend_from_slice(refs);830		self.spec_shapes.push((refs.len(), destruct_ids_count));831	}832833	fn iter_specs(&self) -> impl Iterator<Item = Closure<'_>> {834		let mut refs = self.referenced.as_slice();835		let mut next_id = self.first_in_frame.0;836		self.spec_shapes.iter().map(move |(refs_len, dest_count)| {837			let (this_refs, rest) = refs.split_at(*refs_len);838			refs = rest;839			let start = next_id;840			next_id += arridx(*dest_count);841			Closure {842				references: this_refs,843				ids: start..next_id,844			}845		})846	}847}848849#[derive(Debug, Clone, Copy, PartialEq, Eq)]850pub enum DiagLevel {851	Error,852	Warning,853}854855#[derive(Debug, Clone, Acyclic)]856pub struct Diagnostic {857	pub level: DiagLevel,858	pub message: String,859	pub span: Option<Span>,860}861862struct DefiningClosure {863	first_local: LocalId,864	n_locals: u16,865}866867impl DefiningClosure {868	fn resolve(&self, target: LocalId) -> Option<LocalSlot> {869		let end = self.first_local.0 + u32::from(self.n_locals);870		if target.0 >= self.first_local.0 && target.0 < end {871			Some(LocalSlot(872				u16::try_from(target.0 - self.first_local.0).expect("local slots overflow"),873			))874		} else {875			None876		}877	}878	fn define_local(&mut self, local: LocalId) -> LocalSlot {879		let slot = self.n_locals;880		let id = self.first_local.0 + u32::from(slot);881		debug_assert_eq!(local.0, id);882		self.n_locals = self.n_locals.checked_add(1).expect("local slots overflow");883		LocalSlot(slot)884	}885}886887/// Per-closure capture computation state.888struct ClosureFrame {889	/// Closure may allocate locals890	defining: Option<DefiningClosure>,891	/// `LocalId` => capture index892	captures: FxHashMap<LocalId, CaptureSlot>,893	/// Capture sources in insertion order; consumed by `pop_closure_frame`.894	capture_sources: Vec<LSlot>,895}896897#[allow(clippy::struct_excessive_bools)]898pub struct AnalysisStack {899	local_defs: Vec<LocalDefinition>,900	/// Shadowing isn't used in jsonnet much, 2 because `SmallVec` allows to store 2 ptr-sized without overhead.901	/// TODO: Add test for this assumption (sizeof(SmallVec<[usize; 1]>) == sizeof(SmallVec<[usize; 2]>))902	local_by_name: FxHashMap<IStr, SmallVec<[LocalId; 2]>>,903904	/// Depth of the current locals frame.905	depth: u32,906	/// Last depth, at which object has appeared. `u32::MAX` = not appeared at all907	last_object_depth: u32,908	/// First depth, at which object has appeared. `u32::MAX` = not appeared at all909	/// $ refers to this object.910	first_object_depth: u32,911912	/// `LocalId` bound to the innermost object's `this`913	this_local: Option<LocalId>,914	/// Outermost object `this`, aka `$`915	dollar_alias: Option<LocalId>,916	/// True iff `self` has been referenced in the current object immediate members (not nested children).917	cur_self_used: bool,918	/// True iff `super` has been referenced in the current object immediate members.919	cur_super_used: bool,920	/// True iff `$` has been referenced anywhere since the outermost object's scope was entered.921	dollar_used: bool,922923	/// Stack of closure frames (innermost on top).924	closure_stack: Vec<ClosureFrame>,925926	diagnostics: Vec<Diagnostic>,927	/// Whenever analysis would be broken due to static analysis error.928	errored: bool,929}930931#[must_use]932struct ClosureOnStack {933	bomb: DropBomb,934}935936impl AnalysisStack {937	pub fn new() -> Self {938		Self {939			local_defs: Vec::new(),940			local_by_name: FxHashMap::default(),941			depth: 0,942			last_object_depth: u32::MAX,943			first_object_depth: u32::MAX,944			this_local: None,945			dollar_alias: None,946			cur_self_used: false,947			cur_super_used: false,948			dollar_used: false,949			closure_stack: Vec::new(),950			diagnostics: Vec::new(),951			errored: false,952		}953	}954955	fn push_root_closure(&mut self, externals: u16) -> ClosureOnStack {956		assert!(957			self.closure_stack.is_empty(),958			"root is only possible with empty stack"959		);960961		self.closure_stack.push(ClosureFrame {962			defining: Some(DefiningClosure {963				first_local: LocalId(0),964				n_locals: externals,965			}),966			captures: FxHashMap::default(),967			capture_sources: Vec::new(),968		});969970		ClosureOnStack {971			bomb: DropBomb::new("root closure"),972		}973	}974975	fn push_closure_a(&mut self, first_local: LocalId) -> ClosureOnStack {976		self.closure_stack.push(ClosureFrame {977			defining: Some(DefiningClosure {978				first_local,979				n_locals: 0,980			}),981			captures: FxHashMap::default(),982			capture_sources: Vec::new(),983		});984		ClosureOnStack {985			bomb: DropBomb::new("closure with locals"),986		}987	}988989	#[inline]990	fn in_using_closure<T>(991		&mut self,992		inner: impl FnOnce(&mut AnalysisStack) -> T,993	) -> (ClosureShape, T) {994		fn push_closure_b(stack: &mut AnalysisStack) -> ClosureOnStack {995			stack.closure_stack.push(ClosureFrame {996				defining: None,997				captures: FxHashMap::default(),998				capture_sources: Vec::new(),999			});1000			ClosureOnStack {1001				bomb: DropBomb::new("closure with locals"),1002			}1003		}1004		let closure = push_closure_b(self);1005		let v = inner(self);1006		let shape = self.pop_closure(closure);1007		(shape, v)1008	}10091010	fn pop_closure(&mut self, mut closure: ClosureOnStack) -> ClosureShape {1011		closure.bomb.defuse();1012		let frame = self.closure_stack.pop().expect("closure frame");1013		ClosureShape {1014			captures: frame.capture_sources.into_boxed_slice(),1015			n_locals: frame.defining.map(|d| d.n_locals).unwrap_or_default(),1016		}1017	}10181019	/// Resolve a `LocalId` reference to an `LSlot` against the innermost1020	/// closure frame. May insert capture entries up the closure stack as1021	/// needed.1022	fn resolve_to_slot(&mut self, target: LocalId) -> LSlot {1023		let top = self.closure_stack.len();1024		debug_assert!(top > 0, "resolve_to_slot called with no closure frame");1025		Self::resolve_at(&mut self.closure_stack, top - 1, target)1026	}10271028	fn resolve_at(stack: &mut [ClosureFrame], idx: usize, target: LocalId) -> LSlot {1029		if let Some(def) = &stack[idx].defining {1030			if let Some(resolved) = def.resolve(target) {1031				return LSlot::Local(resolved);1032			}1033		} else {1034			// A sibling letrec slot must never be packed as a capture, or1035			// it would read an empty `OnceCell`.1036			for j in (0..idx).rev() {1037				if let Some(def) = &stack[j].defining {1038					if let Some(resolved) = def.resolve(target) {1039						return LSlot::Local(resolved);1040					}1041					break;1042				}1043			}1044		}1045		if let Some(&cap_idx) = stack[idx].captures.get(&target) {1046			return LSlot::Capture(cap_idx);1047		}1048		debug_assert!(idx > 0, "no enclosing closure frame for target {target:?}");1049		let parent_slot = Self::resolve_at(stack, idx - 1, target);1050		let frame = &mut stack[idx];1051		let cap_idx = CaptureSlot(1052			frame1053				.capture_sources1054				.len()1055				.try_into()1056				.expect("frame has more than u16::MAX captures"),1057		);1058		frame.capture_sources.push(parent_slot);1059		frame.captures.insert(target, cap_idx);1060		LSlot::Capture(cap_idx)1061	}10621063	fn next_local_id(&self) -> LocalId {1064		LocalId(arridx(self.local_defs.len()))1065	}10661067	fn report_error(&mut self, msg: impl Into<String>, span: Option<Span>) {1068		self.errored = true;1069		self.diagnostics.push(Diagnostic {1070			level: DiagLevel::Error,1071			message: msg.into(),1072			span,1073		});1074	}1075	fn report_warning(&mut self, msg: impl Into<String>, span: Option<Span>) {1076		self.diagnostics.push(Diagnostic {1077			level: DiagLevel::Warning,1078			message: msg.into(),1079			span,1080		});1081	}10821083	fn use_local(&mut self, name: &IStr, span: Span, taint: &mut AnalysisResult) -> Option<LSlot> {1084		let Some(ids) = self.local_by_name.get(name) else {1085			let names = suggest_names(name, self.local_by_name.keys());1086			self.report_error(1087				format!("undefined local: {name}{}", format_found(&names, "local")),1088				Some(span),1089			);1090			return None;1091		};1092		let id = *ids.last().expect("empty stacks should be removed");1093		let depth = self.depth;1094		let def = &mut self.local_defs[id.idx()];1095		def.use_at(depth);1096		taint.depend_on_local(def.defined_at_depth);1097		if def.analyzed {1098			taint.taint_by(def.analysis);1099		} else {1100			def.scratch_referenced = true;1101		}1102		Some(self.resolve_to_slot(id))1103	}11041105	/// Assign name to the value provided externally, e.g `std`.1106	pub fn define_external_local(&mut self, name: IStr, id: LocalId) {1107		assert!(1108			self.local_defs.iter().all(|d| d.analyzed),1109			"external locals must be defined before the root expression is analysed"1110		);1111		assert_eq!(1112			id,1113			self.next_local_id(),1114			"external local id mismatch for {name} (externals must be defined in allocation order)"1115		);1116		self.local_defs.push(LocalDefinition {1117			name: name.clone(),1118			span: None,1119			defined_at_depth: 0,1120			used_at_depth: u32::MAX,1121			used_by_sibling: false,1122			analysis: AnalysisResult::default(),1123			analyzed: true,1124			scratch_referenced: false,1125		});1126		self.local_by_name.entry(name).or_default().push(id);1127	}11281129	fn defining_closure_mut(&mut self) -> &mut DefiningClosure {1130		self.closure_stack1131			.iter_mut()1132			.rev()1133			.find_map(|c| c.defining.as_mut())1134			.expect("no enclosing defining closure frame")1135	}1136	fn defining_closure(&self) -> &DefiningClosure {1137		self.closure_stack1138			.iter()1139			.rev()1140			.find_map(|c| c.defining.as_ref())1141			.expect("no enclosing defining closure frame")1142	}1143}11441145impl Default for AnalysisStack {1146	fn default() -> Self {1147		Self::new()1148	}1149}11501151impl AnalysisStack {1152	fn top_defining_local(&self) -> LocalId {1153		self.defining_closure().first_local1154	}11551156	/// Merge `used`'s analysis into `user`'s analysis and record that `user`1157	/// transitively depends on `used` (same-frame sibling reference).1158	/// Returns `true` if `user`'s analysis changed.1159	fn propagate_analysis(&mut self, user: LocalId, used: LocalId) -> bool {1160		let (used_analysis, used_defined_at_depth) = {1161			let u = &self.local_defs[used.idx()];1162			(u.analysis, u.defined_at_depth)1163		};1164		let user_def = &mut self.local_defs[user.idx()];1165		let before_obj = user_def.analysis.object_dependent_depth;1166		let before_loc = user_def.analysis.local_dependent_depth;1167		user_def.analysis.taint_by(used_analysis);1168		user_def.analysis.depend_on_local(used_defined_at_depth);1169		before_obj != user_def.analysis.object_dependent_depth1170			|| before_loc != user_def.analysis.local_dependent_depth1171	}1172}11731174mod names {1175	use crate::names;11761177	names! {1178		this: "this",1179	}1180}11811182// Object scope helpers1183impl AnalysisStack {1184	#[inline]1185	fn in_object_scope<T>(1186		&mut self,1187		inner: impl FnOnce(&mut AnalysisStack) -> T,1188	) -> (ObjectUsage, ClosureShape, T) {1189		fn enter_object_scope(stack: &mut AnalysisStack) -> ObjectScope {1190			let is_outermost = stack.first_object_depth == u32::MAX;1191			let this_id = stack.next_local_id();1192			let closure = stack.push_closure_a(this_id);1193			let pushed = stack.push_pseudo_local(names::this());1194			debug_assert_eq!(pushed, this_id, "this pseudo-local id");1195			let scope = ObjectScope {1196				this_id,1197				is_outermost,1198				prev_this_local: stack.this_local,1199				prev_dollar_alias: stack.dollar_alias,1200				prev_cur_self_used: stack.cur_self_used,1201				prev_cur_super_used: stack.cur_super_used,1202				prev_dollar_used: is_outermost.then_some(stack.dollar_used),1203				prev_last_object: stack.last_object_depth,1204				prev_first_object: stack.first_object_depth,1205				closure,1206			};12071208			stack.this_local = Some(scope.this_id);1209			if is_outermost {1210				stack.dollar_alias = Some(scope.this_id);1211				stack.first_object_depth = stack.depth;1212				stack.dollar_used = false;1213			}1214			stack.last_object_depth = stack.depth;1215			stack.cur_self_used = false;1216			stack.cur_super_used = false;1217			scope1218		}12191220		fn leave_object_scope(1221			stack: &mut AnalysisStack,1222			scope: ObjectScope,1223		) -> (ObjectUsage, ClosureShape) {1224			let ObjectScope {1225				this_id,1226				is_outermost,1227				prev_this_local,1228				prev_dollar_alias,1229				prev_cur_self_used,1230				prev_cur_super_used,1231				prev_dollar_used,1232				prev_last_object,1233				prev_first_object,1234				closure,1235			} = scope;1236			let _ = stack.local_defs.pop().expect("this pseudo-local exists");1237			debug_assert_eq!(stack.local_defs.len(), this_id.0 as usize);12381239			let set_dollar = is_outermost && stack.dollar_used;1240			let usage = ObjectUsage {1241				this_used: stack.cur_self_used || stack.cur_super_used || set_dollar,1242				uses_super: stack.cur_super_used,1243				set_dollar,1244			};12451246			stack.this_local = prev_this_local;1247			stack.dollar_alias = prev_dollar_alias;1248			stack.cur_self_used = prev_cur_self_used;1249			stack.cur_super_used = prev_cur_super_used;1250			if let Some(prev) = prev_dollar_used {1251				stack.dollar_used = prev;1252			}1253			stack.last_object_depth = prev_last_object;1254			stack.first_object_depth = prev_first_object;12551256			let frame_shape = stack.pop_closure(closure);1257			(usage, frame_shape)1258		}1259		let scope = enter_object_scope(self);1260		let v = inner(self);1261		let (usage, shape) = leave_object_scope(self, scope);1262		(usage, shape, v)1263	}12641265	fn push_pseudo_local(&mut self, name: IStr) -> LocalId {1266		let id = self.next_local_id();1267		self.local_defs.push(LocalDefinition {1268			name,1269			span: None,1270			defined_at_depth: self.depth,1271			used_at_depth: u32::MAX,1272			used_by_sibling: false,1273			analysis: AnalysisResult::default(),1274			analyzed: true,1275			scratch_referenced: false,1276		});1277		{1278			let def = self.defining_closure_mut();1279			let _ = def.define_local(id);1280		}1281		id1282	}12831284	fn use_this(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1285		let id = self.this_local?;1286		self.cur_self_used = true;1287		self.use_pseudo_local(id, taint);1288		Some(self.resolve_to_slot(id))1289	}12901291	fn use_super(&mut self, taint: &mut AnalysisResult) -> Option<()> {1292		let id = self.this_local?;1293		self.cur_super_used = true;1294		self.use_pseudo_local(id, taint);1295		Some(())1296	}12971298	fn use_dollar(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1299		let id = self.dollar_alias?;1300		self.dollar_used = true;1301		self.use_pseudo_local(id, taint);1302		Some(self.resolve_to_slot(id))1303	}13041305	// TODO: Dedicated type for object references instead of "pseudo local" BS, idk1306	fn use_pseudo_local(&mut self, id: LocalId, taint: &mut AnalysisResult) {1307		let depth = self.depth;1308		let def = &mut self.local_defs[id.idx()];1309		def.use_at(depth);1310		taint.depend_on_local(def.defined_at_depth);1311		taint.depend_on_object(def.defined_at_depth);1312	}1313}13141315#[must_use]1316struct ObjectScope {1317	this_id: LocalId,1318	is_outermost: bool,1319	prev_this_local: Option<LocalId>,1320	prev_dollar_alias: Option<LocalId>,1321	prev_cur_self_used: bool,1322	prev_cur_super_used: bool,1323	prev_dollar_used: Option<bool>,1324	prev_last_object: u32,1325	prev_first_object: u32,1326	closure: ClosureOnStack,1327}13281329struct ObjectUsage {1330	this_used: bool,1331	uses_super: bool,1332	set_dollar: bool,1333}13341335fn analyze_assert(1336	stmt: &AssertStmt,1337	stack: &mut AnalysisStack,1338	taint: &mut AnalysisResult,1339) -> LAssertStmt {1340	let cond = analyze(&stmt.assertion.value, stack, taint);1341	let message = stmt.message.as_ref().map(|m| analyze(m, stack, taint));1342	LAssertStmt {1343		cond: Spanned::new(cond, stmt.assertion.span.clone()),1344		message,1345	}1346}13471348#[allow(clippy::too_many_lines)]1349pub fn analyze_named(1350	name: IStr,1351	expr: &Expr,1352	stack: &mut AnalysisStack,1353	taint: &mut AnalysisResult,1354) -> LExpr {1355	if let Expr::Function(span, params, body) = expr {1356		return analyze_function(Some(name), span, params, body, stack, taint);1357	}1358	analyze(expr, stack, taint)1359}1360#[allow(clippy::too_many_lines)]1361pub fn analyze(expr: &Expr, stack: &mut AnalysisStack, taint: &mut AnalysisResult) -> LExpr {1362	match expr {1363		Expr::Identity(span, l) => match l {1364			IdentityKind::This => stack.use_this(taint).map_or_else(1365				|| {1366					stack.report_error("`self` used outside of object", Some(span.clone()));1367					LExpr::BadLocal("self")1368				},1369				LExpr::Slot,1370			),1371			IdentityKind::Super => {1372				if stack.use_super(taint).is_some() {1373					LExpr::Super1374				} else {1375					stack.report_error("`super` used outside of object", Some(span.clone()));1376					LExpr::BadLocal("super")1377				}1378			}1379			IdentityKind::Dollar => stack.use_dollar(taint).map_or_else(1380				|| {1381					stack.report_error("`$` used outside of object", Some(span.clone()));1382					LExpr::BadLocal("$")1383				},1384				LExpr::Slot,1385			),1386		},1387		Expr::Trivial(tv) => LExpr::Trivial(tv.clone()),1388		Expr::Var(v) => stack1389			.use_local(&v.value, v.span.clone(), taint)1390			.map_or_else(|| LExpr::BadLocal("ref"), LExpr::Slot),1391		Expr::Arr(a) => {1392			if a.iter().all(|i| matches!(i, Expr::Trivial(_))) {1393				let trivials: Vec<_> = a1394					.iter()1395					.map(|i| match i {1396						Expr::Trivial(tv) => tv.clone(),1397						_ => unreachable!("checked above"),1398					})1399					.collect();1400				return LExpr::ArrConst(Rc::new(trivials));1401			}1402			let (shape, items) = stack.in_using_closure(|stack| {1403				a.iter()1404					.map(|v| analyze(v, stack, taint))1405					.collect::<Vec<_>>()1406			});1407			LExpr::Arr {1408				shape,1409				items: Rc::new(items),1410			}1411		}1412		Expr::ArrComp(inner, comp) => analyze_arr_comp(inner, comp, stack, taint),1413		Expr::Obj(obj) => LExpr::Obj(analyze_obj_body(obj, stack, taint)),1414		Expr::ObjExtend(base, obj) => LExpr::ObjExtend(1415			Box::new(analyze(base, stack, taint)),1416			analyze_obj_body(obj, stack, taint),1417		),1418		Expr::UnaryOp(op, value) => LExpr::UnaryOp(*op, Box::new(analyze(value, stack, taint))),1419		Expr::BinaryOp(op) => {1420			let BinaryOp {1421				lhs,1422				op: optype,1423				rhs,1424			} = &**op;1425			LExpr::BinaryOp {1426				lhs: Box::new(analyze(lhs, stack, taint)),1427				op: *optype,1428				rhs: Box::new(analyze(rhs, stack, taint)),1429			}1430		}1431		Expr::AssertExpr(assert) => {1432			let AssertExpr { assert, rest } = &**assert;1433			let assert = Rc::new(analyze_assert(assert, stack, taint));1434			let rest = Box::new(analyze(rest, stack, taint));1435			LExpr::AssertExpr { assert, rest }1436		}1437		Expr::LocalExpr(binds, body) => analyze_local_expr(binds, body, stack, taint),1438		Expr::Import(kind, path_expr) => {1439			let Expr::Trivial(TrivialVal::Str(path)) = &**path_expr else {1440				stack.report_error(1441					"import path must be a string literal",1442					Some(kind.span.clone()),1443				);1444				return LExpr::BadLocal("bad import");1445			};1446			LExpr::Import {1447				kind: kind.clone(),1448				kind_span: kind.span.clone(),1449				path: path.clone(),1450			}1451		}1452		Expr::ErrorStmt(span, inner) => {1453			LExpr::Error(span.clone(), Box::new(analyze(inner, stack, taint)))1454		}1455		Expr::Apply(applicable, args, tailstrict) => {1456			let app = analyze(applicable, stack, taint);1457			let ArgsDesc {1458				unnamed,1459				names,1460				values,1461			} = &args.value;1462			let unnamed_l = unnamed1463				.iter()1464				.map(|a| Rc::new(analyze(a, stack, taint)))1465				.collect();1466			let values_l = values1467				.iter()1468				.map(|a| Rc::new(analyze(a, stack, taint)))1469				.collect();1470			LExpr::Apply {1471				applicable: Box::new(app),1472				args: Spanned::new(1473					LArgsDesc {1474						unnamed: unnamed_l,1475						names: names.clone(),1476						values: values_l,1477					},1478					args.span.clone(),1479				),1480				tailstrict: *tailstrict,1481			}1482		}1483		Expr::Index { indexable, parts } => {1484			let idx = analyze(indexable, stack, taint);1485			let parts_l = parts1486				.iter()1487				.map(|p| {1488					let value = analyze(&p.value, stack, taint);1489					LIndexPart {1490						span: p.span.clone(),1491						value,1492						#[cfg(feature = "exp-null-coaelse")]1493						null_coaelse: p.null_coaelse,1494					}1495				})1496				.collect();1497			LExpr::Index {1498				indexable: Box::new(idx),1499				parts: parts_l,1500			}1501		}1502		Expr::Function(span, params, body) => {1503			analyze_function(None, span, params, body, stack, taint)1504		}1505		Expr::IfElse(ifelse) => {1506			let IfElse {1507				cond,1508				cond_then,1509				cond_else,1510			} = &**ifelse;1511			let cond_l = analyze(&cond.cond, stack, taint);1512			let then_l = analyze(cond_then, stack, taint);1513			let else_l = cond_else1514				.as_ref()1515				.map(|e| Box::new(analyze(e, stack, taint)));1516			LExpr::IfElse {1517				cond: Box::new(cond_l),1518				cond_then: Box::new(then_l),1519				cond_else: else_l,1520			}1521		}1522		Expr::Slice(slice) => {1523			let Slice {1524				value,1525				slice: SliceDesc { start, end, step },1526			} = &**slice;1527			let value_l = analyze(value, stack, taint);1528			let start_l = start.as_ref().map(|e| analyze(&e.value, stack, taint));1529			let end_l = end.as_ref().map(|e| analyze(&e.value, stack, taint));1530			let step_l = step.as_ref().map(|e| analyze(&e.value, stack, taint));1531			LExpr::Slice(Box::new(LSliceExpr {1532				value: value_l,1533				start: start_l,1534				end: end_l,1535				step: step_l,1536			}))1537		}1538	}1539}15401541fn analyze_local_expr(1542	binds: &[BindSpec],1543	body: &Expr,1544	stack: &mut AnalysisStack,1545	taint: &mut AnalysisResult,1546) -> LExpr {1547	if binds.is_empty() {1548		return analyze(body, stack, taint);1549	}1550	let frame_start = stack.next_local_id();1551	let closure = stack.push_closure_a(frame_start);1552	let (l_binds, body_expr) = process_local_frame(binds, stack, taint, |stack, taint| {1553		analyze(body, stack, taint)1554	});1555	let frame_shape = stack.pop_closure(closure);1556	LExpr::LocalExpr(Box::new(LLocalExpr {1557		frame_shape,1558		binds: l_binds,1559		body: body_expr,1560	}))1561}15621563fn analyze_bind_value(1564	bind: &BindSpec,1565	stack: &mut AnalysisStack,1566	taint: &mut AnalysisResult,1567) -> LExpr {1568	match bind {1569		BindSpec::Field {1570			value: Expr::Function(span, params, value),1571			into: Destruct::Full(name),1572		} => analyze_function(Some(name.value.clone()), span, params, value, stack, taint),1573		BindSpec::Field { value, .. } => analyze(value, stack, taint),1574		BindSpec::Function {1575			params,1576			value,1577			name,1578		} => analyze_function(1579			Some(name.value.clone()),1580			&name.span,1581			params,1582			value,1583			stack,1584			taint,1585		),1586	}1587}15881589fn process_local_frame<R>(1590	binds: &[BindSpec],1591	stack: &mut AnalysisStack,1592	taint: &mut AnalysisResult,1593	body_fn: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1594) -> (Vec<LBind>, R) {1595	let mut alloc = FrameAlloc::new(stack);15961597	let mut destructs: Vec<Option<LDestruct>> = Vec::with_capacity(binds.len());1598	for bind in binds {1599		destructs.push(alloc.alloc_bind(bind));1600	}1601	let mut pending = alloc.finish();16021603	let mut l_binds: Vec<LBind> = Vec::with_capacity(binds.len());1604	for (bind, destruct) in binds.iter().zip(destructs) {1605		let mut value_taint = AnalysisResult::default();1606		let (value_shape, value) = pending1607			.stack1608			.in_using_closure(|stack| analyze_bind_value(bind, stack, &mut value_taint));1609		taint.taint_by(value_taint);1610		if let Some(destruct) = destruct {1611			pending.record_spec_init(&destruct, value_taint);1612			l_binds.push(LBind {1613				destruct,1614				value_shape,1615				value: Rc::new(value),1616			});1617		} else {1618			pending.closures.push_spec(0, &[]);1619		}1620	}16211622	let body_frame = pending.finish();1623	let result = body_fn(body_frame.stack, taint);1624	body_frame.finish();16251626	(l_binds, result)1627}16281629fn analyze_function(1630	name: Option<IStr>,1631	span: &Span,1632	params: &ExprParams,1633	body: &Expr,1634	stack: &mut AnalysisStack,1635	taint: &mut AnalysisResult,1636) -> LExpr {1637	let mut alloc = FrameAlloc::new(stack);1638	let closure = alloc.push_locals_closure();16391640	let mut param_destructs: Vec<Option<LDestruct>> = Vec::with_capacity(params.exprs.len());1641	for p in &params.exprs {1642		param_destructs.push(alloc.alloc_destruct(&p.destruct));1643	}16441645	let mut pending = alloc.finish();16461647	let mut l_params: Vec<LParam> = Vec::with_capacity(params.exprs.len());1648	for (p, destruct) in params.exprs.iter().zip(param_destructs) {1649		let mut value_taint = AnalysisResult::default();1650		let default = p.default.as_ref().map_or_else(1651			|| None,1652			|d| {1653				Some(1654					pending1655						.stack1656						.in_using_closure(|stack| Rc::new(analyze(d, stack, &mut value_taint))),1657				)1658			},1659		);1660		taint.taint_by(value_taint);1661		if let Some(destruct) = destruct {1662			let name = match &p.destruct {1663				Destruct::Full(n) => Some(n.value.clone()),1664				#[cfg(feature = "exp-destruct")]1665				_ => None,1666			};1667			pending.record_spec_init(&destruct, value_taint);1668			l_params.push(LParam {1669				name,1670				destruct,1671				default,1672			});1673		} else {1674			pending.closures.push_spec(0, &[]);1675		}1676	}16771678	let body_frame = pending.finish();1679	let body_expr = analyze(body, body_frame.stack, taint);1680	body_frame.finish();1681	let body_shape = stack.pop_closure(closure);16821683	// function(x) x is an identity function1684	if l_params.len() == 1 && l_params[0].default.is_none() {1685		#[allow(irrefutable_let_patterns, reason = "refutable with exp-destruct")]1686		if let LDestruct::Full(param_slot) = &l_params[0].destruct1687			&& let LExpr::Slot(LSlot::Local(s)) = &body_expr1688			&& s == param_slot1689		{1690			stack.report_warning(1691				"do not define identity functions manually, use std.id instead",1692				Some(span.clone()),1693			);1694			return LExpr::IdentityFunction {};1695		}1696	}16971698	LExpr::Function(Rc::new(LFunction {1699		name,1700		params: l_params,1701		signature: params.signature.clone(),1702		body_shape,1703		body: Rc::new(body_expr),1704	}))1705}17061707fn analyze_obj_body(1708	obj: &ObjBody,1709	stack: &mut AnalysisStack,1710	taint: &mut AnalysisResult,1711) -> LObjBody {1712	match obj {1713		ObjBody::MemberList(members) => {1714			let lowered = analyze_obj_members(members, stack, taint);1715			match try_lower_static(lowered) {1716				Ok(static_members) => LObjBody::StaticMembers(Box::new(static_members)),1717				Err(member_list) => LObjBody::MemberList(member_list),1718			}1719		}1720		ObjBody::ObjComp(comp) => LObjBody::ObjComp(Box::new(analyze_obj_comp(comp, stack, taint))),1721	}1722}17231724fn try_lower_static(members: LObjMembers) -> Result<LObjStaticMembers, LObjMembers> {1725	let mut seen: FxHashSet<IStr> = FxHashSet::with_capacity(members.fields.len());1726	for f in &members.fields {1727		match &f.name {1728			LFieldName::Fixed(name) => {1729				if !seen.insert(name.clone()) {1730					return Err(members);1731				}1732			}1733			LFieldName::Dyn(_) => return Err(members),1734		}1735	}17361737	let LObjMembers {1738		frame_shape,1739		this,1740		set_dollar,1741		uses_super,1742		locals,1743		asserts,1744		fields,1745	} = members;17461747	let mut shape_fields = Vec::with_capacity(fields.len());1748	let mut bindings = Vec::with_capacity(fields.len());1749	let mut next_index = FieldIndex::default();1750	for f in fields {1751		let LFieldName::Fixed(name) = f.name else {1752			unreachable!("checked above");1753		};1754		let index = next_index;1755		next_index = next_index.next();1756		shape_fields.push(ShapeField {1757			name,1758			flags: ObjFieldFlags::new(f.plus, f.visibility),1759			location: None,1760			index,1761		});1762		bindings.push(f.value);1763	}17641765	Ok(LObjStaticMembers {1766		frame_shape,1767		this,1768		set_dollar,1769		uses_super,1770		locals,1771		asserts,1772		shape: Rc::new(ObjShape::new(shape_fields)),1773		bindings,1774	})1775}17761777fn analyze_obj_members(1778	members: &ObjMembers,1779	stack: &mut AnalysisStack,1780	taint: &mut AnalysisResult,1781) -> LObjMembers {1782	let ObjMembers {1783		locals,1784		asserts,1785		fields,1786	} = members;17871788	// Names are analyzed in enclosing scope, they can't depend on locals or self/super1789	let field_names: Vec<LFieldName> = fields1790		.iter()1791		.map(|f| match &f.name.value {1792			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1793			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1794		})1795		.collect();17961797	let (usage, frame_shape, (l_binds, (l_asserts_opt, l_fields))) =1798		stack.in_object_scope(|stack| {1799			process_local_frame(locals, stack, taint, |stack, taint| {1800				let l_asserts_opt = if asserts.is_empty() {1801					None1802				} else {1803					let (shape, l_asserts) = stack.in_using_closure(|stack| {1804						let mut l_asserts = Vec::with_capacity(asserts.len());1805						for a in asserts {1806							let mut assert_taint = AnalysisResult::default();1807							l_asserts.push(analyze_assert(a, stack, &mut assert_taint));1808							taint.taint_by(assert_taint);1809						}1810						l_asserts1811					});1812					Some(Rc::new(LObjAsserts {1813						shape,1814						asserts: l_asserts,1815					}))1816				};1817				let mut l_fields = Vec::with_capacity(fields.len());1818				for (f, name) in fields.iter().zip(field_names) {1819					let value = stack.in_using_closure(|stack| {1820						if let Some(params) = &f.params {1821							analyze_function(1822								name.function_name(),1823								&f.name.span,1824								params,1825								&f.value,1826								stack,1827								taint,1828							)1829						} else {1830							analyze(&f.value, stack, taint)1831						}1832					});1833					l_fields.push(LFieldMember {1834						name,1835						plus: f.plus,1836						visibility: f.visibility,1837						value: Rc::new(value),1838					});1839				}1840				(l_asserts_opt, l_fields)1841			})1842		});1843	// `this` was allocated as the first local of the object's frame,1844	// so its slot is 0 within that frame.1845	let this_slot = usage.this_used.then_some(LocalSlot(0));1846	LObjMembers {1847		frame_shape,1848		this: this_slot,1849		set_dollar: usage.set_dollar,1850		uses_super: usage.uses_super,1851		locals: Rc::new(l_binds),1852		asserts: l_asserts_opt,1853		fields: l_fields,1854	}1855}18561857fn analyze_obj_comp(1858	comp: &ObjComp,1859	stack: &mut AnalysisStack,1860	taint: &mut AnalysisResult,1861) -> LObjComp {1862	let res = analyze_comp_specs(&comp.compspecs, stack, taint, |stack, taint| {1863		let field_name = match &comp.field.name.value {1864			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1865			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1866		};18671868		let (usage, frame_shape, body) = stack.in_object_scope(|stack| {1869			process_local_frame(&comp.locals, stack, taint, |stack, taint| {1870				let value = stack.in_using_closure(|stack| {1871					if let Some(params) = &comp.field.params {1872						analyze_function(1873							None,1874							&comp.field.name.span,1875							params,1876							&comp.field.value,1877							stack,1878							taint,1879						)1880					} else {1881						analyze(&comp.field.value, stack, taint)1882					}1883				});1884				LFieldMember {1885					name: field_name,1886					plus: comp.field.plus,1887					visibility: comp.field.visibility,1888					value: Rc::new(value),1889				}1890			})1891		});1892		(usage, frame_shape, body)1893	});1894	let (usage, frame_shape, (locals, field)) = res.inner;1895	let this_slot = usage.this_used.then_some(LocalSlot(0));1896	LObjComp {1897		frame_shape: Rc::new(frame_shape),1898		this: this_slot,1899		set_dollar: usage.set_dollar,1900		uses_super: usage.uses_super,1901		locals: Rc::new(locals),1902		field,1903		compspecs: res.compspecs,1904	}1905}19061907fn analyze_arr_comp(1908	inner: &Expr,1909	specs: &[CompSpec],1910	stack: &mut AnalysisStack,1911	taint: &mut AnalysisResult,1912) -> LExpr {1913	let res = analyze_comp_specs(specs, stack, taint, |stack, taint| {1914		stack.in_using_closure(|stack| analyze(inner, stack, taint))1915	});1916	let (value_shape, value) = res.inner;1917	LExpr::ArrComp(Box::new(LArrComp {1918		value_shape,1919		value: Rc::new(value),1920		compspecs: res.compspecs,1921	}))1922}19231924fn analyze_comp_specs<R>(1925	specs: &[CompSpec],1926	stack: &mut AnalysisStack,1927	taint: &mut AnalysisResult,1928	inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1929) -> CompSpecResult<R> {1930	fn go<R>(1931		idx: usize,1932		specs: &[CompSpec],1933		outer_depth: u32,1934		stack: &mut AnalysisStack,1935		taint: &mut AnalysisResult,1936		inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1937	) -> (R, Vec<LCompSpec>) {1938		if idx >= specs.len() {1939			return (inside(stack, taint), Vec::new());1940		}1941		match &specs[idx] {1942			CompSpec::IfSpec(IfSpecData { cond, .. }) => {1943				let cond_l = analyze(cond, stack, taint);1944				let (r, mut rest) = go(idx + 1, specs, outer_depth, stack, taint, inside);1945				rest.insert(0, LCompSpec::If(cond_l));1946				(r, rest)1947			}1948			CompSpec::ForSpec(ForSpecData { destruct, over }) => {1949				let mut over_taint = AnalysisResult::default();1950				let over_l = analyze(over, stack, &mut over_taint);1951				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1952				taint.taint_by(over_taint);19531954				let mut alloc = FrameAlloc::new(stack);1955				let closure = alloc.push_locals_closure();1956				let Some(l_destruct) = alloc.alloc_destruct(destruct) else {1957					stack.pop_closure(closure);1958					return go(idx + 1, specs, outer_depth, stack, taint, inside);1959				};1960				let mut pending = alloc.finish();19611962				let var_analysis = AnalysisResult::default();1963				pending.record_spec_init(&l_destruct, var_analysis);19641965				let body_frame = pending.finish();1966				let (r, mut rest) =1967					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);1968				body_frame.finish();1969				let frame_shape = stack.pop_closure(closure);19701971				rest.insert(1972					0,1973					LCompSpec::For {1974						frame_shape,1975						destruct: l_destruct,1976						over: over_l,1977						loop_invariant,1978					},1979				);1980				(r, rest)1981			}1982			#[cfg(feature = "exp-object-iteration")]1983			CompSpec::ForObjSpec(data) => {1984				let mut over_taint = AnalysisResult::default();1985				let over_l = analyze(&data.over, stack, &mut over_taint);1986				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1987				taint.taint_by(over_taint);19881989				let mut alloc = FrameAlloc::new(stack);1990				let closure = alloc.push_locals_closure();1991				let Some((_, key_slot)) = alloc.define_local(data.key.clone(), None) else {1992					stack.pop_closure(closure);1993					return go(idx + 1, specs, outer_depth, stack, taint, inside);1994				};1995				let Some(l_value) = alloc.alloc_destruct(&data.value) else {1996					stack.pop_closure(closure);1997					return go(idx + 1, specs, outer_depth, stack, taint, inside);1998				};1999				let mut pending = alloc.finish();20002001				let var_analysis = AnalysisResult::default();2002				pending.record_spec_init(&LDestruct::Full(key_slot), var_analysis);2003				pending.record_spec_init(&l_value, var_analysis);20042005				let body_frame = pending.finish();2006				let (r, mut rest) =2007					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);2008				body_frame.finish();2009				let frame_shape = stack.pop_closure(closure);20102011				rest.insert(2012					0,2013					LCompSpec::ForObj {2014						frame_shape,2015						key: key_slot,2016						visibility: data.visibility,2017						value: l_value,2018						over: over_l,2019						loop_invariant,2020					},2021				);2022				(r, rest)2023			}2024		}2025	}2026	let outer_depth = stack.depth;2027	let (r, compspecs) = go(0, specs, outer_depth, stack, taint, inside);2028	CompSpecResult {2029		inner: r,2030		compspecs,2031	}2032}20332034struct CompSpecResult<R> {2035	inner: R,2036	compspecs: Vec<LCompSpec>,2037}20382039pub fn analyze_root(expr: &Expr, ctx: Vec<(IStr, LocalId)>) -> AnalysisReport {2040	let mut stack = AnalysisStack::new();2041	for (name, id) in ctx {2042		stack.define_external_local(name, id);2043	}20442045	let externals_count: u16 = stack2046		.local_defs2047		.len()2048		.try_into()2049		.expect("more than u16::MAX externals");2050	let closure = stack.push_root_closure(externals_count);20512052	let mut taint = AnalysisResult::default();2053	let lir = analyze(expr, &mut stack, &mut taint);20542055	let root_shape = stack.pop_closure(closure);2056	debug_assert!(2057		stack.closure_stack.is_empty(),2058		"closure stack imbalance after analyze"2059	);20602061	AnalysisReport {2062		lir,2063		root_shape,2064		root_analysis: taint,2065		diagnostics_list: stack.diagnostics,2066		errored: stack.errored,2067	}2068}20692070pub struct AnalysisReport {2071	pub lir: LExpr,2072	pub root_shape: ClosureShape,2073	pub root_analysis: AnalysisResult,2074	pub diagnostics_list: Vec<Diagnostic>,2075	pub errored: bool,2076}20772078#[cfg(test)]2079mod tests {2080	#[test]2081	#[cfg(not(feature = "exp-null-coaelse"))]2082	fn snapshots() {2083		use std::fs;20842085		use insta::{assert_snapshot, glob};2086		use jrsonnet_ir::Source;20872088		use super::*;20892090		fn render_diagnostics(src: &str, diags: &[Diagnostic]) -> String {2091			use std::fmt::Write;20922093			use hi_doc::{Formatting, SnippetBuilder, Text};20942095			let mut out = String::new();2096			let mut unspanned = Vec::new();2097			let mut spanned: Vec<&Diagnostic> = Vec::new();2098			for d in diags {2099				if d.span.is_some() {2100					spanned.push(d);2101				} else {2102					unspanned.push(d);2103				}2104			}2105			if !spanned.is_empty() {2106				let mut builder = SnippetBuilder::new(src);2107				for d in spanned {2108					let span = d.span.as_ref().expect("spanned");2109					let ab = match d.level {2110						DiagLevel::Error => {2111							builder.error(Text::fragment(d.message.clone(), Formatting::default()))2112						}2113						DiagLevel::Warning => builder2114							.warning(Text::fragment(d.message.clone(), Formatting::default())),2115					};2116					ab.range(span.range()).build();2117				}2118				out.push_str(&hi_doc::source_to_ansi(&builder.build()));2119			}2120			for d in unspanned {2121				let prefix = match d.level {2122					DiagLevel::Error => "error",2123					DiagLevel::Warning => "warning",2124				};2125				writeln!(out, "{prefix}: {}", d.message).expect("fmt");2126			}2127			out2128		}2129		fn fmt_depth(d: u32) -> String {2130			if d == u32::MAX {2131				"none".into()2132			} else {2133				d.to_string()2134			}2135		}21362137		glob!("analysis_tests/*.jsonnet", |path| {2138			let code = fs::read_to_string(path).expect("read test file");2139			let src = Source::new_virtual("<test>".into(), code.clone().into());2140			let expr = crate::parse_jsonnet(&code, src.clone()).expect("parse");2141			let report = analyze_root(&expr, Vec::new());21422143			let diagnostics = render_diagnostics(src.code(), &report.diagnostics_list);2144			// Strip ANSI escapes from diagnostics so snapshots are readable.2145			let diagnostics = strip_ansi_escapes::strip_str(&diagnostics);2146			let rendered = format!(2147				"--- source ---\n{}\n--- root analysis ---\nobject_dependent_depth: {}\nlocal_dependent_depth: {}\nerrored: {}\n--- diagnostics ---\n{}--- lir ---\n{:#?}\n",2148				code.trim_end(),2149				fmt_depth(report.root_analysis.object_dependent_depth),2150				fmt_depth(report.root_analysis.local_dependent_depth),2151				report.errored,2152				diagnostics,2153				report.lir,2154			);2155			assert_snapshot!(rendered);2156		});2157	}2158}