#!/usr/bin/env python
#
# Copyright 2007 Google Inc.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#
"""Code for representing and manipulating handlers in app.yaml.

App.yaml requires developers to list handlers - specifications for how URL
requests in their app are handled. This module contains classes for
representing handlers, as well as functions for creating handlers from
specifications in appengine-web.xml and web.xml, manipulating and matching
paths, and ordering them correctly so that the yaml file preserves the semantics
of the user-specified xml.

In this module:
  Handler: Ancestor class that provides pattern matching and other utilities.
  SimpleHandler: A representation of path handling specified in XML - a path
    along with properties detailing how it is handled.
  OverlappedHandler: A representation of combinations of paths specified by
    users in Xml. OverlappedHandlers combine properties, such as security
    settings, from the SimpleHandlers that they are made up of.
  GetOrderedIntersection: Returns an ordered list of Handlers that can be
    written directly to Yaml.
"""

import fnmatch
import itertools
import re


class Handler(object):
  """Ancestor class for Handler manipulation. Patterns are globs.

  (http://en.wikipedia.org/wiki/Glob_(programming)).
  """

  ALL_PROPERTIES = [
      'expiration',
      'http_headers',
      'required_role',
      'transport_guarantee',
      'type',
      'welcome'
      ]

  def __init__(self, pattern):
    self.pattern = pattern

  def _GetPattern(self):
    return self._pattern

  def _SetPattern(self, the_pattern):
    self._pattern = the_pattern
    self._regex = re.compile(re.escape(the_pattern).replace('\\*', '.*') + '$')
    self.is_literal = '*' not in the_pattern

  pattern = property(_GetPattern, _SetPattern)

  @property
  def regex(self):
    return self._regex

  def Regexify(self):
    """Returns a regex-looking string to write to Yaml."""

    return self.pattern.replace('.', '\\.').replace('*', '.*')

  def MatchesString(self, pattern_str):
    """Returns true if input path string is matched by glob pattern."""
    return self._regex.match(pattern_str) is not None

  def MatchesAll(self, other_glob):
    """Returns True if self matches everything other_glob matches."""


    return self.MatchesString(other_glob.pattern)

  def HasMoreSpecificPatternThan(self, other_handler):
    """Returns True if self is more specific than other_handler.

    Priority in determining specificity is first determined by literal-ness,
    second by length. This is according to the Java servlet spec for
    mapping URL paths.

    Args:
      other_handler: another handler to compare against.

    Returns:
      True if self.pattern is a literal and other_handler.pattern is not,
      False if vice versa, and otherwise True if self.pattern is longer.
    """

    if self.is_literal != other_handler.is_literal:
      return self.is_literal

    return len(self.pattern) > len(other_handler.pattern)

  def __eq__(self, other_handler):
    return (isinstance(other_handler, Handler) and
            self.__dict__ == other_handler.__dict__)

  def IsFullyHandledBy(self, other_handler):
    """Returns True if self specifies something unique.

    For example, If we have a Handler with pattern "foo*bar"
    which has properties {'type': 'static'}, and other_handler
    has pattern "foo*" with the same properties, then
    other_handler does everything that self does.

    Args:
      other_handler: other handler to be matched against
    Returns:
      Boolean value of whether other_handler fully handles self.
    """
    return (other_handler.MatchesAll(self) and
            self._PropertiesMatch(other_handler))

  def _PropertiesMatch(self, other):
    """Returns True if other.properties is superset of self.properties."""
    for prop in Handler.ALL_PROPERTIES:
      if self.GetProperty(prop) not in (None, other.GetProperty(prop)):
        return False
    return True


def _MakeHandlerList(*pattern_strings):
  return [SimpleHandler(a) for a in pattern_strings]


class SimpleHandler(Handler):
  """Subclass of Handler which includes user-defined settings with urls.

  SimpleHandlers should be treated as immutable.
  """

  def __init__(self, pattern, properties=None):
    super(SimpleHandler, self).__init__(pattern)
    if properties:
      self.properties = properties
    else:
      self.properties = {}

  def __hash__(self):
    return hash((self.pattern, tuple(sorted(self.properties.items()))))

  def GetProperty(self, prop, default=None):
    return self.properties.get(prop, default)

  def CreateOverlappedHandler(self):
    """Creates a Combined Handler with self's pattern and self as a child."""
    return OverlappedHandler(self.pattern, matchers=[self])


