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.
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.
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.
23 use collections::HashMap;
26 use syntax::ast_util::IdRange;
27 use syntax::print::{pp, pprust};
30 use util::ppaux::Repr;
33 pub struct DataFlowContext<O> {
35 priv method_map: typeck::MethodMap,
37 /// the data flow operator
40 /// number of bits to propagate per id
41 priv bits_per_id: uint,
43 /// number of words we will use to store bits_per_id.
44 /// equal to bits_per_id/uint::BITS rounded up.
45 priv words_per_id: uint,
47 // mapping from node to bitset index.
48 priv nodeid_to_bitset: HashMap<ast::NodeId,uint>,
50 // Bit sets per id. The following three fields (`gens`, `kills`,
51 // and `on_entry`) all have the same structure. For each id in
52 // `id_range`, there is a range of words equal to `words_per_id`.
53 // So, to access the bits for any given id, you take a slice of
54 // the full vector (see the method `compute_id_range()`).
56 /// bits generated as we exit the scope `id`. Updated by `add_gen()`.
59 /// bits killed as we exit the scope `id`. Updated by `add_kill()`.
62 /// bits that are valid on entry to the scope `id`. Updated by
64 priv on_entry: ~[uint]
67 /// Parameterization for the precise form of data flow that is used.
68 pub trait DataFlowOperator {
69 /// Specifies the initial value for each bit in the `on_entry` set
70 fn initial_value(&self) -> bool;
72 /// Joins two predecessor bits together, typically either `|` or `&`
73 fn join(&self, succ: uint, pred: uint) -> uint;
76 struct PropagationContext<'a, O> {
77 dfcx: &'a mut DataFlowContext<O>,
81 struct LoopScope<'a> {
86 impl<O:DataFlowOperator> pprust::PpAnn for DataFlowContext<O> {
87 fn pre(&self, node: pprust::AnnNode) -> io::IoResult<()> {
88 let (ps, id) = match node {
89 pprust::NodeExpr(ps, expr) => (ps, expr.id),
90 pprust::NodeBlock(ps, blk) => (ps, blk.id),
91 pprust::NodeItem(ps, _) => (ps, 0),
92 pprust::NodePat(ps, pat) => (ps, pat.id)
95 if self.nodeid_to_bitset.contains_key(&id) {
96 let (start, end) = self.compute_id_range_frozen(id);
97 let on_entry = self.on_entry.slice(start, end);
98 let entry_str = bits_to_str(on_entry);
100 let gens = self.gens.slice(start, end);
101 let gens_str = if gens.iter().any(|&u| u != 0) {
102 format!(" gen: {}", bits_to_str(gens))
107 let kills = self.kills.slice(start, end);
108 let kills_str = if kills.iter().any(|&u| u != 0) {
109 format!(" kill: {}", bits_to_str(kills))
114 let comment_str = format!("id {}: {}{}{}",
115 id, entry_str, gens_str, kills_str);
116 try!(pprust::synth_comment(ps, comment_str));
117 try!(pp::space(&mut ps.s));
123 impl<O:DataFlowOperator> DataFlowContext<O> {
124 pub fn new(tcx: ty::ctxt,
125 method_map: typeck::MethodMap,
128 bits_per_id: uint) -> DataFlowContext<O> {
129 let words_per_id = (bits_per_id + uint::BITS - 1) / uint::BITS;
131 debug!("DataFlowContext::new(id_range={:?}, bits_per_id={:?}, words_per_id={:?})",
132 id_range, bits_per_id, words_per_id);
140 method_map: method_map,
141 words_per_id: words_per_id,
142 nodeid_to_bitset: HashMap::new(),
143 bits_per_id: bits_per_id,
151 pub fn add_gen(&mut self, id: ast::NodeId, bit: uint) {
152 //! Indicates that `id` generates `bit`
154 debug!("add_gen(id={:?}, bit={:?})", id, bit);
155 let (start, end) = self.compute_id_range(id);
157 let gens = self.gens.mut_slice(start, end);
162 pub fn add_kill(&mut self, id: ast::NodeId, bit: uint) {
163 //! Indicates that `id` kills `bit`
165 debug!("add_kill(id={:?}, bit={:?})", id, bit);
166 let (start, end) = self.compute_id_range(id);
168 let kills = self.kills.mut_slice(start, end);
173 fn apply_gen_kill(&mut self, id: ast::NodeId, bits: &mut [uint]) {
174 //! Applies the gen and kill sets for `id` to `bits`
176 debug!("apply_gen_kill(id={:?}, bits={}) [before]",
177 id, mut_bits_to_str(bits));
178 let (start, end) = self.compute_id_range(id);
179 let gens = self.gens.slice(start, end);
180 bitwise(bits, gens, |a, b| a | b);
181 let kills = self.kills.slice(start, end);
182 bitwise(bits, kills, |a, b| a & !b);
184 debug!("apply_gen_kill(id={:?}, bits={}) [after]",
185 id, mut_bits_to_str(bits));
188 fn apply_kill(&mut self, id: ast::NodeId, bits: &mut [uint]) {
189 debug!("apply_kill(id={:?}, bits={}) [before]",
190 id, mut_bits_to_str(bits));
191 let (start, end) = self.compute_id_range(id);
192 let kills = self.kills.slice(start, end);
193 bitwise(bits, kills, |a, b| a & !b);
194 debug!("apply_kill(id={:?}, bits={}) [after]",
195 id, mut_bits_to_str(bits));
198 fn compute_id_range_frozen(&self, id: ast::NodeId) -> (uint, uint) {
199 let n = *self.nodeid_to_bitset.get(&id);
200 let start = n * self.words_per_id;
201 let end = start + self.words_per_id;
205 fn compute_id_range(&mut self, id: ast::NodeId) -> (uint, uint) {
206 let mut expanded = false;
207 let len = self.nodeid_to_bitset.len();
208 let n = self.nodeid_to_bitset.find_or_insert_with(id, |_| {
213 let entry = if self.oper.initial_value() { uint::MAX } else {0};
214 for _ in range(0, self.words_per_id) {
217 self.on_entry.push(entry);
220 let start = *n * self.words_per_id;
221 let end = start + self.words_per_id;
223 assert!(start < self.gens.len());
224 assert!(end <= self.gens.len());
225 assert!(self.gens.len() == self.kills.len());
226 assert!(self.gens.len() == self.on_entry.len());
232 pub fn each_bit_on_entry_frozen(&self,
236 //! Iterates through each bit that is set on entry to `id`.
237 //! Only useful after `propagate()` has been called.
238 if !self.nodeid_to_bitset.contains_key(&id) {
241 let (start, end) = self.compute_id_range_frozen(id);
242 let on_entry = self.on_entry.slice(start, end);
243 debug!("each_bit_on_entry_frozen(id={:?}, on_entry={})",
244 id, bits_to_str(on_entry));
245 self.each_bit(on_entry, f)
248 pub fn each_bit_on_entry(&mut self,
252 //! Iterates through each bit that is set on entry to `id`.
253 //! Only useful after `propagate()` has been called.
255 let (start, end) = self.compute_id_range(id);
256 let on_entry = self.on_entry.slice(start, end);
257 debug!("each_bit_on_entry(id={:?}, on_entry={})",
258 id, bits_to_str(on_entry));
259 self.each_bit(on_entry, f)
262 pub fn each_gen_bit(&mut self, id: ast::NodeId, f: |uint| -> bool)
264 //! Iterates through each bit in the gen set for `id`.
266 let (start, end) = self.compute_id_range(id);
267 let gens = self.gens.slice(start, end);
268 debug!("each_gen_bit(id={:?}, gens={})",
269 id, bits_to_str(gens));
270 self.each_bit(gens, f)
273 pub fn each_gen_bit_frozen(&self, id: ast::NodeId, f: |uint| -> bool)
275 //! Iterates through each bit in the gen set for `id`.
276 if !self.nodeid_to_bitset.contains_key(&id) {
279 let (start, end) = self.compute_id_range_frozen(id);
280 let gens = self.gens.slice(start, end);
281 debug!("each_gen_bit(id={:?}, gens={})",
282 id, bits_to_str(gens));
283 self.each_bit(gens, f)
286 fn each_bit(&self, words: &[uint], f: |uint| -> bool) -> bool {
287 //! Helper for iterating over the bits in a bit set.
289 for (word_index, &word) in words.iter().enumerate() {
291 let base_index = word_index * uint::BITS;
292 for offset in range(0u, uint::BITS) {
293 let bit = 1 << offset;
294 if (word & bit) != 0 {
295 // NB: we round up the total number of bits
296 // that we store in any given bit set so that
297 // it is an even multiple of uint::BITS. This
298 // means that there may be some stray bits at
299 // the end that do not correspond to any
300 // actual value. So before we callback, check
301 // whether the bit_index is greater than the
302 // actual value the user specified and stop
304 let bit_index = base_index + offset;
305 if bit_index >= self.bits_per_id {
307 } else if !f(bit_index) {
318 impl<O:DataFlowOperator+Clone+'static> DataFlowContext<O> {
319 // ^^^^^^^^^^^^^ only needed for pretty printing
320 pub fn propagate(&mut self, blk: &ast::Block) {
321 //! Performs the data flow analysis.
323 if self.bits_per_id == 0 {
324 // Optimize the surprisingly common degenerate case.
329 let mut propcx = PropagationContext {
334 let mut temp = vec::from_elem(self.words_per_id, 0u);
335 let mut loop_scopes = ~[];
337 while propcx.changed {
338 propcx.changed = false;
340 propcx.walk_block(blk, temp, &mut loop_scopes);
344 debug!("Dataflow result:");
346 self.pretty_print_to(~io::stderr(), blk).unwrap();
351 fn pretty_print_to(&self, wr: ~io::Writer,
352 blk: &ast::Block) -> io::IoResult<()> {
353 let mut ps = pprust::rust_printer_annotated(wr, self);
354 try!(pprust::cbox(&mut ps, pprust::indent_unit));
355 try!(pprust::ibox(&mut ps, 0u));
356 try!(pprust::print_block(&mut ps, blk));
357 try!(pp::eof(&mut ps.s));
362 impl<'a, O:DataFlowOperator> PropagationContext<'a, O> {
363 fn tcx(&self) -> ty::ctxt {
367 fn walk_block(&mut self,
370 loop_scopes: &mut ~[LoopScope]) {
371 debug!("DataFlowContext::walk_block(blk.id={}, in_out={})",
372 blk.id, bits_to_str(in_out));
374 self.merge_with_entry_set(blk.id, in_out);
376 for &stmt in blk.stmts.iter() {
377 self.walk_stmt(stmt, in_out, loop_scopes);
380 self.walk_opt_expr(blk.expr, in_out, loop_scopes);
382 self.dfcx.apply_gen_kill(blk.id, in_out);
385 fn walk_stmt(&mut self,
388 loop_scopes: &mut ~[LoopScope]) {
390 ast::StmtDecl(decl, _) => {
391 self.walk_decl(decl, in_out, loop_scopes);
394 ast::StmtExpr(expr, _) | ast::StmtSemi(expr, _) => {
395 self.walk_expr(expr, in_out, loop_scopes);
398 ast::StmtMac(..) => {
399 self.tcx().sess.span_bug(stmt.span, "unexpanded macro");
404 fn walk_decl(&mut self,
407 loop_scopes: &mut ~[LoopScope]) {
409 ast::DeclLocal(local) => {
410 self.walk_opt_expr(local.init, in_out, loop_scopes);
411 self.walk_pat(local.pat, in_out, loop_scopes);
414 ast::DeclItem(_) => {}
418 fn walk_expr(&mut self,
421 loop_scopes: &mut ~[LoopScope]) {
422 debug!("DataFlowContext::walk_expr(expr={}, in_out={})",
423 expr.repr(self.dfcx.tcx), bits_to_str(in_out));
425 self.merge_with_entry_set(expr.id, in_out);
428 ast::ExprFnBlock(..) | ast::ExprProc(..) => {
431 ast::ExprIf(cond, then, els) => {
445 self.walk_expr(cond, in_out, loop_scopes);
447 let mut then_bits = in_out.to_owned();
448 self.walk_block(then, then_bits, loop_scopes);
450 self.walk_opt_expr(els, in_out, loop_scopes);
451 join_bits(&self.dfcx.oper, then_bits, in_out);
454 ast::ExprWhile(cond, blk) => {
467 self.walk_expr(cond, in_out, loop_scopes);
469 let mut body_bits = in_out.to_owned();
470 loop_scopes.push(LoopScope {
472 break_bits: in_out.to_owned()
474 self.walk_block(blk, body_bits, loop_scopes);
475 self.add_to_entry_set(expr.id, body_bits);
476 let new_loop_scope = loop_scopes.pop().unwrap();
477 copy_bits(new_loop_scope.break_bits, in_out);
480 ast::ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
482 ast::ExprLoop(blk, _) => {
492 let mut body_bits = in_out.to_owned();
494 loop_scopes.push(LoopScope {
496 break_bits: in_out.to_owned()
498 self.walk_block(blk, body_bits, loop_scopes);
499 self.add_to_entry_set(expr.id, body_bits);
501 let new_loop_scope = loop_scopes.pop().unwrap();
502 assert_eq!(new_loop_scope.loop_id, expr.id);
503 copy_bits(new_loop_scope.break_bits, in_out);
506 ast::ExprMatch(discr, ref arms) => {
518 self.walk_expr(discr, in_out, loop_scopes);
520 let mut guards = in_out.to_owned();
522 // We know that exactly one arm will be taken, so we
523 // can start out with a blank slate and just union
524 // together the bits from each arm:
527 for arm in arms.iter() {
528 // in_out reflects the discr and all guards to date
529 self.walk_opt_expr(arm.guard, guards, loop_scopes);
531 // determine the bits for the body and then union
532 // them into `in_out`, which reflects all bodies to date
533 let mut body = guards.to_owned();
534 self.walk_pat_alternatives(arm.pats, body, loop_scopes);
535 self.walk_block(arm.body, body, loop_scopes);
536 join_bits(&self.dfcx.oper, body, in_out);
540 ast::ExprRet(o_e) => {
541 self.walk_opt_expr(o_e, in_out, loop_scopes);
545 ast::ExprBreak(label) => {
546 let scope = self.find_scope(expr, label, loop_scopes);
547 self.break_from_to(expr, scope, in_out);
551 ast::ExprAgain(label) => {
552 let scope = self.find_scope(expr, label, loop_scopes);
553 self.pop_scopes(expr, scope, in_out);
554 self.add_to_entry_set(scope.loop_id, in_out);
558 ast::ExprAssign(l, r) |
559 ast::ExprAssignOp(_, l, r) => {
560 self.walk_expr(r, in_out, loop_scopes);
561 self.walk_expr(l, in_out, loop_scopes);
564 ast::ExprVec(ref exprs, _) => {
565 self.walk_exprs(*exprs, in_out, loop_scopes)
568 ast::ExprRepeat(l, r, _) => {
569 self.walk_expr(l, in_out, loop_scopes);
570 self.walk_expr(r, in_out, loop_scopes);
573 ast::ExprStruct(_, ref fields, with_expr) => {
574 for field in fields.iter() {
575 self.walk_expr(field.expr, in_out, loop_scopes);
577 self.walk_opt_expr(with_expr, in_out, loop_scopes);
580 ast::ExprCall(f, ref args) => {
581 self.walk_expr(f, in_out, loop_scopes);
582 self.walk_call(expr.id, *args, in_out, loop_scopes);
585 ast::ExprMethodCall(_, _, ref args) => {
586 self.walk_call(expr.id, *args, in_out, loop_scopes);
589 ast::ExprIndex(l, r) |
590 ast::ExprBinary(_, l, r) if self.is_method_call(expr) => {
591 self.walk_call(expr.id, [l, r], in_out, loop_scopes);
594 ast::ExprUnary(_, e) if self.is_method_call(expr) => {
595 self.walk_call(expr.id, [e], in_out, loop_scopes);
598 ast::ExprTup(ref exprs) => {
599 self.walk_exprs(*exprs, in_out, loop_scopes);
602 ast::ExprBinary(op, l, r) if ast_util::lazy_binop(op) => {
603 self.walk_expr(l, in_out, loop_scopes);
604 let temp = in_out.to_owned();
605 self.walk_expr(r, in_out, loop_scopes);
606 join_bits(&self.dfcx.oper, temp, in_out);
609 ast::ExprIndex(l, r) |
610 ast::ExprBinary(_, l, r) => {
611 self.walk_exprs([l, r], in_out, loop_scopes);
616 ast::ExprPath(..) => {}
618 ast::ExprAddrOf(_, e) |
619 ast::ExprCast(e, _) |
620 ast::ExprUnary(_, e) |
622 ast::ExprVstore(e, _) |
623 ast::ExprField(e, _, _) => {
624 self.walk_expr(e, in_out, loop_scopes);
627 ast::ExprBox(s, e) => {
628 self.walk_expr(s, in_out, loop_scopes);
629 self.walk_expr(e, in_out, loop_scopes);
632 ast::ExprInlineAsm(ref inline_asm) => {
633 for &(_, expr) in inline_asm.inputs.iter() {
634 self.walk_expr(expr, in_out, loop_scopes);
636 for &(_, expr) in inline_asm.outputs.iter() {
637 self.walk_expr(expr, in_out, loop_scopes);
641 ast::ExprBlock(blk) => {
642 self.walk_block(blk, in_out, loop_scopes);
645 ast::ExprMac(..) => {
646 self.tcx().sess.span_bug(expr.span, "unexpanded macro");
650 self.dfcx.apply_gen_kill(expr.id, in_out);
653 fn pop_scopes(&mut self,
654 from_expr: &ast::Expr,
655 to_scope: &mut LoopScope,
656 in_out: &mut [uint]) {
657 //! Whenever you have a `break` or a `loop` statement, flow
658 //! exits through any number of enclosing scopes on its
659 //! way to the new destination. This function applies the kill
660 //! sets of those enclosing scopes to `in_out` (those kill sets
661 //! concern items that are going out of scope).
663 let tcx = self.tcx();
665 debug!("pop_scopes(from_expr={}, to_scope={:?}, in_out={})",
666 from_expr.repr(tcx), to_scope.loop_id,
667 bits_to_str(in_out));
669 let mut id = from_expr.id;
670 while id != to_scope.loop_id {
671 self.dfcx.apply_kill(id, in_out);
673 match tcx.region_maps.opt_encl_scope(id) {
674 Some(i) => { id = i; }
678 format!("pop_scopes(from_expr={}, to_scope={:?}) \
679 to_scope does not enclose from_expr",
680 from_expr.repr(tcx), to_scope.loop_id));
686 fn break_from_to(&mut self,
687 from_expr: &ast::Expr,
688 to_scope: &mut LoopScope,
689 in_out: &mut [uint]) {
690 self.pop_scopes(from_expr, to_scope, in_out);
691 self.dfcx.apply_kill(from_expr.id, in_out);
692 join_bits(&self.dfcx.oper, in_out, to_scope.break_bits);
693 debug!("break_from_to(from_expr={}, to_scope={}) final break_bits={}",
694 from_expr.repr(self.tcx()),
696 bits_to_str(in_out));
699 fn walk_exprs(&mut self,
700 exprs: &[@ast::Expr],
702 loop_scopes: &mut ~[LoopScope]) {
703 for &expr in exprs.iter() {
704 self.walk_expr(expr, in_out, loop_scopes);
708 fn walk_opt_expr(&mut self,
709 opt_expr: Option<@ast::Expr>,
711 loop_scopes: &mut ~[LoopScope]) {
712 for &expr in opt_expr.iter() {
713 self.walk_expr(expr, in_out, loop_scopes);
717 fn walk_call(&mut self,
718 call_id: ast::NodeId,
721 loop_scopes: &mut ~[LoopScope]) {
722 self.walk_exprs(args, in_out, loop_scopes);
724 // FIXME(#6268) nested method calls
725 // self.merge_with_entry_set(in_out);
726 // self.dfcx.apply_gen_kill(in_out);
728 let return_ty = ty::node_id_to_type(self.tcx(), call_id);
729 let fails = ty::type_is_bot(return_ty);
735 fn walk_pat(&mut self,
738 _loop_scopes: &mut ~[LoopScope]) {
739 debug!("DataFlowContext::walk_pat(pat={}, in_out={})",
740 pat.repr(self.dfcx.tcx), bits_to_str(in_out));
742 ast_util::walk_pat(pat, |p| {
743 debug!(" p.id={} in_out={}", p.id, bits_to_str(in_out));
744 self.merge_with_entry_set(p.id, in_out);
745 self.dfcx.apply_gen_kill(p.id, in_out);
750 fn walk_pat_alternatives(&mut self,
753 loop_scopes: &mut ~[LoopScope]) {
755 // Common special case:
756 return self.walk_pat(pats[0], in_out, loop_scopes);
759 // In the general case, the patterns in `pats` are
760 // alternatives, so we must treat this like an N-way select
762 let initial_state = in_out.to_owned();
763 for &pat in pats.iter() {
764 let mut temp = initial_state.clone();
765 self.walk_pat(pat, temp, loop_scopes);
766 join_bits(&self.dfcx.oper, temp, in_out);
770 fn find_scope<'a>(&self,
772 label: Option<ast::Ident>,
773 loop_scopes: &'a mut ~[LoopScope]) -> &'a mut LoopScope {
774 let index = match label {
776 let len = loop_scopes.len();
781 let def_map = self.tcx().def_map.borrow();
782 match def_map.get().find(&expr.id) {
783 Some(&ast::DefLabel(loop_id)) => {
784 match loop_scopes.iter().position(|l| l.loop_id == loop_id) {
787 self.tcx().sess.span_bug(
789 format!("no loop scope for id {:?}", loop_id));
795 self.tcx().sess.span_bug(
797 format!("bad entry `{:?}` in def_map for label", r));
803 &mut loop_scopes[index]
806 fn is_method_call(&self, expr: &ast::Expr) -> bool {
807 let method_map = self.dfcx.method_map.borrow();
808 method_map.get().contains_key(&expr.id)
811 fn reset(&mut self, bits: &mut [uint]) {
812 let e = if self.dfcx.oper.initial_value() {uint::MAX} else {0};
813 for b in bits.mut_iter() { *b = e; }
816 fn add_to_entry_set(&mut self, id: ast::NodeId, pred_bits: &[uint]) {
817 debug!("add_to_entry_set(id={:?}, pred_bits={})",
818 id, bits_to_str(pred_bits));
819 let (start, end) = self.dfcx.compute_id_range(id);
820 let changed = { // FIXME(#5074) awkward construction
821 let on_entry = self.dfcx.on_entry.mut_slice(start, end);
822 join_bits(&self.dfcx.oper, pred_bits, on_entry)
825 debug!("changed entry set for {:?} to {}",
826 id, bits_to_str(self.dfcx.on_entry.slice(start, end)));
831 fn merge_with_entry_set(&mut self,
833 pred_bits: &mut [uint]) {
834 debug!("merge_with_entry_set(id={:?}, pred_bits={})",
835 id, mut_bits_to_str(pred_bits));
836 let (start, end) = self.dfcx.compute_id_range(id);
837 let changed = { // FIXME(#5074) awkward construction
838 let on_entry = self.dfcx.on_entry.mut_slice(start, end);
839 let changed = join_bits(&self.dfcx.oper, pred_bits, on_entry);
840 copy_bits(on_entry, pred_bits);
844 debug!("changed entry set for {:?} to {}",
845 id, bits_to_str(self.dfcx.on_entry.slice(start, end)));
851 fn mut_bits_to_str(words: &mut [uint]) -> ~str {
855 fn bits_to_str(words: &[uint]) -> ~str {
856 let mut result = ~"";
859 // Note: this is a little endian printout of bytes.
861 for &word in words.iter() {
863 for _ in range(0u, uint::BYTES) {
864 result.push_char(sep);
865 result.push_str(format!("{:02x}", v & 0xFF));
870 result.push_char(']');
874 fn copy_bits(in_vec: &[uint], out_vec: &mut [uint]) -> bool {
875 bitwise(out_vec, in_vec, |_, b| b)
878 fn join_bits<O:DataFlowOperator>(oper: &O,
880 out_vec: &mut [uint]) -> bool {
881 bitwise(out_vec, in_vec, |a, b| oper.join(a, b))
885 fn bitwise(out_vec: &mut [uint], in_vec: &[uint], op: |uint, uint| -> uint)
887 assert_eq!(out_vec.len(), in_vec.len());
888 let mut changed = false;
889 for (out_elt, in_elt) in out_vec.mut_iter().zip(in_vec.iter()) {
890 let old_val = *out_elt;
891 let new_val = op(old_val, *in_elt);
893 changed |= old_val != new_val;
898 fn set_bit(words: &mut [uint], bit: uint) -> bool {
899 debug!("set_bit: words={} bit={}",
900 mut_bits_to_str(words), bit_str(bit));
901 let word = bit / uint::BITS;
902 let bit_in_word = bit % uint::BITS;
903 let bit_mask = 1 << bit_in_word;
904 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, word);
905 let oldv = words[word];
906 let newv = oldv | bit_mask;
911 fn bit_str(bit: uint) -> ~str {
913 let lobits = 1 << (bit & 0xFF);
914 format!("[{}:{}-{:02x}]", bit, byte, lobits)