IntegerNode values

Currently client libraries need to parse the value of the integer themselves. We can make this easier by putting the value of the integer on the node itself in cases where it fits into a certain size. If it doesn't fit, we can still provide some niceties in the form of a cleaned up string representation. To do this, we will need:

A new uint32 parameter (value) on IntegerNode.
Parsing to put the right value into value.
A string parameter (string) on IntegerNode.
Parsing to put the right value into string.

A couple of examples.

12345 => IntegerNode[value: 12345, string: "12345"]

In this case, the number is easily representable and nothing has to happen to the string.

0xA_A_A => IntegerNode[value: 2730, string: "0xAAA"]

In this case the value is converted to decimal and the string removes the underscores.

0x80000000 => IntegerNode[value: 4294967295, string: "0x80000000"]

This one is special! We need a way to indicate that the value cannot fit into the 32 bits we've allocated for storing it. Because the number here cannot be represented, we instead reserve the value of 4294967295 (all 1s) as meaning "unrepresentable". In the Ruby API we would make this nil or maybe :unrepresentable or something similar.

Note that we're explicitly not handling negative integers because in our parse tree -1 is represented as Unary(Integer()).

Thanks for opening an issue to discuss this.
Previous discussion about this: #622

Note that we're explicitly not handling negative integers because in our parse tree -1 is represented as Unary(Integer()).

Ooh, that is quite surprising:

$ bin/parse -e '-13'
#<YARP::ParseResult:0x00007f37b4c64010
 @comments=[],
 @errors=[],
 @value=
  ProgramNode(0...3)(
    [],
    StatementsNode(0...3)([CallNode(0...3)(IntegerNode(1...3)(), nil, (0...1), nil, nil, nil, nil, 0, "-@")])
  ),
 @warnings=[]>

So it calls -@ on the positive Integer.
That means for compilation/execution one needs to detect this pattern to avoid the non-trivial overhead of a call per negative integer literal.

I think it would be more intuitive to have IntegerNode support negative values directly, what's the rationale to represent it as a call when this call is not done semantically?

I am happy to add support for an int32 type.
Agreed to use the min/max value to mean "use the string instead", I thought the same.

0xA_A_A => IntegerNode[value: 2730, string: "0xAAA"]

It would be much more convenient if the string was always base 10 to parse it. For instance new BigInteger(String) in Java only handles decimal numbers. If we only remove the _ there is no much value, we might a well use the logic for Kernel#Integer if we need to handle 0x.../0b.../0....
OTOH I guess the main blocker to do this is that would mean YARP would need some big integer representation internally to convert from one base to another, which I can understand might be out of scope of YARP.
(maybe there is a way to convert base without needing it? I don't know)

So, maybe let's not provide the string since it doesn't help much over using the node location, and consumes a significant number of bytes when serialized?

In the Ruby API we would make this nil or maybe :unrepresentable or something similar.

I think ideally in the Ruby API it would return the actual value, using Kernel#Integer() if the value is the special "too big" value. It could be done by just writing that value or so method manually for IntegerNode.

Ahh yeah, that makes a lot of sense. Actually we can provide that interface today, I think I'll add that.

@kddnewton

@kddnewton I was going to open an issue on us depending on source for the integer string but this issue should handle that right?

@enebo

@enebo I'm still not clear on the actual solution here. We can embed the value for < 32 bit integers but what do you want to do for larger than that?

@kddnewton

@kddnewton For syntax tools I guess the tree should always have the string (whether retrieved from source or as a constant). I don't think we will need that string in compiling though....except read on.

Idea

IntegerNode -> FixnumNode and BignumNode

FixnumNode -> value: int64_t
BignumNode -> value: constant string thing (but not from source)

I think there is disparity on platforms between how much is in a Fixnum before becoming a Bignum but I think all platforms can store a fixnum in int64_t. If this was still a problem I think we could make a SmallFixnumNode with int32_t.

Err the SmallFixnumNode part of that is a discussion on how to lay that out in case where there is only int32_t. I am not clear on why in32_t was the type we have to use so???

Fixnum depends on machine word size and also it's - 1 bit on CRuby.
So it feels a bit messy to have something called a FixnumNode.

I think this would be best, it's similar to the issue description:

an int32_t for fast access, because it's very rare to have >32 <64 bit integer literals. Could be 4 bytes serialized or ZigZag varint encoding (https://protobuf.dev/programming-guides/encoding/#signed-ints). Field name could be int32_value or so to be obvious. If the value is min/max (I'd choose min) then it doesn't fit in a signed 32-bit int and
an optional string field, only provided if it doesn't fit in int32. Optional so it doesn't waste serialized size and memory needlessly. We probably shouldn't unescape the literal because removing _ is trivial. We'd still have to handle 0x etc prefixes which are more complex anyway, and needed anyway to implement Kernel#Integer.

