{"thread":{"id":"39070","subject":"git fsck: unreachable vs. dangling","startedAt":"2015-04-14T07:16:59Z","lastAt":"2015-04-14T16:19:34Z","messageCount":9,"participants":["Sebastian Schuberth","Junio C Hamano","Michael J Gruber"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"259329","messageId":"CAHGBnuOYLpkeUop9vNH3+WSKqrM3NCSqvu-NZnPnk3gEkAr6eg@mail.gmail.com","threadId":"39070","inReplyTo":null,"subject":"git fsck: unreachable vs. dangling","fromName":"Sebastian Schuberth","fromEmail":"sschuberth@gmail.com","sentAt":"2015-04-14T07:16:59Z","receivedAt":"2015-04-14T07:16:59Z","isPatch":false,"sender":{"key":"sschuberth@gmail.com","avatar":"https://avatars.githubusercontent.com/u/349154?v=4"},"body":"Hi,\n\nreading through the fsck docs [1] I'm having a hard time understanding\nwhat the difference between \"unreachable\" and \"dangling\" objects are.\n\nBy example, suppose I have a commit A that is the tip of exactly one\nbranch (and no tag or other ref points to A). If I delete that branch,\nis A now dangling, or unreachable, or both?\n\n[1] http://git-scm.com/docs/git-fsck.html\n\n-- \nSebastian Schuberth\n"},{"id":"259330","messageId":"CAPc5daXRpfSrvcae0W+YU-51prCoFGxz_hkhtp7FZ-K9_eeeBQ@mail.gmail.com","threadId":"39070","inReplyTo":"CAHGBnuOYLpkeUop9vNH3+WSKqrM3NCSqvu-NZnPnk3gEkAr6eg@mail.gmail.com","subject":"Re: git fsck: unreachable vs. dangling","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-04-14T08:05:10Z","receivedAt":"2015-04-14T08:05:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"On Tue, Apr 14, 2015 at 12:16 AM, Sebastian Schuberth\n wrote:\n> Hi,\n>\n> reading through the fsck docs [1] I'm having a hard time understanding\n> what the difference between \"unreachable\" and \"dangling\" objects are.\n>\n> By example, suppose I have a commit A that is the tip of exactly one\n> branch (and no tag or other ref points to A). If I delete that branch,\n> is A now dangling, or unreachable, or both?\n\nSuppose that branch consists of two commits, A and A^.\nWhen you lose that branch (git branch -D that-branch),\nboth A and A^ become unreachable. So are trees and\nblobs that appear only in A and A^ and nowhere else;\nthey are also unreachable.\n\nA dangling object is an unreachable object that cannot be\nmade reachable by any way other than pointing at it\ndirectly with a ref. A^ is not dangling, because you can\nmake it reachable by pointing A (the tip of the original\nbranch you just lost) with a ref. A on the other hand is\ndangling (if you had a tag object that points at A that\nyou lost, then A is merely unreachable but not dangling,\nbecause you can point at that tag with a ref and make A\nreachable).\n"},{"id":"259332","messageId":"552CD4C8.2020700@drmicha.warpmail.net","threadId":"39070","inReplyTo":"CAPc5daXRpfSrvcae0W+YU-51prCoFGxz_hkhtp7FZ-K9_eeeBQ@mail.gmail.com","subject":"Re: git fsck: unreachable vs. dangling","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2015-04-14T08:50:16Z","receivedAt":"2015-04-14T08:50:16Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Junio C Hamano venit, vidit, dixit 14.04.2015 10:05:\n> On Tue, Apr 14, 2015 at 12:16 AM, Sebastian Schuberth\n> wrote:\n>> Hi,\n>>\n>> reading through the fsck docs [1] I'm having a hard time understanding\n>> what the difference between \"unreachable\" and \"dangling\" objects are.\n>>\n>> By example, suppose I have a commit A that is the tip of exactly one\n>> branch (and no tag or other ref points to A). If I delete that branch,\n>> is A now dangling, or unreachable, or both?\n> \n> Suppose that branch consists of two commits, A and A^.\n> When you lose that branch (git branch -D that-branch),\n> both A and A^ become unreachable. So are trees and\n> blobs that appear only in A and A^ and nowhere else;\n> they are also unreachable.\n> \n> A dangling object is an unreachable object that cannot be\n> made reachable by any way other than pointing at it\n> directly with a ref. A^ is not dangling, because you can\n> make it reachable by pointing A (the tip of the original\n> branch you just lost) with a ref. A on the other hand is\n> dangling (if you had a tag object that points at A that\n> you lost, then A is merely unreachable but not dangling,\n> because you can point at that tag with a ref and make A\n> reachable).\n> \n\nThis terminology is established, but misleading if you try to\nunderstanding things from the word and the technical tree structure:\n\n\"to dangle\" means \"to hang loosely\".\n\nSo, in the description above, \"A^ dangles from A loosely\" because it\nhangs from A (you can reach it from A) but loosely, because it would\n\"drop\" if A gets dropped and A is \"likely\" to be dropped (because it is\nunreachable by refs). But A^ is not dangling in our terminology.\n\nIf you *reverse the arrows*, i.e. consider A^ pointing to A, it becomes\nmore apparent that A is dangling: it is an unreferenced leaf node.\n\nBut really, we're switching directions of the arrows again and again\nwhen, on the one hand, we talk about refs pointing to commits, commits\npointing to parent commits (which they are, of course) but then, on the\nother hand, use terms like \"root\" and \"dangling\" which make sense only\nwhen you think of the oppositely oriented tree.\n\nMaybe we should introduce the terms DAG and reverse DAG (GAD?) to make\nthis clearer. Our DAG is technically oriented from commits to their\nparents all the way \"up\" to the root.\n\nVisually, we often orient it from the root towards child commits.\n\nWhen we do a revision walk, do we walk forward or backwards?\n\nI'd say users think in the ordering in which they create commits (from\nroot to children), let's call that DAG. It explains \"root\" and \"dangle\"\nand such, and a revision walk is a walk backwards in that orientation.\n\nTechnically, our acyclic graph is oriented the other way, a revision\nwalk walks forward in that orientation - it couldn't walk any other way\nwithout extensive searching. This orientation (GAD?) explains \"points\nto\", be it \"ref to rev\" or \"commit to parent\".\n\nMichael\n\nP.S.: The more mathematically inclined will notice that we can have more\nthan 2 orientations if our graph is not connected... But I'd say we have\none \"technical\" orientation (commit->parent) and the opposite and can\nforget about others.\n"},{"id":"259333","messageId":"CAHGBnuOuMnAsP12dukPSP31ABRoUc=s7iZFnca9-K2hOcog9cQ@mail.gmail.com","threadId":"39070","inReplyTo":"CAPc5daXRpfSrvcae0W+YU-51prCoFGxz_hkhtp7FZ-K9_eeeBQ@mail.gmail.com","subject":"Re: git fsck: unreachable vs. dangling","fromName":"Sebastian Schuberth","fromEmail":"sschuberth@gmail.com","sentAt":"2015-04-14T08:52:31Z","receivedAt":"2015-04-14T08:52:31Z","isPatch":false,"sender":{"key":"sschuberth@gmail.com","avatar":"https://avatars.githubusercontent.com/u/349154?v=4"},"body":"On Tue, Apr 14, 2015 at 10:05 AM, Junio C Hamano wrote:\n\n> A dangling object is an unreachable object that cannot be\n> made reachable by any way other than pointing at it\n> directly with a ref.\n\nThanks a lot for the prompt explanation!\n\n-- \nSebastian Schuberth\n"},{"id":"259334","messageId":"CAHGBnuPepR11r9qpxb2G7pGhq0iiaqCCLnbt5NB_xohHi=cVxA@mail.gmail.com","threadId":"39070","inReplyTo":"552CD4C8.2020700@drmicha.warpmail.net","subject":"Re: git fsck: unreachable vs. dangling","fromName":"Sebastian Schuberth","fromEmail":"sschuberth@gmail.com","sentAt":"2015-04-14T08:58:39Z","receivedAt":"2015-04-14T08:58:39Z","isPatch":false,"sender":{"key":"sschuberth@gmail.com","avatar":"https://avatars.githubusercontent.com/u/349154?v=4"},"body":"On Tue, Apr 14, 2015 at 10:50 AM, Michael J Gruber\n wrote:\n\n> \"to dangle\" means \"to hang loosely\".\n>\n> So, in the description above, \"A^ dangles from A loosely\" because it\n> hangs from A (you can reach it from A) but loosely, because it would\n> \"drop\" if A gets dropped and A is \"likely\" to be dropped (because it is\n> unreachable by refs). But A^ is not dangling in our terminology.\n>\n> If you *reverse the arrows*, i.e. consider A^ pointing to A, it becomes\n> more apparent that A is dangling: it is an unreferenced leaf node.\n\nThat's exactly what confused me. In the very literal sense, something\ncan only \"hang loosely\", i.e. dangle, if it's only tied at *one* end,\nand that's the case for A (which is only connected to A^) but not for\nA^ (which is connected to its parent, and A). Especially when talking\nabout A as a \"leaf\" node, like in the leaf of a natural tree, I would\nthink that A is dangling.\n\n-- \nSebastian Schuberth\n"},{"id":"259335","messageId":"xmqq1tjn3vzs.fsf@gitster.dls.corp.google.com","threadId":"39070","inReplyTo":"CAHGBnuPepR11r9qpxb2G7pGhq0iiaqCCLnbt5NB_xohHi=cVxA@mail.gmail.com","subject":"Re: git fsck: unreachable vs. dangling","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-04-14T09:22:15Z","receivedAt":"2015-04-14T09:22:15Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sebastian Schuberth writes:\n\n> On Tue, Apr 14, 2015 at 10:50 AM, Michael J Gruber\n> wrote:\n>\n>> \"to dangle\" means \"to hang loosely\".\n>>\n>> So, in the description above, \"A^ dangles from A loosely\" because it\n>> hangs from A (you can reach it from A) but loosely, because it would\n>> \"drop\" if A gets dropped and A is \"likely\" to be dropped (because it is\n>> unreachable by refs). But A^ is not dangling in our terminology.\n>>\n>> If you *reverse the arrows*, i.e. consider A^ pointing to A, it becomes\n>> more apparent that A is dangling: it is an unreferenced leaf node.\n>\n> That's exactly what confused me. In the very literal sense, something\n> can only \"hang loosely\", i.e. dangle, if it's only tied at *one* end,\n> and that's the case for A (which is only connected to A^) but not for\n> A^ (which is connected to its parent, and A). Especially when talking\n> about A as a \"leaf\" node, like in the leaf of a natural tree, I would\n> think that A is dangling.\n\nI am not sure if I follow, but probably it is just me who is not\nstrong at math, or whose eyesight is not keen enough to notice the\narrow heads on links between the commits.\n\nI just visualize commits to be ping-pong balls with strings between\nthem, and then grab the root of the graph and lift the whole thing\nup, while tips of the branches and tags are anchored. Commit A will\nbe dangling in the wind if you shake the whole thing.\n\nBut that visualization breaks down once you start thinking about\nwhat will happen to A^{tree} and its blobs; they are attached to A\nwith thin strings and they will have to float above A (i.e. sit\nsomewhere closer to the root of the tree) just like A^ will go\ncloser to the root, to make A appear the \"dangling\" one, as the\ndirection of the arrow is from A to A^{tree} just like we have an\narrow from A to A^; just like A^ is not dangling because of A,\nA^{tree} is not dangling.\n"},{"id":"259336","messageId":"CAHGBnuNA7fVKJRA-oMbnL5J+zoe7F6sy0rU_0PvAX52x0ofXdQ@mail.gmail.com","threadId":"39070","inReplyTo":"xmqq1tjn3vzs.fsf@gitster.dls.corp.google.com","subject":"Re: git fsck: unreachable vs. dangling","fromName":"Sebastian Schuberth","fromEmail":"sschuberth@gmail.com","sentAt":"2015-04-14T09:28:41Z","receivedAt":"2015-04-14T09:28:41Z","isPatch":false,"sender":{"key":"sschuberth@gmail.com","avatar":"https://avatars.githubusercontent.com/u/349154?v=4"},"body":"On Tue, Apr 14, 2015 at 11:22 AM, Junio C Hamano wrote:\n\n> I just visualize commits to be ping-pong balls with strings between\n> them, and then grab the root of the graph and lift the whole thing\n> up, while tips of the branches and tags are anchored. Commit A will\n> be dangling in the wind if you shake the whole thing.\n\nI used to have exactly the same visualization in mind, but got\nconfused in between, unsure whether my understanding was correct. As\nit turns out it is, and when sticking to that visualization everything\nseems to be consistent in the fsck docs. They could still benefit some\nmore clarification I guess. I'll see if I can come up with something.\n\nThanks again.\n\n-- \nSebastian Schuberth\n"},{"id":"259350","messageId":"CAHGBnuODrwq-MSp53zacgfcevX7tdtfPEC+fyTrWrnTKaFKO1g@mail.gmail.com","threadId":"39070","inReplyTo":"CAHGBnuOuMnAsP12dukPSP31ABRoUc=s7iZFnca9-K2hOcog9cQ@mail.gmail.com","subject":"Re: git fsck: unreachable vs. dangling","fromName":"Sebastian Schuberth","fromEmail":"sschuberth@gmail.com","sentAt":"2015-04-14T14:20:07Z","receivedAt":"2015-04-14T14:20:07Z","isPatch":false,"sender":{"key":"sschuberth@gmail.com","avatar":"https://avatars.githubusercontent.com/u/349154?v=4"},"body":"On Tue, Apr 14, 2015 at 10:52 AM, Sebastian Schuberth\n wrote:\n\n>> A dangling object is an unreachable object that cannot be\n>> made reachable by any way other than pointing at it\n>> directly with a ref.\n>\n> Thanks a lot for the prompt explanation!\n\nNote to myself: I just realized that both \"dangling\" and \"unreachable\"\nare also nicely defined in the Git glossary [1].\n\n[1] http://git-scm.com/docs/gitglossary/\n\n-- \nSebastian Schuberth\n"},{"id":"259354","messageId":"552D3E16.7090504@drmicha.warpmail.net","threadId":"39070","inReplyTo":"xmqq1tjn3vzs.fsf@gitster.dls.corp.google.com","subject":"Re: git fsck: unreachable vs. dangling","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2015-04-14T16:19:34Z","receivedAt":"2015-04-14T16:19:34Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Junio C Hamano venit, vidit, dixit 14.04.2015 11:22:\n> Sebastian Schuberth writes:\n> \n>> On Tue, Apr 14, 2015 at 10:50 AM, Michael J Gruber\n>> wrote:\n>>\n>>> \"to dangle\" means \"to hang loosely\".\n>>>\n>>> So, in the description above, \"A^ dangles from A loosely\" because it\n>>> hangs from A (you can reach it from A) but loosely, because it would\n>>> \"drop\" if A gets dropped and A is \"likely\" to be dropped (because it is\n>>> unreachable by refs). But A^ is not dangling in our terminology.\n>>>\n>>> If you *reverse the arrows*, i.e. consider A^ pointing to A, it becomes\n>>> more apparent that A is dangling: it is an unreferenced leaf node.\n>>\n>> That's exactly what confused me. In the very literal sense, something\n>> can only \"hang loosely\", i.e. dangle, if it's only tied at *one* end,\n>> and that's the case for A (which is only connected to A^) but not for\n>> A^ (which is connected to its parent, and A). Especially when talking\n>> about A as a \"leaf\" node, like in the leaf of a natural tree, I would\n>> think that A is dangling.\n> \n> I am not sure if I follow, but probably it is just me who is not\n> strong at math, or whose eyesight is not keen enough to notice the\n> arrow heads on links between the commits.\n\n\"git log --graph\" does not show arrow heads, obviously. Many\nillustrations about Git do.\n\nThe relation between commits is clearly directed: A being a parent\ncommit of B is different from B being a parent commit of A (and both\ncannot be true simultaneously due to the \"A\" in \"DAG\")\n\n > I just visualize commits to be ping-pong balls with strings between\n> them, and then grab the root of the graph and lift the whole thing\n> up, while tips of the branches and tags are anchored. Commit A will\n> be dangling in the wind if you shake the whole thing.\n\nIf you don't have a concept of direction it is difficult to distinguish\nroots from tips...\n\nOur commit relationship is certainly a directed one. You can define it\nusing either \"is parent of\" or \"is child of\". They are opposite, and\nlead to opposite notions of \"root\" (a node without predecessors) and\n\"tip\" (a node without successors).\n\n> But that visualization breaks down once you start thinking about\n> what will happen to A^{tree} and its blobs; they are attached to A\n> with thin strings and they will have to float above A (i.e. sit\n> somewhere closer to the root of the tree) just like A^ will go\n> closer to the root, to make A appear the \"dangling\" one, as the\n> direction of the arrow is from A to A^{tree} just like we have an\n> arrow from A to A^; just like A^ is not dangling because of A,\n> A^{tree} is not dangling.\n> \n"}]}