Auto casting arguments using OverloadTree

[jitsedesmet]

With the newly added (#101 ) OverloadTree we can enable auto casting like talked about in #94. I create this new issue because #94 is getting a little big and would get much bigger. I'll link some of the, in my opinion, most relevant comments for this issue from #94 here.

• Auto casting idea: Enable no-redeclare rule #94 (comment) and Enable no-redeclare rule #94 (comment)
• Needing depth first search: Enable no-redeclare rule #94 (comment)
• There's some talk about what types should be handled by auto casting. A clear scheme should be created for this. Once the scheme is ready I will link it in here.
• Rewriting builder: Rewrite/overloadmap as tree #101 (comment)

When using auto cast, it could happen that searching an overload operation is pretty expensive. The chosen overload for a given array of arguments will never change however. Each node could have some kind of cache to keep the already calculated searchStack in. This cache would make sparqlee have a global state. We want to take control over that state so when implementing the cache, we should provide functions to reset and maybe set the cache status. A package that could be used for this is: https://www.npmjs.com/package/lru-cache

If I forgot something, please add it in the comments. The issue became kinda big to keep track of 😅

[rubensworks]

👍

This cache would make sparqlee have a global state. We want to take control over that state so when implementing the cache, we should provide functions to reset and maybe set the cache status. A package that could be used for this is: https://www.npmjs.com/package/lru-cache

For this, I would recommend allowing this cache to be retrieved from the evaluator, so it can be reused in other evaluators by passing it into *EvaluatorConfig.

[wschella]

If we can use a cache, why don't we just precompute? If we do the cache with ArgumentType[] as keys, we're back at the OverloadMap that was not a tree but a HashMap (and you need array equality again), with the difference being that the map now might incomplete (and thus smaller).

So the question/tradeoff for me is: you can generate this 'cache' in advance for all types, but it's a combinatorial explosion of entries in the map (i.e. use the tree only as an intermediate representation, and flatten it). Might that be worth it (a bit more memory, but O(1) lookups)? I don't really know. The cache might hit a good sweet spot.

I also think the lookup in the tree is quite cheap, and it might be improved a bit still. So implementing a cache might be overkill to start with. Especially if it's configurable, as that would require exposing our internal implementations for all functions!

Also let's get terminology straight first, there are at least 2 distinct cases (that I know of):

• Type promotion Implement Type Promotion #12 (https://www.w3.org/TR/xpath-31/#promotion)
• Subtype substitution Implement Subtype Substitution  #13 (https://www.w3.org/TR/xpath-31/#dt-subtype-substitution)
• Possible also Implement automatic type casting for xs:untypedAtomic  comunica#1253 (which I don't understand very well)

We can refer to all of these generally as auto-casting, but they're distinct cases w.r.t. to their type relations! I think this is the moment to fix all these things completely.

[rubensworks]

Might that be worth it (a bit more memory, but O(1) lookups)? I don't really know. The cache might hit a good sweet spot.

Yeah, I also don't know. It may be worth it to precompute.
If we start with the cache solution, we could run benchmarks with different cache sizes and compare with precompution.
If memory is manageable with precomputing, we could still go for that option afterwards.

[wschella]

Thinking a bit more on it, another argument against precompute is that might add a non-negligible overhead to the initialization phase that will not matter for most expressions. You save no time by doing precomputation, you just move it from the moment of first lookup to all computations in advance, which is possibly a big waste, and really only advantageous if you can do it when you're waiting for e.g. IO.

Thus: we can consider the cache more like a lazy computation approach. You can argue that when you have a cache with unlimited size, you do no extra computations, and you only do them when it's needed. (I think there's little reason to limit the cache size).

Conclusion: I'm fan of the cache! (especially as the different Bindings in a stream will have likely have very similar types)

[jitsedesmet]

I'm glad you like the cache idea. I have a few question about what you said.
What doe you mean with

Especially if it's configurable, as that would require exposing our internal implementations for all functions!

I also want to clarify that the a cache item would (partly) be identified by the node. There would not be any reason to keep a list in the cache like we did with the OverloadMap.

You also said:

I think this is the moment to fix all these things completely.

Is it good if I look at these issues after the first PR handling what I meant with auto-cast is done? (That PR will be big enough on itself :) )

[jitsedesmet]

EDIT: This comment contains false information!

@wschella pointed out

Type promotion Implement Type Promotion #12 (https://www.w3.org/TR/xpath-31/#promotion)

It should be noted that we can easily implement this behavior in #103 , we would just need to edit the extensionTableInput a little bit.

[wschella]

I'm glad you like the cache idea. I have a few question about what you said.
What doe you mean with

Especially if it's configurable, as that would require exposing our internal implementations for all functions!

How do you let someone add cache entries without giving access to the possible values (i.e. our function implementations)? But I think I have understood wrongly, I believe the idea actually is just to copy the cache from one evaluator to the next?

I also want to clarify that the a cache item would (partly) be identified by the node. There would not be any reason to keep a list in the cache like we did with the OverloadMap.

