Why isn't this just a func?

Oops. It's a draft for a reason. ;)

Nice, could use this for postorderTraversal as well. Should have documentation if we decide to export it though, otherwise there is no point?

Nit: should this be SkipFn instead to distinguish from an interface?

I think the semantics should be: if cmp == nil we default to an exported function that does what you call binary equivalency. Otherwise we defer to cmp entirely.

That way we could use this function to replace coreAreTypesCompatible which has a completely different notion of equality.

This is missing a check for !at.Empty() || !bt.Empty(), see coreAreTypesCompatible.

I think pre-order traversal is better here: https://en.wikipedia.org/wiki/Tree_traversal#Data_structures_for_tree_traversal It would mean we fail faster when there is a difference. The implementation of preorder can also be faster since it doesn't need as much temporary storage.

Oh absolutely, postorder is much too expensive for this. I initially tried comparing all vmlinux' types against themselves, and that didn't finish within 5 minutes or so. Preorder doesn't require any allocs except for the iterator that has some scratch space, and as you mentioned, would allow us to bail out much sooner.

"binary equivalency" is not really self explanatory.

Agreed, I think 'layout' should be the term used.

Allowing skipping like this is dangerous, I think. postorderTraversal flattens a graph into a list, so we lose the shape of the graph. This is okay (I think, need to convince myself of that again) as long as we always proceed in lockstep, consuming one type from each list. This skipping breaks that invariant so I think you can end up comparing types from different branches of a type.

All valid concerns indeed, and of course skips need to be used with care, that's somewhat self-explanatory.

The hierarchies are indeed flattened, but a and b are flattened the exact same way, and the same skip() is executed on both of them. At some point the comparison will converge on a complex (struct/union/func) parent node. If either side skipped a whole branch, one side will still be evaluating the branch while the other hits the parent, and a mismatch will occur.

I don't think this is a huge concern as it will flag a mismatch at some point, but it does call into question the usefulness of skipping anything other than qualifiers and typedefs. At worst the output will be inaccurate.

The hierarchies are indeed flattened, but a and b are flattened the exact same way [...]. If either side skipped a whole branch, one side will still be evaluating the branch while the other hits the parent, and a mismatch will occur.

I had something like these types in mind. Would this mechanism still work for them? I'm kinda sceptical (and now think that the CO-RE logic is buggy because of this).

struct {
  a struct{}
  b int
  c int
}

struct {
  a struct {
    b int
    c int
  }
}

and the same skip() is executed on both of them.

That assumes that skip is a pure function. I've already been bitten by that not being true when using postorderTraversal in the Spec.Add PR, and I wrote that code!

but it does call into question the usefulness of skipping anything other than qualifiers and typedefs.

Yes, indeed. However, I seem to remember a case where I wanted to skip only qualifiers and not typedefs though (GoFormatter maybe?) That implies that just a skip bool doesn't cut it.

That implies that just a skip bool doesn't cut it.

Totally, just being devil's advocate. Equal() should always take some form of function for maximum flexibility and composability.

Would this mechanism still work for them? [..example..]

With the current PR, this should flatten both hierarchies into [c, b, a, <parent struct>], and both legs will visit them in the same order.

c and b will indeed match, even though they're not at the same level in the hierarchy. a will not match because the left side has 0 members and the right side has two members. Likewise, <parent struct> has 3 members on the left and 1 member on the right, so won't match either. See what I mean? Even though the flattened hierarchy may overlap in some sections, their branch nodes (structs/unions) need to appear at the same index and must have the same type and amount of members.

I'm sure you could come up with an example that does make this fall over, though. :)

IMO this should be deferred to cmp. Maybe even the a == b == nil case.

Nit: skip the comment, it applies to Pointer, Const, etc. as well.

I think this should always be false, because walkType never recurses into a cycle.