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