DEV Community: Michal Ciesielski

Interactive project report with Jira and LLM

Michal Ciesielski — Sun, 08 Sep 2024 19:55:06 +0000

For all projects I worked on, I used some sort of project management system where project scope was defined as a list of tasks (tickets), and progress was reported by changing task statuses.

While such project management systems offer various dashboards and reports, interpreting a long list of tasks with cryptic titles created by engineers is not trivial. To provide transparency for project sponsors and customers, I had to manually create a project report and then answer related questions.

What if instead we asked LLM for help? The idea is simple: fetch all project tasks and feed them to LLM asking for the report. Then start a chat allowing for further questions.

Collecting data

We will use Jira for this experiment as it's a popular tool with easy-to-use REST API. The example project, for which we'll create the report, is very technical - it's about creating a build script that can detect what the code uses and generate the required instructions for the build system. Such a project will surely have technical tasks with cryptic titles.

Let's start with fetching tasks. The project in the example setup is represented as a single parent ticket (an epic) with a list of child tickets (tasks). For each task, we will fetch the full history to see how the ticket status changes over time. Using Python's Jira client the implementation is simple. Note in Jira nomenclature the term issue is used instead of ticket which is reflected in the code.

jira = JIRA(server=os.environ["JIRA_SERVER"], basic_auth=(os.environ["JIRA_USER"], os.environ["JIRA_TOKEN"]))

def fetch_issues(epic_key):
    issues = []
    print("Loading epic data...", end="", flush=True)
    issues.append(jira.issue(epic_key))
    print("done")

    print("Loading tasks...", end="", flush=True)
    child_issues = jira.search_issues(f"parent = {epic_key}")
    for issue in child_issues:
        issues.append(jira.issue(issue.key, expand="changelog"))
    print("done")

    return issues

Since fetching all tickets with history takes a while, it is handy to store this data locally for further experiments. While playing with the implementation I used the below functions to save tasks to, and load them from a file:

def save_issues(filename, issues):  
    with open(filename, "x") as file:
        file.write("[")
        file.write(",".join(
            json.dumps(issue.raw) for issue in issues))
        file.write("]")

def load_issues(filename):
    with open(filename, "r") as file:
        data = json.load(file)
        return [Issue(jira._options, jira._session, raw=raw_issue)
            for raw_issue in data]

Preparing data

The next step is to prepare data for LLM. Raw Jira data in JSON format is quite verbose, we don't need all these extra fields. Let's extract basic information: subject, description, type, status, and creation date. From history, we will only extract ticket status changes along with their date and author, ignoring changes to other fields.

All this information will be stored as plain text. I have seen people using JSON or XML as LLM input, but my observation is LLMs are very good at interpreting plain text data. Plus with this approach, I don't need to worry about formatting text fields to be JSON or XML compatible. The only processing I do is to strip empty lines from the description, and the primary reason is to make it easier for me to look at results.

def strip_empty_lines(s):
    return "".join(line for line in (s or "").splitlines() if line.strip())

def issue_to_str(issue):
    return f"""
{issue.fields.issuetype}: {issue.key}
Summary: {issue.fields.summary}
Description: {strip_empty_lines(issue.fields.description)}
Type: {issue.fields.issuetype}
Status: {issue.fields.status}
Created: {issue.fields.created}
Priority: {issue.fields.priority}
"""

def changelog_to_str(changelog, changeitem):
    return f"""
Author: {changelog.author.displayName}
Date: {changelog.created}
Status change from: {changeitem.fromString} to: {changeitem.toString}
"""


def history_to_str(issue):
    if issue.changelog is None or issue.changelog.total == 0:
        return ""
    history_description = ""
    for changelog in issue.changelog.histories:
        try:
            statuschange = next(filter(lambda i: i.field == "status", changelog.items))
            history_description += changelog_to_str(changelog, statuschange)
        except StopIteration:
            pass
    return history_description

#this function assumes the first issue is an epic followed by tasks.
def describe_issues(issues):
    description = "Project details:"
    description += issue_to_str(issues[0])
    description += "\nProject tasks:"
    for issue in issues[1:]:
        description += "\n" + issue_to_str(issue)
        description += f"History of changes for task {issue.key}:"
        description += history_to_str(issue)
    return description

The epic I use for this experiment has 30 tasks that have between 1 and 15 status changes in their history. I will not quote the full output of the describe_issues function, but to give you an idea of how it looks here is a short excerpt:

Project details:
Epic: TKT-642
Summary: Create universal build script
Description: 
Type: Epic
Status: In Development
Created: 2024-05-24T10:48:33.050+0200
Priority: P4 - Low

Project tasks:

Task: TKT-805
Summary: add test reporting for e2e tests
Description: 
Type: Task
Status: In Progress
Created: 2024-09-06T09:56:33.919+0200
Priority: P4 - Low
History of changes for task TKT-805:
Author: Jane Doe
Date: 2024-09-06T10:04:15.325+0200
Status change from: To Do to: In Progress

Task: TKT-801
Summary: Sonar detection
Description: * add sonar config file detection *
Type: Task
Status: In Progress
Created: 2024-08-30T13:57:44.364+0200
Priority: P4 - Low
History of changes for task TKT-801:
Author: Jane Doe
Date: 2024-08-30T13:57:58.450+0200
Status change from: To Do to: In Progress

Task: TKT-799
Summary: Add check_tests step
Description: 
Type: Task
Status: Review
Created: 2024-08-29T18:33:52.268+0200
Priority: P4 - Low
History of changes for task TKT-799:
Author: Jane Doe
Date: 2024-08-29T18:40:35.305+0200
Status change from: In Progress to: Review
Author: Jane Doe
Date: 2024-08-29T18:33:57.095+0200
Status change from: To Do to: In Progress

Prompting

The prompt we'll use consists of two parts. First, it gives an instruction to create a report, detailing what specific information we want in the report. Then we insert ticket information prepared in previous paragraphs. LLMs tend to give verbose responses, so we ask specifically to not add any additional explanation. As the experiment is performed in the terminal, we'll also ask to make the response terminal-freindly.

def create_prompt(isses_description):
    return f"""
    Using below information from jira generate executive report that focuses on what was done and what is remaining.
    Provide project progress information. Point out problematic tasks and what may be wrong.
    Use status change history to point out tasks that were worked on for too long or have been reopened many times. 
    Check if you can detect other problems from tasks or their history.
    Provide only text content that can be displayed on terminal, without any additional explanation or markdown.
    {isses_description}
    """

The LLM I use for this experiment is Anthropic's Claude 3.5 Sonnet. In addition to sending the prompt message, we'll also specify identity. Identity could be just added as another line at the beginning of the prompt, but since the plan is to follow up with questions (create an interactive chat), Claude's documentation recommends setting identity as a separate system parameter in such a scenario.

