Alternative way to constrain the use of string

[Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>]

"FPDS" (stands for "Following Pattern Distinguished String" is the key
concept of detecting string/data abuse.


first, define three state type fpdsType.
fpdsType can be either "no", "string" or "anyString".

* OR operation (commutative)
  "no"||"no"          -> "no"
  "string"||"string"  -> "string"
  "anyStr"||"anyStr"  -> "anyStr"
  
  "string"|| X        -> "string"
  "anyStr"|| "no"     -> "anyStr"



The algorithm consists of two procedures. Procedure "check" detects if
the given pattern abuses string/data. Procedure "calcFPDS" computes if
the given pattern can start with string/data/anyString.

The check process starts by check( topLevelPattern, "no" ).



algorithm: check
   detects abuse of string/data.

input:  $pattern  : TREX pattern
        $fpds     : fpdsType

output: nothing

if($pattern is "<string>e</string>" or "<data>e</data>"
           and $fpds="string","anyStr")
  this pattern is illegal.

if($pattern is "<group>p1 p2</group>")
  check( p2, $fpds )
  check( p1, calcFPDS(p2,$fpds) )

if($pattern is "<oneOrMore> p1 </oneOrMore>")
  check( p1, $fpds || calcFPDS(p1,$fpds) )

if($pattern is "<interleave> p1 p2 ... pn </interleave>")
  for i=1 to n do
    $fpds |= calcFPDS(pi,false)
  next
  for i=1 to n do
    check( pi, $fpds )
  next

if($pattern is "<choice> p1 p2 </choice>")
  check( p1, $fpds )
  check( p2, $fpds )

if($pattern is "<anyString />" and $fpds=="string")
  this pattern is illegal.

if($pattern is "<attribute>p</attribute>" or "<element>p</element>")
  check( p, "no" )

exit function.

------------------------------------------------------------------

algorithm: calcFPDS
  computes if the given pattern can start with string literal.

input:  $pattern  : TREX pattern
        $fpds     : fpdsType
output: fpdsType

if($pattern is "<string>e</string>" or "<data>e</data>" and $fpds=true)
  return "string"

if($pattern is "<group>p1 p2</group>")
  return calcFPDS(p1, calcFPDS(p2,$fpds))

if($pattern is "<oneOrMore> p1 </oneOrMore>")
  return calcFPDS(p1,$fpds)

if($pattern is "<interleave> p1 p2 </interleave>")
  return calcFPDS(p1,$fpds)||calcFPDS(p2,$fpds)

if($pattern is "<choice> p1 p2 </choice>")
  return calcFPDS(p1,$fpds)||calcFPDS(p2,$fpds)

if($pattern is "<anyString />")
  return "anyStr"

if($pattern is "<attribute />" or "<element />")
  return "no"

exit function.


----
Kohsuke KAWAGUCHI
Phone: 650-786-0721