Delete trailing whitespace at end of lines.
[pspp-builds.git] / src / libpspp / taint.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 2007 Free Software Foundation, Inc.
3
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.
8
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.
13
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
17    02110-1301, USA. */
18
19 #include <config.h>
20
21 #include <libpspp/taint.h>
22
23 #include <stddef.h>
24
25 #include <libpspp/array.h>
26 #include <libpspp/assertion.h>
27
28 #include "xalloc.h"
29
30 /* This code maintains two invariants:
31
32    1. If a node is tainted, then all of its successors are
33       tainted.
34
35    2. If a node is tainted, then it and all of its predecessors are
36       successor-tainted. */
37
38 /* A list of pointers to taint structures. */
39 struct taint_list
40   {
41     size_t cnt;
42     struct taint **taints;
43   };
44
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 *);
49
50 /* A taint. */
51 struct taint
52   {
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? */
58   };
59
60 static void recursively_set_taint (struct taint *);
61 static void recursively_set_tainted_successor (struct taint *);
62
63 /* Creates and returns a new taint object. */
64 struct taint *
65 taint_create (void)
66 {
67   struct taint *taint = xmalloc (sizeof *taint);
68   taint->ref_cnt = 1;
69   taint_list_init (&taint->successors);
70   taint_list_init (&taint->predecessors);
71   taint->tainted = false;
72   taint->tainted_successor = false;
73   return taint;
74 }
75
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.) */
81 struct taint *
82 taint_clone (const struct taint *taint_)
83 {
84   struct taint *taint = (struct taint *) taint_;
85
86   assert (taint->ref_cnt > 0);
87   taint->ref_cnt++;
88   return taint;
89 }
90
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
96    still taint C. */
97 bool
98 taint_destroy (struct taint *taint)
99 {
100   bool was_tainted = taint_is_tainted (taint);
101   if (--taint->ref_cnt == 0)
102     {
103       size_t i, j;
104
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]);
109
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);
114
115       taint_list_destroy (&taint->successors);
116       taint_list_destroy (&taint->predecessors);
117       free (taint);
118     }
119   return !was_tainted;
120 }
121
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.
127
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
135    infinite loop. */
136 void
137 taint_propagate (const struct taint *from_, const struct taint *to_)
138 {
139   struct taint *from = (struct taint *) from_;
140   struct taint *to = (struct taint *) to_;
141
142   if (from != to)
143     {
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);
150     }
151 }
152
153 /* Returns true if TAINT is tainted, false otherwise. */
154 bool
155 taint_is_tainted (const struct taint *taint)
156 {
157   return taint->tainted;
158 }
159
160 /* Marks TAINT tainted and propagates the taint to all of its
161    successors. */
162 void
163 taint_set_taint (const struct taint *taint_)
164 {
165   struct taint *taint = (struct taint *) taint_;
166   if (!taint->tainted)
167     recursively_set_taint (taint);
168 }
169
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
174    from X.) */
175 bool
176 taint_has_tainted_successor (const struct taint *taint)
177 {
178   return taint->tainted_successor;
179 }
180
181 /* Attempts to reset the successor-taint on TAINT.  This is
182    successful only if TAINT currently has no tainted successor. */
183 void
184 taint_reset_successor_taint (const struct taint *taint_)
185 {
186   struct taint *taint = (struct taint *) taint_;
187
188   if (taint->tainted_successor)
189     {
190       size_t i;
191
192       for (i = 0; i < taint->successors.cnt; i++)
193         if (taint->successors.taints[i]->tainted_successor)
194           return;
195
196       taint->tainted_successor = false;
197     }
198 }
199 \f
200 /* Initializes LIST as an empty list of taints. */
201 static void
202 taint_list_init (struct taint_list *list)
203 {
204   list->cnt = 0;
205   list->taints = NULL;
206 }
207
208 /* Destroys LIST. */
209 static void
210 taint_list_destroy (struct taint_list *list)
211 {
212   free (list->taints);
213 }
214
215 /* Returns true if TAINT is in LIST, false otherwise. */
216 static bool
217 taint_list_contains (const struct taint_list *list, const struct taint *taint)
218 {
219   size_t i;
220
221   for (i = 0; i < list->cnt; i++)
222     if (list->taints[i] == taint)
223       return true;
224
225   return false;
226 }
227
228 /* Returns true if X is zero or a power of 2, false otherwise. */
229 static bool
230 is_zero_or_power_of_2 (size_t x)
231 {
232   return (x & (x - 1)) == 0;
233 }
234
235 /* Adds TAINT to LIST, if it isn't already in the list. */
236 static void
237 taint_list_add (struct taint_list *list, struct taint *taint)
238 {
239   if (!taint_list_contains (list, taint))
240     {
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;
251     }
252 }
253
254 /* Removes TAINT from LIST (which must contain it). */
255 static void
256 taint_list_remove (struct taint_list *list, const struct taint *taint)
257 {
258   size_t i;
259
260   for (i = 0; i < list->cnt; i++)
261     if (list->taints[i] == taint)
262       {
263         remove_element (list->taints, list->cnt, sizeof *list->taints, i);
264         list->cnt--;
265         return;
266       }
267
268   NOT_REACHED ();
269 }
270 \f
271 /* Marks TAINT as tainted, as well as all of its successors
272    recursively.  Also marks TAINT's predecessors as
273    successor-tainted, recursively. */
274 static void
275 recursively_set_taint (struct taint *taint)
276 {
277   size_t i;
278
279   taint->tainted = taint->tainted_successor = true;
280    for (i = 0; i < taint->successors.cnt; i++)
281     {
282       struct taint *s = taint->successors.taints[i];
283       if (!s->tainted)
284         recursively_set_taint (s);
285     }
286   for (i = 0; i < taint->predecessors.cnt; i++)
287     {
288       struct taint *p = taint->predecessors.taints[i];
289       if (!p->tainted_successor)
290         recursively_set_tainted_successor (p);
291     }
292 }
293
294 /* Marks TAINT as successor-tainted, as well as all of its
295    predecessors recursively. */
296 static void
297 recursively_set_tainted_successor (struct taint *taint)
298 {
299   size_t i;
300
301   taint->tainted_successor = true;
302   for (i = 0; i < taint->predecessors.cnt; i++)
303     {
304       struct taint *p = taint->predecessors.taints[i];
305       if (!p->tainted_successor)
306         recursively_set_tainted_successor (p);
307     }
308 }
309