1# -*- coding: utf-8 -*-2# Copyright 2011 Takeshi KOMIYA3#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 at7#8# http://www.apache.org/licenses/LICENSE-2.09#10# Unless required by applicable law or agreed to in writing, software11# 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 and14# limitations under the License.1516from blockdiag import parser17from blockdiag.elements import Diagram, DiagramEdge, DiagramNode, NodeGroup18from blockdiag.plugins import fire_node_event19from blockdiag.utils import XY, unquote20from blockdiag.utils.compat import cmp_to_key212223class DiagramTreeBuilder:24 def build(self, tree, config):25 self.config = config26 self.diagram = Diagram()27 self.instantiate(self.diagram, tree)28 for subgroup in self.diagram.traverse_groups():29 if len(subgroup.nodes) == 0:30 subgroup.group.nodes.remove(subgroup)3132 self.bind_edges(self.diagram)33 self.fire_node_event('build_finished')34 return self.diagram3536 def fire_node_event(self, event_type):37 for node in self.diagram.nodes:38 if node.drawable:39 fire_node_event(node, event_type)4041 def is_related_group(self, group1, group2):42 if group1.is_parent(group2) or group2.is_parent(group1):43 return True44 else:45 return False4647 def belong_to(self, node, group):48 if node.group and node.group.level > group.level:49 override = False50 else:51 override = True5253 if node.group and node.group != group and override:54 if not self.is_related_group(node.group, group):55 msg = "could not belong to two groups: %s" % node.id56 raise RuntimeError(msg)5758 old_group = node.group5960 parent = group.parent(old_group.level + 1)61 if parent:62 if parent in old_group.nodes:63 old_group.nodes.remove(parent)6465 index = old_group.nodes.index(node)66 old_group.nodes.insert(index + 1, parent)6768 old_group.nodes.remove(node)69 node.group = None7071 if node.group is None:72 node.group = group7374 if node not in group.nodes:75 group.nodes.append(node)7677 def instantiate(self, group, tree):78 for stmt in tree.stmts:79 # Translate Node having group attribute to Group80 if isinstance(stmt, parser.Node):81 group_attr = [a for a in stmt.attrs if a.name == 'group']82 if group_attr:83 group_id = group_attr[-1]84 stmt.attrs.remove(group_id)8586 if group_id.value != group.id:87 stmt = parser.Group(group_id.value, [stmt])8889 # Instantiate statements90 if isinstance(stmt, parser.Node):91 node = DiagramNode.get(stmt.id)92 node.set_attributes(stmt.attrs)93 self.belong_to(node, group)9495 elif isinstance(stmt, parser.Edge):96 from_nodes = [DiagramNode.get(n) for n in stmt.from_nodes]97 to_nodes = [DiagramNode.get(n) for n in stmt.to_nodes]9899 for node in from_nodes + to_nodes:100 self.belong_to(node, group)101102 for node1 in from_nodes:103 for node2 in to_nodes:104 edge = DiagramEdge.get(node1, node2)105 edge.set_dir(stmt.edge_type)106 edge.set_attributes(stmt.attrs)107108 elif isinstance(stmt, parser.Group):109 subgroup = NodeGroup.get(stmt.id)110 subgroup.level = group.level + 1111 self.belong_to(subgroup, group)112 self.instantiate(subgroup, stmt)113114 elif isinstance(stmt, parser.Attr):115 group.set_attribute(stmt)116117 elif isinstance(stmt, parser.Extension):118 if stmt.type == 'class':119 name = unquote(stmt.name)120 Diagram.classes[name] = stmt121 elif stmt.type == 'plugin':122 self.diagram.set_plugin(stmt.name, stmt.attrs,123 config=self.config)124125 elif isinstance(stmt, parser.Statements):126 self.instantiate(group, stmt)127128 group.update_order()129 return group130131 def bind_edges(self, group):132 for node in group.nodes:133 if isinstance(node, DiagramNode):134 group.edges += DiagramEdge.find(node)135 else:136 self.bind_edges(node)137138139class DiagramLayoutManager:140 def __init__(self, diagram):141 self.diagram = diagram142143 self.circulars = []144 self.heightRefs = []145 self.coordinates = []146147 def run(self):148 if isinstance(self.diagram, Diagram):149 for group in self.diagram.traverse_groups():150 self.__class__(group).run()151152 self.edges = DiagramEdge.find_by_level(self.diagram.level)153 self.do_layout()154 self.diagram.fixiate()155156 if self.diagram.orientation == 'portrait':157 self.rotate_diagram()158159 def rotate_diagram(self):160 for node in self.diagram.traverse_nodes():161 node.xy = XY(node.xy.y, node.xy.x)162 node.colwidth, node.colheight = (node.colheight, node.colwidth)163164 if isinstance(node, NodeGroup):165 if node.orientation == 'portrait':166 node.orientation = 'landscape'167 else:168 node.orientation = 'portrait'169170 xy = (self.diagram.colheight, self.diagram.colwidth)171 self.diagram.colwidth, self.diagram.colheight = xy172173 def do_layout(self):174 self.detect_circulars()175176 self.set_node_xpos()177 self.adjust_node_order()178179 height = 0180 for node in self.diagram.nodes:181 if node.xy.x == 0:182 self.set_node_ypos(node, height)183 height = max(xy.y for xy in self.coordinates) + 1184185 def get_related_nodes(self, node, parent=False, child=False):186 uniq = {}187 for edge in self.edges:188 if edge.folded:189 continue190191 if parent and edge.node2 == node:192 uniq[edge.node1] = 1193 elif child and edge.node1 == node:194 uniq[edge.node2] = 1195196 related = []197 for uniq_node in uniq.keys():198 if uniq_node == node:199 pass200 elif uniq_node.group != node.group:201 pass202 else:203 related.append(uniq_node)204205 related.sort(key=lambda x: x.order)206 return related207208 def get_parent_nodes(self, node):209 return self.get_related_nodes(node, parent=True)210211 def get_child_nodes(self, node):212 return self.get_related_nodes(node, child=True)213214 def detect_circulars(self):215 for node in self.diagram.nodes:216 if not [x for x in self.circulars if node in x]:217 self.detect_circulars_sub(node, [node])218219 # remove part of other circular220 for c1 in self.circulars[:]:221 for c2 in self.circulars:222 intersect = set(c1) & set(c2)223224 if c1 != c2 and set(c1) == intersect:225 if c1 in self.circulars:226 self.circulars.remove(c1)227 break228229 if c1 != c2 and intersect:230 if c1 in self.circulars:231 self.circulars.remove(c1)232 self.circulars.remove(c2)233 self.circulars.append(c1 + c2)234 break235236 def detect_circulars_sub(self, node, parents):237 for child in self.get_child_nodes(node):238 if child in parents:239 i = parents.index(child)240 if parents[i:] not in self.circulars:241 self.circulars.append(parents[i:])242 else:243 self.detect_circulars_sub(child, parents + [child])244245 def is_circular_ref(self, node1, node2):246 for circular in self.circulars:247 if node1 in circular and node2 in circular:248 parents = []249 for node in circular:250 for parent in self.get_parent_nodes(node):251 if parent not in circular:252 parents.append(parent)253254 for parent in sorted(parents, key=lambda x: x.order):255 children = self.get_child_nodes(parent)256 if node1 in children and node2 in children:257 if circular.index(node1) > circular.index(node2):258 return True259 elif node2 in children:260 return True261 elif node1 in children:262 return False263 else:264 if circular.index(node1) > circular.index(node2):265 return True266267 return False268269 def set_node_xpos(self, depth=0):270 for node in self.diagram.nodes:271 if node.xy.x != depth:272 continue273274 for child in self.get_child_nodes(node):275 if self.is_circular_ref(node, child):276 pass277 elif node == child:278 pass279 elif child.xy.x > node.xy.x + node.colwidth:280 pass281 else:282 child.xy = XY(node.xy.x + node.colwidth, 0)283284 depther_node = [x for x in self.diagram.nodes if x.xy.x > depth]285 if len(depther_node) > 0:286 self.set_node_xpos(depth + 1)287288 def adjust_node_order(self):289 for node in list(self.diagram.nodes):290 parents = self.get_parent_nodes(node)291 if len(set(parents)) > 1:292 for i in range(1, len(parents)):293 node1 = parents[i - 1]294 node2 = parents[i]295296 if node1.xy.x == node2.xy.x:297 idx1 = self.diagram.nodes.index(node1)298 idx2 = self.diagram.nodes.index(node2)299300 if idx1 < idx2:301 self.diagram.nodes.remove(node2)302 self.diagram.nodes.insert(idx1 + 1, node2)303 else:304 self.diagram.nodes.remove(node1)305 self.diagram.nodes.insert(idx2 + 1, node1)306307 children = self.get_child_nodes(node)308 if len(set(children)) > 1:309 for i in range(1, len(children)):310 node1 = children[i - 1]311 node2 = children[i]312313 idx1 = self.diagram.nodes.index(node1)314 idx2 = self.diagram.nodes.index(node2)315316 if node1.xy.x == node2.xy.x:317 if idx1 < idx2:318 self.diagram.nodes.remove(node2)319 self.diagram.nodes.insert(idx1 + 1, node2)320 else:321 self.diagram.nodes.remove(node1)322 self.diagram.nodes.insert(idx2 + 1, node1)323 elif self.is_circular_ref(node1, node2):324 pass325 else:326 if node1.xy.x < node2.xy.x:327 self.diagram.nodes.remove(node2)328 self.diagram.nodes.insert(idx1 + 1, node2)329 else:330 self.diagram.nodes.remove(node1)331 self.diagram.nodes.insert(idx2 + 1, node1)332333 if isinstance(node, NodeGroup):334 children = self.get_child_nodes(node)335 if len(set(children)) > 1:336 while True:337 exchange = 0338339 for i in range(1, len(children)):340 node1 = children[i - 1]341 node2 = children[i]342343 idx1 = self.diagram.nodes.index(node1)344 idx2 = self.diagram.nodes.index(node2)345 ret = self.compare_child_node_order(node,346 node1, node2)347348 if ret > 0 and idx1 < idx2:349 self.diagram.nodes.remove(node1)350 self.diagram.nodes.insert(idx2 + 1, node1)351 exchange += 1352353 if exchange == 0:354 break355356 self.diagram.update_order()357358 def compare_child_node_order(self, parent, node1, node2):359 def compare(x, y):360 x = x.duplicate()361 y = y.duplicate()362 while x.node1 == y.node1 and x.node1.group is not None:363 x.node1 = x.node1.group364 y.node1 = y.node1.group365366 # cmp x.node1.order and y.node1.order367 if x.node1.order < y.node1.order:368 return -1369 elif x.node1.order == y.node1.order:370 return 0371 else:372 return 1373374 edges = (DiagramEdge.find(parent, node1) +375 DiagramEdge.find(parent, node2))376 edges.sort(key=cmp_to_key(compare))377 if len(edges) == 0:378 return 0379 elif edges[0].node2 == node2:380 return 1381 else:382 return -1383384 def mark_xy(self, xy, width, height):385 for w in range(width):386 for h in range(height):387 self.coordinates.append(XY(xy.x + w, xy.y + h))388389 def set_node_ypos(self, node, height=0):390 for x in range(node.colwidth):391 for y in range(node.colheight):392 xy = XY(node.xy.x + x, height + y)393 if xy in self.coordinates:394 return False395 node.xy = XY(node.xy.x, height)396 self.mark_xy(node.xy, node.colwidth, node.colheight)397398 def cmp(x, y):399 if x.xy.x < y.xy.y:400 return -1401 elif x.xy.x == y.xy.y:402 return 0403 else:404 return 1405406 count = 0407 children = self.get_child_nodes(node)408 children.sort(key=cmp_to_key(cmp))409410 grandchild = 0411 for child in children:412 if self.get_child_nodes(child):413 grandchild += 1414415 prev_child = None416 for child in children:417 if child.id in self.heightRefs:418 pass419 elif node.xy.x >= child.xy.x:420 pass421 else:422 if isinstance(node, NodeGroup):423 parent_height = self.get_parent_node_ypos(node, child)424 if parent_height and parent_height > height:425 height = parent_height426427 if (prev_child and grandchild > 1 and428 (not self.is_rhombus(prev_child, child))):429 coord = [p.y for p in self.coordinates if p.x > child.xy.x]430 if coord and max(coord) >= node.xy.y:431 height = max(coord) + 1432433 while True:434 if self.set_node_ypos(child, height):435 child.xy = XY(child.xy.x, height)436 self.mark_xy(child.xy, child.colwidth, child.colheight)437 self.heightRefs.append(child.id)438439 count += 1440 break441 else:442 if count == 0:443 return False444445 height += 1446447 height += 1448 prev_child = child449450 return True451452 def is_rhombus(self, node1, node2):453 ret = False454 while True:455 if node1 == node2:456 ret = True457 break458459 child1 = self.get_child_nodes(node1)460 child2 = self.get_child_nodes(node2)461462 if len(child1) != 1 or len(child2) != 1:463 break464 elif node1.xy.x > child1[0].xy.x or node2.xy.x > child2[0].xy.x:465 break466 else:467 node1 = child1[0]468 node2 = child2[0]469470 return ret471472 def get_parent_node_ypos(self, parent, child):473 heights = []474 for e in DiagramEdge.find(parent, child):475 y = parent.xy.y476477 node = e.node1478 while node != parent:479 y += node.xy.y480 node = node.group481482 heights.append(y)483484 if heights:485 return min(heights)486 else:487 return None488489490class EdgeLayoutManager(object):491 def __init__(self, diagram):492 self.diagram = diagram493494495 def groups(self):496 if self.diagram.separated:497 seq = self.diagram.nodes498 else:499 seq = self.diagram.traverse_groups(preorder=True)500501 for group in seq:502 if not group.drawable:503 yield group504505506 def nodes(self):507 if self.diagram.separated:508 seq = self.diagram.nodes509 else:510 seq = self.diagram.traverse_nodes()511512 for node in seq:513 if node.drawable:514 yield node515516517 def edges(self):518 for edge in (e for e in self.diagram.edges if e.style != 'none'):519 yield edge520521 for group in self.groups:522 for edge in (e for e in group.edges if e.style != 'none'):523 yield edge524525 def run(self):526 for edge in self.edges:527 _dir = edge.direction528529 if edge.node1.group.orientation == 'landscape':530 if _dir == 'right':531 r = range(edge.node1.xy.x + 1, edge.node2.xy.x)532 for x in r:533 xy = (x, edge.node1.xy.y)534 nodes = [x for x in self.nodes if x.xy == xy]535 if len(nodes) > 0:536 edge.skipped = 1537 elif _dir == 'right-up':538 r = range(edge.node1.xy.x + 1, edge.node2.xy.x)539 for x in r:540 xy = (x, edge.node1.xy.y)541 nodes = [x for x in self.nodes if x.xy == xy]542 if len(nodes) > 0:543 edge.skipped = 1544 elif _dir == 'right-down':545 if self.diagram.edge_layout == 'flowchart':546 r = range(edge.node1.xy.y, edge.node2.xy.y)547 for y in r:548 xy = (edge.node1.xy.x, y + 1)549 nodes = [x for x in self.nodes if x.xy == xy]550 if len(nodes) > 0:551 edge.skipped = 1552553 r = range(edge.node1.xy.x + 1, edge.node2.xy.x)554 for x in r:555 xy = (x, edge.node2.xy.y)556 nodes = [x for x in self.nodes if x.xy == xy]557 if len(nodes) > 0:558 edge.skipped = 1559 elif _dir in ('left-down', 'down'):560 r = range(edge.node1.xy.y + 1, edge.node2.xy.y)561 for y in r:562 xy = (edge.node1.xy.x, y)563 nodes = [x for x in self.nodes if x.xy == xy]564 if len(nodes) > 0:565 edge.skipped = 1566 elif _dir == 'up':567 r = range(edge.node2.xy.y + 1, edge.node1.xy.y)568 for y in r:569 xy = (edge.node1.xy.x, y)570 nodes = [x for x in self.nodes if x.xy == xy]571 if len(nodes) > 0:572 edge.skipped = 1573 else:574 if _dir == 'right':575 r = range(edge.node1.xy.x + 1, edge.node2.xy.x)576 for x in r:577 xy = (x, edge.node1.xy.y)578 nodes = [x for x in self.nodes if x.xy == xy]579 if len(nodes) > 0:580 edge.skipped = 1581 elif _dir in ('left-down', 'down'):582 r = range(edge.node1.xy.y + 1, edge.node2.xy.y)583 for y in r:584 xy = (edge.node1.xy.x, y)585 nodes = [x for x in self.nodes if x.xy == xy]586 if len(nodes) > 0:587 edge.skipped = 1588 elif _dir == 'right-down':589 if self.diagram.edge_layout == 'flowchart':590 r = range(edge.node1.xy.x, edge.node2.xy.x)591 for x in r:592 xy = (x + 1, edge.node1.xy.y)593 nodes = [x for x in self.nodes if x.xy == xy]594 if len(nodes) > 0:595 edge.skipped = 1596597 r = range(edge.node1.xy.y + 1, edge.node2.xy.y)598 for y in r:599 xy = (edge.node2.xy.x, y)600 nodes = [x for x in self.nodes if x.xy == xy]601 if len(nodes) > 0:602 edge.skipped = 1603604605class ScreenNodeBuilder:606607 def build(cls, tree, config=None, layout=True):608 DiagramNode.clear()609 DiagramEdge.clear()610 NodeGroup.clear()611 Diagram.clear()612613 return cls(tree, config, layout).run()614615 def __init__(self, tree, config, layout):616 self.diagram = DiagramTreeBuilder().build(tree, config)617 self.config = config618 self.layout = layout619620 def run(self):621 if self.layout:622 DiagramLayoutManager(self.diagram).run()623 self.diagram.fixiate(True)624625 EdgeLayoutManager(self.diagram).run()626627 return self.diagram628629630class SeparateDiagramBuilder(ScreenNodeBuilder):631632 def _groups(self):633 # Store nodes and edges of subgroups634 nodes = {self.diagram: self.diagram.nodes}635 edges = {self.diagram: self.diagram.edges}636 levels = {self.diagram: self.diagram.level}637 for group in self.diagram.traverse_groups():638 nodes[group] = group.nodes639 edges[group] = group.edges640 levels[group] = group.level641642 groups = {}643 orders = {}644 for node in self.diagram.traverse_nodes():645 groups[node] = node.group646 orders[node] = node.order647648 for group in self.diagram.traverse_groups():649 yield group650651 # Restore nodes, groups and edges652 for g in nodes:653 g.nodes = nodes[g]654 g.edges = edges[g]655 g.level = levels[g]656657 for n in groups:658 n.group = groups[n]659 n.order = orders[n]660 n.xy = XY(0, 0)661 n.colwidth = 1662 n.colheight = 1663 n.separated = False664665 for edge in DiagramEdge.find_all():666 edge.skipped = False667 edge.crosspoints = []668669 yield self.diagram670671 def _filter_edges(self, edges, parent, level):672 filtered = {}673 for e in edges:674 if e.node1.group.is_parent(parent):675 if e.node1.group.level > level:676 e = e.duplicate()677 if isinstance(e.node1, NodeGroup):678 e.node1 = e.node1.parent(level + 1)679 else:680 e.node1 = e.node1.group.parent(level + 1)681 else:682 continue683684 if e.node2.group.is_parent(parent):685 if e.node2.group.level > level:686 e = e.duplicate()687 if isinstance(e.node2, NodeGroup):688 e.node2 = e.node2.parent(level + 1)689 else:690 e.node2 = e.node2.group.parent(level + 1)691 else:692 continue693694 filtered[(e.node1, e.node2)] = e695696 return filtered.values()697698 def run(self):699 for i, group in enumerate(self._groups):700 base = self.diagram.duplicate()701 base.level = group.level - 1702703 # bind edges on base diagram (outer the group)704 edges = (DiagramEdge.find(None, group) +705 DiagramEdge.find(group, None))706 base.edges = self._filter_edges(edges, self.diagram, group.level)707708 # bind edges on target group (inner the group)709 subgroups = group.traverse_groups()710 edges = sum([g.edges for g in subgroups], group.edges)711 group.edges = []712 for e in self._filter_edges(edges, group, group.level):713 if isinstance(e.node1, NodeGroup) and e.node1 == e.node2:714 pass715 else:716 group.edges.append(e)717718 # clear subgroups in the group719 for g in group.nodes:720 if isinstance(g, NodeGroup):721 g.nodes = []722 g.edges = []723 g.separated = True724725 # pick up nodes to base diagram726 nodes1 = [e.node1 for e in DiagramEdge.find(None, group)]727 nodes1.sort(key=lambda x: x.order)728 nodes2 = [e.node2 for e in DiagramEdge.find(group, None)]729 nodes2.sort(key=lambda x: x.order)730731 nodes = nodes1 + [group] + nodes2732 for i, n in enumerate(nodes):733 n.order = i734 if n not in base.nodes:735 base.nodes.append(n)736 n.group = base737738 if isinstance(group, Diagram):739 base = group740741 DiagramLayoutManager(base).run()742 base.fixiate(True)743 EdgeLayoutManager(base).run()744745 yield base