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

--- a/Cargo.lock
+++ b/Cargo.lock
@@ -852,18 +852,18 @@
 
 [[package]]
 name = "jrsonnet-gcmodule"
-version = "0.4.4"
+version = "0.4.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "21dd97b40cbfb2043094219f95d96519858ba1aee4e8260eb048a1774832a517"
+checksum = "95f9ce64915cdb0cab5367940a7cc024394fcf4f2608531e49f6dad39e2082d7"
 dependencies = [
  "jrsonnet-gcmodule-derive",
 ]
 
 [[package]]
 name = "jrsonnet-gcmodule-derive"
-version = "0.4.4"
+version = "0.4.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "ede3d0445c2a7d7adab0a3cc33bdb33df78ffebebc21a2848c221526cb1795d4"
+checksum = "64364cfb68be0968a940d69ccb651ec445cde47830da5b294d55d2e47eee8708"
 dependencies = [
  "proc-macro2",
  "quote",

--- a/Cargo.toml
+++ b/Cargo.toml
@@ -5,7 +5,7 @@
 
 [workspace.package]
 authors = ["Yaroslav Bolyukin <iam@lach.pw>"]
-edition = "2021"
+edition = "2024"
 license = "MIT"
 repository = "https://github.com/CertainLach/jrsonnet"
 version = "0.5.0-pre98"
@@ -22,7 +22,7 @@
 jrsonnet-cli = { path = "./crates/jrsonnet-cli", version = "0.5.0-pre98" }
 jrsonnet-types = { path = "./crates/jrsonnet-types", version = "0.5.0-pre98" }
 jrsonnet-formatter = { path = "./crates/jrsonnet-formatter", version = "0.5.0-pre98" }
-jrsonnet-gcmodule = { version = "0.4.4" }
+jrsonnet-gcmodule = { version = "0.4.5" }
 # Diagnostics.
 # hi-doc is my library, which handles text formatting very well, but isn't polished enough yet
 # Previous implementation was based on annotate-snippets, which I don't like for many reasons.

14//! }14//! }
15//! ```15//! ```
1616
17use std::{fmt::Write, rc::Rc};17use std::rc::Rc;
1818
19use drop_bomb::DropBomb;19use drop_bomb::DropBomb;
20use hi_doc::{Formatting, SnippetBuilder, Text};
21use jrsonnet_gcmodule::Acyclic;20use jrsonnet_gcmodule::Acyclic;
22use jrsonnet_interner::IStr;21use jrsonnet_interner::IStr;
23use jrsonnet_ir::{22use jrsonnet_ir::{
78	}77	}
79}78}
79
80#[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}
87
88#[derive(Debug, Acyclic)]
89pub struct ClosureShape {
90	pub captures: Box<[LSlot]>,
91	pub n_locals: u16,
92}
8093
81struct LocalDefinition {94struct LocalDefinition {
82	name: IStr,95	name: IStr,
121134
122#[derive(Debug, Acyclic)]135#[derive(Debug, Acyclic)]
123pub enum LExpr {136pub enum LExpr {
124	Local(LocalId),137	Slot(LSlot),
125	Null,138	Null,
126	Bool(bool),139	Bool(bool),
127	Str(IStr),140	Str(IStr),
128	Num(NumValue),141	Num(NumValue),
129	Arr(Rc<Vec<LExpr>>),142	Arr {
143		shape: ClosureShape,
144		items: Rc<Vec<LExpr>>,
145	},
130	ArrComp(Box<LArrComp>),146	ArrComp(Box<LArrComp>),
131	Obj(LObjBody),147	Obj(LObjBody),
132	ObjExtend(Box<LExpr>, LObjBody),148	ObjExtend(Box<LExpr>, LObjBody),
141		rest: Box<LExpr>,157		rest: Box<LExpr>,
142	},158	},
143	Error(Span, Box<LExpr>),159	Error(Span, Box<LExpr>),
144	LocalExpr {160	LocalExpr(Box<LLocalExpr>),
145		binds: Vec<LBind>,
146		body: Box<LExpr>,
147	},
148	Import {161	Import {
149		kind: Spanned<ImportKind>,162		kind: Spanned<ImportKind>,
150		kind_span: Span,163		kind_span: Span,
160		parts: Vec<LIndexPart>,173		parts: Vec<LIndexPart>,
161	},174	},
162	Function(Rc<LFunction>),175	Function(Rc<LFunction>),
176	IdentityFunction,
163	IfElse {177	IfElse {
164		cond: Box<LExpr>,178		cond: Box<LExpr>,
165		cond_then: Box<LExpr>,179		cond_then: Box<LExpr>,
173	BadLocal(&'static str),187	BadLocal(&'static str),
174}188}
189
190#[derive(Debug, Acyclic)]
191pub struct LLocalExpr {
192	pub frame_shape: ClosureShape,
193	pub binds: Vec<LBind>,
194	pub body: LExpr,
195}
175196
176#[derive(Debug, Acyclic)]197#[derive(Debug, Acyclic)]
177pub struct LFunction {198pub struct LFunction {
178	pub name: Option<IStr>,199	pub name: Option<IStr>,
179	pub params: Vec<LParam>,200	pub params: Vec<LParam>,
180	pub signature: FunctionSignature,201	pub signature: FunctionSignature,
202
203	pub body_shape: ClosureShape,
181	pub body: Rc<LExpr>,204	pub body: Rc<LExpr>,
182}205}
183206
186	pub name: Option<IStr>,209	pub name: Option<IStr>,
187	pub destruct: LDestruct,210	pub destruct: LDestruct,
211
188	pub default: Option<Rc<LExpr>>,212	pub default: Option<(ClosureShape, Rc<LExpr>)>,
189}213}
190214
191#[derive(Debug, Acyclic)]215#[derive(Debug, Acyclic)]
192pub struct LBind {216pub struct LBind {
193	pub destruct: LDestruct,217	pub destruct: LDestruct,
218	pub value_shape: ClosureShape,
194	pub value: Rc<LExpr>,219	pub value: Rc<LExpr>,
195}220}
221
222#[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);
196226
197#[derive(Debug, Clone, Acyclic)]227#[derive(Debug, Acyclic)]
198pub enum LDestruct {228pub enum LDestruct {
199	Full(LocalId),229	Full(LocalSlot),
200	#[cfg(feature = "exp-destruct")]230	#[cfg(feature = "exp-destruct")]
201	Skip,231	Skip,
202	#[cfg(feature = "exp-destruct")]232	#[cfg(feature = "exp-destruct")]
214244
215#[derive(Debug, Clone, Copy, Acyclic)]245#[derive(Debug, Clone, Copy, Acyclic)]
216pub enum LDestructRest {246pub enum LDestructRest {
217	Keep(LocalId),247	Keep(LocalSlot),
218	Drop,248	Drop,
219}249}
220250
221#[derive(Debug, Clone, Acyclic)]251#[derive(Debug, Acyclic)]
222pub struct LDestructField {252pub struct LDestructField {
223	pub name: IStr,253	pub name: IStr,
224	pub into: Option<LDestruct>,254	pub into: Option<LDestruct>,
225	pub default: Option<Rc<LExpr>>,255	pub default: Option<(ClosureShape, Rc<LExpr>)>,
226}256}
227257
228impl LDestruct {258impl LDestruct {
229	pub fn each_id<F: FnMut(LocalId)>(&self, f: &mut F) {259	pub fn each_slot<F: FnMut(LocalSlot)>(&self, f: &mut F) {
230		match self {260		match self {
231			Self::Full(id) => f(*id),261			Self::Full(s) => f(*s),
232			#[cfg(feature = "exp-destruct")]262			#[cfg(feature = "exp-destruct")]
233			Self::Skip => {}263			Self::Skip => {}
234			#[cfg(feature = "exp-destruct")]264			#[cfg(feature = "exp-destruct")]
235			Self::Array { start, rest, end } => {265			Self::Array { start, rest, end } => {
236				for d in start {266				for d in start {
237					d.each_id(f);267					d.each_slot(f);
238				}268				}
239				if let Some(LDestructRest::Keep(id)) = rest {269				if let Some(LDestructRest::Keep(s)) = rest {
240					f(*id);270					f(*s);
241				}271				}
242				for d in end {272				for d in end {
243					d.each_id(f);273					d.each_slot(f);
244				}274				}
245			}275			}
246			#[cfg(feature = "exp-destruct")]276			#[cfg(feature = "exp-destruct")]
247			Self::Object { fields, rest } => {277			Self::Object { fields, rest } => {
248				for field in fields {278				for field in fields {
249					if let Some(into) = &field.into {279					if let Some(into) = &field.into {
250						into.each_id(f);280						into.each_slot(f);
251					} else {281					} else {
252						unreachable!("shorthand object destruct must store `into`");282						unreachable!("shorthand object destruct must store `into`");
253					}283					}
254				}284				}
255				if let Some(LDestructRest::Keep(id)) = rest {285				if let Some(LDestructRest::Keep(s)) = rest {
256					f(*id);286					f(*s);
257				}287				}
258			}288			}
259		}289		}
260	}290	}
261291
262	pub fn ids(&self) -> SmallVec<[LocalId; 1]> {292	pub fn slots(&self) -> SmallVec<[LocalSlot; 1]> {
263		let mut out = SmallVec::new();293		let mut out = SmallVec::new();
264		self.each_id(&mut |id| out.push(id));294		self.each_slot(&mut |s| out.push(s));
265		out295		out
266	}296	}
267}297}
303333
304#[derive(Debug, Acyclic)]334#[derive(Debug, Acyclic)]
305pub struct LObjMembers {335pub struct LObjMembers {
336	pub frame_shape: ClosureShape,
306	/// If current object identity (`super`/`this`/`$`) is used, `this` should be saved to the specified local337	/// If current object identity (`super`/`this`/`$`) is used, `this` should
338	/// be saved to the specified local slot.
307	pub this: Option<LocalId>,339	pub this: Option<LocalSlot>,
308	/// Set if dollar should also be assigned to object identity, `this` should also be set (TODO: proper type-level validation)340	/// Set if dollar should also be assigned to object identity, `this` should also be set (TODO: proper type-level validation)
309	pub set_dollar: bool,341	pub set_dollar: bool,
310	/// True iff `super` is referenced by this object's members.342	/// True iff `super` is referenced by this object's members.
311	pub uses_super: bool,343	pub uses_super: bool,
312344
313	pub locals: Rc<Vec<LBind>>,345	pub locals: Rc<Vec<LBind>>,
314	pub asserts: Rc<Vec<LAssertStmt>>,346	pub asserts: Option<Rc<LObjAsserts>>,
315	pub fields: Vec<LFieldMember>,347	pub fields: Vec<LFieldMember>,
316}348}
317349
318#[derive(Debug, Acyclic)]350#[derive(Debug, Acyclic)]
319pub struct LObjComp {351pub struct LObjComp {
352	pub frame_shape: Rc<ClosureShape>,
320	pub this: Option<LocalId>,353	pub this: Option<LocalSlot>,
321	pub set_dollar: bool,354	pub set_dollar: bool,
322	pub uses_super: bool,355	pub uses_super: bool,
323356
331	pub name: LFieldName,364	pub name: LFieldName,
332	pub plus: bool,365	pub plus: bool,
333	pub visibility: Visibility,366	pub visibility: Visibility,
334	pub value: Rc<LExpr>,367	pub value: Rc<(ClosureShape, LExpr)>,
335}368}
369
370#[derive(Debug, Acyclic)]
371pub struct LClosure<T: Acyclic> {
372	pub shape: ClosureShape,
373	pub value: T,
374}
375
376#[derive(Debug, Acyclic)]
377pub struct LObjAsserts {
378	pub shape: ClosureShape,
379	pub asserts: Vec<LAssertStmt>,
380}
336381
337#[derive(Debug, Acyclic)]382#[derive(Debug, Acyclic)]
338pub enum LFieldName {383pub enum LFieldName {
350395
351#[derive(Debug, Acyclic)]396#[derive(Debug, Acyclic)]
352pub struct LArrComp {397pub struct LArrComp {
398	pub value_shape: ClosureShape,
353	pub value: Rc<LExpr>,399	pub value: Rc<LExpr>,
354	pub compspecs: Vec<LCompSpec>,400	pub compspecs: Vec<LCompSpec>,
355}401}
358pub enum LCompSpec {404pub enum LCompSpec {
359	If(LExpr),405	If(LExpr),
360	For {406	For {
407		frame_shape: ClosureShape,
361		destruct: LDestruct,408		destruct: LDestruct,
362		over: LExpr,409		over: LExpr,
363		/// Is `over` does not depend on any variable introduced by an earlier for-spec in this comprehension chain410		/// Is `over` does not depend on any variable introduced by an earlier for-spec in this comprehension chain
364		loop_invariant: bool,411		loop_invariant: bool,
365	},412	},
366}413}
367414
368// TODO: Binding frame state machine:415struct FrameAlloc<'s> {
369// Pending => AllocIds => Initialize => Body => Exit416	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	}
428
429	fn push_locals_closure(&mut self) -> ClosureOnStack {
430		self.stack.push_closure_a(self.first_in_frame)
431	}
432
433	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 = start
479					.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 = end
491					.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 defaults
500				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_fields
511					.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	}
545
546	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}
370565
371/// Frame state: `LocalIds` allocated, values not yet analysed.566/// Frame state: `LocalIds` allocated, values not yet analysed.
372struct PendingInit {567struct PendingInit<'s> {
373	first_in_frame: LocalId,568	first_after_frame: LocalId,
374	first_after_frame: LocalId,569	stack: &'s mut AnalysisStack,
570	closures: Closures,
375	bomb: DropBomb,571	bomb: DropBomb,
376}572}
573
574impl<'s> PendingInit<'s> {
575	/// Record the analysis of a spec's value: stamp every id bound by the
576	/// spec with `analysis`, collect the spec's same-frame references, and
577	/// 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		}
587
588		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 between
601	/// 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;
609
610		debug_assert_eq!(
611			first_after_frame,
612			stack.next_local_id(),
613			"frame initialisation left unfinished locals"
614		);
615
616		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		);
621
622		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		}
634
635		stack.depth += 1;
636		PendingBody {
637			first_after_frame,
638			closures,
639			stack,
640			bomb,
641		}
642	}
643}
377644
378/// Frame state: values analysed, body not yet walked.645/// Frame state: values analysed, body not yet walked.
379struct PendingBody {646struct PendingBody<'s> {
380	first_in_frame: LocalId,
381	first_after_frame: LocalId,647	first_after_frame: LocalId,
382	closures: Closures,648	closures: Closures,
649	stack: &'s mut AnalysisStack,
383	bomb: DropBomb,650	bomb: DropBomb,
384}651}
652impl<'s> PendingBody<'s> {
653	/// After the body is processed, drop the frame's locals and emit any
654	/// "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;
664
665		debug_assert_eq!(
666			first_after_frame,
667			stack.next_local_id(),
668			"nested scopes must be popped before outer frames"
669		);
670
671		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		}
692
693		let drained: Vec<LocalDefinition> = stack
694			.local_defs
695			.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 = stack
700				.local_by_name
701				.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			}
708
709			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_depth
719				&& def.analysis.object_dependent_depth > def.defined_at_depth
720				&& def.defined_at_depth != 0
721			{
722				// The value doesn't depend on anything defined at or inside
723				// 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}
385732
386struct Closures {733struct Closures {
387	/// All the referenced locals, maybe repeated multiple times734	/// All the referenced locals, maybe repeated multiple times
451}798}
452799
453impl Closures {800impl Closures {
454	fn new(first_in_frame: LocalId) -> Self {
455		Self {
456			referenced: Vec::new(),
457			spec_shapes: Vec::new(),
458			first_in_frame,
459		}
460	}
461
462	fn push_spec(&mut self, destruct_ids_count: usize, refs: &[LocalId]) {801	fn push_spec(&mut self, destruct_ids_count: usize, refs: &[LocalId]) {
463		self.referenced.extend_from_slice(refs);802		self.referenced.extend_from_slice(refs);
493	pub span: Option<Span>,832	pub span: Option<Span>,
494}833}
834
835struct DefiningClosure {
836	first_local: LocalId,
837	n_locals: u16,
838}
839
840impl 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			None
849		}
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}
859
860/// Per-closure capture computation state.
861struct ClosureFrame {
862	/// Closure may allocate locals
863	defining: Option<DefiningClosure>,
864	/// `LocalId` => capture index
865	captures: FxHashMap<LocalId, CaptureSlot>,
866	/// Capture sources in insertion order; consumed by `pop_closure_frame`.
867	capture_sources: Vec<LSlot>,
868}
495869
496#[allow(clippy::struct_excessive_bools)]870#[allow(clippy::struct_excessive_bools)]
497pub struct AnalysisStack {871pub struct AnalysisStack {
519	/// True iff `$` has been referenced anywhere since the outermost object's scope was entered.893	/// True iff `$` has been referenced anywhere since the outermost object's scope was entered.
520	dollar_used: bool,894	dollar_used: bool,
895
896	/// Stack of closure frames (innermost on top).
897	closure_stack: Vec<ClosureFrame>,
521898
522	diagnostics: Vec<Diagnostic>,899	diagnostics: Vec<Diagnostic>,
523	/// Whenever analysis would be broken due to static analysis error.900	/// Whenever analysis would be broken due to static analysis error.
524	errored: bool,901	errored: bool,
525}902}
903
904#[must_use]
905struct ClosureOnStack {
906	bomb: DropBomb,
907}
526908
527impl AnalysisStack {909impl AnalysisStack {
528	pub fn new() -> Self {910	pub fn new() -> Self {
537			cur_self_used: false,919			cur_self_used: false,
538			cur_super_used: false,920			cur_super_used: false,
539			dollar_used: false,921			dollar_used: false,
922			closure_stack: Vec::new(),
540			diagnostics: Vec::new(),923			diagnostics: Vec::new(),
541			errored: false,924			errored: false,
542		}925		}
543	}926	}
927
928	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		);
933
934		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		});
942
943		ClosureOnStack {
944			bomb: DropBomb::new("root closure"),
945		}
946	}
947
948	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	}
961
962	#[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	}
982
983	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	}
991
992	/// Resolve a `LocalId` reference to an `LSlot` against the innermost
993	/// closure frame. May insert capture entries up the closure stack as
994	/// 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	}
1000
1001	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, or
1008			// 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			frame
1026				.capture_sources
1027				.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	}
5441035
545	fn next_local_id(&self) -> LocalId {1036	fn next_local_id(&self) -> LocalId {
546		LocalId(self.local_defs.len() as u32)1037		LocalId(self.local_defs.len() as u32)
562		});1053		});
563	}1054	}
5641055
565	fn use_local(1056	fn use_local(&mut self, name: &IStr, span: Span, taint: &mut AnalysisResult) -> Option<LSlot> {
566		&mut self,
567		name: &IStr,
568		span: Span,
569		taint: &mut AnalysisResult,
570	) -> Option<LocalId> {
571		let Some(ids) = self.local_by_name.get(name) else {1057		let Some(ids) = self.local_by_name.get(name) else {
572			let names = suggest_names(name, self.local_by_name.keys());1058			let names = suggest_names(name, self.local_by_name.keys());
573			self.report_error(1059			self.report_error(
586		} else {1072		} else {
587			def.scratch_referenced = true;1073			def.scratch_referenced = true;
588		}1074		}
589		Some(id)1075		Some(self.resolve_to_slot(id))
590	}1076	}
5911077
592	/// Assign name to the value provided externally, e.g `std`.1078	/// Assign name to the value provided externally, e.g `std`.
613		self.local_by_name.entry(name).or_default().push(id);1099		self.local_by_name.entry(name).or_default().push(id);
614	}1100	}
6151101
616	/// Define a new local inside a frame currently being built.
617	fn define_local(1102	fn defining_closure_mut(&mut self) -> &mut DefiningClosure {
618		&mut self,1103		self.closure_stack
619		name: IStr,1104			.iter_mut()
620		span: Option<Span>,1105			.rev()
621		frame_start: LocalId,1106			.find_map(|c| c.defining.as_mut())
622	) -> Option<LocalId> {1107			.expect("no enclosing defining closure frame")
623		let id = self.next_local_id();1108	}
624		let stack = self.local_by_name.entry(name.clone()).or_default();
625		if let Some(&existing) = stack.last() {1109	fn defining_closure(&self) -> &DefiningClosure {
1110		self.closure_stack
1111			.iter()
626			if !existing.defined_before(frame_start) {1112			.rev()
627				self.report_error(1113			.find_map(|c| c.defining.as_ref())
628					format!("local is already defined in the current frame: {name}"),1114			.expect("no enclosing defining closure frame")
629					span,
630				);
631				return None;
632			}
633		}1115	}
634		stack.push(id);
635		self.local_defs.push(LocalDefinition {
636			name,
637			span,
638			defined_at_depth: self.depth,
639			used_at_depth: u32::MAX,
640			used_by_sibling: false,
641			analysis: AnalysisResult::default(),
642			analyzed: false,
643			scratch_referenced: false,
644		});
645		Some(id)
646	}
647}1116}
6481117
649impl Default for AnalysisStack {1118impl Default for AnalysisStack {
653}1122}
6541123
655impl AnalysisStack {1124impl AnalysisStack {
656	fn alloc_destruct(&mut self, destruct: &Destruct, frame_start: LocalId) -> Option<LDestruct> {
657		match destruct {
658			Destruct::Full(name) => {
659				let id =
660					self.define_local(name.value.clone(), Some(name.span.clone()), frame_start)?;
661				Some(LDestruct::Full(id))
662			}
663			#[cfg(feature = "exp-destruct")]
664			Destruct::Skip => Some(LDestruct::Skip),
665			#[cfg(feature = "exp-destruct")]
666			Destruct::Array { start, rest, end } => {
667				let start = start
668					.iter()
669					.map(|d| self.alloc_destruct(d, frame_start))
670					.collect::<Option<Vec<_>>>()?;
671				let rest = match rest {
672					Some(jrsonnet_ir::DestructRest::Keep(name)) => {
673						let id = self.define_local(name.clone(), None, frame_start)?;
674						Some(LDestructRest::Keep(id))
675					}
676					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),
677					None => None,
678				};
679				let end = end
680					.iter()
681					.map(|d| self.alloc_destruct(d, frame_start))
682					.collect::<Option<Vec<_>>>()?;
683				Some(LDestruct::Array { start, rest, end })
684			}
685			#[cfg(feature = "exp-destruct")]
686			Destruct::Object { fields, rest } => {
687				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());
688				// Two passes: first allocate ALL destruct LocalIds, then
689				// analyse defaults (which may reference later fields).
690				let mut l_fields: Vec<(IStr, LDestruct)> = Vec::with_capacity(fields.len());
691				for (name, into, _default) in fields {
692					let into = if let Some(inner) = into {
693						self.alloc_destruct(inner, frame_start)?
694					} else {
695						let id = self.define_local(name.clone(), None, frame_start)?;
696						LDestruct::Full(id)
697					};
698					l_fields.push((name.clone(), into));
699				}
700				// Second pass: all locals exist, so defaults can reference
701				// any sibling.
702				let l_fields: Vec<LDestructField> = l_fields
703					.into_iter()
704					.zip(fields.iter())
705					.map(|((name, into), (_n, _i, default))| {
706						let default = default.as_ref().map(|e| {
707							let mut default_taint = AnalysisResult::default();
708							Rc::new(analyze(&e.value, self, &mut default_taint))
709						});
710						LDestructField {
711							name,
712							into: Some(into),
713							default,
714						}
715					})
716					.collect();
717				let rest = match rest {
718					Some(jrsonnet_ir::DestructRest::Keep(name)) => {
719						let id = self.define_local(name.clone(), None, frame_start)?;
720						Some(LDestructRest::Keep(id))
721					}
722					Some(jrsonnet_ir::DestructRest::Drop) => Some(LDestructRest::Drop),
723					None => None,
724				};
725				Some(LDestruct::Object {
726					fields: l_fields,
727					rest,
728				})
729			}
730		}
731	}
732
733	// TODO: Proper state machine
734	fn begin_frame_alloc(&mut self) -> LocalId {
735		self.next_local_id()
736	}
737
738	fn finish_frame_alloc(&mut self, first_in_frame: LocalId) -> PendingInit {
739		let first_after_frame = self.next_local_id();
740		PendingInit {
741			first_in_frame,
742			first_after_frame,
743			bomb: DropBomb::new("PendingInit must be passed to finish_frame_init"),
744		}
745	}
746
747	/// Record the analysis of a spec's value: stamp every id bound by the
748	/// spec with `analysis`, collect the spec's same-frame references, and
749	/// append them to `closures`.
750	fn record_spec_init(
751		&mut self,
752		pending: &PendingInit,
753		destruct: &LDestruct,
754		analysis: AnalysisResult,
755		closures: &mut Closures,
756	) {
757		let mut refs: SmallVec<[LocalId; 4]> = SmallVec::new();
758		for i in pending.first_in_frame.0..pending.first_after_frame.0 {
759			let def = &mut self.local_defs[i as usize];
760			if def.scratch_referenced {
761				refs.push(LocalId(i));
762				def.scratch_referenced = false;
763			}
764		}
765
766		let mut ids_count = 0;
767		destruct.each_id(&mut |id| {
768			ids_count += 1;
769			let def = &mut self.local_defs[id.idx()];
770			debug_assert!(!def.analyzed, "sanity: local {:?} analysed twice", def.name);
771			def.analysis = analysis;
772			def.analyzed = true;
773		});
774		closures.push_spec(ids_count, &refs);
775	}
776
777	/// After all specs are analysed, propagate dependency information between
778	/// siblings to a fix-point, then switch to "body" mode.
779	fn finish_frame_init(&mut self, pending: PendingInit, closures: Closures) -> PendingBody {1125	fn top_defining_local(&self) -> LocalId {
780		let PendingInit {
781			first_in_frame,
782			first_after_frame,
783			mut bomb,
784		} = pending;
785		bomb.defuse();
786
787		debug_assert_eq!(
788			first_after_frame,
789			self.next_local_id(),
790			"frame initialisation left unfinished locals"
791		);
792
793		debug_assert_eq!(
794			closures.spec_shapes.iter().map(|(_, d)| *d).sum::<usize>(),
795			(first_after_frame.0 - first_in_frame.0) as usize,
796			"closures destruct-id counts must match frame local count"
797		);
798
799		let mut changed = true;
800		while changed {
801			changed = false;
802			for spec in closures.iter_specs() {
803				for id_raw in spec.ids.clone() {
804					let user = LocalId(id_raw);
805					for &used in spec.references {
806						changed |= self.propagate_analysis(user, used);1126		self.defining_closure().first_local
807					}1127	}
808				}
809			}
810		}
811
812		self.depth += 1;
813		PendingBody {
814			first_in_frame,
815			first_after_frame,
816			closures,
817			bomb: DropBomb::new("PendingBody must be passed to finish_frame_body"),
818		}
819	}
8201128
821	/// Merge `used`'s analysis into `user`'s analysis and record that `user`1129	/// Merge `used`'s analysis into `user`'s analysis and record that `user`
822	/// transitively depends on `used` (same-frame sibling reference).1130	/// transitively depends on `used` (same-frame sibling reference).
835			|| before_loc != user_def.analysis.local_dependent_depth1143			|| before_loc != user_def.analysis.local_dependent_depth
836	}1144	}
837
838	/// After the body is processed, drop the frame's locals and emit any
839	/// "unused local" warnings.
840	fn finish_frame_body(&mut self, pending: PendingBody) {
841		let PendingBody {
842			first_in_frame,
843			first_after_frame,
844			closures,
845			mut bomb,
846		} = pending;
847		bomb.defuse();
848		self.depth -= 1;
849
850		debug_assert_eq!(
851			first_after_frame,
852			self.next_local_id(),
853			"nested scopes must be popped before outer frames"
854		);
855
856		let mut changed = true;
857		while changed {
858			changed = false;
859			for spec in closures.iter_specs() {
860				// Effective used_at_depth for the spec = min over its ids.
861				let mut min_used_at = u32::MAX;
862				for id_raw in spec.ids.clone() {
863					min_used_at = min_used_at.min(self.local_defs[id_raw as usize].used_at_depth);
864				}
865				if min_used_at == u32::MAX {
866					continue;
867				}
868				for &used in spec.references {
869					let used_def = &mut self.local_defs[used.idx()];
870					if min_used_at < used_def.used_at_depth {
871						used_def.used_at_depth = min_used_at;
872						changed = true;
873					}
874				}
875			}
876		}
877
878		let drained: Vec<LocalDefinition> = self.local_defs.drain(first_in_frame.idx()..).collect();
879		for (i, def) in drained.iter().enumerate().rev() {
880			let id = LocalId(first_in_frame.0 + i as u32);
881			let stack = self
882				.local_by_name
883				.get_mut(&def.name)
884				.expect("local must be in name map");
885			let popped = stack.pop().expect("name stack should not be empty");
886			debug_assert_eq!(popped, id, "name stack integrity");
887			if stack.is_empty() {
888				self.local_by_name.remove(&def.name);
889			}
890
891			if def.used_at_depth == u32::MAX {
892				if def.used_by_sibling {
893					self.report_warning(
894						format!("local is only referenced by unused siblings: {}", def.name),
895						def.span.clone(),
896					);
897				} else {
898					self.report_warning(format!("unused local: {}", def.name), def.span.clone());
899				}
900			} else if def.analysis.local_dependent_depth > def.defined_at_depth
901				&& def.analysis.object_dependent_depth > def.defined_at_depth
902				&& def.defined_at_depth != 0
903			{
904				// The value doesn't depend on anything defined at or inside
905				// this local's scope - can be hoisted, unfortunately not automatically.
906				self.report_warning(
907					format!("local could be hoisted to an outer scope: {}", def.name),
908					def.span.clone(),
909				);
910			}
911		}
912	}
913}1145}
9141146
915mod names {1147mod names {
9221154
923// Object scope helpers1155// Object scope helpers
924impl AnalysisStack {1156impl AnalysisStack {
925	// TODO: proper state machine1157	#[inline]
1158	fn in_object_scope<T>(
1159		&mut self,
1160		inner: impl FnOnce(&mut AnalysisStack) -> T,
1161	) -> (ObjectUsage, ClosureShape, T) {
926	fn enter_object_scope(&mut self) -> ObjectScope {1162		fn enter_object_scope(stack: &mut AnalysisStack) -> ObjectScope {
927		let is_outermost = self.first_object_depth == u32::MAX;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");
928		let scope = ObjectScope {1168			let scope = ObjectScope {
929			this_id: self.push_pseudo_local(names::this()),1169				this_id,
930			is_outermost,1170				is_outermost,
931			prev_this_local: self.this_local,1171				prev_this_local: stack.this_local,
932			prev_dollar_alias: self.dollar_alias,1172				prev_dollar_alias: stack.dollar_alias,
933			prev_cur_self_used: self.cur_self_used,1173				prev_cur_self_used: stack.cur_self_used,
934			prev_cur_super_used: self.cur_super_used,1174				prev_cur_super_used: stack.cur_super_used,
935			prev_dollar_used: is_outermost.then_some(self.dollar_used),1175				prev_dollar_used: is_outermost.then_some(stack.dollar_used),
936			prev_last_object: self.last_object_depth,1176				prev_last_object: stack.last_object_depth,
937			prev_first_object: self.first_object_depth,1177				prev_first_object: stack.first_object_depth,
1178				closure,
938		};1179			};
9391180
940		self.this_local = Some(scope.this_id);1181			stack.this_local = Some(scope.this_id);
941		if is_outermost {1182			if is_outermost {
942			self.dollar_alias = Some(scope.this_id);1183				stack.dollar_alias = Some(scope.this_id);
943			self.first_object_depth = self.depth;1184				stack.first_object_depth = stack.depth;
944			self.dollar_used = false;1185				stack.dollar_used = false;
945		}1186			}
946		self.last_object_depth = self.depth;1187			stack.last_object_depth = stack.depth;
947		self.cur_self_used = false;1188			stack.cur_self_used = false;
948		self.cur_super_used = false;1189			stack.cur_super_used = false;
949		scope1190			scope
950	}1191		}
9511192
952	fn leave_object_scope(&mut self, scope: ObjectScope) -> ObjectUsage {1193		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;
953		let _ = self.local_defs.pop().expect("this pseudo-local exists");1209			let _ = stack.local_defs.pop().expect("this pseudo-local exists");
954		debug_assert_eq!(self.local_defs.len(), scope.this_id.0 as usize);1210			debug_assert_eq!(stack.local_defs.len(), this_id.0 as usize);
9551211
956		let set_dollar = scope.is_outermost && self.dollar_used;1212			let set_dollar = is_outermost && stack.dollar_used;
957		let usage = ObjectUsage {1213			let usage = ObjectUsage {
958			this_id: scope.this_id,
959			this_used: self.cur_self_used || self.cur_super_used || set_dollar,1214				this_used: stack.cur_self_used || stack.cur_super_used || set_dollar,
960			uses_super: self.cur_super_used,1215				uses_super: stack.cur_super_used,
961			set_dollar,1216				set_dollar,
962		};1217			};
9631218
964		self.this_local = scope.prev_this_local;1219			stack.this_local = prev_this_local;
965		self.dollar_alias = scope.prev_dollar_alias;1220			stack.dollar_alias = prev_dollar_alias;
966		self.cur_self_used = scope.prev_cur_self_used;1221			stack.cur_self_used = prev_cur_self_used;
967		self.cur_super_used = scope.prev_cur_super_used;1222			stack.cur_super_used = prev_cur_super_used;
968		if let Some(prev) = scope.prev_dollar_used {1223			if let Some(prev) = prev_dollar_used {
969			self.dollar_used = prev;1224				stack.dollar_used = prev;
970		}1225			}
971		self.last_object_depth = scope.prev_last_object;1226			stack.last_object_depth = prev_last_object;
972		self.first_object_depth = scope.prev_first_object;1227			stack.first_object_depth = prev_first_object;
9731228
1229			let frame_shape = stack.pop_closure(closure);
974		usage1230			(usage, frame_shape)
975	}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	}
9761237
977	fn push_pseudo_local(&mut self, name: IStr) -> LocalId {1238	fn push_pseudo_local(&mut self, name: IStr) -> LocalId {
978		let id = self.next_local_id();1239		let id = self.next_local_id();
986			analyzed: true,1247			analyzed: true,
987			scratch_referenced: false,1248			scratch_referenced: false,
988		});1249		});
1250		{
1251			let def = self.defining_closure_mut();
1252			let _ = def.define_local(id);
1253		}
989		id1254		id
990	}1255	}
9911256
992	fn use_this(&mut self, taint: &mut AnalysisResult) -> Option<LocalId> {1257	fn use_this(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {
993		let id = self.this_local?;1258		let id = self.this_local?;
994		self.cur_self_used = true;1259		self.cur_self_used = true;
995		self.use_pseudo_local(id, taint);1260		self.use_pseudo_local(id, taint);
996		Some(id)1261		Some(self.resolve_to_slot(id))
997	}1262	}
9981263
999	fn use_super(&mut self, taint: &mut AnalysisResult) -> Option<()> {1264	fn use_super(&mut self, taint: &mut AnalysisResult) -> Option<()> {
1003		Some(())1268		Some(())
1004	}1269	}
10051270
1006	fn use_dollar(&mut self, taint: &mut AnalysisResult) -> Option<LocalId> {1271	fn use_dollar(&mut self, taint: &mut AnalysisResult) -> Option<LSlot> {
1007		let id = self.dollar_alias?;1272		let id = self.dollar_alias?;
1008		self.dollar_used = true;1273		self.dollar_used = true;
1009		self.use_pseudo_local(id, taint);1274		self.use_pseudo_local(id, taint);
1010		Some(id)1275		Some(self.resolve_to_slot(id))
1011	}1276	}
10121277
1013	// TODO: Dedicated type for object references instead of "pseudo local" BS, idk1278	// TODO: Dedicated type for object references instead of "pseudo local" BS, idk
1020	}1285	}
1021}1286}
10221287
1288#[must_use]
1023struct ObjectScope {1289struct ObjectScope {
1024	this_id: LocalId,1290	this_id: LocalId,
1025	is_outermost: bool,1291	is_outermost: bool,
1030	prev_dollar_used: Option<bool>,1296	prev_dollar_used: Option<bool>,
1031	prev_last_object: u32,1297	prev_last_object: u32,
1032	prev_first_object: u32,1298	prev_first_object: u32,
1299	closure: ClosureOnStack,
1033}1300}
10341301
1035struct ObjectUsage {1302struct ObjectUsage {
1036	this_id: LocalId,
1037	this_used: bool,1303	this_used: bool,
1038	uses_super: bool,1304	uses_super: bool,
1039	set_dollar: bool,1305	set_dollar: bool,
1073					stack.report_error("`self` used outside of object", None);1339					stack.report_error("`self` used outside of object", None);
1074					LExpr::BadLocal("self")1340					LExpr::BadLocal("self")
1075				},1341				},
1076				LExpr::Local,1342				LExpr::Slot,
1077			),1343			),
1078			LiteralType::Super => {1344			LiteralType::Super => {
1079				if stack.use_super(taint).is_some() {1345				if stack.use_super(taint).is_some() {
1088					stack.report_error("`$` used outside of object", None);1354					stack.report_error("`$` used outside of object", None);
1089					LExpr::BadLocal("$")1355					LExpr::BadLocal("$")
1090				},1356				},
1091				LExpr::Local,1357				LExpr::Slot,
1092			),1358			),
1093			LiteralType::Null => LExpr::Null,1359			LiteralType::Null => LExpr::Null,
1094			LiteralType::True => LExpr::Bool(true),1360			LiteralType::True => LExpr::Bool(true),
1098		Expr::Num(n) => LExpr::Num(*n),1364		Expr::Num(n) => LExpr::Num(*n),
1099		Expr::Var(v) => stack1365		Expr::Var(v) => stack
1100			.use_local(&v.value, v.span.clone(), taint)1366			.use_local(&v.value, v.span.clone(), taint)
1101			.map_or_else(|| LExpr::BadLocal("ref"), LExpr::Local),1367			.map_or_else(|| LExpr::BadLocal("ref"), LExpr::Slot),
1102		Expr::Arr(a) => LExpr::Arr(Rc::new(1368		Expr::Arr(a) => {
1369			let (shape, items) = stack
1103			a.iter().map(|v| analyze(v, stack, taint)).collect(),1370				.in_using_closure(|stack| a.iter().map(|v| analyze(v, stack, taint)).collect());
1371			LExpr::Arr {
1104		)),1372				shape,
1373				items: Rc::new(items),
1374			}
1375		}
1105		Expr::ArrComp(inner, comp) => analyze_arr_comp(inner, comp, stack, taint),1376		Expr::ArrComp(inner, comp) => analyze_arr_comp(inner, comp, stack, taint),
1106		Expr::Obj(obj) => LExpr::Obj(analyze_obj_body(obj, stack, taint)),1377		Expr::Obj(obj) => LExpr::Obj(analyze_obj_body(obj, stack, taint)),
1107		Expr::ObjExtend(base, obj) => LExpr::ObjExtend(1378		Expr::ObjExtend(base, obj) => LExpr::ObjExtend(
1238	if binds.is_empty() {1509	if binds.is_empty() {
1239		return analyze(body, stack, taint);1510		return analyze(body, stack, taint);
1240	}1511	}
1512	let frame_start = stack.next_local_id();
1513	let closure = stack.push_closure_a(frame_start);
1241	let (_frame_start, l_binds, body_expr) =1514	let (l_binds, body_expr) = process_local_frame(binds, stack, taint, |stack, taint| {
1242		process_local_frame(binds, stack, taint, |stack, taint| {
1243			analyze(body, stack, taint)1515		analyze(body, stack, taint)
1244		});1516	});
1517	let frame_shape = stack.pop_closure(closure);
1245	LExpr::LocalExpr {1518	LExpr::LocalExpr(Box::new(LLocalExpr {
1519		frame_shape,
1246		binds: l_binds,1520		binds: l_binds,
1247		body: Box::new(body_expr),1521		body: body_expr,
1248	}1522	}))
1249}1523}
12501524
1251fn analyze_bind_value(1525fn analyze_bind_value(
1267	}1541	}
1268}1542}
1269
1270fn alloc_bind_destruct(
1271	bind: &BindSpec,
1272	stack: &mut AnalysisStack,
1273	frame_start: LocalId,
1274) -> Option<LDestruct> {
1275	match bind {
1276		BindSpec::Field { into, .. } => stack.alloc_destruct(into, frame_start),
1277		BindSpec::Function { name, .. } => stack
1278			.define_local(name.clone(), None, frame_start)
1279			.map(LDestruct::Full),
1280	}
1281}
12821543
1283fn process_local_frame<R>(1544fn process_local_frame<R>(
1284	binds: &[BindSpec],1545	binds: &[BindSpec],
1285	stack: &mut AnalysisStack,1546	stack: &mut AnalysisStack,
1286	taint: &mut AnalysisResult,1547	taint: &mut AnalysisResult,
1287	body_fn: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,1548	body_fn: impl FnOnce(&mut AnalysisStack, &mut AnalysisResult) -> R,
1288) -> (LocalId, Vec<LBind>, R) {1549) -> (Vec<LBind>, R) {
1289	let frame_start = stack.begin_frame_alloc();1550	let mut alloc = FrameAlloc::new(stack);
12901551
1291	let mut destructs: Vec<Option<LDestruct>> = Vec::with_capacity(binds.len());1552	let mut destructs: Vec<Option<LDestruct>> = Vec::with_capacity(binds.len());
1292	for bind in binds {1553	for bind in binds {
1293		destructs.push(alloc_bind_destruct(bind, stack, frame_start));1554		destructs.push(alloc.alloc_bind(bind));
1294	}1555	}
1295	let pending = stack.finish_frame_alloc(frame_start);1556	let mut pending = alloc.finish();
12961557
1297	let mut closures = Closures::new(frame_start);
1298	let mut l_binds: Vec<LBind> = Vec::with_capacity(binds.len());1558	let mut l_binds: Vec<LBind> = Vec::with_capacity(binds.len());
1299	for (bind, destruct) in binds.iter().zip(destructs.into_iter()) {1559	for (bind, destruct) in binds.iter().zip(destructs.into_iter()) {
1300		let mut value_taint = AnalysisResult::default();1560		let mut value_taint = AnalysisResult::default();
1301		let value = analyze_bind_value(bind, stack, &mut value_taint);1561		let (value_shape, value) = pending
1562			.stack
1563			.in_using_closure(|stack| analyze_bind_value(bind, stack, &mut value_taint));
1302		taint.taint_by(value_taint);1564		taint.taint_by(value_taint);
1303		if let Some(destruct) = destruct {1565		if let Some(destruct) = destruct {
1304			stack.record_spec_init(&pending, &destruct, value_taint, &mut closures);1566			pending.record_spec_init(&destruct, value_taint);
1305			l_binds.push(LBind {1567			l_binds.push(LBind {
1306				destruct,1568				destruct,
1569				value_shape,
1307				value: Rc::new(value),1570				value: Rc::new(value),
1308			});1571			});
1309		} else {1572		} else {
1310			closures.push_spec(0, &[]);1573			pending.closures.push_spec(0, &[]);
1311		}1574		}
1312	}1575	}
13131576
1314	let body_frame = stack.finish_frame_init(pending, closures);1577	let body_frame = pending.finish();
1315	let result = body_fn(stack, taint);1578	let result = body_fn(body_frame.stack, taint);
1316	stack.finish_frame_body(body_frame);1579	body_frame.finish();
13171580
1318	(frame_start, l_binds, result)1581	(l_binds, result)
1319}1582}
13201583
1321fn analyze_function(1584fn analyze_function(
1325	stack: &mut AnalysisStack,1588	stack: &mut AnalysisStack,
1326	taint: &mut AnalysisResult,1589	taint: &mut AnalysisResult,
1327) -> LExpr {1590) -> LExpr {
1591	let mut alloc = FrameAlloc::new(stack);
1328	let frame_start = stack.begin_frame_alloc();1592	let closure = alloc.push_locals_closure();
13291593
1330	let mut param_destructs: Vec<Option<LDestruct>> = Vec::with_capacity(params.exprs.len());1594	let mut param_destructs: Vec<Option<LDestruct>> = Vec::with_capacity(params.exprs.len());
1331	for p in &params.exprs {1595	for p in &params.exprs {
1332		param_destructs.push(stack.alloc_destruct(&p.destruct, frame_start));1596		param_destructs.push(alloc.alloc_destruct(&p.destruct));
1333	}1597	}
13341598
1335	let pending = stack.finish_frame_alloc(frame_start);1599	let mut pending = alloc.finish();
13361600
1337	let mut closures = Closures::new(frame_start);
1338	let mut l_params: Vec<LParam> = Vec::with_capacity(params.exprs.len());1601	let mut l_params: Vec<LParam> = Vec::with_capacity(params.exprs.len());
1339	for (p, destruct) in params.exprs.iter().zip(param_destructs.into_iter()) {1602	for (p, destruct) in params.exprs.iter().zip(param_destructs.into_iter()) {
1340		let mut value_taint = AnalysisResult::default();1603		let mut value_taint = AnalysisResult::default();
1341		let default = p1604		let default = p.default.as_ref().map_or_else(
1342			.default1605			|| None,
1343			.as_ref()
1344			.map(|d| Rc::new(analyze(d, stack, &mut value_taint)));1606			|d| {
1607				Some(
1608					pending
1609						.stack
1610						.in_using_closure(|stack| Rc::new(analyze(d, stack, &mut value_taint))),
1611				)
1612			},
1613		);
1345		taint.taint_by(value_taint);1614		taint.taint_by(value_taint);
1346		if let Some(destruct) = destruct {1615		if let Some(destruct) = destruct {
1349				#[cfg(feature = "exp-destruct")]1618				#[cfg(feature = "exp-destruct")]
1350				_ => None,1619				_ => None,
1351			};1620			};
1352			stack.record_spec_init(&pending, &destruct, value_taint, &mut closures);1621			pending.record_spec_init(&destruct, value_taint);
1353			l_params.push(LParam {1622			l_params.push(LParam {
1354				name,1623				name,
1355				destruct,1624				destruct,
1356				default,1625				default,
1357			});1626			});
1358		} else {1627		} else {
1359			closures.push_spec(0, &[]);1628			pending.closures.push_spec(0, &[]);
1360		}1629		}
1361	}1630	}
13621631
1363	let body_frame = stack.finish_frame_init(pending, closures);1632	let body_frame = pending.finish();
1364	let body_expr = analyze(body, stack, taint);1633	let body_expr = analyze(body, body_frame.stack, taint);
1634	body_frame.finish();
1365	stack.finish_frame_body(body_frame);1635	let body_shape = stack.pop_closure(closure);
1636
1637	// function(x) x is an identity function
1638	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].destruct
1645			&& let LExpr::Slot(LSlot::Local(s)) = &body_expr
1646			&& s == param_slot
1647		{
1648			return LExpr::IdentityFunction {};
1649		}
1650	}
13661651
1367	LExpr::Function(Rc::new(LFunction {1652	LExpr::Function(Rc::new(LFunction {
1368		name,1653		name,
1369		params: l_params,1654		params: l_params,
1370		signature: params.signature.clone(),1655		signature: params.signature.clone(),
1656		body_shape,
1371		body: Rc::new(body_expr),1657		body: Rc::new(body_expr),
1372	}))1658	}))
1373}1659}
1405		})1691		})
1406		.collect();1692		.collect();
14071693
1408	let scope = stack.enter_object_scope();
1409	let (_frame_start, l_binds, (l_asserts, l_fields)) =1694	let (usage, frame_shape, (l_binds, (l_asserts_opt, l_fields))) =
1695		stack.in_object_scope(|stack| {
1410		process_local_frame(locals, stack, taint, |stack, taint| {1696			process_local_frame(locals, stack, taint, |stack, taint| {
1697				let l_asserts_opt = if asserts.is_empty() {
1698					None
1699				} else {
1700					let (shape, l_asserts) = stack.in_using_closure(|stack| {
1411			let mut l_asserts = Vec::with_capacity(asserts.len());1701						let mut l_asserts = Vec::with_capacity(asserts.len());
1412			for a in asserts {1702						for a in asserts {
1413				let mut assert_taint = AnalysisResult::default();1703							let mut assert_taint = AnalysisResult::default();
1414				l_asserts.push(analyze_assert(a, stack, &mut assert_taint));1704							l_asserts.push(analyze_assert(a, stack, &mut assert_taint));
1415				taint.taint_by(assert_taint);1705							taint.taint_by(assert_taint);
1416			}1706						}
1707						l_asserts
1708					});
1709					Some(Rc::new(LObjAsserts {
1710						shape,
1711						asserts: l_asserts,
1712					}))
1713				};
1417			let mut l_fields = Vec::with_capacity(fields.len());1714				let mut l_fields = Vec::with_capacity(fields.len());
1418			for (f, name) in fields.iter().zip(field_names) {1715				for (f, name) in fields.iter().zip(field_names) {
1419				let value = if let Some(params) = &f.params {1716					let value = stack.in_using_closure(|stack| {
1717						if let Some(params) = &f.params {
1420					analyze_function(name.function_name(), params, &f.value, stack, taint)1718							analyze_function(name.function_name(), params, &f.value, stack, taint)
1421				} else {1719						} else {
1422					analyze(&f.value, stack, taint)1720							analyze(&f.value, stack, taint)
1423				};1721						}
1722					});
1424				l_fields.push(LFieldMember {1723					l_fields.push(LFieldMember {
1425					name,1724						name,
1426					plus: f.plus,1725						plus: f.plus,
1427					visibility: f.visibility,1726						visibility: f.visibility,
1428					value: Rc::new(value),1727						value: Rc::new(value),
1429				});1728					});
1430			}1729				}
1431			(l_asserts, l_fields)1730				(l_asserts_opt, l_fields)
1432		});1731			})
1732		});
1733	// `this` was allocated as the first local of the object's frame,
1734	// so its slot is 0 within that frame.
1433	let usage = stack.leave_object_scope(scope);1735	let this_slot = usage.this_used.then_some(LocalSlot(0));
1434	LObjMembers {1736	LObjMembers {
1737		frame_shape,
1435		this: usage.this_used.then_some(usage.this_id),1738		this: this_slot,
1436		set_dollar: usage.set_dollar,1739		set_dollar: usage.set_dollar,
1437		uses_super: usage.uses_super,1740		uses_super: usage.uses_super,
1438		locals: Rc::new(l_binds),1741		locals: Rc::new(l_binds),
1439		asserts: Rc::new(l_asserts),1742		asserts: l_asserts_opt,
1440		fields: l_fields,1743		fields: l_fields,
1441	}1744	}
1442}1745}
1452			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),1755			FieldName::Dyn(e) => LFieldName::Dyn(analyze(e, stack, taint)),
1453		};1756		};
14541757
1455		let scope = stack.enter_object_scope();
1456		let body = process_local_frame(&comp.locals, stack, taint, |stack, taint| {1758		let (usage, frame_shape, body) = stack.in_object_scope(|stack| {
1759			process_local_frame(&comp.locals, stack, taint, |stack, taint| {
1457			let value = if let Some(params) = &comp.field.params {1760				let value = stack.in_using_closure(|stack| {
1761					if let Some(params) = &comp.field.params {
1458				analyze_function(None, params, &comp.field.value, stack, taint)1762						analyze_function(None, params, &comp.field.value, stack, taint)
1459			} else {1763					} else {
1460				analyze(&comp.field.value, stack, taint)1764						analyze(&comp.field.value, stack, taint)
1461			};1765					}
1766				});
1462			LFieldMember {1767				LFieldMember {
1463				name: field_name,1768					name: field_name,
1464				plus: comp.field.plus,1769					plus: comp.field.plus,
1465				visibility: comp.field.visibility,1770					visibility: comp.field.visibility,
1466				value: Rc::new(value),1771					value: Rc::new(value),
1467			}1772				}
1468		});1773			})
1469		let usage = stack.leave_object_scope(scope);1774		});
1470		(usage, body)1775		(usage, frame_shape, body)
1471	});1776	});
1472	let (usage, (_frame_start, locals, field)) = res.inner;1777	let (usage, frame_shape, (locals, field)) = res.inner;
1778	let this_slot = usage.this_used.then_some(LocalSlot(0));
1473	LObjComp {1779	LObjComp {
1474		this: usage.this_used.then_some(usage.this_id),1780		frame_shape: Rc::new(frame_shape),
1781		this: this_slot,
1475		set_dollar: usage.set_dollar,1782		set_dollar: usage.set_dollar,
1476		uses_super: usage.uses_super,1783		uses_super: usage.uses_super,
1477		locals: Rc::new(locals),1784		locals: Rc::new(locals),
1487	taint: &mut AnalysisResult,1794	taint: &mut AnalysisResult,
1488) -> LExpr {1795) -> LExpr {
1489	let res = analyze_comp_specs(specs, stack, taint, |stack, taint| {1796	let res = analyze_comp_specs(specs, stack, taint, |stack, taint| {
1490		analyze(inner, stack, taint)1797		stack.in_using_closure(|stack| analyze(inner, stack, taint))
1491	});1798	});
1799	let (value_shape, value) = res.inner;
1492	LExpr::ArrComp(Box::new(LArrComp {1800	LExpr::ArrComp(Box::new(LArrComp {
1801		value_shape,
1493		value: Rc::new(res.inner),1802		value: Rc::new(value),
1494		compspecs: res.compspecs,1803		compspecs: res.compspecs,
1495	}))1804	}))
1496}1805}
1525				let loop_invariant = over_taint.local_dependent_depth > outer_depth;1834				let loop_invariant = over_taint.local_dependent_depth > outer_depth;
1526				taint.taint_by(over_taint);1835				taint.taint_by(over_taint);
15271836
1837				let mut alloc = FrameAlloc::new(stack);
1528				let frame_start = stack.begin_frame_alloc();1838				let closure = alloc.push_locals_closure();
1529				let Some(l_destruct) = stack.alloc_destruct(destruct, frame_start) else {1839				let Some(l_destruct) = alloc.alloc_destruct(destruct) else {
1840					stack.pop_closure(closure);
1530					return go(idx + 1, specs, outer_depth, stack, taint, inside);1841					return go(idx + 1, specs, outer_depth, stack, taint, inside);
1531				};1842				};
1532				let pending = stack.finish_frame_alloc(frame_start);1843				let mut pending = alloc.finish();
15331844
1534				let var_analysis = AnalysisResult::default();1845				let var_analysis = AnalysisResult::default();
1535				let mut closures = Closures::new(frame_start);
1536				stack.record_spec_init(&pending, &l_destruct, var_analysis, &mut closures);1846				pending.record_spec_init(&l_destruct, var_analysis);
15371847
1538				let body_frame = stack.finish_frame_init(pending, closures);1848				let body_frame = pending.finish();
1539				let (r, mut rest) = go(idx + 1, specs, outer_depth, stack, taint, inside);1849				let (r, mut rest) =
1850					go(idx + 1, specs, outer_depth, body_frame.stack, taint, inside);
1851				body_frame.finish();
1540				stack.finish_frame_body(body_frame);1852				let frame_shape = stack.pop_closure(closure);
15411853
1542				rest.insert(1854				rest.insert(
1543					0,1855					0,
1544					LCompSpec::For {1856					LCompSpec::For {
1857						frame_shape,
1545						destruct: l_destruct,1858						destruct: l_destruct,
1546						over: over_l,1859						over: over_l,
1547						loop_invariant,1860						loop_invariant,
1570		stack.define_external_local(name, id);1883		stack.define_external_local(name, id);
1571	}1884	}
1885
1886	let externals_count: u16 = stack
1887		.local_defs
1888		.len()
1889		.try_into()
1890		.expect("more than u16::MAX externals");
1891	let closure = stack.push_root_closure(externals_count);
15721892
1573	let mut taint = AnalysisResult::default();1893	let mut taint = AnalysisResult::default();
1574	let lir = analyze(expr, &mut stack, &mut taint);1894	let lir = analyze(expr, &mut stack, &mut taint);
1895
1896	let root_shape = stack.pop_closure(closure);
1897	debug_assert!(
1898		stack.closure_stack.is_empty(),
1899		"closure stack imbalance after analyze"
1900	);
15751901
1576	AnalysisReport {1902	AnalysisReport {
1577		lir,1903		lir,
1904		root_shape,
1578		root_analysis: taint,1905		root_analysis: taint,
1579		diagnostics_list: stack.diagnostics,1906		diagnostics_list: stack.diagnostics,
1580		errored: stack.errored,1907		errored: stack.errored,
1581	}1908	}
1582}1909}
15831910
1911#[cfg(test)]
1584fn render_diagnostics(src: &str, diags: &[Diagnostic]) -> String {1912fn render_diagnostics(src: &str, diags: &[Diagnostic]) -> String {
1913	use std::fmt::Write;
1914
1915	use hi_doc::{Formatting, SnippetBuilder, Text};
1916
1585	let mut out = String::new();1917	let mut out = String::new();
1586	let mut unspanned = Vec::new();1918	let mut unspanned = Vec::new();
16201952
1621pub struct AnalysisReport {1953pub struct AnalysisReport {
1622	pub lir: LExpr,1954	pub lir: LExpr,
1955	pub root_shape: ClosureShape,
1623	pub root_analysis: AnalysisResult,1956	pub root_analysis: AnalysisResult,
1624	pub diagnostics_list: Vec<Diagnostic>,1957	pub diagnostics_list: Vec<Diagnostic>,
1625	pub errored: bool,1958	pub errored: bool,