Cache key of element changes between Python 3.12 and 3.13

[bbhtt]

Create an image with Python 3.13 to get cache key:

distrobox create --pull -i python:3.13 --name py313 && distrobox enter py313
sudo apt -y install python3-venv python3-pip lzip git bubblewrap
python3 -m venv .venv && source .venv/bin/activate
pip install dulwich==0.22.7 requests==2.32.3 buildstream==2.4.0
git clone git@gitlab.com:freedesktop-sdk/freedesktop-sdk.git && cd freedesktop-sdk
git checkout 9544ef08d442518af349be4188f808a271c08168

bst show -f "%{full-key}" --deps none components/glib.bst
f3bc575e05a5df618f57874c4c8b54b82519bf2cd3cffb0f41def6f0a1c08fa7

Now do the same with a Python 3.12 based image:

distrobox create --pull -i python:3.12 --name py312 && distrobox enter py312
sudo apt -y install python3-venv python3-pip lzip git bubblewrap
python3 -m venv .venv && source .venv/bin/activate
pip install dulwich==0.22.7 requests==2.32.3 buildstream==2.4.0
git clone git@gitlab.com:freedesktop-sdk/freedesktop-sdk.git && cd freedesktop-sdk
git checkout 9544ef08d442518af349be4188f808a271c08168

bst show -f "%{full-key}" --deps none components/glib.bst
ad991b447c32c8755bcf7f530299eefd810a2d04ab8d619e9345d98ff5989919

Primary investigation reveals that get_unique_key elements are changing order between Python versions for example the below (but there are others too):

Here is the cache_key_dict from _calculate_cache_key in element.py. Diffing between them shows a bunch of elements changed positions between the two python versions.

python3.13-cache_key_dict.txt
python3.12-cache_key_dict.txt

This seems to also cause public deps data to change:

On components/gobject-introspection-base.bst for example:

bst show -f "%{name}|%{key}|%{state}|%{config}|%{vars}|%{env}|%{public}|%{deps}|%{runtime-deps}" --deps none components/gobject-introspection-base.bst

Python 3.13

components/gobject-introspection-base.bst|94ee4616|waiting|configure-commands:
- "meson setup . _builddir --prefix=/usr \\\n--bindir=/usr/bin \\\n--sbindir=/usr/bin
  \\\n--sysconfdir=/etc \\\n--datadir=/usr/share \\\n--includedir=/usr/include \\\n
  --libdir=/usr/lib/x86_64-linux-gnu \\\n--libexecdir=/usr/libexec \\\n--localstatedir=/var
  \\\n--sharedstatedir=/usr/com \\\n--mandir=/usr/share/man \\\n--infodir=/usr/share/info
  --buildtype=plain -Dauto_features=enabled -Db_pie=true -Ddefault_library=shared
  -Db_lto=true -Db_lto_threads=${LTOJOBS} -Dcairo=disabled -Dgtk_doc=true -Ddoctool=enabled"
build-commands:
- ninja -v -j ${JOBS} -C _builddir
install-commands:
- env DESTDIR="/buildstream-install" meson install -C _builddir --no-rebuild
strip-commands:
- "OPTS=()\nif ! \"true\"; then\n  OPTS+=(\"-n\")\nfi\nif ! \"true\"; then\n  OPTS+=(\"\
  -p\")\nfi\nfor p in /usr /usr; do\n  OPTS+=(\"-t\" \"${p}\")\ndone\nfreedesktop-sdk-stripper
  \\\n    \"${OPTS[@]}\" \\\n    \"/buildstream-build\" \\\n    \"/usr/lib/debug/source/components/gobject-introspection-base.bst\"\
  \ \\\n    \"/usr/lib/debug/dwz/components/gobject-introspection-base.bst\" \\\n\
  \    \"/usr/lib/debug\" \\\n    \"/buildstream-install\""
|prefix: /usr
exec_prefix: /usr
bindir: /usr/bin
sbindir: /usr/bin
libexecdir: /usr/libexec
datadir: /usr/share
sysconfdir: /etc
sharedstatedir: /usr/com
localstatedir: /var
lib: lib/x86_64-linux-gnu
libdir: /usr/lib/x86_64-linux-gnu
debugdir: /usr/lib/debug
includedir: /usr/include
docdir: /usr/share/doc
infodir: /usr/share/info
mandir: /usr/share/man
build-root: /buildstream-build
conf-root: .
install-root: /buildstream-install
strip-binaries: "OPTS=()\nif ! \"true\"; then\n  OPTS+=(\"-n\")\nfi\nif ! \"true\"\
  ; then\n  OPTS+=(\"-p\")\nfi\nfor p in /usr /usr; do\n  OPTS+=(\"-t\" \"${p}\")\n
  done\nfreedesktop-sdk-stripper \\\n    \"${OPTS[@]}\" \\\n    \"/buildstream-build\"\
  \ \\\n    \"/usr/lib/debug/source/components/gobject-introspection-base.bst\" \\\
  \n    \"/usr/lib/debug/dwz/components/gobject-introspection-base.bst\" \\\n    \"\
  /usr/lib/debug\" \\\n    \"/buildstream-install\""
