1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
#[doc = "Interface for running tree-based traversals over layout boxes"]
use base::{RenderBox, RenderBoxTree};
use intrinsic::TyDesc;
export full_traversal;
export top_down_traversal;
export bottom_up_traversal;
export extended_full_traversal;
export extended_top_down_traversal;
// The underlying representation of an @T. We don't actually care
// what it is, just that we can transform to and from this
// representation to send boxes across task boundaries.
type shared_box<T> = {
mut refcount : uint,
// These are generic unsafe pointers, not just *ints
foo : *int,
bar : *int,
baz : *int,
payload : T
};
#[doc="Transform and @ into its underlying representation. The reference count stays constant."]
fn unwrap_box(-b : @RenderBox) -> *shared_box<RenderBox> unsafe {
let new_box : *shared_box<RenderBox> = cast::transmute(b);
return new_box;
}
#[doc="Transform an underlying representation back to an @. The reference count stays constant."]
fn rewrap_box(-b : *shared_box<RenderBox>) -> @RenderBox unsafe {
let new_box : @RenderBox = cast::transmute(b);
return new_box;
}
#[doc="
Iterate down and then up a tree of layout boxes in parallel and apply
the given functions to each box. Each box applies the first function,
spawns a task to complete all of its children in parallel, passing
each child the result of the ifrst funciton. It waits for them to
finish, and then applies the second function to the current box.
# Arguments
* `root` - The current top of the tree, the functions will be applied
to it and its children.
* `returned` - The value returned by applying top_down to the parent
of the current box, or a passed in default
* `top_down` - A function that is applied to each node after it is
applied to that node's parent.
* `bottom_up` - A function that is applied to each node after it is
applied to that node's children
"]
fn traverse_helper<T : Copy Send>(-root : @RenderBox, returned : T, -top_down : fn~(+T, @RenderBox) -> T,
-bottom_up : fn~(@RenderBox)) {
let returned = top_down(returned, root);
do listen |ack_chan| {
let mut count = 0;
// For each child we will send it off to another task and then
// recurse. It is safe to send these boxes across tasks
// because root still holds a reference to the children so
// they will not be destroyed from the other task. Also the
// current task will block until all of it's children return,
// so the original owner of the @-box will not exit while the
// children are still live.
for RenderBoxTree.each_child(root) |kid| {
count += 1;
// Unwrap the box so we can send it out of this task
let unwrapped = unwrap_box(copy kid);
// Hide the box in an option so we can get it across the
// task boundary without copying it
let swappable : ~mut Option<*shared_box<RenderBox>> = ~mut Some(unwrapped);
do task::spawn |copy top_down, copy bottom_up| {
// Get the box out of the option and into the new task
let mut swapped_in = None;
swapped_in <-> *swappable;
// Retrieve the original @RenderBox and recurse
let new_kid = rewrap_box(option::unwrap(swapped_in));
traverse_helper(new_kid, copy returned, copy top_down, copy bottom_up);
ack_chan.send(());
}
}
// wait for all the children to finish before preceding
for count.times() { ack_chan.recv(); }
}
bottom_up(root);
}
#[doc="A noneffectful function to be used if only one pass is required."]
fn nop(_box : @RenderBox) {
return;
}
#[doc= "
A wrapper to change a function that only acts on a box to one that
threasds a unit through to match travserse_helper
"]
fn unit_wrapper(-fun : fn~(@RenderBox)) -> fn~(+(), @RenderBox) {
fn~(+_u : (), box : @RenderBox) { fun(box); }
}
#[doc="
Iterate in parallel over the boxes in a tree, applying one function
to a parent before recursing on its children and one after.
"]
fn full_traversal(+root : @RenderBox, -top_down : fn~(@RenderBox), -bottom_up : fn~(@RenderBox)) {
traverse_helper(root, (), unit_wrapper(top_down), bottom_up);
}
#[doc="
Iterate in parallel over the boxes in a tree, applying the given
function to a parent before its children.
"]
fn top_down_traversal(+root : @RenderBox, -top_down : fn~(@RenderBox)) {
traverse_helper(root, (), unit_wrapper(top_down), nop);
}
#[doc="
Iterate in parallel over the boxes in a tree, applying the given
function to a parent after its children.
"]
fn bottom_up_traversal(+root : @RenderBox, -bottom_up : fn~(@RenderBox)) {
traverse_helper(root, (), unit_wrapper(nop), bottom_up);
}
#[doc="
Iterate in parallel over the boxes in a tree, applying the given
function to a parent before its children, the value returned by the
function is passed to each child when they are recursed upon. As
the recursion unwinds, the second function is applied to first the
children in parallel, and then the parent.
"]
fn extended_full_traversal<T : Copy Send>(+root : @RenderBox, first_val : T,
-top_down : fn~(+T, @RenderBox) -> T,
-bottom_up : fn~(@RenderBox)) {
traverse_helper(root, first_val, top_down, bottom_up);
}
#[doc="
Iterate in parallel over the boxes in a tree, applying the given
function to a parent before its children, the value returned by the
function is passed to each child when they are recursed upon.
"]
fn extended_top_down_traversal<T : Copy Send>(+root : @RenderBox, first_val : T,
-top_down : fn~(+T, @RenderBox) -> T) {
traverse_helper(root, first_val, top_down, nop);
}
|