"""Class for representing nodes in Universal Dependency trees.

# TODO: Benchmark memory and speed of slots vs. classic dict.

# With Python 3.5 split dict, slots may not be better.

# TODO: Should not we include __weakref__ in slots?

# TODO: Benchmark using node._ord instead node.ord in this file

__slots__ = [

'_ord', # Word-order index of the node (root has 0).

'form', # Word form or punctuation symbol.

'lemma', # Lemma of word form.

'upos', # Universal PoS tag.

'xpos', # Language-specific part-of-speech tag; underscore if not available.

'deprel', # UD dependency relation to the HEAD (root iff HEAD = 0).

'_misc', # Any other annotation as udapi.core.dualdict.DualDict object.

'_raw_deps', # Enhanced dependencies (head-deprel pairs) in their original CoNLLU format.

'_deps', # Deserialized enhanced dependencies in a list of {parent, deprel} dicts.

'_feats', # Morphological features as udapi.core.feats.Feats object.

'_parent', # Parent node.

'_children', # Ord-ordered list of child nodes.

'_root', # Technical root of the tree

'_mwt', # Multi-word token in which this word participates.

'_mentions', # List of udapi.core.coref.CorefMention objects whose span includes this node

]

def __init__(self, root, form=None, lemma=None, upos=None, # pylint: disable=too-many-arguments

xpos=None, feats=None, deprel=None, misc=None):

"""Create a new node and initialize its attributes using the keyword arguments."""

self._root = root

self._ord = None

self.form = form

self.lemma = lemma

self.upos = upos

self.xpos = xpos

self._feats = Feats(feats) if feats and feats != '_' else None

self.deprel = deprel

self._misc = DualDict(misc) if misc and misc != '_' else None

self._raw_deps = '_'

self._deps = None

self._parent = None

self._children = list()

self._mwt = None

self._mentions = list()

def __str__(self):

"""String representation of the Node object: <n.address(), n.form>."""

return f"<{self.address()}, {self.form}>"

def __repr__(self):

"""String representation of the Node object: Node<n.address(), n.form>."""

return f"Node<{self.address()}, {self.form}>"

@property

def root(self):

return self._root

# ord is implemented as a property, so that it can be overriden in EmptyNode and Root

@property

def ord(self):

return self._ord

@ord.setter

def ord(self, new_ord):

self._ord = new_ord

def __lt__(self, other):

"""Calling `nodeA < nodeB` is equivalent to `nodeA.ord < nodeB.ord`.

return self._ord < other._ord

@property

def udeprel(self):

"""Return the universal part of dependency relation, e.g. `acl` instead of `acl:relcl`.

return self.deprel.split(':')[0] if self.deprel is not None else None

@udeprel.setter

def udeprel(self, value):

sdeprel = self.sdeprel

if sdeprel is not None and sdeprel != '':

self.deprel = value + ':' + sdeprel

else:

self.deprel = value

@property

def sdeprel(self):

"""Return the language-specific part of dependency relation.

if self.deprel is None:

return None

parts = self.deprel.split(':', 1)

if len(parts) == 2:

return parts[1]

return ''

@sdeprel.setter

def sdeprel(self, value):

udeprel = self.udeprel

if value is not None and value != '':

self.deprel = udeprel + ':' + value

else:

self.deprel = udeprel

@property

def feats(self):

"""Property for morphological features stored as a `Feats` object.

if self._feats is None:

self._feats = Feats()

return self._feats

@feats.setter

def feats(self, value):

if self._feats is None:

self._feats = Feats(value)

else:

self._feats.set_mapping(value)

@property

def misc(self):

"""Property for MISC attributes stored as a `DualDict` object.

if self._misc is None:

self._misc = DualDict()

return self._misc

@misc.setter

def misc(self, value):

if self._misc is None:

self._misc = DualDict(value)

else:

self._misc.set_mapping(value)

@property

def raw_deps(self):

