Extension structs can't be chained

[Ralith]

When a struct has a p_next member, there may be a set of structs that can be pointed to with it to access extended functionality. This is currently gracefully supported by builders. However, those structs can be chained: If Foo and Bar both extend Baz, then a Baz -> Foo -> Bar chain of p_next references is legal, even though Bar does not extend Foo. We should find a way to support this.

My first idea was to replace FooNext and BarNext with BazNext, but some extension structs (e.g. VkPhysicalDeviceVariablePointerFeatures) extend multiple structs, so there would be no correct single trait to replace their extension traits with. Another approach is to compute the union of legal extensions for every extended struct type, but this would cause a quadratic increase in generated code for every new extension struct.

Worst-case scenario, we can fall back on fn next<T>(self, &'a T) without any typechecking at all. Validation layers should do a decent job of checking these, after all.

[MatusT]

I have an alternative idea for the next function which, however, may introduce a run-time penalty. The next function would be the same for every struct with p_next and It would simply iterate through p_next linked list to the end and append:

pub fn next<T>(mut self, append: &'a mut T) {
  current = self.inner.p_next;
  while(current.p_next != null) { current = current.p_next }
  current.p_next = append;
}

[Ralith]

With self: Foo and T: ExtendsFoo? That's a pretty cool idea. I wouldn't be surprised if it optimized well, either.

[MaikKlein]

This has been fixed for a while now. We decided on fn next<T>(self, &'a T) without any type checking.

[MaikKlein]

@Ralith This is just about this issue. I am generally not happy about how we handle p_next in ash and I am still looking for a better solution.

[Ralith]

I don't think that's true. The generator is still using the original trait bounds. I think @MatusT's proposal is likely the right way to go here.

[MaikKlein]

Oops you are right my bad, I did not notice the where bounds in docs.rs. I might find time to implement it next week, at the latest in two weeks.

[MaikKlein]

I just had a quick look at it.

We can't just iterate over the chains and update them. pNext is usually *const. Unless I am mistaken if we want to update the last pointer, it has to be *mut.

Maybe it is okay to just cast if we always borrow as &mut T. It might be okay because we have an explicit lifetime on that borrow.

[Ralith]

If fn next always takes &mut T then that should be correct, yeah. I think your idea of prepending instead of appending is a great one anyway, since it skips the loop. I don't think order usually matters, though it might for cases where T extends U and U extends V but T does not extend V, but prepending supports those cases fine, docs will just need to be clear.

[MaikKlein]

I now have some time to address this issue. I had another look at it and I think we should tackle it differently.

As you said there can be multiple extends.

        <type category="struct" name="VkPhysicalDeviceVariablePointerFeatures" structextends="VkPhysicalDeviceFeatures2,VkDeviceCreateInfo">
            <member values="VK_STRUCTURE_TYPE_PHYSICAL_DEVICE_VARIABLE_POINTER_FEATURES"><type>VkStructureType</type> <name>sType</name></member>
            <member><type>void</type>*                            <name>pNext</name></member>
            <member><type>VkBool32</type>                         <name>variablePointersStorageBuffer</name></member>
            <member><type>VkBool32</type>                         <name>variablePointers</name></member>
        </type>

structextends="VkPhysicalDeviceFeatures2,VkDeviceCreateInfo"

While it is true that it can extend multiple things, in this case VkPhysicalDeviceFeatures2 also extends VkDeviceCreateInfo.

I think we only should create and implement traits for create infos like VkDeviceCreateInfo and so next for VkPhysicalDeviceFeatures2 would look like fn next<T: ExtendDeviceCreateInfo>(..).

It is just a bit harder to implement as we would have to find the out most create info, but even that shouldn't be too complicated.

[Ralith]

Are we certain that there are no, and never will be, cases where A extends B extends C, but A does not extend C?

[MaikKlein]

A extends B extends C, but A does not extend C

If that would be the case then C can't be used at all right? If A is the "root" create info from a function and if A points to B and the points to C, then surely C must be valid also valid for A. If that is not the case C could never be used.

The point chain is linear at one point you have to append another pointer chain.

A -> B -> D
A -> C -> E

A -> B -> D -> C -> E 
or
A -> C -> E -> B -> D

The vulkan spec is a bit vague with pnext.

I could only imagine

A extends B
A1 extends B extends C

And so C and only be used with A1 and not A, but I don't think we could encode this because we verify that for B and B can extend C it just can't be passed to a function that takes an A. Although I would be surprised if that would be in the API.

[Ralith]

If that would be the case then C can't be used at all right? If A is the "root" create info from a function and if A points to B and the points to C, then surely C must be valid also valid for A. If that is not the case C could never be used.

You've got it backwards; in that example, C is the root.

[MaikKlein]

You've got it backwards; in that example, C is the root.

Oops sorry, but the comment is still valid. You just have to swap A and C.

[Ralith]

I don't follow, then. If A extends B, then by definition B's pNext field can legally point to A, regardless of what B extends. That dosn't mean that A makes sense on its own as an extension for everything that B extends.

[MaikKlein]

I also had a look at how VulkanHpp does it

https://github.com/KhronosGroup/Vulkan-Hpp/blob/master/VulkanHppGenerator.cpp#L3946

  template <> struct isStructureChainValid<PhysicalDeviceFeatures2, PhysicalDeviceVariablePointerFeatures>{ enum { value = true }; };
  template <> struct isStructureChainValid<DeviceCreateInfo, PhysicalDeviceVariablePointerFeatures>{ enum { value = true }; };

And they validate it with

  template <typename List, typename X>
  struct extendCheck
  {
    static const bool valid = isStructureChainValid<typename List::last, X>::value || extendCheck<typename List::list,X>::valid;
  };

  template <typename T, typename X>
  struct extendCheck<TypeList<void,T>,X>
  {
    static const bool valid = isStructureChainValid<T, X>::value;
  };

  template <typename X>
  struct extendCheck<void,X>
  {
    static const bool valid = true;
  };

Are we certain that there are no, and never will be, cases where A extends B extends C, but A does not extend C?

Going back to you first comment

C -> B -> A would be valid, but C -> A -> B would not be. This is what you meant right?
The latter also doesn't compile with vulkan.hpp.

I just don't understand one aspect of it.

If

C extends B extends A
D extends A

Why would this then be valid? A -> B -> C -> D

I assume the rules are from right to left, (or down to up) I sort of expected that the order doesn't matter.

So A -> B -> C -> D would be valid because A can be reached from D.
Afaik the spec doesn't really say anything about this at all.

[Ralith]

I also had a look at how VulkanHpp does it

What is the contents of the type list in this example?

C -> B -> A would be valid, but C -> A -> B would not be. This is what you meant right?

I was hypothesizing a case where C -> B -> A is valid, but C -> A is not.

Why would this then be valid? A -> B -> C -> D

The rule that seems most obvious/natural to me is "extension structs must be preceded in a pNext chain by a struct that they extend". @MatusT's approach implements these semantics.

[MaikKlein]

The rule that seems most obvious/natural to me is "extension structs must be preceded in a pNext chain by a struct that they extend". @MatusT's approach implements these semantics.

I think I will just finish up #183 as it currently is. I'll also open an issue on the Vulkan docs, would be nice if this would be defined by the spec.

[MaikKlein]

KhronosGroup/Vulkan-Docs#929

The order doesn't matter, and A extends B extends C, but A does not extend C can not happen. There might be something if B is used then C can't be used, but we can not easily express it like this. We could do something similar like vulkanhpp Chain<(Foo, Bar, Baz)> but I am not a big fan on this.

I think my previous proposal is the best implementation, we don't have to iterate the chain and it is the most vulkan like implementation.

Invalid cases (which should be rare) can be caught by the validation layers.

[Ralith]

Nice research!

I think we should proceed with @MatusT's approach, modified to prepend rather than append so iteration is unneeded. If order explicitly doesn't matter this is fine, it avoids having to do any aggregation, and it gracefully handles the case where one struct can be used to extend two different root structs that do not share all their extensions. We can then disable generating ExtendsFoo traits for extension structs entirely.