libbanshee/engine/term-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 <ansidecl.h>
  34 #include "term-sort.h"
  35
  36 struct term_constant_ /* extends gen_e */
  37 {
  38 #ifdef NONSPEC
  39   sort_kind sort;
  40 #endif
  41   int type;
  42   stamp st;
  43   char *name;
  44 };
  45
  46 typedef struct term_constant_ *term_constant_;
  47
  48 region term_sort_region;
  49 term_hash term_sort_hash;
  50 bool flag_occurs_check = FALSE;
  51
  52 struct term_stats term_stats;
  53
  54 stamp term_get_stamp(gen_e e)
  55 {
  56   if ( ((gen_term)e)->type == VAR_TYPE )
  57     return ((gen_term)term_get_ecr(e))->st;
  58   else
  59     return ((gen_term)e)->st;
  60 }
  61
  62 gen_e term_fresh(const char *name)
  63 {
  64   term_stats.fresh++;
  65   return (gen_e)tv_fresh(term_sort_region,name);
  66 }
  67
  68 gen_e term_fresh_large(const char *name)
  69 {
  70   term_stats.fresh_large++;
  71   return (gen_e)tv_fresh_large(term_sort_region,name);
  72 }
  73
  74 gen_e term_fresh_small(const char *name)
  75 {
  76   term_stats.fresh_small++;
  77   return (gen_e)tv_fresh_small(term_sort_region,name);
  78 }
  79
  80
  81 #ifdef NONSPEC
  82 static struct gen_term zero = {ZERO_TYPE,term_sort,ZERO_TYPE};
  83 static struct gen_term one  = {ONE_TYPE,term_sort,ONE_TYPE};
  84 #else
  85 static struct gen_term zero = {ZERO_TYPE,ZERO_TYPE};
  86 static struct gen_term one  = {ONE_TYPE,ONE_TYPE};
  87 #endif /* NONSPEC */
  88
  89 gen_e term_zero(void)
  90 {
  91   return (gen_e)&zero;
  92 }
  93
  94 gen_e term_one(void)
  95 {
  96   return (gen_e)&one;
  97 }
  98
  99
 100 gen_e term_constant(const char *str)
 101 {
 102   stamp st[2];
 103   gen_e result;
 104   char *name = rstrdup(term_sort_region,str);
 105
 106   assert (str != NULL);
 107
 108   st[0] = CONSTANT_TYPE;
 109   st[1] = stamp_string(name);
 110
 111   if ( (result = term_hash_find(term_sort_hash,st,2)) == NULL)
 112     {
 113       term_constant_ c = ralloc(term_sort_region, struct term_constant_);
 114       c->type = CONSTANT_TYPE;
 115       c->st = stamp_fresh();
 116       c->name = name;
 117
 118       result = (gen_e) c;
 119       term_hash_insert(term_sort_hash,result,st,2);
 120
 121       return result;
 122     }
 123
 124   else
 125     {
 126       return result;
 127     }
 128
 129 }
 130
 131 static bool term_is_bottom(gen_e e)
 132 {
 133   return (term_is_zero(e) || term_is_var(e));
 134 }
 135
 136 bool term_is_zero(gen_e e)
 137 {
 138   return ( ((gen_term)term_get_ecr(e))->type == ZERO_TYPE);
 139 }
 140
 141 bool term_is_one(gen_e e)
 142 {
 143   return ( ((gen_term)term_get_ecr(e))->type == ONE_TYPE);
 144 }
 145
 146 bool term_is_var(gen_e e)
 147 {
 148   return ( ((gen_term)term_get_ecr(e))->type == VAR_TYPE);
 149 }
 150
 151 bool term_is_constant(gen_e e)
 152 {
 153   return ( ((gen_term)term_get_ecr(e))->type == CONSTANT_TYPE);
 154 }
 155
 156 char *term_get_constant_name(gen_e e)
 157 {
 158   gen_e ecr = term_get_ecr(e);
 159   if(! term_is_constant(ecr))
 160     return NULL;
 161   else
 162     return ((term_constant_)ecr)->name;
 163 }
 164
 165 gen_e term_get_ecr(gen_e e)
 166 {
 167   if (((gen_term)e)->type == VAR_TYPE)
 168     return tv_get_ecr((term_var)e);
 169   else return e;
 170 }
 171
 172 static void fire_pending(term_var v, gen_e e,
 173                          con_match_fn_ptr con_match,
 174                          occurs_check_fn_ptr occurs)
 175 {
 176   gen_e_list_scanner scan;
 177   gen_e temp;
 178
 179   gen_e_list_scan(tv_get_pending(v),&scan);
 180   while (gen_e_list_next(&scan,&temp))
 181     {
 182       term_unify(con_match,occurs,temp,e);
 183     }
 184 }
 185
 186 static bool eq(gen_e e1, gen_e e2)
 187 {
 188   return term_get_ecr(e1) == term_get_ecr(e2);
 189 }
 190
 191 void term_unify(con_match_fn_ptr con_match, occurs_check_fn_ptr occurs,
 192                 gen_e a, gen_e b)
 193 {
 194   gen_e e1 = term_get_ecr(a),
 195     e2 = term_get_ecr(b);
 196
 197   if ( eq(e1,e2) )
 198     {
 199       return;
 200     }
 201   if (term_is_constant(e1) && term_is_constant(e2))
 202     {
 203       failure("Inconsistent system of constraints\n");
 204     }
 205   else if (term_is_var(e1))
 206     {
 207       term_var v = (term_var)e1;
 208
 209
 210       if (! term_is_bottom(e2))
 211         fire_pending(v,e2,con_match,occurs);
 212
 213       if (term_is_var(e2))
 214         tv_unify_vars(v,(term_var)e2);
 215       else /* v = e2, e2 is not a var */
 216         {
 217           if (occurs(v,e2))
 218             failure("Unify terms: occurs check failed\n");
 219           tv_unify(v,e2);
 220         }
 221     }
 222   else if (term_is_var(e2))
 223     {
 224       term_var v = (term_var)e2;
 225
 226       if (! term_is_bottom(e2))
 227         fire_pending(v,e1,con_match,occurs);
 228
 229       /* v = e1, e1 is not a var */
 230       if (occurs(v,e1))
 231         failure("Unify terms: occurs check failed\n");
 232       tv_unify(v,e1);
 233
 234     }
 235   else con_match(e1,e2);
 236 }
 237
 238 void term_cunify(con_match_fn_ptr con_match, occurs_check_fn_ptr occurs,
 239                  gen_e e1, gen_e e2)
 240 {
 241   if (term_is_bottom(e1) && term_is_var(e1))
 242     {
 243       term_var v1 = (term_var)e1;
 244       tv_add_pending(v1,e2);
 245     }
 246   else
 247     {
 248       term_unify(con_match,occurs,e1,e2);
 249     }
 250 }
 251
 252 static void term_reset_stats(void)
 253 {
 254   term_stats.fresh = 0;
 255   term_stats.fresh_small = 0;
 256   term_stats.fresh_large = 0;
 257 }
 258
 259 void term_print_stats(FILE *f)
 260 {
 261   fprintf(f,"\n========== Term Var Stats ==========\n");
 262   fprintf(f,"Fresh : %d\n",term_stats.fresh);
 263   fprintf(f,"Fresh Small : %d\n",term_stats.fresh_small);
 264   fprintf(f,"Fresh Large : %d\n",term_stats.fresh_large);
 265   fprintf(f,"=====================================\n");
 266 }
 267
 268 /* TODO */
 269 void term_print_constraint_graph(FILE *f ATTRIBUTE_UNUSED)
 270 {
 271 }
 272
 273 void term_init(void)
 274 {
 275   term_sort_region = newregion();
 276   term_sort_hash = make_term_hash(term_sort_region);
 277 }
 278
 279 void term_reset(void)
 280 {
 281   term_hash_delete(term_sort_hash);
 282   deleteregion_ptr(&term_sort_region);
 283
 284   term_reset_stats();
 285
 286   term_sort_region = newregion();
 287   term_sort_hash = make_term_hash(term_sort_region);
 288 }
 289
 290
 291