Repository: py-pdf/pypdf
Issue category: Performance Issue

Issue:
ROB: reading PDF with multiple forms is really slow
When reading a specific PDF file with a lot of forms, the `get_fields()` seems to loop for a very long time (one hour and a half on my setup).

## Environment

Which environment were you using when you encountered the problem?

```bash
$ python -m platform
Linux-5.4.0-173-generic-x86_64-with-glibc2.29

$ python -c "import pypdf;print(pypdf._debug_versions)"
pypdf==4.2.0, crypt_provider=('pycryptodome', '3.20.0'), PIL=10.3.0
```

## Code + PDF

This is a minimal, complete example that shows the issue:

```python
from pypdf import PdfReader
with open('inheritance.pdf', 'rb') as f:
    doc = PdfReader(f)
    doc.get_fields()
```

The PDF file (coming from https://www.nj.gov/treasury/taxation/pdf/other_forms/inheritance/itrbk.pdf):
[inheritance.pdf](https://github.com/py-pdf/pypdf/files/15306053/inheritance.pdf)


## Traceback

The `get_fields()` function seems to make a lot of recursive `_check_kids()` calls

```
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1115, 0, 133206044573808), IndirectObject(1865, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1107, 0, 133206044573808), IndirectObject(1866, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1107, 0, 133206044573808), IndirectObject(1866, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1071, 0, 133206044573808), IndirectObject(1864, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1115, 0, 133206044573808), IndirectObject(1865, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1107, 0, 133206044573808), IndirectObject(1866, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1107, 0, 133206044573808), IndirectObject(1866, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1115, 0, 133206044573808), IndirectObject(1865, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1107, 0, 133206044573808), IndirectObject(1866, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(942, 0, 133206044573808), IndirectObject(922, 0, 133206044573808)]
Recursing down 5 kids: [IndirectObject(1120, 0, 133206044573808), IndirectObject(1867, 0, 133206044573808)]
```



Hints:
Thanks for the report. That surely does not look right.
If ever useful: another (smaller) file where the same problem happens: https://www.courts.ca.gov/documents/fl410.pdf
@farjasju 
You should have a look  at the document with PdfBox with debug function to look at the pdf structure. There is a lot of fields that exists in the document (fields can be identified in the field /T. You may see a lot of fields named 0, 1 : they are different from each others : the qualified name are differents.
There might be some optimisation. also can you check the document does not includes some (infinite)loops (where some protection may be required)
I confirm that the file is "corrupted" with some objects being a grand child of itself:

![67820872-daee-48e8-aa91-0c83441be86b](https://github.com/py-pdf/pypdf/assets/4083478/3aa8ccc1-34a7-45ad-accc-9bd8ba7d19d1)


Patch:
diff --git a/pypdf/_doc_common.py b/pypdf/_doc_common.py
index 84e99208a..0baab4fc7 100644
--- a/pypdf/_doc_common.py
+++ b/pypdf/_doc_common.py
@@ -492,17 +492,19 @@ def get_fields(
         tree: Optional[TreeObject] = None,
         retval: Optional[Dict[Any, Any]] = None,
         fileobj: Optional[Any] = None,
+        stack: Optional[List[PdfObject]] = None,
     ) -> Optional[Dict[str, Any]]:
         """
         Extract field data if this PDF contains interactive form fields.
 
-        The *tree* and *retval* parameters are for recursive use.
+        The *tree*, *retval*, *stack* parameters are for recursive use.
 
         Args:
-            tree:
-            retval:
+            tree: Current object to parse.
+            retval: In-progress list of fields.
             fileobj: A file object (usually a text file) to write
                 a report to on all interactive form fields found.
+            stack: List of already parsed objects.
 
         Returns:
             A dictionary where each key is a field name, and each
@@ -515,6 +517,7 @@ def get_fields(
         if retval is None:
             retval = {}
             catalog = self.root_object
+            stack = []
             # get the AcroForm tree
             if CD.ACRO_FORM in catalog:
                 tree = cast(Optional[TreeObject], catalog[CD.ACRO_FORM])
@@ -522,19 +525,15 @@ def get_fields(
                 return None
         if tree is None:
             return retval
-        self._check_kids(tree, retval, fileobj)
-        for attr in field_attributes:
-            if attr in tree:
-                # Tree is a field
-                self._build_field(tree, retval, fileobj, field_attributes)
-                break
-
+        assert stack is not None
         if "/Fields" in tree:
             fields = cast(ArrayObject, tree["/Fields"])
             for f in fields:
                 field = f.get_object()
-                self._build_field(field, retval, fileobj, field_attributes)
-
+                self._build_field(field, retval, fileobj, field_attributes, stack)
+        elif any(attr in tree for attr in field_attributes):
+            # Tree is a field
+            self._build_field(tree, retval, fileobj, field_attributes, stack)
         return retval
 
     def _get_qualified_field_name(self, parent: DictionaryObject) -> str:
@@ -557,25 +556,11 @@ def _build_field(
         retval: Dict[Any, Any],
         fileobj: Any,
         field_attributes: Any,
+        stack: List[PdfObject],
     ) -> None:
-        self._check_kids(field, retval, fileobj)
-        try:
-            key = cast(str, field["/TM"])
-        except KeyError:
-            try:
-                if "/Parent" in field:
-                    key = (
-                        self._get_qualified_field_name(
-                            cast(DictionaryObject, field["/Parent"])
-                        )
-                        + "."
-                    )
-                else:
-                    key = ""
-                key += cast(str, field["/T"])
-            except KeyError:
-                # Ignore no-name field for now
-                return
+        if all(attr not in field for attr in ("/T", "/TM")):
+            return
+        key = self._get_qualified_field_name(field)
         if fileobj:
             self._write_field(fileobj, field, field_attributes)
             fileobj.write("\n")
@@ -604,14 +589,27 @@ def _build_field(
                 and "/Off" in retval[key]["/_States_"]
             ):
                 del retval[key]["/_States_"][retval[key]["/_States_"].index("/Off")]
+        # at last for order
+        self._check_kids(field, retval, fileobj, stack)
 
     def _check_kids(
-        self, tree: Union[TreeObject, DictionaryObject], retval: Any, fileobj: Any
+        self,
+        tree: Union[TreeObject, DictionaryObject],
+        retval: Any,
+        fileobj: Any,
+        stack: List[PdfObject],
     ) -> None:
+        if tree in stack:
+            logger_warning(
+                f"{self._get_qualified_field_name(tree)} already parsed", __name__
+            )
+            return
+        stack.append(tree)
         if PA.KIDS in tree:
             # recurse down the tree
             for kid in tree[PA.KIDS]:  # type: ignore
-                self.get_fields(kid.get_object(), retval, fileobj)
+                kid = kid.get_object()
+                self.get_fields(kid, retval, fileobj, stack)
 
     def _write_field(self, fileobj: Any, field: Any, field_attributes: Any) -> None:
         field_attributes_tuple = FA.attributes()


Test patch:
diff --git a/tests/test_reader.py b/tests/test_reader.py
index 83b61bc59..4557270bb 100644
--- a/tests/test_reader.py
+++ b/tests/test_reader.py
@@ -1530,3 +1530,30 @@ def test_damaged_pdf():
     assert (
         exc.value.args[0] == "Expected object ID (21 0) does not match actual (-1 -1)."
     )
+
+
+@pytest.mark.enable_socket()
+@pytest.mark.timeout(10)
+def test_looping_form(caplog):
+    """Cf iss 2643"""
+    url = "https://github.com/py-pdf/pypdf/files/15306053/inheritance.pdf"
+    name = "iss2643.pdf"
+    reader = PdfReader(BytesIO(get_data_from_url(url, name=name)), strict=False)
+    flds = reader.get_fields()
+    assert all(
+        x in flds
+        for x in (
+            "Text10",
+            "Text10.0.0.1.1.1.1.1.1.1.1.1.1.1.1.1.1.1",
+            "amt1.0",
+            "amt1.1",
+            "DSS#3pg3#0hgu7",
+        )
+    )
+    writer = PdfWriter(reader)
+    writer.root_object["/AcroForm"]["/Fields"][5]["/Kids"].append(
+        writer.root_object["/AcroForm"]["/Fields"][5]["/Kids"][0]
+    )
+    flds2 = writer.get_fields()
+    assert "Text68.0 already parsed" in caplog.text
+    assert list(flds.keys()) == list(flds2.keys())