From 02b234c461611f6f479c2dc3697a1b42b03cf050 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 16 Feb 2011 10:43:02 -0500 Subject: [PATCH] AST: basic node structure + reparent operation Signed-off-by: Mathieu Desnoyers --- formats/ctf/metadata/ctf-ast.h | 46 ++- formats/ctf/metadata/ctf-parser.y | 533 ++++++++++++++++++++++++++++++ 2 files changed, 567 insertions(+), 12 deletions(-) diff --git a/formats/ctf/metadata/ctf-ast.h b/formats/ctf/metadata/ctf-ast.h index db297afd..74e1ecb4 100644 --- a/formats/ctf/metadata/ctf-ast.h +++ b/formats/ctf/metadata/ctf-ast.h @@ -17,7 +17,7 @@ struct ctf_node; struct ctf_parser; enum node_type { - NODE_UNKNOWN, + NODE_UNKNOWN = 0, NODE_ROOT, NODE_EVENT, @@ -27,6 +27,8 @@ enum node_type { NODE_CTF_EXPRESSION, NODE_TYPEDEF, + NODE_TYPEALIAS_TARGET, + NODE_TYPEALIAS_ALIAS, NODE_TYPEALIAS, NODE_TYPE_SPECIFIER, @@ -56,6 +58,12 @@ struct ctf_node { struct { } unknown; struct { + struct cds_list_head _typedef; + struct cds_list_head typealias; + struct cds_list_head declaration_specifier; + struct cds_list_head trace; + struct cds_list_head stream; + struct cds_list_head event; } root; struct { /* @@ -65,6 +73,7 @@ struct ctf_node { struct cds_list_head _typedef; struct cds_list_head typealias; struct cds_list_head ctf_expression; + struct cds_list_head declaration_specifier; } event; struct { /* @@ -74,6 +83,7 @@ struct ctf_node { struct cds_list_head _typedef; struct cds_list_head typealias; struct cds_list_head ctf_expression; + struct cds_list_head declaration_specifier; } stream; struct { /* @@ -83,10 +93,12 @@ struct ctf_node { struct cds_list_head _typedef; struct cds_list_head typealias; struct cds_list_head ctf_expression; + struct cds_list_head declaration_specifier; } trace; struct { char *left_id; enum { + EXP_UNKNOWN = 0, EXP_ID, EXP_TYPE, } type; @@ -97,17 +109,24 @@ struct ctf_node { } ctf_expression; struct { struct ctf_node *declaration_specifier; - struct cds_list_head type_declarator; + struct cds_list_head type_declarators; } _typedef; + /* new type is "alias", existing type "target" */ + struct { + struct ctf_node *declaration_specifier; + struct cds_list_head type_declarators; + } typealias_target; + struct { + struct ctf_node *declaration_specifier; + struct cds_list_head type_declarators; + } typealias_alias; struct { - /* new type is "alias", existing type "target" */ - struct ctf_node *target_declaration_specifier; - struct cds_list_head target_type_declarator; - struct ctf_node *alias_declaration_specifier; - struct cds_list_head alias_type_declarator; + struct ctf_node *target; + struct ctf_node *alias; } typealias; struct { enum { + TYPESPEC_UNKNOWN = 0, TYPESPEC_VOID, TYPESPEC_CHAR, TYPESPEC_SHORT, @@ -147,18 +166,18 @@ struct ctf_node { struct { struct cds_list_head pointers; enum { + TYPEDEC_UNKNOWN = 0, TYPEDEC_ID, /* identifier */ - TYPEDEC_TYPEDEC,/* nested with () */ - TYPEDEC_DIRECT, /* array or sequence */ + TYPEDEC_NESTED, /* (), array or sequence */ } type; union { char *id; - struct ctf_node *typedec; struct { /* typedec has no pointer list */ - struct ctf_node *typedec; + struct ctf_node *type_declarator; struct { enum { + TYPEDEC_TYPE_UNKNOWN = 0, TYPEDEC_TYPE_VALUE, /* must be > 0 */ TYPEDEC_TYPE_TYPE, } type; @@ -167,7 +186,7 @@ struct ctf_node { struct ctf_node *declaration_specifier; } u; } length; - } direct; + } nested; } u; } type_declarator; struct { @@ -197,6 +216,7 @@ struct ctf_node { char *enum_id; struct { enum { + ENUM_TYPE_UNKNOWN = 0, ENUM_TYPE_VALUE, /* must be > 0 */ ENUM_TYPE_TYPE, } type; @@ -209,6 +229,7 @@ struct ctf_node { } _enum; struct { struct ctf_node *declaration_specifier; + struct cds_list_head type_declarators; } struct_or_variant_declaration; struct { struct cds_list_head _typedef; @@ -225,6 +246,7 @@ struct ctf_node { struct ctf_ast { struct ctf_node root; + struct cds_list_head allocated_nodes; }; #endif /* _CTF_PARSER_H */ diff --git a/formats/ctf/metadata/ctf-parser.y b/formats/ctf/metadata/ctf-parser.y index 7847a85d..4ae9b4ee 100644 --- a/formats/ctf/metadata/ctf-parser.y +++ b/formats/ctf/metadata/ctf-parser.y @@ -24,6 +24,7 @@ #include #include #include +#include #include "ctf-scanner.h" #include "ctf-parser.h" #include "ctf-ast.h" @@ -138,6 +139,512 @@ static void add_type(struct ctf_scanner *scanner, const char *id) g_hash_table_insert(scanner->cs->types, type_id, type_id); } +static struct ctf_node *make_node(struct ctf_scanner *scanner, + enum node_type type) +{ + struct ctf_ast *ast = ctf_scanner_get_ast(scanner); + struct ctf_node *node; + + node = malloc(sizeof(*node)); + if (!node) + return NULL; + memset(node, 0, sizeof(*node)); + node->type = type; + CDS_INIT_LIST_HEAD(&node->siblings); + cds_list_add(&node->gc, &ast->allocated_nodes); + + switch (type) { + case NODE_ROOT: + fprintf(stderr, "[error] %s: trying to create root node\n", __func__); + break; + + case NODE_EVENT: + CDS_INIT_LIST_HEAD(&node->u.event._typedef); + CDS_INIT_LIST_HEAD(&node->u.event.typealias); + CDS_INIT_LIST_HEAD(&node->u.event.ctf_expression); + CDS_INIT_LIST_HEAD(&node->u.event.declaration_specifier); + break; + case NODE_STREAM: + CDS_INIT_LIST_HEAD(&node->u.stream._typedef); + CDS_INIT_LIST_HEAD(&node->u.stream.typealias); + CDS_INIT_LIST_HEAD(&node->u.stream.ctf_expression); + CDS_INIT_LIST_HEAD(&node->u.stream.declaration_specifier); + break; + case NODE_TRACE: + CDS_INIT_LIST_HEAD(&node->u.trace._typedef); + CDS_INIT_LIST_HEAD(&node->u.trace.typealias); + CDS_INIT_LIST_HEAD(&node->u.trace.ctf_expression); + CDS_INIT_LIST_HEAD(&node->u.trace.declaration_specifier); + break; + + case NODE_CTF_EXPRESSION: + break; + + case NODE_TYPEDEF: + CDS_INIT_LIST_HEAD(&node->u._typedef.type_declarators); + break; + case NODE_TYPEALIAS_TARGET: + CDS_INIT_LIST_HEAD(&node->u.typealias_target.type_declarators); + break; + case NODE_TYPEALIAS_ALIAS: + CDS_INIT_LIST_HEAD(&node->u.typealias_alias.type_declarators); + break; + case NODE_TYPEALIAS: + break; + + case NODE_TYPE_SPECIFIER: + break; + case NODE_DECLARATION_SPECIFIER: + CDS_INIT_LIST_HEAD(&node->u.declaration_specifier.type_specifiers); + break; + case NODE_POINTER: + break; + case NODE_TYPE_DECLARATOR: + CDS_INIT_LIST_HEAD(&node->u.type_declarator.pointers); + break; + + case NODE_FLOATING_POINT: + CDS_INIT_LIST_HEAD(&node->u.floating_point.expressions); + break; + case NODE_INTEGER: + CDS_INIT_LIST_HEAD(&node->u.integer.expressions); + break; + case NODE_STRING: + CDS_INIT_LIST_HEAD(&node->u.string.expressions); + break; + case NODE_ENUMERATOR: + break; + case NODE_ENUM: + CDS_INIT_LIST_HEAD(&node->u._enum.enumerator_list); + break; + case NODE_STRUCT_OR_VARIANT_DECLARATION: + CDS_INIT_LIST_HEAD(&node->u.struct_or_variant_declaration.type_declarators); + break; + case NODE_VARIANT: + CDS_INIT_LIST_HEAD(&node->u.variant._typedef); + CDS_INIT_LIST_HEAD(&node->u.variant.typealias); + CDS_INIT_LIST_HEAD(&node->u.variant.declaration_list); + break; + case NODE_STRUCT: + CDS_INIT_LIST_HEAD(&node->u._struct._typedef); + CDS_INIT_LIST_HEAD(&node->u._struct.typealias); + CDS_INIT_LIST_HEAD(&node->u._struct.declaration_list); + break; + + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type %d\n", __func__, + (int) type); + break; + } + + return node; +} + +static int reparent_ctf_expression(struct ctf_node *node, + struct ctf_node *parent) +{ + switch (parent->type) { + case NODE_EVENT: + cds_list_add(&node->siblings, &parent->u.event.ctf_expression); + break; + case NODE_STREAM: + cds_list_add(&node->siblings, &parent->u.stream.ctf_expression); + break; + case NODE_TRACE: + cds_list_add(&node->siblings, &parent->u.trace.ctf_expression); + break; + case NODE_FLOATING_POINT: + cds_list_add(&node->siblings, &parent->u.floating_point.expressions); + break; + case NODE_INTEGER: + cds_list_add(&node->siblings, &parent->u.integer.expressions); + break; + case NODE_STRING: + cds_list_add(&node->siblings, &parent->u.string.expressions); + break; + + case NODE_ROOT: + case NODE_CTF_EXPRESSION: + case NODE_TYPEDEF: + case NODE_TYPEALIAS_TARGET: + case NODE_TYPEALIAS_ALIAS: + case NODE_TYPEALIAS: + case NODE_TYPE_SPECIFIER: + case NODE_DECLARATION_SPECIFIER: + case NODE_POINTER: + case NODE_TYPE_DECLARATOR: + case NODE_ENUMERATOR: + case NODE_ENUM: + case NODE_STRUCT_OR_VARIANT_DECLARATION: + case NODE_VARIANT: + case NODE_STRUCT: + return -EPERM; + + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type %d\n", __func__, + (int) parent->type); + return -EINVAL; + } + return 0; +} + +static int reparent_typedef(struct ctf_node *node, struct ctf_node *parent) +{ + switch (parent->type) { + case NODE_ROOT: + cds_list_add(&node->siblings, &parent->u.root._typedef); + break; + case NODE_EVENT: + cds_list_add(&node->siblings, &parent->u.event._typedef); + break; + case NODE_STREAM: + cds_list_add(&node->siblings, &parent->u.stream._typedef); + break; + case NODE_TRACE: + cds_list_add(&node->siblings, &parent->u.trace._typedef); + break; + case NODE_VARIANT: + cds_list_add(&node->siblings, &parent->u.variant._typedef); + break; + case NODE_STRUCT: + cds_list_add(&node->siblings, &parent->u._struct._typedef); + break; + + case NODE_FLOATING_POINT: + case NODE_INTEGER: + case NODE_STRING: + case NODE_CTF_EXPRESSION: + case NODE_TYPEDEF: + case NODE_TYPEALIAS_TARGET: + case NODE_TYPEALIAS_ALIAS: + case NODE_TYPEALIAS: + case NODE_TYPE_SPECIFIER: + case NODE_DECLARATION_SPECIFIER: + case NODE_POINTER: + case NODE_TYPE_DECLARATOR: + case NODE_ENUMERATOR: + case NODE_ENUM: + case NODE_STRUCT_OR_VARIANT_DECLARATION: + return -EPERM; + + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type %d\n", __func__, + (int) parent->type); + return -EINVAL; + } + return 0; +} + +static int reparent_typealias(struct ctf_node *node, struct ctf_node *parent) +{ + switch (parent->type) { + case NODE_ROOT: + cds_list_add(&node->siblings, &parent->u.root.typealias); + break; + case NODE_EVENT: + cds_list_add(&node->siblings, &parent->u.event.typealias); + break; + case NODE_STREAM: + cds_list_add(&node->siblings, &parent->u.stream.typealias); + break; + case NODE_TRACE: + cds_list_add(&node->siblings, &parent->u.trace.typealias); + break; + case NODE_VARIANT: + cds_list_add(&node->siblings, &parent->u.variant.typealias); + break; + case NODE_STRUCT: + cds_list_add(&node->siblings, &parent->u._struct.typealias); + break; + + case NODE_FLOATING_POINT: + case NODE_INTEGER: + case NODE_STRING: + case NODE_CTF_EXPRESSION: + case NODE_TYPEDEF: + case NODE_TYPEALIAS_TARGET: + case NODE_TYPEALIAS_ALIAS: + case NODE_TYPEALIAS: + case NODE_TYPE_SPECIFIER: + case NODE_DECLARATION_SPECIFIER: + case NODE_POINTER: + case NODE_TYPE_DECLARATOR: + case NODE_ENUMERATOR: + case NODE_ENUM: + case NODE_STRUCT_OR_VARIANT_DECLARATION: + return -EPERM; + + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type %d\n", __func__, + (int) parent->type); + return -EINVAL; + } + return 0; +} + +static int reparent_declaration_specifier(struct ctf_node *node, + struct ctf_node *parent) +{ + switch (parent->type) { + case NODE_ROOT: + cds_list_add(&node->siblings, &parent->u.root.declaration_specifier); + break; + case NODE_EVENT: + cds_list_add(&node->siblings, &parent->u.event.declaration_specifier); + break; + case NODE_STREAM: + cds_list_add(&node->siblings, &parent->u.stream.declaration_specifier); + break; + case NODE_TRACE: + cds_list_add(&node->siblings, &parent->u.trace.declaration_specifier); + break; + case NODE_VARIANT: + cds_list_add(&node->siblings, &parent->u.variant.declaration_list); + break; + case NODE_STRUCT: + cds_list_add(&node->siblings, &parent->u._struct.declaration_list); + break; + case NODE_TYPEDEF: + parent->u._typedef.declaration_specifier = node; + break; + case NODE_TYPEALIAS_TARGET: + parent->u.typealias_target.declaration_specifier = node; + break; + case NODE_TYPEALIAS_ALIAS: + parent->u.typealias_alias.declaration_specifier = node; + break; + case NODE_TYPE_DECLARATOR: + parent->u.type_declarator.type = TYPEDEC_NESTED; + parent->u.type_declarator.u.nested.length.type = TYPEDEC_TYPE_TYPE; + parent->u.type_declarator.u.nested.length.u.declaration_specifier = node; + break; + case NODE_ENUM: + parent->u._enum.container_type.type = ENUM_TYPE_TYPE; + parent->u._enum.container_type.u.declaration_specifier = node; + break; + case NODE_STRUCT_OR_VARIANT_DECLARATION: + parent->u.struct_or_variant_declaration.declaration_specifier = node; + break; + case NODE_TYPEALIAS: + case NODE_FLOATING_POINT: + case NODE_INTEGER: + case NODE_STRING: + case NODE_CTF_EXPRESSION: + case NODE_TYPE_SPECIFIER: + case NODE_DECLARATION_SPECIFIER: + case NODE_POINTER: + case NODE_ENUMERATOR: + return -EPERM; + + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type %d\n", __func__, + (int) parent->type); + return -EINVAL; + } + return 0; +} + +static int reparent_type_declarator(struct ctf_node *node, + struct ctf_node *parent) +{ + switch (parent->type) { + case NODE_TYPE_DECLARATOR: + parent->u.type_declarator.type = TYPEDEC_NESTED; + parent->u.type_declarator.u.nested.type_declarator = node; + break; + case NODE_STRUCT_OR_VARIANT_DECLARATION: + cds_list_add(&node->siblings, &parent->u.struct_or_variant_declaration.type_declarators); + break; + case NODE_TYPEDEF: + cds_list_add(&node->siblings, &parent->u._typedef.type_declarators); + break; + case NODE_TYPEALIAS_TARGET: + cds_list_add(&node->siblings, &parent->u.typealias_target.type_declarators); + break; + case NODE_TYPEALIAS_ALIAS: + cds_list_add(&node->siblings, &parent->u.typealias_alias.type_declarators); + break; + + case NODE_ROOT: + case NODE_EVENT: + case NODE_STREAM: + case NODE_TRACE: + case NODE_VARIANT: + case NODE_STRUCT: + case NODE_TYPEALIAS: + case NODE_ENUM: + case NODE_FLOATING_POINT: + case NODE_INTEGER: + case NODE_STRING: + case NODE_CTF_EXPRESSION: + case NODE_TYPE_SPECIFIER: + case NODE_DECLARATION_SPECIFIER: + case NODE_POINTER: + case NODE_ENUMERATOR: + return -EPERM; + + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type %d\n", __func__, + (int) parent->type); + return -EINVAL; + } + return 0; +} + +/* + * reparent node + * + * Relink node to new parent. Returns 0 on success, -EPERM if it is not + * permitted to create the link declared by the input, -ENOENT if node or parent + * is NULL, -EINVAL if there is an internal structure problem. + */ +static int reparent_node(struct ctf_node *node, + struct ctf_node *parent) +{ + if (!node || !parent) + return -ENOENT; + + /* Unlink from old parent */ + cds_list_del(&node->siblings); + + /* Link to new parent */ + node->parent = parent; + + switch (node->type) { + case NODE_ROOT: + fprintf(stderr, "[error] %s: trying to reparent root node\n", __func__); + return -EINVAL; + + case NODE_EVENT: + if (parent->type == NODE_ROOT) + cds_list_add(&node->siblings, &parent->u.root.event); + else + return -EPERM; + break; + case NODE_STREAM: + if (parent->type == NODE_ROOT) + cds_list_add(&node->siblings, &parent->u.root.stream); + else + return -EPERM; + break; + case NODE_TRACE: + if (parent->type == NODE_ROOT) + cds_list_add(&node->siblings, &parent->u.root.trace); + else + return -EPERM; + break; + + case NODE_CTF_EXPRESSION: + return reparent_ctf_expression(node, parent); + + case NODE_TYPEDEF: + return reparent_typedef(node, parent); + case NODE_TYPEALIAS_TARGET: + if (parent->type == NODE_TYPEALIAS) + parent->u.typealias.target = node; + else + return -EINVAL; + case NODE_TYPEALIAS_ALIAS: + if (parent->type == NODE_TYPEALIAS) + parent->u.typealias.alias = node; + else + return -EINVAL; + case NODE_TYPEALIAS: + return reparent_typealias(node, parent); + + case NODE_TYPE_SPECIFIER: + if (parent->type == NODE_DECLARATION_SPECIFIER) + cds_list_add(&node->siblings, &parent->u.declaration_specifier.type_specifiers); + else + return -EPERM; + break; + case NODE_DECLARATION_SPECIFIER: + return reparent_declaration_specifier(node, parent); + case NODE_POINTER: + if (parent->type == NODE_TYPE_DECLARATOR) + cds_list_add(&node->siblings, &parent->u.type_declarator.pointers); + else + return -EPERM; + break; + case NODE_TYPE_DECLARATOR: + return reparent_type_declarator(node, parent); + + case NODE_FLOATING_POINT: + if (parent->type == NODE_TYPE_SPECIFIER) { + parent->u.type_specifier.type = TYPESPEC_FLOATING_POINT; + parent->u.type_specifier.u.floating_point = node; + } else + return -EPERM; + break; + case NODE_INTEGER: + if (parent->type == NODE_TYPE_SPECIFIER) { + parent->u.type_specifier.type = TYPESPEC_INTEGER; + parent->u.type_specifier.u.integer = node; + } else + return -EPERM; + break; + case NODE_STRING: + if (parent->type == NODE_TYPE_SPECIFIER) { + parent->u.type_specifier.type = TYPESPEC_STRING; + parent->u.type_specifier.u.string = node; + } else + return -EPERM; + break; + case NODE_ENUMERATOR: + if (parent->type == NODE_ENUM) + cds_list_add(&node->siblings, &parent->u._enum.enumerator_list); + else + return -EPERM; + break; + case NODE_ENUM: + if (parent->type == NODE_TYPE_SPECIFIER) { + parent->u.type_specifier.type = TYPESPEC_ENUM; + parent->u.type_specifier.u._enum = node; + } else + return -EPERM; + break; + case NODE_STRUCT_OR_VARIANT_DECLARATION: + switch (parent->type) { + case NODE_STRUCT: + cds_list_add(&node->siblings, &parent->u.variant.declaration_list); + break; + case NODE_VARIANT: + cds_list_add(&node->siblings, &parent->u._struct.declaration_list); + break; + default: + return -EINVAL; + } + break; + case NODE_VARIANT: + if (parent->type == NODE_TYPE_SPECIFIER) { + parent->u.type_specifier.type = TYPESPEC_VARIANT; + parent->u.type_specifier.u.variant = node; + } else + return -EPERM; + break; + case NODE_STRUCT: + if (parent->type == NODE_TYPE_SPECIFIER) { + parent->u.type_specifier.type = TYPESPEC_STRUCT; + parent->u.type_specifier.u._struct = node; + } else + return -EPERM; + break; + + case NODE_UNKNOWN: + default: + fprintf(stderr, "[error] %s: unknown node type %d\n", __func__, + (int) parent->type); + return -EINVAL; + } + return 0; +} + void yyerror(struct ctf_scanner *scanner, const char *str) { fprintf(stderr, "error %s\n", str); @@ -164,11 +671,24 @@ static struct ctf_ast *ctf_ast_alloc(void) if (!ast) return NULL; memset(ast, 0, sizeof(*ast)); + CDS_INIT_LIST_HEAD(&ast->allocated_nodes); + ast->root.type = NODE_ROOT; + CDS_INIT_LIST_HEAD(&ast->root.siblings); + CDS_INIT_LIST_HEAD(&ast->root.u.root._typedef); + CDS_INIT_LIST_HEAD(&ast->root.u.root.typealias); + CDS_INIT_LIST_HEAD(&ast->root.u.root.declaration_specifier); + CDS_INIT_LIST_HEAD(&ast->root.u.root.trace); + CDS_INIT_LIST_HEAD(&ast->root.u.root.stream); + CDS_INIT_LIST_HEAD(&ast->root.u.root.event); return ast; } static void ctf_ast_free(struct ctf_ast *ast) { + struct ctf_node *node, *tmp; + + cds_list_for_each_entry_safe(node, tmp, &ast->allocated_nodes, gc) + free(node); } int ctf_scanner_append_ast(struct ctf_scanner *scanner) @@ -241,6 +761,10 @@ void ctf_scanner_free(struct ctf_scanner *scanner) struct ctf_node *n; } +%type event_declaration +%type ctf_assignment_expression_list +%type ctf_assignment_expression + %% file: @@ -345,6 +869,10 @@ declaration: event_declaration: event_declaration_begin event_declaration_end | event_declaration_begin ctf_assignment_expression_list event_declaration_end + { + $$ = make_node(scanner, NODE_EVENT); + /* TODO */ + } ; event_declaration_begin: @@ -625,6 +1153,11 @@ ctf_assignment_expression_list: ctf_assignment_expression: unary_expression EQUAL unary_expression + { + $$ = make_node(scanner, NODE_CTF_EXPRESSION); + /* TODO */ + + } | unary_expression TYPEASSIGN type_specifier | declaration_specifiers TYPEDEF declaration_specifiers type_declarator_list | TYPEDEF declaration_specifiers type_declarator_list -- 2.34.1