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, 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	Trivial(TrivialVal),142	Arr {143		shape: ClosureShape,144		items: Rc<Vec<LExpr>>,145	},146	ArrConst(Rc<Vec<TrivialVal>>),147	ArrComp(Box<LArrComp>),148	Obj(LObjBody),149	ObjExtend(Box<LExpr>, LObjBody),150	UnaryOp(UnaryOpType, Box<LExpr>),151	BinaryOp {152		lhs: Box<LExpr>,153		op: BinaryOpType,154		rhs: Box<LExpr>,155	},156	AssertExpr {157		assert: Rc<LAssertStmt>,158		rest: Box<LExpr>,159	},160	Error(Span, Box<LExpr>),161	LocalExpr(Box<LLocalExpr>),162	Import {163		kind: Spanned<ImportKind>,164		kind_span: Span,165		path: IStr,166	},167	Apply {168		applicable: Box<LExpr>,169		args: Spanned<LArgsDesc>,170		tailstrict: bool,171	},172	Index {173		indexable: Box<LExpr>,174		parts: Vec<LIndexPart>,175	},176	Function(Rc<LFunction>),177	IdentityFunction,178	IfElse {179		cond: Box<LExpr>,180		cond_then: Box<LExpr>,181		cond_else: Option<Box<LExpr>>,182	},183	Slice(Box<LSliceExpr>),184	Super,185186	/// Allows partial evaluation of broken expression tree,187	/// expressions with failed static analysis end up here188	BadLocal(&'static str),189}190191#[derive(Debug, Acyclic)]192pub struct LLocalExpr {193	pub frame_shape: ClosureShape,194	pub binds: Vec<LBind>,195	pub body: LExpr,196}197198#[derive(Debug, Acyclic)]199pub struct LFunction {200	pub name: Option<IStr>,201	pub params: Vec<LParam>,202	pub signature: FunctionSignature,203204	pub body_shape: ClosureShape,205	pub body: Rc<LExpr>,206}207208#[derive(Debug, Acyclic)]209pub struct LParam {210	pub name: Option<IStr>,211	pub destruct: LDestruct,212213	pub default: Option<(ClosureShape, Rc<LExpr>)>,214}215216#[derive(Debug, Acyclic)]217pub struct LBind {218	pub destruct: LDestruct,219	pub value_shape: ClosureShape,220	pub value: Rc<LExpr>,221}222223#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, Acyclic)]224pub struct CaptureSlot(pub(crate) u16);225#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, Acyclic)]226pub struct LocalSlot(pub(crate) u16);227228#[derive(Debug, Acyclic)]229pub enum LDestruct {230	Full(LocalSlot),231	#[cfg(feature = "exp-destruct")]232	Skip,233	#[cfg(feature = "exp-destruct")]234	Array {235		start: Vec<LDestruct>,236		rest: Option<LDestructRest>,237		end: Vec<LDestruct>,238	},239	#[cfg(feature = "exp-destruct")]240	Object {241		fields: Vec<LDestructField>,242		rest: Option<LDestructRest>,243	},244}245246#[derive(Debug, Clone, Copy, Acyclic)]247pub enum LDestructRest {248	Keep(LocalSlot),249	Drop,250}251252#[derive(Debug, Acyclic)]253pub struct LDestructField {254	pub name: IStr,255	pub into: Option<LDestruct>,256	pub default: Option<(ClosureShape, Rc<LExpr>)>,257}258259impl LDestruct {260	pub fn each_slot<F: FnMut(LocalSlot)>(&self, f: &mut F) {261		match self {262			Self::Full(s) => f(*s),263			#[cfg(feature = "exp-destruct")]264			Self::Skip => {}265			#[cfg(feature = "exp-destruct")]266			Self::Array { start, rest, end } => {267				for d in start {268					d.each_slot(f);269				}270				if let Some(LDestructRest::Keep(s)) = rest {271					f(*s);272				}273				for d in end {274					d.each_slot(f);275				}276			}277			#[cfg(feature = "exp-destruct")]278			Self::Object { fields, rest } => {279				for field in fields {280					if let Some(into) = &field.into {281						into.each_slot(f);282					} else {283						unreachable!("shorthand object destruct must store `into`");284					}285				}286				if let Some(LDestructRest::Keep(s)) = rest {287					f(*s);288				}289			}290		}291	}292293	pub fn slots(&self) -> SmallVec<[LocalSlot; 1]> {294		let mut out = SmallVec::new();295		self.each_slot(&mut |s| out.push(s));296		out297	}298}299300#[derive(Debug, Acyclic)]301pub struct LSliceExpr {302	pub value: LExpr,303	pub start: Option<LExpr>,304	pub end: Option<LExpr>,305	pub step: Option<LExpr>,306}307308#[derive(Debug, Acyclic)]309pub struct LArgsDesc {310	pub unnamed: Vec<Rc<LExpr>>,311	pub names: Vec<IStr>,312	pub values: Vec<Rc<LExpr>>,313}314315#[derive(Debug, Acyclic)]316pub struct LAssertStmt {317	pub cond: Spanned<LExpr>,318	pub message: Option<LExpr>,319}320321#[derive(Debug, Acyclic)]322pub struct LIndexPart {323	pub span: Span,324	pub value: LExpr,325	#[cfg(feature = "exp-null-coaelse")]326	pub null_coaelse: bool,327}328329#[derive(Debug, Acyclic)]330pub enum LObjBody {331	MemberList(LObjMembers),332	ObjComp(Box<LObjComp>),333}334335#[derive(Debug, Acyclic)]336pub struct LObjMembers {337	pub frame_shape: ClosureShape,338	/// If current object identity (`super`/`this`/`$`) is used, `this` should339	/// be saved to the specified local slot.340	pub this: Option<LocalSlot>,341	/// Set if dollar should also be assigned to object identity, `this` should also be set (TODO: proper type-level validation)342	pub set_dollar: bool,343	/// True iff `super` is referenced by this object's members.344	pub uses_super: bool,345346	pub locals: Rc<Vec<LBind>>,347	pub asserts: Option<Rc<LObjAsserts>>,348	pub fields: Vec<LFieldMember>,349}350351#[derive(Debug, Acyclic)]352pub struct LObjComp {353	pub frame_shape: Rc<ClosureShape>,354	pub this: Option<LocalSlot>,355	pub set_dollar: bool,356	pub uses_super: bool,357358	pub locals: Rc<Vec<LBind>>,359	pub field: LFieldMember,360	pub compspecs: Vec<LCompSpec>,361}362363#[derive(Debug, Acyclic)]364pub struct LFieldMember {365	pub name: LFieldName,366	pub plus: bool,367	pub visibility: Visibility,368	pub value: Rc<(ClosureShape, LExpr)>,369}370371#[derive(Debug, Acyclic)]372pub struct LClosure<T: Acyclic> {373	pub shape: ClosureShape,374	pub value: T,375}376377#[derive(Debug, Acyclic)]378pub struct LObjAsserts {379	pub shape: ClosureShape,380	pub asserts: Vec<LAssertStmt>,381}382383#[derive(Debug, Acyclic)]384pub enum LFieldName {385	Fixed(IStr),386	Dyn(LExpr),387}388impl LFieldName {389	fn function_name(&self) -> Option<IStr> {390		match self {391			LFieldName::Fixed(istr) => Some(istr.clone()),392			LFieldName::Dyn(_) => None,393		}394	}395}396397#[derive(Debug, Acyclic)]398pub struct LArrComp {399	pub value_shape: ClosureShape,400	pub value: Rc<LExpr>,401	pub compspecs: Vec<LCompSpec>,402}403404#[derive(Debug, Acyclic)]405pub enum LCompSpec {406	If(LExpr),407	For {408		frame_shape: ClosureShape,409		destruct: LDestruct,410		over: LExpr,411		/// Is `over` does not depend on any variable introduced by an earlier for-spec in this comprehension chain412		loop_invariant: bool,413	},414	#[cfg(feature = "exp-object-iteration")]415	ForObj {416		frame_shape: ClosureShape,417		key: LocalSlot,418		visibility: jrsonnet_ir::Visibility,419		value: LDestruct,420		over: LExpr,421		loop_invariant: bool,422	},423}424425struct FrameAlloc<'s> {426	first_in_frame: LocalId,427	stack: &'s mut AnalysisStack,428	bomb: DropBomb,429}430impl<'s> FrameAlloc<'s> {431	fn new(stack: &'s mut AnalysisStack) -> Self {432		FrameAlloc {433			first_in_frame: stack.next_local_id(),434			stack,435			bomb: DropBomb::new("binding frame state"),436		}437	}438439	fn push_locals_closure(&mut self) -> ClosureOnStack {440		self.stack.push_closure_a(self.first_in_frame)441	}442443	fn define_local(&mut self, name: IStr, span: Option<Span>) -> Option<(LocalId, LocalSlot)> {444		let id = self.stack.next_local_id();445		let stack = self.stack.local_by_name.entry(name.clone()).or_default();446		if let Some(&existing) = stack.last()447			&& !existing.defined_before(self.first_in_frame)448		{449			self.stack.report_error(450				format!("local is already defined in the current frame: {name}"),451				span,452			);453			return None;454		}455		stack.push(id);456		self.stack.local_defs.push(LocalDefinition {457			name,458			span,459			defined_at_depth: self.stack.depth,460			used_at_depth: u32::MAX,461			used_by_sibling: false,462			analysis: AnalysisResult::default(),463			analyzed: false,464			scratch_referenced: false,465		});466		let def = self.stack.defining_closure_mut();467		Some((id, def.define_local(id)))468	}469	fn alloc_bind(&mut self, bind: &BindSpec) -> Option<LDestruct> {470		match bind {471			BindSpec::Field { into, .. } => self.alloc_destruct(into),472			BindSpec::Function { name, .. } => {473				let (_, id) = self.define_local(name.value.clone(), Some(name.span.clone()))?;474				Some(LDestruct::Full(id))475			}476		}477	}478	fn alloc_destruct(&mut self, destruct: &Destruct) -> Option<LDestruct> {479		Some(match destruct {480			Destruct::Full(name) => {481				let (_, id) = self.define_local(name.value.clone(), Some(name.span.clone()))?;482				LDestruct::Full(id)483			}484			#[cfg(feature = "exp-destruct")]485			Destruct::Skip => LDestruct::Skip,486			#[cfg(feature = "exp-destruct")]487			Destruct::Array { start, rest, end } => {488				let start = start489					.iter()490					.map(|d| self.alloc_destruct(d))491					.collect::<Option<Vec<_>>>()?;492				let rest = match rest {493					Some(jrsonnet_ir::DestructRest::Keep(name)) => {494						let (_, id) = self.define_local(name.clone(), None)?;495						Some(LDestructRest::Keep(id))496					}497					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),498					None => None,499				};500				let end = end501					.iter()502					.map(|d| self.alloc_destruct(d))503					.collect::<Option<Vec<_>>>()?;504				LDestruct::Array { start, rest, end }505			}506			#[cfg(feature = "exp-destruct")]507			Destruct::Object { fields, rest } => {508				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());509				// Allocate destruct LocalIds, then analyse defaults510				for (name, into, _default) in fields {511					let into = if let Some(inner) = into {512						self.alloc_destruct(inner)?513					} else {514						let (_, id) = self.define_local(name.clone(), None)?;515						LDestruct::Full(id)516					};517					l_fields.push((name.clone(), into));518				}519				// All locals exist, so defaults can reference any sibling.520				let l_fields: Vec<LDestructField> = l_fields521					.into_iter()522					.zip(fields.iter())523					.map(|((name, into), (_n, _i, default))| {524						let default = match default {525							Some(e) => {526								let mut default_taint = AnalysisResult::default();527								Some(self.stack.in_using_closure(|stack| {528									Rc::new(analyze(&e.value, stack, &mut default_taint))529								}))530							}531							None => None,532						};533						LDestructField {534							name,535							into: Some(into),536							default,537						}538					})539					.collect();540				let rest = match rest {541					Some(jrsonnet_ir::DestructRest::Keep(name)) => {542						let (_, id) = self.define_local(name.clone(), None)?;543						Some(LDestructRest::Keep(id))544					}545					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),546					None => None,547				};548				LDestruct::Object {549					fields: l_fields,550					rest,551				}552			}553		})554	}555556	fn finish(self) -> PendingInit<'s> {557		let Self {558			first_in_frame,559			stack,560			bomb,561		} = self;562		let first_after_frame = stack.next_local_id();563		PendingInit {564			first_after_frame,565			stack,566			closures: Closures {567				referenced: vec![],568				spec_shapes: vec![],569				first_in_frame,570			},571			bomb,572		}573	}574}575576/// Frame state: `LocalIds` allocated, values not yet analysed.577struct PendingInit<'s> {578	first_after_frame: LocalId,579	stack: &'s mut AnalysisStack,580	closures: Closures,581	bomb: DropBomb,582}583584impl<'s> PendingInit<'s> {585	/// Record the analysis of a spec's value: stamp every id bound by the586	/// spec with `analysis`, collect the spec's same-frame references, and587	/// append them to `closures`.588	fn record_spec_init(&mut self, destruct: &LDestruct, analysis: AnalysisResult) {589		let mut refs: SmallVec<[LocalId; 4]> = SmallVec::new();590		for i in self.closures.first_in_frame.0..self.first_after_frame.0 {591			let def = &mut self.stack.local_defs[i as usize];592			if def.scratch_referenced {593				refs.push(LocalId(i));594				def.scratch_referenced = false;595			}596		}597598		let mut ids_count = 0;599		let first_local = self.stack.top_defining_local();600		destruct.each_slot(&mut |slot| {601			ids_count += 1;602			let id = LocalId(first_local.0 + u32::from(slot.0));603			let def = &mut self.stack.local_defs[id.idx()];604			debug_assert!(!def.analyzed, "sanity: local {:?} analysed twice", def.name);605			def.analysis = analysis;606			def.analyzed = true;607		});608		self.closures.push_spec(ids_count, &refs);609	}610	/// After all specs are analysed, propagate dependency information between611	/// siblings to a fix-point, then switch to "body" mode.612	fn finish(self) -> PendingBody<'s> {613		let Self {614			first_after_frame,615			closures,616			stack,617			bomb,618		} = self;619620		debug_assert_eq!(621			first_after_frame,622			stack.next_local_id(),623			"frame initialisation left unfinished locals"624		);625626		debug_assert_eq!(627			closures.spec_shapes.iter().map(|(_, d)| *d).sum::<usize>(),628			(first_after_frame.0 - closures.first_in_frame.0) as usize,629			"closures destruct-id counts must match frame local count"630		);631632		let mut changed = true;633		while changed {634			changed = false;635			for spec in closures.iter_specs() {636				for id_raw in spec.ids.clone() {637					let user = LocalId(id_raw);638					for &used in spec.references {639						changed |= stack.propagate_analysis(user, used);640					}641				}642			}643		}644645		stack.depth += 1;646		PendingBody {647			first_after_frame,648			closures,649			stack,650			bomb,651		}652	}653}654655/// Frame state: values analysed, body not yet walked.656struct PendingBody<'s> {657	first_after_frame: LocalId,658	closures: Closures,659	stack: &'s mut AnalysisStack,660	bomb: DropBomb,661}662impl PendingBody<'_> {663	/// After the body is processed, drop the frame's locals and emit any664	/// "unused local" warnings.665	fn finish(self) {666		let PendingBody {667			first_after_frame,668			closures,669			stack,670			mut bomb,671		} = self;672		bomb.defuse();673		stack.depth -= 1;674675		debug_assert_eq!(676			first_after_frame,677			stack.next_local_id(),678			"nested scopes must be popped before outer frames"679		);680681		let mut changed = true;682		while changed {683			changed = false;684			for spec in closures.iter_specs() {685				// Effective used_at_depth for the spec = min over its ids.686				let mut min_used_at = u32::MAX;687				for id_raw in spec.ids.clone() {688					min_used_at = min_used_at.min(stack.local_defs[id_raw as usize].used_at_depth);689				}690				if min_used_at == u32::MAX {691					continue;692				}693				for &used in spec.references {694					let used_def = &mut stack.local_defs[used.idx()];695					if min_used_at < used_def.used_at_depth {696						used_def.used_at_depth = min_used_at;697						changed = true;698					}699				}700			}701		}702703		let drained: Vec<LocalDefinition> = stack704			.local_defs705			.drain(closures.first_in_frame.idx()..)706			.collect();707		for (i, def) in drained.iter().enumerate().rev() {708			let id = LocalId(closures.first_in_frame.0 + arridx(i));709			let stack_locals = stack710				.local_by_name711				.get_mut(&def.name)712				.expect("local must be in name map");713			let popped = stack_locals.pop().expect("name stack should not be empty");714			debug_assert_eq!(popped, id, "name stack integrity");715			if stack_locals.is_empty() {716				stack.local_by_name.remove(&def.name);717			}718719			if def.used_at_depth == u32::MAX {720				if def.used_by_sibling {721					stack.report_warning(722						format!("local is only referenced by unused siblings: {}", def.name),723						def.span.clone(),724					);725				} else {726					stack.report_warning(format!("unused local: {}", def.name), def.span.clone());727				}728			} else if def.analysis.local_dependent_depth > def.defined_at_depth729				&& def.analysis.object_dependent_depth > def.defined_at_depth730				&& def.defined_at_depth != 0731			{732				// The value doesn't depend on anything defined at or inside733				// this local's scope - can be hoisted, unfortunately not automatically.734				stack.report_warning(735					format!("local could be hoisted to an outer scope: {}", def.name),736					def.span.clone(),737				);738			}739		}740	}741}742743struct Closures {744	/// All the referenced locals, maybe repeated multiple times745	/// It is recorded as continous vec of sets, I.e we have746	/// a = 1, 2, 3747	/// b = 3, 4, 5, 6748	/// And in `referenced` we have `[ 1, 2, 3, 3, 4, 5, 6 ]`. To actually get, which closure refers to which element, see `spec_shapes`...749	/// Flat concatenation of sibling-local references across all specs.750	referenced: Vec<LocalId>,751	/// Amount of elements per closure, for the above case it is a = 3, b = 4, so here752	/// lies `[ 3, 4 ]`753	/// ~~closures: Vec<usize>,~~754	/// Finally, we have destructs.755	/// Because single destruct references single closure, but destructs to multiple locals, we have even more complicated structure.756	/// Luckly, every destruct is not interleaved with each other, so here we can have full list...757	/// 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 elements758	/// for each destruct starting from `first_destruct_local`759	/// ~~destructs: Vec<usize>,~~760	///761	/// => two of those fields were merged, as there is currently no per-destruct tracking of closures.762	/// For each spec in order: `(references_count, destruct_ids_count)`.763	/// `references_count` tells us how many entries of `referenced` belong764	/// to this spec; `destruct_ids_count` tells us how many `LocalIds` it765	/// binds.766	spec_shapes: Vec<(usize, usize)>,767	/// This is not a related doccomment, just a continuation of docs for previous fields.768	/// Having769	/// ```jsonnet770	/// local771	///     [a, b, c] = [d, e, f],772	///     [d, e, f] = [a, b, c, h],773	///     h = 1,774	/// ;775	/// ```776	///777	/// We have total of 7 locals778	/// First local here is `a` => `first_destruct_local` = `a`779	/// 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`780	/// [d, e, f] = [a, b, c, h], => `referenced += [a, b, c, h]`, `closures += 4`, `destructs += 3` (Note that this destruct will fail at runtime,781	///                                                                                               this thing should not care about that, it only captures what the value are referencing)782	/// h = 1 => referenced += [], closures += 0, destructs += 1783	/// And the result is784	///785	/// ```rust,ignore786	/// Closures {787	///     referenced: vec![d, e, f, a, b, c, h]788	///     spec_shapes: vec![(3, 3), (4, 3), (0, 1)],789	///     first_destruct_label: a,790	/// }791	/// ```792	///793	/// Reconstruction of that:794	///795	/// We know that we start with a796	/// We get the first number from destructs: `destructs.shift() == 3` => `destructs = [3, 1]`797	/// 3 elements counting from a => [a, b, c]798	/// Then we take first number from closures: `closures.shift() == 3` => `closures = [4, 0]`799	/// Then we take 3 items from referenced: `referenced.shift()x3 == d, e, f` => `referenced = [a, b, c, h]`800	///801	/// Thus we have [a, b, c] = [d, e, f]802	first_in_frame: LocalId,803}804805struct Closure<'a> {806	references: &'a [LocalId],807	ids: std::ops::Range<u32>,808}809810impl Closures {811	fn push_spec(&mut self, destruct_ids_count: usize, refs: &[LocalId]) {812		self.referenced.extend_from_slice(refs);813		self.spec_shapes.push((refs.len(), destruct_ids_count));814	}815816	fn iter_specs(&self) -> impl Iterator<Item = Closure<'_>> {817		let mut refs = self.referenced.as_slice();818		let mut next_id = self.first_in_frame.0;819		self.spec_shapes.iter().map(move |(refs_len, dest_count)| {820			let (this_refs, rest) = refs.split_at(*refs_len);821			refs = rest;822			let start = next_id;823			next_id += arridx(*dest_count);824			Closure {825				references: this_refs,826				ids: start..next_id,827			}828		})829	}830}831832#[derive(Debug, Clone, Copy, PartialEq, Eq)]833pub enum DiagLevel {834	Error,835	Warning,836}837838#[derive(Debug, Clone, Acyclic)]839pub struct Diagnostic {840	pub level: DiagLevel,841	pub message: String,842	pub span: Option<Span>,843}844845struct DefiningClosure {846	first_local: LocalId,847	n_locals: u16,848}849850impl DefiningClosure {851	fn resolve(&self, target: LocalId) -> Option<LocalSlot> {852		let end = self.first_local.0 + u32::from(self.n_locals);853		if target.0 >= self.first_local.0 && target.0 < end {854			Some(LocalSlot(855				u16::try_from(target.0 - self.first_local.0).expect("local slots overflow"),856			))857		} else {858			None859		}860	}861	fn define_local(&mut self, local: LocalId) -> LocalSlot {862		let slot = self.n_locals;863		let id = self.first_local.0 + u32::from(slot);864		debug_assert_eq!(local.0, id);865		self.n_locals = self.n_locals.checked_add(1).expect("local slots overflow");866		LocalSlot(slot)867	}868}869870/// Per-closure capture computation state.871struct ClosureFrame {872	/// Closure may allocate locals873	defining: Option<DefiningClosure>,874	/// `LocalId` => capture index875	captures: FxHashMap<LocalId, CaptureSlot>,876	/// Capture sources in insertion order; consumed by `pop_closure_frame`.877	capture_sources: Vec<LSlot>,878}879880#[allow(clippy::struct_excessive_bools)]881pub struct AnalysisStack {882	local_defs: Vec<LocalDefinition>,883	/// Shadowing isn't used in jsonnet much, 2 because `SmallVec` allows to store 2 ptr-sized without overhead.884	/// TODO: Add test for this assumption (sizeof(SmallVec<[usize; 1]>) == sizeof(SmallVec<[usize; 2]>))885	local_by_name: FxHashMap<IStr, SmallVec<[LocalId; 2]>>,886887	/// Depth of the current locals frame.888	depth: u32,889	/// Last depth, at which object has appeared. `u32::MAX` = not appeared at all890	last_object_depth: u32,891	/// First depth, at which object has appeared. `u32::MAX` = not appeared at all892	/// $ refers to this object.893	first_object_depth: u32,894895	/// `LocalId` bound to the innermost object's `this`896	this_local: Option<LocalId>,897	/// Outermost object `this`, aka `$`898	dollar_alias: Option<LocalId>,899	/// True iff `self` has been referenced in the current object immediate members (not nested children).900	cur_self_used: bool,901	/// True iff `super` has been referenced in the current object immediate members.902	cur_super_used: bool,903	/// True iff `$` has been referenced anywhere since the outermost object's scope was entered.904	dollar_used: bool,905906	/// Stack of closure frames (innermost on top).907	closure_stack: Vec<ClosureFrame>,908909	diagnostics: Vec<Diagnostic>,910	/// Whenever analysis would be broken due to static analysis error.911	errored: bool,912}913914#[must_use]915struct ClosureOnStack {916	bomb: DropBomb,917}918919impl AnalysisStack {920	pub fn new() -> Self {921		Self {922			local_defs: Vec::new(),923			local_by_name: FxHashMap::default(),924			depth: 0,925			last_object_depth: u32::MAX,926			first_object_depth: u32::MAX,927			this_local: None,928			dollar_alias: None,929			cur_self_used: false,930			cur_super_used: false,931			dollar_used: false,932			closure_stack: Vec::new(),933			diagnostics: Vec::new(),934			errored: false,935		}936	}937938	fn push_root_closure(&mut self, externals: u16) -> ClosureOnStack {939		assert!(940			self.closure_stack.is_empty(),941			"root is only possible with empty stack"942		);943944		self.closure_stack.push(ClosureFrame {945			defining: Some(DefiningClosure {946				first_local: LocalId(0),947				n_locals: externals,948			}),949			captures: FxHashMap::default(),950			capture_sources: Vec::new(),951		});952953		ClosureOnStack {954			bomb: DropBomb::new("root closure"),955		}956	}957958	fn push_closure_a(&mut self, first_local: LocalId) -> ClosureOnStack {959		self.closure_stack.push(ClosureFrame {960			defining: Some(DefiningClosure {961				first_local,962				n_locals: 0,963			}),964			captures: FxHashMap::default(),965			capture_sources: Vec::new(),966		});967		ClosureOnStack {968			bomb: DropBomb::new("closure with locals"),969		}970	}971972	#[inline]973	fn in_using_closure<T>(974		&mut self,975		inner: impl FnOnce(&mut AnalysisStack) -> T,976	) -> (ClosureShape, T) {977		fn push_closure_b(stack: &mut AnalysisStack) -> ClosureOnStack {978			stack.closure_stack.push(ClosureFrame {979				defining: None,980				captures: FxHashMap::default(),981				capture_sources: Vec::new(),982			});983			ClosureOnStack {984				bomb: DropBomb::new("closure with locals"),985			}986		}987		let closure = push_closure_b(self);988		let v = inner(self);989		let shape = self.pop_closure(closure);990		(shape, v)991	}992993	fn pop_closure(&mut self, mut closure: ClosureOnStack) -> ClosureShape {994		closure.bomb.defuse();995		let frame = self.closure_stack.pop().expect("closure frame");996		ClosureShape {997			captures: frame.capture_sources.into_boxed_slice(),998			n_locals: frame.defining.map(|d| d.n_locals).unwrap_or_default(),999		}1000	}10011002	/// Resolve a `LocalId` reference to an `LSlot` against the innermost1003	/// closure frame. May insert capture entries up the closure stack as1004	/// needed.1005	fn resolve_to_slot(&mut self, target: LocalId) -> LSlot {1006		let top = self.closure_stack.len();1007		debug_assert!(top > 0, "resolve_to_slot called with no closure frame");1008		Self::resolve_at(&mut self.closure_stack, top - 1, target)1009	}10101011	fn resolve_at(stack: &mut [ClosureFrame], idx: usize, target: LocalId) -> LSlot {1012		if let Some(def) = &stack[idx].defining {1013			if let Some(resolved) = def.resolve(target) {1014				return LSlot::Local(resolved);1015			}1016		} else {1017			// A sibling letrec slot must never be packed as a capture, or1018			// it would read an empty `OnceCell`.1019			for j in (0..idx).rev() {1020				if let Some(def) = &stack[j].defining {1021					if let Some(resolved) = def.resolve(target) {1022						return LSlot::Local(resolved);1023					}1024					break;1025				}1026			}1027		}1028		if let Some(&cap_idx) = stack[idx].captures.get(&target) {1029			return LSlot::Capture(cap_idx);1030		}1031		debug_assert!(idx > 0, "no enclosing closure frame for target {target:?}");1032		let parent_slot = Self::resolve_at(stack, idx - 1, target);1033		let frame = &mut stack[idx];1034		let cap_idx = CaptureSlot(1035			frame1036				.capture_sources1037				.len()1038				.try_into()1039				.expect("frame has more than u16::MAX captures"),1040		);1041		frame.capture_sources.push(parent_slot);1042		frame.captures.insert(target, cap_idx);1043		LSlot::Capture(cap_idx)1044	}10451046	fn next_local_id(&self) -> LocalId {1047		LocalId(arridx(self.local_defs.len()))1048	}10491050	fn report_error(&mut self, msg: impl Into<String>, span: Option<Span>) {1051		self.errored = true;1052		self.diagnostics.push(Diagnostic {1053			level: DiagLevel::Error,1054			message: msg.into(),1055			span,1056		});1057	}1058	fn report_warning(&mut self, msg: impl Into<String>, span: Option<Span>) {1059		self.diagnostics.push(Diagnostic {1060			level: DiagLevel::Warning,1061			message: msg.into(),1062			span,1063		});1064	}10651066	fn use_local(&mut self, name: &IStr, span: Span, taint: &mut AnalysisResult) -> Option<LSlot> {1067		let Some(ids) = self.local_by_name.get(name) else {1068			let names = suggest_names(name, self.local_by_name.keys());1069			self.report_error(1070				format!("undefined local: {name}{}", format_found(&names, "local")),1071				Some(span),1072			);1073			return None;1074		};1075		let id = *ids.last().expect("empty stacks should be removed");1076		let depth = self.depth;1077		let def = &mut self.local_defs[id.idx()];1078		def.use_at(depth);1079		taint.depend_on_local(def.defined_at_depth);1080		if def.analyzed {1081			taint.taint_by(def.analysis);1082		} else {1083			def.scratch_referenced = true;1084		}1085		Some(self.resolve_to_slot(id))1086	}10871088	/// Assign name to the value provided externally, e.g `std`.1089	pub fn define_external_local(&mut self, name: IStr, id: LocalId) {1090		assert!(1091			self.local_defs.iter().all(|d| d.analyzed),1092			"external locals must be defined before the root expression is analysed"1093		);1094		assert_eq!(1095			id,1096			self.next_local_id(),1097			"external local id mismatch for {name} (externals must be defined in allocation order)"1098		);1099		self.local_defs.push(LocalDefinition {1100			name: name.clone(),1101			span: None,1102			defined_at_depth: 0,1103			used_at_depth: u32::MAX,1104			used_by_sibling: false,1105			analysis: AnalysisResult::default(),1106			analyzed: true,1107			scratch_referenced: false,1108		});1109		self.local_by_name.entry(name).or_default().push(id);1110	}11111112	fn defining_closure_mut(&mut self) -> &mut DefiningClosure {1113		self.closure_stack1114			.iter_mut()1115			.rev()1116			.find_map(|c| c.defining.as_mut())1117			.expect("no enclosing defining closure frame")1118	}1119	fn defining_closure(&self) -> &DefiningClosure {1120		self.closure_stack1121			.iter()1122			.rev()1123			.find_map(|c| c.defining.as_ref())1124			.expect("no enclosing defining closure frame")1125	}1126}11271128impl Default for AnalysisStack {1129	fn default() -> Self {1130		Self::new()1131	}1132}11331134impl AnalysisStack {1135	fn top_defining_local(&self) -> LocalId {1136		self.defining_closure().first_local1137	}11381139	/// Merge `used`'s analysis into `user`'s analysis and record that `user`1140	/// transitively depends on `used` (same-frame sibling reference).1141	/// Returns `true` if `user`'s analysis changed.1142	fn propagate_analysis(&mut self, user: LocalId, used: LocalId) -> bool {1143		let (used_analysis, used_defined_at_depth) = {1144			let u = &self.local_defs[used.idx()];1145			(u.analysis, u.defined_at_depth)1146		};1147		let user_def = &mut self.local_defs[user.idx()];1148		let before_obj = user_def.analysis.object_dependent_depth;1149		let before_loc = user_def.analysis.local_dependent_depth;1150		user_def.analysis.taint_by(used_analysis);1151		user_def.analysis.depend_on_local(used_defined_at_depth);1152		before_obj != user_def.analysis.object_dependent_depth1153			|| before_loc != user_def.analysis.local_dependent_depth1154	}1155}11561157mod names {1158	use crate::names;11591160	names! {1161		this: "this",1162	}1163}11641165// Object scope helpers1166impl AnalysisStack {1167	#[inline]1168	fn in_object_scope<T>(1169		&mut self,1170		inner: impl FnOnce(&mut AnalysisStack) -> T,1171	) -> (ObjectUsage, ClosureShape, T) {1172		fn enter_object_scope(stack: &mut AnalysisStack) -> ObjectScope {1173			let is_outermost = stack.first_object_depth == u32::MAX;1174			let this_id = stack.next_local_id();1175			let closure = stack.push_closure_a(this_id);1176			let pushed = stack.push_pseudo_local(names::this());1177			debug_assert_eq!(pushed, this_id, "this pseudo-local id");1178			let scope = ObjectScope {1179				this_id,1180				is_outermost,1181				prev_this_local: stack.this_local,1182				prev_dollar_alias: stack.dollar_alias,1183				prev_cur_self_used: stack.cur_self_used,1184				prev_cur_super_used: stack.cur_super_used,1185				prev_dollar_used: is_outermost.then_some(stack.dollar_used),1186				prev_last_object: stack.last_object_depth,1187				prev_first_object: stack.first_object_depth,1188				closure,1189			};11901191			stack.this_local = Some(scope.this_id);1192			if is_outermost {1193				stack.dollar_alias = Some(scope.this_id);1194				stack.first_object_depth = stack.depth;1195				stack.dollar_used = false;1196			}1197			stack.last_object_depth = stack.depth;1198			stack.cur_self_used = false;1199			stack.cur_super_used = false;1200			scope1201		}12021203		fn leave_object_scope(1204			stack: &mut AnalysisStack,1205			scope: ObjectScope,1206		) -> (ObjectUsage, ClosureShape) {1207			let ObjectScope {1208				this_id,1209				is_outermost,1210				prev_this_local,1211				prev_dollar_alias,1212				prev_cur_self_used,1213				prev_cur_super_used,1214				prev_dollar_used,1215				prev_last_object,1216				prev_first_object,1217				closure,1218			} = scope;1219			let _ = stack.local_defs.pop().expect("this pseudo-local exists");1220			debug_assert_eq!(stack.local_defs.len(), this_id.0 as usize);12211222			let set_dollar = is_outermost && stack.dollar_used;1223			let usage = ObjectUsage {1224				this_used: stack.cur_self_used || stack.cur_super_used || set_dollar,1225				uses_super: stack.cur_super_used,1226				set_dollar,1227			};12281229			stack.this_local = prev_this_local;1230			stack.dollar_alias = prev_dollar_alias;1231			stack.cur_self_used = prev_cur_self_used;1232			stack.cur_super_used = prev_cur_super_used;1233			if let Some(prev) = prev_dollar_used {1234				stack.dollar_used = prev;1235			}1236			stack.last_object_depth = prev_last_object;1237			stack.first_object_depth = prev_first_object;12381239			let frame_shape = stack.pop_closure(closure);1240			(usage, frame_shape)1241		}1242		let scope = enter_object_scope(self);1243		let v = inner(self);1244		let (usage, shape) = leave_object_scope(self, scope);1245		(usage, shape, v)1246	}12471248	fn push_pseudo_local(&mut self, name: IStr) -> LocalId {1249		let id = self.next_local_id();1250		self.local_defs.push(LocalDefinition {1251			name,1252			span: None,1253			defined_at_depth: self.depth,1254			used_at_depth: u32::MAX,1255			used_by_sibling: false,1256			analysis: AnalysisResult::default(),1257			analyzed: true,1258			scratch_referenced: false,1259		});1260		{1261			let def = self.defining_closure_mut();1262			let _ = def.define_local(id);1263		}1264		id1265	}12661267	fn use_this(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1268		let id = self.this_local?;1269		self.cur_self_used = true;1270		self.use_pseudo_local(id, taint);1271		Some(self.resolve_to_slot(id))1272	}12731274	fn use_super(&mut self, taint: &mut AnalysisResult) -> Option<()> {1275		let id = self.this_local?;1276		self.cur_super_used = true;1277		self.use_pseudo_local(id, taint);1278		Some(())1279	}12801281	fn use_dollar(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1282		let id = self.dollar_alias?;1283		self.dollar_used = true;1284		self.use_pseudo_local(id, taint);1285		Some(self.resolve_to_slot(id))1286	}12871288	// TODO: Dedicated type for object references instead of "pseudo local" BS, idk1289	fn use_pseudo_local(&mut self, id: LocalId, taint: &mut AnalysisResult) {1290		let depth = self.depth;1291		let def = &mut self.local_defs[id.idx()];1292		def.use_at(depth);1293		taint.depend_on_local(def.defined_at_depth);1294		taint.depend_on_object(def.defined_at_depth);1295	}1296}12971298#[must_use]1299struct ObjectScope {1300	this_id: LocalId,1301	is_outermost: bool,1302	prev_this_local: Option<LocalId>,1303	prev_dollar_alias: Option<LocalId>,1304	prev_cur_self_used: bool,1305	prev_cur_super_used: bool,1306	prev_dollar_used: Option<bool>,1307	prev_last_object: u32,1308	prev_first_object: u32,1309	closure: ClosureOnStack,1310}13111312struct ObjectUsage {1313	this_used: bool,1314	uses_super: bool,1315	set_dollar: bool,1316}13171318fn analyze_assert(1319	stmt: &AssertStmt,1320	stack: &mut AnalysisStack,1321	taint: &mut AnalysisResult,1322) -> LAssertStmt {1323	let cond = analyze(&stmt.assertion.value, stack, taint);1324	let message = stmt.message.as_ref().map(|m| analyze(m, stack, taint));1325	LAssertStmt {1326		cond: Spanned::new(cond, stmt.assertion.span.clone()),1327		message,1328	}1329}13301331#[allow(clippy::too_many_lines)]1332pub fn analyze_named(1333	name: IStr,1334	expr: &Expr,1335	stack: &mut AnalysisStack,1336	taint: &mut AnalysisResult,1337) -> LExpr {1338	if let Expr::Function(span, params, body) = expr {1339		return analyze_function(Some(name), &span, &params, body, stack, taint);1340	}1341	analyze(expr, stack, taint)1342}1343#[allow(clippy::too_many_lines)]1344pub fn analyze(expr: &Expr, stack: &mut AnalysisStack, taint: &mut AnalysisResult) -> LExpr {1345	match expr {1346		Expr::Identity(span, l) => match l {1347			IdentityKind::This => stack.use_this(taint).map_or_else(1348				|| {1349					stack.report_error("`self` used outside of object", Some(span.clone()));1350					LExpr::BadLocal("self")1351				},1352				LExpr::Slot,1353			),1354			IdentityKind::Super => {1355				if stack.use_super(taint).is_some() {1356					LExpr::Super1357				} else {1358					stack.report_error("`super` used outside of object", Some(span.clone()));1359					LExpr::BadLocal("super")1360				}1361			}1362			IdentityKind::Dollar => stack.use_dollar(taint).map_or_else(1363				|| {1364					stack.report_error("`$` used outside of object", Some(span.clone()));1365					LExpr::BadLocal("$")1366				},1367				LExpr::Slot,1368			),1369		},1370		Expr::Trivial(tv) => LExpr::Trivial(tv.clone()),1371		Expr::Var(v) => stack1372			.use_local(&v.value, v.span.clone(), taint)1373			.map_or_else(|| LExpr::BadLocal("ref"), LExpr::Slot),1374		Expr::Arr(a) => {1375			if a.iter().all(|i| matches!(i, Expr::Trivial(_))) {1376				let trivials: Vec<_> = a1377					.iter()1378					.map(|i| match i {1379						Expr::Trivial(tv) => tv.clone(),1380						_ => unreachable!("checked above"),1381					})1382					.collect();1383				return LExpr::ArrConst(Rc::new(trivials));1384			}1385			let (shape, items) = stack.in_using_closure(|stack| {1386				a.iter()1387					.map(|v| analyze(v, stack, taint))1388					.collect::<Vec<_>>()1389			});1390			LExpr::Arr {1391				shape,1392				items: Rc::new(items),1393			}1394		}1395		Expr::ArrComp(inner, comp) => analyze_arr_comp(inner, comp, stack, taint),1396		Expr::Obj(obj) => LExpr::Obj(analyze_obj_body(obj, stack, taint)),1397		Expr::ObjExtend(base, obj) => LExpr::ObjExtend(1398			Box::new(analyze(base, stack, taint)),1399			analyze_obj_body(obj, stack, taint),1400		),1401		Expr::UnaryOp(op, value) => LExpr::UnaryOp(*op, Box::new(analyze(value, stack, taint))),1402		Expr::BinaryOp(op) => {1403			let BinaryOp {1404				lhs,1405				op: optype,1406				rhs,1407			} = &**op;1408			LExpr::BinaryOp {1409				lhs: Box::new(analyze(lhs, stack, taint)),1410				op: *optype,1411				rhs: Box::new(analyze(rhs, stack, taint)),1412			}1413		}1414		Expr::AssertExpr(assert) => {1415			let AssertExpr { assert, rest } = &**assert;1416			let assert = Rc::new(analyze_assert(assert, stack, taint));1417			let rest = Box::new(analyze(rest, stack, taint));1418			LExpr::AssertExpr { assert, rest }1419		}1420		Expr::LocalExpr(binds, body) => analyze_local_expr(binds, body, stack, taint),1421		Expr::Import(kind, path_expr) => {1422			let Expr::Trivial(TrivialVal::Str(path)) = &**path_expr else {1423				stack.report_error(1424					"import path must be a string literal",1425					Some(kind.span.clone()),1426				);1427				return LExpr::BadLocal("bad import");1428			};1429			LExpr::Import {1430				kind: kind.clone(),1431				kind_span: kind.span.clone(),1432				path: path.clone(),1433			}1434		}1435		Expr::ErrorStmt(span, inner) => {1436			LExpr::Error(span.clone(), Box::new(analyze(inner, stack, taint)))1437		}1438		Expr::Apply(applicable, args, tailstrict) => {1439			let app = analyze(applicable, stack, taint);1440			let ArgsDesc {1441				unnamed,1442				names,1443				values,1444			} = &args.value;1445			let unnamed_l = unnamed1446				.iter()1447				.map(|a| Rc::new(analyze(a, stack, taint)))1448				.collect();1449			let values_l = values1450				.iter()1451				.map(|a| Rc::new(analyze(a, stack, taint)))1452				.collect();1453			LExpr::Apply {1454				applicable: Box::new(app),1455				args: Spanned::new(1456					LArgsDesc {1457						unnamed: unnamed_l,1458						names: names.clone(),1459						values: values_l,1460					},1461					args.span.clone(),1462				),1463				tailstrict: *tailstrict,1464			}1465		}1466		Expr::Index { indexable, parts } => {1467			let idx = analyze(indexable, stack, taint);1468			let parts_l = parts1469				.iter()1470				.map(|p| {1471					let value = analyze(&p.value, stack, taint);1472					LIndexPart {1473						span: p.span.clone(),1474						value,1475						#[cfg(feature = "exp-null-coaelse")]1476						null_coaelse: p.null_coaelse,1477					}1478				})1479				.collect();1480			LExpr::Index {1481				indexable: Box::new(idx),1482				parts: parts_l,1483			}1484		}1485		Expr::Function(span, params, body) => {1486			analyze_function(None, span, params, body, stack, taint)1487		}1488		Expr::IfElse(ifelse) => {1489			let IfElse {1490				cond,1491				cond_then,1492				cond_else,1493			} = &**ifelse;1494			let cond_l = analyze(&cond.cond, stack, taint);1495			let then_l = analyze(cond_then, stack, taint);1496			let else_l = cond_else1497				.as_ref()1498				.map(|e| Box::new(analyze(e, stack, taint)));1499			LExpr::IfElse {1500				cond: Box::new(cond_l),1501				cond_then: Box::new(then_l),1502				cond_else: else_l,1503			}1504		}1505		Expr::Slice(slice) => {1506			let Slice {1507				value,1508				slice: SliceDesc { start, end, step },1509			} = &**slice;1510			let value_l = analyze(value, stack, taint);1511			let start_l = start.as_ref().map(|e| analyze(&e.value, stack, taint));1512			let end_l = end.as_ref().map(|e| analyze(&e.value, stack, taint));1513			let step_l = step.as_ref().map(|e| analyze(&e.value, stack, taint));1514			LExpr::Slice(Box::new(LSliceExpr {1515				value: value_l,1516				start: start_l,1517				end: end_l,1518				step: step_l,1519			}))1520		}1521	}1522}15231524fn analyze_local_expr(1525	binds: &[BindSpec],1526	body: &Expr,1527	stack: &mut AnalysisStack,1528	taint: &mut AnalysisResult,1529) -> LExpr {1530	if binds.is_empty() {1531		return analyze(body, stack, taint);1532	}1533	let frame_start = stack.next_local_id();1534	let closure = stack.push_closure_a(frame_start);1535	let (l_binds, body_expr) = process_local_frame(binds, stack, taint, |stack, taint| {1536		analyze(body, stack, taint)1537	});1538	let frame_shape = stack.pop_closure(closure);1539	LExpr::LocalExpr(Box::new(LLocalExpr {1540		frame_shape,1541		binds: l_binds,1542		body: body_expr,1543	}))1544}15451546fn analyze_bind_value(1547	bind: &BindSpec,1548	stack: &mut AnalysisStack,1549	taint: &mut AnalysisResult,1550) -> LExpr {1551	match bind {1552		BindSpec::Field {1553			value: Expr::Function(span, params, value),1554			into: Destruct::Full(name),1555		} => analyze_function(Some(name.value.clone()), &span, params, value, stack, taint),1556		BindSpec::Field { value, .. } => analyze(value, stack, taint),1557		BindSpec::Function {1558			params,1559			value,1560			name,1561		} => analyze_function(1562			Some(name.value.clone()),1563			&name.span,1564			params,1565			value,1566			stack,1567			taint,1568		),1569	}1570}15711572fn process_local_frame<R>(1573	binds: &[BindSpec],1574	stack: &mut AnalysisStack,1575	taint: &mut AnalysisResult,1576	body_fn: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1577) -> (Vec<LBind>, R) {1578	let mut alloc = FrameAlloc::new(stack);15791580	let mut destructs: Vec<Option<LDestruct>> = Vec::with_capacity(binds.len());1581	for bind in binds {1582		destructs.push(alloc.alloc_bind(bind));1583	}1584	let mut pending = alloc.finish();15851586	let mut l_binds: Vec<LBind> = Vec::with_capacity(binds.len());1587	for (bind, destruct) in binds.iter().zip(destructs) {1588		let mut value_taint = AnalysisResult::default();1589		let (value_shape, value) = pending1590			.stack1591			.in_using_closure(|stack| analyze_bind_value(bind, stack, &mut value_taint));1592		taint.taint_by(value_taint);1593		if let Some(destruct) = destruct {1594			pending.record_spec_init(&destruct, value_taint);1595			l_binds.push(LBind {1596				destruct,1597				value_shape,1598				value: Rc::new(value),1599			});1600		} else {1601			pending.closures.push_spec(0, &[]);1602		}1603	}16041605	let body_frame = pending.finish();1606	let result = body_fn(body_frame.stack, taint);1607	body_frame.finish();16081609	(l_binds, result)1610}16111612fn analyze_function(1613	name: Option<IStr>,1614	span: &Span,1615	params: &ExprParams,1616	body: &Expr,1617	stack: &mut AnalysisStack,1618	taint: &mut AnalysisResult,1619) -> LExpr {1620	let mut alloc = FrameAlloc::new(stack);1621	let closure = alloc.push_locals_closure();16221623	let mut param_destructs: Vec<Option<LDestruct>> = Vec::with_capacity(params.exprs.len());1624	for p in &params.exprs {1625		param_destructs.push(alloc.alloc_destruct(&p.destruct));1626	}16271628	let mut pending = alloc.finish();16291630	let mut l_params: Vec<LParam> = Vec::with_capacity(params.exprs.len());1631	for (p, destruct) in params.exprs.iter().zip(param_destructs) {1632		let mut value_taint = AnalysisResult::default();1633		let default = p.default.as_ref().map_or_else(1634			|| None,1635			|d| {1636				Some(1637					pending1638						.stack1639						.in_using_closure(|stack| Rc::new(analyze(d, stack, &mut value_taint))),1640				)1641			},1642		);1643		taint.taint_by(value_taint);1644		if let Some(destruct) = destruct {1645			let name = match &p.destruct {1646				Destruct::Full(n) => Some(n.value.clone()),1647				#[cfg(feature = "exp-destruct")]1648				_ => None,1649			};1650			pending.record_spec_init(&destruct, value_taint);1651			l_params.push(LParam {1652				name,1653				destruct,1654				default,1655			});1656		} else {1657			pending.closures.push_spec(0, &[]);1658		}1659	}16601661	let body_frame = pending.finish();1662	let body_expr = analyze(body, body_frame.stack, taint);1663	body_frame.finish();1664	let body_shape = stack.pop_closure(closure);16651666	// function(x) x is an identity function1667	if l_params.len() == 1 && l_params[0].default.is_none() {1668		#[allow(irrefutable_let_patterns, reason = "refutable with exp-destruct")]1669		if let LDestruct::Full(param_slot) = &l_params[0].destruct1670			&& let LExpr::Slot(LSlot::Local(s)) = &body_expr1671			&& s == param_slot1672		{1673			stack.report_warning(1674				"do not define identity functions manually, use std.id instead",1675				Some(span.clone()),1676			);1677			return LExpr::IdentityFunction {};1678		}1679	}16801681	LExpr::Function(Rc::new(LFunction {1682		name,1683		params: l_params,1684		signature: params.signature.clone(),1685		body_shape,1686		body: Rc::new(body_expr),1687	}))1688}16891690fn analyze_obj_body(1691	obj: &ObjBody,1692	stack: &mut AnalysisStack,1693	taint: &mut AnalysisResult,1694) -> LObjBody {1695	match obj {1696		ObjBody::MemberList(members) => {1697			LObjBody::MemberList(analyze_obj_members(members, stack, taint))1698		}1699		ObjBody::ObjComp(comp) => LObjBody::ObjComp(Box::new(analyze_obj_comp(comp, stack, taint))),1700	}1701}17021703fn analyze_obj_members(1704	members: &ObjMembers,1705	stack: &mut AnalysisStack,1706	taint: &mut AnalysisResult,1707) -> LObjMembers {1708	let ObjMembers {1709		locals,1710		asserts,1711		fields,1712	} = members;17131714	// Names are analyzed in enclosing scope, they can't depend on locals or self/super1715	let field_names: Vec<LFieldName> = fields1716		.iter()1717		.map(|f| match &f.name.value {1718			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1719			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1720		})1721		.collect();17221723	let (usage, frame_shape, (l_binds, (l_asserts_opt, l_fields))) =1724		stack.in_object_scope(|stack| {1725			process_local_frame(locals, stack, taint, |stack, taint| {1726				let l_asserts_opt = if asserts.is_empty() {1727					None1728				} else {1729					let (shape, l_asserts) = stack.in_using_closure(|stack| {1730						let mut l_asserts = Vec::with_capacity(asserts.len());1731						for a in asserts {1732							let mut assert_taint = AnalysisResult::default();1733							l_asserts.push(analyze_assert(a, stack, &mut assert_taint));1734							taint.taint_by(assert_taint);1735						}1736						l_asserts1737					});1738					Some(Rc::new(LObjAsserts {1739						shape,1740						asserts: l_asserts,1741					}))1742				};1743				let mut l_fields = Vec::with_capacity(fields.len());1744				for (f, name) in fields.iter().zip(field_names) {1745					let value = stack.in_using_closure(|stack| {1746						if let Some(params) = &f.params {1747							analyze_function(1748								name.function_name(),1749								&f.name.span,1750								params,1751								&f.value,1752								stack,1753								taint,1754							)1755						} else {1756							analyze(&f.value, stack, taint)1757						}1758					});1759					l_fields.push(LFieldMember {1760						name,1761						plus: f.plus,1762						visibility: f.visibility,1763						value: Rc::new(value),1764					});1765				}1766				(l_asserts_opt, l_fields)1767			})1768		});1769	// `this` was allocated as the first local of the object's frame,1770	// so its slot is 0 within that frame.1771	let this_slot = usage.this_used.then_some(LocalSlot(0));1772	LObjMembers {1773		frame_shape,1774		this: this_slot,1775		set_dollar: usage.set_dollar,1776		uses_super: usage.uses_super,1777		locals: Rc::new(l_binds),1778		asserts: l_asserts_opt,1779		fields: l_fields,1780	}1781}17821783fn analyze_obj_comp(1784	comp: &ObjComp,1785	stack: &mut AnalysisStack,1786	taint: &mut AnalysisResult,1787) -> LObjComp {1788	let res = analyze_comp_specs(&comp.compspecs, stack, taint, |stack, taint| {1789		let field_name = match &comp.field.name.value {1790			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1791			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1792		};17931794		let (usage, frame_shape, body) = stack.in_object_scope(|stack| {1795			process_local_frame(&comp.locals, stack, taint, |stack, taint| {1796				let value = stack.in_using_closure(|stack| {1797					if let Some(params) = &comp.field.params {1798						analyze_function(1799							None,1800							&comp.field.name.span,1801							params,1802							&comp.field.value,1803							stack,1804							taint,1805						)1806					} else {1807						analyze(&comp.field.value, stack, taint)1808					}1809				});1810				LFieldMember {1811					name: field_name,1812					plus: comp.field.plus,1813					visibility: comp.field.visibility,1814					value: Rc::new(value),1815				}1816			})1817		});1818		(usage, frame_shape, body)1819	});1820	let (usage, frame_shape, (locals, field)) = res.inner;1821	let this_slot = usage.this_used.then_some(LocalSlot(0));1822	LObjComp {1823		frame_shape: Rc::new(frame_shape),1824		this: this_slot,1825		set_dollar: usage.set_dollar,1826		uses_super: usage.uses_super,1827		locals: Rc::new(locals),1828		field,1829		compspecs: res.compspecs,1830	}1831}18321833fn analyze_arr_comp(1834	inner: &Expr,1835	specs: &[CompSpec],1836	stack: &mut AnalysisStack,1837	taint: &mut AnalysisResult,1838) -> LExpr {1839	let res = analyze_comp_specs(specs, stack, taint, |stack, taint| {1840		stack.in_using_closure(|stack| analyze(inner, stack, taint))1841	});1842	let (value_shape, value) = res.inner;1843	LExpr::ArrComp(Box::new(LArrComp {1844		value_shape,1845		value: Rc::new(value),1846		compspecs: res.compspecs,1847	}))1848}18491850fn analyze_comp_specs<R>(1851	specs: &[CompSpec],1852	stack: &mut AnalysisStack,1853	taint: &mut AnalysisResult,1854	inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1855) -> CompSpecResult<R> {1856	fn go<R>(1857		idx: usize,1858		specs: &[CompSpec],1859		outer_depth: u32,1860		stack: &mut AnalysisStack,1861		taint: &mut AnalysisResult,1862		inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1863	) -> (R, Vec<LCompSpec>) {1864		if idx >= specs.len() {1865			return (inside(stack, taint), Vec::new());1866		}1867		match &specs[idx] {1868			CompSpec::IfSpec(IfSpecData { cond, .. }) => {1869				let cond_l = analyze(cond, stack, taint);1870				let (r, mut rest) = go(idx + 1, specs, outer_depth, stack, taint, inside);1871				rest.insert(0, LCompSpec::If(cond_l));1872				(r, rest)1873			}1874			CompSpec::ForSpec(ForSpecData { destruct, over }) => {1875				let mut over_taint = AnalysisResult::default();1876				let over_l = analyze(over, stack, &mut over_taint);1877				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1878				taint.taint_by(over_taint);18791880				let mut alloc = FrameAlloc::new(stack);1881				let closure = alloc.push_locals_closure();1882				let Some(l_destruct) = alloc.alloc_destruct(destruct) else {1883					stack.pop_closure(closure);1884					return go(idx + 1, specs, outer_depth, stack, taint, inside);1885				};1886				let mut pending = alloc.finish();18871888				let var_analysis = AnalysisResult::default();1889				pending.record_spec_init(&l_destruct, var_analysis);18901891				let body_frame = pending.finish();1892				let (r, mut rest) =1893					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);1894				body_frame.finish();1895				let frame_shape = stack.pop_closure(closure);18961897				rest.insert(1898					0,1899					LCompSpec::For {1900						frame_shape,1901						destruct: l_destruct,1902						over: over_l,1903						loop_invariant,1904					},1905				);1906				(r, rest)1907			}1908			#[cfg(feature = "exp-object-iteration")]1909			CompSpec::ForObjSpec(data) => {1910				let mut over_taint = AnalysisResult::default();1911				let over_l = analyze(&data.over, stack, &mut over_taint);1912				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1913				taint.taint_by(over_taint);19141915				let mut alloc = FrameAlloc::new(stack);1916				let closure = alloc.push_locals_closure();1917				let Some((_, key_slot)) = alloc.define_local(data.key.clone(), None) else {1918					stack.pop_closure(closure);1919					return go(idx + 1, specs, outer_depth, stack, taint, inside);1920				};1921				let Some(l_value) = alloc.alloc_destruct(&data.value) else {1922					stack.pop_closure(closure);1923					return go(idx + 1, specs, outer_depth, stack, taint, inside);1924				};1925				let mut pending = alloc.finish();19261927				let var_analysis = AnalysisResult::default();1928				pending.record_spec_init(&LDestruct::Full(key_slot), var_analysis);1929				pending.record_spec_init(&l_value, var_analysis);19301931				let body_frame = pending.finish();1932				let (r, mut rest) =1933					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);1934				body_frame.finish();1935				let frame_shape = stack.pop_closure(closure);19361937				rest.insert(1938					0,1939					LCompSpec::ForObj {1940						frame_shape,1941						key: key_slot,1942						visibility: data.visibility,1943						value: l_value,1944						over: over_l,1945						loop_invariant,1946					},1947				);1948				(r, rest)1949			}1950		}1951	}1952	let outer_depth = stack.depth;1953	let (r, compspecs) = go(0, specs, outer_depth, stack, taint, inside);1954	CompSpecResult {1955		inner: r,1956		compspecs,1957	}1958}19591960struct CompSpecResult<R> {1961	inner: R,1962	compspecs: Vec<LCompSpec>,1963}19641965pub fn analyze_root(expr: &Expr, ctx: Vec<(IStr, LocalId)>) -> AnalysisReport {1966	let mut stack = AnalysisStack::new();1967	for (name, id) in ctx {1968		stack.define_external_local(name, id);1969	}19701971	let externals_count: u16 = stack1972		.local_defs1973		.len()1974		.try_into()1975		.expect("more than u16::MAX externals");1976	let closure = stack.push_root_closure(externals_count);19771978	let mut taint = AnalysisResult::default();1979	let lir = analyze(expr, &mut stack, &mut taint);19801981	let root_shape = stack.pop_closure(closure);1982	debug_assert!(1983		stack.closure_stack.is_empty(),1984		"closure stack imbalance after analyze"1985	);19861987	AnalysisReport {1988		lir,1989		root_shape,1990		root_analysis: taint,1991		diagnostics_list: stack.diagnostics,1992		errored: stack.errored,1993	}1994}19951996pub struct AnalysisReport {1997	pub lir: LExpr,1998	pub root_shape: ClosureShape,1999	pub root_analysis: AnalysisResult,2000	pub diagnostics_list: Vec<Diagnostic>,2001	pub errored: bool,2002}20032004#[cfg(test)]2005mod tests {2006	#[test]2007	#[cfg(not(feature = "exp-null-coaelse"))]2008	fn snapshots() {2009		use std::fs;20102011		use insta::{assert_snapshot, glob};2012		use jrsonnet_ir::Source;20132014		use super::*;20152016		fn render_diagnostics(src: &str, diags: &[Diagnostic]) -> String {2017			use std::fmt::Write;20182019			use hi_doc::{Formatting, SnippetBuilder, Text};20202021			let mut out = String::new();2022			let mut unspanned = Vec::new();2023			let mut spanned: Vec<&Diagnostic> = Vec::new();2024			for d in diags {2025				if d.span.is_some() {2026					spanned.push(d);2027				} else {2028					unspanned.push(d);2029				}2030			}2031			if !spanned.is_empty() {2032				let mut builder = SnippetBuilder::new(src);2033				for d in spanned {2034					let span = d.span.as_ref().expect("spanned");2035					let ab = match d.level {2036						DiagLevel::Error => {2037							builder.error(Text::fragment(d.message.clone(), Formatting::default()))2038						}2039						DiagLevel::Warning => builder2040							.warning(Text::fragment(d.message.clone(), Formatting::default())),2041					};2042					ab.range(span.range()).build();2043				}2044				out.push_str(&hi_doc::source_to_ansi(&builder.build()));2045			}2046			for d in unspanned {2047				let prefix = match d.level {2048					DiagLevel::Error => "error",2049					DiagLevel::Warning => "warning",2050				};2051				writeln!(out, "{prefix}: {}", d.message).expect("fmt");2052			}2053			out2054		}2055		fn fmt_depth(d: u32) -> String {2056			if d == u32::MAX {2057				"none".into()2058			} else {2059				d.to_string()2060			}2061		}20622063		glob!("analysis_tests/*.jsonnet", |path| {2064			let code = fs::read_to_string(path).expect("read test file");2065			let src = Source::new_virtual("<test>".into(), code.clone().into());2066			let expr = crate::parse_jsonnet(&code, src.clone()).expect("parse");2067			let report = analyze_root(&expr, Vec::new());20682069			let diagnostics = render_diagnostics(src.code(), &report.diagnostics_list);2070			// Strip ANSI escapes from diagnostics so snapshots are readable.2071			let diagnostics = strip_ansi_escapes::strip_str(&diagnostics);2072			let rendered = format!(2073				"--- source ---\n{}\n--- root analysis ---\nobject_dependent_depth: {}\nlocal_dependent_depth: {}\nerrored: {}\n--- diagnostics ---\n{}--- lir ---\n{:#?}\n",2074				code.trim_end(),2075				fmt_depth(report.root_analysis.object_dependent_depth),2076				fmt_depth(report.root_analysis.local_dependent_depth),2077				report.errored,2078				diagnostics,2079				report.lir,2080			);2081			assert_snapshot!(rendered);2082		});2083	}2084}