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

     8

class TreeParseError (Exception) :

     9

    """

    10

        Error parsing a tree file

    11

    """

    12

    13

    pass

    14

    15

def _read_lines (file, stop_tokens=None, charset='utf8') :

    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

        File is either a str with the filesystem path, or a something that supports iterating over lines. 

    22

    23

        Charset is what to decode the lines with, or pass None to not decode.

    24

    25

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

    26

        indentation is taken as zero. Ignored if empty.

    27

    """

    28

    29

    # open path?

    30

    if isinstance(file, str) :

    31

        file = open(file, 'rb')

    32

    33

    # iterate over lines

    34

    for line_number, line in enumerate(file) :

    35

        if charset :

    36

            # decode to unicode

    37

            line = line.decode(charset)

    38

    39

        indent = 0

    40

    41

        # count indent

    42

        for char in line :

    43

            # tabs break things

    44

            assert char != '\t'

    45

    46

            # increment up to first non-space char

    47

            if char == ' ' :

    48

                indent += 1

    49

    50

            elif stop_tokens and char in stop_tokens :

    51

                # consider line as not having any indentation at all

    52

                indent = 0

    53

                break

    54

    55

            else :

    56

                break

    57

    58

        # strip whitespace

    59

        line = line.strip()

    60

    61

        # ignore empty lines

    62

        if not line :

    63

            continue

    64

    65

        # yield

    66

        yield line_number + 1, indent, line

    67

    68

def parse (file, stop_tokens='', charset='utf8') :

    69

    """

    70

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

    71

    """

    72

    73

    # stack of (indent, PageInfo) items

    74

    stack = []

    75

    76

    # the root item

    77

    root = None

    78

    79

    # the previous item processed, None for first one

    80

    prev = None

    81

    82

    # read lines

    83

    for line_number, indent, line in _read_lines(file, stop_tokens, charset) :

    84

        # create item

    85

        item = (line_number, line, [])

    86

    87

        # are we the first item?

    88

        if not prev :

    89

            # root node does not have a parent

    90

            parent = None

    91

    92

            # set root

    93

            root = item

    94

    95

            # initialize stack

    96

            stack.append((0, root))

    97

    98

        else :

    99

            # peek stack

   100

            stack_indent, stack_parent = stack[-1]

   101

   102

            # new indent level?

   103

            if indent > stack_indent :

   104

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

   105

                parent = prev

   106

   107

                # push new indent level + its parent

   108

                stack.append((indent, parent))

   109

   110

            # same indent level as previous

   111

            elif indent == stack_indent :

   112

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

   113

                parent = stack_parent

   114

   115

            # unravel stack

   116

            elif indent < stack_indent :

   117

                while True :

   118

                    # remove current stack level

   119

                    stack.pop(-1)

   120

   121

                    # peek next level

   122

                    stack_indent, stack_parent = stack[-1]

   123

   124

                    # found the level to return to?

   125

                    if stack_indent == indent :

   126

                        # restore prev

   127

                        parent = stack_parent

   128

   129

                        break

   130

   131

                    elif stack_indent < indent :

   132

                        raise TreeParseError("Bad unindent on %s:%d, %d < %d" % (file, line_number, stack_indent, indent))

   133

   134

        # add to parent?

   135

        if parent :

   136

            parent[2].append(item)

   137

   138

        # update prev

   139

        prev = item

   140

   141

    # return the root

   142

    return root

   143