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 use std::collections::hash_map::Entry::{Occupied, Vacant};
  25
  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
  35 /// 50 new contexts
  36 pub struct SCTable {
  37     table: RefCell<Vec<SyntaxContext_>>,
  38     mark_memo: RefCell<HashMap<(SyntaxContext,Mrk),SyntaxContext>>,
  39     rename_memo: RefCell<HashMap<(SyntaxContext,Ident,Name),SyntaxContext>>,
  40 }
  41
  42 #[deriving(PartialEq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
  43 pub enum SyntaxContext_ {
  44     EmptyCtxt,
  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.
  56     IllegalCtxt
  57 }
  58
  59 /// A list of ident->name renamings
  60 pub type RenameList = Vec<(Ident, Name)>;
  61
  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))
  65 }
  66
  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 {
  69     let key = (ctxt, m);
  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(),
  73     }
  74 }
  75
  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))
  80 }
  81
  82 /// Extend a syntax context with a given rename and sctable (explicit memoization)
  83 fn apply_rename_internal(id: Ident,
  84                        to: Name,
  85                        ctxt: SyntaxContext,
  86                        table: &SCTable) -> SyntaxContext {
  87     let key = (ctxt, id, to);
  88
  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(),
  92     }
  93 }
  94
  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)
 102     })
 103 }
 104
 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,
 108 {
 109     thread_local!(static SCTABLE_KEY: SCTable = new_sctable_internal());
 110     SCTABLE_KEY.with(move |slot| op(slot))
 111 }
 112
 113 // Make a fresh syntax context table with EmptyCtxt in slot zero
 114 // and IllegalCtxt in slot one.
 115 fn new_sctable_internal() -> SCTable {
 116     SCTable {
 117         table: RefCell::new(vec!(EmptyCtxt, IllegalCtxt)),
 118         mark_memo: RefCell::new(HashMap::new()),
 119         rename_memo: RefCell::new(HashMap::new()),
 120     }
 121 }
 122
 123 /// Print out an SCTable for debugging
 124 pub fn display_sctable(table: &SCTable) {
 125     error!("SC table:");
 126     for (idx,val) in table.table.borrow().iter().enumerate() {
 127         error!("{:4} : {}",idx,val);
 128     }
 129 }
 130
 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();
 137     });
 138     with_resolve_table_mut(|table| *table = HashMap::new());
 139 }
 140
 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();
 147     });
 148     with_resolve_table_mut(|table| *table = HashMap::new());
 149 }
 150
 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 {
 153     vec.push(val);
 154     (vec.len() - 1) as u32
 155 }
 156
 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)
 162         })
 163     })
 164 }
 165
 166 type ResolveTable = HashMap<(Name,SyntaxContext),Name>;
 167
 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,
 172 {
 173     thread_local!(static RESOLVE_TABLE_KEY: RefCell<ResolveTable> = {
 174         RefCell::new(HashMap::new())
 175     });
 176
 177     RESOLVE_TABLE_KEY.with(move |slot| op(&mut *slot.borrow_mut()))
 178 }
 179
 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,
 183                     table: &SCTable,
 184                     resolve_table: &mut ResolveTable) -> Name {
 185     let key = (id.name, id.ctxt);
 186
 187     match resolve_table.get(&key) {
 188         Some(&name) => return name,
 189         None => {}
 190     }
 191
 192     let resolved = {
 193         let result = (*table.table.borrow())[id.ctxt as uint];
 194         match result {
 195             EmptyCtxt => id.name,
 196             // ignore marks here:
 197             Mark(_,subctxt) =>
 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) => {
 202                 let resolvedfrom =
 203                     resolve_internal(Ident{name:name, ctxt:ctxt},
 204                                      table, resolve_table);
 205                 let resolvedthis =
 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)) {
 211                     toname
 212                 } else {
 213                     resolvedthis
 214                 }
 215             }
 216             IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
 217         }
 218     };
 219     resolve_table.insert(key, resolved);
 220     resolved
 221 }
 222
 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))
 226 }
 227
 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,
 232                     stopname: Name,
 233                     table: &SCTable) -> Vec<Mrk> {
 234     let mut result = Vec::new();
 235     let mut loopvar = ctxt;
 236     loop {
 237         let table_entry = (*table.table.borrow())[loopvar as uint];
 238         match table_entry {
 239             EmptyCtxt => {
 240                 return result;
 241             },
 242             Mark(mark, tl) => {
 243                 xor_push(&mut result, mark);
 244                 loopvar = tl;
 245             },
 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 {
 250                     return result;
 251                 } else {
 252                     loopvar = tl;
 253                 }
 254             }
 255             IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
 256         }
 257     }
 258 }
 259
 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] {
 265             Mark(mrk, _) => mrk,
 266             _ => panic!("can't retrieve outer mark when outside is not a mark")
 267         }
 268     })
 269 }
 270
 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();
 276     } else {
 277         marks.push(mark);
 278     }
 279 }
 280
 281 #[cfg(test)]
 282 mod tests {
 283     use self::TestSC::*;
 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;
 289
 290     #[test]
 291     fn xorpush_test () {
 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));
 307     }
 308
 309     fn id(n: u32, s: SyntaxContext) -> Ident {
 310         Ident {name: Name(n), ctxt: s}
 311     }
 312
 313     // because of the SCTable, I now need a tidy way of
 314     // creating syntax objects. Sigh.
 315     #[deriving(Clone, PartialEq, Show)]
 316     enum TestSC {
 317         M(Mrk),
 318         R(Ident,Name)
 319     }
 320
 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)
 324         -> SyntaxContext {
 325         tscs.iter().rev().fold(tail, |tail : SyntaxContext, tsc : &TestSC|
 326                   {match *tsc {
 327                       M(mrk) => apply_mark_internal(mrk,tail,table),
 328                       R(ident,name) => apply_rename_internal(ident,name,tail,table)}})
 329     }
 330
 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();
 334         loop {
 335             let table = table.table.borrow();
 336             match (*table)[sc as uint] {
 337                 EmptyCtxt => {return result;},
 338                 Mark(mrk,tail) => {
 339                     result.push(M(mrk));
 340                     sc = tail;
 341                     continue;
 342                 },
 343                 Rename(id,name,tail) => {
 344                     result.push(R(id,name));
 345                     sc = tail;
 346                     continue;
 347                 }
 348                 IllegalCtxt => panic!("expected resolvable context, got IllegalCtxt")
 349             }
 350         }
 351     }
 352
 353     #[test]
 354     fn test_unfold_refold(){
 355         let mut t = new_sctable_internal();
 356
 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);
 359         {
 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));
 364         }
 365         assert_eq!(refold_test_sc(4,&t),test_sc);
 366     }
 367
 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)
 371                     -> SyntaxContext {
 372         mrks.iter().rev().fold(tail, |tail:SyntaxContext, mrk:&Mrk|
 373                    {apply_mark_internal(*mrk,tail,table)})
 374     }
 375
 376     #[test] fn unfold_marks_test() {
 377         let mut t = new_sctable_internal();
 378
 379         assert_eq!(unfold_marks(vec!(3,7),EMPTY_CTXT,&mut t),3);
 380         {
 381             let table = t.table.borrow();
 382             assert!((*table)[2] == Mark(7,0));
 383             assert!((*table)[3] == Mark(3,2));
 384         }
 385     }
 386
 387     #[test]
 388     fn test_marksof () {
 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));}
 396         // does xoring work?
 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)),
 406                           Name(100101102)),
 407                         M(14));
 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),
 414                          stopname),
 415                        M(14));
 416          let ans = unfold_test_sc(chain,EMPTY_CTXT,&mut t);
 417          assert_eq! (marksof_internal (ans, stopname, &t), vec!(9)); }
 418     }
 419
 420
 421     #[test]
 422     fn resolve_tests () {
 423         let a = 40;
 424         let mut t = new_sctable_internal();
 425         let mut rt = HashMap::new();
 426         // - ctxt is MT
 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)),
 437                                    M(1),
 438                                    M(2)),
 439                                  EMPTY_CTXT,&mut t);
 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))),
 455                                   EMPTY_CTXT,&mut t);
 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)),
 466                                               M(9)),
 467                                            a_to_a50,
 468                                            &mut t);
 469          assert_eq!(resolve_internal(id(a,a50_to_a51_b),&mut t, &mut rt),Name(50));}
 470     }
 471
 472     #[test]
 473     fn mtwt_resolve_test(){
 474         let a = 40;
 475         assert_eq!(resolve(id(a,EMPTY_CTXT)),Name(a));
 476     }
 477
 478
 479     #[test]
 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....
 487     }
 488
 489     #[test]
 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);
 500     }
 501
 502     #[test]
 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));
 509     }
 510 }