common_flags: -O2 -pipe
debug_flags: -g
target_flags_fortify_source: -Wp,-D_FORTIFY_SOURCE=3
target_flags_glibcxx_assertions: -Wp,-D_GLIBCXX_ASSERTIONS
target_flags_exceptions: -fexceptions
target_flags_stack_protector_strong: -fstack-protector-strong
target_flags_record_gcc_switches: -grecord-gcc-switches
target_common_flags: -g -Wp,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS -fexceptions
  -fstack-protector-strong -grecord-gcc-switches
local_flags:
target_x86_64_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection
  -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer
target_i686_flags: -mstackrealign -fasynchronous-unwind-tables -fstack-clash-protection
  -fcf-protection
target_aarch64_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fno-omit-frame-pointer
  -mno-omit-leaf-frame-pointer
target_arm_flags:
target_ppc64le_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fno-omit-frame-pointer
target_ppc64_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fno-omit-frame-pointer
target_riscv64_flags: -fasynchronous-unwind-tables -fstack-clash-protection
target_loongarch64_flags: -fasynchronous-unwind-tables -fstack-clash-protection
target_flags: '-O2 -pipe -g -Wp,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS -fexceptions
  -fstack-protector-strong -grecord-gcc-switches -fasynchronous-unwind-tables -fstack-clash-protection
  -fcf-protection -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer '
rust_local_flags:
rust_target_x86_64_flags: -Cforce-frame-pointers=yes
rust_target_i686_flags:
rust_target_aarch64_flags: -Cforce-frame-pointers=yes
rust_target_arm_flags:
rust_target_ppc64le_flags:
rust_target_ppc64_flags:
rust_target_riscv64_flags:
rust_target_loongarch64_flags:
rust_target_flags: '-Cforce-frame-pointers=yes '
common_ldflags: -Wl,-z,relro,-z,now -Wl,--as-needed
local_ldflags:
ldflags_defaults: '-Wl,-z,relro,-z,now -Wl,--as-needed '
indep-libdir: /usr/lib
sourcedir: /usr/lib/debug/source
flatpak_xmldir: /usr/share/app-info/xmls
gcc_triplet: x86_64-linux-gnu
triplet: x86_64-unknown-linux-gnu
gcc_arch: x86_64
flatpak_arch: x86_64
abi: gnu
optimize-debug: true
compress-debug: true
debugdatadir: /usr/lib/debug
stripdir-suffix: components/gobject-introspection-base.bst
toolchain-prefixes: /usr /usr
branch: 25.08beta
branch-extra: 25.08beta-extra
snap-branch: 2508
source-date-epoch: 1320937200
freedesktop-sdk-flatpak-branch: 25.08beta
freedesktop-sdk-flatpak-branch-extra: 25.08beta-extra
freedesktop-sdk-snap-branch: 2508
openh264-version: 2.5.0
host-triplet: x86_64-unknown-linux-gnu
build-triplet: x86_64-unknown-linux-gnu
libtool_dlsearch_path: /usr/lib/x86_64-linux-gnu
snap_arch: amd64
go-arch: amd64
target_arch_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection
  -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer
rust_target_arch_flags: -Cforce-frame-pointers=yes
arch: x86_64
linux-root: 4F68BCE3-E8CD-4DB1-96E7-FBCAF984B709
project-name: freedesktop-sdk
max-jobs: 8
bootstrap_build_arch: x86_64
target_arch: x86_64
snap_grade: devel
full_abi_diff: 0
build-dir: _builddir
meson-global: --buildtype=plain -Dauto_features=enabled -Db_pie=true -Ddefault_library=shared
  -Db_lto=true -Db_lto_threads=${LTOJOBS}
meson-local: -Dcairo=disabled -Dgtk_doc=true -Ddoctool=enabled
meson-args: "--prefix=/usr \\\n--bindir=/usr/bin \\\n--sbindir=/usr/bin \\\n--sysconfdir=/etc
  \\\n--datadir=/usr/share \\\n--includedir=/usr/include \\\n--libdir=/usr/lib/x86_64-linux-gnu
  \\\n--libexecdir=/usr/libexec \\\n--localstatedir=/var \\\n--sharedstatedir=/usr/com
  \\\n--mandir=/usr/share/man \\\n--infodir=/usr/share/info --buildtype=plain -Dauto_features=enabled
  -Db_pie=true -Ddefault_library=shared -Db_lto=true -Db_lto_threads=${LTOJOBS} -Dcairo=disabled
  -Dgtk_doc=true -Ddoctool=enabled"
