Hacker News Reader

Comment by googlryas | Hacker News Reader

For anyone wondering, '1' * 4301 creates a string of '11111....' 4301 characters long. It doesn't result in an integer value of 4301 like in some other languages.

I find this a strange modification to the language, though probably not a particularly painful one. Has python saved you from yourself when dealing with non-linear built-in algorithms before? IIRC it is also possible to have the regex engine take an inordinate amount of time for certain matching concepts(I think stackoverflow was affected by this?), but the engine wasn't hobbled to throw in those cases, it is merely up to the user to write efficient regex that aren't subject to those problems.

View on HN

Backtracking regular expressions as an intentional or accidental DOS vector are a moderately well-known issue, and while I prefer that a standard library implementation be robust against them, I can see the POV that it's buyer beware.

Converting a string to an integer is somewhat less well known as a DOS vector, more painful to avoid as an application creator, and easier to fix in code.

So there's a cost-benefit argument that you should just do this before you rewrite your regex engine.

> I can see the POV that it's buyer beware.

On the other hands, lots of buyers are not aware that it's an issue, and more frustratingly there are regex engines which are very resilient to it... but are not widely used.

Python's stdlib will fall over on any exponential backtracking pattern, but last time I tried to make postgres fall over I didn't succeed. Even though it does have lookahead, lookbehind, and backrefs, so should be sensible to the issue (aka it's not a pure DFA).

This does seem like a strange level of handholding, even if the motivation makes lots of sense. If you start going down the road of protecting people who don't sanitize user input, you may have quite a long journey ahead...

Well, in C++ int('1' * 4301) is a perfectly valid expression, but it evaluates to 210749, not 4301.

Or some other value.

If sizeof(int)=2, the result is undefined.

Not if CHAR_BIT is 10 or more!

I wonder how much software will fail on platforms where CHAR_BIT is not 8.

I've seen 2 programs in my life that checked for CHAR_BIT (and one was a toy decimal -> binary converter). My guess is basically all of it.

I worked with some MCUs whose only redeeming quality was their cost that had CHAR_BIT=16. The answer is basically everything. It made string processing was profoundly annoying, even for C.

Is it one of TI’s custom ISAs for their DSP line? The TMS430, for example, has a 16 bit char. That causes some unintuitive looking code to fight that.

No, it was with xap [1] chips. TI is also on my list of annoying chip vendors because they're one of the few companies still making big endian ARM chips, which should die in a fire.

[1] https://en.wikipedia.org/wiki/XAP_processor

Whether evaluating that expression results in undefined behaviour also depends on the basic execution character set and the bit width of the machine byte.

it doesn't evaluate to 4301 in Python either ;-)

In Algol 68, you can do that; it's part of the standard prelude. I think that some people who'd worked on Algol 68 in the Netherlands also worked on the ABC language, where it's "1" ^^ 4301, and Guido worked on ABC before Python.

They should have made the analogous inverse operation: '1234' / 2 = ['12', '34']

That's not the inverse of the multiplication though. The inverse would be '33' / 2 = '3', and '1234'/2 should then probably raise a ValueError.

I was more expecting '1111' / 4 = '1'. This would be the inverse operation. However, it opens up even more questions like what to do if your string has mixed values etc

The string multiplication is about _joining_ strings, the inverse is about _splitting_ them in several parts. It's only confusing because the * appends the string to itself, the / is actually very clear.

Disagree. The inverse "string" * value is logically splitting, and then collapsing the repeated values. The logical split can be omitted, but the collapsing cannot.

Naming is hard they say

Operator overloading sure seems to increase the prevalence of foot-guns, security issues, and other gotchas.

str.ccClone(4301) # ConCatenate Clones of the source string N times.

Would even an abbreviated, named, function not be more self documenting and better for human and machine reviews?

I think how Rust does it is fine, but I agree operators are often a mess. Yesterday I was looking at a memory dump where there was a problem in a destructor (a double free was detected) and it was an absolute mess trying to figure out the exact execution location in source code since it was setting the value of a smart pointer which triggered a decrement of a reference counted value in turn triggering a free. It's junk like that which starts to convince me that Linus was right to avoid C++. Rust obviously also has destructors, but it doesn't have the nightmare that is inheritance+function overloading+implicit casting.

> and it was an absolute mess trying to figure out the exact execution location in source code since it was setting the value of a smart pointer which triggered a decrement of a reference counted value in turn triggering a free.

Isn't all that context there in the stack trace?

Yes, probably. Depends on the compiler settings. Stuff can get optimized out and stripped.

When writing the code in the first place, though, it's difficult to see problems like that because it's all hidden behind magic calls to copy constructors, move semantics, and destructor calls. Out of sight, out of mind.

I think it's separate from his point but some of those things could potentially be tail calls, meaning the functions actually leading to the free/delete might not be in the stacktrace even if they were called.

Succinct string operations is honestly like half of what I use python for and the great numeric support with bignum by default and powerful libraries with overloads like numpy and tensorflow is the other half.

Other than that being a terrible name (it's almost impossible to be sure what it does without consulting documentation), I personally do prefer fewer implicit/overloaded operations.

What name would you suggest? That was my 5 min of thought version.

cc prefix for concatenate because that word is very long and it seemed likely that strings may have a large number of different concatenation focused functions that could all share the prefix.

Clone as the type of concatenation operation to perform.

Rust uses `repeat()`, which sounds much more descriptive to me. The types in the function signature make the "clone" part of the name redundant.

Offhand, is repeat(0) an empty string, repeat(1) the input string, etc? If so that's a great name for the function.

Repeat is an iterator, so you can apply it to any type you want, not just strings. You can chain it with other iterators, or collect it into some data structure. But yes, repeat(0) returns an empty iterator.

https://doc.rust-lang.org/std/iter/fn.repeat.html

This is wrong, repeat(0) gives you a Repeat which will repeat 0 forever, that's its purpose:

https://play.rust-lang.org/?version=stable&mode=debug&editio...

This example makes a repeat(0) but asks for just the first 12 things in it, they are, of course, all twelve zeroes. Feel free to adjust it to ask for more if you think maybe there aren't any more, or they stop being zero.

Shit, I should not post in the morning before my first coffee :(

That's the wrong repeat(), I was talking about str::repeat(): https://doc.rust-lang.org/std/primitive.str.html#method.repe...

Shit, I should not post in the morning before my first coffee :(

I originally wrote a reply here that I deleted because I realised somebody introduced the wrong idea below. Yes, the repeat() function on strings does what you describe.

https://doc.rust-lang.org/std/primitive.str.html#method.repe...

str::repeat() behaves exactly as you describe. "No".repeat(4) is "NoNoNoNo" and "What".repeat(0) is "" and so on.

Note that str::repeat() returns a String, not a str, because if n > 1 it obviously needs to allocate somewhere to put the String. As a result it is not available in environments which don't have String, like a tiny embedded device - for them str::repeat() does not exist whereas stuff like str::starts_with() and str::split_once() are fine.

> Operator overloading sure seems to increase the prevalence of foot-guns, security issues, and other gotchas.

How exactly? What would you expect an expression like ('1' * 4301) to give you, and why would you think it would be different from ('caterpillar' * 4301)?

In Lua, the first is 4301 and the second is a runtime error. ('1' .. 4301) is 14301, the equivalent of the weird thing Python is fixing would be spelled `tonumber(('1'):rep(4301))` which is obviously wrong.

To my taste operator overloading is fine, but concatenation isn't addition, so they shouldn't be overloaded because... [gestures vaguely at a half dozen language]

Concatenation is obviously a multiplication!

(By extension, string repeat is exponentiation!)

Well, let's assume that the "expected" behaviour holds, shall we? Let's open up a python REPL and try

  >>> 'caterpillar' * 2
  'caterpillarcaterpillar'

OK, now for something different:

  >>> [1, 2, 3] * 2
  [1, 2, 3, 1, 2, 3]

Marvellous! How about this then:

  >>> True * 2
  2

Wait, what? Hm.

  >>> False * 2
  0

Whoops! Implicit type conversion takes place... Even worse:

  >>> 'abc' + 'efg'
  'acbefg'
  >>> 'efg' + 'abc'
  'efgabc'

Now I'm stumped. Isn't addition supposed to be commutative?

So yeah, without contracts in place, operator overloading is BAD. You can never know what the operator does, or what its properties are by just looking at how it's used. There's simply no enforced rules and so no-one's stopping you from doing

   >>> class Complex:
     def __init__(self, real, imag):
       self.real = real
       self.imag = imag

     def __add__(self, other):
       return Complex(self.real - other.real, self.imag - other.imag)

     def __repr__(self):
       return f'Complex({self.real}+{self.imag})'

   >>> x = Complex(1, 2)
   >>> y = Complex(1, 2)
   >>> x + y
   Complex(0+0j)

Now this intentionally being malicious of course, but plenty of libraries overload operators in non-intuitive ways so that the operator's properties and behaviour isn't obvious. This is especially true if commutative operators are implemented as being non-commutative (e.g. abusing '+' for concatenation instead of using another symbol like '&' for example) or if the behaviour changes depending on the order of operands.

Just give them the TL:DR, friend.

If you didn't read it, you don't know. If you don't know, you have only yourself to blame when demons fly out your nose.

Friends don't let friends spew demons out their nose.

Yeah, all the examples you give rub me up the wrong way. I don't like use of + for concatenate, even though it is present in Rust which I like very much on the whole.

Here's what Rust tells programmers in core::ops (the sub-library whose safe Traits result in operator "overloading" for Rust). I put "overloading" in quotes because these operators just don't exist at all for your type if you don't implement the appropriate Trait.

> Implementations of operator traits should be unsurprising in their respective contexts, keeping in mind their usual meanings and operator precedence. For example, when implementing Mul, the operation should have some resemblance to multiplication (and share expected properties like associativity).

> Isn't addition supposed to be commutative?

No. Maybe crack open an introductory textbook to abstract algebra.

Common convention in abstract algebra is to use + only for commutative algebras (* is used for non-commutative ones as well as in rings).

> No. Maybe crack open an introductory textbook to abstract algebra

Sources please! '+' is used as the standard operator for abelian groups.

You know what, just for shits and giggles I actually DID open an introductory textbook on abstract algebra, just in case my undergraduate degree in maths failed me. Here's what the first chapter says about addition ('+') in Z:

  Here are 4 elementary properties that + satisfies:
  • (Associativity): a + (b + c) = (a + b) + c ∀a, b, c ∈ Z
  • (Existence of additive identity) a + 0 = 0 + a = a ∀a ∈ Z.
  • (Existence of additive inverses) a + (−a) = (−a) + a = 0 ∀a ∈ Z
  • (Commutativity) a + b = b + a ∀a, b ∈ Z.

Also:

  Key Observation: There are naturally occuring sets (other than Z and Q) which 
  come equipped with a concept of + and ×, whose most basic properties are the 
  same as those of the usual addition and multiplication on Z or Q.

I could go on with rings, fields, and vector spaces which also rely on the concept of addition as defined in Z, but I'm really curious to learn about addition being commonly used as a non-commutative operation, especially in the presence of an accompanying multiplication operation.

edit: I forgot to provide proper references, so here's another example including a reference:

  When dealing with Abelian groups, it is customary to use additive notation.
  That is, the group operation will be called "addition," and 
  we will "add" two elements rather than "multiply" them. We write g + h instead of g • h or gh, and ng replaces g^n.

[Walker, Elbert A., "Introduction to Abstract Algebra", 1987; Ch. 2, Pg. 70]

True and False are internally considered to be one and zero, so that example is correct.

String concatenation is not addition. How would you expect commutative string concatenation to work?

I guess, to boil it right down, what I'm asking is "do you understand what the word 'context' means?"

> String concatenation is not addition.

Exactly! So why use the addition operator then? It's not as if alternatives (like the '&' I mentioned) aren't available.

It is really useful sugar for:

  for _ in range(4301):
    llama.append(‘1’)

(there’s probably an easier way to do that but you get the point)

where python can see both sides of the operation and optimize it on the C side of things.

The issue really has nothing to do with that though, it is converting a string to an int which is the whole point of the security update.

Reply on news.ycombinator.com