class OverlappedHandler(Handler):
  """Subclass of Handler which allows for the combination of SimpleHandlers.

  An intuitive way to think about globbed patterns is as sets - for example, the
  pattern "admin/*" is the set of all paths that are in the admin/ directory,
  and the pattern "*.txt" is the set of all paths to text files. An
  OverlappedHandler is designed to describe the intersection of the sets
  of paths - ie the set of paths that is matched by EVERY one its
  handler patterns.

  In the Xml files, paths are specified in different places - in servlet
  patterns, in static files includes, in security constraint specifications,
  etc. There is often some overlap between the paths that are specified by
  these patterns. Since App.Yaml does not have separate places to specify how
  different paths are handled, but rather just lists paths along with a bunch
  of ways that the paths is handled, we need to make sure that these properties
  for various paths are being combined at some point in the translation process.

  Thus an OverlappedHandler holds a list of "matchers" - ie. handlers with more
  general patterns, to choose properties from. OverlappedHandlers do not
  explicitly specify properties but rather choose the value from the most
  specific "matcher" with the value of that property specified. The matchers
  are SimpleHandlers.

  Attributes:
    pattern: inherited from Handler.
    matchers: A list of SimpleHandlers. Matchers are handlers which happen to
      match OverlappedHandler's pattern and whose properties are thus necessary
      to track in order to make sure that OverlappedHandler's pattern is handled
      correctly.
  """

  def __init__(self, pattern, matchers=()):
    super(OverlappedHandler, self).__init__(pattern)
    self.matchers = []
    for sub_handler in matchers:
      self.AddMatchingHandler(sub_handler)

  def GetProperty(self, prop, default=None):
    """Returns the property value of matcher with most specific pattern."""

    largest_handler = None
    prop_value = default
    for sub_handler in self.matchers:
      if sub_handler.GetProperty(prop) is not None:
        if (not largest_handler or
            sub_handler.HasMoreSpecificPatternThan(largest_handler)):
          largest_handler = sub_handler
          prop_value = sub_handler.GetProperty(prop)
    return prop_value

  def __eq__(self, other_handler):
    return (isinstance(other_handler, OverlappedHandler) and
            self.pattern == other_handler.pattern and
            set(self.matchers) == set(other_handler.matchers))

  def AddMatchingHandler(self, matcher):
    """Flattens the handler if it is overlapped and adds to matchers."""
    if isinstance(matcher, SimpleHandler):
      self.matchers.append(matcher)
    else:
      self.matchers.extend(matcher.matchers)


def GetOrderedIntersection(handler_list):
  """Implements algorithm for combining and reordering Handlers.

  GetOrderedIntersection performs the heavy lifting of converting a randomly
  ordered list of Handlers (globbed patterns, each with various potentially
  conflicting properties attached), into an ordered list of handlers with
  property values resolved.

  The purpose of this process is to convert the Web.xml URL mapping scheme to
  that of app.yaml. In Web.xml the most specific path, according to
  literal-ness and length, is chosen. In app.yaml the first listed matching
  path is chosen. Thus to preserve user preferences through the translation
  process we order the patterns from specific to general.

  For example, if three handlers are given as input (in any order):

  "/admin/*" (security=admin)
  "/*.png" (type=static)
  "*" (type=dynamic, security=required)

  we want to get this ordered list as output:
  1. "/admin/*.png" (security=admin, type=static)
  2. "/admin/*" (security=admin, type=dynamic)
  3. "/*.png" (security=required, type=static)
  4. "*" (type=dynamic, security=required).

  so that the properties of any given path are those of the longest matching
  path. The SimpleHandler and OverlappedHandler classes provide the logic for
  attaching globbed patterns to the right properties and resolving potential
  property value conflicts.

  Args:
    handler_list: List of SimpleHandlers in arbitrary order.
  Returns:
    An ordered list of OverlappedHandlers and SimpleHandlers. See the above
    example for what this would look like.
  """
  results = _Intersect(handler_list)


  results = sorted(results, key=lambda h: h.pattern)
  _ReorderHandlers(results)
  _GivePropertiesFromGeneralToSpecific(results)
  return _RemoveRedundantHandlers(results)