def send_messages(messages):
    client = anthropic.Anthropic(api_key=os.environ["ANTHROPIC_KEY"])
    identity = "You are a seasoned IT program manager. You have very good communication skills, your answers are concise and focus on key insights."
    message = client.messages.create(
        system=identity,
        max_tokens=2048,
        messages=messages,
        model="claude-3-5-sonnet-20240620"
    )
    return message.content[0].text

def generate_report(prompt):
    messages=[
        {
            "role": "user",
            "content": prompt 
        }]
    return send_messages(messages)

Let's put this together and run:

if __name__=="__main__":
    issues = fetch_issues('TKT-642')
    descrption = describe_issues(issues)
    prompt = create_prompt(description)
    report = generate_report(prompt)
    print(report)

Below is the full report I received from Claude:

Executive Report: Universal Build Script Project (TKT-642)

Project Progress:

11 out of 24 tasks are completed (45.8%)

5 tasks are in progress or review (20.8%)

8 tasks remain to be started (33.3%)

Key Accomplishments:

Created prototype jinja template for builder

Implemented config extension and validation

Added unit tests execution step

Integrated support for sonar scanning

Created image for building config and tech scripts

In Progress:

Adding test reporting for e2e tests

Implementing filtering logic for environments and Sonar detection

Developing developer documentation

Problematic Areas:

Task TKT-734 (Add config extension) went through multiple status changes, indicating potential issues or complexity.

Task TKT-697 (Add support for sonar scanning) has been reopened multiple times, suggesting implementation challenges.

Task TKT-715 (Create developer documentation) has been in progress for an extended period without completion.

Upcoming Work:

Integration of the build system into various services (authentication, database-api, shopping-cart, reporting, localization)

Adding support for monorepos and custom jobs

Creating user documentation

Recommendations:

Review the implementation of config extension and sonar scanning to address recurring issues.

Prioritize the completion of developer documentation to support team adoption.

Begin planning for the integration of the build system into remaining services.

Consider reassessing the priority of tasks that have remained in the "To Do" state for an extended period.

Overall, the project is making steady progress, with nearly half of the tasks completed. However, attention should be given to resolving recurring issues and completing in-progress tasks to maintain momentum.

The result is quite good. It did miscount tickets - in various runs I did it gave me a different number, but never a correct number of 30. Well, LLMs are known for not being able to count r's in the word strawberry. But the summary is correct, recommendations are also reasonable.

Asking questions

Now let's create an interactive session and ask some questions. We'll start with a pre-defined question which is the original prompt we used to generate the report. Then we will read the user's input and attach it to messages. Each response, along with the report is also recorded in the messages chain.

def interactive_session(prompt):
    messages = []
    user_input = prompt
    while user_input != "exit":
        messages.append({
            "role" : "user",
            "content" : user_input
        })
        response = send_messages(messages)
        print(response)
        messages.append({
            "role" : "assistant",
            "content" : response
        })
        user_input = input("QUESTION: ")
    return messages

To run this, just replace generate_report in the main section of the script with interactive_session. Below is a recording of an example session I did. I omitted from the quote the first response which just prints out the report.

QUESTION: how many engineers the team counts?

Based on the information provided in the task histories, I can identify at least three distinct engineers working on this project:

John Smith

Jane Doe

Mike Carpenter

These three names appear frequently in the status change histories for various tasks. However, it's important to note that this may not represent the full team size. There could be other team members who haven't made changes recorded in these specific task histories, or who are involved in the project in other capacities not reflected in this data.

To get an accurate count of the team size, you would need additional information beyond what's provided in these task histories.

QUESTION: is unit test execution task done yet?

Yes, the unit test execution task is completed. Specifically, task TKT-700 with the summary "Add unit tests execution step" is marked as Done. Here's the relevant information:

Task: TKT-700
Summary: Add unit tests execution step
Status: Done

The history of changes for this task shows that it was moved to "Done" status on 2024-08-02, after going through the typical workflow stages (To Do -> In Progress -> Review -> PREPROD VERIFICATION -> READY FOR PRODUCTION -> Done).

QUESTION: does the scope include running some sort of static code analysis tool?

Yes, the project scope includes running static code analysis. Specifically, there's a task for implementing Sonar scanning, which is a popular static code analysis tool. Here are the details:

Task: TKT-697
Summary: Add support for sonar scanning
Status: Done

This task was completed and moved to "Done" status on 2024-09-02. The implementation of Sonar scanning indicates that static code analysis is part of the universal build script project.

Additionally, there's another related task that's currently in progress:

Task: TKT-801
Summary: Sonar detection
Status: In Progress

This task mentions "sonar detection" in its summary, which further confirms that Sonar (a static analysis tool) is being integrated into the build process.

These tasks demonstrate that static code analysis, particularly using Sonar, is included in the project scope and has been largely implemented.

QUESTION: what are the 3 biggest risks of the project?

Based on the provided information, the three biggest risks for this project appear to be:

Integration Delays:
Several tasks for integrating the build system into various services (localization, reporting, shopping cart, authentication, database API) are still in "To Do" status. This poses a risk of delays in widespread adoption of the universal build script across different services. Failure to integrate across all intended services could limit the project's overall impact and value.

Documentation Lag:
The task for creating developer documentation (TKT-715) has only recently moved to "In Progress" after being in "To Do" for an extended period. Additionally, the user documentation task (TKT-714) is still in "To Do" status. This lag in documentation creation risks hindering the adoption, proper use, and maintenance of the new build system. It could lead to misuse, inefficiencies, or resistance to adoption due to lack of clear guidance.

Complexity in Implementation:
Several tasks, particularly those related to Sonar scanning (TKT-697) and config extension (TKT-734), have shown multiple status changes between "In Progress" and "Review". This pattern suggests potential technical challenges or uncertainties in implementation. There's a risk that these complexities could lead to bugs, performance issues, or maintenance difficulties in the future if not properly resolved.

These risks could potentially impact the project's timeline, adoption rate, and overall success if not properly managed and mitigated.

That was surprisingly good. I do like the fact the LLM is using generic knowledge in addition to prompt data, so it was able to answer questions about the "static code analysis tool" even though no ticket data mentions those terms. The answers are a bit too verbose, more experiments with the prompt are required - probably appending instructions to each user's query would help shape better answers.
Issues such as miscounting tickets should be easy to solve, we can calculate base statistics and include them in the prompt itself.

Building Zerocalc, part V - Iced UI, subscriptions, and code release!

Michal Ciesielski — Sun, 28 Jul 2024 20:07:04 +0000

The UI

In the last part of the series, we will build a simple UI for Zerocalc. We will use the Iced GUI library as it has a very nice API and very poor documentation which is a great opportunity to dig into its internals...

The UI will consist of two panes, one containing an editor to enter expressions and the other one showing a result:

.________________.
|.______________.|
||   2+2  |  4  ||
||        |     ||
||        |     ||
|.______________.|
.________________.

The Iced-based application consists of three main elements:

