<commit_before># Natural Language Toolkit: Feature Structures
#
# Copyright (C) 2003 University of Pennsylvania
# Author: <NAME> <<EMAIL>>,
#         <NAME> (original code)
# URL: <http://nltk.sourceforge.net>
# For license information, see LICENSE.TXT
#
# $Id$


"""
Basic data classes for representing feature structures.  A X{feature
structure} is a mapping from feature names to feature values, where:

  - Each X{feature name} is a case sensitive string.
  - Each X{feature value} can be a base value (such as a string), a
    variable, or a nested feature structure.

Feature structures are typically used to represent partial information
about objects.  A feature name that is not mapped to a value stands
for a feature whose value is unknown (I{not} a feature without a
value).  Two feature structures that represent (potentially
overlapping) information about the same object can be combined by
X{unification}.  When two inconsistant feature structures are unified,
the unification fails and returns C{None}.

Features are usually specified using X{feature paths}, or tuples of
feature names that specify path through the nested feature structures
to a value.

Feature structures may contain reentrant feature values.  A
X{reentrant feature value} is a single feature value that can be
accessed via multiple feature paths.  Unification preserves the
reentrance relations imposed by both of the unified feature
structures.  After unification, any extensions to a reentrant feature
value will be visible using any of its feature paths.

Feature structure variables are encoded using the
L{FeatureVariable} class.  Feature structure variables are
essentially just names; they do not directly contain values.  Instead,
the mapping from variables to values is encoded externally to the
variable, as a set of X{bindings}.  These bindings are stored using
the L{FeatureBindings} class.

@todo: more test cases
@sort: FeatureStructure, FeatureVariable, AliasedFeatureVariable,
       FeatureBindings
@group Feature Structures: FeatureStructure
@group Variables: FeatureVariable, AliasedFeatureVariable,
                  FeatureBindings
@group Unit Tests: FeatureStructureTestCase
"""

# Open question: should there be a "feature" object?
#
# The current implementation doesn't actually include an object to
# encode a "feature" (i.e., a name/value pair).  This makes the code
# simpler -- one less class to deal with, and you can directly query
# for feature values, rather than going through a feature object.  But
# there might be use cases for adding a Feature object.  E.g., if we
# wanted to assign properties (like is_required) to features.  But I'd
# like to see some compelling use cases before we add it.

import re
from nltk.chktype import chktype as _chktype
from types import NoneType

#//////////////////////////////////////////////////////////////////////
# Variables and variable bindings
#//////////////////////////////////////////////////////////////////////

