#############################################################################
# Copyright (C) DSTC Pty Ltd (ACN 052 372 577) 1993, 1994, 1995.
# Unpublished work.  All Rights Reserved.
#
# The software contained on this media is the property of the
# DSTC Pty Ltd.  Use of this software is strictly in accordance
# with the license agreement in the accompanying LICENSE.DOC file.
# If your distribution of this software does not contain a
# LICENSE.DOC file then you have no rights to use this software
# in any manner and should contact DSTC at the address below
# to determine an appropriate licensing arrangement.
# 
#      DSTC Pty Ltd
#      Level 7, Gehrmann Labs
#      University of Queensland
#      St Lucia, 4072
#      Australia
#      Tel: +61 7 3365 4310
#      Fax: +61 7 3365 4311
#      Email: enquiries@dstc.edu.au
# 
# This software is being provided "AS IS" without warranty of
# any kind.  In no event shall DSTC Pty Ltd be liable for
# damage of any kind arising out of or in connection with
# the use or performance of this software.
#
# Project:  Python Tools
#
# File:     ast.py
#
# Description:
#           Functions to traverse and inspect Python ASTs.
#
# History:
#           19-Dec-1995  Martin Chilvers (martin) : created
#
# "@(#)$RCSfile: ast.py,v $ $Revision: 1 $"
#
#$Log: /Gendoc/ast.py $
# 
# 1     98-04-01 13:15 Daniel
# Revision 1.2  1996/07/08  05:34:28  omfadmin
# Incorporated Fred Drake's changes (Python 1.4 support).
#
# Revision 1.1  1996/06/13  17:57:56  omfadmin
# Initial revision
#
#Revision 1.4  1995/12/19 01:43:40  martin
#Added DSTC header.
#
#
#############################################################################

""" Functions to traverse and inspect Python abstract syntax trees (ASTs). 

The ASTs must be in tuple form as produced by the function 'ast2tuple' in the
parser module.

The functions intended for public consumption are:-

    'map_fn'        map a function to every node in an AST.
    'search'        search an AST for nodes of particular types.
    'match'         compare two ASTs using some simple pattern matching.
    'terminals'     return a list of all terminals in an AST.
    'nonterminals'  return a list of all non-terminals in an AST.
    'str'           return a string that is the concatenation of all the
                    terminals in an AST.
    'node_type'     return the type of an AST node.
    'node_body'     return the body of an AST node (ie. the node minus its
                    type).

All other functions are intended for private use only (but you can use them
if you *really* want to ;^)

"""

# Built-in/standard modules.
import types
import string

# Local modules.
import token
import symbol


# Prefix to identify pattern matching variables.
AST_PATTERN = '$$$$'


def map_fn(node, fn):
    """ Map a function to every node in an AST (depth-first).

        'node'  is the root of the AST.
        'fn'    is the function to map to every node.

    """

    if len(node) > 0:
	apply(fn, (node,))

	if token.ISNONTERMINAL(node_type(node)):
	    for child in node_body(node):
		map_fn(child, fn)

    return


def search(node, lst_tokens, lst_found, n = 0):
    """ Search an AST for nodes of particular types.

    'node'        is the root of the AST.
    'lst_tokens'  is the list of tokens to search for eg:-
                  [token.INDENT, token.DEDENT, symbol.fpdef]
    'lst_found'   is the list of matching nodes (output).
    'n'           is the number of nodes to match. If 'n' is zero (the
                  default) then ALL matching nodes are listed.

    Returns (a reference to) the list of matching nodes.
    
    """

    if len(node) > 0:
	if node_type(node) in lst_tokens:
	    lst_found.append(node)

	if token.ISNONTERMINAL(node_type(node)):
	    for child in node_body(node):
		search(child, lst_tokens, lst_found, n)
		if n != 0 and len(lst_found) >= n:
		    break

    return lst_found


