On Tue, Apr 12, 2016 at 4:27 AM, Brent Royal-Gordon <br...@architechies.com> wrote: >>> (On the other hand, it might be that I'm conceiving of the purpose of >>> `limitedBy` differently from you—I think of it as a safety measure, but you >>> may be thinking of it specifically as an automatic truncation mechanism.) >> >> Hi Brent, >> >> Could you explain what kind of safety do you have in mind? Swift will >> guarantee memory safety even if you attempt to advance an index past >> endIndex using the non-limiting overload. > > By "safety" here, I mean what I will call "index safety": not accidentally > using an index which would violate the preconditions of the methods or > properties you are planning to use it with. I think it's too easy to > accidentally overrun the permitted range of indices, and the API should help > you avoid doing that.
Hi Brent, Thank you for the explanation. Assuming that I am interpreting you correctly, I can't agree with your conclusions though. I want to make a point that avoiding precondition violations by removing preconditions is not the solution. When you design an API, it frequently has some constraints on the arguments or on the execution environment, which, when violated, prevent the API from performing the operation correctly. As an API designer, you document these constraints, but for the implementation you have two choices: 1. You rigorously check the constraints, and return back some indicator of the failure back to the caller (a nil return, a thrown error etc.) This decision makes the checks guaranteed, permanent, documented part of your API behavior. Users can now rely on these checks for their normal logic. In this case, the constraints are not preconditions that the user is required to satisfy. 2. You perform the operation anyway, relying on the caller to satisfy the constraints. The constraints become preconditions. The implementation can still check some of the constraints for either QoI reasons or memory safety reasons. Apart from preventing memory safety violations, the implementation is not required to check the constraints. Now the question becomes, given a certain API design problem, how do you make a choice between (1) and (2)? In some cases, the answer is clear: - You can be forced to make your constraints into checks in API behavior. Example: a network i/o operation can fail. This is a completely normal thing that networks do sometimes, and the caller of networking code should be expected to deal with networking failures, or such code can't work on a real network. - Some preconditions just can't be checked at all, or can't be checked in time that is acceptable for the intended API purpose. A trivial example is UnsafePointer.pointee (we can't know whether the pointer actually points to an instance of a correct type). Another example is sort predicates -- we can't check that the order defined by the predicate is indeed a strict weak ordering for all values of the type. We can check that the predicate defines a strict weak order for all values in a particular dataset, but that requires O(n^2) time while sort() complexity is O(n log n). What about those cases when both (1) and (2) are implementable? There exists a trade-off between making the API "resilient" to programming mistakes and hiding bugs by not stopping the application when an issue happens. We are very conservative in Swift about hiding errors. If your APIs document that they check preconditions and trap if they are not satisfied, then developers can rely on it, and you are not allowed to weaken remove the checks in future. If the app can recover from a precondition failure, the recovery path just becomes a part of the API behavior. You can end up with a system where every API can signal failure back to the calling code. Now users have to handle these failures. There are two ways to handle them: - force-unwrap, or 'try!'. - follow the advice of people who advocate never using force-unwrap and 'try!'. The code that does so will likely have a lot of untested, untestable, and dead branches that try to deal defensively with situations that can't happen, but the API forces them to do so anyway. I don't think either option leads to good code. Thus, it is only reasonable that we design the API based on a purpose that we intend for this API. Let's talk about how this applies to Collection. For example, Collection APIs in question that work with indices are primitive APIs that the rest of Collection APIs build upon. One of these APIs, basically the reason why indices exist, is Collection.subscript(Index). Today the behavior is unspecified if the index is not valid. If we follow the principle that you outlined: > not accidentally using an index which would violate the preconditions of the > methods or properties you are planning to use it with. Collection.subscript(Index) should return an optional. Does this match your expectations? If so, how do you imagine even trivial algorithms written? for i in data.indices { data[i]! = data[i]! * 2 // assume that 'data[i]!' can be made settable. } This code has two force-unwraps in it, despite being completely safe. If you follow the "never force-unwrap" school of thought, then you end up with two branches, and an error return from this function, that are dead, untestable code. If every API can fail, then you can't write useful code. You need to have some fundamental basis that you can rely on, and trust to operate correctly. The primitive Collection APIs are the basis of the Collection API. If they would be burdened with required range checks, then, just as you are saying, the code would be full of redundant range checks. For example, UnsafeBufferPointer would also be burdened with them. > I think it's too easy to accidentally overrun the permitted range of indices, > and the API should help you avoid doing that. I wholeheartedly agree that APIs should help you to avoid making mistakes. There are multiple ways in which they can do so: 1. (best) Make wrong code not compile. Swift has a strong type system that allows us to express complex constraints between types, preventing some mistakes from being compiled. 2. Check preconditions where it is possible (implementable), and when the performance hit is reasonable, and deterministically trap as soon as the violation was detected. Unfortunately, validity of indices is a complex dynamic property of the index-collection instance pair. We can't encode it in the static type system. Consider the following example: --- var a = [1, 2, 3] let i: Int = a.check(a.startIndex) a.removeAll() a[i] // trap --- Ok, mutation can invalidate indices. Can immutability help? --- let a = [1, 2, 3] let b: [Int] = [] let i = a.check(a.startIndex) b[i] // trap --- Since it is not possible to encode the validity relationship in the type system, we want to encourage these operations to trap if they detect violations. Now let's go back to the demangling algorithm. We know that we have weaknesses in the String parsing, and it is important for us to know how well we are covering these use cases, and how we need to improve. I think this is a great problem. I implemented it using three different approaches: https://gist.github.com/gribozavr/ed95f71b762d25bee2991dd9c0191b34 A high-level point that I'd like to make is that when using collections, you need to make use of algorithms to the biggest extent possible. This allows to express the semantics of your operation in your domain using a high-level vocabulary. I would like to draw attention to the following part: // Approach #3: change Collection.index(_:stepsFrom:limitedBy:) to return an // optional index. // // This method has to perform the range check to stop advancing the index when // it reaches the limit. Currently it just discards the information about // whether it reached the limit or not. Instead, it can cheaply return it to // the caller. // // Note that the same logic does not apply to other // Collection.index(_:stepsFrom:) overloads. We will change the index(_:stepsFrom:limitedBy:) overload to return an optional, and we will see what other implications it has, and how it fits into the rest of the system. Thanks again, Brent. Dmitri -- main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if (j){printf("%d\n",i);}}} /*Dmitri Gribenko <griboz...@gmail.com>*/ _______________________________________________ swift-evolution mailing list swift-evolution@swift.org https://lists.swift.org/mailman/listinfo/swift-evolution