?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Update Spanish translation
[gnumeric.git] / src / dependent.c
blob217e6c08a5b63bd44bf9613b21070c1716dc851c
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 GnmFuncEvalInfo fei;
1115 GnmDependentFlags flag;
1116
1117 gnm_func_load_if_stub (tree->func.func);
1118 fei.pos = ep;
1119 fei.func_call = &tree->func;
1120 flag = gnm_func_link_dep (tree->func.func, &fei, qlink);
1121
1122 if (!(flag & DEPENDENT_IGNORE_ARGS))
1123 for (i = 0; i < tree->func.argc; i++)
1124 flag |= link_unlink_expr_dep (ep, tree->func.argv[i], qlink);
1125 return flag;
1126 }
1127
1128 case GNM_EXPR_OP_NAME:
1129 if (qlink)
1130 expr_name_add_dep (tree->name.name, ep->dep);
1131 else
1132 expr_name_remove_dep (tree->name.name, ep->dep);
1133 if (expr_name_is_active (tree->name.name))
1134 return link_unlink_expr_dep (ep, tree->name.name->texpr->expr, qlink) | DEPENDENT_USES_NAME;
1135 return DEPENDENT_USES_NAME;
1136
1137 case GNM_EXPR_OP_ARRAY_ELEM: {
1138 /* Non-corner cells depend on the corner */
1139 GnmCellRef a;
1140 GnmCellPos const *pos = dependent_pos (ep->dep);
1141 // We cannot support array expressions unless we have
1142 // a position.
1143 g_return_val_if_fail (pos != NULL, DEPENDENT_NO_FLAG);
1144
1145 a.col_relative = a.row_relative = FALSE;
1146 a.sheet = ep->dep->sheet;
1147 a.col = pos->col - tree->array_elem.x;
1148 a.row = pos->row - tree->array_elem.y;
1149
1150 return link_unlink_single_dep (ep->dep, pos, &a, qlink);
1151 }
1152
1153 case GNM_EXPR_OP_ARRAY_CORNER: {
1154 // It's mildly unclean to do this here. We need the texpr, so get the cell.
1155 GnmCellPos const *cpos = dependent_pos (ep->dep);
1156 GnmCell const *cell = sheet_cell_get (ep->dep->sheet, cpos->col, cpos->row);
1157 GnmEvalPos pos = *ep;
1158 pos.array_texpr = cell->base.texpr;
1159 /* Corner cell depends on the contents of the expr */
1160 return link_unlink_expr_dep (&pos, tree->array_corner.expr, qlink);
1161 }
1162
1163 case GNM_EXPR_OP_SET: {
1164 int i;
1165 GnmDependentFlags res = DEPENDENT_NO_FLAG;
1166
1167 for (i = 0; i < tree->set.argc; i++)
1168 res |= link_unlink_expr_dep (ep, tree->set.argv[i], qlink);
1169 return res;
1170 }
1171 #ifndef DEBUG_SWITCH_ENUM
1172 default:
1173 g_assert_not_reached ();
1174 #endif
1175 }
1176 return DEPENDENT_NO_FLAG;
1177 }
1178
1179 static void
1180 workbook_link_3d_dep (GnmDependent *dep)
1181 {
1182 Workbook *wb = dep->sheet->workbook;
1183
1184 if (wb->being_reordered)
1185 return;
1186 if (wb->sheet_order_dependents == NULL)
1187 wb->sheet_order_dependents =
1188 g_hash_table_new (g_direct_hash, g_direct_equal);
1189 g_hash_table_insert (wb->sheet_order_dependents, dep, dep);
1190 }
1191
1192 static void
1193 workbook_unlink_3d_dep (GnmDependent *dep)
1194 {
1195 Workbook *wb = dep->sheet->workbook;
1196
1197 /* during destruction */
1198 if (wb->sheet_order_dependents == NULL)
1199 return;
1200
1201 if (wb->being_reordered)
1202 return;
1203
1204 g_hash_table_remove (wb->sheet_order_dependents, dep);
1205 }
1206
1207 /**
1208 * gnm_dep_style_dependency:
1209 * @sheet:
1210 * @texpr:
1211 * @r:
1212 * @accum: (inout) (transfer full) (element-type GnmDependent):
1213 **/
1214 void
1215 gnm_dep_style_dependency (Sheet *sheet,
1216 GnmExprTop const *texpr,
1217 GnmRange const *r,
1218 GPtrArray *accum)
1219 {
1220 int row, col;
1221
1222 /*
1223 * FIXME: Maybe do better for an expression that is just an
1224 * absolute ref.
1225 */
1226
1227 for (row = r->start.row; row <= r->end.row; row++) {
1228 for (col = r->start.col; col <= r->end.col; col++) {
1229 GnmStyleDependent *sd = g_new0 (GnmStyleDependent, 1);
1230 GnmDependent *dep = &sd->base;
1231
1232 dep->sheet = sheet;
1233 dep->flags = DEPENDENT_STYLE;
1234 dep->texpr = NULL;
1235 sd->pos.col = col;
1236 sd->pos.row = row;
1237
1238 dependent_set_expr (dep, texpr);
1239 dependent_link (dep);
1240 g_ptr_array_add (accum, dep);
1241 }
1242 }
1243 }
1244
1245 /*****************************************************************************/
1246
1247 static void
1248 cell_dep_eval (GnmDependent *dep)
1249 {
1250 gboolean finished = gnm_cell_eval_content (GNM_DEP_TO_CELL (dep));
1251 (void)finished; /* We don't currently care */
1252 dep->flags &= ~GNM_CELL_HAS_NEW_EXPR;
1253 }
1254
1255 static void
1256 cell_dep_set_expr (GnmDependent *dep, GnmExprTop const *new_texpr)
1257 {
1258 /*
1259 * Explicitly do not check for array subdivision, we may be
1260 * replacing the corner of an array.
1261 */
1262 gnm_cell_set_expr_unsafe (GNM_DEP_TO_CELL (dep), new_texpr);
1263 }
1264
1265 static GSList *
1266 cell_dep_changed (GnmDependent *dep)
1267 {
1268 /* When a cell changes, so do its dependents. */
1269
1270 GSList *deps = cell_list_deps (GNM_DEP_TO_CELL (dep));
1271 GSList *waste = NULL, *work = NULL;
1272 GSList *next, *list;
1273 for (list = deps; list != NULL ; list = next) {
1274 GnmDependent *dep = list->data;
1275 next = list->next;
1276 if (dependent_needs_recalc (dep)) {
1277 list->next = waste;
1278 waste = list;
1279 } else {
1280 dependent_flag_recalc (dep);
1281 list->next = work;
1282 work = list;
1283 }
1284 }
1285 g_slist_free (waste);
1286 return work;
1287 }
1288
1289 static GnmCellPos *
1290 cell_dep_pos (GnmDependent const *dep)
1291 {
1292 return &GNM_DEP_TO_CELL (dep)->pos;
1293 }
1294
1295 static void
1296 cell_dep_debug_name (GnmDependent const *dep, GString *target)
1297 {
1298 g_string_append (target, cell_name (GNM_DEP_TO_CELL (dep)));
1299 }
1300
1301 /*****************************************************************************/
1302 /*
1303 * "Managed" dependent handling.
1304 *
1305 * A managed dependent is simply an expression set up to be maintained by
1306 * the dependency system so it follows row/column insert/delete nicely.
1307 *
1308 * The expression being managed is typically a cell range, but can be any
1309 * expression. Everything is interpreted relative to A1 in the sheet.
1310 */
1311
1312 void
1313 dependent_managed_init (GnmDependent *dep, Sheet *sheet)
1314 {
1315 memset (dep, 0, sizeof (*dep));
1316 dep->flags = DEPENDENT_MANAGED;
1317 dep->sheet = sheet;
1318 }
1319
1320 void
1321 dependent_managed_set_expr (GnmDependent *dep, GnmExprTop const *texpr)
1322 {
1323 g_return_if_fail (dep != NULL);
1324 #if 0
1325 /* We need some kind of IS_A */
1326 g_return_if_fail (dependent_type (dep) == DEPENDENT_MANAGED);
1327 #endif
1328
1329 dependent_set_expr (dep, texpr);
1330 if (texpr && dep->sheet)
1331 dependent_link (dep);
1332 }
1333
1334 void
1335 dependent_managed_set_sheet (GnmDependent *dep, Sheet *sheet)
1336 {
1337 GnmExprTop const *texpr;
1338
1339 g_return_if_fail (dep != NULL);
1340 #if 0
1341 /* We need some kind of IS_A */
1342 g_return_if_fail (dependent_type (dep) == DEPENDENT_MANAGED);
1343 #endif
1344
1345 if (dep->sheet == sheet)
1346 return;
1347
1348 texpr = dep->texpr;
1349 if (texpr) gnm_expr_top_ref (texpr);
1350 dependent_set_expr (dep, NULL);
1351 /* We're now unlinked from everything. */
1352 dep->sheet = sheet;
1353 dependent_managed_set_expr (dep, texpr);
1354 if (texpr) gnm_expr_top_unref (texpr);
1355 }
1356
1357 static void
1358 managed_dep_debug_name (GnmDependent const *dep, GString *target)
1359 {
1360 g_string_append_printf (target, "Managed%p", (void *)dep);
1361 }
1362
1363 /*****************************************************************************/
1364
1365 static gboolean
1366 debug_style_deps (void)
1367 {
1368 static int debug = -1;
1369 if (debug < 0)
1370 debug = gnm_debug_flag ("style-deps");
1371 return debug;
1372 }
1373
1374 static void
1375 style_dep_unrender (GnmDependent *dep, const char *what)
1376 {
1377 GnmCellPos const *pos = dependent_pos (dep);
1378 GnmCell *cell;
1379 Sheet *sheet = dep->sheet;
1380
1381 if (debug_style_deps ())
1382 g_printerr ("StyleDep %p at %s %s\n",
1383 dep, cellpos_as_string (pos), what);
1384
1385 /*
1386 * If the cell exists, unrender it so format changes can take
1387 * effect.
1388 */
1389 cell = sheet_cell_get (sheet, pos->col, pos->row);
1390 if (cell)
1391 gnm_cell_unrender (cell);
1392
1393 sheet_redraw_region (sheet,
1394 pos->col, pos->row,
1395 pos->col, pos->row);
1396 }
1397
1398 static void
1399 style_dep_eval (GnmDependent *dep)
1400 {
1401 /*
1402 * It is possible that the cell has been rendered between ::changed
1403 * was called and now.
1404 */
1405 style_dep_unrender (dep, "being evaluated");
1406 }
1407
1408 static GSList *
1409 style_dep_changed (GnmDependent *dep)
1410 {
1411 style_dep_unrender (dep, "changed");
1412 return NULL;
1413 }
1414
1415 static GnmCellPos *
1416 style_dep_pos (GnmDependent const *dep)
1417 {
1418 return &((GnmStyleDependent*)dep)->pos;
1419 }
1420
1421 static void
1422 style_dep_debug_name (GnmDependent const *dep, GString *target)
1423 {
1424 g_string_append_printf (target, "StyleDep@%s[%p]",
1425 cellpos_as_string (style_dep_pos (dep)),
1426 dep);
1427 }
1428
1429 /*****************************************************************************/
1430
1431 static void
1432 name_dep_debug_name (GnmDependent const *dep, GString *target)
1433 {
1434 g_string_append_printf (target, "Name%p", (void *)dep);
1435 }
1436
1437 /*****************************************************************************/
1438
1439 static GSList *
1440 dynamic_dep_changed (GnmDependent *dep)
1441 {
1442 DynamicDep const *dyn = (DynamicDep *)dep;
1443
1444 /* When a dynamic dependent changes, we mark its container. */
1445
1446 if (dependent_needs_recalc (dyn->container))
1447 return NULL;
1448
1449 dependent_flag_recalc (dyn->container);
1450 return g_slist_prepend (NULL, dyn->container);
1451 }
1452
1453 static void
1454 dynamic_dep_debug_name (GnmDependent const *dep, GString *target)
1455 {
1456 g_string_append_printf (target, "DynamicDep%p", (void *)dep);
1457 }
1458
1459 void
1460 dependent_add_dynamic_dep (GnmDependent *dep, GnmRangeRef const *rr)
1461 {
1462 GnmDependentFlags flags;
1463 DynamicDep *dyn;
1464 GnmCellPos const *pos;
1465 DependencyRange range;
1466
1467 g_return_if_fail (dep != NULL);
1468
1469 pos = dependent_pos (dep);
1470
1471 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS)
1472 dyn = g_hash_table_lookup (dep->sheet->deps->dynamic_deps, dep);
1473 else {
1474 dep->flags |= DEPENDENT_HAS_DYNAMIC_DEPS;
1475 dyn = g_new (DynamicDep, 1);
1476 dyn->base.flags = DEPENDENT_DYNAMIC_DEP;
1477 dyn->base.sheet = dep->sheet;
1478 dyn->base.texpr = NULL;
1479 dyn->container = dep;
1480 dyn->ranges = NULL;
1481 dyn->singles = NULL;
1482 g_hash_table_insert (dep->sheet->deps->dynamic_deps, dep, dyn);
1483 }
1484
1485 gnm_cellpos_init_cellref (&range.range.start, &rr->a, pos, dep->sheet);
1486 gnm_cellpos_init_cellref (&range.range.end, &rr->b, pos, dep->sheet);
1487 if (range_is_singleton (&range.range)) {
1488 flags = link_single_dep (&dyn->base, pos, &rr->a);
1489 dyn->singles = g_slist_prepend (dyn->singles, gnm_rangeref_dup (rr));
1490 } else {
1491 flags = link_unlink_cellrange_dep (&dyn->base, pos, &rr->a, &rr->b, TRUE);
1492 dyn->ranges = g_slist_prepend (dyn->ranges, gnm_rangeref_dup (rr));
1493 }
1494 if (flags & DEPENDENT_HAS_3D)
1495 workbook_link_3d_dep (dep);
1496 }
1497
1498 static void
1499 dependent_clear_dynamic_deps (GnmDependent *dep)
1500 {
1501 g_hash_table_remove (dep->sheet->deps->dynamic_deps, dep);
1502 }
1503
1504 /*****************************************************************************/
1505
1506 /**
1507 * dependent_link:
1508 * @dep: the dependent that changed
1509 *
1510 * Adds the dependent to the workbook wide list of dependents.
1511 */
1512 void
1513 dependent_link (GnmDependent *dep)
1514 {
1515 Sheet *sheet;
1516 GnmEvalPos ep;
1517
1518 g_return_if_fail (dep != NULL);
1519 g_return_if_fail (dep->texpr != NULL);
1520 g_return_if_fail (!(dep->flags & DEPENDENT_IS_LINKED));
1521 g_return_if_fail (IS_SHEET (dep->sheet));
1522 g_return_if_fail (dep->sheet->deps != NULL);
1523
1524 sheet = dep->sheet;
1525
1526 /* Make this the new tail of the dependent list. */
1527 dep->prev_dep = sheet->deps->tail;
1528 dep->next_dep = NULL;
1529 if (dep->prev_dep)
1530 dep->prev_dep->next_dep = dep;
1531 else
1532 sheet->deps->head = dep; /* first element */
1533 sheet->deps->tail = dep;
1534 dep->flags |= DEPENDENT_IS_LINKED |
1535 link_unlink_expr_dep (eval_pos_init_dep (&ep, dep),
1536 dep->texpr->expr, TRUE);
1537
1538 if (dep->flags & DEPENDENT_HAS_3D)
1539 workbook_link_3d_dep (dep);
1540 }
1541
1542 /**
1543 * dependent_unlink:
1544 * @dep: the dependent that changed
1545 *
1546 * Removes the dependent from its container's set of dependents and always
1547 * removes the linkages to what it depends on.
1548 */
1549 void
1550 dependent_unlink (GnmDependent *dep)
1551 {
1552 GnmDepContainer *contain;
1553 GnmEvalPos ep;
1554
1555 g_return_if_fail (dep != NULL);
1556 g_return_if_fail (dependent_is_linked (dep));
1557 g_return_if_fail (dep->texpr != NULL);
1558 g_return_if_fail (IS_SHEET (dep->sheet));
1559
1560 link_unlink_expr_dep (eval_pos_init_dep (&ep, dep),
1561 dep->texpr->expr, FALSE);
1562 contain = dep->sheet->deps;
1563 if (contain != NULL) {
1564 if (contain->head == dep)
1565 contain->head = dep->next_dep;
1566 if (contain->tail == dep)
1567 contain->tail = dep->prev_dep;
1568 if (dep->next_dep)
1569 dep->next_dep->prev_dep = dep->prev_dep;
1570 if (dep->prev_dep)
1571 dep->prev_dep->next_dep = dep->next_dep;
1572
1573 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS)
1574 dependent_clear_dynamic_deps (dep);
1575 }
1576
1577 if (dep->flags & DEPENDENT_HAS_3D)
1578 workbook_unlink_3d_dep (dep);
1579 dep->flags &= ~DEPENDENT_LINK_FLAGS;
1580 }
1581
1582 /**
1583 * gnm_cell_eval_content:
1584 * @cell: the cell to evaluate.
1585 *
1586 * This function evaluates the contents of the cell,
1587 * it should not be used by anyone. It is an internal
1588 * function.
1589 **/
1590 static gboolean
1591 gnm_cell_eval_content (GnmCell *cell)
1592 {
1593 static GnmCell *iterating = NULL;
1594 GnmValue *v;
1595 GnmEvalPos pos;
1596 int max_iteration;
1597
1598 if (!gnm_cell_has_expr (cell) || /* plain cells without expr */
1599 !dependent_is_linked (&cell->base)) /* special case within TABLE */
1600 return TRUE;
1601
1602 #ifdef DEBUG_EVALUATION
1603 {
1604 GnmParsePos pp;
1605 char *str = gnm_expr_top_as_string
1606 (cell->base.texpr,
1607 parse_pos_init_cell (&pp, cell),
1608 NULL);
1609 g_printerr ("{\nEvaluating %s!%s: %s;\n",
1610 cell->base.sheet->name_quoted, cell_name (cell),
1611 str);
1612 g_free (str);
1613 }
1614 #endif
1615
1616 /* This is the bottom of a cycle */
1617 if (cell->base.flags & DEPENDENT_BEING_CALCULATED) {
1618 if (!cell->base.sheet->workbook->iteration.enabled)
1619 return TRUE;
1620
1621 /* but not the first bottom */
1622 if (cell->base.flags & DEPENDENT_BEING_ITERATED) {
1623 #ifdef DEBUG_EVALUATION
1624 g_printerr ("}; /* already-iterate (%d) */\n", iterating == NULL);
1625 #endif
1626 return iterating == NULL;
1627 }
1628
1629 /* if we are still marked as iterating then make this the last
1630 * time through.
1631 */
1632 if (iterating == cell) {
1633 #ifdef DEBUG_EVALUATION
1634 puts ("}; /* NO-iterate (1) */");
1635 #endif
1636 return TRUE;
1637 } else if (iterating == NULL) {
1638 cell->base.flags |= DEPENDENT_BEING_ITERATED;
1639 iterating = cell;
1640 #ifdef DEBUG_EVALUATION
1641 puts ("}; /* START iterate = TRUE (0) */");
1642 #endif
1643 return FALSE;
1644 } else {
1645 #ifdef DEBUG_EVALUATION
1646 puts ("}; /* other-iterate (0) */");
1647 #endif
1648 return FALSE;
1649 }
1650 }
1651
1652 /* Prepare to calculate */
1653 eval_pos_init_cell (&pos, cell);
1654 cell->base.flags |= DEPENDENT_BEING_CALCULATED;
1655
1656 /*
1657 * I'm somewhat afraid of thinking about the semantics of iteration
1658 * if different workbooks have different settings.
1659 */
1660 max_iteration = cell->base.sheet->workbook->iteration.max_number;
1661
1662 iterate:
1663 v = gnm_expr_top_eval (cell->base.texpr, &pos,
1664 GNM_EXPR_EVAL_SCALAR_NON_EMPTY);
1665 if (v == NULL)
1666 v = value_new_error (&pos, "Internal error");
1667
1668 #ifdef DEBUG_EVALUATION
1669 {
1670 char *valtxt = v
1671 ? value_get_as_string (v)
1672 : g_strdup ("NULL");
1673 g_printerr ("Evaluation(%d) %s := %s\n",
1674 max_iteration, cell_name (cell), valtxt);
1675 g_free (valtxt);
1676 }
1677 #endif
1678
1679 /* The top of a cycle */
1680 if (cell->base.flags & DEPENDENT_BEING_ITERATED) {
1681 cell->base.flags &= ~DEPENDENT_BEING_ITERATED;
1682
1683 /* We just completed the last iteration, don't change things */
1684 if (iterating && max_iteration-- > 0) {
1685 /* If we are within bounds make this the last round */
1686 if (value_diff (cell->value, v) < cell->base.sheet->workbook->iteration.tolerance)
1687 max_iteration = 0;
1688 else {
1689 #ifdef DEBUG_EVALUATION
1690 puts ("/* iterate == NULL */");
1691 #endif
1692 iterating = NULL;
1693 }
1694 value_release (cell->value);
1695 cell->value = v;
1696
1697 gnm_cell_unrender (cell);
1698 #ifdef DEBUG_EVALUATION
1699 puts ("/* LOOP */");
1700 #endif
1701 goto iterate;
1702 }
1703 g_return_val_if_fail (iterating, TRUE);
1704 iterating = NULL;
1705 } else {
1706 gboolean had_value = (cell->value != NULL);
1707 if (had_value && value_equal (v, cell->value)) {
1708 /* Value didn't change. */
1709 value_release (v);
1710 } else {
1711 gboolean was_string = had_value && (VALUE_IS_STRING (cell->value) || VALUE_IS_ERROR (cell->value));
1712 gboolean is_string = VALUE_IS_STRING (v) || VALUE_IS_ERROR (v);
1713
1714 if ((was_string || is_string))
1715 sheet_cell_queue_respan (cell);
1716
1717 if (had_value)
1718 value_release (cell->value);
1719 cell->value = v;
1720
1721 gnm_cell_unrender (cell);
1722 }
1723 }
1724
1725 if (iterating == cell)
1726 iterating = NULL;
1727
1728 #ifdef DEBUG_EVALUATION
1729 g_printerr ("} (%d)\n", iterating == NULL);
1730 #endif
1731 cell->base.flags &= ~DEPENDENT_BEING_CALCULATED;
1732 return iterating == NULL;
1733 }
1734
1735 /**
1736 * dependent_eval:
1737 * @dep:
1738 */
1739 static void
1740 dependent_eval (GnmDependent *dep)
1741 {
1742 int const t = dependent_type (dep);
1743 GnmDependentClass *klass = g_ptr_array_index (dep_classes, t);
1744
1745 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS) {
1746 dependent_clear_dynamic_deps (dep);
1747 dep->flags &= ~DEPENDENT_HAS_DYNAMIC_DEPS;
1748 }
1749
1750 /*
1751 * Problem: this really should be a tail call.
1752 */
1753 klass->eval (dep);
1754
1755 /* Don't clear flag until after in case we iterate */
1756 dep->flags &= ~DEPENDENT_NEEDS_RECALC;
1757 }
1758
1759 void
1760 gnm_cell_eval (GnmCell *cell)
1761 {
1762 if (gnm_cell_needs_recalc (cell)) {
1763 /*
1764 * This should be a tail call so the stack frame can be
1765 * eliminated before the call.
1766 */
1767 dependent_eval (GNM_CELL_TO_DEP (cell));
1768 }
1769 }
1770
1771
1772 /**
1773 * cell_queue_recalc:
1774 * @cell:
1775 *
1776 * Queue the cell and everything that depends on it for recalculation.
1777 * If a dependency is already queued ignore it.
1778 */
1779 void
1780 cell_queue_recalc (GnmCell *cell)
1781 {
1782 g_return_if_fail (cell != NULL);
1783
1784 if (!gnm_cell_needs_recalc (cell)) {
1785 GSList *deps;
1786
1787 if (gnm_cell_has_expr (cell))
1788 dependent_flag_recalc (GNM_CELL_TO_DEP (cell));
1789
1790 deps = cell_list_deps (cell);
1791 dependent_queue_recalc_list (deps);
1792 g_slist_free (deps);
1793 }
1794 }
1795
1796 typedef struct {
1797 int col, row;
1798 GnmDepFunc func;
1799 gpointer user;
1800 } search_rangedeps_closure_t;
1801
1802 static void
1803 cb_search_rangedeps (gpointer key, G_GNUC_UNUSED gpointer value,
1804 gpointer closure)
1805 {
1806 search_rangedeps_closure_t const *c = closure;
1807 DependencyRange const *deprange = key;
1808 GnmRange const *range = &(deprange->range);
1809
1810 #if 0
1811 /* When things get slow this is a good test to enable */
1812 static int counter = 0;
1813 if ((++counter % 100000) == 0)
1814 g_printerr ("%d\n", counter / 100000);
1815 #endif
1816
1817 if (range_contains (range, c->col, c->row)) {
1818 GnmDepFunc func = c->func;
1819 micro_hash_foreach_dep (deprange->deps, dep,
1820 (func) (dep, c->user););
1821 }
1822 }
1823
1824 static void
1825 cell_foreach_range_dep (GnmCell const *cell, GnmDepFunc func, gpointer user)
1826 {
1827 search_rangedeps_closure_t closure;
1828 GHashTable *bucket =
1829 cell->base.sheet->deps->range_hash[BUCKET_OF_ROW (cell->pos.row)];
1830
1831 if (bucket != NULL) {
1832 closure.col = cell->pos.col;
1833 closure.row = cell->pos.row;
1834 closure.func = func;
1835 closure.user = user;
1836 g_hash_table_foreach (bucket, &cb_search_rangedeps, &closure);
1837 }
1838 }
1839
1840 static void
1841 cell_foreach_single_dep (Sheet const *sheet, int col, int row,
1842 GnmDepFunc func, gpointer user)
1843 {
1844 DependencySingle lookup, *single;
1845 GnmDepContainer *deps = sheet->deps;
1846
1847 lookup.pos.col = col;
1848 lookup.pos.row = row;
1849
1850 single = g_hash_table_lookup (deps->single_hash, &lookup);
1851 if (single != NULL)
1852 micro_hash_foreach_dep (single->deps, dep,
1853 (*func) (dep, user););
1854 }
1855
1856 /**
1857 * cell_foreach_dep:
1858 * @cell: #GnmCell
1859 * @func: (scope call):
1860 * @user: user data.
1861 *
1862 **/
1863 void
1864 cell_foreach_dep (GnmCell const *cell, GnmDepFunc func, gpointer user)
1865 {
1866 g_return_if_fail (cell != NULL);
1867
1868 /* accelerate exit */
1869 if (!cell->base.sheet->deps)
1870 return;
1871
1872 cell_foreach_range_dep (cell, func, user);
1873 cell_foreach_single_dep (cell->base.sheet, cell->pos.col, cell->pos.row,
1874 func, user);
1875 }
1876
1877 static void
1878 cb_recalc_all_depends (gpointer key, G_GNUC_UNUSED gpointer value,
1879 G_GNUC_UNUSED gpointer ignore)
1880 {
1881 DependencyAny const *depany = key;
1882 GSList *work = NULL;
1883 micro_hash_foreach_dep (depany->deps, dep, {
1884 if (!dependent_needs_recalc (dep)) {
1885 dependent_flag_recalc (dep);
1886 work = g_slist_prepend (work, dep);
1887 }
1888 });
1889 dependent_queue_recalc_main (work);
1890 }
1891
1892
1893
1894 static void
1895 cb_range_contained_depend (gpointer key, G_GNUC_UNUSED gpointer value,
1896 gpointer user)
1897 {
1898 DependencyRange const *deprange = key;
1899 GnmRange const *range = &deprange->range;
1900 GnmRange const *target = user;
1901
1902 if (range_overlap (target, range)) {
1903 GSList *work = NULL;
1904 micro_hash_foreach_dep (deprange->deps, dep, {
1905 if (!dependent_needs_recalc (dep)) {
1906 dependent_flag_recalc (dep);
1907 work = g_slist_prepend (work, dep);
1908 }
1909 });
1910 dependent_queue_recalc_main (work);
1911 }
1912 }
1913
1914 static void
1915 cb_single_contained_depend (gpointer key,
1916 G_GNUC_UNUSED gpointer value,
1917 gpointer user)
1918 {
1919 DependencySingle const *depsingle = key;
1920 GnmRange const *target = user;
1921
1922 if (range_contains (target, depsingle->pos.col, depsingle->pos.row)) {
1923 GSList *work = NULL;
1924 micro_hash_foreach_dep (depsingle->deps, dep, {
1925 if (!dependent_needs_recalc (dep)) {
1926 dependent_flag_recalc (dep);
1927 work = g_slist_prepend (work, dep);
1928 }
1929 });
1930 dependent_queue_recalc_main (work);
1931 }
1932 }
1933
1934 /**
1935 * sheet_region_queue_recalc:
1936 * @sheet: The sheet.
1937 * @range: Optionally NULL range.
1938 *
1939 * Queues things that depend on @sheet!@range for recalc.
1940 *
1941 * If @range is NULL the entire sheet is used.
1942 */
1943 void
1944 sheet_region_queue_recalc (Sheet const *sheet, GnmRange const *r)
1945 {
1946 int i;
1947
1948 g_return_if_fail (IS_SHEET (sheet));
1949 g_return_if_fail (sheet->deps != NULL);
1950
1951 if (r == NULL) {
1952 /* mark the contained depends dirty non recursively */
1953 SHEET_FOREACH_DEPENDENT (sheet, dep,
1954 dependent_flag_recalc (dep););
1955
1956 /* look for things that depend on the sheet */
1957 for (i = sheet->deps->buckets - 1; i >= 0 ; i--) {
1958 GHashTable *hash = sheet->deps->range_hash[i];
1959 if (hash != NULL)
1960 g_hash_table_foreach (hash,
1961 &cb_recalc_all_depends, NULL);
1962 }
1963 g_hash_table_foreach (sheet->deps->single_hash,
1964 &cb_recalc_all_depends, NULL);
1965 } else {
1966 int const first = BUCKET_OF_ROW (r->start.row);
1967
1968 /* mark the contained depends dirty non recursively */
1969 SHEET_FOREACH_DEPENDENT (sheet, dep, {
1970 GnmCell *cell = GNM_DEP_TO_CELL (dep);
1971 if (dependent_is_cell (dep) &&
1972 range_contains (r, cell->pos.col, cell->pos.row))
1973 dependent_flag_recalc (dep);
1974 });
1975
1976 /* look for things that depend on target region */
1977 for (i = BUCKET_OF_ROW (r->end.row); i >= first ; i--) {
1978 GHashTable *hash = sheet->deps->range_hash[i];
1979 if (hash != NULL)
1980 g_hash_table_foreach (hash,
1981 &cb_range_contained_depend, (gpointer)r);
1982 }
1983 g_hash_table_foreach (sheet->deps->single_hash,
1984 &cb_single_contained_depend, (gpointer)r);
1985 }
1986 }
1987
1988 typedef struct
1989 {
1990 int dep_type;
1991 union {
1992 GnmParsePos pos;
1993 GnmDependent *dep;
1994 } u;
1995 GnmExprTop const *oldtree;
1996 } ExprRelocateStorage;
1997
1998 /**
1999 * dependents_unrelocate_free:
2000 * @info:
2001 *
2002 * Free the undo info associated with a dependent relocation.
2003 */
2004 static void
2005 dependents_unrelocate_free (GSList *info)
2006 {
2007 GSList *ptr = info;
2008 for (; ptr != NULL ; ptr = ptr->next) {
2009 ExprRelocateStorage *tmp = ptr->data;
2010 gnm_expr_top_unref (tmp->oldtree);
2011 g_free (tmp);
2012 }
2013 g_slist_free (info);
2014 }
2015
2016 /**
2017 * dependents_unrelocate:
2018 * @info:
2019 *
2020 * Apply the undo info associated with a dependent relocation.
2021 */
2022 static void
2023 dependents_unrelocate (GSList *info)
2024 {
2025 GSList *ptr = info;
2026 for (; ptr != NULL ; ptr = ptr->next) {
2027 ExprRelocateStorage *tmp = ptr->data;
2028
2029 if (tmp->dep_type == DEPENDENT_CELL) {
2030 if (!IS_SHEET (tmp->u.pos.sheet)) {
2031 /* FIXME : happens when undoing a move from a deleted
2032 * sheet. Do we want to do something here */
2033 } else {
2034 GnmCell *cell = sheet_cell_get
2035 (tmp->u.pos.sheet,
2036 tmp->u.pos.eval.col, tmp->u.pos.eval.row);
2037
2038 /* It is possible to have a NULL if the relocation info
2039 * is not really relevant. eg when undoing a pasted
2040 * cut that was relocated but also saved to a buffer */
2041 if (cell != NULL) {
2042 if (gnm_expr_top_is_array_corner (tmp->oldtree)) {
2043 int cols, rows;
2044
2045 gnm_expr_top_get_array_size (tmp->oldtree, &cols, &rows);
2046 gnm_cell_set_array_formula (tmp->u.pos.sheet,
2047 tmp->u.pos.eval.col,
2048 tmp->u.pos.eval.row,
2049 tmp->u.pos.eval.col + cols - 1,
2050 tmp->u.pos.eval.row + rows - 1,
2051 gnm_expr_top_new (gnm_expr_copy (gnm_expr_top_get_array_expr (tmp->oldtree))));
2052 cell_queue_recalc (cell);
2053 sheet_flag_status_update_cell (cell);
2054 } else
2055 sheet_cell_set_expr (cell, tmp->oldtree);
2056 }
2057 }
2058 } else if (tmp->dep_type == DEPENDENT_NAME) {
2059 } else {
2060 dependent_set_expr (tmp->u.dep, tmp->oldtree);
2061 dependent_flag_recalc (tmp->u.dep);
2062 dependent_link (tmp->u.dep);
2063 }
2064 }
2065 }
2066
2067 /**
2068 * dependents_link:
2069 * @deps: (element-type GnmDependent): An slist of dependents.
2070 *
2071 * link a list of dependents. (The list used to get freed, but is not
2072 * freed anymore.)
2073 */
2074 void
2075 dependents_link (GSList *deps)
2076 {
2077 GSList *ptr = deps;
2078
2079 /* put them back */
2080 for (; ptr != NULL ; ptr = ptr->next) {
2081 GnmDependent *dep = ptr->data;
2082 if (dep->sheet->being_invalidated)
2083 continue;
2084 if (dep->sheet->deps != NULL && !dependent_is_linked (dep)) {
2085 dependent_link (dep);
2086 dependent_queue_recalc (dep);
2087 }
2088 }
2089 }
2090
2091 typedef struct {
2092 GnmRange const *target;
2093 GSList *list;
2094 } CollectClosure;
2095
2096 static void
2097 cb_range_contained_collect (DependencyRange const *deprange,
2098 G_GNUC_UNUSED gpointer ignored,
2099 CollectClosure *user)
2100 {
2101 GnmRange const *range = &deprange->range;
2102
2103 if (range_overlap (user->target, range))
2104 micro_hash_foreach_dep (deprange->deps, dep, {
2105 if (!(dep->flags & (DEPENDENT_FLAGGED | DEPENDENT_CAN_RELOCATE)) &&
2106 dependent_type (dep) != DEPENDENT_DYNAMIC_DEP) {
2107 dep->flags |= DEPENDENT_FLAGGED;
2108 user->list = g_slist_prepend (user->list, dep);
2109 }});
2110 }
2111
2112 static void
2113 cb_single_contained_collect (DependencySingle const *depsingle,
2114 G_GNUC_UNUSED gpointer ignored,
2115 CollectClosure *user)
2116 {
2117 if (range_contains (user->target, depsingle->pos.col, depsingle->pos.row))
2118 micro_hash_foreach_dep (depsingle->deps, dep, {
2119 if (!(dep->flags & (DEPENDENT_FLAGGED | DEPENDENT_CAN_RELOCATE)) &&
2120 dependent_type (dep) != DEPENDENT_DYNAMIC_DEP) {
2121 dep->flags |= DEPENDENT_FLAGGED;
2122 user->list = g_slist_prepend (user->list, dep);
2123 }});
2124 }
2125
2126 static void
2127 cb_collect_names (GnmNamedExpr *nexpr,
2128 G_GNUC_UNUSED gpointer value,
2129 GSList **l)
2130 {
2131 *l = g_slist_prepend (*l, nexpr);
2132 }
2133
2134 struct cb_remote_names {
2135 GSList *names;
2136 Workbook *wb;
2137 };
2138
2139 static void
2140 cb_remote_names1 (G_GNUC_UNUSED gconstpointer key,
2141 GnmNamedExpr *nexpr,
2142 struct cb_remote_names *data)
2143 {
2144 data->names = g_slist_prepend (data->names, nexpr);
2145 }
2146
2147 static void
2148 cb_remote_names2 (GnmNamedExpr *nexpr,
2149 G_GNUC_UNUSED gpointer value,
2150 struct cb_remote_names *data)
2151 {
2152 Workbook *wb =
2153 nexpr->pos.sheet ? nexpr->pos.sheet->workbook : nexpr->pos.wb;
2154 if (wb != data->wb)
2155 data->names = g_slist_prepend (data->names, nexpr);
2156 }
2157
2158 /*
2159 * Get a list of all names that (may) reference data in a given sheet.
2160 * This is approximated as all names in the sheet, all global names in
2161 * its workbook, and all external references that actually mention the
2162 * sheet explicitly.
2163 */
2164 static GSList *
2165 names_referencing_sheet (Sheet *sheet)
2166 {
2167 struct cb_remote_names data;
2168
2169 data.names = NULL;
2170 data.wb = sheet->workbook;
2171
2172 workbook_foreach_name (sheet->workbook, TRUE,
2173 (GHFunc)cb_remote_names1,
2174 &data);
2175 gnm_sheet_foreach_name (sheet, (GHFunc)cb_remote_names1, &data);
2176
2177 if (sheet->deps->referencing_names)
2178 g_hash_table_foreach (sheet->deps->referencing_names,
2179 (GHFunc)cb_remote_names2,
2180 &data);
2181
2182 return data.names;
2183 }
2184
2185
2186 /**
2187 * dependents_relocate:
2188 * @info: the descriptor record for what is being moved where.
2189 *
2190 * Fixes references to or from a region that is going to be moved.
2191 * Returns: (transfer full): a list of the locations and expressions that were changed outside of
2192 * the region.
2193 **/
2194 GOUndo *
2195 dependents_relocate (GnmExprRelocateInfo const *rinfo)
2196 {
2197 GnmExprRelocateInfo local_rinfo;
2198 GSList *l, *dependents = NULL, *undo_info = NULL;
2199 Sheet *sheet;
2200 GnmRange const *r;
2201 int i;
2202 CollectClosure collect;
2203 GOUndo *u_exprs, *u_names;
2204
2205 g_return_val_if_fail (rinfo != NULL, NULL);
2206
2207 /* short circuit if nothing would move */
2208 if (rinfo->col_offset == 0 && rinfo->row_offset == 0 &&
2209 rinfo->origin_sheet == rinfo->target_sheet)
2210 return NULL;
2211
2212 sheet = rinfo->origin_sheet;
2213 r = &rinfo->origin;
2214
2215 /* collect contained cells with expressions */
2216 SHEET_FOREACH_DEPENDENT (rinfo->origin_sheet, dep, {
2217 GnmCell *cell = GNM_DEP_TO_CELL (dep);
2218 if (dependent_is_cell (dep) &&
2219 range_contains (r, cell->pos.col, cell->pos.row)) {
2220 dependents = g_slist_prepend (dependents, dep);
2221 dep->flags |= DEPENDENT_FLAGGED;
2222 }
2223 });
2224
2225 /* collect the things that depend on source region */
2226 collect.target = r;
2227 collect.list = dependents;
2228 g_hash_table_foreach (sheet->deps->single_hash,
2229 (GHFunc) &cb_single_contained_collect,
2230 (gpointer)&collect);
2231 {
2232 int const first = BUCKET_OF_ROW (r->start.row);
2233 GHashTable *hash;
2234 for (i = BUCKET_OF_ROW (r->end.row); i >= first ; i--) {
2235 hash = sheet->deps->range_hash[i];
2236 if (hash != NULL)
2237 g_hash_table_foreach (hash,
2238 (GHFunc) &cb_range_contained_collect,
2239 (gpointer)&collect);
2240 }
2241 }
2242 dependents = collect.list;
2243 local_rinfo = *rinfo;
2244 for (l = dependents; l; l = l->next) {
2245 GnmExprTop const *newtree;
2246 GnmDependent *dep = l->data;
2247
2248 dep->flags &= ~DEPENDENT_FLAGGED;
2249 sheet_flag_status_update_range (dep->sheet, NULL);
2250
2251 parse_pos_init_dep (&local_rinfo.pos, dep);
2252
2253 /* it is possible nothing changed for contained deps
2254 * using absolute references */
2255 newtree = gnm_expr_top_relocate (dep->texpr, &local_rinfo, FALSE);
2256 if (newtree != NULL) {
2257 int const t = dependent_type (dep);
2258 ExprRelocateStorage *tmp =
2259 g_new (ExprRelocateStorage, 1);
2260
2261 tmp->dep_type = t;
2262 if (t == DEPENDENT_NAME) {
2263 #warning "What should we do here and why do we leak tmp?"
2264 } else {
2265 if (t == DEPENDENT_CELL)
2266 tmp->u.pos = local_rinfo.pos;
2267 else
2268 tmp->u.dep = dep;
2269 tmp->oldtree = dep->texpr;
2270 gnm_expr_top_ref (tmp->oldtree);
2271 undo_info = g_slist_prepend (undo_info, tmp);
2272
2273 dependent_set_expr (dep, newtree); /* unlinks */
2274 gnm_expr_top_unref (newtree);
2275
2276 /* queue the things that depend on the changed dep
2277 * even if it is going to move.
2278 */
2279 dependent_queue_recalc (dep);
2280
2281 /* relink if it is not going to move, if it is moving
2282 * then the caller is responsible for relinking.
2283 * This avoids a link/unlink/link tuple
2284 */
2285 if (t == DEPENDENT_CELL) {
2286 GnmCellPos const *pos = &GNM_DEP_TO_CELL (dep)->pos;
2287 if (dep->sheet != sheet ||
2288 !range_contains (r, pos->col, pos->row))
2289 dependent_link (dep);
2290 } else
2291 dependent_link (dep);
2292 }
2293 } else {
2294 /*
2295 * The expression may not be changing, but it depends
2296 * on something that is. Not-corner array cells go here
2297 * too
2298 */
2299 dependent_queue_recalc (dep);
2300 }
2301
2302 /* Not the most efficient, but probably not too bad. It is
2303 * definitely cheaper than finding the set of effected sheets. */
2304 sheet_flag_status_update_range (dep->sheet, NULL);
2305 }
2306 g_slist_free (dependents);
2307
2308 u_exprs = go_undo_unary_new (undo_info,
2309 (GOUndoUnaryFunc)dependents_unrelocate,
2310 (GFreeFunc)dependents_unrelocate_free);
2311
2312 u_names = NULL;
2313
2314 switch (rinfo->reloc_type) {
2315 case GNM_EXPR_RELOCATE_INVALIDATE_SHEET:
2316 case GNM_EXPR_RELOCATE_MOVE_RANGE:
2317 break;
2318
2319 case GNM_EXPR_RELOCATE_COLS:
2320 case GNM_EXPR_RELOCATE_ROWS: {
2321 GSList *l, *names = names_referencing_sheet (sheet);
2322 GnmExprRelocateInfo rinfo2 = *rinfo;
2323
2324 for (l = names; l; l = l->next) {
2325 GnmNamedExpr *nexpr = l->data;
2326 GnmExprTop const *newtree;
2327 rinfo2.pos = nexpr->pos;
2328 newtree = gnm_expr_top_relocate (nexpr->texpr,
2329 &rinfo2, TRUE);
2330 if (newtree) {
2331 GOUndo *u = expr_name_set_expr_undo_new (nexpr);
2332 u_names = go_undo_combine (u_names, u);
2333 expr_name_set_expr (nexpr, newtree);
2334 }
2335 }
2336 g_slist_free (names);
2337 break;
2338
2339 default:
2340 g_assert_not_reached ();
2341 }
2342 }
2343
2344 return go_undo_combine (u_exprs, u_names);
2345 }
2346
2347 /*******************************************************************/
2348
2349 static gboolean
2350 cb_collect_range (G_GNUC_UNUSED gpointer key,
2351 DependencyAny *depany,
2352 GSList **collector)
2353 {
2354 *collector = g_slist_prepend (*collector, depany);
2355 return TRUE;
2356 }
2357
2358 static void
2359 dep_hash_destroy (GHashTable *hash, GSList **dyn_deps, Sheet *sheet)
2360 {
2361 GSList *deps = NULL, *l;
2362 GnmExprRelocateInfo rinfo;
2363 GSList *deplist = NULL;
2364 gboolean destroy = (sheet->revive == NULL);
2365
2366 /* We collect first because we will be changing the hash. */
2367 if (destroy) {
2368 g_hash_table_foreach_remove (hash,
2369 (GHRFunc)cb_collect_range,
2370 &deps);
2371 g_hash_table_destroy (hash);
2372 } else {
2373 g_hash_table_foreach (hash, (GHFunc)cb_collect_range, &deps);
2374 }
2375
2376 for (l = deps; l; l = l->next) {
2377 DependencyAny *depany = l->data;
2378
2379 micro_hash_foreach_dep (depany->deps, dep, {
2380 if (dependent_type (dep) == DEPENDENT_DYNAMIC_DEP) {
2381 GnmDependent *c = ((DynamicDep *)dep)->container;
2382 if (!c->sheet->being_invalidated)
2383 *dyn_deps =
2384 g_slist_prepend (*dyn_deps, c);
2385 } else if (!dep->sheet->being_invalidated) {
2386 /*
2387 * We collect here instead of doing right away as
2388 * the dependent_set_expr below can change the
2389 * container we are looping over.
2390 */
2391 deplist = g_slist_prepend (deplist, dep);
2392 }
2393 });
2394
2395 if (destroy)
2396 micro_hash_release (&depany->deps);
2397 }
2398 g_slist_free (deps);
2399
2400 /*
2401 * We do this after the above loop as this loop will
2402 * invalidate some of the DependencyAny pointers from
2403 * above. The testcase for that is 314207, deleting
2404 * all but the first sheet in one go.
2405 */
2406 rinfo.reloc_type = GNM_EXPR_RELOCATE_INVALIDATE_SHEET;
2407 for (l = deplist; l; l = l->next) {
2408 GnmDependent *dep = l->data;
2409 GnmExprTop const *te = dep->texpr;
2410 /* We are told this dependent depends on this region, hence if
2411 * newtree is null then either
2412 * 1) we did not depend on it (ie., serious breakage )
2413 * 2) we had a duplicate reference and we have already removed it.
2414 * 3) We depended on things via a name which will be
2415 * invalidated elsewhere */
2416 GnmExprTop const *newtree = gnm_expr_top_relocate (te, &rinfo, FALSE);
2417 if (newtree != NULL) {
2418 if (sheet->revive)
2419 go_undo_group_add
2420 (sheet->revive,
2421 gnm_dep_set_expr_undo_new (dep));
2422 dependent_set_expr (dep, newtree);
2423 gnm_expr_top_unref (newtree);
2424 dependent_link (dep);
2425 }
2426 }
2427 g_slist_free (deplist);
2428 }
2429
2430 static void
2431 cb_collect_deps_of_name (GnmDependent *dep, G_GNUC_UNUSED gpointer value,
2432 GSList **accum)
2433 {
2434 /* grab unflagged linked depends */
2435 if ((dep->flags & (DEPENDENT_FLAGGED|DEPENDENT_IS_LINKED)) == DEPENDENT_IS_LINKED) {
2436 dep->flags |= DEPENDENT_FLAGGED;
2437 *accum = g_slist_prepend (*accum, dep);
2438 }
2439 }
2440
2441 struct cb_collect_deps_of_names {
2442 GSList *names;
2443 GSList *deps;
2444 };
2445
2446 static void
2447 cb_collect_deps_of_names (GnmNamedExpr *nexpr,
2448 G_GNUC_UNUSED gpointer value,
2449 struct cb_collect_deps_of_names *accum)
2450 {
2451 accum->names = g_slist_prepend (accum->names, nexpr);
2452 if (nexpr->dependents)
2453 g_hash_table_foreach (nexpr->dependents,
2454 (GHFunc)cb_collect_deps_of_name,
2455 &accum->deps);
2456 }
2457
2458 static void
2459 invalidate_name (GnmNamedExpr *nexpr, Sheet *sheet)
2460 {
2461 GnmExprTop const *old_expr = nexpr->texpr;
2462 GnmExprTop const *new_expr = NULL;
2463 gboolean scope_being_killed =
2464 nexpr->pos.sheet
2465 ? nexpr->pos.sheet->being_invalidated
2466 : nexpr->pos.wb->during_destruction;
2467
2468 if (!scope_being_killed) {
2469 GnmExprRelocateInfo rinfo;
2470 rinfo.reloc_type = GNM_EXPR_RELOCATE_INVALIDATE_SHEET;
2471 new_expr = gnm_expr_top_relocate (old_expr, &rinfo, FALSE);
2472 g_return_if_fail (new_expr != NULL);
2473 }
2474
2475 if (nexpr->dependents && g_hash_table_size (nexpr->dependents))
2476 g_warning ("Left-over name dependencies\n");
2477
2478 if (sheet->revive)
2479 go_undo_group_add (sheet->revive,
2480 expr_name_set_expr_undo_new (nexpr));
2481
2482 expr_name_set_expr (nexpr, new_expr);
2483 }
2484
2485 static void
2486 handle_dynamic_deps (GSList *dyn_deps)
2487 {
2488 GSList *ptr;
2489
2490 for (ptr = dyn_deps; ptr != NULL ; ptr = ptr->next) {
2491 GnmDependent *dep = ptr->data;
2492 if (dep->flags & DEPENDENT_HAS_DYNAMIC_DEPS) {
2493 dependent_clear_dynamic_deps (dep);
2494 dep->flags &= ~DEPENDENT_HAS_DYNAMIC_DEPS;
2495 }
2496 }
2497 dependent_queue_recalc_list (dyn_deps);
2498 g_slist_free (dyn_deps);
2499 }
2500
2501 static void
2502 handle_referencing_names (GnmDepContainer *deps, Sheet *sheet)
2503 {
2504 GSList *ptr;
2505 GHashTable *names = deps->referencing_names;
2506 struct cb_collect_deps_of_names accum;
2507 gboolean destroy = (sheet->revive == NULL);
2508
2509 if (!names)
2510 return;
2511
2512 if (destroy)
2513 deps->referencing_names = NULL;
2514
2515 accum.deps = NULL;
2516 accum.names = NULL;
2517 g_hash_table_foreach (names,
2518 (GHFunc)cb_collect_deps_of_names,
2519 (gpointer)&accum);
2520
2521 for (ptr = accum.deps; ptr; ptr = ptr->next) {
2522 GnmDependent *dep = ptr->data;
2523 dep->flags &= ~DEPENDENT_FLAGGED;
2524 dependent_unlink (dep);
2525 }
2526
2527 /* now that all of the dependents of these names are unlinked.
2528 * change the references in the names to avoid this sheet */
2529 for (ptr = accum.names; ptr; ptr = ptr->next) {
2530 GnmNamedExpr *nexpr = ptr->data;
2531 invalidate_name (nexpr, sheet);
2532 }
2533 g_slist_free (accum.names);
2534
2535 /* then relink things en-mass in case one of the deps outside
2536 * this sheet used multiple names that referenced us */
2537 dependents_link (accum.deps);
2538
2539 if (destroy) {
2540 g_slist_free (accum.deps);
2541 g_hash_table_destroy (names);
2542 } else {
2543 go_undo_group_add (sheet->revive,
2544 gnm_dep_unlink_undo_new (accum.deps));
2545 }
2546 }
2547
2548 static void
2549 handle_outgoing_references (GnmDepContainer *deps, Sheet *sheet)
2550 {
2551 GnmDependentFlags what = DEPENDENT_USES_NAME;
2552 GSList *accum = NULL;
2553
2554 what |= (sheet->workbook && sheet->workbook->during_destruction)
2555 ? DEPENDENT_GOES_INTERBOOK
2556 : DEPENDENT_GOES_INTERSHEET;
2557 DEPENDENT_CONTAINER_FOREACH_DEPENDENT (deps, dep, {
2558 if (dependent_is_linked (dep) && (dep->flags & what)) {
2559 dependent_unlink (dep);
2560 if (sheet->revive)
2561 accum = g_slist_prepend (accum, dep);
2562 }
2563 });
2564
2565 if (accum)
2566 go_undo_group_add (sheet->revive,
2567 gnm_dep_unlink_undo_new (accum));
2568 }
2569
2570 /*
2571 * do_deps_destroy:
2572 * Invalidate references of all kinds to the sheet.
2573 *
2574 * Also destroy the dependency container.
2575 */
2576 static void
2577 do_deps_destroy (Sheet *sheet)
2578 {
2579 GnmDepContainer *deps;
2580 GSList *dyn_deps = NULL;
2581 int i;
2582
2583 g_return_if_fail (IS_SHEET (sheet));
2584 g_return_if_fail (sheet->being_invalidated);
2585
2586 /* The GnmDepContainer (i.e., sheet->deps) contains the names that
2587 * reference this, not the names it contains. Remove the locally
2588 * defined names here.
2589 *
2590 * NOTE : they may continue to exist inactively for a bit. Be
2591 * careful to remove them _before_ destroying the deps. This is
2592 * a bit wasteful in that we unlink and relink a few things that
2593 * are going to be deleted. However, it is necessary to catch
2594 * all the different life cycles.
2595 */
2596 gnm_named_expr_collection_free (sheet->names);
2597 sheet->names = NULL;
2598
2599 deps = sheet->deps;
2600 if (deps == NULL)
2601 return;
2602
2603 /* Destroy the records of what depends on this sheet. There is no need
2604 * to delicately remove individual items from the lists. The only
2605 * purpose that serves is to validate the state of our data structures.
2606 * If required this optimization can be disabled for debugging.
2607 */
2608 sheet->deps = NULL;
2609 if (sheet->revive) {
2610 g_object_unref (sheet->revive);
2611 sheet->revive = NULL;
2612 }
2613
2614 for (i = deps->buckets - 1; i >= 0 ; i--) {
2615 GHashTable *hash = deps->range_hash[i];
2616 if (hash != NULL)
2617 dep_hash_destroy (hash, &dyn_deps, sheet);
2618 }
2619 dep_hash_destroy (deps->single_hash, &dyn_deps, sheet);
2620
2621 g_free (deps->range_hash);
2622 deps->range_hash = NULL;
2623 /*
2624 * Note: we have not freed the elements in the pool. This call
2625 * frees everything in one go.
2626 */
2627 go_mem_chunk_destroy (deps->range_pool, TRUE);
2628 deps->range_pool = NULL;
2629
2630 deps->single_hash = NULL;
2631 /*
2632 * Note: we have not freed the elements in the pool. This call
2633 * frees everything in one go.
2634 */
2635 go_mem_chunk_destroy (deps->single_pool, TRUE);
2636 deps->single_pool = NULL;
2637
2638 /* Now that we have tossed all deps to this sheet we can queue the
2639 * external dyn deps for recalc and free them */
2640 handle_dynamic_deps (dyn_deps);
2641
2642 g_hash_table_destroy (deps->dynamic_deps);
2643 deps->dynamic_deps = NULL;
2644
2645 handle_referencing_names (deps, sheet);
2646
2647 /* Now we remove any links from dependents in this sheet to
2648 * to other containers. If the entire workbook is going away
2649 * just look for inter-book links.
2650 */
2651 handle_outgoing_references (deps, sheet);
2652
2653 g_free (deps);
2654 }
2655
2656 /*
2657 * do_deps_invalidate:
2658 * Invalidate references of all kinds to the sheet.
2659 */
2660 static void
2661 do_deps_invalidate (Sheet *sheet)
2662 {
2663 GnmDepContainer *deps;
2664 GSList *dyn_deps = NULL;
2665 int i;
2666
2667 g_return_if_fail (IS_SHEET (sheet));
2668 g_return_if_fail (sheet->being_invalidated);
2669 g_return_if_fail (sheet->revive == NULL);
2670
2671 sheet->revive = go_undo_group_new ();
2672
2673 gnm_named_expr_collection_unlink (sheet->names);
2674
2675 deps = sheet->deps;
2676
2677 for (i = deps->buckets - 1; i >= 0 ; i--) {
2678 GHashTable *hash = deps->range_hash[i];
2679 if (hash != NULL)
2680 dep_hash_destroy (hash, &dyn_deps, sheet);
2681 }
2682 dep_hash_destroy (deps->single_hash, &dyn_deps, sheet);
2683
2684 /* Now that we have tossed all deps to this sheet we can queue the
2685 * external dyn deps for recalc and free them */
2686 handle_dynamic_deps (dyn_deps);
2687
2688 handle_referencing_names (deps, sheet);
2689
2690 /* Now we remove any links from dependents in this sheet to
2691 * to other containers. If the entire workbook is going away
2692 * just look for inter-book links.
2693 */
2694 handle_outgoing_references (deps, sheet);
2695 }
2696
2697 static void
2698 cb_tweak_3d (GnmDependent *dep, G_GNUC_UNUSED gpointer value, GSList **deps)
2699 {
2700 *deps = g_slist_prepend (*deps, dep);
2701 }
2702
2703 static void
2704 tweak_3d (Sheet *sheet)
2705 {
2706 Workbook *wb = sheet->workbook;
2707 GSList *deps = NULL, *l;
2708 GnmExprRelocateInfo rinfo;
2709
2710 if (!wb->sheet_order_dependents)
2711 return;
2712
2713 g_hash_table_foreach (wb->sheet_order_dependents,
2714 (GHFunc)cb_tweak_3d,
2715 &deps);
2716
2717 rinfo.reloc_type = GNM_EXPR_RELOCATE_INVALIDATE_SHEET;
2718 for (l = deps; l; l = l->next) {
2719 GnmDependent *dep = l->data;
2720 GnmExprTop const *te = dep->texpr;
2721 GnmExprTop const *newtree = gnm_expr_top_relocate (te, &rinfo, FALSE);
2722
2723 if (newtree != NULL) {
2724 if (sheet->revive)
2725 go_undo_group_add
2726 (sheet->revive,
2727 gnm_dep_set_expr_undo_new (dep));
2728 dependent_set_expr (dep, newtree);
2729 gnm_expr_top_unref (newtree);
2730 dependent_link (dep);
2731 dependent_changed (dep);
2732 }
2733 }
2734 g_slist_free (deps);
2735 }
2736
2737 static void
2738 dependents_invalidate_sheets (GSList *sheets, gboolean destroy)
2739 {
2740 GSList *tmp;
2741 Workbook *last_wb;
2742
2743 /* Mark all first. */
2744 for (tmp = sheets; tmp; tmp = tmp->next) {
2745 Sheet *sheet = tmp->data;
2746 sheet->being_invalidated = TRUE;
2747 }
2748
2749 /*
2750 * Fixup 3d refs that start or end on one of these sheets.
2751 * Ideally we do this one per workbook, but that is not critical
2752 * so we are not going to outright sort the sheet list.
2753 */
2754 last_wb = NULL;
2755 for (tmp = sheets; tmp; tmp = tmp->next) {
2756 Sheet *sheet = tmp->data;
2757 Workbook *wb = sheet->workbook;
2758
2759 if (wb != last_wb)
2760 tweak_3d (sheet);
2761 last_wb = wb;
2762 }
2763
2764 /* Now invalidate. */
2765 for (tmp = sheets; tmp; tmp = tmp->next) {
2766 Sheet *sheet = tmp->data;
2767 if (destroy)
2768 do_deps_destroy (sheet);
2769 else
2770 do_deps_invalidate (sheet);
2771 }
2772
2773 /* Unmark. */
2774 for (tmp = sheets; tmp; tmp = tmp->next) {
2775 Sheet *sheet = tmp->data;
2776 sheet->being_invalidated = FALSE;
2777 }
2778 }
2779
2780 void
2781 dependents_invalidate_sheet (Sheet *sheet, gboolean destroy)
2782 {
2783 GSList l;
2784
2785 g_return_if_fail (IS_SHEET (sheet));
2786
2787 l.next = NULL;
2788 l.data = sheet;
2789 dependents_invalidate_sheets (&l, destroy);
2790 }
2791
2792 void
2793 dependents_workbook_destroy (Workbook *wb)
2794 {
2795 g_return_if_fail (GNM_IS_WORKBOOK (wb));
2796 g_return_if_fail (wb->during_destruction);
2797 g_return_if_fail (wb->sheets != NULL);
2798
2799 /* Mark all first. */
2800 WORKBOOK_FOREACH_SHEET (wb, sheet, sheet->being_invalidated = TRUE;);
2801
2802 /* Kill 3d deps and workbook-level names, if needed. */
2803 if (wb->sheet_order_dependents) {
2804 g_hash_table_destroy (wb->sheet_order_dependents);
2805 wb->sheet_order_dependents = NULL;
2806 }
2807 gnm_named_expr_collection_free (wb->names);
2808 wb->names = NULL;
2809
2810 WORKBOOK_FOREACH_SHEET (wb, sheet, do_deps_destroy (sheet););
2811
2812 /* Unmark. */
2813 WORKBOOK_FOREACH_SHEET (wb, sheet, sheet->being_invalidated = FALSE;);
2814 }
2815
2816 /*
2817 * dependents_revive_sheet:
2818 * Undo the effects of dependents_invalidate_sheet (sheet, FALSE).
2819 */
2820 void
2821 dependents_revive_sheet (Sheet *sheet)
2822 {
2823 go_undo_undo (GO_UNDO (sheet->revive));
2824 g_object_unref (sheet->revive);
2825 sheet->revive = NULL;
2826
2827 /* Re-link local names. */
2828 gnm_named_expr_collection_relink (sheet->names);
2829
2830 gnm_dep_container_sanity_check (sheet->deps);
2831 }
2832
2833 void
2834 workbook_queue_all_recalc (Workbook *wb)
2835 {
2836 /* FIXME: what about dependents in other workbooks? */
2837 WORKBOOK_FOREACH_DEPENDENT (wb, dep, dependent_flag_recalc (dep););
2838 }
2839
2840 void
2841 workbook_queue_volatile_recalc (Workbook *wb)
2842 {
2843 WORKBOOK_FOREACH_DEPENDENT (wb, dep, {
2844 if (dependent_is_volatile (dep))
2845 dependent_flag_recalc (dep);
2846 });
2847 }
2848
2849
2850 /**
2851 * workbook_recalc:
2852 * @wb:
2853 *
2854 * Computes all dependents in @wb that have been flaged as requiring
2855 * recomputation.
2856 *
2857 * NOTE! This does not recalc dependents in other workbooks.
2858 */
2859 void
2860 workbook_recalc (Workbook *wb)
2861 {
2862 gboolean redraw = FALSE;
2863
2864 g_return_if_fail (GNM_IS_WORKBOOK (wb));
2865
2866 gnm_app_recalc_start ();
2867
2868 WORKBOOK_FOREACH_DEPENDENT (wb, dep, {
2869 if (dependent_needs_recalc (dep)) {
2870 redraw = TRUE;
2871 dependent_eval (dep);
2872 }
2873 });
2874
2875 gnm_app_recalc_finish ();
2876
2877 /*
2878 * This is a bit of a band-aid. If anything is recalculated, we
2879 * force a full redraw. The alternative is to ask for updates
2880 * of every cell that is changed and that is probably more
2881 * expensive.
2882 */
2883 if (redraw) {
2884 WORKBOOK_FOREACH_SHEET (wb, sheet, {
2885 SHEET_FOREACH_VIEW (sheet, sv, gnm_sheet_view_flag_selection_change (sv););
2886 sheet_redraw_all (sheet, FALSE);});
2887 }
2888 }
2889
2890 /**
2891 * workbook_recalc_all:
2892 * @wb:
2893 *
2894 * Queues all dependents for recalc and recalculates.
2895 */
2896 void
2897 workbook_recalc_all (Workbook *wb)
2898 {
2899 workbook_queue_all_recalc (wb);
2900
2901 /* Recalculate this workbook unconditionally. */
2902 workbook_recalc (wb);
2903
2904 /* Recalculate other workbooks when needed. */
2905 gnm_app_recalc ();
2906
2907 WORKBOOK_FOREACH_VIEW (wb, view,
2908 sheet_update (wb_view_cur_sheet (view)););
2909 }
2910
2911 static void
2912 dynamic_dep_free (DynamicDep *dyn)
2913 {
2914 GnmDependent *dep = dyn->container;
2915 GnmCellPos const *pos = dependent_pos (dep);
2916 GnmRangeRef *rr;
2917 GSList *ptr;
2918
2919 for (ptr = dyn->singles ; ptr != NULL ; ptr = ptr->next) {
2920 rr = ptr->data;
2921 unlink_single_dep (&dyn->base, pos, &rr->a);
2922 g_free (rr);
2923 }
2924 g_slist_free (dyn->singles);
2925 dyn->singles = NULL;
2926
2927 for (ptr = dyn->ranges ; ptr != NULL ; ptr = ptr->next) {
2928 rr = ptr->data;
2929 link_unlink_cellrange_dep (&dyn->base, pos,
2930 &rr->a, &rr->b, FALSE);
2931 g_free (rr);
2932 }
2933 g_slist_free (dyn->ranges);
2934 dyn->ranges = NULL;
2935
2936 if (dyn->base.flags & DEPENDENT_HAS_3D)
2937 workbook_unlink_3d_dep (&dyn->base);
2938 g_free (dyn);
2939 }
2940
2941
2942 gboolean
2943 dependent_is_volatile (GnmDependent *dep)
2944 {
2945 /* This might need to be a virtual call. */
2946 return dep->texpr && gnm_expr_top_is_volatile (dep->texpr);
2947 }
2948
2949 /**
2950 * gnm_dep_container_new: (skip)
2951 * @sheet: #Sheet
2952 *
2953 * Returns: (transfer full):
2954 **/
2955 GnmDepContainer *
2956 gnm_dep_container_new (Sheet *sheet)
2957 {
2958 GnmDepContainer *deps = g_new (GnmDepContainer, 1);
2959
2960 deps->head = deps->tail = NULL;
2961
2962 deps->buckets = 1 + BUCKET_OF_ROW (gnm_sheet_get_last_row (sheet));
2963 deps->range_hash = g_new0 (GHashTable *, deps->buckets);
2964 deps->range_pool = go_mem_chunk_new ("range pool",
2965 sizeof (DependencyRange),
2966 16 * 1024 - 100);
2967 deps->single_hash = g_hash_table_new ((GHashFunc) depsingle_hash,
2968 (GEqualFunc) depsingle_equal);
2969 deps->single_pool = go_mem_chunk_new ("single pool",
2970 sizeof (DependencySingle),
2971 16 * 1024 - 100);
2972 deps->referencing_names = g_hash_table_new (g_direct_hash,
2973 g_direct_equal);
2974
2975 deps->dynamic_deps = g_hash_table_new_full (g_direct_hash, g_direct_equal,
2976 NULL, (GDestroyNotify) dynamic_dep_free);
2977
2978 return deps;
2979 }
2980
2981 void
2982 gnm_dep_container_resize (GnmDepContainer *deps, int rows)
2983 {
2984 int i, buckets = 1 + BUCKET_OF_ROW (rows - 1);
2985
2986 for (i = buckets; i < deps->buckets; i++) {
2987 GHashTable *hash = deps->range_hash[i];
2988 if (hash != NULL) {
2989 int s = g_hash_table_size (hash);
2990 if (s)
2991 g_printerr ("Hash table size: %d\n", s);
2992 g_hash_table_destroy (hash);
2993 deps->range_hash[i] = NULL;
2994 }
2995 }
2996
2997 deps->range_hash = g_renew (GHashTable *, deps->range_hash, buckets);
2998
2999 for (i = deps->buckets; i < buckets; i++)
3000 deps->range_hash[i] = NULL;
3001
3002 deps->buckets = buckets;
3003 }
3004
3005 /****************************************************************************
3006 * Debug utils
3007 */
3008
3009 static void
3010 dependent_debug_name_for_sheet (GnmDependent const *dep, Sheet *sheet,
3011 GString *target)
3012 {
3013 int t;
3014 GnmDependentClass *klass;
3015
3016 g_return_if_fail (dep != NULL);
3017 g_return_if_fail (dep_classes);
3018
3019 if (!dep->sheet)
3020 g_warning ("Invalid dep, missing sheet");
3021
3022 if (sheet == dep->sheet) {
3023 /* Nothing */
3024 } else {
3025 g_string_append (target,
3026 dep->sheet ? dep->sheet->name_quoted : "?");
3027 g_string_append_c (target, '!');
3028 }
3029
3030 t = dependent_type (dep);
3031 klass = g_ptr_array_index (dep_classes, t);
3032 klass->debug_name (dep, target);
3033 }
3034
3035
3036 /**
3037 * dependent_debug_name:
3038 * @dep: The dependent we are interested in.
3039 *
3040 * A useful little debugging utility.
3041 */
3042 void
3043 dependent_debug_name (GnmDependent const *dep, GString *target)
3044 {
3045 dependent_debug_name_for_sheet (dep, NULL, target);
3046 }
3047
3048
3049 static void
3050 dump_range_dep (gpointer key, G_GNUC_UNUSED gpointer value, gpointer sheet_)
3051 {
3052 DependencyRange const *deprange = key;
3053 GnmRange const *range = &(deprange->range);
3054 Sheet *sheet = sheet_;
3055 GString *target = g_string_sized_new (10000);
3056 gboolean first = TRUE;
3057
3058 g_string_append (target, " ");
3059 g_string_append (target, range_as_string (range));
3060 g_string_append (target, " -> (");
3061
3062 micro_hash_foreach_dep (deprange->deps, dep, {
3063 if (first)
3064 first = FALSE;
3065 else
3066 g_string_append (target, ", ");
3067 dependent_debug_name_for_sheet (dep, sheet, target);
3068 });
3069 g_string_append_c (target, ')');
3070
3071 g_printerr ("%s\n", target->str);
3072 g_string_free (target, TRUE);
3073 }
3074
3075 static void
3076 dump_single_dep (gpointer key, G_GNUC_UNUSED gpointer value, gpointer sheet_)
3077 {
3078 DependencySingle *depsingle = key;
3079 Sheet *sheet = sheet_;
3080 GString *target = g_string_sized_new (10000);
3081 gboolean first = TRUE;
3082
3083 g_string_append (target, " ");
3084 g_string_append (target, cellpos_as_string (&depsingle->pos));
3085 g_string_append (target, " -> ");
3086
3087 micro_hash_foreach_dep (depsingle->deps, dep, {
3088 if (first)
3089 first = FALSE;
3090 else
3091 g_string_append (target, ", ");
3092 dependent_debug_name_for_sheet (dep, sheet, target);
3093 });
3094
3095 g_printerr ("%s\n", target->str);
3096 g_string_free (target, TRUE);
3097 }
3098
3099 static void
3100 dump_dynamic_dep (gpointer key, G_GNUC_UNUSED gpointer value,
3101 G_GNUC_UNUSED gpointer closure)
3102 {
3103 GnmDependent *dep = key;
3104 DynamicDep *dyn = value;
3105 GSList *l;
3106 GnmParsePos pp;
3107 GnmConventionsOut out;
3108
3109 out.accum = g_string_new (NULL);
3110 out.pp = &pp;
3111 out.convs = gnm_conventions_default;
3112
3113 pp.wb = dep->sheet->workbook;
3114 pp.sheet = dep->sheet;
3115 pp.eval = *dependent_pos (dyn->container);
3116
3117 g_string_append (out.accum, " ");
3118 dependent_debug_name (dep, out.accum);
3119 g_string_append (out.accum, " -> ");
3120 dependent_debug_name (&dyn->base, out.accum);
3121 g_string_append (out.accum, " { c=");
3122 dependent_debug_name (dyn->container, out.accum);
3123
3124 g_string_append (out.accum, ", s=[");
3125 for (l = dyn->singles; l; l = l->next) {
3126 rangeref_as_string (&out, l->data);
3127 if (l->next)
3128 g_string_append (out.accum, ", ");
3129 }
3130
3131 g_string_append (out.accum, "], r=[");
3132 for (l = dyn->ranges; l; l = l->next) {
3133 rangeref_as_string (&out, l->data);
3134 if (l->next)
3135 g_string_append (out.accum, ", ");
3136 }
3137
3138 g_string_append (out.accum, "] }");
3139 g_printerr ("%s\n", out.accum->str);
3140 g_string_free (out.accum, TRUE);
3141 }
3142
3143 /**
3144 * gnm_dep_container_dump:
3145 * @deps:
3146 *
3147 * A useful utility for checking the state of the dependency data structures.
3148 */
3149 void
3150 gnm_dep_container_dump (GnmDepContainer const *deps,
3151 Sheet *sheet)
3152 {
3153 int i;
3154
3155 g_return_if_fail (deps != NULL);
3156
3157 gnm_dep_container_sanity_check (deps);
3158
3159 for (i = deps->buckets - 1; i >= 0 ; i--) {
3160 GHashTable *hash = deps->range_hash[i];
3161 if (hash != NULL && g_hash_table_size (hash) > 0) {
3162 g_printerr (" Bucket %d (rows %d-%d): Range hash size %d: range over which cells in list depend\n",
3163 i,
3164 BUCKET_START_ROW (i) + 1,
3165 BUCKET_END_ROW (i) + 1,
3166 g_hash_table_size (hash));
3167 g_hash_table_foreach (hash,
3168 dump_range_dep,
3169 sheet);
3170 }
3171 }
3172
3173 if (deps->single_hash && g_hash_table_size (deps->single_hash) > 0) {
3174 g_printerr (" Single hash size %d: cell on which list of cells depend\n",
3175 g_hash_table_size (deps->single_hash));
3176 g_hash_table_foreach (deps->single_hash,
3177 dump_single_dep,
3178 sheet);
3179 }
3180
3181 if (deps->dynamic_deps && g_hash_table_size (deps->dynamic_deps) > 0) {
3182 g_printerr (" Dynamic hash size %d: cells that depend on dynamic dependencies\n",
3183 g_hash_table_size (deps->dynamic_deps));
3184 g_hash_table_foreach (deps->dynamic_deps,
3185 dump_dynamic_dep, NULL);
3186 }
3187
3188 if (deps->referencing_names && g_hash_table_size (deps->referencing_names) > 0) {
3189 GSList *l, *names = NULL;
3190
3191 g_hash_table_foreach (deps->referencing_names,
3192 (GHFunc)cb_collect_names,
3193 &names);
3194
3195 g_printerr (" Names whose expressions explicitly reference this sheet\n ");
3196 for (l = names; l; l = l->next) {
3197 GnmNamedExpr *nexpr = l->data;
3198 g_printerr ("%s%s",
3199 expr_name_name (nexpr),
3200 l->next ? ", " : "\n");
3201 }
3202 g_slist_free (names);
3203 }
3204 }
3205
3206 void
3207 dependents_dump (Workbook *wb)
3208 {
3209 WORKBOOK_FOREACH_SHEET
3210 (wb, sheet,
3211 {
3212 int count = 0;
3213 SHEET_FOREACH_DEPENDENT (sheet, dep, count++;);
3214 g_printerr ("Dependencies for %s (count=%d):\n",
3215 sheet->name_unquoted, count);
3216 gnm_dep_container_dump (sheet->deps, sheet);
3217 });
3218 }
3219
3220 void
3221 gnm_dep_container_sanity_check (GnmDepContainer const *deps)
3222 {
3223 GnmDependent const *dep;
3224 GHashTable *seenb4;
3225
3226 if (deps->head && !deps->tail)
3227 g_warning ("Dependency container %p has head, but no tail.", (void *)deps);
3228 if (deps->tail && !deps->head)
3229 g_warning ("Dependency container %p has tail, but no head.", (void *)deps);
3230 if (deps->head && deps->head->prev_dep)
3231 g_warning ("Dependency container %p has head, but not at the beginning.", (void *)deps);
3232 if (deps->tail && deps->tail->next_dep)
3233 g_warning ("Dependency container %p has tail, but not at the end.", (void *)deps);
3234
3235 seenb4 = g_hash_table_new (g_direct_hash, g_direct_equal);
3236 for (dep = deps->head; dep; dep = dep->next_dep) {
3237 if (dep->prev_dep && (dep->prev_dep->next_dep != dep))
3238 g_warning ("Dependency container %p has left double-link failure at %p.", (void *)deps, (void *)dep);
3239 if (dep->next_dep && (dep->next_dep->prev_dep != dep))
3240 g_warning ("Dependency container %p has right double-link failure at %p.", (void *)deps, (void *)dep);
3241 if (!dep->next_dep && dep != deps->tail)
3242 g_warning ("Dependency container %p ends before its tail.", (void *)deps);
3243 if (!dependent_is_linked (dep))
3244 g_warning ("Dependency container %p contains unlinked dependency %p.", (void *)deps, (void *)dep);
3245 if (g_hash_table_lookup (seenb4, dep)) {
3246 g_warning ("Dependency container %p is circular.", (void *)deps);
3247 break;
3248 }
3249 g_hash_table_insert (seenb4, (gpointer)dep, (gpointer)dep);
3250 }
3251 g_hash_table_destroy (seenb4);
3252 }
3253
3254 /* ------------------------------------------------------------------------- */
gnumeric mirror