Stage II Dependency tree optimization. Intermediate virtual patch removal.
First what need to be done - all virtual patches should be eliminated. I create full tree which represents each revision and in result for one System patch with revision 20 it will be 19 virtual patches created from 1 to 19. It is reasonable to have because other patch may require revision 7 and it will be simple linked to virtual revision 7 and this way we may trace up to existed revision 20. But it will be better, after all this relations set - after stage II when no changes no additional data will be for dependancy tree, to minimize all this consecutive link and merge them all into one. This is simple operation to each virtual patch I takes all links leading to it and then relink them to parent - if parent exist. This is cellular auomate kind of operation - simple rule applied to all objects (also good for performance). In result all intermediate virtual patches will be removed from the tree. Virtual patches which are on top of the inheritance line will remain in the tree. So if somebody require patch which is not present and has no descendants it will stay in the tree and represents this reference for following dependancy check. This operation is not recursive. In addition to removing patch from the tree it is also marked as Virtual_Removed - for additional control, if somehow I will hit this patch later it will indicates that something going wrong. Incompatible links upraising. Incompatible relation is very complicated. The problem is that it is only one place were it is defined. One patch declare other incompatible. But this actually mean that the other one and all patches up in inheritance line will be also incompatible. To check some patch in terms of it being incompatible this way I have to go down by inheritance tree and check in any ancestors are declared as incompatible by some other patch.This operation has opposite direction to recursive path I have in dependancy check and so instead of cameing up with complicated two-way recursive algorithm I decide to do tree optimization instead and if one patch declare other as incompatible I multiply this relation to each descendant of that declared as incompatible patch. So when I need to check was it declared as incompatible I will have direct link to analyze. This is simple recursive operation I run for each patch which has incompatible relation set up - just copy incompatible links up to the inheritance line. Package sharing. Next optimization I have is to handle partially installed patches. When I load installed patches I create bidirectional link between patches and packages and this mean that package is patched. When I load requested to install patches I creates unidirectional links and this mean that package is not patched and so this patch is partially installed. Inheritance, of course, complicates this. For example we may have patch partially installed and also obsoleted by other patch which already present on the system which also did not deliver changes to same package and so also partially installed, but we do not have it available to reinstall - it is not among requested to install patches. Even first partially installed patch is obsoleted we still should reapply it and fix inconsistency for that package. But if descendant did deliver changes to package - then we should not reapply that partially installed patch. For this reason I propagate bidirectional package link down the inheritance tree. I can not copy all packages down because descendant may have more packages then ancestor due to accumulation and in case of merging two patches and direct inheritance also package areas are merged and so should not be propagated to all ancestor branches. To do this I have two step optimization - first I propagates up monodirectional package links to make sure that all packages listed in requested to install patch will be listed also for all its descendant up the inheritance tree. This way all packages up to the tree from partially installed will have same packages referenced (as a subset). Then I propagates bidirectional links down the inheritance tree, but I copy bidirectional link down only if correspondent monodirectional link presents. In result some of partially installed patches will turn into fully installed if they got bidirectional link set from their descendants. It is very simple algorithmically - same cellular automates model: 1. Copy monodirectional links up recursively. 2. Copy bidirectional links down recursively. But in result pretty complicated problem - inheritance of partially installed patches (I was really enjoying programming this...). At that point 1. All unnecessary virtual patches will be removed and so length of the tree to analyze will be dramatically reduced. 2. Incompatible relation will be set for all patches involved. 3. Only real partially installed patches will be left in the structure, all obsoleted will be reset to "System" state. vassun This message posted from opensolaris.org
