Synnefo » snf-ganeti

#

#

# Copyright (C) 2010, 2011 Google Inc.

#

# This program is free software; you can redistribute it and/or modify

# it under the terms of the GNU General Public License as published by

# the Free Software Foundation; either version 2 of the License, or

# (at your option) any later version.

#

# This program is distributed in the hope that it will be useful, but

# WITHOUT ANY WARRANTY; without even the implied warranty of

# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

# General Public License for more details.

#

# You should have received a copy of the GNU General Public License

# along with this program; if not, write to the Free Software

# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA

# 02110-1301, USA.

"""Module for query operations

How it works:

  - Add field definitions

    - See how L{NODE_FIELDS} is built

    - Each field gets:

      - Query field definition (L{objects.QueryFieldDefinition}, use

        L{_MakeField} for creating), containing:

          - Name, must be lowercase and match L{FIELD_NAME_RE}

          - Title for tables, must not contain whitespace and match

            L{TITLE_RE}

          - Value data type, e.g. L{constants.QFT_NUMBER}

          - Human-readable description, must not end with punctuation or

            contain newlines

      - Data request type, see e.g. C{NQ_*}

      - OR-ed flags, see C{QFF_*}

      - A retrieval function, see L{Query.__init__} for description

    - Pass list of fields through L{_PrepareFieldList} for preparation and

      checks

  - Instantiate L{Query} with prepared field list definition and selected fields

  - Call L{Query.RequestedData} to determine what data to collect/compute

  - Call L{Query.Query} or L{Query.OldStyleQuery} with collected data and use

    result

      - Data container must support iteration using C{__iter__}

      - Items are passed to retrieval functions and can have any format

  - Call L{Query.GetFields} to get list of definitions for selected fields

@attention: Retrieval functions must be idempotent. They can be called multiple

  times, in any order and any number of times.

"""

import logging

import operator

import re

from ganeti import constants

from ganeti import errors

from ganeti import utils

from ganeti import compat

from ganeti import objects

from ganeti import ht

from ganeti import qlang

from ganeti.constants import (QFT_UNKNOWN, QFT_TEXT, QFT_BOOL, QFT_NUMBER,

                              QFT_UNIT, QFT_TIMESTAMP, QFT_OTHER,

                              RS_NORMAL, RS_UNKNOWN, RS_NODATA,

                              RS_UNAVAIL, RS_OFFLINE)

# Constants for requesting data from the caller/data provider. Each property

# collected/computed separately by the data provider should have its own to

# only collect the requested data and not more.

(NQ_CONFIG,

 NQ_INST,

 NQ_LIVE,

 NQ_GROUP,

 NQ_OOB) = range(1, 6)

(IQ_CONFIG,

 IQ_LIVE,

 IQ_DISKUSAGE,

 IQ_CONSOLE) = range(100, 104)

(LQ_MODE,

 LQ_OWNER,

 LQ_PENDING) = range(10, 13)

(GQ_CONFIG,

 GQ_NODE,

 GQ_INST) = range(200, 203)

# Query field flags

QFF_HOSTNAME = 0x01

QFF_IP_ADDRESS = 0x02

# Next values: 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x100, 0x200

QFF_ALL = (QFF_HOSTNAME | QFF_IP_ADDRESS)

FIELD_NAME_RE = re.compile(r"^[a-z0-9/._]+$")

TITLE_RE = re.compile(r"^[^\s]+$")

DOC_RE = re.compile(r"^[A-Z].*[^.,?!]$")

#: Verification function for each field type

_VERIFY_FN = {

  QFT_UNKNOWN: ht.TNone,

  QFT_TEXT: ht.TString,

  QFT_BOOL: ht.TBool,

  QFT_NUMBER: ht.TInt,

  QFT_UNIT: ht.TInt,

  QFT_TIMESTAMP: ht.TOr(ht.TInt, ht.TFloat),

  QFT_OTHER: lambda _: True,

  }

# Unique objects for special field statuses

_FS_UNKNOWN = object()

_FS_NODATA = object()

_FS_UNAVAIL = object()

_FS_OFFLINE = object()

#: List of all special status

_FS_ALL = frozenset([_FS_UNKNOWN, _FS_NODATA, _FS_UNAVAIL, _FS_OFFLINE])

#: VType to QFT mapping