That string field though would then just be the same as the node startOffset and length. So we wouldn't really need it, except for serialization as there we wouldn't want to need to access the source (and all strings/constants would just be part of the serialized output so those are fine). Maybe we could serialize the IntegerNode specially but still that wouldn't add the field when creating the deserialized IntegerNode (in Ruby or Java or Rust).

I think a clear first step is adding that int32_t int32_value field to IntegerNode. For the string it seems much less clear and anyway we should probably embed all constants & strings in the serialized output first, that might make things clearer.

Maybe just avoiding the Fixnum/Bignum terms is one way, and then we could have:

SmallIntegerNode for integers that fit in int32_t, with a int32_t value field.
BigIntegerNode for integers that don't fit in int32_t, with a string field.

I like the single IntegerNode better though from a user POV, especially in Ruby where it doesn't matter if big or small, there is a IntegerNode#value method anyway.

"Fixnum depends on machine word size and also it's - 1 bit on CRuby.
So it feels a bit messy to have something called a FixnumNode."

Let's call it something else then...Fixed64BitFoobarNode. My original point is if prism can return a int64_t then the implementations can build/compile that into whatever is appropriate. The fact that 64 bits seems to be enough for all impls to represent at least a fixnum I think will make it fine. If they use less then I guess they make a Bignum out of it from a certain range.

"an int32_t for fast access, because it's very rare to have >32 <64 bit integer literals."

You are concerned about the speed of accessing a single field that you will only access once? Size I may have understood but is this really an issue?

"So we wouldn't really need it, except for serialization as there we wouldn't want to need to access the source (and all strings/constants would just be part of the serialized output so those are fine)."

If we don't need it why would we add it for serialization?

"
SmallIntegerNode for integers that fit in int32_t, with a int32_t value field.
BigIntegerNode for integers that don't fit in int32_t, with a string field.
"

Personally I am ok with the naming on this but I would still prefer int64_t since it would cleanly be capable of what a fixnum is in 4 of the 5 impls (mruby I think is different)?

You are concerned about the speed of accessing a single field that you will only access once? Size I may have understood but is this really an issue?

By fast access there I meant mostly "no need to parse a string", but not only.
For int32_t vs int64_t yes I think it's a clear loss for size for int64_t, because in the C struct it will be 8 vs 4 bytes and same for serialized unless zigzag varint in which case it doesn't matter for serialized size. Also (signed) int64_t is likely difficult to deal with, e.g. we can't represent 2**63 in Java, and neither can CRuby in a Fixnum, so there will be overhead for such values (which are valid in zigzag encoding and e.g. 2**63 represents 2**62), which might cause general overhead for the method implementing the deserialization of that value.

If we don't need it why would we add it for serialization?

That way we wouldn't need to access the source for deserialization.

Yet another possibility would be to have arbitrary large signed varints for this. That could work well for deserialization, but it's not clear how we could represent that in C at all without some kind of bigint functionality, so it doesn't seem a practical solution. Unless there is a fairly easy way in C to parse an integer literal > 2**64 as an array of int32_t/int64_t maybe, in bases 2, 8, 16 and more difficult base 10?

and more difficult base 10?

Well, this might be one way: https://stackoverflow.com/a/7987670/388803, and having the sign be a separate bit or so for simplicity.

Putting this onto the list for next year.

As a note, we already have varsint which can represent any int32_t since #1944.

Done on main

Navigation Menu

Repository navigation

IntegerNode values #1098

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

IntegerNode values #1098

Description

Activity

eregon commented on Jun 29, 2023

eregon commented on Jun 29, 2023

kddnewton commented on Jun 30, 2023

enebo commented on Oct 13, 2023

kddnewton commented on Oct 13, 2023

enebo commented on Oct 13, 2023

enebo commented on Oct 13, 2023

eregon commented on Oct 13, 2023

eregon commented on Oct 13, 2023

enebo commented on Oct 13, 2023

eregon commented on Oct 14, 2023

eregon commented on Oct 14, 2023

kddnewton commented on Dec 7, 2023

eregon commented on Dec 8, 2023

kddnewton commented on Feb 23, 2024

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions