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