References to other objects / local variable pointers

[nebkat]

I'm working with a format that has internal references to other objects based on their object IDs:

// Simplified
using ObjectId = u8;
using ReferencedObjectId = u8;
struct Object {
    ObjectId id;
    ReferencedObjectId referencedObjectId;
};

Object objects[while($ < std::mem::size())] @ 0x0;

01 04 // Object 1 => 4
04 03 // Object 4 => 3
03 01 // Object 3 => 1

I would like to have referencedObjectId be a link/reference to the appropriate object in the array, if found.

---

As a partial solution I have been able to hack together a way for the objects to have a pointer to other objects by doing the following:

g_objects[256];
fn get_object_ptr(u8 ptr) {
    return g_objects[ptr] - ptr; // Subtract ptr because it is about to be added to the base
}

using ObjectId = u8;
struct ReferencedObjectId {
    ObjectId id [[no_unique_address]];
    ObjectId *ptr : u16 [[pointer_base("get_object_ptr"), inline]];
};

struct Object {
    g_objects[std::mem::read_unsigned($, 1)] = $;
    ObjectId id;
    ReferencedObjectId referencedObjectId;
};

// First pass to build map
Object objectsFirstPass[while($ < std::mem::size())] @ 0x0 [[hidden]];

// Second pass
Object objects[while($ < std::mem::size())] @ 0x0;

The end result in terms of the pattern data is actually perfect but as you can see it's quite a horrible way to go about it.

---

Some possible solutions/improvements I have identified:

1. Allow local variable pointers: ObjectId *ptr : u16 = g_addresses[id];
2. Allow [[transform]] on pointers or [[pointer_transform]] in place of [[pointer_base]]
3. A reference data type (to map to other objects in the pattern data view)
4. A map data type (to avoid the large array)
5. A "lazy" mechanism that would evaluate a local variable after the initial pass, so that the objects array could be available for searching.

A combination of 3/4/5 (rather ambitious!) would allow:

struct ReferencedObjectId {
    ObjectId id;
    lazy Object reference = objects[id];
}

---

Is there some alternative way this can be achieved?

[paxcut]

why not simply use a pointer and addressof to point to that object?

struct Test<auto object> {
  Object *obj : u32 @ addressof(object);
};

you can also write your own pointer_base function to do anything you want and are not restricted to only use the ones provided. You may be making it more difficult that it needs to be. a pointer is just a variable that is interpreted as an address and you can always create local variables that hold values of addresses and can be used as part of a @ to access any other object.
EDIT:
As explained below that doesn't work because there is no data in the input file that holds the address you want to point to . You can create a section and write the address to it then place an object using Type val @ value in 0 to refer to the input file section id.

[paxcut]

That was wrong as it uses the contents of the thing you want a point to as an address so it goes to the worng place. This works though:

struct NewEntity {
    u32 uid;
};

NewEntity ne @0;

struct Test<T, auto object> {
   T ptr @ addressof(object);
};

Test<NewEntity,ne> t@10;

[paxcut]

If you are really bent on using pointers here is one way to obtain the reference. The trick is to use the pointer base function to subtract whatever value we assigned the pointer to be at (in this case zero) and add the actual address of the object.

struct NewEntity {
    u32 uid;
};

NewEntity ne @10;

struct Test<T, auto object> {
  
   T *ptr : u32 @ 0 [[pointer_base("point_to_object")]]; 
};

fn point_to_object(auto v) {
  return  addressof(object)-v;
};

Test<NewEntity,ne> t@0;

ptr then becomes a pointer to an object of type T that is located at the address where object is located at. The addresses chosen to place the pointer and to place the struct that holds the pointer are arbitrary. Sorry about all the consecutive posts,

[nebkat]

why not simply use a pointer and addressof to point to that object?

Well I didn't realize that was possible, seems obvious in hindsight... thank you 😅

That simplifies my existing solution to a more palatable:

// TYPO in the original, u16 was missing here - these are addresses:
u16 g_objects[256];

using ObjectId = u8;
struct ReferencedObjectId {
    ObjectId id;
    ObjectId ptr @ g_objects[id];
};

struct Object {
    ObjectId id;
    ReferencedObjectId referencedObjectId;
    g_objects[id] = addressof(this);
};

// First pass to build map
Object objectsFirstPass[while($ < std::mem::size())] @ 0x0 [[hidden]];

// Second pass
Object objects[while($ < std::mem::size())] @ 0x0;

That said I suppose the original suggestions remain valid - pointer variables display slightly differently to placed variables so it would be nice to have the ability to define them as local variables. It makes the indirection more explicit and is good for validating pointer arithmetic by seeing the computed pointer in the value column.

If you are really bent on using pointers here is one way to obtain the reference.

fn point_to_object(auto v) {
 return  addressof(object)-v;
};

This is the same idea as my original get_obj_ptr.

In reality my Objects are much more complicated than the example and can include circular references which is why I have to avoid actually instantiating the object. That was what brought me to the idea of references to existing variables.

They are also stored in a single top level array so I can't pass them as NTTPs, but that is probably a reasonable limitation of the system.

[paxcut]

