1fbe9daa4413e5973f90d45a604c4aaef55f3c4b
[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': "%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 model['fields'] = sorted(model['fields'].items())
157
158 app_title = app_model._meta.app_label.title().lower().capitalize()
159 if app_title not in graphs:
160 graphs[app_title] = {}
161 graphs[app_title].update({app_model.__name__: model})
162
163 if json:
164 return dumps(graphs)
165 else:
166 return graphs
167
168
169 def qbe_graph(admin_site=None, directed=False):
170 models = qbe_models(admin_site)
171 graph = {}
172 for k, v in models.items():
173 for l, w in v.items():
174 key = "%s.%s" % (k, l)
175 if key not in graph:
176 graph[key] = []
177 for relation in w['relations']:
178 source = relation['source']
179 target = relation['target']
180 if "through" in target:
181 through = target["through"]
182 model = "%s.%s" % (through['name'], through['model'])
183 value = (source, model, through['field'])
184 else:
185 model = "%s.%s" % (target['name'], target['model'])
186 value = (source, model, target['field'])
187 if value not in graph[key]:
188 graph[key].append(value)
189 if not directed:
190 if model not in graph:
191 graph[model] = []
192 target_field = target['field']
193 target_value = (target_field, key, source)
194 if target_value not in graph[model]:
195 graph[model].append(target_value)
196 if not graph[key]:
197 del graph[key]
198 return graph
199
200
201 def qbe_tree(graph, nodes, root=None):
202 """
203 Given a graph, nodes to explore and an optinal root, do a breadth-first
204 search in order to return the tree.
205 """
206 if root:
207 start = root
208 else:
209 index = random.randint(0, len(nodes) - 1)
210 start = nodes[index]
211 # A queue to BFS instead DFS
212 to_visit = deque()
213 cnodes = copy(nodes)
214 visited = set()
215 # Format is (parent, parent_edge, neighbor, neighbor_field)
216 to_visit.append((None, None, start, None))
217 tree = {}
218 while len(to_visit) != 0 and nodes:
219 parent, parent_edge, v, v_edge = to_visit.pop()
220 # Prune
221 if v in nodes:
222 nodes.remove(v)
223 node = graph[v]
224 if v not in visited and len(node) > 1:
225 visited.add(v)
226 # Preorder process
227 if all((parent, parent_edge, v, v_edge)):
228 if parent not in tree:
229 tree[parent] = []
230 if (parent_edge, v, v_edge) not in tree[parent]:
231 tree[parent].append((parent_edge, v, v_edge))
232 if v not in tree:
233 tree[v] = []
234 if (v_edge, parent, parent_edge) not in tree[v]:
235 tree[v].append((v_edge, parent, parent_edge))
236 # Iteration
237 for node_edge, neighbor, neighbor_edge in node:
238 value = (v, node_edge, neighbor, neighbor_edge)
239 to_visit.append(value)
240 remove_leafs(tree, cnodes)
241 return tree, (len(nodes) == 0)
242
243
244 def remove_leafs(tree, nodes):
245
246 def get_leafs(tree, nodes):
247 return [node for node, edges in tree.items()
248 if len(edges) < 2 and node not in nodes]
249
250 def delete_edge_leafs(tree, leaf):
251 for node, edges in tree.items():
252 for node_edge, neighbor, neighbor_edge in edges:
253 if leaf == neighbor:
254 edge = (node_edge, neighbor, neighbor_edge)
255 tree[node].remove(edge)
256 del tree[leaf]
257
258 leafs = get_leafs(tree, nodes)
259 iterations = 0
260 while leafs or iterations > len(tree) ^ 2:
261 for node in leafs:
262 if node in tree:
263 delete_edge_leafs(tree, node)
264 leafs = get_leafs(tree, nodes)
265 iterations += 0
266 return tree
267
268
269 def qbe_forest(graph, nodes):
270 forest = []
271 for node, edges in graph.items():
272 tree, are_all = qbe_tree(graph, copy(nodes), root=node)
273 if are_all and tree not in forest:
274 forest.append(tree)
275 return sorted(forest, cmp=lambda x, y: cmp(len(x), len(y)))
276
277
278 def find_all_paths(graph, start_node, end_node, path=None):
279 if not path:
280 path = []
281 path = path + [start_node]
282 if start_node == end_node:
283 return [path]
284 if start_node not in graph:
285 return []
286 paths = []
287 for source_edge, target_node, target_edge in graph[start_node]:
288 if target_node not in path:
289 newpaths = find_all_paths(graph, target_node, end_node, path)
290 for newpath in newpaths:
291 paths.append(newpath)
292 return paths
293
294
295 def find_minimal_paths(graph, start_node, end_node):
296
297 def find_all_paths(graph, start_node, end_node, start_edge, end_edge,
298 path=None, minimun=float("Inf")):
299 if not path:
300 path = []
301 path = path + [start_node]
302 if start_node == end_node:
303 return [path], minimun
304 if start_node not in graph:
305 return [], minimun
306 paths = []
307 if len(path) < minimun:
308 for source_edge, target_node, target_edge in graph[start_node]:
309 if target_node not in path:
310 newpaths, minimun = find_all_paths(graph, target_node,
311 end_node,
312 target_edge,
313 source_edge,
314 path, minimun)
315 for newpath in newpaths:
316 newpath_length = len(newpath)
317 if minimun > newpath_length:
318 minimun = newpath_length
319 if newpath not in paths:
320 paths.append(newpath)
321 return paths, minimun
322
323 paths, minimun = find_all_paths(graph, start_node, end_node,
324 start_edge=None, end_edge=None,
325 path=None, minimun=float("Inf"))
326 return paths
327
328
329 def _combine(items, val=None, paths=None, length=None):
330 if not paths:
331 paths = []
332 if not length:
333 length = len(items)
334 if not val:
335 val = []
336 if len(val) == length - 1 and len(items) == 1:
337 return [(val + [i]) for i in items[0]]
338 for i, item in enumerate(items[:-1]):
339 for value in item:
340 val.append(value)
341 path = _combine(items[i + 1:], val, paths, length)
342 val.pop()
343
344 def visited_path(x):
345 return x not in paths
346 path = filter(visited_path, path)
347 paths.extend(path)
348 return paths
349
350
351 def combine(items, k=None):
352 """
353 Create a matrix in wich each row is a tuple containing one of solutions or
354 solution k-esima.
355 """
356 length_items = len(items)
357 lengths = [len(i) for i in items]
358 length = reduce(lambda x, y: x * y, lengths)
359 repeats = [reduce(lambda x, y: x * y, lengths[i:])
360 for i in range(1, length_items)] + [1]
361 if k is not None:
362 k = k % length
363 # Python division by default is integer division (~ floor(a/b))
364 indices = [(k % (lengths[i] * repeats[i])) / repeats[i]
365 for i in range(length_items)]
366 return [items[i][indices[i]] for i in range(length_items)]
367 else:
368 matrix = []
369 for i, item in enumerate(items):
370 row = []
371 for subset in item:
372 row.extend([subset] * repeats[i])
373 times = length / len(row)
374 matrix.append(row * times)
375 # Transpose the matrix or return the columns instead rows
376 return zip(*matrix)
377
378
379 def graphs_join(graphs):
380 print "Combine % elements" % len(graphs)
381 return []
382
383
384 def autocomplete_graph(admin_site, current_models, directed=False):
385 graph = qbe_graph(admin_site, directed=directed)
386 valid_paths = []
387 for c, d in combinations(current_models, 2):
388 paths = find_minimal_paths(graph, c, d)
389 combined_sets = combine(paths)
390 for combined_set in combined_sets:
391 path = graphs_join(combined_set)
392 valid_paths.append(path)
393 # for path in paths:
394 # if all(map(lambda x: x in path, current_models)):
395 # if path not in valid_paths:
396 # valid_paths.append(path)
397 return sorted(valid_paths, cmp=lambda x, y: cmp(len(x), len(y)))
398
399
400 # Taken from django.contrib.sessions.backends.base
401 def pickle_encode(session_dict):
402 "Returns the given session dictionary pickled and encoded as a string."
403 pickled = pickle.dumps(session_dict, pickle.HIGHEST_PROTOCOL)
404 pickled_md5 = md5_constructor(pickled + settings.SECRET_KEY).hexdigest()
405 return base64.encodestring(pickled + pickled_md5)
406
407
408 # Adapted from django.contrib.sessions.backends.base
409 def pickle_decode(session_data):
410 # The '+' character is translated to ' ' in request
411 session_data = session_data.replace(" ", "+")
412 # The length of the encoded string should be a multiple of 4
413 while (((len(session_data) / 4.0) - (len(session_data) / 4)) != 0):
414 session_data += u"="
415 encoded_data = base64.decodestring(session_data)
416 pickled, tamper_check = encoded_data[:-32], encoded_data[-32:]
417 pickled_md5 = md5_constructor(pickled + settings.SECRET_KEY).hexdigest()
418 if pickled_md5 != tamper_check:
419 raise SuspiciousOperation("User tampered with session cookie.")
420 try:
421 return pickle.loads(pickled)
422 # Unpickling can cause a variety of exceptions. If something happens,
423 # just return an empty dictionary (an empty session).
424 except:
425 return {}