Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

get/set queries #23

Open
wants to merge 10 commits into
base: master
Choose a base branch
from
Open

get/set queries #23

wants to merge 10 commits into from

Conversation

rafaqz
Copy link
Member

@rafaqz rafaqz commented Jun 6, 2021

This PR adds get/set queries as discussed in #9, returning a Tuple of values from an object, or setting object values from a Tuple

Currently you can select objects by a select function, and choose where to descend with a descend function.

For macros I was thinking something like this could be nice:

@getall x isa Int
@setall x isa AbstractArray = arrays

TODO:

  • organise to use set/modify as other optics/lenses do
  • compose with other optics/lenses
  • write macros
  • context queries, where the returned value can be some function of obj/fieldname/value
  • tree context queries, where you can build a tree structure of e.g. fieldnames that lead to the queries objects
  • include Properties/Elements distinction, and maybe add Fields? this is using fieldnames in a @generated function

Notes:

  • After rewriting to match the style here it seems difficult to match the performance of a standalone recursive generated function. Might get there with some work. The performance is fine. There is one type stabiulity issue left checking values have been changed to avoid using constructorof - typeof val/state pairs are needed to track if a change occurred. Otherewise its a lot faster now when the types are unstable.
  • Performance with fieldnames in @generated with the Fields optic I added is 10-100x better than Properties. But it may need some additions to ConstructionBase.jl to be legitimate. Flatten.jl has always done this, but it predates ConstructionBase.jl, and it's a bit dodgy. We could add fieldconstructor and propertyconstructor that both default to constructorof, in case they need to be different.

@rafaqz rafaqz changed the title first pass get/set queries get/set queries Jun 6, 2021
Copy link
Member

@jw3126 jw3126 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Wow, thanks a lot. I find the code super elegant, especially how you could "contain" the use of @generated! Does composition work?