"""String serialization of enhanced dependencies as stored in CoNLL-U files.

# TODO: node.deps.append(dep) should be hooked and

# mark the serialized cache dirty, i.e. self._raw_deps = None.

# Afterwards, we can use the following optimization

#if self._raw_deps is not None:

# return self._raw_deps

if self._deps:

self._raw_deps = '|'.join(f"{p}:{r}" for p, r in sorted(set((d['parent'].ord, d['deprel']) for d in self._deps)))

return self._raw_deps

@raw_deps.setter

def raw_deps(self, value):

"""Set serialized enhanced dependencies (the new value is a string).

self._raw_deps = value

self._deps = None

@property

def deps(self):

"""Return enhanced dependencies as a Python list of dicts.

if self._deps is None:

# Create a list of secondary dependencies.

self._deps = list()

if self._raw_deps == '_':

return self._deps

# Obtain a list of all nodes in the dependency tree.

nodes = [self._root] + self._root._descendants

for raw_dependency in self._raw_deps.split('|'):

# Deprel itself may contain one or more ':' (subtypes).

head, deprel = raw_dependency.split(':', maxsplit=1)

# Empty nodes have to be located differently than normal nodes.

if '.' in head:

try:

parent = next(x for x in self._root.empty_nodes if str(x._ord) == head)

except StopIteration:

raise ValueError(f'Empty node with ord={head} not found')

else:

parent = nodes[int(head)]

self._deps.append({'parent': parent, 'deprel': deprel})

return self._deps

@deps.setter

def deps(self, value):

"""Set deserialized enhanced dependencies (the new value is a list of dicts)."""

self._deps = value

self._raw_deps = None

@property

def parent(self):

"""Return dependency parent (head) node."""

return self._parent

@parent.setter

def parent(self, new_parent):

"""Set a new dependency parent node.

# If the parent is already assigned, return.

if self._parent is new_parent:

return

# Check for None new_parent and cycles.

if new_parent is None:

raise ValueError(f'Cannot set None as parent: {self}')

if new_parent.is_empty():

raise ValueError(f'Cannot set EmptyNode as parent in basic dependencies: {self}')

if self is new_parent:

raise CycleError('Cannot set a node as its own parent (cycle are forbidden): %s', self)

if self._children and new_parent.is_descendant_of(self):

raise CycleError('Setting the parent of %s to %s would lead to a cycle.', self, new_parent)

# Remove the current Node from the children of the old parent.

# Forbid moving nodes from one tree to another using parent setter.

if self._parent:

self._parent._children.remove(self)

if self._parent._root is not new_parent._root:

raise ValueError('Cannot move nodes between trees with parent setter, '

'use new_root.steal_nodes(nodes_to_be_moved) instead')

# Set the new parent.

self._parent = new_parent

# Append the current node to the new parent children.

if not new_parent._children or self > new_parent._children[-1]:

new_parent._children.append(self)

else:

new_parent._children.append(self)

new_parent._children.sort()

@property

def children(self):

"""Return a list of dependency children (direct dependants) nodes.

return ListOfNodes(self._children, origin=self)

@property

def siblings(self):

"""Return a list of dependency sibling nodes.

return ListOfNodes([n for n in self._parent._children if n!=self], origin=self)

@property

def descendants(self):

"""Return a list of all descendants of the current node.

# The following code is equivalent to

# ListOfNodes(sorted(self.unordered_descendants()), origin=self)

# but it is faster because there is no extra copying of lists of nodes.

stack = list(self._children)

descendants = ListOfNodes(stack, origin=self)

while(stack):

n = stack.pop()

if n._children:

stack.extend(n._children)

descendants.extend(n._children)

descendants.sort()

return descendants

def is_descendant_of(self, node):

"""Is the current node a descendant of the node given as argument?"""

if node and node._children:

climber = self._parent

while climber:

if climber is node:

return True

climber = climber._parent

return False

def create_child(self, **kwargs):

"""Create and return a new child of the current node."""

new_node = Node(root=self._root, **kwargs)

new_node._ord = len(self._root._descendants) + 1

self._root._descendants.append(new_node)

self._children.append(new_node)

new_node._parent = self

return new_node

def create_empty_child(self, deprel, after=True, **kwargs):

"""Create and return a new empty node child of the current node.

