# dagparser.py - parser and generator for concise description of DAGs

#

# Copyright 2010 Peter Arrenbrecht <peter@arrenbrecht.ch>

#

# This software may be used and distributed according to the terms of the

# GNU General Public License version 2 or any later version.

def parsedag(desc):

    '''parses a DAG from a concise textual description; generates events

    "+n" is a linear run of n nodes based on the current default parent

    "." is a single node based on the current default parent

    "$" resets the default parent to -1 (implied at the start);

        otherwise the default parent is always the last node created

    "<p" sets the default parent to the backref p

    "*p" is a fork at parent p, where p is a backref

    "*p1/p2/.../pn" is a merge of parents p1..pn, where the pi are backrefs

    "/p2/.../pn" is a merge of the preceding node and p2..pn

    ":name" defines a label for the preceding node; labels can be redefined

    "@text" emits an annotation event for text

    "!command" emits an action event for the current node

    "!!my command\n" is like "!", but to the end of the line

    "#...\n" is a comment up to the end of the line

    Whitespace between the above elements is ignored.

    A backref is either

     * a number n, which references the node curr-n, where curr is the current

       node, or

     * the name of a label you placed earlier using ":name", or

     * empty to denote the default parent.

    All string valued-elements are either strictly alphanumeric, or must

    be enclosed in double quotes ("..."), with "\" as escape character.

    Generates sequence of

      ('n', (id, [parentids])) for node creation

      ('l', (id, labelname)) for labels on nodes

      ('a', text) for annotations

      ('c', command) for actions (!)

      ('C', command) for line actions (!!)

    Examples

    --------

    Example of a complex graph (output not shown for brevity):

        >>> len(list(parsedag("""

        ...

        ... +3         # 3 nodes in linear run

        ... :forkhere  # a label for the last of the 3 nodes from above

        ... +5         # 5 more nodes on one branch

        ... :mergethis # label again

        ... <forkhere  # set default parent to labeled fork node

        ... +10        # 10 more nodes on a parallel branch

        ... @stable    # following nodes will be annotated as "stable"

        ... +5         # 5 nodes in stable

        ... !addfile   # custom command; could trigger new file in next node

        ... +2         # two more nodes

        ... /mergethis # merge last node with labeled node

        ... +4         # 4 more nodes descending from merge node

        ...

        ... """)))

        34

    Empty list:

        >>> list(parsedag(""))

        []

    A simple linear run:

        >>> list(parsedag("+3"))

        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))]

    Some non-standard ways to define such runs:

        >>> list(parsedag("+1+2"))

        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))]

        >>> list(parsedag("+1*1*"))

        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))]

        >>> list(parsedag("*"))

        [('n', (0, [-1]))]

        >>> list(parsedag("..."))

        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [1]))]

    A fork and a join, using numeric back references:

        >>> list(parsedag("+2*2*/2"))

        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), ('n', (3, [2, 1]))]

        >>> list(parsedag("+2<2+1/2"))

        [('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])), ('n', (3, [2, 1]))]

    Placing a label:

        >>> list(parsedag("+1 :mylabel +1"))

        [('n', (0, [-1])), ('l', (0, 'mylabel')), ('n', (1, [0]))]

    An empty label (silly, really):

        >>> list(parsedag("+1:+1"))

        [('n', (0, [-1])), ('l', (0, '')), ('n', (1, [0]))]

    Fork and join, but with labels instead of numeric back references:

        >>> list(parsedag("+1:f +1:p2 *f */p2"))

        [('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), ('l', (1, 'p2')),

         ('n', (2, [0])), ('n', (3, [2, 1]))]

        >>> list(parsedag("+1:f +1:p2 <f +1 /p2"))

        [('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])), ('l', (1, 'p2')),

         ('n', (2, [0])), ('n', (3, [2, 1]))]

    Restarting from the root:

        >>> list(parsedag("+1 $ +1"))

        [('n', (0, [-1])), ('n', (1, [-1]))]

    Annotations, which are meant to introduce sticky state for subsequent nodes:

        >>> list(parsedag("+1 @ann +1"))

        [('n', (0, [-1])), ('a', 'ann'), ('n', (1, [0]))]

        >>> list(parsedag('+1 @"my annotation" +1'))

        [('n', (0, [-1])), ('a', 'my annotation'), ('n', (1, [0]))]

    Commands, which are meant to operate on the most recently created node:

        >>> list(parsedag("+1 !cmd +1"))

        [('n', (0, [-1])), ('c', 'cmd'), ('n', (1, [0]))]

        >>> list(parsedag('+1 !"my command" +1'))

        [('n', (0, [-1])), ('c', 'my command'), ('n', (1, [0]))]

        >>> list(parsedag('+1 !!my command line\\n +1'))

        [('n', (0, [-1])), ('C', 'my command line'), ('n', (1, [0]))]

    Comments, which extend to the end of the line:

        >>> list(parsedag('+1 # comment\\n+1'))

        [('n', (0, [-1])), ('n', (1, [0]))]

    Error:

        >>> try: list(parsedag('+1 bad'))

        ... except Exception, e: print e

        invalid character in dag description: bad...

    '''

    if not desc:

        return

    wordchars = string.ascii_letters + string.digits

    labels = {}

    p1 = -1

    r = 0

    def resolve(ref):

        if not ref:

            return p1

        elif ref[0] in string.digits:

            return r - int(ref)

        else:

            return labels[ref]

    chiter = (c for c in desc)

    def nextch():

        return next(chiter, '\0')

    def nextrun(c, allow):

        s = ''

        while c in allow:

            s += c

            c = nextch()

        return c, s

    def nextdelimited(c, limit, escape):

        s = ''

        while c != limit:

            if c == escape:

                c = nextch()

            s += c

            c = nextch()

        return nextch(), s

    def nextstring(c):

        if c == '"':

            return nextdelimited(nextch(), '"', '\\')

        else:

            return nextrun(c, wordchars)

    c = nextch()

    while c != '\0':

        while c in string.whitespace:

            c = nextch()

        if c == '.':

            yield 'n', (r, [p1])

            p1 = r

            r += 1

            c = nextch()

        elif c == '+':

            c, digs = nextrun(nextch(), string.digits)

            n = int(digs)

            for i in xrange(0, n):

                yield 'n', (r, [p1])

                p1 = r

                r += 1

        elif c in '*/':

            if c == '*':

                c = nextch()

            c, pref = nextstring(c)

            prefs = [pref]

            while c == '/':

                c, pref = nextstring(nextch())

                prefs.append(pref)

            ps = [resolve(ref) for ref in prefs]

            yield 'n', (r, ps)

            p1 = r

            r += 1

        elif c == '<':

            c, ref = nextstring(nextch())

            p1 = resolve(ref)

        elif c == ':':

            c, name = nextstring(nextch())

            labels[name] = p1

            yield 'l', (p1, name)

        elif c == '@':

            c, text = nextstring(nextch())

            yield 'a', text

        elif c == '!':

            c = nextch()

            if c == '!':

                cmd = ''

                c = nextch()

                while c not in '\n\r\0':

                    cmd += c

                    c = nextch()

                yield 'C', cmd

            else:

                c, cmd = nextstring(c)

                yield 'c', cmd

        elif c == '#':

            while c not in '\n\r\0':

                c = nextch()

        elif c == '$':

            p1 = -1

            c = nextch()

        elif c == '\0':

            return # in case it was preceded by whitespace

        else:

            s = ''

            i = 0

            while c != '\0' and i < 10:

                s += c

                i += 1

                c = nextch()

            raise util.Abort(_('invalid character in dag description: '

                               '%s...') % s)

