UUIDs.. you know you want them

[monte]

Posting the UUID proposal discussed on the dev list here as it's a more open forum:

UUID proposal

For those that haven't been listening in on the lcVCS discussion there are many issues with LiveCode IDs that make them an unreliable solution for object references when merging stackfiles. They also happen to have significant namespace issues with referencing image IDs via icons. An example of this can be seen when using the icon picker in the IDE. Quite often the icons shown in the icon picker are not the right ones because they are out of context. There also must be other issues too because for some reason the revGeometry library uses a (fairly fragile) unique id based on the milliseconds but I haven't investigated why that was deemed necessary.

To cut a long story short I think we need to transition to a UUID rather than a sequential integer ID for our controls.

The current situation is stacks have objects with unique IDs in the scope of the stack. For a VCS we still don't need unique IDs of any greater scope than the stack. We don't care about ID collisions outside the stack scope but we do need to ensure there are no ID collisions when working on the same stack in a distributed environment. So the current IDs that the engine has assigned are all fine until we want to start working in a distributed way. At that point the problem is not the current IDs in the stack it's the new ones. So a scheme that changed the way that IDs were assigned to objects when they were created wouldn't need to change existing IDs.

This is all quite helpful because it would be very hard/impossible for us to create an ID scheme that was unique in a greater scope than the individual stack anyway because of the conundrum of what to do when a stack is cloned. Obviously there would be many properties that rely on the ID so just having the engine change all the IDs silently will break the cloned stack. So while UUIDs are globally unique we can only 100% reliably say that a rugged UUID will only ever refer to a single object in the stacks in memory.

All we need then is for ID to be upgraded to a 128 bit integer (which is what UUID is) and be generated using one of the UUID schemes moving forward. Then for convenience we could have ID object references accept either a UUID form or a number form of the same integer.

When getting ID object references we would either use some adjective to get the UUID form if we wanted that or the engine would just return the UUID form when we request IDs. I'm not convinced that anyone would have code that relies on the ID being returned as an integer so I'd prefer the latter because it would really deprecate integer IDs from the language but I've left the adjective in the code examples because I think it will be easier for people to swallow....

An example of how this would work for an object created before the change

Let's say card 1 of a stack is currently 1002.
After the change:
the ID of card 1 is 1002 is true
the unique ID of card 1 is 00000000-0000-0000-0000-0000000003EA is true
because baseConvert(1002,10,16) = 3EA

Also..
set the ID of card 1 to 00000000-0000-0000-0000-0000000003EA
the ID of card 1 is 1002 is true

And...
set the ID of card 1 to 1002
the unique ID of card 1 is 00000000-0000-0000-0000-0000000003EA is true

Now the above example is obviously not a real UUID but it really doesn't matter as long as everything works does it. Over time these legacy IDs fade into history but if a developer really wanted to clean them out of their stacks they could do so quite easily.

For objects created after the change

The object is assigned a globally unique ID using one of the UUID schemes when it's created so no matter how many developers are working in parallel on the same stack there won't be an ID collision.

[Mark]

Monte,

Somewhere hidden in the source there must be a way to generate UDID´s already but it isn't included in standalones IIRC. Did RunRev remove that? If not then I propose to make RunRev's approach available in standalones.

Mark

[mwieder]

Thanks, Monte. And the tl;dr is: IDs as they currently exist in LC aren't unique and this can cause conflicts. Allowing IDs to be changed was the first step in fixing this, and uuids are the next evolutionary step. This proposal allows for migration to unique IDs without breaking existing functionality.

[mwieder]

@Mark- these are UUIDs, not UDIDs. That's a different topic.

[monte]

Yes @Mark look for the generateUUID topic.

[malte]

As I suggested before. If we are moving to UUIDs (which I can only encourage), please let us not do it "half-assed". I am pretty sure there are OSS libraiers floating around that could be used.

Maybe something like this:

http://www.opensource.apple.com/source/ ... uuid.c?txt

?

Cheers,

Malte

[mwieder]

Malte - not to worry. The primary property of a uuid is that it's unique. Other than that, for all our purposes it's just an opaque number. We don't care about the content as long as there's no conflict with other 128-bit uuids. There are OSS libraries we could use, and there are also native libraries already existing in each OS. It shouldn't matter what route we take to get to the end result of having unique identifiers.

[malte]

Mark, while I agree that for Control IDs uniqueness is the highest priority, I still believe it would be good to support at least Type 3 and Type 4 UUIDs with Type 5 and Type 2 UUIDs being a bonus. While I have a working LiveCode solution to generate those I need, I would much prefer to have that in the engine to loose a couple of 100 lines of code in overhead and to gain some speed there. I really appreciate all the work you guys are doing, it is just that UUIDs are somewhat of a pet peeve of me

BTW: Will you be in Edinburgh for the Con this year?

Cheers,

Malte

[monte]

Are you saying the proposal is half-assed? I do think the backwards compatibility aspects of it are important.

We really need a cross platform lax licensed UUID lib and they seem hard to find. The boost one would be cross platform but runrevmark has ruled boost libraries out. Alternatively we can extend the existing uuid generation code that uses platform specific APIs.. not sure about JNI calls to generate an id for an object on android... obviously we need something really fast because when we are creating lots of objects on the fly we need high performance.... If you're just talking about having uuid generation in general then there's another topic on that. For the purposes of object ID I don't think we need to stress about type too much.. we should use whatever's fastest I think...

Now if you want a half-assed proposal then I have been considering lately that in the event of resistance to move to a 128 bit ID then perhaps generating our 32 bit one randomly could resolve the problem sufficiently. We would need to be comparing 77000 randomly generated 32 bit ints to get a 50% probability of a collision... The thing is we aren't creating that many ids (most of us aren't) on each branch of our stack file. There could be a lot of creation and deletion but the new objects created that actually get committed would on average be quite low numbers.... The other thing is if the random ID is generated and there's a collision in the current stackfile that's open then obviously the engine would silently generate a new ID... so we then only need to worry about collisions of new objects created on the branches being merged. Now if we are talking about less than 2900 new IDs from the two branches then that's less than .1% probability of a collision. That's perhaps low enough probability to just throw up a dialog saying the ID of object X has been regenerated and let the user sort it out....

If we could move to a 64 bit ID (which would be much simpler than a UUID) then all these numbers get significantly less risky...

[mwieder]

@Malte: Ah, yes, I'd forgotten you need the exact uuid types. Yes, it would be good if we could find compatibly-licensed uuid libraries for this. I forget why Mark ruled out the boost libraries... maybe we can lobby for those, or maybe something else is out there.

And yes, I'm leaving for Edinburgh in a week. And then a week in Karlsruhe/Heidelberg after the conference.

[mwieder]

Thinking this over, is there a reason *not* to use the native uuid libraries in the OS?

[monte]

Cool... looking forward to meeting you guys... perhaps we could discuss ID options and how to implement them in the engine workshops...

The native UUID libraries that _internal call "generateuuid" all seem to return different UUID types... so they aren't brilliant for what Malte wants to do but would be fine for the ID stuff... My main concern is speed... android in particular would need a JNI call but also doing stuff like getting the MAC address or reading /dev/random might noticeably slow down object creation which I don't think we can afford to do.

[monte]

Random number generation library which could be involved in the solution: http://randomlib.sourceforge.net

[mwieder]

Do we need this on mobile platforms? They're deploy-only platforms, so I don't think we need to generate uuids, just consume them.

[monte]

They need to create objects yes... if the engine assigns a uuid to an object as it creates them then it will need code to generate the uuid