meson: "meson setup . _builddir --prefix=/usr \\\n--bindir=/usr/bin \\\n--sbindir=/usr/bin
  \\\n--sysconfdir=/etc \\\n--datadir=/usr/share \\\n--includedir=/usr/include \\\n
  --libdir=/usr/lib/x86_64-linux-gnu \\\n--libexecdir=/usr/libexec \\\n--localstatedir=/var
  \\\n--sharedstatedir=/usr/com \\\n--mandir=/usr/share/man \\\n--infodir=/usr/share/info
  --buildtype=plain -Dauto_features=enabled -Db_pie=true -Ddefault_library=shared
  -Db_lto=true -Db_lto_threads=${LTOJOBS} -Dcairo=disabled -Dgtk_doc=true -Ddoctool=enabled"
meson-build: ninja -v -j ${JOBS} -C _builddir
meson-install: env DESTDIR="/buildstream-install" meson install -C _builddir --no-rebuild
meson-lto-flags: -Db_lto=true -Db_lto_threads=${LTOJOBS}
element-name: components/gobject-introspection-base.bst
|PATH: /usr/bin:/bin:/usr/sbin:/sbin
SHELL: /bin/sh
TERM: dumb
USER: tomjon
USERNAME: tomjon
LOGNAME: tomjon
LC_ALL: en_US.UTF-8
HOME: /tmp
TZ: UTC
SOURCE_DATE_EPOCH: 1320937200
CFLAGS: '-O2 -pipe -g -Wp,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS -fexceptions
  -fstack-protector-strong -grecord-gcc-switches -fasynchronous-unwind-tables -fstack-clash-protection
  -fcf-protection -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer '
CXXFLAGS: '-O2 -pipe -g -Wp,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS -fexceptions
  -fstack-protector-strong -grecord-gcc-switches -fasynchronous-unwind-tables -fstack-clash-protection
  -fcf-protection -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer '
LDFLAGS: '-Wl,-z,relro,-z,now -Wl,--as-needed '
RUSTFLAGS: '-Cforce-frame-pointers=yes '
G_SLICE: always-malloc
OMP_NUM_THREADS: 4
GOMAXPROCS: 8
PYTHON: /usr/bin/python3
PYTHONHASHSEED: 0
GZIP: --no-name
JOBS: 8
LTOJOBS: 8
|bst:
  split-rules:
    runtime:
    - /usr/bin
    - /usr/bin/*
    - /usr/bin
    - /usr/bin/*
    - /usr/libexec
    - /usr/libexec/*
    - /usr/lib/x86_64-linux-gnu/lib*.so*
    devel:
    - /usr/include
    - /usr/include/**
    - /usr/lib/x86_64-linux-gnu/pkgconfig
    - /usr/lib/x86_64-linux-gnu/pkgconfig/**
    - /usr/share/pkgconfig
    - /usr/share/pkgconfig/**
    - /usr/share/aclocal
    - /usr/share/aclocal/**
    - /usr/share/cmake/**
    - /usr/lib/cmake
    - /usr/lib/cmake/**
    - /usr/lib/x86_64-linux-gnu/cmake
    - /usr/lib/x86_64-linux-gnu/cmake/**
    - /usr/lib/*.a
    - /usr/lib/x86_64-linux-gnu/*.a
    - /usr/share/gir-1.0
    - /usr/share/gir-1.0/**
    - /usr/share/vala*/vapi
    - /usr/share/vala*/vapi/**
    - /usr/src/**
    - /usr/lib/x86_64-linux-gnu/gobject-introspection/giscanner
    - /usr/lib/x86_64-linux-gnu/gobject-introspection/giscanner/**
    - /usr/share/gir-1.0
    - /usr/share/gir-1.0/**
    - /usr/share/gobject-introspection-1.0
    - /usr/share/gobject-introspection-1.0/**
    - /usr/bin/g-ir-*
    - /usr/lib/x86_64-linux-gnu/libgirepository-1.0.so
    debug:
    - /usr/lib/debug/**
    doc:
    - /usr/share/doc
    - /usr/share/doc/**
    - /usr/share/info
    - /usr/share/info/**
    - /usr/share/man
    - /usr/share/man/**
    - /usr/share/gtk-doc/html
    - /usr/share/gtk-doc/html/**
    - /usr/share/examples
    - /usr/share/examples/**
    - /usr/share/help
    - /usr/share/help/**
    - /usr/share/ri
    - /usr/share/ri/**
    - /usr/share/cmake-*/Help
    - /usr/share/cmake-*/Help/**
    locale:
    - /usr/share/locale
    - /usr/share/locale/**
    - /usr/share/i18n
    - /usr/share/i18n/**
    - /usr/share/zoneinfo
    - /usr/share/zoneinfo/**
    static-blocklist: []
cpe:
  product: gobject-introspection
|- components/flex.bst
- public-stacks/runtime-minimal.bst
- components/python3.bst
- components/python3-setuptools.bst
- components/bison.bst
- components/python3-markdown.bst
- public-stacks/buildsystem-meson.bst
- components/glib-stage1.bst
- components/gtk-doc.bst
- components/python3-mako.bst|- public-stacks/runtime-minimal.bst
- components/python3.bst
- components/python3-setuptools.bst
- components/python3-markdown.bst
- components/python3-mako.bst

Python 3.12

components/gobject-introspection-base.bst|5723a673|waiting|configure-commands:
- "meson setup . _builddir --prefix=/usr \\\n--bindir=/usr/bin \\\n--sbindir=/usr/bin
  \\\n--sysconfdir=/etc \\\n--datadir=/usr/share \\\n--includedir=/usr/include \\\n
  --libdir=/usr/lib/x86_64-linux-gnu \\\n--libexecdir=/usr/libexec \\\n--localstatedir=/var
  \\\n--sharedstatedir=/usr/com \\\n--mandir=/usr/share/man \\\n--infodir=/usr/share/info
  --buildtype=plain -Dauto_features=enabled -Db_pie=true -Ddefault_library=shared
  -Db_lto=true -Db_lto_threads=${LTOJOBS} -Dcairo=disabled -Dgtk_doc=true -Ddoctool=enabled"
build-commands:
- ninja -v -j ${JOBS} -C _builddir
install-commands:
- env DESTDIR="/buildstream-install" meson install -C _builddir --no-rebuild
strip-commands:
- "OPTS=()\nif ! \"true\"; then\n  OPTS+=(\"-n\")\nfi\nif ! \"true\"; then\n  OPTS+=(\"\
  -p\")\nfi\nfor p in /usr /usr; do\n  OPTS+=(\"-t\" \"${p}\")\ndone\nfreedesktop-sdk-stripper
  \\\n    \"${OPTS[@]}\" \\\n    \"/buildstream-build\" \\\n    \"/usr/lib/debug/source/components/gobject-introspection-base.bst\"\
  \ \\\n    \"/usr/lib/debug/dwz/components/gobject-introspection-base.bst\" \\\n\
  \    \"/usr/lib/debug\" \\\n    \"/buildstream-install\""
|prefix: /usr
exec_prefix: /usr
bindir: /usr/bin
sbindir: /usr/bin
libexecdir: /usr/libexec
datadir: /usr/share
sysconfdir: /etc
sharedstatedir: /usr/com
localstatedir: /var
lib: lib/x86_64-linux-gnu
libdir: /usr/lib/x86_64-linux-gnu
debugdir: /usr/lib/debug
includedir: /usr/include
docdir: /usr/share/doc
infodir: /usr/share/info
mandir: /usr/share/man
build-root: /buildstream-build
conf-root: .
install-root: /buildstream-install
strip-binaries: "OPTS=()\nif ! \"true\"; then\n  OPTS+=(\"-n\")\nfi\nif ! \"true\"\
  ; then\n  OPTS+=(\"-p\")\nfi\nfor p in /usr /usr; do\n  OPTS+=(\"-t\" \"${p}\")\n
  done\nfreedesktop-sdk-stripper \\\n    \"${OPTS[@]}\" \\\n    \"/buildstream-build\"\
  \ \\\n    \"/usr/lib/debug/source/components/gobject-introspection-base.bst\" \\\
  \n    \"/usr/lib/debug/dwz/components/gobject-introspection-base.bst\" \\\n    \"\
  /usr/lib/debug\" \\\n    \"/buildstream-install\""
common_flags: -O2 -pipe
debug_flags: -g
target_flags_fortify_source: -Wp,-D_FORTIFY_SOURCE=3
target_flags_glibcxx_assertions: -Wp,-D_GLIBCXX_ASSERTIONS
target_flags_exceptions: -fexceptions
target_flags_stack_protector_strong: -fstack-protector-strong
target_flags_record_gcc_switches: -grecord-gcc-switches
target_common_flags: -g -Wp,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS -fexceptions
  -fstack-protector-strong -grecord-gcc-switches
local_flags:
target_x86_64_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection
  -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer
target_i686_flags: -mstackrealign -fasynchronous-unwind-tables -fstack-clash-protection
  -fcf-protection
target_aarch64_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fno-omit-frame-pointer
  -mno-omit-leaf-frame-pointer
target_arm_flags:
target_ppc64le_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fno-omit-frame-pointer
target_ppc64_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fno-omit-frame-pointer
target_riscv64_flags: -fasynchronous-unwind-tables -fstack-clash-protection
target_loongarch64_flags: -fasynchronous-unwind-tables -fstack-clash-protection
target_flags: '-O2 -pipe -g -Wp,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS -fexceptions
  -fstack-protector-strong -grecord-gcc-switches -fasynchronous-unwind-tables -fstack-clash-protection
  -fcf-protection -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer '
rust_local_flags:
rust_target_x86_64_flags: -Cforce-frame-pointers=yes
rust_target_i686_flags:
rust_target_aarch64_flags: -Cforce-frame-pointers=yes
rust_target_arm_flags:
rust_target_ppc64le_flags:
rust_target_ppc64_flags:
rust_target_riscv64_flags:
rust_target_loongarch64_flags:
rust_target_flags: '-Cforce-frame-pointers=yes '
common_ldflags: -Wl,-z,relro,-z,now -Wl,--as-needed
local_ldflags:
ldflags_defaults: '-Wl,-z,relro,-z,now -Wl,--as-needed '
indep-libdir: /usr/lib
sourcedir: /usr/lib/debug/source
flatpak_xmldir: /usr/share/app-info/xmls
gcc_triplet: x86_64-linux-gnu
triplet: x86_64-unknown-linux-gnu
gcc_arch: x86_64
flatpak_arch: x86_64
abi: gnu
optimize-debug: true
compress-debug: true
debugdatadir: /usr/lib/debug
stripdir-suffix: components/gobject-introspection-base.bst
toolchain-prefixes: /usr /usr
branch: 25.08beta
branch-extra: 25.08beta-extra
snap-branch: 2508
source-date-epoch: 1320937200
freedesktop-sdk-flatpak-branch: 25.08beta
freedesktop-sdk-flatpak-branch-extra: 25.08beta-extra
freedesktop-sdk-snap-branch: 2508
openh264-version: 2.5.0
host-triplet: x86_64-unknown-linux-gnu
build-triplet: x86_64-unknown-linux-gnu
libtool_dlsearch_path: /usr/lib/x86_64-linux-gnu
snap_arch: amd64
go-arch: amd64
target_arch_flags: -fasynchronous-unwind-tables -fstack-clash-protection -fcf-protection
  -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer
rust_target_arch_flags: -Cforce-frame-pointers=yes
arch: x86_64
linux-root: 4F68BCE3-E8CD-4DB1-96E7-FBCAF984B709
project-name: freedesktop-sdk
max-jobs: 8
bootstrap_build_arch: x86_64
target_arch: x86_64
snap_grade: devel
full_abi_diff: 0
build-dir: _builddir
meson-global: --buildtype=plain -Dauto_features=enabled -Db_pie=true -Ddefault_library=shared
  -Db_lto=true -Db_lto_threads=${LTOJOBS}
meson-local: -Dcairo=disabled -Dgtk_doc=true -Ddoctool=enabled
meson-args: "--prefix=/usr \\\n--bindir=/usr/bin \\\n--sbindir=/usr/bin \\\n--sysconfdir=/etc
  \\\n--datadir=/usr/share \\\n--includedir=/usr/include \\\n--libdir=/usr/lib/x86_64-linux-gnu
  \\\n--libexecdir=/usr/libexec \\\n--localstatedir=/var \\\n--sharedstatedir=/usr/com
  \\\n--mandir=/usr/share/man \\\n--infodir=/usr/share/info --buildtype=plain -Dauto_features=enabled
  -Db_pie=true -Ddefault_library=shared -Db_lto=true -Db_lto_threads=${LTOJOBS} -Dcairo=disabled
  -Dgtk_doc=true -Ddoctool=enabled"
meson: "meson setup . _builddir --prefix=/usr \\\n--bindir=/usr/bin \\\n--sbindir=/usr/bin
  \\\n--sysconfdir=/etc \\\n--datadir=/usr/share \\\n--includedir=/usr/include \\\n
  --libdir=/usr/lib/x86_64-linux-gnu \\\n--libexecdir=/usr/libexec \\\n--localstatedir=/var
  \\\n--sharedstatedir=/usr/com \\\n--mandir=/usr/share/man \\\n--infodir=/usr/share/info
  --buildtype=plain -Dauto_features=enabled -Db_pie=true -Ddefault_library=shared
  -Db_lto=true -Db_lto_threads=${LTOJOBS} -Dcairo=disabled -Dgtk_doc=true -Ddoctool=enabled"
meson-build: ninja -v -j ${JOBS} -C _builddir
meson-install: env DESTDIR="/buildstream-install" meson install -C _builddir --no-rebuild
meson-lto-flags: -Db_lto=true -Db_lto_threads=${LTOJOBS}
element-name: components/gobject-introspection-base.bst
|PATH: /usr/bin:/bin:/usr/sbin:/sbin
SHELL: /bin/sh
TERM: dumb
USER: tomjon
USERNAME: tomjon
LOGNAME: tomjon
LC_ALL: en_US.UTF-8
HOME: /tmp
TZ: UTC
SOURCE_DATE_EPOCH: 1320937200
CFLAGS: '-O2 -pipe -g -Wp,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS -fexceptions
  -fstack-protector-strong -grecord-gcc-switches -fasynchronous-unwind-tables -fstack-clash-protection
  -fcf-protection -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer '
CXXFLAGS: '-O2 -pipe -g -Wp,-D_FORTIFY_SOURCE=3 -Wp,-D_GLIBCXX_ASSERTIONS -fexceptions
  -fstack-protector-strong -grecord-gcc-switches -fasynchronous-unwind-tables -fstack-clash-protection
  -fcf-protection -fno-omit-frame-pointer -mno-omit-leaf-frame-pointer '
LDFLAGS: '-Wl,-z,relro,-z,now -Wl,--as-needed '
RUSTFLAGS: '-Cforce-frame-pointers=yes '
G_SLICE: always-malloc
OMP_NUM_THREADS: 4
GOMAXPROCS: 8
PYTHON: /usr/bin/python3
PYTHONHASHSEED: 0
GZIP: --no-name
JOBS: 8
LTOJOBS: 8
|bst:
  split-rules:
    runtime:
    - /usr/bin
    - /usr/bin/*
    - /usr/bin
    - /usr/bin/*
    - /usr/libexec
    - /usr/libexec/*
    - /usr/lib/x86_64-linux-gnu/lib*.so*
    devel:
    - /usr/include
    - /usr/include/**
    - /usr/lib/x86_64-linux-gnu/pkgconfig
    - /usr/lib/x86_64-linux-gnu/pkgconfig/**
    - /usr/share/pkgconfig
    - /usr/share/pkgconfig/**
    - /usr/share/aclocal
    - /usr/share/aclocal/**
    - /usr/share/cmake/**
    - /usr/lib/cmake
    - /usr/lib/cmake/**
    - /usr/lib/x86_64-linux-gnu/cmake
    - /usr/lib/x86_64-linux-gnu/cmake/**
    - /usr/lib/*.a
    - /usr/lib/x86_64-linux-gnu/*.a
    - /usr/share/gir-1.0
    - /usr/share/gir-1.0/**
    - /usr/share/vala*/vapi
    - /usr/share/vala*/vapi/**
    - /usr/src/**
    - /usr/lib/x86_64-linux-gnu/gobject-introspection/giscanner
    - /usr/lib/x86_64-linux-gnu/gobject-introspection/giscanner/**
    - /usr/share/gir-1.0
    - /usr/share/gir-1.0/**
    - /usr/share/gobject-introspection-1.0
    - /usr/share/gobject-introspection-1.0/**
    - /usr/bin/g-ir-*
    - /usr/lib/x86_64-linux-gnu/libgirepository-1.0.so
    debug:
    - /usr/lib/debug/**
    doc:
    - /usr/share/doc
    - /usr/share/doc/**
    - /usr/share/info
    - /usr/share/info/**
    - /usr/share/man
    - /usr/share/man/**
    - /usr/share/gtk-doc/html
    - /usr/share/gtk-doc/html/**
    - /usr/share/examples
    - /usr/share/examples/**
    - /usr/share/help
    - /usr/share/help/**
    - /usr/share/ri
    - /usr/share/ri/**
    - /usr/share/cmake-*/Help
    - /usr/share/cmake-*/Help/**
    locale:
    - /usr/share/locale
    - /usr/share/locale/**
    - /usr/share/i18n
    - /usr/share/i18n/**
    - /usr/share/zoneinfo
    - /usr/share/zoneinfo/**
    static-blocklist: []
cpe:
  product: gobject-introspection
|- components/flex.bst
- public-stacks/runtime-minimal.bst
- components/python3.bst
- components/python3-setuptools.bst
- components/bison.bst
- components/gtk-doc.bst
- components/python3-mako.bst
- components/python3-markdown.bst
- public-stacks/buildsystem-meson.bst
- components/glib-stage1.bst|- public-stacks/runtime-minimal.bst
- components/python3.bst
- components/python3-setuptools.bst
- components/python3-mako.bst
- components/python3-markdown.bst

The diff shows similar changes in deps order:

[nanonyme]

Is it just me or does the order of deps in both cases look arbitrary? This is what the actual elements defines:

build-depends:
- public-stacks/buildsystem-meson.bst
- components/bison.bst
- components/flex.bst
- components/glib-stage1.bst
- components/gtk-doc.bst

depends:
- public-stacks/runtime-minimal.bst
- components/python3.bst
- components/python3-mako.bst
- components/python3-markdown.bst
- components/python3-setuptools.bst

Neither of the two orders follow the order in which dependencies are declared in YAML or alphabetical order.
3.13 is

- components/flex.bst
- public-stacks/runtime-minimal.bst
- components/python3.bst
- components/python3-setuptools.bst
- components/bison.bst
- components/python3-markdown.bst
- public-stacks/buildsystem-meson.bst
- components/glib-stage1.bst
- components/gtk-doc.bst
- components/python3-mako.bst

while 3.12 is

- components/flex.bst
- public-stacks/runtime-minimal.bst
- components/python3.bst
- components/python3-setuptools.bst
- components/bison.bst
- components/gtk-doc.bst
- components/python3-mako.bst
- components/python3-markdown.bst
- public-stacks/buildsystem-meson.bst
- components/glib-stage1.bst

[abderrahim]

Neither of the two orders follow the order in which dependencies are declared in YAML or alphabetical order.

Yes, the order doesn't follow the order of declaration in YAML. It's supposed to have a deterministic order so that reordering the deps in the YAML doesn't affect the cache key. Alphabetical ordering could have been a useful order, but apparently something else was used.

[nanonyme]

Okay, so where does this order actually come from? It sounds knowing this might help for understanding the bug.

[Kekun]

The order comes from the _dependency_cmp() function, but it seems not everything is compared against everything, e.g. I see bison compared against gtk-doc in 3.12 but not against python3-markdown, and vice versa in 3.13, which leads to them being flipped in the dependencies list of gobject-introspection-base, which in turn leads to calculating a different cache key. So it seems we somehow have a partial order (which is hence sensitive to changes in the sorting algorithm) instead of total order, but I don't know why yet. That or we have a total order and that's a regression in Cython, but us having a imperfect comparison function sounds more likely to me somehow.

[Edit]

I just noticed gtk-doc is compared to python3-markdown in 3.12 but not in 3.13, too. I don't know how the two or compared in 3.13 as it's clearly indirect, but clearly their order is flipped in some places.

[Edit]

Also in components where the dependencies order changes between Python versions, the order before sorting in the same in both versions, it's only different after sorting them, so that's clearly where the problem lies: in the call to element.dependencies.sort(key=cmp_to_key(_dependency_cmp)).

[nanonyme]

The documentation is funny on cmp_to_key https://docs.python.org/3/library/functools.html "This function is primarily used as a transition tool for programs being converted from Python 2 which supported the use of comparison functions."

[Kekun]

Yeah maybe that's where the issue comes from, also "The sort() method is guaranteed to be stable. A sort is stable if it guarantees not to change the relative order of elements that compare equal — this is helpful for sorting in multiple passes (for example, sort by department, then by salary grade)."

[nanonyme]

cmp_to_key itself has not changed for last 14 years. It looks like it creates a wrapper class around the function that implements total ordering https://github.com/python/cpython/blob/v3.13.0/Lib/functools.py#L209
Edit: I just noticed there is a C implementation of cmp_to_key which is used if present. No changes to the C function either with exception to this python/cpython@17a8af9

[nanonyme]

AI claims to me that Python sort only uses __lt__ when present. I don't know if it can be relied upon.

[bbhtt]

I bisected this when I opened the issue, but looks like I forgot to post the result. Last good version is v3.13.0a5, first bad version is v3.13.0a6. didn't get the chance to check the relevance with bst yet.

bf121d6a694bea4fe9864a19879fe0c70c4e0656 is the first bad commit
commit bf121d6a694bea4fe9864a19879fe0c70c4e0656
Author: Tim Peters <tim.peters@gmail.com>
Date:   Tue Mar 12 19:59:42 2024 -0500

    GH-116554: Relax list.sort()'s notion of "descending" runs (#116578)
    
    * GH-116554: Relax list.sort()'s notion of "descending" run
    
    Rewrote `count_run()` so that sub-runs of equal elements no longer end a descending run. Both ascending and descending runs can have arbitrarily many sub-runs of arbitrarily many equal elements now. This is tricky, because we only use ``<`` comparisons, so checking for equality doesn't come "for free". Surprisingly, it turned out there's a very cheap (one comparison) way to determine whether an ascending run consisted of all-equal elements. That sealed the deal.
    
    In addition, after a descending run is reversed in-place, we now go on to see whether it can be extended by an ascending run that just happens to be adjacent. This succeeds in finding at least one additional element to append about half the time, and so appears to more than repay its cost (the savings come from getting to skip a binary search, when a short run is artificially forced to length MIINRUN later, for each new element `count_run()` can add to the initial run).
    
    While these have been in the back of my mind for years, a question on StackOverflow pushed it to action:
    
    https://stackoverflow.com/questions/78108792/
    
    They were wondering why it took about 4x longer to sort a list like:
    
    [999_999, 999_999, ..., 2, 2, 1, 1, 0, 0]
    
    than "similar" lists. Of course that runs very much faster after this patch.
    
    Co-authored-by: Alex Waygood <Alex.Waygood@Gmail.com>
    Co-authored-by: Pieter Eendebak <pieter.eendebak@gmail.com>

 Lib/test/test_sort.py                              |  21 +++
 .../2024-03-11-00-45-39.gh-issue-116554.gYumG5.rst |   1 +
 Objects/listobject.c                               | 157 ++++++++++++++-------
 Objects/listsort.txt                               |  43 ++++--
 4 files changed, 156 insertions(+), 66 deletions(-)
 create mode 100644 Misc/NEWS.d/next/Core and Builtins/2024-03-11-00-45-39.gh-issue-116554.gYumG5.rst

[nanonyme]

Well, that is quite fundamental. Python sort function does no longer seem to be Timsort after that change with regards to what descending run means.

[nanonyme]

I quickly read how the cmp works and I think we should build the deptrees manually. The strongest mechanism in cmp is dependencies and with fallback to alphabetical comparison. Junctions are not applicable in this. It should be possible to manually create expected linearization from deptree. I suspect the 3.13 linearization is now incorrect.

[Kekun]

I tried custom bubble sort and quicksort functions, here is what I have for the deps of gobject-introspection-base.bst. The custom quicksort gives me the same result as list.sort() in 3.12, though it's somehow not the same as the custom quicksort.

list.sort() 3.12

['components/flex.bst',
 'public-stacks/runtime-minimal.bst',
 'components/python3.bst',
 'components/python3-setuptools.bst',
 'components/bison.bst',
 'components/gtk-doc.bst',
 'components/python3-mako.bst',
 'components/python3-markdown.bst',
 'public-stacks/buildsystem-meson.bst',
 'components/glib-stage1.bst']

list.sort() 3.13

['components/flex.bst',
 'public-stacks/runtime-minimal.bst',
 'components/python3.bst',
 'components/python3-setuptools.bst',
 'components/bison.bst',
 'components/python3-markdown.bst',
 'public-stacks/buildsystem-meson.bst',
 'components/glib-stage1.bst',
 'components/gtk-doc.bst',
 'components/python3-mako.bst']

Bubble Sort

['components/flex.bst',
 'public-stacks/runtime-minimal.bst',
 'components/python3.bst',
 'components/python3-setuptools.bst',
 'components/bison.bst',
 'public-stacks/buildsystem-meson.bst',
 'components/glib-stage1.bst',
 'components/gtk-doc.bst',
 'components/python3-mako.bst',
 'components/python3-markdown.bst']

Quicksort

['components/flex.bst',
 'public-stacks/runtime-minimal.bst',
 'components/python3.bst',
 'components/python3-setuptools.bst',
 'components/bison.bst',
 'components/gtk-doc.bst',
 'components/python3-mako.bst',
 'components/python3-markdown.bst',
 'public-stacks/buildsystem-meson.bst',
 'components/glib-stage1.bst']

[nanonyme]

That is not exactly the same as what BuildStream does though. You were invoking a simple single-key sort whereas BuildStream cmp has two conditions and is not same as simple string-based sort.

[Kekun]

I'm using BuildStream's comparison function in the sorts. I believe the problem is that the comparison function doesn't result in a total order and I think I'm starting to guess why, I'm testing things.

There are things like this which in case of a dependency loop would give different results based on the used sort function:

    if element_a.depends(element_b):
        return 1
    elif element_b.depends(element_a):
        return -1

So comparing a and b or b and a could give a different order.

If I am right, a fix would be this:

    if element_a.depends(element_b) != element_b.depends(element_a):
        if element_a.depends(element_b):
            return 1
        else:
            return -1

But I'm still unsure, I'm testing this.