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

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}414415struct FrameAlloc<'s> {416	first_in_frame: LocalId,417	stack: &'s mut AnalysisStack,418	bomb: DropBomb,419}420impl<'s> FrameAlloc<'s> {421	fn new(stack: &'s mut AnalysisStack) -> Self {422		FrameAlloc {423			first_in_frame: stack.next_local_id(),424			stack,425			bomb: DropBomb::new("binding frame state"),426		}427	}428429	fn push_locals_closure(&mut self) -> ClosureOnStack {430		self.stack.push_closure_a(self.first_in_frame)431	}432433	fn define_local(&mut self, name: IStr, span: Option<Span>) -> Option<(LocalId, LocalSlot)> {434		let id = self.stack.next_local_id();435		let stack = self.stack.local_by_name.entry(name.clone()).or_default();436		if let Some(&existing) = stack.last()437			&& !existing.defined_before(self.first_in_frame)438		{439			self.stack.report_error(440				format!("local is already defined in the current frame: {name}"),441				span,442			);443			return None;444		}445		stack.push(id);446		self.stack.local_defs.push(LocalDefinition {447			name,448			span,449			defined_at_depth: self.stack.depth,450			used_at_depth: u32::MAX,451			used_by_sibling: false,452			analysis: AnalysisResult::default(),453			analyzed: false,454			scratch_referenced: false,455		});456		let def = self.stack.defining_closure_mut();457		Some((id, def.define_local(id)))458	}459	fn alloc_bind(&mut self, bind: &BindSpec) -> Option<LDestruct> {460		match bind {461			BindSpec::Field { into, .. } => self.alloc_destruct(into),462			BindSpec::Function { name, .. } => {463				let (_, id) = self.define_local(name.clone(), None)?;464				Some(LDestruct::Full(id))465			}466		}467	}468	fn alloc_destruct(&mut self, destruct: &Destruct) -> Option<LDestruct> {469		Some(match destruct {470			Destruct::Full(name) => {471				let (_, id) = self.define_local(name.value.clone(), Some(name.span.clone()))?;472				LDestruct::Full(id)473			}474			#[cfg(feature = "exp-destruct")]475			Destruct::Skip => LDestruct::Skip,476			#[cfg(feature = "exp-destruct")]477			Destruct::Array { start, rest, end } => {478				let start = start479					.iter()480					.map(|d| self.alloc_destruct(d))481					.collect::<Option<Vec<_>>>()?;482				let rest = match rest {483					Some(jrsonnet_ir::DestructRest::Keep(name)) => {484						let (_, id) = self.define_local(name.clone(), None)?;485						Some(LDestructRest::Keep(id))486					}487					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),488					None => None,489				};490				let end = end491					.iter()492					.map(|d| self.alloc_destruct(d))493					.collect::<Option<Vec<_>>>()?;494				LDestruct::Array { start, rest, end }495			}496			#[cfg(feature = "exp-destruct")]497			Destruct::Object { fields, rest } => {498				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());499				// Allocate destruct LocalIds, then analyse defaults500				for (name, into, _default) in fields {501					let into = if let Some(inner) = into {502						self.alloc_destruct(inner)?503					} else {504						let (_, id) = self.define_local(name.clone(), None)?;505						LDestruct::Full(id)506					};507					l_fields.push((name.clone(), into));508				}509				// All locals exist, so defaults can reference any sibling.510				let l_fields: Vec<LDestructField> = l_fields511					.into_iter()512					.zip(fields.iter())513					.map(|((name, into), (_n, _i, default))| {514						let default = match default {515							Some(e) => {516								let mut default_taint = AnalysisResult::default();517								Some(self.stack.in_using_closure(|stack| {518									Rc::new(analyze(&e.value, stack, &mut default_taint))519								}))520							}521							None => None,522						};523						LDestructField {524							name,525							into: Some(into),526							default,527						}528					})529					.collect();530				let rest = match rest {531					Some(jrsonnet_ir::DestructRest::Keep(name)) => {532						let (_, id) = self.define_local(name.clone(), None)?;533						Some(LDestructRest::Keep(id))534					}535					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),536					None => None,537				};538				LDestruct::Object {539					fields: l_fields,540					rest,541				}542			}543		})544	}545546	fn finish(self) -> PendingInit<'s> {547		let Self {548			first_in_frame,549			stack,550			bomb,551		} = self;552		let first_after_frame = stack.next_local_id();553		PendingInit {554			first_after_frame,555			stack,556			closures: Closures {557				referenced: vec![],558				spec_shapes: vec![],559				first_in_frame,560			},561			bomb,562		}563	}564}565566/// Frame state: `LocalIds` allocated, values not yet analysed.567struct PendingInit<'s> {568	first_after_frame: LocalId,569	stack: &'s mut AnalysisStack,570	closures: Closures,571	bomb: DropBomb,572}573574impl<'s> PendingInit<'s> {575	/// Record the analysis of a spec's value: stamp every id bound by the576	/// spec with `analysis`, collect the spec's same-frame references, and577	/// append them to `closures`.578	fn record_spec_init(&mut self, destruct: &LDestruct, analysis: AnalysisResult) {579		let mut refs: SmallVec<[LocalId; 4]> = SmallVec::new();580		for i in self.closures.first_in_frame.0..self.first_after_frame.0 {581			let def = &mut self.stack.local_defs[i as usize];582			if def.scratch_referenced {583				refs.push(LocalId(i));584				def.scratch_referenced = false;585			}586		}587588		let mut ids_count = 0;589		let first_local = self.stack.top_defining_local();590		destruct.each_slot(&mut |slot| {591			ids_count += 1;592			let id = LocalId(first_local.0 + u32::from(slot.0));593			let def = &mut self.stack.local_defs[id.idx()];594			debug_assert!(!def.analyzed, "sanity: local {:?} analysed twice", def.name);595			def.analysis = analysis;596			def.analyzed = true;597		});598		self.closures.push_spec(ids_count, &refs);599	}600	/// After all specs are analysed, propagate dependency information between601	/// siblings to a fix-point, then switch to "body" mode.602	fn finish(self) -> PendingBody<'s> {603		let Self {604			first_after_frame,605			closures,606			stack,607			bomb,608		} = self;609610		debug_assert_eq!(611			first_after_frame,612			stack.next_local_id(),613			"frame initialisation left unfinished locals"614		);615616		debug_assert_eq!(617			closures.spec_shapes.iter().map(|(_, d)| *d).sum::<usize>(),618			(first_after_frame.0 - closures.first_in_frame.0) as usize,619			"closures destruct-id counts must match frame local count"620		);621622		let mut changed = true;623		while changed {624			changed = false;625			for spec in closures.iter_specs() {626				for id_raw in spec.ids.clone() {627					let user = LocalId(id_raw);628					for &used in spec.references {629						changed |= stack.propagate_analysis(user, used);630					}631				}632			}633		}634635		stack.depth += 1;636		PendingBody {637			first_after_frame,638			closures,639			stack,640			bomb,641		}642	}643}644645/// Frame state: values analysed, body not yet walked.646struct PendingBody<'s> {647	first_after_frame: LocalId,648	closures: Closures,649	stack: &'s mut AnalysisStack,650	bomb: DropBomb,651}652impl<'s> PendingBody<'s> {653	/// After the body is processed, drop the frame's locals and emit any654	/// "unused local" warnings.655	fn finish(self) {656		let PendingBody {657			first_after_frame,658			closures,659			stack,660			mut bomb,661		} = self;662		bomb.defuse();663		stack.depth -= 1;664665		debug_assert_eq!(666			first_after_frame,667			stack.next_local_id(),668			"nested scopes must be popped before outer frames"669		);670671		let mut changed = true;672		while changed {673			changed = false;674			for spec in closures.iter_specs() {675				// Effective used_at_depth for the spec = min over its ids.676				let mut min_used_at = u32::MAX;677				for id_raw in spec.ids.clone() {678					min_used_at = min_used_at.min(stack.local_defs[id_raw as usize].used_at_depth);679				}680				if min_used_at == u32::MAX {681					continue;682				}683				for &used in spec.references {684					let used_def = &mut stack.local_defs[used.idx()];685					if min_used_at < used_def.used_at_depth {686						used_def.used_at_depth = min_used_at;687						changed = true;688					}689				}690			}691		}692693		let drained: Vec<LocalDefinition> = stack694			.local_defs695			.drain(closures.first_in_frame.idx()..)696			.collect();697		for (i, def) in drained.iter().enumerate().rev() {698			let id = LocalId(closures.first_in_frame.0 + i as u32);699			let stack_locals = stack700				.local_by_name701				.get_mut(&def.name)702				.expect("local must be in name map");703			let popped = stack_locals.pop().expect("name stack should not be empty");704			debug_assert_eq!(popped, id, "name stack integrity");705			if stack_locals.is_empty() {706				stack.local_by_name.remove(&def.name);707			}708709			if def.used_at_depth == u32::MAX {710				if def.used_by_sibling {711					stack.report_warning(712						format!("local is only referenced by unused siblings: {}", def.name),713						def.span.clone(),714					);715				} else {716					stack.report_warning(format!("unused local: {}", def.name), def.span.clone());717				}718			} else if def.analysis.local_dependent_depth > def.defined_at_depth719				&& def.analysis.object_dependent_depth > def.defined_at_depth720				&& def.defined_at_depth != 0721			{722				// The value doesn't depend on anything defined at or inside723				// this local's scope - can be hoisted, unfortunately not automatically.724				stack.report_warning(725					format!("local could be hoisted to an outer scope: {}", def.name),726					def.span.clone(),727				);728			}729		}730	}731}732733struct Closures {734	/// All the referenced locals, maybe repeated multiple times735	/// It is recorded as continous vec of sets, I.e we have736	/// a = 1, 2, 3737	/// b = 3, 4, 5, 6738	/// And in `referenced` we have `[ 1, 2, 3, 3, 4, 5, 6 ]`. To actually get, which closure refers to which element, see `spec_shapes`...739	/// Flat concatenation of sibling-local references across all specs.740	referenced: Vec<LocalId>,741	/// Amount of elements per closure, for the above case it is a = 3, b = 4, so here742	/// lies `[ 3, 4 ]`743	/// ~~closures: Vec<usize>,~~744	/// Finally, we have destructs.745	/// Because single destruct references single closure, but destructs to multiple locals, we have even more complicated structure.746	/// Luckly, every destruct is not interleaved with each other, so here we can have full list...747	/// 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 elements748	/// for each destruct starting from `first_destruct_local`749	/// ~~destructs: Vec<usize>,~~750	///751	/// => two of those fields were merged, as there is currently no per-destruct tracking of closures.752	/// For each spec in order: `(references_count, destruct_ids_count)`.753	/// `references_count` tells us how many entries of `referenced` belong754	/// to this spec; `destruct_ids_count` tells us how many `LocalIds` it755	/// binds.756	spec_shapes: Vec<(usize, usize)>,757	/// This is not a related doccomment, just a continuation of docs for previous fields.758	/// Having759	/// ```jsonnet760	/// local761	///     [a, b, c] = [d, e, f],762	///     [d, e, f] = [a, b, c, h],763	///     h = 1,764	/// ;765	/// ```766	///767	/// We have total of 7 locals768	/// First local here is `a` => `first_destruct_local` = `a`769	/// 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`770	/// [d, e, f] = [a, b, c, h], => `referenced += [a, b, c, h]`, `closures += 4`, `destructs += 3` (Note that this destruct will fail at runtime,771	///                                                                                               this thing should not care about that, it only captures what the value are referencing)772	/// h = 1 => referenced += [], closures += 0, destructs += 1773	/// And the result is774	///775	/// ```rust,ignore776	/// Closures {777	///     referenced: vec![d, e, f, a, b, c, h]778	///     spec_shapes: vec![(3, 3), (4, 3), (0, 1)],779	///     first_destruct_label: a,780	/// }781	/// ```782	///783	/// Reconstruction of that:784	///785	/// We know that we start with a786	/// We get the first number from destructs: `destructs.shift() == 3` => `destructs = [3, 1]`787	/// 3 elements counting from a => [a, b, c]788	/// Then we take first number from closures: `closures.shift() == 3` => `closures = [4, 0]`789	/// Then we take 3 items from referenced: `referenced.shift()x3 == d, e, f` => `referenced = [a, b, c, h]`790	///791	/// Thus we have [a, b, c] = [d, e, f]792	first_in_frame: LocalId,793}794795struct Closure<'a> {796	references: &'a [LocalId],797	ids: std::ops::Range<u32>,798}799800impl Closures {801	fn push_spec(&mut self, destruct_ids_count: usize, refs: &[LocalId]) {802		self.referenced.extend_from_slice(refs);803		self.spec_shapes.push((refs.len(), destruct_ids_count));804	}805806	fn iter_specs(&self) -> impl Iterator<Item = Closure<'_>> {807		let mut refs = self.referenced.as_slice();808		let mut next_id = self.first_in_frame.0;809		self.spec_shapes.iter().map(move |(refs_len, dest_count)| {810			let (this_refs, rest) = refs.split_at(*refs_len);811			refs = rest;812			let start = next_id;813			next_id += *dest_count as u32;814			Closure {815				references: this_refs,816				ids: start..next_id,817			}818		})819	}820}821822#[derive(Debug, Clone, Copy, PartialEq, Eq)]823pub enum DiagLevel {824	Error,825	Warning,826}827828#[derive(Debug, Clone, Acyclic)]829pub struct Diagnostic {830	pub level: DiagLevel,831	pub message: String,832	pub span: Option<Span>,833}834835struct DefiningClosure {836	first_local: LocalId,837	n_locals: u16,838}839840impl DefiningClosure {841	fn resolve(&self, target: LocalId) -> Option<LocalSlot> {842		let end = self.first_local.0 + u32::from(self.n_locals);843		if target.0 >= self.first_local.0 && target.0 < end {844			Some(LocalSlot(845				u16::try_from(target.0 - self.first_local.0).expect("local slots overflow"),846			))847		} else {848			None849		}850	}851	fn define_local(&mut self, local: LocalId) -> LocalSlot {852		let slot = self.n_locals;853		let id = self.first_local.0 + u32::from(slot);854		debug_assert_eq!(local.0, id);855		self.n_locals = self.n_locals.checked_add(1).expect("local slots overflow");856		LocalSlot(slot)857	}858}859860/// Per-closure capture computation state.861struct ClosureFrame {862	/// Closure may allocate locals863	defining: Option<DefiningClosure>,864	/// `LocalId` => capture index865	captures: FxHashMap<LocalId, CaptureSlot>,866	/// Capture sources in insertion order; consumed by `pop_closure_frame`.867	capture_sources: Vec<LSlot>,868}869870#[allow(clippy::struct_excessive_bools)]871pub struct AnalysisStack {872	local_defs: Vec<LocalDefinition>,873	/// Shadowing isn't used in jsonnet much, 2 because `SmallVec` allows to store 2 ptr-sized without overhead.874	/// TODO: Add test for this assumption (sizeof(SmallVec<[usize; 1]>) == sizeof(SmallVec<[usize; 2]>))875	local_by_name: FxHashMap<IStr, SmallVec<[LocalId; 2]>>,876877	/// Depth of the current locals frame.878	depth: u32,879	/// Last depth, at which object has appeared. `u32::MAX` = not appeared at all880	last_object_depth: u32,881	/// First depth, at which object has appeared. `u32::MAX` = not appeared at all882	/// $ refers to this object.883	first_object_depth: u32,884885	/// `LocalId` bound to the innermost object's `this`886	this_local: Option<LocalId>,887	/// Outermost object `this`, aka `$`888	dollar_alias: Option<LocalId>,889	/// True iff `self` has been referenced in the current object immediate members (not nested children).890	cur_self_used: bool,891	/// True iff `super` has been referenced in the current object immediate members.892	cur_super_used: bool,893	/// True iff `$` has been referenced anywhere since the outermost object's scope was entered.894	dollar_used: bool,895896	/// Stack of closure frames (innermost on top).897	closure_stack: Vec<ClosureFrame>,898899	diagnostics: Vec<Diagnostic>,900	/// Whenever analysis would be broken due to static analysis error.901	errored: bool,902}903904#[must_use]905struct ClosureOnStack {906	bomb: DropBomb,907}908909impl AnalysisStack {910	pub fn new() -> Self {911		Self {912			local_defs: Vec::new(),913			local_by_name: FxHashMap::default(),914			depth: 0,915			last_object_depth: u32::MAX,916			first_object_depth: u32::MAX,917			this_local: None,918			dollar_alias: None,919			cur_self_used: false,920			cur_super_used: false,921			dollar_used: false,922			closure_stack: Vec::new(),923			diagnostics: Vec::new(),924			errored: false,925		}926	}927928	fn push_root_closure(&mut self, externals: u16) -> ClosureOnStack {929		assert!(930			self.closure_stack.is_empty(),931			"root is only possible with empty stack"932		);933934		self.closure_stack.push(ClosureFrame {935			defining: Some(DefiningClosure {936				first_local: LocalId(0),937				n_locals: externals,938			}),939			captures: FxHashMap::default(),940			capture_sources: Vec::new(),941		});942943		ClosureOnStack {944			bomb: DropBomb::new("root closure"),945		}946	}947948	fn push_closure_a(&mut self, first_local: LocalId) -> ClosureOnStack {949		self.closure_stack.push(ClosureFrame {950			defining: Some(DefiningClosure {951				first_local,952				n_locals: 0,953			}),954			captures: FxHashMap::default(),955			capture_sources: Vec::new(),956		});957		ClosureOnStack {958			bomb: DropBomb::new("closure with locals"),959		}960	}961962	#[inline]963	fn in_using_closure<T>(964		&mut self,965		inner: impl FnOnce(&mut AnalysisStack) -> T,966	) -> (ClosureShape, T) {967		fn push_closure_b(stack: &mut AnalysisStack) -> ClosureOnStack {968			stack.closure_stack.push(ClosureFrame {969				defining: None,970				captures: FxHashMap::default(),971				capture_sources: Vec::new(),972			});973			ClosureOnStack {974				bomb: DropBomb::new("closure with locals"),975			}976		}977		let closure = push_closure_b(self);978		let v = inner(self);979		let shape = self.pop_closure(closure);980		(shape, v)981	}982983	fn pop_closure(&mut self, mut closure: ClosureOnStack) -> ClosureShape {984		closure.bomb.defuse();985		let frame = self.closure_stack.pop().expect("closure frame");986		ClosureShape {987			captures: frame.capture_sources.into_boxed_slice(),988			n_locals: frame.defining.map(|d| d.n_locals).unwrap_or_default(),989		}990	}991992	/// Resolve a `LocalId` reference to an `LSlot` against the innermost993	/// closure frame. May insert capture entries up the closure stack as994	/// needed.995	fn resolve_to_slot(&mut self, target: LocalId) -> LSlot {996		let top = self.closure_stack.len();997		debug_assert!(top > 0, "resolve_to_slot called with no closure frame");998		Self::resolve_at(&mut self.closure_stack, top - 1, target)999	}10001001	fn resolve_at(stack: &mut [ClosureFrame], idx: usize, target: LocalId) -> LSlot {1002		if let Some(def) = &stack[idx].defining {1003			if let Some(resolved) = def.resolve(target) {1004				return LSlot::Local(resolved);1005			}1006		} else {1007			// A sibling letrec slot must never be packed as a capture, or1008			// it would read an empty `OnceCell`.1009			for j in (0..idx).rev() {1010				if let Some(def) = &stack[j].defining {1011					if let Some(resolved) = def.resolve(target) {1012						return LSlot::Local(resolved);1013					}1014					break;1015				}1016			}1017		}1018		if let Some(&cap_idx) = stack[idx].captures.get(&target) {1019			return LSlot::Capture(cap_idx);1020		}1021		debug_assert!(idx > 0, "no enclosing closure frame for target {target:?}");1022		let parent_slot = Self::resolve_at(stack, idx - 1, target);1023		let frame = &mut stack[idx];1024		let cap_idx = CaptureSlot(1025			frame1026				.capture_sources1027				.len()1028				.try_into()1029				.expect("frame has more than u16::MAX captures"),1030		);1031		frame.capture_sources.push(parent_slot);1032		frame.captures.insert(target, cap_idx);1033		LSlot::Capture(cap_idx)1034	}10351036	fn next_local_id(&self) -> LocalId {1037		LocalId(self.local_defs.len() as u32)1038	}10391040	fn report_error(&mut self, msg: impl Into<String>, span: Option<Span>) {1041		self.errored = true;1042		self.diagnostics.push(Diagnostic {1043			level: DiagLevel::Error,1044			message: msg.into(),1045			span,1046		});1047	}1048	fn report_warning(&mut self, msg: impl Into<String>, span: Option<Span>) {1049		self.diagnostics.push(Diagnostic {1050			level: DiagLevel::Warning,1051			message: msg.into(),1052			span,1053		});1054	}10551056	fn use_local(&mut self, name: &IStr, span: Span, taint: &mut AnalysisResult) -> Option<LSlot> {1057		let Some(ids) = self.local_by_name.get(name) else {1058			let names = suggest_names(name, self.local_by_name.keys());1059			self.report_error(1060				format!("undefined local: {name}{}", format_found(&names, "local")),1061				Some(span),1062			);1063			return None;1064		};1065		let id = *ids.last().expect("empty stacks should be removed");1066		let depth = self.depth;1067		let def = &mut self.local_defs[id.idx()];1068		def.use_at(depth);1069		taint.depend_on_local(def.defined_at_depth);1070		if def.analyzed {1071			taint.taint_by(def.analysis);1072		} else {1073			def.scratch_referenced = true;1074		}1075		Some(self.resolve_to_slot(id))1076	}10771078	/// Assign name to the value provided externally, e.g `std`.1079	pub fn define_external_local(&mut self, name: IStr, id: LocalId) {1080		assert!(1081			self.local_defs.iter().all(|d| d.analyzed),1082			"external locals must be defined before the root expression is analysed"1083		);1084		assert_eq!(1085			id,1086			self.next_local_id(),1087			"external local id mismatch for {name} (externals must be defined in allocation order)"1088		);1089		self.local_defs.push(LocalDefinition {1090			name: name.clone(),1091			span: None,1092			defined_at_depth: 0,1093			used_at_depth: u32::MAX,1094			used_by_sibling: false,1095			analysis: AnalysisResult::default(),1096			analyzed: true,1097			scratch_referenced: false,1098		});1099		self.local_by_name.entry(name).or_default().push(id);1100	}11011102	fn defining_closure_mut(&mut self) -> &mut DefiningClosure {1103		self.closure_stack1104			.iter_mut()1105			.rev()1106			.find_map(|c| c.defining.as_mut())1107			.expect("no enclosing defining closure frame")1108	}1109	fn defining_closure(&self) -> &DefiningClosure {1110		self.closure_stack1111			.iter()1112			.rev()1113			.find_map(|c| c.defining.as_ref())1114			.expect("no enclosing defining closure frame")1115	}1116}11171118impl Default for AnalysisStack {1119	fn default() -> Self {1120		Self::new()1121	}1122}11231124impl AnalysisStack {1125	fn top_defining_local(&self) -> LocalId {1126		self.defining_closure().first_local1127	}11281129	/// Merge `used`'s analysis into `user`'s analysis and record that `user`1130	/// transitively depends on `used` (same-frame sibling reference).1131	/// Returns `true` if `user`'s analysis changed.1132	fn propagate_analysis(&mut self, user: LocalId, used: LocalId) -> bool {1133		let (used_analysis, used_defined_at_depth) = {1134			let u = &self.local_defs[used.idx()];1135			(u.analysis, u.defined_at_depth)1136		};1137		let user_def = &mut self.local_defs[user.idx()];1138		let before_obj = user_def.analysis.object_dependent_depth;1139		let before_loc = user_def.analysis.local_dependent_depth;1140		user_def.analysis.taint_by(used_analysis);1141		user_def.analysis.depend_on_local(used_defined_at_depth);1142		before_obj != user_def.analysis.object_dependent_depth1143			|| before_loc != user_def.analysis.local_dependent_depth1144	}1145}11461147mod names {1148	use crate::names;11491150	names! {1151		this: "this",1152	}1153}11541155// Object scope helpers1156impl AnalysisStack {1157	#[inline]1158	fn in_object_scope<T>(1159		&mut self,1160		inner: impl FnOnce(&mut AnalysisStack) -> T,1161	) -> (ObjectUsage, ClosureShape, T) {1162		fn enter_object_scope(stack: &mut AnalysisStack) -> ObjectScope {1163			let is_outermost = stack.first_object_depth == u32::MAX;1164			let this_id = stack.next_local_id();1165			let closure = stack.push_closure_a(this_id);1166			let pushed = stack.push_pseudo_local(names::this());1167			debug_assert_eq!(pushed, this_id, "this pseudo-local id");1168			let scope = ObjectScope {1169				this_id,1170				is_outermost,1171				prev_this_local: stack.this_local,1172				prev_dollar_alias: stack.dollar_alias,1173				prev_cur_self_used: stack.cur_self_used,1174				prev_cur_super_used: stack.cur_super_used,1175				prev_dollar_used: is_outermost.then_some(stack.dollar_used),1176				prev_last_object: stack.last_object_depth,1177				prev_first_object: stack.first_object_depth,1178				closure,1179			};11801181			stack.this_local = Some(scope.this_id);1182			if is_outermost {1183				stack.dollar_alias = Some(scope.this_id);1184				stack.first_object_depth = stack.depth;1185				stack.dollar_used = false;1186			}1187			stack.last_object_depth = stack.depth;1188			stack.cur_self_used = false;1189			stack.cur_super_used = false;1190			scope1191		}11921193		fn leave_object_scope(1194			stack: &mut AnalysisStack,1195			scope: ObjectScope,1196		) -> (ObjectUsage, ClosureShape) {1197			let ObjectScope {1198				this_id,1199				is_outermost,1200				prev_this_local,1201				prev_dollar_alias,1202				prev_cur_self_used,1203				prev_cur_super_used,1204				prev_dollar_used,1205				prev_last_object,1206				prev_first_object,1207				closure,1208			} = scope;1209			let _ = stack.local_defs.pop().expect("this pseudo-local exists");1210			debug_assert_eq!(stack.local_defs.len(), this_id.0 as usize);12111212			let set_dollar = is_outermost && stack.dollar_used;1213			let usage = ObjectUsage {1214				this_used: stack.cur_self_used || stack.cur_super_used || set_dollar,1215				uses_super: stack.cur_super_used,1216				set_dollar,1217			};12181219			stack.this_local = prev_this_local;1220			stack.dollar_alias = prev_dollar_alias;1221			stack.cur_self_used = prev_cur_self_used;1222			stack.cur_super_used = prev_cur_super_used;1223			if let Some(prev) = prev_dollar_used {1224				stack.dollar_used = prev;1225			}1226			stack.last_object_depth = prev_last_object;1227			stack.first_object_depth = prev_first_object;12281229			let frame_shape = stack.pop_closure(closure);1230			(usage, frame_shape)1231		}1232		let scope = enter_object_scope(self);1233		let v = inner(self);1234		let (usage, shape) = leave_object_scope(self, scope);1235		(usage, shape, v)1236	}12371238	fn push_pseudo_local(&mut self, name: IStr) -> LocalId {1239		let id = self.next_local_id();1240		self.local_defs.push(LocalDefinition {1241			name,1242			span: None,1243			defined_at_depth: self.depth,1244			used_at_depth: u32::MAX,1245			used_by_sibling: false,1246			analysis: AnalysisResult::default(),1247			analyzed: true,1248			scratch_referenced: false,1249		});1250		{1251			let def = self.defining_closure_mut();1252			let _ = def.define_local(id);1253		}1254		id1255	}12561257	fn use_this(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1258		let id = self.this_local?;1259		self.cur_self_used = true;1260		self.use_pseudo_local(id, taint);1261		Some(self.resolve_to_slot(id))1262	}12631264	fn use_super(&mut self, taint: &mut AnalysisResult) -> Option<()> {1265		let id = self.this_local?;1266		self.cur_super_used = true;1267		self.use_pseudo_local(id, taint);1268		Some(())1269	}12701271	fn use_dollar(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {1272		let id = self.dollar_alias?;1273		self.dollar_used = true;1274		self.use_pseudo_local(id, taint);1275		Some(self.resolve_to_slot(id))1276	}12771278	// TODO: Dedicated type for object references instead of "pseudo local" BS, idk1279	fn use_pseudo_local(&mut self, id: LocalId, taint: &mut AnalysisResult) {1280		let depth = self.depth;1281		let def = &mut self.local_defs[id.idx()];1282		def.use_at(depth);1283		taint.depend_on_local(def.defined_at_depth);1284		taint.depend_on_object(def.defined_at_depth);1285	}1286}12871288#[must_use]1289struct ObjectScope {1290	this_id: LocalId,1291	is_outermost: bool,1292	prev_this_local: Option<LocalId>,1293	prev_dollar_alias: Option<LocalId>,1294	prev_cur_self_used: bool,1295	prev_cur_super_used: bool,1296	prev_dollar_used: Option<bool>,1297	prev_last_object: u32,1298	prev_first_object: u32,1299	closure: ClosureOnStack,1300}13011302struct ObjectUsage {1303	this_used: bool,1304	uses_super: bool,1305	set_dollar: bool,1306}13071308fn analyze_assert(1309	stmt: &AssertStmt,1310	stack: &mut AnalysisStack,1311	taint: &mut AnalysisResult,1312) -> LAssertStmt {1313	let cond = analyze(&stmt.assertion.value, stack, taint);1314	let message = stmt.message.as_ref().map(|m| analyze(m, stack, taint));1315	LAssertStmt {1316		cond: Spanned::new(cond, stmt.assertion.span.clone()),1317		message,1318	}1319}13201321#[allow(clippy::too_many_lines)]1322pub fn analyze_named(1323	name: IStr,1324	expr: &Expr,1325	stack: &mut AnalysisStack,1326	taint: &mut AnalysisResult,1327) -> LExpr {1328	if let Expr::Function(params, body) = expr {1329		return analyze_function(Some(name), params, body, stack, taint);1330	}1331	analyze(expr, stack, taint)1332}1333#[allow(clippy::too_many_lines)]1334pub fn analyze(expr: &Expr, stack: &mut AnalysisStack, taint: &mut AnalysisResult) -> LExpr {1335	match expr {1336		Expr::Literal(l) => match l {1337			LiteralType::This => stack.use_this(taint).map_or_else(1338				|| {1339					stack.report_error("`self` used outside of object", None);1340					LExpr::BadLocal("self")1341				},1342				LExpr::Slot,1343			),1344			LiteralType::Super => {1345				if stack.use_super(taint).is_some() {1346					LExpr::Super1347				} else {1348					stack.report_error("`super` used outside of object", None);1349					LExpr::BadLocal("super")1350				}1351			}1352			LiteralType::Dollar => stack.use_dollar(taint).map_or_else(1353				|| {1354					stack.report_error("`$` used outside of object", None);1355					LExpr::BadLocal("$")1356				},1357				LExpr::Slot,1358			),1359			LiteralType::Null => LExpr::Null,1360			LiteralType::True => LExpr::Bool(true),1361			LiteralType::False => LExpr::Bool(false),1362		},1363		Expr::Str(s) => LExpr::Str(s.clone()),1364		Expr::Num(n) => LExpr::Num(*n),1365		Expr::Var(v) => stack1366			.use_local(&v.value, v.span.clone(), taint)1367			.map_or_else(|| LExpr::BadLocal("ref"), LExpr::Slot),1368		Expr::Arr(a) => {1369			let (shape, items) = stack1370				.in_using_closure(|stack| a.iter().map(|v| analyze(v, stack, taint)).collect());1371			LExpr::Arr {1372				shape,1373				items: Rc::new(items),1374			}1375		}1376		Expr::ArrComp(inner, comp) => analyze_arr_comp(inner, comp, stack, taint),1377		Expr::Obj(obj) => LExpr::Obj(analyze_obj_body(obj, stack, taint)),1378		Expr::ObjExtend(base, obj) => LExpr::ObjExtend(1379			Box::new(analyze(base, stack, taint)),1380			analyze_obj_body(obj, stack, taint),1381		),1382		Expr::UnaryOp(op, value) => LExpr::UnaryOp(*op, Box::new(analyze(value, stack, taint))),1383		Expr::BinaryOp(op) => {1384			let BinaryOp {1385				lhs,1386				op: optype,1387				rhs,1388			} = &**op;1389			LExpr::BinaryOp {1390				lhs: Box::new(analyze(lhs, stack, taint)),1391				op: *optype,1392				rhs: Box::new(analyze(rhs, stack, taint)),1393			}1394		}1395		Expr::AssertExpr(assert) => {1396			let AssertExpr { assert, rest } = &**assert;1397			let assert = Rc::new(analyze_assert(assert, stack, taint));1398			let rest = Box::new(analyze(rest, stack, taint));1399			LExpr::AssertExpr { assert, rest }1400		}1401		Expr::LocalExpr(binds, body) => analyze_local_expr(binds, body, stack, taint),1402		Expr::Import(kind, path_expr) => {1403			let Expr::Str(path) = &**path_expr else {1404				stack.report_error(1405					"import path must be a string literal",1406					Some(kind.span.clone()),1407				);1408				return LExpr::BadLocal("bad import");1409			};1410			LExpr::Import {1411				kind: kind.clone(),1412				kind_span: kind.span.clone(),1413				path: path.clone(),1414			}1415		}1416		Expr::ErrorStmt(span, inner) => {1417			LExpr::Error(span.clone(), Box::new(analyze(inner, stack, taint)))1418		}1419		Expr::Apply(applicable, args, tailstrict) => {1420			let app = analyze(applicable, stack, taint);1421			let ArgsDesc {1422				unnamed,1423				names,1424				values,1425			} = &args.value;1426			let unnamed_l = unnamed1427				.iter()1428				.map(|a| Rc::new(analyze(a, stack, taint)))1429				.collect();1430			let values_l = values1431				.iter()1432				.map(|a| Rc::new(analyze(a, stack, taint)))1433				.collect();1434			LExpr::Apply {1435				applicable: Box::new(app),1436				args: Spanned::new(1437					LArgsDesc {1438						unnamed: unnamed_l,1439						names: names.clone(),1440						values: values_l,1441					},1442					args.span.clone(),1443				),1444				tailstrict: *tailstrict,1445			}1446		}1447		Expr::Index { indexable, parts } => {1448			let idx = analyze(indexable, stack, taint);1449			let parts_l = parts1450				.iter()1451				.map(|p| {1452					let value = analyze(&p.value, stack, taint);1453					LIndexPart {1454						span: p.span.clone(),1455						value,1456						#[cfg(feature = "exp-null-coaelse")]1457						null_coaelse: p.null_coaelse,1458					}1459				})1460				.collect();1461			LExpr::Index {1462				indexable: Box::new(idx),1463				parts: parts_l,1464			}1465		}1466		Expr::Function(params, body) => analyze_function(None, params, body, stack, taint),1467		Expr::IfElse(ifelse) => {1468			let IfElse {1469				cond,1470				cond_then,1471				cond_else,1472			} = &**ifelse;1473			let cond_l = analyze(&cond.cond, stack, taint);1474			let then_l = analyze(cond_then, stack, taint);1475			let else_l = cond_else1476				.as_ref()1477				.map(|e| Box::new(analyze(e, stack, taint)));1478			LExpr::IfElse {1479				cond: Box::new(cond_l),1480				cond_then: Box::new(then_l),1481				cond_else: else_l,1482			}1483		}1484		Expr::Slice(slice) => {1485			let Slice {1486				value,1487				slice: SliceDesc { start, end, step },1488			} = &**slice;1489			let value_l = analyze(value, stack, taint);1490			let start_l = start.as_ref().map(|e| analyze(&e.value, stack, taint));1491			let end_l = end.as_ref().map(|e| analyze(&e.value, stack, taint));1492			let step_l = step.as_ref().map(|e| analyze(&e.value, stack, taint));1493			LExpr::Slice(Box::new(LSliceExpr {1494				value: value_l,1495				start: start_l,1496				end: end_l,1497				step: step_l,1498			}))1499		}1500	}1501}15021503fn analyze_local_expr(1504	binds: &[BindSpec],1505	body: &Expr,1506	stack: &mut AnalysisStack,1507	taint: &mut AnalysisResult,1508) -> LExpr {1509	if binds.is_empty() {1510		return analyze(body, stack, taint);1511	}1512	let frame_start = stack.next_local_id();1513	let closure = stack.push_closure_a(frame_start);1514	let (l_binds, body_expr) = process_local_frame(binds, stack, taint, |stack, taint| {1515		analyze(body, stack, taint)1516	});1517	let frame_shape = stack.pop_closure(closure);1518	LExpr::LocalExpr(Box::new(LLocalExpr {1519		frame_shape,1520		binds: l_binds,1521		body: body_expr,1522	}))1523}15241525fn analyze_bind_value(1526	bind: &BindSpec,1527	stack: &mut AnalysisStack,1528	taint: &mut AnalysisResult,1529) -> LExpr {1530	match bind {1531		BindSpec::Field {1532			value: Expr::Function(params, value),1533			into: Destruct::Full(name),1534		} => analyze_function(Some(name.value.clone()), params, value, stack, taint),1535		BindSpec::Field { value, .. } => analyze(value, stack, taint),1536		BindSpec::Function {1537			params,1538			value,1539			name,1540		} => analyze_function(Some(name.clone()), params, value, stack, taint),1541	}1542}15431544fn process_local_frame<R>(1545	binds: &[BindSpec],1546	stack: &mut AnalysisStack,1547	taint: &mut AnalysisResult,1548	body_fn: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1549) -> (Vec<LBind>, R) {1550	let mut alloc = FrameAlloc::new(stack);15511552	let mut destructs: Vec<Option<LDestruct>> = Vec::with_capacity(binds.len());1553	for bind in binds {1554		destructs.push(alloc.alloc_bind(bind));1555	}1556	let mut pending = alloc.finish();15571558	let mut l_binds: Vec<LBind> = Vec::with_capacity(binds.len());1559	for (bind, destruct) in binds.iter().zip(destructs.into_iter()) {1560		let mut value_taint = AnalysisResult::default();1561		let (value_shape, value) = pending1562			.stack1563			.in_using_closure(|stack| analyze_bind_value(bind, stack, &mut value_taint));1564		taint.taint_by(value_taint);1565		if let Some(destruct) = destruct {1566			pending.record_spec_init(&destruct, value_taint);1567			l_binds.push(LBind {1568				destruct,1569				value_shape,1570				value: Rc::new(value),1571			});1572		} else {1573			pending.closures.push_spec(0, &[]);1574		}1575	}15761577	let body_frame = pending.finish();1578	let result = body_fn(body_frame.stack, taint);1579	body_frame.finish();15801581	(l_binds, result)1582}15831584fn analyze_function(1585	name: Option<IStr>,1586	params: &ExprParams,1587	body: &Expr,1588	stack: &mut AnalysisStack,1589	taint: &mut AnalysisResult,1590) -> LExpr {1591	let mut alloc = FrameAlloc::new(stack);1592	let closure = alloc.push_locals_closure();15931594	let mut param_destructs: Vec<Option<LDestruct>> = Vec::with_capacity(params.exprs.len());1595	for p in &params.exprs {1596		param_destructs.push(alloc.alloc_destruct(&p.destruct));1597	}15981599	let mut pending = alloc.finish();16001601	let mut l_params: Vec<LParam> = Vec::with_capacity(params.exprs.len());1602	for (p, destruct) in params.exprs.iter().zip(param_destructs.into_iter()) {1603		let mut value_taint = AnalysisResult::default();1604		let default = p.default.as_ref().map_or_else(1605			|| None,1606			|d| {1607				Some(1608					pending1609						.stack1610						.in_using_closure(|stack| Rc::new(analyze(d, stack, &mut value_taint))),1611				)1612			},1613		);1614		taint.taint_by(value_taint);1615		if let Some(destruct) = destruct {1616			let name = match &p.destruct {1617				Destruct::Full(n) => Some(n.value.clone()),1618				#[cfg(feature = "exp-destruct")]1619				_ => None,1620			};1621			pending.record_spec_init(&destruct, value_taint);1622			l_params.push(LParam {1623				name,1624				destruct,1625				default,1626			});1627		} else {1628			pending.closures.push_spec(0, &[]);1629		}1630	}16311632	let body_frame = pending.finish();1633	let body_expr = analyze(body, body_frame.stack, taint);1634	body_frame.finish();1635	let body_shape = stack.pop_closure(closure);16361637	// function(x) x is an identity function1638	if l_params.len() == 1 && l_params[0].default.is_none() {1639		stack.report_warning(1640			"do not define identity functions manually, use std.id instead",1641			None,1642		);1643		#[allow(irrefutable_let_patterns, reason = "refutable with exp-destruct")]1644		if let LDestruct::Full(param_slot) = &l_params[0].destruct1645			&& let LExpr::Slot(LSlot::Local(s)) = &body_expr1646			&& s == param_slot1647		{1648			return LExpr::IdentityFunction {};1649		}1650	}16511652	LExpr::Function(Rc::new(LFunction {1653		name,1654		params: l_params,1655		signature: params.signature.clone(),1656		body_shape,1657		body: Rc::new(body_expr),1658	}))1659}16601661fn analyze_obj_body(1662	obj: &ObjBody,1663	stack: &mut AnalysisStack,1664	taint: &mut AnalysisResult,1665) -> LObjBody {1666	match obj {1667		ObjBody::MemberList(members) => {1668			LObjBody::MemberList(analyze_obj_members(members, stack, taint))1669		}1670		ObjBody::ObjComp(comp) => LObjBody::ObjComp(Box::new(analyze_obj_comp(comp, stack, taint))),1671	}1672}16731674fn analyze_obj_members(1675	members: &ObjMembers,1676	stack: &mut AnalysisStack,1677	taint: &mut AnalysisResult,1678) -> LObjMembers {1679	let ObjMembers {1680		locals,1681		asserts,1682		fields,1683	} = members;16841685	// Names are analyzed in enclosing scope, they can't depend on locals or self/super1686	let field_names: Vec<LFieldName> = fields1687		.iter()1688		.map(|f| match &f.name.value {1689			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1690			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1691		})1692		.collect();16931694	let (usage, frame_shape, (l_binds, (l_asserts_opt, l_fields))) =1695		stack.in_object_scope(|stack| {1696			process_local_frame(locals, stack, taint, |stack, taint| {1697				let l_asserts_opt = if asserts.is_empty() {1698					None1699				} else {1700					let (shape, l_asserts) = stack.in_using_closure(|stack| {1701						let mut l_asserts = Vec::with_capacity(asserts.len());1702						for a in asserts {1703							let mut assert_taint = AnalysisResult::default();1704							l_asserts.push(analyze_assert(a, stack, &mut assert_taint));1705							taint.taint_by(assert_taint);1706						}1707						l_asserts1708					});1709					Some(Rc::new(LObjAsserts {1710						shape,1711						asserts: l_asserts,1712					}))1713				};1714				let mut l_fields = Vec::with_capacity(fields.len());1715				for (f, name) in fields.iter().zip(field_names) {1716					let value = stack.in_using_closure(|stack| {1717						if let Some(params) = &f.params {1718							analyze_function(name.function_name(), params, &f.value, stack, taint)1719						} else {1720							analyze(&f.value, stack, taint)1721						}1722					});1723					l_fields.push(LFieldMember {1724						name,1725						plus: f.plus,1726						visibility: f.visibility,1727						value: Rc::new(value),1728					});1729				}1730				(l_asserts_opt, l_fields)1731			})1732		});1733	// `this` was allocated as the first local of the object's frame,1734	// so its slot is 0 within that frame.1735	let this_slot = usage.this_used.then_some(LocalSlot(0));1736	LObjMembers {1737		frame_shape,1738		this: this_slot,1739		set_dollar: usage.set_dollar,1740		uses_super: usage.uses_super,1741		locals: Rc::new(l_binds),1742		asserts: l_asserts_opt,1743		fields: l_fields,1744	}1745}17461747fn analyze_obj_comp(1748	comp: &ObjComp,1749	stack: &mut AnalysisStack,1750	taint: &mut AnalysisResult,1751) -> LObjComp {1752	let res = analyze_comp_specs(&comp.compspecs, stack, taint, |stack, taint| {1753		let field_name = match &comp.field.name.value {1754			FieldName::Fixed(s) => LFieldName::Fixed(s.clone()),1755			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1756		};17571758		let (usage, frame_shape, body) = stack.in_object_scope(|stack| {1759			process_local_frame(&comp.locals, stack, taint, |stack, taint| {1760				let value = stack.in_using_closure(|stack| {1761					if let Some(params) = &comp.field.params {1762						analyze_function(None, params, &comp.field.value, stack, taint)1763					} else {1764						analyze(&comp.field.value, stack, taint)1765					}1766				});1767				LFieldMember {1768					name: field_name,1769					plus: comp.field.plus,1770					visibility: comp.field.visibility,1771					value: Rc::new(value),1772				}1773			})1774		});1775		(usage, frame_shape, body)1776	});1777	let (usage, frame_shape, (locals, field)) = res.inner;1778	let this_slot = usage.this_used.then_some(LocalSlot(0));1779	LObjComp {1780		frame_shape: Rc::new(frame_shape),1781		this: this_slot,1782		set_dollar: usage.set_dollar,1783		uses_super: usage.uses_super,1784		locals: Rc::new(locals),1785		field,1786		compspecs: res.compspecs,1787	}1788}17891790fn analyze_arr_comp(1791	inner: &Expr,1792	specs: &[CompSpec],1793	stack: &mut AnalysisStack,1794	taint: &mut AnalysisResult,1795) -> LExpr {1796	let res = analyze_comp_specs(specs, stack, taint, |stack, taint| {1797		stack.in_using_closure(|stack| analyze(inner, stack, taint))1798	});1799	let (value_shape, value) = res.inner;1800	LExpr::ArrComp(Box::new(LArrComp {1801		value_shape,1802		value: Rc::new(value),1803		compspecs: res.compspecs,1804	}))1805}18061807fn analyze_comp_specs<R>(1808	specs: &[CompSpec],1809	stack: &mut AnalysisStack,1810	taint: &mut AnalysisResult,1811	inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1812) -> CompSpecResult<R> {1813	fn go<R>(1814		idx: usize,1815		specs: &[CompSpec],1816		outer_depth: u32,1817		stack: &mut AnalysisStack,1818		taint: &mut AnalysisResult,1819		inside: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1820	) -> (R, Vec<LCompSpec>) {1821		if idx >= specs.len() {1822			return (inside(stack, taint), Vec::new());1823		}1824		match &specs[idx] {1825			CompSpec::IfSpec(IfSpecData { cond, .. }) => {1826				let cond_l = analyze(cond, stack, taint);1827				let (r, mut rest) = go(idx + 1, specs, outer_depth, stack, taint, inside);1828				rest.insert(0, LCompSpec::If(cond_l));1829				(r, rest)1830			}1831			CompSpec::ForSpec(ForSpecData { destruct, over }) => {1832				let mut over_taint = AnalysisResult::default();1833				let over_l = analyze(over, stack, &mut over_taint);1834				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1835				taint.taint_by(over_taint);18361837				let mut alloc = FrameAlloc::new(stack);1838				let closure = alloc.push_locals_closure();1839				let Some(l_destruct) = alloc.alloc_destruct(destruct) else {1840					stack.pop_closure(closure);1841					return go(idx + 1, specs, outer_depth, stack, taint, inside);1842				};1843				let mut pending = alloc.finish();18441845				let var_analysis = AnalysisResult::default();1846				pending.record_spec_init(&l_destruct, var_analysis);18471848				let body_frame = pending.finish();1849				let (r, mut rest) =1850					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);1851				body_frame.finish();1852				let frame_shape = stack.pop_closure(closure);18531854				rest.insert(1855					0,1856					LCompSpec::For {1857						frame_shape,1858						destruct: l_destruct,1859						over: over_l,1860						loop_invariant,1861					},1862				);1863				(r, rest)1864			}1865		}1866	}1867	let outer_depth = stack.depth;1868	let (r, compspecs) = go(0, specs, outer_depth, stack, taint, inside);1869	CompSpecResult {1870		inner: r,1871		compspecs,1872	}1873}18741875struct CompSpecResult<R> {1876	inner: R,1877	compspecs: Vec<LCompSpec>,1878}18791880pub fn analyze_root(expr: &Expr, ctx: Vec<(IStr, LocalId)>) -> AnalysisReport {1881	let mut stack = AnalysisStack::new();1882	for (name, id) in ctx {1883		stack.define_external_local(name, id);1884	}18851886	let externals_count: u16 = stack1887		.local_defs1888		.len()1889		.try_into()1890		.expect("more than u16::MAX externals");1891	let closure = stack.push_root_closure(externals_count);18921893	let mut taint = AnalysisResult::default();1894	let lir = analyze(expr, &mut stack, &mut taint);18951896	let root_shape = stack.pop_closure(closure);1897	debug_assert!(1898		stack.closure_stack.is_empty(),1899		"closure stack imbalance after analyze"1900	);19011902	AnalysisReport {1903		lir,1904		root_shape,1905		root_analysis: taint,1906		diagnostics_list: stack.diagnostics,1907		errored: stack.errored,1908	}1909}19101911#[cfg(test)]1912fn render_diagnostics(src: &str, diags: &[Diagnostic]) -> String {1913	use std::fmt::Write;19141915	use hi_doc::{Formatting, SnippetBuilder, Text};19161917	let mut out = String::new();1918	let mut unspanned = Vec::new();1919	let mut spanned: Vec<&Diagnostic> = Vec::new();1920	for d in diags {1921		if d.span.is_some() {1922			spanned.push(d);1923		} else {1924			unspanned.push(d);1925		}1926	}1927	if !spanned.is_empty() {1928		let mut builder = SnippetBuilder::new(src);1929		for d in spanned {1930			let span = d.span.as_ref().expect("spanned");1931			let ab = match d.level {1932				DiagLevel::Error => {1933					builder.error(Text::fragment(d.message.clone(), Formatting::default()))1934				}1935				DiagLevel::Warning => {1936					builder.warning(Text::fragment(d.message.clone(), Formatting::default()))1937				}1938			};1939			ab.range(span.range()).build();1940		}1941		out.push_str(&hi_doc::source_to_ansi(&builder.build()));1942	}1943	for d in unspanned {1944		let prefix = match d.level {1945			DiagLevel::Error => "error",1946			DiagLevel::Warning => "warning",1947		};1948		writeln!(out, "{prefix}: {}", d.message).expect("fmt");1949	}1950	out1951}19521953pub struct AnalysisReport {1954	pub lir: LExpr,1955	pub root_shape: ClosureShape,1956	pub root_analysis: AnalysisResult,1957	pub diagnostics_list: Vec<Diagnostic>,1958	pub errored: bool,1959}19601961#[cfg(test)]1962mod tests {1963	use std::fs;19641965	use insta::{assert_snapshot, glob};1966	use jrsonnet_ir::Source;19671968	use super::*;19691970	#[test]1971	fn snapshots() {1972		glob!("analysis_tests/*.jsonnet", |path| {1973			let code = fs::read_to_string(path).expect("read test file");1974			let src = Source::new_virtual("<test>".into(), code.clone().into());1975			let expr = crate::parse_jsonnet(&code, src.clone()).expect("parse");1976			let report = analyze_root(&expr, Vec::new());19771978			let diagnostics = render_diagnostics(src.code(), &report.diagnostics_list);1979			// Strip ANSI escapes from diagnostics so snapshots are readable.1980			let diagnostics = strip_ansi_escapes::strip_str(&diagnostics);1981			let rendered = format!(1982				"--- source ---\n{}\n--- root analysis ---\nobject_dependent_depth: {}\nlocal_dependent_depth: {}\nerrored: {}\n--- diagnostics ---\n{}--- lir ---\n{:#?}\n",1983				code.trim_end(),1984				fmt_depth(report.root_analysis.object_dependent_depth),1985				fmt_depth(report.root_analysis.local_dependent_depth),1986				report.errored,1987				diagnostics,1988				report.lir,1989			);1990			assert_snapshot!(rendered);1991		});1992	}19931994	fn fmt_depth(d: u32) -> String {1995		if d == u32::MAX {1996			"none".into()1997		} else {1998			d.to_string()1999		}2000	}2001}