Tree.py

Summary

Lines:

219 of 219 covered (100.0%)

Branches:

98 of 98 taken (100.0%), 0 lines partially

Coverage:

100.0%

Directory:

Sphinx

Source

pyTooling/Sphinx/Tree.pycoveredpartialuncoveredexcludednot executable

# ==================================================================================================================== #
#             _____           _ _               ____        _     _                                                    #
#  _ __  _   |_   _|__   ___ | (_)_ __   __ _  / ___| _ __ | |__ (_)_ __ __  __                                        #
# | '_ \| | | || |/ _ \ / _ \| | | '_ \ / _` | \___ \| '_ \| '_ \| | '_ \\ \/ /                                        #
# | |_) | |_| || | (_) | (_) | | | | | | (_| |_ ___) | |_) | | | | | | | |>  <                                         #
# | .__/ \__, ||_|\___/ \___/|_|_|_| |_|\__, (_)____/| .__/|_| |_|_|_| |_/_/\_\                                        #
# |_|    |___/                          |___/        |_|                                                               #
# ==================================================================================================================== #
# Authors:                                                                                                             #
#   Patrick Lehmann                                                                                                    #
#                                                                                                                      #
# License:                                                                                                             #
# ==================================================================================================================== #
# Copyright 2026-2026 Patrick Lehmann - Bötzingen, Germany                                                             #
#                                                                                                                      #
# Licensed under the Apache License, Version 2.0 (the "License");                                                      #
# you may not use this file except in compliance with the License.                                                     #
# You may obtain a copy of the License at                                                                              #
#                                                                                                                      #
#   http://www.apache.org/licenses/LICENSE-2.0                                                                         #
#                                                                                                                      #
# Unless required by applicable law or agreed to in writing, software                                                  #
# distributed under the License is distributed on an "AS IS" BASIS,                                                    #
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.                                             #
# See the License for the specific language governing permissions and                                                  #
# limitations under the License.                                                                                       #
#                                                                                                                      #
# SPDX-License-Identifier: Apache-2.0                                                                                  #
# ==================================================================================================================== #
#
"""
A Sphinx directive drawing a hierarchy as a tree: a directory, a class hierarchy, the structure of a testsuite.

Written as text in a code block, a hierarchy needs its lines drawn by hand, can't link to what it shows, and can't
be folded. The ``tree`` directive takes the hierarchy as an indented list in the style of a YAML block sequence, and
draws the lines itself:

.. code-block:: ReST

   .. tree::
      :root-icon: 📦
      :node-icon: 📁
      :leaf-icon: 📄
      :icons:     > 📁

      - pyTooling
        - Tree
          - :class:`~pyTooling.Tree.Node`
        > Graph
        - README.md

**An entry is a line starting with a marker** and a space, and an entry indented deeper than the one above it is that
entry's child. An entry's text is inline ReST, so a role such as ``:class:`` or ``:ref:`` links to what the entry names.

.. rubric:: Descriptions

**A** ``|`` **between spaces separates an entry's text from its description**, which is inline ReST too. HTML draws
the descriptions as a second column: all of them start at the same horizontal position, whatever the entry's level.
An entry without a description stays valid:

.. code-block:: ReST

   .. tree::

      - CoverageSummary         | the report
        - Directory             | e.g. ``myPackage/``
          - File                | e.g. ``myPackage/Shapes.py``
        - Package

A ``|`` within a literal or a role's text, or escaped as ``\\|``, separates nothing, and neither does a substitution
reference such as ``|br|``.

.. rubric:: Roots, nodes and leaves

An entry without a parent is a root, an entry with children is a node, and every other entry is a leaf. An entry
marked ``-`` gets the icon of its kind. Option ``:icons:`` declares more markers, each with its own icon, whatever the
entry's kind is - e.g. a folder for an empty directory, which is a leaf.

.. rubric:: Legend

**An icon option may explain its icon**, behind a ``|`` between spaces: ``:leaf-icon: 📄 | file``. Option ``:icons:``
then declares one marker per line. The texts form the tree's legend, which HTML draws below the tree - or above it, as
option ``:legend:`` chooses:

.. code-block:: ReST

   .. tree::
      :legend:    top
      :root-icon: 📦 | package
      :node-icon: 📁 | directory
      :leaf-icon: 📄 | file
      :icons:     > ⚙️ | settings
                  # 🐍 | Python module

.. rubric:: HTML and other formats

HTML draws an entry with children as a ``<details>`` element, so a reader folds and unfolds it without JavaScript;
the stylesheet draws the lines and shows the expanded or the collapsed icon. Every other format - e.g. LaTeX - finds
no visitor for :class:`~pyTooling.Sphinx.Node.TreeItem` and :class:`~pyTooling.Sphinx.Node.TreeLabel` and renders
their base-classes instead: a nested bullet list without icons, with a description behind its entry's text and an en
dash. These formats have no legend, as their trees show no icons: :class:`RemoveTreeLegends` removes it.

.. seealso::

   :ref:`DIR/Tree`
      |rarr| The directive's options, with rendered examples.
   :mod:`pyTooling.Sphinx`
      |rarr| The extension this belongs to, and what else it brings.
"""
from re                                import compile as re_compile
from typing                            import Any, Iterable, Optional as Nullable
from unicodedata                       import category, east_asian_width

