]> www.infradead.org Git - users/dwmw2/qemu.git/commit
scripts/decodetree: Implement a topological sort
authorPeter Maydell <peter.maydell@linaro.org>
Tue, 23 May 2023 12:04:45 +0000 (13:04 +0100)
committerRichard Henderson <richard.henderson@linaro.org>
Tue, 30 May 2023 17:55:39 +0000 (10:55 -0700)
commit36d612448273d0c295f519d9df3b10208177487a
treec67807836df5edef8ff91667746ee2c16b6b302c
parentaeac22ba1e91a40d1d831cb02a1935391e67c7e2
scripts/decodetree: Implement a topological sort

To support named fields, we will need to be able to do a topological
sort (so that we ensure that we output the assignment to field A
before the assignment to field B if field B refers to field A by
name). The good news is that there is a tsort in the python standard
library; the bad news is that it was only added in Python 3.9.

To bridge the gap between our current minimum supported Python
version and 3.9, provide a local implementation that has the
same API as the stdlib version for the parts we care about.
In future when QEMU's minimum Python version requirement reaches
3.9 we can delete this code and replace it with an 'import' line.

The core of this implementation is based on
https://code.activestate.com/recipes/578272-topological-sort/
which is MIT-licensed.

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
Acked-by: Richard Henderson <richard.henderson@linaro.org>
Message-Id: <20230523120447.728365-5-peter.maydell@linaro.org>
scripts/decodetree.py