1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19 #include <libpspp/taint.h>
23 #include <libpspp/array.h>
24 #include <libpspp/assertion.h>
28 /* This code maintains two invariants:
30 1. If a node is tainted, then all of its successors are
33 2. If a node is tainted, then it and all of its predecessors are
36 /* A list of pointers to taint structures. */
40 struct taint **taints;
43 static void taint_list_init (struct taint_list *);
44 static void taint_list_destroy (struct taint_list *);
45 static void taint_list_add (struct taint_list *, struct taint *);
46 static void taint_list_remove (struct taint_list *, const struct taint *);
51 size_t ref_cnt; /* Number of owners. */
52 struct taint_list successors; /* Successors in graph. */
53 struct taint_list predecessors; /* Predecessors in graph. */
54 bool tainted; /* Is this node tainted? */
55 bool tainted_successor; /* Is/was any derived taint tainted? */
58 static void recursively_set_taint (struct taint *);
59 static void recursively_set_tainted_successor (struct taint *);
61 /* Creates and returns a new taint object. */
65 struct taint *taint = xmalloc (sizeof *taint);
67 taint_list_init (&taint->successors);
68 taint_list_init (&taint->predecessors);
69 taint->tainted = false;
70 taint->tainted_successor = false;
74 /* Returns a clone of the given TAINT.
75 The new and old taint objects are logically indistinguishable,
76 as if they were the same object. (In this implementation,
77 they are in fact the same object, but this is not a guarantee
78 made by the interface.) */
80 taint_clone (const struct taint *taint_)
82 struct taint *taint = (struct taint *) taint_;
84 assert (taint->ref_cnt > 0);
89 /* Destroys the given TAINT.
90 Returns false if TAINT was tainted, true otherwise.
91 Any propagation relationships through TAINT are preserved.
92 That is, if A taints B and B taints C, then destroying B will
93 preserve the transitive relationship, so that tainting A will
96 taint_destroy (struct taint *taint)
98 bool was_tainted = taint_is_tainted (taint);
99 if (--taint->ref_cnt == 0)
103 for (i = 0; i < taint->predecessors.cnt; i++)
104 for (j = 0; j < taint->successors.cnt; j++)
105 taint_propagate (taint->predecessors.taints[i],
106 taint->successors.taints[j]);
108 for (i = 0; i < taint->predecessors.cnt; i++)
109 taint_list_remove (&taint->predecessors.taints[i]->successors, taint);
110 for (i = 0; i < taint->successors.cnt; i++)
111 taint_list_remove (&taint->successors.taints[i]->predecessors, taint);
113 taint_list_destroy (&taint->successors);
114 taint_list_destroy (&taint->predecessors);
120 /* Adds a propagation relationship from FROM to TO. This means
121 that, should FROM ever become tainted, then TO will
122 automatically be marked tainted as well. This takes effect
123 immediately: if FROM is currently tainted, then TO will be
124 tainted after the call completes.
126 Taint propagation is transitive: if A propagates to B and B
127 propagates to C, then tainting A taints both B and C. Taint
128 propagation is not commutative: propagation from A to B does
129 not imply propagation from B to A. Taint propagation is
130 robust against loops, so that if A propagates to B and vice
131 versa, whether directly or indirectly, then tainting either A
132 or B will cause the other to be tainted, without producing an
135 taint_propagate (const struct taint *from_, const struct taint *to_)
137 struct taint *from = (struct taint *) from_;
138 struct taint *to = (struct taint *) to_;
142 taint_list_add (&from->successors, to);
143 taint_list_add (&to->predecessors, from);
144 if (from->tainted && !to->tainted)
145 recursively_set_taint (to);
146 else if (to->tainted_successor && !from->tainted_successor)
147 recursively_set_tainted_successor (from);
151 /* Returns true if TAINT is tainted, false otherwise. */
153 taint_is_tainted (const struct taint *taint)
155 return taint->tainted;
158 /* Marks TAINT tainted and propagates the taint to all of its
161 taint_set_taint (const struct taint *taint_)
163 struct taint *taint = (struct taint *) taint_;
165 recursively_set_taint (taint);
168 /* Returns true if TAINT is successor-tainted, that is, if it or
169 any of its successors is or ever has been tainted. (A
170 "successor" of a taint object X is any taint object that can
171 be reached by following propagation relationships starting
174 taint_has_tainted_successor (const struct taint *taint)
176 return taint->tainted_successor;
179 /* Attempts to reset the successor-taint on TAINT. This is
180 successful only if TAINT currently has no tainted successor. */
182 taint_reset_successor_taint (const struct taint *taint_)
184 struct taint *taint = (struct taint *) taint_;
186 if (taint->tainted_successor)
190 for (i = 0; i < taint->successors.cnt; i++)
191 if (taint->successors.taints[i]->tainted_successor)
194 taint->tainted_successor = false;
198 /* Initializes LIST as an empty list of taints. */
200 taint_list_init (struct taint_list *list)
208 taint_list_destroy (struct taint_list *list)
213 /* Returns true if TAINT is in LIST, false otherwise. */
215 taint_list_contains (const struct taint_list *list, const struct taint *taint)
219 for (i = 0; i < list->cnt; i++)
220 if (list->taints[i] == taint)
226 /* Returns true if X is zero or a power of 2, false otherwise. */
228 is_zero_or_power_of_2 (size_t x)
230 return (x & (x - 1)) == 0;
233 /* Adds TAINT to LIST, if it isn't already in the list. */
235 taint_list_add (struct taint_list *list, struct taint *taint)
237 if (!taint_list_contains (list, taint))
239 /* To save a few bytes of memory per list, we don't store
240 the list capacity as a separate member. Instead, the
241 list capacity is always zero or a power of 2. Thus, if
242 the list count is one of these threshold values, we need
243 to allocate more memory. */
244 if (is_zero_or_power_of_2 (list->cnt))
245 list->taints = xnrealloc (list->taints,
246 list->cnt == 0 ? 1 : 2 * list->cnt,
247 sizeof *list->taints);
248 list->taints[list->cnt++] = taint;
252 /* Removes TAINT from LIST (which must contain it). */
254 taint_list_remove (struct taint_list *list, const struct taint *taint)
258 for (i = 0; i < list->cnt; i++)
259 if (list->taints[i] == taint)
261 remove_element (list->taints, list->cnt, sizeof *list->taints, i);
269 /* Marks TAINT as tainted, as well as all of its successors
270 recursively. Also marks TAINT's predecessors as
271 successor-tainted, recursively. */
273 recursively_set_taint (struct taint *taint)
277 taint->tainted = taint->tainted_successor = true;
278 for (i = 0; i < taint->successors.cnt; i++)
280 struct taint *s = taint->successors.taints[i];
282 recursively_set_taint (s);
284 for (i = 0; i < taint->predecessors.cnt; i++)
286 struct taint *p = taint->predecessors.taints[i];
287 if (!p->tainted_successor)
288 recursively_set_tainted_successor (p);
292 /* Marks TAINT as successor-tainted, as well as all of its
293 predecessors recursively. */
295 recursively_set_tainted_successor (struct taint *taint)
299 taint->tainted_successor = true;
300 for (i = 0; i < taint->predecessors.cnt; i++)
302 struct taint *p = taint->predecessors.taints[i];
303 if (!p->tainted_successor)
304 recursively_set_tainted_successor (p);