src/optics.jl Outdated
"""
mapfields(f, obj)

Construct a copy of `obj`, with each property replaced by
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
Construct a copy of `obj`, with each property replaced by
Construct a copy of `obj`, with each field replaced by

src/optics.jl Outdated
@@ -185,7 +205,7 @@ $EXPERIMENTAL
struct Elements end
OpticStyle(::Type{<:Elements}) = ModifyBased()

function modify(f, obj, ::Elements)
function modify(f, obj, ::Elements, object=List())
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

There are other ideas what n argument modify could mean. I think defining it is not essential for this PR? So let's try to avoid it.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Alternatively if you feel strongly about using modify we can also discuss that.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The reason for adding this argument is so we can use the same code to both Construct new objects in and return tuples of fields, with Tuple (for all) and Splat (for some filtered subset). This is how Flatten.jl works, it's just impossible to read that that is whats happening - your structure is so much cleaner here.

We can also use a different method entirely to do this, this was just me trying to find the cleanest way of using everything already written here and build things so the other optics can use what Ive added.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This method isn't working currently for that, it's just a dummy argument so it doesn't break.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ok sure, we can in the end decide whether to rename this. Competing ideas were to use extra args of modify for passing context around. Or have modify(f, obj, lens) behave to map(f, itr) as modify(f, objs..., lens) behaves to map(f, itrs...).

Copy link
Member Author

@rafaqz rafaqz Jun 7, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Better to keep the syntax open for map etc.

I've made them separate methods for now, we can work towards reducing the differences. Probably it should only affect the inner _modify not modify anyway.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 7, 2021

Thanks! It was awful before I rewrote it with the structure here.

I'm not sure how to do composition properly yet, it needs more thinking. That's the part I understand the least about Accessors.jl so far... but getting there.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 7, 2021

The iterator is broken too, I knew it couldn't be that easy lol...

Fixed: but things are getting a bit less elegant - the iterator has to be passed around everywhere. Probably the end result of this is that things will mostly look clear like you say, but mapfields will be hell, with lots of tuple return value manipulation and special casing.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 7, 2021

This is composing now. It hast to compose internally, as you want to compose with whatever fields are selected by Query, not with its return value.

@jw3126
Copy link
Member

jw3126 commented Jun 7, 2021

This is composing now. It hast to compose internally, as you want to compose with whatever fields are selected by Query, not with its return value.

Can you give a few examples of what Query should do and how you think it should compose?
I toyed a bit with this branch and found that things often do not behave as I anticipated.
Now I realize that this is very much WIP so I am not sure, whether I don't understand the intended semantics of Query or whether these are just bugs / not really implemented.

For instance

julia> using Accessors

julia> obj = (a=missing, b=1, c=(d=missing, e=(f=missing, g=2)))
(a = missing, b = 1, c = (d = missing, e = (f = missing, g = 2)))

julia> Query(ismissing)(obj)
(missing, 1, missing, missing, 2)

I would have expected (missing,missing,missing) instead.

Also are querries supposed to be lenses? That is should q::Query satisfy the lens laws:

@assert q(set(obj, q, val))  val
        # You get what you set.
@assert set(obj, q, q(obj))  obj
        # Setting what was already there changes nothing.
@assert set(set(obj, q, val1), q, val2)  set(obj, q, val2)
        # The last set wins.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 7, 2021

Yeah that's just a bug, the answer should be what you expect. I need to write a few more tests.

It should follow the lens laws... notice modify just uses map over the results of get to feed into set:
https://github.com/rafaqz/Accessors.jl/blob/e6e851b67318daac07647adcdab8714ad47627be/src/optics.jl#L530

The few tests I had just randomly work as expected 😆

@rafaqz
Copy link
Member Author

rafaqz commented Jun 8, 2021

Ok this version should be working for lens laws, but with some problems with set for Properties and bad set performance.

@jw3126
Copy link
Member

jw3126 commented Jun 8, 2021

I just realized, that querries are not lenses in general.

@assert q(set(obj, q, val))  val
        # You get what you set.
@assert set(obj, q, q(obj))  obj
        # Setting what was already there changes nothing.
@assert set(set(obj, q, val1), q, val2)  set(obj, q, val2)
        # The last set wins.

I believe the first and second lens law should always hold, but the third may not:

julia> using Accessors

julia> obj = (a=missing, b=1, c=(d=missing, e=(f=missing, g=2)))
(a = missing, b = 1, c = (d = missing, e = (f = missing, g = 2)))

julia> q = Query(ismissing);

julia> obj2 = set(obj, q, ["first", "wins", "here"])

julia> set(obj2, q, ["second", "should", "win"])

Not a huge deal, but we should be careful about using lens as a variable name.

src/optics.jl Outdated

$EXPERIMENTAL
"""
struct Properties end
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Since we have ConstructionBase.getproperties and ConstructionBase.setproperties I wonder if we could base this on

set(obj, ::Properties, val) = setproperties(obj, val)
(::Properties)(obj) = getproperties(obj)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah that's probably better.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 8, 2021

Yeah... the query would have to be updated for that to hold, e.g:

julia> set(obj2, Query(x -> x isa String), ["second", "should", "win"])
(a = "second", b = 1, c = (d = "should", e = (f = "win", g = 2)))

So it breaks 3. when the the values passed to set would give a different query result to the values in the object that they replace. We just need to give that a name I guess.

Formally (for tuples at least) maybe its:

islens = query(values) == values

Also let me know what you think of the macros (theyre in the tests now too). They seem nice for simple use cases, just using the Query object is probably easier beyond something like this:

julia> missings_obj = (a=missing, b=1, c=(d=missing, e=(f=missing, g=2)))
(a = missing, b = 1, c = (d = missing, e = (f = missing, g = 2)))

julia> @getall missings_obj isa Number
(1, 2)

julia> @setall ismissing(missings_obj) = (1.0, 2.0, 3.0)
(a = 1.0, b = 1, c = (d = 2.0, e = (f = 3.0, g = 2)))

Edit: it feels like these examples should also work for an iterator like a single number or Ref, although that breaks lens laws as well.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 8, 2021

How do you feel about a dependency on Static.jl?

Using StaticInt as an iterator solves the type stability with set.

@jw3126
Copy link
Member

jw3126 commented Jun 8, 2021

How do you feel about a dependency on Static.jl?

Using StaticInt as an iterator solves the type stability with set.

Static.jl looks like a small dependency, so I am fine with it.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 8, 2021

Turns out Static.jl doesn't actually fix it, I'm just getting Revise.jl artifacts from this Julia bug:
JuliaLang/julia#35800

