Repository: explosion/spaCy
Pull request: Detect cycle during projectivize
<!--- Provide a general summary of your changes in the title. -->

## Description
Attempting to detect cycles during `projectivize` step in `get_aligned_parse`. Fixes #10859.

### Types of change
Small bugfix

## Checklist

- [x] I confirm that I have the right to submit this contribution under the project's MIT license.
- [x] I ran the tests, and all new and existing tests passed.
- [x] My changes don't require a change to the documentation, or if they do, I've added all required information.


Problem statement:
Parser initialization hangs on parses with cycles
<!-- NOTE: For questions or install related issues, please open a Discussion instead. -->

## How to reproduce the behaviour
<!-- Include a code example or the steps that led to the problem. Please try to be as specific as possible. -->

`projectivize` hangs when there are cycles in the dependency tree (or non-tree as it were), which means that the parser initialization step hangs on ill-formed input docs.

Specific places where this hangs in practice:

* `spacy debug data` hangs while initializing the pipeline, right before loading the training corpus
* `spacy train` hangs right after `Finished initializing nlp object` as it starts to initialize the individual pipeline components

Potential fix under discussion: modify the implementation of `_get_smallest_nonproj_arc` to detect cycles during projectivization in order to be able to raise an error.

The current parser refactor will be completed first and it may make sense to delay any changes to the projectivization algorithm to v4.

Hints from issue discussion:

Commit message: Remove unused error code

Patch to review:
diff --git a/spacy/pipeline/_parser_internals/nonproj.hh b/spacy/pipeline/_parser_internals/nonproj.hh
new file mode 100644
index 00000000000..071fd57b4d8
--- /dev/null
+++ b/spacy/pipeline/_parser_internals/nonproj.hh
@@ -0,0 +1,11 @@
+#ifndef NONPROJ_HH
+#define NONPROJ_HH
+
+#include <stdexcept>
+#include <string>
+
+void raise_domain_error(std::string const &msg) {
+    throw std::domain_error(msg);
+}
+
+#endif // NONPROJ_HH
diff --git a/spacy/pipeline/_parser_internals/nonproj.pxd b/spacy/pipeline/_parser_internals/nonproj.pxd
index e69de29bb2d..aabdf7ebe31 100644
--- a/spacy/pipeline/_parser_internals/nonproj.pxd
+++ b/spacy/pipeline/_parser_internals/nonproj.pxd
@@ -0,0 +1,4 @@
+from libcpp.string cimport string
+
+cdef extern from "nonproj.hh":
+    cdef void raise_domain_error(const string& msg) nogil except +
diff --git a/spacy/pipeline/_parser_internals/nonproj.pyx b/spacy/pipeline/_parser_internals/nonproj.pyx
index 36163fcc356..adafbcc6ac4 100644
--- a/spacy/pipeline/_parser_internals/nonproj.pyx
+++ b/spacy/pipeline/_parser_internals/nonproj.pyx
@@ -8,6 +8,7 @@ from libc.limits cimport INT_MAX
 from libc.stdlib cimport abs
 from libcpp cimport bool
 from libcpp.vector cimport vector
+from libcpp.unordered_set cimport unordered_set
 
 from ...tokens.doc cimport Doc, set_children_from_heads
 
@@ -49,7 +50,7 @@ def is_nonproj_arc(tokenid, heads):
     return _is_nonproj_arc(tokenid, c_heads)
 
 
-cdef bool _is_nonproj_arc(int tokenid, const vector[int]& heads) nogil:
+cdef bool _is_nonproj_arc(int tokenid, const vector[int]& heads) nogil except *:
     # definition (e.g. Havelka 2007): an arc h -> d, h < d is non-projective
     # if there is a token k, h < k < d such that h is not
     # an ancestor of k. Same for h -> d, h > d
@@ -58,28 +59,34 @@ cdef bool _is_nonproj_arc(int tokenid, const vector[int]& heads) nogil:
         return False
     elif head < 0:  # unattached tokens cannot be non-projective
         return False
-    
+
     cdef int start, end
     if head < tokenid:
         start, end = (head+1, tokenid)
     else:
         start, end = (tokenid+1, head)
     for k in range(start, end):
