Installation de la version modifié de QBE dans src/
[auf_rh_dae.git] / src / qbe / django_qbe / utils.py
1 # -*- coding: utf-8 -*-
2 import base64
3 import pickle
4 import random
5
6 from collections import deque
7 from copy import copy
8 try:
9 from itertools import combinations
10 except ImportError:
11
12 def combinations(items, n):
13 if n == 0:
14 yield []
15 else:
16 for i in xrange(len(items)):
17 for cc in combinations(items[i + 1:], n - 1):
18 yield [items[i]] + cc
19
20 from django.db.models import get_models
21 from django.db.models.fields.related import (ForeignKey, OneToOneField,
22 ManyToManyField)
23 from django.core.exceptions import SuspiciousOperation
24 from django.conf import settings
25 from django.utils.hashcompat import md5_constructor
26 from django.utils.importlib import import_module
27 from django.utils.simplejson import dumps
28
29 try:
30 from django.db.models.fields.generic import GenericRelation
31 except ImportError:
32 from django.contrib.contenttypes.generic import GenericRelation
33
34 try:
35 qbe_formats = getattr(settings, "QBE_FORMATS_EXPORT", "qbe_formats")
36 formats = import_module(qbe_formats).formats
37 except ImportError:
38 from django_qbe.exports import formats
39 formats # Makes pyflakes happy
40
41
42 def qbe_models(admin_site=None, only_admin_models=False, json=False):
43 app_models = get_models(include_auto_created=True, include_deferred=True)
44 app_models_with_no_includes = get_models(include_auto_created=False,
45 include_deferred=False)
46 if admin_site:
47 admin_models = [m for m, a in admin_site._registry.items()]
48 else:
49 admin_models = []
50 if only_admin_models:
51 app_models = admin_models
52 graphs = {}
53
54 def get_field_attributes(field):
55 return {field.name: {
56 'name': field.name,
57 'type': type(field).__name__,
58 'blank': field.blank,
59 'label': u"%s" % field.verbose_name.lower().capitalize(),
60 'primary': field.primary_key,
61 }}
62
63 def get_through_fields(field):
64 # Deprecated
65 through_fields = []
66 for through_field in field.rel.through._meta.fields:
67 label = through_field.verbose_name.lower().capitalize()
68 through_fields_dic = {
69 'name': through_field.name,
70 'type': type(through_field).__name__,
71 'blank': through_field.blank,
72 'label': u"%s" % label,
73 }
74 if hasattr(through_field.rel, "to"):
75 through_rel = through_field.rel
76 through_mod = through_rel.to.__module__.split(".")[-2]
77 through_name = through_mod.lower().capitalize()
78 through_target = {
79 'name': through_name,
80 'model': through_rel.to.__name__,
81 'field': through_rel.get_related_field().name,
82 }
83 through_fields_dic.update({
84 "target": through_target,
85 })
86 through_fields.append(through_fields_dic)
87 return through_fields
88
89 def get_target(field):
90 name = field.rel.to.__module__.split(".")[-2].lower().capitalize()
91 target = {
92 'name': name,
93 'model': field.rel.to.__name__,
94 'field': field.rel.to._meta.pk.name,
95 }
96 if hasattr(field.rel, 'through') and field.rel.through is not None:
97 name = field.rel.through.__module__.split(".")[-2]
98 target.update({
99 'through': {
100 'name': name.lower().capitalize(),
101 'model': field.rel.through.__name__,
102 'field': field.rel.through._meta.pk.name,
103 }
104 })
105 return target
106
107 def get_target_relation(field, extras=""):
108 target = get_target(field)
109 relation = {
110 'target': target,
111 'type': type(field).__name__,
112 'source': field.name,
113 'arrows': extras,
114 }
115 return target, relation
116
117 def add_relation(model, field, extras=""):
118 target, relation = get_target_relation(field, extras=extras)
119 if relation not in model['relations']:
120 model['relations'].append(relation)
121 model['fields'][field.name].update({'target': target})
122 return model
123
124 for app_model in app_models:
125 model = {
126 'name': app_model.__name__,
127 'fields': {},
128 'relations': [],
129 'primary': app_model._meta.pk.name,
130 'collapse': ((app_model not in admin_models) or
131 (app_model not in app_models_with_no_includes)),
132 'is_auto': app_model not in app_models_with_no_includes,
133 }
134
135 for field in app_model._meta.fields:
136 field_attributes = get_field_attributes(field)
137 model['fields'].update(field_attributes)
138 if isinstance(field, ForeignKey):
139 model = add_relation(model, field)
140 elif isinstance(field, OneToOneField):
141 extras = "" # "[arrowhead=none arrowtail=none]"
142 model = add_relation(model, field, extras=extras)
143
144 if app_model._meta.many_to_many:
145 for field in app_model._meta.many_to_many:
146 field_attributes = get_field_attributes(field)
147 model['fields'].update(field_attributes)
148 if isinstance(field, ManyToManyField):
149 extras = "" # "[arrowhead=normal arrowtail=normal]"
150 model = add_relation(model, field, extras=extras)
151 elif isinstance(field, GenericRelation):
152 extras = "" # '[style="dotted"]
153 # [arrowhead=normal arrowtail=normal]'
154 model = add_relation(model, field, extras=extras)
155
156 app_title = app_model._meta.app_label.title().lower().capitalize()
157 if app_title not in graphs:
158 graphs[app_title] = {}
159 graphs[app_title].update({app_model.__name__: model})
160
161 if json:
162 return dumps(graphs)
163 else:
164 return graphs
165
166
167 def qbe_graph(admin_site=None, directed=False):
168 models = qbe_models(admin_site)
169 graph = {}
170 for k, v in models.items():
171 for l, w in v.items():
172 key = "%s.%s" % (k, l)
173 if key not in graph:
174 graph[key] = []
175 for relation in w['relations']:
176 source = relation['source']
177 target = relation['target']
178 if "through" in target:
179 through = target["through"]
180 model = "%s.%s" % (through['name'], through['model'])
181 value = (source, model, through['field'])
182 else:
183 model = "%s.%s" % (target['name'], target['model'])
184 value = (source, model, target['field'])
185 if value not in graph[key]:
186 graph[key].append(value)
187 if not directed:
188 if model not in graph:
189 graph[model] = []
190 target_field = target['field']
191 target_value = (target_field, key, source)
192 if target_value not in graph[model]:
193 graph[model].append(target_value)
194 if not graph[key]:
195 del graph[key]
196 return graph
197
198
199 def qbe_tree(graph, nodes, root=None):
200 """
201 Given a graph, nodes to explore and an optinal root, do a breadth-first
202 search in order to return the tree.
203 """
204 if root:
205 start = root
206 else:
207 index = random.randint(0, len(nodes) - 1)
208 start = nodes[index]
209 # A queue to BFS instead DFS
210 to_visit = deque()
211 cnodes = copy(nodes)
212 visited = set()
213 # Format is (parent, parent_edge, neighbor, neighbor_field)
214 to_visit.append((None, None, start, None))
215 tree = {}
216 while len(to_visit) != 0 and nodes:
217 parent, parent_edge, v, v_edge = to_visit.pop()
218 # Prune
219 if v in nodes:
220 nodes.remove(v)
221 node = graph[v]
222 if v not in visited and len(node) > 1:
223 visited.add(v)
224 # Preorder process
225 if all((parent, parent_edge, v, v_edge)):
226 if parent not in tree:
227 tree[parent] = []
228 if (parent_edge, v, v_edge) not in tree[parent]:
229 tree[parent].append((parent_edge, v, v_edge))
230 if v not in tree:
231 tree[v] = []
232 if (v_edge, parent, parent_edge) not in tree[v]:
233 tree[v].append((v_edge, parent, parent_edge))
234 # Iteration
235 for node_edge, neighbor, neighbor_edge in node:
236 value = (v, node_edge, neighbor, neighbor_edge)
237 to_visit.append(value)
238 remove_leafs(tree, cnodes)
239 return tree, (len(nodes) == 0)
240
241
242 def remove_leafs(tree, nodes):
243
244 def get_leafs(tree, nodes):
245 return [node for node, edges in tree.items()
246 if len(edges) < 2 and node not in nodes]
247
248 def delete_edge_leafs(tree, leaf):
249 for node, edges in tree.items():
250 for node_edge, neighbor, neighbor_edge in edges:
251 if leaf == neighbor:
252 edge = (node_edge, neighbor, neighbor_edge)
253 tree[node].remove(edge)
254 del tree[leaf]
255
256 leafs = get_leafs(tree, nodes)
257 iterations = 0
258 while leafs or iterations > len(tree) ^ 2:
259 for node in leafs:
260 if node in tree:
261 delete_edge_leafs(tree, node)
262 leafs = get_leafs(tree, nodes)
263 iterations += 0
264 return tree
265
266
267 def qbe_forest(graph, nodes):
268 forest = []
269 for node, edges in graph.items():
270 tree, are_all = qbe_tree(graph, copy(nodes), root=node)
271 if are_all and tree not in forest:
272 forest.append(tree)
273 return sorted(forest, cmp=lambda x, y: cmp(len(x), len(y)))
274
275
276 def find_all_paths(graph, start_node, end_node, path=None):
277 if not path:
278 path = []
279 path = path + [start_node]
280 if start_node == end_node:
281 return [path]
282 if start_node not in graph:
283 return []
284 paths = []
285 for source_edge, target_node, target_edge in graph[start_node]:
286 if target_node not in path:
287 newpaths = find_all_paths(graph, target_node, end_node, path)
288 for newpath in newpaths:
289 paths.append(newpath)
290 return paths
291
292
293 def find_minimal_paths(graph, start_node, end_node):
294
295 def find_all_paths(graph, start_node, end_node, start_edge, end_edge,
296 path=None, minimun=float("Inf")):
297 if not path:
298 path = []
299 path = path + [start_node]
300 if start_node == end_node:
301 return [path], minimun
302 if start_node not in graph:
303 return [], minimun
304 paths = []
305 if len(path) < minimun:
306 for source_edge, target_node, target_edge in graph[start_node]:
307 if target_node not in path:
308 newpaths, minimun = find_all_paths(graph, target_node,
309 end_node,
310 target_edge,
311 source_edge,
312 path, minimun)
313 for newpath in newpaths:
314 newpath_length = len(newpath)
315 if minimun > newpath_length:
316 minimun = newpath_length
317 if newpath not in paths:
318 paths.append(newpath)
319 return paths, minimun
320
321 paths, minimun = find_all_paths(graph, start_node, end_node,
322 start_edge=None, end_edge=None,
323 path=None, minimun=float("Inf"))
324 return paths
325
326
327 def _combine(items, val=None, paths=None, length=None):
328 if not paths:
329 paths = []
330 if not length:
331 length = len(items)
332 if not val:
333 val = []
334 if len(val) == length - 1 and len(items) == 1:
335 return [(val + [i]) for i in items[0]]
336 for i, item in enumerate(items[:-1]):
337 for value in item:
338 val.append(value)
339 path = _combine(items[i + 1:], val, paths, length)
340 val.pop()
341
342 def visited_path(x):
343 return x not in paths
344 path = filter(visited_path, path)
345 paths.extend(path)
346 return paths
347
348
349 def combine(items, k=None):
350 """
351 Create a matrix in wich each row is a tuple containing one of solutions or
352 solution k-esima.
353 """
354 length_items = len(items)
355 lengths = [len(i) for i in items]
356 length = reduce(lambda x, y: x * y, lengths)
357 repeats = [reduce(lambda x, y: x * y, lengths[i:])
358 for i in range(1, length_items)] + [1]
359 if k is not None:
360 k = k % length
361 # Python division by default is integer division (~ floor(a/b))
362 indices = [(k % (lengths[i] * repeats[i])) / repeats[i]
363 for i in range(length_items)]
364 return [items[i][indices[i]] for i in range(length_items)]
365 else:
366 matrix = []
367 for i, item in enumerate(items):
368 row = []
369 for subset in item:
370 row.extend([subset] * repeats[i])
371 times = length / len(row)
372 matrix.append(row * times)
373 # Transpose the matrix or return the columns instead rows
374 return zip(*matrix)
375
376
377 def graphs_join(graphs):
378 print "Combine % elements" % len(graphs)
379 return []
380
381
382 def autocomplete_graph(admin_site, current_models, directed=False):
383 graph = qbe_graph(admin_site, directed=directed)
384 valid_paths = []
385 for c, d in combinations(current_models, 2):
386 paths = find_minimal_paths(graph, c, d)
387 combined_sets = combine(paths)
388 for combined_set in combined_sets:
389 path = graphs_join(combined_set)
390 valid_paths.append(path)
391 # for path in paths:
392 # if all(map(lambda x: x in path, current_models)):
393 # if path not in valid_paths:
394 # valid_paths.append(path)
395 return sorted(valid_paths, cmp=lambda x, y: cmp(len(x), len(y)))
396
397
398 # Taken from django.contrib.sessions.backends.base
399 def pickle_encode(session_dict):
400 "Returns the given session dictionary pickled and encoded as a string."
401 pickled = pickle.dumps(session_dict, pickle.HIGHEST_PROTOCOL)
402 pickled_md5 = md5_constructor(pickled + settings.SECRET_KEY).hexdigest()
403 return base64.encodestring(pickled + pickled_md5)
404
405
406 # Adapted from django.contrib.sessions.backends.base
407 def pickle_decode(session_data):
408 # The '+' character is translated to ' ' in request
409 session_data = session_data.replace(" ", "+")
410 # The length of the encoded string should be a multiple of 4
411 while (((len(session_data) / 4.0) - (len(session_data) / 4)) != 0):
412 session_data += u"="
413 encoded_data = base64.decodestring(session_data)
414 pickled, tamper_check = encoded_data[:-32], encoded_data[-32:]
415 pickled_md5 = md5_constructor(pickled + settings.SECRET_KEY).hexdigest()
416 if pickled_md5 != tamper_check:
417 raise SuspiciousOperation("User tampered with session cookie.")
418 try:
419 return pickle.loads(pickled)
420 # Unpickling can cause a variety of exceptions. If something happens,
421 # just return an empty dictionary (an empty session).
422 except:
423 return {}