We'll have to settle for 20-100ns or so timings until that gets fixed. I can get everything under 2ns using Revise but it wont stick on restart, which has been driving me crazy.

@jw3126
Copy link
Member

jw3126 commented Jun 9, 2021

I think I have an alternative approach how this can be implemented. Let me first sketch a slow implementation,
analyze why it is slow and sketch how to fix it.

struct Query{S,D,O}
    select::S
    descend_condition::D
    optic::O
end

function modify(f, obj, q)
    modify(obj, q.optic) do o
        if q.select_condition(o)
            f(o)
        elseif q.descent_condition(o)
            modify(f, o, q)
        else
            o
        end
    end
end

pop(x) = first(x), Base.tail(x)
push(x, val) = (x..., val)

function setall(obj, q, vals)
    modify(obj, q) do o
        val, vals=pop(vals)
        val
    end
end

function getall(obj, q)
    ret = ()
    modify(obj,q) do o
        push(ret, o)
        o
    end
    return ret
end

Now this is slow, because we change captured variables in a closure. How to fix this?
By passing state around explicitly. So we have to replace modify as a primitive by a state aware modify_stateful.

function getall(obj, q)
    initial_state = ()
    _, final_state = modify_stateful((obj, initial_state), q) do o, state
        new_state = push(state, o)
        o, new_state
    end
    return final_state
end

"""

    new_obj, new_state = modify_stateful(f, (obj,state), optic)

Here `f` has signature `f(::Value, ::State) -> Tuple{NewValue, NewState}`.
"""
function modify_stateful end

function modify_stateful(f, (obj, state1), optic::Properties)
    # @generated function that produces the following code:
    nt = getproperties(obj)
    val1, state2 = modify_stateful(f, (nt.field1, state1), optic)
    val2, state3 = modify_stateful(f, (nt.field2, state2), optic)
    val3, state4 = modify_stateful(f, (nt.field3, state3), optic)
    val4, state5 = modify_stateful(f, (nt.field4, state4), optic)
    patch = (field1=val1, field2=val2...)
    new_obj = setproperties(obj, patch)
    new_state = state5
    return (new_obj, new_state)
end

function modify_stateful(f, (obj, state), q::Query)
    modify_stateful((obj,state), q.optic) do o,s
        if q.select_condition(o)
            f(o,s)
        elseif q.descent_condition(o)
            modify_stateful(f, (o,s), q)
        else
            o, s
        end
    end
end

function modify_stateful(f, (obj, state), ::ComposedOptic)
    ...
end

# all currently existing modify methods in Accessors.jl can be rewritten into `modify_stateful` in a straight forward fashion.
# Like with modify we want to use trait based dispatch `_modify_stateful(f, obj_state, optic, ::OpticStyle)`.
# `modify` may in the end be reimplemented in terms of `modify_stateful` if the compiler likes it.

What do you think?

@rafaqz
Copy link
Member Author

rafaqz commented Jun 9, 2021

Wow that looks like a flexible generalisation, lets use it. Thanks for putting the time in to rethink this.

@jw3126
Copy link
Member

jw3126 commented Jun 9, 2021

Also let me know what you think of the macros (theyre in the tests now too). They seem nice for simple use cases, just using the Query object is probably easier beyond something like this:

I wonder if we can capture generator syntax here to make the macros a bit more flexible.

@getall (x for x in obj if select(x))
@getall Float64[x for x in obj if select(x)] # collects into a vector of Float64 
@modify CuArray(x) for x in obj if x isa AbstractArray # move everything to GPU
@getall (x for x in obj |> Elements()) # customize the optic to flatten a nested tuple

@rafaqz
Copy link
Member Author

rafaqz commented Jun 9, 2021

This is nice syntax:

@getall Float64[x for x in obj if select(x)] # collects into a vector of Float64 

You could also use lenses:

@getall [x.a for x in obj if x isa NamedTuple]
@setall (x[2] for x in obj if x isa AbstractArray) = (1, 2 ,3)

@jw3126
Copy link
Member

jw3126 commented Jun 9, 2021

Not for this PR, but for a later stage I think we can connect this with Transducers. The idea is to turn (obj, optic) into a ReducibleCollection.
Roughly speaking by:

