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