import scala.collection.mutable
import scala.sys.process.Process
import java.io.File

class Node
{
  val tags = new mutable.ListBuffer[String]
  def report( prefix:Any ) {
    println( tags.mkString( prefix+" [", ",", "]" ) ) }
  def compare( file:File ) {
    if ( tags.size != 2 || "/" != tags.head )
      report( file ) }
}
class Tree extends Node
{
  val kids = new mutable.HashMap[String, Node]
  def leaf( name:String ) =
    kids.getOrElseUpdate( name, new Node )
  def tree( name:String ) =
    kids.getOrElseUpdate( name, new Tree ).asInstanceOf[Tree]
  def branch( path:List[String] ):Tree =
    if ( path.isEmpty ) this else
      tree( path.head ).branch( path.tail )
  def prune( name:String ) {
    val old = kids.remove( name ).get.asInstanceOf[Tree] // throw if not
    leaf( name ).tags ++= old.tags }
  override def compare( file:File ) {
    require( file.isDirectory )
    if ( tags.size < 2 || "/" != tags.head )
      report( file+"/" )
    val list = file.list
    if ( list == null ) report( file+"!" )
    else list foreach { "/" +=: leaf( _ ).tags }
    for ( (name,node) <- kids )
      node.compare( new File( file, name ) ) }
}
object Main
{
  val slash = "/".r
  val parse = "([^ ]+) /(?:([^/]+(?:/[^/]+)*)/)?([^/]+)(/?)".r

  def main( ignored:Array[String] )
  {
    val root = new Tree
    val tags = new mutable.HashMap[String,String]
    for ( parse(tag,path,last,dir) <- Process( "pacman -Ql" ).lines ) {
      val from = if ( path == null ) root else
        root.branch( slash.split(path).toList )
      val node = if ( dir.nonEmpty ) from.tree(last) else from.leaf(last)
      node.tags += tags.getOrElseUpdate( tag, tag ) }
    for ( item <- List( "dev", "proc", "run", "sys", "tmp",
      // these look wrong, but see .head & .tail below
      "certs/etc/ssl", "locale/usr/share", "pkg/var/cache/pacman" ) ) {
      val path = slash.split(item).toList
      root.branch( path.tail ).prune( path.head ) }
    require( !tags.contains( "/" ), "reserved tag" )
    "/" +=: root.tags
    root.compare( new File( "/" ) )
  }
}