new_node = EmptyNode(root=self._root, **kwargs)

new_node.deps = [{'parent': self, 'deprel': deprel}]

# self.enh_children.append(new_node) TODO

# new_node.enh_parents.append(self) TODO

base_ord = self._ord if after else self._ord - 1

new_ord = base_ord + 0.1

for empty in self._root.empty_nodes:

if empty._ord > new_ord:

break

if empty._ord == new_ord:

if isinstance(new_ord, OrdTuple):

new_ord.increase()

elif new_ord == base_ord + 0.9:

new_ord = OrdTuple(base_ord, 10)

else:

new_ord = round(new_ord+0.1, 1)

new_node._ord = new_ord

if not self._root.empty_nodes or new_node > self._root.empty_nodes[-1]:

self._root.empty_nodes.append(new_node)

else:

self._root.empty_nodes.append(new_node)

self._root.empty_nodes.sort()

return new_node

# TODO: make private: _unordered_descendants

def unordered_descendants(self):

"""Return a list of all descendants in any order."""

stack = list(self._children)

descendants = list(stack)

while(stack):

n = stack.pop()

if n._children:

stack.extend(n._children)

descendants.extend(n._children)

return descendants

@staticmethod

def is_root():

"""Is the current node a (technical) root?

return False

@staticmethod

def is_empty():

"""Is the current node an empty node?

return False

def remove(self, children=None):

