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

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::error::{format_found, suggest_names};3233#[derive(Debug, Clone, Copy)]34#[must_use]35pub struct AnalysisResult {36	/// Highest object, on which identity the value is dependent. `u32::MAX` = not dependent at all37	pub object_dependent_depth: u32,38	/// Highest local frame, on which this value depends. `u32::MAX` = not dependent at all39	pub local_dependent_depth: u32,40}4142impl Default for AnalysisResult {43	fn default() -> Self {44		Self {45			object_dependent_depth: u32::MAX,46			local_dependent_depth: u32::MAX,47		}48	}49}5051impl AnalysisResult {52	fn depend_on_object(&mut self, depth: u32) {53		if depth < self.object_dependent_depth {54			self.object_dependent_depth = depth;55		}56	}57	fn depend_on_local(&mut self, depth: u32) {58		if depth < self.local_dependent_depth {59			self.local_dependent_depth = depth;60		}61	}62	fn taint_by(&mut self, other: AnalysisResult) {63		self.depend_on_object(other.object_dependent_depth);64		self.depend_on_local(other.local_dependent_depth);65	}66}6768#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Acyclic)]69pub struct LocalId(pub u32);7071impl LocalId {72	fn idx(self) -> usize {73		self.0 as usize74	}75	fn defined_before(self, other: Self) -> bool {76		self.0 < other.077	}78}7980#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Acyclic)]81pub enum LSlot {82	/// Enclosing frame locals (sibling letrec, params, etc.).83	Local(LocalSlot),84	/// Enclosing closure's capture pack.85	Capture(CaptureSlot),86}8788#[derive(Debug, Acyclic)]89pub struct ClosureShape {90	pub captures: Box<[LSlot]>,91	pub n_locals: u16,92}9394struct LocalDefinition {95	name: IStr,96	span: Option<Span>,97	/// At which frame depth this local was defined98	defined_at_depth: u32,99	/// Min frame depth, at which this local was used. `u32::MAX` = not used at all.100	/// This check won't catch unused argument closures, i.e:101	/// ```jsonnet102	/// local103	///     a = b,104	///     b = a,105	/// ; 2 + 2106	///107	/// ```108	/// Both `a` and `b` here are "used", but the whole closure was not used here.109	used_at_depth: u32,110	/// Used as part of the current frame closure111	used_by_sibling: bool,112	/// Analysys result for value of this local113	analysis: AnalysisResult,114	/// Has `analysis` been filled in?115	/// For sanity checking, locals are initialized in batchs, use `first_uninitialized_local`116	analyzed: bool,117	/// During walk over uninitialized vars, we can't refer to analysis results of other locals,118	/// but we need to. To make that work, for each variable in variable frame we capture its closure,119	/// by looking at referenced variables.120	scratch_referenced: bool,121}122123impl LocalDefinition {124	fn use_at(&mut self, depth: u32) {125		if depth == self.defined_at_depth {126			self.used_by_sibling = true;127			return;128		}129		if depth < self.used_at_depth {130			self.used_at_depth = depth;131		}132	}133}134135#[derive(Debug, Acyclic)]136pub enum LExpr {137	Slot(LSlot),138	Null,139	Bool(bool),140	Str(IStr),141	Num(NumValue),142	Arr {143		shape: ClosureShape,144		items: Rc<Vec<LExpr>>,145	},146	ArrComp(Box<LArrComp>),147	Obj(LObjBody),148	ObjExtend(Box<LExpr>, LObjBody),149	UnaryOp(UnaryOpType, Box<LExpr>),150	BinaryOp {151		lhs: Box<LExpr>,152		op: BinaryOpType,153		rhs: Box<LExpr>,154	},155	AssertExpr {156		assert: Rc<LAssertStmt>,157		rest: Box<LExpr>,158	},159	Error(Span, Box<LExpr>),160	LocalExpr(Box<LLocalExpr>),161	Import {162		kind: Spanned<ImportKind>,163		kind_span: Span,164		path: IStr,165	},166	Apply {167		applicable: Box<LExpr>,168		args: Spanned<LArgsDesc>,169		tailstrict: bool,170	},171	Index {172		indexable: Box<LExpr>,173		parts: Vec<LIndexPart>,174	},175	Function(Rc<LFunction>),176	IdentityFunction,177	IfElse {178		cond: Box<LExpr>,179		cond_then: Box<LExpr>,180		cond_else: Option<Box<LExpr>>,181	},182	Slice(Box<LSliceExpr>),183	Super,184185	/// Allows partial evaluation of broken expression tree,186	/// expressions with failed static analysis end up here187	BadLocal(&'static str),188}189190#[derive(Debug, Acyclic)]191pub struct LLocalExpr {192	pub frame_shape: ClosureShape,193	pub binds: Vec<LBind>,194	pub body: LExpr,195}196197#[derive(Debug, Acyclic)]198pub struct LFunction {199	pub name: Option<IStr>,200	pub params: Vec<LParam>,201	pub signature: FunctionSignature,202203	pub body_shape: ClosureShape,204	pub body: Rc<LExpr>,205}206207#[derive(Debug, Acyclic)]208pub struct LParam {209	pub name: Option<IStr>,210	pub destruct: LDestruct,211212	pub default: Option<(ClosureShape, Rc<LExpr>)>,213}214215#[derive(Debug, Acyclic)]216pub struct LBind {217	pub destruct: LDestruct,218	pub value_shape: ClosureShape,219	pub value: Rc<LExpr>,220}221222#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, Acyclic)]223pub struct CaptureSlot(pub(crate) u16);224#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq, Acyclic)]225pub struct LocalSlot(pub(crate) u16);226227#[derive(Debug, Acyclic)]228pub enum LDestruct {229	Full(LocalSlot),230	#[cfg(feature = "exp-destruct")]231	Skip,232	#[cfg(feature = "exp-destruct")]233	Array {234		start: Vec<LDestruct>,235		rest: Option<LDestructRest>,236		end: Vec<LDestruct>,237	},238	#[cfg(feature = "exp-destruct")]239	Object {240		fields: Vec<LDestructField>,241		rest: Option<LDestructRest>,242	},243}244245#[derive(Debug, Clone, Copy, Acyclic)]246pub enum LDestructRest {247	Keep(LocalSlot),248	Drop,249}250251#[derive(Debug, Acyclic)]252pub struct LDestructField {253	pub name: IStr,254	pub into: Option<LDestruct>,255	pub default: Option<(ClosureShape, Rc<LExpr>)>,256}257258impl LDestruct {259	pub fn each_slot<F: FnMut(LocalSlot)>(&self, f: &mut F) {260		match self {261			Self::Full(s) => f(*s),262			#[cfg(feature = "exp-destruct")]263			Self::Skip => {}264			#[cfg(feature = "exp-destruct")]265			Self::Array { start, rest, end } => {266				for d in start {267					d.each_slot(f);268				}269				if let Some(LDestructRest::Keep(s)) = rest {270					f(*s);271				}272				for d in end {273					d.each_slot(f);274				}275			}276			#[cfg(feature = "exp-destruct")]277			Self::Object { fields, rest } => {278				for field in fields {279					if let Some(into) = &field.into {280						into.each_slot(f);281					} else {282						unreachable!("shorthand object destruct must store `into`");283					}284				}285				if let Some(LDestructRest::Keep(s)) = rest {286					f(*s);287				}288			}289		}290	}291292	pub fn slots(&self) -> SmallVec<[LocalSlot; 1]> {293		let mut out = SmallVec::new();294		self.each_slot(&mut |s| out.push(s));295		out296	}297}298299#[derive(Debug, Acyclic)]300pub struct LSliceExpr {301	pub value: LExpr,302	pub start: Option<LExpr>,303	pub end: Option<LExpr>,304	pub step: Option<LExpr>,305}306307#[derive(Debug, Acyclic)]308pub struct LArgsDesc {309	pub unnamed: Vec<Rc<LExpr>>,310	pub names: Vec<IStr>,311	pub values: Vec<Rc<LExpr>>,312}313314#[derive(Debug, Acyclic)]315pub struct LAssertStmt {316	pub cond: Spanned<LExpr>,317	pub message: Option<LExpr>,318}319320#[derive(Debug, Acyclic)]321pub struct LIndexPart {322	pub span: Span,323	pub value: LExpr,324	#[cfg(feature = "exp-null-coaelse")]325	pub null_coaelse: bool,326}327328#[derive(Debug, Acyclic)]329pub enum LObjBody {330	MemberList(LObjMembers),331	ObjComp(Box<LObjComp>),332}333334#[derive(Debug, Acyclic)]335pub struct LObjMembers {336	pub frame_shape: ClosureShape,337	/// If current object identity (`super`/`this`/`$`) is used, `this` should338	/// be saved to the specified local slot.339	pub this: Option<LocalSlot>,340	/// Set if dollar should also be assigned to object identity, `this` should also be set (TODO: proper type-level validation)341	pub set_dollar: bool,342	/// True iff `super` is referenced by this object's members.343	pub uses_super: bool,344345	pub locals: Rc<Vec<LBind>>,346	pub asserts: Option<Rc<LObjAsserts>>,347	pub fields: Vec<LFieldMember>,348}349350#[derive(Debug, Acyclic)]351pub struct LObjComp {352	pub frame_shape: Rc<ClosureShape>,353	pub this: Option<LocalSlot>,354	pub set_dollar: bool,355	pub uses_super: bool,356357	pub locals: Rc<Vec<LBind>>,358	pub field: LFieldMember,359	pub compspecs: Vec<LCompSpec>,360}361362#[derive(Debug, Acyclic)]363pub struct LFieldMember {364	pub name: LFieldName,365	pub plus: bool,366	pub visibility: Visibility,367	pub value: Rc<(ClosureShape, LExpr)>,368}369370#[derive(Debug, Acyclic)]371pub struct LClosure<T: Acyclic> {372	pub shape: ClosureShape,373	pub value: T,374}375376#[derive(Debug, Acyclic)]377pub struct LObjAsserts {378	pub shape: ClosureShape,379	pub asserts: Vec<LAssertStmt>,380}381382#[derive(Debug, Acyclic)]383pub enum LFieldName {384	Fixed(IStr),385	Dyn(LExpr),386}387impl LFieldName {388	fn function_name(&self) -> Option<IStr> {389		match self {390			LFieldName::Fixed(istr) => Some(istr.clone()),391			LFieldName::Dyn(_) => None,392		}393	}394}395396#[derive(Debug, Acyclic)]397pub struct LArrComp {398	pub value_shape: ClosureShape,399	pub value: Rc<LExpr>,400	pub compspecs: Vec<LCompSpec>,401}402403#[derive(Debug, Acyclic)]404pub enum LCompSpec {405	If(LExpr),406	For {407		frame_shape: ClosureShape,408		destruct: LDestruct,409		over: LExpr,410		/// Is `over` does not depend on any variable introduced by an earlier for-spec in this comprehension chain411		loop_invariant: bool,412	},413	#[cfg(feature = "exp-object-iteration")]414	ForObj {415		frame_shape: ClosureShape,416		key: LocalSlot,417		visibility: jrsonnet_ir::Visibility,418		value: LDestruct,419		over: LExpr,420		loop_invariant: bool,421	},422}423424struct FrameAlloc<'s> {425	first_in_frame: LocalId,426	stack: &'s mut AnalysisStack,427	bomb: DropBomb,428}429impl<'s> FrameAlloc<'s> {430	fn new(stack: &'s mut AnalysisStack) -> Self {431		FrameAlloc {432			first_in_frame: stack.next_local_id(),433			stack,434			bomb: DropBomb::new("binding frame state"),435		}436	}437438	fn push_locals_closure(&mut self) -> ClosureOnStack {439		self.stack.push_closure_a(self.first_in_frame)440	}441442	fn define_local(&mut self, name: IStr, span: Option<Span>) -> Option<(LocalId, LocalSlot)> {443		let id = self.stack.next_local_id();444		let stack = self.stack.local_by_name.entry(name.clone()).or_default();445		if let Some(&existing) = stack.last()446			&& !existing.defined_before(self.first_in_frame)447		{448			self.stack.report_error(449				format!("local is already defined in the current frame: {name}"),450				span,451			);452			return None;453		}454		stack.push(id);455		self.stack.local_defs.push(LocalDefinition {456			name,457			span,458			defined_at_depth: self.stack.depth,459			used_at_depth: u32::MAX,460			used_by_sibling: false,461			analysis: AnalysisResult::default(),462			analyzed: false,463			scratch_referenced: false,464		});465		let def = self.stack.defining_closure_mut();466		Some((id, def.define_local(id)))467	}468	fn alloc_bind(&mut self, bind: &BindSpec) -> Option<LDestruct> {469		match bind {470			BindSpec::Field { into, .. } => self.alloc_destruct(into),471			BindSpec::Function { name, .. } => {472				let (_, id) = self.define_local(name.clone(), None)?;473				Some(LDestruct::Full(id))474			}475		}476	}477	fn alloc_destruct(&mut self, destruct: &Destruct) -> Option<LDestruct> {478		Some(match destruct {479			Destruct::Full(name) => {480				let (_, id) = self.define_local(name.value.clone(), Some(name.span.clone()))?;481				LDestruct::Full(id)482			}483			#[cfg(feature = "exp-destruct")]484			Destruct::Skip => LDestruct::Skip,485			#[cfg(feature = "exp-destruct")]486			Destruct::Array { start, rest, end } => {487				let start = start488					.iter()489					.map(|d| self.alloc_destruct(d))490					.collect::<Option<Vec<_>>>()?;491				let rest = match rest {492					Some(jrsonnet_ir::DestructRest::Keep(name)) => {493						let (_, id) = self.define_local(name.clone(), None)?;494						Some(LDestructRest::Keep(id))495					}496					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),497					None => None,498				};499				let end = end500					.iter()501					.map(|d| self.alloc_destruct(d))502					.collect::<Option<Vec<_>>>()?;503				LDestruct::Array { start, rest, end }504			}505			#[cfg(feature = "exp-destruct")]506			Destruct::Object { fields, rest } => {507				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());508				// Allocate destruct LocalIds, then analyse defaults509				for (name, into, _default) in fields {510					let into = if let Some(inner) = into {511						self.alloc_destruct(inner)?512					} else {513						let (_, id) = self.define_local(name.clone(), None)?;514						LDestruct::Full(id)515					};516					l_fields.push((name.clone(), into));517				}518				// All locals exist, so defaults can reference any sibling.519				let l_fields: Vec<LDestructField> = l_fields520					.into_iter()521					.zip(fields.iter())522					.map(|((name, into), (_n, _i, default))| {523						let default = match default {524							Some(e) => {525								let mut default_taint = AnalysisResult::default();526								Some(self.stack.in_using_closure(|stack| {527									Rc::new(analyze(&e.value, stack, &mut default_taint))528								}))529							}530							None => None,531						};532						LDestructField {533							name,534							into: Some(into),535							default,536						}537					})538					.collect();539				let rest = match rest {540					Some(jrsonnet_ir::DestructRest::Keep(name)) => {541						let (_, id) = self.define_local(name.clone(), None)?;542						Some(LDestructRest::Keep(id))543					}544					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),545					None => None,546				};547				LDestruct::Object {548					fields: l_fields,549					rest,550				}551			}552		})553	}554555	fn finish(self) -> PendingInit<'s> {556		let Self {557			first_in_frame,558			stack,559			bomb,560		} = self;561		let first_after_frame = stack.next_local_id();562		PendingInit {563			first_after_frame,564			stack,565			closures: Closures {566				referenced: vec![],567				spec_shapes: vec![],568				first_in_frame,569			},570			bomb,571		}572	}573}574575/// Frame state: `LocalIds` allocated, values not yet analysed.576struct PendingInit<'s> {577	first_after_frame: LocalId,578	stack: &'s mut AnalysisStack,579	closures: Closures,580	bomb: DropBomb,581}582583impl<'s> PendingInit<'s> {584	/// Record the analysis of a spec's value: stamp every id bound by the585	/// spec with `analysis`, collect the spec's same-frame references, and586	/// append them to `closures`.587	fn record_spec_init(&mut self, destruct: &LDestruct, analysis: AnalysisResult) {588		let mut refs: SmallVec<[LocalId; 4]> = SmallVec::new();589		for i in self.closures.first_in_frame.0..self.first_after_frame.0 {590			let def = &mut self.stack.local_defs[i as usize];591			if def.scratch_referenced {592				refs.push(LocalId(i));593				def.scratch_referenced = false;594			}595		}596597		let mut ids_count = 0;598		let first_local = self.stack.top_defining_local();599		destruct.each_slot(&mut |slot| {600			ids_count += 1;601			let id = LocalId(first_local.0 + u32::from(slot.0));602			let def = &mut self.stack.local_defs[id.idx()];603			debug_assert!(!def.analyzed, "sanity: local {:?} analysed twice", def.name);604			def.analysis = analysis;605			def.analyzed = true;606		});607		self.closures.push_spec(ids_count, &refs);608	}609	/// After all specs are analysed, propagate dependency information between610	/// siblings to a fix-point, then switch to "body" mode.611	fn finish(self) -> PendingBody<'s> {612		let Self {613			first_after_frame,614			closures,615			stack,616			bomb,617		} = self;618619		debug_assert_eq!(620			first_after_frame,621			stack.next_local_id(),622			"frame initialisation left unfinished locals"623		);624625		debug_assert_eq!(626			closures.spec_shapes.iter().map(|(_, d)| *d).sum::<usize>(),627			(first_after_frame.0 - closures.first_in_frame.0) as usize,628			"closures destruct-id counts must match frame local count"629		);630631		let mut changed = true;632		while changed {633			changed = false;634			for spec in closures.iter_specs() {635				for id_raw in spec.ids.clone() {636					let user = LocalId(id_raw);637					for &used in spec.references {638						changed |= stack.propagate_analysis(user, used);639					}640				}641			}642		}643644		stack.depth += 1;645		PendingBody {646			first_after_frame,647			closures,648			stack,649			bomb,650		}651	}652}653654/// Frame state: values analysed, body not yet walked.655struct PendingBody<'s> {656	first_after_frame: LocalId,657	closures: Closures,658	stack: &'s mut AnalysisStack,659	bomb: DropBomb,660}661impl<'s> PendingBody<'s> {662	/// After the body is processed, drop the frame's locals and emit any663	/// "unused local" warnings.664	fn finish(self) {665		let PendingBody {666			first_after_frame,667			closures,668			stack,669			mut bomb,670		} = self;671		bomb.defuse();672		stack.depth -= 1;673674		debug_assert_eq!(675			first_after_frame,676			stack.next_local_id(),677			"nested scopes must be popped before outer frames"678		);679680		let mut changed = true;681		while changed {682			changed = false;683			for spec in closures.iter_specs() {684				// Effective used_at_depth for the spec = min over its ids.685				let mut min_used_at = u32::MAX;686				for id_raw in spec.ids.clone() {687					min_used_at = min_used_at.min(stack.local_defs[id_raw as usize].used_at_depth);688				}689				if min_used_at == u32::MAX {690					continue;691				}692				for &used in spec.references {693					let used_def = &mut stack.local_defs[used.idx()];694					if min_used_at < used_def.used_at_depth {695						used_def.used_at_depth = min_used_at;696						changed = true;697					}698				}699			}700		}701702		let drained: Vec<LocalDefinition> = stack703			.local_defs704			.drain(closures.first_in_frame.idx()..)705			.collect();706		for (i, def) in drained.iter().enumerate().rev() {707			let id = LocalId(closures.first_in_frame.0 + i as u32);708			let stack_locals = stack709				.local_by_name710				.get_mut(&def.name)711				.expect("local must be in name map");712			let popped = stack_locals.pop().expect("name stack should not be empty");713			debug_assert_eq!(popped, id, "name stack integrity");714			if stack_locals.is_empty() {715				stack.local_by_name.remove(&def.name);716			}717718			if def.used_at_depth == u32::MAX {719				if def.used_by_sibling {720					stack.report_warning(721						format!("local is only referenced by unused siblings: {}", def.name),722						def.span.clone(),723					);724				} else {725					stack.report_warning(format!("unused local: {}", def.name), def.span.clone());726				}727			} else if def.analysis.local_dependent_depth > def.defined_at_depth728				&& def.analysis.object_dependent_depth > def.defined_at_depth729				&& def.defined_at_depth != 0730			{731				// The value doesn't depend on anything defined at or inside732				// this local's scope - can be hoisted, unfortunately not automatically.733				stack.report_warning(734					format!("local could be hoisted to an outer scope: {}", def.name),735					def.span.clone(),736				);737			}738		}739	}740}741742struct Closures {743	/// All the referenced locals, maybe repeated multiple times744	/// It is recorded as continous vec of sets, I.e we have745	/// a = 1, 2, 3746	/// b = 3, 4, 5, 6747	/// And in `referenced` we have `[ 1, 2, 3, 3, 4, 5, 6 ]`. To actually get, which closure refers to which element, see `spec_shapes`...748	/// Flat concatenation of sibling-local references across all specs.749	referenced: Vec<LocalId>,750	/// Amount of elements per closure, for the above case it is a = 3, b = 4, so here751	/// lies `[ 3, 4 ]`752	/// ~~closures: Vec<usize>,~~753	/// Finally, we have destructs.754	/// Because single destruct references single closure, but destructs to multiple locals, we have even more complicated structure.755	/// Luckly, every destruct is not interleaved with each other, so here we can have full list...756	/// 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 elements757	/// for each destruct starting from `first_destruct_local`758	/// ~~destructs: Vec<usize>,~~759	///760	/// => two of those fields were merged, as there is currently no per-destruct tracking of closures.761	/// For each spec in order: `(references_count, destruct_ids_count)`.762	/// `references_count` tells us how many entries of `referenced` belong763	/// to this spec; `destruct_ids_count` tells us how many `LocalIds` it764	/// binds.765	spec_shapes: Vec<(usize, usize)>,766	/// This is not a related doccomment, just a continuation of docs for previous fields.767	/// Having768	/// ```jsonnet769	/// local770	///     [a, b, c] = [d, e, f],771	///     [d, e, f] = [a, b, c, h],772	///     h = 1,773	/// ;774	/// ```775	///776	/// We have total of 7 locals777	/// First local here is `a` => `first_destruct_local` = `a`778	/// 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`779	/// [d, e, f] = [a, b, c, h], => `referenced += [a, b, c, h]`, `closures += 4`, `destructs += 3` (Note that this destruct will fail at runtime,780	///                                                                                               this thing should not care about that, it only captures what the value are referencing)781	/// h = 1 => referenced += [], closures += 0, destructs += 1782	/// And the result is783	///784	/// ```rust,ignore785	/// Closures {786	///     referenced: vec![d, e, f, a, b, c, h]787	///     spec_shapes: vec![(3, 3), (4, 3), (0, 1)],788	///     first_destruct_label: a,789	/// }790	/// ```791	///792	/// Reconstruction of that:793	///794	/// We know that we start with a795	/// We get the first number from destructs: `destructs.shift() == 3` => `destructs = [3, 1]`796	/// 3 elements counting from a => [a, b, c]797	/// Then we take first number from closures: `closures.shift() == 3` => `closures = [4, 0]`798	/// Then we take 3 items from referenced: `referenced.shift()x3 == d, e, f` => `referenced = [a, b, c, h]`799	///800	/// Thus we have [a, b, c] = [d, e, f]801	first_in_frame: LocalId,802}803804struct Closure<'a> {805	references: &'a [LocalId],806	ids: std::ops::Range<u32>,807}808809impl Closures {810	fn push_spec(&mut self, destruct_ids_count: usize, refs: &[LocalId]) {811		self.referenced.extend_from_slice(refs);812		self.spec_shapes.push((refs.len(), destruct_ids_count));813	}814815	fn iter_specs(&self) -> impl Iterator<Item = Closure<'_>> {816		let mut refs = self.referenced.as_slice();817		let mut next_id = self.first_in_frame.0;818		self.spec_shapes.iter().map(move |(refs_len, dest_count)| {819			let (this_refs, rest) = refs.split_at(*refs_len);820			refs = rest;821			let start = next_id;822			next_id += *dest_count as u32;823			Closure {824				references: this_refs,825				ids: start..next_id,826			}827		})828	}829}830831#[derive(Debug, Clone, Copy, PartialEq, Eq)]832pub enum DiagLevel {833	Error,834	Warning,835}836837#[derive(Debug, Clone, Acyclic)]838pub struct Diagnostic {839	pub level: DiagLevel,840	pub message: String,841	pub span: Option<Span>,842}843844struct DefiningClosure {845	first_local: LocalId,846	n_locals: u16,847}848849impl DefiningClosure {850	fn resolve(&self, target: LocalId) -> Option<LocalSlot> {851		let end = self.first_local.0 + u32::from(self.n_locals);852		if target.0 >= self.first_local.0 && target.0 < end {853			Some(LocalSlot(854				u16::try_from(target.0 - self.first_local.0).expect("local slots overflow"),855			))856		} else {857			None858		}859	}860	fn define_local(&mut self, local: LocalId) -> LocalSlot {861		let slot = self.n_locals;862		let id = self.first_local.0 + u32::from(slot);863		debug_assert_eq!(local.0, id);864		self.n_locals = self.n_locals.checked_add(1).expect("local slots overflow");865		LocalSlot(slot)866	}867}868869/// Per-closure capture computation state.870struct ClosureFrame {871	/// Closure may allocate locals872	defining: Option<DefiningClosure>,873	/// `LocalId` => capture index874	captures: FxHashMap<LocalId, CaptureSlot>,875	/// Capture sources in insertion order; consumed by `pop_closure_frame`.876	capture_sources: Vec<LSlot>,877}878879#[allow(clippy::struct_excessive_bools)]880pub struct AnalysisStack {881	local_defs: Vec<LocalDefinition>,882	/// Shadowing isn't used in jsonnet much, 2 because `SmallVec` allows to store 2 ptr-sized without overhead.883	/// TODO: Add test for this assumption (sizeof(SmallVec<[usize; 1]>) == sizeof(SmallVec<[usize; 2]>))884	local_by_name: FxHashMap<IStr, SmallVec<[LocalId; 2]>>,885886	/// Depth of the current locals frame.887	depth: u32,888	/// Last depth, at which object has appeared. `u32::MAX` = not appeared at all889	last_object_depth: u32,890	/// First depth, at which object has appeared. `u32::MAX` = not appeared at all891	/// $ refers to this object.892	first_object_depth: u32,893894	/// `LocalId` bound to the innermost object's `this`895	this_local: Option<LocalId>,896	/// Outermost object `this`, aka `$`897	dollar_alias: Option<LocalId>,898	/// True iff `self` has been referenced in the current object immediate members (not nested children).899	cur_self_used: bool,900	/// True iff `super` has been referenced in the current object immediate members.901	cur_super_used: bool,902	/// True iff `$` has been referenced anywhere since the outermost object's scope was entered.903	dollar_used: bool,904905	/// Stack of closure frames (innermost on top).906	closure_stack: Vec<ClosureFrame>,907908	diagnostics: Vec<Diagnostic>,909	/// Whenever analysis would be broken due to static analysis error.910	errored: bool,911}912913#[must_use]914struct ClosureOnStack {915	bomb: DropBomb,916}917918impl AnalysisStack {919	pub fn new() -> Self {920		Self {921			local_defs: Vec::new(),922			local_by_name: FxHashMap::default(),923			depth: 0,924			last_object_depth: u32::MAX,925			first_object_depth: u32::MAX,926			this_local: None,927			dollar_alias: None,928			cur_self_used: false,929			cur_super_used: false,930			dollar_used: false,931			closure_stack: Vec::new(),932			diagnostics: Vec::new(),933			errored: false,934		}935	}936937	fn push_root_closure(&mut self, externals: u16) -> ClosureOnStack {938		assert!(939			self.closure_stack.is_empty(),940			"root is only possible with empty stack"941		);942943		self.closure_stack.push(ClosureFrame {944			defining: Some(DefiningClosure {945				first_local: LocalId(0),946				n_locals: externals,947			}),948			captures: FxHashMap::default(),949			capture_sources: Vec::new(),950		});951952		ClosureOnStack {953			bomb: DropBomb::new("root closure"),954		}955	}956957	fn push_closure_a(&mut self, first_local: LocalId) -> ClosureOnStack {958		self.closure_stack.push(ClosureFrame {959			defining: Some(DefiningClosure {960				first_local,961				n_locals: 0,962			}),963			captures: FxHashMap::default(),964			capture_sources: Vec::new(),965		});966		ClosureOnStack {967			bomb: DropBomb::new("closure with locals"),968		}969	}970971	#[inline]972	fn in_using_closure<T>(973		&mut self,974		inner: impl FnOnce(&mut AnalysisStack) -> T,975	) -> (ClosureShape, T) {976		fn push_closure_b(stack: &mut AnalysisStack) -> ClosureOnStack {977			stack.closure_stack.push(ClosureFrame {978				defining: None,979				captures: FxHashMap::default(),980				capture_sources: Vec::new(),981			});982			ClosureOnStack {983				bomb: DropBomb::new("closure with locals"),984			}985		}986		let closure = push_closure_b(self);987		let v = inner(self);988		let shape = self.pop_closure(closure);989		(shape, v)990	}991992	fn pop_closure(&mut self, mut closure: ClosureOnStack) -> ClosureShape {993		closure.bomb.defuse();994		let frame = self.closure_stack.pop().expect("closure frame");995		ClosureShape {996			captures: frame.capture_sources.into_boxed_slice(),997			n_locals: frame.defining.map(|d| d.n_locals).unwrap_or_default(),998		}999	}10001001	/// Resolve a `LocalId` reference to an `LSlot` against the innermost1002	/// closure frame. May insert capture entries up the closure stack as1003	/// needed.1004	fn resolve_to_slot(&mut self, target: LocalId) -> LSlot {1005		let top = self.closure_stack.len();1006		debug_assert!(top > 0, "resolve_to_slot called with no closure frame");1007		Self::resolve_at(&mut self.closure_stack, top - 1, target)1008	}10091010	fn resolve_at(stack: &mut [ClosureFrame], idx: usize, target: LocalId) -> LSlot {1011		if let Some(def) = &stack[idx].defining {1012			if let Some(resolved) = def.resolve(target) {1013				return LSlot::Local(resolved);1014			}1015		} else {1016			// A sibling letrec slot must never be packed as a capture, or1017			// it would read an empty `OnceCell`.1018			for j in (0..idx).rev() {1019				if let Some(def) = &stack[j].defining {1020					if let Some(resolved) = def.resolve(target) {1021						return LSlot::Local(resolved);1022					}1023					break;1024				}1025			}1026		}1027		if let Some(&cap_idx) = stack[idx].captures.get(&target) {1028			return LSlot::Capture(cap_idx);1029		}1030		debug_assert!(idx > 0, "no enclosing closure frame for target {target:?}");1031		let parent_slot = Self::resolve_at(stack, idx - 1, target);1032		let frame = &mut stack[idx];1033		let cap_idx = CaptureSlot(1034			frame1035				.capture_sources1036				.len()1037				.try_into()1038				.expect("frame has more than u16::MAX captures"),1039		);1040		frame.capture_sources.push(parent_slot);1041		frame.captures.insert(target, cap_idx);1042		LSlot::Capture(cap_idx)1043	}10441045	fn next_local_id(&self) -> LocalId {1046		LocalId(self.local_defs.len() as u32)1047	}10481049	fn report_error(&mut self, msg: impl Into<String>, span: Option<Span>) {1050		self.errored = true;1051		self.diagnostics.push(Diagnostic {1052			level: DiagLevel::Error,1053			message: msg.into(),1054			span,1055		});1056	}1057	fn report_warning(&mut self, msg: impl Into<String>, span: Option<Span>) {1058		self.diagnostics.push(Diagnostic {1059			level: DiagLevel::Warning,1060			message: msg.into(),1061			span,1062		});1063	}10641065	fn use_local(&mut self, name: &IStr, span: Span, taint: &mut AnalysisResult) -> Option<LSlot> {1066		let Some(ids) = self.local_by_name.get(name) else {1067			let names = suggest_names(name, self.local_by_name.keys());1068			self.report_error(1069				format!("undefined local: {name}{}", format_found(&names, "local")),1070				Some(span),1071			);1072			return None;1073		};1074		let id = *ids.last().expect("empty stacks should be removed");1075		let depth = self.depth;1076		let def = &mut self.local_defs[id.idx()];1077		def.use_at(depth);1078		taint.depend_on_local(def.defined_at_depth);1079		if def.analyzed {1080			taint.taint_by(def.analysis);1081		} else {1082			def.scratch_referenced = true;1083		}1084		Some(self.resolve_to_slot(id))1085	}10861087	/// Assign name to the value provided externally, e.g `std`.1088	pub fn define_external_local(&mut self, name: IStr, id: LocalId) {1089		assert!(1090			self.local_defs.iter().all(|d| d.analyzed),1091			"external locals must be defined before the root expression is analysed"1092		);1093		assert_eq!(1094			id,1095			self.next_local_id(),1096			"external local id mismatch for {name} (externals must be defined in allocation order)"1097		);1098		self.local_defs.push(LocalDefinition {1099			name: name.clone(),1100			span: None,1101			defined_at_depth: 0,1102			used_at_depth: u32::MAX,1103			used_by_sibling: false,1104			analysis: AnalysisResult::default(),1105			analyzed: true,1106			scratch_referenced: false,1107		});1108		self.local_by_name.entry(name).or_default().push(id);1109	}11101111	fn defining_closure_mut(&mut self) -> &mut DefiningClosure {1112		self.closure_stack1113			.iter_mut()1114			.rev()1115			.find_map(|c| c.defining.as_mut())1116			.expect("no enclosing defining closure frame")1117	}1118	fn defining_closure(&self) -> &DefiningClosure {1119		self.closure_stack1120			.iter()1121			.rev()1122			.find_map(|c| c.defining.as_ref())1123			.expect("no enclosing defining closure frame")1124	}1125}11261127impl Default for AnalysisStack {1128	fn default() -> Self {1129		Self::new()1130	}1131}11321133impl AnalysisStack {1134	fn top_defining_local(&self) -> LocalId {1135		self.defining_closure().first_local1136	}11371138	/// Merge `used`'s analysis into `user`'s analysis and record that `user`1139	/// transitively depends on `used` (same-frame sibling reference).1140	/// Returns `true` if `user`'s analysis changed.1141	fn propagate_analysis(&mut self, user: LocalId, used: LocalId) -> bool {1142		let (used_analysis, used_defined_at_depth) = {1143			let u = &self.local_defs[used.idx()];1144			(u.analysis, u.defined_at_depth)1145		};1146		let user_def = &mut self.local_defs[user.idx()];1147		let before_obj = user_def.analysis.object_dependent_depth;1148		let before_loc = user_def.analysis.local_dependent_depth;1149		user_def.analysis.taint_by(used_analysis);1150		user_def.analysis.depend_on_local(used_defined_at_depth);1151		before_obj != user_def.analysis.object_dependent_depth1152			|| before_loc != user_def.analysis.local_dependent_depth1153	}1154}11551156mod names {1157	use crate::names;11581159	names! {1160		this: "this",1161	}1162}11631164// Object scope helpers1165impl AnalysisStack {1166	#[inline]1167	fn in_object_scope<T>(1168		&mut self,1169		inner: impl FnOnce(&mut AnalysisStack) -> T,1170	) -> (ObjectUsage, ClosureShape, T) {1171		fn enter_object_scope(stack: &mut AnalysisStack) -> ObjectScope {1172			let is_outermost = stack.first_object_depth == u32::MAX;1173			let this_id = stack.next_local_id();1174			let closure = stack.push_closure_a(this_id);1175			let pushed = stack.push_pseudo_local(names::this());1176			debug_assert_eq!(pushed, this_id, "this pseudo-local id");1177			let scope = ObjectScope {1178				this_id,1179				is_outermost,1180				prev_this_local: stack.this_local,1181				prev_dollar_alias: stack.dollar_alias,1182				prev_cur_self_used: stack.cur_self_used,1183				prev_cur_super_used: stack.cur_super_used,1184				prev_dollar_used: is_outermost.then_some(stack.dollar_used),1185				prev_last_object: stack.last_object_depth,1186				prev_first_object: stack.first_object_depth,1187				closure,1188			};11891190			stack.this_local = Some(scope.this_id);1191			if is_outermost {1192				stack.dollar_alias = Some(scope.this_id);1193				stack.first_object_depth = stack.depth;1194				stack.dollar_used = false;1195			}1196			stack.last_object_depth = stack.depth;1197			stack.cur_self_used = false;1198			stack.cur_super_used = false;1199			scope1200		}12011202		fn leave_object_scope(1203			stack: &mut AnalysisStack,1204			scope: ObjectScope,1205		) -> (ObjectUsage, ClosureShape) {1206			let ObjectScope {1207				this_id,1208				is_outermost,1209				prev_this_local,1210				prev_dollar_alias,1211				prev_cur_self_used,1212				prev_cur_super_used,1213				prev_dollar_used,1214				prev_last_object,1215				prev_first_object,1216				closure,1217			} = scope;1218			let _ = stack.local_defs.pop().expect("this pseudo-local exists");1219			debug_assert_eq!(stack.local_defs.len(), this_id.0 as usize);12201221			let set_dollar = is_outermost && stack.dollar_used;1222			let usage = ObjectUsage {1223				this_used: stack.cur_self_used || stack.cur_super_used || set_dollar,1224				uses_super: stack.cur_super_used,1225				set_dollar,1226			};12271228			stack.this_local = prev_this_local;1229			stack.dollar_alias = prev_dollar_alias;1230			stack.cur_self_used = prev_cur_self_used;1231			stack.cur_super_used = prev_cur_super_used;1232			if let Some(prev) = prev_dollar_used {1233				stack.dollar_used = prev;1234			}1235			stack.last_object_depth = prev_last_object;1236			stack.first_object_depth = prev_first_object;12371238			let frame_shape = stack.pop_closure(closure);1239			(usage, frame_shape)1240		}1241		let scope = enter_object_scope(self);1242		let v = inner(self);1243		let (usage, shape) = leave_object_scope(self, scope);1244		(usage, shape, v)1245	}12461247	fn push_pseudo_local(&mut self, name: IStr) -> LocalId {1248		let id = self.next_local_id();1249		self.local_defs.push(LocalDefinition {1250			name,1251			span: None,1252			defined_at_depth: self.depth,1253			used_at_depth: u32::MAX,1254			used_by_sibling: false,1255			analysis: AnalysisResult::default(),1256			analyzed: true,1257			scratch_referenced: false,1258		});1259		{1260			let def = self.defining_closure_mut();1261			let _ = def.define_local(id);1262		}1263		id1264	}12651266	fn use_this(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1267		let id = self.this_local?;1268		self.cur_self_used = true;1269		self.use_pseudo_local(id, taint);1270		Some(self.resolve_to_slot(id))1271	}12721273	fn use_super(&mut self, taint: &mut AnalysisResult) -> Option<()> {1274		let id = self.this_local?;1275		self.cur_super_used = true;1276		self.use_pseudo_local(id, taint);1277		Some(())1278	}12791280	fn use_dollar(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1281		let id = self.dollar_alias?;1282		self.dollar_used = true;1283		self.use_pseudo_local(id, taint);1284		Some(self.resolve_to_slot(id))1285	}12861287	// TODO: Dedicated type for object references instead of "pseudo local" BS, idk1288	fn use_pseudo_local(&mut self, id: LocalId, taint: &mut AnalysisResult) {1289		let depth = self.depth;1290		let def = &mut self.local_defs[id.idx()];1291		def.use_at(depth);1292		taint.depend_on_local(def.defined_at_depth);1293		taint.depend_on_object(def.defined_at_depth);1294	}1295}12961297#[must_use]1298struct ObjectScope {1299	this_id: LocalId,1300	is_outermost: bool,1301	prev_this_local: Option<LocalId>,1302	prev_dollar_alias: Option<LocalId>,1303	prev_cur_self_used: bool,1304	prev_cur_super_used: bool,1305	prev_dollar_used: Option<bool>,1306	prev_last_object: u32,1307	prev_first_object: u32,1308	closure: ClosureOnStack,1309}13101311struct ObjectUsage {1312	this_used: bool,1313	uses_super: bool,1314	set_dollar: bool,1315}13161317fn analyze_assert(1318	stmt: &AssertStmt,1319	stack: &mut AnalysisStack,1320	taint: &mut AnalysisResult,1321) -> LAssertStmt {1322	let cond = analyze(&stmt.assertion.value, stack, taint);1323	let message = stmt.message.as_ref().map(|m| analyze(m, stack, taint));1324	LAssertStmt {1325		cond: Spanned::new(cond, stmt.assertion.span.clone()),1326		message,1327	}1328}13291330#[allow(clippy::too_many_lines)]1331pub fn analyze_named(1332	name: IStr,1333	expr: &Expr,1334	stack: &mut AnalysisStack,1335	taint: &mut AnalysisResult,1336) -> LExpr {1337	if let Expr::Function(params, body) = expr {1338		return analyze_function(Some(name), params, body, stack, taint);1339	}1340	analyze(expr, stack, taint)1341}1342#[allow(clippy::too_many_lines)]1343pub fn analyze(expr: &Expr, stack: &mut AnalysisStack, taint: &mut AnalysisResult) -> LExpr {1344	match expr {1345		Expr::Literal(l) => match l {1346			LiteralType::This => stack.use_this(taint).map_or_else(1347				|| {1348					stack.report_error("`self` used outside of object", None);1349					LExpr::BadLocal("self")1350				},1351				LExpr::Slot,1352			),1353			LiteralType::Super => {1354				if stack.use_super(taint).is_some() {1355					LExpr::Super1356				} else {1357					stack.report_error("`super` used outside of object", None);1358					LExpr::BadLocal("super")1359				}1360			}1361			LiteralType::Dollar => stack.use_dollar(taint).map_or_else(1362				|| {1363					stack.report_error("`$` used outside of object", None);1364					LExpr::BadLocal("$")1365				},1366				LExpr::Slot,1367			),1368			LiteralType::Null => LExpr::Null,1369			LiteralType::True => LExpr::Bool(true),1370			LiteralType::False => LExpr::Bool(false),1371		},1372		Expr::Str(s) => LExpr::Str(s.clone()),1373		Expr::Num(n) => LExpr::Num(*n),1374		Expr::Var(v) => stack1375			.use_local(&v.value, v.span.clone(), taint)1376			.map_or_else(|| LExpr::BadLocal("ref"), LExpr::Slot),1377		Expr::Arr(a) => {1378			let (shape, items) = stack1379				.in_using_closure(|stack| a.iter().map(|v| analyze(v, stack, taint)).collect());1380			LExpr::Arr {1381				shape,1382				items: Rc::new(items),1383			}1384		}1385		Expr::ArrComp(inner, comp) => analyze_arr_comp(inner, comp, stack, taint),1386		Expr::Obj(obj) => LExpr::Obj(analyze_obj_body(obj, stack, taint)),1387		Expr::ObjExtend(base, obj) => LExpr::ObjExtend(1388			Box::new(analyze(base, stack, taint)),1389			analyze_obj_body(obj, stack, taint),1390		),1391		Expr::UnaryOp(op, value) => LExpr::UnaryOp(*op, Box::new(analyze(value, stack, taint))),1392		Expr::BinaryOp(op) => {1393			let BinaryOp {1394				lhs,1395				op: optype,1396				rhs,1397			} = &**op;1398			LExpr::BinaryOp {1399				lhs: Box::new(analyze(lhs, stack, taint)),1400				op: *optype,1401				rhs: Box::new(analyze(rhs, stack, taint)),1402			}1403		}1404		Expr::AssertExpr(assert) => {1405			let AssertExpr { assert, rest } = &**assert;1406			let assert = Rc::new(analyze_assert(assert, stack, taint));1407			let rest = Box::new(analyze(rest, stack, taint));1408			LExpr::AssertExpr { assert, rest }1409		}1410		Expr::LocalExpr(binds, body) => analyze_local_expr(binds, body, stack, taint),1411		Expr::Import(kind, path_expr) => {1412			let Expr::Str(path) = &**path_expr else {1413				stack.report_error(1414					"import path must be a string literal",1415					Some(kind.span.clone()),1416				);1417				return LExpr::BadLocal("bad import");1418			};1419			LExpr::Import {1420				kind: kind.clone(),1421				kind_span: kind.span.clone(),1422				path: path.clone(),1423			}1424		}1425		Expr::ErrorStmt(span, inner) => {1426			LExpr::Error(span.clone(), Box::new(analyze(inner, stack, taint)))1427		}1428		Expr::Apply(applicable, args, tailstrict) => {1429			let app = analyze(applicable, stack, taint);1430			let ArgsDesc {1431				unnamed,1432				names,1433				values,1434			} = &args.value;1435			let unnamed_l = unnamed1436				.iter()1437				.map(|a| Rc::new(analyze(a, stack, taint)))1438				.collect();1439			let values_l = values1440				.iter()1441				.map(|a| Rc::new(analyze(a, stack, taint)))1442				.collect();1443			LExpr::Apply {1444				applicable: Box::new(app),1445				args: Spanned::new(1446					LArgsDesc {1447						unnamed: unnamed_l,1448						names: names.clone(),1449						values: values_l,1450					},1451					args.span.clone(),1452				),1453				tailstrict: *tailstrict,1454			}1455		}1456		Expr::Index { indexable, parts } => {1457			let idx = analyze(indexable, stack, taint);1458			let parts_l = parts1459				.iter()1460				.map(|p| {1461					let value = analyze(&p.value, stack, taint);1462					LIndexPart {1463						span: p.span.clone(),1464						value,1465						#[cfg(feature = "exp-null-coaelse")]1466						null_coaelse: p.null_coaelse,1467					}1468				})1469				.collect();1470			LExpr::Index {1471				indexable: Box::new(idx),1472				parts: parts_l,1473			}1474		}1475		Expr::Function(params, body) => analyze_function(None, params, body, stack, taint),1476		Expr::IfElse(ifelse) => {1477			let IfElse {1478				cond,1479				cond_then,1480				cond_else,1481			} = &**ifelse;1482			let cond_l = analyze(&cond.cond, stack, taint);1483			let then_l = analyze(cond_then, stack, taint);1484			let else_l = cond_else1485				.as_ref()1486				.map(|e| Box::new(analyze(e, stack, taint)));1487			LExpr::IfElse {1488				cond: Box::new(cond_l),1489				cond_then: Box::new(then_l),1490				cond_else: else_l,1491			}1492		}1493		Expr::Slice(slice) => {1494			let Slice {1495				value,1496				slice: SliceDesc { start, end, step },1497			} = &**slice;1498			let value_l = analyze(value, stack, taint);1499			let start_l = start.as_ref().map(|e| analyze(&e.value, stack, taint));1500			let end_l = end.as_ref().map(|e| analyze(&e.value, stack, taint));1501			let step_l = step.as_ref().map(|e| analyze(&e.value, stack, taint));1502			LExpr::Slice(Box::new(LSliceExpr {1503				value: value_l,1504				start: start_l,1505				end: end_l,1506				step: step_l,1507			}))1508		}1509	}1510}15111512fn analyze_local_expr(1513	binds: &[BindSpec],1514	body: &Expr,1515	stack: &mut AnalysisStack,1516	taint: &mut AnalysisResult,1517) -> LExpr {1518	if binds.is_empty() {1519		return analyze(body, stack, taint);1520	}1521	let frame_start = stack.next_local_id();1522	let closure = stack.push_closure_a(frame_start);1523	let (l_binds, body_expr) = process_local_frame(binds, stack, taint, |stack, taint| {1524		analyze(body, stack, taint)1525	});1526	let frame_shape = stack.pop_closure(closure);1527	LExpr::LocalExpr(Box::new(LLocalExpr {1528		frame_shape,1529		binds: l_binds,1530		body: body_expr,1531	}))1532}15331534fn analyze_bind_value(1535	bind: &BindSpec,1536	stack: &mut AnalysisStack,1537	taint: &mut AnalysisResult,1538) -> LExpr {1539	match bind {1540		BindSpec::Field {1541			value: Expr::Function(params, value),1542			into: Destruct::Full(name),1543		} => analyze_function(Some(name.value.clone()), params, value, stack, taint),1544		BindSpec::Field { value, .. } => analyze(value, stack, taint),1545		BindSpec::Function {1546			params,1547			value,1548			name,1549		} => analyze_function(Some(name.clone()), params, value, stack, taint),1550	}1551}15521553fn process_local_frame<R>(1554	binds: &[BindSpec],1555	stack: &mut AnalysisStack,1556	taint: &mut AnalysisResult,1557	body_fn: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1558) -> (Vec<LBind>, R) {1559	let mut alloc = FrameAlloc::new(stack);15601561	let mut destructs: Vec<Option<LDestruct>> = Vec::with_capacity(binds.len());1562	for bind in binds {1563		destructs.push(alloc.alloc_bind(bind));1564	}1565	let mut pending = alloc.finish();15661567	let mut l_binds: Vec<LBind> = Vec::with_capacity(binds.len());1568	for (bind, destruct) in binds.iter().zip(destructs.into_iter()) {1569		let mut value_taint = AnalysisResult::default();1570		let (value_shape, value) = pending1571			.stack1572			.in_using_closure(|stack| analyze_bind_value(bind, stack, &mut value_taint));1573		taint.taint_by(value_taint);1574		if let Some(destruct) = destruct {1575			pending.record_spec_init(&destruct, value_taint);1576			l_binds.push(LBind {1577				destruct,1578				value_shape,1579				value: Rc::new(value),1580			});1581		} else {1582			pending.closures.push_spec(0, &[]);1583		}1584	}15851586	let body_frame = pending.finish();1587	let result = body_fn(body_frame.stack, taint);1588	body_frame.finish();15891590	(l_binds, result)1591}15921593fn analyze_function(1594	name: Option<IStr>,1595	params: &ExprParams,1596	body: &Expr,1597	stack: &mut AnalysisStack,1598	taint: &mut AnalysisResult,1599) -> LExpr {1600	let mut alloc = FrameAlloc::new(stack);1601	let closure = alloc.push_locals_closure();16021603	let mut param_destructs: Vec<Option<LDestruct>> = Vec::with_capacity(params.exprs.len());1604	for p in &params.exprs {1605		param_destructs.push(alloc.alloc_destruct(&p.destruct));1606	}16071608	let mut pending = alloc.finish();16091610	let mut l_params: Vec<LParam> = Vec::with_capacity(params.exprs.len());1611	for (p, destruct) in params.exprs.iter().zip(param_destructs.into_iter()) {1612		let mut value_taint = AnalysisResult::default();1613		let default = p.default.as_ref().map_or_else(1614			|| None,1615			|d| {1616				Some(1617					pending1618						.stack1619						.in_using_closure(|stack| Rc::new(analyze(d, stack, &mut value_taint))),1620				)1621			},1622		);1623		taint.taint_by(value_taint);1624		if let Some(destruct) = destruct {1625			let name = match &p.destruct {1626				Destruct::Full(n) => Some(n.value.clone()),1627				#[cfg(feature = "exp-destruct")]1628				_ => None,1629			};1630			pending.record_spec_init(&destruct, value_taint);1631			l_params.push(LParam {1632				name,1633				destruct,1634				default,1635			});1636		} else {1637			pending.closures.push_spec(0, &[]);1638		}1639	}16401641	let body_frame = pending.finish();1642	let body_expr = analyze(body, body_frame.stack, taint);1643	body_frame.finish();1644	let body_shape = stack.pop_closure(closure);16451646	// function(x) x is an identity function1647	if l_params.len() == 1 && l_params[0].default.is_none() {1648		stack.report_warning(1649			"do not define identity functions manually, use std.id instead",1650			None,1651		);1652		#[allow(irrefutable_let_patterns, reason = "refutable with exp-destruct")]1653		if let LDestruct::Full(param_slot) = &l_params[0].destruct1654			&& let LExpr::Slot(LSlot::Local(s)) = &body_expr1655			&& s == param_slot1656		{1657			return LExpr::IdentityFunction {};1658		}1659	}16601661	LExpr::Function(Rc::new(LFunction {1662		name,1663		params: l_params,1664		signature: params.signature.clone(),1665		body_shape,1666		body: Rc::new(body_expr),1667	}))1668}16691670fn analyze_obj_body(1671	obj: &ObjBody,1672	stack: &mut AnalysisStack,1673	taint: &mut AnalysisResult,1674) -> LObjBody {1675	match obj {1676		ObjBody::MemberList(members) => {1677			LObjBody::MemberList(analyze_obj_members(members, stack, taint))1678		}1679		ObjBody::ObjComp(comp) => LObjBody::ObjComp(Box::new(analyze_obj_comp(comp, stack, taint))),1680	}1681}16821683fn analyze_obj_members(1684	members: &ObjMembers,1685	stack: &mut AnalysisStack,1686	taint: &mut AnalysisResult,1687) -> LObjMembers {1688	let ObjMembers {1689		locals,1690		asserts,1691		fields,1692	} = members;16931694	// Names are analyzed in enclosing scope, they can't depend on locals or self/super1695	let field_names: Vec<LFieldName> = fields1696		.iter()1697		.map(|f| match &f.name.value {1698			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1699			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1700		})1701		.collect();17021703	let (usage, frame_shape, (l_binds, (l_asserts_opt, l_fields))) =1704		stack.in_object_scope(|stack| {1705			process_local_frame(locals, stack, taint, |stack, taint| {1706				let l_asserts_opt = if asserts.is_empty() {1707					None1708				} else {1709					let (shape, l_asserts) = stack.in_using_closure(|stack| {1710						let mut l_asserts = Vec::with_capacity(asserts.len());1711						for a in asserts {1712							let mut assert_taint = AnalysisResult::default();1713							l_asserts.push(analyze_assert(a, stack, &mut assert_taint));1714							taint.taint_by(assert_taint);1715						}1716						l_asserts1717					});1718					Some(Rc::new(LObjAsserts {1719						shape,1720						asserts: l_asserts,1721					}))1722				};1723				let mut l_fields = Vec::with_capacity(fields.len());1724				for (f, name) in fields.iter().zip(field_names) {1725					let value = stack.in_using_closure(|stack| {1726						if let Some(params) = &f.params {1727							analyze_function(name.function_name(), params, &f.value, stack, taint)1728						} else {1729							analyze(&f.value, stack, taint)1730						}1731					});1732					l_fields.push(LFieldMember {1733						name,1734						plus: f.plus,1735						visibility: f.visibility,1736						value: Rc::new(value),1737					});1738				}1739				(l_asserts_opt, l_fields)1740			})1741		});1742	// `this` was allocated as the first local of the object's frame,1743	// so its slot is 0 within that frame.1744	let this_slot = usage.this_used.then_some(LocalSlot(0));1745	LObjMembers {1746		frame_shape,1747		this: this_slot,1748		set_dollar: usage.set_dollar,1749		uses_super: usage.uses_super,1750		locals: Rc::new(l_binds),1751		asserts: l_asserts_opt,1752		fields: l_fields,1753	}1754}17551756fn analyze_obj_comp(1757	comp: &ObjComp,1758	stack: &mut AnalysisStack,1759	taint: &mut AnalysisResult,1760) -> LObjComp {1761	let res = analyze_comp_specs(&comp.compspecs, stack, taint, |stack, taint| {1762		let field_name = match &comp.field.name.value {1763			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1764			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1765		};17661767		let (usage, frame_shape, body) = stack.in_object_scope(|stack| {1768			process_local_frame(&comp.locals, stack, taint, |stack, taint| {1769				let value = stack.in_using_closure(|stack| {1770					if let Some(params) = &comp.field.params {1771						analyze_function(None, params, &comp.field.value, stack, taint)1772					} else {1773						analyze(&comp.field.value, stack, taint)1774					}1775				});1776				LFieldMember {1777					name: field_name,1778					plus: comp.field.plus,1779					visibility: comp.field.visibility,1780					value: Rc::new(value),1781				}1782			})1783		});1784		(usage, frame_shape, body)1785	});1786	let (usage, frame_shape, (locals, field)) = res.inner;1787	let this_slot = usage.this_used.then_some(LocalSlot(0));1788	LObjComp {1789		frame_shape: Rc::new(frame_shape),1790		this: this_slot,1791		set_dollar: usage.set_dollar,1792		uses_super: usage.uses_super,1793		locals: Rc::new(locals),1794		field,1795		compspecs: res.compspecs,1796	}1797}17981799fn analyze_arr_comp(1800	inner: &Expr,1801	specs: &[CompSpec],1802	stack: &mut AnalysisStack,1803	taint: &mut AnalysisResult,1804) -> LExpr {1805	let res = analyze_comp_specs(specs, stack, taint, |stack, taint| {1806		stack.in_using_closure(|stack| analyze(inner, stack, taint))1807	});1808	let (value_shape, value) = res.inner;1809	LExpr::ArrComp(Box::new(LArrComp {1810		value_shape,1811		value: Rc::new(value),1812		compspecs: res.compspecs,1813	}))1814}18151816fn analyze_comp_specs<R>(1817	specs: &[CompSpec],1818	stack: &mut AnalysisStack,1819	taint: &mut AnalysisResult,1820	inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1821) -> CompSpecResult<R> {1822	fn go<R>(1823		idx: usize,1824		specs: &[CompSpec],1825		outer_depth: u32,1826		stack: &mut AnalysisStack,1827		taint: &mut AnalysisResult,1828		inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1829	) -> (R, Vec<LCompSpec>) {1830		if idx >= specs.len() {1831			return (inside(stack, taint), Vec::new());1832		}1833		match &specs[idx] {1834			CompSpec::IfSpec(IfSpecData { cond, .. }) => {1835				let cond_l = analyze(cond, stack, taint);1836				let (r, mut rest) = go(idx + 1, specs, outer_depth, stack, taint, inside);1837				rest.insert(0, LCompSpec::If(cond_l));1838				(r, rest)1839			}1840			CompSpec::ForSpec(ForSpecData { destruct, over }) => {1841				let mut over_taint = AnalysisResult::default();1842				let over_l = analyze(over, stack, &mut over_taint);1843				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1844				taint.taint_by(over_taint);18451846				let mut alloc = FrameAlloc::new(stack);1847				let closure = alloc.push_locals_closure();1848				let Some(l_destruct) = alloc.alloc_destruct(destruct) else {1849					stack.pop_closure(closure);1850					return go(idx + 1, specs, outer_depth, stack, taint, inside);1851				};1852				let mut pending = alloc.finish();18531854				let var_analysis = AnalysisResult::default();1855				pending.record_spec_init(&l_destruct, var_analysis);18561857				let body_frame = pending.finish();1858				let (r, mut rest) =1859					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);1860				body_frame.finish();1861				let frame_shape = stack.pop_closure(closure);18621863				rest.insert(1864					0,1865					LCompSpec::For {1866						frame_shape,1867						destruct: l_destruct,1868						over: over_l,1869						loop_invariant,1870					},1871				);1872				(r, rest)1873			}1874			#[cfg(feature = "exp-object-iteration")]1875			CompSpec::ForObjSpec(data) => {1876				let mut over_taint = AnalysisResult::default();1877				let over_l = analyze(&data.over, stack, &mut over_taint);1878				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1879				taint.taint_by(over_taint);18801881				let mut alloc = FrameAlloc::new(stack);1882				let closure = alloc.push_locals_closure();1883				let Some((_, key_slot)) = alloc.define_local(data.key.clone(), None) else {1884					stack.pop_closure(closure);1885					return go(idx + 1, specs, outer_depth, stack, taint, inside);1886				};1887				let Some(l_value) = alloc.alloc_destruct(&data.value) else {1888					stack.pop_closure(closure);1889					return go(idx + 1, specs, outer_depth, stack, taint, inside);1890				};1891				let mut pending = alloc.finish();18921893				let var_analysis = AnalysisResult::default();1894				pending.record_spec_init(&LDestruct::Full(key_slot), var_analysis);1895				pending.record_spec_init(&l_value, var_analysis);18961897				let body_frame = pending.finish();1898				let (r, mut rest) =1899					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);1900				body_frame.finish();1901				let frame_shape = stack.pop_closure(closure);19021903				rest.insert(1904					0,1905					LCompSpec::ForObj {1906						frame_shape,1907						key: key_slot,1908						visibility: data.visibility,1909						value: l_value,1910						over: over_l,1911						loop_invariant,1912					},1913				);1914				(r, rest)1915			}1916		}1917	}1918	let outer_depth = stack.depth;1919	let (r, compspecs) = go(0, specs, outer_depth, stack, taint, inside);1920	CompSpecResult {1921		inner: r,1922		compspecs,1923	}1924}19251926struct CompSpecResult<R> {1927	inner: R,1928	compspecs: Vec<LCompSpec>,1929}19301931pub fn analyze_root(expr: &Expr, ctx: Vec<(IStr, LocalId)>) -> AnalysisReport {1932	let mut stack = AnalysisStack::new();1933	for (name, id) in ctx {1934		stack.define_external_local(name, id);1935	}19361937	let externals_count: u16 = stack1938		.local_defs1939		.len()1940		.try_into()1941		.expect("more than u16::MAX externals");1942	let closure = stack.push_root_closure(externals_count);19431944	let mut taint = AnalysisResult::default();1945	let lir = analyze(expr, &mut stack, &mut taint);19461947	let root_shape = stack.pop_closure(closure);1948	debug_assert!(1949		stack.closure_stack.is_empty(),1950		"closure stack imbalance after analyze"1951	);19521953	AnalysisReport {1954		lir,1955		root_shape,1956		root_analysis: taint,1957		diagnostics_list: stack.diagnostics,1958		errored: stack.errored,1959	}1960}19611962pub struct AnalysisReport {1963	pub lir: LExpr,1964	pub root_shape: ClosureShape,1965	pub root_analysis: AnalysisResult,1966	pub diagnostics_list: Vec<Diagnostic>,1967	pub errored: bool,1968}19691970#[cfg(test)]1971mod tests {1972	#[test]1973	#[cfg(not(feature = "exp-null-coaelse"))]1974	fn snapshots() {1975		use std::fs;19761977		use insta::{assert_snapshot, glob};1978		use jrsonnet_ir::Source;19791980		use super::*;19811982		fn render_diagnostics(src: &str, diags: &[Diagnostic]) -> String {1983			use std::fmt::Write;19841985			use hi_doc::{Formatting, SnippetBuilder, Text};19861987			let mut out = String::new();1988			let mut unspanned = Vec::new();1989			let mut spanned: Vec<&Diagnostic> = Vec::new();1990			for d in diags {1991				if d.span.is_some() {1992					spanned.push(d);1993				} else {1994					unspanned.push(d);1995				}1996			}1997			if !spanned.is_empty() {1998				let mut builder = SnippetBuilder::new(src);1999				for d in spanned {2000					let span = d.span.as_ref().expect("spanned");2001					let ab = match d.level {2002						DiagLevel::Error => {2003							builder.error(Text::fragment(d.message.clone(), Formatting::default()))2004						}2005						DiagLevel::Warning => builder2006							.warning(Text::fragment(d.message.clone(), Formatting::default())),2007					};2008					ab.range(span.range()).build();2009				}2010				out.push_str(&hi_doc::source_to_ansi(&builder.build()));2011			}2012			for d in unspanned {2013				let prefix = match d.level {2014					DiagLevel::Error => "error",2015					DiagLevel::Warning => "warning",2016				};2017				writeln!(out, "{prefix}: {}", d.message).expect("fmt");2018			}2019			out2020		}2021		fn fmt_depth(d: u32) -> String {2022			if d == u32::MAX {2023				"none".into()2024			} else {2025				d.to_string()2026			}2027		}20282029		glob!("analysis_tests/*.jsonnet", |path| {2030			let code = fs::read_to_string(path).expect("read test file");2031			let src = Source::new_virtual("<test>".into(), code.clone().into());2032			let expr = crate::parse_jsonnet(&code, src.clone()).expect("parse");2033			let report = analyze_root(&expr, Vec::new());20342035			let diagnostics = render_diagnostics(src.code(), &report.diagnostics_list);2036			// Strip ANSI escapes from diagnostics so snapshots are readable.2037			let diagnostics = strip_ansi_escapes::strip_str(&diagnostics);2038			let rendered = format!(2039				"--- source ---\n{}\n--- root analysis ---\nobject_dependent_depth: {}\nlocal_dependent_depth: {}\nerrored: {}\n--- diagnostics ---\n{}--- lir ---\n{:#?}\n",2040				code.trim_end(),2041				fmt_depth(report.root_analysis.object_dependent_depth),2042				fmt_depth(report.root_analysis.local_dependent_depth),2043				report.errored,2044				diagnostics,2045				report.lir,2046			);2047			assert_snapshot!(rendered);2048		});2049	}2050}