1

     2

"""

     3

    Parsing trees of node stored using a python-like syntax.

     4

     5

    A file consists of a number of lines, and each line consists of indenting whitespace and data. Each line has a parent

     6

"""

     7

    15

def _read_lines (path, stop_tokens='') :

    16

    """

    17

        Reads lines from the given path, ignoring empty lines, and yielding (line_number, indent, line) tuples, where 

    18

        line_number is the line number, indent counts the amount of leading whitespace, and line is the actual line

    19

        data with whitespace stripped.

    20

    21

        Stop tokens is a list of chars to stop counting indentation on - if such a line begins with such a char, its

    22

        indentation is taken as zero.

    23

    """

    24

    25

    for line_number, line in enumerate(open(path, 'rb')) :

    26

        indent = 0

    27

    28

        # count indent

    29

        for char in line :

    30

            # tabs break things

    31

            assert char != '\t'

    32

    33

            # increment up to first non-space char

    34

            if char == ' ' :

    35

                indent += 1

    36

    37

            elif char in stop_tokens :

    38

                # consider line as not having any indentation at all

    39

                indent = 0

    40

                break

    41

    42

            else :

    43

                break

    44

    45

        # strip whitespace

    46

        line = line.strip()

    47

    48

        # ignore empty lines

    49

        if not line :

    50

            continue

    51

    52

        # yield

    53

        yield line_number + 1, indent, line

    54

    55

def parse (path, stop_tokens='') :

    56

    """

    57

        Reads and parses the file at the given path, returning a list of (line_number, line, children) tuples.

    58

    """

    59

    60

    # stack of (indent, PageInfo) items

    61

    stack = []

    62

    63

    # the root item

    64

    root = None

    65

    66

    # the previous item processed, None for first one

    67

    prev = None

    68

    69

    # read lines

    70

    for line_number, indent, line in _read_lines(path, stop_tokens) :

    71

        # create item

    72

        item = (line_number, line, [])

    73

    74

        # are we the first item?

    75

        if not prev :

    76

            # root node does not have a parent

    77

            parent = None

    78

    79

            # set root

    80

            root = item

    81

    82

            # initialize stack

    83

            stack.append((0, root))

    84

    85

        else :

    86

            # peek stack

    87

            stack_indent, stack_parent = stack[-1]

    88

    89

            # new indent level?

    90

            if indent > stack_indent :

    91

                # set parent to previous item, and push new indent level + parent to stack

    92

                parent = prev

    93

    94

                # push new indent level + its parent

    95

                stack.append((indent, parent))

    96

    97

            # same indent level as previous

    98

            elif indent == stack_indent :

    99

                # parent is the one of the current stack level, stack doesn't change

   100

                parent = stack_parent

   101

   102

            # unravel stack

   103

            elif indent < stack_indent :

   104

                while True :

   105

                    # remove current stack level

   106

                    stack.pop(-1)

   107

   108

                    # peek next level

   109

                    stack_indent, stack_parent = stack[-1]

   110

   111

                    # found the level to return to?

   112

                    if stack_indent == indent :

   113

                        # restore prev

   114

                        parent = stack_parent

   115

   116

                        break

   117

   118

                    elif stack_indent < indent :

   120

   121

        # add to parent?

   122

        if parent :

   123

            parent[2].append(item)

   124

   125

        # update prev

   126

        prev = item

   127

   128

    # return the root

   129

    return root

   130