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
34 #include "term-sort.h"
36 struct term_constant_ /* extends gen_e */
46 typedef struct term_constant_ *term_constant_;
48 region term_sort_region;
49 term_hash term_sort_hash;
50 bool flag_occurs_check = FALSE;
52 struct term_stats term_stats;
54 stamp term_get_stamp(gen_e e)
56 if ( ((gen_term)e)->type == VAR_TYPE )
57 return ((gen_term)term_get_ecr(e))->st;
59 return ((gen_term)e)->st;
62 gen_e term_fresh(const char *name)
65 return (gen_e)tv_fresh(term_sort_region,name);
68 gen_e term_fresh_large(const char *name)
70 term_stats.fresh_large++;
71 return (gen_e)tv_fresh_large(term_sort_region,name);
74 gen_e term_fresh_small(const char *name)
76 term_stats.fresh_small++;
77 return (gen_e)tv_fresh_small(term_sort_region,name);
82 static struct gen_term zero = {ZERO_TYPE,term_sort,ZERO_TYPE};
83 static struct gen_term one = {ONE_TYPE,term_sort,ONE_TYPE};
85 static struct gen_term zero = {ZERO_TYPE,ZERO_TYPE};
86 static struct gen_term one = {ONE_TYPE,ONE_TYPE};
100 gen_e term_constant(const char *str)
104 char *name = rstrdup(term_sort_region,str);
106 assert (str != NULL);
108 st[0] = CONSTANT_TYPE;
109 st[1] = stamp_string(name);
111 if ( (result = term_hash_find(term_sort_hash,st,2)) == NULL)
113 term_constant_ c = ralloc(term_sort_region, struct term_constant_);
114 c->type = CONSTANT_TYPE;
115 c->st = stamp_fresh();
119 term_hash_insert(term_sort_hash,result,st,2);
131 static bool term_is_bottom(gen_e e)
133 return (term_is_zero(e) || term_is_var(e));
136 bool term_is_zero(gen_e e)
138 return ( ((gen_term)term_get_ecr(e))->type == ZERO_TYPE);
141 bool term_is_one(gen_e e)
143 return ( ((gen_term)term_get_ecr(e))->type == ONE_TYPE);
146 bool term_is_var(gen_e e)
148 return ( ((gen_term)term_get_ecr(e))->type == VAR_TYPE);
151 bool term_is_constant(gen_e e)
153 return ( ((gen_term)term_get_ecr(e))->type == CONSTANT_TYPE);
156 char *term_get_constant_name(gen_e e)
158 gen_e ecr = term_get_ecr(e);
159 if(! term_is_constant(ecr))
162 return ((term_constant_)ecr)->name;
165 gen_e term_get_ecr(gen_e e)
167 if (((gen_term)e)->type == VAR_TYPE)
168 return tv_get_ecr((term_var)e);
172 static void fire_pending(term_var v, gen_e e,
173 con_match_fn_ptr con_match,
174 occurs_check_fn_ptr occurs)
176 gen_e_list_scanner scan;
179 gen_e_list_scan(tv_get_pending(v),&scan);
180 while (gen_e_list_next(&scan,&temp))
182 term_unify(con_match,occurs,temp,e);
186 static bool eq(gen_e e1, gen_e e2)
188 return term_get_ecr(e1) == term_get_ecr(e2);
191 void term_unify(con_match_fn_ptr con_match, occurs_check_fn_ptr occurs,
194 gen_e e1 = term_get_ecr(a),
195 e2 = term_get_ecr(b);
201 if (term_is_constant(e1) && term_is_constant(e2))
203 failure("Inconsistent system of constraints\n");
205 else if (term_is_var(e1))
207 term_var v = (term_var)e1;
210 if (! term_is_bottom(e2))
211 fire_pending(v,e2,con_match,occurs);
214 tv_unify_vars(v,(term_var)e2);
215 else /* v = e2, e2 is not a var */
218 failure("Unify terms: occurs check failed\n");
222 else if (term_is_var(e2))
224 term_var v = (term_var)e2;
226 if (! term_is_bottom(e2))
227 fire_pending(v,e1,con_match,occurs);
229 /* v = e1, e1 is not a var */
231 failure("Unify terms: occurs check failed\n");
235 else con_match(e1,e2);
238 void term_cunify(con_match_fn_ptr con_match, occurs_check_fn_ptr occurs,
241 if (term_is_bottom(e1) && term_is_var(e1))
243 term_var v1 = (term_var)e1;
244 tv_add_pending(v1,e2);
248 term_unify(con_match,occurs,e1,e2);
252 static void term_reset_stats(void)
254 term_stats.fresh = 0;
255 term_stats.fresh_small = 0;
256 term_stats.fresh_large = 0;
259 void term_print_stats(FILE *f)
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");
269 void term_print_constraint_graph(FILE *f ATTRIBUTE_UNUSED)
275 term_sort_region = newregion();
276 term_sort_hash = make_term_hash(term_sort_region);
279 void term_reset(void)
281 term_hash_delete(term_sort_hash);
282 deleteregion_ptr(&term_sort_region);
286 term_sort_region = newregion();
287 term_sort_hash = make_term_hash(term_sort_region);