from docutils                          import nodes
from docutils.parsers.rst              import directives
from sphinx.transforms.post_transforms import SphinxPostTransform

from pyTooling.Common                  import StringEnum
from pyTooling.Decorators              import export
from pyTooling.Tree                    import Node
from pyTooling.Sphinx                  import BaseDirective, SphinxExtensionError, strip
from pyTooling.Sphinx.Node             import TreeDescription, TreeItem, TreeLabel, TreeLegend, TreeLegendItem
from pyTooling.Sphinx.Node             import TreeSeparator


__all__ = [
	"DEFAULT_MARKER", "DEFAULT_ICONS", "CODE_POINT_PATTERN", "SEPARATOR_PATTERN", "SEPARATOR"
]

#: The marker of an entry whose icon is the one of its kind.
DEFAULT_MARKER = "-"

#: The icons drawn when the directive's options don't state one, keyed by the option's name.
#:
#: Roots, nodes and leaves have none, so a tree shows only its lines; a node with children shows whether it is
#: expanded.
DEFAULT_ICONS = {
	"root-icon":      "",
	"node-icon":      "",
	"leaf-icon":      "",
	"expanded-icon":  "▾",
	"collapsed-icon": "▸",
}

#: A word of an icon option written as a Unicode code point, e.g. ``U+1F4C1``.
CODE_POINT_PATTERN = re_compile(r"U\+([0-9A-Fa-f]{1,6})")

#: The separator between an entry's text and its description, as group ``separator``: a ``|`` after whitespace and
#: before whitespace or the line's end.
#:
#: The other alternatives match what the separator isn't searched in - an escaped character, an inline literal, and
#: interpreted text such as a role's -, so a ``|`` in them separates nothing.
SEPARATOR_PATTERN = re_compile(r"\\.|``.*?``|`(?:\\.|[^`\\])*`|(?<=\s)(?P<separator>\|)(?=\s|$)")

#: What a format without columns writes between an entry's text and its description: an en dash between spaces.
SEPARATOR = " \u2013 "

_Entry = Node
"""
An entry of the content: its text as the value, the index of its line, its marker and its description as key-value
pairs.
"""


@export
def icon(option: Nullable[str]) -> str:
	"""
	Option converter reading an icon: characters as written, and a word ``U+<hex>`` as the code point it names.

	A code point keeps a document readable in an editor whose font lacks the icon's glyph.

	:param option:      The option's value as it was written; ``None`` if the option has no value.
	:returns:           The icon's characters; empty if the option has no value, which draws no icon.
	:raises ValueError: If a word names a code point beyond U+10FFFF.
	:raises ValueError: If a word names a surrogate code point, which is no character.
	"""
	if option is None:
		return ""

	characters = []
	for word in option.split():
		if (match := CODE_POINT_PATTERN.fullmatch(word)) is None:
			characters.append(word)
		elif (codePoint := int(match[1], 16)) > 0x10ffff:
			raise ValueError(f"'{word}' is beyond the last code point U+10FFFF.")
		elif 0xd800 <= codePoint <= 0xdfff:
			raise ValueError(f"'{word}' is a surrogate code point, which is no character.")
		else:
			characters.append(chr(codePoint))

	return "".join(characters)


