1 /****************************************************************\
2 * *
3 * C4 dynamic programming library - code for models *
4 * *
5 * Guy St.C. Slater.. mailto:guy@ebi.ac.uk *
6 * Copyright (C) 2000-2009. All Rights Reserved. *
7 * *
8 * This source code is distributed under the terms of the *
9 * GNU General Public License, version 3. See the file COPYING *
10 * or http://www.gnu.org/licenses/gpl.txt for details *
11 * *
12 * If you use this code, please keep this notice intact. *
13 * *
14 \****************************************************************/
15
16 #include "c4.h"
17 #include "matrix.h"
18
19 #include <ctype.h> /* For isalnum() */
20 #include <string.h> /* For strlen() */
21
22 /**/
23
C4_State_create(gchar * name)24 static C4_State *C4_State_create(gchar *name){
25 register C4_State *state = g_new(C4_State, 1);
26 g_assert(name);
27 state->name = g_strdup(name);
28 state->input_transition_list = g_ptr_array_new();
29 state->output_transition_list = g_ptr_array_new();
30 state->src_shadow_list = g_ptr_array_new();
31 return state;
32 }
33
C4_State_destroy(C4_State * state)34 static void C4_State_destroy(C4_State *state){
35 g_assert(state);
36 g_ptr_array_free(state->input_transition_list, TRUE);
37 g_ptr_array_free(state->output_transition_list, TRUE);
38 g_ptr_array_free(state->src_shadow_list, TRUE);
39 g_free(state->name);
40 g_free(state);
41 return;
42 }
43
44 /**/
45
C4_Calc_create(gchar * name,C4_Score max_score,C4_CalcFunc calc_func,gchar * calc_macro,C4_PrepFunc init_func,gchar * init_macro,C4_PrepFunc exit_func,gchar * exit_macro,C4_Protect protect)46 static C4_Calc *C4_Calc_create(gchar *name, C4_Score max_score,
47 C4_CalcFunc calc_func, gchar *calc_macro,
48 C4_PrepFunc init_func, gchar *init_macro,
49 C4_PrepFunc exit_func, gchar *exit_macro,
50 C4_Protect protect){
51 register C4_Calc *calc = g_new(C4_Calc, 1);
52 g_assert(name);
53 g_assert(calc_macro?(calc_func?TRUE:FALSE):TRUE);
54 g_assert(init_macro?(init_func?TRUE:FALSE):TRUE);
55 g_assert(exit_macro?(exit_func?TRUE:FALSE):TRUE);
56 if(calc_func && (!calc_macro))
57 g_warning("Missing calc_macro for Calc: [%s]", name);
58 if(init_func && (!init_macro))
59 g_warning("Missing init_macro for Calc: [%s]", name);
60 if(exit_func && (!exit_macro))
61 g_warning("Missing exit_macro for Calc: [%s]", name);
62 calc->name = g_strdup(name);
63 calc->max_score = max_score;
64 calc->calc_func = calc_func;
65 calc->calc_macro = g_strdup(calc_macro);
66 calc->init_func = init_func;
67 calc->init_macro = g_strdup(init_macro);
68 calc->exit_func = exit_func;
69 calc->exit_macro = g_strdup(exit_macro);
70 calc->protect = protect;
71 return calc;
72 }
73
C4_Calc_destroy(C4_Calc * calc)74 static void C4_Calc_destroy(C4_Calc *calc){
75 g_assert(calc);
76 if(calc->calc_macro)
77 g_free(calc->calc_macro);
78 if(calc->init_macro)
79 g_free(calc->init_macro);
80 if(calc->exit_macro)
81 g_free(calc->exit_macro);
82 g_free(calc->name);
83 g_free(calc);
84 return;
85 }
86
C4_Calc_diff(C4_Calc * a,C4_Calc * b)87 static gboolean C4_Calc_diff(C4_Calc *a, C4_Calc *b){
88 if((a->max_score == b->max_score)
89 && (a->calc_func == b->calc_func)
90 && (a->init_func == b->init_func)
91 && (a->exit_func == b->exit_func)
92 && (a->protect == b->protect))
93 return FALSE;
94 return TRUE;
95 }
96
97 /**/
98
C4_StartState_create(C4_State * state,C4_Scope scope,C4_CellStartFunc cell_start_func,gchar * cell_start_macro)99 static C4_StartState* C4_StartState_create(C4_State *state,
100 C4_Scope scope,
101 C4_CellStartFunc cell_start_func, gchar *cell_start_macro){
102 register C4_StartState *start_state = g_new(C4_StartState, 1);
103 g_assert(state);
104 start_state->state = state;
105 start_state->scope = scope;
106 start_state->cell_start_func = cell_start_func;
107 if(cell_start_macro)
108 start_state->cell_start_macro = g_strdup(cell_start_macro);
109 else
110 start_state->cell_start_macro = NULL;
111 return start_state;
112 }
113
C4_StartState_destroy(C4_StartState * start_state)114 static void C4_StartState_destroy(C4_StartState *start_state){
115 g_assert(start_state);
116 if(start_state->cell_start_macro)
117 g_free(start_state->cell_start_macro);
118 g_free(start_state);
119 return;
120 }
121
122 /**/
123
C4_EndState_create(C4_State * state,C4_Scope scope,C4_CellEndFunc cell_end_func,gchar * cell_end_macro)124 static C4_EndState* C4_EndState_create(C4_State *state, C4_Scope scope,
125 C4_CellEndFunc cell_end_func, gchar *cell_end_macro){
126 register C4_EndState *end_state = g_new(C4_EndState, 1);
127 g_assert(state);
128 end_state->state = state;
129 end_state->scope = scope;
130 end_state->cell_end_func = cell_end_func;
131 if(cell_end_macro)
132 end_state->cell_end_macro = g_strdup(cell_end_macro);
133 else
134 end_state->cell_end_macro = NULL;
135 return end_state;
136 }
137
C4_EndState_destroy(C4_EndState * end_state)138 static void C4_EndState_destroy(C4_EndState *end_state){
139 g_assert(end_state);
140 if(end_state->cell_end_macro)
141 g_free(end_state->cell_end_macro);
142 g_free(end_state);
143 return;
144 }
145
146 /**/
147
C4_Transition_create(gchar * name,C4_State * input,C4_State * output,gint advance_query,gint advance_target,C4_Calc * calc,C4_Label label,gpointer label_data)148 static C4_Transition *C4_Transition_create(gchar *name,
149 C4_State *input, C4_State *output,
150 gint advance_query, gint advance_target,
151 C4_Calc *calc, C4_Label label,
152 gpointer label_data){
153 register C4_Transition *transition = g_new(C4_Transition, 1);
154 g_assert(name);
155 transition->name = g_strdup(name);
156 transition->input = input;
157 transition->output = output;
158 transition->advance_query = advance_query;
159 transition->advance_target = advance_target;
160 transition->calc = calc;
161 transition->label = label;
162 transition->label_data = label_data;
163 transition->dst_shadow_list = g_ptr_array_new();
164 return transition;
165 }
166
C4_Transition_destroy(C4_Transition * transition)167 static void C4_Transition_destroy(C4_Transition *transition){
168 g_assert(transition);
169 g_ptr_array_free(transition->dst_shadow_list, TRUE);
170 g_free(transition->name);
171 g_free(transition);
172 return;
173 }
174
175 /**/
176
C4_Shadow_create(gchar * name,C4_State * src,C4_Transition * dst,C4_StartFunc start_func,gchar * start_macro,C4_EndFunc end_func,gchar * end_macro)177 static C4_Shadow *C4_Shadow_create(gchar *name,
178 C4_State *src, C4_Transition *dst,
179 C4_StartFunc start_func, gchar *start_macro,
180 C4_EndFunc end_func, gchar *end_macro){
181 register C4_Shadow *shadow = g_new0(C4_Shadow, 1);
182 g_assert(name);
183 g_assert(start_macro?(start_func?TRUE:FALSE):TRUE);
184 g_assert(end_macro?(end_func?TRUE:FALSE):TRUE);
185 if(start_func && (!start_macro))
186 g_warning("Missing start_macro for Shadow: [%s]", name);
187 if(end_func && (!end_macro))
188 g_warning("Missing end_macro for Shadow: [%s]", name);
189 shadow->name = g_strdup(name);
190 g_assert(src);
191 g_assert(dst);
192 shadow->src_state_list = g_ptr_array_new();
193 shadow->dst_transition_list = g_ptr_array_new();
194 g_ptr_array_add(shadow->src_state_list, src);
195 g_ptr_array_add(shadow->dst_transition_list, dst);
196 shadow->start_func = start_func;
197 if(start_macro)
198 shadow->start_macro = g_strdup(start_macro);
199 shadow->end_func = end_func;
200 if(end_macro)
201 shadow->end_macro = g_strdup(end_macro);
202 g_ptr_array_add(src->src_shadow_list, shadow);
203 g_ptr_array_add(dst->dst_shadow_list, shadow);
204 return shadow;
205 }
206
C4_Shadow_destroy(C4_Shadow * shadow)207 static void C4_Shadow_destroy(C4_Shadow *shadow){
208 g_ptr_array_free(shadow->src_state_list, TRUE);
209 g_ptr_array_free(shadow->dst_transition_list, TRUE);
210 g_free(shadow->name);
211 if(shadow->start_macro)
212 g_free(shadow->start_macro);
213 if(shadow->end_macro)
214 g_free(shadow->end_macro);
215 g_free(shadow);
216 return;
217 }
218
C4_Shadow_add_src_state(C4_Shadow * shadow,C4_State * src)219 void C4_Shadow_add_src_state(C4_Shadow *shadow, C4_State *src){
220 g_assert(shadow);
221 g_assert(src);
222 g_ptr_array_add(shadow->src_state_list, src);
223 g_ptr_array_add(src->src_shadow_list, shadow);
224 return;
225 }
226
C4_Shadow_add_dst_transition(C4_Shadow * shadow,C4_Transition * dst)227 void C4_Shadow_add_dst_transition(C4_Shadow *shadow,
228 C4_Transition *dst){
229 g_assert(shadow);
230 g_assert(dst);
231 g_ptr_array_add(shadow->dst_transition_list, dst);
232 g_ptr_array_add(dst->dst_shadow_list, shadow);
233 return;
234 }
235
C4_Shadow_is_valid(C4_Shadow * shadow,C4_Model * model)236 static gboolean C4_Shadow_is_valid(C4_Shadow *shadow, C4_Model *model){
237 register gint i, j;
238 register C4_State *state;
239 register C4_Transition *transition;
240 g_assert(shadow);
241 g_assert(shadow->src_state_list->len);
242 g_assert(shadow->dst_transition_list->len);
243 for(i = 0; i < shadow->src_state_list->len; i++){
244 state = shadow->src_state_list->pdata[i];
245 g_assert(state);
246 for(j = 0; j < shadow->dst_transition_list->len; j++){
247 transition = shadow->dst_transition_list->pdata[j];
248 g_assert(transition);
249 /* FIXME: this is not necessarily true for derived models */
250 /*
251 g_assert(C4_Model_path_is_possible(model, state,
252 transition->input));
253 */
254 }
255 }
256 return TRUE;
257 }
258
259 /**/
260
C4_Portal_create(gchar * name,C4_Calc * calc,gint advance_query,gint advance_target)261 static C4_Portal *C4_Portal_create(gchar *name, C4_Calc *calc,
262 gint advance_query, gint advance_target){
263 register C4_Portal *portal = g_new(C4_Portal, 1);
264 g_assert(name);
265 g_assert(calc);
266 portal->name = g_strdup(name);
267 portal->calc = calc;
268 portal->advance_query = advance_query;
269 portal->advance_target = advance_target;
270 portal->transition_list = g_ptr_array_new();
271 return portal;
272 }
273
C4_Portal_destroy(C4_Portal * portal)274 static void C4_Portal_destroy(C4_Portal *portal){
275 g_free(portal->name);
276 g_ptr_array_free(portal->transition_list, TRUE);
277 g_free(portal);
278 return;
279 }
280
281 /**/
282
C4_Span_find_loop_transitions(C4_Span * span)283 static void C4_Span_find_loop_transitions(C4_Span *span){
284 register gint i;
285 register C4_Transition *transition;
286 span->query_loop = span->target_loop = NULL;
287 for(i = 0; i < span->span_state->output_transition_list->len; i++){
288 transition = span->span_state->output_transition_list->pdata[i];
289 if(transition->output == span->span_state){ /* looping */
290 /* Find a C4_Calc which is sequence position independent */
291 if((!transition->calc) || (!transition->calc->calc_func)){
292 g_assert((!transition->calc)
293 || (!transition->calc->max_score));
294 g_assert(transition->advance_query
295 || transition->advance_target);
296 g_assert(!(transition->advance_query
297 && transition->advance_target));
298 if(transition->advance_query){
299 g_assert(!span->query_loop);
300 g_assert(!transition->advance_target);
301 span->query_loop = transition;
302 } else {
303 g_assert(!span->target_loop);
304 g_assert(transition->advance_target);
305 g_assert(!transition->advance_query);
306 span->target_loop = transition;
307 }
308 }
309 }
310 }
311 g_assert(span->query_loop || span->target_loop);
312 return;
313 }
314
C4_Span_create(gchar * name,C4_State * span_state,gint min_query,gint max_query,gint min_target,gint max_target)315 static C4_Span *C4_Span_create(gchar *name, C4_State *span_state,
316 gint min_query, gint max_query,
317 gint min_target, gint max_target){
318 register C4_Span *span = g_new(C4_Span, 1);
319 g_assert(name);
320 g_assert(span_state);
321 g_assert(min_query >= 0);
322 g_assert(min_query <= max_query);
323 g_assert(min_target >= 0);
324 g_assert(min_target <= max_target);
325 span->name = g_strdup(name);
326 span->span_state = span_state;
327 span->min_query = min_query;
328 span->max_query = max_query;
329 span->min_target = min_target;
330 span->max_target = max_target;
331 C4_Span_find_loop_transitions(span);
332 return span;
333 }
334
C4_Span_destroy(C4_Span * span)335 static void C4_Span_destroy(C4_Span *span){
336 g_assert(span);
337 g_free(span->name);
338 g_free(span);
339 return;
340 }
341
342 /**/
343
C4_Model_add_calc(C4_Model * model,gchar * name,C4_Score max_score,C4_CalcFunc calc_func,gchar * calc_macro,C4_PrepFunc init_func,gchar * init_macro,C4_PrepFunc exit_func,gchar * exit_macro,C4_Protect protect)344 C4_Calc *C4_Model_add_calc(C4_Model *model, gchar *name,
345 C4_Score max_score,
346 C4_CalcFunc calc_func, gchar *calc_macro,
347 C4_PrepFunc init_func, gchar *init_macro,
348 C4_PrepFunc exit_func, gchar *exit_macro,
349 C4_Protect protect){
350 register C4_Calc *calc = C4_Calc_create(name, max_score,
351 calc_func, calc_macro,
352 init_func, init_macro,
353 exit_func, exit_macro,
354 protect);
355 g_assert(model);
356 g_assert(name);
357 g_assert(model->is_open);
358 g_ptr_array_add(model->calc_list, calc);
359 return calc;
360 }
361
C4_Model_match_calc(C4_Model * model,C4_Calc * calc)362 static C4_Calc *C4_Model_match_calc(C4_Model *model, C4_Calc *calc){
363 register C4_Calc *mcalc = NULL;
364 register gint i;
365 g_assert(model);
366 g_assert(calc);
367 for(i = 0; i < model->calc_list->len; i++){
368 mcalc = model->calc_list->pdata[i];
369 if(!C4_Calc_diff(mcalc, calc))
370 return mcalc;
371 }
372 return NULL;
373 }
374
C4_Model_add_state(C4_Model * model,gchar * name)375 C4_State *C4_Model_add_state(C4_Model *model, gchar *name){
376 register C4_State *state = C4_State_create(name);
377 g_assert(model);
378 g_assert(name);
379 g_assert(model->is_open);
380 g_ptr_array_add(model->state_list, state);
381 return state;
382 }
383
C4_Model_select_transitions(C4_Model * model,C4_Label label)384 GPtrArray *C4_Model_select_transitions(C4_Model *model, C4_Label label){
385 register gint i;
386 register GPtrArray *list = g_ptr_array_new();
387 register C4_Transition *transition;
388 for(i = 0; i < model->transition_list->len; i++){
389 transition = model->transition_list->pdata[i];
390 if(transition->label == label)
391 g_ptr_array_add(list, transition);
392 }
393 if(!list->len){
394 g_ptr_array_free(list, TRUE);
395 return NULL;
396 }
397 return list;
398 }
399
C4_Model_select_single_transition(C4_Model * model,C4_Label label)400 C4_Transition *C4_Model_select_single_transition(C4_Model *model,
401 C4_Label label){
402 register C4_Transition *transition = NULL;
403 register GPtrArray *transition_list
404 = C4_Model_select_transitions(model, label);
405 g_assert(transition_list);
406 g_assert(transition_list->len == 1);
407 if(transition_list){
408 if(transition_list->len == 1)
409 transition = transition_list->pdata[0];
410 g_ptr_array_free(transition_list, TRUE);
411 }
412 return transition;
413 }
414
415
416 /**/
417
C4_Model_add_transition(C4_Model * model,gchar * name,C4_State * input,C4_State * output,gint advance_query,gint advance_target,C4_Calc * calc,C4_Label label,gpointer label_data)418 C4_Transition *C4_Model_add_transition(C4_Model *model, gchar *name,
419 C4_State *input, C4_State *output,
420 gint advance_query, gint advance_target,
421 C4_Calc *calc, C4_Label label,
422 gpointer label_data){
423 register C4_Transition *transition;
424 g_assert(model);
425 g_assert(name);
426 g_assert(model->is_open);
427 g_assert(advance_query >= 0);
428 g_assert(advance_target >= 0);
429 g_assert( (label == C4_Label_NONE)
430 || (advance_query || advance_target));
431 g_assert( (label != C4_Label_MATCH)
432 || (advance_query && advance_target));
433 g_assert( (label != C4_Label_GAP)
434 || (advance_query || advance_target));
435 g_assert( (label != C4_Label_FRAMESHIFT)
436 || (advance_query || advance_target));
437 if(!input)
438 input = model->start_state->state;
439 if(!output)
440 output = model->end_state->state;
441 transition = C4_Transition_create(name, input, output,
442 advance_query, advance_target, calc, label,
443 label_data);
444 g_ptr_array_add(input->output_transition_list, transition);
445 g_ptr_array_add(output->input_transition_list, transition);
446 g_ptr_array_add(model->transition_list, transition);
447 return transition;
448 }
449
C4_Model_add_shadow(C4_Model * model,gchar * name,C4_State * src,C4_Transition * dst,C4_StartFunc start_func,gchar * start_macro,C4_EndFunc end_func,gchar * end_macro)450 C4_Shadow *C4_Model_add_shadow(C4_Model *model, gchar *name,
451 C4_State *src, C4_Transition *dst,
452 C4_StartFunc start_func, gchar *start_macro,
453 C4_EndFunc end_func, gchar *end_macro){
454 register C4_Shadow *shadow;
455 register gint i;
456 g_assert(model);
457 g_assert(name);
458 g_assert(model->is_open);
459 g_assert(start_func);
460 g_assert(end_func);
461 if(!src)
462 src = model->start_state->state;
463 if(dst){
464 shadow = C4_Shadow_create(name, src, dst,
465 start_func, start_macro,
466 end_func, end_macro);
467 } else { /* Use all transitions to END as dst */
468 g_assert(model->end_state->state->input_transition_list->len);
469 dst = model->end_state->state->input_transition_list->pdata[0];
470 shadow = C4_Shadow_create(name, src, dst,
471 start_func, start_macro,
472 end_func, end_macro);
473 for(i = 1; i < model->end_state->state
474 ->input_transition_list->len; i++){
475 dst = model->end_state->state
476 ->input_transition_list->pdata[i];
477 C4_Shadow_add_dst_transition(shadow, dst);
478 }
479 }
480 g_assert(shadow);
481 g_ptr_array_add(model->shadow_list, shadow);
482 return shadow;
483 }
484
C4_Model_add_portal(C4_Model * model,gchar * name,C4_Calc * calc,gint advance_query,gint advance_target)485 C4_Portal *C4_Model_add_portal(C4_Model *model, gchar *name,
486 C4_Calc *calc, gint advance_query, gint advance_target){
487 register C4_Portal *portal;
488 g_assert(model->is_open);
489 g_assert(calc);
490 g_assert(calc->calc_func); /* Must have position specific calc */
491 portal = C4_Portal_create(name, calc,
492 advance_query, advance_target);
493 /* Add the portal to the model */
494 g_ptr_array_add(model->portal_list, portal);
495 return portal;
496 }
497
C4_Model_add_span(C4_Model * model,gchar * name,C4_State * span_state,gint min_query,gint max_query,gint min_target,gint max_target)498 C4_Span *C4_Model_add_span(C4_Model *model, gchar *name,
499 C4_State *span_state,
500 gint min_query, gint max_query,
501 gint min_target, gint max_target){
502 register C4_Span *span;
503 g_assert(model->is_open);
504 span = C4_Span_create(name, span_state, min_query, max_query,
505 min_target, max_target);
506 g_ptr_array_add(model->span_list, span);
507 return span;
508 }
509
C4_Model_create(gchar * name)510 C4_Model *C4_Model_create(gchar *name){
511 register C4_Model *model = g_new(C4_Model, 1);
512 g_assert(name);
513 model->name = g_strdup(name);
514 /**/
515 model->global_code_list = g_ptr_array_new();
516 model->local_code_list = g_ptr_array_new();
517 model->cflags_add_list = g_ptr_array_new();
518 model->init_func = NULL;
519 model->init_macro = NULL;
520 model->exit_func = NULL;
521 model->exit_macro = NULL;
522 /**/
523 model->thread_ref = ThreadRef_create();
524 model->is_open = TRUE;
525 /**/
526 model->state_list = g_ptr_array_new();
527 model->transition_list = g_ptr_array_new();
528 model->shadow_list = g_ptr_array_new();
529 model->calc_list = g_ptr_array_new();
530 model->portal_list = g_ptr_array_new();
531 model->span_list = g_ptr_array_new();
532 /**/
533 model->start_state = C4_StartState_create(
534 C4_Model_add_state(model, "START"),
535 C4_Scope_ANYWHERE, NULL, NULL);
536 model->end_state = C4_EndState_create(
537 C4_Model_add_state(model, "END"),
538 C4_Scope_ANYWHERE, NULL, NULL);
539 return model;
540 }
541
C4_Model_rename(C4_Model * model,gchar * name)542 void C4_Model_rename(C4_Model *model, gchar *name){
543 g_assert(model);
544 g_assert(name);
545 g_free(model->name);
546 model->name = g_strdup(name);
547 return;
548 }
549
550 /**/
551
C4_Model_destroy_string_list(GPtrArray * string_list)552 static void C4_Model_destroy_string_list(GPtrArray *string_list){
553 register gint i;
554 for(i = 0; i < string_list->len; i++)
555 g_free(string_list->pdata[i]);
556 g_ptr_array_free(string_list, TRUE);
557 return;
558 }
559
C4_Model_destroy(C4_Model * model)560 void C4_Model_destroy(C4_Model *model){
561 register gint i;
562 g_assert(model);
563 if(ThreadRef_destroy(model->thread_ref))
564 return;
565 g_free(model->name);
566 C4_Model_destroy_string_list(model->global_code_list);
567 C4_Model_destroy_string_list(model->local_code_list);
568 C4_Model_destroy_string_list(model->cflags_add_list);
569 if(model->init_macro)
570 g_free(model->init_macro);
571 if(model->exit_macro)
572 g_free(model->exit_macro);
573 C4_StartState_destroy(model->start_state);
574 C4_EndState_destroy(model->end_state);
575 for(i = 0; i < model->state_list->len; i++)
576 C4_State_destroy(model->state_list->pdata[i]);
577 for(i = 0; i < model->transition_list->len; i++)
578 C4_Transition_destroy(model->transition_list->pdata[i]);
579 for(i = 0; i < model->shadow_list->len; i++)
580 C4_Shadow_destroy(model->shadow_list->pdata[i]);
581 for(i = 0; i < model->calc_list->len; i++)
582 C4_Calc_destroy(model->calc_list->pdata[i]);
583 for(i = 0; i < model->portal_list->len; i++)
584 C4_Portal_destroy(model->portal_list->pdata[i]);
585 for(i = 0; i < model->span_list->len; i++)
586 C4_Span_destroy(model->span_list->pdata[i]);
587 g_ptr_array_free(model->state_list, TRUE);
588 g_ptr_array_free(model->transition_list, TRUE);
589 g_ptr_array_free(model->shadow_list, TRUE);
590 g_ptr_array_free(model->calc_list, TRUE);
591 g_ptr_array_free(model->portal_list, TRUE);
592 g_ptr_array_free(model->span_list, TRUE);
593 g_free(model);
594 return;
595 }
596
C4_Model_share(C4_Model * model)597 C4_Model *C4_Model_share(C4_Model *model){
598 g_assert(model);
599 g_assert(!model->is_open);
600 ThreadRef_share(model->thread_ref);
601 return model;
602 }
603
C4_State_compare_by_name(gconstpointer a,gconstpointer b)604 static gint C4_State_compare_by_name(gconstpointer a,
605 gconstpointer b){
606 register C4_State *state_a = (C4_State*)a,
607 *state_b = (C4_State*)b;
608 return strcmp(state_a->name, state_b->name);
609 }
610
C4_Transition_compare_by_name(gconstpointer a,gconstpointer b)611 static gint C4_Transition_compare_by_name(gconstpointer a,
612 gconstpointer b){
613 register C4_Transition *tran_a = (C4_Transition*)a,
614 *tran_b = (C4_Transition*)b;
615 return strcmp(tran_a->name, tran_b->name);
616 }
617
618 /* FIXME: rewrite without using state names */
C4_Model_build_state_map(C4_Model * src,C4_Model * dst)619 C4_State **C4_Model_build_state_map(C4_Model *src, C4_Model *dst){
620 register C4_State **state_map = g_new0(C4_State*,
621 src->state_list->len);
622 register gint i;
623 register C4_State *src_state, *dst_state;
624 register GTree *state_map_tree
625 = g_tree_new(C4_State_compare_by_name);
626 g_assert(src);
627 g_assert(dst);
628 g_assert(src->state_list->len == dst->state_list->len);
629 for(i = 0; i < dst->state_list->len; i++){
630 dst_state = dst->state_list->pdata[i];
631 if(g_tree_lookup(state_map_tree, dst_state))
632 g_error("Duplicate state name [%s] in model [%s]",
633 dst_state->name, src->name);
634 g_assert(!g_tree_lookup(state_map_tree, dst_state));
635 g_tree_insert(state_map_tree, dst_state, dst_state);
636 }
637 for(i = 0; i < src->state_list->len; i++){
638 src_state = src->state_list->pdata[i];
639 dst_state = g_tree_lookup(state_map_tree, src_state);
640 g_assert(dst_state);
641 state_map[src_state->id] = dst_state;
642 }
643 g_tree_destroy(state_map_tree);
644 return state_map;
645 }
646
647 /* FIXME: rewrite without using transition names */
C4_Model_build_transition_map(C4_Model * src,C4_Model * dst)648 C4_Transition **C4_Model_build_transition_map(C4_Model *src,
649 C4_Model *dst){
650 register C4_Transition **transition_map = g_new0(C4_Transition*,
651 src->transition_list->len);
652 register gint i;
653 register C4_Transition *src_transition, *dst_transition;
654 register GTree *transition_map_tree
655 = g_tree_new(C4_Transition_compare_by_name);
656 g_assert(src);
657 g_assert(dst);
658 g_assert(src->transition_list->len == dst->transition_list->len);
659 for(i = 0; i < dst->transition_list->len; i++){
660 dst_transition = dst->transition_list->pdata[i];
661 if(g_tree_lookup(transition_map_tree, dst_transition))
662 g_error("Duplicate transition name [%s] in model [%s]",
663 dst_transition->name, src->name);
664 g_assert(!g_tree_lookup(transition_map_tree, dst_transition));
665 g_tree_insert(transition_map_tree, dst_transition,
666 dst_transition);
667 }
668 for(i = 0; i < src->transition_list->len; i++){
669 src_transition = src->transition_list->pdata[i];
670 dst_transition = g_tree_lookup(transition_map_tree,
671 src_transition);
672 g_assert(dst_transition);
673 transition_map[src_transition->id] = dst_transition;
674 }
675 g_tree_destroy(transition_map_tree);
676 return transition_map;
677 }
678
679 /**/
680
C4_Model_make_stereo(C4_Model * model,gchar * suffix_a,gchar * suffix_b)681 void C4_Model_make_stereo(C4_Model *model, gchar *suffix_a,
682 gchar *suffix_b){
683 register gint i, j,
684 prev_state_count = model->state_list->len,
685 prev_transition_count = model->transition_list->len,
686 prev_shadow_count = model->shadow_list->len;
687 register C4_State *state,
688 **state_map = g_new0(C4_State*, prev_state_count);
689 register C4_Transition *transition,
690 **transition_map = g_new0(C4_Transition*,
691 prev_transition_count);
692 register C4_Shadow *shadow, *new_shadow;
693 register gchar *name;
694 g_assert(model->is_open);
695 /* Copy each state -> state.suffix_b */
696 for(i = 0; i < prev_state_count; i++){
697 state = model->state_list->pdata[i];
698 if((state != model->start_state->state)
699 && (state != model->end_state->state)){
700 name = g_strconcat(state->name, " ", suffix_b, NULL);
701 state_map[state->id] = C4_Model_add_state(model, name);
702 g_free(name);
703 }
704 }
705 /* Copy each transition -> transition.suffix_b */
706 for(i = 0; i < prev_transition_count; i++){
707 transition = model->transition_list->pdata[i];
708 name = g_strconcat(transition->name, " ", suffix_b, NULL);
709 transition_map[transition->id] = C4_Model_add_transition(
710 model, name,
711 state_map[transition->input->id],
712 state_map[transition->output->id],
713 transition->advance_query, transition->advance_target,
714 transition->calc, transition->label,
715 transition->label_data);
716 g_free(name);
717 }
718 /* Copy each shadow -> shadow.suffix_b */
719 for(i = 0; i < prev_shadow_count; i++){
720 shadow = model->shadow_list->pdata[i];
721 name = g_strconcat(shadow->name, " ", suffix_b, NULL);
722 g_assert(shadow->src_state_list->len);
723 g_assert(shadow->dst_transition_list->len);
724 state = shadow->src_state_list->pdata[0];
725 transition = shadow->dst_transition_list->pdata[0];
726 new_shadow = C4_Model_add_shadow(model, name,
727 state_map[state->id],
728 transition_map[transition->id],
729 shadow->start_func, shadow->start_macro,
730 shadow->end_func, shadow->end_macro);
731 g_free(name);
732 /* Copy remainding src states */
733 for(j = 1; j < shadow->src_state_list->len; j++){
734 state = shadow->src_state_list->pdata[j];
735 C4_Shadow_add_src_state(new_shadow, state);
736 }
737 /* Copy remainding dst transitions */
738 for(j = 1; j < shadow->dst_transition_list->len; j++){
739 transition = shadow->dst_transition_list->pdata[j];
740 C4_Shadow_add_dst_transition(new_shadow, transition);
741 }
742 }
743 /* Rename each original state -> state.suffix_a */
744 for(i = 0; i < prev_state_count; i++){
745 state = model->state_list->pdata[i];
746 if((state != model->start_state->state)
747 && (state != model->end_state->state)){
748 name = state->name;
749 state->name = g_strconcat(name, " ", suffix_a, NULL);
750 g_free(name);
751 }
752 }
753 /* Rename each transition -> transition.suffix_a */
754 for(i = 0; i < prev_transition_count; i++){
755 transition = model->transition_list->pdata[i];
756 name = transition->name;
757 transition->name = g_strconcat(name, " ", suffix_a, NULL);
758 g_free(name);
759 }
760 /* Rename each shadow -> shadow.suffix_a */
761 for(i = 0; i < prev_shadow_count; i++){
762 shadow = model->shadow_list->pdata[i];
763 name = shadow->name;
764 shadow->name = g_strconcat(name, " ", suffix_a, NULL);
765 g_free(name);
766 }
767 g_free(state_map);
768 g_free(transition_map);
769 return;
770 }
771
C4_Model_insert_calcs(C4_Model * target,C4_Model * insert,C4_Calc ** calc_map)772 static void C4_Model_insert_calcs(C4_Model *target, C4_Model *insert,
773 C4_Calc **calc_map){
774 register gint i;
775 register C4_Calc *insert_calc, *target_calc;
776 for(i = 0; i < insert->calc_list->len; i++){
777 insert_calc = insert->calc_list->pdata[i];
778 target_calc = C4_Model_match_calc(target, insert_calc);
779 if(!target_calc)
780 target_calc = C4_Model_add_calc(target, insert_calc->name,
781 insert_calc->max_score,
782 insert_calc->calc_func, insert_calc->calc_macro,
783 insert_calc->init_func, insert_calc->init_macro,
784 insert_calc->exit_func, insert_calc->exit_macro,
785 insert_calc->protect);
786 calc_map[insert_calc->id] = target_calc;
787 }
788 return;
789 }
790
C4_Model_insert_states(C4_Model * target,C4_Model * insert,C4_State ** state_map)791 static void C4_Model_insert_states(C4_Model *target, C4_Model *insert,
792 C4_State **state_map){
793 register gint i;
794 register C4_State *insert_state;
795 for(i = 0; i < insert->state_list->len; i++){
796 insert_state = insert->state_list->pdata[i];
797 if((insert_state != insert->start_state->state)
798 && (insert_state != insert->end_state->state))
799 state_map[insert_state->id]
800 = C4_Model_add_state(target, insert_state->name);
801 }
802 return;
803 }
804
C4_Model_insert_transitions(C4_Model * target,C4_Model * insert,C4_State * src,C4_State * dst,C4_Calc ** calc_map,C4_State ** state_map,C4_Transition ** transition_map)805 static void C4_Model_insert_transitions(C4_Model *target,
806 C4_Model *insert,
807 C4_State *src, C4_State *dst,
808 C4_Calc **calc_map,
809 C4_State **state_map,
810 C4_Transition **transition_map){
811 register gint i;
812 register C4_Transition *transition;
813 register C4_Calc *calc;
814 for(i = 0; i < insert->transition_list->len; i++){
815 transition = insert->transition_list->pdata[i];
816 g_assert(transition);
817 if(transition->calc){
818 calc = calc_map[transition->calc->id];
819 } else {
820 calc = NULL;
821 }
822 transition_map[transition->id] = C4_Model_add_transition(
823 target, transition->name,
824 state_map[transition->input->id],
825 state_map[transition->output->id],
826 transition->advance_query, transition->advance_target,
827 calc, transition->label, transition->label_data);
828 }
829 return;
830 }
831
C4_Model_insert_shadows(C4_Model * target,C4_Model * insert,C4_State * src,C4_State * dst,C4_State ** state_map,C4_Transition ** transition_map)832 static void C4_Model_insert_shadows(C4_Model *target,
833 C4_Model *insert,
834 C4_State *src, C4_State *dst,
835 C4_State **state_map,
836 C4_Transition **transition_map){
837 register gint i, j;
838 register C4_Shadow *shadow, *new_shadow;
839 register C4_State *state, *src_state;
840 register C4_Transition *transition, *dst_transition;
841 /* For each insert shadow */
842 for(i = 0; i < insert->shadow_list->len; i++){
843 shadow = insert->shadow_list->pdata[i];
844 g_assert(shadow);
845 g_assert(shadow->src_state_list->len);
846 g_assert(shadow->dst_transition_list->len);
847 state = shadow->src_state_list->pdata[0];
848 src_state = state_map[state->id];
849 transition = shadow->dst_transition_list->pdata[0];
850 dst_transition = transition_map[transition->id];
851 new_shadow = C4_Model_add_shadow(target, shadow->name,
852 src_state, dst_transition,
853 shadow->start_func, shadow->start_macro,
854 shadow->end_func, shadow->end_macro);
855 for(j = 1; j < shadow->src_state_list->len; j++){
856 state = shadow->src_state_list->pdata[j];
857 src_state = state_map[state->id];
858 C4_Shadow_add_src_state(new_shadow, src_state);
859 }
860 for(j = 1; j < shadow->dst_transition_list->len; j++){
861 transition = shadow->dst_transition_list->pdata[j];
862 dst_transition = transition_map[transition->id];
863 C4_Shadow_add_dst_transition(new_shadow, dst_transition);
864 }
865 }
866 return;
867 }
868
C4_Calc_is_same(C4_Calc * calc_a,C4_Calc * calc_b)869 static gboolean C4_Calc_is_same(C4_Calc *calc_a, C4_Calc *calc_b){
870 if((calc_a->max_score == calc_b->max_score)
871 && (calc_a->calc_func == calc_b->calc_func)
872 && (calc_a->init_func == calc_b->init_func)
873 && (calc_a->exit_func == calc_b->exit_func)
874 && (calc_a->protect == calc_b->protect))
875 return TRUE;
876 return FALSE;
877 }
878
C4_Portal_is_same(C4_Portal * portal_a,C4_Portal * portal_b)879 static gboolean C4_Portal_is_same(C4_Portal *portal_a,
880 C4_Portal *portal_b){
881 if((portal_a->advance_query == portal_b->advance_query)
882 && (portal_a->advance_target == portal_b->advance_target)
883 && C4_Calc_is_same(portal_a->calc, portal_b->calc))
884 return TRUE;
885 return FALSE;
886 }
887
C4_Model_insert_portals(C4_Model * target,C4_Model * insert,C4_Calc ** calc_map)888 static void C4_Model_insert_portals(C4_Model *target,
889 C4_Model *insert, C4_Calc **calc_map){
890 register gint i, j;
891 register C4_Portal *insert_portal, *target_portal;
892 register C4_Transition *transition;
893 register gboolean found_same;
894 for(i = 0; i < insert->portal_list->len; i++){
895 insert_portal = insert->portal_list->pdata[i];
896 found_same = FALSE;
897 for(j = 0; j < target->portal_list->len; j++){
898 target_portal = target->portal_list->pdata[j];
899 if(C4_Portal_is_same(insert_portal, target_portal)){
900 for(j = 0; j < insert_portal->transition_list->len;
901 j++){
902 transition
903 = insert_portal->transition_list->pdata[j];
904 g_ptr_array_add(target_portal->transition_list,
905 transition);
906 }
907 found_same = TRUE;
908 break;
909 }
910 }
911 if(!found_same){
912 C4_Model_add_portal(target, insert_portal->name,
913 calc_map[insert_portal->calc->id],
914 insert_portal->advance_query,
915 insert_portal->advance_target);
916 }
917 }
918 return;
919 }
920 /* FIXME: merge duplicate portals */
921
C4_Model_insert_spans(C4_Model * target,C4_Model * insert,C4_State ** state_map)922 static void C4_Model_insert_spans(C4_Model *target,
923 C4_Model *insert, C4_State **state_map){
924 register gint i;
925 register C4_Span *span;
926 for(i = 0; i < insert->span_list->len; i++){
927 span = insert->span_list->pdata[i];
928 C4_Model_add_span(target, span->name,
929 state_map[span->span_state->id],
930 span->min_query, span->max_query,
931 span->min_target, span->max_target);
932 }
933 return;
934 }
935
C4_Model_string_list_contains(GPtrArray * list,gchar * str)936 static gboolean C4_Model_string_list_contains(GPtrArray *list,
937 gchar *str){
938 register gint i;
939 for(i = 0; i < list->len; i++)
940 if(!strcmp(list->pdata[i], str))
941 return TRUE;
942 return FALSE;
943 }
944
C4_Model_merge_codegen_list(GPtrArray * dst,GPtrArray * src)945 static void C4_Model_merge_codegen_list(GPtrArray *dst, GPtrArray *src){
946 register gint i;
947 for(i = 0; i < src->len; i++)
948 if(!C4_Model_string_list_contains(dst, src->pdata[i]))
949 g_ptr_array_add(dst, g_strdup(src->pdata[i]));
950 return;
951 }
952
C4_Model_merge_codegen(C4_Model * dst,C4_Model * src)953 static void C4_Model_merge_codegen(C4_Model *dst, C4_Model *src){
954 C4_Model_merge_codegen_list(dst->global_code_list,
955 src->global_code_list);
956 C4_Model_merge_codegen_list(dst->local_code_list,
957 src->local_code_list);
958 C4_Model_merge_codegen_list(dst->cflags_add_list,
959 src->cflags_add_list);
960 return;
961 }
962
C4_Model_insert(C4_Model * target,C4_Model * insert,C4_State * src,C4_State * dst)963 void C4_Model_insert(C4_Model *target, C4_Model *insert,
964 C4_State *src, C4_State *dst){
965 register C4_Calc **calc_map = g_new0(C4_Calc*,
966 insert->calc_list->len);
967 register C4_State **state_map = g_new0(C4_State*,
968 insert->state_list->len);
969 register C4_Transition **transition_map = g_new0(C4_Transition*,
970 insert->transition_list->len);
971 g_assert(target->is_open);
972 g_assert(!insert->is_open);
973 if(!src)
974 src = target->start_state->state;
975 if(!dst)
976 dst = target->end_state->state;
977 C4_Model_insert_calcs(target, insert, calc_map);
978 C4_Model_insert_states(target, insert, state_map);
979 /* Add src and dst states to the state map */
980 state_map[insert->start_state->state->id] = src;
981 state_map[insert->end_state->state->id] = dst;
982 C4_Model_insert_transitions(target, insert, src, dst,
983 calc_map, state_map, transition_map);
984 C4_Model_insert_shadows(target, insert, src, dst,
985 state_map, transition_map);
986 C4_Model_insert_portals(target, insert, calc_map);
987 C4_Model_insert_spans(target, insert, state_map);
988 C4_Model_merge_codegen(target, insert);
989 C4_Model_configure_extra(target,
990 insert->init_func, insert->init_macro,
991 insert->exit_func, insert->exit_macro);
992 g_free(state_map);
993 g_free(transition_map);
994 g_free(calc_map);
995 return;
996 }
997
998 /**/
999
C4_Model_clear_codegen(C4_Model * model)1000 void C4_Model_clear_codegen(C4_Model *model){
1001 C4_Model_destroy_string_list(model->global_code_list);
1002 model->global_code_list = g_ptr_array_new();
1003 C4_Model_destroy_string_list(model->local_code_list);
1004 model->local_code_list = g_ptr_array_new();
1005 C4_Model_destroy_string_list(model->cflags_add_list);
1006 model->cflags_add_list = g_ptr_array_new();
1007 return;
1008 }
1009
C4_Model_append_codegen(C4_Model * model,gchar * global_code,gchar * local_code,gchar * cflags_add)1010 void C4_Model_append_codegen(C4_Model *model,
1011 gchar *global_code, gchar *local_code,
1012 gchar *cflags_add){
1013 if((global_code) && (!C4_Model_string_list_contains(
1014 model->global_code_list, global_code)))
1015 g_ptr_array_add(model->global_code_list, g_strdup(global_code));
1016 if((local_code) && (!C4_Model_string_list_contains(
1017 model->local_code_list, local_code)))
1018 g_ptr_array_add(model->local_code_list, g_strdup(local_code));
1019 if((cflags_add) && (!C4_Model_string_list_contains(
1020 model->cflags_add_list, cflags_add)))
1021 g_ptr_array_add(model->cflags_add_list, g_strdup(cflags_add));
1022 return;
1023 }
1024
C4_Model_configure_extra(C4_Model * model,C4_PrepFunc init_func,gchar * init_macro,C4_PrepFunc exit_func,gchar * exit_macro)1025 void C4_Model_configure_extra(C4_Model *model,
1026 C4_PrepFunc init_func, gchar *init_macro,
1027 C4_PrepFunc exit_func, gchar *exit_macro){
1028 g_assert(model);
1029 g_assert(model->is_open);
1030 g_assert(init_macro?(init_func?TRUE:FALSE):TRUE);
1031 g_assert(exit_macro?(exit_func?TRUE:FALSE):TRUE);
1032 /* FIXME: all instances should be on a calc ... */
1033 /*
1034 g_assert(!init_func);
1035 g_assert(!exit_func);
1036 */
1037 /*
1038 if(init_func && (!init_macro))
1039 g_warning("Missing init_macro for Model: [%s]", model->name);
1040 if(exit_func && (!exit_macro))
1041 g_warning("Missing exit_macro for Model: [%s]", model->name);
1042 */
1043 model->init_func = init_func;
1044 if(model->init_macro){
1045 if(model->init_macro)
1046 g_free(model->init_macro);
1047 model->init_macro = g_strdup(init_macro);
1048 }
1049 model->exit_func = exit_func;
1050 if(model->exit_macro){
1051 if(model->exit_macro)
1052 g_free(model->exit_macro);
1053 model->exit_macro = g_strdup(exit_macro);
1054 }
1055 return;
1056 }
1057 /* FIXME: need to allow joining of multiple funcs and macros ... */
1058
C4_Model_configure_start_state(C4_Model * model,C4_Scope scope,C4_CellStartFunc cell_start_func,gchar * cell_start_macro)1059 void C4_Model_configure_start_state(C4_Model *model, C4_Scope scope,
1060 C4_CellStartFunc cell_start_func, gchar *cell_start_macro){
1061 g_assert(model);
1062 /*
1063 if(cell_start_func && (!cell_start_macro))
1064 g_warning("Missing cell_start_macro for Model: [%s]",
1065 model->name);
1066 */
1067 model->start_state->scope = scope;
1068 model->start_state->cell_start_func = cell_start_func;
1069 if(model->start_state->cell_start_macro != cell_start_macro){
1070 if(model->start_state->cell_start_macro)
1071 g_free(model->start_state->cell_start_macro);
1072 if(cell_start_macro)
1073 model->start_state->cell_start_macro
1074 = g_strdup(cell_start_macro);
1075 else
1076 model->start_state->cell_start_macro = NULL;
1077 } else {
1078 model->start_state->cell_start_macro = NULL;
1079 }
1080 return;
1081 }
1082
C4_Model_configure_end_state(C4_Model * model,C4_Scope scope,C4_CellEndFunc cell_end_func,gchar * cell_end_macro)1083 void C4_Model_configure_end_state(C4_Model *model, C4_Scope scope,
1084 C4_CellEndFunc cell_end_func, gchar *cell_end_macro){
1085 g_assert(model);
1086 /*
1087 if(cell_end_func && (!cell_end_macro))
1088 g_warning("Missing cell_end_macro for Model: [%s]",
1089 model->name);
1090 */
1091 model->end_state->scope = scope;
1092 model->end_state->cell_end_func = cell_end_func;
1093 if(model->end_state->cell_end_macro != cell_end_macro){
1094 if(model->end_state->cell_end_macro)
1095 g_free(model->end_state->cell_end_macro);
1096 if(cell_end_macro)
1097 model->end_state->cell_end_macro = g_strdup(cell_end_macro);
1098 else
1099 model->end_state->cell_end_macro = NULL;
1100 } else {
1101 model->end_state->cell_end_macro = NULL;
1102 }
1103 return;
1104 }
1105
1106 /**/
1107
C4_Scope_get_name(C4_Scope scope)1108 gchar *C4_Scope_get_name(C4_Scope scope){
1109 register gchar *name = NULL;
1110 switch(scope){
1111 case C4_Scope_ANYWHERE:
1112 name = "anywhere";
1113 break;
1114 case C4_Scope_EDGE:
1115 name = "edge";
1116 break;
1117 case C4_Scope_QUERY:
1118 name = "query";
1119 break;
1120 case C4_Scope_TARGET:
1121 name = "target";
1122 break;
1123 case C4_Scope_CORNER:
1124 name = "corner";
1125 break;
1126 default:
1127 g_error("Unknown C4_Scope type [%d]", scope);
1128 break;
1129 }
1130 return name;
1131 }
1132
C4_Label_get_name(C4_Label label)1133 gchar *C4_Label_get_name(C4_Label label){
1134 register gchar *name = NULL;
1135 switch(label){
1136 case C4_Label_NONE:
1137 name = "none";
1138 break;
1139 case C4_Label_MATCH:
1140 name = "match";
1141 break;
1142 case C4_Label_GAP:
1143 name = "gap";
1144 break;
1145 case C4_Label_NER:
1146 name = "ner";
1147 break;
1148 case C4_Label_5SS:
1149 name = "5'ss";
1150 break;
1151 case C4_Label_3SS:
1152 name = "3'ss";
1153 break;
1154 case C4_Label_INTRON:
1155 name = "intron";
1156 break;
1157 case C4_Label_SPLIT_CODON:
1158 name = "split codon";
1159 break;
1160 case C4_Label_FRAMESHIFT:
1161 name = "frameshift";
1162 break;
1163 default:
1164 g_error("Unknown label [%d]", label);
1165 break;
1166 }
1167 return name;
1168 }
1169
C4_Model_print(C4_Model * model)1170 void C4_Model_print(C4_Model *model){
1171 register gint i;
1172 register C4_State *state;
1173 register C4_Transition *transition;
1174 register C4_Calc *calc;
1175 register C4_Portal *portal;
1176 register C4_Span *span;
1177 g_assert(model);
1178 g_print("--\n"
1179 " Info for model [%s]\n"
1180 " status [%s]\n"
1181 " start scope [%s]\n"
1182 " end scope [%s]\n",
1183 model->name, model->is_open?"OPEN":"CLOSED",
1184 C4_Scope_get_name(model->start_state->scope),
1185 C4_Scope_get_name(model->end_state->scope));
1186 for(i = 0; i < model->state_list->len; i++){
1187 state = model->state_list->pdata[i];
1188 g_print("State [%s]\n", state->name);
1189 }
1190 for(i = 0; i < model->transition_list->len; i++){
1191 transition = model->transition_list->pdata[i];
1192 g_print("Transition [%s] ( [%s]->[%s] ) [%d,%d]\n",
1193 transition->name,
1194 transition->input->name,
1195 transition->output->name,
1196 transition->advance_query,
1197 transition->advance_query);
1198 }
1199 for(i = 0; i < model->calc_list->len; i++){
1200 calc = model->calc_list->pdata[i];
1201 g_print("Calc [%s]\n", calc->name);
1202 }
1203 for(i = 0; i < model->portal_list->len; i++){
1204 portal = model->portal_list->pdata[i];
1205 g_print("Portal [%s]\n", portal->name);
1206 }
1207 for(i = 0; i < model->span_list->len; i++){
1208 span = model->span_list->pdata[i];
1209 g_print("Span [%s]\n", span->name);
1210 }
1211 g_print("--\n");
1212 return;
1213 }
1214
clean_string(gchar * str)1215 static gchar *clean_string(gchar *str){
1216 register gchar *new_string = g_strdup(str);
1217 register gint i;
1218 for(i = 0; new_string[i]; i++){
1219 if(!isalnum(new_string[i]))
1220 new_string[i] = '_';
1221 }
1222 return new_string;
1223 }
1224
break_string(gchar * str)1225 static gchar *break_string(gchar *str){
1226 register GString *s = g_string_sized_new(strlen(str)+10);
1227 register gchar *new_string;
1228 register gint i;
1229 for(i = 0; str[i]; i++){
1230 if(isspace(str[i]))
1231 g_string_append(s, "\\n");
1232 else
1233 g_string_append_c(s, str[i]);
1234 }
1235 new_string = s->str;
1236 g_string_free(s, FALSE);
1237 return new_string;
1238 }
1239
C4_Model_dump_graphviz(C4_Model * model)1240 void C4_Model_dump_graphviz(C4_Model *model){
1241 register gint i, j, k;
1242 register C4_State *state;
1243 register C4_Transition *transition;
1244 register C4_Shadow *shadow;
1245 register gchar *identifier;
1246 g_assert(model);
1247 g_assert(!model->is_open);
1248 identifier = clean_string(model->name);
1249 g_print("// --- START OF GRAPHVIZ DUMP ---\n");
1250 g_print("digraph %s {\n", identifier);
1251 g_free(identifier);
1252 g_print("// states\n");
1253 for(i = 0; i < model->state_list->len; i++){
1254 state = model->state_list->pdata[i];
1255 identifier = break_string(state->name);
1256 g_print("state_%d [label=\"%s\"", state->id, identifier);
1257 g_free(identifier);
1258 if((state == model->start_state->state)
1259 || (state == model->end_state->state))
1260 g_print(",shape=box");
1261 g_print("]\n");
1262 }
1263 g_print("// transitions\n");
1264 for(i = 0; i < model->transition_list->len; i++){
1265 transition = model->transition_list->pdata[i];
1266 g_print("state_%d -> state_%d",
1267 transition->input->id,
1268 transition->output->id);
1269 if(transition->advance_query || transition->advance_target)
1270 g_print(" [label=\"%d:%d\"]",
1271 transition->advance_query, transition->advance_target);
1272 g_print(" // %s", transition->name);
1273 g_print("\n");
1274 }
1275 if(model->shadow_list->len)
1276 g_print("// shadows\n");
1277 /* Shadows are just drawn from src to dst->input */
1278 for(i = 0; i < model->shadow_list->len; i++){
1279 shadow = model->shadow_list->pdata[i];
1280 for(j = 0; j < shadow->src_state_list->len; j++){
1281 state = shadow->src_state_list->pdata[j];
1282 for(k = 0; k < shadow->dst_transition_list->len; k++){
1283 transition = shadow->dst_transition_list->pdata[k];
1284 g_print("state_%d -> state_%d"
1285 " [style=dotted,label=\"%s\"]\n",
1286 state->id,
1287 transition->input->id,
1288 transition->name);
1289 }
1290 }
1291 }
1292 g_print("}\n");
1293 g_print("// --- END OF GRAPHVIZ DUMP ---\n");
1294 return;
1295 }
1296 /* FIXME: include display of portals and spans
1297 * with peripheries=2 etc
1298 */
1299
C4_Model_open(C4_Model * model)1300 void C4_Model_open(C4_Model *model){
1301 g_assert(model);
1302 g_assert(!model->is_open);
1303 model->is_open = TRUE;
1304 return;
1305 }
1306
C4_Model_path_is_possible_recur(C4_Model * model,C4_State * src,C4_State * dst,gboolean * visited)1307 static gboolean C4_Model_path_is_possible_recur(C4_Model *model,
1308 C4_State *src, C4_State *dst, gboolean *visited){
1309 register C4_Transition *transition;
1310 register C4_State *next_state;
1311 register gint i;
1312 visited[src->id] = TRUE;
1313 for(i = 0; i < src->output_transition_list->len; i++){
1314 transition = src->output_transition_list->pdata[i];
1315 next_state = transition->output;
1316 if(next_state == dst)
1317 return TRUE;
1318 if(!visited[next_state->id]){
1319 if(C4_Model_path_is_possible_recur(model,
1320 next_state, dst, visited)){
1321 return TRUE;
1322 }
1323 }
1324 }
1325 return FALSE;
1326 }
1327 /* Assumes that state->id is set */
1328
C4_Model_path_is_possible(C4_Model * model,C4_State * src,C4_State * dst)1329 gboolean C4_Model_path_is_possible(C4_Model *model,
1330 C4_State *src, C4_State *dst){
1331 register gboolean *visited;
1332 register gboolean is_valid;
1333 g_assert(model);
1334 g_assert(src);
1335 g_assert(dst);
1336 visited = g_new0(gboolean, model->state_list->len);
1337 is_valid = C4_Model_path_is_possible_recur(model, src, dst,
1338 visited);
1339 g_free(visited);
1340 return is_valid;
1341 }
1342
C4_Model_has_start_to_end_path(C4_Model * model)1343 static gboolean C4_Model_has_start_to_end_path(C4_Model *model){
1344 return C4_Model_path_is_possible(model,
1345 model->start_state->state,
1346 model->end_state->state);
1347 }
1348
C4_Model_set_ids(C4_Model * model)1349 static void C4_Model_set_ids(C4_Model *model){
1350 register gint i;
1351 register C4_State *state;
1352 register C4_Transition *transition;
1353 register C4_Shadow *shadow;
1354 register C4_Calc *calc;
1355 register C4_Portal *portal;
1356 register C4_Span *span;
1357 g_assert(model);
1358 for(i = 0; i < model->state_list->len; i++){
1359 state = model->state_list->pdata[i];
1360 state->id = i;
1361 }
1362 for(i = 0; i < model->transition_list->len; i++){
1363 transition = model->transition_list->pdata[i];
1364 transition->id = i;
1365 }
1366 for(i = 0; i < model->shadow_list->len; i++){
1367 shadow = model->shadow_list->pdata[i];
1368 shadow->id = i;
1369 }
1370 for(i = 0; i < model->calc_list->len; i++){
1371 calc = model->calc_list->pdata[i];
1372 calc->id = i;
1373 }
1374 for(i = 0; i < model->portal_list->len; i++){
1375 portal = model->portal_list->pdata[i];
1376 portal->id = i;
1377 }
1378 for(i = 0; i < model->span_list->len; i++){
1379 span = model->span_list->pdata[i];
1380 span->id = i;
1381 }
1382 return;
1383 }
1384
C4_Model_is_valid(C4_Model * model)1385 static gboolean C4_Model_is_valid(C4_Model *model){
1386 register gint i;
1387 register C4_State *state;
1388 g_assert(model);
1389 for(i = 0; i < model->state_list->len; i++){
1390 state = model->state_list->pdata[i];
1391 /* All states except start must have input transitions */
1392 if(state == model->start_state->state)
1393 g_assert(!state->input_transition_list->len);
1394 else
1395 g_assert(state->input_transition_list->len);
1396 /* All states except end must have output transitions */
1397 if(state == model->end_state->state)
1398 g_assert(!state->output_transition_list->len);
1399 else
1400 g_assert(state->output_transition_list->len);
1401 }
1402 return TRUE;
1403 }
1404
c4_g_ptr_array_reverse(GPtrArray * ptr_array)1405 static void c4_g_ptr_array_reverse(GPtrArray *ptr_array){
1406 register gint a, z;
1407 register gpointer swap;
1408 for(a = 0, z = ptr_array->len-1; a < z; a++, z--){
1409 swap = ptr_array->pdata[a];
1410 ptr_array->pdata[a] = ptr_array->pdata[z];
1411 ptr_array->pdata[z] = swap;
1412 }
1413 return;
1414 }
1415
1416 /* Calculate dependency ordering and transition precedence:
1417 */
C4_Model_topological_sort(C4_Model * model)1418 static void C4_Model_topological_sort(C4_Model *model){
1419 register gint *dependent
1420 = g_new0(gint, model->transition_list->len);
1421 register GPtrArray *ordered = g_ptr_array_new();
1422 register gint i, j;
1423 register C4_Transition *transition, *input_transition;
1424 register C4_State *state;
1425 register gboolean removed_transition;
1426 /**/
1427 /* Set initial dependencies */
1428 for(i = 0; i < model->transition_list->len; i++){
1429 transition = model->transition_list->pdata[i];
1430 if((transition->advance_query == 0)
1431 && (transition->advance_target == 0)){
1432 state = transition->input;
1433 for(j = 0; j < state->input_transition_list->len; j++){
1434 input_transition
1435 = state->input_transition_list->pdata[j];
1436 if((input_transition->advance_query == 0)
1437 && (input_transition->advance_target == 0)){
1438 dependent[input_transition->id]++;
1439 }
1440 }
1441 }
1442 }
1443 /* Perform topological sort of static transitions */
1444 do {
1445 removed_transition = FALSE;
1446 for(i = 0; i < model->transition_list->len; i++){
1447 if(dependent[i] != 0)
1448 continue;
1449 transition = model->transition_list->pdata[i];
1450 if((transition->advance_query != 0)
1451 || (transition->advance_target != 0))
1452 continue;
1453 removed_transition = TRUE;
1454 dependent[transition->id] = -1;
1455 g_ptr_array_add(ordered, transition);
1456 state = transition->input;
1457 for(j = 0; j < state->input_transition_list->len; j++){
1458 input_transition
1459 = state->input_transition_list->pdata[j];
1460 if((transition->advance_query == 0)
1461 && (transition->advance_target == 0))
1462 dependent[input_transition->id]--;
1463 }
1464 }
1465 } while(removed_transition);
1466 /* Take the precedence zero transitions */
1467 for(i = 0; i < model->transition_list->len; i++){
1468 transition = model->transition_list->pdata[i];
1469 if(transition->advance_query || transition->advance_target)
1470 g_ptr_array_add(ordered, transition);
1471 }
1472 /**/
1473 c4_g_ptr_array_reverse(ordered);
1474 /* Assert that there are no cycles */
1475 g_assert(ordered->len == model->transition_list->len);
1476 /* Reorder the transition list */
1477 for(i = 0; i < ordered->len; i++){
1478 transition = ordered->pdata[i];
1479 transition->id = i;
1480 model->transition_list->pdata[i] = transition;
1481 }
1482 /**/
1483 g_ptr_array_free(ordered, TRUE);
1484 g_free(dependent);
1485 return;
1486 }
1487 /* FIXME: optimisation:
1488 * transitions are only ordered;
1489 * may wish to store precedence info instead
1490 * to allow some optimisations.
1491 */
1492
C4_Portal_find_transitions(C4_Portal * portal,C4_Model * model)1493 static void C4_Portal_find_transitions(C4_Portal *portal,
1494 C4_Model *model){
1495 register gint i;
1496 register C4_Transition *transition;
1497 /* Find applicable transitions for portal->calc */
1498 for(i = 0; i < model->transition_list->len; i++){
1499 transition = model->transition_list->pdata[i];
1500 if((transition->calc == portal->calc)
1501 && (transition->input == transition->output)){
1502 g_assert(transition->advance_query
1503 == portal->advance_query);
1504 g_assert(transition->advance_target
1505 == portal->advance_target);
1506 g_ptr_array_add(portal->transition_list, transition);
1507 }
1508 }
1509 g_assert(portal->transition_list->len);
1510 return;
1511 }
1512
C4_Model_finalise(C4_Model * model)1513 static void C4_Model_finalise(C4_Model *model){
1514 register gint i;
1515 register C4_Portal *portal;
1516 register C4_Transition *transition;
1517 g_assert(model);
1518 for(i = 0; i < model->portal_list->len; i++){
1519 portal = model->portal_list->pdata[i];
1520 if(portal->transition_list->len)
1521 g_ptr_array_set_size(portal->transition_list, 0);
1522 C4_Portal_find_transitions(portal, model);
1523 }
1524 model->max_query_advance = 0;
1525 model->max_target_advance = 0;
1526 for(i = 0; i < model->transition_list->len; i++){
1527 transition = model->transition_list->pdata[i];
1528 if(model->max_query_advance < transition->advance_query)
1529 model->max_query_advance = transition->advance_query;
1530 if(model->max_target_advance < transition->advance_target)
1531 model->max_target_advance = transition->advance_target;
1532 }
1533 g_assert(model->max_query_advance || model->max_target_advance);
1534 return;
1535 }
1536
1537 /**/
1538
C4_Shadow_designate_recur(C4_Shadow * shadow,C4_Transition * transition,gboolean * des,gboolean * states_visited)1539 static void C4_Shadow_designate_recur(C4_Shadow *shadow,
1540 C4_Transition *transition,
1541 gboolean *des,
1542 gboolean *states_visited){
1543 register gint i;
1544 register C4_State *state = transition->input;
1545 if(!states_visited[state->id]){
1546 states_visited[state->id] = TRUE;
1547 /* If transition is an dst transition stop */
1548 for(i = 0; i < transition->dst_shadow_list->len; i++){
1549 if(shadow == transition->dst_shadow_list->pdata[i])
1550 return;
1551 }
1552 /* Visit input transitions of input state */
1553 for(i = 0; i < state->input_transition_list->len; i++){
1554 transition = state->input_transition_list->pdata[i];
1555 g_assert(!des[transition->id]);
1556 des[transition->id] = TRUE;
1557 C4_Shadow_designate_recur(shadow, transition,
1558 des, states_visited);
1559 }
1560 }
1561 return;
1562 }
1563
C4_Shadow_get_designation(C4_Model * model,C4_Shadow * shadow)1564 static gboolean *C4_Shadow_get_designation(C4_Model *model,
1565 C4_Shadow *shadow){
1566 register gboolean *des = g_new0(gboolean,
1567 model->transition_list->len);
1568 register gboolean *states_visited = g_new0(gboolean,
1569 model->state_list->len);
1570 register gint i;
1571 register C4_Transition *transition;
1572 g_assert(C4_Shadow_is_valid(shadow, model));
1573 for(i = 0; i < shadow->dst_transition_list->len; i++){
1574 transition = shadow->dst_transition_list->pdata[i];
1575 des[transition->id] = TRUE;
1576 C4_Shadow_designate_recur(shadow, transition,
1577 des, states_visited);
1578 }
1579 g_free(states_visited);
1580 return des;
1581 }
1582
C4_Shadow_designation_fits(C4_Model * model,gboolean * des_a,gboolean * des_b)1583 static gboolean C4_Shadow_designation_fits(C4_Model *model,
1584 gboolean *des_a, gboolean *des_b){
1585 register gint i;
1586 register gboolean *state_is_used;
1587 register C4_Transition *transition;
1588 for(i = 0; i < model->transition_list->len; i++)
1589 if(des_a[i] && des_b[i])
1590 return FALSE;
1591 state_is_used = g_new0(gboolean, model->state_list->len);
1592 /* Fail if any des_a output states are des_b inputs */
1593 for(i = 0; i < model->transition_list->len; i++)
1594 if(des_a[i]){
1595 transition = model->transition_list->pdata[i];
1596 state_is_used[transition->output->id] = TRUE;
1597 }
1598 for(i = 0; i < model->transition_list->len; i++)
1599 if(des_b[i]){
1600 transition = model->transition_list->pdata[i];
1601 if(state_is_used[transition->input->id]){
1602 g_free(state_is_used);
1603 return FALSE;
1604 }
1605 }
1606 for(i = 0; i < model->state_list->len; i++)
1607 state_is_used[i] = FALSE;
1608 /* Fail if any des_b output states are des_a inputs */
1609 for(i = 0; i < model->transition_list->len; i++)
1610 if(des_b[i]){
1611 transition = model->transition_list->pdata[i];
1612 state_is_used[transition->output->id] = TRUE;
1613 }
1614 for(i = 0; i < model->transition_list->len; i++)
1615 if(des_a[i]){
1616 transition = model->transition_list->pdata[i];
1617 if(state_is_used[transition->input->id]){
1618 g_free(state_is_used);
1619 return FALSE;
1620 }
1621 }
1622 g_free(state_is_used);
1623 return TRUE;
1624 }
1625
C4_Shadow_designation_join(C4_Model * model,gboolean * master,gboolean * copy)1626 static void C4_Shadow_designation_join(C4_Model *model,
1627 gboolean *master, gboolean *copy){
1628 register gint i;
1629 for(i = 0; i < model->transition_list->len; i++){
1630 if(copy[i]){
1631 g_assert(!master[i]);
1632 master[i] = TRUE;
1633 }
1634 }
1635 return;
1636 }
1637
C4_Model_designate_shadows(C4_Model * model)1638 static void C4_Model_designate_shadows(C4_Model *model){
1639 register gboolean *des, *curr_des;
1640 register GPtrArray *designation_list = g_ptr_array_new();
1641 register gint i, j;
1642 register C4_Shadow *shadow;
1643 for(i = 0; i < model->shadow_list->len; i++){
1644 shadow = model->shadow_list->pdata[i];
1645 curr_des = C4_Shadow_get_designation(model, shadow);
1646 shadow->designation = -1;
1647 for(j = 0; j < designation_list->len; j++){
1648 des = designation_list->pdata[j];
1649 if(C4_Shadow_designation_fits(model, des, curr_des)){
1650 C4_Shadow_designation_join(model, des, curr_des);
1651 shadow->designation = j;
1652 break;
1653 }
1654 }
1655 if(shadow->designation == -1){ /* not designated */
1656 shadow->designation = designation_list->len;
1657 g_ptr_array_add(designation_list, curr_des);
1658 } else {
1659 g_free(curr_des);
1660 }
1661 }
1662 model->total_shadow_designations = designation_list->len;
1663 for(i = 0; i < designation_list->len; i++)
1664 g_free(designation_list->pdata[i]);
1665 g_ptr_array_free(designation_list, TRUE);
1666 return;
1667 }
1668
C4_Model_close(C4_Model * model)1669 void C4_Model_close(C4_Model *model){
1670 g_assert(model);
1671 g_assert(model->is_open);
1672 g_assert(C4_Model_is_valid(model));
1673 C4_Model_set_ids(model);
1674 g_assert(C4_Model_has_start_to_end_path(model));
1675 C4_Model_topological_sort(model);
1676 C4_Model_designate_shadows(model);
1677 C4_Model_finalise(model);
1678 model->is_open = FALSE;
1679 return;
1680 }
1681
1682 /**/
1683
C4_Calc_init(C4_Calc * calc,Region * region,gpointer user_data)1684 void C4_Calc_init(C4_Calc *calc, Region *region, gpointer user_data){
1685 if(!calc)
1686 return;
1687 if(calc->init_func)
1688 calc->init_func(region, user_data);
1689 return;
1690 }
1691
C4_Calc_exit(C4_Calc * calc,Region * region,gpointer user_data)1692 void C4_Calc_exit(C4_Calc *calc, Region *region, gpointer user_data){
1693 if(!calc)
1694 return;
1695 if(calc->exit_func)
1696 calc->exit_func(region, user_data);
1697 return;
1698 }
1699
C4_Calc_score(C4_Calc * calc,gint query_pos,gint target_pos,gpointer user_data)1700 C4_Score C4_Calc_score(C4_Calc *calc, gint query_pos, gint target_pos,
1701 gpointer user_data){
1702 register C4_Score score;
1703 if(!calc)
1704 return 0;
1705 if(calc->calc_func){
1706 score = calc->calc_func(query_pos, target_pos, user_data);
1707 g_assert(score <= calc->max_score);
1708 return score;
1709 }
1710 return calc->max_score;
1711 }
1712
C4_Model_copy(C4_Model * old_model)1713 C4_Model *C4_Model_copy(C4_Model *old_model){
1714 register C4_Model *new_model;
1715 register gchar *name;
1716 register gint i, j;
1717 register C4_Calc *calc, **calc_map = g_new0(C4_Calc*,
1718 old_model->calc_list->len);
1719 register C4_State *state, **state_map = g_new0(C4_State*,
1720 old_model->state_list->len);
1721 register C4_State *src_state, *dst_state;
1722 register C4_Transition *transition,
1723 **transition_map = g_new0(C4_Transition*,
1724 old_model->transition_list->len);
1725 register C4_Shadow *shadow, *new_shadow;
1726 register C4_Portal *portal;
1727 register C4_Span *span;
1728 g_assert(old_model);
1729 g_assert(!old_model->is_open);
1730 name = g_strdup_printf("Copy:%s", old_model->name);
1731 new_model = C4_Model_create(name);
1732 g_free(name);
1733 /* Copy calcs */
1734 for(i = 0; i < old_model->calc_list->len; i++){
1735 calc = old_model->calc_list->pdata[i];
1736 calc_map[i] = C4_Model_add_calc(new_model, calc->name,
1737 calc->max_score,
1738 calc->calc_func, calc->calc_macro,
1739 calc->init_func, calc->init_macro,
1740 calc->exit_func, calc->exit_macro,
1741 calc->protect);
1742 }
1743 /* Copy states */
1744 for(i = 0; i < old_model->state_list->len; i++){
1745 state = old_model->state_list->pdata[i];
1746 if((state == old_model->start_state->state)
1747 || (state == old_model->end_state->state))
1748 continue;
1749 state_map[i] = C4_Model_add_state(new_model, state->name);
1750 }
1751 /* Copy transitions */
1752 for(i = 0; i < old_model->transition_list->len; i++){
1753 transition = old_model->transition_list->pdata[i];
1754 if(transition->input == old_model->start_state->state)
1755 src_state = NULL;
1756 else
1757 src_state = state_map[transition->input->id];
1758 if(transition->output == old_model->end_state->state)
1759 dst_state = NULL;
1760 else
1761 dst_state = state_map[transition->output->id];
1762 transition_map[i]
1763 = C4_Model_add_transition(new_model, transition->name,
1764 src_state, dst_state,
1765 transition->advance_query, transition->advance_target,
1766 transition->calc?calc_map[transition->calc->id]:NULL,
1767 transition->label, transition->label_data);
1768 }
1769 /* Copy shadows */
1770 for(i = 0; i < old_model->shadow_list->len; i++){
1771 shadow = old_model->shadow_list->pdata[i];
1772 state = shadow->src_state_list->pdata[0];
1773 transition = shadow->dst_transition_list->pdata[0];
1774 new_shadow = C4_Model_add_shadow(new_model, shadow->name,
1775 state_map[state->id], transition_map[transition->id],
1776 shadow->start_func, shadow->start_macro,
1777 shadow->end_func, shadow->end_macro);
1778 for(j = 1; j < shadow->src_state_list->len; j++){
1779 state = shadow->src_state_list->pdata[j];
1780 C4_Shadow_add_src_state(new_shadow, state_map[state->id]);
1781 }
1782 for(j = 1; j < shadow->dst_transition_list->len; j++){
1783 transition = shadow->dst_transition_list->pdata[j];
1784 C4_Shadow_add_dst_transition(new_shadow,
1785 transition_map[transition->id]);
1786 }
1787 }
1788 /* Copy portals */
1789 for(i = 0; i < old_model->portal_list->len; i++){
1790 portal = old_model->portal_list->pdata[i];
1791 C4_Model_add_portal(new_model, portal->name,
1792 calc_map[portal->calc->id],
1793 portal->advance_query, portal->advance_target);
1794 }
1795 /* Copy spans */
1796 for(i = 0; i < old_model->span_list->len; i++){
1797 span = old_model->span_list->pdata[i];
1798 C4_Model_add_span(new_model, span->name,
1799 state_map[span->span_state->id],
1800 span->min_query, span->max_query,
1801 span->min_target, span->max_target);
1802 }
1803 /* Configure extras */
1804 C4_Model_merge_codegen(new_model, old_model);
1805 C4_Model_configure_extra(new_model,
1806 old_model->init_func, old_model->init_macro,
1807 old_model->exit_func, old_model->exit_macro);
1808 /* Configure start and end states */
1809 C4_Model_configure_start_state(new_model,
1810 old_model->start_state->scope,
1811 old_model->start_state->cell_start_func,
1812 old_model->start_state->cell_start_macro);
1813 C4_Model_configure_end_state(new_model,
1814 old_model->end_state->scope,
1815 old_model->end_state->cell_end_func,
1816 old_model->end_state->cell_end_macro);
1817 g_free(calc_map);
1818 g_free(state_map);
1819 g_free(transition_map);
1820 /* Close the model without a topological sort */
1821 C4_Model_set_ids(new_model);
1822 C4_Model_designate_shadows(new_model);
1823 C4_Model_finalise(new_model);
1824 new_model->is_open = FALSE;
1825 return new_model;
1826 }
1827
1828 /**/
1829
C4_Model_remove_transition(C4_Model * model,C4_Transition * transition)1830 void C4_Model_remove_transition(C4_Model *model,
1831 C4_Transition *transition){
1832 register gboolean removed_transition;
1833 /* Remove from the input state */
1834 removed_transition = g_ptr_array_remove_fast(
1835 transition->input->output_transition_list, transition);
1836 g_assert(removed_transition);
1837 /* Remove from the output state */
1838 removed_transition = g_ptr_array_remove_fast(
1839 transition->output->input_transition_list, transition);
1840 g_assert(removed_transition);
1841 /* Remove from the Model */
1842 removed_transition = g_ptr_array_remove_fast(model->transition_list,
1843 transition);
1844 g_assert(removed_transition);
1845 C4_Transition_destroy(transition);
1846 return;
1847 }
1848
C4_Model_remove_shadow(C4_Model * model,C4_Shadow * shadow)1849 static void C4_Model_remove_shadow(C4_Model *model,
1850 C4_Shadow *shadow){
1851 register gint i;
1852 register gboolean removed_shadow;
1853 register C4_State *state;
1854 register C4_Transition *transition;
1855 /* Remove from src states */
1856 for(i = 0; i < shadow->src_state_list->len; i++){
1857 state = shadow->src_state_list->pdata[i];
1858 removed_shadow = g_ptr_array_remove_fast(
1859 state->src_shadow_list, shadow);
1860 g_assert(removed_shadow);
1861 }
1862 /* Remove from dst transitions */
1863 for(i = 0; i < shadow->dst_transition_list->len; i++){
1864 transition = shadow->dst_transition_list->pdata[i];
1865 removed_shadow = g_ptr_array_remove_fast(
1866 transition->dst_shadow_list, shadow);
1867 g_assert(removed_shadow);
1868 }
1869 /* Remove from the Model */
1870 removed_shadow = g_ptr_array_remove_fast(model->shadow_list,
1871 shadow);
1872 g_assert(removed_shadow);
1873 C4_Shadow_destroy(shadow);
1874 return;
1875 }
1876
C4_Model_remove_state(C4_Model * model,C4_State * state)1877 void C4_Model_remove_state(C4_Model *model, C4_State *state){
1878 register gboolean was_open, removed_state;
1879 register gint i;
1880 register C4_Transition *transition;
1881 register C4_Shadow *shadow;
1882 register C4_Calc *calc;
1883 register C4_Portal *portal;
1884 register C4_Span *span;
1885 register gboolean *calc_used;
1886 /* Check not start or end */
1887 g_assert(model);
1888 g_assert(state);
1889 g_assert(state != model->start_state->state);
1890 g_assert(state != model->end_state->state);
1891 /* Open model if not open */
1892 was_open = model->is_open;
1893 if(!was_open)
1894 C4_Model_open(model);
1895 /* Remove from state */
1896 removed_state = g_ptr_array_remove_fast(model->state_list, state);
1897 g_assert(removed_state);
1898 /* Remove unused transitions */
1899 for(i = 0; i < state->input_transition_list->len; i++){
1900 transition = state->input_transition_list->pdata[i];
1901 C4_Model_remove_transition(model, transition);
1902 }
1903 for(i = 0; i < state->output_transition_list->len; i++){
1904 transition = state->input_transition_list->pdata[i];
1905 C4_Model_remove_transition(model, transition);
1906 }
1907 /* Remove state from shadows */
1908 for(i = 0; i < state->src_shadow_list->len; i++){
1909 shadow = state->src_shadow_list->pdata[i];
1910 if(shadow->src_state_list->len == 1){ /* Remove entire shadow */
1911 C4_Model_remove_shadow(model, shadow);
1912 } else { /* Remove state from shadow state list */
1913 removed_state = g_ptr_array_remove_fast(
1914 shadow->src_state_list, state);
1915 g_assert(removed_state);
1916 }
1917 }
1918 /* Remove unused calcs */
1919 calc_used = g_new0(gboolean, model->calc_list->len);
1920 for(i = 0; i < model->calc_list->len; i++){
1921 calc = model->calc_list->pdata[i];
1922 calc->id = i;
1923 }
1924 for(i = 0; i < model->transition_list->len; i++){
1925 transition = model->transition_list->pdata[i];
1926 calc_used[transition->calc->id] = TRUE;
1927 }
1928 for(i = model->calc_list->len-1; i >= 0; i--){
1929 if(!calc_used[i]){
1930 calc = model->calc_list->pdata[i];
1931 g_ptr_array_remove_fast(model->calc_list, calc);
1932 C4_Calc_destroy(calc);
1933 }
1934 }
1935 /* Remove unused portals */
1936 for(i = model->portal_list->len; i >= 0; i--){
1937 portal = model->portal_list->pdata[i];
1938 if(!calc_used[portal->calc->id]){
1939 g_ptr_array_remove_fast(model->portal_list, portal);
1940 C4_Portal_destroy(portal);
1941 }
1942 }
1943 g_free(calc_used);
1944 /* Remove related spans */
1945 for(i = model->span_list->len-1; i >= 0; i--){
1946 span = model->span_list->pdata[i];
1947 if(span->span_state == state){
1948 g_ptr_array_remove_fast(model->span_list, span);
1949 C4_Span_destroy(span);
1950 }
1951 }
1952 /* Close model */
1953 if(!was_open)
1954 C4_Model_close(model);
1955 C4_State_destroy(state);
1956 return;
1957 }
1958
C4_Model_is_global(C4_Model * model)1959 gboolean C4_Model_is_global(C4_Model *model){
1960 if(model->start_state->scope != C4_Scope_CORNER)
1961 return FALSE;
1962 if(model->end_state->scope != C4_Scope_CORNER)
1963 return FALSE;
1964 return TRUE;
1965 }
1966
C4_Model_is_local(C4_Model * model)1967 gboolean C4_Model_is_local(C4_Model *model){
1968 if(model->start_state->scope != C4_Scope_ANYWHERE)
1969 return FALSE;
1970 if(model->end_state->scope != C4_Scope_ANYWHERE)
1971 return FALSE;
1972 return TRUE;
1973 }
1974
C4_Model_remove_all_shadows(C4_Model * model)1975 void C4_Model_remove_all_shadows(C4_Model *model){
1976 register C4_Shadow *shadow;
1977 g_assert(model->is_open);
1978 while(model->shadow_list->len){
1979 shadow = model->shadow_list->pdata[0];
1980 g_assert(shadow);
1981 C4_Model_remove_shadow(model, shadow);
1982 }
1983 return;
1984 }
1985
1986 /**/
1987
1988 typedef struct {
1989 GPtrArray *new_src_state_list;
1990 GPtrArray *new_dst_transition_list;
1991 } C4_ProtoShadow;
1992
C4_ProtoShadow_create(void)1993 static C4_ProtoShadow *C4_ProtoShadow_create(void){
1994 register C4_ProtoShadow *cps = g_new(C4_ProtoShadow, 1);
1995 cps->new_src_state_list = g_ptr_array_new();
1996 cps->new_dst_transition_list = g_ptr_array_new();
1997 return cps;
1998 }
1999
C4_ProtoShadow_destroy(C4_ProtoShadow * cps)2000 static void C4_ProtoShadow_destroy(C4_ProtoShadow *cps){
2001 g_ptr_array_free(cps->new_src_state_list, TRUE);
2002 g_ptr_array_free(cps->new_dst_transition_list, TRUE);
2003 g_free(cps);
2004 return;
2005 }
2006
C4_ProtoShadow_add_state(C4_ProtoShadow * cps,C4_State * state)2007 static void C4_ProtoShadow_add_state(C4_ProtoShadow *cps,
2008 C4_State *state){
2009 g_ptr_array_add(cps->new_src_state_list, state);
2010 return;
2011 }
2012
C4_ProtoShadow_add_transition(C4_ProtoShadow * cps,C4_Transition * transition)2013 static void C4_ProtoShadow_add_transition(C4_ProtoShadow *cps,
2014 C4_Transition *transition){
2015 g_ptr_array_add(cps->new_dst_transition_list, transition);
2016 return;
2017 }
2018
C4_ProtoShadow_generate(C4_ProtoShadow * cps,C4_Model * old_model,C4_Model * new_model,C4_Shadow * old_shadow)2019 static void C4_ProtoShadow_generate(C4_ProtoShadow *cps,
2020 C4_Model *old_model,
2021 C4_Model *new_model,
2022 C4_Shadow *old_shadow){
2023 register gint i;
2024 register C4_Shadow *new_shadow;
2025 g_assert(cps);
2026 g_assert(cps->new_src_state_list->len);
2027 g_assert(cps->new_dst_transition_list->len);
2028 new_shadow = C4_Model_add_shadow(new_model,
2029 old_shadow->name,
2030 cps->new_src_state_list->pdata[0],
2031 cps->new_dst_transition_list->pdata[0],
2032 old_shadow->start_func, old_shadow->start_macro,
2033 old_shadow->end_func, old_shadow->end_macro);
2034 for(i = 1; i < cps->new_src_state_list->len; i++)
2035 C4_Shadow_add_src_state(new_shadow,
2036 cps->new_src_state_list->pdata[i]);
2037 for(i = 1; i < cps->new_dst_transition_list->len; i++)
2038 C4_Shadow_add_dst_transition(new_shadow,
2039 cps->new_dst_transition_list->pdata[i]);
2040 return;
2041 }
2042
2043 /**/
2044
C4_Model_segment_reuse_state(C4_Model * old_model,C4_Model * new_model,C4_State * old_state,C4_State ** state_map,C4_ProtoShadow ** proto_shadow_map)2045 static void C4_Model_segment_reuse_state(C4_Model *old_model,
2046 C4_Model *new_model,
2047 C4_State *old_state,
2048 C4_State **state_map,
2049 C4_ProtoShadow **proto_shadow_map){
2050 register C4_State *new_state;
2051 register gint i;
2052 register C4_Shadow *shadow;
2053 if(old_state == old_model->start_state->state)
2054 return;
2055 if(old_state == old_model->end_state->state)
2056 return;
2057 if(state_map[old_state->id]) /* Already reused */
2058 return;
2059 new_state = C4_Model_add_state(new_model, old_state->name);
2060 state_map[old_state->id] = new_state;
2061 for(i = 0; i < old_state->src_shadow_list->len; i++){
2062 shadow = old_state->src_shadow_list->pdata[i];
2063 if(!proto_shadow_map[shadow->id])
2064 proto_shadow_map[shadow->id] = C4_ProtoShadow_create();
2065 C4_ProtoShadow_add_state(proto_shadow_map[shadow->id],
2066 new_state);
2067 }
2068 return;
2069 }
2070
C4_Model_segment_add_transition(C4_Model * old_model,C4_Model * new_model,C4_Transition * transition,C4_State ** state_map,C4_Calc ** calc_map,GTree * transition_map_tree,C4_ProtoShadow ** proto_shadow_map,gboolean from_start,gboolean to_end)2071 static void C4_Model_segment_add_transition(C4_Model *old_model,
2072 C4_Model *new_model,
2073 C4_Transition *transition, C4_State **state_map,
2074 C4_Calc **calc_map, GTree *transition_map_tree,
2075 C4_ProtoShadow **proto_shadow_map,
2076 gboolean from_start, gboolean to_end){
2077 register C4_Calc *calc = NULL;
2078 register C4_Transition *new_transition;
2079 register gint i;
2080 register C4_Shadow *shadow;
2081 if(!from_start)
2082 C4_Model_segment_reuse_state(old_model, new_model,
2083 transition->input, state_map,
2084 proto_shadow_map);
2085 if(!to_end)
2086 C4_Model_segment_reuse_state(old_model, new_model,
2087 transition->output, state_map,
2088 proto_shadow_map);
2089 if(transition->calc){
2090 if(!calc_map[transition->calc->id]){
2091 calc_map[transition->calc->id]
2092 = C4_Model_add_calc(new_model,
2093 transition->calc->name,
2094 transition->calc->max_score,
2095 transition->calc->calc_func,
2096 transition->calc->calc_macro,
2097 transition->calc->init_func,
2098 transition->calc->init_macro,
2099 transition->calc->exit_func,
2100 transition->calc->exit_macro,
2101 transition->calc->protect);
2102 }
2103 calc = calc_map[transition->calc->id];
2104 }
2105 new_transition = C4_Model_add_transition(new_model,
2106 transition->name,
2107 from_start?NULL:state_map[transition->input->id],
2108 to_end?NULL:state_map[transition->output->id],
2109 transition->advance_query, transition->advance_target,
2110 calc, transition->label, transition->label_data);
2111 g_tree_insert(transition_map_tree, new_transition, transition);
2112 for(i = 0; i < transition->dst_shadow_list->len; i++){
2113 shadow = transition->dst_shadow_list->pdata[i];
2114 if(!proto_shadow_map[shadow->id])
2115 proto_shadow_map[shadow->id] = C4_ProtoShadow_create();
2116 C4_ProtoShadow_add_transition(proto_shadow_map[shadow->id],
2117 new_transition);
2118 }
2119 return;
2120 }
2121
C4_Model_segment_recur(C4_Model * old_model,C4_Model * new_model,C4_State * state,gboolean * visited_state,C4_State ** state_map,C4_Calc ** calc_map,GTree * transition_map_tree,C4_ProtoShadow ** proto_shadow_map)2122 static void C4_Model_segment_recur(C4_Model *old_model,
2123 C4_Model *new_model,
2124 C4_State *state,
2125 gboolean *visited_state,
2126 C4_State **state_map,
2127 C4_Calc **calc_map,
2128 GTree *transition_map_tree,
2129 C4_ProtoShadow **proto_shadow_map){
2130 register gint i;
2131 register C4_Transition *transition;
2132 if(!state_map[state->id]) /* Check that it is on the state map */
2133 return;
2134 if(visited_state[state->id]) /* Check is it not already visited */
2135 return;
2136 if(state == old_model->start_state->state)
2137 return;
2138 if(state == old_model->end_state->state)
2139 return;
2140 visited_state[state->id] = TRUE;
2141 for(i = 0; i < state->output_transition_list->len; i++){
2142 transition = state->output_transition_list->pdata[i];
2143 if(transition->output == old_model->end_state->state)
2144 continue;
2145 C4_Model_segment_add_transition(old_model, new_model,
2146 transition, state_map, calc_map,
2147 transition_map_tree, proto_shadow_map, FALSE, FALSE);
2148 C4_Model_segment_recur(old_model, new_model,
2149 transition->output,
2150 visited_state, state_map, calc_map,
2151 transition_map_tree, proto_shadow_map);
2152 }
2153 return;
2154 }
2155
2156 #if 0
2157 /* FIXME: not currently used */
2158
2159 static void C4_State_remove_duplicate_transitions(C4_State *state,
2160 C4_Model *model, GPtrArray *to_remove){
2161 register gint i, j;
2162 register C4_Score score_a, score_b;
2163 register C4_Transition *transition_a, *transition_b;
2164 for(i = 0; i < state->output_transition_list->len; i++){
2165 transition_a = state->output_transition_list->pdata[i];
2166 for(j = 0; j < i; j++){
2167 transition_b = state->output_transition_list->pdata[j];
2168 if(transition_a->output != transition_b->output)
2169 continue;
2170 if(transition_a->advance_query
2171 != transition_b->advance_query)
2172 continue;
2173 if(transition_a->advance_target
2174 != transition_b->advance_target)
2175 continue;
2176 if(transition_a->calc == transition_b->calc)
2177 C4_Model_remove_transition(model, transition_b);
2178 if(transition_a->calc && transition_a->calc->calc_func)
2179 continue;
2180 if(transition_b->calc && transition_b->calc->calc_func)
2181 continue;
2182 score_a = transition_a->calc ? transition_a->calc->max_score
2183 : 0;
2184 score_b = transition_b->calc ? transition_b->calc->max_score
2185 : 0;
2186 if(score_a > score_b){
2187 g_ptr_array_add(to_remove, transition_b);
2188 } else {
2189 g_ptr_array_add(to_remove, transition_a);
2190 }
2191 }
2192 }
2193 return;
2194 }
2195
2196 static void C4_Model_remove_duplicate_transitions(C4_Model *model){
2197 register gint i;
2198 register C4_State *state;
2199 register C4_Transition *transition;
2200 register GPtrArray *to_remove = g_ptr_array_new();
2201 /* Find transitions to remove */
2202 for(i = 0; i < model->state_list->len; i++){
2203 state = model->state_list->pdata[i];
2204 C4_State_remove_duplicate_transitions(state, model, to_remove);
2205 }
2206 /* Remove transitions from the model */
2207 for(i = 0; i < to_remove->len; i++){
2208 transition = to_remove->pdata[i];
2209 C4_Model_remove_transition(model, transition);
2210 }
2211 g_ptr_array_free(to_remove, TRUE);
2212 return;
2213 }
2214
2215 #endif /* 0 */
2216
C4_Model_select(C4_Model * model,C4_State * src,C4_State * dst,C4_State ** state_map,GTree * transition_map_tree)2217 static C4_Model *C4_Model_select(C4_Model *model,
2218 C4_State *src, C4_State *dst,
2219 C4_State **state_map,
2220 GTree *transition_map_tree){
2221 register gchar *name = g_strdup_printf(
2222 "Segment(\"%s\"->\"%s\"):[%s]",
2223 src->name, dst->name, model->name);
2224 register C4_Model *segment_model = C4_Model_create(name);
2225 register C4_Transition *transition;
2226 register gboolean *visited_state = g_new0(gboolean,
2227 model->state_list->len);
2228 register C4_State *state;
2229 register C4_Calc **calc_map = g_new0(C4_Calc*,
2230 model->calc_list->len);
2231 register gint i;
2232 register C4_Shadow *shadow;
2233 register C4_ProtoShadow **proto_shadow_map = g_new0(C4_ProtoShadow*,
2234 model->shadow_list->len);
2235 /* Propagate model extras */
2236 C4_Model_configure_extra(segment_model,
2237 model->init_func, model->init_macro,
2238 model->exit_func, model->exit_macro);
2239 C4_Model_merge_codegen(segment_model, model);
2240 /* Propagate any shadows from start */
2241 for(i = 0; i < src->src_shadow_list->len; i++){
2242 shadow = src->src_shadow_list->pdata[i];
2243 if(!proto_shadow_map[shadow->id])
2244 proto_shadow_map[shadow->id] = C4_ProtoShadow_create();
2245 C4_ProtoShadow_add_state(proto_shadow_map[shadow->id],
2246 segment_model->start_state->state);
2247 }
2248 /* Transitions from start */
2249 for(i = 0; i < src->output_transition_list->len; i++){
2250 transition = src->output_transition_list->pdata[i];
2251 if(!C4_Model_path_is_possible(model, transition->output, dst))
2252 continue;
2253 C4_Model_segment_add_transition(model, segment_model,
2254 transition, state_map, calc_map,
2255 transition_map_tree, proto_shadow_map, TRUE, FALSE);
2256 }
2257 /* Transitions to end */
2258 for(i = 0; i < dst->input_transition_list->len; i++){
2259 transition = dst->input_transition_list->pdata[i];
2260 if(!C4_Model_path_is_possible(model, src, transition->input))
2261 continue;
2262 C4_Model_segment_add_transition(model, segment_model,
2263 transition, state_map, calc_map,
2264 transition_map_tree, proto_shadow_map, FALSE, TRUE);
2265 }
2266 /* Other transitions */
2267 for(i = 0; i < model->state_list->len; i++){
2268 state = model->state_list->pdata[i];
2269 C4_Model_segment_recur(model, segment_model,
2270 state, visited_state,
2271 state_map, calc_map,
2272 transition_map_tree,
2273 proto_shadow_map);
2274 }
2275 /* Remove duplicate equivalent transitions */
2276 /* C4_Model_remove_duplicate_transitions(segment_model); */
2277 for(i = 0; i < model->shadow_list->len; i++){
2278 if(proto_shadow_map[i]){
2279 C4_ProtoShadow_generate(proto_shadow_map[i], model,
2280 segment_model,
2281 model->shadow_list->pdata[i]);
2282 C4_ProtoShadow_destroy(proto_shadow_map[i]);
2283 }
2284 }
2285 g_free(proto_shadow_map);
2286 g_free(calc_map);
2287 g_free(visited_state);
2288 g_free(name);
2289 return segment_model;
2290 }
2291
C4_Transition_compare_by_address(gconstpointer a,gconstpointer b)2292 static gint C4_Transition_compare_by_address(gconstpointer a,
2293 gconstpointer b){
2294 return GPOINTER_TO_INT(a)-GPOINTER_TO_INT(b);
2295 }
2296
C4_DerivedModel_create(C4_Model * original_model,C4_State * src,C4_State * dst,C4_Scope start_scope,C4_CellStartFunc cell_start_func,gchar * cell_start_macro,C4_Scope end_scope,C4_CellEndFunc cell_end_func,gchar * cell_end_macro)2297 C4_DerivedModel *C4_DerivedModel_create(C4_Model *original_model,
2298 C4_State *src, C4_State *dst,
2299 C4_Scope start_scope, C4_CellStartFunc cell_start_func,
2300 gchar *cell_start_macro,
2301 C4_Scope end_scope, C4_CellEndFunc cell_end_func,
2302 gchar *cell_end_macro){
2303 register C4_DerivedModel *derived_model = g_new(C4_DerivedModel, 1);
2304 register GTree *transition_map_tree
2305 = g_tree_new(C4_Transition_compare_by_address);
2306 register gint i;
2307 register C4_Transition *original_transition, *derived_transition;
2308 register C4_State **state_map = g_new0(C4_State*,
2309 original_model->state_list->len);
2310 g_assert(!original_model->is_open);
2311 g_assert(src);
2312 g_assert(dst);
2313 derived_model->original = C4_Model_share(original_model);
2314 derived_model->derived = C4_Model_select(original_model, src, dst,
2315 state_map,
2316 transition_map_tree);
2317 g_free(state_map);
2318 C4_Model_close(derived_model->derived);
2319 C4_Model_configure_start_state(derived_model->derived,
2320 start_scope, cell_start_func, cell_start_macro);
2321 C4_Model_configure_end_state(derived_model->derived,
2322 end_scope, cell_end_func, cell_end_macro);
2323 derived_model->transition_map = g_new(C4_Transition*,
2324 derived_model->derived->transition_list->len);
2325 for(i = 0; i < derived_model->derived->transition_list->len; i++){
2326 derived_transition
2327 = derived_model->derived->transition_list->pdata[i];
2328 g_assert(derived_transition);
2329 original_transition = g_tree_lookup(transition_map_tree,
2330 derived_transition);
2331 g_assert(original_transition);
2332 derived_model->transition_map[derived_transition->id]
2333 = original_transition;
2334 }
2335 g_tree_destroy(transition_map_tree);
2336 return derived_model;
2337 }
2338 /* FIXME: optimisation: when start and end are the same as original,
2339 * just do a C4_Model_copy(), (with transition map)
2340 */
2341
C4_DerivedModel_destroy(C4_DerivedModel * derived_model)2342 void C4_DerivedModel_destroy(C4_DerivedModel *derived_model){
2343 C4_Model_destroy(derived_model->original);
2344 C4_Model_destroy(derived_model->derived);
2345 g_free(derived_model->transition_map);
2346 g_free(derived_model);
2347 return;
2348 }
2349
2350 /**/
2351
2352