// `findPathToLeaf()` returns an array of revs that goes from the specified
// leaf rev to the root of that leaf’s branch.
//
// eg. for this rev tree:
// 1-9692 ▶ 2-37aa ▶ 3-df22 ▶ 4-6e94 ▶ 5-df4a ▶ 6-6a3a ▶ 7-57e5
//          ┃                 ┗━━━━━━▶ 5-8d8c ▶ 6-65e0
//          ┗━━━━━━▶ 3-43f6 ▶ 4-a3b4
//
// For a `targetRev` of '7-57e5', `findPathToLeaf()` would return ['7-57e5', '6-6a3a', '5-df4a']
// The `revs` argument has the same structure as what `revs_tree` has on e.g.
// the IndexedDB representation of the rev tree datastructure. Please refer to
// tests/unit/test.purge.js for examples of what these look like.
//
// This function will throw an error if:
// - The requested revision does not exist
// - The requested revision is not a leaf
function findPathToLeaf(revs, targetRev) {
  let path = [];
  const toVisit = revs.slice();

  let node;
  while ((node = toVisit.pop())) {
    const { pos, ids: tree } = node;
    const rev = `${pos}-${tree[0]}`;
    const branches = tree[2];

    // just assuming we're already working on the path up towards our desired leaf.
    path.push(rev);

    // we've reached the leaf of our dreams, so return the computed path.
    if (rev === targetRev) {
      //…unleeeeess
      if (branches.length !== 0) {
        throw new Error('The requested revision is not a leaf');
      }
      return path.reverse();
    }

    // this is based on the assumption that after we have a leaf (`branches.length == 0`), we handle the next
    // branch. this is true for all branches other than the path leading to the winning rev (which is 7-57e5 in
    // the example above. i've added a reset condition for branching nodes (`branches.length > 1`) as well.
    if (branches.length === 0 || branches.length > 1) {
      path = [];
    }

    // as a next step, we push the branches of this node to `toVisit` for visiting it during the next iteration
    for (let i = 0, len = branches.length; i < len; i++) {
      toVisit.push({ pos: pos + 1, ids: branches[i] });
    }
  }
  if (path.length === 0) {
    throw new Error('The requested revision does not exist');
  }
  return path.reverse();
}

export default findPathToLeaf;
