Hi,
I was looking through dwarfcmp to try to understand the libdw/c++ stuff. In particular dwarf_comparator and dwarf_tracker. But I admit to get lost a bit in the technicalities of the implementation (my c++ template foo is pretty weak). So I thought about how I would solve the general problem of finding out whether two die tree/graphs are equivalent. Hopefully the idea is somewhat similar to how the code solves it, so I only have to better understand the added caching and understand the implicit stacks/paths that are kept better (the little walk, step, visitor classes to push and pop when things come in and go out scope with destructors is neat, but make my head hurt). But maybe my idea has flaws that explain why the code is different/more involved than what I expect.
- We start with two DIEs that we want to prove equivalent.
- A DIE has an unique identifier (normally the file plus index into the .debug_info, but it could be something else), if two DIEs have the same unique identifier they are equal. Two DIEs with different unique identifiers could still be equal.
- A DIE has a tag, for two DIEs to be equal they must have the same tag.
- A DIE has a (ordered) list of children DIEs. For two DIEs to be equal they must have the same number of equal children DIEs (in order).
- Till this far we just have a tree of (tagged) DIEs which we could compare by walking them in some (breath-first/depth-first) order and see if all the DIE tags match up.
- The wrinkle comes from a DIE also having a set of attributes. The attributes don't have an order, but we could invent some by sorting them before comparison. An attribute as a key and a value.
- The attribute keys are simple names. For two DIEs to be equal they have to have the same number of attributes, with the same names.
- The attribute values can be simple values. For two DIEs to be equal all attributes with the same names with simple values should have the same value (modulo encoding of such value).
- The attribute values can also be references to DIEs. This might be new DIEs, but also DIEs "up" in the DIE children tree. This is why the DIE tree is actually a (pointed) graph.
- For two DIEs to be equal the attribute values of the attributes with the same key names that have references to DIEs as value should: a) Be both not yet seen DIEs in the respective trees so far, and be equal DIEs (in this case we can just treat the attribute reference as we would a child DIE, compare it in order). Or: b) Be both already seen DIEs in the respective trees so far, and be in the "same location".
The "same location" means that the references to the DIEs in the trees are at the same place if we would walk the tree in the order chosen above.
To keep the order of the nodes I would keep two stacks of DIEs that represent the path traveled so far. That way whether or not a DIE has already been seen is just whether it is already on the stack, and the "location" can just be expressed as the index of that DIE into the stack.
Does any of the above make sense? Is this what the comparator/tracker logic does? Are there wrinkles in the above logic that make it more involved? What kind of caching should be added to make the above easier/better/faster?
Cheers,
Mark
That's the basics, and that's indeed how dwarf_comparator works (depth first).
- The attribute values can also be references to DIEs. This might be new DIEs, but also DIEs "up" in the DIE children tree. This is why the DIE tree is actually a (pointed) graph.
This is indeed the only reason the whole thing is hairy at all.
- For two DIEs to be equal the attribute values of the attributes with the same key names that have references to DIEs as value should: a) Be both not yet seen DIEs in the respective trees so far, and be equal DIEs (in this case we can just treat the attribute reference as we would a child DIE, compare it in order). Or: b) Be both already seen DIEs in the respective trees so far, and be in the "same location".
I don't understand the "already seen" or not distinction here. Whether they are forward references or not doesn't matter in any way I can think of (except in how you'd implement it, of course). Regardless, you need the subtrees to be equal and their locations to be equivalent.
The "same location" means that the references to the DIEs in the trees are at the same place if we would walk the tree in the order chosen above.
Approximately, yes. I've called this "equivalent context" rather than "same location" to abstract it a little.
The definition for "exact equivalence" I mean is that each parent DIE has matching attributes and equivalent parents. That's a recursive definition, so it iterates on up to the root of the tree (the CU).
For the overall goal of maximal sharing constrained only by the real high-level semantic needs to avoid wrong conflations, we'll want some flexibility to ignore some kinds of attribute differences.
This decision is encoded in dwarf_comparator::equal_enough. The current definition of "equal enough" is that we ignore the reference attributes. That's as much as anything else just because another vector of complex equality checking with references would just make things even harder to think about. In practice, I'm pretty sure the differences between "context" DIEs that matter semantically are not in their references.
But, in the abstract, if it were easy to implement, then the ideal place to start would be "exact equivalence", references and all, and whittle down from there.
To keep the order of the nodes I would keep two stacks of DIEs that represent the path traveled so far. That way whether or not a DIE has already been seen is just whether it is already on the stack, and the "location" can just be expressed as the index of that DIE into the stack.
The comparator does a depth-first recursive traversal. So it has a live call frame associated with each DIE currently under consideration. Remembering anything beyond that is done by the tracker.
The comparison constructs a tracker::step object when it considers a pair of DIEs. This object and its destructor are what trigger the tracker code to record where we are right now. It tracks each of the two parallel walks with a dwarf_path_finder. Each of these holds a a stack of DIEs, called a die_path in the code.
A step on the walk (tracker::step -> dwarf_path_finder::step) pushes the new DIE on the stack. It also records the whole current stack in a map keyed by that DIE's identity. Looking these up are how we can consider the "context" when we have an attribute reference to this DIE later on.
Does any of the above make sense? Is this what the comparator/tracker logic does? Are there wrinkles in the above logic that make it more involved? What kind of caching should be added to make the above easier/better/faster?
You've asked a lot and we'll have to get to it a bit at a time.
I'm not sure I followed exactly what you meant about a stack or how it relates to the tracking we have going on now.
The definition of "equal" is recursive, in that for two DIEs to be equal their references have to be to equal DIEs. Yet the referenced DIEs may have references of their own that have to be compared. After one step or many steps, references could lead back to the first DIE. Not only do you have to terminate, but two DIEs with congruently circular references must be considered equal.
If you follow forward references immediately to answer the equality question, you will cover lots of the tree out of order relative to the main comparison walk. If you did no caching, you would repeat many subtree comparisons many many times.
So the tracker also records equivalences. If you compare two subtrees once in the main walk, you want to record that they were or weren't equal, so that you know that answer immediately when you later come across a need to compare reference attributes pointing to each. Likewise, if you follow a forward reference and compare referenced subtrees, you want to record that result so that when you come across that subtree later in the main walk (or again via another reference) then you don't repeat that comparison.
tracker::reference_match is an untidy mashup of both the attempts at handling circularities and the caching of comparison results. It isn't doing either correctly.
Thanks, Roland
On Fri, 2010-07-16 at 02:17 -0700, Roland McGrath wrote:
- For two DIEs to be equal the attribute values of the attributes with the same key names that have references to DIEs as value should: a) Be both not yet seen DIEs in the respective trees so far, and be equal DIEs (in this case we can just treat the attribute reference as we would a child DIE, compare it in order). Or: b) Be both already seen DIEs in the respective trees so far, and be in the "same location".
I don't understand the "already seen" or not distinction here. Whether they are forward references or not doesn't matter in any way I can think of (except in how you'd implement it, of course). Regardless, you need the subtrees to be equal and their locations to be equivalent.
I make that distinction because I really would like to see the equivalence as comparing two lists (the depth-first search paths) of nodes (DIEs). This might confuse matters a little since we go from concept to comparison algorithm immediately.
To me we are comparing paths, and "already seen" nodes/dies are just things that have to be the same on both paths.
The "same location" means that the references to the DIEs in the trees are at the same place if we would walk the tree in the order chosen above.
Approximately, yes. I've called this "equivalent context" rather than "same location" to abstract it a little.
The definition for "exact equivalence" I mean is that each parent DIE has matching attributes and equivalent parents. That's a recursive definition, so it iterates on up to the root of the tree (the CU).
Why the CU? Isn't the start the starting DIE(s) of the comparison? The CU seems to be just another DIE that might be in the (flattened) path (both CU DIEs should of course be equivalent if the appear in a depth-first walk of the tree).
For the overall goal of maximal sharing constrained only by the real high-level semantic needs to avoid wrong conflations, we'll want some flexibility to ignore some kinds of attribute differences.
This decision is encoded in dwarf_comparator::equal_enough. The current definition of "equal enough" is that we ignore the reference attributes. That's as much as anything else just because another vector of complex equality checking with references would just make things even harder to think about. In practice, I'm pretty sure the differences between "context" DIEs that matter semantically are not in their references.
I am not sure I am following that. Isn't what they reference precisely what makes them similar or not?
To keep the order of the nodes I would keep two stacks of DIEs that represent the path traveled so far. That way whether or not a DIE has already been seen is just whether it is already on the stack, and the "location" can just be expressed as the index of that DIE into the stack.
The comparator does a depth-first recursive traversal. So it has a live call frame associated with each DIE currently under consideration. Remembering anything beyond that is done by the tracker.
And that is indeed the part I find somewhat hard to understand. In my (simplistic) view all you need is the depth-first recursive traversal (keep track of circularity, mark them, stop recursing, and check it is the same circular reference in both walks). And if the full walk in both trees finds the exact same path with the exact same nodes in both you are done, they are similar.
I'm not sure I followed exactly what you meant about a stack or how it relates to the tracking we have going on now.
The stack is just my way of expressing we keep the path of DIEs traveled so far. It is just keeping track of when we saw which DIE. And if any deeper reference points to a DIE we already seen it will be on that stack (path) and for the other DIE tree to be equivalent it needs to have a DIE reference to exactly the same point in the stack (path) we are constructing while walking the other DIE tree.
If you follow forward references immediately to answer the equality question, you will cover lots of the tree out of order relative to the main comparison walk. If you did no caching, you would repeat many subtree comparisons many many times.
I don't doubt that without caching things might be somewhat inefficient. But the caching confuses me somewhat, so for now I am trying to ignore it. Wouldn't we see every subtree only once, since we are just walking the tree from starting DIE in a specific order (breaking cycles when we notice we already seen a DIE node earlier in the walk)?
Cheers,
Mark
I make that distinction because I really would like to see the equivalence as comparing two lists (the depth-first search paths) of nodes (DIEs). This might confuse matters a little since we go from concept to comparison algorithm immediately.
Ok, I see what you mean. You are talking about the entire walk here when you say a "path".
The definition for "exact equivalence" I mean is that each parent DIE has matching attributes and equivalent parents. That's a recursive definition, so it iterates on up to the root of the tree (the CU).
Why the CU? Isn't the start the starting DIE(s) of the comparison? The CU seems to be just another DIE that might be in the (flattened) path (both CU DIEs should of course be equivalent if the appear in a depth-first walk of the tree).
It sounds like we are talking past each other here. This paragraph is all about the "context". For "context" we are only talking about the tree path, not any path walking references.
I am not sure I am following that. Isn't what they reference precisely what makes them similar or not?
Which "what"? The contents of a subtree is not all that matters.
Consider these two trees:
<compile_unit> <namespace name="a"> <class_type name="foo"> <member name="x"/> </class_type> </namespace> <variable name="v" type="#ref to a::foo"/> </compile_unit>
<compile_unit> <namespace name="b"> <class_type name="foo"> <member name="x"/> </class_type> </namespace> <variable name="v" type="#ref to b::foo"/> </compile_unit>
Now, are the two "v" entries equal? They are if their type attribute references are equal. If "what they reference" means just the subtree, then both those "foo" subtrees are identical.
But it would be wrong to conflate these two references together and thus call each "v" equal to the other. One has type a::foo and one has type b::foo, and never the twain shall meet.
And that is indeed the part I find somewhat hard to understand. In my (simplistic) view all you need is the depth-first recursive traversal (keep track of circularity, mark them, stop recursing, and check it is the same circular reference in both walks). And if the full walk in both trees finds the exact same path with the exact same nodes in both you are done, they are similar.
It's not quite clear to me what this traversal order is with respect to references. The comparator checks attributes first, then children, so its walk follows references depth-first, then children depth-first, at each node.
The stack is just my way of expressing we keep the path of DIEs traveled so far. It is just keeping track of when we saw which DIE. And if any deeper reference points to a DIE we already seen it will be on that stack (path) and for the other DIE tree to be equivalent it needs to have a DIE reference to exactly the same point in the stack (path) we are constructing while walking the other DIE tree.
Ok. I think this is similar to what the core of the reference_match logic does. Your stack is the call frame stack. Each recursion records a pointer in a map keyed by the lhs DIE identity. It checks this map for an existing entry, and looks at this record. What that records is the rhs DIE identity that recursion is comparing the lhs to. So if that record matches the rhs we are comparing to now, then the circularities match.
I don't doubt that without caching things might be somewhat inefficient. But the caching confuses me somewhat, so for now I am trying to ignore it. Wouldn't we see every subtree only once, since we are just walking the tree from starting DIE in a specific order (breaking cycles when we notice we already seen a DIE node earlier in the walk)?
I think that makes sense, yes.
Thanks, Roland
On Fri, 2010-07-16 at 03:38 -0700, Roland McGrath wrote:
Which "what"? The contents of a subtree is not all that matters.
Consider these two trees:
<compile_unit> <namespace name="a"> <class_type name="foo"> <member name="x"/> </class_type> </namespace> <variable name="v" type="#ref to a::foo"/> </compile_unit>
<compile_unit> <namespace name="b"> <class_type name="foo"> <member name="x"/> </class_type> </namespace> <variable name="v" type="#ref to b::foo"/> </compile_unit>
Now, are the two "v" entries equal? They are if their type attribute references are equal. If "what they reference" means just the subtree, then both those "foo" subtrees are identical.
But it would be wrong to conflate these two references together and thus call each "v" equal to the other. One has type a::foo and one has type b::foo, and never the twain shall meet.
Thanks for that example! OK, I did completely miss that. So for each DIE to be considered equal you also need to account for the "context path" from the root (CU). Which is a secondary tree walk... Except that for this walk you might care about different attributes of the DIEs to take into consideration for determining what counts as "equal" (I am not yet really clear which attributes matter for the context path and which don't).
And that is indeed the part I find somewhat hard to understand. In my (simplistic) view all you need is the depth-first recursive traversal (keep track of circularity, mark them, stop recursing, and check it is the same circular reference in both walks). And if the full walk in both trees finds the exact same path with the exact same nodes in both you are done, they are similar.
It's not quite clear to me what this traversal order is with respect to references. The comparator checks attributes first, then children, so its walk follows references depth-first, then children depth-first, at each node.
It shouldn't matter. Just pick one and be consistent. Either first follow all attribute references (in a particular deterministic order) or the children. As long as it is clear what the expected order is. Only attribute references can create circles, but that seems just a technicality.
Thanks for the explanations. I think I now finally understand what the comparator/tracker try to match up.
Cheers,
Mark
(I am not yet really clear which attributes matter for the context path and which don't).
It's not really well-established yet. We'll want to tune that later on. To a first approximation, we can say it's none of the attributes of the root compile_unit entry, and all of the attributes of other levels of the tree.
It shouldn't matter. Just pick one and be consistent. Either first follow all attribute references (in a particular deterministic order) or the children. As long as it is clear what the expected order is. Only attribute references can create circles, but that seems just a technicality.
Right. Since non-reference attributes are most of the actual "meat", it's natural to compare attributes before children, since in a mismatch usually the simply-valued attributes won't match. This makes attribute references before children seem like the natural order as to the graph walking.
Here's another example to consider. (I'll use "id" as a fake attribute to indicate what entry reference attributes point to.)
<compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p2"/> <pointer_type id="p2" type="#t1"/> </compile_unit> vs <compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p1"/> </compile_unit>
Now, compare just the "v" entry. In the first file, the walk goes: "v" -> p2 -> t1 -> "next" -> p1 -> t1 * CYCLE In the second file, it goes: "v" -> p1 -> t1 -> "next" -> p1 * CYCLE
But, these two "v" entries are equal. When you hit it, you know you have a cycle on the rhs, but don't have a cycle on the lhs. You can't tell that the parallel p1's are equal or aren't until you follow the lhs further.
In the actual case, the second file is a compressed version of the first file, where the logical tree looks like:
<compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p1"/> <pointer_type id="p1" type="#t1"/> </compile_unit>
because both "p1" nodes (or whole subtrees if they were that) are actually the same physical thing with imported_unit entries telling us to synthesize a logical tree view with that subtree grafted in at two places. So then, both whole compile_unit trees are entirely equal, not just the walk rooted at "v".
Thanks, Roland
On Fri, 2010-07-16 at 04:55 -0700, Roland McGrath wrote:
Here's another example to consider. (I'll use "id" as a fake attribute to indicate what entry reference attributes point to.)
<compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p2"/> <pointer_type id="p2" type="#t1"/> </compile_unit> vs <compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p1"/> </compile_unit>
Now, compare just the "v" entry. In the first file, the walk goes: "v" -> p2 -> t1 -> "next" -> p1 -> t1 * CYCLE In the second file, it goes: "v" -> p1 -> t1 -> "next" -> p1 * CYCLE
But, these two "v" entries are equal. When you hit it, you know you have a cycle on the rhs, but don't have a cycle on the lhs. You can't tell that the parallel p1's are equal or aren't until you follow the lhs further.
Nice example. Although you are getting somewhat greedy I what you want to recognize as equal :)
If you want to recognize such situations you seem to have to do a full duplication/equality check on each new DIE node in your walk against all previous encountered DIEs (and not just compare against the IDs of the DIEs already seen). And if the new DIE is equal to any already encountered you mark it as a cycle to that one instead of treating it as a new one. In your example in CU1 we see p1, notice it is equal to p2 and so create a cycle to it in the walk. Which makes the CU1-v and CU2-v walks the same.
That seems rather expensive. No wonder you go crazy about caching these equalities.
In the actual case, the second file is a compressed version of the first file, where the logical tree looks like:
<compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p1"/> <pointer_type id="p1" type="#t1"/> </compile_unit>
because both "p1" nodes (or whole subtrees if they were that) are actually the same physical thing with imported_unit entries telling us to synthesize a logical tree view with that subtree grafted in at two places. So then, both whole compile_unit trees are entirely equal, not just the walk rooted at "v".
I am not completely following this example. So we have two DIE nodes with the exact same identifier. Wouldn't we just treat those always equal anyway?
Cheers,
Mark
On Fri, 2010-07-16 at 14:51 +0200, Mark Wielaard wrote:
On Fri, 2010-07-16 at 04:55 -0700, Roland McGrath wrote:
Here's another example to consider. (I'll use "id" as a fake attribute to indicate what entry reference attributes point to.)
<compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p2"/> <pointer_type id="p2" type="#t1"/> </compile_unit> vs <compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p1"/> </compile_unit>
Now, compare just the "v" entry. In the first file, the walk goes: "v" -> p2 -> t1 -> "next" -> p1 -> t1 * CYCLE In the second file, it goes: "v" -> p1 -> t1 -> "next" -> p1 * CYCLE
But, these two "v" entries are equal. When you hit it, you know you have a cycle on the rhs, but don't have a cycle on the lhs. You can't tell that the parallel p1's are equal or aren't until you follow the lhs further.
Nice example. Although you are getting somewhat greedy in what you want to recognize as equal :)
If you want to recognize such situations you seem to have to do a full duplication/equality check on each new DIE node in your walk against all previous encountered DIEs (and not just compare against the IDs of the DIEs already seen). And if the new DIE is equal to any already encountered you mark it as a cycle to that one instead of treating it as a new one. In your example in CU1 we see p1, notice it is equal to p2 and so create a cycle to it in the walk. Which makes the CU1-v and CU2-v walks the same.
That seems rather expensive.
Thinking about it a bit more it seems a bit less expensive than what I described before. You don't need to proof equivalence between every DIE node on the path. Just if you come across a cycle (back reference to a point on the walk-path) on one, only then you have to proof that the next DIE node on the other path is equal (or identical) to the same DIE node in the same place on the other walk-path. Still seems somewhat expensive though.
And I do need to convince myself that this will actually terminate in the case of crazy double double equal DIE nodes in the graph.
Phew,
Mark
Nice example. Although you are getting somewhat greedy I what you want to recognize as equal :)
Thosea are the correct semantics, even by your problem description.
If you want to recognize such situations you seem to have to do a full duplication/equality check on each new DIE node in your walk against all previous encountered DIEs (and not just compare against the IDs of the DIEs already seen). And if the new DIE is equal to any already encountered you mark it as a cycle to that one instead of treating it as a new one. In your example in CU1 we see p1, notice it is equal to p2 and so create a cycle to it in the walk. Which makes the CU1-v and CU2-v walks the same.
That's not how I approached it in dwarfcmp. But that is similar to the approach in dwarf_output, where "comparison" is only part of the issue.
In the actual case, the second file is a compressed version of the first file, where the logical tree looks like:
<compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p1"/> <pointer_type id="p1" type="#t1"/> </compile_unit>
because both "p1" nodes (or whole subtrees if they were that) are actually the same physical thing with imported_unit entries telling us to synthesize a logical tree view with that subtree grafted in at two places. So then, both whole compile_unit trees are entirely equal, not just the walk rooted at "v".
I am not completely following this example. So we have two DIE nodes with the exact same identifier. Wouldn't we just treat those always equal anyway?
I don't understand this question.
Thanks, Roland
On Fri, 2010-07-16 at 13:05 -0700, Roland McGrath wrote:
Nice example. Although you are getting somewhat greedy in what you want to recognize as equal :)
Those are the correct semantics, even by your problem description.
Yes, they are semantically equal. I was just pointing out that this is an extra syntactical equivalence recognition step. These do add up. The concern is more with the added complexity. It might not be that bad in practice though.
That's not how I approached it in dwarfcmp. But that is similar to the approach in dwarf_output, where "comparison" is only part of the issue.
OK, so some of the equivalence detection can be done when we read in the original DIEs and others when we write out the DIEs again.
In the actual case, the second file is a compressed version of the first file, where the logical tree looks like:
<compile_unit> <structure_type id="t1" name="list"> <member name="next" type="#p1"/> </structure_type> <pointer_type id="p1" type="#t1"/> <variable name="v" type="#p1"/> <pointer_type id="p1" type="#t1"/> </compile_unit>
because both "p1" nodes (or whole subtrees if they were that) are actually the same physical thing with imported_unit entries telling us to synthesize a logical tree view with that subtree grafted in at two places. So then, both whole compile_unit trees are entirely equal, not just the walk rooted at "v".
I am not completely following this example. So we have two DIE nodes with the exact same identifier. Wouldn't we just treat those always equal anyway?
I don't understand this question.
We talked about this a little on irc. Just for the list. The example was just to highlight that the physical tree (where imported_unit entries are not expanded) is simpler to compare because there are equal nodes that don't need any walking. (dwarflint could/can check that imported_unit subtrees are used only in equivalent context.)
Cheers,
Mark
Yes, they are semantically equal. I was just pointing out that this is an extra syntactical equivalence recognition step. These do add up. The concern is more with the added complexity. It might not be that bad in practice though.
This is just the first example of new complexity. My ad hoc algorithm covered that much (not clear how efficiently), but there was more to come along in practice. And everything was too slow, though it's still not entirely clear how much of that was algorithmic. So, the task is to handle all possible complexity as efficiently as we can.
That's not how I approached it in dwarfcmp. But that is similar to the approach in dwarf_output, where "comparison" is only part of the issue.
OK, so some of the equivalence detection can be done when we read in the original DIEs and others when we write out the DIEs again.
I don't really follow this comment at all.
The mandate for dwarfcmp is to handle any valid physical formulation of each input and say correctly whether they are semantically equivalent, and there is no writing out involved at all there.
The existing design for dwarf_output has two phases: copy construction, which is what drives all the reading and creation of internal memory representations of CUs; and output, where format writing is done. All of the duplicate detection is part of the first phase.
We haven't really talked about that whole design yet to establish a shared vocabulary, so picking apart your remark this way is probably premature. But, I really don't know what you meant.
We talked about this a little on irc. Just for the list. The example was just to highlight that the physical tree (where imported_unit entries are not expanded) is simpler to compare because there are equal nodes that don't need any walking. (dwarflint could/can check that imported_unit subtrees are used only in equivalent context.)
Yes. Petr, this should go on the to-do list for dwarflint. (Where is that list kept?) Multiple DW_TAG_imported_unit DIEs referring to a given CU (partial_unit or compile_unit DIE) must appear in equivalent contexts. That is, be owned by a DIE of the same tag and equal-enough attributes, in an equivalent context (iterate). Eventually we'll probably have some user knobs and common code for the equal-enough predicate's meaning.
Thanks, Roland
On Mon, 2010-07-19 at 17:55 -0700, Roland McGrath wrote:
OK, so some of the equivalence detection can be done when we read in the original DIEs and others when we write out the DIEs again.
I don't really follow this comment at all.
That is probably because I assumed something worked in a certain way based on the name, and I didn't yet grok the code.
The mandate for dwarfcmp is to handle any valid physical formulation of each input and say correctly whether they are semantically equivalent, and there is no writing out involved at all there.
The existing design for dwarf_output has two phases: copy construction, which is what drives all the reading and creation of internal memory representations of CUs; and output, where format writing is done. All of the duplicate detection is part of the first phase.
OK thanks, that was my misunderstanding then.
BTW. I do think it is good to be explicit about the classes of equivalence we can/want/do detect. It is sometimes very easy for us humans to say "look semantically equivalent", while the (syntactical) comparisons needed to proof such equivalence are pretty involved. And it would allow us to more easily experiment with turning some of them off. Like we have for context equivalence (equal-enough).
We haven't really talked about that whole design yet to establish a shared vocabulary, so picking apart your remark this way is probably premature. But, I really don't know what you meant.
No, please do pick them apart. It probably shows sloppy thinking/bad interpretation of the code if I say things which don't are rooted in any logical universe :)
I was just thinking about how/when detecting what kinds of equivalence is the most opportune. My thinking was that some comparisons are easier/cheaper done when we are already doing some transformation on (reading in/writing out) the whole DIE tree already.
Cheers,
Mark
BTW. I do think it is good to be explicit about the classes of equivalence we can/want/do detect. It is sometimes very easy for us humans to say "look semantically equivalent", while the (syntactical) comparisons needed to proof such equivalence are pretty involved. And it would allow us to more easily experiment with turning some of them off. Like we have for context equivalence (equal-enough).
Agreed. I guess I thought it was all fairly explicit, once I'd mentioned about the equal-enough predicate for context DIE attributes.
I was just thinking about how/when detecting what kinds of equivalence is the most opportune. My thinking was that some comparisons are easier/cheaper done when we are already doing some transformation on (reading in/writing out) the whole DIE tree already.
Oh, sure. That is, some of the things dwarf_output is doing might be things a pure comparator should do to be efficient. Yeah, perhaps. I mean, it's certainly true that a goal of dwarf_output is that subtrees that should be equivalent to dwarfcmp have equal .identity () (i.e. pointer equality) when you get them constructed in the dwarf_output object. So one way to do "pure" comparison is to just do that and throw away the collected output objects rather than write anything. But part of the point of dwarfcmp is to be a least partly independent implementation of the pure correct semantic comparison logic so that it serves usefully as a validating test on what dwarf_output does.
Thanks, Roland
Hi -
On Fri, Jul 16, 2010 at 02:17:08AM -0700, Roland McGrath wrote:
[...] tracker::reference_match is an untidy mashup of both the attempts at handling circularities and the caching of comparison results. It isn't doing either correctly.
My guess is that you will need to do these comparisons bottom-up, and hash/memoize the heck out of them, in order to prevent exponential time.
- FChE
elfutils-devel@lists.fedorahosted.org