-        if _has_head_as_ancestor(k, head, heads):
-            continue
-        else:  # head not in ancestors: d -> h is non-projective
+        if not _has_head_as_ancestor(k, head, heads):
             return True
     return False
 
 
-cdef bool _has_head_as_ancestor(int tokenid, int head, const vector[int]& heads) nogil:
+cdef bool _has_head_as_ancestor(int tokenid, int head, const vector[int]& heads) nogil except *:
     ancestor = tokenid
-    cnt = 0
-    while cnt < heads.size():
+    cdef unordered_set[int] seen_tokens
+    seen_tokens.insert(ancestor)
+    while True:
+        # Reached the head or a disconnected node
         if heads[ancestor] == head or heads[ancestor] < 0:
             return True
+        # Reached the root
+        if heads[ancestor] == ancestor:
+            return False
         ancestor = heads[ancestor]
-        cnt += 1
+        result = seen_tokens.insert(ancestor)
+        # Found cycle
+        if not result.second:
+            raise_domain_error("Found cycle in dependency graph")
 
     return False
 
@@ -176,11 +183,12 @@ def get_smallest_nonproj_arc_slow(heads):
     return _get_smallest_nonproj_arc(c_heads)
 
 
-cdef int _get_smallest_nonproj_arc(const vector[int]& heads) nogil:
+cdef int _get_smallest_nonproj_arc(const vector[int]& heads) nogil except -2:
     # return the smallest non-proj arc or None
     # where size is defined as the distance between dep and head
     # and ties are broken left to right
     cdef int smallest_size = INT_MAX
+    # -1 means its already projective.
     cdef int smallest_np_arc = -1
     cdef int size
     cdef int tokenid
diff --git a/spacy/tests/parser/test_nonproj.py b/spacy/tests/parser/test_nonproj.py
index 60d000c449c..5e9d0541b0b 100644
--- a/spacy/tests/parser/test_nonproj.py
+++ b/spacy/tests/parser/test_nonproj.py
@@ -84,8 +84,10 @@ def deprojectivize(proj_heads, deco_labels):
     tree = [1, 2, 2]
     nonproj_tree = [1, 2, 2, 4, 5, 2, 7, 4, 2]
     nonproj_tree2 = [9, 1, 3, 1, 5, 6, 9, 8, 6, 1, 6, 12, 13, 10, 1]
+    cyclic_tree = [1, 2, 2, 4, 5, 3, 2]
     labels = ["det", "nsubj", "root", "det", "dobj", "aux", "nsubj", "acl", "punct"]
     labels2 = ["advmod", "root", "det", "nsubj", "advmod", "det", "dobj", "det", "nmod", "aux", "nmod", "advmod", "det", "amod", "punct"]
+    cyclic_labels = ["det", "nsubj", "root", "det", "dobj", "aux", "punct"]
     # fmt: on
     assert nonproj.decompose("X||Y") == ("X", "Y")
     assert nonproj.decompose("X") == ("X", "")
@@ -97,6 +99,8 @@ def deprojectivize(proj_heads, deco_labels):
     assert nonproj.get_smallest_nonproj_arc_slow(nonproj_tree2) == 10
     # fmt: off
     proj_heads, deco_labels = nonproj.projectivize(nonproj_tree, labels)
+    with pytest.raises(ValueError):
+        nonproj.projectivize(cyclic_tree, cyclic_labels)
     assert proj_heads == [1, 2, 2, 4, 5, 2, 7, 5, 2]
     assert deco_labels == ["det", "nsubj", "root", "det", "dobj", "aux",
                            "nsubj", "acl||dobj", "punct"]
diff --git a/spacy/tests/training/test_training.py b/spacy/tests/training/test_training.py
index 8e08a25fbfc..31bf7e07bf4 100644
--- a/spacy/tests/training/test_training.py
+++ b/spacy/tests/training/test_training.py
@@ -671,13 +671,13 @@ def test_gold_ner_missing_tags(en_tokenizer):
 
 def test_projectivize(en_tokenizer):
     doc = en_tokenizer("He pretty quickly walks away")