class FeatureVariable:
    """
    A variable that can stand for a single feature value in a feature
    structure.  Each variable is defined by a unique identifier, which
    can be either a case-sensitive string (for X{named variables}) or
    an integer (for X{numbered variables}).

    Named variables are created by calling the C{FeatureVariable}
    constructor with a string identifier.  If multiple named variables
    objects are created with the same identifier, then they represent
    the same variable.  Numbered variables are created by calling the
    C{FeatureVariable} constructor with no arguments; a new identifier
    will be automatically generated.  Each new numbered variable object
    is guaranteed to have a unique identifier.

    Variables do not directly contain values; instead, the mapping
    from variables to values is encoded externally as a set of
    bindings, using L{FeatureBindings}.  If a set of
    bindings assigns a value to a variable, then that variable is said
    to be X{bound} with respect to those bindings; otherwise, it is
    said to be X{unbound}.

    @see: L{FeatureStructure}
    """
    _next_numbered_id = 1
    
    def __init__(self, identifier=None):
        """
        Construct a new feature structure variable.
        @type identifier: C{string}
        @param identifier: A unique identifier for this variable.
            Any two C{FeatureVariable} objects with the
            same identifier are treated as the same variable.
        """
        assert _chktype(1, identifier, str, NoneType)
        if identifier is None:
            self._identifier = FeatureVariable._next_numbered_id
            FeatureVariable._next_numbered_id += 1
        else:
            self._identifier = identifier

    def identifier(self):
        """
        @return: This variable's unique identifier.
        @rtype: C{string}
        """
        return self._identifier

    def __repr__(self):
        """
        @return: A string representation of this feature structure
           variable.  A feature structure variable with identifier
           C{I{x}} is represented as C{'?I{x}'}.
        """
        return '?%s' % self._identifier

    def __cmp__(self, other):
        if not isinstance(other, FeatureVariable): return -1
        return cmp(self._identifier, other._identifier)

    def __hash__(self):
        return self._identifier.__hash__()

    def alias(self, variable):
        """
        Return an aliased variable that constrains this variable to be
        equal to C{variable}.
        @rtype: L{AliasedFeatureVariable}
        """
        if self == variable: return self
        return AliasedFeatureVariable(self, variable)

    def parse(s):
        """
        Given a string that encodes a feature variable, return that
        variable.  This method can be used to parse both
        C{FeatureVariables} and C{AliasedFeatureVariables}.  However,
        this method can not be used to parse numbered variables, since
        doing so could violate the guarantee that each numbered
        variable object has a unique identifier.
        """
        # Simple variable
        match = re.match(r'\?[a-zA-Z_][a-zA-Z0-9_]*$', s)
        if match:
            return FeatureVariable(s[1:])

        # Aliased variable
        match = re.match(r'\?<[a-zA-Z_][a-zA-Z0-9_]*'+
                         r'(=[a-zA-Z_][a-zA-Z0-9_]*)*>$', s)
        if match:
            idents = s[2:-1].split('=')
            vars = [FeatureVariable(i) for i in idents]
            return AliasedFeatureVariable(*vars)

        raise ValueError('Bad FeatureVariable string')
    
    parse=staticmethod(parse)

class AliasedFeatureVariable(FeatureVariable):
    """    
    A set of variables that are constrained to be equal.  An aliased
    variable can be used in place of a simple variable.  In
    particular, an aliased variable stands for a single feature value,
    and requires that each its aliases are bound to that same
    value.  Aliased variables can be categorized according to their
    values in a set of bindings:
    
      - An aliased variable is X{unbound} if none of its aliases
        is assigned a value.
        
      - An aliased variable is X{bound} if at least one of its
        aliases is bound, and all of its bound aliases are
        assigned the same value.  (If at least one alias is
        unbound, then the aliased variable is said to be X{partially
        bound}.)
        
      - An aliased variable is X{inconsistant} if two or more
        aliases are bound to different values.

    @ivar _aliases: The set of aliases contained by
        this aliased variable.  This set is encoded as a dictionary
        whose keys are variables.
    """
    def __init__(self, *aliases):
        """
        Construct a new feature structure variable that contains the
        given aliases.  If C{aliases} contains aliased
        variables, then they are replaced by their lists of
        aliases.
        @raise ValueError: If no aliases are specified.
        """
        if len(aliases) == 0:
            raise ValueError('Expected at least one alias')
        assert _chktype(1, aliases, (FeatureVariable,))
        self._aliases = {}
        for subvar in aliases:
            if isinstance(subvar, AliasedFeatureVariable):
                self._aliases.update(subvar._aliases)
            else:
                self._aliases[subvar] = 1

    def identifier(self):
        """
        Raise C{ValueError}, since aliased variables do not have a
        single identifier.
        """
        raise ValueError('Aliased variables do not have identifiers')
    
    def aliases(self):
        """
        @return: A list of the variables that are constrained to be
            equal by this aliased variable.
        """
        return self._aliases.keys()
    
    def __repr__(self):
        """
        @return: A string representation of this feature structure
           variable.  A feature structure variable with identifiers
           C{I{X1}, I{X2}, ..., I{Xn}} is represented as
           C{'?<I{X1}=I{X2}=...=I{Xn}>'}.
        """
        idents = [v._identifier for v in self.aliases()]
        idents.sort()
        return '?<' + '='.join(idents) + '>'
    
    def __cmp__(self):
        if not isinstance(other, FeatureVariable): return -1
        return cmp(self._aliases, other._identifier)
    
    def __hash__(self):
        return self._aliases.__hash__()

