NON-trivial regular expression problem (could not find on google)

NON-trivial regular expression problem (could not find on google)

[Instant Democracy]

Regular expression facilities are slightly varied in
sed
awk
lisp
emacs-lisp
Therefore these newsgroups can all contribute to the discussion.

A frequent problem involves simplifying a pathname. The string format we
can expect to encounter is covered by the following three examples:

"dir.name/../dir/../file"
"dir/../d2/../file.ext"
"d1/d2/../../file.ext"

The "" are part of the string, and not just string delimiters. These
strings are inside regular text on the line. The paths are never
absolute so that you will not encounter "/d1/file.ext".

The task is to eliminate patterns such as 
    DIRNAME/../
from the path because they are redundant.

For lines which do not have ../.. in them, this is
trivial, for example by regexp in sed, emacs etc.

The real problem is constructing a regular expression for
the DIRNAME before the /..

This DIRNAME can be described as a string that contains neither
/ not double-dot but anything else. Perhaps I am overlooking
something else about DIRNAME.

The regular expression for the first two cases is demonstrated by this
sed script although the lisp variants are identical.

sed 's,\(^.*\)\(/\|"\)\([^/][^/]*/\.\./\)\(.*"\),\1\2\4,'

The regex I use for DIRNAME is [^/]+ written above using * because
sed is without plus.

I will follow all the cross-posted newsgroups. If you prefer, because
some people are allergic to any cross-posting, you can post your reply
in just one of the groups pertaining to your application, ie lisp/elisp/sed/awk.

democrat

sigfile - you are welcome to use it or modify without changing its thrust.
>
> US DEMONCRACY IS FLAWED - THE SOLUTION FOR TODAY IS HERE
> 
> THE ECONOMY CAN BE KICK-STARTED BY LAYING OFF THE
> POLITICIANS AND REDUCING THEIR SALARIES BY 60%
> 
> What do we have today? A faulty plutocracy that was
> designed in an age that had no electricity, no
> electronics, no internet and no mass media. It was in a
> barbaric age of slavery and bigotry.  The people were so
> illiterate that they even failed to understand what they
> wrote in the constitution - otherwise there would be no
> slavery side by side with "... all men are created equal
> ...."
> 
> The reason for world-wide wars is corruption, and
> plutocracy. The power of criminal rulers is not being
> checked properly by that of the people.  There is too
> much effort to bring down a corrupt leader. For example,
> Clinton managed to lollypop a number of women before he
> was caught.  The child molesters in the church were not
> caught for a greater part of their life-time. But make
> no mistake, those who are caught are the unskilled
> ones. The highly skilled criminals like Bush and his ilk
> are not going to be caught in their life-time, so
> cleverly have they concealed their ill deeds.
> 
> The plutocrats are pathetic. The senators, congressmen
> and presidents failed to eliminate slavery and there is
> no justification to pay them high salaries to the tune
> of $500,000 per year and then the retirements, perks,
> security.
> 
> It happened on the battle field because plutocrats would
> not allow people's wishes to be translated into action.
> 
> Today, we are way behind times.
> 
> There is no need for a president, electoral college,
> congressmen and senators.
> 
> What is needed are state messengers and clerks. The
> public would vote weekly by telephone from their home to
> an electronic computer. Enter their password and vote on
> an issue. All can be made secure by multiple redundancy
> and open source code and interpreter that can be run on
> any PC. All voting is to be open and everyone can check
> cheating. If our medical records are going to be open,
> it is but little that all voting on issues is open and
> everyone can check their own voting with confirmation.
> 
> Just as we are secure with our bank accounts and check
> our balance by phone, we can vote on issues.
> 
> All issues can be discussed by internet, phone, and so
> on to educate the public.
> 
> But the senators, congressmen and presidents are
> corrupt, unfaithful even to their wives, take too much
> money for salary for a work executed pathetically. Some
> president are doing affairs, others are moral quacks
> with basic errors in english grammar and also
> intellectual and personality wise, midgets.
> 
> This is an age of instant telephone referendum and
> instant democracy.
> 
> The power to wage war should neither belong to the
> president, nor to the congress, but to the people via
> instant referendum.
> 
> The electoral college is also a dinosaur. Americans are
> educated enough to decide who to choose as a referendum
> executioner, that is, the president.
> 
> This is not a third world country, with slavery, no
> electricity, no media, no railway, no steam engine, no
> satellites, no telephone that we must not have instant
> democracy.
> 
> What we have today is not democracy, but demoncracy of a
> few.
>