Application state
View that defines how to visualize the state
Messages that define state changes

The state of Zerocalc UI consists of expressions entered by the user (input text) and the result of evaluating those expressions (output text). This can be described as the following structure:

struct Editor {
    content: text_editor::Content,
    result: String,
}

The UI components will be laid out in a single row. I am using TextEditor widget for editing (created using text_editor helper function) and Text widget to display results (created using text helper function) with a vertical rule to separate them visually.

impl Application for Editor {

    fn view(&self) -> Element<Self::Message> {
        let input = text_editor(&self.content)
            .height(Length::Fill)
            .padding(0)
            .on_action(Message::Edit);

        let output = text(self.result.clone()).size(16);

        row![
            container(input).padding(12).width(Length::FillPortion(3)),
            Rule::vertical(2),
            container(output).padding(12).width(Length::FillPortion(1))
        ]
        .into()
    }

The state is manipulated in two situations:

When the user edits the text
When expressions are evaluated

This means we need two messages - one that tells the input text should be updated (Edit), and one that tells results should be updated (Evaluate):

enum Message {
    Edit(text_editor::Action),
    Evaluate,
}

With those messages, we can now implement the Iced update function that will manipulate the state:

// impl Application for Editor continued

    fn update(&mut self, message: Message) -> Command<Message> {
        match message {
            Message::Edit(action) => self.content.perform(action),
            Message::Evaluate => self.update_result(),
        };
        Command::none()
    }

The update_result function just calls the parsing and evaluation functions described in previous episodes of the series and stores the output in self.result field. Details can be found in the full source code I link to at the end of this article.

The key problem to solve is how to trigger the Evaluate message. We could simply do this after each keystroke, but that's lots of wasted evaluations. I'd like to do some debouncing and only re-evaluate periodically, let's say every 250ms.

This sounds similar to displaying the clock on the screen which also is updated periodically. Luckily the Iced library comes with the clock example that shows how to do exactly that. Following the example we define the subscription method that will produce Evaluate messages every 250ms:

    fn subscription(&self) -> Subscription<Message> {
        iced::time::every(Duration::from_millis(250))
            .map(|_| { Message::Evaluate })
    }

The iced::time::every function requires one of the asynchronous runtimes to be installed as a dependency. Zerocalc UI will use smol as it is smaller, simpler, and easier to reason about than the most popular tokio runtime. We need to add smol feature to iced dependency in Cargo.toml:

[dependencies]
iced = {version="0.12.1", features=["debug", "smol"] }

Now we can build, run, and - voila, it works!

Iced Subscription

While I am happy it does work, the magic in the subscription method is bothering me. How does the Subscription in Iced work?

Let's look at how Subscription is defined. It's part of iced_futures crate:

pub struct Subscription<Message> {
    recipes: Vec<Box<dyn Recipe<Output = Message>>>,
}

It is a list of objects that implement Recipe trait. Since the compiler does not know what those recipes will be, they are kept as pointers to trait implementations, which in most object-oriented languages would be a pointer to an interface but in rust terms, it's a Box<dyn Recipe>. The Recipe trait has two methods - hash that a runtime can use to identify the recipe and stream that creates a stream of Messages:

pub trait Recipe {
    type Output;
    fn hash(&self, state: &mut Hasher);
    fn stream(self: Box<Self>, input: EventStream) -> BoxStream<Self::Output>;
}

The stream method receives EventStream as input which it can (but does not have to) use to produce messages. EventStream is a stream of UI events such as keystrokes, mouse movements, window events, etc.

The iced::time::every function creates an instance of Recipe called Every and wraps it in the Subscription:

    pub fn every(
        duration: std::time::Duration,
    ) -> Subscription<std::time::Instant> {
        Subscription::from_recipe(Every(duration))
    }

The Every implementation is simple - it ignores the EventStream parameters and just creates smol's timer. Timer in turn implements standard rust's Stream

    struct Every(std::time::Duration);
    impl subscription::Recipe for Every {
        type Output = std::time::Instant;

        fn hash(//...

        fn stream(
            self: Box<Self>,
            _input: subscription::EventStream,
        ) -> futures::stream::BoxStream<'static, Self::Output> {
            use futures::stream::StreamExt;

            smol::Timer::interval(self.0).boxed()
        }
    }
}

Going back to our subscription method implementation:

    fn subscription(&self) -> Subscription<Message> {
        iced::time::every(Duration::from_millis(250))
            .map(|_| { Message::Evaluate })
    }

The iced:time::every creates a Subscription that every 250ms will spill out the current timestamp (as the std::time::Instance value). Since we need to produce instances of Message::Evaluate instead, we call Subscription::map that changes Subscription<std::time::Instance> into Subscription<Message>. We can ignore the timestamp value as we just need a trigger that tells us it's time to calculate results. A sample clock implementation could use this value to display the current time on the screen.

Now we know what Subscription does and how it is created. Let's take a look at how it is consumed. The entry point is in the application's main loop, which is defined in winit create that Iced uses to work with application windows across different platforms. Each time current UI events are processed, winit generates AboutToWait event that tells the application it's time to look at "other stuff". This triggers update function which is defined as follows:

/// Updates an [`Application`] by feeding it the provided messages, spawning any
/// resulting [`Command`], and tracking its [`Subscription`].
pub fn update<A: Application, C, E: Executor>(

    //do some more work not related to this article...

    let subscription = application.subscription();
    runtime.track(subscription.into_recipes());
}

Here the Iced framework calls our subscription method and extracts recipes from the Subscription we returned. The recipes are passed on to runtime. The runtime updates the list of alive subscriptions. It uses the subscription's hash method to identify subscriptions. This explains the following comment from the Iced documentation:

A Subscription will be kept alive as long as you keep returning it, and the messages produced will be handled by update.

If we want to stop a subscription, we simply stop returning it from the subscription method and the runtime will remove it.

What happens next is runtime calls recipes to create streams and waits for next items to be returned from those streams. The runtime holds a reference to the application's event loop and each time an item is returned from the stream it is passed on to the event loop. Thanks to this if we return Message::Evaluate from the stream it will be put into the event loop and eventually will be passed on to our application's update method. And that's how we know ~250ms have passed and it's time to recalculate results.

Source code

Full source code created while writing this series is available on GitHub under MIT license:
https://github.com/michal1024/zerocalc

Sources:

Building Zerocalc, part IV - precision

Michal Ciesielski — Sun, 07 Jul 2024 10:11:46 +0000

Performing arithmetic calculations using computers results in limited precision. Operations on integers are accurate up to minimum and maximum values allowed by the selected integer representation. Using the i128 type we can get any number up to 38 digits long which is enough assuming you will not try to count atoms in the known universe (~10^79). Floating point operations are more challenging as not all values can be represented in the standard used by Rust (IEEE 754). For example:

1.1 * 2.2 = 2.4200000000000004