class FeatureBindings:
    """
    A partial mapping from feature variables to values.  Simple
    variables can be either X{bound} (i.e., assigned a value), or
    X{unbound} (i.e., left unspecified).  Aliased variables can
    additionally be X{inconsistant} (i.e., assigned multiple
    incompatible values).

    @ivar _bindings: A dictionary mapping from bound variables
        to their values.
    """
    def __init__(self, **initial_bindings):
        """
        Construct a new set of bindings.
        
        @param initial_bindings: A dictionary from variables to
            values, specifying the initial assignments for the bound
            variables.
        """
        # Check that variables are not used as values.
        for val in initial_bindings.values():
            if isinstance(val, FeatureVariable):
                err = 'Variables cannot be bound to other variables'
                raise ValueError(err)
        
        self._bindings = initial_bindings.copy()

    def bound_variables(self):
        """
        @return: A list of all simple variables that have been
            assigned values.
        @rtype: C{list} of L{FeatureVariable}
        """
        return self._bindings.keys()

    def is_bound(self, variable):
        """
        @return: True if the given variable is bound.  A simple
        variable is bound if it has been assigned a value.  An aliased
        variable is bound if at least one of its aliases is bound
        and all of its bound aliases are assigned the same value.
        
        @rtype: C{bool}
        """
        assert _chktype(1, variable, FeatureVariable)

        if isinstance(variable, AliasedFeatureVariable):
            bindings = [self._bindings.get(v)
                        for v in variable.aliases()
                        if self._bindings.has_key(v)]
            if len(bindings) == 0: return 0
            inconsistant = [val for val in bindings if val != bindings[0]]
            if inconsistant: return 0
            return 1
        
        return self._bindings.has_key(variable)

    def lookup(self, variable, update_aliased_bindings=False):
        """
        @return: The value that it assigned to the given variable, if
        it's bound; or the variable itself if it's unbound.  The value
        assigned to an aliased variable is defined as the value that's
        assigned to its bound aliases.

        @param update_aliased_bindings: If true, then looking up a
            bound aliased variable will cause any unbound aliases
            it has to be bound to its value.  E.g., if C{?x} is bound
            to C{1} and C{?y} is unbound, then looking up C{?x=y} will
            cause C{?y} to be bound to C{1}.
        @raise ValueError: If C{variable} is an aliased variable with an
            inconsistant value (i.e., if two or more of its bound
            aliases are assigned different values).
        """
        assert _chktype(1, variable, FeatureVariable)

        # If it's an aliased variable, then we need to check that the
        # bindings of all of its aliases are consistant.
        if isinstance(variable, AliasedFeatureVariable):
            # Get a list of all bindings.
            bindings = [self._bindings.get(v)
                        for v in variable.aliases()
                        if self._bindings.has_key(v)]
            # If it's unbound, return the (aliased) variable.
            if len(bindings) == 0: return variable
            # Make sure all the bindings are equal.
            val = bindings[0]
            for binding in bindings[1:]:
                if binding != val:
                    raise ValueError('inconsistant value')
            # Set any unbound aliases, if requested
            if update_aliased_bindings:
                for subvar in variable.aliases():
                    self._bindings[subvar] = val
            # Return the value.
            return val

        return self._bindings.get(variable, variable)
    
    def bind(self, variable, value):
        """
        Assign a value to a variable.  If C{variable} is an aliased
        variable, then the value is assigned to all of its
        aliases.  Variables can only be bound to values; they may
        not be bound to other variables.
        
        @raise ValueError: If C{value} is a variable.
        """
        assert _chktype(1, variable, FeatureVariable)
        if isinstance(value, FeatureVariable):
            raise ValueError('Variables cannot be bound to other variables')
        
        if isinstance(variable, AliasedFeatureVariable):
            for subvar in variable.aliases():
                self._bindings[subvar] = value
        else:
            self._bindings[variable] = value

    def copy(self):
        """
        @return: a copy of this set of bindings.
        """
        return FeatureBindings(**self._bindings)

    def __repr__(self):
        """
        @return: a string representation of this set of bindings.
        """
        if self._bindings:
            bindings = ['%r=%r' % (k,v) for (k,v) in self._bindings.items()]
            return '<Bindings: %s>' % (', '.join(bindings))
        else:
            return '<Bindings (empty)>'

    def __cmp__(self, other):
        if not isinstance(other, FeatureVariable): return -1
        return cmp((self._bindings, self._synonyms),
                   (other._bindings, other._synonyms))