@export
def describedIcon(option: Nullable[str]) -> tuple[str, str]:
	"""
	Option converter reading an icon and the text explaining it in the tree's legend: ``<icon> | <text>``.

	The icon is read by :func:`icon`. The text follows a separator ``|`` between spaces - see :data:`SEPARATOR_PATTERN`
	-, and is inline ReST. An icon without a text has no item in the legend.

	:param option:      The option's value as it was written; ``None`` if the option has no value.
	:returns:           The icon's characters and the text; empty if the option has no value or no text.
	:raises ValueError: If the value has more than one separator ``|``.
	:raises ValueError: If the value has a text, but no icon.
	"""
	if option is None:
		return "", ""

	value = f" {option}"  # a separator at the start follows a space too
	separators = [match.start() for match in SEPARATOR_PATTERN.finditer(value) if match["separator"] is not None]
	if len(separators) > 1:
		raise ValueError(f"'{option.strip()}' has more than one separator ' | '; a '|' in a text is escaped as '\\|'.")
	elif len(separators) == 0:
		return icon(option), ""

	characters = icon(value[:separators[0]])
	text =       value[separators[0] + 1:].strip()
	if characters == "" and text != "":
		raise ValueError(f"'{option.strip()}' has a text, but no icon.")

	return characters, text


@export
class LegendPosition(StringEnum):
	"""
	Where a tree's legend is drawn, as option ``:legend:`` of the ``tree`` directive states it.

	The legend gets the CSS class ``tree-legend-<value>``.
	"""

	Top =    "top"     #: Above the tree.
	Bottom = "bottom"  #: Below the tree.
	Hidden = "none"    #: Not at all.

	DEFAULT = Bottom   #: An option without a value draws the legend below the tree.


@export
def markerIcons(option: Nullable[str]) -> dict[str, tuple[str, str]]:
	"""
	Option converter reading the markers an entry may start with, each with its icon and the text explaining it in the
	tree's legend: ``<marker> <icon>``, separated by commas, or ``<marker> <icon> | <text>``, one per line.

	A marker is one character, neither a letter, a digit, a comma nor a space. An icon and its text are read by
	:func:`describedIcon`. A line with a separator ``|`` holds one marker, so a text may contain commas; a line without
	one is split at its commas.

	:param option:      The option's value as it was written; ``None`` if the option has no value.
	:returns:           The icons and their texts, keyed by their marker, in the order declared.
	:raises ValueError: If an item isn't a marker followed by a space and an icon.
	:raises ValueError: If a marker is a letter, a digit or a comma.
	:raises ValueError: If a marker is declared twice.
	:raises ValueError: If an item has more than one separator ``|``.
	"""
	if option is None:
		return {}

	icons: dict[str, tuple[str, str]] = {}
	for line in option.splitlines():
		if any(match["separator"] is not None for match in SEPARATOR_PATTERN.finditer(line)):
			items = [line]
		else:
			items = line.split(",")

		for item in items:
			if (item := item.strip()) == "":
				continue

			marker =    item[0]
			separator = item[1:2]
			value =     item[2:]
			if separator.strip() != "" or value.strip() == "":
				raise ValueError(f"'{item}' is not a marker followed by a space and an icon.")
			elif marker.isalnum():
				raise ValueError(f"Marker '{marker}' is a letter or a digit.")
			elif marker in icons:
				raise ValueError(f"Marker '{marker}' is declared twice.")

			icons[marker] = describedIcon(value)

	return icons


