{"thread":{"id":"20857","subject":"unpack-trees traversing with index quite broken...","startedAt":"2009-09-05T06:40:13Z","lastAt":"2009-09-05T06:40:13Z","messageCount":1,"participants":["Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"122485","messageId":"7vr5ul99o2.fsf@alter.siamese.dyndns.org","threadId":"20857","inReplyTo":null,"subject":"unpack-trees traversing with index quite broken...","fromName":"Junio C Hamano","fromEmail":"junio@pobox.com","sentAt":"2009-09-05T06:40:13Z","receivedAt":"2009-09-05T06:40:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus,\n\nI found an issue I do not know how to resolve.\n\nSuppose you try to merge these three trees:\n\n - Tree #1 (ancestor)\n   t   tree, in which there is an entry f that is a blob\n   t/f blob\n\n - Tree #2 (ours)\n   t   blob\n   t-f blob\n\n - Tree #3 (theirs)\n   t-f blob\n\nThe index matches our tree.\n\nThe callchain that causes \"read-tree -m -u #1 #2 #3\" misbehave looks like this.\n\nunpack_trees()\n->traverse_trees()\n  entry[0] = \"t\" (tree taken from Tree #1)\n  entry[1] = \"t\" (blob taken from Tree #2)\n  entry[2] = nothing\n  ->unpack_callback()\n    ce = \"t\" (blob taken from the index)\n    ->unpack_nondirectories()\n      src[0] = \"t\" (blob from the index)\n      src[1] = conflict (tree taken from Tree #1)\n      src[2] = \"t\" (blob taken from Tree #2)\n      src[3] = NULL\n    ->call_unpack_fn()\n      This callback is perfectly fine.\n    /* Now handle any directories.. unpack-trees.c, ll.336- */\n    ->traverse_trees_recursive()\n      Now we stepped into tree \"t\".\n      ->traverse_trees()\n        entry[0] = \"f\" (blob from \"t/\" tree in Tree #1)\n        entry[1] = nothing (Tree #2 does not have \"t/\" subtree)\n        entry[2] = nothing (Tree #3 does not have \"t/\" subtree)\n        ->unpack_callback()\n          ce = \"t-f\" (blob taken from the index)\n          ->compare_entry(ce, entry[])\n          <- \"t-f\" comes anything in \"t/\" directory, return negative\n\n          Because we are processing \"t/something\" at this level, and\n          \"t-f\" that should come earlier than any \"t/something\", we\n          assume that there is no matching entries in the trees.\n          ->unpack_index_entry(ce = \"t-f\")\n            ->call_unpack_fn()\n              This callback is utterly wrong.  \"t-f\" from the index\n              has a matching entry in Tree #2 and Tree #3, but we\n              haven't seen them yet!\n\nAt first, I thought that we could fudge this particular example by\nnoticing that \"t-f\" is earlier only because \"t-f\" sorts before \"t/\", the\npath-prefix of the problematic level, and pretend the negative return from\ncompare_entry() as if it was positive (i.e. deferring the processing of\nthe index entry).  While this approach lets the problematic level\ncorrectly feed only \"t/f\" to call_unpack_fn() and come back, and the rest\nmay proceed cleanly for this particular case, I do not think it is the\nright solution.\n\nIf Tree #3 had another tree \"t/\" in it, the situation would look like this\ninstead:\n\n - Tree #1 (ancestor)\n   t   tree, in which there is an entry f that is a blob\n   t/f blob\n\n - Tree #2 (ours, matches the index)\n   t   blob\n   t-f blob\n\n - Tree #3 (theirs)\n   t-f blob\n   t   tree, in which there is an entry f that is a blob    \n\nSince traverse_trees() wants to walk the trees in parallel, never seeking\nback, I do not think it would feed t-f from Tree #2 and Tree #3 to the\nunpack_callback() sanely.  Worse yet, the logic to walk the index in\nparallel while this is happening (i.e. \"Are we supposed to look at the\nindex too?\" part) does not want to seek o->pos pointer back either, so I\nam stuck X-<...\n"}]}