Okay, but a cache is a (key, value) store. What are the keys? I believe ArgumentType[], since that's what coming in at runtime? The whole point of the OverloadTree is to associate ArgumentType[] with one of it's nodes (and mostly a specific implementation), so how could you use the Node as a key, if you have only have access to ArgumentType[]?

I think this is the moment to fix all these things completely.

Is it good if I look at these issues after the first PR handling what I meant with auto-cast is done? (That PR will be big enough on itself :) )

The problem is I'm not sure what you mean with auto-casting right now! I think it's actually #13 ? So it might be worth checking these out (the first 2), just to have a more formal framework to reason in.

[rubensworks]

I believe the idea actually is just to copy the cache from one evaluator to the next?

Indeed. No need for external modification of the cache I think.

[jitsedesmet]

I believe the idea actually is just to copy the cache from one evaluator to the next?

Yes

Okay, but a cache is a (key, value) store. What are the keys?

I'm thinking about making the Tree know what function (as a string name) it represents calling this name.
This is where things get fuzzy. And should be discussed.

1. We give each node an index (those indices would be easy to handle and not change) we could then identify a node in the tree by it's name in combination with the path taken so think of something like '+11'. Tree for the '+' operator and you take the first path twice. This would allow us to speed up the getSubTreeWithArg function. The time we spend search would not change however. Just the time spend in each node.
2. We try to cache the search function instead. We could do this by mapping the args with something like

args.map(arg => arg.termType === 'literal' ? (<E.Literal<any>> arg).type : arg.termType).join('');

This would make one long string we can use as a key. This string would then be:

const key = this.functionName + args.map(arg => arg.termType === 'literal' ? (<E.Literal<any>> arg).type : arg.termType).join('');

It is extremely possible that there is another solution but this already gives some idea as to where I would go with this. Some food fo thought. 😄

I think it's actually #13 ?

I think so too.

[jitsedesmet]

Reading https://www.w3.org/TR/xpath-31/#promotion it says:

A function that expects a parameter $p of type xs:float can be invoked with a value of type xs:decimal. This is an example of type promotion. The value is actually converted to the expected type. Within the body of the function, $p instance of xs:decimal returns false.

So what we did with being able to give XSD_ANY_URI to XSD_STRING is wrong. We also previously just did this internal conversion even when not needed.

