This is something that I'd implicitly assume to be true for such a type. I think that asserting it once in the definition of SubAssemblyID would be enough:

static_assert(std::numeric_limits<value_type>::max() <= std::numeric_limits<size_t>::max());

Also, isn't uint64_t implicitly convertible to size_t? You have static casts to size_t all over the place and I think they're not necessary.

This will fail for emscripten, as there size_t is 32 bits. :)

This assembling code would be more concise if we defined a conversion method in SubAssemblyID() that does the cast and asserts that the value is in the range of the value_type.

We could then use that in several other places, e.g. CompilerContext.h or EthAssemblyAdapter.cpp.

BTW, almost all of these assertThrow()s should really be solAssert()s. The few that do represent proper validations should be replaced with solRequire().

I'd recommend converting any of them that you touch in your PRs.

if we defined a conversion method

I have added a conversion constructor, that is indeed a good idea, makes the code much more readable and the assertions more concentrated in the place where they're needed.

almost all of these assertThrow()s should really be solAssert()s.

Right, solAssert and/or solRequire is also much easier to digest than assertThrow

Wait, isn't this an ID rather than an index? You're iterating a vector of SubAssemblyIDs.
Though I also see that it gets cast size_t without extracting the .value. Why does that even work?

This would be much clearer without auto obscuring the type.

You also have some other loops using size_t subIDIndex where just using SubAssemblyID for the counter would make things simpler. E.g. in optimiseInternal() I think you could just do this:

for (SubAssemblyID subID = 0; subID.value < m_subs.size(); ++subID.value)

It works because you can unpack structs much like tuples, auto [subIDIndex] = subIDs.front() already refers to the contained value member. Although subIDIndex was not a good name, should have been subIDValue.

In any case, I have changed the loop now to just iterate over the SubAssemblyID instances instead of contained members and then extract the index with a new asIndex method that does static casting and size checking if needed. As an added benefit it limits the amount of static casts being littered about.

Is this assert correct? I think it will fail when _subID is zero, but zero is a valid ID and an empty one is represented with max() instead. The message indicates that the function considers max() to be set and 0 to be unset, which does not seem right.

Also, now that the sub ID is well-defined as 64-bits, I think we should have asserts that the upper bits of data are actually zeros.

Is this assert correct? I think it will fail when _subID is zero, but zero is a valid ID and an empty one is represented with max() instead. The message indicates that the function considers max() to be set and 0 to be unset, which does not seem right.

You are not the only whose head hurts by this stuff :) the condition data() < (u256(1) << 64) checks just if data() fits into 64 bits, as we have

u256(std::numeric_limits<uint64_t>::max()) + 1 == (u256(1) << 64)

So it would pass if data() is zero and it indeed already asserts that the upper bits are zero. Or am I misunderstanding your concern?

Oh, it's the first time I see assemblies referred to as subroutines. It really stretches the definition. From Wikipedia:

In computer programming, a function (also procedure, method, subroutine, routine, or subprogram) is a callable unit[1] of software logic that has a well-defined interface and behavior and can be invoked multiple times.

It's going to become very confusing with EOF, where we have both functions (code sections) and assemblies (containers). I'd by default interpret "subroutine" to mean to former (there was even a competing "simple subroutines" EIP). We should really rename this at some point.

Ugh, I thought I understood what's happening and then I ran into this. WTF are we doing? It just makes my head hurt. If I understand correctly:

• Assembly keeps track of chunks of data and subassemblies separately.
  • Assemblies are stored in m_subs vector.
  • Data is stored by hash in m_data.
    • Except for metadata, which is singled out and stored in m_auxiliaryData.
• EthAssemblyAdapter holds the assembly and independently keeps track of all the appended data chunks in m_dataHashBySubId.
  • It gives them fake IDs in the upper half of the subassembly ID space
• When a Yul object is being compiled, EVMObjectCompiler adds subassemblies and data chunks via the adapter, receiving both real and fake IDs.
  • It stores the IDs in BuiltinContext, each one associated with a Yul node by name.
  • This is done only for children of the object. Anything nested deeper does not get an ID.
• BuiltinContext is passed to Yul code transform and later to builtins defined in EVMDialect.
  • Builtins like datasize then use BuiltinContext to map Yul node names to sub IDs.
    • If the name is present in BuiltinContext, they take the ID stored there.
    • If not, they assume the name is a dotted path and convert it to a sequence of IDs.
      • BTW, this is a pretty questionable assumption: #13794, #15540.
    • In either case the sequence is passed into EthAssemblyAdapter::appendDataSize().
      • It assumes that if the first ID in the sequence is present in m_dataHashBySubId, it must be a fake ID assigned to a data chunk.
      • Otherwise it converts the path to a sub ID using Assembly::encodeSubPath() and assumes it must be a subassembly.
        • There seems to be an assumption that Yul Object tree structure matches the Assembly tree, which I'm not sure is true. For example we sometimes we move things (e.g. long Yul strings) to data chunks and the transition happens in evmasm optimizer, which means that they do not have corresponding data nodes at Yul level.
      • I actually don't understand how paths to nested data are handled. I don't think they're are added to BuiltinContext, but then how do they not end up treated as assemblies by appendDataSize()?

Overall, looks like we have several kinds of sub IDs sharing the same ID space, without any checks for conflicts (just assuming the space is large enough that they won't happen):

• Normal IDs assigned to subassemblies, starting at 0.
  • EOF ContainerIDs are a subset of this and are limited to uint8_t.
• Empty ID at max().
• Fake data IDs starting at max() / 2.
• "Negative" IDs representing deeply nested paths, starting at max() and going down.

I think we should assign a non-overlapping region to each of them and have asserts enforcing that.

The way we assign IDs should also be more prominently documented. For example m_subPaths does not even say that the "negative" IDs mean.

Sounds like a good idea to define non-overlapping regions. That way each of the regions can also be independently and cleanly documented. Perhaps in a follow up?
Regarding documenting subpaths and negative IDs: @r0qs had written something up about it and iirc wanted to add it in some form to the documentation.

Sounds like a good idea to define non-overlapping regions. That way each of the regions can also be independently and cleanly documented. Perhaps in a follow up? Regarding documenting subpaths and negative IDs: @r0qs had written something up about it and iirc wanted to add it in some form to the documentation.

Yes, it is here: https://github.com/ethereum/solidity/wiki/Assembly-Indices

We use size_t for tag ID but that should really be uint64_t as well. Would be nice to change that too at some point.

The tag+sub pair would also be better off as a proper struct with methods for converting to/from u256. We wouldn't then have to hard-code all those masks and 64s all over the place.

Agree, it would also make it easier to reason about the whole program and data flow.