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