function Transducers.foldl(rf, ReducibleCollection(obj, optic), init)
    # TODO this is the wrong method to overload, but you get the idea
    _, ret = modify_stateful((obj, init), optic) do o, state
        new_state = rf(state, o)
        o, new_state
    end
    return ret
end

We would have:

getall(obj, q) = foldl(push!!, ReducibleCollection(obj, q))

Benefits would be that we could directly apply reduction functions to queries and Transducers could take care of the output container (e.g. Tuple, Vector, lazy iterator...).

@rafaqz
Copy link
Member Author

rafaqz commented Jun 9, 2021

Transducers interop sounds good for a future PR. I probably have to leave that to you as I haven't had time to get my head around transducers yet.

@jw3126
Copy link
Member

jw3126 commented Jun 9, 2021

You could also use lenses:

@getall [x.a for x in obj if x isa NamedTuple]
@setall (x[2] for x in obj if x isa AbstractArray) = (1, 2 ,3)

Ah nice, this is a way to deal with simple "contextful" queries.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 9, 2021

The context that is harder to get is the parent object and field name (probably as a StaticSymbol/StaticInt). Fieldname is really useful for making name => value pairs e.g widget labels or checking you are querying the right fields. We can work it into state somehow.

This was fairly straightforward but not finished:

julia> missings_obj = (a=missing, b=1, c=(d=missing, e=(f=missing, g=2)))
(a = missing, b = 1, c = (d = missing, e = (f = missing, g = 2)))

julia> @getall (x.e for x in missings_obj if x isa NamedTuple)
((f = missing, g = 2),)

@jw3126
Copy link
Member

jw3126 commented Jun 9, 2021

The context that is harder to get is the parent object and field name (probably as a StaticSymbol/StaticInt). Fieldname is really useful for making name => value pairs e.g widget labels or checking you are querying the right fields. We can work it into state somehow.

I totally agree fieldnames are so useful. More general context is tough and IMO out of scope for this PR. But as you say the way to go piggy bag context into state. Probably via some PushCtx() mechanism like what I tried to sketch here.

@rafaqz
Copy link
Member Author

rafaqz commented Jun 19, 2021

I've implemented modify_stateful and built getall, setall and context methods on it generally following the ideas from this comment. The structure seems pretty clean, although the generated function is still a bit of a mess. State wrappers like ConstextState, GetAllState and SetAllState allow dispatching behaviours for each type and also wrapping state objects.

Unfortunately it's harder to optimise now, I've got some lingering type instabilities. Maybe you can see whats causing them.

Comment on lines +482 to +475
modify_stateful((obj, state), inner(q.optic)) do o, s
if (q::Q).select_condition(o)
(f::F)(o, s)
elseif (q::Q).descent_condition(o)
ds = descent_state(s)
o, ns = modify_stateful(f::F, (o, ds), q::Q)
o, merge_state(ds, ns)
else
o, s
end
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks a lot for pushing this further. I also played around with implementing this, see this branch:
https://github.com/JuliaObjects/Accessors.jl/tree/modify_stateful
Like with your implementation I encountered inference issues. I do not fully understand them, but it seems the compiler dislikes this switch. To explore what's going on I replaced elseif (q::Q).descent_condition(o) into elseif true but the thing would still not infer. OTOH manually deleting the elseif branch did help the compiler to infer.

Note I did this experimentation with my branch, which is somewhat different then yours, but I guess has the same underlying issues. Worth checking if things are better with the new ConstructionBase version and nightly julia.

If not I think it would be good to produce an MWE and report it upstream. I don't know if it is considered a bug, but maybe we'll get an explanation of why it is this way and how to work around it.

A quick and dirty workaround would be to introduce a more narrow query where you can only select and descent based on type. Then the if elseif ... could be replaced by three methods.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ok interesting we both hit the same problem.

I think the differences are mostly just my code to handle context and optional construction in setall. But those aren't whats causing the instability...

It seems like the problem is calling modify_stateful recursively? It still seems broken even without the elseif, and the elseif was fine in the previous version. I don't understand exactly what is different between these implementations and my previous one or Flatten.jl, but it could be the additional complexity of the return objects? Or there is a little more happening at runtime in modify_stateful than I had in mapobject or Flatten.jl, and the compiler is giving up on something?