There are libraries, such as rug, that can help us deal with this problem, offering extended precision and big integer operations. For Zerocalc I am going to do something simpler and still get some benefits of improved precision: as long as we operate on integers, we will stick to integers and only switch to floats when necessary.

For example, when adding or multiplying integers, the result is an integer. When dividing, if the division has no reminder, we will use integers. I also want to make the operations easy to write just as we used normal primitives, for example, I want to write:

x = 1
y = 2
result = x * y

and don't think about what primitive types to operate on.

To achieve this we will use two Rust features: enums and std::ops traits which are similar to C++'s operator overloading. Let's start with defining our numbers. We will derive from PartialEq to allow comparisons of Number instances:

#[derive(Debug, PartialEq)]
pub enum Number {
    Int(i128),
    Float(f64),
    NaN
}

The extra NaN or Not a Number option will help us handle edge cases such as division by 0. Rust's floating point numbers already have similar values defined as constants such as std::f64::NAN. To make it easy to create Number instances in tests, we can add a helper conversion implementations:

impl From<f64> for Number {
    fn from(value: f64) -> Self {
        if value == std::f64::NAN || value == std::f64::INFINITY || value == std::f64::NEG_INFINITY {
            Number::NaN
        } else {
            Number::Float(value)
        }

    }
}

impl From<Number> for f64 {
    fn from(value: Number) -> Self {
        match value {
            Number::Int(i) => i as f64,
            Number::Float(f) => f,
            Number::NaN => f64::NAN
        }
    }
}

impl From<i128> for Number {
    fn from(value: i128) -> Self {
        Number::Int(value)
    }
}

impl From<Option<i128>> for Number {
    fn from(value: Option<i128>) -> Self {
        match value {
            Some(i) => Number::Int(i),
            None => Number::NaN
        }
    }
}

With this, we can create a Number from actual values easily:

let x: Number = 1.into(); // creates Number::Int(1)
let y: Number = 1.0.into(); // creates Number::Float(1.0)

You may be wondering why we have two conversions for i128 - one for the actual integer and one for the option. This will help us to handle errors as we will see in the next step.

Now we can define the first operator - addition. The rules for addition will be:

If any operand is NaN, the result is NaN.
If both operands are integers, the result is an integer.
In all other cases (one or both operands are float) the result is float.
If the result cannot be represented as i128 or f64 - return NaN.

impl Add for Number {
    type Output = Number;
    fn add(self, rhs: Self) -> Self::Output {
        match (self, rhs) {
            (Number::NaN, _) | (_, Number::NaN) => Number::NaN,
            (Number::Int(l), Number::Int(r)) => l.checked_add(r).into(),
            _ => {
                let l: f64 = self.into();
                let r: f64 = rhs.into();
                (l + r).into()
             }
        }
    }
}

The checked_add method returns an option - Some if the result can be safely represented as i128, None in other cases. This is where our From<Option<i281>> comes in handy. In the case of floats the errors will be returned as predefined constants such as NAN. Let's test it!

#[test]
fn test_add() {
    let int1: Number = 1.into();
    let int2: Number = 2.into();
    assert_eq!(Number::Int(3), int1 + int2);

    let fl2: Number = 2.0.into();

    if let Number::Float(fl_res) = int1 + fl2 {
        assert!((fl_res - 3.0).abs() < std::f64::EPSILON);
    } else {
        panic!("Float expected");
    }
}

Subtraction and multiplication are very similar, in the case of division we need to check if the reminder of dividing two integrals is 0 - if yes, the result will also be 0. We also have to watch for division by 0 operations. checked_rem will handle both for us:

impl Div for Number {
    type Output = Number;
    fn div(self, rhs: Self) -> Self::Output {
        match (self, rhs) {
            (Number::NaN, _) | (_, Number::NaN) => Number::NaN,
            (Number::Int(l), Number::Int(r)) => {
                let rem = l.checked_rem(r);
                match rem {
                    Some(r) if r > 0 => Number::Float(self.into()) / Number::Float(rhs.into()),
                    Some(_) => Number::Int(l / r),
                    None => Number::NaN
                }
            },
            _ => {
                let l: f64 = self.into();
                let r: f64 = rhs.into();
                (l / r).into()
            }
        }
    }
}

With this simple approach, we can make easy calculations that will preserve integers as long as possible and will gracefully handle errors.

Bonus

A cautious reader may have noticed the impl From<Number> for f64 implementation does not do any checks when converting 128 into f64. How can we safely convert a 128-bit integer into an 64-bit float? According to IEEE-754, the 64-bit floating numbers are stored as:

11 bit exponent
53 bit precision number

Quoting after Wikipedia:

The 11 bit width of the exponent allows the representation of numbers between 10^−308 and 10^308

So there will be rounding errors, but we can store a maximum i128 number; we can even count atoms in the universe! Let's check what happens if we convert 128::MAX:

fn main() {
    println!("i128::MAX: {},\ni128::MAX as f64: {}", std::i128::MAX, std::i128::MAX as f64) 
}

Output:

i128::MAX: 170141183460469231731687303715884105727,
i128::MAX as f64: 170141183460469230000000000000000000000

Sources:

https://rtfeldman-rust-workshop.netlify.app/1.2
https://crates.io/crates/rug
https://www.wolframalpha.com/input?i=number+of+atoms+in+universe
https://en.wikipedia.org/wiki/Double-precision_floating-point_format

Building Zerocalc, part III - errors and grammar

Michal Ciesielski — Sun, 23 Jun 2024 08:45:16 +0000

The basic parsing method presented in part II works well for simple expressions that consist of binary operators and literals. Our calculator must support more complex expressions, including unary operators, parenthesis, and function calls. In addition, we'd like to be able to communicate parsing errors to the user pointing them to the potential source of the problem.

Errors

When a parser hits an issue, the user will usually get a message explaining the problem the parser hit and where in the code it happened:

To return such errors, we need to store the message and the span of input code the error relates to:

pub struct Span {
    pos: usize,
    len: usize
}

impl Span {
    pub fn new(pos: usize, len: usize) -> Self {
        Span {
            pos,
            len
        }
    }
}

pub struct Error {
    message: String,
    span: Span
}