"""Delete this node (and all its descendants unlsess specified otherwise).

self._parent._children.remove(self)

# If there are any children, do the action specified in the "children" parameter.

if children is not None and self._children:

if children.startswith('rehang'):

for child in self._children:

child._parent = self._parent

self._parent._children.extend(self._children)

self._parent._children.sort()

self._children.clear()

if children.endswith('warn'):

logging.warning('%s is being removed by remove(children=%s), '

' but it has (unexpected) children', self, children)

# When self is the only node being removed, it is faster to root._descendants.remove(self)

# and update the ords only where necessary (from self._ord further).

# When removing also its children+descendants, it is faster to recompute root._descendants

# and update all ords (computing leftmost descendant of self would be too slow).

if not self._children:

try:

self._root._descendants.remove(self)

except ValueError:

pass # self may be an already deleted node e.g. if n.remove() called twice

else:

for (new_ord, node) in enumerate(self._root._descendants[self._ord - 1:], self._ord):

node.ord = new_ord

last_ord = 0

for empty in self._root.empty_nodes:

if empty._ord > self._ord:

new_ord = round(empty._ord - 1, 1)

if new_ord <= last_ord:

new_ord = round(last_ord + 0.1, 1)

empty.ord = new_ord

last_ord = empty._ord

else:

# Remember the position of empty nodes, so we can reorder them as well.

empty_follows = None

if self._root.empty_nodes:

will_be_removed = self if children and children.startswith('rehang') else self.descendants(add_self=1)

prev_nonempty = self._root

empty_follows = {}

for node in self._root.descendants_and_empty:

if node.is_empty():

empty_follows[node] = prev_nonempty

elif node not in will_be_removed:

prev_nonempty = node

# TODO nodes_to_remove = self.unordered_descendants()

# and mark all nodes as deleted, remove them from MWT and coref mentions

self._root._descendants = sorted(self._root.unordered_descendants())

for (new_ord, node) in enumerate(self._root._descendants, 1):

node.ord = new_ord

# Decrease ord of empty nodes (keep their fractional part)

# Make sure that e.g. after deleting node with ord=2

# ords "1 1.1 1.2 2 2.1" will become "1 1.1 1.2 1.3".

if empty_follows:

last_ord = 0

for empty in self._root.empty_nodes:

prev_nonempty = empty_follows[empty]

new_ord = round(prev_nonempty._ord + (empty._ord % 1), 1)

while new_ord <= last_ord:

new_ord = round(new_ord + 0.1, 1)

last_ord, empty.ord = new_ord, new_ord

def _shift_before_ord(self, reference_ord, without_children=False):

"""Internal method for changing word order."""

all_nodes = self._root._descendants

empty_nodes = self._root.empty_nodes

# Moving a single node can be faster than nodes_to_move = [self]

if without_children or not self._children:

my_ord = self._ord

if reference_ord > my_ord + 1:

for i_ord in range(my_ord, reference_ord - 1):

all_nodes[i_ord - 1] = all_nodes[i_ord]

all_nodes[i_ord - 1]._ord = i_ord

all_nodes[reference_ord - 2] = self

self._ord = reference_ord - 1

for en in empty_nodes:

if en._ord > my_ord and en._ord < reference_ord:

en._ord -= 1

elif reference_ord < my_ord:

for i_ord in range(my_ord, reference_ord, -1):

all_nodes[i_ord - 1] = all_nodes[i_ord - 2]

all_nodes[i_ord - 1]._ord = i_ord

all_nodes[reference_ord - 1] = self

self._ord = reference_ord

for en in empty_nodes:

# Empty nodes before the first overt token (ID=0.X) will be never moved this way.

# We cannot know whether the caller wanted to place the shifted node before or after them.

if en._ord < my_ord and en._ord > reference_ord:

en._ord += 1

self._parent._children.sort()

return

#TODO: Updating ords of empty nodes is implemented only for the simple case above,

# but it has to be implemented also for the complex case below!

nodes_to_move = self.descendants(add_self=True)

first_ord, last_ord = nodes_to_move[0]._ord, nodes_to_move[-1]._ord

# If there are no "gaps" in nodes_to_move (e.g. when it is projective),

# we can make the shifting a bit faster and simpler.

if last_ord - first_ord + 1 == len(nodes_to_move):

# First, move a node from position src_ord to position trg_ord RIGHT-ward.

trg_ord, src_ord = last_ord, first_ord - 1

while src_ord >= reference_ord:

all_nodes[trg_ord - 1] = all_nodes[src_ord - 1]

all_nodes[trg_ord-1]._ord = trg_ord

trg_ord, src_ord = trg_ord - 1, src_ord - 1

# Second, move a node from position src_ord to position trg_ord LEFT-ward.

trg_ord, src_ord = first_ord, last_ord + 1

while src_ord < reference_ord:

all_nodes[trg_ord - 1] = all_nodes[src_ord - 1]

all_nodes[trg_ord - 1]._ord = trg_ord

trg_ord, src_ord = trg_ord + 1, src_ord + 1

# Third, move nodes_to_move to trg_ord RIGHT-ward.

trg_ord = reference_ord if reference_ord < first_ord else trg_ord

for node in nodes_to_move:

all_nodes[trg_ord - 1], node._ord = node, trg_ord

trg_ord += 1

self._parent._children.sort()

return

# First, move a node from position src_ord to position trg_ord RIGHT-ward.

# src_ord iterates decreasingly over nodes which are not moving.

trg_ord, src_ord, mov_ord = last_ord, last_ord - 1, len(nodes_to_move) - 2

while src_ord >= reference_ord:

while all_nodes[src_ord - 1] is nodes_to_move[mov_ord]:

mov_ord, src_ord = mov_ord - 1, src_ord - 1

if src_ord < reference_ord:

break

else:

all_nodes[trg_ord - 1] = all_nodes[src_ord - 1]

all_nodes[trg_ord - 1]._ord = trg_ord

trg_ord, src_ord = trg_ord - 1, src_ord - 1

# Second, move a node from position src_ord to position trg_ord LEFT-ward.

# src_ord iterates increasingly over nodes which are not moving.

trg_ord, src_ord, mov_ord = first_ord, first_ord + 1, 1

while src_ord < reference_ord:

while mov_ord < len(nodes_to_move) and all_nodes[src_ord - 1] is nodes_to_move[mov_ord]:

mov_ord, src_ord = mov_ord + 1, src_ord + 1

if src_ord >= reference_ord:

break

else:

all_nodes[trg_ord - 1] = all_nodes[src_ord - 1]

all_nodes[trg_ord - 1]._ord = trg_ord

trg_ord, src_ord = trg_ord + 1, src_ord + 1

# Third, move nodes_to_move to trg_ord RIGHT-ward.

trg_ord = reference_ord if reference_ord < first_ord else trg_ord

for node in nodes_to_move:

all_nodes[trg_ord - 1], node._ord = node, trg_ord

trg_ord += 1

self._parent._children.sort()

def shift_after_node(self, reference_node, without_children=False, skip_if_descendant=False):

"""Shift this node after the reference_node."""

if not without_children and reference_node.is_descendant_of(self):

if skip_if_descendant:

return

raise ValueError(f'{reference_node} is a descendant of {self}. Consider without_children=1.')

self._shift_before_ord(reference_node._ord + 1, without_children=without_children)

def shift_before_node(self, reference_node, without_children=False, skip_if_descendant=False):

"""Shift this node before the reference_node."""

if reference_node.is_root():

raise ValueError(f'Cannot shift a node before the root ({reference_node})')

if not without_children and reference_node.is_descendant_of(self):

if skip_if_descendant:

return

raise ValueError(f'{reference_node} is a descendant of {self}. Consider without_children=1.')

self._shift_before_ord(reference_node._ord, without_children=without_children)

def shift_after_subtree(self, reference_node, without_children=False, skip_if_descendant=False):

"""Shift this node (and its subtree) after the subtree rooted by reference_node.

