src/libsyntax/ext/mtwt.rs

   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.
   4 //
   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.
  10
  11 //! Machinery for hygienic macros, as described in the MTWT[1] paper.
  12 //!
  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
  17
  18 pub use self::SyntaxContext_::*;
  19
  20 use ast::{Ident, Mrk, Name, SyntaxContext};
  21
  22 use std::cell::RefCell;
  23 use std::collections::HashMap;
  24
  25 /// The SCTable contains a table of SyntaxContext_'s. It
  26 /// represents a flattened tree structure, to avoid having
  27 /// managed pointers everywhere (that caused an ICE).
  28 /// the mark_memo and rename_memo fields are side-tables
  29 /// that ensure that adding the same mark to the same context
  30 /// gives you back the same context as before. This shouldn't
  31 /// change the semantics--everything here is immutable--but
  32 /// it should cut down on memory use *a lot*; applying a mark
  33 /// to a tree containing 50 identifiers would otherwise generate
  34 /// 50 new contexts
  35 pub struct SCTable {
  36     table: RefCell<Vec<SyntaxContext_>>,
  37     mark_memo: RefCell<HashMap<(SyntaxContext,Mrk),SyntaxContext>>,
  38     rename_memo: RefCell<HashMap<(SyntaxContext,Ident,Name),SyntaxContext>>,
  39 }
  40
  41 #[derive(PartialEq, RustcEncodable, RustcDecodable, Hash, Debug, Copy, Clone)]
  42 pub enum SyntaxContext_ {
  43     EmptyCtxt,
  44     Mark (Mrk,SyntaxContext),
  45     /// flattening the name and syntaxcontext into the rename...
  46     /// HIDDEN INVARIANTS:
  47     /// 1) the first name in a Rename node
  48     /// can only be a programmer-supplied name.
  49     /// 2) Every Rename node with a given Name in the
  50     /// "to" slot must have the same name and context
  51     /// in the "from" slot. In essence, they're all
  52     /// pointers to a single "rename" event node.
  53     Rename (Ident,Name,SyntaxContext),
  54     /// actually, IllegalCtxt may not be necessary.
  55     IllegalCtxt
  56 }
  57
  58 /// A list of ident->name renamings
  59 pub type RenameList = Vec<(Ident, Name)>;
  60
  61 /// Extend a syntax context with a given mark
  62 pub fn apply_mark(m: Mrk, ctxt: SyntaxContext) -> SyntaxContext {
  63     with_sctable(|table| apply_mark_internal(m, ctxt, table))
  64 }
  65
  66 /// Extend a syntax context with a given mark and sctable (explicit memoization)
  67 fn apply_mark_internal(m: Mrk, ctxt: SyntaxContext, table: &SCTable) -> SyntaxContext {
  68     let key = (ctxt, m);
  69     * table.mark_memo.borrow_mut().entry(key)
  70         .or_insert_with(|| idx_push(&mut *table.table.borrow_mut(), Mark(m, ctxt)))
  71 }
  72
  73 /// Extend a syntax context with a given rename
  74 pub fn apply_rename(id: Ident, to:Name,
  75                   ctxt: SyntaxContext) -> SyntaxContext {
  76     with_sctable(|table| apply_rename_internal(id, to, ctxt, table))
  77 }
  78
  79 /// Extend a syntax context with a given rename and sctable (explicit memoization)
  80 fn apply_rename_internal(id: Ident,
  81                        to: Name,
  82                        ctxt: SyntaxContext,
  83                        table: &SCTable) -> SyntaxContext {
  84     let key = (ctxt, id, to);
  85
  86     * table.rename_memo.borrow_mut().entry(key)
  87         .or_insert_with(|| idx_push(&mut *table.table.borrow_mut(), Rename(id, to, ctxt)))
  88 }
  89
  90 /// Apply a list of renamings to a context
  91 // if these rename lists get long, it would make sense
  92 // to consider memoizing this fold. This may come up
  93 // when we add hygiene to item names.
  94 pub fn apply_renames(renames: &RenameList, ctxt: SyntaxContext) -> SyntaxContext {
  95     renames.iter().fold(ctxt, |ctxt, &(from, to)| {
  96         apply_rename(from, to, ctxt)
  97     })
  98 }
  99
 100 /// Fetch the SCTable from TLS, create one if it doesn't yet exist.
 101 pub fn with_sctable<T, F>(op: F) -> T where
 102     F: FnOnce(&SCTable) -> T,
 103 {
 104     thread_local!(static SCTABLE_KEY: SCTable = new_sctable_internal());
 105     SCTABLE_KEY.with(move |slot| op(slot))
 106 }
 107
 108 // Make a fresh syntax context table with EmptyCtxt in slot zero
 109 // and IllegalCtxt in slot one.
 110 fn new_sctable_internal() -> SCTable {
 111     SCTable {
 112         table: RefCell::new(vec!(EmptyCtxt, IllegalCtxt)),
 113         mark_memo: RefCell::new(HashMap::new()),
 114         rename_memo: RefCell::new(HashMap::new()),
 115     }
 116 }
 117
 118 /// Print out an SCTable for debugging
 119 pub fn display_sctable(table: &SCTable) {
 120     error!("SC table:");
 121     for (idx,val) in table.table.borrow().iter().enumerate() {
 122         error!("{:4} : {:?}",idx,val);
 123     }
 124 }
 125
 126 /// Clear the tables from TLD to reclaim memory.
 127 pub fn clear_tables() {
 128     with_sctable(|table| {
 129         *table.table.borrow_mut() = Vec::new();
 130         *table.mark_memo.borrow_mut() = HashMap::new();
 131         *table.rename_memo.borrow_mut() = HashMap::new();
 132     });
 133     with_resolve_table_mut(|table| *table = HashMap::new());
 134 }
 135
 136 /// Reset the tables to their initial state
 137 pub fn reset_tables() {
 138     with_sctable(|table| {
 139         *table.table.borrow_mut() = vec!(EmptyCtxt, IllegalCtxt);
 140         *table.mark_memo.borrow_mut() = HashMap::new();
 141         *table.rename_memo.borrow_mut() = HashMap::new();
 142     });
 143     with_resolve_table_mut(|table| *table = HashMap::new());
 144 }
 145
 146 /// Add a value to the end of a vec, return its index
 147 fn idx_push<T>(vec: &mut Vec<T>, val: T) -> u32 {
 148     vec.push(val);
 149     (vec.len() - 1) as u32
 150 }
 151
 152 /// Resolve a syntax object to a name, per MTWT.
 153 pub fn resolve(id: Ident) -> Name {
 154     with_sctable(|sctable| {
 155         with_resolve_table_mut(|resolve_table| {
 156             resolve_internal(id, sctable, resolve_table)
 157         })
 158     })
 159 }
 160
 161 type ResolveTable = HashMap<(Name,SyntaxContext),Name>;
 162
 163 // okay, I admit, putting this in TLS is not so nice:
 164 // fetch the SCTable from TLS, create one if it doesn't yet exist.
 165 fn with_resolve_table_mut<T, F>(op: F) -> T where
 166     F: FnOnce(&mut ResolveTable) -> T,
 167 {
 168     thread_local!(static RESOLVE_TABLE_KEY: RefCell<ResolveTable> = {
 169         RefCell::new(HashMap::new())
 170     });
 171
 172     RESOLVE_TABLE_KEY.with(move |slot| op(&mut *slot.borrow_mut()))
 173 }
 174
 175 /// Resolve a syntax object to a name, per MTWT.
 176 /// adding memoization to resolve 500+ seconds in resolve for librustc (!)
 177 fn resolve_internal(id: Ident,
 178                     table: &SCTable,
 179                     resolve_table: &mut ResolveTable) -> Name {
 180     let key = (id.name, id.ctxt);
 181
 182     match resolve_table.get(&key) {
 183         Some(&name) => return name,
 184         None => {}
 185     }
 186
 187     let resolved = {
 188         let result = (*table.table.borrow())[id.ctxt as usize];
 189         match result {
 190             EmptyCtxt => id.name,
 191             // ignore marks here:
 192             Mark(_,subctxt) =>
 193                 resolve_internal(Ident{name:id.name, ctxt: subctxt},
 194                                  table, resolve_table),
 195             // do the rename if necessary:
 196             Rename(Ident{name, ctxt}, toname, subctxt) => {
 197                 let resolvedfrom =
 198                     resolve_internal(Ident{name:name, ctxt:ctxt},
 199                                      table, resolve_table);
 200                 let resolvedthis =
 201                     resolve_internal(Ident{name:id.name, ctxt:subctxt},
 202                                      table, resolve_table);
 203                 if (resolvedthis == resolvedfrom)
 204                     && (marksof_internal(ctxt, resolvedthis, table)
 205                         == marksof_internal(subctxt, resolvedthis, table)) {
 206                     toname
 207                 } else {
 208                     resolvedthis
 209                 }
 210             }
 211             IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
 212         }
 213     };
 214     resolve_table.insert(key, resolved);
 215     resolved
 216 }
 217
 218 /// Compute the marks associated with a syntax context.
 219 pub fn marksof(ctxt: SyntaxContext, stopname: Name) -> Vec<Mrk> {
 220     with_sctable(|table| marksof_internal(ctxt, stopname, table))
 221 }
 222
 223 // the internal function for computing marks
 224 // it's not clear to me whether it's better to use a [] mutable
 225 // vector or a cons-list for this.
 226 fn marksof_internal(ctxt: SyntaxContext,
 227                     stopname: Name,
 228                     table: &SCTable) -> Vec<Mrk> {
 229     let mut result = Vec::new();
 230     let mut loopvar = ctxt;
 231     loop {
 232         let table_entry = (*table.table.borrow())[loopvar as usize];
 233         match table_entry {
 234             EmptyCtxt => {
 235                 return result;
 236             },
 237             Mark(mark, tl) => {
 238                 xor_push(&mut result, mark);
 239                 loopvar = tl;
 240             },
 241             Rename(_,name,tl) => {
 242                 // see MTWT for details on the purpose of the stopname.
 243                 // short version: it prevents duplication of effort.
 244                 if name == stopname {
 245                     return result;
 246                 } else {
 247                     loopvar = tl;
 248                 }
 249             }
 250             IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
 251         }
 252     }
 253 }
 254
 255 /// Return the outer mark for a context with a mark at the outside.
 256 /// FAILS when outside is not a mark.
 257 pub fn outer_mark(ctxt: SyntaxContext) -> Mrk {
 258     with_sctable(|sctable| {
 259         match (*sctable.table.borrow())[ctxt as usize] {
 260             Mark(mrk, _) => mrk,
 261             _ => panic!("can't retrieve outer mark when outside is not a mark")
 262         }
 263     })
 264 }
 265
 266 /// Push a name... unless it matches the one on top, in which
 267 /// case pop and discard (so two of the same marks cancel)
 268 fn xor_push(marks: &mut Vec<Mrk>, mark: Mrk) {
 269     if (!marks.is_empty()) && (*marks.last().unwrap() == mark) {
 270         marks.pop().unwrap();
 271     } else {
 272         marks.push(mark);
 273     }
 274 }
 275
 276 #[cfg(test)]
 277 mod tests {
 278     use self::TestSC::*;
 279     use ast::{EMPTY_CTXT, Ident, Mrk, Name, SyntaxContext};
 280     use super::{resolve, xor_push, apply_mark_internal, new_sctable_internal};
 281     use super::{apply_rename_internal, apply_renames, marksof_internal, resolve_internal};
 282     use super::{SCTable, EmptyCtxt, Mark, Rename, IllegalCtxt};
 283     use std::collections::HashMap;
 284
 285     #[test]
 286     fn xorpush_test () {
 287         let mut s = Vec::new();
 288         xor_push(&mut s, 14);
 289         assert_eq!(s.clone(), [14]);
 290         xor_push(&mut s, 14);
 291         assert_eq!(s.clone(), []);
 292         xor_push(&mut s, 14);
 293         assert_eq!(s.clone(), [14]);
 294         xor_push(&mut s, 15);
 295         assert_eq!(s.clone(), [14, 15]);
 296         xor_push(&mut s, 16);
 297         assert_eq!(s.clone(), [14, 15, 16]);
 298         xor_push(&mut s, 16);
 299         assert_eq!(s.clone(), [14, 15]);
 300         xor_push(&mut s, 15);
 301         assert_eq!(s.clone(), [14]);
 302     }
 303
 304     fn id(n: u32, s: SyntaxContext) -> Ident {
 305         Ident {name: Name(n), ctxt: s}
 306     }
 307
 308     // because of the SCTable, I now need a tidy way of
 309     // creating syntax objects. Sigh.
 310     #[derive(Clone, PartialEq, Debug)]
 311     enum TestSC {
 312         M(Mrk),
 313         R(Ident,Name)
 314     }
 315
 316     // unfold a vector of TestSC values into a SCTable,
 317     // returning the resulting index
 318     fn unfold_test_sc(tscs : Vec<TestSC> , tail: SyntaxContext, table: &SCTable)
 319         -> SyntaxContext {
 320         tscs.iter().rev().fold(tail, |tail : SyntaxContext, tsc : &TestSC|
 321                   {match *tsc {
 322                       M(mrk) => apply_mark_internal(mrk,tail,table),
 323                       R(ident,name) => apply_rename_internal(ident,name,tail,table)}})
 324     }
 325
 326     // gather a SyntaxContext back into a vector of TestSCs
 327     fn refold_test_sc(mut sc: SyntaxContext, table : &SCTable) -> Vec<TestSC> {
 328         let mut result = Vec::new();
 329         loop {
 330             let table = table.table.borrow();
 331             match (*table)[sc as usize] {
 332                 EmptyCtxt => {return result;},
 333                 Mark(mrk,tail) => {
 334                     result.push(M(mrk));
 335                     sc = tail;
 336                     continue;
 337                 },
 338                 Rename(id,name,tail) => {
 339                     result.push(R(id,name));
 340                     sc = tail;
 341                     continue;
 342                 }
 343                 IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
 344             }
 345         }
 346     }
 347
 348     #[test]
 349     fn test_unfold_refold(){
 350         let mut t = new_sctable_internal();
 351
 352         let test_sc = vec!(M(3),R(id(101,0),Name(14)),M(9));
 353         assert_eq!(unfold_test_sc(test_sc.clone(),EMPTY_CTXT,&mut t),4);
 354         {
 355             let table = t.table.borrow();
 356             assert!((*table)[2] == Mark(9,0));
 357             assert!((*table)[3] == Rename(id(101,0),Name(14),2));
 358             assert!((*table)[4] == Mark(3,3));
 359         }
 360         assert_eq!(refold_test_sc(4,&t),test_sc);
 361     }
 362
 363     // extend a syntax context with a sequence of marks given
 364     // in a vector. v[0] will be the outermost mark.
 365     fn unfold_marks(mrks: Vec<Mrk> , tail: SyntaxContext, table: &SCTable)
 366                     -> SyntaxContext {
 367         mrks.iter().rev().fold(tail, |tail:SyntaxContext, mrk:&Mrk|
 368                    {apply_mark_internal(*mrk,tail,table)})
 369     }
 370
 371     #[test] fn unfold_marks_test() {
 372         let mut t = new_sctable_internal();
 373
 374         assert_eq!(unfold_marks(vec!(3,7),EMPTY_CTXT,&mut t),3);
 375         {
 376             let table = t.table.borrow();
 377             assert!((*table)[2] == Mark(7,0));
 378             assert!((*table)[3] == Mark(3,2));
 379         }
 380     }
 381
 382     #[test]
 383     fn test_marksof () {
 384         let stopname = Name(242);
 385         let name1 = Name(243);
 386         let mut t = new_sctable_internal();
 387         assert_eq!(marksof_internal (EMPTY_CTXT,stopname,&t),Vec::new());
 388         // FIXME #5074: ANF'd to dodge nested calls
 389         { let ans = unfold_marks(vec!(4,98),EMPTY_CTXT,&mut t);
 390          assert_eq! (marksof_internal (ans,stopname,&t), [4, 98]);}
 391         // does xoring work?
 392         { let ans = unfold_marks(vec!(5,5,16),EMPTY_CTXT,&mut t);
 393          assert_eq! (marksof_internal (ans,stopname,&t), [16]);}
 394         // does nested xoring work?
 395         { let ans = unfold_marks(vec!(5,10,10,5,16),EMPTY_CTXT,&mut t);
 396          assert_eq! (marksof_internal (ans, stopname,&t), [16]);}
 397         // rename where stop doesn't match:
 398         { let chain = vec!(M(9),
 399                         R(id(name1.usize() as u32,
 400                              apply_mark_internal (4, EMPTY_CTXT,&mut t)),
 401                           Name(100101102)),
 402                         M(14));
 403          let ans = unfold_test_sc(chain,EMPTY_CTXT,&mut t);
 404          assert_eq! (marksof_internal (ans, stopname, &t), [9, 14]);}
 405         // rename where stop does match
 406         { let name1sc = apply_mark_internal(4, EMPTY_CTXT, &mut t);
 407          let chain = vec!(M(9),
 408                        R(id(name1.usize() as u32, name1sc),
 409                          stopname),
 410                        M(14));
 411          let ans = unfold_test_sc(chain,EMPTY_CTXT,&mut t);
 412          assert_eq! (marksof_internal (ans, stopname, &t), [9]); }
 413     }
 414
 415
 416     #[test]
 417     fn resolve_tests () {
 418         let a = 40;
 419         let mut t = new_sctable_internal();
 420         let mut rt = HashMap::new();
 421         // - ctxt is MT
 422         assert_eq!(resolve_internal(id(a,EMPTY_CTXT),&mut t, &mut rt),Name(a));
 423         // - simple ignored marks
 424         { let sc = unfold_marks(vec!(1,2,3),EMPTY_CTXT,&mut t);
 425          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),Name(a));}
 426         // - orthogonal rename where names don't match
 427         { let sc = unfold_test_sc(vec!(R(id(50,EMPTY_CTXT),Name(51)),M(12)),EMPTY_CTXT,&mut t);
 428          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),Name(a));}
 429         // - rename where names do match, but marks don't
 430         { let sc1 = apply_mark_internal(1,EMPTY_CTXT,&mut t);
 431          let sc = unfold_test_sc(vec!(R(id(a,sc1),Name(50)),
 432                                    M(1),
 433                                    M(2)),
 434                                  EMPTY_CTXT,&mut t);
 435         assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), Name(a));}
 436         // - rename where names and marks match
 437         { let sc1 = unfold_test_sc(vec!(M(1),M(2)),EMPTY_CTXT,&mut t);
 438          let sc = unfold_test_sc(vec!(R(id(a,sc1),Name(50)),M(1),M(2)),EMPTY_CTXT,&mut t);
 439          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), Name(50)); }
 440         // - rename where names and marks match by literal sharing
 441         { let sc1 = unfold_test_sc(vec!(M(1),M(2)),EMPTY_CTXT,&mut t);
 442          let sc = unfold_test_sc(vec!(R(id(a,sc1),Name(50))),sc1,&mut t);
 443          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), Name(50)); }
 444         // - two renames of the same var.. can only happen if you use
 445         // local-expand to prevent the inner binding from being renamed
 446         // during the rename-pass caused by the first:
 447         println!("about to run bad test");
 448         { let sc = unfold_test_sc(vec!(R(id(a,EMPTY_CTXT),Name(50)),
 449                                     R(id(a,EMPTY_CTXT),Name(51))),
 450                                   EMPTY_CTXT,&mut t);
 451          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt), Name(51)); }
 452         // the simplest double-rename:
 453         { let a_to_a50 = apply_rename_internal(id(a,EMPTY_CTXT),Name(50),EMPTY_CTXT,&mut t);
 454          let a50_to_a51 = apply_rename_internal(id(a,a_to_a50),Name(51),a_to_a50,&mut t);
 455          assert_eq!(resolve_internal(id(a,a50_to_a51),&mut t, &mut rt),Name(51));
 456          // mark on the outside doesn't stop rename:
 457          let sc = apply_mark_internal(9,a50_to_a51,&mut t);
 458          assert_eq!(resolve_internal(id(a,sc),&mut t, &mut rt),Name(51));
 459          // but mark on the inside does:
 460          let a50_to_a51_b = unfold_test_sc(vec!(R(id(a,a_to_a50),Name(51)),
 461                                               M(9)),
 462                                            a_to_a50,
 463                                            &mut t);
 464          assert_eq!(resolve_internal(id(a,a50_to_a51_b),&mut t, &mut rt),Name(50));}
 465     }
 466
 467     #[test]
 468     fn mtwt_resolve_test(){
 469         let a = 40;
 470         assert_eq!(resolve(id(a,EMPTY_CTXT)),Name(a));
 471     }
 472
 473
 474     #[test]
 475     fn hashing_tests () {
 476         let mut t = new_sctable_internal();
 477         assert_eq!(apply_mark_internal(12,EMPTY_CTXT,&mut t),2);
 478         assert_eq!(apply_mark_internal(13,EMPTY_CTXT,&mut t),3);
 479         // using the same one again should result in the same index:
 480         assert_eq!(apply_mark_internal(12,EMPTY_CTXT,&mut t),2);
 481         // I'm assuming that the rename table will behave the same....
 482     }
 483
 484     #[test]
 485     fn resolve_table_hashing_tests() {
 486         let mut t = new_sctable_internal();
 487         let mut rt = HashMap::new();
 488         assert_eq!(rt.len(),0);
 489         resolve_internal(id(30,EMPTY_CTXT),&mut t, &mut rt);
 490         assert_eq!(rt.len(),1);
 491         resolve_internal(id(39,EMPTY_CTXT),&mut t, &mut rt);
 492         assert_eq!(rt.len(),2);
 493         resolve_internal(id(30,EMPTY_CTXT),&mut t, &mut rt);
 494         assert_eq!(rt.len(),2);
 495     }
 496
 497     #[test]
 498     fn new_resolves_test() {
 499         let renames = vec!((Ident{name:Name(23),ctxt:EMPTY_CTXT},Name(24)),
 500                            (Ident{name:Name(29),ctxt:EMPTY_CTXT},Name(29)));
 501         let new_ctxt1 = apply_renames(&renames,EMPTY_CTXT);
 502         assert_eq!(resolve(Ident{name:Name(23),ctxt:new_ctxt1}),Name(24));
 503         assert_eq!(resolve(Ident{name:Name(29),ctxt:new_ctxt1}),Name(29));
 504     }
 505 }