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