_VTToQFT = {

  # TODO: fix validation of empty strings

  constants.VTYPE_STRING: QFT_OTHER, # since VTYPE_STRINGs can be empty

  constants.VTYPE_MAYBE_STRING: QFT_OTHER,

  constants.VTYPE_BOOL: QFT_BOOL,

  constants.VTYPE_SIZE: QFT_UNIT,

  constants.VTYPE_INT: QFT_NUMBER,

  }

_SERIAL_NO_DOC = "%s object serial number, incremented on each modification"

def _GetUnknownField(ctx, item): # pylint: disable-msg=W0613

  """Gets the contents of an unknown field.

  """

  return _FS_UNKNOWN

def _GetQueryFields(fielddefs, selected):

  """Calculates the internal list of selected fields.

  Unknown fields are returned as L{constants.QFT_UNKNOWN}.

  @type fielddefs: dict

  @param fielddefs: Field definitions

  @type selected: list of strings

  @param selected: List of selected fields

  """

  result = []

  for name in selected:

    try:

      fdef = fielddefs[name]

    except KeyError:

      fdef = (_MakeField(name, name, QFT_UNKNOWN, "Unknown field '%s'" % name),

              None, 0, _GetUnknownField)

    assert len(fdef) == 4

    result.append(fdef)

  return result

def GetAllFields(fielddefs):

  """Extract L{objects.QueryFieldDefinition} from field definitions.

  @rtype: list of L{objects.QueryFieldDefinition}

  """

  return [fdef for (fdef, _, _, _) in fielddefs]

class _FilterHints:

  """Class for filter analytics.

  When filters are used, the user of the L{Query} class usually doesn't know

  exactly which items will be necessary for building the result. It therefore

  has to prepare and compute the input data for potentially returning

  everything.

  There are two ways to optimize this. The first, and simpler, is to assign

  each field a group of data, so that the caller can determine which

  computations are necessary depending on the data groups requested. The list

  of referenced groups must also be computed for fields referenced in the

  filter.

  The second is restricting the items based on a primary key. The primary key

  is usually a unique name (e.g. a node name). This class extracts all

  referenced names from a filter. If it encounters any filter condition which

  disallows such a list to be determined (e.g. a non-equality filter), all

  names will be requested.

  The end-effect is that any operation other than L{qlang.OP_OR} and

  L{qlang.OP_EQUAL} will make the query more expensive.

  """

  def __init__(self, namefield):

    """Initializes this class.

    @type namefield: string

    @param namefield: Field caller is interested in

    """

    self._namefield = namefield

    #: Whether all names need to be requested (e.g. if a non-equality operator

    #: has been used)

    self._allnames = False

    #: Which names to request

    self._names = None

    #: Data kinds referenced by the filter (used by L{Query.RequestedData})

    self._datakinds = set()

  def RequestedNames(self):

    """Returns all requested values.

    Returns C{None} if list of values can't be determined (e.g. encountered

    non-equality operators).

    @rtype: list

    """

    if self._allnames or self._names is None:

      return None

    return utils.UniqueSequence(self._names)

  def ReferencedData(self):

    """Returns all kinds of data referenced by the filter.

    """

    return frozenset(self._datakinds)

  def _NeedAllNames(self):

    """Changes internal state to request all names.

    """

    self._allnames = True

    self._names = None

  def NoteLogicOp(self, op):

    """Called when handling a logic operation.

    @type op: string

    @param op: Operator

    """

    if op != qlang.OP_OR:

      self._NeedAllNames()

  def NoteUnaryOp(self, op): # pylint: disable-msg=W0613

    """Called when handling an unary operation.

    @type op: string

    @param op: Operator

    """

    self._NeedAllNames()

  def NoteBinaryOp(self, op, datakind, name, value):

    """Called when handling a binary operation.

    @type op: string

    @param op: Operator

    @type name: string

    @param name: Left-hand side of operator (field name)

    @param value: Right-hand side of operator

    """

    if datakind is not None:

      self._datakinds.add(datakind)

    if self._allnames:

      return

    # If any operator other than equality was used, all names need to be

    # retrieved

    if op == qlang.OP_EQUAL and name == self._namefield:

      if self._names is None:

        self._names = []

      self._names.append(value)

    else:

      self._NeedAllNames()

def _WrapLogicOp(op_fn, sentences, ctx, item):

  """Wrapper for logic operator functions.

  """

  return op_fn(fn(ctx, item) for fn in sentences)

def _WrapUnaryOp(op_fn, inner, ctx, item):

  """Wrapper for unary operator functions.

  """

  return op_fn(inner(ctx, item))