I also saw no difference between ConstructionBase versions.

Copy link
Member Author

@rafaqz rafaqz Jun 20, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Seems its the layers of anonymous functions. Flatten.jl has the shared code inside the generated functions, and simple separate generated functions for getall/setall (flatten/reconstruct).

I much prefer the clarity of the current solution here. But it seems like if we want this to compile away we cant use anonymous functions inside the recursion.

I can't get this version to compile away even if you don't return any of the updated objects - so Julia can't even tell that the anonymous function is not modifying external state somehow and runs it even if it's not used.

Copy link
Member

@jw3126 jw3126 Jun 23, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It does not seem to be related to anonymous functions per see. I played with eliminating all anonymous functions.
I replaced code like

modify_stateful(...) do os
    do_stuff(os, captured, variables)
end

with code like

struct DoStuff{C,V}
    captured::C
    variables::V
end
(f::DoStruff)(os) = do_stuff(os, f.captured, f.variables)
modify_stateful(DoStuff(captured, variables), ...)

It helped in very small examples, small examples still fail. Also, @inline everything did not help. Also eliminating all @generated functions by manually defining all ConstructionBase.f(::MyObject, ...) did not help.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Damn, that's exhaustive.

It feels like the compiler is using some heuristic to give up on solving the returned state of the recursion instead of just trying. A single non-recursive modify_stateful compiles away completely, but it wont if called recursively.

Copy link
Member Author

@rafaqz rafaqz Jun 23, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ok, think i found the issue. If you define the select and descent conditions like this it's type stable:

select_condition(x::NamedTuple) = true
select_condition(x) = false

descent_condition(x::Tuple) = true
descent_condition(x) = false

So the compiler optimises these methods differently to methods that are passed in in any way. Even with the function in the type instead of fields, or just passing a Type to a 2 arg version of descend_condition still doesn't work. It's just giving up and returning Any. If you actually include the types to pass to 2 arg descend_condition(T, x) in the code, it's type-stable.

I had assumed previously that using a type from a type parameters was practically the same as writing the type in the code manually, but it seems like it isn't.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Awesome that you found the issue! This looks like a bug to me, can you maybe produce a MWE and report it upstream?

Copy link
Member Author

@rafaqz rafaqz Jun 23, 2021

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah I'm cutting it down to size, but its probably 1.6 inference problems like JuliaLang/julia#35800.

It's all type stable on 1.4 - that's why this feels weird for performance intuition. These things used to just work.

Actually no its still all #35800, even on 1.4!! if you compile if with the types hard coded once then it knows when you use revise with the types as parameters, and is type stable. Then it's not on restart.

@rafaqz
Copy link
Member Author

rafaqz commented Jul 19, 2021

@jw3126 sorry I haven't had time for this in a while, just revisiting now.

How do you feel about these options:

  1. finish this with the current type instability
  2. reduce the scope to only matching types (so all at compile time) and separate out more generated functions to get type stability

@jw3126
Copy link
Member

jw3126 commented Feb 11, 2022

IIRC queries of moderate complexity are not type stable, trivial queries work?

@bgroenks96
Copy link

Do you mean the query complexity or the complexity of the type being queried?

If the former, having type stable @getall x isa T would already be enormously helpful.

@rafaqz
Copy link
Member Author

rafaqz commented Feb 11, 2022

@bgroenks96 your trick in Flatten.jl of mapping out the type beforehand might help here too? Idk.

I was hoping the compiler might get better some julia version and handle this. It obviously can do it, because Revise.jl can "fix" the type stability. But if it will is another question.

But agreed, type stable @getall x isa T will be amazing.

@bgroenks96
Copy link

I can take a look when I have some time to see if it is applicable.... although I must say I am hesitant. That is some of the most dense, inelegant, and unreadable code I have written in years...

@rafaqz
Copy link
Member Author

rafaqz commented Feb 11, 2022

Yeah, and we did put a lot of work into making this elegant. The bug that lets Revise.jl fix this also makes it hell to work on - you have to restart Julia to check your changes.

@jw3126
Copy link
Member

jw3126 commented Feb 11, 2022