def dagtextlines(events,

                 addspaces=True,

                 wraplabels=False,

                 wrapannotations=False,

                 wrapcommands=False,

                 wrapnonlinear=False,

                 usedots=False,

                 maxlinewidth=70):

    '''generates single lines for dagtext()'''

    def wrapstring(text):

        if re.match("^[0-9a-z]*$", text):

            return text

        return '"' + text.replace('\\', '\\\\').replace('"', '\"') + '"'

    def gen():

        labels = {}

        run = 0

        wantr = 0

        needroot = False

        for kind, data in events:

            if kind == 'n':

                r, ps = data

                # sanity check

                if r != wantr:

                    raise util.Abort(_("expected id %i, got %i") % (wantr, r))

                if not ps:

                    ps = [-1]

                else:

                    for p in ps:

                        if p >= r:

                            raise util.Abort(_("parent id %i is larger than "

                                               "current id %i") % (p, r))

                wantr += 1

                # new root?

                p1 = r - 1

                if len(ps) == 1 and ps[0] == -1:

                    if needroot:

                        if run:

                            yield '+' + str(run)

                            run = 0

                        if wrapnonlinear:

                            yield '\n'

                        yield '$'

                        p1 = -1

                    else:

                        needroot = True

                if len(ps) == 1 and ps[0] == p1:

                    if usedots:

                        yield "."

                    else:

                        run += 1

                else:

                    if run:

                        yield '+' + str(run)

                        run = 0

                    if wrapnonlinear:

                        yield '\n'

                    prefs = []

                    for p in ps:

                        if p == p1:

                            prefs.append('')

                        elif p in labels:

                            prefs.append(labels[p])

                        else:

                            prefs.append(str(r - p))

                    yield '*' + '/'.join(prefs)

            else:

                if run:

                    yield '+' + str(run)

                    run = 0

                if kind == 'l':

                    rid, name = data

                    labels[rid] = name

                    yield ':' + name

                    if wraplabels:

                        yield '\n'

                elif kind == 'c':

                    yield '!' + wrapstring(data)

                    if wrapcommands:

                        yield '\n'

                elif kind == 'C':

                    yield '!!' + data

                    yield '\n'

                elif kind == 'a':

                    if wrapannotations:

                        yield '\n'

                    yield '@' + wrapstring(data)

                elif kind == '#':

                    yield '#' + data

                    yield '\n'

                else:

                    raise util.Abort(_("invalid event type in dag: %s")

                                     % str((type, data)))

        if run:

            yield '+' + str(run)

    line = ''

    for part in gen():

        if part == '\n':

            if line:

                yield line

                line = ''

        else:

            if len(line) + len(part) >= maxlinewidth:

                yield line

                line = ''

            elif addspaces and line and part != '.':

                line += ' '

            line += part

    if line:

        yield line

