4.3.3: Example - Filehandle Iterators

Go already provides a good package to read a file line by line. It is bufio.Reader so this iterator is simply a wrapper around that reader.

type fh struct {
    in   *bufio.Reader
    line string
    err  error
}

func Fh(in io.Reader) i.Forward {
    f := fh{in: bufio.NewReader(in)}
    f.Next()
    return &f
}

func (f *fh) Error() error {
    if f.err == io.EOF {
        return nil
    }
    return f.err
}

func (f *fh) Value() interface{} {
    return f.line
}

func (f *fh) AtEnd() bool {
    return f.err == io.EOF
}

We need to check if err is io.EOF or any other error since io.EOF is not an error condition but simply an EOS indicator. Everything else is pretty much self explanatory.

func (f *fh) Next() error {
    if f.line, f.err = f.in.ReadString('\n'); f.err != nil && f.err != io.EOF {
        return f.err
    }
    // chomp
    f.line = strings.TrimSuffix(f.line, "\n")
    return nil
}

The Next() function will read the next line from the file and chomp of the new line indicator.

i.Each(
    Fh(os.Stdin),
    func(itr i.Iterator) bool {
        line, _ := itr.Value().(string)
        fmt.Println("Line: " + line)
        return true
    })

Usage is same as before.
Get the source at GitHub.

4.3: Examples

The first example is to use the Dirwalk iterator from the previous post and create some filters on top of it. To do that, we need to create a Filter iterator.

type FilterFunc func(Iterator) bool

type filter struct {
    f   FilterFunc
    itr Forward
}

func Filter(f FilterFunc, itr Forward) Forward {
    return &filter{f, itr}
}

func (i *filter) AtEnd() bool {
    for !i.itr.AtEnd() {
        if i.f(i.itr) {
            return false
        }
        i.itr.Next()
    }
    return true
}

func (i *filter) Next() error {
    return i.itr.Next()
}

func (i *filter) Value() interface{} {
    return i.itr.Value()
}

func (i *filter) Error() error {
    return i.itr.Error()
}

The Filter iterator is a struct that wraps around a Forward iterator. For most part it simply forwards any method calls to the enclosed iterator. The filtering function is provided by the AtEnd() method. If the wrapped iterator contains further elements, it simply loops until it finds an element that fulfills the requirements of the user supplied FilterFunc. At first, this seems to break the idempotency requirement. But if we call AtEnd() it will loop until it hits the end of stream or finds an element that is not filtered. If we then call AtEnd() again without calling Next(), it simply finds the same element again and returns at the same position.

I've put this Filter iterator into the i package.

Now the problem is simply to create a FilterFunc that performs the filtering we require.

func hasInName(val string) i.FilterFunc {
    val = strings.ToUpper(val)
    return func(itr i.Iterator) bool {
        filename, _ := itr.Value().(string)
        return strings.Contains(strings.ToUpper(filename), val)
    }
}

func not(f i.FilterFunc) i.FilterFunc {
    return func(itr i.Iterator) bool {
        return !f(itr)
    }
}

hasInName performs a case insensitive search, matching val to filenames that Dirwalk returns. not simply negates the result of any FilterFunc.

i.Each(
    i.Filter(not(hasInName("example")), Dirwalk(os.Args[1])),
    func(itr i.Iterator) bool {
        fmt.Println(itr.Value())
        return true
    })

This constructs loops through all filenames under os.Args[1] and returns any that don't contain the string example.

Get the source at GitHub.

4.2.2: dir_walk()

The recursive dirwalk can be rewritten as an Forward iterator.

type dirwalk struct {
    cur   string
    queue []string
    err   error
}

func Dirwalk(filename string) i.Forward {
    // remove trailing /
    strings.TrimSuffix(filename, "/")

    // construct and initialize
    var dw dirwalk
    dw.queue = []string{filename}
    dw.Next()
    return &dw
}

The dirwalk structure contains a queue of filenames to be processed. The cur variable holds the filename that will be returned when Value() is called. Dirwalk simply constructs this structure and returns it, encapsulated as a Forward iterator.

func (dw *dirwalk) Value() interface{} {
    return dw.cur
}

func (dw *dirwalk) Error() error {
    return dw.err
}

func (dw *dirwalk) AtEnd() bool {
    return len(dw.queue) == 0
}

The length of the queue represents the state of the iteration; once it hits zero we are done.

