libbanshee/engine/flowrow-sort.c

   1 /*
   2  * Copyright (c) 2000-2001
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   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.
  16  *
  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
  27  * SUCH DAMAGE.
  28  *
  29  */
  30
  31 #include <regions.h>
  32 #include <assert.h>
  33 #include <stdio.h>
  34 #include <string.h>
  35 #include <ansidecl.h>
  36 #include "flowrow-sort.h"
  37 #include "termhash.h"
  38
  39 #include "setif-sort.h"
  40
  41 #define ABS_TYPE 2
  42 #define WILD_TYPE 3
  43 #define ROW_TYPE 4
  44
  45 /* generic flow row */
  46 struct flowrow_gen
  47 {
  48 #ifdef NONSPEC
  49   sort_kind sort;
  50 #endif
  51   int type;
  52   stamp st;
  53 #ifdef NONSPEC
  54   sort_kind base_sort;
  55 #endif
  56 };
  57
  58 typedef struct flowrow_gen *flowrow_gen;
  59
  60 struct flowrow
  61 {
  62 #ifdef NONSPEC
  63   sort_kind sort;
  64 #endif
  65   int type;
  66   stamp st;
  67 #ifdef NONSPEC
  68   sort_kind base_sort;
  69 #endif
  70   flowrow_map fields;
  71   gen_e rest;
  72 };
  73
  74 typedef struct flowrow *flowrow;
  75
  76 struct field_split
  77 {
  78   gen_e_list matched1;
  79   gen_e_list matched2;
  80   flowrow_map nomatch1;
  81   flowrow_map nomatch2;
  82 };
  83
  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;
  88
  89 stamp flowrow_get_stamp(gen_e e)
  90 {
  91   if ( ((flowrow_gen)e)->type == ALIAS_TYPE)
  92     return ((flowrow_gen)fv_get_alias( (flow_var)e ))->st;
  93   else
  94     return ((flowrow_gen)e)->st;
  95
  96 }
  97
  98 static flowrow_map flowrow_get_fields(gen_e e)
  99 {
 100   assert (flowrow_is_row(e));
 101
 102   return ((flowrow)e)->fields;
 103 }
 104
 105 static gen_e flowrow_get_rest(gen_e e)
 106 {
 107   assert(flowrow_is_row(e));
 108
 109   return ((flowrow)e)->rest;
 110 }
 111
 112
 113 static int field_compare(const flowrow_field f1,const flowrow_field f2)
 114
 115 {
 116   int compare = strcmp(f1->label,f2->label);
 117   return compare;
 118 }
 119
 120
 121 static int field_compare_ne(const flowrow_field f1,const flowrow_field f2)
 122
 123 {
 124   int compare = strcmp(f1->label,f2->label);
 125
 126   if (! compare) /* rows should never have two fields with the same labels */
 127     {
 128       failure("Multiple fields in this row share the same label\n");
 129     }
 130   return compare;
 131 }
 132
 133 static struct field_split split_fields(region r, flowrow_map fields1,
 134                                        flowrow_map fields2)
 135 {
 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;;
 141
 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);
 146
 147   flowrow_map_scan(fields1,&scan1);
 148   flowrow_map_scan(fields2,&scan2);
 149
 150   while (TRUE)
 151     {
 152       if (consumed1)
 153         fields1_remain = flowrow_map_next(&scan1,&field1);
 154       if (consumed2)
 155         fields2_remain = flowrow_map_next(&scan2,&field2);
 156
 157       if (fields1_remain && fields2_remain)
 158         {
 159           int compare_fields = field_compare(field1,field2);
 160
 161           if (compare_fields < 0)
 162             {
 163               flowrow_map_cons(field1,split.nomatch1);
 164               consumed1 = TRUE;
 165               consumed2 = FALSE;
 166             }
 167           else if (compare_fields > 0)
 168             {
 169               flowrow_map_cons(field2,split.nomatch2);
 170               consumed2 = TRUE;
 171               consumed1 = FALSE;
 172             }
 173           else /* two fields are equal */
 174             {
 175               gen_e_list_cons(field1->expr,split.matched1);
 176               gen_e_list_cons(field2->expr,split.matched2);
 177               consumed1 = TRUE;
 178               consumed2 = TRUE;
 179               continue;
 180             }
 181         }
 182       else if (fields1_remain)
 183         {
 184           /* flowrow_map_append(split.nomatch1,flowrow_map_copy(r,fields1)); */
 185           flowrow_map_cons(field1,split.nomatch1);
 186
 187           while (flowrow_map_next(&scan1,&field1))
 188             {
 189               flowrow_map_cons(field1,split.nomatch1);
 190             }
 191
 192           break;
 193         }
 194       else if (fields2_remain)
 195         {
 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))
 199             {
 200               flowrow_map_cons(field2,split.nomatch2);
 201             }
 202           break;
 203         }
 204       else /* no remaining fields, so */ break;
 205     }
 206
 207   return split;
 208 }
 209
 210 static bool flowrow_is_normalized(gen_e r)
 211 {
 212  if ( flowrow_is_row(r) )
 213     {
 214       gen_e rest = flowrow_get_rest(r);
 215
 216       if ( flowrow_is_row(rest) || flowrow_is_alias(rest) )
 217         return FALSE;
 218     }
 219  else if ( flowrow_is_alias(r) )
 220     return FALSE;
 221
 222   return TRUE;
 223 }
 224
 225 static gen_e normalize(get_stamp_fn_ptr get_stamp,
 226                          flowrow_map m,gen_e r) deletes
 227 {
 228   if (flowrow_is_row(r))
 229     {
 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));
 234     }
 235   else if (flowrow_is_alias(r))
 236     {
 237       assert (! flowrow_is_alias(fv_get_alias((flow_var)r)) );
 238       return normalize(get_stamp, m,fv_get_alias((flow_var)r));
 239     }
 240   else
 241     return flowrow_row(get_stamp,m,r);
 242 }
 243
 244 static gen_e normalize_row(get_stamp_fn_ptr get_stamp, gen_e r) deletes
 245 {
 246   if (flowrow_is_normalized(r))
 247     return r;
 248   else /* normalize the row */
 249     return normalize(get_stamp,new_flowrow_map(flowrow_region),r);
 250 }
 251
 252 static bool eq(gen_e e1, gen_e e2)
 253 {
 254   return ( flowrow_get_stamp(e1) == flowrow_get_stamp(e2) );
 255 }
 256
 257
 258 /*
 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).
 261
 262   tlv(row) = {X} if row is a var X, {} otherwise
 263 */
 264 static bool l_inductive(gen_e e1, gen_e e2)
 265 {
 266   if (flowrow_is_var(e2))
 267     {
 268       if (flowrow_is_var(e1))
 269         return flowrow_get_stamp(e2) > flowrow_get_stamp(e1);
 270       else return TRUE;
 271     }
 272   return FALSE;
 273 }
 274
 275 /*
 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)
 278 */
 279 static bool r_inductive(gen_e e1, gen_e e2)
 280 {
 281   if (flowrow_is_var(e1))
 282     {
 283       if (flowrow_is_var(e2))
 284         return flowrow_get_stamp(e1) > flowrow_get_stamp(e2);
 285       else return TRUE;
 286     }
 287   return FALSE;
 288 }
 289
 290 static inline bool flowrow_minimal(flowrow r)
 291 {
 292   return flowrow_is_zero(r->rest);
 293 }
 294
 295 static inline bool flowrow_maximal(flowrow r)
 296 {
 297   return flowrow_is_one(r->rest);
 298 }
 299
 300 static inline bool flowrow_closed(flowrow r)
 301 {
 302   return flowrow_is_abs(r->rest);
 303 }
 304
 305 static inline bool flowrow_wildcard(flowrow r)
 306 {
 307   return flowrow_is_wild(r->rest);
 308 }
 309
 310 static inline bool flowrow_var(flowrow r)
 311 {
 312   return flowrow_is_var(r->rest);
 313 }
 314
 315 static gen_e contour_instantiate(fresh_fn_ptr fresh,
 316                                  get_stamp_fn_ptr get_stamp,
 317                                  gen_e e) deletes
 318 {
 319   if (flowrow_is_row(e))
 320     {
 321       gen_e result;
 322       flowrow_map_scanner scan;
 323       flowrow_field f;
 324       gen_e row = normalize_row(get_stamp,e);
 325
 326       region scratch_rgn = newregion();
 327
 328       flowrow_map new_fields = new_flowrow_map(scratch_rgn);
 329
 330       flowrow_map_scan(flowrow_get_fields(row),&scan);
 331
 332       while (flowrow_map_next(&scan,&f))
 333         {
 334           flowrow_field new_field =
 335             ralloc(flowrow_region,struct flowrow_field);
 336           new_field->label = f->label;
 337           new_field->expr = fresh(NULL);
 338
 339           flowrow_map_cons(new_field,new_fields);
 340         }
 341
 342       result = flowrow_row(get_stamp,new_fields,flowrow_fresh(NULL));
 343
 344       deleteregion(scratch_rgn);
 345
 346       assert( flowrow_is_row(result) );
 347
 348       return result;
 349     }
 350
 351   else /* TODO */
 352     {
 353       failure("Unmatched contour\n");
 354       return NULL;
 355     }
 356 }
 357
 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)
 360 {
 361   if (flowrow_is_row(e))
 362     {
 363       contour result;
 364
 365       result = ralloc(flowrow_region,struct contour);
 366       result->shape = e;
 367       result->fresh = fresh;
 368       result->get_stamp = get_stamp;
 369       result->instantiate = contour_instantiate;
 370
 371       return result;
 372     }
 373   else /* TODO */
 374     {
 375       failure("Unmatched contour\n");
 376       return NULL;
 377     }
 378 }
 379
 380
 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
 384 {
 385   gen_e temp;
 386   gen_e_list_scanner scan;
 387
 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);
 391
 392 }
 393
 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
 397 {
 398   gen_e temp;
 399   gen_e_list_scanner scan;
 400
 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);
 404 }
 405
 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
 409 {
 410   if (fv_has_contour(v)) /* _ <= v, and v has a contour */
 411     {
 412       gen_e shape = fv_instantiate_contour(v);
 413
 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);
 417
 418       flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,e,shape);
 419
 420     }
 421
 422   else if (flowrow_is_var(e))
 423     {
 424       flow_var v_lb = (flow_var)e;
 425
 426       if (fv_has_contour(v_lb)) /* v1 <= v2, v1 has a contour */
 427         {
 428           gen_e shape = fv_instantiate_contour(v_lb);
 429
 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);
 433
 434           flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,
 435                             shape,(gen_e)v);
 436
 437         }
 438
 439       else /* we have v1 <= v2, no contours */
 440         {
 441           bool redundant;
 442
 443           fv_unify_contour(v,(flow_var)e);
 444           redundant = fv_add_lb(v,e,flowrow_get_stamp(e));
 445
 446           if (! redundant)
 447             trans_ubs(fresh,get_stamp,field_incl,zero_elem,v,e);
 448
 449         }
 450     }
 451   else /* we have c(...) <= v, and v has no contour */
 452     {
 453       gen_e shape = NULL;
 454       fv_set_contour(v,get_contour(fresh,get_stamp,zero_elem,e));
 455
 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);
 460
 461       flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,e,shape);
 462
 463     }
 464 }
 465
 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
 469 {
 470   if (fv_has_contour(v)) /* v isn't aliased, and we discovered a contour*/
 471     {
 472       gen_e shape = fv_instantiate_contour(v);
 473
 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);
 477
 478       flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,shape,e);
 479
 480     }
 481
 482   else if (flowrow_is_var(e))
 483     {
 484       flow_var v2 = (flow_var)e;
 485
 486       if (fv_has_contour(v2)) /* v2 isn't aliased, and we discovered a contour */
 487         {
 488           gen_e shape = fv_instantiate_contour(v2);
 489
 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);
 493
 494
 495           flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,
 496                             (gen_e)v,shape);
 497
 498         }
 499
 500       else /* we have v1 <= v2, no contours */
 501         {
 502           bool redundant;
 503
 504           fv_unify_contour(v,(flow_var)e);
 505           redundant = fv_add_ub(v,e,flowrow_get_stamp(e));
 506
 507           if (! redundant)
 508             trans_lbs(fresh,get_stamp,field_incl,zero_elem,v,e);
 509
 510         }
 511     }
 512   else /* we have v <= c(...), and v has no contour */
 513     {
 514       gen_e shape = NULL;
 515       fv_set_contour(v,get_contour(fresh,get_stamp,zero_elem,e));
 516
 517       shape = fv_instantiate_contour(v);
 518
 519       if (! flowrow_is_row(shape) )
 520         {
 521           assert(0);
 522         }
 523
 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);
 527
 528
 529       flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,shape,e);
 530
 531     }
 532
 533 }
 534
 535 /* END */
 536
 537
 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,
 540                        gen_e b) deletes
 541 {
 542   gen_e e1 = normalize_row(get_stamp, a),
 543     e2 = normalize_row(get_stamp, b);
 544
 545   if (eq(e1,e2))
 546     return;
 547   else if (flowrow_is_zero(e1) || flowrow_is_wild(e1))
 548     return;
 549   else if (flowrow_is_one(e2) || flowrow_is_wild(e2))
 550     return;
 551
 552   else if ( l_inductive(e1,e2) )
 553     {
 554       flow_var v2 = (flow_var)e2;
 555
 556       flowrow_stats.rows_l_inductive++;
 557
 558       update_lower_bound(fresh,get_stamp,field_incl,zero_elem,v2,e1);
 559       return;
 560     }
 561
 562   else if ( r_inductive(e1,e2) )
 563     {
 564       flow_var v1 = (flow_var)e1;
 565
 566       flowrow_stats.rows_r_inductive++;
 567
 568       update_upper_bound(fresh,get_stamp,field_incl,zero_elem,v1,e2);
 569       return;
 570     }
 571
 572   else if ( flowrow_is_row(e1) && flowrow_is_row(e2))
 573     {
 574       region scratch_rgn = newregion();
 575
 576       flowrow r1 = (flowrow)e1,
 577         r2 = (flowrow)e2;
 578
 579       struct field_split split =
 580         split_fields(scratch_rgn,r1->fields,r2->fields);
 581
 582       if ( gen_e_list_empty(split.matched1) )
 583         {
 584           assert ( gen_e_list_empty(split.matched2) );
 585
 586           if (flowrow_wildcard(r1) || flowrow_minimal(r1))
 587             {
 588               gen_e newrow =
 589                 flowrow_row(get_stamp,split.nomatch1,flowrow_get_rest(e1));
 590
 591               flowrow_inclusion(fresh,get_stamp,field_incl, zero_elem,newrow,
 592                                 flowrow_get_rest(e2));
 593             }
 594           else if (flowrow_maximal(r2) || flowrow_closed(r2))
 595             {
 596               gen_e newrow =
 597                 flowrow_row(get_stamp,split.nomatch2,flowrow_get_rest(e2));
 598
 599               flowrow_inclusion(fresh, get_stamp,field_incl,zero_elem,
 600                                 flowrow_get_rest(e1),newrow);
 601             }
 602           else
 603             {
 604               gen_e rest1 = flowrow_get_rest(e1),
 605                 rest2 = flowrow_get_rest(e2);
 606
 607               /*assert( flowrow_is_var(rest1) && flowrow_is_var(rest2));*/
 608
 609               if ( eq(rest1,rest2))
 610                   failure("Recursive row resolution\n");
 611               else
 612                 {
 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);
 616
 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);
 621                 }
 622
 623             }
 624         }
 625
 626       else /* some fields matched */
 627         {
 628           gen_e_list_scanner scan1, scan2;
 629           gen_e f1,f2;
 630
 631           assert( gen_e_list_length(split.matched1)
 632                   == gen_e_list_length(split.matched2) );
 633
 634           gen_e_list_scan(split.matched1,&scan1);
 635           gen_e_list_scan(split.matched2,&scan2);
 636
 637           while (gen_e_list_next(&scan1,&f1) &&
 638                  gen_e_list_next(&scan2,&f2) )
 639             {
 640               field_incl(f1,f2);
 641             }
 642
 643           if ( flowrow_wildcard(r1) && flowrow_wildcard(r2) )
 644             {
 645               goto END;
 646             }
 647           else
 648             {
 649               flowrow_map fields1 = split.nomatch1;
 650               flowrow_map fields2 = split.nomatch2;
 651
 652               gen_e newrow1 = flowrow_row(get_stamp,fields1,r1->rest);
 653               gen_e newrow2 = flowrow_row(get_stamp,fields2,r2->rest);
 654
 655               flowrow_inclusion(fresh,get_stamp,field_incl,zero_elem,
 656                                 newrow1, newrow2);
 657             }
 658         }
 659     END:
 660       deleteregion(scratch_rgn);
 661     }
 662
 663   else /* potentially a problem normalizing a row? */
 664     {
 665       failure("Unmatched case in row inclusion\n");
 666       return;
 667     }
 668 }
 669
 670 gen_e flowrow_row(get_stamp_fn_ptr get_stamp,flowrow_map f, gen_e rest) deletes
 671 {
 672   flowrow_map fields = flowrow_map_copy(flowrow_region,f);
 673
 674   if (flowrow_map_empty(fields))
 675     {
 676       return rest;
 677     }
 678   else
 679     {
 680       flowrow_map_scanner scan;
 681       flowrow_field temp;
 682       gen_e result;
 683       int i = 2,
 684         length = flowrow_map_length(fields);
 685       stamp st[2+2*length];
 686
 687       st[0] = ROW_TYPE;
 688       if (rest)
 689         st[1] = flowrow_get_stamp(rest);
 690       else
 691         assert(0);
 692
 693       flowrow_map_sort(fields,field_compare_ne);
 694
 695       flowrow_map_scan(fields,&scan);
 696       while(flowrow_map_next(&scan,&temp))
 697       {
 698         st[i++] = stamp_string(temp->label);
 699         if (temp->expr)
 700           st[i++] = get_stamp(temp->expr);
 701         else
 702           assert(0);
 703       }
 704
 705       if ( (result = term_hash_find(flowrow_hash,st,2 + 2*length)) == NULL)
 706         {
 707           flowrow r = ralloc(flowrow_region, struct flowrow);
 708           r->type = ROW_TYPE;
 709           r->st = stamp_fresh();
 710           r->fields = fields;
 711           r->rest = rest;
 712
 713 #ifdef NONSPEC
 714           r->base_sort = row_map_head(fields)->expr->sort;
 715           r->sort = flowrow_sort;
 716 #endif
 717           result = (gen_e) r;
 718           term_hash_insert(flowrow_hash,result,st,2+2*length);
 719         }
 720       /*  assert(flowrow_is_normalized(result)); */
 721       return result;
 722
 723     }
 724 }
 725
 726 #ifndef NONSPEC
 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};
 731
 732 gen_e flowrow_zero(void)
 733 {
 734   return (gen_e)&zero_row;
 735 }
 736
 737 gen_e flowrow_one(void)
 738 {
 739   return (gen_e)&one_row;
 740 }
 741
 742 gen_e flowrow_abs(void)
 743 {
 744   return (gen_e)&abs_row;
 745 }
 746
 747 gen_e flowrow_wild(void)
 748 {
 749   return (gen_e)&wild_row;
 750 }
 751
 752 gen_e flowrow_fresh(const char *name)
 753 {
 754   flowrow_stats.fresh++;
 755   return (gen_e)fv_fresh(flowrow_region,name);
 756 }
 757
 758 gen_e flowrow_fresh_small(const char *name)
 759 {
 760   flowrow_stats.fresh_small++;
 761   return (gen_e)fv_fresh_small(flowrow_region,name);
 762 }
 763
 764 gen_e flowrow_fresh_large(const char *name)
 765 {
 766   flowrow_stats.fresh_large++;
 767   return (gen_e)fv_fresh_large(flowrow_region,name);
 768 }
 769
 770 #else
 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};
 775
 776
 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};
 781
 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};
 786
 787
 788 gen_e flowrow_zero(sort_kind base_sort)
 789 {
 790   switch (base_sort)
 791     {
 792     case setif_sort:
 793       return (gen_e)&setif_zero_row;
 794     case setst_sort:
 795       return (gen_e)&setst_zero_row;
 796     case term_sort:
 797       return (gen_e)&term_zero_row;
 798     default:
 799       {
 800         failure("No matching base sort: flowrow_zero\n");
 801         return NULL;
 802       }
 803     }
 804
 805   return NULL;
 806 }
 807
 808 gen_e flowrow_one(sort_kind base_sort)
 809 {
 810   switch (base_sort)
 811     {
 812     case setif_sort:
 813       return (gen_e)&setif_one_row;
 814     case setst_sort:
 815       return (gen_e)&setst_one_row;
 816     case term_sort:
 817       return (gen_e)&term_one_row;
 818     default:
 819       {
 820         failure("No matching base sort: flowrow_one\n");
 821         return NULL;
 822       }
 823     }
 824
 825   return NULL;
 826 }
 827
 828 gen_e flowrow_abs(sort_kind base_sort)
 829 {
 830   switch (base_sort)
 831     {
 832     case setif_sort:
 833       return (gen_e)&setif_abs_row;
 834     case setst_sort:
 835       return (gen_e)&setst_abs_row;
 836     case term_sort:
 837       return (gen_e)&term_abs_row;
 838     default:
 839       {
 840         failure("No matching base sort: flowrow_abs\n");
 841         return NULL;
 842       }
 843     }
 844
 845   return NULL;
 846 }
 847
 848 gen_e flowrow_wild(sort_kind base_sort)
 849 {
 850
 851   switch (base_sort)
 852     {
 853     case setif_sort:
 854       return (gen_e)&setif_wild_row;
 855     case setst_sort:
 856       return (gen_e)&setst_wild_row;
 857     case term_sort:
 858       return (gen_e)&term_wild_row;
 859     default:
 860       {
 861         failure("No matching base sort: flowrow_wild\n");
 862         return NULL;
 863       }
 864     }
 865
 866   return NULL;
 867 }
 868
 869 gen_e flowrow_fresh(const char *name,sort_kind base_sort)
 870 {
 871
 872   switch (base_sort)
 873     {
 874     case setif_sort:
 875       return
 876     case setst_sort:
 877       return (gen_e)&setst_one_row;
 878     case term_sort:
 879       return (gen_e)&term_one_row;
 880     default:
 881       {
 882         failure("No matching base sort: flowrow_one\n");
 883         return NULL;
 884       }
 885     }
 886
 887   return NULL;
 888 }
 889
 890 gen_e flowrow_fresh_small(sort_kind base_sort)
 891 {
 892
 893   switch (base_sort)
 894     {
 895     case setif_sort:
 896       return (gen_e)&setif_one_row;
 897     case setst_sort:
 898       return (gen_e)&setst_one_row;
 899     case term_sort:
 900       return (gen_e)&term_one_row;
 901     default:
 902       {
 903         failure("No matching base sort: flowrow_one\n");
 904         return NULL;
 905       }
 906     }
 907
 908   return NULL;
 909 }
 910
 911 gen_e flowrow_fresh_large(sort_kind base_sort)
 912 {
 913
 914 }
 915
 916 sort_kind flowrow_base_sort(gen_e e)
 917 {
 918
 919 }
 920 #endif /* NONSPEC */
 921
 922 static const char* field_eq_name;
 923 static bool field_eq(const flowrow_field f)
 924 {
 925   return (! strcmp(f->label,field_eq_name));
 926 }
 927
 928 gen_e flowrow_extract_field(const char *name, gen_e e)
 929 {
 930   if (flowrow_is_row(e))
 931     {
 932       flowrow_map fields = flowrow_get_fields(e);
 933       flowrow_field f;
 934
 935       field_eq_name = name;
 936       f = flowrow_map_find(fields,field_eq);
 937
 938       if (f)
 939         return f->expr;
 940     }
 941   return NULL;
 942 }
 943
 944 gen_e flowrow_extract_rest(gen_e e)
 945 {
 946   if (flowrow_is_row(e))
 947     return flowrow_get_rest(e);
 948   else
 949     return NULL;
 950 }
 951
 952 flowrow_map flowrow_extract_fields(gen_e e)
 953 {
 954   if (flowrow_is_row(e))
 955     return flowrow_map_copy(flowrow_region,flowrow_get_fields(e));
 956   else
 957     return NULL;
 958 }
 959
 960
 961 bool flowrow_is_alias(gen_e e)
 962 {
 963   return ((flowrow_gen)e)->type == ALIAS_TYPE;
 964 }
 965
 966 bool flowrow_is_zero(gen_e e)
 967 {
 968   return ((flowrow_gen)e)->type == ZERO_TYPE;
 969 }
 970
 971 bool flowrow_is_one(gen_e e)
 972 {
 973   return ((flowrow_gen)e)->type == ONE_TYPE;
 974 }
 975
 976 bool flowrow_is_abs(gen_e e)
 977 {
 978   return ((flowrow_gen)e)->type == ABS_TYPE;
 979 }
 980
 981 bool flowrow_is_wild(gen_e e)
 982 {
 983   return ((flowrow_gen)e)->type == WILD_TYPE;
 984 }
 985
 986 bool flowrow_is_var(gen_e e)
 987 {
 988   return ((flowrow_gen)e)->type == VAR_TYPE;
 989 }
 990
 991 bool flowrow_is_row(gen_e e)
 992 {
 993   return ((flowrow_gen)e)->type == ROW_TYPE;
 994 }
 995
 996 void flowrow_init(void)
 997 {
 998   flowrow_region = newregion();
 999   flowrow_hash = make_term_hash(flowrow_region);
1000 }
1001
1002 static void flowrow_reset_stats(void)
1003 {
1004   flowrow_stats.fresh = 0;
1005   flowrow_stats.fresh_small = 0;
1006   flowrow_stats.fresh_large = 0;
1007
1008   flowrow_stats.rows_disjoint_wild = 0;
1009   flowrow_stats.rows_equal = 0;
1010   flowrow_stats.rows_zero_one_wild = 0;
1011   flowrow_stats.rows_l_inductive = 0;
1012   flowrow_stats.rows_r_inductive = 0;
1013   flowrow_stats.rows_disjoint_r1_minimal = 0;
1014   flowrow_stats.rows_disjoint_r1_var_r2_minimal = 0;
1015   flowrow_stats.rows_disjoint_r1_var_r2_maximal = 0;
1016   flowrow_stats.rows_disjoint_r1_var_r2_closed = 0;
1017   flowrow_stats.rows_disjoint_r1_var_r2_var_lt = 0;
1018   flowrow_stats.rows_disjoint_r1_var_r2_var_gt = 0;
1019   flowrow_stats.rows_equal_domains = 0;
1020   flowrow_stats.rows_nonempty_intersection = 0;
1021   flowrow_stats.rows_fresh = 0;
1022   flowrow_stats.rows_fresh_large = 0;
1023 }
1024
1025 void flowrow_reset(void) deletes
1026 {
1027   term_hash_delete(flowrow_hash);
1028   deleteregion_ptr(&flowrow_region);
1029
1030   flowrow_reset_stats();
1031
1032   flowrow_region = newregion();
1033   flowrow_hash = make_term_hash(flowrow_region);
1034
1035 }
1036
1037 static void fields_print(FILE *f,flowrow_map m,field_print_fn_ptr field_print) deletes
1038 {
1039   flowrow_map_scanner scan;
1040   flowrow_field temp;
1041
1042   flowrow_map_scan(m,&scan);
1043
1044   if (flowrow_map_next(&scan,&temp))
1045     {
1046       fprintf(f,"%s : ",temp->label);
1047
1048       if (field_print)
1049         field_print(f,temp->expr);
1050       else
1051         fprintf(f,"?");
1052     }
1053
1054   while (flowrow_map_next(&scan,&temp))
1055     {
1056       fprintf(f,",%s : ",temp->label);
1057
1058       if (field_print)
1059         field_print(f,temp->expr);
1060       else
1061         fprintf(f,"?");
1062     }
1063 }
1064
1065 void flowrow_print(FILE *f,get_stamp_fn_ptr get_stamp,
1066                    field_print_fn_ptr field_print,gen_e row) deletes
1067 {
1068   gen_e e = normalize_row(get_stamp,row);
1069
1070   switch ( ((flowrow_gen)e)->type)
1071     {
1072     case ZERO_TYPE:
1073       fprintf(f, "0");
1074       break;
1075     case ONE_TYPE:
1076       fprintf(f, "1");
1077       break;
1078     case ABS_TYPE:
1079       fprintf(f, "abs");
1080       break;
1081     case WILD_TYPE:
1082       fprintf(f, "wild");
1083       break;
1084     case VAR_TYPE:
1085       fprintf(f, fv_get_name((flow_var)e));
1086       break;
1087     case ROW_TYPE:
1088       fprintf(f, "<");
1089       fields_print(f, flowrow_get_fields(e), field_print);
1090       fprintf(f, "|");
1091       flowrow_print(f, get_stamp, field_print, flowrow_get_rest(e));
1092       fprintf(f, ">");
1093       break;
1094     default:
1095       assert(0);
1096       break;
1097     }
1098 }
1099
1100 void flowrow_print_stats(FILE *f)
1101 {
1102   fprintf(f,"\n========== Flow Var Stats ==========\n");
1103   fprintf(f,"Fresh : %d\n",flowrow_stats.fresh);
1104   fprintf(f,"Fresh Small : %d\n",flowrow_stats.fresh_small);
1105   fprintf(f,"Fresh Large : %d\n",flowrow_stats.fresh_large);
1106   fprintf(f,"=====================================\n");
1107 }
1108
1109 DEFINE_LIST(flowrow_map,flowrow_field)