def _WrapBinaryOp(op_fn, retrieval_fn, value, ctx, item):

  """Wrapper for binary operator functions.

  """

  return op_fn(retrieval_fn(ctx, item), value)

def _WrapNot(fn, lhs, rhs):

  """Negates the result of a wrapped function.

  """

  return not fn(lhs, rhs)

class _FilterCompilerHelper:

  """Converts a query filter to a callable usable for filtering.

  """

  # String statement has no effect, pylint: disable-msg=W0105

  #: How deep filters can be nested

  _LEVELS_MAX = 10

  # Unique identifiers for operator groups

  (_OPTYPE_LOGIC,

   _OPTYPE_UNARY,

   _OPTYPE_BINARY) = range(1, 4)

  """Functions for equality checks depending on field flags.

  List of tuples containing flags and a callable receiving the left- and

  right-hand side of the operator. The flags are an OR-ed value of C{QFF_*}

  (e.g. L{QFF_HOSTNAME}).

  Order matters. The first item with flags will be used. Flags are checked

  using binary AND.

  """

  _EQUALITY_CHECKS = [

    (QFF_HOSTNAME,

     lambda lhs, rhs: utils.MatchNameComponent(rhs, [lhs],

                                               case_sensitive=False)),

    (None, operator.eq),

    ]

  """Known operators

  Operator as key (C{qlang.OP_*}), value a tuple of operator group

  (C{_OPTYPE_*}) and a group-specific value:

    - C{_OPTYPE_LOGIC}: Callable taking any number of arguments; used by

      L{_HandleLogicOp}

    - C{_OPTYPE_UNARY}: Always C{None}; details handled by L{_HandleUnaryOp}

    - C{_OPTYPE_BINARY}: Callable taking exactly two parameters, the left- and

      right-hand side of the operator, used by L{_HandleBinaryOp}

  """

  _OPS = {

    # Logic operators

    qlang.OP_OR: (_OPTYPE_LOGIC, compat.any),

    qlang.OP_AND: (_OPTYPE_LOGIC, compat.all),

    # Unary operators

    qlang.OP_NOT: (_OPTYPE_UNARY, None),

    qlang.OP_TRUE: (_OPTYPE_UNARY, None),

    # Binary operators

    qlang.OP_EQUAL: (_OPTYPE_BINARY, _EQUALITY_CHECKS),

    qlang.OP_NOT_EQUAL:

      (_OPTYPE_BINARY, [(flags, compat.partial(_WrapNot, fn))

                        for (flags, fn) in _EQUALITY_CHECKS]),

    qlang.OP_GLOB: (_OPTYPE_BINARY, NotImplemented),

    qlang.OP_REGEXP: (_OPTYPE_BINARY, NotImplemented),

    qlang.OP_CONTAINS: (_OPTYPE_BINARY, [

      (None, operator.contains),

      ]),

    }

  def __init__(self, fields):

    """Initializes this class.

    @param fields: Field definitions (return value of L{_PrepareFieldList})

    """

    self._fields = fields

    self._hints = None

    self._op_handler = None

  def __call__(self, hints, filter_):

    """Converts a query filter into a callable function.

    @type hints: L{_FilterHints} or None

    @param hints: Callbacks doing analysis on filter

    @type filter_: list

    @param filter_: Filter structure

    @rtype: callable

    @return: Function receiving context and item as parameters, returning

             boolean as to whether item matches filter

    """

    self._op_handler = {

      self._OPTYPE_LOGIC:

        (self._HandleLogicOp, getattr(hints, "NoteLogicOp", None)),

      self._OPTYPE_UNARY:

        (self._HandleUnaryOp, getattr(hints, "NoteUnaryOp", None)),

      self._OPTYPE_BINARY:

        (self._HandleBinaryOp, getattr(hints, "NoteBinaryOp", None)),

      }

    try:

      filter_fn = self._Compile(filter_, 0)

    finally:

      self._op_handler = None

    return filter_fn

  def _Compile(self, filter_, level):

    """Inner function for converting filters.

    Calls the correct handler functions for the top-level operator. This

    function is called recursively (e.g. for logic operators).

    """

    if not (isinstance(filter_, (list, tuple)) and filter_):

      raise errors.ParameterError("Invalid filter on level %s" % level)

    # Limit recursion

    if level >= self._LEVELS_MAX:

      raise errors.ParameterError("Only up to %s levels are allowed (filter"

                                  " nested too deep)" % self._LEVELS_MAX)

    # Create copy to be modified

    operands = filter_[:]

    op = operands.pop(0)

    try:

      (kind, op_data) = self._OPS[op]

    except KeyError:

      raise errors.ParameterError("Unknown operator '%s'" % op)

    (handler, hints_cb) = self._op_handler[kind]

    return handler(hints_cb, level, op, op_data, operands)

  def _LookupField(self, name):

    """Returns a field definition by name.

    """

    try:

      return self._fields[name]

    except KeyError:

      raise errors.ParameterError("Unknown field '%s'" % name)

  def _HandleLogicOp(self, hints_fn, level, op, op_fn, operands):

    """Handles logic operators.

    @type hints_fn: callable

    @param hints_fn: Callback doing some analysis on the filter

    @type level: integer

    @param level: Current depth

    @type op: string

    @param op: Operator

    @type op_fn: callable

    @param op_fn: Function implementing operator

    @type operands: list

    @param operands: List of operands

    """

    if hints_fn:

      hints_fn(op)

    return compat.partial(_WrapLogicOp, op_fn,

                          [self._Compile(op, level + 1) for op in operands])

  def _HandleUnaryOp(self, hints_fn, level, op, op_fn, operands):

    """Handles unary operators.

    @type hints_fn: callable

    @param hints_fn: Callback doing some analysis on the filter

    @type level: integer

    @param level: Current depth

    @type op: string

    @param op: Operator

    @type op_fn: callable

    @param op_fn: Function implementing operator

    @type operands: list

    @param operands: List of operands

    """

    assert op_fn is None

    if hints_fn:

      hints_fn(op)

    if len(operands) != 1:

      raise errors.ParameterError("Unary operator '%s' expects exactly one"

                                  " operand" % op)

    if op == qlang.OP_TRUE:

      (_, _, _, retrieval_fn) = self._LookupField(operands[0])

      op_fn = operator.truth

      arg = retrieval_fn

    elif op == qlang.OP_NOT:

      op_fn = operator.not_

      arg = self._Compile(operands[0], level + 1)

    else:

      raise errors.ProgrammerError("Can't handle operator '%s'" % op)

    return compat.partial(_WrapUnaryOp, op_fn, arg)

  def _HandleBinaryOp(self, hints_fn, level, op, op_data, operands):

    """Handles binary operators.

    @type hints_fn: callable

    @param hints_fn: Callback doing some analysis on the filter

    @type level: integer

    @param level: Current depth

    @type op: string

    @param op: Operator

    @param op_data: Functions implementing operators

    @type operands: list

    @param operands: List of operands

    """

    # Unused arguments, pylint: disable-msg=W0613

    try:

      (name, value) = operands

    except (ValueError, TypeError):

      raise errors.ParameterError("Invalid binary operator, expected exactly"

                                  " two operands")

    (fdef, datakind, field_flags, retrieval_fn) = self._LookupField(name)

    assert fdef.kind != QFT_UNKNOWN

    # TODO: Type conversions?

    verify_fn = _VERIFY_FN[fdef.kind]

    if not verify_fn(value):

      raise errors.ParameterError("Unable to compare field '%s' (type '%s')"

                                  " with '%s', expected %s" %

                                  (name, fdef.kind, value.__class__.__name__,

                                   verify_fn))

    if hints_fn:

      hints_fn(op, datakind, name, value)

    for (fn_flags, fn) in op_data:

      if fn_flags is None or fn_flags & field_flags:

        return compat.partial(_WrapBinaryOp, fn, retrieval_fn, value)

    raise errors.ProgrammerError("Unable to find operator implementation"

                                 " (op '%s', flags %s)" % (op, field_flags))