-    heads = [3, 2, 3, 0, 2]
+    heads = [3, 2, 3, 3, 2]
     deps = ["dep"] * len(heads)
     example = Example.from_dict(doc, {"heads": heads, "deps": deps})
     proj_heads, proj_labels = example.get_aligned_parse(projectivize=True)
     nonproj_heads, nonproj_labels = example.get_aligned_parse(projectivize=False)
-    assert proj_heads == [3, 2, 3, 0, 3]
-    assert nonproj_heads == [3, 2, 3, 0, 2]
+    assert proj_heads == [3, 2, 3, 3, 3]
+    assert nonproj_heads == [3, 2, 3, 3, 2]
 
 
 def test_iob_to_biluo():


Code review comments:
diff_hunk: @@ -48,76 +47,54 @@ def contains_cycle(heads):
 
 def is_nonproj_arc(tokenid, heads):
     cdef vector[int] c_heads = _heads_to_c(heads)
-    is_nonproj = _is_nonproj_arc(tokenid, c_heads)
-    if is_nonproj.second:
-        raise ValueError(Errors.E1038.format(heads=heads))
-    return is_nonproj.first
+    return _is_nonproj_arc(tokenid, c_heads)
 
 
-cdef pair[bool, bool] _is_nonproj_arc(int tokenid, const vector[int]& heads) nogil:
-    # Returns (True, False) if the arc is projective, (False, False)
-    # if it is non-projective, or (False, True) when there is a
-    # cycle.
-    #
+cdef bool _is_nonproj_arc(int tokenid, const vector[int]& heads) nogil except *:
     # definition (e.g. Havelka 2007): an arc h -> d, h < d is non-projective
     # if there is a token k, h < k < d such that h is not
     # an ancestor of k. Same for h -> d, h > d
     head = heads[tokenid]
     if head == tokenid:  # root arcs cannot be non-projective
-        return pair[bool, bool](False, False)
+        return False
     elif head < 0:  # unattached tokens cannot be non-projective
-        return pair[bool, bool](False, False)
+        return False
 
     cdef int start, end
     if head < tokenid:
         start, end = (head+1, tokenid)
     else:
         start, end = (tokenid+1, head)
     for k in range(start, end):
-        has_head = _has_head_as_ancestor(k, head, heads)
-        # Do we have a cycle?
-        if has_head.second:
-            return pair[bool, bool](False, True)
-        # head not in ancestors?: d -> h is non-projective
-        elif not has_head.first:
-            return pair[bool, bool](True, False)
-    return pair[bool, bool](False, False)
-
-
-cdef pair[bool, bool] _has_head_as_ancestor(int tokenid, int head, const vector[int]& heads) nogil:
-    # Returns (True, False) if tokenid as head as an ancestor,
-    # (False, False) if it does not have head as an ancestor,
-    # (False, True) when there is a cycle.
+        if not _has_head_as_ancestor(k, head, heads):
+            return True
+    return False
+
+
+cdef bool _has_head_as_ancestor(int tokenid, int head, const vector[int]& heads) nogil except *:
     ancestor = tokenid
     cdef unordered_set[int] seen_tokens
     seen_tokens.insert(ancestor)
     while True:
         # Reached the head or a disconnected node
         if heads[ancestor] == head or heads[ancestor] < 0:
-            return pair[bool, bool](True, False)
+            return True
         # Reached the root
         if heads[ancestor] == ancestor:
-            return pair[bool, bool](False, False)
+            return False
         ancestor = heads[ancestor]
         result = seen_tokens.insert(ancestor)
         # Found cycle
         if not result.second:
-            return pair[bool, bool](False, True)
+            raise_domain_error("Found cycle in dependency graph")
path: spacy/pipeline/_parser_internals/nonproj.pyx
text: @user1:
Perhaps we can also include a representation of `heads` in the error message? It's a pity we can't use `raise` here with our default error message machinery, as we'll end up with the GIL-RefNanny catch-22 as before. 

@user2:
Good idea, I'll add something!

@user2:
Done. A bit ugly, because we don't have `ostringstream` in Cython, so we cannot do this the nice C++ way.