On Wed, Jan 14, 2009 at 11:03 PM, Bryan Ischo <bji-keyword-pacman.3644cb@www.ischo.com> wrote:
Sorry about that, I discovered after composing my first 4 patches that I hadn't yet removed the logging as requested by Nagy. After spending hours crafting 4 patches out of my one big patch, I didn't feel like repeating the process just to remove a couple of log lines. Although, I am sure I could have crafted the patches much more quickly the second time around since I really knew what I was doing after the first time.
I know how it is, I was also very inefficient the first time (or the first few times) I did a specific task with git. But after the initial difficulties, it is very pleasant to use. Btw "git rebase -i" is very nice for this task, so I would suggest reading about it if you don't use it already.
Otherwise about your patchset, I am still not convinced that this is the smallest and best implementation possible. I would say the patches themselves are readable and well written, with good comments, etc. But I would still like to give more thinking to it and to explore other alternative ways. Last thing, Nagy seems to have given these patches a closer look, and he did a lot of good work on that deps.c file in my opinion, so I would like to know his overall feeling about this patchset now 8)
Well I'd love to hear feedback that's specific about the methods used. Nagy has provided detailed and specific feedback which has been very helpful. I too would like to hear Nagy's overall feeling about the patchset. I think I addressed all of his concerns, except for one which I didn't quite understand and for which I have asked for clarifying comments.
The only other way I could see doing it would involve a much larger rework of the existing codebase. What I did was insert as little code as I could to track the dependencies such that I could calculate which set of packages needed to be removed due to unresolved dependencies. Probably existing data structures could be modified to contain this information; however, I am not sure where else it would be used, even if it were collapsed into other existing data structures. And I am sure that this approach would require more significant rewrite of the existing _alpm_resolvedeps function than my approach did.
As an aside, I think part of the problem is that the code base tries to shoehorn everything into a single list type. When a doubly linked list is your only real data structure, the algorithms have to be more complex, and in the case of managing dependents (instead of dependencies), there is no choice but to introduce new data structures. Well, that's not entirely true. Probably my change could have used a linked list of linked lists, where each linked list was rooted at a package and contained all dependents of that package. There would be alot of redundant information in such a data structure and it would be much more difficult to manage than the graph structure I have introduced, but it could be done, I am sure.
Much larger rework is fine as long as we introduce significant benefits. I do think that integrating a well adapted data structure for dependencies checking / resolving is a worthy goal and we should seriously consider that, because as you said, it would allow simpler algorithms, and probably better and more efficient code overall. As you may have seen, we already have some kind of graph structure in graphs.h, used by the sortbydeps function in deps.c. If this structure is too specific / not general enough for all the usages we might have, we should try to fix that. And its current usage is unfortunately very localized.