# Feature structures use identity-based-equality.
class FeatureStructure:
    """
    A structured set of features.  These features are represented as a
    mapping from feature names to feature values, where each feature
    value is either a basic value (such as a string or an integer), or
    a nested feature structure.

    A feature structure's feature values can be accessed via indexing:

      >>> fstruct1 = FeatureStructure(number='singular', person='3rd')
      >>> print fstruct1['number']
      'singular'

      >>> fstruct2 = FeatureStructure(subject=fstruct1)
      >>> print fstruct2['subject']['person']
      '3rd'

    A nested feature value can be also accessed via a X{feature
    paths}, or a tuple of feature names that specifies the paths to
    the nested feature:

      >>> fpath = ('subject','number')
      >>> print fstruct2[fpath]
      'singular'

    Feature structures may contain reentrant feature values.  A
    X{reentrant feature value} is a single feature value that can be
    accessed via multiple feature paths.

    @note: Should I present them as DAGs instead?  That would make it
        easier to explain reentrancy.
    @ivar _features: A dictionary mapping from feature names to values.

    @ivar _forward: A pointer to another feature structure that
        replaced this feature structure.  This is used during the
        unification process to preserve reentrance.  In particular, if
        we're unifying feature structures A and B, where:

          - x and y are feature paths.
          - A contains a feature structure A[x]
          - B contains a reentrant feature structure B[x]=B[y]

        Then we need to ensure that in the unified structure C,
        C[x]=C[y].  (Here the equals sign is used to denote the object
        identity relation, i.e., C{is}.)
    """
    def __init__(self, **features):
        self._features = features

    def __getitem__(self, index):
        if type(index) == str:
            return self._features[index]
        elif len(index) == 0:
            return self
        elif len(index) == 1:
            return self._features[index[0]]
        elif isinstance(self._features[index[0]], FeatureStructure):
            return self._features[index[0]][index[1:]]
        else:
            raise IndexError('Bad feature path')

    def feature_names(self):
        """
        @return: A list of the names of the features whose values are
            defined by this feature structure.
        @rtype: C{list} of C{string}
        """
        return self._features.keys()

    def equal_values(self, other, check_reentrance=False):
        """
        @return: True if C{self} and C{other} assign the same value to
        to every feature.  In particular, return true if
        C{self[M{p}]==other[M{p}]} for every feature path M{p} such
        that C{self[M{p}]} or C{other[M{p}]} is a base value (i.e.,
        not a nested feature structure).

        Note that this is a weaker equality test than L{==<__eq__>},
        which tests for equal identity.

        @param check_reentrance: If true, then any difference in the
            reentrance relations between C{self} and C{other} will
            cause C{equal_values} to return false.
        """
        if not isinstance(other, FeatureStructure): return 0
        if check_reentrances: return `self` == `other`
        if len(self._features) != len(other._features): return 0
        for (fname, selfval) in self._features.items():
            otherval = other._features[fname]
            if isinstance(selfval, FeatureStructure):
                if not selfval.equal_values(otherval): return 0
            else:
                if selfval != otherval: return 0
        return 1

    def __eq__(self, other):
        """
        @return: True if C{self} is the same object as C{other}.  This<commit_msg>Fixed a couple of bugs: * 'check_reentrances' should be 'check_reentrance' * It seems the FeatureBindings constructor could never be run with arguments,   because it expected them as keyword arguments (with **initial_bindings), but   the keys of 'initial_bindings' are FeatureVariables, and the keys of keyword   arguments have to be strings. I changed 'bindings' to a plain argument to   make this work.<commit_after># Natural Language Toolkit: Feature Structures
#
# Copyright (C) 2003 University of Pennsylvania
# Author: <NAME> <<EMAIL>>,
#         <NAME> (original code)
# URL: <http://nltk.sourceforge.net>
# For license information, see LICENSE.TXT
#
# $Id$


"""
Basic data classes for representing feature structures.  A X{feature
structure} is a mapping from feature names to feature values, where:

  - Each X{feature name} is a case sensitive string.
  - Each X{feature value} can be a base value (such as a string), a
    variable, or a nested feature structure.

