Improve feaure: Implement pattern as cycle-free directed graph

Issue #186 new
Roman Telezhynskyi repo owner created an issue

Create graph that help delete all depend objects in pattern before delete current.

Comments (36)

  1. Roman Telezhynskyi reporter

    For such deletion need know all ids of children. In current realization each tool increment reference value to object that prevent object deletion if value > 1.

    Main difficulties extract is information about objects from formula. We already can extract line angle, line length, arc length, curve length etc. Parser should use this information for adding new connections.

    I think, we should use tree data structure for operation with this information. Qt himself doesn't provide such data structures. We can look the tree.hh library, very promising candidate.

  2. Susan Spencer

    Important because of the ease of user changes. Currently some points cannot be deleted without manually deleting all the child points, objects, and details.

  3. Barbara Weberkind

    Since an object, e.g. a line, can depend on more than one object (like, a line on two points), the pattern graph is more complex than a tree. It's a cycle-free directed graph. Smart delete would need to delete the closure of the deleted object. Needs a very simple graph library. The pattern program I wrote in C# has that... could try to convert and add. On this subject, it could also be useful to highlight the upstream/downstream objects of a selected object, to see what it depends on or what depends on it.

  4. Roman Telezhynskyi reporter

    Yes, seem like a good idea. But don't forget about a formula, especially about internal variables like Line_A_B. An object that use the variable also depend on A and B points.

  5. Barbara Weberkind

    Yes, that's what I mean by 'closure'. Anything that uses Line_A_B has dependency on the line, which in turn has dependency on the two points. That's what a graph would represent.

  6. Barbara Weberkind

    Hello, I have started to work on this. I would like to discuss on the Google discussion group, unfortunately I can't post there, and google doesn't let me log in, I tried everything. So I need to discuss this here. It's quite an architectural change, so I'd like to discuss the changes needed first.

  7. Barbara Weberkind

    So, first my observations of the existing code. Because I am not as familiar with the codebase as Roman or Susan or Valentina, can you just say 'yes' or 'no' to my observations here?

    1. For every DOM element in the .val file, more precisely every 'data' element (point, line, spline, and so on), a corresponding tool is created at the time of loading the .Val file or at the time of adding the element to the pattern.

    2. The tool ID and the ID of the corresponding DOM element are the same.

    3. Both the tool (VAbstractTool) and the element (QDomElement) have a pointer to the document (VAbstractPattern). The VAbstractPattern in turn can get every tool and every DOM element by ID. So having an ID and the pattern document is enough to get both the QDomEelement and the tool.

    4. The deletion is currently prevented in VDrawTool::ContextMenu(), where the context menu item gets grayed out, and VAbstractTool::DeleteTool(), where deletion is refused in case we were to get there.

    5. What the refusal to delete is based on is a reference count, the member variable _referens. The minimum _referens is 1. If it is larger, >1, it means there are foreign dependencies on this tool, and the deletion is disallowed.

    6. When a tool is created based on another tool, e.g. a point B at a distance from a point A, the _referens count of point A is increased. The function to do this is VDataTool::incrementReferens(), which in turn is called by VPattern::IncrementReferens().

    7. All calls to increment or decrement the reference count pass through this global method on the pattern, VPattern::IncrementReferens().

  8. Barbara Weberkind

    So it appears to me that this VDataTool::incrementReferens() and VPattern::IncrementReferens() are the crucial points that can help determine the pattern graph of actual internal dependencies. What is needed to create the graph there is that instead of just saying "there is another dependency on this one", to actually pass on which tool is the newly dependent one. The change would be to add a parameter to VDataTool::incrementReferens() and its overloads to take the ID of the dependent tool/element, and to change the signature of VPattern::IncrementRefeens() to not take just 1 ID (the ID of the tool to increase the reference count for), but 2 IDs (also the ID of the referencing tool).

    Before: VDataTool::incrementReferens()

    After: VDataTool::incrementReferens(quint32 child_id)

    Before: VPattern::IncrementReferens(quint32 tool_id)

    After: VPattern::IncrementReferens(quint32 parent_id, quint32 child_id)

    and VPattern::IncrementReferens(quint32 parent_id, quint32 child_id) would call something that builds the graph.

    DecrementReferens() would work correspondingly, just the other way round.

  9. Barbara Weberkind

    When that is done, then it could be hugely useful. E.g. VDrawTool::ContextMenu() would not need to disallow the 'Remove' menu option any more, because deletion would be on principle allowed. VAbstractTool::DeleteTool() could ask the graph (via the document) for any dependencies of the tool it's about to delete. It could display a list of the dependencies or highlight them in the draw view, and ask the user for confirmation. And if the user confirms, then it could in turn delete all those dependent tools.

  10. Barbara Weberkind

    I hope it's clear how I meant this... I meant to imply as a matter of course: where incrementReferens() or ContextMenu() or DeleteTool() are overridden, the overrides would be changed correspondlgly, dependent on how they work.

  11. Roman Telezhynskyi reporter

    Hello, I have started to work on this. I would like to discuss on the Google discussion group, unfortunately I can't post there, and google doesn't let me log in, I tried everything.

    Very strange because you don't need to be a member for posting. Also you don't need a google account to be able to use the mail list. All we need to know is your email. Give it to me and i will send you an invite.

    So I need to discuss this here. It's quite an architectural change, so I'd like to discuss the changes needed first.

    I understand, but don't think this is really the best place for this.

  12. Roman Telezhynskyi reporter
    1. For every DOM element in the .val file, more precisely every 'data' element (point, line, spline, and so on), a corresponding tool is created at the time of loading the .Val file or at the time of adding the element to the pattern.

    Yes.

    1. The tool ID and the ID of the corresponding DOM element are the same.

    Not always. Some tools have more child objects. Or invisible for a user, only children are visible.

    1. Both the tool (VAbstractTool) and the element (QDomElement) have a pointer to the document (VAbstractPattern). The VAbstractPattern in turn can get every tool and every DOM element by ID. So having an ID and the pattern document is enough to get both the QDomEelement and the tool.

    Yes.

    1. The deletion is currently prevented in VDrawTool::ContextMenu(), where the context menu item gets grayed out, and VAbstractTool::DeleteTool(), where deletion is refused in case we were to get there.

    Yes.

    1. What the refusal to delete is based on is a reference count, the member variable _referens. The minimum _referens is 1. If it is larger, >1, it means there are foreign dependencies on this tool, and the deletion is disallowed.

    Yes.

    1. When a tool is created based on another tool, e.g. a point B at a distance from a point A, the _referens count of point A is increased. The function to do this is VDataTool::incrementReferens(), which in turn is called by VPattern::IncrementReferens().

    Yes.

    1. All calls to increment or decrement the reference count pass through this global method on the pattern, VPattern::IncrementReferens().

    Yes.

  13. Roman Telezhynskyi reporter

    How i see it not enough just say id X uses you. Don't forget about formulas. Maybe some tool doesn't use another, but also relies on length/angle this tool creates. If you delete a tool a formula will be broken.

    Second thing. How to delete all dependencies before deleting actual tool.

    As you said it would be nice to visualize all dependent objects.

  14. Barbara Weberkind

    Right now, my first step is just to get the list of children, and try to do the 'smart delete'.

    My understanding is that when 'smart deleting' a tool like this, say tool A... Being smart about this, and deleting all dependent tools X with A -- any and every tool that uses anything, like angle or length of A would be a dependent tool and so would get deleted, not broken. That's what 'smart' would mean.

    ... unless you tell me the _referens' count does not get increased when using the angle or length of another tool. If that is so, then I have to do more research and find this out. I plan to make every tool a descendent that uses any attribute of the corresponding DOM element, like angle or length.

    In the meantime, can I be made part of the dev list for this and be assigned this issue? I can also regularly push my commits to my branch for review, if you like. Or create pull requests for review if I get anywhere with this.

    someWhoKnowsWhatUser@yandex.com

  15. Roman Telezhynskyi reporter

    In the meantime, can I be made part of the dev list for this and be assigned this issue?

    Yes, sure.

    I can also regularly push my commits to my branch for review, if you like. Or create pull requests for review if I get anywhere with this.

    Making a pull request is a bad idea. Better i will comment your repository. I am watching it and see all pushes.

  16. Roman Telezhynskyi reporter

    If that is so, then I have to do more research and find this out. I plan to make every tool a descendent that uses any attribute of the corresponding DOM element, like angle or length.

    Some, not all support formulas. Inside formulas you can meet internal variables LineAngle, LineLength and so on. We should parse this objects and get labels of points. These labels than convert to ids. This is how i see it.

  17. Barbara Weberkind

    Hello Susan,

    thanks so much for asking and pulling me back, yes, still interested, just so busy. I have worked on it and should maybe commit my branch intermediately, maybe outline what I've found what needs changing....

  18. Barbara Weberkind

    Hi Susan, I don't know if it's too much of an ask, but I need a test file and wonder if you could help me (or someone could). The test file would not really contain a pattern, it would just be there to test all possible tool dependencies. It would simply contain a point at a distance to the base point, and the line between the two points.

    Then, it would contain ... every other tool that exists. But every other tool, in every one of its parameters, would use the length of that first line. I.e., the file would contain an Increment that is the length of the first line. It would have another 'point at a distance' where the distance is the length of the first line. It would create an arc where the radius is the length of that line. And a curve where the gradient lengths and angles somehow are calculated from the length of the first line. And a point along the curve at a distance that is the length of the first line.

    etc etc etc. I am asking because I am not even sure that I know how to use all tools that could contain a formula somewhere which could point to another object.

    Thanks for any help in advance.

  19. Barbara Weberkind

    OK, status of this... and some of my observations:

    Got it so that 2 basic uses cases actually work, and that's: - when making a point based on another, the new dependency of the one point on the new point is correctly modeled in the graph; - when a variable, e.g. length between two points, is used in an attribute of some other tool, then the two points that form the line become dependent on the tool that use this length.

    Thirdly, interestingly, I observed that when a point is deleted, the dependency and the node is not deleted, but instead the entire pattern re-parsed and so the graph gets built up again to correctness. This behaviour of a new full parse because of deletion ... why is it?

    The following is still TODO: -- it has to be tested and debugged for all possible tools, variables, and all possible attributes.

    -- The downside is that whenever a new variable or new attribute is created, the programmer who does that must make sure that it gets included in the graph logic. I.e. new attributes that can be formulas must be noted as such. New variables must get a 'GetToolIds()' function. New attributes that can point to the ID of an object must be noted as such as well.

    -- when the dialog for formulas is opened, the list of variables that can be used must be created differently, taking into account all independent variables, not just those with lower ids.

    -- indeed, the reference _referens count and all that is associated with it can go; instead, where it is used, the graph must be interrogated. At the point where it is decided whether a point can be deleted, this is already done. 'Smart delete'.

    -- Highlighting all dependent children would still be a good idea.

    -- and of course, unit tests for it all.....

    The last commit is here: https://bitbucket.org/curious_one/valentina/commits/all

    If you like you can review, but because there are still so many TODOs, I'm not making a pull request yet.

    Thanks!

  20. Roman Telezhynskyi reporter

    Thirdly, interestingly, I observed that when a point is deleted, the dependency and the node is not deleted, but instead the entire pattern re-parsed and so the graph gets built up again to correctness. This behaviour of a new full parse because of deletion ... why is it?

    Where? I don't think i understand you.

    If you like you can review, but because there are still so many TODOs, I'm not making a pull request yet.

    Agree, not best time for PR.

    But i don't see how you will do undo deleting.

  21. Barbara Weberkind

    Hell Susan,

    thanks very much, will try them!!! will report back. The point is, the naked implementation has been done, but so far it's still a bit difficult to then verify that it worked correctly. I really need some tests.

    thanks so much!

  22. Log in to comment