Fix GCC 4.3 warning about uninitialized structure member.
[pspp] / src / libpspp / taint.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 #include <config.h>
18
19 #include <libpspp/taint.h>
20
21 #include <stddef.h>
22
23 #include <libpspp/array.h>
24 #include <libpspp/assertion.h>
25
26 #include "xalloc.h"
27
28 /* This code maintains two invariants:
29
30    1. If a node is tainted, then all of its successors are
31       tainted.
32
33    2. If a node is tainted, then it and all of its predecessors are
34       successor-tainted. */
35
36 /* A list of pointers to taint structures. */
37 struct taint_list
38   {
39     size_t cnt;
40     struct taint **taints;
41   };
42
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 *);
47
48 /* A taint. */
49 struct taint
50   {
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? */
56   };
57
58 static void recursively_set_taint (struct taint *);
59 static void recursively_set_tainted_successor (struct taint *);
60
61 /* Creates and returns a new taint object. */
62 struct taint *
63 taint_create (void)
64 {
65   struct taint *taint = xmalloc (sizeof *taint);
66   taint->ref_cnt = 1;
67   taint_list_init (&taint->successors);
68   taint_list_init (&taint->predecessors);
69   taint->tainted = false;
70   taint->tainted_successor = false;
71   return taint;
72 }
73
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.) */
79 struct taint *
80 taint_clone (const struct taint *taint_)
81 {
82   struct taint *taint = (struct taint *) taint_;
83
84   assert (taint->ref_cnt > 0);
85   taint->ref_cnt++;
86   return taint;
87 }
88
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
94    still taint C. */
95 bool
96 taint_destroy (struct taint *taint)
97 {
98   if ( 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   return true;
123 }
124
125 /* Adds a propagation relationship from FROM to TO.  This means
126    that, should FROM ever become tainted, then TO will
127    automatically be marked tainted as well.  This takes effect
128    immediately: if FROM is currently tainted, then TO will be
129    tainted after the call completes.
130
131    Taint propagation is transitive: if A propagates to B and B
132    propagates to C, then tainting A taints both B and C.  Taint
133    propagation is not commutative: propagation from A to B does
134    not imply propagation from B to A.  Taint propagation is
135    robust against loops, so that if A propagates to B and vice
136    versa, whether directly or indirectly, then tainting either A
137    or B will cause the other to be tainted, without producing an
138    infinite loop. */
139 void
140 taint_propagate (const struct taint *from_, const struct taint *to_)
141 {
142   struct taint *from = (struct taint *) from_;
143   struct taint *to = (struct taint *) to_;
144
145   if (from != to)
146     {
147       taint_list_add (&from->successors, to);
148       taint_list_add (&to->predecessors, from);
149       if (from->tainted && !to->tainted)
150         recursively_set_taint (to);
151       else if (to->tainted_successor && !from->tainted_successor)
152         recursively_set_tainted_successor (from);
153     }
154 }
155
156 /* Returns true if TAINT is tainted, false otherwise. */
157 bool
158 taint_is_tainted (const struct taint *taint)
159 {
160   return taint->tainted;
161 }
162
163 /* Marks TAINT tainted and propagates the taint to all of its
164    successors. */
165 void
166 taint_set_taint (const struct taint *taint_)
167 {
168   struct taint *taint = (struct taint *) taint_;
169   if (!taint->tainted)
170     recursively_set_taint (taint);
171 }
172
173 /* Returns true if TAINT is successor-tainted, that is, if it or
174    any of its successors is or ever has been tainted.  (A
175    "successor" of a taint object X is any taint object that can
176    be reached by following propagation relationships starting
177    from X.) */
178 bool
179 taint_has_tainted_successor (const struct taint *taint)
180 {
181   return taint->tainted_successor;
182 }
183
184 /* Attempts to reset the successor-taint on TAINT.  This is
185    successful only if TAINT currently has no tainted successor. */
186 void
187 taint_reset_successor_taint (const struct taint *taint_)
188 {
189   struct taint *taint = (struct taint *) taint_;
190
191   if (taint->tainted_successor)
192     {
193       size_t i;
194
195       for (i = 0; i < taint->successors.cnt; i++)
196         if (taint->successors.taints[i]->tainted_successor)
197           return;
198
199       taint->tainted_successor = false;
200     }
201 }
202 \f
203 /* Initializes LIST as an empty list of taints. */
204 static void
205 taint_list_init (struct taint_list *list)
206 {
207   list->cnt = 0;
208   list->taints = NULL;
209 }
210
211 /* Destroys LIST. */
212 static void
213 taint_list_destroy (struct taint_list *list)
214 {
215   free (list->taints);
216 }
217
218 /* Returns true if TAINT is in LIST, false otherwise. */
219 static bool
220 taint_list_contains (const struct taint_list *list, const struct taint *taint)
221 {
222   size_t i;
223
224   for (i = 0; i < list->cnt; i++)
225     if (list->taints[i] == taint)
226       return true;
227
228   return false;
229 }
230
231 /* Returns true if X is zero or a power of 2, false otherwise. */
232 static bool
233 is_zero_or_power_of_2 (size_t x)
234 {
235   return (x & (x - 1)) == 0;
236 }
237
238 /* Adds TAINT to LIST, if it isn't already in the list. */
239 static void
240 taint_list_add (struct taint_list *list, struct taint *taint)
241 {
242   if (!taint_list_contains (list, taint))
243     {
244       /* To save a few bytes of memory per list, we don't store
245          the list capacity as a separate member.  Instead, the
246          list capacity is always zero or a power of 2.  Thus, if
247          the list count is one of these threshold values, we need
248          to allocate more memory. */
249       if (is_zero_or_power_of_2 (list->cnt))
250         list->taints = xnrealloc (list->taints,
251                                   list->cnt == 0 ? 1 : 2 * list->cnt,
252                                   sizeof *list->taints);
253       list->taints[list->cnt++] = taint;
254     }
255 }
256
257 /* Removes TAINT from LIST (which must contain it). */
258 static void
259 taint_list_remove (struct taint_list *list, const struct taint *taint)
260 {
261   size_t i;
262
263   for (i = 0; i < list->cnt; i++)
264     if (list->taints[i] == taint)
265       {
266         remove_element (list->taints, list->cnt, sizeof *list->taints, i);
267         list->cnt--;
268         return;
269       }
270
271   NOT_REACHED ();
272 }
273 \f
274 /* Marks TAINT as tainted, as well as all of its successors
275    recursively.  Also marks TAINT's predecessors as
276    successor-tainted, recursively. */
277 static void
278 recursively_set_taint (struct taint *taint)
279 {
280   size_t i;
281
282   taint->tainted = taint->tainted_successor = true;
283    for (i = 0; i < taint->successors.cnt; i++)
284     {
285       struct taint *s = taint->successors.taints[i];
286       if (!s->tainted)
287         recursively_set_taint (s);
288     }
289   for (i = 0; i < taint->predecessors.cnt; i++)
290     {
291       struct taint *p = taint->predecessors.taints[i];
292       if (!p->tainted_successor)
293         recursively_set_tainted_successor (p);
294     }
295 }
296
297 /* Marks TAINT as successor-tainted, as well as all of its
298    predecessors recursively. */
299 static void
300 recursively_set_tainted_successor (struct taint *taint)
301 {
302   size_t i;
303
304   taint->tainted_successor = true;
305   for (i = 0; i < taint->predecessors.cnt; i++)
306     {
307       struct taint *p = taint->predecessors.taints[i];
308       if (!p->tainted_successor)
309         recursively_set_tainted_successor (p);
310     }
311 }
312