def _CompileFilter(fields, hints, filter_):

  """Converts a query filter into a callable function.

  See L{_FilterCompilerHelper} for details.

  @rtype: callable

  """

  return _FilterCompilerHelper(fields)(hints, filter_)

class Query:

  def __init__(self, fieldlist, selected, filter_=None, namefield=None):

    """Initializes this class.

    The field definition is a dictionary with the field's name as a key and a

    tuple containing, in order, the field definition object

    (L{objects.QueryFieldDefinition}, the data kind to help calling code

    collect data and a retrieval function. The retrieval function is called

    with two parameters, in order, the data container and the item in container

    (see L{Query.Query}).

    Users of this class can call L{RequestedData} before preparing the data

    container to determine what data is needed.

    @type fieldlist: dictionary

    @param fieldlist: Field definitions

    @type selected: list of strings

    @param selected: List of selected fields

    """

    assert namefield is None or namefield in fieldlist

    self._fields = _GetQueryFields(fieldlist, selected)

    self._filter_fn = None

    self._requested_names = None

    self._filter_datakinds = frozenset()

    if filter_ is not None:

      # Collect requested names if wanted

      if namefield:

        hints = _FilterHints(namefield)

      else:

        hints = None

      # Build filter function

      self._filter_fn = _CompileFilter(fieldlist, hints, filter_)

      if hints:

        self._requested_names = hints.RequestedNames()

        self._filter_datakinds = hints.ReferencedData()

    if namefield is None:

      self._name_fn = None

    else:

      (_, _, _, self._name_fn) = fieldlist[namefield]

  def RequestedNames(self):

    """Returns all names referenced in the filter.

    If there is no filter or operators are preventing determining the exact

    names, C{None} is returned.

    """

    return self._requested_names

  def RequestedData(self):

    """Gets requested kinds of data.

    @rtype: frozenset

    """

    return (self._filter_datakinds |

            frozenset(datakind for (_, datakind, _, _) in self._fields

                      if datakind is not None))

  def GetFields(self):

    """Returns the list of fields for this query.

    Includes unknown fields.

    @rtype: List of L{objects.QueryFieldDefinition}

    """

    return GetAllFields(self._fields)

  def Query(self, ctx, sort_by_name=True):

    """Execute a query.

    @param ctx: Data container passed to field retrieval functions, must

      support iteration using C{__iter__}

    @type sort_by_name: boolean

    @param sort_by_name: Whether to sort by name or keep the input data's

      ordering

    """

    sort = (self._name_fn and sort_by_name)

    result = []

    for idx, item in enumerate(ctx):

      if not (self._filter_fn is None or self._filter_fn(ctx, item)):

        continue

      row = [_ProcessResult(fn(ctx, item)) for (_, _, _, fn) in self._fields]

      # Verify result

      if __debug__:

        _VerifyResultRow(self._fields, row)

      if sort:

        (status, name) = _ProcessResult(self._name_fn(ctx, item))

        assert status == constants.RS_NORMAL

        # TODO: Are there cases where we wouldn't want to use NiceSort?

        result.append((utils.NiceSortKey(name), idx, row))

      else:

        result.append(row)

    if not sort:

      return result

    # TODO: Would "heapq" be more efficient than sorting?

    # Sorting in-place instead of using "sorted()"

    result.sort()

    assert not result or (len(result[0]) == 3 and len(result[-1]) == 3)

    return map(operator.itemgetter(2), result)

  def OldStyleQuery(self, ctx, sort_by_name=True):

    """Query with "old" query result format.

    See L{Query.Query} for arguments.

    """

    unknown = set(fdef.name for (fdef, _, _, _) in self._fields

                  if fdef.kind == QFT_UNKNOWN)

    if unknown:

      raise errors.OpPrereqError("Unknown output fields selected: %s" %

                                 (utils.CommaJoin(unknown), ),

                                 errors.ECODE_INVAL)

    return [[value for (_, value) in row]

            for row in self.Query(ctx, sort_by_name=sort_by_name)]

def _ProcessResult(value):

  """Converts result values into externally-visible ones.

  """

  if value is _FS_UNKNOWN:

    return (RS_UNKNOWN, None)

  elif value is _FS_NODATA:

    return (RS_NODATA, None)

  elif value is _FS_UNAVAIL:

    return (RS_UNAVAIL, None)

  elif value is _FS_OFFLINE:

    return (RS_OFFLINE, None)

  else:

    return (RS_NORMAL, value)

def _VerifyResultRow(fields, row):

  """Verifies the contents of a query result row.

  @type fields: list

  @param fields: Field definitions for result

  @type row: list of tuples

  @param row: Row data

  """

  assert len(row) == len(fields)

  errs = []

  for ((status, value), (fdef, _, _, _)) in zip(row, fields):

    if status == RS_NORMAL:

      if not _VERIFY_FN[fdef.kind](value):

        errs.append("normal field %s fails validation (value is %s)" %

                    (fdef.name, value))

    elif value is not None:

      errs.append("abnormal field %s has a non-None value" % fdef.name)

  assert not errs, ("Failed validation: %s in row %s" %

                    (utils.CommaJoin(errors), row))

def _PrepareFieldList(fields, aliases):

  """Prepares field list for use by L{Query}.