1 /* 2 * Copyright 2006-2008 The FLWOR Foundation. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 #pragma once 17 #ifndef ZORBA_COMPILER_PROLOG_GRAPH 18 #define ZORBA_COMPILER_PROLOG_GRAPH 19 20 #include <map> 21 #include <list> 22 #include <set> 23 #include <cassert> 24 25 #include "common/shared_types.h" 26 27 #include "compiler/expression/var_expr.h" 28 29 30 namespace zorba 31 { 32 33 34 class function; 35 class var_expr; 36 37 38 /******************************************************************************* 39 Class to represent a vertex in the dependency graph among var and udfs decls 40 in the prolog of a module. A vertex is represented as a pointer to either a 41 var_expr (if var decl) or a function obj (if udf decl). 42 ********************************************************************************/ 43 class PrologGraphVertex 44 { 45 public: 46 typedef enum { VAR, FUN } Kind; 47 48 typedef union 49 { 50 const var_expr* var; 51 const function* fun; 52 } Key; 53 54 public: 55 Key theKey; 56 Kind theKind; 57 58 public: PrologGraphVertex()59 PrologGraphVertex() : theKind(VAR) 60 { 61 theKey.var = NULL; 62 } 63 PrologGraphVertex(const var_expr * v)64 PrologGraphVertex(const var_expr* v) : theKind(VAR) 65 { 66 theKey.var = v; 67 } 68 PrologGraphVertex(const function * f)69 PrologGraphVertex(const function* f) : theKind(FUN) 70 { 71 theKey.fun = f; 72 } 73 isNull()74 bool isNull() const { return theKey.var == NULL; } 75 setNull()76 void setNull() { theKey.var = NULL; } 77 getKind()78 Kind getKind() const { return theKind; } 79 isVar()80 bool isVar() const { return theKind == VAR; } 81 isUDF()82 bool isUDF() const { return theKind == FUN; } 83 getFunction()84 const function* getFunction() const 85 { 86 assert(theKind == FUN); 87 return theKey.fun; 88 } 89 getVarExpr()90 const var_expr* getVarExpr() const 91 { 92 assert(theKind == VAR); 93 return theKey.var; 94 } 95 96 bool operator==(const PrologGraphVertex& other) const 97 { 98 return (theKey.var == other.theKey.var); 99 } 100 101 bool operator<(const PrologGraphVertex& other) const 102 { 103 return (theKey.var < other.theKey.var); 104 } 105 }; 106 107 108 /******************************************************************************* 109 110 ********************************************************************************/ 111 class PrologGraph 112 { 113 typedef std::set<PrologGraphVertex> VSet; 114 115 typedef std::map<PrologGraphVertex, VSet*> GraphImpl; 116 117 private: 118 static_context * theModuleSctx; 119 120 GraphImpl theGraph; 121 122 std::vector<const var_expr*> theVarDecls; 123 std::vector<const function*> theFuncDecls; 124 125 public: addEdge(GraphImpl & graph,const PrologGraphVertex & v1,const PrologGraphVertex & v2)126 static void addEdge( 127 GraphImpl& graph, 128 const PrologGraphVertex& v1, 129 const PrologGraphVertex& v2) 130 { 131 GraphImpl::iterator ite = graph.find(v1); 132 133 if (ite == graph.end()) 134 { 135 VSet* vset = new VSet; 136 vset->insert(v2); 137 138 graph[v1] = vset; 139 140 //std::cout << "Allocated new vset : " << vset << std::endl << std::endl; 141 } 142 else 143 { 144 (*ite).second->insert(v2); 145 } 146 } 147 148 public: PrologGraph(static_context * sctx)149 PrologGraph(static_context* sctx) : theModuleSctx(sctx) { } 150 ~PrologGraph()151 ~PrologGraph() 152 { 153 GraphImpl::iterator ite = theGraph.begin(); 154 GraphImpl::iterator end = theGraph.end(); 155 for (; ite != end; ++ite) 156 { 157 //std::cout << "De-allocated vset : " << (*ite).second << std::endl << std::endl; 158 159 delete (*ite).second; 160 } 161 } 162 addVarVertex(const var_expr * v)163 void addVarVertex(const var_expr* v) 164 { 165 theVarDecls.push_back(v); 166 } 167 addFuncVertex(const function * v)168 void addFuncVertex(const function* v) 169 { 170 theFuncDecls.push_back(v); 171 } 172 173 void addEdge(const PrologGraphVertex& v1, const PrologGraphVertex& v2); 174 175 void reorder_globals(std::list<GlobalBinding>& prologVarBindings); 176 177 private: 178 void reportCycle(const QueryLoc& loc, const PrologGraphVertex* v); 179 }; 180 181 182 } 183 #endif 184 185 /* 186 * Local variables: 187 * mode: c++ 188 * End: 189 */ 190 /* vim:set et sw=2 ts=2: */ 191