<s> """<STR_LIT>""" <EOL> import itertools <EOL> from google . appengine . api import datastore_types <EOL> from google . appengine . api import validation <EOL> from google . appengine . api import yaml_errors <EOL> from google . appengine . api import yaml_object <EOL> from google . appengine . datastore import datastore_pb <EOL> from google . appengine . datastore import entity_pb <EOL> class Property ( validation . Validated ) : <EOL> """<STR_LIT>""" <EOL> ATTRIBUTES = { <EOL> '<STR_LIT:name>' : validation . Type ( str , convert = False ) , <EOL> '<STR_LIT>' : validation . Options ( ( '<STR_LIT>' , ( '<STR_LIT>' , ) ) , <EOL> ( '<STR_LIT>' , ( '<STR_LIT>' , ) ) , <EOL> default = '<STR_LIT>' ) , <EOL> } <EOL> class Index ( validation . Validated ) : <EOL> """<STR_LIT>""" <EOL> ATTRIBUTES = { <EOL> '<STR_LIT>' : validation . Type ( str , convert = False ) , <EOL> '<STR_LIT>' : validation . Type ( bool , convert = False , default = False ) , <EOL> '<STR_LIT>' : validation . Optional ( validation . Repeated ( Property ) ) , <EOL> } <EOL> class IndexDefinitions ( validation . Validated ) : <EOL> """<STR_LIT>""" <EOL> ATTRIBUTES = { <EOL> '<STR_LIT>' : validation . Optional ( validation . Repeated ( Index ) ) , <EOL> } <EOL> def ParseIndexDefinitions ( document , open_fn = None ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> return yaml_object . BuildSingleObject ( IndexDefinitions , document ) <EOL> except yaml_errors . EmptyConfigurationFile : <EOL> return None <EOL> def ParseMultipleIndexDefinitions ( document ) : <EOL> """<STR_LIT>""" <EOL> return yaml_object . BuildObjects ( IndexDefinitions , document ) <EOL> def IndexDefinitionsToKeys ( indexes ) : <EOL> """<STR_LIT>""" <EOL> keyset = set ( ) <EOL> if indexes is not None : <EOL> if indexes . indexes : <EOL> for index in indexes . indexes : <EOL> keyset . add ( IndexToKey ( index ) ) <EOL> return keyset <EOL> def IndexToKey ( index ) : <EOL> """<STR_LIT>""" <EOL> props = [ ] <EOL> if index . properties is not None : <EOL> for prop in index . properties : <EOL> if prop . direction == '<STR_LIT>' : <EOL> direction = ASCENDING <EOL> else : <EOL> direction = DESCENDING <EOL> props . append ( ( prop . name , direction ) ) <EOL> return index . kind , index . ancestor , tuple ( props ) <EOL> ASCENDING = datastore_pb . Query_Order . ASCENDING <EOL> DESCENDING = datastore_pb . Query_Order . DESCENDING <EOL> EQUALITY_OPERATORS = set ( ( datastore_pb . Query_Filter . EQUAL , <EOL> ) ) <EOL> INEQUALITY_OPERATORS = set ( ( datastore_pb . Query_Filter . LESS_THAN , <EOL> datastore_pb . Query_Filter . LESS_THAN_OR_EQUAL , <EOL> datastore_pb . Query_Filter . GREATER_THAN , <EOL> datastore_pb . Query_Filter . GREATER_THAN_OR_EQUAL , <EOL> ) ) <EOL> EXISTS_OPERATORS = set ( ( datastore_pb . Query_Filter . EXISTS , <EOL> ) ) <EOL> _DIRECTION_MAP = { <EOL> '<STR_LIT>' : entity_pb . Index_Property . ASCENDING , <EOL> '<STR_LIT>' : entity_pb . Index_Property . ASCENDING , <EOL> '<STR_LIT>' : entity_pb . Index_Property . DESCENDING , <EOL> '<STR_LIT>' : entity_pb . Index_Property . DESCENDING , <EOL> } <EOL> def Normalize ( filters , orders , exists ) : <EOL> """<STR_LIT>""" <EOL> eq_properties = set ( ) <EOL> inequality_properties = set ( ) <EOL> for f in filters : <EOL> if f . op ( ) == datastore_pb . Query_Filter . IN and f . property_size ( ) == <NUM_LIT:1> : <EOL> f . set_op ( datastore_pb . Query_Filter . EQUAL ) <EOL> if f . op ( ) in EQUALITY_OPERATORS : <EOL> eq_properties . add ( f . property ( <NUM_LIT:0> ) . name ( ) ) <EOL> elif f . op ( ) in INEQUALITY_OPERATORS : <EOL> inequality_properties . add ( f . property ( <NUM_LIT:0> ) . name ( ) ) <EOL> eq_properties -= inequality_properties <EOL> remove_set = eq_properties . copy ( ) <EOL> new_orders = [ ] <EOL> for o in orders : <EOL> if o . property ( ) not in remove_set : <EOL> remove_set . add ( o . property ( ) ) <EOL> new_orders . append ( o ) <EOL> orders = new_orders <EOL> remove_set . update ( inequality_properties ) <EOL> new_filters = [ ] <EOL> for f in filters : <EOL> if f . op ( ) not in EXISTS_OPERATORS : <EOL> new_filters . append ( f ) <EOL> continue <EOL> name = f . property ( <NUM_LIT:0> ) . name ( ) <EOL> if name not in remove_set : <EOL> remove_set . add ( name ) <EOL> new_filters . append ( f ) <EOL> for prop in exists : <EOL> if prop not in remove_set : <EOL> remove_set . add ( prop ) <EOL> new_filter = datastore_pb . Query_Filter ( ) <EOL> new_filter . set_op ( datastore_pb . Query_Filter . EXISTS ) <EOL> new_prop = new_filter . add_property ( ) <EOL> new_prop . set_name ( prop ) <EOL> new_prop . set_multiple ( False ) <EOL> new_prop . mutable_value ( ) <EOL> new_filters . append ( new_filter ) <EOL> filters = new_filters <EOL> if datastore_types . KEY_SPECIAL_PROPERTY in eq_properties : <EOL> orders = [ ] <EOL> new_orders = [ ] <EOL> for o in orders : <EOL> if o . property ( ) == datastore_types . KEY_SPECIAL_PROPERTY : <EOL> new_orders . append ( o ) <EOL> break <EOL> new_orders . append ( o ) <EOL> orders = new_orders <EOL> return ( filters , orders ) <EOL> def RemoveNativelySupportedComponents ( filters , orders , exists ) : <EOL> """<STR_LIT>""" <EOL> ( filters , orders ) = Normalize ( filters , orders , exists ) <EOL> for f in filters : <EOL> if f . op ( ) in EXISTS_OPERATORS : <EOL> return ( filters , orders ) <EOL> has_key_desc_order = False <EOL> if orders and orders [ - <NUM_LIT:1> ] . property ( ) == datastore_types . KEY_SPECIAL_PROPERTY : <EOL> if orders [ - <NUM_LIT:1> ] . direction ( ) == ASCENDING : <EOL> orders = orders [ : - <NUM_LIT:1> ] <EOL> else : <EOL> has_key_desc_order = True <EOL> if not has_key_desc_order : <EOL> for f in filters : <EOL> if ( f . op ( ) in INEQUALITY_OPERATORS and <EOL> f . property ( <NUM_LIT:0> ) . name ( ) != datastore_types . KEY_SPECIAL_PROPERTY ) : <EOL> break <EOL> else : <EOL> filters = [ f for f in filters <EOL> if f . property ( <NUM_LIT:0> ) . name ( ) != datastore_types . KEY_SPECIAL_PROPERTY ] <EOL> return ( filters , orders ) <EOL> def CompositeIndexForQuery ( query ) : <EOL> """<STR_LIT>""" <EOL> required = True <EOL> kind = query . kind ( ) <EOL> ancestor = query . has_ancestor ( ) <EOL> filters = query . filter_list ( ) <EOL> orders = query . order_list ( ) <EOL> for filter in filters : <EOL> assert filter . op ( ) != datastore_pb . Query_Filter . IN , '<STR_LIT>' <EOL> nprops = len ( filter . property_list ( ) ) <EOL> assert nprops == <NUM_LIT:1> , '<STR_LIT>' % nprops <EOL> if not kind : <EOL> required = False <EOL> exists = list ( query . property_name_list ( ) ) <EOL> exists . extend ( query . group_by_property_name_list ( ) ) <EOL> filters , orders = RemoveNativelySupportedComponents ( filters , orders , exists ) <EOL> eq_filters = [ f for f in filters if f . op ( ) in EQUALITY_OPERATORS ] <EOL> ineq_filters = [ f for f in filters if f . op ( ) in INEQUALITY_OPERATORS ] <EOL> exists_filters = [ f for f in filters if f . op ( ) in EXISTS_OPERATORS ] <EOL> assert ( len ( eq_filters ) + len ( ineq_filters ) + <EOL> len ( exists_filters ) ) == len ( filters ) , '<STR_LIT>' <EOL> if ( kind and not ineq_filters and not exists_filters and <EOL> not orders ) : <EOL> names = set ( f . property ( <NUM_LIT:0> ) . name ( ) for f in eq_filters ) <EOL> if not names . intersection ( datastore_types . _SPECIAL_PROPERTIES ) : <EOL> required = False <EOL> ineq_property = None <EOL> if ineq_filters : <EOL> for filter in ineq_filters : <EOL> if ( filter . property ( <NUM_LIT:0> ) . name ( ) == <EOL> datastore_types . _UNAPPLIED_LOG_TIMESTAMP_SPECIAL_PROPERTY ) : <EOL> continue <EOL> if not ineq_property : <EOL> ineq_property = filter . property ( <NUM_LIT:0> ) . name ( ) <EOL> else : <EOL> assert filter . property ( <NUM_LIT:0> ) . name ( ) == ineq_property <EOL> group_by_props = set ( query . group_by_property_name_list ( ) ) <EOL> prefix = frozenset ( f . property ( <NUM_LIT:0> ) . name ( ) for f in eq_filters ) <EOL> postfix_ordered = [ ( order . property ( ) , order . direction ( ) ) for order in orders ] <EOL> postfix_group_by = frozenset ( f . property ( <NUM_LIT:0> ) . name ( ) for f in exists_filters <EOL> if f . property ( <NUM_LIT:0> ) . name ( ) in group_by_props ) <EOL> postfix_unordered = frozenset ( f . property ( <NUM_LIT:0> ) . name ( ) for f in exists_filters <EOL> if f . property ( <NUM_LIT:0> ) . name ( ) not in group_by_props ) <EOL> if ineq_property : <EOL> if orders : <EOL> assert ineq_property == orders [ <NUM_LIT:0> ] . property ( ) <EOL> else : <EOL> postfix_ordered . append ( ( ineq_property , None ) ) <EOL> property_count = ( len ( prefix ) + len ( postfix_ordered ) + len ( postfix_group_by ) <EOL> + len ( postfix_unordered ) ) <EOL> if kind and not ancestor and property_count <= <NUM_LIT:1> : <EOL> required = False <EOL> if postfix_ordered : <EOL> prop , dir = postfix_ordered [ <NUM_LIT:0> ] <EOL> if prop == datastore_types . KEY_SPECIAL_PROPERTY and dir is DESCENDING : <EOL> required = True <EOL> props = prefix , ( tuple ( postfix_ordered ) , postfix_group_by , postfix_unordered ) <EOL> return required , kind , ancestor , props <EOL> def GetRecommendedIndexProperties ( properties ) : <EOL> """<STR_LIT>""" <EOL> prefix , postfix = properties <EOL> result = [ ] <EOL> for sub_list in itertools . chain ( ( prefix , ) , postfix ) : <EOL> if isinstance ( sub_list , ( frozenset , set ) ) : <EOL> for prop in sorted ( sub_list ) : <EOL> result . append ( ( prop , ASCENDING ) ) <EOL> else : <EOL> for prop , dir in sub_list : <EOL> result . append ( ( prop , dir if dir is not None else ASCENDING ) ) <EOL> return tuple ( result ) <EOL> def _MatchPostfix ( postfix_props , index_props ) : <EOL> """<STR_LIT>""" <EOL> index_props_rev = reversed ( index_props ) <EOL> for property_group in reversed ( postfix_props ) : <EOL> index_group_iter = itertools . islice ( index_props_rev , len ( property_group ) ) <EOL> if isinstance ( property_group , ( frozenset , set ) ) : <EOL> index_group = set ( prop for prop , _ in index_group_iter ) <EOL> if index_group != property_group : <EOL> return None <EOL> else : <EOL> index_group = list ( index_group_iter ) <EOL> if len ( index_group ) != len ( property_group ) : <EOL> return None <EOL> for ( index_prop , index_dir ) , ( prop , direction ) in itertools . izip ( <EOL> index_group , reversed ( property_group ) ) : <EOL> if index_prop != prop or ( direction and index_dir != direction ) : <EOL> return None <EOL> remaining = list ( index_props_rev ) <EOL> remaining . reverse ( ) <EOL> return remaining <EOL> def MinimalCompositeIndexForQuery ( query , index_defs ) : <EOL> """<STR_LIT>""" <EOL> required , kind , ancestor , ( prefix , postfix ) = CompositeIndexForQuery ( query ) <EOL> if not required : <EOL> return None <EOL> remaining_dict = { } <EOL> for definition in index_defs : <EOL> if ( kind != definition . kind or <EOL> ( not ancestor and definition . ancestor ) ) : <EOL> continue <EOL> _ , _ , index_props = IndexToKey ( definition ) <EOL> index_prefix = _MatchPostfix ( postfix , index_props ) <EOL> if index_prefix is None : <EOL> continue <EOL> remaining_index_props = set ( [ prop for prop , _ in index_prefix ] ) <EOL> if remaining_index_props - prefix : <EOL> continue <EOL> index_postfix = tuple ( index_props [ len ( index_prefix ) : ] ) <EOL> remaining = remaining_dict . get ( index_postfix ) <EOL> if remaining is None : <EOL> remaining = prefix . copy ( ) , ancestor <EOL> props_remaining , ancestor_remaining = remaining <EOL> props_remaining -= remaining_index_props <EOL> if definition . ancestor : <EOL> ancestor_remaining = False <EOL> if not ( props_remaining or ancestor_remaining ) : <EOL> return None <EOL> if ( props_remaining , ancestor_remaining ) == remaining : <EOL> continue <EOL> remaining_dict [ index_postfix ] = ( props_remaining , ancestor_remaining ) <EOL> if not remaining_dict : <EOL> return ( True , kind , ancestor , ( prefix , postfix ) ) <EOL> def calc_cost ( minimal_props , minimal_ancestor ) : <EOL> result = len ( minimal_props ) <EOL> if minimal_ancestor : <EOL> result += <NUM_LIT:2> <EOL> return result <EOL> minimal_postfix , remaining = remaining_dict . popitem ( ) <EOL> minimal_props , minimal_ancestor = remaining <EOL> minimal_cost = calc_cost ( minimal_props , minimal_ancestor ) <EOL> for index_postfix , ( props_remaining , ancestor_remaining ) in ( <EOL> remaining_dict . iteritems ( ) ) : <EOL> cost = calc_cost ( props_remaining , ancestor_remaining ) <EOL> if cost < minimal_cost : <EOL> minimal_cost = cost <EOL> minimal_postfix = index_postfix <EOL> minimal_props = props_remaining <EOL> minimal_ancestor = ancestor_remaining <EOL> props = frozenset ( minimal_props ) , ( minimal_postfix , frozenset ( ) , frozenset ( ) ) <EOL> return False , kind , minimal_ancestor , props <EOL> def IndexYamlForQuery ( kind , ancestor , props ) : <EOL> """<STR_LIT>""" <EOL> yaml = [ ] <EOL> yaml . append ( '<STR_LIT>' % kind ) <EOL> if ancestor : <EOL> yaml . append ( '<STR_LIT>' ) <EOL> if props : <EOL> yaml . append ( '<STR_LIT>' ) <EOL> for name , direction in props : <EOL> yaml . append ( '<STR_LIT>' % name ) <EOL> if direction == DESCENDING : <EOL> yaml . append ( '<STR_LIT>' ) <EOL> return '<STR_LIT:\n>' . join ( yaml ) <EOL> def IndexXmlForQuery ( kind , ancestor , props ) : <EOL> """<STR_LIT>""" <EOL> xml = [ ] <EOL> xml . append ( '<STR_LIT>' <EOL> % ( kind , '<STR_LIT:true>' if ancestor else '<STR_LIT:false>' ) ) <EOL> for name , direction in props : <EOL> xml . append ( '<STR_LIT>' <EOL> % ( name , '<STR_LIT>' if direction == ASCENDING else '<STR_LIT>' ) ) <EOL> xml . append ( '<STR_LIT>' ) <EOL> return '<STR_LIT:\n>' . join ( xml ) <EOL> def IndexDefinitionToProto ( app_id , index_definition ) : <EOL> """<STR_LIT>""" <EOL> proto = entity_pb . CompositeIndex ( ) <EOL> proto . set_app_id ( app_id ) <EOL> proto . set_id ( <NUM_LIT:0> ) <EOL> proto . set_state ( entity_pb . CompositeIndex . WRITE_ONLY ) <EOL> definition_proto = proto . mutable_definition ( ) <EOL> definition_proto . set_entity_type ( index_definition . kind ) <EOL> definition_proto . set_ancestor ( index_definition . ancestor ) <EOL> if index_definition . properties is not None : <EOL> for prop in index_definition . properties : <EOL> prop_proto = definition_proto . add_property ( ) <EOL> prop_proto . set_name ( prop . name ) <EOL> prop_proto . set_direction ( _DIRECTION_MAP [ prop . direction ] ) <EOL> return proto <EOL> def IndexDefinitionsToProtos ( app_id , index_definitions ) : <EOL> """<STR_LIT>""" <EOL> return [ IndexDefinitionToProto ( app_id , index ) <EOL> for index in index_definitions ] <EOL> def ProtoToIndexDefinition ( proto ) : <EOL> """<STR_LIT>""" <EOL> properties = [ ] <EOL> proto_index = proto . definition ( ) <EOL> for prop_proto in proto_index . property_list ( ) : <EOL> prop_definition = Property ( name = prop_proto . name ( ) ) <EOL> if prop_proto . direction ( ) == entity_pb . Index_Property . DESCENDING : <EOL> prop_definition . direction = '<STR_LIT>' <EOL> properties . append ( prop_definition ) <EOL> index = Index ( kind = proto_index . entity_type ( ) , properties = properties ) <EOL> if proto_index . ancestor ( ) : <EOL> index . ancestor = True <EOL> return index <EOL> def ProtosToIndexDefinitions ( protos ) : <EOL> """<STR_LIT>""" <EOL> return [ ProtoToIndexDefinition ( definition ) for definition in protos ] </s>
