main.py 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418
  1. import sys
  2. from collections import defaultdict
  3. import os
  4. import gzip
  5. import time
  6. import marshal
  7. # Work around Python 2 where a 'big integer' automatically becomes a long
  8. if sys.version > '3': # pragma: no cover
  9. integer_types = (int,)
  10. primitive_types = (int, float, str, bool)
  11. else: # pragma: no cover
  12. integer_types = (int, long)
  13. primitive_types = (int, long, float, str, bool, unicode)
  14. complex_primitives = frozenset(["if", "while", "assign", "call", "break", "continue", "return","resolve","access", "constant", "input", "output", "declare", "global", "none"])
  15. def instance_to_string(value):
  16. return value["value"]
  17. def string_to_instance(value):
  18. return {'value': value}
  19. class ModelverseState(object):
  20. def __init__(self, bootfile = None):
  21. self.free_id = 0
  22. self.edges = {}
  23. self.outgoing = {}
  24. self.incoming = {}
  25. self.values = {}
  26. self.nodes = set()
  27. self.GC = True
  28. self.to_delete = set()
  29. self.cache = {}
  30. self.cache_node = {}
  31. if bootfile is not None:
  32. self.root = self.parse(bootfile)
  33. else:
  34. self.root = self.create_node()
  35. def dump_modelverse(self):
  36. with open("/tmp/modelverse.out", "w") as f:
  37. f.write("digraph main {\n")
  38. for n in self.nodes:
  39. if n in self.values:
  40. f.write("a_%s [label=\"a_%s (%s)\"];\n" % (n, n, self.values[n]))
  41. else:
  42. f.write("a_%s [label=\"a_%s\"];\n" % (n, n))
  43. for i, e in list(self.edges.items()):
  44. f.write("%s -> %s [label=\"%s\"];\n" % (e[0], e[1], i))
  45. f.write("}")
  46. return self.root
  47. def parse(self, filename):
  48. picklefile = filename + ".pickle"
  49. try:
  50. if os.path.getmtime(picklefile) > os.path.getmtime(filename):
  51. # Pickle is more recent than bootstrap file, so we can use it
  52. self.root, self.free_id, self.nodes, self.edges, self.values, self.cache, self.cache_node = marshal.load(open(picklefile, 'rb'))
  53. for name in self.edges:
  54. source, destination = self.edges[name]
  55. self.outgoing.setdefault(source, set()).add(name)
  56. self.incoming.setdefault(destination, set()).add(name)
  57. return self.root
  58. else:
  59. raise Exception("Invalid pickle")
  60. except Exception as e:
  61. # We have to parse the file and create the pickle
  62. symbols = {}
  63. def resolve(symb):
  64. try:
  65. return int(symb)
  66. except:
  67. if symb[0] == "?":
  68. derefs = symb[1:].split("/")
  69. v = self.read_dict(symbols["root"], "__hierarchy")
  70. for deref in derefs:
  71. v = self.read_dict(v, deref)
  72. return v
  73. else:
  74. return symbols[symb]
  75. with gzip.open(filename, 'rb') as f:
  76. for line in f:
  77. #handle str to bytes
  78. if sys.version_info[0] > 2:
  79. line = line.decode()
  80. element_type, constructor = line.split(None, 1)
  81. name, values = constructor.split("(", 1)
  82. values, _ = values.rsplit(")", 1)
  83. if element_type == "Node":
  84. name = name.split()[0]
  85. if values == "":
  86. symbols[name] = self.create_node()
  87. else:
  88. value = values
  89. if value in complex_primitives:
  90. value = string_to_instance(value)
  91. else:
  92. value = eval(value)
  93. symbols[name] = self.create_nodevalue(value)
  94. elif element_type == "Edge":
  95. name = name.split()[0]
  96. values = [v.split()[0] for v in values.split(",")]
  97. symbols[name] = self.create_edge(resolve(values[0]), resolve(values[1]))
  98. elif element_type == "Dict":
  99. values = [v.split()[0] for v in values.split(",")]
  100. if values[1] in complex_primitives:
  101. values[1] = string_to_instance(values[1])
  102. else:
  103. values[1] = eval(values[1])
  104. self.create_dict(resolve(values[0]), values[1], resolve(values[2]))
  105. else:
  106. raise Exception("Unknown element type: %s" % element_type)
  107. # Creation successful, now also create a pickle
  108. with open(picklefile, 'wb') as f:
  109. marshal.dump((symbols["root"], self.free_id, self.nodes, self.edges, self.values, self.cache, self.cache_node), f)
  110. return symbols["root"]
  111. def read_root(self):
  112. return self.root
  113. def create_node(self):
  114. self.nodes.add(self.free_id)
  115. self.free_id += 1
  116. return self.free_id - 1
  117. def create_edge(self, source, target):
  118. if source not in self.edges and source not in self.nodes:
  119. return None
  120. elif target not in self.edges and target not in self.nodes:
  121. return None
  122. else:
  123. self.outgoing.setdefault(source, set()).add(self.free_id)
  124. self.incoming.setdefault(target, set()).add(self.free_id)
  125. self.edges[self.free_id] = (source, target)
  126. self.free_id += 1
  127. if source in self.edges:
  128. # We are creating something dict_readable
  129. # Fill in the cache already!
  130. dict_source, dict_target = self.edges[source]
  131. if target in self.values:
  132. self.cache.setdefault(dict_source, {})[self.values[target]] = source
  133. self.cache_node.setdefault(dict_source, {})[target] = source
  134. return self.free_id - 1
  135. def is_valid_datavalue(self, value):
  136. if isinstance(value, dict):
  137. if "value" in value and value["value"] in complex_primitives:
  138. return True
  139. else:
  140. return False
  141. elif not isinstance(value, primitive_types):
  142. return False
  143. elif isinstance(value, integer_types) and not (-2**63 <= value <= 2**63 - 1):
  144. return False
  145. return True
  146. def create_nodevalue(self, value):
  147. if not self.is_valid_datavalue(value):
  148. return None
  149. self.values[self.free_id] = value
  150. self.nodes.add(self.free_id)
  151. self.free_id += 1
  152. return self.free_id - 1
  153. def create_dict(self, source, data, destination):
  154. if isinstance(destination, dict):
  155. print("ERROR IN CD: " + str(locals()))
  156. if source not in self.nodes and source not in self.edges:
  157. return None
  158. elif destination not in self.nodes and destination not in self.edges:
  159. return None
  160. elif not self.is_valid_datavalue(data):
  161. return None
  162. else:
  163. n = self.create_nodevalue(data)
  164. e = self.create_edge(source, destination)
  165. self.create_edge(e, n)
  166. self.cache.setdefault(source, {})[data] = e
  167. self.cache_node.setdefault(source, {})[n] = e
  168. def read_value(self, node):
  169. if node in self.values:
  170. return self.values[node]
  171. else:
  172. return None
  173. def read_outgoing(self, elem):
  174. if elem in self.edges or elem in self.nodes:
  175. if elem in self.outgoing:
  176. return list(self.outgoing[elem])
  177. else:
  178. return []
  179. return None
  180. def read_incoming(self, elem):
  181. if elem in self.edges or elem in self.nodes:
  182. if elem in self.incoming:
  183. return list(self.incoming[elem])
  184. else:
  185. return []
  186. else:
  187. return None
  188. def read_edge(self, edge):
  189. if edge in self.edges:
  190. return [self.edges[edge][0], self.edges[edge][1]]
  191. else:
  192. return [None, None]
  193. def read_dict(self, node, value):
  194. #print("RD -- " + str(value))
  195. try:
  196. first = self.cache[node][value]
  197. # Got hit, so validate
  198. if (self.edges[first][0] == node) and \
  199. (value in [self.values[self.edges[i][1]] for i in self.outgoing[first] if self.edges[i][1] in self.values]):
  200. return self.edges[first][1]
  201. # Hit but invalid now
  202. del self.cache[node][value]
  203. except KeyError:
  204. # Didn't exist
  205. pass
  206. except:
  207. raise
  208. return None
  209. def read_dict_keys(self, node):
  210. if node not in self.nodes and node not in self.edges:
  211. return None
  212. result = []
  213. #NOTE cannot just use the cache here, as some keys in the cache might not actually exist; we would have to check all of them anyway
  214. if node in self.outgoing:
  215. for e1 in self.outgoing[node]:
  216. if e1 in self.outgoing:
  217. for e2 in self.outgoing[e1]:
  218. result.append(self.edges[e2][1])
  219. return result
  220. def read_dict_edge(self, node, value):
  221. try:
  222. first = self.cache[node][value]
  223. # Got hit, so validate
  224. if (self.edges[first][0] == node) and \
  225. (value in [self.values[self.edges[i][1]] for i in self.outgoing[first] if self.edges[i][1] in self.values]):
  226. return first
  227. # Hit but invalid now
  228. del self.cache[node][value]
  229. except KeyError:
  230. # Didn't exist
  231. pass
  232. return None
  233. def read_dict_node(self, node, value_node):
  234. e = self.read_dict_node_edge(node, value_node)
  235. if e is None:
  236. return None
  237. else:
  238. self.cache_node.setdefault(node, {})[value_node] = e
  239. return self.edges[e][1]
  240. def read_dict_node_edge(self, node, value_node):
  241. try:
  242. first = self.cache_node[node][value_node]
  243. # Got hit, so validate
  244. if (self.edges[first][0] == node) and \
  245. (value_node in [self.edges[i][1] for i in self.outgoing[first]]):
  246. return first
  247. # Hit but invalid now
  248. del self.cache_node[node][value_node]
  249. except KeyError:
  250. # Didn't exist
  251. pass
  252. return None
  253. def read_reverse_dict(self, node, value):
  254. if node not in self.nodes and node not in self.edges:
  255. return None
  256. elif not self.is_valid_datavalue(value):
  257. return None
  258. # Get all outgoing links
  259. matches = []
  260. if node in self.incoming:
  261. for e1 in self.incoming[node]:
  262. # For each link, we read the links that might link to a data value
  263. if e1 in self.outgoing:
  264. for e2 in self.outgoing[e1]:
  265. # Now read out the target of the link
  266. target = self.edges[e2][1]
  267. # And access its value
  268. if target in self.values and self.values[target] == value:
  269. # Found a match
  270. matches.append(e1)
  271. return [self.edges[e][0] for e in matches]
  272. def delete_node(self, node):
  273. if node == self.root:
  274. return None
  275. elif node not in self.nodes:
  276. return None
  277. self.nodes.remove(node)
  278. if node in self.values:
  279. del self.values[node]
  280. s = set()
  281. if node in self.outgoing:
  282. for e in self.outgoing[node]:
  283. s.add(e)
  284. del self.outgoing[node]
  285. if node in self.incoming:
  286. for e in self.incoming[node]:
  287. s.add(e)
  288. del self.incoming[node]
  289. for e in s:
  290. self.delete_edge(e)
  291. if node in self.outgoing:
  292. del self.outgoing[node]
  293. if node in self.incoming:
  294. del self.incoming[node]
  295. return None
  296. def delete_edge(self, edge):
  297. if edge not in self.edges:
  298. return None
  299. s, t = self.edges[edge]
  300. if t in self.incoming:
  301. self.incoming[t].remove(edge)
  302. if s in self.outgoing:
  303. self.outgoing[s].remove(edge)
  304. del self.edges[edge]
  305. s = set()
  306. if edge in self.outgoing:
  307. for e in self.outgoing[edge]:
  308. s.add(e)
  309. if edge in self.incoming:
  310. for e in self.incoming[edge]:
  311. s.add(e)
  312. for e in s:
  313. self.delete_edge(e)
  314. if edge in self.outgoing:
  315. del self.outgoing[edge]
  316. if edge in self.incoming:
  317. del self.incoming[edge]
  318. if (self.GC) and (t in self.incoming and not self.incoming[t]) and (t not in self.edges):
  319. # Remove this node as well
  320. # Edges aren't deleted like this, as they might have a reachable target and source!
  321. # If they haven't, they will be removed because the source was removed.
  322. self.to_delete.add(t)
  323. def purge(self):
  324. initial_nodes = len(self.nodes)
  325. initial_edges = len(self.edges)
  326. while self.to_delete:
  327. t = self.to_delete.pop()
  328. if t in self.incoming and not self.incoming[t]:
  329. self.delete_node(t)
  330. values = set(self.edges)
  331. values.update(self.nodes)
  332. visit_list = [self.root]
  333. while visit_list:
  334. elem = visit_list.pop()
  335. if elem in values:
  336. # Remove it from the leftover values
  337. values.remove(elem)
  338. if elem in self.edges:
  339. visit_list.extend(self.edges[elem])
  340. if elem in self.outgoing:
  341. visit_list.extend(self.outgoing[elem])
  342. if elem in self.incoming:
  343. visit_list.extend(self.incoming[elem])
  344. dset = set()
  345. for key in self.cache:
  346. if key not in self.nodes and key not in self.edges:
  347. dset.add(key)
  348. for key in dset:
  349. del self.cache[key]
  350. dset = set()
  351. for key in self.cache_node:
  352. if key not in self.nodes and key not in self.edges:
  353. dset.add(key)
  354. for key in dset:
  355. del self.cache_node[key]
  356. # All remaining elements are to be purged
  357. if len(values) > 0:
  358. while values:
  359. v = values.pop()
  360. if v in self.nodes:
  361. self.delete_node(v)