Skip to content

Detect cycles in dependency graph #78

@BoltonBailey

Description

@BoltonBailey

This is a bit of a niche error that I was experiencing when I accidentally included a circular dependency in the dependency graph of the latex \uses labels in our blueprint project.

This led to an error building the blueprint which manifested as:

  File "/home/runner/work/LiveProveBench/LiveProveBench/env/lib/python3.11/site-packages/plasTeX/TeX.py", line 428, in parse
    callback()
  File "/home/runner/work/LiveProveBench/LiveProveBench/env/lib/python3.11/site-packages/leanblueprint/Packages/blueprint.py", line 233, in make_lean_data
    n) == 'definition' for n in graph.ancestors(node).union({node}))
                                ^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/work/LiveProveBench/LiveProveBench/env/lib/python3.11/site-packages/plastexdepgraph/Packages/depgraph.py", line 112, in ancestors
    pred.union(*map(self.ancestors, pred)))
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/work/LiveProveBench/LiveProveBench/env/lib/python3.11/site-packages/plastexdepgraph/Packages/depgraph.py", line 112, in ancestors
    pred.union(*map(self.ancestors, pred)))
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/work/LiveProveBench/LiveProveBench/env/lib/python3.11/site-packages/plastexdepgraph/Packages/depgraph.py", line 112, in ancestors
    pred.union(*map(self.ancestors, pred)))
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  [Previous line repeated 987 more times]
  File "/home/runner/work/LiveProveBench/LiveProveBench/env/lib/python3.11/site-packages/plastexdepgraph/Packages/depgraph.py", line 110, in ancestors
    pred = self.predecessors(node)
           ^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/work/LiveProveBench/LiveProveBench/env/lib/python3.11/site-packages/plastexdepgraph/Packages/depgraph.py", line 94, in predecessors
    if node in self._predecessors:
       ^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/work/LiveProveBench/LiveProveBench/env/lib/python3.11/site-packages/plasTeX/DOM/__init__.py", line 1171, in __hash__
    return id(self)
           ^^^^^^^^
RecursionError: maximum recursion depth exceeded while calling a Python object

I eventually tracked down the change that included the circular dependency, but it would be nicer if either blueprint or plastexdepgraph would short-circuit these cycles so it could tell me the names of the labels that were causing the problem.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions