text: # $Id: contexts.py 081917d30609 2010-03-05 mtnyogi $
  # coding=utf-8
  # 
  # Copyright © 2007-2008 Bruce Frederiksen
  # 
  # Permission is hereby granted, free of charge, to any person obtaining a copy
  # of this software and associated documentation files (the "Software"), to deal
  # in the Software without restriction, including without limitation the rights
  # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  # copies of the Software, and to permit persons to whom the Software is
  # furnished to do so, subject to the following conditions:
  # 
  # The above copyright notice and this permission notice shall be included in
  # all copies or substantial portions of the Software.
  # 
  # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  # THE SOFTWARE.
  
  """
      A context is used to store all of a rule's pattern variable bindings for a
      specific rule invocation during inferencing (both forward-chaining and
      backward-chaining rules).
  
          >>> from pyke import pattern
          >>> c = simple_context()
          >>> var = variable('foo')
          >>> var
          $foo
          >>> var.name
          'foo'
          >>> c.bind(var.name, c, 123)
          True
          >>> c.lookup(var)
          (123, None)
          >>> c.lookup_data(var.name)
          123
      
      This is a shallow binding scheme which must "unbind" variables when a
      rule is done.  Each time a rule is invoked, a new context object is
      created to store the bindings for the variables in that rule.  When the
      rule is done, this context is abandoned; so the variables bound there
      do not need to be individually unbound.  But bindings done to
      variables in other contexts _do_ need to be individually unbound.
      These bindings happen when a variable in the calling rule, which must
      be bound in that rule's context, is matched to a non-variable pattern (i.e.,
      pattern_literal or pattern_tuple) in the called rule's context.
  
      For example, a caller, rule A, has its own context:
  
          >>> A_context = simple_context()
  
      and a pattern of $foo within a subgoal in its 'when' clause:
  
          >>> A_pattern = variable('foo')
  
      In proving this subgoal, rule B is being tried.  A new context is
      created for rule B:
  
          >>> B_context = simple_context()
  
      Rule B has a literal 123 in its 'proven' clause:
  
          >>> B_pattern = pattern.pattern_literal(123)
  
      Now B's 'proven' clause is pattern matched to A's subgoal, which
      results in:
  
          >>> B_pattern.match_pattern(B_context, B_context, A_pattern, A_context)
          True
  
      The pattern matches!  But the $foo variable belongs to A, so it must be
      bound in A's context, not B's.
  
          >>> A_context.lookup(A_pattern)
          (123, None)
          >>> B_context.lookup(A_pattern)
          Traceback (most recent call last):
              ...
          KeyError: '$foo not bound'
  
      This is done by using the current rule's context as a controlling context
      for all the bindings that occur within that rule.  If the binding is for
      a variable in another context, the controlling context remembers the
      binding in its undo_list.  When the rule is finished, it executes a 'done'
      method on its context which undoes all of the bindings in its undo_list.
  
          >>> B_context.done()
          >>> A_context.lookup(A_pattern)
          Traceback (most recent call last):
              ...
          KeyError: '$foo not bound'
  
      Thus, in binding a variable to a value, there are three contexts
      involved:
  
          controlling_context.bind(variable, variable_context,
                                   value [, value_context])
  
      The value_context must be omitted if value is any python data, and
      must be included if value is a pattern (including another variable).
  
      Variables are bound to as just strings so that they can be accessed
      easily from python code without needing the variable objects.
  
          >>> A_context.bind('foo', A_context, 123)
          True
          >>> A_context.lookup_data('foo')
          123
      
      But to differentiate variables from string literals in the patterns,
      variables are special objects.  When a variable is bound as data (to
      another variable), it is bound as a variable object (again, to
      differentiate it from plain python strings).
  
          >>> a_var = variable('a_var')
          >>> a_var
          $a_var
          >>> b_var = variable('b_var')
          >>> b_var
          $b_var
          >>> B_context.bind(b_var.name, B_context, a_var, A_context)
          True
          >>> B_context.lookup(b_var)
          Traceback (most recent call last):
              ...
          KeyError: '$a_var not bound'
          >>> ans = B_context.lookup(b_var, True)
          >>> ans                                 # doctest: +ELLIPSIS
          ($a_var, <pyke.contexts.simple_context object at ...>)
          >>> ans[1] is A_context
          True
      
      But to differentiate variables from string literals in the patterns,
      variables are special objects.  When a variable is bound as data (to
      another variable), it is bound as a variable object (again, to
      differentiate it from plain python strings).
  
          >>> type(ans[0])
          <class 'pyke.contexts.variable'>
  
      The anonymous variables have names starting with '_'.  Binding
      requests on anonymous variables are silently ignored.
  
          >>> anonymous('_ignored')
          $_ignored
          >>> A_context.bind('_bogus', A_context, 567)
          False
          >>> A_context.lookup_data('_bogus')
          Traceback (most recent call last):
              ...
          KeyError: '$_bogus not bound'
          >>> A_context.lookup_data('_bogus', True)
          '$_bogus'
  """
  
  import sys
  
  from pyke import pattern, unique
  
  _Not_found = unique.unique('Not_found')
  
  # Set to a sequence (or frozenset) of variable names to trace their bindings:
  debug = ()
  
  class simple_context(object):
      def __init__(self):
          self.bindings = {}
          self.undo_list = []
          self.save_all_undo_count = 0
  
      def dump(self):
          for var_name in sorted(self.bindings.iterkeys()):
              print "%s: %s" % (var_name, repr(self.lookup_data(var_name, True)))
  
      def bind(self, var_name, var_context, val, val_context = None):
          """ val_context must be None iff val is not a pattern.
              Returns True if a new binding was created.
          """
          assert not isinstance(val, pattern.pattern) \
                     if val_context is None \
                     else isinstance(val, pattern.pattern)
          if var_name[0] == '_': return False
          if var_context is self:
              assert var_name not in self.bindings
              if val_context is not None:
                  val, val_context = val_context.lookup(val, True)
              if val_context == var_context and isinstance(val, variable) and \
                 val.name == var_name:
                  # binding $x to $x; no binding necessary!
                  return False
              if var_name in debug:
                  if val_context:
                      sys.stderr.write("binding %s in %s to %s in %s\n" %
                          (var_name, var_context, val, val_context))
                  else:
                      sys.stderr.write("binding %s in %s to %s\n" %
                          (var_name, var_context, val))
              self.bindings[var_name] = (val, val_context)
              if self.save_all_undo_count:
                  self.undo_list.append((var_name, self))
              return True
          ans = var_context.bind(var_name, var_context, val, val_context)
          if ans: self.undo_list.append((var_name, var_context))
          return ans
  
      def is_bound(self, var):
          val, where = var, self
          while where is not None and isinstance(val, variable):
              ans = where.bindings.get(val.name)
              if ans is None: return False
              val, where = ans
          # where is None or not isinstance(val, variable)
          return where is None or val.is_data(where)
  
      def lookup_data(self, var_name, allow_vars = False, final = None):
          """ Converts the answer into data only (without any patterns in it).
              If there are unbound variables anywhere in the data, a KeyError is
              generated.
          """
          if final is not None:
              val = final.get((var_name, self), _Not_found)
              if val is not _Not_found: return val
          binding = self.bindings.get(var_name)
          if binding is None:
              if allow_vars: return "$" + var_name
              raise KeyError("$%s not bound" % var_name)
          val, context = binding
          if context is not None:
              val = val.as_data(context, allow_vars, final)
          if isinstance(val, bc_context): val = val.create_plan(final)
          if final is not None: final[var_name, self] = val
          return val
  
      def lookup(self, var, allow_variable_in_ans = False):
          """ Returns value, val_context.
              Returns (var, self) if not bound and allow_variable_in_ans, else
              raises KeyError.
          """
          val, where = var, self
          while where is not None and isinstance(val, variable):
              ans = where.bindings.get(val.name)
              if ans is None: break
              val, where = ans
          else:
              # where is None or not isinstance(val, variable)
              return val, where
          # where is not None and isinstance(val, variable)
          if allow_variable_in_ans: return val, where
          raise KeyError("%s not bound" % str(val))
  
      def mark(self, save_all_undo = False):
          if save_all_undo: self.save_all_undo_count += 1
          return len(self.undo_list)
  
      def end_save_all_undo(self):
          assert self.save_all_undo_count > 0
          self.save_all_undo_count -= 1
  
      def undo_to_mark(self, mark, *var_names_to_undo):
          for var_name, var_context in self.undo_list[mark:]:
              var_context._unbind(var_name)
          del self.undo_list[mark:]
          for var_name in var_names_to_undo:
              self._unbind(var_name)
  
      def done(self):
          """ Unbinds all variables bound through 'self's 'bind' method.
              The assumption here is that 'self' is being abandoned, so we don't
              need to worry about self.bindings.
          """
          for var_name, var_context in self.undo_list:
              var_context._unbind(var_name)
  
      def _unbind(self, var_name):
          del self.bindings[var_name]
  
  class bc_context(simple_context):
      def __init__(self, rule):
          super(bc_context, self).__init__()
          self.rule = rule
  
      def name(self): return self.rule.name
  
      def __repr__(self):
          return "<bc_context for %s at 0x%x>" % (self.name(), id(self))
  
      def create_plan(self, final = None):
          if final is None: final = {}
          return self.rule.make_plan(self, final)
  
  class variable(pattern.pattern):
      """ The code to force variables of the same name to be the same object is
          probably not needed anymore...
      """
      Variables = {}
  
      def __new__(cls, name):
          var = cls.Variables.get(name)
          if var is None:
              var = super(variable, cls).__new__(cls)
              cls.Variables[name] = var
          return var
  
      def __init__(self, name):
          self.name = name
  
      def __repr__(self): return '$' + self.name
  
      def lookup(self, my_context, allow_variable_in_ans = False):
          return my_context.lookup(self, allow_variable_in_ans)
  
      def match_data(self, bindings, my_context, data):
          if self.name in debug:
              sys.stderr.write("%s.match_data(%s, %s, %s)\n" %
                  (self, bindings, my_context, data))
          var, var_context = my_context.lookup(self, True)
          if isinstance(var, variable):
              bindings.bind(var.name, var_context, data)
              return True
          if self.name in debug:
              sys.stderr.write("%s.match_data: lookup got %s in %s\n" %
                  (self, var, var_context))
          if var_context is None: return var == data
          return var.match_data(bindings, var_context, data)
  
      def simple_match_pattern(self, bindings, my_context, pattern_b, b_context):
          var, var_context = my_context.lookup(self, True)
          if isinstance(var, variable):
              bindings.bind(var.name, var_context, pattern_b, b_context)
              return True
          if var_context is None:
              return pattern_b.match_data(bindings, b_context, var)
          return var.simple_match_pattern(bindings, var_context,
                                          pattern_b, b_context)
  
      def match_pattern(self, bindings, my_context, pattern_b, b_context):
          var, var_context = my_context.lookup(self, True)
          if isinstance(var, variable):
              bindings.bind(var.name, var_context, pattern_b, b_context)
              return True
          if var_context is None:
              return pattern_b.match_data(bindings, b_context, var)
          return var.match_pattern(bindings, var_context, pattern_b, b_context)
  
      def as_data(self, my_context, allow_vars = False, final = None):
          return my_context.lookup_data(self.name, allow_vars, final)
  
      def is_data(self, my_context):
          return my_context.is_bound(self)
  
  class anonymous(variable):
      def __init__(self, name):
          assert name[0] == '_', \
                 "anonymous variables must start with '_', not %s" % name
          super(anonymous, self).__init__(name)
  
      def lookup(self, my_context, allow_variable_in_ans = False):
          if allow_variable_in_ans: return self, my_context
          raise KeyError("$%s not bound" % self.name)
  
      def match_data(self, bindings, my_context, data):
          return True
  
      def match_pattern(self, bindings, my_context, pattern_b, b_context):
          return True
  
      def as_data(self, my_context, allow_vars = False, final = None):
          if allow_vars: return "$%s" % self.name
          raise KeyError("$%s not bound" % self.name)
  
      def is_data(self, my_context):
          return False
  
  