)]}'
{"placement/objects/allocation_candidate.py":[{"author":{"_account_id":11564,"name":"Chris Dent","email":"cdent@anticdent.org","username":"chdent"},"change_message_id":"74198e10a204b0ef5a2492c34b8380025bba4d6f","unresolved":false,"context_lines":[{"line_number":710,"context_line":"    areq_lists_by_anchor \u003d collections.defaultdict("},{"line_number":711,"context_line":"        lambda: collections.defaultdict(list))"},{"line_number":712,"context_line":"    # Save off all the provider summary ids - we\u0027ll use \u0027em later."},{"line_number":713,"context_line":"    all_psums \u003d set()"},{"line_number":714,"context_line":"    # Construct a dict, keyed by resource provider + resource class, of"},{"line_number":715,"context_line":"    # ProviderSummaryResource.  This will be used to do a final capacity"},{"line_number":716,"context_line":"    # check/filter on each merged AllocationRequest."}],"source_content_type":"text/x-python","patch_set":1,"id":"7faddb67_8cdf59d5","line":713,"updated":"2019-08-09 12:40:15.000000000","message":"this could be a dict to which a relevant summary is added and then the list comp at the end might not be quite some cumbersome","commit_id":"14f39a3e91f50b8dd298eae4f2617cade91f2c78"},{"author":{"_account_id":14070,"name":"Eric Fried","email":"openstack@fried.cc","username":"efried"},"change_message_id":"52f99812557f170871433a45927216c8f11d3ac5","unresolved":false,"context_lines":[{"line_number":149,"context_line":"                areq.use_same_provider \u003d group.use_same_provider"},{"line_number":150,"context_line":"            candidates[suffix] \u003d alloc_reqs"},{"line_number":151,"context_line":""},{"line_number":152,"context_line":"        # At this point, each (alloc_requests, summary_obj) in `candidates` is"},{"line_number":153,"context_line":"        # independent of the others. We need to fold them together such that"},{"line_number":154,"context_line":"        # each allocation request satisfies *all* the incoming `requests`.  The"},{"line_number":155,"context_line":"        # `candidates` dict is guaranteed to contain entries for all suffixes,"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_f0c80276","line":152,"range":{"start_line":152,"start_character":30,"end_line":152,"end_character":59},"updated":"2019-08-12 17:16:48.000000000","message":"I think this isn\u0027t right anymore","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":11564,"name":"Chris Dent","email":"cdent@anticdent.org","username":"chdent"},"change_message_id":"09935706b29fe4190fc1e4d009c5bc89a4d0e116","unresolved":false,"context_lines":[{"line_number":496,"context_line":"    # Build up a dict, keyed by internal resource provider ID, of"},{"line_number":497,"context_line":"    # ProviderSummary objects containing one or more ProviderSummaryResource"},{"line_number":498,"context_line":"    # objects representing the resources the provider has inventory for."},{"line_number":499,"context_line":"    for usage in pared_usages:"},{"line_number":500,"context_line":"        rp_id \u003d usage[\u0027resource_provider_id\u0027]"},{"line_number":501,"context_line":"        summary \u003d rw_ctx.summaries_by_id.get(rp_id)"},{"line_number":502,"context_line":"        if not summary:"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_d86ae8eb","line":499,"updated":"2019-08-09 18:13:13.000000000","message":"So, it turns out that this loop is now the big consumer of cpu. In the nested-perfload setup we process 9000 pared_usages and internal to this loop (not creating the objects, not calling other methods) the python adds up to 11.42% of total time.\n\nI\u0027m pretty sure 9000 is the expected amount here and the check above causes a second _build_provider_summaries to exit early.\n\nSo this isn\u0027t really a question of us needing to send in less data, just that the processing is expensive. So there may be nothing to do here, but if people have ideas, shout.","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":11564,"name":"Chris Dent","email":"cdent@anticdent.org","username":"chdent"},"change_message_id":"8630a13b1bb97b531cd5475b11ff26344a5f64d3","unresolved":false,"context_lines":[{"line_number":496,"context_line":"    # Build up a dict, keyed by internal resource provider ID, of"},{"line_number":497,"context_line":"    # ProviderSummary objects containing one or more ProviderSummaryResource"},{"line_number":498,"context_line":"    # objects representing the resources the provider has inventory for."},{"line_number":499,"context_line":"    for usage in pared_usages:"},{"line_number":500,"context_line":"        rp_id \u003d usage[\u0027resource_provider_id\u0027]"},{"line_number":501,"context_line":"        summary \u003d rw_ctx.summaries_by_id.get(rp_id)"},{"line_number":502,"context_line":"        if not summary:"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_d0af0629","line":499,"in_reply_to":"7faddb67_b0e92ae4","updated":"2019-08-12 16:14:12.000000000","message":"I\u0027m not really sure. It seems that a 9000 element loop, with the associated builtins within the loop simply adds up.\n\nOf course this is relatively speaking. Everything is much less consuming, in the absolute, than it was a couple weeks ago.","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":9708,"name":"Balazs Gibizer","display_name":"gibi","email":"gibizer@gmail.com","username":"gibi"},"change_message_id":"0d879a9b5864be87b95c87763bcbed7fa40b49d1","unresolved":false,"context_lines":[{"line_number":496,"context_line":"    # Build up a dict, keyed by internal resource provider ID, of"},{"line_number":497,"context_line":"    # ProviderSummary objects containing one or more ProviderSummaryResource"},{"line_number":498,"context_line":"    # objects representing the resources the provider has inventory for."},{"line_number":499,"context_line":"    for usage in pared_usages:"},{"line_number":500,"context_line":"        rp_id \u003d usage[\u0027resource_provider_id\u0027]"},{"line_number":501,"context_line":"        summary \u003d rw_ctx.summaries_by_id.get(rp_id)"},{"line_number":502,"context_line":"        if not summary:"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_b0e92ae4","line":499,"in_reply_to":"7faddb67_d86ae8eb","updated":"2019-08-12 16:07:32.000000000","message":"\u003e So, it turns out that this loop is now the big consumer of cpu. In\n \u003e the nested-perfload setup we process 9000 pared_usages and internal\n \u003e to this loop (not creating the objects, not calling other methods)\n\nDoes this mean that dict key insert like\n\n    rw_ctx.summaries_by_id[rp_id] \u003d summary\n\nor possible list resizing like\n\n       summary.resources.append(rpsr)\n\nout of the possible offenders in the cost?\n\n\n \u003e the python adds up to 11.42% of total time.\n \u003e \n \u003e I\u0027m pretty sure 9000 is the expected amount here and the check\n \u003e above causes a second _build_provider_summaries to exit early.\n \u003e \n \u003e So this isn\u0027t really a question of us needing to send in less data,\n \u003e just that the processing is expensive. So there may be nothing to\n \u003e do here, but if people have ideas, shout.","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":9708,"name":"Balazs Gibizer","display_name":"gibi","email":"gibizer@gmail.com","username":"gibi"},"change_message_id":"0d879a9b5864be87b95c87763bcbed7fa40b49d1","unresolved":false,"context_lines":[{"line_number":681,"context_line":"    produced."},{"line_number":682,"context_line":""},{"line_number":683,"context_line":"    :param candidates: A dict, keyed by suffix string or \u0027\u0027, of tuples of"},{"line_number":684,"context_line":"            (allocation_requests, provider_summary_ids) to be merged."},{"line_number":685,"context_line":"    :param rw_ctx: RequestWideSearchContext."},{"line_number":686,"context_line":"    :return: A tuple of (allocation_requests, provider_summaries)."},{"line_number":687,"context_line":"    \"\"\""}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_909c2e6b","line":684,"range":{"start_line":684,"start_character":34,"end_line":684,"end_character":54},"updated":"2019-08-12 16:07:32.000000000","message":"Isn\u0027t summaries removed from the candidates?","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":14070,"name":"Eric Fried","email":"openstack@fried.cc","username":"efried"},"change_message_id":"52f99812557f170871433a45927216c8f11d3ac5","unresolved":false,"context_lines":[{"line_number":680,"context_line":"    For that merged list of alloc_reqs, a corresponding provider_summaries is"},{"line_number":681,"context_line":"    produced."},{"line_number":682,"context_line":""},{"line_number":683,"context_line":"    :param candidates: A dict, keyed by suffix string or \u0027\u0027, of tuples of"},{"line_number":684,"context_line":"            (allocation_requests, provider_summary_ids) to be merged."},{"line_number":685,"context_line":"    :param rw_ctx: RequestWideSearchContext."},{"line_number":686,"context_line":"    :return: A tuple of (allocation_requests, provider_summaries)."},{"line_number":687,"context_line":"    \"\"\""}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_70a2d2af","line":684,"range":{"start_line":683,"start_character":64,"end_line":684,"end_character":55},"updated":"2019-08-12 17:16:48.000000000","message":"They\u0027re just AllocationRequestZ now, right?","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":11564,"name":"Chris Dent","email":"cdent@anticdent.org","username":"chdent"},"change_message_id":"8630a13b1bb97b531cd5475b11ff26344a5f64d3","unresolved":false,"context_lines":[{"line_number":681,"context_line":"    produced."},{"line_number":682,"context_line":""},{"line_number":683,"context_line":"    :param candidates: A dict, keyed by suffix string or \u0027\u0027, of tuples of"},{"line_number":684,"context_line":"            (allocation_requests, provider_summary_ids) to be merged."},{"line_number":685,"context_line":"    :param rw_ctx: RequestWideSearchContext."},{"line_number":686,"context_line":"    :return: A tuple of (allocation_requests, provider_summaries)."},{"line_number":687,"context_line":"    \"\"\""}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_b0ddaade","line":684,"range":{"start_line":684,"start_character":34,"end_line":684,"end_character":54},"in_reply_to":"7faddb67_909c2e6b","updated":"2019-08-12 16:14:12.000000000","message":"yeah, forgot to update that, good eye","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":14070,"name":"Eric Fried","email":"openstack@fried.cc","username":"efried"},"change_message_id":"52f99812557f170871433a45927216c8f11d3ac5","unresolved":false,"context_lines":[{"line_number":711,"context_line":"        for areq in areqs:"},{"line_number":712,"context_line":"            anchor \u003d areq.anchor_root_provider_uuid"},{"line_number":713,"context_line":"            areq_lists_by_anchor[anchor][suffix].append(areq)"},{"line_number":714,"context_line":"            for arr in areq.resource_requests:"},{"line_number":715,"context_line":"                arr_rp_id \u003d arr.resource_provider.id"},{"line_number":716,"context_line":"                summary \u003d rw_ctx.summaries_by_id[arr_rp_id]"},{"line_number":717,"context_line":"                parent_uuid_by_rp_uuid[summary.resource_provider.uuid] \u003d ("}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_70c89220","line":714,"updated":"2019-08-12 17:16:48.000000000","message":"wouldn\u0027t be a huge savings, but I\u0027m pretty sure we can\n\n if arr.resource_provider.uuid in parent_uuid_by_rp_uuid:\n     # We already processed this resource provider\n     continue","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":14070,"name":"Eric Fried","email":"openstack@fried.cc","username":"efried"},"change_message_id":"52f99812557f170871433a45927216c8f11d3ac5","unresolved":false,"context_lines":[{"line_number":799,"context_line":"    for areq in areqs:"},{"line_number":800,"context_line":"        for arr in areq.resource_requests:"},{"line_number":801,"context_line":"            tree_uuids.add(arr.resource_provider.root_provider_uuid)"},{"line_number":802,"context_line":"    psums \u003d ["},{"line_number":803,"context_line":"        rw_ctx.summaries_by_id[rp_id] for rp_id in rw_ctx.summaries_by_id"},{"line_number":804,"context_line":"        if rw_ctx.summaries_by_id[rp_id].resource_provider.root_provider_uuid"},{"line_number":805,"context_line":"        in tree_uuids]"},{"line_number":806,"context_line":""},{"line_number":807,"context_line":"    LOG.debug(\u0027Merging candidates yields %d allocation requests and %d \u0027"},{"line_number":808,"context_line":"              \u0027provider summaries\u0027, len(areqs), len(psums))"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_b0f60a5d","line":805,"range":{"start_line":802,"start_character":12,"end_line":805,"end_character":22},"updated":"2019-08-12 17:16:48.000000000","message":"/me discards same comment","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":9708,"name":"Balazs Gibizer","display_name":"gibi","email":"gibizer@gmail.com","username":"gibi"},"change_message_id":"0d879a9b5864be87b95c87763bcbed7fa40b49d1","unresolved":false,"context_lines":[{"line_number":799,"context_line":"    for areq in areqs:"},{"line_number":800,"context_line":"        for arr in areq.resource_requests:"},{"line_number":801,"context_line":"            tree_uuids.add(arr.resource_provider.root_provider_uuid)"},{"line_number":802,"context_line":"    psums \u003d ["},{"line_number":803,"context_line":"        rw_ctx.summaries_by_id[rp_id] for rp_id in rw_ctx.summaries_by_id"},{"line_number":804,"context_line":"        if rw_ctx.summaries_by_id[rp_id].resource_provider.root_provider_uuid"},{"line_number":805,"context_line":"        in tree_uuids]"},{"line_number":806,"context_line":""},{"line_number":807,"context_line":"    LOG.debug(\u0027Merging candidates yields %d allocation requests and %d \u0027"},{"line_number":808,"context_line":"              \u0027provider summaries\u0027, len(areqs), len(psums))"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_707ad2f0","line":805,"range":{"start_line":802,"start_character":0,"end_line":805,"end_character":22},"updated":"2019-08-12 16:07:32.000000000","message":"It would be a bit more readable if we iterate the values\n\n  psum \u003d [\n      summary for summary in rw_ctx.summaries_by_id.values()\n      if summary.resource_provider.root_provider_uuid\n      in tree_uuids]\n\nalso it is less dict key access.","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":11564,"name":"Chris Dent","email":"cdent@anticdent.org","username":"chdent"},"change_message_id":"8630a13b1bb97b531cd5475b11ff26344a5f64d3","unresolved":false,"context_lines":[{"line_number":799,"context_line":"    for areq in areqs:"},{"line_number":800,"context_line":"        for arr in areq.resource_requests:"},{"line_number":801,"context_line":"            tree_uuids.add(arr.resource_provider.root_provider_uuid)"},{"line_number":802,"context_line":"    psums \u003d ["},{"line_number":803,"context_line":"        rw_ctx.summaries_by_id[rp_id] for rp_id in rw_ctx.summaries_by_id"},{"line_number":804,"context_line":"        if rw_ctx.summaries_by_id[rp_id].resource_provider.root_provider_uuid"},{"line_number":805,"context_line":"        in tree_uuids]"},{"line_number":806,"context_line":""},{"line_number":807,"context_line":"    LOG.debug(\u0027Merging candidates yields %d allocation requests and %d \u0027"},{"line_number":808,"context_line":"              \u0027provider summaries\u0027, len(areqs), len(psums))"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_d001463b","line":805,"range":{"start_line":802,"start_character":0,"end_line":805,"end_character":22},"in_reply_to":"7faddb67_707ad2f0","updated":"2019-08-12 16:14:12.000000000","message":"yup, another good catch","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":14070,"name":"Eric Fried","email":"openstack@fried.cc","username":"efried"},"change_message_id":"52f99812557f170871433a45927216c8f11d3ac5","unresolved":false,"context_lines":[{"line_number":905,"context_line":"    \"\"\"Returns a set of uuids of ancestors for a given rp uuid\"\"\""},{"line_number":906,"context_line":"    if ancestors is None:"},{"line_number":907,"context_line":"        ancestors \u003d set([rp_uuid])"},{"line_number":908,"context_line":"    parent_uuid \u003d parent_uuid_by_rp_uuid.get(rp_uuid)"},{"line_number":909,"context_line":"    if parent_uuid is None:"},{"line_number":910,"context_line":"        return ancestors"},{"line_number":911,"context_line":"    ancestors.add(parent_uuid)"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_504a3683","line":908,"range":{"start_line":908,"start_character":18,"end_line":908,"end_character":53},"updated":"2019-08-12 17:16:48.000000000","message":"I don\u0027t understand why this change makes sense. Before, we were saying \"we know we registered rp_uuid in parent_uuid_by_rp_uuid; if its value is None it means rp_uuid represents a root provider\". Now we\u0027re saying \"we might have neglected to register rp_uuid; but if so, it\u0027s a root, promise\".\n\nUnder what circumstances could we have neglected to register rp_uuid? And why is that okay?\n\n[Later] Okay, I think I see. Now we\u0027re building parent_uuid_by_rp_uuid only based on the psums related to the ARRs under consideration. Whereas before we were building it based on *all* psums for all providers in the world.\n\nWhich means we have a bug. Because as written this will only work as long as we always have resources from at least one provider at most one level down from the root. Looklook:\n\n          root\n            |\n          child\n            |\n        grandchild\n\nRight now we\u0027re relying on there being an ARR for `root` (parent_uuid_by_rp_uuid[root] will be present, and None) or `child` (parent_uuid_by_rp_uuid[child] will be present, and point to `root`, but `root`  will be absent, but we\u0027re assuming its parent is None, which happens to be true).\n\nBut if we had no ARR for `root` or `child`, then we would look for `grandchild`\u0027s parent, which would be absent, and assume *its* parent is None, i.e. that `child` is a root, which it\u0027s not.\n\nSo\n\nWhat we need is a test case where resources (and... traits?) are only requested starting at the third tier, and such that the same_subtree algorithm should produce different results if we\u0027re only considering the subtree starting at `child` as \"the whole tree\".","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":9708,"name":"Balazs Gibizer","display_name":"gibi","email":"gibizer@gmail.com","username":"gibi"},"change_message_id":"304d636be45384a028e385634409474d71ea5183","unresolved":false,"context_lines":[{"line_number":905,"context_line":"    \"\"\"Returns a set of uuids of ancestors for a given rp uuid\"\"\""},{"line_number":906,"context_line":"    if ancestors is None:"},{"line_number":907,"context_line":"        ancestors \u003d set([rp_uuid])"},{"line_number":908,"context_line":"    parent_uuid \u003d parent_uuid_by_rp_uuid.get(rp_uuid)"},{"line_number":909,"context_line":"    if parent_uuid is None:"},{"line_number":910,"context_line":"        return ancestors"},{"line_number":911,"context_line":"    ancestors.add(parent_uuid)"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_7b9cce5a","line":908,"range":{"start_line":908,"start_character":18,"end_line":908,"end_character":53},"in_reply_to":"7faddb67_504a3683","updated":"2019-08-14 12:53:37.000000000","message":"\u003e I don\u0027t understand why this change makes sense. Before, we were\n \u003e saying \"we know we registered rp_uuid in parent_uuid_by_rp_uuid; if\n \u003e its value is None it means rp_uuid represents a root provider\". Now\n \u003e we\u0027re saying \"we might have neglected to register rp_uuid; but if\n \u003e so, it\u0027s a root, promise\".\n \u003e \n \u003e Under what circumstances could we have neglected to register\n \u003e rp_uuid? And why is that okay?\n \u003e \n \u003e [Later] Okay, I think I see. Now we\u0027re building parent_uuid_by_rp_uuid\n \u003e only based on the psums related to the ARRs under consideration.\n \u003e Whereas before we were building it based on *all* psums for all\n \u003e providers in the world.\n \u003e \n \u003e Which means we have a bug. Because as written this will only work\n \u003e as long as we always have resources from at least one provider at\n \u003e most one level down from the root. Looklook:\n \u003e \n \u003e root\n \u003e |\n \u003e child\n \u003e |\n \u003e grandchild\n \u003e \n \u003e Right now we\u0027re relying on there being an ARR for `root`\n \u003e (parent_uuid_by_rp_uuid[root] will be present, and None) or `child`\n \u003e (parent_uuid_by_rp_uuid[child] will be present, and point to\n \u003e `root`, but `root`  will be absent, but we\u0027re assuming its parent\n \u003e is None, which happens to be true).\n \u003e \n \u003e But if we had no ARR for `root` or `child`, then we would look for\n \u003e `grandchild`\u0027s parent, which would be absent, and assume *its*\n \u003e parent is None, i.e. that `child` is a root, which it\u0027s not.\n \u003e \n\nDo you mean we would think `grandchild` is a root not `child`?","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":14070,"name":"Eric Fried","email":"openstack@fried.cc","username":"efried"},"change_message_id":"44b35e9d7fe5ec199b80dcacc477b63f5e53d96f","unresolved":false,"context_lines":[{"line_number":905,"context_line":"    \"\"\"Returns a set of uuids of ancestors for a given rp uuid\"\"\""},{"line_number":906,"context_line":"    if ancestors is None:"},{"line_number":907,"context_line":"        ancestors \u003d set([rp_uuid])"},{"line_number":908,"context_line":"    parent_uuid \u003d parent_uuid_by_rp_uuid.get(rp_uuid)"},{"line_number":909,"context_line":"    if parent_uuid is None:"},{"line_number":910,"context_line":"        return ancestors"},{"line_number":911,"context_line":"    ancestors.add(parent_uuid)"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_1c034d12","line":908,"range":{"start_line":908,"start_character":18,"end_line":908,"end_character":53},"in_reply_to":"7faddb67_760aa026","updated":"2019-08-14 17:13:33.000000000","message":"Aha! I found one that breaks:\n\n(3A): same_subtree({G1.1, C2, R})\n - check_these \u003d {G1.1, C2, R}\n - ancestors_G1.1 \u003d {G1.1, C1, R}\n - ancestors_C2 \u003d {C2, R}\n - ancestors_R \u003d {R}\n - common_ancestors \u003d {G1.1, C1, R} \u0026 {C2, R} \u0026 {R} \u003d {R}\n - check_these \u0026 common_ancestors \u003d {G1.1, C2, R} \u0026 {R} \u003d {R}\n - return True\n\n(3B): same_subtree({G1.1, C2, R})\n - check_these \u003d {G1.1, C2, R}\n - ancestors_G1.1 \u003d {G1.1, C1}  \u003c\u003d\u003d l@@k, {R} is missing!\n - ancestors_C2 \u003d {C2, R}\n - ancestors_R \u003d {R}\n - common_ancestors \u003d {G1.1, C1} \u0026 {C2, R} \u0026 {R} \u003d {}\n - check_these \u0026 common_ancestors \u003d {G1.1, C2, R} \u0026 {} \u003d {}\n - return False\n\nSo generically, to trigger this problem, you have to have a \"hole\" in the ancestry tree. That is, the ancestry line of a provider involved in the request hits a provider *not* involved, and then hits another provider that *is* involved.","commit_id":"8547a8c08882f750eb150303c8417bf524115299"},{"author":{"_account_id":14070,"name":"Eric Fried","email":"openstack@fried.cc","username":"efried"},"change_message_id":"94097477d91dac7a306e1c87436b30be9bf0f7c0","unresolved":false,"context_lines":[{"line_number":905,"context_line":"    \"\"\"Returns a set of uuids of ancestors for a given rp uuid\"\"\""},{"line_number":906,"context_line":"    if ancestors is None:"},{"line_number":907,"context_line":"        ancestors \u003d set([rp_uuid])"},{"line_number":908,"context_line":"    parent_uuid \u003d parent_uuid_by_rp_uuid.get(rp_uuid)"},{"line_number":909,"context_line":"    if parent_uuid is None:"},{"line_number":910,"context_line":"        return ancestors"},{"line_number":911,"context_line":"    ancestors.add(parent_uuid)"}],"source_content_type":"text/x-python","patch_set":2,"id":"7faddb67_760aa026","line":908,"range":{"start_line":908,"start_character":18,"end_line":908,"end_character":53},"in_reply_to":"7faddb67_7b9cce5a","updated":"2019-08-14 17:02:32.000000000","message":"\u003e Do you mean we would think `grandchild` is a root not `child`?\n\nI... don\u0027t think so? I think I meant this:\n\nIf the grandchild is involved in the request, but the child is not, then when we recurse to build the ancestry for the grandchild, we\u0027ll do this:\n- grandchild.parent \u003d\u003e child\n- child.parent \u003d\u003e not in the dict, so assume None, and stop.\n\nWe only notice this if there is more than one \"empty\" (i.e. not involved in the request) tier above the provider for which we\u0027re trying to calculate ancestry.\n\nI still haven\u0027t fully noodled how (or even if) this would affect the same_subtree calculation. Lemme go do that now...\n\n[Later]\n\nOkay, so we\u0027re first intersecting the \"ancestry lines\" for all the providers we\u0027re checking for same_subtree-ness. This identifies all and only their common ancestors. By definition this first intersection should *always* include the root (ignoring sharing).\n\nThen we see whether any of the providers we\u0027re checking are in that set of common ancestors. (Actually I believe there can be at most one.) If so, we declare same_subtree to be true.\n\nUsing this example:\n\n              R\n            /   \\\n          C1     C2\n         /  \\      \\\n      G1.1  G1.2   G2\n\nScenarios (A), when the ancestry dict is fully populated:\n\nScenario (1A): same_subtree({C1, G1.1})\n - check_these \u003d {C1, G1.1}\n - ancestors_C1 \u003d {C1, R}\n - ancestors_G1.1 \u003d {G1.1, C1, R}\n - common_ancestors \u003d ancestors_C1 \u0026 ancestors_G1.1 \u003d {C1, R}\n - check_these \u0026 common_ancestors \u003d {C1, G1.1} \u0026 {C1, R} \u003d {C1}\n - This is nonempty, return True\n\nScenario (2A): same_subtree({C2, G1.1})\n - check_these \u003d {C2, G1.1}\n - ancestors_C2 \u003d {C2, R}\n - ancestors_G1.1 \u003d {G1.1, C1, R}\n - common_ancestors \u003d ancestors_C2 \u0026 ancestors_G1.1 \u003d {R}\n - check_these \u0026 common_ancestors \u003d {C2, G1.1} \u0026 {R} \u003d {}\n - This is empty, return False\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nSo what happens if that first intersection stops too early? It would exclude providers not involved in the request... but the second intersection would be excluding those anyway.\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n\nScenarios (B), when the ancestry dict only includes providers involved in the request:\n\nScenario (1B): same_subtree({C1, G1.1})\n - check_these \u003d {C1, G1.1}\n - ancestors_C1 \u003d {C1}  (*not* R)\n - ancestors_G1.1 \u003d {G1.1, C1}  (*not* R)\n - common_ancestors \u003d ancestors_C1 \u0026 ancestors_G1.1 \u003d {C1}\n - check_these \u0026 common_ancestors \u003d {C1, G1.1} \u0026 {C1} \u003d {C1}\n - This is nonempty, return True\n\nScenario (2B): same_subtree({C2, G1.1})\n - check_these \u003d {C2, G1.1}\n - ancestors_C2 \u003d {C2}  (*not* R)\n - ancestors_G1.1 \u003d {G1.1, C1}  (*not* R)\n - common_ancestors \u003d ancestors_C2 \u0026 ancestors_G1.1 \u003d {}\n - check_these \u0026 common_ancestors \u003d {C2, G1.1} \u0026 {} \u003d {}\n - This is empty, return False\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n\nSo after all that, I\u0027m pretty sure it totally doesn\u0027t matter, and this (by serendipity, not intent) was a valid optimization.\n\nI\u0027m pretty sure Chris\u0027s gabbi test [1] covers this ground, but it\u0027s pretty hard to rationalize at that high a level. So IMO it would be worthwhile to have unit test coverage. We already have test_check_same_subtree which exercises (A); it should be pretty easy to twiddle its parent_by_rp dict to exercise (B).\n\n\n[1] https://review.opendev.org/#/c/676204/","commit_id":"8547a8c08882f750eb150303c8417bf524115299"}]}