Re: [basex-talk] Hitting the Tail Recursion wall
If you need to join the resulting strings just use well ...
string-join ...
declare function local:topath($path){
let $pathseg := tokenize($path, "/")
let $pathsequence :=
fold-left($pathseg, (), function($out, $segment){
if($segment = "." or $segment = "") then $out
else if($segment = "..") then $out[position() lt count($out)]
else ($out, $segment)
})
return string-join($pathsequence, "/")
};
local:topath("/a/b/c/../../../g")
On 01/04/19 22:02, Andreas Mixich wrote:
Marco Lettere wrote onm 01.04.2019 at 18:01:
declare function local:topath($path){ let $pathseg := tokenize($path,
"/") return fold-left($pathseg, (), function($out, $segment){
if($segment = "." or $segment = "") then $out else if($segment =
"..") then $out[position() lt count($out)] else ($out,
$segment) })}; local:topath("/a/b/c/../../../g")
Beautiful and very close, except for a minor caveat: the "/" are needed,
to reconstruct the absolute path-part from the relative.
I played around and tried to place some "/" to your function, but all
variants placed some "/" wrong or twice.
Last but not least: You asked for the use case, which is described on
https://tools.ietf.org/html/rfc3986#section-5.2.4 (note also the
sequences shown after the description of the steps)
5.2.4 .
Remove Dot Segments
The pseudocode also refers to a "remove_dot_segments" routine for
interpreting and removing the special "." and ".." complete path
segments from a referenced path. This is done after the path is
extracted from a reference, whether or not the path was relative, in
order to remove any invalid or extraneous dot-segments prior to
forming the target URI. Although there are many ways to accomplish
this removal process, we describe a simple method using two string
buffers.
1. The input buffer is initialized with the now-appended path
components and the output buffer is initialized to the empty
string.
2. While the input buffer is not empty, loop as follows:
A. If the input buffer begins with a prefix of "../" or "./",
then remove that prefix from the input buffer; otherwise,
B. if the input buffer begins with a prefix of "/./" or "/.",
where "." is a complete path segment, then replace that
prefix with "/" in the input buffer; otherwise,
C. if the input buffer begins with a prefix of "/../" or "/..",
where ".." is a complete path segment, then replace that
prefix with "/" in the input buffer and remove the last
segment and its preceding "/" (if any) from the output
buffer; otherwise,
D. if the input buffer consists only of "." or "..", then remove
that from the input buffer; otherwise,
E. move the first path segment in the input buffer to the end of
the output buffer, including the initial "/" character (if
any) and any subsequent characters up to, but not including,
the next "/" character or the end of the input buffer.
3. Finally, the output buffer is returned as the result of
remove_dot_segments.
Note that dot-segments are intended for use in URI references to
express an identifier relative to the hierarchy of names in the base
URI. The remove_dot_segments algorithm respects that hierarchy by
removing extra dot-segments rather than treat them as an error or
leaving them to be misinterpreted by dereference implementations.
The following illustrates how the above steps are applied for two
examples of merged paths, showing the state of the two buffers after
each step.
STEP OUTPUT BUFFER INPUT BUFFER
1 : /a/b/c/./../../g
2E: /a/b/c/./../../g
2E: /a/b /c/./../../g
2E: /a/b/c/./../../g
2B: /a/b/c/../../g
2C: /a/b /../g
2C: /a/g
2E: /a/g
STEP OUTPUT BUFFER INPUT BUFFER
1 :
mid/content=5/../6
2E: mid /content=5/../6
2E: mid/content=5 /../6
2C: mid /6
2E: mid/6
Re: [basex-talk] Hitting the Tail Recursion wall
Marco Lettere wrote onm 01.04.2019 at 18:01:
> declare function local:topath($path){ let $pathseg := tokenize($path,
> "/") return fold-left($pathseg, (), function($out, $segment){
> if($segment = "." or $segment = "") then $out else if($segment =
> "..") then $out[position() lt count($out)] else ($out,
> $segment) })}; local:topath("/a/b/c/../../../g")
Beautiful and very close, except for a minor caveat: the "/" are needed,
to reconstruct the absolute path-part from the relative.
I played around and tried to place some "/" to your function, but all
variants placed some "/" wrong or twice.
Last but not least: You asked for the use case, which is described on
https://tools.ietf.org/html/rfc3986#section-5.2.4 (note also the
sequences shown after the description of the steps)
5.2.4 .
Remove Dot Segments
The pseudocode also refers to a "remove_dot_segments" routine for
interpreting and removing the special "." and ".." complete path
segments from a referenced path. This is done after the path is
extracted from a reference, whether or not the path was relative, in
order to remove any invalid or extraneous dot-segments prior to
forming the target URI. Although there are many ways to accomplish
this removal process, we describe a simple method using two string
buffers.
1. The input buffer is initialized with the now-appended path
components and the output buffer is initialized to the empty
string.
2. While the input buffer is not empty, loop as follows:
A. If the input buffer begins with a prefix of "../" or "./",
then remove that prefix from the input buffer; otherwise,
B. if the input buffer begins with a prefix of "/./" or "/.",
where "." is a complete path segment, then replace that
prefix with "/" in the input buffer; otherwise,
C. if the input buffer begins with a prefix of "/../" or "/..",
where ".." is a complete path segment, then replace that
prefix with "/" in the input buffer and remove the last
segment and its preceding "/" (if any) from the output
buffer; otherwise,
D. if the input buffer consists only of "." or "..", then remove
that from the input buffer; otherwise,
E. move the first path segment in the input buffer to the end of
the output buffer, including the initial "/" character (if
any) and any subsequent characters up to, but not including,
the next "/" character or the end of the input buffer.
3. Finally, the output buffer is returned as the result of
remove_dot_segments.
Note that dot-segments are intended for use in URI references to
express an identifier relative to the hierarchy of names in the base
URI. The remove_dot_segments algorithm respects that hierarchy by
removing extra dot-segments rather than treat them as an error or
leaving them to be misinterpreted by dereference implementations.
The following illustrates how the above steps are applied for two
examples of merged paths, showing the state of the two buffers after
each step.
STEP OUTPUT BUFFER INPUT BUFFER
1 : /a/b/c/./../../g
2E: /a/b/c/./../../g
2E: /a/b /c/./../../g
2E: /a/b/c/./../../g
2B: /a/b/c/../../g
2C: /a/b /../g
2C: /a/g
2E: /a/g
STEP OUTPUT BUFFER INPUT BUFFER
1 :
mid/content=5/../6
2E: mid /content=5/../6
2E: mid/content=5 /../6
2C: mid /6
2E: mid/6
--
Goody Bye, Minden jót, Mit freundlichen Grüßen,
Andreas Mixich
Re: [basex-talk] Hitting the Tail Recursion wall
Hi Andreas,
I don't know whether I correctly understood you use-case but what about
going with hof functions [1]?
Maybe your code could turn to something as simple as
declare function local:topath($path){
let $pathseg := tokenize($path, "/")
return
fold-left($pathseg, (), function($out, $segment){
if($segment = "." or $segment = "") then $out
else if($segment = "..") then $out[position() lt count($out)]
else ($out, $segment)
})
};
local:topath("/a/b/c/../../../g")
Regards,
Marco.
[1] http://docs.basex.org/wiki/Higher-Order_Functions
On 01/04/19 15:49, Andreas Mixich wrote:
I think, I am finding it...
I replaced the first expression with
`prof:dump(concat("in: ", $path, " out: ",
string-join(array:flatten($out,`
and this gives me more info. So I may be able to solve this alone.
Re: [basex-talk] Hitting the Tail Recursion wall
I think, I am finding it...
I replaced the first expression with
`prof:dump(concat("in: ", $path, " out: ",
string-join(array:flatten($out,`
and this gives me more info. So I may be able to solve this alone.
--
Goody Bye, Minden jót, Mit freundlichen Grüßen,
Andreas Mixich
[basex-talk] Hitting the Tail Recursion wall
Hi,
I am trying to implement the algorithm outlined at
https://tools.ietf.org/html/rfc3986#section-5.2.4
(Two other implementations are at [1] and [2])
The following function is my work in progress. It seems, all goes fine,
till the last `else`,
which is commented with `(: E :)`. I hit the tail recursion barrier and
I do not see why.
The function may not (yet) make sense, since I am still experimenting.
`local:remove-dot-segments("/a/b/c/./../../g",[])`
```
(:~
Remove dot segments from a URI path component according to RFC 3986
Section 5.2.4
@param $path the path component of an URL
@param $out an empty (!) array
@return the path component with the relative part (dot segments)
removed and
resolved to the absolute path.
@see https://tools.ietf.org/html/rfc3986#section-5.2.4
:)
declare function local:remove-dot-segments(
$path as xs:string,
$out as array(*))
as item()*
{
concat("in: ", $path, " out: ", string-join(array:flatten($out))),
if (not(contains($path, ".")))
then $path
else
if (string-length($path) > 0)
then (: A :)
if (substring($path,1,3) = "../")
then local:remove-dot-segments(substring($path, 4), $out)
else
if (substring($path, 1, 2) = "./")
then local:remove-dot-segments(substring($path, 3), $out)
else (: B :)
if (substring($path,1,3) = "/./")
then local:remove-dot-segments(concat("/", substring($path,
4)), $out)
else
if (substring($path, 1, 2) = "/.")
then local:remove-dot-segments(concat("/", substring($path,
3)), $out)
else (: C :)
if (substring($path, 1, 4) = "/../")
then
let $ret := array:remove($out, array:size($out))
return local:remove-dot-segments(concat("/",
substring($path, 5)), $ret)
else
if (substring($path, 1, 3) = "/..")
then
let $ret := array:remove($out, array:size($out))
return local:remove-dot-segments(concat("/",
substring($path, 4)), $ret)
else (: D :)
if ($path = ".." or $path = ".")
then local:remove-dot-segments(concat(substring((),
4), ""), $out)
else (: E :)
let $ret :=
if (starts-with($path, "/"))
then array:append($out, concat("/",
substring-before(substring($path,2), "/")))
else array:append($out,
substring-before(substring($path,1), "/"))
return local:remove-dot-segments($path, $ret)
else $path
};
```
Sorry for throwing such a big function at you, but I do not find the
place, where the stack overflow gets triggered. It does not happen, if I
return an empty sequence at `else (: E :)`. If I replace that part
(after `else (: E :)`) with `local:remove-dot-segments($path, $out)` I
get the stack overflow as well, which is, what confuses me the most.
[1]https://github.com/ariutta/remove-dot-segments/blob/master/index.js
[2] https://gist.github.com/rdlowrey/5f56cc540099de9d5006
--
Goody Bye, Minden jót, Mit freundlichen Grüßen,
Andreas Mixich
