1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Machinery for hygienic macros, as described in the MTWT[1] paper.
13 //! [1] Matthew Flatt, Ryan Culpepper, David Darais, and Robert Bruce Findler.
14 //! 2012. *Macros that work together: Compile-time bindings, partial expansion,
15 //! and definition contexts*. J. Funct. Program. 22, 2 (March 2012), 181-216.
16 //! DOI=10.1017/S0956796812000093 http://dx.doi.org/10.1017/S0956796812000093
18 pub use self::SyntaxContext_::*;
20 use ast::{Ident, Mrk, Name, SyntaxContext};
22 use std::cell::RefCell;
23 use std::collections::HashMap;
24 use std::collections::hash_map::Entry::{Occupied, Vacant};
26 /// The SCTable contains a table of SyntaxContext_'s. It
27 /// represents a flattened tree structure, to avoid having
28 /// managed pointers everywhere (that caused an ICE).
29 /// the mark_memo and rename_memo fields are side-tables
30 /// that ensure that adding the same mark to the same context
31 /// gives you back the same context as before. This shouldn't
32 /// change the semantics--everything here is immutable--but
33 /// it should cut down on memory use *a lot*; applying a mark
34 /// to a tree containing 50 identifiers would otherwise generate
37 table: RefCell<Vec<SyntaxContext_>>,
38 mark_memo: RefCell<HashMap<(SyntaxContext,Mrk),SyntaxContext>>,
39 rename_memo: RefCell<HashMap<(SyntaxContext,Ident,Name),SyntaxContext>>,
42 #[derive(PartialEq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
43 pub enum SyntaxContext_ {
45 Mark (Mrk,SyntaxContext),
46 /// flattening the name and syntaxcontext into the rename...
47 /// HIDDEN INVARIANTS:
48 /// 1) the first name in a Rename node
49 /// can only be a programmer-supplied name.
50 /// 2) Every Rename node with a given Name in the
51 /// "to" slot must have the same name and context
52 /// in the "from" slot. In essence, they're all
53 /// pointers to a single "rename" event node.
54 Rename (Ident,Name,SyntaxContext),
55 /// actually, IllegalCtxt may not be necessary.
59 /// A list of ident->name renamings
60 pub type RenameList = Vec<(Ident, Name)>;
62 /// Extend a syntax context with a given mark
63 pub fn apply_mark(m: Mrk, ctxt: SyntaxContext) -> SyntaxContext {
64 with_sctable(|table| apply_mark_internal(m, ctxt, table))
67 /// Extend a syntax context with a given mark and sctable (explicit memoization)
68 fn apply_mark_internal(m: Mrk, ctxt: SyntaxContext, table: &SCTable) -> SyntaxContext {
70 * match table.mark_memo.borrow_mut().entry(key) {
71 Vacant(entry) => entry.set(idx_push(&mut *table.table.borrow_mut(), Mark(m, ctxt))),
72 Occupied(entry) => entry.into_mut(),
76 /// Extend a syntax context with a given rename
77 pub fn apply_rename(id: Ident, to:Name,
78 ctxt: SyntaxContext) -> SyntaxContext {
79 with_sctable(|table| apply_rename_internal(id, to, ctxt, table))
82 /// Extend a syntax context with a given rename and sctable (explicit memoization)
83 fn apply_rename_internal(id: Ident,
86 table: &SCTable) -> SyntaxContext {
87 let key = (ctxt, id, to);
89 * match table.rename_memo.borrow_mut().entry(key) {
90 Vacant(entry) => entry.set(idx_push(&mut *table.table.borrow_mut(), Rename(id, to, ctxt))),
91 Occupied(entry) => entry.into_mut(),
95 /// Apply a list of renamings to a context
96 // if these rename lists get long, it would make sense
97 // to consider memoizing this fold. This may come up
98 // when we add hygiene to item names.
99 pub fn apply_renames(renames: &RenameList, ctxt: SyntaxContext) -> SyntaxContext {
100 renames.iter().fold(ctxt, |ctxt, &(from, to)| {
101 apply_rename(from, to, ctxt)
105 /// Fetch the SCTable from TLS, create one if it doesn't yet exist.
106 pub fn with_sctable<T, F>(op: F) -> T where
107 F: FnOnce(&SCTable) -> T,
109 thread_local!(static SCTABLE_KEY: SCTable = new_sctable_internal());
110 SCTABLE_KEY.with(move |slot| op(slot))
113 // Make a fresh syntax context table with EmptyCtxt in slot zero
114 // and IllegalCtxt in slot one.
115 fn new_sctable_internal() -> SCTable {
117 table: RefCell::new(vec!(EmptyCtxt, IllegalCtxt)),
118 mark_memo: RefCell::new(HashMap::new()),
119 rename_memo: RefCell::new(HashMap::new()),
123 /// Print out an SCTable for debugging
124 pub fn display_sctable(table: &SCTable) {
126 for (idx,val) in table.table.borrow().iter().enumerate() {
127 error!("{:4} : {}",idx,val);
131 /// Clear the tables from TLD to reclaim memory.
132 pub fn clear_tables() {
133 with_sctable(|table| {
134 *table.table.borrow_mut() = Vec::new();
135 *table.mark_memo.borrow_mut() = HashMap::new();
136 *table.rename_memo.borrow_mut() = HashMap::new();
138 with_resolve_table_mut(|table| *table = HashMap::new());
141 /// Reset the tables to their initial state
142 pub fn reset_tables() {
143 with_sctable(|table| {
144 *table.table.borrow_mut() = vec!(EmptyCtxt, IllegalCtxt);
145 *table.mark_memo.borrow_mut() = HashMap::new();
146 *table.rename_memo.borrow_mut() = HashMap::new();
148 with_resolve_table_mut(|table| *table = HashMap::new());
151 /// Add a value to the end of a vec, return its index
152 fn idx_push<T>(vec: &mut Vec<T>, val: T) -> u32 {
154 (vec.len() - 1) as u32
157 /// Resolve a syntax object to a name, per MTWT.
158 pub fn resolve(id: Ident) -> Name {
159 with_sctable(|sctable| {
160 with_resolve_table_mut(|resolve_table| {
161 resolve_internal(id, sctable, resolve_table)
166 type ResolveTable = HashMap<(Name,SyntaxContext),Name>;
168 // okay, I admit, putting this in TLS is not so nice:
169 // fetch the SCTable from TLS, create one if it doesn't yet exist.
170 fn with_resolve_table_mut<T, F>(op: F) -> T where
171 F: FnOnce(&mut ResolveTable) -> T,
173 thread_local!(static RESOLVE_TABLE_KEY: RefCell<ResolveTable> = {
174 RefCell::new(HashMap::new())
177 RESOLVE_TABLE_KEY.with(move |slot| op(&mut *slot.borrow_mut()))
180 /// Resolve a syntax object to a name, per MTWT.
181 /// adding memoization to resolve 500+ seconds in resolve for librustc (!)
182 fn resolve_internal(id: Ident,
184 resolve_table: &mut ResolveTable) -> Name {
185 let key = (id.name, id.ctxt);
187 match resolve_table.get(&key) {
188 Some(&name) => return name,
193 let result = (*table.table.borrow())[id.ctxt as uint];
195 EmptyCtxt => id.name,
196 // ignore marks here:
198 resolve_internal(Ident{name:id.name, ctxt: subctxt},
199 table, resolve_table),
200 // do the rename if necessary:
201 Rename(Ident{name, ctxt}, toname, subctxt) => {
203 resolve_internal(Ident{name:name, ctxt:ctxt},
204 table, resolve_table);
206 resolve_internal(Ident{name:id.name, ctxt:subctxt},
207 table, resolve_table);
208 if (resolvedthis == resolvedfrom)
209 && (marksof_internal(ctxt, resolvedthis, table)
210 == marksof_internal(subctxt, resolvedthis, table)) {
216 IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
219 resolve_table.insert(key, resolved);
223 /// Compute the marks associated with a syntax context.
224 pub fn marksof(ctxt: SyntaxContext, stopname: Name) -> Vec<Mrk> {
225 with_sctable(|table| marksof_internal(ctxt, stopname, table))
228 // the internal function for computing marks
229 // it's not clear to me whether it's better to use a [] mutable
230 // vector or a cons-list for this.
231 fn marksof_internal(ctxt: SyntaxContext,
233 table: &SCTable) -> Vec<Mrk> {
234 let mut result = Vec::new();
235 let mut loopvar = ctxt;
237 let table_entry = (*table.table.borrow())[loopvar as uint];
243 xor_push(&mut result, mark);
246 Rename(_,name,tl) => {
247 // see MTWT for details on the purpose of the stopname.
248 // short version: it prevents duplication of effort.
249 if name == stopname {
255 IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
260 /// Return the outer mark for a context with a mark at the outside.
261 /// FAILS when outside is not a mark.
262 pub fn outer_mark(ctxt: SyntaxContext) -> Mrk {
263 with_sctable(|sctable| {
264 match (*sctable.table.borrow())[ctxt as uint] {
266 _ => panic!("can't retrieve outer mark when outside is not a mark")
271 /// Push a name... unless it matches the one on top, in which
272 /// case pop and discard (so two of the same marks cancel)
273 fn xor_push(marks: &mut Vec<Mrk>, mark: Mrk) {
274 if (marks.len() > 0) && (*marks.last().unwrap() == mark) {
275 marks.pop().unwrap();
284 use ast::{EMPTY_CTXT, Ident, Mrk, Name, SyntaxContext};
285 use super::{resolve, xor_push, apply_mark_internal, new_sctable_internal};
286 use super::{apply_rename_internal, apply_renames, marksof_internal, resolve_internal};
287 use super::{SCTable, EmptyCtxt, Mark, Rename, IllegalCtxt};
288 use std::collections::HashMap;
292 let mut s = Vec::new();
293 xor_push(&mut s, 14);
294 assert_eq!(s.clone(), vec!(14));
295 xor_push(&mut s, 14);
296 assert_eq!(s.clone(), Vec::new());
297 xor_push(&mut s, 14);
298 assert_eq!(s.clone(), vec!(14));
299 xor_push(&mut s, 15);
300 assert_eq!(s.clone(), vec!(14, 15));
301 xor_push(&mut s, 16);
302 assert_eq!(s.clone(), vec!(14, 15, 16));
303 xor_push(&mut s, 16);
304 assert_eq!(s.clone(), vec!(14, 15));
305 xor_push(&mut s, 15);
306 assert_eq!(s.clone(), vec!(14));
309 fn id(n: u32, s: SyntaxContext) -> Ident {
310 Ident {name: Name(n), ctxt: s}
313 // because of the SCTable, I now need a tidy way of
314 // creating syntax objects. Sigh.
315 #[derive(Clone, PartialEq, Show)]
321 // unfold a vector of TestSC values into a SCTable,
322 // returning the resulting index
323 fn unfold_test_sc(tscs : Vec<TestSC> , tail: SyntaxContext, table: &SCTable)
325 tscs.iter().rev().fold(tail, |tail : SyntaxContext, tsc : &TestSC|
327 M(mrk) => apply_mark_internal(mrk,tail,table),
328 R(ident,name) => apply_rename_internal(ident,name,tail,table)}})
331 // gather a SyntaxContext back into a vector of TestSCs
332 fn refold_test_sc(mut sc: SyntaxContext, table : &SCTable) -> Vec<TestSC> {
333 let mut result = Vec::new();
335 let table = table.table.borrow();
336 match (*table)[sc as uint] {
337 EmptyCtxt => {return result;},
343 Rename(id,name,tail) => {
344 result.push(R(id,name));
348 IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
354 fn test_unfold_refold(){
355 let mut t = new_sctable_internal();
357 let test_sc = vec!(M(3),R(id(101,0),Name(14)),M(9));
358 assert_eq!(unfold_test_sc(test_sc.clone(),EMPTY_CTXT,&mut t),4);
360 let table = t.table.borrow();
361 assert!((*table)[2] == Mark(9,0));
362 assert!((*table)[3] == Rename(id(101,0),Name(14),2));
363 assert!((*table)[4] == Mark(3,3));
365 assert_eq!(refold_test_sc(4,&t),test_sc);
368 // extend a syntax context with a sequence of marks given
369 // in a vector. v[0] will be the outermost mark.
370 fn unfold_marks(mrks: Vec<Mrk> , tail: SyntaxContext, table: &SCTable)
372 mrks.iter().rev().fold(tail, |tail:SyntaxContext, mrk:&Mrk|
373 {apply_mark_internal(*mrk,tail,table)})
376 #[test] fn unfold_marks_test() {
377 let mut t = new_sctable_internal();
379 assert_eq!(unfold_marks(vec!(3,7),EMPTY_CTXT,&mut t),3);
381 let table = t.table.borrow();
382 assert!((*table)[2] == Mark(7,0));
383 assert!((*table)[3] == Mark(3,2));
389 let stopname = Name(242);
390 let name1 = Name(243);
391 let mut t = new_sctable_internal();
392 assert_eq!(marksof_internal (EMPTY_CTXT,stopname,&t),Vec::new());
393 // FIXME #5074: ANF'd to dodge nested calls
394 { let ans = unfold_marks(vec!(4,98),EMPTY_CTXT,&mut t);
395 assert_eq! (marksof_internal (ans,stopname,&t),vec!(4,98));}
397 { let ans = unfold_marks(vec!(5,5,16),EMPTY_CTXT,&mut t);
398 assert_eq! (marksof_internal (ans,stopname,&t), vec!(16));}
399 // does nested xoring work?
400 { let ans = unfold_marks(vec!(5,10,10,5,16),EMPTY_CTXT,&mut t);
401 assert_eq! (marksof_internal (ans, stopname,&t), vec!(16));}
402 // rename where stop doesn't match:
403 { let chain = vec!(M(9),
404 R(id(name1.uint() as u32,
405 apply_mark_internal (4, EMPTY_CTXT,&mut t)),
408 let ans = unfold_test_sc(chain,EMPTY_CTXT,&mut t);
409 assert_eq! (marksof_internal (ans, stopname, &t), vec!(9,14));}
410 // rename where stop does match
411 { let name1sc = apply_mark_internal(4, EMPTY_CTXT, &mut t);
412 let chain = vec!(M(9),
413 R(id(name1.uint() as u32, name1sc),
416 let ans = unfold_test_sc(chain,EMPTY_CTXT,&mut t);
417 assert_eq! (marksof_internal (ans, stopname, &t), vec!(9)); }
422 fn resolve_tests () {
424 let mut t = new_sctable_internal();
425 let mut rt = HashMap::new();
427 assert_eq!(resolve_internal(id(a,EMPTY_CTXT),&mut t, &mut rt),Name(a));
428 // - simple ignored marks
429 { let sc = unfold_marks(vec!(1,2,3),EMPTY_CTXT,&mut t);
430 assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),Name(a));}
431 // - orthogonal rename where names don't match
432 { let sc = unfold_test_sc(vec!(R(id(50,EMPTY_CTXT),Name(51)),M(12)),EMPTY_CTXT,&mut t);
433 assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),Name(a));}
434 // - rename where names do match, but marks don't
435 { let sc1 = apply_mark_internal(1,EMPTY_CTXT,&mut t);
436 let sc = unfold_test_sc(vec!(R(id(a,sc1),Name(50)),
440 assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), Name(a));}
441 // - rename where names and marks match
442 { let sc1 = unfold_test_sc(vec!(M(1),M(2)),EMPTY_CTXT,&mut t);
443 let sc = unfold_test_sc(vec!(R(id(a,sc1),Name(50)),M(1),M(2)),EMPTY_CTXT,&mut t);
444 assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), Name(50)); }
445 // - rename where names and marks match by literal sharing
446 { let sc1 = unfold_test_sc(vec!(M(1),M(2)),EMPTY_CTXT,&mut t);
447 let sc = unfold_test_sc(vec!(R(id(a,sc1),Name(50))),sc1,&mut t);
448 assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), Name(50)); }
449 // - two renames of the same var.. can only happen if you use
450 // local-expand to prevent the inner binding from being renamed
451 // during the rename-pass caused by the first:
452 println!("about to run bad test");
453 { let sc = unfold_test_sc(vec!(R(id(a,EMPTY_CTXT),Name(50)),
454 R(id(a,EMPTY_CTXT),Name(51))),
456 assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), Name(51)); }
457 // the simplest double-rename:
458 { let a_to_a50 = apply_rename_internal(id(a,EMPTY_CTXT),Name(50),EMPTY_CTXT,&mut t);
459 let a50_to_a51 = apply_rename_internal(id(a,a_to_a50),Name(51),a_to_a50,&mut t);
460 assert_eq!(resolve_internal(id(a,a50_to_a51),&mut t, &mut rt),Name(51));
461 // mark on the outside doesn't stop rename:
462 let sc = apply_mark_internal(9,a50_to_a51,&mut t);
463 assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),Name(51));
464 // but mark on the inside does:
465 let a50_to_a51_b = unfold_test_sc(vec!(R(id(a,a_to_a50),Name(51)),
469 assert_eq!(resolve_internal(id(a,a50_to_a51_b),&mut t, &mut rt),Name(50));}
473 fn mtwt_resolve_test(){
475 assert_eq!(resolve(id(a,EMPTY_CTXT)),Name(a));
480 fn hashing_tests () {
481 let mut t = new_sctable_internal();
482 assert_eq!(apply_mark_internal(12,EMPTY_CTXT,&mut t),2);
483 assert_eq!(apply_mark_internal(13,EMPTY_CTXT,&mut t),3);
484 // using the same one again should result in the same index:
485 assert_eq!(apply_mark_internal(12,EMPTY_CTXT,&mut t),2);
486 // I'm assuming that the rename table will behave the same....
490 fn resolve_table_hashing_tests() {
491 let mut t = new_sctable_internal();
492 let mut rt = HashMap::new();
493 assert_eq!(rt.len(),0);
494 resolve_internal(id(30,EMPTY_CTXT),&mut t, &mut rt);
495 assert_eq!(rt.len(),1);
496 resolve_internal(id(39,EMPTY_CTXT),&mut t, &mut rt);
497 assert_eq!(rt.len(),2);
498 resolve_internal(id(30,EMPTY_CTXT),&mut t, &mut rt);
499 assert_eq!(rt.len(),2);
503 fn new_resolves_test() {
504 let renames = vec!((Ident{name:Name(23),ctxt:EMPTY_CTXT},Name(24)),
505 (Ident{name:Name(29),ctxt:EMPTY_CTXT},Name(29)));
506 let new_ctxt1 = apply_renames(&renames,EMPTY_CTXT);
507 assert_eq!(resolve(Ident{name:Name(23),ctxt:new_ctxt1}),Name(24));
508 assert_eq!(resolve(Ident{name:Name(29),ctxt:new_ctxt1}),Name(29));