I have but 1 idea on how to fix this problem properly (if it's even possible to make these casts)
When adding a function that takes XSD_STRING to a tree, it will also add a function that takes XSD_ANY_URI but will alter it's imlementation in a way that before calling the provided implementation it will cast its argument of XSD_ANY_URI to `XSD_STRING

[rubensworks]

So what we did with being able to give XSD_ANY_URI to XSD_STRING is wrong. We also previously just did this internal conversion even when not needed.

Not sure I understand the problem.

I see this being mentioned in the spec (https://www.w3.org/TR/xpath-31/#promotion):

URI type promotion: A value of type xs:anyURI (or any type derived by restriction from xs:anyURI) can be promoted to the type xs:string. The result of this promotion is created by casting the original value to the type xs:string.

So that's exactly what we're trying to achieve, right?

[jitsedesmet]

Yes, but it's not what #103 does right now. Right now it will keep the type XSD_ANY_URI but it will be provided to a function expecting XSD_STRING what we should do is first change it's type before providing it to that function.

[rubensworks]

Right now it will keep the type XSD_ANY_URI but it will be provided to a function expecting XSD_STRING what we should do is first change it's type before providing it to that function.

The type change you're talking about, isn't this something we need to do in all cases?

[jitsedesmet]

That's not how I understand https://www.w3.org/TR/xpath-31/#dt-subtype-substitution . It says:

Subtype substitution does not change the actual type of a value.

[rubensworks]

Then I don't know what is supposed to happen 🤷
My knowledge is limited to the SPARQL spec, I don't know that much of XPath...

[wschella]

Responding on #102 (comment), regarding caching architecture.

1. If we speed up the time we spend in each node I wouldn't call it casting. I don't think I really understand what you are proposing now, but I do believe there is room for improvement that is not cache based (but just encodes the relations better statically). It might be worth experimenting going full recursive instead of working with the search stack as well.
2. So for an actual cache what you proposed in point 2 makes sense. In my head, the cache was per function (replaces a concat of the function name with an object lookup). This might be annoying with cache sizes tho. But I don't actually think it makes sense to limit the cache size (it can not grow infinite, and if the user's datatypes are all different, it will be worth it). I think we should consider it a lazy computation.

Now, I have another idea entirely for the cache (i.e. the lazy computation): we also make it a tree.
The reason we don't precompute the OverloadTree with all posibilities of concrete types is because the relations between arity, subtypes, promotions, etc. make the combinations explode categorically and they won't be used that often. Now, every combination that does occur is one worth saving.

So imagine you have a certain call f_a(type1, type2, type3). You look up the correct implementation, and create a path in the cache: {f_1: { type1: {type2: {type3: implementation}}. The next time you have these exact types, you can find it in the cache in arity x object lookups (vs arity x string concats + 1 lookup), which I think will be faster. But now you think: @wschella this is stupid, this means you're just back at depth first searching because you can have partial matches! Yes exactly, but we can solve this cleanly: we could keep this cache in the overload tree, i.e. the path I described is now added, giving the same combination of types a fast path in the tree, since we need to check for concrete type matches at each node anyway (see [1]).

A cache to copy from an other evaluator is just a tree to be merged then. This embodies the idea that we just lazily compute the OverloadTree. The tree that we have now is just the minimal representation, and each concrete type lookup adds a fast path. This also makes "precomputation" a spectrum, we could choose to add these fast paths for certain type & function combinations we now to occur a lot, but are not in the minimal tree.

Opinions? If this is what you meant in point 1, please forgive me ^^

[1] For search, I believe this is the order to be respected at each node:

• concrete type match
• subtype substitution on concrete types (i.e. byte to int)
• type promotion (taking into account subtypes, i.e. float to double)
• subtype subsitution on abstract types (i.e. int to literal, "numeric", term)

Do you think this is correct?

[jitsedesmet]

My opinions on this:

It might be worth experimenting going full recursive instead of working with the search stack as well.

I think an array we edit our self will be much faster (so what we have now). We never copy the array? This is an ideal search strategy?

Now, every combination that does occur is one worth saving.

Yes exactly! That's what the idea for the caches is. I think we mean the same things but just give them different names. I would keep using the cache system just because it enables some control over the resources. This can be a very good thing to have?

I like the name fast path and the way you would go about indexing the tree ({f_1: { type1: {type2: {type3: implementation}}.).

I don't really understand the last order you mention but I think that doesn't matter as much?
A fast path would be indexed by the most concrete type to not overload the tree and not to make it unnecessarily complex. For a given evaluator I think the provided types will mostly be the same? No need to make this so complicated no one would understand.

[wschella]

I think an array we edit our self will be much faster (so what we have now). We never copy the array? This is an ideal search strategy?

True, I was mistaken in thinking that .search was still implemented partly recursive.

I don't really understand the last order you mention but I think that doesn't matter as much?

The order I mention there defines which implementation we should prefer. If multiple match: i.e. a definition for f(byte) is prefered over f(term) if the arg has the type byte.

And just to be sure that we are on the same page, in my head:

• there is no separate data structure for the fast path/cache/lazy computation, it's just another entry in the subtrees of a node, always with a concrete type as key.
• the main point is to avoid expensive operations (like sorting), if that's not possible, we might have to think on the idea again

[jitsedesmet]

the main point is to avoid expensive operations (like sorting), if that's not possible, we might have to think on the idea again

Absolutely and also avoiding the depth first search of course.

here is no separate data structure for the fast path/cache/lazy computation,

I see where you're coming from. I first thought the same thing. However, @rubensworks pointed out that it is importend to be able to reset these fast paths. Implementing fast paths would create a global state. We need to have absolute control over this state. I would give this control by making a cache a separate data structure that could be provided to the search function (or some other access point in that vicinity)

[wschella]

Why do you want to reset the fast paths?

[jitsedesmet]

Mainly for test purposes and control over the state. reproducibility

[wschella]

If your cache is a separate data structure, you need depth first search again[1], and when you find now match you now must start again from the beginning in the OverloadTree.

What I do understand is a need to have a separate tree instance for each evaluator, but this can be the same data structure, with the same logic. But this can be solved by just copying the tree[2], which is then done for each evaluator. All state can be reset by making a new evaluator. I don't see the need for more fine grained control?

[1] Because you can have partial matches (i.e. a cache hit for the first 2 arguments, but not the third). Although it's a lot faster, cause there's no need to handle subtype substitution and promotion and such, but still.
[2] It's not exactly copying the tree, it's copying the function definitions constructed in lib/functions/index (which contain the OverloadTrees).

[jitsedesmet]

If a full match is not made, we need to do the complete search! We can not cut off the first 2. The same reason we need DFS in the first place.

What I do understand is a need to have a separate tree instance for each evaluator,

We could do that but I thought you weren't a fan of making the complete path from evaluator to overloadTree class based?

Anyway. I think you're approach is a little complicated? Might be because I don't understand it?
Anyway, I'm gonna leave this cache thing be what it is for now. The casting itself is the priority and will be a big shift. I think all we be clearer once the current PR is done. :)

[wschella]

If a full match is not made, we need to do the complete search! We can not cut off the first 2. The same reason we need DFS in the first place.

With a separate datastructure, you need 2 complete searches! While in the overload tree, the fast path is just the first option considered, if it fails, search resumes as it normally would. E.g. if you have 2 matches with concrete types, but if the last argument fails, you can check first if e.g. the last argument also accepts a term.

We could do that but I thought you weren't a fan of making the complete path from evaluator to overloadTree class based?

I don't really understand what this means.

Caching is indeed something to be left for another PR. Maybe we should make a new issue for it?

I'd be happy to have a call discussing this further.

[jitsedesmet]

We could make a new issue. This issue should also take the additionalExtensionTypes into account as this will change the way we cache in some ways.
I'd like to have a call too when that time comes :) .

[jitsedesmet]

This issue can be closed. I wanted to type 102 instead of 103 in #103 (comment) .