nickel_lang_core/transform/
free_vars.rs

1//! Annotate recursive record fields with the intersection of the set of their free variables and
2//! the fields of the record. This way, we can track dependencies between recursive fields, which
3//! make it possible in particular to avoid potential memory leaks by providing only references to
4//! the recursive fields that actually appear in the definition of each field when computing the
5//! fixpoint.
6use crate::{
7    eval::value::{Container, NickelValue, ValueContentRefMut},
8    identifier::Ident,
9    term::{
10        AnnotatedData, AppData, FunData, IndexMap, LetData, Op1Data, Op2Data, OpNData,
11        RecRecordData, StrChunk, Term, TypeAnnotation,
12        record::{Field, FieldDeps, Include, RecordDeps},
13    },
14    typ::{RecordRowF, RecordRows, RecordRowsF, Type, TypeF},
15};
16
17use std::{collections::HashSet, rc::Rc};
18
19/// Apply the full free var transformation on a term.
20pub fn transform(value: &mut NickelValue) {
21    value.collect_free_vars(&mut HashSet::new())
22}
23
24pub trait CollectFreeVars {
25    /// Collect the free variables of a term or type inside the provided hashset. Doing so, fill
26    /// the recursive record dependencies data accordingly.
27    fn collect_free_vars(&mut self, working_set: &mut HashSet<Ident>);
28}
29
30impl CollectFreeVars for NickelValue {
31    fn collect_free_vars(&mut self, free_vars: &mut HashSet<Ident>) {
32        match self.content_make_mut() {
33            ValueContentRefMut::Null(_)
34            | ValueContentRefMut::Bool(_)
35            | ValueContentRefMut::Array(Container::Empty)
36            | ValueContentRefMut::Record(Container::Empty)
37            | ValueContentRefMut::Number(_)
38            | ValueContentRefMut::String(_)
39            | ValueContentRefMut::ForeignId(_)
40            | ValueContentRefMut::SealingKey(_)
41            | ValueContentRefMut::Label(_) => (),
42            ValueContentRefMut::Array(Container::Alloc(array_data)) => {
43                for t in array_data.array.iter_mut() {
44                    t.collect_free_vars(free_vars);
45                }
46            }
47            ValueContentRefMut::Record(Container::Alloc(record)) => {
48                for t in record.fields.values_mut() {
49                    t.collect_free_vars(free_vars);
50                }
51            }
52            ValueContentRefMut::Term(term) => term.collect_free_vars(free_vars),
53            ValueContentRefMut::EnumVariant(enum_variant) => {
54                if let Some(arg) = &mut enum_variant.arg {
55                    arg.collect_free_vars(free_vars);
56                }
57            }
58            ValueContentRefMut::CustomContract(ctr) => {
59                ctr.collect_free_vars(free_vars);
60            }
61            ValueContentRefMut::Type(type_data) => {
62                type_data.typ.collect_free_vars(free_vars);
63                type_data.contract.collect_free_vars(free_vars);
64            }
65            ValueContentRefMut::Thunk(_) => {
66                unreachable!("should never see closures at the transformation stage")
67            }
68        }
69    }
70}
71
72impl CollectFreeVars for Term {
73    fn collect_free_vars(&mut self, free_vars: &mut HashSet<Ident>) {
74        match self {
75            Term::Var(id) => {
76                free_vars.insert(id.ident());
77            }
78            Term::ParseError(_)
79            | Term::RuntimeError(_)
80            | Term::Import { .. }
81            | Term::ResolvedImport(_) => (),
82            Term::Fun(data) => data.collect_free_vars(free_vars),
83            Term::Let(data) => data.collect_free_vars(free_vars),
84            Term::App(data) => data.collect_free_vars(free_vars),
85            Term::Op1(data) => data.collect_free_vars(free_vars),
86            Term::Op2(data) => data.collect_free_vars(free_vars),
87            Term::OpN(data) => data.collect_free_vars(free_vars),
88            Term::Sealed(data) => data.inner.collect_free_vars(free_vars),
89            Term::RecRecord(data) => data.collect_free_vars(free_vars),
90            Term::StrChunks(chunks) => {
91                for chunk in chunks {
92                    if let StrChunk::Expr(t, _) = chunk {
93                        t.collect_free_vars(free_vars)
94                    }
95                }
96            }
97            Term::Annotated(data) => data.collect_free_vars(free_vars),
98            Term::Closurize(v) => v.collect_free_vars(free_vars),
99        }
100    }
101}
102
103impl CollectFreeVars for Type {
104    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
105        match &mut self.typ {
106            TypeF::Dyn
107            | TypeF::Number
108            | TypeF::Bool
109            | TypeF::String
110            | TypeF::ForeignId
111            | TypeF::Symbol
112            | TypeF::Var(_)
113            | TypeF::Wildcard(_) => (),
114            TypeF::Forall { body: ty, .. }
115            | TypeF::Dict {
116                type_fields: ty, ..
117            }
118            | TypeF::Array(ty) => ty.as_mut().collect_free_vars(set),
119            // No term can appear anywhere in a enum row type, hence we can stop here.
120            TypeF::Enum(_) => (),
121            TypeF::Record(rrows) => rrows.collect_free_vars(set),
122            TypeF::Arrow(ty1, ty2) => {
123                ty1.as_mut().collect_free_vars(set);
124                ty2.as_mut().collect_free_vars(set);
125            }
126            TypeF::Contract(rt) => rt.collect_free_vars(set),
127        }
128    }
129}
130
131impl CollectFreeVars for RecordRows {
132    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
133        match &mut self.0 {
134            RecordRowsF::Empty | RecordRowsF::TailDyn | RecordRowsF::TailVar(_) => (),
135            RecordRowsF::Extend {
136                row: RecordRowF { typ, .. },
137                tail,
138            } => {
139                typ.collect_free_vars(set);
140                tail.collect_free_vars(set);
141            }
142        }
143    }
144}
145
146impl CollectFreeVars for TypeAnnotation {
147    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
148        for labeled_ty in self.iter_mut() {
149            labeled_ty.typ.collect_free_vars(set);
150        }
151    }
152}
153
154impl CollectFreeVars for Field {
155    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
156        if let Some(metadata) = &mut self.metadata.0 {
157            for labeled_ty in Rc::make_mut(metadata).annotation.iter_mut() {
158                labeled_ty.typ.collect_free_vars(set)
159            }
160        }
161
162        if let Some(ref mut value) = self.value {
163            value.collect_free_vars(set);
164        }
165    }
166}
167
168impl CollectFreeVars for Include {
169    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
170        self.metadata.annotation.collect_free_vars(set);
171    }
172}
173
174impl CollectFreeVars for FunData {
175    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
176        let mut fresh = HashSet::new();
177
178        self.body.collect_free_vars(&mut fresh);
179        fresh.remove(&self.arg.ident());
180
181        set.extend(fresh);
182    }
183}
184
185impl CollectFreeVars for LetData {
186    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
187        let mut fresh = HashSet::new();
188
189        for (_id, value) in self.bindings.iter_mut() {
190            if self.attrs.rec {
191                value.collect_free_vars(&mut fresh);
192            } else {
193                value.collect_free_vars(set);
194            }
195        }
196
197        self.body.collect_free_vars(&mut fresh);
198        for (id, _value) in &self.bindings {
199            fresh.remove(&id.ident());
200        }
201
202        set.extend(fresh);
203    }
204}
205
206impl CollectFreeVars for RecRecordData {
207    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
208        let mut fresh = HashSet::new();
209
210        let mut rec_fields: HashSet<Ident> =
211            self.record.fields.keys().map(|id| id.ident()).collect();
212        // `{include foo, [..]}` is defined to have the semantics of `let foo_ = foo in
213        // {foo = foo_, [..]}`, hence an included field also counts as a recursive field.
214        rec_fields.extend(self.includes.iter().map(|incl| incl.ident.ident()));
215
216        let mut new_deps = RecordDeps {
217            stat_fields: IndexMap::with_capacity(self.record.fields.len() + self.includes.len()),
218            dyn_fields: Vec::with_capacity(self.dyn_fields.len()),
219        };
220
221        for incl in self.includes.iter_mut() {
222            fresh.clear();
223
224            incl.collect_free_vars(&mut fresh);
225
226            new_deps
227                .stat_fields
228                .insert(incl.ident.ident(), FieldDeps::from(&fresh & &rec_fields));
229
230            set.extend(&fresh - &rec_fields);
231            set.insert(incl.ident.ident());
232        }
233
234        for (id, t) in self.record.fields.iter_mut() {
235            fresh.clear();
236
237            t.collect_free_vars(&mut fresh);
238            new_deps
239                .stat_fields
240                .insert(id.ident(), FieldDeps::from(&fresh & &rec_fields));
241
242            set.extend(&fresh - &rec_fields);
243        }
244
245        for (t1, t2) in self.dyn_fields.iter_mut() {
246            fresh.clear();
247
248            // Currently, the identifier part of a dynamic definition is not recursive,
249            // i.e. one can't write `{foo = "hey", "%{foo}" = 5}`. Hence, we add their free
250            // variables directly to the final set without taking them into account for
251            // recursive dependencies.
252            t1.collect_free_vars(set);
253            t2.collect_free_vars(&mut fresh);
254            new_deps
255                .dyn_fields
256                .push(FieldDeps::from(&fresh & &rec_fields));
257
258            set.extend(&fresh - &rec_fields);
259        }
260
261        // Even if deps were previously filled (it shouldn't), we had to recompute the free
262        // variables anyway for the nodes higher up, because `deps` alone is not sufficient
263        // to reconstruct the full set of free variables. At this point, we override it in
264        // any case.
265        self.deps = Some(new_deps);
266    }
267}
268
269impl CollectFreeVars for Op1Data {
270    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
271        self.arg.collect_free_vars(set);
272    }
273}
274
275impl CollectFreeVars for Op2Data {
276    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
277        self.arg1.collect_free_vars(set);
278        self.arg2.collect_free_vars(set);
279    }
280}
281
282impl CollectFreeVars for OpNData {
283    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
284        for t in &mut self.args {
285            t.collect_free_vars(set);
286        }
287    }
288}
289
290impl CollectFreeVars for AnnotatedData {
291    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
292        use std::rc::Rc;
293
294        for ctr in Rc::make_mut(&mut self.annot).iter_mut() {
295            ctr.typ.collect_free_vars(set)
296        }
297
298        self.inner.collect_free_vars(set);
299    }
300}
301
302impl CollectFreeVars for AppData {
303    fn collect_free_vars(&mut self, set: &mut HashSet<Ident>) {
304        self.head.collect_free_vars(set);
305        self.arg.collect_free_vars(set);
306    }
307}
nickel_lang_core/transform/free_vars.rs

nickel_lang_core/transform/
free_vars.rs