The problem is recursion complexity, which is driven by complexity of the optic (query). Accessors is based on composing simple optics and methods on a composed optic recurse into the parts. The code in this PR seems to reach compiler limits particular quickly. But it is a general problem in Accessors.jl. See also: JuliaLang/julia#43296 (comment)
The problem is recursion complexity. In case of queries the main driver is recursing over nested structs, so object complexity. For most other optics, it is recursion into optics pieces. It is a general problem in Accessors.jl. See also: JuliaLang/julia#43296 (comment)

@rafaqz
Copy link
Member Author

rafaqz commented Feb 11, 2022

Oh wow so its actually getting worse, not better

@jw3126
Copy link
Member

jw3126 commented Feb 11, 2022

Oh wow so its actually getting worse, not better

Yeah, it got worse in 1.7.

@rafaqz
Copy link
Member Author

rafaqz commented Feb 11, 2022

Ok, yes It seems like Flatten.jl also got worse with 1.7 - its a huge chunk of the TTFX for DynamicGrids.jl now.

What surprised me recently is that type instability in these methods seems to have a large effect on compile time - if you look at @snoopi_deep profiles the compiler chases the result type through the whole tree of recursive methods, but starting with abstract types.

So it precompiles a whole tree of abstract methods that will never be used, which of course fails to produce a known output type but costs like half a second to conclude that. You cant precompile this away either.

@bgroenks96
Copy link

So I guess I will continue sticking with 1.6 then...

@bgroenks96
Copy link

@rafaqz Perhaps we should consider cleaning up and generalizing the type tree concept in Flatten.jl and making it a separate package that could also be consumed by Accessors.jl?. Maybe compile-time type analysis in generated functions has to be the workaround until these compiler issues get fixed. It's a bit annoying though because we're basically just doing the compiler's job for it. And it's not an enviable job.

@bgroenks96
Copy link

Ok, yes It seems like Flatten.jl also got worse with 1.7 - its a huge chunk of the TTFX for DynamicGrids.jl now.

Can you tell if it is flatten or reconstruct which is contributing the most?

@rafaqz
Copy link
Member Author

rafaqz commented Feb 11, 2022

Pretty sure its reconstruct

@bgroenks96
Copy link

Oof. Ok, then it might be the type tree actually causing it then.

@rafaqz
Copy link
Member Author

rafaqz commented Feb 11, 2022

I wouldn't conclude that yet honestly, I'll have to look into it more.

It's possible the problem is further out. But we should still think about the fact that the compiler will push abstract types through these methods to try and work out the result type.

@rafaqz
Copy link
Member Author

rafaqz commented Feb 11, 2022

@bgroenks96 you might be right about generalising that package, but it is pretty annoying to do that work for the compiler.

@Tokazama
Copy link

I can't be sure without explicitly testing this, but I think inference is failing because you are trying to operate on a complex type instead of the instance. I've encountered similar issues recently and you can get around it if you have a clear path through each struct's fields and are willing to do some work upfront with the instance instead of the type.

@rafaqz
Copy link
Member Author

rafaqz commented Apr 27, 2022

Hmm maybe, but I'm not sure exactly what you mean. Do you have any specific lines/areas that could be changed?

It looked to me like the compiler gives up on chasing function return types through nested recursive functions. Which also happens in Flatten.jl now.

@aplavin
Copy link
Member

aplavin commented May 15, 2023

This functionality is implemented in AccessorsExtra, and works fine in my usage over recent months.
Do you @rafaqz @jw3126 think it covers everything, or something remains from the features developed/attempted in this PR?

julia> using AccessorsExtra
julia> obj = (a=missing, b=1, c=(d=missing, e=(f=missing, g=2)))

julia> o = RecursiveOfType(Number)
julia> xs = getall(obj, o)
(1, 2)
julia> setall(obj, o, xs .+ 1)
(a = missing, b = 2, c = (d = missing, e = (f = missing, g = 3)))

julia> o = RecursiveOfType(Missing)  @optic _.c
julia> getall(obj, o)
(missing, missing)
julia> setall(obj, o, (:x, :y))
(a = missing, b = 1, c = (d = :x, e = (f = :y, g = 2)))

