?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Code cleanup
[gnumeric.git] / src / dependent.c
blob757ff604bac64e7002a2232e97db54bd2ae77d1f
1 /* vim: set sw=8: -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
2 /*
3 * dependent.c: Manage calculation dependencies between objects
4 *
5 * Copyright (C) 2000-2006 Jody Goldberg (jody@gnome.org)
6 * Copyright (C) 2006-2013 Morten Welinder (terra@gnome.org)
7 *
8 * This program is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU General Public License as
10 * published by the Free Software Foundation; either version 2 of the
11 * License, or (at your option) version 3.
12 *
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
21 * USA
22 */
23 #include <gnumeric-config.h>
24 #include "gnumeric.h"
25 #include "dependent.h"
26
27 #include "workbook-priv.h"
28 #include "value.h"
29 #include "cell.h"
30 #include "sheet.h"
31 #include "expr.h"
32 #include "expr-impl.h"
33 #include "expr-name.h"
34 #include "application.h"
35 #include "workbook-view.h"
36 #include "ranges.h"
37 #include "gutils.h"
38 #include "sheet-view.h"
39 #include "func.h"
40
41 #include <goffice/goffice.h>
42 #include <string.h>
43
44 static gboolean gnm_cell_eval_content (GnmCell *cell);
45 static void dependent_changed (GnmDependent *dep);
46 static void dependent_clear_dynamic_deps (GnmDependent *dep);
47
48 /* ------------------------------------------------------------------------- */
49
50 /*
51 * Note: we unconditionally use pools for
52 * deps->range_pool
53 * deps->single_pool
54 * since we need the ability to free en masse.
55 */
56
57 #ifndef USE_POOLS
58 #define USE_POOLS 0
59 #endif
60
61 #if USE_POOLS
62 static GOMemChunk *micro_few_pool;
63 static GOMemChunk *cset_pool;
64 #define CHUNK_ALLOC(T,p) ((T*)go_mem_chunk_alloc (p))
65 #define CHUNK_FREE(p,v) go_mem_chunk_free ((p), (v))
66 #define MICRO_HASH_FEW 3 /* Odd and small. */
67 #define NEW_FEW CHUNK_ALLOC (gpointer, micro_few_pool)
68 #define FREE_FEW(p) CHUNK_FREE (micro_few_pool, p)
69 #else
70 #define CHUNK_ALLOC(T,c) g_slice_new (T)
71 #define CHUNK_FREE(p,v) g_slice_free1 (sizeof(*v),(v))
72 #define MICRO_HASH_FEW 4 /* Even and small. */
73 #define NEW_FEW (gpointer *)g_slice_alloc (MICRO_HASH_FEW * sizeof (gpointer))
74 #define FREE_FEW(p) g_slice_free1 (MICRO_HASH_FEW * sizeof (gpointer), p)
75 #endif
76
77 /* ------------------------------------------------------------------------- */
78 /* Maps between row numbers and bucket numbers. */
79
80 #define BUCKET_SIZE 1024
81 #define BUCKET_OF_ROW(row) ((row) / BUCKET_SIZE)
82 #define BUCKET_START_ROW(b) ((b) * BUCKET_SIZE)
83 #define BUCKET_END_ROW(b) ((b) * BUCKET_SIZE + (BUCKET_SIZE - 1))
84
85 /* ------------------------------------------------------------------------- */
86
87 /* Keep this odd */
88 #define CSET_SEGMENT_SIZE 29
89
90 typedef struct _CSet CSet;
91 struct _CSet {
92 int count;
93 CSet *next;
94 gpointer data[CSET_SEGMENT_SIZE];
95 /* And one pointer for allocation overhead. */
96 };
97
98 #if 0
99 static gboolean
100 cset_find (CSet *list, gpointer datum)
101 {
102 while (list) {
103 guint i = list->count;
104 while (i-- > 0)
105 if (list->data[i] == datum)
106 return TRUE;
107 list = list->next;
108 }
109 return FALSE;
110 }
111 #endif
112
113 static void
114 cset_free (CSet *list)
115 {
116 while (list) {
117 CSet *next = list->next;
118 CHUNK_FREE (cset_pool, list);
119 list = next;
120 }
121 }
122
123 /* NOTE: takes reference. */
124 static void
125 cset_insert (CSet **list, gpointer datum)
126 {
127 CSet *cs = *list;
128 if (cs == NULL || cs->count == CSET_SEGMENT_SIZE) {
129 CSet *h = *list = CHUNK_ALLOC (CSet, cset_pool);
130 h->next = cs;
131 h->count = 1;
132 h->data[0] = datum;
133 } else
134 cs->data[cs->count++] = datum;
135 }
136
137 /* NOTE: takes reference. Returns TRUE if datum was already present. */
138 static gboolean
139 cset_insert_checked (CSet **list, gpointer datum)
140 {
141 CSet *cs = *list;
142 CSet *nonfull = NULL;
143
144 while (cs) {
145 guint i = cs->count;
146 if (i != CSET_SEGMENT_SIZE)
147 nonfull = cs;
148 while (i-- > 0)
149 if (cs->data[i] == datum)
150 return TRUE;
151 cs = cs->next;
152 }
153
154 if (nonfull)
155 nonfull->data[nonfull->count++] = datum;
156 else
157 cset_insert (list, datum);
158 return FALSE;
159 }
160
161
162 /* NOTE: takes reference. Returns TRUE if removed. */
163 static gboolean
164 cset_remove (CSet **list, gpointer datum)
165 {
166 CSet *l, *last = NULL;
167
168 for (l = *list; l; l = l->next) {
169 guint i;
170
171 for (i = l->count; i-- > 0; )
172 if (l->data[i] == datum) {
173 l->count--;
174 if (l->count == 0) {
175 if (last)
176 last->next = l->next;
177 else
178 *list = l->next;
179 CHUNK_FREE (cset_pool, l);
180 } else
181 l->data[i] = l->data[l->count];
182 return TRUE;
183 }
184 last = l;
185 }
186 return FALSE;
187 }
188
189 #define CSET_FOREACH(list,var,code) \
190 do { \
191 CSet *cs_; \
192 for (cs_ = (list); cs_; cs_ = cs_->next) { \
193 guint i_; \
194 for (i_ = cs_->count; i_-- > 0; ) { \
195 var = cs_->data[i_]; \
196 code \
197 } \
198 } \
199 } while (0)
200
201
202 /* ------------------------------------------------------------------------- */
203
204 static void
205 gnm_dep_set_expr_undo_undo (GnmDependent *dep, GnmExprTop const *texpr)
206 {
207 dependent_set_expr (dep, texpr);
208 dependent_link (dep);
209 dependent_changed (dep);
210 }
211
212 static GOUndo *
213 gnm_dep_set_expr_undo_new (GnmDependent *dep)
214 {
215 gnm_expr_top_ref (dep->texpr);
216 return go_undo_binary_new (dep, (gpointer)dep->texpr,
217 (GOUndoBinaryFunc)gnm_dep_set_expr_undo_undo,
218 NULL,
219 (GFreeFunc)gnm_expr_top_unref);
220 }
221
222 static GOUndo *
223 gnm_dep_unlink_undo_new (GSList *deps)
224 {
225 return go_undo_unary_new (deps,
226 (GOUndoUnaryFunc)dependents_link,
227 (GFreeFunc)g_slist_free);
228 }
229
230 /* ------------------------------------------------------------------------- */
231
232 #undef DEBUG_EVALUATION
233
234 static void
235 dummy_dep_eval (G_GNUC_UNUSED GnmDependent *dep)
236 {
237 }
238
239 static void cell_dep_eval (GnmDependent *dep);
240 static void cell_dep_set_expr (GnmDependent *dep, GnmExprTop const *new_texpr);
241 static GSList *cell_dep_changed (GnmDependent *dep);
242 static GnmCellPos *cell_dep_pos (GnmDependent const *dep);
243 static void cell_dep_debug_name (GnmDependent const *dep, GString *target);
244 static const GnmDependentClass cell_dep_class = {
245 cell_dep_eval,
246 cell_dep_set_expr,
247 cell_dep_changed,
248 cell_dep_pos,
249 cell_dep_debug_name,
250 };
251
252 static GSList *dynamic_dep_changed (GnmDependent *dep);
253 static void dynamic_dep_debug_name (GnmDependent const *dep, GString *target);
254 static const GnmDependentClass dynamic_dep_class = {
255 dummy_dep_eval,
256 NULL,
257 dynamic_dep_changed,
258 NULL,
259 dynamic_dep_debug_name,
260 };
261 typedef struct {
262 GnmDependent base;
263 GnmDependent *container;
264 GSList *ranges;
265 GSList *singles;
266 } DynamicDep;
267
268 static void name_dep_debug_name (GnmDependent const *dep, GString *target);
269 static const GnmDependentClass name_dep_class = {
270 dummy_dep_eval,
271 NULL,
272 NULL,
273 NULL,
274 name_dep_debug_name,
275 };
276
277 static void managed_dep_debug_name (GnmDependent const *dep, GString *target);
278 static const GnmDependentClass managed_dep_class = {
279 dummy_dep_eval,
280 NULL,
281 NULL,
282 NULL,
283 managed_dep_debug_name,
284 };
285
286 static void style_dep_eval (GnmDependent *dep);
287 static GSList *style_dep_changed (GnmDependent *dep);
288 static GnmCellPos *style_dep_pos (GnmDependent const *dep);
289 static void style_dep_debug_name (GnmDependent const *dep, GString *target);
290 static const GnmDependentClass style_dep_class = {
291 style_dep_eval,
292 NULL,
293 style_dep_changed,
294 style_dep_pos,
295 style_dep_debug_name,
296 };
297 typedef struct {
298 GnmDependent base;
299 GnmCellPos pos;
300 } GnmStyleDependent;
301
302
303 static GPtrArray *dep_classes = NULL;
304
305 void
306 dependent_types_init (void)
307 {
308 g_return_if_fail (dep_classes == NULL);
309
310 /* Init with a NULL class so we can access directly */
311 dep_classes = g_ptr_array_new ();
312 g_ptr_array_add (dep_classes, NULL); /* bogus filler */
313 g_ptr_array_add (dep_classes, (gpointer)&cell_dep_class);
314 g_ptr_array_add (dep_classes, (gpointer)&dynamic_dep_class);
315 g_ptr_array_add (dep_classes, (gpointer)&name_dep_class);
316 g_ptr_array_add (dep_classes, (gpointer)&managed_dep_class);
317 g_ptr_array_add (dep_classes, (gpointer)&style_dep_class);
318
319 #if USE_POOLS
320 micro_few_pool =
321 go_mem_chunk_new ("micro few pool",
322 MICRO_HASH_FEW * sizeof (gpointer),
323 16 * 1024 - 128);
324 cset_pool =
325 go_mem_chunk_new ("cset pool",
326 sizeof (CSet),
327 16 * 1024 - 128);
328 #endif
329 }
330
331 void
332 dependent_types_shutdown (void)
333 {
334 g_return_if_fail (dep_classes != NULL);
335 g_ptr_array_free (dep_classes, TRUE);
336 dep_classes = NULL;
337
338 #if USE_POOLS
339 go_mem_chunk_destroy (micro_few_pool, FALSE);
340 micro_few_pool = NULL;
341 go_mem_chunk_destroy (cset_pool, FALSE);
342 cset_pool = NULL;
343 #endif
344 }
345
346 /**
347 * dependent_register_type:
348 * @klass: A vtable
349 *
350 * Store the vtable and allocate an ID for a new class
351 * of dependents.
352 */
353 guint32
354 dependent_type_register (GnmDependentClass const *klass)
355 {
356 guint32 res;
357
358 g_return_val_if_fail (dep_classes != NULL, 0);
359
360 g_ptr_array_add (dep_classes, (gpointer)klass);
361 res = dep_classes->len-1;
362
363 g_return_val_if_fail (res <= DEPENDENT_TYPE_MASK, res);
364
365 return res;
366 }
367
368 /*
369 * dependent_flag_recalc:
370 * @dep: the dependent that contains the expression needing recomputation.
371 *
372 * Marks @dep as needing recalculation
373 * NOTE : it does NOT recursively dirty dependencies.
374 */
375 #define dependent_flag_recalc(dep) \
376 do { (dep)->flags |= DEPENDENT_NEEDS_RECALC; } while (0)
377
378 /**
379 * dependent_changed:
380 * @cell: the dependent that changed
381 *
382 * Queues a recalc.
383 */
384 static void
385 dependent_changed (GnmDependent *dep)
386 {
387 if (dep->sheet &&
388 dep->sheet->workbook->recursive_dirty_enabled)
389 dependent_queue_recalc (dep);
390 else
391 dependent_flag_recalc (dep);
392 }
393
394 /**
395 * dependent_set_expr:
396 * @dep: The dependent we are interested in.
397 * @new_texpr: new expression.
398 *
399 * When the expression associated with @dep needs to change this routine
400 * dispatches to the virtual handler, unlinking @dep if necessary beforehand.
401 * Adds a ref to @new_expr.
402 *
403 * NOTE : it does NOT relink dependents in case they are going to move later.
404 **/
405 void
406 dependent_set_expr (GnmDependent *dep, GnmExprTop const *new_texpr)
407 {
408 int const t = dependent_type (dep);
409 GnmDependentClass *klass = g_ptr_array_index (dep_classes, t);
410
411 if (dependent_is_linked (dep))
412 dependent_unlink (dep);
413 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS)
414 dependent_clear_dynamic_deps (dep);
415
416 if (klass->set_expr)
417 klass->set_expr (dep, new_texpr);
418 else {
419 if (new_texpr)
420 gnm_expr_top_ref (new_texpr);
421 if (dep->texpr)
422 gnm_expr_top_unref (dep->texpr);
423 dep->texpr = new_texpr;
424 if (new_texpr)
425 dependent_changed (dep);
426 }
427 }
428
429 gboolean
430 dependent_has_pos (GnmDependent const *dep)
431 {
432 int const t = dependent_type (dep);
433 GnmDependentClass *klass = g_ptr_array_index (dep_classes, t);
434 return klass->pos != NULL;
435 }
436
437 GnmCellPos const *
438 dependent_pos (GnmDependent const *dep)
439 {
440 static GnmCellPos const dummy = { 0, 0 };
441 int const t = dependent_type (dep);
442 GnmDependentClass *klass = g_ptr_array_index (dep_classes, t);
443
444 return klass->pos ? klass->pos (dep) : &dummy;
445 }
446
447 void
448 dependent_move (GnmDependent *dep, int dx, int dy)
449 {
450 int const t = dependent_type (dep);
451 GnmDependentClass *klass = g_ptr_array_index (dep_classes, t);
452 GnmCellPos *pos;
453
454 g_return_if_fail (klass->pos != NULL);
455 pos = klass->pos (dep);
456 /* Need a virtual for this? */
457 pos->col += dx;
458 pos->row += dy;
459 }
460
461
462 /**
463 * dependent_set_sheet:
464 * @dep:
465 * @sheet:
466 */
467 void
468 dependent_set_sheet (GnmDependent *dep, Sheet *sheet)
469 {
470 g_return_if_fail (dep != NULL);
471 g_return_if_fail (dep->sheet == NULL);
472 g_return_if_fail (!dependent_is_linked (dep));
473
474 dep->sheet = sheet;
475 if (dep->texpr) {
476 dependent_link (dep);
477 dependent_changed (dep);
478 }
479 }
480
481 static void
482 cb_cell_list_deps (GnmDependent *dep, gpointer user)
483 {
484 GSList **list = (GSList **)user;
485 *list = g_slist_prepend (*list, dep);
486 }
487
488 static GSList *
489 cell_list_deps (GnmCell const *cell)
490 {
491 GSList *deps = NULL;
492 cell_foreach_dep (cell, cb_cell_list_deps, &deps);
493 return deps;
494 }
495
496 static void
497 dependent_queue_recalc_main (GSList *work)
498 {
499 /*
500 * Work is now a list of marked cells whose dependencies need
501 * to be marked. Marking early guarentees that we will not
502 * get duplicates. (And it thus limits the length of the list.)
503 * We treat work as a stack.
504 */
505
506 while (work) {
507 GnmDependent *dep = work->data;
508 int const t = dependent_type (dep);
509 GnmDependentClass *klass = g_ptr_array_index (dep_classes, t);
510
511 /* Pop the top element. */
512 work = g_slist_delete_link (work, work);
513
514 if (klass->changed) {
515 GSList *extra = klass->changed (dep);
516 if (extra) {
517 g_slist_last (extra)->next = work;
518 work = extra;
519 }
520 }
521 }
522 }
523
524
525 /**
526 * dependent_queue_recalc_list:
527 * @list:
528 *
529 * Queues any elements of @list for recalc that are not already queued,
530 * and marks all elements as needing a recalc.
531 */
532 static void
533 dependent_queue_recalc_list (GSList *list)
534 {
535 GSList *work = NULL;
536
537 for (; list != NULL ; list = list->next) {
538 GnmDependent *dep = list->data;
539 if (!dependent_needs_recalc (dep)) {
540 dependent_flag_recalc (dep);
541 work = g_slist_prepend (work, dep);
542 }
543 }
544
545 dependent_queue_recalc_main (work);
546 }
547
548 void
549 dependent_queue_recalc (GnmDependent *dep)
550 {
551 g_return_if_fail (dep != NULL);
552
553 #ifdef DEBUG_EVALUATION
554 g_printerr ("/* QUEUE (%s) */\n", cell_name (GNM_DEP_TO_CELL (dep)));
555 #endif
556 if (!dependent_needs_recalc (dep)) {
557 GSList listrec;
558 listrec.next = NULL;
559 listrec.data = dep;
560 dependent_queue_recalc_list (&listrec);
561 }
562 }
563
564 /**************************************************************************/
565
566 typedef struct {
567 gint num_buckets;
568 gint num_elements;
569 union {
570 gpointer one;
571 gpointer *few;
572 CSet **many;
573 } u;
574 } MicroHash;
575
576 #define MICRO_HASH_MIN_SIZE 11
577 #define MICRO_HASH_MAX_SIZE 13845163
578
579 #define MICRO_HASH_hash(key) ((guint)GPOINTER_TO_UINT(key))
580
581 static void
582 micro_hash_many_to_few (MicroHash *hash_table)
583 {
584 CSet **buckets = hash_table->u.many;
585 int nbuckets = hash_table->num_buckets;
586 int i = 0;
587
588 hash_table->u.few = NEW_FEW;
589
590 while (nbuckets-- > 0 ) {
591 gpointer datum;
592
593 CSET_FOREACH (buckets[nbuckets], datum, {
594 hash_table->u.few[i++] = datum;
595 });
596 cset_free (buckets[nbuckets]);
597 }
598
599 g_free (buckets);
600 }
601
602 static void
603 micro_hash_many_resize (MicroHash *hash_table, int new_nbuckets)
604 {
605 CSet **buckets = hash_table->u.many;
606 int nbuckets = hash_table->num_buckets;
607 CSet **new_buckets = g_new0 (CSet *, new_nbuckets);
608
609 hash_table->u.many = new_buckets;
610 hash_table->num_buckets = new_nbuckets;
611
612 while (nbuckets-- > 0 ) {
613 gpointer datum;
614
615 CSET_FOREACH (buckets[nbuckets], datum, {
616 guint bucket = MICRO_HASH_hash (datum) % new_nbuckets;
617 cset_insert (&(new_buckets[bucket]), datum);
618 });
619 cset_free (buckets[nbuckets]);
620 }
621 g_free (buckets);
622
623 #if 0
624 {
625 int nonzero = 0;
626 int capacity = 0, totlen = 0;
627 int i;
628
629 for (i = 0; i < new_nbuckets; i++) {
630 CSet *cs = new_buckets[i];
631 if (cs) {
632 nonzero++;
633 while (cs) {
634 totlen += cs->count;
635 capacity += CSET_SEGMENT_SIZE;
636 cs = cs->next;
637 }
638 }
639 }
640
641 g_printerr ("resize %p: %d [%d %.1f %.0f%%]\n",
642 hash_table,
643 new_nbuckets,
644 hash_table->num_elements,
645 (double)totlen / nonzero,
646 100.0 * totlen / capacity);
647 }
648 #endif
649 }
650
651
652 static void
653 micro_hash_few_to_many (MicroHash *hash_table)
654 {
655 int nbuckets = hash_table->num_buckets = MICRO_HASH_MIN_SIZE;
656 CSet **buckets = g_new0 (CSet *, nbuckets);
657 int i;
658
659 for (i = 0; i < hash_table->num_elements; i++) {
660 gpointer datum = hash_table->u.few[i];
661 guint bucket = MICRO_HASH_hash (datum) % nbuckets;
662 cset_insert (&(buckets[bucket]), datum);
663 }
664 FREE_FEW (hash_table->u.few);
665 hash_table->u.many = buckets;
666 }
667
668
669
670 static void
671 micro_hash_insert (MicroHash *hash_table, gpointer key)
672 {
673 int N = hash_table->num_elements;
674
675 g_return_if_fail (key != NULL);
676
677 if (N == 0) {
678 hash_table->u.one = key;
679 } else if (N == 1) {
680 gpointer key0 = hash_table->u.one;
681 if (key == key0)
682 return;
683 /* one --> few */
684 hash_table->u.few = NEW_FEW;
685 hash_table->u.few[0] = key0;
686 hash_table->u.few[1] = key;
687 memset (hash_table->u.few + 2, 0, (MICRO_HASH_FEW - 2) * sizeof (gpointer));
688 } else if (N <= MICRO_HASH_FEW) {
689 int i;
690
691 for (i = 0; i < N; i++)
692 if (hash_table->u.few[i] == key)
693 return;
694
695 if (N == MICRO_HASH_FEW) {
696 guint bucket;
697
698 micro_hash_few_to_many (hash_table);
699 bucket = MICRO_HASH_hash (key) % hash_table->num_buckets;
700 cset_insert (&(hash_table->u.many[bucket]), key);
701 } else
702 hash_table->u.few[N] = key;
703 } else {
704 int nbuckets = hash_table->num_buckets;
705 guint bucket = MICRO_HASH_hash (key) % nbuckets;
706 CSet **buckets = hash_table->u.many;
707
708 if (cset_insert_checked (&(buckets[bucket]), key))
709 return;
710
711 if (N > CSET_SEGMENT_SIZE * nbuckets &&
712 nbuckets < MICRO_HASH_MAX_SIZE) {
713 int new_nbuckets = g_spaced_primes_closest (N / (CSET_SEGMENT_SIZE / 2));
714 if (new_nbuckets > MICRO_HASH_MAX_SIZE)
715 new_nbuckets = MICRO_HASH_MAX_SIZE;
716 micro_hash_many_resize (hash_table, new_nbuckets);
717 }
718 }
719
720 hash_table->num_elements++;
721 }
722
723 static void
724 micro_hash_remove (MicroHash *hash_table, gpointer key)
725 {
726 int N = hash_table->num_elements;
727 guint bucket;
728
729 if (N == 0)
730 return;
731
732 if (N == 1) {
733 if (hash_table->u.one != key)
734 return;
735 hash_table->u.one = NULL;
736 hash_table->num_elements--;
737 return;
738 }
739
740 if (N <= MICRO_HASH_FEW) {
741 int i;
742
743 for (i = 0; i < N; i++)
744 if (hash_table->u.few[i] == key) {
745 hash_table->u.few[i] = hash_table->u.few[N - 1];
746 hash_table->num_elements--;
747 if (hash_table->num_elements > 1)
748 return;
749 /* few -> one */
750 key = hash_table->u.few[0];
751 FREE_FEW (hash_table->u.few);
752 hash_table->u.one = key;
753 return;
754 }
755 return;
756 }
757
758 bucket = MICRO_HASH_hash (key) % hash_table->num_buckets;
759 if (cset_remove (&(hash_table->u.many[bucket]), key)) {
760 hash_table->num_elements--;
761
762 if (hash_table->num_elements <= MICRO_HASH_FEW)
763 micro_hash_many_to_few (hash_table);
764 else {
765 /* Maybe resize? */
766 }
767 return;
768 }
769 }
770
771
772 static void
773 micro_hash_release (MicroHash *hash_table)
774 {
775 int N = hash_table->num_elements;
776
777 if (N <= 1)
778 ; /* Nothing */
779 else if (N <= MICRO_HASH_FEW)
780 FREE_FEW (hash_table->u.few);
781 else {
782 guint i = hash_table->num_buckets;
783 while (i-- > 0)
784 cset_free (hash_table->u.many[i]);
785 g_free (hash_table->u.many);
786 }
787 hash_table->num_elements = 0;
788 hash_table->num_buckets = 1;
789 hash_table->u.one = NULL;
790 }
791
792 static void
793 micro_hash_init (MicroHash *hash_table, gpointer key)
794 {
795 hash_table->num_elements = 1;
796 hash_table->u.one = key;
797 }
798
799 static inline gboolean
800 micro_hash_is_empty (MicroHash const *hash_table)
801 {
802 return hash_table->num_elements == 0;
803 }
804
805 /*************************************************************************/
806
807 #define micro_hash_foreach_dep(dc, dep, code) do { \
808 guint i_ = dc.num_elements; \
809 if (i_ <= MICRO_HASH_FEW) { \
810 const gpointer *e_ = (i_ == 1) ? &dc.u.one : dc.u.few; \
811 while (i_-- > 0) { \
812 GnmDependent *dep = e_[i_]; \
813 code \
814 } \
815 } else { \
816 GnmDependent *dep; \
817 guint b_ = dc.num_buckets; \
818 while (b_-- > 0) \
819 CSET_FOREACH (dc.u.many[b_], dep, code); \
820 } \
821 } while (0)
822
823 /**************************************************************************
824 * Data structures for managing dependencies between objects.
825 *
826 * The DependencyRange hash needs to be improved. It is a huge
827 * performance hit when there are large numbers of range depends.
828 */
829
830 /*
831 * A DependencyRange defines a range of cells whose values
832 * are used by another objects in the spreadsheet.
833 *
834 * A change in those cells will trigger a recomputation on the
835 * cells listed in deps.
836 */
837 typedef struct {
838 MicroHash deps; /* Must be first */
839 GnmRange range;
840 } DependencyRange;
841
842 /*
843 * A DependencySingle stores a list of dependents that rely
844 * on the cell at @pos.
845 *
846 * A change in this cell will trigger a recomputation on the
847 * cells listed in deps.
848 */
849 typedef struct {
850 MicroHash deps; /* Must be first */
851 GnmCellPos pos;
852 } DependencySingle;
853
854 /* A utility type */
855 typedef struct {
856 MicroHash deps; /* Must be first */
857 } DependencyAny;
858
859 static guint
860 deprange_hash (DependencyRange const *r)
861 {
862 guint a = r->range.start.row;
863 guint b = r->range.end.row;
864 guint c = r->range.start.col;
865 guint d = r->range.end.col;
866
867 return (((((a << 8) + b) << 8) + c) << 8) + d;
868 }
869
870 static gint
871 deprange_equal (DependencyRange const *r1, DependencyRange const *r2)
872 {
873 return range_equal (&(r1->range), &(r2->range));
874 }
875
876 static guint
877 depsingle_hash (DependencySingle const *depsingle)
878 {
879 return (depsingle->pos.row << 8) ^ depsingle->pos.col;
880 }
881
882 static gint
883 depsingle_equal (DependencySingle const *a, DependencySingle const *b)
884 {
885 return (a->pos.row == b->pos.row && a->pos.col == b->pos.col);
886 }
887
888 static GnmDependentFlags
889 link_single_dep (GnmDependent *dep, GnmCellPos const *pos, GnmCellRef const *ref)
890 {
891 DependencySingle lookup;
892 DependencySingle *single;
893 GnmDependentFlags flag = DEPENDENT_NO_FLAG;
894 Sheet const *sheet = eval_sheet (ref->sheet, dep->sheet);
895 GnmDepContainer *deps = sheet->deps;
896
897 if (sheet != dep->sheet)
898 flag = (sheet->workbook != dep->sheet->workbook)
899 ? DEPENDENT_GOES_INTERBOOK
900 : DEPENDENT_GOES_INTERSHEET;
901
902 /* Inserts if it is not already there */
903 gnm_cellpos_init_cellref (&lookup.pos, ref, pos, sheet);
904 single = g_hash_table_lookup (deps->single_hash, &lookup);
905 if (single == NULL) {
906 single = go_mem_chunk_alloc (deps->single_pool);
907 *single = lookup;
908 micro_hash_init (&single->deps, dep);
909 g_hash_table_insert (deps->single_hash, single, single);
910 } else
911 micro_hash_insert (&single->deps, dep);
912
913 return flag;
914 }
915
916 static GnmDependentFlags
917 unlink_single_dep (GnmDependent *dep, GnmCellPos const *pos, GnmCellRef const *a)
918 {
919 DependencySingle lookup;
920 DependencySingle *single;
921 GnmDependentFlags flag = DEPENDENT_NO_FLAG;
922 Sheet const *sheet = eval_sheet (a->sheet, dep->sheet);
923 GnmDepContainer *deps = sheet->deps;
924
925 if (sheet != dep->sheet)
926 flag = (sheet->workbook != dep->sheet->workbook)
927 ? DEPENDENT_GOES_INTERBOOK
928 : DEPENDENT_GOES_INTERSHEET;
929 if (!deps)
930 return flag;
931
932 gnm_cellpos_init_cellref (&lookup.pos, a, pos, sheet);
933 single = g_hash_table_lookup (deps->single_hash, &lookup);
934 if (single != NULL) {
935 micro_hash_remove (&single->deps, dep);
936 if (micro_hash_is_empty (&single->deps)) {
937 g_hash_table_remove (deps->single_hash, single);
938 micro_hash_release (&single->deps);
939 go_mem_chunk_free (deps->single_pool, single);
940 }
941 }
942
943 return flag;
944 }
945
946 static inline GnmDependentFlags
947 link_unlink_single_dep (GnmDependent *dep, GnmCellPos const *pos,
948 GnmCellRef const *a, gboolean qlink)
949 {
950 return qlink
951 ? link_single_dep (dep, pos, a)
952 : unlink_single_dep (dep, pos, a);
953 }
954
955
956 static void
957 link_range_dep (GnmDepContainer *deps, GnmDependent *dep,
958 DependencyRange const *r)
959 {
960 int i = BUCKET_OF_ROW (r->range.start.row);
961 int end = BUCKET_OF_ROW (r->range.end.row);
962 DependencyRange r2 = *r;
963
964 /*
965 * It is possible to see ranges bigger than the sheet when
966 * operating with 3D ranges. See bug #704109.
967 */
968 end = MIN (end, deps->buckets - 1);
969
970 for ( ; i <= end; i++) {
971 DependencyRange *result;
972
973 /* Restrict range to bucket. */
974 r2.range.start.row = MAX (r->range.start.row, BUCKET_START_ROW (i));
975 r2.range.end.row = MIN (r->range.end.row, BUCKET_END_ROW (i));
976
977 if (deps->range_hash[i] == NULL)
978 deps->range_hash[i] = g_hash_table_new (
979 (GHashFunc) deprange_hash,
980 (GEqualFunc) deprange_equal);
981 else {
982 result = g_hash_table_lookup (deps->range_hash[i], &r2);
983 if (result) {
984 /* Inserts if it is not already there */
985 micro_hash_insert (&result->deps, dep);
986 continue;
987 }
988 }
989
990 /* Create a new DependencyRange structure */
991 result = go_mem_chunk_alloc (deps->range_pool);
992 *result = r2;
993 micro_hash_init (&result->deps, dep);
994 g_hash_table_insert (deps->range_hash[i], result, result);
995 }
996 }
997
998 static void
999 unlink_range_dep (GnmDepContainer *deps, GnmDependent *dep,
1000 DependencyRange const *r)
1001 {
1002 int i = BUCKET_OF_ROW (r->range.start.row);
1003 int end = BUCKET_OF_ROW (r->range.end.row);
1004 DependencyRange r2 = *r;
1005
1006 if (!deps)
1007 return;
1008
1009 end = MIN (end, deps->buckets - 1);
1010
1011 for ( ; i <= end; i++) {
1012 DependencyRange *result;
1013
1014 /* Restrict range to bucket. */
1015 r2.range.start.row = MAX (r->range.start.row, BUCKET_START_ROW (i));
1016 r2.range.end.row = MIN (r->range.end.row, BUCKET_END_ROW (i));
1017
1018 result = g_hash_table_lookup (deps->range_hash[i], &r2);
1019 if (result) {
1020 micro_hash_remove (&result->deps, dep);
1021 if (micro_hash_is_empty (&result->deps)) {
1022 g_hash_table_remove (deps->range_hash[i], result);
1023 micro_hash_release (&result->deps);
1024 go_mem_chunk_free (deps->range_pool, result);
1025 }
1026 }
1027 }
1028 }
1029
1030 static inline void
1031 link_unlink_range_dep (GnmDepContainer *deps, GnmDependent *dep,
1032 DependencyRange const *r, gboolean qlink)
1033 {
1034 if (qlink)
1035 link_range_dep (deps, dep, r);
1036 else
1037 unlink_range_dep (deps, dep, r);
1038 }
1039
1040 static GnmDependentFlags
1041 link_unlink_cellrange_dep (GnmDependent *dep, GnmCellPos const *pos,
1042 GnmCellRef const *a, GnmCellRef const *b,
1043 gboolean qlink)
1044 {
1045 DependencyRange range;
1046 GnmDependentFlags flag = DEPENDENT_NO_FLAG;
1047
1048 gnm_cellpos_init_cellref (&range.range.start, a, pos, dep->sheet);
1049 gnm_cellpos_init_cellref (&range.range.end, b, pos, dep->sheet);
1050 range_normalize (&range.range);
1051
1052 if (a->sheet != NULL) {
1053 if (a->sheet != dep->sheet)
1054 flag = (a->sheet->workbook != dep->sheet->workbook)
1055 ? DEPENDENT_GOES_INTERBOOK : DEPENDENT_GOES_INTERSHEET;
1056
1057 if (b->sheet != NULL && a->sheet != b->sheet) {
1058 Workbook const *wb = a->sheet->workbook;
1059 int i = a->sheet->index_in_wb;
1060 int stop = b->sheet->index_in_wb;
1061 if (i > stop) { int tmp = i; i = stop ; stop = tmp; }
1062
1063 g_return_val_if_fail (b->sheet->workbook == wb, flag);
1064
1065 while (i <= stop) {
1066 Sheet *sheet = g_ptr_array_index (wb->sheets, i);
1067 i++;
1068 link_unlink_range_dep (sheet->deps, dep, &range,
1069 qlink);
1070 }
1071 flag |= DEPENDENT_HAS_3D;
1072 } else
1073 link_unlink_range_dep (a->sheet->deps, dep, &range,
1074 qlink);
1075 } else
1076 link_unlink_range_dep (dep->sheet->deps, dep, &range, qlink);
1077
1078 return flag;
1079 }
1080
1081 static GnmDependentFlags
1082 link_unlink_expr_dep (GnmEvalPos *ep, GnmExpr const *tree, gboolean qlink)
1083 {
1084 g_return_val_if_fail (tree != NULL, DEPENDENT_NO_FLAG);
1085
1086 switch (GNM_EXPR_GET_OPER (tree)) {
1087 case GNM_EXPR_OP_RANGE_CTOR: /* See #562363 */
1088 case GNM_EXPR_OP_INTERSECT:
1089 case GNM_EXPR_OP_ANY_BINARY:
1090 return link_unlink_expr_dep (ep, tree->binary.value_a, qlink) |
1091 link_unlink_expr_dep (ep, tree->binary.value_b, qlink);
1092 case GNM_EXPR_OP_ANY_UNARY:
1093 return link_unlink_expr_dep (ep, tree->unary.value, qlink);
1094 case GNM_EXPR_OP_CELLREF:
1095 return link_unlink_single_dep (ep->dep, dependent_pos (ep->dep), &tree->cellref.ref, qlink);
1096
1097 case GNM_EXPR_OP_CONSTANT:
1098 /* TODO: pass in eval flags so that we can use implicit
1099 * intersection
1100 */
1101 if (VALUE_IS_CELLRANGE (tree->constant.value))
1102 return link_unlink_cellrange_dep
1103 (ep->dep, dependent_pos (ep->dep),
1104 &tree->constant.value->v_range.cell.a,
1105 &tree->constant.value->v_range.cell.b,
1106 qlink);
1107 return DEPENDENT_NO_FLAG;
1108
1109 /*
1110 * FIXME: needs to be taught implicit intersection +
1111 * more cunning handling of argument type matching.
1112 */
1113 case GNM_EXPR_OP_FUNCALL: {
1114 int i;
1115 GnmDependentFlags flag = DEPENDENT_NO_FLAG;
1116 if (tree->func.func->fn_type == GNM_FUNC_TYPE_STUB)
1117 gnm_func_load_stub (tree->func.func);
1118 if (tree->func.func->linker) {
1119 GnmFuncEvalInfo fei;
1120 fei.pos = ep;
1121 fei.func_call = &tree->func;
1122 flag = tree->func.func->linker (&fei, qlink);
1123 }
1124 if (!(flag & DEPENDENT_IGNORE_ARGS))
1125 for (i = 0; i < tree->func.argc; i++)
1126 flag |= link_unlink_expr_dep (ep, tree->func.argv[i], qlink);
1127 return flag;
1128 }
1129
1130 case GNM_EXPR_OP_NAME:
1131 if (qlink)
1132 expr_name_add_dep (tree->name.name, ep->dep);
1133 else
1134 expr_name_remove_dep (tree->name.name, ep->dep);
1135 if (expr_name_is_active (tree->name.name))
1136 return link_unlink_expr_dep (ep, tree->name.name->texpr->expr, qlink) | DEPENDENT_USES_NAME;
1137 return DEPENDENT_USES_NAME;
1138
1139 case GNM_EXPR_OP_ARRAY_ELEM: {
1140 /* Non-corner cells depend on the corner */
1141 GnmCellRef a;
1142 GnmCellPos const *pos = dependent_pos (ep->dep);
1143 // We cannot support array expressions unless we have
1144 // a position.
1145 g_return_val_if_fail (pos != NULL, DEPENDENT_NO_FLAG);
1146
1147 a.col_relative = a.row_relative = FALSE;
1148 a.sheet = ep->dep->sheet;
1149 a.col = pos->col - tree->array_elem.x;
1150 a.row = pos->row - tree->array_elem.y;
1151
1152 return link_unlink_single_dep (ep->dep, pos, &a, qlink);
1153 }
1154
1155 case GNM_EXPR_OP_ARRAY_CORNER: {
1156 // It's mildly unclean to do this here. We need the texpr, so get the cell.
1157 GnmCellPos const *cpos = dependent_pos (ep->dep);
1158 GnmCell const *cell = sheet_cell_get (ep->dep->sheet, cpos->col, cpos->row);
1159 GnmEvalPos pos = *ep;
1160 pos.array_texpr = cell->base.texpr;
1161 /* Corner cell depends on the contents of the expr */
1162 return link_unlink_expr_dep (&pos, tree->array_corner.expr, qlink);
1163 }
1164
1165 case GNM_EXPR_OP_SET: {
1166 int i;
1167 GnmDependentFlags res = DEPENDENT_NO_FLAG;
1168
1169 for (i = 0; i < tree->set.argc; i++)
1170 res |= link_unlink_expr_dep (ep, tree->set.argv[i], qlink);
1171 return res;
1172 }
1173 #ifndef DEBUG_SWITCH_ENUM
1174 default:
1175 g_assert_not_reached ();
1176 #endif
1177 }
1178 return DEPENDENT_NO_FLAG;
1179 }
1180
1181 static void
1182 workbook_link_3d_dep (GnmDependent *dep)
1183 {
1184 Workbook *wb = dep->sheet->workbook;
1185
1186 if (wb->being_reordered)
1187 return;
1188 if (wb->sheet_order_dependents == NULL)
1189 wb->sheet_order_dependents =
1190 g_hash_table_new (g_direct_hash, g_direct_equal);
1191 g_hash_table_insert (wb->sheet_order_dependents, dep, dep);
1192 }
1193
1194 static void
1195 workbook_unlink_3d_dep (GnmDependent *dep)
1196 {
1197 Workbook *wb = dep->sheet->workbook;
1198
1199 /* during destruction */
1200 if (wb->sheet_order_dependents == NULL)
1201 return;
1202
1203 if (wb->being_reordered)
1204 return;
1205
1206 g_hash_table_remove (wb->sheet_order_dependents, dep);
1207 }
1208
1209 /**
1210 * gnm_dep_style_dependency:
1211 * @sheet:
1212 * @texpr:
1213 * @r:
1214 * @accum: (inout) (transfer full) (element-type GnmDependent):
1215 **/
1216 void
1217 gnm_dep_style_dependency (Sheet *sheet,
1218 GnmExprTop const *texpr,
1219 GnmRange const *r,
1220 GPtrArray *accum)
1221 {
1222 int row, col;
1223
1224 /*
1225 * FIXME: Maybe do better for an expression that is just an
1226 * absolute ref.
1227 */
1228
1229 for (row = r->start.row; row <= r->end.row; row++) {
1230 for (col = r->start.col; col <= r->end.col; col++) {
1231 GnmStyleDependent *sd = g_new0 (GnmStyleDependent, 1);
1232 GnmDependent *dep = &sd->base;
1233
1234 dep->sheet = sheet;
1235 dep->flags = DEPENDENT_STYLE;
1236 dep->texpr = NULL;
1237 sd->pos.col = col;
1238 sd->pos.row = row;
1239
1240 dependent_set_expr (dep, texpr);
1241 dependent_link (dep);
1242 g_ptr_array_add (accum, dep);
1243 }
1244 }
1245 }
1246
1247 /*****************************************************************************/
1248
1249 static void
1250 cell_dep_eval (GnmDependent *dep)
1251 {
1252 gboolean finished = gnm_cell_eval_content (GNM_DEP_TO_CELL (dep));
1253 (void)finished; /* We don't currently care */
1254 dep->flags &= ~GNM_CELL_HAS_NEW_EXPR;
1255 }
1256
1257 static void
1258 cell_dep_set_expr (GnmDependent *dep, GnmExprTop const *new_texpr)
1259 {
1260 /*
1261 * Explicitly do not check for array subdivision, we may be
1262 * replacing the corner of an array.
1263 */
1264 gnm_cell_set_expr_unsafe (GNM_DEP_TO_CELL (dep), new_texpr);
1265 }
1266
1267 static GSList *
1268 cell_dep_changed (GnmDependent *dep)
1269 {
1270 /* When a cell changes, so do its dependents. */
1271
1272 GSList *deps = cell_list_deps (GNM_DEP_TO_CELL (dep));
1273 GSList *waste = NULL, *work = NULL;
1274 GSList *next, *list;
1275 for (list = deps; list != NULL ; list = next) {
1276 GnmDependent *dep = list->data;
1277 next = list->next;
1278 if (dependent_needs_recalc (dep)) {
1279 list->next = waste;
1280 waste = list;
1281 } else {
1282 dependent_flag_recalc (dep);
1283 list->next = work;
1284 work = list;
1285 }
1286 }
1287 g_slist_free (waste);
1288 return work;
1289 }
1290
1291 static GnmCellPos *
1292 cell_dep_pos (GnmDependent const *dep)
1293 {
1294 return &GNM_DEP_TO_CELL (dep)->pos;
1295 }
1296
1297 static void
1298 cell_dep_debug_name (GnmDependent const *dep, GString *target)
1299 {
1300 g_string_append (target, cell_name (GNM_DEP_TO_CELL (dep)));
1301 }
1302
1303 /*****************************************************************************/
1304 /*
1305 * "Managed" dependent handling.
1306 *
1307 * A managed dependent is simply an expression set up to be maintained by
1308 * the dependency system so it follows row/column insert/delete nicely.
1309 *
1310 * The expression being managed is typically a cell range, but can be any
1311 * expression. Everything is interpreted relative to A1 in the sheet.
1312 */
1313
1314 void
1315 dependent_managed_init (GnmDependent *dep, Sheet *sheet)
1316 {
1317 memset (dep, 0, sizeof (*dep));
1318 dep->flags = DEPENDENT_MANAGED;
1319 dep->sheet = sheet;
1320 }
1321
1322 void
1323 dependent_managed_set_expr (GnmDependent *dep, GnmExprTop const *texpr)
1324 {
1325 g_return_if_fail (dep != NULL);
1326 #if 0
1327 /* We need some kind of IS_A */
1328 g_return_if_fail (dependent_type (dep) == DEPENDENT_MANAGED);
1329 #endif
1330
1331 dependent_set_expr (dep, texpr);
1332 if (texpr && dep->sheet)
1333 dependent_link (dep);
1334 }
1335
1336 void
1337 dependent_managed_set_sheet (GnmDependent *dep, Sheet *sheet)
1338 {
1339 GnmExprTop const *texpr;
1340
1341 g_return_if_fail (dep != NULL);
1342 #if 0
1343 /* We need some kind of IS_A */
1344 g_return_if_fail (dependent_type (dep) == DEPENDENT_MANAGED);
1345 #endif
1346
1347 if (dep->sheet == sheet)
1348 return;
1349
1350 texpr = dep->texpr;
1351 if (texpr) gnm_expr_top_ref (texpr);
1352 dependent_set_expr (dep, NULL);
1353 /* We're now unlinked from everything. */
1354 dep->sheet = sheet;
1355 dependent_managed_set_expr (dep, texpr);
1356 if (texpr) gnm_expr_top_unref (texpr);
1357 }
1358
1359 static void
1360 managed_dep_debug_name (GnmDependent const *dep, GString *target)
1361 {
1362 g_string_append_printf (target, "Managed%p", (void *)dep);
1363 }
1364
1365 /*****************************************************************************/
1366
1367 static gboolean
1368 debug_style_deps (void)
1369 {
1370 static int debug = -1;
1371 if (debug < 0)
1372 debug = gnm_debug_flag ("style-deps");
1373 return debug;
1374 }
1375
1376 static void
1377 style_dep_unrender (GnmDependent *dep, const char *what)
1378 {
1379 GnmCellPos const *pos = dependent_pos (dep);
1380 GnmCell *cell;
1381 Sheet *sheet = dep->sheet;
1382
1383 if (debug_style_deps ())
1384 g_printerr ("StyleDep %p at %s %s\n",
1385 dep, cellpos_as_string (pos), what);
1386
1387 /*
1388 * If the cell exists, unrender it so format changes can take
1389 * effect.
1390 */
1391 cell = sheet_cell_get (sheet, pos->col, pos->row);
1392 if (cell)
1393 gnm_cell_unrender (cell);
1394
1395 sheet_redraw_region (sheet,
1396 pos->col, pos->row,
1397 pos->col, pos->row);
1398 }
1399
1400 static void
1401 style_dep_eval (GnmDependent *dep)
1402 {
1403 /*
1404 * It is possible that the cell has been rendered between ::changed
1405 * was called and now.
1406 */
1407 style_dep_unrender (dep, "being evaluated");
1408 }
1409
1410 static GSList *
1411 style_dep_changed (GnmDependent *dep)
1412 {
1413 style_dep_unrender (dep, "changed");
1414 return NULL;
1415 }
1416
1417 static GnmCellPos *
1418 style_dep_pos (GnmDependent const *dep)
1419 {
1420 return &((GnmStyleDependent*)dep)->pos;
1421 }
1422
1423 static void
1424 style_dep_debug_name (GnmDependent const *dep, GString *target)
1425 {
1426 g_string_append_printf (target, "StyleDep@%s[%p]",
1427 cellpos_as_string (style_dep_pos (dep)),
1428 dep);
1429 }
1430
1431 /*****************************************************************************/
1432
1433 static void
1434 name_dep_debug_name (GnmDependent const *dep, GString *target)
1435 {
1436 g_string_append_printf (target, "Name%p", (void *)dep);
1437 }
1438
1439 /*****************************************************************************/
1440
1441 static GSList *
1442 dynamic_dep_changed (GnmDependent *dep)
1443 {
1444 DynamicDep const *dyn = (DynamicDep *)dep;
1445
1446 /* When a dynamic dependent changes, we mark its container. */
1447
1448 if (dependent_needs_recalc (dyn->container))
1449 return NULL;
1450
1451 dependent_flag_recalc (dyn->container);
1452 return g_slist_prepend (NULL, dyn->container);
1453 }
1454
1455 static void
1456 dynamic_dep_debug_name (GnmDependent const *dep, GString *target)
1457 {
1458 g_string_append_printf (target, "DynamicDep%p", (void *)dep);
1459 }
1460
1461 void
1462 dependent_add_dynamic_dep (GnmDependent *dep, GnmRangeRef const *rr)
1463 {
1464 GnmDependentFlags flags;
1465 DynamicDep *dyn;
1466 GnmCellPos const *pos;
1467 DependencyRange range;
1468
1469 g_return_if_fail (dep != NULL);
1470
1471 pos = dependent_pos (dep);
1472
1473 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS)
1474 dyn = g_hash_table_lookup (dep->sheet->deps->dynamic_deps, dep);
1475 else {
1476 dep->flags |= DEPENDENT_HAS_DYNAMIC_DEPS;
1477 dyn = g_new (DynamicDep, 1);
1478 dyn->base.flags = DEPENDENT_DYNAMIC_DEP;
1479 dyn->base.sheet = dep->sheet;
1480 dyn->base.texpr = NULL;
1481 dyn->container = dep;
1482 dyn->ranges = NULL;
1483 dyn->singles = NULL;
1484 g_hash_table_insert (dep->sheet->deps->dynamic_deps, dep, dyn);
1485 }
1486
1487 gnm_cellpos_init_cellref (&range.range.start, &rr->a, pos, dep->sheet);
1488 gnm_cellpos_init_cellref (&range.range.end, &rr->b, pos, dep->sheet);
1489 if (range_is_singleton (&range.range)) {
1490 flags = link_single_dep (&dyn->base, pos, &rr->a);
1491 dyn->singles = g_slist_prepend (dyn->singles, gnm_rangeref_dup (rr));
1492 } else {
1493 flags = link_unlink_cellrange_dep (&dyn->base, pos, &rr->a, &rr->b, TRUE);
1494 dyn->ranges = g_slist_prepend (dyn->ranges, gnm_rangeref_dup (rr));
1495 }
1496 if (flags & DEPENDENT_HAS_3D)
1497 workbook_link_3d_dep (dep);
1498 }
1499
1500 static void
1501 dependent_clear_dynamic_deps (GnmDependent *dep)
1502 {
1503 g_hash_table_remove (dep->sheet->deps->dynamic_deps, dep);
1504 }
1505
1506 /*****************************************************************************/
1507
1508 /**
1509 * dependent_link:
1510 * @dep: the dependent that changed
1511 *
1512 * Adds the dependent to the workbook wide list of dependents.
1513 */
1514 void
1515 dependent_link (GnmDependent *dep)
1516 {
1517 Sheet *sheet;
1518 GnmEvalPos ep;
1519
1520 g_return_if_fail (dep != NULL);
1521 g_return_if_fail (dep->texpr != NULL);
1522 g_return_if_fail (!(dep->flags & DEPENDENT_IS_LINKED));
1523 g_return_if_fail (IS_SHEET (dep->sheet));
1524 g_return_if_fail (dep->sheet->deps != NULL);
1525
1526 sheet = dep->sheet;
1527
1528 /* Make this the new tail of the dependent list. */
1529 dep->prev_dep = sheet->deps->tail;
1530 dep->next_dep = NULL;
1531 if (dep->prev_dep)
1532 dep->prev_dep->next_dep = dep;
1533 else
1534 sheet->deps->head = dep; /* first element */
1535 sheet->deps->tail = dep;
1536 dep->flags |= DEPENDENT_IS_LINKED |
1537 link_unlink_expr_dep (eval_pos_init_dep (&ep, dep),
1538 dep->texpr->expr, TRUE);
1539
1540 if (dep->flags & DEPENDENT_HAS_3D)
1541 workbook_link_3d_dep (dep);
1542 }
1543
1544 /**
1545 * dependent_unlink:
1546 * @dep: the dependent that changed
1547 *
1548 * Removes the dependent from its container's set of dependents and always
1549 * removes the linkages to what it depends on.
1550 */
1551 void
1552 dependent_unlink (GnmDependent *dep)
1553 {
1554 GnmDepContainer *contain;
1555 GnmEvalPos ep;
1556
1557 g_return_if_fail (dep != NULL);
1558 g_return_if_fail (dependent_is_linked (dep));
1559 g_return_if_fail (dep->texpr != NULL);
1560 g_return_if_fail (IS_SHEET (dep->sheet));
1561
1562 link_unlink_expr_dep (eval_pos_init_dep (&ep, dep),
1563 dep->texpr->expr, FALSE);
1564 contain = dep->sheet->deps;
1565 if (contain != NULL) {
1566 if (contain->head == dep)
1567 contain->head = dep->next_dep;
1568 if (contain->tail == dep)
1569 contain->tail = dep->prev_dep;
1570 if (dep->next_dep)
1571 dep->next_dep->prev_dep = dep->prev_dep;
1572 if (dep->prev_dep)
1573 dep->prev_dep->next_dep = dep->next_dep;
1574
1575 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS)
1576 dependent_clear_dynamic_deps (dep);
1577 }
1578
1579 if (dep->flags & DEPENDENT_HAS_3D)
1580 workbook_unlink_3d_dep (dep);
1581 dep->flags &= ~DEPENDENT_LINK_FLAGS;
1582 }
1583
1584 /**
1585 * gnm_cell_eval_content:
1586 * @cell: the cell to evaluate.
1587 *
1588 * This function evaluates the contents of the cell,
1589 * it should not be used by anyone. It is an internal
1590 * function.
1591 **/
1592 static gboolean
1593 gnm_cell_eval_content (GnmCell *cell)
1594 {
1595 static GnmCell *iterating = NULL;
1596 GnmValue *v;
1597 GnmEvalPos pos;
1598 int max_iteration;
1599
1600 if (!gnm_cell_has_expr (cell) || /* plain cells without expr */
1601 !dependent_is_linked (&cell->base)) /* special case within TABLE */
1602 return TRUE;
1603
1604 #ifdef DEBUG_EVALUATION
1605 {
1606 GnmParsePos pp;
1607 char *str = gnm_expr_top_as_string
1608 (cell->base.texpr,
1609 parse_pos_init_cell (&pp, cell),
1610 NULL);
1611 g_printerr ("{\nEvaluating %s!%s: %s;\n",
1612 cell->base.sheet->name_quoted, cell_name (cell),
1613 str);
1614 g_free (str);
1615 }
1616 #endif
1617
1618 /* This is the bottom of a cycle */
1619 if (cell->base.flags & DEPENDENT_BEING_CALCULATED) {
1620 if (!cell->base.sheet->workbook->iteration.enabled)
1621 return TRUE;
1622
1623 /* but not the first bottom */
1624 if (cell->base.flags & DEPENDENT_BEING_ITERATED) {
1625 #ifdef DEBUG_EVALUATION
1626 g_printerr ("}; /* already-iterate (%d) */\n", iterating == NULL);
1627 #endif
1628 return iterating == NULL;
1629 }
1630
1631 /* if we are still marked as iterating then make this the last
1632 * time through.
1633 */
1634 if (iterating == cell) {
1635 #ifdef DEBUG_EVALUATION
1636 puts ("}; /* NO-iterate (1) */");
1637 #endif
1638 return TRUE;
1639 } else if (iterating == NULL) {
1640 cell->base.flags |= DEPENDENT_BEING_ITERATED;
1641 iterating = cell;
1642 #ifdef DEBUG_EVALUATION
1643 puts ("}; /* START iterate = TRUE (0) */");
1644 #endif
1645 return FALSE;
1646 } else {
1647 #ifdef DEBUG_EVALUATION
1648 puts ("}; /* other-iterate (0) */");
1649 #endif
1650 return FALSE;
1651 }
1652 }
1653
1654 /* Prepare to calculate */
1655 eval_pos_init_cell (&pos, cell);
1656 cell->base.flags |= DEPENDENT_BEING_CALCULATED;
1657
1658 /*
1659 * I'm somewhat afraid of thinking about the semantics of iteration
1660 * if different workbooks have different settings.
1661 */
1662 max_iteration = cell->base.sheet->workbook->iteration.max_number;
1663
1664 iterate:
1665 v = gnm_expr_top_eval (cell->base.texpr, &pos,
1666 GNM_EXPR_EVAL_SCALAR_NON_EMPTY);
1667 if (v == NULL)
1668 v = value_new_error (&pos, "Internal error");
1669
1670 #ifdef DEBUG_EVALUATION
1671 {
1672 char *valtxt = v
1673 ? value_get_as_string (v)
1674 : g_strdup ("NULL");
1675 g_printerr ("Evaluation(%d) %s := %s\n",
1676 max_iteration, cell_name (cell), valtxt);
1677 g_free (valtxt);
1678 }
1679 #endif
1680
1681 /* The top of a cycle */
1682 if (cell->base.flags & DEPENDENT_BEING_ITERATED) {
1683 cell->base.flags &= ~DEPENDENT_BEING_ITERATED;
1684
1685 /* We just completed the last iteration, don't change things */
1686 if (iterating && max_iteration-- > 0) {
1687 /* If we are within bounds make this the last round */
1688 if (value_diff (cell->value, v) < cell->base.sheet->workbook->iteration.tolerance)
1689 max_iteration = 0;
1690 else {
1691 #ifdef DEBUG_EVALUATION
1692 puts ("/* iterate == NULL */");
1693 #endif
1694 iterating = NULL;
1695 }
1696 value_release (cell->value);
1697 cell->value = v;
1698
1699 gnm_cell_unrender (cell);
1700 #ifdef DEBUG_EVALUATION
1701 puts ("/* LOOP */");
1702 #endif
1703 goto iterate;
1704 }
1705 g_return_val_if_fail (iterating, TRUE);
1706 iterating = NULL;
1707 } else {
1708 gboolean had_value = (cell->value != NULL);
1709 if (had_value && value_equal (v, cell->value)) {
1710 /* Value didn't change. */
1711 value_release (v);
1712 } else {
1713 gboolean was_string = had_value && (VALUE_IS_STRING (cell->value) || VALUE_IS_ERROR (cell->value));
1714 gboolean is_string = VALUE_IS_STRING (v) || VALUE_IS_ERROR (v);
1715
1716 if ((was_string || is_string))
1717 sheet_cell_queue_respan (cell);
1718
1719 if (had_value)
1720 value_release (cell->value);
1721 cell->value = v;
1722
1723 gnm_cell_unrender (cell);
1724 }
1725 }
1726
1727 if (iterating == cell)
1728 iterating = NULL;
1729
1730 #ifdef DEBUG_EVALUATION
1731 g_printerr ("} (%d)\n", iterating == NULL);
1732 #endif
1733 cell->base.flags &= ~DEPENDENT_BEING_CALCULATED;
1734 return iterating == NULL;
1735 }
1736
1737 /**
1738 * dependent_eval:
1739 * @dep:
1740 */
1741 static void
1742 dependent_eval (GnmDependent *dep)
1743 {
1744 int const t = dependent_type (dep);
1745 GnmDependentClass *klass = g_ptr_array_index (dep_classes, t);
1746
1747 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS) {
1748 dependent_clear_dynamic_deps (dep);
1749 dep->flags &= ~DEPENDENT_HAS_DYNAMIC_DEPS;
1750 }
1751
1752 /*
1753 * Problem: this really should be a tail call.
1754 */
1755 klass->eval (dep);
1756
1757 /* Don't clear flag until after in case we iterate */
1758 dep->flags &= ~DEPENDENT_NEEDS_RECALC;
1759 }
1760
1761 void
1762 gnm_cell_eval (GnmCell *cell)
1763 {
1764 if (gnm_cell_needs_recalc (cell)) {
1765 /*
1766 * This should be a tail call so the stack frame can be
1767 * eliminated before the call.
1768 */
1769 dependent_eval (GNM_CELL_TO_DEP (cell));
1770 }
1771 }
1772
1773
1774 /**
1775 * cell_queue_recalc:
1776 * @cell:
1777 *
1778 * Queue the cell and everything that depends on it for recalculation.
1779 * If a dependency is already queued ignore it.
1780 */
1781 void
1782 cell_queue_recalc (GnmCell *cell)
1783 {
1784 g_return_if_fail (cell != NULL);
1785
1786 if (!gnm_cell_needs_recalc (cell)) {
1787 GSList *deps;
1788
1789 if (gnm_cell_has_expr (cell))
1790 dependent_flag_recalc (GNM_CELL_TO_DEP (cell));
1791
1792 deps = cell_list_deps (cell);
1793 dependent_queue_recalc_list (deps);
1794 g_slist_free (deps);
1795 }
1796 }
1797
1798 typedef struct {
1799 int col, row;
1800 GnmDepFunc func;
1801 gpointer user;
1802 } search_rangedeps_closure_t;
1803
1804 static void
1805 cb_search_rangedeps (gpointer key, G_GNUC_UNUSED gpointer value,
1806 gpointer closure)
1807 {
1808 search_rangedeps_closure_t const *c = closure;
1809 DependencyRange const *deprange = key;
1810 GnmRange const *range = &(deprange->range);
1811
1812 #if 0
1813 /* When things get slow this is a good test to enable */
1814 static int counter = 0;
1815 if ((++counter % 100000) == 0)
1816 g_printerr ("%d\n", counter / 100000);
1817 #endif
1818
1819 if (range_contains (range, c->col, c->row)) {
1820 GnmDepFunc func = c->func;
1821 micro_hash_foreach_dep (deprange->deps, dep,
1822 (func) (dep, c->user););
1823 }
1824 }
1825
1826 static void
1827 cell_foreach_range_dep (GnmCell const *cell, GnmDepFunc func, gpointer user)
1828 {
1829 search_rangedeps_closure_t closure;
1830 GHashTable *bucket =
1831 cell->base.sheet->deps->range_hash[BUCKET_OF_ROW (cell->pos.row)];
1832
1833 if (bucket != NULL) {
1834 closure.col = cell->pos.col;
1835 closure.row = cell->pos.row;
1836 closure.func = func;
1837 closure.user = user;
1838 g_hash_table_foreach (bucket, &cb_search_rangedeps, &closure);
1839 }
1840 }
1841
1842 static void
1843 cell_foreach_single_dep (Sheet const *sheet, int col, int row,
1844 GnmDepFunc func, gpointer user)
1845 {
1846 DependencySingle lookup, *single;
1847 GnmDepContainer *deps = sheet->deps;
1848
1849 lookup.pos.col = col;
1850 lookup.pos.row = row;
1851
1852 single = g_hash_table_lookup (deps->single_hash, &lookup);
1853 if (single != NULL)
1854 micro_hash_foreach_dep (single->deps, dep,
1855 (*func) (dep, user););
1856 }
1857
1858 /**
1859 * cell_foreach_dep:
1860 * @cell: #GnmCell
1861 * @func: (scope call):
1862 * @user: user data.
1863 *
1864 **/
1865 void
1866 cell_foreach_dep (GnmCell const *cell, GnmDepFunc func, gpointer user)
1867 {
1868 g_return_if_fail (cell != NULL);
1869
1870 /* accelerate exit */
1871 if (!cell->base.sheet->deps)
1872 return;
1873
1874 cell_foreach_range_dep (cell, func, user);
1875 cell_foreach_single_dep (cell->base.sheet, cell->pos.col, cell->pos.row,
1876 func, user);
1877 }
1878
1879 static void
1880 cb_recalc_all_depends (gpointer key, G_GNUC_UNUSED gpointer value,
1881 G_GNUC_UNUSED gpointer ignore)
1882 {
1883 DependencyAny const *depany = key;
1884 GSList *work = NULL;
1885 micro_hash_foreach_dep (depany->deps, dep, {
1886 if (!dependent_needs_recalc (dep)) {
1887 dependent_flag_recalc (dep);
1888 work = g_slist_prepend (work, dep);
1889 }
1890 });
1891 dependent_queue_recalc_main (work);
1892 }
1893
1894
1895
1896 static void
1897 cb_range_contained_depend (gpointer key, G_GNUC_UNUSED gpointer value,
1898 gpointer user)
1899 {
1900 DependencyRange const *deprange = key;
1901 GnmRange const *range = &deprange->range;
1902 GnmRange const *target = user;
1903
1904 if (range_overlap (target, range)) {
1905 GSList *work = NULL;
1906 micro_hash_foreach_dep (deprange->deps, dep, {
1907 if (!dependent_needs_recalc (dep)) {
1908 dependent_flag_recalc (dep);
1909 work = g_slist_prepend (work, dep);
1910 }
1911 });
1912 dependent_queue_recalc_main (work);
1913 }
1914 }
1915
1916 static void
1917 cb_single_contained_depend (gpointer key,
1918 G_GNUC_UNUSED gpointer value,
1919 gpointer user)
1920 {
1921 DependencySingle const *depsingle = key;
1922 GnmRange const *target = user;
1923
1924 if (range_contains (target, depsingle->pos.col, depsingle->pos.row)) {
1925 GSList *work = NULL;
1926 micro_hash_foreach_dep (depsingle->deps, dep, {
1927 if (!dependent_needs_recalc (dep)) {
1928 dependent_flag_recalc (dep);
1929 work = g_slist_prepend (work, dep);
1930 }
1931 });
1932 dependent_queue_recalc_main (work);
1933 }
1934 }
1935
1936 /**
1937 * sheet_region_queue_recalc:
1938 * @sheet: The sheet.
1939 * @range: Optionally NULL range.
1940 *
1941 * Queues things that depend on @sheet!@range for recalc.
1942 *
1943 * If @range is NULL the entire sheet is used.
1944 */
1945 void
1946 sheet_region_queue_recalc (Sheet const *sheet, GnmRange const *r)
1947 {
1948 int i;
1949
1950 g_return_if_fail (IS_SHEET (sheet));
1951 g_return_if_fail (sheet->deps != NULL);
1952
1953 if (r == NULL) {
1954 /* mark the contained depends dirty non recursively */
1955 SHEET_FOREACH_DEPENDENT (sheet, dep,
1956 dependent_flag_recalc (dep););
1957
1958 /* look for things that depend on the sheet */
1959 for (i = sheet->deps->buckets - 1; i >= 0 ; i--) {
1960 GHashTable *hash = sheet->deps->range_hash[i];
1961 if (hash != NULL)
1962 g_hash_table_foreach (hash,
1963 &cb_recalc_all_depends, NULL);
1964 }
1965 g_hash_table_foreach (sheet->deps->single_hash,
1966 &cb_recalc_all_depends, NULL);
1967 } else {
1968 int const first = BUCKET_OF_ROW (r->start.row);
1969
1970 /* mark the contained depends dirty non recursively */
1971 SHEET_FOREACH_DEPENDENT (sheet, dep, {
1972 GnmCell *cell = GNM_DEP_TO_CELL (dep);
1973 if (dependent_is_cell (dep) &&
1974 range_contains (r, cell->pos.col, cell->pos.row))
1975 dependent_flag_recalc (dep);
1976 });
1977
1978 /* look for things that depend on target region */
1979 for (i = BUCKET_OF_ROW (r->end.row); i >= first ; i--) {
1980 GHashTable *hash = sheet->deps->range_hash[i];
1981 if (hash != NULL)
1982 g_hash_table_foreach (hash,
1983 &cb_range_contained_depend, (gpointer)r);
1984 }
1985 g_hash_table_foreach (sheet->deps->single_hash,
1986 &cb_single_contained_depend, (gpointer)r);
1987 }
1988 }
1989
1990 typedef struct
1991 {
1992 int dep_type;
1993 union {
1994 GnmParsePos pos;
1995 GnmDependent *dep;
1996 } u;
1997 GnmExprTop const *oldtree;
1998 } ExprRelocateStorage;
1999
2000 /**
2001 * dependents_unrelocate_free:
2002 * @info:
2003 *
2004 * Free the undo info associated with a dependent relocation.
2005 */
2006 static void
2007 dependents_unrelocate_free (GSList *info)
2008 {
2009 GSList *ptr = info;
2010 for (; ptr != NULL ; ptr = ptr->next) {
2011 ExprRelocateStorage *tmp = ptr->data;
2012 gnm_expr_top_unref (tmp->oldtree);
2013 g_free (tmp);
2014 }
2015 g_slist_free (info);
2016 }
2017
2018 /**
2019 * dependents_unrelocate:
2020 * @info:
2021 *
2022 * Apply the undo info associated with a dependent relocation.
2023 */
2024 static void
2025 dependents_unrelocate (GSList *info)
2026 {
2027 GSList *ptr = info;
2028 for (; ptr != NULL ; ptr = ptr->next) {
2029 ExprRelocateStorage *tmp = ptr->data;
2030
2031 if (tmp->dep_type == DEPENDENT_CELL) {
2032 if (!IS_SHEET (tmp->u.pos.sheet)) {
2033 /* FIXME : happens when undoing a move from a deleted
2034 * sheet. Do we want to do something here */
2035 } else {
2036 GnmCell *cell = sheet_cell_get
2037 (tmp->u.pos.sheet,
2038 tmp->u.pos.eval.col, tmp->u.pos.eval.row);
2039
2040 /* It is possible to have a NULL if the relocation info
2041 * is not really relevant. eg when undoing a pasted
2042 * cut that was relocated but also saved to a buffer */
2043 if (cell != NULL) {
2044 if (gnm_expr_top_is_array_corner (tmp->oldtree)) {
2045 int cols, rows;
2046
2047 gnm_expr_top_get_array_size (tmp->oldtree, &cols, &rows);
2048 gnm_cell_set_array_formula (tmp->u.pos.sheet,
2049 tmp->u.pos.eval.col,
2050 tmp->u.pos.eval.row,
2051 tmp->u.pos.eval.col + cols - 1,
2052 tmp->u.pos.eval.row + rows - 1,
2053 gnm_expr_top_new (gnm_expr_copy (gnm_expr_top_get_array_expr (tmp->oldtree))));
2054 cell_queue_recalc (cell);
2055 sheet_flag_status_update_cell (cell);
2056 } else
2057 sheet_cell_set_expr (cell, tmp->oldtree);
2058 }
2059 }
2060 } else if (tmp->dep_type == DEPENDENT_NAME) {
2061 } else {
2062 dependent_set_expr (tmp->u.dep, tmp->oldtree);
2063 dependent_flag_recalc (tmp->u.dep);
2064 dependent_link (tmp->u.dep);
2065 }
2066 }
2067 }
2068
2069 /**
2070 * dependents_link:
2071 * @deps: (element-type GnmDependent): An slist of dependents.
2072 *
2073 * link a list of dependents. (The list used to get freed, but is not
2074 * freed anymore.)
2075 */
2076 void
2077 dependents_link (GSList *deps)
2078 {
2079 GSList *ptr = deps;
2080
2081 /* put them back */
2082 for (; ptr != NULL ; ptr = ptr->next) {
2083 GnmDependent *dep = ptr->data;
2084 if (dep->sheet->being_invalidated)
2085 continue;
2086 if (dep->sheet->deps != NULL && !dependent_is_linked (dep)) {
2087 dependent_link (dep);
2088 dependent_queue_recalc (dep);
2089 }
2090 }
2091 }
2092
2093 typedef struct {
2094 GnmRange const *target;
2095 GSList *list;
2096 } CollectClosure;
2097
2098 static void
2099 cb_range_contained_collect (DependencyRange const *deprange,
2100 G_GNUC_UNUSED gpointer ignored,
2101 CollectClosure *user)
2102 {
2103 GnmRange const *range = &deprange->range;
2104
2105 if (range_overlap (user->target, range))
2106 micro_hash_foreach_dep (deprange->deps, dep, {
2107 if (!(dep->flags & (DEPENDENT_FLAGGED | DEPENDENT_CAN_RELOCATE)) &&
2108 dependent_type (dep) != DEPENDENT_DYNAMIC_DEP) {
2109 dep->flags |= DEPENDENT_FLAGGED;
2110 user->list = g_slist_prepend (user->list, dep);
2111 }});
2112 }
2113
2114 static void
2115 cb_single_contained_collect (DependencySingle const *depsingle,
2116 G_GNUC_UNUSED gpointer ignored,
2117 CollectClosure *user)
2118 {
2119 if (range_contains (user->target, depsingle->pos.col, depsingle->pos.row))
2120 micro_hash_foreach_dep (depsingle->deps, dep, {
2121 if (!(dep->flags & (DEPENDENT_FLAGGED | DEPENDENT_CAN_RELOCATE)) &&
2122 dependent_type (dep) != DEPENDENT_DYNAMIC_DEP) {
2123 dep->flags |= DEPENDENT_FLAGGED;
2124 user->list = g_slist_prepend (user->list, dep);
2125 }});
2126 }
2127
2128 static void
2129 cb_collect_names (GnmNamedExpr *nexpr,
2130 G_GNUC_UNUSED gpointer value,
2131 GSList **l)
2132 {
2133 *l = g_slist_prepend (*l, nexpr);
2134 }
2135
2136 struct cb_remote_names {
2137 GSList *names;
2138 Workbook *wb;
2139 };
2140
2141 static void
2142 cb_remote_names1 (G_GNUC_UNUSED gconstpointer key,
2143 GnmNamedExpr *nexpr,
2144 struct cb_remote_names *data)
2145 {
2146 data->names = g_slist_prepend (data->names, nexpr);
2147 }
2148
2149 static void
2150 cb_remote_names2 (GnmNamedExpr *nexpr,
2151 G_GNUC_UNUSED gpointer value,
2152 struct cb_remote_names *data)
2153 {
2154 Workbook *wb =
2155 nexpr->pos.sheet ? nexpr->pos.sheet->workbook : nexpr->pos.wb;
2156 if (wb != data->wb)
2157 data->names = g_slist_prepend (data->names, nexpr);
2158 }
2159
2160 /*
2161 * Get a list of all names that (may) reference data in a given sheet.
2162 * This is approximated as all names in the sheet, all global names in
2163 * its workbook, and all external references that actually mention the
2164 * sheet explicitly.
2165 */
2166 static GSList *
2167 names_referencing_sheet (Sheet *sheet)
2168 {
2169 struct cb_remote_names data;
2170
2171 data.names = NULL;
2172 data.wb = sheet->workbook;
2173
2174 workbook_foreach_name (sheet->workbook, TRUE,
2175 (GHFunc)cb_remote_names1,
2176 &data);
2177 gnm_sheet_foreach_name (sheet, (GHFunc)cb_remote_names1, &data);
2178
2179 if (sheet->deps->referencing_names)
2180 g_hash_table_foreach (sheet->deps->referencing_names,
2181 (GHFunc)cb_remote_names2,
2182 &data);
2183
2184 return data.names;
2185 }
2186
2187
2188 /**
2189 * dependents_relocate:
2190 * @info: the descriptor record for what is being moved where.
2191 *
2192 * Fixes references to or from a region that is going to be moved.
2193 * Returns: (transfer full): a list of the locations and expressions that were changed outside of
2194 * the region.
2195 **/
2196 GOUndo *
2197 dependents_relocate (GnmExprRelocateInfo const *rinfo)
2198 {
2199 GnmExprRelocateInfo local_rinfo;
2200 GSList *l, *dependents = NULL, *undo_info = NULL;
2201 Sheet *sheet;
2202 GnmRange const *r;
2203 int i;
2204 CollectClosure collect;
2205 GOUndo *u_exprs, *u_names;
2206
2207 g_return_val_if_fail (rinfo != NULL, NULL);
2208
2209 /* short circuit if nothing would move */
2210 if (rinfo->col_offset == 0 && rinfo->row_offset == 0 &&
2211 rinfo->origin_sheet == rinfo->target_sheet)
2212 return NULL;
2213
2214 sheet = rinfo->origin_sheet;
2215 r = &rinfo->origin;
2216
2217 /* collect contained cells with expressions */
2218 SHEET_FOREACH_DEPENDENT (rinfo->origin_sheet, dep, {
2219 GnmCell *cell = GNM_DEP_TO_CELL (dep);
2220 if (dependent_is_cell (dep) &&
2221 range_contains (r, cell->pos.col, cell->pos.row)) {
2222 dependents = g_slist_prepend (dependents, dep);
2223 dep->flags |= DEPENDENT_FLAGGED;
2224 }
2225 });
2226
2227 /* collect the things that depend on source region */
2228 collect.target = r;
2229 collect.list = dependents;
2230 g_hash_table_foreach (sheet->deps->single_hash,
2231 (GHFunc) &cb_single_contained_collect,
2232 (gpointer)&collect);
2233 {
2234 int const first = BUCKET_OF_ROW (r->start.row);
2235 GHashTable *hash;
2236 for (i = BUCKET_OF_ROW (r->end.row); i >= first ; i--) {
2237 hash = sheet->deps->range_hash[i];
2238 if (hash != NULL)
2239 g_hash_table_foreach (hash,
2240 (GHFunc) &cb_range_contained_collect,
2241 (gpointer)&collect);
2242 }
2243 }
2244 dependents = collect.list;
2245 local_rinfo = *rinfo;
2246 for (l = dependents; l; l = l->next) {
2247 GnmExprTop const *newtree;
2248 GnmDependent *dep = l->data;
2249
2250 dep->flags &= ~DEPENDENT_FLAGGED;
2251 sheet_flag_status_update_range (dep->sheet, NULL);
2252
2253 parse_pos_init_dep (&local_rinfo.pos, dep);
2254
2255 /* it is possible nothing changed for contained deps
2256 * using absolute references */
2257 newtree = gnm_expr_top_relocate (dep->texpr, &local_rinfo, FALSE);
2258 if (newtree != NULL) {
2259 int const t = dependent_type (dep);
2260 ExprRelocateStorage *tmp =
2261 g_new (ExprRelocateStorage, 1);
2262
2263 tmp->dep_type = t;
2264 if (t == DEPENDENT_NAME) {
2265 #warning "What should we do here and why do we leak tmp?"
2266 } else {
2267 if (t == DEPENDENT_CELL)
2268 tmp->u.pos = local_rinfo.pos;
2269 else
2270 tmp->u.dep = dep;
2271 tmp->oldtree = dep->texpr;
2272 gnm_expr_top_ref (tmp->oldtree);
2273 undo_info = g_slist_prepend (undo_info, tmp);
2274
2275 dependent_set_expr (dep, newtree); /* unlinks */
2276 gnm_expr_top_unref (newtree);
2277
2278 /* queue the things that depend on the changed dep
2279 * even if it is going to move.
2280 */
2281 dependent_queue_recalc (dep);
2282
2283 /* relink if it is not going to move, if it is moving
2284 * then the caller is responsible for relinking.
2285 * This avoids a link/unlink/link tuple
2286 */
2287 if (t == DEPENDENT_CELL) {
2288 GnmCellPos const *pos = &GNM_DEP_TO_CELL (dep)->pos;
2289 if (dep->sheet != sheet ||
2290 !range_contains (r, pos->col, pos->row))
2291 dependent_link (dep);
2292 } else
2293 dependent_link (dep);
2294 }
2295 } else {
2296 /*
2297 * The expression may not be changing, but it depends
2298 * on something that is. Not-corner array cells go here
2299 * too
2300 */
2301 dependent_queue_recalc (dep);
2302 }
2303
2304 /* Not the most efficient, but probably not too bad. It is
2305 * definitely cheaper than finding the set of effected sheets. */
2306 sheet_flag_status_update_range (dep->sheet, NULL);
2307 }
2308 g_slist_free (dependents);
2309
2310 u_exprs = go_undo_unary_new (undo_info,
2311 (GOUndoUnaryFunc)dependents_unrelocate,
2312 (GFreeFunc)dependents_unrelocate_free);
2313
2314 u_names = NULL;
2315
2316 switch (rinfo->reloc_type) {
2317 case GNM_EXPR_RELOCATE_INVALIDATE_SHEET:
2318 case GNM_EXPR_RELOCATE_MOVE_RANGE:
2319 break;
2320
2321 case GNM_EXPR_RELOCATE_COLS:
2322 case GNM_EXPR_RELOCATE_ROWS: {
2323 GSList *l, *names = names_referencing_sheet (sheet);
2324 GnmExprRelocateInfo rinfo2 = *rinfo;
2325
2326 for (l = names; l; l = l->next) {
2327 GnmNamedExpr *nexpr = l->data;
2328 GnmExprTop const *newtree;
2329 rinfo2.pos = nexpr->pos;
2330 newtree = gnm_expr_top_relocate (nexpr->texpr,
2331 &rinfo2, TRUE);
2332 if (newtree) {
2333 GOUndo *u = expr_name_set_expr_undo_new (nexpr);
2334 u_names = go_undo_combine (u_names, u);
2335 expr_name_set_expr (nexpr, newtree);
2336 }
2337 }
2338 g_slist_free (names);
2339 break;
2340
2341 default:
2342 g_assert_not_reached ();
2343 }
2344 }
2345
2346 return go_undo_combine (u_exprs, u_names);
2347 }
2348
2349 /*******************************************************************/
2350
2351 static gboolean
2352 cb_collect_range (G_GNUC_UNUSED gpointer key,
2353 DependencyAny *depany,
2354 GSList **collector)
2355 {
2356 *collector = g_slist_prepend (*collector, depany);
2357 return TRUE;
2358 }
2359
2360 static void
2361 dep_hash_destroy (GHashTable *hash, GSList **dyn_deps, Sheet *sheet)
2362 {
2363 GSList *deps = NULL, *l;
2364 GnmExprRelocateInfo rinfo;
2365 GSList *deplist = NULL;
2366 gboolean destroy = (sheet->revive == NULL);
2367
2368 /* We collect first because we will be changing the hash. */
2369 if (destroy) {
2370 g_hash_table_foreach_remove (hash,
2371 (GHRFunc)cb_collect_range,
2372 &deps);
2373 g_hash_table_destroy (hash);
2374 } else {
2375 g_hash_table_foreach (hash, (GHFunc)cb_collect_range, &deps);
2376 }
2377
2378 for (l = deps; l; l = l->next) {
2379 DependencyAny *depany = l->data;
2380
2381 micro_hash_foreach_dep (depany->deps, dep, {
2382 if (dependent_type (dep) == DEPENDENT_DYNAMIC_DEP) {
2383 GnmDependent *c = ((DynamicDep *)dep)->container;
2384 if (!c->sheet->being_invalidated)
2385 *dyn_deps =
2386 g_slist_prepend (*dyn_deps, c);
2387 } else if (!dep->sheet->being_invalidated) {
2388 /*
2389 * We collect here instead of doing right away as
2390 * the dependent_set_expr below can change the
2391 * container we are looping over.
2392 */
2393 deplist = g_slist_prepend (deplist, dep);
2394 }
2395 });
2396
2397 if (destroy)
2398 micro_hash_release (&depany->deps);
2399 }
2400 g_slist_free (deps);
2401
2402 /*
2403 * We do this after the above loop as this loop will
2404 * invalidate some of the DependencyAny pointers from
2405 * above. The testcase for that is 314207, deleting
2406 * all but the first sheet in one go.
2407 */
2408 rinfo.reloc_type = GNM_EXPR_RELOCATE_INVALIDATE_SHEET;
2409 for (l = deplist; l; l = l->next) {
2410 GnmDependent *dep = l->data;
2411 GnmExprTop const *te = dep->texpr;
2412 /* We are told this dependent depends on this region, hence if
2413 * newtree is null then either
2414 * 1) we did not depend on it (ie., serious breakage )
2415 * 2) we had a duplicate reference and we have already removed it.
2416 * 3) We depended on things via a name which will be
2417 * invalidated elsewhere */
2418 GnmExprTop const *newtree = gnm_expr_top_relocate (te, &rinfo, FALSE);
2419 if (newtree != NULL) {
2420 if (sheet->revive)
2421 go_undo_group_add
2422 (sheet->revive,
2423 gnm_dep_set_expr_undo_new (dep));
2424 dependent_set_expr (dep, newtree);
2425 gnm_expr_top_unref (newtree);
2426 dependent_link (dep);
2427 }
2428 }
2429 g_slist_free (deplist);
2430 }
2431
2432 static void
2433 cb_collect_deps_of_name (GnmDependent *dep, G_GNUC_UNUSED gpointer value,
2434 GSList **accum)
2435 {
2436 /* grab unflagged linked depends */
2437 if ((dep->flags & (DEPENDENT_FLAGGED|DEPENDENT_IS_LINKED)) == DEPENDENT_IS_LINKED) {
2438 dep->flags |= DEPENDENT_FLAGGED;
2439 *accum = g_slist_prepend (*accum, dep);
2440 }
2441 }
2442
2443 struct cb_collect_deps_of_names {
2444 GSList *names;
2445 GSList *deps;
2446 };
2447
2448 static void
2449 cb_collect_deps_of_names (GnmNamedExpr *nexpr,
2450 G_GNUC_UNUSED gpointer value,
2451 struct cb_collect_deps_of_names *accum)
2452 {
2453 accum->names = g_slist_prepend (accum->names, nexpr);
2454 if (nexpr->dependents)
2455 g_hash_table_foreach (nexpr->dependents,
2456 (GHFunc)cb_collect_deps_of_name,
2457 &accum->deps);
2458 }
2459
2460 static void
2461 invalidate_name (GnmNamedExpr *nexpr, Sheet *sheet)
2462 {
2463 GnmExprTop const *old_expr = nexpr->texpr;
2464 GnmExprTop const *new_expr = NULL;
2465 gboolean scope_being_killed =
2466 nexpr->pos.sheet
2467 ? nexpr->pos.sheet->being_invalidated
2468 : nexpr->pos.wb->during_destruction;
2469
2470 if (!scope_being_killed) {
2471 GnmExprRelocateInfo rinfo;
2472 rinfo.reloc_type = GNM_EXPR_RELOCATE_INVALIDATE_SHEET;
2473 new_expr = gnm_expr_top_relocate (old_expr, &rinfo, FALSE);
2474 g_return_if_fail (new_expr != NULL);
2475 }
2476
2477 if (nexpr->dependents && g_hash_table_size (nexpr->dependents))
2478 g_warning ("Left-over name dependencies\n");
2479
2480 if (sheet->revive)
2481 go_undo_group_add (sheet->revive,
2482 expr_name_set_expr_undo_new (nexpr));
2483
2484 expr_name_set_expr (nexpr, new_expr);
2485 }
2486
2487 static void
2488 handle_dynamic_deps (GSList *dyn_deps)
2489 {
2490 GSList *ptr;
2491
2492 for (ptr = dyn_deps; ptr != NULL ; ptr = ptr->next) {
2493 GnmDependent *dep = ptr->data;
2494 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS) {
2495 dependent_clear_dynamic_deps (dep);
2496 dep->flags &= ~DEPENDENT_HAS_DYNAMIC_DEPS;
2497 }
2498 }
2499 dependent_queue_recalc_list (dyn_deps);
2500 g_slist_free (dyn_deps);
2501 }
2502
2503 static void
2504 handle_referencing_names (GnmDepContainer *deps, Sheet *sheet)
2505 {
2506 GSList *ptr;
2507 GHashTable *names = deps->referencing_names;
2508 struct cb_collect_deps_of_names accum;
2509 gboolean destroy = (sheet->revive == NULL);
2510
2511 if (!names)
2512 return;
2513
2514 if (destroy)
2515 deps->referencing_names = NULL;
2516
2517 accum.deps = NULL;
2518 accum.names = NULL;
2519 g_hash_table_foreach (names,
2520 (GHFunc)cb_collect_deps_of_names,
2521 (gpointer)&accum);
2522
2523 for (ptr = accum.deps; ptr; ptr = ptr->next) {
2524 GnmDependent *dep = ptr->data;
2525 dep->flags &= ~DEPENDENT_FLAGGED;
2526 dependent_unlink (dep);
2527 }
2528
2529 /* now that all of the dependents of these names are unlinked.
2530 * change the references in the names to avoid this sheet */
2531 for (ptr = accum.names; ptr; ptr = ptr->next) {
2532 GnmNamedExpr *nexpr = ptr->data;
2533 invalidate_name (nexpr, sheet);
2534 }
2535 g_slist_free (accum.names);
2536
2537 /* then relink things en-mass in case one of the deps outside
2538 * this sheet used multiple names that referenced us */
2539 dependents_link (accum.deps);
2540
2541 if (destroy) {
2542 g_slist_free (accum.deps);
2543 g_hash_table_destroy (names);
2544 } else {
2545 go_undo_group_add (sheet->revive,
2546 gnm_dep_unlink_undo_new (accum.deps));
2547 }
2548 }
2549
2550 static void
2551 handle_outgoing_references (GnmDepContainer *deps, Sheet *sheet)
2552 {
2553 GnmDependentFlags what = DEPENDENT_USES_NAME;
2554 GSList *accum = NULL;
2555
2556 what |= (sheet->workbook && sheet->workbook->during_destruction)
2557 ? DEPENDENT_GOES_INTERBOOK
2558 : DEPENDENT_GOES_INTERSHEET;
2559 DEPENDENT_CONTAINER_FOREACH_DEPENDENT (deps, dep, {
2560 if (dependent_is_linked (dep) && (dep->flags & what)) {
2561 dependent_unlink (dep);
2562 if (sheet->revive)
2563 accum = g_slist_prepend (accum, dep);
2564 }
2565 });
2566
2567 if (accum)
2568 go_undo_group_add (sheet->revive,
2569 gnm_dep_unlink_undo_new (accum));
2570 }
2571
2572 /*
2573 * do_deps_destroy:
2574 * Invalidate references of all kinds to the sheet.
2575 *
2576 * Also destroy the dependency container.
2577 */
2578 static void
2579 do_deps_destroy (Sheet *sheet)
2580 {
2581 GnmDepContainer *deps;
2582 GSList *dyn_deps = NULL;
2583 int i;
2584
2585 g_return_if_fail (IS_SHEET (sheet));
2586 g_return_if_fail (sheet->being_invalidated);
2587
2588 /* The GnmDepContainer (i.e., sheet->deps) contains the names that
2589 * reference this, not the names it contains. Remove the locally
2590 * defined names here.
2591 *
2592 * NOTE : they may continue to exist inactively for a bit. Be
2593 * careful to remove them _before_ destroying the deps. This is
2594 * a bit wasteful in that we unlink and relink a few things that
2595 * are going to be deleted. However, it is necessary to catch
2596 * all the different life cycles.
2597 */
2598 gnm_named_expr_collection_free (sheet->names);
2599 sheet->names = NULL;
2600
2601 deps = sheet->deps;
2602 if (deps == NULL)
2603 return;
2604
2605 /* Destroy the records of what depends on this sheet. There is no need
2606 * to delicately remove individual items from the lists. The only
2607 * purpose that serves is to validate the state of our data structures.
2608 * If required this optimization can be disabled for debugging.
2609 */
2610 sheet->deps = NULL;
2611 if (sheet->revive) {
2612 g_object_unref (sheet->revive);
2613 sheet->revive = NULL;
2614 }
2615
2616 for (i = deps->buckets - 1; i >= 0 ; i--) {
2617 GHashTable *hash = deps->range_hash[i];
2618 if (hash != NULL)
2619 dep_hash_destroy (hash, &dyn_deps, sheet);
2620 }
2621 dep_hash_destroy (deps->single_hash, &dyn_deps, sheet);
2622
2623 g_free (deps->range_hash);
2624 deps->range_hash = NULL;
2625 /*
2626 * Note: we have not freed the elements in the pool. This call
2627 * frees everything in one go.
2628 */
2629 go_mem_chunk_destroy (deps->range_pool, TRUE);
2630 deps->range_pool = NULL;
2631
2632 deps->single_hash = NULL;
2633 /*
2634 * Note: we have not freed the elements in the pool. This call
2635 * frees everything in one go.
2636 */
2637 go_mem_chunk_destroy (deps->single_pool, TRUE);
2638 deps->single_pool = NULL;
2639
2640 /* Now that we have tossed all deps to this sheet we can queue the
2641 * external dyn deps for recalc and free them */
2642 handle_dynamic_deps (dyn_deps);
2643
2644 g_hash_table_destroy (deps->dynamic_deps);
2645 deps->dynamic_deps = NULL;
2646
2647 handle_referencing_names (deps, sheet);
2648
2649 /* Now we remove any links from dependents in this sheet to
2650 * to other containers. If the entire workbook is going away
2651 * just look for inter-book links.
2652 */
2653 handle_outgoing_references (deps, sheet);
2654
2655 g_free (deps);
2656 }
2657
2658 /*
2659 * do_deps_invalidate:
2660 * Invalidate references of all kinds to the sheet.
2661 */
2662 static void
2663 do_deps_invalidate (Sheet *sheet)
2664 {
2665 GnmDepContainer *deps;
2666 GSList *dyn_deps = NULL;
2667 int i;
2668
2669 g_return_if_fail (IS_SHEET (sheet));
2670 g_return_if_fail (sheet->being_invalidated);
2671 g_return_if_fail (sheet->revive == NULL);
2672
2673 sheet->revive = go_undo_group_new ();
2674
2675 gnm_named_expr_collection_unlink (sheet->names);
2676
2677 deps = sheet->deps;
2678
2679 for (i = deps->buckets - 1; i >= 0 ; i--) {
2680 GHashTable *hash = deps->range_hash[i];
2681 if (hash != NULL)
2682 dep_hash_destroy (hash, &dyn_deps, sheet);
2683 }
2684 dep_hash_destroy (deps->single_hash, &dyn_deps, sheet);
2685
2686 /* Now that we have tossed all deps to this sheet we can queue the
2687 * external dyn deps for recalc and free them */
2688 handle_dynamic_deps (dyn_deps);
2689
2690 handle_referencing_names (deps, sheet);
2691
2692 /* Now we remove any links from dependents in this sheet to
2693 * to other containers. If the entire workbook is going away
2694 * just look for inter-book links.
2695 */
2696 handle_outgoing_references (deps, sheet);
2697 }
2698
2699 static void
2700 cb_tweak_3d (GnmDependent *dep, G_GNUC_UNUSED gpointer value, GSList **deps)
2701 {
2702 *deps = g_slist_prepend (*deps, dep);
2703 }
2704
2705 static void
2706 tweak_3d (Sheet *sheet)
2707 {
2708 Workbook *wb = sheet->workbook;
2709 GSList *deps = NULL, *l;
2710 GnmExprRelocateInfo rinfo;
2711
2712 if (!wb->sheet_order_dependents)
2713 return;
2714
2715 g_hash_table_foreach (wb->sheet_order_dependents,
2716 (GHFunc)cb_tweak_3d,
2717 &deps);
2718
2719 rinfo.reloc_type = GNM_EXPR_RELOCATE_INVALIDATE_SHEET;
2720 for (l = deps; l; l = l->next) {
2721 GnmDependent *dep = l->data;
2722 GnmExprTop const *te = dep->texpr;
2723 GnmExprTop const *newtree = gnm_expr_top_relocate (te, &rinfo, FALSE);
2724
2725 if (newtree != NULL) {
2726 if (sheet->revive)
2727 go_undo_group_add
2728 (sheet->revive,
2729 gnm_dep_set_expr_undo_new (dep));
2730 dependent_set_expr (dep, newtree);
2731 gnm_expr_top_unref (newtree);
2732 dependent_link (dep);
2733 dependent_changed (dep);
2734 }
2735 }
2736 g_slist_free (deps);
2737 }
2738
2739 static void
2740 dependents_invalidate_sheets (GSList *sheets, gboolean destroy)
2741 {
2742 GSList *tmp;
2743 Workbook *last_wb;
2744
2745 /* Mark all first. */
2746 for (tmp = sheets; tmp; tmp = tmp->next) {
2747 Sheet *sheet = tmp->data;
2748 sheet->being_invalidated = TRUE;
2749 }
2750
2751 /*
2752 * Fixup 3d refs that start or end on one of these sheets.
2753 * Ideally we do this one per workbook, but that is not critical
2754 * so we are not going to outright sort the sheet list.
2755 */
2756 last_wb = NULL;
2757 for (tmp = sheets; tmp; tmp = tmp->next) {
2758 Sheet *sheet = tmp->data;
2759 Workbook *wb = sheet->workbook;
2760
2761 if (wb != last_wb)
2762 tweak_3d (sheet);
2763 last_wb = wb;
2764 }
2765
2766 /* Now invalidate. */
2767 for (tmp = sheets; tmp; tmp = tmp->next) {
2768 Sheet *sheet = tmp->data;
2769 if (destroy)
2770 do_deps_destroy (sheet);
2771 else
2772 do_deps_invalidate (sheet);
2773 }
2774
2775 /* Unmark. */
2776 for (tmp = sheets; tmp; tmp = tmp->next) {
2777 Sheet *sheet = tmp->data;
2778 sheet->being_invalidated = FALSE;
2779 }
2780 }
2781
2782 void
2783 dependents_invalidate_sheet (Sheet *sheet, gboolean destroy)
2784 {
2785 GSList l;
2786
2787 g_return_if_fail (IS_SHEET (sheet));
2788
2789 l.next = NULL;
2790 l.data = sheet;
2791 dependents_invalidate_sheets (&l, destroy);
2792 }
2793
2794 void
2795 dependents_workbook_destroy (Workbook *wb)
2796 {
2797 g_return_if_fail (GNM_IS_WORKBOOK (wb));
2798 g_return_if_fail (wb->during_destruction);
2799 g_return_if_fail (wb->sheets != NULL);
2800
2801 /* Mark all first. */
2802 WORKBOOK_FOREACH_SHEET (wb, sheet, sheet->being_invalidated = TRUE;);
2803
2804 /* Kill 3d deps and workbook-level names, if needed. */
2805 if (wb->sheet_order_dependents) {
2806 g_hash_table_destroy (wb->sheet_order_dependents);
2807 wb->sheet_order_dependents = NULL;
2808 }
2809 gnm_named_expr_collection_free (wb->names);
2810 wb->names = NULL;
2811
2812 WORKBOOK_FOREACH_SHEET (wb, sheet, do_deps_destroy (sheet););
2813
2814 /* Unmark. */
2815 WORKBOOK_FOREACH_SHEET (wb, sheet, sheet->being_invalidated = FALSE;);
2816 }
2817
2818 /*
2819 * dependents_revive_sheet:
2820 * Undo the effects of dependents_invalidate_sheet (sheet, FALSE).
2821 */
2822 void
2823 dependents_revive_sheet (Sheet *sheet)
2824 {
2825 go_undo_undo (GO_UNDO (sheet->revive));
2826 g_object_unref (sheet->revive);
2827 sheet->revive = NULL;
2828
2829 /* Re-link local names. */
2830 gnm_named_expr_collection_relink (sheet->names);
2831
2832 gnm_dep_container_sanity_check (sheet->deps);
2833 }
2834
2835 void
2836 workbook_queue_all_recalc (Workbook *wb)
2837 {
2838 /* FIXME: what about dependents in other workbooks? */
2839 WORKBOOK_FOREACH_DEPENDENT (wb, dep, dependent_flag_recalc (dep););
2840 }
2841
2842 void
2843 workbook_queue_volatile_recalc (Workbook *wb)
2844 {
2845 WORKBOOK_FOREACH_DEPENDENT (wb, dep, {
2846 if (dependent_is_volatile (dep))
2847 dependent_flag_recalc (dep);
2848 });
2849 }
2850
2851
2852 /**
2853 * workbook_recalc:
2854 * @wb:
2855 *
2856 * Computes all dependents in @wb that have been flaged as requiring
2857 * recomputation.
2858 *
2859 * NOTE! This does not recalc dependents in other workbooks.
2860 */
2861 void
2862 workbook_recalc (Workbook *wb)
2863 {
2864 gboolean redraw = FALSE;
2865
2866 g_return_if_fail (GNM_IS_WORKBOOK (wb));
2867
2868 gnm_app_recalc_start ();
2869
2870 WORKBOOK_FOREACH_DEPENDENT (wb, dep, {
2871 if (dependent_needs_recalc (dep)) {
2872 redraw = TRUE;
2873 dependent_eval (dep);
2874 }
2875 });
2876
2877 gnm_app_recalc_finish ();
2878
2879 /*
2880 * This is a bit of a band-aid. If anything is recalculated, we
2881 * force a full redraw. The alternative is to ask for updates
2882 * of every cell that is changed and that is probably more
2883 * expensive.
2884 */
2885 if (redraw) {
2886 WORKBOOK_FOREACH_SHEET (wb, sheet, {
2887 SHEET_FOREACH_VIEW (sheet, sv, gnm_sheet_view_flag_selection_change (sv););
2888 sheet_redraw_all (sheet, FALSE);});
2889 }
2890 }
2891
2892 /**
2893 * workbook_recalc_all:
2894 * @wb:
2895 *
2896 * Queues all dependents for recalc and recalculates.
2897 */
2898 void
2899 workbook_recalc_all (Workbook *wb)
2900 {
2901 workbook_queue_all_recalc (wb);
2902
2903 /* Recalculate this workbook unconditionally. */
2904 workbook_recalc (wb);
2905
2906 /* Recalculate other workbooks when needed. */
2907 gnm_app_recalc ();
2908
2909 WORKBOOK_FOREACH_VIEW (wb, view,
2910 sheet_update (wb_view_cur_sheet (view)););
2911 }
2912
2913 static void
2914 dynamic_dep_free (DynamicDep *dyn)
2915 {
2916 GnmDependent *dep = dyn->container;
2917 GnmCellPos const *pos = dependent_pos (dep);
2918 GnmRangeRef *rr;
2919 GSList *ptr;
2920
2921 for (ptr = dyn->singles ; ptr != NULL ; ptr = ptr->next) {
2922 rr = ptr->data;
2923 unlink_single_dep (&dyn->base, pos, &rr->a);
2924 g_free (rr);
2925 }
2926 g_slist_free (dyn->singles);
2927 dyn->singles = NULL;
2928
2929 for (ptr = dyn->ranges ; ptr != NULL ; ptr = ptr->next) {
2930 rr = ptr->data;
2931 link_unlink_cellrange_dep (&dyn->base, pos,
2932 &rr->a, &rr->b, FALSE);
2933 g_free (rr);
2934 }
2935 g_slist_free (dyn->ranges);
2936 dyn->ranges = NULL;
2937
2938 if (dyn->base.flags & DEPENDENT_HAS_3D)
2939 workbook_unlink_3d_dep (&dyn->base);
2940 g_free (dyn);
2941 }
2942
2943
2944 gboolean
2945 dependent_is_volatile (GnmDependent *dep)
2946 {
2947 /* This might need to be a virtual call. */
2948 return dep->texpr && gnm_expr_top_is_volatile (dep->texpr);
2949 }
2950
2951 /**
2952 * gnm_dep_container_new: (skip)
2953 * @sheet: #Sheet
2954 *
2955 * Returns: (transfer full):
2956 **/
2957 GnmDepContainer *
2958 gnm_dep_container_new (Sheet *sheet)
2959 {
2960 GnmDepContainer *deps = g_new (GnmDepContainer, 1);
2961
2962 deps->head = deps->tail = NULL;
2963
2964 deps->buckets = 1 + BUCKET_OF_ROW (gnm_sheet_get_last_row (sheet));
2965 deps->range_hash = g_new0 (GHashTable *, deps->buckets);
2966 deps->range_pool = go_mem_chunk_new ("range pool",
2967 sizeof (DependencyRange),
2968 16 * 1024 - 100);
2969 deps->single_hash = g_hash_table_new ((GHashFunc) depsingle_hash,
2970 (GEqualFunc) depsingle_equal);
2971 deps->single_pool = go_mem_chunk_new ("single pool",
2972 sizeof (DependencySingle),
2973 16 * 1024 - 100);
2974 deps->referencing_names = g_hash_table_new (g_direct_hash,
2975 g_direct_equal);
2976
2977 deps->dynamic_deps = g_hash_table_new_full (g_direct_hash, g_direct_equal,
2978 NULL, (GDestroyNotify) dynamic_dep_free);
2979
2980 return deps;
2981 }
2982
2983 void
2984 gnm_dep_container_resize (GnmDepContainer *deps, int rows)
2985 {
2986 int i, buckets = 1 + BUCKET_OF_ROW (rows - 1);
2987
2988 for (i = buckets; i < deps->buckets; i++) {
2989 GHashTable *hash = deps->range_hash[i];
2990 if (hash != NULL) {
2991 int s = g_hash_table_size (hash);
2992 if (s)
2993 g_printerr ("Hash table size: %d\n", s);
2994 g_hash_table_destroy (hash);
2995 deps->range_hash[i] = NULL;
2996 }
2997 }
2998
2999 deps->range_hash = g_renew (GHashTable *, deps->range_hash, buckets);
3000
3001 for (i = deps->buckets; i < buckets; i++)
3002 deps->range_hash[i] = NULL;
3003
3004 deps->buckets = buckets;
3005 }
3006
3007 /****************************************************************************
3008 * Debug utils
3009 */
3010
3011 static void
3012 dependent_debug_name_for_sheet (GnmDependent const *dep, Sheet *sheet,
3013 GString *target)
3014 {
3015 int t;
3016 GnmDependentClass *klass;
3017
3018 g_return_if_fail (dep != NULL);
3019 g_return_if_fail (dep_classes);
3020
3021 if (!dep->sheet)
3022 g_warning ("Invalid dep, missing sheet");
3023
3024 if (sheet == dep->sheet) {
3025 /* Nothing */
3026 } else {
3027 g_string_append (target,
3028 dep->sheet ? dep->sheet->name_quoted : "?");
3029 g_string_append_c (target, '!');
3030 }
3031
3032 t = dependent_type (dep);
3033 klass = g_ptr_array_index (dep_classes, t);
3034 klass->debug_name (dep, target);
3035 }
3036
3037
3038 /**
3039 * dependent_debug_name:
3040 * @dep: The dependent we are interested in.
3041 *
3042 * A useful little debugging utility.
3043 */
3044 void
3045 dependent_debug_name (GnmDependent const *dep, GString *target)
3046 {
3047 dependent_debug_name_for_sheet (dep, NULL, target);
3048 }
3049
3050
3051 static void
3052 dump_range_dep (gpointer key, G_GNUC_UNUSED gpointer value, gpointer sheet_)
3053 {
3054 DependencyRange const *deprange = key;
3055 GnmRange const *range = &(deprange->range);
3056 Sheet *sheet = sheet_;
3057 GString *target = g_string_sized_new (10000);
3058 gboolean first = TRUE;
3059
3060 g_string_append (target, " ");
3061 g_string_append (target, range_as_string (range));
3062 g_string_append (target, " -> (");
3063
3064 micro_hash_foreach_dep (deprange->deps, dep, {
3065 if (first)
3066 first = FALSE;
3067 else
3068 g_string_append (target, ", ");
3069 dependent_debug_name_for_sheet (dep, sheet, target);
3070 });
3071 g_string_append_c (target, ')');
3072
3073 g_printerr ("%s\n", target->str);
3074 g_string_free (target, TRUE);
3075 }
3076
3077 static void
3078 dump_single_dep (gpointer key, G_GNUC_UNUSED gpointer value, gpointer sheet_)
3079 {
3080 DependencySingle *depsingle = key;
3081 Sheet *sheet = sheet_;
3082 GString *target = g_string_sized_new (10000);
3083 gboolean first = TRUE;
3084
3085 g_string_append (target, " ");
3086 g_string_append (target, cellpos_as_string (&depsingle->pos));
3087 g_string_append (target, " -> ");
3088
3089 micro_hash_foreach_dep (depsingle->deps, dep, {
3090 if (first)
3091 first = FALSE;
3092 else
3093 g_string_append (target, ", ");
3094 dependent_debug_name_for_sheet (dep, sheet, target);
3095 });
3096
3097 g_printerr ("%s\n", target->str);
3098 g_string_free (target, TRUE);
3099 }
3100
3101 static void
3102 dump_dynamic_dep (gpointer key, G_GNUC_UNUSED gpointer value,
3103 G_GNUC_UNUSED gpointer closure)
3104 {
3105 GnmDependent *dep = key;
3106 DynamicDep *dyn = value;
3107 GSList *l;
3108 GnmParsePos pp;
3109 GnmConventionsOut out;
3110
3111 out.accum = g_string_new (NULL);
3112 out.pp = &pp;
3113 out.convs = gnm_conventions_default;
3114
3115 pp.wb = dep->sheet->workbook;
3116 pp.sheet = dep->sheet;
3117 pp.eval = *dependent_pos (dyn->container);
3118
3119 g_string_append (out.accum, " ");
3120 dependent_debug_name (dep, out.accum);
3121 g_string_append (out.accum, " -> ");
3122 dependent_debug_name (&dyn->base, out.accum);
3123 g_string_append (out.accum, " { c=");
3124 dependent_debug_name (dyn->container, out.accum);
3125
3126 g_string_append (out.accum, ", s=[");
3127 for (l = dyn->singles; l; l = l->next) {
3128 rangeref_as_string (&out, l->data);
3129 if (l->next)
3130 g_string_append (out.accum, ", ");
3131 }
3132
3133 g_string_append (out.accum, "], r=[");
3134 for (l = dyn->ranges; l; l = l->next) {
3135 rangeref_as_string (&out, l->data);
3136 if (l->next)
3137 g_string_append (out.accum, ", ");
3138 }
3139
3140 g_string_append (out.accum, "] }");
3141 g_printerr ("%s\n", out.accum->str);
3142 g_string_free (out.accum, TRUE);
3143 }
3144
3145 /**
3146 * gnm_dep_container_dump:
3147 * @deps:
3148 *
3149 * A useful utility for checking the state of the dependency data structures.
3150 */
3151 void
3152 gnm_dep_container_dump (GnmDepContainer const *deps,
3153 Sheet *sheet)
3154 {
3155 int i;
3156
3157 g_return_if_fail (deps != NULL);
3158
3159 gnm_dep_container_sanity_check (deps);
3160
3161 for (i = deps->buckets - 1; i >= 0 ; i--) {
3162 GHashTable *hash = deps->range_hash[i];
3163 if (hash != NULL && g_hash_table_size (hash) > 0) {
3164 g_printerr (" Bucket %d (rows %d-%d): Range hash size %d: range over which cells in list depend\n",
3165 i,
3166 BUCKET_START_ROW (i) + 1,
3167 BUCKET_END_ROW (i) + 1,
3168 g_hash_table_size (hash));
3169 g_hash_table_foreach (hash,
3170 dump_range_dep,
3171 sheet);
3172 }
3173 }
3174
3175 if (deps->single_hash && g_hash_table_size (deps->single_hash) > 0) {
3176 g_printerr (" Single hash size %d: cell on which list of cells depend\n",
3177 g_hash_table_size (deps->single_hash));
3178 g_hash_table_foreach (deps->single_hash,
3179 dump_single_dep,
3180 sheet);
3181 }
3182
3183 if (deps->dynamic_deps && g_hash_table_size (deps->dynamic_deps) > 0) {
3184 g_printerr (" Dynamic hash size %d: cells that depend on dynamic dependencies\n",
3185 g_hash_table_size (deps->dynamic_deps));
3186 g_hash_table_foreach (deps->dynamic_deps,
3187 dump_dynamic_dep, NULL);
3188 }
3189
3190 if (deps->referencing_names && g_hash_table_size (deps->referencing_names) > 0) {
3191 GSList *l, *names = NULL;
3192
3193 g_hash_table_foreach (deps->referencing_names,
3194 (GHFunc)cb_collect_names,
3195 &names);
3196
3197 g_printerr (" Names whose expressions explicitly reference this sheet\n ");
3198 for (l = names; l; l = l->next) {
3199 GnmNamedExpr *nexpr = l->data;
3200 g_printerr ("%s%s",
3201 expr_name_name (nexpr),
3202 l->next ? ", " : "\n");
3203 }
3204 g_slist_free (names);
3205 }
3206 }
3207
3208 void
3209 dependents_dump (Workbook *wb)
3210 {
3211 WORKBOOK_FOREACH_SHEET
3212 (wb, sheet,
3213 {
3214 int count = 0;
3215 SHEET_FOREACH_DEPENDENT (sheet, dep, count++;);
3216 g_printerr ("Dependencies for %s (count=%d):\n",
3217 sheet->name_unquoted, count);
3218 gnm_dep_container_dump (sheet->deps, sheet);
3219 });
3220 }
3221
3222 void
3223 gnm_dep_container_sanity_check (GnmDepContainer const *deps)
3224 {
3225 GnmDependent const *dep;
3226 GHashTable *seenb4;
3227
3228 if (deps->head && !deps->tail)
3229 g_warning ("Dependency container %p has head, but no tail.", (void *)deps);
3230 if (deps->tail && !deps->head)
3231 g_warning ("Dependency container %p has tail, but no head.", (void *)deps);
3232 if (deps->head && deps->head->prev_dep)
3233 g_warning ("Dependency container %p has head, but not at the beginning.", (void *)deps);
3234 if (deps->tail && deps->tail->next_dep)
3235 g_warning ("Dependency container %p has tail, but not at the end.", (void *)deps);
3236
3237 seenb4 = g_hash_table_new (g_direct_hash, g_direct_equal);
3238 for (dep = deps->head; dep; dep = dep->next_dep) {
3239 if (dep->prev_dep && (dep->prev_dep->next_dep != dep))
3240 g_warning ("Dependency container %p has left double-link failure at %p.", (void *)deps, (void *)dep);
3241 if (dep->next_dep && (dep->next_dep->prev_dep != dep))
3242 g_warning ("Dependency container %p has right double-link failure at %p.", (void *)deps, (void *)dep);
3243 if (!dep->next_dep && dep != deps->tail)
3244 g_warning ("Dependency container %p ends before its tail.", (void *)deps);
3245 if (!dependent_is_linked (dep))
3246 g_warning ("Dependency container %p contains unlinked dependency %p.", (void *)deps, (void *)dep);
3247 if (g_hash_table_lookup (seenb4, dep)) {
3248 g_warning ("Dependency container %p is circular.", (void *)deps);
3249 break;
3250 }
3251 g_hash_table_insert (seenb4, (gpointer)dep, (gpointer)dep);
3252 }
3253 g_hash_table_destroy (seenb4);
3254 }
3255
3256 /* ------------------------------------------------------------------------- */
gnumeric mirror