sphinxdocs: add typedef directive for documenting user-defined types (#2300)

This adds support for documenting user-defined Starlark "types".
Starlark doesn't have
user-defined types as a first-class concept, but an equivalent can be
done by using
`struct` with lambdas and closures. On the documentation side, the
structure of these
objects can be shown by have a module-level struct with matching
attributes.

On the Sphinx side of things, this is simple to support (and the
functionality was largely
already there): it's just having a directive with other directives
within it (this
is the same way other languages handle it).

On the Starlark side of things, its a bit more complicated. Stardoc can
process a
module-level struct, but essentially returns a list of `(dotted_name,
object_proto)`,
and it will only include object types it recognizes (e.g. functions,
providers, rules, etc).

To work within this limitation, the proto-to-markdown converter special
cases the name
"TYPEDEF" to indicate a typedef. Everything with the same prefix is then
treated as
a member of the typedef and nested within the generated typedef
directive. Conveniently,
because the "TYPEDEF" object is a function, it can then include that in
the output
and we get "class doc" functionality for free.

This is mostly motivated by converting rules_testing to use sphinxdocs.
While rules_python
has a couple user-define types (e.g. the depset/runfiles/PyInfo
builders),
rules_testing has dozens of such types, which makes it untenable to
hand-write docs
describing them all. Today, rules_testing is already mostly following
the format sphinxdocs
proscribes to generate its at
https://rules-testing.readthedocs.io/en/latest/api/index.html,
and it's worked pretty well.
diff --git a/sphinxdocs/docs/sphinx-bzl.md b/sphinxdocs/docs/sphinx-bzl.md
index 73ae138..8376f60 100644
--- a/sphinxdocs/docs/sphinx-bzl.md
+++ b/sphinxdocs/docs/sphinx-bzl.md
@@ -227,6 +227,11 @@
 MyST notation.
 :::
 
+Directives can be nested, but [the inner directives must have **fewer** colons
+than outer
+directives](https://myst-parser.readthedocs.io/en/latest/syntax/roles-and-directives.html#nesting-directives).
+
+
 :::{rst:directive} .. bzl:currentfile:: file
 
 This directive indicates the Bazel file that objects defined in the current
@@ -237,21 +242,87 @@
 :::
 
 
-:::{rst:directive} .. bzl:target:: target
+:::::{rst:directive} .. bzl:target:: target
 
 Documents a target. It takes no directive options. The format of `target`
 can either be a fully qualified label (`//foo:bar`), or the base target name
 relative to `{bzl:currentfile}`.
 
-```
+````
 :::{bzl:target} //foo:target
 
 My docs
 :::
-```
+````
+
+:::::
 
 :::{rst:directive} .. bzl:flag:: target
 
 Documents a flag. It has the same format as `{bzl:target}`
 :::
 
+::::::{rst:directive} .. bzl:typedef:: typename
+
+Documents a user-defined structural "type".  These are typically generated by
+the {obj}`sphinx_stardoc` rule after following [User-defined types] to create a
+struct with a `TYPEDEF` field, but can also be manually defined if there's
+no natural place for it in code, e.g. some ad-hoc structural type.
+
+`````
+::::{bzl:typedef} Square
+Doc about Square
+
+:::{bzl:field} width
+:type: int
+:::
+
+:::{bzl:function} new(size)
+  ...
+:::
+
+:::{bzl:function} area()
+  ...
+:::
+::::
+`````
+
+Note that MyST requires the number of colons for the outer typedef directive
+to be greater than the inner directives. Otherwise, only the first nested
+directive is parsed as part of the typedef, but subsequent ones are not.
+::::::
+
+:::::{rst:directive} .. bzl:field:: fieldname
+
+Documents a field of an object. These are nested within some other directive,
+typically `{bzl:typedef}`
+
+Directive options:
+* `:type:` specifies the type of the field
+
+````
+:::{bzl:field} fieldname
+:type: int | None | str
+
+Doc about field
+:::
+````
+:::::
+
+:::::{rst:directive} .. bzl:provider-field:: fieldname
+
+Documents a field of a provider. The directive itself is autogenerated by
+`sphinx_stardoc`, but the content is simply the documentation string specified
+in the provider's field.
+
+Directive options:
+* `:type:` specifies the type of the field
+
+````
+:::{bzl:provider-field} fieldname
+:type: depset[File] | None
+
+Doc about the provider field
+:::
+````
+:::::
diff --git a/sphinxdocs/docs/starlark-docgen.md b/sphinxdocs/docs/starlark-docgen.md
index d131607..ba4ab51 100644
--- a/sphinxdocs/docs/starlark-docgen.md
+++ b/sphinxdocs/docs/starlark-docgen.md
@@ -73,3 +73,90 @@
    deps = ...
 )
 ```
+
+## User-defined types
+
+While Starlark doesn't have user-defined types as a first-class concept, it's
+still possible to create such objects using `struct` and lambdas. For the
+purposes of documentation, they can be documented by creating a module-level
+`struct` with matching fields *and* also a field named `TYPEDEF`. When the
+`sphinx_stardoc` rule sees a struct with a `TYPEDEF` field, it generates doc
+using the {rst:directive}`bzl:typedef` directive and puts all the struct's fields
+within the typedef. The net result is the rendered docs look similar to how
+a class would be documented in other programming languages.
+
+For example, a the Starlark implemenation of a `Square` object with a `area()`
+method would look like:
+
+```
+
+def _Square_typedef():
+    """A square with fixed size.
+
+    :::{field} width
+    :type: int
+    :::
+    """
+
+def _Square_new(width):
+    """Creates a Square.
+
+    Args:
+        width: {type}`int` width of square
+
+    Returns:
+        {type}`Square`
+    """
+    self = struct(
+        area = lambda *a, **k: _Square_area(self, *a, **k),
+        width = width
+    )
+    return self
+
+def _Square_area(self, ):
+   """Tells the area of the square."""
+   return self.width * self.width
+
+Square = struct(
+  TYPEDEF = _Square_typedef,
+  new = _Square_new,
+  area = _Square_area,
+)
+```
+
+This will then genereate markdown that looks like:
+
+```
+::::{bzl:typedef} Square
+A square with fixed size
+
+:::{bzl:field} width
+:type: int
+:::
+:::{bzl:function} new()
+...args etc from _Square_new...
+:::
+:::{bzl:function} area()
+...args etc from _Square_area...
+:::
+::::
+```
+
+Which renders as:
+
+:::{bzl:currentfile} //example:square.bzl
+:::
+
+::::{bzl:typedef} Square
+A square with fixed size
+
+:::{bzl:field} width
+:type: int
+:::
+:::{bzl:function} new()
+...
+:::
+:::{bzl:function} area()
+...
+:::
+::::
diff --git a/sphinxdocs/private/proto_to_markdown.py b/sphinxdocs/private/proto_to_markdown.py
index d667eec..1f0fe31 100644
--- a/sphinxdocs/private/proto_to_markdown.py
+++ b/sphinxdocs/private/proto_to_markdown.py
@@ -96,6 +96,15 @@
         self._module = module
         self._out_stream = out_stream
         self._public_load_path = public_load_path
+        self._typedef_stack = []
+
+    def _get_colons(self):
+        # There's a weird behavior where increasing colon indents doesn't
+        # parse as nested objects correctly, so we have to reduce the
+        # number of colons based on the indent level
+        indent = 10 - len(self._typedef_stack)
+        assert indent >= 0
+        return ":::" + ":" * indent
 
     def render(self):
         self._render_module(self._module)
@@ -115,11 +124,10 @@
             "\n\n",
         )
 
-        # Sort the objects by name
         objects = itertools.chain(
             ((r.rule_name, r, self._render_rule) for r in module.rule_info),
             ((p.provider_name, p, self._render_provider) for p in module.provider_info),
-            ((f.function_name, f, self._render_func) for f in module.func_info),
+            ((f.function_name, f, self._process_func_info) for f in module.func_info),
             ((a.aspect_name, a, self._render_aspect) for a in module.aspect_info),
             (
                 (m.extension_name, m, self._render_module_extension)
@@ -130,13 +138,31 @@
                 for r in module.repository_rule_info
             ),
         )
+        # Sort by name, ignoring case. The `.TYPEDEF` string is removed so
+        # that the .TYPEDEF entries come before what is in the typedef.
+        objects = sorted(objects, key=lambda v: v[0].removesuffix(".TYPEDEF").lower())
 
-        objects = sorted(objects, key=lambda v: v[0].lower())
-
-        for _, obj, func in objects:
-            func(obj)
+        for name, obj, func in objects:
+            self._process_object(name, obj, func)
             self._write("\n")
 
+        # Close any typedefs
+        while self._typedef_stack:
+            self._typedef_stack.pop()
+            self._render_typedef_end()
+
+    def _process_object(self, name, obj, renderer):
+        # The trailing doc is added to prevent matching a common prefix
+        typedef_group = name.removesuffix(".TYPEDEF") + "."
+        while self._typedef_stack and not typedef_group.startswith(
+            self._typedef_stack[-1]
+        ):
+            self._typedef_stack.pop()
+            self._render_typedef_end()
+        renderer(obj)
+        if name.endswith(".TYPEDEF"):
+            self._typedef_stack.append(typedef_group)
+
     def _render_aspect(self, aspect: stardoc_output_pb2.AspectInfo):
         _sort_attributes_inplace(aspect.attribute)
         self._write("::::::{bzl:aspect} ", aspect.aspect_name, "\n\n")
@@ -242,12 +268,32 @@
             # Rather than error, give some somewhat understandable value.
             return _AttributeType.Name(attr.type)
 
+    def _process_func_info(self, func):
+        if func.function_name.endswith(".TYPEDEF"):
+            self._render_typedef_start(func)
+        else:
+            self._render_func(func)
+
+    def _render_typedef_start(self, func):
+        self._write(
+            self._get_colons(),
+            "{bzl:typedef} ",
+            func.function_name.removesuffix(".TYPEDEF"),
+            "\n",
+        )
+        if func.doc_string:
+            self._write(func.doc_string.strip(), "\n")
+
+    def _render_typedef_end(self):
+        self._write(self._get_colons(), "\n\n")
+
     def _render_func(self, func: stardoc_output_pb2.StarlarkFunctionInfo):
-        self._write("::::::{bzl:function} ")
+        self._write(self._get_colons(), "{bzl:function} ")
 
         parameters = self._render_func_signature(func)
 
-        self._write(func.doc_string.strip(), "\n\n")
+        if doc_string := func.doc_string.strip():
+            self._write(doc_string, "\n\n")
 
         if parameters:
             for param in parameters:
@@ -268,10 +314,13 @@
             self._write(":::::{deprecated}: unknown\n")
             self._write("  ", _indent_block_text(func.deprecated.doc_string), "\n")
             self._write(":::::\n")
-        self._write("::::::\n")
+        self._write(self._get_colons(), "\n")
 
     def _render_func_signature(self, func):
-        self._write(f"{func.function_name}(")
+        func_name = func.function_name
+        if self._typedef_stack:
+            func_name = func.function_name.removeprefix(self._typedef_stack[-1])
+        self._write(f"{func_name}(")
         # TODO: Have an "is method" directive in the docstring to decide if
         # the self parameter should be removed.
         parameters = [param for param in func.parameter if param.name != "self"]
diff --git a/sphinxdocs/src/sphinx_bzl/bzl.py b/sphinxdocs/src/sphinx_bzl/bzl.py
index 54b1285..90fb109 100644
--- a/sphinxdocs/src/sphinx_bzl/bzl.py
+++ b/sphinxdocs/src/sphinx_bzl/bzl.py
@@ -424,7 +424,7 @@
         return [wrapper]
 
 
-class _BzlField(_BzlXrefField, docfields.Field):
+class _BzlDocField(_BzlXrefField, docfields.Field):
     """A non-repeated field with xref support."""
 
 
@@ -623,6 +623,7 @@
         relative_name = relative_name.strip()
 
         name_prefix, _, base_symbol_name = relative_name.rpartition(".")
+
         if name_prefix:
             # Respect whatever the signature wanted
             display_prefix = name_prefix
@@ -819,6 +820,28 @@
     """Abstract base class for objects that are callable."""
 
 
+class _BzlTypedef(_BzlObject):
+    """Documents a typedef.
+
+    A typedef describes objects with well known attributes.
+
+    `````
+    ::::{bzl:typedef} Square
+
+    :::{bzl:field} width
+    :type: int
+    :::
+
+    :::{bzl:function} new(size)
+    :::
+
+    :::{bzl:function} area()
+    :::
+    ::::
+    `````
+    """
+
+
 class _BzlProvider(_BzlObject):
     """Documents a provider type.
 
@@ -837,7 +860,7 @@
     """
 
 
-class _BzlProviderField(_BzlObject):
+class _BzlField(_BzlObject):
     """Documents a field of a provider.
 
     Fields can optionally have a type specified using the `:type:` option.
@@ -872,6 +895,10 @@
         return alt_names
 
 
+class _BzlProviderField(_BzlField):
+    pass
+
+
 class _BzlRepositoryRule(_BzlCallable):
     """Documents a repository rule.
 
@@ -951,7 +978,7 @@
             rolename="attr",
             can_collapse=False,
         ),
-        _BzlField(
+        _BzlDocField(
             "provides",
             label="Provides",
             has_arg=False,
@@ -1078,13 +1105,13 @@
     """
 
     doc_field_types = [
-        _BzlField(
+        _BzlDocField(
             "os-dependent",
             label="OS Dependent",
             has_arg=False,
             names=["os-dependent"],
         ),
-        _BzlField(
+        _BzlDocField(
             "arch-dependent",
             label="Arch Dependent",
             has_arg=False,
@@ -1448,7 +1475,8 @@
         # Providers are close enough to types that we include "type". This
         # also makes :type: Foo work in directive options.
         "provider": domains.ObjType("provider", "provider", "type", "obj"),
-        "provider-field": domains.ObjType("provider field", "field", "obj"),
+        "provider-field": domains.ObjType("provider field", "provider-field", "obj"),
+        "field": domains.ObjType("field", "field", "obj"),
         "repo-rule": domains.ObjType("repository rule", "repo_rule", "obj"),
         "rule": domains.ObjType("rule", "rule", "obj"),
         "tag-class": domains.ObjType("tag class", "tag_class", "obj"),
@@ -1457,6 +1485,7 @@
         "flag": domains.ObjType("flag", "flag", "target", "obj"),
         # types are objects that have a constructor and methods/attrs
         "type": domains.ObjType("type", "type", "obj"),
+        "typedef": domains.ObjType("typedef", "typedef", "type", "obj"),
     }
 
     # This controls:
@@ -1483,7 +1512,9 @@
         "function": _BzlFunction,
         "module-extension": _BzlModuleExtension,
         "provider": _BzlProvider,
+        "typedef": _BzlTypedef,
         "provider-field": _BzlProviderField,
+        "field": _BzlField,
         "repo-rule": _BzlRepositoryRule,
         "rule": _BzlRule,
         "tag-class": _BzlTagClass,
diff --git a/sphinxdocs/tests/proto_to_markdown/proto_to_markdown_test.py b/sphinxdocs/tests/proto_to_markdown/proto_to_markdown_test.py
index 3b664a5..7835d64 100644
--- a/sphinxdocs/tests/proto_to_markdown/proto_to_markdown_test.py
+++ b/sphinxdocs/tests/proto_to_markdown/proto_to_markdown_test.py
@@ -193,6 +193,22 @@
         self.assertIn('{default-value}`"@repo//pkg:file.bzl"`', actual)
         self.assertIn("{default-value}`'<function foo from //bar:baz.bzl>'", actual)
 
+    def test_render_typedefs(self):
+        proto_text = """
+file: "@repo//pkg:foo.bzl"
+func_info: { function_name: "Zeta.TYPEDEF" }
+func_info: { function_name: "Carl.TYPEDEF" }
+func_info: { function_name: "Carl.ns.Alpha.TYPEDEF" }
+func_info: { function_name: "Beta.TYPEDEF" }
+func_info: { function_name: "Beta.Sub.TYPEDEF" }
+"""
+        actual = self._render(proto_text)
+        self.assertIn("\n:::::::::::::{bzl:typedef} Beta\n", actual)
+        self.assertIn("\n::::::::::::{bzl:typedef} Beta.Sub\n", actual)
+        self.assertIn("\n:::::::::::::{bzl:typedef} Carl\n", actual)
+        self.assertIn("\n::::::::::::{bzl:typedef} Carl.ns.Alpha\n", actual)
+        self.assertIn("\n:::::::::::::{bzl:typedef} Zeta\n", actual)
+
 
 if __name__ == "__main__":
     absltest.main()
diff --git a/sphinxdocs/tests/sphinx_stardoc/BUILD.bazel b/sphinxdocs/tests/sphinx_stardoc/BUILD.bazel
index 3741e41..60a5e8d 100644
--- a/sphinxdocs/tests/sphinx_stardoc/BUILD.bazel
+++ b/sphinxdocs/tests/sphinx_stardoc/BUILD.bazel
@@ -42,7 +42,10 @@
 
 sphinx_stardocs(
     name = "simple_bzl_docs",
-    srcs = [":bzl_rule_bzl"],
+    srcs = [
+        ":bzl_rule_bzl",
+        ":bzl_typedef_bzl",
+    ],
     target_compatible_with = _TARGET_COMPATIBLE_WITH,
 )
 
@@ -76,6 +79,11 @@
     deps = [":func_and_providers_bzl"],
 )
 
+bzl_library(
+    name = "bzl_typedef_bzl",
+    srcs = ["bzl_typedef.bzl"],
+)
+
 sphinx_build_binary(
     name = "sphinx-build",
     tags = ["manual"],  # Only needed as part of sphinx doc building
diff --git a/sphinxdocs/tests/sphinx_stardoc/bzl_typedef.bzl b/sphinxdocs/tests/sphinx_stardoc/bzl_typedef.bzl
new file mode 100644
index 0000000..5afd0bf
--- /dev/null
+++ b/sphinxdocs/tests/sphinx_stardoc/bzl_typedef.bzl
@@ -0,0 +1,46 @@
+"""Module doc for bzl_typedef."""
+
+def _Square_typedef():
+    """Represents a square
+
+    :::{field} width
+    :type: int
+    The length of the sides
+    :::
+
+    """
+
+def _Square_new(width):
+    """Creates a square.
+
+    Args:
+        width: {type}`int` the side size
+
+    Returns:
+        {type}`Square`
+    """
+
+    # buildifier: disable=uninitialized
+    self = struct(
+        area = lambda *a, **k: _Square_area(self, *a, **k),
+        width = width,
+    )
+    return self
+
+def _Square_area(self):
+    """Tells the area
+
+    Args:
+        self: implicitly added
+
+    Returns:
+        {type}`int`
+    """
+    return self.width * self.width
+
+# buildifier: disable=name-conventions
+Square = struct(
+    TYPEDEF = _Square_typedef,
+    new = _Square_new,
+    area = _Square_area,
+)
diff --git a/sphinxdocs/tests/sphinx_stardoc/typedef.md b/sphinxdocs/tests/sphinx_stardoc/typedef.md
new file mode 100644
index 0000000..08c4aa2
--- /dev/null
+++ b/sphinxdocs/tests/sphinx_stardoc/typedef.md
@@ -0,0 +1,32 @@
+:::{default-domain} bzl
+:::
+
+:::{bzl:currentfile} //lang:typedef.bzl
+:::
+
+
+# Typedef
+
+below is a provider
+
+:::::::::{bzl:typedef} MyType
+
+my type doc
+
+:::{bzl:function} method(a, b)
+
+:arg a:
+  {type}`depset[str]`
+  arg a doc
+:arg b: ami2 doc
+  {type}`None | depset[File]`
+  arg b doc
+:::
+
+:::{bzl:field} field
+:type: str
+
+field doc
+:::
+
+:::::::::