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