1 /* PSPP - computes sample statistics.
2 Copyright (C) 2007 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 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, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 #include <libpspp/taint.h>
25 #include <libpspp/array.h>
26 #include <libpspp/assertion.h>
30 /* This code maintains two invariants:
32 1. If a node is tainted, then all of its successors are
35 2. If a node is tainted, then it and all of its predecessors are
38 /* A list of pointers to taint structures. */
42 struct taint **taints;
45 static void taint_list_init (struct taint_list *);
46 static void taint_list_destroy (struct taint_list *);
47 static void taint_list_add (struct taint_list *, struct taint *);
48 static void taint_list_remove (struct taint_list *, const struct taint *);
53 size_t ref_cnt; /* Number of owners. */
54 struct taint_list successors; /* Successors in graph. */
55 struct taint_list predecessors; /* Predecessors in graph. */
56 bool tainted; /* Is this node tainted? */
57 bool tainted_successor; /* Is/was any derived taint tainted? */
60 static void recursively_set_taint (struct taint *);
61 static void recursively_set_tainted_successor (struct taint *);
63 /* Creates and returns a new taint object. */
67 struct taint *taint = xmalloc (sizeof *taint);
69 taint_list_init (&taint->successors);
70 taint_list_init (&taint->predecessors);
71 taint->tainted = false;
72 taint->tainted_successor = false;
76 /* Returns a clone of the given TAINT.
77 The new and old taint objects are logically indistinguishable,
78 as if they were the same object. (In this implementation,
79 they are in fact the same object, but this is not a guarantee
80 made by the interface.) */
82 taint_clone (const struct taint *taint_)
84 struct taint *taint = (struct taint *) taint_;
86 assert (taint->ref_cnt > 0);
91 /* Destroys the given TAINT.
92 Returns false if TAINT was tainted, true otherwise.
93 Any propagation relationships through TAINT are preserved.
94 That is, if A taints B and B taints C, then destroying B will
95 preserve the transitive relationship, so that tainting A will
98 taint_destroy (struct taint *taint)
100 bool was_tainted = taint_is_tainted (taint);
101 if (--taint->ref_cnt == 0)
105 for (i = 0; i < taint->predecessors.cnt; i++)
106 for (j = 0; j < taint->successors.cnt; j++)
107 taint_propagate (taint->predecessors.taints[i],
108 taint->successors.taints[j]);
110 for (i = 0; i < taint->predecessors.cnt; i++)
111 taint_list_remove (&taint->predecessors.taints[i]->successors, taint);
112 for (i = 0; i < taint->successors.cnt; i++)
113 taint_list_remove (&taint->successors.taints[i]->predecessors, taint);
115 taint_list_destroy (&taint->successors);
116 taint_list_destroy (&taint->predecessors);
122 /* Adds a propagation relationship from FROM to TO. This means
123 that, should FROM ever become tainted, then TO will
124 automatically be marked tainted as well. This takes effect
125 immediately: if FROM is currently tainted, then TO will be
126 tainted after the call completes.
128 Taint propagation is transitive: if A propagates to B and B
129 propagates to C, then tainting A taints both B and C. Taint
130 propagation is not commutative: propagation from A to B does
131 not imply propagation from B to A. Taint propagation is
132 robust against loops, so that if A propagates to B and vice
133 versa, whether directly or indirectly, then tainting either A
134 or B will cause the other to be tainted, without producing an
137 taint_propagate (const struct taint *from_, const struct taint *to_)
139 struct taint *from = (struct taint *) from_;
140 struct taint *to = (struct taint *) to_;
144 taint_list_add (&from->successors, to);
145 taint_list_add (&to->predecessors, from);
146 if (from->tainted && !to->tainted)
147 recursively_set_taint (to);
148 else if (to->tainted_successor && !from->tainted_successor)
149 recursively_set_tainted_successor (from);
153 /* Returns true if TAINT is tainted, false otherwise. */
155 taint_is_tainted (const struct taint *taint)
157 return taint->tainted;
160 /* Marks TAINT tainted and propagates the taint to all of its
163 taint_set_taint (const struct taint *taint_)
165 struct taint *taint = (struct taint *) taint_;
167 recursively_set_taint (taint);
170 /* Returns true if TAINT is successor-tainted, that is, if it or
171 any of its successors is or ever has been tainted. (A
172 "successor" of a taint object X is any taint object that can
173 be reached by following propagation relationships starting
176 taint_has_tainted_successor (const struct taint *taint)
178 return taint->tainted_successor;
181 /* Attempts to reset the successor-taint on TAINT. This is
182 successful only if TAINT currently has no tainted successor. */
184 taint_reset_successor_taint (const struct taint *taint_)
186 struct taint *taint = (struct taint *) taint_;
188 if (taint->tainted_successor)
192 for (i = 0; i < taint->successors.cnt; i++)
193 if (taint->successors.taints[i]->tainted_successor)
196 taint->tainted_successor = false;
200 /* Initializes LIST as an empty list of taints. */
202 taint_list_init (struct taint_list *list)
210 taint_list_destroy (struct taint_list *list)
215 /* Returns true if TAINT is in LIST, false otherwise. */
217 taint_list_contains (const struct taint_list *list, const struct taint *taint)
221 for (i = 0; i < list->cnt; i++)
222 if (list->taints[i] == taint)
228 /* Returns true if X is zero or a power of 2, false otherwise. */
230 is_zero_or_power_of_2 (size_t x)
232 return (x & (x - 1)) == 0;
235 /* Adds TAINT to LIST, if it isn't already in the list. */
237 taint_list_add (struct taint_list *list, struct taint *taint)
239 if (!taint_list_contains (list, taint))
241 /* To save a few bytes of memory per list, we don't store
242 the list capacity as a separate member. Instead, the
243 list capacity is always zero or a power of 2. Thus, if
244 the list count is one of these threshold values, we need
245 to allocate more memory. */
246 if (is_zero_or_power_of_2 (list->cnt))
247 list->taints = xnrealloc (list->taints,
248 list->cnt == 0 ? 1 : 2 * list->cnt,
249 sizeof *list->taints);
250 list->taints[list->cnt++] = taint;
254 /* Removes TAINT from LIST (which must contain it). */
256 taint_list_remove (struct taint_list *list, const struct taint *taint)
260 for (i = 0; i < list->cnt; i++)
261 if (list->taints[i] == taint)
263 remove_element (list->taints, list->cnt, sizeof *list->taints, i);
271 /* Marks TAINT as tainted, as well as all of its successors
272 recursively. Also marks TAINT's predecessors as
273 successor-tainted, recursively. */
275 recursively_set_taint (struct taint *taint)
279 taint->tainted = taint->tainted_successor = true;
280 for (i = 0; i < taint->successors.cnt; i++)
282 struct taint *s = taint->successors.taints[i];
284 recursively_set_taint (s);
286 for (i = 0; i < taint->predecessors.cnt; i++)
288 struct taint *p = taint->predecessors.taints[i];
289 if (!p->tainted_successor)
290 recursively_set_tainted_successor (p);
294 /* Marks TAINT as successor-tainted, as well as all of its
295 predecessors recursively. */
297 recursively_set_tainted_successor (struct taint *taint)
301 taint->tainted_successor = true;
302 for (i = 0; i < taint->predecessors.cnt; i++)
304 struct taint *p = taint->predecessors.taints[i];
305 if (!p->tainted_successor)
306 recursively_set_tainted_successor (p);