def _RemoveRedundantHandlers(handler_list):
  """Removes duplicated or unnecessary handlers from the list.

  If a handler's pattern and functionality are fully matched by another handler
  with a more general pattern, we do not need the  first handler. At the same
  time, we remove duplicates.

  Args:
    handler_list: list of ordered handlers with possibly redundant entries.
  Returns:
    new list which contains entries of handler_list, except redundant ones.
  """

  no_duplicates = []
  patterns_found_so_far = set()
  for i in xrange(len(handler_list)):
    current_handler = handler_list[i]
    matched_by_later = False
    for j in xrange(i + 1, len(handler_list)):
      if current_handler.IsFullyHandledBy(handler_list[j]):
        matched_by_later = True
        break

    if (not matched_by_later and
        current_handler.pattern not in patterns_found_so_far):
      no_duplicates.append(current_handler)
      patterns_found_so_far.add(current_handler.pattern)

  return no_duplicates


def _ReorderHandlers(handler_list):
  """Reorders handlers from specific to general for writing to yaml file.

  This is a topological sort - ie. it makes sure that elements related to
  each other are ordered correctly. In this case, we want to make sure that
  any Handler with a pattern that matches all of the Handlers of another pattern
  occurs later. Thus, we want to make sure that "foo*" occurs after "foo*bar",
  but it does not matter how it is ordered relative to "*baz", since they have
  an empty intersection of patterns.

  The problem with using Python's built-in sorted is that it relies on the
  class's less-than operator. We want an ordering such that
    (handler1 < handler2) iff (not handler1.MatchesAll(handler2))
  Then, since "foo*" and "*baz" do not contain each other, foo* < *baz == True
  and *baz < foo* == True. This is a problem because Python's sorted does not
  explicitly compare every pair of elements, but operates under the assumption
  that if a < b and b < c, then a < c. Therefore, if we have
    a = "foo*bar", b = "*baz", c = "foo*"
  then a < b == True and b < c == True, so a < c is assumed to be True. This
  often leads to wrong orderings.

  Therefore, this function performs a topological sort
  (http://en.wikipedia.org/wiki/Topological_sorting), reordering only those
  patterns where one matches all of the other.

  This is an in-place sort.

  Args:
    handler_list: Unordered list of handlers.
  """
  for i, j in itertools.combinations(xrange(len(handler_list)), 2):
    if handler_list[i].MatchesAll(handler_list[j]):
      handler_list[i], handler_list[j] = handler_list[j], handler_list[i]


def _GivePropertiesFromGeneralToSpecific(handler_list):
  """Makes sure that handlers have all properties of more general ones.

  Ex. Since "*" matches everything "admin/*" matches, we want everything
  matched by "admin/*" to have all the properties specified to "*".
  Therefore we give properties from the "*" handler to the "admin/*" handler.
  If the "*" handler is a SimpleHandler, it carries its own properties, so it
  becomes a child of the "admin/*" handler. Otherwise, its properties are
  define by its children, so its children are copied to the "admin/*"
  handler.

  This is an in-place mutation of the list.

  Args:
    handler_list: List of ordered Handlers.
  """
  for i, j in itertools.combinations(xrange(len(handler_list)), 2):
    if handler_list[j].MatchesAll(handler_list[i]):
      if isinstance(handler_list[i], SimpleHandler):
        handler_list[i] = handler_list[i].CreateOverlappedHandler()
      handler_list[i].AddMatchingHandler(handler_list[j])


def _Intersect(handler_list):
  """Returns an unordered list of all possible intersections of handlers."""
  if not handler_list:
    return set()

  handlers = set([handler_list[0]])


  for input_handler in handler_list[1:]:
    new_handlers = set()
    for g in handlers:
      new_handlers |= _IntersectTwoHandlers(input_handler, g)
    handlers = new_handlers
  return list(handlers)


def _IntersectTwoHandlers(first_handler, second_handler):
  """Returns intersections of first_handler and second_handler patterns."""
  shared_prefix = _SharedPrefix(first_handler.pattern, second_handler.pattern)

  if shared_prefix:
    return _HandleCommonPrefix(first_handler, second_handler, shared_prefix)


  shared_suffix = _SharedSuffix(first_handler.pattern, second_handler.pattern)
  if shared_suffix:
    return _HandleCommonSuffix(first_handler, second_handler, shared_suffix)

  handler_set = set()
  handler_set |= _HandleWildcardCases(first_handler, second_handler)


  handler_set |= _HandleWildcardCases(second_handler, first_handler)

  handler_set |= set([first_handler, second_handler])

  return handler_set


