diff options
Diffstat (limited to 'libbanshee/engine/flowrow-sort.c')
| -rw-r--r-- | libbanshee/engine/flowrow-sort.c | 1107 |
1 files changed, 1107 insertions, 0 deletions
diff --git a/libbanshee/engine/flowrow-sort.c b/libbanshee/engine/flowrow-sort.c new file mode 100644 index 00000000000..baee348ffd3 --- /dev/null +++ b/libbanshee/engine/flowrow-sort.c @@ -0,0 +1,1107 @@ +/* + * Copyright (c) 2000-2001 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + */ + +#include <regions.h> +#include <assert.h> +#include <stdio.h> +#include <string.h> +#include <ansidecl.h> +#include "flowrow-sort.h" +#include "termhash.h" + +#include "setif-sort.h" + +#define ABS_TYPE 2 +#define WILD_TYPE 3 +#define ROW_TYPE 4 + +/* generic flow row */ +struct flowrow_gen +{ +#ifdef NONSPEC + sort_kind sort; +#endif + int type; + stamp st; +#ifdef NONSPEC + sort_kind base_sort; +#endif +}; + +typedef struct flowrow_gen *flowrow_gen; + +struct flowrow +{ +#ifdef NONSPEC + sort_kind sort; +#endif + int type; + stamp st; +#ifdef NONSPEC + sort_kind base_sort; +#endif + flowrow_map fields; + gen_e rest; +}; + +typedef struct flowrow *flowrow; + +struct field_split +{ + gen_e_list matched1; + gen_e_list matched2; + flowrow_map nomatch1; + flowrow_map nomatch2; +}; + +region flowrow_region; +term_hash flowrow_hash; +struct flowrow_stats flowrow_stats; +static void fields_print(FILE *f,flowrow_map m,field_print_fn_ptr field_print) deletes; + +stamp flowrow_get_stamp(gen_e e) +{ + if ( ((flowrow_gen)e)->type == ALIAS_TYPE) + return ((flowrow_gen)fv_get_alias( (flow_var)e ))->st; + else + return ((flowrow_gen)e)->st; + +} + +static flowrow_map flowrow_get_fields(gen_e e) +{ + assert (flowrow_is_row(e)); + + return ((flowrow)e)->fields; +} + +static gen_e flowrow_get_rest(gen_e e) +{ + assert(flowrow_is_row(e)); + + return ((flowrow)e)->rest; +} + + +static int field_compare(const flowrow_field f1,const flowrow_field f2) + +{ + int compare = strcmp(f1->label,f2->label); + return compare; +} + + +static int field_compare_ne(const flowrow_field f1,const flowrow_field f2) + +{ + int compare = strcmp(f1->label,f2->label); + + if (! compare) /* rows should never have two fields with the same labels */ + { + failure("Multiple fields in this row share the same label\n"); + } + return compare; +} + +static struct field_split split_fields(region r, flowrow_map fields1, + flowrow_map fields2) +{ + struct field_split split; + flowrow_map_scanner scan1, scan2; + flowrow_field field1,field2; + bool consumed1 = TRUE,consumed2 = TRUE, + fields1_remain = TRUE, fields2_remain = TRUE;; + + split.matched1 = new_gen_e_list(r); + split.matched2 = new_gen_e_list(r); + split.nomatch1 = new_flowrow_map(r); + split.nomatch2 = new_flowrow_map(r); + + flowrow_map_scan(fields1,&scan1); + flowrow_map_scan(fields2,&scan2); + + while (TRUE) + { + if (consumed1) + fields1_remain = flowrow_map_next(&scan1,&field1); + if (consumed2) + fields2_remain = flowrow_map_next(&scan2,&field2); + + if (fields1_remain && fields2_remain) + { + int compare_fields = field_compare(field1,field2); + + if (compare_fields < 0) + { + flowrow_map_cons(field1,split.nomatch1); + consumed1 = TRUE; + consumed2 = FALSE; + } + else if (compare_fields > 0) + { + flowrow_map_cons(field2,split.nomatch2); + consumed2 = TRUE; + consumed1 = FALSE; + } + else /* two fields are equal */ + { + gen_e_list_cons(field1->expr,split.matched1); + gen_e_list_cons(field2->expr,split.matched2); + consumed1 = TRUE; + consumed2 = TRUE; + continue; + } + } + else if (fields1_remain) + { + /* flowrow_map_append(split.nomatch1,flowrow_map_copy(r,fields1)); */ + flowrow_map_cons(field1,split.nomatch1); + + while (flowrow_map_next(&scan1,&field1)) + { + flowrow_map_cons(field1,split.nomatch1); + } + + break; + } + else if (fields2_remain) + { + /* flowrow_map_append(split.nomatch2,flowrow_map_copy(r,fields2)); */ + flowrow_map_cons(field2,split.nomatch2); + while (flowrow_map_next(&scan2,&field2)) + { + flowrow_map_cons(field2,split.nomatch2); + } + break; + } + else /* no remaining fields, so */ break; + } + + return split; +} + +static bool flowrow_is_normalized(gen_e r) +{ + if ( flowrow_is_row(r) ) + { + gen_e rest = flowrow_get_rest(r); + + if ( flowrow_is_row(rest) || flowrow_is_alias(rest) ) + return FALSE; + } + else if ( flowrow_is_alias(r) ) + return FALSE; + + return TRUE; +} + +static gen_e normalize(get_stamp_fn_ptr get_stamp, + flowrow_map m,gen_e r) deletes +{ + if (flowrow_is_row(r)) + { + flowrow_map_append(m, + flowrow_map_copy(flowrow_region, + flowrow_get_fields(r))); + return normalize(get_stamp,m,flowrow_get_rest(r)); + } + else if (flowrow_is_alias(r)) + { + assert (! flowrow_is_alias(fv_get_alias((flow_var)r)) ); + return normalize(get_stamp, m,fv_get_alias((flow_var)r)); + } + else + return flowrow_row(get_stamp,m,r); +} + +static gen_e normalize_row(get_stamp_fn_ptr get_stamp, gen_e r) deletes +{ + if (flowrow_is_normalized(r)) + return r; + else /* normalize the row */ + return normalize(get_stamp,new_flowrow_map(flowrow_region),r); +} + +static bool eq(gen_e e1, gen_e e2) +{ + return ( flowrow_get_stamp(e1) == flowrow_get_stamp(e2) ); +} + + +/* + A row constraint row1 <= row2 is l-inductive iff row2 is a var and for all + X = tlv(row1), o(row2) > o(X). + + tlv(row) = {X} if row is a var X, {} otherwise +*/ +static bool l_inductive(gen_e e1, gen_e e2) +{ + if (flowrow_is_var(e2)) + { + if (flowrow_is_var(e1)) + return flowrow_get_stamp(e2) > flowrow_get_stamp(e1); + else return TRUE; + } + return FALSE; +} + +/* + A row constraint row1 <= row2 is r-inductive iff row1 is a var and for all + X = tlv(row2), o(row1) > o(X) +*/ +static bool r_inductive(gen_e e1, gen_e e2) +{ + if (flowrow_is_var(e1)) + { + if (flowrow_is_var(e2)) + return flowrow_get_stamp(e1) > flowrow_get_stamp(e2); + else return TRUE; + } + return FALSE; +} + +static inline bool flowrow_minimal(flowrow r) +{ + return flowrow_is_zero(r->rest); +} + +static inline bool flowrow_maximal(flowrow r) +{ + return flowrow_is_one(r->rest); +} + +static inline bool flowrow_closed(flowrow r) +{ + return flowrow_is_abs(r->rest); +} + +static inline bool flowrow_wildcard(flowrow r) +{ + return flowrow_is_wild(r->rest); +} + +static inline bool flowrow_var(flowrow r) +{ + return flowrow_is_var(r->rest); +} + +static gen_e contour_instantiate(fresh_fn_ptr fresh, + get_stamp_fn_ptr get_stamp, + gen_e e) deletes +{ + if (flowrow_is_row(e)) + { + gen_e result; + flowrow_map_scanner scan; + flowrow_field f; + gen_e row = normalize_row(get_stamp,e); + + region scratch_rgn = newregion(); + + flowrow_map new_fields = new_flowrow_map(scratch_rgn); + + flowrow_map_scan(flowrow_get_fields(row),&scan); + + while (flowrow_map_next(&scan,&f)) + { + flowrow_field new_field = + ralloc(flowrow_region,struct flowrow_field); + new_field->label = f->label; + new_field->expr = fresh(NULL); + + flowrow_map_cons(new_field,new_fields); + } + + result = flowrow_row(get_stamp,new_fields,flowrow_fresh(NULL)); + + deleteregion(scratch_rgn); + + assert( flowrow_is_row(result) ); + + return result; + } + + else /* TODO */ + { + failure("Unmatched contour\n"); + return NULL; + } +} + +static contour get_contour(fresh_fn_ptr fresh,get_stamp_fn_ptr get_stamp, + gen_e zero_elem ATTRIBUTE_UNUSED,gen_e e) +{ + if (flowrow_is_row(e)) + { + contour result; + + result = ralloc(flowrow_region,struct contour); + result->shape = e; + result->fresh = fresh; + result->get_stamp = get_stamp; + result->instantiate = contour_instantiate; + + return result; + } + else /* TODO */ + { + failure("Unmatched contour\n"); + return NULL; + } +} + + +static void trans_lbs(fresh_fn_ptr fresh,get_stamp_fn_ptr get_stamp, + incl_fn_ptr field_incl, gen_e zero_elem, + flow_var v, gen_e e) deletes +{ + gen_e temp; + gen_e_list_scanner scan; + + gen_e_list_scan(fv_get_lbs(v),&scan); + while (gen_e_list_next(&scan,&temp)) + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,temp,e); + +} + +static void trans_ubs(fresh_fn_ptr fresh,get_stamp_fn_ptr get_stamp, + incl_fn_ptr field_incl, gen_e zero_elem, + flow_var v, gen_e e) deletes +{ + gen_e temp; + gen_e_list_scanner scan; + + gen_e_list_scan(fv_get_ubs(v),&scan); + while (gen_e_list_next(&scan,&temp)) + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,e,temp); +} + +static void update_lower_bound(fresh_fn_ptr fresh,get_stamp_fn_ptr get_stamp, + incl_fn_ptr field_incl, gen_e zero_elem, + flow_var v,gen_e e) deletes +{ + if (fv_has_contour(v)) /* _ <= v, and v has a contour */ + { + gen_e shape = fv_instantiate_contour(v); + + fv_set_alias(v,shape); + trans_ubs(fresh,get_stamp,field_incl,zero_elem,v,shape); + trans_lbs(fresh,get_stamp,field_incl,zero_elem,v,shape); + + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,e,shape); + + } + + else if (flowrow_is_var(e)) + { + flow_var v_lb = (flow_var)e; + + if (fv_has_contour(v_lb)) /* v1 <= v2, v1 has a contour */ + { + gen_e shape = fv_instantiate_contour(v_lb); + + fv_set_alias(v_lb,shape); + trans_ubs(fresh,get_stamp,field_incl,zero_elem,v_lb,shape); + trans_lbs(fresh,get_stamp,field_incl,zero_elem,v_lb,shape); + + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem, + shape,(gen_e)v); + + } + + else /* we have v1 <= v2, no contours */ + { + bool redundant; + + fv_unify_contour(v,(flow_var)e); + redundant = fv_add_lb(v,e,flowrow_get_stamp(e)); + + if (! redundant) + trans_ubs(fresh,get_stamp,field_incl,zero_elem,v,e); + + } + } + else /* we have c(...) <= v, and v has no contour */ + { + gen_e shape = NULL; + fv_set_contour(v,get_contour(fresh,get_stamp,zero_elem,e)); + + shape = fv_instantiate_contour(v); + fv_set_alias(v,shape); + trans_ubs(fresh,get_stamp,field_incl,zero_elem,v,shape); + trans_lbs(fresh,get_stamp,field_incl,zero_elem,v,shape); + + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,e,shape); + + } +} + +static void update_upper_bound(fresh_fn_ptr fresh,get_stamp_fn_ptr get_stamp, + incl_fn_ptr field_incl, gen_e zero_elem, + flow_var v,gen_e e) deletes +{ + if (fv_has_contour(v)) /* v isn't aliased, and we discovered a contour*/ + { + gen_e shape = fv_instantiate_contour(v); + + fv_set_alias(v,shape); + trans_ubs(fresh,get_stamp,field_incl,zero_elem,v,shape); + trans_lbs(fresh,get_stamp,field_incl,zero_elem,v,shape); + + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,shape,e); + + } + + else if (flowrow_is_var(e)) + { + flow_var v2 = (flow_var)e; + + if (fv_has_contour(v2)) // v2 isn't aliased, and we discovered a contour + { + gen_e shape = fv_instantiate_contour(v2); + + fv_set_alias(v2,shape); + trans_ubs(fresh,get_stamp,field_incl,zero_elem,v2,shape); + trans_lbs(fresh,get_stamp,field_incl,zero_elem,v2,shape); + + + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem, + (gen_e)v,shape); + + } + + else /* we have v1 <= v2, no contours */ + { + bool redundant; + + fv_unify_contour(v,(flow_var)e); + redundant = fv_add_ub(v,e,flowrow_get_stamp(e)); + + if (! redundant) + trans_lbs(fresh,get_stamp,field_incl,zero_elem,v,e); + + } + } + else /* we have v <= c(...), and v has no contour */ + { + gen_e shape = NULL; + fv_set_contour(v,get_contour(fresh,get_stamp,zero_elem,e)); + + shape = fv_instantiate_contour(v); + + if (! flowrow_is_row(shape) ) + { + assert(0); + } + + fv_set_alias(v,shape); + trans_ubs(fresh,get_stamp,field_incl,zero_elem,v,shape); + trans_lbs(fresh,get_stamp,field_incl,zero_elem,v,shape); + + + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,shape,e); + + } + +} + +// END + + +void flowrow_inclusion(fresh_fn_ptr fresh,get_stamp_fn_ptr get_stamp, + incl_fn_ptr field_incl, gen_e zero_elem, gen_e a, + gen_e b) deletes +{ + gen_e e1 = normalize_row(get_stamp, a), + e2 = normalize_row(get_stamp, b); + + if (eq(e1,e2)) + return; + else if (flowrow_is_zero(e1) || flowrow_is_wild(e1)) + return; + else if (flowrow_is_one(e2) || flowrow_is_wild(e2)) + return; + + else if ( l_inductive(e1,e2) ) + { + flow_var v2 = (flow_var)e2; + + flowrow_stats.rows_l_inductive++; + + update_lower_bound(fresh,get_stamp,field_incl,zero_elem,v2,e1); + return; + } + + else if ( r_inductive(e1,e2) ) + { + flow_var v1 = (flow_var)e1; + + flowrow_stats.rows_r_inductive++; + + update_upper_bound(fresh,get_stamp,field_incl,zero_elem,v1,e2); + return; + } + + else if ( flowrow_is_row(e1) && flowrow_is_row(e2)) + { + region scratch_rgn = newregion(); + + flowrow r1 = (flowrow)e1, + r2 = (flowrow)e2; + + struct field_split split = + split_fields(scratch_rgn,r1->fields,r2->fields); + + if ( gen_e_list_empty(split.matched1) ) + { + assert ( gen_e_list_empty(split.matched2) ); + + if (flowrow_wildcard(r1) || flowrow_minimal(r1)) + { + gen_e newrow = + flowrow_row(get_stamp,split.nomatch1,flowrow_get_rest(e1)); + + flowrow_inclusion(fresh,get_stamp,field_incl, zero_elem,newrow, + flowrow_get_rest(e2)); + } + else if (flowrow_maximal(r2) || flowrow_closed(r2)) + { + gen_e newrow = + flowrow_row(get_stamp,split.nomatch2,flowrow_get_rest(e2)); + + flowrow_inclusion(fresh, get_stamp,field_incl,zero_elem, + flowrow_get_rest(e1),newrow); + } + else + { + gen_e rest1 = flowrow_get_rest(e1), + rest2 = flowrow_get_rest(e2); + + //assert( flowrow_is_var(rest1) && flowrow_is_var(rest2)); + + if ( eq(rest1,rest2)) + failure("Recursive row resolution\n"); + else + { + gen_e fv = flowrow_fresh(NULL); + gen_e newrow1 = flowrow_row(get_stamp,split.nomatch1,fv); + gen_e newrow2 = flowrow_row(get_stamp,split.nomatch2,fv); + + flowrow_inclusion(fresh,get_stamp,field_incl, + zero_elem,rest1,newrow2); + flowrow_inclusion(fresh,get_stamp,field_incl, + zero_elem,newrow1,rest2); + } + + } + } + + else /* some fields matched */ + { + gen_e_list_scanner scan1, scan2; + gen_e f1,f2; + + assert( gen_e_list_length(split.matched1) + == gen_e_list_length(split.matched2) ); + + gen_e_list_scan(split.matched1,&scan1); + gen_e_list_scan(split.matched2,&scan2); + + while (gen_e_list_next(&scan1,&f1) && + gen_e_list_next(&scan2,&f2) ) + { + field_incl(f1,f2); + } + + if ( flowrow_wildcard(r1) && flowrow_wildcard(r2) ) + { + goto END; + } + else + { + flowrow_map fields1 = split.nomatch1; + flowrow_map fields2 = split.nomatch2; + + gen_e newrow1 = flowrow_row(get_stamp,fields1,r1->rest); + gen_e newrow2 = flowrow_row(get_stamp,fields2,r2->rest); + + flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem, + newrow1, newrow2); + } + } + END: + deleteregion(scratch_rgn); + } + + else /* potentially a problem normalizing a row? */ + { + failure("Unmatched case in row inclusion\n"); + return; + } +} + +gen_e flowrow_row(get_stamp_fn_ptr get_stamp,flowrow_map f, gen_e rest) deletes +{ + flowrow_map fields = flowrow_map_copy(flowrow_region,f); + + if (flowrow_map_empty(fields)) + { + return rest; + } + else + { + flowrow_map_scanner scan; + flowrow_field temp; + gen_e result; + int i = 2, + length = flowrow_map_length(fields); + stamp st[2+2*length]; + + st[0] = ROW_TYPE; + if (rest) + st[1] = flowrow_get_stamp(rest); + else + assert(0); + + flowrow_map_sort(fields,field_compare_ne); + + flowrow_map_scan(fields,&scan); + while(flowrow_map_next(&scan,&temp)) + { + st[i++] = stamp_string(temp->label); + if (temp->expr) + st[i++] = get_stamp(temp->expr); + else + assert(0); + } + + if ( (result = term_hash_find(flowrow_hash,st,2 + 2*length)) == NULL) + { + flowrow r = ralloc(flowrow_region, struct flowrow); + r->type = ROW_TYPE; + r->st = stamp_fresh(); + r->fields = fields; + r->rest = rest; + +#ifdef NONSPEC + r->base_sort = row_map_head(fields)->expr->sort; + r->sort = flowrow_sort; +#endif + result = (gen_e) r; + term_hash_insert(flowrow_hash,result,st,2+2*length); + } + /* assert(flowrow_is_normalized(result)); */ + return result; + + } +} + +#ifndef NONSPEC +static struct flowrow_gen zero_row = {ZERO_TYPE,ZERO_TYPE}; +static struct flowrow_gen one_row = {ONE_TYPE,ONE_TYPE}; +static struct flowrow_gen abs_row = {ABS_TYPE, ABS_TYPE}; +static struct flowrow_gen wild_row = {WILD_TYPE, WILD_TYPE}; + +gen_e flowrow_zero(void) +{ + return (gen_e)&zero_row; +} + +gen_e flowrow_one(void) +{ + return (gen_e)&one_row; +} + +gen_e flowrow_abs(void) +{ + return (gen_e)&abs_row; +} + +gen_e flowrow_wild(void) +{ + return (gen_e)&wild_row; +} + +gen_e flowrow_fresh(const char *name) +{ + flowrow_stats.fresh++; + return (gen_e)fv_fresh(flowrow_region,name); +} + +gen_e flowrow_fresh_small(const char *name) +{ + flowrow_stats.fresh_small++; + return (gen_e)fv_fresh_small(flowrow_region,name); +} + +gen_e flowrow_fresh_large(const char *name) +{ + flowrow_stats.fresh_large++; + return (gen_e)fv_fresh_large(flowrow_region,name); +} + +#else +static struct flowrow_gen term_zero_row = {flowrow_sort,ZERO_TYPE,ZERO_TYPE,term_sort}; +static struct flowrow_gen term_one_row = {flowrow_sort,ONE_TYPE,ONE_TYPE,term_sort}; +static struct flowrow_gen term_abs_row = {flowrow_sort,ABS_TYPE, ABS_TYPE,term_sort}; +static struct flowrow_gen term_wild_row = {flowrow_sort,WILD_TYPE, WILD_TYPE,term_sort}; + + +static struct flowrow_gen setif_zero_row = {flowrow_sort,ZERO_TYPE,ZERO_TYPE,setif_sort}; +static struct flowrow_gen setif_one_row = {flowrow_sort,ONE_TYPE,ONE_TYPE,setif_sort}; +static struct flowrow_gen setif_abs_row = {flowrow_sort,ABS_TYPE, ABS_TYPE,setif_sort}; +static struct flowrow_gen setif_wild_row = {flowrow_sort,WILD_TYPE, WILD_TYPE,setif_sort}; + +static struct flowrow_gen setst_zero_row = {flowrow_sort,ZERO_TYPE,ZERO_TYPE,setst_sort}; +static struct flowrow_gen setst_one_row = {flowrow_sort,ONE_TYPE,ONE_TYPE,setst_sort}; +static struct flowrow_gen setst_abs_row = {flowrow_sort,ABS_TYPE, ABS_TYPE,setst_sort}; +static struct flowrow_gen setst_wild_row = {flowrow_sort,WILD_TYPE, WILD_TYPE,setst_sort}; + + +gen_e flowrow_zero(sort_kind base_sort) +{ + switch (base_sort) + { + case setif_sort: + return (gen_e)&setif_zero_row; + case setst_sort: + return (gen_e)&setst_zero_row; + case term_sort: + return (gen_e)&term_zero_row; + default: + { + failure("No matching base sort: flowrow_zero\n"); + return NULL; + } + } + + return NULL; +} + +gen_e flowrow_one(sort_kind base_sort) +{ + switch (base_sort) + { + case setif_sort: + return (gen_e)&setif_one_row; + case setst_sort: + return (gen_e)&setst_one_row; + case term_sort: + return (gen_e)&term_one_row; + default: + { + failure("No matching base sort: flowrow_one\n"); + return NULL; + } + } + + return NULL; +} + +gen_e flowrow_abs(sort_kind base_sort) +{ + switch (base_sort) + { + case setif_sort: + return (gen_e)&setif_abs_row; + case setst_sort: + return (gen_e)&setst_abs_row; + case term_sort: + return (gen_e)&term_abs_row; + default: + { + failure("No matching base sort: flowrow_abs\n"); + return NULL; + } + } + + return NULL; +} + +gen_e flowrow_wild(sort_kind base_sort) +{ + + switch (base_sort) + { + case setif_sort: + return (gen_e)&setif_wild_row; + case setst_sort: + return (gen_e)&setst_wild_row; + case term_sort: + return (gen_e)&term_wild_row; + default: + { + failure("No matching base sort: flowrow_wild\n"); + return NULL; + } + } + + return NULL; +} + +gen_e flowrow_fresh(const char *name,sort_kind base_sort) +{ + + switch (base_sort) + { + case setif_sort: + return + case setst_sort: + return (gen_e)&setst_one_row; + case term_sort: + return (gen_e)&term_one_row; + default: + { + failure("No matching base sort: flowrow_one\n"); + return NULL; + } + } + + return NULL; +} + +gen_e flowrow_fresh_small(sort_kind base_sort) +{ + + switch (base_sort) + { + case setif_sort: + return (gen_e)&setif_one_row; + case setst_sort: + return (gen_e)&setst_one_row; + case term_sort: + return (gen_e)&term_one_row; + default: + { + failure("No matching base sort: flowrow_one\n"); + return NULL; + } + } + + return NULL; +} + +gen_e flowrow_fresh_large(sort_kind base_sort) +{ + +} + +sort_kind flowrow_base_sort(gen_e e) +{ + +} +#endif /* NONSPEC */ + + +gen_e flowrow_extract_field(const char *name, gen_e e) +{ + + static bool field_eq(const flowrow_field f) + { + return (! strcmp(f->label,name)); + } + + if (flowrow_is_row(e)) + { + flowrow_map fields = flowrow_get_fields(e); + flowrow_field f = flowrow_map_find(fields,field_eq); + + if (f) + return f->expr; + } + return NULL; +} + +gen_e flowrow_extract_rest(gen_e e) +{ + if (flowrow_is_row(e)) + return flowrow_get_rest(e); + else + return NULL; +} + +flowrow_map flowrow_extract_fields(gen_e e) +{ + if (flowrow_is_row(e)) + return flowrow_map_copy(flowrow_region,flowrow_get_fields(e)); + else + return NULL; +} + + +bool flowrow_is_alias(gen_e e) +{ + return ((flowrow_gen)e)->type == ALIAS_TYPE; +} + +bool flowrow_is_zero(gen_e e) +{ + return ((flowrow_gen)e)->type == ZERO_TYPE; +} + +bool flowrow_is_one(gen_e e) +{ + return ((flowrow_gen)e)->type == ONE_TYPE; +} + +bool flowrow_is_abs(gen_e e) +{ + return ((flowrow_gen)e)->type == ABS_TYPE; +} + +bool flowrow_is_wild(gen_e e) +{ + return ((flowrow_gen)e)->type == WILD_TYPE; +} + +bool flowrow_is_var(gen_e e) +{ + return ((flowrow_gen)e)->type == VAR_TYPE; +} + +bool flowrow_is_row(gen_e e) +{ + return ((flowrow_gen)e)->type == ROW_TYPE; +} + +void flowrow_init(void) +{ + flowrow_region = newregion(); + flowrow_hash = make_term_hash(flowrow_region); +} + +static void flowrow_reset_stats(void) +{ + flowrow_stats.fresh = 0; + flowrow_stats.fresh_small = 0; + flowrow_stats.fresh_large = 0; + + flowrow_stats.rows_disjoint_wild = 0; + flowrow_stats.rows_equal = 0; + flowrow_stats.rows_zero_one_wild = 0; + flowrow_stats.rows_l_inductive = 0; + flowrow_stats.rows_r_inductive = 0; + flowrow_stats.rows_disjoint_r1_minimal = 0; + flowrow_stats.rows_disjoint_r1_var_r2_minimal = 0; + flowrow_stats.rows_disjoint_r1_var_r2_maximal = 0; + flowrow_stats.rows_disjoint_r1_var_r2_closed = 0; + flowrow_stats.rows_disjoint_r1_var_r2_var_lt = 0; + flowrow_stats.rows_disjoint_r1_var_r2_var_gt = 0; + flowrow_stats.rows_equal_domains = 0; + flowrow_stats.rows_nonempty_intersection = 0; + flowrow_stats.rows_fresh = 0; + flowrow_stats.rows_fresh_large = 0; +} + +void flowrow_reset(void) deletes +{ + term_hash_delete(flowrow_hash); + deleteregion_ptr(&flowrow_region); + + flowrow_reset_stats(); + + flowrow_region = newregion(); + flowrow_hash = make_term_hash(flowrow_region); + +} + +static void fields_print(FILE *f,flowrow_map m,field_print_fn_ptr field_print) deletes +{ + flowrow_map_scanner scan; + flowrow_field temp; + + flowrow_map_scan(m,&scan); + + if (flowrow_map_next(&scan,&temp)) + { + fprintf(f,"%s : ",temp->label); + + if (field_print) + field_print(f,temp->expr); + else + fprintf(f,"?"); + } + + while (flowrow_map_next(&scan,&temp)) + { + fprintf(f,",%s : ",temp->label); + + if (field_print) + field_print(f,temp->expr); + else + fprintf(f,"?"); + } +} + +void flowrow_print(FILE *f,get_stamp_fn_ptr get_stamp, + field_print_fn_ptr field_print,gen_e row) deletes +{ + gen_e e = normalize_row(get_stamp,row); + + switch ( ((flowrow_gen)e)->type) + { + case ZERO_TYPE: + fprintf(f, "0"); + break; + case ONE_TYPE: + fprintf(f, "1"); + break; + case ABS_TYPE: + fprintf(f, "abs"); + break; + case WILD_TYPE: + fprintf(f, "wild"); + break; + case VAR_TYPE: + fprintf(f, fv_get_name((flow_var)e)); + break; + case ROW_TYPE: + fprintf(f, "<"); + fields_print(f, flowrow_get_fields(e), field_print); + fprintf(f, "|"); + flowrow_print(f, get_stamp, field_print, flowrow_get_rest(e)); + fprintf(f, ">"); + break; + default: + assert(0); + break; + } +} + +void flowrow_print_stats(FILE *f) +{ + fprintf(f,"\n========== Flow Var Stats ==========\n"); + fprintf(f,"Fresh : %d\n",flowrow_stats.fresh); + fprintf(f,"Fresh Small : %d\n",flowrow_stats.fresh_small); + fprintf(f,"Fresh Large : %d\n",flowrow_stats.fresh_large); + fprintf(f,"=====================================\n"); +} + +DEFINE_LIST(flowrow_map,flowrow_field) |