Everything is type-stable, little to no overhead, differentiates automatically, and composes with other optics (2nd example).
Implementation looks reasonable, but pretty involved and not without tricks: https://gitlab.com/aplavin/AccessorsExtra.jl/-/blob/master/src/recursive.jl. So, I don't propose to include it here for now.

@rafaqz
Copy link
Member Author

rafaqz commented May 15, 2023

Nice, looks similar to Flatten.jl.

Honestly I doubt this will ever be possible without the generated functions.

So Im not sure what we will be waiting on to put it here...

@aplavin
Copy link
Member

aplavin commented May 16, 2023

It's not just @generated, but also:

  • Core.Compiler.return_type...
  • ... in @generated function - are they guaranteed to play nicely together?
  • Hack for staticarrays (can probably be removed after improve getall/setall for staticarrays #108)
  • setall doesn't work when Vectors or other runtime-length arrays are involved - but the semantics is clear, it should work

Interestingly, getall turns out to be possible without any code generation using a neat recursion trick taken from here. Maybe, setall can also be implemented similarly? IDK.

Accessors itself is basically free of hacks/julia internals for now, and it's probably best for such a foundational package to stay that way. At some point when the code matures, it can be upstreamed from AccessorsExtra to Accessors, but I'm not sure if that movement would bring any tangible benefits by itself now. The optic works and can already be used by anyone, and AccessorsExtra link is present here in the README.

@aplavin
Copy link
Member

aplavin commented Aug 8, 2023

Aside from implementation challenges, I noticed there's also a question of semantics: how should recursion work exactly. Should RecursiveOfType(T) recurse into T to access other Ts nested within? Current implementation in AccessorsExtra says "yes", and it's convenient sometimes - but not always.

Convert all namedtuples to dicts, no matter how nested they are:

julia> modify(Dict  pairs, (a=1, bs=((c=1, d="2"), (c=3, d="xxx"))), RecursiveOfType(NamedTuple))
Dict{Symbol, Any} with 2 entries:
  :a  => 1
  :bs => (Dict{Symbol, Any}(:d=>"2", :c=>1), Dict{Symbol, Any}(:d=>"xxx", :c=>3))

but the same decision can lead to pretty confusing

julia> modify(x -> 10x, (a=1+2im,), RecursiveOfType(Number))
(a = 100 + 200im,)

julia> getall((a=1+(2//3)im,), RecursiveOfType(Number))
(1, 1, 1//1, 2, 3, 2//3, 1//1 + 2//3*im)

Do you have any suggestions of what's the better/more principled default, and how to make it convenient to switch between recurse/not recurse into T?

@jw3126
Copy link
Member

jw3126 commented Aug 8, 2023

I noticed there's also a question of semantics: how should recursion work exactly.

That is a very good point. We should support both. Naming is tricky though. Somewhat similar concepts are breadth first vs depth first search or prewalk and postwalk in MacroTools.

@aplavin
Copy link
Member

aplavin commented Aug 8, 2023

Yeah, pre/post order is another option indeed! Applicable only when it recurses from T into nested Ts.
Potential interface idea:

modify(f, x, RecursiveOfType(T, order=:post))  # postwalk
modify(f, x, RecursiveOfType(T, recurse_nested=false))

@aplavin
Copy link
Member

aplavin commented Jan 1, 2024

In a recent AccessorsExtra version from December, I finally added the order argument: RecursiveOfType(..., order=:pre)/:post/nothing (default). The main interface seems complete now...

...plus a few other neat functions

like "unrecurcising" a recursive optic for advanced usecases:

julia> obj = (a=1, b=([2,3,4,5], "", 6+7im))

julia> ConcatOptics(obj, RecursiveOfType(Real))
(@optic _.a) ++ (@optic _.b[1][]) ++ (@optic _.b[3].re) ++ (@optic _.b[3].im)

Actually, getall and modify don't really use any internals explicitly, although they rely on a hack I don't fully understand (taken from Functors.jl). Maybe, it's time to include this functionality into Accessors, idk.
Meanwhile, setall heavily relies on return_type-in-@generated which I do not know how to get rid of. It works but is well into "internals" territory, so I don't think this part should be put into Accessors for now.

Happy New Year :)

@jw3126
Copy link
Member

jw3126 commented Jan 1, 2024

Happy new year! We could add the modify/getall part if you think it works well enough to Accessors.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

5 participants