src/librustc/middle/dataflow.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
  12 /*!
  13  * A module for propagating forward dataflow information. The analysis
  14  * assumes that the items to be propagated can be represented as bits
  15  * and thus uses bitvectors. Your job is simply to specify the so-called
  16  * GEN and KILL bits for each expression.
  17  */
  18
  19 pub use self::EntryOrExit::*;
  20
  21 use middle::cfg;
  22 use middle::cfg::CFGIndex;
  23 use middle::ty;
  24 use std::io;
  25 use std::uint;
  26 use syntax::ast;
  27 use syntax::ast_util::IdRange;
  28 use syntax::visit;
  29 use syntax::print::{pp, pprust};
  30 use util::nodemap::NodeMap;
  31
  32 #[deriving(Show)]
  33 pub enum EntryOrExit { Entry, Exit }
  34
  35 #[deriving(Clone)]
  36 pub struct DataFlowContext<'a, 'tcx: 'a, O> {
  37     tcx: &'a ty::ctxt<'tcx>,
  38
  39     /// a name for the analysis using this dataflow instance
  40     analysis_name: &'static str,
  41
  42     /// the data flow operator
  43     oper: O,
  44
  45     /// number of bits to propagate per id
  46     bits_per_id: uint,
  47
  48     /// number of words we will use to store bits_per_id.
  49     /// equal to bits_per_id/uint::BITS rounded up.
  50     words_per_id: uint,
  51
  52     // mapping from node to cfg node index
  53     // FIXME (#6298): Shouldn't this go with CFG?
  54     nodeid_to_index: NodeMap<CFGIndex>,
  55
  56     // Bit sets per cfg node.  The following three fields (`gens`, `kills`,
  57     // and `on_entry`) all have the same structure. For each id in
  58     // `id_range`, there is a range of words equal to `words_per_id`.
  59     // So, to access the bits for any given id, you take a slice of
  60     // the full vector (see the method `compute_id_range()`).
  61
  62     /// bits generated as we exit the cfg node. Updated by `add_gen()`.
  63     gens: Vec<uint>,
  64
  65     /// bits killed as we exit the cfg node. Updated by `add_kill()`.
  66     kills: Vec<uint>,
  67
  68     /// bits that are valid on entry to the cfg node. Updated by
  69     /// `propagate()`.
  70     on_entry: Vec<uint>,
  71 }
  72
  73 pub trait BitwiseOperator {
  74     /// Joins two predecessor bits together, typically either `|` or `&`
  75     fn join(&self, succ: uint, pred: uint) -> uint;
  76 }
  77
  78 /// Parameterization for the precise form of data flow that is used.
  79 pub trait DataFlowOperator : BitwiseOperator {
  80     /// Specifies the initial value for each bit in the `on_entry` set
  81     fn initial_value(&self) -> bool;
  82 }
  83
  84 struct PropagationContext<'a, 'b: 'a, 'tcx: 'b, O: 'a> {
  85     dfcx: &'a mut DataFlowContext<'b, 'tcx, O>,
  86     changed: bool
  87 }
  88
  89 fn to_cfgidx_or_die(id: ast::NodeId, index: &NodeMap<CFGIndex>) -> CFGIndex {
  90     let opt_cfgindex = index.get(&id).map(|&i|i);
  91     opt_cfgindex.unwrap_or_else(|| {
  92         panic!("nodeid_to_index does not have entry for NodeId {}", id);
  93     })
  94 }
  95
  96 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
  97     fn has_bitset_for_nodeid(&self, n: ast::NodeId) -> bool {
  98         assert!(n != ast::DUMMY_NODE_ID);
  99         self.nodeid_to_index.contains_key(&n)
 100     }
 101 }
 102
 103 impl<'a, 'tcx, O:DataFlowOperator> pprust::PpAnn for DataFlowContext<'a, 'tcx, O> {
 104     fn pre(&self,
 105            ps: &mut pprust::State,
 106            node: pprust::AnnNode) -> io::IoResult<()> {
 107         let id = match node {
 108             pprust::NodeIdent(_) | pprust::NodeName(_) => 0,
 109             pprust::NodeExpr(expr) => expr.id,
 110             pprust::NodeBlock(blk) => blk.id,
 111             pprust::NodeItem(_) => 0,
 112             pprust::NodePat(pat) => pat.id
 113         };
 114
 115         if self.has_bitset_for_nodeid(id) {
 116             assert!(self.bits_per_id > 0);
 117             let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
 118             let (start, end) = self.compute_id_range(cfgidx);
 119             let on_entry = self.on_entry.slice(start, end);
 120             let entry_str = bits_to_string(on_entry);
 121
 122             let gens = self.gens.slice(start, end);
 123             let gens_str = if gens.iter().any(|&u| u != 0) {
 124                 format!(" gen: {}", bits_to_string(gens))
 125             } else {
 126                 "".to_string()
 127             };
 128
 129             let kills = self.kills.slice(start, end);
 130             let kills_str = if kills.iter().any(|&u| u != 0) {
 131                 format!(" kill: {}", bits_to_string(kills))
 132             } else {
 133                 "".to_string()
 134             };
 135
 136             try!(ps.synth_comment(format!("id {}: {}{}{}", id, entry_str,
 137                                           gens_str, kills_str)));
 138             try!(pp::space(&mut ps.s));
 139         }
 140         Ok(())
 141     }
 142 }
 143
 144 fn build_nodeid_to_index(decl: Option<&ast::FnDecl>,
 145                          cfg: &cfg::CFG) -> NodeMap<CFGIndex> {
 146     let mut index = NodeMap::new();
 147
 148     // FIXME (#6298): Would it be better to fold formals from decl
 149     // into cfg itself?  i.e. introduce a fn-based flow-graph in
 150     // addition to the current block-based flow-graph, rather than
 151     // have to put traversals like this here?
 152     match decl {
 153         None => {}
 154         Some(decl) => add_entries_from_fn_decl(&mut index, decl, cfg.entry)
 155     }
 156
 157     cfg.graph.each_node(|node_idx, node| {
 158         if node.data.id != ast::DUMMY_NODE_ID {
 159             index.insert(node.data.id, node_idx);
 160         }
 161         true
 162     });
 163
 164     return index;
 165
 166     fn add_entries_from_fn_decl(index: &mut NodeMap<CFGIndex>,
 167                                 decl: &ast::FnDecl,
 168                                 entry: CFGIndex) {
 169         //! add mappings from the ast nodes for the formal bindings to
 170         //! the entry-node in the graph.
 171         struct Formals<'a> {
 172             entry: CFGIndex,
 173             index: &'a mut NodeMap<CFGIndex>,
 174         }
 175         let mut formals = Formals { entry: entry, index: index };
 176         visit::walk_fn_decl(&mut formals, decl);
 177         impl<'a, 'v> visit::Visitor<'v> for Formals<'a> {
 178             fn visit_pat(&mut self, p: &ast::Pat) {
 179                 self.index.insert(p.id, self.entry);
 180                 visit::walk_pat(self, p)
 181             }
 182         }
 183     }
 184 }
 185
 186 impl<'a, 'tcx, O:DataFlowOperator> DataFlowContext<'a, 'tcx, O> {
 187     pub fn new(tcx: &'a ty::ctxt<'tcx>,
 188                analysis_name: &'static str,
 189                decl: Option<&ast::FnDecl>,
 190                cfg: &cfg::CFG,
 191                oper: O,
 192                id_range: IdRange,
 193                bits_per_id: uint) -> DataFlowContext<'a, 'tcx, O> {
 194         let words_per_id = (bits_per_id + uint::BITS - 1) / uint::BITS;
 195         let num_nodes = cfg.graph.all_nodes().len();
 196
 197         debug!("DataFlowContext::new(analysis_name: {}, id_range={}, \
 198                                      bits_per_id={}, words_per_id={}) \
 199                                      num_nodes: {}",
 200                analysis_name, id_range, bits_per_id, words_per_id,
 201                num_nodes);
 202
 203         let entry = if oper.initial_value() { uint::MAX } else {0};
 204
 205         let gens = Vec::from_elem(num_nodes * words_per_id, 0);
 206         let kills = Vec::from_elem(num_nodes * words_per_id, 0);
 207         let on_entry = Vec::from_elem(num_nodes * words_per_id, entry);
 208
 209         let nodeid_to_index = build_nodeid_to_index(decl, cfg);
 210
 211         DataFlowContext {
 212             tcx: tcx,
 213             analysis_name: analysis_name,
 214             words_per_id: words_per_id,
 215             nodeid_to_index: nodeid_to_index,
 216             bits_per_id: bits_per_id,
 217             oper: oper,
 218             gens: gens,
 219             kills: kills,
 220             on_entry: on_entry
 221         }
 222     }
 223
 224     pub fn add_gen(&mut self, id: ast::NodeId, bit: uint) {
 225         //! Indicates that `id` generates `bit`
 226         debug!("{} add_gen(id={}, bit={})",
 227                self.analysis_name, id, bit);
 228         assert!(self.nodeid_to_index.contains_key(&id));
 229         assert!(self.bits_per_id > 0);
 230
 231         let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
 232         let (start, end) = self.compute_id_range(cfgidx);
 233         let gens = self.gens.slice_mut(start, end);
 234         set_bit(gens, bit);
 235     }
 236
 237     pub fn add_kill(&mut self, id: ast::NodeId, bit: uint) {
 238         //! Indicates that `id` kills `bit`
 239         debug!("{} add_kill(id={}, bit={})",
 240                self.analysis_name, id, bit);
 241         assert!(self.nodeid_to_index.contains_key(&id));
 242         assert!(self.bits_per_id > 0);
 243
 244         let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
 245         let (start, end) = self.compute_id_range(cfgidx);
 246         let kills = self.kills.slice_mut(start, end);
 247         set_bit(kills, bit);
 248     }
 249
 250     fn apply_gen_kill(&self, cfgidx: CFGIndex, bits: &mut [uint]) {
 251         //! Applies the gen and kill sets for `cfgidx` to `bits`
 252         debug!("{} apply_gen_kill(cfgidx={}, bits={}) [before]",
 253                self.analysis_name, cfgidx, mut_bits_to_string(bits));
 254         assert!(self.bits_per_id > 0);
 255
 256         let (start, end) = self.compute_id_range(cfgidx);
 257         let gens = self.gens.slice(start, end);
 258         bitwise(bits, gens, &Union);
 259         let kills = self.kills.slice(start, end);
 260         bitwise(bits, kills, &Subtract);
 261
 262         debug!("{} apply_gen_kill(cfgidx={}, bits={}) [after]",
 263                self.analysis_name, cfgidx, mut_bits_to_string(bits));
 264     }
 265
 266     fn compute_id_range(&self, cfgidx: CFGIndex) -> (uint, uint) {
 267         let n = cfgidx.node_id();
 268         let start = n * self.words_per_id;
 269         let end = start + self.words_per_id;
 270
 271         assert!(start < self.gens.len());
 272         assert!(end <= self.gens.len());
 273         assert!(self.gens.len() == self.kills.len());
 274         assert!(self.gens.len() == self.on_entry.len());
 275
 276         (start, end)
 277     }
 278
 279
 280     pub fn each_bit_on_entry(&self,
 281                              id: ast::NodeId,
 282                              f: |uint| -> bool)
 283                              -> bool {
 284         //! Iterates through each bit that is set on entry to `id`.
 285         //! Only useful after `propagate()` has been called.
 286         if !self.has_bitset_for_nodeid(id) {
 287             return true;
 288         }
 289         let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
 290         self.each_bit_for_node(Entry, cfgidx, f)
 291     }
 292
 293     pub fn each_bit_for_node(&self,
 294                              e: EntryOrExit,
 295                              cfgidx: CFGIndex,
 296                              f: |uint| -> bool)
 297                              -> bool {
 298         //! Iterates through each bit that is set on entry/exit to `cfgidx`.
 299         //! Only useful after `propagate()` has been called.
 300
 301         if self.bits_per_id == 0 {
 302             // Skip the surprisingly common degenerate case.  (Note
 303             // compute_id_range requires self.words_per_id > 0.)
 304             return true;
 305         }
 306
 307         let (start, end) = self.compute_id_range(cfgidx);
 308         let on_entry = self.on_entry.slice(start, end);
 309         let temp_bits;
 310         let slice = match e {
 311             Entry => on_entry,
 312             Exit => {
 313                 let mut t = on_entry.to_vec();
 314                 self.apply_gen_kill(cfgidx, t.as_mut_slice());
 315                 temp_bits = t;
 316                 temp_bits.as_slice()
 317             }
 318         };
 319         debug!("{} each_bit_for_node({}, cfgidx={}) bits={}",
 320                self.analysis_name, e, cfgidx, bits_to_string(slice));
 321         self.each_bit(slice, f)
 322     }
 323
 324     pub fn each_gen_bit(&self, id: ast::NodeId, f: |uint| -> bool)
 325                         -> bool {
 326         //! Iterates through each bit in the gen set for `id`.
 327         if !self.has_bitset_for_nodeid(id) {
 328             return true;
 329         }
 330
 331         if self.bits_per_id == 0 {
 332             // Skip the surprisingly common degenerate case.  (Note
 333             // compute_id_range requires self.words_per_id > 0.)
 334             return true;
 335         }
 336
 337         let cfgidx = to_cfgidx_or_die(id, &self.nodeid_to_index);
 338         let (start, end) = self.compute_id_range(cfgidx);
 339         let gens = self.gens.slice(start, end);
 340         debug!("{} each_gen_bit(id={}, gens={})",
 341                self.analysis_name, id, bits_to_string(gens));
 342         self.each_bit(gens, f)
 343     }
 344
 345     fn each_bit(&self, words: &[uint], f: |uint| -> bool) -> bool {
 346         //! Helper for iterating over the bits in a bit set.
 347         //! Returns false on the first call to `f` that returns false;
 348         //! if all calls to `f` return true, then returns true.
 349
 350         for (word_index, &word) in words.iter().enumerate() {
 351             if word != 0 {
 352                 let base_index = word_index * uint::BITS;
 353                 for offset in range(0u, uint::BITS) {
 354                     let bit = 1 << offset;
 355                     if (word & bit) != 0 {
 356                         // NB: we round up the total number of bits
 357                         // that we store in any given bit set so that
 358                         // it is an even multiple of uint::BITS.  This
 359                         // means that there may be some stray bits at
 360                         // the end that do not correspond to any
 361                         // actual value.  So before we callback, check
 362                         // whether the bit_index is greater than the
 363                         // actual value the user specified and stop
 364                         // iterating if so.
 365                         let bit_index = base_index + offset;
 366                         if bit_index >= self.bits_per_id {
 367                             return true;
 368                         } else if !f(bit_index) {
 369                             return false;
 370                         }
 371                     }
 372                 }
 373             }
 374         }
 375         return true;
 376     }
 377
 378     pub fn add_kills_from_flow_exits(&mut self, cfg: &cfg::CFG) {
 379         //! Whenever you have a `break` or `continue` statement, flow
 380         //! exits through any number of enclosing scopes on its way to
 381         //! the new destination. This function infers the kill bits of
 382         //! those control operators based on the kill bits associated
 383         //! with those scopes.
 384         //!
 385         //! This is usually called (if it is called at all), after
 386         //! all add_gen and add_kill calls, but before propagate.
 387
 388         debug!("{} add_kills_from_flow_exits", self.analysis_name);
 389         if self.bits_per_id == 0 {
 390             // Skip the surprisingly common degenerate case.  (Note
 391             // compute_id_range requires self.words_per_id > 0.)
 392             return;
 393         }
 394         cfg.graph.each_edge(|_edge_index, edge| {
 395             let flow_exit = edge.source();
 396             let (start, end) = self.compute_id_range(flow_exit);
 397             let mut orig_kills = self.kills.slice(start, end).to_vec();
 398
 399             let mut changed = false;
 400             for &node_id in edge.data.exiting_scopes.iter() {
 401                 let opt_cfg_idx = self.nodeid_to_index.get(&node_id).map(|&i|i);
 402                 match opt_cfg_idx {
 403                     Some(cfg_idx) => {
 404                         let (start, end) = self.compute_id_range(cfg_idx);
 405                         let kills = self.kills.slice(start, end);
 406                         if bitwise(orig_kills.as_mut_slice(), kills, &Union) {
 407                             changed = true;
 408                         }
 409                     }
 410                     None => {
 411                         debug!("{} add_kills_from_flow_exits flow_exit={} \
 412                                 no cfg_idx for exiting_scope={}",
 413                                self.analysis_name, flow_exit, node_id);
 414                     }
 415                 }
 416             }
 417
 418             if changed {
 419                 let bits = self.kills.slice_mut(start, end);
 420                 debug!("{} add_kills_from_flow_exits flow_exit={} bits={} [before]",
 421                        self.analysis_name, flow_exit, mut_bits_to_string(bits));
 422                 bits.clone_from_slice(orig_kills.as_slice());
 423                 debug!("{} add_kills_from_flow_exits flow_exit={} bits={} [after]",
 424                        self.analysis_name, flow_exit, mut_bits_to_string(bits));
 425             }
 426             true
 427         });
 428     }
 429 }
 430
 431 impl<'a, 'tcx, O:DataFlowOperator+Clone+'static> DataFlowContext<'a, 'tcx, O> {
 432 //                                ^^^^^^^^^^^^^ only needed for pretty printing
 433     pub fn propagate(&mut self, cfg: &cfg::CFG, blk: &ast::Block) {
 434         //! Performs the data flow analysis.
 435
 436         if self.bits_per_id == 0 {
 437             // Optimize the surprisingly common degenerate case.
 438             return;
 439         }
 440
 441         {
 442             let words_per_id = self.words_per_id;
 443             let mut propcx = PropagationContext {
 444                 dfcx: &mut *self,
 445                 changed: true
 446             };
 447
 448             let mut temp = Vec::from_elem(words_per_id, 0u);
 449             while propcx.changed {
 450                 propcx.changed = false;
 451                 propcx.reset(temp.as_mut_slice());
 452                 propcx.walk_cfg(cfg, temp.as_mut_slice());
 453             }
 454         }
 455
 456         debug!("Dataflow result for {}:", self.analysis_name);
 457         debug!("{}", {
 458             self.pretty_print_to(box io::stderr(), blk).unwrap();
 459             ""
 460         });
 461     }
 462
 463     fn pretty_print_to(&self, wr: Box<io::Writer+'static>,
 464                        blk: &ast::Block) -> io::IoResult<()> {
 465         let mut ps = pprust::rust_printer_annotated(wr, self);
 466         try!(ps.cbox(pprust::indent_unit));
 467         try!(ps.ibox(0u));
 468         try!(ps.print_block(blk));
 469         pp::eof(&mut ps.s)
 470     }
 471 }
 472
 473 impl<'a, 'b, 'tcx, O:DataFlowOperator> PropagationContext<'a, 'b, 'tcx, O> {
 474     fn walk_cfg(&mut self,
 475                 cfg: &cfg::CFG,
 476                 in_out: &mut [uint]) {
 477         debug!("DataFlowContext::walk_cfg(in_out={}) {}",
 478                bits_to_string(in_out), self.dfcx.analysis_name);
 479         assert!(self.dfcx.bits_per_id > 0);
 480
 481         cfg.graph.each_node(|node_index, node| {
 482             debug!("DataFlowContext::walk_cfg idx={} id={} begin in_out={}",
 483                    node_index, node.data.id, bits_to_string(in_out));
 484
 485             let (start, end) = self.dfcx.compute_id_range(node_index);
 486
 487             // Initialize local bitvector with state on-entry.
 488             in_out.clone_from_slice(self.dfcx.on_entry.slice(start, end));
 489
 490             // Compute state on-exit by applying transfer function to
 491             // state on-entry.
 492             self.dfcx.apply_gen_kill(node_index, in_out);
 493
 494             // Propagate state on-exit from node into its successors.
 495             self.propagate_bits_into_graph_successors_of(in_out, cfg, node_index);
 496             true // continue to next node
 497         });
 498     }
 499
 500     fn reset(&mut self, bits: &mut [uint]) {
 501         let e = if self.dfcx.oper.initial_value() {uint::MAX} else {0};
 502         for b in bits.iter_mut() {
 503             *b = e;
 504         }
 505     }
 506
 507     fn propagate_bits_into_graph_successors_of(&mut self,
 508                                                pred_bits: &[uint],
 509                                                cfg: &cfg::CFG,
 510                                                cfgidx: CFGIndex) {
 511         cfg.graph.each_outgoing_edge(cfgidx, |_e_idx, edge| {
 512             self.propagate_bits_into_entry_set_for(pred_bits, edge);
 513             true
 514         });
 515     }
 516
 517     fn propagate_bits_into_entry_set_for(&mut self,
 518                                          pred_bits: &[uint],
 519                                          edge: &cfg::CFGEdge) {
 520         let source = edge.source();
 521         let cfgidx = edge.target();
 522         debug!("{} propagate_bits_into_entry_set_for(pred_bits={}, {} to {})",
 523                self.dfcx.analysis_name, bits_to_string(pred_bits), source, cfgidx);
 524         assert!(self.dfcx.bits_per_id > 0);
 525
 526         let (start, end) = self.dfcx.compute_id_range(cfgidx);
 527         let changed = {
 528             // (scoping mutable borrow of self.dfcx.on_entry)
 529             let on_entry = self.dfcx.on_entry.slice_mut(start, end);
 530             bitwise(on_entry, pred_bits, &self.dfcx.oper)
 531         };
 532         if changed {
 533             debug!("{} changed entry set for {} to {}",
 534                    self.dfcx.analysis_name, cfgidx,
 535                    bits_to_string(self.dfcx.on_entry.slice(start, end)));
 536             self.changed = true;
 537         }
 538     }
 539 }
 540
 541 fn mut_bits_to_string(words: &mut [uint]) -> String {
 542     bits_to_string(words)
 543 }
 544
 545 fn bits_to_string(words: &[uint]) -> String {
 546     let mut result = String::new();
 547     let mut sep = '[';
 548
 549     // Note: this is a little endian printout of bytes.
 550
 551     for &word in words.iter() {
 552         let mut v = word;
 553         for _ in range(0u, uint::BYTES) {
 554             result.push(sep);
 555             result.push_str(format!("{:02x}", v & 0xFF).as_slice());
 556             v >>= 8;
 557             sep = '-';
 558         }
 559     }
 560     result.push(']');
 561     return result
 562 }
 563
 564 #[inline]
 565 fn bitwise<Op:BitwiseOperator>(out_vec: &mut [uint],
 566                                in_vec: &[uint],
 567                                op: &Op) -> bool {
 568     assert_eq!(out_vec.len(), in_vec.len());
 569     let mut changed = false;
 570     for (out_elt, in_elt) in out_vec.iter_mut().zip(in_vec.iter()) {
 571         let old_val = *out_elt;
 572         let new_val = op.join(old_val, *in_elt);
 573         *out_elt = new_val;
 574         changed |= old_val != new_val;
 575     }
 576     changed
 577 }
 578
 579 fn set_bit(words: &mut [uint], bit: uint) -> bool {
 580     debug!("set_bit: words={} bit={}",
 581            mut_bits_to_string(words), bit_str(bit));
 582     let word = bit / uint::BITS;
 583     let bit_in_word = bit % uint::BITS;
 584     let bit_mask = 1 << bit_in_word;
 585     debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, word);
 586     let oldv = words[word];
 587     let newv = oldv | bit_mask;
 588     words[word] = newv;
 589     oldv != newv
 590 }
 591
 592 fn bit_str(bit: uint) -> String {
 593     let byte = bit >> 8;
 594     let lobits = 1u << (bit & 0xFF);
 595     format!("[{}:{}-{:02x}]", bit, byte, lobits)
 596 }
 597
 598 struct Union;
 599 impl BitwiseOperator for Union {
 600     fn join(&self, a: uint, b: uint) -> uint { a | b }
 601 }
 602 struct Subtract;
 603 impl BitwiseOperator for Subtract {
 604     fn join(&self, a: uint, b: uint) -> uint { a & !b }
 605 }