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