if not without_children and reference_node.is_descendant_of(self):

if skip_if_descendant:

return

raise ValueError(f'{reference_node} is a descendant of {self}. Consider without_children=1.')

ref_ord = reference_node._ord

for node in reference_node.unordered_descendants():

if node._ord > ref_ord and node is not self:

ref_ord = node._ord

self._shift_before_ord(ref_ord + 1, without_children=without_children)

def shift_before_subtree(self, reference_node, without_children=0, skip_if_descendant=False):

"""Shift this node (and its subtree) before the subtree rooted by reference_node.

if reference_node.is_root():

raise ValueError(f'Cannot shift a node before the root ({reference_node})')

if not without_children and reference_node.is_descendant_of(self):

if skip_if_descendant:

return

raise ValueError(f'{reference_node} is a descendant of {self}. Consider without_children=1.')

ref_ord = reference_node._ord

for node in reference_node.unordered_descendants():

if node._ord < ref_ord and node is not self:

ref_ord = node._ord

self._shift_before_ord(ref_ord, without_children=without_children)

@property

def prev_node(self):

"""Return the previous node according to word order."""

new_ord = self._ord - 1

if new_ord < 0:

return None

if new_ord == 0:

return self._root

return self._root._descendants[new_ord - 1]

@property

def next_node(self):

"""Return the following node according to word order."""

# Note that all_nodes[n].ord == n+1

try:

return self._root._descendants[self._ord]

except IndexError:

return None

def precedes(self, node):

"""Does this node precedes another `node` in word order?

if self._root is node._root:

return self._ord < node._ord

if self._root._zone != node._root._zone:

raise ValueError(f"Cannot compare word order across zones: {self} {node}")

if self._root._bundle._document is not node._root._bundle._document:

raise ValueError(f"Cannot compare word order across documents: {self} {node}")

return self._root._bundle.number < node._root._bundle.number

def is_leaf(self):

"""Is this node a leaf, ie. a node without any children?"""

return not self._children

def _get_attr(self, name): # pylint: disable=too-many-return-statements

if name == 'dir':

if not self._parent or self._parent.is_root():

return 'root'

return 'left' if self.precedes(self._parent) else 'right'

if name == 'edge':

if not self._parent or self._parent.is_root():

return 0

return self._ord - self._parent._ord

if name == 'children':

return len(self._children)

if name == 'siblings':

return 0 if not self._parent else len(self._parent._children) - 1

if name == 'depth':

value = 0

tmp = self

while tmp and not tmp.is_root():

tmp = tmp._parent

value += 1

return value

if name == 'feats_split':

return str(self.feats).split('|')

if name == 'misc_split':