def match(x, y, d_matches):
    """ Compare two ASTs using some simple(!!) pattern matching.

    'x'          is the AST to match (cannot contain patterns!).
    'y'          is the AST to match WITH (CAN contain patterns!).
    'd_matches'  is the dictionary of matched patterns (output).

    Returns true if the ASTs match, otherwise false.

    Patterns are specified in 'y' as strings prefixed with 'AST_PATTERN' (eg.
    my_pattern = AST_PATTERN + 'FOOBAR'). If a pattern match is found then the
    element of 'x' that matches the pattern is added to the dictionary
    'd_matches' with 'my_pattern' as the key. Terminals can be matched on both
    their type AND their value, whereas non-terminals can only be matched at
    the node level.

    eg. 1

    (token.STRING, 'Value') matches (AST_PATTERN + 'Type', AST_PATTERN + 'Doc')

    where d_matches[AST_PATTERN + 'Type'] = token.STRING
    and   d_matches[AST_PATTERN + 'Doc']  = 'Value'

    eg. 2

    (symbol.fpdef, ..rest of node..) matches (AST_PATTERN + 'ANode')

    where d_matches[AST_PATTERN + 'Anode'] = (symbol.fpdef, ..rest of node..)

    """

    if len(x) > 0:
	if token.ISTERMINAL(node_type(x)):
	    result = match_terminal(x, y, d_matches)

	else:
	    result = match_nonterminal(x, y, d_matches)

    else:
	result = len(y) == 0

    return result


def terminals(node, lst_found):
    """ Return a list of all terminals in an AST.

    'node'       is the root of the AST.
    'lst_found'  is the list of all terminals in the AST (output).

    Returns (a reference to) the list of terminals found.

    """

    if len(node) > 0:
	if token.ISTERMINAL(node_type(node)):
	    lst_found.append(node)
	else:
	    for child in node_body(node):
		terminals(child, lst_found)

    return lst_found


def nonterminals(node, lst_found):
    """ Return a list of all non-terminals in an AST.

    'node'       is the root of the AST.
    'lst_found'  is the list of all non-terminals in the AST (output).

    Returns (a reference to) the list of terminals found.

    """

    if len(node) > 0:
	if token.ISNONTERMINAL(node_type(node)):
	    lst_found.append(node)

	    for child in node_body(node):
		nonterminals(child, lst_found)

    return lst_found


def str(node, sep = ''):
    """ Return the string concatenation of all the terminals in an AST.

    'node'  is root of the AST.
    'sep'   is the string used to separate each terminal.

    Returns a string containing all of the terminals separated by 'sep'.

    """

    lst_terminals = terminals(node, [])
    return string.joinfields(map(lambda (a, b): b, lst_terminals), sep)


def node_type(node):
    """ Returns the type of an AST node (ie. its token/symbol value). """

    return node[0]


def node_body(node):
    """ Returns the body of an AST node (ie. the node minus its type!). """

    return node[1:]


def is_pattern(x):
    """ Determine whether or not an item is a pattern matching variable. """

    return type(x) == types.StringType and x[:len(AST_PATTERN)] == AST_PATTERN


def match_item(x, y, d_matches):
    """ Compare two node items using some simple pattern matching! """

    if is_pattern(y):
	d_matches[y] = x
	result = 1

    else:
	result = x == y

    return result


def match_terminal((x_type, x_value), (y_type, y_value), d_matches):
    """ Compare two terminals. """

    return (match_item(x_type, y_type, d_matches)
	    and match_item(x_value, y_value, d_matches))


def match_nonterminal(x, y, d_matches):
    """ Compare two nonterminals. """

    result = (match_item(x, y, d_matches)
	      or match_item(node_type(x), node_type(y), d_matches))

    if result:
	for i in range (len(node_body(x))):
	    result = match(node_body(x)[i],
			   node_body(y)[i], d_matches)
	    if not result:
		break

    return result