2 * Copyright (c) 2000-2001
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 #include "flowrow-sort.h"
39 #include "setif-sort.h"
45 /* generic flow row */
58 typedef struct flowrow_gen
*flowrow_gen
;
74 typedef struct flowrow
*flowrow
;
84 region flowrow_region
;
85 term_hash flowrow_hash
;
86 struct flowrow_stats flowrow_stats
;
87 static void fields_print(FILE *f
,flowrow_map m
,field_print_fn_ptr field_print
) deletes
;
89 stamp
flowrow_get_stamp(gen_e e
)
91 if ( ((flowrow_gen
)e
)->type
== ALIAS_TYPE
)
92 return ((flowrow_gen
)fv_get_alias( (flow_var
)e
))->st
;
94 return ((flowrow_gen
)e
)->st
;
98 static flowrow_map
flowrow_get_fields(gen_e e
)
100 assert (flowrow_is_row(e
));
102 return ((flowrow
)e
)->fields
;
105 static gen_e
flowrow_get_rest(gen_e e
)
107 assert(flowrow_is_row(e
));
109 return ((flowrow
)e
)->rest
;
113 static int field_compare(const flowrow_field f1
,const flowrow_field f2
)
116 int compare
= strcmp(f1
->label
,f2
->label
);
121 static int field_compare_ne(const flowrow_field f1
,const flowrow_field f2
)
124 int compare
= strcmp(f1
->label
,f2
->label
);
126 if (! compare
) /* rows should never have two fields with the same labels */
128 failure("Multiple fields in this row share the same label\n");
133 static struct field_split
split_fields(region r
, flowrow_map fields1
,
136 struct field_split split
;
137 flowrow_map_scanner scan1
, scan2
;
138 flowrow_field field1
,field2
;
139 bool consumed1
= TRUE
,consumed2
= TRUE
,
140 fields1_remain
= TRUE
, fields2_remain
= TRUE
;;
142 split
.matched1
= new_gen_e_list(r
);
143 split
.matched2
= new_gen_e_list(r
);
144 split
.nomatch1
= new_flowrow_map(r
);
145 split
.nomatch2
= new_flowrow_map(r
);
147 flowrow_map_scan(fields1
,&scan1
);
148 flowrow_map_scan(fields2
,&scan2
);
153 fields1_remain
= flowrow_map_next(&scan1
,&field1
);
155 fields2_remain
= flowrow_map_next(&scan2
,&field2
);
157 if (fields1_remain
&& fields2_remain
)
159 int compare_fields
= field_compare(field1
,field2
);
161 if (compare_fields
< 0)
163 flowrow_map_cons(field1
,split
.nomatch1
);
167 else if (compare_fields
> 0)
169 flowrow_map_cons(field2
,split
.nomatch2
);
173 else /* two fields are equal */
175 gen_e_list_cons(field1
->expr
,split
.matched1
);
176 gen_e_list_cons(field2
->expr
,split
.matched2
);
182 else if (fields1_remain
)
184 /* flowrow_map_append(split.nomatch1,flowrow_map_copy(r,fields1)); */
185 flowrow_map_cons(field1
,split
.nomatch1
);
187 while (flowrow_map_next(&scan1
,&field1
))
189 flowrow_map_cons(field1
,split
.nomatch1
);
194 else if (fields2_remain
)
196 /* flowrow_map_append(split.nomatch2,flowrow_map_copy(r,fields2)); */
197 flowrow_map_cons(field2
,split
.nomatch2
);
198 while (flowrow_map_next(&scan2
,&field2
))
200 flowrow_map_cons(field2
,split
.nomatch2
);
204 else /* no remaining fields, so */ break;
210 static bool flowrow_is_normalized(gen_e r
)
212 if ( flowrow_is_row(r
) )
214 gen_e rest
= flowrow_get_rest(r
);
216 if ( flowrow_is_row(rest
) || flowrow_is_alias(rest
) )
219 else if ( flowrow_is_alias(r
) )
225 static gen_e
normalize(get_stamp_fn_ptr get_stamp
,
226 flowrow_map m
,gen_e r
) deletes
228 if (flowrow_is_row(r
))
230 flowrow_map_append(m
,
231 flowrow_map_copy(flowrow_region
,
232 flowrow_get_fields(r
)));
233 return normalize(get_stamp
,m
,flowrow_get_rest(r
));
235 else if (flowrow_is_alias(r
))
237 assert (! flowrow_is_alias(fv_get_alias((flow_var
)r
)) );
238 return normalize(get_stamp
, m
,fv_get_alias((flow_var
)r
));
241 return flowrow_row(get_stamp
,m
,r
);
244 static gen_e
normalize_row(get_stamp_fn_ptr get_stamp
, gen_e r
) deletes
246 if (flowrow_is_normalized(r
))
248 else /* normalize the row */
249 return normalize(get_stamp
,new_flowrow_map(flowrow_region
),r
);
252 static bool eq(gen_e e1
, gen_e e2
)
254 return ( flowrow_get_stamp(e1
) == flowrow_get_stamp(e2
) );
259 A row constraint row1 <= row2 is l-inductive iff row2 is a var and for all
260 X = tlv(row1), o(row2) > o(X).
262 tlv(row) = {X} if row is a var X, {} otherwise
264 static bool l_inductive(gen_e e1
, gen_e e2
)
266 if (flowrow_is_var(e2
))
268 if (flowrow_is_var(e1
))
269 return flowrow_get_stamp(e2
) > flowrow_get_stamp(e1
);
276 A row constraint row1 <= row2 is r-inductive iff row1 is a var and for all
277 X = tlv(row2), o(row1) > o(X)
279 static bool r_inductive(gen_e e1
, gen_e e2
)
281 if (flowrow_is_var(e1
))
283 if (flowrow_is_var(e2
))
284 return flowrow_get_stamp(e1
) > flowrow_get_stamp(e2
);
290 static inline bool flowrow_minimal(flowrow r
)
292 return flowrow_is_zero(r
->rest
);
295 static inline bool flowrow_maximal(flowrow r
)
297 return flowrow_is_one(r
->rest
);
300 static inline bool flowrow_closed(flowrow r
)
302 return flowrow_is_abs(r
->rest
);
305 static inline bool flowrow_wildcard(flowrow r
)
307 return flowrow_is_wild(r
->rest
);
310 static inline bool flowrow_var(flowrow r
)
312 return flowrow_is_var(r
->rest
);
315 static gen_e
contour_instantiate(fresh_fn_ptr fresh
,
316 get_stamp_fn_ptr get_stamp
,
319 if (flowrow_is_row(e
))
322 flowrow_map_scanner scan
;
324 gen_e row
= normalize_row(get_stamp
,e
);
326 region scratch_rgn
= newregion();
328 flowrow_map new_fields
= new_flowrow_map(scratch_rgn
);
330 flowrow_map_scan(flowrow_get_fields(row
),&scan
);
332 while (flowrow_map_next(&scan
,&f
))
334 flowrow_field new_field
=
335 ralloc(flowrow_region
,struct flowrow_field
);
336 new_field
->label
= f
->label
;
337 new_field
->expr
= fresh(NULL
);
339 flowrow_map_cons(new_field
,new_fields
);
342 result
= flowrow_row(get_stamp
,new_fields
,flowrow_fresh(NULL
));
344 deleteregion(scratch_rgn
);
346 assert( flowrow_is_row(result
) );
353 failure("Unmatched contour\n");
358 static contour
get_contour(fresh_fn_ptr fresh
,get_stamp_fn_ptr get_stamp
,
359 gen_e zero_elem ATTRIBUTE_UNUSED
,gen_e e
)
361 if (flowrow_is_row(e
))
365 result
= ralloc(flowrow_region
,struct contour
);
367 result
->fresh
= fresh
;
368 result
->get_stamp
= get_stamp
;
369 result
->instantiate
= contour_instantiate
;
375 failure("Unmatched contour\n");
381 static void trans_lbs(fresh_fn_ptr fresh
,get_stamp_fn_ptr get_stamp
,
382 incl_fn_ptr field_incl
, gen_e zero_elem
,
383 flow_var v
, gen_e e
) deletes
386 gen_e_list_scanner scan
;
388 gen_e_list_scan(fv_get_lbs(v
),&scan
);
389 while (gen_e_list_next(&scan
,&temp
))
390 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,temp
,e
);
394 static void trans_ubs(fresh_fn_ptr fresh
,get_stamp_fn_ptr get_stamp
,
395 incl_fn_ptr field_incl
, gen_e zero_elem
,
396 flow_var v
, gen_e e
) deletes
399 gen_e_list_scanner scan
;
401 gen_e_list_scan(fv_get_ubs(v
),&scan
);
402 while (gen_e_list_next(&scan
,&temp
))
403 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,e
,temp
);
406 static void update_lower_bound(fresh_fn_ptr fresh
,get_stamp_fn_ptr get_stamp
,
407 incl_fn_ptr field_incl
, gen_e zero_elem
,
408 flow_var v
,gen_e e
) deletes
410 if (fv_has_contour(v
)) /* _ <= v, and v has a contour */
412 gen_e shape
= fv_instantiate_contour(v
);
414 fv_set_alias(v
,shape
);
415 trans_ubs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,shape
);
416 trans_lbs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,shape
);
418 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,e
,shape
);
422 else if (flowrow_is_var(e
))
424 flow_var v_lb
= (flow_var
)e
;
426 if (fv_has_contour(v_lb
)) /* v1 <= v2, v1 has a contour */
428 gen_e shape
= fv_instantiate_contour(v_lb
);
430 fv_set_alias(v_lb
,shape
);
431 trans_ubs(fresh
,get_stamp
,field_incl
,zero_elem
,v_lb
,shape
);
432 trans_lbs(fresh
,get_stamp
,field_incl
,zero_elem
,v_lb
,shape
);
434 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,
439 else /* we have v1 <= v2, no contours */
443 fv_unify_contour(v
,(flow_var
)e
);
444 redundant
= fv_add_lb(v
,e
,flowrow_get_stamp(e
));
447 trans_ubs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,e
);
451 else /* we have c(...) <= v, and v has no contour */
454 fv_set_contour(v
,get_contour(fresh
,get_stamp
,zero_elem
,e
));
456 shape
= fv_instantiate_contour(v
);
457 fv_set_alias(v
,shape
);
458 trans_ubs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,shape
);
459 trans_lbs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,shape
);
461 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,e
,shape
);
466 static void update_upper_bound(fresh_fn_ptr fresh
,get_stamp_fn_ptr get_stamp
,
467 incl_fn_ptr field_incl
, gen_e zero_elem
,
468 flow_var v
,gen_e e
) deletes
470 if (fv_has_contour(v
)) /* v isn't aliased, and we discovered a contour*/
472 gen_e shape
= fv_instantiate_contour(v
);
474 fv_set_alias(v
,shape
);
475 trans_ubs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,shape
);
476 trans_lbs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,shape
);
478 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,shape
,e
);
482 else if (flowrow_is_var(e
))
484 flow_var v2
= (flow_var
)e
;
486 if (fv_has_contour(v2
)) // v2 isn't aliased, and we discovered a contour
488 gen_e shape
= fv_instantiate_contour(v2
);
490 fv_set_alias(v2
,shape
);
491 trans_ubs(fresh
,get_stamp
,field_incl
,zero_elem
,v2
,shape
);
492 trans_lbs(fresh
,get_stamp
,field_incl
,zero_elem
,v2
,shape
);
495 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,
500 else /* we have v1 <= v2, no contours */
504 fv_unify_contour(v
,(flow_var
)e
);
505 redundant
= fv_add_ub(v
,e
,flowrow_get_stamp(e
));
508 trans_lbs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,e
);
512 else /* we have v <= c(...), and v has no contour */
515 fv_set_contour(v
,get_contour(fresh
,get_stamp
,zero_elem
,e
));
517 shape
= fv_instantiate_contour(v
);
519 if (! flowrow_is_row(shape
) )
524 fv_set_alias(v
,shape
);
525 trans_ubs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,shape
);
526 trans_lbs(fresh
,get_stamp
,field_incl
,zero_elem
,v
,shape
);
529 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,shape
,e
);
538 void flowrow_inclusion(fresh_fn_ptr fresh
,get_stamp_fn_ptr get_stamp
,
539 incl_fn_ptr field_incl
, gen_e zero_elem
, gen_e a
,
542 gen_e e1
= normalize_row(get_stamp
, a
),
543 e2
= normalize_row(get_stamp
, b
);
547 else if (flowrow_is_zero(e1
) || flowrow_is_wild(e1
))
549 else if (flowrow_is_one(e2
) || flowrow_is_wild(e2
))
552 else if ( l_inductive(e1
,e2
) )
554 flow_var v2
= (flow_var
)e2
;
556 flowrow_stats
.rows_l_inductive
++;
558 update_lower_bound(fresh
,get_stamp
,field_incl
,zero_elem
,v2
,e1
);
562 else if ( r_inductive(e1
,e2
) )
564 flow_var v1
= (flow_var
)e1
;
566 flowrow_stats
.rows_r_inductive
++;
568 update_upper_bound(fresh
,get_stamp
,field_incl
,zero_elem
,v1
,e2
);
572 else if ( flowrow_is_row(e1
) && flowrow_is_row(e2
))
574 region scratch_rgn
= newregion();
576 flowrow r1
= (flowrow
)e1
,
579 struct field_split split
=
580 split_fields(scratch_rgn
,r1
->fields
,r2
->fields
);
582 if ( gen_e_list_empty(split
.matched1
) )
584 assert ( gen_e_list_empty(split
.matched2
) );
586 if (flowrow_wildcard(r1
) || flowrow_minimal(r1
))
589 flowrow_row(get_stamp
,split
.nomatch1
,flowrow_get_rest(e1
));
591 flowrow_inclusion(fresh
,get_stamp
,field_incl
, zero_elem
,newrow
,
592 flowrow_get_rest(e2
));
594 else if (flowrow_maximal(r2
) || flowrow_closed(r2
))
597 flowrow_row(get_stamp
,split
.nomatch2
,flowrow_get_rest(e2
));
599 flowrow_inclusion(fresh
, get_stamp
,field_incl
,zero_elem
,
600 flowrow_get_rest(e1
),newrow
);
604 gen_e rest1
= flowrow_get_rest(e1
),
605 rest2
= flowrow_get_rest(e2
);
607 //assert( flowrow_is_var(rest1) && flowrow_is_var(rest2));
609 if ( eq(rest1
,rest2
))
610 failure("Recursive row resolution\n");
613 gen_e fv
= flowrow_fresh(NULL
);
614 gen_e newrow1
= flowrow_row(get_stamp
,split
.nomatch1
,fv
);
615 gen_e newrow2
= flowrow_row(get_stamp
,split
.nomatch2
,fv
);
617 flowrow_inclusion(fresh
,get_stamp
,field_incl
,
618 zero_elem
,rest1
,newrow2
);
619 flowrow_inclusion(fresh
,get_stamp
,field_incl
,
620 zero_elem
,newrow1
,rest2
);
626 else /* some fields matched */
628 gen_e_list_scanner scan1
, scan2
;
631 assert( gen_e_list_length(split
.matched1
)
632 == gen_e_list_length(split
.matched2
) );
634 gen_e_list_scan(split
.matched1
,&scan1
);
635 gen_e_list_scan(split
.matched2
,&scan2
);
637 while (gen_e_list_next(&scan1
,&f1
) &&
638 gen_e_list_next(&scan2
,&f2
) )
643 if ( flowrow_wildcard(r1
) && flowrow_wildcard(r2
) )
649 flowrow_map fields1
= split
.nomatch1
;
650 flowrow_map fields2
= split
.nomatch2
;
652 gen_e newrow1
= flowrow_row(get_stamp
,fields1
,r1
->rest
);
653 gen_e newrow2
= flowrow_row(get_stamp
,fields2
,r2
->rest
);
655 flowrow_inclusion(fresh
,get_stamp
,field_incl
,zero_elem
,
660 deleteregion(scratch_rgn
);
663 else /* potentially a problem normalizing a row? */
665 failure("Unmatched case in row inclusion\n");
670 gen_e
flowrow_row(get_stamp_fn_ptr get_stamp
,flowrow_map f
, gen_e rest
) deletes
672 flowrow_map fields
= flowrow_map_copy(flowrow_region
,f
);
674 if (flowrow_map_empty(fields
))
680 flowrow_map_scanner scan
;
684 length
= flowrow_map_length(fields
);
685 stamp st
[2+2*length
];
689 st
[1] = flowrow_get_stamp(rest
);
693 flowrow_map_sort(fields
,field_compare_ne
);
695 flowrow_map_scan(fields
,&scan
);
696 while(flowrow_map_next(&scan
,&temp
))
698 st
[i
++] = stamp_string(temp
->label
);
700 st
[i
++] = get_stamp(temp
->expr
);
705 if ( (result
= term_hash_find(flowrow_hash
,st
,2 + 2*length
)) == NULL
)
707 flowrow r
= ralloc(flowrow_region
, struct flowrow
);
709 r
->st
= stamp_fresh();
714 r
->base_sort
= row_map_head(fields
)->expr
->sort
;
715 r
->sort
= flowrow_sort
;
718 term_hash_insert(flowrow_hash
,result
,st
,2+2*length
);
720 /* assert(flowrow_is_normalized(result)); */
727 static struct flowrow_gen zero_row
= {ZERO_TYPE
,ZERO_TYPE
};
728 static struct flowrow_gen one_row
= {ONE_TYPE
,ONE_TYPE
};
729 static struct flowrow_gen abs_row
= {ABS_TYPE
, ABS_TYPE
};
730 static struct flowrow_gen wild_row
= {WILD_TYPE
, WILD_TYPE
};
732 gen_e
flowrow_zero(void)
734 return (gen_e
)&zero_row
;
737 gen_e
flowrow_one(void)
739 return (gen_e
)&one_row
;
742 gen_e
flowrow_abs(void)
744 return (gen_e
)&abs_row
;
747 gen_e
flowrow_wild(void)
749 return (gen_e
)&wild_row
;
752 gen_e
flowrow_fresh(const char *name
)
754 flowrow_stats
.fresh
++;
755 return (gen_e
)fv_fresh(flowrow_region
,name
);
758 gen_e
flowrow_fresh_small(const char *name
)
760 flowrow_stats
.fresh_small
++;
761 return (gen_e
)fv_fresh_small(flowrow_region
,name
);
764 gen_e
flowrow_fresh_large(const char *name
)
766 flowrow_stats
.fresh_large
++;
767 return (gen_e
)fv_fresh_large(flowrow_region
,name
);
771 static struct flowrow_gen term_zero_row
= {flowrow_sort
,ZERO_TYPE
,ZERO_TYPE
,term_sort
};
772 static struct flowrow_gen term_one_row
= {flowrow_sort
,ONE_TYPE
,ONE_TYPE
,term_sort
};
773 static struct flowrow_gen term_abs_row
= {flowrow_sort
,ABS_TYPE
, ABS_TYPE
,term_sort
};
774 static struct flowrow_gen term_wild_row
= {flowrow_sort
,WILD_TYPE
, WILD_TYPE
,term_sort
};
777 static struct flowrow_gen setif_zero_row
= {flowrow_sort
,ZERO_TYPE
,ZERO_TYPE
,setif_sort
};
778 static struct flowrow_gen setif_one_row
= {flowrow_sort
,ONE_TYPE
,ONE_TYPE
,setif_sort
};
779 static struct flowrow_gen setif_abs_row
= {flowrow_sort
,ABS_TYPE
, ABS_TYPE
,setif_sort
};
780 static struct flowrow_gen setif_wild_row
= {flowrow_sort
,WILD_TYPE
, WILD_TYPE
,setif_sort
};
782 static struct flowrow_gen setst_zero_row
= {flowrow_sort
,ZERO_TYPE
,ZERO_TYPE
,setst_sort
};
783 static struct flowrow_gen setst_one_row
= {flowrow_sort
,ONE_TYPE
,ONE_TYPE
,setst_sort
};
784 static struct flowrow_gen setst_abs_row
= {flowrow_sort
,ABS_TYPE
, ABS_TYPE
,setst_sort
};
785 static struct flowrow_gen setst_wild_row
= {flowrow_sort
,WILD_TYPE
, WILD_TYPE
,setst_sort
};
788 gen_e
flowrow_zero(sort_kind base_sort
)
793 return (gen_e
)&setif_zero_row
;
795 return (gen_e
)&setst_zero_row
;
797 return (gen_e
)&term_zero_row
;
800 failure("No matching base sort: flowrow_zero\n");
808 gen_e
flowrow_one(sort_kind base_sort
)
813 return (gen_e
)&setif_one_row
;
815 return (gen_e
)&setst_one_row
;
817 return (gen_e
)&term_one_row
;
820 failure("No matching base sort: flowrow_one\n");
828 gen_e
flowrow_abs(sort_kind base_sort
)
833 return (gen_e
)&setif_abs_row
;
835 return (gen_e
)&setst_abs_row
;
837 return (gen_e
)&term_abs_row
;
840 failure("No matching base sort: flowrow_abs\n");
848 gen_e
flowrow_wild(sort_kind base_sort
)
854 return (gen_e
)&setif_wild_row
;
856 return (gen_e
)&setst_wild_row
;
858 return (gen_e
)&term_wild_row
;
861 failure("No matching base sort: flowrow_wild\n");
869 gen_e
flowrow_fresh(const char *name
,sort_kind base_sort
)
877 return (gen_e
)&setst_one_row
;
879 return (gen_e
)&term_one_row
;
882 failure("No matching base sort: flowrow_one\n");
890 gen_e
flowrow_fresh_small(sort_kind base_sort
)
896 return (gen_e
)&setif_one_row
;
898 return (gen_e
)&setst_one_row
;
900 return (gen_e
)&term_one_row
;
903 failure("No matching base sort: flowrow_one\n");
911 gen_e
flowrow_fresh_large(sort_kind base_sort
)
916 sort_kind
flowrow_base_sort(gen_e e
)
923 gen_e
flowrow_extract_field(const char *name
, gen_e e
)
926 static bool field_eq(const flowrow_field f
)
928 return (! strcmp(f
->label
,name
));
931 if (flowrow_is_row(e
))
933 flowrow_map fields
= flowrow_get_fields(e
);
934 flowrow_field f
= flowrow_map_find(fields
,field_eq
);
942 gen_e
flowrow_extract_rest(gen_e e
)
944 if (flowrow_is_row(e
))
945 return flowrow_get_rest(e
);
950 flowrow_map
flowrow_extract_fields(gen_e e
)
952 if (flowrow_is_row(e
))
953 return flowrow_map_copy(flowrow_region
,flowrow_get_fields(e
));
959 bool flowrow_is_alias(gen_e e
)
961 return ((flowrow_gen
)e
)->type
== ALIAS_TYPE
;
964 bool flowrow_is_zero(gen_e e
)
966 return ((flowrow_gen
)e
)->type
== ZERO_TYPE
;
969 bool flowrow_is_one(gen_e e
)
971 return ((flowrow_gen
)e
)->type
== ONE_TYPE
;
974 bool flowrow_is_abs(gen_e e
)
976 return ((flowrow_gen
)e
)->type
== ABS_TYPE
;
979 bool flowrow_is_wild(gen_e e
)
981 return ((flowrow_gen
)e
)->type
== WILD_TYPE
;
984 bool flowrow_is_var(gen_e e
)
986 return ((flowrow_gen
)e
)->type
== VAR_TYPE
;
989 bool flowrow_is_row(gen_e e
)
991 return ((flowrow_gen
)e
)->type
== ROW_TYPE
;
994 void flowrow_init(void)
996 flowrow_region
= newregion();
997 flowrow_hash
= make_term_hash(flowrow_region
);
1000 static void flowrow_reset_stats(void)
1002 flowrow_stats
.fresh
= 0;
1003 flowrow_stats
.fresh_small
= 0;
1004 flowrow_stats
.fresh_large
= 0;
1006 flowrow_stats
.rows_disjoint_wild
= 0;
1007 flowrow_stats
.rows_equal
= 0;
1008 flowrow_stats
.rows_zero_one_wild
= 0;
1009 flowrow_stats
.rows_l_inductive
= 0;
1010 flowrow_stats
.rows_r_inductive
= 0;
1011 flowrow_stats
.rows_disjoint_r1_minimal
= 0;
1012 flowrow_stats
.rows_disjoint_r1_var_r2_minimal
= 0;
1013 flowrow_stats
.rows_disjoint_r1_var_r2_maximal
= 0;
1014 flowrow_stats
.rows_disjoint_r1_var_r2_closed
= 0;
1015 flowrow_stats
.rows_disjoint_r1_var_r2_var_lt
= 0;
1016 flowrow_stats
.rows_disjoint_r1_var_r2_var_gt
= 0;
1017 flowrow_stats
.rows_equal_domains
= 0;
1018 flowrow_stats
.rows_nonempty_intersection
= 0;
1019 flowrow_stats
.rows_fresh
= 0;
1020 flowrow_stats
.rows_fresh_large
= 0;
1023 void flowrow_reset(void) deletes
1025 term_hash_delete(flowrow_hash
);
1026 deleteregion_ptr(&flowrow_region
);
1028 flowrow_reset_stats();
1030 flowrow_region
= newregion();
1031 flowrow_hash
= make_term_hash(flowrow_region
);
1035 static void fields_print(FILE *f
,flowrow_map m
,field_print_fn_ptr field_print
) deletes
1037 flowrow_map_scanner scan
;
1040 flowrow_map_scan(m
,&scan
);
1042 if (flowrow_map_next(&scan
,&temp
))
1044 fprintf(f
,"%s : ",temp
->label
);
1047 field_print(f
,temp
->expr
);
1052 while (flowrow_map_next(&scan
,&temp
))
1054 fprintf(f
,",%s : ",temp
->label
);
1057 field_print(f
,temp
->expr
);
1063 void flowrow_print(FILE *f
,get_stamp_fn_ptr get_stamp
,
1064 field_print_fn_ptr field_print
,gen_e row
) deletes
1066 gen_e e
= normalize_row(get_stamp
,row
);
1068 switch ( ((flowrow_gen
)e
)->type
)
1083 fprintf(f
, fv_get_name((flow_var
)e
));
1087 fields_print(f
, flowrow_get_fields(e
), field_print
);
1089 flowrow_print(f
, get_stamp
, field_print
, flowrow_get_rest(e
));
1098 void flowrow_print_stats(FILE *f
)
1100 fprintf(f
,"\n========== Flow Var Stats ==========\n");
1101 fprintf(f
,"Fresh : %d\n",flowrow_stats
.fresh
);
1102 fprintf(f
,"Fresh Small : %d\n",flowrow_stats
.fresh_small
);
1103 fprintf(f
,"Fresh Large : %d\n",flowrow_stats
.fresh_large
);
1104 fprintf(f
,"=====================================\n");
1107 DEFINE_LIST(flowrow_map
,flowrow_field
)