Identification of implicit element as a search problem

example1.svg

example2.svg

example3.svg

patternTreeLeafs.py

#!/usr/bin/env python
#-*- coding:utf-8 -*-


# author: Filipe Funenga
# date: 8 Jul 2013


# Basic Elements in a CLI specification. Just skip ahead.

class Leaf:
    def __init__(self, name, value):
        self.name = name
        self.value = value
    def __repr__(self):
        return '%s("%s", %s)' % (
                self.__class__.__name__, self.name, self.value)

class Command(Leaf):
    def __repr__(self):
        return self.name

class Argument(Leaf):
    def __repr__(self):
        return self.name

class Option(Leaf):
    def __repr__(self):
        return self.name

class Branch:
    def __init__(self, children):
        self.children = children
    def __repr__(self):
        return '%s(%s)' % (self.__class__.__name__, str(self.children))

class Required(Branch):
    def __repr__(self):
        return '(%s)' % ' '.join([str(c) for c in self.children])

class Optional(Branch):
    def __repr__(self):
        return '[%s]' % ' '.join([str(c) for c in self.children])

class Either(Branch):
    def __repr__(self):
        return ' | '.join([str(c) for c in self.children])

class OneOrMore(Branch):
    def __repr__(self):
        return ' '.join([str(c) for c in self.children]) + '...'


# Search Tree Node

class Node:
    def __init__(self, pattern):
        assert isinstance(pattern, Required)
        self.key = ''.join([('w' if isinstance(elem, Command) or
                                    isinstance(elem, Argument) else
                             'o' if isinstance(elem, Option) else '')
                            for elem in pattern.children])
        self.pattern = pattern
        self.children = self.__get_children()

    def __get_children(self):
        for child in self.pattern.children:
            if isinstance(child, Branch):
                children = []
                if isinstance(child, Required):
                    __temp = [([c] if c is not child else child.children)
                              for c in self.pattern.children]
                    children.append(Required([i for l in __temp for i in l]))
                elif isinstance(child, Optional):
                    children.append(Required([c for c in self.pattern.children
                                                if c is not child]))
                    __temp = [([c] if c is not child else child.children)
                              for c in self.pattern.children]
                    children.append(Required([i for l in __temp for i in l]))
                elif isinstance(child, Either):
                    for elem in child.children:
                        __temp = [([c] if c is not elem else elem.children)
                                  for c in self.pattern.children]
                        children.append(Required([i for l in __temp for i in l]))
                elif isinstance(child, OneOrMore):
                    print child
                return children
        return []

    def __repr__(self):
        return str(self.pattern)


# Main function

def main():
    # Define the CLI pattern here. This structure is usually retrieved from the
    # CLI specification (known as docopt string). Some examples are provided
    # bellow.
    def pattern1():  # Usage: ./prog [<file>] update
        argv1 = Optional([Argument('<file>', None)])
        argv2 = Command('update', None)
        return Required([argv1, argv2])
    def pattern2():  # Usage: ./prog [<file> [<template>]] update
        argv1 = Optional([Argument('<file>', None),
                          Optional([Argument('<template>', None)])])
        argv2 = Command('update', None)
        return Required([argv1, argv2])
    def pattern3():  # Usage: ./prog [<file>] update [<template>]
        argv1 = Optional([Argument('<file>', None)])
        argv2 = Command('update', None)
        argv3 = Optional([Argument('<template>', None)])
        return Required([argv1, argv2, argv3])
    argv = pattern1()  # change this function to try other patterns
    print 'argv:', argv

    # Search pattern tree (either using DFS or BFS) and collects leaf nodes.
    # These new leaf nodes need to checked if they are ambiguous: if the
    # pattern of skipped options (i.e. only commands and arguments) is not
    # unique, then the CLI pattern is ambiguous.
    print '---', 'tree search:', 'DFS'
    search = {'DFS': -1, 'BFS': 0}['DFS']
    idx = 0
    leafs = {}
    queue = [argv]
    while queue:
        node = queue.pop(search)
        print 'idx: %d,' % idx, 'node:', node
        idx += 1
        node = Node(node)
        if len(node.children):
            queue.extend(node.children)
        else:
            if not leafs.has_key(node.key):
                leafs[node.key] = node.pattern
            else:
                exit('Ambiguous pattern in "%s" vs "%s"' % (
                        str(leafs[node.key]), str(node.pattern)))

    # Use collected leafs to make something. In this case, it just prints out
    # the pattern.
    print '---'
    print 'leafs:'
    for k,v in leafs.iteritems():
        print '  ', k, v


if __name__ == "__main__":
    main()