def _HandleWildcardCases(first_handler, second_handler):
  """Handle cases with trailing and leading wildcards.

  This function finds the set of intersections of two handlers where one has a
  leading wildcard (eg. *foo) in its pattern and at least one has a trailing
  wildcard (eg. baz*) in its pattern. The arguments are not symmetric.

  Args:
    first_handler: A SimpleHandler instance
    second_handler: A SimpleHandler instance
  Returns:
    A set of intersection patterns of the two Handlers. Example: If the
    pattern of first_handler is abc* and that of the second is *xyz, we return
    the intersection of the patterns, abc*xyz. Find more examples in the inline
    comments.
  """
  merged_handlers = set()

  if len(first_handler.pattern) <= 1 or len(second_handler.pattern) <= 1:
    return merged_handlers

  if (first_handler.pattern[-1], second_handler.pattern[0]) != ('*', '*'):
    return merged_handlers


  first_no_star = first_handler.pattern[:-1]
  merged_handlers.add(SimpleHandler(first_no_star + second_handler.pattern))
  if second_handler.MatchesString(first_no_star):


    merged_handlers.add(SimpleHandler(first_no_star))
  return merged_handlers


def _HandleCommonPrefix(first_handler, second_handler, common_prefix):
  """Strips common literal prefix from handlers and intersects the substrings.

  Ex. "abc" and "a*c" become "a | bc" and "a | *c". We find the set of
  intersections of "bc" and "*c" and prepend "a" onto each member of that set.
  By common literal prefix, we mean a prefix of the two patterns that contains
  no wildcard characters; any string matched by either of the patterns must
  begin with that prefix.

  Args:
    first_handler: A SimpleHandler.
    second_handler: A SimpleHandler.
    common_prefix: The shared literal prefix of the patterns of the two
    handlers.
  Returns:
    The set of intersections of first_handler and second_handler. This is done
    by stripping the common prefix to create new SimpleHandlers which we call
    _IntersectTwoHandlers on, and then prepend the prefix to each member of that
    set.
  """
  stripped_first_handler = SimpleHandler(
      first_handler.pattern[len(common_prefix):], first_handler.properties)
  stripped_second_handler = SimpleHandler(
      second_handler.pattern[len(common_prefix):], second_handler.properties)
  stripped_handlers = _IntersectTwoHandlers(stripped_first_handler,
                                            stripped_second_handler)
  handlers = set()
  for stripped_handler in stripped_handlers:
    handlers.add(SimpleHandler(common_prefix + stripped_handler.pattern,
                               stripped_handler.properties))
  return handlers


def _HandleCommonSuffix(first_handler, second_handler, common_suffix):
  """Strips matching suffix from handlers and intersects the substrings."""

  stripped_first_handler = SimpleHandler(
      first_handler.pattern[:-len(common_suffix)], first_handler.properties)
  stripped_second_handler = SimpleHandler(
      second_handler.pattern[:-len(common_suffix)], second_handler.properties)
  stripped_handlers = _IntersectTwoHandlers(
      stripped_first_handler, stripped_second_handler)
  handlers = set()
  for stripped_handler in stripped_handlers:
    handlers.add(SimpleHandler(stripped_handler.pattern + common_suffix,
                               stripped_handler.properties))
  return handlers


def _SharedPrefix(pattern1, pattern2):
  """Returns the shared prefix of two patterns.

  Args:
    pattern1: A handler's pattern string
    pattern2: A handler's pattern string
  Returns:
    The shared prefix of the two patterns, up to the index of the first
    wildcard of either pattern. For example, the shared prefix of "a*bd" and
    "ac*d" is a. The shared prefix of "*x" and "y" is the empty string. The
    shared prefix of "john" and "johnny" is the empty string, and the shared
    prefix of "bc*" and "c*" is also the empty string.
  """
  first_star1 = (pattern1 + '*').find('*')
  first_star2 = (pattern2 + '*').find('*')
  if (first_star1, first_star2) != (len(pattern1), len(pattern2)):
    min_star = min(first_star1, first_star2)
    if min_star and pattern1[:min_star] == pattern2[:min_star]:
      return pattern1[:min_star]
  return ''


def _SharedSuffix(pattern1, pattern2):
  """Returns the shared suffix of two patterns."""
  return _SharedPrefix(pattern1[::-1], pattern2[::-1])[::-1]