impl Error {
    pub fn new(message: &str, span: Span) -> Self {
        Error {
            message: String::from(message),
            span
        }
    }

Sometimes the error is detected by a function coming from a library we use and the error type is different than our Error. In this case, it will be handy to wrap that error in our Error structure to have consistent error flow through the call stack:

impl Error {
    pub fn wrap<T: Display>(t: T) -> Self {
        Error {
            message: format!("{t}"),
            span: Span::new(0, 0)
        }
    }
}

We can use the wrap method with Rust's handy Result::map_err method:

pub fn parse_int(input: &str) -> Result<i128, Error> {
    input.parse().map_err(Error::wrap)
}

Grammar

Let's now look into improving our parser to handle more complex expressions. We are following recursive descent parsing (RDP) - but how exactly such a parser should be built? Wikipedia's definition of RDP states:

In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.

We need to build a grammar and then create a procedure for each non-terminal of the grammar. A non-terminal is an element of the grammar defined by other terminals and non-terminals. A terminal is the actual token we read. A grammar for basic addition can be defined as follows:

exp: fact + fact
fact: literal

The exp (expression) consists of two factors and + operator. A factor is a simple literal. Grammar like this defines a single addition operation 2+2. To define a chain of additions, we need to add recursion to the grammar:

exp: fact + exp | fact
fact: literal

This can define anything from a single literal 1 to any number of additions 1+2+3.... The fact exp is on the right-hand side of the fact + exp term is not an accident - parsing left-recursive grammars is more complicated, and for RDP we need to use right-side recursion.

Next, we need to consider operator precedence. The 1+2*3 should be computed as 1+(2*3) and 1*2+3 should become (1*2)+3. It means that for lower precedence operations like + each side can be a literal or a higher-precedence operation. so for + and * we can write:

exp: exp1 + exp | exp1
exp1: fact * exp1 | fact
fact: literal

It's a bit tricky but as the old joke says, "to understand recursion you first need to understand recursion".

Now we can write full grammar for the expressions we want to handle in our calculator. In addition to basic mathematical operations, we want to handle parenthesis, identifiers (which may be constants like pi or e), and functions like sin.

exp: exp1 | empty
exp1: exp2 op1 exp1 | exp2
op1: + | -
exp2: exp3 op2 exp2| exp3
op2: * | / | %
exp3: term op3 exp3 | term
op3: ^
fact: +fact | -fact | (exp1) | func | id | literal
func: id(exp1)

Parsing

The idea for the parser implementation follows the RDP definition: for each non-terminal, we write a function that will parse this non-terminal. The function will return true if parsing consumed a terminal or false if parsing ended with an empty statement. This will help us check whether all sides of the expression returned the actual result. Example function for parsing a non-terminal:

I added comments showing pieces of grammar each function is responsible for:

    pub fn parse(&mut self) -> Result<bool, Error> {
        self.init();
        self.parse_exp()
    }


    // exp: exp1 | empty
    pub fn parse_exp(&mut self) -> Result<bool, Error> {
        match self.next_token.kind {
            lexer::TokenKind::Eof => Ok(false),
            _ => self.parse_exp1()
        }
    }


    // exp1: exp2 op1 exp1 | exp2
    // op1: + | -
    fn parse_exp1(&mut self) -> Result<bool, Error> {
        let has = self.parse_exp2()?;
        match self.next_token.kind {
            kind @(lexer::TokenKind::Add | lexer::TokenKind::Sub) => {
                self.bump();
                if self.parse_exp1()? {
                    self.parse_binary_op(kind)?;
                    Ok(true)
                } else {
                    self.error(ERR_EOF)
                }
            },
            _ => Ok(has),
        }
    }

    // exp2: exp3 op2 exp2| exp3
    // op2: * | / | %
    fn parse_exp2(&mut self) -> Result<bool, Error> {
        let has = self.parse_exp3()?;
        match self.next_token.kind {
            kind @(lexer::TokenKind::Mul | lexer::TokenKind::Div | lexer::TokenKind::Mod) => {
                self.bump();
                if self.parse_exp2()? {
                    self.parse_binary_op(kind)?;
                    Ok(true)
                } else {
                    self.error(ERR_EOF)
                }
            },
            _ => Ok(has)
        }
    }

    // exp3: fact op3 exp3 | fact
    // op3: ^
    fn parse_exp3(&mut self) -> Result<bool, Error> {
        let has = self.parse_fact()?;
        match self.current_token.kind {
            kind @lexer::TokenKind::Pow => {
                self.bump();
                if self.parse_exp3()? {
                    self.parse_binary_op(kind)?;
                    Ok(true)
                } else {
                    self.error(ERR_EOF)
                }
            },
            _ => Ok(has)
        }
    }

    // fact: +fact | -fact | (exp1) | func | id | literal
    // func: id(exp1)
    fn parse_fact(&mut self) -> Result<bool, Error> {
        self.bump();
        match self.current_token.kind {
            kind@ (lexer::TokenKind::Add |lexer::TokenKind::Sub) => {
                if !self.parse_fact()? {
                    return self.error("Unary operator needs expression");
                }
                self.parse_unary_op(kind)
            }
            lexer::TokenKind::Lpar => {
                let has = self.parse_exp1()?;
                if self.next_token.kind != lexer::TokenKind::Rpar {
                    return self.error("Missing closing parenthesis");
                };
                self.bump();
                Ok(has)
            },
            lexer::TokenKind::Literal(kind) => {
                self.parse_literal(kind)
            },
            lexer::TokenKind::Eof => Ok(false),
            // etc for id, function...
            _ => self.error(ERR_UNEXP)
        }
    }

I shortened parse_fact a bit but you get the idea. When parsing a terminal, we just add it to the output program I described in the previous post:


    fn parse_literal(&mut self, l: lexer::LiteralKind) -> Result<bool, Error> {
        let val = match l {
            lexer::LiteralKind::Int => self.parse_int()?,
            lexer::LiteralKind::Float => self.parse_float()?
        };
        self.program.push(Expression::Val(val));
        Ok(true)
    }