Feature structures are typically used to represent partial information
about objects.  A feature name that is not mapped to a value stands
for a feature whose value is unknown (I{not} a feature without a
value).  Two feature structures that represent (potentially
overlapping) information about the same object can be combined by
X{unification}.  When two inconsistant feature structures are unified,
the unification fails and returns C{None}.

Features are usually specified using X{feature paths}, or tuples of
feature names that specify path through the nested feature structures
to a value.

Feature structures may contain reentrant feature values.  A
X{reentrant feature value} is a single feature value that can be
accessed via multiple feature paths.  Unification preserves the
reentrance relations imposed by both of the unified feature
structures.  After unification, any extensions to a reentrant feature
value will be visible using any of its feature paths.

Feature structure variables are encoded using the
L{FeatureVariable} class.  Feature structure variables are
essentially just names; they do not directly contain values.  Instead,
the mapping from variables to values is encoded externally to the
variable, as a set of X{bindings}.  These bindings are stored using
the L{FeatureBindings} class.

@todo: more test cases
@sort: FeatureStructure, FeatureVariable, AliasedFeatureVariable,
       FeatureBindings
@group Feature Structures: FeatureStructure
@group Variables: FeatureVariable, AliasedFeatureVariable,
                  FeatureBindings
@group Unit Tests: FeatureStructureTestCase
"""

# Open question: should there be a "feature" object?
#
# The current implementation doesn't actually include an object to
# encode a "feature" (i.e., a name/value pair).  This makes the code
# simpler -- one less class to deal with, and you can directly query
# for feature values, rather than going through a feature object.  But
# there might be use cases for adding a Feature object.  E.g., if we
# wanted to assign properties (like is_required) to features.  But I'd
# like to see some compelling use cases before we add it.

import re
from nltk.chktype import chktype as _chktype
from types import NoneType

#//////////////////////////////////////////////////////////////////////
# Variables and variable bindings
#//////////////////////////////////////////////////////////////////////

class FeatureVariable:
    """
    A variable that can stand for a single feature value in a feature
    structure.  Each variable is defined by a unique identifier, which
    can be either a case-sensitive string (for X{named variables}) or
    an integer (for X{numbered variables}).

    Named variables are created by calling the C{FeatureVariable}
    constructor with a string identifier.  If multiple named variables
    objects are created with the same identifier, then they represent
    the same variable.  Numbered variables are created by calling the
    C{FeatureVariable} constructor with no arguments; a new identifier
    will be automatically generated.  Each new numbered variable object
    is guaranteed to have a unique identifier.

    Variables do not directly contain values; instead, the mapping
    from variables to values is encoded externally as a set of
    bindings, using L{FeatureBindings}.  If a set of
    bindings assigns a value to a variable, then that variable is said
    to be X{bound} with respect to those bindings; otherwise, it is
    said to be X{unbound}.

    @see: L{FeatureStructure}
    """
    _next_numbered_id = 1
    
    def __init__(self, identifier=None):
        """
        Construct a new feature structure variable.
        @type identifier: C{string}
        @param identifier: A unique identifier for this variable.
            Any two C{FeatureVariable} objects with the
            same identifier are treated as the same variable.
        """
        assert _chktype(1, identifier, str, NoneType)
        if identifier is None:
            self._identifier = FeatureVariable._next_numbered_id
            FeatureVariable._next_numbered_id += 1
        else:
            self._identifier = identifier

    def identifier(self):
        """
        @return: This variable's unique identifier.
        @rtype: C{string}
        """
        return self._identifier

    def __repr__(self):
        """
        @return: A string representation of this feature structure
           variable.  A feature structure variable with identifier
           C{I{x}} is represented as C{'?I{x}'}.
        """
        return '?%s' % self._identifier

    def __cmp__(self, other):
        if not isinstance(other, FeatureVariable): return -1
        return cmp(self._identifier, other._identifier)

    def __hash__(self):
        return self._identifier.__hash__()

    def alias(self, variable):
        """
        Return an aliased variable that constrains this variable to be
        equal to C{variable}.
        @rtype: L{AliasedFeatureVariable}
        """
        if self == variable: return self
        return AliasedFeatureVariable(self, variable)

    def parse(s):
        """
        Given a string that encodes a feature variable, return that
        variable.  This method can be used to parse both
        C{FeatureVariables} and C{AliasedFeatureVariables}.  However,
        this method can not be used to parse numbered variables, since
        doing so could violate the guarantee that each numbered
        variable object has a unique identifier.
        """
        # Simple variable
        match = re.match(r'\?[a-zA-Z_][a-zA-Z0-9_]*$', s)
        if match:
            return FeatureVariable(s[1:])

        # Aliased variable
        match = re.match(r'\?<[a-zA-Z_][a-zA-Z0-9_]*'+
                         r'(=[a-zA-Z_][a-zA-Z0-9_]*)*>$', s)
        if match:
            idents = s[2:-1].split('=')
            vars = [FeatureVariable(i) for i in idents]
            return AliasedFeatureVariable(*vars)

        raise ValueError('Bad FeatureVariable string')
    
    parse=staticmethod(parse)

class AliasedFeatureVariable(FeatureVariable):
    """    
    A set of variables that are constrained to be equal.  An aliased
    variable can be used in place of a simple variable.  In
    particular, an aliased variable stands for a single feature value,
    and requires that each its aliases are bound to that same
    value.  Aliased variables can be categorized according to their
    values in a set of bindings:
    
      - An aliased variable is X{unbound} if none of its aliases
        is assigned a value.
        
      - An aliased variable is X{bound} if at least one of its
        aliases is bound, and all of its bound aliases are
        assigned the same value.  (If at least one alias is
        unbound, then the aliased variable is said to be X{partially
        bound}.)
        
      - An aliased variable is X{inconsistant} if two or more
        aliases are bound to different values.

    @ivar _aliases: The set of aliases contained by
        this aliased variable.  This set is encoded as a dictionary
        whose keys are variables.
    """
    def __init__(self, *aliases):
        """
        Construct a new feature structure variable that contains the
        given aliases.  If C{aliases} contains aliased
        variables, then they are replaced by their lists of
        aliases.
        @raise ValueError: If no aliases are specified.
        """
        if len(aliases) == 0:
            raise ValueError('Expected at least one alias')
        assert _chktype(1, aliases, (FeatureVariable,))
        self._aliases = {}
        for subvar in aliases:
            if isinstance(subvar, AliasedFeatureVariable):
                self._aliases.update(subvar._aliases)
            else:
                self._aliases[subvar] = 1

    def identifier(self):
        """
        Raise C{ValueError}, since aliased variables do not have a
        single identifier.
        """
        raise ValueError('Aliased variables do not have identifiers')
    
    def aliases(self):
        """
        @return: A list of the variables that are constrained to be
            equal by this aliased variable.
        """
        return self._aliases.keys()
    
    def __repr__(self):
        """
        @return: A string representation of this feature structure
           variable.  A feature structure variable with identifiers
           C{I{X1}, I{X2}, ..., I{Xn}} is represented as
           C{'?<I{X1}=I{X2}=...=I{Xn}>'}.
        """
        idents = [v._identifier for v in self.aliases()]
        idents.sort()
        return '?<' + '='.join(idents) + '>'
    
    def __cmp__(self):
        if not isinstance(other, FeatureVariable): return -1
        return cmp(self._aliases, other._identifier)
    
    def __hash__(self):
        return self._aliases.__hash__()

class FeatureBindings:
    """
    A partial mapping from feature variables to values.  Simple
    variables can be either X{bound} (i.e., assigned a value), or
    X{unbound} (i.e., left unspecified).  Aliased variables can
    additionally be X{inconsistant} (i.e., assigned multiple
    incompatible values).

    @ivar _bindings: A dictionary mapping from bound variables
        to their values.
    """
    def __init__(self, initial_bindings=None):
        """
        Construct a new set of bindings.
        
        @param initial_bindings: A dictionary from variables to
            values, specifying the initial assignments for the bound
            variables.
        """
        # Check that variables are not used as values.
        if initial_bindings is None: initial_bindings = {}
        for val in initial_bindings.values():
            if isinstance(val, FeatureVariable):
                err = 'Variables cannot be bound to other variables'
                raise ValueError(err)
        
        self._bindings = initial_bindings.copy()

    def bound_variables(self):
        """
        @return: A list of all simple variables that have been
            assigned values.
        @rtype: C{list} of L{FeatureVariable}
        """
        return self._bindings.keys()

    def is_bound(self, variable):
        """
        @return: True if the given variable is bound.  A simple
        variable is bound if it has been assigned a value.  An aliased
        variable is bound if at least one of its aliases is bound
        and all of its bound aliases are assigned the same value.
        
        @rtype: C{bool}
        """
        assert _chktype(1, variable, FeatureVariable)

        if isinstance(variable, AliasedFeatureVariable):
            bindings = [self._bindings.get(v)
                        for v in variable.aliases()
                        if self._bindings.has_key(v)]
            if len(bindings) == 0: return 0
            inconsistant = [val for val in bindings if val != bindings[0]]
            if inconsistant: return 0
            return 1
        
        return self._bindings.has_key(variable)

    def lookup(self, variable, update_aliased_bindings=False):
        """
        @return: The value that it assigned to the given variable, if
        it's bound; or the variable itself if it's unbound.  The value
        assigned to an aliased variable is defined as the value that's
        assigned to its bound aliases.

        @param update_aliased_bindings: If true, then looking up a
            bound aliased variable will cause any unbound aliases
            it has to be bound to its value.  E.g., if C{?x} is bound
            to C{1} and C{?y} is unbound, then looking up C{?x=y} will
            cause C{?y} to be bound to C{1}.
        @raise ValueError: If C{variable} is an aliased variable with an
            inconsistant value (i.e., if two or more of its bound
            aliases are assigned different values).
        """
        assert _chktype(1, variable, FeatureVariable)

        # If it's an aliased variable, then we need to check that the
        # bindings of all of its aliases are consistant.
        if isinstance(variable, AliasedFeatureVariable):
            # Get a list of all bindings.
            bindings = [self._bindings.get(v)
                        for v in variable.aliases()
                        if self._bindings.has_key(v)]
            # If it's unbound, return the (aliased) variable.
            if len(bindings) == 0: return variable
            # Make sure all the bindings are equal.
            val = bindings[0]
            for binding in bindings[1:]:
                if binding != val:
                    raise ValueError('inconsistant value')
            # Set any unbound aliases, if requested
            if update_aliased_bindings:
                for subvar in variable.aliases():
                    self._bindings[subvar] = val
            # Return the value.
            return val

        return self._bindings.get(variable, variable)
    
    def bind(self, variable, value):
        """
        Assign a value to a variable.  If C{variable} is an aliased
        variable, then the value is assigned to all of its
        aliases.  Variables can only be bound to values; they may
        not be bound to other variables.
        
        @raise ValueError: If C{value} is a variable.
        """
        assert _chktype(1, variable, FeatureVariable)
        if isinstance(value, FeatureVariable):
            raise ValueError('Variables cannot be bound to other variables')
        
        if isinstance(variable, AliasedFeatureVariable):
            for subvar in variable.aliases():
                self._bindings[subvar] = value
        else:
            self._bindings[variable] = value

    def copy(self):
        """
        @return: a copy of this set of bindings.
        """
        return FeatureBindings(self._bindings)

    def __repr__(self):
        """
        @return: a string representation of this set of bindings.
        """
        if self._bindings:
            bindings = ['%r=%r' % (k,v) for (k,v) in self._bindings.items()]
            return '<Bindings: %s>' % (', '.join(bindings))
        else:
            return '<Bindings (empty)>'

    def __cmp__(self, other):
        if not isinstance(other, FeatureVariable): return -1
        return cmp((self._bindings, self._synonyms),
                   (other._bindings, other._synonyms))

# Feature structures use identity-based-equality.
class FeatureStructure:
    """
    A structured set of features.  These features are represented as a
    mapping from feature names to feature values, where each feature
    value is either a basic value (such as a string or an integer), or
    a nested feature structure.

    A feature structure's feature values can be accessed via indexing:

      >>> fstruct1 = FeatureStructure(number='singular', person='3rd')
      >>> print fstruct1['number']
      'singular'

      >>> fstruct2 = FeatureStructure(subject=fstruct1)
      >>> print fstruct2['subject']['person']
      '3rd'

    A nested feature value can be also accessed via a X{feature
    paths}, or a tuple of feature names that specifies the paths to
    the nested feature:

      >>> fpath = ('subject','number')
      >>> print fstruct2[fpath]
      'singular'

    Feature structures may contain reentrant feature values.  A
    X{reentrant feature value} is a single feature value that can be
    accessed via multiple feature paths.

    @note: Should I present them as DAGs instead?  That would make it
        easier to explain reentrancy.
    @ivar _features: A dictionary mapping from feature names to values.

    @ivar _forward: A pointer to another feature structure that
        replaced this feature structure.  This is used during the
        unification process to preserve reentrance.  In particular, if
        we're unifying feature structures A and B, where:

          - x and y are feature paths.
          - A contains a feature structure A[x]
          - B contains a reentrant feature structure B[x]=B[y]

        Then we need to ensure that in the unified structure C,
        C[x]=C[y].  (Here the equals sign is used to denote the object
        identity relation, i.e., C{is}.)
    """
    def __init__(self, **features):
        self._features = features

    def __getitem__(self, index):
        if type(index) == str:
            return self._features[index]
        elif len(index) == 0:
            return self
        elif len(index) == 1:
            return self._features[index[0]]
        elif isinstance(self._features[index[0]], FeatureStructure):
            return self._features[index[0]][index[1:]]
        else:
            raise IndexError('Bad feature path')

    def feature_names(self):
        """
        @return: A list of the names of the features whose values are
            defined by this feature structure.
        @rtype: C{list} of C{string}
        """
        return self._features.keys()

    def equal_values(self, other, check_reentrance=False):
        """
        @return: True if C{self} and C{other} assign the same value to
        to every feature.  In particular, return true if
        C{self[M{p}]==other[M{p}]} for every feature path M{p} such
        that C{self[M{p}]} or C{other[M{p}]} is a base value (i.e.,
        not a nested feature structure).

        Note that this is a weaker equality test than L{==<__eq__>},
        which tests for equal identity.

        @param check_reentrance: If true, then any difference in the
            reentrance relations between C{self} and C{other} will
            cause C{equal_values} to return false.
        """
        if not isinstance(other, FeatureStructure): return 0
        if check_reentrance: return `self` == `other`
        if len(self._features) != len(other._features): return 0
        for (fname, selfval) in self._features.items():
            otherval = other._features[fname]
            if isinstance(selfval, FeatureStructure):
                if not selfval.equal_values(otherval): return 0
            else:
                if selfval != otherval: return 0
        return 1

    def __eq__(self, other):
        """
        @return: True if C{self} is the same object as C{other}.  This
{'fraction_non_alphanumeric': 0.08321486863581319, 'fraction_numerical': 0.0030537566471858053, 'mean_word_length': 2.3380492091388403, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 61, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2107517', 'n_tokens_mistral': 9876, 'n_tokens_neox': 9632, 'n_words': 4102}