Re: NON-trivial regular expression problem (could not find on google)

[Harry Putnam]

democrat@india.com (Instant Democracy) writes:

Let me say first, that I'm not sure I understand the problem but
after several readings it appears to be simply that you want to
reduce the file names to the last componenet only.

> A frequent problem involves simplifying a pathname. The string format we
> can expect to encounter is covered by the following three examples:

Overlooking the `"' part for a moment, that problem is often handled
with shell operators % # or %% ## rather than regex.

> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"

In any of the bourn based shells.
  var='dir.name/../dir/../file'
  echo ${var##*/}
    file

> The "" are part of the string, and not just string delimiters. These
> strings are inside regular text on the line. The paths are never
> absolute so that you will not encounter "/d1/file.ext".

In the above scheme they can be handled like:
  var='"dir.name/../dir/../file"'
  echo ${var##*/}|sed 's/\"//'
    file

> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.
>
> For lines which do not have ../.. in them, this is
> trivial, for example by regexp in sed, emacs etc.

Not sure I see why you would need to eleminate anything if 
../.. is not present.

> The real problem is constructing a regular expression for
> the DIRNAME before the /..
>
> This DIRNAME can be described as a string that contains neither
> / not double-dot but anything else. Perhaps I am overlooking
> something else about DIRNAME.

Do the shell operators mentioned solve it?  Or have I missed the boat
entirely?

Re: NON-trivial regular expression problem (could not find on google)

[Kai Großjohann]

democrat@india.com (Instant Democracy) writes:

> A frequent problem involves simplifying a pathname. The string format we
> can expect to encounter is covered by the following three examples:
>
> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"
>
> The "" are part of the string, and not just string delimiters. These
> strings are inside regular text on the line. The paths are never
> absolute so that you will not encounter "/d1/file.ext".
>
> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.

Let s be a string such as the above, but without quotes.  Then

    (expand-file-name s "/")

will return a suitable string, except that it starts with slash.

So in Emacs Lisp, you can do it without regular expressions, but in
three steps:

    (1) Remove quotes
    (2) Above Lisp expression
    (3) Remove leading slash

In Emacs, regular expressions are often not the answer.
-- 
Ambibibentists unite!

Re: NON-trivial regular expression problem (could not find on google)

[AW]

Instant Democracy wrote:
> Regular expression facilities are slightly varied in
> sed
> awk
> lisp
> emacs-lisp
> Therefore these newsgroups can all contribute to the discussion.
> 
> A frequent problem involves simplifying a pathname. The string format we
> can expect to encounter is covered by the following three examples:
> 
> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"
> 
> The "" are part of the string, and not just string delimiters. These
> strings are inside regular text on the line. The paths are never
> absolute so that you will not encounter "/d1/file.ext".
> 
> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.
> 
> For lines which do not have ../.. in them, this is
> trivial, for example by regexp in sed, emacs etc.
> 
> The real problem is constructing a regular expression for
> the DIRNAME before the /..
> 
> This DIRNAME can be described as a string that contains neither
> / not double-dot but anything else. Perhaps I am overlooking
> something else about DIRNAME.
> 
> The regular expression for the first two cases is demonstrated by this
> sed script although the lisp variants are identical.
> 
> sed 's,\(^.*\)\(/\|"\)\([^/][^/]*/\.\./\)\(.*"\),\1\2\4,'
> 
> The regex I use for DIRNAME is [^/]+ written above using * because
> sed is without plus.
> 
> I will follow all the cross-posted newsgroups. If you prefer, because
> some people are allergic to any cross-posting, you can post your reply
> in just one of the groups pertaining to your application, ie lisp/elisp/sed/awk.
> 
> democrat
> 

Using the shell is easier, but here goes.

BEGIN { FS="/"} { for( i=2;i<=NF;i++) { if( $i == "." ) $i =""; if($i == 
"..")  $(i-1) == ""; print; }

You only owe two bucks coz I burned your signature for heat...

Re: NON-trivial regular expression problem (could not find on google)

[Edi Weitz]

democrat@india.com (Instant Democracy) writes:

> Regular expression facilities are slightly varied in
> sed
> awk
> lisp
> emacs-lisp
> Therefore these newsgroups can all contribute to the discussion.
> 
> A frequent problem involves simplifying a pathname. The string format we
> can expect to encounter is covered by the following three examples:
> 
> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"
> 
> The "" are part of the string, and not just string delimiters. These
> strings are inside regular text on the line. The paths are never
> absolute so that you will not encounter "/d1/file.ext".
> 
> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.

In Lisp on a Unix system you would use the function TRUENAME provided
that the file in question exists, see

  <http://www.lispworks.com/reference/HyperSpec/Body/f_tn.htm>.

If I understand your problem description correctly this can't be
solved with regular expressions. Or, to be more exact, if the nesting
of "../" parts can be arbitrarily deep you won't be able to solve your
problem with a _single_ application of _one_ regular expression.

However, it should be easy to do this with _repeated_ applications of
a regular expression unless I missed something:

  perl -le 'while (<>) { 1 while s#[^/]+/\.\./##; print }'

Edi.

Re: NON-trivial regular expression problem (could not find on google)

[Larry Clapp]

In article <7606630f.0301181219.60384da2@posting.google.com>, Instant Democracy wrote:
> A frequent problem involves simplifying a pathname. The string
> format we can expect to encounter is covered by the following
> three examples:
> 
> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"
> 
> The "" are part of the string, and not just string delimiters.
> These strings are inside regular text on the line. The paths
> are never absolute so that you will not encounter
> "/d1/file.ext".
> 
> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.
> 
> For lines which do not have ../.. in them, this is trivial, for
> example by regexp in sed, emacs etc.
> 
> The real problem is constructing a regular expression for the
> DIRNAME before the /..
> 
> This DIRNAME can be described as a string that contains neither
> / not double-dot but anything else. Perhaps I am overlooking
> something else about DIRNAME.

Yes.  "../.." doesn't matter.  Find any pathname component
followed by ".." and remove both.  Continue until no more ".."'s
exist in the string.  In Perl:

    $_ = "d1/d2/../../file.ext";
    do {} while (s#[^/]+/\.\./##g);
    print $_;

In Common Lisp:

    (defun split (s delim)
      (let ((start-at 0))
	(nconc 
	  (loop for c across s 
		and i upto (length s)
		nconc (when (eql c delim)
			(prog1 
			  (list (subseq s start-at i))
			  (setf start-at (1+ i)))))
	  (list (subseq s start-at)))))

    (defun join (list delim)
      (let ((res (car list))
	    (delim (make-string 1 :initial-element delim)))
	(dolist (el (cdr list))
	  (setf res (concatenate 'string res delim el)))
	res))

    (defun normalize-path (path)
      (let ((names (split path #\/))
	    (stack nil))
	(dolist (name names)
	  (cond ((string= name "..") (pop stack))
		(t (push name stack))))
	(join (reverse stack) #\/)))

Testing:

    (let ((paths '("dir.name/../dir/../file"
		   "dir/../d2/../file.ext"
		   "d1/d2/../../file.ext"
		   "1234/../2345/../3546/3456/3456/../../asdf/asdf/file")))
      (dolist (path paths)
	(print (normalize-path path))))
    -> "file" 
    -> "file.ext" 
    -> "file.ext" 
    -> "3546/asdf/asdf/file" 
    => NIL

> [...]
> sigfile - you are welcome to use it or modify without changing
> its thrust.

Please drop this 3k sigfile.  Thank you.

-- Larry



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----

Re: NON-trivial regular expression problem (could not find on google)

[Dr. Yuan Liu]

Instant Democracy wrote:
> A frequent problem involves simplifying a pathname. The string format we
> can expect to encounter is covered by the following three examples:
> 
> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"
> 
> The "" are part of the string, and not just string delimiters. These
> strings are inside regular text on the line. The paths are never
> absolute so that you will not encounter "/d1/file.ext".
> 
> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.
> 
> For lines which do not have ../.. in them, this is
> trivial, for example by regexp in sed, emacs etc.

It turns out to be trivial in both cases.

 > The real problem is constructing a regular expression for the DIRNAME 
before the /..

In order to illustrate your question, I reconstructed test data to be 
non-trivial.  The solution is just one regexp with one loop in sed, 
':2dots; s;[^/]*/\.\./;;g; t2dots':

$ sed ':2dots; s;[^/]*/\.\./;;g; t2dots' <<EOM # test data ends with EOM
d01/dir.name/../dir/../file
d02/dir/../d2/../file.ext1
d03/d1/d2/../../file.ext2
EOM
d01/file
d02/file.ext1
d03/file.ext2

Just learned this loop trick from John L. a couple of days ago:-)

Yuan Liu

Re: NON-trivial regular expression problem (could not find on google)

[John W. Krahn]

Instant Democracy wrote:
> 
> Regular expression facilities are slightly varied in
> sed
> awk
> lisp
> emacs-lisp
> Therefore these newsgroups can all contribute to the discussion.
> 
> A frequent problem involves simplifying a pathname. The string format we
> can expect to encounter is covered by the following three examples:
> 
> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"
> 
> The "" are part of the string, and not just string delimiters. These
> strings are inside regular text on the line. The paths are never
> absolute so that you will not encounter "/d1/file.ext".
> 
> The task is to eliminate patterns such as
>     DIRNAME/../
> from the path because they are redundant.


$ perl -le'
@paths = qw( "dir.name/../dir/../file"
             "dir/../d2/../file.ext"
             "d1/d2/../../file.ext"
             "../../../file"
           );
for ( @paths ) {
    print;
    s%([^"]+)% local $_ = $1; 1 while s|[^/]+(?<!\.\.)/\.\./||g; $_ %e;
    print;
    }
'
"dir.name/../dir/../file"
"file"
"dir/../d2/../file.ext"
"file.ext"
"d1/d2/../../file.ext"
"file.ext"
"../../../file"
"../../../file"




John
-- 
use Perl;
program
fulfillment

Re: NON-trivial regular expression problem (could not find on google)

[William Park]

In comp.unix.shell Instant Democracy <democrat@india.com> wrote:
> "dir.name/../dir/../file"
> "dir/../d2/../file.ext"
> "d1/d2/../../file.ext"
> 
> The "" are part of the string, and not just string delimiters. These
> strings are inside regular text on the line. The paths are never
> absolute so that you will not encounter "/d1/file.ext".
> 
> The task is to eliminate patterns such as 
>    DIRNAME/../
> from the path because they are redundant.
> 
> For lines which do not have ../.. in them, this is
> trivial, for example by regexp in sed, emacs etc.
> 
> The real problem is constructing a regular expression for
> the DIRNAME before the /..
> 
> This DIRNAME can be described as a string that contains neither
> / not double-dot but anything else. Perhaps I am overlooking
> something else about DIRNAME.
> 
> The regular expression for the first two cases is demonstrated by this
> sed script although the lisp variants are identical.
> 
> sed 's,\(^.*\)\(/\|"\)\([^/][^/]*/\.\./\)\(.*"\),\1\2\4,'
> 
> The regex I use for DIRNAME is [^/]+ written above using * because
> sed is without plus.

What's wrong with that?  ie.
    sed 's,[^/]\+/\.\./,,g'

> 
> I will follow all the cross-posted newsgroups. If you prefer, because
> some people are allergic to any cross-posting, you can post your reply
> in just one of the groups pertaining to your application, ie lisp/elisp/sed/awk.

-- 
William Park, Open Geometry Consulting, <opengeometry@yahoo.ca>
Linux solution for data management and processing. 

Re: NON-trivial regular expression problem (could not find on google)

[Peter J. Acklam]

democrat@india.com (Instant Democracy) wrote:

> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.

Are they really?  If DIRNAME is a symlink, then there is no
guarantee that these two point to the same place:

   foo/bar/..
   foo

You *must* ensure that DIRNAME is not a symlink before you
simplify the pathnames like this.

Peter

-- 
I wish dialog boxes had a butten saying "Whatever".  I hate being
forced to answer "Yes" or "No" to a question I have no opinion on
whatsoever.  There ought to be a button matching my indifference.

Re: NON-trivial regular expression problem (could not find on google)

[Dr. Yuan Liu]

Peter J. Acklam wrote:
> democrat@india.com (Instant Democracy) wrote:
>>The task is to eliminate patterns such as 
>>    DIRNAME/../
>>from the path because they are redundant.
> 
> Are they really?  If DIRNAME is a symlink, then there is no
> guarantee that these two point to the same place:
> 
>    foo/bar/..
>    foo
> 
> You *must* ensure that DIRNAME is not a symlink before you
> simplify the pathnames like this.

This seems to depend on the shell.  Only C-ish shells will turn symlinks 
into real path and cause a problem.  Bournish and Kornish shells all 
stick with the symbolic path, i.e., foo/bar/.. is always foo.

Yuan Liu

Re: NON-trivial regular expression problem (could not find on google)

[Peter J. Acklam]

"Dr. Yuan Liu" <yliu@stemnet.nf.ca.remove_this> wrote:

> Bournish and Kornish shells all stick with the symbolic
> path, i.e., foo/bar/.. is always foo.

Take a look at the following -- it is an example of a case where
"foo/bar/.." and "foo" is not the same (ksh on Solaris 8):

    /var/tmp $ mkdir -p foo/fee/fie/foe
    /var/tmp $ ln -s fee/fie/foe foo/bar
    /var/tmp $ ls foo
    bar  fee
    /var/tmp $ ls foo/bar/..
    foe

In this case, "foo/bar/.." is "foo/fee/fie/foe/.." which is
"foo/fee/fie" which is *not* the same as "foo".  The reason
is simply that "foo/bar/.." resolves to a different directory
than "foo".  So, you can *not* assume "foo/bar/.." is "foo".

Peter

Re: NON-trivial regular expression problem (could not find on google)

[Bruce Barnett]

democrat@india.com (Instant Democracy) writes:

> The task is to eliminate patterns such as 
>     DIRNAME/../
> from the path because they are redundant.

I assume that you are also trying to deal with security issues.
(Someone trying deliberately to gain access to fles outside of a directory)

Don't forget to include these cases:

        DIRNAME/./../
        DIRNAME/././../ etc.

        And also consider whatever quoting/conversions might occur.
        Hex encoding? Backslashes?

        How are "//" interpreted? Some cases these are treated as a single slash.
        Other cases it's the top of the directory.

        A/DIRNAME//../ - is this A, or / ?



-- 
Sending unsolicited commercial e-mail to this account incurs a fee of 
$500 per message, and acknowledges the legality of this contract.

Re: NON-trivial regular expression problem (could not find on google)

[Yuan Liu]

Peter J. Acklam wrote:
> "Dr. Yuan Liu" <yliu@stemnet.nf.ca.remove_this> wrote:
> 
> 
>>Bournish and Kornish shells all stick with the symbolic
>>path, i.e., foo/bar/.. is always foo.
> 
> 
> Take a look at the following -- it is an example of a case where
> "foo/bar/.." and "foo" is not the same (ksh on Solaris 8):
> 
>     /var/tmp $ mkdir -p foo/fee/fie/foe
>     /var/tmp $ ln -s fee/fie/foe foo/bar
>     /var/tmp $ ls foo
>     bar  fee
>     /var/tmp $ ls foo/bar/..
>     foe

Interesting.  ls and pwd, cd behave differently.  Thanks for pointing out.

Yuan Liu

> In this case, "foo/bar/.." is "foo/fee/fie/foe/.." which is
> "foo/fee/fie" which is *not* the same as "foo".  The reason
> is simply that "foo/bar/.." resolves to a different directory
> than "foo".  So, you can *not* assume "foo/bar/.." is "foo".
> 
> Peter