    fn parse_binary_op(&mut self, kind: lexer::TokenKind) -> Result<bool, Error>{
        let op = match kind {
            lexer::TokenKind::Add => Op::Add,
            lexer::TokenKind::Sub => Op::Sub,
            lexer::TokenKind::Div => Op::Div,
            lexer::TokenKind::Mul => Op::Mul,
            lexer::TokenKind::Mod => Op::Mod,
            lexer::TokenKind::Pow => Op::Pow,
            _ => return self.error("Invalid binary operator")
        };
        self.program.push(Expression::BinaryOp(op));
        Ok(true)
    }

And that's it! We can now parse very complex mathematical expressions.

Sources:

Building Zerocalc, part II - evaluating then parsing

Michal Ciesielski — Sun, 16 Jun 2024 14:33:36 +0000

In part I we built a simple tokenizer while explaining how rustc converts an input text into a stream of tokens. The next step is to transform the stream of tokens into a representation that will be easy to evaluate. This time we will not follow the rustc implementation. The rustc parser is a complex system that produces multiple representations of the code, including abstract syntax tree (AST), high-, mid-, and low-level intermediate language. Those representations are used to perform different checks and transformations such as borrow checking or macro expansion before the low-level code is handed over to LLVM for actual machine code generation. We do not need all that complexity for a simple calculator.

Evaluating

Before we build a parser let's think about what the parser will produce. There are multiple ways of representing and evaluating mathematical expressions such as using an expression tree or following a reverse polish notation. The latter is more interesting as it is closer to what the real machine does.

Let's consider what the machine has to do to add two numbers 1+2

Store 1 in a register
Store 2 in a register
Call the add instruction to add the two registers
Store the result in a register

We can write this as the following pseudo-assembly code. This code uses a stack instead of registers, but the idea is very similar:

push 1
push 2
add // adds 2 numbers from the top of the stack and stores the result back to the stack
pop // get the result from the stack

The above expression can be represented in a reverse polish notation as: 1 2 +. A more interesting example, which requires considering operator precedence, will be 1 + 2 * 3. This example in reverse polish notation will be 1 2 3 * +.

Our calculator will need a representation that can store values and operations on a stack. Let's define two enums for that:

enum Expression {
    Val(i32),
    BinOp(Op)
}

enum Op {
    Add,
    Mul
}

An entire mathematical expression or a program to evaluate is a list of expressions:

type Program = Vec<Expression>;

With this representation evaluating mathematical expressions becomes very simple:

fn evaluate(p: &Program) -> i32 {
    let mut stack: Vec<i32> = vec![];
    for exp in p {
        match exp {
            Expression::Val(i) => stack.push(*i),
            Expression::BinOp(Op::Add) => {
                let a = stack.pop().unwrap();
                let b = stack.pop().unwrap();
                stack.push(a+b);
            },
            Expression::BinOp(Op::Mul) => {
                let a = stack.pop().unwrap();
                let b = stack.pop().unwrap();
                stack.push(a*b);
            }
        }
    };
    //final result is now on the stack
    stack.pop().unwrap()
}

#[test]
fn test_add() {
    let program = vec![
        Expression::Val(1),
        Expression::Val(2),
        Expression::BinOp(Op::Add)
    ];
    assert_eq!(3, evaluate(&program));
}

The above code ignores error checking, such as overflow errors. I will leave it up to the reader to consider solving that issue. Hint: one possible solution is to use a number wrapper that can keep an actual number and the NaN (not-a-number) term.

Parsing

Our parsing algorithm will use information about the precedence of operations. Literal (value) has the highest precedence - if we see it, we immediately store it in our output program. Then we consider, in order, multiplication and addition. We have 2 extra tokens: Eof (end of the input stream) and Unknown (used for initial values of the tokens) - they will have the lowest precedence. Let's define precedence as a function:

fn precedence(token_kind: lexer::TokenKind) -> i32 {
    use lexer::TokenKind::*;
    match token_kind {
        Unknown | Eof => 0,
        Add => 1,
        Mul => 2,
        Literal(_) => 3
    }
}

Our parser, in addition to storing the source being parsed and an output program, needs a few extra things:

a variable to track the current position in the source so that token text can be extracted,
variables to store the current and next token

We will use Cursor structure we defined in part I to tokenize the input string. The lifetime of our parser will be bound to the lifetime of the source code being parsed.

struct Parser<'src> {
    source: &'src str,
    cursor: lexer::Cursor<'src>,
    pos: usize,
    current_token: lexer::Token,
    next_token: lexer::Token,
    program: Program
}

We will also implement a few extra methods, that will help us with parsing:

from_source - a constructor to create the parser from the source code string
init - to initialize parsing
bump - to advance the parser, tracking its position
current_value - to extract the string value of a token using the current position

impl<'src> Parser<'src> {
    fn from_source(source: &'src str) -> Parser<'src> {
        Parser {
            source,
            cursor: lexer::Cursor::new(source),
            pos: 0,
            current_token: lexer::Token::new(lexer::TokenKind::Unknown, 0),
            next_token: lexer::Token::new(lexer::TokenKind::Unknown, 0),
            program: vec![]
        }
    }

    fn init(&mut self) {
        self.next_token = self.cursor.advance_token();
    }

    fn bump(&mut self) {
        self.pos += self.current_token.len;
        self.current_token = mem::replace(&mut self.next_token, self.cursor.advance_token());
    }

    fn current_value(&self) -> &'src str {
        &self.source[self.pos..self.pos + self.current_token.len]
    }
}

Note the mem:replace function used in the bump method. In Rust, we cannot simply move ownership from one variable to another while leaving the old variable pointing to nothing. We could clone the value, but we only need one copy, so we can use the replace function instead, moving ownership, and assigning a new value in one go. Internally the replace function uses unsafe code to swap references without copying the actual content of the target object.

For the parsing algorithm, we are going to iterate over tokens and:

Compare the precedence of the next token and current token - if the precedence of the next token is higher, call parsing recursively
Push the current expression on the stack.

Akin to the recursive descent parsing method, we will match tokens and delegate parsing each type of token to specialized methods.

    fn parse(&mut self) {
        self.init();
        while self.next_token.kind != lexer::TokenKind::Eof {
            self.parse_next(precedence(self.next_token.kind));
        }
    }

    fn parse_next(&mut self, current_precedence: i32) {
        while precedence(self.next_token.kind) >= current_precedence {
            self.bump();
            match self.current_token.kind {
                lexer::TokenKind::Add => self.parse_binary_op(Op::Add),
                lexer::TokenKind::Mul => self.parse_binary_op(Op::Mul),
                lexer::TokenKind::Literal(_) => self.parse_literal(),
                _ => (),
            }
        }
    }

    fn parse_binary_op(&mut self, op: Op) {
        //continue parsing while tokens are of higher or equal precedence
        self.parse_next(precedence(self.current_token.kind));
        self.program.push(
            Expression::BinOp(op)
        );
    }

    fn parse_literal(&mut self) {
        let i: i32 = self.current_value().parse().unwrap();
        self.program.push(
            Expression::Val(i)
        );
    }

Let's check if it works:

#[test]
fn test_parse() {
    let source = "1+2*3";
    let expected = vec![
        Expression::Val(1),
        Expression::Val(2),
        Expression::Val(3),
        Expression::BinOp(Op::Mul),
        Expression::BinOp(Op::Add)
    ];
    let mut parser = Parser::from_source(source);
    parser.parse();
    assert_eq!(expected, parser.program);
}

That's it! Our basic parser is ready to be enhanced with more operations and proper error handling.

Sources:

Building Zerocalc, part I - rustc lexer and a lexer in rust

Michal Ciesielski — Sat, 01 Jun 2024 19:39:26 +0000

After reading The Rust Programming Language book and implementing a few exercises, it's time to write a real application. I want to write something I can use myself, which is not yet another "Todo" list. So I decided to build... yet another calculator!

The calculators I enjoy using are the notebook-like ones such as Insect or Parsify. I found this to be a good project idea for learning a new programming language. Building such a calculator requires a parser implementation and UI implementation. Once the basic calculator is done, enhancements and technology exploration are endless possibilities. Consider a currency conversion feature that takes real-time data from some online currency exchange service. Implementing it would involve REST API calls, async code, and/or threading.

To drive our implementation, we will use this very simple expression:

123+4

The first thing our calculator needs to do is to parse this expression. A common way to do it is to break parsing into two phases:

Processing text into a stream of tokens
Building a graph representing the expression (the abstract syntax tree).

In this post, we will focus on tokenization. There are many ways to do tokenization, including using regular expressions or generating tokenizer code with generators such as flex. But what if we check how rustc's parser does it?

Rustc uses straightforward token representation:

pub struct Token {
    kind: TokenKind,
    len: usize
}

Note there is no token value or token position stored. We'll later see how the parser can retrieve the token's value using just the length of the token.

TokenKind identifies the type of token. Rustc defines 39 token kinds. For our simple expression, we need much less, however, the general idea remains the same:

pub enum TokenKind {
    /// 123, 0.123, "abc" etc.
    Literal(LiteralKind),
    /// +
    Add,
    /// not recognized
    Unknown,
    /// end of input
    Eof,
}

Some token types need additional parameters, for example, in the case of literal, we need to know whether this is an integer, floating point number, string, etc. To parse our sample expression we need at least integers:

pub enum LiteralKind {
    Int,
}

Actual rust literals are more complex: an integer needs information about its base (for binary, decimal, octal, or hex numbers) and the length of its suffix so that 12u32 can be properly recognized as a 32-bit unsigned integer. All this information is stored in the parameters of the literal enum.

Tokenization is done by a structure called Cursor which also is very minimalistic:

pub struct Cursor<'a> {
    chars: Chars<'a>,
    len_remaining: usize,
}

impl Cursor<'_> {
    fn new(input: &str) -> Cursor<'_> {
        Cursor {
            chars: input.chars(),
            len_remaining: input.len(),
        }
    }
    //...

The Chars type from the Rust standard library implements the Iterator trait over a str slice. Cursor uses this iterator to advance over the input string with the bump method. It also uses it to calculate the length of the token; the length of the token is a difference between the previous length of input and the remaining length of input. This calculation is done by the pos_within_token method. Once a token is parsed, the remaining length is updated (reset_pos_within_token).

    // impl Cursor continued
    fn new(input: &str) -> Cursor<'_> {
        Cursor {
            chars: input.chars(),
            len_remaining: input.len(),
        }
    }

    fn bump(&mut self) -> Option<char> {
        self.chars.next()
    }

    fn pos_within_token(&mut self) -> usize {
        self.len_remaining - self.chars.as_str().len()
    }

    fn reset_pos_within_token(&mut self) {
        self.len_remaining = self.chars.as_str().len();
    }
}

Let's see how this may work for our input expression 123+4. The initial length is 5. If we stop at +, the remaining length will be 2, so pos_within_token will return 3 which is the actual length of 123 literal.

Before we start tokenizing we need one more utility - the ability to sneak preview the next character before we advance the cursor. This helps to determine the token kind. For example, if we see / it's good to know if what follows is / (regular comment), // (doc comment), or * (block comment).

    // impl Cursor continued
    fn first(&self) -> char {
        self.chars.clone().next().unwrap_or(EOF_CHAR)
    }

    fn second(&self) -> char {
        let mut iter = self.chars.clone();
        iter.next();
        iter.next().unwrap_or(EOF_CHAR)
    }

    fn third(&self) -> char {
        let mut iter = self.chars.clone();
        iter.next();
        iter.next();
        iter.next().unwrap_or(EOF_CHAR)
    }

That looks like a lot, but apparently, cloning the cursor and advancing it optimizes very well; Rust focuses on operating on a stack with types of known size which I guess makes generating optimized code easier.

Now let's tokenize our expression:

impl Cursor<'_> {
    fn advance_token(&mut self) -> Token {
        let char = match self.bump() {
            Some(c) => c,
            None => return Token::new(TokenKind::Eof, 0),
        };
        let token_kind = match char {
            '0'..='9' => {
                let literal_kind = self.number();
                TokenKind::Literal(literal_kind)
            }
            '+' => TokenKind::Add,
            _ => TokenKind::Unknown,
        };
        let token = Token::new(token_kind, self.pos_within_token());
        self.reset_pos_within_token();

        token
    }

We start with reading the next character (and advancing the cursor at the same time). If that operation does not return value, it means we reached the end of input so we need to return the final Eof token. Then we need to decide what kind of token we are parsing. That may require looking ahead with one of first/second/third methods as in the case of comments. For our simple 123+4 expression, it's enough if we check if we deal with a digit or a + sign. If we face something surprising, we return Unknown letting client code decide what to do.

Parsing Int literal in our example is very simple:

    fn number(&mut self) -> LiteralKind {
        loop {
            match self.first() {
                '0'..='9' => {
                    self.bump();
                }
                _ => break,
            }
        }
        LiteralKind::Int
    }

Actual Rust literals are much more complex - different string types, different number representations, etc. Rustc's lexer advances over input and matches received characters against patterns, building an understanding of what type of literal or other token kind it deals with. This method of top-down parsing is called Recursive Descent Parsing.

To make our tokenizer easier to use, we can wrap Cursor into the Iterator trait. There is a nice utility in Rust std library to do this, namely the iter::from_fn:

pub fn tokenize(input: &str) -> impl Iterator<Item = Token> + '_ {
    let mut cursor = Cursor::new(input);
    std::iter::from_fn(move || {
        let token = cursor.advance_token();
        if token.kind != TokenKind::Eof { Some(token) } else { None }
    })
}

How one uses this tokenizer? Let's write a test to show it:

#[test]
fn test_cursor() {
    let input = "123+4";
    let mut pos = 0;

    let mut cursor = tokenize(&input);

    let Token { kind, len } = cursor.next().unwrap();
    let token_val = &input[pos..pos + len];

    assert_eq!(TokenKind::Literal(LiteralKind::Int), kind);
    assert_eq!(token_val, "123");

    pos = pos + len;

    let Token { kind, len } = cursor.next().unwrap();
    let token_val = &input[pos..pos + len];

    assert_eq!(TokenKind::Add, kind);
    assert_eq!(token_val, "+");

    pos = pos + len;

    let Token { kind, len } = cursor.next().unwrap();
    let token_val = &input[pos..pos + len];

    assert_eq!(TokenKind::Literal(LiteralKind::Int), kind);
    assert_eq!(token_val, "4");

    assert_eq!(None, cursor.next());
}

Client code must track the position of the token within the input string. This allows to read the actual value of the token directly from the input string and tokenization does not require copying any of the input string.

And that is it! The rest of the rustc tokenizer code is mostly heuristics that allow the tokenizer to identify tokens.

My first job as a software engineer was in a software quality company where I worked on a C++ code analyzer. We've been working with a parser that was generated using bison/flex-like tools. Since C++ is a context-sensitive language, it cannot be expressed as a simple LL(k) grammar. As a result, our parser was a stack of patches and hacks on top of auto-generated code and a real nightmare to work with. After a while, we switched to a third-party parser which was implemented as a recursive descent parser. I enjoy the clarity and flexibility of this approach to parsing code.