func (dw *dirwalk) Next() error {
    // pop head from queue
    dw.cur, dw.queue = dw.queue[0], append(dw.queue[1:])

    // open file
    var file *os.File
    if file, dw.err = os.Open(dw.cur); dw.err != nil {
        return dw.err
    }
    defer file.Close()

    // stat file
    var stat os.FileInfo
    if stat, dw.err = file.Stat(); dw.err != nil {
        return dw.err
    }
    if stat.IsDir() {
        // read files in directory
        var files []string
        if files, dw.err = file.Readdirnames(0); dw.err != nil {
            return dw.err
        }

        // add files in directory to queue
        for _, subfile := range files {
            dw.queue = append(dw.queue, dw.cur+string(os.PathSeparator)+subfile)
        }
    }
    return dw.err
}

Next is the engine of the iterator. It pops the queue for the current filename and then processes it. If it is a simple file we are done and return. If it is a directory we read through it and put the filenames in it on the queue.

for itr := Dirwalk(os.Args[1]); !itr.AtEnd(); itr.Next() {
    fmt.Println(itr.Value())
}

Using the iterator is very simple, simply construct it and loop through it. This provides an opportunity to write the first higher order function that depends on the Iterator interface. The loop can be written as an Each function as follows:

type EachFunc func(i Iterator) bool

func Each(i Forward, e EachFunc) {
    for ; !i.AtEnd(); i.Next() {
        if !e(i) {
            break
        }
    }
}

It accepts a Forward iterator and a function of type EachFunc, loops through the data stream and calls the function on each Iterator. If the function returns false, the loop breaks. Now we can use the Dirwalk() iterator as follows:

Each(Dirwalk(os.Args[1]), func(itr i.Iterator) bool {
    fmt.Println(itr.Value())
    return true
})

Yes, this is very trivial and of dubious value, but it is a start. You can get the source at GitHub and you can get the source for the Each function in the i package.

1.5: Applications and Variations of Directory Walking

The dirwalk is an generic function (yes, Go lacks generics, we will get to that) that walks a directory tree and executes a supplied file function or a supplied directory function for each entry. 

To start there are some types that need to be declared. ComputeType is our generic type and FileFunc and DirFunc are the two user supplied functions.

type (
 ComputeType interface{}
 FileFunc    func(f *os.File) ComputeType
 DirFunc     func(d *os.File, results []ComputeType) ComputeType
)

Next comes a utility function that is only needed so that the user can call dirwalk without either a FileFunc or a DirFunc if those are not needed. It simply returns a empty value.

func empty() ComputeType {
 var e ComputeType
 return e
}

dirwalk opens a file entry and checks if it is a regular file or a directory. If it is a regular file it calls the FileFunc on it and returns the result. If it is a directory it loops through all entries of that directory calling itself recursively on each entry, collecting the results in a slice. It then calls the DirFunc on the result collection and returns the result of the DirFunc.

func dirwalk(name string, f FileFunc, d DirFunc) ComputeType {
 file, err := os.Open(name)
 if err != nil {
  panic(err.Error())
 }
 defer file.Close()

 stat, err := file.Stat()
 if err != nil {
  panic(err.Error())
 }
 if stat.IsDir() {
  files, err := file.Readdirnames(0)
  if err != nil {
   panic(err.Error())
  }
  name = name + string(os.PathSeparator)
  results := make([]ComputeType, 0)
  for _, subfile := range files {
   results = append(results, dirwalk(name+subfile, f, d))
  }
  if d == nil {
   return empty()
  }
  return d(file, results)
 }
 if f == nil {
  return empty()
 }
 return f(file)
}

Now the lack of proper generics starts to complicate things. So far dirwalk has only used the interface{} type but the point of all this is to compute actual values. Typecasting is needed. To reduce the code the following utility function is used. It tries to typecast and panics on failure. Another way to write this function is to accept a default value and return that on failure.

func int64value(val interface{}) int64 {
 if v, ok := val.(int64); ok {
  return v
 }
 panic(fmt.Sprintf("Unexpected type: %v", val))
}

The FileFunc used here simply returns the size of the file, which is an int64 value.

func filefunc(f *os.File) ComputeType {
 stat, err := f.Stat()
 if err != nil {
  panic(err.Error())
 }
 return ComputeType(stat.Size())
}

DirFunc goes through the results slice, extracting the int64 value for each entry and returning the total.

func dirfunc(d *os.File, results []ComputeType) ComputeType {
 var total int64
 for _, v := range results {
  total += int64value(v)
 }
 return total
}

The main function simply calls dirwalk with the size calculation functions and then extracts the int64 value.

func main() {
 if len(os.Args) != 2 {
  fmt.Printf("Usage %s NAME\n", os.Args[0])
  os.Exit(0)
 }
 fmt.Println(int64value(dirwalk(os.Args[1], filefunc, dirfunc)))
}

Get the source at GitHub.