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