Sources:

Lifetimes in Rust - one difficult exercise

Michal Ciesielski — Sun, 26 May 2024 19:02:38 +0000

The excellent online book Rust By Practice in the Lifetime chapter has a difficult exercise called... A difficult exercise. I struggled with it for a while, then looked at the solution and - I still did not get it. Not until I read the chapter on ownership from The Rustonomicon. Let's dive into the problem and describe the solution in detail.

First we need to go over the code in the exercise and explain what it does. It defines a structure called List; that structure has nothing to do with an actual list, it is just a container for a single object. The object it holds is an instance of a Manager structure. The List gives mutable access to the Manager but not directly - instead it creates container called Interface that holds mutable reference to the Manager. This is done in get_interface method that returns Interface. The only method of Interface is noop(self).

struct Interface<'a> {
    manager: &'a mut Manager<'a>
}

impl<'a> Interface<'a> {
    pub fn noop(self) {
        println!("interface consumed");
    }
}

struct Manager<'a> {
    text: &'a str
}

struct List<'a> {
    manager: Manager<'a>,
}

impl<'a> List<'a> {
    pub fn get_interface(&'a mut self) -> Interface {
        Interface {
            manager: &mut self.manager
        }
    }
}

fn main() {
    let mut list = List {
        manager: Manager {
            text: "hello"
        }
    };

    list.get_interface().noop(); // <--- Interface created and used here.

    println!("Interface should be dropped here and the borrow released");

    use_list(&list);
}

fn use_list(list: &List) {
    println!("{}", list.manager.text);
}

When trying to run this code, rust fails to compile it with the following error:

According to rust's lifetime rules, borrow is valid from it's declaration to it's last use. Last use of Interface is when noop() is called in the main function. It should be similar to this example:

fn main() {
    let mut x = 1;
    let y = &mut x;
    // print!("{x}"); <-- this will not compile, 
    //                    x is mutably borrowed so print cannot borrow it again

    *y = 42; // last use of y

    print!("{x}"); // x no longer borrowed, can be used
}

So why it does not work? Let's analyze reference lifetimes in the main function. I am using similar notation that the The Rustonomicon is using, showing scopes of each lifetime. Note this is not valid rust syntax!

fn main() {
    'a {
        let mut list = List { // list has lifetime 'a
            manager: Manager {
                text: "hello"
            }
        };        

        'b {
            list.get_interface().noop(); // Interface uses lifetime 'b
        }

        // 'b is out of scope
        println!("Interface should be dropped here and the borrow released");

        use_list(&list);
    } // lifetime 'a ends here
}

But... this still does not explain the issue. 'b lifetime is short and ends before use_list is called. To understand what happens we need to look closer at get_interface() method declaration:

impl<'a> List<'a> {
    pub fn get_interface(&'a mut self) -> Interface {
        Interface {
            manager: &mut self.manager // what is lifetime of this?
        }
    }
}

Rust lifetime elision allows us to skip some lifetime parameters. If we make all lifetimes explicit, the declaration will look as below

impl<'a> List<'a> {
    pub fn get_interface(&'a mut self) -> Interface<'a> {
        Interface::<'a> {
            manager: &'a mut self.manager
        }
    }
}

The lifetime 'a from above snippet will be the same as the lifetime 'a from main function since we are calling this method on list object in main. This means Interface.manager will hold reference with 'a lifetime. And if you look inside Manager struct it uses this lifetime in text reference. Recall the implementation of Interface:

struct Interface<'a> {
    manager: &'a mut Manager<'a>
}

Even if we stop using Interface, the manager reference is still alive as it is using 'a lifetime, which in get_interface will be bound to List's lifetime also called 'a here.

How do we fix this? We need to untangle Interface's lifetime from Manager's lifetime. Let's introduce separate lifetime 'b for Interface's reference. I will consistently use 'a and 'b which should make it easier to track which lifetime is which.

struct Interface<'b, 'a> {
    manager: &'b mut Manager<'a> // reference with lifetime 'b
                                 // holding Manager with lifetime 'a
}

impl<'b, 'a> Interface<'b, 'a> {
    pub fn noop(self) {
        println!("interface consumed");
    }
}

We could bind the lifetimes declaring 'a: 'b to indicate 'a outlives 'b, but this is not necessary in this example.

The last thing remaining is to create Interface instance with proper lifetimes. List uses only one lifetime 'a, but we can extend get_interface method to take another generic lifetime parameter 'b.

impl<'a> List<'a> {
    pub fn get_interface<'b>(&'b mut self) -> Interface<'b, 'a> {
        Interface {
            manager: &mut self.manager
        }
    }
}

Now we explicitly told rust to use 'b lifetime for reference inside Interface. Once usage is done, rust can release the reference and list becomes available.

The Rustonomicon describes itself as the awful details that you need to understand when writing Unsafe Rust programs. In this example we did not do any unsafe rust, yet the knowledge from that book was very helpful. I recommend reading The Rustonomicon even if you only plan to play safe.

Sources:

How does Rust go “from” here “into” there

Michal Ciesielski — Sun, 19 May 2024 19:39:34 +0000

I have heard a lot of (mostly) good things about the Rust programming language. Recently, I decided to give it a try and learn Rust basics myself.

When learning something, I am always curious how things work inside. It is no different this time; I keep stumbling upon the question: But how does it work? I decided that this time I will start blogging about my findings.

One of features that caught my attention is dependency between From and Into traits. The documentation says:

One should always prefer implementing From over Into because implementing From automatically provides one with an implementation of Into thanks to the blanket implementation in the standard library.

It means that when we will implement From trait the into() method invocation will magically work:

struct A(i32);

struct B(i32);

impl From<A> for B {
    fn from(value: A) -> B {
        B(value.0)
    }
}

fn main() {
    let a = A(1);
    let b: B = a.into();
    assert_eq!(1, b.0)
}

Where does the into method come from? The answer is in source code of Rust std library (removed macros and comments for readability):

impl<T, U> Into<U> for T
where
    U: From<T>,
{
    fn into(self) -> U {
        U::from(self)
    }
}

It is blanket implementation indeed - converts one generic type into another generic type. But how does compiler know what trait to use when it sees into call? My struct does not implement any Traits nor is it bound to them in any way.

The answer lies within compiler's trait resolution algorithm. When the compiler looks for what method implementation to use, it first collects candidates (candidate assembly). The compiler searches for impls/where-clauses/etc that might possibly be used to satisfy the obligation (the term "obligation" is a trait reference that compiler is trying to resolve). As part of this process, it is checking if instantiation of a generic trait will satisfy obligation (see collect_trait_impls function in src/librustdoc/passes/collect_trait_impls.rs). Once compiler collects all candidates it then attempts to resolve ambiguities. If it can successfully resolve ambiguities, it verifies the candidate can be used with specified types. And voila! That's how from become into.

Sources: