Changeset 3f3e088 in rtems-central


Ignore:
Timestamp:
10/10/20 19:18:29 (2 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
2e2d9eb
Parents:
faed4e3
git-author:
Sebastian Huber <sebastian.huber@…> (10/10/20 19:18:29)
git-committer:
Sebastian Huber <sebastian.huber@…> (10/11/20 13:06:58)
Message:

interface: Improve ordering

Close #4134.

Location:
rtemsspec
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • rtemsspec/interface.py

    rfaed4e3 r3f3e088  
    2727from contextlib import contextmanager
    2828import os
    29 from typing import Any, Callable, Dict, Iterator, List, Union
     29from typing import Any, Callable, Dict, Iterator, List, Union, Set
    3030
    3131from rtemsspec.content import CContent, CInclude, enabled_by_to_exp, \
     
    177177class Node:
    178178    """ Nodes of a header file. """
     179
     180    # pylint: disable=too-many-instance-attributes
    179181    def __init__(self, header_file: "_HeaderFile", item: Item,
    180182                 ingroups: ItemMap):
     
    186188        self.content = CContent()
    187189        self.mapper = _InterfaceMapper(self)
     190        try:
     191            group = next(item.children("placement-order"))
     192        except StopIteration:
     193            self.index = None
     194        else:
     195            self.index = (group.uid,
     196                          list(group.parents("placement-order")).index(item))
    188197
    189198    def __lt__(self, other: "Node") -> bool:
     
    428437
    429438
     439def _is_ready_to_bubble(before: Node, after: Node) -> bool:
     440    if after in before.dependents:
     441        return False
     442
     443    # Move the groups towards the top of the header file
     444    group = "interface/group"
     445    if (before.item.type == group) ^ (after.item.type == group):
     446        return after.item.type == group
     447
     448    # Move items with an explicit placement order towards the bottom of the
     449    # file
     450    if before.index and after.index:
     451        return before.index > after.index
     452    if after.index:
     453        return False
     454
     455    return before > after
     456
     457
     458def _bubble_sort(nodes: List[Node]) -> List[Node]:
     459    node_count = len(nodes)
     460    for i in range(node_count - 1):
     461        for j in range(node_count - 1 - i):
     462            if _is_ready_to_bubble(nodes[j], nodes[j + 1]):
     463                nodes[j], nodes[j + 1] = nodes[j + 1], nodes[j]
     464    return nodes
     465
     466
    430467class _HeaderFile:
    431468    """ A header file. """
     
    481518        """
    482519        Gets the nodes of this header file ordered according to node
    483         dependencies and UIDs.
    484 
    485         Performs a topological sort using Kahn's algorithm.
     520        dependencies and other criteria.
     521
     522        The nodes form a partially ordered set (poset).  The ordering is done
     523        in two steps.  Firstly, a topological sort using Kahn's algorithm is
     524        carried out.  Secondly, the nodes are sorted using a bubble sort which
     525        takes node dependencies into account.  There are more efficient ways to
     526        do this, however, if you experience run time problems due to this
     527        method, then maybe you should reconsider your header file organization.
    486528        """
    487529        nodes_in_dependency_order = []  # type: List[Node]
     
    492534            in_degree[node.item.uid] = len(node.dependents)
    493535
    494         # Create a queue with all nodes with no incoming edges sorted by UID
     536        # Create a queue with all nodes with no incoming edges
    495537        queue = []  # type: List[Node]
    496538        for node in self._nodes.values():
    497539            if in_degree[node.item.uid] == 0:
    498540                queue.append(node)
    499         queue.sort(reverse=True)
    500541
    501542        # Topological sort
     
    504545            nodes_in_dependency_order.insert(0, node)
    505546
    506             # Sort by UID
    507             for other in sorted(node.depends_on):
     547            for other in node.depends_on:
    508548                in_degree[other.item.uid] -= 1
    509549                if in_degree[other.item.uid] == 0:
    510550                    queue.append(other)
    511551
    512         return nodes_in_dependency_order
     552        return _bubble_sort(nodes_in_dependency_order)
    513553
    514554    def finalize(self) -> None:
  • rtemsspec/tests/spec-interface/gb.yml

    rfaed4e3 r3f3e088  
    2020  uid: func2
    2121- role: placement-order
     22  uid: func3
     23- role: placement-order
    2224  uid: enum
    2325name: Group B
  • rtemsspec/tests/test_interface.py

    rfaed4e3 r3f3e088  
    139139 */
    140140
    141 /* Generated from spec:/forward-decl */
    142 
    143 /* Forward declaration */
    144 struct Struct;
    145 
    146 /* Generated from spec:/enum */
    147 
    148 /**
    149  * @ingroup GroupB
    150  *
    151  * @brief Enum brief description.
    152  *
    153  * Enum description.
    154  */
    155 typedef enum {
    156   /**
    157    * @brief Enumerator 0 brief description.
    158    */
    159   ENUMERATOR_0,
    160 
    161   /**
    162    * @brief Enumerator 1 brief description.
    163    */
    164   ENUMERATOR_1,
    165 
    166   /**
    167    * @brief Enumerator 2 brief description.
    168    */
    169   ENUMERATOR_2
    170 } Enum;
    171 
    172141/* Generated from spec:/define */
    173142
     
    184153#endif
    185154
     155/* Generated from spec:/forward-decl */
     156
     157/* Forward declaration */
     158struct Struct;
     159
     160/* Generated from spec:/enum */
     161
     162/**
     163 * @ingroup GroupB
     164 *
     165 * @brief Enum brief description.
     166 *
     167 * Enum description.
     168 */
     169typedef enum {
     170  /**
     171   * @brief Enumerator 0 brief description.
     172   */
     173  ENUMERATOR_0,
     174
     175  /**
     176   * @brief Enumerator 1 brief description.
     177   */
     178  ENUMERATOR_1,
     179
     180  /**
     181   * @brief Enumerator 2 brief description.
     182   */
     183  ENUMERATOR_2
     184} Enum;
     185
    186186/* Generated from spec:/enum3 */
    187187
     
    218218 */
    219219void Function( int Param0, const int *Param1, int *Param2, int *Param3 );
     220
     221/* Generated from spec:/macro */
     222
     223/**
     224 * @ingroup GroupB
     225 *
     226 * @brief Very long macro brief description.
     227 *
     228 * @param VeryLongParam0 is very long parameter 0 with some super important and
     229 *   extra very long description which makes a lot of sense.
     230 *
     231 * @param[in] VeryLongParam1 is very long parameter 1.
     232 *
     233 * @param[out] VeryLongParam2 is very long parameter 2.
     234 *
     235 * @param[in,out] VeryLongParam3 is very long parameter 3.
     236 *
     237 * @retval 1 is returned, in case A.
     238 *
     239 * @retval 2 is returned, in case B.
     240 *
     241 * @return Sometimes some value.
     242 */
     243#define VERY_LONG_MACRO( \\
     244  VeryLongParam0, \\
     245  VeryLongParam1, \\
     246  VeryLongParam2, \\
     247  VeryLongParam3 \\
     248) \\
     249  do { \\
     250    (void) VeryLongParam1; \\
     251    (void) VeryLongParam2; \\
     252    (void) VeryLongParam3; \\
     253  } while ( 0 ); \\
     254  VeryLongParam0 + 1;
     255
     256/* Generated from spec:/macro2 */
     257
     258/**
     259 * @ingroup GroupB
     260 *
     261 * @brief Short macro brief description.
     262 *
     263 * @param Param0 is parameter 0.
     264 *
     265 * @return Sometimes some value.
     266 */
     267#if 0
     268  #define MACRO( Param0 )
     269#else
     270  #define MACRO( Param0 ) ( ( Param0 ) + 1 )
     271#endif
     272
     273/* Generated from spec:/s */
     274
     275/**
     276 * @ingroup GroupC
     277 */
     278struct Struct {
     279  /**
     280   * @brief Brief union description.
     281   *
     282   * Union description.
     283   */
     284  union {
     285    /**
     286     * @brief Brief member description.
     287     *
     288     * Member description.
     289     */
     290    uint32_t some_member;
     291
     292    /**
     293     * @brief Brief struct description.
     294     *
     295     * struct description.
     296     */
     297    struct {
     298      /**
     299       * @brief Brief member 2 description.
     300       *
     301       * Member 2 description.
     302       */
     303      uint32_t some_member_2;
     304
     305      /**
     306       * @brief Brief member 3 description.
     307       *
     308       * Member 3 description.
     309       */
     310      Enum some_member_3;
     311    } some_struct;
     312  } some_union;
     313
     314  /**
     315   * @brief Brief member 4 description.
     316   *
     317   * Member 4 description.
     318   */
     319  Enum some_member_4;
     320};
     321
     322/* Generated from spec:/td */
     323
     324/**
     325 * @ingroup GroupB
     326 *
     327 * @brief Typedef Integer brief description.
     328 *
     329 * Typedef Integer description.
     330 */
     331typedef uint32_t Integer /* Some comment. */;
     332
     333/* Generated from spec:/td3 */
     334
     335/**
     336 * @ingroup GroupB
     337 */
     338#if defined(RTEMS_SMP)
     339  typedef uint32_t Integer3;
     340#endif
     341
     342#if !defined(ASM)
     343  /* Generated from spec:/var */
     344
     345  /**
     346   * @ingroup GroupC
     347   *
     348   * @brief Variable brief description.
     349   *
     350   * Variable description.
     351   */
     352  extern struct Struct *Variable;
     353#endif
    220354
    221355/* Generated from spec:/func2 */
     
    260394}
    261395
    262 /* Generated from spec:/macro */
    263 
    264 /**
    265  * @ingroup GroupB
    266  *
    267  * @brief Very long macro brief description.
    268  *
    269  * @param VeryLongParam0 is very long parameter 0 with some super important and
    270  *   extra very long description which makes a lot of sense.
    271  *
    272  * @param[in] VeryLongParam1 is very long parameter 1.
    273  *
    274  * @param[out] VeryLongParam2 is very long parameter 2.
    275  *
    276  * @param[in,out] VeryLongParam3 is very long parameter 3.
    277  *
    278  * @retval 1 is returned, in case A.
    279  *
    280  * @retval 2 is returned, in case B.
    281  *
    282  * @return Sometimes some value.
    283  */
    284 #define VERY_LONG_MACRO( \\
    285   VeryLongParam0, \\
    286   VeryLongParam1, \\
    287   VeryLongParam2, \\
    288   VeryLongParam3 \\
    289 ) \\
    290   do { \\
    291     (void) VeryLongParam1; \\
    292     (void) VeryLongParam2; \\
    293     (void) VeryLongParam3; \\
    294   } while ( 0 ); \\
    295   VeryLongParam0 + 1;
    296 
    297 /* Generated from spec:/macro2 */
    298 
    299 /**
    300  * @ingroup GroupB
    301  *
    302  * @brief Short macro brief description.
    303  *
    304  * @param Param0 is parameter 0.
    305  *
    306  * @return Sometimes some value.
    307  */
    308 #if 0
    309   #define MACRO( Param0 )
    310 #else
    311   #define MACRO( Param0 ) ( ( Param0 ) + 1 )
    312 #endif
    313 
    314 /* Generated from spec:/s */
    315 
    316 /**
    317  * @ingroup GroupC
    318  */
    319 struct Struct {
    320   /**
    321    * @brief Brief union description.
    322    *
    323    * Union description.
    324    */
    325   union {
    326     /**
    327      * @brief Brief member description.
    328      *
    329      * Member description.
    330      */
    331     uint32_t some_member;
    332 
    333     /**
    334      * @brief Brief struct description.
    335      *
    336      * struct description.
    337      */
    338     struct {
    339       /**
    340        * @brief Brief member 2 description.
    341        *
    342        * Member 2 description.
    343        */
    344       uint32_t some_member_2;
    345 
    346       /**
    347        * @brief Brief member 3 description.
    348        *
    349        * Member 3 description.
    350        */
    351       Enum some_member_3;
    352     } some_struct;
    353   } some_union;
    354 
    355   /**
    356    * @brief Brief member 4 description.
    357    *
    358    * Member 4 description.
    359    */
    360   Enum some_member_4;
    361 };
    362 
    363 /* Generated from spec:/td */
    364 
    365 /**
    366  * @ingroup GroupB
    367  *
    368  * @brief Typedef Integer brief description.
    369  *
    370  * Typedef Integer description.
    371  */
    372 typedef uint32_t Integer /* Some comment. */;
    373 
    374 /* Generated from spec:/td3 */
    375 
    376 /**
    377  * @ingroup GroupB
    378  */
    379 #if defined(RTEMS_SMP)
    380   typedef uint32_t Integer3;
    381 #endif
    382 
    383 #if !defined(ASM)
    384   /* Generated from spec:/var */
    385 
    386   /**
    387    * @ingroup GroupC
    388    *
    389    * @brief Variable brief description.
    390    *
    391    * Variable description.
    392    */
    393   extern struct Struct *Variable;
    394 #endif
    395 
    396396#ifdef __cplusplus
    397397}
Note: See TracChangeset for help on using the changeset viewer.