[rtems-central commit] interface: Improve ordering
Sebastian Huber
sebh at rtems.org
Sun Oct 11 13:21:03 UTC 2020
Module: rtems-central
Branch: master
Commit: 3f3e088740abc2d00cf9986452bef81eae83260e
Changeset: http://git.rtems.org/rtems-central/commit/?id=3f3e088740abc2d00cf9986452bef81eae83260e
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Sat Oct 10 21:18:29 2020 +0200
interface: Improve ordering
Close #4134.
---
rtemsspec/interface.py | 58 +++++++++++++++---
rtemsspec/tests/spec-interface/gb.yml | 2 +
rtemsspec/tests/test_interface.py | 110 +++++++++++++++++-----------------
3 files changed, 106 insertions(+), 64 deletions(-)
diff --git a/rtemsspec/interface.py b/rtemsspec/interface.py
index 0628833..57ed8e5 100644
--- a/rtemsspec/interface.py
+++ b/rtemsspec/interface.py
@@ -26,7 +26,7 @@
from contextlib import contextmanager
import os
-from typing import Any, Callable, Dict, Iterator, List, Union
+from typing import Any, Callable, Dict, Iterator, List, Union, Set
from rtemsspec.content import CContent, CInclude, enabled_by_to_exp, \
ExpressionMapper, get_value_double_colon, get_value_doxygen_function, \
@@ -176,6 +176,8 @@ def _add_definition(node: "Node", item: Item, prefix: str,
class Node:
""" Nodes of a header file. """
+
+ # pylint: disable=too-many-instance-attributes
def __init__(self, header_file: "_HeaderFile", item: Item,
ingroups: ItemMap):
self.header_file = header_file
@@ -185,6 +187,13 @@ class Node:
self.depends_on = set() # type: Set["Node"]
self.content = CContent()
self.mapper = _InterfaceMapper(self)
+ try:
+ group = next(item.children("placement-order"))
+ except StopIteration:
+ self.index = None
+ else:
+ self.index = (group.uid,
+ list(group.parents("placement-order")).index(item))
def __lt__(self, other: "Node") -> bool:
return self.item.uid < other.item.uid
@@ -427,6 +436,34 @@ _NODE_GENERATORS = {
}
+def _is_ready_to_bubble(before: Node, after: Node) -> bool:
+ if after in before.dependents:
+ return False
+
+ # Move the groups towards the top of the header file
+ group = "interface/group"
+ if (before.item.type == group) ^ (after.item.type == group):
+ return after.item.type == group
+
+ # Move items with an explicit placement order towards the bottom of the
+ # file
+ if before.index and after.index:
+ return before.index > after.index
+ if after.index:
+ return False
+
+ return before > after
+
+
+def _bubble_sort(nodes: List[Node]) -> List[Node]:
+ node_count = len(nodes)
+ for i in range(node_count - 1):
+ for j in range(node_count - 1 - i):
+ if _is_ready_to_bubble(nodes[j], nodes[j + 1]):
+ nodes[j], nodes[j + 1] = nodes[j + 1], nodes[j]
+ return nodes
+
+
class _HeaderFile:
""" A header file. """
def __init__(self, item: Item, enabled_by_defined: Dict[str, str]):
@@ -480,9 +517,14 @@ class _HeaderFile:
def _get_nodes_in_dependency_order(self) -> List[Node]:
"""
Gets the nodes of this header file ordered according to node
- dependencies and UIDs.
-
- Performs a topological sort using Kahn's algorithm.
+ dependencies and other criteria.
+
+ The nodes form a partially ordered set (poset). The ordering is done
+ in two steps. Firstly, a topological sort using Kahn's algorithm is
+ carried out. Secondly, the nodes are sorted using a bubble sort which
+ takes node dependencies into account. There are more efficient ways to
+ do this, however, if you experience run time problems due to this
+ method, then maybe you should reconsider your header file organization.
"""
nodes_in_dependency_order = [] # type: List[Node]
@@ -491,25 +533,23 @@ class _HeaderFile:
for node in self._nodes.values():
in_degree[node.item.uid] = len(node.dependents)
- # Create a queue with all nodes with no incoming edges sorted by UID
+ # Create a queue with all nodes with no incoming edges
queue = [] # type: List[Node]
for node in self._nodes.values():
if in_degree[node.item.uid] == 0:
queue.append(node)
- queue.sort(reverse=True)
# Topological sort
while queue:
node = queue.pop(0)
nodes_in_dependency_order.insert(0, node)
- # Sort by UID
- for other in sorted(node.depends_on):
+ for other in node.depends_on:
in_degree[other.item.uid] -= 1
if in_degree[other.item.uid] == 0:
queue.append(other)
- return nodes_in_dependency_order
+ return _bubble_sort(nodes_in_dependency_order)
def finalize(self) -> None:
""" Finalizes the header file. """
diff --git a/rtemsspec/tests/spec-interface/gb.yml b/rtemsspec/tests/spec-interface/gb.yml
index 43cffe2..38660c2 100644
--- a/rtemsspec/tests/spec-interface/gb.yml
+++ b/rtemsspec/tests/spec-interface/gb.yml
@@ -19,6 +19,8 @@ links:
- role: placement-order
uid: func2
- role: placement-order
+ uid: func3
+- role: placement-order
uid: enum
name: Group B
type: interface
diff --git a/rtemsspec/tests/test_interface.py b/rtemsspec/tests/test_interface.py
index 357a411..897430f 100644
--- a/rtemsspec/tests/test_interface.py
+++ b/rtemsspec/tests/test_interface.py
@@ -138,6 +138,20 @@ extern "C" {
* @ingroup GroupA
*/
+/* Generated from spec:/define */
+
+/**
+ * @ingroup GroupA
+ */
+#if defined(A) || (B > C)
+ #define DEFINE ((float_t) 456)
+#elif defined(C) && defined(D)
+ #define DEFINE ((float_t) 789)
+#else
+ #define DEFINE \\
+ ((float_t) 123)
+#endif
+
/* Generated from spec:/forward-decl */
/* Forward declaration */
@@ -169,20 +183,6 @@ typedef enum {
ENUMERATOR_2
} Enum;
-/* Generated from spec:/define */
-
-/**
- * @ingroup GroupA
- */
-#if defined(A) || (B > C)
- #define DEFINE ((float_t) 456)
-#elif defined(C) && defined(D)
- #define DEFINE ((float_t) 789)
-#else
- #define DEFINE \\
- ((float_t) 123)
-#endif
-
/* Generated from spec:/enum3 */
/**
@@ -218,47 +218,6 @@ typedef enum EnumB {
*/
void Function( int Param0, const int *Param1, int *Param2, int *Param3 );
-/* Generated from spec:/func2 */
-
-/**
- * @ingroup GroupB
- *
- * @brief Very long function brief description.
- *
- * VeryLongFunction description.
- *
- * VeryLongFunction notes.
- *
- * @param VeryLongParam0 is very long parameter 0 with some super important and
- * extra very long description which makes a lot of sense.
- *
- * @param[in] VeryLongParam1 is very long parameter 1.
- *
- * @param[out] VeryLongParam2 is very long parameter 2.
- *
- * @param[in,out] VeryLongParam3 is very long parameter 3.
- *
- * @retval 1 is returned, in case A.
- *
- * @retval 2 is returned, in case B.
- *
- * @retval #Enum is returned, in case C.
- *
- * @return Sometimes some value. See Function().
- */
-static inline int VeryLongFunction(
- int VeryLongParam0,
- const struct Struct *VeryLongParam1,
- struct Struct *( *VeryLongParam2 )( void ),
- struct Struct *VeryLongParam3
-)
-{
- (void) VeryLongParam1;
- (void) VeryLongParam2;
- (void) VeryLongParam3;
- return VeryLongParam0 + 1;
-}
-
/* Generated from spec:/macro */
/**
@@ -393,6 +352,47 @@ typedef uint32_t Integer /* Some comment. */;
extern struct Struct *Variable;
#endif
+/* Generated from spec:/func2 */
+
+/**
+ * @ingroup GroupB
+ *
+ * @brief Very long function brief description.
+ *
+ * VeryLongFunction description.
+ *
+ * VeryLongFunction notes.
+ *
+ * @param VeryLongParam0 is very long parameter 0 with some super important and
+ * extra very long description which makes a lot of sense.
+ *
+ * @param[in] VeryLongParam1 is very long parameter 1.
+ *
+ * @param[out] VeryLongParam2 is very long parameter 2.
+ *
+ * @param[in,out] VeryLongParam3 is very long parameter 3.
+ *
+ * @retval 1 is returned, in case A.
+ *
+ * @retval 2 is returned, in case B.
+ *
+ * @retval #Enum is returned, in case C.
+ *
+ * @return Sometimes some value. See Function().
+ */
+static inline int VeryLongFunction(
+ int VeryLongParam0,
+ const struct Struct *VeryLongParam1,
+ struct Struct *( *VeryLongParam2 )( void ),
+ struct Struct *VeryLongParam3
+)
+{
+ (void) VeryLongParam1;
+ (void) VeryLongParam2;
+ (void) VeryLongParam3;
+ return VeryLongParam0 + 1;
+}
+
#ifdef __cplusplus
}
#endif
More information about the vc
mailing list