If instantiation can lead to circular references then referencing variables will have the same problem because you need instances to create references and the references will also become circular. The way to avoid circular references is by building a hierarchy of references that ensure you can't link children back to parents. Storing them as arrays doesn't implied they can't be passed as template arguments (I assume thats what you mean since im not aware of the meaning for NTTP's) .

If you need pointers use the pointer_base function. That is in effect creating the references that you seek.When creating references of references the possibility if circularity always exists but that is a separate issue that is not related to the creation of references per se. Any new method created to implement thew references will also have the same potential problem with circular referencing.

[nebkat]

If instantiation can lead to circular references then referencing variables will have the same problem because you need instances to create references and the references will also become circular.

That is what had brought me to the idea of "lazy" variables that are evaluated as required in the pattern data view after the initial pass. At that point the global objects array would be fully initialized and could then simply be searched for the object with corresponding ID.

The "references" would have an arrow that brings you to the item in the pattern data view.

But again to be clear I am aware that is a huge request!

Storing them as arrays doesn't implied they can't be passed as template arguments (I assume thats what you mean since im not aware of the meaning for NTTP's) .

I'm referring to:

struct Object {
    ...
    // * Can't access `objects` here while we are constructing it, even if there were only references/pointers to previously processed entries that are already present *
}

Object objects[while($ < std::mem::size())];

If you need pointers use the pointer_base function.

Just for arguments sake (not relevant to my format) how would one implement a format with tagged pointers? e.g. It's known that the pointer will be 4-byte aligned so the lower 2-bits can be used to store other fields. Or perhaps more unorthodox a 256-aligned pointer where the lower byte could be dropped entirely.

A [[pointer_transform("...")]] function would be useful here to mask/shift the pointer instead of changing the base to some arbitrary number to make it work.

[paxcut]

If circular references are created, they will be made inside the array of pointers, so delaying evaluation doesn't solve the problem. You need to analyze the pointers to eliminate all possible loops. You can do the analysis on the fly so there is no need to do two passes. as you create the pointers, you make sure you don't revisit ones that were created already on their respective branches.

I don't see why you cant create the references as you are reading the data since all you need is the address of thething you want to reference. placing the pointer does not actually read the data, it only reads the address.
As an example of what i mean consider the following simplified version of your partial solution. Using the pointer base is fine, but what isn't is how the data is being manipulated when it can be done all while the data is being read

import std.io;
import std.mem;

using ObjectId = u8;

struct ReferencedObjectId {
    ObjectId * ptr : u8 @ addressof(parent) [[pointer_base("as_reference_to_parent")]];
};

fn as_reference_to_parent(auto ptr) {
  return addressof(parent.parent.parent) - ptr;
};

struct Object {
    ObjectId id;
    ReferencedObjectId referencedObjectId;
};

Object objects[while(!std::mem::eof())] @ 0x0;

I understand this is simplified, but the same process should be applicable to more complicated cases because there are no constrains that are imposed by the procedure. The reference and the original data occupy the same space so there is no need to go back and forth. (BTW if you are wondering the reason why three parents are needed is because of a bug that adds scopes when creating attributes but when fixed it would work with just one parent.)

Finally for the last argument about transforming the pointer instead of returning the base. From a computational point of view both are equivalent and equipotent. the base approach returns a number that when added to the pointer value it results in the desired final address. Transforming the pointer does the exact same thing, only it doesn't have the extra addition but in general if the pointer transform wants the address to become x then the base pointer approach can achieve this by returning x-ptr. All the computations that you do to obtain x from ptr will done exactly the same way but you would return x-ptr instead of x. From the way pointers are used in machine code it makes more sense to use a base approach than returning the value directly because more often than not, pointers are alays treated as relative to some base.

[nebkat]

Maybe I have not explained this clearly enough - there are no actual pointers in this data format.

There are N objects stored sequentially in a file each identified identified by an ID: a random but unique number. The objects contain other fields, such as a string name and variable length data.

Some of the objects have a field which references other objects by their ID. Circular references are not a problem because the actual program consuming the format simply stores all the objects in a map in a first pass, after which it can access map[referencedObjectId].name as needed. The referenced objects may be anywhere in the file, both before and after the current object.

struct Object {
    u8 id;
    char name[32];
    u8 referencedId;
    u32 length;
    u8 data[length];
}

Within ImHex I can easily perform that first pass and show the IDs of the objects being referenced. But to save the user having to manually find the referenced object I am trying to give them a shortcut to the object.

I can start by maintaining a map of object IDs to their respective addresses, and later reference this in a second pass.

However, whether I use variable placement or pointers, I cannot use Object as the pointee type as that would then kick off potentially infinite recursion if two objects reference each other.

Even if infinite recursion was not a problem, the intention is not for the user to explore the tree of objects by descending deeper and deeper into nested items - I simply want to link to the existing top level item in the pattern data view, similar to how the actual program does it. This is what delaying execution would allow for.

What I have settled on for now as in your example is pointing to the object ID instead of the object itself, which is better than nothing, but it still doesn't let the user jump to the entry in the pattern data view to explore further.

From a computational point of view both are equivalent and equipotent.

I say this purely from an ergonomics perspective, while those kind of pointers are no doubt rare they do exist and having to juggle the pointer base like that seems unnecessary.