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