@export
class Tree(BaseDirective):
	"""
	The ``tree`` directive: a hierarchy, written as an indented list, drawn as a tree.

	:meth:`_ParseEntries` reads the content into :class:`~pyTooling.Tree.Node` instances, one tree per root, and
	:meth:`_BuildItem` turns them into nested bullet lists of :class:`~pyTooling.Sphinx.Node.TreeItem` and
	:class:`~pyTooling.Sphinx.Node.TreeLabel`. The options choose the icons and how many levels are expanded initially;
	``:class:`` puts additional CSS classes on the tree. :meth:`_BuildLegend` turns the texts of the icons into the
	tree's legend, which ``:legend:`` places above or below the tree.

	If an entry has a description, every entry's text ends with a :class:`~pyTooling.Sphinx.Node.TreeDescription`, and
	:meth:`_ColumnWidth` estimates how wide the column of the texts in front of the descriptions is.
	"""

	directiveName: str = "tree"  #: Name the directive is invoked by.

	has_content =               True   #: A boolean; ``True`` if content is allowed.
	required_arguments =        0      #: Number of required directive arguments.
	optional_arguments =        0      #: Number of optional arguments after the required ones.
	final_argument_whitespace = False  #: A boolean; ``True`` if the last argument may contain spaces.
	# docutils declares 'option_spec' on 'Directive' and 'BaseDirective' assigns it, so mypy calls every
	# spelling of this override a conflict with one of them
	#: Mapping of option names to validator functions.
	option_spec: dict[str, Any] = {  # type: ignore[misc]
		"root-icon":       describedIcon,
		"node-icon":       describedIcon,
		"leaf-icon":       describedIcon,
		"expanded-icon":   icon,
		"collapsed-icon":  icon,
		"icons":           markerIcons,
		"legend":          LegendPosition.Parse,
		"expanded-levels": directives.nonnegative_int,
		"class":           strip,
	}

	def run(self) -> list[nodes.Node]:
		"""
		Draw the hierarchy written in the content, and the legend of its icons.

		Option ``:legend:`` without any icon having a text draws no legend, and is warned about.

		:returns: The tree as a bullet list with its legend above or below it, or the message of whatever the content or
		          the icons' texts got wrong.
		"""
		markers = self.options.get("icons", {})
		describedIcons = {
			name: self.options.get(name, (DEFAULT_ICONS[name], "")) for name in ("root-icon", "node-icon", "leaf-icon")
		}
		describedIcons.update(markers)
		position = self.options.get("legend", LegendPosition.DEFAULT)
		try:
			roots = self._ParseEntries(self.content, (DEFAULT_MARKER, *markers))
			legend, messages = self._BuildLegend(describedIcons.values(), position)
		except SphinxExtensionError as ex:
			return [self.state.document.reporter.error(f"{self.directiveName}: {ex}", line=self.lineno)]

		icons = {name: self.options.get(name, DEFAULT_ICONS[name]) for name in ("expanded-icon", "collapsed-icon")}
		icons.update((key, characters) for key, (characters, _) in describedIcons.items())
		expandedLevels = self.options.get("expanded-levels", None)
		descriptionColumn = any(entry["description"] != "" for root in roots for entry in root.IteratePreOrder())

		tree = nodes.bullet_list(classes=["pytooling-tree"] + self.options.get("class", "").split())
		for root in roots:
			tree += self._BuildItem(root, icons, expandedLevels, descriptionColumn)

		if descriptionColumn:
			columnWidth = self._ColumnWidth(tree.findall(TreeLabel))
			for item in tree.children:
				item["columnWidth"] = columnWidth

		if len(legend.children) == 0:
			if "legend" in self.options and position is not LegendPosition.Hidden:
				messages.append(self.state.document.reporter.warning(
					f"{self.directiveName}: ':legend: {position}' without an icon having a text draws no legend.",
					line=self.lineno
				))
			return [tree, *messages]
		elif position is LegendPosition.Top:
			return [legend, tree, *messages]
		elif position is LegendPosition.Bottom:
			return [tree, legend, *messages]
		else:
			return [tree, *messages]

	def _BuildLegend(
		self,
		describedIcons: Iterable[tuple[str, str]],
		position: LegendPosition
	) -> tuple[TreeLegend, list[nodes.system_message]]:
		"""
		Build the legend of the tree's icons: an item per icon with a text, in the order given.

		An icon given twice with the same text - e.g. a folder for a node and for a marker - is explained once. A text is
		parsed as inline ReST at the directive's line, as an option has no line of its own.

		:param describedIcons:        Each icon with its text; an icon with an empty text has no item.
		:param position:              Where the legend is drawn; the legend gets the CSS class ``tree-legend-<position>``.
		:returns:                     The legend - without items, if no icon has a text -, and the messages about the
		                              texts.
		:raises SphinxExtensionError: If an icon is given twice with different texts.
		"""
		texts: dict[str, str] = {}
		for characters, text in describedIcons:
			if text == "":
				continue
			elif characters not in texts:
				texts[characters] = text
			elif texts[characters] != text:
				raise SphinxExtensionError(f"Icon '{characters}' has two texts: '{texts[characters]}' and '{text}'.")

		legend = TreeLegend("", classes=["pytooling-tree-legend", f"tree-legend-{position}"])
		messages: list[nodes.system_message] = []
		for characters, text in texts.items():
			textNodes, textMessages = self.state.inline_text(text, self.lineno)
			legend += TreeLegendItem(text, "", *textNodes, icon=characters)
			messages.extend(textMessages)

		return legend, messages

	@staticmethod
	def _ParseEntries(content: Iterable[str], markers: Iterable[str] = (DEFAULT_MARKER, )) -> list[_Entry]:
		"""
		Read the content into trees: an entry per line, and an entry indented deeper than the one above is its child.

		An entry's text is the node's value. Key ``index`` holds the index of the entry's line in the content, key
		``marker`` the marker the line starts with, and key ``description`` the text behind a separator ``|`` - see
		:data:`SEPARATOR_PATTERN` -, or an empty string.

		:param content:               The directive's content, line by line.
		:param markers:               Optional, the markers an entry may start with. Default: ``-``.
		:returns:                     The root of each tree, in the order written.
		:raises SphinxExtensionError: If the content holds no entry.
		:raises SphinxExtensionError: If a line doesn't start with a marker and a space.
		:raises SphinxExtensionError: If a line has more than one separator ``|``.
		:raises SphinxExtensionError: If an entry has no text.
		:raises SphinxExtensionError: If an entry is indented less than the entry above, but not as deep as one of its
		                              ancestors.
		"""
		roots: list[_Entry] = []
		ancestors: list[tuple[int, _Entry]] = []  # entries the next one can be a child or a sibling of, with indentation
		for index, line in enumerate(content):
			if (text := line.lstrip(" ")).strip() == "":
				continue

			indentation = len(line) - len(text)
			marker = text[0]
			if marker not in markers or text[1:2].strip() != "":
				accepted = ", ".join(f"'{marker} '" for marker in markers)
				raise SphinxExtensionError(f"'{text.rstrip()}' is not an entry, which starts with {accepted}.")

			separators = [match.start() for match in SEPARATOR_PATTERN.finditer(text) if match["separator"] is not None]
			if len(separators) > 1:
				raise SphinxExtensionError(
					f"'{text.rstrip()}' has more than one separator ' | '; a '|' in a text is escaped as '\\|'."
				)
			elif len(separators) == 1:
				value, description = text[1:separators[0]].strip(), text[separators[0] + 1:].strip()
			else:
				value, description = text[1:].strip(), ""

			if value == "":
				raise SphinxExtensionError(f"'{text.rstrip()}' is an entry without text.")

			closed = False
			while len(ancestors) > 0 and ancestors[-1][0] > indentation:
				ancestors.pop()
				closed = True

			if len(ancestors) > 0 and ancestors[-1][0] == indentation:
				ancestors.pop()
			elif closed:
				raise SphinxExtensionError(
					f"'{text.rstrip()}' is indented less than the entry above, but not as deep as one of its ancestors."
				)

			parent = ancestors[-1][1] if len(ancestors) > 0 else None
			entry: _Entry = Node(
				value=value, keyValuePairs={"index": index, "marker": marker, "description": description}, parent=parent
			)
			if parent is None:
				roots.append(entry)

			ancestors.append((indentation, entry))

		if len(roots) == 0:
			raise SphinxExtensionError("The directive's content holds no entry.")

		return roots

	def _BuildItem(
		self,
		entry: _Entry,
		icons: dict[str, str],
		expandedLevels: Nullable[int],
		descriptionColumn: bool
	) -> TreeItem:
		"""
		Build an entry and, below it, its children.

		The entry's text and description are parsed as inline ReST at the line they were written on, so a message about
		a role in them points to that line. Such messages follow the entry's text in the list item.

		:param entry:             The entry, as :meth:`_ParseEntries` read it.
		:param icons:             The icons, keyed by the option naming them, or by their marker.
		:param expandedLevels:    How many levels are expanded initially; ``None`` expands all.
		:param descriptionColumn: Whether the tree has descriptions: then the entry's text ends with a description, empty
		                          if the entry has none.
		:returns:                 The entry as a list item, holding its text and a bullet list of its children.
		"""
		line = self.content_offset + entry["index"] + 1
		textNodes, messages = self.state.inline_text(entry.Value, line)

		if entry.IsRoot:
			kind = "root"
		elif entry.HasChildren:
			kind = "node"
		else:
			kind = "leaf"

		entryIcon = icons[entry["marker"]] if entry["marker"] in icons else icons[f"{kind}-icon"]

		item = TreeItem("", classes=[f"tree-{kind}"] + (["tree-expandable"] if entry.HasChildren else []))
		item["columnWidth"] = None
		item += (label := TreeLabel(entry.Value, "", *textNodes, icon=entryIcon, level=entry.Level))
		if descriptionColumn:
			description = TreeDescription(entry["description"])
			if entry["description"] != "":
				descriptionNodes, descriptionMessages = self.state.inline_text(entry["description"], line)
				description += descriptionNodes
				messages += descriptionMessages
				label += TreeSeparator("", SEPARATOR)

			label += description

		item += messages

		if not entry.HasChildren:
			item["expanded"] = None
			label["expandedIcon"] = None
			label["collapsedIcon"] = None
			return item

		item["expanded"] = expandedLevels is None or entry.Level < expandedLevels
		label["expandedIcon"] = icons["expanded-icon"]
		label["collapsedIcon"] = icons["collapsed-icon"]

		item += (children := nodes.bullet_list())
		for child in entry.GetChildren():
			children += self._BuildItem(child, icons, expandedLevels, descriptionColumn)

		return item

	@staticmethod
	def _ColumnWidth(labels: Iterable[TreeLabel]) -> str:
		"""
		Estimate the width of the column of the entries' texts in a tree with descriptions, from the tree's left edge.

		An entry needs its level's indentation, its expander, and its icon, a gap and its text. HTML renders the text
		later, in a font chosen by the theme, so the text's width is estimated in character cells, CSS unit ``ch``: two
		for a wide character, e.g. an emoji, none for a combining or format character, e.g. a variation selector, and
		one for every other character. The gap counts as one cell.

		The width is the widest entry's: per level, the indentation and the most cells at that level, and of these the
		maximum, computed by the browser with CSS function ``max()``. The indentation is CSS custom property
		``--pyTooling-tree-level``, so a project's indentation is accounted for.

		:param labels: The entries' texts, with their level, icon and description.
		:returns:      The width as a CSS length.
		"""
		cellsPerLevel: dict[int, int] = {}
		for label in labels:
			text = "".join(
				child.astext() for child in label.children if not isinstance(child, (TreeSeparator, TreeDescription))
			)
			if label["icon"] != "":
				text = f"{label['icon']} {text}"

			cells = sum(
				2 if east_asian_width(character) in ("W", "F") else 0 if category(character) in ("Mn", "Me", "Cf") else 1
				for character in text
			)
			cellsPerLevel[label["level"]] = max(cells, cellsPerLevel.get(label["level"], 0))

		widths = ", ".join(
			f"{cells}ch" if level == 0 else f"calc({level} * var(--pyTooling-tree-level) + {cells}ch)"
			for level, cells in sorted(cellsPerLevel.items())
		)
		return f"calc(var(--pyTooling-tree-expander-width) + max({widths}))"


@export
class RemoveTreeLegends(SphinxPostTransform):
	"""
	A post-transform removing the trees' legends from the output formats, whose trees show no icons: LaTeX, text,
	manual pages and Texinfo.

	These formats write a tree as a nested bullet list, so a legend would explain icons the reader doesn't see.
	"""

	default_priority = 200                                  #: Priority among the post-transforms.
	formats =          ("latex", "text", "man", "texinfo")  #: Output formats the transform runs for.

	def run(self, **kwargs: Any) -> None:
		"""
		Remove every legend of a tree.

		:param kwargs: Keyword arguments Sphinx passes to a post-transform; none is used.
		"""
		for legend in list(self.document.findall(TreeLegend)):
			legend.parent.remove(legend)