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

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::{fmt::Write, rc::Rc};1819use drop_bomb::DropBomb;20use hi_doc::{Formatting, SnippetBuilder, Text};21use jrsonnet_gcmodule::Acyclic;22use jrsonnet_interner::IStr;23use jrsonnet_ir::{24	function::FunctionSignature, ArgsDesc, AssertExpr, AssertStmt, BinaryOp, BinaryOpType,25	BindSpec, CompSpec, Destruct, Expr, ExprParams, FieldName, ForSpecData, IfElse, IfSpecData,26	ImportKind, LiteralType, NumValue, ObjBody, ObjComp, ObjMembers, Slice, SliceDesc, Span,27	Spanned, UnaryOpType, Visibility,28};29use rustc_hash::FxHashMap;30use smallvec::SmallVec;3132use crate::error::{format_found, suggest_names};3334#[derive(Debug, Clone, Copy)]35#[must_use]36pub struct AnalysisResult {37	/// Highest object, on which identity the value is dependent. `u32::MAX` = not dependent at all38	pub object_dependent_depth: u32,39	/// Highest local frame, on which this value depends. `u32::MAX` = not dependent at all40	pub local_dependent_depth: u32,41}4243impl Default for AnalysisResult {44	fn default() -> Self {45		Self {46			object_dependent_depth: u32::MAX,47			local_dependent_depth: u32::MAX,48		}49	}50}5152impl AnalysisResult {53	fn depend_on_object(&mut self, depth: u32) {54		if depth < self.object_dependent_depth {55			self.object_dependent_depth = depth;56		}57	}58	fn depend_on_local(&mut self, depth: u32) {59		if depth < self.local_dependent_depth {60			self.local_dependent_depth = depth;61		}62	}63	fn taint_by(&mut self, other: AnalysisResult) {64		self.depend_on_object(other.object_dependent_depth);65		self.depend_on_local(other.local_dependent_depth);66	}67}6869#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Acyclic)]70pub struct LocalId(pub u32);7172impl LocalId {73	fn idx(self) -> usize {74		self.0 as usize75	}76	fn defined_before(self, other: Self) -> bool {77		self.0 < other.078	}79}8081struct LocalDefinition {82	name: IStr,83	span: Option<Span>,84	/// At which frame depth this local was defined85	defined_at_depth: u32,86	/// Min frame depth, at which this local was used. `u32::MAX` = not used at all.87	/// This check won't catch unused argument closures, i.e:88	/// ```jsonnet89	/// local90	///     a = b,91	///     b = a,92	/// ; 2 + 293	///94	/// ```95	/// Both `a` and `b` here are "used", but the whole closure was not used here.96	used_at_depth: u32,97	/// Used as part of the current frame closure98	used_by_sibling: bool,99	/// Analysys result for value of this local100	analysis: AnalysisResult,101	/// Has `analysis` been filled in?102	/// For sanity checking, locals are initialized in batchs, use `first_uninitialized_local`103	analyzed: bool,104	/// During walk over uninitialized vars, we can't refer to analysis results of other locals,105	/// but we need to. To make that work, for each variable in variable frame we capture its closure,106	/// by looking at referenced variables.107	scratch_referenced: bool,108}109110impl LocalDefinition {111	fn use_at(&mut self, depth: u32) {112		if depth == self.defined_at_depth {113			self.used_by_sibling = true;114			return;115		}116		if depth < self.used_at_depth {117			self.used_at_depth = depth;118		}119	}120}121122#[derive(Debug, Acyclic)]123pub enum LExpr {124	Local(LocalId),125	Null,126	Bool(bool),127	Str(IStr),128	Num(NumValue),129	Arr(Rc<Vec<LExpr>>),130	ArrComp(Box<LArrComp>),131	Obj(LObjBody),132	ObjExtend(Box<LExpr>, LObjBody),133	UnaryOp(UnaryOpType, Box<LExpr>),134	BinaryOp {135		lhs: Box<LExpr>,136		op: BinaryOpType,137		rhs: Box<LExpr>,138	},139	AssertExpr {140		assert: Rc<LAssertStmt>,141		rest: Box<LExpr>,142	},143	Error(Span, Box<LExpr>),144	LocalExpr {145		binds: Vec<LBind>,146		body: Box<LExpr>,147	},148	Import {149		kind: Spanned<ImportKind>,150		kind_span: Span,151		path: IStr,152	},153	Apply {154		applicable: Box<LExpr>,155		args: Spanned<LArgsDesc>,156		tailstrict: bool,157	},158	Index {159		indexable: Box<LExpr>,160		parts: Vec<LIndexPart>,161	},162	Function(Rc<LFunction>),163	IfElse {164		cond: Box<LExpr>,165		cond_then: Box<LExpr>,166		cond_else: Option<Box<LExpr>>,167	},168	Slice(Box<LSliceExpr>),169	Super,170171	/// Allows partial evaluation of broken expression tree,172	/// expressions with failed static analysis end up here173	BadLocal(&'static str),174}175176#[derive(Debug, Acyclic)]177pub struct LFunction {178	pub name: Option<IStr>,179	pub params: Vec<LParam>,180	pub signature: FunctionSignature,181	pub body: Rc<LExpr>,182}183184#[derive(Debug, Acyclic)]185pub struct LParam {186	pub name: Option<IStr>,187	pub destruct: LDestruct,188	pub default: Option<Rc<LExpr>>,189}190191#[derive(Debug, Acyclic)]192pub struct LBind {193	pub destruct: LDestruct,194	pub value: Rc<LExpr>,195}196197#[derive(Debug, Clone, Acyclic)]198pub enum LDestruct {199	Full(LocalId),200	#[cfg(feature = "exp-destruct")]201	Skip,202	#[cfg(feature = "exp-destruct")]203	Array {204		start: Vec<LDestruct>,205		rest: Option<LDestructRest>,206		end: Vec<LDestruct>,207	},208	#[cfg(feature = "exp-destruct")]209	Object {210		fields: Vec<LDestructField>,211		rest: Option<LDestructRest>,212	},213}214215#[derive(Debug, Clone, Copy, Acyclic)]216pub enum LDestructRest {217	Keep(LocalId),218	Drop,219}220221#[derive(Debug, Clone, Acyclic)]222pub struct LDestructField {223	pub name: IStr,224	pub into: Option<LDestruct>,225	pub default: Option<Rc<LExpr>>,226}227228impl LDestruct {229	pub fn each_id<F: FnMut(LocalId)>(&self, f: &mut F) {230		match self {231			Self::Full(id) => f(*id),232			#[cfg(feature = "exp-destruct")]233			Self::Skip => {}234			#[cfg(feature = "exp-destruct")]235			Self::Array { start, rest, end } => {236				for d in start {237					d.each_id(f);238				}239				if let Some(LDestructRest::Keep(id)) = rest {240					f(*id);241				}242				for d in end {243					d.each_id(f);244				}245			}246			#[cfg(feature = "exp-destruct")]247			Self::Object { fields, rest } => {248				for field in fields {249					if let Some(into) = &field.into {250						into.each_id(f);251					} else {252						unreachable!("shorthand object destruct must store `into`");253					}254				}255				if let Some(LDestructRest::Keep(id)) = rest {256					f(*id);257				}258			}259		}260	}261262	pub fn ids(&self) -> SmallVec<[LocalId; 1]> {263		let mut out = SmallVec::new();264		self.each_id(&mut |id| out.push(id));265		out266	}267}268269#[derive(Debug, Acyclic)]270pub struct LSliceExpr {271	pub value: LExpr,272	pub start: Option<LExpr>,273	pub end: Option<LExpr>,274	pub step: Option<LExpr>,275}276277#[derive(Debug, Acyclic)]278pub struct LArgsDesc {279	pub unnamed: Vec<Rc<LExpr>>,280	pub names: Vec<IStr>,281	pub values: Vec<Rc<LExpr>>,282}283284#[derive(Debug, Acyclic)]285pub struct LAssertStmt {286	pub cond: Spanned<LExpr>,287	pub message: Option<LExpr>,288}289290#[derive(Debug, Acyclic)]291pub struct LIndexPart {292	pub span: Span,293	pub value: LExpr,294	#[cfg(feature = "exp-null-coaelse")]295	pub null_coaelse: bool,296}297298#[derive(Debug, Acyclic)]299pub enum LObjBody {300	MemberList(LObjMembers),301	ObjComp(Box<LObjComp>),302}303304#[derive(Debug, Acyclic)]305pub struct LObjMembers {306	/// If current object identity (`super`/`this`/`$`) is used, `this` should be saved to the specified local307	pub this: Option<LocalId>,308	/// Set if dollar should also be assigned to object identity, `this` should also be set (TODO: proper type-level validation)309	pub set_dollar: bool,310	/// True iff `super` is referenced by this object's members.311	pub uses_super: bool,312313	pub locals: Rc<Vec<LBind>>,314	pub asserts: Rc<Vec<LAssertStmt>>,315	pub fields: Vec<LFieldMember>,316}317318#[derive(Debug, Acyclic)]319pub struct LObjComp {320	pub this: Option<LocalId>,321	pub set_dollar: bool,322	pub uses_super: bool,323324	pub locals: Rc<Vec<LBind>>,325	pub field: LFieldMember,326	pub compspecs: Vec<LCompSpec>,327}328329#[derive(Debug, Acyclic)]330pub struct LFieldMember {331	pub name: LFieldName,332	pub plus: bool,333	pub visibility: Visibility,334	pub value: Rc<LExpr>,335}336337#[derive(Debug, Acyclic)]338pub enum LFieldName {339	Fixed(IStr),340	Dyn(LExpr),341}342impl LFieldName {343	fn function_name(&self) -> Option<IStr> {344		match self {345			LFieldName::Fixed(istr) => Some(istr.clone()),346			LFieldName::Dyn(_) => None,347		}348	}349}350351#[derive(Debug, Acyclic)]352pub struct LArrComp {353	pub value: Rc<LExpr>,354	pub compspecs: Vec<LCompSpec>,355}356357#[derive(Debug, Acyclic)]358pub enum LCompSpec {359	If(LExpr),360	For {361		destruct: LDestruct,362		over: LExpr,363		/// Is `over` does not depend on any variable introduced by an earlier for-spec in this comprehension chain364		loop_invariant: bool,365	},366}367368// TODO: Binding frame state machine:369// Pending => AllocIds => Initialize => Body => Exit370371/// Frame state: `LocalIds` allocated, values not yet analysed.372struct PendingInit {373	first_in_frame: LocalId,374	first_after_frame: LocalId,375	bomb: DropBomb,376}377378/// Frame state: values analysed, body not yet walked.379struct PendingBody {380	first_in_frame: LocalId,381	first_after_frame: LocalId,382	closures: Closures,383	bomb: DropBomb,384}385386struct Closures {387	/// All the referenced locals, maybe repeated multiple times388	/// It is recorded as continous vec of sets, I.e we have389	/// a = 1, 2, 3390	/// b = 3, 4, 5, 6391	/// And in `referenced` we have `[ 1, 2, 3, 3, 4, 5, 6 ]`. To actually get, which closure refers to which element, see `spec_shapes`...392	/// Flat concatenation of sibling-local references across all specs.393	referenced: Vec<LocalId>,394	/// Amount of elements per closure, for the above case it is a = 3, b = 4, so here395	/// lies `[ 3, 4 ]`396	/// ~~closures: Vec<usize>,~~397	/// Finally, we have destructs.398	/// Because single destruct references single closure, but destructs to multiple locals, we have even more complicated structure.399	/// Luckly, every destruct is not interleaved with each other, so here we can have full list...400	/// 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 elements401	/// for each destruct starting from `first_destruct_local`402	/// ~~destructs: Vec<usize>,~~403	///404	/// => two of those fields were merged, as there is currently no per-destruct tracking of closures.405	/// For each spec in order: `(references_count, destruct_ids_count)`.406	/// `references_count` tells us how many entries of `referenced` belong407	/// to this spec; `destruct_ids_count` tells us how many `LocalIds` it408	/// binds.409	spec_shapes: Vec<(usize, usize)>,410	/// This is not a related doccomment, just a continuation of docs for previous fields.411	/// Having412	/// ```jsonnet413	/// local414	///     [a, b, c] = [d, e, f],415	///     [d, e, f] = [a, b, c, h],416	///     h = 1,417	/// ;418	/// ```419	///420	/// We have total of 7 locals421	/// First local here is `a` => `first_destruct_local` = `a`422	/// 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`423	/// [d, e, f] = [a, b, c, h], => `referenced += [a, b, c, h]`, `closures += 4`, `destructs += 3` (Note that this destruct will fail at runtime,424	///                                                                                               this thing should not care about that, it only captures what the value are referencing)425	/// h = 1 => referenced += [], closures += 0, destructs += 1426	/// And the result is427	///428	/// ```429	/// Closures {430	///     referenced: vec![d, e, f, a, b, c, h]431	///     spec_shapes: vec![(3, 3), (4, 3), (0, 1)],432	///     first_destruct_label: a,433	/// }434	/// ```435	///436	/// Reconstruction of that:437	///438	/// We know that we start with a439	/// We get the first number from destructs: `destructs.shift() == 3` => `destructs = [3, 1]`440	/// 3 elements counting from a => [a, b, c]441	/// Then we take first number from closures: `closures.shift() == 3` => `closures = [4, 0]`442	/// Then we take 3 items from referenced: `referenced.shift()x3 == d, e, f` => `referenced = [a, b, c, h]`443	///444	/// Thus we have [a, b, c] = [d, e, f]445	first_in_frame: LocalId,446}447448struct Closure<'a> {449	references: &'a [LocalId],450	ids: std::ops::Range<u32>,451}452453impl Closures {454	fn new(first_in_frame: LocalId) -> Self {455		Self {456			referenced: Vec::new(),457			spec_shapes: Vec::new(),458			first_in_frame,459		}460	}461462	fn push_spec(&mut self, destruct_ids_count: usize, refs: &[LocalId]) {463		self.referenced.extend_from_slice(refs);464		self.spec_shapes.push((refs.len(), destruct_ids_count));465	}466467	fn iter_specs(&self) -> impl Iterator<Item = Closure<'_>> {468		let mut refs = self.referenced.as_slice();469		let mut next_id = self.first_in_frame.0;470		self.spec_shapes.iter().map(move |(refs_len, dest_count)| {471			let (this_refs, rest) = refs.split_at(*refs_len);472			refs = rest;473			let start = next_id;474			next_id += *dest_count as u32;475			Closure {476				references: this_refs,477				ids: start..next_id,478			}479		})480	}481}482483#[derive(Debug, Clone, Copy, PartialEq, Eq)]484pub enum DiagLevel {485	Error,486	Warning,487}488489#[derive(Debug, Clone, Acyclic)]490pub struct Diagnostic {491	pub level: DiagLevel,492	pub message: String,493	pub span: Option<Span>,494}495496#[allow(clippy::struct_excessive_bools)]497pub struct AnalysisStack {498	local_defs: Vec<LocalDefinition>,499	/// Shadowing isn't used in jsonnet much, 2 because `SmallVec` allows to store 2 ptr-sized without overhead.500	/// TODO: Add test for this assumption (sizeof(SmallVec<[usize; 1]>) == sizeof(SmallVec<[usize; 2]>))501	local_by_name: FxHashMap<IStr, SmallVec<[LocalId; 2]>>,502503	/// Depth of the current locals frame.504	depth: u32,505	/// Last depth, at which object has appeared. `u32::MAX` = not appeared at all506	last_object_depth: u32,507	/// First depth, at which object has appeared. `u32::MAX` = not appeared at all508	/// $ refers to this object.509	first_object_depth: u32,510511	/// `LocalId` bound to the innermost object's `this`512	this_local: Option<LocalId>,513	/// Outermost object `this`, aka `$`514	dollar_alias: Option<LocalId>,515	/// True iff `self` has been referenced in the current object immediate members (not nested children).516	cur_self_used: bool,517	/// True iff `super` has been referenced in the current object immediate members.518	cur_super_used: bool,519	/// True iff `$` has been referenced anywhere since the outermost object's scope was entered.520	dollar_used: bool,521522	diagnostics: Vec<Diagnostic>,523	/// Whenever analysis would be broken due to static analysis error.524	errored: bool,525}526527impl AnalysisStack {528	pub fn new() -> Self {529		Self {530			local_defs: Vec::new(),531			local_by_name: FxHashMap::default(),532			depth: 0,533			last_object_depth: u32::MAX,534			first_object_depth: u32::MAX,535			this_local: None,536			dollar_alias: None,537			cur_self_used: false,538			cur_super_used: false,539			dollar_used: false,540			diagnostics: Vec::new(),541			errored: false,542		}543	}544545	fn next_local_id(&self) -> LocalId {546		LocalId(self.local_defs.len() as u32)547	}548549	fn report_error(&mut self, msg: impl Into<String>, span: Option<Span>) {550		self.errored = true;551		self.diagnostics.push(Diagnostic {552			level: DiagLevel::Error,553			message: msg.into(),554			span,555		});556	}557	fn report_warning(&mut self, msg: impl Into<String>, span: Option<Span>) {558		self.diagnostics.push(Diagnostic {559			level: DiagLevel::Warning,560			message: msg.into(),561			span,562		});563	}564565	fn use_local(566		&mut self,567		name: &IStr,568		span: Span,569		taint: &mut AnalysisResult,570	) -> Option<LocalId> {571		let Some(ids) = self.local_by_name.get(name) else {572			let names = suggest_names(name, self.local_by_name.keys());573			self.report_error(574				format!("undefined local: {name}{}", format_found(&names, "local")),575				Some(span),576			);577			return None;578		};579		let id = *ids.last().expect("empty stacks should be removed");580		let depth = self.depth;581		let def = &mut self.local_defs[id.idx()];582		def.use_at(depth);583		taint.depend_on_local(def.defined_at_depth);584		if def.analyzed {585			taint.taint_by(def.analysis);586		} else {587			def.scratch_referenced = true;588		}589		Some(id)590	}591592	/// Assign name to the value provided externally, e.g `std`.593	pub fn define_external_local(&mut self, name: IStr, id: LocalId) {594		assert!(595			self.local_defs.iter().all(|d| d.analyzed),596			"external locals must be defined before the root expression is analysed"597		);598		assert_eq!(599			id,600			self.next_local_id(),601			"external local id mismatch for {name} (externals must be defined in allocation order)"602		);603		self.local_defs.push(LocalDefinition {604			name: name.clone(),605			span: None,606			defined_at_depth: 0,607			used_at_depth: u32::MAX,608			used_by_sibling: false,609			analysis: AnalysisResult::default(),610			analyzed: true,611			scratch_referenced: false,612		});613		self.local_by_name.entry(name).or_default().push(id);614	}615616	/// Define a new local inside a frame currently being built.617	fn define_local(618		&mut self,619		name: IStr,620		span: Option<Span>,621		frame_start: LocalId,622	) -> Option<LocalId> {623		let id = self.next_local_id();624		let stack = self.local_by_name.entry(name.clone()).or_default();625		if let Some(&existing) = stack.last() {626			if !existing.defined_before(frame_start) {627				self.report_error(628					format!("local is already defined in the current frame: {name}"),629					span,630				);631				return None;632			}633		}634		stack.push(id);635		self.local_defs.push(LocalDefinition {636			name,637			span,638			defined_at_depth: self.depth,639			used_at_depth: u32::MAX,640			used_by_sibling: false,641			analysis: AnalysisResult::default(),642			analyzed: false,643			scratch_referenced: false,644		});645		Some(id)646	}647}648649impl Default for AnalysisStack {650	fn default() -> Self {651		Self::new()652	}653}654655impl AnalysisStack {656	fn alloc_destruct(&mut self, destruct: &Destruct, frame_start: LocalId) -> Option<LDestruct> {657		match destruct {658			Destruct::Full(name) => {659				let id =660					self.define_local(name.value.clone(), Some(name.span.clone()), frame_start)?;661				Some(LDestruct::Full(id))662			}663			#[cfg(feature = "exp-destruct")]664			Destruct::Skip => Some(LDestruct::Skip),665			#[cfg(feature = "exp-destruct")]666			Destruct::Array { start, rest, end } => {667				let start = start668					.iter()669					.map(|d| self.alloc_destruct(d, frame_start))670					.collect::<Option<Vec<_>>>()?;671				let rest = match rest {672					Some(jrsonnet_ir::DestructRest::Keep(name)) => {673						let id = self.define_local(name.clone(), None, frame_start)?;674						Some(LDestructRest::Keep(id))675					}676					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),677					None => None,678				};679				let end = end680					.iter()681					.map(|d| self.alloc_destruct(d, frame_start))682					.collect::<Option<Vec<_>>>()?;683				Some(LDestruct::Array { start, rest, end })684			}685			#[cfg(feature = "exp-destruct")]686			Destruct::Object { fields, rest } => {687				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());688				// Two passes: first allocate ALL destruct LocalIds, then689				// analyse defaults (which may reference later fields).690				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());691				for (name, into, _default) in fields {692					let into = if let Some(inner) = into {693						self.alloc_destruct(inner, frame_start)?694					} else {695						let id = self.define_local(name.clone(), None, frame_start)?;696						LDestruct::Full(id)697					};698					l_fields.push((name.clone(), into));699				}700				// Second pass: all locals exist, so defaults can reference701				// any sibling.702				let l_fields: Vec<LDestructField> = l_fields703					.into_iter()704					.zip(fields.iter())705					.map(|((name, into), (_n, _i, default))| {706						let default = default.as_ref().map(|e| {707							let mut default_taint = AnalysisResult::default();708							Rc::new(analyze(&e.value, self, &mut default_taint))709						});710						LDestructField {711							name,712							into: Some(into),713							default,714						}715					})716					.collect();717				let rest = match rest {718					Some(jrsonnet_ir::DestructRest::Keep(name)) => {719						let id = self.define_local(name.clone(), None, frame_start)?;720						Some(LDestructRest::Keep(id))721					}722					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),723					None => None,724				};725				Some(LDestruct::Object {726					fields: l_fields,727					rest,728				})729			}730		}731	}732733	// TODO: Proper state machine734	fn begin_frame_alloc(&mut self) -> LocalId {735		self.next_local_id()736	}737738	fn finish_frame_alloc(&mut self, first_in_frame: LocalId) -> PendingInit {739		let first_after_frame = self.next_local_id();740		PendingInit {741			first_in_frame,742			first_after_frame,743			bomb: DropBomb::new("PendingInit must be passed to finish_frame_init"),744		}745	}746747	/// Record the analysis of a spec's value: stamp every id bound by the748	/// spec with `analysis`, collect the spec's same-frame references, and749	/// append them to `closures`.750	fn record_spec_init(751		&mut self,752		pending: &PendingInit,753		destruct: &LDestruct,754		analysis: AnalysisResult,755		closures: &mut Closures,756	) {757		let mut refs: SmallVec<[LocalId; 4]> = SmallVec::new();758		for i in pending.first_in_frame.0..pending.first_after_frame.0 {759			let def = &mut self.local_defs[i as usize];760			if def.scratch_referenced {761				refs.push(LocalId(i));762				def.scratch_referenced = false;763			}764		}765766		let mut ids_count = 0;767		destruct.each_id(&mut |id| {768			ids_count += 1;769			let def = &mut self.local_defs[id.idx()];770			debug_assert!(!def.analyzed, "sanity: local {:?} analysed twice", def.name);771			def.analysis = analysis;772			def.analyzed = true;773		});774		closures.push_spec(ids_count, &refs);775	}776777	/// After all specs are analysed, propagate dependency information between778	/// siblings to a fix-point, then switch to "body" mode.779	fn finish_frame_init(&mut self, pending: PendingInit, closures: Closures) -> PendingBody {780		let PendingInit {781			first_in_frame,782			first_after_frame,783			mut bomb,784		} = pending;785		bomb.defuse();786787		debug_assert_eq!(788			first_after_frame,789			self.next_local_id(),790			"frame initialisation left unfinished locals"791		);792793		debug_assert_eq!(794			closures.spec_shapes.iter().map(|(_, d)| *d).sum::<usize>(),795			(first_after_frame.0 - first_in_frame.0) as usize,796			"closures destruct-id counts must match frame local count"797		);798799		let mut changed = true;800		while changed {801			changed = false;802			for spec in closures.iter_specs() {803				for id_raw in spec.ids.clone() {804					let user = LocalId(id_raw);805					for &used in spec.references {806						changed |= self.propagate_analysis(user, used);807					}808				}809			}810		}811812		self.depth += 1;813		PendingBody {814			first_in_frame,815			first_after_frame,816			closures,817			bomb: DropBomb::new("PendingBody must be passed to finish_frame_body"),818		}819	}820821	/// Merge `used`'s analysis into `user`'s analysis and record that `user`822	/// transitively depends on `used` (same-frame sibling reference).823	/// Returns `true` if `user`'s analysis changed.824	fn propagate_analysis(&mut self, user: LocalId, used: LocalId) -> bool {825		let (used_analysis, used_defined_at_depth) = {826			let u = &self.local_defs[used.idx()];827			(u.analysis, u.defined_at_depth)828		};829		let user_def = &mut self.local_defs[user.idx()];830		let before_obj = user_def.analysis.object_dependent_depth;831		let before_loc = user_def.analysis.local_dependent_depth;832		user_def.analysis.taint_by(used_analysis);833		user_def.analysis.depend_on_local(used_defined_at_depth);834		before_obj != user_def.analysis.object_dependent_depth835			|| before_loc != user_def.analysis.local_dependent_depth836	}837838	/// After the body is processed, drop the frame's locals and emit any839	/// "unused local" warnings.840	fn finish_frame_body(&mut self, pending: PendingBody) {841		let PendingBody {842			first_in_frame,843			first_after_frame,844			closures,845			mut bomb,846		} = pending;847		bomb.defuse();848		self.depth -= 1;849850		debug_assert_eq!(851			first_after_frame,852			self.next_local_id(),853			"nested scopes must be popped before outer frames"854		);855856		let mut changed = true;857		while changed {858			changed = false;859			for spec in closures.iter_specs() {860				// Effective used_at_depth for the spec = min over its ids.861				let mut min_used_at = u32::MAX;862				for id_raw in spec.ids.clone() {863					min_used_at = min_used_at.min(self.local_defs[id_raw as usize].used_at_depth);864				}865				if min_used_at == u32::MAX {866					continue;867				}868				for &used in spec.references {869					let used_def = &mut self.local_defs[used.idx()];870					if min_used_at < used_def.used_at_depth {871						used_def.used_at_depth = min_used_at;872						changed = true;873					}874				}875			}876		}877878		let drained: Vec<LocalDefinition> = self.local_defs.drain(first_in_frame.idx()..).collect();879		for (i, def) in drained.iter().enumerate().rev() {880			let id = LocalId(first_in_frame.0 + i as u32);881			let stack = self882				.local_by_name883				.get_mut(&def.name)884				.expect("local must be in name map");885			let popped = stack.pop().expect("name stack should not be empty");886			debug_assert_eq!(popped, id, "name stack integrity");887			if stack.is_empty() {888				self.local_by_name.remove(&def.name);889			}890891			if def.used_at_depth == u32::MAX {892				if def.used_by_sibling {893					self.report_warning(894						format!("local is only referenced by unused siblings: {}", def.name),895						def.span.clone(),896					);897				} else {898					self.report_warning(format!("unused local: {}", def.name), def.span.clone());899				}900			} else if def.analysis.local_dependent_depth > def.defined_at_depth901				&& def.analysis.object_dependent_depth > def.defined_at_depth902				&& def.defined_at_depth != 0903			{904				// The value doesn't depend on anything defined at or inside905				// this local's scope - can be hoisted, unfortunately not automatically.906				self.report_warning(907					format!("local could be hoisted to an outer scope: {}", def.name),908					def.span.clone(),909				);910			}911		}912	}913}914915mod names {916	use crate::names;917918	names! {919		this: "this",920	}921}922923// Object scope helpers924impl AnalysisStack {925	// TODO: proper state machine926	fn enter_object_scope(&mut self) -> ObjectScope {927		let is_outermost = self.first_object_depth == u32::MAX;928		let scope = ObjectScope {929			this_id: self.push_pseudo_local(names::this()),930			is_outermost,931			prev_this_local: self.this_local,932			prev_dollar_alias: self.dollar_alias,933			prev_cur_self_used: self.cur_self_used,934			prev_cur_super_used: self.cur_super_used,935			prev_dollar_used: is_outermost.then_some(self.dollar_used),936			prev_last_object: self.last_object_depth,937			prev_first_object: self.first_object_depth,938		};939940		self.this_local = Some(scope.this_id);941		if is_outermost {942			self.dollar_alias = Some(scope.this_id);943			self.first_object_depth = self.depth;944			self.dollar_used = false;945		}946		self.last_object_depth = self.depth;947		self.cur_self_used = false;948		self.cur_super_used = false;949		scope950	}951952	fn leave_object_scope(&mut self, scope: ObjectScope) -> ObjectUsage {953		let _ = self.local_defs.pop().expect("this pseudo-local exists");954		debug_assert_eq!(self.local_defs.len(), scope.this_id.0 as usize);955956		let set_dollar = scope.is_outermost && self.dollar_used;957		let usage = ObjectUsage {958			this_id: scope.this_id,959			this_used: self.cur_self_used || self.cur_super_used || set_dollar,960			uses_super: self.cur_super_used,961			set_dollar,962		};963964		self.this_local = scope.prev_this_local;965		self.dollar_alias = scope.prev_dollar_alias;966		self.cur_self_used = scope.prev_cur_self_used;967		self.cur_super_used = scope.prev_cur_super_used;968		if let Some(prev) = scope.prev_dollar_used {969			self.dollar_used = prev;970		}971		self.last_object_depth = scope.prev_last_object;972		self.first_object_depth = scope.prev_first_object;973974		usage975	}976977	fn push_pseudo_local(&mut self, name: IStr) -> LocalId {978		let id = self.next_local_id();979		self.local_defs.push(LocalDefinition {980			name,981			span: None,982			defined_at_depth: self.depth,983			used_at_depth: u32::MAX,984			used_by_sibling: false,985			analysis: AnalysisResult::default(),986			analyzed: true,987			scratch_referenced: false,988		});989		id990	}991992	fn use_this(&mut self, taint: &mut AnalysisResult) -> Option<LocalId> {993		let id = self.this_local?;994		self.cur_self_used = true;995		self.use_pseudo_local(id, taint);996		Some(id)997	}998999	fn use_super(&mut self, taint: &mut AnalysisResult) -> Option<()> {1000		let id = self.this_local?;1001		self.cur_super_used = true;1002		self.use_pseudo_local(id, taint);1003		Some(())1004	}10051006	fn use_dollar(&mut self, taint: &mut AnalysisResult) -> Option<LocalId> {1007		let id = self.dollar_alias?;1008		self.dollar_used = true;1009		self.use_pseudo_local(id, taint);1010		Some(id)1011	}10121013	// TODO: Dedicated type for object references instead of "pseudo local" BS, idk1014	fn use_pseudo_local(&mut self, id: LocalId, taint: &mut AnalysisResult) {1015		let depth = self.depth;1016		let def = &mut self.local_defs[id.idx()];1017		def.use_at(depth);1018		taint.depend_on_local(def.defined_at_depth);1019		taint.depend_on_object(def.defined_at_depth);1020	}1021}10221023struct ObjectScope {1024	this_id: LocalId,1025	is_outermost: bool,1026	prev_this_local: Option<LocalId>,1027	prev_dollar_alias: Option<LocalId>,1028	prev_cur_self_used: bool,1029	prev_cur_super_used: bool,1030	prev_dollar_used: Option<bool>,1031	prev_last_object: u32,1032	prev_first_object: u32,1033}10341035struct ObjectUsage {1036	this_id: LocalId,1037	this_used: bool,1038	uses_super: bool,1039	set_dollar: bool,1040}10411042fn analyze_assert(1043	stmt: &AssertStmt,1044	stack: &mut AnalysisStack,1045	taint: &mut AnalysisResult,1046) -> LAssertStmt {1047	let cond = analyze(&stmt.assertion.value, stack, taint);1048	let message = stmt.message.as_ref().map(|m| analyze(m, stack, taint));1049	LAssertStmt {1050		cond: Spanned::new(cond, stmt.assertion.span.clone()),1051		message,1052	}1053}10541055#[allow(clippy::too_many_lines)]1056pub fn analyze_named(1057	name: IStr,1058	expr: &Expr,1059	stack: &mut AnalysisStack,1060	taint: &mut AnalysisResult,1061) -> LExpr {1062	if let Expr::Function(params, body) = expr {1063		return analyze_function(Some(name), params, body, stack, taint);1064	}1065	analyze(expr, stack, taint)1066}1067#[allow(clippy::too_many_lines)]1068pub fn analyze(expr: &Expr, stack: &mut AnalysisStack, taint: &mut AnalysisResult) -> LExpr {1069	match expr {1070		Expr::Literal(l) => match l {1071			LiteralType::This => stack.use_this(taint).map_or_else(1072				|| {1073					stack.report_error("`self` used outside of object", None);1074					LExpr::BadLocal("self")1075				},1076				LExpr::Local,1077			),1078			LiteralType::Super => {1079				if stack.use_super(taint).is_some() {1080					LExpr::Super1081				} else {1082					stack.report_error("`super` used outside of object", None);1083					LExpr::BadLocal("super")1084				}1085			}1086			LiteralType::Dollar => stack.use_dollar(taint).map_or_else(1087				|| {1088					stack.report_error("`$` used outside of object", None);1089					LExpr::BadLocal("$")1090				},1091				LExpr::Local,1092			),1093			LiteralType::Null => LExpr::Null,1094			LiteralType::True => LExpr::Bool(true),1095			LiteralType::False => LExpr::Bool(false),1096		},1097		Expr::Str(s) => LExpr::Str(s.clone()),1098		Expr::Num(n) => LExpr::Num(*n),1099		Expr::Var(v) => stack1100			.use_local(&v.value, v.span.clone(), taint)1101			.map_or_else(|| LExpr::BadLocal("ref"), LExpr::Local),1102		Expr::Arr(a) => LExpr::Arr(Rc::new(1103			a.iter().map(|v| analyze(v, stack, taint)).collect(),1104		)),1105		Expr::ArrComp(inner, comp) => analyze_arr_comp(inner, comp, stack, taint),1106		Expr::Obj(obj) => LExpr::Obj(analyze_obj_body(obj, stack, taint)),1107		Expr::ObjExtend(base, obj) => LExpr::ObjExtend(1108			Box::new(analyze(base, stack, taint)),1109			analyze_obj_body(obj, stack, taint),1110		),1111		Expr::UnaryOp(op, value) => LExpr::UnaryOp(*op, Box::new(analyze(value, stack, taint))),1112		Expr::BinaryOp(op) => {1113			let BinaryOp {1114				lhs,1115				op: optype,1116				rhs,1117			} = &**op;1118			LExpr::BinaryOp {1119				lhs: Box::new(analyze(lhs, stack, taint)),1120				op: *optype,1121				rhs: Box::new(analyze(rhs, stack, taint)),1122			}1123		}1124		Expr::AssertExpr(assert) => {1125			let AssertExpr { assert, rest } = &**assert;1126			let assert = Rc::new(analyze_assert(assert, stack, taint));1127			let rest = Box::new(analyze(rest, stack, taint));1128			LExpr::AssertExpr { assert, rest }1129		}1130		Expr::LocalExpr(binds, body) => analyze_local_expr(binds, body, stack, taint),1131		Expr::Import(kind, path_expr) => {1132			let Expr::Str(path) = &**path_expr else {1133				stack.report_error(1134					"import path must be a string literal",1135					Some(kind.span.clone()),1136				);1137				return LExpr::BadLocal("bad import");1138			};1139			LExpr::Import {1140				kind: kind.clone(),1141				kind_span: kind.span.clone(),1142				path: path.clone(),1143			}1144		}1145		Expr::ErrorStmt(span, inner) => {1146			LExpr::Error(span.clone(), Box::new(analyze(inner, stack, taint)))1147		}1148		Expr::Apply(applicable, args, tailstrict) => {1149			let app = analyze(applicable, stack, taint);1150			let ArgsDesc {1151				unnamed,1152				names,1153				values,1154			} = &args.value;1155			let unnamed_l = unnamed1156				.iter()1157				.map(|a| Rc::new(analyze(a, stack, taint)))1158				.collect();1159			let values_l = values1160				.iter()1161				.map(|a| Rc::new(analyze(a, stack, taint)))1162				.collect();1163			LExpr::Apply {1164				applicable: Box::new(app),1165				args: Spanned::new(1166					LArgsDesc {1167						unnamed: unnamed_l,1168						names: names.clone(),1169						values: values_l,1170					},1171					args.span.clone(),1172				),1173				tailstrict: *tailstrict,1174			}1175		}1176		Expr::Index { indexable, parts } => {1177			let idx = analyze(indexable, stack, taint);1178			let parts_l = parts1179				.iter()1180				.map(|p| {1181					let value = analyze(&p.value, stack, taint);1182					LIndexPart {1183						span: p.span.clone(),1184						value,1185						#[cfg(feature = "exp-null-coaelse")]1186						null_coaelse: p.null_coaelse,1187					}1188				})1189				.collect();1190			LExpr::Index {1191				indexable: Box::new(idx),1192				parts: parts_l,1193			}1194		}1195		Expr::Function(params, body) => analyze_function(None, params, body, stack, taint),1196		Expr::IfElse(ifelse) => {1197			let IfElse {1198				cond,1199				cond_then,1200				cond_else,1201			} = &**ifelse;1202			let cond_l = analyze(&cond.cond, stack, taint);1203			let then_l = analyze(cond_then, stack, taint);1204			let else_l = cond_else1205				.as_ref()1206				.map(|e| Box::new(analyze(e, stack, taint)));1207			LExpr::IfElse {1208				cond: Box::new(cond_l),1209				cond_then: Box::new(then_l),1210				cond_else: else_l,1211			}1212		}1213		Expr::Slice(slice) => {1214			let Slice {1215				value,1216				slice: SliceDesc { start, end, step },1217			} = &**slice;1218			let value_l = analyze(value, stack, taint);1219			let start_l = start.as_ref().map(|e| analyze(&e.value, stack, taint));1220			let end_l = end.as_ref().map(|e| analyze(&e.value, stack, taint));1221			let step_l = step.as_ref().map(|e| analyze(&e.value, stack, taint));1222			LExpr::Slice(Box::new(LSliceExpr {1223				value: value_l,1224				start: start_l,1225				end: end_l,1226				step: step_l,1227			}))1228		}1229	}1230}12311232fn analyze_local_expr(1233	binds: &[BindSpec],1234	body: &Expr,1235	stack: &mut AnalysisStack,1236	taint: &mut AnalysisResult,1237) -> LExpr {1238	if binds.is_empty() {1239		return analyze(body, stack, taint);1240	}1241	let (_frame_start, l_binds, body_expr) =1242		process_local_frame(binds, stack, taint, |stack, taint| {1243			analyze(body, stack, taint)1244		});1245	LExpr::LocalExpr {1246		binds: l_binds,1247		body: Box::new(body_expr),1248	}1249}12501251fn analyze_bind_value(1252	bind: &BindSpec,1253	stack: &mut AnalysisStack,1254	taint: &mut AnalysisResult,1255) -> LExpr {1256	match bind {1257		BindSpec::Field {1258			value: Expr::Function(params, value),1259			into: Destruct::Full(name),1260		} => analyze_function(Some(name.value.clone()), params, value, stack, taint),1261		BindSpec::Field { value, .. } => analyze(value, stack, taint),1262		BindSpec::Function {1263			params,1264			value,1265			name,1266		} => analyze_function(Some(name.clone()), params, value, stack, taint),1267	}1268}12691270fn alloc_bind_destruct(1271	bind: &BindSpec,1272	stack: &mut AnalysisStack,1273	frame_start: LocalId,1274) -> Option<LDestruct> {1275	match bind {1276		BindSpec::Field { into, .. } => stack.alloc_destruct(into, frame_start),1277		BindSpec::Function { name, .. } => stack1278			.define_local(name.clone(), None, frame_start)1279			.map(LDestruct::Full),1280	}1281}12821283fn process_local_frame<R>(1284	binds: &[BindSpec],1285	stack: &mut AnalysisStack,1286	taint: &mut AnalysisResult,1287	body_fn: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1288) -> (LocalId, Vec<LBind>, R) {1289	let frame_start = stack.begin_frame_alloc();12901291	let mut destructs: Vec<Option<LDestruct>> = Vec::with_capacity(binds.len());1292	for bind in binds {1293		destructs.push(alloc_bind_destruct(bind, stack, frame_start));1294	}1295	let pending = stack.finish_frame_alloc(frame_start);12961297	let mut closures = Closures::new(frame_start);1298	let mut l_binds: Vec<LBind> = Vec::with_capacity(binds.len());1299	for (bind, destruct) in binds.iter().zip(destructs.into_iter()) {1300		let mut value_taint = AnalysisResult::default();1301		let value = analyze_bind_value(bind, stack, &mut value_taint);1302		taint.taint_by(value_taint);1303		if let Some(destruct) = destruct {1304			stack.record_spec_init(&pending, &destruct, value_taint, &mut closures);1305			l_binds.push(LBind {1306				destruct,1307				value: Rc::new(value),1308			});1309		} else {1310			closures.push_spec(0, &[]);1311		}1312	}13131314	let body_frame = stack.finish_frame_init(pending, closures);1315	let result = body_fn(stack, taint);1316	stack.finish_frame_body(body_frame);13171318	(frame_start, l_binds, result)1319}13201321fn analyze_function(1322	name: Option<IStr>,1323	params: &ExprParams,1324	body: &Expr,1325	stack: &mut AnalysisStack,1326	taint: &mut AnalysisResult,1327) -> LExpr {1328	let frame_start = stack.begin_frame_alloc();13291330	let mut param_destructs: Vec<Option<LDestruct>> = Vec::with_capacity(params.exprs.len());1331	for p in &params.exprs {1332		param_destructs.push(stack.alloc_destruct(&p.destruct, frame_start));1333	}13341335	let pending = stack.finish_frame_alloc(frame_start);13361337	let mut closures = Closures::new(frame_start);1338	let mut l_params: Vec<LParam> = Vec::with_capacity(params.exprs.len());1339	for (p, destruct) in params.exprs.iter().zip(param_destructs.into_iter()) {1340		let mut value_taint = AnalysisResult::default();1341		let default = p1342			.default1343			.as_ref()1344			.map(|d| Rc::new(analyze(d, stack, &mut value_taint)));1345		taint.taint_by(value_taint);1346		if let Some(destruct) = destruct {1347			let name = match &p.destruct {1348				Destruct::Full(n) => Some(n.value.clone()),1349				#[cfg(feature = "exp-destruct")]1350				_ => None,1351			};1352			stack.record_spec_init(&pending, &destruct, value_taint, &mut closures);1353			l_params.push(LParam {1354				name,1355				destruct,1356				default,1357			});1358		} else {1359			closures.push_spec(0, &[]);1360		}1361	}13621363	let body_frame = stack.finish_frame_init(pending, closures);1364	let body_expr = analyze(body, stack, taint);1365	stack.finish_frame_body(body_frame);13661367	LExpr::Function(Rc::new(LFunction {1368		name,1369		params: l_params,1370		signature: params.signature.clone(),1371		body: Rc::new(body_expr),1372	}))1373}13741375fn analyze_obj_body(1376	obj: &ObjBody,1377	stack: &mut AnalysisStack,1378	taint: &mut AnalysisResult,1379) -> LObjBody {1380	match obj {1381		ObjBody::MemberList(members) => {1382			LObjBody::MemberList(analyze_obj_members(members, stack, taint))1383		}1384		ObjBody::ObjComp(comp) => LObjBody::ObjComp(Box::new(analyze_obj_comp(comp, stack, taint))),1385	}1386}13871388fn analyze_obj_members(1389	members: &ObjMembers,1390	stack: &mut AnalysisStack,1391	taint: &mut AnalysisResult,1392) -> LObjMembers {1393	let ObjMembers {1394		locals,1395		asserts,1396		fields,1397	} = members;13981399	// Names are analyzed in enclosing scope, they can't depend on locals or self/super1400	let field_names: Vec<LFieldName> = fields1401		.iter()1402		.map(|f| match &f.name.value {1403			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1404			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1405		})1406		.collect();14071408	let scope = stack.enter_object_scope();1409	let (_frame_start, l_binds, (l_asserts, l_fields)) =1410		process_local_frame(locals, stack, taint, |stack, taint| {1411			let mut l_asserts = Vec::with_capacity(asserts.len());1412			for a in asserts {1413				let mut assert_taint = AnalysisResult::default();1414				l_asserts.push(analyze_assert(a, stack, &mut assert_taint));1415				taint.taint_by(assert_taint);1416			}1417			let mut l_fields = Vec::with_capacity(fields.len());1418			for (f, name) in fields.iter().zip(field_names) {1419				let value = if let Some(params) = &f.params {1420					analyze_function(name.function_name(), params, &f.value, stack, taint)1421				} else {1422					analyze(&f.value, stack, taint)1423				};1424				l_fields.push(LFieldMember {1425					name,1426					plus: f.plus,1427					visibility: f.visibility,1428					value: Rc::new(value),1429				});1430			}1431			(l_asserts, l_fields)1432		});1433	let usage = stack.leave_object_scope(scope);1434	LObjMembers {1435		this: usage.this_used.then_some(usage.this_id),1436		set_dollar: usage.set_dollar,1437		uses_super: usage.uses_super,1438		locals: Rc::new(l_binds),1439		asserts: Rc::new(l_asserts),1440		fields: l_fields,1441	}1442}14431444fn analyze_obj_comp(1445	comp: &ObjComp,1446	stack: &mut AnalysisStack,1447	taint: &mut AnalysisResult,1448) -> LObjComp {1449	let res = analyze_comp_specs(&comp.compspecs, stack, taint, |stack, taint| {1450		let field_name = match &comp.field.name.value {1451			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1452			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1453		};14541455		let scope = stack.enter_object_scope();1456		let body = process_local_frame(&comp.locals, stack, taint, |stack, taint| {1457			let value = if let Some(params) = &comp.field.params {1458				analyze_function(None, params, &comp.field.value, stack, taint)1459			} else {1460				analyze(&comp.field.value, stack, taint)1461			};1462			LFieldMember {1463				name: field_name,1464				plus: comp.field.plus,1465				visibility: comp.field.visibility,1466				value: Rc::new(value),1467			}1468		});1469		let usage = stack.leave_object_scope(scope);1470		(usage, body)1471	});1472	let (usage, (_frame_start, locals, field)) = res.inner;1473	LObjComp {1474		this: usage.this_used.then_some(usage.this_id),1475		set_dollar: usage.set_dollar,1476		uses_super: usage.uses_super,1477		locals: Rc::new(locals),1478		field,1479		compspecs: res.compspecs,1480	}1481}14821483fn analyze_arr_comp(1484	inner: &Expr,1485	specs: &[CompSpec],1486	stack: &mut AnalysisStack,1487	taint: &mut AnalysisResult,1488) -> LExpr {1489	let res = analyze_comp_specs(specs, stack, taint, |stack, taint| {1490		analyze(inner, stack, taint)1491	});1492	LExpr::ArrComp(Box::new(LArrComp {1493		value: Rc::new(res.inner),1494		compspecs: res.compspecs,1495	}))1496}14971498fn analyze_comp_specs<R>(1499	specs: &[CompSpec],1500	stack: &mut AnalysisStack,1501	taint: &mut AnalysisResult,1502	inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1503) -> CompSpecResult<R> {1504	fn go<R>(1505		idx: usize,1506		specs: &[CompSpec],1507		outer_depth: u32,1508		stack: &mut AnalysisStack,1509		taint: &mut AnalysisResult,1510		inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1511	) -> (R, Vec<LCompSpec>) {1512		if idx >= specs.len() {1513			return (inside(stack, taint), Vec::new());1514		}1515		match &specs[idx] {1516			CompSpec::IfSpec(IfSpecData { cond, .. }) => {1517				let cond_l = analyze(cond, stack, taint);1518				let (r, mut rest) = go(idx + 1, specs, outer_depth, stack, taint, inside);1519				rest.insert(0, LCompSpec::If(cond_l));1520				(r, rest)1521			}1522			CompSpec::ForSpec(ForSpecData { destruct, over }) => {1523				let mut over_taint = AnalysisResult::default();1524				let over_l = analyze(over, stack, &mut over_taint);1525				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1526				taint.taint_by(over_taint);15271528				let frame_start = stack.begin_frame_alloc();1529				let Some(l_destruct) = stack.alloc_destruct(destruct, frame_start) else {1530					return go(idx + 1, specs, outer_depth, stack, taint, inside);1531				};1532				let pending = stack.finish_frame_alloc(frame_start);15331534				let var_analysis = AnalysisResult::default();1535				let mut closures = Closures::new(frame_start);1536				stack.record_spec_init(&pending, &l_destruct, var_analysis, &mut closures);15371538				let body_frame = stack.finish_frame_init(pending, closures);1539				let (r, mut rest) = go(idx + 1, specs, outer_depth, stack, taint, inside);1540				stack.finish_frame_body(body_frame);15411542				rest.insert(1543					0,1544					LCompSpec::For {1545						destruct: l_destruct,1546						over: over_l,1547						loop_invariant,1548					},1549				);1550				(r, rest)1551			}1552		}1553	}1554	let outer_depth = stack.depth;1555	let (r, compspecs) = go(0, specs, outer_depth, stack, taint, inside);1556	CompSpecResult {1557		inner: r,1558		compspecs,1559	}1560}15611562struct CompSpecResult<R> {1563	inner: R,1564	compspecs: Vec<LCompSpec>,1565}15661567pub fn analyze_root(expr: &Expr, ctx: Vec<(IStr, LocalId)>) -> AnalysisReport {1568	let mut stack = AnalysisStack::new();1569	for (name, id) in ctx {1570		stack.define_external_local(name, id);1571	}15721573	let mut taint = AnalysisResult::default();1574	let lir = analyze(expr, &mut stack, &mut taint);15751576	AnalysisReport {1577		lir,1578		root_analysis: taint,1579		diagnostics_list: stack.diagnostics,1580		errored: stack.errored,1581	}1582}15831584fn render_diagnostics(src: &str, diags: &[Diagnostic]) -> String {1585	let mut out = String::new();1586	let mut unspanned = Vec::new();1587	let mut spanned: Vec<&Diagnostic> = Vec::new();1588	for d in diags {1589		if d.span.is_some() {1590			spanned.push(d);1591		} else {1592			unspanned.push(d);1593		}1594	}1595	if !spanned.is_empty() {1596		let mut builder = SnippetBuilder::new(src);1597		for d in spanned {1598			let span = d.span.as_ref().expect("spanned");1599			let ab = match d.level {1600				DiagLevel::Error => {1601					builder.error(Text::fragment(d.message.clone(), Formatting::default()))1602				}1603				DiagLevel::Warning => {1604					builder.warning(Text::fragment(d.message.clone(), Formatting::default()))1605				}1606			};1607			ab.range(span.range()).build();1608		}1609		out.push_str(&hi_doc::source_to_ansi(&builder.build()));1610	}1611	for d in unspanned {1612		let prefix = match d.level {1613			DiagLevel::Error => "error",1614			DiagLevel::Warning => "warning",1615		};1616		writeln!(out, "{prefix}: {}", d.message).expect("fmt");1617	}1618	out1619}16201621pub struct AnalysisReport {1622	pub lir: LExpr,1623	pub root_analysis: AnalysisResult,1624	pub diagnostics_list: Vec<Diagnostic>,1625	pub errored: bool,1626}16271628#[cfg(test)]1629mod tests {1630	use std::fs;16311632	use insta::{assert_snapshot, glob};1633	use jrsonnet_ir::Source;16341635	use super::*;16361637	#[test]1638	fn snapshots() {1639		glob!("analysis_tests/*.jsonnet", |path| {1640			let code = fs::read_to_string(path).expect("read test file");1641			let src = Source::new_virtual("<test>".into(), code.clone().into());1642			let expr = crate::parse_jsonnet(&code, src.clone()).expect("parse");1643			let report = analyze_root(&expr, Vec::new());16441645			let diagnostics = render_diagnostics(src.code(), &report.diagnostics_list);1646			// Strip ANSI escapes from diagnostics so snapshots are readable.1647			let diagnostics = strip_ansi_escapes::strip_str(&diagnostics);1648			let rendered = format!(1649				"--- source ---\n{}\n--- root analysis ---\nobject_dependent_depth: {}\nlocal_dependent_depth: {}\nerrored: {}\n--- diagnostics ---\n{}--- lir ---\n{:#?}\n",1650				code.trim_end(),1651				fmt_depth(report.root_analysis.object_dependent_depth),1652				fmt_depth(report.root_analysis.local_dependent_depth),1653				report.errored,1654				diagnostics,1655				report.lir,1656			);1657			assert_snapshot!(rendered);1658		});1659	}16601661	fn fmt_depth(d: u32) -> String {1662		if d == u32::MAX {1663			"none".into()1664		} else {1665			d.to_string()1666		}1667	}1668}