/** * @file query/types.h * @brief Internal types and functions for queries. */ #ifndef FLECS_QUERY_TYPES #define FLECS_QUERY_TYPES typedef struct ecs_query_impl_t ecs_query_impl_t; typedef uint8_t ecs_var_id_t; typedef int16_t ecs_query_lbl_t; typedef ecs_flags64_t ecs_write_flags_t; #define flecs_query_impl(query) (ECS_CONST_CAST(ecs_query_impl_t*, query)) #define EcsQueryMaxVarCount (64) #define EcsVarNone ((ecs_var_id_t)-1) #define EcsThisName "this" /* -- Variable types -- */ typedef enum { EcsVarEntity, /* Variable that stores an entity id */ EcsVarTable, /* Variable that stores a table */ EcsVarAny /* Used when requesting either entity or table var */ } ecs_var_kind_t; typedef struct ecs_query_var_t { int8_t kind; /* variable kind (EcsVarEntity or EcsVarTable) */ bool anonymous; /* variable is anonymous */ ecs_var_id_t id; /* variable id */ ecs_var_id_t table_id; /* id to table variable, if any */ ecs_var_id_t base_id; /* id to base entity variable, for lookups */ const char *name; /* variable name */ const char *lookup; /* Lookup string for variable */ #ifdef FLECS_DEBUG const char *label; /* for debugging */ #endif } ecs_query_var_t; /* Placeholder values for queries with only $this variable */ extern ecs_query_var_t flecs_this_array; extern char *flecs_this_name_array; /* -- Instruction kinds -- */ typedef enum { EcsQueryAll, /* Yield all tables */ EcsQueryAnd, /* And operator: find or match id against variable source */ EcsQueryAndAny, /* And operator with support for matching Any src/id */ EcsQueryAndWcTgt, /* And operator for (*, T) queries */ EcsQueryTriv, /* Trivial search (batches multiple terms) */ EcsQueryCache, /* Cached search */ EcsQueryIsCache, /* Cached search for queries that are entirely cached */ EcsQueryUp, /* Up traversal */ EcsQuerySelfUp, /* Self|up traversal */ EcsQueryWith, /* Match id against fixed or variable source */ EcsQueryWithWcTgt, /* Match (*, T) id against fixed or variable source */ EcsQueryTrav, /* Support for transitive/reflexive queries */ EcsQueryAndFrom, /* AndFrom operator */ EcsQueryOrFrom, /* OrFrom operator */ EcsQueryNotFrom, /* NotFrom operator */ EcsQueryIds, /* Test for existence of ids matching wildcard */ EcsQueryIdsRight, /* Find ids in use that match (R, *) wildcard */ EcsQueryIdsLeft, /* Find ids in use that match (*, T) wildcard */ EcsQueryEach, /* Iterate entities in table, populate entity variable */ EcsQueryStore, /* Store table or entity in variable */ EcsQueryReset, /* Reset value of variable to wildcard (*) */ EcsQueryOr, /* Or operator */ EcsQueryOptional, /* Optional operator */ EcsQueryIfVar, /* Conditional execution on whether variable is set */ EcsQueryIfSet, /* Conditional execution on whether term is set */ EcsQueryNot, /* Sets iterator state after term was not matched */ EcsQueryEnd, /* End of control flow block */ EcsQueryPredEq, /* Test if variable is equal to, or assign to if not set */ EcsQueryPredNeq, /* Test if variable is not equal to */ EcsQueryPredEqName, /* Same as EcsQueryPredEq but with matching by name */ EcsQueryPredNeqName, /* Same as EcsQueryPredNeq but with matching by name */ EcsQueryPredEqMatch, /* Same as EcsQueryPredEq but with fuzzy matching by name */ EcsQueryPredNeqMatch, /* Same as EcsQueryPredNeq but with fuzzy matching by name */ EcsQueryMemberEq, /* Compare member value */ EcsQueryMemberNeq, /* Compare member value */ EcsQueryToggle, /* Evaluate toggle bitset, if present */ EcsQueryToggleOption, /* Toggle for optional terms */ EcsQuerySparse, /* Evaluate sparse component */ EcsQuerySparseNot, /* Evaluate sparse component with not operator */ EcsQuerySparseSelfUp, EcsQuerySparseUp, EcsQuerySparseWith, /* Evaluate sparse component against fixed or variable source */ EcsQueryLookup, /* Lookup relative to variable */ EcsQuerySetVars, /* Populate it.sources from variables */ EcsQuerySetThis, /* Populate This entity variable */ EcsQuerySetFixed, /* Set fixed source entity ids */ EcsQuerySetIds, /* Set fixed (component) ids */ EcsQuerySetId, /* Set id if not set */ EcsQueryContain, /* Test if table contains entity */ EcsQueryPairEq, /* Test if both elements of pair are the same */ EcsQueryYield, /* Yield result back to application */ EcsQueryNothing /* Must be last */ } ecs_query_op_kind_t; /* Op flags to indicate if ecs_query_ref_t is entity or variable */ #define EcsQueryIsEntity (1 << 0) #define EcsQueryIsVar (1 << 1) #define EcsQueryIsSelf (1 << 6) /* Op flags used to shift EcsQueryIsEntity and EcsQueryIsVar */ #define EcsQuerySrc 0 #define EcsQueryFirst 2 #define EcsQuerySecond 4 /* References to variable or entity */ typedef union { ecs_var_id_t var; ecs_entity_t entity; } ecs_query_ref_t; /* Query instruction */ typedef struct ecs_query_op_t { uint8_t kind; /* Instruction kind */ ecs_flags8_t flags; /* Flags storing whether 1st/2nd are variables */ int8_t field_index; /* Query field corresponding with operation */ int8_t term_index; /* Query term corresponding with operation */ ecs_query_lbl_t prev; /* Backtracking label (no data) */ ecs_query_lbl_t next; /* Forwarding label. Must come after prev */ ecs_query_lbl_t other; /* Misc register used for control flow */ ecs_flags16_t match_flags; /* Flags that modify matching behavior */ ecs_query_ref_t src; ecs_query_ref_t first; ecs_query_ref_t second; ecs_flags64_t written; /* Bitset with variables written by op */ } ecs_query_op_t; /* All context */ typedef struct { int32_t cur; ecs_table_record_t dummy_tr; } ecs_query_all_ctx_t; /* And context */ typedef struct { ecs_component_record_t *cr; ecs_table_cache_iter_t it; int16_t column; int16_t remaining; bool non_fragmenting; } ecs_query_and_ctx_t; /* Sparse context */ typedef struct { ecs_query_and_ctx_t and_; /* For mixed sparse/non-sparse results */ ecs_sparse_t *sparse; ecs_table_range_t range; int32_t cur; bool self; bool exclusive; ecs_component_record_t *cr; ecs_table_range_t prev_range; int32_t prev_cur; } ecs_query_sparse_ctx_t; /* Down traversal cache (for resolving up queries w/unknown source) */ typedef struct { ecs_table_t *table; bool leaf; /* Table owns and inherits id (for Up queries without Self) */ } ecs_trav_down_elem_t; typedef struct { ecs_vec_t elems; /* vector */ bool ready; } ecs_trav_down_t; typedef struct { ecs_entity_t src; ecs_id_t id; ecs_table_record_t *tr; bool ready; } ecs_trav_up_t; typedef enum { EcsTravUp = 1, EcsTravDown = 2 } ecs_trav_direction_t; typedef struct { ecs_map_t src; /* map or map */ ecs_id_t with; ecs_trav_direction_t dir; } ecs_trav_up_cache_t; /* And up context */ typedef struct { ecs_table_t *table; int32_t row; int32_t end; ecs_entity_t trav; ecs_id_t with; ecs_id_t matched; ecs_component_record_t *cr_with; ecs_component_record_t *cr_trav; ecs_trav_down_t *down; int32_t cache_elem; ecs_trav_up_cache_t cache; } ecs_query_up_impl_t; typedef struct { union { ecs_query_and_ctx_t and; ecs_query_sparse_ctx_t sparse_; } is; /* Indirection because otherwise the ctx struct gets too large */ ecs_query_up_impl_t *impl; } ecs_query_up_ctx_t; /* Cache for storing results of upward/downward "all" traversal. This type of * traversal iterates and caches the entire tree. */ typedef struct { ecs_entity_t entity; ecs_component_record_t *cr; const ecs_table_record_t *tr; } ecs_trav_elem_t; typedef struct { ecs_id_t id; ecs_component_record_t *cr; ecs_vec_t entities; bool up; } ecs_trav_cache_t; /* Trav context */ typedef struct { ecs_query_and_ctx_t and; int32_t index; int32_t offset; int32_t count; ecs_trav_cache_t cache; bool yield_reflexive; } ecs_query_trav_ctx_t; /* Eq context */ typedef struct { ecs_table_range_t range; int32_t index; int16_t name_col; bool redo; } ecs_query_eq_ctx_t; /* Each context */ typedef struct { int32_t row; } ecs_query_each_ctx_t; /* Setthis context */ typedef struct { ecs_table_range_t range; } ecs_query_setthis_ctx_t; /* Ids context */ typedef struct { ecs_component_record_t *cur; } ecs_query_ids_ctx_t; /* Control flow context */ typedef struct { ecs_query_lbl_t op_index; ecs_id_t field_id; bool is_set; } ecs_query_ctrl_ctx_t; /* Trivial iterator context */ typedef struct { ecs_table_cache_iter_t it; const ecs_table_record_t *tr; int32_t start_from; int32_t first_to_eval; } ecs_query_trivial_ctx_t; /* *From operator iterator context */ typedef struct { ecs_query_and_ctx_t and; ecs_entity_t type_id; ecs_type_t *type; int32_t first_id_index; int32_t cur_id_index; } ecs_query_xfrom_ctx_t; /* Member equality context */ typedef struct { ecs_query_each_ctx_t each; void *data; } ecs_query_membereq_ctx_t; /* Toggle context */ typedef struct { ecs_table_range_t range; int32_t cur; int32_t block_index; ecs_flags64_t block; ecs_termset_t prev_set_fields; bool optional_not; bool has_bitset; } ecs_query_toggle_ctx_t; typedef struct ecs_query_op_ctx_t { union { ecs_query_all_ctx_t all; ecs_query_and_ctx_t and; ecs_query_xfrom_ctx_t xfrom; ecs_query_up_ctx_t up; ecs_query_trav_ctx_t trav; ecs_query_ids_ctx_t ids; ecs_query_eq_ctx_t eq; ecs_query_each_ctx_t each; ecs_query_setthis_ctx_t setthis; ecs_query_ctrl_ctx_t ctrl; ecs_query_trivial_ctx_t trivial; ecs_query_membereq_ctx_t membereq; ecs_query_toggle_ctx_t toggle; ecs_query_sparse_ctx_t sparse; } is; } ecs_query_op_ctx_t; typedef struct { /* Labels used for control flow */ ecs_query_lbl_t lbl_query; /* Used to find the op that does the actual searching */ ecs_query_lbl_t lbl_begin; ecs_query_lbl_t lbl_cond_eval; ecs_write_flags_t written_or; /* Cond written flags at start of or chain */ ecs_write_flags_t cond_written_or; /* Cond written flags at start of or chain */ ecs_query_ref_t src_or; /* Source for terms in current or chain */ bool src_written_or; /* Was src populated before OR chain */ bool in_or; /* Whether we're in an or chain */ } ecs_query_compile_ctrlflow_t; /* Query compiler state */ typedef struct { ecs_vec_t *ops; ecs_write_flags_t written; /* Bitmask to check which variables have been written */ ecs_write_flags_t cond_written; /* Track conditional writes (optional operators) */ /* Maintain control flow per scope */ ecs_query_compile_ctrlflow_t ctrlflow[FLECS_QUERY_SCOPE_NESTING_MAX]; ecs_query_compile_ctrlflow_t *cur; /* Current scope */ int32_t scope; /* Nesting level of query scopes */ ecs_flags32_t scope_is_not; /* Whether scope is prefixed with not */ ecs_oper_kind_t oper; /* Temp storage to track current operator for term */ int32_t skipped; /* Term skipped during compilation */ } ecs_query_compile_ctx_t; /* Query run state */ typedef struct { uint64_t *written; /* Bitset to check which variables have been written */ ecs_query_lbl_t op_index; /* Currently evaluated operation */ ecs_var_t *vars; /* Variable storage */ ecs_iter_t *it; /* Iterator */ ecs_query_op_ctx_t *op_ctx; /* Operation context (stack) */ ecs_world_t *world; /* Reference to world */ const ecs_query_impl_t *query; /* Reference to query */ const ecs_query_var_t *query_vars; /* Reference to query variable array */ ecs_query_iter_t *qit; } ecs_query_run_ctx_t; struct ecs_query_impl_t { ecs_query_t pub; /* Public query data */ ecs_stage_t *stage; /* Stage used for allocations */ /* Variables */ ecs_query_var_t *vars; /* Variables */ int32_t var_count; /* Number of variables */ int32_t var_size; /* Size of variable array */ ecs_hashmap_t tvar_index; /* Name index for table variables */ ecs_hashmap_t evar_index; /* Name index for entity variables */ ecs_var_id_t *src_vars; /* Array with ids to source variables for fields */ /* Query plan */ ecs_query_op_t *ops; /* Operations */ int32_t op_count; /* Number of operations */ /* Misc */ int16_t tokens_len; /* Length of tokens buffer */ char *tokens; /* Buffer with string tokens used by terms */ int32_t *monitor; /* Change monitor for fields with fixed src */ #ifdef FLECS_DEBUG ecs_termset_t final_terms; /* Terms that don't use component inheritance */ #endif /* Query cache */ struct ecs_query_cache_t *cache; /* Cache, if query contains cached terms */ /* User context */ ecs_ctx_free_t ctx_free; /* Callback to free ctx */ ecs_ctx_free_t binding_ctx_free; /* Callback to free binding_ctx */ /* Mixins */ flecs_poly_dtor_t dtor; }; #endif