return str(self.misc).split('|')

if name.startswith('feats['):

return self.feats[name[6:-1]]

if name.startswith('misc['):

return self.misc[name[5:-1]]

return getattr(self, name)

def get_attrs(self, attrs, undefs=None, stringify=True):

"""Return multiple attributes or pseudo-attributes, possibly substituting empty ones.

values = []

for name in attrs:

nodes = [self]

if name.startswith('p_'):

nodes, name = [self._parent], name[2:]

elif name.startswith('c_'):

nodes, name = self.children, name[2:]

elif name.startswith('l_'):

nodes, name = [self.prev_node], name[2:]

elif name.startswith('r_'):

nodes, name = [self.next_node], name[2:]

for node in (n for n in nodes if n is not None):

if name in {'feats_split', 'misc_split'}:

values.extend(node._get_attr(name))

else:

values.append(node._get_attr(name))

if undefs is not None:

values = [x if x is not None else undefs for x in values]

if stringify:

values = [str(x) if x is not None else None for x in values]

return values

def compute_text(self, use_mwt=True):

"""Return a string representing this subtree's text (detokenized).

string = ''

last_mwt_id = 0

for node in self.descendants(add_self=not self.is_root()):

mwt = node.multiword_token

if use_mwt and mwt:

if node._ord > last_mwt_id:

last_mwt_id = mwt.words[-1]._ord

string += mwt.form

if mwt.misc['SpaceAfter'] != 'No':

string += ' '

else:

string += node.form

if node.misc['SpaceAfter'] != 'No':

string += ' '

return string.rstrip()

def print_subtree(self, **kwargs):

"""deprecated name for draw()"""

logging.warning("node.print_subtree() is deprecated, use node.draw() instead.")

TextModeTrees(**kwargs).process_tree(self)

def draw(self, **kwargs):

"""Print ASCII visualization of the dependency structure of this subtree.

TextModeTrees(**kwargs).process_tree(self)

def address(self):

"""Return full (document-wide) id of the node.

return f"{self._root.address() if self._root else '?'}#{self._ord}"

@property

def multiword_token(self):

"""Return the multi-word token which includes this node, or None.

return self._mwt

@property

def words(self):

"""Return one-item list with this node.

return [self]

def is_nonprojective(self):

"""Is the node attached to its parent non-projectively?

# Root and its children are always projective

parent = self._parent

if not parent or parent.is_root():

return False

# Edges between neighboring nodes are always projective.

# Check it now to make it a bit faster.

ord1, ord2 = self._ord, parent._ord

if ord1 > ord2:

ord1, ord2 = ord2, ord1

distance = ord2 - ord1

if distance == 1:

return False

# Get all the descendants of parent that are in the span of the edge.

span = [n for n in parent.unordered_descendants() if n._ord > ord1 and n._ord < ord2]

# For projective edges, span must include all the nodes between parent and self.

return len(span) != distance - 1

def is_nonprojective_gap(self):

"""Is the node causing a non-projective gap within another node's subtree?

ancestors = set([self])

node = self

while node._parent:

node = node._parent

ancestors.add(node)

all_nodes = node._descendants

for left_node in all_nodes[:self._ord - 1]:

if self.precedes(left_node._parent) and left_node._parent not in ancestors:

return True

for right_node in all_nodes[self._ord:]:

if right_node._parent.precedes(self) and right_node._parent not in ancestors:

return True

return False

@property

def no_space_after(self):

"""Boolean property as a shortcut for `node.misc["SpaceAfter"] == "No"`."""

return self.misc["SpaceAfter"] == "No"

@property

def gloss(self):

"""String property as a shortcut for `node.misc["Gloss"]`."""

return self.misc["Gloss"]

@gloss.setter

def gloss(self, new_gloss):

self.misc["Gloss"] = new_gloss

@property

def coref_mentions(self):

self._root.bundle.document._load_coref()

return self._mentions

@property

def coref_entities(self):

self._root.bundle.document._load_coref()

return [m.entity for m in self._mentions if m.entity is not None]

# TODO: is this method useful?