#!/usr/bin/env python
#
# Natural Language Toolkit: TGrep search
#
# Copyright (C) 2001-2023 NLTK Project
# Author: Will Roberts <wildwilhelm@gmail.com>
# URL: <https://www.nltk.org/>
# For license information, see LICENSE.TXT

"""
Unit tests for nltk.tgrep.
"""


import unittest

from nltk import tgrep
from nltk.tree import ParentedTree


class TestSequenceFunctions(unittest.TestCase):

    """
    Class containing unit tests for nltk.tgrep.
    """

    def test_tokenize_simple(self):
        """
        Simple test of tokenization.
        """
        tokens = tgrep.tgrep_tokenize("A .. (B !< C . D) | ![<< (E , F) $ G]")
        self.assertEqual(
            tokens,
            [
                "A",
                "..",
                "(",
                "B",
                "!",
                "<",
                "C",
                ".",
                "D",
                ")",
                "|",
                "!",
                "[",
                "<<",
                "(",
                "E",
                ",",
                "F",
                ")",
                "$",
                "G",
                "]",
            ],
        )

    def test_tokenize_encoding(self):
        """
        Test that tokenization handles bytes and strs the same way.
        """
        self.assertEqual(
            tgrep.tgrep_tokenize(b"A .. (B !< C . D) | ![<< (E , F) $ G]"),
            tgrep.tgrep_tokenize("A .. (B !< C . D) | ![<< (E , F) $ G]"),
        )

    def test_tokenize_link_types(self):
        """
        Test tokenization of basic link types.
        """
        self.assertEqual(tgrep.tgrep_tokenize("A<B"), ["A", "<", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>B"), ["A", ">", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<3B"), ["A", "<3", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>3B"), ["A", ">3", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<,B"), ["A", "<,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>,B"), ["A", ">,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<-3B"), ["A", "<-3", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>-3B"), ["A", ">-3", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<-B"), ["A", "<-", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>-B"), ["A", ">-", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<'B"), ["A", "<'", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>'B"), ["A", ">'", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<:B"), ["A", "<:", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>:B"), ["A", ">:", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<<B"), ["A", "<<", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>>B"), ["A", ">>", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<<,B"), ["A", "<<,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>>,B"), ["A", ">>,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<<'B"), ["A", "<<'", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>>'B"), ["A", ">>'", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A<<:B"), ["A", "<<:", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A>>:B"), ["A", ">>:", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A.B"), ["A", ".", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A,B"), ["A", ",", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A..B"), ["A", "..", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A,,B"), ["A", ",,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A$B"), ["A", "$", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A$.B"), ["A", "$.", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A$,B"), ["A", "$,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A$..B"), ["A", "$..", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A$,,B"), ["A", "$,,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<B"), ["A", "!", "<", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>B"), ["A", "!", ">", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<3B"), ["A", "!", "<3", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>3B"), ["A", "!", ">3", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<,B"), ["A", "!", "<,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>,B"), ["A", "!", ">,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<-3B"), ["A", "!", "<-3", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>-3B"), ["A", "!", ">-3", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<-B"), ["A", "!", "<-", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>-B"), ["A", "!", ">-", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<'B"), ["A", "!", "<'", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>'B"), ["A", "!", ">'", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<:B"), ["A", "!", "<:", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>:B"), ["A", "!", ">:", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<<B"), ["A", "!", "<<", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>>B"), ["A", "!", ">>", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<<,B"), ["A", "!", "<<,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>>,B"), ["A", "!", ">>,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<<'B"), ["A", "!", "<<'", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>>'B"), ["A", "!", ">>'", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!<<:B"), ["A", "!", "<<:", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!>>:B"), ["A", "!", ">>:", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!.B"), ["A", "!", ".", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!,B"), ["A", "!", ",", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!..B"), ["A", "!", "..", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!,,B"), ["A", "!", ",,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!$B"), ["A", "!", "$", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!$.B"), ["A", "!", "$.", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!$,B"), ["A", "!", "$,", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!$..B"), ["A", "!", "$..", "B"])
        self.assertEqual(tgrep.tgrep_tokenize("A!$,,B"), ["A", "!", "$,,", "B"])

    def test_tokenize_examples(self):
        """
        Test tokenization of the TGrep2 manual example patterns.
        """
        self.assertEqual(tgrep.tgrep_tokenize("NP < PP"), ["NP", "<", "PP"])
        self.assertEqual(tgrep.tgrep_tokenize("/^NP/"), ["/^NP/"])
        self.assertEqual(
            tgrep.tgrep_tokenize("NP << PP . VP"), ["NP", "<<", "PP", ".", "VP"]
        )
        self.assertEqual(
            tgrep.tgrep_tokenize("NP << PP | . VP"), ["NP", "<<", "PP", "|", ".", "VP"]
        )
        self.assertEqual(
            tgrep.tgrep_tokenize("NP !<< PP [> NP | >> VP]"),
            ["NP", "!", "<<", "PP", "[", ">", "NP", "|", ">>", "VP", "]"],
        )
        self.assertEqual(
            tgrep.tgrep_tokenize("NP << (PP . VP)"),
            ["NP", "<<", "(", "PP", ".", "VP", ")"],
        )
        self.assertEqual(
            tgrep.tgrep_tokenize("NP <' (PP <, (IN < on))"),
            ["NP", "<'", "(", "PP", "<,", "(", "IN", "<", "on", ")", ")"],
        )
        self.assertEqual(
            tgrep.tgrep_tokenize("S < (A < B) < C"),
            ["S", "<", "(", "A", "<", "B", ")", "<", "C"],
        )
        self.assertEqual(
            tgrep.tgrep_tokenize("S < ((A < B) < C)"),
            ["S", "<", "(", "(", "A", "<", "B", ")", "<", "C", ")"],
        )
        self.assertEqual(
            tgrep.tgrep_tokenize("S < (A < B < C)"),
            ["S", "<", "(", "A", "<", "B", "<", "C", ")"],
        )
        self.assertEqual(tgrep.tgrep_tokenize("A<B&.C"), ["A", "<", "B", "&", ".", "C"])

    def test_tokenize_quoting(self):
        """
        Test tokenization of quoting.
        """
        self.assertEqual(
            tgrep.tgrep_tokenize('"A<<:B"<<:"A $.. B"<"A>3B"<C'),
            ['"A<<:B"', "<<:", '"A $.. B"', "<", '"A>3B"', "<", "C"],
        )

    def test_tokenize_nodenames(self):
        """
        Test tokenization of node names.
        """
        self.assertEqual(tgrep.tgrep_tokenize("Robert"), ["Robert"])
        self.assertEqual(tgrep.tgrep_tokenize("/^[Bb]ob/"), ["/^[Bb]ob/"])
        self.assertEqual(tgrep.tgrep_tokenize("*"), ["*"])
        self.assertEqual(tgrep.tgrep_tokenize("__"), ["__"])
        # test tokenization of NLTK tree position syntax
        self.assertEqual(tgrep.tgrep_tokenize("N()"), ["N(", ")"])
        self.assertEqual(tgrep.tgrep_tokenize("N(0,)"), ["N(", "0", ",", ")"])
        self.assertEqual(tgrep.tgrep_tokenize("N(0,0)"), ["N(", "0", ",", "0", ")"])
        self.assertEqual(
            tgrep.tgrep_tokenize("N(0,0,)"), ["N(", "0", ",", "0", ",", ")"]
        )

    def test_tokenize_macros(self):
        """
        Test tokenization of macro definitions.
        """
        self.assertEqual(
            tgrep.tgrep_tokenize(
                "@ NP /^NP/;\n@ NN /^NN/;\n@NP [!< NP | < @NN] !$.. @NN"
            ),
            [
                "@",
                "NP",
                "/^NP/",
                ";",
                "@",
                "NN",
                "/^NN/",
                ";",
                "@NP",
                "[",
                "!",
                "<",
                "NP",
                "|",
                "<",
                "@NN",
                "]",
                "!",
                "$..",
                "@NN",
            ],
        )

    def test_node_simple(self):
        """
        Test a simple use of tgrep for finding nodes matching a given
        pattern.
        """
        tree = ParentedTree.fromstring(
            "(S (NP (DT the) (JJ big) (NN dog)) " "(VP bit) (NP (DT a) (NN cat)))"
        )
        self.assertEqual(list(tgrep.tgrep_positions("NN", [tree])), [[(0, 2), (2, 1)]])
        self.assertEqual(
            list(tgrep.tgrep_nodes("NN", [tree])), [[tree[0, 2], tree[2, 1]]]
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("NN|JJ", [tree])), [[(0, 1), (0, 2), (2, 1)]]
        )

    def test_node_printing(self):
        """Test that the tgrep print operator ' is properly ignored."""
        tree = ParentedTree.fromstring("(S (n x) (N x))")
        self.assertEqual(
            list(tgrep.tgrep_positions("N", [tree])),
            list(tgrep.tgrep_positions("'N", [tree])),
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("/[Nn]/", [tree])),
            list(tgrep.tgrep_positions("'/[Nn]/", [tree])),
        )

    def test_node_encoding(self):
        """
        Test that tgrep search strings handles bytes and strs the same
        way.
        """
        tree = ParentedTree.fromstring(
            "(S (NP (DT the) (JJ big) (NN dog)) " "(VP bit) (NP (DT a) (NN cat)))"
        )
        self.assertEqual(
            list(tgrep.tgrep_positions(b"NN", [tree])),
            list(tgrep.tgrep_positions(b"NN", [tree])),
        )
        self.assertEqual(
            list(tgrep.tgrep_nodes(b"NN", [tree])),
            list(tgrep.tgrep_nodes("NN", [tree])),
        )
        self.assertEqual(
            list(tgrep.tgrep_positions(b"NN|JJ", [tree])),
            list(tgrep.tgrep_positions("NN|JJ", [tree])),
        )

    def test_node_nocase(self):
        """
        Test selecting nodes using case insensitive node names.
        """
        tree = ParentedTree.fromstring("(S (n x) (N x))")
        self.assertEqual(list(tgrep.tgrep_positions('"N"', [tree])), [[(1,)]])
        self.assertEqual(list(tgrep.tgrep_positions('i@"N"', [tree])), [[(0,), (1,)]])

    def test_node_quoted(self):
        """
        Test selecting nodes using quoted node names.
        """
        tree = ParentedTree.fromstring('(N ("N" x) (N" x) ("\\" x))')
        self.assertEqual(list(tgrep.tgrep_positions('"N"', [tree])), [[()]])
        self.assertEqual(list(tgrep.tgrep_positions('"\\"N\\""', [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions('"N\\""', [tree])), [[(1,)]])
        self.assertEqual(list(tgrep.tgrep_positions('"\\"\\\\\\""', [tree])), [[(2,)]])

    def test_node_regex(self):
        """
        Test regex matching on nodes.
        """
        tree = ParentedTree.fromstring("(S (NP-SBJ x) (NP x) (NNP x) (VP x))")
        # This is a regular expression that matches any node whose
        # name starts with NP, including NP-SBJ:
        self.assertEqual(list(tgrep.tgrep_positions("/^NP/", [tree])), [[(0,), (1,)]])

    def test_node_regex_2(self):
        """
        Test regex matching on nodes.
        """
        tree = ParentedTree.fromstring("(S (SBJ x) (SBJ1 x) (NP-SBJ x))")
        self.assertEqual(list(tgrep.tgrep_positions("/^SBJ/", [tree])), [[(0,), (1,)]])
        # This is a regular expression that matches any node whose
        # name includes SBJ, including NP-SBJ:
        self.assertEqual(
            list(tgrep.tgrep_positions("/SBJ/", [tree])), [[(0,), (1,), (2,)]]
        )

    def test_node_tree_position(self):
        """
        Test matching on nodes based on NLTK tree position.
        """
        tree = ParentedTree.fromstring("(S (NP-SBJ x) (NP x) (NNP x) (VP x))")
        # test all tree positions that are not leaves
        leaf_positions = {tree.leaf_treeposition(x) for x in range(len(tree.leaves()))}
        tree_positions = [x for x in tree.treepositions() if x not in leaf_positions]
        for position in tree_positions:
            node_id = f"N{position}"
            tgrep_positions = list(tgrep.tgrep_positions(node_id, [tree]))
            self.assertEqual(len(tgrep_positions[0]), 1)
            self.assertEqual(tgrep_positions[0][0], position)

    def test_node_noleaves(self):
        """
        Test node name matching with the search_leaves flag set to False.
        """
        tree = ParentedTree.fromstring("(S (A (T x)) (B (N x)))")
        self.assertEqual(
            list(tgrep.tgrep_positions("x", [tree])), [[(0, 0, 0), (1, 0, 0)]]
        )
        self.assertEqual(list(tgrep.tgrep_positions("x", [tree], False)), [[]])

    def tests_rel_dominance(self):
        """
        Test matching nodes based on dominance relations.
        """
        tree = ParentedTree.fromstring("(S (A (T x)) (B (N x)))")
        self.assertEqual(list(tgrep.tgrep_positions("* < T", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* < T > S", [tree])), [[(0,)]])
        self.assertEqual(
            list(tgrep.tgrep_positions("* !< T", [tree])),
            [[(), (0, 0), (0, 0, 0), (1,), (1, 0), (1, 0, 0)]],
        )
        self.assertEqual(list(tgrep.tgrep_positions("* !< T > S", [tree])), [[(1,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* > A", [tree])), [[(0, 0)]])
        self.assertEqual(list(tgrep.tgrep_positions("* > B", [tree])), [[(1, 0)]])
        self.assertEqual(
            list(tgrep.tgrep_positions("* !> B", [tree])),
            [[(), (0,), (0, 0), (0, 0, 0), (1,), (1, 0, 0)]],
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* !> B >> S", [tree])), [[(0,), (0, 0), (1,)]]
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* >> S", [tree])),
            [[(0,), (0, 0), (1,), (1, 0)]],
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* >>, S", [tree])), [[(0,), (0, 0)]]
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* >>' S", [tree])), [[(1,), (1, 0)]]
        )
        # Known issue:
        # self.assertEqual(list(tgrep.tgrep_positions('* !>> S', [tree])),
        #                 [[()]])
        self.assertEqual(list(tgrep.tgrep_positions("* << T", [tree])), [[(), (0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <<' T", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <<1 N", [tree])), [[(1,)]])
        self.assertEqual(
            list(tgrep.tgrep_positions("* !<< T", [tree])),
            [[(0, 0), (0, 0, 0), (1,), (1, 0), (1, 0, 0)]],
        )
        tree = ParentedTree.fromstring("(S (A (T x)) (B (T x) (N x )))")
        self.assertEqual(list(tgrep.tgrep_positions("* <: T", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* < T", [tree])), [[(0,), (1,)]])
        self.assertEqual(
            list(tgrep.tgrep_positions("* !<: T", [tree])),
            [[(), (0, 0), (0, 0, 0), (1,), (1, 0), (1, 0, 0), (1, 1), (1, 1, 0)]],
        )
        self.assertEqual(list(tgrep.tgrep_positions("* !<: T > S", [tree])), [[(1,)]])
        tree = ParentedTree.fromstring("(S (T (A x) (B x)) (T (C x)))")
        self.assertEqual(list(tgrep.tgrep_positions("* >: T", [tree])), [[(1, 0)]])
        self.assertEqual(
            list(tgrep.tgrep_positions("* !>: T", [tree])),
            [[(), (0,), (0, 0), (0, 0, 0), (0, 1), (0, 1, 0), (1,), (1, 0, 0)]],
        )
        tree = ParentedTree.fromstring(
            "(S (A (B (C (D (E (T x))))))" " (A (B (C (D (E (T x))) (N x)))))"
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* <<: T", [tree])),
            [
                [
                    (0,),
                    (0, 0),
                    (0, 0, 0),
                    (0, 0, 0, 0),
                    (0, 0, 0, 0, 0),
                    (1, 0, 0, 0),
                    (1, 0, 0, 0, 0),
                ]
            ],
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* >>: A", [tree])),
            [
                [
                    (0, 0),
                    (0, 0, 0),
                    (0, 0, 0, 0),
                    (0, 0, 0, 0, 0),
                    (0, 0, 0, 0, 0, 0),
                    (1, 0),
                    (1, 0, 0),
                ]
            ],
        )

    def test_bad_operator(self):
        """
        Test error handling of undefined tgrep operators.
        """
        tree = ParentedTree.fromstring("(S (A (T x)) (B (N x)))")
        self.assertRaises(
            tgrep.TgrepException, list, tgrep.tgrep_positions("* >>> S", [tree])
        )

    def test_comments(self):
        """
        Test that comments are correctly filtered out of tgrep search
        strings.
        """
        tree = ParentedTree.fromstring("(S (NN x) (NP x) (NN x))")
        search1 = """
        @ NP /^NP/;
        @ NN /^NN/;
        @NN
        """
        self.assertEqual(list(tgrep.tgrep_positions(search1, [tree])), [[(0,), (2,)]])
        search2 = """
        # macros
        @ NP /^NP/;
        @ NN /^NN/;

        # search string
        @NN
        """
        self.assertEqual(list(tgrep.tgrep_positions(search2, [tree])), [[(0,), (2,)]])

    def test_rel_sister_nodes(self):
        """
        Test matching sister nodes in a tree.
        """
        tree = ParentedTree.fromstring("(S (A x) (B x) (C x))")
        self.assertEqual(list(tgrep.tgrep_positions("* $. B", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* $.. B", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* $, B", [tree])), [[(2,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* $,, B", [tree])), [[(2,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* $ B", [tree])), [[(0,), (2,)]])

    def tests_rel_indexed_children(self):
        """
        Test matching nodes based on their index in their parent node.
        """
        tree = ParentedTree.fromstring("(S (A x) (B x) (C x))")
        self.assertEqual(list(tgrep.tgrep_positions("* >, S", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* >1 S", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* >2 S", [tree])), [[(1,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* >3 S", [tree])), [[(2,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* >' S", [tree])), [[(2,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* >-1 S", [tree])), [[(2,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* >-2 S", [tree])), [[(1,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* >-3 S", [tree])), [[(0,)]])
        tree = ParentedTree.fromstring(
            "(S (D (A x) (B x) (C x)) (E (B x) (C x) (A x)) " "(F (C x) (A x) (B x)))"
        )
        self.assertEqual(list(tgrep.tgrep_positions("* <, A", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <1 A", [tree])), [[(0,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <2 A", [tree])), [[(2,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <3 A", [tree])), [[(1,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <' A", [tree])), [[(1,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <-1 A", [tree])), [[(1,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <-2 A", [tree])), [[(2,)]])
        self.assertEqual(list(tgrep.tgrep_positions("* <-3 A", [tree])), [[(0,)]])

    def test_rel_precedence(self):
        """
        Test matching nodes based on precedence relations.
        """
        tree = ParentedTree.fromstring(
            "(S (NP (NP (PP x)) (NP (AP x)))"
            " (VP (AP (X (PP x)) (Y (AP x))))"
            " (NP (RC (NP (AP x)))))"
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* . X", [tree])), [[(0,), (0, 1), (0, 1, 0)]]
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* . Y", [tree])), [[(1, 0, 0), (1, 0, 0, 0)]]
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* .. X", [tree])),
            [[(0,), (0, 0), (0, 0, 0), (0, 1), (0, 1, 0)]],
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* .. Y", [tree])),
            [[(0,), (0, 0), (0, 0, 0), (0, 1), (0, 1, 0), (1, 0, 0), (1, 0, 0, 0)]],
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* , X", [tree])), [[(1, 0, 1), (1, 0, 1, 0)]]
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* , Y", [tree])),
            [[(2,), (2, 0), (2, 0, 0), (2, 0, 0, 0)]],
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* ,, X", [tree])),
            [[(1, 0, 1), (1, 0, 1, 0), (2,), (2, 0), (2, 0, 0), (2, 0, 0, 0)]],
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("* ,, Y", [tree])),
            [[(2,), (2, 0), (2, 0, 0), (2, 0, 0, 0)]],
        )

    def test_examples(self):
        """
        Test the Basic Examples from the TGrep2 manual.
        """
        tree = ParentedTree.fromstring("(S (NP (AP x)) (NP (PP x)))")
        # This matches any NP node that immediately dominates a PP:
        self.assertEqual(list(tgrep.tgrep_positions("NP < PP", [tree])), [[(1,)]])

        tree = ParentedTree.fromstring("(S (NP x) (VP x) (NP (PP x)) (VP x))")
        # This matches an NP that dominates a PP and is immediately
        # followed by a VP:
        self.assertEqual(list(tgrep.tgrep_positions("NP << PP . VP", [tree])), [[(2,)]])

        tree = ParentedTree.fromstring(
            "(S (NP (AP x)) (NP (PP x)) " "(NP (DET x) (NN x)) (VP x))"
        )
        # This matches an NP that dominates a PP or is immediately
        # followed by a VP:
        self.assertEqual(
            list(tgrep.tgrep_positions("NP << PP | . VP", [tree])), [[(1,), (2,)]]
        )

        tree = ParentedTree.fromstring(
            "(S (NP (NP (PP x)) (NP (AP x)))"
            " (VP (AP (NP (PP x)) (NP (AP x))))"
            " (NP (RC (NP (AP x)))))"
        )
        # This matches an NP that does not dominate a PP. Also, the NP
        # must either have a parent that is an NP or be dominated by a
        # VP:
        self.assertEqual(
            list(tgrep.tgrep_positions("NP !<< PP [> NP | >> VP]", [tree])),
            [[(0, 1), (1, 0, 1)]],
        )

        tree = ParentedTree.fromstring(
            "(S (NP (AP (PP x) (VP x))) " "(NP (AP (PP x) (NP x))) (NP x))"
        )
        # This matches an NP that dominates a PP which itself is
        # immediately followed by a VP. Note the use of parentheses to
        # group ". VP" with the PP rather than with the NP:
        self.assertEqual(
            list(tgrep.tgrep_positions("NP << (PP . VP)", [tree])), [[(0,)]]
        )

        tree = ParentedTree.fromstring(
            "(S (NP (DET a) (NN cat) (PP (IN on) (NP x)))"
            " (NP (DET a) (NN cat) (PP (IN on) (NP x)) (PP x))"
            " (NP x))"
        )
        # This matches an NP whose last child is a PP that begins with
        # the preposition "on":
        self.assertEqual(
            list(tgrep.tgrep_positions("NP <' (PP <, (IN < on))", [tree])), [[(0,)]]
        )

        tree = ParentedTree.fromstring(
            "(S (S (C x) (A (B x))) (S (C x) (A x)) " "(S (D x) (A (B x))))"
        )
        # The following pattern matches an S which has a child A and
        # another child that is a C and that the A has a child B:
        self.assertEqual(
            list(tgrep.tgrep_positions("S < (A < B) < C", [tree])), [[(0,)]]
        )

        tree = ParentedTree.fromstring(
            "(S (S (A (B x) (C x))) (S (S (C x) (A (B x)))))"
        )
        # However, this pattern means that S has child A and that A
        # has children B and C:
        self.assertEqual(
            list(tgrep.tgrep_positions("S < ((A < B) < C)", [tree])), [[(0,)]]
        )

        # It is equivalent to this:
        self.assertEqual(
            list(tgrep.tgrep_positions("S < (A < B < C)", [tree])), [[(0,)]]
        )

    def test_use_macros(self):
        """
        Test defining and using tgrep2 macros.
        """
        tree = ParentedTree.fromstring(
            "(VP (VB sold) (NP (DET the) "
            "(NN heiress)) (NP (NN deed) (PREP to) "
            "(NP (DET the) (NN school) (NN house))))"
        )
        self.assertEqual(
            list(
                tgrep.tgrep_positions(
                    "@ NP /^NP/;\n@ NN /^NN/;\n@NP !< @NP !$.. @NN", [tree]
                )
            ),
            [[(1,), (2, 2)]],
        )
        # use undefined macro @CNP
        self.assertRaises(
            tgrep.TgrepException,
            list,
            tgrep.tgrep_positions(
                "@ NP /^NP/;\n@ NN /^NN/;\n@CNP !< @NP !$.. @NN", [tree]
            ),
        )

    def test_tokenize_node_labels(self):
        """Test tokenization of labeled nodes."""
        self.assertEqual(
            tgrep.tgrep_tokenize("S < @SBJ < (@VP < (@VB $.. @OBJ))"),
            [
                "S",
                "<",
                "@SBJ",
                "<",
                "(",
                "@VP",
                "<",
                "(",
                "@VB",
                "$..",
                "@OBJ",
                ")",
                ")",
            ],
        )
        self.assertEqual(
            tgrep.tgrep_tokenize("S < @SBJ=s < (@VP=v < (@VB $.. @OBJ))"),
            [
                "S",
                "<",
                "@SBJ",
                "=",
                "s",
                "<",
                "(",
                "@VP",
                "=",
                "v",
                "<",
                "(",
                "@VB",
                "$..",
                "@OBJ",
                ")",
                ")",
            ],
        )

    def test_tokenize_segmented_patterns(self):
        """Test tokenization of segmented patterns."""
        self.assertEqual(
            tgrep.tgrep_tokenize("S < @SBJ=s < (@VP=v < (@VB $.. @OBJ)) : =s .. =v"),
            [
                "S",
                "<",
                "@SBJ",
                "=",
                "s",
                "<",
                "(",
                "@VP",
                "=",
                "v",
                "<",
                "(",
                "@VB",
                "$..",
                "@OBJ",
                ")",
                ")",
                ":",
                "=s",
                "..",
                "=v",
            ],
        )

    def test_labeled_nodes(self):
        """
        Test labeled nodes.

        Test case from Emily M. Bender.
        """
        search = """
            # macros
            @ SBJ /SBJ/;
            @ VP /VP/;
            @ VB /VB/;
            @ VPoB /V[PB]/;
            @ OBJ /OBJ/;

            # 1 svo
            S < @SBJ=s < (@VP=v < (@VB $.. @OBJ)) : =s .. =v"""
        sent1 = ParentedTree.fromstring(
            "(S (NP-SBJ I) (VP (VB eat) (NP-OBJ (NNS apples))))"
        )
        sent2 = ParentedTree.fromstring(
            "(S (VP (VB eat) (NP-OBJ (NNS apples))) (NP-SBJ I))"
        )
        search_firsthalf = search.split("\n\n")[0] + "S < @SBJ < (@VP < (@VB $.. @OBJ))"
        search_rewrite = "S < (/.*SBJ/ $.. (/VP/ < (/VB/ $.. /.*OBJ/)))"

        self.assertTrue(list(tgrep.tgrep_positions(search_firsthalf, [sent1]))[0])
        self.assertTrue(list(tgrep.tgrep_positions(search, [sent1]))[0])
        self.assertTrue(list(tgrep.tgrep_positions(search_rewrite, [sent1]))[0])
        self.assertEqual(
            list(tgrep.tgrep_positions(search, [sent1])),
            list(tgrep.tgrep_positions(search_rewrite, [sent1])),
        )
        self.assertTrue(list(tgrep.tgrep_positions(search_firsthalf, [sent2]))[0])
        self.assertFalse(list(tgrep.tgrep_positions(search, [sent2]))[0])
        self.assertFalse(list(tgrep.tgrep_positions(search_rewrite, [sent2]))[0])
        self.assertEqual(
            list(tgrep.tgrep_positions(search, [sent2])),
            list(tgrep.tgrep_positions(search_rewrite, [sent2])),
        )

    def test_multiple_conjs(self):
        """
        Test that multiple (3 or more) conjunctions of node relations are
        handled properly.
        """
        sent = ParentedTree.fromstring("((A (B b) (C c)) (A (B b) (C c) (D d)))")
        # search = '(A < B < C < D)'
        # search_tworels = '(A < B < C)'
        self.assertEqual(
            list(tgrep.tgrep_positions("(A < B < C < D)", [sent])), [[(1,)]]
        )
        self.assertEqual(
            list(tgrep.tgrep_positions("(A < B < C)", [sent])), [[(0,), (1,)]]
        )

    def test_trailing_semicolon(self):
        """
        Test that semicolons at the end of a tgrep2 search string won't
        cause a parse failure.
        """
        tree = ParentedTree.fromstring(
            "(S (NP (DT the) (JJ big) (NN dog)) " "(VP bit) (NP (DT a) (NN cat)))"
        )
        self.assertEqual(list(tgrep.tgrep_positions("NN", [tree])), [[(0, 2), (2, 1)]])
        self.assertEqual(list(tgrep.tgrep_positions("NN;", [tree])), [[(0, 2), (2, 1)]])
        self.assertEqual(
            list(tgrep.tgrep_positions("NN;;", [tree])), [[(0, 2), (2, 1)]]
        )