def dagtext(dag,

            addspaces=True,

            wraplabels=False,

            wrapannotations=False,

            wrapcommands=False,

            wrapnonlinear=False,

            usedots=False,

            maxlinewidth=70):

    '''generates lines of a textual representation for a dag event stream

    events should generate what parsedag() does, so:

      ('n', (id, [parentids])) for node creation

      ('l', (id, labelname)) for labels on nodes

      ('a', text) for annotations

      ('c', text) for commands

      ('C', text) for line commands ('!!')

      ('#', text) for comment lines

    Parent nodes must come before child nodes.

    Examples

    --------

    Linear run:

        >>> dagtext([('n', (0, [-1])), ('n', (1, [0]))])

        '+2'

    Two roots:

        >>> dagtext([('n', (0, [-1])), ('n', (1, [-1]))])

        '+1 $ +1'

    Fork and join:

        >>> dagtext([('n', (0, [-1])), ('n', (1, [0])), ('n', (2, [0])),

        ...          ('n', (3, [2, 1]))])

        '+2 *2 */2'

    Fork and join with labels:

        >>> dagtext([('n', (0, [-1])), ('l', (0, 'f')), ('n', (1, [0])),

        ...          ('l', (1, 'p2')), ('n', (2, [0])), ('n', (3, [2, 1]))])

        '+1 :f +1 :p2 *f */p2'

    Annotations:

        >>> dagtext([('n', (0, [-1])), ('a', 'ann'), ('n', (1, [0]))])

        '+1 @ann +1'

        >>> dagtext([('n', (0, [-1])),

        ...          ('a', 'my annotation'),