length method redundant and missing implementations, and LinkedList's non-tail recursive's length

[scabug]

LinkedListLike's length implementation (with which size happens to be overridden) is recursive, but not tail-recursive. Naturally, this means a call to length can result in Stack Overflow.

In a brief research into length and size implementations I couldn't find any other suffering from this malady. So I propose the following implementation for it:

override def length: Int = {
  var len = 0
  var left = this
  while (!left.isEmpty) {
    len += 1
    left = left.next
  }
  len
}

Which happens to be an almost verbattim copy of... I think Stream, replacing tail with next. LinearSeqOptimized also has a very similar definition, but using these instead of left as the variable name, so I'm not sure why Stream is overridding it at all, except, perhaps, as an optimization opportunity missed.

Since tail is present all the way back in Seq, I don't see why the above implementation (but using tail) isn't made default at SeqLike, and let collections which can optimize it override that.

At any rate, LinkedListLike's implementation ought to be fixed.

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-3996?orig=1
Reporter: @dcsobral

[scabug]

@paulp said:
It's worse than that. Here is TraversableOnce:

def size: Int = {
  var result = 0	
  for (x <- self) result += 1
  result
}

Why is this not sufficient. Does someone have evidence that some other way of writing this is faster if you have to traverse the collection regardless? Because otherwise we could just stop overriding it without a clear reason.

[scabug]

@dcsobral said:
Well, I did see that at TraversableOnce, but it uses a closure, which the implementation using while and tail avoids. I guess both come pretty close with specialization and JVM optimizations, but...

[scabug]

@axel22 said:
Tail-recursive and loop-based solution seem to have the same performance.

http://www.copypastecode.com/51823/

Tail-recursive is probably more elegant.

[scabug]

@axel22 said:
(In r23533) Fixes #3996.

No review.