Implementing a multi-user spreadsheet. Change Log
Assignment Released (2024-04-03)
Assignment 2
COMP6991 24T1 Assignment 2 Runthrough
Copyright By PowCoder代写 加微信 powcoder
One of the earliest “killer apps” for a computer was VisiCalc. Released on the I in 1979, it was the first spreadsheet program, and it was a huge success. It was so successful that it was the main reason that people bought I computers. In this assignment, you will be implementing a simple spreadsheet program in Rust.
Specifically, you will build a server program which is controlled through simple commands. Those commands will allow you to set and get values within a spreadsheet. Since values in the spreadsheet may be dependent on other values, you will also need to manage cells being calculated and re-calculated.
The goals of this assignment are:
1. TogetexperiencewithRust’sconstructsformanagingconcurrency.
2. Todesignandstructureaprogramcapableofcorrectlyand(somewhat)efficientlymanagingconcurrentinteractions. 3. Tohavefuncreatinganaestheticandinterestingapplication.
We want to also be explicit about what the goals aren’t:
1. Toassessyourabilitytowritespreadsheetformulae.Specifically,whileweuseaparticularlanguagetowriteformulae,you don’t need to learn to use it yourself.
2. Toassessyourabilitytowritelargeamountsofuselesscruftsolelyforustomarkyouon.Whereyou’rewritingcode,wehavea reason for it. Where you’re writing text, it’s because we want to genuinely understand your thinking.
Part of this assignment involves submitting a mark_request.txt file. This gives you an opportunity to talk about both the highlights and limitations of your design. If you can identify limitations in your design, we’ll give you some marks even where we would have otherwise taken them away, since identifying sub-optimal design and learning from it is part of the challenge of the assignment.
An Introduction to Spreadsheets
A spreadsheet is a grid of cells, each of which can contain a value. Cells are addressed using the “A1” method. Each cell has a column and a row. The characters in the column are the column name, and the number is the row number. For example, the cell in the first column and the first row is “A1”. The cell in the second column and the first row is “B1”. The cell in the first column and the
second row is “A2”. Importantly, the cell in the 27th column and the 1st row is “AA1”. (after AA comes AB, AC, and so on until BA…). Because it is surprisingly difficult to write this logic yourself; we have provided a function called column_number_to_name to do this conversion for you.
In this program, the logic for spreadsheets will be executed using the Rhai Language. Rhai is a small, fast, safe and embeddable scripting language that feels very similar to Rust. We have provided a type CommandRunner which manages your interactions with this language for you. You do not need to understand the Rhai language, nor know how to use it. You will only need to use the simple CommandRunner type in your assignment.
How your program will work
We have provided you with starter code. You must use this code as a starting point for your assignment. The starter code manages all the input and output for you, such that you only need to implement the rsheet library. That is, you will not have to modify main.rs. The starter code explains exactly what you will need to do.
To use the starter code, you have two options:
To start with, you can run the starter code with no arguments. This will let you enter commands, and see what effect they have. This is the easiest way to run your code, and is generally recommended.
Alternatively, you can run the starter code with a single argument, which is a network address. This will cause your program to start receiving instructions over a network connection. Running 6991 rsc
We have provided a reference solution to check behaviour you are unsure of. You can run the reference solution with the command: 6991 rsheet.
How We’ll Code
In this assignment, we won’t be providing Design Excellence like in Assignment 1. That’s mainly because apart from just “add more features”, there wasn’t really anything we felt would significantly add to the experience of doing this assignment.
Markers also won’t be providing general feedback over your whole assignment. We’ve done this for a few reasons:
We’ve already had an opportunity to give general Rust feedback to you on Assignment 1
This assignment focusses more on concurrent design than on general design.
Necessarily, feedback for this assignment will be given after the end of term so we often find students aren’t as interested in general feedback.
Instead, we’ll be asking you to answer 5 questions to reflect on your design. In that, you’ll point out some particular areas of your code; and where necessary we’ll leave feedback on those answers and those bits of code.
Furthermore, if you have particular questions about your design; we encourage you to leave them in the mark_request.txt file. Your marker will reply to those questions. Notably, you only need to leave questions if you want to. Also importantly, we’ve asked markers to be as specific with their answers as you are with your questions. For example, “how could I have done better?” is a pretty general question, we’ll give some general answers. “in my Blah struct I returned a `Box`, is there a better way to do that?” is a much more specific question.
The Tasks To Complete
Stage 1. Basic Get and Set (15%)
The basis of this assignment is two commands: get and set. These allow you to interact with the state of the spreadsheet. You can use the Manager trait to receive these commands, and to communicate back to the user. You will receive these commands as strings. You will send the user back a rsheet_lib::replies::Reply enum (which contain a message with either a cell’s value, or an error).
For now, you will only have one user talking to your code, so you do not need to handle multiple connections.
The get command takes one argument: a cell name. It returns the value of that cell. By default, all cells are CellValue::None until modified. Cells can have one of four types of values: None (the default), an integer (i64), a string (String), or an error (also represented as a String).
The set command takes the name of a cell, and then a string (which might contain many spaces!) which is an expression to evaluate. It sets the cell to the given value. The set command has no output. That said, the set command must occur atomically. In other
words, if you receive a set command, then a get command; the set command must finish before the get command starts.
Given a set command you can use the rsheet_lib::command_runner::CommandRunner struct, and its run method to evaluate the
expression. This will take the expression, and evaluate it correctly; returning a CellValue. For example, it will take 2 + (4 * 6) and evaluate that to 26.
A note on the spreadsheet language
The spreadsheet formula language is Rhai. You do not need to learn any Rhai to be able to complete this assignment, but if you’re interested, it’s a Rust-like scripting language. All the usual arithmetic operations are supported, as well as string concatenation (“abc” + “def” == “abcdef”).
We’ve also implemented two useful built-in functions for you:
sum(arg) takes a number, list, or list of lists; and returns the sum.
sleep_then(time, value) takes a time (in ms) and a value. It waits the given number of milliseconds, then executes. Error Handling
If the run command encounters an error, it will return a CellValue::Error. For now, you should treat this like any other cell value.
If you receive an invalid cell reference (i.e. get r2d2) you should return a Reply::Error.
If you receive an invalid command (i.e. frobnicate B1), you should return a Reply::Error
A simple example:
A more complex example:
A note on –mark-mode
The starter code includes a variable, –mark-mode. In this mode, any errors you send back to the user are replaced with a standard error message. You should write descriptive error messages in your program, and they can be completely different to the reference solution. During marking, only the fact you’ve sent back an error message will be checked, not the contents of the error.
Stage 2. Using Variables in Calculations (15%)
A spreadsheet isn’t very useful unless it can actually use variables. In this stage, you will add support for variables into rsheet.
Variables can be used in the set command simply by referencing them. For example, set A2 A1 + 1 means “set the A2 cell to be equal to A1 + 1”. To make this work, you should use the cell_runner::CommandRunner::find_variables function to find variables referenced inside a command, and then pass them to the cell_runner::CommandRunner::run function.
An important note, which only applies until Stage 5 (at which point you will lose this guarantee) is that you can assume that the cells on which other cells depend will never change.
This means you don’t need to handle the dependencies changing, and updating them until stage 5. There are three types of variables you should support:
Scalar Variables: these are individual cells; like A1. They will contain a single value, either a string or an integer.
set A1 3 + 5 get A1
set ASDF a
Error: Invalid Key Provided
set A1 this-isn’t-code
A1 = Error: “‘this’ can only be used in functions (line 1, position 1)”
set A1 set A2 get A1 A1 = 2 set A1 get A2 A1 = 4
3 # <---- this will never happen # <---- this will never happen
Vector Variables: these are a vertical or horizontal list of cells; spelled A1_A3 or A1_C1. These are represented by a 1- dimensional list.
Matrix Variables: these are rectangular selections of cells; like A1_B3. They will contain a list of lists; where each sub-list corresponds to a row (not a column) in the spreadsheet.
Here is an example of what certain variables would equate to if the sheet was:
In the image, the blue outline is A1_C1 and the green outline is A1_B3. These would be represented as [1, 2, 3] and [[1, 2], [4, 5], [7, 8]] respectively.
Stage 3. Multiple Readers and Writers (20%)
In this section, you will support more than one reader/writer accessing your spreadsheet simultaneously. Because you're using a terminal to interact with the spreadsheet, we have a special syntax that will allow you to pretend to be from multiple clients at once. This syntax is already implemented, you do not need to do anything to get it to work.
To use this special syntax, you'll do something like this:
The part before the : uniquely indicates a "sender". If you type a new sender, a new connection will be made to your sheet. If you reuse an existing sender, it will send another command over the same connection
One important part of this assignment is that interactions with the sheet from a single observer must happen in order. For example, from snd2's point of view, the set must happen before the get.
Of course, with multiple readers and writers, it's not guaranteed that two different senders's actions will happen in any particular order. To deal with this in testing, we've added a utility for marking called sleep, which ensures a gap of a certain number of milliseconds between commands. Thus:
snd1: set A1 1 snd2: get A1 A1 = ???
isn't guaranteed to say that A1 is set; but the following will.
We've designed all the test cases so that there should be one correct ordering of outputs. There are many other inputs to your program that could have multiple correct orderings, depending on exactly how the threads behave. For example, the following code block could set A1 to 1 or 2.
We will not test you on any of these cases.
Stage 4. Simple Dependency Changes (20%)
snd1: get A1
snd2: set A2 42 snd2: get A2
snd1: set A1 1
snd2: sleep 50 # <--- this is implemented for you in Rhai, you do not need to do this yourself. snd2: get A1
snd1: set A1 1 snd2: set A1 2 snd1: get A1 A1 = ???
In this stage, you will start to deal with simple dependencies. This means, for example, that you'll set B1 A1 * 2 (i.e. B1 = (A1 * 2)). Then, we might change A1. If A1 is set to 3, then B1 must be set to 6. If A1 is set to "blah", then B1 will be an error (since "blah" * 2 causes an error in Rhai).
It is important that these dependency changes happen asynchronously. In other words, say that you've run the following commands: set A1 1
set B1 A1 + 1
Because of the guarantee that sets occur atomically, you're assured that A1 will be equal to 1 by the time that we set B1. However, let's say you now run set A1 2. A1 will be equal to 2 immediately. However, B1 will not yet be equal to 3. That should happen separately, and not necessarily atomically.
Importantly, that means that this code is not guaranteed to have B1 be 3 straight away.
For that reason, we'll usually put a sleep that gives your extra thread enough time to process B1 before we check it.
It's also important to note that for this section, we will only test dependency chains exactly one-cell long. You'll never end up in a situation where C1 depends on B1, and B1 depends on A1 (in this stage). You'll also never be given a circular dependency (in this stage).
A Complex Edge Case
As part of completing this stage, there is a complex edge case which you will need to decide how to handle. This edge case involves the fact that dependencies can be updated in strange orders.
In particular, some cell updates might take some time (emulated using the sleep_then function). Say user A makes an update to a cell that takes 5 seconds to compute. User B then makes an update to that same cell 1 second later, but that update only takes 2 seconds to compute. In rsheet, we want to make sure a more recent update is never wiped out by an older one. Since user B's update was more recent, once user A's update finishes computing (at T=5 seconds), it should not override the value produced by user B.
Here is an example in rsheet code:
It's clear that A1 should be equal to 10 here (since it was the more recent update). That means that B1 should be equal to 11. However, this could be (incorrectly) written out like this:
0 seconds in: B1 got set,
0 seconds in: snd1 sleeps for 5 seconds, waiting to update A1 0 seconds in: snd2 sleeps for 1 second.
1 second in: snd2 sleeps for 2 seconds, waiting to update A1 3 seconds in: snd2 updates A1 = 10
3.001 seconds in: B1 updates to 11
5 seconds in: A1 is (incorrectly!) updated to 5
5.001 seconds in: B1 is (incorrectly) updates to 6.
Even though the user more recently set A1 to 10, it gets set back to 5, because it was slower to compute. Furthermore, any dependencies are also incorrectly set as a result of this mistake.
You will need to account for this edge case in your code.
Stage 5. Multi-Layered Dependencies (20%)
In this stage, you will expand your implementation of Stage 5 so that it works for dependency chains of any length. In other words, you might have a situation where C1 depends on B1, and B1 depends on A1. You might also have tricker dependencies, like where C1 depends on A1_B1, and B1 depends on A1.
For this stage, you are guaranteed that you will never be asked to calculate a circular dependency. That is, there will never be a chain of dependencies such that a cell depends on itself, like set A2 A2 or set A1 A2; set A2 A1.
set B1 A1 + 1
get B1 # <-- potentially B1 is still 2
snd1: set B1 A1 + 1
snd1: set A1 sleep_then(5000, 5) snd2: sleep 1000
snd2: set A1 sleep_then(2000, 10)
Stage 6. Circular Dependencies (10%)
In this stage, you will detect and prevent circular dependencies. That is, when a cell depends on itself. If this happens in a cell, getting the cell should send back an error.
For example:
Design Questions
These questions are worth 15% of your final mark for this assignment. You should answer them in the mark_request.txt file. Each question requires specific references to lines of code (like "src/main.rs:123"). You must not write more than 150 words for each question (the autotests check this).
1. Howdidyourepresentcommandswithinyourprogram?Identifyanalternativerepresentation,andeitherjustifyyourchoice;or explain why that alternative representation would be better.
2. PointtowhereyouhandleScalar,VectorandMatrixvariables.HowmuchduplicationofcodedidtheScalar,VectorandMatrix variables require? Could you have improved this?
3. Pointoutthelinesofcodethatincludeanyconcurrentdatastructures.Contrasthowyourcodewouldlookifyouweretomake this assignment single-threaded.
4. Whatline/linesofcodeshowhowyoudealwiththe"complexedgecase"inpart4.Justifyhowyoursolutionensuresyou'll never have the problem described.
5. Identifythethread(orthreads)you'reusingtoperformthecalculationsofupdateddependencies.Howwouldyouneedto change the code to use multiple threads (the assignment only requires one thread for calculating updates).
Other Information
Submission
See the instructions down the bottom of the page.
Using Other Crates
We are happy for you to use any crate that has been published on crates.io under three conditions:
The crate must not have been authored by anyone else in the course.
The crate must have at least 1000 downloads, excluding the last 30 days.
The crate must not impose license restrictions which require you to share your own code.
If you are in doubt (or think these restrictions unfairly constrain you from using a reasonable crate), ask on the course forum.
Marking Scheme
There are 3 things on which you will be marked:
Mechanical Style (10% of the total marks for this assignment) Functional Correctness (75% of the total marks for this assignment) Design Questions (15% of the total marks for this assignment)
And a detailed analysis is shown below:
1. Mechanical Style (10%):
We will look at your crates, and make sure they:
Compile, with no warnings or errors.
Raise no issues with 6991 cargo clippy.
Are formatted with rustfmt (you can run 6991 cargo fmt to auto-format your crate). Have any tests written for them pass.
set A1 get A1 Error:
set B1 set C1 get C1 Error:
Cell A1 is self-referential
Cell C1 is self-referential
If they do all of the above, you get full marks. Otherwise, we will award partial marks. This is meant to be the "easy marks" of programming.
2. Functional Correctness (75%):
You should pass the provided test cases. We will vary the test case very slightly during marking, to ensure you haven't just hard- coded things; but we're not going to do anything that's not just changing around some commands and re-ordering things.
3. Design Questions (15%):
You should answer the 5 design questions from above. You will be marked based on your response to these questions, and the relevant code and design that you reference as part of your answers.
IMPORTANT: your marks for the assignment are not the percentage of tests which you pass. We'll scale the tests to fit in with the weights described above.
You should complete the questions of the mark_request faithfully. If you do not answer the questions in the file, you will not receive design question marks. The "Questions to the Marker" do not count towards any marks and are entirely optional.
Note that the following penalties apply to your total mark for plagiarism:
0 for the assignment
0 for the assignment
0 FL for COMP6991
Knowingly providing your work to anyone and it is subsequently submitted (by anyone).
Submitting any other persons work. This includes joint work.
Paying another person to complete work. Sub
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com