regexp from Beautiful Code, in tongues

re.js

function match(re, txt) {
  return re.length == 0 ||
         re.charAt(0) == '^' && matchAt(re.substring(1), txt, 0) ||
         findMatch(re, txt)
}

function findMatch(re, txt) {
  for (var i = 0; i < txt.length; i++) if (matchAt(re, txt, i)) return true
  return false
}

function matchAt(re, txt, at) {
  return re.length == 0 ||
         (re == "$" && txt.length == at) ||
         (re.length > 1 && re.charAt(1) == '*' && matchStar(re.charAt(0), re.substring(2), txt, at)) ||
         (at < txt.length && (re.charAt(0) == '.' || re.charAt(0) == txt.charAt(at)) && matchAt(re.substring(1), txt, at + 1))
}

function matchStar(c, re, txt, at) {
  return at < txt.length && (matchAt(re, txt, at) || (c == '.' || c == txt.charAt(at)) && matchStar(c, re, txt, at + 1))
}

function test(positive, cases) {
  var failed = []
  for (var re in cases) {
    var txt = cases[re]
    for (var i in txt) if (match(re, txt[i]) != positive) failed.push("\"" + re + "\": \"" + txt[i] + "\"")
  }
  var what = positive ? "positive" : "negative"
  log((failed.length == 0 ? ("Succeeded: " + what) : ("Failed: " + what + " " + failed)) + "\n")
}

test(true, {
      "": [""],
      "a": ["a"],
      "abc": ["xyzabc"],
      ".bc": ["xyzbc"],
      "a.c": ["xyzanc"],
      "x.": ["ayx?"],
      "ab*c": ["xacy"],
      "ab*c": ["abc"],
      "ab*c": ["xabbbbbbbbbbc"],
      "^ab*c": ["abbc"],
      "ab*c$": ["abbbbc"]
      }
    )

test(false, {
      "x": [""],
      "ab": ["a"],
      "xyabc": ["xyzabc"],
      ".bcd": ["xyzbc"],
      "ya.c": ["xyzanc"],
      "ab*c": ["xaxcy"],
      "ab*c": ["abzc"],
      "ab*c": ["xabbzbbbbbbbbc"],
      "ab*c$": ["abbbbC"]
      }
    )

RE.scala

case class Ch(c: Char) { def ~=(x: Char) = c == '.' || c == x }

class RE(val regexp: String) {
  def skip(n: Int) = RE(regexp.substring(n))

  implicit def token(c: Char) = Ch(c)
  def c0 = Ch(regexp(0))
  def c1 = regexp(1)

  def ~=(text: String): Boolean = {
    regexp.isEmpty ||
    regexp.startsWith("^") && skip(1).matchAt(text)(0) ||
    ((0 until text.length) exists (matchAt(text)))
  }

  def matchAt(text: String)(at: Int): Boolean = {
    regexp.isEmpty ||
      (regexp.length > 1 && c1 == '*' && skip(2).matchStar(c0, text)(at) ||
       regexp == "$" && text.length == at ||
       at < text.length && (c0 ~= text(at)) && skip(1).matchAt(text)(at + 1))
  }

  def matchStar(c: Ch, text: String)(at: Int): Boolean = {
    at < text.length && (matchAt(text)(at) || (c ~= text(at)) && matchStar(c, text)(at + 1))
  }
}

object RE {
  implicit def apply(regex: String) = new RE(regex)
}

RETest.scala

import org.specs.runner.JUnit4
import org.specs.Specification
import org.specs.execute.FailureException

class RETest extends JUnit4(RETest)

object RETest extends Specification {

  class RegCheck(r: String) extends RE(r) {
    def ~(text: String) = {
      try {
        if (!(this ~= text)) fail("Failed to match \"" + text + "\" with \"" + r + "\"")
      } catch {
        case fe: FailureException => throw fe
        case e =>  fail("Failed matching \"" + text + "\" with \"" + r + "\": " + e)
      }
    }

    def !~(text: String) = {
      try {
        if (this ~= text) fail("Should not have matched \"" + text + "\" with \"" + r + "\"")
      } catch {
        case fe: FailureException => throw fe
        case e: RuntimeException => fail("Failed matching \"" + text + "\" with \"" + r + "\": " + e.getMessage)
      }
    }
  }

  implicit def rc(r: String) = new RegCheck(r)

  "RE" should {
    "accept" in {
      "" ~ ""
      "a" ~ "a"
      "abc" ~ "xyzabc"
      ".bc" ~ "xyzbc"
      "a.c" ~ "xyzanc"
      "x." ~ "ayx?"
      "ab*c" ~ "xacy"
      "ab*c" ~ "abc"
      "ab*c" ~ "xabbbbbbbbbbc"
      "^ab*c" ~ "abbc"
      "ab*c$" ~ "abbbbc"
      true mustBe true
    }
    "discard" in {
      "x" !~ ""
      "ab" !~ "a"
      "xyabc" !~ "xyzabc"
      ".bcd" !~ "xyzbc"
      "ya.c" !~ "xyzanc"
      "ab*c" !~ "xaxcy"
      "ab*c" !~ "abzc"
      "ab*c" !~ "xabbzbbbbbbbbc"
      "ab*c$" !~ "abbbbC"
      true mustBe true
    }
  }
}

These two small classes are samples for our SVPG.

They implement a simple regexp matcher from Beautiful Code.

Nothing special here, just to discuss with friends.