00001 /* Part of the culibs project, <http://www.eideticdew.org/culibs/>. 00002 * Copyright (C) 2008--2009 Petter Urkedal <urkedal@nbi.dk> 00003 * 00004 * This program is free software: you can redistribute it and/or modify 00005 * it under the terms of the GNU General Public License as published by 00006 * the Free Software Foundation, either version 3 of the License, or 00007 * (at your option) any later version. 00008 * 00009 * This program is distributed in the hope that it will be useful, 00010 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00012 * GNU General Public License for more details. 00013 * 00014 * You should have received a copy of the GNU General Public License 00015 * along with this program. If not, see <http://www.gnu.org/licenses/>. 00016 */ 00017 00018 #ifndef CUEX_OCCURTREE_H 00019 #define CUEX_OCCURTREE_H 00020 00021 #include <cuex/iteration.h> 00022 #include <cucon/ucset.h> 00023 #include <stdio.h> 00024 00025 CU_BEGIN_DECLARATIONS 00026 /** \defgroup cuex_occurtree_h cuex/occurtree.h: Caching of Variable Occurences 00027 ** @{ \ingroup cuex_mod */ 00028 00029 struct cuex_occurtree 00030 { 00031 cuex_t e; 00032 cu_bool_least_t has_ref; 00033 int mu_height; 00034 cucon_ucset_t free_vars; 00035 cuex_occurtree_t sub[1]; 00036 }; 00037 00038 /** Returns an occurtree treating μ-variables like regular variables. If \a 00039 ** force_comm, then use commutative iteration for all compounds. */ 00040 cuex_occurtree_t cuex_folded_occurtree(cuex_t e, cu_bool_t force_comm); 00041 00042 /** Returns an occurtree where a free μ-variable also implies all variables 00043 ** which are free in the corresponding μ-bind. If \a force_comm, then use the 00044 ** commutative iteration for all compounds. */ 00045 cuex_occurtree_t cuex_unfolded_occurtree(cuex_t e, cu_bool_t force_comm); 00046 00047 /** The expression from which \a tree was created. */ 00048 CU_SINLINE cuex_t 00049 cuex_occurtree_expr(cuex_occurtree_t tree) 00050 { return tree->e; } 00051 00052 /** Returns occurtree for subexpression number \a i under \a tree. */ 00053 CU_SINLINE cuex_occurtree_t 00054 cuex_occurtree_at(cuex_occurtree_t tree, cu_rank_t i) 00055 { return tree->sub[i]; } 00056 00057 /** True iff \a tree has no free variables. */ 00058 CU_SINLINE cu_bool_t 00059 cuex_occurtree_is_closed(cuex_occurtree_t tree) 00060 { return cucon_ucset_is_empty(tree->free_vars); } 00061 00062 /** True iff \a tree has no free μ-variables. */ 00063 CU_SINLINE cu_bool_t 00064 cuex_occurtree_is_muclosed(cuex_occurtree_t tree) 00065 { return tree->mu_height < 0; } 00066 00067 /** Returns the set of free variables in \a tree. */ 00068 CU_SINLINE cucon_ucset_t 00069 cuex_occurtree_free_vars(cuex_occurtree_t tree) 00070 { return tree->free_vars; } 00071 00072 /** Remove unused μ-binding sites from \a tree and return the new root. This 00073 ** destructs \a tree in the process. */ 00074 cuex_occurtree_t cuex_occurtree_prune_mu(cuex_occurtree_t tree, 00075 cuex_opview_t view); 00076 00077 /** Debug printout of \a tree. */ 00078 void cuex_occurtree_dump(cuex_occurtree_t tree, FILE *out); 00079 00080 /** @} */ 00081 CU_END_DECLARATIONS 00082 00083 #endif