graphs: implementation of linear-time algorithm for modular decomposition #16667

Workflow file for this run

	name: Build & Test

	on:
	pull_request:
	merge_group:
	push:
	branches:
	- master
	- develop
	# Ignore pushes on tags to prevent two uploads of codecov reports
	tags-ignore: ['**']
	workflow_dispatch:
	# Allow to run manually
	inputs:
	platform:
	description: 'Platform'
	required: true
	default: 'ubuntu-jammy-standard'
	docker_tag:
	description: 'Docker tag'
	required: true
	default: 'dev'

	concurrency:
	# Cancel previous runs of this workflow for the same branch
	group: ${{ github.workflow }}-${{ github.ref }}
	cancel-in-progress: true

	#
	# The three workflows:
	#
	# - build.yml (with jobs test-new, test-mod, test-long),
	# - doc-build.yml,
	# - doc-build-pdf.yml
	#
	# each build Sage:
	#
	# - incrementally starting from a Docker image that ci-linux.yml
	# publishes on each development release to ghcr.io,
	# - orchestrated using a tox-generated Dockerfile,
	# - using https://github.com/marketplace/actions/build-and-push-docker-images,
	# - pushing the image to a local registry,
	# - then executing a container loaded from that registry,
	#
	# and then run various tests or build the documentation.
	#
	# Without the use of a cache, this runs the same incremental rebuild of Sage
	# multiple times; there is no interaction between these workflow and jobs.
	#
	# This baseline is transparently improved by our use of the GH Actions cache,
	# see https://docs.docker.com/build/ci/github-actions/cache/#cache-backend-api.
	#
	# Jobs test-mod and test-long are only started after test-new completed;
	# but the workflows doc-build.yml and doc-build-pdf.yml are started independently.
	#
	# - When nothing is cached and the 3 workflows are launched in parallel,
	# they may each run the same incremental rebuild.
	#
	# - When there's congestion that leads to the workflows to be run serially,
	# the 2nd and 3rd workflow will be able to use the cache from the 1st workflow.
	#
	# This elasticity may be helpful in reducing congestion.
	#
	# There is a rather small per-project limit of 10 GB for this cache.
	# Use https://github.com/sagemath/sage/actions/caches to monitor the utilization
	# of the cache.
	#

	env:
	# Adapted from docker.yml
	TOX_ENV: "docker-${{ github.event.inputs.platform \|\| 'ubuntu-jammy-standard' }}-incremental"
	BUILD_IMAGE: "localhost:5000/${{ github.repository }}/sage-${{ github.event.inputs.platform \|\| 'ubuntu-jammy-standard' }}-with-targets:ci"
	FROM_DOCKER_REPOSITORY: "ghcr.io/sagemath/sage/"
	FROM_DOCKER_TARGET: "with-targets"
	FROM_DOCKER_TAG: ${{ github.event.inputs.docker_tag \|\| 'dev'}}
	EXTRA_CONFIGURE_ARGS: --enable-fat-binary

	jobs:
	test-new:
	runs-on: ubuntu-latest
	outputs:
	build_targets: ${{ steps.build-targets.outputs.build_targets }}
	services:
	# https://docs.docker.com/build/ci/github-actions/local-registry/
	registry:
	image: registry:2
	ports:
	- 5000:5000
	steps:
	- name: Maximize build disk space
	uses: easimon/maximize-build-space@v10
	with:
	# need space in /var for Docker images
	root-reserve-mb: 30000
	remove-dotnet: true
	remove-android: true
	remove-haskell: true
	remove-codeql: true
	remove-docker-images: true

	- name: Checkout
	id: checkout
	uses: actions/checkout@v4

	- name: Get changed files and packages
	id: changed-files
	uses: tj-actions/changed-files@v45
	with:
	# File extensions for doctests per sage.doctest.control.skipfile
	files_yaml: \|
	configures:
	- 'build/pkgs/*/spkg-configure.m4'
	pkgs:
	- 'build/pkgs/**'
	- '!build/pkgs/_**'
	- '!build/pkgs/configure/**'
	- 'pkgs/**'
	doctests:
	- 'src/*/.{py,pyx,pxd,pxi,sage,spyx,rst,tex}'
	- '!src/{setup,conftest*}.py'

	- name: Determine targets to build
	id: build-targets
	run: \|
	uninstall_targets=$(echo $(
	for a in '' ${{ steps.changed-files.outputs.configures_all_changed_files }}; do
	# Extract package name from the file path and append '-uninstall'
	echo $a \| sed -E 's,build/pkgs/([a-z0-9][_.a-z0-9])/spkg-configure[.]m4 ,\1-uninstall,'
	done \| sort -u # Sort and ensure uniqueness
	))
	build_targets=$(echo $(
	for a in '' ${{ steps.changed-files.outputs.pkgs_all_changed_files }}; do
	# Extract package name, replace '-' with '_', and strip extra parts from the path
	SPKG=$(echo $a \| sed -E 's,-,_,g;s,(build/)?pkgs/([a-z0-9][-_.a-z0-9])/[^ ] *,\2,;')
	# Check if key files exist in the package directory
	if [ -f "build/pkgs/$SPKG/checksums.ini" ] \|\| \
	[ -f "build/pkgs/$SPKG/requirements.txt" ] \|\| \
	[ -f "build/pkgs/$SPKG/spkg-install" ]; then
	echo "$SPKG-ensure" # add the "$SPKG-ensure" target
	fi
	done \| sort -u # Sort and ensure uniqueness
	))
	if [ -n "$uninstall_targets" ]; then
	echo "build_targets=$uninstall_targets reconfigure $build_targets ci-build-with-fallback" >> $GITHUB_OUTPUT
	else
	echo "build_targets=$build_targets ci-build-with-fallback" >> $GITHUB_OUTPUT
	fi
	cat $GITHUB_OUTPUT

	- uses: actions/checkout@v4
	with:
	ref: ${{ github.base_ref }}
	path: worktree-base
	if: github.base_ref && steps.changed-files.outputs.pkgs_all_changed_files

	- name: Compute metrics
	run: \|
	export PATH=build/bin:$PATH
	if [ -d worktree-base ]; then
	(echo "# $GITHUB_BASE_REF"; SAGE_ROOT=worktree-base sage-package metrics :all:) > base-metrics.txt
	(echo "# $GITHUB_REF"; sage-package metrics :all:) > metrics.txt
	diff --color=always --width=100 --side-by-side --left-column base-metrics.txt metrics.txt \|\| true
	else
	sage-package metrics :all:
	fi

	- name: Install test prerequisites
	# From docker.yml
	run: \|
	sudo DEBIAN_FRONTEND=noninteractive apt-get update
	sudo DEBIAN_FRONTEND=noninteractive apt-get install tox
	sudo apt-get clean
	df -h

	- name: Merge CI fixes from sagemath/sage
	# From docker.yml
	# This step needs to happen after the commit sha is put in DOCKER_TAG
	# so that multi-stage builds can work correctly.
	run: \|
	mkdir -p upstream
	.ci/merge-fixes.sh 2>&1 \| tee upstream/ci_fixes.log
	env:
	GH_TOKEN: ${{ github.token }}
	SAGE_CI_FIXES_FROM_REPOSITORIES: ${{ vars.SAGE_CI_FIXES_FROM_REPOSITORIES }}

	# Building

	- name: Generate Dockerfile
	# From docker.yml
	run: \|
	tox -e ${{ env.TOX_ENV }}
	cp .tox/${{ env.TOX_ENV }}/Dockerfile .
	env:
	# Only generate the Dockerfile, do not run 'docker build' here
	DOCKER_TARGETS: ""

	- name: Set up Docker Buildx
	uses: docker/setup-buildx-action@v3
	with:
	driver-opts: network=host

	- name: Build Docker image
	id: image
	uses: docker/build-push-action@v6
	with:
	# push and load may not be set together at the moment
	#
	# We are using "push" (to the local registry) because it was
	# more reliable than "load", for which we observed random failure
	# conditions in which the built image could not be found.
	#
	push: ${{ steps.changed-files.outputs.doctests_all_changed_files && true \|\| false }}
	load: false
	context: .
	tags: ${{ env.BUILD_IMAGE }}
	target: with-targets
	cache-from: type=gha
	cache-to: type=gha,mode=max
	build-args: \|
	NUMPROC=6
	USE_MAKEFLAGS=-k V=0 SAGE_NUM_THREADS=4 --output-sync=recurse
	TARGETS_PRE=build/make/Makefile
	TARGETS=${{ steps.build-targets.outputs.build_targets }}

	- name: Start container
	id: container
	# Try to continue when "exporting to GitHub Actions Cache" failed with timeout
	if: (success() \|\| failure()) && steps.changed-files.outputs.doctests_all_changed_files
	run: \|
	docker run --name BUILD -dit \
	--mount type=bind,src=$(pwd),dst=$(pwd) \
	--workdir $(pwd) \
	${{ env.BUILD_IMAGE }} /bin/sh

	# Testing

	- name: Check that all modules can be imported
	if: (success() \|\| failure()) && steps.container.outcome == 'success' && steps.changed-files.outputs.doctests_all_changed_files
	run: \|
	# Increase the length of the lines in the "short summary"
	export COLUMNS=120
	# The following command checks that all modules can be imported.
	# The output also includes a long list of modules together with the number of tests in each module.
	# This can be ignored.
	./sage -python -m pip install pytest-xdist
	./sage -python -m pytest -c tox.ini -qq --doctest --collect-only \|\| true
	shell: sh .ci/docker-exec-script.sh BUILD /sage {0}

	- name: Test changed files (sage -t --new)
	if: (success() \|\| failure()) && steps.container.outcome == 'success' && steps.changed-files.outputs.doctests_all_changed_files
	run: \|
	export MAKE="make -j2 --output-sync=recurse" SAGE_NUM_THREADS=4
	# https://github.com/tj-actions/changed-files?tab=readme-ov-file#outputs-
	./sage -t --long --format github -p4 ${{ steps.changed-files.outputs.doctests_all_changed_files }}
	shell: sh .ci/docker-exec-script.sh BUILD /sage {0}

	test-mod:
	runs-on: ubuntu-latest
	needs: [test-new]
	services:
	# https://docs.docker.com/build/ci/github-actions/local-registry/
	registry:
	image: registry:2
	ports:
	- 5000:5000
	strategy:
	fail-fast: false
	matrix:
	targets:
	- sagemath_categories-check
	steps:
	- name: Maximize build disk space
	uses: easimon/maximize-build-space@v10
	with:
	# need space in /var for Docker images
	root-reserve-mb: 30000
	remove-dotnet: true
	remove-android: true
	remove-haskell: true
	remove-codeql: true
	remove-docker-images: true

	- name: Checkout
	id: checkout
	uses: actions/checkout@v4

	- name: Install test prerequisites
	# From docker.yml
	run: \|
	sudo DEBIAN_FRONTEND=noninteractive apt-get update
	sudo DEBIAN_FRONTEND=noninteractive apt-get install tox
	sudo apt-get clean
	df -h

	- name: Merge CI fixes from sagemath/sage
	# From docker.yml
	# This step needs to happen after the commit sha is put in DOCKER_TAG
	# so that multi-stage builds can work correctly.
	run: \|
	.ci/merge-fixes.sh
	env:
	GH_TOKEN: ${{ github.token }}

	# Building

	- name: Generate Dockerfile
	# From docker.yml
	run: \|
	tox -e ${{ env.TOX_ENV }}
	cp .tox/${{ env.TOX_ENV }}/Dockerfile .
	env:
	# Only generate the Dockerfile, do not run 'docker build' here
	DOCKER_TARGETS: ""

	- name: Set up Docker Buildx
	uses: docker/setup-buildx-action@v3
	with:
	driver-opts: network=host

	- name: Build Docker image
	id: image
	uses: docker/build-push-action@v6
	with:
	push: true
	load: false
	context: .
	tags: ${{ env.BUILD_IMAGE }}
	target: with-targets
	cache-from: type=gha
	cache-to: type=gha,mode=max
	build-args: \|
	NUMPROC=6
	USE_MAKEFLAGS=-k V=0 SAGE_NUM_THREADS=4 --output-sync=recurse
	TARGETS_PRE=build/make/Makefile
	TARGETS=${{ needs.test-new.outputs.build_targets }}

	- name: Start container
	id: container
	if: (success() \|\| failure())
	run: \|
	docker run --name BUILD -dit \
	--mount type=bind,src=$(pwd),dst=$(pwd) \
	--workdir $(pwd) \
	${{ env.BUILD_IMAGE }} /bin/sh

	# Testing

	- name: Test modularized distributions
	if: (success() \|\| failure()) && steps.container.outcome == 'success'
	run: \|
	export MAKE="make -j2 --output-sync=recurse" SAGE_NUM_THREADS=4
	make V=0 tox-ensure && make ${{ matrix.targets }}
	shell: sh .ci/docker-exec-script.sh BUILD /sage {0}

	test-long:
	runs-on: ubuntu-latest
	needs: [test-new]
	services:
	# https://docs.docker.com/build/ci/github-actions/local-registry/
	registry:
	image: registry:2
	ports:
	- 5000:5000
	strategy:
	fail-fast: false
	matrix:
	tests:
	- "src/sage/[a-f]*"
	- "src/sage/[g-o]*"
	- "src/sage/[p-z]*"
	- "src/doc src/sage_docbuild src/sage_setup"
	steps:
	- name: Maximize build disk space
	uses: easimon/maximize-build-space@v10
	with:
	# need space in /var for Docker images
	root-reserve-mb: 30000
	remove-dotnet: true
	remove-android: true
	remove-haskell: true
	remove-codeql: true
	remove-docker-images: true

	- name: Checkout
	id: checkout
	uses: actions/checkout@v4

	- name: Install test prerequisites
	# From docker.yml
	run: \|
	sudo DEBIAN_FRONTEND=noninteractive apt-get update
	sudo DEBIAN_FRONTEND=noninteractive apt-get install tox
	sudo apt-get clean
	df -h

	- name: Merge CI fixes from sagemath/sage
	# From docker.yml
	# This step needs to happen after the commit sha is put in DOCKER_TAG
	# so that multi-stage builds can work correctly.
	run: \|
	.ci/merge-fixes.sh
	env:
	GH_TOKEN: ${{ github.token }}

	# Building

	- name: Generate Dockerfile
	# From docker.yml
	run: \|
	tox -e ${{ env.TOX_ENV }}
	cp .tox/${{ env.TOX_ENV }}/Dockerfile .
	env:
	# Only generate the Dockerfile, do not run 'docker build' here
	DOCKER_TARGETS: ""

	- name: Set up Docker Buildx
	uses: docker/setup-buildx-action@v3
	with:
	driver-opts: network=host

	- name: Build Docker image
	id: image
	uses: docker/build-push-action@v6
	with:
	push: true
	load: false
	context: .
	tags: ${{ env.BUILD_IMAGE }}
	target: with-targets
	cache-from: type=gha
	cache-to: type=gha,mode=max
	build-args: \|
	NUMPROC=6
	USE_MAKEFLAGS=-k V=0 SAGE_NUM_THREADS=4 --output-sync=recurse
	TARGETS_PRE=build/make/Makefile
	TARGETS=${{ needs.test-new.outputs.build_targets }}

	- name: Start container
	id: container
	if: (success() \|\| failure())
	run: \|
	docker run --name BUILD -dit \
	--mount type=bind,src=$(pwd),dst=$(pwd) \
	--workdir $(pwd) \
	${{ env.BUILD_IMAGE }} /bin/sh

	# Testing

	- name: Test all files (sage -t --long ${{ matrix.tests }})
	if: (success() \|\| failure()) && steps.container.outcome == 'success'
	run: \|
	mkdir .coverage
	rm -rf /sage/.coverage
	ln -s $(pwd)/.coverage /sage/
	cd /sage
	./sage -python -m pip install coverage
	./sage -python -m coverage run --rcfile=src/tox.ini src/bin/sage-runtests --force-lib --long -p4 --format github --random-seed=286735480429121101562228604801325644303 ${{ matrix.tests }}
	shell: sh .ci/docker-exec-script.sh BUILD . {0}

	- name: Combine coverage results
	if: (success() \|\| failure()) && steps.container.outcome == 'success'
	run: \|
	./sage -python -m coverage combine --rcfile=src/tox.ini
	shell: sh .ci/docker-exec-script.sh BUILD /sage {0}

	- name: Prepare upload
	id: copy-coverage
	if: (success() \|\| failure()) && steps.container.outcome == 'success'
	run: \|
	echo tests_id=$(echo "${{ matrix.tests }}" \| sed -E 's, +,--,g;s,/,_,g;s/[^-_A-Za-z]//g;') >> "$GITHUB_OUTPUT"

	- name: Upload coverage results
	if: (success() \|\| failure()) && steps.container.outcome == 'success'
	uses: actions/upload-artifact@v4
	with:
	# The path .coverage is a directory that contains the combined coverage
	# data file .coverage, which is a hidden file because of the leading dot
	name: coverage-${{ steps.copy-coverage.outputs.tests_id }}
	path: .coverage
	include-hidden-files: true

	coverage-report:
	runs-on: ubuntu-latest
	needs: [test-long]
	if: (success() \|\| failure())
	services:
	# https://docs.docker.com/build/ci/github-actions/local-registry/
	registry:
	image: registry:2
	ports:
	- 5000:5000
	steps:
	- name: Maximize build disk space
	uses: easimon/maximize-build-space@v10
	with:
	# need space in /var for Docker images
	root-reserve-mb: 30000
	remove-dotnet: true
	remove-android: true
	remove-haskell: true
	remove-codeql: true
	remove-docker-images: true

	- name: Checkout
	id: checkout
	uses: actions/checkout@v4

	- name: Install test prerequisites
	# From docker.yml
	run: \|
	sudo DEBIAN_FRONTEND=noninteractive apt-get update
	sudo DEBIAN_FRONTEND=noninteractive apt-get install tox
	sudo apt-get clean
	df -h

	- name: Merge CI fixes from sagemath/sage
	# From docker.yml
	# This step needs to happen after the commit sha is put in DOCKER_TAG
	# so that multi-stage builds can work correctly.
	run: \|
	.ci/merge-fixes.sh
	env:
	GH_TOKEN: ${{ github.token }}

	# Building

	- name: Generate Dockerfile
	# From docker.yml
	run: \|
	tox -e ${{ env.TOX_ENV }}
	cp .tox/${{ env.TOX_ENV }}/Dockerfile .
	env:
	# Only generate the Dockerfile, do not run 'docker build' here
	DOCKER_TARGETS: ""

	- name: Set up Docker Buildx
	uses: docker/setup-buildx-action@v3
	with:
	driver-opts: network=host

	- name: Build Docker image
	id: image
	uses: docker/build-push-action@v6
	with:
	push: true
	load: false
	context: .
	tags: ${{ env.BUILD_IMAGE }}
	target: with-targets
	cache-from: type=gha
	cache-to: type=gha,mode=max
	build-args: \|
	NUMPROC=6
	USE_MAKEFLAGS=-k V=0 SAGE_NUM_THREADS=4 --output-sync=recurse
	TARGETS_PRE=build/make/Makefile
	TARGETS=${{ needs.test-new.outputs.build_targets }}

	- name: Start container
	id: container
	if: (success() \|\| failure())
	run: \|
	docker run --name BUILD -dit \
	--mount type=bind,src=$(pwd),dst=$(pwd) \
	--workdir $(pwd) \
	${{ env.BUILD_IMAGE }} /bin/sh

	# Combining

	- name: Download coverage artifacts
	if: (success() \|\| failure()) && steps.container.outcome == 'success'
	uses: actions/download-artifact@v4
	with:
	path: .coverage
	pattern: coverage-*

	- name: Coverage report
	if: (success() \|\| failure()) && steps.container.outcome == 'success'
	# Using --omit to avoid "CoverageWarning: Couldn't parse '/tmp/tmp06qizzie/tmp_ldpu46ob.py': No source for code"
	run: \|
	rm -rf /sage/.coverage
	ln -s $(pwd)/.coverage /sage/
	cd /sage
	./sage -python -m pip install coverage
	./sage -python -m coverage combine --rcfile=src/tox.ini .coverage/coverage-*/.coverage
	./sage -python -m coverage xml --rcfile=src/tox.ini --omit="/tmp/*"
	mkdir -p .coverage/coverage-report
	mv coverage.xml .coverage/coverage-report/
	shell: sh .ci/docker-exec-script.sh BUILD . {0}

	- name: Upload coverage to codecov
	if: (success() \|\| failure()) && steps.container.outcome == 'success'
	uses: codecov/codecov-action@v4
	with:
	directory: .coverage/coverage-report

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

graphs: implementation of linear-time algorithm for modular decomposition #16667

Workflow file

graphs: implementation of linear-time algorithm for modular decomposition #16667

Jobs

Run details

Workflow file for this run