From 05c749e538ebc3a4f6735f62d022655cf92fc17e Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Thu, 14 Apr 2011 02:45:24 -0400 Subject: [PATCH] Definition scope lookup (for variant/enum) Signed-off-by: Mathieu Desnoyers --- include/babeltrace/types.h | 18 ++++- types/array.c | 13 +++- types/enum.c | 9 ++- types/float.c | 11 ++- types/integer.c | 7 +- types/sequence.c | 15 ++-- types/string.c | 7 +- types/struct.c | 12 ++- types/types.c | 155 +++++++++++++++++++++++++++++++++++-- types/variant.c | 16 +++- 10 files changed, 223 insertions(+), 40 deletions(-) diff --git a/include/babeltrace/types.h b/include/babeltrace/types.h index ed2aae87..885a6a1b 100644 --- a/include/babeltrace/types.h +++ b/include/babeltrace/types.h @@ -105,6 +105,12 @@ struct definition_scope { /* Hash table mapping field name GQuark to "struct definition" */ GHashTable *definitions; struct definition_scope *parent_scope; + /* + * Complete "path" leading to this definition scope. + * Includes trace/stream/event '.' field name '.' field name '.' .... + * Array of GQuark elements (which are each separated by dots). + */ + GArray *scope_path; /* array of GQuark */ }; enum ctf_type_id { @@ -131,7 +137,8 @@ struct declaration { void (*declaration_free)(struct declaration *declaration); struct definition * (*definition_new)(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); /* * definition_free called with definition ref is decremented to 0. */ @@ -147,6 +154,7 @@ struct declaration { struct definition { struct declaration *declaration; + int index; /* Position of the definition in its container */ int ref; /* number of references to the definition */ }; @@ -360,13 +368,15 @@ void free_declaration_scope(struct declaration_scope *scope); * definition scopes. */ struct definition * - lookup_field_definition(GQuark field_name, - struct definition_scope *scope); + lookup_definition(GArray *cur_path, /* array of GQuark */ + GArray *lookup_path, /* array of GQuark */ + struct definition_scope *scope); int register_field_definition(GQuark field_name, struct definition *definition, struct definition_scope *scope); struct definition_scope * - new_definition_scope(struct definition_scope *parent_scope); + new_definition_scope(struct definition_scope *parent_scope, + GQuark field_name); void free_definition_scope(struct definition_scope *scope); void declaration_ref(struct declaration *declaration); diff --git a/types/array.c b/types/array.c index 7b1d92a5..3e1f2181 100644 --- a/types/array.c +++ b/types/array.c @@ -21,7 +21,8 @@ static struct definition *_array_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); static void _array_definition_free(struct definition *definition); @@ -85,7 +86,8 @@ struct declaration_array * static struct definition * _array_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope) + struct definition_scope *parent_scope, + GQuark field_name, int index) { struct declaration_array *array_declaration = container_of(declaration, struct declaration_array, p); @@ -96,10 +98,13 @@ struct definition * array->p.declaration = declaration; array->declaration = array_declaration; array->p.ref = 1; - array->scope = new_definition_scope(parent_scope); + array->p.index = index; + array->scope = new_definition_scope(parent_scope, field_name); array->current_element.definition = array_declaration->elem->definition_new(array_declaration->elem, - parent_scope); + parent_scope, + g_quark_from_static_string("[]"), + 0); return &array->p; } diff --git a/types/enum.c b/types/enum.c index 67c23f09..36e310b0 100644 --- a/types/enum.c +++ b/types/enum.c @@ -23,7 +23,8 @@ static struct definition *_enum_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); static void _enum_definition_free(struct definition *definition); @@ -421,7 +422,8 @@ struct declaration_enum * static struct definition * _enum_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope) + struct definition_scope *parent_scope, + GQuark field_name, int index) { struct declaration_enum *enum_declaration = container_of(declaration, struct declaration_enum, p); @@ -433,10 +435,11 @@ struct definition * _enum->p.declaration = declaration; _enum->declaration = enum_declaration; _enum->p.ref = 1; + _enum->p.index = index; _enum->value = NULL; definition_integer_parent = enum_declaration->integer_declaration->p.definition_new(&enum_declaration->integer_declaration->p, - parent_scope); + parent_scope, field_name, 0); _enum->integer = container_of(definition_integer_parent, struct definition_integer, p); return &_enum->p; diff --git a/types/float.c b/types/float.c index b12cf6be..eef123c8 100644 --- a/types/float.c +++ b/types/float.c @@ -21,7 +21,8 @@ static struct definition *_float_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); static void _float_definition_free(struct definition *definition); @@ -88,7 +89,8 @@ struct declaration_float * static struct definition * _float_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope) + struct definition_scope *parent_scope, + GQuark field_name, int index) { struct declaration_float *float_declaration = container_of(declaration, struct declaration_float, p); @@ -96,9 +98,10 @@ struct definition * _float = g_new(struct definition_float, 1); declaration_ref(&float_declaration->p); - _float->p.declaration= declaration; - _float->declaration= float_declaration; + _float->p.declaration = declaration; + _float->declaration = float_declaration; _float->p.ref = 1; + _float->p.index = index; _float->value = 0.0; return &_float->p; } diff --git a/types/integer.c b/types/integer.c index c207079d..928e4960 100644 --- a/types/integer.c +++ b/types/integer.c @@ -23,7 +23,8 @@ static struct definition *_integer_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); static void _integer_definition_free(struct definition *definition); @@ -80,7 +81,8 @@ struct declaration_integer * static struct definition * _integer_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope) + struct definition_scope *parent_scope, + GQuark field_name, int index) { struct declaration_integer *integer_declaration = container_of(declaration, struct declaration_integer, p); @@ -91,6 +93,7 @@ struct definition * integer->p.declaration = declaration; integer->declaration = integer_declaration; integer->p.ref = 1; + integer->p.index = index; integer->value._unsigned = 0; return &integer->p; } diff --git a/types/sequence.c b/types/sequence.c index 8db1ee04..2f6a7f18 100644 --- a/types/sequence.c +++ b/types/sequence.c @@ -25,7 +25,8 @@ static struct definition *_sequence_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); static void _sequence_definition_free(struct definition *definition); @@ -94,7 +95,8 @@ struct declaration_sequence * static struct definition *_sequence_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope) + struct definition_scope *parent_scope, + GQuark field_name, int index) { struct declaration_sequence *sequence_declaration = container_of(declaration, struct declaration_sequence, p); @@ -106,14 +108,17 @@ struct definition *_sequence_definition_new(struct declaration *declaration, sequence->p.declaration = declaration; sequence->declaration = sequence_declaration; sequence->p.ref = 1; - sequence->scope = new_definition_scope(parent_scope); + sequence->p.index = index; + sequence->scope = new_definition_scope(parent_scope, field_name); len_parent = sequence_declaration->len_declaration->p.definition_new(&sequence_declaration->len_declaration->p, - parent_scope); + parent_scope, + g_quark_from_static_string("length"), 0); sequence->len = container_of(len_parent, struct definition_integer, p); sequence->current_element.definition = sequence_declaration->elem->definition_new(sequence_declaration->elem, - parent_scope); + parent_scope, + g_quark_from_static_string("[]"), 1); return &sequence->p; } diff --git a/types/string.c b/types/string.c index 5796bf44..41ac7576 100644 --- a/types/string.c +++ b/types/string.c @@ -22,7 +22,8 @@ static struct definition *_string_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); static void _string_definition_free(struct definition *definition); @@ -72,7 +73,8 @@ struct declaration_string *string_declaration_new(const char *name) static struct definition * _string_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope) + struct definition_scope *parent_scope, + GQuark field_name, int index) { struct declaration_string *string_declaration = container_of(declaration, struct declaration_string, p); @@ -83,6 +85,7 @@ struct definition * string->p.declaration = declaration; string->declaration = string_declaration; string->p.ref = 1; + string->p.index = index; string->value = NULL; return &string->p; } diff --git a/types/struct.c b/types/struct.c index 03c92ea4..21465c73 100644 --- a/types/struct.c +++ b/types/struct.c @@ -25,7 +25,8 @@ static struct definition *_struct_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); static void _struct_definition_free(struct definition *definition); @@ -101,7 +102,8 @@ struct declaration_struct *struct_declaration_new(const char *name, static struct definition * _struct_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope) + struct definition_scope *parent_scope, + GQuark field_name, int index) { struct declaration_struct *struct_declaration = container_of(declaration, struct declaration_struct, p); @@ -114,7 +116,8 @@ struct definition * _struct->p.declaration = declaration; _struct->declaration = struct_declaration; _struct->p.ref = 1; - _struct->scope = new_definition_scope(parent_scope); + _struct->p.index = index; + _struct->scope = new_definition_scope(parent_scope, field_name); _struct->fields = g_array_sized_new(FALSE, TRUE, sizeof(struct field), DEFAULT_NR_STRUCT_FIELDS); @@ -129,7 +132,8 @@ struct definition * field->name = declaration_field->name; field->definition = declaration_field->declaration->definition_new(declaration_field->declaration, - _struct->scope); + _struct->scope, + field->name, i); ret = register_field_definition(field->name, field->definition, _struct->scope); diff --git a/types/types.c b/types/types.c index 90720e2b..208b303f 100644 --- a/types/types.c +++ b/types/types.c @@ -72,17 +72,143 @@ struct definition * (gconstpointer) (unsigned long) field_name); } +/* + * Returns the index at which the paths differ. + * If the value returned equals len, it means the paths are identical + * from index 0 to len-1. + */ +static int compare_paths(GArray *a, GArray *b, int len) +{ + int i; + + assert(len <= a->len); + assert(len <= b->len); + + for (i = 0; i < len; i++) { + GQuark qa, qb; + + qa = g_array_index(a, GQuark, i); + qb = g_array_index(b, GQuark, i); + if (qa != qb) + return i; + } + return i; +} + +static int is_path_child_of(GArray *path, GArray *maybe_parent) +{ + if (path->len <= maybe_parent->len) + return 0; + if (compare_paths(path, maybe_parent, maybe_parent->len) + == maybe_parent->len) + return 1; + else + return 0; +} + +static struct definition_scope * + get_definition_scope(struct definition *definition) +{ + switch (definition->declaration->id) { + case CTF_TYPE_STRUCT: + { + struct definition_struct *def = + container_of(definition, struct definition_struct, p); + return def->scope; + } + case CTF_TYPE_VARIANT: + { + struct definition_variant *def = + container_of(definition, struct definition_variant, p); + return def->scope; + } + case CTF_TYPE_ARRAY: + { + struct definition_array *def = + container_of(definition, struct definition_array, p); + return def->scope; + } + case CTF_TYPE_SEQUENCE: + { + struct definition_sequence *def = + container_of(definition, struct definition_sequence, p); + return def->scope; + } + + case CTF_TYPE_INTEGER: + case CTF_TYPE_FLOAT: + case CTF_TYPE_ENUM: + case CTF_TYPE_STRING: + case CTF_TYPE_UNKNOWN: + default: + return NULL; + } +} + +/* + * OK, here is the fun. We want to lookup a field that is: + * - either in the current scope, but prior to the current field. + * - or in a parent scope (or parent of parent ...) still in a field + * prior to the current field position within the parents. + * A reaching through a dynamic scoping (e.g. from payload structure to + * event header structure), the parent fields are always entirely prior + * to the child. + * If we cannot find such a field that is prior to our current path, we + * return NULL. + * + * cur_path: the path leading to the variant definition. + * lookup_path: the path leading to the enum we want to look for. + * scope: the definition scope containing the variant definition. + */ struct definition * - lookup_field_definition(GQuark field_name, - struct definition_scope *scope) + lookup_definition(GArray *cur_path, + GArray *lookup_path, + struct definition_scope *scope) { - struct definition *definition; + struct definition *definition, *lookup_definition; + GQuark last; + int index; while (scope) { - definition = lookup_field_definition_scope(field_name, scope); - if (definition) - return definition; - scope = scope->parent_scope; + /* going up in the hierarchy. Check where we come from. */ + assert(is_path_child_of(cur_path, scope->scope_path)); + assert(cur_path->len - scope->scope_path->len == 1); + last = g_array_index(cur_path, GQuark, cur_path->len - 1); + definition = lookup_field_definition_scope(last, scope); + assert(definition); + index = definition->index; +lookup: + if (is_path_child_of(lookup_path, scope->scope_path)) { + /* Means we can lookup the field in this scope */ + last = g_array_index(lookup_path, GQuark, + scope->scope_path->len); + lookup_definition = lookup_field_definition_scope(last, scope); + if (!lookup_definition || ((index != -1) && lookup_definition->index >= index)) + return NULL; + /* Found it! And it is prior to the current field. */ + if (lookup_path->len - scope->scope_path->len == 1) { + /* Direct child */ + return lookup_definition; + } else { + scope = get_definition_scope(lookup_definition); + /* Check if the definition has a sub-scope */ + if (!scope) + return NULL; + /* + * Don't compare index anymore, because we are + * going within a scope that has been validated + * to be entirely prior to the current scope. + */ + cur_path = NULL; + index = -1; + goto lookup; + } + } else { + assert(index != -1); + /* lookup_path is within an upper scope */ + cur_path = scope->scope_path; + scope = scope->parent_scope; + } } return NULL; } @@ -281,19 +407,32 @@ int register_enum_declaration(GQuark enum_name, } struct definition_scope * - new_definition_scope(struct definition_scope *parent_scope) + new_definition_scope(struct definition_scope *parent_scope, + GQuark field_name) { struct definition_scope *scope = g_new(struct definition_scope, 1); + int scope_path_len = 1; scope->definitions = g_hash_table_new_full(g_direct_hash, g_direct_equal, NULL, (GDestroyNotify) definition_unref); scope->parent_scope = parent_scope; + if (scope->parent_scope) + scope_path_len += scope->parent_scope->scope_path->len; + scope->scope_path = g_array_sized_new(FALSE, TRUE, sizeof(GQuark), + scope_path_len); + g_array_set_size(scope->scope_path, scope_path_len); + if (scope->parent_scope) + memcpy(scope->scope_path, scope->parent_scope->scope_path, + sizeof(GQuark) * (scope_path_len - 1)); + g_array_index(scope->scope_path, GQuark, scope_path_len - 1) = + field_name; return scope; } void free_definition_scope(struct definition_scope *scope) { + g_array_free(scope->scope_path, TRUE); g_hash_table_destroy(scope->definitions); g_free(scope); } diff --git a/types/variant.c b/types/variant.c index e522621b..4a8abcb1 100644 --- a/types/variant.c +++ b/types/variant.c @@ -22,7 +22,8 @@ static struct definition *_variant_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope); + struct definition_scope *parent_scope, + GQuark field_name, int index); static void _variant_definition_free(struct definition *definition); @@ -95,7 +96,8 @@ struct declaration_variant *variant_declaration_new(const char *name, static struct definition * _variant_definition_new(struct declaration *declaration, - struct definition_scope *parent_scope) + struct definition_scope *parent_scope, + GQuark field_name, int index) { struct declaration_variant *variant_declaration = container_of(declaration, struct declaration_variant, p); @@ -107,7 +109,8 @@ struct definition * variant->p.declaration = declaration; variant->declaration = variant_declaration; variant->p.ref = 1; - variant->scope = new_definition_scope(parent_scope); + variant->p.index = index; + variant->scope = new_definition_scope(parent_scope, field_name); variant->fields = g_array_sized_new(FALSE, TRUE, sizeof(struct field), DEFAULT_NR_STRUCT_FIELDS); @@ -120,9 +123,14 @@ struct definition * struct field, i); field->name = declaration_field->name; + /* + * All child definition are at index 0, because they are + * various choices of the same field. + */ field->definition = declaration_field->declaration->definition_new(declaration_field->declaration, - variant->scope); + variant->scope, + field->name, 0); } variant->current_field = NULL; return &variant->p; -- 2.34.1