1 /* Links between top-level syms and the exprs which reference them
2 */
3
4 /*
5
6 Copyright (C) 1991-2003 The National Gallery
7
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License along
19 with this program; if not, write to the Free Software Foundation, Inc.,
20 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21
22 */
23
24 /*
25
26 These files are distributed with VIPS - http://www.vips.ecs.soton.ac.uk
27
28 */
29
30 /*
31 #define DEBUG
32 #define DEBUG_DIRTY
33 */
34
35 #include "ip.h"
36
37 void *
link_expr_destroy(LinkExpr * le)38 link_expr_destroy( LinkExpr *le )
39 {
40 GSList **llinks = le->dynamic ? &le->link->dynamic_links :
41 &le->link->static_links;
42 GSList **elinks = le->dynamic ? &le->expr->dynamic_links :
43 &le->expr->static_links;
44
45 #ifdef DEBUG
46 printf( "link_expr_destroy: removing expr " );
47 symbol_name_print( le->expr->sym );
48 printf( "referencing link->child = " );
49 symbol_name_print( le->link->child );
50 printf( "\n" );
51 #endif /*DEBUG*/
52
53 *llinks = slist_remove_all( *llinks, le );
54 *elinks = slist_remove_all( *elinks, le );
55
56 im_free( le );
57
58 return( NULL );
59 }
60
61 static LinkExpr *
link_expr_new(Link * link,Expr * expr,gboolean dynamic)62 link_expr_new( Link *link, Expr *expr, gboolean dynamic )
63 {
64 GSList **llinks = dynamic ? &link->dynamic_links : &link->static_links;
65 GSList **elinks = dynamic ? &expr->dynamic_links : &expr->static_links;
66 LinkExpr *le;
67
68 g_assert( expr_get_root_dynamic( expr )->sym == link->parent );
69
70 #ifdef DEBUG
71 printf( "link_expr_new: expr " );
72 symbol_name_print( expr->sym );
73 printf( "references link->child = " );
74 symbol_name_print( link->child );
75 printf( "\n" );
76 #endif /*DEBUG*/
77
78 if( !(le = INEW( NULL, LinkExpr )) )
79 return( NULL );
80
81 le->link = link;
82 le->expr = expr;
83 le->count = 1;
84 le->dynamic = dynamic;
85
86 *llinks = g_slist_prepend( *llinks, le );
87 *elinks = g_slist_prepend( *elinks, le );
88
89 return( le );
90 }
91
92 /* Make a new serial number.
93 */
94 int
link_serial_new(void)95 link_serial_new( void )
96 {
97 static int serial = 0;
98
99 return( serial++ );
100 }
101
102 /* Fwd ref.
103 */
104 static void *symbol_dirty_set( Symbol *sym );
105
106 /* child has become dirty ... update parent's dirty count.
107 */
108 static void *
link_dirty_child(Link * link)109 link_dirty_child( Link *link )
110 {
111 g_assert( link->parent->ndirtychildren >= 0 );
112
113 link->parent->ndirtychildren += 1;
114
115 if( link->parent->ndirtychildren == 1 )
116 /* Parent had no dirty children ... it does now.
117 */
118 symbol_dirty_set( link->parent );
119
120 symbol_state_change( link->parent );
121
122 return( NULL );
123 }
124
125 /* link->parent no longer has link->child as a dirty child (cleaned or
126 * removed) ... update counts.
127 */
128 static void *
link_clean_child(Link * link)129 link_clean_child( Link *link )
130 {
131 Symbol *parent = link->parent;
132
133 /* One fewer dirty children!
134 */
135 parent->ndirtychildren--;
136 g_assert( parent->ndirtychildren >= 0 );
137
138 /* Have we just cleaned the last dirty child of link->parent? If we
139 * have and if link->parent has an error, clear the error so that
140 * link->parent gets a chance to recalc. The new value of
141 * link->child might fix the problem.
142 */
143 if( parent->ndirtychildren == 0 )
144 expr_error_clear( parent->expr );
145
146 symbol_state_change( parent );
147
148 return( NULL );
149 }
150
151 /* Junk a link.
152 */
153 void *
link_destroy(Link * link)154 link_destroy( Link *link )
155 {
156 #ifdef DEBUG
157 printf( "link_destroy: destroying link from " );
158 symbol_name_print( link->parent );
159 printf( "to " );
160 symbol_name_print( link->child );
161 printf( "\n" );
162 #endif /*DEBUG*/
163
164 if( link->child->dirty )
165 (void) link_clean_child( link );
166
167 link->parent->topchildren =
168 slist_remove_all( link->parent->topchildren, link );
169 link->child->topparents =
170 slist_remove_all( link->child->topparents, link );
171 slist_map( link->static_links,
172 (SListMapFn) link_expr_destroy, NULL );
173 slist_map( link->dynamic_links,
174 (SListMapFn) link_expr_destroy, NULL );
175
176 im_free( link );
177
178 return( NULL );
179 }
180
181 /* Make a new link.
182 */
183 static Link *
link_new(Symbol * child,Symbol * parent)184 link_new( Symbol *child, Symbol *parent )
185 {
186 Link *link;
187
188 g_assert( is_top( parent ) && is_top( child ) );
189 g_assert( parent != child );
190
191 #ifdef DEBUG
192 printf( "link_new: making link from " );
193 symbol_name_print( parent );
194 printf( "to " );
195 symbol_name_print( child );
196 printf( "\n" );
197 #endif /*DEBUG*/
198
199 if( !(link = INEW( NULL, Link )) )
200 return( NULL );
201
202 link->parent = parent;
203 link->child = child;
204 link->serial = 0;
205 link->static_links = NULL;
206 link->dynamic_links = NULL;
207
208 parent->topchildren = g_slist_prepend( parent->topchildren, link );
209 child->topparents = g_slist_prepend( child->topparents, link );
210
211 /* If the new child is dirty, note it.
212 */
213 if( child->dirty )
214 link_dirty_child( link );
215
216 return( link );
217 }
218
219 static Link *
link_find_child_sub(Link * link,Symbol * child)220 link_find_child_sub( Link *link, Symbol *child )
221 {
222 if( link->child == child )
223 return( link );
224
225 return( NULL );
226 }
227
228 /* Look up connection between child and parent.
229 */
230 static Link *
link_find_child(Symbol * child,Symbol * parent)231 link_find_child( Symbol *child, Symbol *parent )
232 {
233 return( (Link *) slist_map( parent->topchildren,
234 (SListMapFn) link_find_child_sub, child ) );
235 }
236
237 static void *
link_expr_find_expr_sub(LinkExpr * le,Expr * expr)238 link_expr_find_expr_sub( LinkExpr *le, Expr *expr )
239 {
240 if( le->expr == expr )
241 return( le );
242
243 return( NULL );
244 }
245
246 /* Look up a linkexpr by expr.
247 */
248 static LinkExpr *
link_expr_find_expr(Link * link,Expr * expr,gboolean dynamic)249 link_expr_find_expr( Link *link, Expr *expr, gboolean dynamic )
250 {
251 GSList *links = dynamic ? link->dynamic_links : link->static_links;
252
253 return( (LinkExpr *) slist_map( links,
254 (SListMapFn) link_expr_find_expr_sub, expr ) );
255 }
256
257 /* Add a reference from expr to child to the link graph.
258 */
259 void *
link_add(Symbol * child,Expr * expr,gboolean dynamic)260 link_add( Symbol *child, Expr *expr, gboolean dynamic )
261 {
262 Expr *parent = expr_get_root_dynamic( expr );
263 Link *link;
264 LinkExpr *le;
265
266 #ifdef DEBUG
267 printf( "link_add: child = " );
268 symbol_name_print( child );
269 printf( "; expr = " );
270 expr_name_print( expr );
271 printf( "; dynamic = %s\n", bool_to_char( dynamic ) );
272 #endif /*DEBUG*/
273
274 g_assert( parent );
275 g_assert( parent->sym );
276 g_assert( is_top( child ) && is_top( parent->sym ) );
277 g_assert( child != parent->sym );
278
279 if( !(link = link_find_child( child, parent->sym )) ) {
280 if( !(link = link_new( child, parent->sym )) )
281 return( child );
282 }
283
284 if( !(le = link_expr_find_expr( link, expr, dynamic )) ) {
285 if( !(le = link_expr_new( link, expr, dynamic )) )
286 return( child );
287 }
288 else
289 le->count++;
290
291 return( NULL );
292 }
293
294 /* Remove a ref from expr to child.
295 */
296 void *
link_remove(Symbol * child,Expr * expr,gboolean dynamic)297 link_remove( Symbol *child, Expr *expr, gboolean dynamic )
298 {
299 Symbol *parent = expr_get_root_dynamic( expr )->sym;
300 Link *link = link_find_child( child, parent );
301 LinkExpr *le = link_expr_find_expr( link, expr, dynamic );
302
303 g_assert( is_top( parent ) && is_top( child ) );
304 g_assert( parent != child );
305 g_assert( link );
306
307 le->count--;
308 if( le->count == 0 ) {
309 if( link_expr_destroy( le ) )
310 return( child );
311 }
312 if( !link->static_links && !link->dynamic_links ) {
313 if( link_destroy( link ) )
314 return( child );
315 }
316
317 return( NULL );
318 }
319
320 /* Is this a ref to a top-level? Add to link graph if it is.
321 */
322 static void *
link_children_expr_sub(Symbol * child,Expr * expr)323 link_children_expr_sub( Symbol *child, Expr *expr )
324 {
325 if( is_top( child ) ) {
326 Expr *root = expr_get_root_dynamic( expr );
327
328 /* Don't need to record recursive refs.
329 */
330 if( root && root->sym && root->sym != child ) {
331 if( link_add( child, expr, FALSE ) )
332 return( child );
333 }
334 }
335
336 return( NULL );
337 }
338
339 /* Fwd.
340 */
341 static void *link_children( Symbol *child, Symbol *parent );
342
343 /* Add any refs to top-level syms within this local to the
344 * top-level sym we are within.
345 */
346 static void *
link_children_expr(Expr * expr,Symbol * parent)347 link_children_expr( Expr *expr, Symbol *parent )
348 {
349 if( expr->compile ) {
350 Compile *compile = expr->compile;
351
352 /* Add refs which local makes directly.
353 */
354 if( slist_map( compile->children,
355 (SListMapFn) link_children_expr_sub, expr ) )
356 return( expr );
357
358 /* ... and recurse for sub-children.
359 */
360 (void) icontainer_map( ICONTAINER( compile ),
361 (icontainer_map_fn) link_children, parent, NULL );
362 }
363
364 return( NULL );
365 }
366
367 /* Add any refs to top-level syms within this local to the
368 * top-level sym we are within.
369 */
370 static void *
link_children(Symbol * child,Symbol * parent)371 link_children( Symbol *child, Symbol *parent )
372 {
373 if( child->expr ) {
374 if( link_children_expr( child->expr, parent ) )
375 return( child );
376 }
377
378 return( NULL );
379 }
380
381 /* row is editing sym's value ... add any dependancies the user has included
382 * there.
383 */
384 static void *
link_row(Model * model,Symbol * parent)385 link_row( Model *model, Symbol *parent )
386 {
387 if( !IS_ROW( model ) || !ROW( model )->expr )
388 return( NULL );
389
390 /* Add any stuff in this row.
391 */
392 return( link_children_expr( ROW( model )->expr, parent ) );
393 }
394
395 static void *
symbol_ndirty_sub(Link * link,int * nd)396 symbol_ndirty_sub( Link *link, int *nd )
397 {
398 if( link->child->dirty )
399 *nd += 1;
400
401 return( NULL );
402 }
403
404 /* Count the number of dirty children. Used to generate initial leaf counts
405 * and for assert() checking.
406 */
407 int
symbol_ndirty(Symbol * sym)408 symbol_ndirty( Symbol *sym )
409 {
410 int nd = 0;
411
412 (void) slist_map( sym->topchildren,
413 (SListMapFn) symbol_ndirty_sub, &nd );
414
415 return( nd );
416 }
417
418 /* Fix a leaf count.
419 */
420 void *
symbol_fix_counts(Symbol * sym)421 symbol_fix_counts( Symbol *sym )
422 {
423 #ifdef DEBUG
424 int old_count = sym->ndirtychildren;
425 #endif /*DEBUG*/
426
427 sym->ndirtychildren = symbol_ndirty( sym );
428
429 #ifdef DEBUG
430 g_assert( sym->ndirtychildren == old_count );
431 #endif /*DEBUG*/
432
433 symbol_state_change( sym );
434
435 return( NULL );
436 }
437
438 /* Junk all old links, static + dynamic.
439 */
440 void
symbol_link_destroy(Symbol * sym)441 symbol_link_destroy( Symbol *sym )
442 {
443 (void) slist_map( sym->topchildren, (SListMapFn) link_destroy, NULL );
444 }
445
446 /* Scan a symbol, remaking all the links.
447 */
448 void
symbol_link_build(Symbol * sym)449 symbol_link_build( Symbol *sym )
450 {
451 g_assert( is_top( sym ) );
452
453 /* Make static links for our expr and all subexprs. If this symbol
454 * is being edited, get stuff from the edited value.
455 */
456 if( sym->expr ) {
457 if( sym->expr->row )
458 (void) icontainer_map_all(
459 ICONTAINER( sym->expr->row ),
460 (icontainer_map_fn) link_row, sym );
461 else
462 (void) link_children_expr( sym->expr, sym );
463 }
464
465 #ifdef DEBUG
466 printf( "symbol_link_build: " );
467 symbol_name_print( sym );
468 printf( "\n" );
469 dump_links( sym );
470 #endif /*DEBUG*/
471
472 }
473
474 static void *
link_dirty_set_sub(LinkExpr * le,int serial)475 link_dirty_set_sub( LinkExpr *le, int serial )
476 {
477 return( expr_dirty( le->expr, serial ) );
478 }
479
480 /* Mark exprs in parent dirty. These may be sub exprs, so parent is not
481 * necessarily going to be symbol_dirty_set() ... eg. A2 may be displaying an
482 * instance of class "fred", and we might have edited one of A2's members to
483 * refer to A1 ... but A2 depends on A1, fred does not.
484 */
485 static void *
link_dirty_set(Link * link,int serial)486 link_dirty_set( Link *link, int serial )
487 {
488 /* Mark exprs in parent dirty.
489 */
490 if( slist_map( link->static_links,
491 (SListMapFn) link_dirty_set_sub, GINT_TO_POINTER( serial ) ) ||
492 slist_map( link->dynamic_links,
493 (SListMapFn) link_dirty_set_sub, GINT_TO_POINTER( serial ) ) )
494 return( link );
495
496 return( NULL );
497 }
498
499 /* Walk the link graph, marking stuff for recomputation ... link->child has
500 * changed, mark link->parent dirty.
501 */
502 static void *
link_dirty_walk(Link * link,int serial)503 link_dirty_walk( Link *link, int serial )
504 {
505 /* Have we walked down this link before?
506 */
507 if( link->serial == serial )
508 return( NULL );
509 link->serial = serial;
510
511 /* Mark all exprs in parent dirty.
512 */
513 return( link_dirty_set( link, serial ) );
514 }
515
516 /* A symbol has changed ... walk the link graph, marking stuff dirty as
517 * required. We don't mark this sym dirty.
518 */
519 void *
symbol_dirty_intrans(Symbol * sym,int serial)520 symbol_dirty_intrans( Symbol *sym, int serial )
521 {
522 g_assert( is_top( sym ) );
523
524 return( slist_map( sym->topparents,
525 (SListMapFn) link_dirty_walk, GINT_TO_POINTER( serial ) ) );
526 }
527
528 static void *
symbol_dirty_set(Symbol * sym)529 symbol_dirty_set( Symbol *sym )
530 {
531 g_assert( is_top( sym ) );
532
533 /* Clear error, to make sure we will recomp it.
534 */
535 if( sym->expr )
536 expr_error_clear( sym->expr );
537
538 if( !sym->dirty ) {
539 #ifdef DEBUG_DIRTY
540 printf( "symbol_dirty_set: " );
541 symbol_name_print( sym );
542 printf( "(%p)\n", sym );
543 #endif /*DEBUG_DIRTY*/
544
545 /* Change of state.
546 */
547 sym->dirty = TRUE;
548
549 /* Update dirty counts on our parents.
550 */
551 (void) slist_map( sym->topparents,
552 (SListMapFn) link_dirty_child, NULL );
553
554 /* Note change in leaf set and display.
555 */
556 symbol_state_change( sym );
557 }
558
559 return( NULL );
560 }
561
562 /* ... mark this one as well.
563 */
564 void *
symbol_dirty(Symbol * sym,int serial)565 symbol_dirty( Symbol *sym, int serial )
566 {
567 g_assert( is_top( sym ) );
568
569 symbol_dirty_set( sym );
570
571 return( symbol_dirty_intrans( sym, serial ) );
572 }
573
574 void *
link_dirty_total(Link * link,int serial)575 link_dirty_total( Link *link, int serial )
576 {
577 static int recursion_depth = 0;
578
579 /* Entering: note new recursion.
580 */
581 if( recursion_depth++ > 1000 ) {
582 error_top( _( "Circular dependency." ) );
583 error_sub( _( "Circular dependency detected near "
584 "symbol \"%s\"." ),
585 IOBJECT( link->parent )->name );
586 recursion_depth = 0;
587 return( link );
588 }
589
590 /* Mark this sub-tree as dirty.
591 */
592 symbol_dirty( link->child, serial );
593
594 /* ... and repeat for any parents.
595 */
596 if( link->child->type != SYM_ZOMBIE )
597 if( slist_map( link->child->topchildren,
598 (SListMapFn) link_dirty_total,
599 GINT_TO_POINTER( serial ) ) )
600 return( link );
601
602 /* Pop recursion measure.
603 */
604 recursion_depth--;
605
606 return( NULL );
607 }
608
609 /* As above, but mark children as dirty as well. Used by force recalc to make
610 * sure that everything is completely rebuilt. Be careful of cycles!
611 */
612 void *
symbol_dirty_total(Symbol * sym,int serial)613 symbol_dirty_total( Symbol *sym, int serial )
614 {
615 if( sym->type == SYM_ZOMBIE )
616 return( NULL );
617
618 /* No children: just mark this sub-tree as dirty.
619 */
620 if( !sym->topchildren && symbol_dirty( sym, serial ) )
621 return( sym );
622
623 if( slist_map( sym->topchildren,
624 (SListMapFn) link_dirty_total, GINT_TO_POINTER( serial ) ) )
625 return( sym );
626
627 return( NULL );
628 }
629
630 /* Mark a symbol as clean. Knock down the leaf count of the things which refer
631 * to us ... one of them may turn into a leaf as a result.
632 */
633 void *
symbol_dirty_clear(Symbol * sym)634 symbol_dirty_clear( Symbol *sym )
635 {
636 g_assert( is_top( sym ) );
637
638 if( sym->dirty ) {
639 #ifdef DEBUG_DIRTY
640 printf( "symbol_dirty_clear: " );
641 symbol_name_print( sym );
642 printf( "(%p)\n", sym );
643 #endif /*DEBUG_DIRTY*/
644
645 /* Change of state.
646 */
647 sym->dirty = FALSE;
648 symbol_state_change( sym );
649
650 /* Update dirty counts on our parents.
651 */
652 (void) slist_map( sym->topparents,
653 (SListMapFn) link_clean_child, NULL );
654 }
655
656 return( NULL );
657 }
658