From 4481ff1ad9f2d5fa2eae803e848b6d480496d7c7 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Fri, 19 Mar 2021 08:58:11 +0100 Subject: validation: Optimize transition map Further reduce the source code and read-only data size through one level of indirection. --- rtemsspec/tests/test_validation.py | 144 ++++++++++++++---------------------- rtemsspec/validation.py | 146 +++++++++++++++++++++---------------- 2 files changed, 139 insertions(+), 151 deletions(-) diff --git a/rtemsspec/tests/test_validation.py b/rtemsspec/tests/test_validation.py index 35ae8475..a4873746 100644 --- a/rtemsspec/tests/test_validation.py +++ b/rtemsspec/tests/test_validation.py @@ -622,62 +622,24 @@ typedef struct { uint16_t Post_Id : 3; } Directive_Entry; -#define E( x0, x1, x2, x3, x4, x5) { x0, x1, x2, x3, \\ - Directive_Post_Status_##x4, Directive_Post_Id_##x5 } - -#define EZ( x0, x1) { 0, 0, 0, 0, Directive_Post_Status_##x0, \\ - Directive_Post_Id_##x1 } - static const Directive_Entry -Directive_Map[] = { - EZ( InvAddr, NullPtr ), - EZ( InvName, Nop ), - EZ( InvAddr, NullPtr ), - EZ( InvName, Nop ), - EZ( InvAddr, NullPtr ), - EZ( InvName, Nop ), - EZ( InvAddr, NullPtr ), - EZ( InvName, Nop ), - EZ( InvAddr, NullPtr ), - EZ( InvName, Nop ), - EZ( InvAddr, NullPtr ), - EZ( InvName, Nop ), - EZ( InvAddr, NullPtr ), - EZ( Ok, Self ), - EZ( InvAddr, NullPtr ), - EZ( Ok, Self ), - EZ( InvAddr, NullPtr ), - EZ( Ok, Self ), - EZ( InvAddr, NullPtr ), - EZ( Ok, Self ), - EZ( InvAddr, NullPtr ), - EZ( Ok, Self ), - EZ( InvAddr, NullPtr ), - EZ( Ok, Self ), - EZ( InvAddr, NullPtr ), - EZ( Ok, LocalTask ), - EZ( InvAddr, NullPtr ), -#if defined(RTEMS_MULTIPROCESSING) - EZ( Ok, RemoteTask ), -#else - EZ( InvName, Nop ), -#endif - EZ( InvAddr, NullPtr ), - EZ( InvName, Nop ), - EZ( InvAddr, NullPtr ), - EZ( Ok, LocalTask ), - EZ( InvAddr, NullPtr ), +Directive_Entries[] = { + { 0, 0, 0, 0, Directive_Post_Status_InvAddr, Directive_Post_Id_NullPtr }, + { 0, 0, 0, 0, Directive_Post_Status_InvName, Directive_Post_Id_Nop }, + { 0, 0, 0, 0, Directive_Post_Status_Ok, Directive_Post_Id_Self }, + { 0, 0, 0, 0, Directive_Post_Status_Ok, Directive_Post_Id_LocalTask }, #if defined(RTEMS_MULTIPROCESSING) - EZ( Ok, RemoteTask ), + { 0, 0, 0, 0, Directive_Post_Status_Ok, Directive_Post_Id_RemoteTask } #else - EZ( InvName, Nop ), + { 0, 0, 0, 0, Directive_Post_Status_InvName, Directive_Post_Id_Nop } #endif - EZ( InvAddr, NullPtr ), - EZ( Ok, LocalTask ) }; -#undef E -#undef EZ +static const uint8_t +Directive_Map[] = { + 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 2, 0, 3, + 0, 4, 0, 1, 0, 3, 0, 4, 0, 3 +}; static size_t Directive_Scope( void *arg, char *buf, size_t n ) { @@ -700,12 +662,20 @@ static T_fixture Directive_Fixture = { .initial_context = &Directive_Instance }; +static inline Directive_Entry Directive_GetEntry( size_t index ) +{ + return Directive_Entries[ + Directive_Map[ index ] + ]; +} + /** * @fn void T_case_body_Directive( void ) */ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) { Directive_Context *ctx; + Directive_Entry entry; size_t index; ctx = T_fixture_context(); @@ -717,7 +687,9 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) ctx->pcs[ 0 ] < Directive_Pre_Name_NA; ++ctx->pcs[ 0 ] ) { - if ( Directive_Map[ index ].Pre_Name_NA ) { + entry = Directive_GetEntry( index ); + + if ( entry.Pre_Name_NA ) { ctx->pcs[ 0 ] = Directive_Pre_Name_NA; index += ( Directive_Pre_Name_NA - 1 ) * Directive_Pre_Node_NA @@ -729,7 +701,9 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) ctx->pcs[ 1 ] < Directive_Pre_Node_NA; ++ctx->pcs[ 1 ] ) { - if ( Directive_Map[ index ].Pre_Node_NA ) { + entry = Directive_GetEntry( index ); + + if ( entry.Pre_Node_NA ) { ctx->pcs[ 1 ] = Directive_Pre_Node_NA; index += ( Directive_Pre_Node_NA - 1 ) * Directive_Pre_Id_NA; @@ -740,14 +714,14 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) ctx->pcs[ 2 ] < Directive_Pre_Id_NA; ++ctx->pcs[ 2 ] ) { - Directive_Entry entry; + entry = Directive_GetEntry( index ); - if ( Directive_Map[ index ].Pre_Id_NA ) { + if ( entry.Pre_Id_NA ) { ctx->pcs[ 2 ] = Directive_Pre_Id_NA; index += ( Directive_Pre_Id_NA - 1 ); } - if ( Directive_Map[ index ].Skip ) { + if ( entry.Skip ) { ++index; continue; } @@ -756,7 +730,6 @@ T_TEST_CASE_FIXTURE( Directive, &Directive_Fixture ) Directive_Pre_Node_Prepare( ctx, ctx->pcs[ 1 ] ); Directive_Pre_Id_Prepare( ctx, ctx->pcs[ 2 ] ); Directive_Action( ctx ); - entry = Directive_Map[ index ]; Directive_Post_Status_Check( ctx, entry.Post_Status ); Directive_Post_Id_Check( ctx, entry.Post_Id ); ++index; @@ -2125,35 +2098,19 @@ typedef struct { uint16_t Post_B : 2; } Action2_Entry; -#define E( x0, x1, x2, x3, x4, x5) { x0, x1, x2, x3, Action2_Post_A_##x4, \\ - Action2_Post_B_##x5 } - -#define EZ( x0, x1) { 0, 0, 0, 0, Action2_Post_A_##x0, Action2_Post_B_##x1 } - static const Action2_Entry -Action2_Map[] = { - EZ( A1, B0 ), - EZ( A1, B0 ), - EZ( A1, B0 ), - E( 0, 1, 0, 0, A1, NA ), - E( 0, 1, 0, 0, A1, NA ), - E( 0, 1, 0, 0, A1, NA ), - EZ( A2, B0 ), - EZ( A2, B0 ), - EZ( A2, B0 ), - EZ( A2, B0 ), - EZ( A2, B0 ), - EZ( A3, B0 ), - E( 0, 1, 0, 0, A1, NA ), - E( 0, 1, 0, 0, A1, NA ), - E( 0, 1, 0, 0, A1, NA ), - E( 1, 0, 0, 0, NA, NA ), - E( 1, 0, 0, 0, NA, NA ), - E( 1, 0, 0, 0, NA, NA ) +Action2_Entries[] = { + { 0, 1, 0, 0, Action2_Post_A_A1, Action2_Post_B_NA }, + { 0, 0, 0, 0, Action2_Post_A_A2, Action2_Post_B_B0 }, + { 0, 0, 0, 0, Action2_Post_A_A1, Action2_Post_B_B0 }, + { 1, 0, 0, 0, Action2_Post_A_NA, Action2_Post_B_NA }, + { 0, 0, 0, 0, Action2_Post_A_A3, Action2_Post_B_B0 } }; -#undef E -#undef EZ +static const uint8_t +Action2_Map[] = { + 2, 2, 2, 0, 0, 0, 1, 1, 1, 1, 1, 4, 0, 0, 0, 3, 3, 3 +}; static size_t Action2_Scope( void *arg, char *buf, size_t n ) { @@ -2176,11 +2133,19 @@ static T_fixture Action2_Fixture = { .initial_context = &Action2_Instance }; +static inline Action2_Entry Action2_GetEntry( size_t index ) +{ + return Action2_Entries[ + Action2_Map[ index ] + ]; +} + static T_fixture_node Action2_Node; void Action2_Run( int *a, int b, int *c ) { Action2_Context *ctx; + Action2_Entry entry; size_t index; ctx = T_push_fixture( &Action2_Node, &Action2_Fixture ); @@ -2196,7 +2161,9 @@ void Action2_Run( int *a, int b, int *c ) ctx->pcs[ 0 ] < Action2_Pre_A_NA; ++ctx->pcs[ 0 ] ) { - if ( Action2_Map[ index ].Pre_A_NA ) { + entry = Action2_GetEntry( index ); + + if ( entry.Pre_A_NA ) { ctx->pcs[ 0 ] = Action2_Pre_A_NA; index += ( Action2_Pre_A_NA - 1 ) * Action2_Pre_B_NA @@ -2208,7 +2175,9 @@ void Action2_Run( int *a, int b, int *c ) ctx->pcs[ 1 ] < Action2_Pre_B_NA; ++ctx->pcs[ 1 ] ) { - if ( Action2_Map[ index ].Pre_B_NA ) { + entry = Action2_GetEntry( index ); + + if ( entry.Pre_B_NA ) { ctx->pcs[ 1 ] = Action2_Pre_B_NA; index += ( Action2_Pre_B_NA - 1 ) * Action2_Pre_C_NA; @@ -2219,14 +2188,14 @@ void Action2_Run( int *a, int b, int *c ) ctx->pcs[ 2 ] < Action2_Pre_C_NA; ++ctx->pcs[ 2 ] ) { - Action2_Entry entry; + entry = Action2_GetEntry( index ); - if ( Action2_Map[ index ].Pre_C_NA ) { + if ( entry.Pre_C_NA ) { ctx->pcs[ 2 ] = Action2_Pre_C_NA; index += ( Action2_Pre_C_NA - 1 ); } - if ( Action2_Map[ index ].Skip ) { + if ( entry.Skip ) { ++index; continue; } @@ -2236,7 +2205,6 @@ void Action2_Run( int *a, int b, int *c ) Action2_Pre_B_Prepare( ctx, ctx->pcs[ 1 ] ); Action2_Pre_C_Prepare( ctx, ctx->pcs[ 2 ] ); Action2_Action( ctx ); - entry = Action2_Map[ index ]; Action2_Post_A_Check( ctx, entry.Post_A ); Action2_Post_B_Check( ctx, entry.Post_B ); Action2_Cleanup( ctx ); diff --git a/rtemsspec/validation.py b/rtemsspec/validation.py index c3034f85..e75aff95 100644 --- a/rtemsspec/validation.py +++ b/rtemsspec/validation.py @@ -467,8 +467,31 @@ class Transition(NamedTuple): post_cond: Tuple[int, ...] +class _TransitionEntry: + def __init__(self): + self.key = "" + self.variants = [] # type: List[Transition] + + def __bool__(self): + return bool(self.variants) + + def __getitem__(self, key): + return self.variants[key] + + def __len__(self): + return len(self.variants) + + def add(self, variant: Transition) -> None: + """ Adds the variant to the transitions of the entry. """ + self.key += "".join( + (enabled_by_to_exp(variant.enabled_by, + ExpressionMapper()), str(variant.skip), + str(variant.pre_cond_na), str(variant.post_cond))) + self.variants.append(variant) + + _IdxToX = Tuple[Tuple[str, ...], ...] -_TransitionMap = List[List[Transition]] +_TransitionMap = List[_TransitionEntry] def _to_st_idx(conditions: List[Any]) -> Tuple[Dict[str, int], ...]: @@ -619,8 +642,9 @@ class TransitionMap: self._post_co_idx_to_co_name = dict( (co_idx, condition["name"]) for co_idx, condition in enumerate(item["post-conditions"])) + self._entries = {} # type: Dict[str, List[Any]] self._map = self._build_map() - self._check_completeness() + self._post_process() def __getitem__(self, key: str): return self._item[key] @@ -628,7 +652,7 @@ class TransitionMap: def __iter__(self): yield from self._map - def _check_completeness(self) -> None: + def _post_process(self) -> None: for map_idx, transitions in enumerate(self): if not transitions or not isinstance( transitions[0].enabled_by, @@ -637,6 +661,14 @@ class TransitionMap: f"transition map of {self._item.spec} contains no default " "entry for pre-condition set " f"{{{self._map_index_to_pre_conditions(map_idx)}}}") + entry = self._entries.get(transitions.key, [0, 0, transitions]) + entry[0] += 1 + self._entries[transitions.key] = entry + for index, entry in enumerate( + sorted(self._entries.values(), + key=lambda x: x[0], + reverse=True)): + entry[1] = index def _map_index_to_pre_conditions(self, map_idx: int) -> str: conditions = [] @@ -776,7 +808,7 @@ class TransitionMap: f"{self._item.spec} is the first variant for " f"{{{self._map_index_to_pre_conditions(map_idx)}}} " "and it is not enabled by default") - transition_map[map_idx].append( + transition_map[map_idx].add( Transition(desc_idx, enabled_by, skip_post_cond[0], pre_cond_na, post_cond)) @@ -786,7 +818,7 @@ class TransitionMap: enabled_by = desc["enabled-by"] for map_idx, transition in enumerate(transition_map): if not transition: - transition.append( + transition.add( Transition( desc_idx, enabled_by, skip_post_cond[0], (0, ) * self._pre_co_count, @@ -807,8 +839,7 @@ class TransitionMap: raise ValueError(f"pre-condition '{condition['name']}' of " f"{self._item.spec} has no states") transition_count *= state_count - transition_map = [list() for _ in range(transition_count) - ] # type: _TransitionMap + transition_map = [_TransitionEntry() for _ in range(transition_count)] for desc_idx, desc in enumerate(self["transition-map"]): if isinstance(desc["post-conditions"], dict): try: @@ -833,25 +864,17 @@ class TransitionMap: skip_post_cond) return transition_map - def _get_entry(self, variant: Transition) -> str: - skip_pre_cond_na = (variant.skip, ) + variant.pre_cond_na - for value in skip_pre_cond_na: - if value != 0: - text = "E( " + ", ".join( - itertools.chain( - map(str, skip_pre_cond_na), - (self._post_co_idx_st_idx_to_st_name[co_idx][st_idx] - for co_idx, st_idx in enumerate(variant.post_cond)))) - break - else: - text = "EZ( " + ", ".join( - self._post_co_idx_st_idx_to_st_name[co_idx][st_idx] - for co_idx, st_idx in enumerate(variant.post_cond)) + def _get_entry(self, ident: str, variant: Transition) -> str: + text = "{ " + ", ".join( + itertools.chain(map(str, (variant.skip, ) + variant.pre_cond_na), ( + (f"{ident}_Post_{self._post_co_idx_to_co_name[co_idx]}" + f"_{self._post_co_idx_st_idx_to_st_name[co_idx][st_idx]}") + for co_idx, st_idx in enumerate(variant.post_cond)))) wrapper = textwrap.TextWrapper() wrapper.initial_indent = " " - wrapper.subsequent_indent = " " - wrapper.width = 75 - return "\n".join(wrapper.wrap(text)) + " )," + wrapper.subsequent_indent = " " + wrapper.width = 79 + return "\n".join(wrapper.wrap(text)) + " }," def _get_entry_bits(self) -> int: bits = self._pre_co_count + 1 @@ -859,42 +882,24 @@ class TransitionMap: bits += math.ceil(math.log2(len(st_idx_to_st_name))) return 2**max(math.ceil(math.log2(bits)), 3) - def _add_entry_macro(self, content: CContent, ident: str, name: str, - pre_count_0: int, pre_count_1: int) -> None: - # pylint: disable=too-many-arguments - entry = f"#define {name}( " - entry += ", ".join( - f"x{index}" for index in range(pre_count_0 + self._post_co_count)) - entry += ") { " - entry += ", ".join( - itertools.chain( - (f"x{index}" for index in range(pre_count_0)), - ("0" for index in range(pre_count_1)), - (f"{ident}_Post_{condition['name']}_##x{pre_count_0 + co_idx}" - for co_idx, condition in enumerate(self["post-conditions"])))) - wrapper = textwrap.TextWrapper() - wrapper.initial_indent = "" - wrapper.subsequent_indent = " " - wrapper.width = 77 - content.add(" \\\n".join(wrapper.wrap(entry)) + " }") - def add_map(self, content: CContent, ident: str) -> None: """ Adds the transition map definitions to the content. """ entries = [] mapper = ExpressionMapper() - for transistions in self._map: - if len(transistions) == 1: - entries.append(self._get_entry(transistions[0])) + for entry in sorted(self._entries.values(), key=lambda x: x[1]): + transitions = entry[2] + if len(transitions) == 1: + entries.append(self._get_entry(ident, transitions[0])) else: ifelse = "#if " enumerators = [] # type: List[str] - for variant in transistions[1:]: + for variant in transitions[1:]: enumerators.append( ifelse + enabled_by_to_exp(variant.enabled_by, mapper)) - enumerators.append(self._get_entry(variant)) + enumerators.append(self._get_entry(ident, variant)) ifelse = "#elif " enumerators.append("#else") - enumerators.append(self._get_entry(transistions[0])) + enumerators.append(self._get_entry(ident, transitions[0])) enumerators.append("#endif") entries.append("\n".join(enumerators)) bits = self._get_entry_bits() @@ -908,13 +913,21 @@ class TransitionMap: content.append( f"uint{bits}_t Post_{condition['name']} : {state_bits};") content.add(f"}} {ident}_Entry;") - pre_count = 1 + self._pre_co_count - self._add_entry_macro(content, ident, "E", pre_count, 0) - self._add_entry_macro(content, ident, "EZ", 0, pre_count) - content.add([f"static const {ident}_Entry", f"{ident}_Map[] = {{"]) - entries[-1] = entries[-1].replace("),", ")") + content.add([f"static const {ident}_Entry", f"{ident}_Entries[] = {{"]) + entries[-1] = entries[-1].replace("},", "}") content.append(entries) - content.append(["};", "", "#undef E", "#undef EZ"]) + bits = math.ceil(math.log2(len(self._entries)) / 8) * 8 + content.append( + ["};", "", f"static const uint{bits}_t", f"{ident}_Map[] = {{"]) + text = ", ".join( + str(self._entries[transitions.key][1]) + for transitions in self._map) + wrapper = textwrap.TextWrapper() + wrapper.initial_indent = " " + wrapper.subsequent_indent = " " + wrapper.width = 79 + content.append(wrapper.wrap(text)) + content.append("};") def get_post_entry_member(self, co_idx: int) -> str: """ @@ -996,7 +1009,7 @@ class _ActionRequirementTestItem(_TestItem): def _add_loop_body(self, content: CContent, transition_map: TransitionMap) -> None: - with content.condition(f"{self.ident}_Map[ index ].Skip"): + with content.condition("entry.Skip"): content.append(["++index;", "continue;"]) content.add_blank_line() self._add_call(content, "test-prepare", "Prepare") @@ -1005,7 +1018,6 @@ class _ActionRequirementTestItem(_TestItem): content.call_function(None, f"{enum[0]}_Prepare", ["ctx", f"ctx->pcs[ {index} ]"]) self._add_call(content, "test-action", "Action") - content.append(f"entry = {self.ident}_Map[ index ];") for index, enum in enumerate(self._post_co_idx_to_enum): content.gap = False content.call_function(None, f"{enum[0]}_Check", [ @@ -1022,11 +1034,10 @@ class _ActionRequirementTestItem(_TestItem): end = self._pre_co_idx_to_enum[index][-1] with content.for_loop(f"{var} = {begin}", f"{var} < {end}", f"++{var}"): - if index + 1 == self._pre_co_count: - content.add(f"{self.ident}_Entry entry;") name = self._item['pre-conditions'][index]["name"] - pre_na = f"{self.ident}_Map[ index ].Pre_{name}_NA" - with content.condition(pre_na): + content.call_function("entry =", f"{self.ident}_GetEntry", + ["index"]) + with content.condition(f"entry.Pre_{name}_NA"): content.append(f"{var} = {end};") content.append(f"index += ( {end} - 1 )") for index_2 in range(index + 1, self._pre_co_count): @@ -1040,6 +1051,15 @@ class _ActionRequirementTestItem(_TestItem): def _add_test_case(self, content: CContent, transition_map: TransitionMap, header: Dict[str, Any]) -> None: + ret = f"static inline {self.ident}_Entry" + name = f"{self.ident}_GetEntry" + params = ["size_t index"] + with content.function(ret, name, params, align=True): + content.add([ + f"return {self.ident}_Entries[", + f" {self.ident}_Map[ index ]", "];" + ]) + entry = f"{self.ident}_Entry entry;" fixture = f"{self.ident}_Fixture" prologue = CContent() epilogue = CContent() @@ -1048,7 +1068,7 @@ class _ActionRequirementTestItem(_TestItem): ret = "void" name = f"{self.ident}_Run" params = self._get_run_params(header) - prologue.add([f"{self.context} *ctx;", "size_t index;"]) + prologue.add([f"{self.context} *ctx;", entry, "size_t index;"]) prologue.call_function("ctx =", "T_push_fixture", [f"&{self.ident}_Node", f"&{fixture}"]) prologue.add([ @@ -1066,7 +1086,7 @@ class _ActionRequirementTestItem(_TestItem): name = "T_TEST_CASE_FIXTURE" params = [f"{self.ident}", f"&{fixture}"] prologue.add([ - f"{self.context} *ctx;", "size_t index;", "", + f"{self.context} *ctx;", entry, "size_t index;", "", "ctx = T_fixture_context();", "ctx->in_action_loop = true;", "index = 0;" ]) -- cgit v1.2.3